TSEA81 - Datorteknik och realtidssystem

TSEA81 - Computer Engineering and Real-time Systems

Lecture - 7 - Scheduling

This lecture treats methods for determining how tasks shall execute in real-time systems. This is referred to as scheduling.

Scheduling is treated in Chapter 9 in [RT] (the book Realtidsprogrammering).

Real-time requirements

Requirements on real-time systems are often formulated as requirements on response times. There may be requirements on the maximum allowed response time, expressed as the time between an external event, e.g. a measurement from a sensor, and the corresponding related action, e.g. a control action from a controller in a control system. There may also be requirements on the maximum allowed variation in response time, often referred to as jitter.

Requirements on jitter may vary, e.g. for a control system some jitter may be tolerated, since the inherent feedback mechanism in the control system makes it robust towards a certain degree of variations in the sampling time used. For other systems, where safety-critical actions must be taken at precise moments in time, more stringent requirements on jitter apply, and in the most stringent cases a completely deterministic response may be required.

An important requirement for the scheduling method chosen, is therefore that requirements on response times are fulfilled. Another requirement for scheduling may be that the scheduling is fair, in order to prevent situations where certain tasks are not allowed to run for longer time intervals. A task which is not allowed to run as often as desired is said to be exposed to starvation.

Requirements on response times may be expressed as deadlines. A deadline is a time instant when an execution of a task must be finished, often for the purpose of generating a response to an environment, e.g. in the form of a control signal which shall be sent to an external equipment.

There may also be internal requirements, between tasks, e.g. expressed as precedence relations between tasks, stating that tasks must execute in a certain order. This type of requirements may be interpreted as requirements on deadlines, expressed as time instants where one task needs to be finished, for the purpose of letting the next task in a precedence chain execute. This type of internal deadlines may be enforced by the same type of scheduling as is used to fulfil the external deadlines.

Precedence requirements can also be interpreted as requirements on causality, simply saying that one task must execute before another, then leading to a more event-driven view of the scheduling. As an example, in a wireless modem, there may be an external deadline, relative to the time of reception of data, when data must be sent back to a base station. In order to achieve this, several tasks need to execute, with precedence relations between them, e.g. a filtering task must be executed before a demodulation task, which in turn must be executed before a decoding task. Setting up internal deadlines, expressed as time instants, for these tasks, may lead to a controlled execution, where the internal dealines are met. It may however also result in a system with unneccessary periods of idle time, due to time margins being inserted between tasks, e.g. to compensate for variations in task processing time. In contrast, an event-driven approach, where one tasks triggers the next when the execution of the first task is ready, may lead to a system where the resources are utilized more efficiently.

Time-driven scheduling

Scheduling can be performed by taking action at specified instants of time, e.g. to initiate a task switch, or to decide that a task switch is not necessary at the current time. This approach can be referred to as time-driven scheduling.

One method for time driven scheduling is called static cyclic scheduling, also referred to as cyclic executive. Tasks are here treated as functions, which are called at specified time instants. The time instants are oftened determined using a periodic interrupt.

When using static cyclic scheduling, tasks typically have different run frequencies. As an example, there may be a controller task running every millisecond, a measurement task running ten time faster, for the purpose of collecting measurements and performing filtering, and a logging task executed once for every tenth control action.

Periodic execution of tasks, by function calls at specified time intervals, requires that all tasks finish their execution within their assigned time intervals. If this is not the case, it may be necessary to split the task code, so that it is divided into segments. Another alternative is to let a task run as a background task. This means that all tasks required to execute periodically are started, as function calls, when timer interrupts occur. The remaining tasks, arranged as a sequence of funcion calls to the corresponding functions, run when there is no interrupt active. The resulting system then becomes a foreground/background system, where the important tasks are executed when triggered from interrupts, and where the background tasks are executed in a main-loop.

An alternative can be to use a real-time operating system for scheduling of the background tasks, leading to a combined system, where safety-critical tasks are executed in a time-triggered static cyclic scheduling, and where the remaining tasks are scheduled using the method available in the real-time operating system. This approach is taken in the Rubus real-time operating system, available from Arcticus systems.

The execution sequence for tasks used in static cyclic scheduling may be decided in advance, before the system is started. This makes it possible to do off-line analysis of the system's timely properties, and its fulfilment of requirements on response times. This type of analysis may be mandatory for safety-critical systems, e.g. for systems in aircraft and cars.

Another approach to time-driven scheduling is to assign a time quantum to each task. When a task has executed for the duration of its time quantum, a task switch is initiated, and another task is allowed to run. This approach is taken in Linux, and is e.g. discussed in this forum.

Priority based scheduling

Priority based scheduling means that the task with highest priority, among the tasks that are ready for execution, is selected for execution. A task switch is then initiated. A task switch can be initiated from an interrupt, or from a task. A task switch can be initiated from a task e.g. by a function call to a function in a real-time operating system, e.g. for performing a Wait-operation on a semaphore. It can also be initiated by a system call in an operating system, e.g. Linux.

If two tasks are allowed to have the same priority, this must be handled. One possibility is to use a time quantum, as described in Section Time-driven scheduling, to make tasks with equal priorities share the available processor time.

Another possibility is to select the task which has become ready-to-run at the earliest time instant, among the tasks with equal priority, and let this task execute.

A task priority may be static. This means that the priority does not change, as the task executes. Static priorities are often used in real-time operating systems.

As an alternative, dynamic priorities can be used, thereby allowing the task priority to change over time. As an example, it may be advantegous to rise the priority of a task, for the purpose of performing I/O operations, and to lower the priority during a period when the task performes lenghty numerical calculations. Dynamic priorities are often used in operating systems, e.g. Linux.

Preemption

A scheduling method where all task switches are initiated by tasks is referred to as a method that uses non-preemptive scheduling, also known as cooperative scheduling. This means that all task switches are done on a voluntary basis, since the task to be suspended voluntarily suspends itself, allowing another task to run.

Non-preemptive scheduling is less suitable for real-time systems with requirements response times. In this case, it is more advantageous to use preemptive scheduling. In preemptive scheduling, a task switch can be initiated during an interrupt, resulting in the running task being forced to suspend its execution when the interrupt occurs.

Priority based, preemptive scheduling, is a common scheduling method in real-time operating systems.

It can be noted that time-driven scheduling, as described in Section Time-driven scheduling, requires preemption, since a task switch shall be initiated directly when a time quanta expires, which e.g. is detected during the handling of a timer interrupt.

Priority Inversion

Priority based scheduling can result in priority inversion. This means that a task with low priority prevents the execution of a task with higher priority. Priority inversion can occur e.g. when there are three tasks, of which two use a shared resource, and a third task, with a priority between the priorities of the other two tasks, becomes ready for execution when the shared resource is reserved by the task having the lowest priority.

Priority inversion can be prevented using a methodology referred to as priority inheritance, e.g. described in the EE Times article How to use priority inheritance. This article also describes a method referred to as the priority ceiling protocol, which can be used to prevent priority inversion, and which also prevents deadlock, which can occur e.g. if tasks reserve more than one resource each, and two tasks reserve two resources in different order. This situation is described in Section 5.4 in [RT].

Priority inversion can cause problems in real-time systems. A description of a situation where this occurs, which happened on the Mars Rover Pathfinder, is available in an article called What really happened on Mars Rover Pathfinder .

Further information, where the previous article is commented upon, is available via Re: What really happened on Mars? by Glenn Reeves .

Priority inheritance and priority inversion are treated in Section 9.1.1 in [RT].

Periodic tasks

A special class of tasks, which are commonly used in real-time systems, are periodic tasks. A common requirement on periodic tasks is that there are time instants, referred to as deadlines, where the tasks must have finished their ongoing executions, e.g. for the purpose of delivery of a control signal to an external equipment, sending a message on a communication channel, or taking a measurement sample from a physical process. Another example is a clock, which is used in Assignment 2 - Alarm Clock, where it is required that the clock shall finish its executions so that it can start a new execution each second.

When periodic tasks are used in a system with priority-based, preemptive scheduling, e.g. in a real-time operating system, the frequency of the periodic tasks can be used to determine the priorities of the tasks. One method for performing such a priority assignment is referred to as Rate-monotonic scheduling.

The method of Rate-monotonic scheduling implies that priorities for tasks shall be chosen in proportion to the task frequencies, so that tasks executing more often receive higher priorities.

It has been shown, by Liu and Layland, in 1973, that given a set of periodic tasks, with deadlines defined by the ends of their execution periods, independent of each other and not allowed to block e.g. when reserving resources, that if the processor utilization is below a certain bound, then the method of using Rate-monotonic scheduling results is a feasible schedule, in the sense that all tasks will meet their deadlines.

Periodic tasks are treated in Section 9.1.2 in [RT].

Scheduling algorithms

A real-time system can use priority based scheduling, implemented in a real-time operating system where a number of tasks execute. This results in dynamic scheduling, where decisions regarding which task to select for execution at a given time instant are made while the system is running.

It is also possible to use static scheduling, as is the case when the static cyclic scheduling method, described in Section Time-driven scheduling is used.

There is a scheduling method denoted Earliest deadline first, or EDF, where the task which has the shortest remaining time to its next deadline is selected for execution. It is possible to analyze the EDF algorithm, and to show that if the processor utilization is smaller than 100 percent, in a system with periodic and independent tasks not allowed to block, then the EDF algorithm results in a schedulable system, i.e. all tasks will meet their deadlines.

There is an implementation of EDF for the Linux kernel, called SCHED_DEADLINE.

The Rate-monotonic method, described in Section Periodic tasks is also often considered a scheduling algorithm, even though it really is a method for determining priorities for tasks in a system with priority based, preemptive, scheduling.

Scheduling using EDF, and Rate Monotonic Sceduling, are treated in Section 9.2 in [RT].