Scheduling algorithm (SCAN, LOOK) in LLD - Scalability & System Analysis

Scalability Analysis - Scheduling algorithm (SCAN, LOOK)

Growth Table: Scheduling Algorithm (SCAN, LOOK)

Users/Requests	Disk Requests per Second	Queue Length	Response Time	Resource Usage
100 requests/sec	100	Short queue	Low latency	Single disk, CPU low
10,000 requests/sec	10,000	Medium queue	Moderate latency	Disk busy, CPU moderate
1,000,000 requests/sec	1,000,000	Long queue	High latency	Disk saturated, CPU high
100,000,000 requests/sec	100,000,000	Very long queue	Very high latency	Disk overloaded, CPU maxed

First Bottleneck

The disk I/O is the first bottleneck because SCAN and LOOK algorithms optimize disk head movement but cannot increase physical disk speed. As requests grow, the disk queue lengthens, causing delays.

Scaling Solutions

• Horizontal scaling: Add more disks and distribute requests (e.g., RAID, sharding data across disks).
• Caching: Use memory caches to reduce disk reads for repeated data.
• Upgrade hardware: Use SSDs or faster disks to reduce seek time.
• Load balancing: Distribute requests evenly to avoid hotspots.
• Algorithm tuning: Use LOOK to reduce unnecessary disk head movement compared to SCAN.

Cost Analysis

At 10,000 requests/sec, disk I/O bandwidth and seek time become critical. Each request may require 5-10 ms seek time on HDDs, limiting throughput to ~100-200 requests/sec per disk.

To handle 1,000,000 requests/sec, thousands of disks or SSDs are needed, increasing cost significantly.

CPU usage grows with queue management and scheduling overhead but is usually less critical than disk I/O.

Interview Tip

Start by explaining how SCAN and LOOK reduce disk head movement to improve throughput. Then discuss physical disk limits as bottlenecks. Finally, propose scaling solutions like adding disks, caching, and upgrading hardware.

Self Check

Your disk handles 1000 requests/sec. Traffic grows 10x to 10,000 requests/sec. What do you do first?

Answer: Add more disks and distribute requests to reduce queue length and avoid disk saturation.

Key Result

SCAN and LOOK scheduling improve disk efficiency but physical disk speed limits throughput; scaling requires adding disks, caching, or upgrading hardware.

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