W4118 OPERATING SYSTEMS I

Spring 2011 -- Junfeng Yang

Homework 4 is due 03/28 at 12:01am EDT


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.

  1. MOS 3.4
  2. MOS 3.9
  3. MOS 3.11
  4. MOS 3.15
  5. MOS 3.21
  6. MOS 3.28
  7. MOS 3.29
  8. MOS 3.35

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: Priority Scheduling Algorithm (60 pts)

Programming assignments are to be done in your assigned groups in xv6. For the programming problems, you are required to write README documenting your files and codes. In this programming assignment, you'll implement priority scheduling algorithm in xv6.

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 hw4 origin/hw4
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 hw4-<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/hw4 hw4. 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. Note that it takes a while to run the test programs, so please be patient.

Part A: Implementing priority scheduling algorithm (40 pts)

The existing scheduler in xv6 is a Round-Robin (RR) scheduler. On each timer interrupts, the interrupt handler switches to the kernel scheduler, which then selects the next available process to run. This scheduler, while simple, is too primitive to do anything interesting.

In this assignment, you'll implement an advanced scheduler that schedules processes based on their priorities. Each process has a priority, and the scheduler always picks the process with the highest priority. The scheduler does RR scheduling for processes with equal priorities. Note: to simplify the assignment, assume all processes are single-threaded.

To implement this scheduler you will need to implement the following system calls:

Your scheduler will support five possible priority classes, identified by integers 0, 1, 2, 3, 4. The smaller the integer, the higher the priority. For example, 0 represents the highest priority. nice(incr) system call increases or decreases the priority of the current process by incr. The argument incr may be either positive or negative. For example, if the priority of the current process is 1, and after calling nice(1), the priority will become 2. The system call, nice(incr) , should return 0 only when it successfully increases or decreases the priority of the current process, and should return -1 if the priority exceeds the priority range [0, 4] or upon any other failures.

The system call getpriority(pid) retrieves the priority of the process with pid, and setpriority(pid, new_priority) sets new priority for the process with pid. These system calls should return 0 only if it successfully sets the priority, and should return -1 otherwise.

Your implementation must satisfy the following requirements. Your scheduler uses multiple queues of processes. Each queue is associated with a priority class, and it contains all processes with this priority. Only the processes in the RUNNABLE state should be in one of the ready qeueus. On each timer interrupt or when the current process yields the CPU (e.g., via a call to yield()), the scheduler puts the current process to the back of the corresponding queue. It then schedules the process from the front of the ready queue with the highest priority. If the ready queue with the highest priority is empty, the scheduler goes to the next queue, and so on.

Your queues should only store processes in the RUNNABLE state. For example, if a process calls sleep(), it should not stay in the ready queue, until it is woken up. The scheduler should put processes just created or woken up to the back of the corresponding ready queue.

The init process will initially has priority 0 as it was spawned. When some process calls fork(), the child process should inherit the priority of the parent process

Note that to simplify this assignment, we do not ask you to implement per-CPU ready queues. In stead, you keep a global array of ready queues, and the scheduler running on each CPU all grab processes from this global array.

Part B: Adding CPU affinity to the scheduling algorithm (20 pts)

As discussed in class, setting CPU affinity is often desirable because we can increase the cache locality of processes. Specifically, each process can specify the CPUs it prefers, and the scheduler tries to scheduler the process on the preferred CPUs. The first time the process runs, it populates the CPU cache. Next time it runs, it can reuse the data in the cache, increasing efficiency.

In this part of the assignment, you are required to implement CPU affinity into your scheduling algorithm. You will implement the following system calls to support CPU affinity.

The affinity is either -1, indicating that the process does not care where it runs; or it can be the ID of a particular CPU, so that the scheduler always schedules the process on the specified CPU. The getaffinity(pid) system call retrieves the affinity of the target process, while the setaffinity(pid, new_affinity) sets the new affinity to the target process. These system calls return 0 only if they executed successfully, and return -1 otherwise.

To recap, the scheduler schedules a process on the current CPU if

  1. the process affinity is -1; or
  2. the process affinity is the ID of the current CPU.
In other words, after a process is associated to a certain CPU, the process can only be run on that CPU. The only way to change the affinity of the processes is through setaffinity(pid, new_affinity) system call.

HINT: The CPU is identified through the id attribute inside struct cpu in proc.h . Just as proc is the global variable specifiying the current process, cpu is also a global varialbe specifying "this" cpu. These two important global variables are both defined in proc.h.