HANDLING OVERLOAD CONDITIONS - Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications - page 325

SOLUTION 2: BUDGET OVERRUN

The second approach consists in entering a critical section without performing any
budget check. When the budget is exhausted inside a resource, the server is allowed to
consume some extra budget until the end of the critical section. In this case, the max-
imum extra budget must be estimated off-line and taken into account in the schedu-
lability analysis. An example of such a strategy is illustrated in Figure 9.23. In this
example, at time t =5, when the budget is exhausted inside the resource, τ 2 is allowed
to continue the execution until the end of the critical section, consuming 2 extra units
of budget. In the worst case, the extra budget to be taken into account is equal to the
longest critical section of the served task.

normal execution

critical section

τ 1

served
task

server
budget

0 2 4 8 10 12 14 16 18 20 22

Figure 9.23 Example of budget overrun to allow resource sharing within reservations.

This approach was first proposed by Abeni and Buttazzo under EDF, using a Constant
Bandwidth Server (CBS) [AB04]. Then, it was analyzed under fixed priority systems
by Davis and Burns [DB06] and later extended under EDF by Behnam et al. [BSNN08,
BNSS10]. Davis and Burns proposed two versions of this mechanism:

1. overrun with payback , where the server pays back in the next execution instant,
in that the next budget replenishment is decreased by the overrun value;
2. overrun without payback , where no further action is taken after the overrun.

Note that the first solution (budget check) does not affect the execution of tasks in
other reservations, but penalizes the response time of the served task. On the contrary,
the second solution (budget overrun) does not increase the response time of the served
task at the cost of a greater bandwidth requirement for the reservation.