SECA4007 - REAL TIME SYSTEM DESIGN

UNIT -2 REAL-TIME TASK SCHEDULING

Task Modelling -Types of Schedulers – Preemptive and Non-Preemptive scheduling -

Cyclic schedulers- Rate Monotonic Algorithm (RMA-Earliest Deadline First
Algorithm (EDFA)- Handling Resource sharing among real-time tasks – Priority
Inversion – Priority Inheritance and Priority Ceiling Protocol for Deadlock prevention.

Task Modelling:
The system is subjected to real-time, i.e. response should be guaranteed within a
specified timing constraint or system should meet the specified deadline. For
example flight control systems, real-time monitors, etc.
There are two types of tasks in real-time systems:
1. Periodic tasks
2. Dynamic tasks
 Periodic Tasks: In periodic tasks, jobs are released at regular intervals. A
periodic task is one that repeats itself after a fixed time interval. A periodic task is
denoted by four tuples: Ti = < Φi, Pi, ei, Di >
Where,
 Φi – is the phase of the task. Phase is the release time of the first job
in the task. If the phase is not mentioned then the release time of the first job is
assumed to be zero.
 Pi – is the period of the task i.e. the time interval between the release
times of two consecutive jobs.
 ei – is the execution time of the task.
 Di – is the relative deadline of the task.
For example: Consider the task Ti with period = 5 and execution time = 3
Phase is not given so, assume the release time of the first job as zero. So the job of
this task is first released at t = 0 then it executes for 3s and then the next job is
released at t = 5 which executes for 3s and then the next job is released at t = 10. So
jobs are released at t = 5k where k = 0, 1, . . ., n

Hyper period of a set of periodic tasks is the least common multiple of periods of all
the tasks in that set. For example, two tasks T1 and T2 having period 4 and 5
respectively will have a hyper period, H = lcm(p1, p2) = lcm(4, 5) = 20. The hyper
period is the time after which pattern of job release times starts to repeat.
 Dynamic Tasks: It is a sequential program that is invoked by the occurrence
of an event. An event may be generated by the processes external to the system or
by processes internal to the system. Dynamically arriving tasks can be
categorized on their criticality and knowledge about their occurrence times.
1. Aperiodic Tasks: In this type of task, jobs are released at arbitrary
time intervals i.e. randomly. Aperiodic tasks have soft deadlines or no deadlines.
2. Sporadic Tasks: They are similar to aperiodic tasks i.e. they repeat
at random instances. The only difference is that sporadic tasks have hard
deadlines. A sporadic task is denoted by three tuples: Ti =(ei, gi, Di)
Where
ei – the execution time of the task.
gi – the minimum separation between the occurrence of two consecutive instances
of the task.
Di – the relative deadline of the task.

Jitter: Sometimes actual release time of a job is not known. Only know that ri is in
a range [ ri-, ri+ ]. This range is known as release time jitter. Here ri– is how early a
job can be released and ri+ is how late a job can be released. Only the range [ ei-,
ei+ ] of the execution time of a job is known. Here ei– is the minimum amount of
time required by a job to complete its execution and ei+ is the maximum amount of
time required by a job to complete its execution.
Precedence Constraint of Jobs: Jobs in a task are independent if they can be
executed in any order. If there is a specific order in which jobs in a task have to be
executed then jobs are said to have precedence constraints. For representing
precedence constraints of jobs a partial order relation < is used. This is called
precedence relation. A job Ji is a predecessor of job Jj if Ji < Jj i.e. Jj cannot begin
its execution until Ji completes. Ji is an immediate predecessor of Jj if Ji < Jj and
there is no other job Jk such that Ji < Jk < Jj. Ji and Jj are independent if neither Ji <
Jj nor Jj < Ji is true.

An efficient way to represent precedence constraints is by using a directed graph G

= (J, <) where J is the set of jobs. This graph is known as the precedence graph. Jobs
are represented by vertices of the graph and precedence constraints are represented
using directed edges. If there is a directed edge from Ji to Jj then it means that Ji is
the immediate predecessor of Jj. For example: Consider a task T having 5 jobs J1,
J2, J3, J4, and J5 such that J2 and J5 cannot begin their execution until J1 completes
and there are no other constraints.
The precedence constraints for this example are:
J1 < J2 and J1 < J5

Set representation of precedence graph:

1. < (1) = { }
2. < (2) = {1}
3. < (3) = { }
4. < (4) = { }
5. < (5) = {1}
 Real-time systems are systems that carry real-time tasks. These tasks need to be
performed immediately with a certain degree of urgency. In particular, these tasks
are related to control of certain events (or) reacting to them. Real-time tasks can be
classified as hard real-time tasks and soft real-time tasks.
A hard real-time task must be performed at a specified time which could otherwise
lead to huge losses. In soft real-time tasks, a specified deadline can be missed. This
is because the task can be rescheduled (or) can be completed after the specified time.
In real-time systems, the scheduler is considered as the most important component
which is typically a short-term task scheduler. The main focus of this scheduler is to
reduce the response time associated with each of the associated processes instead of
handling the deadline.
If a preemptive scheduler is used, the real-time task needs to wait until its
corresponding tasks time slice completes. In the case of a non-preemptive scheduler,
even if the highest priority is allocated to the task, it needs to wait until the
completion of the current task. This task can be slow (or) of the lower priority and
can lead to a longer wait.
A better approach is designed by combining both preemptive and non-preemptive
scheduling. This can be done by introducing time-based interrupts in priority based
systems which means the currently running process is interrupted on a time-based
interval and if a higher priority process is present in a ready queue, it is executed by
preempting the current process.
Based on schedulability, implementation (static or dynamic), and the result (self or
dependent) of analysis, the scheduling algorithm are classified as follows.

1. Static table-driven approaches:

These algorithms usually perform a static analysis associated with scheduling and
capture the schedules that are advantageous. This helps in providing a schedule
that can point out a task with which the execution must be started at run time.

2. Static priority-driven preemptive approaches:

Similar to the first approach, these type of algorithms also uses static analysis of
scheduling. The difference is that instead of selecting a particular schedule, it
provides a useful way of assigning priorities among various tasks in preemptive
scheduling.

3. Dynamic planning-based approaches:

Here, the feasible schedules are identified dynamically (at run time). It carries a
certain fixed time interval and a process is executed if and only if satisfies the
time constraint.

4. Dynamic best effort approaches:

These types of approaches consider deadlines instead of feasible schedules.
Therefore the task is aborted if its deadline is reached. This approach is used
widely is most of the real-time systems.
Types of Schedulers:
i)Preemptive Scheduling:
Preemptive scheduling is used when a process switches from running state to ready
state or from the waiting state to ready state. The resources (mainly CPU cycles) are
allocated to the process for a limited amount of time and then taken away, and the
process is again placed back in the ready queue if that process still has CPU burst
time remaining. That process stays in the ready queue till it gets its next chance to
execute.
Algorithms based on preemptive scheduling are: Round Robin (RR),Shortest
Remaining Time First (SRTF), Priority (preemptive version), etc.

ii) Non-Preemptive Scheduling:

Non-preemptive Scheduling is used when a process terminates, or a process
switches from running to the waiting state. In this scheduling, once the resources
(CPU cycles) are allocated to a process, the process holds the CPU till it gets
terminated or reaches a waiting state. In the case of non-preemptive scheduling does
not interrupt a process running CPU in the middle of the execution. Instead, it waits
till the process completes its CPU burst time, and then it can allocate the CPU to
another process.

Algorithms based on non-preemptive scheduling are: Shortest Job First (SJF

basically non preemptive) and Priority (non preemptive version), etc.
 Key Differences Between Preemptive and Non-Preemptive Scheduling:
1. In preemptive scheduling, the CPU is allocated to the processes for a limited
time whereas, in Non-preemptive scheduling, the CPU is allocated to the process
till it terminates or switches to the waiting state.
2. The executing process in preemptive scheduling is interrupted in the middle
of execution when higher priority one comes whereas, the executing process in
non-preemptive scheduling is not interrupted in the middle of execution and waits
till its execution.
3. In Preemptive Scheduling, there is the overhead of switching the process
from the ready state to running state, vise-verse and maintaining the ready queue.
Whereas in the case of non-preemptive scheduling has no overhead of switching
the process from running state to ready state.
4. In preemptive scheduling, if a high-priority process frequently arrives in the
ready queue then the process with low priority has to wait for a long, and it may
have to starve. , in the non-preemptive scheduling, if CPU is allocated to the
process having a larger burst time then the processes with small burst time may
have to starve.
5. Preemptive scheduling attains flexibility by allowing the critical processes to
access the CPU as they arrive into the ready queue, no matter what process is
executing currently. Non-preemptive scheduling is called rigid as even if a critical
process enters the ready queue the process running CPU is not disturbed.
6. Preemptive Scheduling has to maintain the integrity of shared data that’s
why it is cost associative which is not the case with Non-preemptive Scheduling.

Parameter PREEMPTIVE NON-PREEMPTIVE

SCHEDULING SCHEDULING

Basic In this resources(CPU Cycle) Once resources(CPU Cycle) are

are allocated to a process for a allocated to a process, the process
limited time. holds it till it completes its burst
time or switches to waiting state.

Interrupt Process can be interrupted in Process can not be interrupted until

between. it terminates itself or its time is up.

Starvation If a process having high If a process with a long burst time is

priority frequently arrives in running CPU, then later coming
the ready queue, a low priority process with less CPU burst time
process may starve. may starve.

Overhead It has overheads of scheduling It does not have overheads.

the processes.

Flexibility flexible rigid

Cost cost associated no cost associated

CPU In preemptive scheduling, CPU It is low in non preemptive

Parameter PREEMPTIVE NON-PREEMPTIVE
SCHEDULING SCHEDULING

Utilization utilization is high. scheduling.

Waiting Preemptive scheduling waiting Non-preemptive scheduling waiting

Time time is less. time is high.

Response Preemptive scheduling Non-preemptive scheduling

Time response time is less. response time is high.

Examples Examples of preemptive Examples of non-preemptive

scheduling are Round Robin scheduling are First Come First
and Shortest Remaining Time Serve and Shortest Job First.
First.

iii) Cyclic Scheduler:

Cyclic scheduling is simple. Each task is allowed to run to completion before it hands
over to the next. A task cannot be discontinued as it runs.

A diagrammatic example of cyclic scheduling is shown in Figure Here the horizontal

band represents CPU activity and the numbered blocks the tasks as they execute.
Tasks are seen executing in turn, with Task 3 initially the longest and 2 the shortest.
In the third iteration, however, Task 1 takes longer and the overall loop time is
longer.

Rate-Monotonic Algorithm (RMA)/ scheduling:

Rate monotonic scheduling is a priority algorithm that belongs to the static priority
scheduling category of Real Time Operating Systems. It is preemptive in nature.
The priority is decided according to the cycle time of the processes that are involved.
If the process has a small job duration, then it has the highest priority. Thus if a
process with highest priority starts execution, it will preempt the other running
processes. The priority of a process is inversely proportional to the period it will run
for.
A set of processes can be scheduled only if they satisfy the following equation :

Where n is the number of processes in the process set, Ci is the computation time of
the process, Ti is the Time period for the process to run and U is the processor
utilization.
Example:
An example to understand the working of Rate monotonic scheduling algorithm.
 Processes Execution Time (C) Time period (T)

P1 3 20

P2 2 5

P3 2 10

n( 2^1/n - 1 ) = 3 ( 2^1/3 - 1 ) = 0.7977

U = 3/20 + 2/5 + 2/10 = 0.75

It is less than 1 or 100% utilization. The combined utilization of three processes is
less than the threshold of these processes that means the above set of processes are
schedulable and thus satisfies the above equation of the algorithm.

[Link] time
For calculating the Scheduling time of algorithm we have to take the LCM of the
Time period of all the processes. LCM ( 20, 5, 10 ) of the above example is 20. Thus
we can schedule it by 20 time units.
[Link]
As discussed above, the priority will be the highest for the process which has the
least running time period. Thus P2 will have the highest priority, after that P3 and
lastly P1.
P2 > P3 > P1
[Link] and flow

1.
Above figure says that, Process P2 will execute two times for every 5 time units,
Process P3 will execute two times for every 10 time units and Process P1 will
execute three times in 20 time units. This has to be kept in mind for understanding
the entire execution of the algorithm below.
2.
3.
Process P2 will run first for 2 time units because it has the highest priority. After
completing its two units, P3 will get the chance and thus it will run for 2 time units.
4.
As we know that process P2 will run 2 times in the interval of 5 time units and
process P3 will run 2 times in the interval of 10 time units, they have fulfilled the
criteria and thus now process P1 which has the least priority will get the chance and
it will run for 1 time. And here the interval of five time units have completed.
Because of its priority P2 will preempt P1 and thus will run 2 times. As P3 have
completed its 2 time units for its interval of 10 time units, P1 will get chance and it
will run for the remaining 2 times, completing its execution which was thrice in 20
time units.
5.
Now 9-10 interval remains idle as no process needs it. At 10 time units, process P2
will run for 2 times completing its criteria for the third interval ( 10-15 ). Process P3
will now run for two times completing its execution. Interval 14-15 will again
remain idle for the same reason mentioned above. At 15 time unit, process P2 will
execute for two times completing its [Link] is how the rate monotonic
scheduling works.
6.
Conditions :
The analysis of Rate monotonic scheduling assumes few properties that every
process should possess. They are :
1. Processes involved should not share the resources with other processes.
2. Deadlines must be similar to the time periods. Deadlines are deterministic.
3. Process running with highest priority that needs to run, will preempt all the
other processes.
4. Priorities must be assigned to all the processes according to the protocol of
Rate monotonic scheduling.

Advantages :
1. It is easy to implement.
2. If any static priority assignment algorithm can meet the deadlines then rate
monotonic scheduling can also do the same. It is optimal.
3. It consists of calculated copy of the time periods unlike other time-sharing
algorithms as Round robin which neglects the scheduling needs of the processes.

Disadvantages :
1. It is very difficult to support aperiodic and sporadic tasks under RMA.
2. RMA is not optimal when tasks period and deadline differ.
 Earliest Deadline First Algorithm (EDFA):
Earliest Deadline First (EDF) is an optimal dynamic priority scheduling algorithm
used in real-time systems.
It can be used for both static and dynamic real-time scheduling.
EDF uses priorities to the jobs for scheduling. It assigns priorities to the task
according to the absolute deadline. The task whose deadline is closest gets the
highest priority. The priorities are assigned and changed in a dynamic fashion. EDF
is very efficient as compared to other scheduling algorithms in real-time systems. It
can make the CPU utilization to about 100% while still guaranteeing the deadlines
of all the tasks.
EDF includes the kernel overload. In EDF, if the CPU usage is less than 100%, then
it means that all the tasks have met the deadline. EDF finds an optimal feasible
schedule. The feasible schedule is one in which all the tasks in the system are
executed within the deadline. If EDF is not able to find a feasible schedule for all
the tasks in the real-time system, then it means that no other task scheduling
algorithms in real-time systems can give a feasible schedule. All the tasks which are
ready for execution should announce their deadline to EDF when the task becomes
runnable.
EDF scheduling algorithm does not need the tasks or processes to be periodic and
also the tasks or processes require a fixed CPU burst time. In EDF, any executing
task can be preempted if any other periodic instance with an earlier deadline is ready
for execution and becomes active. Preemption is allowed in the Earliest Deadline
First scheduling algorithm.
Example:
Consider two processes P1 and P2.
Let the period of P1 be p1 = 50
Let the processing time of P1 be t1 = 25
Let the period of P2 be period2 = 75
Let the processing time of P2 be t2 = 30

Steps for solution:

1. Deadline pf P1 is earlier, so priority of P1>P2.
2. Initially P1 runs and completes its execution of 25 time.
3. After 25 times, P2 starts to execute until 50 times, when P1 is able to execute.
4. Now, comparing the deadline of (P1, P2) = (100, 75), P2 continues to
execute.
5. P2 completes its processing at time 55.
6. P1 starts to execute until time 75, when P2 is able to execute.
7. Now, again comparing the deadline of (P1, P2) = (100, 150), P1 continues to
execute.
8. Repeat the above steps…
9. Finally at time 150, both P1 and P2 have the same deadline, so P2 will
continue to execute till its processing time after which P1 starts to execute.

Limitations of EDF scheduling algorithm:

 Transient Overload Problem
 Resource Sharing Problem
 Efficient Implementation Problem

Priority Inversion :
Priority inversion is a operating system scenario in which a higher priority process is
preempted by a lower priority process. This implies the inversion of the priorities of
the two processes.

Problems due to Priority Inversion

Some of the problems that occur due to priority inversion are given as follows.
 A system malfunction may occur if a high priority process is not provided the
required resources.
 Priority inversion may also lead to implementation of corrective measures.
These may include the resetting of the entire system.
 The performance of the system can be reduces due to priority inversion. This
may happen because it is imperative for higher priority tasks to execute promptly.
 System responsiveness decreases as high priority tasks may have strict time
constraints or real time response guarantees.
 Sometimes there is no harm caused by priority inversion as the late execution
of the high priority process is not noticed by the system.

Solutions of Priority Inversion

Some of the solutions to handle priority inversion are given as follows.

 Priority Ceiling
All of the resources are assigned a priority that is equal to the highest priority of
any task that may attempt to claim them. This helps in avoiding priority inversion.

 Disabling Interrupts
There are only two priorities in this case i.e. interrupts disabled and preemptible.
So priority inversion is impossible as there is no third option.

 Priority Inheritance
This solution temporarily elevates the priority of the low priority task that is
executing to the highest priority task that needs the resource. This means that
medium priority tasks cannot intervene and lead to priority inversion.
  No blocking
Priority inversion can be avoided by avoiding blocking as the low priority task
blocks the high priority task.

 Random boosting
The priority of the ready tasks can be randomly boosted until they exit the critical
section.

Priority Inheritance Protocol :

Priority Inheritance Protocol (PIP) is a technique which is used for sharing
critical resources among different tasks. This allows the sharing of critical resources
among different without the occurrence of unbounded priority inversions.
Basic Concept of PIP :
The basic concept of PIP is that when a task goes through priority inversion, the
priority of the lower priority task which has the critical resource is increased by the
priority inheritance mechanism. It allows this task to use the critical resource as
early as possible without going through the preemption. It avoids the unbounded
priority inversion.
Working of PIP :
 When several tasks are waiting for the same critical resource, the task which
is currently holding this critical resource is given the highest priority among all
the tasks which are waiting for the same critical resource.
 Now after the lower priority task having the critical resource is given the
highest priority then the intermediate priority tasks can not preempt this task. This
helps in avoiding the unbounded priority inversion.
 When the task which is given the highest priority among all tasks, finishes
the job and releases the critical resource then it gets back to its original priority
value (which may be less or equal).
 If a task is holding multiple critical resources then after releasing one critical
resource it can not go back to it original priority value. In this case it inherits the
highest priority among all tasks waiting for the same critical resource.
If the critical resource is free then
allocate the resource
If the critical resource is held by higher priority task then
wait for the resource
If the critical resource is held by lower priority task
{
lower priority task is provided the highest priority
other tasks wait for the resource
}
Advantages of PIP :
Priority Inheritance protocol has the following advantages:
 It allows the different priority tasks to share the critical resources.
 The most prominent advantage with Priority Inheritance Protocol is that it
avoids the unbounded priority inversion.
 Disadvantages of PIP :
Priority Inheritance Protocol has two major problems which may occur:
 Deadlock –
There is possibility of deadlock in the priority inheritance protocol.
For example, there are two tasks T1 and T2. Suppose T1 has the higher priority than
T2. T2 starts running first and holds the critical resource CR2.

After that, T1 arrives and preempts T2. T1 holds critical resource CR1 and also tries
to hold CR2 which is held by T2. Now T1 blocks and T2 inherits the priority of
T1 according to PIP. T2 starts execution and now T2 tries to hold CR1 which is held
by T1.
Thus, both T1 and T2 are deadlocked.

 Chain Blocking –
When a task goes through priority inversion each time it needs a resource then
this process is called chain blocking.
For example, there are two tasks T1 and T2. Suppose T1 has the higher priority than
T2. T2 holds the critical resource CR1 and CR2. T1 arrives and requests for CR1.
T2 undergoes the priority inversion according to PIP.

Now, T1 request CR2, again T2 goes for priority inversion according to PIP.

Hence, multiple priority inversion to hold the critical resource leads to chain
blocking.

Priority Ceiling Protocol :

Priority Ceiling Protocol is a job task synchronization protocol in a real-time
system that is better than Priority inheritance protocol in many ways. Real-Time
Systems are multitasking systems that involve the use of semaphore variables,
signals, and events for job synchronization.
In Priority ceiling protocol an assumption is made that all the jobs in the system
have a fixed priority. It does not fall into a deadlock state.
The chained blocking problem of the Priority Inheritance Protocol is resolved in the
Priority Ceiling Protocol.
The basic properties of Priority Ceiling Protocols are:
1. Each of the resources in the system is assigned a priority ceiling.
2. The assigned priority ceiling is determined by the highest priority among all
the jobs which may acquire the resource.
3. It makes use of more than one resource or semaphore variable, thus
eliminating chain blocking.
4. A job is assigned a lock on a resource if no other job has acquired lock on
that resource.
5. A job J, can acquire a lock only if the job’s priority is strictly greater than the
priority ceilings of all the locks held by other jobs.
6. If a high priority job has been blocked by a resource, then the job holding
that resource gets the priority of the high priority task.
7. Once the resource is released, the priority is reset back to the original.
8. In the worst case, the highest priority job J1 can be blocked by T lower
priority tasks in the system when J1 has to access T semaphores to finish its
execution.

Priority Scheduling Protocol can be used to tackle the problem of the priority
inversion problem unlike that of Priority Inheritance Protocol. It makes use of
semaphores to share the resources with the jobs in a real-time system.