COMS W4118: Operating Systems I

Dept. of Computer Science, Columbia University

Spring 2013 — Kaustubh Joshi

Homework 3

Homework 3 is due Wednesday 3/27 Monday 4/1 at 12:01 AM ET.

All written problems in this assignment are to be done alone, while the programming assignment is a group assignment. Submit the written and programming assignments separately using the instructions on the homeworks page. Periodically check back on the course page for any errata or updates to submission instructions.

Written Assignment (40 pts)

Exercise numbers X.Y refer to the exercise problem Y in Chapter X in the course textbook, Operating Systems Concepts 9e. Each problem is worth 5 points. Make your answers concise. You'll lose points for verbosity. Your written assignment directory should contain a single ASCII file called hw2.txt with your solutions and a completed teammate evaluation form for the programming assignment.

  1. 5.18: Assume that a context switch takes T time. Suggest an upper bound (in terms of T) for holding a spinlock. If the spinlock is held for any longer, a mutex lock (where waiting threads are put to sleep) is a better alternative.

  2. 5.20 (modified): Consider the following code for allocating and releasing processes: 

         #define MAX_PROC 255
     int nr_proc = 0;

     /* Call on fork() */
     int allocate_pid() {
         if (nr_proc < MAX_PROC)
             return ++nr_proc;
         else
             return -1;
     }

     /* Call on exit() */
     void release_pid() {
         --nr_proc;
     }

     int sys_full() {
         if (nr_proc < MAX_PROC)
             return 0;
         else
             return 1;
     }
    1. Identify the race condition(s).
    2. Could we replace the integer variable int nr_proc = 0 with an atomic atomic_t nr_proc = 0 to prevent the race condition(s)?

  3. 5.41 (modified) We've studied memory barriers in class. A barrier can also be a useful tool to synchronize between multiple threads/processes. When a thread reaches a barrier point, it cannot proceed until all other threads have reached this point as well. When the last thread reaches the barrier point, all threads are released and can resume concurrent execution. Which of the several synchronization primitives we've studied in class (locks, semaphores, monitors, atomics) would make for the easiest barrier implementation? Using your chosen primitive, write pseudo-code for the following two barrier functions:

    1. init(n): initialize a new barrier. n is the number of threads that must wait at the barrier point.
    2. barrier(void): identifies the barrier point. A thread calling this function must be blocked until all other threads have also called this function.

  4. 6.16: Consider the following set of processes, with the length of the CPU burst given in milliseconds:

    ProcessBurst TimePriority
    P122
    P211
    P384
    P442
    P553

    The processes are assumed to have arrived in the order P1, P2, P3, P4, P5, all at time 0.

    1. Draw four Gantt charts that illustrate the execution of these processes using the following scheduling algorithms: FCFS, SJF, nonpreemptive priority (a larger priority number implies a higher priority), and RR (quantum = 2).
    2. What is the turnaround time of each process for each of the scheduling algorithms?
    3. What is the waiting time of each process for each of these scheduling algorithms?
    4. Which of the algorithms results in the minimum average waiting time (over all processes)?

  5. 6.21: Consider a system running ten I/O-bound tasks and one CPU-bound task. Assume that the I/O-bound tasks issue an I/O operation once for every millisecond of CPU computing and that each I/O operation takes 10 milliseconds to complete. Also assume that the context-switching overhead is 0.1 millisecond and that all processes are long-running tasks. Describe the CPU utilization for a round-robin scheduler when:

    1. The time quantum is 1 millisecond
    2. The time quantum is 10 milliseconds

  6. 6.23 (modified): Consider a preemptive priority scheduling algorithm based on dynamically changing priorities. Larger priority numbers imply higher priority. When a process is waiting for the CPU (in the ready queue, but not running), its priority changes at a rate A. When it is running, its priority changes at a rate B. All processes are given a priority of 0 when they enter the ready queue. The parameters A and B can be set to give many different scheduling algorithms.

    1. What is the algorithm that results from B > A > 0?
    2. What is the algorithm that results from B < A = 0?

  7. 6.31: Consider two processes, P1 and P2, where p1 = 50, t1 = 25, p2 = 75, and t2 = 30.

    1. Can these two processes be scheduled using rate-monotonic scheduling? Illustrate your answer using a Gantt chart such as the ones in Figure 6.16–Figure 6.19.
    2. Illustrate the scheduling of these two processes using earliest-deadline-first (EDF) scheduling.

  8. 7.18: Consider a system consisting of m resources of the same type being shared by n processes. A process can request or release only one resource at a time. Show that the system is deadlock free if the following two conditions hold:

    1. The maximum need of each process is between 1 and m resources
    2. The sum of all maximum needs is less than m + n
    Hint: see how the banker's algorithm works and try to show that the given constraints can never cause an unsafe state.

  9. Extra credit (5 points): Locks and RCUs are synchronization techniques with very different philosophies. But both can be used to protect shared pointer-based data structures. In fact, in Homework 2 you have encountered a data structure, the Android tasklist, that can be protected by either acquiring an RCU lock, or by acquiring a tasklist_lock. Why does this work? Specifically, imagine a global pointer to a shared data structure struct mystruct* global; that can be protected either using the Linux RCU protocol described in class or by a lock global_lock. What must a writer do when updating the global pointer to account for the fact that both RCU readers and readlock readers may be accessing the pointer at the same time? Note: just focus on the pointer itself, you do not need to worry about the contents of mystruct, which can be protected individually.

Group Programming Assignment: Net_Locks (100 pts)

In this programming assignment, we'll be working with the Android kernel again using the same emulator environment you constructed for Homework 2 using these Android installation instructions. In your checked out git repository, make sure you checkout the hw3 branch before starting work on this assignment using git checkout hw3.

As the deliverable, you will be required to submit a kernel patch and diff against the hw3_clean tag in your git repo. The patch shows us all commits you have made to the kernel during development, while the diff reflects only your latest code. To produce the patch and diff files, make sure you've committed all your changes, and then go to the root of the kernel tree and type git format-patch hw3_clean.. --stdout > groupN_hw3.patch where N is your group number. This command should create a single groupN_hw2.patch file to submit. Similarly, use the command git diff hw3_clean.. > groupN_hw3.diff to create a single diff file to submit. In addition to these files, you should also include all user mode test programs: .c, .h, Makefile files, the executable files for your test programs, and a README file documenting your files and code that explains any way in which your solution differs from what was assigned, and any assumptions you made. In addition, you are required to also fill out and include this cover sheet to indicate whether your code has any problems or not, and what attempts you have made to fix them.

The usual coding instructions apply. All code must be written in C and a Makefile must be provided with a default target that compiles all user-mode programs. When using gcc, the -Wall switch must be used to display warnings. In addition, you must check your kernel diff against the Linux coding guidelines using the scripts/checkpatch.pl groupN_hw3.diff command in the kernel tree. You can find a tutorial on how to use checkpatch and general kernel hacking tips here. Before submitting, make sure you remove any files produced during compilation (.o files, executable).

Description

No one likes a phone whose battery dies after an hour of using it, so energy consumption is a critical issue when designing mobile applications. Data transfer over cellular radio networks is one of the most energy intensive operations on mobile devices, and so cellular protocols such as 3G (HSPA) and LTE are designed to allow phones to keep their radio transmitters and receivers turned off when they are not needed.

Even so, mobile applications still have to be careful. Because there's a fixed energy and signaling cost to turning a radio on and off (the radio must register with the network when it is turned on), applications that exchange data in short bursts can cause frequent on-off transitions that waste a lot of energy. To learn more, read this and this article. As Figure 1 shows, just 0.2% of an application's data can account for as much as 45% of its energy usage.

In this assignment, we are going to design an OS facility to allow phone applications to co-ordinate their data transfers so that network traffic can be grouped into a smaller number of batches to minimize radio transitions. We're going to do this by providing a new kernel synchronization facility called a "net-lock" that provides a twist on reader-writer locks, and a new process scheduler.

The idea is as follows. The kernel will maintain one net-lock per radio interface (you can assume that there is only one for this assignment). There will be a user-level radio sleep controller that will decide based on demand for the network when to turn the radio on and off. When it wishes to turn the radio off, it acquires the net-lock in "sleep" (write) mode, and releases it after turning the radio back on. When an application wishes to transmit some data, it requests a net-lock in "use" (read) mode along with a timeout value indicating how long it can afford to wait to do the data transfer. E.g., an app might want to show a new advertisement after one minute, so it may request a use-lock with a timeout of 60 seconds to tell the system that it wants to use the network some time during the next minute.

If the radio is already on, i.e. the sleep controller doesn't have a sleep-lock, a use-lock is granted right away and the application may transmit or receive data before releasing the lock. If the radio is off (sleep-lock was acquired by the sleep controller), then any acquire use-lock call should block until the radio is turned back on. Once this happens, all processes that are waiting on the use-lock should be scheduled, in order of their timeout deadlines (EDF), so that they can transfer their data and release the lock. A sleep-lock request must block until there are no outstanding use-requests, (i.e., readers get preference over writers).

Deliverables

  1. Part I (45 points): Design a user-sleeper (reader-writer) "net-lock" synchronization primitive that prioritizes use over sleeping. The locking primitive should be implemented in the kernel/netlock.c file, and should export the following system calls to acquire and release the net lock as a user or sleeper:
         /* Syscall 333. Acquire netlock. type indicates
        whether a use or sleep lock is needed, and the timeout_val indicates
        how long a user is willing to wait in seconds. It's value is
        ignored for sleepers. Returns 0 on success and -1 on failure.  
      */
     int net_lock(netlock_t type, u_int16_t timeout_val);

     /* Syscall 334. Release netlock.Return 0
        on success and -1 on failure.  
      */
     int net_unlock(void);

     enum __netlock_t {
         NET_LOCK_USE,
         NET_LOCK_SLEEP
     } ;
     typedef enum __netlock_t netlock_t;

    Finally, we also need a facility to inform our radio sleep controller when it is time to turn on the radio and release the sleep lock. To do that, we are going to provide a blocking system call net_lock_wait_timeout that a sleeper can call to wait until the user with the earliest timeout times out. Note: in a real system, the radio might also be woken up due to incoming packets or if there are sufficient users waiting so that it makes sense to turn on the radio before a timeout, but we are going to ignore that possibility for now. If there are no users when the sleeper called wait_timeout, it must block for new users to arrive, and return at the earliest timeout. Changes to the users as a result of new net_lock or net_unlock calls while the sleeper is waiting on the wait_timeout call may also change when it returns. 
         /* Syscall 335. Wait for user timeout. Return 0 on a successful
        timeout, and -<Corresponding ERRNO> on failure.  
      */
     int net_lock_wait_timeout();

    Hints: Read LKD Ch. 4, pg 58-61 to learn about wait queues, and Ch. 11 to read about how to use kernel timers, and you can assume that precision isn't important (we don't need sub-second level granularity). Think about which data-structures you will use to keep track of timeout values efficiently and how they will be used to implement the net_lock_wait_timeout call. Do not assume any upper limit on how many users may be waiting on the net_lock at a time. Don't make any assumptions about whether the system is a uniprocessor or multiprocessor system, and synchronize access to your data structures apropriately so that your code is both correct and efficient, in this order. For instance, you should prefer a spinlock over a semaphore if-and-only-if you don't plan to sleep while holding it.

  2. Part II (45 points): In this part of the assignment, we will change the scheduler so that net_lock users that were waiting for the radio to turn on are preferentially scheduled in the order of their timeouts. To do this, you will add a new scheduler EDF that implements the earliest deadline first scheduling discipline. The Linux kernel supports multiple scheduling classes corresponding to different scheduling policies. Add a new scheduling class for EDF called sched_edf_class and implement all EDF functions in kernel/sched_edf.c. Your scheduler should operate alongside the existing Linux scheduler. Therefore, you should add a new scheduling policy, SCHED_EDF with value 6. Only tasks whose policy is set to SCHED_EDF should be considered for selection by your new scheduler. EDF should be a higher priority scheduler than the default CFS scheduler (but not SCHED_RR or SCHED_FIFO), and processes should be assigned to it only as long as they are waiting on or currently hold a use net_lock. Once they release their net_lock, the process should be added back to it's original scheduling discipline (Note: in a real system, one would release the user netlock automatically after the first time a user is scheduled. But, we're not asking you to do this to avoid making what is already a challenging assignment even tougher). Holders of a sleep net_lock shouldn't be affected. The timeout value from the net_lock system call should be used to compute the deadlines. To prevent EDF processes from starving other processes, an EDF task should only be picked with 80\% probability on every schedule() call so that normal tasks running under the fair scheduler have a 20\% chance to run while there are EDF tasks active. You can assume that this probability value is specified as a constant - no need to implement syscalls to get/set its value. Don't make any assumptions about whether the system is a uniprocessor or multiprocessor system — if there are multiple CPUs, assign the next task to the CPU with the smallest number of already running EDF tasks. Since we expect EDF tasks to only be temporary in nature, you don't need to implement any periodic load balancing functions.

    Hints: Read Documentation/scheduler/sched-design-CFS.txt to read about how Linux schedulers are abstracted by Scheduling Classes, and look at include/linux/sched.h, kernel/sched.c, kernel/sched_fair.c, and kernel/sched_rt.c for examples on how to create a new class and implement scheduler functions. You don't need to read all the code, but understand what you can and cannot ignore (look at the sched_class struct). Proper synchronization and locking is crucial for an SMP scheduler. Pay close attention to the kind of locking used in existing kernel schedulers.

  3. Part III (10 points): Write a test program to test your netlock implementation. You need to write two programs, one user and one sleeper.
    • The sleeper should be daemon called net_monitor. It's logic is simple. It acquires a sleep net lock so that it can turn off the radio (you don't have to do the radio bit) and waits for a user timeout via the net_lock_wait_timeout syscall to release the net lock and turn on the radio. Then it loops, acquiring the sleep lock again, and repeating the entire process.
    • The user program should be called my_net_app, and accept three integer valued command line arguments, wait, timeout, and long int spin. It should sleep for wait seconds before trying to acquire a use net lock with a timeout of timeout seconds that indicates how long it can afford to wait for the radio. Finally, it should do a for loop for spin number of iterations, and after the loop is done, release the net lock. The output of the program should be four timestamped statements (using the number of seconds since epoch returned by gettimeofday) printing it's arguments and pid before sleeping, before acquiring the use lock, before entering the for loop, and finally before releasing the use lock as follows:
          $ my_net_app 10 10 30000
    1362334176: sleeping pid:135 args:10,10
    1362334186: calling_net_lock pid:135
    1362334196: return_net_lock pid:135
    1362334203: calling_net_unlock pid:135
      You can test your lock implementation and scheduler by calling this program multiple times with different values of sleep and timeout to simulate any arrival order of net_lock users you want. If your locking mechanism works, the return_net_lock statement should reflect the earliest timeout value of any net_lock user, and the return_net_lock statements of the different invocations of your test program should print in EDF order. You can vary the spin value to vary the time for which each EDF process runs before relinquishing the use lock. Optionally, you can include sample test runs in your README file to document your testing.

Error Handling

Check the return values of all functions utilizing system resources. Do not blithely assume all requests for memory will succeed and all writes to a file will occur correctly. Your code should handle errors properly. Many failed function calls should not be fatal to a program. Typically, a system call will return -1 in the case of an error (malloc will return NULL). If a function call sets the errno variable (see the function's man page to find out if it does), you should use the result of strerror(errno) as part of your error message. As far as system calls are concerned, you will want to use one of the mechanisms described in Reporting Errors or Error Reporting.