ENSI -- II2 FN

Systèmes d'Exploitation & Programmation Concurrente

ORDONNANCEMENT DES ROCESSUS

1. Introduction
2. Types d’ordonnancement
3. Modèle simple d'ordonnancement
4. Politiques d’ordonnancement
Organisations des files d’attente
Ordonnancement FCFS / SJF/ priorité/RR/ SRTF/ Multi-
niveaux
5. Hiérarchie d’ordonnancement
6. Ordonnancement des threads
 Généralités

Qu’est ce que l’ordonnancement?

Commuter dès qu’un processus se bloque ou se termine

ENSI -- F. Najjar Ordonnancement des Processus 2

 Généralités (suite)

Le SE permet 2 types de décisions sur le processeur :

Ordonnancement des processus: L’ordonnanceur (scheduler) choisit

quel est le processus qui doit tourner

Problème: Dans quel ordre les processus sont servis?; par exemple, un
seul processeur et plusieurs processus.

Allocation du processeur: l’allocateur (dispatcher) lance l’exécution du

processus choisi par le scheduler

Scheduler

Politique d’ordonnancement?

Dispatcher

Mécanisme d’allocation?

ENSI -- F. Najjar Ordonnancement des Processus 3

 Introduction -- Généralités

Ordonnanceur -- Scheduler

Objectif : Sur un intervalle de temps assez grand, faire progresser tous

les processus, tout en ayant, à un instant donné, un seul processus actif

(dans le processeur).

Rôle: Prendre en charge la commutation de processus, qui règle les

transitions d’un état à un autre des différents processus.

Multi-programmation: réalisée par l’ordonnanceur au niveau le plus

bas du système, elle est activée par des interruptions d’horloge, de

disque et de terminaux.

ENSI -- F. Najjar Ordonnancement des Processus 4

 Introduction -- Objectifs de la Multiprogrammation

Maximiser le taux d’utilisation de l’unité centrale (efficacité) :

Durée(UC_active)/Durée_totale.
En pratique, on obtient des valeurs comprises entre 40% et 90% (très
mauvais - très bon)
Maximiser le débit (nombre de processus utilisateurs traités en moyenne par
unité de temps).
Minimiser le temps de traitement moyen
Moyenne des intervalles de temps séparant la soumission d’une tâche de sa
fin d’exécution.
Minimiser le temps de traitement total (temps de vie d’un processus dans le
système)
Temps(Résidence_FA_process_Prêts) + Temps(Occup_UC) +
Temps(At_FA_E/S) + Temps( Résidence_MS)
Minimiser le temps d’attente
Ces objectifs sont contradictoires! Il faut des compromis -- optimiser pour des
moyennes, valeurs min/max ou variance (prévisibilité)?

ENSI -- F. Najjar Ordonnancement des Processus 5

 Types d’ Ordonnancement des Processus

Plusieurs processus sont prêts (en RAM) à être exécutés

Le SE doit faire un choix -- algorithme d’ordonnancement :

Equité : chaque processus doit recevoir sa part du temps processeur

Efficacité : le processeur doit être utilisé à 100%

Temps de réponse: l ’utilisateur devant sa machine ne doit pas trop

attendre (mode interactif)

Temps d’exécution: une séquence d’instructions ne doit pas trop durer

(minimiser le temps d’attente en traitement par lots)

Rendement (’’throughput ’’): il faut faire le plus de choses en une unité

de temps

ENSI -- F. Najjar Ordonnancement des Processus 6

 Types d’ Ordonnancement des Processus

Les types d’ordonnancements: ils sont distingués suivant les transitions

permises dans le graphe d'état d’un processus
Transition ’’interrompue’’ interdite --Ordonnancement sans réquisition
(exp. Windows (< 95), Windows NT, Mac OS (< 10))
un processus est exécuté jusqu’à la fin : inefficace :-(!

Transition ’’interrompue’’ autorisée --Ordonnancement avec

réquisition (Exp. Windows 95, Mac OS X, UNIX)

(temps partagé)

à chaque signal d’horloge, le SE reprend la main, décide si le

processus courant a consommé son quantum de temps et alloue
éventuellement le processeur à un autre processus

Il existe de nombreux algorithmes d’ordonnancement

ENSI -- F. Najjar Ordonnancement des Processus 7

 Modèle Simple d’Ordonnancement

Représentation de l’ordonnancement des processus

File des processus prêts Terminaison

Scheduler

dispatcher
UC

File d’attente E/S

E/S Demande E/S

Tranche de temps expirée

exit
Fils s’exécute Fork un fils

Interruption Attente It

ENSI -- F. Najjar Ordonnancement des Processus 8

 4. Politique d’Ordonnancement – Organisations des
FAs
Hypothèse : Un seul processeur + plusieurs processus
Une file d’attente, soit FA, des processus prêts: Espace réservé dans la
mémoire centrale, contenant les informations relatives aux entités que gère la
FA (pointer sur les BCPi).
Principe de chaînage d’une FA : avant/ arrière/ mixte
Plusieurs processus sont mis dans une FA, et le service demandé leur est fourni
tour à tour, en fonction de critères de gestion spécifiques à la FA.
Plusieurs situations peuvent se produire

Réquisition

File d’attente des prêts

Arrivée Service
UC satisfait Sortie

Scheduler Dispatcher

Gère la FA : Arrivée des processus et Gère l’allocation du processeur,

leur placement il peut réquisitionner

ENSI -- F. Najjar Ordonnancement des Processus 9

 Algorithmes sans préemption (FIFO
FIFO, SJF, Priorité) (1)

Algorithme FIFO (First In First Out) -- Premier Arrivé Premier Servi

Un processus s'exécute jusqu'à sa terminaison, sans retrait forcé de la ressource --SCHED_FIFO
Même priorité pour les processus (aucun privilège entre les processus)
Facile à implanter, mais peu efficace (le choix n’est pas lié à l’utilisation de l’UC)
Exemple

Processus Durée estimée Date d’arrivée

P1 24 0
P2 8 1
P3 12 2
P4 3 3
Schématiser l’exécution des processus selon leur ordre d'arrivée. Pour cela, on utilise le
DIAGRAMME DE GANTT
P1 P2 P3 P4
0 24 32 44 47 Temps de vie des processus
Temps de traitement moyen = [(24 - 0) + (32 - 1) + (44 -2) + (47 -3)]/4 = 35,25
ENSI -- F. Najjar Ordonnancement des Processus 10
 Algorithmes sans préemption (FIFO, SJF
SJF, Priorité) (2)

Algorithme SJF -- Shortest Job First (STCF -- Shortest Time to Completion First) :
Algorithme du ’’Plus Court d’Abord ’’ :
Suppose la connaissance des temps d'exécution : estimation de la durée de chaque processus
en attente
Les processus sont disponibles simultanément Algorithme optimal (sans préemption)
Exécuter le processus le plus court Minimise le temps moyen d'exécution
Analogie avec la FA à une caisse de grande surface, où une règle de politesse est de laisser
passer quelqu’un qui a peu de choses si l’on a plein dans le caddie

ENSI -- F. Najjar Ordonnancement des Processus 11

 Priorité, RR, SRTF) (1)
Algorithmes avec préemption (Priorité

A chaque processus est assignée (automatiquement par le SE /externe) une priorité

Assignation statique -- priorités fixes facile à implanter
Assignation dynamique : la priorité initiale assignée à un processus peut être ajustée à d ’autres
valeurs difficile à implanter
Pb. de famine : un processus de faible priorité peut ne jamais s'exécuter si des processus
plus prioritaires se présentent constamment

Recalculer périodiquement le numéro de priorité des processus (plusieurs FA) la

priorité d’un processus décroît (croit) au cours du temps pour ne pas bloquer les autres FA
Principe : On lance le processus ayant la plus grande priorité

Algorithme d’ordonnancement à classes de priorité

ENSI -- F. Najjar Ordonnancement des Processus 12
Algorithmes avec préemption (Round Robin Priorité, SRTF) (2)
Round Robin,

ROUND ROBIN (SCHED_RR) : algorithme tourniquet, l’un des plus utilisés et des plus
fiables
Ordonnancement selon l’ordre FIFO + préemption (Equitable)
Chaque processus possède un quantum de temps pendant lequel il s’exécute
Lorsqu’un processus épuise son quantum de temps : au suivant !
S’il n’a pas fini : le processus passe en queue du tourniquet et au suivant !
Exemple : Le quantum de temps, Q, est égale à 2 unités; quel est le temps de traitement moyen?
P2 P3
(4 unités) (2 unités)

Exécution P1 Q Q P4
CPU (3 unités) (3 unités)
Q Q

Q Q
P8 P5
(2 unités) Q Q (3 unités)

P7 P6
(4 unités) (5 unités)

ENSI -- F. Najjar Ordonnancement des Processus 13

 Algorithme Tourniquet -- Round Robin (suite)

P1 P2 P3 P4 P5 P6 P7 P8 P1 P2 P4 P5 P6 P7 P6
0 2 4 6 8 10 12 14 16 17 19 20 21 23 25 26 Temps de vie
Diagramme de Gantt (Q=2 unités)

Temps de traitement moyen =

[(17-0) + (19-1) + (6-2) + (20-3) + (21-4) + (26-5) + (25-6) + (16-7)] /8 = 15,25
Problème = réglage du quantum (petit/grand; fixe/variable; est-il le même pour tous les processus ?)
Les quanta égaux rendent les différents processus égaux
Quantum trop petit provoque trop de commutations de processus
Le changement de contexte devient coûteux (perte de temps CPU)
Quantum trop grand : augmentation du temps de réponse d’une commande (même simple)
RR dégénère vers FIFO
Réglage correct : varie d’un système (resp. d’une charge) à un autre et d’un processus à un autre
Il existe d ’autres variantes de RR, telle que RR avec priorités

ENSI -- F. Najjar Ordonnancement des Processus 14

 Algorithme Tourniquet avec priorités

Le système de gestion possède n FA à différents niveaux de priorités (+

différents quanta)

- FA n-1 (Q n-1)

Réquisition

FA1 (Q1) Q 0 ≤ Q 1 ≤ Q 2 ≤ ... ≤ Q n-1

Arrivée Terminaison
FA 0 (Q 0) CPU

Priorité Scheduler Dispatcher

A son arrivée, le processus est rangé dans la FA la plus prioritaire FA0

Si un processus dans FAi épuise son quantum de temps Qi (0 ≤i ≤n-2), il sera placé dans la FAi+1
(moins prioritaire)
Une FAi (0 ≤ i ≤n-1 ) ne peut être servie que si toutes les FAj (0 ≤ j< i) sont vides
un processus qui a traversé toutes les FA sans épuiser son temps de traitement reste dans la FA la moins prioritaire.
ENSI -- F. Najjar Ordonnancement des Processus 15
 Algorithmes avec préemption (RR, Priorité, SRTF
SRTF) (3)

Algorithme SRTF (Shortest Remaining Time First) -- SJF avec réquisition

Choisir le processus dont le temps d'exécution restant est le plus court
Il y a réquisition selon le critère de temps d'exécution restant et l'arrivée d’un processus
Possibilité de morcellement d’un processus
Nécessité de sauvegarder le temps restant
Exemple : Processus Durée estimée Date d’arrivée
P1 8 0
P2 5 2
P3 5 3
P4 2 4
Diagramme de Gantt

P1 P2 P4 P2 P3 P1 P1
0 2 4 6 9 14 20
Temps de vie

Temps de traitement moyen = [(20 - 0) + (9 -2) + (14 -3) + (6-4)]/4 = 9,5

Théoriquement, + SRTF offre un minimum de temps d’attente; - difficile de prédire le futur
ENSI -- F. Najjar Ordonnancement des Processus 16
 Hiérarchie d’Ordonnancement (1)

L’ensemble des processus prêts est-il souvent en mémoire centrale?

Un processus élu, qui est sur disque, prend beaucoup plus de temps qu’un
processus en RAM pour être chargé.
Les algorithmes d’ordonnancement complexes permettent de distinguer entre 2
types différents:
Ordonnancement à court terme (short term scheduling): considère
seulement les processus prêts en mémoire centrale.
Ordonnancement à long terme (long term scheduling): consiste à utiliser un
deuxième algorithme d’ordonnancement pour gérer les ‘’swapping ’’ des
processus prêts entre le disque et la RAM

’’Swap out’’ Processus

File d’attente des Prêts Sortie

Arrivée
UC

E/S Files d’attente des E/S

ENSI -- F. Najjar Ordonnancement des Processus 17

 Hiérarchie d’Ordonnancement (2)

Ordonnancement multi-niveaux permet de satisfaire :

Favoriser les processus courts
Favoriser les processus ‘’I/O Bound’’, qui ne demandent pas trop l ’UC
Déterminer la nature de chaque processus le plutôt possible et effectuer
l’ordonnancement correspondant
Files d’attente sans liens : un processus se trouvant dans dans FAi ne peut se
trouver dans FAj (j≠i); il reste dans FAi jusqu’à ce qu’il se termine

FA n-1
(RR)
Réquisition

FA1
(FCFS/SJF) Processus Interactifs
Terminaison
CPU
+ FA 0
Priorité fixe Processus Système

ENSI -- F. Najjar Ordonnancement des Processus 18

 Hiérarchie d’Ordonnancement (3)

Files d’attente avec liens : hiérarchiser les FAs

Arrivée niveau n-1 FA n-1

(RR)

Réquisition
Arrivée niveau 1
FA1
(FCFS)

Terminaison
Arrivée niveau 0 CPU
FA 0
(FCFS)
Un processus dans FAi ne peut être sélectionné que si toutes les FAj (j<i) sont toutes vides
Permettre aux processus de se déplacer d’une FA à une autre
Hiérarchie descendante/ascendante/bidirectionnelle
Changement dynamique dans le comportement des processus
Chaque FA a son propre algorithme d’ordonnancement
Descendante FA0 est gérée avec FCFS
Ascendante Fn_1 est gérée avec FCFS
ENSI -- F. Najjar Ordonnancement des Processus 19
 Thread Scheduling

Local Scheduling – How the threads library decides which

user thread to run next within the process

Global Scheduling – How the kernel decides which kernel

thread to run next

ENSI -- F. Najjar Ordonnancement des Processus 20

 Exemples d’ordonnancement
Unix: multi-niveaux, plusieurs politiques, qui peuvent changer dans le temps

Linux – multi-niveaux avec 3 niveaux les plus importants

Realtime FIFO

Realtime round robin

Timesharing

Windows Vista – politique avec priorité à deux dimensions:

Classe des processus prioritaires

Real-time, high, above normal, normal, below normal, idle

Les priorités des threads sont relatives dela la classe des priorités.

Time-critical, highest, …, idle

ENSI -- F. Najjar Ordonnancement des Processus 21

 Exemples d’ordonnancement POSIX

ENSI -- F. Najjar Ordonnancement des Processus 22

 Annexe

Threads scheduling

ENSI -- F. Najjar Ordonnancement des Processus 23

 Threads scheduling (1/4)

Mixed

Mach:

user-level code to provide scheduling hints to the kernel

Solaris:

assign each user-level thread to a kernel-level thread

(multiple user threads can be in one kernel thread)

creation/switching at the user level

scheduling at the kernel level

ENSI -- F. Najjar Ordonnancement des Processus 24

 Threads Scheduling (2/4)

FastThread package

hierarchical, event-based scheduling

each process has a user-level thread scheduler

virtual processors are allocated to processes

the # of virtual processors depends on a process's needs
physical processors are assigned to virtual processors
virtual processors can be dynamically allocated and deallocated to a
process according to its needs.
Scheduler Activation (SA)

event/call from kernel to user-level scheduler

represents a time slice on a virtual processor (# of SA's < # of
virtual processors)
user-level scheduler can assign threads to SA's (time slices).

ENSI -- F. Najjar Ordonnancement des Processus

25
 Threads Scheduling (3/4)

Events from user-level scheduler to kernel

P idle: virtual processor is idle
P needed: new virtual processor needed
Events from kernel to user-level scheduler
Virtual processor allocated (P added):
– User-level: scheduler can choose a ready thread to run
SA blocked (in kernel):
– Kernel: sends a new SA
– User-level: a ready thread is assigned to the new SA to run
SA unblocked (in kernel):
– user-level: thread is back on the ready queue
– kernel: allocate new virtual processor to process or preempt
another SA
SA preempted (in kernel):
– user-level: puts the thread back to the ready queue

ENSI -- F. Najjar Ordonnancement des Processus 25

 Threads Scheduling (4/4) --Scheduler activations

P added
Process Process
A B SA preempted
Process SA unblocked
SA blocked
Kernel

P idle
Virtual processors Kernel
P needed

A. Assignment of virtual processors B. Events between user-level scheduler & kernel

to processes Key: P = processor; SA = scheduler activation

ENSI -- F. Najjar Ordonnancement

27 des Processus