It’s an ongoing topic of research and the vast majority of assignment/scheduling problems on systems with more than two processors are NP-complete.
2). Basic Terminologies:
Task: Formally speaking a task consumes resources and puts out one or more resources. Each task has resource requirements. All tasks require some execution time on a processor. Tasks may have precedence constraints. Also a task may require a certain amount of memory or access to a bus.Sometimes, a resource must be exclusively held by a task. (i.e. the task must have the sole possession of it).In other cases the resources are non exclusive. The same physical resource may be exclusive or nonexclusive depending on the operation to be performed on it. For instance memory object (or anything else to which the writing is not atomic) that is being read is nonexclusive. However while it is being written into, it must be held exclusively by the writing task.
The release time of a task is the time at which all the data that are required to begin executing are available, and the deadline is the time by which the task must complete its execution .The deadline may be hard or soft depending on the nature of the corresponding task .
The relative deadline of a task is the absolute deadline minus the release time. That is, if task Ti a relative deadline di and is released at time t, it must be executed by time t+di .The absolute deadline is the time by which the task must be completed.So, in this case the absolute deadline is t+di .
Types of Tasks: A task may be periodic, sporadic or aperiodic.
· Periodic Task: A task Ti is periodic if it is released periodically, say every Pi seconds. Pi is called the period of task Ti. The periodicity constraint requires the task to run exactly once every period; it does not require that the tasks be run exactly one period apart. Quite commonly the period of a task is also it’s deadline.
· Sporadic Task: The task is sporadic if it is not periodic but may be invoked at irregular intervals. Sporadic tasks are characterized by an upper bound on the rate at which they may be invoked. This is commonly specified by requiring that the successive invocations of a sporadic task Ti be separated in time by at least t(i) seconds.
· Aperiodic Tasks: Sporadic tasks are sometimes also called aperiodic.Sometimes aperiodic tasks are supposed to be those tasks which are not periodic and which also have no upper bound on their invocation rate.
3) Fixed Priority Scheduling – A Simple Model :
Consider a simple, real-time program which periodically receives inputs from a device every T units of time, computes a result and sends it to another device. Assume that there is a deadline of D time units between the arrival of an input and the dispatch of the corresponding output.
For the program to meet this deadline, the computation of the result must take always place in less than D time units: in other words, for every possible execution path through the program, the time taken for the execution of the section of code between the input and output statements must be less than D time units.
If that section of the program consists solely of assignment statements, it would be possible to obtain a very accurate estimate of its execution time as there will be just one path between the statements. In general, however, a program will have a control structure with several possible execution paths.
For example, consider the following structured if statement:
1 Sensor_Input.Read(Reading);
2 if Reading = 5 then Sensor_Output.Write(20)
3 elseif Reading < 10 then Sensor_Output.Write(25)
4 else ...
5 Sensor_Output.Write( ...)
6 end if;
There are a number of possible execution paths through this statement: e.g. there is one path through lines 1, 2 and 6 and another through lines 1, 2, 3 and 6. Paths will generally differ in the number of boolean tests and assignment statements executed and so, on most computers, will take different execution times.
In some cases, as in the previous example, the execution time of each path can be computed statically, possibly even by a compiler. But there are statements where this is not possible:
Sensor_Input.Read(Reading);
while X > Reading
...
end
Finding all the possible paths through this statement may not be easy: even if it is known that there are m different paths for any one iteration of this while loop, the actual number of iterations will depend on the input value in Reading
Number of paths is finite.
So, after a simple examination of alternative and iterative statements, we can conclude that:
· It is not possible to know in advance exactly how long a program execution will take, but
· It may be possible to find the range of possible values of the execution time.
Rather than deal with all possible execution times, one solution is to use just the longest possible, or worst-case, execution time for the program. If the program will meet its deadline for this worst-case execution, it will meet the deadline for any execution.
Worst-case
Assume that the worst-case upper bound to the execution time can be computed for any real-time program.
Computational model
We can now redefine the simple real-time program as follows: program P receives an event from a sensor every T units of time (i.e. the inter-arrival time is T) and in the worst case an event requires C units of computation time (Figure 2.1).
Assume that the processing of each event must always be completed before the arrival of the next event (i.e. there is no buffering). Let the deadline for completing the computation be D (Figure 2.2).
If D < C, the deadline cannot be met. If T < D, the program must still process each event in a time <T if no events are to be lost. Thus the deadline is effectively bounded by T and we need to handle only those cases where
C <D < T.
Now consider a program which receives events from two sensors (Figure 2.3). Inputs from Sensor 1 come every T1 time units and each needs C1 time units for computation; events from Sensor 2 come every T2 time units and each needs C2 time units. Assume the deadlines are the same as the periods, i.e. T1 time units for Sensor 1 and T2 time units for Sensor 2. Under what conditions will these deadlines be met?
More generally, if a program receives events from n such devices, how can it be determined if the deadline for each device will be satisfied? Before we begin to analyze this problem, we first define a program model and a system
model. This allows us to study the problem of timing analysis in a limited context.
Program model
Assume that a real-time program consists of a number of independent tasks that do not share data or communicate with each other. A task is periodically invoked by the occurrence of a particular event.
_
System model
Assume that the system has one processor; the system periodically receives events from the external environment and these are not buffered. Each event is an invocation for a particular task. Note that events may be periodically produced by the environment or the system may have a timer that periodically creates the events.
Let the tasks of program P be t1, t2,….. tn.
Let the inter-arrival time, or period, for invocations to task ti be Ti and let the computation time for each such invocation be Ci.
We shall use the following terminology:
· A task is released when it has a waiting invocation.
· A task is ready as long as the processing associated with an invocation has not been completed.
· A processor is idle when it is not executing a task.
Static scheduling
One way to schedule the program is to analyze its tasks statically and determine their timing properties. These times can be used to create a fixed scheduling table according to which tasks will be despatched for execution at run-time. Thus, the order of execution of tasks is fixed and it is assumed that their execution times are also fixed.
Typically, if tasks t1, t2,….., tn have periods of T1, T2,….., Tn, the table must cover scheduling for a length of time equal to the least common multiple of the periods, i.e. LCM({T1, T2,…..., Tn}), as that is the time in which each task will have an integral number of invocations. If any of the Ti are co-primes, this length of time can be extremely large so where possible it is advisable to choose values of Ti that are small multiples of a common value.
Advantages:
Static scheduling has the significant advantage that the order of execution of tasks is determined ‘off-line’, before the execution of the program, so the run-time scheduling overheads can be very small.
Disadvantages:
But it has some major disadvantages:
· There is no flexibility at run-time as all choices must be made in advance and must therefore be made conservatively to cater for every possible demand for computation.
· It is difficult to cater for sporadic tasks which may occur occasionally, if ever, but which have high urgency when they do occur.
For example: An alarm condition which requires a system to be shut down within a short interval of time may not occur very often but its task must still be accommodated in the scheduling table so that its deadline will be met if the alarm condition does occur.
Types:
In scheduling terms, a priority is usually a positive integer representing the urgency or importance assigned to an activity. By convention, the urgency is in inverse order to the numeric value of the priority and priority 1 is the highest level of priority. We shall assume here that a task has a single, fixed priority. Consider the following two simple scheduling disciplines:
1) Priority-based execution
When the processor is idle, the ready task with the highest priority is chosen for execution; once chosen, a task is run to completion.
2) Pre-emptive priority-based execution
When the processor is idle, the ready task with the highest priority is chosen for execution; at any time execution of a task can be pre-empted if a task of higher priority becomes ready. Thus, at all times the processor is either idle or executing the ready task with the highest priority.
Example: Consider a program with 3 tasks, t1, t2 and t3, that have the priorities, repetition periods and computation times defined in Figure 2.4. Let the deadline Di for each task ti be Ti. Assume that the tasks are scheduled according to priorities, with no pre-emption.
Priority Period Comp. time
t1 1 7 2
t2 2 16 4
t3 3 31 7
If all three tasks have invocations and are ready at time=0, task t1 will be chosen for execution as it has the highest priority. When it has completed its execution, task t2 will be executed until its completion at time=6.
At that time, only task t3 is ready for execution and it will execute from time=6 to time=13, even though an invocation comes for task t1 at time=7. So there is just one unit of time for task t1 to complete its computation requirement of two units and its next invocation will arrive before processing of the previous invocation is complete.
In some cases, the priorities allotted to tasks can be used to solve such problems; in this case, there is no allocation of priorities to tasks under which task t1 will meet its deadlines. But a simple examination of the timing diagram shows that between time=15 and time=31 (at which the next invocation for task t3 will arrive) the processor is not always busy and task t3 does not need to complete its execution until time=31. If there were some way of making the processor available to tasks t1 and t2 when needed and
then returning it to task t3, they could all meet their deadlines.
This can be done using priorities with pre-emption: execution of task t3 will then be pre-empted at time=7, allowing task t1 to complete its execution at time=9 (Figure 2.5). Process t3 is pre-empted once more by task t1 at time=14 and this is followed by the next execution of task t2 from time=16 to time=20 before task t3 completes the rest of its execution at time=21.
Simple methods of analysis
Timing diagrams provide a good way to visualize and even to calculate the timing properties of simple programs. But they have obvious limits, not least of which is that a very long sheet of paper might be needed to draw some timing diagrams! A better method of analysis would be to derive conditions to be satisfied by the timing properties of a program for it to meet its deadlines.
Let an implementation consist of a hardware platform and the scheduler under which the program is executed. An implementation is called feasible if every execution of the program will meet all its deadlines.
Using the notation of the previous section, in the following sections we shall consider a number of conditions that might be applied. We shall first examine conditions that are necessary to ensure that an implementation is feasible. The aim is to find necessary conditions that are also sufficient, so that if they are satisfied an implementation is guaranteed to be feasible.
Necessary conditions
Condition C1
It is obviously necessary that the computation time for a task is smaller than its period, as, without this condition, its implementation can be trivially shown to be infeasible. However, this condition is not sufficient, as can be seen from the following example.
Example 2.2
Priority Period Comp.time
t1 1 10 8
t2 2 5 3
At time=0, execution of task t1 begins (since it has the higher priority) and this will continue for eight time units before the processor is relinquished; task t2 will therefore miss its first deadline at time=5.
Thus, under Condition C1, it is possible that the total time needed for computation in an interval of time is larger than the length of the interval..
Condition C2
Ci/Ti is the utilization of the processor in unit time at level i. Condition C2 improves on Condition C1 in an important way: not only is the utilization Ci=Ti required to be less than 1 but the sum of this ratio over all tasks is also required not to exceed 1. Thus, taken over a sufficiently long interval, the total time needed for computation must lie within that interval.
This condition is necessary but it is not sufficient. The following example shows an implementation which satisfies Condition C2 but is infeasible.
Priority Period Comp.time
t1 1 6 3
t2 1 9 2
t3 2 11 2
Exercise 2.4.1 Draw a timing diagram for Example 2.3 and show that the deadline for t3 is not met. Condition C2 checks that over an interval of time the arithmetic sum of the utilizations Ci/Ti is < 1. But that is not sufficient to ensure that the total computation time needed for each task, and for all those of higher priority, is also smaller than the period of each task.
Condition C3
Here, Condition C2 has been strengthened so that, for each task, account is taken of the computation needs of all higher priority tasks. Assume that Ti=Tj represents integer division:
· Processing of all invocations at priority levels 1, …, i-1 must be completed in the time Ti-Ci, as this is the ‘free’ time available at that level.
· At each level j, 1< j<i-1 there will be Ti/Tj invocations in the time Ti and each invocation will need a computation time of Cj. Hence, at level j the total computation time needed is Ti/Tj*Cj.
and summing this over all values of j < i will give the total computation needed at level i. Condition C3 says that this must be true for all values of i.
This is another necessary condition. But, once again, it is not sufficient: if Tj > Ti, Condition C3 reduces to Condition C1 which has already been shown to be not sufficient.
There is another problem with Condition C3. It assumes that there are Ti/Tj invocations at level j in the time Ti. If Ti is not exactly divisible by Tj, then either dTi=Tje is an overestimate of the number of invocations or bTi=Tjc is an underestimate. In both cases, an exact condition will be hard to define.To avoid the approximation resulting from integer division, consider an interval Mi which is the least common multiple of all periods up to Ti:
Mi = LCM({T1,T2,….,Ti})
Since Mi is exactly divisible by all Tj; j<i, the number of invocations at any level j within Mi is exactly Mi/Mj .
This leads to the next condition.
Condition C4
Condition C4 is the Load Relation and must be satisfied by any feasible implementation. However, this condition averages the computational requirements over each LCM period and can easily be shown to be not sufficient.
Example 2.4
Priority Period Comp.time
t1 1 12 5
t2 2 4 2
Since the computation time of task t1 exceeds the period of task t2, the implementation is infeasible, though it does satisfy Condition C4.
Condition C4 can, moreover, be simplified to
which is Condition 2 and thus is necessary but not sufficient.
Condition C2 fails to take account of an important requirement of any feasible implementation. Not only must the average load be smaller than 1 over the interval Mi, but the load must at all times be sufficiently small for the deadlines to be met. More precisely, if at any time T there are t time units left for the next deadline at priority level i, the total computation requirement at time T for level i and all higher levels must be smaller than t. Since it averages over the whole of the interval Mi, Condition C2 is unable to take
account of peaks in the computational requirements. But while on the one hand it is necessary that at every instant there is sufficient computation time remaining for all deadlines to be met, it is important to remember that once
a deadline at level i has been met there is no further need to make provision for computation at that level up to the end of the current period. Conditions which average over a long interval may take account of computations over the whole of that interval, including the time after a deadline has been met. For example, in Figure 2.5, task t2 has met its first deadline at time=6 and the computations at level 1 from time=7 to time=9 and from time=14 to time=16 cannot affect t2’s response time, even though they occur before the end of t2’s period at time=16.
A sufficient condition—Rate monotonic scheduling algorithm
So far, we have assumed that priorities are assigned to tasks in some way that characterizes their urgency, but not necessarily in relation to their repetition periods (or deadlines).
Consider, instead, assigning priorities to tasks in rate-monotonic order, i.e. in the inverse order to their repetition periods. Assume that task deadlines are the same as their periods. It can then be shown that if under a rate-monotonic allocation an implementation is infeasible then it will be infeasible under all other similar allocations.
Let time=0 be a critical instant, when invocations to all tasks arrive simultaneously. For an implementation to be feasible, the following condition must hold.
Condition C5
· The first deadline for every task must be met.
· This will occur if the following relation is satisfied:
Example 2.5
Priority Period Comp. time
t1 1 6 4
t2 2 12 4
For n = 2, the upper bound to the utilization
Is 82:84%; for large values of n the limit is 69:31%. This bound is conservative: it is sufficient but not necessary.
In this case (Figure 2.6), the utilization is 100% and thus fails the test. On the other hand, it is quite clear from the graphical analysis that the implementation is feasible as all deadlines are met.
Extending the analysis
The rate-monotonic order provides one way of assigning priorities to tasks. It is easy to think of other ways: e.g. in deadline-monotonic order (if deadlines are smaller than periods). Priorities can also be assigned to tasks in increasing order of slack time, where the slack time for task ti is the difference Ti-Ci between its period and its computation time. All these methods of assignment are static as the priority of a task is never changed during execution. The method of analysis described in this chapter can be used for any static assignment of priorities, but it does not provide a way of choosing between them. So far, we have considered a very simple program model with independent tasks that do not inter-communicate. This has made it possible to schedule tasks without regard to any dependencies between them: any task with some incomplete computation is ready and it can be scheduled whenever it is ready and the processor is free. This type of model can be used for simple data-logging programs but most real-time programs have a more complex structure. If tasks can communicate with each other, using shared memory or by message passing, scheduling becomes far more complicated as it is not only time-driven.
A task can receive a message only after the message has been sent, so a receiving task t2 will not be ready to be scheduled until the corresponding sending task t1 has been scheduled, even if t1 is of lower priority than t2. When analysis shows that no allocation of priorities to tasks is feasible, it may mean that the single available processor is not sufficient to meet the processing load. Solutions are then either to obtain a faster processor (thereby effectively reducing the computation time for each task) or to add one or more processors. With multiple processors, there is the question of exactly how the processing load is divided between the processors. When tasks are statically assigned to processors, the analysis described here can be used for each processor. But two difficult problems are introduced: first, to find a good assignment of tasks to processors so that response time requirements are met, noting that finding the ‘best’ assignment of tasks to processors is in general an NP-complete problem; second, to account for communication between tasks over multiple processors, and without some
Constraints this can make the analysis very difficult.
4) Dynamic Priority Scheduling
Dynamic scheduling of a real-time program requires a sequence of decisions to be taken during execution on the assignment of system resources to transactions. Each decision must be taken without prior knowledge of the needs of future tasks. As in the case of fixed priority scheduling, the system resources include processors, memory and shared data structures; but tasks can now have arbitrary attributes: arrival times, resource requirements, computation times, deadlines and importance values.
Dynamic algorithms are needed for applications where the computing requirements may vary widely, making fixed priority scheduling difficult or inefficient. Many real-time applications require support for dynamic scheduling: e.g. in robotics, where the control subsystem must adapt to a dynamic environment. This kind of scheduling also allows more flexibility in dealing with practical issues, such as the need to alter scheduling decisions based on the occurrence of overloads, e.g. when
· The environment changes,
· There is a burst of task arrivals, or
· A part of the system fails.
In a practical system, it can prove costly to assume that overloads and failures will never occur and, at the same time, be inefficient to determine schedulability or a priori to construct a fixed schedule for a system with such variable properties.
Dynamic scheduling has three basic steps:
· Feasibility checking
· Schedule construction, and
· Dispatching.
Depending on the kind of application for which the system is designed, the programming model adopted and the scheduling algorithm used, all of the steps may not be needed. Often, the boundaries between the steps may also not be clear. A computational transaction will now be assumed to be made up of one or more processes composed in parallel. A process consists of one or more tasks.
Feasibility analysis
It is the process of determining whether the timing requirements of a set of tasks can be satisfied, usually under a given set of resource requirements and precedence constraints. With fixed priority scheduling, feasibility analysis is typically done statically, before the program is executed. Dynamic systems perform feasibility checking on-line, as tasks arrive.
There are two approaches to scheduling in dynamic real-time systems:
1. Dynamic planning-based approaches: Execution of a task is begun only if it passes a feasibility test, i.e that it will complete execution before its deadline. Often, one of the results of the feasibility analysis is a schedule or plan that is used to decide when a task should begin execution.
2. Dynamic best-effort approaches: Here no feasibility checking is done; the system tries to ‘do its best’ to meet deadlines but, since feasibility is not checked, a task may be aborted during its execution.
In a planning-based approach, the feasibility of a set of tasks is checked in terms of a scheduling policy such as ‘earliest-deadline-first’ or ‘least- laxity-first’, before the execution of a set of tasks. By contrast, in a best-effort approach, tasks may be queued according to policies that take account of the time constraints (similar to the kind of scheduling found in a non-real-time operating system). No feasibility checking is done before the tasks are queued.
The relative importance of a task and the value given to its completion are used to take scheduling decisions, whether or not feasibility checking is done. This information is usually given as a time-value function that specifies the contribution of a task to the system upon its successful completion. Figure 4.1 relates value with completion time, for different value functions.
For hard real-time tasks, the value drops immediately after the deadline and dynamic algorithms cannot be used: there should be a priori verification that such tasks will meet their deadlines. Dynamic algorithms are suitable for the tasks in the ‘firm’ and ‘soft’ categories.
To achieve high system performance, the system must also consider the relative values of tasks, or their importance, when determining which tasks to reject and which to execute.
Because a dynamic scheduling algorithm takes decisions without prior knowledge of the tasks, the total value is not predictable and the algorithm must attempt to maximize the value accrued from tasks that complete on time. Most dynamic algorithms developed so far assume that a value function assigns a positive value to a task that is successfully completed, and zero to an incomplete task. This corresponds to the curve marked ‘firm’
in Figure 4.1, where the value for a task remains constant until its deadline and then drops to zero. If all the tasks have the same value, maximizing the accrued value is the same as maximizing the number of completed tasks.
While achieving maximum value, real-time systems must also exhibit a capability for ‘graceful degradation’. To achieve this, not only must the fact that a task did not meet its deadline be detected, but the fact that this is going to occur must be detected as soon as possible. An exception must then be signalled to make it possible for the task to be substituted by one or more contingency tasks. Thus on-line schedulability analysis must have an early warning feature which provides sufficient lead time for the timely invocation of contingency tasks, making it possible for the scheduler to take account of a continuously changing environment. Such schedulability analysis is especially important for transactions for which recovery following an aborted partial execution can be complicated. Error handlers are complex
in general and abnormal termination may produce inconsistent system states. This is likely to be the case especially if the transaction involves inter-process interaction. In such situations, it is better to allow a transaction to take place only if it can be guaranteed to complete by its deadline. If such a guarantee cannot be provided, then the program can perform an alternative action. And to provide sufficient time for executing the alternative action, a deadline may be imposed on the determination of schedulability. This can
be generalized so that there are N versions of the transaction and the algorithm attempts to guarantee the execution of the best possible version. ‘Best’ refers to the value of the results produced by a particular version; typically, the better the value of the result, the longer the execution time.
Schedule construction
Schedule construction is the process of ordering the tasks to be executed and storing this in a form that can be used by the dispatching step. Feasibility checking is sometimes performed by checking if there is a schedule or plan in which all the tasks will meet their deadlines. For planning-based approaches, schedule construction is usually a direct consequence of feasibility checking. In other cases, priorities are assigned to tasks and at run-time the task in execution has the highest priority. This is the case with fixed priority approaches and with some simple dynamic priority approaches, such as earliest-deadline-first or least-laxity-first, where feasibility checking involves ensuring that the total processor utilization is below a bound.
Thus, scheduling involves deciding when tasks will execute. The schedule
is maintained explicitly in the form of a plan or implicitly as the assignment of priorities to tasks.
Dispatching
Dispatching is the process of deciding which task to execute next. The complexity and requirements for the dispatching step depend on:
1. The scheduling algorithm used in the feasibility checking step,
2. Whether a schedule is constructed as part of the schedulability analysis step,
3. The kinds of tasks, e.g. whether they are independent or with precedence constraints, and whether their execution is pre-emptive or non-pre-emptive,
4. The nature of the execution platform, e.g. whether it has one processor or more and how communication takes place.
For example, with non-pre-emptive scheduling a task is dispatched exactly once; with pre-emptive scheduling, a task will be dispatched once when it first begins execution and again whenever it is resumed. We discuss how the timing requirements of transactions can be specified and how user level transactions can be mapped into tasks with different characteristics including timing constraints, precedence constraints, resource requirements, importance levels and communication characteristics. Issues to be considered for dynamic scheduling are introduced and different ways of assigning priorities to tasks are considered. The two types of dynamic scheduling approach, best-effort scheduling and planning-based scheduling, are discussed in detail and, since the run-time cost of a dynamic approach is an important practical consideration, several techniques are discussed for efficient dynamic scheduling.
Programming dynamic real-time systems
The requirements for tasks in a real-time system can be quite varied. In this section, we show how they can be specified from within a program. For dynamic real-time applications, it should be possible to specify several important requirements:
· Before initiating a time-constrained transaction, it should be possible for the program to ask for a guarantee from the run-time system that the transaction will be completed within the specified deadline.A transaction can be guaranteed to complete within its deadline if a schedule can be created for this transaction and the other transactions that have been previously guaranteed to meet their deadlines.
· If the system cannot give a guarantee when it is sought, then it should be possible to choose an alternative activity. When a guarantee is not sought and it is not possible to meet the timing constraint, it should be possible to take alternative action. In either case, the alternative may be a timing-error handler that will allow some corrective action to be taken. Language constructs to express such constraints are described using a form of pseudocode.
In what follows, terminals are shown in typewriter font,[ ]encloses optional items and | separates alternatives. A transaction (shown in italics) refers to a statement. A real-time transaction has a time constraint such as a periodicity requirement or a deadline.
Activities with deadlines
Timeouts can be associated with any statement using the within deadline statement which has the form
Within deadline(d) statement1
[ else statement2 ]
During execution, if execution of a within deadline statement starts at time t and is not completed by t+d, then it is terminated and statement2, if provided, is executed. Hence, d is the deadline relative to the current time. The effect of this abnormal termination is local if statement1 does not require any inter-process communication; otherwise, the other interacting processes may be affected.
Example Air traffic control 1. An air-traffic control system should provide final clearance for a pilot to land within 60 seconds after clearance is requested. Otherwise the pilot will abort the landing procedure:
within deadline (60) get clearance
else abort landing
Guaranteed transactions
The guarantee statement is used to ensure before a transaction is started that it can be completed within the specified time constraint:
within deadline (gd ) guarantee
time constrained statement
[else statement ]
where gd is the deadline for obtaining the guarantee. If the guarantee is not possible, or if it cannot be given within gd, the else statement, if provided, is executed. Otherwise, the time-constrained statement is executed.To provide such a guarantee, the execution time and the resource requirements of the statement must a priori be determinable (at least at the time of the guarantee). This makes it important for the execution time to lie within relatively small bounds as resources must be provided for the worst-case needs. In general, the larger the worst-case needs, the less likely it will be to obtain a guarantee; further, even if a guarantee can be given for large
bounds, it is likely to affect future guarantees.
Dynamic scheduling makes it possible to use run-time information about tasks, such as execution times and resource constraints. Such information can be derived from formulas provided by the compiler for evaluation at the time of task invocation. For example,the calculation of the execution time can then take into account the specific parameters of the invocation and hence be more accurate (and perhaps less pessimistic) than a statically determined execution time; such calculations can make use of data only available at run-time, such as the number and values of inputs. As for compile-time calculation of worst-case execution times, run-time calculation also requires loop iterations and communication times to be bounded. If synchronous communication statements do not have associated time-constraints, it is necessary to consider the communicating tasks together
as a transaction when checking feasibility.
Example The following statement tries to guarantee that statement1 will be completed within the next d seconds:
within deadline (gd) guarantee
within deadline (d) statement1
[else ...]
[else statement2 ]
If execution starts at time t, statement2 will be executed if it is not possible to obtain the guarantee by t + gd. If guaranteed, execution of statement1 will start at st and end by t+ d, where st lies in the interval (t; t+gd).
Example A simple railway crossing. The task controlling a railway signal has to determine whether a certain track will be clear by the time a train is expected to reach there. This must be done early enough to give enough time to stop the train if the track is not expected to be clear. Assume that the train will not reach the track before d seconds and that it takes at most s seconds to stop the train (s < d):
within deadline (d-s) guarantee
within deadline (d) clear track
else ...
else stop train
Start-time-constraints
The following statement attaches start time constraints to transactions with deadlines:
start at (s) within deadline (d ) statement1
[else statement2]
If execution of the within deadline statement starts at time t, then execution of statement1 should start at or after t+s and be completed by t+d, where d > s. A simple extension gives the guaranteed version of this statement. The value v of a task is specified by attaching the construct value v to the within deadline statement.
Flexible time-constraints: The time-constraints described thus far are to ensure that if a transaction is not completed within the specified time, it is terminated and timing-error handling is done. This is appropriate if there is no value in completing the transaction after the specified time.
For many real-time applications, while it may be desirable for all transactions to meet the timing-constraints, it may be better, and sometimes necessary, to complete a transaction even if it is delayed. Such time-constraints will be called flexible. Thus a transaction may have a non-zero value up to some point past its deadline; if this point does not lie in a fixed interval, the transaction should be completed regardless of how long it takes.
To express flexible time-constraints, an overflow is associated with a time-constraint. If the overflow is positive, a transaction should be terminated only after the end of the interval corresponding to the overflow. This corresponds to a soft deadline. If the overflow has a negative value, it indicates that the transaction must be completed by the specified deadline but, if possible, within overflow units before the deadline. (This is like asking the system to ‘be nice’ to a transaction by trying to complete it before the deadline.)
A deadline-constrained transaction statement1 is specified as
within deadline (d)[overflow] statement1
else statement2
and has the following effect:
_ If execution of statement1 is not completed by max(d;d+overflow), processing of statement1 is terminated and statement2, if provided, is executed.
_ If overflow is not specified, it is assumed to be zero.
_ If a guarantee is requested, it will be first attempted for min(d;d+overflow) and, if this is unsuccessful, for max(d,d+overflow); if the second attempt is also unsuccessful, the else clause, if specified, will be executed.
_ If a time-constrained component of statement1 has an overflow, it can increase the worst-case execution time of statement1.
Example . Air traffic control 2. An air-traffic control system should provide final clearance for a pilot to land within t1 seconds after the request has been made; if this is not possible, clearance should be given within another t2 seconds or the pilot will abort the landing procedure:
within deadline (t1)(t2) clear landing
else abort landing
It is easy to see that a large overflow indicates that the transaction has only a nominal deadline and should be allowed to complete even if the deadline is past.
Issues in dynamic scheduling
With static priorities, a task’s priority is assigned when it arrives and fresh evaluation is not required as time progresses and new tasks arrive. Hence static priorities are well suited for periodic tasks that execute at all times (but, with the extensions, they can be used for aperiodic tasks as well).
In a dynamic system, static feasibility checking is not possible and dynamic decision making algorithms must be used. This has several implications. It is no longer possible to guarantee that all task arrivals will be able to meet their deadlines: if the arrival times of tasks are not known, the schedulability of the tasks cannot be guaranteed. However, if the system has only independent, periodic tasks and one processor, static schedulability analysis can be used even if the scheduling policy is dynamic. For tasks with a more complex structure, other attributes can be used to assign priorities. This gives dynamic algorithms a lot of flexibility and adds to their ability to deal with a wide variety of tasks. But there may be substantial overheads in calculating the priorities of tasks and in selecting the task of highest priority. When dynamic priorities are used, the relative priorities of tasks can change as time progresses, as new tasks arrive or as tasks execute. Whenever one of these events occurs, the priority of all the remaining tasks must be recomputed. This makes the use of dynamic priorities more expensive in terms of run-time overheads, and in practice these overheads must be kept as small as possible. A shortcoming of static schedulability analysis arises from the assumptions and the restrictions on which off-line guarantees are based. For example, if there is a non-zero probability that these assumptions are unlikely to hold or that restrictions may be violated, a system using a static approach will not perform as designed and tasks may miss their deadlines. And, under some situations, effective control of the system can be lost because of the limited scheduling capability available at run-time. Thus, when constraints assumed by off-line schedulability analysis are likely to be violated, dynamic scheduling approaches provide a solution.
Consider a very simple example. If system overloads are known to be impossible, then the earliest-deadline-first algorithm (EDF) can be used. Since overloads cannot occur, when a task is pre-empted there is an implicit guarantee that the remainder of the task will be completed before its deadline; without overloads, simple algorithms such as EDF and least-laxity-first (LLF) perform very well. But if overloads are possible, in the worst case, EDF and LLF may produce zero value, i.e. none of the tasks that arrive will meet its deadline (even if, under another scheduling discipline, some tasks may meet their deadlines). An optimal dynamic scheduling algorithm always produces a feasible schedule whenever a clairvoyant algorithm, i.e. a scheduling algorithm with complete prior knowledge of the tasks, can do so. Unfortunately, it is difficult to construct a good on-line algorithm to compete with a clairvoyant algorithm. Competitiveness analysis, involving the comparison of an on-line algorithm with a clairvoyant algorithm, is one way to predict the behaviour of a dynamic algorithm. However, this analysis considers only worst-case behaviours involving all possible task characteristics. For predictability, planning-based scheduling is a viable Alternative. Here, given a particular priority assignment policy and the requirements of a task before it begins execution, a check is made to see whether there is a way for the task to meet its deadline. As mentioned earlier, many planning approaches also produce a schedule for task execution as a useful by-product and the added cost of the checking may be well spent.
Dynamic priority assignment
Construction of a plan in planning-based approaches and determining which task to execute next in best-effort approaches requires assigning priorities to tasks; this raises the question of how priorities are assigned. Further, there is a conflict between priority-based scheduling and the goal of maximizing resource utilization in a real-time system.
Simple priority assignment policies
In a real-time system, priority assignment must be related to the time constraints associated with a task, e.g. according to EDF or LLF ordering. For scheduling independent tasks with deadline constraints on single processors, EDF and LLF are optimal methods, so if any assignment of priorities can feasibly schedule such tasks, then so can EDF and LLF.
For a given task set, if tasks have the same arrival times but differrent deadlines, EDF generates a non-pre-emptive schedule, while the LLF schedule requires pre-emptions. If both arrival times and deadlines are arbitrary, EDF and LLF schedules may both require pre-emptions. These algorithms use the timing characteristics of tasks and are suitable when the processor is the only resource needed and tasks are independent of each other.
Priority assignment for tasks with complex requirements
Of more practical interest is the scheduling of tasks with timing constraints, precedence constraints, resource constraints and arbitrary values on multi-processors. Unfortunately, most instances of the scheduling problem for real-time systems are computationally intractable. Non-pre-emptive scheduling is desirable as it avoids context switching overheads, but determining such a schedule is an NP-hard problem even on uniprocessors if
tasks can have arbitrary ready times. The presence of precedence constraints exacerbates the situation and finding a resource-constrained schedule is an NP-complete problem.
This makes it clear that it serves no effective purpose to try to obtain an optimal schedule, especially when decisions are made dynamically. And, with multi-processors, no dynamic scheduling algorithm is optimal and can guarantee all tasks without prior knowledge of task deadlines, computation times and arrival times. Such knowledge is not available in dynamic systems so it is necessary to resort to approximate algorithms or to use heuristics, as we shall now see.
A task t is the unit for scheduling; it is characterized by its arrival
time AT, its absolute deadline D, its value V, its worst-case computation time C and its resource requirements {RR}. Tasks are assumed to be independent, non-periodic and non-pre-emptive. A task uses a resource either in shared mode or in exclusive mode and holds a requested resource as long as it executes. EST is the earliest start time at which the task can begin execution (EST is calculated when scheduling decisions are made).
The following condition relates AT, D, C, EST and the current time T :
AT < EST<D<C
Let Pr(t) be the priority of task t, and assume that the smaller the value of Pr(t), the higher the priority. There are a number of possible priority assignment policies.
1. Smallest arrival time first, or first-come-first served (FCFS): Pr(t) = AT. FCFS is a fair policy but it does not take any real-time considerations into account. For tasks with the same priority, FCFS may be a suitable policy.
2. Minimum processing time first (Min C): Pr(t) = C. In non-real-time environments, the simple heuristic Min C is often a rule for minimizing average response times but it is not usually adequate for real-time systems.
3. Minimum (or earliest) deadline first (Min D): Pr(t) = D. For tasks needing only a processor resource, Min D can be a suitable policy.
4. Minimum earliest start time first (Min S): Pr(t) = EST. This is the first policy to take resource requirements into account through calculation of EST.
5. Minimum laxity first (Min L): Pr(t) = D_(EST+C). Like EDF, (Min L) is optimal for tasks that have just processing requirements; Min L takes into account the information used in Min D and Min S.
6. Minimum value first (Min V): Pr(t) = V. Min V considers only the value of a task.
7. Minimum value density first (Min VD): Pr(t) = TV C . Unlike Min V, which does not take the computation time into account, Min VD considers the value per unit time when assigning task priorities.
Priority-based scheduling and resources
There is usually a conflict between keeping resources busy and respecting task priorities: if resources are to be used to the fullest extent possible, there may be task executions that violate task priorities.
Implementing planning-based scheduling
Here there are two main considerations: feasibility checking and schedule construction.
In a multi-processor system, feasibility checking and dispatching can be done independently, allowing these system functions to run in parallel. The dispatcher works with a set of tasks that have been previously guaranteed to meet their deadlines, and feasibility checking is done on the set of currently guaranteed tasks plus any newly invoked tasks.
Feasibility checking and schedule construction
One of the crucial issues in dynamic scheduling is the cost of scheduling: the more time that is spent on scheduling the less there is for task executions.
In a single-processor system, feasibility checking and task executions compete for processing time. If feasibility checking is delayed, there is less benefit from the early warning feature. However, if feasibility checking is performed immediately after a task arrives, this may lead to guaranteed tasks missing their deadlines. Thus, when tasks are guaranteed, some time must be set aside for scheduling-related work and a good balance must be struck depending on task arrival rates and task characteristics such as computation
times.
One way is to provide for the periodic execution of the scheduler. Whenever invoked, the scheduler will attempt to guarantee all pending tasks. In addition, if needed, the scheduler could be invoked sporadically whenever these extra invocations will affect neither guaranteed tasks nor the minimum guaranteed periodic rate of other system tasks.
Another alternative, applicable to multi-processor systems, is to designate a ‘scheduling’ processor whose sole responsibility is to deal with feasibility checking and schedule construction. Guaranteed tasks are executed on the remaining ‘application’ processors. In this case, feasibility checking can be done concurrently with task execution. Recall that a task is guaranteed as long as it can be executed to meet its deadline and the deadlines of previously guaranteed tasks remain guaranteed. Guaranteeing a new task might require re-scheduling of previously guaranteed tasks and so care must be taken to ensure that currently running tasks will not be re-scheduled.
These considerations suggest that scheduling costs should be computed based on the total number of tasks in the schedule plus the newly arrived tasks, the complexity of the scheduling algorithm and the cost of scheduling one task. Tasks with scheduled start times before the current time plus the scheduling cost are not considered for rescheduling; the remaining tasks are candidates for re-scheduling to accommodate new tasks.
Dispatching
Planning-based schedulers typically use non-pre-emptive schedules. Dispatching depends on whether the tasks are independent and whether there are resource constraints. If the tasks are independent and have no resource constraints, dispatching can be extremely simple: the task to be executed next is the next task in the schedule, and this task can always be executed immediately even if its scheduled start time has not arrived.
On the other hand, precedence constraints and resource constraints may increase the complexity of dispatching. If tasks have resource or precedence constraints, the dispatching process must take these into account. When the actual computation time of a task differs from its worst-case computation time in a non-pre-emptive multi-processor schedule with resource constraints, run-time anomalies may occur, causing some of the scheduled
tasks to miss their deadlines. There are two possible kinds of dispatcher:
1. Dispatch tasks exactly according to the given schedule. In this case, upon the completion of one task, the dispatcher may not be able to dispatch another task immediately because idle time intervals may have been inserted by the scheduler to conform to the precedence constraints or resource constraints. One way to construct a correct dispatcher is to use a hardware (count down) timer in order to enforce the start time constraint.
2. Dispatch tasks taking into consideration the fact that, given the variance in task execution times, some tasks will complete earlier than expected. The dispatcher tries to reclaim the time left by early completion and uses it to execute other tasks.
Clearly, non-real-time tasks can be executed in the idle time slots. More valuable is an approach that improves the guarantees of tasks that have time-constraints. Several issues must be considered to achieve this. Resource reclaiming algorithms used in systems that perform dynamic planning-based scheduling must maintain the feasibility of guaranteed tasks, must have low overheads, as a resource reclaiming algorithm is invoked whenever
a task finishes, and must have costs that are independent of the number of tasks in the schedule. They must also be effective in improving the performance of the system.
Complete rescheduling of all remaining tasks is an available option, but, given the complexity of scheduling, it is usually expensive and ineffective.
A feasible multi-processor schedule provides task ordering information that is sufficient to guarantee the timing and resource requirements of tasks in the schedule. If two tasks overlap in time on different processors in a schedule, then it can be concluded that no matter which of them is dispatched first at run-time, the deadline of the ot her will not be affected. On the other hand, if two tasks do not overlap in time, the same conclusion cannot be drawn without re-examining resource constraints or without total rescheduling.
Assume each task ti is assigned a scheduled start time SSTi and a scheduled finish time SFTi in the given feasible schedule. Resource reclaiming algorithms use this information to perform local optimization at run-time, while preserving the correct relative ordering among the scheduled tasks and ensuring the original guarantees. This local optimization is accomplished by reasoning only about the first task scheduled to execute on each of the m processors, and there is no need to examine the availability of the resources needed in order to dispatch a task when reclaiming occurs. Thus, the complexity of the algorithm is independent of the number of tasks in the schedule and depends only on the number of processors.
No comments:
Post a Comment
leave your opinion