Input/Output Models

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.

"""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.

"""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.

"""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.