FOR FREE MATERIALS

Rate-Monotonic Scheduling

The rate-monotonic scheduling algorithm schedules periodic processes using a static priority policy with preemption. 

Here each periodic process is assigned a priority based on its period. Shorter period has higher priority and longer period processes have lower priority.

If a lower-priority process is running and a higher-priority process becomes available to run, it will preempt the lower-priority process. 

The logic behind this policy is to assign a higher priority to tasks that require the CPU more often.

Furthermore, rate-monotonic scheduling assumes that every time a process acquires same duration of CPU burst. 

Period: Processes always occur at regular intervals of time which is called period.

Deadline: The time by which operation of the process must complete.

Execution time: Time required to execute the process i.e. CPU time. 

Now clear the concepts better way by an example.

Example 1: (Rate-Monotonic Scheduling)

In this example1, the deadline is not mentioned so we can assume here period and the deadline is the same.

Now hyper period is either given the question or we can calculate by LCM of periods of all process.

So, here hyper period is LCM (20, 5, 10) = 20.

Periodic Task Timing Diagram:   

As we know the processes are scheduled as per priority i.e. shorter period has higher priority and longer period processes have lower priority

As per the question, P2 has the lowest period than P3 and surely P1 has the highest period. So, processes are scheduled as per priority as follow:

P2 → P3 → P1

Periodic Task Timing Diagram: 

a) Initially at time unit 0, all processes are ready to execute, but as per the smallest period of P2. We assign P2 first for 2 units. 

b) Now at time unit 2, only P1 and P3 are ready processes and P3 has the lowest period compare to P1, so here P3 has been assigned for 2 units. 

c) Now at time unit 4 only ready process is P1. So, we assign P1 for 1 unit (though the execution time of P1 is 3), because as we know at every time unit we have to check which process has the lowest period in between ready processes.

d) Now after 1 unit of P1, at time unit 5, ready processes are P1 and P2. Here P2 is the lowest period compare to P1, so we assign P2 for 2 units.

e) Now after completion of P2, at time unit 7, the only ready process is P1. So, we can assign P1 for 2 units because in between there is no ready process.

f) Now after P1 finished, at time unit 9, no process is ready. So, from time unit 9 to 10 there is no scheduling done.

g) At time unit 10, only P2 and P3 processes are ready and P2 has the lowest period. Here we assign P2 for 2 units.

h) At time unit 12, only P3 is ready to execute. So, we assign 2 units for P3.

i) Now after P3 finished, at time unit 14, no process is ready. So, from time units 14 to 15 there is no scheduling done.

j) At time unit 15, only P2 is ready to execute. So, we assign 2 units for P2.

Now P1, P2, and P3 are completed. 

Calculation for CPU utilization:

Process P1:  3x1=3 (Process P1 runs 3 units for 1 time in the total period)

Process P2:  2x4=8 (Process P2 runs 2 units for 4 times in the total period)

Process P3:  2x2=4 (Process P3 runs 2 units for 2 times in the total period)

CPU Utilization= 15/20 = 0.75 means 75%

Limitation of Rate Monotonic scheduling: 

Despite being optimal, then, rate-monotonic scheduling has a limitation: CPU utilization is bounded, and it is not always possible fully to maximize CPU resources. The worst-case CPU utilization for scheduling N processes is N(21/N − 1). With one process in the system, CPU utilization is 100 percent, but it falls to approximately 69 percent as the number of processes approaches infinity.