Shulou(Shulou.com)06/02 Report--

Today, I will talk to you about what disk scheduling algorithms there are, which may not be well understood by many people. In order to make you understand better, the editor summed up the following content for you. I hope you can get something according to this article.

Disk scheduling algorithms are: 1, first-come, first-served algorithm, scheduling according to the sequence of process requests to access the disk; 2, the shortest search time priority algorithm, select the track of scheduling processing is the track closest to the track where the current head is located, in order to minimize the search time each time; 3, scanning algorithm; 4, circular scanning algorithm.

Disk scheduling in a multiprogramming computer system, each process may constantly make different requests for read / write operations on the disk. Because sometimes these processes send requests faster than disks respond, it is necessary to establish a waiting queue for each disk device.

There are four commonly used disk scheduling algorithms:

First come first served algorithm (FCFS)

Shortest seek time first algorithm (SSTF)

Scanning algorithm (SCAN)

Cyclic scan algorithm (CSCAN)

First come first served algorithm

The FCFS algorithm schedules the disk according to the order in which the process requests to access the disk, which is the simplest scheduling algorithm. The advantage of this algorithm is fairness. It is expected to achieve better performance if only a small number of processes need to access, and most of the requests are to access clustered file sectors, but if a large number of processes compete to use disks, then the performance of this algorithm is often close to random scheduling. Therefore, some more complex scheduling algorithms are considered in the actual disk scheduling.

1. Algorithm idea: service according to the order in which the access request arrives.

2. Advantages: simple and fair.

3, disadvantage: the efficiency is not high, two adjacent requests may cause the innermost to outermost cylindrical seek, make the magnetic head move repeatedly, increase the service time, and it is also disadvantageous to the machine.

Shortest search time priority algorithm

The SSTF algorithm chooses that the track for scheduling processing is the track closest to the track where the current head is located, so as to minimize the search time for 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 the phenomenon of "hunger".

1. The idea of the algorithm: priority is given to the access request closest to the current head for service, mainly considering seek priority.

2. Advantages: the average disk service time has been improved.

3. Disadvantages: some access requests can not be served for a long time.

Scanning algorithm (also known as elevator algorithm)

The SCAN algorithm selects the request closest to the track of the current head as the next service object in the current moving direction of the head. Because the movement law of magnetic head is similar to that of elevator, it is also called elevator scheduling algorithm. The SCAN algorithm is unfair to the recently scanned areas, so it is not as good as the FCFS algorithm and SSTF algorithm in terms of access locality.

1. The idea of the algorithm: 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, serves the access request encountered in the process of moving [2], and then determines whether there is an access request in that direction. If so, continue to scan; otherwise, change the direction of movement and serve the access requests that have passed, and so on.

2. Advantages: it overcomes the disadvantage of the shortest seek priority, taking into account not only the distance but also the direction.

Cyclic scanning algorithm

On the basis of the scanning algorithm, it is stipulated that the magnetic head moves unidirectionally to provide services, and when returning, it moves directly and quickly to the beginning without serving any request. Because the SCAN algorithm tends to handle access requests that are close to the innermost or outermost tracks, an improved C-SCAN algorithm is used to avoid this problem.

When using SCAN algorithm and C-SCAN algorithm, the magnetic head always strictly follows from one end of the disk surface to the other end. Obviously, it can be improved in practical use, that is, the magnetic head movement only needs to reach the farthest end of the request to return, and does not need to reach the disk endpoint. This form of SCAN algorithm and C-SCAN algorithm are called LOOK and C-LOOK scheduling. This is because they check for requests before moving in a given direction. Note that unless otherwise specified, you can also default SCAN algorithm and C-SCAN algorithm to LOOK and C-LOOK scheduling.

After reading the above, do you have any further understanding of what disk scheduling algorithms are available? If you want to know more knowledge or related content, please follow the industry information channel, thank you for your support.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.