HW6: Freezer

Part 0: Learn CFS & BFS

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.

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

  2. Do the same for the task #2. Also answer whether the root privilege is required for creating the task #2 scenario.

Part 2: Build a kernel with BFS

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.

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

  2. Copy over the .config file from the ../linux-4.4.50 directory.

  3. Learn how to apply a patch file, and patch the kernel with the right version of BFS patch.

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

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

Deliverables

Part 3: Priorities in BFS

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.

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

  2. Repeat the task #2 of part 1.

  3. BFS features unprivileged real-time tasks. Perform the task #2 of part 1 with and without root privilege. Describe the difference.

Part 4: CFS v. BFS

Time for a shoot-out!

  1. Con Kolivas claims that kernel compile under BFS will be faster than CFS. Verify his claim.

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

Part 5: HZ and Jiffies

Reading assignment

Tasks

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

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

  2. What is the currently configured HZ in your system?
  3. What is Jiffies? What is the relationship between jiffies and jiffies_64? Again, be brief.

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

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

Part 6: Freezer built, but not yet turned on

Reading assignment

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

Part 6 tasks and requirements

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

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

Part 9: CFS v. Freezer

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!


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.


Last updated: 2017–03–26