Processus et tourniquet
Lors de son fonctionnement, le système d'exploitation d'un ordinateur doit partager la ressource de calcul entre différents processus. Pour ce faire, il met en œuvre un algorithme d'ordonnancement. On s'intéresse dans cet exercice à l'algorithme du tourniquet (round-robin en anglais).
Dans cet algorithme :
- chaque processus est associé à une certaine durée d'exécution ;
- initialement, les processus sont tous placés dans une file ;
- à chaque itération de l'algorithme :
- le processeur pioche le premier processus de la file et l'exécute durant un certain de temps de calcul appelé quantum ;
- si, à l'issue de ce temps de calcul, le processus n'est pas terminé, il est ré-enfilé ;
- l'algorithme s'arrête lorsque la file est vide.
On fournit deux classes Processus et File permettant de mettre en œuvre cet algorithme. Ces classes sont d'ores et déjà importées dans l'éditeur.
La classe Processus
Cette classe permet de représenter un processus. Un objet de type Processus est caractérisé par deux attributs :
pid: nombre entier positif permettant d'identifier le processus. On notepidpour « process id » ;_duree: nombre entier positif ou nul représentant la durée d'exécution restante, exprimée en ms.
Les exemples ci-dessous présentent l'interface de la classe.
>>> p = Processus(123, 5) # création d'un processus
>>> p # affichage
(PID=123 ; durée=5)
>>> p.pid # accès au PID
123
>>> p.execute(3) # exécution durant 3 ms
>>> p.est_fini() # le processus est-il fini ?
False
>>> p.execute(3) # exécution durant 3 ms -> bloque à 0
>>> p1.est_fini()
True
Code (pour information)
class Processus:
"""Classe définissant un processus"""
def __init__(self, pid, duree):
self.pid = pid
self._duree = duree # ne pas modifier cet attribut
def execute(self, quantum):
"""Diminue la durée d'exécution restante de quantum. Bloque à 0"""
self._duree = max(0, self._duree - quantum)
def est_fini(self):
"""Renvoie le booléen répondant à la question 'Le processus est-il terminé ?'"""
return self._duree == 0
def __repr__(self):
"""Affichage"""
return f"(PID={self.pid} ; durée={self._duree})"
La classe File
Cette classe permet de représenter une file. Les exemples ci-dessous présentent l'interface de la classe.
>>> f = File()
>>> f.est_vide()
True
>>> f.enfile("a")
>>> f.enfile("b")
>>> f.enfile("c")
>>> f
(queue) c -> b -> a (tête)
>>> f.defile()
a
>>> f
(queue) c -> b (tête)
>>> f.est_vide()
False
Code (pour information)
from collections import deque
class File:
"""Classe définissant une structure de file"""
def __init__(self):
self.valeurs = deque([])
def est_vide(self):
"""Renvoie le booléen True si la file est vide, False sinon"""
return len(self.valeurs) == 0
def enfile(self, x):
"""Place x à la queue de la file"""
self.valeurs.appendleft(x)
def defile(self):
"""Retire et renvoie l'élément placé à la tête de la file.
Provoque une erreur si la file est vide
"""
if self.est_vide():
raise ValueError("La file est vide")
return self.valeurs.pop()
def __repr__(self):
"""Convertit la file en une chaîne de caractères"""
return f"{list(self.valeurs)}"
Écrire la fonction tourniquet qui prend en paramètres une file de processus file ainsi qu'un entier strictement positif quantum représentant la durée d'exécution allouée par l'algorithme à chaque itération (en ms).
Cette fonction renvoie la liste ordonnée des pid des processus exécutés.
On garantit que les processus présents dans la file ont tous des PID différents.
Exemples
>>> f = File()
>>> f.enfile(Processus(0, 5))
>>> f.enfile(Processus(1, 2))
>>> tourniquet(f, 1) # chaque processus est exécuté durant 1 ms
[0, 1, 0, 1, 0, 0, 0]
>>> f = File()
>>> f.enfile(Processus(8, 5))
>>> f.enfile(Processus(26, 2))
>>> f.enfile(Processus(7, 6))
>>> tourniquet(f, 6) # chaque processus est exécuté durant 6 ms
[8, 26, 7]
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)