Hi Mike Bilow, how are you

27-Feb-96 21:41:46, Mike Bilow wrote to Ivan Joergensen
          Subject: async timer thread

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

 MB> This is an interesting idea, but why then does OS/2 not guarantee
 MB> that threads requesting the same semaphore will receive it in the
 MB> order requested?
From "Control programming reference":
  If more than one thread is blocked on a DosRequestMutexSem request, then
  ownership is given to the thread that has the highest priority level. If
  more than one of the waiting threads have the same priority level, then
  FIFO ordering is used to determine which thread is unblocked and given
  ownership of the semaphore.
So OS/2 guarantee priority first, FIFO second. The FIFO list has to be
somewhere.

 MB> In fact, a semaphore internally is just a reference counter, and
 MB> it is referenced by address.  The thread scheduler list is not
 MB> modified by the semaphore handling code, but rather each
 MB> scheduled thread is flagged as to state: ready, blocked, or running.
I will get back to that at the end of this letter.

 MB> There are several reasons for keeping lists of semaphores
 MB> associated with each thread instead of keeping lists of threads
 MB> associated with each semaphore, but the main reason is that the
 MB> OS/2 dynamic scheduling scheme would force a lot of work to be
 MB> done on the expiration of each semaphore. In your method, OS/2
 MB> would have to inspect all threads in the system and sort them by
 MB> priority order each time a semaphore changed state.
No, only the threads waiting for the semaphore has to be considered.

 MB> In the system actually used, the
 MB> threads
 MB> in the system are always kept sorted in priority order, and the address 
 MB> of the
 MB> semaphore is simply dereferenced and checked by the scheduler on each
 MB> scheduling transition.

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

(Getting back to your claim that semaphore handling code does not
modify thread state)

Suppose that we have two event semaphores: ev1 and ev2, and a muxwait
semaphore, mux1, consisting of ev1 and ev2. Suppose that ev1 is posted
and ev2 is reset. A thread is waiting for mux1. If another thread
executes this code:
  DosPostEventSem(ev2);
  DosResetEventSem(ev2);
The first thread must be awakened, since the condition (that both ev1
and ev2 is posted) has been true for a brief moment. If the thread
state only could be changed at scheduler transition time the scheduler
would not be able to "see" that the thread should be unblocked. So
DosPostEventSem _has_ to change the scheduler's list if the event
semaphore is part of a muxwait semaphore. And if the DosPostEventSem
has to change the scheduler's lists sometimes, why not let it always
change them?


Incidentally, I have made a thread library (for DOS). My library's
scheduler maintains three lists of threads: ready-to-run, waiting and
waiting-with-timeout. Each wait-thing (mutex, event or something else)
maintains a list of threads that are waiting for it. When a wait-thing
should unblock one or more threads (the equivalent of DosReleaseMutex
or DosPostEventSem) the wait-thing selects a thread from its wait-list,
removes the thread from the wait-list and tells the scheduler to move
the thread has changed state from waiting to ready-to-run. The result
is that the scheduler only has to consider read-to-run threads when
switching threads.

 -=> Yours sincerely, Ivan Joergensen <=-

--- Terminate 3.00/Pro