Quels sont les algorithmes de planification de disque ?

Les algorithmes de planification de disque comprennent : 1. L'algorithme premier arrivé, premier servi, qui planifie en fonction de l'ordre dans lequel les processus demandent l'accès au disque ; 2. L'algorithme de priorité du temps de recherche le plus court, qui sélectionne la piste de planification du traitement la plus proche de la piste où se trouve la tête actuelle afin de minimiser le temps de recherche à chaque fois ; 3. Algorithme de numérisation, sélectionnez la demande la plus proche de la piste où se trouve la tête actuelle dans la direction de déplacement actuelle de la tête magnétique comme prochain service. objet ; 4. Algorithme d'analyse cyclique, spécifié sur la base de l'algorithme d'analyse. La tête de disque se déplace dans une direction pour fournir des services, et lors du retour, elle se déplace directement vers l'extrémité de départ sans répondre à aucune demande.

L'environnement d'exploitation de ce tutoriel : système Windows 7, ordinateur Dell G3.

Planification du disque Dans un système informatique multiprogrammé, chaque processus peut continuellement effectuer différentes demandes d'opérations de lecture/écriture sur le disque. Étant donné que ces processus peuvent parfois envoyer des requêtes plus rapidement que le disque ne peut y répondre, il est nécessaire de créer une file d'attente pour chaque périphérique de disque.

Algorithmes de planification de disque couramment utilisés

Algorithme du premier arrivé, premier servi

L'algorithme FCFS planifie en fonction de l'ordre dans lequel les processus demandent à accéder au disque. Il s'agit de l'algorithme de planification le plus simple. L’avantage de cet algorithme est son équité. Si seul un petit nombre de processus ont besoin d'un accès et que la plupart des requêtes accèdent à des secteurs de fichiers groupés, de bonnes performances sont attendues ; mais s'il existe un grand nombre de processus en concurrence pour l'utilisation du disque, les performances de cet algorithme sont souvent proches d'une planification aléatoire. Par conséquent, certains algorithmes de planification plus complexes sont pris en compte dans la planification réelle des disques.

• Idée d'algorithme : traiter les demandes d'accès dans l'ordre dans lequel elles arrivent.

• Avantages : Simple et équitable.

• Inconvénients : L'inefficacité n'est pas élevée. Deux demandes adjacentes peuvent provoquer une recherche du cylindre du plus intérieur vers l'extérieur, provoquant des mouvements répétés de la tête magnétique, augmentant le temps de service et étant préjudiciable à la machine.

Algorithme du temps de recherche le plus court en premier

L'algorithme SSTF sélectionne la piste pour le traitement de planification qui est la plus proche de la piste où se trouve la tête actuelle, de sorte que le temps de recherche soit le plus court à chaque fois. Bien entendu, toujours choisir le temps de recherche minimum ne garantit pas le temps de recherche moyen minimum, mais il peut offrir de meilleures performances que l'algorithme FCFS. Cet algorithme va produire un phénomène de « famine ».

• Idée d'algorithme : prioriser les demandes d'accès les plus proches du responsable de service actuel, en tenant principalement compte de la priorité de recherche.

• Avantages : Amélioration du temps de service moyen du disque.

• Inconvénient : faire attendre longtemps certaines demandes d'accès et ne pas être servies.

Algorithme de numérisation (également connu sous le nom d'algorithme d'ascenseur)

L'algorithme de numérisation sélectionne la demande la plus proche de la piste où se trouve la tête actuelle dans la direction de déplacement actuelle de la tête magnétique comme prochain objet de service. Étant donné que le modèle de mouvement de la tête est similaire à celui d’un ascenseur, on l’appelle également algorithme de planification d’ascenseur. L'algorithme SCAN n'est pas équitable pour les zones récemment analysées, par conséquent, il n'est pas aussi bon que l'algorithme FCFS et l'algorithme SSTF en termes de localité d'accès.

Idée d'algorithme : Lorsque l'appareil n'a pas de demande d'accès, la tête magnétique ne bouge pas ; lorsqu'il y a une demande d'accès, la tête magnétique se déplace dans un sens, et pendant le mouvement [2] elle répond aux demandes d'accès rencontrées, et détermine ensuite la direction de la demande d'accès s'il y a encore des demandes d'accès, si c'est le cas, continuez l'analyse sinon, changez la direction du mouvement et répondez aux demandes d'accès qui passent, et ainsi de suite ; Comme le montre la figure ci-dessous :

La trajectoire du mouvement de la tête de l'algorithme de balayage (algorithme d'ascenseur)

• Avantages : Surmonter les inconvénients de la recherche la plus courte en premier, en tenant compte à la fois de la distance et de la direction.

Algorithme de balayage cyclique

Basé sur l'algorithme de balayage, la tête magnétique est stipulée pour se déplacer dans une direction pour fournir des services. Lors du retour, elle se déplacera directement vers l'extrémité de départ rapidement sans répondre à aucune demande. Étant donné que l'algorithme SCAN préfère traiter les demandes d'accès proches des pistes les plus internes ou les plus externes, l'algorithme C-SCAN amélioré est utilisé pour éviter ce problème.

Lors de l'utilisation de l'algorithme SCAN et de l'algorithme C-SCAN, la tête magnétique suit toujours strictement d'une extrémité du disque à l'autre extrémité. Évidemment, elle peut être améliorée en utilisation réelle, c'est-à-dire que le mouvement de la tête magnétique n'a besoin que de cela. atteindre une requête à l’extrémité la plus éloignée Renvoie sans atteindre le point de terminaison du disque. Cette forme d'algorithme SCAN et d'algorithme C-SCAN est appelée planification LOOK et C-LOOK. En effet, ils vérifient s’il y a une demande avant de se déplacer dans une direction donnée. Notez que sauf indication contraire, l'algorithme SCAN et l'algorithme C-SCAN peuvent également être planifiés comme LOOK et C-LOOK par défaut.

Supplément : Comparaison de divers algorithmes

	Avantages	Inconvénients
Algorithme FCFS	Équitable, simple	La distance de recherche moyenne est grande et ne doit être utilisée que dans des situations avec moins d'E/S disque
Algorithme SSTF	Les performances sont meilleures que "premier arrivé, premier servi"	Ne peut pas garantir une recherche moyenne Le temps le plus court, un phénomène de « famine » peut se produire
L'algorithme SCAN	a de meilleures performances de recherche et peut éviter le phénomène de « famine »	Il n'est pas propice aux demandes d'accès à distance de l'extrémité de la tête magnétique
L'algorithme C-SCAN	élimine l'injustice des demandes de suivi aux deux extrémités	--

Pour plus de connaissances connexes, veuillez visiter le Colonne FAQ !

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!