OPERATING SYSTEMS I: Junfeng Yang

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

The test program is due 03/23 at 12:01am EDT

Jingyue will be holding a TA session on this homework at CSB 477 (the open area) from 4-6 on Wednesday, March 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.19
MOS 2.22
MOS 2.33
MOS 2.35
MOS 2.37
MOS 3.3
MOS 3.4
Describe how the time slice for a SCHED_NORMAL process may be updated in Linux 2.6.11. Be sure to list the relevant procedures, data structures, and variables; explain the meaning of each.

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: Adding a New Scheduling Algorithm to Linux (60 pts)

Programming problems are to be done in your assigned groups using copies of the virtual machine (VM) image already provided. For all programming problems you will be required to submit source code, 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. 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.

You will build your own Linux kernel for this class. The image of the kernel you build for this assignment should be vmlinuz.hmwk4. Grading for this assignment will be done based on vmlinuz.hmwk4. You will 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.

Description

The Linux kernel supports kernel-level threads, which have to be scheduled by the kernel scheduler. Thus, we do not distinguish thread scheduling and process scheduling in this homework; instead, we call them task scheduling.

When the Linux kernel scheduler chooses a task, it considers a variety of factors. However, it doesn't consider the likelihood that a task may race with one of the currently running tasks. In this assignment, you will add a race-averse scheduling algorithm to the Linux kernel, to let the kernel schedule a task that is least likely to race with any of the currently running tasks.

For this scheduling algorithm to work, the kernel scheduler has to know how likely two tasks race. We will ask users to specify these likelihood numbers in two steps. First, they assign colors to tasks, where a color is represented as an integer in the range of [0, 5). Then, they assign race probabilities between colors, where a probability is represented as an integer in the rage of [0, 10]. The higher this integer, the more likely the tasks of the two colors race with each other.

Once users specify the colors and race probabilities between colors, our race-averse scheduling algorithm should work as follows. It should iterate through all colors, compute an overall race probability (the race probability for tasks of each color to race with any of the currently running tasks) for each task, and schedule a task of the color with the smallest overall race probability. If the chosen color has more than one tasks, you should round-robin between them. If there are more than one colors with the minimum race probability, your design should avoid starving one of the colors.

For simplicity, the overall race probability of a color should be computed using simple sums, as shown in the pseudo code below:

      int overall_race_prob(int color) {
          int prob = 0;
          foreach running task T {
              int c = T's color
              prob += race_prob(color, c); // race_prob() returns the race 
                                           // probability between color and c
          }
          return prob;
      }

You are strongly advised to read Understanding Linux Kernel Chapter 7 Process Scheduling, before starting the programming assignment. Most of the code of interest for this assignment is in kernel/sched.c and include/linux/sched.h. These are probably not the only files you will need to look at, but they're a good start. While there is a fair amount of code in these files, a key goal of this assignment is for you to understand how to abstract the scheduler code so that you learn in detail the parts of the scheduler that are crucial for this assignment and ignore the parts that are not.

(50 pts.) Implement a new task scheduler - Race-Averse Scheduler (RAS)
- Implement race probabilities. Add two system calls, getprob() and setprob(), with the following prototypes:
  
  int getprob(int color1, int color2);
  
  int setprob(int color1, int color2, int prob);
  
  Give getprob() syscall number 291, and setprob() number 292. getprob() should return the race probability of the specified color pair, or -1 on error. The default race probability should be 0. setprob() should give the specified color pair the specified race probability, and return 0, or -1 on error. Race probabilities are symmetric: race_prob(color1, color2) == race_prob(color2, color1).
  
  The range of color should be [0, 5). A bad color should result in a return value of -1 and errno set to EINVAL. The range of prob should be [0, 10]. A bad prob should result in a return value of -1 and errno set to EINVAL. Only root is allowed to call setprob(); a call by any other user should return -1 and set errno to EPERM.
  
  Again, put your code for these two system calls at the bottom of kernel/sched.c.
- Implement colors. Add two system calls, getcolor() and setcolor(), with the following prototypes:
  
  int getcolor(int pid);
  
  int setcolor(int pid, int color);
  
  Give getcolor() syscall number 289, and setcolor() number 290. getcolor() should return the color of the specified task (identified by pid, the process id), or -1 on error. The default user color should be 0. setcolor() should give the specified task (identified by pid, the process id) the specified weight, and return 0, or -1 on error.
  
  The range of color should be [0, 5). A bad color should result in a return value of -1 and errno set to EINVAL. Only root is allowed to call setcolor(); a call by any other user should return -1 and set errno to EPERM.
  
  Put your code for these two system calls at the bottom of kernel/sched.c.
- Implement the race-averse scheduling algorithm discussed above.
  - You should add a new scheduling policy, SCHED_RAS. The value of SCHED_RAS should be 4. Only tasks whose policy is set to SCHED_RAS (normally done via the system call sched_setscheduler()) should be considered for selection by your new scheduler.
  - When computing overall race probabilities to make a scheduling decision for one CPU, you should consider processes currently running on all other CPUs.
  - If only one color has the minimum race probability, you should schedule a task of this color. It is OK for tasks of this color to starve tasks of other colors. However, it is not OK for a task of this color to starve another task of the same color. Instead, you should use RR to schedule tasks of the same color. The time slice for each RAS task should be 100 ms.
  - If two colors have the same minimum race probability, you should avoid the situation where tasks of one color starve tasks of the other color.
  - Linux uses an O(1) scheduler: picking the next process to run takes constant time. Your scheduling algorithm should adhere to this goal. We will take off points for algorithms that are O(N) (N is the number of ready SCHED_RAS processes).
- Your scheduler and the existing scheduler should interoperate as follows:
  - If there are any running tasks whose policy is SCHED_RR or SCHED_FIFO, one of them should be chosen before any other, according to the existing Linux scheduler rules.
  - If there are any running tasks whose policy is SCHED_RAS (your scheduler), one of them should be chosen before any SCHED_NORMAL (the default scheduler) tasks, according to the rules outlined.
  - If all running tasks have a policy of SCHED_NORMAL, default scheduler should be used to choose a task, according to the default scheduler's rules.
  In other words, there should be a strict priority relationship where SCHED_RR and SCHED_FIFO are first, SCHED_RAS is second, and SCHED_NORMAL is last.
  
  Making your scheduler operate alongside the existing may seem like an unnecessary difficulty, but it spares you the (significant) difficulty of dealing with scheduling during initialization, so you can get a system up and running before any of your own code goes into action.
(10 pts.) Create a simple test program to show that your scheduler works
Write a program that creates a number of threads and sets up their colors and race probabilities between the colors. Each of the thread should run something like:
```
        int i;
        time_t start, end;
        time(&start);
        while(++i < MAX_ITER)
                sched_yield();
        time(&end);
        printf ("thread %d ran for %d seconds\n", 
                (int)pthread_self(), end-start);
          
```
Normally these threads should run roughly the same amount of time. However, you can vary the race probabilities to make the threads run different amount of time.

For example, if you create three threads T1, T2, and T3, each having a different color C1, C2, and C3. Then, you set two colors C1 and C2 to have a race probability of 0 between them, but a race probability of 10 with the third color C3. Then, you should observe that T1 and T2 run roughly the same amount of time, but T3 runs roughly twice long. Why? figure it out.

Hints on the assignment:

Linux uses prio_array_t for keeping track of tasks for scheduling. Tasks in this array are indexed by priority. You may find this data structure useful for implementing RAS. Specifically, you may consider adding another priority level, representing RAS tasks. If you do so, you have to avoid letting users observe invalid nice values. So, you must modify functions that set and get nice values accordingly.
As aforementioned, there are two starvation scenarios you should avoid: (1) one task starves other tasks of the same color, and (2) tasks of one color starve tasks of another color when they have a tie on minimum overall race probability.

To avoid the first starvation scenario, you may want to put all ready SCHED_RAS tasks on one queue, and round-robin between them. To avoid the second starvation scenario, you may want to traverse this queue from the beginning until you find a task with the minimum overall race probability. This solution works, but it may have a time complexity of O(N) in the worst case. A more efficient solution is to remember when each SCHED_RAS task is appended to the queue, so that you can break the tie between tasks of two colors by simply choosing the task appended to the queue the earliest.

There are definitely other ways to solve the starvation problems described above. You are highly encouraged to come up with your own algorithm. Just make sure that its time complexity is still O(1).

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)

Programming Assignment: Adding a New Scheduling Algorithm to Linux (60 pts)

Description

Additional Information