Scheduling algorithm (SCAN, LOOK) in LLD - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

How does the SCAN disk scheduling algorithm work?

Imagine a disk head moving over tracks numbered 0 to 199. The head is currently at track 50 and moving towards higher track numbers. The pending requests are at tracks 55, 58, 39, 18, and 90.

Which sequence of servicing requests correctly represents the SCAN algorithm's order?

A 39, 18, 55, 58, 90

B 55, 58, 90, 39, 18

C 90, 58, 55, 39, 18

D 55, 58, 90, 199 (end), 39, 18

💡 Hint

Think of the disk head moving in one direction servicing requests until it reaches the end, then reversing.

SCAN moves the head towards the end (track 199), servicing requests on the way (55, 58, 90), then reverses direction to service remaining requests (39, 18).

❓ Architecture

intermediate

Choosing between SCAN and LOOK for disk scheduling

You are designing a disk scheduling module for a system with frequent requests clustered near the middle tracks. Which algorithm between SCAN and LOOK is better to reduce unnecessary head movement and why?

A LOOK, because it only goes as far as the last request in each direction, avoiding unnecessary travel to disk ends.

B SCAN, because it always goes to the disk ends, ensuring fairness.

C LOOK, because it randomly jumps to requests to reduce wait time.

D SCAN, because it ignores requests near the middle to speed up processing.

💡 Hint

Consider how far the head moves in each algorithm.

LOOK moves the head only up to the furthest request in each direction, reducing unnecessary movement compared to SCAN, which always goes to the disk ends.

❓ scaling

advanced

Scaling disk scheduling with high request volume

A disk scheduling system using SCAN is experiencing high request volume with requests spread across all tracks. What is a key architectural change to maintain low latency and throughput?

A Implement request queues partitioned by track ranges to parallelize scheduling and reduce head movement.

B Switch to FIFO scheduling to simplify processing under load.

C Increase disk rotation speed to reduce seek time without changing scheduling.

D Use random scheduling to distribute load evenly.

💡 Hint

Think about dividing work to handle many requests efficiently.

Partitioning requests by track ranges allows parallel scheduling and reduces head movement, improving latency and throughput under high load.

❓ tradeoff

advanced

Tradeoffs between SCAN and LOOK in real-time systems

In a real-time system requiring predictable maximum wait times, which disk scheduling algorithm is preferable and why?

A LOOK, because it prioritizes requests randomly for fairness.

B SCAN, because it always scans to the disk ends, providing a predictable maximum wait time.

C LOOK, because it skips empty tracks, reducing maximum wait time unpredictably.

D SCAN, because it ignores some requests to speed up processing.

💡 Hint

Consider which algorithm guarantees a maximum travel distance.

SCAN always moves to the disk ends, so the maximum wait time is predictable. LOOK may stop early, making max wait time less predictable.

❓ estimation

expert

Estimating average seek time with LOOK scheduling

A disk has 200 tracks (0-199). Requests arrive uniformly at random. The disk head is currently at track 100. Using LOOK scheduling, estimate the average seek distance per request assuming a large number of requests.

A Approximately 0 tracks, because LOOK minimizes movement completely.

B Approximately 100 tracks, because the head always moves from one end to the other.

C Approximately 50 tracks, because LOOK moves only between the furthest requests, averaging half the disk range.

D Approximately 25 tracks, because requests cluster near the current head position.

💡 Hint

Think about the average distance between random points on a line segment.

With uniform random requests, the average distance between requests is about half the disk size. LOOK moves only between the furthest requests, so average seek distance is about 50 tracks.