Objectifs du cours

• Comprendre la notion d’interblocage :

– Comment modéliser l’utilisation des ressources ?
– Comment détecter l’interblocage ?
– Comment prévénir l’interblocage ?
• Apprendre la programmation avec le système.
– Comment créer des applications qui communiquent avec l’OS ou avec
d’autres applications, en se synchronisant correctement.
• Comprendre les principes du fonctionnement d’un système.
– Que se passe-t-il quand je tape ls ?
– Quand je tape Ctrl-C, Ctrl-S ou Ctrl-Z ?
– Comment
• sont gérés les processus,
• sont stockées les données sur disque ?
• Comprendre l’utilisation des sockets (programmation réseau).
 Plan
• Chap 1 : Généralités sur la programmation
concurrente
• Chap 2 : Initiation à la programmation
système
• Chap 3 : Initiation à la programmation réseau
 Généralités sur la
programmation concurrente
Chapitre 1
NOTION DE PROGRAMMATION
CONCURRENTE
Programme Concurrent vs. séquentiel
• Programme séquentiel = Un programme qui
comporte un seul fil d’exécution — un seul
processus ⇒ Un seul doigt suffit pour indiquer
l’instruction en cours d’exécution
• Programme concurrent = Un programme qui
contient deux ou plusieurs processus qui
coopèrent ⇒ Plusieurs doigts sont nécessaires
pour indiquer les instructions en cours
d’exécution
• Un processus ici peut aussi bien être un
processus lourd qu’un processus léger (thread)
 Types d’applications concurrentes
• Application multi-contextes = contient deux ou plusieurs
processus, qui peuvent ou non s’exécuter en même temps, et qui
sont utilisés pour mieux organiser et structurer l’application
(meilleure modularité)
Exemples : Système d’exploitation multi-tâches, interface personne-
machine, …
• Application parallèle = chaque processus s’exécute sur son propre
processeur (ou coeur), dans le but de résoudre plus rapidement un
problème — ou pour résoudre un problème plus gros
Exemples : Prévisions météorologiques, modélisation du climat,
simulations physiques, bio-informatique, traitement graphique, etc.
• Application distribuée = contient deux ou plusieurs processus, qui
communiquent par l’intermédiaire d’un réseau (⇒ délais plus
longs), et ce pour répartir, géographiquement, des données et des
traitements
Exemples : Serveurs de fichiers, accès à distance à des banques de
données
 État des processus
• Suspendu : à la création
• Suspendu -> prêt :
allocation mémoire
• Prêt->en exécution :
choix par ordonnanceur
• En exécution -> prêt :
préemption
• En exécution -> bloqué :
attente d’E/S
 Ordonnancement
• Ordonnanceur : partie du SE qui détermine à
un instant donnée le processus à exécuter
• Algorithme d’ordonnancement : ensemble de
règles permettant de choisir parmi plusieurs
processus prêts lequel exécuter
• Algorithmes classiques : File de processus prêt

– FCFS ou FIFO ; Pi

– SRT ou PCTER ;
Pi+1
– RR ou Tourniquet ;
– Priorité.
Pi+n
 Conventions

Processus Arrivée Durée

….. ….. …..

Pi ti di
Pi+1 ti+1 di+1
Pi+2 ti+2 di+2
….. ….. …..
….. ….. …..
 Algorithme FCFS
 FCFS : First-come first- Exemple
served - premier entré,
premier sortie ou FIFO Processus Arrivée Durée
(First In First Out) P1 2 3
 Critère : ordre d’arrivée P2 0 4
 Algorithme non préemptif P3 0 6
 Favorise d’avantage les P4 1 2
processus tributaires de
l’UC
P2 P3 P4 P1
0 4 10 12 15

TR moyen =((15-2)+(4-0)+(10-0)+(12-1))/4
 Algorithme SRT
 SRT : shortest Remaining
Time – temps restant le Exemple
plus court ou PCTER (Plus
Court Temps d’Exécution Processus Arrivée Durée
Restant)
 Critère : temps de P1 2 3
traitement restant le plus P2 0 4
court
P3 0 6
 En cas d’égalité utiliser FCFS
 Algorithme préemptif
P4 1 2

P2 P4 P2 P1 P3
0 1 3 6 9 15

TR moyen =((9-2)+(6-0)+(15-0)+(3-1))/4
 Algorithme RR
 RR : round robin - Exemple : q=1
tourniquet
 Algorithme préemptif Processus Arrivée Durée

 Critère : quantum de P1 2 3
temps d’exécution – P2 0 4
ordre d’arrivé P3 0 6
 Algorithme préemptif P4 1 2

P2 P3 P4 P2 P1 P3 P4 P2 P1 P3 P2 P1 P3 P3 P3
0 4 8 12 15

TR moyen =((12-2)+(11-0)+(15-0)+(7-1))/4
 Algorithme avec priorité
 Critère : priorité Exemple : priorité statique (prio
 En cas d’égalité de priorité 1 > prio 2), préemptif
utilise FCFS Processus Arrivée Durée priorité
 Variantes :
 Préemptif/non préemptif
 Priorité statique/ priorité
P1 2 3 1
dynamique
P2 0 4 2
P3 0 6 1
P4 1 2 3

P3 P1 P2 P4
0 6 9 13 15

TR moyen =((9-2)+(13-0)+(6-0)+(15-1))/4
Programme CPU-bound et Programme
IO-bound
• CPU-bound : un programme est CPU-bound si
son temps d’exécution est limité (contraint)
par la vitesse du CPU.
• IO-bound : un programme est IO-bound si son
temps d’exécution est limité (contraint) par la
vitesse du système d’entrées/sorties (accès
disques, accès réseaux, etc.).
 Actions atomiques
• Action atomique = Une action qui examine ou
change l’état d’un processus de façon indivisible.
• Un processus exécute une séquence
d’instructions. Chaque instruction peut elle-
même être mise en oeuvre par une séquence
d’une ou plusieurs actions atomiques associées à
des instructions machines.
• Pour qu’un programme concurrent soit considéré
correct, il doit produire le bon résultat peu
importe la vitesse à laquelle s’exécute chacun des
processus
RESSOURCES CRITIQUES ET
INTERBLOCAGES
 Ressource
• Une ressource est un objet allouable à un seul processus à la fois.
• Elle peut être un périphérique matériel ou une information.

2 Type de ressources
préemptibles: ressource pouvant
être retirée sans dommages du
processus

Non préemptibles : ressource qui

ne peut être enlevée sans que le Interblocage
traitement échoue
• De nombreuses applications nécessitent un accès exclusif à plusieurs
ressources (ex : impression d’un fichier depuis une disquette)
• PB : dans un système multiprogrammé, plusieurs processus peuvent
désirer accéder aux mêmes ressources exclusives
• Ex : 2 processus qui veulent imprimer un fichier contenu sur une
disquette
– Proc A requiert l’imprimante et l’obtient
– Proc B monte la disquette
– A essaye de monter la disquette, malheureusement B ne la libère
pas et demande l’imprimante
– A ce stade les 2 processus sont bloqués et le resteront indéfiniment
• Cette situation est appelée interblocage (deadlock)
• Les interblocages peuvent intervenir dans bien d’autres situations que
l’accès à des périphériques d’E/S
• Ex : l’accès à 2 enregistrements d’une BD
• Les interblocages peuvent donc se produire sur des ressources
matérielles et logicielles
 Interblocages : définition

Un ensemble de processus est en interblocage si chaque

processus attend un événement que seul un autre de
l’ensemble peut engendrer

• Comme tous les processus attendent, aucun ne pourra

produire l’événement pour réveiller un des autres
processus
• La plupart du temps, l’événement attendu par un
processus est la libération d’une ressource détenue par
un autre
• Le nombre de processus, le nombre de ressources et la
nature des ressources n’importent pas.
 Modélisation des ressources
Cycle d’utilisation d’une ressource R par un processus P
Solliciter (Demander) Utiliser (Détenir) la
Libérer la ressource
la ressource ressource
R R R

P P P

• L’utilisation d’une ressource produit 3 événements :

1. Demande de la ressource
2. Utilisation de la ressource
3. Libération de la ressource
• Nous considérons qu’un processus demandant une ressource
déjà allouée est bloqué (ou en sommeil)
 Modélisation des ressources multi-
M ressources instances
M ressources

N processus
Alloc= Aij
Besoin= Bij N processus

Nombre d’instances de la Nombre d’instances de la

ressource Rj allouées à Pi ressource Rj dont Pi à besoin
M ressources
M ressources
Dispo= Dj Exist= Ej
Nombre d’instances
Nombre total d’instances de
disponible de la ressource Rj
la ressource Rj

Ej=∑i Aij + Dj
 Conditions d’interblocage
Interblocage Un ensemble de processus est en interblocage si
R et seulement si chaque processus attend un
Q évènement (libération d’une ressource) que seul
P un processus de l’ensemble peut engendrer
S

Conditions Chaque ressource est soit attribuée à un seul

Exclusion mutuelle processus, soit disponible
Un processus ayant déjà obtenu des ressources
Occupation - Attente
peut demander de nouvelles ressources
Une ressource allouée ne peut être retirée de force
Non réquisition
à un processus
Il doit y avoir un cycle d’au moins 2 processus,
Attente circulaire chacun attendant une ressource détenue par un
autre processus du cycle
 R
Détection avec le graphe P
Q

S
1. Pour chaque nœud N dans le graphe suivez les cinq étapes ci-après,
avec N comme point de départ.
2. Initialisez L à une liste vide et désignez tous les arcs comme marqués
3. Ajoutez le nœud en cours à la fin de la liste L et vérifiez que le nœud
apparaît deux fois dans L. Si tel est le cas, le graphe contient un cycle
(répertorié dans L) et l’algorithme prend fin.
4. Pour un nœud donné, voyez s’il y a des arcs non marqués sortants.
Dans ce cas rendez-vous à l’étape 5, et à l’étape 6 dans le cas
contraire.
5. Choisissez au hasard un arc sortant non marqué et marquez-le.
Suivez-le jusqu’au prochain nouveau nœud en cours et rendez-vous à
l’étape 3.
6. Vous vous trouvez dans une impasse. Supprimez l’arc et revenez au
nœud précédent, c’est-à-dire à celui qui était actif juste avant celui-ci.
Faites-en le nœud en cours et retournez à l’étape 3. Si ce nœud est le
nœud initial, le graphe ne contient pas de cycles et l’algorithme prend
fin.
 Détection avec les matrices
1. On cherche un processus non marqué, Pi pour
lequel la ième rangée de Besoin est inférieure ou
égale à Dispo.
2. Si l’on trouve ce processus, on ajoute la ième
rangée de Alloc à Dispo, on marque le processus
et l’on revient à l’étape 1.
3. Si un tel processus n’existe pas, l’algorithme se
termine
Lorsque l’algorithme se termine, tous les processus
non marqués , s’il y’en a, sont en interblocage.
 Traitement des interblocages
Mépris Détection - Reprise
Détection
Ressources avec instances Uniques → Graphes
d’allocation
Ressources avec instances multiples → 2
Matrices (Alloc, Besoin) 2 vecteurs (Dispo,
Hypothèses : Les interblocages Exist)
surviennent rarement. Le coût Reprise
de prévention contre les Par préemption de ressource
interblocages est prohibitif. Par rollback : Points de Reprise permettant de
Evitement restaurer un état précèdent.
Par suppression des processus : Supprimer
Algorithme du banquier : des processus jusqu’à ce que le cycle est
examiner chaque nouvelle détruit
requête pour voir si elle conduit à
un état sûr Prévention
Si oui→allouer la ressource Mettre en défaut l’une des 4
Si non→ne pas allouer la ressource conditions d’interblocage
SECTION CRITIQUE ET
SYNCHRONISATION PAR SÉMAPHORE
 Section critique
• Schéma général
Processus 1 Processus 2

….. …..
Entrée en section critique Entrée en section critique
Section critique Section critique
Sortie de section critique Sortie de section critique
…. ….

• Exclusion mutuelle garantie par les opérations

(entrée en section critique) et (sortie de
section critique)
 Réalisation d’une section critique par attente active
Hypothèses : atomicité d’accès et de modification de variables
Solution FAUSSE numéro 1
Demande alternance stricte ;
while (tour != MOI) ; /*attente active */ Impossible d’entrer deux fois de
SC(); /*section critique */ suite dans SC() (même si il y a un
tour = 1- MOI ; /* passer le tour à l’autre*/ seul processus) : famine

Solution FAUSSE numéro 2 Pas d’exclusion mutuelle

while (flag[1- MOI+) ; /*attente l’autre */ (compétition)
flag[MOI]=VRAI ; /*annonce entrer */ P0 test flag[1] et trouve FAUX
SC(); /*section critique */ P1 test flag[0] et trouve FAUX
flag[MOI]=FAUX ; /* débloque l’autre*/ Les deux entre dans SC()

Solution FAUSSE numéro 3 Possibilité d’interblocage

flag[MOI]=VRAI ; /*annonce entrer */ P0 : flag*0+ ←VRAI
while (flag[1- MOI+) ; /*attente l’autre */ P1 : flag*1+ ←VRAI
SC(); /*section critique */ Les deux processus entrent dans
flag[MOI]=FAUX ; /* débloque l’autre*/ la boucle d’attente active
 Algorithme correct d’attente active

Algorithme de Peterson
flag[MOI] =VRAI /* Annonce être intéressé */
tour = 1-MOI /* mais on laisse la priorité à l’autre */
while((flag[1-MOI])==VRAI && /*on entre si l’autre ne veux pas entrer */
(tour==1-MOI)) /*ou s’il nous a laissé la priorité */
CS()
flag[MOI]=FAUX /*sorti de la section critique*/

GL Peterson. A New Solution to Lamport’s Concurrent Programming Problem.

1983. [Link]
 Problèmes de synchronisation
• Condition de compétition (race condition)
– Définition : le résultat change avec l’ordre des instructions
– Difficile à corriger car difficile à reproduire (ordre aléatoire )
• Interblocage (deadlock)
– Définition : un groupe de processus bloqués en attente
mutuelle
– Evitement parfois difficile (correction de l’algorithme)
– Détection assez simple, mais pas de guérison sans perte
• Famine (starvation)
– Définition : un processus attend indéfiniment une ressource
(problème d’équité)
– Servir équitablement les processus demandeurs
 Sémaphore : outil de base pour la
synchronisation
• Objet composé :
– D’une variable : valeur du sémaphore (nombre de places restantes)
– D’une file d’attente : liste des processus bloqués sur le sémaphore
• Primitives associées :
– Initialisation (avec une valeur positive ou nulle)
– Prise (P, Probeer, down, wait) = demande d’autorisation ( puis-je ? )
Si valeur = 0, blocage du processus ; Si non, valeur = valeur − 1
– Validation (V, Verhoog, up, signal) = fin d’utilisation ( vas-y )
Si valeur = 0 et processus bloqué, déblocage d’un processus ;
Si non, valeur = valeur + 1

• E.W. Dijkstra. Solution of a Problem in Concurrent Programming

Control. 1965. (lire l’article)
 Schémas de synchronisation
• Exclusion mutuelle : ressource accessible par une seule entité à la fois
– Compte bancaire ; Carte son
• Problème de cohorte : ressource partagée par au plus N utilisateurs
– Un parking souterrain peut accueillir 500 voitures (pas une de plus)
– Un serveur doom peut accueillir 2000 joueurs
• Rendez-vous : des processus collaborant doivent s’attendre mutuellement
– Roméo et Juliette ne peuvent se prendre la main que s’ils se rencontrent
– Le GIGN doit entrer en même temps par le toit, la porte et la fenêtre
– Processus devant échanger des informations entre les étapes de l’algorithme
• Producteurs/Consommateurs : un processus doit attendre la fin d’un autre
– Réception de données sur le réseau puis traitement
• Lecteurs/Rédacteurs : notion d’accès exclusif entre catégories
d’utilisateurs
– Sur une section de voie unique, tous les trains doivent rouler dans le même
sens
– Un fichier pouvant être lu par plusieurs, si personne ne le modifie
– Tâches de maintenance (défragmentation) quand pas de tâches interactives
 Exclusion mutuelle par sémaphore

Initialisation
sem =semaphore (1)

Agence Ouaga Agence Koudougou

P(sem) P(sem)
Courant = get_account(1867A) Actuel = get_account(1867A)
Nouveau = Courant +1000 New = Actuel - 1000
update_account(1867A, Nouveau) update_account(1867A, New)
V(sem) V(sem)
Cohortes et sémaphores

Initialisation Garer sa voiture

sem =semaphore (3)
P(sem)
Poser sa voiture au parking
Aller faire les courses
Reprendre la voiture
V(sem)

Ressource partagée par au

plus N utilisateurs
 Envoi de signal et sémaphores
Envoi de signal
Un processus indique quelque chose à un autre (ex : disponibilité
d’une donnée)
Initialisation Processus 1 Processus 2
top =semaphore (0) ….. …..
Calcul(info) P(top) /*Bloque en attente */
V(top) Utilisation(info)
….. …..
Rendez-vous et sémaphores

Rendez-vous entre deux processus

Les processus s’attendent mutuellement

Initialisation Processus 1 (Romeo) Processus 2 (Juliette)

rom =semaphore (0)
P(rom) /*se bloque*/ V(rom) /*libère Ro*/
jul =semaphore (0)
V(jul) /*libère Ju*/ P(jul) /*se bloque*/
Producteurs et consomateurs
Contrôle de flux entre producteur(s) et consommateur(s) par
tampon
Exemple :
1. Situation initiale : tampon vide (pas de lecture possible)
2. Après une production :
3. Une autre production :
4. Encore une production : (plus de production possible)
5. Une consommation : (production de nouveau possible)

Réalisation
Initialisation Producteur Consommateur
placedispo =semaphore (N) Répéter Répéter
infoprete=semaphore (0) Calcul(info) P(infoprete)
P(placedispo) extraire(info)
Déposer(info) V(placedispo)
V(infoprete) Utiliser(info)

Le tampon doit être circulaire pour traiter les données dans l’ordre de production
Attention aux compétitions entre producteurs (idem entre consommateurs)
Lecteurs et rédacteurs
Contrôle d’accès exclusif entre catégories d’utilisateurs
• Accès simultané de plusieurs lecteurs
• Accès exclusif d’un seul rédacteur, également exclusif de tout lecteur
• Schéma assez classique (fichier sur disque, zone mémoire, etc.)
Première solution
Lecteur Rédacteur
Initialisation
P(lecteur) P(redacteur)
NbLect=NbLect+1 LecturesEtEcritures()
lecteur =semaphore (1)
Si NbLect==1 alors V(redacteur)
redacteur=semaphore (1)
P(redacteur)
NbLect=0
V(lecteur)
Lectures()
P(lecteur)
NbLect=NbLect-1
Si NbLect==0 alors
V(redacteur)
V(lecteur)

Problème : famine potentielle des rédacteurs

Lecteurs et rédacteurs sans famine

Lecteur Rédacteur
Initialisation
P(fifo) P(fifo)
lecteur =semaphore (1) P(redacteur)
P(lecteur)
redacteur=semaphore (1) V(fifo)
NbLect=NbLect+1
fifo=semaphore (1) LecturesEtEcritures()
Si NbLect==1 alors
NbLect=0 V(redacteur)
P(redacteur)
V(lecteur)
V(fifo)
Lectures()
P(lecteur)
NbLect=NbLect-1
Si NbLect==0 alors
V(redacteur)
V(lecteur)