Programming assignment #4 - CPU Scheduling

Due by Monday, November 11th .

Please use the class discussion board (you can find it on your blackboard) as a communication and Q&A tool.  Should you still need to send an e-mail inquiry, address it to the TA (Xiaowan Dong: xdong at cs...) and cc the instructor. This assignment will be examined through demo with the TA. The demo time should be conducted with the TA by the due date or earlier. We expect that each demo will take 20-30 minutes. Please reserve your time slot with the TA ahead of time.

This is a group assignment. This is a group assignment. You may form a group of two to complete this assignment. As with the last assignment, please switch to a different partner.

Disclaimer: This assignment is adapted from a project developed by Dr. Jason Nieh at Columbia University.

Assignment background: GWRR Scheduling

The Linux scheduler repeatedly switches between all the running tasks on the system, attempting to give a fair amount of CPU time to each task. Fair-share scheduling is a strategy that shares the CPU among sets of processes according to the groups that own those processes. For example, suppose that Mary, Jane, and Sam belong to different groups and are logged in to a machine that uses fair-share scheduling. Suppose Mary has one runnable process, Jane has three, and Sam has six. Fair-share scheduling views the ten runnable processes in three groups, and each group receives one-third of the CPU cycles allocated to the processes that it owns. Mary's single process would therefore get about 33% of the available CPU cycles, each of Jane's three processes would get roughly 11% of the available CPU cycles, and each of Sam's six processes would get about 5.5% of the CPU cycles. Suppose Jim belongs to Jane's group and he logs in to the machine and creates two more processes. Then Mary's single process would still get its 33% of the CPU and each of Sam's six processes would still get about 5.5% of the CPU. Jim and Jane together would have five processes that in total receive one-third of the CPU, so that each process would get about 6.7% of the CPU.

We introduce a new scheduling policy to support fair-share scheduling. We call this policy GWRR, for group weighted round-robin scheduling. GWRR should use fair-share scheduling based on each process's UNIX group identification. At each invocation of the scheduler, we will use a hierarchical scheme to choose which task to run: first, a group is chosen, then, a task within that group's set is chosen. If we allow each group's chosen task the same amount of time on the CPU, each group should be represented equally.

Since we have to make two choices in each scheduling decision, we need two algorithms: one to choose the group and one to choose one of that group's tasks. Let's start by assuming we will use a Round-Robin scheme to decide which group to choose. We keep a queue of groups, and whichever group was chosen last time we scheduled, we choose the next group in the queue for this schedule. We then choose a task within this group's set of tasks (more on this later), and let it run for a fixed amount of time. Now every group gets an equal amount of CPU time at a relatively fine grain.

Now let's say that some groups are more equal than others. Imagine that we associate an integer, which we'll call a weight, with each group. We then modify the round-robin algorithm above so that we pick the same group for W time quanta (instead of a single time quantum), where W is the group's weight, before moving on to the next group in the queue. In this way, we can specify that some groups get more CPU time than others, and also how much more. A group with a weight of 3 will get 50% more CPU time than a group with weight 2. This is called proportional sharing. More specifically, this implementation of proportional sharing is called Weighted Round-Robin.

We still haven't specified how a task is to be chosen once we choose a group. For simplicity, use a simple round-robin (RR) scheduling algorithm to do that. The intragroup RR scheduler should use the same default timeslice as the Linux scheduler uses for a task with the default nice value. Otherwise, the RR scheduler should work the same as GWRR except that it schedules tasks, not groups, and there are no different task weights.

Assignment description

In this assignment, you are asked to implement a new task scheduler GWRR as described above:

Create five users: Mary, Jane, Sam, Jim, and Pat. Assign Mary and Jane to the same group, Sam and Jim to the same group, and Pat to a separate group. Assign weights of 30, 10, and 10 to the respective groups. Create a simple test program that measures its own CPU usage as it runs and and use it to show that your GWRR scheduler behaves properly. Prepare the tests before the demo and document your results in a writeup taken to the demo.

Help on Linux administration:
Groups can be added using the command: "groupadd group_name" and users can be added using the command: "useradd user_name".