Homework 4 is due 03/26 at 12:01am EDT
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. Each problem is worth 5 points. Make your answers concise. You'll lose points for verbosity.
- MOS 3.4: Consder a swapping system in which memory consists of ...
- MOS 3.9: A machine has a 32-bit address space and an 8-KB page ...
- MOS 3.11: Suppose that a machine has 38-bit virtual addresses and ...
- MOS 3.15: A computer whose processes have 1024 pages in their address ...
- MOS 3.21: Suppose that the virtual page reference stream contains ...
- MOS 3.28: A computer has four page frames. The time of loading, time ...
- MOS 3.29: Consder the following two-dimensional array: ...
- MOS 3.35: A machine language instruction to load a 32-bit word into a ...
Programming Assignment: Priority Scheduling Algorithm (60 pts)
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://debug.cs.columbia.edu/xv6.git 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-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/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 interrupt, 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. Recall homework 2 for how to add new system calls.
- int nice(int incr);
- int getpriority(int pid);
- int setpriority(int pid, int new_priority);
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.
In your implementation, the scheduler will always schedule a RUNNABLE process with the highest priority. For the processes with the same priority, the scheduler follows first-come-first-serve principle, which means the earlier a process turns to RUNNABLE status, the earlier it gets scheduler.
To implement this scheduler, we suggest that you use 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. Instead, you keep a global array of ready queues, and the scheduler running on each CPU all grab processes from this global array.
Also, note that if a process's priority is set by another process by calling setpriority(), you can either leave the first process in the current priority queue or move it to the back of the priority queue with corresponding priority level.
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. Specifically, each process can specify the CPUs it prefers, and the scheduler tries to schedule the process on the preferred CPUs. The first time a process runs, it populates the CPU cache. Next time it runs on the same CPU, it can reuse the data in the cache, increasing efficiency.
In this part of the assignment, you are required to add CPU affinity support into your scheduling algorithm. You will implement the following system calls to support CPU affinity.
- int getaffinity(int pid);
- int setaffinity(int pid, int new_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 run successfully, or return -1 otherwise.
To recap, the scheduler schedules a process on the current CPU if
- the process affinity is -1; or
- the process affinity is the ID of the current CPU.
For your convenience we have marked the places where you might want to fill in your code. You can run the following command to find out all the places.
$ cd xv6
$ grep "hw4: your code here" *
Note that these are only suggestions. You can of course put your code
anywhere you want, as long as it implement the required functionality.
Note that if you do so, be sure to include a README in you submission
to explain in details what you code does.
You might want to take a look at
homework 4 FAQ
when you have questions. You are also
encouraged to use Courseworks for discussion.