Algorithme d'ascenseur

L' algorithme d'ascenseur , ou SCAN , est un algorithme de planification de disque permettant de déterminer le mouvement du bras et de la tête du disque lors du traitement des demandes de lecture et d'écriture.

Cet algorithme doit son nom au comportement d'un ascenseur de bâtiment , où l'ascenseur continue de se déplacer dans sa direction actuelle (vers le haut ou vers le bas) jusqu'à ce qu'il soit vide, s'arrêtant uniquement pour laisser descendre des individus ou pour prendre de nouveaux individus se dirigeant dans la même direction.

D'un point de vue de mise en œuvre, le lecteur conserve une mémoire tampon de demandes de lecture/écriture en attente, ainsi que le numéro de cylindre associé à la demande, dans lequel les numéros de cylindre inférieurs indiquent généralement que le cylindre est plus proche de la broche, et les numéros plus élevés indiquent que le cylindre est plus éloigné.

Lorsqu'une nouvelle requête arrive alors que le lecteur est inactif, le mouvement initial du bras/de la tête se fera dans la direction du cylindre où les données sont stockées, soit vers l'intérieur , soit vers l'extérieur . Lorsque des requêtes supplémentaires arrivent, les requêtes sont traitées uniquement dans la direction actuelle du mouvement du bras jusqu'à ce que le bras atteigne le bord du disque. Lorsque cela se produit, la direction du bras s'inverse et les requêtes qui restaient dans la direction opposée sont traitées, et ainsi de suite.

Une variante de cette méthode garantit que toutes les requêtes sont traitées dans une seule direction, c'est-à-dire qu'une fois que la tête est arrivée au bord extérieur du disque, elle revient au début et traite les nouvelles requêtes dans cette seule direction (ou vice versa). C'est ce qu'on appelle l'« algorithme de l'ascenseur circulaire » ou C-SCAN. Bien que le temps de recherche de retour soit gaspillé, cela se traduit par des performances plus égales pour toutes les positions de la tête, car la distance attendue par rapport à la tête est toujours la moitié de la distance maximale, contrairement à l'algorithme de l'ascenseur standard où les cylindres du milieu seront traités jusqu'à deux fois plus souvent que les cylindres les plus à l'intérieur ou les plus à l'extérieur.

D'autres variantes incluent :

• Analyseur de spectre de masse
• REGARDER
  • C-REGARDER
• Scan en N étapes

Voici un exemple de calcul des temps de recherche de disque moyens pour les algorithmes SCAN et C-SCAN.

• Exemple de liste de demandes de disque en attente (classées par numéro de piste) : 100, 50, 10, 20, 75.
• Le numéro de piste de départ pour les exemples sera 35.
• La liste devra être triée par ordre croissant : 10, 20, 50, 75, 100.

Les algorithmes SCAN et C-SCAN se comportent de la même manière jusqu'à ce qu'ils atteignent la dernière piste en file d'attente. Pour les besoins de cet exemple, supposons que l'algorithme SCAN passe actuellement d'un numéro de piste inférieur à un numéro de piste supérieur (comme le fait C-SCAN). Pour les deux méthodes, on prend la différence de grandeur (c'est-à-dire la valeur absolue) entre la demande de piste suivante et la piste actuelle.

• Recherche 1 : 50 − 35 = 15
• Recherche 2 : 75 − 50 = 25
• Recherche 3 : 100 − 75 = 25

À ce stade, les deux ont atteint la demande de piste la plus élevée (fin). SCAN inversera simplement la direction et traitera la demande de disque la plus proche (dans cet exemple, 20) et C-SCAN reviendra toujours à la piste 0 et commencera à passer aux demandes de piste supérieures.

• Recherche 4 (SCAN) : 20 − 100 = 80
• Recherche 5 (SCAN) : 10 − 20 = 10
• Total (SCAN) : 155
• Moyenne (SCAN) : 155 ÷ 5 = 31
• Recherche 4 (C-SCAN) : 0 − 100 = 0 mouvement de tête car les cylindres sont traités comme une liste circulaire (C-SCAN revient toujours à la première piste)
• Recherche 5 (C-SCAN) : 10 − 0 = 10
• Recherche 6 (C-SCAN) : 20 − 10 = 10
• Total (C-SCAN) : 85
• Moyenne (C-SCAN) : 85 ÷ 5 = 17

Même si six recherches ont été effectuées à l'aide de l'algorithme C-SCAN, seules cinq E/S ont été réellement effectuées.

L'algorithme de balayage (souvent appelé algorithme de somme de préfixes) est couramment utilisé en informatique pour les problèmes impliquant le calcul de la somme cumulative ou du résultat cumulé d'une série d'éléments dans un tableau ou une liste. Il fonctionne en parcourant la liste et en conservant un résultat accumulé jusqu'à l'élément actuel, et peut être utilisé dans divers scénarios tels que le calcul parallèle, la réduction des opérations ou le traitement efficace de données volumineuses.

Voici un exemple concret où l’algorithme d’analyse est appliqué :

Exemple : Traitement des données en temps réel dans l'analyse du marché boursier Imaginez une application de trading financier qui suit les variations de prix d'une action au fil du temps et calcule la valeur cumulée ou le gain/la perte de l'action à tout moment.

Scénario : vous disposez d'une liste de variations quotidiennes du cours de l'action (valeurs positives ou négatives) pour une action particulière sur une période de plusieurs jours. L'algorithme d'analyse peut être utilisé pour calculer le gain ou la perte cumulé à chaque jour, en indiquant la variation totale du cours de l'action depuis le début jusqu'à ce jour.

Données d'entrée : une liste des variations quotidiennes du cours des actions :

csharp Copier le code [10, -5, 3, 7, -2] Où :

10 représente un gain de 10 $ le jour 1, -5 représente une perte de 5 $ le jour 2, 3 représente un gain de 3 $ le jour 3, 7 représente un gain de 7 $ le jour 4, -2 représente une perte de 2 $ le jour 5. Exécution étape par étape (algorithme d'analyse) :

Commencez avec une somme cumulative initiale de 0. Pour chaque jour suivant, ajoutez la variation du jour à la somme cumulative : Jour 1 : 0 + 10 = 10 (Gain total jusqu'à présent : 10 $) Jour 2 : 10 + (-5) = 5 (Gain total jusqu'à présent : 5 $) Jour 3 : 5 + 3 = 8 (Gain total jusqu'à présent : 8 $) Jour 4 : 8 + 7 = 15 (Gain total jusqu'à présent : 15 $) Jour 5 : 15 + (-2) = 13 (Gain total jusqu'à présent : 13 $) Résultat : Les gains cumulés après chaque jour :

csharp Copier le code [10, 5, 8, 15, 13] Cette liste cumulative montre les performances de l'action en termes de gain/perte totale pour chaque jour de la période. En utilisant l'algorithme d'analyse, vous calculez efficacement ces résultats cumulés en un seul passage sur les données.

Parallélisme et optimisation : dans une application réelle où l'ensemble de données est volumineux (par exemple, le suivi des cours boursiers sur des milliers de jours pour plusieurs actions), cet algorithme d'analyse peut être parallélisé pour s'exécuter plus rapidement. Par exemple, en utilisant des techniques telles que la somme de préfixes parallèles (où le tableau d'entrée est divisé en blocs, traité en parallèle, puis fusionné), les données à grande échelle peuvent être traitées beaucoup plus efficacement.

Cas d'utilisation au-delà de l'analyse boursière : Traitement d'images : opérations cumulatives (comme les intensités de pixels) pour des tâches telles que la convolution ou les filtres de flou. Systèmes distribués : agrégation de valeurs sur plusieurs nœuds pour calculer des statistiques cumulatives. Systèmes de bases de données : calcul efficace des totaux cumulés dans les applications financières ou d'analyse. L'algorithme d'analyse est essentiel dans les scénarios où vous devez traiter ou agréger des données d'une manière qui s'appuie sur des calculs antérieurs, et son implémentation parallèle permet de passer à l'échelle supérieure pour des ensembles de données plus volumineux.

Pour les deux versions de l'algorithme d'ascenseur, le mouvement du bras est inférieur à deux fois le nombre total de cylindres et produit une plus petite variation du temps de réponse. L'algorithme est également relativement simple.

L'algorithme de l'ascenseur n'est pas toujours meilleur que l' algorithme de recherche la plus courte en premier , qui est légèrement plus proche de l'optimum, mais peut entraîner une grande variation du temps de réponse et même une famine lorsque de nouvelles demandes sont continuellement traitées avant les demandes existantes. Des techniques anti-famine peuvent être appliquées à l'algorithme de recherche la plus courte en premier pour garantir un temps de réponse maximal.