Disk Scheduling

From Algorithm Wiki
Jump to navigation Jump to search

Problem Description

File systems must be accessed in an efficient manner, especially with hard drives, which are the slowest part of a computer. As a computer deals with multiple processes over a period of time, a list of requests to access the disk builds up. For efficiency purposes, all requests (from all processes) are aggregated together.

The technique that the operating system uses to determine which requests to satisfy first is called disk scheduling.

Bounds Chart

Disk SchedulingBoundsChart.png

Step Chart

Disk SchedulingStepChart.png

Improvement Table

Complexity Classes Algorithm Paper Links Lower Bounds Paper Links
Exp/Factorial
Polynomial > 3
Cubic
Quadratic
nlogn
Linear [FCFS (1979)]

[SSTF (1979)]

[SCAN (1979)]

[LOOK (1979)]

[C-SCAN (1979)]

[C-LOOK (1979)]

logn