Time Complexity: Why disk scheduling reduces seek time
O(n log n)
0
0
Why disk scheduling reduces seek time in Operating Systems - Performance Analysis
Understanding Time Complexity
We want to understand how disk scheduling affects the time it takes to move the disk head.
Specifically, how does organizing requests reduce the total movement needed?
Scenario Under Consideration
Analyze the time complexity of this simplified disk scheduling approach.
requests = [55, 58, 39, 18, 90, 160, 150, 38, 184]
head = 50
# Sort requests to minimize seek
requests.sort()
for req in requests:
move_head_to(req)
This code sorts disk requests to reduce the total distance the disk head moves.
Identify Repeating Operations
Look for repeated actions that affect time.
- Primary operation: Moving the disk head to each request.
- How many times: Once for each request in the list.
How Execution Grows With Input
As the number of requests grows, the total head movement depends on their order.
| Input Size (n) | Approx. Operations (head moves) |
|---|---|
| 10 | 10 moves, optimized order reduces distance |
| 100 | 100 moves, sorting helps reduce total movement |
| 1000 | 1000 moves, scheduling keeps movement efficient |
Pattern observation: The number of moves grows linearly, but sorting reduces wasted movement between requests.
Final Time Complexity
Time Complexity: O(n log n)
This means the main cost comes from sorting the requests, which helps reduce the total head movement time.
Common Mistake
[X] Wrong: "Disk scheduling makes the disk head move fewer times."
[OK] Correct: The disk head still moves once per request, but scheduling reduces the distance it travels between requests.
Interview Connect
Understanding how disk scheduling reduces seek time shows your grasp of optimizing resource use, a key skill in system design and performance.
Self-Check
What if we processed requests in the order they arrive without sorting? How would the time complexity and seek time change?