lecture 14

Queuing Models
On many systems, the processes that are run vary from day to day, so there is no static set of processes (or times) to use for deterministic modeling. What can be determined, however, is the distribution of CPU and I/0 bursts. These distributions can be measured and then approximated or simply estimated. The result is a mathematical formula describing the probability of a particular CPU burst. Commonly, this distribution is exponential and is described by its mean.
Similarly, we can describe the distribution of times when processes arrive in the system (the arrival-time distribution). From these two distributions, it is possible to compute the average throughput, utilization, waiting time, and so on for most algorithms. The computer system is described as a network of servers. Each server has a queue of waiting processes. The CPU is a server with its ready queue, as is the I/0 system with its device queues. Knowing arrival rates and service rates, we can compute utilization, average queue length, average wait time, and so on. This area of study is called queuing-network analysis.
As an example, let n be the average queue length (excluding the process being serviced), let W be the average waiting time in the queue, and let ? be the average arrival rate for new processes in the queue (such as three processes per second). We expect that during the time W that a process waits, ? x W new processes will arrive in the queue. If the system is in a steady state, then the number of processes leaving the queue must be equal to the number of processes that arrive. Thus,


This equation, known as Little s formula, is particularly useful because it is valid for any scheduling algorithm and arrival distribution. We can use Little s formula to compute one of the three variables if we know the other two.