|
|
|
|
|
|
|
More sophisticated processorsincluding certainly almost all pipelined processorsmake buffered requests to memory, unless a cache is used. Even with pipelined processors that use cache, some of the requests (such as writes) may be buffered. Whenever requests are buffered, the effect of contention and the resulting delay are reduced. The simple models fail to accurately represent the processor-memory relationship. More powerful tools that incorporate buffered requests are needed. For these tools, we turn to queueing theory. |
|
|
|
|
|
|
|
|
Open- and closed-queue models are frequently used in the evaluation of computer system designs. In this section, we review and present the main results for simple queueing systems without derivation of the underlying basic queue equations. While queueing models are useful in understanding memory behavior, they also provide a robust basis to study various computer system interactions, such as multiple processors and I/O. The reader is referred to Kleinrock [166] and Kobayashi [169] for a more general treatment of queueing theory. |
|
|
|
|
|
|
|
|
Suppose requestors desire service from a common server. These requestors are assumed to be independent from one another, except that they make a request on the basis of a probability distribution function called the request distribution function. Similarly, the server is able to process requests one at a time, each independently of the others, except that the service time is distributed according to the server probability distribution function. The mean of the arrival or request rate is measured in items per unit of time and is called l, and the mean of the service rate distribution is m. The ratio of arrival rate to service rate (r) defines a very important parameter in queueing systems called the utilization or the occupancy. |
|
|
|
|
|
|
|
|
The higher the occupancy ratio, the more likely it is that requestors will be waiting (in a buffer or queue) for service and the longer the expected queue length for items awaiting service. In open queueing systems, if the arrival rate equals or exceeds the service rate, an infinitely long queue develops in front of the server, as requests are arriving faster than or at the same rate at which they can be served. For open-queue systems, arrivals are truly independent of the server or the queue length. For closed-queue systems, the rate of arrival of requests is in some way limited or governed by the performance of the server. |
|
|
|
|
|
|
|
|
The simplest queueing models are open-queueing models, where the arrival and service distribution are known. |
|
|
|
| |
|
|
|
|
As processors have become increasingly complex, their performance can be predicted only statistically. Indeed, oftentimes running the same job on the same processor on two different occasions may create significantly different execution times (based perhaps on the initial state of the list of available pages maintained by the operating system). Queueing theory has been a powerful tool in evaluating the performance of not only memory systems, but also I/O systems, networks, and multiprocessor systems. |
|
|
|
|
|
|