The Constant Bandwidth Server (CBS) is an algorithm for providing temporal protection and real-time guarantees to real-time sporadic tasks. Recently, an implementation of this algorithm called SCHED_DEADLINE has been included in the Linux kernel. Therefore, the CBS algorithm is now used to serve more generic tasks than do not obey to the classical sporadic task model. One important type of tasks which was not considered by the original CBS algorithm is the so called “self-suspending task model”, where a task instance can suspend itself waiting for an external event. Even if the original algorithm is adapted so that the temporal protection property continues to hold, it is difficult for developers to provide guarantees and to select the most appropriate server parameters for such tasks. This paper investigates the problem of using the CBS algorithm for serving self-suspending tasks, by analysing it from a theoretical point of view and showing how to select the server parameters (budget and periods) for self-suspending tasks. Finally, the effectiveness of these proposals is shown through both simulations and real experiments on Linux / SCHED_DEADLINE.
This work has been partially supported by the 7th Framework Programme JUNIPER (FP7-ICT-2011.4.4) project, founded by the European Community under grant agreement n. 318763. a regular/periodic activation/execution pattern. Moreover, the CBS allows tasks to execute earlier (consuming some of their future reserved time) if there is enough idle time in the system.
The CBS algorithm also provides real-time guarantees to
sporadic real-time tasks that respect the so-called Liu and
Layland task model [
For real-time applications, the temporal protection property
is as important as the traditional memory protection (or
address space protection) mechanism provided by
generalpurpose Operating Systems (OSs). As a matter of fact, some
general-purpose OS kernels started to use some temporal
protection mechanisms to bound the amount of execution
time used by fixed priority (real-time) processes or threads.
For example, the Linux kernel provides a mechanism called
RT throttling to avoid the risk that a high-priority real-time
process starves all the other applications in the system. It
can be considered as a first necessary step to allow non
privileged users to use real-time priorities. Although RT
throttling is useful in many situations and can achieve its goals
in general, it lacks a strong theoretical foundation; hence, it
is not possible to provide a complete schedulability analysis.
Moreover, processes or threads characterised by aperiodic /
irregular arrival / execution patterns can end up consuming
more CPU time than expected, compromising the real-time
performance of the other ones (because, for example, of the
infamous deferrable server problem [
To address this issue, and to allow the predictable
execution of real-time application without starving the non
realtime ones, an implementation of the CBS algorithm, named
SCHED_DEADLINE [
Thanks to SCHED_DEADLINE, it is possible to use the CBS to schedule every application that can run on a Linux-based OS, including applications that were not originally developed with the Liu and Layland task model in mind. Of course, this fact provides new interesting possibilities, but also raises some issues: how to provide real-time guarantees to such tasks (which do not respect the original Liu and Layland model)? How to assign the CBS parameters to them? One important task model which was not considered by the original CBS is the self-suspending task model, in which tasks can self-suspend waiting for external events. For example, a task may suspend waiting for the response of a hardware device, the response of a server or from a co-processor. Tasks that make use of the GPU can be typically modelled as self-suspending tasks. The CBS algorithm and the SCHED_DEADLINE implementation, interpret every suspension as an end-of-instance; therefore, it is difficult to provide guarantees to self-suspending tasks scheduled by the CBS algorithm, and it is not easy to select the most appropriate budget and period for such tasks.
While the problem of analysing self-suspending tasks has
already been addressed in the real-time systems literature
[
In this paper, we address this problem first from the theoretical point of view: after recalling the algorithm in Section 2, we propose one alternative rule for the algorithm in Section 2.2. Moreover, in Section 3 we analyse the problem of setting the CBS parameters for a self-suspending task. In Section 4 we show a set of simulation experiments on synthetically generated tasks set to evaluate the proposed methodology. Finally in Section 5 we discuss related work, and in Section 6 we present our conclusions.
The original CBS algorithm has been designed to schedule real-time tasks which can be described by the so-called “Liu and Layland real-time task model” (each real-time task can be modelled as sequences of jobs that never block). In this section, after quickly recalling the original model and algorithm, we show how the original CBS can be easily modified to serve real-time tasks that do not respect such a strict model.
Traditionally, a real-time task τi is modelled as a stream of jobs Ji,j , with the jth job of the task (named Ji,j ) arriving (becoming ready for execution) at time ri,j , executing for a time ci,j and finishing at time fi,j . Each job is also characterised by an absolute deadline di,j which is respected if fi,j ≤ di,j . Notice that job Ji,j never blocks, so it is ready for execution from time ri,j to time fi,j .
Based on these definitions (which characterise the previously mentioned “Liu and Layland real-time task model”), the CBS algorithm was defined as follows: 1. A real-time task τi can be associated to a CBS (representing a CPU reservation) in order to schedule it 2. The CBS associated to task τi is characterised by a budget qis and by an ordered pair (Qis, Tis), where Qi s is the maximum budget and Tis is the so called server period (or reservation period). A scheduling deadline dis is also associated to the CBS 3. The CBS associated to task τi is said to be active at time t if there are pending jobs for task τi; that is, if there exist a job Ji,j such that ri,j ≤ t < fi,j . A CBS is said to be idle if it is not active 4. When a job Ji,j of a task τi served by an active CBS arrives, a request is enqueued 5. When a job Ji,j of a task τi served by an idle CBS arrives, if qis ≥ (dis − ri,j) QTsis then the CBS generates i a new scheduling deadline dis = ri,j + Tis and the budget is recharged to the maximum value Qis: qis = Qis. Otherwise, the job is served with the current scheduling deadline and budget 6. Whenever a task τi served by a CBS executes for a time δ, the budget qis is decreased accordingly: qis = qis − δ 7. When qis = 0, it is recharged to the maximum value s Qi , and the scheduling deadline is postponed by one server period Tis: qis = Qis, dis = dis + Tis 8. When a job finishes, the next pending job for the task, if any, is served using the current budget and scheduling deadline. If there are no pending jobs, the CBS becomes idle.
According to these rules, every active real-time task is ass signed a scheduling deadline di , which is used by an EDF scheduler to decide which task to execute at any time instant.
If U = Pi QTsis ≤ 1, it can be proved that the finishing time
i
of every job will be smaller than the scheduling deadline of
the task at the instant of the job completion (see Theorem
1 in [
Thanks to this temporal protection property provided by the
CBS algorithm, it is possible to ensure that all the deadlines
of all the jobs of task τi will be respected by setting Qis ≥
maxj {ci,j } and Tis ≤ minj{ri,j+1 − ri,j}. This is known as
hard schedulability property. It is also possible to perform a
stochastic/probabilistic analysis to provide an upper bound
for the probability of missed deadlines for each single task
τi [
As already mentioned, the algorithm description presented above (which is basically the original CBS) assumes that each real-time task τi served by a CBS blocks only when a job finishes, and then wakes up when the next job arrives. Examples can be a periodic task that only blocks waiting for a periodic timer (which is used to activate the various jobs) or a sporadic task that only blocks waiting for the event that activates the next job. For these tasks, a job Ji,j can be described by its arrival time ri,j, its deadline di,j , and its execution time ci,j .
There are two reasons for this assumption. The first one is the simplicity of implementation in the kernel: every time the task blocks the kernel interprets this event as end-of-job; and every time the task is unblocked, the kernel interprets is as a new job activation. The second reason concerns the behaviour of the algorithm: if a job blocks on some other event different from a job completion (for example, on a file descriptor waiting for data coming from an external device), the scheduler has to be modified to properly handle this situation so that the CBS properties are not broken. In particular, if the remaining budget and scheduling deadline are not correctly updated the temporal protection property risks to be broken.
However, although the original assumption about non selfsuspending jobs can help in simplifying the scheduler, it is not realistic in practice: a job Ji,j of a real task τi might block (even multiple times) before finishing, hence describing its execution through a single execution time ci,j might be too simplistic. A more realistic task model considers selfsuspending tasks, where job Ji,j executes for a time ci0,j , then blocks for a time si0,j, executes for a time ci1,j, blocks for a time si1,j , etc... In other words, Ji,j is composed by ki,j different segments, having execution times ci0,j . . . cik,ij,j , and between segment h and segment h + 1 the job sleeps for a time sih,j.
In order to be really usable in practice, a modern CBS implementation (such as SCHED_DEADLINE) has to correctly support self-suspending tasks, hence both the two problems mentioned above have to be addressed. As a result, it is important to understand how to adjust the budget and the scheduling deadline when a job of the task blocks and unblocks (between two consecutive segments). A first idea could be to use the original CBS “wake up rule” (rule 5) for all the wake-ups (even if a new job is not arrived). Such a rule, which was used by the original CBS algorithm only when a new job Ji,j arrives (at time ri,j ) performs the following check: s qis ≥ (dis − ri,j) QTsi .
i
If the condition holds, it is necessary to compute a new
budget and a new scheduling deadline, otherwise the old ones
can be re-used without compromising the CBS properties
[
The rule can be informally explained as follows: the scheduler checks if the fraction of CPU time that the job will use f(rgoivmennbowy tthoe tchuerrsecnhtebduudlignegt dqiseaddilvinidee)disbylatrhgeertitmheandisQT−sisrio,jr not:
s qis ≥ (dis − ri,j) QTsi ⇒ i
qis dis − ri,j
s ≥ Qi
Tis If this condition is true, then the task cannot be scheduled using the current scheduling deadline and the current (1) i (2) budget, because it would consume a fraction of CPU time larger than Qis/Tis, breaking the temporal protection property. The solution used in the original paper was to generate a new scheduling deadline dis = ri,j + Tis and a new budget qis = Qis so that the condition is verified.
When considering self-suspending tasks, the same deadline assignment rule can be re-used to check if the current scheduling deadline dis and budget qis can be used when a job wakes up at time t (at the beginning of a new segment). However, other approaches could also be used. For example, it is possible to set s qis = (dis − t) QTsi i (3) and leave dis unchanged thus preserving the bandwidth limit. This will be referred as revised wake-up rule in the rest of the paper.
The solution adopted in the original paper makes sense for new job arrivals (because it tries to associate a new deadline equal to ri,j + Tis to each job), but can have bad effects on the task’s response times when other kinds wake-ups happen. The revised wake-up rule discussed above (decrease the current budget leaving the scheduling deadline unchanged), instead, could be more useful when the wake-up does not correspond to a new job arrival, because it allows to continue serving the current job with the current scheduling deadline.
When considering only non self-suspending tasks,
configuring the CBS parameters Qis and Tis is pretty simple: for
example (as already mentioned) if Qis ≥ maxj{ci,j } and
Tis ≤ minj{ri,j+1 − ri,j} then the deadlines of all the jobs
Ji,j of task τi will be respected (regardless of the behaviours
of all the other tasks running in the system). In particular,
for periodic tasks τi with ri,j+1 −ri,j = Pi it is possible to set
Tis = Pi. Although smaller values of Tis are sometimes used
when performing stochastic analysis [
Hence, in order to have a better control on the worst-case real-time performance of self-suspending real-time tasks scheduled by a CBS it could be useful to set Tis < Pi; in particular, Tis = Pi/R, with R ∈ N .
Reducing the value of Tis (while keeping the ratio Qis/Tis constant), it is possible to have a better control on the jobs’ response times (at the cost of a larger number of preemptions). In particular, when Tis → 0 (and consequently Qis → 0) the finishing time for the job becomes:
Tis,Qis→0 ri,j + lim 0 ci,j Qs
i + 1 ci,j Qs i Tis − Qis + (ci0,j %Qis) + si,j
Tis − Qis + (ci1,j%Qis) =
0 1 = ri,j + cQi,sj Tis + si,j + cQi,sj Tis i i because Tis → 0 ⇒ Qis → 0, Tis → 0 ⇒ ⌈ci0,j /Qis⌉ → ci0,j /Qis, and Tis → 0 ⇒ ci0,j %Qs → 0. This is the so called “fluid flow execution model”, according to which every task executes in parallel with the other tasks at a speed Qis/Tis. Notice that the fluid flow execution model is a mathematical abstraction which is not reasonable in practice (Tis → 0 makes no sense in a real system), but provides interesting results for comparison.
According to this model, the first segment of the job executes 0 s in ci,j (Tis/Qi ) time units, so the second segment starts a time t′′ = ri,j + ci0,j (Tis/Qis) + si,j and the job finishes at time ri,j + ci0,j QTiss + si,j + ci1,j QTiss = (ci0,j + ci1,j ) QTiss + si,j (5) i i i If Cih = maxj{cih,j } and Si = maxj{si,j }, then it is possible to say that in the (ideal) fluid flow execution model each job would respect its deadline if
s QTsi = i
Ci0 + Ci
1
Pi − Si hence in a real system (with Tis = Pi/R >> 0) the ratio between the CBS maximum budget Qis and the server period Tis should be larger than (Ci0 + Ci1)/(Pi − Si).
Notice that the discussion above has been performed considering only two segments, but can be generalised: in case of tasks with segments 0...k,
s QTsi ≥ i
Pkh=0 Cih Pi − Pkh−=10 Sih (6) (7) 2.5 s ilnde 2 a e d d e s ism 1.5 f o e g a t rcen 1 e P 0.5 0 0.6 0.65 0.7 0.75 0.8
Utilisation 0.85 0.9 0.95
The suitability of the CBS algorithm (with the two different
“wake-up rules” described in this paper and with different
Pi/Tis values) has been tested through a large set of
simulations and real experiments (based on SCHED_DEADLINE).
Both simulations and real experiments have been performed
by using some randomly generated sets of traditional and
self-suspending real-time tasks. In order to generate such
task sets, taskgen [
The simulations have been performed by using RTSim [
R 1 2 3 4 1 2 3 4 going from 0.6 to 0.95 (the results obtained on the 50 runs with the 50 different tasksets have been averaged). The figure compares the original CBS and the revised wake-up rule presented in Section 2.2, with Tis = Pi/R and R = 1..4. From this first experiment, it is possible to notice that: 1. As expected, the deadline miss probability generally increases when increasing the system utilisation U 2. The revised rule generally works better (causes less missed deadlines) than the original CBS 3. Decreasing Tis (increasing R) helps to greatly reduce the probability of missing deadlines (arriving to nearly 0 even for high system utilisations) Also notice that setting Tis = Pi/2 already allows to reduce the probability to miss a deadline to less than 0.5%, for almost all the values of the utilisation (and using the revised wake-up rule further improves the real-time performance without introducing the additional overhead of higher values of R). Finally, the real-time performance of the “pure periodic” (non self-suspending) tasks have been checked, verifying that such tasks do not miss any deadline; this proves that the temporal protection property is respected.
After evaluating the proposed approach through simulations, some experiments have been performed by running real periodic tasks on Linux 3.15.6, with the SCHED_DEADLINE scheduling policy. The experiments have been performed on an machine based on an Intel Xeon W3690 CPU (having 6 cores) running at 3.47GHz. The Linux kernel used for the experiments (3.15.6) already includes also the SCHED_DEADLINE policy which implements the original CBS algorithm, and has been modified to optionally provide the revised wake-up rule presented in Section 2.2.
The real-time tasks used for the experiments are implemented by an application called rt-app. Using this application it is possible to run on a real system the same tasksets used for the previous simulations (of course, in the real system effects like the kernel latency or some other kind of overhead can affect the results). Since each run of each experiment is 60s long, the real experiments require much more time than the simulation; hence, only some interesting number of tasks / utilisation configurations have been used. First of all, rt-app has been used to execute on a single core the tasksets simulated for N = 6, U = 0.8. The results are shown in Table 1. From the table, it is possible to notice that the results obtained in real experiments with small values of R are comparable with the simulation results, proving the accuracy of the simulation model and the correctness of the SCHED_DEADLINE implementation. However, notice that increasing R (decreasing the server period Tis) the difference between the results of the real experiments and the results of the simulations increases (in particular, the number of missed deadlines in real experiments becomes considerably larger than in simulations), because of the overhead implied by small server periods (which is not modelled in the simulations). In any case, decreasing the server period decreases the probability of missing a deadline, even in real experiments (although the performance improvement is smaller than for simulations).
Finally, notice that even in real experiments the revised CBS is able to improve the real-time performance of selfsuspending tasks respect to the original CBS. A more detailed analysis showed that the revised CBS “suffers” in real experiments more than in simulations because in practice the revised wake up rule tends to reduce the current runtime to values which are too small, and the kernel immediately sets it to 0.
Some additional experiments have been performed on multicore configurations (using 4 of the 6 cores available on the Xeon CPU) with SCHED_DEADLINE using global EDF to schedule the tasks on multiple cores based on their scheduling deadlines. In general, these experiments confirmed the initial results for example, Table 2 reports the deadline miss probabilities for self-suspending tasks measured with 16 tasks and utilisation U = 3.8 (remember that with 4 cores the utilisation should be ≤ 4). Again, both reducing the server period and using the revised wake-up rule allow to reduce the number of deadlines missed by self suspending tasks; notice that with R = 2 or R = 4 the revised rule allows to avoid any missed deadline.
The reservation approach is not new [
This paper described some issues experienced when using the new SCHED_DEADLINE scheduling policy to schedule real tasks. In particular, when considering self-suspending task the strategy used to assign scheduling parameters to tasks should be changed. It can also be argued that the rule used by the original CBS algorithm to handle tasks wake-ups should be revised, in order to properly handle the wakeups that do not correspond to new job arrivals. Simulations show that both decreasing the server period and using the revised wake-up rule improve the real-time performance of self-suspending tasks, and these results are confirmed by some experiments with real applications running on a Linuxbased machine, performed on SCHED_DEADLINE.