SSTF (Shortest Seek Time First) in Operating Systems - Full Explanation

Introduction

Imagine waiting for a library assistant to fetch books from different shelves. The order in which the assistant picks books can make the wait longer or shorter. SSTF helps decide which request to handle next to reduce waiting time in disk operations.

Explanation

Purpose of SSTF

SSTF is a method used by operating systems to decide the order of disk read/write requests. It picks the request closest to the current position of the disk head to minimize movement. This reduces the time the disk takes to access data.

SSTF chooses the nearest request to reduce disk head movement and access time.

How SSTF Works

When multiple requests are waiting, SSTF calculates the distance from the current head position to each request. It then selects the request with the shortest distance. This process repeats after each request is served, always picking the closest next request.

SSTF always selects the next request with the shortest seek distance from the current head position.

Advantages of SSTF

By reducing the distance the disk head moves, SSTF can improve overall performance compared to simple methods like First-Come-First-Served. It lowers average waiting time and speeds up data access in many cases.

SSTF improves disk efficiency by lowering average seek time compared to simpler scheduling methods.

Limitations of SSTF

SSTF can cause some requests to wait too long if they are far from the current head position, leading to a problem called starvation. It also does not guarantee the shortest total movement over all requests, only the next closest one.

SSTF may cause starvation for distant requests and does not always minimize total disk movement.

Real World Analogy

Imagine a librarian fetching books from shelves arranged in a line. Instead of fetching books in the order requested, the librarian always picks the book closest to their current position to save walking time. However, some books far away might have to wait longer.

Purpose of SSTF → Librarian choosing the closest book to fetch next to save walking time

How SSTF Works → Librarian checking distances to all requested books and picking the nearest one

Advantages of SSTF → Librarian reducing total walking distance compared to fetching books in request order

Limitations of SSTF → Books far away waiting longer because librarian keeps picking closer books

Diagram

Diagram

Current Head Position
      ↓
┌─────┬─────┬─────┬─────┬─────┬─────┐
│  10 │  22 │  20 │  2  │  40 │  6  │
└─────┴─────┴─────┴─────┴─────┴─────┘
Requests: 2, 6, 10, 20, 22, 40
SSTF picks 10 first (closest), then 6, then 2, and so on.

This diagram shows disk requests on a line with the current head position and the order SSTF picks requests based on shortest distance.

Key Facts

SSTF → A disk scheduling algorithm that selects the request closest to the current head position.

Seek Time → The time it takes for the disk head to move to the track where data is stored.

Starvation → A situation where some requests wait indefinitely because others are always closer.

Disk Head → The part of the disk that reads or writes data by moving over tracks.

Code Example

Operating Systems

def sstf_schedule(requests, head):
    requests = requests.copy()
    order = []
    while requests:
        distances = {r: abs(r - head) for r in requests}
        closest = min(distances, key=distances.get)
        order.append(closest)
        head = closest
        requests.remove(closest)
    return order

# Example usage
requests = [10, 22, 20, 2, 40, 6]
head = 15
print(sstf_schedule(requests, head))

Common Confusions

SSTF always gives the fastest overall disk access.

SSTF always gives the fastest overall disk access. SSTF only picks the closest next request, but this does not guarantee the shortest total movement or fastest overall completion.

SSTF prevents all requests from waiting too long.

SSTF prevents all requests from waiting too long. SSTF can cause starvation where some requests far from the head position wait much longer than others.

Summary

SSTF reduces disk seek time by always choosing the closest request next.

It improves performance but can cause some requests to wait too long (starvation).

SSTF does not guarantee the shortest total disk movement, only the next shortest seek.

Practice

1. What does SSTF (Shortest Seek Time First) disk scheduling algorithm prioritize?

easy

A. The request closest to the current head position

B. The request that arrived first

C. The request farthest from the current head position

D. Requests in a fixed circular order

Solution

1. Step 1: Understand SSTF purpose

   SSTF aims to reduce the seek time by choosing the disk request nearest to the current head position.

2. Step 2: Compare options with SSTF behavior

   Only the request closest to the current head position matches this behavior; others describe different algorithms.

3. Final Answer:

   The request closest to the current head position -> Option A

4. Quick Check:

   SSTF = closest request [OK]

Hint: Pick the request nearest to the head position [OK]

Common Mistakes:

• Confusing SSTF with FCFS (First Come First Serve)
• Thinking SSTF picks requests in arrival order
• Assuming SSTF picks the farthest request

2. Which of the following is the correct way to describe SSTF in disk scheduling?

easy

A. It processes requests in the order they arrive.

B. It selects the request with the longest waiting time first.

C. It selects the request closest to the current head position.

D. It moves the head in one direction servicing all requests.

Solution

1. Step 1: Review SSTF definition

   SSTF selects the disk request closest to the current head position to minimize seek time.

2. Step 2: Match options with SSTF behavior

   The option "It selects the request closest to the current head position." correctly describes SSTF. Other options describe different algorithms like FCFS or SCAN.

3. Final Answer:

   It selects the request closest to the current head position. -> Option C

4. Quick Check:

   SSTF = closest request selection [OK]

Hint: Remember SSTF picks nearest request, not oldest [OK]

Common Mistakes:

• Mixing SSTF with FCFS or SCAN algorithms
• Assuming SSTF picks requests by waiting time
• Confusing direction-based scheduling with SSTF

3. Given the disk head is at position 50 and requests are at positions [45, 70, 10, 55], which request will SSTF service first?

medium

A. 45

B. 70

C. 10

D. 55

Solution

1. Step 1: Calculate distances from head position 50

   Distances: 45 (5), 70 (20), 10 (40), 55 (5)

2. Step 2: Identify closest request

   Requests at 45 and 55 are both 5 units away. SSTF can pick either, but usually picks the first closest found, here 45.

3. Final Answer:

   45 -> Option A

4. Quick Check:

   Closest request = 45 [OK]

Hint: Calculate absolute distance, pick smallest [OK]

Common Mistakes:

• Choosing the farthest request by mistake
• Ignoring equal distances and picking wrong one
• Confusing SSTF with FCFS order

4. A disk head is at position 30. Requests are at [35, 25, 40, 20]. A student incorrectly picks 40 as the next request in SSTF. What is the error?

medium

A. They ignored the current head position.

B. They chose the farthest request instead of the closest.

C. They picked the request with the longest waiting time.

D. They selected requests in arrival order.

Solution

1. Step 1: Calculate distances from head position 30

   Distances: 35 (5), 25 (5), 40 (10), 20 (10)

2. Step 2: Identify correct SSTF choice

   Closest requests are 35 and 25 (5 units away). Choosing 40 (10 units) is incorrect.

3. Final Answer:

   They chose the farthest request instead of the closest. -> Option B

4. Quick Check:

   SSTF picks closest, not farthest [OK]

Hint: Always pick request with minimum distance [OK]

Common Mistakes:

• Picking requests based on arrival time
• Ignoring actual distances from head
• Confusing SSTF with other algorithms

5. A disk head starts at position 100. The request queue is [120, 89, 130, 80, 110]. Using SSTF, what is the order in which requests will be serviced?

hard

A. [110, 120, 130, 89, 80]

B. [89, 80, 110, 120, 130]

C. [110, 120, 89, 80, 130]

D. [110, 89, 80, 120, 130]

Solution

1. Step 1: Start at head position 100 and find closest request

   Distances: 120(20), 89(11), 130(30), 80(20), 110(10). Closest is 110 (10 units).

2. Step 2: Move head to 110 and repeat

   Remaining: 120(10), 89(21), 130(20), 80(30). Closest is 120 (10).

3. Step 3: Move head to 120 and repeat

   Remaining: 89(31), 130(10), 80(40). Closest is 130 (10).

4. Step 4: Move head to 130 and repeat

   Remaining: 89(41), 80(50). Closest is 89 (41).

5. Step 5: Move head to 89 and last request is 80 (9 away)

   Order: 110, 120, 130, 89, 80.

6. Final Answer:

   [110, 120, 130, 89, 80] -> Option D

7. Quick Check:

   SSTF services closest request each step [OK]

Hint: Pick closest request step-by-step from current head [OK]

Common Mistakes:

• Not updating head position after each request
• Choosing requests by arrival order
• Ignoring equal distances and picking wrong request