Systeme d’exploitation

Systeme d’exploitation

POLYTECH’MONTPELLIER Systeme d’exploitation 2 IG4 ? 2008/2009 POLYTECH’MONTPELLIER  Systeme d’exploitation – IG4 2008/2009 D’apres le cours de Mlle. Cart. Page 2 POLYTECH’MONTPELLIER  Systeme d’exploitation – IG4 2008/2009 SOMMAIRE CHAPITRE 1 – INTRODUCTION A LA PROGRAMMATION PARALLELE ……………………………………………………………… 6  1. 1. 1. 2. Definition ………………………………………………………………………………………………………………… 7  Champs d’application et motivations  ………………………………………………………………………….   . Parties de programme independantes …………………………………………………………………. 7  Simulation ………………………………………………………………………………………………………… 8  Controle de processus industriel …………………………………………………………………………. 8  Systeme d’exploitation ………………………………………………………………………………………. 8  1. 2. 1. 1. 2. 2. 1. 2. 3. 1. 2. 4. 1. 3. 1. 4.

Systeme de traitement par lot (batch processing) ………………………………………………………… 8  Sommaire ……………………………………………………………………………………………………………… 10 CHAPITRE 2 – PROCESSUS …………………………………………………………………………………………………………… 11  2. 1. 2. 2. 2. 3. 2. 4. 2. 5. 2. 6. 2. 7. Preliminaires ………………………………………………………………………………………………………….. 2  Definition d’un processus ………………………………………………………………………………………… 12 Ressources d’un processus ………………………………………………………………………………………. 12  Etats d’un processus ……………………………………………………………………………………………….. 12  Contexte d’un processus (en un point d’observation) …………………………………………………. 13  Ensemble de processus et parallelisme …………………………………………………………………….. 3  Operation elementaires sur les processus …………………………………………………………………. 13  Existence : creation/destruction ……………………………………………………………………….. 13  Competition, cooperation ………………………………………………………………………………… 13 2. 7. 1. 2. 7. 2. 2. 8. 2. 9. Apercu de la mise en ? uvre des processus ……………………………………………………………….. 14  Annexe : creation et terminaison de processus sous UNIX  ………………………………………….. 5  . Creation de processus ……………………………………………………………………………………… 15  Terminaison de processus ………………………………………………………………………………… 16  Attente de la terminaison d’un processus ………………………………………………………….. 16 2. 9. 1. 2. 9. 2. 2. 9. 3. CHAPITRE 3 – EXCLUSION MUTUELLE ……………………………………………………………………………………………… 17  3. 1.

Presentation du probleme ………………………………………………………………………………………. 18  Necessite de l’exclusion mutuelle ……………………………………………………………………… 18  Position du probleme ………………………………………………………………………………………. 19  Exclusion mutuelle elementaire (materielle) ………………………………………………………. 19 3. 1. 1. 3. 1. 2. 3. 1. 3. D’apres le cours de Mlle. Cart. Page 3

POLYTECH’MONTPELLIER  Systeme d’exploitation – IG4 2008/2009    Solutions logicielles ………………………………………………………………………………………………… 19  Exclusion mutuelle entre deux processus, Algorithme de DEKKER (1965) ………………. 19  Exclusion mutuelle entre   processus ……………………………………………………………….. 21 3. 2. 3. 2. 1. 3. 2. 2. 3. 3. Solutions materielles ………………………………………………………………………………………………. 1  Machine monoprocesseur  ……………………………………………………………………………….. 21  . Machine a   processeurs,   …………………………………………………………………….. 21 3. 3. 1. 3. 3. 2. 3. 4. 3. 5. Comment diminuer l’attente active ? ……………………………………………………………………….. 22  Verrou [lock] ………………………………………………………………………………………………………….. 3  Presentation …………………………………………………………………………………………………… 23  Utilisation : exclusion mutuelle …………………………………………………………………………. 23 3. 5. 1. 3. 5. 2. 3. 6. Semaphore [semaphore] …………………………………………………………………………………………. 24  Presentation …………………………………………………………………………………………………… 24 3.

Désolé, mais les essais complets ne sont disponibles que pour les utilisateurs enregistrés

Choisissez un plan d'adhésion
6. 1. 3. 7.

Difficultes de l’exclusion mutuelle ……………………………………………………………………………. 25  Sections critiques imbriquees …………………………………………………………………………… 25 Risque de privation ………………………………………………………………………………………….. 25  Pas de garde? fous ……………………………………………………………………………………………. 26 3. 7. 1. 3. 7. 2. 3. 7. 3. 3. 8. Annexe : mise en ? vre des primitives de synchronisation  ………………………………………… 26  . CHAPITRE 4 – SYNCHRONISATION ………………………………………………………………………………………………….. 27  4. 1. Presentation du probleme ………………………………………………………………………………………. 28  Necessite de la synchronisation ………………………………………………………………………… 28  Insuffisance des operations activer/bloquer pour assurer la synchronisation …………. 28 4. 1. 1. 4. 1. 2. 4. 2. 4. 3.

Synchronisation par semaphore ………………………………………………………………………………. 29  Synchronisation par evenement ………………………………………………………………………………. 31  Evenements memorises …………………………………………………………………………………… 31  Evenement non memorise ……………………………………………………………………………….. 31 4. 3. 1. 4. 3. 2. 4. 4. Le probleme des lecteurs et des redacteurs ………………………………………………………………. 1  Presentation du probleme ……………………………………………………………………………….. 31  Modelisation du probleme ……………………………………………………………………………….. 32  Strategies de service possible …………………………………………………………………………… 32 4. 4. 1. 4. 4. 2. 4. 4. 3. CHAPITRE 5 – COMMUNICATION …………………………………………………………………………………………………… 34  5. 1.

Introduction …………………………………………………………………………………………………………… 35 D’apres le cours de Mlle. Cart. Page 4 POLYTECH’MONTPELLIER  Systeme d’exploitation – IG4 2008/2009    5. 2. Communication  par  acces  a  des  variables  partagees  et  primitives  de  synchronisation  (semaphores)  …………………………………………………………………………………………………………………… 36  . 5. 3. Primitives adaptees a la communication …………………………………………………………………… 8  Presentation …………………………………………………………………………………………………… 38  Synchronisation sous? jacente a la communication ………………………………………………. 38  Designation de la destination et de la provenance ………………………………………………. 39 5. 3. 1. 5. 3. 2. 5. 3. 3. 5. 4. ANNEXE – Utilisation des tubes dans UNIX ………………………………………………………………… 41  Creation d’un tube [pipe] …………………………………………………………………………………. 1  Lecture …………………………………………………………………………………………………………… 41  Ecriture ………………………………………………………………………………………………………….. 41  Fermeture d’un tube ……………………………………………………………………………………….. 42 5. 4. 1. 5. 4. 2. 5. 4. 3. 5. 4. 4. CHAPITRE 6 – LANGAGES CONCURRENTS …………………………………………………………………………………………. 43  6. 1. 6. 2. 6. 3. 6. 4.

Modularite …………………………………………………………………………………………………………….. 44 Synchronisation ……………………………………………………………………………………………………… 44  Modele producteur? consommateur …………………………………………………………………………. 46  Java : partage d’objet entre activites concurrentes …………………………………………………….. 47 D’apres le cours de Mlle. Cart. Page 5 POLYTECH’MONTPELLIER  Systeme d’exploitation – IG4 2008/2009 CHAPITRE 1 – INTRODUCTION A

LA PROGRAMMATION  PARALLELE D’apres le cours de Mlle. Cart. Page 6 POLYTECH’MONTPELLIER  Systeme d’exploitation – IG4 2008/2009 1. 1. Definition Jusqu’a  maintenant,  on  a  etudie  et  fait  des  programmes  sequentiels. Desormais,  on  va  mettre  en  ? uvre des programmes paralleles. 1. 2. Champs d’application et motivations 1. 2. 1. Parties de programme independantes Sequentiellement : debut t1 t2 t3 t4 t5 fin := := := := := a+b ; c+d ; t1xt2 ; e/f ; t3-t4 ; / En parallele : debut t1:=a+b; t3:=t1xt2; t4:=t3-t4; fin t2:=c+d; t4:=e/f; Hypothese sur le langage concurrent : pardebut a1; a2; a3; parfin a1//a2//a3 D’apres le cours de Mlle.

Cart. Page 7 POLYTECH’MONTPELLIER  Systeme d’exploitation – IG4 2008/2009 debut pardebut debut pardebut t1:=a+b; t2:=c+d; parfin t3:=t1xt2; fin t4:=e/f; parfin t5:=t3-t4; fin 1. 2. 2. Simulation  L’interet est de modeliser, d’avoir une meilleure qualite. 1. 2. 3. Controle de processus industriel  Le  nombre  de  processus  n’est  pas  important,  on  ameliore  la  qualite  du  programme  et  on  peut  le  maintenir plus facilement. A la difference de la simulation, on a ici la contrainte du temps reel. 1. 2. 4. Systeme d’exploitation  Motivations :   technologie :  UE(unite d’echange) // UC  systemes multiprocesseurs  systemes repartis . 3. Systeme de traitement par lot (batch processing) UC 2 lecteur de carte imprimante UE debit faible 1 Memoire  centrale UE 3 debit faible UE debit faible D’apres le cours de Mlle. Cart. Page 8 POLYTECH’MONTPELLIER  Systeme d’exploitation – IG4 2008/2009    Mise en ? uvre par un programme sequentiel Programme de traitement par lot debut repeter lire un travail ; executer le travail ; imprimer les resultats ; sans fin fin UE cartes  UC  UE imprimante                 File des travaux  File des resultats ENTREE  TRAVAIL SORTIE programme ENTREE debut repeter lire un travail deposer le travail dans la file des travaux sans fin fin rogramme TRAVAIL debut repeter retirer travail de la file des travaux executer travail deposer resultat dans la file des resultats sans fin fin D’apres le cours de Mlle. Cart. Page 9 POLYTECH’MONTPELLIER  Systeme d’exploitation – IG4 2008/2009 programme SORTIE debut repeter retirer resultat de la file des resultats imprimer les resultats sans fin fin Les trois programmes ne sont pas independants  b) Donnees communes  c) Relation producteur consommateur 1. 4. • • • • • Sommaire Chapitre 2. Processus  Chapitre 3. Exclusion mutuelle  Relations entre  Chapitre 4. Synchronisation  processus  Chapitre 5. Communication  Chapitre 6.

Langages concurrents (notion de moniteur, Java) D’apres le cours de Mlle. Cart. Page 10 POLYTECH’MONTPELLIER  Systeme d’exploitation – IG4 2008/2009 CHAPITRE 2 – PROCESSUS D’apres le cours de Mlle. Cart. Page 11 POLYTECH’MONTPELLIER  Systeme d’exploitation – IG4 2008/2009 2. 1. Preliminaires Memoire centrale processeurs,  1 Rappel : Instructions  Donnees  Pile (Memoire commune) Hypothese : le nombre de processeurs n’est pas limite. 2. 2. Definition d’un processus Chaque  processus  est  identifie  par  un  numero,  et  est  compose  de  trois  segments :  Instructions,  donnees, code. 2. 3. Ressources d’un processus

On peut les ranger en deux categories :  d) physiques (processeur, memoire centrale…)  e) logiques (fichier, donnee, evenement…) Une ressource possede des points d’acces. Si  une ressource possede un seul  point d’acces, il s’agit  d’une ressource critique qui doit etre utilisee en exclusion mutuelle. Il peut y avoir un probleme de competition entre processus pour l’acces a une ressource critique. Pour  les  ressources  physiques,  le  systeme  d’exploitation  gere  la  competition  de  maniere  transparente. Pour les ressources logiques, il y a deux cas : certaines sont gerees par le systeme, d’autres doivent  l’etre par le programmeur. . 4. Etats d’un processus f) Elu  g) Eligible  h) Bloque Processus p     lire_ligne ;     traitement_ligne ; p passe dans l’etat bloque fin d’ES, p passe dans  l’etat eligible. D’apres le cours de Mlle. Cart. Page 12 POLYTECH’MONTPELLIER  Systeme d’exploitation – IG4 2008/2009 2. 5. Contexte d’un processus (en un point d’observation) Le contexte regroupe toutes les informations necessaires pour la reprise d’un processus. Ces informations sont :  i) j) k) l) m) l’etat  l’adresse de reprise  les variables du programme  les ressources allouees, fichiers ouverts…  les droits 2. 6.

Ensemble de processus et parallelisme Parallelisme a l’execution. Hypothese : deux processus p et q. Execution des processus :              Soit en execution parallele (deux processeurs)        p  q  Soit execution sequentielle  p  q Soit en pseudo parallelisme (depend du niveau d’observation)  p  q  p  q 2. 7. Operation elementaires sur les processus 2. 7. 1. Existence : creation/destruction  Creer un processus :  n) creer le contexte initial par l’appel d’un autre processus    Detruire un processus :  o) autodestruction  p) destruction a l’initiative du systeme ou d’un autre processus  2. . 2. Competition, cooperation  q) Blocage de processus : bloquer(p : nom_processus) //Met le processus p dans l’etat bloque  r) Activer un processus : activer(p : nom_processus) //Met le processus dans l’etat actif D’apres le cours de Mlle. Cart. Page 13 POLYTECH’MONTPELLIER  Systeme d’exploitation – IG4 2008/2009    Exemple : gestion des E/S  p :    lire_ligne ;        traitement de la ligne ; lancement E/S    bloquer(p) ;  fin d’E/S    activer(p) ; 2. 8. Apercu de la mise en ? uvre des processus La partie du systeme d’exploitation qui met en ? uvre les processus est le noyau.

On execute du code  du  noyau  suite  a  un  appel  systeme,  un  deroutement  ou  une  interruption. Il  se  alors  produit  une  commutation de mot d’etat. Le noyau gere le mecanisme de descripteur de processus. s) sauvegarde du contexte du processus elu sur le processeur interrompu  t) allouer processeur                                            SE  Noyau Materiel noyau materiel t  P1 Noyau  P2 Noyau  P3 Noyau  P1 commutation  de processus D’apres le cours de Mlle. Cart. Page 14 POLYTECH’MONTPELLIER  Systeme d’exploitation – IG4 2008/2009 2. 9.

Annexe : creation et terminaison de processus sous UNIX 2. 9. 1. Creation de processus  On va utiliser l’appel systeme suivant : fonction fork:entier ; var pid:entier ; pid:=fork ; imprimer(pid); –Affiche 4907 et 0, on ne peux pas savoir dans quel ordre Resultat :  u) si la creation ne s’est pas faite : ? 1  v) si la creation s’est faite :  le processus fils recupere la valeur 0  le  processus  pere  recupere  une  valeur  positive  qui  correspond  a  l’identite  du  processus fils Descripteur fils pid 0  pid 4807 Descripteur pere Instructions Donnees Pile Donnees Pile

Les  donnees  du  processus  fils  sont  la  copie  des  donnees  du  pere,  la  pile  du  processus  fils  est  une  copie de la pile du pere. Schema general d’utilisation : var pid:entier; pid:=fork; si pid=0 alors –Processus fils programme execute par le fils sinon –processus pere –pid: identite du fils /-1 si pid=-1 alors –le fils n’a pas pu etre cree instructions 1 sinon –le fils a ete cree correctement instructions 2 D’apres le cours de Mlle. Cart. Pere  fork  Pere  Fils Page 15 POLYTECH’MONTPELLIER  Systeme d’exploitation – IG4 2008/2009    2. 9. 2. Terminaison de processus  2. . 2. 1. 2. 9. 2. 2. Autodestruction  Destruction d’un autre processus fonction exit(etat:entier) :entier fonction kill(pid, signal :entier) :entier Cette  fonction  permet  de  signaler  un  evenement  a  un  processus. Entre  autres,  le  signal  SIGINT  de  valeur 2 signifie qu’on veut detruire le processus. SIGKILL, SIGTERM…  Un processus peut traiter un evenement de plusieurs facons :  w) en l’interceptant  x) en le masquant  y) en laissant le systeme faire l’action par defaut correspondante  2. 9. 3. Attente de la terminaison d’un processus fonction wait(var etat :entier) :entier

Resultat :  z) S’il n’y a plus de processus fils vivant, le processus pere recupere ? 1. aa) Sinon, le processus recupere le pid du fils qui a termine son execution. La vie d’un processus :      Creation  fork Terminaison  exit, kill Wait  execute par  le pere Vivant tant que wait(etat)? pidfils faire; –On attend un fils particulier tant que wait(etat)? 0 faire; –On attend tous les fils D’apres le cours de Mlle. Cart. Page 16 POLYTECH’MONTPELLIER  Systeme d’exploitation – IG4 2008/2009 CHAPITRE 3 – EXCLUSION  MUTUELLE D’apres le cours de Mlle. Cart. Page 17 POLYTECH’MONTPELLIER  Systeme d’exploitation – IG4 2008/2009 . 1. Presentation du probleme 3. 1. 1. Necessite de l’exclusion mutuelle  Exemple 1 : Soit deux processus p et q. var commune, partagee      n :entier ;  processus q  : n :=n+   1’ load R2,n  2’ add R2,    3’ store R2,n processus p  : n :=n+     1 load R1,n    2 add R1,      3 store R1,n L’ordre  d’execution  1  1’  2’  3’  2  3  pose  probleme,  la  variable    etant  commune,  un  conflit  se  pose  entre les deux executions. On doit imposer que les deux executions ne s’entrelacent pas : execution  en exclusion mutuelle. On dit aussi qu’il faut serialiser   et  .

Les sequences qui doivent s’executer en exclusion mutuelle se nomment des sections critiques. Exemple 2 : liste simplement chainee, insertion en tete. premier    suiv  suiv 4  1  suiv 2 3            processus p  1 e. suiv:=premier;  4 premier:=e;    Ici, la valeur f sera perdue ! processus q  2 f. suiv:=premier  3 premier :=f ; suiv D’apres le cours de Mlle. Cart. Page 18 POLYTECH’MONTPELLIER  Systeme d’exploitation – IG4 2008/2009      3. 1. 2. Position du probleme  On a   processus   avec  ,           Proprietes de la solution :   a) A tout instant, un processus au plus peut se trouver en section critique. ) Si plusieurs processus sont en attente d’entree en section critique alors qu’aucun processus  ne se trouve en section critique, l’un d’eux doit pouvoir y entrer au bout d’un temps fini. c) Si un processus est hors de la section critique et du protocole qui la controle, il ne doit pas  empecher un autre processus d’entrer en section critique. d) La solution doit etre la meme pour tout le monde. 3. 1. 3. Exclusion mutuelle elementaire (materielle)  Elle s’exprime en deux points :  ? ? Un  processeur :  toute  instruction  commencee  va  jusqu’a  bout  ? gt;  indivisibilite  d’une  instruction. Multiprocesseurs : les acces simultanes au meme mot memoire sont serialises (garanti par le  fabriquant). Initialisation  processus    demande d’entree  section critique  sortie  processus    demande d’entree  section critique  sortie    0,1 … 1}. Les  solutions  peuvent  etre  logicielles,  materielles  ou  mixtes. Les  solutions  logicielles  ne  sont  pas  utilisees en pratique. 3. 2. Solutions logicielles 3. 2. 1. Exclusion mutuelle entre deux processus, Algorithme de DEKKER (1965)  Algorithme 1 ar partagee :drapeau :booleen — initialise a faux — drapeau=vrai un processus est en section critique : tant que drapeau faire rien ; drapeau :=vrai ; section critique drapeau=faux ; D’apres le cours de Mlle. Cart. Page 19 POLYTECH’MONTPELLIER  Systeme d’exploitation – IG4 2008/2009 Cette solution ne fonctionne pas puisque si   perd le processeur juste apres le tant que, il y pourrait  y avoir une erreur au retour sur ce processus. Algorithme 2 var partagee tour (0.. 1) — tour=i le processus peut entrer en section critique  : tant que tour=j faire rien ; section critique tour:=j ; Ici,  on  a  bien  exclusion  mutuelle.

Cependant,  cette  solution  exige  que  les  processus  entrent  en  section critique en alternance. Algorithme 3 var partagee drapeau :tableau[0.. 1] de booleen — drapeau[i]=vrai est en section critique. Initialement, les deux elements du tableau sont a faux. — drapeau[i]=faux n’est pas en section critique,  peut entrer en section critique. : tant que drapeau[j] faire rien; drapeau[i]:=vrai; section critique drapeau[i]:=faux; Meme  probleme  que  dans  l’algorithme  1,  on  ne  garanti  pas  l’exclusion  mutuelle. Cependant  on  remarque que   leve son drapeau en sortie de boucle, et c’est trop tard.

Algorithme 4 var partagee drapeau :tableau[0.. 1] de booleen — Initialement a faux. — drapeau[i]=vrai est en section critique ou demande a y entrer. : drapeau[i]:=vrai; tant que drapeau[j] faire rien; section critique drapeau[i]:=faux; Cette solution garanti l’exclusion mutuelle. Algorithme 5 var partagee drapeau :tableau[0.. 1] de booleen — Initialement a faux. — drapeau[i]=vrai est en section critique ou demande a y entrer. : drapeau[i]:=vrai; tant que drapeau[j] faire debut drapeau[i]:=faux; tant que drapeau[j] faire rien ; drapeau[j] :=vrai ; fin section critique drapeau[i]:=faux;

D’apres le cours de Mlle. Cart. Page 20 POLYTECH’MONTPELLIER  Systeme d’exploitation – IG4 2008/2009    Cette solution est problematique si les deux processus font la meme action au « meme » moment. Algorithme 6 var partagee drapeau :tableau[0.. 1] de booleen — Initialement a faux. — drapeau[i]=vrai est en section critique ou demande a y entrer. tour: (0,1); — Initial 0 ou 1 ;  : drapeau[i]:=vrai; tant que drapeau[j] faire si tour=j alors debut drapeau[i]:=faux; tant que tour=j faire rien ; drapeau[j] :=vrai ; fin section critique drapeau[i]:=faux; tour=j ; Exclusion mutuelle, sans blocage mutuel  3. 2. 2.

Exclusion mutuelle entre   processus  Generalisation de l’algorithme de DEKKER par DIJKSTRA(1965), mais risque de privation. Apparition  de  solutions  equitables. La  premiere  garantissait  2   tours  avant  qu’un  processus    soit  elu,  la  suivante  puis finalement  1 tours. 3. 3. Solutions materielles instructions specialisees 3. 3. 1. Machine monoprocesseur          3. 3. 2. Machine a   processeurs,  3. 3. 2. 1. Principe: fonction indivisible Test_and_set(var drapeau:booleen):booleen; debut Test_and_set:=drapeau; drapeau:=vrai; fin; :  masquer les interruptions  section critique  demasquer les interruptions

Solution  exploitee  uniquement  dans  le  systeme  d’exploitation,  car  un  programme  utilisateur  pourrait  boucler  en  section  critique  et  ne  pourrait plus etre interrompu. Test_and_set Le  fabriquant  assure  que  la  lecture  et  l’ecriture  seront  indivisibles :  elles  seront  obligatoirement  serialisees. D’apres le cours de Mlle. Cart. Page 21 POLYTECH’MONTPELLIER  Systeme d’exploitation – IG4 2008/2009    Utilisation :  Algorithme 1 : var drapeau: booleen initial(faux) ; — drapeau=vrai un processus est en section critique ;  : tant que drapeau faire rien ; drapeau[j] :=vrai ; section critique drapeau[i]:=faux; ant que Test_and_set(drapeau) faire rien ; 3. 3. 2. 2. Principe: fonction indivisible Swap(var a,b:booleen) var temp:booleen; debut temp:=a; a:=b; b:=temp; fin; Swap Utilisation: var partagee verrou: booleen; — verrou=vrai un processus en section critique processus pi : var locale : cle : booleen ; cle :=vrai ; tant que cle faire Swap(cle, verrou) ; Section critique verrou :=faux ; 3. 4. Comment diminuer l’attente active ? On va considerer qu’un processus voulant entrer en section critique et ne pouvant pas, veut en fait  une ressource non disponible. On va donc le faire passer en etat bloque afin qu’il ne monopolise pas e processeur. var partagee drapeau: booleen; — initialiser a faux — drapeau=vrai un processus en section critique F : file_de_processus ; type file_de_processus ; entrer(p:nom_processus, F :file de processus) ; sortir(q:nom_processus, F :file_de_processus) ; demande d’entree si non drapeau alors drapeau:=vrai ; sinon — Soit p le processus qui execute le code debut entree(p,F) ; bloquer(p) ; fin section critique D’apres le cours de Mlle. Cart. Page 22 POLYTECH’MONTPELLIER  Systeme d’exploitation – IG4 2008/2009 sortie Si sinon alors drapeau:=faux ; debut sortir(q,F) ; –choix de q dans F activer(q) ; fin . 5. Verrou [lock] 3. 5. 1. Presentation  Le type verrou definit deux operations :   ? Verrouiller [lock]  ? Deverrouiller [unlock]  Ces deux operations sont indivisibles, elles seront donc executees en exclusion mutuelle. Effets des operations : exemple d’implementation type verrou = structure val : booleen ; F : file de processus ; fin ; var V verrou ; conditions initiales V. val=faux V. F=  ; Verouiller(V) : si non V. val alors V. val:=vrai ; sinon — Soit p le processus qui execute le code debut entree(p,V. F) ; bloquer(p) ; fin Deverrouiller(V) : Si . alors V. al:=faux ; sinon debut sortir(q,V. F) ; –choix de q dans F activer(q) ; fin 3. 5. 2. Utilisation : exclusion mutuelle n processus var partagee : V. verrou ;  : Verrouiller(V) ; section critique Deverouiller(V) ; D’apres le cours de Mlle. Cart. Page 23 POLYTECH’MONTPELLIER  Systeme d’exploitation – IG4 2008/2009    Exemple :                var   :entier ;  V. verrou    processus p  Verrouiller( ) ;  n :=n+  ;  Deverrouiller( ) ;    Verrouiller( ) ;  l :=l+  ;  Deverrouiller( ) ; processus q  Verrouiller( ) ;  n :=n+  ;  Deverrouiller( ) ;    Verrouiller( ) ;  l :=l+  ;  Deverrouiller( ) ; . 6. Semaphore [semaphore] 3. 6. 1. Presentation  Le type semaphore definit deux operations :  ? ? P(Passeren) Puis? je ? V(Vrygeven) Vas? y ! Effet des operations P et V : exemple d’implementation type semaphore = structure Val :entier ; F : file_de_processus ; fin var S :semaphore initial ( ) condition initiales S. val 0 S. F= P(S) : S. val :=S. val-1 ; si S. val0 alors V(tous_la); V(mutex);  ; On  constate  que  la  sequence  encadree  peut  etre  executee  par    processus  mais  jamais  en  meme  temps,  les  processus  etant  reveilles  les  uns  apres  les  autres.

On  n’a  donc  pas  besoin  de  section  critique : on peut ne pas ecrire le dernier P(mutex) et le dernier V(mutex). Variantes de semaphores. Certains  systemes  permettent  d’executer  une  operation  P  sur  un  ensemble  de  semaphores :  ;  Attention :  cette  operation  est  differente  de  ;.. ;    car  l’operation  , .. ; precedente permet de franchir soit tous les semaphores, soit aucun. L’operation  ; est  , .. ;.. ;    ; identique  a  On peut aussi avoir une operation P conditionnelle :  , e .

Cette operation n’est pas  bloquante, et on fait le P si le semaphore n’est pas bloquant. On recupere le resultat de l’operation  dans la variable resultat. D’apres le cours de Mlle. Cart. Page 30 POLYTECH’MONTPELLIER  Systeme d’exploitation – IG4 2008/2009    Attention, mal utilises, les semaphores peuvent creer un inter? blocage. 4. 3. Synchronisation par evenement Quand on utilise un objet  du  type evenement, on  peut  utiliser les operations  attendre  et signaler. Les  evenements  permettent  de  resoudre  les  problemes  de  synchronisation  de  maniere  beaucoup  plus intuitive.

Il existe deux types d’evenements : les memorises et les non memorises. 4. 3. 1. Evenements memorises  Quand un evenement se produit et qu’il n’est pas attendu par un processus, il est memorise. Exemple :    autorisation_lecture : evenement_memorise;      processus p  processus q      attendre(autorisation_lecture);  ecrire(x) ;  lire(x) ;    signaler(autorisation_lecture);      4. 3. 2. Evenement non memorise  Un evenement qui se produit sans etre attendu est perdu. Exemple : var partagees : tous_la: evenement_non_memorise ; nb : entier initial (0) ;  : e ; nb:=nb+1; Si nb