Chapitre 2: Processus et

Ordonnancement
INTTIC
Cours Système Exploitation
Processus
 Un Processus est une activité, crée et gérée par le système d’exploitation (SE),
dont le but est d’accompagner l’exécution d’un programme.
 Cette activité possède plusieurs états, qui transite l’un vers l’autres à cause de
plusieurs événement (E/S, ressources disponible ou pas, fin programme...)
 Pour simplifié, en considérera une architecture monoprocesseur (exemple:
Intel 8086).
 Le processus dans les différent système:
 Système batch:
 1 seul processus occupe le CPU jusqu’à ce qu’il termine.
 Implémentation simple, généralement aucun conflit sur les ressources.
 Système Multiprogrammation:
 Plusieurs processus occupe, a tour de rôle, le CPU jusqu’à ce qu’ils terminent l’un
après l’autre.
 Nécessite des gestions de temps, d’états et de contexte de chaque processus, ainsi
que la gestion (partage) de ressources pour éviter tout genre de conflits et/ou
d’interblocage .
 Processus
Le modèle de processus.

 Multiprogrammation de quatre programmes

 Conceptuellement: 4 processus séquentiels indépendants
 À chaque instant, un seul processus est actif

3
Processus
Le modèle de processus.
 Processus de conception séquentiel donnant une
impression de parallélisme lors de l’exécution.
 De point de vue conceptuelle, chaque processus possède
son propre CPU (Virtuelle).
 Un compteur ordinale (virtuelle) existe pour chaque
processus. Un compteur ordinal (physique sur la machine).
Processus
Création de processus.

 Système à 1 seul application (ex: four à micro-ondes): tout

les processus nécessaire sont crées à l’allumage, et détruits à
l’extinction.

 Système à application multiple (Ordinateur): Nécessite une

méthode pour création et arrêt de processus (selon le cas)
au cours de l’exécution.
Processus
Création de processus
 Quatre (4) événements créent des processus:
1. Initialisation du system
2. Exécution d’un appel système demandé par un processus
3. Un usager demande de créer un processus
4. Initiation d’une tâche (sur un système de traitement par lots).

 Créer un processus?
 UNIX: fork –création d’un clone et execve –modifier l’image du processus
 Windows: CreateProcess
 Processus
 Démons (daemon) ou en arrière-plan, exemples: courriers électroniques, pages web…
 Premier-plan
 Les voir?
 Ctrl+alt+del sur Windows
 ps sur UNIX
 Système Multiprogrammation: basculement entre processus donnant
l’impression d’un parallélismes (pseudo parallélisme).
 Nécessite une gestion d’accès des processus au CPU (l’ordonnancement).
 Les ressources sont demandé par plusieurs processus donnant naissance à
plusieurs problèmes de partage et d’interblocage, qui doivent être résolus.
 Communication inter Processus.
 ........................................
 Chaque Fenêtre graphique est un processus, l’utilisateur en choisissant une
fenêtre il rentre en interaction avec le processus.
Fin d’un processus:
1. Arrêt normal (volontaire).

2. Arrêt pour erreur (volontaire), exemple: « gcc test.c » où

« test.c » n’existe pas
3. Arrêt pour erreur fatale (involontaire) (ex: division/0)
4. Le processus est arrêté par un autre Processus: kill ou
TerminateProcess.
Qu’ utilise le SE pour gérer les
processus:
La gestion des processus nécessite :
 Des Programmes pour « La gestion des Processus »:
1. Le Programme «Ordonnanceur» (Scheduler).
2. Le Programme dispatcher.

 Des structures de donnés: pour sauvegarder les information

concernant les processus:
1. PCB par processus (Process Control Bloc)
2. Un ensemble de file d’attente (différents états +
différentes ressources).
3. Les nœuds dans ces files d’attentes sont des PCB.
 Etats de Processus
Terminé
Nouveau
(1)
(2)
En cours (6)
Prêt d’exécution
(3)
(5) (4)
Bloqué

 En cours d’exécution (utilisant le processeur à cet instant)

 Prêt (temporairement arrêté pour laisser exécuter un autre)
 Bloqué (ne pouvant s’exécuter tant qu’un événement externe
ne se produit)
11
 Etats de Processus
Terminé
Nouveau
(1)
(2)
En cours (6)
Prêt d’exécution
(3)
(5) (4)
Bloqué
1. Lancement nouveau Processus,
2. L’ordonnanceur choisit un processus
3. L’ordonnanceur remet processus en file d’attente,
4. Le processus est bloqué (blocage interne: wait(), ou externe: demande de
ressource E/S)
5. La ressource devient disponible,
6. Processus termine son exécution
12
 Etats de Processus
nouveau terminé

e
ad
interruption

rti
mi

so
s
activer

prêt - en
prêt
suspendu exécution
suspendre
te
r dispatch de l’ordonnanceur
terminaison d’E/S ou mi
d’ ain

en S
ou d’évènement év so

em E/
t
èn n

én d’
em d’E

év nte
en attente - en /S en attente

ou tte
t

a
suspendu

activer

suspendre

Un modèle de processus à 7 états

 Etats de Processus
• État Nouveau
• Le SE crée un PCB pour processus
• Mais ne l’a pas encore admis dans l’état prêt
• N’a pas encore alloué des ressources
• La file des nouveaux travaux est souvent appelée spoule travaux
(job spooler)
• État Terminé:
• Le processus n’est plus exécutable. Le SE est encore en train de
nettoyer ses données.
 Implémentation des processus
PCB = Process Control Block
 Chaque processus utilisateur possède un PCB.
 Le PCB est crée lorsque l’utilisateur lance un
programme (qui devient un processus) et est supprimé
du système lorsque le processus est tué.
 Tous ces PCBs sont en mémoire réservée pour le SE.
 Implémentation des processus
PCB = Process Control Block
Bloc d'informations caractérisant complètement un
processus
 Etat
 Compteur d'instruction
 état des registres
 paramètres de priorité et d'ordonnancement
 paramètres de gestion de la mémoire
 informations comptables
 informations I/O (fichiers ouverts…)
Vision plus détaillée des PCB

les PCB sont regroupés dans une table de processus

Changement (commutation) de contexte
 Rôle du matériel et du logiciel dans
le traitement d’interruptions LOGICIEL
MATÉRIEL
Le code de traitement de
l’interruption est exécuté

Signal d’interruption généré

Infos
sauvegardées dans PCB

CPU termine l’instruction courante

et détecte interruption L’ordonnanceur choisit un
processus qui est prêt

Registres CPU sont

sauvegardés dans la pile des interr. Les infos relatives à ce processus
sont rétablies à partir de son PCB

CPU saute à l’adresse trouvée dans Les registres CPU sont rechargés
le vecteur d’interruption avec ces infos dispatcher

CPU reprend l’exec de ce proc

Files d’attente
 Les ressources d’un ordi sont souvent limitées, et solliciter par
différent en même temps
 Chaque ressource a sa propre file de processus en attente
 Quand il y a interruption sur une ressource (ex fin d’E/S), les files
permettent de déterminer quel processus doit être notifié
 En changeant d’état, les processus se déplacent d ’une file à l`autre
 File prêt: les processus en état prêt=ready
 Files associés à chaque unité E/S
 etc.
 PCBs sur différentes files d’attente
file prêt

Nous supposons que le premier processus dans une file est celui qui utilise la ressource: ici, proc7
exécute, proc3 utilise disque 0, etc.
 Une façon plus synthétique de
décrire la même situation
prêt  7  2
bandmag0 
bandmag1 
disq0  3  14  6
term0  5
 Les files contiennent les pointeurs sur PCB
et non les PCB eux mêmes

term. unit 0 ready

. . . PCB2 PCB3 PCB4 PCB5 PCB6 PCB7 PCB14

. . .

disk unit 0
 Au départ
 Au départ
 Au départ
 Processus dans le SE – Representation
Pour les utilisateurs (et les processus) un processus est identifié par
son Process ID (PID)
Dans le SE, les processus sont représentés par des entrées dans la
Table des Processus(Process Table (PT))
PID est un index dans l’entrés de la PT
Entré PT = Process Control Block (PCB)
PCB est une large structure de donné qui contient (ou pointe vers)
tous les informations concernant un processus
Linux – défini dans task_struct –plus de 70 champs
voir include/linux/sched.h
Windows XP – définie dans EPROCESS – a peu prêt 60 champs
 Ordonnancement

28
 Ordonnanceur & Algorithme
d’ordonnancement
1. Ordonnanceur (scheduler): partie du SE qui
sélectionne les processus.
2. Algo d’ordonnancement (scheduling algorithm)
1. Non-Préemptif: Le processus, quitte le CPU
uniquement s’il termine ou se bloque sur E/S.
2. Préemptif: Non-Préemptif ou qu’un processus plus
prioritaire se présente.

29
 Ordonnanceur
Processus

cat ls ... disk vid

Ordonnanceur
 Conceptuellement, l’ordonnanceur est au niveau le plus bas du SE
 Prend en charge les interruptions et l’ordonnancement
 Les autres processus séquentiels sont au dessus
 Ordonnancement & Ressources
 Objectif multiprogrammation =
 Utilisation optimale des ressources: CPU, périphériques..
 Bon temps de réponse pour l’utilisateur
 L`ordonnanceur décide, a travers un Algorithme, quel
processus doit occuper la ressource lorsqu’elle se libère.
 Le CPU est une ressource.
 Les périphériques sont aussi des ressources.
 Les mêmes Algorithmes peuvent donc être appliqués pour l’
ordonnancement des processus sur les périphériques d’E/S.

31
 Critères d’ordonnancement
 Système Batch
 Débit: nombre de processus exécutés par unité de temps
 Rendement utilisation processeur
 Temps de restitution / service : délai entre la soumission et
fin de tache.
 Système Interactif
 Temps de réponse : délai entre la soumission et début
d’execution .
 Temps d’attente : temps passé en état prêt
 Proportionnalité : aux attentes des utilisateurs

32
 Critères d’ordonnancement
 Système Temps-réel
 Respect des dates limites : éviter la perte de données
 Prédictibilité : stabilité des applications multimédia

 Autres Critères valable pour tout système

 Équité : répartition du CPU
 Respect de politique : imposer les choix d’ordonnancement
 Équilibre : occupation de toutes les parties du système

 =) Optimisation = min, max.

33
 Critères d’ordonnancement:
maximiser/minimiser

 Faut-il maximiser ou minimiser les critères suivants?

 Rendement CPU
 Débit = Throughput
 Temps de
 Rotation (séjour)
 Attente
 Réponse

34
Politiques d’ordonnancement
Pour
Systèmes par lots
Ordonnancement FIFO/FCFS
Exemple: Processus Temps de cycle
P1 24
P2 3
P3 3
 Si les processus arrivent au temps 0 dans l’ordre: P1 , P2 , P3
Le diagramme de Gantt est le suivant:

P1 P2 P3

0 24 27 30

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

Temps attente moyen: (0 + 24 + 27)/3 = 17
Ordonnancement FIFO/FCFS
 Débit = 3/30 = 0,1
 3 processus complétés en 30 unités de temps
 Temps de séjour moyen: (24+27+30)/3 = 27

P1 P2 P3

0 24 27 30
 Ordonnancement FIFO/FCFS
Si les mêmes processus arrivent à 0 mais dans l’ordre
PP22 , P3 , P
P31 P1

0 3 6 30

 Temps d’attente(P1 ,P2 ,P3)=(6,0,3)

 Temps d’attente moyen : (6 + 0 + 3)/3 = 3(17 avant)
 Temps de séjour moyen: (3+6+30)/3 = 13 (27 avant)
 Beaucoup mieux!
 Donc pour cette technique, les temps peuvent varier grandement par
rapport au temps d’arrivée des processus
Tenir compte du temps d’arrivé!
 Soustraire les temps d’arrivée
 Exercice: répéter les calculs si:
 P1 arrive à temps 0 et dure 24
 P2 arrive à temps 2 et dure 3
 P3 arrive à temps 5 et dure 3
 Temps d’attente(P1) = 0-0=0
 Temps d’attente(P2) = 24-2=22
 Temps d’attente(P3) = 27-5=22

P1 P2 P3

0 24 27 30
 Ordonnancement FIFO/FCFS
 Principe
 Algorithme sans réquisition (préemption).
 File d’attente FIFO pour les processus prêts
 Facile à comprendre et à programmer
 Intrinsèquement équitable pour des processus équivalents
 Inconvénients
 Grande variance des critères d’ordonnancement
 Effet d’accumulation
 =) Mauvais algorithme pour les systèmes interactif , temps-partagé et
temps réel. OK pour les systèmes de batch.
Ordonnancement SJF - Shortest Job First
 Le processus qui demande moins de CPU est sélectionner en premier
 Optimal en principe du point de vue du temps d’attente moyen
 (v. le dernier exemple)

P2 P3 P1

0 3 6 30
SJF (avec ou sans préemption )
Arrivé d’un nouveau processus:
• SJF Sans préemption: on permet au processus
courant de terminer son cycle

• SJF Avec préemption:

• Comparer le temps d’exécution du nouveau processus et le
temps restant au processus en cours d’exécution.
• Préempter si plus petit
◦ SRTF: shortest remaining-time first
SJF sans préemption
Processus Arrivée Cycle CPU
P1 0 7
P2 2 4
P3 4 1
P4 5 4
SJF (sans préemption)
P1 P3 P2 P4

0 7 8 12 16

 Temps d’attente moyen = (0+(8-2)+(7-4)+(12-5))/4

(0 + 6 + 3 + 7)/4 = 4
 Temps de séjour moyen = (7+(12-2)+(8-4)+(16-5) )/4= 8
 SJF avec préemption
Processus Arrivée Cycle
P1 0 7
P2 2 4
P3 4 1
P4 5 4
 SJF (avec préemption)

P1 P2 P3 P2 P4 P1

0 2 4 5 7 11 16
P2 arr.
P3 arr. P4 arr
• Temps moyen d`attente = (9 + 1 + 0 +2)/4 = 3
 P1 attend de 2 à 11, P2 de 4 à 5, P4 de 5 à 7

44
• Temps de rotation moyen = 16+ (7-2) + (5-4) + (11-5) = 7
 Ordonnancement SJF
 Principe
 Algorithme sans préemption
 Le prochain cycle le plus court est sélectionné
 En cas d’égalité, on revient au FCFS
 Version avec préemption : « temps restant le plus court » (SRTF)
 Avantage
 Temps moyen d’attente minimal
 Inconvénient
 Difficulté de calculer la longueur des cycles (Approximation possible par moyenne
exponentiel): τn+1 = ατn + (1−α)τn−1
 Risque d’obtention d’une « Situation de famine »

 =) Peu adapté pour l’ordonnancement à court terme. OK pour les systèmes

de batch.
Politiques d’ordonnancement
Pour
Systèmes interactifs
 Round-Robin- Tourniquet (RR)
 Chaque processus réserve une tranche de temps (p.ex. 10-100
millisecs.) pour exécution
 Tranche aussi appelée quantum
 S’il s’exécute pendant une tranche entière sans aucunes interruptions,
il est interrompu par la minuterie, l’ordonnanceur s’active puis le
CPU est donné à un autre processus
 Le processus interrompu redevient prêt (à la fin de la file)
 Méthode préemptive
 Le plus utilisé en pratique, conçu spécialement pour le temps
partagé.

47
 Exemple: RR, Quantum = 20 ms
Processus Cycle
P1 53
P2 17
P3 68
P4 24

P1 P2 P3 P4 P1 P3 P4 P1 P3 P3

0 20 37 57 77 97 117 121 134 154 162

 Observation:
 Temps de séjour et temps d’attente moyens beaucoup plus élevés que SJF
 mais aucun processus n’est favorisé

48  Temps de réponse est minimiser

 Round-Robin- Tourniquet (RR)
 Principe
 FCFS avec réquisition sur une base de quantums (20 –50ms)
 Nécessite une horloge et mécanismes d’interruption,
 Précautions
 Le quantum > temps de commutation de contexte.
 Le quantum ne doit pas être trop grand (sinon, comportement
semblable au FCFS)

 =) Réquisition pour les cycles plus longs que le quantum,

commutation passive (FCFS) pour les cycles plus courts

49
 Le temps de séjour (turnaround) varie
avec la tranche

= FIFO

Exemple qui montre que le temps de séjour moyen ne s’améliore pas nécessairement en
augmentant la tranche (sans considérer les temps de commutation contexte)
50
 Ordonnancement par Priorités

 Affectation d’une priorité au processus (un nombre entier)

 souvent les petits chiffres dénotent des hautes priorités (0 la
plus haute).

 La CPU est affecté au processus prêt, avec la plus haute

priorité.

51
 Ordonnancement par Priorités
 Principe
 Généralisation du SJF.
 Algorithme avec ou sans réquisition
 Priorités internes (consommation de ressources etc.)
 Priorités externes (fixées par l’utilisateur)
 Inconvénient
 Risque de situation de « famine »
 Solution : technique du « vieillissement » (augmentation
progressive de la priorité des processus en attente)

52
 Ordonnancement avec files multiples
 Chaque file
possède son
propre algorithm
d‘odonnancement.
 Les processus
interactive – RR,
80% temps CPU
 Processus
Arrière plan
 (batch) –
FCFS, 20%
temps CPU

Un proc peut être servi seulement si toutes les files de priorités plus hautes sont vides
53
 Ordonnancement avec files multiples
 Principe
 Découpage de la file d’attente des processus prêts en plusieurs
files (processus système, interactifs, arrière-plan etc.)
 Ordonnancement spécifique au sein de chaque file (RR, FCFS).
 Ordonnancement des files entre elles (priorités fixes, allocation
de tranches de temps etc.)
 Ordonnancement file multiples avec feedback (recyclage)
 Possibilité de déplacer les processus d’une file d’attente à
l’autre
 implémentation du vieillissement
 dégradation des priorités (ex. cycles longs)

54
 Ordonnancement par loterie
 Principe
 Distribution de tickets
 Tirage du gagnant à intervalle fixe

 Avantages
 Implémentation légère d’un mécanisme de « promesse » (les
processus importants peuvent obtenir plusieurs tickets)
 Efficace pour des processus coopératifs (transmission de tickets)

55
 Ordonnancement équitable
 Principe
 Partager le temps processeur équitablement entre les
utilisateurs.

 Exemple
 User1: A,B,C,D
 User2:E
Ordonnancement équitable =
A,E,B,E,C,E,D,E,A,E,B,E,C,E,D,E,.....

56
Politiques d’ordonnancement
Pour
Systèmes Temps-réels
Catégories d’événements temps réel
 Types d’événements
 Périodiques : distribution vidéo, chaîne industrielle etc.
 Apériodiques : monitoring hospitalier, contrôleur de bord etc.
 Cas particulier
 Systèmes « ordonnançables » : Soient N événements
périodiques de période Pi, nécessitant Ci temps CPU pour
s’exécuter. Le système est dit ordonnançable si et seulement
si :
Catégories d’ordonnanceurs temps
réel
 Types d’ordonnanceurs
 Temps réel rigide : « réservation de ressource ».
 L’ordonnanceur doit connaître exactement les échéances de chaque
processus, et les ressources nécessaires.
 Temps réel souples : fournir des priorités hautes et non dégradables,
minimiser la latence de dispatching.