Plan du cours

CH.1- Concepts généraux

CH.2- Processus

CH.3- Communication interprocessus

CH.4- Synchronisation de processus

CH.5- Moniteur et interblocage

CH.6- Ordonnancement de processus

CH.7- Gestion de la mémoire et mémoire virtuelle

CH.8- Systèmes de fichiers

[Link],[Link] - SE 1
 CH.1- Concepts Généraux
❑ Système informatique

Imprimante
Disque Ecran
dur
Scanner

Disquette
Unité Centrale Vidéo
(UC)

CD-ROM
DVD
Son
Souris Fax
Clavier Modem
[Link],[Link] - SE RNIS 2
 CH.1- Concepts Généraux
❑ Système informatique

Unité centrale de
traitement Mémoire cache

Unité de commande Instructions

Mémoire centrale
(RAM)

UAL
(Unité Arithmétique Données
et Logique)

Unités d’entrées/sortie (I/O)

Contrôleur de
périphériques
Carte réseau

périphériques

[Link],[Link] - SE 3
 CH.1- Concepts Généraux
❑ Système informatique
Utilisateurs

Programmes Programmes
utilitaires d’applications

- Éditeur de textes - Systèmes de bases de données

Compilateurs - Jeux
-Tableur
Assembleurs
- Système de gestion

Programmes systèmes

Système d’exploitation
Système
informatique
Matériel

[Link],[Link] - SE 4
 CH.1- Concepts Généraux
❑ Fonctions principales d’un S.E.
τ2
τ3

R
Gestion de τ1 τ4
processus τ5
τ1
Protection

Mémoire cache
Gestion de Mémoire
la mémoire centrale
(RAM)
principale
SE
Gestion des E/S

Gestion de la
mémoire auxiliaire

Gestion
[Link],[Link] - SE de fichiers 55
 CH.1- Concepts Généraux
❑ Fonctions principales d’un S.E.

Ressources partagées par les processus

• CPU (cœur d’un processeur)
Proc Proc Proc Proc
• Mémoire 1 2 3 4

• Entrées-sorties

Système d’exploitation
Gestion par le Système d'Exploitation
• Exclusion mutuelle
• Contrôle de l'accès au matériel
• Droits d'accès
• Non-dépassement des limites processeur
disque mémoire
dur
 CH. 1- Concepts Généraux
❑ Evolution du mode d’exploitation
➢Les nouvelles tendances

• architecture micro-noyau (microkernel);

• exécution multifilière (multithreading);
• traitement parallèle symétrique (symmetric
multiprocessing);
• système d’exploitation réparti (distributed operating
system);
• Systèmes d’exploitation temps-réel.

[Link],[Link] - SE 7
 CH.2- Processus
❑ Qu’est ce qu’un processus
Un est un programme en cours d’exécution. Il est caractérisé par:

pointeur État du
processus Autres informations indiquant, notamment
• son processus père;
Numéro du processus
• ses processus fils;
Compteur d’instructions
Mot d’état • son groupe;
Registres • ses variables d’environnement;
Limites de la mémoire • les statistiques et les limites d’utilisation des
Liste des fichiers ouverts ressources;
Priorité •les signaux à capturer, à masquer, à ignorer, en
Pointeur sur Files d’attente
attente ainsi que les actions associées.

[Link],[Link] - SE 8
 CH.2- Processus
❑ Qu’est ce qu’un processus
➢ Le système d’exploitation maintient dans une table appelée « table des processus » les
informations sur tous les processus crées (PCB ou BCP).
➢Cette table permet au S.E. de localiser et gérer tous les processus.

Dans la plupart des systèmes d’exploitation,

Le BCP est composé de deux zones:

➢ La première contient les informations

critiques dont le système a toujours besoin
(jamais MAJ)

➢ La deuxième contient les informations

utilisée uniquement lorsque le processus
est en exécution

[Link],[Link] - SE 9
 CH.2- Processus
❑ Etat d’un processus
➢ L’état d’un processus décrit sa dynamique actuelle. Un processus
peut se trouver dans 6 (7) états:

Terminé
Nouveau admis
élu exit

Prêt interrompu En exécution

reprise occurrence attente

d’un événement d’un événement

Suspendu
En attente Bloqué

[Link],[Link] - SE 10
 CH.2- Processus
❑ Hiérarchie des processus

➢ Le système d’exploitation fournit un ensemble d’appels système

qui permettent le création, la destruction, la communication et le
synchronisation des processus.

➢ Les processus sont crées et détruits dynamiquement.

➢ Un processus peut créer un ou plusieurs processus qui, à leur tour,

Peuvent en créer d’autres:

Hiérarchie des processus

[Link],[Link] - SE 11
 CH.2- Processus
➢ Hiérarchie des processus sous UNIX

racine

Père
pagedaemon swappeur init

utilisateur1 utilisateur2 utilisateur3

Ses 3 fils

Descendance de
utilisateur 3

[Link],[Link] - SE 12
 CH.2- Processus
❑ Processus d’Unix

➢ Chaque processus a un numéro d’identification unique (PID).

L’appel system getpid() permet de récupérer le PID du processus : int getpid();

➢ Chaque processus a un père, à l’exception du premier processus créé

(structure arborescente).
✓ S’il perd son père (se termine), il est tout de suite adopté par le processus
init de PID 1.
✓ L’appel système getppid() permet de récupérer le PID de son processus
père.

➢ Un processus père s’exécute en concurrence avec ses fils (exécution

asynchrone).

[Link],[Link] - SE 13
 CH.2- Processus
❑ Processus d’Unix
➢ Un processus fils peut partager certaines ressources (mémoire, fichiers)
avec son processus père ou avoir ses propres ressources. Le processus
père peut contrôler l’usage des ressources partagées.

➢ Le processus père peut avoir une certaine autorité sur ses processus fils.
Il peut les suspendre, les détruire (appel système kill), attendre leur
terminaison (appel système wait) mais ne peut pas les renier.

➢La création de processus est réalisée par duplication de l’espace

d’adressage et de certaines tables du processus créateur (l’appel système
fork). La duplication facilite la création et le partage de ressources. Le fils
hérite des résultats déjà calculés par le père.

➢Un processus peut remplacer son code exécutable par un autre (appel
système exec).

[Link],[Link] - SE 14
 Processus Père
Pid 12
Fork
Le
Programme toto mêm
e pr
Variables x, n, i…. ogr
….. amm
x := 0.2; n := 1; e
i := fork(); C.O.
C.O.
Processus Fils
Prochaine instruction Pid 74
Fork

0.2 74 0.2 0
x 1 i x 1 i
n n
Espace mémoire Père Espace mémoire Fils
Copie de Espace mémoire Père

[Link],[Link] - SE 15
 Processus Père Processus Fils Exec
Pid 12 Pid 74
Fichier titi
Programme toto
Variables…..
x, n, i…. Programme un_autre
Variables z, p…
x := 0.2; n := 1; C.O.
i := fork(); C.O. Première instruction

If i = 0 then
C.O.
exec(titi);
End if;

0.2 74 0.2 0
x 1 i x 1 i
n n
Espace mémoire Père
Espace mémoire Fils

[Link],[Link] - SE z p 16
 CH.2- Processus
❑ Terminaison d’un processus

➢Un processus se termine par une demande d’arrêt volontaire (appel système exit) ou
par un arrêt forcé provoqué par un autre processus (appel système kill) ou une erreur.
void exit(int vstatus);

➢ Lorsqu’un processus fils se termine :

✓son état de terminaison est enregistré dans son PCB,
✓la plupart des autres ressources allouées au processus sont libérées.
✓le processus passe à l’état zombie (<defunct>).

➢ Son PCB et son PID sont conservés jusqu’à ce que son processus père ait
récupéré cet état de terminaison.

➢ Les appels système wait(status) et waitpid.(pid, status, option) permettent au processus

père de récupérer, dans le paramètre status, cet état de terminaison.

[Link],[Link] - SE 17
 CH.2- Processus
❑ Etats d’un processus

destruction

Terminé

création terminaison
(kill, exit, fin)
élection
Prêt Actif
préemption

acquisition de la ressource attente d'une

(ou kill pour certaines ressource
attentes)
En attente

[Link],[Link] - SE 18
18
 CH.3- Communication interprocessus
Il existe plusieurs mécanismes de communication
interprocessus:
❑ Les données communes;
❑ Les signaux;
❑ Les messages.

➢ Les processus partagent un ensemble de données communes qui sont

soit en mémoire (variables ou segments de données) ou sur disque
(fichiers).
➢ Chaque processus peut accéder en lecture ou en écriture à cet ensemble
de données (espace de données commun).
➢ Il est possible de créer des segments de données, de les rattacher et de
les détacher des processus.
➢ On peut ainsi créer des segments de données communs à plusieurs
Processus.

[Link],[Link] - SE 19
 CH.3- Communication interprocessus
Il existe plusieurs mécanismes de communication
interprocessus:
❑ Les données communes;
❑ Les signaux;
❑ Les messages.
➢ Un signal est une interruption logicielle asynchrone qui a pour but d’informer
de l’arrivée d’un événement (outil de base de notification d’événement).
➢ Ce mécanisme de communication permet à un processus de réagir à un
événement sans être obligé de tester en permanence l’arrivée
➢ Le système d’exploitation gère un ensemble de signaux. Chaque signal a un
nom, un numéro, un gestionnaire (handler) et est associé à un type
d’événement.
➢ Le SE associe à chaque signal un traitement par défaut (abort, exit, ignore, stop,
continue).
➢ Le SE permet à un processus de redéfinir pour certains signaux leurs
gestionnaires. Un processus peut donc indiquer au système ce qui doit se
passer à la réception d’un signal.

[Link],[Link] - SE 20
 CH.3- Communication interprocessus
Il existe plusieurs mécanismes de communication
interprocessus:
❑ Les données communes;
❑ Les signaux;
❑ Les messages.
Un autre mécanisme de communication entre processus est l’échange de messages.
Chaque message véhicule des données. Il existe plusieurs mécanismes de
communication par envoi de messages:
➢ Les tubes de communication;
➢ Les files de messages;
➢ Les sockets.
Les tubes de communication permettent à deux ou plusieurs processus
d’échanger des informations. On distingue deux types de tubes:
✓ Les tubes anonymes;
✓Les tubes nommés.
o Les tubes anonymes peuvent être considérés comme des fichiers temporaires;
o Ils permettent d’établir des liaisons unidirectionnels de communication entre
processus dépendants;
o Un tube de communication permet de mémoriser des informations et se comporte
comme une file FIFO.
[Link],[Link] - SE 21
 CH.3- Communication interprocessus
Il existe plusieurs mécanismes de communication
interprocessus:
❑ Les données communes;
❑ Les signaux;
❑ Les messages.
Un autre mécanisme de communication entre processus est l’échange
de messages. Chaque message véhicule des données. Il existe plusieurs
mécanismes de communication par envoi de messages:
➢ Les tubes de communication;
➢ Les files de messages;
➢Les sockets.
Les tubes de communication permettent à deux ou plusieurs processus
d’échanger des informations. On distingue deux types de tubes:
✓ Les tubes anonymes;
✓ Les tubes nommés (qui ont une existence dans le système de fichier).
Ils sont plus intéressants que les tubes anonymes car ils offrent, en plus, les
avantages suivants:
o Ils ont chacun un nom qui existe dans le système de fichier;
o Ils peuvent être utilisés par des processus indépendants;
o Ils existent jusqu’à ce qu’ils soient supprimés explicitement.
[Link],[Link] - SE 22
 CH.3- Communication interprocessus
Il existe plusieurs mécanismes de communication
interprocessus:

❑ Les données communes;

❑ Les signaux;
❑ Les messages.

Un autre mécanisme de communication entre processus est l’échange de

messages. Chaque message véhicule des données. Il existe plusieurs
mécanismes de communication par envoi de messages:
➢ Les tubes de communication;
➢ Les files de messages;
➢ Les sockets.

[Link],[Link] - SE 23
 CH.4 - Synchronisation de processus: Introduction

❑ Dans un SE multiprogrammé en temps partagé, plusieurs processus

s’exécutent en pseudo-parallèle ou en parallèle et partagent des objets
(mémoire, imprimante,…)

❑ Le partage d’objet sans précaution particulière peut conduire à des

résultats imprévisibles (l’état final des données dépend de la séquence
d’exécution des processus).

❑ Lorsqu’un processus modifie un objet partagé, les autres processus

ne doivent ni la lire, ni la modifier jusqu’à ce que le processus ait terminé
de la modifier.

❑ Autrement dit, l’accès à l’objet doit se faire en exclusion mutuelle.

[Link],[Link] - SE 24
 CH.4 - Synchronisation de processus: Section critique
❑ Section critique: suite d’instructions qui opèrent sur un ou plusieurs objets partagés
et qui nécessitent une utilisation exclusive des objets partagés.

❑ Les sections critiques des différents processus qui opèrent sur des objets communs
doivent s’exécuter en exclusion mutuelle.

❑ Avant d’entamer l’exécution d’une de ses sections critiques, un processus doit

s’assurer de l’utilisation exclusive des objets partagés manipulés par la section critique:
➢ Encadrer chaque section critique par des opérations spéciales qui visent à
assurer l’utilisation exclusive des objets partagés.
➢ Quatre conditions sont nécessaires pour réaliser correctement une exclusion
mutuelle :
✓ Deux processus ne peuvent être en même temps dans leurs sections
critiques.
✓ Aucune hypothèse ne doit être faite sur les vitesses relatives des processus
et sur le nombre de processeurs.
✓ Aucun processus suspendu en dehors de sa section critique ne doit bloquer
les autres processus.
✓ Aucun processus ne doit attendre trop longtemps avant d’entrer en section
critique (attente bornée).
[Link],[Link] - SE 25
 CH.4 - Synchronisation de processus: Section critique
❑ Masquage des interruptions
➢ Avant d’entrer dans une section critique, le processus masque les interruptions.

➢ Il les restaure à la fin de la section critique.

➢ Il ne peut être alors suspendu durant l’exécution de la section critique.

Problèmes:

➢ Solution dangereuse : si le processus, pour une raison ou pour une autre,

ne restaure pas les interruptions à la sortie de la section critique, ce serait la
fin du système.

➢ Elle n’assure pas l’exclusion mutuelle, si le système n’est pas

monoprocesseur (le masquage des interruptions concerne uniquement le
processeur qui a demandé l’interdiction). Les autres processus exécutés
par un autre processeur pourront donc accéder aux objets partagés.

➢ En revanche, cette technique est parfois utilisée par le système d’exploitation.

[Link],[Link] - SE 26
 CH.4 - Synchronisation de processus: Section critique
❑ Attente active et verrouillage
➢ Utiliser une variable partagée verrou, unique, initialisée à 0.
➢ Pour rentrer en section critique, un processus doit tester la valeur du verrou.
➢ Si verrou = 0, le processus met le verrou à 1 puis exécute sa section critique.
➢ A la fin de la section critique , il remet le verrou à 0.
➢ Sinon, il attend (attente active ) que le verrou devienne égal à 0 :
while(verrou !=0) ;

Problèmes
➢ Elle n’assure pas l’exclusion mutuelle :
✓Supposons qu’un processus est suspendu juste après avoir lu la valeur du
verrou qui est égal à 0.
✓Ensuite, un autre processus est élu. Ce dernier teste le verrou qui est toujours
égal à 0, met le verrou à 1 et entre dans sa section critique.
✓Ce processus est suspendu avant de quitter la section critique. Le premier
processus est alors réactivé, il entre dans sa section critique et met le verrou à 1.
✓Les deux processus sont en même temps en section critique.
➢L’attente active surcharge le CPU

[Link],[Link] - SE 27
 CH.4 - Synchronisation de processus: Section critique
❑ Attente active avec alternance
➢ Utiliser une variable tour qui mémorise le tour du processus qui doit entrer en section
critique.
➢ tour est initialisée à 0.
Processus P0 Processus P1
while (1) while (1)
{ /*attente active*/ { /*attente active*/
while (tour !=0) ; while (tour !=1) ;
section_critique_P0() ; section_critique_P1() ;
tour = 1 ; tour = 0 ;
…. ….
} }
Problèmes
➢ Un processus peut être bloqué par un processus qui n’est pas en section critique.
✓ P0 lit la valeur de tour qui vaut 0 et entre dans sa section critique. Il est suspendu et P1
est exécuté.
✓ P1 teste la valeur de tour qui est toujours égale à 0. Il entre donc dans une boucle en attendant
que tour prenne la valeur 1. Il est suspendu et P0 est élu de nouveau.
✓ P0 quitte sa section critique, met tour à 1 et entame sa section non critique. Il est suspendu et
P1 est exécuté.
✓ P1 exécute rapidement sa section critique, tour = 0 et sa section non critique. Il teste tour qui
vaut 0. Il attend que tour prenne la valeur 1.
➢ Attente active consomme du temps CPU.
[Link],[Link] - SE 28
 CH.4 - Synchronisation de processus: Section critique
❑ Solution de Peterson
➢ Cette solution se base sur deux fonctions entrer_region et quitter_region.
➢ Chaque processus doit, avant d’entrer dans sa section critique appeler la fonction
entrer_region en lui fournissant en paramètre son numéro de processus.
➢ Cet appel le fera attendre si nécessaire jusqu’à ce qu’il n’y ait plus de risque.
➢ A la fin de la section critique, il doit appeler quitter_region pour indiquer qu’il quitte
sa section critique et pour autoriser l’accès aux autres processus.
void entrer_region(int process)
{
int autre ;
autre = 1 – process ; //l’autre processus
interesse[process] = TRUE ; //indiquer qu’on est intéressé
tour = process ;
while (tour == process && interesse[autre] ==TRUE) ;
}
void quitter_region (int process )
{
interesse[process] = false ;
}
Problème :
attente active = consommation du temps CPU

[Link],[Link] - SE 29
 CH.4 - Synchronisation de processus: Section critique
❑ L’instruction Test and Set Lock (TSL)
➢ L’instruction Test and Set Lock « int TSL (int b) » exécute de manière indivisible les opérations
suivantes :
✓ récupère la valeur de b,
✓affecte la valeur 1 à b et
✓ retourne l’ancienne valeur de b.
➢ Lorsqu’un processeur exécute l’instruction TSL, il verrouille le bus de données pour
empêcher les autres processus d’accéder à la mémoire pendant la durée de l’exécution.
➢ Cette instruction peut être utilisée pour établir et supprimer des verrous
(assurer l’exclusion mutuelle).

✓Valeur initiale de verrou est 0.

✓entrer_region :
while(TSL(verrou) ) ;
✓ quitter_region :
verrou =0;

Problèmes:
➢ attente active = consommation du temps CPU
➢ Inversion de priorité

[Link],[Link] - SE 30
 CH.4 - Synchronisation de processus: Section critique
❑ Les primitives SLEEP et WAKEUP
➢ SLEEP est un appel système qui suspend l’appelant en attendant qu’un autre le réveille.
➢ WAKEUP(process) : est un appel système qui réveille le processus process.
➢ Un processus H qui veut entrer dans sa section critique est suspendu si un autre processus
B est déjà dans sa section critique.
➢ Le processus H sera réveillé par le processus B, lorsqu’il quitte la section critique.

Problèmes
➢ Les tests et les mises à jour des conditions d’entrée en section critique ne sont pas
exécutés en exclusion mutuelle.
➢ Si le signal émis par WAKEUP(P1) arrive avant que P1 ne soit endormi, P1 pourra
dormir pour toujours.
verrou = 0;
Processus P0 Processus P1
{ {
if(verrou ==1) SLEEP(); if (verrou ==0) SLEEP();
verrou = 0; verrou= 1;
section_critique_P0( ); section_critique_P1( );
verrou = 1; verrou= 0;
WAKEUP(P1) ; WAKEUP(P0) ;
…. ….
} }
[Link],[Link] - SE 31
 CH.4 - Synchronisation de processus: Section critique

❑ Résumé des problèmes

➢ Attentes actives consommation du temps CPU.

➢ Masquage des interruptions dangereuse pour le système.

➢ TSL attente active + inversion des priorités => boucle infinie.

➢ SLEEP et WAKEUP synchronisation des signaux

[Link],[Link] - SE 32
 CH.4 - Synchronisation de processus: Section critique
❑ Sémaphores
➢ Pour contrôler les accès à un objet partagé, E. W. Dijkstra (1965) suggéra
l’emploi d’un nouveau type de variables appelées sémaphores.

➢ Un sémaphore est un compteur entier qui désigne le nombre d’autorisations d’accès

disponibles.

➢ Chaque sémaphore a un nom et une valeur initiale.

➢ Les sémaphores sont manipulés au moyen des opérations :

✓ P (désigné aussi par down ou wait) et
✓ V (désigné aussi par up ou signal).
S = (val, (liste de processus))
S_R = (3, liste_vide) (-4, (P1, P2, P3, P4))
Ressource R 4 processus en attente
I1 I2 I3 disponibles Plus d’instances disponibles

[Link],[Link] - SE 33
 CH.4 - Synchronisation de processus: Section critique
❑ Sémaphores
Init
[Link] := nombre d’instances de
ressources existantes
Problème de la SC

Prendre Semaphore S = 1 ;

[Link] := [Link] - 1; Processus P1 : Processus P2 :

Si [Link] < 0 then { {
Placer le processus dans la liste [Link]; P(S) P(S)
Le commuter à l’état en attente Section_critique _de_P1() ; Section_critique_de_P2();
V(S) ; V(S) ;
Vendre } }

[Link] := [Link] + 1;
Si [Link] <= 0 then
Sélectionner un processus de S. liste;
Le supprimer de S. liste;
Le commuter à l’état prêt;

➢ Chacune de ces deux opérations doit être implémentée comme une opération indivisible.
[Link],[Link] - SE 34
 CH.4 - Synchronisation de processus: Section critique
❑ Modélisation de la précédence et du rendez-vous

➢ Les sémaphores permettent de modéliser la précédence:

P1 P2 s’écrira, à l’aide d’un sémaphore S initialisé à 0
Semaphore S;

P1 P2

Corps P(S)

V(S) Corps

➢ Le rendez vous s’écrira à l’aide de deux sémaphores S1 et S2 initialisés à 0

Semaphore S;

P1 P2

V(S1) V(S2)

P(S2) P(S1)
[Link],[Link] - SE 35
 CH.4 - Synchronisation de processus: Section critique
❑ Problème du producteur/consommateur

Deux processus partagent une mémoire tampon de taille fixe N. L’un d’entre eux,
le producteur, dépose des informations dans le tampon, et l’autre, le consommateur,
les retire.

Producteur : Consommateur :
{ {
ip =0; ic =0;
Répeter Répéter
{ S’il y a, au moins, une entrée libre dans le tampon { S’il y a, au moins, une entrée occupée dans le tampon
alors produire(tampon, ip); ip = Mod(ip +1,N); alors consommer(tampon,ic); ic= Mod(ic+1, N);
sinon attendre jusqu’à ce qu’une entrée se libère sinon attendre jusqu’à ce qu’une entrée devienne occupée
} tantque vrai } tantque vrai
} }

[Link],[Link] - SE 36
 CH.4 - Synchronisation de processus: Section critique
❑Problème du producteur/consommateur

➢ La solution du problème au moyen des sémaphores nécessite deux

sémaphores.

➢ Le premier, nommé occupe, compte le nombre d’emplacements

occupés. Il est initialisé à 0.

➢ Il sert à bloquer/débloquer le consommateur (P(occupe) et

V(occupe)).

➢ Le second, nommé libre, compte le nombre d’emplacements libres.

Il est initialisé à N (N est la taille du tampon).

➢ Il sert à bloquer/débloquer le producteur (P(libre) et V(libre)).

[Link],[Link] - SE 37
 CH.4 - Synchronisation de processus: Section critique
❑ Problème du producteur/consommateur

tampon [N];

Producteur : Consommateur :
{ {
int ip =0; int ic =0;
Répeter Répéter
{ {
P(libre) ; P(occupe);
produire(tampon, ip); consommer(tampon,ic);
ip = Mod(ip +1,N); ic= Mod(ic+1, N);
V(occupe); V(libre);
} tantque vrai } tantque vrai
} }

[Link],[Link] - SE 38
 CH.4 - Synchronisation de processus: Section critique
❑ Problème des philosophes

➢ Cinq philosophes sont assis autour d’une table. Sur la table, il y a alternativement 5
plats de spaghettis et 5 fourchettes.

➢ Un philosophe passe son temps à manger et à penser.

➢ Pour manger son plat de spaghettis, un philosophe a besoin de deux fourchettes qui
sont de part et d’autre de son plat.

➢ Si tous les philosophes prennent en même temps, chacun une fourchette, aucun
d’entre eux ne pourra prendre l’autre fourchette (situation d’interblocage).

➢ Pour éviter cette situation, un philosophe ne prend jamais une seule fourchette.

➢ Les fourchettes sont les objets partagés. L’accès et l’utilisation d’une fourchette doit
se faire en exclusion mutuelle. On utilisera le sémaphore mutex pour réaliser
l’exclusion mutuelle

[Link],[Link] - SE 39
 CH.4 - Synchronisation de processus: Section critique
❑Problème des philosophes

[Link],[Link] - SE 40
 CH.4 - Synchronisation de processus: Section critique
❑ Problème des philosophes
philosophe( i in [0,4])
{
Répéter
{
penser(); // procedure qui vérifie si le philosophe i peut manger
// tenter de manger void Test(int i)
P(mutex) ; {
Etat[i]=faim ; if( (Etat[i] == faim) && ( Etat[G(i)] != manger)
Test(i); && (Etat[D(i)] !=manger) )
V(mutex) ; {
P(S[i]) ; Etat[i] = manger ;
manger(); V(S[i]) ;
// libérer les fourchettes }
P(mutex) ; }
Etat[i] = penser ;
// vérifier si ses voisins peuvent manger
Test(G(i)) ;
Test(D(i)) ;
V(mutex) ;
}
}
[Link],[Link] - SE 41
 CH.4 - Synchronisation de processus: Section critique
❑ Problème des Lecteurs / Rédacteurs

➢ Ce problème modélise les accès à une base de données. Plusieurs

processus tentent constamment d’accéder à la base de données soit pour
écrire, soit pour lire des informations.

➢ Pour assurer une certaine cohérence des données de la base, il faut

interdire l’accès (en lecture et en écriture) à tous les processus, si un autre
processus est en train de modifier la base (accède à la base en mode
écriture).

➢ Par contre, plusieurs processus peuvent accéder à la base, en même

temps, en mode lecture.

➢ Les rédacteurs représentent les processus qui demandent des accès en

écriture à la base de données.

➢ Les lecteurs représentent les processus qui demandent des accès en

lecture à la base de données.
[Link],[Link] - SE 42
 CH.4 - Synchronisation de processus: Section critique
❑ Problème des Lecteurs / Rédacteurs

➢ Pour contrôler les accès à la base, on a besoin de connaître le nombre de

lecteurs qui sont en train de lire de la base (NbL).

➢ Le compteur NbL est un objet partagé par tous les lecteurs. L’accès à ce
compteur doit être exclusif (sémaphore mutex).

➢ Un lecteur peut accéder à la base, s’il y a déjà un lecteur qui accède à la

base (NbL>0) ou aucun rédacteur n’est en train d’utiliser la base.

➢ Un rédacteur peut accéder à la base, si elle n’est pas utilisée par les autres
(un accès exclusif à la base). Pour assurer cet accès exclusif, on utilise un
autre sémaphore (Redact).

[Link],[Link] - SE 43
 CH.4 - Synchronisation de processus: Section critique

❑ Moniteur : Qu’est ce qu’un moniteur ?

➢ Moniteur = { variables globales + sections critiques d’un même problème}

➢ Pour assurer l’exclusion mutuelle, à tout moment un processus au plus est

actif dans le moniteur.

➢ Si un processus est actif dans le moniteur et un autre demande à y accéder

(appel une procédure du moniteur), ce dernier est mis en attente.

➢ C’est le compilateur qui se charge de cette tâche. Pour ce faire, il rajoute au

moniteur le code nécessaire pour assurer l’exclusion mutuelle.

➢ Cette solution est plus simple que les sémaphores et les compteurs
d’événements, puisque le programmeur n’a pas à se préoccuper de contrôler
les accès aux sections critiques.

[Link],[Link] - SE 44
 CH.4 - Synchronisation de processus: Section critique
❑ Moniteur : Risque d’interblocage

➢ Le processus actif dans le moniteur a besoin d’une ressource détenue par

un autre en attente du moniteur.

➢ Pour éviter des situations d’interblocage, il faut trouver un moyen

permettant à un processus actif à l’intérieur d’un moniteur de se suspendre
pour laisser place à un autre.

Exemple : Producteur/consommateur

➢ Le consommateur est actif dans le moniteur et le tampon est vide

⇒il devrait se mettre en attente et laisser place au producteur.

➢ Le producteur est actif dans le moniteur et le tampon est plein

=> il devrait se mettre en attente et laisser place au consommateur.

[Link],[Link] - SE 45
 CH.4 - Synchronisation de processus: Section critique
❑ Moniteur : Risque d’interblocage
Moniteur ProducteurConsommateur
{
int compteur =0, ic=0, ip=0 ;

void mettre (int objet) // section critique pour le dépôt

{
while (compteur==N);
tampon[ip] = objet ;
ip = (ip+1)%N ;
compteur++ ;
}

void retirer (int* objet) //section critique pour le retrait

{
while (compteur ==0) ;
objet = tampon[ic] ;
ic = (ic+1)%N ;
compteur -- ; Attente infinie dans le
} moniteur si le consommateur
accède en premier alors que
le tampon est vide.
}
Le producteur est en attente
[Link],[Link] - SE du moniteur. 46
 CH.4 - Synchronisation de processus: Section critique

❑ Moniteur : Variables de condition des moniteurs

➢ Une variable de condition est une variable booléenne manipulée au moyen de

deux opérations wait and signal.

➢ wait(x) :
✓ suspendre l’exécution du processus (thread) appelant (le mettre en attente de x);
✓ autoriser un autre processus en attente du moniteur à y entrer;

➢ signal(x) :
✓ débloquer un processus en attente de la condition x.

➢ Le processus débloqué est soit :

✓ mis dans la file d’attente du moniteur (signal and continue),
✓ activé dans le moniteur (signal and wait) => Le processus appelant est dans ce
cas mis en attente.

[Link],[Link] - SE 47
 CH.4 - Synchronisation de processus: Section critique
❑Moniteur : Exemple : Problème Producteur/consommateur

➢ Les sections critiques du problème du producteur et du consommateur sont

les opérations de dépôt et de retrait du tampon partagé.

➢ Un dépôt est possible uniquement si le tampon n’est pas plein. Pour

bloquer le producteur tant que le buffer est plein, il suffit d’utiliser une
variable de condition nplein et de précéder chaque opération de dépôt par
l’action wait(nplein), si le tampon est plein.

➢ L’action signal(nplein) sera appelée suite à un retrait d’un buffer plein.

➢ Un retrait est possible uniquement si le tampon n’est pas vide. Pour bloquer
le consommateur tant que le buffer est vide, il suffit d’utiliser une variable
de condition nvide et de précéder chaque opération de retrait par l’action
wait(nvide), si le tampon est vide.

➢ L’action signal(nvide) sera appelée par l’opération de dépôt dans le cas

d’un dépôt dans un buffer vide.
[Link],[Link] - SE 48
 CH.4 - Synchronisation de processus: Section critique
❑ Moniteur : Exemple : Problème Producteur/consommateur

Moniteur ProducteurConsommateur
{ boolc nplein, nvide ; //variable conditionnelle pour non plein et non vide
int compteur =0, ic=0, ip=0 ;

void mettre (int objet) // section critique pour le dépôt

{ //attendre jusqu’à ce que le tampon devienne non plein
if (compteur==N) wait(nplein) ;
tampon[ip] = objet ;
ip = (ip+1)%N ;
compteur++ ;
// si le tampon était vide, envoyer un signal pour réveiller le consommateur.
if (compteur==1) signal(nvide) ;
}

void retirer (int* objet) //section critique pour le retrait

{ if (compteur ==0) wait(nvide) ;
objet = tampon[ic] ;
ic = (ic+1)%N ;
compteur -- ;
// si le tampon était plein, envoyer un signal pour réveiller le producteur.
if(compteur==N-1) signal(nplein) ;
}
}
[Link],[Link] - SE 49
 CH.4 - Synchronisation de processus: Section critique
❑ Moniteur : Implémentation des moniteurs

➢ Une file d’attente pour mémoriser les demandes d’accès au moniteur

(file d’attente du moniteur).

➢ Une file d’attente pour chaque variable de condition (wait(x)).

➢ Éventuellement, une file d’attente des processus suspendus`dans le

moniteur suite à l’opération signal(x) (dans le cas de signal and wait).

➢ Si cette dernière file est gérée, elle est plus prioritaire que la file
d’attente du moniteur.

[Link],[Link] - SE 50
Données Type Mon_moniteur ;
partagées Var
n, p : integer;
Tab : array (1..10) of boolean;
Dispo : boolean;
n, p : integer;
Tab : array(1..10) of boolean;
Procedure P1;
Dispo : boolean;
end P1;
P1 F1(…) Ps(…) Function F1(q: integer);
Liens avec
End F1; l’extérieur
…
Procedure Ps (paramètre);

End Ps;
Opérations
Begin
Code d’initialisation --Initialisation :
Dispo := true;
N := 0; p := q;
Tab := (others =< false);
End Mon_moniteur;
Sans variables conditionnelles
[Link],[Link] - SE 51
 Type Mon_moniteur ;
Données Var
partagées x, y : condition;

x Procedure P1;
y Begin
If mauvaise condition then
[Link];
End if;
Accès aux objets partagés;
end P1;
Hypothèse
…
Signal terminal
Procedure Ps (paramètre);
Begin
Libération d’objets partagés;
Opérations [Link]; Sortie du moniteur
Code End Ps;
d’initialisation Begin
--Initialisation :
Dispo := true;
Avec variables conditionnelles N := 0; p := q;
Tab := (others =< false);
[Link],[Link] - SE 52
End Mon_moniteur;
 CH.4 - Synchronisation de processus: Section critique
❑ Moniteur : Implémentation des moniteurs au moyen de sémaphores

➢ Un sémaphore binaire mutex, initialisé à 1, pour assurer l’accès en

exclusion mutuelle au moniteur.
File du mutex = File d’attente du moniteur

➢ Pour chaque variable de condition x du moniteur,

– un sémaphore binaire x-sem initialisé à 0,
File de x-sem = File d’attente de x
– un compteur du nombre de processus en attente de x.

➢ Un sémaphore next, initialisé à 0, pour mémoriser tous les processus

qui ont cédé le moniteur à un autre processus (signal and wait).
File de next = File d’attente des processus suspendus

➢ Un compteur du nombre de processus suspendus à l’intérieur du

moniteur next_count.

[Link],[Link] - SE 53
 CH.5 - Interblocage
❑ Introduction
➢ L’exécution d’un processus nécessite un ensemble de ressources (espace
mémoire centrale, espace disque, fichier, périphériques, …) qui lui sont
attribuées par le système d’exploitation.

➢ Des problèmes peuvent survenir, si des processus détiennent des

ressources et en demandent d’autres qui sont déjà allouées.

Exemple:
➢ un processus Proc1 détient une ressource R1 et attend une autre ressource
R2 qui est utilisée par un autre processus Proc2 ;

➢ le processus Proc2 détient la ressource R2 et attend la ressource R1.

➢ On a une situation d’interblocage (Proc1 attend Proc2 et Proc2 attend

Proc1). Les deux processus vont attendre indéfiniment.

[Link],[Link] - SE 54
 CH.5 - Interblocage
❑ Introduction

P1 P2
Alloué

Demande

R1 R2

➢ Un ensemble de processus est en interblocage si chaque processus

attend la libération d’une ressource allouée à un autre appartenant à
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. Ils attendront
tous indéfiniment.

[Link],[Link] - SE 55
 CH.5 - Interblocage
❑ Conditions nécessaires pour interblocage (Coffman, Elphick et Shoshani)

➢ Exclusion mutuelle : une ressource est soit allouée à un seul processus,

soit disponible ;

➢ Détention et attente : les processus qui détiennent des ressources peuvent

en demander d’autres ;

➢ pas de réquisition : les ressources allouées à un processus sont libérées

uniquement par le processus (ressources non préemptives);

➢ Attente circulaire: un ensemble de processus attendant chacun une

ressource allouée à un autre.

[Link],[Link] - SE 56
 CH.5 - Interblocage
❑ Solutions au problème d’interblocage

➢ Les détecter et y remédier.

➢ Les éviter en allouant les ressources avec précaution. Si l’allocation d’une

ressource peut conduire à un interblocage, elle est retardée jusqu’à ce qu’il
n’y ait plus de risque.

➢ Les prévenir en empêchant l’apparition de l’une des quatre conditions

nécessaires à leur existence.

Remarque :
➢ En général, ce problème est ignoré par les systèmes d’exploitation car le
prix à payer pour les éviter ou les traiter est trop élevé pour des situations
qui se produisent rarement.

[Link],[Link] - SE 57
 CH.5 - Interblocage
❑ Solutions au problème d’interblocage: La détection et la reprise

➢ Dans ce cas, le système ne cherche pas à empêcher les interblocages. Il

tente de les détecter et d’y remédier.

➢ 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.

➢ Le système vérifie s’il y a des interblocages :

– A chaque modification du graphe suite à une demande d’une ressource
(coûteuse en termes de temps processeur).
– Périodiquement ou lorsque l’utilisation du processeur est inférieure à un
certain seuil (la détection peut être tardive).

[Link],[Link] - SE 58
 CH.5 - Interblocage
❑ Solutions au problème d’interblocage: La détection et la reprise

➢ Graphe d’allocation des ressources

✓ Le graphe d’allocation des ressources est un graphe biparti composé de
deux types de noeuds et d’un ensemble d’arcs :
o Les processus qui sont représentés par des cercles ;
o 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 ;
o Un arc orienté d’une ressource vers un processus signifie que la ressource est
allouée au processus.
o 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.

✓ La détection est réalisée en réduisant le graphe.

[Link],[Link] - SE 59
 R1 R2 R4 R1 R2 R4

P1 P2 P3 P1 P2 P3

R3 R3

R1 R2 R4

P1 P2 P3

R3
[Link],[Link] - SE 60
 CH.5 - Interblocage
La reprise des interblocages

➢ Lorsque le système détecte un interblocage, il doit le

supprimer, ce qui se traduit généralement par la réalisation de
l’une des opérations suivantes :

✓ Retirer temporairement une ressource à un processus pour

l’attribuer à un autre.

✓ Restaurer un état antérieur (retour arrière) et éviter de retomber

dans la même situation.

✓ Supprimer un ou plusieurs processus.

➢ La reprise n’est pas évidente.

[Link],[Link] - SE 61
 CH.5 - Interblocage
❑ L’évitement des interblocages

➢ Dans ce cas, lorsqu’un processus demande une ressource, le système doit

déterminer si l’attribution de la ressource est sûre (mènent vers un état sûr).

➢ 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 un ordre d’allocation de ressources qui permet à tous les processus
de se terminer).

➢ Il faut connaître à l’avance les besoins en ressources de chaque processus

(ce qui est en général impossible).

[Link],[Link] - SE 62
 CH.5 - Interblocage
❑ Déterminer si un état est sûr ou non : L’algorithme du banquier
➢ L‘état est caractérisé par quatre tableaux.

R1 R2 R3 R4

E= ( 4 2 3 1 )
[Link] un processus Pi non marqué dont la
A=( 2 1 0 0 )
rangée Pi de Req est inférieure ou égale à A ;
R1 R2 R3 R4
[Link] un tel processus n’existe pas alors l’état est
P1 0 0 1 0 non sûr. L’algorithme se termine.
Alloc= P2 2 0 0 1
P3 0 1 2 0 [Link], ajouter la rangée Pi de Alloc à A,
marquer le processus ;
R1 R2 R3 R4

P1 2 0 0 1
[Link] tous les processus sont marqués alors l’état
Req= P2 1 0 1 0 est sûr et l’algorithme se termine, sinon aller à
P3 2 1 0 0 l’étape 1.

• Alloc : ressources attribuées ;

• Req : ressources nécessaires non encore obtenues ;
• A : ressources disponibles ;
• E : ressources du système

[Link],[Link] - SE 63
 CH.5 - Interblocage
❑La prévention des interblocages
➢ Pour prévenir les interblocages, on doit faire de telle sorte que l’une des
quatre conditions nécessaires à leur existence ne soit jamais satisfaite.
➢ Pas d’exclusion mutuelle : impossible car certaines ressources sont
à usage exclusif.
➢ Pas de « détention et attente » : Il faudrait que toutes les ressources
nécessaires à un processus soient demandées et allouées à la fois. Le
processus ne doit pas détenir des ressources et en demander d’autres.
✓ Il est difficile de prévoir les besoins du processus
✓ Problème de famine.
➢ 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é.
➢ Pas d’attente circulaire, si on parvient à :
✓ Établir un ordre total entre les ressources et
✓ Imposer, à chaque processus, la règle de demande de ressources suivante :
Un processus peut demander une ressource Rj seulement
si toutes les ressources qu’il détient sont inférieures à Rj
[Link],[Link] - SE 64
 CH.6 - Ordonnancement de processus

❑ Les ordonnanceurs
➢ Les programmes lancés sont d’abord admis par le système qui se charge
d’en créer les processus nécessaires.
➢ Dans un système multiprogrammé, plusieurs processus peuvent être
présents en mémoire centrale.
➢ Le système d’exploitation décide de l’ordre et du moment de l’admission des
programmes en attente (ordonnanceur de haut niveau).
➢ Il gère également l’allocation du processeur aux différents processus à
exécuter (ordonnanceur de bas niveau).
➢ L’exécution d’un processus est une séquence alternée de calculs CPU
(rafales « burst ») et d’attentes d’événements (E/S, attente d’un
sémaphore..).
➢ Lorsque le processus en cours se bloque, le processeur est alloué à un autre

[Link],[Link] - SE 65
 CH.6 - Ordonnancement de processus
❑ Les ordonnanceurs
File d'attente

Processus Ordonnanceur Ressource

CPU Scheduler CPU

Device Scheduler

Périphériques
Device Scheduler

Device Scheduler

Table des processus Mean terme swapper

Job Scheduler Zone de Swap

[Link],[Link] - SE login 66
 CH.6 - Ordonnancement de processus
❑ Les ordonnanceurs

À un instant donné, le CPU n'exécute qu'un processus

• Les autres processus attendent
L'ordonnanceur partage le CPU par « quantum de temps » (en
anglais, timeslice)
• À la fin du timeslice, l’ordonnanceur préempte le processus
s’exécutant et choisit un autre processus

P P P P P P
Processus 2 1 1 2 1 1
P P P P P P
prêt 3 3 2 3 3 2

Processus
exécuté P1 P2 P3 P1 P2 P3

t
 CH.6 - Ordonnancement de processus
❑ Les ordonnanceurs

Entrées/sorties attente d'une ressource (disque, carte réseau,

écran, etc.)
Libération du CPU en attendant la ressource
Processus P P P
en attente 2 2 2

P P P P P
Processus 2 1 P P P 1 2 1
prêt P P 1 3 1 P P P
3 3 2 3 3

Processus
exécuté P1 P2 P3 P1 P3 P1 P2

t
 CH.6 - Ordonnancement de processus
❑ La commutation de contexte

➢ Pour accélérer la commutation, certains processeurs sont dotés de deux ou

plusieurs groupes de registres.

[Link],[Link] - SE 69
 CH.6 - Ordonnancement de processus
❑ La commutation de contexte
⬛ La commutation a lieu lors de l'élection d'un processus :
• Sauvegarde du contexte du processus évincé
• Chargement du contexte du processus élu
⬛ Contexte : ensemble des infos associées au processus
• Valeur des registres
• Informations mémoire (emplacement, etc.)
Restauration du
contexte
Processus P1 P2 P1
exécuté
Sauvegarde du
contexte
t

Mem

➢ Pour accélérer la commutation, certains processeurs sont dotés de deux ou

plusieurs groupes de registres.
 CH.6 - Ordonnancement de processus
❑ Objectifs de l’ordonnancement
1. Maximiser le nombre de processus exécutés par unité de temps.

2. Minimiser le temps d’attente d’exécution de chaque processus.

3. Maximiser les temps d’utilisation des processeurs et autres ressources.

4. Respecter les échéanciers (terminer l’exécution avant leurs deadlines).

5. Éviter le problème de famine (attente infinie).

6. Favoriser les processus les plus prioritaires (éviter le problème d’inversion des
priorités).

7. Minimiser le nombre et la durée des changements de contexte.

➢ Difficile de les satisfaire à la fois (exemple objectifs 1 et 4).

➢ Prioriser les objectifs.
[Link],[Link] - SE 71
 CH.6 - Ordonnancement de processus
❑ Politique d’ordonnancement
➢ Choix du processus à exécuter ?
✓ Premier arrivé, premier servi.
✓ Plus prioritaire (priorités statiques ou dynamiques).
✓ Plus court temps ….

➢ Le temps d’allocation du processeur au processus choisi :

✓ Allocation jusqu’à terminaison ou libération volontaire (ordonnanceur non
préemptifs).
✓ Temps d’allocation limité fixe ou variable (ordonnanceur préemptifs).

➢ Quand appeler l’ordonnanceur ?

✓ Le processus en cours se termine, se bloque ou cède le processeur,
✓ Le temps alloué a expiré.
✓ L’arrivée d’un processus plus prioritaire…

[Link],[Link] - SE 72
 CH.6 - Ordonnancement de processus
❑ Politique d’ordonnancement
➢ Ordonnanceurs non préemptifs

✓ Le système d’exploitation choisit le prochain processus à exécuter :

o Premier arrivé, Premier servi (FCFS, First-Come First-Served) ou
o Plus court d’abord (SPF, Short Process First ou SJF Short Job First).
o Plus prioritaire d’abord (ex: priorite = (temps d’attente + temps d’exécution) /
temps d’exécution).
✓ Il lui alloue le processeur jusqu’à ce qu’il se termine, se bloque (en
attente d’un événement) ou cède le processeur. Il n’y a pas de
réquisition.
✓Exemple:
Processus Arrivée Durée Priorité

P1 2 3 1
P2 0 4 3
P3 0 6 1
P4 1 2 2
[Link],[Link] - SE 73
P5 1 1 1
 CH.6 - Ordonnancement de processus
❑ Politique d’ordonnancement
➢ Ordonnanceurs 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 :
o poursuivre son exécution ou
o être suspendu pour laisser place à un autre.
✓ S’il décide de suspendre l’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 (commutation de contexte).
✓ Cette sauvegarde est nécessaire pour pouvoir poursuivre ultérieurement
l’exécution du processus suspendu.

[Link],[Link] - SE 74
 CH.6 - Ordonnancement de processus
❑ Politique d’ordonnancement
➢ Ordonnanceurs préemptifs

✓ Le processeur passe donc d’un processus à un autre en exécutant chaque

processus pendant quelques dizaines ou centaines de millisecondes.

✓ Le temps d’allocation du processeur au processus est appelé quantum.

✓ Cette commutation entre processus doit être rapide (temps nettement

inférieur au quantum).

✓ Le processeur, à un instant donné, n’exécute réellement qu’un seul

processus.

✓ Pendant une seconde, le processeur peut exécuter plusieurs processus et

donne ainsi l’impression de parallélisme (pseudo-parallélisme).

[Link],[Link] - SE 75
 CH.6 - Ordonnancement de processus
❑ Politique d’ordonnancement
➢ Ordonnanceurs préemptifs

✓ Shortest Remaining Time SRT (PCTER)

o Lorsqu’un processus arrive, l’ordonnanceur compare le temps estimé de

son exécution avec celle du processus actuellement en exécution
(version préemptive du SPF).
o Si ce temps est plus petit, on exécute immédiatement le nouveau
processus.
Processus Arrivée Durée Priorité

P1 2 3 1
P2 0 4 3
P3 0 6 1
P4 1 2 2
[Link],[Link] - SE P5 1 1 1 76
 CH.6 - Ordonnancement de processus
❑ Politique d’ordonnancement
➢ Ordonnanceurs préemptifs
✓ Ordonnancement circulaire (Tourniquet ou round robin)
o Algorithme ancien, simple, fiable et très utilisé.
o Il mémorise dans une file (FIFO : First In First Out), la liste des
processus en attente d’exécution (prêts).
o Algorithme équitable mais sensible au choix du quantum.
o Un quantum trop petit provoque trop de commutations de processus et abaisse
l’efficacité du processeur.
o Un quantum trop élevé augmente le temps de réponse des courtes commandes
en mode interactif.
Processus Arrivée Durée Priorité

P1 2 3 1
P2 0 4 3
P3 0 6 1
P4 1 2 2
[Link],[Link] - SE P5 1 1 1 77
 CH.6 - Ordonnancement de processus
❑ Politique d’ordonnancement
➢ Ordonnanceurs préemptifs
✓ Ordonnanceur à priorité avec files multiples

o Il attribue une priorité à chaque processus (statique ou dynamique).

o Les processus de même priorité sont dans une file FIFO
o Il y a autant de files qu’il y a de niveaux de priorité
o Les processus de chaque file sont ordonnancés selon l’algorithme du
tourniquet (Round Robin avec un quantum variable ou fixe) ou FCFS.
Problèmes
o Équité : L’exécution des processus moins prioritaires peut
être constamment retardée par l’arrivée de processus plus
prioritaires.
o Inversion des priorités :
❖ un processus moins prioritaire détient une ressource nécessaire
à l’exécution d’un processus plus prioritaire.
❖ Le processus moins prioritaire ne peut pas s’exécuter car il y a
constamment des processus actifs plus prioritaires.
[Link],[Link] - SE 78
 CH.6 - Ordonnancement de processus
❑ Politique d’ordonnancement
➢ Ordonnanceurs préemptifs
✓ Ordonnanceur à priorité avec files multiples
o Pour empêcher les processus de priorité élevée de s’exécuter indéfiniment,
l’ordonnanceur diminue régulièrement la priorité du processus en cours
d’exécution (priorité dynamique) et augmente progressivement celles des
processus en attente.
o La priorité du processus en cours est comparée régulièrement à celle du
processus prêt le plus prioritaire (en tête de file). Lorsqu’elle devient
inférieure, la commutation a lieu.
o Dans ce cas, le processus suspendu est inséré en queue de file
correspondant à sa nouvelle priorité.
o Pour favoriser les processus qui font beaucoup d’E/S, ils doivent acquérir le
processeur dès qu’ils le demandent, afin de leur permettre de lancer leurs
requêtes suivantes d’E/S.
o Pour éviter qu’il y ait beaucoup de commutations pour les processus
consommateurs de temps CPU, il est préférable d’allouer un plus grand
quantum à ces processus (quantum variable).
[Link],[Link] - SE 79
 CH.7 Gestion de la mémoire vive
❑ Généralités
➢ L’espace d’adressage d’un processus est généré par le compilateur et l’éditeur de liens.

[Link],[Link] - SE 80
 CH.7 Gestion de la mémoire vive
❑ Généralités
➢ L’espace d’adressage d’un processus est généré par le compilateur et l’éditeur de liens.

Édition de liens +
Compilation Chargement

Programme
Programme

Programme
exécutable
source

objet
Adresses abstraites Adresses Adresses
x, n, p... translatables physiques

adresse de base
du programme
Calcul d’adresses

[Link],[Link] - SE adresse + adresse 81

relative physique
 CH.7 Gestion de la mémoire vive
❑ Généralités
➢ Rôle du gestionnaire de la mémoire
Le gestionnaire de la mémoire est le composant du système d’exploitation qui se charge de
gérer l’allocation d’espace mémoire aux processus à exécuter :

✓ Comment organiser la mémoire ? (une ou plusieurs partitions, le nombre et la taille des partitions fixes ou
variables au cours du temps).

✓ Faut-il allouer une zone contiguë à chaque processus à charger en mémoire ? Faut-il allouer tout l’espace
nécessaire à l’exécution du processus entier ? (politique d’allocation).

✓ Comment mémoriser l’état de la mémoire? Parmi les parties libres en mémoire, lesquelles allouées au
processus? (politique de placement)

✓ S’il n’y a pas assez d’espace en mémoire, doit-on libérer de l’espace en retirant des parties ou des
processus entiers? Si oui lesquels ? (politique de remplacement).

✓ Les adresses figurant dans les instructions sont-elles relatives? Si oui, comment les convertir en adresses
physiques.

✓ Si plusieurs processus peuvent être résident en mémoire, comment assurer la protection des processus
(éviter qu’un processus soit altéré par un autre?
[Link],[Link] - SE 82
 CH.7 Gestion de la mémoire vive
❑ Généralités
➢ Exigences

✓ Efficacité : la mémoire doit être allouée équitablement et à moindre coût

tout en assurant une meilleure utilisation des ressources (mémoire,
processeurs et disque).

✓ Protection : Les processus ne peuvent pas se corrompre.

✓ Transparence : Chacun des processus doit ignorer l’existence des autres

en mémoire.

✓ Relocation : la possibilité de déplacer un processus en mémoire (lui

changer de place).

[Link],[Link] - SE 83
 CH.7 Gestion de la mémoire vive
❑ Partitionnement de la mémoire
➢ Partitions fixes

✓ La mémoire réservée aux utilisateurs est divisée en un ensemble de partitions.

✓ Le nombre et la taille des partitions sont fixés à l'avance (lors du chargement

du système).

✓ Les partitions peuvent être égales ou non.

✓ La choix du nombre et de la taille des partitions dépend du niveau de

multiprogrammation voulu.

✓ On peut avoir une file par partition ou une file globale.

✓ L’unité d’allocation est une partition.

[Link],[Link] - SE 84
 CH.7 Gestion de la mémoire vive
❑ Partitionnement de la mémoire
➢ Partitions variables

✓ Initialement, l’espace mémoire réservée aux utilisateurs constitue une seule

partition.

✓ Quand un nouveau processus doit être chargé, on lui alloue une zone contiguë
de taille suffisamment grande pour le contenir.

✓ Le nombre et les tailles des partitions varient au cours du temps.

✓ Cette forme d'allocation conduit éventuellement à l'apparition de trous trop

petits pour les allouer à d’autres processus : c'est la fragmentation externe

✓ Solutions:
– Compactage (coûteux et exige que les processus soient relocalisables)
– Allocation discontinue.

[Link],[Link] - SE 85
 CH.7 Gestion de la mémoire vive
❑ Etat de la mémoire

Pour gérer l'allocation et la libération de l'espace mémoire, le gestionnaire

doit :

➢ Connaître l'état de la mémoire :

✓ Tables de bits,
✓ Listes chaînées.

➢ Avoir une politique de placement et de récupération d’espace.

✓ Premier ajustement
✓ Meilleur ajustement
✓ Pire ajustement
✓ Par subdivision

[Link],[Link] - SE 86
 CH.7 Gestion de la mémoire vive
❑ Mémoire virtuelle

➢ Le but de la mémoire virtuelle est de permettre l’exécution de programmes

dont la taille excède celle de la mémoire réelle.

➢ Il y a deux types d’adresses dans les systèmes implantant la mémoire

virtuelle :
✓ Celles référencées par les processus (adresses virtuelles ou logiques),
✓ Celles de la mémoire physique (adresses physiques ou réelles).

➢ L’espace d’adressage virtuel d’un processus =

{ adresses virtuelles que le processus peut référencer}

➢ Sa taille maximale dépend de l’organisation de l’espace virtuel (>> à celle

de la mémoire physique).

[Link],[Link] - SE 87
 CH.7 Gestion de la mémoire vive
❑ Mémoire virtuelle

➢ D’une manière générale, l’espace d’adressage est structuré en blocs de :

✓ mêmes tailles (pages-> pagination) ou

✓ tailles différentes (segments->segmentation).

➢ Les deux organisations peuvent être combinées : segment = {pages}

➢ Le format de l’adresse virtuelle est :

✓ (numéro de page, déplacement dans la page) pour la pagination;

✓ (numéro de segment, déplacement dans le segment) pour la segmentation;
✓ (numéro de segment, numéro de page, déplacement dans la page) pour la
segmentation/pagination.

[Link],[Link] - SE 88
 CH.7 Gestion de la mémoire vive
❑ Mémoire virtuelle

➢ supposons que l’adresse virtuelle (b, d) est sur 32 bits, n bits pour d :
✓ Le nombre maximal de blocs que peut contenir l’espace virtuel : 232-n
✓ La taille maximale d’un bloc : 2n
n => fragmentation interne et table des blocs

n => fragmentation interne et table des blocs

➢ La table des blocs d’un processus indique quels sont les blocs en mémoire. Elle
contient une entrée pour chaque bloc de l’espace virtuel du processus.
(bit de présence, adresse physique du début du bloc, ….).
➢ L’adresse de la table des blocs fait partie du contexte du processus à sauver ou
à restaurer lors du changement de contexte (un registre).

[Link],[Link] - SE 89
 CH.7 Gestion de la mémoire vive
❑ Mémoire virtuelle
Processeur

Espace d’adressage logique

Unité de gestion
de la mémoire

Ram Disque

[Link],[Link] - SE 90
 CH.7 Gestion de la mémoire vive
❑ Mémoire virtuelle
➢La pagination pure

✓ La mémoire virtuelle et la mémoire physique sont structurées en unités

d’allocations (pages pour la mémoire virtuelle et cases pour la mémoire physique).

✓ La taille d’une page est fixe et égale à celle d’une case. Elle varie entre 512 octets
et 8 Ko.

✓ Il n’y a pas de fragmentation externe car toutes les pages sont de même taille.

✓ Par contre, il peut y avoir une fragmentation interne si la dernière page de

l’espace d’adressage logique n’est pas pleine.

[Link],[Link] - SE 91
 CH.7 Gestion de la mémoire vive
❑ Mémoire virtuelle
➢La pagination pure

0
t p. 0
t-1 d=0 kt
t d=1 kt + 1
t p. 1 d
d=2 kt + 2
2t-1 . .
2t kt + d
. .
t p. 2 . .
3t-1 .
.
3t . .
t p. 3
4t-1
d = t-1 (k+1)t -1

kt
t p. k Page k
(k+1)t-1
[Link],[Link] - SE 92
 CH.7 Gestion de la mémoire vive
❑ Mémoire virtuelle
➢La pagination pure: Conversion d’adresses virtuelles
✓ Adresse virtuelle = (numéro de page, déplacement dans la page).
✓ Les adresses virtuelles référencées par l’instruction en cours d’exécution doivent
être converties en adresses physiques.
✓ La correspondance entre les pages et les cases est mémorisée dans une table
appelée table des pages. Le nombre d’entrées dans la table est égal au nombre
de pages virtuelles.
✓ La table des pages d’un processus doit être (en totalité ou en partie) en
mémoire centrale lors de l’exécution du processus. Elle est nécessaire pour la
conversion des adresses virtuelles en adresses physiques.
✓ Chaque entrée de la table des pages est composée de plusieurs champs,
notamment :
o Le bit de présence
o Le bit de référence (R)
o Les bits de protection
o Le bit de modification (M)
o Le numéro de case correspondant à la page
o son emplacement
[Link],[Link] - SEsur disque 93
 CH.7 Gestion de la mémoire vive
❑ Mémoire virtuelle
➢La pagination pure: Conversion d’adresses virtuelles
adresse
adresse
physique P
logique L
Processus x d y d

x y

Table des pages

[Link],[Link] - SE Mémoire physique 94
 CH.7 Gestion de la mémoire vive
❑ Mémoire virtuelle adresse valeur
➢La pagination pure: Conversion d’adresses virtuelles 0 Cadre 0

adresse valeur 4 Cadre 1

0 a e
8
Page 0 1 b f Cadre 2
2 c g
3 d 0 5 h
4 e 12 i Cadre 3
Page 1 1 2 j
5 f k
6 g 2 l
3 16
7 h Cadre 4
8 i 3 7
Page 2 9 j 20 a Cadre 5
10 k b
Table des pages c
11 l d
12 m 24
n Cadre 6
Page 3 13
14 o
28 m Cadre 7
15 p n
[Link],[Link] - SE Mémoire logique o 90
95
p
Mémoire physique
 CH.7 Gestion de la mémoire vive
❑ Mémoire virtuelle
➢La pagination pure: Conversion d’adresses virtuelles

Table des pages à plusieurs niveaux

✓ La taille de la table des pages peut être très grande (ex: pour un adressage virtuel sur 32 bits et des pages de 4 Ko).

✓ Pour éviter d’avoir des tables trop grandes en mémoire, de nombreux ordinateurs utilisent des tables
des pages à plusieurs niveaux.

✓ Par exemple, une table des pages à deux niveaux, pour un adressage sur 32 bits et des pages de 4 Ko,
est composée combien de tables de 1024 entrées ?

✓ Dans ce cas, une adresse virtuelle de 32 bits est composée de trois champs :

– un pointeur sur la table du 1er niveau ,

– un pointeur sur une table du 2nd niveau et
– un déplacement dans la page .

[Link],[Link] - SE 96
 CH.7 Gestion de la mémoire vive
❑ Mémoire virtuelle
➢La pagination pure: Conversion d’adresses virtuelles

Page de la table
des pages
Page kt -1 C 0
Page t-1 C1
0 75 P1 P2 d
…
t-1 1
Page 0 C 75
t 100
p1
.. 900
. 2t-1
p2
Page t C 100

(k-1)t 904 Table des pages d

Table des externe
kt -1 Page de la
pages externe 0
Page 2t-1 C 900
table des pages
Table des pages
Page (k-1) C 904
(kt pages) Page désirée
[Link],[Link] - SE 97
 CH.7 Gestion de la mémoire vive
❑ Mémoire virtuelle
➢La pagination pure: Conversion d’adresses virtuelles

✓ Cette conversion d’adresse est effectuée par un composant matériel du processeur

le MMU : Memory Management Unit (MMU).

✓ Le MMU vérifie si l’adresse virtuelle reçue correspond à une adresse en mémoire

physique (en consultant la table des pages).

✓ Si c’est le cas, le MMU transmet sur le bus de la mémoire l’adresse réelle,

sinon il y a un défaut de page.

✓ Un défaut de page provoque un déroutement (trap) dont le rôle est de ramener

à partir du disque la page manquante référencée (l’unité de transfert est la page).

[Link],[Link] - SE 98
 CH.7 Gestion de la mémoire vive
❑ Mémoire virtuelle : défaut de page

SE
3

2
1

Charge M i
6

Table des pages

Cadre de page
libre 4
5

[Link],[Link] - SE 99
Mémoire physique
 CH.7 Gestion de la mémoire vive
❑ Mémoire virtuelle
➢Algorithme de remplacement de page

✓ A la suite d’un défaut de page, le système d’exploitation doit ramener en

mémoire la page manquante à partir du disque.
✓ S’il n’y a pas de cases libres en mémoire, il doit retirer une page de la mémoire
pour la remplacer par celle demandée.
✓ Si la page à retirer a été modifiée depuis son chargement en mémoire, il faut la
réécrire sur le disque.
✓ Quelle est la page à retirer de manière à minimiser le nombre de défauts de
page ?
o Le choix de la page à retirer peut se limiter aux pages du processus qui a
provoqué le défaut de page (allocation locale) ou à l’ensemble des pages en
mémoire (allocation globale).
o En général, l’allocation globale produit de meilleurs résultats que l’allocation
locale.
✓ Ces algorithmes mémorisent les références passées aux pages. Le choix de la
page à retirer dépend des références passées.
[Link],[Link] - SE 100
 CH.7 Gestion de la mémoire vive
❑ Mémoire virtuelle : remplacement de page

Cadre Bit
valide/invalide
de page

1
12 5 v/ i 2
Cadre 5 victime 12

84 5 i/ v 4
3

84
Table des pages

[Link],[Link] - SE 101
Mémoire physique
 CH.7 Gestion de la mémoire vive
❑ Mémoire virtuelle
➢Algorithme de remplacement de page
✓ Algorithme aléatoire

o Critère : choisir au hasard une page victime (à retirer de la mémoire)

o Facile

o Version locale et globale

o Utilisé pour des comparaisons entre méthodes

[Link],[Link] - SE 102
 CH.7 Gestion de la mémoire vive
❑ Mémoire virtuelle
➢Algorithme de remplacement de page
✓ Algorithme optimal (BELADY) : OPT

o Critère : remplacer la page qui sera référencée le plus tard possible dans le futur
o Irréalisable
o Version locale et globale
o Intérêt pour faire des études analytiques comparatives
Exemple 1 avec 3 cadres

[Link],[Link] - SE 103
 CH.7 Gestion de la mémoire vive
❑ Mémoire virtuelle
➢Algorithme de remplacement de page
✓ Algorithme FIFO
o Critère : la page dont le temps de résidence est le plus long
o Implémentation facile :
❖ pages résidentes en ordre FIFO –› on expulse la première
o Ce n’est pas une bonne stratégie :
❖ Son critère n’est pas fondé sur l’utilisation de la page
o Anomalie de Belady
❖ On peut rencontrer des exemples où en augmentant le nombre de
cadres on augmente le nombre de défauts de page au lieu de le
diminuer.

[Link],[Link] - SE 104
 CH.7 Gestion de la mémoire vive
❑ Mémoire virtuelle
➢Algorithme de remplacement de page
✓ Algorithme FIFO : Anomalie de Belady

[Link],[Link] - SE 105
 CH.7 Gestion de la mémoire vive
❑ Mémoire virtuelle
➢Algorithme de remplacement de page
✓ Algorithme LRU
o Critère : page résidente la moins récemment utilisée

o Basé sur le principe de localité : une page a tendance à être réutilisée dans
un futur proche.

o Difficile à implémenter sans support matériel

Exemple avec 3 cadres

[Link],[Link] - SE 106
 CH.7 Gestion de la mémoire vive

❑ Mémoire virtuelle
➢Segmentation/pagination

✓ Dans un système paginé, l’espace d’adressage virtuel d’un processus est à une
dimension.

✓ Or en général, un processus est composé d’un ensemble d’unités logiques :

o les différents codes : le programme principal, les procédures, les
fonctions bibliothèques ;
o Les données ;
o Les piles d’exécution.

✓ On peut associer à chaque unité logique un espace

d’adressage (un segment).

[Link],[Link] - SE 107
 CH.7 Gestion de la mémoire vive
❑ Mémoire virtuelle

➢Segmentation/pagination

✓ L’espace d’adressage d’un processus est composé d’un ensemble de segments.

Ces segments sont de tailles différentes .

✓ La segmentation facilite l’édition de liens, le partage entre processus de segments

de données ou de codes.

✓ La segmentation peut être combinée avec la pagination : Chaque segment est

composé d’un ensemble de pages.

✓ Les adresses virtuelles sont des triplets :

(numéro du segment, numéro de page, déplacement dans la page)

[Link],[Link] - SE 108
 CH.8 Système de fichier
❑ Qu’est ce qu’un système de fichier ?
➢ Un système de fichiers est la partie du système d’exploitation qui se charge
de gérer le stockage et la manipulation de fichiers (sur une unité de stockage :
partition, disque, CD, disquette).

➢ Avant qu’un système de fichiers puisse créer et gérer des fichiers sur une
unité de stockage, son unité doit être formatée selon les spécificités du système
de fichiers.

➢ Le formatage inspecte les secteurs, efface les données et crée le répertoire

racine du système de fichiers.

➢ Il crée également un superbloc pour stocker les informations nécessaires à

assurer l’intégrité du système de fichiers.

[Link],[Link] - SE 109
 CH.8 Système de fichier
❑ Qu’est ce qu’un système de fichier ?
➢ Un superbloc contient notamment :

✓ L’identifiant du système de fichiers (C:, D : ..)

✓ Le nombre de blocs dans le système de fichiers.

✓ La liste des blocs libres.

✓ L’emplacement du répertoire racine.

✓ La date et l’heure de la dernière modification du système de fichiers.

✓ Une information indiquant s’il faut tester l’intégrité du système de fichiers.

[Link],[Link] - SE 110
 CH.8 Système de fichier
❑ Qu’est ce qu’un fichier ?
➢ Un fichier désigne un ensemble de données manipulées comme une seule unité.

➢ Il a un ensemble d’attributs qui peuvent être regroupés en deux catégories :

✓ Les attributs qui servent à contrôler les accès (code de protection, mot de passe,
propriétaire …).
✓ Les attributs qui définissent le type et l’état courant du fichier (indicateur du
type ASCII/binaire, taille courante, location, date de création, date de la dernière
modification, …).

➢ Dans un système, il existe plusieurs types de fichiers :

✓ Les fichiers ordinaires (ASCII ou binaires).
✓ Les répertoires sont des fichiers système qui maintiennent la structure du
système de fichiers.
✓ Les fichiers spéciaux caractère sont liés aux E/S et permettent de modéliser les
périphériques d’E/S série tels que les terminaux, les imprimantes et les réseaux.
✓ Les fichiers spéciaux bloc modélisent les disques, les disquettes...
[Link],[Link] - SE 111
 CH.8 Système de fichier
❑ Qu’est ce qu’un fichier ?
➢ Modes d’accès

Accès séquentiel
Articles accessibles

Article pointé

Accès relatif ou indexé

Articles accessibles

[Link],[Link] - SE Article pointé 112

 CH.8 Système de fichier
❑ Répertoire de fichiers
➢ Les systèmes de fichiers organisent leurs fichiers dans des répertoires.

➢ Chaque répertoire comporte des fichiers et éventuellement des sous répertoires.

➢ Chaque système de fichier a un répertoire racine (/, C:, E:).

➢ Chaque processus a un répertoire de travail désigné par « . »

➢ Le répertoire père est désigné par « ..»

➢ La référence à un fichier indique le chemin d’accès au fichier :

✓ Chemin d’accès relatif
✓ Chemin d’accès absolu

[Link],[Link] - SE 113
 CH.8 Système de fichier
❑ Stockage des fichiers
➢ Chaque fichier (ordinaire ou répertoire) d’un système de fichiers est stocké
sur l’unité de stockage du système de fichiers. Ses données sont dans des
blocs de taille fixe (512, 1024, ou 2048 octets, …).
➢ À chaque fichier est alloué un nombre de blocs. Le bloc est l’unité
d’allocation => fragmentation interne
➢ La lecture ou l’écriture d’un élément d’un fichier impliquera le transfert vers
la mémoire du bloc entier qui contient cet élément.
➢ Le système de fichiers conserve, dans un ou plusieurs blocs spécifiques
(superblocs), un certain nombre d’informations telles que le nombre de ses
blocs, leur taille, la liste des blocs libres….
➢ Pour pouvoir récupérer l’état des blocs (libre ou alloué), les systèmes de
fichiers maintiennent :
✓ une liste chaînée des blocs libres ou
✓ une table de bits contenant un bit pour chaque bloc (0 pour libre).
➢ Les blocs d’un même fichier sont contiguës ou non contiguës

[Link],[Link] - SE 114
 CH.8 Système de fichier
❑ Stockage des fichiers
➢Structure des disques

Têtes de Axe
• Accès: lecture/écriture
Secteur ou bloc
– Positionnement
des têtes sur le bon Piste
cylindre
– Rotation pour
atteindre le bon
secteur
– Transfert des
informations

Plateau

[Link],[Link] - SE 115
 CH.8 Système de fichier
❑ Stockage des fichiers

➢Temps d’accès

Temps de latence
+
Temps de recherche
+
Temps de transfert

[Link],[Link] - SE 116
 CH.8 Système de fichier
❑ Stockage des fichiers

➢Transfert d’un bloc

pilote
1 0 1 2 3
4 5 6 7

2 8 9 10 11
2
Zone tampon 12 13 14 15
Ram

[Link],[Link] - SE 117
 CH.8 Système de fichier
❑ Stockage des fichiers
➢Méthodes d’allocation (1)
Répertoire

0 1 2 3 début fin lgueur

Allocation
4 5 6 7 0 6 7
contiguë
8 9 10 11
10 15 6
12 13 14 15

5 blocs libres
0 1 2 3 0 1 2 3

Toto : 4 blocs 4 5 6 7 4 5 6 7
8 9 10 11 8 9 10 11
Ne loge pas compactage
12 13 14 15 12 13 14 15

[Link],[Link]
Fragmentation - SE externe 118
Toto
 CH.8 Système de fichier
❑ Stockage des fichiers
➢Méthodes d’allocation (2)

0 1 2 3 début lgueur
Allocation 0 4
4 5 6 7
chaînée 1 6
8 9 10 11
12 13 14 15

Le pointeur

Données
du fichier

Un bloc
[Link],[Link] - SE 119
 CH.8 Système de fichier
❑ Stockage des fichiers
➢Méthodes d’allocation (2)
✓File Allocation Table

0
Entrée du répertoire
48 339
toto … 217

217 619

339 Fin-fichier (Ctrl Z)

619 48

[Link],[Link] - SE 120
 CH.8 Système de fichier
❑ Stockage des fichiers
➢Méthodes d’allocation (3)

index lgueur
0 1 2 3 7 4
Allocation
4 5 6 7
indexée
8 9 10 11

12 13 14 15

0
6
9 128 entrées
13
15
0
8
....
Bloc n°7
[Link],[Link] - SE 121
 CH.8 Système de fichier
❑ Stockage des fichiers
➢Méthodes d’allocation (4)

Indexation à
3 niveaux

[Link],[Link] - SE 122
 CH.8 Système de fichier
❑ Stockage des fichiers
➢Méthodes d’allocation (5)

I-node d’Unix
10 accès
directs

Indirections
simple

double

triple
[Link],[Link] - SE 123
 CH.9 Introduction à la sécurité
Cryptage par clé publique

communication
E et D publiques

B’ publique A’ publique
Bob Alice A’’ secrète
B’’ secrète

EA’ DA’’
M M’ M’’ = M

DA’’ EA’
M’ M M’’ = M’

[Link],[Link] - SE 124
 Secret des données

A’ A’’
publique privée

EA’ DA’’
M M’ transmis M’ M’’ = M

Authenticité des données

DA’’
M M’’

secrète
EA’
M
publique

[Link],[Link] - SE 125
 Secret + authenticité

privée publique transmission

M DB’’ EA’
M’=DB’’(M) M’’=EA’(M’) M’’
signature

privée
publique
M EB’ DA’’
M’ M’’

[Link],[Link] - SE 126