Correction : TP algorithmes d'ordonnancement

Modélisation des processus


class Processus:
    """
    Modélise un processus.
    """
    def __init__(self, id: str, date_arrivee: int, duree: int):
        """
        id : identifiant (str)
        duree : durée ( restante ) d’exécution (int)
        date_arrivee : date d'arrivée dans la file d'exécution (int)
        """
        self.id = id
        self.duree = duree
        self.date_arrivee = date_arrivee

    def executer(self)->None:
        """
        Diminue la durée d’exécution du processus de 1.
        """
        self.duree -= 1

    def est_termine(self)->bool:
        """
        renvoie un booléen signalant si l’exécution du processus est terminée ( durée d’exécution = 0 )
        """
        return self.duree == 0
			
processus = [Processus('P1', 0, 6), Processus('P2', 1, 4), Processus('P3', 3, 1), Processus('P4', 5, 3)]

Algorithmes non-préemptifs

FIFO


from ordonnanceur import Ordonnanceur
from processus import Processus

class FIFO(Ordonnanceur):

    def inserer(self, p):
        self.file_execution.append(p)
			
processus = [Processus('P1', 0, 6), Processus('P2', 1, 4), Processus('P3', 3, 1), Processus('P4', 5, 3)]		

ordo = FIFO(processus)
print(ordo)

0	1	2	3	4	5	6	7	8	9	10	11	12	13	
P1	P1	P1	P1	P1	P1	P2	P2	P2	P2	P3	P4	P4	P4	
>>>

Temps de séjour moyen :

P1 : 6 - 0 = 6
P2 : 10 - 1 = 9
P3 : 11 - 3 = 8
P4 : 14 - 5 = 9
Moyenne : (6+9+8+9)/4 = 8

Temps d'attente moyen :

P1 : 0 - 0 = 0
P2 : 6 - 1 = 5
P3 : 10 - 3 = 7
P4 : 11 - 5 = 6
Moyenne : (0+5+7+6)/4 = 4,5

On doit pouvoir faire mieux...

SJF


from ordonnanceur import Ordonnanceur
from processus import Processus

class SJF(Ordonnanceur):

    def inserer(self, p):
        self.file_execution.append(p) # position actuelle = dernier élément de la file
        place = len(self.file_execution)-1 # indice actuel du processus dans la file d’exécution ( indice du dernier élément )

        while place > 1 and p.duree < self.file_execution[place-1].duree:
            self.file_execution[place] = self.file_execution[place-1]
            place -= 1

        self.file_execution[place] = p
			
processus = [Processus('P1', 0, 6), Processus('P2', 1, 4), Processus('P3', 3, 1), Processus('P4', 5, 3)]		

ordo = SJF(processus)
print(ordo)

0	1	2	3	4	5	6	7	8	9	10	11	12	13	
P1	P1	P1	P1	P1	P1	P3	P4	P4	P4	P2	P2	P2	P2
>>>

Temps de séjour moyen :

P1 : 6 - 0 = 6
P2 : 14 - 1 = 13
P3 : 7 - 3 = 4
P4 : 10 - 5 = 5
Moyenne : (6+13+4+5)/4 = 7

Temps d'attente moyen :

P1 : 0 - 0 = 0
P2 : 10 - 1 = 9
P3 : 6 - 3 = 3
P4 : 7 - 5 = 2
Moyenne : (0+9+3+2)/4 = 3,5

Les processus restent presque aussi longtemps dans la file d’exécution, mais ils attendent moins longtemps pour être élu : plus de réactivité !

Algorithmes préemptifs

SRTF


from ordonnanceur import Ordonnanceur
from processus import Processus

class SRTF(Ordonnanceur):

    def inserer(self, p):
        self.file_execution.append(p)
        place = len(self.file_execution)-1 

        while place > 0 and p.duree < self.file_execution[place-1].duree: # le processus peut prendre la première place !
            self.file_execution[place] = self.file_execution[place-1]
            place -= 1

        self.file_execution[place] = p
			
processus = [Processus('P1', 0, 6), Processus('P2', 1, 4), Processus('P3', 3, 1), Processus('P4', 5, 3)]		

ordo = SRTF(processus)
print(ordo)

0	1	2	3	4	5	6	7	8	9	10	11	12	13	
P1	P2	P2	P3	P2	P2	P4	P4	P4	P1	P1	P1	P1	P1
>>>

Temps de séjour moyen :

P1 : 14 - 0 = 14
P2 : 6 - 1 = 5
P3 : 4 - 3 = 1
P4 : 9 - 5 = 4
Moyenne : (14+5+1+4)/4 = 6

Temps d'attente moyen :

P1 : 0 - 0 = 0
P2 : 1 - 1 = 0
P3 : 3 - 3 = 0
P4 : 6 - 5 = 1
Moyenne : (0+0+0+1)/4 = 0,25

Encore plus réactif : les processus n'attendent presque pas avant de commencer leur exécution, et le temps d'exécution global est un peu plus court.

SRTF semble être l'algorithme optimal, mais en pratique, il est très difficile de connaître la durée exacte d'exécution d'un processus.

RR


from ordonnanceur import Ordonnanceur
from processus import Processus

class RR(Ordonnanceur):

    def __init__(self, processus: list[Processus], quantum: int):
        super().__init__(processus) # appelle le constructeur de la classe parente
        self.quantum = quantum

    def inserer(self, p):
        self.file_execution.append(p)

    def tick(self):
        # un nouveau processus ( s'il en reste ! ) arrive ?
        if len(self.processus) != 0:
            p = self.processus[0]
            if p.date_arrivee == self.temps:
                self.inserer(p)
                self.processus.pop(0)

        # un quantum s'est écoulé ?
        if self.temps%self.quantum == 0: # c'est à dire : la date est un multiple du quantum
            self.file_execution.append(self.file_execution.pop(0)) # on sort le processus élu et on le replace en queue de file d'exécution

        # éxécution du processus élu
        elu = self.file_execution[0]
        elu.executer()

        # tick: elu
        self.ticks.append(elu)

        # elu terminé ?
        if elu.est_termine():
            self.file_execution.pop(0)

        self.temps += 1
			
processus = [Processus('P1', 0, 6), Processus('P2', 1, 4), Processus('P3', 3, 1), Processus('P4', 5, 3)]		
quantum = 2

ordo = RR(processus, quantum)
print(ordo)

0	1	2	3	4	5	6	7	8	9	10	11	12	13	
P1	P1	P2	P2	P1	P1	P3	P2	P4	P4	P1	P1	P4	P2
>>>

Temps de séjour moyen :

P1 : 12 - 0 = 12
P2 : 14 - 1 = 13
P3 : 7 - 3 = 4
P4 : 13 - 5 = 8
Moyenne : (12+13+4+8)/4 = 9,3

Temps d'attente moyen :

P1 : 0 - 0 = 0
P2 : 2 - 1 = 1
P3 : 6 - 3 = 3
P4 : 8 - 5 = 3
Moyenne : (0+1+3+3)/4 = 1,8

Le temps d'attente est correct, mais les processus mettent du temps à pouvoir terminer leur exécution.

Les performances dépendent beaucoup du quantum de temps choisi, ce n'est pas évident à déterminer...