C-SCAN Scheduling and LOOK Scheduling

Circular SCAN is a variant of SCAN that is designed to provide a more uniform wait time. Like SCAN, C-SCAN moves the head from one end of the disk to the other, servicing requests along the way. When the head reaches the other end, however, it immediately returns to the beginning of the disk, without servicing any requests on the return trip. The C-SCAN scheduling algorithm essentially treats the cylinders as a circular list that wraps around from the final cylinder to the first one.

Both SCAN and C-SCAN move the disk arm across the full width of the disk. In practice, neither of the algorithm is implemented this way. More commonly, the arm goes only as far as the final request in each direction. Then, it reverses the direction immediately, without first going all the way to the end of the disk. These versions of SCAN and C-SCAN are called LOOK and C-LOOK scheduling.

How to select a Disk Scheduling algorithm ?
With any scheduling algorithm, performance depends heavily on the number and types of requests. Suppose that the queue has just one request, then, all the scheduling algorithms are forced to behave the same, because they have no choice except one. They all behave like FCFS scheduling.
The requests for disk service can be greatly influenced by the file allocation method. The location of directories and index blocks is also important. Since every file must be opened to be used, and opening a file requires searching the directory structure, the directories will be accessed frequently.
The disk scheduling algorithm should be written as a separate module so that it can be replaced with a different algorithm if necessary. Either SSTF or LOOK is a reasonable choice for default algorithm.

Disk Scheduling Algorithm - SCAN Scheduling

In this algorithm the head always constantly moves from the most inner cylinder to the outer cylinder, then it changes its direction back towards the center. As the head moves, if there is a request for the current disk position it is satisfied. The throughput is better than in FIFO. The SCAN algorithm is more fair that SSTF. This algorithm is named after the behavior of a building elevator, where the elevator continues to travel in its current direction (up or down) until empty, stopping only to let individuals off or to pick up new individuals heading in the same direction.



The arm movement is thus always less than twice the number of total cylinders then, for both versions of the elevator algorithm. The variation has the advantage to have a smaller variance in response time. The algorithm is also relatively simple.
However, the elevator algorithm is not always better than Shortest seek first, which is slightly closer to optimal, but can result in high variance in response time and even in starvation when new requests continually get serviced prior to existing requests.
Anti-starvation techniques can be applied to the shortest seek time first algorithm to guarantee an optimum response time.

Disk Scheduling Algorithm - SSTF Scheduling

Shortest seek first (or shortest seek time first) is a secondary storage scheduling algorithm to determine the motion of the disk's arm and head in servicing read and write requests. This is a direct improvement upon a first-come first-served (FIFO) algorithm. The drive maintains an incoming buffer of requests, and tied with each request is a cylinder number of the request. Lower cylinder numbers indicate that the cylinder is closest to the spindle, and higher numbers indicate the cylinder is further away.

The shortest seek first algorithm determines which request is closest to the current position of the head, and then services that request next. The shortest seek first algorithm has the direct benefit of simplicity and is clearly advantageous in comparison to the FCFS method, in that overall arm movement is reduced, resulting in lower average response time.

However, since the buffer is always getting new requests, these can skew the service time of requests that may be farthest away from the disk head's current location, if the new requests are all close to the current location; in fact, starvation may result, with the faraway requests never being able to make progress.
SSTF scheduling is essentially a form of shortest-job-first (SJF) scheduling, and like SJF scheduling, it may cause starvation of some requests.

Disk Scheduling Algorithm - FCFS Scheduling

Scheduling is a key concept in computer multitasking, multiprocessing operating system and real-time operating system designs. The scheduler is concerned mainly with :
* CPU utilization - to keep the CPU as busy as possible.
* Throughput - number of process that complete their execution per time unit.
* Turnaround - total time between submission of a process and its completion.
* Waiting time - amount of time a process has been waiting in the ready queue.
* Response time - amount of time it takes from when a request was submitted until the first response is produced.
* Fairness - Equal CPU time to each thread.

Scheduling Algorithms :
CPU scheduling deals with the problem of deciding which of the processes in the ready queue is to be allocated the CPU. There are many different CPU scheduling algorithms.

- First Come First Served (FCFS): The disk controller processes the I/O requests in the order in which they arrive, thus moving backwards and forwards across the surface of the disk to get to the next requested location each time. Since no reordering of request takes place the head may move almost randomly across the surface of the disk. This policy aims to minimize response time with little regard for throughput.
Illustration shows total head movement of 640 cylinders.
queue = 98, 183, 37, 122, 14, 124, 65, 67
Head starts at 53.



The problem with this schedule is illustrated by the wide swing from 122 to 14 and then back to 124. If the requests for cylinders 37 and 14 could be serviced together, before or after the requests at 122 and 124, the total head movement could be decreased substantially, and performance could be improved.