What is the CPU–I/O burst cycle?
Process execution consists of a cycle of CPU execution and I/O wait.
How are CPU-burst lengths generally distributed?
Exponentially: many short bursts, few long bursts.
Under which of the four decision points is scheduling nonpreemptive?
Only under 1 (running → waiting) and 4 (terminates); all other scheduling is preemptive.
Why is preemptive scheduling harder to implement?
It must maintain consistency of data shared between processes and, more importantly, kernel data structures (e.g., I/O queues).
What three things does dispatching involve?
Switching context; switching to user mode; jumping to the proper location in the user program to restart that program.
Define dispatch latency.
The time it takes for the dispatcher to stop one process and start another running.
Throughput vs turnaround time.
Throughput: # of processes that complete their execution per time unit (maximize). Turnaround: time from submission to termination of a process (minimize).
Define waiting time.
The amount of time a process has been waiting in the ready queue.
Define response time.
The time from when a request is submitted until the first response is produced, not output (for timesharing environments).
What is the convoy effect?
Short processes stuck behind a long process (in FCFS).
Why is FCFS not useful for interactive users?
Because it cannot guarantee good response time.
Why is SJF called optimal, and what is its difficulty?
It gives the minimum average waiting time for a given set of processes; the difficulty is knowing the length of the next CPU request.
What is SRTF?
Preemptive SJF: if a new process arrives with a CPU burst shorter than the remaining time of the current process, preempt it.
P1 (arrives 0.0, burst 7), P2 (2.0, 4), P3 (4.0, 1), P4 (5.0, 4): average waiting time with nonpreemptive SJF vs SRTF?
Nonpreemptive SJF: (0 + 6 + 3 + 7)/4 = 4. SRTF: (9 + 1 + 0 + 2)/4 = 3.
Exponential averaging formula.
τₙ₊₁ = α tₙ + (1 − α) τₙ, with 0 ≤ α ≤ 1 (tₙ = actual nth burst, τₙ₊₁ = predicted next burst).
What do α = 0 and α = 1 mean?
α = 0: τₙ₊₁ = τₙ, recent history does not count. α = 1: τₙ₊₁ = tₙ, only the actual last CPU burst counts.
In priority scheduling, which number is the highest priority?
The smallest integer.
Starvation and aging.
Starvation: low-priority processes may never execute. Aging: as time progresses, increase the priority of the process.
How is SJF related to priority scheduling?
SJF is a priority scheduling where priority is the predicted next CPU burst time.
Round robin: maximum wait with n processes and quantum q.
No process waits more than (n − 1)q time units; each gets 1/n of the CPU time in chunks of at most q.
RR: what happens if q is very large? very small?
q large ⇒ FIFO. q small ⇒ q must be large with respect to context switch, otherwise overhead is too high.
RR compared with SJF.
Typically higher average turnaround than SJF, but better response.
Two ways to schedule between the queues of a multilevel queue.
Fixed priority preemptive scheduling (serve all foreground then background; possible starvation), or time slice (e.g., 80% foreground in RR, 20% background in FCFS).
Multilevel queue vs multilevel feedback queue.
In a multilevel feedback queue a process can move between the queues (aging can be implemented this way).
In the Q0/Q1/Q2 example, when is a job moved to Q2?
If it still does not complete after 8 ms in Q0 plus 16 additional ms in Q1 (24 ms); at Q2 it is served FCFS.