Feedback Control for Computer Systems

Chapter 16. Case Study: Waiting-Queue Control

Queueing systems are ubiquitous, and they are always somewhat nerve-racking because they are inherently unstable. If we don’t do something to handle the work items that are being added all the time, the queue will “blow up.” Queueing systems require control to function properly. However, the very nature of queueing systems prevents the straightforward application of feedback principles.

On the Nature of Queues and Buffers

Why do queues exist? They do not simply occur because resources are insufficient to handle incoming requests. Insufficient resources are the reason for exploding queues but not for queues in general.

Queues exist to smooth out variations. If customers arrived at (say) a bank in regular intervals and if each transaction took the same amount of time, then there would be no queues: we could schedule tellers to meet demand exactly. In fact, many automated manufacturing lines work in precisely this way. But if customers arrive randomly and if transactions can take up different amounts of time, then there will be moments when demand can (temporarily) not be met. This happens even if the tellers’ processing capacity is not less than the average arrival rate. There are only two ways to avoid such random accumulation of pending requests: scheduling arrivals periodically (thus reducing variation) or having an excess capacity of resources to handle requests (enough tellers to deal with anything). The first of these options is often ...