Two threads belong to the same process. Which of the following are shared between them?

The table of open file descriptors

For the same four processes — arrivals 0, 1, 2, 3 and bursts 8, 4, 9, 5 — the average waiting times are 6.5 under SRTF, 7.75 under non-preemptive SJF, 8.75 under FCFS and 11.75 under round robin with quantum 4. Which conclusion is correct?

Round robin loses on average waiting time because it is optimising bounded response time instead

Round robin is a poor scheduler and should not be used in practice

Round robin loses on average waiting time because it is optimising bounded response time instead

A larger quantum would make round robin beat SRTF on average waiting time

The ordering would reverse if the bursts were all equal

In a process using user-level threads, one thread issues a blocking `read` system call. What happens to the other threads of that process?

They are all blocked, because the kernel sees only one schedulable entity

They continue to run, since only the calling thread is waiting

They are all blocked, because the kernel sees only one schedulable entity

They are migrated to another CPU by the thread library

They continue only if the process has more than one kernel thread

Round robin scheduling with a quantum larger than every process’s CPU burst behaves identically to:

Priority scheduling with ageing

On the same four processes (arrivals 0, 1, 2, 3; bursts 8, 4, 9, 5), FCFS gives an average waiting time of 8.75 while non-preemptive SJF gives 7.75. The 1.0 difference comes from:

SJF running P4 before P3 at time 12, moving 9 units of waiting off P4 onto P3

SJF preempting P1 when P2 arrives at time 1

SJF running P4 before P3 at time 12, moving 9 units of waiting off P4 onto P3

SJF having a lower context-switch cost

System Calls, Processes, Threads and CPU Scheduling

Section 8 of the Computer Science paper. An operating system is best understood as the answer to one question: a program cannot be trusted with the hardware, so what does it do when it needs the hardware? It asks. A system call is that request — the single controlled doorway from user mode into kernel mode — and it is the item the syllabus revision added, so it is worth knowing precisely: a system call is not a function call, it is a mode switch, and that is why it costs orders of magnitude more. Above that doorway sit two abstractions the questions never stop distinguishing. A process is a program plus its own address space; a thread is a flow of control inside one address space. From that one difference everything examinable follows — what is shared, what is private, what a fork costs, and why a blocking call behaves differently for a user-level thread than for a kernel-level one. Then scheduling, which is where the arithmetic lives. Four algorithms, one question shape: given arrival and burst times, compute average waiting time. The reliable way through it is to draw the Gantt chart and read the numbers off, because waiting time = turnaround time − burst time is an identity you can apply mechanically once completion times are known. And one fact is worth carrying in before any calculation: shortest-remaining-time-first minimises average waiting time, provably, so if an option claims some other algorithm beat it on the same input, the arithmetic is wrong somewhere.

The Doorway: What a System Call Actually Costs

User code runs in user mode, where the privileged instructions — talk to a device, change the page tables, halt the processor — are simply unavailable. A system call is the one legitimate way across: the program puts a call number and its arguments where the convention says, executes a trap instruction, and the hardware switches to kernel mode and jumps to a fixed handler. The kernel then validates every argument, because the caller is not trusted, does the work, and returns. Read open, read, write, fork, exec, wait and exit as system calls; read printf as a library function that eventually makes one. That distinction is examined directly, and the reason it matters is cost: an ordinary function call is a jump, while a system call is a mode switch with argument validation on the other side.

🧠 Counting the processes a chain of forks creates

fork() returns twice: the child gets 0 and the parent gets the child’s PID, and that single asymmetry is the whole basis of the code that follows a fork. The counting question falls out of it. After n unconditional forks in a row, every existing process forks at every step, so the population doubles each time: 2ⁿ processes exist in total and 2ⁿ − 1 of them are new. Three forks therefore give 8 processes and 7 children — not 3, and not 4. The trap is a fork inside an if (fork() == 0), where only one branch continues forking, and then the doubling stops and you have to draw the tree. Draw it; the doubling formula is only valid when the forks are unconditional.

ℹ️ The five process states, and the one transition that is not the process’s choice

New, ready, running, blocked (waiting) and terminated. Only one process per CPU is running; ready means runnable but not chosen; blocked means not runnable, waiting on I/O or an event. Three transitions are the process’s own doing — ready → running when the scheduler picks it, running → blocked when it asks for something, blocked → ready when that something arrives. The fourth is not: running → ready is preemption, done to the process by the scheduler on a timer interrupt, and it is the transition that separates a preemptive algorithm from a non-preemptive one. Note what is missing from the list: blocked → running does not exist. A process that finishes waiting goes to the ready queue and waits its turn like everything else, and options claiming otherwise are a standard distractor.

Threads: One Address Space, Several Flows

What threads of one process share, and what each keeps to itself
Resource	Shared or private?	Why it has to be that way
Code (text) segment	Shared	One program; threads run different parts of the same instructions
Global and heap data	Shared	The reason threads are cheap to communicate with — and the reason they need locks
Open files, signal handlers	Shared	They are process-level resources, not per-flow
Stack	Private	Each flow has its own call chain and its own locals
Registers, program counter	Private	Each flow is at a different instruction — that is what makes it a flow

⚠️ A user-level thread that blocks blocks everybody

The examinable difference between user-level and kernel-level threads is not speed, it is what the kernel can see. User-level threads are scheduled by a library inside the process, so the kernel sees one schedulable entity. Two consequences follow, and they are opposite in sign. Switching between them is very cheap — no mode switch, just a register swap in user space. But when one of them makes a blocking system call, the kernel blocks the only thing it knows about, which is the whole process, so every other thread stops even though they were perfectly runnable. Kernel-level threads are each visible and separately schedulable, so a block affects only the caller and a multiprocessor can run several at once, at the cost of a mode switch per switch. User-level threads cannot exploit multiple CPUs for the same reason: one schedulable entity gets one CPU.

Four Algorithms, One Process Set, Computed

The comparison below runs one process set through all four algorithms, because four separate examples teach nothing about the ordering. Take P1(arrival 0, burst 8), P2(1, 4), P3(2, 9), P4(3, 5). Build the Gantt chart, read off each completion time, then apply the two identities: turnaround = completion − arrival and waiting = turnaround − burst. Nothing here needs to be remembered — it needs to be run, and run in that order, because trying to reason about waiting time directly is where the arithmetic goes wrong.

P1(0,8) P2(1,4) P3(2,9) P4(3,5) — average waiting time under each algorithm
Algorithm	Completion times	Avg waiting	Avg turnaround
SRTF (preemptive SJF)	17, 5, 26, 10	6.5	13
SJF, non-preemptive	8, 12, 26, 17	7.75	14.25
FCFS	8, 12, 21, 26	8.75	15.25
Round robin, quantum 4	20, 8, 26, 25	11.75	18.25

🎯 Why SRTF wins, and what round robin is buying with its 11.75

The ordering 6.5 < 7.75 < 8.75 < 11.75 is not an accident of this input. SRTF is provably optimal for average waiting time: running the job with the least remaining work first means every unit of time you spend is the unit that finishes something soonest, and any swap towards a longer job increases the total. Non-preemptive SJF is the same idea with its hands tied — it cannot interrupt P1 when the shorter P2 arrives at time 1, so it loses 1.25. FCFS loses more, and the reason has a name: the convoy effect, where one long job at the head makes every short job behind it wait its full length. And round robin is worst on this metric while being the one you would actually deploy, which is the real lesson: it is not optimising average waiting time at all, it is optimising response time — the wait before a job first runs, which round robin bounds at (n−1)q while SJF leaves it unbounded. A short interactive job under FCFS behind a 9-unit batch job waits 9 units to say anything. Under round robin it waits at most 12 and then runs every cycle. Choosing a scheduler means choosing which number you refuse to let get large.

⚠️ Round robin’s quantum has two degenerate ends

Both limits are asked, and both are worth deriving rather than recalling. As the quantum grows past the longest burst, nobody is ever preempted and round robin becomes FCFS. As the quantum shrinks towards zero, the switching cost dominates: with quantum q and context-switch cost s, the fraction of the CPU doing useful work is q/(q+s), so a tiny quantum spends almost all of the processor on switching — the behaviour sometimes called processor sharing, and in practice thrashing the scheduler. This is why the question “which quantum minimises average waiting time?” has the unhelpful honest answer the largest one, and why real systems pick the quantum from a response-time target instead.

The Other Half: Scheduling the Disk

The syllabus item is CPU and I/O scheduling, and the second half is a different problem with the same shape. A disk request costs mostly seek time, the head’s travel, so the scheduler minimises total head movement rather than waiting time — and the metric is cylinders traversed, which you count off the request order exactly as you counted a Gantt chart. One example, computed for all six algorithms: head at cylinder 53, disk 0 to 199, pending requests 98, 183, 37, 122, 14, 124, 65, 67.

Head at 53, requests 98 183 37 122 14 124 65 67 — total cylinders traversed
Algorithm	Service order	Movement
FCFS	98, 183, 37, 122, 14, 124, 65, 67	640
SSTF	65, 67, 37, 14, 98, 122, 124, 183	236 — the least here
SCAN (to 199, then reverse)	65, 67, 98, 122, 124, 183, 199, 37, 14	331
C-SCAN (to 199, jump to 0)	65, 67, 98, 122, 124, 183, 199, 0, 14, 37	382
LOOK (turn at the last request)	65, 67, 98, 122, 124, 183, 37, 14	299
C-LOOK	65, 67, 98, 122, 124, 183, 14, 37	322

🎯 SSTF wins by 63% and is still not what a disk uses

SSTF cuts FCFS’s 640 cylinders to 236, a 63% saving, and the reason it is nonetheless rejected is the same reason SJF is rejected for the CPU: greedy on distance means starvation. A steady stream of requests near the current head position can keep the head in that neighbourhood indefinitely while a request at cylinder 183 waits without bound. SCAN fixes it structurally rather than by tuning: the head sweeps in one direction servicing everything on the way, so a request’s wait is bounded by one full sweep no matter where it is. That bound is what the extra 95 cylinders buy. C-SCAN goes further and returns to the start without servicing anything, which costs still more here (382), and it buys something specific — under plain SCAN the cylinders in the middle get visited twice per round trip and the edges once, so C-SCAN makes the wait uniform across the disk rather than merely bounded. And LOOK and C-LOOK are the same two algorithms with one refinement: turn around at the last actual request rather than at the physical end of the disk, which is why LOOK’s 299 beats SCAN’s 331 with an identical service order. The pattern to carry away is the one from CPU scheduling: the algorithm with the best average is rarely the one deployed, because bounded worst case is worth paying for.

Key takeaways

A system call is a mode switch, not a function call — that is where its cost comes from.
n unconditional forks give 2ⁿ processes; a conditional fork breaks the doubling, so draw the tree.
Threads share code, globals, heap and open files; they keep stack, registers and PC private.
A blocking call in a user-level thread blocks the whole process, and one such process gets one CPU.
Compute completion times first, then turnaround = completion − arrival, then waiting = turnaround − burst.
SRTF is optimal for average waiting time; if an option beats it on the same input, the arithmetic is wrong.
Round robin trades average waiting time for a bounded response time; a huge quantum makes it FCFS.
Running → ready is preemption, and blocked → running does not exist.
Disk scheduling counts cylinders: FCFS 640, SSTF 236, SCAN 331, LOOK 299 on the standard example.
SSTF starves distant requests, which is why SCAN exists — the same trade as SJF against round robin.

Practice questions (9)

Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.

A program executes fork(); fork(); fork(); with no conditionals and no process exiting early. How many processes are in existence when the last statement completes?
1. 4
2. 7
3. 8
4. 6
Show answer
Answer: C — 8
8. Every process that exists at a fork executes it, so the population doubles at each of the three calls: 1 → 2 → 4 → 8. The count of children created is one less, 7, and option B is that number offered for the question that was not asked — read whether the question says “processes in existence” or “child processes created”. Option A counts one child per call, which would be right only if a single process did all the forking while the children skipped ahead. The doubling holds here precisely because the forks are unconditional; put the second one inside if (fork() == 0) and only the children continue, so the tree has to be drawn.
Processes P1, P2, P3, P4 arrive at times 0, 1, 2, 3 with CPU bursts 8, 4, 9, 5 respectively. Under shortest-remaining-time-first (preemptive) scheduling, the average waiting time in time units is ______
Numerical answer — type the value.
Show answer
Answer: 6.5
6.5. Build the Gantt chart. P1 runs 0–1; P2 arrives with burst 4 against P1’s remaining 7, so it preempts and runs 1–5 to completion. At t=5 the remaining work is P1 7, P3 9, P4 5, so P4 runs 5–10, then P1 10–17, then P3 17–26. Completion times are P1 17, P2 5, P3 26, P4 10. Turnaround = completion − arrival gives 17, 4, 24, 7; waiting = turnaround − burst gives 9, 0, 15, 2, summing to 26 over four processes = 6.5. Two checks worth doing: P2 waits 0 because it preempted immediately on arrival, and the answer must not exceed FCFS on the same input (8.75), because SRTF is optimal for this metric. Getting 7.75 means the preemption at t=1 was missed — that is non-preemptive SJF.
Two threads belong to the same process. Which of the following are shared between them?
1. The heap
2. The table of open file descriptors
3. The stack
4. Global variables
Show answer
Answer: A — The heap; B — The table of open file descriptors; D — Global variables
A, B and D. Threads exist to share an address space, so everything that lives in that space and is not per-flow is shared: the heap, the globals, and process-level resources such as the open-file table and the signal handlers. C is the exception and is the whole point of a thread: each flow of control is at a different instruction with a different call chain, so each needs its own stack, along with its own registers and program counter. That asymmetry is exactly what makes threads both cheap and dangerous — cheap because two threads can pass data through a global with no kernel involvement, dangerous because that same global needs a lock. A useful cross-check: anything you could not duplicate without breaking the abstraction (stack, PC, registers) is private; everything else is shared.
For the same four processes — arrivals 0, 1, 2, 3 and bursts 8, 4, 9, 5 — the average waiting times are 6.5 under SRTF, 7.75 under non-preemptive SJF, 8.75 under FCFS and 11.75 under round robin with quantum 4. Which conclusion is correct?
1. Round robin is a poor scheduler and should not be used in practice
2. Round robin loses on average waiting time because it is optimising bounded response time instead
3. A larger quantum would make round robin beat SRTF on average waiting time
4. The ordering would reverse if the bursts were all equal
Show answer
Answer: B — Round robin loses on average waiting time because it is optimising bounded response time instead
The four numbers are measuring one thing, and round robin is not trying to minimise it. Its guarantee is on response time — with n processes and quantum q, no job waits more than about (n−1)q before it first runs — which is the number an interactive system cares about, and which SJF-family schedulers leave unbounded. Option A draws the wrong lesson from a single metric. Option C is impossible in the direction it claims: SRTF is provably optimal for average waiting time, so nothing can beat it on the same input; a larger quantum only pushes round robin towards FCFS’s 8.75, which is still worse. Option D goes the wrong way — with equal bursts and the same arrival order, FCFS, SJF and SRTF all produce the same schedule, so the ordering collapses rather than reverses.
In a process using user-level threads, one thread issues a blocking read system call. What happens to the other threads of that process?
1. They continue to run, since only the calling thread is waiting
2. They are all blocked, because the kernel sees only one schedulable entity
3. They are migrated to another CPU by the thread library
4. They continue only if the process has more than one kernel thread
Show answer
Answer: B — They are all blocked, because the kernel sees only one schedulable entity
All of them block. User-level threads are scheduled by a library inside the process, so the kernel knows about exactly one schedulable entity — the process — and blocking is something the kernel does to entities it knows about. It therefore blocks the process, and every other thread stops even though each was perfectly runnable. Option A is the answer for kernel-level threads, which are individually visible and separately schedulable, and the contrast is the examinable content. Option C describes something a user-level library cannot do: it has one CPU because it has one schedulable entity, which is also why user-level threads cannot exploit a multiprocessor. Option D is a real hybrid design (many-to-many) but it is not what the question specifies, and reading “user-level” as “hybrid” is the slip it is testing.
Which process state transition is caused by the scheduler rather than by the process itself?
1. Running → blocked
2. Blocked → ready
3. Running → ready
4. Running → terminated
Show answer
Answer: C — Running → ready
Running → ready is preemption, and it is the only transition in the list the process does not bring about. The scheduler does it on a timer interrupt, taking the CPU from a process that was still willing to use it — which is precisely what makes a scheduling algorithm preemptive. The others are all the process’s own doing or a consequence of it: running → blocked happens because the process asked for something it must wait for, running → terminated because it called exit, and blocked → ready when the awaited event arrives (the I/O completion handler moves it, but the process caused the wait). One transition is absent from the whole list and is a common distractor elsewhere: blocked → running does not exist. A process that finishes waiting joins the ready queue and is scheduled like anything else.
Round robin scheduling with a quantum larger than every process’s CPU burst behaves identically to:
1. Shortest job first
2. First come first served
3. Shortest remaining time first
4. Priority scheduling with ageing
Show answer
Answer: B — First come first served
FCFS. Round robin preempts a process only when its quantum expires; if the quantum exceeds every burst, no quantum ever expires, so each process runs to completion in the order it entered the ready queue — which is the definition of FCFS. Notice what the answer does not depend on: burst lengths play no part in round robin’s choice, which is why it cannot degenerate into SJF or SRTF (options A and C) no matter how the quantum is set. Those need burst-length information that round robin never consults. Option D adds a mechanism round robin does not have. The other limit is worth holding alongside this one: as the quantum shrinks towards zero the useful fraction of the CPU is q/(q+s) for context-switch cost s, so the overhead swamps the work.
On the same four processes (arrivals 0, 1, 2, 3; bursts 8, 4, 9, 5), FCFS gives an average waiting time of 8.75 while non-preemptive SJF gives 7.75. The 1.0 difference comes from:
1. SJF preempting P1 when P2 arrives at time 1
2. SJF running P4 before P3 at time 12, moving 9 units of waiting off P4 onto P3
3. SJF using a shorter quantum
4. SJF having a lower context-switch cost
Show answer
Answer: B — SJF running P4 before P3 at time 12, moving 9 units of waiting off P4 onto P3
Both algorithms run P1 0–8 and P2 8–12, so they agree until t=12. There FCFS takes P3 (arrived at 2) and SJF takes the shorter P4, and that single reordering is the entire difference. The waiting times go from FCFS’s 0, 7, 10, 18 to SJF’s 0, 7, 15, 9: P4 saves 9 and P3 loses 5, a net saving of 4 over four processes = 1.0, which is exactly the gap. Option A describes SRTF, not non-preemptive SJF — that preemption is worth a further 1.25 and takes the average to 6.5, so attributing it here double-counts. Options C and D import round robin’s quantum and a cost model neither algorithm uses; both averages above are computed with zero switching cost.
A disk has cylinders 0 to 199 and the head is at cylinder 53. The pending requests, in arrival order, are 98, 183, 37, 122, 14, 124, 65, 67. Under SSTF disk scheduling, the total number of cylinders the head traverses is ______
Numerical answer — type the value.
Show answer
Answer: 236
236. SSTF always goes to the nearest pending request, so trace it: from 53 the nearest is 65 (12 cylinders), then 67 (2), then the nearest is 37 (30) rather than 98, then 14 (23), and only now does the head cross the disk to 98 (84), then 122 (24), 124 (2) and 183 (59). Adding: 12 + 2 + 30 + 23 + 84 + 24 + 2 + 59 = 236. Compare FCFS on the same queue, which services in arrival order and traverses 640 — SSTF saves 63%, and the single expensive move (84 cylinders from 14 to 98) is unavoidable because the queue has requests on both sides of the head. The commonest error is to sweep in one direction, which gives SCAN’s 331 or LOOK’s 299 instead: SSTF has no notion of direction at all, and it reverses whenever the nearest request is behind it.