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.

Practice

1. What is the main difference between the SCAN and LOOK disk scheduling algorithms?

easy

A. SCAN stops at the last request in the direction, LOOK goes to the disk edge

B. LOOK moves the head randomly, SCAN moves sequentially

C. LOOK stops at the last request in the direction, SCAN goes to the disk edge

D. SCAN only moves in one direction, LOOK moves back and forth

Solution

1. Step 1: Understand SCAN behavior

   SCAN moves the disk head to the end of the disk in one direction, servicing requests along the way.

2. Step 2: Understand LOOK behavior

   LOOK moves the disk head only as far as the last request in the current direction, then reverses.

3. Final Answer:

   LOOK stops at the last request in the direction, SCAN goes to the disk edge -> Option C

4. Quick Check:

   LOOK stops early, SCAN goes to edge [OK]

Hint: LOOK stops at last request, SCAN goes to disk edge [OK]

Common Mistakes:

• Confusing which algorithm stops at disk edge
• Thinking LOOK moves randomly
• Assuming SCAN moves only one way

2. Which of the following is the correct order of servicing requests using the SCAN algorithm if the head starts at 50 and requests are at [10, 20, 35, 70, 90] with disk size 100?

easy

A. 50 -> 70 -> 90 -> 35 -> 20 -> 10

B. 50 -> 70 -> 90 -> 100 -> 35 -> 20 -> 10

C. 50 -> 35 -> 20 -> 10 -> 0 -> 70 -> 90

D. 50 -> 90 -> 70 -> 35 -> 20 -> 10

Solution

1. Step 1: SCAN moves towards higher end first

   Starting at 50, SCAN moves up servicing 70 and 90, then reaches disk edge 100.

2. Step 2: SCAN reverses direction

   After reaching 100, it moves down servicing 35, 20, and 10.

3. Final Answer:

   50 -> 70 -> 90 -> 100 -> 35 -> 20 -> 10 -> Option B

4. Quick Check:

   SCAN goes to edge 100 before reversing [OK]

Hint: SCAN always goes to disk edge before reversing [OK]

Common Mistakes:

• Not including disk edge in the path
• Reversing direction too early
• Skipping requests on the way

3. Given the LOOK algorithm with head starting at 40 and requests at [10, 20, 35, 70, 90], what is the order of servicing requests if the head moves towards higher track numbers first?

medium

A. [40, 90, 70, 35, 20, 10]

B. [40, 70, 90, 100, 35, 20, 10]

C. [40, 35, 20, 10, 70, 90]

D. [40, 70, 90, 35, 20, 10]

Solution

1. Step 1: LOOK moves towards higher requests first

   Starting at 40, it services 70 and 90, stopping at last request 90.

2. Step 2: LOOK reverses direction

   Then it moves down servicing 35, 20, and 10, stopping at last request in that direction.

3. Final Answer:

   [40, 70, 90, 35, 20, 10] -> Option D

4. Quick Check:

   LOOK stops at last request, no disk edge [OK]

Hint: LOOK stops at last request, no disk edge [OK]

Common Mistakes:

• Including disk edge in LOOK path
• Reversing direction too early
• Skipping requests on the way

4. Identify the error in this SCAN algorithm implementation snippet where the head moves from 30 to 90 with requests at [20, 40, 60, 80]:

requests = [20, 40, 60, 80]
head = 30
for track in range(head, 100):
    if track in requests:
        print(f"Servicing {track}")
for track in range(head-1, -1, -1):
    if track in requests:
        print(f"Servicing {track}")

medium

A. The first loop should go to 101, not 100

B. The first loop should include the head position

C. The second loop should start from head, not head-1

D. The second loop should start from 99, not head-1

Solution

1. Step 1: Check range end in first loop

   range(head, 100) goes from 30 to 99 (exclusive end), missing disk edge at 100.

2. Step 2: Confirm disk convention

   As per standard problems (disk size 100 includes edge 100), first loop should be range(head, 101) to reach 100.

3. Final Answer:

   The first loop should go to 101, not 100 -> Option A

4. Quick Check:

   range exclusive, edge 100 needs 101 [OK]

Hint: Range end exclusive, use 101 for disk edge 100 [OK]

Common Mistakes:

• Confusing inclusive vs exclusive range ends
• Starting second loop incorrectly
• Assuming head position is included twice

5. You have a disk with size 200 tracks and requests at [10, 50, 120, 180]. The head is at 100 and moves using LOOK algorithm. What is the total head movement if the head moves towards lower track numbers first?

hard

A. 260 tracks

B. 160 tracks

C. 180 tracks

D. 120 tracks

Solution

1. Step 1: Initial direction to lower tracks

   Lower requests: 50, 10. Path: 100 -> 50 (50 tracks), 50 -> 10 (40 tracks). Subtotal: 90.

2. Step 2: Reverse direction to higher tracks

   Higher requests: 120, 180. Path: 10 -> 120 (110 tracks), 120 -> 180 (60 tracks). Subtotal: 170.

3. Step 3: Total head movement

   90 + 170 = 260 tracks.

4. Final Answer:

   260 tracks -> Option A

5. Quick Check:

   Sum of |current - next| over servicing sequence [OK]

Hint: Sum distances in servicing order: 100-50-10-120-180 [OK]

Common Mistakes:

• Including disk edges in LOOK movement
• Adding extra distances beyond last requests
• Misordering request servicing