A real time system is a system whose correctness includes its response time as well as its functional correctness. The system does not just run software to plough through the process. it needs to do it in a timely manner. A real time OS is a multitasking OS intended for real time applications. Such applications include embedded systems, industrial robots, spacecraft, industrial control, and scientific research equipment. The purpose of real time systems is to have a physical effect within a chosen time frame. a real time system consists of a controlling system and a controlled system. This interacts with its environment based on information available about the environment. On a real time computer, which controllers a device or process, sensors will provide reading sat periodic levels and the computer must respond by sending signals. There may be unexpected or irregular events and these must also receive a response.
In all cases there will be a time bound within which the response should be delivered. The ability of computer to meet these demands depends on its capacity to perform the necessary computations in the given time bounds. It may be that, even so, the system is unable to meet all possible unexpected demands.
In this case we say that the system lacks sufficient resources: a system with unlimited resources and capable of processing at infinite speed could satisfy any such timing constraint. Failure to meet the timing constraints for a response can have different consequences: there may be no effect at all, or the effect may be minor correctable. Each task occurring in a real time systems has some timing properties.
The timing properties of a given task refer to the following items
Ready time: it is the time at which the task is ready for processing
Deadline: time by which end of execution of the task.
Minimum delay: minimum time that must elapse before execution of the task started.
Execution time: maximum time to complete the process.
Runtime: time to complete the task without interruption
Weight: relative urgency of the task.
Examples for RTOS:
1. Flight control system
2. Intelligent highway system
The basic requirements are described bellow
Multi-tasking and preemptable: the scheduler should have the possibility to pre-empt any process and give the resources to the other process. Multiple levels of interrupts should be supported to handle multiple priority levels.
Dynamic deadline identification: RTOS should identify the task with earliest deadline. To handle this approach is to convert the information into priority levels. The process gets highest priority when it has earliest deadline.
Predictable synchronization: the ability for multiple processes to communicate among themselves in a predictable time. When processes are sharing resources, synchronization is needed. For this many systems are using semaphores. If task is using shared resources other process has to wait for resources. This waiting time is unpredictable. To overcome this problem assigning deadlines with semaphores. Although this is not guarantee, that critical process has access over non critical processes. Other technique is using non blocking synchronization with FIFO queues. The worst case execution time of accessing a shared resource can thus be determined.
Sufficient priority level:
To implement priority based scheduling there has to be sufficient priority levels. Priority inversion occurs, when a highest priority task must wait on a lower priority task to release a resource in turn the lower priority task must wait on a medium priority task. There are 2 solutions for this problem
Priority inheritance protocol
Priority ceiling protocol(pap) both need sufficient priority levels
The timing of API calls must provide expected latencies. There are 3 types of latencies
Task switching latency
Interrupt dispatch latency
Classification of real time scheduling algorithm is shown in below figure
Real-Time Scheduling Algorithms
Figure 1: real time scheduling algorithms
In general real time systems can be divided into 3 classes
Hard real time systems: all tasks must meet their deadlines. if missing a deadline is a fatal error or has disastrous consequences it is considered as hard.
Examples: Breaking system controller, sensory acquisition, lowlevel control, sensory motor planning, nuclear reactor control system.
An example of a hard real time system is a digital fly_by_wire control system of an aircraft
No lateness is accepted under any conditions; else the aircraft is not controllable. If the control system does not respond timely, the result is a hole in the ground
Cost of missing deadline is infinitely high. The lives of people depend on the correct working of the control system of the aircraft.
Firm real time systems:
Only some jobs are allowed to miss their deadline
Example: food processing plant control system.
Soft real time systems: Most of the modern operating systems can serve as the base for soft real time systems. This contains only tasked with no hard timing constraints. this is also known as "best effort" systems. jobs don't have deadlines.if some percentage of missed deadlines is accepted is called as soft.
Multimedia streaming, reading date from keyboard, user command interpretation, message did playing, graphical activities, multimedia transmission and reception, networking, websites and services, telecom(cellular)networks, computer games, dvd player.
Real time systems are less restrictive time by nature. Soft real time systems requires careful design of the scheduler and other related aspects of os. These systems requires that critical processes receive priority over less critical ones. The system interactions must be known as well as the system must have priority scheduling giving the highest priority to real time processes. In addition, the dispatch latency must be small.
Hard real time systems:
Tasks contains with hard timing constraints
These systems requires formal verification of being to always meet its hard deadlines
E.g.: air traffic control, vehicles subsystems control, medical systems
The scheduler then does one of two operations given below
allowance of the process:
Guaranteeing that the process will be completed on time.
Rejection of the process:
This is known as the resource reservation. In this type scheduler knows the exact length of the time of each process the os to perform.
Therefore, each task takes an optimal amount time. These systems are composed of special purpose s/w running on h/w dedicated to their critical process.
The goals of the scheduling a real time system:
Meeting a timing constraints of the system
Preventing simultaneous access to resources and devices
Reduce the cost of the context switches
Reduce the communication cost.
Covering reliability, security, safety.
Given real time systems, the appropriate scheduling approach should be designed based on the properties of the system and the tasks occurring in it. These properties are as follows
1. soft/hard/firm real time tasks
2. periodic/aperiodic/sporadic tasks
3. pre-emptive/nonpreemptive tasks
4. Single processer/ multiprocessor systems
5. Fixed (static) /dynamic priority tasks
6. Static /dynamic systems
7. Independent and dependent tasks
Uniprocesser scheduling algorithms:
These are divided into 2 major subjects
1. Offline: generates scheduling information prior to system execution
2. Online: generates scheduling information
Online again 2 types
Classification of real time systems:
There are 2 different types of execution models:
In the execution time the task may be interrupted and another task run in its place
Can minimize response time to events.
Requires considerable computational resources for scheduling
No other task will be executed till the end of the current executing task.
Task execution times ~= task switching times.
Less computational resources needed for scheduling
Can leads to starvation (not met the deadline) especially for those real time tasks ( or high priority tasks).
The task model for a real time system has 2 types
Every task is cyclic and executes periodically, even I/O is polled. The nature of tasks doesn't vary much between cycles
Aperiodic: most tasks in the system are not periodic.
Basic requirements of RTOS:
Multi threading and preemptibility
Thread synchronization mechanisms
Task switching latency: time to save the context of a current executing task and switch to another task
This is the time elapsed between the execution of the current instruction of the interrupt task and the first instruction in the interrupt handier
Interrupt dispatch latency: this is the time to go from the last instruction in the interrupt handler to the next scheduled to run
Priority inversion: occurs when higher priority task must wait on a low priority task to release a resource
Each resource has an assigned priority
Priority of thread is the highest of all priorities of the resources its holding
The thread holding a resource inherits the priority of the thread blocked on that resource
Pre-emptive scheduling: in a pre-emptive kernel, when the event makes a higher priority task ready to run, the current task is immediate suspended and the high priority task is given contrail of the CPU
Re-entrancy function: can be used by more than 1 task without fear of date corruption.
Non Re-entrancy: cannot be shared by more than 1 task unless mutual exclusion to the functions is ensured by either using a semaphore, by disabling interrupts during critical sections of code Compilers specially designed for embedded software will generally provide reentrantnruntime libraries.
Clock driven scheduling:
All parameters about tasks(release time, execution time, deadline) know in advance.
Schedule can be commuted offline or at some regular time instances.
Minimal runtime overhead.
This is not suitable for many of the applications.
Weighted round robin scheduling:
Tasks scheduled in first in first out manner
Time quantum given to jobs is proportional to its weight
E.g.: high speed switching network
Not suitable for precedence constrained tasks.
E.g.: task 1 run only after task 2.
Processor allocated to processes according to priorities of the task
Processor never left idle when there is a ready task Priorities
Static: at design time
Dynamic: at runtime
Earliest deadline first:
Highest priority is given to the earliest deadline.
Least slack time first
Slack = relative deadline-execution left
Rate monotonic scheduling :
This algorithm for periodic tasks
Tasks priority inversely proportional to its period
The issues with scheduling applicable here
Resources can be allocated in
Weighted round robin
In resources are non perceptible
Real-time scheduling algorithms have been an active topic of research since the late 1960's. Real-time scheduling algorithms work either dynamically or statically. Static scheduling algorithms and techniques have more computer time to devote to scheduling because scheduling is completed before the target system begins. As you might expect, unless all Information about all tasks is known before the system is brought online, the system may not use a static scheduling algorithm.
The dynamic scheduling algorithms are further divided into static priority and dynamic priority. As you might expect, unless all information about all tasks
Stays unchanged throughout each of the tasks' lifetimes, the system may not use a static priority algorithm.
Many dynamic scheduling algorithms studied in research use a simple heuristic.
Example dynamic priority scheduling algorithms are the Earliest Deadline First (EDF) and First- In First-Out (FIFO).
An example of a static priority dynamic scheduling algorithm is the Rate Monotonic (RM). The RM schedules the tasks in order of increasing period, where period is equal to the amount of time between requests. In dynamic scheduling practice, techniques that combine simple heuristic algorithms may be used. The RM is the optimal static priority dynamic real-time scheduling algorithm and "any periodic task set of any size will be able to meet all deadlines all of the time if the rate monotonic
Algorithm is used and the total (processor) utilization is not greater than .693".The application of the RM results have proven to be effective when used in combination with other techniques for scheduling periodic and aperiodic task loads as well.
Real-time Operating Systems:
Real-time Operating Systems are available in open-source and commercially in all price ranges. They differ in size (memory space), and in available options/features. RTOS that are more expensive typically require expensive software tools to complete development of applications.
Examples of RTOS are VxWorks, RTLinux, LynxOS, QNX, and Windows CE.
Embedded platforms are more frequently the target for RTOS. Relatively few RTOS have been written for the PC (there is a version of QNX that runs on the PC). A recently available open-
Source RTOS for PC's is KURT .
An ordinal number which represents the relative importance of a task
The priority of the task is not automatically adjusted by the system. This priority is typically changed by the user.
The priority of the task is automatically adjusted by the system according to the behaviour and the system loading
This imposes an overhead on the system
This can improve response times and eliminate indefinite postponing
Rate monotonic algorithm:
The most commonly used scheduling is static scheduling algorithm is (RM) scheduling algorithm
Schedulable utilization = 0.693
If U < 0.693, schedulability is guaranteed
Tasks may be schedulable even if U > 0.693
The RM algorithm assigns different priorities proposal to the frequency of the tasks
The task with low frequency (shortest) gets high priority and the task with high frequency (long period) get the lowest static priority.
Rate monotonic algorithm is a dynamic pre-emptive algorithm based on static priorities RM algorithm provides no support for the dynamically changing task periods and priorities and tasks that may priority inversion
Priority inversion occurs in RM systems where in order to enforce rate monotonicity; a non critical task with higher frequency of execution is assigned a higher priority than a critical task with lower frequency of execution. A priority ceiling protocol: can be used to counter priority inversion, wherein a task blocking a higher priority task inherits the higher priority for the duration of the blocked task The priority ceiling protocol is used to scheduling a set dependant periodic tasks that share resources protected by semaphores
Earliest deadline first:
Earliest deadline first scheduling can be used for the both static real time scheduling and dynamic real ]time scheduling
A dynamic priority algorithm which uses the deadline of a task as the priority
It gives the highest priority to the earliest deadline task
Execution profile of two periodic tasks
Arrives 0 20 40 â€¦
Execution Time 10 10 10 â€¦
End by 20 40 60 â€¦
Arrives 0 50 100 â€¦
Execution Time 25 25 25 â€¦
End by 50 100 150 â€¦
Minimum laxity firstïŒ(hybrid task)
Laxity is assigned to each of the task in the system. The priority is given according to that. The highest priority is given to the minimum laxity tasks
Laxity is defined as the time difference between completion deadline and its remaining processing time requirement
MLF considers the execution time of a task, which edf does not
A task with zero laxity must be scheduled right away and executed with out pre-emption or it will fail to meet its deadline.
The negative laxity indicates that the task will miss the deadline, no matter when it is picked up for execution. This is the major problem
This is impractical to implement because laxity ties. This will cause system performance to remarkably degrade.
Modified least laxity first:
This is same as llf algorithm. If the laxity tie occurs, the running task continues to run with no pre-emption as far as the deadlines of other tasks are not missed. The mllf algorithm defers the context switching until necessary and it is safe even if laxity tie occurs. It allows the laxity inversion where a task with the latest laxity may not be scheduled immediately. Laxity inversion applies the current running task.
Maximum urgency first algorithm:
This is the combination of static and dynamic priority scheduling, also called mixed priority scheduling. In this each task is given as urgency. Which is combination of both static and dynamic priority? In this algorithm, each task is given an urgency which is defined as a combination of two fixed priorities. Static and dynamic priority that is inversely proposal to the laxity.
The MUF algorithm assigns priorities in 2 phases
Assign static priority to tasks
Deals with the run time behaviour of the muf scheduler.
It sorts the tasks from the shortest period to the longest period. Then it defines the critical set as the first n tasks such that the total cpu load factor doesnot exceed 100%. These tasks are guaranteed not to fail even during a transient overload.
2nd phase: muf scheduler follows an algorithm to select a task for execution.
This is executed when new task is arrived in the queue.
The algorithm is as follows
If there is only 1 task, pick it up and start executr it.
If more than one highly critical task, select the one with the highest dynamic priority. Here least laxity is considered to be the highest priority.
If same laxity exits, select the one with highest user priority
Comparing different algorithms:
RMS may not guarantee schedulability even when U < 1
Low overhead: Priorities do not change for a fixed task set
EDF guarantee schedulability as long as U <= 1
High overhead: Task priorities may change dynamically
Assume a single processor system with 2 tasks
T1= (2, 1)
T2= (5, 2.5)
The total utilization is 1.0 no slack time
This is one case of the cases where EDS works better than RM/DM
H=10 figure 3: timing diagram
Simulating schedules is both tedious and error-proneâ€¦ can we
Demonstrate correctness without working through the schedule?
Yes, in some cases. This is a schedulability test
A test to demonstrate that all deadlines are met, when scheduled using a
- An efficient schedulability test can be used as an on-line acceptance test;
Clearly exhaustive simulation is too expensive
â€¢ Recall: a periodic task Ti is defined by the 4-tuple (Ï†
i, pi, ei, Di)
with utilization ui = ei / pi
â€¢ Total utilization of the system where 0 â‰¤ U â‰¤ 1
â€¢ A scheduling algorithm can feasibly schedule any system of
Periodic tasks on a processor if U is equal to or less than the
Maximum schedulable utilization of the algorithm, UALG
- If UALG = 1, the algorithm is optimal
â€¢ Why is knowing of UALG important? It gives a schedulability test,
Where a system can be validated by showing that U â‰¤ UALG
Schedulable Utilization: EDF
A system of independent preempt able periodic tasks With Di = pi can be feasibly scheduled on one processor using EDF if and only if U â‰¤ 1
- UEDF = 1 for independent, preempt able periodic tasks with Di = pi
result also holds if deadline longer than period: UEDF = 1 for
Independent preempt able periodic tasks with Di â‰¥ pi
- Result is independent of i
- Result can also be shown to apply to strict LST
Schedulable Utilization: EDF
What happens if Di < pi for some i? The test doesn't workâ€¦
- E.g. T1 = (2, 0.8), T2=(5, 2.3, 3)
â€¢ However, there is an alternative test:
- The density of the task, Ti, is ïƒ¤
i = ei / min(Di, pi)
- The density of the system is ïƒ„ï€ = ïƒ¤1 + ïƒ¤2 + â€¦ + ïƒ¤n
- Theorem: A system T of independent, preemptable periodic tasks can be
Feasibly scheduled on one processor using EDT if ïƒ„ï€ â‰¤ 1.
- This is a sufficient condition, but not a necessary condition - i.e. a system
Is guaranteed to be feasible if ïƒ„ï€ â‰¤ 1, but might still be feasible if ïƒ„ï€ > 1
(Would have to run the exhaustive simulation to prove)
J1,1 J1,2 J1,3 J1,4 J2,2
0 1 2 3 4 5 6 7
J2,1 J2,1 J2,2
J2,1 is preempted and misses deadline
Schedulable Utilization of RM
â€¢ Theorem: a system of n independent preemptable periodic tasks
with Di = pi can be feasibly scheduled on one processor using RM
if U â‰¤ nâ‹…(21/n - 1)
- URM(n) = nâ‹…(21/n - 1)
- For large n â†’ï€ ln 2
(i.e. n â†’ï€ 0.69314718056â€¦)
- [Proof in book - complicated!]
- U â‰¤ URM(n) is a sufficient, but not necessary, condition - i.e. a feasible rate
monotonic schedule is guaranteed to exist if U â‰¤ URM(n), but might still be
Possible if U > URM (n)
In this chapter we present the timing diagrams of the schedules provided by some real-time Scheduling algorithms, namely the earliest deadline ï¬rst (EDF), the rate-monotonic (RM), and The least laxity ï¬rst (LLF) algorithms, on two given sets of tasks.
Table 2: The repetition periods, computation times, and deadlines of the tasks
Figure 4: The timing diagram of task denned in Table 2, before scheduling
Figure 5: The timing diagram of task denned in Table 2, before scheduling
Example A.1: Consider a system consisting of three tasks t1,t2 and t3, that have the Repetition periods, computation times, the ï¬rst invocation times and deadlines denned in Table 2. The deadline di, Of each task pi and tasks are preemptive. Figures 4, 5 and 6 present
The timing diagram of each task t1,t2,t3 ,respectively, before scheduling.
Earliest deadline ï¬rst algorithm
Figure 6: The timing diagram of task denned in Table 2, before scheduling
Figure 7: The timing diagram of the schedule provided by any of the earliest deadline ï¬rst, rate monotonic, least laxity ï¬rst algorithms on the tasks set denned in Table 2
Figure 7 presents a portion of the timing diagram of the schedule provided by the EDF Algorithm on the tasks set deï¬ned in Table 2. Between time interval 0 and 17 we observe that no deadline is missed.
ô°« Rate monotonic algorithm
As shown in Figure 7, if we schedule the tasks set by the RM algorithm, no deadline is
Missed between time interval 0 and 17.
ô°« Least laxity ï¬rst algorithm
Similar to the previous two scheduling algorithms, the least laxity ï¬rst algorithm pro-
Videos a schedule such that all deadlines are met between time interval 0 and 17 (see
Table 3: The repetition periods, computation times and deadlines of the tasks t1,t2,t3
Figure 8: The timing diagram of task Defined in Table 3, before scheduling
Figure 9: The timing diagram of task t2 defined in Table 3, before scheduling
Figure 10: The timing diagram of task t3 defined in Table 3, before scheduling
Example A.2: Consider a system consisting of three tasks T1,t2
and t3, that have the Repetition periods, computation times, ï¬rst invocation times and deadlines denned in Table 3. The tasks are pre-emptive. The timing diagrams in Figures 8, 9 and 10 present the timing Diagram of each task t1,t2,t3
, respectively, before scheduling.
Earliest deadline ï¬rst algorithm
As presented in Figure 11, the uniprocessor real-time system consisting of the tasks
set denned in Table 3 is not EDF-schedulable, because while the execution of the ï¬rst
Invocation of the task t2 is not ï¬nished yet, the new invocation of the task arrives. In
other words, an overrun condition happens.
Figure 11: The timing diagram of the schedule provided by the earliest deadline algorithm on the tasks set denned in Table 3
Rate monotonic algorithm
As shown in Figure 12, the uniprocessor real-time system consisting of the tasks set
Defined in Table 3 is not RM-schedulable. The reason is that the deadline of the ï¬rst
Invocation of the task Is missed. The execution of the ï¬rst invocation is required to be
ï¬nished by time 6, but the schedule could not make it.
ô°ƒ Least laxity ï¬rst algorithm
Figure 13 presents a portion of the timing diagram of the schedule provided by the least
laxity ï¬rst algorithm on the tasks set denned in Table 3. As shown in the ï¬gure, the
deadline of the third invocation of the task t1cannot be met. we conclude that the
uniprocessor real-time system consisting of the tasks set denned in Table 3 is not LLF-
Figure 12: The timing diagram of the schedule provided by the rate monotonic algorithm on the tasks set denned in Table 3
Figure 13: The timing diagram of the schedule provided by the least laxity ï¬rst algorithm on the tasks set denned in Table 3
Real time system must satisfy explicit boundary response time constraints, otherwise risk serve consequences including failure. Failure happens when a system cannot satisfy one or more of the requirements laid out in the formal system specifications
for a set of jobs the general scheduling problem asks for an order according to which the tasks are to be executed such that various constants are satisfied. For a given set of tasks, we are asked to devise a feasible allocation. The release time, the deadline, and execution time of the jobs are some of parameters that should be considered for the scheduling. The dead line mat hard, firm, soft. Tasks may have precedence constraints. A task may be periodic, a periodic, or sporadic. The scheduler may be non pre-emptive or pre-emptive. Less critical tasks must allowed to be pre-empted by higher critical ones. The number of processors is another parameter to be considered. The available processer may identical are differs.
In this the concepts of rtos and task and algorithm s are described. Also the concept of utilization bound and optimality criteria, which leads to design appropriate scheduling algorithms, are addressed.
List of open problems:
If real time tasks are hard , pre-emptive and have fixed priorities, periodic, then find the minimum number of processors required to guarantee that all deadlines are met. Some heuristic algorithms have already been proposed, however we believe better algorithms with improved performance can developed in future.
If a system has p identical processors, real time tasks are pre-emptive and have fixed priorities. Hard tasks are periodic. Communication cost is negligible. Find a scheduler that minimizes mean response time while guaranteeing that all deadlines are met.
Suppose there exist m identical processors, real-time tasks are preemptive and have fixe priorities, a penalty function p(ti) is assigned to each soft real-time task, and a reward(ti) is determined for each firm real-time task. Communication cost is negligible. Find a schedule that guarantees all deadlines are met and is p(t)/r(t) minimized.
Consider the conditions of problem (3), except that communication cost is non-trivial. Give a schedule that minimizes the communication cost. Minimizing the number of migrations is one way to reduce the communication cost. Consider the conditions of problem (3), except that communication cost is non trivial. Give a schedule that minimizes the communication cost. Minimizing the number of migrations is one way to reduce the communication cost.
Suppose there exist identical processors, real-time tasks are aperiodic, preemptive, and have fixed priorities. Communication cost is negligible. Find a schedule that not only guarantees that all deadlines are met, but also minimizes mean response time. Find the utilization bound of the algorithm.
Consider the conditions of problem (5), except that tasks are non-preemptive. Find a Schedule that not only guarantees that all deadlines are met, but also minimizes mean response time. Find the utilization bound of the algorithm.
Solve above things when task are dynamic priority.
Solve above when tasks are uniform
We may apply either of the following approaches to solve each of the above problems: the vast majority of the optimization allocating/scheduling problems on real-time systems With more than two processors are NP-hard. In those cases where the problems Listed above are NP-hard, one of the following approaches could be used.
Since the problem is NP-hard, one should strive to obtain a polynomial-time guaranteed approximation Algorithm. Indeed, for some scheduling problems, a heuristic algorithm May be found that runs in polynomial time in the size of the problem and Delivers an approximate solution whose ratio to the optimal solution is guaranteed To be no larger than a given constant or a certain function of the size of the problem. However, for most NP-hard problems guaranteeing such an approximate solution Is itself an NP-complete problem? In this case, the amount of improvement of the Heuristic algorithm with respect to the existing algorithms should be measured via Simulation. A challenging problem in real-time systems theory is calculating the utilization Bounds associated with each allocation/schedule algorithm. The obtained utilization bound allows not only to test the schedulability of any given task set for the scheduling algorithm, but also it allows to quantify the effect of certain parameters such as the number of the processors, the size of the tasks, and the number of Preemptions on schedulability. Calculation of utilization bounds of multiprocessor Scheduling for real-time systems is one of the major research directions that should be further investigated.
If we reduce the scheduling problem into a known NP-complete problem , such as bin-packing or discrete knapsack problem, the existing approximation algorithms for problem can be applied to the scheduling problem. Consider each of the aforementioned problems. The second possibility is developing a polynomial time algorithm that provides an optimal feasible schedule for the problem. The optimality of the algorithm should be proved. We must prove that the algorithm may fail to meet a deadline only if no other scheduling algorithm can meet the deadline. In order to prove optimality, we need to have the utilization bounds associated with the algorithm. The utilization bounds enable an admission controller to decide whether an incoming task can meet its deadline based on utilization-related metrics. In fact, the utilization bounds express the sufficient conditions required for feasibility of the algorithm.