Subheading : On brief research on Disk I/O schedulers

Today, I researched about the disk I/O scheduling. The disk I/O scheduler is a scheduler that schedules disk I/O requests. Before the block device driver, the requests go on the scheduling process and are then sent to the driver. The scheduler often sorts or merges the requests into one request or changes the reading sequence into efficient requests to optimize the I/O operations.

source : ji007, tistory

The device driver has a queue that maintains the kernel's requests. The I/O scheduler mainly strives to reduce the movements of the head and the minimum starvation of the request. There are many disk I/O scheduling algorithms, and I have to implement the scheduler based on one of these algorithms... (Gosh, this is going to be hard..)

Sources of this information on these algorithms are this book and this book.

1. FCFS Algorithm

It's a simple algorithm. First Comes, First Served. Most straightforward and most inefficient. The book shows some excellent diagrams about the problem of swing in FCFS.. and I'm not going to paste that here. (Search up Google, and you'll get many images like that.)

2. SSTF Algorithm

The SSTF stands for Shortest Seek Time First. As the name implies, the algorithm prioritizes the closest request (= has the shortest seek time) to the current head location.

Advantages

1. Able to maximize the throughput. The time to move the head is minimized, so the time to actually read the data is maximized.
2. Quite efficient in batch systems.
3. Better than FCFS

Disadvantages

1. Some requests can experience starvation. Say, we have requests for sectors 20, 30, and 100. Theoretically, when we keep getting the requests closer to sectors 20 and 30, the sector 100 requests will wait forever.
2. There could be a high difference in response time between the outer track and the inner track.

3. SCAN Algorithm

The SCAN algorithm is often called the Elevator Algorithm because its mechanism is very similar to how an elevator works. Basically, the algorithm runs similarly to SSTF. Still, the difference is that it prioritizes the closest request in the direction the head is currently going. When the head reaches the end, the head changes direction and handles requests.

Advantages

1. Quite easy to implement

Disadvantages

1. Requests in the opposite direction will experience high response time or even starvation.

4. LOOK Algorithm

LOOK algorithm is a variation of the SCAN algorithm. The twist is that it doesn't go to the end of the track. Instead, it only moves until the last requested track. A Little bit of a decrease in head movement.

5. C-SCAN Algorithm

C-SCAN(Circular SCAN) is another variation of SCAN. While the SCAN algorithm only changes direction when it reaches the end of the track, the C-SCAN moves entirely to the start position.

source : geeksforgeeks

As you can see, when the head reaches the end, the head circulates back to the start of the track. Unlike the SCAN algorithm, the head's direction is not changed. Still, the position of the head circulates back to the starting track position.

Advantages(Compare to SCAN)

1. Fixed SCAN's unfair response time by circulating the track(like a circular queue.)
2. The deviation between the outer track and the inner track decreases.

...

Now that I know basic stuff about disk I/O scheduling, I have to figure out how to actually implement these algorithms into my kernel. But we need more than these algorithms. The Disk I/O scheduler also requires more than just changing the order of requests. The proper I/O scheduler has to merge the requests into one(if possible). Nevertheless, my first priority is figuring out how to make a disk I/O scheduler... At least I have to make a working I/O scheduler, no matter its algorithm. Oh, by the way, we also gotta learn about caching in disk I/O... (so much learning to do!)