cs358 Lecture Notes Week 8, Tuesday Queuing theory -------------- Interesting things about queues 1) often, the longer you have been waiting, the longer you expect to wait 2) random arrivals yield exponential interarrival times 2) Little's law 3) transient effects 4) one queue is better than many (assuming constant number of servers) 5) shortest job first minimizes average turnaround time Background ---------- A random variable is like an urn full of marbles -- it determines how often each value (color) occurs. Or, you can think of it in terms of a histogram. Random variables usually denoted with capital letters. You can think of an RV as the output of a RNG. An alternate way to think about a distribution is to ask: Given a random variable T, what is the probability that a given sample is less than x? Pr {T < x} is a function of x. This function is known as the cumulative distribution of T (or CDF). As x increases, Pr {T < x} gets bigger and bigger. Survival curve for humans. Life expectancy. UBNE vs NBUE ------------ survival curves and remaining lifetimes 1) expected lifetime vs. age 2) expected remaining lifetime vs. age 3) median remaining lifetime (medical prognoses) The Median is Not the Message by Steven Jay Gould http://cancerguide.org/median_not_msg.html Some common distributions and their expected remaining lifetimes. 1) uniform 2) Pareto (distribution of lifetimes for UNIX jobs, file sizes) 3) exponential Exponential distribution is Markovian (historyless) Example 1: Doesn't matter how long you've been waiting. The chance of an arrival in the next interval is the same. Example 2: Your chance of living to 150, given that you are 100 are the same as your chance of living to 50 at birth. If human lifespans were distributed exponentially. But they're not. Actual distributions with UBNE property 0) time to failure for new electronic components 1) lifetimes of premature babies, cancer patients, new motorcycle riders 2) wait times for elevators (cancel buttons) 3) transaction times at banks, checkout Random arrivals --------------- Random arrivals: 1) people at a service station 2) particles at a sensor 3) planes, trains and automobiles How long do you have to wait for a customer, particle, or bus? Random arrivals yield exponential interarrival times. Derivation ---------- Rate of arrivals is lambda. In a large interval with duration t, the expected number of arrivals is lambda t. In a small interval dt, the probability of finding one arrival is lambda dt. But in a large interval it is nontrivial to figure out the probability of 1, 2, or more arrivals. One the other hand, we can figure out the prob of zero arrivals in time T, which gives us the distribution of interarrival times. Pr {zero arrivals in time x} = Pr {T >= x} Pr {zero arrivals in time x} = P0 (x) I don't know what P0(x) is, but I can write a recurrence relation about it. P0(x + dx) = P0(x) (1 - lambda dx) Subtracting P0(x) from both sides yields P0(x + dx) - PO(x) = P0(x) (1 - lambda dx) - P0(x) = P0(x) (1 - lambda dx - 1) = - P0(x) lambda dx Dividing through by dx yields P0(x + dx) - PO(x) ------------------ = - lambda P0(x) dx In the limit as dx goes to zero, the thing on the left is d/dx P0(x) = -lambda P0(x) What function is its own derivative multiplied by a constant? P0(x) = K exp (-lamba x) This is the only function that satisfies the diff eq. Using the boundary condition P0(0) = 1, we get K=1. Pr {T >= x} = exp (- lambda x) Pr {T < x} = 1 - exp (- lambda x) The mean of this distribution is 1/lambda, which is the average time between arrivals, which makes sense if lambda is the rate of arrivals. Conclusion for day one: if people have no particular preference for when during a day they go for service, then: 1) from a client's point of view, his arrival time is uniformly distributed during the day 2) from the server's point of view the time between arrivals is distributed exponentially, which implies 3) how long you have been waiting is irrelevant for predicting the time of the next arrival. Queueing systems ---------------- Find the distribution of queue lengths. n is the number of people in queue, including the person in service. pn(t) is the probability that there are n people in queue at time t. Interarrival times are distributed exponentially. Rate of arrivals is lambda. Service times are distributed exponentially. Rate of departures is mu. (What do we think of these assumptions?) Because the arrival and departure processes are memoryless, future behavior depends only on current state, not on past information. Therefore: pn(t + dt) = pn(t) Pr {no arrivals and no completions} + pn-1(t) Pr {one arrival and no completions} + pn+1(t) Pr {no arrivals and one completion} Of course, there are never fewer than zero people in queue, so p-1(t) = 0 We assume that dt is so small that the probability of more than one event (arrival or completion) is zero. In a small interval dt, the probability of one arrival is lambda dt. The probability of finding one departure is mu dt. pn(t + dt) = pn(t) (1 - lambda dt) (1 - mu dt) + pn-1(t) lambda dt (1 - mu dt) + pn+1(t) (1 - lambda dt) (mu dt) Combining all the terms, we can eleminate anything with dt^2 in it... pn(t + dt) = pn(t) (1 - lambda dt - mu dt) + pn-1(t) lambda dt + pn+1(t) mu dt Subtracting pn(t) from both sides and dividing through by dt yields d pn(t) ------- = - (lambda + mu) pn(t) + mu pn+1(t) + lambda pn-1(t) dt As t gets large, the system reaches steady state if and only if lambda < mu. If the arrival rate is greater than the departure rate, then the queue length goes to infinity. Steady state means that the probabilities associated with each queue length stop changing. In other words, their derivatives are zero. Setting d pn(t)/dt to zero yields pn+1 = (lambda + mu) / mu * pn - lambda / mu * pn-1 Notice that pn is no longer a function of t (in steady state). The solution of this difference equation is pn = (lambda / mu)^n p0 lambda / mu is so useful that it is common to write rho = lambda/mu pn = rho^n p0 To find p0, we note that the sum of the pns must be one. sum_0^infinity rho^n = 1 / (1 - rho) Thus p0 = 1- rho The chance of finding the system idle is 1-rho. Thus, rho is the chance of finding the system busy, sometimes called the load. pn = rho^n (1- rho)