HW6: 200 points total, group project
Submission notes
The submission process is the same as HW5, except the name of the
tarball. That is, one member of a group will submit a single gzipped
tar file named group_xx_hw6.tgz
where xx is your two digit group
number (with leading zeros, if applicable).
The top level directory in the tarball must be hw6
.
Please use the kernel version 4.4.50.
First, read the OSC and LKD reading assignments on scheduling.
After you finish reading about scheduling in general and the Linux CFS scheduler, read Con Kolivas’s BFS FAQ.
Start 10 processes of a CPU-bound program in a VM that has multiple
CPUs. Make all 10 processes run on a single CPU. Arrange the relative
priorities between them so that 5 of them will use about 70% of the CPU
and the other 5 will use the remaining 30%. The processes in each group
of 5 will have equal priorities between them. Verify it using the top
command.
Here is a part of the screen of a sample top
session:
top - 23:15:24 up 6:45, 12 users, load average: 10.00, 10.07, 10.24
Tasks: 177 total, 11 running, 166 sleeping, 0 stopped, 0 zombie
%Cpu0 : 0.0/0.0 0[ ]
%Cpu1 : 0.0/0.7 1[| ]
%Cpu2 : 100.0/0.0 100[|||||||||||||||||||||||||||||||||||||||||||]
%Cpu3 : 0.0/0.0 0[ ]
%Cpu4 : 0.0/0.0 0[ ]
%Cpu5 : 0.0/0.0 0[ ]
%Cpu6 : 0.0/0.0 0[ ]
%Cpu7 : 0.0/0.0 0[ ]
GiB Mem : 10.4/3.457 [ ]
GiB Swap: 0.0/0.000 [ ]
PID %CPU COMMAND
457 0.0 `- xfce4-terminal
521 0.0 `- gnome-pty-helpe
524 0.0 `- bash
531 0.0 `- bash
3854 0.0 `- myprogram
3857 13.9 `- myprogram
3858 13.9 `- myprogram
3859 13.9 `- myprogram
3860 13.9 `- myprogram
3861 14.6 `- myprogram
3863 0.0 `- myprogram
3864 6.0 `- myprogram
3865 5.3 `- myprogram
3866 6.6 `- myprogram
3867 6.0 `- myprogram
3868 6.6 `- myprogram
It shows the 10 processes of myprogram
(not counting the two parent
processes that forked them), dividing the CPU time as specified. I
chose to run them on the Cpu2
among the 8 available cores.
You can code up your own program (and you don’t have to name it myprogram), or you can use any existing command line tools to create the scenario.
Now, add one more process of myprogram
, but this time with real-time
priority. Verify that the real-time process preempts all the other 10
processes. Here is a sample top
session for this:
top - 23:25:57 up 6:56, 11 users, load average: 10.43, 10.54, 10.47
Tasks: 180 total, 13 running, 167 sleeping, 0 stopped, 0 zombie
%Cpu0 : 0.0/0.0 0[ ]
%Cpu1 : 0.7/0.0 1[| ]
%Cpu2 : 100.0/0.0 100[|||||||||||||||||||||||||||||||||||||||||||]
%Cpu3 : 0.0/0.0 0[ ]
%Cpu4 : 0.0/0.0 0[ ]
%Cpu5 : 0.0/0.0 0[ ]
%Cpu6 : 0.0/0.0 0[ ]
%Cpu7 : 0.0/0.0 0[ ]
GiB Mem : 10.6/3.457 [ ]
GiB Swap: 0.0/0.000 [ ]
PID %CPU COMMAND
3854 0.0 `- myprogram
3857 0.0 `- myprogram
3858 0.0 `- myprogram
3859 0.0 `- myprogram
3860 0.0 `- myprogram
3861 0.0 `- myprogram
3863 0.0 `- myprogram
3864 0.0 `- myprogram
3865 0.0 `- myprogram
3866 0.0 `- myprogram
3867 0.0 `- myprogram
3868 0.0 `- myprogram
5317 0.0 `- myprogram
5318 100.0 `- myprogram
Describe in your README.txt
how you created the task #1 scenario.
Include your program in the test
subdirectory if you wrote any.
Include the command lines you executed. Include the top
output.
You can remove the irrelevant rows like I did above, but do NOT
remove any columns. Also make sure to include the part where it shows
the loads of all CPUs.
Do the same for the task #2. Also answer whether the root privilege is required for creating the task #2 scenario.
Find the BFS patch file by Con Kolivas, and apply it to your kernel source.
You will build another custom kernel with version string 4.4.50-UNI-bfs
.
You will later compare the performance of the BFS kernel with that of your
previous 4.4.50-UNI
kernel.
Create a separate kernel build directory, named linux-4.4.50-bfs
for example. You will use this directory to build a BFS-patched kernel,
which you will use to perform tests. But all your answers and test
results should go into the README.txt
in your git repo, i.e.,
../linux-4.4.50/README.txt
. Nothing will be submitted from this
linux-4.4.50-bfs
directory.
Copy over the .config
file from the ../linux-4.4.50
directory.
Learn how to apply a patch file, and patch the kernel with the right version of BFS patch.
After you apply the BFS patch file, run make menuconfig
, and change
the local version to -UNI-bfs
so that the kernel version string will
be 4.4.50-UNI-bfs
.
When you exit make menuconfig
, it will actually make additional
modifications to your .config
. Save it to another name, like
.config-UNI-bfs
. Examine the diff of the old and new config files.
Copy and paste the diff of the two config files. For example:
diff ../linux-4.4.50/.config .config-UNI-bfs
Your statement that you have successfully patched and built your BFS-enabled kernel, and successfully booted into it.
In this part, you will repeat the tasks from part 1, but after booting into
the BFS-patched kernel. Remember that all your answers should go into
../linux-4.4.50/README.txt
.
Repeat the task #1 of part 1. Briefly describe how the result is
different, if there is any difference. You don’t have to include the
top
output.
Repeat the task #2 of part 1.
BFS features unprivileged real-time tasks. Perform the task #2 of part 1 with and without root privilege. Describe the difference.
Time for a shoot-out!
Con Kolivas claims that kernel compile under BFS will be faster than CFS. Verify his claim.
Note that there is no right answer here. Your mileage may vary. The fact that we are running in a VM affects the results too.
Run make mrproper
to clean up your kernel build directory. It
will delete your .config
as well. You need to copy it back from
your saved one.
You may find time
command handy.
Design an experiment that you think will highlight BFS’s strength. Perform the experiment and report your findings.
Some possible activities you might like to consider:
Kernel compile in the background
Watching hi-res video
Highly interactive tasks
CPU-intensive tasks
Please write the answers to the following questions in your README.txt
.
What are the advantages and disadvantages of a larger HZ? You don’t have to write an essay. Be brief, like 2 - 3 sentences for each.
What is Jiffies? What is the relationship between jiffies
and
jiffies_64
? Again, be brief.
Print the current value of jiffies
in your system. Report it in your
README.txt. What uptime does it represent? Verify using the uptime
command.
Print the current value of jiffies
and jiffies_64
together. Report
them in your README.txt. Did you expect them to be the same? Are they?
If they are different, explain why. (Feel free to google for things.)
Please make sure you have done the OSC and LKD reading assignments on scheduling.
In this assignment, we add a new Linux scheduler called Freezer. It has the following features and characteristics:
Implements a simple round-robin scheduling algorithm.
Supports SMP.
Every task has the same time slice of 100 milliseconds.
When deciding which CPU a task should be assigned to, it should be assigned to the CPU with the least number of freezer-policy processes.
The freezer scheduling policy, SCHED_FREEZER, sits right in between SCHED_NORMAL and the real-time scheduling policies. That is, SCHED_FREEZER takes priority over SCHED_NORMAL, but not over SCHED_RR or SCHED_FIFO.
Parts 6, 7, 8 are structured to guide you in developing a new scheduler. Each part represent a milestone towards a working scheduler implementation. This forces you to develop incrementally. This also allows us to award you partial credits if you could not get the whole working at the end.
In part 6, you will code up all the necessary data structures for freezer and add them to the right places, but they will remain unused by the rest of the kernel.
In part 7, you will flesh out the implementation of freezer and enable it in the kernel. But you will keep the old CFS scheduler as the default, so that the system will boot even if your freezer implementation is still unstable.
In part 8, you will make freezer the default scheduler of your kernel. All normal processes and kernel threads will run on freezer (unless they are explicitly assigned to a specific scheduling policy).
Implement the following data structures and definitions. For grading purpose, please use the EXACT names. Points for this part will be based on your design and placement of these data structures.
// SCHED_FREEZER must be defined to be 7
#define SCHED_FREEZER 7
// define FREEZER_TIMESLICE so that every task receives
// a time slice of 100 milliseconds
#define FREEZER_TIMESLICE <the-right-value>
// freezer run queue and entity
struct freezer_rq;
struct sched_freezer_entity;
// freezer scheduling policy implementation
// put the code in kernel/sched/freezer.c
struct sched_class freezer_sched_class
The freezer_sched_class
methods can be left incomplete at this point
because no one is going to call them. Maybe have the struct and
functions defined, but leave most of them empty. Maybe put some “TODO”
comments. Your objective in this part is to get all your data
structures in the right place and get them compiled.
idle_task.c
for an example of a very minimal sched_class object.freezer_sched_class
in kernel/sched/freezer.c
.Learn from the man page of the ps
command what the following command
shows you:
ps -e --forest -o sched,policy,psr,pcpu,c,pid,user,cmd
Use the ps command above before and after this part, to verify that your addition to the kernel had no effect.
Now we turn on the freezer, and hook it up to the rest of the kernel. You will have to modify various parts of the kernel to enable the new SCHED_FREEZER scheduling policy. However, in this part, SCHED_NORMAL will remain as the default policy.
Make sure that the CFS scheduler is still the default scheduler. Use the ps command from part 6 to verify that everything is still the same when you booted into your new freezer-enabled kernel.
Write set-freezer
, a command line program that changes a process’s
scheduling policy to SCHED_FREEZER. It takes a PID as a argument.
Your objective in this part is to have your kernel and the set-freezer program to work together successfully, so you can change a process’s scheduling policy to freezer, and verify it with the ps command from part 6.
If your freezer code is not quite stable at this point, it might be easier to get things to work if you use I/O-bound processes for testing, like your editor. Here is a sample session of changing 6 gvim processes, and an excerpt from the ps output:
$ ./set-freezer 1522
[1522] sched policy changed: 0 --> 7
$ ./set-freezer 1527
[1527] sched policy changed: 0 --> 7
$ ./set-freezer 1532
[1532] sched policy changed: 0 --> 7
$ ./set-freezer 1537
[1537] sched policy changed: 0 --> 7
$ ./set-freezer 1542
[1542] sched policy changed: 0 --> 7
$ ./set-freezer 1547
[1547] sched policy changed: 0 --> 7
0 TS 0 0.0 0 514 jae /usr/lib/at-spi2-core/at-spi2-registryd
0 TS 2 0.0 0 1165 root /usr/sbin/rpc.statd --no-notify
0 TS 1 0.0 0 1167 rpc /usr/bin/rpcbind -w
7 #7 0 0.0 0 1522 jae gvim -R set-freezer.c
7 #7 1 0.0 0 1527 jae gvim -R set-freezer.c
7 #7 1 0.0 0 1532 jae gvim -R set-freezer.c
7 #7 1 0.0 0 1537 jae gvim -R set-freezer.c
7 #7 0 0.0 0 1542 jae gvim -R set-freezer.c
7 #7 2 0.0 0 1547 jae gvim -R set-freezer.c
Include your session in your README.txt.
Some relevant source files: core.c
, rt.c
, fair.c
This is going to be hard to debug. You might want to invest a little bit
of time up front and learn how to use trace_printk()
, and the ftrace
tracing framework in general. Googling turns up many resources.
Now let’s make freezer the default scheduling policy. This means that all
system and user tasks will have the SCHED_FREEZER policy by default. You
need to set the freezer scheduling policy for the init_task
, which will be
inherited by all its descendants. You also need to set it for all kernel
threads, which is done in kernel/kthread.c
.
Verify that the ps output shows that most tasks, including kernel threads, are running under freezer. The SCH column will show 7 and the POL column will show “#7”.
Verify that new tasks get the freezer policy.
Verify that the tasks are assigned to CPUs as specified.
Verify that the tasks run in round-robin fashion.
Verify that your scheduler is stable and can handle running multiple CPU-intensive tasks.
Here is a part of a ps command output that shows 20 CPU-bound processes running across 4 CPUs:
$ ps -e --forest -o sched,policy,psr,pcpu,c,pid,user,cmd
SCH POL PSR %CPU C PID USER CMD
7 #7 1 0.0 0 2 root [kthreadd]
7 #7 0 0.0 0 3 root \_ [ksoftirqd/0]
7 #7 0 0.0 0 4 root \_ [kworker/0:0]
7 #7 0 0.0 0 5 root \_ [kworker/0:0H]
7 #7 1 0.0 0 6 root \_ [kworker/u8:0]
7 #7 2 0.0 0 7 root \_ [rcu_sched]
7 #7 0 0.0 0 8 root \_ [rcu_bh]
1 FF 0 0.0 0 9 root \_ [migration/0]
1 FF 0 0.0 0 10 root \_ [watchdog/0]
1 FF 1 0.0 0 11 root \_ [watchdog/1]
1 FF 1 0.0 0 12 root \_ [migration/1]
7 #7 1 0.0 0 13 root \_ [ksoftirqd/1]
7 #7 1 0.0 0 14 root \_ [kworker/1:0]
...
7 #7 0 0.0 0 1 root /sbin/init
7 #7 2 0.0 0 139 root /usr/lib/systemd/systemd-journald
7 #7 0 0.0 0 163 root /usr/lib/systemd/systemd-udevd
7 #7 0 0.0 0 208 avahi avahi-daemon: running [vm04.local]
7 #7 0 0.0 0 217 avahi \_ avahi-daemon: chroot helper
7 #7 1 0.0 0 210 root /usr/bin/haveged -F -w 1024 -v 1
7 #7 2 0.0 0 211 root /usr/lib/systemd/systemd-logind
7 #7 2 0.0 0 212 dbus /usr/bin/dbus-daemon --system
7 #7 3 0.0 0 215 root /usr/bin/dhcpcd -q -b
7 #7 0 0.0 0 221 root /usr/bin/VBoxService -f
7 #7 0 0.0 0 223 root login -- jae
7 #7 2 0.0 0 271 jae \_ -bash
7 #7 1 0.0 0 278 jae \_ /bin/sh /usr/bin/startx
...
7 #7 1 59.0 59 387 jae \_ xfce4-terminal
7 #7 0 0.0 0 452 jae | \_ gnome-pty-helper
7 #7 2 0.0 0 455 jae | \_ bash
7 #7 0 26.6 26 458 jae | \_ bash
7 #7 1 0.0 0 2201 jae | | \_ myprogram
7 #7 0 386 99 2204 jae | | | \_ myprogram
7 #7 0 392 99 2205 jae | | | \_ myprogram
7 #7 3 381 99 2206 jae | | | \_ myprogram
7 #7 2 390 99 2207 jae | | | \_ myprogram
7 #7 3 363 99 2208 jae | | | \_ myprogram
7 #7 2 389 99 2209 jae | | | \_ myprogram
7 #7 0 359 99 2210 jae | | | \_ myprogram
7 #7 1 393 99 2211 jae | | | \_ myprogram
7 #7 3 393 99 2212 jae | | | \_ myprogram
7 #7 2 391 99 2213 jae | | | \_ myprogram
7 #7 1 382 99 2214 jae | | | \_ myprogram
7 #7 0 393 99 2215 jae | | | \_ myprogram
7 #7 3 362 99 2216 jae | | | \_ myprogram
7 #7 2 389 99 2217 jae | | | \_ myprogram
7 #7 3 386 99 2218 jae | | | \_ myprogram
7 #7 0 383 99 2219 jae | | | \_ myprogram
7 #7 3 392 99 2220 jae | | | \_ myprogram
7 #7 2 392 99 2221 jae | | | \_ myprogram
7 #7 1 378 99 2222 jae | | | \_ myprogram
7 #7 0 381 99 2224 jae | | | \_ myprogram
7 #7 2 79392 99 2263 jae | | \_ ps -e ...
Focus on making a stable system that can handle running multiple CPU-bound processes, distributed to all available CPUs.
Note that the ps output above shows nonsensical numbers in the “%CPU” column. This is because our code, at the time of this writing, is broken in this regard. If you can get it working correctly, awesome. If not, don’t worry about it. It’s only fair that we don’t grade on something that we couldn’t get working in time ourselves… :)
Compare Freezer with CFS.
This part will not be a big part of your grade, if at all.
If you got Freezer working, say a few words in your README.txt about how they perform compared to CFS. Your comparison doesn’t have to be a quantitative one. You can explain the perceived difference as you have interacted with the two schedulers.
If your Freezer is rock solid, you may repeat the shoot-out you performed in part 4 with your freezer kernel. But this is not required.
Good luck!
Sankalp Singayapally, a TA for COMS W4118 Operating Systems I, Spring 2015, Columbia University, wrote the solution code for this assignment, based on his work in Fall 2014 in collaboration with Nicolas Mesa and Di Ruan.
Mitchell Gouzenko and Akira Baruah, TAs in Spring 2016, updated the code for the 4.1.18 kernel.
Benjamin Hanser and Emily Meng, TAs in Spring 2017, updated the code for the 4.4.50 kernel.
Last updated: 2017–03–26