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 16th of Nov., 8am, CET, to submit your report (pdf) and source code (tgz) by email (see at the end of this page to know about the report structure). 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.

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 10
   T2 12 2
   T3 5 3
   

   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. Energy Aware Scheduling [15 points]

In embedded systems, it's common to schedule running processes based on their expected energy consumption. This type of scheduling is especially prevalent in mobile phones. Please read the description of the Linux Energy Aware Scheduler thoroughly before answering the subsequent questions. You can also access the document here.

1. [1 point] What are the two primary objectives of the scheduling policy outlined in the provided document?


2. [4 points] Based on the example provided in the document, devise an algorithm that takes a set of processors, their respective energy models, the current tasks assigned to them, and a task to be scheduled (i.e., linked to a processor). This algorithm should determine the most optimal processor to execute the task. In your report, present this algorithm in pseudo-code and demonstrate its effectiveness with the provided example. You can refer to this document for help on writing pseudo-code.

Moving forward, you'll implement and test your algorithm.


3. [2 points] Begin by defining a file format to describe your algorithm's inputs. This format should allow your program to discern the set of tasks to be scheduled in a multi-processor system, inclusive of the processors' energy models. Tasks should be defined by their util_avg and arrival time (optional).


4. [4 points] Implement your Energy Aware Algorithm, which, of course, is based on the algorithm you've previously outlined.


5. [4 points] Validate your algorithm using at least three task and processor sets, chosen for their relevance in testing your implementation. Ensure your tests cover interesting scenarios, including sets of tasks and processors with distinct energy models.

VII. Format of the report

The files and directories of the archive you send me MUST be 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.


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

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

  • Each Makefile should have one target for each test:
  
  

  $ make eas
  $ 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.