2 Background

Fair-share scheduling [1] 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, Dic, and Harry belong to different groups and are logged in to a machine that used fair-share scheduling. Further, suppose that Tim has only one runnable process, Dic 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 Toms single process will get 33% of the available CPU cycles, each of Dics processes will get about 11% of the available CPU cycles. and each of Harrys six processes will get about 5.5% of the CPU cycles. If Betty belongs to Dics group and she logged in to the machine and created two more processes, then Toms group would have one process but still receive one-third of the CPU cycles. Dic 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 Harrys six processes would continue to receive about 5.5% of the available CPU cycles.

3 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 3.1 Part A:

Add a New Scheduling Policy to Support Fair-share Scheduling 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 processs UNIX group identifi- cation (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.

3.2 Part B:

Comparing Scheduler Performance Insert instrumentation software into the kernel so that you can obtain detailed performance data regarding the schedulers 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.

4 Attacking the Problem 4.1 Planning a Solution 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. 4.2 Comparing Scheduler Performance In programming assignment 1, you learned how to use the /proc file system to observe various facets of kernel performance. You should consider the /proc facilities to get your first measurements of the modified system. For example, set up an experiment using a few different groups with CPU-intensive processes (for example, processes that simply execute a very long for loop). Start several instances of the CPU-intensive process, and then use the /proc tools to see how the CPU time is distributed among the different processes. Next, you can exploit the timer information that is available to each process. You can rewrite your CPUintensive load generator program so that it reads that task timers and then report each timer value to a file. You can analyze the collective files after you have run your experiment. The first technique will not provide you with very fine-grained performance data, and the second has the liability that it does not take all activity in the system into account. After you have exploited these approaches, you should insert new instrumentation code into the kernel sources, along with a new system call to enable and disable the instrumentation. This level of performance inspection requires that you again design and modify kernel code, so you must do it carefully.