2

Click here to load reader

1 Politiques d’ordonnancement - LIPNfouquere/ENSEIGNEMENT/L2SR/TDTP_Syste… · Ordonnancement 1 Politiques d’ordonnancement ... Processus Type Date de d ebut d’ex ecution Dur

Embed Size (px)

Citation preview

Page 1: 1 Politiques d’ordonnancement - LIPNfouquere/ENSEIGNEMENT/L2SR/TDTP_Syste… · Ordonnancement 1 Politiques d’ordonnancement ... Processus Type Date de d ebut d’ex ecution Dur

Institut Galilee Systemes d’exploitation et ReseauxLicence 2

TD 3Ordonnancement

1 Politiques d’ordonnancementL’objectif de l’exercice est de comparer 4 politiques d’ordonnancement differentes : FIFO (First

In-First Out), SJF (ou PCTE, Shortest Job First), SRTF (ou PCTER, Shortest Remaining Time First)et RR (ou Tourniquet, Round Robin). Afin de comparer ces differentes politiques, nous utiliserons toutau long de l’exercice la meme description de processus s’executant sur le systeme (cf. tableau ci-dessous).

Precisions : Ces processus ne font pas d’entrees-sorties et leur priorite ne change pas en coursd’execution. On ne tiendra pas compte du temps de commutation des processus. Les processus sontexecutes sur le meme processeur.

Numero de processus Date de creation Duree supposee d’execution1 0 82 2 23 5 54 6 35 7 1

Pour chacune des politiques FIFO, SJF, SRTF, RR (avec un quantum de 2 unites de temps) :

1. Donnez le diagramme de Gantt de l’execution des processus.

2. Calculez le temps moyen de traitement et le temps moyen d’attente de cette politique.

3. Calculez le temps moyen de reponse. Que constatez-vous ?

4. Que se passe-t-il lorsque 2 processeurs sont disponibles ? et avec 3 ?

2 Politique multiple

L’ordonnancement dans les systemes actuels combine plusieurs classes d’ordonnancement utiliseesselon le type de processus qui s’execute :

— politique FIFO pour les taches tres prioritaires et fortement contraintes (temps reel).— politique RR pour les taches systeme.— politique RR a multiniveaux pour les taches utilisateur.

2.1 Round Robin a multiniveauxOn trouvera ci-dessous un algorithme pour la politique RR a multiniveaux pour une machine a un seul

processeur (elu est l’identifiant du processus en execution). On suppose n files notees F1, . . ., Fn ou lesprocessus sont ranges (un processus n’apparaıt que dans une seule file). Pour chaque processus P , P.fileest le numero de la file ou se trouve P . Pour chaque file Fi, size(Fi) retourne le nombre de processusdans la file Fi, pop(Fi) retourne le premier processus de la file Fi et l’enleve de la file, push(Fi, P ) met enqueue de file Fi le processus P (et le supprime d’une autre file si necessaire).Ces files ont des priorites decroissantes (i.e. on execute les processus presents dans la file F1, ceux de lafile F2 quand la file F1 est vide, etc.). La fonction Schedule renvoie le processus elu (0 s’il n’y a pas deprocessus en attente). En cas de changement de processus (a cause d’une demande d’entree-sortie ou

1

Page 2: 1 Politiques d’ordonnancement - LIPNfouquere/ENSEIGNEMENT/L2SR/TDTP_Syste… · Ordonnancement 1 Politiques d’ordonnancement ... Processus Type Date de d ebut d’ex ecution Dur

d’une fin de quantum), si le processus stoppe n’a pas termine ou si un nouveau processus est cree, laprocedure Insert est appelee.

function Schedulei← 1while i <= n do

if size(Fi) > 0 thenelu← pop(Fi)return elu

end ifi← i + 1

end whilereturn 0

end function

procedure Insert(P)if P is new then

push(F1, P )P.file← 1

elseq ← P.filej ← min(n, q + 1)push(Fj , P )P.file← j

end ifend procedure

1. Montrer par un exemple que cet algorithme peut creer une situation de famine.

2. Modifier l’algorithme pour eviter le probleme de famine.

2.2 Exemple avec politique mixteOn considere maintenant le systeme complet d’ordonnancement avec une file temps reel (RT, mode

FIFO), une file de processus systeme (Sys, methode RR avec quantum 3), une file de processus utilisateur(User, methode RR avec quantum 2). L’election d’un processus suit un protocole simple. Pour chaqueelection, l’ordonnanceur consulte la file RT. Si des processus sont en attente dans cette file, il les executetous en tenant compte de la politique de la file. Si aucun processus n’est en attente dans cette file,l’ordonnanceur passe a la file Sys et effectue le meme traitement. Si aucun processus n’est present dansla file Sys, il effectue le meme traitement avec la file User. Cette operation s’effectue a chaque election.

Processus Type Date de debut d’execution Duree supposee d’execution1 RT 0 22 Sys 0 33 User 2 64 RT 3 15 RT 4 26 Sys 9 47 Sys 10 38 User 15 59 RT 20 310 Sys 22 3

Donnez le diagramme de Gantt de l’execution des processus en utilisant cette politique mixte.

2