Other Bandwidth Preserving Services

Other Bandwidth Preserving Services

There are three other bandwidth preserving server algorithms that give a simple way to schedule aperiodic jobs in a deadline driven system. They are

1. Constant Utilization Server
2. Total Bandwidth server
3. Weighted Fair Queuing Server

All these algorithms are approximations of an ideal generalized processor sharing (GPS) algorithm. The objective is to assign a portion of available processor time to a task making it believe that it was execution on a slower processor independent of any other task. It also provides fair schedule, timing isolation or guaranteed server in each round a very small amount of time slice of length proportional to server size.

Constant Utilization Server

The server that is used to schedule aperiodic jobs along with periodic tasks in a deadline driven system is called constant utilization server. A constant utilization server reserves a non-fiction u_s’ (instantaneous utilization) of the processor time for execution of the server. Like other bandwidth preserving server, it has a budget and is defined in terms of consumption and replenishment rules.

When the budget is non-zero, the same server is scheduled with tasks on an EDF basis. The budget and deadline of the server are chosen such that the utilization of the server is constant when it executes and it is always given enough budget to complete ate the head of the queue each time its budget is replenished. The server never has budget if it has no work to do.

Consumption Rule:

A constant utilization server only consumes budget only when it executes.

Replenishment Rule:

R1: Initially, budget e_s = 0 and deadline d = 0

R2: When an aperiodic job with execution time e arrives at time t to an empty aperiodic job queue,

1. If t<d, do nothing
2. If t>=d, then set d = t+(e/u_s’) and e_s=e

R3: At the deadline d of the servers,

1. If the server is backlogged, set d = d + (e/u_s’) and e_s = e.
2. If the server is idle, do nothing.

Consider, T₁ + (4, 0.5), T₂ = (4, 1), T₃ = (19, 4.5) and u_s’ = 0.25. Similarly, the aperiodic jobs A1 = (3, 1), A2 = (6.9, 2) and A3 = (15.5, 2).

The timing diagram for the execution of these tasks is below:

Total Bandwidth Server

The constant utilization server gives a non-fraction of processor capacity to a task, but it cannot claim unused capacity to complete the task earlier. The total bandwidth server improves the responsiveness by permitting a server to claim background time not used by the periodic task. This is achieved by having the scheduler replenish the server budget as soon as the budget is exhausted if the server is backlogged or as soon as the server becomes backlogged. For, a given set aperiodic jobs and server size, both total bandwidth server and constant utilization server have the same sequence of deadlines but the budget of a total bandwidth server may be replenished earlier than that of a constant utilization server.

Consumption rule:

A total bandwidth server only consumes budget when it executes.

Replenishment rule:

R1: Initially, e_s = 0 and d = 0

R2: When an aperiodic job executes arrive, at time t to an empty periodic job queue, set di=max (d, t) + e/u_s’ and e_s = e.

R3: When the server completes current aperiodic the job is removed from the queue and

1. If the server is backlogged, set d = d + e/u_s’ and e_s = e
2. If the server is idle, do nothing

Weighted Fair Queuing Server

The objective of constant utilization server and total bandwidth server is to assign some fraction of processor capacity to a task. When assigning the capacity there is the issue of fairness. A scheduling algorithm is said to be fair within any particular time interval of the fraction of processor time in the interval obtained by each backlogged server is proportional to the serve size. In such cases, not only all the tasks met their deadline, but they all make continual progress according to their share of the processor and no starvation occurs.

References

Liu, Jane W. S. Real Time Systems. Integre Technical Publishing Co., Inc, January 10, 2000. Print.