What are the disk scheduling algorithms?

Disk scheduling algorithms include: 1. First come, first served algorithm, scheduling is performed according to the order in which the process requests access to the disk; 2. Shortest search time first algorithm, the track selected for scheduling processing is the distance from the track where the current head is located The nearest track to minimize the search time each time; 3. Scanning algorithm; 4. Loop scanning algorithm.

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. Because sometimes these processes can send requests faster than the disk can respond, it is necessary to create a waiting queue for each disk device.

There are four commonly used disk scheduling algorithms:

• First come, first served algorithm (FCFS)

• Shortest seek Track Time Priority Algorithm (SSTF)

• Scan Algorithm (SCAN)

• Cyclic Scan Algorithm (CSCAN)

First come, first served algorithm

The FCFS algorithm schedules according to the order in which the process requests access to the disk. This is the simplest scheduling algorithm. The advantage of this algorithm is its fairness. If only a small number of processes need access, and most requests access clustered file sectors, good performance is expected; but if there are a large number of processes competing for disk use, the performance of this algorithm is often close to random scheduling. . Therefore, some more complex scheduling algorithms are considered in actual disk scheduling.

1. Algorithm idea: serve access requests in the order they arrive.

2. Advantages: simple and fair.

3. Disadvantages: The efficiency is not high. Two adjacent requests may cause the cylinder seek from the innermost to the outermost, causing the magnetic head to move repeatedly, which increases the service time and is not good for the machine.

Shortest search time first algorithm

The SSTF algorithm selects the track for scheduling processing that is closest to the track where the current head is located, so that the search time is the shortest each time. Of course, always choosing the minimum search time does not guarantee the minimum average search time, but it can provide better performance than the FCFS algorithm. This algorithm will produce a "starvation" phenomenon.

1. Algorithm idea: Prioritize access requests closest to the current head for service, mainly considering seek priority.

2. Advantages: Improved average disk service time.

3. Disadvantage: causing some access requests to wait for a long time and not be served.

Scan algorithm (also known as elevator algorithm)

The SCAN algorithm selects the request closest to the track where the current head is located in the current moving direction of the head as the next service object. . Since the head movement pattern is similar to that of an elevator, it is also called an elevator scheduling algorithm. The SCAN algorithm is not fair to recently scanned areas, therefore, it is not as good as the FCFS algorithm and SSTF algorithm in terms of access locality.

1. Algorithm idea: When the device has no access request, the magnetic head does not move; when there is an access request, the magnetic head moves in one direction, and services the access requests encountered during the movement [2] , and then determine whether there are still access requests in this direction, and if so, continue scanning; otherwise, change the movement direction and serve the passing access requests, and so on.

2. Advantages: Overcoming the shortcomings of shortest seek first, taking into account both distance and direction.

Cyclic scanning algorithm

Based on the scanning algorithm, it is stipulated that the magnetic head moves in one direction to provide services. When returning, it moves directly to the starting end quickly without serving any requests. Since the SCAN algorithm prefers to process access requests close to the innermost or outermost tracks, the improved C-SCAN algorithm is used to avoid this problem.

When using the SCAN algorithm and the C-SCAN algorithm, the magnetic head always strictly follows the movement from one end of the disk to the other. Obviously, it can be improved in actual use, that is, the magnetic head movement only needs to reach the farthest end. A single request can be returned without reaching the disk endpoint. This form of SCAN algorithm and C-SCAN algorithm is called LOOK and C-LOOK scheduling. This is because they look to see if there is a request before moving in a given direction. Note that unless otherwise specified, the SCAN algorithm and C-SCAN algorithm can also be scheduled as LOOK and C-LOOK by default.

For more related knowledge, please visit the FAQ column!

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