Temps d'exécution de processus⚓︎
On considère une liste de processus pour lesquels sont précisés les temps d'arrivée, la durée supposée d'exécution.
Etats d'un processus
Un processus peut être dans un des trois états suivants : prêt, élu ou bloqué.
stateDiagram
[*] --> prêt
prêt --> élu
élu --> prêt
élu --> bloqué
bloqué --> prêt
élu --> [*]A l'inverse, le processus passera à l'état terminé (état final du diagramme représenté par un point cerclé de noir) quand sa durée d'exécution sera atteinte.
L'ordonnancement utilisé est le modèle tourniquet. (Les explications de cet ordonnacement peut se retrouver dans l'exercice Processus et tourniquet)
À tour de rôle, l'ordonnanceur attribuera à un processus, une durée QUANTUM pour poursuivre l'exécution. Plusieurs situations peuvent alors se produire :
- le processus se termine pendant cette période. Il passe à l'état
terminé. - le processus n'est pas encore
terminéà la fin de la période. Il passe à l'étatprêtet est de nouveau placé dans la file d'attente.
La fonction temps_execution prend en paramètre une liste de processus ordonnée suivant la valeur de l'attribut arrivee. Elle renvoie un dictionnaire, dont les clés sont les processus et les valeurs la liste des tuples (debut, fin) des exécutions successives du processus.
On définit les classes Processus et File.
La classe Processus
Un processus est un objet de la classe Processus. Il possède les attributs suivants :
nom: nom du processusarrivee: heure d'arrivée du processus dans la file d'attente.etat:"élu","prêt"et"terminé"duree: durée restante supposée d'exécution du processus.
Cette classe est celle travaillée dans l'exercice Etats des processus
Exemple d'utilisation d'un processus :
Exemples
>>> processus_courant = Processus("P1", 3, arrivee = 0)
>>> processus_courant.est_pret(0)
>>> processus_courant
{'etat': 'prêt', 'nom': 'P1', 'arrivee': 0, 'duree': 3}
>>> processus_courant.elit(2)
>>> processus_courant
{'etat': 'élu', 'nom': 'P1', 'arrivee': 0, 'duree': 3}
>>> processus_courant.execute()
>>> processus_courant
{'etat': 'élu', 'nom': 'P1', 'arrivee': 0, 'duree': 2}
>>> processus_courant.execute()
>>> processus_courant
{'etat': 'prêt', 'nom': 'P1', 'arrivee': 0, 'duree': 1}
>>> processus_courant.elit(2)
>>> processus_courant
{'etat': 'élu', 'nom': 'P1', 'arrivee': 0, 'duree': 1}
>>> processus_courant.execute()
>>> processus_courant
{'etat': 'terminé', 'nom': 'P1', 'arrivee': 0, 'duree': 0}
La classe File
Cette classe permet de représenter une file. Les exemples ci-dessous présentent l'interface de la classe.
A noter la méthode tete qui l'élément en tête mais sans le défiler.
>>> f = File()
>>> f.est_vide()
True
>>> f.enfile("a")
>>> f.enfile("b")
>>> f.enfile("c")
>>> f
['a', 'b', 'c']
>>> f.tete()
a
>>> f
['a', 'b', 'c']
>>> f.defile()
a
>>> f
(queue) c -> b (tête)
>>> f.est_vide()
False
Code (pour information)
class File():
def __init__(self):
self.file = []
def est_vide(self):
return len(self.file) == 0
def enfile(self, elt):
self.file.append(elt)
def defile(self):
assert not self.est_vide(), "une file vide ne peut être défilée"
return self.file.pop(0)
def tete(self):
return self.file[0]
def __repr__(self):
return str(self.file)
On définira deux files :
- une file
arriveesqui contiendra les processus qui vont arriver dans la file de l'ordonnanceur. - une file
file_attentequi correspond à la file d'attente des processus, gérée par l'ordonnanceur.
Example
On considère 4 processus P1, P2, P3 et P4. Les durées supposées d'exécution et l'heure d'arrivée dans la file d'attente sont résumées dans le tableau suivant :
| Processus | P1 | P2 | P3 | P4 |
|---|---|---|---|---|
| Durée en unité de temps | 3 | 4 | 2 | 1 |
| Heure d'arrivée | 1 | 2 | 3 | 4 |
À chaque passage à l'état élu, l'ordonnanceur donne, ici, 2qt pour continuer l'exécution.
On suppose de plus qu'aucun processus n'est bloqué pendant son exécution.
S'il y a simultanément arrivée d'un processus et passage d'un autre processus de l'état élu à l'état prêt, c'est le processus arrivant qui entre en premier dans la file d'attente.
On peut représenter l'évolution de l'exécution avec le schéma suivant :
gantt
title Déroulement de l'exécution
dateFormat SSS
axisFormat %L
section Arrivée
p1 : milestone, , 001,
p1bis : milestone, , 003,
p2 : milestone, , 002,
p2bis : milestone, , 005,
p3 : milestone, , 003,
p4 : milestone, , 004,
section Exécution
P1 : p1,001, 2ms
P1 : p1bis, after p3, 1ms
P2 :p2,after p1, 2ms
P2 :p2bis,after p4, 2ms
P3: p3, after p2, 2ms
P4 :p4,after p1bis , 1msPour une liste de processus, initialement stockés dans une file arrivees dans leur ordre d'arrivée, on souhaite récupérer les informations qui permettent de construire la représentation de la partie basse, à savoir pour chaque processus une liste de couples (debut, fin) donnant les périodes d'exécution du processus. Le tout étant regroupé dans un dictionnaire.
Exemples
>>> QUANTUM = 2
>>> arrivees = File()
>>> arrivees.enfile(Processus("P1", arrivee = 0, duree = 1))
>>> temps_execution(arrivees)
{"P1":[(0, 1)]}
>>> arrivees = File()
>>> arrivees.enfile(Processus("P1", arrivee = 0, duree = 3))
>>> temps_execution(arrivees)
{"P1":[(0, 2), (2,3)]}
>>> arrivees = File()
>>> arrivees.enfile(Processus("P1", arrivee = 1, duree = 3))
>>> temps_execution(arrivees)
{"P1":[(1, 3), (3,4)]}
>>> arrivees = File()
>>> arrivees.enfile(Processus("P1", arrivee = 0, duree = 3))
>>> arrivees.enfile(Processus("P2", arrivee = 1, duree = 3))
>>> temps_execution(arrivees)
{"P1":[(0, 2), (4,5)], "P2":[(2, 4), (5,6)]}
Voici l'algorithme utilisé :
- L'horloge est initialisée à zéro
- Tant qu'il reste un processus dans une des deux file ou comme processus courant :
- Si un nouveau processus arrive, le créer(passer son état de
Noneàprêt), et le mettre dans la file d'attente. - Si le processus courant est passé à l'état
"prêt"(il a utilisé son quota sans être terminé), le mettre dans la file d'attente. Il n'y a alors plus de processus courant(passage à l'état None). - S'il n'y a pas de processus courant et que la file d'attente n'est pas vide :
- on récupère le processus courant de la file d'attente
- l'ordonnanceur élit ce processus,
- on initialise, au temps d'horloge, l'horaire de début du quantum alloué.
- on incrémente l'horloge
- Si le processus courant est à l'état
"élu"- on l'exécute d'un temps d'horloge
- Si le processus courant n'est pas à l'état
"élu"- on enregistre sa période d'exécution
- si le processus courant est passé à l'état
"terminé"- il n'y a alors plus de processus courant(passage à l'état None).
- Si un nouveau processus arrive, le créer(passer son état de
Compléter le code suivant.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)