CSE506: Block Device Scheduling (DRAFT)

The big picture:

From ref1: "Below the generic block layer, the "I/O scheduler " sorts the pending I/O data transfer requests according to predefined kernel policies. The purpose of the scheduler is to group requests of data that lie near each other on the physical medium. "
Scheduling的目的:
1. Throughput, Latency,
2. Safety: file system can be recovered after a crash
3. Fairness – surprisingly, very little attention is given to storage access fairness

Problems:
- Between page cache and disk, you have a queue of pending requests
- Requests are a tuple of (block #, read/write, buffer addr)
- You can reorder these as you like to improve throughput

Below is from ref2.
Elevator Algorithm
- 像搭電梯一樣, 要上樓就把所有人一起往上載, 要下樓就一起往下載
idea: Require disk arm to move in continuous “sweeps” in and out
- Reorder requests within a sweep
- This approach prevents starvation: Sectors at “inside” or “outside”get service after a bounded time

Complete Fairness Queue
- 利用round robin 保證每個request公平的被分到
idea: add a second layer of queue, one per process. Then do the round-robin.
(x) Ping-pong disk head around

Deadline Scheduler
- Deadline快到的先被執行
idea: associate expiration time with requests. As requests get close to expiration, make sure they are deployed. Good for real time applications.

Anticipatory Scheduler
- 當某個Process有burstness特性時, 先等一下 (batching), 然後在一起執行
idea: Try to anticipate locality of requests
If process P tends to issue bursts of requests for close disk blocks, When you see are quest from P, wait a bit and see if more come in before scheduling them

Reference:
1. Understanding the Linux Kernel, Chapter 14.3
2. cse506 slide by Don Porter