Multi tasking and real time systems

Multi tasking and real time systems


Scheduling is a major component when it comes to multi-tasking and real-time systems. As we squeeze in lot of tasks to be executed in a single CPU, the maximum utilization becomes very important. So to execute all the tasks efficiently without missing deadlines at the same time keeping the CPU utilization to the maximum a good choice of correct scheduling algorithms is necessary. So this paper discusses the various scheduling algorithms, gives a comparison of these scheduling algorithms and finally touches the area of multi-core scheduling.

Types of tasks:

There are three different types of tasks that need to be handled by the algorithms.

  • Periodic
  • Aperiodic
  • Sporadic

The periodic tasks are those that will repeat itself after certain predefined time. For example sampling a sensor output can be defined to be done every 10 ms.

Aperiodic tasks are the once that cannot be anticipated. They can occur anytime and at any frequency within a period of time. For example interrupts are aperiodic. An aperiodic task with hard deadlines and with a minimum time of arrival between two consecutive arrivals is called the sporadic tasks. Note that without that minimum inter-arrival time it is not possible to guarantee that the deadlines of the sporadic tasks will be met.

There are different scheduling strategies, which depends on the variation involved in these three parameters, the configuration, runtime dispatch and the analysis. In the configuration we decide before the start of the system, what is the information to be provided to the system, for scheduling. In the runtime dispatch it is how we switch task when the system is running. In most real-time systems there's little a user or the system analyst could do to do on this run-time dispatch part to alter the way the system behaves when it is in operation. Analysis is the method by which we predict or guarantee that the system will deliver the tasks within their timing constraints. The main difference between the scheduling algorithms is about how much of each part is involved.

There are two type of scheduling algorithms, the offline scheduling and the online scheduling. In the offline scheduling we decide all the tasks that are to be run, analyzed with some heuristics and then all the necessary inputs are fed to the system, and when the system is in operation there is no change made in the things that were decided. There are no specific algorithms formulated for this. Conditions are checked that all the deadlines are met. In the online method, the scheduling algorithm is provided the intelligence to act according to the situation; it modifies the order of task execution according to the changing priority to meet deadlines. In online scheduling algorithms there are two types of priority assignment, the static and the dynamic priorities. In this paper we will cover rate monotonic, deadline monotonic as part of static priority algorithms and Earliest Deadline First (EDF) and Rate monotonic with priority Inheritance protocol for dynamic priority. Finally in the periodic task scheduling we will discuss about the ubiquitous, round robin and FIFO scheduling algorithms.

In the static priority, the analysis is done with all the tasks that are needed to be run, their deadlines, periods are all calculated and given statically. There is no change of these priorities during run time. In the dynamic priority, according to the altering conditions the priorities keep changing, i.e. the priorities may keep changing for every other request of the same task.


Rate Monotonic:

This is one of the oldest scheduling algorithms. The work on rate monotonic was first presented by Liu and Layland in the year 1973 [1]. Rate monotonic follows a simple rule; the task with highest request rate is the task with highest priority. In their paper Liu and Layland say that for large task sets the processor utilization may be as low as 70%. And this can be improved by assigning priorities dynamically.

In this section we see a priority scheduling done by rate monotonic, which gives an optimum scheduling with static priority assignment. The following definitions are necessary for determining the optimum scheduling algorithm. Deadlineis the time before which the task should complete its execution, in rate monotonic deadline is equal to the period. An overflow occurs at time t, if a deadline of a task is not fulfilled at time t. The response time of a request is the difference in time when the task request arrives and the time when the task completes execution. The critical instantof a task is the time at which the task when released will have the largest response time. The critical time zone is the time interval between the critical instant and the response time of the corresponding task request.

There are a few assumptions made in the analysis of the Rate Monotonic algorithm:

  • The tasks that have hard deadlines are periodic and have constant inter-interval time.
  • Each task should be completely executed within its period, i.e. before the arrival of next task request.
  • The execution for every task is constant and they do not vary with time. Here execution time is the time taken by the processor to execute a task without interruption from other tasks.
  • All the tasks are independent to each other.
  • All aperiodic tasks are considered to be separate and they do not have hard deadlines.
  • The period is equal to the deadlines.

In their paper, Liu and Layland [1] showed that Rate Monotonic is optimal, in the sense that if any other fixed priority algorithm is able to schedule a task set, then rate monotonic algorithm will also be able to schedule the set. They also derived a least upper bound processor utilization factor. If a task set of n tasks is said to be schedulable if it follows the following condition:

U <= n (21/n - 1)

Where U is the utilization factor. Though this gives the schedulability condition, it is just a sufficient condition. A task set may be schedulable even if it does not satisfy this condition, which means if this condition is satisfied it is guaranteed that the task set it schedulable. The upper bound in the rate monotonic algorithm keeps decreasing as the number of task increases and it asymptotically reaches 69.3% as the number of task becomes very high.

As said the processor utilization test is a sufficient but not a necessary test condition. So in the case where a task set fails the processor utilization schedulability test it still needs to be check further for schedulability. One such test is the response-time analysis given by Joseph and Pandya [2]. This method will work for any static priority algorithm not specific to rate monotonic. In response time analysis, the worst case response time of all the tasks are obtained analytically and are compared individually to their corresponding deadlines. For any task ti the worst case response time Ri is given by:

Ri = Ci + Ii

Where Ci is the task computation time and Ii is the interference the task ti can experience within it critical time zone. For the highest priority task the worst case response time will be it computation time i.e. R = C, because it will not be interrupted by any other lower priority task. The calculation is simple, consider the task ti:

  1. Assume that all the higher priority tasks start at the same time this task ti is starting.
  2. Calculate the time by which this task is getting delayed by interference from other tasks. If the calculated response time is less than or equal to the deadline of the task then it is schedulable, otherwise the task ti will miss its deadline.

Consider one task tj that is of higher priority than task ti. So number of times that task tj interrupts task ti within its critical time zone is given by:


So the maximum interference time by tj on ti is given by:


So let us consider there are n tasks with higher priority than task ti. This gives the total interference from all these tasks on the task ti as:


Where hp(i) is the set of tasks that have priorities higher than the priority for the task ti. So the response time of the task ti summarizes to:


This formula can be extended to calculate the response time of nth task. Here the value of Ri appears in both the sides of the equation. This equation can be used to get the worst case response time of the (n+1)th task from the previously calculated worst case response time values of nth task.

Deadline Monotonic:

One of the assumptions of the Rate Monotonic algorithm is that the task deadlines are equal to the period. Which means the task is allowed to run anywhere between the period. And since the priority assignment is by the rate of arrival or length of period a very important task with long period will have a low priority. This is not a desirable characteristic in real-time applications. The deadline monotonic algorithm relaxes the assumptions of period is equal to deadline and extends rate monotonic to one step further [3]. In deadline monotonic shorter the relative deadline the higher will be the priority assigned to that task. This apparently means that if the period is equal to deadline then the priority ordering of the rate monotonic and deadline monotonic will be the same.

The Deadline Monotonic is a optimal algorithm in the sense that if any static priority algorithm is able to schedule a task set with unequal period and deadlines then the deadline monotonic will also be able to schedule that. And DM also over comes the above mentioned problem in RM where the tasks with longer periods will not meet deadlines. The schedulability test for the DM is similar to the Rate monotonic processor utilization analysis, by equating the time period to the corresponding task deadlines.

i=1nCiDi≤ n (21/n - 1)

But as in rate monotonic this schedulability test may fail and still a task set may be schedulable. In that case, the response time analysis can determine whether a task set is schedulable by Deadline Monotonic or not. In deadline monotonic we compare worst response time of tasks with their corresponding relative deadlines:

Ri ≤ Di

In the response time analysis the worst case response time must be equal to or less than the relative deadlines. Else the task set is not schedulable by deadline monotonic. This is a necessary and must to be satisfied condition by any task set to be schedulable by deadline monotonic and any other static priority algorithms.

Response time Analysis:

In their paper on response time analysis, Joseph and Pandya along with the necessary and the sufficient condition equations they also provided a solution for those static priority algorithms that do not satisfy the time period and the worst case response time condition [2]. The response time analysis is already discussed in detail in rate monotonic algorithm, and the worst case response time equation is derived which will be further used here for analysis. There may be a situation in which a task set, satisfies the LCM condition which bounds the average load within limits, but does not satisfy the worst case response time relation. In this case the worst case response time may be atleast one level higher than the period. The priorities of such systems are still possible with use of buffers to save the inputs, usually saved in a first come first serve basis.

Consider an interval 0 to Ti where the LCM condition is satisfied but not the worst case response time relation. The critical instant of the system occurs at time 0. So at this interval (0, Ti) there will be finite number of inputs arriving which needs to be served before the period Ti. So the number of buffers required will also be finite. It is in this critical instant that the maximum number of buffers will be used. The number of buffers required will be the smallest integer that satisfies the following condition:

Ri ≤ k*Ti

Where k is the number of buffers. For example consider there is one task that gets two inputs at an instant, we can have one buffer so as when one input is being served the other inputs is saved to the buffer preventing the loss of information. So in this case while the average load condition still holds, the worst case response time condition becomes:

Ri ≤ 2Ti

Thus relaxing the worst case response time relation.

Buffering can be a solution only if the average load condition is satisfied. In cases where the load condition is not satisfied, the average load over the entire system has to be reduced. There can be two possible solutions for this. One is the direct method where by increasing the processor speed reduces the time taken by each task thus reducing the average load. The second method is using multiple processors. This method is becoming more and more used for the power and it can provide over the latter method. In this method we divide the inputs to be processed by the system among the m different processors available thus reducing the load by m. An easy case that does not need any examination is the system where there are n inputs and m processors in such a way that n < m. Here if each of the inputs are assigned to every other processor and if a guarantee is given that the period of arrival of the inputs are less than the computing time then its very apparent that the deadlines are met. If n > m, then a suitable scheduling algorithm should be able to allocate the tasks statically the processors so that the response time analysis conditions are satisfied.

This is a simple method but has powerful outcome in the calculation of deadlines for real time systems. Careful coding of real-time systems will reduce a lot of problems faced. But that alone is not sufficient, neither is it sufficient enough if we just keep the processor utilization low, because still the tasks may miss the inputs at some critical instants where the worst case response time exceeds the time period. So it is necessary to calculate, check and analyze the tasks schedulability and response time for particular computation times. This will ensure that the hard deadlines are met. The analysis of the worst case response time makes a lot of assumptions:

  1. Every task is independent of each other. This is also becomes a necessary condition in the case where parallel computing is exploited.
  2. For a given task at a given particular computing time, inputs do not rely on its previous outputs.

And most of the static scheduling algorithms are proved considering these two assumptions. So it becomes the programmer's task to analyze the code in case of dependencies. While it is a general tendency to consider these cases to be handled on the fly, which can end up extremely complex and through surprising errors, especially in the conditions where we use multiprocessors and preemptive process handling.


Rate Monotonic and Priority Inheritance Protocol:

In the analysis of rate monotonic algorithms there were a few assumptions made that restrict the tasks to be independent of each other. But in the real scenario there will be dependencies like sharing global data where the two or more tasks trying to accessing the data have to be synchronized. This is very often done with synchronization techniques like semaphores, which offers a lot in the calculation of worst case execution time in these specific cases. This leads to a problem where a higher priority task is blocked by a lower priority task for indefinite time called priority inversion, and has been resolved with resource management protocols like priority inheritance and extension of that which is priority ceiling. These protocols tend to change the task priorities when the system is running to meet the tasks hard deadlines. So the rate monotonic no longer is a static priority algorithm, but now is a dynamic priority algorithm.

Normally a high priority task should be able to preempt a task with lower priority. But there may be cases where a lower priority job and the higher priority job shares a common global segment which has been locked previously by the lower priority task. So when the higher priority task tries to preempt it and finds the global segment already locked and gets blocked until the lower priority task relinquishes the lock. Let's analyze the scenario with an example, consider there are three tasks with J1, J2 and J3 with decreasing order of priorities. And consider J1 and J3 share a common global data segment, and a binary semaphore exists to lock the segment before accessing. Ideally J1 having higher priority should be able to preempt J3. At a time instance t, J3 starts and locks the global data segment. Then at any time t1, greater than time t, J1 starts and tried to lock the global data segment, finds it locked and gets blocked. Since J2 which is of higher priority than J3 but lower in priority than J1 does not access the global data segment, it can preempt the execution of J3. When J2 finishes since lock still exist, J3 starts running, blocking J1 again. Now the higher priority task J1 gets even more delayed, and will not be able to lock the global data segment until J3 relinquishes the data segment. We will not know how many times before releasing the lock J3 gets preempted by J2. And conditions can get even worse if there are many more tasks. Task J1 gets blocked indefinitely. This is not a desirable characteristic in real-time system and also reduces the reliability and predictability of the system.

Priority inheritance is one method to overcome this problem of priority inversion [5]. Now let's say in the above example task J1 when it finds the global data to be locked, and gets blocked. The priority inheritance protocol requires that the when it is executing the critical section which uses the lock it should run with the priority of task J1 which is the highest priority task that will be using the global data. This ensures that the task J3 is not interrupted by other at present lower priority task J2. When J3 completes the work and relinquishes the lock, it wakes up task J1 which was blocked on the same lock attains its original lower priority and task J1 now regains it actual priority, locks the global data and starts running. This ensures that the task J1, though it is blocked for the time J3 locks the global data, it does not get delayed by preemption by other tasks that are in higher priority than task J3. So by this way we can reduce the delay in execution of task J1, but one more necessity is bounding the delay which will be done using the following properties of priority inheritance. Take two tasks Jh and Jl, which shares the same lock, and Jl is of lower priority than Jh:

  1. The task Jh can be blocked by task Jl only if Jh tries to get the lock that is being held by Jl when Jh is initiated.
  2. The task Jl can block Jh only for one lock that it is holding on to now regardless of how many ever locks they share between them.
  3. Under PIP, if there are n tasks that are of lower priority than task Jh, then task Jh can be blocked for at most the duration taken to release one lock in each of these n tasks.
  4. Task Jl cannot acquire the priority of task Jh if it is holding a lock that is not tried to lock by task Jh when it is initiated, and so task Jl is preempted by Jh.
  5. If there are n semaphores that can block task Jh, then Jh can be blocked for at most n times.

So properties 3 and 5 place an upper bound on the maximum delay that can incur in the blocking scheme.

There are two things that are not addressed in the priority inheritance protocol, the deadlocks and chained blocking. Consider there are two tasks T1 and T2 with increasing priority, and two semaphores S1 and S2, shown in figure below. At time t1 task T1 is initiated and locks the semaphore S1. Then at any time t2 greater than time t1 task T1 makes an attempt for nested lock and tries to take semaphore S2. However at his time task T2 is initiated preempts the task T1 and locks semaphore S2. Now T2 tries to lock S1 which is already held by T1, and a deadlock is formed. Deadlock problem can be solved by carefully locking semaphores. But the chained blocking can cause substantial delay. Consider there is one more task T3 that is of higher priority and it has to take semaphores S1 and S2 in sequence. But tasks T1 and T2 have already taken it, then task T3 has to wait for two unlocks one on S1 by T1 and other on S2 by T2. The priority ceiling protocol addresses both the problems.

Chain Blocking, T3 with higher priority is blocked twice

The priority ceiling protocol belongs to a class of pessimistic protocols, which blocks a task for any other semaphore locked, which often ends in unnecessary locking, but it still improves the worst case delay introduced in the locking schemes. According to this protocol, a task T can lock a semaphore only if its priority is higher than all the priority ceilings of all other locked semaphores by lower priority tasks. So every semaphore is assigned a priority ceiling which is equal to the priority of the highest priority task among all the tasks that will potentially be locking it. So this priority ceiling prevents deadlocks and chained blocking. Now a peep into the properties of priority ceiling protocol:

  1. A task Th can be blocked by a task Tl which is of lower priority only if the priority of Th is not higher than the highest priority ceiling of all the semaphore held by lower priority tasks.
  2. Suppose a task Th preempts a task Tl which was executing in the critical region, and Th is running in the critical region, then the task Tl cannot inherit a priority equal to or higher than the task Th until Th completes execution.
  3. All the properties of the priority inheritance applies here, along with the additional checking of the priority ceiling assigned to every semaphore.

The following example elucidates the principle of priority ceiling. Consider three jobs J1, J2 and J3 with J3 given highest priority and J1 lowest. There are three semaphores associated with these jobs S1, S2 and S3, and their priority ceilings and job association are as follow,

J1 S1 (V=PJ2) S2 (V=PJ2)

J2 S1 (V=PJ2) S2 (V=PJ2)

J3 S3 (V=PJ3)

Where V is the ceiling of that semaphore and PS1, PS2 and PS3 are the priorities of jobs J1, J2 and J3 respectively.

Deadlock Prevention with Priority Ceiling

First job J1 runs and locks S1 and is preempted by job J2 which tries to lock S2. Since S1 which is associated with both J1 and J2 is already locked by S1 and priority of J2 is not greater than the ceiling of S1 it will not lock S2 and is blocked, and now the priorities of J2 and J1 are exchanged. Now J1 will lock S2, Job J3 which of higher priority than the exchanged priority of J1 preempts J1, locks S3 since it is not associated with any other locked semaphores, completes the task and gives back the CPU to J1. J1 runs to completion, unlocks the semaphores and falls back to its own priority. Now J2 preempts J1 locks S2 and S1 and proceeds with its work. This avoids deadlock and also assigning ceiling values avoids chain blocking of the higher priority tasks.

The combination of this in rate monotonic is interesting. In the rate monotonic we saw two main assumptions as, the tasks are independent to each other, and the blocking other than the blocking due to preemption by higher priority task were not considered. So here we need to include blocking time from three types of blocking direct blocking that is introduced while accessing shared memory region, push-through blocking introduced by priority inheritance, and the ceiling blocking from priority ceiling. Let's consider all this blocking to sum up to not more than Bi. Then by extending the processor utilization criteria of rate monotonic for these three blockings we have the resultant bound as:

i=1n+1CiTi+max⁡(B1T1,…,BnTn)≤ (n+1) (21/(n+1) - 1)

This bounds the rate monotonic algorithm for the tasks that are dependent and that have memory regions that are shared between other tasks.

Earliest Deadline First:

This algorithm is a dynamic priority algorithm that follows the rule that at any instance the task with the lowest absolute deadline will have the highest priority and is scheduled to run. The idea of EDF was given by Jackson, late in 1955. But the formal definition was given by Dertouzos in 1974 and the proof was given in the same paper in which rate monotonic algorithm was first introduced. In their paper Lui and Layland proved that EDF will have better processor utilization even 100% than the fixed priority algorithm rate monotonic [1].

Dertouzos introduced an interchange algorithm to exchange the tasks that are currently being executed and the task that has the lowest absolute deadline at any particular instant which is calculated as the sum of task release time and relative deadline, given by:

di,k = ri,k + Di

where di,k is kth job of task Ti, released at time ri,k with relative deadline Di. By that algorithm, consider T be any task that is executing at the instance j, and there is a task Te that at this instant j has the least absolute deadline. Then at this instant, the task Te is given higher priority over task T and Te and the time slices are exchanged. The time slice for task T is guaranteed at a time t so as its deadline is not missed.

A task set of m tasks is said to be schedulable by the earliest deadline first algorithm if it follows the following condition:

(C1/T1) + (C2/T2) + …. + (Cm/Tm) ≤ 1


Earliest Deadline First is considered to be one of the best dynamic scheduling algorithms because it gives maximum processor utilization, and also the priority does not depend on the period. It is allocated dynamically according to the absolute deadline as and when task is initiated at any particular instant. Which means the EDF can also be used to schedule aperiodic tasks. But there are a lot of misconceptions about EDF which will be dealt with here. We will have a small comparison between rate monotonic and earliest deadline first, and also why EDF is finding it hard to find its way into famous real-time operating systems [7].

The most common problem that everyone says about EDF is its implementation complexity. Rate Monotonic is the most used priority based scheduling algorithm because it is easy to implement. It can be implemented over existing preemptive kernels without any changes with ease. But EDF needs some major modification in the kernel keep track of the absolute deadline, task mapping according to their changing deadlines etc. This is one major reason specified for the popularity of RM. But the advantage here is according to Liu and Layland, RM can only provide a processor utilization of 69% for large number of tasks, but EDF provides better processor utilization nearly 100% the proof of which was derived by them in the same paper. It is commonly said that EDF results in high runtime overhead. In fact this is true to certain extent, because at every instant the scheduler has to calculate the absolute deadlines of the tasks and should allocate the cpu for the task with the least absolute deadline. But this is overhead is not there in the case of rate monotonic, where priorities are assigned statically and the scheduler should just dispatch the jobs in their allocated priority as and when they arrive. But due to the need that the static priority should be maintained RM tends to have lots of preemption whereas EDF may have very little preemption for the same task set. This implies that there is less context switching while using EDF compared to RM. This ability of EDF cancels out or rather proves advantages over RM, so the impact of this small runtime overhead is acceptable. One of the most interesting tests will be the robustness under overloads. There are two overloads that have to be considered, permanent overloads and transient overloads. In permanent overloads i.e. U > 1, both the algorithms tend to give somewhat similar results. In RM the lower priority tasks will never be given opportunity to run, but in EDF it reduces the overall rate. In transient overload conditions RM makes sure that the higher priority tasks are given time appropriately with the cost of missed deadlines in lower priority jobs. But in EDF since the priority depends on the deadlines any task that has least deadline will get to run. In this case RM has an advantage over EDF that higher priority tasks are not missed and the deadline misses are predictable. As for jitter and latency an outward thought over this issue, will show that EDF will have high jitter. But this is not always true, and it can be proved with counter examples as given the comparison between RM and EDF paper from Buttazzo. And again in RM jitter for high priority tasks are reduce with the cost of high jitter for lower priority tasks, but EDF gives an optimal performance reducing the overall systems jitter. It has been proved clearly that the input output latency in EDF is lesser than in RM by Cervin. It is a fact that many of us think that popular aperiodic scheduling algorithms like deferrable server, sporadic server, priority exchange etc, are available only for RM, but optimal algorithms like these are available for EDF too, which on combination produces better results compared to RM. And to make it clear RM out of the box does not support aperiodic task handling, but EDF can support aperiodic task handling to some extent, since priority is not given based on periods. One more major hurdle is resource sharing, where we hear protocols like priority inheritance protocol (PIP), priority ceiling protocol (PCP) which was introduces as an extension to PIP only for RM, but a lot of optimal algorithms are available for EDF too like dynamic priority inheritance, dynamic priority ceiling, stack resource policy etc. The availability of all these algorithms makes EDF predictable too. The problem with most of these arguments of superiority of RM is because of the popularity of RM, while EDF and its related algorithms are still not under extensive use and are research based schedulers. So their availability is either not commonly known or not used at all.

Round Robin and FIFO Scheduling:

These do not belong to the dynamic priority scheduling category. But round robin and FIFO are one of the most famous, simple, oldest and widely used algorithm in many real-time operating systems, so it takes its place here before we go ahead to aperiodic scheduling. As for round-robin, the policy is simple, as done in operating systems we have a ready queue which contains all the tasks that are ready to be executed. Consider there are n tasks and a general time slice is selected which is q. The n tasks will need 1/n of the CPU to complete execution. If this 1/n is lesser than the time slice then it completes the task and relinquishes the CPU which is then allocated to other tasks. If this 1/n is greater than the time slice allotted then the process is preempted and CPU is allotted to other task which is next in the ready queue. The task which is preempted is put to the end of the ready queue, which is executed again when its next time slice occurs. New tasks that arrive when system is on the fly are added to the end of the ready queue. So brief it up a queue is maintained where new tasks and preempted tasks are added to the end of the queue and processes at the top of the queue get the CPU and are executed until the time slice expires. A special case in this is when execution time 1/n of all the tasks is less than the time slice, in this condition the round robin become similar in working to the FIFO algorithm, which makes it clear that the only difference between the round-robin and the FIFO is the time slice. In FIFO the task that is given the CPU, executes to completion, there is no time slice for it to be preempted. One more parameter to be noted is the waiting time of the task nq, which can be extended with a more accurate time of nq + ∆t, where ∆t is the context switch overhead. Usually in real-time operating systems it is carefully designed such that this overhead time is negligible compared to the waiting time nq.


Real-time systems are so restrictively built such that even aperiodic tasks have to meet their deadlines. As said before there is no guarantee of the schedulability of the sporadic task without knowing the minimum inter-arrival time. There are many algorithms that in combination with other periodic scheduling algorithms provide schedulability for aperiodic tasks. Some of them are priority exchange, deferrable server, sporadic server for hard aperiodic tasks and the most widely used algorithms like background processing and polling server for tasks with soft deadlines which we will be discussing here [9].

One method of servicing soft aperiodic deadline is background processing. In this an aperiodic request is run as a background task, whenever processor is idle without other periodic request. This method may not be suitable because consider a case where the periodic task processor utilization is very high, or sometime when there is overload in periodic tasks utilization, then aperiodic tasks may get very less time to execute or may never be serviced at all. But this has to be avoided; aperiodic tasks should be services like any other periodic task. So to ensure this the polling server introduced a new method in which there will be a periodic task that will service the aperiodic task. This periodic task will be run periodically in a predetermined period and any aperiodic task that falls when this periodic task arrives will be serviced. But problem with this is if an aperiodic task arrives just after the instance of servicing periodic task, it has to wait for the next execution of the servicing periodic task. There is another special case problem here, consider the execution time of the servicing periodic task is t, and an aperiodic task arrives which needs an execution time lesser than that allotted for the servicing periodic task, then the rest of the allotted time is wasted away, another problem following this will be if the execution time t is less than the aperiodic task that arrives, then it will take two instances for the periodic task to complete the aperiodic job, which might be a long time provided the period of the servicing periodic task is long, because it has to wait until next arrival period to be completed.

The priority exchange (PE) and deferrable server (DS) introduced by Lehoczky, Sha and Strosnider overcome these problems that were of the polling server and background processing. These algorithms rather than wasting away the excess time allotted will preserve the time for further use so that aperiodic tasks that come immediately after another aperiodic tasks and is before the next period of the server can also be served. After a period they have a replenishment period when the exhausted time is replenished for use again. These are called bandwidth conservation algorithms since they conserve the available excess bandwidth rather than rendering them unusable as in polling server and background processing. This has also proved to be efficient and provides better response to aperiodic tasks.

The difference between DS and PE is in the way they conserve the bandwidth. The DS has a high priority aperiodic execution time that is preserved over the period of the server. And the aperiodic tasks are serviced as and when received if the execution time within that period is not exhausted. The execution time is then replenished if exhausted in the next period of the server. But the PE's way of preserving the execution time is bit different and increases the implementation complexity of the PE. In PE the high-priority execution server is first replenished to its full capacity at the beginning. If any aperiodic tasks are pending for execution then it uses the high-priority execution server to complete its execution. If not the high-priority aperiodic execution time is utilized by the highest pending periodic task. In this way the bandwidth is preserved as the periodic task execution time and is not lost by exchanging the priorities with each other. This priority exchange continues until the aperiodic execution time is exhausted by an arrival of an aperiodic task or if it is degraded to priority lower than the lowest priority (this happens only if no aperiodic request occurs within the period of the execution server). And any tie in priority will always be won by the aperiodic execution server, since it provides a low overall average response time for aperiodic tasks. The execution time of the server is called the server size (Us) in both PE and DS. The periodic task bound (Up) is determined by the size of this aperiodic task execution server, which was derived in the same paper to be:

PE: Up = ln ( 2/(Us + 1) ) DS: Up = ln ( (Us + 2)/(2Us + 1) )

On comparing PE and DS we see that, DS is simple to implement but PE is complex since it has to maintain aperiodic tasks at all priority levels. The average priority of the DS server is higher than PE server because DS maintains the priority in the same level over the entire period. But the PE has a server size advantage over the DS; the server size of PE is higher. PE will prove to be advantageous when there are multiple servers running over different priority levels. A good soft aperiodic scheduling algorithm will have the advantages of both these scheduling algorithms, the server size advantage of PE and the less implementation complexity advantage of the DS. And with this it should be able to provide support for aperiodic tasks with hard deadlines. A minimum inter-arrival time is to be known for guaranteeing hard deadlines and the aperiodic task deadline must be equal to or greater than the minimum inter-arrival time. The sporadic server guarantees this with a deadline based priority assignment.

The main difference between these two and the Sporadic Server (SS) is the way the SS replenishes its execution time. The SS replenishes the execution time only when all or some of its execution time is used up. In the SS there is replenishment time (Rt). When a small or all of the execution time is used up the server is scheduled to be replenished in the time Rt. An example would explain this clearly. Consider a SS with execution time 3, and replenishment time Rt. At time t1 a aperiodic task arrives and the server runs the task, and the task uses up half of the servers time i.e. 1.5, now a replenishment will be scheduled at time Rt when the task starts execution, which will schedule the replenish the servers depleted execution time of 1.5 and not more than that. And again if another aperiodic task arrives and uses up the rest of the servers execution time then another replenishment is scheduled at time, Rt from now. So a replenishment cycle is scheduled as and when the execution time of the server gets used up. This is the advantage of the SS. Unlike the PE and DS where there is a particular period over which the entire server capacity is replenished without taking into consideration the amount of server capacity used up, here replenishment occurs when execution time is used up and the amount used up is the amount to be replenished. This provides good responsiveness to aperiodic task. Thus SS proves superior to PE and DS. We shall see priority exchange, deferrable server and sporadic server with an example for each.


All the above mentionsed online scheduling algorithms will be optimal scheduling algorithms for single processors. But when there is a question of having two or more processors in the systems, the optimality of the schedulers are proved to be wrong. In the multiprocessor environment a task set cannot be scheduled by any online scheduling algorithm without the knowledge of three parameters the start time, deadlines and the computation time, which means if these three parameters are not provided there is no online scheduling algorithm that can provide an optimal scheduling. It will provide schedulability for some tasks in the cost of other, or at the cost of delayed response time. Dertouzos and Aloysius in their paper on online scheduling algorithms for multiprocessors proved this theory using theorems and counter examples [12]. They also derived two bounding conditions or sufficient conditions which when satisfied by a task set, it can be scheduled by any good algorithms like EDF or least laxity scheduling. In their paper they proposed that any scheduling algorithm that takes a task set for scheduling might need prior knowledge of their start times. The first case is if a task set has unit computation time for all its task set. This is a very simple case which will not be followed by if not all, many of the systems. For tasks with some random computation time they proved that, if all the tasks are schedulable when their start times are same, then this task set will also be schedulable online even if they have different start time when the system is running. If this boundary condition is satisfied the task set can be scheduled with one of the above scheduling algorithms, the EDF or the least laxity, which schedules without the knowledge of the start times.

Though the above has been proved, researchers have been constantly bringing out different sufficient and necessary conditions to make many of the already existing online scheduling algorithms fit in the multiprocessor scheduling space. Baruah in his paper on “Scheduling periodic tasks on uniform processor” loosely categorizes multiprocessors into three types:

Identical parallel Machines: These are multiprocessors where all the processors have the same computing power.

Uniform parallel machines: Every processor is associated with its own computing capacity. The Identical parallel machines are a special case in this category.

Unrelated parallel machines: Each processor and task ordered pair is characterized by an execution rate.

Among these he says the uniform parallel machines model is the one that is used in many real-world systems, and gives three reasons for that:

  1. It gives the freedom to use processors of variable speeds.
  2. It provides a way in which even identical processors can have a part of it for running periodic real-time tasks and the rest is utilized for some other non-real-time tasks.
  3. New faster processors become available every other day. So with this model we will be able to add processors to the existing ones and make the system extendible.

To model periodic tasks he considers the following constraints that need to be satisfied: Job preemption is permitted, job migration is permitted (jobs generated by a task can be run on different processors at different times), and finally job parallelism is forbidden (same job cannot be run on different processors at the same time). Many application do not consider the constraint that preemptions can be done only in certain circumstances. He defines an integer boundary conditions for that according to which the jobs that are executing in a processor can be preempted only on integer number of execution units. For example a task after completing execution for one time unit it can be preempted or continue execution, then after the next time unit of execution it can be preempted or continue running. It cannot be preempted between the execution time of this one whole unit. He proposed two theorems in which he says: the feasibility analysis of a system of n periodic tasks on m uniform processors can be done in O(n + mlogn) (reference from “Scheduling periodic tasks on uniform processor” - Sanjoy baruah), and a second theorem in which he says feasibility analysis of a task set considering the IBC can be intractable and is NP-hard. There are certain special cases where even with IBC the system is tractable. Consider the light system, a system where the maximum weight of a task is lesser than the minimum computing time of the processor. In a system of this kind even with IBC imposed the system can be scheduled by a known periodic scheduling algorithm.

Multiprocessor Rate Monotonic:

Keeping in mind the above three categorizations of multiprocessors and the reasons for choice of uniform parallel machines, we go into the extension of the RM algorithm for the multiprocessors. Buruah and Goossens extended the RM to multiprocessors [16]. In their paper stated the same reason mentioned above for uniform parallel machines choice, and stated that RM for multiprocessors will be based on Global scheduling model and it will be designed as a greedy scheduling algorithm. An algorithm is said to be greedy if it satisfies the following conditions:

  1. It does not idle any processor when there are tasks ready in the ready queue.
  2. If it idles any processor because of the non availability of tasks to be executed it will be the slowest one that is idled.
  3. The fastest processor will execute the highest priority job; this ensures reduced computation times for high priority tasks and eventually meeting deadlines.

The terms used in the explanation are:

P - an uniform multiprocessor platform.

N(P) - N processors of the platform P.

si(P) - ith fastest processor.

S(P) - the total computing capacity of the platform P of N processors.

l(P) - max(i) {j=i+1NPsjP/si(P)} i = 1 to N(P)

u(P) - max(i) {j=iNPsjP/si(P)} i = 1 to N(P)

With this they derived a sufficient condition which is proved with 3 lemmas that when satisfied will make RM feasible for a task set T = {T1, T2, T3,...} over the uniform multiprocessor platform P.

S(P) ≥ 2.U(T) + u(P) . Umax(T)

is the sufficient condition for ensuring RM is feasible over P.

Multiprocessor EDF and DM:

T. P. Baker took a different path in his paper for multiprocessor EDF and DM, which made the bounding conditions more generalized. The problem is analyzed like this, consider a periodic task set T1, T2, … Tn where each task have a computation time c, deadline d and period P, with c ≤ d ≤ P. This task set is scheduled by a preemptive EDF or DM algorithm on m processors. They analyzed the situation when a deadline is missed and proposed lower and upper bounding condition on the load. Let the task Tk is the one that is missing the deadline, the time window at which deadline is missed is [t, t+dk) which is mentioned as the problem window in the explanation. In a multiprocessor environment when a deadline is missed it means the task Tk is preempted or not allowed to run on the time it is initiated and all the available processors are busy. A lower bound on the load is given like this, if W/dk is the load in the problem window, and t + dk is the missed deadline, then,

W/dk > m (1 - ck/dk) + ck/dk

Further this problem window can be split into three parts for give the upper bound, the head, tail and the body. The head contains any carry in load which is started at a time tb such that tb < t. If a window does not contain the head then the head is null and it does not have any contribution in the overall load of the window. This is the carry-in job. The head is characterized by the difference in computing time problem window and the time it started. Unlike the head, the body and tail have direct impact on the load of the problem window and it is also characterized by the starting time and the deadline. A problem window for task T1 is shown in the figure.

With this problem window analysis Baker derived three bounding algorithm for each EDF and DM for demand, upper bound on load and schedulability test. With this general analysis that can be done for any number of processors they extended EDF and DM to m processors.


Andersson, Baruah and Jonsson experimented on the global static priority scheduling and came up with an algorithm and its boundary conditions [13]; it is basically an extension of the rate monotonic algorithm. In the multiprocessor scheduling there are two approaches: partitioned scheduling, where every task is allocated a processors and all the jobs generated by the task are run on the same processor it is allocated, but in the global scheduling approach task migration is permitted where by jobs generated by task can be run on different processors that is free to execute at that moment the task becomes ready. They call this global static priority scheduling algorithm as RM-US[m/(3m-2)] where m is the total number of identical processors available. Any task set (T) which satisfies the condition U(T) ≤ m2/(3m-2) can be scheduled on m processors with unit speed by the algorithm RM-US[m/(3m-2)]. They have also proved the schedulability of the algorithm with an experimental set up of 900 tasks being scheduled on 30 processors taking it as 30 sets of tasks, and as the number of processors (m) increases the schedulability of the RM-US[m/(3m-2)] algorithm decreases. They have also proved that no static priority algorithm will give a utilization bound of more than 50% of the system's capacity.


Most of the commercial RTOS do not support the algorithms that are theoretically proved to be optimal [21]. EDF for example, after so much research and proof of optimality EDF is yet to find its way into the best of commercial RTOS available in the market like VxWorks and QNX, which means there should be many overheads that do exists apart from what is considered from theoretical proofs. It is supported by a lot of research kernels like SHARK, ERIKA Enterprise, The Everyman kernel, MaRTE OS, AQuoSA and RTLinux. Whereas RM can be implemented over any commercial RTOS, most of the real-time systems developed in VxWorks use RM implemented over its preemptive kernel. Another claim that is given for the extensive usage of RM over EDF thought EDF provide excellent utilization bounds is RM dies gracefully. In case of some overloads that tasks that crosses deadlines are the tasks for which we set lower priorities, so we know the tasks that will be missing the deadlines and it can be implemented in such a way that even if the task fails the system will keep running with minimal problems. But in case of EDF it's hard to predict which task will miss the deadline because the tasks are scheduled dynamically. VxWorks also supports priority inheritance and priority ceiling protocols whereas RTLinux does not support these. All these commercial RTOS use round-robin or FIFO as their default scheduling algorithms. As for aperiodic scheduling one of the best algorithm is the sporadic server and it is supported by the POSIX API's, so any kernel that is POSIX compliant may also include this, QNX includes sporadic server for aperiodic task scheduling. The two RTOS have also long supported SMP. It is necessary to consider your functionality and chose the best RTOS which supports the algorithm which you need, taking into consideration other parameters that are needed are supported by that RTOS.


This paper presents some of the important scheduling algorithms used in scheduling hard real-time systems. Starting with uniprocessor scheduling schemes we saw scheduling of periodic tasks with static priority algorithms like rate monotonic, deadline monotonic their boundary conditions and dynamic priority algorithms like EDF, the problem of applying rate monotonic in systems where there is a probability of higher priority task waiting for lower priority task, resource allocation protocols like priority inheritance and priority ceiling protocol and how the combination of these resource allocation protocol makes rate monotonic a dynamic scheduling algorithm. We also detailed the necessary and the sufficient conditions for schedulability of a task set using each of these scheduling algorithms.

Coming to aperiodic tasks we examined three main important algorithms the deferrable server, priority exchange and the sporadic server, along with this polling and background task execution was also discussed for comparison purposes. We saw that the sporadic server algorithm has an edge over both deferrable server and the priority exchange by combining the advantages of both, the larger server bandwidth of the priority exchange and the simplicity and the ability to maintain the priority of the execution sever at the original level for the entire duration of the server, of the deferrable server. It provides better response times for the sporadic tasks and also performs well when combined with other periodic hard real-time tasks.

Finally we moved to the multiprocessor scheduling algorithms. We first proved the non-feasibility of the already available uniprocessor scheduling algorithms to schedule in multiprocessor environment. It was proved that no online scheduling algorithm can provide optimal schedulability if it does not satisfy the two boundary conditions specified and when satisfied any scheduling algorithm like the EDF or least laxity algorithm will be able to provide optimal schedulability. Then we divided the multiprocessor arena into three types and chose one which would fit for most of the real-time systems. The scheduling scheme was divided into two categories the partitioned scheduling and the global scheduling. At many circumstances results showed that global scheduling would provide better utilization bounds. A new algorithm basically an extension of the multiprocessor rate monotonic, the RM-US[m/(3m-2)] was studied. We have also studied the extension of EDF and deadline monotonic to the multiprocessors. Thus an overall coverage of different types of task, types of scheduling, multiprocessor scheduling and modeling techniques were done.

Please be aware that the free essay that you were just reading was not written by us. This essay, and all of the others available to view on the website, were provided to us by students in exchange for services that we offer. This relationship helps our students to get an even better deal while also contributing to the biggest free essay resource in the UK!