Kernel Monitor Project

by: burt rosenberg
at: university of miami
date: oct 2015
NAME
    my_monitor -- a monitor
    
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


BUGS

Goals

The goals of this project are:

Discussion

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.

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, or the waking up of a waiting thread, and the hand off of the lock to the newly woken thread.

Monitors improve a simple lock by adding a wait queue with queue operations wait, notify and notify-all. When a thread succeeds in holding the monitor lock, it is said to be in the monitor. A thread in the monitor can call wait, which will enqueue the thread on the wait queue, while simultaneously releasing the lock on the monitor, allowing another thread to enter the monitor. A thread in the monitor can call notify, which will awaken a thread that is on the wait queue, placing it back into contention to enter the monitor. (Different styles of monitors handle this notify differently.)

Wait allows the thead to temporarily leave the monitor, and re-enter when a condition is satisfied. The logic built into the monitor allows this leave and re-enter to be done atomcially, so that there are not holes in the logic. For instance, there will not be a critical race between a thread going into a wait state while a newly awoken thread rushes to notify the thread — improperly implemented the notify could be lost.

There are several styles of monitors which differ in the details. Monitors were first defined by Tony Hoare, and his definition is called a Hoare monitor. The Hoare monitor as a variable number of wait queues, eacn one associated with a condition variable. In practice, this sort of monitor proved complicated both to implement and to use. The Mesa Programming Language introduced another sort of monitor, that became known as the Mesa monitor.

The Mesa monitor has a single wait queue, thus eliminating condition variables, and a simple notify logic where the notifying thread continues in the monitor and holding the monitor lock, while the notified thread (or threads) goes back into contention to re-enter the monitor when the monitor is free.

Constructing a Monitor

We show how to construction a Mesa style monitor using semaphores. Two semaphores and an integer variable are required in this construction. One semaphore implements a lock which protects the logic and data of the monitor. The other semaphore is used for its ability to manage a 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
	// 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
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

Linux Semaphores

The linux kernel provides a number of synchronization primitives. Your class textbook, chapter 9 describes them. Please refer to that book, but I would like to make some cautions about changes that have occurred in the kernel since the printing of the book.

Here is an example of semaphore calls and initialization. 


================================================
============ $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 ;
}

Specific steps

  1. Refer to class/proj5 for template files. Create your proj5 directory and copy the templates into it, as needed.
  2. You will have to add the my_monitor system call to the end of the system call table. The name of the function implementing my_monitor is sys_my_monitor.
  3. You will have to add the signature for sys_my_monitor to the linux/syscalls.h file.
  4. You will implement the function sys_my_monitor in the kernel/mysyscalls.c file.
  5. The modifications should be familiar to you as they are similar to the introduction of the ring-buffer syscalls.
  6. You then test your program using the provided test programs. See the makefile target "test".
The Makefile targets "submit" and "kernel-diffs" instructs you on what you should submit:
  1. Submit the diff files kernel__Makefile.diff, linux__syscalls.h.diff, and syscalls__syscall_32.tbl.diff
  2. Submit a copy of your kernel file mysyscalls.c, named as kernel__mysyscalls.c
  3. Submit the result of the test runs mymonitor-test-a.out and mymonitor-test-b.out.
A very important note!
A .ref file exists for mymonitor-test-a, and your .out should match the .ref file. However, for mymonitor-test-b1 and mymonitor-test-b2 there are no .ref files. Because of the multi-threaded nature of these tests, it is not possible to give a definitive .ref file that must be matchd exactly. You must read those tests, understand them, and use your understanding and judgement to assure yourself that the output is correct.
Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.

author: burton rosenberg
created: 13 oct 2015
update: 16 oct 2015