Sponge Bob in Hall Monitor
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.
After creating the monitor, combine with the ring buffer project to implement a producer-consumer solution. Several producer process will add to the the ring buffer while several consumer processes will remove from the ring buffer, and the monitor will keep the buffer critical section safe, as well as provide efficient waiting by consumers when the buffer is empty and by producers when the buffer is full.
Linux provides for semaphores. This code demonstrates how to create and use semaphores in the kernel. If one runs the user program monitortest-up this will be a V operation on the semaphore in the kernel; if one runs the user program monitortest-down this will be a P operation on the semaphore.
================================================
============ $R/kernel/mysyscalls.h ============
================================================
#define MONITOR_DOWN 0
#define MONITOR_UP 1
#define MY_MONITOR 355
================================================
============ $R/kernel/mysyscalls.c ============
================================================
#include<linux/kernel.h>
#include<linux/syscalls.h>
#include<linux/semaphore.h>
#include "./mysystecalls.h"
/* static DECLARE_MUTEX(lock_sema) ; */ /* the book uses a deprecated interface */
static DEFINE_SEMAPHORE(lock_sema) ; /* see http://lwn.net/Articles/304725/ */
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 ;
}
================================================
=== diff $R/arch/x86/syscalls/syscall_32.tbl ===
================================================
< 355 i386 my_monitor sys_my_monitor
================================================
======= diff $R/include/linux/syscalls.h =======
================================================
< asmlinkage long sys_my_monitor(unsigned long op) ;
================================================
=========== diff $R/kernel/Makefile ============
================================================
< async.o range.o groups.o smpboot.o \
< mysyscalls.o
---
> async.o range.o groups.o smpboot.o
================================================
============== monitortest-up.c ================
================================================
#include<stdio.h>
#include<stdlib.h>
#include<unistd.h>
#include "./mysyscalls.h"
int main(int argc, char * argv[]) {
printf("calling up on monitor ...") ;
syscall(MY_MONITOR, MONITOR_UP) ;
printf("done.\n") ;
return 0 ;
}
================================================
============ monitortest-down.c ================
================================================
#include<stdio.h>
#include<stdlib.h>
#include<unistd.h>
#include "./mysyscalls.h"
int main(int argc, char * argv[]) {
printf("calling down on monitor ...") ;
syscall(MY_MONITOR, MONITOR_DOWN) ;
printf("done.\n") ;
return 0 ;
}
Creating a monitor from semaphores was described in my blog post but the algorithm is reproduced here:
// 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
//*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 in the solution to the Producer-Consumer problem. See the blog post on this topic.
The monitor protects the ring buffer. The producer program must enter the monitor, try to add to the ring buffer. If it succeeds, it can notify all and leave the monitor. If the ring buffer is full (returns -1), then the producer should wait on the monitor.
Likewise, the consumer program must enter the monitor and try to remove from the ring buffer, if it succeeds it can notify all and leave. Else it should wait on the monitor.
Your producer and consumer codes are two separate program producer.c and consumer.c. So all in all, you will add your new call to the system call table, and add the monitor code to mysystemcall.c in the kernel, and rebuild your kernel. Then you will write producer.c and consumer.c, and run multiple copies of each simultaneously and watch for correct behavior, which includes proper locking of the ring buffer and proper waiting by producer and consumer.