CSE 422S: Studio 19

Completely Fair Scheduler (CFS)


Hobbits give presents to other people on their own birthdays. Not very expensive ones, as a rule, but it was not a bad system. Actually in Hobbiton and Bywater every day in the year it was somebody's birthday, so that every hobbit in those parts had a fair chance of at least one present at least once a week.

The Fellowship of the Ring, Book 1, Chapter 1

Linux's CFS strives to be completely fair, meaning that all processes should recieve an appropriately weighted proportion of the processor time. In particular, if there are a total of N processes in the system, then (if they have the same nice values) all processes will ideally recieve exactly 1/Nth of the processor time. In this studio we will explore the CFS from user space.

In this studio, you will:

  1. Create different workloads to influence the scheduler
  2. Analyze scheduling behavior from userspace

Please complete the required exercises below, as well as any optional enrichment exercises that you wish to complete. We encourage you to please work in groups of 2 or 3 people on each studio (and the groups are allowed to change from studio to studio) though if you would prefer to complete any studio by yourself that is allowed.

As you work through these exercises, please record your answers, and when you finish them each and every person who worked on them should please log into Canvas, select this course in this semester, and then upload a file containing them and also upload any other files the assignment asks for, and submit those files for this studio assignment (there should be a separate submission from each person who worked together on them).

Make sure that the name of each person who worked on these exercises is listed in the first answer, and make sure you number each of your responses so it is easy to match your responses with each exercise.


Required Exercises

  1. As the answer to the first exercise, list the names of the people who worked together on this studio.

  2. Before we begin we will disable a particular scheduling heuristic (which may improve responsiveness of interactive systems, but can adversely impact performance of high-workload servers, etc.), by changing the value of the file /proc/sys/kernel/sched_autogroup_enabled from 1 to 0 on your Raspberry Pi. To do that, first log into your Raspberry Pi and obtain a root terminal (sudo bash) in order to have permission to modify the value.

    Show the current value of that file using the cat command

    cat /proc/sys/kernel/sched_autogroup_enabled

    then modify the file's value

    echo 0 > /proc/sys/kernel/sched_autogroup_enabled

    and then show the file's new value

    cat /proc/sys/kernel/sched_autogroup_enabled

    and then exit the root terminal. As the answer to this exercise please show the terminal output with the previous and new values of that file.

  3. Now we will create a CPU-bound workload. The simplest CPU-bound program is a while(1) loop, but we want a little control over where this task executes. To do this, we will use Linux's processor affinities.

    For this exercise, write a infinite-loop program that takes a single integer argument from the command line, which gives the processor that the program should execute upon. In order to control where your process is allowed to run, use the function sched_setaffinity(). You will need to specify the set of allowable CPUs with a variable of type cpu_set_t. In order to manipulate this data type you should use the functions documented in man 3 CPU_SET. This is a nonstandard extension, so your program will need to #define _GNU_SOURCE before including sched.h.

    Hint: Ensure that #define _GNU_SOURCE is included before any other header files that you include, as well.

    Hint: Ensure that you include sched.h rather than linux/sched.h since this is user-space code.

    Hint: make sure to use CPU_ZERO to initialize your cpu_set_t variable, before setting the processor on which you wish it to run.

    Use top and trace-cmd (or even better, htop and kernelshark) to verify that your program runs continuously on a processor of your choosing, and as the answer to this exercise please show the output that confirms this is working correctly.

  4. Your Raspberry Pi has four processors, and the Linux convention is to number them starting with zero. Using four separate terminal windows, create an infinite loop task on each of processors 0, 1, 2, and 3 to fully occupy your system. We will call these tasks the background workload.

    While those are running, run a few tasks of your own choosing (text editing, internet browsing, etc.), and notice how well the system responds. Then use Ctrl-C in each of the background workload windows to stop the task in each one, and see how well the system runs without the background workload running.

    As the answer to this question, describe briefly how well the system responded when the background tasks were running, versus when they were not.

  5. Now we'll use the dense_mm program from previous studios to examine the behavior of CPU-bound tasks on a heavily loaded system. First, use the command time ./dense_mm 300 to get a rough measure of program execution time on a quiet system. Now, restart the background tasks and run the same command again.

    As the answer to this exercise, copy and paste the output from each run of time ./dense_mm 300.

  6. Compare the real and user timings. As the answer to this exercise, answer the following questions: what does the previous exercise tell you about the way that two CPU-bound tasks share a processors under the default Linux scheduler (CFS)? What do you predict will happen to the real and user time of dense_mm 300 if you were to increase the number of background tasks that were competing with it?

  7. The CFS scheduler doesn't have a direct notion of timeslice or priority, but Linux's nice priorities can influence the proportion of time a task recieves. Run the command time sudo nice -n -20 ./dense_mm 300. As the answer to this exercise, say what proportion of time (user divided by real) the task recieved.

  8. Repeat the previous exercise for nice priorities -10, -5, 0, 5, 10, and 19 (this last one may take several minutes to finish). Compute their runtime proportions, and list those as the answer to this exercise.

  9. Finally, you will create new background tasks so that each processor contains two infinite loop tasks, in order to test your prediction from the previous exercise.

    The following tips may be helpful, so you don't have to deal with myriad terminal windows. You can detach a command from the terminal by executing it with an ampersand (&) at the end. Also, you can terminate any task using its PID (which you can get from top or htop) via the kill command. For example, if a task's PID was 2424 you could use kill -9 2424 to terminate that task.

    Once you've set up the competing workloads, execute the command time ./dense_mm 300 and as the answer to this exercise show the results and explain briefly whether or not they support your prediction earlier about what will happen to the real and user time of dense_mm 300 if you were to increase the number of background tasks, and why they do or do not.

  10. Optional Enrichment Exercises

  11. Plot the data from the second-to-last exercise on a graph, and as the answer to this exercise describe briefly the relationship between the nice values and the runtime proportions you observed (i.e., what does the proportion look like as a function of the nice value that was used?).

  12. Repeat the last required exercise increasing the number of competing infinite loop tasks on each core from 2 to 3 to 4, etc. and as the answer to this exercise describe (and if you'd like to, plot on a graph) what happens to the real and user time of dense_mm 300 as you do that.

Things to turn in


Page updated Sunday August 9, 2020 by Chris Gill