Systèmes d’Exploitation I

Chapitre III : Ordonnancement des processus - CPU Scheduling

Amine DHRAIEF 1ère année ESEN, Université de la Manouba

Motivations

Lorsqu’un ordinateur est multiprogrammé, il possède fréquemment plusieurs processus/threads en concurrence pour l’obtention de temps processeur.

→ S’il n’y a qu’un seul processeur, un choix doit être fait

01/04/18 OS I 2

Définition

La partie du système d’exploitation qui effectue ce choix se nomme l’ordonnanceur (scheduler) et l’algorithme qu’il emploie s’appel algorithme d’ordonnancement (scheduling algorithm)

Outre le fait de sélectionner le bon processus à exécuter, l’ordonnancement doit également se soucier de faire un usage efficace du processeur, car le passage d’un processus à l’autre sont coûteux en termes de temps de traitement

Processus

scheduler

Challenges

Temps de changement de contexte

Temps d’exécution

Efficacité : Utiliser au mieux le processeur

01/04/18 OS I 4

Objectifs de l'ordonnanceur

###### Les objectifs d'un ordonnanceur d'un système multi-utilisateur sont entre autres :

S'assurer que chaque processus en attente d'exécution

reçoive sa part de temps processeur.

Minimiser le temps de réponse.

Utiliser le processeur à 100%.

Prendre en compte des priorités.

Être prédictible.

01/04/18 OS I 5

États de processus et ordonnancement Quand ordonnancer ?

01/04/18 OS I 6

États de processus et ordonnancement Quand ordonnancer ?

Lorsqu’un nouveau processus est créé

→ il faut se décider s’il faut exécuter d’abord le processus parent ou le processus enfant.

Lorsqu’un processus se termine

→ un autre processus doit être choisi parmi les processus prêts

Lorsqu’un processus se bloque

→ un autre processus doit être sélectionner pour être exécuter

Lorsqu’une interruption d’E/S se produit

→ il faut prendre une décision d’ordonnancement parmi les processus qui étaient bloqué en attente d’E/S.

01/04/18 OS I 7

Interruption ?

Interruption

arrêt temporaire de l’exécution

Catégorie : Matérielle vs. Logicielle

Interruption Logicielle : Trappe ou déroutement

Si le CPU détecte une erreur dans le traitement d’une instruction

(division par zéro par exemple)

Arrêt de l’exécution pour exécuter une routine particulière ISR

( Interrupt Service Routine ) par type d’erreur rencontrer (débordement de mémoire, division par zéro,...)

01/04/18 OS I 8

Interruption Matérielle IRQ : Interrupt Request

Générées par les périphériques (clavier, disque, USB,…)

Peuvent être masquées (interdites ou autorisés)

Interruption : le périphérique signale au CPU les événements par interruption

Éviter au CPU d’attendre un délai supplémentaire (boucler) pour que les

données soient émises par le périphérique (technique de polling ou questionnement)

Le CPU arrête momentanément l’exécution d’un processus pour exécuter la requête du périphérique.

Déclenche l’ordonnancement entre les processus bloqué en l’attente de l’E/S en

question

01/04/18 OS I 9

Interruption et Ordonnacement

###### On utilise les interruptions d’horloge pour commuter les tâches dans les systèmes multitâches.

###### Généralement, une interruption périodique est déclenchée par une horloge (souvent 100 ou 1 000 Hz), et l'ordonnanceur est alors mis en action.

###### 1Hz = 1 cycle par seconde

01/04/18 OS I 10

Classification des algorithmes d'ordonnancement

01/04/18 OS I 11

Algorithmes d'ordonnancement non préemptif

#### Sélectionne un processus, puis le laisse s’exécuter jusqu’à ce qu’il se bloque, ou qu’il libère volontairement le processeur

Même s’il s’exécute pendant des heures, il ne sera

pas suspendu de force

Aucune décision d’ordonnancement n’intervient

pendant les interruptions d’horloge

01/04/18 OS I 12

Algorithmes d'ordonnancement préemptif

#### Sélectionne un processus et le laisse s’exécuter pendant un délai déterminé

si le processus est toujours en cours d’exécution à

l’issue de ce délai, il est suspendu

l’ordonnancement sélectionne un autre processus à

exécuter

01/04/18 OS I 13

Ordonnanceurs non préemptifs

01/04/18 OS I 14

Ordonnanceurs non préemptifs

Dans un système à ordonnancement non préemtif ou sans réquisition, le système d'exploitation choisit le prochain processus à exécuter:

le Premier Arrivé est le Premier Servi PAPS (ou First-Come

First-Served FCFS)

ou le plus court d'abord (Shortest Job First SJF )

Il lui alloue le processeur jusqu'à ce qu'il se termine ou qu'il se bloque (en attente d'un événement).

→ Il n'y a pas de réquisition

01/04/18 OS I 15

First-Come, First-Served

Implémenter via une file d’attente FIFO → code très facile à implémenter

Par contre, c’est une stratégie qui peut engendrer des temps d’attentes moyens importants et très variables

Exemple : considérons les processus P1, P2, P3 avec les temps d’exécutions suivants. Ces processus arrivent tous au temps 0.

P1	24
P2	3
P3	OS I 3

First-Come, First-Served

Si les processus arrivent dans l’ordre P1, P2, P3, on aura le diagramme de Gantt suivant

Le temps d’attente de P1 est de 0ms, celui de P2 est de 24ms et enfin celui de P3 est 27ms

Le temps d’attente moyen est de (0 +24 +27)/3 = 17ms

01/04/18 OS I 17

First-Come, First-Served

##### Supposons que les processus arrivent dans l’odre P2, P3, P1, on aura la diagramme de Gantt suivant :

##### Le temps moyen d’attente devient (0+3+6)/3 = 3ms

01/04/18 OS I 18

Shortest Job First

#### L’ordonnanceur choisit, parmi le lot de processus à exécuter, le plus court (plus petit temps d'exécution).

#### Stratégie offre le temps moyen d’attente minimale

01/04/18 OS I 19

Shortest Job First

#### Exemple les processus P1, P2, P3 et P4 arrivent tous au temps 0 et ont les temps

ution suivant	Col2
P1	6
P2	8
P3	7
P4	3

01/04/18 OS I 20

Shortest Job First

#### Avec SJF, on aura le diagramme de Gantt suivant :

#### P1 attends 3ms, P3 9ms, P2 16ms et P4 0ms. Le temps moyen d’attente est (3+16+9+0)/4 = 7ms

01/04/18 OS I 21

Ordonnanceurs non préemptifs Métriques

#### Temps de séjour = temps de terminaison – temps d’entrée

#### Temps d’attente = temps de séjours – temps d’exécution

01/04/18 OS I 22

Ordonnanceurs non préemptifs Exercice I

Considérons cinq travaux A, B, C, D et E, dont les temps d'exécution et leurs temps d’arrivée respectifs sont les suivants:

Processus	Temps d’exécution	Temps d’arrivée
A	3	0
B	6	1
C	4	4
D	2	6
E	1	7

01/04/18 OS I 23

Ordonnanceurs non préemptifs Exercice I

Faire un schéma qui illustre l’exécution (diagramme de Gantt) et calculer le temps de séjour de chaque processus, le temps moyen de séjour, le temps d'attente et le temps moyen d'attente en utilisant :

Premier arrivé premier servi (FCFS)

Le plus court d'abord (SJF)

01/04/18 OS I 24

Ordonnanceurs non préemptifs Exercice I Correction FCFS

Au temps 0, seulement le processus A est dans le système et il s'exécute.

Au temps 1 le processus B arrive mais il doit attendre que le processus A termine son exécution car il a encore 2 unités de temps.

Ensuite B s'exécute pendant 4 unités de temps.

Au temps 4, 6, et 7 les processus C, D et E arrivent mais B a encore 2 unités de temps.

Une fois que B a terminé, C, D et E entrent au système dans l'ordre

01/04/18 OS I 25

Ordonnanceurs non préemptifs Exercice I Correction FCFS

Temps de séjour = temps de terminaison – temps

d’entrée	Col2	Col3	Col4
Processus	Temps de terminaison	Temps d’arrivée	Temps de séjour
A	3	0	3
B	9	1	8
C	13	4	9
D	15	6	9
E	16	7	9

Le temps moyen de séjour est

(3+8+9+9+9)/5=7.6

01/04/18 OS I 26

Ordonnanceurs non préemptifs Exercice I Correction FCFS

Temps d’attente = temps de séjours – temps d’exécution

Processus	Temps de séjour	Temps d’exécution	Temps d’attente
A	3	3	0
B	8	6	2
C	9	4	5
D	9	2	7
E	9	1	8

Le temps moyen d'attente est : (0+2+5+7+8)/5=4.4

01/04/18 OS I 27

Ordonnanceurs non préemptifs Exercice I Correction FCFS

#### Il y a cinq tâches exécutées dans 16 unités de temps, alors 16/5=3.2 unité de temps par processus en moyenne

01/04/18 OS I 28

Ordonnanceurs non préemptifs Exercice I Correction SJF

#### Le plus court d'abord, schéma d'exécution :

01/04/18 OS I 29

Ordonnanceurs non préemptifs Exercice I Correction SJF

Pour la stratégie SJF nous aurons la séquence d'exécution A,B,E,D,C, et le temps de séjour est : temps de terminaison

– temps d’entrée

Processus	Temps de terminaison	Temps d’arrivée	Temps de séjour
A	3	0	3
B	9	1	8
E	10	7	3
D	12	6	6
C	16	4	12

Le temps moyen de séjour est (3+8+3+6+12)/5 = 6.4

01/04/18 OS I 30

Ordonnanceurs non préemptifs Exercice I Correction SJF

Temps d’attente = temps de séjours – temps d’exécution

Processus	Temps de séjour	Temps d’exécution	Temps d’attente
A	3	3	0
B	8	6	2
E	3	1	2
D	6	2	4
C	12	4	8

Le temps moyen d'attente est (0+2+2+4+8)/5 = 3.2

01/04/18 OS I 31

Ordonnanceurs non préemptifs Exercice I Correction SJF

#### Il y a cinq tâches exécutées dans 16 unités de temps, alors 16/5=3.2 unité de temps par processus

01/04/18 OS I 32

Ordonnanceurs préemptifs

01/04/18 OS I 33

Ordonnanceurs préemptifs

ordonnanceur préemptif = avec réquisition

Pour s'assurer qu'aucun processus ne s'exécute pendant trop de temps → une horloge électronique génère périodiquement une interruption.

A chaque interruption d'horloge, le système d'exploitation reprend la main et décide :

si le processus courant doit poursuivre son exécution

ou s'il doit être suspendu pour laisser place à un autre.

01/04/18 OS I 34

Ordonnanceurs préemptifs

Si le processus courant doit suspendre son exécution au profit d'un autre :

l’OS doit d'abord sauvegarder le contexte du processus

avant de charger le contexte du processus à lancer.

C'est qu'on appelle la commutation de contexte ou le changement de contexte

Cette sauvegarde est nécessaire pour pouvoir poursuivre

ultérieurement l'exécution du processus suspendu.

01/04/18 OS I 35

Ordonnanceurs préemptifs

#### Le temps d'allocation du processeur au processus est appelé quantum.

#### La commutation entre processus doit être rapide, c'est-à-dire, exiger un temps nettement inférieur au quantum

01/04/18 OS I 36

Ordonnancement du plus petit temps de séjour Shortest Remaining Time (SRT)

SRT= la version préemptive de l'algorithme SJF.

Si un processus dont le temps d’exécution est plus court que le reste du temps d’exécution du processus en cours de traitement, alors il prendra sa place.

01/04/18 OS I 37

Shortest Remaining Time (SRT)

Processus	Temps d’arrivée	Temps d’exécution
P1	0	8
P2	1	4
P3	2	9
P4	3	5

P1 commence à t=0, il est le seul processus dans la file d’attente

P2 arrive à t=1ms

Le temps restant à P1 est de 7ms > temps demandé par P2, 4ms → P2 est exécuté et P1 retourne dans le file d’attente

Le temps moyen d’attente = [(10 -1) + (1-1) +(17-2) +(5-3)] /4 =6.5ms < 7.75ms le temps moyen d’attente de SJF

01/04/18 OS I 38

Shortest Remaining Time (SRT)

Processus	Temps d’arrivée	Temps d’exécution	Temps de séjour : Terminaison- Entrée	Temps d’attente : Séjour - Exécution
P1	0	8	17-0=17	17 -8 =9
P2	1	4	5-1=4	4 -4 =0
P3	2	9	26-2=24	24 -9 =15
P4	3	5	10-3=7	7-5=2

Le temps moyen d’attente = (9+0+15+2) /4 =6.5ms < 7.75ms le temps moyen d’attente de SJF

01/04/18 OS I 39

Ordonnancement circulaire Round Robin (RR)

L'algorithme du tourniquet, circulaire ou round robin est un algorithme ancien, simple, fiable et très utilisé.

Il mémorise dans une file du type FIFO (First In First Out) la liste des processus prêts, c'est-à-dire en attente d'exécution.

01/04/18 OS I 40

Choix du processus à exécuter dans RR

Il alloue le processeur au processus en tête de file, pendant un quantum de temps.

Si le processus se bloque ou se termine avant la fin de son quantum, le processeur est immédiatement alloué à un autre processus (celui en tête de file).

Si le processus ne se termine pas au bout de son quantum, son exécution est suspendue.

Le processeur est alloué à un autre processus (celui en tête de file).

Le processus suspendu est inséré en queue de file.

Les processus qui arrivent ou qui passent de l'état bloqué à l'état prêt sont insérés en queue

de file.

Pour éviter la famine, un nouveau processus est insérer en fin de file, pour ne pas doubler

les processus existants

01/04/18 OS I 41

Exemple de RR

P1	24
P2	3
P3	3

Quantum = 4ms

01/04/18 OS I 42

Impact de la valeur du quantum dans RR

Un quantum trop petit provoque trop de commutations de processus et abaisse l'efficacité du processeur.

Un quantum trop élevé augmente le temps de réponse des courtes commandes en mode interactif.

Un quantum entre 20 et 50 ms est souvent un compromis raisonnable

01/04/18 OS I 43

Impact de la valeur du quantum dans RR

01/04/18 OS I 44

Ordonnanceurs préemptifs Exercice II

Soient deux processus A et B prêts tels que A est arrivé en premier suivi de B, 2 unités de temps après. Les temps de processeur nécessaires pour l'exécution des processus A et B sont respectivement 15 et 4 unités de temps.

Processus	Temps d’arrivée	Temps d’exécution
A	0	15
B	2	4

Le temps de commutation est supposé nul. Calculer le temps de séjour de chaque processus A et B, le temps moyen de séjour, le temps d'attente, le temps moyen d'attente, et le nombre de changements de contexte pour:

SRT

Round robin (quantum = 10 unités de temps)

Round robin (quantum = 3 unités de temps)

01/04/18 OS I 45

Ordonnanceurs préemptifs Exercice II Correction SRT

01/04/18 OS I 46

Ordonnanceurs préemptifs Exercice II Correction RR quantum 10

01/04/18 OS I 47

Ordonnanceurs préemptifs Exercice II Correction RR quantum 3

01/04/18 OS I 48

Ordonnanceurs préemptifs Exercice III – Round Robin

Considérons cinq Processus P1, P2, P3, P4, P5, dont les temps d'exécution et leurs temps d’arrivée respectifs sont les suivants

Processus	Temps d’arrivée	Temps d’exécution
P1	0	5
P2	1	3
P3	3	6
P4	5	1
P5	6	4

Le temps de commutation est supposé nul. Dessiner le diagramme de GANTT pour l’ordonnancement Round Robin (quantum = 3 unités de temps)

01/04/18 OS I 49

Correction Exercice III

Processus	Temps d’arrivée	Temps d’exécution
P1	0	5→ 2→ 0
P2	1	3→ 0
P3	3	6→ 3→ 0
P4	5	1→0
P5	6	4→ 1→ 0

Quantum = 3

File d’attente

P1	P2	P3	P1	P4	P5	P3	P5
3	6	9	11	12	15	18	19

01/04/18 OS I 50

Ordonnanceurs préemptifs Exercice IV – Round Robin

Considérons cinq Processus A, B, C, D, e, dont les temps d'exécution et leurs temps d’arrivée respectifs sont les suivants

Processus	Temps d’arrivée	Temps d’exécution
A	0	3
B	2	6
C	4	4
D	6	5
E	8	2

Le temps de commutation est supposé nul. Dessiner le diagramme de GANTT pour l’ordonnancement Round Robin (quantum = 1 unités de temps ensuite quantum = 3)

01/04/18 OS I 51

File d’attente

A	C	C
A	B	B
B	E	D
A	D	D
B	C
C	B
B	E
D	D

Col1	Corre	ection Ex q=1
Processus	Temps d’arrivée	Temps d’exécution
A	0	3→2 → 1→0
B	2	6→5 →4 → 3 → * 2 →1 →0*
C	4	4→3 → 2 → 1 → 0
D	6	5 →4 → 3 → 2 →1 →0
E	8	2 → 1 → 0

A	A	B	A	B	C	B	D	C	B	E	D	C	B	E	D	C	B	D	D
1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20

Quantum = 1

01/04/18 OS I 52

Correction Exercice III

q=3

File d’attente

Processus	Temps d’arrivée	Temps d’exécution
A	0	3 → 0
B	2	6 → 3 → 0
C	4	4 → 1 → 0
D	6	5 → 2 → 0
E	8	2 → 0

A	Col2	Col3	B	Col5	Col6	C	Col8	Col9	D	Col11	Col12	B	Col14	Col15	E	Col17	C	D	Col20
1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20

Quantum = 3

01/04/18 OS I 53

Ordonnancement avec priorité

Certains processus sont plus importants ou urgents que d'autres.

L'ordonnanceur à priorité attribue à chaque processus une priorité. Le choix du processus à élire dépend des priorités des processus prêts.

Les processus de même priorité sont regroupés dans une file du type FIFO.

Il y a autant de files qu'il y a de niveaux de priorité.

L'ordonnanceur choisit le processus le plus prioritaire qui se trouve en tête de

file.

En général, les processus de même priorité sont ordonnancés selon

l'algorithme du tourniquet.

01/04/18 OS I 54

Attribution et évolution des priorités

Pour empêcher les processus de priorité élevée de s'exécuter indéfiniment, l'ordonnanceur diminue régulièrement la priorité du processus en cours d'exécution.

La priorité du processus en cours est comparée régulièrement à celle du processus prêt le plus prioritaire (en tête de file). Lorsqu'elle devient inférieure, la commutation a lieu.

Dans ce cas, le processus suspendu est inséré en queue de le correspondant à sa nouvelle priorité. L'attribution et l'évolution des priorités dépendent des objectifs fixés et de beaucoup de paramètres.

Ordonnancement des processus sous LINUX

01/04/18 OS I 56

États d’un processus

#### Les états peuvent être examinés à l’aide de la commande ps ou en regardant le contenu du pseudo-fichier /proc//status .

#### Ce dernier contient en effet une ligne State:... indiquant l’état du processus.

01/04/18 OS I 57

États d’un processus

01/04/18 OS I 58

États d’un processus

01/04/18 OS I 59

Fonctionnement multitâche, priorités Plusieurs R sur une machine mono-processur ?

Au niveau de la commande ps ou du pseudo-fichier /proc//status, il n’y a aucune différence entre un processus effectivement en exécution et un processus prêt.

Ils sont tous deux indiqués par la lettre R .

Cela explique pourquoi la commande ps aux présente parfois une liste contenant simultanément plusieurs processus à l’état R sur une machine mono-processeur.

01/04/18 OS I 60

Fonctionnement multitâche, priorités

##### Une application qui effectue de larges plages d’opérations de calcul sans réclamer d’entrée-sortie emploie beaucoup la seule ressource qui soit vraiment indispensable pour tous les processus : le CPU.

##### Cette application pénalisera donc les autres logiciels qui font un usage plus raisonnable du processeur.

01/04/18 OS I 61

Fonctionnement multitâche, priorités

Priorité double

Le noyau utilise, pour pallier ce problème, le principe de priorité double .

Une valeur statique de priorité est donnée à tout

processus dès son démarrage et peut partiellement être corrigée par un appel-système approprié.

L’ordonnanceur se sert de cette valeur statique pour

calculer une nouvelle valeur, nommée priorité dynamique, et qui est remise à jour à chaque fois que le processus est traité par l’ordonnanceur . Cette priorité dynamique est entièrement interne au noyau et ne peut pas être modifiée.

01/04/18 OS I 62

Fonctionnement multitâche, priorités

Priorité double

Plus un processus utilise le temps CPU qui lui est imparti, plus le noyau diminue sa priorité dynamique.

Au contraire, plus le processus rend vite la main lorsqu’on l’exécute, plus le noyau augmente sa priorité.

Avec cette politique, les tâches qui exploitent peu le processeur –

déclenchant une opération d’entrée-sortie et s’endormant aussitôt en attente du résultat – passeront beaucoup plus rapidement de l’état Prêt à l’Exécution effective que les tâches qui grignotent tous les cycles CPU qu’on leur offre, sans jamais redonner la main volontairement.

01/04/18 OS I 63

Fonctionnement multitâche, priorités

Priorité double

Il est nécessaire de pouvoir donner au noyau une indication de la priorité qu’on affecte à tel ou tel travail.

Lorsque plusieurs processus seront prêts, le noyau choisira d’abord celui dont la priorité dynamique est la plus importante.

Lors du calcul de la priorité dynamique, l’ordonnanceur utilise la

priorité statique conjointement à d’autres facteurs, comme le fait que le processus ait relâché le processeur avant l’expiration de son délai ou la disponibilité immédiate de son espace d’adressage complet .

01/04/18 OS I 64

Fonctionnement multitâche, priorités

Priorité double

Plus un processus a une priorité dynamique élevée, plus la tranche de temps qu’on lui allouera sera longue.

C’est un moyen de punir les programmes qui bouclent, en les

laissant travailler quand même, mais sans trop perturber les autres processus.

Lorsqu’un processus a consommé tous ses cycles, il ne sera réélu pour l’accès au processeur que dans le cas où aucun autre processus plus courtois n’est prêt.

01/04/18 OS I 65

Fonctionnement multitâche, priorités

nice ou courtois

Lorsqu’un processus désire influer sur sa propre priorité statique, il peut utiliser l’appel système nice(). On indique à celui-ci la « gentillesse » dont le processus appelant désire faire preuve.

La déclaration de cette fonction se trouve dans : int nice (int increment) ;

La valeur transmise est ajoutée à notre gentillesse vis-à-vis des autres processus. Cela signifie qu’un incrément positif diminue la priorité du processus, alors qu’un incrément négatif augmente sa priorité.

01/04/18 OS I 66

Fonctionnement multitâche, priorités

nice ou courtois

#### La plage de valeur utilisée en interne par l’ordonnanceur pour les priorités statiques s’étale de 0 à 40.

#### Toutefois, par convention on présente la gentillesse d’un processus sur une échelle allant de –20 (processus très égoïste) à +20, la valeur 0 étant celle par défaut.

01/04/18 OS I 67

Fonctionnement multitâche, priorités

la commande nice, renice

###### $ nice -n prio cmd : lance la commande cmd avec la priorité prio.

###### $renice -n prio -p PID : modifie la priorité du processus PID.

###### $renice -n prio -p USR : modifie la priorité de tous les processus de USR.

01/04/18 OS I 68

The END

01/04/18 OS I 69