Individual written problems are to be done individually. Group programming problems are to be done in your assigned programming groups. The deadline for group programming problems applies to both CVN and non-CVN students. All homework submissions are to be made via the submit programs. Refer to the homework policy page on the class web site for further details.

Individual Written Problems:

1. Exercise 5.2

2. Exercise 5.3

3. Exercise 6.2

4. Exercise 6.10

5. Exercise 7.1

6. Consider the following set of processes, with the length of the CPU-burst time given in milliseconds:

   Process 	Burst Time      Priority 
   P1 		9 		3 
   P2 		3 		1	
   P3 		2 		3	
   P4 		1 		4	
   P5 		5 		2	
   

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

   a. Draw four Gantt charts illustrating the execution of these processes using FCFS, SJF, a non-preemptive priority (a smaller priority number implies a higher priority), and RR(quantum = 1) scheduling.

   b. What is the turnaround time of each process for each of the scheduling algorithms in part a?

   c. What is the waiting time of each process for each of the scheduling algorithms in part a?

   d. Which of the schedules in part a results in the minimal average waiting time (over all processes)?

7. Describe what happens in the Linux 2.4.2 kernel when a SCHED_OTHER process runs out its time quantum and is preempted when a timer interrupt occurs. Be sure to list the procedures that are called and explain the function of each.

8. The Linux scheduler takes O(N) time to schedule a process to run, where N is the total number of processes. For uniprocessor scheduling only, could the same scheduler with the same scheduling behavior be implemented such that it only requires O(1) time to schedule? Why or why not?

Group Programming Problems:

Programming problems are to be done in your assigned groups using the VM that has been assigned to your group. 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.

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. The kernel you use for this assignment should be the Linux 2.4.2 kernel you built and installed as part of Homework #2.

Background

The purpose of this assignment is to gain better understanding of a commercial scheduler implementation (the Linux scheduler), to extend this scheduler with new scheduling policies, and to evaluate your implementation.

The basic operation of the Linux scheduler is as follows. When a scheduling decision is to be made, the schedule function (/usr/src/linux/kernel/sched.c) is invoked. Its purpose is to select the next process be allocated the CPU. When reading through the scheduler code for the first time, it is easiest to 'skip' over the multiprocessor (__SMP__) aspects and focus on the flow and the purposeful simplicity of the operations.

Within the schedule function, the current process is termed prev and the default for the next process is the idle (swapper) task. The schedule function traverses the run queue to find the best process to schedule next by starting with the init task. For each process on the run queue, it calcuates a goodness value. As it traverses the run queue, if a task is found with a greater goodness value, the scheduler replaces its pointer to the current next task with this task. When it reaches the end of the list, if unable to find a process with a nonzero 'goodness' value, it recalculates the scheduling state used to determine the goodness of SCHED_OTHER processes, then traverses the list again. Once it selects a task, bookkeeping is performed and then architecture-specific functions are used to actually switch to this next task.

The goodness of a task is calculated differently depending on the scheduling policy. For the real time policies (SCHED_RR and SCHED_FIFO), this goodness is the priority (rt_priority) of the process plus a 'boost' to make sure runnable real-time processes always have more goodness than non-realtime processes. Non-realtime processes are scheduled under the SCHED_OTHER policy. Under SCHED_OTHER, goodness is based primarily on the counter and the nice value of the process. The counter is the number of ticks a process will be allowed to run when it is allocated the CPU. If a process was interrupted during it's last allocation of the CPU, the counter value is the number of ticks remaining from the process' last allocation.

Now we get to the fun part!

1. (10 pts.) A proportional share scheduler is one that allocates CPU cycles to processes in proportion to each process's assigned weight. For example, if processes P1 and P2 are both runnable and have assigned weights 3 and 1, a proportional share scheduler will give P1 3 times as many CPU cycles as P2. How can SCHED_OTHER be used to provide proportional share behavior? Write a simple while loop program to test the proportional share behavior of SCHED_OTHER. Your test program's processing loop should not contain I/O operations as they would skew your results. Run 5 different copies of the program concurrently such that the respective processes behave as though they are assigned weights 1, 2, 3, 4, 5.

2. (10 pts.) Show that the CPU time given to each process is in proportion to its weight. Since utilities such as top and ps will be too coarse grained to collect the information you require, you will need a more suitable mechanism to collect the data. Start by simply inserting printk statements in the scheduler to gauge the accuracy of your policy. Obviously, the number of printk statements should be few as the scheduler is time critical and is called very frequently.

   For your final report, use statistics collected by a small program which calls pinfo to retrieve the system and user times of each of the 5 processes at 1 second intervals. You may use your own code for the pinfo system call, or the code posted in the solutions for Homework 2.

3. (30 pts.) Extend the Linux scheduler with a weighted round-robin scheduler. Like other schedulers, it should have a name. Call it SCHED_WRR. SCHED_WRR should be implemented such that it schedules in O(1) time and uses a time quantum of 2 jiffies for a process with weight 1. Furthermore, SCHED_WRR should not run if any real-time (SCHED_RR or SCHED_FIFO) processes need to run, and SCHED_WRR must not starve SCHED_OTHER processes from running, and SCHED_OTHER processes must not starve SCHED_WRR processes from running. You will need to modify the sched_setscheduler system call to allow users to select your new scheduling policy and to assign a weight to a process. Use the same while loop program as before to test your implementation of SCHED_WRR by running 5 different copies of the program concurrently, with respective weights 1, 2, 3, 4, 5.

4. (10 pts.) As in the case of SCHED_OTHER, show that the CPU time given to each process is in proportion to its weight. For your final report, use statistics collected by a small program which calls pinfo to retrieve the system and user times of each of the 5 processes at 1 second intervals. Based on your measurements, is SCHED_WRR or SCHED_OTHER more accurate in proportionally allocating CPU cycles? Conceptually, which scheduler should be more accurate? Do your measurements support your conceptual understanding? Why or why not?

Additional Information:

• As a safety measure, you are strongly encouraged to copy the source files you plan to modify to your home directory on the host system, make your modifications and then FTP your version of the source file to the guest system for the build. Obviously, you still do your builds on the guest system, this procedure is just to ensure your work is not lost in the event of a failure.

• Do not change the prototype for the scheduler system calls or the sched_param structure passed to these calls. Also do not modify the task structure (you will not need to and it will result in significantly more work than this assignment requires).

• You may find the KDB debugger that you installed as part of your first assignment to be a helpful development tool for this assignment.

• 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.