Operating System | Disk Scheduling

DISK SCHEDULING

As processor and main memory speeds increase more rapidly than those of secondary storage devices, optimizing disk performance has become important to realizing optimal performance. Magnetic storage records data by changing the direction of magnetization of regions, each representing a 1 or a 0.
Disk provides the primary on-line storage of information, both programs and data. All the important programs of the system such as compiler, assemblers, loaders, editors, etc. are stored on the disk until loaded into memory. Hence it becomes all-important to properly manage the disk storage and it scheduling.
The disk speed is composed of three parts:
(a) Seek Time
(b) Latency Time
(c) Transfer time

INR31,500

Seek Time
To access a block from the disk, first of all the system has to move the read/write head to the required position. The time consumed in this operation is known as seek time and the head movement is called seek.
Seek time (S) is determined in terms of:
I: startup delays in initiating head movement.
H: the rate at which read/write head can be moved.
C: How far the head must travel. S = H * C + I

Latency Time -
Once the head is positioned at the right track, the disk is to be rotated to move the desired block under the read/write head. This delay is known as latency time.
On average this will be one-half of one revolution. Thus latency can be computed by dividing the number of Revolution Per Minute (RPM), R, into 30.
L = 30 / R

Transfer Time
Finally the actual data is transferred from the disk to main memory. The consumed in this operation is known as transfer time.
Transfer time T, is determined by
the amount of information to be read, B;
the number of bytes per track, N;
and the rotational speed R
T = 60B/RN

So the total time (A) to service a disk request is the sum of these tree i.e. seek time, latency time, and transfer time.

A = S + L + T

Since most of the systems depend heavily on the disk, so it become very important to make the disk service as fast as possible. So a number of variations have been observed in disk organization motivated by the desire to reduce the access time, increase the capacity of the disk and to make optimum use of disk surface.

INR39,639

For a multiprogramming system with many processes, the disk queue may often be non-empty. Thus, when a request is complete, the disk scheduler has to pick a new request from the queue and service it. As apparent, the amount of head movement needed to satisfy a series of I/O requests could affect the performance. For this reason, a number of scheduling algorithms have been proposed.

Disk Scheduling Types-

First Come First Served (FCFS) Scheduling

This form of scheduling is the simplest one but may not provide the best service.
The algorithm is very easy to implement. In it the system picks every time the first request from the disk queue.
In this scheduling the total seek time may be substantially high as evident from the following example:

Considered an ordered disk queue with requests involving tracks: 8
Queue: 86, 140, 23, 50, 12, 89, 14, 120, 64 Head starts at 58

FCFS Disk Scheduling

Shortest Seek Time First (SSTF) Scheduling

This scheduling algorithm services the request whose track position is closest to the current track position.
Shortest-Seek-Time-First selects the request that is asking for minimum seek time from the current head position.
Since seek time is generally proportional to the track difference between the requests, this approach is implemented by moving the head to the closest track in the request queue.
It shows a substantial improvement in disk services i.e. reduction in the total movement of the head resulting into the reduced seek time.

SSTF Disk Scheduling

Scan Scheduling

In this algorithm the read/write head moves back and forth between the innermost and outermost tracks.
As the head gets to each track, satisfies all outstanding requests for that track.
Starvation is possible only if there are repeated requests for the current track.
Also called the elevator algorithm. As it is familiar to the behavior of elevators as they service requests to move from floor to floor in a building.

Scan Disk Scheduling

C-scan (Circular scan) Scheduling

INR3,699 INR 3,969

C-scan is a variant of scan. It is designed to provide a more uniform wait time.
C scan moves the head from one end of the disk to another, servicing requests as it goes.
When it reaches the other end, however, it immediately return to the beginning of the disk, without servicing any requests on the return trip.
C-scan treats the disk, as it was circular, with the last track adjacent to the first one.

Look Disk Scheduling

This algorithm is also similar to scan but unlike scan, the head does not unnecessarily travel to the innermost track and outermost track on each circuit.
Head moves in one direction, satisfying the request for the closest track like scan in that direction.
When there are no more requests in that direction the head is traveling, head reverse the direction and repeat.

N-Step Scan Disk Scheduling

In it the request queue is divided into sub queues with each sub queue having a maximum length of N.
Sub queues are processed in FIFO order. Within a sub queue, requests are processed using Scan. While a sub queue is being serviced, incoming requests are placed in the next non-filled sub queue.
N-step scan eliminates any possibility of starvation.

INR 4099

F-Scan Disk Scheduling

The "F" stands for "freezing" the request queue at a certain time.
It is just like Nstep scan but there are two sub queues only and each is of unlimited length.
While requests in one sub queue are serviced, new requests are placed in other sub queue.

Also Read

Operating System- Deadlock

Operating System-Memory Management

Smart Teaching Board-

INR135,000