--- title: 'Input/Output Models' source: 'https://academia.sh/en/courses/operating-system-concepts/input-output-models' course: 'Operating System Concepts' language: en updated: '2026-08-17T18:08:20+00:00' license: 'CC BY-SA 4.0' --- # Input/Output Models Blocking, non-blocking, and asynchronous input/output measured on the same workload: the polling model drives processor utilization to 1.0000 and never changes the duration, the asynchronous model drops duration from 248 to 38. The previous lesson counted reading a block as one step and never asked how long that step takes. In the common definition, one input/output operation takes **30 time units**; one compute step is one time unit. That factor of thirty is the single number that decides where a process's time goes. This lesson counts three decisions about what the processor does while facing that factor of thirty, on the same workload: wait, ask, or do other work. The result is the course's most contrarian measurement — one of the three models keeps the processor completely full and does not finish its work even one time unit sooner. ## Three Models In a **blocking** call, the process issues the request and leaves the ready queue until it completes; the processor can be handed to another process during this time, but the requesting process does nothing at all. In a **polling** setup, the process is not blocked, it keeps asking whether the operation is complete; this is **busy waiting** and it holds the processor. In an **asynchronous** setup, the process issues the request, returns immediately, does other work, and completion arrives through a notification. The hardware counterpart of the notification is an interrupt; the interrupt itself was defined in the Interrupts lesson of the How Computers Work course and is used here only as a completion notification. - **BD27** — An input/output operation's latency is 30 time units, the processor work per request is 1 time unit. Eight requests are measured. - **BD28** — In the asynchronous model, eight requests can be in flight at once and their latencies fully overlap; the disk serves all eight in parallel. - **BD29** — Processor utilization is the ratio of steps the processor spends busy to total duration. Busy waiting counts as busy — the processor really is executing an instruction. - **BD30** — This lesson is a single machine. There is no network cost, remote call, or data transfer cost of any kind. ```python """M01/K05 common definition (excerpt): input/output models.""" WAIT_TIME = 30 # latency of one input/output operation , time units def io_model(requests, policy="blocking", latency=WAIT_TIME, per_request=1): """requests: how many input/output operations. Returns: duration , busy steps , utilization.""" if policy == "blocking": duration = requests * (latency + per_request) busy = requests * per_request elif policy == "polling": duration = requests * (latency + per_request) busy = duration # busy waiting: processor is always full else: duration = latency + requests * per_request busy = requests * per_request return {"duration": duration, "busy": busy, "utilization": round(busy / duration, 4)} print("eight requests , the common definition's measurement") for y in ("blocking", "polling", "asynchronous"): print(f" {y:12s}", io_model(8, y)) print() print("requests blocking polling asynchronous") print(" duration util. duration util. duration util.") for requests in (1, 2, 4, 8, 16, 32): e = io_model(requests, "blocking") y = io_model(requests, "polling") a = io_model(requests, "asynchronous") print(f"{requests:5d} {e['duration']:6d} {e['utilization']:8.4f} {y['duration']:6d}" f" {y['utilization']:8.4f} {a['duration']:6d} {a['utilization']:8.4f}") ``` ``` eight requests , the common definition's measurement blocking {'duration': 248, 'busy': 8, 'utilization': 0.0323} polling {'duration': 248, 'busy': 248, 'utilization': 1.0} asynchronous {'duration': 38, 'busy': 8, 'utilization': 0.2105} requests blocking polling asynchronous duration util. duration util. duration util. 1 31 0.0323 31 1.0000 31 0.0323 2 62 0.0323 62 1.0000 32 0.0625 4 124 0.0323 124 1.0000 34 0.1176 8 248 0.0323 248 1.0000 38 0.2105 16 496 0.0323 496 1.0000 46 0.3478 32 992 0.0323 992 1.0000 62 0.5161 ``` Three numbers sit side by side. **Baseline:** blocking calls, eight requests, **248 time units**, processor utilization 0.0323. **Setup:** the asynchronous model, **38 time units**, utilization 0.2105. **Cost:** processing eight completion notifications and keeping a ledger of eight simultaneously in-flight requests — both get counted shortly. ## High Utilization Is Not a Success Metric The table's middle column is the course's most contrarian result. The polling model drives processor utilization to **1.0000**: the processor is never idle, a command executes on every time unit. The duration on the same row is **248** — identical to the blocking model. Keeping the processor completely full did not bring the work forward by even one time unit. The reason reads directly from the definition. In the polling model, the processor's commands ask "is it done yet"; they produce no work. Of the 248 busy steps, only 8 are real work, the remaining 240 are the waiting step spent in a different form. The blocking model leaves those same 240 steps idle; the polling model fills them and **speeds up nothing.** The rule that follows concerns metric choice. Processor utilization is a **proxy metric**: the question actually being asked is "when does the work finish," but because it is easy to measure, utilization stands in for that question instead. On this workload the proxy runs backward — the highest-utilization model does not give the best duration, and the model that does, the asynchronous one, has a utilization of only 0.2105. If a setup's utilization is high, nothing can be said without asking **what it is full of**. How the asynchronous model wins is in the same table. Its duration barely moves with request count: 31 at one request, 62 at thirty-two. The blocking model climbs from 31 to 992 while the asynchronous model does not even double, because the thirty-unit latency is paid once and every request overlaps inside it. The gain grows with request count: 6.5 times at eight, 16 times at thirty-two. ## Non-Blocking Calls and the Polling Interval The mechanism beneath the polling setup is a separate concept with a separate name. A **non-blocking** call does not put the process to sleep if the result is not ready; it returns immediately, saying "not ready yet." Polling is repeating that call inside a loop. The two are not the same thing: a non-blocking call is an interface property, polling is only one way of using it — and the most expensive one. In the measurement above, polling was done every time unit. The interval can be widened; the processor then asks less often, but notices completion later. - **BD31** — Polling happens at fixed intervals, and each question takes one time unit. Completion is noticed on the first question after the latency elapses. ```python """Non-blocking calls: which two costs the polling interval pits against each other.""" LATENCY = 30 REQUESTS = 8 print("interval polls noticed at extra delay total duration processor steps") for interval in (1, 2, 4, 7, 10, 30, 45): polls = -(-LATENCY // interval) # how many questions until completion is noticed noticed = polls * interval # moment of notice print(f"{interval:8d} {polls:5d} {noticed:10d} {noticed - LATENCY:11d}" f" {REQUESTS * (noticed + 1):14d} {REQUESTS * (polls + 1):15d}") ``` ``` interval polls noticed at extra delay total duration processor steps 1 30 30 0 248 248 2 15 30 0 248 128 4 8 32 2 264 72 7 5 35 5 288 48 10 3 30 0 248 32 30 1 30 0 248 16 45 1 45 15 368 16 ``` As the interval widens from 1 to 30, processor steps drop from **248 to 16** and duration stays at 248: on this workload, 240 of polling's steps were entirely wasted work. But the table does not run in a straight line. At intervals 4 and 7, the delay before completion is noticed stretches by 2 and 5 units, and duration climbs to 264 and 288; at interval 45, completion is noticed 15 units late and duration jumps to 368. Wherever the interval does not evenly divide the latency, a remainder is paid — the cost of not knowing exactly when the operation will finish. The gap between the two extremes is this: **a small interval costs the processor, a large one costs response time.** There is no single best point in between — the 30-unit interval minimizes both costs here only because the latency happens to be known to be exactly 30. If the latency varies, that knowledge is gone and the choice turns back into a guess. The asynchronous model, using a completion notification, removes this guess entirely — in exchange it needs a mechanism to process the notification. ## Two Limits of Asynchrony The measurement above counted two things as free: processing the completion notification, and requests being independent of one another. Neither is always true. - **BD32** — Processing one completion notification takes `notification` time units; this is the interrupt handler running and the request being struck off the ledger. The swept value ranges from 0 to 16. - **BD33** — In a dependent chain, every request uses the previous one's result; so latencies cannot overlap. ```python """Two limits of the asynchronous model: notification cost and dependency.""" LATENCY = 30 REQUESTS = 8 def asynchronous(requests, notification=0, dependent=False): """notification: time units to process each completion notification. dependent: if every request waits on the previous one's result , there is no overlap.""" per_request = 1 + notification duration = requests * (LATENCY + per_request) if dependent else LATENCY + requests * per_request busy = requests * per_request return {"duration": duration, "busy": busy, "utilization": round(busy / duration, 4)} print("independent requests , notification cost swept") print("notification duration busy util. gain over blocking") for b in (0, 1, 2, 4, 8, 16): a = asynchronous(REQUESTS, b) print(f"{b:12d} {a['duration']:8d} {a['busy']:4d} {a['utilization']:8.4f}" f" {REQUESTS * (LATENCY + 1) / a['duration']:19.2f}") print() print("dependent chain (each request waits on the previous)") for b in (0, 1): a = asynchronous(REQUESTS, b, dependent=True) print(f" notification {b}: duration {a['duration']} utilization {a['utilization']}") print(" blocking model's duration:", REQUESTS * (LATENCY + 1)) ``` ``` independent requests , notification cost swept notification duration busy util. gain over blocking 0 38 8 0.2105 6.53 1 46 16 0.3478 5.39 2 54 24 0.4444 4.59 4 70 40 0.5714 3.54 8 102 72 0.7059 2.43 16 166 136 0.8193 1.49 dependent chain (each request waits on the previous) notification 0: duration 248 utilization 0.0323 notification 1: duration 256 utilization 0.0625 blocking model's duration: 248 ``` The first limit is the notification's cost. When 16 time units of processing are added to each completion, duration climbs from 38 to **166** and the gain over the blocking model drops from 6.53 times to **1.49 times**. What stands out is that utilization climbs from **0.2105 to 0.8193** across the same sweep: the model slows down at every step while its metric keeps improving — the second proof that utilization is not a success metric. The second limit is dependency. If requests wait on one another's results, there is nothing left to overlap; the asynchronous model finishes in **248 time units**, exactly the same as the blocking model. Once notification processing is added, it climbs to **256**, and the asynchronous setup becomes **worse** than the blocking one. What asynchrony sells is not speed, it is **overlap**; with no work to overlap, all that remains is bookkeeping cost. ## Summary - On eight input/output requests, the blocking model finishes in 248 time units at 0.0323 utilization; the polling model finishes in the same 248 at 1.0000 utilization; the asynchronous model finishes in 38 at 0.2105 utilization. - Busy waiting fills the processor and speeds up nothing: of the 248 busy steps, only 8 produce work, 240 are the question "is it done yet." - Processor utilization is a proxy metric and runs backward on this workload; if a setup's utilization is high, no conclusion follows without asking what it is full of. - A non-blocking call is an interface property, polling is one way of using it; widening the polling interval from 1 to 30 drops processor steps from 248 to 16, but when the interval does not evenly divide the latency, duration stretches to 288 and 368. - The asynchronous model's gain comes from overlap and grows with request count: 6.5 times at eight requests, 16 times at thirty-two. - The gain erodes under two conditions: it drops to 1.49 times once 16 time units are paid per completion notification, and it vanishes when requests depend on one another, dropping below the blocking model once notification cost is added. ## Course Wrap-Up Fifteen lessons modeled a single machine and asked a single question: how many steps does an abstraction charge while it delivers convenience. On every lesson, three numbers stood side by side — the baseline without the abstraction, the setup with it, and the cost between them. The course's rule was this: **an abstraction whose cost goes uncounted counts as unmeasured.** | Lesson | Baseline without abstraction | Setup with abstraction | Cost | |---|---|---|---| | The Process Concept | five processes run one after another: **669** time units | five processes sharing one core: **194** | **22 context switches = 44 time units**, above the real work (39); 111 idle-core steps | | Process Forking | no forking: **0** copied pages | four forks, eager copy: **64 virtual pages** | copy-on-write brings it down to **15 pages**, 49 of which were empty; the advantage disappears past a fault cost of **4** | | Threads | five separate processes: **194** time units, **15** extra virtual pages | five threads in one process: **186**, **4** stack pages | **73.33** percent memory gain, only **8** units in duration; the cost is **isolation disappearing entirely** | | Choosing Between Processes and Threads | a single address space: **0** copied pages, spread ratio **5.0** | five separate address spaces: **1** affected unit | **15** copied pages (64 with eager copy); partial isolation is not linear — 6 pages bring 5 down to 3, the last 5 pages buy only 1 | | Scheduling Algorithms | non-preemptive queue: **194** (189 on the second workload) | time-sliced scheduling: **197** (202 on the second workload) | **206** at slice 1, **36** context switches, wait **33.00**; no best policy in either workload | | Race Conditions | one execution order: **1** result | two threads, a splittable three-step operation: **20** interleavings | **18 wrong** (0.9000); at slice 3, of the **2** reachable interleavings **none** is wrong — the bug does not vanish, it becomes invisible | | Locks, Mutexes, and Semaphores | one thread: **20** time units, **0** wait steps | eight threads, a mutex: **83** | **252** wait steps, utilization from **1.0000 to 0.2410**; waiting is **4.5** times $n(n-1)$ | | Deadlock and Starvation | uncoordinated acquisition: **264** of 648 states locked (0.4074) | ordered acquisition: state space **36**, deadlocked **0** | **+144** wait steps at eight threads; throughput does not drop under starvation, the failure shows only in **distribution** | | Concurrency on Multiple Cores | one core: **197**, 108 idle-core steps | four cores: **179** (lower bound 173) | **639** idle-core steps, total work **fixed at 39**; slice protection disappears, reachable interleavings go from 2 to **20** | | Concurrency Models | thread model: **197** (202 on the second workload) | event loop **178**, message passing **179** | the 1-time-unit gap is **below the measurement band**; the difference shows in idle-core steps: **139 versus 639** | | Virtual Memory | 15 physical pages, 15 compulsory faults, 489 time units | 2 physical pages, paging, first in first out | 15 extra page faults, 450 time units | | Memory Allocation | end-to-end allocation, 6 requests placed | block-list allocator, best fit, 8 requests placed | two 10-byte remainders, external fragmentation ratio 0.5000 | | Garbage Collection | manual release, 0 scan steps | tracing collector, 17 of 40 objects reachable | 17-step pause, 40-step sweep, 57 steps total | | File System Abstraction | contiguous placement, 4741 bytes | 12 blocks of 512 bytes, 6144 bytes on disk | 1403 bytes internal fragmentation, 12 block pointers | | Input/Output Models | blocking call, 248 time units | asynchronous model, 38 time units | 8 completion notifications and a ledger of 8 in-flight requests | The table's second reading is worth more than its first: **an abstraction sometimes makes things worse.** A smarter page replacement policy can produce more faults, best fit can leave behind a more unusable remainder, splitting a pause can grow total work, a journaled layout writes every byte twice, busy waiting fills the processor and speeds up nothing. None of these results were hidden, because someone who cannot tell when an abstraction worsens things also cannot tell when to choose it. The third and most expensive result came from the concurrency topic: **correct output does not mean a correct program.** The same bug is entirely invisible once the scheduler's slice happens to be large enough. The bug does not disappear, it only becomes invisible — and the only thing that reveals an invisible bug is modeling the mechanism and counting every state. Everything measured across the course was measured on **a single machine**. Network cost, remote call latency, and inter-machine data transfer appear in none of these measurements; these numbers lose validity once carried into a distributed setup. The next course, **Modeling and Representation**, takes the model itself as its subject. Here a model was executable text and its output a number; there, a model will be a diagram and its output a question answered. The shared discipline does not change: a diagram earns its keep only when it is clear which question it answers, just as an abstraction counts as measured only once its cost is counted. Showing a system through class, component, sequence, and state diagrams does, in another representation, what this course did with numbers — and there too the criterion for avoiding needless representation is the same question: what does this measure.