Operating Systems

Homework 4

Hand-In Procedure

You are to turn in this homework before the lecture begins. Please drop your homework in a cardboard box near to the lecture podium. Your homework must be hand-written (typed homeworks will not be accepted).

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->sector);

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

Assignment : ZCAV

This homework is based on the ZCAV tool: see ZCAV documentation here.

Background

To deal with this situation, modern disks divide their tracks into zones. The inner zones have lower angular sector density, while the outer zones have higher angular sector density. Effectively, this means that the disk throughput at the outer zones is higher. This is also called zoned constant angular velocity (ZCAV).

To take advantage of this, the disk controllers usually map the lower sector numbers (starting from sector number zero) on the outer tracks, while the higher sector numbers are mapped to inner tracks. The thinking being that the lower sector numbers are likely to have higher frequency of access. Notice that this is just an assumption and may not be true!

ZCAV program measures the disk throughput at different sector numbers. To do this, it reads/writes 256MB (default) worth of data starting at sector X, where X is varied from 0 to disk-size.

You can see the results of running ZCAV on some disk configurations here.

Turn in

• A disk on a physical laptop. If you have a laptop, report its make and model, and published disk characteristics (seek, latency, throughput). Then measure it using ZCAV and report. Also, report any interesting conclustions (if any). If you do not have access to a laptop, please borrow it from one of your friends or one of the TAs, and clearly specify whose laptop you borrowed.
• A USB (pen) drive. Report the make, model, and published characteristics of the USB drive and compare with your obtained results. If you do not have a USB drive, please borrow one.

Tips

• Downloading and Installing: download this tarball, and type the following commands:

  • tar xzf bonnie++-1.03e.tgz

  • cd bonnie++-1.03e

  • ./configure

  • make

• Running: sudo ./zcav /dev/sda (replace sda with sdb, hda, etc. depending on the disk being tested).
• You only need to test the read performance (not write).
• You may first want to setup the experiment on your private machine before experimenting on GCL. Note that one experiment can take hours to complete, so plan in advance on accessing the GCL machine.
• While zcav is running, you may want to check that your CPU is not bottlenecked (i.e., utilization is below 100\%) using top. Also, you may want to check that no other IO-intensive operation is running using iotop.

Fun

• Can you modify the ZCAV program to estimate the seek and latency of the magnetic disk? How? What were your results?
• Try the same experiments for writes (instead of reads). Do your results differ? For which environments? Why? Warning: writes will overwrite your filesystem and can potentially make the FS unusable. So any write experiments should not be done on the disk containing the current FS.
• Try the same experiments on filesystems (instead of raw disks as above). Here, you would need to create a large file, and then use the command:./zcav filename.
  • Try for different filesystems and different FS options: in particular, try for ext4 ordered mode vs. ext4 default mode.