TWiki> CS385fall14 Web>Homework7 (revision 4)EditAttach

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.

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.

Hybrid lock

In our hybrid lock, we spin for some time, hoping the holding thread will soon release the lock. If the lock is not released quickly, we sleep instead.

Adaptive spinlock

An adaptive spinlock spins only if the holder of the lock is currently running. Else, it sleeps.

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.

Edit | Attach | Print version | History: r6 < r5 < r4 < r3 < r2 | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r4 - 2014-10-28 - 20:09:15 - Main.jakob
Copyright 2016 The Board of Trustees
of the University of
Helping Women Faculty Advance
Funded by NSF