freezer

Freezer

Submission

As with previous assignments, we will 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.

NOTE: If at all possible, please try to submit using x86. If one of your group members owns an x86 machine, test on that machine prior to submitting, and do not commit a .armpls file. This will make grading much easier for us.

For students on arm64 computers (e.g. M1/M2 machines): if you want your submission to be built/tested for ARM, you must create and submit a file called .armpls in the top-level directory of your repo; feel free to use the following one-liner:

cd "$(git rev-parse --show-toplevel)" && touch .armpls && git add -f .armpls && git commit .armpls -m "ARM pls"

You should do this first so that this file is present in all parts.

Code Style

There is a script in the skeleton code named run_checkpatch.sh. It is a wrapper over linux/scripts/checkpatch.pl, which is a Perl script that comes with the Linux kernel that checks if your code conforms to the kernel coding style.

Execute run_checkpatch.sh to see if your code conforms to the kernel style – it’ll let you know what changes you should make. You must make these changes before pushing a tag. Passing run_checkpatch.sh with no warnings and no errors is required for this assignment.

Part 1: Priorities in CFS

Tasks

  1. First, read the OSTEP and LKD reading assignments on scheduling and the Linux CFS scheduler.

  2. 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 or htop command.

    Here is a part of the screen of a sample top session:

    top - 15:25:39 up 30 min,  3 users,  load average: 9.59, 6.08, 2.58
    Tasks: 220 total,  11 running, 209 sleeping,   0 stopped,   0 zombie
    %Cpu0  :   0.0/0.7     1[                                           ]
    %Cpu1  :   0.3/0.0     0[                                           ]
    %Cpu2  :   0.0/0.0     0[                                           ]
    %Cpu3  : 100.0/0.0   100[|||||||||||||||||||||||||||||||||||||||||||]
    %Cpu4  :   0.3/0.3     1[                                           ]
    %Cpu5  :   0.0/0.0     0[                                           ]
    %Cpu6  :   0.0/0.3     0[                                           ]
    %Cpu7  :   0.0/0.0     0[                                           ]
    MiB Mem : 20.2/3895.9   [||||||||||||||||                           ]
    MiB Swap:  0.0/975.0    [                                           ]
    
      PID      %CPU     COMMAND
    
     1282       13.3                                    `- myprogram
     1283       13.3                                    `- myprogram
     1284       13.3                                    `- myprogram
     1285       13.3                                    `- myprogram
     1286       13.3                                    `- myprogram
    
     1287       6.6                                     `- myprogram
     1288       6.6                                     `- myprogram
     1289       6.6                                     `- myprogram
     1290       6.6                                     `- myprogram
     1291       6.6                                     `- myprogram
    

    It shows the 10 processes of myprogram, 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.

  3. 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 - 15:28:32 up 33 min,  3 users,  load average: 10.33, 7.92, 3.90
    Tasks: 219 total,  13 running, 206 sleeping,   0 stopped,   0 zombie
    %Cpu0  :   0.0/2.9     3[||                                         ] 
    %Cpu1  :   0.0/0.0     0[                                           ]
    %Cpu2  :   0.0/0.0     0[                                           ]
    %Cpu3  : 100.0/0.0   100[|||||||||||||||||||||||||||||||||||||||||||]
    %Cpu4  :   0.0/0.0     0[                                           ]
    %Cpu5  :   0.0/0.0     0[                                           ]
    %Cpu6  :   0.3/0.0     0[                                           ]
    %Cpu7  :   0.0/0.0     0[                                           ]
    MiB Mem : 21.2/3895.9   [||||||||||||||||                           ]
    MiB Swap:  0.0/975.0    [                                           ]
    
      PID      %CPU     COMMAND
    
     1282       0.7                                    `- myprogram
     1283       0.7                                    `- myprogram
     1284       0.7                                    `- myprogram
     1285       0.7                                    `- myprogram
     1286       0.7                                    `- myprogram
    
     1287       0.3                                    `- myprogram
     1288       0.3                                    `- myprogram
     1289       0.3                                    `- myprogram
     1290       0.3                                    `- myprogram
     1291       0.3                                    `- myprogram
    
     1297      95.0                                    `- myprogram
    

Deliverables

  1. Describe in your written_answers.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: HZ and Jiffies

Reading assignment

Deliverables

Please write the answers to the following questions in your written_answers.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. No need to submit your code, but please describe what you did.
  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 written_answers.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

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

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

Freezer Overview

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

Parts 3-6 are structured to guide you in developing a new scheduler. Each part represents a milestone towards a working scheduler implementation. This forces you to develop incrementally. This also allows us to award you partial credit if you cannot get the whole scheduler working at the end.

In part 3, 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 4, 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 5, 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).

In part 6, you will add idle load balancing to Freezer. This allows processes to make better use of available CPUs.

Part 3: Freezer, unplugged

Reading assignment

Tasks

Deliverables

Submission

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

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

Part 4: 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 hw6p4handin tag with the following:

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

Part 5: 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 (not counting the four parent processes that forked them) 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    3  0.0  0     2 root     [kthreadd]
  7 #7    0  0.0  0     3 root      \_ [rcu_gp]
  7 #7    0  0.0  0     4 root      \_ [rcu_par_gp]
  7 #7    0  0.0  0     6 root      \_ [kworker/0:0H-kblockd]
  7 #7    1  0.0  0     7 root      \_ [kworker/u8:0-events_unbound]
  7 #7    0  0.0  0     8 root      \_ [mm_percpu_wq]
  7 #7    0  0.0  0     9 root      \_ [ksoftirqd/0]
  7 #7    2  0.0  0    10 root      \_ [rcu_sched]
  7 #7    0  0.0  0    11 root      \_ [rcu_bh]
  1 FF    0  0.0  0    12 root      \_ [migration/0]
  7 #7    0  0.0  0    13 root      \_ [kworker/0:1-events]
  7 #7    0  0.0  0    14 root      \_ [cpuhp/0]
  7 #7    1  0.0  0    15 root      \_ [cpuhp/1]
  1 FF    1  0.0  0    16 root      \_ [migration/1]

                                  ...

  7 #7    3  0.1  0     1 root     /sbin/init
  7 #7    3  0.0  0   221 root     /lib/systemd/systemd-journald
  7 #7    3  0.0  0   241 root     /lib/systemd/systemd-udevd
  7 #7    1  0.0  0   454 root     /usr/sbin/ModemManager --filter-policy=strict
  7 #7    2  0.0  0   455 root     /usr/sbin/cron -f
  7 #7    0  0.0  0   456 avahi    avahi-daemon: running [porygon.local]
  7 #7    2  0.0  0   509 avahi     \_ avahi-daemon: chroot helper

                                  ...
    
  7 #7    3  0.0  0   465 root     /lib/systemd/systemd-logind
  7 #7    1  0.0  0   510 root     /usr/lib/policykit-1/polkitd --no-debug
  7 #7    1  0.0  0   511 root     /usr/sbin/alsactl -E HOME=/run/alsa -s -n 19 -c rdaemon
  7 #7    0  0.0  0   535 root     /usr/sbin/sshd -D
  7 #7    0  0.0  0   761 root      \_ sshd: hans [priv]
  7 #7    2  0.0  0   779 hans          \_ sshd: hans@pts/0
  7 #7    0  0.0  0   780 hans              \_ -bash
  7 #7    1  0.0  0   808 hans                  \_ tmux
        
                                  ...

  7 #7    2  0.0  0   810 hans     tmux
  7 #7    2  0.0  0   811 hans      \_ -bash
  7 #7    0  0.0  0  1001 hans      |   \_ ps -e --forest -o sched,policy,psr,pcpu,c,pid,user,cmd
  7 #7    0  0.0  0   822 hans      \_ -bash
  7 #7    0  0.0  0   970 hans          \_ ./myprogram
  7 #7    0 19.9 19   972 hans          |   \_ ./myprogram
  7 #7    0 19.8 19   973 hans          |   \_ ./myprogram
  7 #7    0 19.8 19   974 hans          |   \_ ./myprogram
  7 #7    0 19.9 19   975 hans          |   \_ ./myprogram
  7 #7    0 19.9 19   976 hans          |   \_ ./myprogram
  7 #7    1  0.0  0   977 hans          \_ ./myprogram
  7 #7    1 19.8 19   979 hans          |   \_ ./myprogram
  7 #7    1 19.8 19   980 hans          |   \_ ./myprogram
  7 #7    1 19.9 19   981 hans          |   \_ ./myprogram
  7 #7    1 19.9 19   982 hans          |   \_ ./myprogram
  7 #7    1 19.8 19   983 hans          |   \_ ./myprogram
  7 #7    2  0.0  0   985 hans          \_ ./myprogram
  7 #7    2 20.0 20   987 hans          |   \_ ./myprogram
  7 #7    2 20.0 20   988 hans          |   \_ ./myprogram
  7 #7    2 19.9 19   989 hans          |   \_ ./myprogram
  7 #7    2 19.8 19   990 hans          |   \_ ./myprogram
  7 #7    2 19.8 19   991 hans          |   \_ ./myprogram
  7 #7    3  0.0  0   992 hans          \_ ./myprogram
  7 #7    3 19.9 19   994 hans              \_ ./myprogram
  7 #7    3 20.0 20   995 hans              \_ ./myprogram
  7 #7    3 19.9 19   996 hans              \_ ./myprogram
  7 #7    3 19.9 19   997 hans              \_ ./myprogram
  7 #7    3 19.9 19   998 hans              \_ ./myprogram

Tips

Deliverables

Submission

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

Part 6: Freezer Load Balancing

Finally, let’s add idle load balancing to Freezer. If a CPU is about to start running the idle_task because there are no other tasks running on it, try to move a task from another CPU to the current CPU. This helps us utilize as many CPUs as possible at all times, speeding up performance.

Our load balancing policy is as follows:

Tips

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: CFS v. Freezer (optional)

Compare Freezer with CFS.

Tasks

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

  2. If your Freezer is rock solid, you may perform a shoot-out between CFS and Freezer by timing kernel builds in both your fallback and your Freezer 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. Note that this will delete your .config as well.

    • If you’ve optimized your kernel builds with ccache, you should disable that for this experiment.

    • Make sure to compile with make -j$(nproc).

    • You may find the time utility handy.

  3. Some other activities you might like to consider:

    • Watching hi-res video

    • Highly interactive tasks

    • CPU-intensive tasks

Submission (optional)

If you’d like 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

Good luck!


Acknowledgments

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.

Jonas Guan, TA in Spring 2019, updated the code for the 4.9.153 kernel.

Dave Dirnfeld and Hans Montero, TAs in Spring 2020, updated the assignment for the 4.19.50 kernel.

Kent Hall, John Hui, Xijiao Li, Hans Montero, Akhil Ravipati, Maÿlis Whetsel, and Tal Zussman, TAs in Fall 2021, updated the assignment for the 5.10.57 kernel.

Andy Cheng, Helen Chu, Phoebe Lu, Cynthia Zhang, and Tal Zussman, TAs in Spring 2023, updated the assignment for the 5.10.158 kernel and implemented idle load balancing.


Last updated: 2023-03-22