11 - Queueing analysis

Summary

‘It is very difficult to make an accurate prediction, especially about the future.’

Niels Bohr

At the beginning of our study of computer-systems performance analysis, it was pointed out that there are three fundamental techniques that can be used to find the desired solution to a performance-analysis problem. We have so far examined measurement and simulation techniques. The third and final fundamental solution technique is analytical modeling.

In the memory-performance example in Section 1.3, we developed a very simple analytical model to estimate the memory delay observed by an application program. This equation required only a few pieces of information, specifically, the times required to service a cache hit and a cache miss, and the miss ratio of the application program. Even though this analytical model was a tremendous over-simplification of the performance of a complex memory hierarchy, it can help us develop some insight into the performance trade-offs that are made in a memory subsystem. In this chapter, we extend our view of analytical modeling to provide greater insights into the performance of a computer system than are possible when using only this simple type of intuitive model.

Queueing analysis is an important analytical modeling technique for computer systems. There is a very large body of literature on this topic, and hundreds of new research papers and books are being published every year. This chapter will only scratch the surface of queueing analysis by focusing on a few of the fundamental results that form the basis of the more complex analytical modeling techniques. Fortunately, these fundamental results are often sufficient for answering many of the basic questions you are likely to have about a computer system.