Simuler une file d'attente avec une file

Introduction

Dans la leçon précédente, nous avons découvert le concept de file (queue), une structure de données linéaire fonctionnant sur le principe FIFO (Premier Arrivé, Premier Sorti). Nous avons défini ses opérations fondamentales, enfiler et défiler, et nous nous sommes exercés à tracer manuellement l'état d'une file.

Aujourd'hui, nous allons utiliser cette connaissance pour un objectif très concret, qui correspond parfaitement à votre souhait de vous concentrer sur la pratique : simuler un scénario de file d'attente simple. Pensez à la file d'attente d'une caisse de supermarché, d'un guichet de poste ou d'une imprimante partagée. La file est la structure de données naturelle pour modéliser ces situations.

1. Modéliser le scénario de la file d'attente

Pour simuler une file d'attente, nous devons d'abord en définir les composants. Un scénario de base, comme la gestion des requêtes d'une imprimante, nécessite de modéliser :

• Les tâches ou clients qui attendent.
• La file d'attente elle-même pour stocker ces tâches.
• Le point de service (l'imprimante, le guichet) qui traite une tâche à la fois.
• Le temps qui s'écoule.

Un excellent document pour formaliser ce besoin est un exercice sur la gestion de requêtes d'impression.

Comme vous l'avez lu, nous avons besoin d'une structure de File et de quelques opérations de base pour la manipuler : Initialiser, EstVide, Déposer (enfiler) et Extraire (défiler). C'est avec ces outils que nous allons construire notre simulation.

2. La logique de la simulation : le "moteur de temps"

Une simulation de ce type fonctionne généralement par "pas de temps" discrets, que nous appellerons des "ticks d'horloge". À chaque tick, nous mettons à jour l'état de notre système.

Le cœur de notre algorithme sera donc une boucle qui s'exécute tant qu'il y a des clients à servir ou qu'un client est en cours de service.

Voici le pseudo-code pour une simulation avec un seul guichet et des clients ayant chacun un temps de service défini.

Algorithme Simulation_Guichet_Simple

VARIABLES
    file_attente : File de Clients  // Chaque client a un nom et une durée de service
    guichet_temps_restant : Entier  // Temps restant pour le client actuel
    temps : Entier                  // L'horloge de notre simulation

DEBUT
    // Initialisation
    temps ← 0
    guichet_temps_restant ← 0
    file_attente ← nouvelleFile()

    // Ajoutons quelques clients dans la file pour l'exemple
    enfiler(file_attente, {nom: "Alice", duree: 3})
    enfiler(file_attente, {nom: "Bob", duree: 2})
    enfiler(file_attente, {nom: "Charlie", duree: 4})

    // Boucle principale de la simulation
    TANT QUE (guichet_temps_restant > 0 OU non estVide(file_attente))
        temps ← temps + 1
        AFFICHER "--- Tick d'horloge :", temps, "---"

        // 1. Mettre à jour le guichet
        SI (guichet_temps_restant > 0) ALORS
            guichet_temps_restant ← guichet_temps_restant - 1
            SI (guichet_temps_restant = 0) ALORS
                AFFICHER "Le guichet est maintenant libre."
            FIN SI
        FIN SI

        // 2. Assigner un nouveau client si le guichet est libre et que la file n'est pas vide
        SI (guichet_temps_restant = 0 ET non estVide(file_attente)) ALORS
            client_servi ← defiler(file_attente)
            guichet_temps_restant ← client_servi.duree
            AFFICHER client_servi.nom, "passe au guichet (durée :", guichet_temps_restant, " ticks)."
        FIN SI

        AFFICHER "État de la file : ", file_attente
    FIN TANT QUE

    AFFICHER "Simulation terminée au tick :", temps
FIN

Traçage manuel

Pour bien comprendre, traçons ensemble les premiers ticks sur papier :

• Tick 0 (Initialisation) :

  • temps = 0
  • guichet_temps_restant = 0
  • file_attente = [ {Alice, 3}, {Bob, 2}, {Charlie, 4} ] (Alice est en tête)

• Tick 1 :

  • temps = 1
  • guichet_temps_restant est 0 et la file n'est pas vide.
  • On défile Alice.
  • Alice passe au guichet. guichet_temps_restant devient 3.
  • file_attente = [ {Bob, 2}, {Charlie, 4} ]

• Tick 2 :

  • temps = 2
  • Le guichet est occupé. guichet_temps_restant passe de 3 à 2.
  • file_attente = [ {Bob, 2}, {Charlie, 4} ]

• Tick 3 :

  • temps = 3
  • Le guichet est occupé. guichet_temps_restant passe de 2 à 1.
  • file_attente = [ {Bob, 2}, {Charlie, 4} ]

• Tick 4 :

  • temps = 4
  • Le guichet est occupé. guichet_temps_restant passe de 1 à 0. Le guichet se libère.
  • Puisque le guichet est maintenant libre, on défile Bob.
  • Bob passe au guichet. guichet_temps_restant devient 2.
  • file_attente = [ {Charlie, 4} ]

La simulation continue jusqu'à ce que la file soit vide et que le dernier client ait été servi.

3. Exercice pratique : Simulation avec plusieurs guichets

Maintenant, à vous de jouer ! Nous allons complexifier légèrement le scénario, en nous basant sur un exercice qui modélise une situation très réaliste.

Votre objectif :
En vous inspirant du pseudo-code de la simulation à un seul guichet, écrivez le pseudo-code de la boucle principale de la simulation pour le scénario "Une seule file pour plusieurs guichets".

Consignes et astuces :

• Vous disposez d'une variable ng (nombre de guichets).
• Utilisez un tableau etat_g de taille ng pour stocker le temps de service restant pour chaque guichet. Un guichet est libre si sa valeur dans le tableau est 0.
• À chaque tick d'horloge, votre boucle doit effectuer deux actions principales :
  1. Mettre à jour TOUS les guichets : Parcourez le tableau etat_g et décrémentez le temps de ceux qui sont occupés.
  2. Assigner des clients aux guichets libres : Parcourez à nouveau le tableau etat_g. Pour chaque guichet libre (etat_g[i] == 0), si la file d'attente n'est pas vide, défilez un client et assignez son temps de service à ce guichet.

Prenez le temps de bien structurer votre algorithme sur papier. Il s'agit d'un excellent exercice pour manipuler à la fois les files et les tableaux.

Conclusion

Félicitations pour avoir franchi cette étape ! Vous avez non seulement compris la théorie des files, mais vous avez aussi appris à l'appliquer pour modéliser et simuler un processus du monde réel.

Points clés à retenir :

• La structure de file est l'outil idéal pour gérer des éléments selon le principe FIFO, ce qui correspond parfaitement aux scénarios de files d'attente.
• Une simulation temporelle peut être construite autour d'une boucle principale qui avance par "ticks" d'horloge.
• À chaque tick, l'algorithme doit mettre à jour l'état du système (les guichets) puis traiter les nouveaux événements (assigner un client à un guichet libre).

Et après ?

Nous avons maintenant bien exploré les structures de données linéaires comme les tableaux, les piles et les files. Dans la prochaine leçon, nous allons aborder un concept algorithmique puissant et entièrement différent : la récursivité. Nous apprendrons comment une fonction peut s'appeler elle-même pour résoudre des problèmes d'une manière souvent très élégante. Ce sera un changement de perspective stimulant