14. Distributed and Specialized Systems

Every chapter so far has assumed one machine, one clock, and one memory that all parties can see; this chapter removes those assumptions in three different directions. It looks at systems spread across machines that fail independently and share no clock, at systems where being late is as wrong as being incorrect, and at systems where the battery and the user's attention are the scarcest resources. The common thread is that each specialization changes which OS guarantee is negotiable — consistency, throughput, or average latency — and understanding which one is what separates a working design from a plausible-sounding one.

<a id="141-distributed-operating-systems"></a>

14.1 Distributed Operating Systems

A distributed system differs from a multiprocessor in one fundamental way: there is no shared memory and no shared clock, and any component can fail while the others keep running. This section builds from the architectural models used to glue machines together, through the ordering and coordination primitives that replace shared memory, to consensus — the algorithm that lets a group of unreliable machines behave like one reliable one.

Network Operating System Models

Theory

Start with why anyone connects machines at all. A single machine has a hard ceiling on cores, memory, and disk, and — more importantly — it has a single power supply, a single kernel, and a single building. Distribution buys four things: capacity beyond one box, availability despite one box dying, locality so users in Tokyo are not served from Virginia, and sharing of resources that physically live somewhere else (a printer, a dataset, a licence server).

The interesting question is how much of the distribution the programmer has to see. There is a spectrum, and the position on it is the single most useful classification.

A network operating system is the loosely coupled end. Each machine runs its own independent OS, and remoteness is explicit: you ssh to a host, you scp a file, you mount server:/export at a path you chose. The user knows perfectly well which machine is which, and that knowledge is part of the interface. Nothing migrates, nothing is automatic, and when the remote machine dies you get an error mentioning that machine by name.

A distributed operating system is the tightly coupled end. It presents a single system image: one process namespace, one filesystem, one scheduler, spread transparently over many machines. You start a process and the system decides where it runs; it may migrate mid-execution. Amoeba, Sprite, Plan 9, and MOSIX all did this, and they worked. They also essentially disappeared from production computing, for reasons worth understanding rather than memorising.

In between — and this is where virtually all real systems live — sits middleware: an application-level layer that provides selective transparency over ordinary operating systems. Kubernetes, gRPC, Kafka, Spark, and Cassandra are middleware in this sense. They give you some transparency (you address a service, not a host) while leaving the OS boundaries intact and, crucially, leaving failure visible where it matters.

Transparency is the property being traded, and it is not one property but several. The ISO/ODP model names eight; these five carry most of the weight:

Transparency	Hides	Typical mechanism	Cost when it leaks
Access	Local vs remote call syntax	RPC stubs, NFS	Remote calls fail and stall in ways local ones do not
Location	Where a resource physically is	DNS, service discovery	Latency varies by an order of magnitude
Migration	That a resource moved	Handles instead of addresses	In-flight state must move too
Replication	That there are several copies	Quorum reads/writes	Copies disagree; you must choose which to believe
Failure	That a component died	Retries, timeouts	Retries duplicate side effects; "slow" is indistinguishable from "dead"

The last row is why full transparency failed. Failure transparency is not achievable, only approximable, because a node cannot distinguish a crashed peer from a slow peer from a partitioned network — all three look like silence. A system that pretends otherwise does not remove the failure; it removes your ability to handle it.

That insight is captured in the eight fallacies of distributed computing (Deutsch and Gosling), each of which is an assumption that is true locally and false remotely:

1. The network is reliable.
2. Latency is zero.
3. Bandwidth is infinite.
4. The network is secure.
5. Topology does not change.
6. There is one administrator.
7. Transport cost is zero.
8. The network is homogeneous.

Every one of these is an assumption an access-transparent RPC layer quietly invites you to make. This is the core critique of "make remote calls look local": the syntax can be made identical, but the failure semantics cannot, and the failure semantics are what your error handling is built on.

Finally, the physical arrangement. Client-server centralises state at a server (simple, one place to be consistent, one place to fail). Peer-to-peer gives every node the same role (no bottleneck, no single failure point, much harder to reason about). A cluster is many machines under one administrative domain, presented as one service — and it subdivides usefully into high-availability clusters (a standby takes over, requiring a fencing mechanism so two nodes never both believe they are primary — "split brain") and high-performance clusters (the work is partitioned across nodes, as in MPI or Spark).

Example

   THE TRANSPARENCY SPECTRUM

   NETWORK OS                MIDDLEWARE                DISTRIBUTED OS
   (loosely coupled)         (selective)               (single system image)

   +-----------+             +-----------+             +-------------------+
   | OS A      |             | OS A | OS B|            |   one process     |
   | OS B      |             |  middleware |           |   namespace       |
   | OS C      |             |  (k8s,gRPC) |           |   over N machines |
   +-----------+             +-----------+             +-------------------+

   ssh host2 cmd             call svc "cart"           run cmd
   scp f host2:/tmp          k8s picks the pod         system picks the node
   mount srv:/export         retries are YOUR job      process may migrate

   You KNOW the machine      You know it EXISTS        You cannot tell
   Failure names the host    Failure is an error code  Failure is... what?

   NFS, SMB, ssh             Kubernetes, Kafka,        Amoeba, Sprite,
   (everywhere)              Cassandra (everywhere)    Plan 9 (museum)


   WHY THE RIGHT-HAND COLUMN LOST

   Single system image requires hiding failure.
   Hiding failure requires distinguishing:

        crashed node   ---+
        slow node      ---+---> all three look IDENTICAL: silence
        partitioned    ---+

   You cannot. So the abstraction leaks exactly when it matters most,
   and the application -- which has been written as if it cannot leak --
   has no code path for it.

   Middleware won by making failure VISIBLE but MANAGEABLE.


   THE COST OF PRETENDING A REMOTE CALL IS LOCAL

   local function call        remote procedure call
   ------------------------   ---------------------------------
   ~1 ns                      ~0.5 ms LAN, ~150 ms cross-ocean
   never "half-happens"       may execute 0, 1, or MANY times
   fails => exception         may never return at all
   caller/callee same fate    callee may outlive caller, or vice versa
   arguments by reference     arguments serialised (deep copy)

   Same syntax. Entirely different contract.

# The fallacies, made concrete. The SAME operation, three ways.

import time, socket, requests

# --- 1. Local call: the baseline contract ----------------------------
def get_user_local(db, uid):
    return db[uid]                       # ~100 ns, cannot partially fail

# --- 2. Network-OS style: remoteness is explicit ----------------------
#    The programmer NAMES the machine. Failure mentions the machine.
def get_user_nos(uid):
    s = socket.create_connection(("users.internal", 9000), timeout=2.0)
    s.sendall(f"GET {uid}\n".encode())
    return s.recv(4096)                  # ConnectionRefused / timeout
    # The error tells you WHICH host failed -- that is the point.

# --- 3. Middleware style: selective transparency ----------------------
#    You address a SERVICE, not a host. But failure stays visible,
#    and handling it is still your job.
def get_user_middleware(uid, attempts=3):
    for n in range(attempts):
        try:
            # "users" resolves via service discovery to SOME instance.
            r = requests.get(f"http://users/v1/{uid}", timeout=2.0)
            r.raise_for_status()
            return r.json()
        except requests.Timeout:
            # A timeout does NOT mean the request did not execute.
            # It means you do not know. Retrying a non-idempotent
            # operation here is how duplicate charges happen.
            time.sleep(2 ** n * 0.1)     # exponential backoff
    raise RuntimeError("users service unreachable")

# --- The trap access transparency sets --------------------------------
#   for uid in all_users:        # 10,000 users
#       get_user_middleware(uid) # looks like a loop over a dict
#   Local:  10,000 * 100 ns  = 1 ms
#   Remote: 10,000 * 0.5 ms  = 5 SECONDS, and any one can fail.
#   The N+1 query problem is fallacy #2 ("latency is zero") in the wild.

# ---- Network OS: remoteness is part of the interface ----
ssh build-07 'make -j32'          # you chose the machine
scp results.tar build-07:/data/   # you chose the direction
mount -t nfs fileserver:/export /mnt/shared
ls /mnt/shared                    # hangs hard if fileserver is down:
                                  # access transparency without failure
                                  # transparency -- the classic NFS hang

# ---- Middleware: you address a service, the system picks a host ----
kubectl run job --image=build:v2   # you did NOT choose the node
kubectl get pods -o wide           # ...but you can still SEE which one
curl http://users/v1/42            # "users" is a name, not a machine

# ---- Measure fallacy #2 for yourself ----
ping -c 5 localhost                # ~0.03 ms
ping -c 5 gateway                  # ~0.5  ms   (LAN: ~15x)
ping -c 5 example.com              # ~120  ms   (WAN: ~4000x)
# Anything that loops over a remote call inherits this multiplier.

Key takeaways

• Distribution buys capacity, availability, locality, and resource sharing, and pays for it with partial failure and the loss of a shared clock and shared memory.
• A network OS keeps machines independent and makes remoteness explicit; a distributed OS presents a single system image; middleware provides selective transparency over ordinary operating systems and is what real systems use.
• Transparency is several distinct properties — access, location, migration, replication, failure — and they can be adopted independently.
• Failure transparency is unachievable in principle because a crashed node, a slow node, and a partitioned network are indistinguishable from the outside.
• The eight fallacies of distributed computing are each an assumption that holds locally and fails remotely; access-transparent RPC quietly encourages all of them.
• Client-server centralises state and failure, peer-to-peer removes the bottleneck at the cost of reasoning difficulty, and clusters present many machines as one service.
• High-availability clusters require a fencing mechanism to prevent split brain, where two nodes both believe they are the primary.
• A timeout means "unknown", not "did not happen" — which is why retrying non-idempotent operations is a correctness bug, not a robustness feature.

🧪 Practice

1. Classify each of the following as network OS, middleware, or distributed OS, and justify it in one sentence: NFS, Kubernetes, Plan 9, ssh, Cassandra, MOSIX.
2. Take a loop that fetches 500 records one at a time from a remote service at 0.4 ms RTT. Compute the total time, then explain which of the eight fallacies the code's author assumed and how batching fixes it.
3. Mount an NFS share (or simulate one), kill the server, and observe what ls does on the mount point. Explain which transparency was provided and which was not.
4. Interview-style: "Our RPC framework makes remote calls look exactly like local function calls. Is that good?" Hint: write down the contract of a local call — timing, failure modes, how many times it executes — and check each line against a remote one.

Distributed Coordination

Theory

Once you have several machines that must act as one system, you need them to agree on things: who is in charge, whether a transaction committed, who holds a lock, which nodes are alive. On one machine all of this is trivial — there is a shared memory word, and a mutex protecting it. Distributed coordination is the study of what replaces that word when there is no shared memory.

Begin with the system model, because every algorithm's correctness depends on it. Two axes matter.

Timing. In a synchronous system, message delay and processing time have known upper bounds, so a timeout is proof of failure. In an asynchronous system there are no bounds, so a timeout proves nothing. Real networks are partially synchronous: usually well-behaved, occasionally arbitrarily slow. Algorithms must be safe (never wrong) in the asynchronous model and live (eventually make progress) during synchronous periods. This split is the single most important design pattern in the field.

Failures. Ordered from benign to malicious:

Failure model	Node behaviour	Nodes needed to tolerate f	Used by
Crash-stop	Halts, never returns	2f + 1	Raft, Paxos, etcd
Crash-recovery	Halts, later returns with stable storage	2f + 1	Real Raft implementations
Omission	Drops some messages	2f + 1	Modelled as crash
Byzantine	Arbitrary, possibly malicious	3f + 1	PBFT, blockchains

Next, failure detection, which is the practical form of "is that node alive?". The standard mechanism is a heartbeat: each node periodically announces itself, and a peer that has not been heard from within a timeout is suspected. Note the word — suspected, not known. Choosing the timeout is a direct trade-off: short timeouts detect real failures fast but generate false positives during a GC pause or a network hiccup, and a false positive that triggers failover is often more damaging than the failure it was guarding against. Phi-accrual detectors (used by Cassandra and Akka) improve on this by outputting a continuous suspicion level derived from the observed distribution of heartbeat intervals, letting each consumer pick its own threshold.

A lease is the coordination primitive that makes this workable. A lease is a lock with an expiry: the holder gets a resource for a bounded time, and if it does not renew, the lease expires and someone else may take it. The crucial property is that the granter can hand the resource on after expiry without contacting the old holder — which matters precisely because the old holder may be unreachable. Leases convert "is it alive?" (unanswerable) into "has its lease expired?" (locally decidable by a clock).

Leader election reduces many coordination problems to one: elect a single coordinator, then let it decide sequentially, which restores the single-machine reasoning you are used to. Two classical algorithms:

• Bully algorithm. A node that notices the leader is gone sends ELECTION to all higher-numbered nodes. If none answer, it declares itself leader. If one answers, it drops out and waits. The highest live node always wins; it costs O(n²) messages in the worst case.
• Ring algorithm. Nodes are logically ordered in a ring. An election message circulates carrying the IDs of live nodes; when it returns to the initiator, the highest ID becomes leader. O(n) messages, but requires the ring to be maintained.

Both are correct only in a synchronous model. In a partially synchronous one they can elect two leaders — which is why production systems elect leaders through consensus (covered in the last topic of this section) rather than with these algorithms.

Finally, atomic commit: making a transaction that spans several nodes either commit everywhere or abort everywhere. Two-phase commit (2PC) is the standard protocol. A coordinator asks every participant to prepare; a participant that votes yes must be able to commit afterwards no matter what, so it writes the transaction durably and gives up its right to abort. If all vote yes, the coordinator logs COMMIT and tells everyone; any no vote means abort.

2PC is atomic but blocking. If the coordinator crashes after participants have voted yes but before the decision arrives, those participants are stuck: they cannot commit (maybe someone voted no) and cannot abort (maybe everyone voted yes), and they are holding locks the whole time. Three-phase commit adds a pre-commit round to remove the blocking, but is unsafe under network partitions and is essentially unused. The real fix is to make the coordinator itself fault-tolerant by replicating its decision log through consensus — which is what Spanner and modern distributed databases do.

Example

   HEARTBEATS AND THE TIMEOUT TRADE-OFF

   node A -- "alive" --> node B    every 1 s
                                   B suspects A after T seconds

   T = 2 s   fast detection, but a 2.5 s GC pause triggers a FALSE
             failover: a healthy leader is deposed, in-flight work lost
   T = 30 s  almost no false positives, but 30 s of downtime on a
             REAL crash

   There is no correct T. There is only the cost of each mistake.
   Phi-accrual: output suspicion LEVEL from observed inter-arrival
   distribution; each consumer picks its own threshold.


   THE BULLY ALGORITHM (highest live ID wins)

   Nodes 1..5, leader was 5, node 5 crashes.

   t0  node 2 notices silence from 5
   t1  2 -> ELECTION -> 3, 4, 5        (only HIGHER ids)
   t2  3 -> OK -> 2                    2 drops out
       4 -> OK -> 2                    2 drops out
       5 -> (silence, it is dead)
   t3  3 -> ELECTION -> 4, 5           3 and 4 now run their own
       4 -> ELECTION -> 5
   t4  4 -> OK -> 3                    3 drops out
       5 -> (silence)
   t5  4 -> COORDINATOR -> 1,2,3       node 4 is leader

   Worst case O(n^2) messages. Correct only if timeouts are RELIABLE.


   TWO-PHASE COMMIT, AND ITS FAILURE MODE

   PHASE 1 (prepare)              PHASE 2 (commit)
   C --prepare--> P1              C --commit--> P1  ack
   C --prepare--> P2              C --commit--> P2  ack
   C --prepare--> P3              C --commit--> P3  ack
        <--YES-- all                   all durable, locks released

   Any NO, or any timeout in phase 1  =>  ABORT everywhere. Fine.

   THE BLOCKING CASE:
   C --prepare--> P1,P2,P3
        <--YES-- all
   C writes COMMIT to its log
   C CRASHES before sending anything
                                  P1,P2,P3: voted YES, holding locks,
                                  cannot commit (was there a NO?),
                                  cannot abort (maybe all said YES).
                                  They BLOCK until C returns. Forever,
                                  if C's disk is gone.

   Fix in practice: replicate C's decision log via consensus,
   so "the coordinator" survives losing any single machine.


   LEASES: TURNING AN UNANSWERABLE QUESTION INTO A LOCAL ONE

   "Is node A alive?"           -> cannot be answered remotely
   "Has A's lease expired?"     -> check your own clock. Done.

   t=0   A acquires lease, TTL 10 s
   t=5   A renews  (TTL now to t=15)
   t=6   A is partitioned away
   t=15  lease expires; B may safely take over
         -- WITHOUT needing to reach A, which is the whole point.

   Caveat: A may not KNOW it lost the lease (its clock, its pause).
   => the resource must reject stale holders. See fencing tokens.

# Failure detection and leader election, reduced to their essentials.

import time, threading

# ---------------- Heartbeat failure detector -------------------------
class FailureDetector:
    """Suspects a peer after `timeout` seconds of silence.
    Note: suspect(), never dead(). The distinction is the whole subject."""
    def __init__(self, timeout=5.0):
        self.timeout = timeout
        self.last_seen = {}                     # peer -> monotonic time

    def heartbeat(self, peer):
        self.last_seen[peer] = time.monotonic()

    def suspected(self, peer):
        last = self.last_seen.get(peer, 0)
        return (time.monotonic() - last) > self.timeout

    def alive(self):
        return [p for p in self.last_seen if not self.suspected(p)]

# ---------------- Bully election -------------------------------------
class BullyNode:
    def __init__(self, node_id, peers, transport):
        self.id, self.peers, self.net = node_id, peers, transport
        self.leader = None

    def start_election(self):
        higher = [p for p in self.peers if p > self.id]
        if not higher:                          # nobody above me
            return self.declare_victory()
        responses = [self.net.send(p, "ELECTION", timeout=2.0)
                     for p in higher]
        if not any(r == "OK" for r in responses):
            # Every higher node is silent => treat as dead. This
            # inference is ONLY valid in a synchronous model; a slow
            # higher node here produces TWO leaders.
            return self.declare_victory()
        # Someone higher is alive: stand down and await COORDINATOR.

    def declare_victory(self):
        self.leader = self.id
        for p in self.peers:
            self.net.send(p, f"COORDINATOR {self.id}")

# ---------------- Lease, with the renewal loop -----------------------
class Lease:
    def __init__(self, ttl=10.0):
        self.ttl, self.holder, self.expires = ttl, None, 0.0
        self.lock = threading.Lock()
        self.epoch = 0                          # monotonic fencing token

    def acquire(self, who):
        with self.lock:
            now = time.monotonic()
            if self.holder is None or now > self.expires:
                self.holder, self.expires = who, now + self.ttl
                self.epoch += 1                 # NEW epoch each handover
                return self.epoch               # caller must present this
            return None                         # still held by someone

    def renew(self, who, token):
        with self.lock:
            # Renewal fails if the lease already expired and was regranted.
            if self.holder == who and token == self.epoch \
               and time.monotonic() <= self.expires:
                self.expires = time.monotonic() + self.ttl
                return True
            return False

# Two-phase commit, including the blocking window, made explicit.

class Participant:
    def __init__(self, name):
        self.name, self.state = name, "IDLE"

    def prepare(self, txn):
        if not self.can_commit(txn):
            self.state = "ABORTED"
            return "NO"
        self.write_ahead_log(txn)     # MUST be durable before voting YES:
        self.state = "PREPARED"       # after this we have given up the
        return "YES"                  # right to unilaterally abort

    def decide(self, decision):       # phase 2
        self.state = decision         # COMMITTED or ABORTED; locks freed

class Coordinator:
    def commit(self, txn, participants):
        votes = []
        for p in participants:
            try:
                votes.append(p.prepare(txn))
            except TimeoutError:
                votes.append("NO")    # a silent participant means abort:
                                      # phase 1 timeouts are SAFE
        decision = "COMMIT" if all(v == "YES" for v in votes) else "ABORT"
        self.log(decision)            # <-- the point of no return
        # ***  If we crash HERE, every participant that voted YES is    ***
        # ***  blocked: holding locks, unable to decide, until we       ***
        # ***  return. Phase-2 timeouts are NOT safe to resolve locally.***
        for p in participants:
            p.decide(decision)        # retried until acked, forever
        return decision

Key takeaways

• Coordination algorithms are only correct relative to a system model; assume asynchrony for safety and partial synchrony for liveness.
• Failure models run from crash-stop (tolerate f with 2f + 1 nodes) to Byzantine (3f + 1), and choosing the wrong one is choosing the wrong algorithm.
• Heartbeat detectors suspect rather than know; the timeout trades detection speed against false failovers, and a false failover often costs more than the failure it pre-empts.
• Phi-accrual detectors emit a continuous suspicion level from observed heartbeat statistics instead of a single hard threshold.
• A lease is a lock with an expiry, converting the unanswerable "is it alive?" into the locally decidable "has the lease expired?".
• Bully and ring elections are simple but correct only under synchronous timing; production systems elect leaders through consensus instead.
• Two-phase commit is atomic but blocking: a coordinator crash between the prepare votes and the decision leaves participants holding locks with no safe local resolution.
• Phase-1 timeouts are safe (abort), phase-2 timeouts are not — the asymmetry is the entire weakness of 2PC, and the fix is a consensus-replicated coordinator.

🧪 Practice

1. A service has a 5-second heartbeat timeout and a JVM whose full GC pauses can reach 8 seconds. Describe the sequence of events that follows a full GC on the leader, and name two mitigations.
2. Trace the bully algorithm for five nodes where node 5 (the leader) crashes and node 1 notices first. Count the messages sent.
3. Implement the Participant class above so that prepare survives a process restart, and explain which specific write must reach stable storage before YES is returned.
4. Interview-style: "Why do we not just use two-phase commit everywhere instead of consensus?" Hint: draw the timeline where the coordinator dies at its worst possible moment, and ask what each participant is allowed to do next.

Logical Clocks and Ordering

Theory

Concurrency on one machine is ordered by a shared clock and shared memory: if A wrote a variable before B read it, hardware and the memory model tell you so. Across machines, neither exists. Two events on two nodes have no inherent order at all, and physical clocks cannot supply one.

Why not? Quartz oscillators drift — a typical server clock drifts by tens of microseconds per second, which is seconds per day. NTP corrects this to roughly 1 ms on a LAN and 10-100 ms over the internet, and it corrects by stepping or slewing the clock, meaning wall-clock time can jump backwards. A leap second can make the same second occur twice. So if (ts_a < ts_b) across two machines is not a reliable ordering, and using wall-clock timestamps as version numbers (the "last write wins" of many early distributed stores) silently loses data when a clock is 200 ms fast.

Lamport's insight in 1978 was that most of the time you do not need when; you need whether one thing could have caused another. Define the happened-before relation, written a -> b:

1. If a and b are in the same process and a comes first, then a -> b.
2. If a is the send of a message and b is its receipt, then a -> b.
3. Transitivity: if a -> b and b -> c then a -> c.

If neither a -> b nor b -> a, the events are concurrent (a || b) — not "simultaneous", but causally independent: neither could have influenced the other, so the system is free to order them however it likes. This is a partial order, and it is exactly what causality means when there is no clock.

A Lamport clock implements it with one integer per process:

• Increment your counter before every local event.
• Send the counter with every message.
• On receipt, set counter = max(local, received) + 1.

This guarantees a -> b ⟹ L(a) < L(b). But the converse fails: L(a) < L(b) does not imply a -> b, because concurrent events also get ordered numbers. Lamport clocks give you a consistent total order (break ties with node ID) but cannot detect concurrency — which is precisely what you need to detect conflicting writes.

Vector clocks fix that. Each process keeps a vector of counters, one entry per process:

• Increment your own entry on a local event.
• Send the whole vector.
• On receipt, take the element-wise max, then increment your own entry.

Now V(a) < V(b) (every element ≤, at least one strictly <) if and only if a -> b. If neither vector dominates, the events are genuinely concurrent — a conflict that the application must resolve (Dynamo and Riak surface exactly this as sibling versions). The cost is size: the vector grows with the number of nodes, which is why systems with churn use version vectors keyed by replica rather than client, or dotted version vectors to prune.

Finally, the pragmatic hybrid. Physical time is useful (humans and debuggers want it, and it bounds staleness), causality is correct. Hybrid logical clocks (HLC) combine them: a timestamp is (physical, logical), where the physical part tracks NTP time and the logical part increments when messages arrive with a timestamp from the same or a future physical instant. HLCs are close to wall time, monotonic, and respect causality — and they are what CockroachDB and MongoDB use. Google's TrueTime takes the opposite approach: give every datacentre GPS and atomic clocks, expose time as an interval [earliest, latest] with a bounded error (typically under 7 ms), and have Spanner simply wait out the uncertainty before committing, buying externally consistent global transactions at the cost of a few milliseconds per commit and specialised hardware.

Example

   HAPPENED-BEFORE: THREE PROCESSES, TWO MESSAGES

   P1 ---a------------b-------------------- ...
          \            \
           m1           \
            \            \
   P2 -------c---d-------\--------------- ...
                  \       \
                   m2      \
                    \       \
   P3 ---------------e-------f----------- ...

   a -> c   (message m1)
   c -> d   (same process)
   d -> e   (message m2)
   => a -> e by transitivity

   b || e   ?  b is after a on P1; e is after d on P3. No message path
               connects them => CONCURRENT. Neither caused the other.
               The system may order them either way.


   LAMPORT CLOCKS: correct one way only

   P1:  a(1) ----m1----> P2
   P2:  c(max(0,1)+1 = 2)  d(3) ----m2----> P3
   P3:  e(max(0,3)+1 = 4)

   L(a)=1 < L(e)=4  and indeed a -> e.        GOOD
   P1 continues:    b(2)
   L(b)=2 < L(e)=4  but b || e -- NOT causal.  <-- the false implication

   Lamport:  a -> b  IMPLIES  L(a) < L(b)
             L(a) < L(b) does NOT imply a -> b
   Use for: a consistent total order (tie-break on node id).
   Cannot:  detect conflicts.


   VECTOR CLOCKS: an if-and-only-if

   Vectors are [P1, P2, P3].

   P1: a [1,0,0] ---m1---> 
   P2:            c [1,1,0]   d [1,2,0] ---m2--->
   P3:                                    e [1,2,1]
   P1: b [2,0,0]

   a -> e ?  [1,0,0] <= [1,2,1] elementwise, and strictly < somewhere
             => YES, a happened-before e.
   b vs e ?  b=[2,0,0]  e=[1,2,1]
             b[0]=2 > e[0]=1   AND   b[1]=0 < e[1]=2
             neither dominates  =>  CONCURRENT. A genuine conflict.

   This is what a Dynamo-style store reports as "siblings":
   two values, neither newer, application must merge.


   WHY WALL CLOCKS LOSE DATA ("last write wins")

   client A (clock +200 ms fast)   client B (clock correct)
   t_real=10.000  write X=1        
                  stamps 10.200
   t_real=10.100                   write X=2
                                   stamps 10.100

   Store keeps the HIGHEST timestamp => X=1 wins.
   But B wrote LATER in real time. B's write is silently lost,
   with no error, no conflict, no trace. Clock skew ate it.

# Lamport and vector clocks side by side, with the crucial comparison.

# ---------------- Lamport clock --------------------------------------
class LamportClock:
    def __init__(self):
        self.t = 0

    def local_event(self):
        self.t += 1
        return self.t

    def send(self):
        self.t += 1
        return self.t                       # piggyback on the message

    def receive(self, ts):
        self.t = max(self.t, ts) + 1        # the whole algorithm
        return self.t

def lamport_total_order(e1, e2):
    """Tie-break on node id to get a TOTAL order from a partial one.
    Consistent (never contradicts causality) but arbitrary for
    concurrent events."""
    return (e1.ts, e1.node) < (e2.ts, e2.node)

# ---------------- Vector clock ---------------------------------------
class VectorClock:
    def __init__(self, node_id, nodes):
        self.id = node_id
        self.v = {n: 0 for n in nodes}

    def local_event(self):
        self.v[self.id] += 1
        return dict(self.v)

    def send(self):
        self.v[self.id] += 1
        return dict(self.v)                 # send the ENTIRE vector

    def receive(self, other):
        for n, t in other.items():          # element-wise max ...
            self.v[n] = max(self.v.get(n, 0), t)
        self.v[self.id] += 1                # ... then count the receipt
        return dict(self.v)

def compare(a, b):
    """Returns 'before', 'after', 'equal', or 'concurrent'.
    Only vector clocks can return 'concurrent' correctly."""
    keys = set(a) | set(b)
    le = all(a.get(k, 0) <= b.get(k, 0) for k in keys)   # a <= b
    ge = all(a.get(k, 0) >= b.get(k, 0) for k in keys)   # a >= b
    if le and ge:   return "equal"
    if le:          return "before"          # a -> b
    if ge:          return "after"           # b -> a
    return "concurrent"                      # CONFLICT: app must merge

# --- Demonstrating the difference ------------------------------------
a = {"P1": 2, "P2": 0, "P3": 0}              # event b in the diagram
e = {"P1": 1, "P2": 2, "P3": 1}              # event e in the diagram
print(compare(a, e))                         # 'concurrent'  <- correct
# Lamport would have said 2 < 4, implying an order that does not exist.

# Hybrid logical clock: physical time that never violates causality.

import time

class HybridLogicalClock:
    def __init__(self):
        self.wall = 0          # last physical time used (ms)
        self.logical = 0       # counter for same-millisecond events

    def now(self):
        return int(time.time() * 1000)

    def send_or_local(self):
        pt = self.now()
        if pt > self.wall:
            self.wall, self.logical = pt, 0      # clock advanced normally
        else:
            self.logical += 1                    # clock stalled/went back:
                                                 # stay monotonic anyway
        return (self.wall, self.logical)

    def receive(self, msg_wall, msg_logical):
        pt = self.now()
        # Take the max of: our clock, their clock, and physical time.
        new_wall = max(self.wall, msg_wall, pt)
        if new_wall == self.wall == msg_wall:
            self.logical = max(self.logical, msg_logical) + 1
        elif new_wall == self.wall:
            self.logical += 1
        elif new_wall == msg_wall:
            self.logical = msg_logical + 1
        else:
            self.logical = 0                     # physical time dominates
        self.wall = new_wall
        return (self.wall, self.logical)

# Result: timestamps are within NTP error of real time (so they are
# human-meaningful and bound staleness), strictly monotonic, and
# guarantee a -> b implies HLC(a) < HLC(b). Used by CockroachDB, MongoDB.

Key takeaways

• Physical clocks drift and can be stepped backwards, so cross-machine wall-clock comparison is not a valid ordering and "last write wins" silently loses data under skew.
• Happened-before (->) is the partial order defined by program order plus message send/receive plus transitivity; events unrelated by it are concurrent, meaning causally independent.
• A Lamport clock is one counter updated as max(local, received) + 1; it guarantees a -> b ⟹ L(a) < L(b) but not the converse, so it cannot detect concurrency.
• Lamport timestamps plus a node-ID tie-break give a consistent total order, which is enough for many algorithms that merely need everyone to agree on some order.
• Vector clocks keep one counter per node and give an if-and-only-if test for causality, so they can report genuine conflicts — the "siblings" of Dynamo-style stores.
• Vector clocks cost space proportional to the number of participants, which is why version vectors are keyed by replica rather than client.
• Hybrid logical clocks combine NTP time with a logical counter to get timestamps that are near wall time, monotonic, and causally correct.
• TrueTime exposes time as a bounded interval and has Spanner wait out the uncertainty, converting a clock problem into a latency cost.

🧪 Practice

1. Draw three processes exchanging four messages of your choosing and annotate every event with both its Lamport and its vector timestamp. Identify one pair of concurrent events and show that the Lamport timestamps mislead while the vectors do not.
2. Implement compare() above and use it to write a merge(v1, v2) that returns both values when they are concurrent and the newer one otherwise.
3. Explain why a vector clock entry for a departed node cannot simply be deleted, and describe one pruning scheme that is safe.
4. Interview-style: "Two replicas disagree about the value of a key. How do you decide which is correct?" Hint: first ask whether the question is even well-posed — under what ordering is one of them 'later'?

Distributed Mutual Exclusion

Theory

Chapter 5 solved mutual exclusion with an atomic instruction on a shared memory word. Across machines there is no such word, so the lock must be built out of messages — and every message can be delayed, lost, or arrive after the sender has died. This topic is where the theoretical algorithms and the operationally correct answer diverge sharply, and both are worth knowing.

The three classical algorithms:

Centralised. One node is the coordinator and holds a queue. To enter the critical section you send REQUEST and wait for GRANT; to leave you send RELEASE. Three messages per entry, easy to reason about, trivially supports FIFO fairness. The coordinator is a bottleneck and a single point of failure — and crucially, if it dies while holding requests, its queue dies with it.

Distributed (Ricart-Agrawala). Uses Lamport clocks. To enter, multicast REQUEST(ts, id) to all n-1 peers and wait for REPLY from every one. A peer replies immediately unless it is in the critical section or wants it with a smaller timestamp, in which case it defers the reply until it exits. Timestamp order gives a total order, so exactly one node can be first. Cost is 2(n-1) messages per entry, and — this is the fatal property — it requires every node to reply, so a single crashed node blocks everyone forever unless a failure detector is bolted on.

Token ring. A token circulates; holding it grants the critical section. One message per entry under saturation, but the token can be lost (requiring regeneration, which risks two tokens) and a node can wait a full ring traversal even when nobody else wants the lock.

Algorithm	Messages/entry	Latency to enter	Failure of one node	Fairness
Centralised	3	2 hops	Coordinator fatal; peers harmless	FIFO, easy
Ricart-Agrawala	2(n − 1)	2 hops	Any node fatal	Timestamp order
Maekawa (quorum)	~3√n	2 hops	Tolerates some	Needs deadlock handling
Token ring	1 to ∞	0 to n hops	Token loss fatal	Ring order

Now the operationally important part, which textbooks often omit. A distributed lock is not a mutex; it is a lease, and a lease can expire while its holder still believes it is held. Consider: a client acquires a 10-second lock, then suffers a 15-second stop-the-world GC pause. The lock expires; another client acquires it and starts writing. The first client wakes up with no idea anything happened and also writes. Two writers, corruption, and no algorithm above prevents it — the failure is outside the locking protocol.

The fix is a fencing token: the lock service returns a monotonically increasing number with every grant, the client passes it to the protected resource on every operation, and the resource rejects any token lower than the highest it has seen. Now the stale writer's request is refused at the point where it would do damage. This requires the resource to participate, which is why "we added a distributed lock" is rarely sufficient on its own.

In practice you do not implement any of the classical algorithms. You use a coordination service — ZooKeeper, etcd, or Consul — which implements a consensus-replicated centralised coordinator: the simplicity of the centralised algorithm, without its single point of failure. The idiom is an ephemeral sequential node (ZooKeeper) or a lease-bound key with a compare-and-swap (etcd); the node's sequence number or the key's revision is your fencing token. And the most valuable design move remains avoiding the lock entirely: partition the data so each key has exactly one owner, or use an idempotent operation, or use a compare-and-swap on the resource itself.

Example

   RICART-AGRAWALA: EVERY PEER MUST AGREE

   Three nodes. P1 requests at ts=4, P3 requests at ts=6.

   P1 --REQUEST(4,P1)--> P2, P3
   P3 --REQUEST(6,P3)--> P1, P2

   P2: not interested          -> REPLY to both
   P1: wants it, ts 4 < 6      -> DEFER reply to P3
   P3: wants it, ts 6 > 4      -> REPLY to P1 immediately

   P1 has replies from P2 and P3  => ENTERS
   P3 waits (missing P1's reply)
   P1 exits -> sends deferred REPLY to P3 => P3 ENTERS

   Correct, fully symmetric, no coordinator.
   Now crash P2 while P1 is waiting:
      P1 waits for a REPLY that will never come.  DEADLOCK.
      2(n-1) messages also means it scales badly.
   This is why it is taught, not deployed.


   THE FAILURE NO LOCK ALGORITHM PREVENTS

   time --->
   client1: acquire(lock, ttl=10s)
            [====== GC PAUSE, 15 s ======]
                                          write(x) <-- believes it holds
   lock:    |---- held by c1 ----|expired|
   client2:                      acquire()  write(x)

   Both clients write. The lock service did NOTHING wrong: c1's lease
   really did expire. c1 simply could not be told, because it was frozen.

   No consensus algorithm fixes this. The lock is not the problem.


   FENCING TOKENS: MAKE THE RESOURCE THE ENFORCER

   lock service issues a MONOTONIC token with each grant:

   client1: acquire -> token 33
            [GC pause]
   client2: acquire -> token 34
            write(x, token=34)   storage: 34 >= 34, ACCEPT, high=34
   client1: write(x, token=33)   storage: 33 <  34, REJECT
                                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^
                                 the stale writer is stopped HERE,
                                 at the only place that can stop it.

   Requirement: the RESOURCE must check the token. A lock alone
   cannot give you safety; the write path has to participate.

# Ricart-Agrawala, complete enough to see the deferral logic.

import threading

class RicartAgrawala:
    def __init__(self, node_id, peers, net):
        self.id, self.peers, self.net = node_id, peers, net
        self.clock = 0
        self.requesting = False
        self.my_ts = None
        self.deferred = []                  # peers whose REPLY we withheld
        self.replies = 0
        self.cv = threading.Condition()

    def acquire(self):
        with self.cv:
            self.clock += 1
            self.my_ts = self.clock
            self.requesting = True
            self.replies = 0
        for p in self.peers:
            self.net.send(p, ("REQUEST", self.my_ts, self.id))
        with self.cv:
            # Must hear from EVERY peer. One dead peer = wait forever.
            while self.replies < len(self.peers):
                self.cv.wait()

    def on_request(self, ts, sender):
        with self.cv:
            self.clock = max(self.clock, ts) + 1     # Lamport update
            # Defer only if we are ahead in the total order:
            # smaller timestamp wins; equal timestamps break on node id.
            ahead = self.requesting and (self.my_ts, self.id) < (ts, sender)
            if ahead or self.in_cs:
                self.deferred.append(sender)
                return
        self.net.send(sender, ("REPLY", self.id))

    def on_reply(self, _sender):
        with self.cv:
            self.replies += 1
            self.cv.notify_all()

    def release(self):
        with self.cv:
            self.requesting, self.in_cs = False, False
            pending, self.deferred = self.deferred, []
        for p in pending:                   # release the queued waiters
            self.net.send(p, ("REPLY", self.id))

# What you actually deploy: a lease-based lock with a fencing token.

import etcd3            # pip install etcd3

def with_distributed_lock(client, name, ttl=10):
    lease = client.lease(ttl)                    # auto-expires if we die
    lock = client.lock(name, ttl=ttl)
    if not lock.acquire(timeout=5):
        raise TimeoutError("lock busy")
    # etcd's mod_revision is monotonic across the whole cluster:
    # it is a ready-made fencing token.
    token = lock.uuid                            # plus key revision
    return lock, lease, token

def protected_write(storage, key, value, token):
    """The RESOURCE enforces the fence. Without this function,
    the lock above still permits two concurrent writers."""
    if token <= storage.highest_token_seen(key):
        raise StaleLockError(                    # the stale writer dies
            f"token {token} <= {storage.highest_token_seen(key)}")
    storage.record_token(key, token)
    storage.put(key, value)

# ZooKeeper's ephemeral-sequential idiom, and etcd's lease idiom.

# --- ZooKeeper: create an ephemeral sequential node under /lock ---
#   /lock/n-0000000017   <- yours; the SEQUENCE NUMBER is your fence
#   You hold the lock iff yours is the LOWEST child.
#   Watch only the node immediately below you (avoids the herd effect).
#   "Ephemeral" means the node vanishes when your session expires --
#   the lease, provided by the service.

# --- etcd: lease + compare-and-swap ---
etcdctl lease grant 10                   # -> lease 694d7d...  ttl 10
etcdctl put /locks/job "owner-A" --lease=694d7d
etcdctl lease keep-alive 694d7d          # renew; stop renewing => expiry
etcdctl get /locks/job -w=json | jq .kvs[0].mod_revision
#   mod_revision is cluster-wide monotonic -> use it as the fencing token

# --- Observe the hazard yourself ---
#   1. take a lock with ttl=5
#   2. SIGSTOP the process for 10 s   (kill -STOP <pid>)
#   3. watch another process take the lock
#   4. SIGCONT the first and watch it write as if nothing happened

Key takeaways

• Distributed mutual exclusion replaces an atomic memory word with messages, so every algorithm inherits message loss, delay, and node failure.
• The centralised algorithm costs three messages per entry and is easy to reason about, but the coordinator is a bottleneck and a single point of failure.
• Ricart-Agrawala is fully symmetric and orders entries by Lamport timestamp, but requires a reply from every peer, so a single crashed node blocks the system.
• Token-ring schemes cost one message under saturation but suffer token loss and unbounded entry latency at low load.
• A distributed lock is a lease, and a lease can expire while the holder is paused and unaware, producing two simultaneous writers no locking algorithm can prevent.
• Fencing tokens fix this by making the protected resource reject any operation carrying a token lower than the highest it has seen.
• In production, use a consensus-backed coordination service (ZooKeeper, etcd, Consul) whose sequence number or revision serves as the fencing token.
• The cheapest correct answer is usually to avoid the lock: partition so each key has one owner, make the operation idempotent, or compare-and-swap on the resource itself.

🧪 Practice

1. Compute the messages per critical-section entry for the centralised, Ricart-Agrawala, and token-ring algorithms with n = 4, 16, and 64 nodes, and say which becomes untenable first.
2. Modify the RicartAgrawala class so that a peer that has not replied within a timeout is treated as absent. Then describe precisely what correctness guarantee you have just given up.
3. Reproduce the stale-holder hazard: take a lock with a 5-second TTL, SIGSTOP the holder for 10 seconds, acquire the lock elsewhere, then SIGCONT the first process and observe the double write. Add a fencing token and show the second write is rejected.
4. Interview-style: "We use Redis for distributed locking and everything works in testing. What would you check before trusting it in production?" Hint: ask what happens between the moment the lease expires and the moment the holder finds out — and who, if anyone, is checking at the write path.

Consensus and Fault Tolerance

Theory

Every problem so far reduces to one: get a group of unreliable machines to agree on a single value. Who is the leader? Did the transaction commit? What is the next entry in the log? Solve agreement once and the rest follows.

Formally, a consensus protocol must satisfy:

• Agreement — no two correct nodes decide different values.
• Validity — the decided value was proposed by some node (nothing invented).
• Termination — every correct node eventually decides.

The FLP impossibility result (Fischer, Lynch, Paterson, 1985) proves that in a fully asynchronous system, with even one possible crash failure, no deterministic algorithm satisfies all three. The reason is the familiar one: you cannot distinguish a crashed node from a slow one, so any algorithm can be forced to wait forever. Every practical system responds the same way — keep agreement and validity absolutely, sacrifice guaranteed termination. Raft and Paxos are always safe and eventually terminate once the network behaves. This is why they have randomised election timeouts: not to be correct, but to break the symmetry that stalls them.

The mechanism underneath is the quorum. With 2f + 1 nodes, any two majorities share at least one node, so a value that a majority accepted cannot be contradicted by another majority — the shared node remembers. This is why cluster sizes are odd: 3 tolerates 1 failure, 5 tolerates 2, and 4 tolerates only 1 while needing one more machine and one more round-trip. Adding an even node buys nothing.

Paxos (1989) is the canonical algorithm: a proposer picks a ballot number, asks a majority to promise not to accept lower ballots (returning any value they already accepted), then asks that majority to accept its value — using any previously accepted value if one came back. It is correct and famously hard to build systems from, because it decides one value and the extension to a log (Multi-Paxos) is under-specified.

Raft (2014) was designed for understandability and is what modern systems implement. It decomposes consensus into three pieces:

1. Leader election. Time is divided into numbered terms. Each node is Follower, Candidate, or Leader. A follower that hears no heartbeat within a randomised timeout (150-300 ms) becomes a candidate, increments the term, and requests votes. A node grants at most one vote per term, so at most one candidate can win a majority — hence at most one leader per term.
2. Log replication. All client writes go to the leader, which appends to its log and sends AppendEntries to followers. Once a majority has persisted the entry, it is committed, applied to the state machine, and acknowledged.
3. Safety. A candidate only wins if its log is at least as up to date as the voter's, guaranteeing a new leader already holds every committed entry.

This yields a replicated state machine: identical deterministic state machines fed an identical, identically ordered log produce identical state. Determinism is a real requirement — a state machine that calls random() or time() diverges across replicas.

Two more pieces complete the picture. Byzantine fault tolerance handles nodes that lie rather than merely stop; it needs 3f + 1 nodes and far more messages (PBFT is O(n²) per decision), and it is used where participants are mutually untrusting — blockchains, some avionics. And CAP: when the network partitions, a system must choose between remaining consistent (refuse to serve the minority side; etcd, ZooKeeper, Spanner) and remaining available (serve possibly stale data everywhere and reconcile later; Dynamo, Cassandra). CAP is often overstated — it says nothing about the far more common non-partitioned case, where the real trade-off is the PACELC extension: else, absent a partition, choose between latency and consistency.

Example

   WHY MAJORITIES: TWO QUORUMS ALWAYS OVERLAP

   5 nodes: A B C D E.   Majority = 3.

   quorum 1 = {A,B,C}          quorum 2 = {C,D,E}
                  \                /
                   +--- C is in BOTH ---+

   C remembers what quorum 1 decided, so quorum 2 cannot decide
   something different without C contradicting itself.
   This single fact is the whole reason consensus works.

   nodes  majority  tolerates  note
     3       2          1
     4       3          1      +1 machine, NO extra tolerance
     5       3          2
     6       4          2      +1 machine, NO extra tolerance
     7       4          3
   => always odd.


   RAFT STATE MACHINE

                 times out,          receives majority
                 starts election         of votes
       +----------+ ------------> +-----------+ ------> +--------+
       | FOLLOWER |               | CANDIDATE |         | LEADER |
       +----------+ <------------ +-----------+ <------ +--------+
             ^   discovers current      |   discovers node with
             |   leader or higher term  |   HIGHER TERM
             +--------------------------+

   Randomised timeout (150-300 ms) breaks symmetry so two candidates
   rarely split the vote twice. This is FLP being dodged, not solved:
   safety always holds, liveness is probabilistic.


   LOG REPLICATION AND THE COMMIT POINT

   5 nodes, majority = 3.

   index     1     2     3     4
   leader  [x=1][y=2][x=7][z=9]      <- 4 entries appended
   f1      [x=1][y=2][x=7]
   f2      [x=1][y=2][x=7]
   f3      [x=1][y=2]
   f4      [x=1]
            ^^^^ ^^^^ ^^^^  ^^^^
            5/5  4/5  3/5   1/5
            COMMIT  COMMIT  COMMIT   NOT COMMITTED
                            ^
                            commitIndex = 3: a majority has it durably,
                            so NO future leader can lack it.
   Entry 4 exists only on the leader. If the leader dies now, entry 4
   may vanish -- which is exactly why the client was not acked yet.


   THE SPLIT-BRAIN THAT DOES NOT HAPPEN

   Partition: {A,B} | {C,D,E}         (A was leader, term 7)

   A's side: 2 nodes. Cannot reach 3. A CANNOT commit anything.
             It may still THINK it is leader until its next heartbeat
             round fails -- so reads from A can be stale (hence
             leader leases / ReadIndex for linearizable reads).
   C's side: 3 nodes. Elects a leader in term 8. Commits normally.

   Heal: A sees term 8 > 7, steps down, truncates any uncommitted
         entries, and follows. No divergence, ever.


   CAP DURING THAT PARTITION

   CP  (etcd, ZooKeeper, Spanner, HBase)
       minority side returns ERROR. Correct, unavailable.
   AP  (Cassandra, Dynamo, Riak)
       both sides accept writes. Available, must reconcile later
       (vector clocks / CRDTs / last-write-wins).

   There is no third option. The network decided for you.

# The core of Raft: vote granting and log commitment.
# Simplified, but the safety-critical predicates are exact.

from dataclasses import dataclass, field

@dataclass
class LogEntry:
    term: int
    command: str

@dataclass
class RaftNode:
    id: int
    peers: list
    # --- persistent state: MUST survive a crash, fsync before replying ---
    current_term: int = 0
    voted_for: int = None
    log: list = field(default_factory=list)
    # --- volatile state ---
    commit_index: int = 0
    state: str = "FOLLOWER"
    match_index: dict = field(default_factory=dict)  # leader only

    # ---------------- RequestVote RPC handler -------------------------
    def request_vote(self, term, candidate_id, last_log_index, last_log_term):
        if term < self.current_term:
            return (self.current_term, False)        # stale candidate
        if term > self.current_term:
            self.current_term, self.voted_for = term, None
            self.state = "FOLLOWER"                  # always step down

        # At most ONE vote per term -> at most one leader per term.
        already_voted = self.voted_for not in (None, candidate_id)
        if already_voted:
            return (self.current_term, False)

        # THE SAFETY PREDICATE: only vote for a log at least as
        # up to date as ours. This is what guarantees a new leader
        # already holds every committed entry.
        my_last_term  = self.log[-1].term if self.log else 0
        my_last_index = len(self.log)
        up_to_date = (last_log_term > my_last_term) or \
                     (last_log_term == my_last_term and
                      last_log_index >= my_last_index)
        if not up_to_date:
            return (self.current_term, False)

        self.voted_for = candidate_id
        self.persist()                               # fsync BEFORE replying
        return (self.current_term, True)

    # ---------------- Leader: advance the commit index ----------------
    def advance_commit_index(self):
        """An entry is committed once a MAJORITY has it durably --
        and only if it is from the current term (the subtle Raft rule
        that prevents committing an old entry by counting replicas)."""
        for n in range(len(self.log), self.commit_index, -1):
            replicas = 1 + sum(1 for p in self.peers
                               if self.match_index.get(p, 0) >= n)
            majority = (len(self.peers) + 1) // 2 + 1
            if replicas >= majority and self.log[n - 1].term == self.current_term:
                self.commit_index = n
                self.apply_committed()               # feed the state machine
                return

# Watching real consensus. etcd is Raft with a CLI.

etcd --name n1 --initial-cluster n1=http://10.0.0.1:2380,\
n2=http://10.0.0.2:2380,n3=http://10.0.0.3:2380 ...

etcdctl endpoint status --cluster -w table
# +----------------+----------+---------+-----------+--------+-------+
# |    ENDPOINT    |    ID    | VERSION | IS LEADER | TERM   | INDEX |
# | 10.0.0.1:2379  | 8e9e05.. |  3.5.9  |   true    |   17   | 84213 |
# | 10.0.0.2:2379  | 91bc3c.. |  3.5.9  |   false   |   17   | 84213 |
# | 10.0.0.3:2379  | fd422d.. |  3.5.9  |   false   |   17   | 84211 |
#                                                     ^      ^
#                          everyone agrees on the term |      followers
#                                                             lag slightly

etcdctl endpoint health --cluster
etcdctl move-leader 91bc3c...        # graceful handover before maintenance

# --- Demonstrate CP behaviour: kill a majority ---
# 3-node cluster, stop 2 nodes:
etcdctl put foo bar
#   Error: context deadline exceeded
#   The survivor REFUSES to serve rather than risk divergence.
#   An AP store (Cassandra) would have accepted the write.

# --- Why odd numbers ---
etcdctl member list          # 3 members: survives 1 loss
                             # 4 members: STILL survives only 1 loss,
                             #   and every write needs 3 acks instead of 2

Key takeaways

• Consensus requires agreement, validity, and termination; FLP proves all three are impossible in an asynchronous system with one crash, so real systems keep safety and relax guaranteed termination.
• Quorums work because any two majorities of 2f + 1 nodes share a node, which cannot contradict itself — hence odd cluster sizes, since an even member adds cost without tolerance.
• Raft splits consensus into leader election, log replication, and safety, with randomised election timeouts to break symmetry.
• A node grants at most one vote per term, which is what makes two leaders in one term impossible.
• An entry is committed once a majority has persisted it; entries beyond the commit index may vanish on leader failure, which is why they are not acknowledged to the client.
• The vote-only-for-an-up-to-date-log rule guarantees every new leader already holds all committed entries, removing any need to recover them.
• A replicated state machine requires strict determinism — no clocks, no randomness, no iteration over unordered collections in the applied commands.
• Byzantine tolerance needs 3f + 1 nodes and quadratic messaging, and is warranted only among mutually untrusting participants.
• Under partition, CAP forces a choice between consistency (minority errors out) and availability (both sides accept and reconcile later); PACELC adds the latency-versus-consistency choice that applies the rest of the time.

🧪 Practice

1. For clusters of 3, 4, 5, 6, and 7 nodes, state the majority size and the number of failures tolerated, then explain in one sentence why even sizes are avoided.
2. Trace a Raft cluster of five nodes where the leader is partitioned away with one follower. State which side can commit, what happens to writes on the other side, and what occurs when the partition heals.
3. In the request_vote handler above, remove the "log at least as up to date" check and construct a sequence of events in which a committed entry is lost.
4. Run a three-node etcd cluster, kill two nodes, and attempt a write and a read. Explain the result in CAP terms.
5. Interview-style: "Our system uses a three-node Raft cluster and someone suggests adding a fourth node for extra safety. What do you say?" Hint: write down the majority size before and after, then the number of failures each configuration survives.

<a id="142-real-time-and-embedded-systems"></a>

14.2 Real-Time and Embedded Systems

Every scheduler so far optimised averages: average waiting time, throughput, fairness. A real-time system does not care about averages at all — it cares about the worst case, because a deadline missed once can be fatal. This section covers what "real-time" actually guarantees, where unpredictability comes from and how it is measured, how an RTOS is built differently as a result, and the physical constraints of the embedded hardware these systems usually run on.

Hard vs Soft Real-Time

Theory

The most common misconception in this subject is that real-time means fast. It does not. Real-time means predictable: a correct result delivered after its deadline is a wrong result. A system that responds in 1 ms on average but occasionally takes 100 ms is worse, for real-time purposes, than one that always takes exactly 8 ms.

The formal statement is that correctness has two components: the logical result (the right value) and the temporal result (delivered by the deadline). An airbag controller that computes a perfect deployment decision 300 ms after impact has failed as completely as one that computed the wrong decision.

Systems are classified by what happens when a deadline is missed:

Class	Value after deadline	Consequence of a miss	Examples
Hard	Negative (catastrophic)	System failure, possibly harm	Airbag, pacemaker, flight control, anti-lock brakes, industrial robot
Firm	Zero (useless but harmless)	Result discarded, quality drops	Video frame decode, a stale sensor reading, a market data tick
Soft	Degraded, decreasing	Quality of service suffers	Audio playback, streaming video, UI responsiveness, telephony

The useful way to picture this is a utility function over completion time: hard deadlines drop off a cliff into negative utility, firm deadlines drop to zero, soft deadlines decay gradually. The classification is a property of the consequence, not of the timescale — a hard deadline can be 10 minutes (a chemical reactor vent) and a soft one 5 ms (a game frame).

This changes what you have to know about your own code. A general-purpose OS asks "how fast is this typically?" A real-time system asks for the worst-case execution time (WCET): an upper bound that the code will never exceed, on this hardware, under any input. WCET is genuinely hard to obtain because modern hardware is built for good average behaviour: caches, branch predictors, out-of-order execution, DVFS, and DRAM refresh all make "how long does this take" depend on history. Analysis is either static (model the processor, sum the worst path — sound but pessimistic, often by 2-10x) or measurement-based (run many inputs and add a safety margin — tighter but not a proof). Hard real-time certification (DO-178C for avionics, IEC 61508, ISO 26262 for automotive) generally requires the static kind, which is a large part of why certified systems avoid caches, dynamic allocation, and recursion.

Given WCET values, schedulability analysis answers the actual question: will every task always meet its deadline? For n periodic tasks with execution time Cᵢ and period Tᵢ, utilisation is U = Σ Cᵢ/Tᵢ. Under rate-monotonic scheduling (fixed priorities, shorter period = higher priority) the Liu-Layland bound guarantees schedulability if U ≤ n(2^(1/n) − 1), which tends to ln 2 ≈ 0.693. Under earliest-deadline-first (dynamic priorities) any U ≤ 1 is schedulable. Both were covered in Chapter 4; what matters here is the mindset shift: a real-time engineer proves the schedule before running it, rather than measuring it afterwards and hoping.

Finally, why a general-purpose OS is unsuitable out of the box. Linux's CFS maximises throughput and fairness; it will happily delay your task to batch work efficiently. Page faults, demand paging, non-preemptible kernel sections, interrupt coalescing, and power management all trade worst case for average. None of that is a defect — it is the correct design for a laptop, and the wrong one for a servo loop.

Example

   UTILITY AS A FUNCTION OF COMPLETION TIME

   HARD                    FIRM                    SOFT
   utility                 utility                 utility
     |####                   |####                   |#####
     |####                   |####                   |  ####
     |####                   |####                   |     ####
   0 +----+--------->      0 +----+--------->      0 +--------####--->
     |    |deadline           |    deadline           |     deadline
     |    |                   |                       |
     |####v  NEGATIVE         (zero: discard)         (decays gracefully)
     |#### catastrophe

   airbag, pacemaker,      video frame,            audio buffer,
   flight control          stale sensor read       UI response

   Note: the CLASS is about consequence, not timescale.
   A 10-minute hard deadline and a 5 ms soft deadline both exist.


   "REAL-TIME" IS NOT "FAST"

   System A: mean 1.0 ms, p99 1.2 ms, max 100 ms
   System B: mean 8.0 ms, p99 8.1 ms, max  8.3 ms

   For a web server:     A is far better (8x lower typical latency).
   For a motor control
   loop with a 10 ms
   deadline:             A FAILS. B is the only correct choice.

   Real-time engineering optimises the RIGHT TAIL, and will
   happily sacrifice the mean to shrink the maximum.


   WHY WCET IS HARD: THE SAME CODE, DIFFERENT TIME

   for (i = 0; i < 256; i++) sum += table[i];

   cold cache, DRAM refresh collision : 12,400 cycles
   warm cache, predictable stride     :    290 cycles
                                         ^^^^^^^^^^^
   A 40x spread from hardware state alone. WCET analysis must
   assume the 12,400 -- which is why certified systems often
   DISABLE the cache: 3x slower, but 40x more predictable.


   SCHEDULABILITY, DECIDED BEFORE THE SYSTEM RUNS

   Task   C (ms)   T (ms)   U = C/T
   ---------------------------------
   sense     1       5       0.200
   control   2      10       0.200
   log       5      50       0.100
                           U = 0.500

   RMS bound for n=3: 3*(2^(1/3) - 1) = 0.780
   0.500 <= 0.780  =>  GUARANTEED schedulable under RMS.
   EDF bound: U <= 1.0   =>  also schedulable, with headroom.

   This is a PROOF, computed before deployment -- not a benchmark.

/* The structural difference between a general-purpose task and a
 * hard real-time task, in the same language on the same machine. */

/* ---------- General-purpose: optimised for the common case -------- */
void process_sensor_gp(void)
{
    char *buf = malloc(4096);          /* unbounded: may fault, may fail,
                                        * allocator may take a long path */
    read_config_file("/etc/cfg");      /* disk I/O: milliseconds, or more */
    for (int i = 0; i < n; i++) {      /* n depends on input: no bound  */
        if (unlikely_case(i))
            recurse(i);                /* recursion: unbounded stack    */
    }
    free(buf);
}

/* ---------- Hard real-time: every path bounded by construction ----- */
#define MAX_SAMPLES 256                /* a compile-time bound          */
static uint16_t buf[MAX_SAMPLES];      /* STATIC: no allocator at all   */

void process_sensor_rt(void)
{
    /* Loop count is a constant, so the worst path is countable.      */
    for (int i = 0; i < MAX_SAMPLES; i++) {
        buf[i] = adc_read();           /* fixed-cycle hardware read    */
    }
    /* No recursion, no dynamic allocation, no I/O to a device whose
     * response time is not specified, no unbounded loops. Every one
     * of those restrictions exists to make WCET COMPUTABLE.          */
}

/* ---------- Deadline enforcement: detect a miss, do not hope ------- */
typedef struct {
    uint32_t period_us;
    uint32_t wcet_us;
    uint32_t deadline_us;
    uint32_t misses;
} rt_task_t;

void run_periodic(rt_task_t *t, void (*body)(void))
{
    uint32_t next = now_us();
    for (;;) {
        uint32_t start = now_us();
        body();
        uint32_t elapsed = now_us() - start;

        if (elapsed > t->deadline_us) {
            t->misses++;
            /* A hard system does NOT just log this. Depending on the
             * safety case it degrades to a safe mode, switches to a
             * redundant channel, or resets via the watchdog. Silently
             * continuing is how a deadline miss becomes an accident. */
            enter_safe_state();
        }
        next += t->period_us;
        sleep_until(next);             /* absolute deadline, NOT
                                        * sleep(period): relative sleeps
                                        * accumulate drift every cycle */
    }
}

# Why the distribution -- not the mean -- decides real-time suitability.

import statistics

gp_latencies = [1.0]*990 + [3.0]*9 + [100.0]      # occasional huge outlier
rt_latencies = [8.0]*500 + [8.1]*450 + [8.3]*50   # tight, boring, bounded

def report(name, xs, deadline):
    xs = sorted(xs)
    p = lambda q: xs[int(len(xs) * q)]
    misses = sum(1 for x in xs if x > deadline)
    print(f"{name}: mean={statistics.mean(xs):.2f} "
          f"p50={p(0.50):.1f} p99={p(0.99):.1f} max={xs[-1]:.1f} "
          f"misses={misses}")

report("general-purpose", gp_latencies, deadline=10.0)
report("real-time      ", rt_latencies, deadline=10.0)
# general-purpose: mean=1.11 p50=1.0 p99=3.0 max=100.0 misses=1
# real-time      : mean=8.05 p50=8.0 p99=8.3 max=8.3   misses=0
#
# The GP system is 7x faster on average and STILL fails: one miss in a
# thousand is 86 misses per day at 1 kHz. For an airbag, once is enough.

Key takeaways

• Real-time means predictable, not fast; a late correct answer is a wrong answer, and a system with a better mean but a worse maximum is worse for real-time use.
• Correctness has a logical component (the right value) and a temporal component (by the deadline), and both are required.
• Hard deadlines carry catastrophic cost when missed, firm deadlines make the result merely useless, and soft deadlines degrade quality gradually.
• The classification depends on the consequence of a miss, not on the length of the deadline.
• Worst-case execution time is the central quantity, and modern hardware features that improve average performance — caches, branch prediction, DVFS — make it harder to bound.
• Static WCET analysis is sound but pessimistic; measurement-based analysis is tighter but is not a proof, and certification standards generally demand the former.
• Schedulability is proven in advance from WCET and periods (RMS bound n(2^(1/n) − 1), EDF bound 1.0), rather than discovered by benchmarking.
• General-purpose kernels deliberately trade worst-case latency for throughput and fairness, which is correct for a laptop and disqualifying for a servo loop.
• A missed hard deadline must trigger a defined response — safe state, redundant channel, or watchdog reset — never a log line and a continuation.

🧪 Practice

1. Classify each as hard, firm, or soft, and justify: an ABS brake controller, a video conferencing codec, a stock exchange matching engine, a pacemaker, an industrial oven temperature loop, a smartphone touch response.
2. Three periodic tasks have (C, T) of (2, 10), (3, 15), and (4, 40) ms. Compute the utilisation and decide whether the set is schedulable under RMS, then under EDF.
3. Take a small function of your own and list every construct in it that prevents a bound on its execution time. Rewrite it so that a bound exists.
4. Interview-style: "Our service has a 1 ms median latency. Can we use it for real-time control?" Hint: ask what the maximum is, how it was measured, and over how long — then ask what happens on the single worst sample.

Latency and Jitter Requirements

Theory

If deadlines are the requirement, latency and jitter are the measurements. Two quantities matter.

Interrupt latency is the time from a hardware signal asserting to the first instruction of its handler executing. Dispatch latency is the time from the handler deciding a task should run to that task actually running. Their sum is the system's response time, and the real-time question is not what it usually is but what it can ever be.

Jitter is the variation in that response time. For a control loop, jitter is often worse than latency: a control algorithm can be tuned for a fixed 500 µs delay, but a delay wandering between 100 µs and 900 µs injects noise into the loop that no tuning removes. A stable 1 ms beats a variable 100-900 µs.

Dispatch latency decomposes into a conflict phase and a dispatch phase. The conflict phase is where the trouble lives — it is the time spent waiting for the kernel to reach a point where it is willing to preempt. Its contributors, roughly in order of nastiness:

Source	Why it delays you	Mitigation
Interrupts disabled	The CPU cannot even see the event	Minimise critical sections; measure with irqsoff tracer
Non-preemptible kernel code	A syscall by another process holds the CPU	PREEMPT_RT makes nearly all of it preemptible
Priority inversion	A low-priority task holds a lock your task needs	Priority inheritance or priority ceiling
Page faults	A page must be fetched from disk	mlockall() to pin all memory
Cache/TLB misses	Tens to hundreds of cycles, unpredictably	Cache partitioning, cache locking, or disable
DVFS / C-states	The CPU is in a deep sleep or at a low clock	cpu_dma_latency QoS, disable deep C-states
SMM / SMI (x86)	Firmware steals the CPU invisibly to the OS	Choose hardware without them; measure
CPU migration / IRQ storms	Cold caches, competing work	isolcpus, IRQ affinity, nohz_full

Priority inversion deserves its own paragraph because it is the classic real-time failure. A low-priority task L takes a mutex. A high-priority task H needs the same mutex and blocks. A medium-priority task M, which needs nothing, preempts L — so H now waits on M, indefinitely, despite outranking it. This is not theoretical: it is exactly what happened to the Mars Pathfinder rover in 1997, whose watchdog kept resetting the system until engineers remotely enabled priority inheritance on the offending mutex.

Two standard fixes. Priority inheritance: while L holds a lock that H wants, L temporarily runs at H's priority, so M cannot preempt it. Priority ceiling: every lock carries the priority of the highest task that can ever take it, and a task acquiring it is immediately raised, which also prevents deadlock but requires static analysis of who takes what.

On Linux, the practical route to low latency is PREEMPT_RT (merged into the mainline kernel in 6.12), which converts most spinlocks into sleeping mutexes with priority inheritance and moves interrupt handlers into schedulable kernel threads. It typically takes worst-case latency from the tens of milliseconds down to tens of microseconds — at a cost of roughly 5-20% throughput, since preemptibility means more context switches and more lock overhead. That trade is the entire point.

Measuring is non-negotiable, and the standard tool is cyclictest: it sleeps for a fixed period and reports how late it actually woke. The number that matters is Max, measured over hours or days under load, because a latency spike that appears once an hour will not show up in a 60-second idle run.

Example

   ANATOMY OF A RESPONSE, AND WHERE TIME IS LOST

   device asserts IRQ
        |
        |<-- INTERRUPT LATENCY -->|
        |   (a) interrupts currently disabled by some kernel path
        |   (b) CPU in a deep C-state, must wake            ~10-100 us
        |   (c) vector lookup, save context
        |                         |
        |                    ISR runs (should be SHORT)
        |                         |
        |                         |<---- DISPATCH LATENCY ---->|
        |                         |  CONFLICT PHASE:           |
        |                         |   - finish non-preemptible |
        |                         |     kernel section         |
        |                         |   - release held locks     |
        |                         |   - PRIORITY INVERSION     |
        |                         |  DISPATCH PHASE:           |
        |                         |   - context switch         |
        |                         |   - cache/TLB refill       |
        |                         |                            |
        |                                            RT TASK RUNS
        |<------------------ RESPONSE TIME ------------------->|

   The conflict phase is what separates a 30 ms worst case (stock
   kernel) from a 30 us worst case (PREEMPT_RT). Everything else is
   roughly the same.


   LATENCY vs JITTER: WHICH HURTS A CONTROL LOOP MORE

   System A: 100-900 us   (mean 500, jitter 800 us)
   System B: always 1000 us +/- 20 us

   A control loop can COMPENSATE for a known constant delay.
   It cannot compensate for an unknown varying one.
   => B is the better real-time system despite being 2x slower
      at its best and 10% slower at its worst.

   period    |<--1 ms-->|<--1 ms-->|<--1 ms-->|
   ideal     v          v          v          v
   jittery   . v      v .        v .    v     .   <- accumulating phase
             ^                                       noise in the loop


   PRIORITY INVERSION (the Mars Pathfinder bug)

   prio
   HIGH  H  ....[blocked on mutex M].............[runs]
   MED   M  ..........[RUNS - needs nothing].....|
   LOW   L  [takes M][preempted by M............][releases M]
            ^                                    ^
            holds the lock H needs               finally lets go

   H is delayed by M, which it outranks, for an UNBOUNDED time.
   Pathfinder's watchdog saw the missed deadline and reset the
   spacecraft -- repeatedly -- until priority inheritance was
   enabled remotely.

   WITH PRIORITY INHERITANCE:
   HIGH  H  ....[blocked]..[runs]
   MED   M  ...............[waits]
   LOW   L  [takes M][BOOSTED TO HIGH, finishes fast][release]
                     ^^^^^^^^^^^^^^^^ M cannot preempt it now.
   H's delay is now bounded by L's critical section length.

# ---------- Measure it. Never assume it. ----------

# cyclictest: the standard real-time latency benchmark.
# -m  lock memory   -p99 priority 99   -i200 200us interval
# -h400 histogram   -q quiet           -D1h  run for an hour
sudo cyclictest -m -p99 -i200 -h400 -q -D1h
#  T: 0 (12345) P:99 I:200 C: 18000000 Min: 2 Act: 3 Avg: 3 Max: 21
#                                            ^^^^^^          ^^^^^^
#                              typical case is irrelevant     THIS number
#
#  Stock kernel, idle:        Max ~  100 us
#  Stock kernel, under load:  Max ~ 5000-30000 us   <- unusable for RT
#  PREEMPT_RT, under load:    Max ~   20-80 us
#
# ALWAYS run under load; an idle box tells you nothing:
sudo cyclictest -m -p99 -i200 -D4h & stress-ng --cpu 8 --io 4 --vm 2 --hdd 2

# ---------- Find WHO caused a spike ----------
# ftrace: what was holding interrupts off?
echo irqsoff > /sys/kernel/tracing/current_tracer
echo 1       > /sys/kernel/tracing/tracing_on
cat /sys/kernel/tracing/trace                  # longest irqs-off path

echo preemptoff  > /sys/kernel/tracing/current_tracer   # non-preemptible
echo wakeup_rt   > /sys/kernel/tracing/current_tracer   # RT wakeup latency

# ---------- Configure a machine for low latency ----------
# 1. Isolate cores from the general scheduler and from ticks and RCU:
#    kernel cmdline:
#    isolcpus=2,3 nohz_full=2,3 rcu_nocbs=2,3 irqaffinity=0,1
# 2. Keep the CPU awake and at a fixed frequency:
cpupower idle-set -D 0                   # forbid deep C-states
cpupower frequency-set -g performance    # no DVFS ramping
# 3. Move interrupts off the RT cores:
echo 3 > /proc/irq/24/smp_affinity       # IRQ 24 -> cpus 0,1 only
# 4. Disable the RT throttle only if you are certain (a runaway RT task
#    can then lock the machine):
echo -1 > /proc/sys/kernel/sched_rt_runtime_us
# 5. Verify the kernel is actually RT:
uname -v | grep -i PREEMPT_RT

/* A correctly configured real-time thread on Linux. Every line here
 * removes one source of unbounded delay. */
#define _GNU_SOURCE
#include <pthread.h>
#include <sched.h>
#include <sys/mman.h>
#include <time.h>
#include <stdio.h>

#define NSEC_PER_SEC 1000000000L

static void *rt_loop(void *arg)
{
    struct timespec next;
    clock_gettime(CLOCK_MONOTONIC, &next);

    for (;;) {
        next.tv_nsec += 1000000;                 /* 1 ms period */
        if (next.tv_nsec >= NSEC_PER_SEC) {
            next.tv_nsec -= NSEC_PER_SEC; next.tv_sec++;
        }
        /* ABSOLUTE sleep: relative nanosleep() accumulates the
         * execution time of the body as drift, every single cycle. */
        clock_nanosleep(CLOCK_MONOTONIC, TIMER_ABSTIME, &next, NULL);

        control_step();                          /* bounded work only */
    }
    return NULL;
}

int main(void)
{
    /* 1. Pin ALL memory now and forbid future faults. A single page
     *    fault in the control loop is a multi-millisecond stall. */
    if (mlockall(MCL_CURRENT | MCL_FUTURE) != 0)
        perror("mlockall");

    /* 2. Pre-fault the stack: touch it now so it is never faulted in
     *    while the deadline is running. */
    unsigned char dummy[64 * 1024];
    memset(dummy, 0, sizeof dummy);

    pthread_attr_t attr;
    pthread_attr_init(&attr);
    pthread_attr_setinheritsched(&attr, PTHREAD_EXPLICIT_SCHED);
    /* 3. SCHED_FIFO: runs until it blocks or a higher priority preempts.
     *    NOT SCHED_OTHER, which is fair-share and therefore unbounded. */
    pthread_attr_setschedpolicy(&attr, SCHED_FIFO);
    struct sched_param p = { .sched_priority = 80 };  /* below IRQ threads */
    pthread_attr_setschedparam(&attr, &p);
    pthread_attr_setstacksize(&attr, 256 * 1024);     /* pre-sized stack */

    /* 4. Pin to an isolated core: no migration, warm caches. */
    cpu_set_t cpus; CPU_ZERO(&cpus); CPU_SET(2, &cpus);
    pthread_attr_setaffinity_np(&attr, sizeof cpus, &cpus);

    pthread_t t;
    pthread_create(&t, &attr, rt_loop, NULL);

    /* 5. Any mutex shared with a lower-priority thread MUST use
     *    priority inheritance, or you have rebuilt the Pathfinder bug. */
    pthread_mutexattr_t ma;
    pthread_mutexattr_init(&ma);
    pthread_mutexattr_setprotocol(&ma, PTHREAD_PRIO_INHERIT);
    pthread_mutex_t shared;
    pthread_mutex_init(&shared, &ma);

    pthread_join(t, NULL);
    return 0;
}

Key takeaways

• Interrupt latency is signal-to-handler, dispatch latency is decision-to-task-running, and their sum is the response time whose maximum — not average — defines the system.
• Jitter often matters more than absolute latency, because a control loop can compensate for a constant delay but not a varying one.
• The conflict phase of dispatch latency is where worst-case time accumulates: disabled interrupts, non-preemptible kernel sections, priority inversion, and page faults.
• Priority inversion lets a medium-priority task indefinitely delay a high-priority one through a lock held by a low-priority task; it grounded Mars Pathfinder.
• Priority inheritance bounds the delay to the low-priority task's critical section; priority ceiling raises the holder immediately and also prevents deadlock.
• PREEMPT_RT makes most kernel code preemptible and moves interrupt handlers into threads, cutting worst-case latency from milliseconds to tens of microseconds at a 5-20% throughput cost.
• mlockall(), pre-faulted stacks, SCHED_FIFO, CPU pinning, disabled deep C-states, and fixed frequencies each remove one specific unbounded delay.
• Periodic tasks must sleep to an absolute time, because relative sleeps accumulate the body's execution time as drift on every cycle.
• Latency must be measured with cyclictest under load for hours, since the meaningful number is a rare maximum, and ftrace's irqsoff, preemptoff, and wakeup_rt tracers attribute the spikes.

🧪 Practice

1. Run cyclictest -m -p99 -i200 -D60 -q on an idle machine, then again while running stress-ng --cpu 8 --io 4. Compare the Max values and explain the difference in terms of the conflict phase.
2. Draw the timeline of a priority inversion with three tasks and one mutex, then redraw it with priority inheritance enabled, marking where the high-priority task's delay is now bounded.
3. Take the rt_loop code above and remove mlockall(). Describe what specific event could now introduce a multi-millisecond delay and at what point in the loop.
4. Explain why clock_nanosleep(..., TIMER_ABSTIME, ...) is used rather than nanosleep() with a relative interval, and compute the drift after 10,000 cycles if the body takes 50 µs.
5. Interview-style: "We benchmarked our RT loop for 60 seconds and saw no deadline misses. Are we done?" Hint: at 1 kHz, how many iterations is that, and what event frequency would that test reliably miss?

RTOS Architectures

Theory

Given the requirements above, an RTOS is built on a different set of priorities from a general-purpose kernel. Every design decision answers the same question: does this make the worst case bounded? If not, it is left out, however useful it might be on a desktop.

The defining properties:

• Deterministic, documented API timing. Every kernel call has a published worst case, often in CPU cycles. xQueueSend taking O(1) is not an optimisation; it is part of the contract. A general-purpose kernel documents no such thing.
• Fully preemptible kernel. A higher-priority task becomes runnable and runs now, not at the next convenient point. This is the opposite of the batching that makes throughput-oriented kernels fast.
• Fixed, strict priorities. No fairness, no ageing, no heuristics. The highest-priority runnable task runs, period — even if that starves everything else, because starving a low-priority task is the correct outcome when a high-priority deadline is at stake.
• Priority inheritance mutexes as the default, for the reasons above.
• Bounded memory behaviour. Often no virtual memory at all, or an MPU for protection without paging. No demand paging means no page faults means no unbounded stalls.
• Small footprint. FreeRTOS's kernel is roughly 6-12 KB of code. It fits in a microcontroller's flash alongside the application.

Architecturally there are four common shapes:

Architecture	Structure	Typical latency	Trade-off	Examples
Library RTOS	Kernel links into the app; one address space	1-10 µs	Fast, tiny, no memory protection	FreeRTOS, Zephyr, ThreadX, RIOT
RT microkernel	Minimal kernel, drivers in user space	5-50 µs	Fault isolation; IPC cost	QNX Neutrino, INTEGRITY, PikeOS
Dual-kernel	RT kernel below a general-purpose one	1-20 µs	Hard RT plus Linux features; two APIs	Xenomai, RTAI, (historically RTLinux)
RT patched GPOS	One kernel made preemptible	20-100 µs	Full Linux, one API; soft/firm RT	Linux PREEMPT_RT

The dual-kernel idea is worth understanding because it is elegant: a tiny real-time kernel owns the interrupt controller and runs Linux as its lowest-priority task. Linux cannot disable interrupts — its attempts are virtualised — so nothing Linux does can delay a real-time task. You get hard real-time guarantees and a full Linux userspace, at the price of writing RT code against a separate API and being unable to call Linux services from it. PREEMPT_RT takes the opposite bet: one kernel, one API, slightly weaker guarantees, vastly better ergonomics — and that bet has largely won, which is why it was mainlined.

At the top end, partitioned architectures such as ARINC 653 (avionics) add time and space partitioning: each partition gets a statically defined window in a repeating major time frame, and cannot exceed it. This lets applications of different safety criticality share hardware while remaining certifiable independently — a failure in a non-critical partition cannot consume the critical partition's time budget, because the budget is enforced by a fixed schedule rather than by priorities.

Example

   WHERE THE ARCHITECTURES SIT

   LIBRARY RTOS            RT MICROKERNEL         DUAL-KERNEL
   +-----------------+     +-----------------+    +------------------+
   | app + kernel    |     | app | drv | fs  |    | RT tasks | Linux |
   | one address sp. |     +-----------------+    +----------+ userspc
   +-----------------+     |   microkernel   |    | RT microkernel   |
   |   MCU, no MMU   |     |   (MMU, IPC)    |    | (owns the IRQs)  |
   +-----------------+     +-----------------+    +------------------+
   1-10 us, ~10 KB         5-50 us, isolation     1-20 us, two APIs
   FreeRTOS, Zephyr        QNX, INTEGRITY         Xenomai, RTAI

   PREEMPT_RT LINUX
   +----------------------------------+
   | normal Linux userspace + RT tasks|
   +----------------------------------+
   | one kernel: spinlocks -> sleeping mutexes with PI,
   |             IRQ handlers -> kernel threads         |
   +----------------------------------+
   20-100 us, ONE API, everything Linux has. The pragmatic winner.


   WHY DUAL-KERNEL GIVES HARDER GUARANTEES

   Stock Linux:   Linux code does cli() -> interrupts really off
                  -> RT task cannot run. Unbounded.

   Dual-kernel:   Linux's cli() is INTERCEPTED and only sets a
                  virtual flag. Real interrupts stay enabled.

                  hardware IRQ
                       |
                  +----v-----------------+
                  |  RT kernel (always   |  <- RT tasks: real latency
                  |  gets the interrupt) |
                  +----+-----------------+
                       | (if no RT work)
                  +----v-----------------+
                  |  Linux, as the       |  <- everything else
                  |  lowest prio task    |
                  +----------------------+

   Linux LITERALLY cannot delay the RT side. That is the guarantee.
   The cost: RT code uses Xenomai's API, cannot call Linux services,
   and a mistake crossing the boundary silently loses determinism.


   ARINC 653 TIME PARTITIONING (avionics)

   MAJOR FRAME = 100 ms, repeating exactly, forever

   |<--25ms-->|<--10ms-->|<--40ms-->|<--25ms-->|
   | flight   | nav      | cabin    | flight   |
   | control  |          | systems  | control  |
   | (DAL A)  | (DAL B)  | (DAL D)  | (DAL A)  |

   A partition that overruns is STOPPED at its boundary. Cabin
   systems cannot steal a microsecond from flight control, no
   matter what they do -- the schedule is static, not priority-based.
   This is what makes mixed-criticality certification possible.


   PRIORITY RULES: RTOS vs GENERAL-PURPOSE

   Linux CFS                      FreeRTOS
   ---------                      --------
   vruntime, fairness             strict fixed priority
   priority is a HINT             priority is a CONTRACT
   nice value nudges shares       prio 5 ALWAYS beats prio 4
   everyone eventually runs       low prio may NEVER run (correct!)
   optimises throughput           optimises worst case

/* FreeRTOS: the whole model in one file. Note what is absent --
 * no fork, no malloc in the hot path, no demand paging, no fairness. */
#include "FreeRTOS.h"
#include "task.h"
#include "queue.h"
#include "semphr.h"

#define PRIO_CONTROL   5        /* highest: the 1 ms deadline */
#define PRIO_SENSOR    4
#define PRIO_COMMS     2
#define PRIO_LOGGING   1        /* lowest: may be starved, and that
                                 * is the DESIGNED behaviour */

static QueueHandle_t     sensor_q;
static SemaphoreHandle_t bus_mutex;

/* --- Highest priority: hard 1 ms control loop --------------------- */
static void control_task(void *pv)
{
    TickType_t last = xTaskGetTickCount();
    for (;;) {
        /* Absolute-deadline delay: xTaskDelayUntil accounts for the
         * body's execution time, so the PERIOD does not drift.
         * (xTaskDelay() would drift, exactly like relative nanosleep.) */
        vTaskDelayUntil(&last, pdMS_TO_TICKS(1));

        int16_t sample;
        /* Non-blocking receive: a hard RT task must never wait
         * unboundedly on data that might not arrive. */
        if (xQueueReceive(sensor_q, &sample, 0) == pdTRUE)
            actuate(pid_step(sample));
    }
}

/* --- Interrupt handler: do the minimum, defer the rest ------------ */
void ADC_IRQHandler(void)
{
    BaseType_t woken = pdFALSE;
    int16_t s = ADC->DR;                    /* read the hardware */

    /* FromISR variants never block -- blocking in an ISR would make
     * interrupt latency unbounded for every other interrupt. */
    xQueueSendFromISR(sensor_q, &s, &woken);

    /* If that unblocked a higher-priority task, switch to it on the
     * way out of the ISR rather than waiting for the next tick.
     * This single line is much of what "deterministic" means. */
    portYIELD_FROM_ISR(woken);
}

/* --- A shared resource, with priority inheritance ----------------- */
static void comms_task(void *pv)
{
    for (;;) {
        /* A FreeRTOS MUTEX has priority inheritance; a BINARY SEMAPHORE
         * does NOT. Using the wrong one here recreates the Pathfinder
         * bug -- they look interchangeable and are not. */
        if (xSemaphoreTake(bus_mutex, pdMS_TO_TICKS(10)) == pdTRUE) {
            spi_transfer();                 /* bounded critical section */
            xSemaphoreGive(bus_mutex);
        }
        vTaskDelay(pdMS_TO_TICKS(50));
    }
}

int main(void)
{
    hardware_init();
    sensor_q   = xQueueCreate(16, sizeof(int16_t));  /* STATIC-sized */
    bus_mutex  = xSemaphoreCreateMutex();            /* mutex, not sem */

    /* All tasks created up front. Stack sizes are fixed and must be
     * proven sufficient -- an overflow is silent memory corruption
     * unless configCHECK_FOR_STACK_OVERFLOW is on. */
    xTaskCreate(control_task, "ctrl", 512, NULL, PRIO_CONTROL, NULL);
    xTaskCreate(sensor_task,  "sens", 512, NULL, PRIO_SENSOR,  NULL);
    xTaskCreate(comms_task,   "comm", 768, NULL, PRIO_COMMS,   NULL);
    xTaskCreate(log_task,     "log",  512, NULL, PRIO_LOGGING, NULL);

    vTaskStartScheduler();                  /* never returns */
    for (;;);                               /* only reached if heap
                                             * for the idle task failed */
}

# Linux as an RTOS: check, configure, and verify.

uname -v                        # want: "PREEMPT_RT"
cat /sys/kernel/realtime        # 1 if an RT kernel is running

# Scheduling policies available to userspace:
chrt -m
#   SCHED_OTHER min/max priority        : 0/0     <- fair share, no RT
#   SCHED_FIFO  min/max priority        : 1/99    <- run until preempted
#   SCHED_RR    min/max priority        : 1/99    <- FIFO + timeslice
#   SCHED_DEADLINE                              <- EDF with CBS budgets

chrt -f 80 ./control_loop        # run as SCHED_FIFO priority 80
chrt -p $(pidof control_loop)    # inspect a running process

# SCHED_DEADLINE: declare runtime/deadline/period and the kernel
# ADMISSION-CONTROLS it -- refusing the request if the set would be
# unschedulable. This is EDF enforced by the kernel.
#   sched_setattr(): runtime=1ms deadline=5ms period=5ms

# Keep RT priorities BELOW the threaded IRQ handlers they depend on:
ps -eLo pid,cls,rtprio,comm | grep -E 'irq|FF|RR' | head
#   ...  FF  50  irq/24-eth0      <- IRQ threads here
#   ...  FF  80  control_loop     <- oops: outranks the IRQ feeding it

Key takeaways

• An RTOS chooses bounded worst-case behaviour over average performance in every design decision, which is why features that help throughput are often deliberately absent.
• Every RTOS kernel call has documented worst-case timing, frequently in cycles; a general-purpose kernel makes no such promise.
• Priorities in an RTOS are strict and fixed, with no fairness or ageing, and starving a low-priority task is the intended outcome rather than a bug.
• Library RTOSes link into the application in a single address space for 1-10 µs latency and roughly 10 KB of code, with no memory protection.
• RT microkernels put drivers in user space for fault isolation, paying IPC cost for it; QNX is the canonical example.
• Dual-kernel systems run Linux as the lowest-priority task of a real-time kernel that owns the interrupt controller, so Linux cannot disable interrupts and cannot delay real-time tasks.
• PREEMPT_RT trades slightly weaker guarantees for a single kernel and a single API, and has become the mainstream answer.
• ARINC 653 partitioning enforces static time windows so that a fault in a low-criticality partition cannot consume a high-criticality one's budget.
• In FreeRTOS a mutex provides priority inheritance and a binary semaphore does not, and confusing the two recreates the Pathfinder failure.
• ISR work must be minimal and non-blocking, with FromISR APIs and an explicit yield so a woken high-priority task runs immediately rather than at the next tick.

🧪 Practice

1. Build the FreeRTOS example above (or use the POSIX simulator port) with four tasks at distinct priorities and demonstrate that the lowest-priority task never runs while the highest is always runnable.
2. Replace xSemaphoreCreateMutex() with xSemaphoreCreateBinary() in the code above and construct a three-task scenario that exhibits priority inversion. Then switch it back and show the inversion is bounded.
3. Compare a dual-kernel design and PREEMPT_RT for a system that must run a 20 kHz control loop and also serve a web UI. State which you would pick and what specifically you are giving up.
4. Explain why an ARINC 653 major frame uses a static time schedule rather than fixed priorities, given that fixed priorities are the RTOS norm.
5. Interview-style: "Can we just use Linux for our hard real-time controller?" Hint: separate 'can it usually meet the deadline' from 'can anyone prove it always will', and ask what the certification requirement is.

Embedded System Constraints

Theory

Real-time software usually runs on hardware that a server programmer would find implausible: a microcontroller with 64 KB of RAM, 512 KB of flash, a 48 MHz clock, no MMU, and a power budget measured in microamps. These constraints are not incidental; they reshape how software is written.

Memory. A typical Cortex-M has kilobytes of RAM, so dynamic allocation is usually banned outright. The reason is not just capacity: malloc has unbounded worst-case time and fragments over months of uptime until an allocation fails in a system that cannot be restarted. The standard discipline (codified in MISRA C and similar rules) is to allocate everything statically at compile time, so the linker proves at build time that it fits. Where pools are needed, they are fixed-size block pools with O(1) allocation, never a general heap. Stack sizing is its own hazard: each task gets a fixed stack, overflow silently corrupts whatever is adjacent, and the only defences are worst-case stack analysis, guard regions, and an MPU.

No MMU. Most microcontrollers have at most a memory protection unit — a handful of regions with access permissions, but no address translation. So there is no virtual memory, no demand paging, no fork(), and all code shares one address space where a stray pointer can corrupt anything. An MPU still buys a great deal: mark flash read-only and execute, RAM no-execute, and place a guard region below each stack so an overflow faults instead of silently corrupting.

Flash and execute-in-place. Code usually runs directly from flash (XIP) rather than being copied to RAM, which saves RAM but makes instruction fetch slower and sometimes less predictable. Flash also wears out (typically 10,000-100,000 erase cycles per block) and erases in large blocks, so logging or configuration storage needs wear levelling and a filesystem designed for it (LittleFS, SPIFFS) rather than a general-purpose one.

Power. For a battery device the CPU is asleep almost all the time. The design pattern is the opposite of a server's: do the work in a burst, then return to the deepest sleep state that still preserves what you need. Average current, not peak performance, is the design target — and the arithmetic is brutal. A 220 mAh coin cell powering a device that draws 2 µA asleep and 5 mA awake for 2 ms per second lasts years; raise the sleep current to 20 µA and it lasts months.

Reliability without an operator. An embedded device may run for a decade with no one to restart it. Hence the watchdog timer: a hardware counter that resets the chip unless the software periodically refreshes it. The subtle part is that a correct watchdog is fed only when every critical task has checked in — a naive feed from a timer interrupt will happily keep resetting a system whose main loop is dead. Combined with that: a bootloader supporting A/B firmware slots and rollback, so a bad over-the-air update does not brick a device that is physically unreachable.

Toolchain. Development is cross-compiled on a host, flashed over SWD/JTAG, and debugged with a hardware probe (OpenOCD, Segger). There is often no filesystem, no shell, and no printf except over a serial line — so -Os, --gc-sections, link-time optimisation, and a hard look at the map file are routine parts of the build.

Example

   SCALE: SERVER vs MICROCONTROLLER

                    server            Cortex-M4 MCU     ratio
   RAM              64 GB             64 KB             1,000,000x
   storage          2 TB SSD          512 KB flash      4,000,000x
   clock            3.5 GHz x 32      48 MHz x 1        2,000x
   power            200 W             0.0001 - 0.05 W   ~1,000,000x
   MMU              yes               no (MPU only)
   OS               Linux, 30 MB      FreeRTOS, 10 KB
   reboot           whenever          possibly never in 10 years

   Every one of those rows removes a technique you rely on daily.


   THE MEMORY MAP IS THE DESIGN DOCUMENT

   0x0000_0000  +------------------+
                | vector table     |  interrupt handlers, first entry
                |                  |  is the INITIAL STACK POINTER
                +------------------+
                | .text  (code)    |  executed in place from FLASH
                | .rodata          |  constants, lookup tables
   0x0008_0000  +------------------+  <- 512 KB flash ends
                       ...
   0x2000_0000  +------------------+  <- 64 KB RAM begins
                | .data  (init'd)  |  copied from flash at reset
                | .bss   (zeroed)  |  cleared at reset
                +------------------+
                | task stacks      |  FIXED sizes, chosen at build
                |   [guard page]   |  <- MPU region: overflow FAULTS
                |   task A stack   |     instead of silently corrupting
                |   [guard page]   |
                |   task B stack   |
                +------------------+
                | heap (often 0)   |  <- frequently ELIMINATED entirely
   0x2001_0000  +------------------+

   If .data + .bss + stacks exceed RAM, the LINK FAILS. That is the
   point: the proof that it fits happens at build time, not at 3 a.m.


   WHY malloc IS BANNED, IN ONE PICTURE

   fresh heap:      [################ 16 KB free ##################]
   after 6 months:  [##][ ][####][ ][##][  ][#####][ ][###][ ][####]
                        ^    total free = 6 KB
                        request for 2 KB contiguous  ->  FAILS

   Nothing leaked. Fragmentation alone killed it, after the device
   had been in a wall for half a year, and the failure is
   time-dependent and untestable in a 2-hour soak test.

   Fixed-size pools instead: every block the same size, so a free
   block always satisfies any request. O(1), never fragments.


   THE WATCHDOG, DONE WRONG AND RIGHT

   WRONG: feed from a timer ISR
      timer ISR --> WDT_reload()
      Main loop is deadlocked. ISR still fires. Watchdog is happy.
      The device is dead and the watchdog is protecting it.

   RIGHT: every critical task must check in
      task A --> flag A
      task B --> flag B     supervisor: if (A && B && C) WDT_reload();
      task C --> flag C                 else let it EXPIRE -> reset

/* Static allocation, pools, and a correct watchdog: the three habits
 * that define embedded C. */
#include <stdint.h>
#include <stdbool.h>
#include <string.h>

/* ---------- 1. Everything static. The linker proves it fits. ------- */
#define MAX_SENSORS   8
#define MSG_POOL_SIZE 16
#define MSG_BYTES     64

static sensor_t  sensors[MAX_SENSORS];        /* .bss, fixed forever */
static uint8_t   msg_pool[MSG_POOL_SIZE][MSG_BYTES];
static uint32_t  pool_free_mask = 0xFFFF;     /* one bit per block   */

/* ---------- 2. O(1) fixed-size pool: cannot fragment -------------- */
void *pool_alloc(void)
{
    if (pool_free_mask == 0) return NULL;     /* exhaustion is a
                                               * DESIGNED, tested path */
    int i = __builtin_ctz(pool_free_mask);    /* lowest free bit: O(1) */
    pool_free_mask &= ~(1u << i);
    return msg_pool[i];
}

void pool_free(void *p)
{
    int i = ((uint8_t (*)[MSG_BYTES])p) - msg_pool;
    pool_free_mask |= (1u << i);
}
/* Every block is the same size, so any free block serves any request.
 * Constant time, no fragmentation, no heap metadata to corrupt.      */

/* ---------- 3. Watchdog: fed only if ALL tasks are alive ---------- */
typedef enum { T_CONTROL, T_SENSOR, T_COMMS, T_COUNT } task_id_t;
static volatile uint32_t checkin_mask = 0;

void task_checkin(task_id_t id)               /* called by each task */
{
    checkin_mask |= (1u << id);
}

void supervisor_tick(void)                    /* runs every 100 ms */
{
    const uint32_t ALL = (1u << T_COUNT) - 1;
    if ((checkin_mask & ALL) == ALL) {
        IWDG->KR = 0xAAAA;                    /* reload the watchdog */
        checkin_mask = 0;                     /* require fresh proof */
    }
    /* Otherwise: do nothing. The watchdog expires and resets the chip.
     * Letting it fire is the CORRECT action -- a device nobody can
     * reach must recover itself.                                     */
}

/* ---------- 4. MPU: protection without an MMU --------------------- */
void mpu_setup(void)
{
    /* Region 0: flash, read-only + executable */
    mpu_region(0, 0x08000000, 512 * 1024, MPU_RO | MPU_EXEC);
    /* Region 1: RAM, read-write + NO EXECUTE (blocks injected code) */
    mpu_region(1, 0x20000000,  64 * 1024, MPU_RW | MPU_NX);
    /* Region 2: a 32-byte guard below task A's stack, NO ACCESS.
     * A stack overflow now takes a MemManage fault at the exact
     * instruction that overflowed, instead of silently corrupting
     * whatever happens to live next door.                            */
    mpu_region(2, (uint32_t)&task_a_stack_bottom - 32, 32, MPU_NONE);
    MPU->CTRL = MPU_CTRL_ENABLE | MPU_CTRL_PRIVDEFENA;
}

/* ---------- 5. The power pattern: burst, then sleep deeply -------- */
void main_loop(void)
{
    for (;;) {
        wake_on_rtc_or_irq();                 /* CPU halted until an
                                               * interrupt: ~2 uA      */
        sample_sensors();                     /* ~2 ms at ~5 mA        */
        if (should_transmit())
            radio_burst();                    /* rare, expensive       */
        enter_stop_mode();                    /* deepest state that
                                               * retains RAM + RTC     */
    }
    /* Average current, not peak MHz, is the design target:
     *   (2 uA * 998 ms + 5 mA * 2 ms) / 1000 ms ~= 12 uA
     *   220 mAh coin cell / 12 uA ~= 2 years.
     *   Raise sleep current to 20 uA and it becomes ~4 months.       */
}

# ---- Cross-compile, then read the map file like a budget ----
arm-none-eabi-gcc -mcpu=cortex-m4 -mthumb -Os \
    -ffunction-sections -fdata-sections \
    -Wl,--gc-sections -Wl,-Map=firmware.map \
    -T stm32f4.ld main.c -o firmware.elf

arm-none-eabi-size firmware.elf
#    text    data     bss     dec     hex filename
#   42184     512    8192   50888    c6c8 firmware.elf
#    ^^^^^    ^^^     ^^^
#    flash    flash->RAM    RAM
#  flash used  = text + data = 42,696 / 512 KB   OK
#  RAM used    = data + bss  =  8,704 /  64 KB   plus STACKS

# What is actually big? Sort the map file's symbols:
arm-none-eabi-nm --size-sort -S firmware.elf | tail -20

# Worst-case stack depth, statically (no measurement, a BOUND):
arm-none-eabi-gcc -fstack-usage ...        # emits .su files per function
# then a call-graph tool sums the deepest path per task.

# ---- Flash and debug over SWD ----
openocd -f interface/stlink.cfg -f target/stm32f4x.cfg \
        -c "program firmware.elf verify reset exit"
arm-none-eabi-gdb firmware.elf -ex "target remote :3333"

# ---- Measure the thing that actually matters ----
# A current probe on the supply rail, not a profiler:
#   sleep current, burst current, burst duration -> average current
#   average current + battery capacity -> years of life

Key takeaways

• Embedded targets differ from servers by six orders of magnitude in RAM, storage, and power, and each gap removes a technique that general-purpose programming takes for granted.
• Dynamic allocation is avoided because malloc has unbounded worst-case time and fragments over long uptimes, failing months later in a device that cannot be restarted.
• Static allocation moves the proof that memory fits from runtime to link time, which is the entire point of the discipline.
• Fixed-size block pools give O(1) allocation that cannot fragment, and are the sanctioned alternative where dynamic behaviour is genuinely needed.
• Most microcontrollers have an MPU rather than an MMU: no translation and no paging, but enough to make flash read-only, RAM non-executable, and stack overflows fault at a guard region.
• Code executes in place from flash, which saves RAM but makes instruction timing less predictable, and flash wear demands purpose-built filesystems.
• Battery life is determined by average current, dominated by sleep current, so the design pattern is a short burst of work followed by the deepest usable sleep state.
• A watchdog must be fed only after every critical task has checked in; feeding it from a timer interrupt protects a dead system.
• A/B firmware slots with rollback are essential for devices that receive over-the-air updates and cannot be physically recovered.
• The map file, size, and -fstack-usage are routine build outputs, because fitting in memory is a budget that must be checked, not an assumption.

🧪 Practice

1. Compute the battery life of a device on a 220 mAh cell that sleeps at 3 µA and wakes for 5 ms per second at 8 mA. Then recompute with a sleep current of 30 µA and explain which parameter dominates.
2. Implement the fixed-size pool above with a free-list instead of a bitmask, and argue which version has the better worst-case time and why that matters more than average time.
3. Explain why feeding a watchdog from a periodic timer interrupt is a defect, and rewrite supervisor_tick so that a single hung task causes a reset within 500 ms.
4. Build any small C program for an ARM target with -Wl,-Map, and identify the three largest contributors to .text and to .bss from the map file.
5. Interview-style: "Our firmware works perfectly in testing but a few field units lock up after several months. Where do you look first?" Hint: think about failure modes whose probability grows with uptime rather than with load — and what a two-hour soak test cannot reveal.

<a id="143-mobile-operating-systems"></a>

14.3 Mobile Operating Systems

A phone runs a full multitasking kernel on hardware comparable to a laptop, yet its operating system makes systematically different choices — because its scarcest resources are battery charge and the user's attention, not cycles. This section covers the three mechanisms that follow from that (aggressive power management, memory reclaim without swap, and OS-controlled application lifetimes) and then examines how Android and iOS each implement them.

Mobile Power Management

Theory

On a server, power management is a cost optimisation. On a phone it is the primary design constraint, because the device has roughly 10-20 Wh of energy for a full day and the user judges the product by whether it survives until bedtime.

The foundational fact is that a modern SoC's idle power is dramatically lower than its active power — often by three or four orders of magnitude — and that the transition between them costs both time and energy. This produces two competing strategies, and knowing which applies is most of the skill.

Race to idle says: run at maximum frequency, finish the work as fast as possible, and get back to the deep sleep state where almost no power is drawn. It wins when static (leakage) power dominates and when the sleep state is much cheaper than any active state. Frequency scaling (DVFS) says the opposite: run slower, because dynamic power scales roughly with V²f and voltage can be lowered with frequency, making the energy per instruction lower at low clocks. Real systems do both — the scheduler-driven schedutil governor on Android picks a frequency from the scheduler's own utilisation signal, and Energy Aware Scheduling on big.LITTLE hardware places each task on the core type whose energy model predicts the lowest cost for that task's demand.

But the CPU is frequently not the problem. The expensive components are the display (often the single largest consumer when the screen is on), the cellular radio, and GPS. The radio in particular behaves in a way that surprises people: an LTE modem transitions through RRC states, and after transmitting it stays in a high-power connected state for a tail of 5-15 seconds before stepping down, in case more data arrives. So sending one byte can cost as much energy as sending a megabyte. This makes batching the single highest-value optimisation on mobile: ten separate network requests spread over a minute keep the radio hot the whole time, while the same ten requests issued together pay one tail.

The same logic applies to wakeups. If twenty apps each schedule a timer at an arbitrary moment, the CPU never gets a long sleep. Timer coalescing (aligning timers to shared boundaries) and deferred execution (running work when the device is already awake, charging, or on Wi-Fi) restore long idle periods. This is why modern mobile APIs deliberately refuse to give apps precise periodic timers.

Both platforms enforce this with policy, not just APIs. Android's wakelock is an explicit assertion that the CPU must stay awake; an app holding one incorrectly can flatten a battery overnight, which is why holding one is visible in battery statistics and increasingly restricted. Doze mode suspends network access and defers jobs when the device has been stationary and unused, batching deferred work into periodic maintenance windows whose frequency decreases the longer the device stays idle. App Standby Buckets classify apps by usage frequency (active, working set, frequent, rare, restricted) and tighten their job and alarm quotas accordingly. iOS is stricter still: apps do not generally run in the background at all, and background work is granted through specific entitlements and a scheduler that decides when based on the system's own energy and usage model.

Example

   THE RADIO TAIL: WHY BATCHING BEATS EVERYTHING

   power
     |    +--------+                   +--------+
     |    | TX/RX  |                   | TX/RX  |
   ~1W|   |        |                   |        |
     |    |        +-----tail-----+    |        +-----tail-----+
   ~0.5W  |        | connected,   |    |        | connected,   |
     |    |        | idle, HOT    |    |        | idle, HOT    |
     |    |        | 5-15 s       |    |        | 5-15 s       |
   ~0.01W +--------+--------------+----+--------+--------------+
     +------------------------------------------------------------> t
          ^ 200 ms of actual data        ^ 200 ms of actual data

   TWO requests 30 s apart  = 2 tails = ~20 s of high power
   TWO requests back to back = 1 tail  = ~10 s of high power

   The energy cost is dominated by the NUMBER of transmission
   episodes, not by the number of BYTES. A 1-byte poll every
   minute can cost more than a 1 MB download.


   WAKEUP ALIGNMENT: WHY THE CPU NEVER SLEEPS PROPERLY

   UNALIGNED (each app picks its own moment)
   app A  |    x       x       x       x      |
   app B  |  x    x      x   x       x        |
   app C  |     x    x     x     x      x     |
   CPU    |__/\_/\__/\_/\_/\__/\_/\__/\_/\____|
             never reaches a deep sleep state; every wake pays
             the entry+exit energy again

   COALESCED (timers snapped to shared boundaries)
   app A  |    x               x              |
   app B  |    x               x              |
   app C  |    x               x              |
   CPU    |____/\______________/\_____________|
             two wakeups, long deep-sleep stretches between

   This is why mobile APIs refuse to give apps exact periodic timers.


   ANDROID DOZE: PROGRESSIVE RESTRICTION

   screen off + stationary + unused
        |
        v
   +----------+   maintenance   +----------+   maintenance
   |  DOZE    |---- window ---->|  DOZE    |---- window --->
   | no net   |  jobs+syncs run | no net   |  (less often)
   | no jobs  |  alarms fire    | no jobs  |
   | no alarms|                 | no alarms|
   +----------+                 +----------+
     ~1 min                       ~2 min      ~4 min  ... up to hours

   The idle windows LENGTHEN the longer the device stays untouched.
   High-priority FCM messages still break through; ordinary
   background work does not.


   WHERE THE ENERGY ACTUALLY GOES (rough, screen-on browsing)

   display        ####################################  ~40%
   cellular/WiFi  ####################                  ~25%
   CPU/GPU        ##############                        ~20%
   GPS (if on)    ########                              ~10%
   other          ###                                    ~5%

   Optimising CPU while polling the network every 5 s is
   optimising the wrong fifth of the problem.

// Android: the wrong way and the right way to do periodic work.

// ---------- WRONG: an exact alarm plus a wakelock ----------
// Fires regardless of Doze, wakes the device on its own schedule,
// holds the CPU awake, and cannot be coalesced with anything else.
val am = getSystemService(AlarmManager::class.java)
am.setExactAndAllowWhileIdle(                 // punches through Doze
    AlarmManager.RTC_WAKEUP,
    System.currentTimeMillis() + 60_000,
    pendingIntent
)
val wl = powerManager.newWakeLock(
    PowerManager.PARTIAL_WAKE_LOCK, "app:sync")
wl.acquire()                                  // if a crash skips
doNetworkSync()                               // release(), the battery
wl.release()                                  // is gone by morning

// ---------- RIGHT: describe the CONSTRAINTS, let the OS choose ----
// WorkManager holds the wakelock for you, survives reboots, retries
// with backoff, and coalesces with other apps' deferred work.
val constraints = Constraints.Builder()
    .setRequiredNetworkType(NetworkType.UNMETERED)  // Wi-Fi only
    .setRequiresBatteryNotLow(true)                 // not at 5%
    .setRequiresCharging(true)                      // free energy
    .build()

val sync = PeriodicWorkRequestBuilder<SyncWorker>(
        6, TimeUnit.HOURS)                    // a HINT, not a promise:
    .setConstraints(constraints)              // the OS picks the moment
    .setBackoffCriteria(BackoffPolicy.EXPONENTIAL,
                        30, TimeUnit.SECONDS)
    .build()

WorkManager.getInstance(context)
    .enqueueUniquePeriodicWork("sync", ExistingPeriodicWorkPolicy.KEEP, sync)

class SyncWorker(ctx: Context, params: WorkerParameters)
    : CoroutineWorker(ctx, params) {
    override suspend fun doWork(): Result {
        // Batch everything into ONE radio episode: one tail, not five.
        return try {
            val batch = pendingOperations()          // collect first
            api.sendBatch(batch)                     // then one round trip
            Result.success()
        } catch (e: IOException) {
            Result.retry()                           // backoff handled
        }
    }
}

// iOS: the same principle, enforced more strictly by the platform.

import BackgroundTasks

// Register at launch; the system decides IF and WHEN this ever runs,
// based on how often the user opens the app, battery level, and
// charging state. There is no way to demand a schedule.
BGTaskScheduler.shared.register(
    forTaskWithIdentifier: "com.example.refresh", using: nil
) { task in
    handleRefresh(task: task as! BGAppRefreshTask)
}

func scheduleRefresh() {
    let request = BGAppRefreshTaskRequest(identifier: "com.example.refresh")
    request.earliestBeginDate = Date(timeIntervalSinceNow: 3600)  // a floor,
    try? BGTaskScheduler.shared.submit(request)     // never a guarantee
}

func handleRefresh(task: BGAppRefreshTask) {
    scheduleRefresh()                          // always reschedule first

    // The system may revoke the CPU at any moment; you get seconds.
    task.expirationHandler = {
        operation.cancel()                     // save state, exit cleanly
    }

    operation.completionBlock = {
        // Reporting completion accurately affects whether the system
        // grants you time again: over-running degrades your budget.
        task.setTaskCompleted(success: !operation.isCancelled)
    }
    queue.addOperation(operation)
}

// For large transfers, hand the work to the OS entirely: it runs the
// download out of process, in its own batching window, and wakes the
// app when it is done.
let config = URLSessionConfiguration.background(withIdentifier: "dl")
config.isDiscretionary = true            // "run when it is cheap"
config.allowsCellularAccess = false      // Wi-Fi only

# Inspect and simulate power behaviour on Android.

adb shell dumpsys batterystats --charged com.example.app
#   Wake lock *sync*: 4h 12m 03s partial (12 times)   <- a battery bug
#   Wakeup alarm *walarm*:sync: 1440 times            <- once a minute!

adb shell dumpsys power | grep -A5 "Wake Locks"      # who is holding one now
adb shell dumpsys alarm | grep -B2 -A5 com.example   # scheduled alarms

# Force Doze to test that your app survives it:
adb shell dumpsys deviceidle force-idle
adb shell dumpsys deviceidle step                    # advance the state
adb shell dumpsys deviceidle unforce

# Check and change an app's standby bucket:
adb shell am get-standby-bucket com.example.app      # 10=active .. 45=restricted
adb shell am set-standby-bucket com.example.app rare

# Battery Historian turns a bugreport into a timeline of wakeups,
# radio state, and screen state -- the tool that actually finds drains:
adb bugreport bugreport.zip

Key takeaways

• Battery energy, not CPU time, is the scarce resource on mobile, and idle power is orders of magnitude below active power, so maximising deep-sleep time dominates every other optimisation.
• Race to idle and DVFS are complementary strategies; scheduler-driven governors and Energy Aware Scheduling choose between them using an energy model of the specific hardware.
• The display, cellular radio, and GPS typically consume more than the CPU, so CPU-focused optimisation often addresses the wrong fifth of the problem.
• The radio's RRC tail keeps the modem in a high-power state for 5-15 seconds after any transmission, making the number of transmission episodes matter more than the bytes sent.
• Batching network requests and coalescing timers restore long idle periods, which is why mobile APIs deliberately withhold precise periodic timers from apps.
• Android wakelocks are explicit assertions that the CPU must stay awake, and a leaked one is a classic overnight battery drain.
• Doze defers network access and jobs during stationary idle periods, with maintenance windows that grow further apart the longer the device is untouched.
• App Standby Buckets tighten quotas for infrequently used apps, so background capability is earned by user engagement.
• The correct API pattern is to declare constraints (charging, unmetered network, battery not low) and let the OS choose the moment, rather than demanding an exact schedule.

🧪 Practice

1. An app polls a server every 30 seconds with a 100-byte request. Given a 10-second radio tail, compute the fraction of each minute the modem spends in a high-power state, then recompute for a single batched poll every 15 minutes.
2. Convert the "wrong" AlarmManager example above into a WorkManager request with constraints, and list every failure mode WorkManager handles that the original does not.
3. Run adb shell dumpsys batterystats on a device, identify the app holding the most partial wakelock time, and explain what evidence would distinguish a legitimate hold from a leak.
4. Explain why iOS gives no guarantee that a BGAppRefreshTask will ever run, and what design consequence that has for an app that must display fresh data at launch.
5. Interview-style: "Users report our app drains their battery, but our CPU profiler shows almost no usage. Where do you look?" Hint: profile energy, not cycles — and ask what the device's radio and screen were doing while your code was idle.

Mobile Memory Constraints

Theory

The defining memory fact about a phone is what it does not have: a swap file backed by a disk. Chapter 8's entire demand-paging machinery assumed anonymous pages could be evicted to secondary storage. On mobile that assumption is removed for two reasons — flash has limited write endurance and would wear out under swap traffic, and reading back from flash while the user is touching the screen produces exactly the stalls mobile design is built to avoid.

So the classic response to memory pressure is unavailable. Clean file-backed pages (code, mapped resources) can still be dropped and re-read, but anonymous memory — the heap — cannot go anywhere. Two mechanisms fill the gap.

Compressed memory. Rather than writing pages to flash, compress them in RAM. Android uses zram, a compressed block device in memory used as swap; iOS has an equivalent compressor in the kernel. A typical 2-3x compression ratio means cold anonymous pages effectively shrink, trading CPU cycles (decompression on access) for capacity. This is strictly better than flash swap on this hardware: decompression costs microseconds, a flash read costs hundreds of microseconds and wears the device.

Killing whole processes. When compression is not enough, the OS does something a desktop rarely does: it terminates an entire application. Android's lmkd (low memory killer daemon) and iOS's Jetsam both maintain a ranking of processes and kill from the least important end until pressure subsides. The ranking is derived from what the user is doing: the foreground app is killed last, a visible app next, then services, then cached background apps, which are killed freely and routinely.

On Android this is expressed as oom_score_adj, a per-process value the ActivityManager updates as apps change state. The cached-app tier is the key insight: when you press Home, your process usually stays alive with its heap intact, purely so that returning to it is instant. Those cached processes are a memory cache, and killing them is a normal, healthy operation — not a failure. Modern Android's lmkd triggers on PSI (pressure stall information) rather than raw free-memory thresholds, killing based on how much time processes actually spend stalled on memory rather than on a number that means little on its own.

The consequence for application developers is the central contract of mobile programming: your process can be killed at any moment, without warning, and without running any cleanup code. Not an exception, not a callback you can veto — SIGKILL. Anything the user would be upset to lose must already be persisted. Both platforms provide pressure callbacks (onTrimMemory, didReceiveMemoryWarning) as an opportunity to release caches before the killer reaches you, but they are advisory: responding well makes you a less attractive target, and responding badly gets you killed.

There are also hard per-app heap limits. Android gives each app a Dalvik/ART heap cap that varies by device (commonly 128-512 MB), and exceeding it throws OutOfMemoryError even when the device has free RAM — a deliberate policy that stops one app from monopolising a shared device. Bitmaps are the usual culprit: a 4000×3000 photo at 4 bytes per pixel is 48 MB decoded, regardless of the JPEG being 3 MB on disk.

Example

   NO SWAP CHANGES EVERYTHING

   DESKTOP under memory pressure        MOBILE under memory pressure
   -----------------------------        ---------------------------
   evict clean file pages               evict clean file pages
   swap anonymous pages to disk         COMPRESS anon pages (zram)
   thrash, get slow, stay alive         KILL ENTIRE PROCESSES
   user notices sluggishness            user notices an app "restarted"

   Why no swap: flash write endurance, and a swap-in stall during a
   touch interaction is exactly the jank the whole design avoids.


   ANDROID'S KILL LADDER (oom_score_adj, higher = killed sooner)

   adj    class                          killed
   ----   ----------------------------   ---------------------------
   -1000  native/system critical         never (the kernel itself)
      0   FOREGROUND app (on screen)     last resort only
    100   VISIBLE (behind a dialog)      rarely
    200   PERCEPTIBLE (music playing)    under real pressure
    300   BACKUP / heavy weight
    500   SERVICE (background work)      routinely
    700   CACHED activity (pressed Home) FREELY -- this is by design
    900   CACHED empty process           first, always

   lmkd kills from the BOTTOM UP until memory pressure drops.

   Key point: a cached process is a CACHE. Killing it is normal
   operation, not a failure. Its only purpose is making a return
   to the app instant; when memory is worth more, it goes.


   WHAT THE USER SEES, AND WHY STATE SAVING MATTERS

   user in app A  -> presses Home -> app A becomes CACHED (alive)
                  -> opens B, C, D (camera, maps, game)
                  -> memory pressure -> lmkd kills A
                  -> user returns to A

   If A saved its state:    A restarts, restores scroll position,
                            form contents, selected tab.
                            The user perceives "it was still there".
   If A did not:            A restarts at its home screen with an
                            empty form. The user perceives A CRASH,
                            and blames the app, not the OS.

   Same OS behaviour. Entirely different product.


   THE BITMAP TRAP (the usual cause of OutOfMemoryError)

   file on disk:      photo.jpg          3 MB   (compressed)
   decoded in RAM:    4000 x 3000 x 4 = 48 MB   (ARGB_8888)
   displayed in:      a 400 x 300 thumbnail

   Loading 6 such thumbnails = 288 MB > a 256 MB heap cap -> OOM,
   on a device with 4 GB of free RAM. The cap is per-app POLICY.

   Fix: decode at the size you will actually display
        (inSampleSize / BitmapFactory.Options) -> 400x300x4 = 480 KB,
        a 100x reduction, with no visible difference.

// Android: responding to pressure, and the state-saving contract.

class GalleryActivity : AppCompatActivity() {

    // ---- 1. Release caches when asked. This makes you a LESS
    //         attractive kill target, and is the only warning you get.
    override fun onTrimMemory(level: Int) {
        super.onTrimMemory(level)
        when (level) {
            // The process is cached and near the top of the kill list.
            TRIM_MEMORY_COMPLETE,           // about to be killed
            TRIM_MEMORY_MODERATE ->
                imageCache.evictAll()       // drop everything

            TRIM_MEMORY_BACKGROUND ->
                imageCache.trimToSize(imageCache.size() / 2)

            // Still foreground, but the system is under pressure.
            TRIM_MEMORY_RUNNING_LOW,
            TRIM_MEMORY_RUNNING_CRITICAL ->
                imageCache.trimToSize(maxSize / 4)
        }
    }

    // ---- 2. Save state. Your process WILL be killed eventually.
    //         onSaveInstanceState survives process death; onPause does
    //         not save anything by itself.
    override fun onSaveInstanceState(outState: Bundle) {
        super.onSaveInstanceState(outState)
        outState.putInt("scroll", recyclerView.scrollPosition())
        outState.putString("query", searchBox.text.toString())
        // Small UI state only: the Bundle goes through Binder and has
        // a ~1 MB transaction limit. Large data belongs in a database
        // or a file, written as it changes.
    }

    override fun onCreate(saved: Bundle?) {
        super.onCreate(saved)
        // Cannot distinguish "first launch" from "restored after being
        // killed" except by this Bundle -- and that is the point.
        saved?.let {
            recyclerView.scrollTo(it.getInt("scroll"))
            searchBox.setText(it.getString("query"))
        }
    }

    // ---- 3. Never decode more pixels than you will display.
    fun loadThumbnail(path: String, reqW: Int, reqH: Int): Bitmap {
        val opts = BitmapFactory.Options().apply {
            inJustDecodeBounds = true           // measure without allocating
        }
        BitmapFactory.decodeFile(path, opts)

        var sample = 1
        while (opts.outWidth / sample > reqW * 2) sample *= 2
        opts.inSampleSize = sample              // decode 1/sample per axis
        opts.inJustDecodeBounds = false
        opts.inPreferredConfig = Bitmap.Config.RGB_565   // 2 bytes, not 4
        return BitmapFactory.decodeFile(path, opts)!!
    }
}

// iOS: the same contract, different names. Jetsam, not lmkd.

class GalleryViewController: UIViewController {

    override func viewDidLoad() {
        super.viewDidLoad()
        // The warning arrives on the main thread; act immediately.
        NotificationCenter.default.addObserver(
            self,
            selector: #selector(handleMemoryWarning),
            name: UIApplication.didReceiveMemoryWarningNotification,
            object: nil)
    }

    @objc func handleMemoryWarning() {
        imageCache.removeAllObjects()
        // Ignoring this notification does not defer the problem;
        // Jetsam terminates the app with no further notice and
        // the user sees it as a crash.
    }

    // State restoration: iOS may terminate a suspended app at any time.
    func application(_ app: UIApplication,
                     shouldSaveSecureApplicationState c: NSCoder) -> Bool {
        return true      // opt in, then encode state in the coder
    }
}

// NSCache is purge-aware: the system evicts from it automatically
// under pressure. A plain Dictionary does not, and will get you killed.
let imageCache = NSCache<NSString, UIImage>()
imageCache.totalCostLimit = 50 * 1024 * 1024     // a self-imposed budget

# Observe the machinery on Android.

adb shell cat /proc/meminfo | head -5
adb shell dumpsys meminfo com.example.app
#   Java Heap:  42,180 KB     <- counts against the per-app cap
#   Native Heap: 18,220 KB
#   Graphics:    31,104 KB    <- textures; often the real consumer
#   TOTAL PSS:  104,660 KB    <- proportional set size, the fair metric

# The kill ladder, live:
adb shell cat /proc/$(adb shell pidof com.example.app)/oom_score_adj
#   0     while foreground
#   700   after pressing Home    <- now freely killable

# Who was killed and why:
adb shell dumpsys activity lru
adb logcat | grep -E "lowmemorykiller|lmkd|am_kill"
#   lmkd: Kill 'com.example.app' (12345), adj 700, to free 104660kB
#         because PSI some avg10 = 45.2  <- pressure-based, not
#                                           free-memory-threshold based

# Compressed swap, not flash swap:
adb shell cat /proc/swaps
#   Filename     Type       Size      Used     Priority
#   /dev/block/zram0  partition  2097148  845220   -2
#                     ^^^^^^^^^ in RAM, compressed ~2-3x

# Verify your app survives being killed in the background:
adb shell am kill com.example.app     # simulate lmkd, then reopen it

Key takeaways

• Mobile devices have no flash-backed swap, because flash wears out and swap-in stalls produce exactly the interaction jank the platform is designed to avoid.
• Clean file-backed pages can still be dropped and re-read, but anonymous heap memory has nowhere to go, so the classic eviction path is unavailable.
• Compressed memory (zram on Android, the kernel compressor on iOS) trades CPU for capacity at roughly 2-3x, and is far cheaper than a flash read.
• When compression is insufficient, the OS terminates entire processes — lmkd on Android, Jetsam on iOS — starting from the least important.
• Android ranks processes by oom_score_adj, updated as apps change state, with cached background processes killed freely because they exist only as a fast-resume cache.
• Modern lmkd triggers on pressure stall information rather than free-memory thresholds, reacting to actual stalling rather than an arbitrary number.
• The core mobile contract is that a process can be SIGKILLed with no warning and no cleanup, so anything the user would miss must already be persisted.
• onTrimMemory and didReceiveMemoryWarning are advisory chances to shed caches; responding well lowers your kill priority and ignoring them does not defer the problem.
• Per-app heap caps cause OutOfMemoryError even with free system RAM, and decoded bitmaps — sized by pixels, not by file size — are the usual cause.
• A well-behaved app restores its state so that a kill and restart is indistinguishable from having stayed resident; the OS behaviour is identical, only the perceived quality differs.

🧪 Practice

1. Compute the decoded size of a 6000×4000 photo at ARGB_8888 and at RGB_565, then determine how many of each fit in a 256 MB heap cap. Explain why the JPEG's file size is irrelevant.
2. Read /proc/<pid>/oom_score_adj for an app while it is in the foreground and again after pressing Home. Explain the change in terms of the kill ladder.
3. Use adb shell am kill on your own app while it is backgrounded, reopen it, and determine whether any user-visible state was lost. Fix whatever was.
4. Explain why NSCache is preferable to a dictionary for image caching on iOS, and name the Android equivalent.
5. Interview-style: "Why does Android kill background apps instead of swapping them out like a desktop would?" Hint: consider the physical storage medium, its write endurance, and what a page fault feels like during a touch gesture.

Application Lifecycle Management

Theory

The two previous topics converge on one design decision that most distinguishes mobile from desktop: the operating system, not the user and not the application, decides how long an application's process lives.

On a desktop, an application starts when launched and exits when closed or when it crashes. On mobile, neither event maps cleanly. The user "leaves" an app by pressing Home or swiping; they have no concept of quitting it and generally should not need one. Meanwhile the OS must be free to reclaim that memory. So the platform defines a lifecycle: a state machine the app is moved through, with callbacks at each transition, and a contract about what it may do in each state.

Android's model is built around components rather than a single main function. An Activity (one screen) moves through onCreate → onStart → onResume → running → onPause → onStop → onDestroy, and the key discipline is knowing which callback is guaranteed. onPause is the last callback guaranteed to run before the app loses foreground; onStop usually runs; onDestroy may never run at all, because a process kill skips every callback. So the rule is: persist anything important by onStop at the latest, and never treat onDestroy as a cleanup hook you can rely on. The modern Lifecycle-aware components exist so that observers (a location listener, a camera session, a coroutine scope) attach and detach automatically at the right transitions, which eliminated an entire category of leak.

The crucial subtlety is that Activity lifecycle and process lifetime are different things. An Activity can be destroyed and recreated — a rotation does exactly that — while the process lives on; or the whole process can be killed while the Activity's saved state survives in the system, to be handed back at relaunch. This is why onSaveInstanceState exists separately: it survives process death, whereas fields in your object do not.

iOS uses a simpler, stricter model: Not Running → Inactive → Active → Background → Suspended. The important state is Suspended: the app is still in memory, with all of its state intact, but it receives no CPU time at all. It is frozen, and it can be terminated from that state without any further notification. Background execution is not a right; it is granted for specific declared purposes (audio playback, location, VoIP, background fetch, processing tasks) and even then is time-limited. beginBackgroundTask buys roughly 30 seconds to finish something critical and no more.

The practical consequences are the same on both platforms, and they are worth stating as rules:

• Save state continuously as it changes, not at exit — there may be no exit.
• Any resource held across a transition (camera, GPS, socket, wakelock) must be released when leaving the foreground and reacquired on return, or the OS will hold it against you.
• A cold start after a kill must be fast and must land the user where they were, because to them it was not a restart.
• Never assume a cleanup callback will run.

Example

   ANDROID ACTIVITY LIFECYCLE (and which callbacks you can trust)

                    +-------------+
   launch --------> |  onCreate   |  build UI, restore saved state
                    +------+------+
                           v
                    +-------------+
                    |   onStart   |  becoming visible
                    +------+------+
                           v
                    +-------------+
                    |  onResume   |  foreground, interactive
                    +------+------+     acquire camera/GPS HERE
                           |
                    +------v------+
                    |   RUNNING   |
                    +------+------+
                           |  user presses Home / another app opens
                    +------v------+
                    |   onPause   |  <== LAST GUARANTEED CALLBACK
                    +------+------+     release camera/GPS, stop
                           v            animations. Keep it FAST:
                    +-------------+     the next activity waits on it.
                    |   onStop    |  usually runs; persist by here
                    +------+------+
                           v
                    +-------------+
                    |  onDestroy  |  MAY NEVER RUN. Not a cleanup hook.
                    +-------------+
                           |
                     process killed by lmkd  ---> nothing runs at all
                                                   (SIGKILL)

   RETURN PATH:  onRestart -> onStart -> onResume  (process survived)
                 onCreate(savedInstanceState)      (process was killed)
                          ^^^^^^^^^^^^^^^^^ the Bundle is how state
                                            crosses process death


   PROCESS LIFETIME vs ACTIVITY LIFETIME -- NOT THE SAME AXIS

   rotation:          Activity destroyed + recreated, process ALIVE
                      -> instance fields lost, static/ViewModel kept
   Home + lmkd kill:  Activity AND process gone
                      -> only the saved Bundle survives
   Home, no pressure: both alive, just cached
                      -> instant resume, nothing to restore

   Your code must produce the SAME user experience in all three.


   iOS APP STATES

   +-------------+   launch    +----------+  becomes  +---------+
   | Not Running |------------>| Inactive |---------->| Active  |
   +-------------+             +----------+   active  +---------+
          ^                         ^                      |
          |                         | interrupted          | home /
          |                         | (call, notification) | app switch
          |                         |                      v
          |                    +----+-----------------+---------+
          |                    |            Background          |
          |                    |  ~30 s, or a declared mode     |
          |                    +---------------+----------------+
          |                                    | time expires
          |    terminated (NO notification)    v
          +---------------------------+  +-----------+
                                         | SUSPENDED |  in memory,
                                         +-----------+  ZERO cpu,
                                                        killable silently

   "Suspended" is the state desktop programmers have no model for:
   the app exists, holds all its state, and executes NOTHING.


   THE RULE THAT FOLLOWS FROM ALL OF IT

   Desktop:  save on exit.          There is an exit.
   Mobile:   save as you go.        There may be no exit, ever.

   text field changed -> persist (debounced)
   item added to cart -> persist immediately
   scroll position    -> save in the state bundle
   "are you sure you want to quit?" -> a category error on mobile

// Android: a lifecycle-correct screen.

class MapActivity : AppCompatActivity() {

    private val viewModel: MapViewModel by viewModels()
    // ViewModel survives CONFIGURATION CHANGES (rotation) but NOT
    // process death. Two different survival scopes -- use both.

    override fun onCreate(savedInstanceState: Bundle?) {
        super.onCreate(savedInstanceState)
        setContentView(R.layout.map)

        // Lifecycle-aware: the observer starts and stops itself at the
        // right transitions. This is what removed a whole class of leak
        // where a listener outlived the screen that registered it.
        lifecycle.addObserver(locationTracker)

        // Restore across PROCESS DEATH (the ViewModel cannot do this).
        savedInstanceState?.let {
            viewModel.restoreCamera(it.getParcelable("camera"))
        }
    }

    // Acquire scarce/expensive resources only while interactive.
    override fun onResume() {
        super.onResume()
        mapView.onResume()
        sensorManager.registerListener(compass, rotationSensor, GAME)
    }

    // onPause is the LAST guaranteed callback. Release here, and be
    // quick: the incoming activity's onResume waits for this to return.
    override fun onPause() {
        sensorManager.unregisterListener(compass)   // battery + leak
        mapView.onPause()
        super.onPause()
    }

    // Persist real data by onStop at the latest.
    override fun onStop() {
        super.onStop()
        viewModel.persistDraft()          // to a database or file
    }

    // Small UI state, survives process death via the system.
    override fun onSaveInstanceState(outState: Bundle) {
        super.onSaveInstanceState(outState)
        outState.putParcelable("camera", mapView.cameraPosition)
    }

    // NOT a reliable cleanup hook: a process kill skips it entirely.
    override fun onDestroy() {
        super.onDestroy()
    }
}

// Structured concurrency tied to the lifecycle: this coroutine is
// cancelled automatically when the screen stops, so it cannot leak
// or keep the CPU awake after the user has left.
lifecycleScope.launch {
    repeatOnLifecycle(Lifecycle.State.STARTED) {
        viewModel.locationFlow.collect { updateMarker(it) }
    }
}

// iOS: the scene lifecycle and the 30-second background grace period.

class SceneDelegate: UIResponder, UIWindowSceneDelegate {

    func sceneDidBecomeActive(_ scene: UIScene) {
        resumeTimers(); startLocationUpdates()
    }

    func sceneWillResignActive(_ scene: UIScene) {
        // Called for a phone call or the app switcher too, not just exit.
        pauseTimers()
    }

    func sceneDidEnterBackground(_ scene: UIScene) {
        // This is the realistic last chance to do work. After the grace
        // period the app is SUSPENDED and gets no CPU at all; it may
        // then be terminated with no further callback.
        saveState()
        stopLocationUpdates()      // or the system shows the location
                                   // indicator and blames you for drain
    }
}

// Finishing critical work when leaving the foreground:
func saveOnBackground() {
    var bgTask: UIBackgroundTaskIdentifier = .invalid
    bgTask = UIApplication.shared.beginBackgroundTask(withName: "save") {
        // Expiration handler: the system is reclaiming the time NOW.
        // You must end the task or the app is killed outright.
        UIApplication.shared.endBackgroundTask(bgTask)
        bgTask = .invalid
    }

    DispatchQueue.global().async {
        database.flush()                       // must finish in ~30 s
        UIApplication.shared.endBackgroundTask(bgTask)
        bgTask = .invalid
    }
}

# Drive lifecycle transitions on Android instead of guessing.

# The single most valuable setting during development: "Don't keep
# activities" destroys every activity as soon as it is backgrounded,
# surfacing every state-restoration bug immediately.
adb shell settings put global always_finish_activities 1

adb shell am start -n com.example/.MapActivity
adb shell input keyevent KEYCODE_HOME          # -> onPause, onStop
adb shell am kill com.example                  # simulate lmkd (SIGKILL)
adb shell am start -n com.example/.MapActivity # -> cold start; did the
                                               #    user land where they
                                               #    left off?

adb shell dumpsys activity activities | grep -A3 "mResumedActivity"
adb logcat | grep -E "ActivityManager.*(Start proc|Killing)"

# Rotation: destroys and recreates the activity, process survives.
adb shell settings put system accelerometer_rotation 0
adb shell settings put system user_rotation 1

Key takeaways

• On mobile the OS decides how long a process lives, because the user has no notion of quitting an app and the system must be free to reclaim memory.
• Android's Activity lifecycle guarantees onPause, usually runs onStop, and may never run onDestroy, so cleanup that matters must happen no later than onStop.
• onPause must be fast, because the incoming screen's resume waits on it.
• Activity lifetime and process lifetime are independent axes: rotation destroys the Activity while the process lives, and a kill destroys the process while the saved state survives.
• onSaveInstanceState is the only channel that crosses process death, and it is limited to small state because it travels over Binder.
• iOS moves apps through Not Running, Inactive, Active, Background, and Suspended, where Suspended means fully resident but receiving zero CPU and terminable without notice.
• iOS background execution is granted for declared purposes and is time-limited; beginBackgroundTask buys roughly 30 seconds and requires an expiration handler.
• Exclusive or expensive resources — camera, GPS, sockets, wakelocks — must be released on leaving the foreground and reacquired on return.
• Lifecycle-aware components and lifecycle-scoped coroutines attach and detach observers automatically, eliminating a large category of leaks.
• The governing rule is to save state continuously rather than on exit, because there may be no exit; a correct app makes a kill-and-restart indistinguishable from never having left.

🧪 Practice

1. Enable "Don't keep activities" on an Android device, navigate through an app you use, and list every place state is visibly lost. Explain which callback should have persisted each item.
2. Draw the sequence of callbacks for: a rotation, pressing Home and returning with the process alive, and pressing Home and returning after an lmkd kill. Mark where onSaveInstanceState fires in each.
3. Explain why a ViewModel survives rotation but not process death, and what mechanism is needed to cover the second case.
4. Write the iOS equivalent of "release the camera when leaving the foreground and reacquire it on return", and state which callback you would use for each half and why.
5. Interview-style: "Where should an app save the user's half-written message?" Hint: name the last callback you are guaranteed to receive, then ask what happens if even that one is skipped.

Android Architecture

Theory

Android is often described as "Linux for phones", which is true of the kernel and misleading about everything else. The kernel is Linux, with significant Android-specific additions; above it sits a stack that shares almost nothing with a desktop GNU/Linux distribution — different libc (Bionic), different IPC (Binder), different init model, different security model, and a managed runtime executing app code.

Working upward:

The kernel. Linux, plus additions driven by mobile requirements: Binder (the IPC mechanism), ashmem/memfd (shared anonymous memory), the low-memory-killer interface used by lmkd, wakelocks, and a strict SELinux policy in enforcing mode. Vendors add device drivers, and Project Treble (Android 8) separated the vendor implementation from the framework through a stable HAL interface so the OS could be updated without the silicon vendor rebuilding everything — the structural fix for Android's update problem.

Binder is the piece worth understanding deeply, because essentially every interesting Android operation is a Binder transaction. It is a kernel driver implementing capability-based object-oriented IPC. Compared with the SysV IPC Android could have used, Binder provides: a single copy (the driver copies directly from sender to a receiver-mapped buffer, rather than user→kernel→user), a per-process thread pool with priority inheritance so a high-priority caller is not blocked behind a low-priority server thread, caller credentials (UID/PID) delivered by the kernel so the receiver can authorise reliably rather than trusting a claim, object references that the driver refcounts across processes, and death notifications when a peer dies. Interfaces are declared in AIDL and compiled into proxy/stub code, so getSystemService(...) returning a "location manager" actually returns a proxy whose method calls become Binder transactions into system_server. The one-megabyte-per-process transaction buffer is the origin of TransactionTooLargeException.

Native layer and runtime. Bionic is a compact libc built for size and licensing rather than POSIX completeness. ART (Android Runtime) executes app bytecode using a hybrid strategy: install-time and idle-time AOT compilation guided by a profile of what actually ran, plus a JIT for what the profile missed, so hot code is native and cold code is not wasting flash. Its concurrent copying collector is tuned for short pauses, because a garbage collection pause during a touch gesture is visible.

Zygote. Starting a fresh runtime per app would be slow and would duplicate every framework class. Instead, a single process called Zygote starts at boot, loads the framework classes and resources, and then forks for every new app. Thanks to copy-on-write, all those apps share one physical copy of the framework's pages. This is why app startup is fast and why per-app memory overhead is far lower than it would otherwise be.

system_server hosts the framework services — ActivityManager, PackageManager, WindowManager, PowerManager and dozens more — each reachable over Binder. It is the policy centre: it decides what starts, what is killed, what permissions apply, and which process is foreground.

The security model is the part most different from desktop Linux. Every app gets its own UID, so the classic UNIX user-isolation mechanism is repurposed to isolate applications from each other; app data directories are simply owned by that UID. On top sit SELinux in enforcing mode (mandatory access control constraining even root-owned daemons), permissions that are runtime-granted for dangerous categories and increasingly scoped and revocable, app signing with update-time signature verification, Verified Boot establishing a chain of trust from hardware, and hardware-backed key storage in a Trusted Execution Environment or dedicated security chip.

Example

   THE ANDROID STACK

   +-----------------------------------------------------------+
   |  APPS (Java/Kotlin bytecode, some native via JNI)         |
   +-----------------------------------------------------------+
   |  JAVA API FRAMEWORK                                        |
   |  Activity/Package/Window/Power managers, View system,      |
   |  Content providers  -- all PROXIES over Binder             |
   +-----------------------------------------------------------+
   |  NATIVE LIBS        |  ANDROID RUNTIME (ART)               |
   |  libc(Bionic), SQLite,  AOT+JIT with profiles,             |
   |  Skia, OpenGL/Vulkan,   concurrent copying GC              |
   |  media codecs           (one ART instance per app)         |
   +-----------------------------------------------------------+
   |  HARDWARE ABSTRACTION LAYER (HAL) -- stable since Treble   |
   |  camera / audio / sensors / GPS ... vendor code lives here |
   +-----------------------------------------------------------+
   |  LINUX KERNEL + Android additions                          |
   |  BINDER | ashmem/memfd | lmkd hooks | wakelocks | SELinux  |
   |  vendor drivers                                            |
   +-----------------------------------------------------------+


   PROCESS MODEL: ZYGOTE AND COPY-ON-WRITE

   boot
     |
     +--> init --> zygote  (loads framework classes + resources ONCE,
     |               |      pre-links them, warms the heap)
     |               |
     |               +-- fork --> com.example.app   (ART + framework
     |               |                               pages SHARED, CoW)
     |               +-- fork --> com.other.app
     |               +-- fork --> system_server
     |
     +--> servicemanager   (the Binder name registry)

   Forking from a pre-warmed template means:
     - fast app start (no class loading or linking)
     - one PHYSICAL copy of the framework across all apps
     - each app still gets its own UID, heap, and address space


   A BINDER TRANSACTION, END TO END

   app process                kernel                 system_server
   -----------                ------                 -------------
   LocationManager
     .getLastLocation()
        |
     proxy marshals args
     into a Parcel
        |
     ioctl(BINDER_WRITE_READ) --->  binder driver
                                    - ONE copy into the target's
                                      pre-mapped buffer (not two)
                                    - attaches REAL caller uid/pid
                                    - priority inheritance: server
                                      thread runs at caller's prio
                                                 |
                                                 v
                                          stub unmarshals
                                          checkPermission(uid) <- uid
                                          came from the KERNEL, so
                                          it cannot be forged
                                                 |
     <--- reply Parcel <------------------------ +
     proxy unmarshals -> Location

   Buffer limit: ~1 MB per process => TransactionTooLargeException
   when an app tries to pass a bitmap through Binder.


   SECURITY: UNIX UIDS, REPURPOSED

   traditional Linux              Android
   ------------------             -------
   uid = a PERSON                 uid = an APP
   /home/alice  (uid 1000)        /data/data/com.example  (uid 10234)
   apps of one user share         two apps CANNOT read each
   everything                     other's files at all

   plus: SELinux enforcing, runtime permissions, app signing,
         Verified Boot, hardware-backed keystore (TEE/StrongBox)

   The oldest mechanism in UNIX, pointed at a problem it was
   never designed for, and fitting remarkably well.

// AIDL: the interface definition that becomes a Binder proxy/stub pair.
// File: ILocationService.aidl

interface ILocationService {
    /* Synchronous: the caller BLOCKS in the kernel until the reply
     * arrives. The server thread runs at the caller's priority. */
    Location getLastLocation(String provider);

    /* oneway: fire and forget -- returns as soon as the transaction is
     * queued. Use for notifications; there is no reply and no
     * guarantee the callee even ran. */
    oneway void reportUsage(String tag, long millis);
}

/* The service side, running inside system_server. */
public class LocationService extends ILocationService.Stub {

    @Override
    public Location getLastLocation(String provider) {
        /* getCallingUid() is supplied BY THE KERNEL, not by the caller.
         * This is the property that makes Binder an authorisation
         * mechanism rather than just a transport. */
        int uid = Binder.getCallingUid();
        int pid = Binder.getCallingPid();

        if (checkPermission(ACCESS_FINE_LOCATION, pid, uid) != GRANTED)
            throw new SecurityException("no location permission");

        /* When calling further services on the caller's behalf, clear
         * the identity first or the next check uses OUR uid, silently
         * granting the caller system privileges. This is the classic
         * confused-deputy bug in Android services. */
        long token = Binder.clearCallingIdentity();
        try {
            return mProvider.getLast(provider);
        } finally {
            Binder.restoreCallingIdentity(token);   // ALWAYS restore
        }
    }
}

/* The client side: an ordinary-looking method call that is a syscall. */
IBinder b = ServiceManager.getService("location");
ILocationService svc = ILocationService.Stub.asInterface(b);
Location loc = svc.getLastLocation("gps");   // -> ioctl -> system_server

/* Death notification: know when the peer process dies, instead of
 * discovering it on the next failed call. */
b.linkToDeath(() -> reconnectOrDegrade(), 0);

# Observe the architecture on a real device.

adb shell ps -A -o PID,USER,NAME | head
#   PID   USER      NAME
#   1     root      init
#   xxx   root      zygote64          <- the fork template
#   xxx   system    system_server     <- the framework services
#   xxx   u0_a234   com.example.app   <- one UID per app
#         ^^^^^^^^ "u0_a234" = user 0, app id 234

adb shell service list | head
#   0  activity: [android.app.IActivityManager]
#   1  package:  [android.content.pm.IPackageManager]
#   2  power:    [android.os.IPowerManager]
#   ... every one of these is a Binder object registered by name

# Live Binder traffic and the per-process buffer usage:
adb shell cat /sys/kernel/debug/binder/stats
adb shell cat /sys/kernel/debug/binder/transactions

# App sandbox: UID ownership is the isolation.
adb shell ls -ld /data/data/com.example.app
#   drwx------ u0_a234 u0_a234 ...    <- mode 700, owned by the app's uid

# SELinux domain of a running app:
adb shell ps -AZ | grep com.example
#   u:r:untrusted_app:s0:c234,c256   <- MAC on top of the UID sandbox
adb shell getenforce                 # Enforcing

# ART compilation state (profile-guided):
adb shell dumpsys package dexopt | grep -A2 com.example
#   [status=speed-profile] [reason=bg-dexopt]
#   ^ compiled AOT for the methods the PROFILE says are actually hot

# Verified Boot / update integrity:
adb shell getprop ro.boot.verifiedbootstate      # green = verified

Key takeaways

• Android uses the Linux kernel with mobile-specific additions — Binder, ashmem/memfd, lmkd hooks, wakelocks, enforcing SELinux — but almost nothing above the kernel resembles a desktop Linux distribution.
• Project Treble separated vendor HAL implementations from the framework behind a stable interface so the OS can be updated without vendor rebuilds.
• Binder is a kernel driver providing single-copy, capability-based IPC with a per-process thread pool, priority inheritance, and kernel-supplied caller credentials.
• Because the kernel supplies the caller's UID, a Binder service can authorise reliably instead of trusting a claim, which makes Binder an authorisation mechanism and not merely a transport.
• The roughly 1 MB per-process Binder buffer is the cause of TransactionTooLargeException when large objects are passed through IPC.
• Services calling other services on a caller's behalf must clear and restore the calling identity, or they become a confused deputy that leaks system privilege.
• Zygote preloads framework classes once and forks each app, so startup is fast and framework pages are shared copy-on-write across every process.
• ART combines profile-guided AOT compilation with a JIT and a low-pause concurrent copying collector, because GC pauses during interaction are visible.
• system_server hosts the framework services and is the policy centre for what runs, what is killed, and which permissions apply.
• Each app runs under its own UID, repurposing UNIX user isolation to isolate applications, with SELinux, runtime permissions, app signing, Verified Boot, and hardware-backed keys layered above.

🧪 Practice

1. Run adb shell ps -A on a device and identify zygote, system_server, and three app processes. Explain what the u0_aNNN user names encode.
2. Explain what makes Binder preferable to a UNIX domain socket for framework IPC, naming at least three properties, and state which of them a socket could be made to provide.
3. Take the LocationService example, remove the clearCallingIdentity/restoreCallingIdentity pair, and describe a concrete privilege-escalation scenario that becomes possible.
4. An app throws TransactionTooLargeException when passing a bitmap to another app. Explain the cause and give two correct alternatives.
5. Interview-style: "Two Android apps are both installed by the same person on the same phone. Why can't one read the other's files?" Hint: the answer is a mechanism from 1970s UNIX, applied to a noun it was not originally about.

iOS Architecture

Theory

Where Android's design is shaped by running on hardware from hundreds of vendors, iOS's is shaped by running on hardware Apple designs itself. That single difference explains most of the architectural divergence: iOS can rely on specific silicon for its security guarantees and can make restrictions stick because there is no alternative distribution channel.

The kernel is XNU ("X is Not Unix"), a hybrid: a Mach microkernel core providing tasks, threads, virtual memory, and Mach ports for IPC, combined with a BSD layer providing the POSIX API, processes, signals, sockets, and the VFS, plus IOKit, a driver framework written in a restricted subset of C++ with an object-oriented device model. Both halves run in one address space, so Mach-style modularity is available without the IPC cost of a true microkernel — the hybrid compromise discussed in Chapter 1.

Mach ports are the foundational IPC primitive, and they are capabilities: a port right is unforgeable, can be transferred in a message, and holding one is what grants the ability to send to that port. Higher-level mechanisms (XPC, distributed notifications, much of the frameworks) are built on them. The parallel with Binder is close — both are capability-based, kernel-mediated, credential-carrying object IPC — reached from different lineages.

launchd is PID 1 and the ancestor of systemd's design: a single daemon that starts and supervises everything, with on-demand launching driven by property-list job descriptions. Grand Central Dispatch (GCD) moves thread management into the OS: applications submit blocks to queues with quality-of-service classes, and the kernel maintains the thread pool, which lets the system make global scheduling and energy decisions that individual apps cannot.

The layered frameworks — Cocoa Touch (UIKit/SwiftUI), Media, Core Services, Core OS — are largely Objective-C and Swift, and they are the only supported interface; the BSD layer exists but is heavily restricted from app code by the sandbox.

The security architecture is where iOS is most distinctive, and it is a chain rather than a set of features:

• Boot ROM — immutable, fused into silicon at manufacture, containing Apple's root public key. This is the anchor of trust.
• Secure Boot chain — each stage verifies the signature of the next, so an unsigned kernel cannot be loaded at all.
• Secure Enclave — a separate coprocessor with its own boot ROM, memory, and OS, holding biometric templates and key material. The main CPU never sees these keys; it asks the Enclave to perform operations.
• Code signing — every executable page must be signed, enforced at page-in. The practical consequence is that writable-and-executable memory is not available to apps, which eliminates classic code injection and forces JIT engines to use a special, tightly controlled entitlement.
• Sandbox (seatbelt) — a mandatory access control system applied to every app, with entitlements declaring what an app may do; the default is a private container directory and little else.
• Data Protection — files are encrypted with per-file keys wrapped by class keys tied to the passcode, so data in the strongest class is genuinely unreadable while the device is locked.
• Kernel hardening — KTRR/KIP (kernel text is made immutable after boot), PAC (pointer authentication, signing pointers so a corrupted one fails verification), and Memory Integrity Enforcement on recent silicon.

Memory and lifecycle follow what the previous topics described: no flash swap, a kernel memory compressor, and Jetsam terminating apps by priority band under pressure. Finally, distribution itself is part of the security model: App Review plus mandatory signing means the platform controls what can run at all — the principal reason iOS malware is rare, and the principal reason the model is contested.

Dimension	Android	iOS
Kernel	Linux + Binder, lmkd, wakelocks	XNU: Mach + BSD + IOKit (hybrid)
IPC	Binder (capability, kernel-mediated)	Mach ports / XPC (capability, kernel-mediated)
Runtime	ART, profile-guided AOT + JIT, GC	Native compiled Swift/ObjC, ARC (no tracing GC)
Process start	Zygote fork, CoW-shared framework	launchd spawn, dyld shared cache
App isolation	One UNIX UID per app + SELinux	Sandbox profiles + entitlements
Memory reclaim	zram, lmkd by oom_score_adj	Compressor, Jetsam by priority band
Background work	Services, JobScheduler, WorkManager	Declared modes, BGTaskScheduler, strict limits
Distribution	Play Store plus sideloading	App Store, signing enforced by the kernel
Hardware	Many vendors, HAL via Treble	Apple silicon only, Secure Enclave assumed

Example

   XNU: A HYBRID, NOT A MICROKERNEL

   +-------------------------------------------------------+
   |  Cocoa Touch: UIKit / SwiftUI / Foundation            |
   +-------------------------------------------------------+
   |  Media (Core Animation, AVFoundation, Metal)          |
   +-------------------------------------------------------+
   |  Core Services (Core Foundation, Core Data, CloudKit) |
   +-------------------------------------------------------+
   |  Core OS (libSystem, GCD, Security, BSD syscalls)     |
   +===================== kernel ==========================+
   |   MACH            |   BSD            |   IOKit        |
   |   tasks, threads  |   POSIX API      |   drivers in   |
   |   virtual memory  |   processes,     |   restricted   |
   |   MACH PORTS(IPC) |   signals,       |   C++, object  |
   |   scheduling      |   sockets, VFS   |   oriented     |
   +-------------------------------------------------------+
        ALL IN ONE ADDRESS SPACE: Mach's structure without
        a microkernel's IPC cost on every service call.


   THE SECURE BOOT CHAIN (each link verifies the next)

   +-------------+  verifies  +---------+  verifies  +--------+
   |  Boot ROM   |----------->|  iBoot  |----------->| kernel |
   | immutable,  |  signature |         | signature  | cache  |
   | fused in    |            |         |            |        |
   | silicon;    |            +---------+            +--------+
   | holds Apple |                                       |
   | root pubkey |                                       v
   +-------------+                            every executable page
         ^                                    signature-checked at
         | cannot be modified, ever           PAGE-IN time
         | -- the anchor of the whole chain

   +------------------------+
   |    SECURE ENCLAVE      |  separate CPU, own boot ROM, own RAM,
   |  biometric templates,  |  own OS. The application processor
   |  key material, counters|  NEVER sees these keys -- it can only
   +------------------------+  ASK the Enclave to use them.

   Consequence: no W+X memory for apps. Code injection -- the
   foundation of most exploit chains -- simply has nowhere to land.
   (A JIT needs a specific entitlement and a controlled API.)


   MACH PORTS vs BINDER: CONVERGENT DESIGN

                   Mach port                Binder
   primitive       port right (capability)  binder handle (capability)
   unforgeable     yes, kernel-held         yes, kernel-held
   transferable    yes, in a message        yes, in a Parcel
   credentials     audit token from kernel  uid/pid from kernel
   refcounting     kernel-managed rights    kernel-managed refs
   death notice    port-death notification  linkToDeath()
   built on top    XPC, frameworks          AIDL, system services

   Two independent lineages, the same conclusion: mobile framework
   IPC must be capability-based and kernel-mediated.


   GCD: THREAD MANAGEMENT AS AN OS SERVICE

   app submits BLOCKS + a QoS class, not threads:

     .userInteractive  -> runs now, highest priority (UI, animation)
     .userInitiated    -> user is waiting on a result
     .default
     .utility          -> progress bar work; may be throttled
     .background       -> may be deferred until charging/idle
                          and runs on efficiency cores

   +------------------------------------------+
   |  queues (serial / concurrent)            |
   +------------------------------------------+
   |  ONE system-wide thread pool, sized and  |  <- the kernel can
   |  placed by the KERNEL                    |     make global energy
   +------------------------------------------+     decisions; an app
                                                    choosing its own
   Apps do not size their own pools, so 20 apps      thread count
   cannot each create 8 threads on a 6-core phone.   cannot.

// GCD: declare intent (QoS), let the OS decide placement and timing.

import Foundation

// High priority: the user is looking at this right now.
DispatchQueue.main.async {
    self.spinner.startAnimating()
}

// Background QoS: the scheduler may run this on efficiency cores and
// may defer it entirely while on battery. That is the POINT --
// energy policy belongs to the OS, not to each app.
DispatchQueue.global(qos: .background).async {
    let thumbnails = self.generateThumbnails()      // slow, not urgent
    DispatchQueue.main.async {
        self.collectionView.reloadData()            // UI on main, always
    }
}

// A serial queue as a lock-free mutual exclusion mechanism: only one
// block runs at a time, so the protected state needs no mutex.
let cacheQueue = DispatchQueue(label: "com.example.cache")
cacheQueue.async { self.cache[key] = value }

// XPC: an out-of-process service over Mach ports. Crash isolation plus
// a smaller sandbox for the risky part (parsing untrusted input).
let connection = NSXPCConnection(serviceName: "com.example.Parser")
connection.remoteObjectInterface = NSXPCInterface(with: ParserProtocol.self)
connection.invalidationHandler = { /* peer died: degrade gracefully */ }
connection.resume()

// Data Protection: the file's protection class decides whether it is
// readable while the device is locked. This is a real cryptographic
// guarantee, not a permission flag.

try data.write(to: url, options: .completeFileProtection)
//   .completeFileProtection            unreadable whenever locked
//   .completeUnlessOpen                readable if already open
//   .completeUntilFirstUserAuthentication  readable after first unlock
//                                          (the usual default)
//   .none                              always readable

// Keychain with Secure Enclave-backed keys: the private key material
// is generated inside the Enclave and cannot be extracted, only used.
let access = SecAccessControlCreateWithFlags(
    nil,
    kSecAttrAccessibleWhenUnlockedThisDeviceOnly,   // no backup, no sync
    [.privateKeyUsage, .biometryCurrentSet],        // Face/Touch ID, and
    nil)                                            // invalidated if the
                                                    // enrolled biometry
                                                    // set changes
let attributes: [String: Any] = [
    kSecAttrTokenID as String: kSecAttrTokenIDSecureEnclave,
    kSecAttrKeyType as String: kSecAttrKeyTypeECSECPrimeRandom,
    kSecPrivateKeyAttrs as String: [kSecAttrAccessControl as String: access]
]
var error: Unmanaged<CFError>?
let key = SecKeyCreateRandomKey(attributes as CFDictionary, &error)
// The app holds a REFERENCE. The key itself never enters app memory,
// so a full compromise of the app does not yield the key.

# Inspecting a Darwin system (macOS shares XNU with iOS; an iOS device
# needs a development setup, so run these on macOS to see the same kernel).

uname -a
#   Darwin ... root:xnu-10063.../RELEASE_ARM64_T6020 arm64
#              ^^^ the XNU build

sysctl kern.osrelease kern.version hw.optional.arm.FEAT_PAuth
#   FEAT_PAuth: 1     <- pointer authentication available

# launchd, PID 1, and the job it supervises:
launchctl list | head
launchctl print system/com.apple.example

# Mach ports held by a process (the IPC primitive, made visible):
lsmp -p $(pgrep -n Safari) | head
#   name      right   flags   boost  reqs  recv  send  ...
#   0x0000010b send    --------        ---     0     1  <- a capability

# Code signature and entitlements -- the sandbox is driven by these:
codesign -dv --entitlements :- /Applications/Safari.app 2>&1 | head -30
#   <key>com.apple.security.app-sandbox</key><true/>
#   <key>com.apple.security.network.client</key><true/>

# Memory compressor, not swap-to-flash (the iOS behaviour, visible here):
vm_stat | grep -i compress
#   Pages occupied by compressor:   412789
#   Pages stored in compressor:     998211    <- ~2.4x compression

# On-device app lifecycle and jetsam events are visible in the log:
log show --predicate 'subsystem == "com.apple.kernel"' --last 5m | grep -i jetsam

Key takeaways

• iOS runs XNU, a hybrid kernel combining a Mach core (tasks, threads, VM, ports) with a BSD layer (POSIX, processes, sockets, VFS) and IOKit drivers, all in one address space.
• The hybrid design provides Mach's modular structure without paying a microkernel's IPC cost on every service call.
• Mach ports are unforgeable, transferable capabilities carrying kernel-supplied credentials, converging on the same design conclusions as Binder from a different lineage.
• launchd is PID 1 and supervises all services with on-demand launching; GCD moves thread-pool management into the OS so energy and scheduling decisions can be made globally.
• Security is a chain anchored in an immutable Boot ROM: each boot stage verifies the next, and every executable page's signature is checked at page-in.
• Mandatory code signing means apps cannot obtain writable-executable memory, which removes the injection step most exploit chains depend on.
• The Secure Enclave is a separate coprocessor holding biometric templates and keys that the main CPU can use but never read.
• Data Protection encrypts files with keys tied to the passcode, so the strongest class is cryptographically unreadable while the device is locked.
• Memory pressure is handled with a kernel compressor and Jetsam terminations by priority band, the same no-swap strategy as Android with different names.
• Controlling both the hardware and the only distribution channel is what makes these restrictions enforceable, which is simultaneously the model's security advantage and its principal criticism.

🧪 Practice

1. Explain why XNU is called a hybrid kernel rather than a microkernel, and name one property it gains from each half.
2. Build the Android-versus-iOS comparison table from memory for kernel, IPC, runtime, app isolation, and memory reclaim, then check it against the table above.
3. Explain how mandatory code signing prevents a class of exploit that ASLR and DEP only make harder, and state what a JavaScript engine must do to run at all under that restriction.
4. Run codesign -dv --entitlements :- on a macOS application and interpret three of its entitlements in terms of what the sandbox will permit.
5. Interview-style: "Why is iOS generally considered harder to compromise than Android, and what does it give up for that?" Hint: list the assumptions each platform can make about the hardware it runs on and the channel through which software arrives.

---

<a id="15-case-studies-and-performance"></a>