Warmup due October 10th, Parts 1 and 2 due by Monday, October 21st.
Please use the class discussion board (you can find it on your blackboard) as a communication and Q&A tool. Should you still need to send an e-mail inquiry, address it to the TA (Xiaowan Dong: xdong@cs ...) and cc the instructor. This assignment will be examined through demo with the TA. The demo time should be conducted with the TA by the due date or earlier. We expect that each demo will take 20-30 minutes. Please reserve your time slot with the TA ahead of time. Part one (and the warmup part) of the assignment is an individual assignment.
Part two (in-kernel part) of this assignment is a group assignment. You may form a group of two to complete this part of the assignment.
You will need to form a different group from the last assignment.
Disclaimer: Parts of this assignment are adapted from a project developed by Dr. Jason Nieh at Columbia University.
Warmup: Performance Measurement (Individual Assignment) (5 points) Measure the cost of a thread context switch in pthreads in a manner similar to the previous assignment. Your code should be written in C or C++ and use the pthreads library (use the man pages on pthreads for documentation on specific calls). The tutorial at LLNL will also prove useful.
In this part of the assignment, you will work on synchronization and threads in user space. For this part, you do not need the virtual machine. In other words, you DO NOT have to develop the solution inside QDGL.
In this problem you will add synchronization functionality to the
implementation of SThreads, a simple threading library. Get
the source files here for the graduate network and here for the undergraduate network.
The files provide the source, header, and Makefile for the SThreads
library. The functions and datatypes are declared in the file
The library is used as follows:
sthread_tto be an opaque data type (i.e., only functions in
sthread.cget to know what it really is).
sthread_init()must be called exactly once, as the first thing in
main(). It returns 0 normally, and -1 on error.
int sthread_create(sthread_t *t, sthread_main_t main,
sthread_tobject is returned. The second is the function the new thread should run. The third argument is passed to this function.
sthread_create()returns 0 normally and -1 on error.
sthread_self(), which returns the
sthread_tassociated with the currently running thread, as well as
sthread_suspend(), which puts the currently running thread to sleep, and
sthread_wake(sthread_t t), which wakes up a thread, given the thread's
sthread_tobject. Note that for the SThreads library, first waking up a running thread and then suspending it leaves the thread in a running state.
You are also provided with the function
which atomically sets the integer that x points to to 1, and returns
its original value. Using
test_and_set(), you are to implement the missing
locking primitives in the SThreads library.
You may use
test_and_set() to implement spinlocks, in
which you repeatedly call
test_and_set() and a no-op in a
tight loop, waiting for the test result to be 0. Note that you can use
spinlocks to synchronize access on your locks' shared data structures,
but not to implement the locks themselves. In other words,
if I call
on an unavailable mutex, I should suspend rather than spin until
the lock is released.
Now comes the fun part. For this assignment, implement mutex locks
in the SThreads library. Put your function implementations in a single
sync.c, and your structure definitions in
Skeleton files are provided, but you may have to add functions and
datatypes to these files. You shouldn't have to change
sthread.h. Unless otherwise noted, all functions
should return 0 on success and -1 on error.
The prototypes for the five functions you must implement are found
sync.h, and are all named
You must define
sthread_mutex_destroy() should be used to initialize
and free resources related to this structure. Either or both may be
no-ops if your implementation requires no initialization and/or
sthread_mutex_lock() should obtain the lock, if
it is available, or else the current thread should block until the lock
sthread_mutex_unlock() should make the lock
available. It should be an error for any thread other than the owner of
the lock to call this.
obtain the lock and return 0, if the lock is available, or else return
non-zero immediately. This function does not cause the caller to block.
Your implementation should be recursive, i.e., if the owner of a
lock tries to get the same lock, it should not deadlock, but just
require another call to
sthread_mutex_unlock() to fully
unlock the mutex. Note that this is not how all mutex implementations
work -- many will simply deadlock if the holder of a lock attempts to
get it again. The Linux pthread implementation has both standard and
recursive mutexes: see the
pthread_mutex_init(1) man page
Your implementation should not allow starvation of any thread waiting for the mutex. That is, if two threads are repeatedly locking and unlocking a mutex, that should not prevent a third thread from eventually getting the lock. (Of course, if one thread never unlocks the mutex, the others will starve, but that's a programming error, i.e., not your problem!)
For this part of the assignment, you will implement a new kernel synchronization primitive. It may be helpful to read some references. One example is the "Kernel Synchronization" chapters in the Linux Kernel Development book by Robert Love. Note that the kernel calls its semaphore operations down and up instead of P and V, but the operations are the same. Note that unlike the userspace mutexes you implemented for the first part of this assignment, the synchronization primitives in Linux generally do not have owners and are not recursive. No owners means that there's nothing stopping any piece of code from unlocking every lock in the kernel (and bringing the kernel to a fiery screeching halt, probably). Not recursive means that the owner of a lock (even if there was such a thing) can't obtain the lock twice.
You are asked to design and implement a new kernel synchronization primitive that will allow multiple processes to block on an event until some other process signals the event. When a process signals the event, all processes that are blocked on the event are unblocked. If no processes are blocked on an event when it is signaled, then the signal has no effect. Implement the following new system calls in the Linux kernel, respectively (take a look in the instructions on how to add a system call if you need a refresher).
int doeventopen();Creates a new event, returning event ID on success, -1 on failure.
int doeventclose(int eventID);Destroy the event with the given event ID and signal any processes waiting on the event to leave the event. Return number of processes signaled on success and -1 on failure.
int doeventwait(int eventID);Blocks process until the event is signaled. Return 1 on success and -1 on failure.
int doeventsig(int eventID);Unblocks all waiting processes; ignored if no processes are blocked. Return number of processes signaled on success and -1 on failure.
You are designing a completely new facility to add to the kernel.
You will need to create a new implementation file and change the
Makefile so that it compiles your new file. You are also likely to need
to change a few parts of the existing kernel, such as the
initialization code. To do this, you should write a new
function that can be called when the system is booted. You will need to
change the system initialization code to call this new function.
You should begin by thinking carefully about the data structures
that you will need to solve this problem. Your system will need to
support having multiple events open at the same time, so you will
probably need a set of event descriptor data structures, each of which
identifies an event. Those data structures will need to be put in a
list from which your code can find the appropriate event descriptor
corresponding to the event that you need. Space for the event
descriptors should be dynamically allocated, most likely using the
can choose to work at the level of wait queues and the associated
low-level routines such as
Alternatively, you may find it easier to work with kernel functions
sure to properly synchronize access to your data structures. You should
not make any assumptions about whether the system is a uniprocessor or
You are also asked to write a user-level program to test your new kernel functions. Your test program should show that the kernel functions work for the usual cases, for example, with one process waiting, and also for boundary conditions such as
Have fun hacking!!!
Please make sure to add an extensive README documenting your design and testing procedures. Also make sure to COMMENT your code. Please document how you divided the work amongst yourselves. Note that Part One is an individual assignment. You may discuss approaches with your colleagues, but should not share code. Note also that part of the grade will be reserved for good design and documentation. I expect the CS456 students to document more extensive testing procedures and the grade will be weighted accordingly for the CS456 students. The warmup constitutes 5\% of the grade, the user space portion constitutes 35% of the grade, and the kernel portion constitutes 60%. For the kernel portion, you should make sure to divide up the task into manageable pieces and get each individual piece functional before moving on to the next (for example, there is no excuse for not adding a suggested system call; you should add all the system calls so that they can be tested and then work incrementally on their functionality).