[PDF] [PDF] Chapitre 5 : Ordonnancement

[PDF] SE1_TD3_Ordonnancement de processus_2012_correction

Exercice 2 : Sur un ordinateur, l'Ordonnanceur gère l'ordonnancement des processus par un tourniquet avec un quantum de 100 ms 1 Sachant que le temps 

[PDF] Examen de systèmes dexploitation 1 Exercice1 : Questions de Cours

Q1) la stratégie d'ordonnancement de processus la plus appropriée pour un (a ) Un quantum court dans un ordonnancement Round Robin donne un Exercice 2: Corrigé : Exercice1 : Q1) réponse : (c) Rond-Robin Q2) réponse : ( b) 

[PDF] –CORRIGÉ– Contrôle Syst`emes dexploitation, Réseaux Exercice 1

9 mar 2012 · Exercice 1 : Ordonnancement de processus (6 = 3 + 3) On consid`ere les cinq exécutions de processus suivants (la durée est exprimée en 

[PDF] Chapitre 5 : Ordonnancement

Ordonnancement Solution des exercices Solution de l'exercice 1 Le schéma ci- dessous décrit l'enchaînement des processus : P1 P2 P3 P4 P5 tot moy

[PDF] TD n°4 : Ordonnancement CORRECTION - MIAGE de Nantes

Ordonnancement à priorités Pour ordonnancer ces processus, on va commencer pas en choisir un premier parmi les n Exercice 2 – FCFS, RR, SJF et SRT

[PDF] Partie 6 : Ordonnancement de processus Exercice 1 :

Partie 6 : Ordonnancement de processus Exercice 1 : Considérez un système d' exploitation qui ordonnance les processus selon l'algorithme du tourniquet La file 

[PDF] Problèmes dordonnancement/exercices-corrigé/p1 Problèmes d

Problèmes d'ordonnancement - Exercices - corrigé I On considère 7 tâches devant passer sur un processeur donné a) La solution optimale de ce problème 

[PDF] processus - LAMA - Univ Savoie

Exercice 1 : Ordonnancement simple (non préemptif) On consid`ere les huit processus suivants : processus temps d'arrivée durée priorité P1 0 3 1 P2 1 - ε

[PDF] exercices corrigés sur l'échantillonnage des signaux

[PDF] exercices corrigés sur l'état de rapprochement bancaire pdf

[PDF] exercices corrigés sur la fonction de production pdf

[PDF] exercices corrigés sur la loi de khi deux pdf

[PDF] exercices corrigés sur la masse salariale

[PDF] exercices corrigés sur la ponctuation pdf

[PDF] exercices corrigés sur la production de l énergie électrique

[PDF] exercices corrigés sur la structure de l'atome pdf

[PDF] exercices corrigés sur le centre d inertie

[PDF] exercices corrigés sur le débit binaire

[PDF] exercices corrigés sur le décodage d adresses

[PDF] exercices corrigés sur le diagramme de mollier

[PDF] exercices corrigés sur le mouvement circulaire uniforme

[PDF] exercices corrigés sur le trafic téléphonique pdf

[PDF] exercices corriges sur les agregats economiques pdf

Ordonnancement

Introduction

Un ordonnanceur ( scheduler) comporte deux parties : l ordonnanceur de haut niveau (Long Term Scheduling): politique de dé cision, affectation de priorité l ordonnanceur de bas niveau ou distributeur ( Short Term Scheduling ou d ispatcher) : affectation d'un processeur à un processus Pour l'ordonnanceur de haut niveau, trois concepts sont à détai ller : n

Mode de décision

Il s'agit de spécifier des instants où les priorités des pro cessus sont évaluées et comparées et où des processus sont sélectionnés pour exécution. Entre deux instants consécutifs, l'allocation de processeurs aux processus ne change pas. - mode non pré-emptif : un processus en exécution continue jusqu'à ce qu'il se te rmine ou se bloque (non adéquat pour les systèmes temps réel et temps part agé) - mode pré-emptif : un processus en exécution peut être interrompu par diverses cau ses : un nouveau processus arrive, un processus existant est réveillé, un t emps q s'est écoulé, la priorité d'un processus prêt est devenue plus grande que celle du processus actif, .... compromis : la pré-emption sélective. Elle consiste à assigner

à chaque processus p une paire

de bits (u p , v p u p = 1 si p peut pré-empter un autre processus et 0 dans le cas contrai re ( u p représente la capacité de préemption d'un processus) v p = 1 si p peut être pré-empté par un autre processus et 0 dans le cas contraire ( v p représente une priorité d'exécution). n

Fonction de priorité

A tout moment une priorité est affectée à un processus du fait du résultat de l'application d'une fonction de priorité : ses variables sont divers paramètr es (liés au processus ou au système) et la valeur retour est la priorité . Les paramètres utilisés sont usuellement : l besoins mémoire l temps d'utilisation CPU l temps réel dans le système ( temps d'utilisation CPU + temps d 'attente) l temps total de service

Ordonnancement

Solution des exercices

Solution de l'exercice 1

Le schéma ci-dessous décrit l'enchaînement des processus :

P1P2P3P4P5tot.moy.

FIFO10111314196713,4

SJF191429357

RR1927414469,2

Le tableau, ci-dessus, indique les temps de présence, dans le systè me, des processus. La dernière colonne décrit le temps moyen passé par chaque processus. Il est clair que, sur cet exe mple, la stratégie SJF est la meilleure.

Solution de l'exercice 2

Comme pour l'exercice précédent, on trouve ci-dessous la chronolog ie des événements :

P1P2P3totalmoyenne

FIFO464144,66

LIFO471124

SJF624124

SRT721103,33

HRN634134,33

RR742134,33

Les résultats ci-dessus indiquent que SRT est, pour cet exemple, la m eilleure politique.

Solution de l'exercice 3

On reprendra les politiques de l'exemple précédent et les résul tats chronologiques et synthétiques sont consignés dans le tableau ci-dessous :

P1P2P3P4P5totalmoyenne

FIFO37768316,2

LIFO2072105448,8

SJF39268285,6

SRT39268285,6

HRN39568316,2

RR610598387,6

Les deux politiques les plus intéressantes sont ici SJF et SRT.

Solution de l'exercice 4

Rappelons que chaque estimation est calculée à partir de l'estimat ion précédente et de la durée effective : S n+1 =aT n +(1-a)S n Le tableau suivant donne les durées estimées et réelles des bur sts :

étape n

Tna = 0,8a = 0,5

S n S n+1 SnS n+1

0 102105

1625,255,5

245,24,245,54,75

364,245,654,755,38

445,655,935,384,69

5135,9311,594,698,84

61311,5912,728,8410,92

71312,7212,9410,9211,96

Le calcul des écarts entre les prévisions et la réalité donn e un écart type de 3,28 pour a=0,8 et 3,73 pour a=0,5.

Solution de l'exercice 5

On peut résumer dans un tableau la progression des deux processus P1 et P2 : processus temps de service atteint atemps réel rPriorité P1 P22 3251
4,5 P1

P224362

3,67 P1

P225473

6,16 P1 P22 65847
P1

P227695

7,83 P1 P2287 106
8,66 etc...... P1 P22

20202319

19,5 P1 P22 2121
2420
20,33 P1 P22

23222521

21,16
P1 P22

2423262222

On constate que le processus P2, bénéficiant d'une plus grande pri orité, obtient le premier le processeur. Cette situation se poursuit jusqu'à ce que la priorité de P1 rattrape ce lle de P2, c'est à dire 21 unités de temps après le départ de l'observation.

Ordonnancement

Exercices

Exercice 1

5 processus, P1, P2, P3, P4, P5 sont dans une file d'attente dans cet or

dre (P1 est le premier, P5 est le dernier). Leur exécution demande un temps total de service exprimé en unités arbitraires : processusP1P2P3P4P5 temps de service estimé101215

1) Décrire l'exécution des processus dans le cadre des politiques

d'ordonnancement FIFO, SJF, RR (avec un quantum de 1).

2) Quelle est ,de ces trois politiques, celle qui correspond à un te

mps minimal d'attente moyen par processus ?

Exercice 2

Trois processus P1, P2, P3 ont été chargés sur un système in formatique aux dates indiquées ci-dessous ; leur demande en durée de service est également indiquée (unité s de temps arbitraires). processusdate arrivéedurée de service P104 P202 P331 On considère les politiques d'ordonnancement suivantes : FIFO, LIFO,

SJF, SRT, HRN, RR . Pour les

politiques pré-emptives, le quantum est égal à 1 unité de te mps.

Comparer ces diverses politiques.

Exercice 3

On considère l'ensemble suivant de processus :

processusdate d'arrivéetemps de service 103
215
332
495
5125
Comparer, sur cet exemple, les diverses politiques d'ordonnancement.

Exercice 4

Un processus interactif effectue les "bursts" successifs de durées 6,

4, 6, 4, 13, 13, 13. La durée initiale

estimée d'un burst est 10. Comparer l'estimation et la réalité dans le modèle de la moyenn e pondérée exponentielle (on prendra a = 0.8 et a = 0.5).

Exercice 5

Soit deux processus p1 et p2 dans un système utilisant la politique d 'ordonnancement PDS. La table suivante donne pour chaque processus le temps a de service atteint, le temps ré el r passé dans le système et la fonction f -1 (a) ,à un instant donné : processusarf -1 (a) p122a/2 p235a/6

1) Quel est le processus qui obtient à cet instant le processeur ?

2) Après quelle période de temps les priorités des deux proces

sus seront égales ? l priorités externes l adaptation temporelle l charge du système Le temps total de service peut être estimé dans quelques systèm es. La priorité affectée est alors d'autant plus grande que le temps total de service est court : - un processus "court" devrait être terminé rapidement - traiter d'abord les travaux courts réduit le temps total d'ex

écution de tous

les processus Les priorités externes sont utilisées pour différencier les cla sses d'utilisateurs et de processus exemple : processus temps réel : hautes priorités processus interactifs : moyennes priorités processus batch : basses priorités L'adaptation temporelle prend en compte le fait que l'urgence à terminer une tâche peut varier dans le temps. exemple : accroître la priorité au fur et à mesure que le temps du processus dans le système augmente ( problème des prédictions météo : elles ne peuvent arriver après la date correspondante). n

Règle d'arbitrage

Cette règle est faite pour les conflits entre processus de même pr iorité. Plusieurs possibilités choix au hasard, choix suivant la position dans la file,

Principaux algorithmes

Examinons maintenant quelques algorithmes d'ordonnancement

FIFO ( First In/ First Out)

L'ordre est celui de l'arrivée des processus dans la file des p rocessus prêts. La fonction de priorité est P(r) = r où r est le temps réel passé dans le système. Le mode de décision est non pré-emptif; la règle d'arbitrage est le choix au hasard pour des processus qui arrivent au même moment.

LIFO ( Last In / First Out)

L'ordre est l'inverse du précédent : le dernier arrivé es t le premier servi. La fonction de priorité est P(r) = - r où r représente toujours le temps réel passé dans le systè me.Le mode de décision et la règle d'arbitrage sont comme dans FIFO.

SJF ( Shortest Job First)

On suppose que le temps total de service t est connu à l'avance ( bien adapté aux processus batch où l'utilisateur peut indiquer un temps max). La fonction de priorité est P(t) = -t. Le mode de décision est non pré-emptif. La règle d'arbitrage est la chronologie ou le choix au hasard. La difficulté est évidemment l'estimation du temps de service. Cec i peut s'opérer, par exemple, de la manière suivante, pour un processus interactif qui s'exécute comme une série de "bursts" de durée d'exécution réelle T iquotesdbs_dbs11.pdfusesText_17