OPERATING SYSTEMS I: Junfeng Yang

Homework 3 is due Thursday 3/4 at 12:01 AM ET Tuesday 3/9 at 12:01 AM ET.

The user-space program for testing the new kernel functions you write (programming assignment 2.b) is due Thursday 2/25 at 12:01 AM ET.

Jingyue will be holding a TA session on this homework at CSB 477 (the open area) from 4-6 on Wednesday, Feb 24.

Individual written problems are to be done individually. Group programming problems are to be done in your assigned programming groups. All homework submissions and discussions are to be made via Courseworks.

Individual Written Problems (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.

MOS 2.26
MOS 2.29
MOS 2.46
MOS 2.50
MOS 2.51
Sketch how semaphores can be implemented in the sthread library (see the programming part of this assignment).

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

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.

Group Programming Problems (60 pts)

Programming problems are to be done in your assigned groups, using the VM that has been assigned to your group for any kernel programming that is needed. For all programming problems you will be required to submit source code, a kernel patch, a README file documenting your files and code, and a test run of your programs. In addition, you should submit a cover sheet using either homework_work.txt or homework_nonwork.txt, depending on whether or not the programming assignment is completely working or not. For source code submissions, you only need to submit new source code files that you created and kernel source code files that you changed. Please do not submit binaries or kernel images. You should clearly indicate your names, email addresses, and assigned group number on your submission. Each group is required to submit one writeup for the programming assignment.

For the user threads package part of this assignment, be sure to Submit a Makefile and a README file with your code. The Makefile should have at least a default target that builds all assigned programs. The README should explain the details of your solution, describe any way in which your solution differs from what was assigned, and state any assumptions you made (5 pts). Also, use the -Wall option to gcc when compiling. You will lose points if your code produces warnings when compiled. Note that the user threads package should be tested and run on any host 32-bit CLIC machine, not inside your guest VMs. The threads package is designed to only work on 32-bit x86 machines. To connect to those machines, you can ssh to clic32.cs.columbia.edu.

For the kernel programming part of this assignment, the image of the kernel you build for this assignment should be vmlinuz.hmwk3. Grading for this assignment will be done based on vmlinuz.hmwk3. You should use base your changes on the 2.6.11 kernel that you installed for Homework 2, but without the modifications you made for the new systems calls you wrote for Homework 2. In particular, submitted kernel patches should be patched against your modified KDB-enabled kernel from Homework 2, i.e. do not include KDB code in your patch.

(25 pts.)Synchronization and threads in userspace

In this problem you will add synchronization functionality to the implementation of SThreads, a simple threading library. Get the source files found in this directory. The files provide the source, header, and Makefile for the SThreads library. The publicly available functions and datatypes are in the file sthread.h. The library is used as follows:

Threads are manipulated using variables of type sthread_t. Consider sthread_t to be an opaque data type (i.e. only functions in sthread.c get to know what it really is).
sthread_init() must be called exactly once, as the first thing in main(). It returns 0 normally, and -1 on error.
A new thread is created using the function:

int sthread_create(sthread_t *t, sthread_main_t main, void *arg).

The first argument is where the sthread_t object is returned. The second is the function the new thread should run. The third argument is passed to this function. sthread_create() returns 0 normally and -1 on error.
You are also provided with sthread_self(), which returns the sthread_t associated with the currently running thread, as well as sthread_suspend(), which puts the currently running thread to sleep, and sthread_wake(sthread_t t), which wakes up a thread, given the thread's sthread_t object. Note that for the SThreads library, first waking up a running thread and then suspending it leaves the thread in a running state.

Usage example:

#define _REENTRANT
#include <stdio.h>
#include <string.h>
#include <errno.h>
#include <unistd.h>
#include "sthread.h"

int
threadmain(void *arg)
{
  int threadno = (int)arg;
  for (;;) {
    printf("thread %d: I'm going to sleep\n", threadno);
    sthread_suspend();
    printf("thread %d: I woke up!\n", threadno);
  }
  return 0;
}

int
main(int argc, char *argv[])
{
  sthread_t thr1, thr2;

  if (sthread_init() == -1)
    fprintf(stderr, "%s: sthread_init: %s\n", argv[0], strerror(errno));

  if (sthread_create(&thr1, threadmain, (void *)1) == -1)
    fprintf(stderr, "%s: sthread_create: %s\n", argv[0], strerror(errno));

  if (sthread_create(&thr2, threadmain, (void *)2) == -1)
    fprintf(stderr, "%s: sthread_create: %s\n", argv[0], strerror(errno));

  sleep(1);
  sthread_wake(thr1);
  sleep(1);
  sthread_wake(thr2);
  sleep(1);
  sthread_wake(thr1);
  sthread_wake(thr2);
  sleep(1);

  return 0;
}

Note the #define _REENTRANT at the top of the file. This is necessary in any multithreaded program, as it tells subsequent include files to use reentrant versions of library functions and thread-safe variables. For example, the errno variable, since it is a global variable, is normally not thread-safe. A function in thread A can set it on error, and thread B can set it to something else before the caller in thread A ever gets to read the value. This is an example of a race condition. If you #define _REENTRANT, though, errno is redefined to (*__errno_location()), which references a different address for each thread. An implementation of this function is provided in sthread.c.

You will also be provided with the function test_and_set(int *x), which atomically sets the integer that x points to to 1, and returns its previous value. Using sthread_suspend(), sthread_wake(), and test_and_set(), you are to implement the missing read-write lock primitives in the SThreads library.

You may use test_and_set() to implement spinlocks, in which you repeatedly call test_and_set() and a no-op in a tight loop, waiting for the test result to be 0. sched_yield() is a good no-op function to use, but you don't have to worry about precisely what it does (not until the next homework, anyway!). Note that you can use spinlocks to synchronize access on your readers-writers locks' shared data structures, but not to implement the readers-writers locks' themselves. In other words, if I call sthread_write_lock() on an unavailable read-write lock, I should suspend rather than spinning until the lock is available.

Now comes the fun part. For this assignment, implement readers-writers locks (rwlock) that favor writers in the SThreads library. Your rwlock implementation should allow multiple readers to acquire the lock in read (shared) mode and concurrently execute. It should allow only one thread to acquire the lock in write (exclusive) mode. When the lock is held in read mode by one or more threads, no threads can acquire the lock in write mode. Similarly, when the lock is held in write mode by one thread, no other threads can acquire the lock in read or write mode.

Your rwlock implementation must favor writers over readers. Specifically, if there are threads waiting to acquire the lock in write mode, you should let one of these threads acquire the lock next. 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.

You should strive to make your implementation fair. If multiple threads are waiting to acquire a lock, other things being equal, you should let the first waiting thread acquire the lock first.

Put your function implementations in a single file, called sync.c, and your structure definitions in sync.h. Skeleton files are provided, but you may have to add functions and datatypes to these files. You shouldn't have to change sthread.c or sthread.h. In fact, you shouldn't even have to look at the implementations of the functions in sthread.c (but feel free if you want to, of course). Unless otherwise noted, all functions should return 0 on success and -1 on error.

The prototypes for the eight functions you must implement are found in sync.h, and are all named sthread_*. You must define struct sthread_rwlock_struct. sthread_rwlock_init(sthread_rwlock_t *rwlock) and sthread_rwlock_destroy(sthread_rwlock_t *rwlock) should be used to initialize and free resources related to this struct.

sthread_read_lock(sthread_rwlock_t *rwlock) should acquire the lock rwlock in read mode if the lock is available and otherwise block waiting until the lock can be acquired in read mode. sthread_read_unlock(sthread_rwlock_t *rwlock) should release the lock that was acquired in read mode and wake up one of the threads waiting to acquire the lock in write mode; these two operations must be one atomic step. sthread_read_try_lock(sthread_rwlock_t *rwlock) should obtain the lock in read mode and return 0 if the lock is available and otherwise return 1 immediately without blocking.

sthread_write_lock(sthread_rwlock_t *rwlock) should acquire the lock rwlock in write mode if the lock is available and otherwise block waiting until the lock can be acquired in write mode. sthread_write_unlock(sthread_rwlock_t *rwlock) should release the lock that was acquired in write mode and wake up one of the threads waiting to acquire the lock in write mode or read mode; these two operations must be one atomic step. sthread_write_try_lock(sthread_rwlock_t *rwlock) should obtain the lock in write mode and return 0 if the lock is available and otherwise return 1 immediately without blocking.

Synchronization in the Linux kernel

Background reading. This assignment is difficult. We recommend you to read and understand the "How Processes Are Organized" section in Chapter 3, and the "Synchronization Primitives", "Atomic Operations", "Spin Locks" and "Read/Write Spin Locks" sections in Chapter 5 in Understanding the Linux Kernel. In Chapter 3, pay particular attention to the material about wait queues. Note that unlike the userspace readers-writers locks you implemented for question 1, the synchronization primitives in Linux generally do not have owners and are not recursive. No owners means that there's nothing stopping any piece of code from unlocking every lock in the kernel (and bringing the kernel to a fiery screeching halt, probably). Not recursive means that the owner of a lock (even if there was such a thing) can't obtain the lock twice.

In this assignment, you will design and implement a new kernel synchronization primitive for achieving unilateral exclusion. Recall that you can make threads mutually exclusive using locks: if one thread grabs a lock, another thread trying to acquire the same lock has to wait. This concept provides safety for accessing a shared variable if all threads follow the same locking contract and acquire the same lock before accessing a shared variable. However, not all programmers are as good as you who are taking W4118 and know the correct ways to write multithreaded programs, and they often acquire the wrong lock when accessing a shared variable.

To solve the above problem, you decide to implement a new synchronization primitive to ensure unilateral exclusion. With the synchronization primitive you build, one can make a code region exclusive against all code regions: when a thread enters an unilateral-exclusive region (termed atomic region), it becomes the only running thread within the current process and the kernel blocks all other threads in the same process from running. Unilateral exclusion is thus stronger than mutual exclusion because it does not require all threads to follow the same locking contract.

(30 pts.) Add two new system calls in the Linux kernel, begin_exclusive() and end_exclusive(), with system call number 289 and 290, to implement unilateral exclusion. To mark a code region an atomic region, users can simply bracket the code using these two system calls. These two systems calls should have the following semantics:
- long begin_exclusive(); A thread issues this system call to enter an atomic region and block all other threads in the same process from executing. It returns -1 if the current thread is inside an atomic region already; otherwise, it returns 0 indicating that the current thread has successfully entered the atomic region and blocked other threads in the same process.
- long end_exclusive(); A thread issues this system call to exit an atomic region, so that the other threads in the same process can continue. It returns -1 if the current thread is not inside an atomic region.
(5 pts.) Write a user-space program to test your new kernel functions. Make sure your virtual machine have multiple cores, because concurrency bugs are much more difficult to expose on single-core systems. You should perform some stress tests. For example, you may create 100 threads each of which constantly enters and exits a unilateral exclusive region. Your test program should show that your kernel functions work for special cases as well, for example, when threads sleep or do I/O in unilateral exclusive regions, when different processes concurrently call begin_exclusive() and end_exclusive(), and when a thread inside a unilateral exclusive region exits without calling end_exclusive, either explicitly exits its thread function or killed by signals.

The testcases in your test program should conform to the interface defined in the test program we gave out for homework 2. Specifically, each test case you create in the user-space program should have the following type:
```
        struct testcase {
                 char *num;
                 char *des;
                 long (*test)(void);
        };
      
```
num stores that ID of the test. des stores a short description of the test. and test is the function that carries out the test. This test function should return a negative integer if there is an error.

Hints on the assignment.

Data structure. You should think carefully about the data structure to store the threads that are waiting for another thread to exit an atomic region. For efficiency, you should place waiting threads on a wait queue instead of letting them spin-wait. You'll find the wait_queue_t and wait_queue_head_t in Linux kernel handy. You should also think about where to store this queue. The constraints are: (1) it should be process-specific because atomic regions are process-specific and (2) it should also be shared across all threads within the same process. You'll need to protect this data structure because it can be accessed by multiple threads.
Implementing begin_exclusive(). For safety, only one thread within a process can be inside an atomic region at any time. Your implementation must ensure safety.

When a thread enters an atomic region, you have to block other threads within the same process and place them on the wait queue of the atomic region. There are two types of threads you need to consider, and you have to think carefully how you handle each.
- Waiting threads (threads waiting for some events): You cannot move waiting threads directly to your own wait queue because these threads are waiting for some events. However, since the kernel always wakes up waiting threads and moves them to the runqueues using either function try_to_wake_up or function wake_up_new_task, you can modify these two functions to move the threads to your wait queue instead.
  
  You'll need to understand the field func in wait_queue_t and figure out what you should set this field to as the wakeup function for the queue.
- Runnable threads (including threads running on CPU): There is a chance that while you move these threads to your atomic-region queue, the kernel scheduler decides to run one of these runnable threads. To prevent this, you'll need some way to ensure that these threads are not running when you move them. To do so, you can create a "placeholder" thread for each CPU. When a placeholder thread is running on a CPU, you know for sure that no other threads are running on the same CPU. Thus you can safely move threads in the runqueue for this CPU to the wait queue of your atomic region.
  
  You can learn how to create and manage kernel threads by looking at the code for the migration threads, which are responsible for load balancing. For example, if one CPU gets too many threads to run, the migration threads will move some of the threads to another CPU. You can find code relevant to the migration threads by searching for function migration_thread).
  
  In addition to "kicking" other threads off the CPU, the placeholder thread should actually do the move of threads. How does begin_exclusive tell the placeholder thread what threads to move? You can implement this using a request queue. To move a runnable thread to the wait queue of your atomic region, your begin_exclusive should append a request to the request queue; when the placeholder thread gets a chance to run, it should pop a request off the request queue and perform the move. The structure of a move request should look similar to struct migration_req. After a move request is completed, the placeholder thread should notify begin_exclusive. You can do so using the struct completion structure in Linux kernel.
  
  The pseudo code for the placeholder thread should look like:
```
      
      while (!kthread_should_stop()) {
          Pop out the first move request from the request queue
          If the thread specified in the request is still on the runqueue (*)
              Take the thread off the runqueue
              Put the thread on the wait queue of the atomic region
          Notify begin_exclusive the request is completed
      }
      
      
```
  The above code does not put a thread to the waiting queue if it is already out of the run-queue (the line marked with *). This situation may happen when the thread is swapped out between the request issuing and actual moving.
  
  With the help of the placeholder thread, function begin_exclusive can now move threads into the wait queue of atomic region. Its pseudo code should look like:
```
      
      for each thread other than the current one in this process {
        continue if this thread is in waiting state
        submit a move request to the placeholder thread
        wake up the placeholder thread
      }

      for each ongoing moving request {
        Wait for the placeholder thread to tell us the request is served
      }
      
      
```
  A tricky issue is that the migration threads may conflict with our placeholder threads: when a placeholder thread decides to move a runnable thread to our wait queue for an atomic region, the migration thread moves this runnable thread to another CPU and happily run it there. To avoid this race, you can change the affinity of the thread so that it can only execute on a particular CPU, and the migration thread won't bother migrating it. You can do so using the following code:
```
      
      unsigned long flags;
      struct rq *rq = task_rq_lock(p, &flags);
      p->cpus_allowed = cpumask_of_cpu(task_cpu(p));
      task_rq_unlock(rq, &flags);
      
```
  The above code accesses the cpus_allowed field in task_struct. You'll need to figure out where to put this piece of code. You'll also need to restore this field once the thread is moved.
Synchronization. Be careful about race conditions. Make sure you hold the right lock(s) when you modify the runqueue structures. In Linux, each CPU has its own runqueue structure, which includes all runnable kernel threads to run on the CPU. (See above for why you want to modify this structure). Also, make sure you hold the right lock when you traverse the list of the threads in a process. (See above for why you want to traverse all threads for a process.
Reference counting. The kernel often uses reference counts to keep track of the number of references to kernel objects, e.g., task_struct objects. When the reference count of an object reaches 0, the kernel will free the object. You should increase and decrease reference counts for the objects you use accordingly, to avoid dangling references (references to objects that are already freed by the kernel).
Handle thread exiting inside an atomic region: If a thread exits while inside an atomic region, the entire process may hang. This is actually a programming error, but we expect you to handle this case so that the entire process will not hang.
Memory allocation and deallocation: You'll need to allocate and release memory in this programming assignment, for example, when issuing a moving request or creating a wait queue entry. kmalloc() and kfree() are the functions to allocate and deallocate memory in the kernel. You should not use them inside a critical section protected by spinlocks because they may sleep and cause deadlocks. kmalloc with flag GFP_ATOMIC does not sleep, but is more likely to return NULL. Therefore, use it only when you have to.

Additional Information

Backup your kernel changes outside your VM often. Sometimes your virtual disk can get corrupted, and you may lose all changes you've made.
Remember, as a safety measure, you are strongly encouraged to backup your VMware image from time to time.
printk statements in system calls will print their output to the console whenever they are invoked. To request printk messages be sent to a log file, insert the following line into the /etc/syslog.conf file:
kern.* /var/kern.log
This will cause printk messages to be written to /var/kern.log. You can send a signal to request the syslog daemon re-read the updated /etc/syslog.conf file, with the command "kill -1 pid" where pid is the pid of the syslogd process.
A lot of your problems will come from system administration issues. If nobody in your group in familiar with unix, you might want to pick up a book on Unix/Linux system administration.
You can find some Linux programming tips at the course resources page.

W4118 OPERATING SYSTEMS I

Spring 2010 -- Junfeng Yang

Individual Written Problems (40 pts)

Group Programming Problems (60 pts)

Additional Information