Module Lesson

6 30
Embedded System Real-Time Task
Software Scheduling – Part 2
Version 2 EE IIT, Kharagpur 1 Version 2 EE IIT, Kharagpur 2
Specific Instructional Objectives 1.1. Types of Event Driven Schedulers
At the end of this lesson, the student would be able to: We discuss three important types of event-driven schedulers:
x Simple priority-based
x Get an introduction to event-driven schedulers
x Rate Monotonic Analysis (RMA)
x Understand the basics of Foreground-Background schedulers x Earliest Deadline First (EDF)
The simplest of these is the foreground-background scheduler, which we discuss next. In
x Get an overview of Earliest Deadline First (EDF) Algorithm
section 3.4, we discuss EDF and in section 3.5, we discuss RMA.
x Work out solutions to problems based on EDF
x Know the shortcomings of EDF 1.2. Foreground-Background Scheduler
x Get an overview of Rate Monotonic Algorithm (RMA) A foreground-background scheduler is possibly the simplest priority-driven preemptive
x Know the necessary and sufficient conditions for a set of real-time tasks to be RMA- scheduler. In foreground-background scheduling, the real-time tasks in an application are
schedulable run as fore- ground tasks. The sporadic, aperiodic, and non-real-time tasks are run as
background tasks. Among the foreground tasks, at every scheduling point the highest
x Work out solutions to problems based on EDF priority task is taken up for scheduling. A background task can run when none of the
x Infer the maximum achievable CPU utilization foreground tasks is ready. In other words, the background tasks run at the lowest priority.
Let us assume that in a certain real-time system, there are n foreground tasks which are
x Understand the Advantages and Disadvantages of RMA denoted as: T1,T2,...,Tn. As already mentioned, the foreground tasks are all periodic. Let TB be
x Get an overview of Deadline Monotonic Algorithm (DMA) the only background task. Let eB be the processing time requirement of TB. In this case, the
completion time (ctB) for the background task is given by:
x Understand the phenomenon of Context-Switching and Self-Suspension n
ctB eB  (1i=1¦ ei  pi)
B B … (3.1/2.7)
This expression is easy to interpret. When any foreground task is executing, the background
1. Event-driven Scheduling – An Introduction
task waits. The average CPU utilization due to the foreground task Ti is eipi, since ei amount of
processing time is required over every pi period. It follows that all foreground tasks together
In this lesson, we shall discuss the various algorithms for event-driven scheduling. From the n
previous lesson, we may recollect the following points: would result in CPU utilization of i=1¦ ei  pi. Therefore, the average time available for execution
n
The clock-driven schedulers are those in which the scheduling points are determined by the of the background tasks in every unit of time is 1i=1¦ ei  pi. Hence, Expr. 2.7 follows easily.
interrupts received from a clock. In the event-driven ones, the scheduling points are defined by We now illustrate the applicability of Expr. 2.7 through the following three simple examples.
certain events which precludes clock interrupts. The hybrid ones use both clock interrupts as well
as event occurrences to define their scheduling points
Cyclic schedulers are very efficient. However, a prominent shortcoming of the cyclic 1.3. Examples
schedulers is that it becomes very complex to determine a suitable frame size as well as a
feasible schedule when the number of tasks increases. Further, in almost every frame some Example 1: Consider a real-time system in which tasks are scheduled using foreground-
processing time is wasted (as the frame size is larger than all task execution times) resulting background scheduling. There is only one periodic foreground task Tf : (If 0, pf 50 msec, ef
in sub-optimal schedules. Event-driven schedulers overcome these shortcomings. Further, event- 100 msec, df 100 msec) and the background task be TB (eB 1000 msec). Compute the
B B

driven schedulers can handle aperiodic and sporadic tasks more proficiently. On the flip side, completion time for background task.
event-driven schedulers are less efficient as they deploy more complex scheduling algorithms.
Therefore, event-driven schedulers are less suitable for embedded applications as these are Solution: By using the expression (2.7) to compute the task completion time, we have
required to be of small size, low cost, and consume minimal amount of power. ctB 1000  (150100) 2000 msec
B

It should now be clear why event-driven schedulers are invariably used in all moderate and So, the background task TB would take 2000 milliseconds to complete.
B

large-sized applications having many tasks, whereas cyclic schedulers are predominantly
used in small applications. In event-driven scheduling, the scheduling points are defined Example 2: In a simple priority-driven preemptive scheduler, two periodic tasks T1 and T2
by task completion and task arrival events. This class of schedulers is normally preemptive, and a background task are scheduled. The periodic task T1 has the highest priority and
i.e., when a higher priority task becomes ready, it preempts any lower priority task that may be executes once every 20 milliseconds and requires 10 milliseconds of execution time each
running. time. T2 requires 20 milliseconds of processing every 50 milliseconds. T3 is a background
task and requires 100 milliseconds to complete. Assuming that all the tasks start at time 0,
determine the time at which T3 will complete.

Version 2 EE IIT, Kharagpur 3 Version 2 EE IIT, Kharagpur 4

 2
Solution: The total utilization due to the foreground tasks: i=1¦ ei  pi 1020 + 2050 where ui is average utilization due to the task Ti and n is the total number of tasks in the task
set. Expr. 3.2 is both a necessary and a sufficient condition for a set of tasks to be EDF
90100.
schedulable.
This implies that the fraction of time remaining for the background task to execute is given
EDF has been proven to be an optimal uniprocessor scheduling algorithm. This means that, if
by:
2 a set of tasks is not schedulable under EDF, then no other scheduling algorithm can feasibly
1i=1¦ ei  pi 10100. schedule this task set. In the simple schedulability test for EDF (Expr. 3.2), we assumed that the
Therefore, the background task gets 1 millisecond every 10 milliseconds. Thus, the period of each task is the same as its deadline. However, in practical problems the period of a
background task would take 10 (1001) = 1000 milliseconds to complete. task may at times be different from its deadline. In such cases, the schedulability test needs to be
changed. If pi > di, then each task needs ei amount of computing time every min(pi, di)
Example 3: Suppose in Example 1, an overhead of 1 msec on account of every context duration of time. Therefore, we can rewrite Expr. 3.2 as:
n
switch is to be taken into account. Compute the completion time of TB. B

i=1
¦ ei  min(pi, di) d 1 … (3.3/2.9)
However, if pi  di, it is possible that a set of tasks is EDF schedulable, even when the task
Context Switching Time set fails to meet the Expr 3.3. Therefore, Expr 3.3 is conservative when pi  di, and is not a
necessary condition, but only a sufficient condition for a given task set to be EDF schedulable.
Back Foreground Back Foreground
Foreground ground
ground
Example 4: Consider the following three periodic real-time tasks to be scheduled using EDF
01 51 52 100 Time in milli secs on a uniprocessor: T1 = (e1 10, p1 20), T2 = (e2 5, p2 50), T3 = (e3 10, p3 35). Determine
whether the task set is schedulable.
Fig. 30.1 Task Schedule for Example 3

Solution: The very first time the foreground task runs (at time 0), it incurs a context Solution: The total utilization due to the three tasks is given by:
3
switching overhead of 1 msec. This has been shown as a shaded rectangle in Fig. 30.1. i=1
¦ ei  pi 1020 + 550 + 1035 0.89
Subsequently each time the foreground task runs, it preempts the background task and incurs This is less than 1. Therefore, the task set is EDF schedulable.
one context switch. On completion of each instance of the foreground task, the background Though EDF is a simple as well as an optimal algorithm, it has a few shortcomings
task runs and incurs another context switch. With this observation, to simplify our which render it almost unusable in practical applications. The main problems with EDF are
computation of the actual completion time of TB, we can imagine that the execution time of
B
discussed in Sec. 3.4.3. Next, we discuss the concept of task priority in EDF and then discuss
every foreground task is increased by two context switch times (one due to itself and how EDF can be practically implemented.
the other due to the background task running after each time it completes). Thus, the
net effect of context switches can be imagined to be causing the execution time of 1.4.1. Is EDF Really a Dynamic Priority Scheduling Algorithm?
the foreground task to increase by 2 context switch times, i.e. to 52 milliseconds from
50 milliseconds. This has pictorially been shown in Fig. 30.1. We stated in Sec 3.3 that EDF is a dynamic priority scheduling algorithm. Was it after all
Now, using Expr. 2.7, we get the time required by the background task to complete: correct on our part to assert that EDF is a dynamic priority task scheduling algorithm? If EDF
1000/(152100) 2083.4 milliseconds were to be considered a dynamic priority algorithm, we should be able determine the precise
In the following two sections, we examine two important event-driven schedulers: EDF priority value of a task at any point of time and also be able to show how it changes with time. If
(Earliest Deadline First) and RMA (Rate Monotonic Algorithm). EDF is the optimal dynamic we reflect on our discussions of EDF in this section, EDF scheduling does not require any
priority real-time task scheduling algorithm and RMA is the optimal static priority real-time task priority value to be computed for any task at any time. In fact, EDF has no notion of a priority
scheduling algorithm. value for a task. Tasks are scheduled solely based on the proximity of their deadline.
However, the longer a task waits in a ready queue, the higher is the chance (probability) of
1.4. Earliest Deadline First (EDF) Scheduling being taken up for scheduling. So, we can imagine that a virtual priority value associated with a
task keeps increasing with time until the task is taken up for scheduling. However, it is important
In Earliest Deadline First (EDF) scheduling, at every scheduling point the task having the to understand that in EDF the tasks neither have any priority value associated with them, nor
shortest deadline is taken up for scheduling. This basic principles of this algorithm is very does the scheduler perform any priority computations to determine the schedulability of a task at
intuitive and simple to understand. The schedulability test for EDF is also simple. A task set is either run time or compile time.
schedulable under EDF, if and only if it satisfies the condition that the total processor utilization
due to the task set is less than 1. For a set of periodic real-time tasks {T1, T2, …, Tn}, EDF 1.4.2. Implementation of EDF
schedulability criterion can be expressed as:
n n
i=1
¦ ei  pi i=1¦ ui d 1 A naive implementation of EDF would be to maintain all tasks that are ready for execution in
… (3.2/2.8) a queue. Any freshly arriving task would be inserted at the end of the queue. Every node in the

Version 2 EE IIT, Kharagpur 5 Version 2 EE IIT, Kharagpur 6

queue would contain the absolute deadline of the task. At every preemption point, the entire Resource Sharing Problem: When EDF is used to schedule a set of real-time tasks,
queue would be scanned from the beginning to determine the task having the shortest deadline. unacceptably high overheads might have to be incurred to support resource sharing among
However, this implementation would be very inefficient. Let us analyze the complexity of this the tasks without making tasks to miss their respective deadlines. We examine this issue in
scheme. Each task insertion will be achieved in O(1) or constant time, but task selection (to run some detail in the next lesson.
next) and its deletion would require O(n) time, where n is the number of tasks in the queue.
A more efficient implementation of EDF would be as follows. EDF can be implemented by Efficient Implementation Problem: The efficient implementation that we discussed in Sec.
maintaining all ready tasks in a sorted priority queue. A sorted priority queue can efficiently be 3.4.2 is often not practicable as it is difficult to restrict the number of tasks with
implemented by using a heap data structure. In the priority queue, the tasks are always kept distinct deadlines to a reasonable number. The efficient implementation that achieves
sorted according to the proximity of their deadline. When a task arrives, a record for it can be O(1) overhead assumes that the number of relative deadlines is restricted. This may be
inserted into the heap in O(log2 n) time where n is the total number of tasks in the priority queue. unacceptable in some situations. For a more flexible EDF algorithm, we need to keep the
At every scheduling point, the next task to be run can be found at the top of the heap. When a tasks ordered in terms of their deadlines using a priority queue. Whenever a task arrives, it is
task is taken up for scheduling, it needs to be removed from the priority queue. This can be inserted into the priority queue. The complexity of insertion of an element into a priority
achieved in O(1) time. queue is of the order log2 n, where n is the number of tasks to be scheduled. This represents
A still more efficient implementation of the EDF can be achieved as follows under the a high runtime overhead, since most real-time tasks are periodic with small periods and strict
assumption that the number of distinct deadlines that tasks in an application can have are deadlines.
restricted. In this approach, whenever task arrives, its absolute deadline is computed from its
release time and its relative deadline. A separate FIFO queue is maintained for each distinct 1.5. Rate Monotonic Algorithm(RMA)
relative deadline that tasks can have. The scheduler inserts a newly arrived task at the end of the
corresponding relative deadline queue. Clearly, tasks in each queue are ordered according to We had already pointed out that RMA is an important event-driven scheduling algorithm.
their absolute deadlines. This is a static priority algorithm and is extensively used in practical applications. RMA assigns
To find a task with the earliest absolute deadline, the scheduler only needs to search priorities to tasks based on their rates of occurrence. The lower the occurrence rate of a task, the
among the threads of all FIFO queues. If the number of priority queues maintained by the lower is the priority assigned to it. A task having the highest occurrence rate (lowest period) is
scheduler is Q, then the order of searching would be O(1). The time to insert a task would also accorded the highest priority. RMA has been proved to be the optimal static priority real-time
be O(1). task scheduling algorithm.
In RMA, the priority of a task is directly proportional to its rate (or, inversely proportional to its
1.4.3. Shortcomings of EDF period). That is, the priority of any task Ti is computed as: priority k  pi, where pi is the
period of the task Ti and k is a constant. Using this simple expression, plots of priority values of
In this subsection, we highlight some of the important shortcomings of EDF when used for tasks under RMA for tasks of different periods can be easily obtained. These plots have been
scheduling real-time tasks in practical applications. shown in Fig. 30.10(a) and Fig. 30.10(b). It can be observed from these figures that the priority
of a task increases linearly with the arrival rate of the task and inversely with its period.
Transient Overload Problem: Transient overload denotes the overload of a system for a
very short time. Transient overload occurs when some task takes more time to
complete than what was originally planned during the design time. A task may take
longer to complete due to many reasons. For example, it might enter an infinite loop or
encounter an unusual condition and enter a rarely used branch due to some abnormal input Priority Priority
values. When EDF is used to schedule a set of periodic real-time tasks, a task overshooting
its completion time can cause some other task(s) to miss their deadlines. It is usually very
difficult to predict during program design which task might miss its deadline when a transient
overload occurs in the system due to a low priority task overshooting its deadline. The only Rate Period
prediction that can be made is that the task (tasks) that would run immediately after (b)
(a)
the task causing the transient overload would get delayed and might miss its (their)
respective deadline(s). However, at different times a task might be followed by different Fig. 30.2 Priority Assignment to Tasks in RMA
tasks in execution. However, this lead does not help us to find which task might miss its
deadline. Even the most critical task might miss its deadline due to a very low priority task 1.5.1. Schedulability Test for RMA
overshooting its planned completion time. So, it should be clear that under EDF any amount
of careful design will not guarantee that the most critical task would not miss its deadline An important problem that is addressed during the design of a uniprocessor-based real-time
under transient overload. This is a serious drawback of the EDF scheduling algorithm. system is to check whether a set of periodic real-time tasks can feasibly be scheduled under
RMA. Schedulability of a task set under RMA can be determined from a knowledge of the

Version 2 EE IIT, Kharagpur 7 Version 2 EE IIT, Kharagpur 8

worst-case execution times and periods of the tasks. A pertinent question at this point is how can
a system developer determine the worst-case execution time of a task even before the system is 1
developed. The worst-case execution times are usually determined experimentally or through Ȉ ui
simulation studies.
The following are some important criteria that can be used to check the schedulability of a set 0.692
of tasks set under RMA.
(1,0)
1.5.1.1 Necessary Condition Number of tasks

A set of periodic real-time tasks would not be RMA schedulable unless they satisfy the Fig. 30.3 Achievable Utilization with the Number of Tasks under RMA
following necessary condition:
n n Evaluation of Expr. 3.4 when n o f involves an indeterminate expression of the type f.0.
¦ ei  pi i=1¦ ui d 1
i=1 By applying L’Hospital’s rule, we can verify that the right hand side of the expression evaluates
where ei is the worst case execution time and pi is the period of the task Ti, n is the number of to loge2 0.692. From the above computations, it is clear that the maximum CPU utilization that
tasks to be scheduled, and ui is the CPU utilization due to the task Ti. This test simply expresses can be achieved under RMA is 1. This is achieved when there is only a single task in the system.
the fact that the total CPU utilization due to all the tasks in the task set should be less than 1. As the number of tasks increases, the achievable CPU utilization falls and as n o f, the
achievable utilization stabilizes at loge2, which is approximately 0.692. This is pictorially shown
1.5.1.2 Sufficient Condition in Fig. 30.3. We now illustrate the applicability of the RMA schedulability criteria through a few
examples.
The derivation of the sufficiency condition for RMA schedulability is an important result and
was obtained by Liu and Layland in 1973. A formal derivation of the Liu and Layland’s results 1.5.2. Examples
from first principles is beyond the scope of this discussion. We would subsequently refer to the
sufficiency as the Liu and Layland’s condition. A set of n real-time periodic tasks are Example 5: Check whether the following set of periodic real-time tasks is schedulable under
schedulable under RMA, if
n RMA on a uniprocessor: T1 = (e1 20, p1 100), T2 = (e2 30, p2 150), T3 = (e3 60, p3 200).
i=1
¦ ui d n(21/n  1) (3.4/2.10)
where ui is the utilization due to task Ti. Let us now examine the implications of this result. If a Solution: Let us first compute the total CPU utilization achieved due to the three given
set of tasks satisfies the sufficient condition, then it is guaranteed that the set of tasks would be tasks.
3
RMA schedulable. ¦ ui 20100 + 30150 + 60200 0.7
i=1
Consider the case where there is only one task in the system, i.e. n = 1.
This is less than 1; therefore the necessary condition for schedulability of the tasks is
Substituting n 1 in Expr. 3.4, we get, satisfied. Now checking for the sufficiency condition, the task set is schedulable under RMA
1 1
i=1
¦ ui d 1(21/1  1) or i=1¦ ui d 1 if Liu and Layland’s condition given by Expr. 3.4 is satisfied Checking for satisfaction of
Similarly for n = 2, we get, Expr. 3.4, the maximum achievable utilization is given by:
2 2 13
i=1
¦ ui d 2(21/2  1) or i=1¦ ui d 0.828 3(2  1) 0.78
For n = 3, we get, The total utilization has already been found to be 0.7. Now substituting these in Liu and
3 3 Layland’s criterion:
i=1
¦ ui d 3(21/3  1) or i=1¦ ui d 0.78 3 13
For n o f, we get, i=1
¦ ui d 3(2  1)
f f Therefore, we get 0.7 < 0.78.
i=1
¦ ui d 3(21/f  1) or i=1¦ ui d f.0
Expr. 3.4, a sufficient condition for RMA schedulability, is satisfied. Therefore, the task set
is RMA-schedulable

Example 6: Check whether the following set of three periodic real-time tasks is
schedulable under RMA on a uniprocessor: T1 = (e1 20, p1 100), T2 = (e2 30, p2 150), T3
= (e3 90, p3 200).

Solution: Let us first compute the total CPU utilization due to the given task set:
3
i=1
¦ ui 20100 + 30150 + 90200 0.7

Version 2 EE IIT, Kharagpur 9 Version 2 EE IIT, Kharagpur 10

 Now checking for Liu and Layland criterion: The worst case response time for a task occurs when it is in phase with its higher
3
i=1
¦ ui d 0.78
To see why this statement must be true, consider the following statement. Under RMA whenever
Since 0.85 is not d 0.78, the task set is not RMA-schedulable.
a higher priority task is ready, the lower priority tasks can not execute and have to wait. This
Liu and Layland test (Expr. 2.10) is pessimistic in the following sense.
implies that, a lower priority task will have to wait for the entire duration of execution of each
higher priority task that arises during the execution of the lower priority task. More number of
If a task set passes the Liu and Layland test, then it is guaranteed to be RMA schedulable. On instances of a higher priority task will occur, when a task is in phase with it, when it is in phase
the other hand, even if a task set fails the Liu and Layland test, it may still be RMA with it rather than out of phase with it. This has been illustrated through a simple example in Fig.
schedulable. 30.4. In Fig. 30.4(a), a higher priority task T1=(10,30) is in phase with a lower priority task
T2=(60,120), the response time of T2 is 90 msec. However, in Fig. 30.4(b), when T1 has a 20
It follows from this that even when a task set fails Liu and Layland’s test, we should not
msec phase, the response time of T2 becomes 80. Therefore, if a task meets its first deadline
conclude that it is not schedulable under RMA. We need to test further to check if the task set is
under zero phasing, then they it will meet all its deadlines.
RMA schedulable. A test that can be per- formed to check whether a task set is RMA
schedulable when it fails the Liu and Layland test is the Lehoczky’s test. Lehoczky’s test has
Example 7: Check whether the task set of Example 6 is actually schedulable under RMA.
been expressed as Theorem 3.
Solution: Though the results of Liu and Layland’s test were negative as per the results
1.5.3. Theorem 3 of Example 6, we can apply the Lehoczky test and observe the following:

A set of periodic real-time tasks is RMA schedulable under any task phasing, iff all the tasks For the task T1: e1 < p1 holds since 20 msec < 100 msec. Therefore, it would meet its first
meet their respective first deadlines under zero phasing. deadline (it does not have any tasks that have higher priority).

Deadline for T1

T1 T2 T1 T2 T1 T2 T1

10 30 40 60 70 90 time in msec 20 100

(a) T1 is in phase with T2 (a) T1 meets its first deadline
Deadline for T2

T1 T2
T2 T1 T2 T1 T2
20 30 50 60 80 time in msec 20 50 150
(b) T2 meets its first deadline
(b) T1 has a 20 msec phase with respect to T2 Deadline for T3

Fig. 30.4 Worst Case Response Time for a Task Occurs When It is in Phase
with Its Higher Priority Tasks
T1 T2 T3 T1 T3 T2 T3
A formal proof of this Theorem is beyond the scope of this discussion. However, we provide an
intuitive reasoning as to why Theorem 3 must be true. Intuitively, we can understand this result 20 50 100 120 150 180 190 200
from the following reasoning. First let us try to understand the following fact. (c) T3 meets its first deadline

Fig. 30.5 Checking Lehoczky’s Criterion for Tasks of Example 7

Version 2 EE IIT, Kharagpur 11 Version 2 EE IIT, Kharagpur 12

 For the task T2: T1 is its higher priority task and considering 0 phasing, it would occur once task periods equal their respective deadlines, i.e. pi = di. If pi < di, then the Expr. 3.6 would need
before the deadline of T2. Therefore, (e1 + e2) < p2 holds, since 20 + 30 = 50 msec < 150 modifications as follows.
i-1
msec. Therefore, T2 meets its first deadline. ei + k=1¦ ªdi  pkº ek d di …(3.7/2.13)
Note that even if Expr. 3.7 is not satisfied, there is some possibility that the task set
For the task T3: (2e1 + 2e2 + e3) < p3 holds, since 2 20 + 2 30 + 90 = 190msec < 200 msec. may still be schedulable. This might happen because in Expr. 3.7 we have considered zero
phasing among all the tasks, which is the worst case. In a given problem, some tasks may have
We have considered 2 e1 and 2 e2 since T1 and T2 occur twice within the first deadline of non-zero phasing. Therefore, even when a task set narrowly fails to meet Expr 3.7, there is some
T3. Therefore, T3 meets its first deadline. So, the given task set is schedulable under RMA. The chance that it may in fact be schedulable under RMA. To understand why this is so, consider a
schedulability test for T3 has pictorially been shown in Fig. 30.5. Since all the tasks meet their task set where one particular task Ti fails Expr. 3.7, making the task set not schedulable. The
first deadlines under zero phasing, they are RMA schedulable according to Lehoczky’s results. task misses its deadline when it is in phase with all its higher priority task. However, when the
task has non-zero phasing with at least some of its higher priority tasks, the task might
actually meet its first deadline contrary to any negative results of the expression 3.7.
Let us now consider two examples to illustrate the applicability of the Lehoczky’s results.

Ti(1) Example 8: Consider the following set of three periodic real-time tasks: T1 (10,20),
T2 (15,60), T3 (20,120) to be run on a uniprocessor. Determine whether the task set is
schedulable under RMA.
T1(1) T1(2) T1(3)
Solution: First let us try the sufficiency test for RMA schedulability. By Expr. 3.4 (Liu and
Layland test), the task set is schedulable if ¦ ui d 0.78.
¦ ui = 1020 + 1560 + 20120 = 0.91
Fig. 30.6 Instances of T1 over a single instance of Ti
This is greater than 0.78. Therefore, the given task set fails Liu and Layland test. Since Expr.
Let us now try to derive a formal expression for this important result of Lehoczky. Let {T1, 3.4 is a pessimistic test, we need to test further.
T2, …,Ti} be the set of tasks to be scheduled. Let us also assume that the tasks have been ordered Let us now try Lehoczky’s test. All the tasks T1, T2, T3 are already ordered in decreasing
in descending order of their priority. That is, task priorities are related as: pr(T1) > pr(T2) > … > order of their priorities.
Testing for task T1:
pr(Ti), where pr(Ti) denotes the priority of the task Ti. Observe that the task T1 has the highest
priority and task Ti has the least priority. This priority ordering can be assumed without any loss Since e1 (10 msec) is less than d1 (20 msec), T1 would meet its first deadline.
of generalization since the required priority ordering among an arbitrary collection of tasks can Testing for task T2:
always be achieved by a simple renaming of the tasks. Consider that the task Ti arrives at the 15 + ª6020º 10 d 60 or 15 + 30 = 45 d 60 msec
time instant 0. Consider the example shown in Fig. 30.6. During the first instance of the task Ti, The condition is satisfied. Therefore, T2 would meet its first deadline.
three instances of the task T1 have occurred. Each time T1 occurs, Ti has to wait since T1 has Testing for Task T3:
higher priority than Ti. 20 + ª12020º 10 + ª12060º 15 = 20 + 60 + 30 = 110 msec
Let us now determine the exact number of times that T1 occurs within a single instance of Ti. This is less than T3’s deadline of 120. Therefore T3 would meet its first deadline.
This is given by ªpi  p1º. Since T1’s execution time is e1, then the total execution time required Since all the three tasks meet their respective first deadlines, the task set is RMA schedulable
due to task T1 before the deadline of Ti is ªpi  p1º e1. This expression can easily be generalized according to Lehoczky’s results.
to consider the execution times all tasks having higher priority than Ti (i.e. T1, T2, …, Ti1).
Example 9: RMA is used to schedule a set of periodic hard real-time tasks in a system. Is it
Therefore, the time for which Ti will have to wait due to all its higher priority tasks can be
possible in this system that a higher priority task misses its deadline, whereas a lower
expressed as:
i-1 priority task meets its deadlines? If your answer is negative, prove your denial. If your
k=1
¦ ªpi  pkº ek …(3.5/2.11) answer is affirmative, give an example involving two or three tasks scheduled using RMA
Expression 3.5 gives the total time required to execute Ti’s higher priority tasks for which Ti where the lower priority task meets all its deadlines whereas the higher priority task misses
would have to wait. So, the task Ti would meet its first deadline, iff its deadline.
i-1
ei + k=1¦ ªpi  pkº ek d pi …(3.6/2.12)
That is, if the sum of the execution times of all higher priority tasks occurring before Ti’s first Solution: Yes. It is possible that under RMA a higher priority task misses its deadline where
deadline, and the execution time of the task itself is less than its period pi, then Ti would as a lower priority task meets its deadline. We show this by constructing an example.
complete before its first deadline. Note that in Expr. 3.6, we have implicitly assumed that the Consider the following task set: T1 = (e1 15, p1 20), T2 = (e2 6, p2 35), T3 = (e3 3,
p3 100). For the given task set, it is easy to observe that pr(T1) > pr(T2) > pr(T3). That is, T1,
T2, T3 are ordered in decreasing order of their priorities.
Version 2 EE IIT, Kharagpur 13 Version 2 EE IIT, Kharagpur 14
 For this task set, T3 meets its deadline according to Lehoczky’s test since However, since the task set is harmonically related, pi can be written as m pk for some m.
e3 + ªp3  p2º e2 + ªp3  p1º e1 = 3 + ( ª10035º 6) + ( ª10020º Using this, ªpi  pkº = pi  pk. Now, Expr. 3.6 can be written as:
15) i-1
ei + k=1¦ (pi  pk) ek d pi
= 3 + (3 6) + (5 15) = 96 d 100 msec. n-1
But, T2 does not meet its deadline since For Ti = Tn, we can write, en + k=1¦ (pn  pk) ek d pn.
e2 + ªp2  p1º e1 = 6 + ( ª3520º 15) = 6 + (2 15) = 36 msec. Dividing both sides of this expression by pn, we get the required result.
n n
This is greater than the deadline of T2 (35 msec). Hence, the task set would be schedulable iff k=1¦ ek  pk d 1 or i=1¦ ui d 1.
As a consequence of the results of Example 9, by observing that the lowest priority task of a
given task set meets its first deadline, we can not conclude that the entire task set is RMA
schedulable. On the contrary, it is necessary to check each task individually as to
1.5.6. Advantages and Disadvantages of RMA
whether it meets its first deadline under zero phasing. If one finds that the lowest
In this section, we first discuss the important advantages of RMA over EDF. We then point
priority task meets its deadline, and concludes that the entire task set would be feasibly
out some disadvantages of using RMA. As we had pointed out earlier, RMA is very commonly
scheduled under RMA, he is likely to be flawed.
used for scheduling real-time tasks in practical applications. Basic support is available in almost
all commercial real-time operating systems for developing applications using RMA. RMA is
1.5.4. Achievable CPU Utilization simple and efficient. RMA is also the optimal static priority task scheduling algorithm. Unlike
EDF, it requires very few special data structures. Most commercial real-time operating systems
Liu and Layland’s results (Expr. 3.4) bounded the CPU utilization below which a task set support real-time (static) priority levels for tasks. Tasks having real-time priority levels are
would be schedulable. It is clear from Expr. 3.4 and Fig. 30.10 that the Liu and Layland arranged in multilevel feedback queues (see Fig. 30.7). Among the tasks in a single level, these
schedulability criterion is conservative and restricts the maximum achievable utilization due to commercial real-time operating systems generally provide an option of either time-slicing and
any task set which can be feasibly scheduled under RMA to 0.69 when the number of tasks in the round-robin scheduling or FIFO scheduling.
task set is large. However, (as you might have already guessed) this is a pessimistic figure. In
fact, it has been found experimentally that for a large collection of tasks with independent RMA Transient Overload Handling: RMA possesses good transient overload handling
periods, the maximum utilization below which a task set can feasibly be scheduled is on the capability. Good transient overload handling capability essentially means that, when a lower
average close to 88%. priority task does not complete within its planned completion time, it can not make any higher
For harmonic tasks, the maximum achievable utilization (for a task set to have a feasible priority task to miss its deadline. Let us now examine how transient overload would affect a set
schedule) can still be higher. In fact, if all the task periods are harmonically related, then even a of tasks scheduled under RMA. Will a delay in completion by a lower priority task affect a
task set having 100% utilization can be feasibly scheduled. Let us first understand when are the higher priority task? The answer is: ‘No’. A lower priority task even when it exceeds its planned
periods of a task set said to be harmonically related. The task periods in a task set are said to be execution time cannot make a higher priority task wait according to the basic principles of RMA
harmonically related, iff for any two arbitrary tasks Ti and Tk in the task set, whenever pi > pk, it  whenever a higher priority task is ready, it preempts any executing lower priority task.
should imply that pi is an integral multiple of pk. That is, whenever pi > pk, it should be possible Thus, RMA is stable under transient overload and a lower priority task overshooting its
to express pi as n pk for some integer n > 1. In other words, pk should squarely divide pi. An completion time can not make a higher priority task to miss its deadline.
example of a harmonically related task set is the following: T1 = (5, 30), T2 = (8, 120), T3 = (12,
60).
It is easy to prove that a harmonically related task set with even 100% utilization can feasibly
be scheduled.

1.5.5. Theorem 4
For a set of harmonically related tasks HS = {Ti}, the RMA schedulability criterion is given
n
by i=1¦ ui d 1.

Proof: Let us assume that T1, T2, …, Tn be the tasks in the given task set. Let us further
assume that the tasks in the task set T1, T2, …, Tn have been arranged in increasing order of their
periods. That is, for any i and j, pi < pj whenever i < j. If this relationship is not satisfied, then a
simple renaming of the tasks can achieve this. Now, according to Expr. 3.6, a task Ti meets its
i-1
deadline, if ei + k=1¦ ªpi  pkº ek d pi.

Version 2 EE IIT, Kharagpur 15 Version 2 EE IIT, Kharagpur 16

 Task Queue Priority Level Thus, T2 will miss its first deadline. Hence, the given task set can not be feasibly scheduled
under RMA.
1 Now let us check the schedulability using DMA:
Under DMA, the priority ordering of the tasks is as follows: pr(T2) > pr(T1) > pr(T3).
Checking for T2:
2 15 msec < 20 msec. Hence, T2 will meet its first deadline.
Checking for T1:
(15 + 10) < 35
3
Hence T1 will meet its first deadline.
Checking for T3:
4 (20 + 30 + 40) < 200
Therefore, T3 will meet its deadline.
Therefore, the given task set is schedulable under DMA but not under RMA.
5
1.7. Context Switching Overhead
6 So far, while determining schedulability of a task set, we had ignored the overheads incurred
on account of context switching. Let us now investigate the effect of context switching overhead
Fig. 30.7 Multi-Level Feedback Queue on schedulability of tasks under RMA.
It is easy to realize that under RMA, whenever a task arrives, it preempts at most one task 
The disadvantages of RMA include the following: It is very difficult to support aperiodic and the task that is currently running. From this observation, it can be concluded that in the worst-
sporadic tasks under RMA. Further, RMA is not optimal when task periods and deadlines differ. case, each task incurs at most two context switches under RMA. One when it preempts the
currently running task. And the other when it completes possibly the task that was preempted or
1.6. Deadline Monotonic Algorithm (DMA) some other task is dispatched to run. Of course, a task may incur just one context switching
overhead, if it does not preempt any task. For example, it arrives when the processor is idle or
RMA no longer remains an optimal scheduling algorithm for the periodic real-time tasks, when a higher priority task was running. However, we need to consider two context switches for
when task deadlines and periods differ (i.e. d iz pi) for some tasks in the task set to be scheduled. every task, if we try to determine the worst-case context switching overhead.
For such task sets, Deadline Monotonic Algorithm (DMA) turns out to be more proficient than For simplicity we can assume that context switching time is constant, and equals ‘c’
RMA. DMA is essentially a variant of RMA and assigns priorities to tasks based on their milliseconds where ‘c’ is a constant. From this, it follows that the net effect of context switches
deadlines, rather than assigning priorities based on task periods as done in RMA. DMA assigns is to increase the execution time ei of each task Ti to at most ei + 2 c. It is therefore clear that in
higher priorities to tasks with shorter deadlines. When the relative deadline of every task is order to take context switching time into consideration, in all schedulability computations, we
proportional to its period, RMA and DMA produce identical solutions. When the relative need to replace ei by ei + 2 c for each Ti.
deadlines are arbitrary, DMA is more proficient than RMA in the sense that it can sometimes
produce a feasible schedule when RMA fails. On the other hand, RMA always fails when DMA Example 11: Check whether the following set of periodic real-time tasks is schedulable
fails. We now illustrate our discussions using an example task set that is DMA schedulable but under RMA on a uniprocessor: T1 = (e1 20, p1 100), T2 = (e2 30, p2 150), T3 = (e3 90,
not RMA schedulable. p3 200). Assume that context switching overhead does not exceed 1 msec, and is to be taken
into account in schedulability computations.
Example 10: Is the following task set schedulable by DMA? Also check whether it is
schedulable using RMA. T1 = (e1 10, p1 50, d1 35), T2 = (e2 15, p2 100, d1 20), T3 = Solution: The net effect of context switches is to increase the execution time of each
(e3 20, p3 200, d1 200) [time in msec]. task by two context switching times. Therefore, the utilization due to the task set is:
3
i=1
¦ ui = 22100 + 32150 + 92200 = 0.89
Solution: First, let us check RMA schedulability of the given set of tasks, by checking the 3
Lehoczky’s criterion. The tasks are already ordered in descending order of their priorities. Since i=1¦ ui > 0.78, the task set is not RMA schedulable according to the Liu and Layland
Checking for T1: test.
10 msec < 35 msec. Hence, T1 would meet its first deadline. Let us try Lehoczky’s test. The tasks are already ordered in descending order of their
Checking for T2: priorities.
(10 + 15) > 20 (exceeds deadline) Checking for task T1:
22 < 100

Version 2 EE IIT, Kharagpur 17 Version 2 EE IIT, Kharagpur 18

 i-1
The condition is satisfied; therefore T1 meets its first deadline. ei + bti + k=1¦ ªpi  pkº ek d pi … (3.9/2.16)
Checking for task T2:
We have so far implicitly assumed that a task undergoes at most a single self
(22 2) + 32 < 150 suspension. However, if a task undergoes multiple self-suspensions, then expression 3.9 we
The condition is satisfied; therefore T2 meets its first deadline. derived above, would need to be changed. We leave this as an exercise for the reader.
Checking for task T3:
(22 2) + (32 2) + 90 < 200. Example 14: Consider the following set of periodic real-time tasks: T1 = (e1 10, p1 50), T2 =
The condition is satisfied; therefore T3 meets its first deadline.
(e2 25, p2 150), T3 = (e3 50, p3 200) [all in msec]. Assume that the self-suspension times of
Therefore, the task set can be feasibly scheduled under RMA even when context switching T1, T2, and T3 are 3 msec, 3 msec, and 5 msec, respectively. Determine whether the tasks
overhead is taken into consideration. would meet their respective deadlines, if scheduled using RMA.

1.8. Self Suspension Solution: The tasks are already ordered in descending order of their priorities. By using the
generalized Lehoczky’s condition given by Expr. 3.9, we get:
A task might cause its self-suspension, when it performs its input/output operations or when it For T1 to be schedulable:
waits for some events/conditions to occur. When a task self suspends itself, the operating system (10 + 3) < 50
removes it from the ready queue, places it in the blocked queue, and takes up the next eligible Therefore T1 would meet its first deadline.
task for scheduling. Thus, self-suspension introduces an additional scheduling point, which we For T2 to be schedulable:
did not consider in the earlier sections. Accordingly, we need to augment our definition of a (25 + 6 + 10 3) < 150
scheduling point given in Sec. 2.3.1 (lesson 2). Therefore, T2 meets its first deadline.
For T3 to be schedulable:
In event-driven scheduling, the scheduling points are defined by task completion, task (50 + 11 + (10 4 + 25 2)) < 200
arrival, and self-suspension events. This inequality is also satisfied. Therefore, T3 would also meet its first deadline.
It can therefore be concluded that the given task set is schedulable under RMA even when
Let us now determine the effect of self-suspension on the schedulability of a task set. Let us self-suspension of tasks is considered.
consider a set of periodic real-time tasks {T1, T2, …, Tn}, which have been arranged in the
increasing order of their priorities (or decreasing order of their periods). Let the worst case
self-suspension time of a task Ti is bi. Let the delay that the task Ti might incur due to its own
1.9. Self Suspension with Context Switching Overhead
self-suspension and the self-suspension of all higher priority tasks be bti. Then, bti can be
Let us examine the effect of context switches on the generalized Lehoczky’s test (Expr.3.9)
expressed as:
i-1 for schedulability of a task set, which takes self-suspension by tasks into account. In a fixed
bti bi + k=1¦ min(ek, bk) …(3.8/2.15) priority preemptable system, each task preempts at most one other task if there is no self
Self-suspension of a higher priority task Tk may affect the response time of a lower priority task suspension. Therefore, each task suffers at most two context switches  one context switch when
Ti by as much as its execution time ek if ek < bk. This worst case delay might occur when the it starts and another when it completes. It is easy to realize that any time when a task self-
higher priority task after self-suspension starts its execution exactly at the time instant the lower suspends, it causes at most two additional context switches. Using a similar reasoning, we can
priority task would have otherwise executed. That is, after self-suspension, the execution of the determine that when each task is allowed to self-suspend twice, additional four context switching
higher priority task overlaps with the lower priority task, with which it would otherwise not have overheads are incurred. Let us denote the maximum context switch time as c. The effect of a
overlapped. However, if ek > bk, then the self suspension of a higher priority task can delay a single self-suspension of tasks is to effectively increase the execution time of each task Ti in the
lower priority task by at most bk, since the maximum overlap period of the execution of a higher worst case from ei to (ei + 4 c). Thus, context switching overhead in the presence of a single
priority task due to self-suspension is restricted to bk. self-suspension of tasks can be taken care of by replacing the execution time of a task Ti by (ei +
Note that in a system where some of the tasks are non preemptable, the effect of self 4 c) in Expr. 3.9. We can easily extend this argument to consider two, three, or more self-
suspension is much more severe than that computed by Expr.3.8. The reason is that, every time suspensions.
a processor self suspends itself, it loses the processor. It may be blocked by a non-preemptive
lower priority task after the completion of self-suspension. Thus, in a non-preemptable scenario,
a task incurs delays due to self-suspension of itself and its higher priority tasks, and also the 1.10.Exercises
delay caused due to non-preemptable lower priority tasks. Obviously, a task can not get delayed
due to the self-suspension of a lower priority non-preemptable task. 1. State whether the following assertions are True or False. Write one or two sentences to
The RMA task schedulability condition of Liu and Layland (Expr. 3.4) needs to change when justify your choice in each case.
we consider the effect of self-suspension of tasks. To consider the effect of self-suspension in a. When RMA is used for scheduling a set of hard real-time periodic tasks, the upper
Expr. 3.4, we need to substitute ei by (ei + bti). If we consider the effect of self-suspension on bound on achievable utilization improves as the number in tasks in the system being
task completion time, the Lehoczky criterion (Expr. 3.6) would also have to be generalized: developed increases.

Version 2 EE IIT, Kharagpur 19 Version 2 EE IIT, Kharagpur 20

 b. If a set of periodic real-time tasks fails Lehoczky’s test, then it can safely be h. Under RMA, the achievable utilization of a set of hard real-time periodic tasks
concluded that this task set can not be feasibly scheduled under RMA. would drop when task periods are multiples of each other compared to the case
c. A time-sliced round-robin scheduler uses preemptive scheduling. when they are not.
d. RMA is an optimal static priority scheduling algorithm to schedule a set of periodic i. RMA scheduling of a set of real-time periodic tasks using the Liu and Layland
real-time tasks on a non-preemptive operating system. criterion might produce infeasible schedules when the task periods are different from
e. Self-suspension of tasks impacts the worst case response times of the individual tasks the task deadlines.
much more adversely when preemption of tasks is supported by the operating system 3. What do you understand by scheduling point of a task scheduling algorithm? How are the
compared to the case when preemption is not supported. scheduling points determined in (i) clock-driven, (ii) event-driven, (iii) hybrid schedulers?
f. When a set of periodic real-time tasks is being scheduled using RMA, it can not be How will your definition of scheduling points for the three classes of schedulers change
the case that a lower priority task meets its deadline, whereas some higher priority when (a) self-suspension of tasks, and (b) context switching overheads of tasks are taken
task does not. into account.
g. EDF (Earliest Deadline First) algorithm possesses good transient overload handling 4. What do you understand by jitter associated with a periodic task? How are these
capability. jitters caused?
h. A time-sliced round robin scheduler is an example of a non-preemptive scheduler. 5. Is EDF algorithm used for scheduling real-time tasks a dynamic priority scheduling
i. EDF algorithm is an optimal algorithm for scheduling hard real-time tasks on algorithm? Does EDF compute any priority value of tasks any time? If you answer
a uniprocessor when the task set is a mixture of periodic and aperiodic tasks. affirmatively, then explain when is the priority computed and how is it computed. If you
j. In a non-preemptable operating system employing RMA scheduling for a set of real- answer in negative, then explain the concept of priority in EDF.
time periodic tasks, self-suspension of a higher priority task (due to I/O etc.) may 6. What is the sufficient condition for EDF schedulability of a set of periodic tasks whose
increase the response time of a lower priority task. period and deadline are different? Construct an example involving a set of three periodic
k. The worst-case response time for a task occurs when it is out of phase with its higher tasks whose period differ from their respective deadlines such that the task set fails the
priority tasks. sufficient condition and yet is EDF schedulable. Verify your answer. Show all your
l. Good real-time task scheduling algorithms ensure fairness to real-time tasks while intermediate steps.
scheduling. 7. A preemptive static priority real-time task scheduler is used to schedule two periodic tasks
2. State whether the following assertions are True or False. Write one or two sentences to T1 and T2 with the following characteristics:
justify your choice in each case.
a. The EDF algorithm is optimal for scheduling real-time tasks in a uniprocessor in a Phase Execution Time Relative Deadline Period
non-preemptive environment. Task
mSec mSec mSec mSec
b. When RMA is used to schedule a set of hard real-time periodic tasks in a
uniprocessor environment, if the processor becomes overloaded any time during T1 0 10 20 20
system execution due to overrun by the lowest priority task, it would be very difficult T2 0 20 50 50
to predict which task would miss its deadline.
c. While scheduling a set of real-time periodic tasks whose task periods are
harmonically related, the upper bound on the achievable CPU utilization is the same Assume that T1 has higher priority than T2. A background task arrives at time 0 and would
for both EDF and RMA algorithms. require 1000mSec to complete. Compute the completion time of the background task
d. In a non-preemptive event-driven task scheduler, scheduling decisions are made assuming that context switching takes no more than 0.5 mSec.
only at the arrival and completion of tasks. 8. Assume that a preemptive priority-based system consists of three periodic foreground tasks
e. The following is the correct arrangement of the three major classes of real-time T1, T2, and T3 with the following characteristics:
scheduling algorithms in ascending order of their run-time overheads.
x static priority preemptive scheduling algorithms Task
Phase Execution Time Relative Deadline Period
x table-driven algorithms mSec mSec mSec mSec
x dynamic priority algorithms T1 0 20 100 100
f. While scheduling a set of independent hard real-time periodic tasks on a T2 0 30 150 150
uniprocessor, RMA can be as proficient as EDF under some constraints on the task T3 0 30 300 300
set.
g. RMA should be preferred over the time-sliced round-robin algorithm for scheduling a
set of soft real-time tasks on a uniprocessor. T1 has higher priority than T2 and T2 has higher priority than T3. A background task Tb
arrives at time 0 and would require 2000mSec to complete. Compute the completion time
of the background task Tb assuming that context switching time takes no more than 1
mSec.

Version 2 EE IIT, Kharagpur 21 Version 2 EE IIT, Kharagpur 22

9. Consider the following set of four independent real-time periodic tasks. Start Time Processing Time Period Deadline
Task
mSec mSec mSec mSec
Start Time Processing Time Period T1 20 25 150 100
Task
msec msec msec
T2 40 7 40 40
T1 20 25 150 T3 60 10 60 50
T2 40 10 50 T4 25 10 30 20
T3 20 15 50
15. Construct an example involving two periodic real-time tasks which can be feasibly
T4 60 50 200
scheduled by both RMA and EDF, but the schedule generated by RMA differs from that
generated by EDF. Draw the two schedules on a time line and highlight how the two
Assume that task T3 is more critical than task T2. Check whether the task set can be schedules differ. Consider the two tasks such that for each task:
feasibly scheduled using RMA. a. the period is the same as deadline
10. What is the worst case response time of the background task of a system in which the b. period is different from deadline
background task requires 1000 msec to complete? There are two foreground tasks. The 16. Can multiprocessor real-time task scheduling algorithms be used satisfactorily in
higher priority foreground task executes once every 100mSec and each time requires distributed systems. Explain the basic difference between the characteristics of a real-time
25mSec to complete. The lower priority foreground task executes once every 50 msec and task scheduling algorithm for multiprocessors and a real-time task scheduling algorithm for
requires 15 msec to complete. Context switching requires no more than 1 msec. applications running on distributed systems.
11. Construct an example involving more than one hard real-time periodic task whose 17. Construct an example involving a set of hard real-time periodic tasks that are not
aggregate processor utilization is 1, and yet schedulable under RMA. schedulable under RMA but could be feasibly scheduled by DMA. Verify your answer,
12. Determine whether the following set of periodic tasks is schedulable on a uniprocessor showing all intermediate steps.
using DMA (Deadline Monotonic Algorithm). Show all intermediate steps in your 18. Three hard real-time periodic tasks T1 = (50, 100, 100), T2 = (70, 200, 200), and T3 = (60,
computation. 400, 400) [time in msec] are to be scheduled on a uniprocessor using RMA. Can the task
set be feasibly be scheduled? Suppose context switch overhead of 1 millisecond is to be
Start Time Processing Time Period Deadline taken into account, determine the schedulability.
Task
mSec mSec mSec mSec 19. Consider the following set of three real-time periodic tasks.
T1 20 25 150 140
T2 60 10 60 40 Start Time Processing Time Period Deadline
Task
mSec mSec mSec mSec
T3 40 20 200 120
T4 25 10 80 25 T1 20 25 150 100
T2 40 10 50 50
13. Consider the following set of three independent real-time periodic tasks. T3 60 50 200 200

Start Time Processing Time Period Deadline a. Check whether the three given tasks are schedulable under RMA. Show all
Task intermediate steps in your computation.
mSec mSec mSec mSec
b. Assuming that each context switch incurs an overhead of 1 msec, determine whether
T1 20 25 150 100 the tasks are schedulable under RMA. Also, determine the average context switching
T2 60 10 50 30 overhead per unit of task execution.
c. Assume that T1, T2, and T3 self-suspend for 10 msec, 20 msec, and 15 msec
T3 40 50 200 150 respectively. Determine whether the task set remains schedulable under RMA. The
context switching overhead of 1 msec should be considered in your result. You can
Determine whether the task set is schedulable on a uniprocessor using EDF. Show assume that each task undergoes self-suspension only once during each of its
all intermediate steps in your computation. execution.
14. Determine whether the following set of periodic real-time tasks is schedulable on a d. Assuming that T1 and T2 are assigned the same priority value, determine the
uniprocessor using RMA. Show the intermediate steps in your computation. Is RMA additional delay in response time that T2 would incur compared to the case when they
optimal when the task deadlines differ from the task periods? are assigned distinct priorities. Ignore the self-suspension times and the context
switch overhead for this part of the question.

Version 2 EE IIT, Kharagpur 23 Version 2 EE IIT, Kharagpur 24