What are the various Desk Scheduling methods?

About Disk Scheduling

The I/O system has got the following layers:

1. User processes: The functions of this layer including making I/O calls, formatting the I/O and spooling.
2. Device independent software: Functions are naming, blocking, protection, allocating and buffering.
3. Device drivers: Functions include setting up the device registers and checking their status.
4. Interrupt handlers: These perform the function of waking up the I/O drivers up on the completion of the I/O.
5. Hardware: Performing the I/O operations.

- Disk drives can be pictured as large 1 – D array consisting of logical blocks that are smallest unit of transfer.  

- These blocks are mapped in to the disk sectors in a sequential manner. 

- Mapping is done in the same manner. 

- The responsibility of using the hardware efficiently is the duty of the operating system for the disk drives for increasing the speed of access and bandwidth of the disk. 

Algorithms for Scheduling Disk Requests

There are several algorithms existing for the scheduling of the disk requests:

Ø  SSTF: 

- In this method the request having the minimum seek time is selected from the present head position. 

- This method is a modification of the SJF (shortest job first) scheduling and therefore contains some possibility of process starvation.

Ø  SCAN: 

- From one end of the disk, the disk arm starts and continues in the direction of the other end, serving to the requests till the opposite end. 

- At this end the head is reversed and the process continues. 

- This is sometimes called as the elevator algorithm.

Ø  C – SCAN: 

- A better algorithm then the previous one. 

- This one offers a more uniform waiting time than the previous one. 

- The movement of the head is from one end to another while it services the requests encountered along the way. 

- However, the difference is that when it comes to the other it straightaway goes to the beginning without heeding to any of the requests in the way and then again starts. 

- The cylinders are treated as the circular list wrapped around last and the first cylinder.

Ø  C – Look: 

- This is a modified version of the C – SCAN. 

- Here the arm or the head travels only up to the last request rather than going till the far end. 

- Then immediately the direction is reversed and the process continues.

- For disk scheduling it is important that the method be selected as per the requirements only. 

- The first one is the most commonly used and appeals to the needs naturally. 

- For a system where often there is a heavy load on the disk, the SCAN and C- SCAN methods can help. 

- The number as well as the kind of requests affects the performance in a number of ways.

- On the other hand, the file – allocation method influences the requests for the disk services. 

- These algorithms have to be written as an individual module of the OS so that if required it can be replaced with a different one easily. 

- As a default algorithm, the LOOK or the SSTF is the most reasonable choice. 

Ways to attach to a disk

There are two ways of attaching the disk:

Ø  Network attached: This attachment is made via a network. This is called the network attached storage. All such connected storage devices together form the storage area network.

Ø  Host attached: This attachment is made via the I/O port.

All these disk scheduling methods are for the optimization of the secondary storage access and for making the whole system efficient. 

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.