OSLab
Operating Systems Lab Resources

The Scheduler

Modified. See HW2a and HW2b.

out 9/22/06, due 10/13/06 detailed instructions

Objective

You will learn how process management is designed, particular how the scheduler is implemented. The scheduler is the heart of the multiprogramming system. It is responsible for choosing a new task to run whenever the CPU is available. In this project, you will replace the standard scheduler with a fair-share scheduler. And you will learn how to observe the behavior of the fair-share scheduler and of the standard scheduler.

Background

Fair-share scheduling [Bach 1986] is a more abstract strategy for scheduling than any of the three built-in strategies. The idea is that the CPU should be shared among sets of processes according to the groups that own those processes. For example, suppose that Tom, Dick, and Harry belong to different groups and are logged in to a machine that used fair-share scheduling. Further, suppose that Tom has only one runnable process, Dick has three, and Harry has six. Fair-share scheduling calls for ten runnable processes and instead of each process getting 10% of the CPU cycles, the three groups each get one-third of the CPU cycles to allocate the processes that they own. So Tom's single process will get 33% of the available CPU cycles, each of Dick's processes will get about 11% of the available CPU cycles. and each of Harry's six processes will get about 5.5% of the CPU cycles. If Betty belongs to Dick's group and she logged in to the machine and created two more processes, then Tom's group would have one process but still receive one-third of the CPU cycles. Dick and Betty would have five processes and would be allocated one-third of the CPU cycles, distributed equally among their five processes, with each receiving about 6.7% of the total machine cycles. Each of Harry's six processes would continue to receive about 5.5% of the available CPU cycles.

Start-time Fair Queuing [Goyal '96] is a computationally simple version of weighted fair queuing. For illustration, assume that the weights of all processes add up to 100%. If the weight of process A is 10%, and it has just finished running for 100ms, then the latest time that it could start running again is 1000ms from now. So we put it on the run list with a start time of now+1000ms. If we always schedule the task with the earliest start time, and preempt it when its new start time would be later than that of another task on the run queue, then (within the limits of scheduling granularity) each process will receive its fair share of CPU time. In implementation we use virtual time, instead of real time, and each time a new process is selected we update the virtual clock to equal the start time of that process.

Problem Statement

You are to modify the Linux scheduler and then measure the performance of the system with and without the modified scheduler so that you can compare the effect of the new scheduler.

1. Add a New Scheduling Policy to Support Fair-share Scheduling Start-time fair queuing (STFQ)

• To simplify the problem, have your new scheduler have all processes use fair-share scheduling on the basis of each process's UNIX group identification (as specified in its task descriptor). That is, when your system is running the fair-share scheduler the sched_setscheduler() system call will have no effect.
• Keep a virtual clock, V, and give each process a scheduling deadline, S. When a scheduling decision is made (schedule() or schedule_tick()), if the current process has weight w and has been running for time t, set S to max(V, S+t/w). Choose the process from the run queue with the least value of S, and set V to that value before switching to it.
• To simplify the problem, have all processes use STFQ. Since this is the case, the dynamic priority mechanism and the nice() system call will have no effect on scheduling, so we are free to use nice() to set process weights. (check the getpriority man page for information on how the system library translates external nice values in -20..19 to internal ones)

2. Comparing Scheduler Performance

• Insert instrumentation software into the kernel so that you can obtain detailed performance data regarding the scheduler's behavior. Add a new system call boot parameter that enables or disables the instrumentation. Also, have the system call include an option to initialize the instrumentation and another to dump its internal statistics to a filecreate a /proc file which allows you to dump the scheduler statistics. Study the behavior of your fair-share scheduler, and report on its performance.

Attacking the Problem

You need to modify "kernel/sched.c" to implement your scheduler, and other components, such as the task descriptor. Design your strategy for implementing the fair-share scheduler so that it has as little impact on the existing code and data structures as possible, even if you have to sacrifice some performance. After you get the new scheduler to work properly, you can reconsider the design from the performance perspective.

Submitting Your Assignment

Please submit the following items to lab6 dir on elgate:

1. All source codes/files that you have added/modified and the demonstrative results;
2. A "README" file that contains the follows :
   1. Design, for instance, how did you implement the scheduler;
   2. How did you demonstrate that your scheduler worked;
   3. Suggestions/lessons and useful materials you found;
   4. List of all your files you submitted.
3. A technical report (.ps or .pdf file) that includes the following sections:
   1. Problem description which includes some backgrounds and the current schedulers.
   2. The design of your algorithm. In this section, you should describe the major design, the data structures, the complexity and overhead of your algorithm (required for graduate students), and some other issues that are important factors in your design or implementation.
4. Experimental results. This Section should at least include: 1) how do you design the test, e.g., the criteria you are using to measure the correctness of the algorithm and the overall test strategy; 2) the results with different testing parameters (figures); 3) analysis for those results.
5. Conclusion. In addition to the simple conclusion for your project, you may have some thoughts about, for instance: 1) to which scenario this algorithm may be applied compared to other existing schedulers; 2) what's the advantages and disadvantages of this algorithms for different applications; 3) how to extend this algorithm if possible; and so on. Please put those discussions in this section if you have.
6. Compiled kernel image with the new changes.