--- title: 'The Process Concept' source: 'https://academia.sh/en/courses/operating-system-concepts/process-concept' course: 'Operating System Concepts' language: en updated: '2026-08-17T18:08:21+00:00' license: 'CC BY-SA 4.0' --- # The Process Concept A process as a running instance of a program, and the steps that sharing costs: a process running alone takes 99 time units, but when five processes share the same machine the result is 194 time units and 22 context switches; 44 of those 194 time units go to context switching, which is more than the 39 time units spent on the work itself. The Algorithms course closed by measuring a solution's cost by **its own step count**: comparison count, edges traversed, characters scanned. That measure carried a silent assumption — that the algorithm has the machine to itself. This assumption does not hold in production. The same algorithm runs on the same machine alongside other work, sharing the processor, memory, and disk with it. What this course measures is **sharing itself**. An abstraction's number is not the convenience it provides but **the steps it costs**; an abstraction whose cost is not counted counts as unmeasured. The first abstraction is the process, and the first cost is the steps a processor spends moving back and forth between multiple processes. - **PT1.** The machine is modeled within the lesson. The code below is a **simulator**: no real process is created, no kernel call is made, no real time is measured. - **PT2.** All durations are **time units**. They are not seconds, and are not converted to seconds. - **PT3.** The workload is **five processes**; each process has **twelve steps**. A step is either a **compute step** (takes one time unit, touches one virtual page) or a **wait step** (takes 30 time units, does not use the core). - **PT4.** The seed is **20260218**. The same seed gives the same workload; every number here is reproducible. - **PT5.** The machine has **a single core**. In every time unit, the core executes at most one step. - **PT6.** **The cost of a context switch is 2 time units.** During those two units, the core executes no process's step at all. - **PT7.** Address space, stack, and heap were established in the memory layout lesson of the How Computers Work course; they are **not redefined** here, only counted. - **PT8.** The measurement's **resolution is 2 time units**. A 1-unit difference between two setups **counts as unmeasured**. ## Process: A Running Program A program is a sequence of bytes sitting on disk; a **process** is a running instance of that program. The difference is that a process has something the program does not: **state**. A process's state covers the counter of the step it is on, the current content of its stack, the descriptors it holds open, and its own address space. This state has to be kept somewhere, because when the processor leaves one process for another and later returns, it must resume from **exactly** where it left off. The structure that holds this state is the **process table**: one entry per process, and in each entry the fields needed to resume the process. When two processes are run from the same program, what results is two separate states. Both execute the same instructions, but at different steps, with different data, and without touching each other's memory. This separation is **isolation**, and its cost will be counted in later lessons of this course. A **multitasking operating system** gives the impression that multiple processes are advancing at the same time, even on a single-core machine. The source of that impression is the core switching between processes often enough. From a process's point of view these switches are invisible: it is written as if it executed its own steps without interruption. Measurement breaks this impression, because every switch takes up room on the core and adds to the total duration. ## The Modeled Workload The first block builds the workload. A process is represented as a list of steps; compute steps hold the core, wait steps do not. ```python # This machine is a SIMULATOR. There is no real process, kernel call, or # time measurement; all durations are time units in the model. SEED = 20260218 PROCESS_COUNT = 5 STEP_COUNT = 12 WAIT_DURATION = 30 # how many time units an I/O step takes CONTEXT_COST = 2 # the cost of one context switch (time units) 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() print("process arrival priority compute wait time alone") for i in JOBS: h = sum(1 for t, _ in i["step"] if t == "COMPUTE") b = STEP_COUNT - h print(f" {i['name']:4s} {i['arrival']:5d} {i['priority']:8d} {h:6d} {b:8d}" f" {h + b * WAIT_DURATION:15d}") print("total compute steps:", sum(1 for i in JOBS for t, _ in i["step"] if t == "COMPUTE")) ``` ``` process arrival priority compute wait time alone P1 0 3 9 3 99 P2 4 2 9 3 99 P3 8 1 7 5 157 P4 12 3 7 5 157 P5 16 2 7 5 157 total compute steps: 39 ``` The last column is the **baseline**: how long a process would take if it were alone on the machine. For P1 this is $9 + 3 \times 30 = 99$ time units. The number is the sum of the process's own steps and depends on nothing else. This is exactly the measure used in the Algorithms course. ## Sharing Itself Is Work When five processes use the same core, the core has to make a choice: which one runs. The component that makes this choice is the **scheduler**. The implementation below will be used in every scheduling measurement in this course; here it runs only in **non-preemptive FIFO** mode, meaning a process does not give up the core until it either finishes or enters a wait step. ```python # On top of the first block: JOBS, CONTEXT_COST and STEP_COUNT 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}} ALONE = [schedule([dict(i, arrival=0)], "fifo") for i in JOBS] SHARED = schedule(JOBS, "fifo") print("baseline (five processes back to back, no sharing at all):", sum(s["duration"] for s in ALONE), "time units,", sum(s["context_switches"] for s in ALONE), "context switches") print("setup (five processes sharing the same machine) :", SHARED["duration"], "time units,", SHARED["context_switches"], "context switches") print() print("process alone shared difference") for i, s in zip(JOBS, ALONE): p = SHARED["finish"][i["name"]] - i["arrival"] print(f" {i['name']:4s} {s['duration']:10d} {p:11d} {p - s['duration']:5d}") print("average turnaround:", SHARED["avg_turnaround"], "| average wait:", SHARED["avg_wait"]) ``` ``` baseline (five processes back to back, no sharing at all): 669 time units, 0 context switches setup (five processes sharing the same machine) : 194 time units, 22 context switches process alone shared difference P1 99 103 4 P2 99 112 13 P3 157 176 19 P4 157 173 16 P5 157 178 21 average turnaround: 148.4 | average wait: 14.6 ``` Two numbers are true at the same time and point in opposite directions. **Total duration drops:** running the five processes back to back with no interleaving at all takes 669 time units, while the shared run finishes at 194. The gain comes from handing the core to another process while one is waiting. **Individual duration rises:** no process reaches its own baseline; the baseline of 157 for P5 rises to 178. The difference averages **14.60 time units per process**, and this is time a process spends on other processes' work, not its own. ## A Process's Three States The difference column above leaves a question: what is a process doing in those extra time units when it is not doing its own work. The answer is that a process is, at every moment, in one of three states. **Running** is the state where the process currently holds the core. **Blocked** is the state where the process is in a wait step and cannot run even if the core is idle. **Ready** is the state where the process is able to run but the core belongs to someone else. ```python # On top of the previous blocks: JOBS, SHARED and WAIT_DURATION come from there. print("process running blocked ready(queued) turnaround") total_ready = 0 for i in JOBS: running = sum(1 for t, _ in i["step"] if t == "COMPUTE") blocked = sum(v for t, v in i["step"] if t == "WAIT") turnaround = SHARED["finish"][i["name"]] - i["arrival"] ready = turnaround - running - blocked total_ready += ready print(f" {i['name']:4s} {running:10d} {blocked:12d} {ready:16d} {turnaround:11d}") print("average ready time:", round(total_ready / len(JOBS), 2)) ``` ``` process running blocked ready(queued) turnaround P1 9 90 4 103 P2 9 90 13 112 P3 7 150 19 176 P4 7 150 16 173 P5 7 150 21 178 average ready time: 14.6 ``` The first two columns belong to the baseline and are unaffected by sharing: both a process's compute step count and its wait duration are properties of its own program. The column sharing produces is the third one. Ready time is zero by definition for a process running alone; once five processes share, it rises to a value between 4 and 21, averaging **14.60 time units**. This is the **process-visible** form of the steps the process abstraction costs. The process itself sees neither the context switches nor the process table; the only thing it sees is its own execution pausing to wait now and then. P1's ready time is 4, P5's is 21; the difference comes from arrival order, and **arriving early means waiting less**. That this order is a choice, and that different choices produce different ready times, will be measured in this topic's lesson on scheduling. ## The Breakdown of the 194 Time Units To see where the cost lies, the total duration has to be broken into its components. The process table itself is also counted here; its definition belongs to the How Computers Work course, and the question here is how many fields it carries. ```python # On top of the first two blocks: JOBS, SHARED and CONTEXT_COST come from there. FIELD = ("name", "step", "position", "arrival", "ready", "usage", "finish", "priority", "wait") print("process table:", len(JOBS), "entries x", len(FIELD), "fields =", len(JOBS) * len(FIELD), "fields") print() work_steps = SHARED["total_work"] context_steps = SHARED["context_switches"] * CONTEXT_COST print("breakdown of the 194 time units") print(" compute steps :", work_steps) print(" context switches :", context_steps, f"({SHARED['context_switches']} x {CONTEXT_COST})") print(" idle core steps :", SHARED["idle_core_steps"]) print(" total :", work_steps + context_steps + SHARED["idle_core_steps"]) print(" context / compute ratio:", round(context_steps / work_steps, 4)) ``` ``` process table: 5 entries x 9 fields = 45 fields breakdown of the 194 time units compute steps : 39 context switches : 44 (22 x 2) idle core steps : 111 total : 194 context / compute ratio: 1.1282 ``` This lesson's most important line is the second to last. The five processes' **actual work is 39 time units**; the **context switching** spent to get that work done is **44 time units**. The steps the abstraction costs are **larger** than the steps it carries — the ratio is 1.1282. The remaining 111 units are idle core steps: while every process is in a wait step, the core has no work to do. This is not a flaw of the scheduler; the workload's 21 wait steps take 630 time units in total, and only a portion of that can be interleaved. The way to reduce idle steps is not a better scheduler but **more processes** — and every new process also increases the number of context switches. The process table's 45 fields are why context switching is not free: at every switch, one entry's fields are saved and another's are restored. This course's counter models those two operations as 2 time units. ## Summary - A process is a running instance of a program; what distinguishes it from the program is the state it carries, and that state is held in the process table. - In this workload, a process running alone takes exactly as long as its own steps: 99 time units for P1, 157 for P3. This is the baseline. - When five processes share the same machine, the total duration drops from 669 to **194 time units**, but no process's individual duration reaches its baseline; the average wait is **14.60 time units**. - The cost of sharing is **22 context switches**, taking 44 time units; this is **more** than the workload's actual work of 39 time units. - A process is at every moment running, blocked, or ready; the only new state sharing produces is **ready**, and in this workload it averages 14.60 time units. - The 194 time units break down exactly into 39 compute steps, 44 context-switch units, and 111 idle core steps; every abstraction's cost is visible in this breakdown. ## Next Step This lesson supplied five processes ready-made. On a real machine, processes do not spring from nothing: each is created by another process and inherits things from its creator at the moment of creation. The next lesson takes up forking and counts a single question: setting up a new process means **copying how many pages**.