Overview

Synchronization constructs allow for concurrent processes to operate correctly.

PV Semaphore

Among the sleeping synchronization primitives, we will be working with the PV semaphore, also known as a counting semaphore. There are two operations on a PV semaphore, P or down and V or up.

• The down operation decrements the semaphore count by one, and if resulting counter value is less than zero, the thread sleeps on the semaphore. If the result is zero or greater, the thread continues.
• The up operation increments the semaphore. If there are any threads sleeping on the semaphore, it also awakens one thread, and both threads continue.

These primitives are themselves constructed from other primitives. Test and set instructions are often provided in the instruction set, and can be the foundation for locking upon which we can build semaphores. The test and set will read the current value of a specified bit in memory simultaneously setting (setting value to one) that bit. If the read bit was zero, the thread issuing the instruction has succeeded in taking the lock, and no other thread could have or will succeed in taking the lock until the bit is cleared, i.e. set to zero.

On the other hand, if the value of the bit read was one, the lock was already taken, and the setting of the bit had no effect, effectively writing a one of a bit value already one.

Restricting the PV semaphore to values 1, 0, -1, etc., we have a mutex, short for mutual exclusion. A mutex allows only one thread at a time in the critical section, and the count is the negative of the number of waiting threads.

Experiment

A semaphore system call was implemented. Here is the code:

================================================
=== /usr/src/linux-2.6.26.2/kernel/sched.c =====
================================================

static DECLARE_MUTEX(my_monitor) ;

asmlinkage long sys_monitor(int action)
{
        int result ;
        printk( KERN_DEBUG "sys_monitor: entered") ;
        switch(action){
        case 0:
                printk( KERN_DEBUG "sys_monitor: action 0") ;
                result = down_interruptible(&my_monitor) ;
                break ;
        case 1:
                printk( KERN_DEBUG "sys_monitor: action 1") ;
                up(&my_monitor) ;
                break ;
        case 2: /* reacquire */
                printk( KERN_DEBUG "sys_monitor: action 2") ;
                up(&my_monitor) ;
                /*yield() ;*/ /* unnneeded, Linux implements fairness */
                result = down_interruptible(&my_monitor) ;
                break ;
        default:
                printk( KERN_DEBUG "sys_monitor: unknown action") ;
        }
        return 0 ;
}

The experiments use the following user codes:

================================================
============== monitortest-up.c ================
================================================

#include<stdio.h>
#include<stdlib.h>
#include<unistd.h>

#define __NR_monitor 31

#define MONITOR_DOWN 0
#define MONITOR_UP 1

int main(int argc, char * argv[]) {
   printf("calling up on monitor ...") ;
   syscall(__NR_monitor, MONITOR_UP) ;
   printf("done.\n") ;
   return 0 ;
}


================================================
============ monitortest-down.c ================
================================================

#include<stdio.h>
#include<stdlib.h>
#include<unistd.h>

#define __NR_monitor 31

#define MONITOR_DOWN 0
#define MONITOR_UP 1

int main(int argc, char * argv[]) {
   printf("calling down on monitor ...") ;
   syscall(__NR_monitor, MONITOR_DOWN) ;
   printf("done.\n") ;
   return 0 ;
}


================================================
============= monitortest-reacq.c ==============
================================================

#include<stdio.h>
#include<stdlib.h>
#include<unistd.h>

#define __NR_monitor 31

#define MONITOR_DOWN 0
#define MONITOR_UP 1
#define MONITOR_REACQUIRE 2

int main(int argc, char * argv[]) {
   int i ;
   printf("calling up on monitor ...") ;
   syscall(__NR_monitor, MONITOR_DOWN) ;
   printf("in monitor\n") ;
   // in monitor
   for (i=0;i<10;i++) {
      // leave and reenter monitor
      syscall(__NR_monitor, MONITOR_REACQUIRE) ;
      printf("in monitor i=%d\n",i) ;
      sleep(3) ;
   }
   syscall(__NR_monitor, MONITOR_UP) ;
   // leave monitor
   printf("done.\n") ;
   return 0 ;
}

These experiments use monitortest-down and monitortest-up in two separate shells to experiment with the semaphore.

• Run monitortest-down twice. The first run will complete immediately. The second run will wait on the semaphore, it's count now is -1. Run monitortest-up, and the waiting process shall continue.
• Multiple monitortest-down runs that are waiting will be released oldest wait first, one by one, bt running monitortest-up.
• Multiple runs of monitortest-up allows monitortest-down to run multiple times before it waits, demonstrating the counting mechanism. whereby monitortest-up increments the semaphore, even it there are not waiting process, and the semaphore is strictly positive.
• Run monitortest-reacq multiple times to demonstrate the Linux kernel's fairness in allocating locks. First monitortest-down is run to take the lock. Then two instances of monitortest-reacq are run, and both wait. Then monitortest-up is run to start the two instances of monitortest-reacq alternating running and blocking.

Monitors

A monitor is a computer language construct. It assures locking over a critical section, and also has event-wait constructs. The details vary according to definition. A block of code marked as a monitor cannot be entered with a lock being taken, and the block cannot be exited without the lock being returned. The compiler inserts down and up statements where they are needed, so that mutual exclusion is achieved on code forming the monitor.

A monitor has the additional flexibility of condition variables. While in the monitor, a thread can wait on a condition variable. It will then sleep until the condition is signaled, typically by an other thread that has entered the monitor. When a waiting thread is awakened, it reenters the monitor when the current thread leaves the monitor.

The original monitor model (Hoare semantics) would have the signaled thread immediately displace the signaling thread in the monitor. When the signaled thread returns, or waits, etc., control will return to the signaling thread. If a signal is made on a condition variable at the moment when there are no threads waiting on the variable, the signal is lost.

While the original monitor model had the signaling thread yield the processor to the signaled thread, other monitor definitions use a signal and continue model. In Mesa-style monitors, a signal will make ready to run a single thread waiting on the signal, or will be lost if there are not threads waiting on the signal, but the signaling thread will continue to run and will continue to possess the monitor lock. The signaled thread will only run when the current thread relinquishes the processor.

An additional distinction can be made between monitor models which give priority to singled threads over entering threads and those which don't. A simplified model, the one used in Java, includes only a single (nameless) condition variable, and which gives no priority to signaled threads over newly entering threads. The Java model also allows a "notify all", which awakes all waiting threads. Else, the monitor code must explicitly keep a count of waiting threads, and send that many signals, exactly.

Further distinctions can be made between monitor models based on the way they chose the thread that enters or reenters the monitor. For fairness, Linux chooses the longest waiting thread to awaken.

Project details

The project is to use semaphores to implement a monitor as a kernel API. You will add two system calls, monitor_create which takes a single argument and monitor_op which takes tow arguments.

• monitor_create(MON_CREATE), creates a new monitor, initializes it, and returns the monitor ID, a positive integer, or returns an error value, which is negative.
• monitor_op(MON_DESTROY, mid), destroys monitor identified by monitor ID mid.
• monitor_op(MON_ENTER, mid), enters monitor mid, or is placed in queue to enter the monitor when available.
• monitor_op(MON_LEAVE, mid), leaves monitor mid.
• monitor_op(MON_WAIT, mid), waits for a signal on monitor mid. Will block and leave the monitor (unlock).
• monitor_op(MON_NOTIFY, mid), sends a signal to the longest waiting thread on mintor mid. Signal is lost if no thread is waiting. Signal will place thread on queue to re-enter monitor.
• monitor_op(MON_NOTIFYALL, mid), sends signals to all waiting threads. All threads go the queue to re-enter the monitor.

In designing your monitor, consider:

• deadlock: prove your design free of deadlocks. Under what assumptions?
• fairness: prove your design is fair. Under what definition?
• liveness: prove your design is live.

For liveness you might want to read safety and liveness chapter from Magree and Kramer's Concurrency: state models and java programs. Honestly, I just found that book on a google search for "liveness", and I'm not an expert on such things, but the general idea is clear. The correctness of a design can be broken down into "features", each argued separately. The distillation out of essential features is perhaps the must important step. Lifeness prevents "doing nothing" from being a correct solution, whereas safety is a series of "do not's", including deadlock prevention and perhaps fairness, phrased as "no starvation."

No starvation is not the complement of fairness, although starvation is not fair. But fairness is a subtle issue and might be impossible to fully achieve. Therefore to co-mingle it with safety might back oneself into a corner with respect to proven correctness.