Hi Peter,
My response here is not formatted as I would wish, but is the imit of my current technology.
I work on SqueakElib, and though I am certainly no expert on E, I am somewhat familiar with it's design and implementation. That said, a comment you made caught my eye...
----- Original Message ---- From: Peter William Lount peter@smalltalk.org
If a number of messages are waiting in the input queue of a process that can only process one message at a time since it's not multi-threaded then those messages are BLOCKED while in the thread. Now imagine another process with messages in it's queue that are also BLOCKED since they are waiting in the queue and only one message can be processed at a time. Now imagine that process A and process B each have messages that the other needs before it can proceed but those messages are BLOCKED waiting for processing in the queues.
This is a real example of what can happen with message queues. The order isn't guaranteed. Simple concurrency solutions often have deadlock scenarios. This can occur when objects must synchronize events or information. As soon as you have multiple threads of execution you've got problems that need solving regardless of the concurrency model in place.
Messages don't get blocked, when they are queued for the Vat (thread/process) to service them. They do get queued when they are sent to a Promise, but it does not affect the Vat. When the Promise resolves, the messages are forwarded to the Vat for processing, in order, so partial msg ordering is maintained.
Msg ordering is partial because of this case: object a in Vat A, object b in Vat B, and object c in Vat C are intercommunicating. Both b and c have references to a. At time t1, b sends msg m1 to a, at time t2, c sends msg m2 to a, but there is higher network latency for b, so m2 gets to a at t3 and m1 gets to a at t4 and they are out of order from the remote invocation order.
I hope this helps. Read more about Elib.
cheers, Rob
Hi Rob,
SqueakElib sounds interesting. With all the links on this thread (pun intended) I have weeks of reading and absorbing to do.
My example below wasn't expressed as clear as it could be.
When a message is sitting in an inbound queue on a process waiting for that process to do get to it it is in essence blocked until it gets processed. If the process is only processing one inbound message at once it is possible for a dead lock to occur when multiple processes are in a similar situation with each other. Both processes waiting for the message that would let them continue which is sitting blocked on the other's queue. That's all. Classic deadlock case.
I don't know if that is any clearer, hopefully it is.
All the best,
Peter
Rob Withers wrote:
Hi Peter,
My response here is not formatted as I would wish, but is the imit of my current technology.
I work on SqueakElib, and though I am certainly no expert on E, I am somewhat familiar with it's design and implementation. That said, a comment you made caught my eye...
----- Original Message ---- From: Peter William Lount peter@smalltalk.org
If a number of messages are waiting in the input queue of a process that can only process one message at a time since it's not
multi-threaded
then those messages are BLOCKED while in the thread. Now imagine another process with messages in it's queue that are also BLOCKED since they are waiting in the queue and only one message can be processed at a time. Now imagine that process A and process B each have messages that the other needs before it can proceed but those messages are BLOCKED waiting for processing in the queues.
This is a real example of what can happen with message queues. The order isn't guaranteed. Simple concurrency solutions often have
deadlock
scenarios. This can occur when objects must synchronize events or information. As soon as you have multiple threads of execution
you've got
problems that need solving regardless of the concurrency model in
place.
Messages don't get blocked, when they are queued for the Vat (thread/process) to service them. They do get queued when they are sent to a Promise, but it does not affect the Vat. When the Promise resolves, the messages are forwarded to the Vat for processing, in order, so partial msg ordering is maintained.
Msg ordering is partial because of this case: object a in Vat A, object b in Vat B, and object c in Vat C are intercommunicating. Both b and c have references to a. At time t1, b sends msg m1 to a, at time t2, c sends msg m2 to a, but there is higher network latency for b, so m2 gets to a at t3 and m1 gets to a at t4 and they are out of order from the remote invocation order.
I hope this helps. Read more about Elib.
cheers, Rob
Peter William Lount wrote:
When a message is sitting in an inbound queue on a process waiting for that process to do get to it it is in essence blocked until it gets processed. If the process is only processing one inbound message at once it is possible for a dead lock to occur when multiple processes are in a similar situation with each other. Both processes waiting for the message that would let them continue which is sitting blocked on the other's queue. That's all. Classic deadlock case.
Deadlock can only happen if one process waits for another. E does *never* wait, there is no wait instruction. Instead, it schedules a message to be run when the desired computation completes. This leaves the Vat free to execute other messages in the meantime. In Croquet, this looks like here:
"future is Croquet's variant for sending async messages" promise := rcvr future doSomething. promise whenResolved:[:value| "do something with the result of the computation this block will executed once the concurrent computation is completed and the response message is being processed in this Vat/Island." ].
Because there is no wait, "classic deadlock" simply cannot happen. There is an equivalent situation which is called "data lock" where circular dependencies will cause a computation not to make progress (because a is computed in response to the completion of b, b in response to completion of c and c in response of completion of a). But there are *major* differences to deadlocks: First, datalock is deterministic, it only depends on the sequence of messages which can be examined. Second, because the Vat is *not* blocked, you are free to send further messages to resolve any one of the dependencies and continue making progress.
In other words, the "control flow problem" of deadlock has been turned around into a "data flow problem" (promises and completion messages) with much less dramatic consequences when things go wrong.
Cheers, - Andreas
Hi Andreas,
Glad you weren't scared off by this thread. :)
(comments below)
On 10/25/07, Andreas Raab andreas.raab@gmx.de wrote:
Deadlock can only happen if one process waits for another. E does *never* wait, there is no wait instruction. Instead, it schedules a message to be run when the desired computation completes. This leaves the Vat free to execute other messages in the meantime. In Croquet, this looks like here:
"future is Croquet's variant for sending async messages" promise := rcvr future doSomething. promise whenResolved:[:value| "do something with the result of the computation this block will executed once the concurrent computation is completed and the response message is being processed in this Vat/Island." ].
This is interesting. Is this already truly parallel in Croquet (or even E for that matter)?
The thing I have always worried about with futures is data versioning. For example, if you have a really big chunk of data that gets passed to another process, how does that work?
In an Erlang model, the process would simply block until it had copied the entire structure and sent it. In a future model you don't have to do that (right?), but don't you have to do a local in-image copy to ensure that the local process doesn't mutate the structure while it's being traversed by the remote reading process? Or perhaps I'm missing something.
Because there is no wait, "classic deadlock" simply cannot happen. There is an equivalent situation which is called "data lock" where circular dependencies will cause a computation not to make progress (because a is computed in response to the completion of b, b in response to completion of c and c in response of completion of a). But there are *major* differences to deadlocks: First, datalock is deterministic, it only depends on the sequence of messages which can be examined. Second, because the Vat is *not* blocked, you are free to send further messages to resolve any one of the dependencies and continue making progress.
In other words, the "control flow problem" of deadlock has been turned around into a "data flow problem" (promises and completion messages) with much less dramatic consequences when things go wrong.
Cheers,
- Andreas
Yes this is indeed quite interesting. Do you have a feel for how complex the futures model is, and how complex it would be to make it truly parallel (assuming it isn't already)?
Too much to read and comment i wish to have time for all of this..
If we have different models for solving different concurrency problems - then its obviously must be at language side, not VM side. Enforcing a particular solution for VM will render other solutions hard or even impossible to implement. And i agree, while Erlang provides a solution for Erlang, its clearly not the silver bullet for Smalltalk.
As for VM: i think we have to deal with parallelism and concurrency problems of VM alone (change memory management and interpreter to support a number of native threads running in parallel). Then rest should be considered at language side.
Then we will stop arguing and implement a libraries each proposing own good/bad solutions to concurrency and be happy :)
Peter William Lount schrieb:
When a message is sitting in an inbound queue on a process waiting for that process to do get to it it is in essence blocked until it gets processed. If the process is only processing one inbound message at once it is possible for a dead lock to occur when multiple processes are in a similar situation with each other. Both processes waiting for the message that would let them continue which is sitting blocked on the other's queue. That's all. Classic deadlock case.
That's exactly my gut feeling about the claims of being deadlock free. As far as I understood it, in E, processes can't "wait" for messages while they are processing one message. Each process (or Vat) has a loop which receives and processes one message at a time. There is no way for a process to wait for something else, it may only send messages to other processes. Wherever you would have a remote message invocation in a traditional distributed system, E forces you to write an explicit continuation: put all your current state in an object and pass a handle that object as part of a message to a remote object. When that remote object has computed a result, this result is sent to your state object, which performs the next steps. I think this is completely homomorphous to traditional remote message invocation in its potential for deadlock, just more complicated to program in...
Cheers, Hans-Martin
On 10/25/07, Peter William Lount peter@smalltalk.org wrote:
When a message is sitting in an inbound queue on a process waiting for that process to do get to it it is in essence blocked until it gets processed. If the process is only processing one inbound message at once it is possible for a dead lock to occur when multiple processes are in a similar situation with each other. Both processes waiting for the message that would let them continue which is sitting blocked on the other's queue. That's all. Classic deadlock case.
But imo this is a design issue. From my experience so far in Erlang programming, processes have a lot of similarities with objects in how you define them. If you find yourself in a situation as you describe here, then you probably have two or more processes hiding in a single process. So the solution, as in Smalltalk when you have a class that should be 2 or more, is to refactor to the correct amount of processes.
squeak-dev@lists.squeakfoundation.org
-
Andreas Raab -
Hans-Martin Mosner -
Igor Stasenko -
Jason Johnson -
Peter William Lount -
Rob Withers