W4118 OPERATING SYSTEMS I

Spring 2012 -- Junfeng Yang

Homework 3 is due Monday 3/5 at 12:01 AM ET.

The written problems and the programming problems are to be done individually. All homework submissions are to be made via Courseworks. Refer to the homework policy section on the class web site for further details.

Written Assignment (40 pts)

Exercise numbers refer to the course textbook, Modern Operating Systems(3rd edition). Each problem is worth 5 points. Make your answers concise. You'll lose points for verbosity.

  1. MOS 2.13 (assume uniprocessor and disk with unlimited bandwidth)

    In this problem your are to compare reading a file using a single-threaded file server and a multithreaded server. It takes 15 msec to get a request for work, dispatch it, and do the rest of the necessary processing, assuming that the data needed are in the block cache. If a disk operation is needed, as is the case one-third of the time, and additional 75msec is required, during which time the thread sleeps. How many requests/sec can the server handle if it is single threaded? If it is multithreaded?

  2. MOS 2.26

    Show how counting semaphores(i.e., semaphores that can hold an arbitrary value) can be implemented using only binary semaphores and ordinary machine instructions.

  3. MOS 2.29

    Synchronization within monitors uses condition variables and two special operations wait and signal. A more general form of synchronization would be to have a single primitive waituntil, that had an arbitrary Boolean predicate as parameter. Thus one could say, for example,

    waituntil x<0 or y+z<n

    The signal primitive would no longer be needed. This scheme is clearly more general then that of Hoare or Brinch Hansen, but it is not uses. Why not? Hint: Think about the implementation.

  4. MOS 2.46 (use figure 2-46 instead of 2-20)

    Consider the procedure put_forks in Fig. 2-46. Suppose that the variable state[i] was set to THINKING after the two calls to test, rather than before. How would this change affect the solution?

  5. MOS 2.50

    Solve the dining philosophers problem using monitors instead of semaphores.

  6. MOS 2.51

    Suppose that a university wants to show off how politically correct it is by applying the U.S. Supreme Court's "Separate but equal is inherently unequal" doctrine in gender as well as race, ending its long-standing practice of gender-segregated bathrooms on campus. However, as a concession to tradition, it decrees that when a woman is in a bathroom, other women may enter, but no men, and vice versa. A sign with a sliding marker on the door of each bathroom indicates which of three possible states it is currently in: Empty, Women present, Men present. In some programming language you like, write the following procedures woman_wants_to_enter, man_wants_to_enter, woman_leaves, man_leaves. You may use whatever counters and synchronization techniques you like.

  7. Draw a thread schedule with two threads to show the error in the following software-based lock implementation.

          int flag[2] = {0, 0}; // lock flags, one for each thread.  
                            // 1 indicates a thread wants to enter 
                            // the critical region; 0 indicates it doesn't

      lock()
      {
          flag[self] = 1;        // self is the current thread's ID.
          while(flag[1-self]==1) // 1-self is the other thread's ID
              ;
      }

      unlock()
      {
          flag[self] = 0;
      }

  8. Will Eraser report a race on the following code? Why or why not? Read about "bitfield" in 'K&R' if you don't know what it is. 
            struct {
            lock l1;
            lock l2;
            int f1:1; // bitfield, uses only 1 bit
            int f2:1; // bitfield, uses only 1 bit
        } s;

        // thread T1         // thread T2
        lock(s.l1);          lock(s.l2);      
        s.f1 = 1;            s.f2 = 1;    
        unlock(s.l1);        unlock(s.l2);

Programming Assignment (60 pts)

This programming assignment has two parts. In Part A, you'll extend xv6 to support threads; in Part B, you'll implement a readers-writer lock that favors writers.

The files needed for this assignment are distributed using the Git distributed version control software. To learn about Git, take a look at the Git user's manual, or, if you are already familiar with other version control systems, you may find this Git overview useful.

To get started, run the following commands

    $ git clone http://debug.cs.columbia.edu/xv6.git xv6
    $ cd xv6
    $ git checkout -b hw3 origin/hw3
Submission instructions

When you are ready to hand in your solution, put your UNI in conf.mk, commit all your changes, and run make handin in the xv6 directory. This will generate hw3-programming-<your uni>.tar.gz for you, which you can then upload via courseworks. This tar ball includes a snapshot of all xv6 source code and a patch generated using git diff origin/hw3 hw3. Thus, be sure you commit all your changes (including the new files you add) before running make handin.

We will be grading your solutions with a grading program. You can run make grade to test your solutions with the grading program.

Part A: Implement Threads (40 pts)

Threads are essential in modern operating systems, especially because of the rise of the multicore. In this part of the assignment, you will modify the xv6 kernel to support threads.

We have provided you a basic thread design in xv6. We represent both processes and threads uniformly using struct proc. Each proc structure defined in proc.h has a unique ID, so that we can distinguish these structures. Since threads share address space, open file table, and other per-process data structures, we use struct threadcommon to keep track of these shared data structures. The first thread in a process is called the "main thread," and all other threads are called "non-main threads." When a process is created, its main thread is also created and the threadcommon field is initialized. Later, when non-main threads are created, their common pointers should point to the main thread's threadcommon field.

Exercise 1. To support threads, we have to change how system call parameters are fetched in xv6. We've provided a set of new helper functions to fetch system call arguments. Understand what these helper functions do and why they have to fetch arguments this way. You may find the description on the page table lock in Part B helpful for answering these questions.

For Part A, you'll need to implement the following three system calls:

As discussed in class, adding thread support may require a re-design of process operations. We describe the changed semantics of the xv6 process operations below:

For Part A, you'll also need to modify these process operations so that they work correctly in the presence of threads. Note that the threadcommon field is shared by all threads in a process, and you must protect accesses to this field using a lock. We've defined this lock for you as the lock field in threadcommon, but you need to acquire and release this lock at the right places. We also define some macros in proc.h which may be helpful for your implementation.

Part B: Implement a Readers-Writer lock that favors writers (20 pts)

The page table of a process is also shared by all threads in the process and needs protection. For example, to get a system call argument, the kernel uses the current process's page table to translate a user address to a kernel address. Similarly, when a process calls sbrk(), the kernel modifies the page table of this process accordingly. If we are not careful, we may run into kernel panics. Consider the following scenario. Thread t1 issues a system call and traps into the kernel, and the kernel tries to access a system call argument defined on t1's user stack. Meanwhile, thread t2 calls sbrk() to unmap thread t1's user stack. Without proper synchronization, the kernel may panic.

Although we can protect the page table using the same lock that is used to protect the threadcommon structure, doing so would create unnecessary overhead, but most of the system calls only read the page table without modifying it. In fact, the only system call updates the page table is sbrk().

Thus, we would like to use a readers-writer lock to protect the page table. Only sbrk() grabs this lock in write mode, and all other system calls grab this lock in read mode. In addition, we would like to favor the writer because sbrk() is often called to expand the heap, i.e., the calling process is low on memory.

We have provided you a skeleton implementation of a readers-writer lock in rwlock.c and rwlock.h, and added a readers-writer lock pglock in the threadcommon field. In addition, we've added calls to grab this lock in read mode or write mode at various places.

Exercise 3. Textbook section 2.5 shows a psuedo solution for readers-writer problem by using semaphore. Your implementation does something slightly differently; you use spinlock to protect your variables. File spinlock.c illustrates how xv6 implements spinlock. What does the aquire function do before grabing the lock? How does the release part work?
Exercise 4. Locate where pglock is acquired or released in the homework 3 skeleton. Understand why we must have these lock operations. Construct thread interleavings to show that if these lock operations are removed, the kernel will run into problems.

For Part B, you'll need to implement the following functions defined in rwlock.c:

Note that your implementation must favor writers over readers: whenever there is a thread waiting to acquire the lock in write mode, you should let this thread acquire the lock as soon as possible, To illustrate this point, consider the following example. Suppose the lock is held in read mode and a thread A is waiting to acquire the lock in write mode. Another thread B comes, trying to acquire the lock in read mode. In an implementation that favors readers over writers, thread B can immediately acquire the lock in read mode and proceed. However, in your implementation, thread B must wait and thread A should grab the lock first.