Threads

The previous lesson measured that forking’s cost is the cost of isolation: pages were multiplied so that two processes could not touch each other’s memory. This opens a natural question. If parts of the same program want to touch each other’s memory, what is copying for.

The answer to this question is the thread: an execution unit that shares the address space but keeps its own stack. This lesson runs the same workload from the previous two lessons under two setups and places two numbers side by side — copied pages, and the time units context switching costs.

• PT16. A thread is an execution unit inside a process. It shares its address space with the process’s other threads and keeps its own stack separate.
• PT17. Every new thread requests 1 virtual page for its stack. This is a choice; if the page count grows, the thread’s extra cost grows with it.
• PT18. A process context switch also changes the address space, and takes 2 time units (the CONTEXT_COST value from the shared definition).
• PT19. In a thread context switch the address space stays the same; in this model its cost is 1 time unit. The result is sensitive to this choice, and the sensitivity is swept within the lesson.
• PT20. The workload, seed, and scheduler are the same as in the previous two lessons. The only thing that changes is how the units are set up; the work is the same work.
• PT21. The correctness consequences of a shared address space are not measured in this lesson. Race conditions and mutual exclusion are the concern of the course’s concurrency topic.
• PT22. The measurement’s resolution is 2 time units.

The Same Work, Two Setups

Five execution units will do the same work. In the process setup, each unit runs in its own address space and pays the forking cost from the previous lesson. In the thread setup, the five units run in a single address space; there is no page to copy, but each unit requests its own stack.

# This machine is a SIMULATOR. No real thread, lock, or concurrency library
# is called; all durations are time units in the model.
SEED = 20260218
PROCESS_COUNT = 5
STEP_COUNT = 12
WAIT_DURATION = 30
CONTEXT_COST = 2        # process context switch: the address space changes too
THREAD_CONTEXT_COST = 1     # thread context switch: the address space stays the same
VIRTUAL_PAGE = 16
STACK_PAGE = 1        # every thread needs one virtual page for its own stack


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()
TOUCHED = {i["name"]: {v for t, v in i["step"] if t == "COMPUTE"} for i in JOBS}
NEW = [i["name"] for i in JOBS[1:]]          # the four units besides the first
PROCESS_EAGER = len(NEW) * VIRTUAL_PAGE
PROCESS_COW = sum(len(TOUCHED[a]) for a in NEW)
THREAD = len(NEW) * STACK_PAGE
print("same work, three setups:", len(JOBS), "execution units,",
      len(set().union(*TOUCHED.values())), "distinct virtual pages")
print()
print("setup             address space  copied pages  extra stack pages  total extra pages")
print(f"  process (eager)  {len(JOBS):11d} {PROCESS_EAGER:17d} {0:17d} {PROCESS_EAGER:16d}")
print(f"  process (cow)    {len(JOBS):11d} {PROCESS_COW:17d} {0:17d} {PROCESS_COW:16d}")
print(f"  thread           {1:11d} {0:17d} {THREAD:17d} {THREAD:16d}")

same work, three setups: 5 execution units, 15 distinct virtual pages

setup             address space  copied pages  extra stack pages  total extra pages
  process (eager)            5                64                 0               64
  process (cow)              5                15                 0               15
  thread                     1                 0                 4                4

The difference on the memory side is sharp. Five processes need 15 extra virtual pages even in the best case; five threads need 4, and these are not copies of the address space but stack pages. No copy at all is made to reach shared data: the 15-virtual-page shared area sits as a single copy, and all five units see that same copy.

What It Keeps Separate, What It Shares

Why a thread’s context switch is cheaper can be seen by counting the state it carries. This course’s first lesson counted that the process table carries nine fields. Not all nine of those fields belong to the execution unit itself: some describe the unit’s own progress, and some describe the address space it sits in.

# On top of the first block: JOBS comes from there.
PER_UNIT = ("name", "position", "ready", "usage", "finish", "wait")   # unit-specific
SHARED_FIELDS = ("step", "arrival", "priority")                        # address-space level
n = len(JOBS)
process_fields = n * (len(PER_UNIT) + len(SHARED_FIELDS))
thread_fields = n * len(PER_UNIT) + len(SHARED_FIELDS)
print("unit-specific fields:", PER_UNIT)
print("shared fields       :", SHARED_FIELDS)
print()
print(f"process setup       : {n} entries x {len(PER_UNIT) + len(SHARED_FIELDS)} fields = {process_fields} fields")
print(f"thread setup        : {n} x {len(PER_UNIT)} + {len(SHARED_FIELDS)} = {thread_fields} fields")
print("field difference carried at a context switch:", process_fields - thread_fields,
      f"| {round(100 * (process_fields - thread_fields) / process_fields, 2)} percent reduction")

unit-specific fields: ('name', 'position', 'ready', 'usage', 'finish', 'wait')
shared fields       : ('step', 'arrival', 'priority')

process setup       : 5 entries x 9 fields = 45 fields
thread setup        : 5 x 6 + 3 = 33 fields
field difference carried at a context switch: 12 | 26.67 percent reduction

Six of the nine fields are unit-specific: its name, the step it is on, when it becomes ready to run, how much core it has used, when it finishes. Three are at the address-space level, and a single copy suffices. The process setup holds these three fields five times, the thread setup once; the total drops from 45 fields to 33, a 26.67 percent reduction.

This is the reason for the time difference in the next section. A context switch’s cost is proportional to the size of the state saved and restored; in a thread switch, the address-space-level fields stay in place, untouched.

Two Prices for a Context Switch

The time side is not as sharp as the memory side, and this is the actual thing the lesson needs to measure. The scheduler makes the same decisions in both setups; since the workload does not change, which unit runs when does not change either. The only thing that changes is the price of a switch.

# On top of the first block: JOBS, CONTEXT_COST, THREAD_CONTEXT_COST,
# PROCESS_COW and THREAD come from there.
INFINITY = 10**9


def schedule(jobs, policy="fifo", quantum=4, cores=1,
             context_cost=CONTEXT_COST):
    """policy: fifo (non-preemptive) | round-robin | priority | fair
    Every core runs at most one step per time unit."""
    state = [{"name": i["name"], "step": list(i["step"]), "position": 0, "arrival": i["arrival"],
              "ready": i["arrival"], "usage": 0, "finish": None,
              "priority": i["priority"]} for i in jobs]
    share_limit = INFINITY if policy == "fifo" else quantum
    cores_ = [{"job": None, "previous": None, "share": 0, "block": 0}
              for _ in range(cores)]
    t, context_switches, idle_steps = 0, 0, 0

    def not_done(d):
        return d["position"] < len(d["step"])

    while any(not_done(d) for d in state) or any(d["finish"] is None or d["finish"] > t
                                               for d in state):
        for c in cores_:                       # release
            d = c["job"]
            if d is not None and (not not_done(d) or d["ready"] > t or c["share"] >= share_limit):
                c["job"] = None
        for c in cores_:                       # assignment
            if c["block"] or c["job"] is not None:
                continue
            held = [x["job"] for x in cores_ if x["job"] is not None]
            ready = [d for d in state if not_done(d) and d["ready"] <= t and d not in held]
            if not ready:
                continue
            if policy == "priority":
                chosen = min(ready, key=lambda d: (-d["priority"], d["ready"], d["name"]))
            elif policy == "fair":
                chosen = min(ready, key=lambda d: (d["usage"], d["ready"], d["name"]))
            else:
                chosen = min(ready, key=lambda d: (d["ready"], d["name"]))
            if c["previous"] is not None and c["previous"] is not chosen:
                context_switches += 1
                c["block"] = context_cost
            c["job"] = chosen
            c["previous"] = chosen
            c["share"] = 0
        for c in cores_:                       # execution
            if c["block"]:
                c["block"] -= 1
                continue
            d = c["job"]
            if d is None:
                idle_steps += 1
                continue
            kind, value = d["step"][d["position"]]
            if kind == "WAIT":
                d["position"] += 1
                d["ready"] = t + value
                c["job"] = None
                idle_steps += 1
                if not not_done(d):                  # if the last step is a wait, the job finishes then
                    d["finish"] = t + value
            else:
                d["position"] += 1
                d["usage"] += 1
                d["ready"] = t + 1
                c["share"] += 1
                if not not_done(d):
                    d["finish"] = t + 1
                    c["job"] = None
        t += 1
    for d, i in zip(state, jobs):
        wt = sum(v for kind, v in i["step"] if kind == "WAIT")
        d["wait"] = d["finish"] - d["arrival"] - d["usage"] - wt
    return {"duration": t, "context_switches": context_switches, "idle_core_steps": idle_steps,
            "total_work": sum(d["usage"] for d in state),
            "avg_turnaround": round(sum(d["finish"] - d["arrival"] for d in state) / len(state), 2),
            "avg_wait": round(sum(d["wait"] for d in state) / len(state), 2),
            "finish": {d["name"]: d["finish"] for d in state}}


SETUPS = (("process", CONTEXT_COST, PROCESS_COW),
           ("thread", THREAD_CONTEXT_COST, THREAD),
           ("free baseline", 0, 0))
MEASURE = {name: schedule(JOBS, "fifo", context_cost=b) for name, b, _ in SETUPS}
print("setup            switch cost  switches  duration  avg.turnaround  extra pages")
for name, b, page in SETUPS:
    s = MEASURE[name]
    print(f"  {name:15s} {b:13d} {s['context_switches']:7d} {s['duration']:5d}"
          f" {s['avg_turnaround']:15.2f} {page:9d}")
proc, thread = MEASURE["process"], MEASURE["thread"]
print()
print("from process to thread")
print("  extra pages :", PROCESS_COW, "->", THREAD,
      f"| {round(100 * (PROCESS_COW - THREAD) / PROCESS_COW, 2)} percent reduction")
print("  duration    :", proc["duration"], "->", thread["duration"],
      f"| {round(100 * (proc['duration'] - thread['duration']) / proc['duration'], 2)} percent reduction")
print("  switches    :", proc["context_switches"], "->", thread["context_switches"], "| unchanged")
print()
print("context switch cost sensitivity")
print("cost  duration  avg.wait")
for b in range(5):
    s = schedule(JOBS, "fifo", context_cost=b)
    print(f"{b:5d} {s['duration']:5d} {s['avg_wait']:12.2f}")

setup            switch cost  switches  duration  avg.turnaround  extra pages
  process                     2      22   194          148.40        15
  thread                      1      22   186          142.80         4
  free baseline               0      22   178          137.20         0

from process to thread
  extra pages : 15 -> 4 | 73.33 percent reduction
  duration    : 194 -> 186 | 4.12 percent reduction
  switches    : 22 -> 22 | unchanged

context switch cost sensitivity
cost  duration  avg.wait
    0   178         3.40
    1   186         9.00
    2   194        14.60
    3   202        20.20
    4   211        26.80

The third row is the baseline: if context switching were free, this workload would finish in 178 time units. The 16 units between 194 and 178 are the steps sharing costs in the process setup, and it is exactly $22 \times 2$. The thread setup halves this item: 186, that is, the baseline plus $22 \times 1$.

The number of context switches does not change. Both setups have 22 switches, because the workload decides when a switch happens, not the type of the unit. Threads do not reduce switches; they make every switch cheaper.

Where the Gain Is, Where It Isn’t

The size of the gain differs sharply between the two sides. In memory, extra pages drop from 15 to 4, a 73.33 percent reduction. In time, duration drops from 194 to 186, a 4.12 percent reduction. Eight time units is above the resolution (2 units), so it is measured and real — but it is small next to the memory gain. A thread’s gain in this workload is not in time, it is in memory. The time gain grows only as the context-switch rate rises; the sweep shows this — once the cost climbs to 4, the same workload takes 211 time units.

The difference at setup time is larger than the difference during the run. By the previous lesson’s cost measure — copying one virtual page costs 1 time unit — setting up four processes takes 64 time units with the eager method and 15 with copy-on-write; setting up four threads takes 4 stack pages, that is, 4 time units. In short-lived units, the item that determines total cost is not the run but the setup, and there the ratio is 15 to 4.

The reason the gain stays small is the composition of the workload: 21 of the 60 steps are wait steps, and wait steps take 630 time units. The 44 units going to context switching stays small next to that magnitude. In a compute-heavy workload the ratio flips, and a thread’s time gain becomes pronounced.

The Other Side of Sharing

There is an item that does not appear in the table, and it has to be written down for the lesson to be honest. In the process setup, the five units cannot see each other’s memory; in the thread setup, all five see and can modify the entire 15-virtual-page shared area. The way to avoid copying runs through making the copy unnecessary — that is, through removing isolation.

Separate stacks do not limit this visibility. Stack separation prevents two units from accidentally overwriting each other’s local variables; it does not protect data in the shared area. The shared area is there precisely to be shared, and the thread setup’s entire gain comes from it; the thing that needs protecting and the source of the gain are the same 15 pages.

This is not an extra page cost; it is a correctness cost, and it cannot be measured in pages. The problem that arises when two units write to the same page at the same time is addressed on its own terms in this course’s concurrency topic. This topic’s next lesson counts the other end of the trade-off: how many units a single step that corrupts shared state affects.

Summary

• A thread is an execution unit that shares its address space with the process’s other threads and keeps its own stack separate.
• The same five-unit job needs 15 extra virtual pages when set up with processes, even with copy-on-write; 4 stack pages suffice with threads, a 73.33 percent reduction.
• The number of context switches is 22 in both setups; the type of unit changes not the switch count but the switch’s price.
• Duration drops from 194 to 186 time units. The 8-unit difference is above the resolution and is measured; but it is 4.12 percent, small next to the memory gain.
• The cost sweep shows the result depends on a choice: duration is 178 at a context cost of 0 and 211 at a cost of 4.
• Sharing has a cost that cannot be measured in pages: five threads see the entire shared area, and isolation disappears.

Next Step

There are now two setups and two numbers in hand: threads want fewer pages and a bit less time, while processes give isolation. To make a choice, isolation needs a number of its own. The next lesson produces that number: it measures how many execution units a single step that corrupts shared state spreads to, and sets that against how many pages isolation costs.