Home

Cours02

1. Quelquefois la destruction de plusieurs processus s impose pour r cup rer un nombre suf fisant de ressources Aussi le terme de gu rison semble ici un peu exag r mais s adapte parfaitement la conception occidentale de la m decine qui s attache surtout la symp tomatique des pathologies On peut faire la comparaison avec une amputation d un membre atteint d art rite le patient s estime t il gu ri L ordre dans lequel les processus vont tre supprim s est tr s important Va t on chercher minimiser leur nombre Va t on consid rer la quantit de travail d j accomplie afin de r duire la perte de rendement Va t on consid rer les priorit s des processus Va t on choisir les processus victimes parmi ceux pour lesquels le retrait des ressources n est pas fatal 1 ex cution afin de seulement les suspendre le temps de lt gu rir gt pour ensuite les reprendre en l tat sans perte de travail Et le temps d exploitation de tout cela Et si cela arrive sur un site sur lequel se d roule une application temps r el tr s d licate surveillance de raffinerie de centrale ato mique Voil autant de questions qui donnent r fl chir sur la conception des syst mes de demain et qui loin d tre r solues de fa on satisfaisante occasionnent quelques lt nuits blanches gt aux concepteurs d aujourd hui 7 Et demain Nous venons d avoir un aper u de ce qui se faisait ou pourra
2. ils peuvent conserver les ressources en leur possession tout en r clamant des res sources suppl mentaires il n y aura pas de r quisition afin d aider le syst me les ressources seront demand es une une si une requ te n est pas honor e le processus demandeur conserve n anmoins les ressources en sa possession et attend un temps fini jusqu ce qu il obtienne satis faction seules les requ tes laissant le syst me dans un tat sain sont honor es Dans l ventualit contraire le processus demandeur devra attendre le syst me tant toujours dans un tat sain toutes les requ tes pourront tre satisfaites t t ou tard Cet algorithme semble donc int ressant et tout le moins plus convivial et d un meilleur rendement que les strat gies de pr vention propos es par Havender Toutefois nous allons voir qu il contient de nombreuses faiblesses qui font que les concepteurs de syst mes lui pr f rent d autres approches L algorithme pr suppose et s appuie totalement sur le fait que le nombre de res sources est invariant Or il est bien vident que des probl mes de maintenance du mat riel ou tout simplement des pannes peuvent mettre en d faut ce postulat Il pr suppose aussi que chaque utilisateur annonce le maximum de ressources uti lis es Or l heure actuelle la convivialit grandissante des syst mes fait que rares sont les utilisateurs connaissant pr
3. attente infinie par un processus d une ressource qu il n aura jamais C est notamment le cas si il y a interblocage entre plusieurs processus nous verrons ce cas dans les sections suivantes Finalement l OS doit galement viter la congestion c est dire la demande excessive de ressources En d autres termes POS doit veiller ne pas accepter les demandes quand le syst me est en surcharge Un mod le math matique des files d attente peut fournir aux lt designers gt de syst me des solutions efficaces au probl me d allocation de ressource Les param tres de ce mod le sont la loi de distribution des instants d arriv e la loi de distribution des demandes de service la politique de gestion de la file d attente l absence ou la pr sence d un m canisme de r quisition 2 Les interblocages Le but principal du syst me dans un environnement multiprogramm est le partage des ressources disponibles sur le site entre l ensemble des processus Or certaines de ces ressources tant non partageables un processus poss dant une telle ressource aura un contr le exclusif sur celle ci Si l on g n ralise cela plusieurs processus et plusieurs ressources on voit facilement appara tre les risques d interblocage Leur potentialit est li e aux conditions suivantes 1 les ressources sont utilis es en exclusion mutuelle c est dire par un seul processus la fois 2 chaque
4. me plusieurs processus perdront pour ce faire tout ou partie du travail d j accompli Mais mieux vaut cela que le maintien de l interblocage La gu rison est rendue difficile pour plusieurs raisons i R duction par P9 R duction P9 par P8 P8 E R6 FIGURE 3 R duction d un graphe d allocation Tout d abord nous venons de le voir la d tection de l interblocage n est pas chose ais e et le syst me peut ne pas s en apercevoir tout de suite La plupart des syst mes n ont gu re de facilit pour suspendre ind finiment un processus l enlever du syst me et le reprendre plus tard En particulier cela est hors de question pour les processus temps r els M me si ces possibilit s existaient elles entra neraient un co t d exploitation pro hibitif et n cessiteraient les comp tences d un op rateur attentif ce qui n est pas toujours possible La gu rison d un interblocage de proportions modestes peut tre op r e avec un co t raisonnable mais si l on est en pr sence d un interblocage de grande envergure faisant intervenir plusieurs dizaines ou m me centaines de processus la quantit de travail sera norme La gu rison passe quasi incontournablement par la destruction d un processus afin de r cup rer les ressources qu il poss dait pour permettre aux autres processus de s achever
5. Syst me d exploitation II Allocation de ressources K vin PERROT Aix Marseille Universit 2015 Ce cours est issu des supports de Jean Luc Massat en L3 informatique Luminy Table des mati res 1 Allocations de ressources 1 1 Notion de ressources l a 1 2 Objectifs et outils de l allocation de ressources 2 Les interblocages 2 1 Ressource unique PS 2 2 Interblocage dans un syst me de spooling a a 2 3 Autre forme de blocage la famine 3 La pr vention de blocages 3 1 chec la condition d attente 3 2 chec la condition de non r quisition 3 3 chec la condition d attente circulairel vae e ouo N O oa N 4 vitement d interblocage l algorithme des banquiers 6 5 D tection des interblocages 7 5 1 Graphes d allocation de ressourcel 8 5 2 R duction d un graphe d allocation de ressource 8 6 Gu rison d interblocage 8 7T Et demain 10 1 Allocations de ressources 1 1 Notion de ressources Une ressource est un objet utilisable par un processus Cette utilisation passe par le respect d un mode d emploi qui pr cise comment manipuler la ressource Les ressources sont couramment libres ou allou es Pour chaque ressource ou famille de ressources il existe un allocateur qui a la charge de r pondre
6. age Les syst mes tendent de plus en plus aujourd hui respecter la contrainte de convi vialit Le moins que l on puisse dire est que cette strat gie ne r pond pas cette attente 4 vitement d interblocage l algorithme des banquiers Dans un syst me o les risques d interblocage existent il est toujours possible de l viter en prenant les pr cautions n cessaires chaque allocation de ressource La tech nique la plus connue est sans doute l algorithme des banquiers de Dijkstra ainsi nomm e cause de la grande prudence de ceux ci en mati re de pr ts lt On ne se l che pas des pieds sans se tenir des mains gt Partons du principe que l OS conna t parfaitement l tat de l allocation de ressources aux processus Plus pr cis ment les donn es suivantes sont consid r es comme dispo nibles dispoli nombre de ressources R disponibles sur le syst me maxi j nombre maximum de ressources R utilisables par le processus P allocli j nombre de ressources R couramment allou es au processus P par d finition nous avons donc alloc i j lt maxi j Un processus P peut s ex cuter si et seulement si pour toute ressource R nous avons maxi j alloc i j lt dispoli Un ordre d ex cution P4 P Pa est dit sain si et seulement si les processus P4 P5 peuvent s ex cuter jusqu leur terme les uns apr s les autres dans cet ordre Bie
7. aux requ tes de demande de lib ration et ventuellement de r quisition Les ressources peuvent tre r quisitionnables CPU m moire ou pas unit s de bande partageables m moire disques ou pas imprimantes unit s de bande Elles peuvent tre physiques celles que nous venons de citer coupleurs ou logicielles diteur canal Dans ce dernier cas c est donc un programme qui est partag entre plusieurs processus La duplication de celui ci en autant de copies qu il y a de demandeurs est inconcevable du fait de la perte de taille m moire que cela impliquerait Les ressources logicielles dont le code ne change jamais les donn es tant tablies pour chaque de mandeur sont dites r entrantes Les ressources peuvent galement tre banalis es si on dispose de plusieurs occurrences identiques d une m me ressource 1 2 Objectifs et outils de l allocation de ressources Face tous ces types de ressources il est souhaitable de d finir clairement les objectifs de l allocation de ressources Ces objectifs se retrouvent dans la plupart des allocateurs que nous avons ou que nous allons tudier L OS doit tre quitable dans l allocation de ressources tout en respectant les priorit s En d autres termes pour un m me niveau de priorit les demandes doivent tre trait es sans favoritisme excessif La forme la plus simple de l quit consiste viter la privation de ressource c est dire l
8. cis ment les ressources dont ils ont besoin L algorithme garantit que les requ tes pourront tre satisfaites dans un temps fini Voil qui est rassurant mais gu re suffisant R ciproquement il impose aux processus de restituer les ressources au bout d un temps fini L encore on pourrait s attendre un peu plus d exigence 5 D tection des interblocages Les algorithmes de d tection sont utilis s dans des syst mes o les trois premi res conditions n cessaires sont autoris es et ont pour but de d terminer s il y a attente circulaire L utilisation de ces algorithmes entra ne un co t d exploitation non n gligeable 5 1 Graphes d allocation de ressource L utilisation de graphes orient s repr sentant les allocations et requ tes de ressources facilite la d tection des blocages Dans les sch mas qui vont suivre les carr s repr sentent des processus et les cercles des classes de ressources identiques Les petits cercles contenus dans ces derniers repr sentent le nombre de ressources de chaque classe La figure 2 montre les relations pouvant tre repr sent es dans un graphe d allocation et de requ te des ressources Ces graphes sont modifi s au cours du temps chaque nouvelle allocation ou lib ration de ressource sur le site S il advient qu une ressource d un type donn soit hors service pour une cause quelconque cela se traduira dans le graphe par la suppression d un
9. e l imprimante Une sortie sur un tel p riph rique sera donc aiguill e vers un support d acc s beaucoup plus rapide disque magn tique par exemple afin de lib rer le programme L change effectif avec le p riph rique sera effectu ensuite partir du fichier spool constitu via une unit d change Pour reprendre l exemple de l imprimante on ne pourra tol rer qu un programme qui tourne plusieurs heures au rythme de 100 lignes d impression toutes les 10 minutes monopolise ce pr cieux p riph rique durant tout ce temps C est la raison pour laquelle les fichiers spool ne seront imprim s qu apr s ach vement des programmes correspondants La ressource 1 Le processus B est d tenue par r clame la le processus A ressource 1 processus A processus B Le processus A La ressource 2 r clame la est d tenue par ressource 2 le processus B FIGURE 1 Interblocage simple Dans ces conditions le probl me qui se pose est celui de la place pr vue pour l ensemble des fichiers spool Le spectre de l interblocage se dessine peu peu Il peut en effet arriver un moment o la zone de spool tant satur e plus aucun processus ne puisse op rer des sorties mais aucun n tant achev la zone spool ne peut se vider Que faire ce moment l Supprimer un processus et perdre toute l ex cution pour r cup rer la place qu il occupait Qui nous assure que l on n
10. e sera pas oblig ensuite d en supprimer un deuxi me puis un troisi me Commencer imprimer les sorties d un des processus Lequel choisir Monopolisera t il l imprimante longtemps Le principe lui m me est il acceptable Aurait on pu pr venir cette situation en interdisant tout acc s un nouveau fichier spool c est dire en fait tout nouveau travail d s que l occupation avait atteint un certain taux 2 3 Autre forme de blocage la famine Dans tout syst me o des processus sont en attente pendant que des ressources sont allou es et en particulier le processeur il est possible que l activation d un processus soit ind finiment retard e alors que les autres sont servis Cette situation de famine est aussi pr judiciable qu un blocage Lorsqu une ressource est allou e sur la base de priorit s il se peut qu un processus reste en attente pendant qu une suite ininterrompue de processus de priorit plus lev e ont la pr f rence Or le propre d un syst me est d tre la fois quitable et efficace envers les processus en attente On verra plus loin comment on peut accro tre la priorit au fur et mesure que le temps d attente augmente Ce type de technique pr sent pour la ressource processeur peut tre appliqu pour n importe quelle ressource 3 La pr vention de blocages C est assur ment la technique la plus utilis e par les designers de syst me Nous allons v
11. ise en d faut mais quel prix Quel gaspillage de ressources Supposons qu un programme dont l ex cution dure plusieurs heures ait besoin la plupart du temps de un ou deux d rouleurs de bandes sauf pendant un court instant en fin d ex cution o dix unit s lui sont n cessaires En appliquant cette strat gie le processus devra monopoliser les dix d rouleurs pendant toute son ex cution De plus il devra attendre qu ils soient tous libres avant de pouvoir tre initialis ce qui risque d tre long Nous nous trouvons devant un risque flagrant de famine Une solution utilis e pour rem dier ce gros d faut consiste op rer par tapes lorsque comme dans l exemple que nous venons de voir le programme s y pr te Dans ces conditions l allocation des ressources se fera elle aussi par tape ce qui r duit consid rablement la sous utilisation des ressources mais engendre un co t d exploitation plus lev 3 2 chec la condition de non r quisition Supposons que le syst me autorise un processus conserver les ressources qu il d tient alors qu il op re une nouvelle demande Tant que les ressources suppl mentaires de mand es sont libres le blocage n appara t pas Mais si nous arrivons dans un sch ma montr dans la figure 1 nous sommes en situation d interblocage Havender pr conise en pareil cas d imposer un processus demandeur de lib rer les ressources qu il d tient pour ensuite
12. it se faire aujourd hui En fait ce sont les m thodes de pr vention carr es brutales mais efficaces et sans risque qui sont le plus souvent employ es le blocage tant encore tout fait occasionnel Dans les syst mes futurs les interblocages devront tre trait s de fa on syst matique et efficace pour plusieurs raisons Les syst mes s orienteront de plus en plus vers des op rations parall les asynchrones abandonnant les sch mas s quentiels Les bancs de processeurs seront monnaie cou rante autorisant un parall lisme norme L allocation des ressources sera dynamique La convivialit grandissante des syst mes fera que l on utilisera ce que l on voudra quand on le voudra De plus en plus les donn es seront assimil es des ressources En cons quence la quantit des ressources que devra g rer un syst me atteindra une taille gigantesque On peut donc imaginer que ce probl me tout en devenant de plus en plus important et de plus en plus difficile traiter trouvera n anmoins dans les technologies et les structures futures des solutions efficaces 10
13. les redemander en y ajoutant la nouvelle Cette strat gie met en chec la troisi me condition n cessaire Mais l encore quel prix Lors de la lib ration obligatoire des ressources d tenues tout un travail peut tre perdu bonjour les performances syst me Si cela se produit peu souvent c est tol rable mais si c est fr quent ce peut tre catastrophique en particulier des travaux prioritaires et ou ch ance risquent de voir leur statut s rieusement remis en cause sans parler des risques vidents de famine 3 3 chec la condition d attente circulaire C est le but recherch par la troisi me strat gie propos e par Havender Chaque type de ressource ayant un num ro tout processus ne pourra effectuer ses requ tes que par ordre croissant dans ces types Cette strat gie a t implant e dans de nombreux syst mes mais non sans difficult Les diverses ressources tant requises au moyen de leur num ro d ordre l ajout d une nouvelle ressource sur un site n cessite la modification de tous les programmes La portabilit est nulle Le num ro d ordre allou aux diverses ressources doit refl ter l ordre d utilisation de la plupart des programmes susceptibles d tre ex cut s sur le site Si d aventure un programme ne respecte pas cet ordre lt canonique gt les ressources doivent tre ac quises ventuellement longtemps avant leur utilisation effective D o un gaspill
14. n en tendu l ex cution d un processus P implique la lib ration par Pe des ressources qu il a utilis es Un syst me est dit sain si il existe un ordre d ex cution sain des processus Si un syst me est sain alors il ne peut pas y avoir d interblocages Par contre si le syst me n est pas sain un interblocage peut appara tre mais ce n est pas une obligation 1 Disons que c tait peut tre vrai l poque de nos jours on aurait certainement choisi un autre nom Fe En r sum l apparition d un tat non sain n implique pas pour autant qu il y aura in vitablement un interblocage La seule chose que cela implique est qu une s quence d favorable d v nements peut conduire un interblocage En se basant sur cette propri t l OS face une demande d allocation de la ressource R au processus P applique l algorithme suivant 1 les annonces sont elles respect es c d alloc i j lt maxi jl 2 si j alloue R P l tat obtenu est il sain 3 dans l affirmative je r alise l allocation sinon je suspends le processus P qui ne peut donc pas continuer son ex cution Le principe de l algorithme des banquiers est de refuser toute requ te ayant pour effet de mettre le syst me dans un tat non sain En r sum les conditions d exclusion mutuelle d attente et de non r quisition sont autoris es les processus doivent annoncer leurs besoins en ressources
15. oir ici quelques unes des m thodes propos es en consid rant leurs effets la fois sur les utilisateurs et sur le syst me en particulier du point de vue des performances Havender proposa de mettre en d faut les conditions n cessaires d interblocage en imposant des contraintes aux processus Tout processus doit annoncer les ressources qui vont lui tre n cessaires et ne d marrer que lorsque toutes sont disponibles Si un processus besoin d une ressource suppl mentaire il doit lib rer celles en sa possession et faire une nouvelle demande incluant la nouvelle Les ressources sont class es par type dans un ordre lin aire auquel devra se sou mettre tout processus pour ses demandes d allocation Il est noter que chacune des strat gies propos es ci dessus a pour but de mettre en d faut une des conditions n cessaires d interblocage sauf la premi re En effet nous voulons nous r server le droit de disposer de ressources d di es 3 1 chec la condition d attente La premi re strat gie d Havender impose que toutes les ressources n cessaires un processus soient libres avant qu il puisse commencer ce sera donc du lt tout ou rien gt En aucune fa on les ressources utiles ne pourront tre r serv es jusqu ce que toutes tant libres l ex cution puisse commencer elles devront tres toutes libres simultan ment La deuxi me condition n cessaire est ainsi trivialement m
16. petit cercle dans le grand cercle correspondant au type en question R1 P1 r clame a P1 une ressource de type R1 Une ressource b P1 de type R2 a t allou e P1 FIGURE 2 Graphe de requ te et d allocation de ressource Afin de d terminer s il est en situation de blocage le syst me devra proc der une r duction du graphe 5 2 R duction d un graphe d allocation de ressource Si les requ tes d un processus peuvent tre satisfaites on dit que le graphe est r duit par ce processus cela signifie que l on consid re le graphe comme si le processus s tait achev lib rant ainsi les ressources qu il d tenait Cela se traduit par la suppression des fl ches provenant de ressources et aboutissant ce processus et de celles partant de ce processus vers d autres ressources Si un graphe peut tre r duit par tous ses processus il n y a pas de blocage Dans le cas contraire les processus irr ductibles constituent l ensemble des processus en interblocage La figure f3 montre les diverses tapes de r duction d un graphe permettant d aboutir la conclusion qu il n y a pas d interblocage L ordre dans lequel les r ductions se font est sans importance le r sultat sera toujours le m me 6 Gu rison d interblocage Une fois que le syst me a d termin qu il y avait interblocage il doit le gu rir en supprimant une ou plusieurs des conditions n cessaires Habituellement un ou m
17. processus utilise simultan ment plusieurs ressources qu il acquiert au fur et mesure de ses besoins sans n cessairement lib rer celles qu il poss de d j 3 les ressources ne peuvent tre r quisitionn es 4 il existe un ensemble de processus po P1 Pn tel que chaque p attend une ressource occup e par p 1 et pn attend une ressource occup e par po Apr s avoir pr sent quelques exemples nous tudierons dans les paragraphes qui suivent quelques m thodes employ es pour pr venir viter d tecter et gu rir les inter blocages La pr vention est bas e sur le principe de maintenir chaque instant le syst me dans un tat tel qu aucun interblocage ne soit possible Cette attitude est parfaitement efficace tant que l on ne consid re que l aspect interblocage mais en contre partie elle engendre un mauvais rendement d utilisation des ressources N anmoins ce genre de technique est tr s largement utilis Dans l vitement de blocage le but recherch est de rendre moins strictes les condi tions impos es au syst me comparativement la pr vention afin de mieux utiliser les ressources En fait dans l vitement la possibilit de blocage existe chaque instant mais chaque fois que celui ci s approche il est prudemment contourn Les m thodes de d tection se limitent d terminer si un interblocage est apparu et si c est le cas quels sont les processus et les ressou
18. rces qui sont impliqu s Ce travail tant fait l interblocage peut tre trait et supprim Les m thodes de gu rison sont utilis es pour lt gu rir gt un interblocage en per mettant certains processus impliqu s de terminer leur ex cution afin de lib rer les ressources qu ils utilisent En fait ces techniques la plupart du temps consistent supprimer un ou plusieurs des processus bloqu s Ceux ci sont repris ensuite g n ralement partir du d but leur ex cution pr c dente ayant t perdue 2 1 Ressource unique La plupart des risques d interblocage dans un syst me sont dus aux ressources acc s unique La figure 1 illustre ce type de configuration Nous y voyons deux processus et deux ressources acc s unique Une fl che allant d une ressource un processus indique que celui ci d tient celle l une fl che allant d un processus une ressource signifie que celui l est demandeur de celle ci Nous avons donc dans le cas pr sent un interblocage puisque le processus poss de la ressource 1 et d sire acqu rir en plus la ressource 2 alors que celle ci est d tenue par le processus B qui r clame la ressource 1 Cette configuration boucl e est caract ristique des interblocages 2 2 Interblocage dans un syst me de spooling Rappelons que l utilit d un syst me de spooling est de ne plus assujettir l ex cution d un programme la lenteur de certains p riph riques tels qu

Cours02

Contents

Download Pdf Manuals

Related Search

Related Contents