Ivan Joergensen wrote in a message to Mike Bilow:

 PF>> It is my understanding (from talking to someone who's been
 PF>> in the code before) that a blocked thread is removed from
 PF>> the scheduler's list altogether.  Only "ready to run"
 PF>> threads are seen by the scheduler.

 MB> That's clearly impossible.  What would be the mechanism, then,
 MB> for making the thread wake up?

 IJ> That is possible. When the semaphore is posted/released the
 IJ> waiting thread(s) can be moved into the scheduler's
 IJ> ready-to-run list. This requires that each semaphore has a
 IJ> list of the threads that are waiting for it. For mutex
 IJ> semaphores this list must already exist (in order to
 IJ> implement FIFO behaviour) and for event semaphores it would
 IJ> be a design fault if they did not also have a list of
 IJ> waiting threads. 

 IJ> The exception is when a thread is waiting for a semaphore
 IJ> with a timeout. The timeout must be checked, but not
 IJ> necessarily on each scheduler transition.

This is an interesting idea, but why then does OS/2 not guarantee that
threads requesting the same semaphore will receive it in the order
requested?  In fact, a semaphore internally is just a reference counter,
and it is referenced by address.  The thread scheduler list is not modified
by the semaphore handling code, but rather each scheduled thread is flagged
as to state: ready, blocked, or running.

There are several reasons for keeping lists of semaphores associated with
each thread instead of keeping lists of threads associated with each
semaphore, but the main reason is that the OS/2 dynamic scheduling scheme
would force a lot of work to be done on the expiration of each semaphore. 
In your method, OS/2 would have to inspect all threads in the system and
sort them by priority order each time a semaphore changed state.  In the
system actually used, the threads in the system are always kept sorted in
priority order, and the address of the semaphore is simply dereferenced and
checked by the scheduler on each scheduling transition.

Another serious problem is that certain semaphore-related facilities could
go unstable if not thread-driven, particularly MuxWait.  I think you can
see that MuxWait becomes extremely simple and stable when each thread has a
list of semaphores rather than the other way around.
 
-- Mike


---