marimo-team/marimo-learn

1# /// script2# requires-python = ">=3.13"3# dependencies = [4#     "altair",5#     "asimpy",6#     "marimo",7#     "polars==1.24.0",8# ]9# ///10 11import marimo12 13__generated_with = "0.20.4"14app = marimo.App(width="medium")15 16 17@app.cell(hide_code=True)18def _():19    import marimo as mo20    import random21    import statistics22 23    import altair as alt24    import polars as pl25 26    from asimpy import Environment, Process, Queue, PriorityQueue27 28    return Environment, Process, Queue, PriorityQueue, alt, mo, pl, random, statistics29 30 31@app.cell(hide_code=True)32def _(mo):33    mo.md(r"""34    # The Convoy Effect35 36    ## *One Slow Job Ruins Everyone's Day*37 38    A single server processes jobs that arrive randomly (Poisson process). Most jobs are quick (exponential service with small mean), but a rare few are very slow (exponential service with large mean). This *hyperexponential* service distribution has high variance. This tutorial compares the performance of two scheduling disciplines in this situation:39 40    - FIFO (First In, First Out): jobs are served in the order they arrive.41    - SJF (Shortest Job First): the server always picks the shortest queued job next.42 43    The surprising result is that SJF dramatically outperforms FIFO: not just for the small jobs that directly benefit from skipping ahead, but also for mean sojourn time across *all* jobs. The improvement is most visible at the tail (95th and 99th percentiles) because FIFO creates a *convoy effect*: one long job blocks many short jobs behind it, inflating everyone's wait.44 45    ### The Convoy Metaphor46 47    Picture a one-lane road with one slow truck and many fast cars. Every car behind the truck must drive at truck speed; no overtaking allowed. The truck is the long job; the cars are the short jobs stuck behind it in FIFO order. SJF is like a passing lane: fast cars jump ahead of the truck and reach their destination much sooner. The truck itself arrives at the same time either way, but the total delay experienced by all vehicles plummets.48 49    ### Why FIFO Hurts with High Variance50 51    In FIFO, the server's current job is chosen at arrival time, not at decision time. When a slow job begins service, every subsequent arrival must join the queue and wait. The expected excess work in service (the remaining time of the current job, seen by an arriving customer) under FIFO is:52 53    $$W_{\text{FIFO}} = \frac{\lambda \overline{s^2}}{2(1-\rho)} + \frac{1}{\mu}$$54 55    where $\overline{s^2}$ is the second moment of service time. High variance inflates $\overline{s^2}$ without changing $\rho$, directly worsening wait time.56 57    ### SJF Minimises Mean Sojourn Time58 59    For a single server with non-preemptive SJF and any service-time distribution, the mean sojourn time is given by the formula below (which is discussed in "Understanding the Math" at the end of this lesson):60 61    $$W_{\text{SJF}} = \frac{1}{\mu} + \frac{\lambda \overline{s^2}}{2(1-\rho)}$$62 63    SJF achieves this minimum because short jobs that would otherwise be blocked by a long job are promoted ahead, reducing the total waiting work in the system.64 65    ## Practical Relevance66 67    Operating system CPU schedulers use time-quanta and priority aging to approximate SJF without knowing job sizes in advance. Database query planners estimate query cost and reorder execution to minimize blocking. The phenomenon reappears as *head-of-line blocking* in HTTP/1.1 (one slow response stalls a connection), motivating HTTP/2 multiplexing and HTTP/3's QUIC stream independence.68    """)69    return70 71 72@app.cell(hide_code=True)73def _(mo):74    mo.md(r"""75    ## Implementation76 77    Jobs are placed in a `PriorityQueue` for SJF (tupled as `(service_time, job_id)` so shorter jobs sort earlier) or a plain `Queue()` for FIFO (tupled as `(job_id, service_time)` to preserve arrival order). The same hyperexponential service-time generator (90% short, 10% long) is used in both runs.78    """)79    return80 81 82@app.cell(hide_code=True)83def _(mo):84    sim_time_slider = mo.ui.slider(85        start=0,86        stop=100_000,87        step=1_000,88        value=20_000,89        label="Simulation time",90    )91 92    arrival_rate_slider = mo.ui.slider(93        start=0.1,94        stop=1.5,95        step=0.05,96        value=0.7,97        label="Arrival rate",98    )99 100    seed_input = mo.ui.number(101        value=192,102        step=1,103        label="Random seed",104    )105 106    run_button = mo.ui.run_button(label="Run simulation")107 108    mo.vstack([109        sim_time_slider,110        arrival_rate_slider,111        seed_input,112        run_button,113    ])114    return arrival_rate_slider, seed_input, sim_time_slider115 116 117@app.cell118def _(arrival_rate_slider, seed_input, sim_time_slider):119    SIM_TIME = int(sim_time_slider.value)120    ARRIVAL_RATE = float(arrival_rate_slider.value)121    SEED = int(seed_input.value)122    SHORT_RATE = 4.0123    LONG_RATE = 0.2124    LONG_PROB = 0.10125    return ARRIVAL_RATE, LONG_PROB, LONG_RATE, SEED, SHORT_RATE, SIM_TIME126 127 128@app.cell129def _(LONG_PROB, LONG_RATE, SHORT_RATE, random):130    def service_time():131        if random.random() < LONG_PROB:132            return random.expovariate(LONG_RATE)133        return random.expovariate(SHORT_RATE)134 135    return (service_time,)136 137 138@app.cell139def _(ARRIVAL_RATE, Process, random, service_time):140    class JobSource(Process):141        def init(self, job_queue, arrivals, sjf):142            self.job_queue = job_queue143            self.arrivals = arrivals144            self.sjf = sjf145            self._jid = 0146 147        async def run(self):148            while True:149                await self.timeout(random.expovariate(ARRIVAL_RATE))150                jid = self._jid151                self._jid += 1152                svc = service_time()153                self.arrivals[jid] = (self.now, svc)154                if self.sjf:155                    await self.job_queue.put((svc, jid))156                else:157                    await self.job_queue.put((jid, svc))158 159    return (JobSource,)160 161 162@app.cell163def _(Process):164    class Server(Process):165        def init(self, job_queue, arrivals, sojourn_times, sjf):166            self.job_queue = job_queue167            self.arrivals = arrivals168            self.sojourn_times = sojourn_times169            self.sjf = sjf170 171        async def run(self):172            while True:173                item = await self.job_queue.get()174                if self.sjf:175                    svc, jid = item176                else:177                    jid, svc = item178                await self.timeout(svc)179                arrival_time, _ = self.arrivals[jid]180                self.sojourn_times.append(self.now - arrival_time)181 182    return (Server,)183 184 185@app.cell186def _(Environment, JobSource, Queue, PriorityQueue, SIM_TIME, Server, statistics):187    def simulate(sjf):188        arrivals = {}189        sojourn_times = []190        env = Environment()191        q = PriorityQueue(env) if sjf else Queue(env)192        JobSource(env, q, arrivals, sjf)193        Server(env, q, arrivals, sojourn_times, sjf)194        env.run(until=SIM_TIME)195        return {196            "mean": statistics.mean(sojourn_times),197            "median": statistics.median(sojourn_times),198            "p95": sorted(sojourn_times)[int(0.95 * len(sojourn_times))],199            "p99": sorted(sojourn_times)[int(0.99 * len(sojourn_times))],200            "n": len(sojourn_times),201        }202 203    return (simulate,)204 205 206@app.cell207def _(LONG_PROB, LONG_RATE, SEED, SHORT_RATE, pl, random, simulate):208    def run_scenarios():209        fifo = simulate(sjf=False)210        sjf_res = simulate(sjf=True)211        rows = [212            {213                "metric": m,214                "fifo": fifo[m],215                "sjf": sjf_res[m],216                "improvement": fifo[m] / sjf_res[m],217            }218            for m in ("mean", "median", "p95", "p99")219        ]220        return pl.DataFrame(rows)221 222    random.seed(SEED)223    df = run_scenarios()224    mean_svc = (1 - LONG_PROB) / SHORT_RATE + LONG_PROB / LONG_RATE225    return df, mean_svc226 227 228@app.cell(hide_code=True)229def _(ARRIVAL_RATE, LONG_PROB, LONG_RATE, SHORT_RATE, mean_svc, mo):230    mo.md(f"""231    ## Summary Statistics232 233    Arrival rate: {ARRIVAL_RATE}, estimated mean service: {mean_svc:.3f}234 235    Short jobs: {100 * (1 - LONG_PROB):.0f}% (mean {1 / SHORT_RATE:.2f}),236    Long jobs: {100 * LONG_PROB:.0f}% (mean {1 / LONG_RATE:.1f})237 238    > **Note:** SJF is optimal for mean sojourn time but requires knowing job sizes in advance.239    """)240    return241 242 243@app.cell244def _(df):245    df246    return247 248 249@app.cell250def _(alt, df, pl):251    df_plot = df.filter(pl.col("metric") != "n").unpivot(252        on=["fifo", "sjf"],253        index="metric",254        variable_name="policy",255        value_name="sojourn_time",256    )257    chart = (258        alt.Chart(df_plot)259        .mark_bar()260        .encode(261            x=alt.X("metric:N", title="Metric"),262            y=alt.Y("sojourn_time:Q", title="Sojourn time"),263            color=alt.Color("policy:N", title="Policy"),264            xOffset="policy:N",265            tooltip=["metric:N", "policy:N", "sojourn_time:Q"],266        )267        .properties(title="Convoy Effect: FIFO vs. Shortest Job First")268    )269    chart270    return271 272 273@app.cell(hide_code=True)274def _(mo):275    mo.md(r"""276    ## Understanding the Math277 278    ### The second moment279 280    For a random variable $S$ representing service time, the second moment is $E[S^2]$. Recall from your statistics course that variance is $\text{Var}(S) = E[S^2] - (E[S])^2$, which rearranges to:281 282    $$E[S^2] = \text{Var}(S) + (E[S])^2$$283 284    This means high variance inflates $E[S^2]$ even if the mean $E[S]$ stays fixed. Doubling the spread of service times can quadruple $E[S^2]$, even with the same average service time.285 286    ### Why variance of service time hurts287 288    Imagine a FIFO server handling jobs that are either 0.1 minutes or 10 minutes long, with 90% being short and 10% being long. The mean service time is $0.9 \times 0.1 + 0.1 \times 10 = 1.09$ minutes, so utilization $\rho = \lambda / \mu$ might be modest. But when a 10-minute job starts, every job arriving during those 10 minutes must join the queue and wait. The longer $E[S^2]$, the more average work sits ahead of each arriving job.289 290    ### The Pollaczek–Khinchine formula291 292    The mean time a job spends waiting (not counting its own service time) in a FIFO single-server queue is:293 294    $$W_q = \frac{\lambda \cdot E[S^2]}{2(1 - \rho)}$$295 296    Here $\lambda$ is the arrival rate, $E[S^2]$ is the second moment of service time, and $\rho = \lambda \cdot E[S]$ is the server utilization. Both $\lambda$ and $E[S^2]$ appear in the numerator, so more variance means more waiting even at the same $\rho$. The $(1-\rho)$ denominator is the familiar blow-up term from M/M/1.297    """)298    return299 300 301if __name__ == "__main__":302    app.run()303