Scheduling algorithm (SCAN, LOOK) in LLD - System Design Exercise

Design: Disk Scheduling Algorithm Simulator

In scope: Implementing SCAN and LOOK scheduling logic, input/output handling, dynamic request addition. Out of scope: Actual disk hardware interaction, GUI, multi-threading concurrency.

Functional Requirements

FR1: Simulate disk scheduling using SCAN and LOOK algorithms

FR2: Accept a list of disk I/O requests with track numbers

FR3: Start from a given initial head position

FR4: Output the order of servicing requests and total head movement

FR5: Support both SCAN and LOOK modes selectable by user

FR6: Handle requests arriving dynamically during simulation

Non-Functional Requirements

NFR1: Must handle up to 1000 requests efficiently

NFR2: Response time for simulation results under 1 second

NFR3: Memory usage should be minimal for embedded or low-resource systems

Think Before You Design

Questions to Ask

❓ Question 1

❓ Question 2

❓ Question 3

❓ Question 4

❓ Question 5

Key Components

Request queue sorted by track number

Current head position and direction state

Scheduler module implementing SCAN and LOOK logic

Input/output interface for requests and results

Design Patterns

Two-pointer technique for scanning requests in order

State machine for head direction and movement

Event-driven updates for dynamic request arrival

Reference Architecture

 +---------------------+
 | Disk Scheduling Sim |
 +---------------------+
           |
           v
 +---------------------+       +---------------------+
 | Request Input Queue  |<----->| Dynamic Request Feed |
 +---------------------+       +---------------------+
           |
           v
 +---------------------+
 | Scheduler Module     |--SCAN/LOOK logic
 +---------------------+
           |
           v
 +---------------------+
 | Output: Service Order|
 +---------------------+

Components

Request Input Queue

In-memory sorted list or balanced tree

Store and organize disk I/O requests by track number

Scheduler Module

Low-level logic functions

Implement SCAN and LOOK algorithms to decide service order

Dynamic Request Feed

Event or callback mechanism

Add new requests during simulation runtime

Output Module

Console or log output

Display order of serviced requests and total head movement

Request Flow

1. User inputs initial head position, direction, and request list

2. Requests are stored in the Request Input Queue sorted by track

3. Scheduler Module starts scanning requests in current direction

4. For SCAN: head moves to end track then reverses; for LOOK: head moves only to last request in direction

5. Scheduler selects next request based on algorithm and current head position

6. Serviced request is removed from queue and output recorded

7. If new requests arrive, they are inserted into the queue dynamically

8. Process continues until all requests are serviced

9. Output Module prints the service order and total head movement

Database Schema

Not applicable - system uses in-memory data structures only

Scaling Discussion

Bottlenecks

Large number of requests causing slow sorting or searching

Frequent dynamic insertions disrupting efficient scanning

Memory constraints on embedded or low-resource devices

Solutions

Use balanced binary search trees or indexed data structures for O(log n) insert/search

Batch dynamic requests and insert periodically to reduce overhead

Optimize data structures for memory efficiency and avoid unnecessary copies

Interview Tips

Time: Spend 10 minutes clarifying requirements and constraints, 20 minutes designing the scheduler logic and data flow, 10 minutes discussing scaling and optimizations, 5 minutes summarizing.

Explain difference between SCAN and LOOK algorithms clearly

Describe how head direction and movement affect request servicing

Discuss data structures used for efficient request management

Mention handling of dynamic requests during simulation

Address scalability and performance considerations

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