What are the currently commonly used disk scheduling algorithms?

Currently commonly used disk scheduling algorithms are: 1. First come first served algorithm (FCFS); 2. Shortest seek time first algorithm (SSTF); 3. Scan algorithm (SCAN); 4. Loop scan algorithm (CSCAN).

The operating environment of this tutorial: Windows 7 system, Dell G3 computer.

Disk Scheduling In a multi-programmed computer system, each process may continuously make different requests for read/write operations on the disk. Since sometimes these processes send requests faster than the disk can respond, it is necessary for us to establish a waiting queue for each disk device. There are four commonly used disk scheduling algorithms:

First come First serve algorithm (FCFS),

Shortest seek time first algorithm (SSTF),

Scan algorithm (SCAN),

Cycle scan algorithm (CSCAN)

Example: Assume that a disk has a total of 200 cylinders, numbered 0-199. After serving the requester accessing cylinder No. 143, it is currently serving the request to access cylinder No. 125, and there are several requests at the same time. The users are waiting for service. The cylinder numbers they want to access each time are 86, 147, 91, 177, 94, 150, 102, 175, 130

1. First come first served algorithm (FCFS) First Come First Service

This is a relatively simple disk scheduling algorithm. It is scheduled based on the order in which processes request access to the disk. The advantages of this algorithm are that it is fair and simple, and the requests of each process can be processed in turn, and there will be no situation where the request of a certain process cannot be satisfied for a long time. Since this algorithm does not optimize seek, when there are many disk access requests, this algorithm will reduce the throughput of the device service, resulting in the average seek time being longer, but the response time of each process getting the service is less than The changes are smaller.

First come, first served (125) 86.147.91.177.94.150.102.175.130

2. Shortest Seek Time First Algorithm (SSTF) Shortest Seek Time First

The The algorithm selects a process that requires the accessed track to be closest to the track where the current head is located, so that each seek time is the shortest. This algorithm can obtain better throughput, but it cannot guarantee the shortest average seek time. The disadvantage is that the response opportunities to users' service requests are not equal, resulting in large changes in response time. When there are many service requests, requests to internal and external edge tracks will be delayed indefinitely, and the response time of some requests will be unpredictable.

Shortest seek time first (125) 130.147.150.175.177.102.94.91.86

3. Scanning algorithm (SCAN) elevator scheduling

The scanning algorithm not only takes into account the desired The distance between the accessed track and the current track is more prioritized by the current moving direction of the magnetic head. For example, when the magnetic head is moving from the inside out, the next access object selected by the scanning algorithm should be the track it wants to access that is both outside the current track and the closest. In this way, access is performed from the inside out, and the magnetic arm is reversed and moved from the outside to the inside until no more external tracks need to be accessed. At this time, a process is also selected for scheduling every time, that is, the track it wants to access is within the current track, thus avoiding the occurrence of starvation. Because the law of head movement in this algorithm is quite similar to the operation of an elevator, it is also called an elevator scheduling algorithm. This algorithm basically overcomes the shortcomings of the shortest seek time first algorithm that the service is concentrated on the middle track and the response time varies greatly. It has the advantages of the shortest seek time first algorithm, that is, larger throughput and smaller average response time, but Due to the swing scanning method, the tracks on both sides are still accessed less often than the middle track.

Elevator dispatching (125) 102.94.91.86.130.147.150.175.177

4. Cyclic scanning algorithm (CSCAN)

The cyclic scanning algorithm is an improvement on the scanning algorithm. If access requests to a track are evenly distributed, relatively few access requests will fall behind the head when it reaches one end of the disk and moves in the opposite direction. This is because these tracks have just been processed, and the request density at the other end of the disk is quite high, and these access requests wait for a long time. In order to solve this situation, the circular scan algorithm stipulates that the head moves in one direction. For example, if it only moves from the inside out, when the magnetic head moves to the outermost accessed track, the magnetic head immediately returns to the innermost track to be accessed, that is, the smallest track number is followed by the largest track number to form a cycle for scanning.

Cycle scan (125) 130.147.150.175.177.86.91.94.102

For more computer-related knowledge, please visit the FAQ column!

The above is the detailed content of What are the currently commonly used disk scheduling algorithms?. For more information, please follow other related articles on the PHP Chinese website!