COURS SYSTEME DEXPLOITATION II

UNIV IBN KHALDOUNE - TIARET

Version non corrige

Systme d'exploitation II 2

Cours 1 :

Gnralits sur les systmes dexploitation

1.Schma d'un systme informatique

Les logiciels peuvent tre classs en deux catgories : - les programmes d'application des utilisateurs - les programmes systme qui permettent le fonctionnement de l'ordinateur. Parmi ceux-ci, le systme d'exploitation (SE dans la suite).

Le SE soustrait le matriel au regard du programmeur et offre une prsentation agrable des fichiers. Un SE a ainsi deux objectifs principaux :

- prsentation : Il propose l'utilisateur une abstraction plus simple et plus agrable que le matriel : une machine virtuelle

- gestion : il ordonne et contrle l'allocation des processeurs, des mmoires, des icnes et fentres, des priphriques, des rseaux entre les programmes qui les utilisent. Il assiste les programmes utilisateurs. Il protge les utilisateurs dans le cas d'usage partag.

2. ELEMENTS DE BASE D'UN SYSTEME D'EXPLOITATION

Les principales fonctions assures par un SE sont les suivantes :

- gestion de la mmoire principale et des mmoires secondaires, - excution des E/S faible dbit (terminaux, imprimantes) ou haut dbit (disques, bandes), - multiprogrammation, temps partag, paralllisme : interruption, ordonnancement, rpartition en mmoire, partage des donnes - lancement des outils du systme (compilateurs, environnement utilisateur,...) et des outils pour l'administrateur du systme (cration de points d'entre, modification de privilges,...), - lancement des travaux, - protection, scurit ; facturation des services, - rseaux

Systme d'exploitation II 3

L'interface entre un SE et les programmes utilisateurs est constitue d'un ensemble d'instructions tendues, spcifiques d'un SE, ou appels systme. Gnralement, les appels systme concernent soit les processus, soit le systme de gestion de fichiers (SGF).

3- Les differentes classes des SE

- systmes a machines individuelles: gestion de l information, excution des pgs - systmes

transactions: ex:

systmes

bancaires, systmes de rservation

inconvnient : simultanit cohrence

- systmes de commande: enregistrement, rgulation, scurit - systmes a temps partage: un ensemble de services, un ensemble dusagers pbs :

partage et allocation des ressources, gestion des infos partage

- systmes a temps rel et a temps diffr telephonie, mail

Avec la grande diffusion des micro-ordinateurs, l'volution des performances des rseaux de tlcommunications, deux nouvelles catgories de SE sont apparus :

- les SE en rseaux : ils permettent partir d'une machine de se connecter sur une machine distante, de transfrer des donnes. Mais chaque machine dispose de son propre SE

- les SE distribus ou rpartis : l'utilisateur ne sait pas o sont physiquement ses donnes, ni o s'excute son programme. Le SE gre l'ensemble des machines connectes. Le systme informatique apparat comme un mono-processeur.
- Les SE embarques

Un systme embarqu peut tre dfini comme un systme

lectronique et informatique autonome, qui est ddi une tche bien prcise. Ses ressources disponibles sont gnralement limites. Cette limitation est gnralement d'ordre spatial (taille limite) et nergtique (consommation restreinte).

Systme d'exploitation II 4

Chapitre I : notions sur les processus et la concurrence

Cours 2 :Processus et ressources

1.Introduction
Deux processus sont concurrents sils existent en mme temps

Les processus concurrents sexcutant dans le systme dexploitation peuvent tre des processus coopratifs ou indpendants. Un systme d'exploitation dispose de ressources (imprimantes, disques, mmoire, fichiers, base de donnes, ...), que les processus peuvent vouloir partager.

Ils sont alors en situation de concurrence (race) vis--vis des ressources. Il faut synchroniser leurs actions sur les ressources partages.

2. Actualit de la concurrence
La concurrence entre processus est un sujet de grande actualit pour plusieurs raisons. 1. L'volution des systmes personnels : Dos, Windows, Mac, fait passer ceux-ci d'une organisation mono processus des systmes multiprogramms. 2. Les systmes classiques, MVS, AS 400 (IBM), VMS (Digital) , Solaris (Sun), Unix, Linux, qui sont multiprogramms ds leur conception continuent se dvelopper et sont de plus en plus souvent multiprocesseurs. 3. Les applications temps rel, embarques, enfouies, se dveloppent et requirent des systmes temps rel multiprocessus (on dit, dans ce mtier, des excutifs multitches) 4. Les applications rparties se multiplient et chacun peut dsormais crire ou utiliser des processus concurrents distance avec des applets ou des servlets Java. Les systmes d'architecture client-serveur, les architectures rparties base d'objets ou de

Systme d'exploitation II 5

composants vont aussi dans le sens d'une augmentation du nombre des processus concurrents. 5. Enfin, les clients nomades, les plates-formes mobiles, ne peuvent fonctionner sans utiliser des processus mandataires ou proxys qui sont leurs reprsentants sur les serveurs fixes de ressource. La connaissance des bons comportements et des bonnes mthodes de programmation et d'utilisation de ces processus concurrents est indispensable.

3. Les processus
Un processus est un programme qui s'excute, ainsi que ses donnes, sa pile, son compteur ordinal, son pointeur de pile et les autres contenus de registres ncessaires son excution.

Un processus est un programme en mmoire pour tre excut.

Dans une entit logique unique, gnralement un mot, le SE regroupe des informations-cls sur le fonctionnement du processeur : c'est le mot d'tat du processeur PSW, Il comporte gnralement :

- la valeur du compteur ordinal - des informations sur les interruptions (masques ou non) - le privilge du processeur (mode matre ou esclave) - etc.... (format spcifique un processeur)

A chaque instant, un processus est caractris par son tat courant : c'est l'ensemble des informations ncessaires la poursuite de son excution (valeur du compteur ordinal, contenu des diffrents registres,

informations sur l'utilisation des ressources). A cet effet, tout processus, on associe un bloc de contrle de processus (BCP). Il comprend gnralement :

- une copie du PSW au moment de la dernire interruption du processus - l'tat du processus : prt tre excut, en attente, suspendu, ... - des informations sur les ressources utilises

Systme d'exploitation II 6

- mmoire principale - temps d'excution - priphriques d'E/S en attente - files d'attente dans lesquelles le processus est inclus, etc... - et toutes les informations ncessaires pour assurer la reprise du processus en cas d'interruption

Les BCP sont rangs dans une table en mmoire centrale cause de leur manipulation frquente.

4.* Les interruptions *)

Une interruption est une commutation du mot d'tat provoque par un signal gnr par le matriel. Ce signal est la consquence d'un vnement interne au

processus, rsultant de son excution, ou bien extrieur et indpendant de son excution.

5. Les ressources
On appelle ressource tout ce qui est ncessaire l'avancement d'un processus (continuation ou progression de l'excution) : processeur, mmoire, priphrique, bus,

rseau, compilateur, fichier, message d'un autre processus, etc... Un dfaut de ressource peut provoquer la mise en attente d'un processus.

Un processus demande au SE l'accs une ressource. Certaines demandes sont implicites ou permanentes (la ressource processeur). Le SE alloue une ressource un

processus. Une fois une ressource alloue, le processus a le droit de l'utiliser jusqu' ce qu'il libre la ressource ou jusqu' ce que le SE reprenne la ressource (on parle en ce cas de ressource premptible, de premption).

Une ressource est soit locale, soit commune

plusieurs processus

locale : utilise par un seul processus. Ex.: fichier temporaire, variable de programme. commune ou partageable . Ex. : disque, imprimante, fichier en lecture. Une ressource peut possder un ou plusieurs points d'accs un moment donn :

Systme d'exploitation II 7

* un seul :(accs exclusif) si elle ne peut tre alloue plus d'un processus la fois. On parle de ressource critique Ex: un lecteur de disquettes partag entre plusieurs utilisateurs. Une zone mmoire partage en criture entre plusieurs utilisateurs. * plusieurs points d'accs: (accs partag) par exemple, un fichier en lecture utilisable par plusieurs processus.

Le SE doit contrler l'utilisation des ressources dans une table indiquant si la ressource est disponible ou non, et, si elle est alloue, quel processus. A chaque ressource est associe une file d'attente, pointe par la table prcdente, contenant les BCP des processus qui l'attendent. Chaque fois qu'un nouveau processus fait une demande de la ressource et que cette dernire n'est pas disponible, son BCP est ajout en queue de la file d'attente. Lorsqu'une demande survient de la part d'un processus plus prioritaire que celui qui utilise la ressource, on empile l'tat de la ressource, on la retire au processus en cours pour l'attribuer par rquisition au processus prioritaire. Dans le cadre des ressources limites gres par le systme, il n'est pas toujours possible d'attribuer chaque processus, ds sa cration, toutes les ressources ncessaires. Il peut y avoir blocage .

6. L'ordonnancement
On appelle ordonnancement la stratgie d'attribution des ressources aux processus qui en font la demande. Diffrents critres peuvent tre pris en compte :

- temps moyen d'excution minimal - temps de rponse born pour les systmes interactifs - taux d'utilisation lev de l'UC - respect de la date d'excution au plus tard, pour le temps rel, etc...

Systme d'exploitation II 8

Cours 3 :
1 Paralllisme

Processus et Paralllisme

On appelle simultanit l'activation de plusieurs processus au mme moment. Si le nombre de processeurs est au moins gal au nombre de processus, on parle de simultanit totale ou vraie, sinon de pseudo-simultanit. pseudo-simultanit : c'est par exemple l'excution enchevtre de plusieurs processus sur un seul processeur. La simultanit est obtenue par commutation temporelle d'un processus l'autre sur le processeur. Si les basculements sont suffisamment frquents, l'utilisateur a l'illusion d'une simultanit totale.

Dans le langage de la programmation structure, on encadre par les mots-cls parbegin et parend les sections de tches pouvant s'excuter en parallle ou simultanment. Ex :

2.Etats de processus :
De faon simplifie, on peut imaginer un SE dans lequel les processus pourraient tre dans trois tats :

- lu : en cours d'excution. Un processus lu peut tre arrt, mme s'il peut poursuivre son excution, si le SE dcide d'allouer le processeur un autre processus

- bloqu : il attend un vnement extrieur pour pouvoir continuer (par exemple une ressource; lorsque la ressource est disponible, il passe l'tat "prt") - prt : suspendu provisoirement pour permettre l'excution d'un autre processus La gestion des interruptions, la suspension et la relance des processus sont l'affaire de l'ordonnanceur.

Systme d'exploitation II 9

3. MODELE DE REPRESENTATION DE PROCESSUS

2.1 Dcomposition en tches

On appelle tche une unit lmentaire de traitement ayant une cohrence logique. Si l'excution du processus P est constitue de l'excution squentielle des tches T1, T2,..., Tn, on crit : P = T1 T2...Tn A chaque tche Ti, on associe sa date de dbut ou d'initialisation d i et sa date de terminaison ou de fin fi. La relation Ti < Tj entre tches signifie que fi infrieur dj entre dates. Si on n'a ni Ti < Tj , ni Tj < Ti, alors on dit que Ti et Tj sont excutables en parallle. Une relation de prcdence peut tre reprsente par un graphe orient. Par exemple, la chane de tches S = (( T1, T2, T3), (Ti < Tj pour i infrieur j)) a pour graphe :

T1

T2

T3

2.2 Paralllisation de tches dans un systme de tches

La mise en parallle s'effectue par la structure algorithmique : parbegin ............ parend

exemple 1 :

Systme d'exploitation II 10
lir e a lir e b

c <- a * a

d <- b * b

e <- c + d

soit

debut parbegin lire a lire b parend parbegin ca*a db*b parend ec+d fin

exemple 2 : peut-on reprsenter le graphe suivant de tches par un programme parallle utilisant parbegin et parend ? exemple 2 : (systme S0)
T1 T2 T3 T4 T5 lire X lire Z X X+Z YX+Z afficher Y

Systme d'exploitation II 11

2. LE PROBLEME DE L'EXCLUSION MUTUELLE

Definitions

On appelle processus indpendants des processus ne faisant appel qu' des ressources locales. On appelle processus parallles pour une ressource des processus pouvant utiliser simultanment cette ressource. Lorsque la ressource est critique (ou en accs exclusif), on parle d'exclusion mutuelle (par exemple, sur une machine monoprocesseur, l'UC est une ressource en exclusion mutuelle).

Def.: On appelle section critique la partie d'un programme o la ressource est seulement accessible par le processus en cours. Il faut s'assurer que deux processus n'entrent jamais en mme temps en section critique sur une mme ressource. Exemple : la mise jour d'un fichier (deux mises jour simultanes d'un mme compte client).La section critique comprend : - lecture du compte dans le fichier, - modification du compte, - rcriture du compte dans le fichier.

Programmation multitache : Definitions : Def.: programme multitche : ensemble de plusieurs processus squentiels dont les excutions sont imbriques. Def.: On appelle interblocage la situation o tous les processus sont bloqus. Ex.: chacun attend que l'autre lui envoie un message pour continuer. Ex.: chacun excute une boucle d'attente en attendant une ressource disque indisponible. C'est la situation d'un carrefour avec priorit droite pour tous et des arrives continues de vhicules. Def.: on appelle privation la situation o quelques processus progressent normalement en

bloquant indfiniment d'autres processus. C'est la situation d'un carrefour giratoire avec 4 voies d'accs dont deux ont des arrives continues de vhicules.

Critres dun programme mutlitache juste :

Systme d'exploitation II 12

Rgle 1: les processus doivent tre en relation fortuite. La dfaillance d'un processus en dehors d'une section critique ne doit pas affecter les autres processus. Rgle 2: un programme multitche est juste s'il rpond aux critres de scurit comme

l'exclusion mutuelle.

Rgle 3 : Un programme multitche est juste s'il rpond aux critres de viabilit comme la non privation ou le non interblocage. Les techniques de synchronisation entre processus concurrents peuvent tre classs en deux catgories : par attente active et par attente passive.

Systme d'exploitation II 13

Chapitre II : la synchronisation par attente active

Algorithmes de synchronisation par attente active :
1* masquage des interruptions : le processus qui entre en section critique masque les interruptions et ne peut donc plus tre dsallou (exemple : accs du SE la table des processus). Mais s'il y a plusieurs processeurs ou si le processus "oublie" de dmasquer les interruptions, il y a problme * algorithmes 2.1 2.4 En ce cas, les processus restent dans la liste des processus prts puisqu'ils ont toujours quelque chose tester : d'o une consommation inutile de temps UC - algorithmes par attente passive : les smaphores

3.1 La mthode des coroutines

Algorithme :
int tour ; /* variable de commutation de droit la section critique */ /* valeur 1 pour P1, 2 pour P2 main () { tour = 1; parbegin p1(); p2() ; parend } /*********************************************************************/ p1() { for ( ; ; ) { while (tour == 2); crit1; tour = 2; /* on redonne l'autorisation P 2 */ /* c'est au tour de P 2 ; P1 attend */ /* P1 peut utiliser sa section critique */ */

Systme d'exploitation II 14

reste1; } } /*********************************************************************/ p2() { for (; ; ) { while (tour == 1); crit2; tour = 1; reste2 ; } } /* on redonne l'autorisation P 1 */ /* c'est au tour de P 1 ; P2 attend */

Avantages : - l'exclusion mutuelle est satisfaite. Pour chaque valeur de tour , une section critique et une seule peut s'excuter, et ce jusqu' son terme.

- l'interblocage est impossible puisque tour prend soit la valeur 1, soit la valeur 2 (Les deux processus ne peuvent pas tre bloqus en mme temps ).

- la privation est impossible: un processus ne peut empcher l'autre d'entrer en section critique puisque tour change de valeur la fin de chaque section critique. Inconvnients : - P1 et P2 sont contraints de fonctionner avec la mme frquence d'entre en section critique - Si l'excution de P2 s'arrte, celle de P1 s'arrte aussi: le programme est bloqu. La dpendance de fonctionnement entre P1 et P2 leur confre le nom de coroutines.

3.2 Seconde solution

Chaque processus dispose d'une cl d'entre en section critique (c1 pour P 1, c2 pour P2). P1 n'entre en section critique que si la cl c2 vaut 1. Alors, il affecte 0 sa cl c1 pour empcher P2 d'entrer en section critique.

Systme d'exploitation II 15

Algorithme : int c1, c2 ; /* cls de P1 et P2 - valeur 0: le processus est en section critique */ /* main () { c1=c2 = 1; parbegin p1() ; p2 (); parend } /********************************************************************/ p1 () { for ( ; ; ) { while (c2 == 0); c1 = 0 crit1 ; c1 = 1; reste1 ; } } /********************************************************************/ p2 () { for ( ; ; ) { while (c1 == 0); c2 = 0; crit2 ; c2 = 1 ; reste2; } } /* P 2 n'est plus en section critique */ /* P1 en section critique, P2 attend /* P 2 entre en section critique */ */ /* P1 n'est plus en section critique */ /* P2 en section critique, P1 attend */ /* P 1 entre en section critique */ /* initialement, aucun processus en section critique */ valeur 1: il n'est pas en section critique */

Systme d'exploitation II 16

Avantage : on rend moins dpendants les deux processus en attribuant une cl de section critique chacun.

Inconvnients : Au dbut c1 et c2 sont 1. P1 prend connaissance de c2 et met fin la boucle while. Si la commutation de temps a lieu ce moment, c1 ne sera pas 0 et P2 voluera pour mettre c2 0, tout comme le fera irrmdiablement P1 pour c1. La situation c1 = c2 = 0 qui en rsultera fera entrer simultanment P1 et P2 en section critique : l'exclusion mutuelle ne sera pas satisfaite. Si l'instruction ci = 0 tait place avant la boucle d'attente, l'exclusion mutuelle serait satisfaite, mais on aurait cette fois interblocage. A un moment donn, c1 et c2 seraient nuls simultanment P1 et P2 excuteraient leurs boucles d'attente indfiniment.

3.3 Troisime solution

Lorsque les deux processus veulent entrer en section critique au mme moment, l'un des deux renonce temporairement. Algorithme :
int c1,c2; main () { c1= c2 = 1; parbegin p1(); p2 () ; parend } /**************************************************************************/ p1() { for ( ; ; ) { c1 = 0; while (c2 == 0) /* P1 veut entrer en section critique */ /* ni P1,ni P2 ne veulent entrer en section critique au dpart */ /* 0 si le processus veut entrer en section critique, 1 sinon */

/* tant que P2 veut aussi entrer en section critique ... */

Systme d'exploitation II 17

{ c1 = 1; c1 = 0; } crit1; c1 = 1; reste1 ; } } /*************************************************************************/ p2() { for ( ; ; ) { c2 = 0 ; while (c1 == 0) { c2 = 1; c2 = 0 ; } crit2; c2 = 1 ; reste2 ; } } /* fin de la section critique de P 2 */ /* .. P2 abandonne un temps son intention .... */ /* ..... puis la raffirme */ /* P2 veut entrer en section critique */ /* fin de la section critique de P 1 */ /* ....P1 abandonne un temps son intention... */ /* ..... puis la raffirme */

/* tant que P1 veut aussi entrer en section critique ... */

Commentaires : - l'exclusion mutuelle est satisfaite. (cf. ci-dessus) - il est possible d'aboutir la situation o c1 et c2 sont nuls simultanment. Mais il n'y aura pas interblocage car cette situation instable ne sera pas durable (Elle est lie la commutation de temps entre ci = 1 et ci = 0 dans while).

- il y aura donc d'inutiles pertes de temps par famine limite.

Systme d'exploitation II 18

3.4 Algorithme de DEKKER

DEKKER a propos un algorithme issu des avantages des 1re et 3me solutions pour rsoudre l'ensemble du problme sans aboutir aucun inconvnient. Par rapport, l'algorithme prcdent, un processus peut ritrer sa demande d'entre en section critique, si c'est son tour. Algorithme :
int tour , c1,c2 ; main () { c1 = c2 = tour = 1; /* P1 peut entrer en section critique, mais... */ parbegin p1 () ; p2 () ; parend } p1 () { for ( ; ; ) { c1 = 0; while (c2 == 0) if (tour == 2) { c1 = 1; /* ...... P1 renonce .................... */ */ */ /* P 1 veut entrer en section critique /* tant que P2 le veut aussi........... /* ...... si c'est le tour de P 2 ........ */ */ */ /* ... ni P1, ni P2 ne le demandent */ /* valeur i si c'est au tour de P i de pouvoir entrer en section critique */ /* valeur 0 si le processus veut entrer en section critique,1 sinon */

while (tour == 2) ; /* ...... jusqu' ce que ce soit son tour ...... c1 = 0; } crit1; tour = 2; c1 = 1; reste1; } } /* C'est le tour de P 2 */ /* ..... puis raffirme son intention

/* P1 a achev sa section critique */

/**********************************************************************/ p2 ()

Systme d'exploitation II 19

{ for (; ; ) { c2 = 0; /* P2 veut entrer en section critique */ */ */

while (c1 == 0) /* tant que P1 le veut aussi ......... if (tour == 1) { c2 = 1; /* ........ P2 renonce ....... /* ........ si c'est le tour de P 1 ......

*/ */ */

while (tour == 1); c2 = 0; } crit2; tour = 1; c2 = 1; reste2; } }

/* ..... jusqu' ce que ce soit son tour .... /* ..... puis raffirme son intention

/* C'est le tour de P 1 /* P 2 a achev sa section critique

*/ */

Remarques : - Si p1 veut entrer en section critique (c1 = 0), alors que p2 le veut aussi (c2 = 0), et que c'est le tour de p1 (tour = 1), p1 insistera (while (c2 == 0 ) sera actif). Dans p2, la mme boucle aboutira c2 = 1 (renoncement temporaire de p2). - On dmontre [Ben-Ari pages 51 53] que cet algorithme rsout l'exclusion mutuelle sans privation, sans interblocage, sans blocage du programme par arrt d'un processus. - Cet algorithme peut tre gnralis n processus au prix d'une trs grande complexit.

3.5 Algorithme de Peterson

Debut

Systme d'exploitation II 20

Tour : entier ; C1,c2 : entier ; C1 :=C2 :=tour :=1 ; Paregin P1() P2() Parend ; Processus p1() Debut Faire tj C1 :=0 ; Tour :=2 ; Tq (c2=0 et tour=2) faire ftq <SC> C1 :=1 ; Reste1 ; fin Processus p2() Debut Faire tj C2 :=0 ; Tour :=1 ; Tq (c1=0 et tour=1) faire ftq <SC> C2 :=1 ; Reste1 ; fin Remarque : Lalgorithme de peterson est un pg multitache juste mais il nest valable que pour deux processus concurrents.

Systme d'exploitation II 21

3.6. Algorithme de boulanger

Lamport a propos lalgorithme de boulanger, une solution logicielle pour N processus

Debut Tour[0..N-1] : table de booleen Num[0..N-1]: table dentiers Pp :entier ; Pour i :=2 jusquN faire Debut Tour[i ] :=faux ; Num[i]:=0; fin parbegin p0,p2,,pn-1 ; parend processus pi() var jj :=entier ; debut pp :=i ;/* 0 pour processus 0 ; etc tour[pp] := vrai ; num[pp] :=Max(NUm)+1 tour[pp ] :=Faux ; pour jj :=0 jusqua N faire tq(tour(jj) faire ftq tq ((num(jj)<>0) et (( num(jj)< num(pp) ou ((num(jj)=num(pp) et (jj<pp))) ftq fpour <SC> Num[pp] :=0 ; Fin

Systme d'exploitation II 22

3.7. Les instructions atomiques :

Introduction: On utilise un verrou ( une variable boolenne) pour verrouiller laccs la section critique. Verrou := faux ; Processus pi() Debut Tq (verrou) faire Ftq Verrou :=vrai ; <S C> Verrou :=faux ; Fin

Il y a des processeurs qui fournissent des instructions cbles spciales dont le rle est de rendre atomique la squence : lecture suivie d'criture. Il devient alors impossible deux processeurs excutant des processus concurrents de lire le Verrou Faux avant que l'un d'eux l'ait mis Vrai. les instructions cbles atomiques (on dit aussi indivisibles) les plus usites sont TAS ("test and set") et SWAP ("exchange to memory"). 3.7.1. Linstruction Test And Set (TAS) Linstruction TestAnd Set sexecute comme une action elementaire et indivisible ; elle peut etre dfinie comme suit : Tas(verrou : booleen) : Booleen ; Debut Si verrou alors retourne(vrai) Sinon Verrou := vrai ; Retourne (faux) ; Fin Une instruction Tas execute sur une UC doit sachever avant quune autre puisse sexecuter sur une

autre UC. Verrou : booleen Verrou :=faux ;

Systme d'exploitation II 23

Processus pi () Debut Tq tas(verrou) ftq <SC> Verrou :=faux ; Fin

3.8.2. Linstuction SWAP : Elle est definie comme suit : Procedure Swap( a,b : booleen) C: booleen Debut C:=a; A:=b; B:=c Fin LEM est assure comme suit : Verrou: booleen Verrou :=faux ; Processus pi() Var cle : booleen / * cl : un variable locale pour chaque processus Debut Cle : =vrai ; Tq (cl) faire Swap(cl, verrou) ; Ftq <SC> Verrou :=faux ; Fin

Systme d'exploitation II 24

Bilan de l'attente active : inconvnients et utilisation

L'attente active a comme inconvnients : Immobilisation du processeur simplement pour attendre. Risque d'attendre indfiniment. Congestion du bus mmoire avec des accs pour vrifier que l'attente est toujours ncessaire et cela ralentit les accs mmoire, donc a puissance de calcul, du processeur en section critique. L'attente active est cependant incontournable pour des sections critiques de courte dure
Nouvelle ide : mettre en sommeil un processus qui demande entrer en section critique ds lors qu'un autre processus y est dj. C'est l'attente passive.

Systme d'exploitation II 25

Chapitre II : la synchronisation par attente passive

Cours 5 : smaphores
Introduction: les dfauts des solution par attente active

5.1 Les smaphores

La rsolution des problmes multi-tches a considrablement progress avec l'invention des smaphores par E.W. DIJKSTRA en 1965. Il s'agit d'un outil puissant, facile implanter et utiliser. Les smaphores permettent de rsoudre un grand nombre de problmes lis la programmation simultane, notamment le problme de l'exclusion mutuelle. Un smaphore est une structure deux champs : - une variable entire, ou valeur du smaphore. Un smaphore est dit binaire si sa valeur ne peut tre que 0 ou 1, gnral sinon. - une file d'attente de processus ou de tches. Dans la plupart des cas, la valeur du smaphore reprsente un moment donn le nombre d'accs possibles une ressource.

Seules deux fonctions permettent de manipuler un smaphore : - P (s) ou down (s) ou WAIT (s) - V (s) ou up (s) ou SIGNAL (s)
5.1.1 P (s)

La fonction P(S) dcrmente le smaphore d'une unit condition que sa valeur ne devienne pas ngative. P(s): si s>0 alors s=s-1 Sinon suspendre l'excution du processus en cours et le placer le processus dans la file d'attente du
smaphore

Fsi
5.1.2 V (s)

La fonction V(S) incrmente la valeur du smaphore d'une unit si la file d'attente est vide et si cette incrmentation est possible.

Systme d'exploitation II 26

V(s): si Fat (file d attente) est vide alors s=s+1 Sinon reveiller un processus dans la file d'attente du smaphore, Fsi

Remarques: 1. Du fait de la variable globale verrou, les fonctions P et V sont ininterruptibles (on dit aussi atomiques). Les deux fonctions P et V s'excluent mutuellement. Si P et V sont appeles en mme temps, elles sont excutes l'une aprs l'autre dans un ordre imprvisible.

2. On supposera toujours que le processus rveill par V est le premier entr dans la file d'attente, donc celui qui est en tte de la file d'attente.
5.1.3 Application des smaphores l'exclusion mutuelle

Avec le schma de programme prcdent :

SEMAPHORE s; /* dclaration trs symbolique */ main () { SEMAB (s,1); parbegin p1 () ; p2 () ; parend } /****************************************************************************/ p1 () { for ( ; ; ) { P (s); ................. /* section critique de p1 V (s); ................. /* section non critique de p1 */ } } /***************************************************************************/ p2 () { /* second processus */ */ /* premier processus */ /* instructions trs symboliques */ /* dclaration trs symbolique ; initialise le smaphore binaire s 1 */

Systme d'exploitation II 27

for ( ; ; ) { P (s); ................. /* section critique de p2 V (s); ................ /* section non critique de p2 */ } } */

La dmonstration formelle que l'algorithme rsout l'exclusion mutuelle et ne cre pas d'interblocage est donne dans Ben-Ari page 63. Si l'on tend cet algorithme n processus (n > 2) , il peut y avoir privation (par exemple, P1 et P2 peuvent se rveiller mutuellement et d'autres processus). J.M. Morris a propos en 1979 un algorithme de rsolution de l'exclusion mutuelle sans privation pour n processus dans Information Processing Letters, volume 8 , pages 76 80 . Exemple : Soient 3 processus P1, P2, P3 chargs du calcul de (a+ b) * (c + d) - (e/f) P2 calcule c + d, P3 calcule e/f et P1 le rsultat. On initialise les smaphores s1 et s2 0.
P1 P2 P3

suspendre indfiniment P3 ou

_________________________________________ t1 = a + b P (s1) t4 = t1 * t2 P (s2) res = t4 - t3 t2 = c + d V (s1) t3 = e/f V(s2)

Exemple : avec deux processus p1 et p2, deux smaphores s1 et s2 (s1 = s2 = 1) p1 .... P (S1) ....... P (S2) ....... V (S2) p2 ...... P (S2) .......... P (S1)

Systme d'exploitation II 28

Si p1 fait P (S1) alors S1 = 0 puis p2 fait P (S2) et S2 = 0 puis p1 fait P (S2) et p1 est en attente, ENDORMI puis p2 fait P (S1) et p2 est ENDORMI Il y a donc videmment interblocage (puisque aucun des processus ne peut faire V (On dit aussi treinte fatale ou deadlock) Si les primitives P et V ne sont pas utilises correctement (erreurs dans l'emploi, le partage ou l'initialisation des smaphores), un problme peut survenir.

Proprits des smaphores

En crocus intrts des smaphores mcanisme simple, pas d'attente active meilleur que le masquage des interruptions (conceptuellement) meilleur que l'attente active (ressources processeur et canal) mcanisme logique de base peu coteux si bien implment au bon niveau (noyau) critiques des smaphores A) difficile utiliser avec fiabilit l'oubli d'un V(mutex) peut conduire interblocage l'oubli d'un P(mutex) est une faute d'exclusion mutuelle on retrouve ces problmes pour tous les mcanismes quand les procdures ou les appels systmes peuvent tre embots B) mcanisme non structur; la synchronisation peut apparatre n'importe o dans le code - et non pas dans des rgions bien localises - donc la dtection d'erreurs et la mise au point sont plus difficile car la propagation des erreurs est trs facilite quand les smaphores sont placs comme variables globales. C) mcanisme trop lmentaire au niveau abstraction

extensions simples des smaphores smaphores avec messages (utiliss dans HB 64 renomm DPS 7) smaphores avec P non bloquant et retour d'un compte rendu boolen smaphores avec P bloquant seulement pendant un dlai maximal smaphores avec P(S, n) augmentant l'entier E.S de n, V(S,m) diminuant l'entier E.S de m ( m, n ! 0 et pas seulement n = m = 1)

Systme d'exploitation II 29

Cours 6 : les moniteurs

1-Introduction:
Bien que les semaphores proposent un mcanisme gnral pour contrler l'accs aux sections critiques, leur utilisation ne garantit pas que cet acces est mutuellement exclusif ou que les inter blocages sont vits. On peut aisment imaginer qu'une erreur de programmation des primitives P() et V() ou l'oubli d'une de ces primitives peut tre trs grave : interblocage, incohrence des donnes, etc... En tenant compte des critiques cites ci-dessus, on ne peut donc pas concevoir tout un systme d'exploitation uniquement partir des smaphores. Un outil de programmation plus sr s'avre ncessaire. Dfinition : Un moniteur est une structure de variables et de procdures pouvant tre paramtre et partage par plusieurs processus. Ce concept a t propos par C.A.R. HOARE en 1974 et P. BRINCH-HANSEN en 1975. Le moniteur est une construction du langage de programmation qui garanti un accs approprie a des sections critiques. L'accs contrle est propose par le langage et non par le programmeur. Le type moniteur existe dans certains langages de programmation, tels que Concurrent Pascal.

Schma

Le corps du moniteur est excut ds que le programme est lanc pour initialiser les variables du moniteur. Les variables moniteur ne sont accessibles qu' travers les procdures moniteur. La seule manire pour un processus d'accder une variable moniteur est d'appeler une procdure moniteur. On peut prvoir plusieurs moniteurs pour diffrentes tches qui vont s'excuter en parallle. Chaque moniteur est charg d'une tche bien prcise et chacun a ses donnes et ses instructions rserves. Si un moniteur M1 est le seul moniteur avoir accs la variable u1, on est sr que u1 est en exclusion

Systme d'exploitation II 30

mutuelle. De plus, comme les seules oprations faites sur u1 sont celles programmes dans M1, il ne peut y avoir ni affectation, ni test accidentels. On dit que l'entre du moniteur par un processus exclut l'entre du moniteur par un autre processus. Les moniteurs prsentent plusieurs avantages : - au lieu d'tre disperses dans plusieurs processus, les sections critiques sont transformes en procdures d'un moniteur modularit et de la systmatisation de l'exclusion mutuelle et de la section critique - la gestion des sections critiques n'est plus la charge de l'utilisateur, mais elle est ralise par le moniteur, puisqu'en fait le moniteur tout entier est implant comme une section critique. Des exemples de moniteurs sont donns dans Beauquier, p. 139-141.

Il utilise des variables de type condition et deux primitives agissant sur elles : - WAIT : bloque le processus appelant et autorise un processus en attente entrer dans le moniteur - SIGNAL : rveille le processus endormi en tte de la file d'attente. Puis, ou bien le processus courant est endormi (solution de Hoare), ou bien le processus courant quitte le moniteur (solution de Brinch Hansen, la plus usite), afin qu'il n'y ait pas deux processus actifs dans le moniteur. La syntaxe d'un moniteur ressemble plus en moins au code ci apres: Monit: moniteur Debut // declaration des variables i: entier; c: condition // decalaration des procedures Procedure SCpoint1() Debut // code de procedure fin Procedure SCpoint2() Debut // code d eprocedure

Systme d'exploitation II 31

fin // intialisation debut fin Fin du moniteur

Exemple:
(a+ b) * (c + d) - (e/f)

intrts du moniteur
introduction de la modularit et de la systmatisation de l'exclusion mutuelle et de la section critique se prte bien une formalisation (mieux que le smaphore) car : la section critique est dclare, on peut srialiser les sections critiques, on peut appliquer des preuves squentielles cette srialisation on peut associer des invariants un moniteur

inconvnients du moniteur
la synchronisation par wait et signal peut devenir complexe et se rvler d'aussi bas niveau que les smaphores(des essais pour introduire des sortes d'expressions gardes apportent des amliorations de fiabilit, mais au cot d'une rvaluation dynamique des gardes, des endroits non systmatiques) problme des appels embots = problme gnral des exclusions mutuelles embotes : - soit danger d'interblocage si appel de moniteur possible depuis un autre moniteur (P1 dans M1 appelle M2 "" P2 dans M2 appelle M1) - soit un processus ne doit pouvoir n'appeler qu'un moniteur la fois : contrainte la programmation (explicite statique) ou l'excution(dynamique)

Systme d'exploitation II 32

Chapitre IV : COMMUNICATION INTER-PROCESSUS

COURS 7 : Le modle producteur-consommateur.

Introduction
Les processus ont besoin de communiquer, d'changer des informations de faon plus labore et plus structure que par le biais d'interruptions. Un modle de communication entre processus avec partage de zone commune (tampon) est le modle producteur-consommateur. Le producteur doit pouvoir ranger en zone commune des donnes qu'il produit en attendant que le consommateur soit prt les consommer. Le consommateur ne doit pas essayer de consommer des donnes inexistantes. Hypothses : - les donnes sont de taille constante - les vitesses respectives des deux processus (producteur consommateur) sont quelconques.

Rgle 1 : Le producteur ne peut pas ranger un objet si le tampon est plein Rgle 2 : Le consommateur ne peut pas prendre un objet si le tampon est vide.

PRODUCTEUR Faire toujours produire un objet si nb d'objets ds tampon < N alors dposer l'objet ds le tampon finsi Fait

CONSOMMATEUR Faire toujours si nb d'objets ds tampon >0 alors prendre l'objet consommer l'objet finsi Fait

Rgle 3 : exclusion mutuelle au niveau de l'objet : le consommateur ne peut prlever un objet que le producteur est en train de ranger.

Systme d'exploitation II 33

Rgle 4 : si le producteur (resp. consommateur) est en attente parce que le tampon est plein (resp. vide), il doit tre averti ds que cette condition cesse d'tre vraie. Le tampon peut tre reprsent par une liste circulaire. On introduit donc deux variables caractrisant l'tat du tampon : NPLEIN : nombre d'objets dans le tampon (dbut : 0) NVIDE : nombre d'emplacements disponibles dans le tampon (N au dbut). PRODUCTEUR :
Faire toujours Produire un objet si NVIDE >0 /* dbut d'atome ininterruptible */

/* s'il existe au moins un emplacement vide dans le tampon */

alors NVIDE -sinon s'endormir finsi /* fin d'atome ininterruptible */

ranger l'objet dans le tampon si consommateur endormi

/* dbut d'atome ininterruptible */

alors rveiller le consommateur sinon NPLEIN ++ finsi Fait

CONSOMMATEUR :
Faire toujours si NPLEIN > 0 /* s'il existe au moins un objet dans le tampon */ alors NPLEIN -sinon s'endormir finsi prlever l'objet dans le tampon si producteur endormi alors rveiller le producteur sinon NVIDE ++ finsi consommer l'objet Fait

2- Solution avec des smaphores

Systme d'exploitation II 34

On peut considrer NVIDE et NPLEIN comme des smaphores :

PRODUCTEUR

CONSOMMATEUR

Faire toujours produire un objet P (NVIDE) dposer un objet V (NPLEIN) Fait

Faire toujours P (NPLEIN) prlever un objet V (NVIDE) consommer l'objet

Fait

On dmontre que le producteur et le consommateur ne peuvent tre bloqus simultanment. Cas o le nombre de producteur (consommateur) est suprieur 1 Si plusieurs producteurs (consommateurs) oprent sur le mme tampon, il faut assurer l'exclusion mutuelle dans l' opration dposer un objet ( prlever un objet) afin que le pointeur queue (tete) garde une valeur cohrente, de mme que pour les objets points par queue (tete). Si l'on veut s'assurer de plus qu'il n'y aura aucun problme dans l'accs au tampon, on peut dcider que les oprations prlever et dposer ne s'excutent pas simultanment. Dposer et prlever doivent donc figurer en section critique pour protger les valeurs ressources (tampon, queue, tete). D'o l'utilisation d'un smaphore binaire :
PRODUCTEUR produire un objet P (NVIDE) P (MUTEX) tampon[queue] = objet queue = (queue ++) % N V (MUTEX) V (NPLEIN) CONSOMMATEUR P (NPLEIN) P (MUTEX) objet = tampon [tete] tete = (tete ++) % N V (MUTEX) V (NVIDE) consommer l'objet

Systme d'exploitation II 35

3. Solution avec un compteur d'vnements

D.P. REED et R.K. KANODIA ont propos en 1979 une solution qui utilise une variable entire appele compteur d'vnements. Trois primitives permettent de manipuler une variable compteur d'vnements E, commune tous les processus concerns : - Read (E) donne la valeur de E - Advance (E) incrmente E de 1 de manire atomique - Await (E , v) attend que E v
constante TAILLE /* nombre de places dans le tampon */ compteur_d_vnements in = 0, /* nb d'objets mis dans le tampon */ */

out = 0 /* nb d'objets retirs du tampon producteur Faire toujours produire l'objet suivant nb_produits ++

/* nb_produits : nombre d'objets produits */

await (out, nb_produits - TAILLE) mettre l'objet en position (nb_produits - 1) % TAILLE advance (in) Fait

consommateur Faire toujours nb_retirs ++ /* nb_retirs : nombre d'objets retirs */

await (in, nb_retirs) retirer l'objet en position (nb_retirs - 1) % TAILLE advance (out) consommer l'objet Fait

4-Solution avec moniteurs

Voici une solution du moniteur du problme producteur-consommateur :
moniteur ProdCons /* moniteur, condition : types prdfinis */ condition plein, vide

Systme d'exploitation II 36

int compteur /* dbut du corps du moniteur */ compteur := 0 /* fin du corps du moniteur procdure ajouter () { if compteur = N then WAIT (plein) /* seul un SIGNAL (plein) rveillera le processus */ ........... /* ranger l'objet dans le tampon */ compteur ++ if compteur = 1 then SIGNAL (vide) /* rveille un processus endormi parce que le tampon tait vide */ }

procdure retirer () { if compteur = 0 then WAIT (vide) /* seul un SIGNAL (vide) rveillera le processus */ .......... /* retirer l'objet du tampon */ compteur -if compteur = N-1 then SIGNAL (plein) /* rveille un processus endormi parce que le tampon tait plein */ } fin du moniteur

procdure producteur () { faire toujours produire (lment) ProdCons . ajouter () fin faire }

procdure consommateur () { faire toujours retirer (lment) ProdCons . retirer () fin faire }

Systme d'exploitation II 37

5- Solution avec changes de messages

Certains ont estim que les smaphores sont de trop bas niveau et les moniteurs descriptibles dans un nombre trop restreint de langages. Ils ont propos un mode de communication inter-processus qui repose sur deux primitives qui sont des appels systme ( la diffrence des moniteurs) : - send (destination , &message) - receive (source , &message), o source peut prendre la valeur gnrale ANY Gnralement, pour viter les problmes dans les rseaux, le rcepteur acquitte le message reu. L'metteur envoie nouveau son message s'il ne reoit pas d'acquittement. Le rcepteur, s'il reoit deux messages identiques, ne tient pas compte du second et en tire la conclusion que l'acquittement s'est perdu. Dans le contexte d'un mode client-serveur, le message reu contient le nom et les paramtres d'une procdure lancer. Le processus appelant se bloque jusqu' la fin de l'excution de la procdure et le message en retour contient la liste des rsultats de la procdure. On parle d'appel de procdure distance. On peut proposer une solution au problme producteur-consommateur par change de messages avec les hypothses suivantes : - les messages ont tous la mme taille - les messages envoys et pas encore reus sont stocks par le SE dans une mmoire tampon - le nombre maximal de messages est N - chaque fois que le producteur veut dlivrer un objet au consommateur, il prend un message vide, le remplit et l'envoie. Ainsi, le nombre total de messages dans le systme reste constant dans le temps - si le producteur travaille plus vite que le consommateur, tous les messages seront pleins et le producteur se bloquera dans l'attente d'un message vide ; si le consommateur travaille plus vite que le producteur, tous les messages seront vides et le consommateur se bloquera en attendant que le producteur en remplisse un.
producteur Faire toujours produire_objet (&objet) /* produire un nouvel objet */

Systme d'exploitation II 38

receive (consommateur , &m) faire_message (&m , objet) send (consommateur , &m) Fait

/* attendre un message vide /* construire un message envoyer /* envoyer le message

*/ */ */

consommateur pour (i = 0 ; i < N ; i++) send (producteur , &m) Faire toujours receive (producteur , &m) retirer_objet (&m , &objet) utiliser_objet (objet) send (producteur , &m) Fait /* renvoyer une rponse vide */ /* attendre un message /* retirer l'objet du message */ */ /* envoyer N messages vides */

On peut galement imaginer une solution de type bote aux lettres de capacit N messages , avec un producteur se bloquant si la bote est pleine et un consommateur se bloquant si la bote est vide.

6- Proprits des solutions prcdentes

On dmontre les rsultats d'quivalence suivants entre smaphores, moniteurs et changes de messages : - on peut utiliser des smaphores pour construire un moniteur et un systme d'changes de messages - on peut utiliser des moniteurs pour raliser des smaphores et un systme d'changes de messages - on peut utiliser des messages pour raliser des smaphores et des moniteurs

Systme d'exploitation II 39

Cours 8 : Le problme du diner des philosophes Introduction

Il s'agit d'un problme trs ancien, dont DIJKSTRA a montr en 1965 qu'il modlise bien les processus en concurrence pour accder un nombre limit de ressources. "5 philosophes sont assis autour d'une table ronde. Chaque philosophe a devant lui une assiette de spaghettis si glissants qu'il lui faut deux fourchettes pour les manger. Or, il n'y a qu'une fourchette entre deux assiettes conscutives. L'activit d'un philosophe est partage entre manger et penser. Quand un philosophe a faim, il tente de prendre les deux fourchettes encadrant son assiette. S'il y parvient, il mange, puis il se remet penser. Comment crire un algorithme qui permette chaque philosophe de ne jamais tre bloqu ? " Il faut tout la fois viter les situations : - d'interblocage : par exemple tous les philosophes prennent leur fourchette gauche en mme temps et attendent que la fourchette droite se libre - de privation : tous les philosophes prennent leur fourchette gauche, et, constatant que la droite n'est pas libre, la reposent, puis prennent la droite en mme temps, etc...

Systme d'exploitation II 40

Voici une solution (une autre est donne dans Beauquier p. 155-156) :

Premire solution
#define N 5 (i - 1) % N (i + 1) % N /* nombre de philosophes */ /* n du voisin gauche de i */ /* n du voisin droite de /* il pense */ /* il a faim */ /* il mange */ i */ #define GAUCHE #define DROITE #define PENSE 0 #define FAIM 1

#define MANGE 2 typedef int semaphore; int etat [N]; semaphore mutex = 1, s [N]; /*****************************/ void philosophe (int i) { while (TRUE) { penser (); prendre_fourchettes (i); manger (); poser_fourchettes (i); } } /*****************************/ void prendre_fourchettes (int i) { P (mutex); etat [i] = FAIM; test (i); V (mutex); P (s [i]); }

/* pour mmoriser les tats des philosophes */ /* pour section critique */ /* un smaphore par philosophe */

/* prendre 2 fourchettes ou se bloquer */

/* entre en section critique */

/* tentative d'obtenir 2 fourchettes */ /* sortie de la section critique */ /* blocage si pas 2 fourchettes */

/*****************************/ void poser_fourchettes (int i) { P (mutex); etat [i] = PENSE; test (GAUCHE); /* entre en section critique */

Systme d'exploitation II 41

test (DROITE); V (mutex) ; } /*****************************/ void test (int i) { if (etat [i] == FAIM && etat [GAUCHE] != MANGE && etat [DROITE] != MANGE) { etat [i] = MANGE; V (s [i] ); } } /* sortie de la section critique */

Deuxieme solution
Baguette[5] :table de semapho=1 Chaise: semaphore=4 Philosophe(i:entier): processus Philosophe (i:entier) debut //repas assis avec chaise pour 4 seulement

P(Chaise); P(Baguette(I)); P(Baguette(I + 1) Manger; V(Baguette(I)); V(Baguette(I + 1));

V(Chaise); Fin Parbegin Philosophe(1), Philosophe(2), Philosophe(3), Philosophe(4), Philosophe(5) parend -- ni interblocage, ni famine

Systme d'exploitation II 42

Cours 9 : Le problme des lecteurs et des rdacteurs

Introduction :
Il s'agit d'un autre problme classique dont P.J. COURTOIS a montr en 1971 qu'il modlise bien les accs d'un processus une base de donnes. On peut accepter que plusieurs processus lisent la base en mme temps; mais ds qu'un processus crit dans la base, aucun autre processus ne doit tre autoris y accder, en lecture ou en criture. Voici une solution qui donne la priorit aux lecteurs (COURTOIS a propos une solution qui donne la priorit aux rdacteurs) :
typedef int semaphore; int rc = 0; semaphore mutex = 1, bd = 1; /*****************************/ void lecteur () { while (TRUE) { P (mutex); rc ++; if (rc == 1) P (bd); V (mutex); lire_base_de_donnees (); P (mutex); rc --; if (rc == 0) V (bd); V (mutex); utiliser_donnees_lues (); } } /*****************************/ void redacteur () { while (TRUE) { /* pour obtenir un accs exclusif rc */ /* un lecteur de moins */ /* si c'est le dernier lecteur */ /* pour obtenir un accs exclusif rc */ /* un lecteur de plus */ /* si c'est le 1er lecteur */ /* nb de processus qui lisent ou qui veulent crire */ /* pour contrler l'accs rc */

/* contrle de l'accs la base */

Systme d'exploitation II 43

creer_donnees (); P (bd); ecrire_donnees (); V (bd); } }

Autre bonne solution : Beauquier p. 146-148

Systme d'exploitation II 44

Chapitre V : Interblocage
Cours 10 : prvention et vitement de linterblocage
1. Introduction : Un systme consiste en un nombre fini de ressources qui peuvent tre distribues aux processus en comptition. Ressources : espaces mmoires, les cycles processeurs, fichiers , priphriques dentres sorties..etc SI un systme possde deux processeurs alors le type de ressource processeur a deux instances. (ils peuvent de eux ressources spares). Schema

P1P2P3p1 R1 R2 R3

Les interblocages surviennent lorsque chaque processus d un ensemble de processsu contrle une ressource requise par un autre processus de l ensemble. Chaque processus se bloque en attendant que la ressource requise soit disponible. 2.Quatre conditions sont indispensables pour quun interblocage survienne.

C1. Exclusion mutuelle. Chaque ressource peut tre alloue a u seul processus a tout instant C2. Dtention et attente : le processus ne librent pas les ressources prcdemment octroyes quand ils attendent que des requtes imminentes soient octroyes.

C3. Pas de premption : les ressources prcdemment octroyes ne peuvent pas retires des processus les dtenant C4. Attente circulaire : il existe une chaine de deux processus ou plus, de manire ce que chaque processus de la chaine contienne une ressource requise par le prochain processus de la chaine.

Systme d'exploitation II 45

Interblocage c1^c2^c3^c4

Graphe d allocation de ressources : Si un graphe dallocation de ressources ne possde pas de cycle, alors le systme n est pas en tat d interblockage.

3. Prvenir linterblocage : Il est possible dviter l interblocage condition que les quatre conditions ne soient pas runies.

1. La suppression de l accs exclusif mutuel a toute ressource n apparat pas comme une solution pratique certaines ressources ne peuvent pas tre partage ex : imprimante ( possible avec spooling) 2.La condition de dtention et attente : sapplique en cas de de requtes de ressources par des processus sans ressources. Sol1. On exige qu u processus ne commence son excution s il ne require pas toutes les ressources possibles. Deux inconvnients majeurs : un processus ne sait pas forcement de quelles ressources il a besoin. Les ressources peuvent dpendre de son traitement famine sol 2. demander aux processus de librer toutes ressources retenues lorsqu une requte est mise. Inc. La plupart de temps cette stratgie se rvle peu pratique. Ex : allocation de disque puis imprimante. Risque de perdre ses donnes sur disque.

3.La suppression de la condition de on premption : mois pratique que celle de la non exclusion. Possible pour quelques ressources (processur) ou par dispositif virtuel.

Systme d'exploitation II 46

4. L elimination de la condition d attente circulaire : la technique la plus prometteuse que les autres. Une mthode consiste associer a chaque ressource un numro de priorit unique. Les processus ne peuvent requrir de ressources que si la priorit est plus leve que toutes les ressources dtenues. Si la ressource n a pas de priorits suprieure a toutes les ressources dtenues, celle d entre elles qui est dote la priorit la plus lev doit tre libre en premier.

Ex : Imprimate 1, table tracante2 , modem 3 P1 imprimante table tracante P2 modem imprimante P3 table tracante modem

Inc. Il existe aucun numro de priorit qui corresponde aux besoins de tous les processus.

4. Eviter les interblocages : Au lieu dessayer dliminer lune de conditions ncessaires lapparition de linterblocage, il peut tre vit ce dernires en nallouant jamais de ressources si elle est susceptible dinduire des interblocages. Une solution simple consiste allouer des ressource a un seul processus a la fois. On dit un systme est dans un tat sur s il y a une squence dexcution sure Une squence dexcution sure est une squence dexcution dans laquelle tous les processus sexcutent entirement

Sur

/ non sur (interblockage)

Relations entre les tats sur, non sur et lineterblocage. L'algorithme de banquier ayant pour but de dterminer si un tat est sur ou non d'un systme avec P processus R ressources peut tre rcapitul comme suit: . Algorithme du Banquier

Systme d'exploitation II 47

Debut max[P,R] :entier /* les besoins maximums des processus P en ressources R*/ courant [P,R] : Entier /* les allocations en cours*/ Disp[R]: entier; Done[p]: booleen= "faux"; Sur: booleen; Pp: entire:=0; Tanque pp<P faire Si done[pp] contiune fsi // si les requtes de ce processus sont accordes , peut il sexcuter jusqu sa terminaison ? Pour rr=1 jusuqu R faire si max[pp,rr]-courant [pp,rr]>Disp[rr] alors // non, pas suffisammennt de ressources rr disponibles, processus Pp++ ; Continue 2 // se rend la prochaine itration de la boucle externe Finsi // oui, rinitialiser le systme letat avec le nouveau etat des ressources en ajoutant les ressources libres par pp Pour rr=1 jusuqu R faire Disp[rr]=disp[rr]+courant [pp,rr] ; Fpour Done[pp]= vrai ; Pp=0 ; Fpour // si tous les processus peuvent sexcuter complment , ltat du systme est sur Sur=vrai ; Pour PP=1 jusuqu P faire Si non Done[pp] alors sur =faux Fpour se rend au prochain

Systme d'exploitation II 48

Fin Lalgorithme du banquier prend la dcision daccorder une ressource en se demandant si loctroi dune requte va ou non placer le systmes dans un mode non sur. Bien que trs lgant dans sa conception, lalgorithme du banquier prsente un inconvnient majeur : il lui faut connatre le nombre maximum de ressources que chaque processus peut requrir. Or, ce type de renseignements est rarement disponible sur les systmes : cest pourquoi trs peu de systmes ont recours cet algorithme.

Cours 11 : Dtection et correction de linterblocage

5- Dtecter les interblocages : Plutt que dessayer de prvenir les interbocages , les systmes peuvent galement les laisser se produire (peu frquent) pour les corriger lorsquils surviennent. Une telle stratgie fait appel des mcanismes de dtection et de correction des interblocages. Un graphe dallocation des ressources peut tre utilis pour modliser ltat des allocations de ressources et celui de requtes.

Ex :

Processus

Allocations en cours R1 R2 0 1 2 0 R3 0 0 0 1 R1 0 1 1 0

Requtes mises R2 0 0 0 2 R3 0 0 1 0 R1 0

Ressources disponibles R2 0 R3 0

P1 P2 P3 P4

3 1 0 1

Systme d'exploitation II 49

Un graphe rduit dallocation des ressources peut tre utilis pour dterminer si linterblocage existe ou non. Pour y arriver, on suit les tapes suivantes dune faon itrative : *- si une ressource ne possde que des dparts de flches, il faut effacer toutes les flches. *- si un processus n a que des arrivs des flches, il faut galement effacer toutes ses flches. *- si un processus a des flches au dpart, mais quun point de ressource (au moins) est disponible pour chacune delles dans la ressource dans laquelle pointe la flche, il faut aussi supprimer toutes les flches du processus. Le systme est en interblocage si et seulement sil reste des flches. De ltat du systme pour lhomme, main un ordinateur prfre une approche algorithmique. Lalgorithme dterminant linterblocage est similaire a celui qui dtecte si le systme est en tat sur.

Algorithme Debut dem[P,R] :entier /* les besoins maximums des processus P en ressources R*/ courant [P,R] : Entier /* les allocations en cours*/ Disp[R]: entier; Done[p]: booleen= "faux"; inetrblocage: booleen; Pp: entire:=0; Tanque pp<P faire Si done[pp] contiune fsi // si les requtes de ce processus sont accordes , peut il sexcuter jusqu sa terminaison ? Pour rr=1 jusuqu R faire si dem[pp,rr]>Disp[rr] alors // non, pas suffisamment de ressources rr disponibles, se rend au prochain processus Pp++ ; Continue 2 // se rend la prochaine itration de la boucle externe Finsi // oui, rinitialiser le systme letat avec le nouveau etat des ressources en ajoutant les ressources libres par pp

Systme d'exploitation II 50

Pour rr=1 jusuqu R faire Disp[rr]=disp[rr]+courant [pp,rr] ; Fpour Done[pp]= vrai ; Pp=0 ; Fpour // si tous les processus peuvent sexcuter complment , ltat du systme est sur interblocage=faux ; Pour PP=1 jusuqu P faire Si non Done[pp] alors interblocage =vrai Fpour Fin

6- Corriger les interblocages Les trois approches permettant de corriger les interblocages sont la premption automatique, la terminaison automatique ou lintervention manuelle a- Avec les premption automatique, le systme dexploitation prempte un sous ensemble de ressources alloues. Trois problmes majeurs doivent tre rsolues pour mettre en uvre une telle stratgie. Selection : quelles ressources de quels processus vont tre premptes ? Des facteurs permettant de prendre la dcision sont les suivantes : la priorit dun processus ? Le temps dexcution dun processus Le nombre de ressources habituelles du processus Le nombre de processus affects Consquence : quarrive-t-il aux processus qui ont leurs ressources premptes ? Sauvegarde de la trace dexcution : couteux( temps et stockage), peu pratique. Famine : si le mme processus est sans cesse victime de premption. Solution : faire appel un compteur de premption qui est incrment chaque fois quun processus repasse son tat antrieur.

b- La terminaison automatique fait disparaitre les interblocages en mettant fin au processus .

Systme d'exploitation II 51

Tous les processus ou sous ensemble o o Tous ; une solution pour les systmes qui favorisent la solution rapide. Sous ensemble : l les problmes de la slection comme dans la premption automatique. La terminaison dun processus peut rpercuter sur les autres processus qui dpendent de son traitement ainsi la mise jour partielle des fichiers.

c- Lintervention manuelle : cest loperateur du systme quil incombe de rsoudre le problme. Compte tenu des limites de approches automatique, elle sagit dune solution intressante Mais, certains systmes fonctionnent sans operateur plein temps, dautres doivent ragir une situation dinterblocage ds sa dtection. Dans ces cas, lintervention manuelle est peu commode

7- Lalgorithme de lautruche Tous les mcanismes du traitement des interblocages prsents prsentent tous un inconvnient majeur.( aucun moyen efficace). Pour la plupart des systmes dexploitation , lapparition dinterblocages est fort rare. Par consquent, dans nombreuses situations, le problme des interblocages est ignor, linstar dune autruche qui senfonce la tte dans le sable en esprant que le problme disparaisse. Autrement, est ce que le cout de la solution est justifi par lampleur du problme rsoudre ?

Systme d'exploitation II 52

BIBLIOGRAPHIE

J. BEAUQUIER, B. BERARD, Systmes d'exploitation, Ediscience, 1993 M. BEN-ARI, Processus concurrents, Masson 1986 A. SCHIPER, Programmation concurrente, Presses Polytechnique Romandes 1986 A. TANENBAUM, Les systmes d'exploitation, Prentice Hall, 1999

Crocus Systmes dexploitation des ordinateurs. Serie Schaum Systmes dexploitation.