How does Wait/Signal (semaphore) implementation pseudo-code "work"?

Sharat Chandra picture Sharat Chandra · Mar 16, 2012 · Viewed 7.7k times · Source
Wait(semaphore sem) {                           
  DISABLE_INTS
    sem.val--
    if (sem.val < 0){
      add thread to sem.L
      block(thread)
    }
  ENABLE_INTS

Signal(semaphore sem){
  DISABLE_INTS
    sem.val++
    if (sem.val <= 0) {
      th = remove next
         thread from sem.L
      wakeup(th)
    }
  ENABLE_INTS

If block(thread) stops a thread from executing, how, where, and when does it return?

Which thread enables interrupts following the Wait()? the thread that called block() shouldn’t return until another thread has called wakeup(thread)!

  • but how does that other thread get to run?
  • where exactly does the thread switch occur?

Answer

Rafał Rawicki picture Rafał Rawicki · Mar 16, 2012

block(thread) works that way:

  1. Enables interrupts
  2. Uses some kind of waiting mechanism (provided by the operating system or the busy waiting in the simplest case) to wait until the wakeup(thread) on this thread is called. This means that in this point thread yields its time to the scheduler.
  3. Disables interrupts and returns.