/**/ Real Time Scheduling Algorithms - Operating System Dextutor

Real Time Scheduling Algorithms

Real time scheduling is of two types: Soft Real-Time scheduling which does not guarantee when when a critical real-time process will be scheduled; Hard Real-Time scheduling in which the process must be scheduled before the deadline. In this post we will cover two real time scheduling algorithms: rate monotonic scheduling and earliest deadline first.

Points to Remember in Real Time Scheduling Algorithms

Before starting with the algorithms, it is important to discuss a view characteristics of the processes that are to be scheduled.

The foremost is that the processes are considered periodic i.e., the process will repeat itself after a fixed period of time. The period of a process is denoted by p. The next characteristic is the processing time t i.e., the time for which the process requires the CPU within each period. In other words processing time refers to the burst time. The final characteristic is the deadline d, i.e., the time before which the process must be serviced. In general the relationship between these three characteristics is

0≤t≤d≤p
characteristics of Real time scheduling algorithms

Rate Monotonic Scheduling

In rate-monotonic scheduling algorithm a static priority policy with preemption is used. Whenever a high priority process arrives it will preempt a lower priority process. Every process gets the priority according to its period. Lower the period higher is the priority. Also, the processing time remains the same in each period.

Example:

Suppose there are two processes, P1 and P2. The periods for P1 and P2 are 50 and 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.

ProcessPeriod/DeadlineCPU Burst
P15020
P210035

Solution:

Since, it is mentioned that deadline for each process requires that it complete its CPU burst by the start of its next period, therefore, the deadline is same as the period of a process.

The priority of P1 is higher than P2 because P1 has smaller value for period. Therefore, at time 0, P1 will begin its execution. P1 will finish at 20 and then P2 will begin its execution (Refer Figure 1). At time 50 P1’s second period will start. At the same time P2 has completed 30 nsec only. But since priority of P1 is higher, so P1 will preempt P2 and runs from 50-70. P2 completes the remaining 5 nsec from 70-75 but still meets its deadline of 100. The system remains idle till 100, when the 3rd period of P1 and second period of P2 will start and P1 will begin the execution at that time. The rest of the execution will follow the same execution order as was from 0-100.

rate monotonic scheduling - real time scheduling algorithms
Figure 1: Rate Monotonic Scheduling Algorithm

Failure of rate Monotonic Scheduling:

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

ProcessPeriodCPU Burst
P15025
P28035

In the above example, if we use rate monotonic scheduling, the first process to begin execution will be P1 (lower time period). P1 will execute till 25nsec and then P2 will begin execution and run till 50 when P1 will begin its second period. Till time 50 P2 will finish 25nsec and will be left with 10nsec more. Now, the second peiord of P1 will be between 50 – 75. Now, P2 will requires 10nsec more to finish but only 5nsec are left for the deadline (which is 80). Hence, P2 is not able to finish its execution within the deadline. Thus, Rate Monotonic Scheduling can not be used in this particular scenario.

Earliest Deadline First Scheduling

The second algorithm under real time scheduling is Earliest Deadline First Scheduling. This algorithm assigns priority to the process based on the deadline. Earlier the deadline, higher is the priority. Thus, the priorities keep on changing in this scheduling.

Example:

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

ProcessPeriod/DeadlineCPU Burst
P15025
P28035

Solution:

Since, the deadline for P1 (50) is earlier than P2 (80) hence, the initial priority of P1 is higher than P2. So, P1 executes from 0-25 (Figure 2). Then, P2 starts at 25. At 50 P1 also arrives for second period. At this point the deadline of P2(80) is earlier than the deadline of P1 (which is 100 for second period), hence, P2 will continue till 60. P1 starts at 60. P2 arrives for second period at 80. At this point P1 is having higher priority because deadline for P1 is 100 whereas for P2 it is 160.

So, P1 continues will 85 after which P2 starts. At 100 P2 is preempted because priority of P1 is higher as the deadline for its third period is 150 (which is earlier than deadline of P1 which is 160). So P1 runs from 100-125 and then P2 completes its second period from 125 to 145. The system remains idle till 150 and then P1 resumes its next period.

Figure 2: Earliest deadline first algorithm

PPT on Real Time Scheduling

Practice Question on Real Time Scheduling Algorithms

Practice Question on Rate Monotonic Scheduling

Q. Consider two processes, P1 and P2, where p1 = 40, t1 = 20, p2 = 70, t2 = 30. Deadline for each process is equal to the period of the process. Illustrate the scheduling of these two processes using rate monotonic scheduling.

Practice Question on Earliest Deadline First Scheduling

Q. Consider two processes, P1 and P2, where p1 = 50, t1 = 25, p2 = 75, t2 = 30. Deadline for each process is equal to the period of the process. Illustrate the scheduling of these two processes using earliest-deadline-first (EDF) scheduling.

Relevant Reading Material

First Come First Serve Scheduling

Shortest Job First Scheduling

Round Robin Scheduling