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:
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.
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.
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.
man 2 sched_setschedulerman 2 sched_get_priority_minman 2 sched_get_priority_maxModify 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.
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).
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.
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.
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?
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.
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.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.
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.
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.
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.