Disk Scheduling - SSTF, SCAN, C-SCAN

▶

Steps

setup

Initialize SSTF Scheduler

Initialize the SSTF scheduler with the head at position 50 and the request queue [10, 22, 20, 2, 40, 6, 38, 48]. No requests have been serviced yet.

💡 Setting up initial state is crucial to understand how the scheduler will pick requests based on shortest seek time.

Line:

head = 50
requests = [10, 22, 20, 2, 40, 6, 38, 48]
serviced = []

💡 The scheduler starts with a known head position and a list of pending requests.

compare

SSTF: Find Closest Request to Head (50)

Calculate the distance from the current head position (50) to each pending request to find the closest one.

💡 SSTF selects the request with the shortest seek time to minimize head movement.

Line:

distances = {r: abs(head - r) for r in requests}
closest = min(distances, key=distances.get)

💡 SSTF picks the request minimizing immediate seek time, reducing total movement.

traverse

SSTF: Move Head to Request 48

Move the disk head from position 50 to 48 to service the closest request.

💡 Moving the head to the closest request reduces seek time and total head movement.

Line:

head = closest
requests.remove(closest)
serviced.append(closest)

💡 The head physically moves to the selected request, which is then removed from the queue.

compare

SSTF: Find Next Closest Request to Head (48)

From the updated head position 48, find the next closest request among remaining requests.

💡 SSTF always picks the nearest request to minimize seek time at each step.

Line:

distances = {r: abs(head - r) for r in requests}
closest = min(distances, key=distances.get)

💡 The algorithm dynamically updates choices based on current head position.

traverse

SSTF: Move Head to Request 40

Move the head from 48 to 40 and service the request.

💡 Servicing requests in order of proximity reduces total head movement.

Line:

head = closest
requests.remove(closest)
serviced.append(closest)

💡 The head moves closer to the lower numbered requests as SSTF progresses.

setup

Initialize SCAN Scheduler

Initialize SCAN scheduler with head at 50, requests [10, 22, 20, 2, 40, 6, 38, 48], and direction moving towards higher track numbers.

💡 SCAN moves the head in one direction servicing requests until it reaches the end, then reverses.

Line:

head = 50
requests = [10, 22, 20, 2, 40, 6, 38, 48]
direction = 'up'
serviced = []

💡 SCAN's initial direction and head position set the movement pattern.

traverse

SCAN: Move Head Up to Next Request (48)

Head moves from 50 upwards, servicing requests in ascending order. The closest request in the upward direction is 48, which is serviced first.

💡 SCAN services requests in one direction, reducing seek time by avoiding back-and-forth movement.

Line:

next_requests = [r for r in requests if r >= head]
next_request = min(next_requests)
head = next_request
requests.remove(next_request)
serviced.append(next_request)

💡 SCAN moves linearly in one direction, servicing all requests on the way.

traverse

SCAN: Continue Moving Up to Request 48 (No Higher Requests)

No requests remain above 48, so the head moves to the highest track (assumed 199) before reversing direction.

💡 SCAN moves to the end of the disk before reversing to service remaining requests.

Line:

if not next_requests:
  head = max_track  # e.g., 199
direction = 'down'

💡 SCAN's linear movement includes moving to the disk end even if no requests are there.

traverse

SCAN: Move Head Down to Next Request (40)

Head moves downwards from 199, servicing requests in descending order. The next request is 40.

💡 After reaching the end, SCAN services requests on the return path.

Line:

next_requests = [r for r in requests if r <= head]
next_request = max(next_requests)
head = next_request
requests.remove(next_request)
serviced.append(next_request)

💡 SCAN services all requests in one direction before reversing.

setup

Initialize C-SCAN Scheduler

Initialize C-SCAN scheduler with head at 50, requests [10, 22, 20, 2, 40, 6, 38, 48], and direction moving upwards.

💡 C-SCAN moves head in one direction only, jumping back to start after reaching the end.

Line:

head = 50
requests = [10, 22, 20, 2, 40, 6, 38, 48]
direction = 'up'
serviced = []

💡 C-SCAN's unidirectional movement simplifies wait time analysis.

traverse

C-SCAN: Move Head Up to Next Request (48)

Head moves upwards from 50, servicing requests in ascending order. The next request is 48.

💡 C-SCAN services requests only in one direction, ignoring requests behind the head until it wraps around.

Line:

next_requests = [r for r in requests if r >= head]
next_request = min(next_requests)
head = next_request
requests.remove(next_request)
serviced.append(next_request)

💡 C-SCAN moves linearly and services requests only ahead of the head.

traverse

C-SCAN: Move Head to Disk End and Wrap to Start

After servicing all requests ahead, head moves to disk end (199), then jumps to start (0) without servicing requests during jump.

💡 C-SCAN treats the disk as a circular list, wrapping around to start after reaching the end.

Line:

if not next_requests:
  head = max_track  # 199
  head = 0  # wrap around

💡 This jump avoids servicing requests behind the head until the next upward pass.

traverse

C-SCAN: Service Requests from Start Upwards (2)

After wrapping, head moves upwards from 0, servicing the lowest request 2 first.

💡 C-SCAN services requests only in upward direction after wrap-around.

Line:

next_requests = [r for r in requests if r >= head]
next_request = min(next_requests)
head = next_request
requests.remove(next_request)
serviced.append(next_request)

💡 Requests behind the initial head position are serviced after wrap-around.

reconstruct

Final Step: All Requests Serviced, Calculate Total Head Movement

All requests have been serviced by each scheduler. Calculate total head movement and output the order of servicing.

💡 Final results show the efficiency of each scheduling algorithm.

Line:

return serviced_order, total_head_movement

💡 Comparing total head movement reveals the performance differences between SSTF, SCAN, and C-SCAN.

def sstf_schedule(requests, head):
    serviced = []  # STEP 1
    while requests:  # STEP 2
        distances = {r: abs(head - r) for r in requests}  # STEP 2
        closest = min(distances, key=distances.get)  # STEP 2
        head = closest  # STEP 3
        requests.remove(closest)  # STEP 3
        serviced.append(closest)  # STEP 3
    return serviced  # STEP 14

def scan_schedule(requests, head, max_track=199):
    serviced = []  # STEP 6
    direction = 'up'  # STEP 6
    while requests:  # STEP 7
        if direction == 'up':  # STEP 7
            next_requests = [r for r in requests if r >= head]  # STEP 7
            if next_requests:  # STEP 7
                next_request = min(next_requests)  # STEP 7
                head = next_request  # STEP 7
                requests.remove(next_request)  # STEP 7
                serviced.append(next_request)  # STEP 7
            else:  # STEP 8
                head = max_track  # STEP 8
                direction = 'down'  # STEP 8
        else:  # STEP 9
            next_requests = [r for r in requests if r <= head]  # STEP 9
            if next_requests:  # STEP 9
                next_request = max(next_requests)  # STEP 9
                head = next_request  # STEP 9
                requests.remove(next_request)  # STEP 9
                serviced.append(next_request)  # STEP 9
            else:  # STEP 14
                break  # STEP 14
    return serviced  # STEP 14

def cscan_schedule(requests, head, max_track=199):
    serviced = []  # STEP 10
    direction = 'up'  # STEP 10
    while requests:  # STEP 11
        next_requests = [r for r in requests if r >= head]  # STEP 11
        if next_requests:  # STEP 11
            next_request = min(next_requests)  # STEP 11
            head = next_request  # STEP 11
            requests.remove(next_request)  # STEP 11
            serviced.append(next_request)  # STEP 11
        else:  # STEP 12
            head = max_track  # STEP 12
            head = 0  # STEP 12
    return serviced  # STEP 14

📊

Disk Scheduling - SSTF, SCAN, C-SCAN - Watch the Algorithm Execute, Step by Step

Watching the algorithm step-by-step reveals how each scheduling strategy optimizes disk head movement differently, which is hard to grasp from code alone.

Transition new → ready pid:SSTF - Initialization of SSTF scheduler

SSTF

ready

Ready Queue

empty

Waiting Queue

empty

🖥CPUSSTFt=0

Transition ready → running pid:SSTF - Calculating closest request

SSTF

running

Ready Queue

empty

Waiting Queue

empty

🖥CPUSSTFt=1

SSTF

Transition running → running pid:SSTF - Moved head and serviced request 48

SSTF

running

Ready Queue

empty

Waiting Queue

empty

🖥CPUSSTFt=2

SSTF

Transition running → running pid:SSTF - Calculating next closest request

SSTF

running

Ready Queue

empty

Waiting Queue

empty

🖥CPUSSTFt=3

SSTF

Transition running → running pid:SSTF - Moved head and serviced request 40

SSTF

running

Ready Queue

empty

Waiting Queue

empty

🖥CPUSSTFt=4

SSTF

Transition new → ready pid:SCAN - Initialization of SCAN scheduler

SCAN

ready

Ready Queue

empty

Waiting Queue

empty

🖥CPUSCANt=0

Transition ready → running pid:SCAN - Moved head and serviced request 48

SCAN

running

Ready Queue

empty

Waiting Queue

empty

🖥CPUSCANt=1

SCAN

Transition running → running pid:SCAN - Moved head to disk end and reversed direction

SCAN

running

Ready Queue

empty

Waiting Queue

empty

🖥CPUSCANt=2

SCAN

Transition running → running pid:SCAN - Moved head and serviced request 40

SCAN

running

Ready Queue

empty

Waiting Queue

empty

🖥CPUSCANt=3

SCAN

Transition new → ready pid:C-SCAN - Initialization of C-SCAN scheduler

C-SCAN

ready

Ready Queue

empty

Waiting Queue

empty

🖥CPUC-SCANt=0

Transition ready → running pid:C-SCAN - Moved head and serviced request 48

C-SCAN

running

Ready Queue

empty

Waiting Queue

empty

🖥CPUC-SCANt=1

C-SCAN

Transition running → running pid:C-SCAN - Moved head to disk end and wrapped to start

C-SCAN

running

Ready Queue

empty

Waiting Queue

empty

🖥CPUC-SCANt=2

C-SCAN

Transition running → running pid:C-SCAN - Moved head and serviced request 2

C-SCAN

running

Ready Queue

empty

Waiting Queue

empty

🖥CPUC-SCANt=3

C-SCAN

Transition running → terminated pid:SSTF - All requests serviced

SSTF

terminated

burst: 0

SCAN

terminated

burst: 0

C-SCAN

terminated

burst: 0

Ready Queue

empty

Waiting Queue

empty

🖥CPUidlet=14

SSTF

SCAN

C-SCAN

Key Takeaways

✓ SSTF minimizes immediate seek time by always choosing the closest request next.

This greedy approach is intuitive but can cause starvation for far requests, which is clearer when watching the head movements step-by-step.

✓ SCAN moves the head in one direction servicing all requests until it reaches the end, then reverses direction.

Visualizing SCAN shows how it reduces seek time by avoiding random jumps, unlike SSTF, but still services all requests fairly.

✓ C-SCAN treats the disk as a circular list, moving in one direction and jumping back to start without servicing requests on the return.

Watching C-SCAN's wrap-around clarifies how it provides more uniform wait times compared to SCAN.

Practice

1. Trace the sequence of checks the Banker's Algorithm performs when a process requests additional resources. Which step occurs immediately after verifying the request does not exceed the process's declared maximum need?

easy

A. The algorithm preempts resources from other processes to fulfill the request.

B. The algorithm immediately grants the request without further checks.

C. The algorithm simulates allocation and checks if the system remains in a safe state.

D. The algorithm checks if the requested resources are currently available in the system.

Solution

1. Step 1: Recall the Banker's Algorithm request sequence

   First, it checks if the request is within the process's maximum declared need.

2. Step 2: Next step after need check

   The algorithm then verifies if the requested resources are available in the system's current available pool.

3. Step 3: Subsequent steps

   If available, it simulates allocation and checks for safe state, but this occurs after availability check.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Availability check precedes simulation to avoid unnecessary computation.

Hint: Request ≤ Need -> check availability -> simulate safe state [OK]

Common Mistakes:

• Assuming simulation happens before availability check
• Believing requests are granted immediately after need check
• Thinking preemption is part of Banker's Algorithm

2. When a file grows beyond the capacity of direct block pointers in its inode, what sequence of steps occurs to locate the additional data blocks?

easy

A. The file system uses single indirect pointers to reference blocks that contain further direct block pointers.

B. The inode immediately switches to double indirect pointers, skipping single indirect pointers.

C. The file system allocates new direct pointers dynamically within the inode structure.

D. The inode stores the entire file content directly once direct pointers are exhausted.

Solution

1. Step 1: Recall inode pointer hierarchy

   Inodes have a fixed number of direct pointers, followed by single, double, and triple indirect pointers for larger files.

2. Step 2: Understand pointer escalation

   When direct pointers are full, the file system uses single indirect pointers, which point to blocks containing more direct pointers.

3. Step 3: Eliminate incorrect escalations

   The inode does not skip levels; it uses single indirect before double indirect pointers.

4. Step 4: Clarify inode content storage

   Inodes never store file content directly; they only store metadata and pointers.

5. Final Answer:

   Option A -> Option A

6. Quick Check:

   Single indirect pointers extend data block addressing after direct pointers [OK]

Hint: Direct -> Single Indirect -> Double Indirect pointer escalation

Common Mistakes:

• Skipping pointer levels (double indirect before single indirect)
• Assuming inode can dynamically add direct pointers
• Thinking inode stores file content directly

3. Which of the following statements about the five-state process model is INCORRECT?

medium

A. The New state represents a process that is being created but not yet ready to run

B. The Waiting state is used when a process is blocked for I/O completion

C. A process in the Terminated state can be moved back to Ready state if needed

D. The Running state means the process is currently executing on the CPU

Solution

1. Step 1: Review each statement

   A, B, and D correctly describe standard process states.
   C incorrectly states that a Terminated process can return to Ready, which violates the model.

2. Step 2: Understand Terminated state

   Terminated means process execution is complete; it cannot be restarted or moved back.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Terminated processes cannot be revived in the five-state model [OK]

Hint: Terminated means final; no return to Ready [OK]

Common Mistakes:

• Thinking Terminated processes can be restarted
• Confusing Waiting with Ready state
• Misunderstanding New state as Ready

4. Which of the following statements about non-preemptive SJF scheduling is INCORRECT?

medium

A. Once a process starts executing, it cannot be preempted until completion

B. It selects the process with the shortest burst time from the ready queue when CPU is free

C. It can lead to longer average waiting time compared to preemptive SJF

D. It guarantees no starvation of any process

Solution

1. Step 1: Understand starvation in non-preemptive SJF

   Non-preemptive SJF can cause starvation if short jobs keep arriving, delaying longer jobs indefinitely.

2. Step 2: Analyze other options

   A: Correct, non-preemptive means no interruption once started.
   B: Incorrect, non-preemptive SJF does not guarantee no starvation.
   C: Correct, it can lead to longer average waiting time compared to preemptive SJF.
   D: Correct, selection is based on shortest burst time when CPU is free.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Non-preemptive SJF does not guarantee no starvation; starvation can occur.

Hint: Non-preemptive SJF can starve long processes if short ones keep arriving [OK]

Common Mistakes:

• Assuming non-preemptive SJF prevents starvation
• Confusing preemptive and non-preemptive behavior

5. If a system enforces a strict ordering of resource acquisition to prevent circular wait, which of the following is a potential drawback that an interviewer might probe?

hard

A. Processes may experience increased waiting time due to forced ordering, reducing concurrency.

B. The system can still deadlock due to hold and wait despite ordering.

C. No preemption condition is violated by enforcing ordering.

D. Mutual exclusion is no longer required when ordering is enforced.

Solution

1. Step 1: Understand resource ordering

   Ordering resources prevents circular wait by forcing processes to request resources in a global order.

2. Step 2: Identify drawbacks

   Strict ordering can cause processes to wait longer than necessary, reducing concurrency and system throughput.

3. Step 3: Analyze other options

   The system can still deadlock due to hold and wait despite ordering is incorrect because ordering eliminates circular wait, thus preventing deadlock from that condition. No preemption condition is violated by enforcing ordering is false; ordering does not violate no preemption. Mutual exclusion is no longer required when ordering is enforced is false; mutual exclusion is still required for non-shareable resources.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Ordering trades off concurrency for deadlock prevention.

Hint: Ordering resources prevents circular wait but can reduce concurrency [OK]

Common Mistakes:

• Believing ordering removes all deadlock conditions
• Confusing ordering with preemption
• Assuming mutual exclusion is eliminated by ordering