PV Semaphores and Monitors

by: Burt Rosenberg

at: university of miami

last-update: 14 oct 2024

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, the verb to increase.

Let S be the semaphore, and S.counter be the counter, and S.P and S.V be the operations P and V. S also has a sleep or wait queue, S.queue.

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

On S.V: increment S.counter. And if S.queue is not empty, remove any thread from S.quque 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 Locks to a PV semaphore

We can build a PV semaphore with a lock. To the semaphore structure S add a test-and-set variable S.lock. Before either S.P or S.V the thread must spin-lock on the lock, Once obtaining the lock, the thread completes the activity and then releases the lock,

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(\amp;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(\amp;s->lock,1)==1) ;
    s->count ++ ;
    if (!s->waitlist.is_empty()) {
        t = s->waitlist.remmove() ; // 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.

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.


// 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

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

author: burton rosenberg
created: 14 oct 2024
update: 14 oct 2024