CSE 422S: Studio 11

Real-Time Scheduling

In some distant arcade, a clock tower calls out six times and then stops. The young man slumps at his desk. He has come to the office at dawn, after another upheaval. His hair is uncombed and his trousers are too big. In his hand he holds twenty crumpled pages, his new theory of time ...

Alan Lightman—Einstein's Dreams, Prologue

Linux's real-time scheduling classes are for processes that require a great deal of control over how they execute, including their timing behavior. The real-time scheduling classes can be used to define programs that execute in very specific ways, including preempting other programs and even the operating system kernel.

In this studio, you will:

  1. Write programs that run under the SCHED_RR (and optionally SCHED_FIFO) real-time scheduler
  2. Use the kernel tracer to examine how this program runs

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 finished upload them along with the relevant source code to the appropriate spot on Canvas. If you work in a group with other people, only one of you should please upload the answers (and any other files requested) for the studio, and if you need to resubmit (e.g., if a studio were to be marked incomplete when we grade it) the same person who submitted the studio originally should please do that.

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. First, we'll need a program to run as a real-time workload. In the previous studio you created an infinite-loop program, which we'll modify to use here. One key issue is that (unlike a traditional workload) a real-time workload is capable of preempting the kernel itself, which can make it difficult to stop misbehaving programs, and the kernel may even panic if it cannot run. So, in general it's a very bad idea to create real-time programs with infinite loops, and in this studio we will instead use programs that are computationally intensive but will terminate.

    Copy your CPU-bound workload program from the previous studio into a new file, and modify the new program so that (1) rather than looping forever, it increments a loop index from zero to five hundred million (500,000,000) and (2) the body of the loop performs a simple one-line arithmetic calculation involving addition, multiplication, and assignment. This will provide a CPU bound task that's still computationally intensive but is guaranteed to finish.

    NOTE: Modern compilers are smart enough to optimize your loop away. Make sure to compile without any optimizations when you build your executable file for this exercise. With compiled with no optimization (e.g., simply running gcc -o big_loop big_loop.c), on the Raspberry Pi 3, the instructor's program runs for a little over seven seconds. When compiled with -O1 it runs for about a half second. For any higher optimization level (e.g., -O2 or above) the program runs in several milliseconds. Compile your new program on your Raspberry Pi, without any optimizations, and then use the time command to verify that your program runs for some number of seconds.

    As the answer to this exercise, please show the output from running your new program (compiled without any optimizations) within the time command.

  3. Now, use the trace-cmd command to record sched_switch events during an execution of your program on core 0. Recall that the syntax for this looks like the following example: "sudo trace-cmd record -e sched_switch ./big_loop 0". Note: Optionally, you can try this on other cores as well, to see to what extent running your program on different cores changes the set of processes that may preempt your program, but for the answers in this studio please use core 0.

    Make a copy of the trace.dat trace file that command generated (in the directory where you ran it), so you can inspect it later - the next time we run trace-cmd it will overwrite the current local trace.dat file.

    Then use Kernelshark to inspect the trace, and zoom in on specific portions of the trace (e.g., on CPU core 0 where you pinned the program) to examine how your program executes. As the answer to this exercise, please name three processes that interefered with the execution of your program on that core, and explain briefly how you know they did that based on the trace you examined.

  4. Please run the commands

    man 2 sched_setscheduler


    man 2 sched_get_priority_min


    man 2 sched_get_priority_max

    to see documentation for the data structure and functions needed for this exercise.

    Modify your workload program so that it takes a second command line argument (in addition to the first argument, which specifies on which core the program should run) that gives the real-time priority with which it should run (valid values for that argument are in the range from the value returned by sched_get inclusive).

    Also modify your program so that it uses the sched_param data structure and the sched_setscheduler() function to run under the SCHED_RR scheduling class with the real-time priority that was passed in the second command line argument.

    Be sure your program checks that valid command line parameters were passed (in particular, that the passed priority is in the range from the value returned by sched_get_priority_min(SCHED_RR) to value returned by sched_get_priority_max(SCHED_RR) inclusive), and also checks the return value from calling the sched_setscheduler() function, and that it prints out an appropriate error message (and returns a negative value) in the event of failure.

    Compile your program (without optimization) and run it both as root (using sudo) and not as root with different priority values ranging from 1 to 99. Find the largest number for which sched_setscheduler() succeeds when run as root, and the largest number for which sched_setscheduler() succeeds when run not as root, and report those values as the answer to this exercise.

  5. Then run your program on core 0 under trace-cmd with a real-time priority of 1, to generate a new trace, and inspect the resulting trace in Kernelshark. As the answer to this exercise please say whether any processes preempted your program (and if so which ones), and whether there are any meaningful differences in how these interruptions appear in this trace (kernelshark trace.dat), versus in your original (non-real-time) trace (kernelshark trace_original.dat).

  6. In kernelshark, filter your real-time trace to only show events from the processor that your program used. To do so, go to the Filter menu and select list CPUs, and then uncheck all but that CPU and then click on the Apply button. Do that for each of the CPUs, and then as the answer to this exercise please say how many sched_switch events were recorded on CPU core 0 where your program ran, and compare that number to the number of sched_switch events were recorded on each of the other CPU cores.

  7. Use the command ps -e -o cmd,rtprio to get a list of all processes on the system and their real-time priorities. A dash in the priority column means that this process does not have a real-time priority.

    As the answer to this exercise please (1) say what range of real-time priorities you see being used, (2) what processes have real-time priorities, and (3) speculate why they may need to be run with real-time priority.

  8. Run your program again on core 0 under trace-cmd (as root) with a real-time priority of 99. As the answer to this exercise, please say (1) how many sched_switch events occur on your program's processor, (2) whether your program is ever preempted, and if so (3) when and where is it preempted?

  9. We will now execute multiple real-time processes concurrently, but this is slightly trickier than you might think. For example, if you launch one real-time process, once it reaches a certain point in its execution it may be impossible to launch a second real-time process on that same processor until the first one finishes its work.

    Make a copy of your real-time workload program, and modify it so that it takes a third argument, which will be the number of real-time tasks to create (only accept values ranging from 1 to 10). Using this number, insert appropriate calls to the fork() function. It is essential that fork() is called AFTER you have set the program's real-time priority, but BEFORE you start executing the program's work loop.

    Compile and test your modified program, and when you are confident that it is working correctly, trace the execution of the program running three concurrent real-time workloads, and inspect the trace in Kernelshark. Recalling that you can set marker A with a left mouse click, and set marker B with shift + left mouse click, use markers to measure the length of a round-robin time-slice.

    As the answer to this exercise (1) report the length of the round-robin time-slice you saw, and (2) briefly describe the pattern of execution of the three processes that you saw in that trace.

  10. Things to turn in

    Optional Enrichment Exercises

  11. Linux contains another real-time scheduling class called SCHED_FIFO, under which tasks are allowed to run to completion or until they give up the processor with sched_yield(). Repeat the previous exercises that used the SCHED_RR scheduler with SCHED_FIFO instead, and as the answer to this exercise please describe what differences you saw in the scheduling behavior with SCHED_FIFO, versus what you saw with SCHED_RR.
  12. In real-time systems, tasks must often execute within a precise period of time. The task must complete by its deadline, or bad things (system failure, injury, even death) can occur. With Earliest Deadline First (EDF) scheduling, an operating system will run the task that has the earliest deadline.

    Linux implements EDF through the SCHED_DEADLINE policy. SCHED_DEADLINE was only available with the rt-preempt patch, until it was introduced to the mainline Linux kernel in version 3.14.

    Please run the command man 2 sched_setattr to see documentation for the data structure and function needed for the following remaining exercises. You may also want to read the Linux kernel documentation on deadline task scheduling, particularly the example in Appendix B.

    Make a copy of your program that executes multiple real-time processes, and modify it to use EDF scheduling instead.

    First, you may need to define the sched_attr data structure used by the sched_satattr system call, as it may not be defined in your user-space headers. Be sure to use the __u32 and __u64 data types for its members, which are defined in <linux/kernel.h>

    Next, create a local variable of this datatype in your main() function. Make sure that your program still compiles correctly. As the answer to this exercise, please show your definition for sched_attr.

  13. Assign attributes as appropriate to your sched_attr variable. Set the runtime of your jobs equal to the round-robin time-slice you measured earlier. Set the deadline and period equal to three times this number. Keep in mind that sched_runtime, sched_deadline, and sched_period are specified in nanoseconds.

    As the answer to this exercise, please show your code that sets these attributes.

  14. Now, instead of using sched_setscheduler, you will use the sched_setattr system call. Like with sched_attr, a wrapper function may not be available in your user-space headers. Instead, you can invoke the syscall directly. Like you did in the Linux System Calls studio, use the syscall macro, providing the appropriate arguments for the sched_attr syscall. The first argument should be __NR_sched_setattr.

    Compile your program, making sure there are no errors. As the answer to this exercise, please show your code that invokes the syscall macro.

  15. Once you are confident that your program is working correctly, trace the execution of the program running three concurrent real-time workloads, and inspect the trace in Kernelshark.

    As the answer to this exercise, briefly describe the pattern of execution of the three processes that you saw in that trace, and compare it to the earlier round-robin execution behavior.