Search This Blog

Friday, March 27, 2009

Disk Scheduling In Linux

In a disk, an access time is too big, since it has a mechanical part - disk head which is moving on the disk. It makes overwhole performance of a disk too poor.

Formal problem statement:

Input: A set of requests
Input: The current disk head location
Input: Algorithm state (direction)

Output: the next disk block to get

The goals:

1. Maximize throughput
2. Maximize fairness
3. Avoid starvation
4. Real time concerns

Some scheduling algorithms:

1. A pessimal algorithm
2. An optimal algorithm - shortest service time first
3. First come first serve
4. Elevator
5. Cyclic elevator
6. Deadline scheduler
7. Anticipatory scheduling
8. Completely fair queuing

Conclusion:

Andrew Morton said, "the anticipatory shceduler is wiping the others off the map!"

No comments:

Post a Comment

Blog Archive