freezer

HW6: Freezer

Submission

As with previous assignments, we wil be using GitHub to distribute skeleton code and collect submissions. Please refer to our Git Workflow guide for more details. Note that we will be using multiple tags for this assignment, for each deliverable part.

Part 0: Learn CFS, BFS, and MuQSS

Tasks

  1. First, read the OSC and LKD reading assignments on scheduling.

  2. After you finish reading about scheduling in general and the Linux CFS scheduler, read Con Kolivas’s BFS FAQ.

  3. BFS has been discontinued since Linux 4.9. Read about its replacement, MuQSS, and how it improves on BFS’s shortcomings.

Part 1: Priorities in CFS

Tasks

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

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

Deliverables

  1. Describe in your README.txt how you created the task #1 scenario.

    • Include the command lines you executed

      • Indicate if you needed root privileges for any of those commands
    • Include the top output

      • You can remove the irrelevant rows like I did above, but do NOT remove any columns

      • Make sure to include the part where it shows the loads of all CPUs

    • Include your program in the user/test/ subdirectory if you wrote any

  2. Do the same for the task #2

Submission

To submit this part, push the hw6p1handin tag with the following:

$ git tag -a -m "Completed hw6 part1." hw6p1handin
$ git push origin master
$ git push origin hw6p1handin

Part 2: Build a kernel with MuQSS

Parts 2 through 4 should be completed on a separate branch, muqss, in your homework assignment repo. Before proceeding, create it with the following:

$ git checkout -b muqss
$ git push --set-upstream origin muqss

After pushing this branch to your GitHub repo, your teammates may switch to it by checking it out:

$ git fetch
$ git checkout muqss

You will use this new branch for experimentation with a MuQSS-patched Linux kernel. Do NOT merge in the muqss branch to your master branch.

Tasks

  1. Find the MuQSS patch file by Con Kolivas for your Linux version (4.9).

    • Create a patch/ directory in your repo and put the patch there.

    • Commit the patch file before proceeding.

  2. Apply the patch file to your Linux kernel source tree (under linux/).

    • After the patch has been successfully applied, you should be able to see that a number of files have changed upon running git status.

    • Commit these changes to your branch.

  3. Go into your Linux source tree and configure your MuQSS kernel build.

    • Regenerate/copy over your .config file from your 4.9.81-cs4118 fallback kernel.

    • Run make menuconfig, and change the local version to -<UNI>-muqss.

  4. When you exit make menuconfig, it will actually make additional modifications to your config file.

    • Save it to another name:

      $ mv .config .config-<UNI>-muqss
      $ ln -s .config-<UNI>-muqss .config
      

      This will ensure that it does not get deleted when you clean your repo with make mrproper. Since your MuQSS config file is still a local config file, please do not commit it to your homework repo.

    • Examine the difference between your MuQSS config file and the config file you used to build your 4.9.81-cs4118 mainline kernel.

      • You may use either the diff utility or the diffconfig script included in the Linux source tree.

      • Note the changes in your README.txt.

  5. Build your MuQSS kernel, and boot into it.

Deliverables

  1. The output of diff or diffconfig when comparing the config files for your mainline fallback kernel and your MuqSS kernel in your README.txt.

  2. Your statement that you have successfully patched, built, and booted into your MuQSS-enabled Linux kernel.

Submission

Note that this part is completed on the muqss branch of your assignment repo. To submit this part, push the hw6p2handin tag with the following:

$ git tag -a -m "Completed hw6 part2." hw6p2handin
$ git push origin muqss
$ git push origin hw6p2handin

Part 3: Priorities in MuQSS

Note: you should still be working on the muqss branch of your repo.

In this part, you will repeat the tasks from part 1, but after booting into the MuQSS-patched kernel.

Deliverables

  1. Repeat task #1 of part 1, and briefly describe in your README.txt how the results were different, if at all. You don’t have to include the top output.

  2. Do the same for part #2 of part 1.

  3. MuQSS features unprivileged real-time tasks. Perform task #2 of part 1 with and without root privileges, and describe the differences in your README.txt.

Submission

Note that this part is completed on the muqss branch of your assignment repo. To submit this part, push the hw6p3handin tag with the following:

$ git tag -a -m "Completed hw6 part3." hw6p3handin
$ git push origin muqss
$ git push origin hw6p3handin

Part 4: CFS v. MuQSS

Note: you should still be working on the muqss branch of your repo.

Time for a shoot-out!

Tasks

  1. Con Kolivas claims that kernel compile under MuQSS is faster than CFS. Verify his claim by timing kernel builds in both your fallback and your MuQSS-patched kernels.

    • 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 before you build.

      • This will delete your .config as well. You can recover your configurations from your backed up config file:

        $ ln -s .config-<UNI>-muqss .config 
        
    • If you’ve optimized your kernel builds with ccache, should disable that for this experiment.

    • Make sure to compile with make -j$(nproc), as Kolivas recommends.

    • You may find the time utility handy.

  2. Design an experiment that you think will highlight MuQSS’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

    You can also check out Kolivas’s own benchmarks and interbench benchmarks for inspiration.

Deliverables

Describe and explain your findings in your README.txt, including how you obtained them.

Submission

Note that this part is completed on the muqss branch of your assignment repo. To submit this part, push the hw6p4handin tag with the following:

$ git tag -a -m "Completed hw6 part4." hw6p4handin
$ git push origin muqss
$ git push origin hw6p4handin

Part 5: HZ and Jiffies

For part 5 and onwards, switch back to the master branch of your repo, where you will be working with the pristine (non-MuQSS) Linux kernel source:

$ git checkout master

Also make sure to reboot into your pristine 4.9.81-cs4118 fallback kernel (running CFS) before proceeding.

Reading assignment

Deliverables

Please write the answers to the following questions in your README.txt.

  1. Briefly describe the advantages and disadvantages of a larger HZ.

  2. What is the HZ currently configured for your running Linux system?

    • Using a kernel module might be convenient for this. You can use the HW2 skeleton code for this. No need to submit your code, but please describe what you did.

    • The answer should be 100. You’re welcome. :-) Please do verify though.

  3. What are jiffies? Explain the relationship between jiffies, HZ, and time.

  4. Find the current value of jiffies in your system, and report it in your README.txt.

    • In minutes, how much time does this jiffies value represent?

    • Does it match the uptime reported by the uptime command? (Hint: it doesn’t.) Please give the formula to convert jiffies to the current (real) uptime, in minutes.

    • Why does this large difference exist? (Hint: in 32-bit Linux systems, jiffies is a 32-bit value.)

  5. What are Niffies? How do they differ from Jiffies?

Submission

Note that this part is completed on the master branch of your assignment repo. To submit this part, push the hw6p5handin tag with the following:

$ git tag -a -m "Completed hw6 part5." hw6p5handin
$ git push origin master
$ git push origin hw6p5handin

Freezer Overview

In this assignment, we add a new Linux scheduler called Freezer. It has the following features and characteristics:

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

Part 6: Freezer built, but not yet turned on

Reading assignment

Tasks

Deliverables

Submission

To submit this part, push the hw6p6handin tag with the following:

$ git tag -a -m "Completed hw6 part6." hw6p6handin
$ git push origin master
$ git push origin hw6p6handin

Part 7: Turn on the Freezer

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.

Tasks

Tips

Deliverables

Submission

To submit this part, push the hw6p7handin tag with the following:

$ git tag -a -m "Completed hw6 part7." hw6p7handin
$ git push origin master
$ git push origin hw6p7handin

Part 8: Freeze everything!

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.

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

Tips

Deliverables

Submission

To submit this part, push the hw6p8handin tag with the following:

$ git tag -a -m "Completed hw6 part8." hw6p8handin
$ git push origin master
$ git push origin hw6p8handin

Part 9: CFS v. Freezer (optional)

Compare Freezer with CFS.

Tasks

If you got Freezer working, say a few words in your README.txt about how it performs 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.

Submission (optional)

If you’d like to submit this part, push the hw6p9handin tag with the following:

$ git tag -a -m "Completed hw6 part9." hw6p9handin
$ git push origin master
$ git push origin hw6p9handin

Good luck!


Acknowledgment

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.

John Hui, TA in Spring 2018, updated the code for the 64-bit 4.9.81 kernel, and updated the BFS portion of the assignment to MuQSS.


Last updated: 2018-03-28