[PDF] Ordonnancement Ordonnancement FCFS (FIFO). Ex´ecution

View - Download Ordonnancement

Previous PDF

Next PDF

Ordonnancement

Concepts de base

Crit `eres d"ordonnancement

Algorithmes d"ordonnancement

Ordonnancement de threads

Ordonnancement dans les syst

`emes multiprocesseurs

Stefan Monnier IFT-2245 1

Ordonnancement

Concepts de base

L"ordonnancement de processus permet de mieux utiliser le CPU Ex ´ecution d´ecoup´ee enCPU burstetI/O burst Pr ´eoccupation principale: distribution desCPU bursts

Ordonnancement vise

`a profiter du parall´elisme Maintenir le CPU occup´e pendant l"attente d"un p´eriph´erique Maintenir les p´eriph´eriques occup´es pendant l"attente du CPU

Stefan Monnier IFT-2245 2

Ordonnancement

Ordonnanceur du CPU

l"ordonnanceur`a court-termechoisi parmi les processusready D

´ecision d"ordonnancement se fait:

1.

Lorsqu"un processus passe de running`awaiting

2.

Lorsqu"un processus passe de running`aready

3.

Lorsqu"un processus passe de waiting`aready

4.

Lorsqu"un processus ter mine

Ordonnancementnon-pr´eemptif: sous contrˆole du processus coop´eratif: pas de conditions de course Ordonnancementpr´eemptif: hors de contrˆole du processus

Stefan Monnier IFT-2245 3

Ordonnancement

Dispatcher

Le module dedispatchtransf`ere le contrˆole au processus s´electionn´e

Changer le contenu des registres

Passer en modeutilisateur

Sauter au bon endroit dans le programme

Latencedu dispatcher: temps pour passer d"un processus`a un autre Le temps perdu dans uncontext-switchinclus des cache-miss

Cette latence doit

ˆetre minimis´ee

Impact significatif si fr´equence´elev´ee

Stefan Monnier IFT-2245 4

Ordonnancement

Crit `eres d"ordonnancement

Utilisation du CPU

`A maximiser, traditionnellement, minimiser plus r´ecemment D ´ebit: quantit´e de travail effectif par unit´e de temps `A maximiser Temps d"attente: temps qu"un processus passe dansready `A minimiser

Temps de r

´eponse: d´elai entre une requ`ete et le d´ebut de sa r´eponse `A minimiser

Stefan Monnier IFT-2245 5

Ordonnancement

Ordonnancement FCFS (FIFO)

Ex ´ecution na¨ıve dans l"ordre d"arriv´ee;non-pr´eemptif

Processus

CPU b ursttime P

124
P 23
P 33

Diagramme de GanttP

1P 2P

30 2427 30

Temps moyen d"attente:(0 + 24 + 27)=3 = 17

Stefan Monnier IFT-2245 6

Ordonnancement

Shortest-Job First (SJF)

Ex ´ecute dans l"ordre de dur´ee, du plus court au plus longP 2P 3P

10 36 30

Temps moyen d"attente:(0 + 3 + 6)=3 = 3

SJF estoptimal: donne le temps d"attente moyen minimum Bien sˆur, en g´en´eral, la dur´ee d"ex´ecution est inconnue! Le principe est quand mˆeme fr´equemment utilis´e

On peut utiliser uneestimation

Stefan Monnier IFT-2245 7

Ordonnancement

Deviner la dur

´ee d"ex´ecution

Estimer la dur

´ee d"ex´ecution sur la base du comportement pass´e

Le pass´e est un bon pr´edicteur du futur

t ndur´eeeffectivedu CPU burstn ndur´eepr´evuedu CPU burstn facteur d"amortissement n+1=tn+ (1)n

Valeur courante de:0:5

Dur ´ee exacte peu importante: ordre de grandeur (10ms vs 10s) = 1: pas de m´emoire= 0: ignore ex´ecution effective

Stefan Monnier IFT-2245 8

Ordonnancement

Shortest Remaining Time First

Comme SJF, mais pr

´eemptif

ProcessusArriveeCPU burst timeP

108
P 214
P 329
P 435 P
1P 2P 4P 1P

30 15 10 17 26

Stefan Monnier IFT-2245 9

Ordonnancement

Ordonnancement par priorit

´e

Une priorit

´e num´erique est associ´ee`a chaque processus L"ordonnanceur choisi le processus de la plus haute priorit ´e

En versionpr´eemptiveou non

SJF et SRTF correspondent

`a une priorit´e de1=burst

Utilisation d"une priorit

´e combinant plusieurs facteurs

Priorit´e indiqu´ee par l"utilisateur

1=n, pour avantager les processus courts

ˆAge, pour´eviter lesfamines

Stefan Monnier IFT-2245 10

Ordonnancement

Exemple d"ordonnancement par priorit

´e

Processus

CPU b ursttime

Pr iorit

´eP

1103
P 211
P 324
P 415
P 552

Diagramme de Gantt:P

2P 5P 1P 3P

40 16 16 18 19

Stefan Monnier IFT-2245 11

Ordonnancement

Algorithme du tourniquet (Round Robin)

Pr ´eemption de l"ex´ecution apr`es´ecoulement d"unquantumde temps habituellement, de l"ordre de 10ms-100ms

Accorde un quantum

`a chaque processus avant de recommencer Un long processus ne peut pas retarder excessivement un autre

Offre l"illusion de l"ex

´ecution simultan´ee

N processus`a la fois, mais N fois plus lentement

Choix du quantum important:

trop grand: d´eg´en`ere en FIFO trop court: cause perte de temps en context-switch

Stefan Monnier IFT-2245 12

Ordonnancement

Exemple de Round-Robin

Processus

CPU b ursttime P

124
P 23
P 33

Diagramme de Gantt, avec quantum de 4:P

1P 2P 3P 1P 1P 1P 1P

10 47 10 14 18 22 26 30

Temps d"attente:(6(!)+ 4 + 7)=3 = 5:66(d´epend du quantum) G ´en´eralement meilleurs temps de r´eponse que SJF

Stefan Monnier IFT-2245 13

Ordonnancement

Queues multi-niveaux

Plusieurs queuesready

Tˆaches de fonds, tˆaches interactives, tˆaches de syst`eme, ... Chaque queue peut avoir son propre algorithme d"ordonnancement tˆaches interactives = RR, tˆaches de fonds = FIFO

Ordonnancement entre les queues:

Par priorit´e des queues

RR, possiblement pond´er´e (80% interactif, 20% tˆaches de fonds)

Efficace en resources, mais peu ou trop flexible

Stefan Monnier IFT-2245 14

Ordonnancement

Queues multi-niveaux

`a r´etroaction

Multi-level feedback queues

Les processus peuvent changer de queue

Typiquement, de mani`ere automatique, parˆage oun

Grande cat

´egorie param´etr´ee par:

Nombre queues

Ordonnancement de chaque queue

Ordonnancement entre les queues (habituellement, priorit´e)

Crit`ere de promotion de processus

Crit`ere de d´emotion de processus

Stefan Monnier IFT-2245 15

Ordonnancement

Exemple de multi-level feedback queues

N queues

Queuei: priorit´eNi; RR avec un quantum de2i

Promotion quand le CPU burst se termine avant 50% du quantum Processus courts et interactifs augmente de priorit´e D ´emotion quand le quantum se termine avant le CPU burst

Processus longs diminuent de priorit´e

Promotion r

´eguli`ere de tous les processus

´Evite la famine: temps maximum garanti

Stefan Monnier IFT-2245 16

Ordonnancement

Ordonnancement de threads

Distinction entre threadsuser-leveletkernel-level

Si possible, ordonnancement par thread plut

ˆot que par processus

Proportion du CPU peut

ˆetre par thread ou par processus

SCS (system contention scope): comp´etition entre tous les threads PCS (process contention scope): comp´etition entre thread siblings

Plus g´en´eralement, une hi´erarchie

Stefan Monnier IFT-2245 17

Ordonnancement

Ordonnancement multi-processeurs

Ordonnancement plus complexe

Syst `emeshomog`enes Multiprocesseur sym´etrique: chaque processeur s"ordonnance Multiprocesseur asym´etrique: un processeur se charge des autres

Affinit

´e`a un processeur: pr´ef´erence pour b´en´eficier de la localit´e Affinit´ehard: un processus reste dans son processeur Affinit´esoft: un processus peut migrer occasionnellement Processeurs (et affinit´es) regroup´es hi´erarchiquement

Stefan Monnier IFT-2245 18

Ordonnancement

Equilibrage de charge

load balancing: tenter de maintenir les processeurs´egalement occup´es Migrationpush: tˆache p´eriodique de r´e´equilibrage Migrationpull: processeuridleva chercher du travail ailleurs

On peut utiliser les deux

`a la fois

La migration s"oppose

`a l"affinit´e

Exemple classique: 3 processus sur 2 CPUs

Pr´ef´erable de maintenir un processeur occasionnellementidle

Stefan Monnier IFT-2245 19

quotesdbs_dbs50.pdfusesText_50

[PDF] diagramme de mouture de blé tendre

[PDF] diagramme de mouture de blé tendre pdf

[PDF] diagramme de mouture du blé pdf

[PDF] diagramme de phase binaire exercice corrige pdf

[PDF] diagramme de prédominance terminale s

[PDF] diagramme de transformation blé tendre en farine pdf

[PDF] diagramme de venn exercices corrigés

[PDF] dialogue argumentatif sur le voyage

[PDF] dialogue en allemand exemple

[PDF] dialogue en allemand pdf

[PDF] dialogue en anglais présentation

[PDF] dialogue en français entre deux amis pdf

[PDF] dialogue entre deux amis sur le racisme

[PDF] dialogue sur le voyage en francais

[PDF] dialogue sur les vacances en français