Mutual Exclusion

In this homework, we implement several types of mutual exclusion operators.

For concurrency homeworks such as this, qemu is not a good choice of execution environment: qemu uses a single thread to emulate one or more cores, meaning race conditions, if they happen at all, are going to be very rare indeed.

To properly test synchronization operations, we need to actually run our code on multiple cores. To do this, we run xv6 under VMWare instead of under qemu. VMWare isn't as convenient, however, so I would suggest using qemu for initial development and debugging, and then testing with VMWare.

To create a VMWare image use the qemu-img tool, like this:

qemu-img convert -O vmdk xv6.img xv6.vmdk

and the same for fs.img. Then create a VMWare VM, and replace any disks (including CD-ROM's) with these two images. xv6.vmdk first, then fs.img. Start the VM, and xv6 should boot up.

To try a new version, first shut down the VMWare VM. Then make your updated sources, convert the images as per above, and start the VM back up.

The lock implementations will be tested using programs starting with race. The first program that actually uses locks is race2.c. It includes the header file "multilock.h". By changing #define spinlock to #define waitlock etc, you can switch the lock type used.

(I tried to do this more elegantly with the ## operator and defines passed in from the Makefile, but failed. Suggestions welcome!)

Basic user space spinlock

For this part, use the atomic xchg operator to implement a basic spinlock. The functions spinlock_init, spinlock_acquire and spinlock_release have empty definitions in uspinlock.h. Implement real versions of these functions in uspinlock.c.

Basic user space ticket lock

In a ticket lock, an atomic addition ( xadd) operation is used instead of a compare and exchange. When entering acquire, take a ticket by incrementing a queue count. Then wait until your number comes up on a dequeue count. Upon release, increment the dequeue count. Fill in ticketlock.c and ticketlock.h.

Kernel-support for wait locks in userspace

Here, the thread should go to sleep until the lock becomes available. Rather than do any sort of check in user space, have the kernel decide. We may do mixed userland/kernel locks in the next homework.

For this part, fill in waitlock.h and waitlock.c, and add the necessary system calls to support this.

There are several tests called race* in the template. A correct lock implementation produces the same result for all, and doesn't cause the programs to take more than several seconds to finish.