Hi Michael,<div><br></div><div> responding to clear-up some apparent confusions.</div><div><br><br><div class="gmail_quote">On Tue, Apr 28, 2009 at 3:29 PM, Michael van der Gulik <span dir="ltr"><<a href="mailto:mikevdg@gmail.com">mikevdg@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">On 4/28/09, Andreas Raab <<a href="mailto:andreas.raab@gmx.de">andreas.raab@gmx.de</a>> wrote:<br>
<div class="im">> Igor Stasenko wrote:<br>
>> Ask yourself, why a developer, who may want to suspend any process<br>
>> (regardless of his intents) to resume it later, should make any<br>
>> assertions like "what will be broken if i suspend it?".<br>
><br>
> Thus my question about use cases. I haven't seen many uses of suspend<br>
> outside of the debugger. And I don't think that's by accident - suspend<br>
> is very tricky to deal with in a realistic setting that needs to deal<br>
> with asynchronous signals. Most of the time it is a last resort solution<br>
> (i.e., don't care too much about what happens afterwards) not something<br>
> that you would do casually and expect to be side-effect free.<br>
<br>
</div>IMHO Process>>suspend should never by used in "normal" code. It should<br>
only be used from debuggers and system tools. But it should still be<br>
implemented to exhibit the correct behaviour.</blockquote><div><br></div><div>Define "normal" :)</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
The above is exactly the use case where this bug has bitten me. When I<br>
was trying to debug concurrent code, the debugger would simply ignore<br>
Semaphore>>wait and step right over it! The debugger quickly became<br>
useless when I had to manually keep track of which semaphores were<br>
signalled and which weren't.<br>
<br>
Of course, the debugger would also need improvement to make sure that<br>
it doesn't suspend the entire GUI every time its simulated process<br>
waits on a semaphore, but that's another issue.<br>
<div class="im"><br>
> The problem is that in a "real" environment signals are asynchronous.<br>
> Unless you have some way of stopping time and other external interrupts<br>
> at the same time you simply cannot guarantee that after the #suspend<br>
> there isn't an external signal which causes some other process waiting<br>
> on the semaphore to execute before the process that "ought" to be released.<br>
<br>
</div>By my understanding of how suspending a process should work, if a<br>
Process is suspended (by calling >>suspend) then no force on Earth<br>
other than called >>resume on it should resume it again. Any events or<br>
signals on it should accumulate until it is resumed.</blockquote><div><br></div><div>Signals accumulate on Semaphores, not on processes.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div class="im">> For example, just consider a mutex where for some reason ordering<br>
> matters like in Tweak (which does break if processes are not put back in<br>
> the same order in which they were taken off the list): You have a<br>
> process which holds the mutex, two more are waiting. You send #suspend<br>
> to the first (waiting) one, it is off-list. Now the current mutex owner<br>
> leaves that mutex. What should happen? Should the entire mutex stall<br>
> because the process that was supposed to go next was suspended? If it<br>
> proceeds it changes the ordering and that can cause all sorts of<br>
> problems (as I found out when testing some earlier versions of the<br>
> semaphore fixes that weren't quite correct ;-)<br>
<br>
</div>What list? Are you referring to the linked list that a Semaphore<br>
maintains? I would consider the linked list of Processes that<br>
Semaphores maintain to be an implementation detail of Processes and<br>
Semaphores. Your code should be written to be completely oblivious to<br>
it.</blockquote><div><br></div><div>This is more than an implementation detail. Processes are subclasses of Link that add a "myList" instance variable, and Semaphores subclasses of LinkedList. The runnable process lists in Processor are LinkedList instances. So a process is either the sole activeProcess and not on any list, or suspended, and not on any list, or on one of the runnable process lists, or waiting on a Semaphore. The "myList" instance variable is set to the list a process is waiting on or not. So a process is suspended iff myList == nil and the process ~~ Processor activeProcess. None of Processor (the access of the value of (Smalltalk associationAt: #Process), activeProcess (an inst var accessor) and #== or #and: are suspension points so one can write</div>
<div> Process isSuspended</div><div> ^myList == nil and: [self ~~ Processor activeProcess]</div><div><br></div><div>But wait!?!? The Squeak definition is simply</div><div><span class="Apple-style-span" style="white-space: pre; "> Process methods for accessing</span><br>
</div><div><div><span class="Apple-style-span" style="white-space: pre; "> </span>isSuspended</div><div><span class="Apple-style-span" style="white-space: pre; "> </span><span class="Apple-tab-span" style="white-space:pre"> </span>^myList isNil</div>
<div><br></div><div>which is broken. Take for example the following two forks, the first of which gets added to the runnable process lists before it runs, the second of which runs immediately:</div><div><br></div><div><div>
<span class="Apple-style-span" style="white-space: pre;"> | s r |
s := Semaphore new.
[| thisProcess |
thisProcess := Processor activeProcess.
r := {(Processor instVarNamed: 'quiescentProcessLists') indexOf: (thisProcess instVarNamed: 'myList').
thisProcess priority.
thisProcess isSuspended }.
s signal] forkAt: Processor userBackgroundPriority.
s wait.
r
answers #(1 30 false)
| s r |
s := Semaphore new.
[| thisProcess |
thisProcess := Processor activeProcess.
r := {(Processor instVarNamed: 'quiescentProcessLists') indexOf: (thisProcess instVarNamed: 'myList').
thisProcess priority.
thisProcess isSuspended }.
s signal] forkAt: Processor activePriority + 20.
s wait.
r
answers #(0 60 true)<br></span></div><div><br></div><div>So I'm confused too! There's a bug in the VM and in the definition of isSuspended. isSuspended needs to read</div></div><div><br></div><div><div> isSuspended</div>
<div> ^myList == nil and: [self ~~ Processor activeProcess]</div><div><br></div><div>and the VM needs to set myList to nil in transferTo:.</div><div><br></div><div>If I were thinking of a truly multi-process implementation I'd set myList to the process itself so that we could define</div>
<div><br></div><div><br></div><div><div> isSuspended</div><div> ^myList == nil</div><div><br></div><div> isActive</div></div></div></div> ^myList == self</div><div class="gmail_quote"><br></div><div class="gmail_quote">
but one step at a timee.</div><div class="gmail_quote"><br></div><div class="gmail_quote"><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">I believe the correct behaviour of Semaphore>>signal should be that<br>
the next process to be run would be either the process doing the<br>
signalling, or any other process waiting on that semaphore. Assuming a<br>
multi-core capable VM, two processes might end up concurrrently<br>
continuing execution. There shouldn't be any guaranteed ordering in<br>
the resuming of processes; that's an implementation detail in the VM<br>
that could potentially change.</blockquote><div><br></div><div>Um, this seems very confused. The process doing the signalling should not be affected at all. Only processes waiting on the semaphore should be affected, and by definition the signalling process can't be waiting on the semapihre it seignals because it has to be runnable to be able to signal.</div>
<div><br></div><div>Further, yes there *must* be an ordering in the resumption order. It must be strictly FIFO for many scheduling algorithms to work. Even on a multi-core CPU the scheduler can be well-defined such that processes waiting on a semaphore become active in the order they are waiting on the semaphore. Even in a hypothetical multi-core VM with two concurrent processes simultaneously signalling a semaphore with two processes waiting on it the system would have to ensure that the two signals ended up scheduling both processes, not that both signals ended up somehow proceeding only one; i.e. the VM is going to have to serialize or mutually-exclude access to the semaphore to prevent signals being lost.</div>
<div><br></div><div>And yes, this is guaranteed, very conciously so. The Smalltalk scheduler is strictly a real-time scheduler preemptive across priority and cooperatively-scheduled round-robin within priority, such that all lower-priority runnable processes are preempted by any higher-priority runnable processes as soon as any higher-priority process becomes runnable. The only bug in this in Squeak (apart from the myList snafu above) is that when a lower-priority process is preempted by a higher one it gets added to the back of its scheduling queue, so within a priority processes can't rely on being co-operatively scheduled. This has been fixed in VisualWorks, where a preempted process is added to the front of its runnable process list. (But VisualWorks goes on to break Semaphores by making them priority queues where the first highest priority process is the one that gets run, which will break certain scheduling algorithms).</div>
<div><br></div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">And yes, I believe that in your example, it is correct that the entire<br>
mutex should "stall", meaning that the process that entered the mutex<br>
has entered a "suspended" state and all processes still waiting on<br>
that mutex remain in their "waiting" state. If the mutex didn't<br>
"stall", the debugger wouldn't be particularly helpful.<br>
<div><div></div><div class="h5"><br>
Gulik.<br>
<br>
--<br>
<a href="http://gulik.pbwiki.com/" target="_blank">http://gulik.pbwiki.com/</a><br>
<br>
</div></div></blockquote></div><br></div><div>Cheers</div><div>Eliot</div>