09 convoy effect

%23%20%2F%2F%2F%20script%0A%23%20requires-python%20%3D%20%22%3E%3D3.13%22%0A%23%20dependencies%20%3D%20%5B%0A%23%20%20%20%20%20%22altair%22%2C%0A%23%20%20%20%20%20%22asimpy%22%2C%0A%23%20%20%20%20%20%22marimo%22%2C%0A%23%20%20%20%20%20%22polars%22%2C%0A%23%20%5D%0A%23%20%2F%2F%2F%0A%0Aimport%20marimo%0A%0A__generated_with%20%3D%20%220.20.4%22%0Aapp%20%3D%20marimo.App(width%3D%22medium%22)%0A%0A%0A%40app.cell%0Adef%20_()%3A%0A%20%20%20%20import%20marimo%20as%20mo%0A%20%20%20%20import%20random%0A%20%20%20%20import%20statistics%0A%0A%20%20%20%20import%20altair%20as%20alt%0A%20%20%20%20import%20polars%20as%20pl%0A%0A%20%20%20%20from%20asimpy%20import%20Environment%2C%20Process%2C%20Queue%2C%20PriorityQueue%0A%0A%20%20%20%20return%20(%0A%20%20%20%20%20%20%20%20Environment%2C%0A%20%20%20%20%20%20%20%20PriorityQueue%2C%0A%20%20%20%20%20%20%20%20Process%2C%0A%20%20%20%20%20%20%20%20Queue%2C%0A%20%20%20%20%20%20%20%20alt%2C%0A%20%20%20%20%20%20%20%20mo%2C%0A%20%20%20%20%20%20%20%20pl%2C%0A%20%20%20%20%20%20%20%20random%2C%0A%20%20%20%20%20%20%20%20statistics%2C%0A%20%20%20%20)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%20The%20Convoy%20Effect%0A%0A%20%20%20%20%23%23%20*One%20Slow%20Job%20Ruins%20Everyone's%20Day*%0A%0A%20%20%20%20A%20single%20server%20processes%20jobs%20that%20arrive%20randomly%20(Poisson%20process).%20Most%20jobs%20are%20quick%20(exponential%20service%20with%20small%20mean)%2C%20but%20a%20rare%20few%20are%20very%20slow%20(exponential%20service%20with%20large%20mean).%20This%20*hyperexponential*%20service%20distribution%20has%20high%20variance.%20This%20tutorial%20compares%20the%20performance%20of%20two%20scheduling%20disciplines%20in%20this%20situation%3A%0A%0A%20%20%20%20-%20FIFO%20(First%20In%2C%20First%20Out)%3A%20jobs%20are%20served%20in%20the%20order%20they%20arrive.%0A%20%20%20%20-%20SJF%20(Shortest%20Job%20First)%3A%20the%20server%20always%20picks%20the%20shortest%20queued%20job%20next.%0A%0A%20%20%20%20The%20surprising%20result%20is%20that%20SJF%20dramatically%20outperforms%20FIFO%3A%20not%20just%20for%20the%20small%20jobs%20that%20directly%20benefit%20from%20skipping%20ahead%2C%20but%20also%20for%20mean%20sojourn%20time%20across%20*all*%20jobs.%20The%20improvement%20is%20most%20visible%20at%20the%20tail%20(95th%20and%2099th%20percentiles)%20because%20FIFO%20creates%20a%20*convoy%20effect*%3A%20one%20long%20job%20blocks%20many%20short%20jobs%20behind%20it%2C%20inflating%20everyone's%20wait.%0A%0A%20%20%20%20%23%23%23%20The%20Convoy%20Metaphor%0A%0A%20%20%20%20Picture%20a%20one-lane%20road%20with%20one%20slow%20truck%20and%20many%20fast%20cars.%20Every%20car%20behind%20the%20truck%20must%20drive%20at%20truck%20speed%3B%20no%20overtaking%20allowed.%20The%20truck%20is%20the%20long%20job%3B%20the%20cars%20are%20the%20short%20jobs%20stuck%20behind%20it%20in%20FIFO%20order.%20SJF%20is%20like%20a%20passing%20lane%3A%20fast%20cars%20jump%20ahead%20of%20the%20truck%20and%20reach%20their%20destination%20much%20sooner.%20The%20truck%20itself%20arrives%20at%20the%20same%20time%20either%20way%2C%20but%20the%20total%20delay%20experienced%20by%20all%20vehicles%20plummets.%0A%0A%20%20%20%20%23%23%23%20Why%20FIFO%20Hurts%20with%20High%20Variance%0A%0A%20%20%20%20In%20FIFO%2C%20the%20server's%20current%20job%20is%20chosen%20at%20arrival%20time%2C%20not%20at%20decision%20time.%20When%20a%20slow%20job%20begins%20service%2C%20every%20subsequent%20arrival%20must%20join%20the%20queue%20and%20wait.%20The%20expected%20excess%20work%20in%20service%20(the%20remaining%20time%20of%20the%20current%20job%2C%20seen%20by%20an%20arriving%20customer)%20under%20FIFO%20is%3A%0A%0A%20%20%20%20%24%24W_%7B%5Ctext%7BFIFO%7D%7D%20%3D%20%5Cfrac%7B%5Clambda%20%5Coverline%7Bs%5E2%7D%7D%7B2(1-%5Crho)%7D%20%2B%20%5Cfrac%7B1%7D%7B%5Cmu%7D%24%24%0A%0A%20%20%20%20where%20%24%5Coverline%7Bs%5E2%7D%24%20is%20the%20second%20moment%20of%20service%20time.%20High%20variance%20inflates%20%24%5Coverline%7Bs%5E2%7D%24%20without%20changing%20%24%5Crho%24%2C%20directly%20worsening%20wait%20time.%0A%0A%20%20%20%20%23%23%23%20SJF%20Minimises%20Mean%20Sojourn%20Time%0A%0A%20%20%20%20For%20a%20single%20server%20with%20non-preemptive%20SJF%20and%20any%20service-time%20distribution%2C%20the%20mean%20sojourn%20time%20is%20given%20by%20the%20formula%20below%20(which%20is%20discussed%20in%20%22Understanding%20the%20Math%22%20at%20the%20end%20of%20this%20lesson)%3A%0A%0A%20%20%20%20%24%24W_%7B%5Ctext%7BSJF%7D%7D%20%3D%20%5Cfrac%7B1%7D%7B%5Cmu%7D%20%2B%20%5Cfrac%7B%5Clambda%20%5Coverline%7Bs%5E2%7D%7D%7B2(1-%5Crho)%7D%24%24%0A%0A%20%20%20%20SJF%20achieves%20this%20minimum%20because%20short%20jobs%20that%20would%20otherwise%20be%20blocked%20by%20a%20long%20job%20are%20promoted%20ahead%2C%20reducing%20the%20total%20waiting%20work%20in%20the%20system.%0A%0A%20%20%20%20%23%23%20Practical%20Relevance%0A%0A%20%20%20%20Operating%20system%20CPU%20schedulers%20use%20time-quanta%20and%20priority%20aging%20to%20approximate%20SJF%20without%20knowing%20job%20sizes%20in%20advance.%20Database%20query%20planners%20estimate%20query%20cost%20and%20reorder%20execution%20to%20minimize%20blocking.%20The%20phenomenon%20reappears%20as%20*head-of-line%20blocking*%20in%20HTTP%2F1.1%20(one%20slow%20response%20stalls%20a%20connection)%2C%20motivating%20HTTP%2F2%20multiplexing%20and%20HTTP%2F3's%20QUIC%20stream%20independence.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Implementation%0A%0A%20%20%20%20Jobs%20are%20placed%20in%20a%20%60PriorityQueue%60%20for%20SJF%20(tupled%20as%20%60(service_time%2C%20job_id)%60%20so%20shorter%20jobs%20sort%20earlier)%20or%20a%20plain%20%60Queue()%60%20for%20FIFO%20(tupled%20as%20%60(job_id%2C%20service_time)%60%20to%20preserve%20arrival%20order).%20The%20same%20hyperexponential%20service-time%20generator%20(90%25%20short%2C%2010%25%20long)%20is%20used%20in%20both%20runs.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(mo)%3A%0A%20%20%20%20sim_time_slider%20%3D%20mo.ui.slider(%0A%20%20%20%20%20%20%20%20start%3D0%2C%0A%20%20%20%20%20%20%20%20stop%3D100_000%2C%0A%20%20%20%20%20%20%20%20step%3D1_000%2C%0A%20%20%20%20%20%20%20%20value%3D20_000%2C%0A%20%20%20%20%20%20%20%20label%3D%22Simulation%20time%22%2C%0A%20%20%20%20)%0A%0A%20%20%20%20arrival_rate_slider%20%3D%20mo.ui.slider(%0A%20%20%20%20%20%20%20%20start%3D0.1%2C%0A%20%20%20%20%20%20%20%20stop%3D1.5%2C%0A%20%20%20%20%20%20%20%20step%3D0.05%2C%0A%20%20%20%20%20%20%20%20value%3D0.7%2C%0A%20%20%20%20%20%20%20%20label%3D%22Arrival%20rate%22%2C%0A%20%20%20%20)%0A%0A%20%20%20%20seed_input%20%3D%20mo.ui.number(%0A%20%20%20%20%20%20%20%20value%3D192%2C%0A%20%20%20%20%20%20%20%20step%3D1%2C%0A%20%20%20%20%20%20%20%20label%3D%22Random%20seed%22%2C%0A%20%20%20%20)%0A%0A%20%20%20%20run_button%20%3D%20mo.ui.button(label%3D%22Run%20simulation%22)%0A%0A%20%20%20%20mo.vstack(%5B%0A%20%20%20%20%20%20%20%20sim_time_slider%2C%0A%20%20%20%20%20%20%20%20arrival_rate_slider%2C%0A%20%20%20%20%20%20%20%20seed_input%2C%0A%20%20%20%20%20%20%20%20run_button%2C%0A%20%20%20%20%5D)%0A%20%20%20%20return%20arrival_rate_slider%2C%20seed_input%2C%20sim_time_slider%0A%0A%0A%40app.cell%0Adef%20_(arrival_rate_slider%2C%20seed_input%2C%20sim_time_slider)%3A%0A%20%20%20%20SIM_TIME%20%3D%20int(sim_time_slider.value)%0A%20%20%20%20ARRIVAL_RATE%20%3D%20float(arrival_rate_slider.value)%0A%20%20%20%20SEED%20%3D%20int(seed_input.value)%0A%20%20%20%20SHORT_RATE%20%3D%204.0%0A%20%20%20%20LONG_RATE%20%3D%200.2%0A%20%20%20%20LONG_PROB%20%3D%200.10%0A%20%20%20%20return%20ARRIVAL_RATE%2C%20LONG_PROB%2C%20LONG_RATE%2C%20SEED%2C%20SHORT_RATE%2C%20SIM_TIME%0A%0A%0A%40app.cell%0Adef%20_(LONG_PROB%2C%20LONG_RATE%2C%20SHORT_RATE%2C%20random)%3A%0A%20%20%20%20def%20service_time()%3A%0A%20%20%20%20%20%20%20%20if%20random.random()%20%3C%20LONG_PROB%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20random.expovariate(LONG_RATE)%0A%20%20%20%20%20%20%20%20return%20random.expovariate(SHORT_RATE)%0A%0A%20%20%20%20return%20(service_time%2C)%0A%0A%0A%40app.cell%0Adef%20_(ARRIVAL_RATE%2C%20Process%2C%20random%2C%20service_time)%3A%0A%20%20%20%20class%20JobSource(Process)%3A%0A%20%20%20%20%20%20%20%20def%20init(self%2C%20job_queue%2C%20arrivals%2C%20sjf)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.job_queue%20%3D%20job_queue%0A%20%20%20%20%20%20%20%20%20%20%20%20self.arrivals%20%3D%20arrivals%0A%20%20%20%20%20%20%20%20%20%20%20%20self.sjf%20%3D%20sjf%0A%20%20%20%20%20%20%20%20%20%20%20%20self._jid%20%3D%200%0A%0A%20%20%20%20%20%20%20%20async%20def%20run(self)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20while%20True%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20await%20self.timeout(random.expovariate(ARRIVAL_RATE))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20jid%20%3D%20self._jid%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self._jid%20%2B%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20svc%20%3D%20service_time()%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.arrivals%5Bjid%5D%20%3D%20(self.now%2C%20svc)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20self.sjf%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20await%20self.job_queue.put((svc%2C%20jid))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20await%20self.job_queue.put((jid%2C%20svc))%0A%0A%20%20%20%20return%20(JobSource%2C)%0A%0A%0A%40app.cell%0Adef%20_(Process)%3A%0A%20%20%20%20class%20Server(Process)%3A%0A%20%20%20%20%20%20%20%20def%20init(self%2C%20job_queue%2C%20arrivals%2C%20sojourn_times%2C%20sjf)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.job_queue%20%3D%20job_queue%0A%20%20%20%20%20%20%20%20%20%20%20%20self.arrivals%20%3D%20arrivals%0A%20%20%20%20%20%20%20%20%20%20%20%20self.sojourn_times%20%3D%20sojourn_times%0A%20%20%20%20%20%20%20%20%20%20%20%20self.sjf%20%3D%20sjf%0A%0A%20%20%20%20%20%20%20%20async%20def%20run(self)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20while%20True%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20item%20%3D%20await%20self.job_queue.get()%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20self.sjf%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20svc%2C%20jid%20%3D%20item%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20jid%2C%20svc%20%3D%20item%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20await%20self.timeout(svc)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20arrival_time%2C%20_%20%3D%20self.arrivals%5Bjid%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.sojourn_times.append(self.now%20-%20arrival_time)%0A%0A%20%20%20%20return%20(Server%2C)%0A%0A%0A%40app.cell%0Adef%20_(%0A%20%20%20%20Environment%2C%0A%20%20%20%20JobSource%2C%0A%20%20%20%20PriorityQueue%2C%0A%20%20%20%20Queue%2C%0A%20%20%20%20SIM_TIME%2C%0A%20%20%20%20Server%2C%0A%20%20%20%20statistics%2C%0A)%3A%0A%20%20%20%20def%20simulate(sjf)%3A%0A%20%20%20%20%20%20%20%20arrivals%20%3D%20%7B%7D%0A%20%20%20%20%20%20%20%20sojourn_times%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20env%20%3D%20Environment()%0A%20%20%20%20%20%20%20%20q%20%3D%20PriorityQueue(env)%20if%20sjf%20else%20Queue(env)%0A%20%20%20%20%20%20%20%20JobSource(env%2C%20q%2C%20arrivals%2C%20sjf)%0A%20%20%20%20%20%20%20%20Server(env%2C%20q%2C%20arrivals%2C%20sojourn_times%2C%20sjf)%0A%20%20%20%20%20%20%20%20env.run(until%3DSIM_TIME)%0A%20%20%20%20%20%20%20%20return%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%22mean%22%3A%20statistics.mean(sojourn_times)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22median%22%3A%20statistics.median(sojourn_times)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22p95%22%3A%20sorted(sojourn_times)%5Bint(0.95%20*%20len(sojourn_times))%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22p99%22%3A%20sorted(sojourn_times)%5Bint(0.99%20*%20len(sojourn_times))%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%22n%22%3A%20len(sojourn_times)%2C%0A%20%20%20%20%20%20%20%20%7D%0A%0A%20%20%20%20return%20(simulate%2C)%0A%0A%0A%40app.cell%0Adef%20_(LONG_PROB%2C%20LONG_RATE%2C%20SEED%2C%20SHORT_RATE%2C%20pl%2C%20random%2C%20simulate)%3A%0A%20%20%20%20def%20run_scenarios()%3A%0A%20%20%20%20%20%20%20%20fifo%20%3D%20simulate(sjf%3DFalse)%0A%20%20%20%20%20%20%20%20sjf_res%20%3D%20simulate(sjf%3DTrue)%0A%20%20%20%20%20%20%20%20rows%20%3D%20%5B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22metric%22%3A%20m%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22fifo%22%3A%20fifo%5Bm%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22sjf%22%3A%20sjf_res%5Bm%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22improvement%22%3A%20fifo%5Bm%5D%20%2F%20sjf_res%5Bm%5D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20m%20in%20(%22mean%22%2C%20%22median%22%2C%20%22p95%22%2C%20%22p99%22)%0A%20%20%20%20%20%20%20%20%5D%0A%20%20%20%20%20%20%20%20return%20pl.DataFrame(rows)%0A%0A%20%20%20%20random.seed(SEED)%0A%20%20%20%20df%20%3D%20run_scenarios()%0A%20%20%20%20mean_svc%20%3D%20(1%20-%20LONG_PROB)%20%2F%20SHORT_RATE%20%2B%20LONG_PROB%20%2F%20LONG_RATE%0A%20%20%20%20return%20df%2C%20mean_svc%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(ARRIVAL_RATE%2C%20LONG_PROB%2C%20LONG_RATE%2C%20SHORT_RATE%2C%20mean_svc%2C%20mo)%3A%0A%20%20%20%20mo.md(f%22%22%22%0A%20%20%20%20%23%23%20Summary%20Statistics%0A%0A%20%20%20%20Arrival%20rate%3A%20%7BARRIVAL_RATE%7D%2C%20estimated%20mean%20service%3A%20%7Bmean_svc%3A.3f%7D%0A%0A%20%20%20%20Short%20jobs%3A%20%7B100%20*%20(1%20-%20LONG_PROB)%3A.0f%7D%25%20(mean%20%7B1%20%2F%20SHORT_RATE%3A.2f%7D)%2C%0A%20%20%20%20Long%20jobs%3A%20%7B100%20*%20LONG_PROB%3A.0f%7D%25%20(mean%20%7B1%20%2F%20LONG_RATE%3A.1f%7D)%0A%0A%20%20%20%20%3E%20**Note%3A**%20SJF%20is%20optimal%20for%20mean%20sojourn%20time%20but%20requires%20knowing%20job%20sizes%20in%20advance.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(df)%3A%0A%20%20%20%20df%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(alt%2C%20df%2C%20pl)%3A%0A%20%20%20%20df_plot%20%3D%20df.filter(pl.col(%22metric%22)%20!%3D%20%22n%22).unpivot(%0A%20%20%20%20%20%20%20%20on%3D%5B%22fifo%22%2C%20%22sjf%22%5D%2C%0A%20%20%20%20%20%20%20%20index%3D%22metric%22%2C%0A%20%20%20%20%20%20%20%20variable_name%3D%22policy%22%2C%0A%20%20%20%20%20%20%20%20value_name%3D%22sojourn_time%22%2C%0A%20%20%20%20)%0A%20%20%20%20chart%20%3D%20(%0A%20%20%20%20%20%20%20%20alt.Chart(df_plot)%0A%20%20%20%20%20%20%20%20.mark_bar()%0A%20%20%20%20%20%20%20%20.encode(%0A%20%20%20%20%20%20%20%20%20%20%20%20x%3Dalt.X(%22metric%3AN%22%2C%20title%3D%22Metric%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20y%3Dalt.Y(%22sojourn_time%3AQ%22%2C%20title%3D%22Sojourn%20time%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20color%3Dalt.Color(%22policy%3AN%22%2C%20title%3D%22Policy%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20xOffset%3D%22policy%3AN%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20tooltip%3D%5B%22metric%3AN%22%2C%20%22policy%3AN%22%2C%20%22sojourn_time%3AQ%22%5D%2C%0A%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20.properties(title%3D%22Convoy%20Effect%3A%20FIFO%20vs.%20Shortest%20Job%20First%22)%0A%20%20%20%20)%0A%20%20%20%20chart%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(r%22%22%22%0A%20%20%20%20%23%23%20Understanding%20the%20Math%0A%0A%20%20%20%20%23%23%23%20The%20second%20moment%0A%0A%20%20%20%20For%20a%20random%20variable%20%24S%24%20representing%20service%20time%2C%20the%20second%20moment%20is%20%24E%5BS%5E2%5D%24.%20Recall%20from%20your%20statistics%20course%20that%20variance%20is%20%24%5Ctext%7BVar%7D(S)%20%3D%20E%5BS%5E2%5D%20-%20(E%5BS%5D)%5E2%24%2C%20which%20rearranges%20to%3A%0A%0A%20%20%20%20%24%24E%5BS%5E2%5D%20%3D%20%5Ctext%7BVar%7D(S)%20%2B%20(E%5BS%5D)%5E2%24%24%0A%0A%20%20%20%20This%20means%20high%20variance%20inflates%20%24E%5BS%5E2%5D%24%20even%20if%20the%20mean%20%24E%5BS%5D%24%20stays%20fixed.%20Doubling%20the%20spread%20of%20service%20times%20can%20quadruple%20%24E%5BS%5E2%5D%24%2C%20even%20with%20the%20same%20average%20service%20time.%0A%0A%20%20%20%20%23%23%23%20Why%20variance%20of%20service%20time%20hurts%0A%0A%20%20%20%20Imagine%20a%20FIFO%20server%20handling%20jobs%20that%20are%20either%200.1%20minutes%20or%2010%20minutes%20long%2C%20with%2090%25%20being%20short%20and%2010%25%20being%20long.%20The%20mean%20service%20time%20is%20%240.9%20%5Ctimes%200.1%20%2B%200.1%20%5Ctimes%2010%20%3D%201.09%24%20minutes%2C%20so%20utilization%20%24%5Crho%20%3D%20%5Clambda%20%2F%20%5Cmu%24%20might%20be%20modest.%20But%20when%20a%2010-minute%20job%20starts%2C%20every%20job%20arriving%20during%20those%2010%20minutes%20must%20join%20the%20queue%20and%20wait.%20The%20longer%20%24E%5BS%5E2%5D%24%2C%20the%20more%20average%20work%20sits%20ahead%20of%20each%20arriving%20job.%0A%0A%20%20%20%20%23%23%23%20The%20Pollaczek%E2%80%93Khinchine%20formula%0A%0A%20%20%20%20The%20mean%20time%20a%20job%20spends%20waiting%20(not%20counting%20its%20own%20service%20time)%20in%20a%20FIFO%20single-server%20queue%20is%3A%0A%0A%20%20%20%20%24%24W_q%20%3D%20%5Cfrac%7B%5Clambda%20%5Ccdot%20E%5BS%5E2%5D%7D%7B2(1%20-%20%5Crho)%7D%24%24%0A%0A%20%20%20%20Here%20%24%5Clambda%24%20is%20the%20arrival%20rate%2C%20%24E%5BS%5E2%5D%24%20is%20the%20second%20moment%20of%20service%20time%2C%20and%20%24%5Crho%20%3D%20%5Clambda%20%5Ccdot%20E%5BS%5D%24%20is%20the%20server%20utilization.%20Both%20%24%5Clambda%24%20and%20%24E%5BS%5E2%5D%24%20appear%20in%20the%20numerator%2C%20so%20more%20variance%20means%20more%20waiting%20even%20at%20the%20same%20%24%5Crho%24.%20The%20%24(1-%5Crho)%24%20denominator%20is%20the%20familiar%20blow-up%20term%20from%20M%2FM%2F1.%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20app.run()%0A