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.

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 lock.h. Implement real versions of these functions in a new file called lock.c.

Basic user space ticket lock

In a ticket lock, an atomic increment 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. Call the functions ticketlock_init, ticketlock_acquire, ticketlock_release.

Kernel-support for wait locks in userspace

For this part, implement new system calls called sleeplock_init, sleeplock_acquire, sleeplock_release. Here, if a lock is already in use when sleeplock_acquire is called, the thread should go to sleep until the lock becomes available.