Operating Systems


Homework: locking, memory hierarchy

Assignment Part 1 (locking)

Read: spinlock.c In this part of the assignment we will explore some of the interaction between interrupts and locking.

Make sure you understand what would happen if the kernel executed the following code snippet:

  struct spinlock lk;
  initlock(&lk, "test lock");
  acquire(&lk);
  acquire(&lk);
(Feel free to use QEMU to find out. acquire is in spinlock.c.)

An acquire ensures interrupts are off on the local processor using the cli instruction (via pushcli()), and interrupts remain off until the release of the last lock held by that processor (at which point they are enabled using sti).

Let's see what happens if we turn on interrupts while holding the ide lock. In iderw in ide.c, add a call to sti() after the acquire(), and a call to cli() just before the release(). Rebuild the kernel and boot it in QEMU. Chances are the kernel will panic soon after boot; try booting QEMU a few times if it doesn't.

Turn in: explain in a few sentences why the kernel panicked. You may find it useful to look up the stack trace (the sequence of %eip values printed by panic) in the kernel.asm listing.

Remove the sti() and cli() you added, rebuild the kernel, and make sure it works again.

Now let's see what happens if we turn on interrupts while holding the file_table_lock. This lock protects the table of file descriptors, which the kernel modifies when an application opens or closes a file. In filealloc() in file.c, add a call to sti() after the call to acquire(), and a cli() just before each of the release()es. You will also need to add #include "x86.h" at the top of the file after the other #include lines. Rebuild the kernel and boot it in QEMU. It will not panic.

Turn in: explain in a few sentences why the kernel didn't panic. Why do file_table_lock and ide_lock have different behavior in this respect?

You do not need to understand anything about the details of the IDE hardware to answer this question, but you may find it helpful to look at which functions acquire each lock, and then at when those functions get called.

(There is a very small but non-zero chance that the kernel will panic with the extra sti() in filealloc(). If the kernel does panic, make doubly sure that you removed the sti() call from iderw. If it continues to panic and the only extra sti() is in filealloc(), then email the staff and think about buying a lottery ticket.)

Turn in: Why does release() clear lk->pcs[0] and lk->cpu before clearing lk->locked? Why not wait until after?

Now look at the lock_acquire() and sema_down functions in pintos source code. The sema_down() function in pintos first disables interrupts and then re-enables interrupts (or sets them to their original status) before returning. Whereas xv6 acquire() function keeps interrupts disabled. Also, sema_down() blocks the thread, while acquire() busy waits.

Turn in: Why does sema_down() need to disable (and re-enable) interrupts? Will this implementation work on a multiprocessor? If not, how will you change it so that it works on multiprocessors too? Provide code (or pseudo-code).

Uniprocessor Locking

A uniprocessor OS does not require atomic instructions like xchg to implement locks (or other forms of synchronization). The concurrency on uni-processor systems is due to pre-emption of threads by the timer interrupt. Because the timer interrupt may pre-empt a thread at any point in program execution, instructions of two threads may interleave in any arbitrary order.

Synchronization primitives that work on multi-processor systems are guaranteed to work on uni-processor systems (reason it for yourself). On uniprocessor systems, it is also possible to implement critical sections by disabling interrupts.

Here are some (possibly incorrect) implementations of lock() and unlock() primitives using interrupt enable and disable mechanisms. Answer the associated questions.
lock(L) {
  cli();   //disable preemption
  while (L==0) continue;
  L = 0;
  sti();   //enable preemption
}

unlock(L) {
  L = 1;
}
Does this implementation of locks work on a uniprocessor? If not, why not?
lock(L) {
  int acquired = 0;
  while (!acquired) {
    cli();
    if (L == 1) {
        acquired = 1;
        L = 0;
    }
    sti();
   }
}

unlock(L) {
  L = 1;
}
Does this implementation of locks work on a uniprocessor? If not, why not?

Assignment Part 2 (sleep and wakeup)

Here is a version of the code for a single-queue, multiple-consumer, mutiple-producer problem.
struct pcq {
    void *ptr;
    struct spinlock lock;
};

void*
pcqread(struct pcq *q)
{
    void *p;

    acquire(&q->lock);
    while(q->ptr == 0)
        sleep(q, &q->lock);
    p = q->ptr;
    q->ptr = 0;
    wakeup(q);  /* wake pcqwrite */
    release(&q->lock);
    return p;
}

void
pcqwrite(struct pcq *q, void *p)
{
    acquire(&q->lock);
    while(q->ptr != 0)
        sleep(q, &q->lock);
    q->ptr = p;
    wakeup(q);  /* wake pcqread */
    release(&q->lock);
    return p;
}

Turn in: Both producer (pcqwrite) and consumer (pcqread) are sleeping on the same channel q. Is this correct? Why or why not? Should they sleep on different channels? For example, what happens if the producer calls wakeup(q)? Can some unrelated part of the code call wakeup a consumer thread?