On 4/29/09, Eliot Miranda <eliot.miranda at gmail.com> wrote:
> Hi Michael,
>> What list? Are you referring to the linked list that a Semaphore
>> maintains? I would consider the linked list of Processes that
>> Semaphores maintain to be an implementation detail of Processes and
>> Semaphores. Your code should be written to be completely oblivious to
>> it.
>
>
> 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.  <snip>

Okay, so we have two types of "suspended" going on here:

1: The process is not currently running, but might be soon.
2: The process is in a special "suspended" state for debugging or
management, and won't be scheduled.

Again, you're also working with implementation details. As a
programmer of "normal" code (where "normal" isn't defined here :-P ),
I don't know or care whether Process is a subclass of Link or whether
Semaphores are a subclass of LinkedList. They have protocols that I'd
hopefully never need to use. That sort of stuff should be abstracted
away from me.

What I care about is that:

* When I fork a process, conceptually it is running at the same time.
How the processes are actually scheduled or run should not be of
interest to me.

* When a process waits on a semaphore, it won't restart until that
semaphore is signalled... unless I've asked for a timeout. This
includes when the process has been suspended and resumed - it should
still remain in the "waiting" state.

And either of (depending on who is right between us; discussion
continued below):

* When a semaphore is signalled, *some* process that was waiting on it
shall, at some stage in the future depending on scheduling behaviour,
resume execution.
or
* When a semaphore is signalled, the process that has been waiting on
this semaphore the longest shall, at some stage in the future
depending on scheduling behaviour, resume execution.
(noting that the current implementation in Squeak resumes the waiting
process immediately)

And then:

* If Process>>suspend is invoked on a Process, that Process enteres a
suspended state and won't run until >>resume is invoked on it. (If the
Process was waiting on a semaphore, it will continue waiting on that
semaphore when resumed).

This is my impression of the API that should be presented to
application developers.

> I believe the correct behaviour of Semaphore>>signal should be that
>> the next process to be run would be either the process doing the
>> signalling, or any other process waiting on that semaphore. Assuming a
>> multi-core capable VM, two processes might end up concurrently
>> continuing execution. There shouldn't be any guaranteed ordering in
>> the resuming of processes; that's an implementation detail in the VM
>> that could potentially change.
>
>
> 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.
>
> Further, yes there *must* be an ordering in the resumption order.  It must
> be strictly FIFO for many scheduling algorithms to work.

Would you point me in the right direction on this? Do you have
examples of algorithms where the resumption order of processes waiting
on a Semaphore need to be FIFO?

>  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.
>
> 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.

This would break on a multi-core capable VM. On such a hypothetical VM
(we can dream, right?), any number of processes from any number of
runlevels could be running truly concurrently.

I keep going on about the hypothetical multi-core capable VM, because
I honestly believe that one day some bright spark will make us one and
there will be much rejoicing and joviality. If nobody else does, I
will, once I've finished all my current projects(*).

If all our code relies on the behaviour of the scheduler, then it's
going to be painful for a very long time before our images will be run
nice and concurrently on multi-core PCs. Standard PCs these days have
two or four cores, and I can see the number of cores going all
exponential on us.

Gulik.

(*) ha ha ha ha. See my wiki below.

-- 
http://gulik.pbwiki.com/