CS 455 Lecture Notes

Week Eleven, Tuesday: Queues

Introduction to Queues

A queue is a data structure with many commonly occurring physical counterparts. If a resource is in short supply, people have to wait for it. Waiting in a line (queue) is a civilized way to share the pain of waiting. It's fair because the first one in line gets served first. People resent late-comers shoving into the front of a line to get into a movie, for example.

Cars in traffic wait in queues too. The first car at a red light waits at the intersection. The next car to arrive stops behind the first one, and so on.

If capacity always exceeded demand, queues wouldn't be necessary. Suppose there is a bank that has an unlimited number of tellers. There would never be a line formed in the bank because there would never be any waiting for a teller (this is an example of parallel processing). Resource scarcity is a fact of life, however, and computer systems and networks are no exception.

Operating systems use queues for many things. For example, the keys pressed and mouse operations go into buffers (queues) to await processing.

If a Web server receives more page delivery requests than it can serve at once they are queued and served in order of arrival. Similarly with other network servers like a print server or file server.

Queue ADT

A queue is a data structure of ordered entities that are inserted at the rear and removed from the front. This is called a FIFO data structure.

Queue Application Example: Carwash Simulation

In physical processes, buffers are frequently encountered. For example, when you drive up to a fast food restaurant (such as MacDonald's) if it's around lunch time, you are likely to encounter some cars ahead of you waiting to order food. After you order, you might have to wait again to get to the place to pay, and you might wait again to pick up the food. This is an example of a three-station-pipelined flow with buffers. You will also encounter pipelines in computer architecture (for example, integer arithmetic and floating point arithmetic are performed in different pipelines in a CPU).

In the Networks Laboratory (Prof. Deborah Estrin) right here at USC network simulators are used for developing new network protocols. A network simulator uses queues extensively.

In designing a factory, manufacturing engineers use simulations to find out the optimal configuration and layout of a factory and to verify that the production rate will meet expectations. Factory simulations use buffers and machine simulators extensively in piplined processes (both parallel and single). Sometimes factory buffers are actually stacks and not queues, such as when a product is stacked on a pallet and removed in reverse order.

The MS text presents an example of a carwash simulation. There is only one car washing machine, so there is no parallelism and no pipeline. It's one of the simplest simulations conceivable, having only two objects, a queue and a washer. Nevertheless, it provides an interesting example if one should run the simulation with a variety of input parameters. Even the simplest simulations often provide results that are non-intuitive (therefore they are interesting).


Carwash simulation results.


This page established November 8, 1999; last updated November 8, 1999.