Ordonnanceur

L'objectif de ce TP est d'établir de manière automatique des chronogrammes, étant donné une liste de processus et un algorithme d'ordonnancement. Ceci nous permettra de calculer ensuite des mesures statistiques des différents algorithmes d'ordonnancement afin de pouvoir les comparer entre eux.

Représentation des processus¶

Les processus sont représentés à l'aide d'instances de la classe Processus. Ils sont munis de quatre attributs :

leur pid (pour process identifier, c'est un entier unique au processus en question) ;
leur duree totale d'exécution nécessaire (exprimée en nombres de cycles du processeur) ;
leur instant d'arrivee (exprimé en nombre de cycles du processeur après l'instant initial \(t = 0\)) ;
leur duree_restante (exprimée en nombre de cycles du processeur) qui représente le temps d'exécution nécessaire avant la fin du processus. Initialement, la durée restante d'exécution d'un processus est égale à sa durée totale d'exécution.

Écrire une classe Processus permettant d'instancier des variables munies de ces attributs.
Instancier des variables p1, p2, et p3, représentant les processus dont on donne la description dans le tableau ci-dessous :

Processus Durée d'exécution Instant d'arrivée

P1 10 0

P2 4 3

P3 8 2

###

def testpy-undProcessus():bksl-nl """ Tests pour la méthode py-undpy-undreprpy-undpy-und """bksl-nl print("Tests de Processus.py-undpy-undreprpy-undpy-und passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import Processusbksl-nl# testpy-undProcessus()bksl-nlbksl-nldef testpy-undProcessus():bksl-nl """ Tests pour la méthode avancer """bksl-nl print("Tests de Processus.avancer passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import Processusbksl-nl# testpy-undProcessus()bksl-nlbksl-nldef testpy-undProcessus():bksl-nl """ Tests pour la méthode estpy-undtermine """bksl-nl print("Tests de Processus.estpy-undtermine passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import Processusbksl-nl# testpy-undProcessus()bksl-nlbksl-nldef testpy-undProcessus():bksl-nl """ Tests pour la méthode py-undpy-undinitpy-undpy-und """bksl-nl print("Tests de Processus.py-undpy-undinitpy-undpy-und passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import Processusbksl-nl# testpy-undProcessus()bksl-nlbksl-nldef testpy-undProcessus():bksl-nl """ Tests pour la méthode avancer2 """bksl-nl print("Tests de Processus.avancer2 passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import Processusbksl-nl# testpy-undProcessus()bksl-nlbksl-nldef testpy-undProcessus():bksl-nl """ Tests pour la méthode temps """bksl-nl print("Tests de Processus.temps passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import Processusbksl-nl# testpy-undProcessus()bksl-nlbksl-nl 5/5

class Processus:bksl-nl """Représente un processus"""bksl-nl def py-undpy-undinitpy-undpy-und(self, pid, arrivee, duree):bksl-nl """Processus, int, int, int -> None"""bksl-nl passbksl-nlbksl-nl def py-undpy-undreprpy-undpy-und(self):bksl-nl """ Processus -> strbksl-nl Renvoie une chaine de caractère représentant le processus self """bksl-nl passbksl-nl bksl-nl def avancer(self, d, t):bksl-nl """ Processus, int, int -> Nonebksl-nl Le processus (re)prend son exécution à la date t pour une durée d """bksl-nl passbksl-nl bksl-nl def estpy-undtermine(self):bksl-nl """ Processus -> boolbksl-nl Détermine si le processus p a terminé son exécution """bksl-nl passbksl-nl bksl-nl def py-undpy-undinitpy-undpy-und(self, pid, arrivee, duree):bksl-nl """ Initialise un processus """bksl-nl passbksl-nl bksl-nl def avancer(self, d, t):bksl-nl """ Processus, int, int -> Nonebksl-nl Avance le processus """bksl-nl passbksl-nl bksl-nl def sejour(self):bksl-nl """ Renvoie le temps de séjour de self """bksl-nl passbksl-nl bksl-nl def execution(self):bksl-nl """ Renvoie le temps d'exécution de self """bksl-nl passbksl-nl bksl-nl def attente(self):bksl-nl """ Renvoie le temps d'attente de self """bksl-nl passbksl-nl bksl-nl def latence(self):bksl-nl """ Renvoie le temps de latence de self """bksl-nl passbksl-nlbksl-nl

Représentation d'un processus¶

Écrire une méthode __repr__ de la classe Processus qui affiche une chaine de caractère représentant un processus à l'aide de son pid selon le schéma de l'énoncé.

def __repr__(self):
    """ Processus -> str
    Renvoie une chaine de caractère représentant le processus self """
    pass

Chronogramme¶

On représente un chronogramme à l'aide d'une instance de la classe Chronogramme. Une telle instance permet d'obtenir le temps écoulé t (exprimé en nombre de cycles du processeur) depuis le démarrage du premier processus et est munie d'un attribut table de type list qui stocke la suite des processus ayant été exécutés par le processeur à chacun de ses cycles jusqu'à l'instant t. On remarquera que t est donc égal au nombre d'éléments de table.

Par exemple, si p1, p2, et p3 sont trois objets de type Processus et table est la liste [p1, p1, p2, p3], cela veut dire que le processus p1 a été exécuté pendant deux cycles du processeur, puis que p2 et p3 ont tous les deux été exécutés pendant un cycle. Ainsi, 4 cycles du processeur se sont écoulés depuis l'instant initial.

Écrire une classe Chronogramme permettant d'instancier une variable munie d'un unique attribut table.

###

def testpy-undChronogramme():bksl-nl """ Tests pour la méthode tempspy-undecoule """bksl-nl print("Tests de Chronogramme.tempspy-undecoule passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import Chronogrammebksl-nl# testpy-undChronogramme()bksl-nlbksl-nldef testpy-undChronogramme():bksl-nl """ Tests pour la méthode enregistrer """bksl-nl print("Tests de Chronogramme.enregistrer passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import Chronogrammebksl-nl# testpy-undChronogramme()bksl-nlbksl-nldef testpy-undChronogramme():bksl-nl """ Tests pour la méthode py-undpy-undreprpy-undpy-und """bksl-nl print("Tests de Chronogramme.py-undpy-undreprpy-undpy-und passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import Chronogrammebksl-nl# testpy-undChronogramme()bksl-nlbksl-nl 5/5

class Chronogramme:bksl-nl """Représente un chronogramme"""bksl-nl def py-undpy-undinitpy-undpy-und(self):bksl-nl """Chronogramme -> None"""bksl-nl passbksl-nlbksl-nl def tempspy-undecoule(self):bksl-nl """ Chronogramme -> intbksl-nl Renvoie le nombre de cycles écoulés depuis l'instant initial """bksl-nl passbksl-nl bksl-nl def enregistrer(self, p, q):bksl-nl """ int, int -> Nonebksl-nl Enregistre l'information : le processus p est exécuté pendant q cycles """bksl-nl passbksl-nl bksl-nl def py-undpy-undreprpy-undpy-und(self):bksl-nl """ self -> strbksl-nl Renvoie une chaine de caractère représentant le chronogramme self """bksl-nl passbksl-nlbksl-nl

Méthode `temps_ecoule`¶

Écrire une méthode temps_ecoule de la classe Chronogramme qui renvoie le nombre de cycles écoulés depuis l'instant initial.

def temps_ecoule(self):
    """ Chronogramme -> int
    Renvoie le nombre de cycles écoulés depuis l'instant initial """
    pass

Ordonnanceur FIFO¶

On s'intéresse dans cette partie à un ordonnanceur de type FIFO préemptif : celui-ci suit la logique du premier arrivé, premier servi. Ainsi, les différents processus sont exécutés suivant leur ordre d'arrivée. L'ordonnanceur interrompt les processus à intervalle régulier, définit par un nombre de cycles appelé quantum. Si le dernier processus exécuté n'est pas terminé, alors son exécution reprend là où elle s'était arrêtée. On modélise un tel ordonnanceur à l'aide d'une classe OrdonnanceurFIFO.

Celui-ci sera muni des attributs :

chrono : un chronogramme qui sera mis à jour à chaque cycle du processeur. Cet attribut sera initialisé avec un chronogramme vide.
file_processus : une file contenant les processus à exécuter. Cet attribut sera initialisé par un objet de type File, vide.
quantum : le nombre de cycles du processeur pendant lesquels les processus s'exécutent avant d'être interrompus par le système. À chaque interruption, l'ordonnanceur sélectionne un processus pour exécution. Cet attribut sera initialisé avec une valeur par défaut de 1, qui pourra être modifiée en passant au constructeur de la classe un paramètre optionnel.

On utilisera le code suivant pour représenter et manipuler les objets de type File.

###

class Maillon:bksl-nl def py-undpy-undinitpy-undpy-und(self, v, n):bksl-nl self.valeur = vbksl-nl self.suivant = nbksl-nlbksl-nlclass File:bksl-nl """Une file d'entiers"""bksl-nl def py-undpy-undinitpy-undpy-und(self):bksl-nl """File -> Nonetype"""bksl-nl self.debut = Nonebksl-nl self.fin = Nonebksl-nlbksl-nl def estpy-undvide(self):bksl-nl """ File -> boolbksl-nl Détermine si la file self est vide """bksl-nl return self.debut is None and self.fin is Nonebksl-nl bksl-nl def enfiler(self, v):bksl-nl """ File, int -> Nonetypebksl-nl Ajoute l'élément v à la file self """bksl-nl if self.estpy-undvide():bksl-nl m = Maillon(v,None)bksl-nl self.debut = mbksl-nl self.fin = mbksl-nl else:bksl-nl nouveau = Maillon(v,None)bksl-nl maillonpy-undcourant = self.debutbksl-nl self.fin.suivant = nouveaubksl-nl self.fin = nouveaubksl-nl bksl-nl def defiler(self):bksl-nl """ File -> intbksl-nl Renvoie le premier élément de la file en le supprimant de celle-ci """bksl-nl if self.estpy-undvide():bksl-nl raise IndexError("la file est vide")bksl-nl valeur=self.debut.valeurbksl-nl self.debut=self.debut.suivantbksl-nl if self.debut is None:bksl-nl self.fin = Nonebksl-nl return valeurbksl-nlbksl-nl def examine(self):bksl-nl if self.estpy-undvide():bksl-nl raise IndexError("la file est vide")bksl-nl return self.debut.valeurbksl-nl bksl-nl bksl-nl def py-undpy-undstrpy-undpy-und(self):bksl-nl """ self -> strbksl-nl Construit la chaîne de caractères représentant la file self """bksl-nl s = ["[début]"]bksl-nl maillonpy-undcourant=self.debutbksl-nl while maillonpy-undcourant != None:bksl-nl # s=s+f' {maillonpy-undcourant.valeur}'bksl-nl s.append(f' {maillonpy-undcourant.valeur}')bksl-nl maillonpy-undcourant=maillonpy-undcourant.suivantbksl-nl s.append(" [fin]")bksl-nl return "".join(s)bksl-nlbksl-nl

Écrire une classe OrdonnaceurFIFO permettant d'instancier une variable munie de ces attributs. On importera pour cela la classe File depuis le module . Les objets de type File sont munis d'une méthode examine renvoie l'élément présent au début de la file sans le supprimer de la file.

###

def testpy-undOrdonnanceurFIFO():bksl-nl """ Tests pour la méthode ajoutepy-undprocessus """bksl-nl print("Tests de OrdonnanceurFIFO.ajoutepy-undprocessus passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import OrdonnanceurFIFObksl-nl# testpy-undOrdonnanceurFIFO()bksl-nlbksl-nldef testpy-undOrdonnanceurFIFO():bksl-nl """ Tests pour la méthode execpy-undquantum """bksl-nl print("Tests de OrdonnanceurFIFO.execpy-undquantum passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import OrdonnanceurFIFObksl-nl# testpy-undOrdonnanceurFIFO()bksl-nlbksl-nldef testpy-undOrdonnanceurFIFO():bksl-nl """ Tests pour la méthode exec """bksl-nl print("Tests de OrdonnanceurFIFO.exec passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import OrdonnanceurFIFObksl-nl# testpy-undOrdonnanceurFIFO()bksl-nlbksl-nl 5/5

class OrdonnanceurFIFO:bksl-nl """Représente un ordonnanceur"""bksl-nl def py-undpy-undinitpy-undpy-und(self, q=1):bksl-nl """OrdonnanceurFIFO, int -> None"""bksl-nl passbksl-nlbksl-nl def ajoutepy-undprocessus(self, ppy-undlist):bksl-nl """ OrdonnanceurFIFO, [Processus] -> Nonebksl-nl Ajoute à self.filepy-undprocessus les processus de ppy-undlist par ordre d'arrivée """bksl-nl passbksl-nl bksl-nl def execpy-undquantum(self):bksl-nl """ OrdonnanceurFIFO -> Nonebksl-nl Simule l'exécution d'un quantum """bksl-nl passbksl-nl bksl-nl def exec(self):bksl-nl """ OrdonnanceurFIFO -> Chronogrammebksl-nl Simule l'exécution des processus de la file et en renvoie le chronogramme """bksl-nl passbksl-nlbksl-nl

Ajout des processus¶

L'ordonnanceur FIFO exécute les processus dans leur ordre d'arrivée. On souhaite écrire une méthode ajoute_processus de la classe OrdonnanceurFIFO qui prend en argument une liste de processus p_list et qui les ajoute à la file self.file_processus de l'ordonnanceur self par ordre croissant d'instant d'arrivée. Pour cela, tant que p_list n'est pas vide, on cherche dans p_list le processus dont l'attribut arrivee est le plus petit, on le supprime de p_list et on l'enfile dans la file des processus de l'ordonnanceur.

On procède en deux étapes, détaillées ci-après.

Sélection du premier processus arrivé¶

Écrire une fonction renvoie_et_supprime_premier qui étant donné une liste (supposée non vide) de processus p_list renvoie le processus ayant le plus petit temps d'arrivée parmi les processus de la liste, en le supprimant de celle-ci. On écrira donc un algorithme de recherche de la valeur du minimum ainsi que de son indice d'occurrence, puis et utiliser une instruction du type l.pop(i) (supprime de la liste l l'élément d'indice i en le renvoyant).

###

def testpy-undrenvoiepy-undetpy-undsupprimepy-undpremier():bksl-nl """ Tests pour la fonction renvoiepy-undetpy-undsupprimepy-undpremier """bksl-nl print("Tests de renvoiepy-undetpy-undsupprimepy-undpremier passés avec succès.")bksl-nl return Truebksl-nlbksl-nl# from tp import renvoiepy-undetpy-undsupprimepy-undpremierbksl-nl# testpy-undrenvoiepy-undetpy-undsupprimepy-undpremier()bksl-nlbksl-nl 5/5

def renvoiepy-undetpy-undsupprimepy-undpremier(ppy-undlist):bksl-nl """ [Processus] -> Processusbksl-nl Renvoie et supprime de ppy-undlist le processus dont l'attribut arrivee est le plus petit """bksl-nl passbksl-nlbksl-nl

Ajout des processus à la file¶

Écrire une méthode ajoute_processus de la classe OrdonnanceurFIFO qui prend en argument une liste de processus p_list et qui les ajoute à la file self.file_processus par ordre croissant d'instant d'arrivée.

def ajoute_processus(self, p_list):
    """ OrdonnanceurFIFO, [Processus] -> None
    Ajoute à self.file_processus les processus de p_list par ordre d'arrivée """
    pass

Exécution d'un quantum¶

On souhaite écrire une méthode exec_quantum qui simule la sélection puis l'exécution sur le processeur d'un processus pendant self.quantum cycles. Dans le cas d'un ordonnanceur FIFO l'algorithme est très simple :

récupérer le premier processus de la file des processus ;
enregistrer dans le chronogramme l'information de l'exécution du processus ;
avancer l'exécution du processus de self.quantum unités de temps ;
si le processus est terminé à l'issue de cette étape, le retirer de la file des processus à exécuter.

Méthode `enregistrer`¶

Écrire une méthode enregistrer de la classe Chronogramme qui enregistre dans le chronogramme self l'information selon laquelle le processus p a été exécuté pendant q cycles du processeur. Ainsi, cette méthode ajoute q fois le processus p la fin du tableau self.table.

def enregistrer(self, p, q):
    """ int, int -> None
    Enregistre l'information : le processus p est exécuté pendant q cycles """
    pass

Méthode `avancer`¶

Écrire une méthode avancer de la classe Processus qui diminue la durée d'exécution restante du processus self de d si l'instant t est supérieur à l'instant d'arrivée du processus.

def avancer(self, d, t):
    """ Processus, int, int -> None
    Le processus (re)prend son exécution à la date t pour une durée d """
    pass

Méthode `est_termine`¶

Écrire une méthode est_termine de la classe Processus qui renvoie True si et seulement si le processus self a terminé son exécution. On effectuera pour cela un test utilisant l'attribut duree_restante du processus self.

def est_termine(self):
    """ Processus -> bool
    Détermine si le processus p a terminé son exécution """
    pass

Méthode `exec_quantum`¶

Écrire une méthode exec_quantum qui implémente l'algorithme d'ordonnanceur FIFO décrit dans l'énoncé.

def exec_quantum(self):
    """ OrdonnanceurFIFO -> None
    Simule l'exécution d'un quantum """
    pass

Représentation d'un chronogramme et conclusion¶

Méthode `repr`¶

Écrire une méthode __repr__ de la classe Chronogramme qui affiche la chaine de caractère de votre choix qui permet de représenter un chronogramme. On pourra utiliser l'instruction str(p) où p est un processus pour obtenir une chaine de caractère représentant le processus p.

def __repr__(self):
    """ self -> str
    Renvoie une chaine de caractère représentant le chronogramme self """
    pass

Chronogramme complet¶

Écrire une méthode exec de la classe OrdonnanceurFIFO qui étant donné un ordonnanceur FIFO self simule son exécutition jusqu'à ce que la file des processus à exécuter soit vide. Cette méthode renverra le chronogramme de l'exécution.

Comparer avec les résultats vus en exercice.

def exec(self):
    """ OrdonnanceurFIFO -> Chronogramme
    Simule l'exécution des processus de la file et en renvoie le chronogramme """
    pass

Étude des processus¶

On souhaite étudier "l'efficacité" d'un algorithme d'ordonnancement. Pour cela, on étudie le temps de séjour, le temps d'attente, et le temps de latence moyen des processus gérés. On rappelle les définitions suivantes :

temps de termaison: instant \(t\) auquel le processus termine.
temps d'exécution: c'est le temps pendant lequel le processus a utilisé le processeur.
temps de séjour: c'est la différence entre le temps de terminaison et le temps d'arrivée du processus. C'est la durée pendant laquelle l'algorithme d'ordonnancement doit gérer le processus.
temps d'attente: c'est la différence entre le temps d'exécution et le temps de séjour. C'est la durée pendant laquelle le processus a attendu un accès au processeur.
temps de latence: c'est la différence entre le début de l'exécution du processus sur le processeur et l'arrivée du processus dans la file des processus en cours d'exécution. C'est la durée pendant lequel le processus "attend" son premier accès au processeur.

Modification des attributs des `Processus`¶

Ajouter à la classe Processus deux attributs initialisés avec la valeur -1 :

l'attribut debut : représente l'instant t de la première exécution du processus par le processeur. Dans ce contexte, -1 signifie que le processus n'a pas encore accédé au processeur.
l'attribut fin : représente l'instant t de la fin de la dernière exécution du processus par le processeur. Dans ce contexte, -1 signifie que le processus n'est pas encore terminé.

def __init__(self, pid, arrivee, duree):
    """ Initialise un processus """
    pass

Modification de la méthode `avance`¶

Modifier la méthode avancer de la classe Processus : p.avancer(d, t) diminue la durée restante d'exécution du processus p et met à jour les attributs debut et fin de la manière suivante :

s'il s'agit de la première exécution du processus, alors on sauvegarde l'instant t de l'exécution du processus ;
si après diminution de la durée restante d'exécution le processus est terminé : on sauvegarde l'instant d + t de fin du processus.

def avancer(self, d, t):
    """ Processus, int, int -> None
    Avance le processus """
    pass

Mesurer l'exécution d'un processus¶

Ajouter à la classe Processus les méthodes sejour, attente, latence qui renvoient respectivement les temps de séjour, d'attente et de latence du processus self, lorsque le processus a terminé son exécution.

def sejour(self):
    """ Renvoie le temps de séjour de self """
    pass

def execution(self):
    """ Renvoie le temps d'exécution de self """
    pass

def attente(self):
    """ Renvoie le temps d'attente de self """
    pass

def latence(self):
    """ Renvoie le temps de latence de self """
    pass

Statistiques d'un algorithme d'ordonnancement¶

Déduire des questions précédentes une méthode statistiques de la classe OrdonnanceurFIFO qui affiche sur la sortie standard les temps de séjour moyen, d'attente moyen et de latence moyen de l'ordonnancement généré par l'ordonnanceur self pour les processus ayant été exécutés.

Cette méthode sera toujours appelée après la méthode exec. On pourra modifier la méthode ajoute_processus de telle sorte qu'en plus de remplir la file_processus elle sauvegarde également la liste liste_processus des processus exécutés (on pourra pour cela ajouter un attribut à la classe OrdonnanceurFIFO). On prendra garde aux effets de bords de la fonction renvoie_et_supprime_premier.
1. Adapter le code de la classe OrdonnanceurFIFO pour écrire une classe OrdonnanceurSJF représentant un ordonnanceur préemptif appliquant la politique du plus court travail d'abord (Shortest Job First) : à chaque intervalle de temps, l'ordonnanceur choisit dans la file d'attente le processus avec la durée d'exécution restante la plus courte.
2. Comparer les statistiques d'un ordonnanceur FIFO avec celles d'un ordonnanceur SJF.

Processus	Durée d'exécution	Instant d'arrivée
`P1`	10	0
`P2`	4	3
`P3`	8	2