Home

Support de cours syst`eme d`exploitation

Contents

1. m moire N ns succ s associative adr virtuelle nhyp npv dep Y Y adr npp dep physique O m i v rifier que AS npv lt L a E i 7 a E l A E i a 110 npp R de base Li Table des pages de l hyperpage nhyp d faut de page Table des hyperpages si pr sent 0 F1G 7 3 Pagination deux niveaux Dans ce sch ma la m moire virtuelle est divis e en hyperpages elles m me divis es en pages virtuelles Une adresse virtuelle a maintenant la forme nhyp npv dep Le num ro nhyp gt permet d acc der une table d hyperpages dont chaque entr e comporte un pointeur vers la table de pages de l hyperpage Seules les hyperpages effectivement utilis es se trouvent en m moire principale Dans certains syst mes les tailles de pages et d hyperpages pouvant tre variables un champ taille permettra de contr ler la limitation et d tecter une ventuelle erreur d adressage Les tables de pages sont utilis es comme dans la pagination simple Une m moire associative qui conserve les triplets nhyp npv npp les plus r cents acc l re la consultation qui n cessite deux acc s suppl mentaires la m moire en cas d chec 62 Exemple La pagination a deux niveaux a t introduite sur l IBM 360 67 et reprise sur ses successeurs de la s rie 370 La taille des pages et des hyperpages peut tr
2. niveau 0 y niveau 1 p p niveau 2 y me niveau n 1 o i y niveau n arriv e CPU sortie FIG 5 4 Sch ma de principe du tourniquet multi niveaux de temps il passera en queue de la file de niveau inf rieur celle o il se trouvait jusqu ce qu il atteigne la file de plus bas niveau Dans ce sch ma d ordonnancement la taille du quantum s accro t au fur et mesure que l on descend dans les niveaux de file En cons quence plus un travail est long plus le temps CPU dont il b n ficie est grand Mais en contre partie le processeur lui sera allou plus rarement puisque les processus des files sup rieures ont une plus grande priorit Un processus en t te de quelque file que ce soit ne pourra devenir actif que si les files de niveau sup rieur si elles existent sont vides Il y aura r quisition d s qu un travail arrivera dans la file de plus haut niveau Consid rons pr sent la fa on dont ce m canisme s adapte aux diff rents types de travaux Il favorisera les utilisateurs interactifs dont chaque requ te sera envoy e dans la file prioritaire et satisfaite avant l puisement du quantum De m me les travaux travaillant essentiellement en entr e sortie seront avantag s si l on suppose que le quantum de la file prioritaire est assez grand pour qu une demande d change survienne avant qu il expire Dans c
3. npl dep __ v rifier que npl lt RL y npp prot n Y gt npp gt npp dep z adr physique R de base Table des pages desc F1G 6 8 Organisation d une table de pages npl d placement adresse logique si npl lt RL alors si les protections sont respect es alors adr physique desc npl npp d placement sinon d routement sur violation de protection fin si sinon d routement sur erreur d adressage fin si Le champ desc np1 prot indique le mode d acc s autoris la page logique npl Cette informa tion est utilis e par les m canismes de protection et un acc s non autoris provoque un d routement pour violation de protection Notons qu une table de pages repr sente le contenu d une m moire logique particuli re Si le syst me d exploitation permet chaque processus ou chaque usager du syst me de d finir une m moire logique distincte il doit g rer une table de pages distincte par processus ou par usager Le pointeur vers l origine de cette table RB fait alors partie du contexte du processus ou de l usager Les tables des pages se trouvent en m moire physique dans la partition r serv e au syst me d exploitation La m moire logique d un processus n est plus repr sent e d une mani re contigu en m moire centrale voir figure En effet l indirection des acc s par la table de pages permet de loger les pages logiques dans
4. F1G 2 1 Un exemple d ex cution 2 2 Le m canisme des interruptions Dans tous les types de syst me il est toujours n cessaire de consid rer un travail courant le programme en cours d ex cution et un travail exceptionnel dont le but est de traiter un v nement On peut citer les exemples suivants Dans les syst mes de conduite de processus certains v nements importants voir m me graves doivent tre pris en compte dans les d lais les plus brefs En d autres termes il faut donc interrompre le travail courant relev s des capteurs pour ex cuter un programme prioritaire Il existe toujours un dialogue entre l U C et les organes d E S Notamment une unit de disque ou une imprimante signalent l U C que l E S est termin e Dans ce cas galement le travail courant doit tre interrompu pour prendre en compte cette nouvelle situation de mani re optimiser l utilisation des organes d E S Ces deux exemples ont un point en commun les v nements exceptionnels sont asynchrones c est dire qu il n est pas possible de pr voir leur arriv e Pour contourner ce probl me les machines disposent d un m canisme g n ral permettant de traiter ces v nements asynchrones C est ce m canisme complexe qui vous est pr sent dans cette section Les interruptions permettent d interrompre provisoirement le d roulement d un programme en cours pour ex cuter une routine consid r e comme p
5. tant que Ul victime 1 faire Ulvictime 0 victime suivant victime fin faire Ulvictime 1 victime suivant victime Le pointeur progresse jusqu la premi re page physique dont le bit est z ro les pages physiques rencontr es en route dont le bit est donc 1 re oivent une seconde chance de n tre pas prises comme victime et leur bit est forc z ro Cet algorithme est galement appel algorithme de l horloge clock la progression du pointeur tant analogue celle de l aiguille d une horloge La mise 1 du bit lors d une r f rence peut tre r alis e par un m canisme mat riel ou logiciel De nombreuses tudes exp rimentales ont permis d valuer les algorithmes de remplacement La figure est une repr sentation synth tique des r sultats obtenus On constate 66 Nombre FES de d fauts de page FINUFO LRU OPT Re Taille de la m moire F1G 7 6 Performances des algorithmes de remplacement que les algorithmes se classent en moyenne par performances d croissantes dans l ordre OPT LRU Clock FIFO les performances de FIFO sont du m me ordre que celles du tirage au hasard que l influence de la taille de m moire est tr s largement sup rieure celle de l algorithme de remplacement autrement dit on am liore davantage les performances d un programme en augmentant le nombre de pages physique allou es plut t qu en raffinant l algori
6. un niveau m diocre fonction du nombre moyen de t ches en attente et du temps d ex cution moyen d une t che On sera arriv l algorithme FIFO que nous verront dans le paragraphe suivant Consid rons donc la valeur optimale que nous avons obtenue pr c demment Elle repr sente en fait une petite fraction de seconde Mais cette valeur est elle vraiment bien adapt e chacun des types de t che Est elle assez grande pour que la majeure partie des requ tes interactives puissent tre trait es en un seul quantum En particulier si nous pouvons avoir une distribution moyenne dans le temps des demandes d change mises par m processus interactif il serait avantageux que la valeur du quantum soit sup rieure l intervalle entre deux changes car cela diminuerait d autant le 35 nombre de r quisitions inutiles il vaut mieux qu un processus n utilise pas tout son quantum et c de le contr le cause d une demande d change plut t qu il soit interrompu attende son tour r cup re le contr le pour aussit t lancer un change Temps de r ponse moyen 4 quantum F G 5 1 Influence du quantum sur le temps de r ponse moyen En fait on s aper oit que la valeur de ce quantum va varier d un syst me un autre mais aussi en fonction du taux de charge On vient de montrer qu il peut aussi d pendre du processus 5 2 6 Priorit s Les priorit s peuvent tre allou es automatiquement par le syst me
7. premier servi FIFO La technique FIFO est assur ment la plus simple et de ce fait n engendre qu un tr s faible co t propre C est une technique sans r quisition tout travail commenc se poursuit jusqu ach vement L ordre de priorit correspond de fa on naturelle l ordre d arriv e arriv e sortie F1G 5 2 L ordonnanceur FIFO De ce point de vue il est donc quitable mais il faut toutefois regretter le fait que les longs travaux occasionnent une longue attente des travaux brefs qui suivent et r ciproquement une multitude de petits travaux peut provoquer une longue attente de travaux importants FIFO pr sente une faible variance il est donc plus pr dictible que la plupart des autres techniques De toute vidence il n est pas utilisable dans les syst mes interactifs car il ne garantit pas un bon temps de r ponse C est en particulier une des principales raisons qui font que cette technique est rarement utilis e aujourd hui l tat brut gt N anmoins il faut noter qu elle peut tre associ e une technique plus sophistiqu e qui accordera des priorit s g n rales les processus de m me priorit tant consid r s selon un sch ma FIFO 5 3 3 Tourniquet Round Robbin L ordonnancement de type tourniquet s inspire de la technique FIFO l association d une tranche de temps autorisant la r quisition Les processus au fur et mesure qu ils
8. des proc dures des r gles d utilisation des donn es et proc dures exprimant des restrictions restrictions d acc s aux donn es lecture seule autoris e restrictions sur l ordre des proc dures contraintes de simultan it dans l ex cution des proc dures ou l acc s aux donn es l heure actuelle aucune solution satisfaisante n a encore t propos e pour exprimer les sp cifications d une interface ou les contraintes d utilisation si ce n est le recours au langage naturel Deux m thodes sont utilis es pour prendre en compte dans la sp cification les ventuelles erreurs Chaque proc dure comporte un param tre suppl mentaire code d erreur modifiable par la proc dure La valeur finale de cette variable constitue un compte rendu interpr table un niveau sup rieur chaque cause d erreur est associ e une proc dure de traitement sp cifique En cas d erreur un m canisme que nous d taillerons ult rieurement d routement d clenche automatique ment la proc dure correspondante Dans tous les cas le traitement d une erreur consistera revenir un tat stable du syst me o l ex cution puisse reprendre normalement en perdant le moins d information possible Des deux m thodes de prise en compte d erreur pr sent es plus haut la seconde n cessite un m canisme suppl mentaire mais elle sera pr f rable la premi re pour deux raisons essentielles S
9. es sorties de chaque processus apr s que le processeur lui ait t allou ne l utilise t il qu un temps tr s court avant de r clamer un change 2 le taux d utilisation du processeur pour chaque processus lorsque le processeur lui est allou l utilise t il pendant toute la tranche de temps impartie 3 fonctionnement interactif ou traitement par lots les utilisateurs interactifs mettent g n ralement des requ tes simples qui doivent tre satisfaites tr s rapidement alors que les utilisateurs batch n tant pas pr sents peuvent subir des d lais ceux ci devant toutefois rester dans des limites raisonnables 4 degr d urgence un processus batch ne requiert pas de r ponse imm diate alors qu un processus temps r el n cessite des r ponses tr s rapides 5 priorit des processus les processus de forte priorit doivent b n ficier d un meilleur trai tement que ceux de priorit plus faible 6 taux de r quisition lorsqu un processus est de faible priorit par rapport aux autres il en d coule un fort taux de r quisition Dans ces conditions le syst me doit il essayer de l avantager ou au contraire attendre que les priorit s redeviennent comparables afin d viter les temps de commutation effectu s en pure perte vu la forte probabilit de r quisition 7 temps cumul d allocation du processeur doit on p naliser un processus ayant b n fici d un temps d ex cution imp
10. pendance pour la conception Description totale du comportement d une machine par les sp cifications de son interface Ind pendance pour la modification Les modifications dans la r alisation d une machine n alt rent en rien celles qui l utilisent si les sp cifications d interface demeurent inchang es Ind pendance pour la mise au point Son interface ayant t sp cifi e une machine M peut tre mise au point ind pendamment de celles qui l utilisent r ciproquement une machine M tant r alis e les machines utilisant M peuvent tre mises au point ind pendamment de M 1 2 2 Notion d objet La d composition hi rarchique que l on vient de pr senter r pond mal certains aspects de structuration des syst mes En particulier la description de collections d l ments ayant des ca ract ristiques communes la cr ation ou la destruction dynamique d l ments seront facilit es gr ce la notion d objet nouvel outil de structuration permettant d exprimer des concepts importants tels que d signation liaison type protection Un objet est concr tis par une repr sentation repr sentation externe laquelle a acc s l utili sateur et repr sentation interne qui est celle concernant le syst me Cette repr sentation des objets ainsi que la fa on d y acc der font appel des fonctions d acc s Un autre concept permet de regrouper un ensemble d objets ayant des caract ristiques com munes c est la
11. rarchisation d un syst me d interruption Les syst mes d interruption sont quelquefois plus labor s et sont constitu s d un type d organi sation tr s modulaire ayant les caract ristiques suivantes Les interruptions sont group es en un certain nombre de niveaux hi rarchis s d crits plus haut Un niveau regroupe plusieurs sous niveaux poss dant chacun son fil d interruption et sa priorit l int rieur du niveau les programmes associ s aux sous niveaux d un m me niveau ne peuvent s interrompre les uns les autres leur priorit respective n intervenant que lors du choix si plusieurs d entre eux sont en attente simultan ment Un sous niveau regroupe lui m me plusieurs demandes d interruptions les causes d interrup tion tant recherch es par test d indicateurs 2 3 2 Commande du syst me d interruption Chaque niveau d interruption peut tre dans l un des tats suivants tat d sarm le niveau n accepte aucune demande d interruption 15 tat arm le niveau accepte et m morise une demande d interruption On peut armer ou d sarmer un niveau d interruption par programme en utilisant des instructions privil gi es Cette possibilit est donc r serv e au S E tat masqu le niveau a t inhib par programme de sorte que l interruption a pu tre m moris e mais ne peut tre prise en compte par la CPU tat d attente l interruption peut tre prise en c
12. sous utilis swapping in La r partition globale de la charge consiste agir sur le degr de multiprogrammation pour maintenir les performances du syst me dans des limites acceptables charge faible ou mod r e la multiprogrammation permet d augmenter le taux d utilisation du processeur en utilisant les temps morts dus au blocage ou l attente de pages forte charge on voit appara tre l effet inverse qui caract rise l croulement Ce comportement sugg re l existence d une valeur optimale du degr de multiprogrammation qui maximise le taux d utilisation du processeur pour une configuration mat rielle et une charge donn e Cela est confirm par l tude de mod les analytiques et par l exp rience Un algorithme id al de r gulation de charge devrait maintenir le degr de multiprogrammation au voisinage de cette valeur optimale Plusieurs crit res empiriques d optimalit ont t propos s lls reposent tous sur le m me principe tenter de d tecter le d but de l croulement par la mesure du taux de d fauts de page et maintenir le syst me au dessous de ce point critique L exp rience montre qu il est utile de pr voir un certain amortissement pour viter le pompage oscillations brutales provoqu es par la r gulation lorsque la charge est proche du seuil critique Cela est notamment obtenu en conservant une r serve de pages physiques libres destin es absorber les variations transitoires du taux de d fau
13. 1 L1 F G 6 13 Une m moire segment e Une adresse logique dans un syst me segment aussi appel e adresse segment e est un couple n de segment d placement Comme dans les m moires pagin es le S E maintient une table des segments pour chaque processus figure La correspondance proprement dite est tablie par le mat riel de la mani re suivante seg d pl adresse logique segment e si seg lt RL et d pl lt desc seg taille alors si les protections sont respect es alors adresse physique desc seg origine d pl sinon d routement sur violation de protection fin si sinon d routement sur erreur d adressage fin si Ce m canisme doit tre coupl une m moire associative pour am liorer le temps d acc s moyen en vitant l utilisation de la table des segments Les avantages de cette organisation sont doubles d une part la notion de segment est direc tement utilisable dans un processus et de ce fait on peut esp rer une r duction des temps d acc s moyens les acc s fr quents tant regroup s sur un petit groupe de segments voire m me sur un segment unique d autre part la notion de protection est plus facilement utilisable puisqu elle porte directement sur des segments c est dire des objets logiques 57 m moire physique SS code 2 taille origine prot RB 0 2 L2 code 1 RL table des segments desc SNS F1G 6 14 T
14. 2 5 Calibrage de la tranche de temps La d termination de la tranche de temps ou quantum est critique dans un syst me Doit elle tre longue ou courte Doit elle tre fixe ou variable Doit elle tre la m me pour tous les utilisateurs ou d termin e s par ment pour chacun d eux Aux conditions limites selon que l on fait tendre le quantum vers l infini ou vers z ro un processus s ach vera sans que l ordonnanceur soit intervenu ou au contraire tout le temps CPU sera utilis par l ordonnanceur lui m me et aucun processus ne pourra se d rouler Afin d ajuster le quantum une valeur optimale il nous faut consid rer la courbe du temps de r ponse moyen figure Supposons qu on ait le moyen de faire varier le quantum gr ce un curseur Lorsque celui ci est z ro l ordonnanceur tant la seule t che active le temps de r ponse est infini D s que nous tournons l g rement le curseur augmentant ainsi la dur e du quantum le temps de r ponse commence diminuer Si nous continuons nous allons arriver une position telle que si nous tournons encore l g rement le curseur le temps de r ponse va commencer augmenter Nous aurons atteint la valeur optimale Si nous tournons le curseur fond le temps de r ponse va d cro tre pour le processus actif ce moment l puisqu il va se terminer sans tre interrompu mais va consid rablement augmenter pour tous les autres Le temps de r ponse moyen se stabilisera
15. Ainsi par exemple on peut r cup rer les erreurs arithm tiques ou encore les lectures au del de la fin de la m moire Toutefois le caract re strictement synchrone des d routement interdit leur retard de prise en compte comme cela est possible pour les interruptions en l occurrence la notion de masquage ne peut s appliquer En r sum le mode esclave les d routements vers le S E en cas d erreur et le m canisme des appels syst me imposent un cadre strict pour l ex cution des programmes utilisateur Les syst mes d exploitation r cents sont dits dirig s par les interruptions car ils ne s ex cutent que sur demande explicite Cette demande provenant de l ext rieur interruption mat rielle ou des programmes en cours d ex cution d routement et appel syst me Chapitre 3 Les processus 3 1 D finition Un processus est un programme en cours d ex cution Il faut d embl e faire la diff rence entre un programme qui est un fichier inerte regroupant des instructions de la CPU et un processus qui un l ment actif Figeons un processus pour en observer ses composantes Nous trouvons des donn es variables globales pile et tas stock es dans une zone de la m moire qui a t allou e au processus la valeur des registres g n raux et sp cialis s de la CPU lors de l ex cution les ressources qui lui ont t allou es par le syst me d exploitation m moire principale fichiers ouver
16. 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 la section 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 4 3 La pr vention de blocages C est assur ment la technique la plus utilis e par les designers de syst me Nous allons voir 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 vues en 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 soumettre 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 interbl
17. de contr le des processus On trouve ainsi la file des processus pr ts la file des processus connus la file des processus en attente qui se d compose en la file des processus qui attendent la disponibilit de la ressource unit d E S 0 de la ressource m moire etc la file des processus qui attendent la fin d une op ration d E S sur l unit d E S 0 le disque principal sur l unit d E S 1 un terminal etc etc La figure illustre le chemin suivi par notre diteur de texte dans les files du syst me lors de sa demande d un caract re sur l unit d entr e standard 3 4 Gestion des processus Les processus sont les principaux l ments actifs du syst me Dans ce cadre il est logique que la cr ation d un nouveau processus soit demand e par un processus existe donc une filiation entre processus p re et le s processus fils Lors du d marrage de la machine le S E lance un processus qui est orphelin puisqu il n a pas de p re Ce processus est souvent appel init Le premier r le de ce processus est de lancer des fils qui auront chacun une fonction dans l organisation g n rale de la machine Par exemple un processus pour g rer les E S asynchrones avec les terminaux un processus pour g rer les connexions au syst me avec demande et v rification d un nom d utilisateur et d un mot de passe un processus pour g rer l allocatio
18. de probl me puisqu elle a lieu soit avant soit apr s l ex cution de TAS mais jamais au milieu Soit p une variable enti re propre chaque processus et mutex un variable enti re partag e par les processus qui d sirent entrer en S C L entr e en S C est r alis e par init mutex 1 prologue r p ter TAS p mutex jusqu p 1 pilogue mutex 1 Pour programmer l exclusion mutuelle d acc s une ressource on a utilis un dispositif c bl d ex clusion mutuelle mutex Cette m thode n est pas utilisable si la s quence critique est longue car elle monopolise le processeur sur l attente active 8 2 60 Verrou Pour lib rer la CPU on utilise une file d attente dans laquelle on place tout processus demandeur ne pouvant entrer en section critique Lorsqu un processus sort de la S C un processus de la file est activ si celle ci est non vide Un verrou v est un couple d f dans lequel d est un bool en et f une file d attente de processus proc dure init var v verrou d but v d faux fin proc dure verrouiller var v verrou d but si v d vrai alors entrer le processus appelant dans la file v f suspendre le processus appelant sinon v d vrai fin si fin 74 proc dure d verrouiller var v verrou d but si la file v f est vide alors v d faux sinon sortir un processus Q de la file v f r veiller le processus Q fin si fin Pour programmer l exc
19. est pas toujours possible La gu rison d un interblocage de proportions modestes peut tre op r e avec un co t raison nable 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 Comme nous l avons dit la gu rison passe forc ment 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 Quelquefois la destruction de plusieurs processus s impose pour r cup rer un nombre suffisant 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 symptomatique 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 30 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 gu rir pour ensuite les reprendre en l tat sans perte de travail Et le temps d exploita
20. finies ou transactions souvent interactives Le syst me poss de un grand nombre de points d acc s terminaux et un grand nombre de transactions peuvent se d rouler en m me temps Les exemples types d applications de ce genre sont les syst mes de r servation de places de train ou d avion de gestion de comptes bancaires de consultation ou de documentation L encore une des principales qualit s requises du syst me est la fiabilit int grit et coh rence des donn es Un tel syst me doit en outre poss der des qualit s de disponibilit et des capacit s de tol rance aux pannes 1 4 4 Syst mes en temps partag Le r le d un syst me en temps partag est de fournir ses services un ensemble d usagers chacun b n ficiant de services quivalents ceux accessibles sur une machine individuelle mais aussi de services li s l existence d une communaut d usagers partage d information communi cation entre usagers De plus les co ts tant r partis entre un grand nombre d usagers ceux ci peuvent b n ficier de services qui leur seraient inaccessibles individuellement p riph riques sp ciaux ou logiciels n cessitant un grand espace m moire Les probl mes rencontr s sont donc la fois ceux des ordinateurs individuels et ceux des syst mes transactionnels d finition de la machine virtuelle pour chaque usager partage et allocation des ressources physiques communes processeurs m moires organes d
21. fur et mesure que l attente s accro t mettre en uvre des priorit s fond es sur des crit res pertinents avoir la possibilit de r ajuster ces priorit s soit de mani re globale n cessit de modula rit soit de mani re ponctuelle au cours du temps priorit s dynamiques favoriser les processus ayant un comportement souhaitable veiller ne pas accepter de nouveaux travaux lorsque le syst me est en surcharge etc 33 La liste des contraintes que nous venons d noncer est loin d tre exhaustive mais suffit d j mettre en vidence les conflits 3 10 4 8 1 9 Ceci d note donc une grande complexit dans la d termination des t ches ligibles ce qui est justement en compl te opposition avec le point 5 Ceci explique en partie la raison pour laquelle les ordonnanceurs ne seront souvent qu un ensemble de compromis tr s satisfaisants dans certains cas de figures mais s av rant moyennement voire fortement critiquables dans d autres circonstances Ceci explique aussi pourquoi nous ne pourront pas vous pr senter ensuite L Ordonnanceur avec un grand O mais une panoplie de r alisations dont chacune pourra s av rer satisfaisante sur un site donn mais intol rable sur un autre 5 2 2 Crit res consid rer Afin de pouvoir r aliser tout ou plut t partie des objectifs pr sent s au paragraphe pr c dent le m canisme d ordonnancement doit consid rer 1 le taux des entr
22. informations d signables dans son programme objets l ensemble des informations de d signation noms la mise en correspondance noms objets Dans un programme crit en langage volu noms et objets sont d finis par ce langage Ils sont diff rents de ceux que manipule le processeur physique Le programme doit donc subir une s rie de transformations appel e liaison Celle ci comporte une tape de traduction mise en correspondance des objets avec les emplacements m moire et des noms avec les adresses relatives correspondantes une tape d dition de lien liaison entre programmes traduits s par ment et enfin une tape de chargement fixation d finitive des adresses jusque l d finies une translation pr s La s paration conceptuelle des probl mes de d signation et liaison d une part et des probl mes d allocation m moire d autre part peut tre sch matis e par la figure Langage M moire M moire logique physique Home adresse adresse logique physique d signation allocation et liaison de m moire F G 6 1 Transformation des adresses 42 43 Le fait que la notion de m moire logique ne soit pas rest e un outil conceptuel mais ait t mise en uvre sur certaines machines par des dispositifs physiques de transformation d adresse a conduit ce que la s paration des fonctions soit plus ou moins bien respect e M moire logique contigu El
23. l unit centrale U C Il assure galement des fonctions de protection vis vis du programme en cours d ex cution de limitation de dur e et de supervision des entr es sorties Pour r aliser ces op rations le moniteur est toujours pr sent en m moire l est dit r sident La fin des ann es 50 marque le d but du traitement par lots batch processing Une machine pr pare les donn es en entr e lecture des cartes perfor es cette poque tandis que la machine principale effectue le travail et qu une troisi me produit le r sultat Il existe donc un parall lisme des t ches entre lecture ex cution et impression Les op rations d E S ne sont plus r alis es par la CPU ce qui lib re du temps de calcul 1 3 2 Syst mes multiprogramm s La multiprogrammation arrive au d but des ann es 60 Elle est caract ris e par la pr sence simultan e en m moire de plusieurs programmes sans compter le S E lui m me Cette caract ristique s explique de la mani re suivante l ex cution d un programme peut tre vue comme une suite d tapes de calcul les cycles d U C et d tapes d E S les cycles d E S comme le montre la figure Sur un syst me monoprogramm la CPU est donc inutilis e durant les cycles d E S L id e de base est d utiliser ces temps d attente pour ex cuter un autre programme Ce pro gramme doit n cessairement tre d j pr sent en m moire afin d viter l E S de chargement puisque justement on ch
24. la restauration du contexte 4 Forcer dans le compteur ordinal la valeur pr alablement sauvegard e De cette description on tire deux conclusions 1 les traitants d interruption s ex cutent en mode ma tre donc avec des droits tendus 2 l ex cution du programme interrompu n est pas perturb e par le traitement de l interruption L tape 4 est souvent r alis e au moyen d une instruction de la CPU qui provoque le retour au programme interrompu RTI Cette tape est appel e acquittement de l interruption Les principales utilisations du processus d interruption sont les suivantes Interruption logicielle ou d routement provoqu e par la CPU lors de la d tection d une situation anormale Par exemple appel explicite du S E instruction incorrecte ou inconnue violation de privil ge d passement de capacit division par z ro tentative d acc s une zone prot g e de la m moire Interruption mat rielle g n r e par une unit externe la CPU afin de lui signaler l apparition d un v nement ext rieur Par exemple fin d une E S impulsion d horloge changement d tat d un des p riph riques pr sence d une valeur int ressante sur un capteur Certaines CPU n ont qu une seule cause d interruption Dans ce cas un ou logique de toutes les causes possibles sera effectu et le traitant d interruption qui est unique devra au pr alable tester
25. la file s fp m Q m reprendre le processus Q sinon entrer m dans la file s fm fin si fin La gestion de messages de longueur variable est difficile aussi ce m canisme impose en g n ral une taille fixe Le message peut tre par exemple une adresse chang e par les deux processus Ceci permet en particulier de r soudre simplement le partage d un ensemble de tampons dans une relation Producteur Consommateur le producteur passe au consommateur le message contenant l adresse du tampon o se trouve l objet consommer Chapitre 9 Evaluation de performance des syst mes 9 1 Introduction Comme on le verra tout au long des chapitres qui vont suivre l tude d un syst me informatique pr sente un grand nombre de choix possibles dans la r alisation certaines de ses parties cela vient s ajouter la prise en compte du type d application qui sera trait par le syst me selon le site o il sera implant On peut ainsi d sirer obtenir des r ponses des questions du style Le taux d utilisation de l UC sur le site S4 sera t il sup rieur celui du site S2 Le temps de r ponse serait il modifi si l on augmentait la m moire de 32 m ga octets La taille totale de la m moire physique pagin e demeurant la m me quel est le couple taille de page nombre de pages optimum Quel est le nombre moyen de programmes en attente Nous allons voir dans un premier temps l ensemble des possibilit s d v
26. les indicateurs pour conna tre la cause 2 3 Les interruptions mat rielles Les interruptions mat rielles se pr sentent comme un ensemble de fils num rot s reliant la CPU et les circuits externes de la machine La pr sence d un signal sur un de ces fils provoque une interruption du programme en cours d ex cution Le num ro de cette interruption est directement li au fil qui l a d clench e 14 En r sum un circuit ext rieur g n re une interruption sur la CPU afin de lui signaler un v nement Cette interruption stoppe le programme en cours pour lancer une routine du S E L ex cution de cette routine permet dans les meilleurs d lais la prise en compte par le S E de l v nement ext rieur 2 3 1 Syst me hi rarchis d interruptions Les fils d interruptions peuvent tre hi rarchis s c est dire class s par ordre de priorit s respec tives Un traitant d interruption peut donc tre lui m me interrompu par une demande d interruption intervenant sur un fil de priorit sup rieure Il passe alors l tat d attente La figure repr sente l activit des programmes dans le temps pour un syst me hi rarchis 8 niveaux o le niveau 0 est le plus prioritaire le niveau 7 correspondant au programme d arri re plan int int int int int niv 5 niv 4 nivi niv3 niv 0 N A a BB NN prise en compte de l int niv 3 F1G 2 2 Effet de la hi
27. m thodes analytiques limitent beaucoup plus les mod les envisageables Si l on choisit la dis cipline premier arriv premier servi il ne faut utiliser que des lois exponentielles et les diff rentes 81 classes de clients programmes doivent avoir la m me moyenne de temps de service aux guichets d une station organes de la machine Dans le cas de disciplines moins usit es infinit de serveurs service temps partag ou discipline dernier arriv premier servi avec priorit absolue on peut choisir pour chaque classe de clients une loi g n rale de service Avec la puissance des machines de traitement on fait galement de plus en plus appel aux m thodes num riques dans lesquelles toutes les transitions possibles sont d crites r solution de la matrice des transitions Dans ce cadre les r seaux de P tri prennent une importance de plus en plus grande cause de la mani re simple d obtenir l ensemble des transitions 9 4 Conclusion L volution depuis le d but des ann es 80 consiste produire des progiciels int grant les prin cipales m thodes de r solution analytique un simulateur et un programme qui suivant le mod le propos adopte le bon mode de r solution Ils comportent d autre part un langage de description du mod le De plus une interaction avec l utilisateur permet de le conseiller de simplifier telle ou telle partie afin de pouvoir utiliser un m thode analytique la place d une simulat
28. nouvelles fonctions li es la bonne gestion de la machine physique Structuration de l information sous forme de fichiers en vue de sa conservation et de sa modification Transfert des donn es entre les l ments constituants du syst me informatique unit cen trale p riph riques d impression ou de lecture modem etc Gestion de l ensemble des ressources pour offrir tout utilisateur un environnement n cessaire l ex cution d un travail Gestion du partage des ressources Le syst me doit r partir les ressources dont il dis pose entre les divers usagers en respectant la r gle d quit et en emp chant la famine En particulier il doit r aliser un ordonnancement des travaux qui lui sont soumis et viter les interblocages Extension de la machine h te Le r le du syst me est ici de simuler une machine ayant des caract ristiques diff rentes de celles de la machine r elle sur laquelle il est implant Chaque utilisateur dispose alors d une machine virtuelle munie d un langage tendu permettant l ex cution et la mise au point des programmes au moyen d outils plus facilement utilisables que ceux dont est dot e la machine c bl e 1 1 2 Aspects externes La diversit des t ches remplir et des mat riels utilis s a pour cons quence une grande vari t des aspects externes des syst mes les syst mes destin s la conduite de processus industriels chimie industrie
29. ou de mani re externe Elles peuvent tre m rit es ou acquises Elles peuvent tre statiques ou dynamiques Elles peuvent tre allou es de fa on rationnelle ou arbitraire en particulier lorsque le syst me est contraint de faire une distinction entre plusieurs processus sans avoir les moyens d tre s r de faire le bon choix 5 2 6 1 Priorit s statiques et priorit s dynamiques Par d finition les priorit s statiques ne changeant pas elles sont d une mise en uvre facile et engendrent un faible co t d exploitation Toutefois elles sont insensibles aux changements survenus dans l environnement changements qui justement peuvent n cessiter un ajustement des priorit s A l inverse les priorit s dynamiques peuvent changer en fonction de la modification de l envi ronnement En particulier nous verrons que la priorit initiale peut tre r ajust e tr s rapidement afin d tre mieux adapt e au type du processus consid r Il est bien vident que la gestion des priorit s dynamiques est beaucoup plus complexe et engendre un co t beaucoup plus grand que celle des priorit s statiques En contre partie leur emploi permet d accro tre consid rablement le d bit et la souplesse du syst me 36 5 2 6 2 Priorit s acquises Un syst me doit offrir un service quitable et raisonnable ou plut t raisonnablement quitable la majorit des utilisateurs d un site Mais il doit aussi pouvoir accepter qu un usager b n f
30. plan mat riel le temps partag est bas sur les possibilit s suivantes les programmes sont tous en m moire le temps partag implique donc la multiprogrammation le mat riel doit permettre l interruption d un programme au bout de son quanta de temps pour passer la CPU autre programme les temps de commutation d un programme vers un autre doit tre aussi faible que possible car durant cette tape la CPU est utilis e par le S E au d triment des programmes utilisateurs Les syst mes r partis se d veloppent durant les ann es 80 Dans cette organisation les donn es mais aussi les programmes sont r parties sur plusieurs machines connect es par un r seau Les probl mes sont plus complexes puisqu ils couvrent la communication la synchronisation et la collaboration entre ces machines mais ceci est une autre histoire et un autre cours 1950 1960 1970 1980 pas de traitement multi i Gros logiciels par lots utilisateurs DTS ordinateurs r partis moniteurs temps compilateurs partag pas de temps multi Mini logiciels partag utilisateurs ordinateurs moniteurs compilateurs multi pas de compilateurs lens Les Micros compilateurs et it temps moniteurs partag FIG 1 5 volution des syst mes d exploitation SG94 1 4 Exemples de syst mes d exploitation 1 4 1 Ordinateur individuel Toute configuration de base d un ordinateur individuel comporte une unit centrale et u
31. qu celui du syst me de gestion de fichiers 1 4 2 Commande de proc d s industriels Imaginons que dans une usine de produits chimiques un produit C soit synth tis partir de deux produits et B Le r acteur peut tre sch matis comme suit Le calculateur charg de conduire le processus de fabrication doit assurer trois fonctions r gulation enregistrement et s curit vannes A I R acteur B capteurs signaux de mesure Ordinateur signaux de commande F1G 1 6 Conduite d un r acteur chimique R gulation Les divers param tres de fonctionnement temp rature concentration pression doivent tre maintenues dans des limites fix es pour la bonne marche de la fabrication Pour cela on doit agir sur les vannes A et B sur l alimentation de r sistances de chauffage d un agitateur etc Tous les param tres sont mesur s chaque instant par un ensemble de capteurs dispos s dans la cuve l ordinateur pr l ve ces mesures les interpr te et agit en cons quence sur les organes concern s selon un programme de r gulation Enregistrement Les mesures effectu es par les divers capteurs sont p riodiquement enre gistr es leur valeur est affich e sur un tableau de bord surveill par un responsable et stock e dans un fichier journal en vue d un traitement ult rieur statistiques d explo
32. qu apr s ach vement des programmes correspondants 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 ne 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 im primante longtemps Le principe lui m me est il acceptable 25 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 4 2 4 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
33. que cette ch ance soit respect e Par contre si ce n est pas le cas le service suppl mentaire pourra tre gratuit Ce type d ordonnancement est complexe pour plusieurs raisons le syst me doit respecter l ch ance sans que cela implique pour autant une s v re d gradation de performances pour les autres utilisateurs le syst me doit planifier parfaitement l utilisation des ressources toujours cause de cette ch ance fatidique Or cela est particuli rement difficile car de nouveaux travaux peuvent arriver et mettre des demandes impr visibles afin de limiter les ennuis du point pr c dent l utilisateur r clamant une ch ance doit fournir au lancement la liste exhaustive des ressources qu il utilisera ce qui n est pas vident certaines tant transparentes pour lui tampons d E S canaux etc si plusieurs travaux ch ance sont lanc s en m me temps l ordonnancement va devenir tellement complexe que des m thodes d optimisation tr s sophistiqu es vont tre n cessaires d o un co t d exploitation tr s lourd ce surcro t de temps CPU utilis par l ordonnanceur ajout aux faveurs accord es au x pro cessus ch ance va in vitablement p naliser les autres utilisateurs ce qui risque d engendrer des conflits de personnes Ce facteurs doit tre consid r avec une grande attention par les concepteurs des syst mes d exploitation 37 5 3 2 Premier arriv
34. rations d E S Le but de ce m canisme est de r cup rer le temps d attente pour ex cuter un autre processus sur la CPU 3 3 Repr sentation d un processus Un processus est caract ris dans le syst me par un identificateur ou num ro par exemple le PID pour Process IDentification dans le syst me UNIX un tat op rationnel par exemple un des cinq vus pr c demment 19 un contexte des informations comme les priorit s la date de d marrage la filiation des statistiques calcul es par le S E comme le temps d ex cution cumul le nombre d op rations d E S le nombre de d fauts de page etc Ces informations sont regroup es dans un bloc de contr le de processus ou PCB Process Control Block Le syst me maintient donc un PCB pour chaque processus reconnu Ce PCB est une mine d informations Il repr sente en fait la principale donn e manipul e par l allocateur de la CPU Lorsqu un processus quitte l tat actif son PCB est mis jour et la valeur des registres de la CPU y est sauvegard Pour que ce m me processus redevienne actif le S E recharge les registres de la CPU partir des valeurs sauvegard es dans le PCB il change l tat et finalement il red marre l ex cution du processus Nous verrons plus tard dans quelles conditions un processus peut perdre la CPU Hormis les processus le syst me maintient galement un certain nombre de files qui regroupent les blocs
35. ressources n cessaires r glement de conflits le maintien de la charge du syst me en dessous du seuil d croulement et de son int grit en particulier en cas d incidents impr visibles sont autant de t ches dont l ordonnanceur devra s acquitter avec in vitablement des r percussions sur les travaux soumis Le r le du niveau moyen est de d terminer l ensemble des processus pouvant obtenir le contr le Autrement dit il tient jour les param tres relatifs aux diff rents processus qui permettront de d gager ceux tant susceptibles de devenir actifs Le niveau le plus bas le plus proche du mat riel choisit parmi les processus pr ts en respectant les priorit s celui qui le processeur va tre allou C est le r partiteur qui est toujours r sident en m moire Il faut bien comprendre que le fait d allouer une ressource un processus favorise celui ci au moins de fa on temporaire Ainsi chaque rouage de l ordonnanceur a pour effet d appliquer une certaine politique envers les divers processus et par cons quent envers les utilisateurs Or c est justement cette politique qui sera appel e a tre ventuellement modifi e afin de satisfaire le plus grand nombre d usagers C est la raison pour laquelle ces diff rents points de choix devront tre s par s du c t purement logique de l ordonnanceur Sans donner plus de d tails sur la fa on d valuer la priorit d un processus ce sera l objet du paragr
36. rience montre que l on observe des propri t s communes au comportement de la majorit des programmes relativement ind pendantes de l algorithme de remplacement utilis Ce sont donc des caract ristiques intrins ques du compor tement Intervalle entre d fauts de page w Taille de la m moire F1G 7 4 Intervalle moyen entre d fauts de page en m moire restreinte Elles peuvent tre illustr es par deux courbes obtenues en ex cutant un programme avec diff rentes tailles de m moire principale L allure de ces courbes est repr sentative d un type de comportement fr quemment observ La figure repr sente l intervalle moyen entre deux d fauts de page successifs dit dur e de vie La figure repr sente le nombre total de d fauts de page observ s au cours de l ex cution d un programme Nombre de d fauts de page D Taille de la m moire F1G 7 5 Nombre total de d fauts de page en m moire restreinte On constate que lorsque la taille de m moire diminue ce nombre cro t d abord lentement Au dessous d une certaine taille la croissance devient exponentielle 64 7 5 Gestion d une m moire virtuelle pagin e 7 5 1 Param tres d une politique d allocation Les politiques d allocation d une m moire pagin e peuvent tre class es selon plusieurs crit res Nous supposons que le syst me est multi programm entre plusieurs processus dont chacun poss de sa propre m mo
37. rir un interblocage en permettant 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 4 2 1 Les embouteillages Un exemple que l on rencontre h las tr s fr quemment est caus par la b tise et l individualisme de certains automobilistes abordant un carrefour important une heure de pointe Chacun s r de sa sup riorit sur l autre ignore les contraintes consid r es surann es en la circonstance que sont feux ou priorit et accapare la ressource que constitue le carrefour pr f rant faire confiance son agressivit ou sa soi disant d brouillardise pour imposer sa propre notion de priorit Ce sont g n ralement ces m mes automobilistes qui seront pr ts tout pour faire respecter la loi lorsque d aventure celle ci va dans leur sens unique 24 4 2 2 Ressource unique La plupart des risques d interblocage dans un syst me sont dus aux ressources acc s unique La figure 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
38. travail du processus le moins prioritaire la priorit tant d termin e de fa on externe ou par le temps de r sidence en m moire Un processus ne peut recevoir de m moire que s il y a assez de pages physiques libres pour recevoir son ensemble de travail courant La r alisation de cet algorithme n cessite de pouvoir identifier l ensemble de travail Aussi en dehors de r alisations exp rimentales il n a t mis en uvre que de fa on approch e L estimation de l ensemble de travail peut se faire par le biais d un simple bit d utilisation qui est forc 1 lors de chaque r f rence une page Ce bit existe d j si on utilise un algorithme de remplacement de type FINUFO ou LRU P riodiquement le S E peut pour chaque page physique recopier ce bit l int rieur d un mot en le d calant et forcer 0 le bit d utilisation Pour chaque page physique nous avons donc une suite de bits qui donne un historique d utilisation de la page physique i d signe l intervalle de temps entre deux relev s du bit d utilisation t 0i t 1li t 2i t 3i t Ai t 5i 0 0 1 0 0 1 Cet historique peut facilement tre utilis pour construire l ensemble de travail Dans notre exemple cette page appartient W t T avec T gt 2i mais elle n appartient pas W t 7 avec T lt i 7 6 3 Algorithme fond sur la mesure du taux de d faut de page Une mani re indirecte de d tecter que le nombre de pages physiques al
39. travaux forte priorit ne vient pas perturber l ordre des travaux en attente La r alisation d un ordonnanceur r quisition est nous l avons d j dit tr s d licate En par ticulier le calcul des priorit s ne doit pas voir l aspect sophistiqu l emporter sur le c t signifiant Rester simple est le ma tre mot mais si cela n est pas possible il faut au moins insister pour demeurer effectif et pertinent dans les choix 5 2 4 Intervalle de temps et interruption d horloge Le syst me dispose d un moyen tr s simple pour retirer le contr le un processus Un simple d compteur d impulsions d horloge dont le calibrage peut tre modifi peut d clencher une in terruption prioritaire qui aura pour cons quence d appeler un traitant d interruption du syst me d exploitation Un processus utilisera donc le processeur jusqu ce qu il le lib re volontairement ou qu il y ait interruption d horloge ou tout autre type d interruption r clamant une intervention du syst me Le syst me reprenant le contr le pourra alors le passer qui bon lui semble L interruption d horloge aide garantir des temps de r ponse acceptables dans un syst me interactif vite au syst me de rester monopolis dans une boucle de programme et permet en outre de traiter des applications temps r els C est donc une technique simple efficace et polyvalente qui toutefois demande une attention particuli re pour le calibrage du d compteur 5
40. 1 zone 2 m moire A C programmes B Allocation de la m moire A 1 C 2 B 1 U C programme zone Canal PE a z chargement C 2 A 1 B 1 C 2 sauvegarde Chronogramme d activit FIG 6 4 Syst me partitions fixes En r alit le chronogramme peut tre plus complexe chaque programme pouvant lui m me ex cuter des entr es sorties Dans ce cas le processeur est galement affect un autre programme Les syst mes partitions fixes sont couramment utilis s sur des petites et moyennes installations o un petit nombre d usagers interactifs gt coexistent avec un travail de fond Il est alors possible de d finir au moment de la g n ration du syst me des tailles de partitions adapt es aux diff rentes classes de programmes Le temps de r ponse moyen des processus interactifs d pend du rapport des temps d ex cution aux temps de transferts lui m me fonction du degr de multiplexage des partitions 6 3 Syst me partitions variables Dans un syst me partitions variables le d coupage en partitions n est pas fix une fois pour toutes mais il est red fini chaque d but d ex cution d un processus En cons quence le chargement d un programme fixation des adresses ne peut tre fait qu au dernier moment lorsqu une place lui est attribu e L allocation de la m moire par partitions de tailles variables suppose l existe
41. 25 ns suivant la probabilit de r ussite et donc la taille de la m moire associative Finalement le temps d acc s moyen n a augment que de 25 mais la gestion de la m moire est beaucoup plus souple et les probl mes de fragmentation externe n existent plus 6 4 4 Partage et protection de l information L utilisation d informations partag es entre plusieurs m moires logiques soul ve trois probl mes la d signation comment adresser de mani re uniforme les informations partag es le partage physique comment assurer que les informations partag es existent en exemplaire unique la protection comment garantir le respect des r gles d acc s ventuellement s lectives aux informations partag es Dans un syst me pagin l unit l mentaire de partage est la page Pour tre partag s les informa tions doivent se trouver sur une ou plusieurs page logique partag e Cette page peut tre charg e dans une page physique quelconque les tables de pages des m moires logiques o figure cette page logique contiennent alors l entr e correspondante le m me num ro de page physique Dans l exemple pr sent par la figure les pages contenant le programme Pa et Pb sont partag es mais les pages de donn es D1 D7 ne le sont pas 55 M moire Table des Table des M moire l
42. Q fin si fin 75 Soient np le nombre de primitives P s ex cut es depuis l initialisation n le nombre de primitives V s ny le nombre de processus ayant franchi P depuis l initialisation et co la valeur initiale du s maphore Si les primitives P et V sont seules modifier la valeur de s c on a toujours S C Co Np No Les processus ayant franchi P sont ceux qui n ont pas t bloqu s ou qui ont t d bloqu s depuis On a donc toujours la relation ns min ny Co ne Si aucun processus n a encore effectu V n 0 Si np lt co la demande de ressource a t inf rieure aux disponibilit s donc tous les deman deurs sont pass s Ainsi nf ny Min n Co Si ny gt co les co premiers sont pass s les np co autres ont t bloqu s Donc co demandeurs sont pass s Donc nf co min n c Par cons quent si n 0 la relation est vraie Si maintenant n 0 par d finition les primitives P et V sont ins parables et toute ex cution de V correspond une ex cution de P par le m me processus ou par un autre La diff rence n n repr sente le nombre de processus engag s dans la section critique ou bloqu s sur le s maphore n est le nombre de processus ayant ex cut P puis V donc ns n nombre de processus encore dans la section critique Sur les np n processus demandeurs eo avaient le droit de passer Donc il en est pass min n Ny Co Pa
43. Support de cours syst me d exploitation J Gispert J Guizol J L Massat D partement d informatique Facult de Luminy 163 Avenue de Luminy Case 901 13288 Marseille cedex 9 23 f vrier 2012 Chapitre 1 Organisation d un syst me d exploitation 1 1 Fonctionnalit s d un syst me informatique En se limitant au seul point de vue d un utilisateur d un syst me informatique les fonctions devant tre assur es par celui ci peuvent tre r sum es de la fa on suivante Gestion et conservation de l information Le syst me informatique doit permettre tout utilisateur de cr er conserver retrouver ou d truire les objets sur lesquels celui ci d sire ef fectuer des op rations Pr paration mise au point et exploitation de programmes Logiciel d application Ve G A Outils amp Services Logiciel de base an Syst me d exploitation Machine physique D FIG 1 1 Structure logicielle d un syst me informatique La figure pr cise l organisation logicielle d un syst me informatique avec d une part le logiciel d application traitement de textes gestionnaire de bases de donn es compilateurs etc et d autres part le logiciel de base livr avec la machine 1 1 1 Fonctions d un syst me d exploitation Le syst me d exploitation est un des l ments clef d un syst me informatique Il reprend son compte les deux fonctions pr c dentes en y ajoutant des
44. a r alisation interne On peut alors d crire la structure d un syst me par un graphe dont les n uds repr sentent les machines et les arcs les relations de d pendance Dans la figure le sch ma a repr sente la structure r sultant de la m thode de concep tion descendante Celui ci peut tre g n ralis en b si l on autorise chaque machine utiliser les primitives de toute autre machine de niveau inf rieur Enfin si la seule contrainte est d avoir un graphe sans circuit on obtient le sch ma c o les machines sont class es par niveau d abstraction chacune d elles n utilisant que les machines de niveau inf rieur MO MO MO t 7 E M1 M1 M1 M2 ri pi 4 M2 M2 M3 M4 t t Se A M3 M3 M5 a b F1G 1 2 D composition hi rarchique En r alit la m thode de conception descendante est rarement utilisable l tat pur Plusieurs facteurs sont prendre en consid ration l exp rience du concepteur l existence de machines d j r alis es la difficult de fixer l avance les sp cifications d taill es des interfaces qui utilisent en fait le r sultat d exp rimentation sur des r alisations partielles En tout tat de cause l ind pendance introduite par l abstraction procure la structure hi rarchique par niveau plusieurs avantages Ind
45. a seulement que tout processus qui entre en section critique en sort au bout d un temps fini pas de blocage La solution doit v rifier certaines conditions Exclusion tout instant un processus au plus est en section critique Acc s si plusieurs processus sont bloqu s l entr e d une section critique libre l un d eux doit y entrer au bout d un temps fini 71 Ind pendance le blocage par cette section critique doit tre ind pendant des autres types de blocage donc si un processus est bloqu hors de la section critique il ne doit pas emp cher un autre processus d y entrer Uniformit aucun processus ne doit jouer de r le privil gi ils doivent tous utiliser les m mes m canismes La programmation de l exclusion passe par trois sections de code La premi re initialisation est ex cut e une seule fois par le S E ou par les processus qui d sirent se synchroniser Elle pr pare les variables d tat qui indique que la section critique est libre La seconde prologue effectue la demande d entr e en S C Si l entr e est impossible le processus est bloqu au niveau du prologue La derni re pilogue signale la fin de la S C ce qui permet d en autoriser l acc s un autre processus qui est en attente initialisation prologue section critique pilogue 8 2 3 La m thode des drapeaux Pour r aliser l exclusion mutuelle une premi re solution consiste bloquer
46. able des segments d un processus e Les segments sont des zones contigu s du moins pour l instant On retrouve donc les probl mes d allocation lib ration de zones et l apparition d une fragmentation externe ventuellement corrig e par des compactages de la m moire Dans le cas de la m moire segment e ces compactages im pliquent une remise jour des pointeurs origine gt des tables de segments 6 5 2 Pagination d une m moire segment e La pagination d une m moire segment e vise rendre plus souple l allocation de m moire aux segments en levant la restriction de contiguit pour le placement d un segment Une entr e de la table des segments contient outre les informations propres au segment taille protection type un pointeur vers la table des pages de ce segment Comme dans les techniques pr c dentes une m moire associative conserve les derni res r f rences adr segment e et pagin e seg npl dep adr physique y npp dep v rifier que i npl lt L R de base z OP gt L Y Table des pages Table des segments du segment seg F1G 6 15 Pagination d une m moire segment e Exemple Le syst me Multics utilise une allocation par pages pour sa m moire segment e En raison du nombre lev de segments les tables de pages
47. age la m me situation va nouveau appara tre tr s rapidement obligeant le syst me consacrer une grande partie de son temps effectuer des compactages successifs En conclusion une telle forme d allocation n est gu re adapt e un syst me interactif mais convient mieux lorsque le nombre de partitions allou es est faible et leur temps d allocation grand traitement par trains de travaux F 100 100 100 100 5 50 100 100 100 100 100 50 AA 100 Z 50 50 50 200 150 100 50 F1G 6 6 Diff rentes possibilit s de compactage de la m moire 50 6 4 M moire pagin e Une m moire pagin e est divis e en blocs de taille fixe ou pages logiques qui servent d unit s d allocation La m moire physique est elle m me divis e en blocs de m me taille appel pages phy siques Nous pr sentons successivement les m canismes de pagination d une m moire contigu pa gin e et d une m moire pagin e segment e 6 4 1 Pagination d une m moire contigu La figure repr sente le sch ma g n ral d une m moire contigu pagin e Le r le de la bo te marqu e Fonction de pagination est d tablir une correspondance entre les adresses de pages logiques et les adresses de pages physiques de mani re se qu une page logique puisse tre rang e dans une page physique quelconque Les pages physiques deviennent ainsi des ressources banalis es don
48. aible importance seul leur ordre d arriv e tant pris en compte SJF favorise donc les travaux brefs au d triment des plus importants De ce fait il entra ne une variance beaucoup plus grande que FIFO en particulier pour ce qui concerne les travaux longs SJF 38 fonctionne de fa on ce que la prochaine ex cution puisse s achever et donc quitter le syst me d s que possible Cette technique tend donc r duire le nombre de travaux en attente ce qui a pour cons quence de diminuer la moyenne des temps d attente des processus Le principal inconv nient de SJF est qu il requiert une connaissance pr cise du temps d ex cution valeur qu il n est habituellement pas possible de d terminer Le seul moyen est de se fier une esti mation donn e par les utilisateurs eux m mes Cette estimation peut tre bonne dans des environ nements de production o les m mes travaux sont soumis r guli rement mais elle s av re rarement possible dans les environnements de d veloppement La connaissance de ce sch ma d ordonnancement pourrait tenter certains de sous estimer vo lontairement le temps d ex cution afin de profiter d une priorit indue Afin d viter ce genre de malhonn tet l utilisateur est pr venu l avance que son travail sera abandonn en cas de d passement Cela pr sente deux inconv nients obligation pour les usagers de majorer les estimations mauvaise rentabilit du processeur le temps consac
49. ais aussi un chan gement de mode y a donc un passage automatique du programme utilisateur en mode esclave au S E en mode ma tre l existe un et un seul point d entr e vers le S E pour les processus utilisateur Il est donc plus facile du point de vue du concepteur du syst me de s curiser l appel des primitives syst me Si on part du principe que le vecteur d interruptions se trouve dans une zone inaccessible au programme utilisateur alors ce dernier n a aucun moyen de passer en mode ma tre et l instruction SVC est le seul point de passage G n ralement un appel syst me a la structure ci dessous Heureusement les librairies standards dis ponibles dans tous les syst mes de d veloppement offrent une interface plus agr able et se chargent de programmer en assembleur l appel du syst me Le choix entre les diverses routines se fait non pas par adressage comme c est le cas pour un sous programme mais au moyen d un param tre suppl mentaire pass soit dans un registre soit dans la partie op rande de l instruction SVC pr parer les arguments de la requ te pr parer le type de la requ te SVC analyser le compte rendu du S E 16 En fait vu du programme utilisateur et mise part la forme de l instruction d appel elle m me SVC supervisor call gt tout semble se passer comme un appel de proc dure empilement de l adresse de retour des param tres mais en fait comme nous venons de le voi
50. aluation 9 2 Les m thodes d valuation Sur un syst me d j en ordre de marche on va pouvoir l valuer gr ce des moniteurs mat riels et logiciels Les premiers comportent un ensemble de sondes une unit de traitement et des unit s de stockage pour m moriser les mesures Les sondes sont piqu es en divers points de la machine tudier afin de pouvoir capter les diff rents signaux qui transitent Le processeur peut s lectionner les mesures et ventuellement op rer un pr traitement en temps r el mais le traitement global est le plus souvent effectu hors ligne lorsque la campagne de mesures est termin e Les difficult s de cette m thode sont entre autres la tr s grande quantit de mesures traiter et interpr ter l pose des sondes aux endroits choisis ne se fait pas sans risque de court circuit d autant plus que l int gration grandissante des l ments ne facilite pas la t che Le mat riel de test est tr s on reux et d une utilisation tr s d licate seuls les grands construc teurs quelques grands utilisateurs ou des soci t s sp cialis es disposent de moniteurs mat riels Par contre les r sultats des mesures ne sont pas perturb s et de ce fait tr s fiables Les moniteurs logiciels effectuent eux aussi des mesures mais gr ce un espion logiciel situ dans le moniteur du syst me valuer Chaque fois que se produit un v nement significatif l espion proc
51. aphe suivant le programme simplifi de l ordonnanceur pourrait s crire 31 32 pour toujours p prioritaire tant que tat p pr t faire p suivant p fin faire restaurer contexte p relancer p fin pour Dans ce programme on a suppos la liste ordonn e par priorit d croissante partir de l entr e prioritaire et de plus boucl e 5 2 Les strat gies d ordonnancement de la CPU 5 2 1 Les objectifs Une politique d ordonnancement doit 1 10 tre quitable cette contrainte est satisfaite si tous les processus sont consid r s de la m me mani re et qu aucun n est retard ind finiment rendre le d bit maximum elle doit faire en sorte de satisfaire le plus grand nombre de demandes par unit de temps pouvoir prendre en charge un maximum d utilisateurs interactifs tout en assurant des temps de r ponse acceptables tre pr dictible un m me processus doit pouvoir s ex cuter dans un temps peu pr s quivalent quelle que soit la charge du syst me tre la moins co teuse possible afin de ne pas prouver les performances g n rales du syst me en particulier dans les phases instables avoir pour effet de rationaliser la gestion des ressources en recherchant une utilisation optimum favorisant les t ches peu exigeantes en nombre et en qualit de ressources vitant la famine par exemple en augmentant la priorit au
52. arger un objet en m moire principale lorsqu on en a besoin chargement la demande avant d en avoir besoin pr chargement O charger cet objet S il y a assez de place libre dans quels emplacements le charger placement sinon quel s objet s renvoyer en m moire secondaire afin de lib rer de la place en m moire principale remplacement Plusieurs crit res seront utilis s pour imaginer valuer et comparer les algorithmes d allocation de m moire Crit res li s l utilisation de la ressource m moire mesur e par exemple par le taux de place perdue ou inutilisable Crit res li s l acc s l information comme le temps moyen d acc s ou le taux de d fauts de page Crit res plus globaux caract risant des performances induites par l allocation de la m moire taux d utilisation de la CPU temps de r ponse d un syst me interactif etc 45 6 2 Partage de la m moire sans r implantation 6 2 1 Syst me partition unique va et vient simple Dans les syst mes partition unique aussi appel va et vient simple ou swapping une zone fixe de m moire est r serv e aux processus des usagers voir figure Les programmes sont conserv s sur disque sous forme absolue Pour tre ex cut un programme est d abord amen en m moire principale dans sa totalit L allocation de processeur aux programmes d termine donc les transferts En cas de r qui
53. cas dans les sections suivantes Finalement le S E doit galement viter la congestion c est dire la demande excessive de ressources En d autres termes le S E 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 designers 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 22 23 4 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 les ressources sont utilis es en exclusion mutuelle c est dire par un seul processus la fois voir le chapitre sur la synchronisation de processus chaque processus utilise simultan ment plusieurs ressources qu il acquiert au fur et mesure de ses besoins sans n cessairement lib re
54. 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 ressource 1 La ressource 1 Le processus B est d tenue par r clame la le processus ressource 1 processus processus A B Le processus La ressource 2 r clame la est d tenue par ressource 2 le processus B ressource 2 FIG 4 1 Interblocage simple 4 2 3 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 pro gramme la lenteur de certains p riph riques tels que 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
55. crit res valables quel que soit l algorithme et qui sont appliqu s en priorit 1 Pages virtuelles propres ou sales Toutes choses gales par ailleurs il est toujours moins co teux de remplacer une page virtuelle qui n a pas t modifi e depuis son chargement page propre plut t qu une page modifi e page sa e Une page propre poss de une copie conforme en m moire secondaire et ne doit donc pas tre sauvegard e L indicateur modif entretenu automatiquement permet d appliquer ce crit re 2 Pages virtuelles partag es Une page virtuelle utilis e par un seul processus doit tre remplac e de pr f rence une page partag e entre plusieurs processus 3 Pages virtuelles statut sp cial Dans certains cas on souhaite donner temporairement une page virtuelle un statut sp cial qui la prot ge contre le remplacement Ce cas se pr sente surtout pour des pages utilis es comme tampons d entr e sortie pendant la dur e d un transfert 7 5 2 Algorithmes de remplacement Nous pr sentons d abord deux algorithmes qui servent de r f rence l algorithme optimal qui sup pose une connaissance compl te du comportement futur du programme et un algorithme neutre qui n utilise aucune information Algorithme optimal OPT Pour une cha ne de r f rences donn e on peut montrer que l algorithme suivant minimise le nombre total de d fauts de pages lors d un d faut de page choisir comme
56. curit le caract re syst matique de d routement en cas d erreur est sup rieur au test de code qui peut tre omis provoquant ainsi une propagation d erreur Clart le fait de pouvoir associer une proc dure particuli re chaque cause d erreur per met de s parer clairement le traitement des situations normales de celui des situations exceptionnelles Les m thodes de conception que nous venons de pr senter et les concepts ou outils d abstraction qui leur sont associ s permettent on l a vu gr ce la modularit ainsi acquise de diviser et subdiviser un syst me informatique en plusieurs parties ind pendamment modifiables ou m me interchangeables Cet aspect s av re primordial car les syst mes labor s l heure actuelle sont de plus en plus importants et de plus en plus complexes Si bien que leur r alisation est confi e plusieurs personnes divers services voire plusieurs quipes La coh rence du tout ne peut tre facilement obtenue qu la condition d avoir pr alablement clairement d fini les sp cifications d interface et l arborescence des classes d objets manipul s mais seulement cela D autre part certaines portions du syst me peuvent tre con ues de diff rentes fa ons en utilisant diff rentes strat gies Dans ces conditions les concepteurs devront tester celles ci sur des crit res de rapidit d optimisation d occupation d utilisation de ressources etc Le respect de
57. de un d routement pour prendre le compte et m moriser les valeurs correspondantes L 19 80 encore l utilisation de ces moniteurs logiciels est r serv e des sp cialistes capables de mettre en place l espion criture dans le moniteur d interpr ter les mesures et surtout le plus d licat d appr cier la d formation des r sultats due l utilisation de la machine par l espion lui m me En particulier il s av re tr s difficile de d duire des valeurs maxima d utilisation puisque l espion requiert lui m me de plus en plus de temps Les deux m thodes que l on vient de pr senter permettent une valuation du syst me dans des conditions de charge pr cises Il est donc tr s difficile d extrapoler sur ce que deviendraient les performances si on augmentait la capacit m moire si on ajoutait une entr e sortie Une autre fa on d valuer les performances d une machine consiste la comparer une ou plusieurs autres Dans ce cadre les benchmarks trouvent leur utilit En g n ral les compa raisons m diatiques entre diff rentes machines sont faites partir de ces pseudo caract ristiques Mais il faut savoir que ces benchmarks sont con us par les constructeurs et de ce fait peuvent tre particuli rement bien adapt s leur mat riel et l oppos tr s peu celui des concurrents Tou tefois pour des utilisateurs ayant des besoins pr cis la consultation de ces tests peut favorablement inf
58. de manipuler ces objets et des r gles de composition de ces actions En particulier tout langage d finit une machine capable de l interpr ter les instructions de cette machine repr sentent l ensemble des primitives du langage sa m moire permet de repr senter les objets et son m canisme d ex cution est celui d fini par les r gles d interpr tation du langage D sirant r soudre un probl me une d marche habituelle consiste d composer celui ci en une succession de plusieurs sous probl mes que l on esp re r soudre plus ais ment On essaie donc dans un premier temps de d finir une machine M dont les primitives rendront la r solution du probl me plus facile Le probl me initial suppos r solu par la machine Mo se transforme donc en la r alisation de cette machine M sur la machine disponible M On va alors d finir pour cela une machine M etc jusqu l obtention d une machine M facilement r alisable sur M La puissance de cette m thode ne r side pas dans la seule simplification du probl me chaque niveau mais r sulte aussi du processus d abstraction consistant focaliser l tude sur les aspects essentiels du probl me concr tis s par la sp cification d une machine c est dire en fait celle de son interface Lorsque la r alisation d une machine M utilise l interface d une machine Mj on dit que M d pend de M En fait cette relation de d pendance ne porte que sur l interface et non sur l
59. des segments et les tables de segments 58 elles m mes peuvent d passer la taille d une page et tre elles m mes pagin es La table des pages d un segment est maintenue en m moire principale tant que ce segment est actif c est dire que le fichier correspondant est ouvert pour au moins un processus 6 5 3 Partage de segments Dans une m moire logique segment e le partage s applique aux segments et les tables de pages des segments partag s sont elles m mes partag es dans le cas d un syst me segment pagin Tous les descripteurs d un segment contiennent alors non pas l adresse de ce segment mais celle de sa table de pages qui est unique Si l unit de partage est le segment la protection s lective s applique globalement au segment Les droits d acc s un segment pour un processus figurent dans la table des segments de ce processus Si des droits d acc s individuels aux pages du segment sont sp cifi s ils figurent dans la table de pages partag e par les processus utilisateurs et sont donc les m mes pour tous Ils doivent alors tre compatibles avec les droits globaux associ s au segment taille prot origine ES 0 data 1 1 WW table des segments de P1 code taille prot origine NS 0 gt data 2 1 table des segments de P2 NAS F1G 6 16 Partage de segments dans un syst me segment Chapitre 7 M moir
60. des zones ou des registres propres au S E Dans la pratique la CPU distingue les instructions normales et les instructions privil gi es Ces derni res ne sont utilisables qu en mode ma tre Elles permettent en g n ral la modification des registres sp cialis s et le dialogue avec les unit s d E S Partons du principe que le S E s ex cute en mode ma tre et que les programmes utilisateur s ex cutent en mode esclave La programmation directe des E S est donc r serv e au S E et les E S des programmes utilisateurs devront passer par des requ tes au S E Nous d velopperons ce point la section Une ex cution est une volution discr te de l tat de la machine Cet tat est donn par le contenu de la m moire et la valeur des registres de la CPU Nous sommes donc capables d observer l volution d une machine mais seulement sur certains points que nous appellerons les points obser vables ou points interruptibles Ces points sont situ s dans le temps la fin de l ex cution d une instruction de la CPU Le sch ma d crit sommairement l volution des registres d une C P U simplifi e lors de l ex cution d un programme 11 12 Evolution des registres de la C P U CO R1 R2 Code en cours d ex cution 123 E 34 bas LOAD R1 10 123 LOAD R1 125 10 34 g 124 10 E INC R1 D 125 INC R1 ka 126 ADD R1 R2 126 11 34 Sy ADD R1 R2 127 45 34
61. e choisie parmi plusieurs combinaisons h p d 8 4 12 8 5 Il 4 8 12 8 9 11 On peut donc choisir entre deux tailles de pages 2 ou 4 Ko deux tailles d hyperpages 64 ou 1024 Ko Notons que la m moire virtuelle reste contigue le dernier emplacement de l hyperpage h a pour successeur le premier emplacement de l hyperpage h 1 C est donc par abus de langage que cette technique est souvent appel e segmentation Ce d coupage de la m moire virtuelle peut n anmoins tre utilis pour simuler une m moire segment e 7 3 M canisme du d faut de page Outre la traduction proprement dite des adresses correspondance npv npp le m canisme d acc s une m moire pagin e doit r aliser les op rations suivantes mise jour du bit d criture et du bit d utilisation si ils existent d tection du d faut de page desc npv pr sent 0 qui provoque un d routement Le programme du traitement de d routement pour d faut de page doit 1 trouver en m moire secondaire la page virtuelle manquante 2 trouver une page physique libre en m moire principale s il n y a pas de page physique libre il faut en lib rer une en choisissant une page virtuelle enlever de la m moire c est la victime du d faut de page sauvegardant la victime si n cessaire dans la zone de pagination 3 provoquer le chargement de la page virtuelle dans la page physique ainsi rendue libre L tape 1 n cessite d avoir p
62. e communication gestion de l information partag e fichiers et des communications Les qualit s attendues sont disponibilit fiabilit s curit bonne exploitation des performances du mat riel qualit de l interface et des services offerts l usager facilit d extension et d adaptation Chapitre 2 Interruptions d routements et appels syst me 2 1 Ex cution de programme Avant de pr ciser ce que nous entendons par interruption il est souhaitable de d finir rapidement la notion d ex cution d un programme sur une machine En fait notre objectif est de pr senter un mod le g n ral valable sur la plupart des machines Une machine est compos e sch matiquement d un processeur aussi appel e la C P U d une m moire principale et d organes d E S Le processeur est un circuit actif qui comporte des registres g n raux et des registres sp cialis s L ensemble des registres sp cialis s forment le mot d tat du processeur M E P ou P S W pour Processor Status Word Parmi ces registres on trouve le compteur ordinal CO qui contient l adresse de la prochaine instruction ex cuter le mode d ex cution MODE qui peut tre ma tre ou esclave Le masque d interruptions que nous d taillerons plus tard Un ou plusieurs pointeur s de pile etc La notion de mode a t introduite essentiellement pour des raisons de protection afin qu un programme quelconque ne puisse acc der
63. e la section critique il donne syst matiquement la priorit l autre Solution programm e pour le processus algorithme de Peterson on se donne les variables suivantes var tour entier demande tableau O 1 de bool en Les trois sections de code permettant de programmer l exclusion mutuelle pour le processus avec 0 lt i lt 1 s crivent de la mani re suivante init tour 0 demande faux faux prologue demandeli vrai tour 1 1 r p ter jusqu tour i ou demande 1 i faux pilogue demandeli faux Cet algorithme sera tudi plus pr cis ment en travaux dirig s 8 2 5 Dispositifs de synchronisation c bl s Pour r gler ces probl mes et pour gagner en efficacit de nouvelles instructions ont t ajout es au processeur de mani re faciliter l criture de programme qui s ex cutent en exclusion mutuelle Nous allons d tailler maintenant l instruction TAS Test And Set qui est d finie de la mani re suivante 73 instruction TAS m verrou d but bloquer la case m moire mem verrou mem m meml verrou mem verrou 0 d bloquer la case m moire mem verroul CO CO taille de l instruction TAS fin Cette instruction permet de sauvegarder dans la case m moire m et de modifier le contenu de la case verrou en une seule op ration de la C P U Dans un syst me mono processeur l interruption d horloge ne pose plus
64. e virtuelle pagin e Le principe de localit nous dit que sur un petit intervalle de temps un processus utilise 20 de ses pages logiques On peut donc en conclure que 80 de pages logiques sont en m moire sans raison valable Il est donc raisonnable d enlever ces pages inutiles de mani re offrir plus de place m moire pour d autres processus et ainsi augmenter le degr de multi programmation 7 1 Pagination simple d une m moire virtuelle La figure repr sente le sch ma g n ral d une m moire virtuelle pagin e La m moire virtuelle est plus importante que la m moire physique et les pages virtuelles qui ne se trouvent pas en m moire physique sont stock es en m moire secondaire Nous avons maintenant 2 la taille des pages virtuelles ou physiques 2 le nombre de pages virtuelles taille de la m moire virtuelle et 2 le nombre de pages physiques taille de la m moire physique avec p gt c Une adresse virtuelle est donc un couple npv dep avec npv gt un num ro de page virtuelle sur p bits et dep gt un d placement sur l bits De m me une adresse physique est un couple npp dep avec npp un num ro de page physique sur c bits et dep un d placement sur l bits La fonction de pagination figure a maintenant la charge de transformer les adresses virtuelles en adresse physique et de d tecter les d fauts de page c est dire les acc s des pages virtuelles qui ne sont stock
65. emp ch leur extension des m moires de plus grande taille i entre 16 et 512 100 100 500 500 Ep y L chec F1G 6 10 Sch ma d une m moire associative Dans cette m moire associative on conserve les couples np1 npp relev s lors des acc s les plus r cents En raison de la propri t de localit des programmes on a une probabilit lev e 80 95 avec les tailles usuelles de trouver dans la m moire associative le num ro de la page logique adress e et donc de d terminer sa page physique Ce n est qu en cas d chec que l on passe par la table des 54 pages la m moire associative est alors mise jour le couple npl npp courant rempla ant le plus anciennement utilis figure adr logique ni npl dep RE ER m moire succ s associative T chec L_ v rifier que npl lt RL npp prot a Y Y npp npp dep z adr physique RB Y Table des pages desc F1G 6 11 Pagination avec m moire associative En partant du principe que l acc s la m moire physique prend 100 ns et que le temps de recherche de la m moire associative est de 20 ns le temps moyen d acc s est compris entre 0 8 x 100 20 0 2 x 100 20 100 140 ns 0 95 x 100 20 0 05 x 100 20 100 1
66. emption termin 5 attente 6 signal 5 i 3 actif FIG 3 1 Sch ma simplifi des transitions d tat d un processus Le processus est suspendu et se remet dans l tat pr t 4 Il y a r quisition ou pr emption de la CPU Dans ce cas le S E enl ve la CPU au processus qui la d tient Ce m canisme sera vu en d tail au chapitre traitant de l allocation de la CPU La notion d attente d un v nement m rite par son importance et sa complexit un petit exemple Un diteur de texte encha ne continuellement la boucle suivante r p ter lire un caract re traiter ce caract re jusqu Lorsque le processus diteur est actif il adresse une requ te au S E pour lui demander une op ration d E S la lecture d un caract re Deux cas se pr sentent si il existe un caract re dans le tampon d entr e ce dernier est renvoy par le S E si le tampon d entr e est vide le S E va endormir le processus en changeant son tat Lorsque l utilisateur frappe une touche du clavier le S E qui avait pr alablement sauvegard la demande de l diteur r veille gt l diteur qui pourra ainsi devenir actif et traiter ce fameux caract re Plus g n ralement toutes les op rations lentes en comparaison de la vitesse de la CPU provoquent un arr t momentan du processus demandeur et une reprise ult rieure lorsque l op ration est termin e C est notamment le cas pour les op
67. ent 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 petit cercle dans le grand cercle correspondant au type en question R1 P1 r clame a P1 une ressource de type R1 R2 Une ressource b P1 de type R2 a t allou e P1 FIG 4 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 4 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 montre les diverses tapes de r duction d un graphe permettant d abouti
68. er Il utilise plusieurs types de repr sentation r seaux de P tri stochastiques ou non r seaux de files d attente combinaison des deux Aucune th orie concernant le passage du syst me au mod le n existe seule l exp rience permet d aboutir un bon mod le En particulier la simplification n cessaire pour obtenir un mod le simple risque d impliquer des carts importants avec la r alit et ceux ci ne pourront tre chiffr s qu approximativement avec l habitude En fait les mod les sont g n ralement con us de fa on ce qu un cart de valeur de param tre ne change pas fondamentalement le r sultat Par exemple les valeurs optimales sont le plus souvent excellentes la variations des performances s op rant dans le bon sens sous valuation Si le mod le est trop complexe on a recours un simulateur crit soit dans un langage universel Fortran Pascal qui lui conf re la rapidit des calculs mais aussi des difficult s de mise au point soit dans un langage adapt Simula GPSS Un g n rateur de nombres al atoires est n cessaire afin d engendrer les diff rents tirages des lois de service ou d arriv e De plus ces g n rateurs doivent tre suffisamment longs afin d viter des cycles La simulation permet de d crire exactement le mod le choisi mais il faut tenir compte du fait qu l erreur de mod lisation dont nous avons d j parl vient s ajouter l erreur du simulateur Les
69. erche utiliser les temps morts d E S La r alisation pratique de cette id e n cessite des unit s mat rielles capables d effectuer des E S de mani re autonome lib rant ainsi la C P U pour d autres t ches des possibilit s mat rielles li es la protection de la m moire et ou la r implantation du code pour viter qu une erreur d un programme influence le d roulement d un autre C P U attente Unit d E S d but fin d but fin d E S d E S d E S d E S FIG 1 4 Cycles de CPU et cycles d E S Dans les ann es 60 70 les premiers syst mes en temps partag time sharing sont disponibles Ces syst mes sont directement li s l utilisation interactive des machines au moyen de terminaux vid o Ce mode d utilisation impose un temps de r ponse acceptable puisque les utilisateurs attendent devant leur terminaux Pour garantir un bon temps de r ponse moyen le temps d ex cution de la CPU est d coup en tranches appel es des quanta Ces quanta sont allou es aux programmes en cours d activit Le temps d ex cution de la CPU est donc partag entre les programmes utilisateurs Si le nombre d utilisateurs n est pas trop important et sachant qu un utilisateur moyen passe 90 de son temps r fl chir et seulement 10 ex cuter une action le temps de r ponse reste acceptable et chaque utilisateur l impression d avoir sa propre machine Sur un
70. es conditions d s que la demande d change se produit le processus demandeur est sorti de la file prioritaire et y reviendra lorsque cet change sera effectu b n ficiant ainsi entre chaque demande de la priorit accord e la file de plus haut niveau En ce qui concerne un travail tendant monopoliser la CPU il d butera comme tous les autres dans la file la plus prioritaire puis tr s vite il descendra les niveaux pour arriver dans la file la moins prioritaire son quantum expirant chaque tage L il restera jusqu ce qu il soit achev mais dans les hypoth ses actuelles que se passe t il si d aventure un processus de ce type demande un change Il est sorti de la file et lorsque l change aura t r alis il reviendra dans la file prioritaire moins que le syst me retienne la file dont il tait issu afin de l y replacer ensuite Ce faisant cette technique pr suppose que le comportement pass d un processus est une bonne indication de son comportement futur Mais alors un processus qui apr s une longue phase de calcul entre dans une phase o les changes pr dominent est d savantag Ceci peut encore tre r solu en associant au processus le dernier temps pass dans le r seau de files ou en convenant que tout 41 processus montera d un niveau dans le r seau chaque fois qu il aura volontairement lib r la CPU avant expiration du quantum Le tourniquet multi niveaux est un tr s bon exemp
71. es dans aucune page physique f zone de pagination M moire en m moire virtuelle secondaire M moire physique pagination Fonction de p D faut de page FIG 7 1 M moire virtuelle pagin e 59 60 Pour r aliser cette op ration la table des pages virtuelles comporte pour chaque page virtuelle les informations suivantes figure un num ro de page physique npp un indicateur de pr sence pr sent 1 bit un indicateur de modification modif 1 bit un mode d acc s autoris prot adr virtuelle npv dep m moire associative 7 7 Succes E chec R 8 2 Q g Q c i Y Y e 1 0 npp gt npp de p i z adr physique RB i Table des pages d faut de page virtuelles desc si pr sent 0 FIG 7 2 Transformation adresse virtuelle adresse physique Lors d un acc s la m moire la correspondance adresse virtuelle adresse physique est mise en uvre comme suit npv dep adresse virtuelle v rifier que npv lt RL v rifier les protections si desc npv pr sent 1 alors adresse physique desc npvl npp dep sinon d routement pour d faut de page fin si Lorsque la page virtuelle est pr sente le bit modif indique si la page virtuelle a t modifi e depuis s
72. es deux classements suivants classement par adresses croissantes ou d croissantes classement par tailles croissantes ou d croissantes 48 6 3 2 2 Algorithmes de s lection Une demande tant mise on conna t la taille requise pour charger le programme du processus demandeur Le plus souvent cette demande sera satisfaite gr ce une partition de taille sup rieure la diff rence ou r sidu est rattach e la liste des partitions libres pour autant que cette diff rence ne soit pas trop petite Deux possibilit s peuvent tre envisag es quant au choix de la partition libre pour satisfaire une demande prendre la premi re possible c est dire parcourir la liste jusqu ce que l on en trouve une dont la taille est sup rieur ou gale la demande lt x first fit prendre la partition la plus petite possible celle donnant le plus petit r sidu best fit L allocation d une partition un processus peut se d composer en deux phases recherche de la partition selon l algorithme choisi puis placement du r sidu dans la liste Le classement par tailles croissantes vite de parcourir toute la liste pour trouver la plus petite partition possible permettant ainsi une impl mentation ais e du best fit Par contre le placement du r sidu impose une modification du cha nage A l oppos le classement par adresses croissantes autorise une gestion rapide des r sidus seule la ta
73. es 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 plu part des programmes susceptibles d tre ex cut s sur le site Si d aventure un programme ne respecte pas cet ordre canonique les ressources doivent tre acquises ventuellement longtemps avant leur utilisation effective D o un gaspillage Les syst mes tendent de plus en plus aujourd hui respecter la contrainte de convivialit Le moins que l on puisse dire est que cette strat gie ne r pond pas cette attente 4 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 technique 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 On ne se l che pas des pieds sans se tenir des mains Partons du principe que le S E 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 disponibles dispoli nombre de ressources R disponibles sur le syst me max i j nombre maxim
74. essources mais engendre un co t d exploitation plus lev 4 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 demand es sont libres le blocage n appara t pas Mais si nous arrivons dans un sch ma montr dans la figure 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 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 4 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 divers
75. essus 6 4 2 Comportement des processus en m moire pagin e Le comportement d un processus dans son espace logique d termine ses demandes de m moire physique Il est donc utile de conna tre les caract ristiques de ce comportement pour am liorer l effi cacit des algorithmes de gestion dynamique de la m moire Donnons d abord quelques d finitions L coulement du temps est rep r par l ex cution des instructions successives l ex cution d une instruction d finit une unit de temps Ce temps est dit virtuel car il suppose que le programme dispose de toutes les ressources n cessaires m moire et processeur En cas de partage de ressources on peut ainsi raisonner sur un programme donn en faisant abstraction des autres La m moire logique pagin e est d coup e en page contigu s de taille fixe L acc s un em placement d une page est appel r f rence cette page Le num rotage des pages permet d tiqueter les r f rences Le comportement du processus est d fini par la s rie des num ros de pages r f renc es au cours de l ex cution Cette s quence s appelle cha ne de r f rence pour le processus consid r L ex cution d une instruction peut donner lieu plusieurs r f rences distinctes pages conte nant l instruction le ou les op randes L exp rience montre que les cha nes de r f rences des processus poss dent des caract ristiques communes que nous d finirons d abord de ma
76. i niveaux Nous avons vu les probl mes que posait dans SJF et SRT la difficult de conna tre l avance la quantit de temps CPU n cessaire l ex cution d un programme Un travail fonctionnant essen tiellement en entr e sortie n utilisera en fait la CPU que de courts instants A l oppos un travail r clamant le contr le en permanence monopolisera la CPU durant des heures si l on suppose un sch ma sans r quisition En fait nous l avons vu plus haut et un ordonnanceur doit favoriser les travaux courts favoriser les travaux effectuant de nombreuses E S pour une bonne utilisation des unit s externes d terminer le plus rapidement possible la nature de chaque travail afin de le traiter en cons quence Le tourniquet multi niveaux r pond ces attentes Un nouveau processus est stock en queue de la file de plus haut niveau Il progresse dans cette file FIFO jusqu ce qu il obtienne le contr le Si le processus s ach ve ou lib re la CPU pour une entr e sortie ou une attente d v nement il est sorti de la file d attente Si le quantum expire avant le processus est plac en queue de la file de niveau inf rieur Il deviendra nouveau actif lorsqu il parviendra en t te de cette file et condition que celles de niveau sup rieur soit vides Ainsi chaque fois que le processus puisera sa tranche 40 r quisition pr emption
77. icie d un traitement particulier Celui ci ayant par exemple un travail particuli rement urgent peut d sirer payer un suppl ment de service pour acqu rir une priorit plus forte afin que son programme soit ex cut plus rapidement Ce suppl ment se justifie sous deux aspect tout d abord ce n est que justice car vu sa priorit accrue les ressources qu il va utiliser en particulier le processeur seront enlev es d autres utilisateurs plus souvent que s il avait conserv sa priorit normale Il faudrait toutefois s assurer que le co t pour les autres usagers sera diminu en cons quence l autre aspect laisse supposer que les id es lib rales se sont infiltr es jusque l car en effet si on ne faisait pas payer tout le monde r clamerait un meilleur service ce qui est bien videmment inconcevable 5 3 Algorithmes d ordonnancement Nous allons en fonction des probl mes que nous venons d exposer et des solutions partielles qui ont t envisag es pr senter ici quelques r alisations d ordonnanceurs en montrant pour chacune d elles les avantages et les inconv nients envers le syst me et envers les utilisateurs 5 3 1 Ordonnancement par ch ance Certains travaux peuvent tre soumis accompagn s d une date d ch ance L encore cette option va entra ner un suppl ment d autant plus important que l ch ance est proche de l instant de lancement condition bien s r
78. ident que des probl mes de maintenance du mat riel ou tout simplement des pannes peuvent mettre en d faut ce postulat pr suppose aussi que chaque utilisateur annonce le maximum de ressources utilis es Or l heure actuelle la convivialit grandissante des syst mes fait que rares sont les utilisateurs connaissant pr cis ment les ressources dont ils ont besoin 28 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 4 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 4 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 montre les relations pouvant tre repr s
79. il Les organes de la machine Unit centrale M moire centrale P riph riques sont des ressources certaines entit s logiques aussi comme par exemple les fichiers Un processus est une suite d instructions r alisant une op ration que l on consid re comme l mentaire relativement son algorithme et l ensemble des ressources qu elle n cessite C est une structure s quentielle Il ne faut pas la confondre avec l appel de proc dure qui suspend l appelant et n augmente pas le degr de parall lisme Une application est un ensemble de processus coop rant et ou en comp tition pour l acquisition de ressources Un processus n cessite un processeur pour s ex cuter Pour plusieurs processus concurrents il faut plusieurs processeurs parall lisme vrai ou bien un seul qu ils se partageront dans le temps parall lisme simul 8 1 2 tat des processus Les ressources tant en nombre limit il n est pas possible de les attribuer globalement un processus au moment de sa cr ation On peut donc arriver la situation dans laquelle un processus ne poss de pas toutes les ressources n cessaires pour ex cuter l instruction suivante On dit que ce processus est bloqu C est le cas par exemple dans un syst me pagin lorsqu un programme requiert une page non pr sente en m moire centrale Dans le cas contraire il est dit actif Lorsque dans un syst me plusieurs processus coop rent la r alisation d un m me travail l
80. ille doit tre modifi e le cha nage demeurant inchang pour peu que le chargement s op re en bas de partition Cette technique est mieux adapt e l algorithme du first fit On peut constater que certaines tailles sont demand es plus fr quemment que les autres Dans ces conditions on am liore l efficacit de l allocation en r servant un certain nombre de partitions poss dant ces tailles privil gi es En cas d puisement de cette r serve le m canisme classique est utilis 6 3 2 3 Lib ration d une partition Trois cas sont consid rer lors de la lib ration d une partition la partition lib r e est entour e de deux partitions libres la partition lib r e est entour e d une partition libre et d une partition occup e la partition lib r e est entour e de deux partitions allou es Chaque fois que cela est possible deux premiers cas il est utile de regrouper les partitions libres contigu s afin de r duire la fragmentation de la m moire Il est vident que le classement par adresses croissantes est alors le plus efficace 6 3 3 Fragmentation et compactage Le ph nom ne le plus g nant dans le type d allocation tudi ici est celui de la fragmentation de la m moire qui appara t au bout d un certain temps de fonctionnement et qui est d la multiplication des r sidus de petite taille On peut aboutir une situation o aucune partition de taille suffisante n est disponible pour
81. important et de plus en plus difficile traiter trouvera n anmoins dans les technologies et les structures futures des solutions efficaces Chapitre 5 Allocation du processeur 5 1 Introduction Le partage d une machine entre plusieurs utilisateurs s est tr s rapidement r v l n cessaire pour des raisons d conomie de rentabilit et de convivialit Sous cette hypoth se le probl me qui se pose alors chaque instant pour chaque processeur est de d cider s il doit poursuivre ou interrompre l ex cution du processus courant et dans le second cas de d terminer le prochain processus activer La r gle utilis e pour effectuer ce choix est contenue dans l algorithme d ordonnancement plus couramment appel ordonnanceur scheduler Nous allons pr senter ici quelques param tres inter venant dans l laboration des divers algorithmes utilis s en les justifiant par l id e directrice qui a motiv leur emploi Il faut en fait consid rer l ordonnanceur sous trois aspects Au niveau le plus lev le plus proche de l utilisateur sa fonction consiste d terminer si un travail soumis doit tre admis tout travail admis devient un processus ou pas En d autres termes ce niveau a pour mission d allouer ou r quisitionner des machines virtuelles aux divers utilisateurs du syst me selon certaines r gles induites par la gestion sp cifique du site consid r Ainsi l valuation des priorit s la gestion des
82. ion A l heure actuelle l effort porte sur l interface homme machine pour la description du mod le En particulier gr ce des interfaces graphiques on pourra dans quelques temps dessiner sur un cran tactile le cheminement des clients et les caract ristiques des serveurs Il ne faut cependant pas croire que ces logiciels vont permettre une d mocratisation compl te des outils d valuation En effet malgr les aides apport es la mod lisation celle ci est constitu e d un ensemble d heuristiques plus ou moins heureuses et seul un sp cialiste pourra d gager les mieux adapt es et estimer les compromis provoqu s par le passage du syst me au mod le Un effort de recherche t entrepris dans cette partie de conception au moins aussi importante que la partie r solution Un syst me expert proposant des mod les pr enregistr s de diff rents sous ensembles classiques unit centrale p riph riques r seaux multiprocesseurs permet l utilisateur la mise en place du mod le le plus sophistiqu possible tout en restant pour la plupart des sous mod les dans le cadre de r solutions analytiques Beaucoup de travaux restent faire aussi bien dans la mod lisation que dans l interpr tation des r sultats De plus la recherche de nouvelles m thodes analytiques permettra la prise en compte de mod les de plus en plus pr cis sans pour autant augmenter les temps de conception et de calcul Bibliographie SG94 Pri
83. ions Dans tout ce qu on vient de voir le seul message transmis est l autorisation de continuer On consid re maintenant un probl me d change d information orient constitu de deux processus sp cialis s l un mettant des messages successifs son rythme propre l autre utilisant ces messages L utilisation peut tre lente pour certains messages rapide pour d autres aucune hypoth se n est faite sur les vitesses et l ensemble ne fonctionnera que si les deux processus sont correctement synchronis s 8 3 1 S maphore avec message Pour r soudre le probl me de la communication d informations on peut modifier les primitives P et V de telle sorte que V qui donne l autorisation de continuer transmette en m me temps un message que P re oit chaque ex cution de V un nouveau message est transmis qui doit tre plac dans une file d attente Celle ci n volue pas comme la file des processus qui est remplie par P On appelle donc fp la file des processus et fm la file des messages Les nouvelles primitives Pm et Vm aussi appel es send et receive sont 78 proc dure Pm var s s maphore avec message Var m message d but S C s c 1 si s c lt 0 alors entrer le processus appelant dans la file s fp suspendre le processus appelant sinon sortir m de la file s fm fin si fin proc dure Vm var s s maphore message m message d but s c s c 1 si s c lt 0 alors sortir un processus Q de
84. ire virtuelle Partition fixe ou variable Dans une politique partition fixe un nombre fixe de pages phy siques est attribu chacun des processus notons que ce nombre n est constant que pendant les p riodes o le nombre de processus multiprogramm s est lui m me constant Dans une politique partition variable le nombre de pages physiques attribu es chaque processus varie au cours du temps Les pages physiques tant banalis es c est leur nombre et non leur identit qui est le param tre significatif Pagination la demande une page virtuelle n est charg e en m moire qu la suite d une r f rence donnant lieu un d faut de page Pr chargement Lorsqu une page virtuelle est charg e l avance avant toute r f rence une information qu elle contient on dit qu il y a pr chargement Remplacement local ou global Il y a remplacement de page lorsqu une page virtuelle est charg e dans une page physique occup e c est dire contenant une page virtuelle charg e ant rieurement et susceptible d tre encore utilis e cette derni re page est souvent appel e la victime L algorithme de remplacement est dit ocal ou global selon que la victime est choisie parmi les pages virtuelles du processus qui provoque le chargement ou parmi l ensemble de toutes les pages virtuelles pr sentes en m moire Avant d tudier et de comparer les algorithmes de remplacement de pages il faut mentionner des
85. itation 10 S curit I y a arr t d urgence du r acteur si certaines valeurs pr lev es d passent certains seuils pr d finis Le mode de fonctionnement pr c demment d crit impose des contraintes au syst me Le temps n cessaire au traitement d un ensemble de mesures pr l vement enregistrement d termination et ex cution des commandes qui s imposent doit tre inf rieur la p riode de pr l vement la fonction de priorit doit tre prioritaire sur toutes les autres Le fait de fixer des limites la dur e d un traitement informatique l existence d ch ances la notion de traitement prioritaire et la connexion aux organes de commande et de mesure d un dispositif ext rieur sont caract ristiques des applications dites en temps r el Pour ces syst mes la qualit principale est la fiabilit Les cons quences d une d faillance pouvant tre catastrophiques centrale nucl aire le syst me doit tre en mesure d assurer chaque instant la s curit du processus qu il pilote et en particulier assurer un service minimal en cas de d faillance du mat riel d v nement accidentel s isme ou d erreur humaine 1 4 3 Syst mes transactionnels Ces syst mes sont caract ris s par les propri t s suivantes l ensemble des informations g r es peut atteindre une taille importante milliards d octets Sur ces informations peuvent tre ex cut es un certain nombre d op rations pr d
86. le de m canisme adaptatif Bien s r le co t d un tel ordonnanceur est sup rieur un qui n a pas ces facult s d adaptation mais la meilleure ad quation de l attitude du syst me vis vis des diff rents types de travaux justifie amplement cette d pense noter une variante de ce syst me consistant maintenir un processus plusieurs tours dans une m me file avant qu il passe au niveau inf rieur Habituellement ce nombre de tours s accro t comme la taille du quantum en descendant dans les niveaux Chapitre 6 Allocation de la m moire centrale 6 1 Concepts de base 6 1 1 M moire logique La notion de ressource logique conduit s parer les probl mes d utilisation d une ressource particuli re des probl mes d allocation de cette ressource Pour un processus la m moire logique est le support de l ensemble des informations potentiellement accessibles c est dire l ensemble des emplacements dont l adresse peut tre engendr e par le processeur lors de l ex cution de ce processus L allocation de m moire consiste concr tiser cette m moire logique par des supports physiques d information tels que m moire principale disques magn tiques etc En bout de cha ne l acc s d un processus une information se traduit par l acc s d un processeur physique un emplacement de m moire principale adressable par ce processeur L information accessible un processus est d finie par l ensemble des
87. le est constitu e d une suite d emplacements identiques mots organis s de mani re s quentielle et d sign s par des entiers cons cutifs appel s adresses logiques Un objet est une information occupant un mot ou plusieurs mots cons cutifs il est d sign par l adresse logique du premier mot Cette organisation est donc identique celle des emplacements d une m moire physique M moire logique non contigu ou segment e Elle est constitu e d un ensemble de segments Un segment est une suite de mots et regroupe g n ralement des informations de m me nature Il peut avoir une taille variable Les mots contenus dans un segment sont d sign s par des entiers cons cutifs appel s d placements L adresse logique d un mot est donc un couple num ro de segment d placement dans le segment appel adresse segment e Un objet qui peut occuper un segment entier ou une suite de mots cons cutifs dans un segment est d sign par l adresse segment e de son premier mot M moire physique non contigu Le placement des m moires logiques en m moire physique peut tre contigu ou pas Dans ce dernier cas les pages qui composent la m moire logique sont diss min es dans diff rentes pages physiques C est une organisation en m moire pagin e ou segment e et pagin e 6 1 2 Allocation de M moire On distingue diff rentes mani res de r aliser la mise en correspondance entre organisation de la m moire logique et implanta
88. les processus qui veulent entrer en S C dans le prologue si celle ci n est pas libre Pour programmer ce blocage on se donne une variable bool enne partag e et nous obtenons le code suivant initialisation libre vrai prologue 1 tant que libre faux faire 2 fin faire 3 libre faux pilogue libre vrai Partons du principe qu aucun processus n est en S C donc libre vrai et que deux processus not s p et p2 d sirent entrer en S C Il est possible que l ex cution du prologue se d roule ainsi lp 2p interruption lp 2p2 3p2 interruption 3p On voit bien que p n est pas eu le temps de modifier la valeur du drapeau ce qui provoque l entrer simultan e des deux processus en S C Ce m canisme est donc mis en d faut par l apparition des interruptions d horloge dans les syst mes en temps partag Pour corriger ce probl me on pourrait envisager de masquer les interruptions mais cette solution n est pas envisageable pour deux raisons D une part le blocage des interruptions n est possible qu en mode ma tre ce qui interdit son utilisation dans des processus utilisateur D autre part ce blocage ne r gle le probl me que sur les machines mono processeur En effet si plusieurs processeurs sont disponibles nous pouvons avoir la s quence suivante Ex cution de p sur la CPU 1 1 2 3 Ex cution de p gt sur la CPU 2 1 2 3 12 Les deux process
89. lgorithme choisit donc comme victime la page virtuelle ayant fait l objet de la r f rence la plus ancienne La r alisation de l algorithme impose d ordonner les pages physiques selon la date de derni re r f rence de la page virtuelle qu elles contiennent Pour cela une information doit tre associ e chaque page physique et mise jour chaque r f rence Cette information peut tre une date de r f rence une solution plus conomique mais encore ch re consiste utiliser un compteur incr ment de 1 chaque r f rence la page physique dont le compteur a la valeur la plus faible contient la victime Les compteurs ayant une capacit limit e il doivent tre remis z ro d s que l un d eux atteint sa capacit maximale la r alisation de LRU n est donc qu approch e En raison de son co t cette solution n a t utilis e que sur des installations exp rimentales Si la taille du compteur est r duite a 1 bit on obtient l algorithme suivant dont le co t est acceptable Algorithme de la seconde chance FINUFO ou First In Not Used First Out Cet algorithme est une approximation tr s grossi re de LRU A chaque page physique est associ un bit d utilisation not U mis 1 lors d une r f rence la page qu elle contient Les pages physiques sont ordonn es dans une liste circulaire et un pointeur victime d signe la derni re page physique charg e L algorithme s crit comme suit
90. lle cracking central t l phonique guidage de fus e surveillance m dicale ou monitoring etc les syst mes g rant les bases de donn es r servations de places gestion de stock gestion de comptes bancaires documentation automatique etc les syst mes destin s la cr ation et l ex cution de programmes qui peuvent tre subdivis s en plusieurs classes selon le degr d interaction entre l utilisateur et ses programmes traitement par trains ou conversationnel le mode de partage des ressources mono ou multiprogrammation les possibilit s offertes par le langage tendu acc s un ou plusieurs langages Malgr cette grande diversit les syst mes comportent entre eux des parties tr s ressemblantes voire identiques et il serait donc tr s utile de pouvoir d gager celles ci afin de profiter de certaines tudes partielles dans l laboration de portions plus complexes C est ce souci de rentabilisation qui a conduit une conception modulaire des syst mes et de leurs diff rents constituants technique g n ralisable tout logiciel d velopp sur une machine quelconque 1 2 Structure interne des syst mes d exploitation 1 2 1 Conception descendante et structures en couches Dans cette section le terme de langage sera utilis dans le sens suivant un langage d finit des objets et les m canismes permettant de les cr er des actions ou primitives permettant
91. lou es un processus donn est insuffisant consiste mesurer son taux de d faut de page L algorithme PFF est fond sur ce principe quand ce taux d passe un seuil sup rieur sp cifi pour chaque processus celui ci re oit une page physique suppl mentaire inversement une page physique lui est retir e si son taux de d faut de page tombe au dessous d un seuil inf rieur 7 6 4 Exemples Tous les syst mes multiprogramm s actuels comportent un m canisme d ajustement dynamique du degr de multiprogrammation qui utilise l une ou l autre des m thodes ci dessus VAX VMS est un syst me utilisant une estimation approch e de l ensemble de travail IBM VM 370 et Multics sont des syst mes utilisant une r gulation de charge globale Chapitre 8 Parall lisme et synchronisation Des processus peuvent se d rouler successivement sur un m me processeur ou bien en simul tan it r elle sur des processeurs distincts condition d assurer la communication des donn es et r sultats entre eux Le but de ce chapitre est l tude des processus des ressources qu ils utilisent et de leur mise en oeuvre sur diff rents types de machines Nous tudieront successivement le parall lisme simul sur machine traditionnelle puis le parall lisme r el des architectures nouvelles 8 1 Ex cution de processus 8 1 1 Quelques rappels et d finitions Une ressource est une entit pouvant servir l ex cution d un trava
92. luencer leur choix Autre m thode employ e la mod lisation permet d valuer un syst me par l interm diaire d un mod le le d crivant plus ou moins pr cis ment Ce mod le est r solu soit par des m thodes ana lytiques regroupant des techniques math matiques autour d un syst me de files d attente soit par des simulations Dans le premier cas si la solution est une formule math matique les calculs se ront simples et de nombreux cas de figure pourront tre tudi s optimisation par utilisation des d riv es Dans le cas de la simulation d un mod le r alis la finesse de description du mod le aura une incidence directe sur le rapport entre l unit de temps de la machine simul e et celle de la machine tudi e rapport pouvant varier de 0 01 100 Ne pouvant s appuyer sur des expressions math matiques comme dans le cas pr c dent l optimisation sera donc plus compliqu e cause de leur faible co t de leur facilit de mise en uvre et de la rapidit d obtention de r sultats les m thodes analytiques sont de plus en plus utilis es On s oriente pr sent vers l laboration de progiciels d valuation de performance rendant accessibles des non initi s les m thodes tr s sophistiqu es de la mod lisation 9 3 La mod lisation et les m thodes de r solution La mod lisation consiste passer d un syst me concret connu par ses sp cifications un mod le qui est une simplification du syst me valu
93. lusion mutuelle entre plusieurs processus on se donne un verrou mutex qui est accessible tous les processus et les trois sections de code deviennent init init mutez prologue verrouiller mutez pilogue d verrouiller muter Le verrou est une ressource critique qu il faut prot ger Les deux proc dures verrouiller et d verrouiller sont des sections critiques elles font partie du syst me et se comportent pour l utilisateur comme des instructions On les appelle donc primitives Pour r aliser leur exclusion mutuelle si la machine est monoprocesseur il suffit de masquer les interruptions si elle est multiprocesseur le masquage des interruptions est inop rant on utilise alors une instruction TAS L attente active ne dure que le temps d ex cution de la primitive 8 2 7 S maphores Un ensemble de tampons est une ressource critique plusieurs points d entr e On g n ralise les verrous en s maphores Un s maphore s est un couple c f constitu d une variable enti re s c et d une file d attente s f de processus Il est initialis par s n avec n gt 0 Les primitives sont proc dure P var s s maphore d but s c s c 1 si s c lt 0 alors entrer le processus appelant dans la file s f suspendre le processus appelant fin si fin proc dure V var s s maphore d but S C s C l si s c lt 0 alors sortir un processus Q de la file s f reprendre le processus
94. ment Le co t de SRT est sup rieur celui de SJF il doit tenir compte du temps d j allou aux processus en cours effectuer les commutations chaque arriv e d un travail court qui sera ex cut imm diatement avant de reprendre le processus interrompu moins qu un travail encore plus court ne survienne Les travaux longs subissent une attente moyenne plus longue et une variance plus grande que dans SJF En th orie SRT devrait offrir un temps d attente minimum mais du fait de son co t d exploitation propre il se peut que dans certaines situations SJF soit plus performant Afin de r duire ce co t on peut envisager plusieurs raffinements vitant la r quisition dans des cas limites supposons que le processus en cours soit presque achev et qu un travail avec un temps d ex cution estim tr s faible arrive Doit il y avoir r quisition On peut dans ces cas de figure garantir un processus en cours dont le temps d ex cution restant est inf rieur un seuil qu il soit achev quelles que soient les arriv es autre exemple le processus actif a un temps d ex cution restant l g rement sup rieur au temps estim d un travail arrivant lci encore si SRT est appliqu au pied de la lettre il 39 y a r quisition Mais si le co t de cette r quisition est sup rieur la diff rence entre les deux temps estim s cette d cision devient absurde La conclusion de tout cela est que les designer
95. n de la CPU aux processus 20 r quisition allocation n X de la CPU processus m file des processus pr ts f actifs fin de l E S file des processus en pe attente de fin d E S demande d E S appel de exit file des processus morts Dei F1G 3 2 D placements des processus dans les files du syst me etc Ces processus font partie du syst me d exploitation Ils s ex cutent donc avec des droits tendus Nous les appellerons les processus syst me ou d mons daemons par opposition aux processus utilisateur Le syst me d exploitation est donc compos d un noyau r sident qui ne s ex cute que sur demande explicite interruptions et d routements et d un ensemble de processus syst me qui ont chacun une fonction pr cise assurer Ce d coupage pr sente deux avantages 1 la partie r sidente du syst me est r duite en taille ce qui permet d viter une trop grande consommation de m moire par le syst me 2 les processus syst mes ne sont pas forc ment toujours pr ts ou m me toujours pr sents en m moire ce qui permet encore une fois de r duire la m moire et le temps CPU consomm par le S E au d triment des processus utilisateur Si le syst me est organis base de plusieurs processus des logiciels d application peuvent galement adopter cette structure Si c est le cas il est n cessaire et m me vital de fournir des outils permettant une comm
96. n importe quelle page physique De ce fait la gestion de la m moire physique revient simplement g rer une liste des pages physiques libres sans id e de regrou pement Les probl mes li s la fragmentation externe disparaissent mais la fragmentation interne se fait plus pr sente puisque la page devient l unit l mentaire d allocation et de lib ration en pratique plusieurs kilo octets L acc s une page logique n cessite maintenant deux r f rences la m moire en raison de la consultation de la table des pages Cette augmentation du temps d acc s moyen est bien sur intol rable La r duction de ce co t passe par deux points observer le comportement des processus vis vis de la m moire 52 M moire Table des Table des M moire logique du pages du pages physiques pages du logique du processus 1 processus 1 processus 2 processus 2 ceea A A D D Le B E F C F C G B E F1G 6 9 Un exemple sur deux m moires logiques pagin es optimiser la transformation des adresses au moyen d un circuit particulier les m moire asso ciatives Pour viter l acc s cette table et donc r duire le temps d acc s moyen on passe par un circuit particulier une m moire associative Mais avant de pr senter cette m moire il faut discuter de l utilisation de la m moire par les proc
97. n programme en cours d ex cution qui partage son code et ses donn es avec les autres threads d un m me processus Bien entendu les piles sont propres chaque thread pour viter que les appels de fonctions et les variables locales ne se m langent Cette solution pr sente plusieurs avantages si un processus ne comporte qu un seul thread nous revenons au mod le classique les syst mes multi threads sont donc plus g n raux il n y a plus mettre en place une communication entre les threads d un m me processus puisqu ils agissent tous sur les m mes donn es le temps de commutation entre les threads d un m me processus est r duit car le contexte est le m me et seuls les registres de la CPU doivent tre sauvegard s en associant un ou plusieurs thread s chaque processeur on peut facilement exploiter une structure multi processeurs Chapitre 4 Allocation de ressources et interblocage 4 1 Allocation de ressources 4 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 aflocateur qui a la charge de r pondre aux requ tes de demande de lib ration et ventuellement de r quisition Les ressources peuvent tre r quisitionnables CPU m moire o
98. n ter minal cran clavier et ventuellement souris En g n ral cet ensemble est augment d une m moire secondaire disque dur et d une imprimante L utilisateur potentiel attend de ce syst me principalement deux types de services cr er et nommer des fichiers pouvoir les conserver en m moire secondaire transf rer de l information entre les fichiers et les organes d entr es sorties clavier imprimante cran ex cuter des programmes qui peuvent tre livr s avec le syst me ou cr s et introduits sous forme de fichiers les donn es sont introduites au clavier ou lues dans des fichiers les r sultats sont affich s l cran list s sur l imprimante ou encore stock s dans des fichiers Ce genre de syst me tant utilis par un seul usager la notion de partage de ressources est absente L allocation des ressources intervient pour la gestion de la m moire et de l espace disque Pour ce type de syst me les qualit s essentielles requises sont la fiabilit l efficacit les performances de la machine support tant souvent limit es il importe de les utiliser au mieux la simplicit d utilisation Macintosh de Apple la facilit d extension par adjonction de nouveaux programmes utilitaires ou adaptation des nouveaux p riph riques Ces deux derniers aspects mettent en vidence l importance de la conception des interfaces tant au niveau du langage de commande
99. nce d un m canisme de r implantation dynamique L utilit de celui ci appara tra dans la d signation d objets appartenant des partitions qui auront du tre d plac es en m moire centrale 6 3 1 R implantation dynamique par registre de base Le principe que nous allons d crire est simple Disposant d un registre particulier ou registre de base son contenu est syst matiquement ajout toute adresse engendr e par un processus le r sultat constituant une adresse physique de l information d sign e Si les adresses d un programme 47 sont relatives son d but i e si le programme est implant l adresse logique 0 il suffit que le registre de base soit affect son adresse d implantation en m moire physique voir figure Dans ces conditions le programme pourra tre charg en n importe quel endroit de la m moire En particulier d placer globalement un programme dont l ex cution est commenc e peut s op rer tr s facilement condition de modifier en cons quence la valeur contenue dans le registre de base De plus si programme et donn es sont atteints par l interm diaire de registres distincts leur d placement pourra tre effectu ind pendamment RL RB 6 150 Re 0 A 150 A 1 B 151 B 2 C 152 C oui 3 D 3 Eo m 153 D 4 E 154 E 5 F non 155 F d routement sur erreur d adressage F1G 6 5 Passage logique physique
100. ncipes des syst mes d exploitation A Silberschatz amp P B Galvin Addison Wesley 1994 TE94 Syst mes d exploitation A Tanenbaum Prentice Hall InterEditions 1994 BB90 Syst mes d exploitation concepts et algorithmes J Beauquier amp B B rard Mc Graw Hill 1990 KR87 Principes des syst mes d exploitation des ordinateurs S Krakowiak Dunod Informatique 1987 BA89 Conception du syst me UNIX M J Bach Masson Prentice Hall 1989 82 Table des mati res 83
101. ni re qualitative Non uniformit Soit n le nombre total de r f rences une page p La r partition des n n est pas uniforme un faible pourcentage des pages cumule g n ralement un taux tr s important du nombre total des r f rences Il est courant de constater que plus des 75 des r f rences int ressent moins de 20 des pages 53 Propri t de Localit Sur un temps d observation assez court la r partition des r f rences pr sente une certaine stabilit les r f rences observ es dans un pass r cent sont en g n ral une bonne estimation des prochaines r f rences partir de cette constatation de localit on peut cr er un mod le de comportement des programmes Dans ce mod le le d roulement d un programme est d fini comme une succession de phases s par es par des transitions Une phase est caract ris e par un ensemble de pages S et un intervalle de temps virtuel T Lorsque le programme entre en phase 5 il y reste un temps T en effectuant principalement des r f rences des pages de S Ensuite il subit un transition durant laquelle les r f rences aux pages sont dispers es avant d entrer dans la phase 1 Les phases constituent donc des p riodes de comportement stable et relativement pr visible alors que les transitions correspondent un comportement plus erratique L exp rience montre que les p riodes de transition ne repr sentent qu une faible partie du temps virtuel t
102. notion de classe Les op rations et fonctions d acc s associ es une classe sont applicables chaque objet de la classe Il peut advenir que l on d sire d finir des ensembles d objets ayant la fois des propri t s communes avec une classe d j existante et des propri t s particuli res La notion de sous classe permet d y parvenir Une sous classe h rite des propri t s associ es la classe m re auxquelles s ajoutent des pro pri t s sp cifiques Cette sous classe pourra son tour tre consid r e comme classe m re d un autre ensemble etc On obtient ainsi une hi rarchie de classes Citons quelques classes bien connues et la ressource physique associ e dont elles constituent une abstraction les fichiers m moire secondaire les flots organes p riph riques les processus processeur la m moire virtuelle m moire physique Les fonctions d acc s associ es une classe quelconque permettent entre autre de cr er ou de supprimer des objets de cette classe et donc d en faire varier dynamiquement le nombre Une fois cr un objet dispose d un tat repr sent par ses propres donn es qui peuvent varier dans le temps 1 2 3 Interfaces et sp cifications Comme nous l avons vu dans les deux paragraphes pr c dents une interface est associ e soit une machine abstraite soit une classe d objets Elle comporte trois types d information des structures de donn es
103. obtiennent le statut pr t sont rang s dans une file chacune de ses interventions le distributeur alloue le contr le au processus en t te de file Si le temps d ex cution qui lui est ainsi imparti expire avant son ach vement il est plac en queue de file et le contr le est donn au processus suivant arriv e ki CPU sortie r quisition pr emption FIG 5 3 Ordonnancement par tourniquet Cette technique est satisfaisante dans les syst mes temps partag o les utilisateurs interactifs doivent b n ficier de temps de r ponse corrects Le co t de la r quisition peut tre maintenu faible si les m canismes de commutation sont efficaces et la m moire suffisante pour contenir plusieurs processus simultan ment noter aussi la n cessit d un r glage judicieux du quantum pour accro tre le taux d utilisation du processeur et donc diminuer les temps de r ponse voir 5 3 4 Travail plus court d abord SJF La technique Plus court d abord SJF pour Shortest Job First est encore un sch ma d or donnancement sans r quisition donc inutilisable en temps partag o le processus ayant le plus faible temps estim d ex cution jusqu ach vement est prioritaire C est donc une technique qui a t cr e pour pallier partiellement l inconv nient de FIFO qui autorisait l ex cution de travaux tr s longs avant des travaux de plus f
104. ocage sauf la premi re En effet nous voulons nous r server le droit de disposer de ressources d di es 4 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 tout ou rien 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 mise 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 26 des ressources se fera elle aussi par tape ce qui r duit consid rablement la sous utilisation des r
105. ogique du pages du pages physiques pages du logique du processus 1 processus 1 processus 2 processus 2 Pa Pa 7 Pa Pb j Pb J gt D1 D1 D4 J gt D2 D2 D5 D4 D6 D5 D7 2 p D7 Les pages contenant le programme Pa et Pb sont partag es mais les pages de donn es D1 D7 ne le sont pas F1G 6 12 Partage de pages entre m moires logiques pagin es Si l unit de partage est la page une page physique partag e peut recevoir des droits d acc s dis tincts dans chaque m moire logique o elle figure Ces droits sont sp cifi s l entr e correspondante de la table de pages 56 6 5 M moire segment e 6 5 1 Principe de la segmentation Dans les syst mes de m moire pagin e la division en pages est arbitraire et ne tient pas compte du mode d organisation des donn es d un processus Notamment il est fort probable que certaines structures de donn es vont se trouver cheval sur plusieurs pages ce qui peut tre la cause de temps d acc s plus importants L objectif des m moires segment es est de mettre en rapport la structure logique de la m moire vue des processus et l implantation physique de cette m moire Pour ce faire la m moire logique segment e d un processus est d finie comme un ensemble de segments num rot s partir de z ro figure Un segment est une zone contigu de taille variable code 2 L2 code 1 LO data 2 L3 data
106. ompte imm diatement si deux conditions sont remplies aucun niveau de priorit sup rieure n est en tat d attente la CPU se trouve dans une phase interruptible fin d instruction Le niveau passe alors l tat actif tat actif il implique la prise en compte de l interruption par la CPU et dure pendant toute la dur e du traitant d interruption Des instructions privil gi es permettent d armer ou de d sarmer d autoriser ou de masquer de d clencher un ou plusieurs niveaux d interruption Lorsque le nombre de niveaux d interruption est limit un registre sp cialis de la CPU contient ce que l on appelle le masque d interruption A chaque niveau est associ un bit indiquant s il est autoris ou masqu 2 4 Les appels syst mes Nous avons vu pr c demment que les programmes utilisateur s ex cutent en mode esclave Les instructions privil gi es permettant la programmation des E S leur sont donc interdites Dans ces conditions toute demande d E S et plus g n ralement toutes les actions demandant des droits tendus passent par une requ te en bonne et due forme au S E Cette requ te est r alis e par le truchement d une instruction de la CPU qui provoque une interruption Nous l appellerons SVC pour SuperVisor Call mais on utilise aussi le terme TRAP Cette solution bien que compliqu e a les avantages suivants L interruption provoque un branchement vers le traitant d interruption m
107. on chargement en m moire cette information mise jour automatiquement par le mat riel est utilis e par l algorithme de remplacement pour viter ventuellement la sauvegarde d une page remplac e Exemple DEC VAX 11 780 La m moire virtuelle accessible un processus sur le DEC VAX 11 780 est d finie par une adresse de 32 bits 30 bits d finissent l espace virtuel accessible un usager num ro de page virtuelle sur 21 bits d placement sur 9 bits Les 2 bits restants permettent de d finir une extension de l espace virtuel utilis e par le syst me d exploitation Chaque entr e de la table des pages virtuelles d un processus comporte 32 bits 61 bits signification 31 bit de pr sence 3 27 protection 26 bit d criture 2 21 champ r serv au syst me d exploitation 20 0 num ro de page physique Une m moire associative retient les couples npv npp les plus r cents 7 2 Pagination deux niveaux d une m moire virtuelle La tendance la croissance de la taille des m moires virtuelles se heurte au probl me de l en combrement de la m moire principale par les tables de pages virtuelles dont la taille augmente en proportion La pagination deux niveaux voir m me plusieurs niveaux vise r soudre ce probl me en limitant les tables de pages virtuelles aux seules parties effectivement utilis es de la m moire virtuelle
108. ortant ou au contraire le favoriser car on est en droit de penser qu il va bient t s achever Cette question rev t une importance particuli re lorsque le syst me est en surcharge 8 temps d ex cution restant le temps d attente moyen peut tre r duit en ex cutant de pr f rence les processus r clamant un temps CPU minimum pour s achever h las l valuation de ce temps restant est rarement possible 5 2 3 R quisition ou pas On dit qu un ordonnanceur n op re pas de r quisition si d s lors qu il a allou la CPU un processus il lui est impossible de le lui retirer R ciproquement une politique d ordonnancement autorise la r quisition si le contr le peut tre retir tout moment au processus actif Cette possibilit est absolument et trivialement n cessaire sur les sites supportant des applications temps r el C est la contrainte li e aux temps de r ponse qui rend cette technique indispensable dans les syst mes interactifs Mais la r quisition engendre un surco t non n gligeable l exploitation 34 co t en temps occasionn par les changements de contexte incessants co t en espace engendr par la n cessit de partager la m moire entre tous les processus La non r quisition est g nante pour les travaux courts lorsqu ils doivent attendre qu un travail tr s long s ach ve mais globalement la philosophie semble plus quitable les temps de r ponse sont mieux pr visibles car l arriv e de
109. otal la majeure partie du temps virtuel tant occup par des phases de longues dur e quelques centaines de milliers d instructions Qualitativement ce type de comportement s explique par le fait que les programmes sont souvent organis s en proc dures poss dant chacune un contexte sp cifique que les acc s aux donn es sont souvent concentr s parcours de tableau que les programmes comportent des boucles concentrant aussi les r f rences La notion d ensemble de travail working set est galement utilis e pour caract riser le comportement des programmes et pr voir d apr s l observation Soit W t T l ensemble des pages ayant t r f renc es entre les temps t T et t D apr s la propri t de localit ces pages ont une probabilit plus lev e que les autres de faire l objet d une r f rence au temps t condition toutefois que la taille de la fen tre d observation T soit convenablement choisie En admettant un comportement suivant le mod le phase transition T devra tre inf rieur T en phase i 6 4 3 M moire associative et pagination Une m moire associative est un ensemble de couple entr e sortie La pr sence d une valeur sur le bus d entr e provoque soit l apparition d une valeur de sortie soit un signal d chec indiquant que cette entr e n existe pas dans la m moire associative figure Ces m moires ont quelques dizaines quelques centaines d entr es et leur co t tr s lev a
110. our chaque m moire virtuelle une description d implantation Sa forme la plus simple est celle d une table qui indique pour chaque page virtuelle son adresse en m moire secondaire Une m moire segment e comporte une telle table pour chaque segment Une autre forme de description combine m moire virtuelle et fichiers une zone de m moire virtuelle est associ le contenu d un ou de plusieurs fichiers La localisation d une page virtuelle en m moire secondaire est alors d termin e en consultant la table d implantation du fichier dont elle contient un l ment Exemple Dans le syst me Multics il n y a pas de distinction entre segment et fichier les tables d implantation des fichiers d crivent la localisation des pages virtuelles en m moire secondaire R ciproquement l acc s aux fichiers est op r par association de leur articles aux pages d une m moire virtuelle Cette op ration est appel e couplage L tape 2 met en uvre un algorithme de remplacement voir Elle n cessite de conserver une table d occupation de la m moire physique qui indique pour toute page physique occup e l identit de la page virtuelle qui l occupe ainsi que les renseignements compl mentaires protection partage etc 63 7 4 Comportement des programmes en m moire virtuelle Le comportement d un programme en m moire restreinte pour un algorithme de remplacement donn est caract ris par la suite de ses d fauts de pages L exp
111. p tition pour l acc s une ressource ou une information partag e fonctionner en coop ration pour mener bien une application D s l instant o deux processus ont une ressource en commun l ordre dans lequel ils s ex cutent n est pas indiff rent C est le probl me de la synchronisation Lorsqu ils changent des donn es on parle de communication Ce chapitre traite de ces probl mes en architecture centralis e i e avec m moire commune tous les processus 8 2 Synchronisation de processus 8 2 1 Exclusion mutuelle C est le probl me qui se pose lorsqu une ressource ne peut appartenir qu un seul processus la fois et que plusieurs processus concurrents en ont besoin pour se d rouler Par exemple partage d une imprimante ressource physique acc s un fichier en lecture pour n utilisateurs simultan ment mais en criture pour un seul ressource logique Dans le premier exemple une variable bool enne du syst me indiquera si l imprimante est libre ou non Il ne faut pas que deux processus puissent lire la valeur de cette variable simultan ment la trouver vraie et s approprier donc tous deux l imprimante 8 2 2 Programmation de l exclusion mutuelle Une ressource non partageable simultan ment est dite critique Toute s quence de programme qui utilise une ressource critique est dite section critique S C Les vitesses de calcul des diff rents processus sont inconnues On supposer
112. par registre de base et registre limite 6 3 2 Algorithmes de gestion de la m moire par zones Disposant d une file constitu e par les programmes en attente de traitement un choix doit tre op r afin de d terminer leur ordre de lancement Cet ordre pourra tre tout simplement celui de la file d attente ou dict par des contraintes de priorit s calcul es par le syst me en fonction des demandes de ressources place m moire nombre de p riph riques etc ou du temps d ex cution pr sum En tout tat de cause cet ordre sera aussi fonction de la taille des diff rentes partitions libres Il faut auparavant r soudre les probl mes suivants choix d une repr sentation des partitions d finition des crit res de s lection d une partition libre politique de lib ration d une partition occup e d cision prendre lorsqu aucune partition ne convient 6 3 2 1 Repr sentation des partitions Une partition est d finie par sa taille et son adresse de d but contenues dans un descripteur En supposant que les tailles demand es sont variables le nombre de partitions le sera aussi En cons quence il est pr f rable plut t que de regrouper les descripteurs dans une table de les situer dans les partitions elles m mes et de les cha ner entre eux L ordre du cha nage a une influence sur l efficacit des algorithmes On peut choisir l ordre de lib ration des partitions mais le plus souvent on utilise l un d
113. que d allocation m moire doit donc apporter une solution aux deux probl mes suivants 1 r aliser la correspondance entre adresses logiques et adresses physiques 44 M m physique contigu M m physique non contigu m M m logique contigu Correspondance fixe m moire pagin e partitions fixes m moire virtuelle pagin e partition unique partitions variables M m logique non contigu m moire segment e m moire segment e pagin e FIG 6 2 Les diff rentes organisations de la m moire 2 r aliser la gestion de la m moire physique allocation des emplacements transfert de l infor mation Lorsque les informations appartiennent plusieurs utilisateurs deux contraintes suppl mentaires apparaissent 3 r aliser le partage d information entre ces utilisateurs 4 assurer la protection mutuelle d informations appartenant des usagers distincts Une politique d allocation de m moire id ale aurait pour effet d assurer qu tout instant l informa tion n cessaire l ex cution de l instruction en cours soit imm diatement accessible au processeur donc se trouve en m moire principale Cet objectif n est en g n ral pas atteint on cherche alors r duire la probabilit que l information soit absente de la m moire lorsqu elle est n cessaire d faut de page Le probl me se r sume alors deux questions Quand ch
114. r 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 29 P8 P8 P7 Me P7 R6 R6 R duction P9 par P9 P9 R7 R7 R duction par P7 P8 P8 P7 K P7 R6 R6 R duction P9 par P8 O P9 R7 R7 F1G 4 3 R ductions d un graphe d allocation 4 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 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 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 prohibitif et n cessiteraient les comp tences d un op rateur attentif ce qui n
115. r aux travaux abandonn s faisant rapide ment baisser le rendement Une seconde possibilit est donc offerte poursuivre l ex cution du travail durant le temps estim augment si n cessaire d un certain pourcentage faible en g n ral puis de le mettre de c t dans l tat o il se trouve pour reprendre son ex cution plus tard Bien entendu l utilisateur sera p nalis par cette attente mais aussi par un suppl ment de facturation Une troisi me possibilit est de ne pas mettre de c t le travail mais de poursuivre son ex cution jusqu ach vement en facturant le temps exc dent un taux beaucoup plus lev Cette solution est finalement mieux accept e car le suppl ment correspond effectivement un meilleur service 5 3 5 Plus court temps restant SRT La strat gie SRT pour Shortest Remaining Time est la version avec r quisition de SJF donc utilisable en temps partag o l encore priorit est donn e au processus dont le temps d ex cution restant est le plus faible en consid rant chaque instant les nouveaux arrivants Dans SRT un processus actif peut donc tre interrompu au profit d un nouveau processus ayant un temps d ex cution estim plus court que le temps n cessaire l ach vement du premier L encore et plus particuli rement du fait de la r quisition le designer doit pr voir une dissuasion l gard des malins connaissant la strat gie d ordonnance
116. r le m canisme est beaucoup plus complexe En r sum un appel au S E permet l utilisation depuis un programme utilisateur d un certain nombre de routines syst me exigeant des droits tendus Du cot du S E le traitant de l interruption SVC a la structure suivante sauver le contexte du demandeur v rifier la nature de la requ te v rifier les arguments de la requ te v rifier les droits du demandeur ex cuter la demande restaurer le contexte du demandeur retour vers le demandeur L ensemble des routines syst mes ainsi offertes l utilisateur peut tre consid r comme une ex tension du r pertoire des instructions chaque SVC repr sentant une macro instruction constituant ainsi une nouvelle machine 2 5 Les d routements Un d routement est une interruption qui intervient lorsqu une anomalie t d tect e dans le d roulement d une instruction emp chant ainsi son ex cution On distingue trois types de causes donn es incorrectes division par z ro d bordement arithm tique etc tentative de violation d une protection et ou d une interdiction violation de protection m moire utilisation d une instruction privil gi e en mode esclave etc impossibilit d ex cution d une instruction instruction inconnue ou instruction optionnelle absente de la configuration utilis e etc Selon la cause d un d routement on peut ventuellement en supprimer l effet
117. r celles qu il poss de d j les ressources ne peuvent tre r quisitionn es il existe un ensemble de processus po p1 pA tel que chaque p attend une ressource occup e par pi 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 interblocages 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 conditions 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 ressources 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 gu
118. r cons quent Nf No MINOR ny Co Min n Co no Si on utilise un s maphore pour r aliser l exclusion mutuelle on l initialise 1 On v rifie l aide de la relation pr c dente qu il permet l exclusion mutuelle car le nombre de processus actuellement en section critique est nf No MIN Nu 1 lt 1 Un processus au plus est donc en section critique De m me si aucun processus n est en section critique nf n 0 min np n 1 donc np ny 0 et np ny aucun processus n est bloqu Certaines pr cautions sont n cessaires pour utiliser les s maphores et les verrous leur modification ne doit se faire que par les primitives P et V et donc ils ne doivent pas faire partie de l espace adressable de l utilisateur si un processus est d truit en section critique le syst me doit veiller lib rer la section critique enfin les primitives n indiquent pas l ordre dans lequel les processus en attente sont activ s Dans le cas o l on utilise des priorit s rien n emp che une coalition de processus de forte priorit d en bloquer d autres ind finiment 76 8 2 8 S maphores priv s Un s maphore s est un s maphore priv d un processus si seul ce processus peut ex cuter P s les autres processus ne pouvant agir que par V s Les s maphores priv s sont utilis s pour programmer l envoi l attente et la reception d un signal par un processus Si un processus doit attendre un
119. rioritaire On associe chaque cause d interrup tion un num ro k qui l identifie On dispose galement dans les adresses basses de la m moire d une table appel e le vecteur d interruptions vi Les cases vi k de cette table contiennent l adresse de la routine ex cuter lors d une interruption de cause k Cette routine est appel e le traitant d interruption de cause k Plus pr cis ment lors d une interruption de cause k la CPU effectue d s la fin de l instruction en cours les actions suivantes 1 sauvegarder la valeur du compteur ordinal et le mode d ex cution dans une pile ou dans une case m moire particuli re suivant les C P U 2 passer en mode ma tre 13 3 forcer dans le compteur ordinal la valeur vi k c est dire l adresse de la premi re instruction de la routine associ e l interruption de cause k L interruption est donc un m canisme mat riel puisque la sauvegarde et l initialisation du comp teur ordinal partir du vecteur d interruptions sont des op rations r alis es par la CPU Le traitant repr sente la partie logicielle du m canisme d interruption Il a presque toujours la structure sui vante 1 Sauvegarder la valeur des registres de la CPU dans un emplacement particulier de la m moire Cette tape est couramment appel e la sauvegarde du contexte 2 Traiter la cause de l interruption 3 Restaurer la valeur des registres de la CPU et le mode du programme interrompu C est
120. s de syst mes doivent valuer avec beaucoup de pr cautions les co ts engendr s par des m canismes sophistiqu s car ils peuvent dans bien des cas aller l encontre du but recherch le gain de temps 5 3 6 Plus grand rapport ensuite HRN En 1971 Brinch Hanssen propose la strat gie HRN pour Highest Response Ratio Next Elle corrige certains travers de SJF et en particulier le favoritisme excessif dont b n ficient les nouveaux travaux courts HRN peut tre consid r avec ou sans r quisition La priorit de chaque travail est fonction non seulement du temps de service mais aussi du temps d attente Les priorit s sont donc dynamiques et calcul es par la formule temps d attente temps de service priorit temps de service en choisissant de pr f rence les travaux courts si le niveau de priorit est identique Ce syst me pr sente plusieurs avantages Les travaux longs bien qu tant d favoris s voient leur priorit augmenter au fur et mesure de leur attente Ils sont donc s r de r cup rer la CPU au bout d un temps d attente fini ce qui limine le risque de privation Si on utilise HRN avec un m canisme de r quisition de la CPU les processus qui restent en sommeil un certain temps apr s une demande d E S par exemple voient leur priorit augmenter Cette augmentation permet de leur allouer plus de temps CPU lors du r veil ce qui est assez logique 5 3 7 Tourniquet mult
121. s le pilote envoie des ordres son p riph rique qui r pond au bout d un temps non d fini par le biais d une interruption Le syst me d E S masque les drivers de p riph riques Il offre des fonctions d E S qui bien qu tant de bas niveau ne distinguent pas de mani re explicite la nature du p riph rique Ces E S sont r alis es partir ou vers des zones de la m moire appel s des tampons buffer L allocation de ces tampons passe donc par le gestionnaire de la m moire centrale La gestion de la m moire centrale r pond aux demandes d allocation et de lib ration de zones m moire Dans une premi re approche la m moire virtuelle peut tre vue comme une extension de la m moire centrale qui est temporairement rang e sur disque Ce d placement d une partie de la m moire implique le retour la demande des informations utiles et non pr sentes en m moire centrale c est une op ration d E S l sauvegarde sur disque des informations pr sentes mais inutilis es Le syst me de gestion des fichiers SGF offre toutes les primitives n cessaires la cr ation destruction modification des fichiers se trouvant en m moire secondaire La gestion des processus r partit la ou les CPU entre les t ches qui en ont besoin Ces t ches consomment de la m moire et exploitent des fichiers Les processus utilisateur dont les interpr teurs de commande sont un exemple particulier utili
122. s contraintes d interfa age autorisera la mise au point et l valuation de performance de ces parties par simple substitution sans affecter le reste du syst me propos de ce cas de figure les contraintes s av rent tr s strictes la substitution d un module par un autre module n tant possible qu la condition que les autres modules n y acc dent qu en utilisant son interface En particulier un programme appelant un module ne devra en aucune fa on exploiter des renseignements sur la r alisation interne du module Une m thode efficace pour parvenir ce but a t propos e par Parnas laisser les programmeurs d un module dans l ignorance de la r alisation des autres 1 2 4 Les composantes d un S E L tude des composantes permet de fixer les r les de chaque couche logicielle et les rapports entre ces couches Nous allons par la suite distinguer les modules suivants voir la figure Le gestionnaire d interruptions r cup re les interruptions mat rielles et logicielles et applique le traitement appropri qui varie sur la cause de ces interruptions Les pilotes de p riph riques drivers g rent l change des donn es avec les p riph riques Chaque pilote conna t son p riph rique et cache son mode d utilisation aux couches sup rieures du syst me Ces drivers utilisent les interruptions car le dialogue asynchrone entre CPU et unit s externes s effectue au moyen des interruptions En d autres terme
123. satisfaire une demande alors que la somme des tailles de partitions libre est largement sup rieure Une solution consiste compacter les partitions allou es en les d pla ant vers une extr mit de la m moire laissant appara tre ainsi l autre extr mit une partition libre de taille gale la somme des tailles des partitions libres primitives Le compactage peut s effectuer de deux fa ons possibles par recopie l int rieur de la m moire physique en utilisant une instruction de type MOVE voir ci dessous op ration monopolisant le processeur central MOVE adresse d part adresse arriv e longueur 49 par recopies successives des partitions sur disque puis du disque en m moire la place voulue en utilisant un processeur d entr e sortie L op ration est alors plus longue mais a le m rite de lib rer le processeur central pour poursuivre l ex cution des autres programmes La figure donne un exemple simple de compactage Il montre les diff rentes strat gies de recopie des partitions occup es de mani re limiter la quantit de donn es d placer On passe dans cet exemple de 200 ko 50 ko Il est bien certain que seule une possibilit de r implantation dynamique permet d op rer un tel compactage D autre part Knuth a montr que lorsque l algorithme d allocation ne peut satisfaire une demande cela intervient alors que le taux de remplissage de la m moire est tel qu apr s compac t
124. sent le S E en lui adressant des requ tes en bonne et due forme Ces requ tes permettent au choix de lancer de figer ou de tuer d autres processus d exploiter ou de modifier des fichiers d allouer de la m moire etc processus utilisateur interpr teur de commandes interface d appel au syst me SVC Gestion des processus o Gestion des fichiers y Gestion de la m moire centrale e Gestion du syst me d E S y Gestion des interruptions me Drivers de p riph riques interface vers le mat riel Machine physique FIG 1 3 Les composantes et la structure d un syst me 1 3 Historique des syst mes d exploitation L historique est un moyen agr able de pr senter les principaux concepts en partant de l absence de S E pour arriver aux syst mes r partis 1 3 1 Syst mes monoprogramm s Sur les premiers ordinateurs il n existe pas de S E proprement parler L exploitation de la machine est confi e tour de r le aux utilisateurs chacun disposant d une p riode de temps fixe C est une organisation en porte ouverte Au d but des ann es 50 on voit appara tre le premier programme dont le but est de g rer la machine c est le moniteur d encha nement des t ches Cet embryon de S E a la charge d encha ner l ex cution des programmes pour am liorer l utilisation de
125. signal d un autre il se bloque par P s derri re son s maphore priv initialis 0 Si le processus P est actif lorsque P ex cute V s s tant un s maphore priv de P l tat de P est inchang mais la valeur du s maphore a augment d une unit et le processus P ne se bloquera pas la prochaine primitive P s Le signal est donc m moris Ce m canisme permet de m moriser n signaux successifs On peut combiner les s maphores d exclusion mutuelle et priv s Pour se poursuivre un processus a besoin de tester des variables d tat modifi es par d autres processus Il ne peut faire le test qu l int rieur d une section critique Mais il ne doit pas s y bloquer Il faut donc qu l int rieur de la section critique il se donne un droit de passage par V s s tant un s maphore priv de P dans le cas o il ne doit pas se bloquer rien sinon A la sortie de la section critique il utilise son droit de passage ventuel par P s S il y a eu V s il passe sinon il se bloque hors de la section critique P P mutex si le blocage est inutile alors V sempriv fin si V mutezx P sempriv s quence ex cut e par P sempriv appartient P L activation par un autre processus s crit P P mutex si le processus P doit tre d bloqu alors V sempriv fin si V mutez 8 2 9 Mod le du producteur et du consommateur Ce mod le est bas sur les deux points suivants 1 aucune hypoth se n est fai
126. sition du processeur le programme en cours doit tre sauvegard sur disque avant le chargement de son successeur RL D S E partition unique m moire RB FIG 6 3 Syst me partition unique Afin d viter que des erreurs d adressage du processus utilisateur ne viennent alt rer le S E r sident la partition unique peut tre d limit e par des registres de la CPU registre de base RB pour le d but et registre limite RL pour la taille A chaque acc s une case d adresse a la CPU v rifie que RB lt lt RB RL Si ce test choue un d routement pour erreur d adressage est g n r Ce sch ma a l avantage de la simplicit Son principal inconv nient est de laisser la CPU inutilis e pendant la dur e des transferts Il est employ sur des installations de petite taille lorsque les contraintes de temps de r ponse sont compatibles avec la dur e et la fr quence des transferts Des am liorations permettent de r duire le volume d information transf r e et donc la perte de temps pour la CPU lorsqu un programme est sauvegard sur disque on ne range que la partie modifi e en pratique la zone des donn es l algorithme de la peau d oignon permet d pargner des transferts lorsqu un programme est recouvert par un autre de taille plus petite il suffit pour restaurer le plus gros de recharger la partie recouverte Ces am liorations n apportent n anmoins qu un gain limi
127. t la taille des transferts n intervenant que pour une faible part dans le temps requis Il serait pr f rable de pouvoir ex cuter un programme pen dant la dur e de transfert d un autre Pour ce faire il faut donc conserver simultan ment en m moire plusieurs programmes en partie ou en totalit Ce mode de partage est appel multi programmation Une multi programmation sans r implantation dynamique est possible par la partition de la m moire 6 2 2 Partition fixe de la m moire Dans un syst me partitions fixes la m moire est partag e de fa on statique en un nombre fixe de partitions les tailles et limites de ces partitions tant d finies lors de la g n ration du syst me Chaque programme est affect de fa on fixe une partition au moment de la construction de son image m moire par l tape d dition de liens Les programmes sous leur forme ex cutable sont conserv s sur disque sous forme absolue et les adresses qui y figurent sont les adresses physiques correspondant l implantation de chacun d eux dans la partition qui lui a t attribu e 46 Pendant qu un programme est transf r en entr e ou sortie un autre programme peut tre ex cut dans une autre partition il faut bien entendu disposer d un processeur d entr e sortie auto nome canal ou ADM La figure sch matise l implantation des programmes et le chronogramme d activit dans un syst me partitions fixes S E zone
128. t de pages et en introduisant un temps de retard dans les r actions du r gulateur Un pic transitoire ne provoque donc pas de r action s il n puise pas la r serve et si sa dur e est inf rieure au temps de retard La dur e de ce d lai et la taille de la r serve doivent tre d termin s par l exp rience 68 La r gulation de charge permet d utiliser au mieux les ressources disponibles en pr sence d une charge donn e Pour absorber une charge plus lev e et pour am liorer les performances d un syst me on peut tre amen am liorer les performances du mat riel par extension ou remplace ment Il faut alors veiller ce que la configuration reste quilibr e pour exploiter pleinement ces gains de performance Dans tous les cas de figure le S E doit tre capable d valuer la charge pour prendre la bonne d cision et viter l apparition d un croulement Cette valuation se base sur deux m thodes la m thode de l ensemble de travail l observation de la fr quence d apparition des d fauts de page PFF ou Page Fault Fre quency 7 6 2 Algorithme fond sur l ensemble de travail On entretient en permanence pour chaque processus son ensemble de travail lors d un d faut de page une page virtuelle n appartenant aucun des ensembles de travail pr sents en m moire est choisie comme victime S il n existe pas de telle page on r quisitionne les pages physiques qui contiennent l ensemble de
129. t la gestion est plus simple que celle de partitions de taille variable Le nombre d emplacements d une page physique ou logique est toujours une puissance de 2 Notons 2 la taille nombre d emplacements d une page logique ou physique et 2 le nombre de pages Il y a pour l instant autant de pages logiques que de pages physiques M moire M moire logique physique Fonction de pagination Ps F1G 6 7 M moire lin aire pagin e Une adresse logique pagin e est alors construite par concat nation d un num ro de page lo gique n bits et d un d placement dans la page l bits De m me une adresse physique est la concat nation d un num ro de page physique n bits et d un d placement l bits Les tailles de page usuelles vont de 0 5ko 32ko tant donn un num ro de page logique npl la fonction de pagination permet de trouver le num ro de la page physique npp qui la contient Dans un souci d efficacit cette fonction est r alis e par un m canisme mat riel La r alisation la plus courante de la fonction de pagination utilise une table de pages en m moire index e par un num ro de page logique table desc de la figure Lors d un acc s la m moire la correspondance adresse logique adresse physique qui est une op ration mat rielle est mise en uvre comme suit 51 adr logique
130. te le nombre de processus bloqu s pour traitement du d faut de page augmente galement Donc le degr de multi programmation et le taux d utilisation de la CPU baissent Face cette baisse l ordonnanceur long terme peut d cider de ramener des processus en m moire swapping in pour am liorer le taux d utilisation de la CPU Bien entendu ces nouveaux venus vont prendre des pages physiques provoquer des d fauts de page et augmenter le nombre d j important de d fauts de page chez les autres processus C est un effet boule 67 Taux d utilisation de la CPU D d gr de multiprogrammation FIG 7 7 croulement d un syst me de m moire virtuelle pagin e de neige qui entra ne l croulement Les r sultats qui viennent d tre pr sent s montrent qu il semble pr f rable d essayer d allouer chaque programme une taille de m moire bien adapt e son comportement donc variable dynami quement Cela peut tre tent de deux fa ons en utilisant un algorithme partition variable afin de r quisitionner des pages physiques mal utilis es par un processus pour les redistribuer d autres processus en utilisant une r partition de charge par variation du degr de multi programmation afin d enlever des processus de la m moire centrale quand il y a surcharge swapping out de faire revenir des processus en m moire si le couple de ressources CPU m moire est
131. te sur les vitesses relatives des processus 2 un tampon a une capacit de n messages n gt 0 L algorithme du producteur est le suivant r p ter produire un message le d poser dans le tampon jusqu L algorithme du consommateur est r p ter pr lever un message depuis le tampon le consommer jusqu R gles exclusion mutuelle au niveau du message le Consommateur ne peut pr lever un message que le Producteur est en train de ranger 17 le Producteur ne peut pas placer un message si le tampon est plein le Consommateur doit pr lever tout message une fois et une seule si le Producteur est en attente parce que le tampon est plein il doit tre pr venu d s que ceci n est plus vrai De m me pour le Consommateur avec tampon vide NPlein s maphore 0 NVide s maphore n Le producteur s crit r p ter P NVide produire un message le d poser dans le tampon V NPlein jusqu et le consommateur r p ter P NPlein consommer V NVide jusqu NPlein gt 0 indique le nombre de messages disponibles dans le tampon NPlein lt 0 indique que le consommateur attend un message NVide gt 0 indique le nombre de tampons libres NVide lt 0 indique que le producteur attend un tampon libre 8 3 Communication entre processus La coop ration de plusieurs processus n cessite en g n ral l change d informat
132. thme de remplacement et cela d autant plus que les performances initiales sont mauvaises 7 6 croulement d un syst me de m moire virtuelle pagin e 7 6 1 Apparition de l croulement Sur les premiers syst mes m moire virtuelle pagin e on constatait partir d une certaine charge mesur e par exemple par le nombre d usagers interactifs une d gradation brutale des performances Ce ph nom ne appel croulement thrashing se traduit par une chute du taux d utilisation du processeur et un fort accroissement des changes de pages le temps de r ponse atteint des valeurs inacceptables Une explication qualitative de l croulement permet de mettre en vidence ses causes et de proposer des rem des Consid rons un syst me m moire pagin e entre un ensemble de processus dont chacun correspond un usager interactif La m moire physique est partag e quitablement entre les processus dont le comportement moyen est suppos identique ce partage est mis en uvre par un algorithme de remplacement global Au del d un certain nombre de processus figure le nombre moyen de pages physiques allou es chacun d eux ne permet plus de stocker en m moire centrale leur ensemble de travail c est dire le sous ensemble de leur pages virtuelles fr quemment utilis es La probabilit globale de d faut de page cro t d s lors tr s rapidement avec le nombre de processus Si le nombre de d fauts de page augmen
133. tion de cette m moire logique en m moire physique R implantation dynamique la correspondance logique physique est variable dans le temps De ce fait l allocation de la m moire physique se fait par zones de taille variable et ou par pages de taille fixe Correspondance fixe aussi appel e implantation statique La correspondance est tablie une fois pour toutes au moment de la compilation C est le cas dans les syst mes partition unique ou fixes Correspondance dynamique aussi appel e r implantation dynamique La correspondance lo gique physique peut aussi tre dynamique et ce de deux mani res Elle peut tre fix e au moment du chargement du processus et donc varier entre deux ex cutions La m moire est allou e sous forme de zone contigu s appel s des partitions c est le syst me des partitions variables Elle peut galement varier durant l ex cution du processus Les objets sont donc d plac s l int rieur la m moire centrale Bien entendu ces d placements op r s par le syst me doivent tre transparents pour le processus C est le cas dans les syst mes pagin s ou segment s qui allouent la m moire par pages de taille fixe ou segments de taille variable L allocation de m moire doit permettre un processus l acc s un objet d fini en m moire lo gique en amenant en temps voulu cet objet en m moire principale la seule directement adressable Une politi
134. tion 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 atomique 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 nuits blanches au concepteurs d aujourd hui 4 7 Et demain Nous venons d avoir un aper u de ce qui se faisait ou pourrait 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 abandon nant les sch mas s quentiels Les bancs de processeurs seront monnaie courante 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 sans m me le savoir 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
135. ts p riph riques utilis s etc L ensemble de ces composantes forme le contexte d ex cution d un processus ou plus simplement le contexte 3 2 tat d un processus Un processus n est pas continuellement en train de s ex cuter Si la machine comporte n pro cesseurs identiques un instant donn il y a au maximum n processus actifs En fait parmi tous les processus qui sont susceptibles de s ex cuter seulement un petit nombre s ex cutent r ellement L allocation de la CPU aux processus qui la r clament est appel e l ordonnancement de la CPU Elle sera tudi e au chapitre L tat op rationnel d un processus est un moyen de repr senter les diff rentes tapes de ce processus telles qu elles sont g r es par le syst me d exploitation Le sch ma montre les divers tats dans lesquels dans une premi re approche intuitive peut se trouver un processus Initialement un processus est connu du syst me mais l ex cution n a pas d but Lorsqu il est initialis il devient pr t tre ex cut 1 Lors de l allocation de la CPU ce processus il devient actif 2 Trois cas peuvent alors se pr senter Le processus se termine 3 Le processus est en attente 5 d un v nement et d s sa r ception il redeviendra pr t 6 17 18 o pr t m 6 i 1 1 initialisation connu 2 ex cution He 4 2 3 ach vement 4 pr
136. u pas unit s de bande partageables m moire disques ou pas imprimantes unit s de bande Elles peuvent tre phy siques 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 demandeur sont dites r entrantes Les ressources peuvent galement tre banalis es si on dispose de plusieurs occurrences identiques d une m me ressource 4 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 Le S E 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 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
137. um de ressources R utilisables par le processus P alloc i j nombre de ressources R couramment allou es au processus P par d finition nous avons donc alloc i j lt maxi j 27 Un processus P peut s ex cuter si et seulement si pour toute ressource R nous avons max i j alloc i j lt dispoli Un ordre d ex cution P Po Pa est dit sain si et seulement si les processus P Po Pn peuvent s ex cuter jusqu leur terme les uns apr s les autres dans cet ordre Bien entendu l ex cution d un processus P implique la lib ration par P 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 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 le S E 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 max i 5 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 process
138. un d entre eux peut se trouver dans l impossibilit de progresser pour une raison logique l attente d un signal en provenance d un autre processus Par exemple le processus P labore un r sultat que le processus Q utilise Q ne peut s ex cuter que lorsque P a produit ce r sultat On distingue donc deux types de blocage Technologique pour l absence de ressource 69 70 Intrins que pour la synchronisation Du point de vue du syst me il est commode de consid rer comme des ressources les signaux de synchronisation le blocage ne se produit plus alors que pour l absence d une ressource Au contraire du point de vue du programmeur qui ne se pr occupe que du blocage intrins que il est agr able d envisager que chaque processus s ex cute sur une machine virtuelle qui comprend toutes les ressources n cessaires son ach vement La correspondance entre les ressources de chaque machine virtuelle et les ressources physiques est laiss e la charge du syst me 8 1 3 Acc s aux ressources Une ressource est dite ocale un processus s il est seul a pouvoir l utiliser Elle doit obligatoi rement dispara tre la fin de l ex cution de ce processus Une ressource qui n est locale aucun processus est dite commune Une ressource est dite partageable avec n points d acc s n gt 1 si cette ressource peut tre attribu e au m me instant n processus au plus Un ensemble de processus peut entrer en com
139. unication et une synchronisation ais e entre les processus d une m me application C est l objet du chapitre parall lisme et synchronisation De plus cette structuration base de proces sus coop ratifs est la seule capable d utiliser facilement une structure mat rielle multi processeurs en associant un processus diff rent chaque processeur Nous avons parl de la cr ation d un processus mais sa disparition est une tape importante Elle lieu sur demande d un processus tranger syst me ou p re ou sur sa propre demande sous la forme d un suicide Ce dernier cas correspond l appel de la fonction standard exit du langage C 3 5 Poids lourds et poids l gers Nous avons voqu plus haut les avantages li s la structuration des applications sous la forme de processus coop ratifs Mais cette structure comporte galement des inconv nients elle implique une communication massive entre les processus ce qui engendre un co t non n gligeable de la part du syst me elle augmente le nombre de commutations de contexte c d la sauvegarde et la restauration du contexte d un processus interrompu provoquant de ce fait une perte de temps de CPU 21 La notion de thread et de syst mes multi threads vise r gler ce type de probl me Dans les syst mes multi threads un processus est d fini comme un ensemble de threads Un thread aussi appel processus de poids l ger ou lightweight process LWP est u
140. us Pj 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 ils peuvent conserver les ressources en leur possession tout en r clamant des ressources 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 satisfaction 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 ressources est inva riant Or il est bien v
141. us entrent donc simultan ment en S C En fait le probl me vient du fait que les deux op rations test du drapeau et modification ne sont pas r alis es de mani re atomique 8 2 4 L algorithme de peterson On envisage alors de signaler d abord que le processus demande l acc s la S C en affectant un bool en puis y entre effectivement s il n y a pas de conflit d acc s i e si l autre processus n a pas signal aussi son intention d entrer en S C Trois phases sont consid rer pour l entr e en S C 1 pas de demande d acc s 2 demande d acc s non encore achev e 3 acc s effectif le processus est en S C Les difficult s surviennent lorsque deux processus sont simultan ment dans la phase 2 Chaque processus doit pouvoir d terminer dans quelle phase se trouve l autre On utilisera un bool en pour chaque processus qu il affectera en entrant dans la phase 2 demande i vrai Les deux processus peuvent effectuer simultan ment ces instructions aussi l acc s en S C ne doit tre effectif que s il n y a pas de conflit i e si l autre n a rien signal Sinon il faut donner une priorit l un des processus et mettre l autre en attente S il n y a pas de conflit la priorit n est pas prise en compte et n interdit donc pas l acc s la S C En cas de conflit le processus prioritaire entre en S C l autre dans une boucle d attente contr l e par le m canisme de priorit Lorsqu un processus sort d
142. victime une page virtuelle qui ne fera l objet d aucune r f rence ult rieure ou 65 d faut la page qui fera l objet de la r f rence la plus tardive Cet algorithme suppose une connaissance de l ensemble de la cha ne de r f rences il est donc irr alisable en temps r el II permet d valuer par comparaison les autres algorithmes Tirage al atoire ALEA La victime est choisie au hasard loi uniforme parmi l ensemble des pages virtuelles pr sentes en m moire Cet algorithme n a aucune vertu particuli re car il ne tient aucun compte du comportement observ ou pr visible du programme il sert lui aussi de point de comparaison Ordre chronologique de chargement FIFO ou First In First Out Cet algorithme choisit comme victime la page virtuelle la plus anciennement charg e Son principal int r t est sa simplicit de r alisation il suffit d entretenir dans une file les num ros des pages physiques o sont charg es les pages virtuelles successives Ordre chronologique d utilisation LRU ou Least Recently Used Cet algorithme tente d approcher l algorithme optimal en utilisant la propri t de localit Son principe est le sui vant puisque les pages virtuelles r cemment utilis es ont une probabilit plus lev e que les autres d tre r utilis es dans un futur proche une page virtuelle non utilis e depuis un temps lev a une probabilit faible d tre utilis e prochainement L a

Download Pdf Manuals

Related Search

Related Contents

the PDF  Universal Energy Meter Quick User Guide  MANUEL DE CRÉATION ET DE CONFIGURATION DES    Liquid Crystal - Meadowlark Optics  Integral DDR3 Server  Jwin JT-P850 Corded Phone  Téléchargez - Canadian Tire  SR-CST Nストッパー  APENDICE  

Copyright © All rights reserved. Failed to retrieve file