05 mm1 nonlinearity

%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%20Resource%0A%0A%20%20%20%20return%20Environment%2C%20Process%2C%20Resource%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%20M%2FM%2F1%20Queue%20Nonlinearity%0A%0A%20%20%20%20%23%23%20*The%2090%25%20Utilization%20Trap*%0A%0A%20%20%20%20A%20single%20server%20handles%20jobs%20that%20arrive%20randomly%20and%20take%20a%20random%20amount%20of%20time%20to%20process.%20If%20both%20inter-arrival%20times%20and%20service%20times%20follow%20exponential%20distributions%2C%20this%20is%20called%20an%20*M%2FM%2F1%20queue*%2C%20and%20is%20the%20simplest%20model%20in%20queueing%20theory.%0A%0A%20%20%20%20Managers%20often%20treat%20utilization%20linearly%3A%20%2290%25%20busy%20is%20only%20a%20little%20worse%20than%2080%25%20busy.%22%20The%20M%2FM%2F1%20formula%20shows%20this%20intuition%20is%20badly%20wrong.%20The%20mean%20number%20of%20jobs%20in%20the%20system%20(waiting%20and%20being%20served)%20is%3A%0A%0A%20%20%20%20%24%24L%20%3D%20%5Cfrac%7B%5Crho%7D%7B1%20-%20%5Crho%7D%24%24%0A%0A%20%20%20%20where%20%24%5Crho%20%3D%20%5Clambda%20%2F%20%5Cmu%24%20is%20the%20utilization%20ratio%20(arrival%20rate%20divided%20by%20service%20rate).%20The%20mean%20time%20a%20job%20spends%20in%20the%20system%20follows%20from%20Little's%20Law%20%24L%20%3D%20%5Clambda%20W%24%3A%0A%0A%20%20%20%20%24%24W%20%3D%20%5Cfrac%7B1%7D%7B%5Cmu%20-%20%5Clambda%7D%20%3D%20%5Cfrac%7B1%7D%7B%5Cmu(1%20-%20%5Crho)%7D%24%24%0A%0A%20%20%20%20The%20denominator%20%24(1%20-%20%5Crho)%24%20causes%20both%20%24L%24%20and%20%24W%24%20to%20blow%20up%20as%20%24%5Crho%20%5Cto%201%24.%0A%0A%20%20%20%20%7C%20%24%5Crho%24%20%7C%20%24L%20%3D%20%5Crho%2F(1-%5Crho)%24%20%7C%20Marginal%20%24%5CDelta%20L%24%20per%200.1%20step%20%7C%0A%20%20%20%20%7C-------%3A%7C--------------------%3A%7C--------------------------------%3A%7C%0A%20%20%20%20%7C%20%200.50%20%20%7C%20%20%20%20%20%20%20%20%20%20%20%20%20%20%201.00%20%20%7C%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%E2%80%94%20%20%20%20%7C%0A%20%20%20%20%7C%20%200.60%20%20%7C%20%20%20%20%20%20%20%20%20%20%20%20%20%20%201.50%20%20%7C%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2B0.50%20%20%7C%0A%20%20%20%20%7C%20%200.70%20%20%7C%20%20%20%20%20%20%20%20%20%20%20%20%20%20%202.33%20%20%7C%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2B0.83%20%20%7C%0A%20%20%20%20%7C%20%200.80%20%20%7C%20%20%20%20%20%20%20%20%20%20%20%20%20%20%204.00%20%20%7C%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2B1.67%20%20%7C%0A%20%20%20%20%7C%20%200.90%20%20%7C%20%20%20%20%20%20%20%20%20%20%20%20%20%20%209.00%20%20%7C%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2B5.00%20%20%7C%0A%0A%20%20%20%20Each%20equal%20step%20in%20%24%5Crho%24%20produces%20a%20larger%20jump%20in%20queue%20length%20than%20the%20previous%20step.%20Going%20from%2080%25%20to%2090%25%20utilization%20adds%20more%20queue%20length%20than%20going%20from%200%25%20to%2080%25%20combined.%20This%20happens%20because%20the%20queue%20is%20stabilized%20by%20the%20gaps%20in%20service%20capacity.%20When%20%24%5Crho%20%3D%200.9%24%2C%20only%2010%25%20of%20capacity%20is%20slack.%20Any%20random%20burst%20of%20arrivals%20takes%20far%20longer%20to%20drain%20than%20when%20%24%5Crho%20%3D%200.5%24%20and%2050%25%20of%20capacity%20is%20slack.%20The%20system%20spends%20most%20of%20its%20time%20recovering%20from%20bursts%20rather%20than%20idling.%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%20The%20simulation%20uses%20a%20single%20%60Resource(capacity%3D1)%60%20as%20the%20server.%20A%20generator%20process%20creates%20customers%20with%20inter-arrival%20gaps%20drawn%20from%20%24%5Ctext%7BExp%7D(%5Clambda)%24.%20Each%20customer%20records%20its%20arrival%20time%2C%20waits%20to%20acquire%20the%20server%2C%20receives%20%24%5Ctext%7BExp%7D(%5Cmu)%24%20service%2C%20and%20logs%20its%20total%20sojourn%20time.%20The%20mean%20queue%20length%20%24L%24%20is%20computed%20via%20Little's%20Law%20from%20the%20observed%20mean%20sojourn%20time.%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%20service_rate_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%3D5.0%2C%0A%20%20%20%20%20%20%20%20step%3D0.01%2C%0A%20%20%20%20%20%20%20%20value%3D1.0%2C%0A%20%20%20%20%20%20%20%20label%3D%22Service%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%20service_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%20seed_input%2C%20service_rate_slider%2C%20sim_time_slider%0A%0A%0A%40app.cell%0Adef%20_(seed_input%2C%20service_rate_slider%2C%20sim_time_slider)%3A%0A%20%20%20%20SIM_TIME%20%3D%20int(sim_time_slider.value)%0A%20%20%20%20SERVICE_RATE%20%3D%20float(service_rate_slider.value)%0A%20%20%20%20SEED%20%3D%20int(seed_input.value)%0A%20%20%20%20return%20SEED%2C%20SERVICE_RATE%2C%20SIM_TIME%0A%0A%0A%40app.cell%0Adef%20_(Process%2C%20random)%3A%0A%20%20%20%20class%20Customer(Process)%3A%0A%20%20%20%20%20%20%20%20def%20init(self%2C%20server%2C%20service_rate%2C%20sojourn_times)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.server%20%3D%20server%0A%20%20%20%20%20%20%20%20%20%20%20%20self.service_rate%20%3D%20service_rate%0A%20%20%20%20%20%20%20%20%20%20%20%20self.sojourn_times%20%3D%20sojourn_times%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%20arrival%20%3D%20self.now%0A%20%20%20%20%20%20%20%20%20%20%20%20async%20with%20self.server%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20await%20self.timeout(random.expovariate(self.service_rate))%0A%20%20%20%20%20%20%20%20%20%20%20%20self.sojourn_times.append(self.now%20-%20arrival)%0A%0A%20%20%20%20return%20(Customer%2C)%0A%0A%0A%40app.cell%0Adef%20_(Customer%2C%20Process%2C%20random)%3A%0A%20%20%20%20class%20ArrivalStream(Process)%3A%0A%20%20%20%20%20%20%20%20def%20init(self%2C%20arrival_rate%2C%20service_rate%2C%20server%2C%20sojourn_times)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20self.arrival_rate%20%3D%20arrival_rate%0A%20%20%20%20%20%20%20%20%20%20%20%20self.service_rate%20%3D%20service_rate%0A%20%20%20%20%20%20%20%20%20%20%20%20self.server%20%3D%20server%0A%20%20%20%20%20%20%20%20%20%20%20%20self.sojourn_times%20%3D%20sojourn_times%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.arrival_rate))%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20Customer(self._env%2C%20self.server%2C%20self.service_rate%2C%20self.sojourn_times)%0A%0A%20%20%20%20return%20(ArrivalStream%2C)%0A%0A%0A%40app.cell%0Adef%20_(%0A%20%20%20%20ArrivalStream%2C%0A%20%20%20%20Environment%2C%0A%20%20%20%20Resource%2C%0A%20%20%20%20SERVICE_RATE%2C%0A%20%20%20%20SIM_TIME%2C%0A%20%20%20%20statistics%2C%0A)%3A%0A%20%20%20%20def%20simulate(rho)%3A%0A%20%20%20%20%20%20%20%20arrival_rate%20%3D%20rho%20*%20SERVICE_RATE%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%20server%20%3D%20Resource(env%2C%20capacity%3D1)%0A%20%20%20%20%20%20%20%20ArrivalStream(env%2C%20arrival_rate%2C%20SERVICE_RATE%2C%20server%2C%20sojourn_times)%0A%20%20%20%20%20%20%20%20env.run(until%3DSIM_TIME)%0A%20%20%20%20%20%20%20%20mean_W%20%3D%20statistics.mean(sojourn_times)%20if%20sojourn_times%20else%200.0%0A%20%20%20%20%20%20%20%20sim_L%20%3D%20arrival_rate%20*%20mean_W%0A%20%20%20%20%20%20%20%20theory_L%20%3D%20rho%20%2F%20(1.0%20-%20rho)%0A%20%20%20%20%20%20%20%20return%20sim_L%2C%20theory_L%0A%0A%20%20%20%20return%20(simulate%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%22%22%22%0A%20%20%20%20%23%23%20Simulated%20vs.%20Theoretical%20Queue%20Length%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(SEED%2C%20pl%2C%20random%2C%20simulate)%3A%0A%20%20%20%20def%20sweep()%3A%0A%20%20%20%20%20%20%20%20random.seed(SEED)%0A%20%20%20%20%20%20%20%20rhos%20%3D%20%5B0.1%2C%200.2%2C%200.3%2C%200.5%2C%200.7%2C%200.8%2C%200.9%2C%200.95%5D%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%20in%20rhos%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20sim_L%2C%20theory_L%20%3D%20simulate(rho)%0A%20%20%20%20%20%20%20%20%20%20%20%20pct%20%3D%20100.0%20*%20(sim_L%20-%20theory_L)%20%2F%20theory_L%0A%20%20%20%20%20%20%20%20%20%20%20%20sweep_rows.append(%7B%22rho%22%3A%20rho%2C%20%22theory_L%22%3A%20theory_L%2C%20%22sim_L%22%3A%20sim_L%2C%20%22pct_error%22%3A%20pct%7D)%0A%20%20%20%20%20%20%20%20return%20pl.DataFrame(sweep_rows)%0A%0A%20%20%20%20df_sweep%20%3D%20sweep()%0A%20%20%20%20df_sweep%0A%20%20%20%20return%20(df_sweep%2C)%0A%0A%0A%40app.cell(hide_code%3DTrue)%0Adef%20_(mo)%3A%0A%20%20%20%20mo.md(%22%22%22%0A%20%20%20%20%23%23%20Marginal%20Increase%20in%20L%20per%200.1%20Step%20in%20%CF%81%20(Theory)%0A%20%20%20%20%22%22%22)%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(pl)%3A%0A%20%20%20%20def%20marginal()%3A%0A%20%20%20%20%20%20%20%20marginal_rows%20%3D%20%5B%5D%0A%20%20%20%20%20%20%20%20prev_L%2C%20prev_rho%20%3D%20None%2C%20None%0A%20%20%20%20%20%20%20%20for%20rho%20in%20%5B0.5%2C%200.6%2C%200.7%2C%200.8%2C%200.9%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20theory_L%20%3D%20rho%20%2F%20(1.0%20-%20rho)%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20prev_L%20is%20not%20None%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20marginal_rows.append(%7B%22rho_from%22%3A%20prev_rho%2C%20%22rho_to%22%3A%20rho%2C%20%22delta_L%22%3A%20round(theory_L%20-%20prev_L%2C%204)%7D)%0A%20%20%20%20%20%20%20%20%20%20%20%20prev_L%2C%20prev_rho%20%3D%20theory_L%2C%20rho%0A%20%20%20%20%20%20%20%20return%20pl.DataFrame(marginal_rows)%0A%0A%20%20%20%20df_marginal%20%3D%20marginal()%0A%20%20%20%20df_marginal%0A%20%20%20%20return%0A%0A%0A%40app.cell%0Adef%20_(alt%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%22theory_L%22%2C%20%22sim_L%22%5D%2C%20index%3D%22rho%22%2C%20variable_name%3D%22source%22%2C%20value_name%3D%22L%22%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_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%3AQ%22%2C%20title%3D%22Utilization%20(%CF%81)%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20y%3Dalt.Y(%22L%3AQ%22%2C%20title%3D%22Mean%20queue%20length%20(L)%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20color%3Dalt.Color(%22source%3AN%22%2C%20title%3D%22Source%22)%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20tooltip%3D%5B%22rho%3AQ%22%2C%20%22source%3AN%22%2C%20%22L%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%22M%2FM%2F1%20Queue%20Length%20vs.%20Utilization%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%20Key%20Takeaway%0A%0A%20%20%20%20For%20any%20system%20approximated%20by%20an%20M%2FM%2F1%20queue%2C%20**never%20target%20utilization%20above%2080%E2%80%9385%25**%20if%20low%20latency%20matters.%20The%20last%20few%20percent%20of%20throughput%20come%20at%20an%20enormous%20cost%20in%20queue%20length%20and%20wait%20time.%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