Solution

The time required to read or write a disk block is determined by three factors:

• Seek time (the time to move the arm to the proper cylinder).

• Rotational delay (the time for the proper sector to rotate under the head).

• Actual data transfer time.

• For most disks, the seek time dominates the other two times, so
  reducing the mean seek time can improve system performance
  substantially.

• Various types of disk arm scheduling algorithms are available to decrease mean seek time.

  • FCSC (First come first serve)

  • SSTF (Shorted seek time first)

  • SCAN

  • C-SCAN

  • LOOK (Elevator)

  • C-LOOK

- Disk Scheduling Algorithms

• FCFS: FCFS is the simplest of all the Disk Scheduling Algorithms. In FCFS, the requests are addressed in the order they arrive in the disk queue.Let us understand this with the help of an example.

Example:

• Suppose the order of request is- (82,170,43,140,24,16,190)

  And current position of Read/Write head is : 50

• So, total seek time: =(82-50)+(170-82)+(170-43)+(140-43)+(140-24)+(24-16)+(190-16) =642

Advantages:

• Every request gets a fair chance No indefinite postponement

Disadvantages:

• Does not try to optimize seek time.

• May not provide the best possible service.

SSTF: In SSTF (Shortest Seek Time First), requests having shortest seek time are executed first. So, the seek time of every request is calculated in advance in the queue and then they are scheduled according to their calculated seek time. As a result, the request near the disk arm will get executed first. SSTF is certainly an improvement over FCFS as it decreases the average response time and increases the throughput of system.Let us understand this with the help of an example.

Example:

• Suppose the order of request is- (82,170,43,140,24,16,190)

  Andcurrent position of Read/Write head is : 50

• So, total seek time:

  =(50-43)+(43-24)+(24-16)+(82-16)+(140-82)+(170-140)+(190-170) =208

Advantages:

• Average Response Time decreases

• Throughput increases

Disadvantages:

• Overhead to calculate seek time in advance.

• Can cause Starvation for a request if it has higher seek time as compared to incoming requests.

• High variance of response time as SSTF favours only some requests.

SCAN: In SCAN algorithm 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 and again services the request arriving in its path. So, this algorithm works as an elevator and hence also known as elevator algorithm. As a result, the requests at the midrange are serviced more and those arriving behind the disk arm will have to wait.

Example:

• Suppose the requests to be addressed are-82,170,43,140,24,16,190. And the Read/Write arm is at 50, and it is also given that the disk arm should move “towards the larger value”.

  

• Therefore, the seek time is calculated as:

  =(199-50)+(199-16) =332

Advantages:

• High throughput
• Low variance of response time
• Average response time

Disadvantages:

• Long waiting time for requests for locations just visited by disk arm.

CSCAN: In SCAN algorithm, the disk arm again scans the path that has been scanned, after reversing its direction. So, it may be possible that too many requests are waiting at the other end or there may be zero or few requests pending at the scanned area.

• These situations are avoided in CSCAN algorithm in which the disk arm instead of reversing its direction goes to the other end of the disk and starts servicing the requests from there. So, the disk arm moves in a circular fashion and this algorithm is also similar to SCAN algorithm and hence it is known as C-SCAN (Circular SCAN).

Example:

• Suppose the requests to be addressed are-82,170,43,140,24,16,190. And the Read/Write arm is at 50, and it is also given that the disk arm should move “towards the larger value”.

• Seek time is calculated as:

  =(199-50)+(199-0)+(43-0) =391

Advantages:

• Provides more uniform wait time compared to SCAN

LOOK: It is similar to the SCAN disk scheduling algorithm except for the difference that the 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 only. Thus it prevents the extra delay which occurred due to unnecessary traversal to the end of the disk.

Example:

• Suppose the requests to be addressed are-82,170,43,140,24,16,190. And the Read/Write arm is at 50, and it is also given that the disk arm should move “towards the larger value”.

• So, the seek time is calculated as:

  =(190-50)+(190-16) =314

CLOOK: As LOOK is similar to SCAN algorithm, in similar way, CLOOK is similar to CSCAN disk scheduling algorithm. In 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. Thus, it also prevents the extra delay which occurred due to unnecessary traversal to the end of the disk.

Example:

• Suppose the requests to be addressed are-82,170,43,140,24,16,190. And the Read/Write arm is at 50, and it is also given that the disk arm should move “towards the larger value”.

• So, the seek time is calculated as:

  =(190-50)+(190-16)+(43-16) =341