Semaphores

Question 1

Example: Vaccination by Locking

Answer 1

Lock allows only one in at a time: underutilization of booths

Question 2

Example: Vaccination by Semaphore

Answer 2

Question 3

Vaccination in Code

Answer 3

Question 4

Selling tickets via Semaphore

Answer 4

Question 5

What happens if
* Number of buyers and initial number of tickets are equal?
* There are zero tickets initially?
* Number of tickets is greater than the number of buyers?

Answer 5

Locks only provide mutual exclusion
– One thread executes in the critical section at a time

May want more threads using resources concurrently
* Produce/consumer problem
– Need one thread to run after the other
– Don’t wish to operate in lockstep

Question 6

Semaphore Definition (Dijkstra, 1965)

Answer 6

A synchronization primitive implemented via a counter with a nonnegative initial value, and supports two operations that are guaranteed to be atomic:

• acquire:
  If counter is positive, then decrement counter by 1 and let calling thread continue. If counter is 0, block the thread on the semaphore.
• release:
  Increment counter by 1. If there are blocked threads on
  the semaphore, unblock some such thread.

acquire aka wait aka P aka down
release aka signal aka V or up
Note: Counter value is never negative!

Question 7

Semaphore Psuedocode for Mutual Exclusion

Answer 7

Question 8

How does this work?

Answer 8

Question 9

Blocking/Unblocking Management

Answer 9

Internally managed by thread system

The thread system records the threads that are blocked on a semaphore. E.g., it may place them in a queue for the semaphore.

When semaphore is incremented, the system picks a thread from the queue to run.

The thread runs whenever it is scheduled!

Question 10

Implementing Semaphores in Java

Answer 10

Each Java object O has an associated monitor M, with two conceptual components, a lock L and wait set W
- L ensures at most one thread in any code synchronized on O
- Recall: synchronized method() {body} in O
equiv. to. method(){synchronized(O){body}}

• W: maintains threads blocked on M.
  
  • O.wait() suspends calling thread and adds it to W
    
    • Can only be called from synchronized blocks
    • Releases L
  • O.notify() takes a thread from W and makes it runnable.
    
    • Can only be called from synchronized blocks
    • Thread must obtain L before resuming

Question 11

Semaphores in Java (Buggy)

Answer 11

Semaphores in Java (Fixed)