10 priority starvation

%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%0A%0A%20%20%20%20return%20Environment%2C%20Process%2C%20Queue%2C%20alt%2C%20mo%2C%20pl%2C%20random%2C%20statistics%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%20Priority%20Starvation%0A%0A%20%20%20%20%23%23%20*When%20High-Priority%20Traffic%20Crowds%20Out%20Low-Priority%20Jobs*%0A%0A%20%20%20%20A%20single%20server%20processes%20two%20job%20classes%3A%0A%0A%20%20%20%20-%20High-priority%20jobs%20(class%20H)%20arrive%20frequently%20and%20are%20served%20quickly.%0A%20%20%20%20-%20Low-priority%20jobs%20(class%20L)%20arrive%20rarely%20and%20take%20longer%20to%20serve.%0A%0A%20%20%20%20The%20server%20always%20picks%20the%20highest-priority%20job%20available.%20Total%20server%20utilization%20%24%5Crho%20%3D%20%5Crho_H%20%2B%20%5Crho_L%20%3C%201%24%2C%20so%20the%20server%20has%20spare%20capacity%20on%20average.%20Yet%20low-priority%20jobs%20can%20wait%20far%20longer%20than%20the%20utilization%20level%20suggests%20they%20should.%0A%0A%20%20%20%20%23%23%23%20Static%20Priority%3A%20Starvation%20at%20Moderate%20Load%0A%0A%20%20%20%20With%20a%20static%20priority%20queue%2C%20high-priority%20jobs%20*never*%20yield%20to%20low-priority%20ones.%20Even%20when%20%24%5Crho_H%20%3C%201%24%2C%20high-priority%20bursts%20can%20lock%20out%20low-priority%20jobs%20for%20extended%20periods.%20The%20mean%20wait%20for%20low-priority%20jobs%20under%20a%20static%20non-preemptive%20priority%20queue%20is%3A%0A%0A%20%20%20%20%24%24W_L%20%3D%20%5Cfrac%7B%5Coverline%7Bs%7D_L%7D%7B1-%5Crho_H%7D%20%5Ccdot%20%5Cfrac%7B1%7D%7B1-%5Crho_H-%5Crho_L%7D%24%24%0A%0A%20%20%20%20This%20diverges%20as%20%24%5Crho_H%20%5Cto%201%24%20independently%20of%20%24%5Crho_L%24.%20As%20%24%5Crho_H%24%20approaches%20100%25%2C%20low-priority%20jobs%20wait%20arbitrarily%20long%2C%20even%20if%20only%20a%20few%20low-priority%20jobs%20ever%20arrive.%0A%0A%20%20%20%20%23%23%23%20Aging%3A%20Solving%20Starvation%20Creates%20Oscillation%0A%0A%20%20%20%20The%20standard%20remedy%20for%20starvation%20is%20*priority%20aging*%3A%20a%20waiting%20job's%20priority%20improves%20over%20time%20until%20it%20eventually%20beats%20even%20high-priority%20arrivals.%20This%20guarantees%20finite%20wait%20for%20all%20jobs.%0A%0A%20%20%20%20However%2C%20aging%20introduces%20a%20new%20pathology.%20When%20aged%20low-priority%20jobs%20finally%20burst%20through%2C%20they%20occupy%20the%20server%20and%20leave%20a%20backlog%20of%20high-priority%20jobs%20waiting.%20The%20high-priority%20queue%20then%20drains%2C%20and%20the%20cycle%20repeats%20%E2%80%94%20producing%20oscillating%20bursts%20rather%20than%20smooth%2C%20uniform%20service.%0A%0A%20%20%20%20%23%23%23%20Intuition%0A%0A%20%20%20%20Suppose%20H%20jobs%20arrive%20in%20random%20bursts.%20During%20a%20burst%2C%20the%20server%20never%20pauses%20for%20L%20jobs.%20An%20L%20job%20unlucky%20enough%20to%20arrive%20at%20the%20start%20of%20a%20long%20burst%20must%20wait%20for%20every%20H%20job%20in%20that%20burst%20to%20be%20served%20before%20getting%20its%20turn.%20As%20bursts%20grow%20more%20frequent%20(larger%20%24%5Crho_H%24)%2C%20the%20expected%20burst%20length%20grows%2C%20and%20with%20it%20the%20expected%20wait%20for%20that%20unlucky%20L%20job.%20The%20math%20confirms%3A%20starvation%20is%20a%20real%20risk%20at%20moderate%20%24%5Crho_H%24%2C%20not%20just%20at%20extreme%20loads.%0A%0A%20%20%20%20%23%23%23%20What%20aging%20does%0A%0A%20%20%20%20Aging%20assigns%20each%20waiting%20L%20job%20a%20maximum%20patience%20time%20%24T_%7B%5Cmax%7D%24.%20After%20waiting%20%24T_%7B%5Cmax%7D%24%2C%20the%20job%20is%20promoted%20to%20high%20priority.%20This%20caps%20the%20worst-case%20wait%3A%20no%20L%20job%20can%20wait%20longer%20than%20%24T_%7B%5Cmax%7D%24%20plus%20one%20service%20time.%20Mathematically%2C%20the%20effective%20%24W_L%24%20is%20bounded%20by%20%24T_%7B%5Cmax%7D%20%2B%201%2F%5Cmu_L%24.%0A%0A%20%20%20%20%23%23%20Practical%20Implications%0A%0A%20%20%20%20Priority%20queues%20appear%20throughout%20computing%3A%0A%0A%20%20%20%20-%20OS%20scheduling%3A%20interactive%20processes%20(high%20priority)%20vs.%20batch%20jobs%20(low%20priority).%20Linux%20uses%20dynamic%20priority%20aging%20(nice%20values%20%2B%20sleep%20bonuses)%20to%20avoid%20starvation.%0A%20%20%20%20-%20Network%20QoS%3A%20real-time%20traffic%20(VoIP%2C%20video)%20vs.%20bulk%20data.%20Traffic%20shaping%20with%20Deficit%20Round%20Robin%20(DRR)%20or%20Weighted%20Fair%20Queuing%20(WFQ)%20guarantees%20bandwidth%20shares%20without%20starvation.%0A%20%20%20%20-%20Database%20query%20planning%3A%20short%20OLTP%20queries%20vs.%20long%20OLAP%20queries.%20Resource%20groups%20and%20query%20timeouts%20implement%20a%20form%20of%20aging.%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%20Two%20runs%20are%20compared%3A%0A%0A%20%20%20%201.%20Static%20priority%3A%20H%20jobs%20are%20inserted%20as%20%60(0%2C%20...)%60%20and%20L%20jobs%20as%20%60(1%2C%20...)%60%20into%20a%20%60Queue(priority%3DTrue)%60.%20The%20server%20always%20picks%20the%20smallest%20key%20first%2C%20so%20H%20jobs%20are%20always%20served%20before%20L%20jobs.%0A%20%20%20%202.%20Aging%3A%20an%20%60Ager%60%20process%20wakes%20up%20every%20%60AGING_INTERVAL%60%20time%20units%2C%20inspects%20waiting%20L%20jobs%2C%20and%20promotes%20sufficiently%20old%20ones%20by%20reducing%20their%20priority%20key%20until%20it%20falls%20below%20the%20H%20threshold%20and%20they%20move%20into%20the%20server's%20feed%20queue.%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%20aging_threshold_slider%20%3D%20mo.ui.slider(%0A%20%20%20%20%20%20%20%20start%3D1.0%2C%0A%20%20%20%20%20%20%20%20stop%3D60.0%2C%0A%20%20%20%20%20%20%20%20step%3D1.0%2C%0A%20%20%20%20%20%20%20%20value%3D15.0%2C%0A%20%20%20%20%20%20%20%20label%3D%22Aging%20threshold%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%20aging_threshold_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%20aging_threshold_slider%2C%20seed_input%2C%20sim_time_slider%0A%0A%0A%40app.cell%0Adef%20_(aging_threshold_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%20AGING_THRESHOLD%20%3D%20float(aging_threshold_slider.value)%0A%20%20%20%20SEED%20%3D%20int(seed_input.value)%0A%20%20%20%20SERVICE_RATE_HI%20%3D%202.0%0A%20%20%20%20SERVICE_RATE_LO%20%3D%201.0%0A%20%20%20%20ARRIVAL_RATE_LO%20%3D%200.2%0A%20%20%20%20return%20(%0A%20%20%20%20%20%20%20%20AGING_THRESHOLD%2C%0A%20%20%20%20%20%20%20%20ARRIVAL_RATE_LO%2C%0A%20%20%20%20%20%20%20%20SEED%2C%0A%20%20%20%20%20%20%20%20SERVICE_RATE_HI%2C%0A%20%20%20%20%20%20%20%20SERVICE_RATE_LO%2C%0A%20%20%20%20%20%20%20%20SIM_TIME%2C%0A%20%20%20%20)%0A%0A%0A%40app.cell%0Adef%20_(Process)%3A%0A%20%20%20%20class%20StaticPriorityServer(Process)%3A%0A%20%20%20%20%20%20%20%20def%20init(self%2C%20hi_q%2C%20lo_q%2C%20sojourn_hi%2C%20sojourn_lo)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.hi_q%20%3D%20hi_q%0A%20%20%20%20%20%20%20%20%20%20%20%20self.lo_q%20%3D%20lo_q%0A%20%20%20%20%20%20%20%20%20%20%20%20self.sojourn_hi%20%3D%20sojourn_hi%0A%20%20%20%20%20%20%20%20%20%20%20%20self.sojourn_lo%20%3D%20sojourn_lo%0A%0A%20%20%20%20%20%20%20%20async%20def%20_serve(self%2C%20arrival%2C%20svc%2C%20record)%3A%0A%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%20record.append(self.now%20-%20arrival)%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%20if%20not%20self.hi_q.is_empty()%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20arrival%2C%20svc%20%3D%20await%20self.hi_q.get()%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20await%20self._serve(arrival%2C%20svc%2C%20self.sojourn_hi)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20elif%20not%20self.lo_q.is_empty()%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20arrival%2C%20svc%20%3D%20await%20self.lo_q.get()%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20await%20self._serve(arrival%2C%20svc%2C%20self.sojourn_lo)%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.timeout(0.01)%0A%0A%20%20%20%20return%20(StaticPriorityServer%2C)%0A%0A%0A%40app.cell%0Adef%20_(AGING_THRESHOLD%2C%20Process)%3A%0A%20%20%20%20class%20AgingServer(Process)%3A%0A%20%20%20%20%20%20%20%20def%20init(self%2C%20hi_q%2C%20lo_q%2C%20sojourn_hi%2C%20sojourn_lo)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.hi_q%20%3D%20hi_q%0A%20%20%20%20%20%20%20%20%20%20%20%20self.lo_q%20%3D%20lo_q%0A%20%20%20%20%20%20%20%20%20%20%20%20self.sojourn_hi%20%3D%20sojourn_hi%0A%20%20%20%20%20%20%20%20%20%20%20%20self.sojourn_lo%20%3D%20sojourn_lo%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%20lo_aged%20%3D%20(%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20not%20self.lo_q.is_empty()%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20and%20self.now%20-%20self.lo_q._items%5B0%5D%5B0%5D%20%3E%3D%20AGING_THRESHOLD%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20lo_aged%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20arrival%2C%20svc%20%3D%20await%20self.lo_q.get()%0A%20%20%20%20%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%20%20%20%20%20self.sojourn_lo.append(self.now%20-%20arrival)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20elif%20not%20self.hi_q.is_empty()%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20arrival%2C%20svc%20%3D%20await%20self.hi_q.get()%0A%20%20%20%20%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%20%20%20%20%20self.sojourn_hi.append(self.now%20-%20arrival)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20elif%20not%20self.lo_q.is_empty()%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20arrival%2C%20svc%20%3D%20await%20self.lo_q.get()%0A%20%20%20%20%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%20%20%20%20%20self.sojourn_lo.append(self.now%20-%20arrival)%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.timeout(0.01)%0A%0A%20%20%20%20return%20(AgingServer%2C)%0A%0A%0A%40app.cell%0Adef%20_(Process%2C%20SERVICE_RATE_HI%2C%20random)%3A%0A%20%20%20%20class%20HiSource(Process)%3A%0A%20%20%20%20%20%20%20%20def%20init(self%2C%20rate%2C%20q)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.rate%20%3D%20rate%0A%20%20%20%20%20%20%20%20%20%20%20%20self.q%20%3D%20q%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(self.rate))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20svc%20%3D%20random.expovariate(SERVICE_RATE_HI)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20await%20self.q.put((self.now%2C%20svc))%0A%0A%20%20%20%20return%20(HiSource%2C)%0A%0A%0A%40app.cell%0Adef%20_(ARRIVAL_RATE_LO%2C%20Process%2C%20SERVICE_RATE_LO%2C%20random)%3A%0A%20%20%20%20class%20LoSource(Process)%3A%0A%20%20%20%20%20%20%20%20def%20init(self%2C%20q)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.q%20%3D%20q%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_LO))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20svc%20%3D%20random.expovariate(SERVICE_RATE_LO)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20await%20self.q.put((self.now%2C%20svc))%0A%0A%20%20%20%20return%20(LoSource%2C)%0A%0A%0A%40app.cell%0Adef%20_(%0A%20%20%20%20AgingServer%2C%0A%20%20%20%20Environment%2C%0A%20%20%20%20HiSource%2C%0A%20%20%20%20LoSource%2C%0A%20%20%20%20Queue%2C%0A%20%20%20%20SIM_TIME%2C%0A%20%20%20%20StaticPriorityServer%2C%0A%20%20%20%20statistics%2C%0A)%3A%0A%20%20%20%20def%20simulate(arrival_rate_hi%2C%20use_aging)%3A%0A%20%20%20%20%20%20%20%20env%20%3D%20Environment()%0A%20%20%20%20%20%20%20%20hi_q%20%3D%20Queue(env)%0A%20%20%20%20%20%20%20%20lo_q%20%3D%20Queue(env)%0A%20%20%20%20%20%20%20%20sojourn_hi%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20sojourn_lo%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20HiSource(env%2C%20arrival_rate_hi%2C%20hi_q)%0A%20%20%20%20%20%20%20%20LoSource(env%2C%20lo_q)%0A%20%20%20%20%20%20%20%20if%20use_aging%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20AgingServer(env%2C%20hi_q%2C%20lo_q%2C%20sojourn_hi%2C%20sojourn_lo)%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20StaticPriorityServer(env%2C%20hi_q%2C%20lo_q%2C%20sojourn_hi%2C%20sojourn_lo)%0A%20%20%20%20%20%20%20%20env.run(until%3DSIM_TIME)%0A%20%20%20%20%20%20%20%20return%20sojourn_hi%2C%20sojourn_lo%0A%0A%20%20%20%20def%20mean_or_none(lst)%3A%0A%20%20%20%20%20%20%20%20return%20statistics.mean(lst)%20if%20lst%20else%20None%0A%0A%20%20%20%20def%20pct_or_none(lst%2C%20p)%3A%0A%20%20%20%20%20%20%20%20if%20not%20lst%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20None%0A%20%20%20%20%20%20%20%20return%20sorted(lst)%5Bint(p%20*%20len(lst))%5D%0A%0A%20%20%20%20return%20mean_or_none%2C%20pct_or_none%2C%20simulate%0A%0A%0A%40app.cell%0Adef%20_(%0A%20%20%20%20ARRIVAL_RATE_LO%2C%0A%20%20%20%20SEED%2C%0A%20%20%20%20SERVICE_RATE_HI%2C%0A%20%20%20%20SERVICE_RATE_LO%2C%0A%20%20%20%20mean_or_none%2C%0A%20%20%20%20pl%2C%0A%20%20%20%20random%2C%0A%20%20%20%20simulate%2C%0A)%3A%0A%20%20%20%20def%20sweep()%3A%0A%20%20%20%20%20%20%20%20sweep_rows%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20for%20rho_hi%20in%20%5B0.10%2C%200.20%2C%200.40%2C%200.60%2C%200.70%2C%200.80%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20rate_hi%20%3D%20rho_hi%20*%20SERVICE_RATE_HI%0A%20%20%20%20%20%20%20%20%20%20%20%20hi%2C%20lo%20%3D%20simulate(rate_hi%2C%20use_aging%3DFalse)%0A%20%20%20%20%20%20%20%20%20%20%20%20rho_total%20%3D%20rho_hi%20%2B%20ARRIVAL_RATE_LO%20%2F%20SERVICE_RATE_LO%0A%20%20%20%20%20%20%20%20%20%20%20%20sweep_rows.append(%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22rho_hi%22%3A%20rho_hi%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22rho_total%22%3A%20rho_total%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22mean_W_hi%22%3A%20mean_or_none(hi)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22mean_W_lo%22%3A%20mean_or_none(lo)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D)%0A%20%20%20%20%20%20%20%20return%20pl.DataFrame(sweep_rows)%0A%0A%20%20%20%20random.seed(SEED)%0A%20%20%20%20df_sweep%20%3D%20sweep()%0A%20%20%20%20return%20(df_sweep%2C)%0A%0A%0A%40app.cell%0Adef%20_(%0A%20%20%20%20ARRIVAL_RATE_LO%2C%0A%20%20%20%20SERVICE_RATE_HI%2C%0A%20%20%20%20SERVICE_RATE_LO%2C%0A%20%20%20%20mean_or_none%2C%0A%20%20%20%20pct_or_none%2C%0A%20%20%20%20pl%2C%0A%20%20%20%20simulate%2C%0A)%3A%0A%20%20%20%20FIXED_RHO_HI%20%3D%200.70%0A%20%20%20%20rho_total%20%3D%20FIXED_RHO_HI%20%2B%20ARRIVAL_RATE_LO%20%2F%20SERVICE_RATE_LO%0A%20%20%20%20def%20compare()%3A%0A%20%20%20%20%20%20%20%20rate_hi%20%3D%20FIXED_RHO_HI%20*%20SERVICE_RATE_HI%0A%20%20%20%20%20%20%20%20hi_static%2C%20lo_static%20%3D%20simulate(rate_hi%2C%20use_aging%3DFalse)%0A%20%20%20%20%20%20%20%20hi_aging%2C%20lo_aging%20%3D%20simulate(rate_hi%2C%20use_aging%3DTrue)%0A%0A%20%20%20%20%20%20%20%20compare_rows%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%22policy%22%3A%20%22static%22%2C%20%22class%22%3A%20%22hi%22%2C%20%22n%22%3A%20len(hi_static)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22mean_W%22%3A%20mean_or_none(hi_static)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22p95%22%3A%20pct_or_none(hi_static%2C%200.95)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22p99%22%3A%20pct_or_none(hi_static%2C%200.99)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%2C%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%22policy%22%3A%20%22static%22%2C%20%22class%22%3A%20%22lo%22%2C%20%22n%22%3A%20len(lo_static)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22mean_W%22%3A%20mean_or_none(lo_static)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22p95%22%3A%20pct_or_none(lo_static%2C%200.95)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22p99%22%3A%20pct_or_none(lo_static%2C%200.99)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%2C%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%22policy%22%3A%20%22aging%22%2C%20%22class%22%3A%20%22hi%22%2C%20%22n%22%3A%20len(hi_aging)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22mean_W%22%3A%20mean_or_none(hi_aging)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22p95%22%3A%20pct_or_none(hi_aging%2C%200.95)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22p99%22%3A%20pct_or_none(hi_aging%2C%200.99)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%2C%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%22policy%22%3A%20%22aging%22%2C%20%22class%22%3A%20%22lo%22%2C%20%22n%22%3A%20len(lo_aging)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22mean_W%22%3A%20mean_or_none(lo_aging)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22p95%22%3A%20pct_or_none(lo_aging%2C%200.95)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22p99%22%3A%20pct_or_none(lo_aging%2C%200.99)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%2C%0A%20%20%20%20%20%20%20%20%5D%0A%20%20%20%20%20%20%20%20return%20pl.DataFrame(compare_rows)%0A%0A%20%20%20%20df_compare%20%3D%20compare()%0A%20%20%20%20return%20FIXED_RHO_HI%2C%20df_compare%2C%20rho_total%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(AGING_THRESHOLD%2C%20ARRIVAL_RATE_LO%2C%20SERVICE_RATE_LO%2C%20mo)%3A%0A%20%20%20%20mo.md(f%22%22%22%0A%20%20%20%20%23%23%20Part%201%20%E2%80%94%20Static%20Priority%3A%20Effect%20of%20Hi-Priority%20Load%20on%20Lo-Priority%20Wait%0A%0A%20%20%20%20Lo-priority%3A%20arrival%20rate%20%7BARRIVAL_RATE_LO%7D%2C%20mean%20service%20%7B1%20%2F%20SERVICE_RATE_LO%3A.1f%7D%2C%0A%20%20%20%20%CF%81_lo%20%3D%20%7BARRIVAL_RATE_LO%20%2F%20SERVICE_RATE_LO%3A.2f%7D%0A%0A%20%20%20%20Aging%20threshold%3A%20%7BAGING_THRESHOLD%7D%20time%20units%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(df_sweep)%3A%0A%20%20%20%20df_sweep%0A%20%20%20%20return%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(FIXED_RHO_HI%2C%20mo%2C%20rho_total)%3A%0A%20%20%20%20mo.md(f%22%22%22%0A%20%20%20%20%23%23%20Part%202%20%E2%80%94%20Static%20vs.%20Aging%20at%20%CF%81_hi%20%3D%20%7BFIXED_RHO_HI%3A.2f%7D%2C%20%CF%81_total%20%3D%20%7Brho_total%3A.2f%7D%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(df_compare)%3A%0A%20%20%20%20df_compare%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(alt%2C%20df_compare%2C%20df_sweep)%3A%0A%20%20%20%20df_plot%20%3D%20df_sweep.unpivot(%0A%20%20%20%20%20%20%20%20on%3D%5B%22mean_W_hi%22%2C%20%22mean_W_lo%22%5D%2C%0A%20%20%20%20%20%20%20%20index%3D%5B%22rho_hi%22%2C%20%22rho_total%22%5D%2C%0A%20%20%20%20%20%20%20%20variable_name%3D%22job_class%22%2C%0A%20%20%20%20%20%20%20%20value_name%3D%22mean_W%22%2C%0A%20%20%20%20)%0A%20%20%20%20sweep_chart%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_line(point%3DTrue)%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(%22rho_hi%3AQ%22%2C%20title%3D%22Hi-priority%20utilization%20(%CF%81_hi)%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20y%3Dalt.Y(%22mean_W%3AQ%22%2C%20title%3D%22Mean%20sojourn%20time%20(W)%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20color%3Dalt.Color(%22job_class%3AN%22%2C%20title%3D%22Job%20class%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20tooltip%3D%5B%22rho_hi%3AQ%22%2C%20%22job_class%3AN%22%2C%20%22mean_W%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%22Priority%20Starvation%3A%20Effect%20of%20Hi-Priority%20Load%22)%0A%20%20%20%20)%0A%20%20%20%20compare_chart%20%3D%20(%0A%20%20%20%20%20%20%20%20alt.Chart(df_compare)%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(%22class%3AN%22%2C%20title%3D%22Job%20class%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20y%3Dalt.Y(%22mean_W%3AQ%22%2C%20title%3D%22Mean%20sojourn%20time%20(W)%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%22policy%3AN%22%2C%20%22class%3AN%22%2C%20%22mean_W%3AQ%22%2C%20%22p99%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%22Static%20Priority%20vs.%20Aging%22)%0A%20%20%20%20)%0A%20%20%20%20(sweep_chart%20%7C%20compare_chart)%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%20Mean%20wait%20for%20two-priority%20queues%0A%0A%20%20%20%20Let%20%24%5Clambda_i%24%2C%20%24%5Cmu_i%24%2C%20and%20%24%5Crho_i%20%3D%20%5Clambda_i%20%2F%20%5Cmu_i%24%20be%20the%20arrival%20rate%2C%20service%20rate%2C%20and%20utilization%20of%20class%20%24i%20%5Cin%20%5C%7BH%2C%20L%5C%7D%24.%20For%20a%20non-preemptive%20priority%20queue%3A%0A%0A%20%20%20%20%24%24W_H%20%3D%20%5Cfrac%7BR_0%7D%7B1%20-%20%5Crho_H%7D%24%24%0A%0A%20%20%20%20%24%24W_L%20%3D%20%5Cfrac%7BR_0%7D%7B(1%20-%20%5Crho_H)(1%20-%20%5Crho_H%20-%20%5Crho_L)%7D%24%24%0A%0A%20%20%20%20where%20%24R_0%20%3D%20%5Ctfrac%7B1%7D%7B2%7D(%5Clambda_H%20%5Coverline%7Bs_H%5E2%7D%20%2B%20%5Clambda_L%20%5Coverline%7Bs_L%5E2%7D)%24%20is%20the%20mean%20residual%20work%20seen%20by%20an%20arriving%20customer.%20The%20ratio%20%24W_L%20%2F%20W_H%20%3D%201%2F(1%20-%20%5Crho_H)%24%20grows%20without%20bound%20as%20%24%5Crho_H%20%5Cto%201%24.%0A%0A%20%20%20%20%23%23%23%20Utilization%20of%20each%20class%0A%0A%20%20%20%20Let%20%24%5Clambda_H%24%20be%20the%20arrival%20rate%20of%20high-priority%20jobs%20(H)%20and%20%24%5Cmu_H%24%20be%20their%20service%20rate.%20The%20utilization%20contributed%20by%20H%20jobs%20alone%20is%20%24%5Crho_H%20%3D%20%5Clambda_H%20%2F%20%5Cmu_H%24%20%E2%80%94%20the%20fraction%20of%20server%20time%20that%20H%20jobs%20would%20consume%20if%20they%20were%20the%20only%20class.%20Similarly%2C%20%24%5Crho_L%20%3D%20%5Clambda_L%20%2F%20%5Cmu_L%24%20for%20low-priority%20jobs.%20The%20total%20utilization%20is%20%24%5Crho%20%3D%20%5Crho_H%20%2B%20%5Crho_L%24.%20Requiring%20%24%5Crho%20%3C%201%24%20means%20the%20server%20has%20enough%20capacity%20for%20both%20classes%20on%20average.%0A%0A%20%20%20%20%23%23%23%20Why%20%22on%20average%22%20is%20not%20enough%0A%0A%20%20%20%20Even%20when%20%24%5Crho%20%3C%201%24%2C%20randomness%20creates%20bursts%20of%20H%20arrivals.%20During%20a%20burst%2C%20the%20server%20is%20continuously%20occupied%20by%20H%20jobs%2C%20and%20L%20jobs%20must%20wait%20in%20the%20background.%20The%20mean%20wait%20for%20low-priority%20jobs%20in%20a%20non-preemptive%20priority%20queue%20is%3A%0A%0A%20%20%20%20%24%24W_L%20%3D%20%5Cfrac%7BR_0%7D%7B(1%20-%20%5Crho_H)(1%20-%20%5Crho_H%20-%20%5Crho_L)%7D%24%24%0A%0A%20%20%20%20where%20%24R_0%24%20is%20the%20mean%20residual%20work%20in%20the%20system%20when%20a%20job%20arrives.%20The%20critical%20observation%20is%20the%20factor%20%24(1%20-%20%5Crho_H)%24%20in%20the%20denominator.%20As%20%24%5Crho_H%20%5Cto%201%24%2C%20this%20factor%20approaches%20zero%20and%20%24W_L%20%5Cto%20%5Cinfty%24%20%E2%80%94%20even%20if%20%24%5Crho_L%24%20stays%20small%20and%20the%20total%20load%20%24%5Crho%24%20is%20comfortably%20below%201.%0A%0A%20%20%20%20%23%23%23%20The%20trade-off%0A%0A%20%20%20%20Without%20aging%2C%20%24W_L%24%20can%20be%20infinite%20when%20%24%5Crho_H%24%20is%20large.%20With%20aging%2C%20%24W_L%20%5Cleq%20T_%7B%5Cmax%7D%20%2B%201%2F%5Cmu_L%24%2C%20but%20during%20promotion%20events%20the%20effective%20%24%5Crho_H%24%20spikes%20temporarily%2C%20increasing%20%24W_H%24.%20Choosing%20%24T_%7B%5Cmax%7D%24%20is%20a%20design%20decision%3A%20a%20small%20%24T_%7B%5Cmax%7D%24%20protects%20L%20jobs%20but%20forces%20more%20promotions%20and%20penalizes%20H%20jobs%20more%20often%3B%20a%20large%20%24T_%7B%5Cmax%7D%24%20is%20kinder%20to%20H%20jobs%20but%20allows%20L%20jobs%20to%20wait%20longer.%20There%20is%20no%20setting%20that%20simultaneously%20minimizes%20both%20%E2%80%94%20the%20trade-off%20is%20fundamental.%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