CSE Roadmap

Core tier · about 5 hours · 7 parts

Part 7 of 7 · 3 min read

Exercises

Easy

Easy 1: Order by priority (20 minutes)

Jobs W (priority 3), X (1), Y (4), Z (2) are all ready at time 0 and each needs 2 units. Give the order and the waiting times, without preemption.

Done when: order X, Z, W, Y; waiting 0, 2, 4, 6; average 3.00.

Hint

Lower number first.

Easy 2: Name the problem (20 minutes)

A low-priority job has waited 3 hours while important jobs keep arriving. Name the problem and a cure.

Done when: starvation, cured by aging.

Hint

Think of the hospital.

Easy 3: Rule check (20 minutes)

In an MLFQ, a process uses 1 ms of a 4 ms quantum and then waits for input. Does it move down? Give the rule.

Done when: no, because it gave up the processor before the quantum ended (rule 4).

Hint

Only a full quantum causes a demotion.

Medium

Medium 1: Trace preemptive priority (30 minutes)

Processes (arrival, CPU time, priority; lower is better): P (0, 4, 3), Q (1, 2, 1), R (2, 3, 2). Give the timeline and the waiting times with preemption.

Done when: timeline P 0 to 1, Q 1 to 3, R 3 to 6, P 6 to 9; waiting P 5, Q 0, R 1; average 2.00.

Hint

Q at time 1 has the best priority, so it preempts P.

Medium 2: Aging by hand (30 minutes)

A process at priority 8 gains one step per 4 units of waiting. Other jobs always have priority 5, and ties go to the older process. When does it first run, and at what time does it start?

Done when: it reaches priority 5 after 12 units of waiting, so it starts at time 12.

Hint

Steps needed = 8 − 5 = 3, each step takes 4 units of waiting.

Medium 3: Trace the MLFQ (30 minutes)

Two queues with quanta 2 and 4. Jobs X (arrival 0, CPU 6) and Y (arrival 1, CPU 3), both compute only. Give the timeline.

Done when: timeline X 0 to 2, Y 2 to 4, X 4 to 8, Y 8 to 9, so X ends at 8 and Y ends at 9.

Hint

At time 4, X and Y are both in queue 1, and X is first.

Hard

Hard 1: Draw a priority inversion (60 minutes)

Three threads H, M and L, with priorities high, medium and low. Draw a timeline in which L takes a lock, H wants it and M runs for 10 units. Draw it again with priority inheritance and compare H's waiting time.

Done when: two timelines, with H waiting at least 10 units longer in the first.

Hint

In the second timeline, L runs with H's priority and M cannot preempt.

Hard 2: Simulate an MLFQ (90 minutes)

Write a simulator with three queues (quanta 2, 4 and 8), CPU-bound and I/O-bound jobs, and a boost every 30 units. Run the example of section 4 and check that it prints LLILLILLILLILLLL.

Done when: the same sequence, with finish times I 12 and L 16.

Hint

Keep a remaining-quantum counter for each process.

Hard 3: Game the scheduler (60 minutes)

Change your simulator so that a job gives up the processor 1 unit before every quantum ends. Show that it stays in the top queue. Then add the allotment rule and show that it moves down.

Done when: two runs: one where the gaming job stays at level 0, and one where it sinks.

Hint

Track the time used at the level, and move down when it reaches the quantum.