Choosing Between Processes and Threads

The previous lesson placed two setups side by side and measured that threads are cheap: 4 extra virtual pages instead of 15, 186 time units instead of 194. Choosing threads by looking only at these numbers would mean ignoring a column that is not in the table. What the process setup gave in return was isolation, and no choice can be made until isolation, too, has a number.

This lesson produces that number. The question is: how many execution units does a single step that corrupts shared state affect. The answer differs between the two setups by a factor of five, and this is this topic’s counterpart to the course’s second claim — an abstraction sometimes makes things worse, because the cheapness of sharing also means corruption spreads cheaply.

• PT23. Five execution units run the same workload used in the previous two lessons. Each unit touches specific virtual pages; the touch set is read from the workload’s compute steps.
• PT24. Corruption is a unit writing an incorrect value to a page. It is a single step, and it happens once over the course of the measurement.
• PT25. Direct impact is the number of units that touch the corrupted page.
• PT26. Spread is the number of units the corruption reaches through shared pages: a unit that reads the corrupted data also writes a corrupted value to its own pages. This is a modeling choice, and it is in the pessimistic direction.
• PT27. Units in the same address space are considered linked through a shared page. Spread is the connected component of this graph.
• PT28. There is no edge between units in separate address spaces. This is the definition of isolation: one process’s write cannot reach another’s page.
• PT29. The component computation uses directly the traversal established in the Data Structures course’s lesson on depth-first search; the procedure is not retold here.
• PT30. Time is not measured in this lesson. The two quantities measured are affected units and copied pages.

The Two Ends of the Trade-off

At one end is total sharing: five units run in a single address space, no page is copied, every unit sees every page. At the other end is total isolation: five separate address spaces, four forks, copied pages, and units that cannot touch each other’s memory.

There is no continuous range between these two ends; the number of address spaces is an integer, and the choice is how many address spaces the units are divided among. The five units can be set up in one, two, three, or five spaces. Every division produces two numbers, and these two numbers move in opposite directions.

The term trade-off is not used loosely here. Both quantities arise from the same cause: avoiding a copy also means avoiding the separation the copy provides. There is no way to have both in a single setup, and every number in this lesson is read within that constraint.

The Shared Page Map

The measurement requires knowing which unit touches which page. The workload already determines this; the first block produces the map.

# This machine is a SIMULATOR. No real process or thread is created;
# all numbers are produced inside the model.
SEED = 20260218
PROCESS_COUNT = 5
STEP_COUNT = 12
WAIT_DURATION = 30
VIRTUAL_PAGE = 16


def generator(seed):
    """Deterministic pseudo-random generator. The same seed gives the same sequence."""
    d = seed

    def advance(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return advance


def workload(seed=SEED):
    """A step is either ("COMPUTE", virtual_page) or ("WAIT", duration)."""
    r = generator(seed)
    jobs = []
    for i in range(PROCESS_COUNT):
        steps = []
        for _ in range(STEP_COUNT):
            if r(10) < 3:
                steps.append(("WAIT", WAIT_DURATION))
            else:
                base = (i * 3) % VIRTUAL_PAGE
                steps.append(("COMPUTE", (base + r(4)) % VIRTUAL_PAGE))
        jobs.append({"name": f"P{i+1}", "step": steps,
                      "priority": 1 + r(3), "arrival": i * 4})
    return jobs


JOBS = workload()
NAMES = [i["name"] for i in JOBS]
TOUCHED = {i["name"]: {v for t, v in i["step"] if t == "COMPUTE"} for i in JOBS}
print("unit  virtual pages touched  count")
for a in NAMES:
    print(f"  {a:4s} {str(sorted(TOUCHED[a])):22s} {len(TOUCHED[a]):4d}")
print("distinct pages:", len(set().union(*TOUCHED.values())))
print()
print("page  units touching it")
for s in range(VIRTUAL_PAGE):
    touching = [a for a in NAMES if s in TOUCHED[a]]
    if len(touching) >= 2:
        print(f"{s:5d}  {' '.join(touching)}")

unit  virtual pages touched  count
  P1   [0, 1, 2, 3]              4
  P2   [3, 4, 5, 6]              4
  P3   [6, 7, 8, 9]              4
  P4   [9, 11, 12]               3
  P5   [12, 13, 14, 15]          4
distinct pages: 15

page  units touching it
    3  P1 P2
    6  P2 P3
    9  P3 P4
   12  P4 P5

The map looks narrow: only four of the 15 pages are used by more than one unit, and none is used by more than two. Looking only at direct impact, sharing’s risk seems small — two units in the worst case.

How Far Corruption Spreads

Direct impact is misleading, because corruption does not stop there. P1 and P2 share page 3, P2 and P3 share page 6, P3 and P4 share page 9, P4 and P5 share page 12. Four shared pages build a chain linking all five units end to end.

# On top of the first block: NAMES, TOUCHED and VIRTUAL_PAGE come from there.


def component(group):
    """Units in the same address space are linked through shared pages.
    The set corruption spreads to is this graph's connected component."""
    neighbor = {a: [b for b in group if b != a and TOUCHED[a] & TOUCHED[b]] for a in group}
    seen, comps = set(), []
    for a in group:
        if a in seen:
            continue
        stack, cluster = [a], []
        while stack:                                  # depth-first search
            d = stack.pop()
            if d in seen:
                continue
            seen.add(d)
            cluster.append(d)
            stack.extend(neighbor[d])
        comps.append(sorted(cluster))
    return comps


def setup(groups):
    """groups: each one a set of unit names sharing one address space."""
    comps = [b for g in groups for b in component(g)]
    eager = (len(groups) - 1) * VIRTUAL_PAGE
    cow = sum(len(set().union(*(TOUCHED[a] for a in g))) for g in groups[1:])
    return {"address_spaces": len(groups), "components": len(comps),
            "largest_component": max(len(b) for b in comps),
            "eager": eager, "cow": cow}


PARTITIONS = [[NAMES], [NAMES[:3], NAMES[3:]], [NAMES[:2], NAMES[2:4], NAMES[4:]],
           [[a] for a in NAMES]]
print("address spaces  components  largest component  eager copy  cow copy")
for g in PARTITIONS:
    k = setup(g)
    print(f"{k['address_spaces']:11d} {k['components']:8d} {k['largest_component']:17d}"
          f" {k['eager']:14d} {k['cow']:15d}")
print("component in a single address space:", component(NAMES))

address spaces  components  largest component  eager copy  cow copy
          1        1                 5              0               0
          2        2                 3             16               6
          3        3                 2             32              10
          5        5                 1             64              15
component in a single address space: [['P1', 'P2', 'P3', 'P4', 'P5']]

The last line is this lesson’s core. In a single address space, the five units form a single component; even though no pair of units shares a page directly, all of them are linked through the chain. P1 and P5 have no page in common at all, but a value P1 corrupts reaches P3 through P2, P4 through P3, and from there P5.

The Effect of a Single Step

Counting the spread page by page makes the difference between direct impact and spread visible.

# On top of the previous blocks: NAMES, TOUCHED, VIRTUAL_PAGE and component.
SPREAD = {a: b for b in component(NAMES) for a in b}
print("corrupted page  process model  thread direct  thread spread")
totals = [0, 0, 0]
for s in sorted(set().union(*TOUCHED.values())):
    touching = [a for a in NAMES if s in TOUCHED[a]]
    spread = len({b for a in touching for b in SPREAD[a]})
    totals = [totals[0] + 1, totals[1] + len(touching), totals[2] + spread]
    print(f"{s:15d} {1:14d} {len(touching):15d} {spread:14d}")
print("totals over 15 pages:", totals[0], "|", totals[1], "|", totals[2])
print("spread / process model ratio:", round(totals[2] / totals[0], 4))

corrupted page  process model  thread direct  thread spread
              0              1               1              5
              1              1               1              5
              2              1               1              5
              3              1               2              5
              4              1               1              5
              5              1               1              5
              6              1               2              5
              7              1               1              5
              8              1               1              5
              9              1               2              5
             11              1               1              5
             12              1               2              5
             13              1               1              5
             14              1               1              5
             15              1               1              5
totals over 15 pages: 15 | 19 | 75
spread / process model ratio: 5.0

The last column is 5 no matter which page is corrupted. Where the corruption starts does not matter; in a single address space, every path leads everywhere. In the process model the same column is a constant 1, because there is no edge. The spread ratio is 5.0, and this is exactly the unit count.

Direct impact totals 19, spread totals 75. The 56-unit-page gap between them is exactly the risk that an analysis looking only at the narrow-looking map would miss. Reducing the number of shared pages does not close this gap; the chain has to be cut, and the only way to cut the chain is a separate address space.

A crash is this table’s extreme case. If a thread makes the address space unusable, the affected units are directly 5; there is no intermediate step. If a process does the same thing, it is 1, and the remaining four units keep running. What isolation buys is exactly this difference: the difference between four out of five units staying up and none of them staying up.

Taking Isolation Partially

The partition table’s two columns move in opposite directions and form a curve. As the address space count rises from 1 to 5, the largest component drops from 5 to 1; copied pages rise from 0 to 15 (from 0 to 64 with the eager method). The intermediate points show this exchange does not have to be taken all at once: two address spaces bring the largest component down from 5 to 3 with 6 copied pages. The first 6 copied pages reduce spread by two units; the last 5 copied pages reduce it by only one. Isolation’s first unit is cheaper than its last.

This means the choice is not “all or nothing.” A group of units that trust each other can share a single address space, and an untrusted group can be placed in a separate one. What decides where the partition falls is not the shared page map but which corruption is acceptable.

Cutting the Chain Cheaply

The partition table changes the address space count. There is a cheaper path: keep a single address space, and multiply only the shared pages. Since it is four pages that build the chain, is cutting them enough.

# On top of the previous blocks: NAMES, TOUCHED and VIRTUAL_PAGE.
SHARED = [s for s in range(VIRTUAL_PAGE) if sum(1 for a in NAMES if s in TOUCHED[a]) >= 2]


def cut_components(cut):
    """A cut page is copied per unit; it no longer forms an edge."""
    remaining = {a: TOUCHED[a] - set(cut) for a in NAMES}
    neighbor = {a: [b for b in NAMES if b != a and remaining[a] & remaining[b]] for a in NAMES}
    seen, clusters = set(), []
    for a in NAMES:
        if a in seen:
            continue
        stack, cluster = [a], []
        while stack:
            d = stack.pop()
            if d in seen:
                continue
            seen.add(d)
            cluster.append(d)
            stack.extend(neighbor[d])
        clusters.append(sorted(cluster))
    return clusters


print("shared pages:", SHARED)
print()
print("cut pages      extra copies  components  largest component")
for k in range(len(SHARED) + 1):
    b = cut_components(SHARED[:k])
    print(f"{str(SHARED[:k]):14s} {k:9d} {len(b):8d} {max(len(x) for x in b):17d}")
print()
print("separate-address-space cost for the same result:",
      sum(len(TOUCHED[a]) for a in NAMES[1:]), "copied pages")

shared pages: [3, 6, 9, 12]

cut pages      extra copies  components  largest component
[]                     0        1                 5
[3]                    1        2                 4
[3, 6]                 2        3                 3
[3, 6, 9]              3        4                 2
[3, 6, 9, 12]          4        5                 1

separate-address-space cost for the same result: 15 copied pages

The number is striking: 4 copied pages reach the same result that separate address spaces reached with 15. Every cut page shrinks the largest component by exactly one unit, and on the fourth cut the component count rises to 5.

This cheapness has three conditions, and all three must be written down. First, the map must be known in advance; which page is shared can only be stated once the entire workload is known. Second, the cut is not enforced by hardware; if a unit mistakenly writes to an uncut page, the chain returns. Third, a cut page is no longer shared — in a design that communicates through shared data, cutting breaks the work.

The separate address space’s 15 pages buy exactly these three conditions: no map is needed, the rule is enforced by hardware, and it cannot be broken by mistake. Isolation’s 11 extra pages are a price paid to a mechanism, not to knowledge or care.

The Selection Rule

When three numbers are placed side by side, the rule writes itself. The baseline is a single unit in a single address space: 0 copied pages, 1 affected unit, no spread. The setup is five units running in one address space: still 0 copied pages, but 1 component and a spread of 5. The cost is the 15 copied pages paid to bring that spread down to 1 — 64 with the eager method.

The decision looks at the nature of the work. If the units continuously share the same data, separate address spaces cut the sharing too, and the work becomes impossible; in that case threads are unavoidable, and protection has to be sought at another layer. If the units do independent work, 15 pages is a cheap price for bringing spread down to a fifth. The previous lesson’s time gain of 8 time units is a small item next to this table; choosing threads for their speed is the weakest reason measured here.

Summary

• The choice between isolation and sharing is the question of how many address spaces the units are divided among, and it produces two numbers: copied pages and affected units.
• In this workload only four of the 15 virtual pages are used by more than one unit; direct impact is 2 in the worst case.
• Four shared pages chain the five units together: in a single address space the component count is 1, and spread is 5 no matter which page is corrupted. The spread ratio is 5.0.
• In a process setup the same corruption stays confined to 1 unit; this is the difference isolation buys, at a cost of 15 copied pages (64 with the eager method).
• Partial isolation works, and it is not linear: two address spaces bring the largest component from 5 to 3 with 6 pages, while the last 5 pages gain only 1 unit.
• A thread’s time gain of 8 time units is small next to this trade-off; the choice cannot be defended on speed.

Next Step

Up to here, the question was how the units are set up: how many address spaces, how many copied pages, how many affected units. Once setup is done, one question remains, and it has to be asked again at every time unit: which of the ready units will run. The next lesson takes up the scheduler that makes this decision, runs the same workload under four separate policies, and shows that none of them is best under every workload.