Scheduling

This session is dedicated to the study of process scheduling in Operating Systems.



For this session, you will need to log into a PC running Linux. If you are at Eurecom, simply log on a PC of rooms 52 or 53. You may also use your own PC, but I should be able to compile and execute your work on Eurecom PCs with no error.

I. Concepts

1. Open the slides Scheduling


2. Watch the video on scheduling, part 1.


3. How would you define an interactive process?
(Help me!) An interactive process is a process interacting with the user of a computer, for instance waiting for an input such as a key to be pressed or the mouse to be clicked at a given position.



4. Explain why real-time processes need to be scheduled differently from interactive processes?

II. Scheduling policies

1. Open the slides Scheduling


2. Watch the video on scheduling, part 2. Don't forget to pause the video and to make the exercises.


3. FCFS. What is the AWT for queues "p2, p3, p1" and for "p3, p2, p1"?
(Help me!) p2, p3, p1: (0+3+6)/3 = 3
p3, p2, p1. Same.



4. SJF. Give the AWTs for example #1, slide SJF. Also, find a better scheduling for example 2.
(Help me!) FCFS: (0+8+12+16)/4 = 9
SJF: (0+8+12+16)/4 = 9
Better: p2/p3/p4/p5/p1. AWT=13/5
(But maybe you can find an even better one?)



5. Round-Robin. What happens if the quantum of time is very short?
(Help me!) With a short quantum, the OS schedules processes much more frequently, which induces a lot of overhead



6. Round-Robin. What happens if the quantum of time is very long?
(Help me!) With a long quantum, the OS gives to processes a very long execution time, leading to less responsive systems, i.e.,. to a batch system.



7. Round-Robin AWT. Give the AWT for the set p1/p2/p3
(Help me!) AWT= (6+4+7)/3 = 5.66
P1 waits for 6 (between 4 and 10), p2 waits for 4, and p3 for 7.

III. Advanced scheduling policies

1. Open the slides Scheduling


2. Watch the video on scheduling, part 3.


3. What is/are the drawback(s) of using a single ready-queue accessed by only one processor?
(Help me!) The processor managing the ready queue can become a scheduling bottleneck. As the number of cores and scheduling events increases, scheduling decisions are serialized through one processor, which can increase dispatch latency and leave execution cores temporarily idle.

IV. Scheduling in Windows and Linux

1. Open the slides Scheduling


2. Watch the video on scheduling, part 4.

Now, you will work on several exercises.

V. Scheduling simulator: experimenting with FCFS (First-Come, First-Served)

Understanding the scheduling code of, e.g., the Linux kernel is a bit complex, and that does not help much in understanding scheduling policies.

1. I first provide a scheduling policy simulator that implements one scheduling policy (FCFS). First, uncompress the archive:

$ gunzip labOnScheduling.tar.gz
$ tar -xof labOnScheduling.tar

You may also do this in one command:

$ tar -xzf labOnScheduling.tar.gz

Then, compile the scheduling simulator:

$ cd labOnScheduling
$ make

Essentially, the simulator begins by parsing a tasks file supplied as input (you might want to briefly review the Makefile). An example task file, named tasks, is included in the archive. This file specifies the set of tasks to be scheduled along with their attributes. Its structure is as follows: the first column denotes the task name, the second column indicates the number of computation cycles required by the task (i.e., its computation time), and the final column marks the task's arrival time. Examine the contents of the tasks file for clarity:


$ cat tasks
T1 10 0
T2 12 2
T3 5 2
T4 5 29



2. You are now ready to execute the scheduling policies simulator:

   $ make run
   

   The execution does not complete, and the simulator produces an error (or you might encounter a segmentation fault). This memory error arises during the parsing of the tasks file. Study the code to pinpoint the issue in taskSchedule.c. The GNU Project Debugger, gdb, could assist you in identifying the problem. To acquire more detailed insights while debugging with gdb, first compile your program using the "-g" option. To implement this, modify the Makefile and append "-g" to the compilation command. You may also wish to add two other flags: "-Wall" and "-Wextra" (Figure out their interest and differences). Subsequently, recompile the program.
   

   $ make
   

   Then, you can start gdb on your program as follows:

   $ gdb schedule
   

   Then, type "run" to execute the program:

   (gdb) run tasks
   

   or

   (gdb) run tasks -verbose
   

   The program should stop and tell you which instruction caused the memory error. Once you have found which instruction triggered the fault, have a look at the task structure (struct task ...) and try to understand what were the value passed as argument to the faulty function. Correct the problem, recompile the program, and re-run it:
   

   $ make
   $ make run
   

   Once the problem has been resolved, you should see a trace explaining how the tasks were sequenced by the simulator scheduler. Check that the trace is correct. you can also obtain a more complete trace by starting the program with the -verbose option:

   $ make runverbose
   

   
   
   
3. Now, let's try a different set of tasks. Use another tasks file "tasks2" and put the following content:

   T1 11 11
   T2 12 2
   T3 5 4
   

   Then, start schedule with this new task file:

   ./schedule tasks2
   

   Now, let's verify that your implementation is correct for this set of tasks, and for this scheduler. file represents the expected output of your work. To compare your output with this reference model, we are going to compare them using the diff command. The main idea is to do as follows:

   $ ./schedule tasks2 > mytest2
   $ diff mytest2 test2
   

   If the output is empty, it means that the two files are equal. Note that you can also execute the two previous commands in one line, thus avoiding to create an intermediate file:

   $ diff <(./schedule tasks2) test2
   

   The trace you observe should not be the right one, i.e., the simulator does not implement the FCFS policy correctly: identify the problem, correct it and test!
   

VI. Experimenting with a Real-Time scheduler: RMS

Scheduling real-time tasks consists in taking into account the time constraints of these tasks: real-time tasks are usually given a deadline value, i.e., a date at which they must have completed their execution. For instance, if a task has a deadline of 10, and its release time is 5, then it must have finished its execution before time 15.

This exercise asks you to implement one of the most well-known real-time scheduler: RMS (Rate-Monotonic Scheduling). We assume a set of tasks that are scheduled with RMS scheduler. Also, tasks are all ready to execute at time 0 (arrival time), and they are all periodic, with their period equal to their deadline. Do understand the basics of this scheduling algorithm. Example 1 provided in the Wikipedia page will surely help you.

1. Define a file format for describing tasks. This file format should at least define the task name, its WCET, and its period.


2. Implement RMS algorithm and test. The simulation should run for one hyperperiod.


3. The Liu-Layland utilization bound is sufficient but not necessary. Explain what that means and decide how your simulator will determine whether a task set is schedulable. Make sure to have a special warning when the system is not schedulable, i.e., when a task is sure to miss its deadline. Do not start the schedule in that case, simply return and give an explicit error message.


4. Prove with at least 3 sets of tasks that your algorithm works as expected. Define the test so as to cover interesting situations. Do explain why these different tests are relevant.


5. Now, assume that you have a 2-core processor. Propose a two-core RMS approach, and propose an implementation. Again, provide tests to prove that your approach works according to the policy you have defined. Your rma.c file should now take as input the number of cores (1, 2, or even more if you wish to generalize to n cores. More than 2 cores is considered as a bonus).