Chapitre II

Gestion des processus

SRAIRI SONIA
 Historique des systèmes d'exploitation
L’histoire de l’informatique est très brève et pourtant, elle
a connu de grandes évolutions. L'historique des systèmes
d'exploitation est lié à l'évolution de l’informatique.
Cette évolution est séparée en 4 grandes étapes :
1. Première génération (1945-55) : les tubes à vide.
2. Deuxième génération (1955-65) : les transistors et le
traitement par lots.
3. Troisième génération (1965-80) : les circuits intégrés et
la multiprogrammation.
4. Quatrième génération (1980-aujourd’hui) : les micro-
ordinateurs

2
 Introduction aux processus
Un processus est l’entité créée par le système
d’exploitation pour l’exécution d’un programme
C’est l’entité exécuté par le processeur

Un programme est stocké sur le disque puis chargé en

mémoire afin d’être exécuté
Un seul programme peut nécessiter plusieurs processus
pour son exécution
Une fois, le processus terminé, il est supprimé par le
SE

3
 Introduction aux processus
Un processus est une suites d’instructions, il a des
données en entrée et en sortie

Le SE manipule 2 types de processus:

Ceux du système
Ceux des utilisateurs

A part l’exécution d’instructions, un processus peut

réaliser énormément de tâches :

4
 Introduction aux processus
Accéder à une ressource de manière exclusive (les
périphériques par exemple)
Partager des ressources avec d’autres processus (tels
que les fichiers)
Créer d’autres processus
Se synchroniser avec s’autres processus afin de
collaborer
Echanger des messages avec des processus

5
 Introduction aux processus
Le SE structure ses fonctionnalités en matière de
gestion de processus de la manière suivante:

Création, suppression et interruption du processus

Ordonnancement des processus afin de décider d’un

ordre d’exécution équitable entres les utilisateurs tout en
privilégiant les processus du système

6
 Introduction aux processus
Synchronisation entre les processus ainsi que la
communication

Gestion des conflits d’accès aux ressources partagées

Protection des processus d’un utilisateur contre les

actions d’un autre utilisateur

7
 Description d’un processus
Etats d’un processus

Un processus peut passer par plusieurs états avant de

finir son exécution :
 En exécution : processus en cours d’exécution au niveau du
processeur
 Prêt : s’exécuter dés qu’il sera sélectionné par le SE
 En attente : ou bloqué, il attend des données ou la libération
d’une ressource afin de poursuivre son exécution. Pendant ce
temps le processeur est attribué à u autre processus
 Terminé : processus a terminé son exécution

8
 Description d’un processus
Etats d’un processus

En exécution
(3) (4)

(2)
Prêt Terminé
(1)

(5) (6)
En attente

Transition 652 : a lieu quand

sitôt quel’événement
le le
processus aattendu
processus terminépar
n’a plus le
lede processus
temps
raison
imparti
d’être nepar
peutle se
bloqué;SEréaliser. Il est
pour son
Transition 1 : a lieu quand le processus ne peut plus poursuivre son exécution
donc inutile4unde
exécution:
par exemple,
Transition
Transition ::lesfaire patienter
processus
données
indique d’avantage
nedeviennent
que s’exécute
le processus ce
finiprocessus,
disponibles.
pasa forcément
son autant
jusqu’à
exécution la le
finterminer
car le SE : Un cas
a d’autres
 il a 3besoin signale
d’uneque le SE
ressource a sélectionné
non disponibleun processus
par exemplepour l’exécuter
d’interblocage
processus
Le processus
a exécuter.
passe à l’état
Ou si prêt
un processus plus urgent doit prendre la main.
9
 Contexte d’un processus
Pour pouvoir gérer un processus, un SE doit disposer
d’un ensemble d’information enregistrés dans des
tables pour assurer une gestion cohérentes des
processus.
Dans ces tables, on décrit les caractéristiques des
processus tels que :

Un identificateur de processus

Un état qui peut prendre plusieurs valeurs en fonction de
la progression du processus

10
 Contexte d’un processus
Un compteur ordinal permettant d’identifier la prochaine tâche
à exécuter
Des registres sauvegardant des données relatives aux processus
(ex. résultat calculés par le processus)
Des informations relatives l’ordonnancement du processus
Des informations en rapport avec la gestion de mémoire
Des informations sur la sécurité
Des informations sur les fichiers manipulés

Ces informations sont généralement stockées dans une

structure appelé bloc de contrôle du processus.
11
 Contexte d’un processus
Quand le processus commute d’un process à un autre,
le SE sauvegarde les informations relatives au process
en cour d’exécution et charge celle du nouveau

Ces informations constituent les contextes des

processus

12
 Contexte d’un processus
La commutation de contexte invoque au moins trois
étapes.
Par exemple, en présumant que l'on veut commuter
l'utilisation du processeur par le processus P1 vers le
processus P2:
Sauvegarder le contexte du processus P1 en mémoire
(usuellement sur la pile de P1).
Retrouver le contexte de P2 en mémoire (usuellement
sur la pile de P2).
Restaurer le contexte de P2 dans le processeur, la
dernière étape de la restauration consistant à reprendre
l'exécution de P2 à son point de dernière exécution.
13
Ordonnancement du processus
 Introduction
Ordinateurs personnels de + en + multitâches.
Entreprise : Plusieurs utilisateurs partagent un même
ordinateur.

Les nouvelles technologies permettent d'exécuter une

multitude de processus sur un même ordinateur
monoprocesseur.

Processeur ne peut exécuter qu'un programme à la fois.

15
 Introduction
Si plusieurs processus sont prêts, le système d'exploitation doit gérer
l'allocation du processeur aux différents processus à exécuter.
Attribuer le temps processeur à tous les processus équitablement et
judicieusement.
Le procédé de sélection du processus à exécuter par le processeur
s'appelle : Ordonnancement (Scheduling).
(décider de l’ordre d’exécution des processus)
Il existe un certain nombre d’algorithmes d’ordonnancement suivant
les ordinateurs et les applications concernées.
Nous nous intéresserons essentiellement aux algorithmes des
systèmes à traitement par lots, puis ceux des systèmes interactifs.
Les algorithmes des systèmes temps réel ne feront pas l'objet de ce
cours.

16
 Introduction
L'objectif étant de :

minimiser le temps moyen de traitement (et par

conséquent le temps moyen d'attente) des processus
ET
maximiser le taux d'utilisation de l'unité centrale de
traitement (C.P.U) ou throughput.

17
 Introduction
Taux d’utilisation: le rapport entre la durée où l’unité centrale
est active et la durée totale
Le débit: le nombre de processus utilisateur traités par unité de
temps
Le temps de traitement moyen: la moyenne des intervalles de
temps séparant la soumission d’un processus de sa fin
d’exécution
Temps d’attente moyen: la moyenne des intervalles de temps
séparant la soumission d’un processus de sa mise en exécution
Temps de réponse: c’est le maximum des durées séparant la
soumission d’un processus de son accomplissement

18
 Introduction
À chaque instant, l’ordonnanceur sélectionne, de la file
des processus prêts, celui qui sera exécuté.

 Deux types d’algorithmes sont distingués:

Les algorithmes sans réquisition (non préemptifs) :

le système d'exploitation alloue le processeur au
processus 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.

19
 Introduction
Les algorithmes avec réquisition (préemptifs) :
pour s'assurer qu'aucun processus ne s'exécute pendant trop de
temps, les ordinateurs ont une horloge électronique qui 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.
S'il décide de suspendre son exécution au profit d'un autre, il
doit d'abord sauvegarder l'état des registres du processeur avant
de charger dans les registres les données du processus à lancer.
C'est qu'on appelle la commutation de contexte ou le
changement de contexte..

20
 Systèmes à traitement par lots
Il n'y a pas d'utilisateur en attente.

On utilise des algorithmes à la fois préemptifs et non

préemptifs qui accordent de longs délais aux
processus.

On diminue le nombre de changements de processus et

on optimise ainsi les performances.

21
 Systèmes de traitements par lots
Objectifs.

3 objectifs principaux sont visés :

La capacité de traitement : c'est le nombre de tâches
effectuées en un temps déterminé.
Les délais de rotation : c'est la durée moyenne
d'exécution d'une tâche en entier.
L'utilisation du processeur : le processeur doit être
utilisé le maximum possible.

22
 Systèmes interactifs
Un utilisateur interagit avec le système.

L'utilisation d'un algorithme préemptif devient alors

obligatoire :

il faut permettre l'exécution de programmes pas

forcément interactifs et empêcher un processus de
monopoliser le temps processeur.
(i.e. consommer à lui seul tout le temps processeur).

23
 Systèmes temps réel
Sur ces systèmes, la contrainte de temps est importante
: les tâches doivent pouvoir s'exécuter dans un délai
garanti, elles ne peuvent pas se permettre d'avoir du
retard.

Ainsi, les processus ne peuvent s'exécuter pendant de

longues périodes et peuvent, par conséquent, être
rapidement bloqués.

24
 Objectifs de l'ordonnancement

1. L'équité

Attribuer à chaque processus un temps processeur

équitable : des processus de même priorité devraient
obtenir des services comparables.

Des processus de moindre importance peuvent avoir

moins d'accès au temps processeur.

25
 Objectifs de l'ordonnancement

2. Le respect de la politique

Il faut que la politique d'ordonnancement définie soit

bien appliquée quels que soient les critères qu'elle
utilise : priorités des processus, temps d'exécution,
délais, …

26
 Objectifs de l'ordonnancement

3. L'exploitation maximale du système

L'objectif est d'exploiter au maximum toutes les

composantes du système, faire en sorte qu'il soit plus
efficace et qu'un maximum de processus soit exécuté.
Pour cela, il faut multiplexer (intelligemment) les
processus d'entrée / sortie et les traitements.

27
 Les interruptions

28
 Fonctionnement d’une
interruption
L’interruption est provoquée par un signal généré sur
occurrence d’un événement qui peut être interne (lié au
processus) ou externe et indépendant.
Lorsqu’une interruption est générée, le processus en
cours d’exécution est interrompu.
Il quitte le processeur et un gestionnaire d’interruption
est chargé dans les registres du processeur et s’exécute
pour traiter l’interruption.
Une fois l’interruption traitée, le système charge un
autre processus à partir de la file d’attente et l’execute.

29
 Fonctionnement d’une
interruption
Cas de figure où un processus peut être interrompu :
Interruptions externes au processus : panne, intervention
de l’utilisateur (frappe au clavier)
Interruptions internes au processus qui proviennent de
lui et qui peuvent être de 2 types :
 Déroutements qui sont des interruptions causées par des situations
exceptionnelles généralement des erreurs : division par zéro,
débordement de la mémoire, exécution d’une instructions non
autorisées ….
 Appels systèmes : quand une instruction effectue un appel
système

30
 Fonctionnement d’une
interruption
On distingue alors deux sortes d’interruptions :
Logicielles : générées par le processus en l’appelant par
son numéro  interruption interne
 Les numéros d’interruptions sont standardisés

Matérielles : générées par les périphériques donc

externes au processus pour indiquer qu’une requête doit
être satisfaite
 Parviennent aux processus par l’intermédiaire du contrôleur
d’interruptions (IRQ interrupt request)

31
 Algorithmes d’ordonnancement
Algorithmes non préemptifs

32
 Ordonnancement dans l'ordre d'arrivée
(FIFO ou FCFS)
Principe :

Le premier arrivé est le premier servi

La sélection porte sur le processus qui se trouve en tête
de la file.

Il n’y a pas d’effort à faire de la part de

l’ordonnanceur, il suffit d’insérer le processus
nouvellement crée à la fin de la file (insertion en
queue)

33
 Ordonnancement dans l'ordre d'arrivée
(FIFO ou FCFS)
L'avantage de cet algorithme est qu'il est facile à
implanter
Néanmoins, il n'est pas optimisé (problème du poids
lourd).
Dans le suite, on note:
 i la durée d'exécution de la tâche n° i,
 ti sa date d’entrée dans la file des processus prêts
 l’intervalle de temps négligeable devant l’unité de
temps choisie.
Ti désigne la tâche n° i.

34
 Ordonnancement dans l'ordre d'arrivée
(FIFO ou FCFS)

35
 Ordonnancement dans l'ordre d'arrivée
(FIFO ou FCFS)
Calculons le temps moyen de traitement des trois
tâches: tmoy=((30-0)+(35-  )+(37-2  ))/3=102/3- 
34 unités.
  étant assez petit devant l’unité de temps choisie.
Si on commence l’ordonnancement à la date 2, on
aura la chose suivante:

Calculons le temps moyen de traitement des trois tâches : tmoy=((2+2e-2e)

+(7+2e-e)+(37+2e-0))/3 = 46/3+e » 15.33 unités.
36
 Ordonnancement dans l'ordre d'arrivée
(FIFO ou FCFS)
Cette politique présente un avantage considérable:

Elle ne consomme pas de temps processeur

Cette politique est retenue du fait de sa simplicité et de

sa faible consommation en temps processeur

37
 Ordonnancement selon le plus court
temps d'exécution S.J.F.

Principe du S.J.F (Shortest Job First).

Dans cet algorithme, le choix sera basé sur la tâche
présente dans la file des processus prêts qui possède le
plus court temps d'exécution indépendamment de sa
date d'arrivée dans la file.

Cette politique compare les processus sur la base de

leur durée d’exécution et exécute le plus court

38
 Ordonnancement selon le plus court
temps d'exécution S.J.F.

39
 Ordonnancement selon le plus court
temps d'exécution S.J.F.

Le temps moyen de traitement produit par cet

algorithme est: tmoy=((9-4)+(14-2)+(24-0)+(39-3))/4
= 77/4 = 19.25 unités.

Dans l'exemple précédent, nous avons supposé que

toutes les tâches sont présentes au moment où
commence l'ordonnancement.

40
 Ordonnancement selon le plus court
temps d'exécution S.J.F.
Avec cet algorithme, on peut prouver que S.J.F
optimise le temps moyen de traitement pour l'ensemble
des algorithmes sans réquisition.

Le problème se pose lorsqu'un certain nombre de

tâches entre dans la file des processus prêts au cours de
l'ordonnancement.

41
42
 Exercice d’application
On considère l’ensemble de processus suivant :

43
44
 Algorithmes d’ordonnancement
Algorithmes préemptifs

45
 L'ordonnancement sur les systèmes
interactifs
Objectifs

L'application possible aux systèmes en temps partagé et aux

serveurs : ce type d'ordonnancement doit convenir également
aux serveurs qui ont une charge d'exécution assez lourde.

La réactivité : l'utilisateur doit pouvoir obtenir les résultats

qu'il souhaite dans un délai devant être le plus court possible.

La proportionnalité : le temps de la réalisation de la tâche

doit coller avec l'attente de l'utilisateur. Si l'utilisateur pense que
l'exécution de la tâche va être courte, il faut qu'elle le soit.

46
 L'ordonnancement sur les systèmes
interactifs
Pour certains types d'applications, comme le temps
partagé ou le temps réel, l'ordonnancement sans
réquisition pose beaucoup de problèmes.

En effet, supposons qu'une tâche effectue des calculs à

haute précision sans faire d'E/S, cette tâche va occuper
la C.P.U pendant une bonne période de temps.

47
 L'ordonnancement sur les systèmes
interactifs
Ceci est tout à fait incompatible avec les exigences
d'équité entre les utilisateurs d'un système temps
partagé d'une part et incompatible également avec les
exigences de temps de réponse garanti d'un système
temps réel.

La solution consiste, donc, à mettre en place des

algorithmes permettant d'interrompre une tâche ayant
une durée d'exécution assez longue (même si cette
tâche n'a pas terminé son exécution).

48
 Algorithme du tourniquet ou R.R
(Round Robin)
Principe :
Le premier processus de la file est exécuté durant une
période précise et non en entier .
Une fois sa tranche de temps écoulée, il est interrompu et
mis à la fin de la file.
L’ordonnancement retire le processus suivant et l’exécute
lui aussi durant la même période.
Le tourniquet est une technique des systèmes à temps
partagé puisque chaque processus s’exécute pendant la
même durée à chaque fois.
La tranche de temps est appelée Quantum

49
 Algorithme du tourniquet ou R.R
(Round Robin)
Si cette tâche se termine avant l'expiration du quantum alors
l'ordonnanceur sélectionne la tâche suivante de la liste, remet
à zéro l'horloge et lance l'exécution de la tâche choisie.

Sinon, l'interruption générée par l'horloge redonne le contrôle

à l'ordonnanceur qui fait sauvegarder le contexte de la tâche
interrompue en mettant à jour quelques données et range la
tâche en fin de la liste.

La tâche en tête de la liste est sélectionnée pour être

exécutée.

50
 Algorithme du tourniquet ou R.R
(Round Robin)

51
 Algorithme du tourniquet ou R.R
(Round Robin)
Conclusion.

Un faible quantum de temps fait augmenter la

fréquence de commutation de contexte et fait diminuer
le temps de réponse.

Un quantum de temps assez grand fait augmenter le

temps de réponse mais fait diminuer la fréquence de
commutation de contextes.

52
 Algorithme selon le plus court temps
d'exécution restant (S.R.T.F)
Principe.
Cet algorithme est une généralisation (avec préemption)
de l'algorithme SJF. Pour chaque tâche, le système
maintient sa durée d'exécution restante:  'i.

Au début 'i =  i. l'algorithme sélectionne, toujours, la

tâche ayant la plus petite valeur de  'i (le choix est
arbitraire si deux tâches ont la même valeur de  'i).

À l'expiration du quantum, l'ordonnanceur retranche de  'i

la valeur du quantum q.

53
 Algorithme selon le plus court temps
d'exécution restant (S.R.T.F)

54
 Exercice d’application
On considère l’ensemble de processus
suivant :

55
56
 Ordonnancement par priorités
Ce type d'algorithme est utile sur les machines
multiutilisateurs, partagées et serveurs.

Le principe est de mettre en place un système de priorités

entre les processus.

Chaque processus possède un niveau de priorité qui lui est

propre.

Les processus s'exécutent alors dans l'ordre de leurs

priorités.
57
 Ordonnancement par priorités
Dans certains cas, et pour des raisons d'efficacité, cette équité
entre les utilisateurs doit être réexaminée.

L'objectif étant d'améliorer les performances globales du système.

Certaines tâches système ne doivent pas être devancées par des

tâches utilisateurs.

Parfois, certaines tâches doivent absolument fournir leurs

résultats avant une certaine date; lorsque cette date s'approche, le
système doit exécuter ces tâches avant toutes les autres qui
attendent.

58
 Ordonnancement par priorités
La solution consiste à affecter, pour chaque tâche, un numéro de
priorité.

Ce numéro peut être affecté une fois pour toutes (numéro Statique
ou dynamique) ou il peut évoluer en fonction du temps.

La première solution pose le problème de la famine (les processus

ayant un faible numéro de priorité risquent de ne jamais s'exécuter).

La deuxième méthode exige que le système d'exploitation recalcule

régulièrement la priorité des tâches non exécutées (ce calcul peut se
faire à l'expiration de chaque quantum).

59
 Ordonnancement par priorités
L'ordonnanceur choisit le processus ayant le numéro de
priorité le plus élevé (le processus le plus prioritaire).

Le problème de la famine peut être résolu en augmentant

périodiquement d'une unité la priorité des tâches se
trouvant dans la file des processus prêts.

Une tâche qui avait un faible numéro de priorité au

départ pourrait avoir, dans quelques temps, un numéro de
priorité qui lui permettrait d'être élue par l'ordonnanceur.

60
 Ordonnancement par priorités
L'affectation des priorités aux processus peut se faire
de façon manuelle (par les utilisateurs autorisés) ou de
façon automatique.

En pratique, les processus sont regroupés en classes de

priorités. Les processus ayant la même priorité se
retrouvent donc dans le même groupe de processus.

La queue qui contient les n classes existantes est alors

gérée par un algorithme de type tourniquet

61
 Ordonnancement par priorités
 Les processus A, B et C vont être exécutés en premier. Leur
ordre d'exécution dépendra de leurs priorités exactes les uns par
rapports aux autres.
 Une fois que la catégorie de priorité 3 sera vide, les processus de
la catégorie de priorité 2 pourront être exécutés.
 Il faut par contre penser à revoir les priorités car sinon les
catégories de priorité inférieures subiront une privation de
ressources (famine ou starvation)

62
 Ordonnancement garanti
Principe :

Sur les systèmes multiutilisateurs, chaque utilisateur

reçoit 1/n du temps processeur (où n est le nombre
d'utilisateurs).

Sur les systèmes mono-utilisateur, chaque processus

reçoit 1/n du temps processeur (où n est le nombre de
processus).

63
 Ordonnancement par tirage au
sort
Le principe est de donner à chacun des processus un
ticket pour l'allocation du processeur.

A chaque changement de processus, un tirage au sort

détermine le processus ayant droit au processeur.

Si l'on souhaite instaurer un système de priorités sur

les processus, il suffit alors de distribuer plus de billets
à tel ou tel processus.

64