Kernel Monitor Project

NAME
    my_monitor -- monitor syscall
    
SYNOPSIS
    my_monitor takes a single argument, the operation, and implements monitor semantics
    of enter, leave, wait, notify and notify-all. The monitor implements Mesa semantics
    with a single wait queue.

DESCRIPTION
    The single argument values are:
    
    Argument values:
        0 - release all locks and waits 
        1 - enter the monitor
        2 - leave the monitor
        3 - go into a wait while leaving the monitor
        4 - notify a single thread waiting on in the monitor,
            the notify is lost if there is no waiting thread. 
        5 - notify all thread waiting on the monitor
	
    The monitor uses Mesa semantics. The notify and notify-all release one or all
    waiting threads, respectively, and the thread or threads contend for re-entry
    into the monitor.

    The caller of notify and notify-all remains in the monitor after the call to 
    notify or notify-all.
	
    The programmer must guarantee that leave, wait, notify and notify-all are only 
    called by a thread that is in the monitor. The monitor is not assured to be
    re-entrant: the thread in the monitor must not call enter.

HISTORY
    The kernel monitor project first appeared an project 3 in csc521.111 (2011-2012).

BUGS
    Reset has never been implemented. Failure of user code generally needs to reboot
    the operating system to clear the lock.
    Only one monitor instance for the entire kernel.
    Does not check for which thread holds the monitor, either to enforce semantics, 
    or implement a re-entrant lock.

Goals

Specific steps

A little about libraries

There tends to be a software layer between syscalls and user programs. The parameters and functionality of a syscall are arranged to suit the kernel programming. A syscall's functionality is a balance between what is generally useful and what is the cleanest to implement. To address a viewpoint of a functionality more responsive to application programmer needs, a library transforms in more or less complete ways the calls into the kernel.

To get a feel for this, we will improve the project 2 by passing the functions of our mysyscalls through a library, called lib-mysyscalls. In this project you will "witness" this process. It is mostly automated by the makefile, but I hope you read through the makefile to understand the process.

Libraries can be held in a static archive. These archives are created and maintained by the ar command, and customarily have an .a extension. (Recall that in unix, all extensions are customary. There is no enforcement mechanism, although certain benefits follow from observing the conventions.) An archive is a collection of objects (.o files), with a table of contents to help the linker-loader find functions inside the various collected .o files. Create an archive with ar -c naming first the archive to create, and then a list of object files to place into the archive.

Constructing a Monitor

I give pseudo-code for a Mesa style monitor, built from the kernel semaphores. Synchronization primitives build from more basic up. From the spin-lock, to the kernel semaphore, to more sophisticated, and more manageable primitives such as the monitor. Originally introduced by Hoare, in designing the Mesa operating system, the definition was revised ot simplify the implementation. That became known as the Mesa style monitor.

Linux provides for semaphores. A semaphore has essentially two operations, the P operation, a.k.a. down or wait, and the V operation, a.k.a. up or signal. A semaphore has the ability to make thread-safe decisions about whether code will take a lock or will be into a wait queue waiting for the lock to be free, and take thread-safe action on that decision. Also, the semaphore provides theread-safe logic for the release of the lock, and the hand off of the lock to the newly awoken thread from the wait queue.

Monitors improve a simple semaphore by adding the operations wait, notify and notify-all.

Two Linux semaphores and an integer variable are used in this construction of a monitor. One semaphore implements a lock which protects the logic and data of the monitor. The other semaphore is used to manage a wait queue.

In the following code, 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 place the wait_count++ under the lock else there would be a critical race between the decision to wait and the test by notify of wait_count of process intending to wait

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

Linux Semaphores

Please go by this example. I suggest you implement enter/leave first, to test whether you can get one MUTEX working.

================================================
============ $R/kernel/mysyscalls.c ============
================================================

#include<linux/kernel.h>
#include<linux/syscalls.h>
#include<linux/semaphore.h>


/* how to allocated a static semaphore struct, initialized to count 1 (a mutex) */
/* static DECLARE_MUTEX(lock_sema) ; */ /* the book uses a deprecated interface */
static DEFINE_SEMAPHORE(lock_sema) ; /* see http://lwn.net/Articles/304725/ */
/* how to allocated a static semaphore struct, initialized to count 0 */
static struct semaphore wait_sema = __SEMAPHORE_INITIALIZER(wait_sema,0) ;

asmlinkage long sys_my_monitor(unsigned long op)
{
        int result ;
        printk( KERN_DEBUG "my_monitor: entered") ;
        switch(op){
        case MONITOR_DOWN:
                printk( KERN_DEBUG "my_monitor: MONITOR_DOWN") ;
                result = down_interruptible(&lock_sema) ;
                break ;
        case MONITOR_UP:
                printk( KERN_DEBUG "my_monitor: MONITOR_UP") ;
                up(&lock_sema) ;
                break ;
        default:
                printk( KERN_DEBUG "my_monitor: operation action") ;
        }
        return 0 ;
}

Aborting a Semaphore


* Convert the lock to a second wait queue, keeping track on the
  number of threads on that queue, similar to the first wait queue.

* An "aborting" counter is introduced, normally zero.

* To abort: set the aborting counter to the sum of waiting threads
  on both queues. This is called "poisoning the well", because all the 
  threads now waiting are poisoned.
  
* Notify-all on both the wait queue and the lock-queue. Now all poisoned threadss
  want to enter. (New threads can go onto the lock queue, and are not poisoned).
  
* Return -1 to enter thread trying to enter the monitor
  while aborting counter > 0; return the aborting counter.