Diferrable Servers

DEFERRABLE SERVERS: A deferrable server is the simplest of bandwidth-preserving servers. Like a poller, the execution budget of a deferrable server with period ps and execution budget es is replenished periodically with period ps . Unlike a poller, however, when a deferrable server finds no aperiodic job ready for execution, it preserves its budget.

Operations of Deferrable Servers: Specifically, the consumption and replenishment rules that define a deferrable server (ps , es) are as follows.

1. Consumption Rule: The execution budget of the server is consumed at the rate of one per unit time whenever the server executes.
2. Replenishment Rule: The execution budget of the server is set to es at time instants kpk, for k = 0, 1, 2, . . . .

We note that the server is not allowed to cumulate its budget from period to period. Stated in another way, any budget held by the server immediately before each replenishment time is lost.

As an example, let us look again at the system in Figure 7–2. Suppose that the task (2.5, 0.5) is a deferrable server. When it finds the aperiodic job queue empty at time 0, it suspends itself, with its execution budget preserved. When aperiodic job A arrives at 0.1, the deferrable server resumes and executes A. At time 0.6, its budget completely consumed, the server is suspended. It executes again at time 2.5 when its budget is replenished. When A completes at time 2.8, the aperiodic job queue becomes empty. The server is suspended, but it still has 0.2 unit of execution budget. If another aperiodic job arrives later, say at time 4.0, the server resumes at that time. Figure 7–3 gives another example. Figure 7–3(a) shows that the deferrable server TDS = (3, 1) has the highest priority. The periodic tasks T1 = (2.0, 3.5, 1.5) and T2 = (6.5, 0.5) and the server are scheduled rate-monotonically. Suppose that an aperiodic job A with execution time 1.7 arrives at time 2.8.

1. At time 0, the server is given 1 unit of budget. The budget stays at 1 until time 2.8.When A arrives, the deferrable server executes the job. Its budget decreases as it executes.
2. Immediately before the replenishment time 3.0, its budget is equal to 0.8. This 0.8 unit is lost at time 3.0, but the server acquires a new unit of budget. Hence, the server continues to execute.
3. At time 4.0, its budget is exhausted. The server is suspended, and the aperiodic job A waits.
4. At time 6.0, its budget replenished, the server resumes to execute A.
5. At time 6.5, job A completes. The server still has 0.5 unit of budget. Since no aperiodic job waits in the queue, the server suspends itself holding this budget.

Figure 7–3(b) shows the same periodic tasks and the deferrable server scheduled according to the EDF algorithm. At any time, the deadline of the server is equal to the next replenishment time.
1. At time 2.8, the deadline of the deferrable server is 3.0. Consequently, the deferrable server executes at the highest-priority beginning at this time.

2. At time 3.0, when the budget of the deferrable server is replenished, its deadline for consuming this new unit of budget is 6. Since the deadline of J1,1 is sooner, this job has a higher priority. The deferrable server is preempted.
3. At time 3.7, J1,1 completes. The deferrable server executes until time 4.7 when its budget is exhausted.
4. At time 6 when the server’s budget is replenished, its deadline is 9, which is the same as the deadline of the job J1,2. Hence, J1,2 would have the same priority as the server.

The figure shows that the tie is broken in favor of the server.

Again, the scheduler treats a deferrable server as a periodic task. As you can see from the rules of the deferrable server algorithm, the algorithm is simple. The scheduling overhead of a deferrable server is no higher than that of a poller.
The responsiveness of the system can be further improved if we combine the use of a deferrable server with background execution. In other words, we also use a background server. This server is scheduled whenever the budget of the deferrable server has been exhausted and none of the periodic tasks is ready for execution. When the background server is scheduled, it also executes the aperiodic job at the head of the aperiodic job queue. With such a server, job
A in Figure 7–3(a) would be executed from time 4.7 and completed by time 5.2, rather than 6.5, as shown in the figure.