LOG 710 Hiver2014

Ordonnancement de la CPU

Abdelouahed Gherbi

Hiver 2014

1

LOG 710 Hiver2014

Plan

• Concepts de base – Cycle CPU – Cycle E/S – Ordonnanceur de CPU – Ordonnancement préemptif (avec réquisition) – Critères d’ordonnancement

• Algorithmes d’ordonnancement – Ordonnancement du premier arrivé, premier servi (FCFS) – Ordonnancement du travail le plus court d’abord (SJF) – Ordonnancement avec priorité – Ordonnancement à tourniquet (Round-Robin) – Ordonnancement avec files multiniveaux – Ordonnancement avec files multiniveaux avec retour

2

LOG 710 Hiver2014

Introduction • Ordonnancement de la CPU (CPU scheduling)

– Est à la base des OS multiprogrammés

• La commutation (switching) de la CPU entre plusieurs processus permet de rendre l’ordinateur plus productif

• Dans ce cours – Introduction des concepts de base de l’ordonnancement de la CPU

– Présentation de quelques algorithmes d’ordonnancement

3

LOG 710 Hiver2014

Concepts de base

4

LOG 710 Hiver2014

Ordonnancement • Dans un monoprocesseur

– Un seul processus est en exécution à un instant donné – Les autres processus soit ils attendent que la CPU soit libre (processus prêts)

soit qu’Ils attendent un évènement (fin d’E/S, libération d’une ressource)

• La multiprogrammation permet d’avoir un processus en exécution en tout temps (maximiser l’utilisation de la CPU) – Un processus s’exécute jusqu’au moment où il doit attendre – Typiquement : attendre la terminaison d’une requête d’E/S – Sans la multiprogrammation : la CPU est oisive (idle) perte de temps. – Avec la multiprogrammation : ce temps est utilisé productivement – Quand un processus doit attendre : OS assigne la CPU à un autre processus

• Ce patron se répète

– à chaque fois qu’un processus doit attendre, un autre processus prend la CPU • Ceci est une fonction fondamentale de l’OS : Ordonnancement

5

LOG 710 Hiver2014

Cycle CPU – Cycle E/S • L’exécution d’un processus consiste en une alternance

– Cycle CPU

– Cycle E/S

• Les durées des cycles CPU ont été mesurés extensivement – Variation entre processus et ordis

– Une tendance : plusieurs cycle courts de CPU et quelques longs cycles CPU

6

Alternance cycle CPU-cycle E/S [1]

Distribution typique des cycles CPU [1]

LOG 710 Hiver2014

Ordonnanceur de CPU • A chaque fois qu’un processus deviens oisif (idle)

– OS doit sélectionner un processus dans la file des processus prêts pour lui assigner la CPU

• Cette sélection est effectuée par l’ordonnanceur à court terme (ordonnanceur de CPU)

7

LOG 710 Hiver2014

Quand est ce qu’on décide d’ordonnancer ?

• La décision d’ordonnancement est prise quand :

1. Un nouveau processus est admis dans la file des processus prêt

2. Un processus passe de l’état en exécution à l’état en attente

3. Un processus passe de l’état en exécution à l’état prêt

4. Un processus passe de l’état en attente à l’état prêt

5. Un processus passe à l’état terminé

• Dans les cas 2 et 5 : – pas de choix d’ordonnancement – un nouveau processus de la file prêt (s’Il y

en a) doit être sélectionné.

• Dans les cas 1, 3 et 4: – Il y a un choix

8

Diagramme de transition d’états des processus [1]

LOG 710 Hiver2014

Ordonnancement préemptif • Quand l’ordonnancement se fait seulement dans les cas 2 et

5 – Ordonnancement non préemptif ou coopératif (sans réquisition)

– Une fois la CPU est attribuée à un processus, il garde la CPU jusqu’à ce qu’il la libère en terminant ou il quand il doit attendre

• Sinon : – Ordonnancement préemptif (avec réquisition)

9

LOG 710 Hiver2014

Dispatcheur • Module qui donne le contrôle de la CPU à un processus qui a été

sélectionné par l’ordonnanceur

• La fonction du dispatcheur inclut : – La commutation de contexte – Le passage au mode utilisateur – Le branchement vers la l’emplacement appropriée dans le code du processus

sélectionné pour le démarrer

• Le dispatcheur doit être très rapide car il est invoqué dans chaque

commutation de contexte

• Le temps pris par un dispatcheur d’arrêter un processus et démarrer un autre est appelée latence de dispatch

10

LOG 710 Hiver2014

Critères d’ordonnancement • Plusieurs critères peuvent être utilisés pour comparer les algorithmes d’ordonnancement

• Utilisation de la CPU

– On désire occuper la CPU le plus possible – Conceptuellement : 0 à 100% mais pratiquement 40% - 90%

• Débit (throughput)

– Nombre de processus complétés par unité de temps – Processus long : 1 processus / heure – transaction courtes : 10 processus /sec

• Temps de rotation (turnaround time)

– Perspective d’un processus particulier : temps pris pour exécuter complétement un processus – Intervalle de temps entre la soumission de ce processus et son achèvement – La somme des périodes d’attente dans les files, d’E/S et d’exécution

• Temps d’attente

– L’algorithme d’ordonnancement n’affecte pas le temps durant lequel le processus s’exécute ou attend une E/S – Il affecte le temps durant lequel le processus attend dans la file des processus prêt – Temps d’attente : la somme des périodes passées en attente dans la file des processus prêts

• Temps de réponse

– Dans un système interactif, le temps de rotation n’est pas nécessairement le meilleur critère – Un processus peut rapidement produire des sorties et continuer à calculer d’autres résultats pendant que les

premières sorties sont données à l’utilisateur – Temps de réponse :

• temps entre la soumission d’une requête et le production de la première réponse • Temps nécessaire pour commencer à répondre et non le temps pour sortir cette réponse

11

LOG 710 Hiver2014

Algorithmes d’ordonnancement

12

LOG 710 Hiver2014

Premier arrivé premier servi (FCFS) • Le plus simple algorithme d’ordonnancement

• Le premier processus qui demande la CPU la reçoit en premier

• L’implémentation de FCFS est facilement gérée par une file FIFO

• Quand un processus entre dans la file des processus prêt, sont PCB est

chainé à la fin de la file

• Lorsque la CPU est libérée, on l’alloue au processus en tête de la file

• Le processus en cours d’exécution est alors retiré de la file

• Le code de FCFS est simple à écrire et à comprendre

• Le temps d’attente moyen avec FCFS est souvent long !!!

13

LOG 710 Hiver2014

Premier arrivé premier servi (FCFS) • On considère l’ensemble des processus suivants :

• On suppose que les processus arrivent à l’instant 0 et admis dans l’ordre : P1 , P2 , P3

• Le diagramme de Gantt pour l’ordonnancement FCFS de cet ensemble est :

• Temps d’attente pour P1 = 0; P2 = 24; P3 = 27

• Temps d’attente moyen : (0 + 24 + 27)/3 = 17

Processus Cycle CPU

P1 24

P2 3

P3 3

14

LOG 710 Hiver2014

Premier arrivé premier servi (FCFS) • Supposons que les processus arrivent dans l’ordre P2 , P3 , P1

• Le diagramme de Gantt pour l’ordonnancement FCFS est :

• Temps d’attente P1 = 6; P2 = 0; P3 = 3

• Temps d’attente moyen est: (6 + 0 + 3)/3 = 3

• On obtient donc une réduction substantielle

• Temps d’attente moyen sous FCFS n’est pas minimal et peut varier substantiellement si le temps des cycles CPU varient d’une manière importante.

• Note : FCFS est non préemptif (sans réquisition)

• Est-ce que FCFS est adéquat pour les système à temps partagé (time sharing)?

15

LOG 710 Hiver2014

Travail le plus court d’abord (SJF) • Shortest job first (SJF)

• SJF associe à chaque processus la longueur du prochain cycle CPU

• Lorsque la CPU est disponible, on l’alloue au processus ayant le plus petit prochain cycle CPU

• Si les prochains cycles CPU de deux processus sont identiques, on utilise FCFS (tie break !!)

16

LOG 710 Hiver2014

Travail le plus court d’abord (SJF) • On considère l’ensemble de processus suivant :

• Le diagramme de Gantt avec SJF est :

• Temps d’attente P1 = 3, P2 = 16; P3 = 9 et P 4 = 0

• Temps d’attente moyen est = (3 + 16 + 9 + 0) / 4 = 7

• Exercice : Par comparaison avec FCFS on obtient un temps d’attente = ?

Processus Cycle CPU

P1 6

P2 8

P3 7

P4 3

17

LOG 710 Hiver2014

Travail le plus court d’abord (SJF) • On considère l’ensemble de processus suivant :

• Le diagramme de Gantt avec SJF est :

• Temps d’attente P1 = 3, P2 = 16; P3 = 9 et P 4 = 0

• Temps d’attente moyen est = (3 + 16 + 9 + 0) / 4 = 7

• Par comparaison avec FCFS on obtient un temps d’attente = 10.25

Processus Cycle CPU

P1 6

P2 8

P3 7

P4 3

18

LOG 710 Hiver2014

Travail le plus court d’abord (SJF) • L’algorithme SJF est optimal :

– Il obtient le temps d’attente moyen minimal pour un ensemble de processus donné

– En déplaçant un processus court avant un long, on diminue le temps d’attente du processus court plus qu’on augmente le temps d’attente du processus long.

• Cependant SJF a un défi majeur ! Lequel ?

19

LOG 710 Hiver2014

Travail le plus court d’abord (SJF) • L’algorithme SJF est optimal :

– Il obtient le temps d’attente moyen minimal pour un ensemble de processus donné

– En déplaçant un processus court avant un long, on diminue le temps d’attente du processus court plus qu’on augmente le temps d’attente du processus long.

• Cependant SJF a un défi majeur ! Lequel ?

• La difficulté réelle de SJF est de connaitre à l’avance la longueur du prochain cycle CPU

• Solution : Technique de prédiction

20

LOG 710 Hiver2014

Travail le plus court d’abord (SJF) • L’algorithme SJF peut être préemptif ou non préemptif

• Le choix survient quand un nouveau processus arrive dans la file des processus prêts.

• Le prochain cycle de CPU du nouveau processus peut être plus court que ce qu’il reste à exécuter du processus en cours d’exécution.

• Un algorithme SJF préemptif interrompt le processus en cours alors qu’un algorithme SJF non préemptif le laisse compléter son cycle CPU.

• Un algorithme SJF préemptif s’appelle aussi ordonnancement au temps restant le plus court d’abord (shortest remaining time first)

21

LOG 710 Hiver2014

Travail le plus court d’abord (SJF) • On considère l’ensemble de processus suivant :

• Le diagramme de Gantt avec SJF préemptif est comme suit :

• Quel est le temps d’attente moyen des processus ?

Processus Temps d’arrivée Cycle CPU

P1 0 8

P2 1 4

P3 2 9

P4 3 5

22

LOG 710 Hiver2014

Travail le plus court d’abord (SJF) • On considère l’ensemble de processus suivant :

• Le diagramme de Gantt avec SJF préemptif est comme suit :

• Temps d’attente P1 = 10 -1, P2 = 0; P3 = 17-2 et P 4 = 5-3

• Temps d’attente moyen est = [(10-1) + (1-1) + (17-2) + (5-3)] / 4 = 6.5

• Exercice : Par comparaison avec un SJF non préemptif on obtient un temps d’attente = ?

Processus Temps d’arrivée Cycle CPU

P1 0 8

P2 1 4

P3 2 9

P4 3 5

23

LOG 710 Hiver2014

Travail le plus court d’abord (SJF) • On considère l’ensemble de processus suivant :

• Le diagramme de Gantt avec SJF préemptif est comme suit :

• Temps d’attente P1 = 10 -1, P2 = 0; P3 = 17-2 et P 4 = 5-3

• Temps d’attente moyen est = [(10-1) + (1-1) + (17-2) + (5-3)] / 4 = 6.5

• Par comparaison avec un SJF non préemptif on obtient un temps d’attente = 7.75

Processus Temps d’arrivée Cycle CPU

P1 0 8

P2 1 4

P3 2 9

P4 3 5

24

LOG 710 Hiver2014

Exercice 01

25

LOG 710 Hiver2014

Ordonnancement avec priorité • L’algorithme SJF est un cas particulier d’un algorithme général

d’ordonnancement avec priorité

• Une priorité est associée avec chaque processus

• La CPU est allouée au processus ayant la plus haute priorité

• Les processus ayant une même priorité sont ordonnancés selon le FCFS.

• Question : Quelle est la priorité dans le cas de SJF ?

26

LOG 710 Hiver2014

Ordonnancement avec priorité • On considère l’ensemble de processus suivants qui arrivent à l’instant 0

• Les nombres les plus petits représentent les priorités les plus hautes

• Le diagramme de Gantt avec un ordonnancement avec priorité est comme suit :

• Temps d’attente moyen est = 8.2

Processus Cycle CPU Priorité

P1 10 3

P2 1 1

P3 2 4

P4 1 5

P5 5 2

27

LOG 710 Hiver2014

Ordonnancement avec priorité

• L’ordonnancement avec priorité peut être préemptif ou non préemptif

• Un algorithme d’ordonnancement avec priorité préemptif interrompt le processus courant – si un processus arrive dans la file des processus prêt – Et si le nouveau processus a une priorité plus haute que celle du processus en

cours.

• Un algorithme d’ordonnancement avec priorité non préemptif

– Dépose le nouveau processus en tête de la file des processus prêt

• Un algorithme d’ordonnancement avec priorité pose un problème

majeur. Lequel ?

28

LOG 710 Hiver2014

Ordonnancement avec priorité

• L’ordonnancement avec priorité peut être préemptif ou non préemptif

• Un algorithme d’ordonnancement avec priorité préemptif interrompt le processus courant – si un processus arrive dans la file des processus prêt – Et si le nouveau processus a une priorité plus haute que celle du processus en

cours.

• Un algorithme d’ordonnancement avec priorité non préemptif

– Dépose le nouveau processus en tête de la file des processus prêt

• Un algorithme d’ordonnancement avec priorité pose un problème majeur

– Blocage infini ou famine (starvation) – Peut laisser des processus à priorité basse en attente indéfinie

• Solution ?

29

LOG 710 Hiver2014

Ordonnancement avec priorité

• L’ordonnancement avec priorité peut être préemptif ou non préemptif

• Un algorithme d’ordonnancement avec priorité préemptif interrompt le processus courant – si un processus arrive dans la file des processus prêt – Et si le nouveau processus a une priorité plus haute que celle du processus en cours.

• Un algorithme d’ordonnancement avec priorité non préemptif

– Dépose le nouveau processus en tête de la file des processus prêt

• Un algorithme d’ordonnancement avec priorité pose un problème majeur – Blocage infini ou famine (starvation) – Peut laisser des processus à priorité basse en attente indéfinie

• Solution :

– Vieillissement (aging) – Technique qui consiste à incrémenter graduellement la priorité des processus qui attendent

dans le système depuis une longue période.

30

LOG 710 Hiver2014

Ordonnancement à tourniquet (Round-Robin)

• L’algorithme d’ordonnancement à tourniquet (Round-Robin : RR) est conçu spécialement pour les systèmes à temps partagé

• Similaire à FCFS mais avec réquisition de la CPU afin de passer d’un processus à un autre

• On définit une petite unité de temps appelée quantum de temps (tranche) – Varie entre 10 et 100 millisecondes

• La file des processus prêt est gérée comme une file circulaire

• L’ordonnanceur se déplace dans la file en allouant la CPU au processus pour un intervalle

de temps maximal égale au quantum

• Implémentation de RR: – La file des processus prêt est une FIFO circulaire – Nouveau processus sont ajoutés à la fin de la file – Ordonnanceur RR prend le premier processus dans la file, initialise un timer pour générer une

interruption après un quantum de temps et lance le processus – Premier cas :

• le processus a un cycle CPU inférieure au quantum : il va libérer lui-même la CPU et RR passe au processus suivant dans la file des processus prêt

– Deuxième cas : • Le cycle CPU du processus est plus long que le quantum: le timer va générer une interruption; en traitant cette interruption,

l’OS va mette le processus en fin de la file et RR sélectionne le prochain processus

31

LOG 710 Hiver2014

• Le temps d’attente avec RR est souvent plus long

• On considère l’ensemble des processus suivants arrivant à l’instant 0 et un quantum de temps q = 4

• Le diagramme de Gantt pour l’ordonnancement RR avec q = 4 est comme suit :

• Temps d’attente moyen = 5.66

Ordonnancement à tourniquet (Round-Robin)

Processus Cycle CPU

P1 24

P2 3

P3 3

32

LOG 710 Hiver2014

Ordonnancement à tourniquet (Round-Robin)

• La performance de RR dépends beaucoup de la taille du quantum de temps

• Si on a un quantum de temps très grand : RR est similaire à FCFS

• La commutation de contexte a aussi un impact sur la performance de RR

• Exemple

• Le quantum de temps doit être plus grand que le temps nécessaire à une commutation de contexte mais pas trop grand pour ne pas devenir un FCFS

33

Impact de la taille du Quantum de temps sur le nombre de commutation de contexte [1]

LOG 710 Hiver2014

Exercice 02

34

LOG 710 Hiver2014

Ordonnancement utilisant des files multi-niveaux

• Les processus peuvent être dans différentes catégories

– Exemple: processus en avant-plan (interactifs) et processus en arrière-plan (batch processes)

– Des exigences différentes en temps de réponses

– Besoins différents en ordonnancement

• Avec un algorithme d’ordonnancement utilisant des files multi-niveaux, la file des processus prêt est partitionnée en plusieurs files d’attentes séparées

• Chaque file a son propre algorithme d’ordonnancement

– La file des processus en avant plan : – RR

– La file des processus en arrière plan – FCFS

• En plus, il y a un ordonnancement entre les files d’attentes

– Typiquement : un ordonnancement préemptif avec priorités fixes; (i.e., servir tous les processus en avant plan avant les processus en arrière plan).

– Utiliser une tranche de temps : chaque file obtient une portion du temps de la CPU; P.ex. 80% pour les processus en avant plan avec RR et 20% pour les processus en arrière plan avec FCFS

Files d’ordonnancement multi-niveaux [1]

35

LOG 710 Hiver2014

Ordonnancement utilisant des files multi-niveaux

• Les processus peuvent être dans différentes catégories

– Exemple: processus en avant-plan (interactifs) et processus en arrière-plan (batch processes)

– Des exigences différentes en temps de réponses

– Besoins différents en ordonnancement

• Avec un algorithme d’ordonnancement utilisant des files multi-niveaux, la file des processus prêt est partitionnée en plusieurs files d’attentes séparées

• Chaque file a son propre algorithme d’ordonnancement

– La file des processus en avant plan : – RR

– La file des processus en arrière plan – FCFS

• En plus, il y a un ordonnancement entre les files d’attentes

– Typiquement : un ordonnancement préemptif avec priorités fixes; (i.e., servir tous les processus en avant plan avant les processus en arrière plan).

– Utiliser une tranche de temps : chaque file obtient une portion du temps de la CPU; P.ex. 80% pour les processus en avant plan avec RR et 20% pour les processus en arrière plan avec FCFS

Files d’ordonnancement multi-niveaux [1]

36

Files d’ordonnancement multi-niveaux Figure modifée par Abdel

LOG 710 Hiver2014

Ordonnancement utilisant des files multi-niveaux avec retour

• Dans un algorithme d’ordonnancement à files multiniveaux

– Processus sont affectés d’une manière permanente à une file d’attente particulière

– Les processus ne se déplacent pas entre les files – Avantage : limiter le surcoût (overhead) d’ordonnancement – Inconvénient : pas de flexibilité

• Ordonnancement utilisant des files multi-niveaux avec retour

– Un processus peut passer d’une file à une autre

• Principe :

– Séparer les processus selon les caractéristiques de leur cycles CPU – Si un processus utilise trop le temps de CPU, il est déplacé vers une file de

priorité plus basse • Résultat : Les processus tributaire d’E/S et interactifs demeurent dans les files de plus

haute priorité – Un processus qui attend trop longtemps dans une file de priorité basse peut

être déplacé vers une file plus haute priorité • Cette forme de vieillissement permet de combattre la famine (starvation)

37

LOG 710 Hiver2014

Ordonnancement utilisant des files multi-niveaux avec retour

• Exemple : Ordonnancement utilisant trois (03) files multi-niveaux avec retour

• Ordonnanceur exécutent tous les processus dans la file 0, ensuite (quand la file 0 est vide) les processus de la file 1 et finalement la file 2

• Un processus qui arrive dans la file i va interrompre un processus de la file i+1

• Un nouveau processus prêt est initialement mis dans la file 0

• Un processus de la file 0 est donné un quantum de 8 – S’il ne termine pas il est déplacé vers la file 1.

• Quand la file 0 est vide, le processus en tête de la file 1 est donné un

quantum de 16 – S’il ne termine pas il est déplacé vers la file 2

• Les processus de la file 2 sont exécutés selon FCFS seulement quand la file 0

et 1 sont vides.

• Cet ordonnancement favorise les processus ayant un cycle CPU de 8 ou moins. Les processus entre 8 et 16 sont servis aussi rapidement mais avec moins de priorité. Les processus longs finissent par être servis en FCFS avec moins de priorité

38

Files d’ordonnancement multiniveaux avec retour [1]

LOG 710 Hiver2014

Ordonnancement utilisant des files multi-niveaux avec retour

• En général, un ordonnancement avec files multi-

niveaux avec retour est défini par les paramètres suivant : – Nombre de files

– Algorithme d’ordonnancement pour chaque file

– Méthode utilisée pour déplacer un processus vers une

file de plus haute priorité

– Méthode utilisée pour déplacer un processus vers une file de plus faible priorité

– Méthode utilisée pour déterminée la file initiale d’un processus

• Un ordonnancement avec files multi-niveaux avec

retour est le plus général mais aussi le plus complexe (il faut configurer ses paramètres)

39

Files d’ordonnancement multiniveaux avec retour [1]

LOG 710 Hiver2014

Références

[1] SILBERSCHATZ, A. et P.B. GALVIN, Operating System Concepts. 8th Edition, Addison Wesley.

40