Download en mode ma??

II Chapitre 1 : Présentation générale JJ
Notion de Système Informatique
Définition fonctionnelle :
– Machine de traitement de l’information qui assure
- le stockage des données
- l’exécution des programmes
– Notion de Système Informatique
– Les fonctions d’un système d’exploitation
– Structure en couches :
– Historique et évolutions
– Structure interne d’un système d’exploitation
Logiciels d’application
Outils et Services
– Composantes d’un système d’exploitation
Logiciel de base
Système d’Exploitation
Machine physique
3
2
II Historique des S.E. JJ
Les fonctions d’un système d’exploitation
Gestion de l’information :
- Structuration (codage, fichiers)
- Conservation (fichiers, mémoire)
- Transfert (E/S transparentes)
- Partage (entre plusieurs tâches)
Fin 40 : Organisation en porte ouverte.
– Le temps d’accès à la machine est structuré en période de 30 minutes
– Chaque période est allouée à un utilisateur
– A la fin de la période la machine est réinitialisée
Gestion des ressources :
- Allocation/Arbitrage
- Partage (diminution des coûts)
- Abstraction (simplification)
– L’utilisateur doit attendre la période suivante
Avantage : Chaque utilisateur a la machine pour lui tout seul.
Autres services :
- Sécurité (traitement des erreurs)
- Évaluation/Statistique/Facturation
- Outils divers (sauvegarde, recherche)
Inconvénient : Le travail doit être découpé en tranche de 30 minutes.
4
5
Le moniteur humain de gestion des travaux
Le moniteur logiciel d’enchaı̂nement des travaux
Apparition d’un opérateur de gestion des travaux :
Début 50 : Moniteur logiciel d’enchaı̂nement séquentiel des travaux. Il
assure les fonctions
Utilisateurs
– de compilation des travaux
Travaux
– de chargement en mémoire
– d’enchainement des travaux
Moniteur
File des travaux
en attente
Travail courant
Il récupère les travaux, gère la file d’attente et enchaine les exécutions.
|
|
|
|
|
|
|
chargement du moniteur
compilation en mémoire
exécution du travail 1
chargement du moniteur
compilation en mémoire
exécution du travail 2
...
compilateur
du travail 1
compilateur
du travail 2
6
7
Le moniteur logiciel résidant
Le traitement par lots
Milieux des années 50 : Moniteur logiciel résidant d’enchaı̂nement séquentiel des travaux. Il assure les fonctions
Fin des années 50 : Traitement par lots. Apparition du parallélisme des
tâches entre lecture, calcul et impression.
– d’enchaı̂nement automatique des travaux
Machine
de lecture
– de protection de la mémoire
Machine
de calcul
Machine
d’impression
– de limitation de durée
– de supervision des entrées/sorties
Bandes magnétiques
Bandes magnétiques
d’entrée
de sortie
Mémoire centrale
ML
Préparation du lot 1
Préparation du lot 2
Préparation du lot 3
Moniteur
RB
RL
8
MC
MI
Exécution du lot 1
Exécution du lot 2
Impression du lot 1
9
Cycles de CPU et d’entrée/sortie
Multiprogrammation
Chaque processus enchaı̂ne des cycles de CPU (exécution de code) et des
cycles d’entrée/sortie :
Début 60 : Multiprogrammation. Présence simultanée de plusieurs programmes en mémoire centrale.
Attente
Unité d’E/S
CPU
Périphériques
CPU
Unité d’E/S
E/S
Mémoire centrale (RAM)
CPU
Nouvelles caractéristiques :
- E/S tamponnées : définition d’un canal d’E/S,
- réimplantation du code,
- protection de la mémoire
E/S
10
11
Apparition des terminaux
60/70 : Le temps partagé
60/70 : Intégration des terminaux :
Le temps d’exécution de la CPU est découpé en tranches :
– les terminaux sont connectés au serveur
P0
P1
P2
P0
P1
P2
P0
CPU
– les utilisateurs travaillent devant le terminal
Temps
Quanta
– ils partagent leur temps entre réflexion et action
Si
Hypothèse 1 : Le temps de réflexion est de 90% :
Quanta = 50 millisecondes et une requête ≤ 1 quanta
alors
donc, sur 100 utilisateurs, 10 sont actifs.
Temps de réponse = 10 × 50 ms =
Hypothèse 2 : Les utilisateurs actifs réclament des actions simples :
1
s
2
Contraintes :
prise en compte du travail interactif
- multiprogrammation,
- temps de commutation faible,
- possibilité d’interruption propre .
12
13
II Structure interne d’un système JJ
Les systèmes répartis
1980 : Systèmes répartis. Répartition d’une activité entre plusieurs machines reliées par réseau (lent ou rapide).
Exemple : Le Cluster. La somme de plusieurs machines est vue comme
une seule machine (simplicité, évolutivité, robustesse).
Un résumé de l’historique
1950
Gros
ordinateurs
pas de
logiciels
1960
1970
traitement
par lots
moniteurs
compilateurs
multiutilisateurs
systèmes
répartis
temps
partagé
pas de
logiciels
Mini
ordinateurs
1980
temps
partagé
multiutilisateurs
moniteurs
compilateurs
multiutilisateurs
et
temps
partagé
pas de
compilateurs
compilateurs
Les Micros
moniteurs
14
Organisation en machines
15
Utilité des machines
Une machine c’est
- des objets,
- des actions possibles,
- des règles de composition des actions.
Ancienne machine M0 et son système S0 :
M0
S0
On souhaite développer un système S1 sur une nouvelle machine M1 :
Dans une structure en couches, le S.E. est concu comme un empilement
de machines.
M0
M0
M1
M1
M2
M2
M3
M3
(a)
(b)
M0
M1
S1 ?
Un simulateur de M1 sur M0 est utilisé :
M0
M2
M3
M1 ?
S0
Simulateur M1
S1 (dev)
M1
S1
M4
M5
(c)
Avantages : Sécurité et modularité.
16
17
Spécialisation
Abstraction
Mémoire
centrale
Mémoire
secondaire
Noyau Noyau Noyau Noyau Noyau
Machine virtuelle
Noyau
Mémoire
Virtuelle
Mémoire
physique
Disques
Utilisateurs
Utilisateurs
Mémoire
Utilisateurs
Les machines virtuelles d’IBM (VM)/CMS :
Utilisateurs
Un objet c’est
- une représentation interne / externe,
- des fonctions d’accès,
Utilisateurs
Un premier exemple
Utilisateurs
Organisation objet
Matériel
Disquettes
Avantages : Sécurité, modularité, abstraction et spécialisation.
18
Un deuxième exemple
19
Composantes d’un S.E.
L’architecture Micro-noyau par opposition aux structures monolithiques
des systèmes
processus utilisateur
interpréteur de commandes
SGBDR
MacOS X
OS/2
OSF/1
DOS
BSD 4.3
interface d'appel au système (SVC)
Micro Noyau MACH du M.I.T.
Gestion des processus
Gestion des fichiers
Gestion de la mémoire centrale
Gestion du système d'E/S
Gestion des interruptions
« Drivers » de périphériques
(Tache, ES, Mem Virt)
interface vers le matériel
Matériel
Machine physique
Avantages : Portabilité, Qualité.
20
21
II Présentation des processus JJ
Notion de programme
Un programme est une suite d’instructions rangées en mémoire :
– Notion de programmes
void main() {
...
}
– Notion de machine
– Exécution d’un programme
⇒
2048
LOAD R1,
2052
$ 10
2056
INC R1
2060
ADD R1, R2
⇒
01001001011101101
10011111001010100
11101010001100101
– Processus





 Lancement des E/S




privilégiées
=
Contrôle des interruptions







Contrôle du matériel




Instructions =


mouvement de données







structure de contrôle


 ordinaires
=



calcul







appel du système d’exploitation
2
1
Notion de machine
Description du processeur




Processeur (CPU)






Registres spécialisés








=
Un
 Entier
 Registres
=
processeur (MEP)



=
processeur
Flottant








 généraux

Adresse













 Mot d’état
Une
= Mémoire
(

machine


Contrôleurs



 Organes d’E/S =
Canaux
Unité de calcul (UAL)
L’état d’une machine c’est l’état de ses composants.


compteur ordinal (CO)





mode d’exécution (MODE)


 pointeur de pile (SP)
Registres
=

spécialisés
masque d’interruptions




codes de conditions



 ...
– en mode esclave les instructions privilégiées sont interdites
– en mode maı̂tre les restrictions disparaissent
3
4
Exécution d’un programme
Notion de processus
Une exécution c’est une évolution discrète de l’état de la machine.
Un processus est un programme en cours d’exécution. Il est défini par :
– des zones mémoire (code, pile et données),
Evolution des registres de la C.P.U.
Code en cours
d'exécution
CO
R1
R2
123
-
34
Mémoire d’un processus
LOAD R1, #10
LOAD R1,
124
#10
125
INC R1
126
ADD R1, R2
125
10
34
INC R1
126
11
CST
DATA
PILE
PILE
SYSTEME
Exécution
123
CODE
34
– la valeur des registres de la CPU (un MEP),
ADD R1, R2
127
45
– un ensemble de ressources allouées,
34
Le tout forme le contexte d’exécution du processus.
Notion de points observables.
5
6
II Les interruptions JJ
I Rendez-vous asynchrones J
Problème : Prise en compte rapide d’un événement tout en effectuant un
travail.
– Rendez-vous asynchrone,
Exemple :
– Interruption d’un processus,
– Le travail :
– Interruption matérielle,
- exécuter un processus consommateur de CPU (pas d’entrée/sortie)
– Les appels système,
– Les évènements à gérer :
– Les déroutements.
-
un paquet arrive sur la carte réseau
déplacement de la souris
activation du clavier
apparition d’une alarme
1
2
I Attente active J
I Attente active (suite) J
Solution : l’attente active. Soit F un indicateur qui signale l’événement
...
si (F = 1) alors
F := 0
< traiter l’événement >
fin si
...
– pas de réaction immédiate
Evt
Test
------|-----------------|-----|<--- latence --->|
– risque de collision
Evt
Evt
Test
------|-----------|-----------------|-----|<- écart ->|<--- latence --->|
– le test explicite est pénible et peu sécurisé
– perte de temps C.P.U.
écart minimum > latence
3
4
I Interruption d’un processus : Principe J
Interruption : opération indivisible effectuée par la C.P.U. qui change le
CO et le MODE .
Les interruptions sont déclenchées uniquement sur les points observables
(points interruptibles).
Chaque interruption a une cause identifiée par un entier.
I Interruption d’un processus : Exemple J
Le vecteur d’interruptions ( VI ) est une table logée dans les adresses
basses de la mémoire.


 PUSH CO, MODE ;
interruption
= MODE := ma^
ıtre ;

de cause k
 CO := vi[k] ;
reprise après interruption :
(
instruction RTI =
POP MODE ;
POP CO
5
Code
utilisateur
Vecteur
d'interruptions
Code du
système
LOAD R1,
100
124
#10
101
125
INC R1
102
.
.
.
.
126
ADD R1, R2
103
RTI
I Structure générale d’un traitant J
−
0
123
6
1
−
2
100
3
−
Le code exécuté après une interruption est appelé le traitant de cette
interruption.
Les traitants ont la structure suivante :
Evolution des registres de la C.P.U.
CO
MODE
SP
R1
R2
123
esclave
200
-
34
125
esclave
10
34
LOAD R1, #10
200
Evolution de la pile
-
-
SP
1.
2.
3.
4.
sauvegarde du contexte
traitement de la cause
restauration du contexte
retour au processus interrompu (instruction RTI )
< interruption de cause n° 2 >
100
maître
.
.
.
103
201
10
.
.
.
maître
201
34
<125,e>
.
.
.
-
SP
10
34
10
34
11
34
RTI
125
esclave
200
INC R1
126
esclave
200
<125,e>
-
SP
7
I Utilisation des interruptions J
I Interruption matérielle : principe J
Il existe trois types d’interruptions :
Un signal électrique est émis vers le processeur qui provoque une interruption.
– Interruption matérielle : réaction aux événements extérieurs.
Clavier
– Appel au superviseur : appel explicite d’une routine système.
– Déroutement : traitement des erreurs et des situations anormales.
C.P.U.
Souris
C. vidéo
Controleur
disk0
disk1
disk2
Il y a donc un branchement vers le code de traitement des interruptions (le
traitant) avec un changement de mode.
8
I Interruption matérielle : caractéristiques J
I Les appels systèmes : principe J
Le numéro associé à chaque interruption matérielle indique une priorité :
int.
niv 5
int.
niv 4
int.
niv 1
int.
niv 3
9
Si les processus s’exécutent en mode utilisateur, les entrées/sorties directes
leurs sont interdits.
int.
niv 0
I Pour réaliser des E/S, les processus doivent envoyer des requêtes au
système d’exploitation.
0
1
I L’appel de fonction classique pose des problèmes :
2
3
4
- le nombre de points d’entrée est important
- le mode d’exécution reste esclave
- le code du système d’exploitation est accessible en lecture
5
6
7
prise en compte
de l'int. niv 3
Des instructions privilégiées permettent de
- masquer des niveaux,
- armer ou désarmer des niveaux,
- déclencher des niveaux.
10
11
I Les appels systèmes : moyens J
I Les appels systèmes : Avantages J
Les trappes ( Trap ) : Appel explicite du système par le biais d’une instruction qui déclenche une interruption.
Code utilisateur
en mode esclave
Librairie standard
en mode esclave
Avantages des appels par interruption :
I Changement de mode
I Le nombre de points d’entrée est limité
Processus
en mode maitre
I On obtient un sas qui isole le système d’exploitation
...
x=open("ficA",WRITE);
...
...
...
LOAD R0, SVC_OPEN
LOAD R1, "mon_fic"
LOAD R2, WRITE
SVC
CMP R0, 0
...
...
RTS
switch (R0)
{
I Définition d’une nouvelle machine (ajout d’instructions)
...
...
I Une librairie standard offre
case SVC_OPEN:
< ouverture >
break;
- une interface système agréable et simplifiée
- une interface indépendante du système d’exploitation
- l’implantation réelle des appels systèmes en assembleur
...
...
}
RTI
Code du système d’exploitation
12
13
I Les appels systèmes : Structure du traitant J
I Déroutements : Principe J
L’objectif des déroutements est double :
1. sauvegarde du contexte
I traitement systématique des erreurs ou des situations anormales
(défaut de page),
2. vérifier la conformité de la requête
I protection et bonne utilisation de la machine (les processus s’exécutent
sous surveillance).
- vérifier la nature de la requête
- vérifier la nature des arguments
- vérifier les droits du processus demandeur
Si l’exécution d’une instruction produit une erreur, alors
→ il y a interruption et
→ branchement vers le code de traitement des erreurs du système.
3. exécuter la requête
4. choisir le prochain processus p à exécuter
Les causes possibles sont :
5. restaurer le contexte de p
-
6. relancer le processus p
14
données incorrectes (division par zéro)
opération interdite (instruction privilégiée)
instruction inconnue
accès à une zone mémoire interdite
erreur de bus mémoire
15
I Déroutements : Exemples J
I Implantation d’une gestion utilisateur des erreurs (fonction signal )
I Gestion de la mémoire virtuelle.
I Ajout de nouvelles instructions par simulation logicielle.
I Le mode TRACE sur le processeur 68000 :
– à chaque point interruptible, la C.P.U. génère un déroutement,
– le système récupère donc le contrôle entre chaque instructions,
– il peut visualiser l’évolution des registres.
16
II Gestion des processus JJ
I État d’un processus J
– État d’un processus,
Chaque processus est dans l’un des états opérationnels suivants :
– Représentation d’un processus,
prêt
6
– Rôle du PCB,
1
– Représentation des processus,
– Les threads (processus de poids léger),
connu
en attente
– Utilité des threads ,
2
4
terminé
– Implantation des threads ,
5
actif
1. initialisation
2. exécution
3. achèvement
4. préemption
5. attente
6. signal
3
2
1
I Représentation d’un processus J
I Rôle du PCB J
Pour chaque processus le système maintient :
Le rôle du PCB dans la commutation entre deux processus :
– un identifiant ( pid )
P0
P1
statistiques :
temps CPU
nombre d’E/S
nombre de défauts de page
PCB0
restauration
restauration
PCB1
sauvegarde
actif
– des
-
sauvegarde
prêt
informations diverses :
priorités
filiations
propriétaire
actif
– des
-
prêt
– un contexte d’exécution
prêt
actif
– un état opérationnel
Ces informations sont rangées dans un PCB (Process Control Block).
3
4
I Représentation des processus J
I Gestion des processus J
Les PCB sont rangés dans des files :
Création de processus :
I chaque processus peut créer des processus (ses fils),
réquisition
I il est possible de figer, et de reprendre des processus.
file des processus prêts
allocation
de la CPU
I il est possible de tuer des processus ou demander leur arret.
processus
actifs
fin de
l'E/S
Communication entre processus :
file des processus en
attente de fin d'E/S
I prévoir des outils de communication (fichier, tube, socket, mémoire
partagée, envoi de messages)
demande
d'E/S
appel de exit()
file des processus morts
Synchronisation de processus :
I prévoir des outils de synchronisation (verrou, sémaphore, moniteur)
5
6
I Les threads (processus de poids léger) J
I Programmation des threads J
Un thread (fil) est un programme en cours d’exécution qui partage son
code et ses données.
Processus
Thread 1
Exécution
CODE
MEP
PILE
Thread 2
DATA
Exécution
MEP
Fichiers
ouverts
et Ressources
begin
Instruction 1
co-begin
Instruction 2
Instruction 3
co-end
Instruction 4
end
PILE
Thread 3
Exécution
MEP
void travail() {
int t ;
instruction1() ;
if ((t = thread()) == 0) {
instruction3() ;
thread exit() ;
}
instruction2() ;
thread join(t) ;
instruction4() ;
}
PILE
Trace de l’exécution :
Chaque thread a une pile d’exécution autonome.
CPU0 :
|<--- Ins. 1 --->|<-- Ins. 2 -->|.....|<--- Ins. 4 --->
CPU1 :
|<----- Ins. 3 ----->|
Un processus est composé de threads.
7
8
I Utilité des threads J
I Utilité des threads pour les serveurs J
Étude des dépendances et découpage :
Application serveur
Processus fils
C5 dépend de C2 et C4
C1
C2
C3
C4
C5
Processus
Processus fils
principal
Processus fils
Processus fils
C4 dépend de C3
C2 dépend de C1
Processus serveur
Thread fils
C1
C3
C2
C5
C4
Thread 1
Thread 2
Thread
Thread fils
principal
Thread fils
Thread fils
Données globales
Avantages :
- récupération des temps d’E/S,
- exploitation des machines multi-processeurs,
- coopération entre threads.
La commutation et la communication entre threads est une opération
plus simple
9
10
I Les processus monolithiques J
I Les processus multi-threads J
Il existe un conflit entre
- entrées / sorties synchrones (bloquantes),
- interface homme/machine (IHM).
réseau
disque
Il existe un autre solution basée sur
- le découpage en plusieurs threads,
- une utilisation des E/S synchrones,
- un module de communication.
Boucle des événements
Gestionnaire
de la file
des événements
GUI
récupérer un
événement
réseau
Thread "Gestion réseau"
disque
Thread "Gestion disque"
GUI
Evénements
asynchrones
Thread "Gestion de l’IHM"
Communication
et
synchronisation
Thread "Gestion de la mémoire"
Traiter
Evénements
asynchrones
Processus monolithique
Processus multi−threads
Avantages :
- plus grande simplicité du code,
- indépendance entre les modules.
Solution d’attente active :
- E/S asynchrones (non-bloquantes),
- structure avec boucle d’événements.
11
12
I Implantation des threads J
II Allocation du processeur JJ
– Allocation de la CPU
Implantation au niveau du S.E. :
+ le S.E. connaı̂t et ordonnance les threads,
– Stratégies d’allocation
+ la répartition de la CPU est bonne,
– Les algorithmes d’allocation :
-
− les structures du S.E. sont alourdies.
Implantation au niveau utilisateur (Java) :
+ une librairie se charge de la gestion des threads (création, ...),
+ la commutation entre threads d’un même processus est plus rapide,
FIFO
SJF
SRT
HRN
Le tourniquet
Le tourniquet multi-niveaux
− la répartition de la CPU n’est pas équitable,
− la mise en attente d’un processus entraı̂ne le blocage de tous ses
threads.
13
14
I Allocation de la CPU J
I Stratégies d’allocation J
Il y a perte de la CPU dans trois cas :
Objectifs :
- interruption extérieur,
- déroutements,
- appels système.
-
Quel type d’allocation ?
équité,
débit maximum
maximum de processus interactifs,
rationaliser la gestion des ressources,
favoriser les bons processus,
améliorer les temps de réponse moyen,
– le long terme : variation du degré de multi-programmation par :
- swapping out : les processus sont copiés en mémoire secondaire
- swapping in : les processus sont rapatriés en mémoire centrale
– le moyen terme (détermine et classe les processus prêts),
– le court terme (répartition de la CPU)
15
Critères :
-
le taux d’E/S
le taux d’utilisation de la CPU
le type et la priorité du processus,
temps CPU cumulé,
temps CPU restant,
taux de réquisition
16
I Algorithme d’allocation FIFO J
I Algorithme d’allocation SJF J
FIFO (First In First Out) : absence de réquisition et croissance rapide du
temps de réponse.
arrivée
SJF (Short Job First) : absence de réquisition et risque de privation.
Temps
de
réponse
sortie
SJF
FIFO
temps de réponse = (temps d’attente + temps d’exécution)
temps d’attente = (taille de la file FIFO × durée moyenne d’exécution)
Temps de service demandé
Il faut estimer le temps d’exécution des processus.
17
18
I Algorithmes d’allocation SRT J
I Algorithmes d’allocation HRN J
SRT (Shortest Remaining Time) : c’est SJF + un mécanisme de
réquisition.
– Mêmes contraintes que SJF
– On choisit le processus qui a le temps restant d’exécution le plus petit
– L’arrivée d’un nouveau processus peut interrompre le processus courant
HRN (Highest Response Ratio Next) : Le choix est basé sur le ratio
p(t) =
avec
-
w(t) + ts
ts
w(t) = t − ta : temps d’attente,
ta : date d’arrivée,
ts : temps d’exécution estimé.
Conséquences :
Si w(t) = 0, les travaux les plus courts (ts) sont privilégiés.
- On favorise les travaux courts.
- Coûts d’exploitation importants.
19
20
I Algorithmes d’allocation du tourniquet J
Comment fixer la durée du quanta :
Tourniquet (round robin) : c’est FIFO plus un mécanisme de réquisition.
arrivée
CPU
Temps de
réponse moyen
sortie
réquisition (préemption)
quantum
21
22
I Tourniquet Multi-niveaux J
I Tourniquet Multi-niveaux avec priorités J
Il existe des classes de processus :
réquisition (préemption)
-
niveau 0
niveau 1
niveau 2
systèmes,
temps réel,
interactifs,
d’édition interactive,
batch .
Chaque classe et absolument prioritaire sur celles de niveau inférieur.
.
.
.
.
.
.
processus
processus
processus
processus
processus
A l’intérieur de chaque classe, les processus sont rangés dans un système
de files multi-niveaux.
niveau n-1
niveau n
arrivée
CPU
sortie
23
24
I Le cas des processus temps réel J
I Mélange Temps Réel et temps machine J
Prise en compte d’un évènement :
évènement
Le temps C.P.U. peut être divisé en une partie fixe réservée au processus
Temps Réel, et une partie reservée aux autres processus.
Prise en compte
évènement
attente
temps
attente
T.R.
Autres
T.R.
Autres
si
Les algorithmes précédents s’appliquent dans la partie T.R.,
n est le nombre de processus temps réel,
s le temps pris par l’ordonnanceur,
t le temps moyen pris par les processus T.R.
Les algorithmes classiques sont utilisés par la partie Autres .
alors
(n − 1) × (s + t) < attente.
25
I Allocation multi-processus J
Hypothèse : on dispose de N processeurs identiques.
Objectifs :
- équilibrage de la charge (homogénéité des taux d’utilisation de la
C.P.U.),
- évitez les effets de pompage ,
Système simple : le S.E. s’exécute toujours sur la même C.P.U.
Système plus sophistiqué : le S.E. est capable de s’exécuter en parallèle
sur plusieurs processeurs.
→ Il faut gérer les problèmes de synchronisation.
27
26
II Présentation générale JJ
Accès à des ressources partagées
Le problème :
Soit une pile partagée par plusieurs threads :
- Accès à des ressources partagées
- Les sections critiques
- Le problème de l’exclusion mutuelle
pile = structure
sommet : entier ;
data : tableau [ 1 .. Max ] de entier ;
procédure empiler( var p : pile ; d : entier )
p.sommet := p.sommet + 1 ;
p.data[ p.sommet ] := d ;
Solutions d’attente active :
-
Une solution d’attente active
blocage des interruptions
Algorithme de Peterson (2 processus)
Solution matérielle
Il est possible que nous ayons :
thread1
thread1
:
:
—
thread2 :
thread2 :
thread2 :
...
— —
thread1 :
Solutions de manipulation des processus :
-
Les verrous
Les sémaphores
Le producteur et le consommateur
Les sémaphores à messages
Les régions critiques
empiler( p, 10 )
p.sommet := p.sommet + 1 ;
— interruption — —
empiler( p, 20 )
p.sommet := p.sommet + 1 ;
p.data[ p.sommet ] := 20 ;
...
...
retour au thread 1 — —
p.data[ p.sommet ] := 10 ;
1
2
Les sections critiques
Le problème de l’exclusion mutuelle
Les ressources logicielles ou matérielles qui posent des problèmes sont dites
critiques.
Forme des programmes :
hinitialisationi
Les portions de code qui manipulent ces ressources critiques sont appelées
des sections critiques.
exécuté une seule fois
...
hprologuei
hsection critiquei
hépiloguei
Les notions de ressource critique et section critique sont utiles
– pour les threads d’un processus utilisateur,
– pour les données du système d’exploitation partagées par les processus.
Contraintes :
– Il existe au plus un processus en section critique
– Les processus ne sont pas bloqués sans raison (absence de privation).
– Les sections hprologuei et hépiloguei sont les mêmes pour tous les
processus (uniformité).
3
4
Conflit avec deux threads. Le prologue et l’épilogue encadrent la section
critique :
prologue
Nouvelle formulation
La procédure empiler devient :
procédure empiler( var p : pile ; d : entier )
hprologuei
p.sommet := p.sommet + 1 ;
p.data[ p.sommet ] := d ;
hépiloguei
épilogue
prologue
épilogue
Le problème est réglé en augmentant la durée d’exécution du prologue :
prologue
Nouvelle exécution :
thread1
thread1
thread1
: empiler( p, 10 )
: hprologuei
: p.sommet := p.sommet + 1 ;
— — interruption — —
thread2
: empiler( p, 20 )
thread2
: hprologuei
— — blocage du thread 2 — —
...
...
...
— — retour au thread 1 — —
thread1
: p.data[ p.sommet ] := 10 ;
thread1
: hépiloguei
...
...
...
— — reprise du thread 2 — —
thread2
: p.sommet := p.sommet + 1 ;
thread2
: p.data[ p.sommet ] := 20 ;
thread2
: hépiloguei
épilogue
prologue
épilogue
5
Une solution d’attente active
blocage des interruptions
Soit libre une variable partagée de type booléenne pour coder l’exclusion
mutuelle :
hiniti
(1)
6
libre := vrai ;
hiniti
(1)
libre := vrai ;
hprologuei
(2)
(3)
(4)
(5)
(6)
(7)
(8)
hépiloguei
(9)
soit p une variable privée
répéter
hmasquer les interruptionsi
p := libre ;
libre := faux ;
hrétablir les interruptionsi
jusqu’à (p = vrai)
...
hsection critiquei
...
libre := vrai
...
hprologuei
hépiloguei
(2)
(3)
si (libre = faux) aller en (2)
libre := faux
(4)
hsection critiquei
(5)
libre := vrai
Critiques :
– Consommation de temps processeur
– L’exclusion mutuelle n’est pas toujours respectée :
2 hinterruptioni
2’ 3’ 4’ . . .
hretour au rougei
3 4 ...
7
Critiques :
- L’ordre d’arrivée n’est pas respecté.
- Risque de privation.
- C’est une solution mono-processeur.
- Utilisable uniquement en mode maı̂tre.
8
Solution pour deux processus
Algorithme de Peterson pour deux processus
Soit tour une variable entière partagée :
On ajoute une variable demande pour représenter l’état des processus :
var
tour :
var
entier ;
Voila le codage pour le processus Pi :
hinitialisationi
(1)
tour := 0 ;
hprologuei
(2)
(3)
répéter
jusqu’à (tour = i)
(4)
tour := (1 − i) ;
hépiloguei
tour :
demande :
entier ;
tableau [ 0 .. 1 ] de booléen ;
Voila le codage pour le processus Pi :
Critiques :
- L’ordre est fixé à priori avec alternance
- Risque de privation (blocage inutile)
- Il n’y a pas de mémoire de l’état des processus
hinitialisationi
(1)
(2)
tour := 0 ;
demande := (faux, faux) ;
hprologuei
(3)
(4)
(5)
(6)
demande[i] := vrai ;
tour := 1 − i ;
répéter
jusqu’à (tour = i) ou (demande[1 − i] = faux)
hépiloguei
(7)
demande[i] := faux ;
C’est une solution correcte pour le problème de l’exclusion mutuelle à deux
processus.
9
10
Solution matérielle
Utilisation de Test and Set
On introduit une nouvelle instruction Test and Set pour
Codage de l’exclusion mutuelle avec une variable partagée mutex et une
variable privée p.
– garantir l’atomicité d’une modification,
– construire une solution basée sur l’attente active valable en multiprocesseurs :
hinitialisationi
(1)
mutex := 1 ;
hprologuei
(2)
(3)
(4)
répéter
TAS(p, mutex) ;
jusqu’à (p = 1)
(5)
hsection critiquei
(6)
mutex := 1 ;
Définition de Test and Set :
instruction TAS(var m : entier , var verrou : entier )
hbloquer la case mémoire verroui
m := verrou
verrou := 0
hdébloquer la case mémoire verroui
CO := CO + htaille de l’instruction TASi
hépiloguei
Critiques :
- Consommation de temps processeur.
- Risque de privation (cela peut s’arranger).
- Le processeur doit garantir l’exclusion mutuelle.
C’est une solution utilisable uniquement sur des séquences brèves.
11
12
Les verrous
Les verrous (2)
Objectifs :
Pour un verrou donné, les deux procédures ci-dessous s’exécutent en exclusion mutuelle.
– ne plus perdre de temps CPU,
procédure prendre(var v : verrou)
si (v.libre = faux ) alors
hsoit P le processus appelanti
hentrer P dans la file v.f i
hsuspendre le processus P i
sinon
v.libre := faux ;
fin si
– simplicité de la solution.
Définition des verrous :
verrou : structure
libre : booléen ;
f : file FIFO de processus ;
procédure init(var v : verrou)
v.libre := vrai ;
v.f := {} ;
Un verrou est une structure de donnée partagée du système d’exploitation.
procédure libérer(var v : verrou)
si hla file v.f est videi alors
v.libre := vrai ;
sinon
v.libre := faux ;
hsortir un processus Q de la file v.f i
hréveiller le processus Qi
fin si
13
14
L’exclusion mutuelle avec les verrous
Difficultés des verrous
soit
soit deux processus qui partagent deux ressources :
var
mutex
var
: verrou ;
init(mutex1 ) ;
init(mutex2 ) ;
le code de l’exclusion mutuelle s’écrit
hinitialisationi
(1)
init(mutex ) ;
hprologuei
(2)
hépiloguei
(3)
prendre(mutex ) ;
...
hsection critiquei
...
libérer(mutex ) ;
mutex1 : verrou ;
mutex2 : verrou ;
hP1i
(1)
(2)
(3)
(4)
(5)
prendre(mutex1 ) ;
prendre(mutex2 ) ;
hsection critiquei
libérer(mutex2 ) ;
libérer(mutex1 ) ;
hP2i
(1’)
(2’)
(3’)
(4’)
(5’)
prendre(mutex2 ) ;
prendre(mutex1 ) ;
hsection critiquei
libérer(mutex1 ) ;
libérer(mutex2 ) ;
Il y a blocage pour la séquence
15
1 . . . 1’ . . . 2 3 . . . 3’
16
Les sémaphores
Agir sur les sémaphores
Un verrou ne sait pas compter. . . donc, il faut remplacer le drapeau par un
compteur (Dijkstra).
Pour un sémaphore donné, les deux procédures ci-dessous s’exécutent en
exclusion mutuelle.
Un sémaphore est une structure de donnée partagée du système d’exploitation.
sémaphore : structure
c : entier ;
f : file FIFO de processus ;
procédure P(var s : sémaphore)
s.c := s.c − 1
si (s.c < 0) alors
hsoit P le processus appelanti
hentrer le processus P dans la file s.f i
hsuspendre le processus P i
fin si
procédure V(var s : sémaphore)
s.c := s.c + 1
si (s.c ≤ 0) alors
hsortir un processus Q de la file s.f i
hreprendre le processus Qi
fin si
procédure init(var s : sémaphore ; c0 : entier)
vérifier que c0 ≥ 0 ;
s.c := c0 ;
s.f := {} ;
P pour proberen (tester) ou wait
V pour verhogen (incrémenter) ou signal
17
Utilisation des sémaphores
Les sémaphores simulés par des verrous
Soient trois processus qui exploitent la même ressource :
(1)
(2)
(3)
(4)
(5)
(6)
P1
P(s)
...
...
V(s)
...
...
P2
...
P(s)
...
...
V(s)
...
sémaphore :
blocage
mutex
c
P3
...
...
P(s)
...
...
V(s)
action
P(s)
P(s)
P(s)
V(s)
V(s)
V(s)
(2,{})
(1,{})
(0,{})
(-1,{P3})
(0,{})
(1,{})
(2,{})
P1
SC
SC
SC
A
A
A
P2
A
SC
SC
SC
A
A
structure
: verrou ;
: verrou ;
: entier ;
procédure init(var s : sémaphore ; c0 : entier)
vérifier que c0 ≥ 0 ;
s.c := c0
init(s.blocage) ;
init(s.mutex) ;
La trace de l’exécution donne :
(1)
(2)
(3)
(4)
(5)
(6)
18
P3
A
A
S
SC
SC
A
19
20
Les sémaphores simulés par des verrous
Les sémaphores privées
Soit sempriv un sémaphore privé de P1 et mutex un sémaphore ordinaire :
procédure P(var s : sémaphore)
prendre(s.mutex) ;
s.c := s.c − 1
si (s.c = −1) alors
libérer(s.mutex) ;
prendre(s.blocage) ;
prendre(s.blocage) ;
sinon si (s.c < 0) alors
libérer(s.mutex) ;
prendre(s.blocage) ;
sinon
libérer(s.mutex) ;
fin si
P1 :
P(mutex )
si hle blocage est inutilei alors
V(sempriv )
fin si
V(mutex )
P(sempriv )
P2 :
P(mutex )
si hle processus P1 doit être débloquéi alors
V(sempriv )
fin si
V(mutex )
procédure V(var s : sémaphore)
prendre(s.mutex) ;
s.c := s.c + 1
libérer(s.blocage) ;
libérer(s.mutex) ;
21
22
Le problème du producteur et du consommateur
Codage du producteur/consommateur
Il existe un tampon de taille limité entre le producteur et le consommateur.
Le consommateur consomme si le tampon n’est pas vide :
NPlein
Algorithme du producteur :
répéter
hproduire un messagei
hle déposer dans le tamponi
jusqu’à ...
:
sémaphore
=
(0, {})
producteur :
répéter
hproduire un messagei
hle déposer dans le tamponi
V(NPlein) ;
jusqu’à ...
Algorithme du consommateur :
répéter
hprélever un message depuis le tamponi
hle consommeri
jusqu’à ...
Consommateur :
répéter
P(NPlein) ;
hconsommeri
jusqu’à ...
23
24
Codage du producteur/consommateur (2)
Les sémaphores à messages
Définition des sémaphores :
Définition :
NPlein
NVide
:
:
sémaphore
sémaphore
=
=
(0, {})
(n, {})
séma-mesg : structure
c : entier ;
demandeurs : file FIFO de processus ;
messages : file FIFO de messages ;
Le producteur produit si le tampon n’est pas plein :
répéter
P(NVide) ;
hproduire un messagei
hle déposer dans le tamponi
V(NPlein) ;
jusqu’à ...
Le consommateur consomme si le tampon n’est pas vide :
répéter
P(NPlein) ;
hconsommeri
V(NVide) ;
jusqu’à ...
25
Procédures :
26
Les régions critiques
procédure Pm( var s : séma-mesg ; var m : données )
s.c := s.c − 1
si (s.c < 0) alors
hsoit P le processus appelanti
hentrer le processus P dans la file s.demandeursi
hsuspendre le processus P i
fin si
hsortir m de la file s.messagesi
Soit une pile partagée par plusieurs threads :
pile = structure partagée
sommet : entier ;
data : tableau [ 1 .. Max ] de entier ;
procédure empiler( var p : pile ; d : entier )
région p quand (sommet < Max)
sommet := sommet + 1 ;
data[ sommet ] := d ;
fin de région
procédure Vm( var s : séma-mesg ; m : données )
hentrer m dans la file s.messagesi
s.c := s.c + 1
si (s.c ≤ 0) alors
hsortir un processus Q de la file s.demandeursi
hreprendre le processus Qi
fin si
procédure dépiler( var p : pile ; var d : entier )
région p quand (sommet > 0)
d := data[ sommet ] ;
sommet := sommet - 1 ;
fin de région
27
28
P(mutex) ;
tant que non (condition)
nbEnAttente := nbEnAttente + 1 ;
V(mutex) ;
P(blocage) ;
P(mutex) ;
Les régions critiques simulées par sémaphores
hrégion critiquei
L’instruction
région p quand (condition)
hrégion critiquei
fin de région
répéter nbEnAttente fois V(blocage) ;
nbEnAttente := 0 ;
V(mutex) ;
peut se coder par
var
mutex
blocage
nbEnAttente
: sémaphore = (1, {}) ;
: sémaphore = (0, {}) ;
: entier = (0) ;
29
II Gestion des ressources JJ
Définition d’une ressource
Une ressource est un objet utilisable par une tâche. Elle est caractérisée
par :
Allocation de ressources :
- Définition d’une ressource
- Objectif de l’allocation de ressources
- Le graphe de l’allocation de ressources
- un état (libre ou allouée),
- l’existence d’un mode d’emploi,
- l’existence d’un allocateur qui répond aux requêtes,
Les interblocages :
-
On distingue les ressources :
Définition
Comment traiter les interblocages ?
Prévention des interblocages
Évitement des interblocages
L’algorithme des Banquiers
Détection des interblocages
Guérison des interblocages
– banalisées qui ont des occurences multiples (imprimantes, canaux d’E/S),
– réquisitionnables (CPU, mémoire),
– physiques ou logicielles,
– partageables ou réentrantes (pour le code d’un programme).
2
1
Objectifs de l’allocation de ressources
Le graphe de l’allocation de ressources
Les allocateurs de ressources doivent :
L’état des ressources allouées est décrit au moyen d’un graphe de l’allocation de ressources.
– être équitables (en respectant les priorités),
– éviter la privation (attente sans fin d’une ressource),
Un processus Pi et une ressource Rj ayant 3 occurrences sont décrits par :
– éviter l’apparition d’un interblocage,
Pi
– éviter une congestion en veillant à :
- identifier une demande excessive de ressources,
- ne pas accepter de demandes quand le système est en surcharge
Rj
Les demandes d’allocations et les ressources allouées sont décrits par :
R1
(a)
P1
R2
(b)
3
P1
P1 réclame
une ressource
de type R1
Une ressource
de type R2 a été
allouée à P1
4
Les interblocages
Un exemple d’interblocage
Définition : Attente sans fin pour plusieurs processus d’une ou plusieurs
ressources détenues par d’autres processus.
Un interblocage représenté par un graphe d’allocation des ressources :
Conditions d’apparition :
La ressource 1
est détenue par
le processus A
– les ressources ne sont pas partageables
ressource
1
Le processus B
réclame la
ressource 1
processus
A
– les ressources ne sont pas réquisitionnables
– chaque processus utilise simultanément plusieurs ressources
processus
B
Le processus A
réclame la
ressource 2
– il existe un ensemble de processus (P1, . . . , Pn) tel que
ressource
2
La ressource 2
est détenue par
le processus B
– Pi attend Pi+1 pour 1 ≤ i ≤ n − 1
– Pn attend P1
(1)
(3)
Pa
Pb
prendre R1
...
prendre R2
...
...
prendre R2
...
prendre R1
(2)
(4)
5
Comment traiter les interblocages ?
6
Prévention des interblocages
– La politique de l’autruche.
Diminuer le nombre de ressources qui ne peuvent être réquisitionnées.
– La Prévention : On impose des règles strictes qui évitent l’apparition
d’un interblocage.
– L’évitement : On surveille l’apparition d’un interblocage en imposant
des contraintes moins strictes.
– La détection : Un algorithme à la charge de détecter les interblocages.
– La guérison : Suppression éventuelle de l’un des processus.
7
→ interdire l’accès direct à la ressource,
→ remplacer la ressource réelle par une ressource virtuelle.
exemple
-
processeur → processus,
mémoire → mémoire virtuelle,
imprimante → queue d’impression,
écran → double-buffer, display,
machine → machine virtuelle.
8
Prévention des interblocages
Prévention des interblocages (suite)
Contrainte 1 : Classer les ressources suivant un ordre, et respecter cet
ordre lors des demandes de ressources.
Contrainte 2 : Annoncer les demandes de ressources avant de démarrer
un processus.
+ La condition d’attente circulaire est impossible donc pas d’interblocage
possible.
− Cet ordre doit respecter une certaine logique, . . .mais laquelle ?
− La contrainte est très lourde. . .
Contrainte 3 : À chaque demande d’allocation d’une ressource supplémentaire,
il faut libérer toutes les ressources détenues et les redemander en y ajoutant
la ressource supplémentaire.
Conséquences :
− La portabilité des applications est médiocre.
+ solution parfaite,
− très mauvaise utilisation des ressources,
− programmes difficile à écrire.
− Que faire quand on ajoute une nouvelle ressource ?
9
10
Évitement des interblocages
L’algorithme des Banquiers
On évite les interblocages en adoptant un comportement prudent. C’est
l’algorithme des banquiers.
• Un processus Pi peut s’exécuter ssi
- le S.E. connaı̂t les demandes maximales,
- les allocations/libérations sont libres.
• Les indices k1, . . . , kn forment un ordre d’exécution si et seulement si les
processus Pki (avec i ∈ {1, .., n}) peuvent s’exécuter dans cet ordre les uns
après les autres.
Structures de données :
-
∀j ∈ {1, . . . , M }, (maxi,j − alloci,j ) ≤ dispoj
M : nombre de classes de ressources,
N : nombre de processus,
dispoj pour i ∈ {1, . . . , M },
maxi,j pour i ∈ {1, . . . , N }, j ∈ {1, . . . , M },
alloci,j pour i ∈ {1, . . . , N }, j ∈ {1, . . . , M },
• Un système d’allocation de ressources est dit sain si il existe un ordre
d’exécution. Il n’y aura pas d’interblocages dans un système sain.
Algorithme d’allocation de Rj à Pi :
1.
1.
2.
3.
11
dispoj > 0 ?
les annonces sont-elles respectées ?
si Rj est allouée à Pi, l’état est-il sain ?
si la réponse est négative, suspendre le processus Pi
12
Détection des interblocages
Détection des interblocages (suite)
R1
P8
P7
R2
R1
P8
P7
R6
R2
R5
R5
R6
P9
Réduction
par P9
P9
R7
P1
P2
P3
P4
P5
P1
P2
P3
P4
R7
R4
R3
Réduction par P7
R1
P8
P7
R2
R1
P7
R2
R5
P8
R6
R4
R3
R6
P9
R7
Réduction
par P8
P1
P2
P3
P1
P2
P3
P9
R7
R4
R3
13
Guérison des interblocages
Solution :
- Tuer un processus pour libérer des ressources. . .mais quel processus ?
Introduction des transactions.
15
R3
14