Disk Scheduling Gate Exam-

As we know, a process needs two types of time, CPU time and IO time. For I/O, it requests the Operating system to access the disk.

However, the operating system must be fair enough to satisfy each request and at the same time, an operating system must maintain the efficiency and speed of process execution.

The technique that the operating system uses to determine the request which is to be satisfied next is called disk scheduling.

ARMY STORE IN INDIA ……………………   

AMAZON BEST DEAL ……………………….

Let’s discuss some important terms related to disk scheduling.

  1. 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.

  2. Rotational Latency:

    Rotational Latency is the time taken by the desired sector of disk to rotate into a position so that it can access the read/write heads. So the disk scheduling algorithm that gives minimum rotational latency is better.

  3. Transfer Time:

    Transfer time is the time to transfer the data. It depends on the rotating speed of the disk and number of bytes to be transferred.

  4. Disk Access Time:

    Disk Access Time is:

  5. Disk Response Time: 

    Response Time is the average of time spent by a request waiting to perform its I/O operation. Average Response time is the response time of the all requests. Variance Response Time is measure of how individual request are serviced with respect to average response time. So the disk scheduling algorithm that gives minimum variance response time is better.

Disk Scheduling Algorithms-

  1. 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
    fcfs3
    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
  1. 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)
    And current position of Read/Write head is : 50
    sstf1

    So, total seek time:

    =(50-43)+(43-24)+(24-16)+(82-16)+(140-82)+(170-40)+(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
  1. 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”.
    scan4

    Therefore, the seek time is calculated as:

  1. =(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
  1. 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”.
cscan1

Seek time is calculated as:

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

Advantages:
  • Provides more uniform wait time compared to SCAN
  1. 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”.
    look1

    So, the seek time is calculated as:

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

  1. 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”
    clook1

    So, the seek time is calculated as:

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

  2. RSS

    – It stands for random scheduling and just like its name it is nature. It is used in situations where scheduling involves random attributes such as random processing time, random due dates, random weights, and stochastic machine breakdowns this algorithm sits perfect. Which is why it is usually used for and analysis and simulation.

  1. LIFO

    – In LIFO (Last In, First Out) algorithm, newest jobs are serviced before the existing ones i.e. in order of requests that get serviced the job that is newest or last entered is serviced first and then the rest in the same order.

    Advantages
    • Maximizes locality and resource utilization
    Disadvantages
    • Can seem a little unfair to other requests and if new requests keep coming in, it cause starvation to the old and existing ones.
    Example
    Suppose the order of request is- (82,170,43,142,24,16,190)
    And current position of Read/Write head is : 50

    lcfs

  2. N-STEP SCAN 

    – It is also known as N-STEP LOOK algorithm. In this a buffer is created for N requests. All requests belonging to a buffer will be serviced in one go. Also once the buffer is full no new requests are kept in this buffer and are sent to another one. Now, when these N requests are serviced, the time comes for another top N requests and this way all get requests get a guaranteed service

    Advantages
    • It eliminates starvation of requests completely
  3. FSCAN

    – This algorithm uses two sub-queues. During the scan, all requests in the first queue are serviced and the new incoming requests are added to the second queue. All new requests are kept on halt until the existing requests in the first queue are serviced.

    Advantages
    • FSCAN along with N-Step-SCAN prevents “arm stickiness” (phenomena in I/O scheduling where the scheduling algorithm continues to service requests at or near the current sector and thus prevents any seeking)

Disk Scheduling Numericals

SOME USE FULL LINK

What is Cache Memory Organization   

What is Program Design
Explain File Allocation Methods

USFULL PRODUCT

Tygot Adjustable Aluminium Alloy Tripod Stand Holder for Mobile Phones & Camera, 360 mm -1050 mm, 1/4 inch Screw + Mobile Holde

 DONATE SOME MONEY TO THIS BLOG AND CREATERS

 

0
Open chat