W4118 OPERATING SYSTEMS I

Spring 2011 -- Junfeng Yang

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

The written problems are to be done individually. The programming problems are to be done in your assigned programming groups. 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. 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)
  2. MOS 2.26
  3. MOS 2.29
  4. MOS 2.46 (use figure 2-46 instead of 2-20)
  5. MOS 2.50
  6. MOS 2.51

  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? Google "bitfield" 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);

Please complete and submit a private group programming assignment evaluation. The evaluation should be in a separate file called evaluation.txt that is submitted with your individual written assignment submission.

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://repair.cs.columbia.edu/git/xv6 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 hw2-<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/hw2 hw2. 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 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:

System call tfork() creates a new thread that runs function entry on argument arg, using stack spbottom. It can be called by both main or non-main threads. Before calling this system call, users must first allocate the stack. Note that on x86 stack grows downwards. In addition, to simplify your implementation, assume that function entry must call texit() to exit the current thread. tfork() should return -1 on error, and the ID of the newly created thread. File hw3-test-multiple.c illustrates how to use tfork().

System call twait(tid) is similar to the wait() system call, except it waits for a specific thread within the current process. This function should return -1 if tid is the main thread. That is, a non-main thread cannot wait for the main thread.

System call texit() exits the current thread. It should return -1 if it is called by the main thread.

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.

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 2. 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.