CSE Roadmap

Core tier · about 4 hours · 7 parts

Part 7 of 7 · 3 min read

Exercises

Easy

Easy 1: FCFS waiting times (20 minutes)

Jobs X (arrival 0, CPU 6), Y (arrival 0, CPU 2), Z (arrival 0, CPU 4) run in the order X, Y, Z. Give each waiting time and the average.

Done when: 0, 6, 8 and an average of 14 ÷ 3 = 4.67.

Hint

Waiting of a later job = sum of the earlier jobs' CPU times when all arrive at 0.

Easy 2: Reorder for SJF (20 minutes)

Use the same three jobs, but run them in SJF order. Give the order and the average waiting time.

Done when: order Y, Z, X; waiting 0, 2, 6; average 8 ÷ 3 = 2.67.

Hint

SJF sorts by CPU time.

Easy 3: One prediction (20 minutes)

With α = 0.5, an old estimate of 12 and a measured burst of 6, give the next estimate.

Done when: 9.

Hint

0.5 × 6 + 0.5 × 12.

Medium

Medium 1: Trace SJF (30 minutes)

Processes E (arrival 0, CPU 7), F (arrival 2, CPU 4), G (arrival 4, CPU 1), H (arrival 5, CPU 4). Trace non-preemptive SJF and compute the average waiting time.

Done when: timeline E 0 to 7, G 7 to 8, F 8 to 12, H 12 to 16; waiting 0, 6, 3, 7; average 4.00.

Hint

At time 7 all of F, G and H have arrived, and G is the shortest.

Medium 2: Trace SRTF (30 minutes)

Use the same four processes with SRTF. Give the timeline and the average waiting time.

Done when: timeline E 0 to 2, F 2 to 4, G 4 to 5, F 5 to 7, H 7 to 11, E 11 to 16; waiting E 9, F 1, G 0, H 2; average 3.00.

Hint

G arrives at 4 with 1 unit and F has 2 left, so G preempts.

Medium 3: Predict a series (30 minutes)

With α = 0.5 and τ(0) = 10, give the next three predictions for measured bursts 6, 4 and 6.

Done when: 8, 6, 6.

Hint

Apply the formula three times, each time using the new estimate.

Hard

Hard 1: Convoy with I/O (60 minutes)

One CPU-bound process runs 100 units. Three I/O-bound processes each need 1 unit of CPU and then 10 units of disk wait, repeated. All four arrive at 0, the CPU-bound process first. Explain, with a timeline of the first 20 units, why the disk stays idle under FCFS, and what order would keep both busy.

Done when: a timeline showing the disk idle while the long process runs, and an order that puts the short bursts first.

Hint

The disk can start only when an I/O-bound process has had its CPU burst.

Hard 2: Write the simulator (60 minutes)

Extend the C program from section 2 to implement SRTF, and check it against the trace in section 4.

Done when: it prints the finish times A 10, B 4, C 18, D 6 and the average waiting 3.50.

Hint

Advance time one unit at a time and pick the least remaining time.

Hard 3: Show starvation (60 minutes)

Write a simulation in which a job of length 20 arrives at time 0 and a new job of length 2 arrives every 2 time units. Run SJF for 100 units and report when the long job first runs.

Done when: a result that the long job does not run in 100 units, with an explanation, and a change (such as aging, page 4) that fixes it.

Hint

A short job is always ready before the long one is chosen.