Alternative Approaches

This example illustrates the shortcoming of the polling approach. An aperiodic job that arrives after the aperiodic job queue is examined and found empty must wait for the poller to return to examine the queue again a polling period later. If we can preserve the execution budget of the poller when it finds an empty queue and allow it to execute later in the period if any aperiodic job arrives, we may be able to shorten the response times of some aperiodic jobs. In this example, if the poller were able to examine the queue again at time 0.1, then job A would complete in the second polling period, making its response time significantly shorter.

Algorithms that improve the polling approach in this manner are called bandwidthpreserving server algorithms. Bandwidth-preserving servers are periodic servers. Each type of server is defined by a set of consumption and replenishment rules. The former give the conditions under which its execution budget is preserved and consumed. The latter specify when and by how much the budget is replenished. We will return in Chapters 11 and 12 to discuss the implementation of such servers in networks and operating systems. For now, we assume that they work as follows:

• A backlogged bandwidth-preserving server is ready for execution when it has budget. The scheduler keeps track of the consumption of the server budget and suspends the server when the server budget is exhausted or the server becomes idle. The scheduler moves the server back to the ready queue once it replenishes the server budget if the server is still backlogged at the time.
• The server suspends itself whenever it finds the aperiodic job queue empty, that is, when it becomes idle. When the server becomes backlogged again upon of arrival of an aperiodic job, the scheduler puts the server back to the ready queue if the server has budget at the time.