Disc scheduling Algorithms

Disk scheduling is done by operating systems to schedule I/O requests arriving for the disk. Disk scheduling is also known as I/O scheduling.

Key Terms :

Seek Time:Seek time is the time taken to locate the disk arm to a specified track where the data is to be read or write. So the disk scheduling algorithm that gives minimum average seek time is better.

Head : Is defined as the starting position of the disk arm

The Types

The following are six different types of Disc scheduling algorithms.

FCFS

The requests are addressed in the order they arrive in the disk queue.

Know More

SSTF

Requests having shortest seek time are executed first.

Know More

CSCAN

The disk arm again scans the path that has been scanned, after reversing its direction.

Know More

LOOK

Disk arm in spite of going to the end of the disk goes only to the last request to be serviced in front of the head and then reverses its direction from there.

Know More

SCAN

The disk arm moves into a particular direction and services the requests coming in its path and after reaching the end of disk, it reverses its direction.

Know More

CLOOK

The disk arm in spite of going to the end goes only to the last request to be serviced in front of the head and then from there goes to the other end’s last request.

Know More

FCFS Algorithm

The Algorithm

FCFS is the simplest disk scheduling algorithm. As the name suggests, this algorithm entertains requests in the order they arrive in the disk queue. The algorithm looks very fair and there is no starvation (all requests are serviced sequentially) but generally, it does not provide the fastest service

Step1

Let Request array represents an array storing indexes of tracks that have been requested in ascending order of their time of arrival. ‘head’ is the position of disk head.

Step2

Let us one by one take the tracks in default order and calculate the absolute distance of the track from the head.

Step3

Increment the total seek count with this distance.

Step4

Currently serviced track position now becomes the new head position

Step5

Go to step 2 until all tracks in request array have not been serviced.

Calculate

CSCAN Algorithm

The Algorithm

C-SCAN moves the head from one end servicing all the requests to the other end. However, as soon as the head reaches the other end, it immediately returns to the beginning of the disk without servicing any requests on the return trip (see chart below) and starts servicing again once reaches the beginning. !

Step1

Let Request array represents an array storing indexes of tracks that have been requested in ascending order of their time of arrival. ‘head’ is the position of disk head.

Step2

The head services only in the right direction from 0 to size of the disk.

Step3

While moving in the left direction do not service any of the tracks

Step4

When we reach at the beginning(left end) reverse the direction.

Step5

While moving in right direction it services all tracks one by one.

Step6

While moving in right direction calculate the absolute distance of the track from the head.

Step7

Increment the total seek count with this distance.

Step8

Currently serviced track position now becomes the new head position.

Step9

Go to step 6 until we reach at right end of the disk.

Step10

If we reach at the right end of the disk reverse the direction and go to step 3 until all tracks in request array have not been serviced.

Calculate

LOOK Algorithm

The Algorithm

The LOOK algorithm services request similarly as SCAN algorithm meanwhile it also “looks” ahead as if there are more tracks that are needed to be serviced in the same direction. If there are no pending requests in the moving direction the head reverses the direction and start servicing requests in the opposite direction.

Step1

Let Request array represents an array storing indexes of tracks that have been requested in ascending order of their time of arrival. ‘head’ is the position of disk head.

Step2

The intial direction in which head is moving is given and it services in the same direction.

Step3

The head services all the requests one by one in the direction head is moving.

Step4

The head continues to move in the same direction untill all the request in this direction are not finished.

Step5

While moving in this direction calculate the absolute distance of the track from the head.

Step6

Increment the total seek count with this distance.

Step7

Currently serviced track position now becomes the new head position.

Step8

Go to step 5 until we reach at last request in this direction.

Step9

If we reach where no requests are needed to be serviced in this direction reverse the direction and go to step 3 until all tracks in request array have not been serviced.

Calculate

SCAN Algorithm

The Algorithm

In SCAN disk scheduling algorithm, head starts from one end of the disk and moves towards the other end, servicing requests in between one by one and reach the other end. Then the direction of the head is reversed and the process continues as head continuously scan back and forth to access the disk.

Step1

Let Request array represents an array storing indexes of tracks that have been requested in ascending order of their time of arrival. ‘head’ is the position of disk head.

Step2

Let direction represents whether the head is moving towards left or right.

Step3

In the direction in which head is moving service all tracks one by one.

Step 4

Calculate the absolute distance of the track from the head.

Step 5

Increment the total seek count with this distance.

Step 6

Currently serviced track position now becomes the new head position.

Step 7

Go to step 3 until we reach at one of the ends of the disk.

Step 8

If we reach at the end of the disk reverse the direction and go to step 2 until all tracks in request array have not been serviced.

Calculate

The Team

Nabhi Shah

Design & Algo

Saumya Shah

Front-End & Algo

Pulak Jain

Front-End & Back-End

Om patel

Back-End & Algo

Jugal Soni

Front-End & Design

Thank You!

This website is part of our University project - (Pandit Deendayal Energy University) for the Operating Systems Lab course. We are taking feedbacks for any bugs you face for this site. Ping anyone of the developer on their LinkedIn profile given below if you wish to report a bug.