Operating Systems

Homework 4

Assignment : Spin-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);

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.

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.

(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.)

Uniprocessor Locking

lock(L) {
  cli();   //disable preemption
  while (L==0) continue;
  L = 0;
  sti();   //enable preemption
}

unlock(L) {
  L = 1;
}

lock(L) {
  int acquired = 0;
  while (!acquired) {
    cli();
    if (L == 1) {
        acquired = 1;
        L = 0;
    }
    sti();
   }
}

unlock(L) {
  L = 1;
}

Assignment : 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;
}

Assignment : xv6 file system

Read: sysfile.c (create(), sys_unlink()), fs.c (readi(), writei(), dirlink(), ialloc(), iupdate(), iget(), ilock(), iunlock(), iput(), itrunc()), bio.c (bget(), bread(), bwrite(), brelse())

Add the following line at the beginning of the log_write() function in log.c

cprintf("log_write %d\n", b->blockno);

Start a new session on xv6 with a fresh disk (using make clean followed by make qemu, and type the following command:

$ echo > a

Interrupt the previous command (leave the newly created file unchanged). Next, execute the following command to write data to this file:

$ echo x > a

Next, delete the file by typing the following command:

$ rm a