OSLab
Operating Systems Lab Resources

The Scheduler

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

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.

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

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