Update for October 2012:

• If the idea of mid's confuses you, just do this for a single monitor. The easy way to do multiple monitors is to have an array of some fixed number, say 16, and return the index as the mid. But don't worry about this - it will be easy when everything else is clear.
• The write up says stuff about this code being in subversion. I'm not sure I want to go that route this year. Just take the code from here, or write your own.
• This page provides pseudo-code for making a monitor from a semaphore. Ignore that code!. Try to build a monitor from semaphores on you own. This is very important to understanding concurrency. Take the pseudo-code on this page only as either hints if you are stuck, or confirmation, when you succeed. You may even find an error in my code! But please try to do it yourself.

Overview

Synchronization constructs allow for concurrent processes to operate correctly. The kernel provides semaphores as a synchronization primitive. Some programming languages have support for a more usable form of synchronization called monitors. This project will use kernel level semaphores to implement user level monitors.

To give a head-start, I provide an example of a new kernel system call. It provides access to a single (globally defined) semaphore. The system call has two arguments. The first is an operation, the second is a mid, a monitor ID. In this example, the mid isn't used, and the operation codes are for semaphore operations, not monitor operations.

Your code will implement mid's, and monitor operations. First we experiment with semaphores.

Experiment

A semaphore system call was implemented. This code is in subversion. Find it in the class account, under the proj5 subdirectory.

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

/* static DECLARE_MUTEX(my_monitor) ; */
static DEFINE_SEMAPHORE(my_monitor) ; /* see http://lwn.net/Articles/304725/ */

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

SYSCALL_DEFINE2(monitor, int, action, int, mid)
{
        int result ;
        printk( KERN_DEBUG "sys_monitor: entered") ;
        switch(action){
        case MONITOR_DOWN:
                printk( KERN_DEBUG "sys_monitor: action 0") ;
                result = down_interruptible(&my_monitor) ;
                break ;
        case MONITOR_UP:
                printk( KERN_DEBUG "sys_monitor: action 1") ;
                up(&my_monitor) ;
                break ;
        case MONITOR_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, by 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 alternatingly running and blocking.

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 two 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.

To get this project up and running, here is a sample solution to creating a monitor with semaphores. It uses two semaphores: one to lock the critical sections of the code, and another to implement the wait queue.

// 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
	// if and decrement must be atomic to be SMP safe
	if wait_count>0 
		wait_count--
		up on wait_sema
       	//*let waiting thread run
	//*up on lock_sema 
	//*down on lock_sema
	
notify_all:
	assume: holding lock_sema
	while wait_count>0
		wait_count--
		up on wait_sema
	//*up on lock_sema
	//*down on lock_sema
	
	

The wait_count++ and -- have to be done in a critical section 
to make the increment/decrement atomic.

Also, the check of the wait_count and the decrement have to be in 
the critical section to prevent two thread both finding wait_count positive
(but say equal to one) both doing the decrement (leaving wait_count negative).

I do place the wait_count++ under the lock so that there is not a race
between the decision to wait and the test by notify of wait_count of process
intending to wait

The lines marked //* were commented out to make this a Mesa style monitor

Once you get this up and running, use your monitor. Implement a solution to the Producer-Consumer problem; implement a solution to the Dining-Philosophers problem.

Helpful hints: Given the discussion in class today, let me elucidate a bit.

As Paul Erdos says: If there is a problem you can't solve, then there is an even simpler problem that you also can't solve. Find that problem.

Getting a simplified monitor to work, with a single global monitor is a simpler problem than the full monitor, with several monitors, and initialization routines that automatically dole out monitors. That is the first problem to solve.

A number of people are having trouble with the macros. Mostly this is just struggling with C. I think a review of static, of structures, and so on, by reading H&S would be very helpful. There are a lot of misconceptions about structures, static, arrays, and so forth.

Forget you ever knew them and read H&S.