SKEDSOFT

the execution times of jobs in these tasks are 1, 1, 3, and 3, respectively. Each aperiodic task is executed by a server. The sizes of the servers for the tasks are 1/4, 1/8, 1/4, and 3/8, respectively. Starting from time 0, the jobs in A1, A2, and A3 arrive and keep their respective servers backlogged continuously. The first job in A4 arrives at time 18, and afterwards, the server for A4 also remains backlogged.

Figure 7–14(a) shows their schedules when the servers are total bandwidth servers. Server TBi executes Ai, for i = 1, 2, 3, 4. The numbers under each time line labeled by a server name give the deadlines of the server as time progresses. (You recall that the budget of a backlogged server is replenished and its deadline set each time it completes a job.) In particular, when the first job in A4 arrives at time 18, the deadlines of servers TB1, TB2, and TB3 are 36, 40, and 36, respectively. Since the deadline of TB4 is first set to 26 and, upon the completion of the first job in A4, to 34, TB4 executes until 24, starving the other servers in (18, 24). Before time 18, the amounts of time allocated to the servers according to their sizes are 4.5, 2.25, and 4.5 respectively, but because TB4 is idle and the time left unused by it is shared by backlogged servers, the servers have executed for 8, 4, and 6 units of time, respectively. In contrast, their fair shares of processor time should be 7.2, 3.6, and 7.2, respectively. (The fair fractional share of a backlogged server in a time interval is equal to its size divided by the sum of sizes of all servers backlogged during the interval. So the fair shares of the three servers are 2/5, 1/5, and 2/5 of 18.) This example supports our intuition: The closer the consecutive deadlines (i.e., the larger the server size and the smaller the execution times of jobs), the larger share of background time a server attains at the expense of other backlogged servers.

Now suppose that each aperiodic task Ai is executed by a starvation-free constant utilization/background server CUi, for i = 1, 2, 3, 4. We have the schedule shown in Figure 7–14(b). At time 6, the budgets of all three backlogged servers are exhausted, and the system

becomes idle. According to rule R4, all three servers gets their new budgets and deadlines. Similarly, their budgets are replenished at time 12. Starting from time 18, all four servers are backlogged, and hence the schedule shown here. It is evident that none of the servers suffers starvation. After time 18, the normalized services of all servers are identical in time intervals of length 24 or more. Before 18, the background time left unused by the idle server is not distributed to backlogged servers in proportion to their sizes, however. In this example, the servers have executed for 6, 3, and 9 units of time before 18. This illustrates that although the enhanced constant utilization server algorithm eliminates starvation, it does not ensure fairness. Moreover, it is difficult to determine how the background processor time will be distributed among backlogged server in general.