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 priority algorithm, the track selected for scheduling is the distance from the track where the current head is located The nearest track to minimize each search time; 3. Scanning algorithm, select the request closest to the track where the current head is located in the current moving direction of the magnetic head as the next service object; 4. Loop scanning algorithm, in the scanning algorithm On the basis of stipulating 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.

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.

Commonly used disk scheduling algorithms

First come, first served algorithm

FCFS algorithm is based on process requests Scheduling is performed in the order in which disks are accessed. 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.

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

• Advantages: Simple and fair.

• Disadvantages: The efficiency is not high. Two adjacent requests may cause the cylinder seek from the innermost to the outermost, causing the head to move repeatedly, increasing the service time, and also affecting the machine. unfavorable.

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 each The search time is the shortest. 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.

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

• Advantages: Improved disk average service time.

• Disadvantages: Some access requests may not be serviced due to long waits.

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 object of the next service. 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.

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, serving 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 passing access requests, and so on. As shown in the figure below:

The head movement trajectory of the scanning algorithm (elevator algorithm)

• Advantages: Overcoming the shortest seek priority The shortcomings of the method take into account both the distance and the direction.

Cyclic scanning algorithm

Based on the scanning algorithm, it is stipulated that the magnetic head moves in one direction to provide services, and 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 end. 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.

Supplement: Comparison of various algorithms

	##Advantages	Disadvantages
FCFS algorithm	Fair and simple	The average seek distance is large and should only be used in situations with less disk I/O
SSTF algorithm	Performance is better than "first come, first served"	The shortest average seek time cannot be guaranteed, and "starvation" may occur
SCAN algorithm	The seeking performance is better and can avoid the "starvation" phenomenon	No Conducive to access requests far away from the end of the disk head
C-SCAN algorithm	Eliminates the inconsistency of track requests at both ends Fair	--

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!