Algorithmes de planification d'ascenseur : FCFS, SSTF, SCAN et LOOK

Comme je travaille avec Go depuis un certain temps, j'ai pensé que ce serait un défi amusant d'y implémenter quelques solutions classiques de conception de bas niveau.

Lors de la conception d'un système d'ascenseur, un aspect crucial est de savoir comment décider quel étage desservir ensuite, en particulier lorsque l'ascenseur a plusieurs demandes. La syntaxe simple et les performances de Go le rendent idéal pour modéliser de tels systèmes, j'ai donc décidé de créer des implémentations de base des algorithmes FCFS (First Come First Serve), SSTF (Shortest Seek Time First), SCAN et LOOK.

1. Premier arrivé, premier servi (FCFS)

J'ai commencé avec l'approche la plus simple : les demandes de service dans l'ordre dans lequel elles sont reçues. C'est facile à mettre en œuvre mais peut s'avérer inefficace si les demandes sont réparties sur plusieurs étages, ce qui entraîne un temps de trajet plus long.

func FCFS(currentFloor int, requests []int) []int {
    path := []int{}
    for _, floor := range requests {
        path = append(path, floor)
    }
    return path
}

Dans FCFS, l'ascenseur se déplace simplement vers chaque étage demandé dans l'ordre donné.

2. Temps de recherche le plus court en premier (SSTF)

SSTF essaie de minimiser les déplacements en choisissant ensuite l'étage demandé le plus proche. Cela réduit le temps de trajet mais peut conduire à une « famine » pour les demandes lointaines si de nouvelles demandes plus proches continuent d'arriver.

func SSTF(currentFloor int, requests []int) []int {
    path := []int{}
    remaining := append([]int{}, requests...)

    for len(remaining) > 0 {
        closestIdx := 0
        minDistance := abs(currentFloor - remaining[0])

        for i, floor := range remaining {
            distance := abs(currentFloor - floor)
            if distance < minDistance {
                closestIdx = i
                minDistance = distance
            }
        }

        currentFloor = remaining[closestIdx]
        path = append(path, currentFloor)
        remaining = append(remaining[:closestIdx], remaining[closestIdx+1:]...)
    }
    return path
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

Cette fonction trouve à chaque fois l'étage le plus proche de l'étage actuel, mettant à jour la position de l'ascenseur après chaque déplacement.

3. SCAN (algorithme d'ascenseur)

Dans SCAN, l'ascenseur se déplace dans une direction, répondant à toutes les demandes dans cette direction jusqu'à ce qu'il atteigne la fin, puis s'inverse. Cette approche est plus juste que SSTF car elle réduit la famine.

func SCAN(currentFloor, maxFloor int, requests []int) []int {
    path := []int{}
    up := []int{}
    down := []int{}

    for _, floor := range requests {
        if floor >= currentFloor {
            up = append(up, floor)
        } else {
            down = append(down, floor)
        }
    }

    sort.Ints(up)
    sort.Sort(sort.Reverse(sort.IntSlice(down)))

    path = append(path, up...)
    path = append(path, down...)
    return path
}

Cette fonction divise les demandes en étages au-dessus et en dessous de la position actuelle. Il dessert tous les étages vers le haut, puis vers le bas.

4. REGARDEZ

LOOK est une légère variation de SCAN. Au lieu d'aller jusqu'au bout, l'ascenseur inverse la direction à la dernière demande dans chaque direction. Cela permet de gagner du temps en s'arrêtant là où finissent les demandes, et non aux limites physiques.

func LOOK(currentFloor int, requests []int) []int {
    path := []int{}
    up := []int{}
    down := []int{}

    for _, floor := range requests {
        if floor >= currentFloor {
            up = append(up, floor)
        } else {
            down = append(down, floor)
        }
    }

    sort.Ints(up)
    sort.Sort(sort.Reverse(sort.IntSlice(down)))

    path = append(path, up...)
    path = append(path, down...)
    return path
}

Semblable au SCAN, cette approche ne va que jusqu'à la dernière requête dans chaque direction.

Chaque algorithme a ses compromis :

• FCFS : Simple mais peut être inefficace.
• SSTF : optimise pour les étages les plus proches mais peut affamer les demandes lointaines.
• SCAN : Plus juste et efficace, minimisant les changements de direction.
• REGARDER : Gain de temps supplémentaire en s'arrêtant à la dernière demande.

Le bon choix dépend des exigences spécifiques en matière d'efficacité, d'équité et de temps de réponse du système.

Pour une implémentation complète à l'aide de l'algorithme LOOK, reportez-vous à mon dépôt github :

l'arbre à sel / conception-golang de bas niveau

Solutions aux problèmes de conception de systèmes de bas niveau à Golang

Conception de systèmes de bas niveau dans Go

Bienvenue dans le référentiel Conception de systèmes de bas niveau dans Go ! Ce référentiel contient divers problèmes de conception de systèmes de bas niveau et leurs solutions implémentées dans Go. L'objectif principal est de démontrer la conception et l'architecture des systèmes à travers des exemples pratiques.

Table des matières

• Aperçu
• Système de stationnement
• Système d'ascenseur

Aperçu

La conception de systèmes de bas niveau implique de comprendre les concepts fondamentaux de l'architecture système et de concevoir des systèmes évolutifs, maintenables et efficaces. Ce référentiel tentera de couvrir les solutions de divers problèmes et scénarios utilisant Go.

Système de stationnement

Le premier projet de ce référentiel est un Système de parking. Ce système simule un parking où les véhicules peuvent être garés et déchargés. Cela démontre :

• Modèle de conception Singleton pour la gestion de l'instance de parking.
• Manipulation de différents types de véhicules (par exemple, voitures, camions).
• Gestion des espaces de stationnement sur plusieurs étages.
• Traitement des paiements pour les véhicules stationnés.

Caractéristiques

• Ajouter et supprimer des véhicules du…

Voir sur GitHub

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!