Scheduling

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

The last part of this session is GRADED as indicated below. You have until the 21th of Oct., 8am, CET, to submit your work. Send me by email your work as only one file (see at the end of this page to know about the format of the file you should send me).
Late labs, with no justification (a valid justification is for instance a medical certificate) will get a zero.
Also, do respect the file structure as explained at the end of this page. Labs not respecting the correct format will not be considered.

The grade takes into account your report and the code. Your report should typically explain the decisions you have taken. A long report does not necessarily gets more points: a good report is a report giving answers in a concise way. Do provide answers only for questions with a "GRADED" indication.

The code must be commented whenever it is not self-explicit. Also, your code should be efficient both in terms of runtime and memory space. Also, do provide a Makefile with your code, and all the necessary test files so that I can test your code. Last but not least, your report and code should be your personal work: any attempt at cheating will result in a zero grade (EURECOM regulations).

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.
(Help me!) FCFS: (0+8+12+16)/4 = 9
SJF: (0+ 4+8+12)/4 = 6
Better: p2/p3/p4/p5/p1. AWT=9/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!) I see one main drawback: starvation! Imagine there is an important number of short processes executing in this system. The only processor (or core) handling this queue will have to handle many and frequent scheduling requests, thus leading cores to wait for having to execute a process.

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. Some of the questions or exercises are GRADED. You should provide an answer only for these 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 (often referred to as the "capacity"), 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. 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. GRADED question, [5 points]. 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: RMA (GRADED [15 points])

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: RMA (Rate-Monotonic Scheduling). We assume a set of tasks that are scheduled with a non-preemptive RMA 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 algorithm. Example 1 provided in the Wikipedia page will surely help you.

1. Define a file format for describing tasks. [1 point]


2. Implement a non-preemptive RMA algorithm and test. [5 points]


3. 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. [1 point]


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. [2 points]


5. Now, assume that you have a 2-core processor. Propose a two-core RMA 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). [6 points]

VII. Format of the report

The files and directories of the archive you send me MUST be in tgz format, and structured as follows. Any other code structuring will be ignored, apart if explained. Any other compression format other than tgz are also ignored

• A report in pdf shall answer to graded questions only. Name your report "report_lastname.pdf". The report shall explain your implementation choices when relevant. Again, do not answer to the non-graded questions. The report is part of the tgz (see the tree structure below). DO NOT PUT your executable files in the archive: I will generate the executable files using the provided Makefile.


• Use one directory for FCFS (called fcfs) and one for energy-aware scheduling (eas).
  • The tree of files should look like this:
  
  

  $ tree
  .
  |-- fcfs
  |   |-- Makefile
  |   |-- README
  |   |-- fcfs.c
  |   |-- test1
  |   |-- test2
  |   `-- test3
  |-- rma
  |   |-- Makefile
  |   |-- README
  |   |-- rma.c
  |   |-- test1
  |   `-- test2
  `-- report_lastname.pdf
  

  • Each Makefile should have one target for each test:
  
  

  $ make rma
  $ make test
  running test1
  ...
  running test2
  ...
  $ make test1
  running test1
  ...
  $ make test2
  ...
  

  • test1, test2, etc. are directories containing what is necessary to run the test: tasks file, expected result, etc. Obviously, you can add more tests in the tree structure.