Operating System (CS2701)
Realtime Scheduling
Dr. Rourab Paul
Computer Science Department, SNU University, Chennai
Operating System
Realtime Scheduling
Operating System
2
Unlike general-purpose scheduling (which focuses on fairness or maximizing throughput), real-time scheduling ensures tasks are executed within specific deadlines.
Types of Real-Time Systems
Windows has 32 different priority levels. The highest levels—priority values 16 to 31—are reserved for real-time processes. Solaris and Linux have similar prioritization schemes.
Realtime Scheduling For Periodic Task
Operating System
3
The processes are considered periodic. That is, they require the CPU at constant intervals (periods). Once a periodic process has acquired the CPU, it has a fixed processing time t, a deadline d by which it must be serviced by the CPU, and a period p. The relationship of the processing time, the deadline, and the period can be expressed as 0 ≤ t ≤ d ≤ p. The rate of a periodic task is 1∕p.
Admission Control
Operating System
4
Process may have to announce its deadline requirements to the scheduler. Then, using a technique known as an admission-control algorithm, the scheduler does one of two things. It either admits the process, guaranteeing that the process will complete on time, or rejects the request as impossible if it cannot guarantee that the task will be serviced by its deadline
Rate Monotonic Scheduling (RMS)
Operating System
5
The rate-monotonic scheduling algorithm schedules periodic tasks using a static priority policy with preemption. If a lower-priority process is running and a higher-priority process becomes available to run, it will preempt the lower-priority process.
Upon entering the system, each periodic task is assigned a priority inversely based on its period.
Rate Monotonic Scheduling (RMS)
Operating System
6
We have two processes, P1 and P2. The periods for P1 and P2 are 50 and 100, respectively: that is, p1 = 50 and p2 = 100. The processing times are t1 = 20 for P1 and t2 = 35 for P2. The deadline for each process requires that it complete its CPU burst by the start of its next period.
Rate Monotonic Scheduling (RMS)
Operating System
7
The CPU utilization of a process Pi as the ratio of its burst to its period—ti ∕pi— the CPU utilization of P1 is 20∕50 = 0.40 and that of P2 is 35∕100 = 0.35, for a total CPU utilization of 75 percent.
Rate Monotonic Scheduling (RMS)
Operating System
8
The CPU utilization of a process Pi as the ratio of its burst to its period—ti ∕pi— the CPU utilization of P1 is 20∕50 = 0.40 and that of P2 is 35∕100 = 0.35, for a total CPU utilization of 75 percent.
RMS P2>P1
Operating System
9
Suppose we assign P2 a higher priority than P1.
RMS P1>P2
Operating System
10
RMS, in which we assign P1 a higher priority than P2 because the period of P1 is shorter than that of P2.
RMS
Operating System
11
RMS, in which we assign P1 a higher priority than P2 because the period of P1 is shorter than that of P2.
RMS Utilization Bound
Operating System
12
Despite being optimal, then, rate-monotonic scheduling has a limitation: CPU utilization is bounded, and it is not always possible to maximize CPU resources fully. The worst-case CPU utilization for scheduling N processes is N(2^{1∕N} − 1).
For 1 task: 100% utilization possible.
For 2 tasks: 83% utilization.
For N→∞ tasks: ~69% utilization bound.
If total utilization ≤ 83%, RMS always guarantees a feasible schedule (for any periods of the 2 tasks).
If total utilization > 83%, RMS might still succeed, but schedulability is no longer guaranteed.
RMS
Operating System
13
Assume that process P1 has a period of p1 = 50 and a CPU burst of t1 = 25. For P2, the corresponding values are p2 = 80 and t2 = 35. Rate-monotonic scheduling would assign process P1 a higher priority, as it has the shorter period. The total CPU utilization of the two processes is (25∕50) + (35∕80) = 0.94, and it therefore seems logical that the two processes could be scheduled and still leave the CPU with 6 percent available time.
RMS
Operating System
14
Despite being optimal, then, rate-monotonic scheduling has a limitation: CPU utilization is bounded, and it is not always possible to maximize CPU resources fully.
Earliest-Deadline-First Scheduling(EDF)
Operating System
15
Earliest-Deadline-First Scheduling(EDF)
Operating System
16
To illustrate EDF scheduling, we again schedule the processes shown in Figure 5.23, which failed to meet deadline requirements under rate-monotonic scheduling. Recall that P1 has values of p1 = 50 and t1 = 25 and that P2 has values of p2 = 80 and t2 = 35
Proportional Share Scheduling
It’s a fair scheduling algorithm where the CPU is divided among tasks in proportion to assigned shares (weights).
If Task A has twice the share of Task B, it should get twice the CPU time in the long run.
CPU share =
Scheduler interleaves execution such that, over time, each process gets its fair proportion.
17
Proportional Share Scheduling
When a process arrives in the system, the OS assigns it a weight (or shares) based on:
For example:
Total = 40 shares.
18
So:
Thank You
Operating System
19