Processus = programme (code exécutable statique) + contexte dynamique (compteur de programme, état processeur, espace mémoire, fichiers, ...).
![\begin{automate}[ct]{400}{150}{Les états et transitions d'un processus}{1}(20,5)...
... E/S}
\trans{trois}{cinq}{exit}
\trans{quatre}{deux}{fin E/S}
\par\end{automate}](img1.png)
Les objectifs sont contradictoires, il faut des compromis.
Equitable. Utilisation de l'UC et temps moyen de réponse dépendent du quantum. Une grande valeur de quantum favorise les procesus de type calculs, tandis que une petite valeur favorise les E/S, donc les processus intéractifs.
Equitable. Utilisation de l'UC et temps moyen de réponse sont bons. Diverses stratégies pour la gestion des priorités. Généralement, après une interruption, un processus réintègre la file d'attente correspondante à sa priorité initiale.
Implémentable dans les SGBD, mais pas dans un SE généraliste, car le temps du prochain cycle d'exécution n'est pas connu.
Une implémentation est possible en utilisant une fonction d'estimation du temps du prochain cycle. Par exemple t= a * t + b * te. (t : estimation, te : temps effectif, a+b=1).
L'ensemble des processus prêts est souvent trop important pour tenir en RAM. Certains sont donc sur disque. Un processus élu qui est sur disque prend beaucoup plus de temps qu'un processus en RAM pour être chargé dans l'UC.
Le processus élu est donc toujours pris parmi ceux en RAM. L'algorithme est alors non équitable.
La solution consiste à utiliser un deuxième algorithme d'ordonnancement pour gérer les déplacements des processus prêts entre le disque et la RAM.
![\begin{automate}[ct]{400}{150}{Deux niveaux d'ordonnancement}{1}(25,5)
\etat[i]{...
...e E/S}
\trans{trois}{cinq}{exit}
\trans{quatre}{six}{fin E/S}
\par\end{automate}](img2.png)
La mémoire est partagée entre plusieurs processus (exemple BD), il y a donc des risques de comportements bizarres.
Soient les deux processus suivant et la variable globale compte initialisée à 10.
|
Processus A
var aux : integer begin aux := compte; aux := aux + 10; compte := aux; end. |
|
Processus B
var aux : integer begin aux := compte; aux := aux - 5; compte := aux; end. |
La figure 2.3 représente le graphe des comportements du
``programme'' constitué des deux processus. Chaque n
ud contient les
valeurs des trois variables, et les arcs représentent les instructions.
Le résultat dépend de l'entrelacement des actions, donc de l'ordonnancement des processus. Il y a donc un besoin de contrôler le déroulement d'un processus.
N processus exécutent le programme suivant :
![\begin{automate}[ct]{800}{450}{Les trois variables.
}{0.6}(45,5)
\etat[i]{400}{4...
...\trans[acw]{quinze}{vingtun}{B3}
\trans{dixhuit}{vingtun}{A3}
\par\end{automate}](img4.png)
debut
tant que vrai faire debut
"entrer en section critique"
Section Critique
"sortir de section critique"
Section Non Critique
fin
fin
Les objectifs :
debut
tant que vrai faire debut
tant que feu = rouge faire rien;
feu := rouge;
Section Critique;
feu := vert;
Section Non Critique
fin
fin
Les 2 processus peuvent être ensemble en S.C
debut
tant que vrai faire debut
Flag[i] := true;
tant que Flag[j] faire rien;
Section Critique;
Flag[i] := false;
Section Non Critique
fin
fin
Les 2 processus ne peuvent pas être ensemble en S.C
Il n'y a pas d'attente s'il n'y a pas de compétition.
Il y a possibilité d'attente infinie (famine).
la preuve est faite par la construction du graphe du comportement des deux processus.
debut
tant que vrai faire debut
tant que tour = j faire rien;
Section Critique;
tour := j ;
Section Non Critique
fin
fin
2 processus ne peuvent pas être ensemble en S.C
Il n'y a pas d'attente infinie.
Il peut y avoir attente s'il n'y a pas de compétition. C'est un algorithme d'alternance (jeton).
debut
tant que vrai faire debut
Flag[i] := true;
tour := i ;
tant que (Flag[j] et tour = i) faire rien;
Section Critique;
Flag[i] := false;
Section Non Critique
fin
fin
La preuve sera faite en TD
Le SE doit fournir des primitives pour synchroniser des processus.
Les solutions logicielles font les hypothèses suivantes :
fonction TestAndSet(var but : booleen) : booleen debut TestAndSet := but; but := true; finUne solution non équitable pour N processus au problème de la section critique avec un booléen lock initialise à false.
debut
tant que vrai faire debut
tant que TestAndSet(lock) faire rien
Section Critique
lock := false
Section Non Critique
fin
fin
Certains processeurs possèdent une instruction TestAndSet.
procedure swap(var a, b : booleen) debut aux := a; a := b; b := aux finUne solution non équitable pour N processus au problème de la section critique avec un booléen lock et N booléens key[i] initialises à false.
debut
tant que vrai faire debut
key[i] := true;
tant que key[i] faire
swap(lock,key[i]);
Section Critique;
lock := false
Section Non Critique
fin
fin
Certains processeurs possèdent une instruction swap.
procedure wait(var S : entier) procedure signal(var S : entier) debut debut tant que (S <= 0) faire rien; S := S + 1 S := S - 1; f fin finUne solution non équitable pour N processus au problème de la section critique avec un entier mutex initialisé à 1.
debut
tant que vrai faire debut
wait(mutex);
Section Critique;
signal(mutex);
Section Non Critique
fin
fin
Aucun processeur ne possède ces instructions.
Il existe des solutions équitables.
Le défaut commun à ces solutions est l'attente active (gaspillage de l'UC).
Le SE doit fournir des appels systèmes pour endormir et réveiller des processus.
block qui permet à un processus de se mettre en état d'attente;
d'autre part wakeup(P) qui permet de mettre l'état du processus
P à prêt.
Avec ces hypothèses, il est assez facile d'éliminer l'attente
active. Il suffit de remplacer faire rien par block,
puis ajouter en fin de la phase de sortie une boucle pour reveiller
tous les processus "en attente" grâce à un wakeup(P)
Cette solution est moyennement satisfaisante, car en fait un seul
proceesus doit être reveillé, les autres feront en effet un nouveau
block.
block et wakeup avec
les procédures wait et signal.
type semaphore = (n : entier; l : liste de processus);manipulée uniquement par les actions atomiques
wait et signal.
procedure wait(var S : semaphore) procedure signal(var S : semaphore)
debut debut
S.n := S.n - 1; S.n := S.n + 1;
si (S.n < 0) alors debut si (S.n <= 0) alors debut
ajouter(moi,S.l); enlever(P,S.l);
block; wakeup(P);
fin fin
fin fin
debut
tant que vrai faire debut
wait(mutex);
Section Critique;
signal(mutex);
Section Non Critique
fin
fin
La solution est équitable si la liste de processus est une FIFO.
Les opérations wait et signal des sémaphores binaires
sont implémentés avec les instructions TestAndSet et/ou
Swap
wait et signal.
Soient les deux sémaphores S1(1,vide) et S2(1,vide). les processus P1 et P2 suivant peuvent se bloquer mutuellement.
processus P1 processus P2 debut debut wait(S1); wait(S2); wait(S2); wait(S1); ... ... fin fin
Les S.E. conçus autour d'un micro-noyau utilise principalement cette technique.
Les messages permettent de synchroniser des processus distants.
Il existe des variantes en fonction des sémantiques :
processus Pi
debut
tant que vrai faire debut
emettre(demande,controleur);
recevoir(aquittement,controleur);
Section Critique;
emettre(fin,controleur);
Section Non Critique
fin
fin
processus Controleur
debut
tant que vrai faire
cas de
recevoir(demande,P1); emettre(aquittement,P1); recevoir(fin,P1);
ou
recevoir(demande,P2); emettre(aquittement,P2); recevoir(fin,P2);
ou
...
ou
recevoir(demande,Pn); emettre(aquittement,Pn); recevoir(fin,Pn);
sac
fin
Les structures précédentes (sémaphores et messages) sont puissantes, mais encore difficiles d'utilisation. Les suivantes sont plus simples d'emploi.
Une variable partagée est déclarée par :
var v : shared T;
et ne peut être utilisée que de la façon suivante :
region v when B do S;
Les variables manipulées dans la section critique sont rassemblées dans une structure v déclarée partagée.
debut
tant que vrai faire debut
region v when true do
Section Critique;
Section Non Critique
fin
fin
Le risque, pour l'utilisateur, d'erreur d'entrelacement est nettement diminué.
Définition : Un moniteur comprend des
variables, des conditions, des procédures et un code
d'initialisation. Seules les procédures peuvent être manipulées par
les processus, et le mécanisme du moniteur garantit l'exécution de
chaque procédure en exclusion mutuelle.
Syntaxe d'un moniteur
type nom du moniteur = monitor
déclarations de variables
déclarations de conditions
procedure entry P1(...)
begin ...end;
procedure entry Pn(...)
begin ...end;
begin
code d'initialisation
end.
La synchronisation des processus est obtenu à l'aide des procédures wait et signal appliquées sur les variables de type condition. L'action X.signal provoque le réveil de tous les processus qui ont auparavant effectué X.wait.
Une solution au problème de la section critique
type SectionCritique = monitor
token : booleen;
sc : condition
procedure entry EntreeSC
begin
while not token do sc.wait;
token := false;
end;
procedure entry SortieSC
begin
token := true;
sc.signal;
end;
begin
token := true
end.
shared var SC = SectionCritique
Code des processus
begin
while true do begin
code de la section non critique
SC.EntreeSC;
code de la section critique
SC.SortieSC
end
end.
Par exemple, il est possible d'implémenter une région critique conditionnelle à l'aide des sémaphores mutex(1,vide), delai1(0,vide) et delai2(0,vide), et des entiers compteur1 et compteur2 initialisés à 0.
debut
wait(mutex);
tant que non B faire debut
compteur1 := compteur1 + 1;
si compteur2 > 0 alors
signal(delai2);
sinon
signal(mutex);
wait(delai1);
compteur1 := compteur1 - 1;
compteur2 := compteur2 + 1;
si compteur1 > 0 alors
signal(delai1);
sinon
signal(delai2);
wait(delai2);
compteur2 := compteur2 - 1;
fin;
S;
si compteur1 > 0 alors
signal(delai1);
sinon
si compteur2 > 0 alors
signal(delai2);
sinon
signal(mutex);
fin
Il existe plusieurs problèmes de synchronisation de processus qui permettent de valider, et de comparer les facilités d'utilisation des différents mécanismes.
Un producteur dépose des messages dans un buffer, duquel un comsommateur les retire. La synchronisation doit satisfaire les points suivants :
Un objet est partagé par des lecteurs qui veulent connaître sa valeur, et des rédacteurs qui peuvent modifier sa valeur.
N philosophes alternativement pensent et mangent. Pour manger, ils disposent d'une table circulaire ayant N assiettes et N fourchettes.
Il n'existe pas de contrôle possible pour ce problème sans faire d'hypothèses supplémentaires. (priorité, accès limité à N-1 à la table).