Operating Systems of Mobile Devices (OSMZ)

Week III. (22.2.-26.2.2021)

This week we will have look at process schedulers and later into their implementations in online tasks.

The process scheduler decides which of the pending and ready to run process will be assigned to a processor and the process will run. The selection depends on the priorities of individual processes and the algorithm by which we make the decision. Start with an overview of the most well-known algorithms.

Non-preemptive Scheduling is a CPU scheduling technique the process takes the resource (CPU time) and holds it till the process gets terminated or is pushed to the waiting state. No process is interrupted until it is completed, and after that processor switches to another process. This type of scheduler was used, for example, in Windows 3.1 and nowadays, apart from very special applications, it is not usually used. Preemptive Scheduling is a CPU scheduling technique that works by dividing time slots of CPU to a given process. The time slot given might be able to complete the whole process or might not be able to it. When the burst time of the process is greater than CPU cycle, it is placed back into the ready queue and will execute in the next chance. Switching is triggered by an interrupt from the system timer (PIT or HPET). A summary of the differences between these two approaches can be found here.

In the second part of our practical labs, we will implement the Round-Robin and Lottery Scheduling planning algorithms.

Round-Robin (RR) is one of the oldest and most often implemented planning algorithms. A running process is allocated a certain amount of time for which the process can be processed on the processor. After this time has elapsed (solved by a timer), the process is stopped and another is started instead. The algorithm assumes constant priority for all processes it plans.

Lottery Scheduling (LS) is a type of probabilistic scheduling algorithm. Each process is assigned a number of tickets, and the scheduler draws a random ticket each time it switches. Based on which ticket it selects the next process is allocated for a given amount of time. As soon as the quantum of this process expires, the scheduler will draw again. The distribution of tickets does not have to be uniform; processes with a larger number of tickets have a relatively higher chance of selection and thus a higher priority. This scheduling algorithm inherently solves the problem of starvation. Giving each process at least one ticket guarantees that it has a non-zero probability of being selected.

PRESENTATION

LITERATURE

Andrew S. Tanenbaum - Modern operating systems. 4th edition:

  • chap. 2.4 Process Schedulers (pp. 149 - 167)
  • chap. 8.1.4 Scheduling on Multiprocessor Systems (pp. 539 - 545)
  • chap. 10.3.4 Scheduling in Linux (pp. 746 - 750)

ADDITIONAL READINGS

Simulator of various planning algorithms. Article on the process scheduler design for Mars 2020 mission. Summary of planning algorithms and similar.

QUESTIONS

After reading the above texts, you should be able to answer following questions from the topics for the exam, specifically:

  • Explain the concept of multitasking, preemptive and non-preemptive planning.
  • What is the purpose of the process scheduler, what are its expected properties / strategies.
  • Briefly explain the Round-Robin (RR) planning algorithm, advantages / disadvantages.
  • Briefly explain the advantages / disadvantages of the Lottery Scheduling (LS) algorithm.