A Complete Idea about Real Time CPU-Scheduling (Part-8)
CPU scheduling for real-time operating systems involves special issues. There are 2 major types of systems:
- Soft real time systems — They provide no guarantee as to when a critical real-time process will be scheduled. They guarantee only that the process will be given preference over noncritical processes.
- Hard real time systems — They have stricter requirements. A task must be serviced by its deadline; service after the deadline has expired is the same as no service at all.
There are certain issues associated with these types of scheduling. One such is the task of minimising latency.
Minimising Latency
Event latency refers to the amount of time that elapsed between the event occurring and when it is serviced. Different events may have different latency requirements.
There are 2 types of latency which affect real time systems. They are -
Interrupt Latency
Dispatch Latency
Interrupt latency refers to the period of time from the arrival of an interrupt at the CPU to the start of the routine that services the interrupt. When an interrupt occurs, the operating system must first complete the instruction it is executing and determine the type of interrupt that occurred. It must then save the state of the current process before servicing the interrupt using the specific interrupt service routine (ISR). The total time required to perform these tasks is the interrupt latency.
One important factor contributing to interrupt latency is the amount of time interrupts may be disabled while kernel data structures are being updated. Real-time operating systems require that interrupts be disabled for only very short periods of time.
Dispatch latency is the amount of time required by the scheduling dispatcher to stop one process and start another. The most effective technique for keeping dispatch latency low is to provide preemptive kernels.
The below figure illustrates the dispatch latency:
The conflict phase in dispatch latency has 2 parts:
- Preemption of any process running in the kernel.
- Release by low-priority processes of resources needed by a high-priority process
Let us now see different types of scheduling.
Priority Based Scheduling
Real time systems are required to immediately respond to a real time process. As a result it needs to support a priority based scheduling algorithm with preemption. Since it is priority based each process must be assigned a priority and since it is preemptive, a process currently running on the CPU will be preempted if a higher-priority process becomes available to run.
We have already discussed preemptive priority based scheduling in previous blogs. Most OS give the highest priority to real time processes. A preemptive priority based scheduler only provides soft real time functionality. We need other considerations for hard real time systems. In the coming parts we will discuss considerations for hard real time systems.
First we need to discuss a few terms for further discussion. We assume the processes to be periodic. This means that they require CPU at constant intervals.
Processes in this type of scheduling may sometimes have to announce its deadline requirements to the scheduler. Then using 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
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. The shorter the period, the higher the priority; the longer the period, the lower the priority.
Let us now consider 2 processes, P1 and P2. The time period of each is 50 and 100 respectively (p1 = 50 & p2 = 100). We also consider the processing time to be 20 and 35 respectively (t1 = 20 & t2 = 35). The deadline for each process requires that it complete its CPU burst by the start of its next period.
Suppose we assign P2 a higher priority than P1. As we can see, P2 starts execution first and completes at time 35. At this point, P1 starts; it completes its CPU burst at time 55. However, the first deadline for P1 was at time 50, so the scheduler has caused P1 to miss its deadline.
But if we were to use Rate Monotonic Scheduling, P1 has a higher priority than P2 because the period of P1 is shorter than that of P2. P1 starts first and completes its CPU burst at time 20, thereby meeting its first deadline. P2 starts running at this point and runs until time 50. At this time, it is preempted by P1, although it still has 5 milliseconds remaining in its CPU burst. P1 completes its CPU burst at time 70, at which point the scheduler resumes P2. P2 completes its CPU burst at time 75, also meeting its first deadline. The system is idle until time 100, when P1 is scheduled again.
Rate-monotonic scheduling is considered optimal in that if a set of processes cannot be scheduled by this algorithm, it cannot be scheduled by any other algorithm that assigns static priorities.
Despite being optimal, then, rate-monotonic scheduling has a limitation: CPU utilisation is bounded, and it is not always possible fully to maximise CPU resources. The worst-case CPU utilisation for scheduling N processes is N(2N — 1).
Earliest Deadline First Scheduling
Earliest-deadline-first (EDF) scheduling dynamically assigns priorities according to deadline. The earlier the deadline, the higher the priority and the later the deadline, the lower the priority. Under the EDF policy, when a process becomes runnable, it must announce its deadline requirements to the system. Priorities may have to be adjusted to reflect the deadline of the newly runnable process.
Let us again consider the processes that we have seen above (p1 = 50, p2 = 80, t1 = 20, t2 = 35). Process P1 has the earliest deadline, so its initial priority is higher than that of process P2. Process P2 begins running at the end of the CPU burst for P1. However, whereas rate monotonic scheduling allows P1 to preempt P2 at the beginning of its next period at time 50, EDF scheduling allows process P2 to continue running. P2 now has a higher priority than P1 because its next deadline (at time 80) is earlier than that of P1 (at time 100). Thus, both P1 and P2 met their first deadlines. Process P1 again begins running at time 60 and completes its second CPU burst at time 85, also meeting its second deadline at time 100. P2 begins running at this point, only to be preempted by P1 at the start of its next period at time 100. P2 is preempted because P1 has an earlier deadline (time 150) than P2 (time 160). At time 125, P1 completes its CPU burst and P2 resumes execution, finishing at time 145 and meeting its deadline as well. The system is idle until time 150, when P1 is scheduled to run once again.
Unlike the rate-monotonic algorithm, EDF scheduling does not require that processes be periodic, nor must a process require a constant amount of CPU time per burst. The only requirement is that a process announce its deadline to the scheduler when it becomes runnable.
Proportional Share Scheduling
Proportional share schedulers operate by allocating T shares among all applications. An application can receive N shares of time, thus ensuring that the application will have N/T of the total processor time.
As an example, assume that a total of T = 100 shares is to be divided among three processes, A, B, and C. A is assigned 50 shares, B is assigned 15 shares, and C is assigned 20 shares. This scheme ensures that A will have 50 percent of total processor time, B will have 15 percent, and C will have 20 percent.
Proportional share schedulers must work in conjunction with an admission-control policy to guarantee that an application receives its allocated shares of time. An admission-control policy will admit a client requesting a particular number of shares only if sufficient shares are available.
Quiz Time
- T shares of time are allocated among all processes out of N shares in __________ scheduling algorithm.
a) rate monotonic
b) proportional share
c) earliest deadline first
d) none of the mentioned - Earliest deadline first algorithm assigns priorities according to ____________
a) periods
b) deadlines
c) burst times
d) none of the mentioned - A process P1 has a period of 50 and a CPU burst of t1 = 25, P2 has a period of 80 and a CPU burst of 35., can the two processes be scheduled using the EDF algorithm without missing their respective deadlines?
a) Yes
b) No
c) Maybe
d) None of the mentioned
Wrap Up (Conclusion)
In this blog, we learnt what precisely is meant by Real-time CPU Scheduling, as well as different ways for scheduling the same, and we saw some crucial words that you need know before we can make real-life systems and use all of these ideas.
From the next blog, we will be focused on some research subjects in CPU Scheduling, which is the most exciting aspect of this entire blog series.
This completes the part-8 of this blog series on CPU Scheduling.
Thanks for reading!
We hope you found the content interesting. If you enjoy it, please share it with your friends. Something not stated, or would you want to offer your thoughts? Please leave a remark below, and we will respond as soon as possible. 😉
