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

Question

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?

From a lecture slide ... http://web.cecs.pdx.edu/~walpole/class/cs333/fall2006/slides/5.ppt — Sharat Chandra, Mar 16 '12 at 21:14

Rafał Rawicki · Accepted Answer · 2012-03-16T21:22:20.443

1

block(thread) works that way:

Enables interrupts
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.
Disables interrupts and returns.

edited Mar 16 '12 at 21:22

answered Mar 16 '12 at 21:03

Rafał Rawicki

22,324
5
59
79

The waiting mechanism uses **atomic operations** (you can, for example, check a flag in one atomic processor instruction), so that you can work with interruptions enabled. – Rafał Rawicki Mar 16 '12 at 21:12

score 0 · Answer 2 · answered Jun 24 '14 at 13:40

Yes, UP and DOWN are mostly useful when called from different threads, but it is not impossible that you call these with one thread - if you start semaphore with a value > 0, then the same thread can entry the critical section and execute both DOWN (before) and UP (after). Value which initializes the semaphore tells how many threads can enter the critical section at once, which might be 1 (mutex) or any other positive number.

How are the threads created? That is not shown on the lecture slide, because that is only a principle how semaphore works using a pseudocode. But it is a completely different story how you use those semaphores in your application.

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

2 Answers2