C-SCAN (idea)

C-SCAN is an algorithm used in computer science to control the scheduling of hard disk accesses. It attempts to make the drive as efficient as possible by buffering requests and performing them in a certain order so that a minimum amount of time is spent accelerating and decelerating the disk head.

The mechanical nature of hard disks mean they are unavoidably much slower than the processor and memory using them. A processor could have executed thousands of instructions by the time a hard disk was anywhere near reading the requested data, let alone returning it. For this reason, it is imperative for the performance of a computer to schedule the disk accesses in an efficient way, so that the disk head spends the maximum amount of time reading/writing, and the minimum amount of time moving between cylinders.

There are a number of different approaches, including the noddy First in first out (FIFO) algorithm and the slightly better Shortest seek time first (SSTF). However, the approach that C-SCAN takes is faster than either of these two algorithms, and offers much better guarantees about the maximum amount of time before an access is performed.

The algorithm itself resembles another scheduling system, SCAN (also known as the Elevator algorithm), except C-SCAN is cyclic, hence the name. It is very simple:

• perform the waiting access with the next highest block number
• if there are no waiting accesses with higher block numbers, return the head to block zero

For example, suppose that there are accesses waiting to be performed on block numbers { 101, 500, 23, 354, 272, 32, 65, 365, 164. 493 } with the head already at block number 200. The order of accesses would be 272 => 354 => 365 => 493 => 500 here the edge of the disk is reached and the head reset to zero. The accesses continue: 23 => 32 => 65 => 101 => 164.

Unlike other scheduling algorithms, C-SCAN manages to prevent starvation. This is when, for whatever reason, a particular access takes an inordinate amount of time to be performed, thereby delaying the execution of a process waiting for that access to complete. As the head is always moving up through the disk, the worst-case scenario is an access that is requested just after the head has passed the relevant block. Even in this case, the access will definitely be performed on the next pass of the head, which would almost certainly be very soon.

Also, because the head only performs accesses on increasing block numbers, when the head skips back to the start of the disk, there is likely to be a large number of accesses to be performed there, keeping the head very efficiently utilised. Compare this to algorithms that perform accesses on increasing and decreasing block numbers. At the extremities of the disk, when the head turns round and begins to make its pass back in the opposite direction, there is going to be very few available accesses as they have all just been done in that area of the disk. A good analogy I have heard is to do with snowploughs. While one system might slowly plough both ways up and down a road, our plough, like C-SCAN, ploughs slowly in one direction, then returns quickly to the other end and ploughs again in the same direction. The advantage is that when the first plough turns round, there's not going to be any snow just behind it, so there's no point in making the effort of actually ploughing. The second plough knows this and returns to the start of the road where there is lots of snow, and his plough will be better employed.

Most modern hard disks will implement scheduling themselves, rather than rely on an intelligent OS. A small chip inside the disk casing will cache and buffer data so that the OS can transperently expect disk accesses to be done efficiently, without having any knowledge of how it's done or what disk architecture features are being used.