Algorithme de l'ascenseur

L'algorithme de l'ascenseur, ou SCAN, est une méthode utilisée pour organiser les déplacements de la tête d'un disque dur afin de répondre efficacement aux demandes de lecture et d'écriture.

Cet algorithme fonctionne comme un ascenseur : il continue de se déplacer dans une direction (montée ou descente) jusqu'à ce qu'il ait traité toutes les demandes dans ce sens, en s'arrêtant uniquement là où il y a une opération à effectuer.

En pratique, le disque dur conserve une liste des demandes en attente, avec les numéros des pistes concernées. Les numéros de piste les plus bas correspondent aux zones proches du centre du disque, et les numéros plus élevés aux zones proches du bord.

Description

Quand une nouvelle demande arrive et que le disque est inactif, la tête de lecture se déplace directement vers la piste concernée, soit vers le centre, soit vers le bord. Tant qu'elle se déplace dans une direction, elle traite toutes les demandes qui se trouvent sur son chemin. Une fois arrivée au bord du disque, elle change de direction et traite les demandes dans l'autre sens.

Variantes

Une variante de cet algorithme, appelée C-SCAN (Circular SCAN), traite toutes les demandes dans une seule direction. Lorsque la tête atteint le bord du disque, elle revient directement au début sans s'occuper des demandes sur le chemin du retour. Cette méthode permet d'assurer un traitement plus équitable des demandes, car le temps d'attente est similaire pour toutes les zones du disque.

Autres variantes :

• FSCAN
• LOOK
  • C-LOOK
• N-Step-SCAN

	SCAN	LOOK	C-SCAN	C-LOOK
Déplacement	Va jusqu'à la dernière piste, même si elle n'est pas demandée, puis repart dans l'autre sens.	Va seulement jusqu'à la dernière piste demandée, puis change de direction.	Va jusqu'à la dernière piste, revient au début, et continue dans la même direction.	Va seulement jusqu'à la dernière piste demandée, revient au début, et continue dans la même direction.

Pseudo-code

L'algorithme SCAN peut être décrit en pseudo-code comme suit :

  Fonction SCAN(liste_des_demandes, position_initiale, direction_initiale)
     Trier liste_des_demandes par ordre croissant
     séparer les demandes :
        demandes_au_dessus = toutes les pistes > position_initiale
        demandes_en_dessous = toutes les pistes ≤ position_initiale
     résultats = []
     distance_totale = 0
     
     Si direction_initiale = "vers le haut"
        Pour chaque piste dans demandes_au_dessus
           ajouter piste à résultats
           distance_totale += |piste - position_initiale|
           position_initiale = piste
        Fin Pour
        inverser direction
        Pour chaque piste dans demandes_en_dessous (ordre décroissant)
           ajouter piste à résultats
           distance_totale += |piste - position_initiale|
           position_initiale = piste
        Fin Pour
     Sinon (direction_initiale = "vers le bas")
        Pour chaque piste dans demandes_en_dessous (ordre décroissant)
           ajouter piste à résultats
           distance_totale += |piste - position_initiale|
           position_initiale = piste
        Fin Pour
        inverser direction
        Pour chaque piste dans demandes_au_dessus
           ajouter piste à résultats
           distance_totale += |piste - position_initiale|
           position_initiale = piste
        Fin Pour
     Fin Si
     
     Retourner résultats, distance_totale
  Fin Fonction

Qui se traduirait par exemple en Python :

def SCAN(liste_des_demandes, position_initiale, direction_initiale):
    # Trier la liste des demandes par ordre croissant
    liste_des_demandes.sort()
    
    # Séparer les demandes
    demandes_au_dessus = [piste for piste in liste_des_demandes if piste > position_initiale]
    demandes_en_dessous = [piste for piste in liste_des_demandes if piste <= position_initiale]
    
    resultats = []
    distance_totale = 0
    
    if direction_initiale == "vers le haut":
        # Traiter les demandes au-dessus
        for piste in demandes_au_dessus:
            resultats.append(piste)
            distance_totale += abs(piste - position_initiale)
            position_initiale = piste
        
        # Changer de direction et traiter les demandes en dessous
        demandes_en_dessous.sort(reverse=True)
        for piste in demandes_en_dessous:
            resultats.append(piste)
            distance_totale += abs(piste - position_initiale)
            position_initiale = piste
    
    else:  # direction_initiale = "vers le bas"
        # Traiter les demandes en dessous
        demandes_en_dessous.sort(reverse=True)
        for piste in demandes_en_dessous:
            resultats.append(piste)
            distance_totale += abs(piste - position_initiale)
            position_initiale = piste
        
        # Changer de direction et traiter les demandes au-dessus
        for piste in demandes_au_dessus:
            resultats.append(piste)
            distance_totale += abs(piste - position_initiale)
            position_initiale = piste
    
    return resultats, distance_totale

# Exemple d'utilisation
if __name__ == "__main__":
    # Exemple de liste de demandes de disque
    demandes = [98, 183, 37, 122, 14, 124, 65, 67]
    position_initiale = 53
    direction_initiale = "vers le haut"
    
    resultats, distance = SCAN(demandes, position_initiale, direction_initiale)
    print("Ordre des pistes:", resultats)
    print("Distance totale parcourue:", distance)

Analyse

Ces deux algorithmes limitent les déplacements de la tête à moins de deux fois le nombre total de pistes, ce qui réduit les variations dans les temps d'attente. Ils sont simples et efficaces.

Cependant, l'algorithme SCAN n'est pas toujours meilleur que l'algorithme du plus court déplacement (Shortest Seek Time First). Ce dernier est plus rapide, mais il peut causer des délais importants pour certaines demandes si de nouvelles arrivent en continu. Pour éviter ce problème, des techniques anti-famine peuvent être ajoutées.

Voir aussi

• Premier entré, premier sorti (gestion)