| Real Time Systems: Notes |
These notes make use of mathematical symbols that may not be visible with the default settings on some versions of some browsers.
| Symbol | Symbol Name | Symbol | Symbol Name | Symbol | Symbol Name |
|---|---|---|---|---|---|
| ∼ | sim | ∑ | sum | ⌈ | lceil |
| ⌉ | rceil | ⌊ | lfloor | ⌋ | rfloor |
| → | rarr | ⇒ | rArr | ∞ | infin |
| < | lt | ≤ | le | > | gt |
| ≥ | ge | ≠ | ne | δ | delta |
| Δ | Delta | ∂ | part | τ | tau |
| π | pi | φ | phi | ∞ | infin |
If a blank space appears to the left of any of the names in the table above, or the symbol looks strange, try changing the font settings on your browser or using a different browser.
Usage of the terms "sporadic" and "aperiodic" is not uniform across all authors in real time systems.
In these notes, I use the term "aperiodic task" with the above meaning, and specify whether we have hard or soft deadlines if that is important. Note, however, that Jane Liu's terminology is different, and diverges from that of most authors on this subject. She classifies as "periodic task" what we are calling a sporadic task, classifies as "sporadic task" what we are calling an aperiodic task with hard deadlines, and classifies as "aperiodic task" what we are calling an aperiodic task with soft deadlines.
Some writers use "aperiodic" as a synonym for "not periodic", in which case sporadic tasks would be a subset of aperiodic tasks.
Note also that the "sporadic server" scheduling algorithm, which we will cover below is not specifically linked to any of the above definitions of "sporadic task".
By a "useful" lower bound I mean a bound that can be used effectively to analyze the task's schedulability as a periodic task. For example, we may know that the minimum interarrival time for an aperiodic task is ten microseconds, because that is the minimum hardware interrupt latency, but that too short to be a useful lower bound for schedulability analysis. It would be better to analyze that task as of type 2.
Projecting performance from limited experimental or simulation data can be inaccurate. The figure (from William Stallings' Operating Systems text) compares actual response time of a system against a projection made from actual data up to a load of 0.5. The projection is based on fitting a 3rd-order polynomial to the known data.
The statistical performance of an aperiodic server can be analyzed using techniques from queueing theory.
(Please see separate notes on Queueing Theory for background.)
In particular, all of the aperiodic server algorithms approximate the performance of an ideal processor sharing model in which the aperiodic server executes on its own dedicated processor at speed es/ps.
This approximation can be used to estimate the values of es and ps required to achieve a given average response time.
In general, an aperiodic server cannot do better than such an ideal queueing theory model over a long time interval. However, certain aperiodic server scheduling techniques can do a little bit better locally, since during a burst of server activity the server is actually executing at speed 1, rather than es/ps.
The basic idea of aperiodic server scheduling algorithms is for the aperiodic service requests to be executed by a server thread. The server is a sort of virtual processor, which is allocated a limited fraction of the processor bandwidth. Aperiodic service requests (aperiodic jobs) are put onto a queue (buffer) for the server. The server takes jobs from its queue and executes them, as fast as it can using its available CPU time. How long it takes for the server to get around to serving a given job depends on the server's bandwidth and the amount of other work that is ahead of it in the server's queue.
The differences in algorithms have to do with how the processor bandwidth is allocated to the server. In all cases, the server is supposed to be able to be treated (more or less) as if it were a periodic task, insofar as its effects of the server's workload on the scheduling of other tasks in the system.
We will look at several of the aperiodic server scheduling algorithms in more detail.
Jobs of an aperiodic task are not required to complete before the next job is released. Jobs are queued up, and executed by a server (a schedulable entity, e.g., thread) as soon as the server can get to them.
The server is allocated a budget, which is consumed when aperiodic jobs are executed, and replenished from time to time. When the server's budget is down to zero, or the server is preempted by some higher priority task, requests must wait to be served. Different server scheduling schemes use different rules to determine when the server budget is replenished, when the server budget can be carried forward, and the priority at which the server executes.
The ideal is that the server be scheduled in a way that allows us to model the server's impact on the schedulability of other tasks as if the server were a periodic task. In particular, we would like to have it be true that in any time interval of length ps the server cannot preempt other tasks for longer than es execution time.
We can use the aperiodic server concept with:
Deadline server principle: In a deadline scheduling environment, each allocation of server budget comes with an associated deadline, which governs the scheduling of the server while it is using that portion of its budget.
Aperiodic requests are served at lowest priority. They do not interfere with any periodic task, but aperiodic response times are quite variable and generally long.
Unused budget is given up whenever all requests are served.
Budget can never exceed es.
Scheduling interference on other tasks is no worse than that of periodic task with period ps and es.
In this example, the server polls with period 5 and execution budget 2, for a total utilization of 40%. There are two periodic tasks. &tau1 (light grey) has period 10, execution time 2, and utilization 20%. τ2 (dark grey) has period 15, execution time 6, and utilization 40%. Ties in deadline are resolved in favor of the polling server.
In both cases, the effect of the server on the delays encountered by other tasks is no worse than as if the server were replaced by a normal periodic task with the same period and execution time.
Response time may be nearly a whole period later, even under very light load.
This comparatively long response time is one of the factors that motivated the invention of other server scheduling models, including the deferrable servers.
The segmented lines are average response times of a simulated polling server, with average interarrival time 3600 and 69% periodic load, for several different server periods.
The lower smooth curve is the expected performance of a processor 100% dedicated to serving the aperiodic load, with no periodic load, as predicted by the M/M/1 queueing theory model.
The limiting case of a time-sliced server, with infinitesimal time slicing interval and the same processor utilization as the polling server, as predicted by the M/M/0.31 queueing theory model, is shown by the higher one of the two smooth curves.
The test involved the following set of ten periodic tasks:
| i | pi | ei |
|---|---|---|
| 1 | 5400 | 600 |
| 2 | 14400 | 600 |
| 3 | 24000 | 500 |
| 4 | 43200 | 6400 |
| 5 | 54000 | 3000 |
| 6 | 67500 | 4500 |
| 7 | 72000 | 7200 |
| 8 | 90000 | 3600 |
| 9 | 108000 | 2000 |
| 10 | 120000 | 10500 |
This is a form of "bandwidth preserving" server. The unused budget is retained until the next replenishment point. This allows requests to be served earlier.
The deferrable server may be scheduled with a fixed priority, or scheduled according to EDF. In the latter case, the deadline is incremented by ps at each budget replenishment.
Workload of server may be as high as 2es in a single interval of length ps. This means impact of server on schedulability of other tasks is greater than that of a periodic task with period ps and es.
The deferrable server model falls short of our ideal for schedulability analysis, in that we need to allow for the possibility of the above case, even though it probably will not happen very often. This reduces the schedulable utilization (i.e., the utilization at which we know all tasks are schedulable) of the system.
The worst-case interference caused by the server occurs when there are back-to-back server executions at the end of the time interval.
| wi(t) = ei + es + | ⌈ | t-es ps |
⌉ | es+ |
|
⌈ |
|
⌉ | ek |
The main difference is that the worst-case deadline DS time demand is not quite as high as the fixed-priority DS time demand.
| Fixed Priority | Deadline | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| es + | ⌈ | t-es ps |
⌉ | es | es + | ⌊ | t-es ps |
⌋ | es | |
That is, a job with deadline past the interval will not have high enough priority to preempt a job with deadline inside the interval.
In this example, the server polls with period 5 and execution budget 1.63, for a total utilization of 32.6%. There are two periodic tasks. &tau1 (light grey) has period 10, execution time 2, and utilization 20%. τ2 (dark grey) has period 15, execution time 6, and utilization 40%. Ties in deadline are resolved in favor of the deferrable server.
A set of periodic hard-deadline tasks is schedulable by EDF with a DDS server of period ps and replenishment es if the following holds for each task τk.
|
( | ei min(di,pi) |
)+(1+ | ps-es dk |
) | es ts |
≤ 1 |
This follows from the interfering demand bound above, using the fact that &lfloor x ⌋ ≤ x, and that for task τk to miss a deadline the interfering demand within any busy interval of length dk must exceed ek.
These are simulation results for three specific periodic task sets, at three different utilization levels. The the server utilization level is that above which periodic tasks start to miss deadlines.
Note that the effect of back-to-back server executions, reflected in the term (ps-es)/dk) of the schedulability test, requires a reduction of the server utilization for large server periods to prevent missed periodic deadlines.
Replenishments are done in chunks, delayed according to when the chunks were used. Load never exceeds es in any interval of length ps, so impact on schedulability of other tasks is no greater than that of a collection of periodic tasks with period ps and total execution time es.
The above figure shows what J. Liu calls the SpSL sporadic server variant. There are several other variants. One reason for the variations is that the original version, which was published by Sprunt, Sha, and Lehoczky (SpSL), had a defect not caught by the referees, which (under certain circumstances) would allow the server interference to exceed that of a periodic task with the same period and budget, due to early replenishment. The POSIX variant also a defect with a similar effect.
Note that the term "sporadic" in Sporadic Server scheduling does not imply the method is limited to scheduling sporadic tasks, or that the serve behaves exactly like a sporadic task. Unfortunately, this does add to the confusion over exactly what "sporadic task" means.
J. Liu calls this server "simple" because there is never more than one replenishment pending and the replenishment always brings the budget all the way up to es.
However, as she says later, this "simple" version is actually more complicated to implement.
For this reason, and because we have limited classroom time, I may decide to skip over this version of the algorithm in class.
Warning: Since I found Jane's description rather complicated and difficult to follow, I tried to rewrite her description in my own words, above. I hope I have not changed the meaning. If in doubt, please refer to the textbook for her exact description.
Also please see the textbook for the informal proof of correctness of this algorithm, i.e., the proof that there can be no time interval of length ps in which the server uses more than es execution time.
Uses available background time. Same rules apply as for SSS, except:
This makes sense when there is only one sporadic server in the system.
J. Liu explains another variation on the SS, in which the server is allowed to accumulate replenishments, up to a point. The rules are subtle, to prevent the problem we had with the deferrable server. We will not cover these rules in class. You should read them in the text.
The basic idea is to allow the server to consume and replenish its budget in chunks of less than es.
As J. Liu explains, the original published description of the algorithm was over-simplified, to the point of being incorrect. This is a valuable lesson.
The server has a capacity of es, with initial replenishment time tr = 0
Consumption:
Replenishment:
Jane Liu shows some ways to correct the SpSL sporadic server anomaly, including her "simple" sporadic server. The above is my own attempt to correct the SpSL anomaly. Does it ensure the property we want? That is, is it true that the interference caused by the server in any busy time interval can never exceed that of a perodic task with periodic ps and execution time es?
The following is from the IEEE POSIX and Open Group Unix 98 standards documents:
If _POSIX_SPORADIC_SERVER or _POSIX_THREAD_SPORADIC_SERVER is defined, the implementation shall include a scheduling policy identified by the value SCHED_SPORADIC.
The sporadic server policy is based primarily on two parameters: the replenishment period and the available execution capacity. The replenishment period is given by the sched_ss_repl_period member of the sched_param structure. The available execution capacity is initialized to the value given by the sched_ssinit_budget member of the same parameter. The sporadic server policy is identical to the SCHED_FIFO policy with some additional conditions that cause the thread's assigned priority to be switched between the values specified by the sched_priority and sched_ss_low_priority members of the sched_param structure.
The priority assigned to a thread using the sporadic server scheduling policy is determined in the following manner: if the available execution capacity is greater than zero and the number of pending replenishment operations is strictly less than sched_ss_max_repl, the thread is assigned the priority specified by sched_priority; otherwise, the assigned priority shall be sched_ss_low_priority. If the value of sched_priority is less than or equal to the value of sched_ss_low_priority, the results are undefined. When active, the thread shall belong to the thread list corresponding to its assigned priority level, according to the mentioned priority assignment. The modification of the available execution capacity and, consequently of the assigned priority, is done as follows:
When the thread at the head of the sched_priority list becomes a running thread, its execution time shall be limited to at most its available execution capacity, plus the resolution of the execution time clock used for this scheduling policy. This resolution shall be implementation-defined.
Each time the thread is inserted at the tail of the list associated with sched_priority because as a blocked thread it became runnable with priority sched_priority or because a replenishment operation was performed the time at which this operation is done is posted as the activation_time.
When the running thread with assigned priority equal to sched_priority becomes a preempted thread, it becomes the head of the thread list for its priority, and the execution time consumed is subtracted from the available execution capacity. If the available execution capacity would become negative by this operation, it shall be set to zero.
When the running thread with assigned priority equal to sched_priority becomes a blocked thread, the execution time consumed is subtracted from the available execution capacity, and a replenishment operation is scheduled, as described in 6 and 7. If the available execution capacity would become negative by this operation, it shall be set to zero.
When the running thread with assigned priority equal to sched_priority reaches the limit imposed on its execution time, it becomes the tail of the thread list for sched_ss_low_priority, the execution time consumed is subtracted from the available execution capacity (which becomes zero), and a replenishment operation is scheduled, as described in 6 and 7.
Each time a replenishment operation is scheduled, the amount of execution capacity to be replenished, replenish_amount, is set equal to the execution time consumed by the thread since the activation_time. The replenishment is scheduled to occur at activation_time plus sched_ss_repl_period. If the scheduled time obtained is before the current time, the replenishment operation is carried out immediately. Several replenishments may be pending at the same time, each of which will be serviced at its time. With the above rules, the number of replenishment pending for a given thread that is scheduled under the sporadic server policy shall not be greater than sched_ss_max_repl.
A replenishment operation consists of adding the corresponding available execution capacity at the scheduled time. If, as a consequence of this operation, the execution capacity would become larger than sched_ssinitial_budget, it shall be rounded down to a value equal to sched_ssinitial_budget. Additionally, if the thread was runnable or running, and had assigned priority equal to sched_ss_priority, then it becomes the tail of the thread list for sched_priority.
Execution time is defined in Section 2.2.2 (on page 462).
For this policy, changing the value of a CPU-time clock via clock_settime( ) shall have no effect on its behavior.
For this policy, valid priorities shall be within the range returned by the and sched_get_priority_max( ) functions when SCHED_SPORADIC is provided as the parameter. Conforming implementations shall provide a priority range of at least 32 distinct priorities for this policy.
Consumption:
Replenishment:
In addition, the POSIX version of the Sporadic Server algorithm has a limit on the number of replenishments that a thread may have outstanding at any instant. If this bound is reached, the remaining execution time budget of the thread is given up and added to the amount of the last replenishment. This helps to combat fragmentation of the budget.
Q: Does the POSIX sporadic scheduling policy suffer from the defect of the original publication SpSL version?
Consumption:
Replenishment:
Server priority activation time:
Coalescing chunks:
The server has an initial budget es and a period ps, which define the server's utilization (a.k.a. size), us = es/ps.
The server is "eligible to execute" when its queue and budget are both non-empty.
The chunk χm is the available chunk with the earliest replenishment time. The execution time used by the server is charged to χm.
When the server consumes all of the chunk χm or completes all the queued requests, the portion of χm that the server has consumed is split off and scheduled for replenishment. Suppose the server has used δ execution time. A new chunk, χm', is created, with size σm' = δ and replenishment time ρm' = ts, where ts is the current deadline of the server (which is defined further below). The size of χm is reduced by δ. If the new size is zero, the chunk χm is deleted, and its role is then played by the remaining chunk with earliest replenishment time.
In each case of the definition of ts the variable Now denotes the time at which the condition becomes true. Assume there is an idle-task, with deadline ∞, that executes when no other task is eligible to execute; by the fifth case above, ts is undefined when the idle task is running.
Stated informally, ts is ps later than the most recent time at which the (current) server priority became active. However, we are forced define it without reference to the server priority, to avoid circularity in the definition, since the priority depends on the deadline, which depends on ts.
Note that ts is always defined when the server is eligible to execute, and is never later than the time the server last became eligible to to execute. Sometimes it may be earlier, if the processor was continuously occupied with higher priority tasks just before the server became eligible to execute.
For any time t when ts is defined, it is true that in the interval [ts,t] the processor is continuously busy executing tasks with deadlines ≤ ts+ps. It follows that the effect on the schedulability of other tasks is the same as if the server had become eligible to execute at ts and remained eligible to execute during the entire interval [ts,t].
Note that the replenishment method of the DSS algorithm forces the server not to re-use a chunk of execution time until at least ps time units later than the server last could have become eligible to use that chunk. Thus, the execution time of the server within any time interval cannot exceed the amount that would be used by a periodic task with the same period and execution time.
The chunk merging step is to prevent the execution time budget from being fragmented into smaller and smaller chunks. This cannot affect the scheduling outcome, since ρi is only used in updating ts (and computing the server deadline) when ρi > ts, and we know ts ≥ t.
Based on the arguments above, we have the following lemma, which characterizes the deadline sporadic server load.
Lemma: For every time interval [t',t] such that t is a missed hard deadline, t' ≤ t-es and there is no task with deadline later than t executing in the interval, an upper bound of the deadline sporadic server's demand for CPU time in the interval is
| ⌊ | t - t' ps |
⌋ | es |
The following theorem provides a sufficient condition for feasibility of a set of (periodic and aperiodic) tasks under the DSS algorithm.
Theorem: A set of hard-deadline tasks is schedulable by EDF scheduling and the DSS algorithm if
| n ∀k k=1 |
( | k ∑ i=1 |
ei min {Di,pi} |
) | + us ≤ 1 |
where us = es/ps is the aperiodic server utilization.
In this example, the server polls with period 5 and execution budget 2, for a total utilization of 40%. There are two periodic tasks. &tau1 (light grey) has period 10, execution time 2, and utilization 20%. τ2 (dark grey) has period 15, execution time 6, and utilization 40%. Ties in deadline are resolved in favor of the deferrable server.
Consumption:
Replenishment:
Server priority activation time:
The server deadline is computed the same as for DSS.
The replenishment is not done in chunks. Instead, each time t that the server suspends (either because its queue is empty or because it has consumed all of its budget) the budget is set to zero and a single replenishment of size es is scheduled.
The time of this replenishment is t + (cs - r)ps/es, where r is the amount of the server budget that is remaining at time t.
This algorithm is much simpler than the DSS because it does not have to manage more than one replenishment event, but the performance is generally about as good.
Do not be misled by the work "exchange" to assume that the Deadline Exchange Server is the same idea as the Priority Exchange Server of Lehoczky, Sha, and Strosnider or the Dynamic Exchange Algorithm of Spuri and Buttazzo.
The following graphs show the comparative performance of four different deadline-based aperiodic server scheduling algorithms, based on a simulation.
The simulations used three different simulated periodic task sets. The aperiodic task arrivals and execution times were generated pseudo-randomly, according to an inverse exponential distribution.
The M/M/1 curve indicates the response time if the aperiodic tasks were served by a dedicated CPU of their own. The M/M/(1-U) curve indicates the response time if the aperiodic tasks were served by a dedicated CPU with speed U, where U is the bandwidth allocated to the aperiodic server.
There is something wrong about the labeling on some of the plots below, in particular where the periodic load is claimed to be 69% and the M/M/0.12 server is claimed for comparison. I should re-run these experiments to see what is the real problem.
I am no longer satisfied with the explanation in the DSS paper about why the response time at low load levels suddenly jumps up between period 43200 and 86400. This deserves further explanation.
The work on the EDF deferrable and sporadic servers was done by an FSU student, Teguh Ghazalie, with my supervision and assistance, as part of a master's thesis around 1993-1994.
Theorem: A system of independent preemptable sporadic jobs is schedulable according to the EDF algorithm if the total density of all active jobs in the system is no greater than 1 at all times.
Here the density of sporadic job Ji with release time ri maximum execution time ei and absolute deadline di is ei/(di-ri).
Variations on definition of density:
This refers to jobs, not tasks.
The term "density" is define here for a job.
The mixure of notation is a bit confusing, since in this context di - ri is the relative deadline, and for a task the realtive deadline is di.
The density of a sporadic task is defined to be ei/min di if we assume di ≤ pi, or ei/min (di,pi) in general.
A CUS is always given enough budget to complete the job at the head of its queue each time its budget is replenished. The deadline is adjusted so that the instantaneous utlization (density) is always equal to us.
Here we deviated from J. Liu's notation by omitting the tilde over the 'u' in the notation us for the instantaneous utilization of the server, because it is difficult to produce in HTML.
Question in class: Why not combine all the queued jobs into one big job, and set the budget big enough to complete them all?
Answer: This could be done, but to do so would lower the priority (postpone the deadline) of all but the last job in the group. Thus, we would have potentially poorer reponse time for all but the last job in the group.
On page 223, Jane Liu mentions a way of removing the assumption that the execution times of jobs are known at the times of their arrivals. The wording is a bit cryptic, but I believe what she intends is the following.
I believe this is less effective than the DXS, since with the DXS replenishments occur sooner.
For example, suppose we have server budget u and use a fixed nominal aperiodic task execution time (i.e., quantum) e. With the modified CBS when a task with execution time e1 arrives at time t1 and finds an empty system, the server is initialized with budget e and deadline t+e/u. If ei ≤ e, the server will complete the job no later than the deadline, say at time t'1. If by the deadline there is another job in the server queue, with execution time e2, the server budget will be replenished to e and the deadline will be adjusted to t + (e1 + e)/u.
With the DXS, the server also starts out with budget e and (if a lower priority task was executing) deadline t+e/u. If ei ≤ e, the server will complete the job no later than the deadline, say at time t'1. At that time the budget will be set to zero and a replenishment will be scheduled for time t+e1/u. At time t+e1/u, the replenishment will occur and the budget will be set to e. This replenishment will occur earlier than with the CBS.
Consider in class going through the algorithm to see what happens with this algorithm if we don't know the execution times of aperiodic jobs, and simply use a fixed constant for the budget e.
Replenishment Rules:
Note that the main difference between this algorithm (TBS) and the preceding one (CBS) is that replenishments can occur before the period has expired. When a job completes before the server deadline, and there is another job waiting, the two are effectively combined into one. That is, the server is immediately replenished, but the deadline is dropped back to what it would have been if the two jobs had arrived together and been treated as a single job.
Jane Liu mentions that her comment on the Constant Bandwidth Server (about adapting it to a timeslicing model for situations where the execution times of aperiodic jobs are not known a priori) also applies to the TBS.
Reconsidering our earlier, suppose we have server budget u and use a fixed nominal aperiodic task execution time (i.e., quantum) e. With the modified TBS when a task with execution time e1 arrives at time t1 and finds an empty system, the server is initialized with budget e and deadline t+e/u. If ei ≤ e, the server will complete the job no later than the deadline, say at time t'1. If at that time there is another job in the server queue, with execution time e2, the server budget will be replenished to e and the deadline will be adjusted to t + (e1 + e)/u.
It seems that there are too many different aperiodic server algorithms, which no clear guidance which one to use. Is one of these "best" overall? I'm not sure anyone has actually yet described the best algorithm, or done a good job of comparing the merits of the algorithms that have already been described. The above is my attempt to cut through this confusion.
Based on these principles, I proposed the following "ideal" aperiodic server algorithm.
The server has a fixed budget quantum qs, a fixed utilization us. Define ps = qs/us, which we call the "period" of the server.
The proposal above is intended as a challenge. It may or may not describe a valid EDF server scheduling policy, in the sense that it may or may not allow the server to cause more interference for other tasks than could a sporadic task with the same utilization. In other words, no one has proved that the EDF utilization bound result would not apply with this server scheduling policy.
I also don't know for certain that the policy described above will not turn out to be equivalent to one of the published algorithms, and (assuming it is correct and different) I certainly don't know how the performance compares. I'm suggesting that finding the answer these questions as a final student project for the course.
Note that the version of the algorithm above is a modification of a different proposal made in the previous offering of this course. One student took up the challenge, and gave evidence that led to discovery that the previous proposal was overly aggressive. The new proposal also has not been proven, and so may also suffer from such a bug.
Imagine what would happen with the above algorithm, or with the other bandwidth preserving algorithms, if we hold the server utilization constant and decrease the server period (and budget quantum) down toward zero?
I believe the response time for short jobs, and the average response time should improve. (Why do I believe this? Do you believe it?) On the other hand, the scheduling overhead will eventually become larger than the useful work that is done.
Consider whether the above are "fair", using examples.
| uk / ( | n ∑ i=1 |
ui) |
* Nonpreemptive GPS for packet scheduling is covered in Chapter 11, along with some of the the rest of the huge amount of research that has been done on real-time data communication and networking. We will probably not have time to get to that this term, but you should be aware that it exists.
The effect of the WFQ deadline mechanism is to achieve fairness among the processors that are active at any instant.
| T. P. Baker. ($Id: servers.html,v 1.1 2008/08/25 11:18:48 baker Exp baker $) |