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