PV Semaphores and Monitors

by: Burt Rosenberg

at: university of miami

for: CSC421: Computer Operating Systems

Spin-Locking: A hardware primitive for concurrency

The possibility of locking requires hardware assistance. CPU's have a special instruction, called test-and-set which is guaranteed to swap the value of a register with the value of a memory atomically. This requires that the memory deal with contention for the memory cell, and that all caches are struck-through so that multiple threads on multiple cores agree on the common value in memory (not on a possibly inconsistent cached value).

A lock L is built from test-and-set by having a memory local L.val and initializing it to 0. Then

    L.test-and-set(v)

Will set L.val=v and return the value of L.val just before this update.

Spin-locking is a simple but inefficient way to claim a lock: to repeatedly test-and-set a location until the return value indicates that the lock was unclaimed on call, but the test-and-set assures that the lock is claimed now.

It is safe in that at most one thread will ever have claimed the lock, and it is live in that if the lock is unclaimed on call, it will be claimed. It is not fair nor is it efficient. These defects are acknowledged in that the use of spin-locks are only for the lowest level of contention resolution.

TEST-AND-SET and SPIN-LOCK

On L.test-and-set(v):
    atomic {
       t = L.val
       L.val = v
       return t
    }

LOCK.init:
   alloc L
   L.val = 0
   return L

LOCK.lock:
   return L.test-and-set(1)
   
LOCK.release:
   # PRE: lock held
   L.val = 0

LOCK.spin-lock:
   while L.lock: 
      pass
   # POST: lock held
   return

PV-Semaphore

The PV semaphore is a solution to concurrency proposed by Dijkara in About Semaphores (1974). The PV semaphore has an integer counter and two operations,

P: which stands for Probeer, the imperative singular of the verb Proberen — to try,
and V: which stands for Verhoog, the imperative singular of the verb Verhogen — to increase.

Let S be the semaphore, and,

S.counter: a counter,
S.P and S.V: the operations P and V,
S.queue: a queue of waiting processes.

THE PV-SEMAPHORE

On S.P:
   decrement S.counter
   if S.counter is negative, 
      place the calling thread on S.queue, and sleep the thread.

On S.V:
   increment S.counter.
   if S.queue is not empty, 
      remove any thread from S.queue and resume the thread.

These operations of fully atomic and synchronized. That is, simultaneous calls to S operations will be carried out such that each call runs in a time ordering from start to finish.

Here is why this is important. Without synchronization, starting with S.counter==1, if both threads call S.P simultaneously, both threads see S.counter==1, both threads set S.counter to 0, and both threads continue.

This is incorrect behavior.

If two threads call S.P simultaneously, one P operation must occur fully before the other P operation. And with this contraint, exactly one of the two threads sees S.counter==1, sets it to 0 and continues. The other thread sees S.counter==0, sets it to -1, and sleeps. That is the correct behavior.

From Spin-Locking to a PV semaphore

We have described a semaphore with a count and queue. To make the calls to the semaphore atomic, add a lock, and claim the lock before making changes to the count or queue.

If the P cannot claim the semaphore, that the sleep of the thread will be handled by the scheduler. The thread will be placed into the wait state and the lock released.

The lock will be held only for the briefest time possible, so that any spin-lock, while inefficient, will be brief.

struct PV_Semaphore {
    int lock ;
    int count ;
    struct WaitList * waitlist ;
}

extern thread_t current_thread ;

void P(struct PV_Semaphore * s) {
    while (test_and_set(&s->lock,1)==1) ;
    s->count -- ;
    if (s->count<0) {
        s->waitlist.add(current_thread) ;
        set_state(current_thread, WAITING) ;
        s->lock = 0 ;
        current_thread.yield() ;
        return ;
    }
    s->lock = 0 ;
    return ;
}

void V(struct PV_Semaphore * s) {
    while (test_and_set(&s->lock,1)==1) ;
    s->count ++ ;
    if (!s->waitlist.is_empty()) {
        t = s->waitlist.remove() ; // remove one at random
        set_state(t, READY) ;
    }
    s->lock = 0 ;
    return ;    
}

From a PV semaphore to a Mutex

To achieve mutual exclusion, and Mutex M, create a PV semaphore S.p with S.count initially 1. Then S.P will lock, and S.V will unlock. The thread that wishes the lock but does not obtain it at that point will sleep; and can obtain it in the future.

=== locked
~~~ wait/sleep

         P             V
         |             |  
A:   ----+=============+---------------
                       |
                       | 
B:   --------+~~~~~~~~~+======+--------
             |                |
             P                V

From a PV semaphore to a Monitor

A monitor is a synchronization primitive defied by Brinch Hanson and C.A.R. Hoare in 1973 or 1974. Rather than the original formulation, I will start at a Mesa-style monitor developed for the Mesa Langauge at Xerox Parc in about 1976.

Said monitor as the following API,

enter:: contend for the Mutex of the monitor and enter the critical section with thread safety,
leave:: unset the Mutex so other threads can proceed.
wait:: called while holding the monitor Mutex, sleep the thread while atomically releasing the Mutex.
notify:: called while holding the monitor Mutex. Select any waiting thread and unsleep it, and queue it for contention to re-enter the monitor.
notify-all:: notify all threads sleeping on this monitor.


// solution to monitor project
// burt rosenberg, oct 2010
// updated: oct 2011

// REMEMBER THIS IS PSEUDO-CODE!

semaphore lock_sema
semaphore wait_sema
integer wait_count

init:
    lock_sema unlocked (1)
    wait_sema locked (0)
    wait_count = 0 

enter: 
    assume: not holding lock_sema
    down on lock_sema

leave: 
    assume: holding lock_sema
    up on lock_sema

wait:
    assume: holding lock_sema
    // increment must be atomic
    wait_count++
    up on lock_sema
    // no critical race because wait_count 
    // registers interest in waiting
    down on wait_sema
    // contend to reenter
    down on lock_sema
    
notify:
    assume: holding lock_sema
    // are "if" and decrement SMP safe? yes, lock_sema protects wait_count.
    if wait_count>0 
        wait_count--
        up on wait_sema
    
notify_all:
    assume: holding lock_sema
    while wait_count>0
        wait_count--
        up on wait_sema

A note: Wait_count is necessary because for a monitor, a notify when there is no waiting thread is lost.

It is not possible to query the semaphore whether there is a thread waiting, and notifying conditional on the result, because of a race condition in the wait implementation between the up on lock_sema and the down on wait_seam.

The wait_count is always updated when hold the monitor lock so it has the correct number of waiting threads. If wait is called in thread T1 is on the way to waiting when thread T2 enters notify, the wait_sema will be correctly up'ed, and T1 will continue with it reaches the semaphore and downs it.

Java Monitors

Java implemented these with the synchronized keyword. In Java every object is a monitor. It has a lock, and a method or a code block can be required the acquire the lock before entering the method or code block.

There is one such lock for each object instance. Re-entrantcy (re-acquiring a lock already held) and leave are handled correctly as part of the language.

This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.

author: burton rosenberg
created: 14 oct 2024
update: 29 sep 2025

by:	Burt Rosenberg
at:	university of miami
for:	CSC421: Computer Operating Systems