Disk scheduling algorithms in operating systems are essential for managing and optimizing the sequence in which I/O requests are processed by the disk. The main objective is to reduce search time and rotational delay, therefore enhancing the overall performance of the disk. Below are few prevalent disk scheduling algorithms:
FCFS Disk Scheduling
The most basic scheduling method in which requests are handled in the sequence of their arrival.
Benefits: Simple to execute and comprehend.
Drawbacks: Inadequate performance in terms of total seek time; sometimes referred to as the "convoy effect" (where brief requests may be postponed due to longer ones).
Consider a disk queue with requests for I/O to blocks on Cylinders as shown in the following figure. Initially, the disk head is at cylinder 53. The total cylinder movement is 640.
Disk Scheduling Shortest Seek Time First (SSTF)
This algorithm chooses the request that has the shortest distance from the current position of the disk head.
Benefits: Decreases search time in comparison to First-Come, First-Served (FCFS) scheduling.
Drawbacks: This approach may result in the deprivation of certain requests if there are frequent requests arriving in close proximity to the present head position.
In this policy, the shortest seek time of the cylinder (from the current head position) is chosen. In the following example, the total head movement for reading all the blocks is 236.
Disk Scheduling SCAN
The SCAN algorithm, also known as the Elevator algorithm, is a method in which the disk arm goes in one direction, servicing requests as it progresses until it reaches the end of the disk, at which point it changes direction.
Benefits: Demonstrates satisfactory performance and effectively mitigates the issue of famine.
-
Drawbacks: May lead to a substantial accumulation of requests awaiting the arm's arrival at the disk's end.
In this policy, the head movement starts at one end of the disk and moves towards the other end. At the end, the direction of the head movement is reversed.
The SCAN algorithm is also known as elevator algorithm.
Disk Scheduling C-SCAN
The C-SCAN (Circular SCAN) Algorithm is similar to the SCAN algorithm, but with the difference that the arm immediately returns to the opposite end of the disk after reaching one end, without serving any requests along the way.
Benefits: Decreases waiting time for requests; prevents the arm from remaining stationary at one end. -
Drawbacks: Some requests may still have extended waiting times.
The C-SCAN scheduling algorithm essentially treats the cylinders as a circular list. Unlike SCAN, in C-SCAN policy, instead of scanning the cylinders in head movement to both directions, the cylinders are read in one direction. After reaching the end, the head is moved to the other end immediately to start scanning the cylinders again.
5. LOOK Algorithm: The LOOK algorithm is similar to the SCAN algorithm, but it does not traverse all the way to the end of the disk. Instead, it changes direction when there are no pending requests in the current direction.
Benefits: Decreases waiting duration in comparison to SCAN.
Drawbacks: This may lead to the omission of certain requests if they are in the other direction.
6. C-LOOK Algorithm: The C-LOOK Algorithm is a disk scheduling algorithm that is similar to LOOK. However, unlike LOOK, the arm immediately returns to the other end of the disk after reaching one end, without processing any requests in between.
Benefits: Decreases waiting time for requests; prevents the arm from remaining in one position for an extended period.
Drawbacks: There is a possibility of experiencing prolonged waiting periods for certain requests.
7. N-Step-SCAN Algorithm: The N-Step-SCAN Algorithm is a modified version of the SCAN algorithm that processes requests in a defined number of steps, moving in one direction, and then reversing direction.
Advantages: Offers superior seek time management in comparison to SCAN.
Drawbacks: This could lead to extended waiting periods for specific inquiries.
8. The FSCAN Algorithm: The FSCAN Algorithm is similar to the SCAN Algorithm, except it utilizes two request queues and alternates between them. One queue is being attended to while the other is being filled.
Benefits: Mitigates the effect of incoming requests on the existing queue.
Drawbacks: Demands supplementary memory allocation to accommodate two queues.
The selection of a disk scheduling technique is contingent upon the particular workload characteristics and the desired balance between fairness, response time, and overall system throughput. Every algorithm possesses unique advantages and disadvantages, and there is no universally applicable solution. The efficiency of an operating system's I/O subsystem can be greatly affected by the performance of a disk scheduling algorithm.
Posts
No comments:
Post a Comment