Voici quelques exemples afin de bien comprendre la notion d'ordonnancement des processus.
Exemple 1 :
On considère 4 processus A, B, C et D avec les données d’ordonnancement suivantes : (les temps sont donnés en nombre de cycles CPU).
Le temps d'exécution moyen par processus est de : (3 + 6 + 6 + 2) / 4 ≈ 4,2 cycles CPU. (Il s'agit de la somme de tous les temps d'exécution, divisée par le nombre de processus).
On peut représenter la situation par le schéma suivant :
On va ordonnancer ces 4 processus par la technique FIFO, puis par la technique du tourniquet (Round Robin) avec un quantum allant de 1 (la valeur minimale) à 6 (la valeur maximale, correspondant au temps d'exécution le plus long parmi tous les processus). On obtient les résultats suivants :
(On peut remarquer que Round Robin avec un quantum de 6 donne le même résultat que la méthode FIFO).
Pour chacune de ces techniques d'ordonnancement, on va calculer, pour chaque processus, le temps de séjour (égal au temps de sortie - le temps d'arrivée) et le temps d'attente (égal au temps de séjour - le temps d'exécution).
Par exemple, dans le cas de la méthode FIFO, on a :
temps de séjour (A) = 3 - 0 = 3
temps d'attente (A) = 3 - 3 = 0
temps de séjour (B) = 9 - 1 = 8
temps d'attente (B) = 8 - 6 = 2
temps de séjour (C) = 15 - 2 = 13
temps d'attente (C) = 13 - 6 = 7
temps de séjour (D) = 17 - 4 = 13
temps d'attente (D) = 13 - 2 = 11
Soit un temps de séjour moyen de 5,0 cycles CPU et un temps d'attente moyen de 9,2 cycles CPU.
On refait le même type de calculs pour les autres techniques d'ordonnancement, c'est-à-dire Round Robin avec un quantum de 1 à 6. On obtient le tableau suivant :
D'après ce tableau on peut voir que les méthodes d'ordonnancement les plus efficaces dans ce cas de figure sont : FIFO et Round Robin (quantum = 6), ce qui revient au même.
Exemple 2 :
On considère 4 processus A, B, C et D avec les données d’ordonnancement suivantes : (les temps sont donnés en nombre de cycles CPU).
On va ordonnancer ces 4 processus par la technique FIFO, puis par la technique du tourniquet (Round Robin) avec un quantum allant de 1 (la valeur minimale) à 8 (la valeur maximale, correspondant au temps d'exécution le plus long parmi tous les processus). On obtient les résultats suivants :
Pour chacune de ces techniques d'ordonnancement, on va calculer, pour chaque processus, le temps de séjour (égal au temps de sortie - le temps d'arrivée) et le temps d'attente (égal au temps de séjour - le temps d'exécution), et on obtient les résultats suivants :
D'après ce tableau on peut voir que les méthodes d'ordonnancement les plus efficaces dans ce cas de figure sont : Round Robin (quantum = 2) et Round Robin (quantum = 3).
Vous voulez tester vos propres exemples ?
Voici un code Python qui vous permettra de vérifier vos résultats sur les exemple du cours. Le code est documenté, et modulaire, de façon à pouvoir être facilement réutilisé.
# Importation des librairies utilisées
import math, sys
import matplotlib.pyplot as plt
import matplotlib.patches as mpatches
# Liste des couleurs prédéfinies
COULEURS = ["#e6194b", "#3cb44b", "#ffe119", "#4363d8", "#f58231", "#911eb4", "#46f0f0", "#f032e6", "#bcf60c", "#fabebe"]
# Définitions des fonctions
def creation_processus():
"""
Fonction permettant de créer les données relatives à une suite de processus.
Arguments :
aucun
Renvoie :
un tuple contenant deux listes :
* la première contient les temps d'arrivage des différents processus
* la seconde contient les temps d'exécution des différents processus.
"""
temps_arrivage = []
temps_execution = []
print(" ")
nombre_processus = int(input("Entrez le nombre de processus à ordonnancer ? "))
for i in range(nombre_processus):
print(" ")
print("Processus n°", i + 1)
arrivage = int(input("Temps d'arrivage ? "))
print("Temps d'arrivage = ", arrivage)
temps_arrivage.append(arrivage)
execution = int(input("Temps d'exécution ? "))
print("Temps d'exécution = ", execution)
temps_execution.append(execution)
return temps_arrivage, temps_execution
def fifo(temps_arrivage, temps_execution):
"""
Ordonnancement FIFO (First In, First Out)
Arguments :
- temps_arrivage (list) : liste des temps d'arrivage
- temps_execution (list) : liste des temps d'exécution
Renvoie :
une liste d'entiers contenant les processus ordonnancés
"""
processus_ordonnances = [] # Liste des processus ordonnancés
arrivage = temps_arrivage.copy() # Copie de travail des temps d'arrivage
execution = temps_execution.copy() # Copie de travail des temps d'exécution
numero_processus = [] # Liste des numéros de processus (en commençant par 1)
for i in range(len(temps_arrivage)):
numero_processus.append(i + 1)
# On recherche le numéro du processus ayant le plus petit temps d'arrivage,
# en commençant par la fin pour qu'en cas d'égalité, ce soit le premier processus
# de la liste qui soit sélectionné
for i in range(len(temps_arrivage), 0, -1):
index_temps_mini = 0
for j in range(1, i):
if arrivage[j] < arrivage[index_temps_mini]:
index_temps_mini = j
# On ajoute le processus sélectionné à la liste des processus ordonnancés
# autant de fois que le temps d'exécution correspondant, et on met à jour les
# listes de travail en enlevant les valeurs correspondant au processus traité
processus_ordonnances = processus_ordonnances + [numero_processus.pop(index_temps_mini)] * execution.pop(index_temps_mini)
arrivage.pop(index_temps_mini)
return processus_ordonnances
def tourniquet(temps_arrivage, temps_execution, quantum):
"""
Ordonnancement selon l'algorithme du tourniquet (Round Robin)
Arguments :
- temps_arrivage (list) : liste des temps d'arrivage
- temps_execution (list) : liste des temps d'exécution
- quantum (int) : valeur du quantum pour le tourniquet
Renvoie :
une liste d'entiers contenant les processus ordonnancés
"""
processus_ordonnances = [] # Liste des processus ordonnancés
nombre_processus = len(temps_arrivage) # Nombre de processus
nombre_processus_termines = 0 # Nombre de processus teerminés
temps = 0 # Numéro du cycle CPU en cours
numero_processus_elu = 0 # Numéro du processus élu (0 au départ)
index = [0] * nombre_processus # Liste du numéro de l'instruction en cours pour chaque processus (0 au départ)
processus_termines = [False] * nombre_processus # Etat des processus (aucun n'est terminé au départ)
fini = False # Le traitement de tous les processus n'est pas terminé
while not(fini):
# Si le processus élu est arrivé, et s'il n'est pas terminé...
if temps >= temps_arrivage[numero_processus_elu] and not(processus_termines[numero_processus_elu]):
# ... alors on compte un nombre de cycle CPU égal au quantum...
for i in range(quantum):
# ... et tant qu'il reste des instructions disponibles au processus élu...
if index[numero_processus_elu] < temps_execution[numero_processus_elu]:
# ... on les rajoute à la liste des processus ordonnancés
processus_ordonnances.append(numero_processus_elu + 1)
# On incrémente le compteur d'instruction du processus élu
index[numero_processus_elu] += 1
# On incrémente le compteur de cycles CPU
temps += 1
# Si le processus élu est terminé...
if index[numero_processus_elu] >= temps_execution[numero_processus_elu]:
# ... on le marque comme terminé, et on incrémente le nombre de processus terminés
nombre_processus_termines += 1
processus_termines[numero_processus_elu] = True
# Si tous les processus sont terminés, le traitement l'est aussi
if nombre_processus_termines == nombre_processus:
fini = True
# On élit le processus suivant, en pensant à reboucler
numero_processus_elu += 1
if numero_processus_elu == nombre_processus:
numero_processus_elu = 0
return processus_ordonnances
def calculs_sejour_attente(processus_ordonnances, temps_arrivage, temps_execution):
"""
Calcule les temps de séjour et d'attente des processus selon leur méthode
d'ordonnancement.
Arguments :
- processus_ordonnances (list) : liste contenant les processus ordonnancés
(comme renvoyée par "fifo" ou "tourniquet")
- temps_arrivage (list) : liste des temps d'arrivage
- temps_execution (list) : liste des temps d'exécution
Renvoie :
un tuple contenant deux listes :
* la première contient les temps de séjour des différents processus
* la seconde contient les temps d'attente des différents processus.
"""
nombre_processus = len(temps_arrivage) # Nombre de processus
longueur_file = len(processus_ordonnances) # Longueur de la file d'ordonnancement
temps_sortie = [0] * nombre_processus # Initialisation des temps de sortie
temps_sejour = [0] * nombre_processus # Initialisation des temps de séjour
temps_attente = [0] * nombre_processus # Initialisation des temps d'attente
for i in range(nombre_processus):
# Détermination du temps de sortie du processus n°i
temps_sortie[i] = 0
for j in range(longueur_file):
if processus_ordonnances[j] == i + 1:
temps_sortie[i] = j
temps_sortie[i] += 1
# Calcul des temps de séjour et d'attente correspondant
temps_sejour[i] = temps_sortie[i] - temps_arrivage[i]
temps_attente[i] = temps_sejour[i] - temps_execution[i]
return temps_sejour, temps_attente
def affichage_processus_ordonnances(processus_ordonnances):
"""
Création d'une chaîne de caractère pour affichage dans la console à partir de la
liste des processus ordonnancés.
Arguments :
- processus_ordonnances (list) : liste contenant les processus ordonnancés
Renvoie :
une chaîne de caractère correspondant aux processus ordonnancés avec la convention
suivante : n°1 = "A", n°2 = "B", etc.
"""
resultat = ""
for i in range(len(processus_ordonnances)):
resultat = resultat + chr(64 + processus_ordonnances[i])
return resultat
def calcul_moyenne(liste):
"""
Calcul de la moyenne des valeurs de la liste fournie en argument
Arguments :
- liste (list) : liste de nombres (int ou float)
Renvoie :
La moyenne des valeurs de la liste sous forme d'un float
"""
somme = 0
for i in range(len(liste)):
somme += liste[i]
return somme / len(liste)
def afficher_gantt(processus_ordonnances, titre="Ordonnancement"):
"""
Affiche un diagramme de Gantt à partir d'une liste d'ordonnancement.
Chaque unité de temps correspond à une case colorée indiquant le processus actif.
Arguments :
- processus_ordonnances (list) : liste contenant les processus ordonnancés
- titre (str) : titre du graphique (par défaut "Ordonnancement")
Renvoie :
pas de valeur de retour, mais affiche une fenêtre Matplotlib avec le diagramme
"""
# Taille du graphique
fig, ax = plt.subplots(figsize=(10, 2))
# Pour chaque unité de temps, tracer une petite barre colorée
temps = 0
for i in processus_ordonnances:
couleur = COULEURS[(i - 1) % len(COULEURS)]
ax.barh(0, 1, left=temps, color=couleur, edgecolor="black")
temps += 1
# Définition des axes
ax.set_xlim(0, temps)
ax.set_ylim(-0.5, 0.5)
ax.set_xlabel("Temps")
ax.set_yticks([])
ax.set_title(titre)
# Légende
legendes = []
numeros = sorted(set(processus_ordonnances))
for i in numeros:
legendes.append(mpatches.Patch(color=COULEURS[(i - 1) % len(COULEURS)], label=f"Processus {chr(64+i)}"))
ax.legend(handles=legendes, bbox_to_anchor=(1.02, 1), loc='upper left')
# Affichage de la fenêtre
plt.tight_layout()
plt.show()
return None
def afficher_tous_les_gantt(ordonnancements, nb_processus):
"""
Affiche plusieurs diagrammes de Gantt (un par méthode d'ordonnancement)
dans une seule fenêtre matplotlib, avec une légende unique.
Arguments :
- ordonnancements (list) : liste de tuples (nom_methode, liste_processus_ordonnances)
- nb_processus (int) : nombre total de processus
Renvoie :
pas de valeur de retour, mais affiche une fenêtre Matplotlib avec les diagrammes
"""
# Taille du graphique
n = len(ordonnancements)
fig, axes = plt.subplots(n, 1, figsize=(10, 0.8 * n), sharex=True)
# Tracé des différents diagrammes d'ordonnancement
if n == 1:
axes = [axes] # pour le cas où il n’y a qu’un seul graphe
for i, (nom, processus_ordonnances) in enumerate(ordonnancements):
ax = axes[i]
temps = 0
for j in processus_ordonnances:
couleur = COULEURS[(j - 1) % len(COULEURS)]
ax.barh(0, 1, left=temps, color=couleur, edgecolor="black")
temps += 1
# Définition des axes
ax.set_xlim(0, len(processus_ordonnances))
ax.set_ylim(-0.5, 0.5)
ax.set_yticks([])
ax.set_ylabel(nom, rotation=0, labelpad=40, fontsize=10, fontweight="bold", va="center")
ax.grid(axis='x', linestyle=':', linewidth=0.5)
if i == n - 1:
ax.set_xlabel("Temps")
# Légende commune
legendes = [mpatches.Patch(color=COULEURS[i % len(COULEURS)], label=f"Processus {chr(65+i)}") for i in range(nb_processus)]
fig.legend(handles=legendes, loc="upper center", ncol=nb_processus, frameon=False)
# Titre et tracé de la fenêtre
plt.suptitle("Comparaison des ordonnancements", fontsize=14, fontweight="bold", y=0.95)
plt.tight_layout(rect=[0, 0, 1, 0.93])
plt.show()
return None
def afficher_arrivees_et_durees(temps_arrivage, temps_execution):
"""
Affiche un diagramme illustrant le moment d'arrivée et la durée d'exécution
de chaque processus avant l'ordonnancement.
Paramètres :
- temps_arrivage (list[int]) : temps d'arrivée des processus
- temps_execution (list[int]) : durées d'exécution
Renvoie :
pas de valeur de retour, mais affiche une fenêtre Matplotlib avec le diagramme
"""
n = len(temps_arrivage)
# Calcul du temps total nécessaire pour l'axe des abscisses
t_max = max(temps_arrivage[i] + temps_execution[i] for i in range(n))
t_max = math.ceil(t_max)
# Création du graphique
fig, ax = plt.subplots(figsize=(8, 1 + 0.5 * n))
for i in range(n):
debut = temps_arrivage[i]
duree = temps_execution[i]
nom = chr(65 + i)
couleur = COULEURS[i % len(COULEURS)]
# Barre horizontale du processus
ax.barh(y=i, width=duree, left=debut, height=0.5,
color=couleur, edgecolor="black")
# Nom du processus au centre
ax.text(debut + duree / 2, i, nom,
ha="center", va="center", color="white", fontweight="bold")
# Repères numériques (début et fin)
ax.text(debut - 0.1, i, f"{debut}", ha="right", va="center", fontsize=8, color="gray")
ax.text(debut + duree + 0.1, i, f"{debut + duree}", ha="left", va="center", fontsize=8, color="gray")
# Réglages des axes et titre
ax.set_xlim(0, t_max + 1)
ax.set_xticks(range(0, t_max + 2, 1)) # graduations entières
ax.set_xlabel("Temps")
ax.set_yticks(range(n))
ax.set_yticklabels([chr(65 + i) for i in range(n)])
ax.invert_yaxis()
ax.set_title("Chronologie des arrivées et durées des processus", fontweight="bold")
# Quadrillage en "cases"
ax.grid(True, which='both', axis='x', color='gray', linestyle=':', linewidth=0.8)
for y in range(n):
ax.axhline(y + 0.5, color='lightgray', linewidth=0.5) # lignes horizontales légères
# Légende
legendes = [mpatches.Patch(color=COULEURS[i % len(COULEURS)], label=f"Processus {chr(65+i)}") for i in range(n)]
ax.legend(handles=legendes, loc="upper right", frameon=False, fontsize=8)
# Tracé de la fenêtre
plt.tight_layout()
plt.show()
return None
def demo():
"""
Démonstration des fonctions d'ordonnancement
Arguments :
aucun
Renvoie :
pas de valeur de retour, mais lance une démonstration complète :
* création des processus
* ordonnancement des processus par FIFO et Round-Robin avec plusieurs valeurs de quantum
* détermination des temps de séjour et d'attente
* détermination de la meilleure méthode d'ordonnancement
* affichage éventuel des diagrammes de Gantt sous forme graphique (séparés ou groupés)
"""
# Différents jeux de test
#temps_arrivage = [0, 1, 2, 4]
#temps_execution = [3, 6, 6, 2]
#temps_arrivage = [0, 1, 2, 3, 4]
#temps_execution = [4, 3, 2, 3, 5]
#temps_arrivage = [0, 2, 3, 10, 12, 15]
#temps_execution = [9, 8, 3, 4, 1, 4]
temps_arrivage = [0, 3, 5, 6]
temps_execution = [8, 6, 2, 1]
#temps_arrivage = [0, 2, 4]
#temps_execution = [7, 3, 6]
#temps_arrivage = [0, 1, 2, 4, 6, 7, 8, 9, 11, 12]
#temps_execution = [8, 7, 8, 7, 7, 5, 6, 7, 6, 7]
# Sélection des données à traiter
print()
print("Le jeu de test actuel est :")
print("Temps d'arrivage =", temps_arrivage)
print("Temps d'exécution =", temps_execution)
print()
choix = input("Voulez-vous utiliser ce jeu de test (1) ou entrer vos données (2) ? ")
if choix == "2":
(temps_arrivage, temps_execution) = creation_processus()
print()
# Sélection de la sortie des résultats : console ou fichier
sortie = "console"
choix = input("Voulez-vous les résultats dans la console (1) ou dans un fichier (2) ? ")
if choix == "2":
print()
nom_fichier = input("Nom du fichier ? ")
sortie = "fichier"
fichier = open(nom_fichier, "w")
sys.stdout = fichier
sys.stderr = fichier
# Dans le cas d'une sortie console, choix de la sortie graphique
graphique = "aucun"
if sortie == "console":
print()
print("Voulez-vous :")
print("1: un graphique par ordonnancement")
print("2: un graphique regroupant tous les ordonnancements")
print("3: aucun graphique")
print()
choix = input("Entrez votre choix ? ")
if choix == "1":
graphique = "individuel"
if choix == "2":
graphique = "collectif"
# Affichage de la chronologie d'arrivée des processus :
print()
print()
print(" ******************************************")
print(" ****** ORDONNANCEMENT DES PROCESSUS ******")
print(" ******************************************")
print()
print(" 11111111112222222222333333333344444444445")
print("012345678901234567890123456789012345678901234567890")
print("| | | | | |")
for i in range(len(temps_arrivage)):
print(" " * temps_arrivage[i] + chr(65 + i) * temps_execution[i])
# Affichage des temps d'arrivage, des temps d'exécution, et du temps d'exécution moyen
print()
print("Temps d'arrivage des différents processus :", temps_arrivage)
print("Temps d'exécution des différents processus :", temps_execution)
print()
print("Temps d'exécution moyen par processus :", round(sum(temps_execution)/len(temps_execution), 1))
# Si on a choisi une sortie graphique, affichage du graphique des arrivées des processus
if graphique != "aucun":
afficher_arrivees_et_durees(temps_arrivage, temps_execution)
# Création de listes pour stocker les temps d'attente et de séjour moyens,
# la moyenne des deux résutats précédents, les méthodes utilisées et les listes ordonnancées
temps_sejour = []
temps_attente = []
moyennes = []
methodes = []
processus_ordonnances = []
# Ordonnancement selon la méthode FIFO, avec affichage des processus ordonnancés, temps
# de séjour des processus, temps d'attente des procesus, et temps d'attente moyen
print()
print("Ordonnancement avec la méthode FIFO :")
ordonnancement_fifo = fifo(temps_arrivage, temps_execution)
print("Processus ordonnancés selon :", affichage_processus_ordonnances(ordonnancement_fifo))
calcul_fifo = calculs_sejour_attente(ordonnancement_fifo, temps_arrivage, temps_execution)
print("Temps de séjour :", calcul_fifo[0])
print("Temps d'attente :", calcul_fifo[1])
temps_sejour_moyen_fifo = round(calcul_moyenne(calcul_fifo[0]), 1)
temps_attente_moyen_fifo = round(calcul_moyenne(calcul_fifo[1]), 1)
temps_sejour.append(temps_sejour_moyen_fifo)
temps_attente.append(temps_attente_moyen_fifo)
moyenne = (temps_sejour_moyen_fifo + temps_attente_moyen_fifo) / 2
moyennes.append(round(moyenne, 1))
methodes.append("FIFO")
processus_ordonnances.append(ordonnancement_fifo)
print("Soit un temps d'attente moyen de :", temps_attente_moyen_fifo)
print("Et un temps de séjour moyen de :", temps_sejour_moyen_fifo)
# Création éventuelle du graphe correspondant à l'ordonnancement FIFO
if graphique == "individuel":
afficher_gantt(ordonnancement_fifo, "Ordonnancement FIFO")
# On teste l'ordonnancement selon la méthode du tourniquet en faisant varier le quantum
# entre 1 et le temps d'exécution maximal. Pour chaque valeur du quantum, affichage des
# processus ordonnancés, temps de séjour des processus, temps d'attente des procesus, et
# temps d'attente moyen par processus
for quantum in range(1, max(temps_execution) + 1):
print()
print("Ordonnancement avec la méthode du tourniquet : ( quantum =", quantum, ")")
ordonnancement_tourniquet = tourniquet(temps_arrivage, temps_execution, quantum)
print("Processus ordonnancés selon :", affichage_processus_ordonnances(ordonnancement_tourniquet))
calcul_tourniquet = calculs_sejour_attente(ordonnancement_tourniquet, temps_arrivage, temps_execution)
print("Temps de séjour :", calcul_tourniquet[0])
print("Temps d'attente :", calcul_tourniquet[1])
temps_sejour_moyen_tourniquet = round(calcul_moyenne(calcul_tourniquet[0]), 1)
temps_attente_moyen_tourniquet = round(calcul_moyenne(calcul_tourniquet[1]), 1)
temps_sejour.append(temps_sejour_moyen_tourniquet)
temps_attente.append(temps_attente_moyen_tourniquet)
moyenne = (temps_sejour_moyen_tourniquet + temps_attente_moyen_tourniquet) / 2
moyennes.append(round(moyenne, 1))
methodes.append("R.R." + str(quantum))
processus_ordonnances.append(ordonnancement_tourniquet)
print("Soit un temps de séjour moyen de :", temps_sejour_moyen_tourniquet)
print("Et un temps d'attente moyen de :", temps_attente_moyen_tourniquet)
# Création éventuelle du graphe correspondant à l'ordonnancement tourniquet en cours
if graphique == "individuel":
afficher_gantt(ordonnancement_tourniquet, f"Round Robin (quantum = {quantum})")
# Affichage du tableau bilan
print()
print("BILAN :")
print("-------")
print()
print("-" * 60)
print("| Méthode | t(séjour) | t(attente) | moyenne |")
print("-" * 60)
for i in range(len(temps_attente)):
print(f"| {methodes[i]:<10} | {temps_sejour[i]:<13} | {temps_attente[i]:<13} | {moyennes[i]:<11} |")
print("-" * 60)
print()
# Détermination de la (ou des) meilleure(s) méthode(s) d'ordonnancement
meilleurs_choix = []
valeur_optimale = min(moyennes)
for i in range(len(moyennes)):
if moyennes[i] == valeur_optimale:
meilleurs_choix.append(methodes[i])
if len(meilleurs_choix) == 1:
print("La meilleure méthode d'ordonnancement est :", meilleurs_choix[0])
else:
chaine = "Les meilleures méthodes d'ordonnancement sont : "
for i in range(len(meilleurs_choix) - 1):
chaine += meilleurs_choix[i] + ", "
chaine += meilleurs_choix[i + 1]
print(chaine)
# Création éventuelle du graphe regroupant tous les diagrammes d'ordonnancement
if graphique == "collectif":
processus_a_afficher = []
for i in range(len(processus_ordonnances)):
processus_a_afficher.append((methodes[i], processus_ordonnances[i]))
afficher_tous_les_gantt(processus_a_afficher, len(temps_arrivage))
# En cas de sortie fichier, redirection vers la console et fermeture du fichier
if sortie == "fichier":
sys.stdout = sys.__stdout__
sys.stderr = sys.__stderr__
fichier.close()
print()
print("Les données ont été sauvegardées dans le fichier " + nom_fichier)
if __name__ == "__main__":
demo()
