Chapitre 2 Pdef-1
Chapitre 2 Pdef-1
Chapitre 2 Pdef-1
Introduction
La conception d’un système d’exploitation est intimement liée à la notion de processus. Un processus
représente une abstraction d’un programme en cours d’exécution. L’exécution d’un processus
suppose l’utilisation de ressources machines. Ces dernières étant limitées, l’intention d’y accéder à
plusieurs crée la concurrence. Au cours de ce chapitre, nous allons présenter :
• les interruptions
• l’interblocage (deadlock).
Mots-clés
Ressource : elle désigne toute entité dont a besoin un processus pour s’exécuter
Thread : Les threads sont des entités planifiées pour leur exécution par le processeur. Les threads
autorisent les exécutions multiples dans le même environnement de processus avec une marge
d’indépendance les uns par rapport aux autres.
Programme : C’est une suite ordonnée d’instructions élémentaires en vue d’accomplir une tâche
donnée.
Concurrence : Le fait que deux ou plusieurs processus concourent à l’accès à une même ressource.
Ordonnancement : L’Ordonnancement est le fait d’agencer les processus par ordre de priorité.
Interblocage :C’est un état qui se produit lorsque deux processus concurrentes s’attendent
mutuellement (l’un détenant la ressource que l’autre a besoin).
Un appel système (ou appel superviseur) ou appel noyau est un appel d’une des fonctions du noyau
du système d’exploitation (implémenté au niveau d’une des couches)
1
Tous les ordinateurs modernes sont capables de faire plusieurs tâches simultanément (exécuter un
programme utilisateur par exemple et afficher du texte ainsi qu’effectuer des lectures sur disque,
etc.). Dans un système multiprogrammé, le processeur bascule entre programme pour les servir en
raison de petit laps de temps (au tour des dizaines ou centaines de millisecondes) ce qui fait que le
processeur puisse intervenir pour plusieurs programmes à raison d’une seconde simulant ainsi le
parallélisme. Pour le vrai parallélisme on a des systèmes multiprocesseurs se partageant la même
mémoire physique. Le modèle conceptuel des processus séquentiels permettant de gérer le
parallélisme ainsi que certaines de ses conséquences seront abordés dans cette section.
Dans le cas de systèmes à temps partagé, tous les processus progressent dans le temps, mais un seul
s’exécute à la fois. Lorsque le processeur passe d’un processus à un autre la vitesse de traitement de
processus n’est pas uniforme, ni même reproductible si le même processus s’exécutait une autre fois.
Mais Quelle est la différence entre un processus et un programme ?
2
L’analogie ci-dessous peut aider à mieux les différencier. Prenons un informaticien en train de
confectionner un gâteau d’anniversaire de sa petite amie. Il dispose de:
• la recette du gâteau;
Dans cette métaphore, la recette représente le programme, (algorithme exprimé dans la notation
appropriée), l’informaticien représente le processeur (l’unité centrale) et les ingrédients sont des
données d’entrée. Le processus est l’activité qui consiste à confectionner le gâteau : lecture de la
recette, mélange des ingrédients, cuisson.
Supposons que notre informaticien se mette à hurler car piqué d’une guêpe. Son cerveau enregistre
le point où il s’est arrêté dans la préparation du gâteau (l’état dans lequel le processus en cours est
enregistré). Il commence à suivre les instructions de premiers secours. De ce fait, le processeur
bascule du processus (confection gâteau) vers un autre processus de priorité supérieure (administrer
antidote). Chaque processus découle d’un programme différent (recette et brochure sur les premiers
soins). Une fois le problème de piqure résolu, l’informaticien retourne au point où il avait laissé la
préparation du gâteau.
En résumé un processus est une activité. Il inclut un programme, une entrée, une sortie et un état.
Un processeur peut être partagé par plusieurs processus à l’aide d’un algorithme d’ordonnancement
intervenant pour déterminer à quel moment arrêter de travailler sur un processus pour en servir un
autre.
Les SE ont besoin de savoir que tous les processus nécessaires existent bel et bien. Le SE doit
permettre l’exécution concurrentielle de processus, et a besoin d’une méthode pour créer, et arrêter
les processus au cours de leur activité.
Autrement dit, un programme est une entité passive, , tandis qu’un processus est une entité
active .
Initialisation du système
Lors de l’amorçage du SE, plusieurs processus sont créés. Certains sont des processus de premiers
plans (processus qui interagissent avec l’utilisateur et accomplissent des tâches pour eux), d’autres
sont des processus d’arrière-plan, non associés à une utilisation particulière de l’ordinateur. Ex: les
processus d’arrière-plan conçu pour accepter les courriers électroniques entrant, ceux conçus pour
accepter les requêtes entrantes de pages web hébergées sur l’ordinateur; etc.
Exécution d’un appel système de création de processus par un processus en cours d’exécution
Un processus en exécution peut émettre des appels systèmes pour créer un ou plusieurs nouveaux
processus. Cela est particulièrement utile lorsque la tâche à accomplir peut être divisée en plusieurs
processus qui interagissent entre eux tout en étant indépendants.
Un nouveau processus peut également être créé à la demande d’un utilisateur. Cela passe par la
saisie d’une commande ou dans le mode graphique le clic sur une icône. Ces deux cas de figures
lancent un nouveau processus qui exécute le programme concerné.
3
initiation d’un travail en traitement par lots
Ce cas de figure concerne les gros mainframes. Les utilisateurs peuvent soumettre des
tâches de traitement par lots au système. Lorsque le SE constate qu’il dispose des ressources
nécessaires à l’exécution d’un job supplémentaire, il crée un nouveau processus et exécute le job
suivant de la file d’attente.
Une fois qu’un processus a été créé, il commence à s’exécuter quelle que soit sa tâche et il finira à
s’arrêter pour diverses raisons:
• Arrêt pour erreur (demande d’exécution d’un programme qui n’existe pas);
Les processus interactifs sont démarrés par l’utilisateur connecté au système. Ils sont initialisés et
contrôlés via une session terminale. Ces processus peuvent s’exécuter en avant plan du terminal qui
a lancé le programme. Dans ce cas aucune autre application ne peut être lancée aussi longtemps que
le processus est en train de s’exécuter en avant plan.
Lorsque ces processus s’exécutent en arrière-plan, de nouvelles commandes peuvent être acceptées
par le terminal pendant l’exécution du programme. Lors de l’exécution des programmes en arrière-
plan, le système n’interdit pas l’utilisateur à faire autre chose sur le terminal utilisé pour lancer le
programme. Le job control du noyau du SE offre une gestion aisée de plusieurs processus. Ce
mécanisme fait passer les processus de l’avant plan à l’arrière-plan. En utilisant ce système, des
programmes peuvent également être lancés immédiatement en arrière-plan.
Les processus automatiques ou processus par lot sont des processus non connectés au terminal. Ce
sont plutôt de tâches mises dans une file d’attente pour être exécutées. Cette file d’attente est gérée
selon le mode du premier entré- premier sorti (First in, First out : FIFO). De telles tâches sont
exécutées selon les critères suivants:
• Au moment où le système est suffisamment moins occupé pour accepter d’autres travaux (jobs):
exécutées en utilisant la commande par lot (batch command). Par défaut les tâches sont mises dans
une file dans laquelle elles vont attendre l’exécution jusqu’au moment où le système de chargement
est en-dessous de 0.8. Dans les environnements plus larges, le traitement par lots peut être privilégié
lorsque de grandes quantités de données doivent être traitées ou lorsque des tâches gourmandes en
ressources sont en attente alors que le système est suffisamment chargé. Le traitement par lots est
aussi utilisé dans l’optimisation des performances du système.
4
Les daemons sont des processus serveurs exécutés continuellement. La plus part de temps, ils sont
initialisés au démarrage du système et attendent en arrière-plan jusqu’à ce qu’une demande de leur
service soit faite. Un exemple est le daemon, xinetd, démarré dans presque toutes les procédures de
démarrage. Après le démarrage du système, ce daemon réseau attend qu’un programme client, le
client ftp par exemple, ait besoin de se connecter.
Rappelons qu’un processus est une instance d’un programme en exécution mais pointant le fait
qu’un programme n’est pas à lui-même un processus, c’est une entité passive. Un processus est une
entité active (dynamique) dont on peut étudier l’état au cours du temps. Un processus peut-être
dans trois états différents : élu, prêt, bloqué.
• Un processus est dit élu s’il est en cours d’exécution sur le processeur. Dans le cas d’une machine
multiprocesseurs plusieurs processus peuvent être élus en même temps. Notons cependant que le
nombre de processus élu doit être égal au nombre de processeurs. Lorsque le quantum de temps
attribué au processus élu est épuisé, l’ordonnanceur est appelé de façon asynchrone par interruption
et élit un autre processus parmi les processus prêt. Le processus qui était en cours d’exécution passe
de l’état élu à l’état prêt.
• Un processus est dit prêt s’il est suspendu en faveur d’un autre. Pour un processus prêt, il ne lui
manque que la source processeur pour s’exécuter.
• Lorsqu’un processus en exécution attend un événement externe (décompte d’horloge, attente des
données, etc.), il s’en dort et passe dans l’état bloqué. L’ordonnanceur appelé de façon explicite par
ledit processus, élit un autre processus parmi les processus prêts. Lorsque l’événement externe
attendu se produit le système d’exploitation se charge de son traitement, puisque le processus se
trouve dans un état bloqué. Pour ce faire, le SE interrompt temporairement le processus en
exécution pour traiter les données reçues et faire passer le processus bloqué à l’état prêt.
5
I-4 Gestion des threads
Dans les SE traditionnels, chaque processus possède un espace d’adressage et un thread de contrôle
unique. Il arrive cependant qu’il soit souhaitable de disposer de plusieurs threads de contrôle dans le
même espace d’adressage, ceux-ci s’exécutant quasiment parallèle comme s’il s’agissait de processus
distincts. Cet état de fait sera abordé dans cette partie.
Rappelons que le modèle de processus est fondé sur deux concepts: le regroupement de ressources
et l’exécution. Il est parfois nécessaire de les séparer et c’est là qu’intervient les threads.
Un processus est un espace d’adressage contenant un programme et des données mais aussi
d’autres ressources (fichiers ouverts, les processus enfants, les alertes en attente, les handlers de
signal, les informations de décompte, etc.). En rassemblant ces ressources sous forme de processus,
on facilite leur gestion.
Sous un autre angle, les processus peuvent être vus en considérant leur thread d’exécution (chemin
d’exécution) que l’on se contente d’appeler thread.
Le thread inclut:
Bien qu’un thread s’exécute dans un processus, ce sont deux concepts distincts qui peuvent être
traités séparément. Les processus servent à regrouper les ressources et les threads sont les entités
planifiées pour leur exécution par le processeur.
Les threads autorisent les exécutions multiples dans le même environnement de processus avec une
marge d’indépendance les uns par rapport aux autres. Cela est comparable au fait que plusieurs
processus s’exécutent en parallèle sur un ordinateur.
Dans le premier cas, les threads partagent un espace d’adressage, les fichiers ouverts et les autres
ressources.
Dans le second cas, les processus partagent la même mémoire physique, les disques, les imprimantes
et les autres ressources.
Etant donné que les threads ont certaines propriétés des processus, on les qualifie de processus léger.
Le terme multithreading est également employé pour désigner la situation dans laquelle plusieurs
threads sont présents dans un processus.
6
fig 3 Processus avec un espace d’adressage et un thread de contrôle unique
Comme le montre la figure ci-dessus il s’agit de trois processus traditionnels, chacun possédant son
propre espace d’adressage et un thread de contrôle unique. Ci-dessous, nous présentons un cas de
figure où on a un processus unique avec trois threads de contrôle.
Bien que dans les deux cas on est en présence de trois threads, les deux situations sont différentes.
Dans le premier cas, chaque thread fonctionne dans un espace d’adressage différent, tandis que dans
le second cas les trois threads se partagent le même espace d’adressage (multithreading).Dans ce
dernier cas, le processeur bascule rapidement entre les threads donnant une illusion d’une exécution
en parallèle de threads chacun sur son propre processus. Etant donné que ces threads partage le
même espace d’adressage, ils partagent également les mêmes variables globales (en lecture/écriture)
et aucune protection n’existe entre les threads d’un même processus. Les threads exploitent
également le même jeu de fichiers ouverts, de processus enfant ; d’alertes et de signaux, etc.
Généralement, chaque thread appelle des procédures différentes et donc un historique d’exécution
différent. C’est pour cela que chaque thread a besoin de sa propre pile. Celle-ci contient un frame
pour chaque procédure invoquée mais qui n’a encore rien retourné. Chaque frame contient, les
variables locales de la procédure et l’adresse de retour à employer une fois l’appel de procédure
exécuté. Le schéma ci-dessous présente un processus ayant trois threads.
7
I-4-2 L’utilisation de thread
Dans de nombreuses applications plusieurs activités ont lieu simultanément. En décomposant une
application en plusieurs threads séquentiels, qui vont s’exécuter presque en parallèle, le modèle de
programmation devient plus simple (processus).
Avec les threads, un élément nouveau apparaît: “la capacité pour les entités parallèles à partager un
espace d’adressage et toutes ses données”.
De plus, étant donné qu’aucune ressource n’est associée aux threads, ils deviennent plus faciles à
créer et à détruire que les processus. Les threads peuvent également améliorer le fonctionnement
d’une application.
Notons enfin que les threads sont utiles sur les systèmes multiprocesseurs, sur lesquels un véritable
parallélisme est possible.
Pour pallier les effets d’interruption, les systèmes d’exploitation offrent un modèle conceptuel de
processus séquentiels s’exécutant en parallèle. Les peuvent être créés et arrêter dynamiquement.
Chaque processus possède son propre espace d’adressage. Dans certaines applications, il est
intéressant de disposer de plusieurs threads de contrôle au sein d’un même processus. Les threads
d’un processus sont ordonnancés indépendamment les uns des autres et chacun possède sa propre
pile mais partagent tous un espace d’adressage commun.
3. A la figure 2, trois états de processus apparaissent. En théorie avec trois états on pourrait avoir six
transitions (deux en sortie de chaque état). Cependant on ne voit que quatre transitions commentez
cet état de fait.
4. Supposons que vous devriez concevoir une architecture informatique avancée qui effectuerait la
commutation entre processus au niveau matériel au lieu d’employer les interruptions. De quelle
information le processeur aurait-il besoin. Décrire comment cela pourrait fonctionner.
8
II- Communication et synchronisation interprocessus
Il arrive que les processus aient besoin de communiquer entre eux par exemple dans pipeline du
shell, lorsque la sortie d’un processus doit être passée à un autre processus, etc. Il est donc
préférable que cette communication se fasse de manière structurée. Au cours de cette activité nous
allons aborder quelques-uns des problèmes liés à la communication interprocessus.
• Comment éviter que deux processus ou plus ne produisent pas de conflits lorsqu’ils s’engagent
dans des activités critiques (tentative de récupération du dernier Mo de mémoire par deux processus?
• Comment faire le séquençage en présence de dépendances (un processus B qui travaille sur des
données produites par A, doit attendre que A ait terminé pour pouvoir commencer)?
Les processus concurrents s’exécutant dans le système d’exploitation peuvent être des processus
coopératifs ou indépendants.
♦ Un processus est indépendant s’il n’affecte pas les autres processus ou ne peut pas être affecté
par eux. Un processus qui ne partagent pas de données avec d’autres processus est indépendant
♦ Un processus est coopératifs ’il peut affecter les autres processus en cours d’exécution ou être
affecté par eux ,Un processus qui partage des données avec d’autres processus est un processus
coopératif
♦ Les données partagées par les processus coopératifs peuvent se trouver en mémoire principale ou
en mémoire secondaire dans un fichier
les messages,
les tubes(pipe) ,
les signaux,
les fichiers
Pour résoudre le cas des problèmes d’accès concurrents (voir exemple ci-dessus), il faut éviter que
plus d’un processus accèdent (en lecture/écriture) à une donnée partagée en même temps. Cela
consiste à mettre en place un processus d’exclusion mutuelle à la ressource partagée aussi appelée
section critique.
9
Quatre conditions sont à remplir pour résoudre ce problème:
1. deux processus ne doivent pas se trouver parallèlement dans leurs sections critiques;
2. il ne faut pas faire de suppositions sur la vitesse ou le nombre de processeurs mis en œuvre;
3. Aucun processus s’exécutant en dehors de la section critique ne doit bloquer d’autres processus;
4. aucun processus ne doit attendre indéfiniment pour entrer dans sa section critique.
Il existe plusieurs façons de mettre en œuvre l’exclusion mutuelle. Ci-dessous nous allons détailler
quelques-unes.
Le moyen le plus simple d’éviter les accès concurrents est de masquer les interruptions avant
d’entrer dans la section critique et de les restaurer à la sortie de celle-ci. Cela permettra d’éviter la
suspension du processus en section critique au profit d’un autre processus, puisque l’inhibition des
interruptions empêche l’ordonnanceur de s’exécuter. Les principaux problèmes en rapport avec le
masquage d’interruption sont les suivants:
Malgré ces inconvénients, cette technique est souvent utilisée par le système d’exploitation pour
manipuler de façon sur ses structures internes. Notons que cette technique reste inefficace pour les
structures à multiprocesseurs, puisque les processus s’exécutant peuvent toujours entrer en section
critique.
Rappelons que pour le masquage des interruptions, si un processus entre en section critique, le reste
des processus sont bloqué et cela même si la section critique ne concerne qu’un seul processus. Il
serait mieux alors de définir autant de sections critiques indépendantes que nécessaire. Pour ce faire,
on déclare une variable par section critique pour jouer le rôle de verrou. La variable sera mise à 1 par
le processus entrant en section critique et remise à 0 par le même processus à la sortie de la section
critique. Tout processus qui veut entrer dans la section critique va tester le contenu de la variable
verrou et n’entrer que s’il est égal à 0 (section critique libre). Le processus continuera à tester le
contenu de cette variable aussi longtemps qu’il est égal à 1. Cela est résumé dans le tableau ci-
dessous.
10
Cette solution présente le même inconvénient majeur que la précédente. En effet si un processus lit
le verrou et qu’il le trouve à 0, puis avant de le positionner à 1, un autre processus planifié s’exécute
et le fait à sa place. Au moment où le premier processus s’exécute de nouveau, il va mettre encore le
verrou à 1 et entre à son tour dans la section critique.
Le concept de sémaphore permet une solution élégante à la plupart des problèmes d’exclusion. Ce
concept nécessite la mise en œuvre d’une variable, le sémaphore, et de deux opérations atomiques
associées P et V. Soit SM la variable, elle caractérise les ressources et permet de les gérer. Lorsqu’on
désire effectuer une exclusion mutuelle entre tous les processus par exemple, il n’y a virtuellement
qu’une seule ressource et on donnera à SM la valeur initiale de 1.
• Sinon ce processus sera mis dans une file d’attente jusqu’à la libération d’une ressource.
P(SM) correspond donc à une prise de ressource et V(SM) à une libération de ressource. Dans la
littérature, on trouve parfois d’autres terminologies, respectivement, wait(SM) et signal(SM) ou
get(SM) et release(SM).
Les mutex sont une version simplifiée des sémaphores. Un mutex est une variable qui peut prendre
deux états : déverrouillé ou verrouillé. Par conséquent un seul bit est nécessaire pour le représenter
même si dans la pratique en utilise un entier prenant la valeur 0 quand c’est déverrouillé et une
autre valeur sinon. Deux procédures (mutex_lock et mutex_unlock) interviennent sur les mutex.
Lorsqu’un processus (thread) a besoin d’accéder à une ressource, il invoque la procédure mutex_lock.
Si le mutex est déverrouillé alors l’appel réussit et le processus (thread) est libre d’entrer dans la
section critique.
Par contre, si le mutex est verrouillé, alors le thread appelant est bloqué, jusqu’à ce que le processus
en section critique appelle la procédure mutex_unlock. Si plusieurs threads sont bloqués sur un
mutex l’un d’eux est choisi aléatoirement pour prendre possession du verrou.
Les processus peuvent communiquer entre eux à l’aide de primitif de communication interprocessus,
comme les sémaphores, les moniteurs et les messages. Ces primitives permettent d’empêcher que
deux processus se trouvent dans la même section critique. Un processus peut être dans un état prêt,
en train de s’exécuter ou bloqué. Il peut changer d’état de lui-même ou lorsque un autre primitif
exécute l’un des messages de communication interprocessus. Grâce à ces primitifs, la
communication interprocessus est possible et différentes situations de chaos peuvent être évitées.
11
3. Discuter du problème d’accès concurrents et la manière de le résoudre.
Une interruption est un signal déclenché par un événement interne à la machine ou externe,
provoquant l'arrêt d'un programme en cours d'exécution à la fin de l'opération courante, au profit
d'un programme plus prioritaire appelé programme d'interruption.
Ensuite, le programme interrompu reprend son exécution à l'endroit où il avait été interrompu. Le
système d'interruption est le dispositif incorporé au séquenceur qui détecte les signaux
d'interruption. Ces signaux arrivent de façon asynchrone, à n'importe quel moment, mais ils ne sont
pris en compte qu'à la fin de l'opération en cours.
12
- contenu du mot d'état (registre de drapeaux) rassemblant les indicateurs
( tout cela forme le contexte sauvegardé)
2- Chargement du contexte du programme d'interruption(contexte actif) et passage en
mode système (ou superviseur)
3-Exécution du programme d'interruption
4-Retour au programme interrompu en restaurant le contexte (commande Assembleur
IRET) et en repassant en mode utilisateur.
On distingue donc :
instruction à l'intérieur d'un programme (overflow, erreur d'adressage, code opération inexistant,
(software)
Règle :Une interruption de priorité j est plus prioritaire qu'une interruption de niveau i si j > i.
13
L'intérêt de ce système est la solution de problèmes tels que :
interruption précédente.
On peut utiliser un contrôleur d'interruptions pour regrouper les fils d'interruptions, gérer les
priorités entre les interruptions et donner les éléments de calcul d'adresse au processeur.
Certaines interruptions présentent tellement d’importance qu’il ne doit pas être possible
d'interrompre leur traitement. On masquera alors les autres interruptions pour empêcher leur prise
en compte. Certaines interruptions sont non-masquables : on les prend obligatoirement en compte.
Une interruption masquée n'est pas ignorée : elle est prise en compte dès qu'elle est démasquée.
Au contraire, une interruption peut-être désarmée : elle sera ignorée. Par défaut, les interruptions
sont évidemment armées.
IV -1 Ordonnancement préemptif
C’est la sélection d’un processus qui s’exécute pendant un délai déterminé.Si le processus
est toujours en cours d’exécution après ces délais, il est suspendu et un autre processus est
choisi. L’ordonnancement préemptif nécessite une interruption à la fin du délai afin de
donner le contrôle du processeur à l’ordonnanceur.
Si l’ordonnancement est préemptif, la transition de l’état élu vers l’état prêt est autorisée:
un processus quitte le processeur s’il a terminés on exécution, s’il se bloque ou si le
processeur est réquisitionné
IV -2 Ordonnancement non-préemptif
14
Ici, on la sélection d’un processus qui s’exécute jusqu’à ce qu’il se bloque ou qu’il libère
IV -4 Critères d’ordonnancement
L’objectif d’un algorithme d’ordonnancement consiste à identifier le processus qui
conduira à la meilleure performance possible du système. Certes, il s’agit là d’une
évaluation subjective dans laquelle entrent en compte différents critères à l’importance
relative variable. La politique d’ordonnancement détermine l’importance de chaque critère.
Un certain nombre d’algorithmes ont fait leur preuve dans la mise en œuvre d’une politique
d’ordonnancement.
La liste qui suit passe en revue des critères d’ordonnancement fréquemment utilisés.
Utilisation de l’UC : Pourcentage de temps pendant lequel l’UC exécute un processus.
L’importance de ce critère varie généralement en fonction du degré de partage du système.
Utilisation répartie : Pourcentage du temps pendant lequel est utilisé l’ensemble des
ressources (outre l’UC, mémoire, périphérique d’E/S…)
Débit :Nombre de processus pouvant être exécutés par le système sur une période de temps
donnée.
Temps de rotation :durée moyenne qu’il faut pour qu’un processus s’exécute. Le temps de
rotation d’un processus comprend tout le temps que celui-ci passe dans le système. Il est
inversement proportionnel au débit.
Temps d’attente : durée moyenne qu’un processus passe à attendre. Mesurer la
performance par le temps de rotation présente un inconvénient : Le temps de production du
15
processus accroît le temps de rotation ; Le temps d’attente représente donc une mesure
plus précise de la performance.
Temps de réponse : Temps moyen qu’il faut au système pour commencer à répondre aux
entrées de l’utilisateur.
Equité : degré auquel tous les processus reçoivent une chance égale de s’exécuter.
Priorités :attribue un traitement préférentiel aux processus dont le niveau de priorité est
supérieur.
16
Critique de la méthode :
La méthode FCFS tend à pénaliser les travaux courts: L’algorithme du FCFS n’effectue pas
de réquisition. C’est à dire qu’une fois que le processeur a été alloué à un processus, celui-ci
le garder jusqu’à ce qu’il le libère, soit en terminant, soit après avoir demandé une E/S.
L’algorithme FCFS est particulièrement incommode pour les systèmes à temps partagé, où il
est important que l’utilisateur obtienne le processeur à des intervalles réguliers. Il
peut paraître désastreux de permettre qu’un processus garde le processeur pendant une
période étendue.
V-2 Exécution du job le plus court en premier (Shortest Job First: STF)
Ici, les processus les plus courants sont exécutés en premier. Pas de notion de priorité, c’est un
algorithme non-préemptif qui suppose que les délais d’exécution sont connus d’avance. Le principe
consiste à choisir le processus dans le prochain cycle d’horloge et le plus petit.
Si plusieurs processus ont la même durée, une politique FIFO sera alors utilisée pour les
départager.
Remarque : Cet algorithme demande une connaissance à priori de la longueur du prochain cycle
d’horloge du CPU. Cet algorithme existe en version avec ou sans préemption.
Critique de la méthode :
Il a été prouvé que l’algorithme SJF est optimal dans le temps dans le sens qu’il obtient le
temps d’attente le plus court pour un ensemble de processus donné. Toutefois, cet
17
algorithme est difficile à implémenter pour une raison simple : Comment peut-on connaître
le temps d’exécution d’un processus à l’avance ?.
Exemple: On dispose de 5 processus ayant des priorités différentes, comme le montre ce tableau :
18
Critique de la méthode :
Une situation de blocage peut survenir si les processus de basse priorité attendent
indéfiniment le processeur, alors que des processus de haute priorité continuent à affluer. Pour
éviter une telle situation, on peut utiliser la technique dite du vieillissement. Elle consiste à
incrémenter graduellement la priorité des processus attendant dans le système pendant longtemps.
Par exemple, nous pourrions incrémenter de 1 la priorité d’un processus en attente toutes les 15
minutes. En fin de compte,même un processus ayant une priorité initiale égale à 0 aurait la plus
haute priorité dans le système et serait exécuté.
V-4 L’algorithme du temps restant le plus court (SRT : Shortest Remaining Time)
L’algorithme du temps restant le plus court, est la version préemptive de l’algorithme SJF. Chaque
fois qu’un nouveau processus est introduit dans la file des processus à ordonnancer, l’Ordonnanceur
compare la valeur estimée du temps de traitement restant à celle du processus en cours
d’ordonnancement. Si le temps de traitement du nouveau processus est inférieur, le processus en
cours d’ordonnancement est préempte. Tout comme l’algorithme SJF, l’algorithme SRT favorise les
travaux courts : les travaux longs en revanche peuvent être victimes de famine.
La commutation de processus (overhead) dure un temps non nul pour la mise à jour des tables,
la sauvegarde des registres. Un quantum trop petit provoque trop de commutations de
19
processus et abaisse l'efficacité du processeur. Un quantum trop grand augmente le temps de
réponse en mode interactif. Dans la pratique le quantum s’étale entre 10 et 100ms.
Chacun des utilisateurs aurait l’impression de disposer de son propre processeur . Cependant le
quantum doit être choisi de sorte à ne pas surcharger le système par de fréquentes
commutations de contexte.
Exemple: On dispose d’un processus P dont le temps d’exécution est de 10 ms. Calculons le nombre
de commutations de contexte nécessaires pour un quantum égal respectivement
à : 12, 6 et 1.
20
Temps d’attente=Temps de rotation – Durée d’exécution
21
Les ordinateurs disposent de nombreuses ressources (mémoire principale, disques, fichiers,
périphériques, etc.) mais elles ne peuvent qu’à un seul processus à la fois. L’attribution de ces
ressources à un processus revient au SE. Pour de nombreuses applications, les processus n’ont pas
besoin d’un accès à une seule ressource mais doivent pouvoir accéder à plusieurs.
Supposons que les processus P1 et P2 désirent enregistrer chacun un document numérisé sur CD.
Admettons que le processus P1 demande en premier lieu le scanner et que le processus P2 demande
l’accès au graveur CD. Ces deux premières demandent sont honorées. Supposons maintenant que P1
sollicite le graveur et que la demande est refusée jusqu’à ce que P2 libère la ressource. Au lieu de
libérer la ressource supposons que P2 sollicite à son tour le scanner. A ce stade, les deux processus
sont bloqués et vont le rester indéfiniment. C’est ce que l’on appelle l’interblocage ou deadlock en
anglais.Dans des situations complexes, les interblocages peuvent concerner plusieurs utilisateurs et
plusieurs périphériques à la fois.
Notons que les interblocages ne concernent que les requêtes des périphériques d’E/S. Dans un
système de gestion de base de données par exemple, un programme peut verrouiller plusieurs
enregistrement qu’il utilise afin d’éviter qu’ils entrent en concurrence. Si un processus P1 verrouille
l’enregistrement E1 et qu’un processus P2 verrouille l’enregistrement E2 et que l’un ou les deux
tente(nt) de verrouiller un enregistrement déjà verrouillé par un autre, on est dans une situation
d’interblocage. Les interblocages peuvent donc se produire tant sur les ressources matérielles que
sur les ressources logicielles
Dans cette partie , nous allons examiner les situations d’interblocage, comment elles se présentent
et comment les éviter. Même si nous sommes dans un contexte de SE, notons que les interblocages
peuvent se produire dans des systèmes de base de données et dans d’autres contexte de traitement
de données. Ce qui fait que le contenu développé s’applique à un large éventail de système
multiprocesseurs.
• La demande de la ressource: Si l’on ne peut pas satisfaire la demande celle-ci sera mise dans une
table d’attente des ressources ;
Par ressource, nous faisons référence à tout objet pouvant être alloué à un processus. Il peut s’agir
d’un périphérique physique, d’une information (enregistrement verrouillé dans une base de données)
bref tout ce qui peut être utilisé par un processus.
• réutilisables (existent après leur utilisation) : exemple les ressources physiques (imprimante,
graveur, etc.) ou logiques (fichiers, mutex, verrous, etc.) ;
• d’usage partagé : c’est la ressource qui peut être utilisée par plusieurs processus en même temps ?
Ce genre de ressources n’affecte pas les interblocages.
22
• préemptible ou non préemptible :La différence principale entre ressources préemptibles et non
préemptibles est que les premières peuvent être retirées sans risque au processus qui les détient,
tandis que les deuxièmes ne peuvent être retirées sans provoquer des problèmes. Comme exemples
de ressources preémptibles nous avons le processeur (où le changement de contexte correspond à
l’expropriation et l’état du processeur est copié à la Table de Contrôle de Processus (BCP)) et la
mémoire virtuelle (le remplacement est une expropriation et le contenu de la page doit être copié au
swap). Les imprimantes et les scanners sont des exemples de ressources non preémptibles.
Pour étudier le problème des interblocages, nous allons considérer uniquement les ressources non
préemptibles.
De ce qui précède, nous constatons qu’un ensemble de processus est en interblocage si chaque
processus attend la libération d’une ressource qui est allouée à un autre processus de l’ensemble.
Comme tous les processus sont en attente, aucun ne pourra s’exécuter et donc libérer les ressources
demandées par les autres. Par conséquent ces processus attendront indéfiniment.
• L’exclusion mutuelle : A un instant précis, une ressource est allouée à un seul processus ou est
disponible.
• La détention et l’attente : Les processus qui détiennent des ressources peuvent en demander de
nouvelles.
• Pas de préemption (réquisition) :Les ressources allouées à un processus sont libérées uniquement
par le processus.
• L’attente circulaire :Il existe une chaîne d’au moins deux processus chacun attendant une
ressource détenue par un autre processus de la chaîne.
• Les ressources qui sont représentées par des rectangles. Chaque rectangle contient autant de
points qu’il y a d’exemplaires de la ressource représentée.
• Un arc orienté d’une ressource vers un processus signifie que la ressource est allouée au processus.
23
• Un arc orienté d’un processus vers une ressource signifie que le processus est bloqué en attente
de la ressource.
Ce graphe indique pour chaque processus les ressources qu’il détient ainsi que celles qu’il demande.
Exemple :
Soient trois processus A, B et C qui utilisent trois ressources R, S et T comme illustré ci-dessous:
Si ces trois processus sont exécutés de façon séquentielle : A suivi de B suivi C, il n’y pas
d’interblocage. Par contre, supposons que l’exécution des processus est gérée par un
ordonnanceur du type circulaire. Si les instructions sont exécutées dans l’ordre ci-dessous :
1. A demande R
2. B demande S
3. C demande T
4. A demande S
5. B demande T
6. C demande R
24
Figure : Situation d’interblocage de trois processus
Un graphe réduit peut être utilisé pour déterminer s’il existe ou non un interblocage. Pour la
réduction d’un graphe d’allocation des ressources, les flèches associées à chaque processus et à
chaque ressource doivent être vérifiées.
• Si une ressource possède seulement des flèches qui sortent (il n’y a pas des requêtes), on les
efface.
• Si un processus possède seulement des flèches qui pointent vers lui, on les efface.
• Si une ressource a des flèches qui sortent, mais pour chaque flèche de requête il y a une ressource
disponible dans le bloc de ressources où la flèche pointe, il faut les effacer.
De ce qui précède, nous constatons que les situations d’interblocage peuvent se produire dans un
système. Face à cette situation, que faut-il faire ?
La première solution et c’est la plus simple consiste à appliquer la politique de l’autruche. C’est-à-dire,
ignorer complètement le problème et faire semblant qu’il n’existe pas. Cette stratégie est adoptée
par la plus part des SE courants car le prix à payer pour les éviter est élevé.
Une autre solution consiste à détecter et reprendre les interblocages. C’est-à-dire qu’on les laisse se
produire et on essaie d’y remédier à postériori.Pour détecter les interblocages, il construit
dynamiquement le graphe d’allocation des ressources du système qui indique les attributions et les
demandes de ressources. Dans le cas des ressources à exemplaire unique, il existe un interblocage si
le graphe contient au moins un cycle. Dans le cas des ressources à exemplaires multiples, il existe un
interblocage si le graphe contient au moins un cycle terminal (aucun arc ne permet de le quitter).
• A chaque modification du graphe suite à une demande d’une ressource (coûteuse en termes de
temps processeur).
25
• Périodiquement ou lorsque l’utilisation du processeur est inférieure à un certain seuil (la détection
peut être tardive).
Dans ce cas, lorsqu’un processus demande une ressource, le système doit déterminer si l’attribution
de la ressource est sûre. Si c’est le cas, il lui attribue la ressource. Sinon, la ressource n’est pas
accordée. Un état est sûr si tous les processus peuvent terminer leur exécution (il existe une
séquence d’allocations de ressources qui permet à tous les processus de se terminer).Un état est non
sûr si on ne peut garantir que les processus pourraient terminer leurs exécutions. Mais comment
déterminer si un état est sûr ou non sûr ? Dijkstra a proposé en 1965 un algorithme
d’ordonnancement, appelé l’Algorithme du banquier qui permet de répondre à cette question .
Pour prévenir les interblocages, on doit éliminer une des quatre conditions nécessaires à leur
apparition.
• Pour éviter l’exclusion mutuelle, il est parfois possible de sérialiser les requêtes portant sur une
ressource. Par exemple, pour les imprimantes, les processus « spoolent » leurs travaux dans un
répertoire spécialisé et un démon d’impression les traitera, en série, l’un après l’autre.
• Pour ce qui concerne la deuxième condition (la détention et l’attente), elle pourrait être évitée si
les processus demandaient leurs ressources à l’avance. Ceci est en fait très difficile à réaliser dans la
pratique car l’allocation est, en général, dynamique. Empêcher cette condition serait donc
particulièrement coûteux.
• La troisième condition (pas de préemption) n’est pas raisonnablement traitable pour la plupart des
ressources sans dégrader profondément le fonctionnement du système. On peut cependant
l’envisager pour certaines ressources dont le contexte peut être sauvegardé et restauré.
• Le problème de l’attente circulaire, dernière condition, peut être résolu en numérotant les
ressources et en n’autorisant leur demande, par un processus, que lorsqu’elles correspondent à des
numéros croissants ou en accordant aux processus une seule ressource à la fois (s’il a besoin d’une
autre ressource, il doit libérer la première). Par exemple :
F(CD-ROM)=1
F(imprimante)=2
F(plotter)=3
F(rubban)=4
Ainsi on garantit qu’il n’aura pas de cycles dans le graphe des ressources. On peut exiger seulement
qu’aucun processus ne demande une ressource dont le numéro est inférieur aux ressources déjà
allouées. Mais ceci n’est pas non plus la panacée, car, en général, le nombre potentiel de ressources
est si important qu’il est très difficile de trouver la bonne fonction F pour les numéroter.
Source : http://www.groupes.polymtl.ca/inf2610/documentation/notes/chap7.pdf
D’autres détails se trouvent dans : Andrew Tanenbaum, Systèmes d’exploitation (2ème édition) page
169-195
26
L’interblocage est un problème lorsque des processus ont obtenu des accès exclusif à certaines
ressources et lorsque chacun de ces processus sollicite une ressource détenu par un autre processus
du groupe. Nous avons vu qu’il est possible d’éviter les interblocages en réalisant un suivi des états
(un état sûr présente une séquence d’évènements qui offre la garantie que tous les processus
peuvent se terminer et un état non sûr n’offre pas cette garantie. On a vu également que l’on peut
éviter l’interblocage en concevant un système qui les empêche de se produire.
Conclusion
Pour pallier aux effets d’interruption les SE offrent un modèle conceptuel de processus s’exécutant
en parallèle. Chaque processus possède son propre espace d’adressage. Dans certains cas, il existe
plusieurs threads de contrôle pour un même processus. Ces threads sont ordonnancés
indépendamment les uns et les autres et chacun possède sa propre pile. La communication
interprocessus passe par certaines primitives comme les sémaphores, les moniteurs ou les messages.
Grâce à ces primitives un ensemble de problèmes de synchronisation mais il faut rester attentif aux
erreurs et aux interblocages.
Fiche TD2(partie 4)
Question 1 :
Question 2 :
Des étudiants qui travaillent sur des PC dans un laboratoire d’informatique envoient leurs fichiers à
imprimer par un serveur qui les spoulent sur son disque dur. Sous quelle condition un interblocage
peut-il se produire si l’espace de spoule de l’imprimante est limité ? Comment éviter l’interblocage ?
Question 3 :
sont résolus.
Question 4 :
Dans un système électronique de transfert de fonds, il existe des centaines de processus identiques
qui fonctionnent comme suit : Chaque processus lit une ligne de données qui spécifie la quantité
d’argent, le numéro de compte à créditer et le numéro de compte à débiter. Il verrouille ensuite l’un
après l’autre les deux comptes, transfère l’argent puis libère les verrous.
27
2. Si vous répondez oui à la question précédente, proposez une solution qui permet de
les éviter. Attention : ne pas libérer l’enregistrement d’un compte avant que le transfert
ne soit terminé.
28