CPU Scheduling I: Classic Algorithms and Metrics

Which scheduler decides which ready process gets the CPU next, typically every few milliseconds?

Which is not a responsibility of the CPU scheduler?

In non-preemptive scheduling, when can the scheduler take the CPU from a running process?

A process arrives at 2, first runs at 5, needs 6 units of CPU and finishes at 15. What are its turnaround, waiting and response times?

Tasks T1 = 1 s, T2 = 10 s, T3 = 1 s all arrive at t = 0 and are scheduled with non-preemptive SJF. What is the average waiting time?

Same tasks (T1 = 1, T2 = 10, T3 = 1) with SJF, but arrival times 0, 2 and 4. What is the throughput?

What is the convoy effect?

For the workload A(0,3), B(2,6), C(4,4), D(6,5), E(8,2) [arrival, burst], FCFS gives average waiting 4.60. What does non-preemptive SJF give?

Same workload with SRTF. Which process runs from time 4 to 8?

Which statement about SJF is correct?

With exponential averaging (α = 0.5), the previous prediction is τ = 10 ms and the actual burst was 6 ms. What is the next prediction?

In exponential averaging, what does α = 1 mean?

Five processes arrive at 0: P1 (burst 10, priority 3), P2 (1, 1), P3 (2, 4), P4 (1, 5), P5 (5, 2). Non-preemptive priority (1 = highest). What is the average waiting time?

What is aging in priority scheduling?

In Round Robin, what happens as the time quantum q becomes very large?

For the workload A(0,3), B(2,6), C(4,4), D(6,5), E(8,2), Round Robin with q = 2 (new arrivals queued before the preempted process) gives which order for the first four slices?

On that workload, RR (q = 2) has the worst average waiting time (6.00) of the algorithms compared, yet interactive systems use it. Why?

A time quantum is 4 ms and a context switch costs 0.5 ms. What fraction of CPU time is spent on context switches when processes always use their full quantum?

Under HRRN, a job has waited 6 ms and needs 3 ms of CPU. What is its response ratio?

Why can't long jobs starve under HRRN?

In an MLFQ, a process repeatedly uses its entire time quantum. What happens to it?

Why do real MLFQ schedulers periodically boost all processes to the top queue?

Which job type benefits most from being classified as I/O-bound by an MLFQ?

Three processes hold 50, 30 and 20 lottery tickets. About what share of the CPU does the second process receive over a long period?

Student X runs 1 process and student Y runs 9 CPU-bound processes on a shared server. Which policy gives each student about half of the CPU?

A batch system's main goal is to finish as many jobs per hour as possible. Which metric should it optimize?

For the processes below (all times in ms), draw the Gantt chart and compute each process's turnaround and waiting time and the averages for (a) FCFS and (b) SRTF.

Using HRRN on the workload A(0,3), B(2,6), C(4,4), D(6,5), E(8,2) [arrival, burst], show the response ratios at each decision point, the Gantt chart and the average waiting time. Compare with FCFS (average waiting 4.60).

Trace an MLFQ with three queues — Q0 (quantum 2), Q1 (quantum 4), Q2 (FCFS) — for the jobs batch (arrival 0, burst 12), edit1 (1, 1), sim (3, 7), edit2 (5, 2). New jobs enter Q0; a job that uses its full quantum is demoted; the CPU serves the highest non-empty queue; arrivals during a slice are queued before the demoted job. Give the Gantt chart and each job's turnaround.

You manage the EdgeCampus GPU job queue (Chapter 3). Jobs have very different lengths (2 minutes to 1 hour), users complain that tiny test jobs wait behind long training jobs, but long jobs must also finish eventually. Which scheduling algorithm(s) from this chapter would you use, and why? Mention how you would estimate job lengths.