DUE: Thu 11/07 at 12:05AM ET
The written problems are to be done individually. The programming problems are to be done in your assigned groups. All homework submissions are to be made via Courseworks. Refer to the homework policy section on the class web site for further details.
Written Assignment (40 pts)
Exercise numbers refer to the course textbook, Modern Operating Systems. Each problem is worth 5 points. Make your answers concise. You'll lose points for verbosity.
- MOS 3.4: Consder a swapping system in which memory consists of ...
- MOS 3.9: A machine has a 32-bit address space and an 8-KB page ...
- MOS 3.11: Suppose that a machine has 38-bit virtual addresses and ...
- MOS 3.15: A computer whose processes have 1024 pages in their address ...
- MOS 3.21: Suppose that the virtual page reference stream contains ...
- MOS 3.28: A computer has four page frames. The time of loading, time ...
- MOS 3.29: Consder the following two-dimensional array: ...
- MOS 3.35: A machine language instruction to load a 32-bit word into a ...
Programming Assignment: A Fair, Battery Saving Scheduler (60 pts)
Traditional schedulers designed for desktops and servers focus on CPU utilization, which typically keep the CPU busy if there is any process to run. However, this is not good for the mobile environment because mobile devices usually are usually constrained by battery. CPU underclocking (or throttling) is one attempt to solve the problem, but it is far from ideal because it affects all processes, even the important processes that users want to run at full speed. Can we do better than coarse grained CPU throttling? You bet. In this assignment, you will implement a scheduler that support fine-grained CPU usage limit for individual processes. For example, you can limit a non-critical process to use only 10% of the CPU time, so that even if this process is the only one ready to run, it won't consume more than 10% of the CPU.
Instead of using the stock Linux completely fair scheduler (CFS), which is too complex, you will create a simpler fair scheduler (let's call it MyCFS) and implement CPU usage limit there.
Part A: Implementing MyCFS (30 pts)
In the first part of this assignment, you will implement the fair scheduling algorithm as we discussed in class. The runqueue should be one red-black tree indexed by the virtual runtime. The schedule latency should be 10ms. For simplicity, assume that all processes using MyCFS are equally-weighted, so you don't have to worry about their nice levels.
You will add a new scheduler class called mycfs_sched_class. Its priority should be lower than fair_sched_class and higher than idle_sched_class. Put your scheduler implementation in kernel/sched/mycfs.c.
MyCFS should work alongside existing Linux schedulers. Therefore, you should add a new scheduling policy, SCHED_MYCFS. The value of SCHED_MYCFS should be 6. By default, processes are not using MyCFS, but you can use the sched_setscheduler() system call to change the scheduling policy of a process.
MyCFS should utilize all cores on the Nexus 7. You should have a MyCFS runqueue for each core. However, to make things easier, you don't have to worry about load balancing across cores. Processes on one core are never migrated to another core. If a process forks, the child should stay on the same core as the parent.
You may start with reading Documentation/scheduler/sched-design-CFS.txt. Even though you can look at the current Linux implementation of CFS, please refrain from copying the CFS code since it's way too complex for what you're requested to implement. Write your own code and be prepared to clearly explain how your code works during the demo grading.
Hints: You may find printk() and /proc/kmsg extremely useful. If you ever encounter a kernel panic (hopefully not), you can view previous messages at /proc/last_kmsg.
Part B: Adding CPU usage limit to MyCFS (30 pts)
You might have the experience that sometimes an application eats up all the CPU and makes your Nexus 7 as hot as a frying pan. In the second part of this assignment, you will make MyCFS be able to limit the maximum CPU usage of individual processes.
Let us define CPU usage by the amount of CPU time a process consumes within each period of 100ms. You will add a new system call
int sched_setlimit(pid_t pid, int limit);
to specify the CPU usage limit. For example, limit=40 means the process can only consume 40ms of CPU time within each 100ms period. Calling it with limit=0 means clearing the CPU usage limit for the process. The number of this system call should be 378.
To implement this feature, your MyCFS should schedule processes normally until a process hits its CPU usage limit. After that, MyCFS should skip that process (but continue scheduling other processes that haven't reached their limits yet) for the rest of the 100ms period. The same logic applies for multiple limited processes as well.
You don't have to interrupt a process within a scheduler tick. In the demo, it's fine if your CPU usage limit has an error within 10ms.
If a process forks, the child should inherit the CPU usage limit of the parent.
If a process switches from another scheduler to MyCFS, its CPU usage limit should be cleared.
Submit
Commit your source code changes using the git add and git commit commands you learned from the previous assignment. Remember to add your new file to the code repository. Then use the git diff command to get the code change. You should compare with the original version, so please do
git diff 365a6e06
Here 365a6e06 refers to the initial version of the kernel source before you make any modifications. Then submit the code difference in a .patch file. The file name should be hw4-<your uni>-code.patch.