Home

SYSTEME D`EXPLOITATION - Jean

1. Procesus P Procesus P Figuren 1 Illustration du m canisme de la fonction execl Il est important de comprendre que le processus cr remplace le processus appelant ce qui signifie d une part qu il n y a pas de retour de la primitive execl le processus appelant est purement est simplement limin et d autre part que le processus demeurant apr s la r ussite de cette fonction poss de le m me num ro d ex cution le m me p re les m mes priorit s etc que le processus appelant figure n 1 Une illustration de ce m canisme est donn e par l ex cution du programme essai c suivant Jean Luc Damoiseaux I S LT V 12 Syst me d Exploitation Les Processus include lt stdio h gt include lt stdlib h gt void main void execl bin ps ps al char 0 printf et maintenant je m arrete n return Au lancement du programme le processus essai est cr Ce processus de pid 867 occupe une taille m moire de 88Ko UID PID PPID CP PRI NI VSZ RSS WCHAN S TTY TIME COMMA 25 866 859 1 44 0 1 91M 392K pause S ttyp2 0 00 45 csh 25 867 866 0 44 0 1 22M 88K R ttyp2 0 00 01 essai Apr s l appel la primitive syst me execl on remarque que processus de pid 867 correspond maintenant l ex cution de la commande ps al taille m moi
2. Q T H Figure n 4 Structure physique du disque sous UNIX syst me V 3 3 1 Structure d un noeud d information Chaque i node figure n 5 est un bloc de 64 octets contenant des informations comme le l identit du propri taire le type et les droits d acc s au noeud pour les diff rents utilisateurs le nombre de liens physiques etc plus 13 adresses de blocs logiques 10 adresses directes 1 adresse indirecte simple 1 adresse indirecte double et 1 adresse indirecte triple i node taille 64 octets type et protection nb de liens propri taire groupe bloc de donn es longueur date heure derni r scriture lectur adressel adresse2 bloc de 128 bloc de 128 bloc de 128 pointeurs pointeurs pointeurs Figuren 5 Structure d un i node indirection bloc de 128 pointeurs simple 5 bloc de 128 bloc de 128 indirection pointeurs pointeurs double indirection triple Avec une telle structure les adresses des fichiers d au plus dix blocs sont toutes contenues dans le noeud d information Lorsque la taille d un fichier d passe les 10 blocs il suffit d attribuer un nouveau bloc du disque r f renc par un pointeur simple indirection pour des tailles de fichier importantes on utilisera les pointeurs double ou triple indirection L avantage d un tel m canisme est que quelque soit la taille du fichier la taille de son i node est constante En outre il ne faut
3. la droite gauche du philosophe de droite gauche est dans tat autre que R PA LLE La restitution de fourchettes s crit donc P mutex si etat gauche i ATTENTE alors etat gauche i lt RIPAILII V sempriv gauche i fin si si etat droite i ATTENTE alors etat droite i lt RIPAILII V sempriv droite i fin si V mutex et etat gauche gauche i RIPAILII et etat droite droite i RIPAILII En d finitive l algorithme d un philosophe i est le suivant sortir si Penser c est la Fin _du_ Repas Demander_Fourchettes i Manger Restituer_Fourchettes i fin iter 4 Les processus sous Unix 4 1 G n ralit s Un processus sous UNIX correspond un espace m moire compos de trois zones la zone syst me u area contenant des informations sur le processus cette zone est uniquement manipul e par le syst me la zone des donn es manipul es par le processus la zone d instructions le code du programme ex cut par le processus est stock 1C1 A chaque processus est associ un num ro d identification le pid Ce num ro attribu par le syst me permet de garder une trace de tous les processus et sert galement la synchronisation et la communication entre processus Jean Luc Damoiseaux I S I T V Syst me d Exploitation Les Processus Enfin chaque processus a un p
4. tandis que le tableau suivant r capitule le d roulement simultan de ces trois processus Processus et valeur de file d attente utilisation de la valeur de la instruction compte_utilise ressource ressource 900 francs 900 francs 900 francs Jean Luc Damoiseaux I S I T V 6 Syst me d Exploitation Les Processus 3 Synchronisation entre processus Dans le cadre de la r alisation d une t che par plusieurs processus il existe des relations qui fixent leur d roulement dans le temps L ensemble de ces relations est g n ralement d sign par le terme de synchronisation Le probl me de la synchronisation consiste donc d finir un m canisme permettant un processus actif d en bloquer un autre ou de se bloquer lui m me en attendant un signal d un autre processus d activer un autre processus en lui transmettant ventuellement de l information Deux techniques sont envisageables pour r soudre ce probl me de synchronisation l action directe qui consiste pour un processus agir sur un autre processus en le d signant par son identit On utilise g n ralement deux primitives ayant pour argument l identit du processus bloquer ou activer l action indirecte qui met en jeu non plus l identit du processus mais un ou plusieurs objets interm diaires connus des processus coop rants et manipulables par eux uniquement au travers de primitives sp cifiques 3 1 Synchronisation par s m
5. 3 4 2 Strat gie avec recyclage des travaux Les m thodes pr c dentes en se basant sur une estimation du temps d ex cution temps ventuellement faux ou falsifi et en allouant le processeur un processus durant tout ce temps sont peu adapt es aux conditions des syst mes conversationnels o les demandes sont nombreuses et fr quentes Les strat gies avec recyclage des travaux vitent ces inconv nients en interrompant au bout de quelques millisecondes le processus pour allouer le processeur un autre processus les processus interrompus sont plac s dans des files d attentes a Balayage cyclique ou tourniquet figure n 6 le processeur est allou successivement au processus et ce pour un temps d termin quantum si le processus ne s est pas termin au bout du temps imparti il est interrompu et remis en queue de la file d attente sortie Ye 11111111 gt Fr de entr e Figure n 6 Allocation du processeur par tourniquet Facile mettre en place cette m thode garantie que tout processus est servi au bout d un temps fini et limite le d lai de prise en compte d un processus b Recyclage plusieurs files d attentes figure n 7 les processus demandeurs sont rang s dans n files Q1 Q2 Qn ayant chacune un quantum qi sortie Processeur q2 dl entr e Figure n 7 Allocation du processeur par recyclage sur plusieurs files d attente Un processus situ en t te d une file d
6. dures r entrance simplifie la manipulation des donn es dont la taille varie dynamiquement limine les probl mes d ditions de liens et de compilation s par e Jean Luc Damoiseaux I S I T V 38 Syst me d Exploitation La m moire secondaire Chapitre 5 La m moire secondaire Dans un syst me d exploitation m moire hi rarchis e la m moire secondaire est un organe de stockage de grande capacit et de faible co t ceci relativement la m moire centrale appel e aussi m moire primaire Actuellement la m moire secondaire est constitu e essentiellement de supports magn tiques tels que les disques les tambours tant devenus obsol tes et les moyens futuristes disques optiques disques laser r inscriptibles etc n tant pas encore m rs L exploitation de cette m moire secondaire est une des fonctions essentielles d un syst me d exploitation D une part le syst me assure le contr le du disque et fournit une interface simple son utilisation d autre part il s occupe de son organisation notamment pour la gestion des fichiers 1 Etude du disque magn tique 1 1 Structure physique d un disque Un disque est compos de pistes concentriques elles m mes divis es en secteurs figure n 1 Bien que les secteurs situ s la p riph rie du disque soient plus grands que ceux situ s au centre le m me nombre d octets est utilis pour le stockage de l information sur tous les secteurs Chaque secteur est re
7. il doit obligatoirement r aliser l op ration Pmutex avant Deux cas se pr sentent le processus d cr mente d une unit la variable emutex et comme personne n utilise la ressource critique la valeur de mutex qui tait gale 1 passe O la proc dure Pmutex se termine z le processus d cr mente d une unit la variable emutex et comme un processus utilise la ressource critique la valeur de emutex devient ou reste n gative le processus demandeur est alors mis dans la file d attente fmutex et la proc dure Pmutex Se termine La lib ration de la ressource critique se fait obligatoirement par la proc dure Vmutex Deux cas se pr sentent le processus incr mente d une unit la variable emutex et comme personne d autre n a mis le d sir d utiliser la ressource critique la valeur de emutex qui tait gale O passe 1 la proc dure Vmutex se termine le processus incr mente d une unit la variable emutex comme d autres processus ont mis le d sir d utiliser la ressource critique la valeur de emut ex est n gative et l on sort donc de la file d attente l un des processus demandeurs pour le rendre actif la proc dure Vmutex se termine A titre d exemple nous reprendrons la gestion du compte client pour trois processus P1 P2 P 3 ex cutant le programme suivant derniere facture n P compte _ utilise DF compte_client compte_client derniere_facture V compte_utilise
8. le blocage intrins que pour un probl me de synchronisation Jean Luc Damoiseaux I S I T V 1 Syst me d Exploitation Les Processus Lorsque plusieurs processus existent en m me temps sur un m me syst me on dit qu ils sont parall les Il y a deux sortes de parall lisme le parall lisme vrai o n processus s ex cutent sur m processeurs architecture multiprocesseur le parall lisme simul o n processus s ex cutent sur un processeur qui est successivement attribu chacun des processus 1 3 Acc s aux ressources Une ressource est dite locale un processus s il est le seul pouvoir l utiliser une ressource locale dispara t la mort du processus Une ressource qui n est locale aucun processus est dite globale Une ressource est dite partageable avec n points d acc s si cette ressource peut tre attribu e au m me instant n processus au plus un fichier ouvert en lecture les commandes sous UNIX Une ressource partageable avec un point d acc s est dite critique processeur imprimante etc On appelle section critique d un processus la phase du processus pendant laquelle la ressource critique est utilis e par ce processus Un ensemble de processus peut soit entrer en comp tition pour l acc s une ressource soit fonctionner en coop ration pour mener bien une application Que l on soit dans une situation de parall lisme vrai ou simul les tranches d activit s des process
9. n ralement utilis es dans le traitement par lots Elles utilisent la valeur du temps d ex cution du processus valeur qui en g n ral est inconnue au moment de la demande du processus a File d attente simple FIFO le premier arriv est le premier servi on ne tient pas compte du temps d ex cution les travaux courts ont un temps de r ponse lev si ils passent apr s des travaux longs figure n 4 entr e sortie Processeur Figure n 4 Allocation du processeur par file d attente simple b File d attente ordonn e de mani re croissante suivant le temps estim d ex cution figure n 5 quand un processus arrive 1l est ins r l endroit correspondant son temps d ex cution les travaux courts sont avantag s et les longs toujours retard s entr e sortie Processeur Figure n 5 Allocation du processeur par file d attente ordonn e Cette strat gie peut tre combin e avec un syst me de priorit s croissantes avec le temps d attente et un temps limite d utilisation du processeur On peut galement introduire le Jean Luc Damoiseaux I S LT V 25 Syst me d Exploitation Gestion des Processus concept de pr emption quand un processus arrive son temps estim d ex cution est compar au temps estim restant pour le travail en cours s il est plus faible le travail en cours est interrompu et retourne sa place dans la file d attente tandis que le nouvel arrivant le remplace
10. processus q ex cute la primitive V signal alors le signal est m moris le s maphore passe 1 et lorsque le processus p ex cutera la primitive P signal il ne se bloquera pas 3 2 Probl me des Philosophes et des Spaghetti Il est possible de combiner l emploi des s maphores d exclusion mutuelle et des s maphores priv s pour r aliser des mod les de synchronisation plus complexes D une mani re g n rale d s qu un processus p pour poursuivre ou non son volution a besoin de conna tre la valeur de certaines variables d tat qui peuvent tre modifi es par d autres processus un processus q par exemple il ne peut les consulter que dans une section critique Comme il ne peut se bloquer l int rieur de celle ci le sch ma suivant est utilis P mutex modification et test des variables d tat si on peut continuer alors V sempriv fin si V mutex P sempriv S1 le test des variables d tat indique que le processus p peut continuer alors en ex cutant l op ration V sempriv il se donne un droit de passage et la sortie de la section critique il ne se bloquera pas sur l op ration P sempriv Dans le cas contraire l op ration V sempriv est saut e et le processus p se bloque la sortie de sa section critique sur l op ration P sempriv puisque le s maphore tait initialis 0 L activation par un autre processus le processus q par exemple s crit P mutex modification et test des
11. programmation consid r et dont l ex cution peut tre complexe Une instruction est consid r e comme ind composable indivisible c est dire que l on s interdit d observer le syst me pendant l ex cution d une instruction Le processeur est l entit c bl e ou non capable d ex cuter une instruction Un processus est un programme en cours d ex cution Un processus est d fini par le code et les donn es du programme son contexte d ex cution vecteur d tat savoir les informations qu il utilise explicitement variables proc dures ressources etc et les informations utilis es par le syst me pour g rer l attribution des ressources contenus des registres CI RI etc la taille m moire utilis e ressources mat rielles utilis es Il est important de se rappeler que le vecteur d tat d un processus ne peut tre observ pendant l ex cution d une instruction 1 2 Ressource tat d un processus Une ressource est une entit pouvant servir l ex cution d un travail Des exemples de ressources sont les organes de la machine unit centrale m moire centrale p riph riques un fichier des donn es etc Un processus est dans un tat bloqu s il lui manque la ou les ressources n cessaires l ex cution de sa prochaine instruction dans le cas contraire le processus est dit actif Habituellement on distingue deux types de blocage possibles le blocage technologique pour l absence de ressources
12. re dont le num ro d identification est donn par le ppidl Cette notion de parent entre processus appara t d s lors qu un processus A lance un processus B le processus A tant le p re du processus B et le processus B tant bien videmment le fils du processus A Ainsi sur l exemple suivant obtenue par la commande ps UID PID PPID CP PRI NI VSZ RSS WCHAN S TTY TIME COMMA 25 966 959 1 44 0 1 91M 384K pause S ttyp2 0 00 45 csh 25 967 966 0 44 0 1 22M 88K wait I ttyp2 0 00 01 essai il apparait que le processus essai pid 967 ppid 966 est le fils du processus csh pid 966 Il existe deux fonctions C qui permettent un processus de conna tre son pid et celui de son p re Ces deux primitives sont int getpid void int getppid void La fonction getpid renvoie le num ro d identification du processus appellant et la fonction getppid renvoie le num ro d identification du p re du processus appellant 4 2 Cr ation de processus 4 2 1 La fonction system La fonction system est le premier des m canismes permettant un processus de cr er un autre processus Inclus dans le fichier ent te stdlib h le prototype de cette fonction est le suivant void system char commande et sa r alisation a pour effet d ex cuter la commande donn e en argument le processus appelant tant interrompu jusqu la fin de l ex cution de la commande Par exemple apr s avoir compil et ex cut en arri re pla
13. attente Q ne sera pris en compte que si toutes les files pr c dentes sont vides un processus appartenant la file Q et n ayant pas termin sera Jean Luc Damoiseaux I S LT V 26 Syst me d Exploitation Gestion des Processus plac en queue de la file Q Les processus sortant de Q y retournent Enfin tout processus arrivant dans Q est pris en compte d s que le processeur est libre Cette strat gie pr sente les m mes avantages que la strat gie du tourniquet avec en plus des ajustements plus souples 3 4 3 Strat gie fond e sur la notion de priorit La priorit est un nombre attribu chaque processus et d finissant le degr d urgence de son d roulement La priorit peut tre d finie par le programmeur ou modul par le distributeur Toutes les strat gies d crites pr c demment peuvent int grer cette notion de priorit Ainsi une file peut tre constitu en ordonnant les processus selon leur priorit plusieurs files de processus de m me priorit peuvent tre r alis es Dans les strat gies avec un recyclage on peut imaginer que la priorit d un processus diminue apr s chaque quantum allou ce travail Jean Luc Damoiseaux I S LT V 27 Syst me d Exploitation Allocation de la m moire Chapitre 4 Allocation de la m moire L ex cution d un processus demandant que le code du programme et les donn es utilis es soient pr sents en m moire cette derni re est une ressource essentielle du
14. entr es sorties effectuait les transferts son rythme puis pr venait l unit centrale de la fin de son travail les concepts d interruptions et de m moire tampon furent introduits ce moment A cette m me poque afin d augmenter le rendement de l UC lorsque celle ci tait bloqu e dans l attente d informations ext rieures ou par une saturation des tampons d entr es sorties le concept de multiprogrammation naquit Lorsqu un programme tait bloqu en attente d une entr e sortie le processeur lui tait retir au profit d un autre programme qui pouvait alors s ex cuter le programme retir tait plac dans une file d attente Cette technique de la multiprogrammation n cessita d une part l utilisation de circuits sp cialis s dans la protection d une tache par rapport aux autres et d autre part la mise en place de techniques d ordonnancement des travaux de partage de la m moire et du processeur Malgr l utilisation de ce cette technique on souhaita augmenter le temps de r ponse pour chaque utilisateur et on introduisit alors dans la multiprogrammation la notion de temps partag Un programme en cours d ex cution pouvait perdre l unit centrale soit pour des besoins d entr es sorties soit parce qu il tait d j rest suffisamment longtemps actif quantum de temps intervalle de temps r guliers une horloge produit une interruption dont le traitement donne l unit centrale au programme suivant A noter
15. les entr es sorties sont r alis es par blocs et transitent par des caches du syst me et les fichiers sp ciaux caract res les entr es sorties sont r alis es caract res par caract res et ne transitent pas par les caches du syst me A ces diff rents types de fichiers s ajoutent galement les tubes nomm s les sockets et les liens symboliques 3 3 Organisation du disque L exploitation du ou des disques physiques par le syst me se fait gr ce une organisation logique de l espace de donn es de ce s disque s Un disque physique est ainsi d coup en plusieurs disques logiques r partis dans les deux cat gories suivantes les disques de swap ils servent la sauvegarde des contextes de processus ou des pages sorties momentan ment de la m moire les syst mes de gestion de fichiers caract ris s par leur type qui est soit System V soit ffs ufs BSD L organisation System V est la suivante un bloc de d marrage utilis au chargement du syst me le super bloc contenant des informations g n rales sur le syst me nombre de noeuds allou s et libres liste de blocs libres etc la table desi nodes et le bloc des donn es qui est d coup en blocs logiques allouables de taille 512 1024 2048 ou 4096 octets figure n 4 Jean Luc Damoiseaux I S I T V 46 Syst me d Exploitation La m moire secondaire Bloc des donn e Bloc de d marrag Super bloc 0 TD le G l 4 n 0 TD n 0
16. me qui aura la charge de faire transiter les processus d un tat l autre 3 2 Le distributeur Le distributeur scheduller en anglais est la partie du syst me d exploitation charg e de veiller la bonne attribution du processeur au cours du temps Son r le consiste d une part s lectionner en fonction d une certaine strat gie le processus qui il attribuera le processeur d autre part retirer apr s un certain temps d utilisation ou en fonction d v nements sp cifiques E S demande d une ressource etc le processeur au processus L acquittement de cette t che devra se faire en respectant les contraintes suivantes la garantie chaque processus d un temps donn d allocation le respect d un ordre de priorit entre les processus demandeurs l ex cution totale d un processus Jean Luc Damoiseaux I S LT V 23 Syst me d Exploitation Gestion des Processus la mise l cart d un processus utilisant le processeur pendant un temps sup rieur au maximum fix par le programmeur ou le syst me 3 3 Changement de contexte entre deux processus L op ration qui consiste pour le distributeur retirer le processeur un processus pour l attribuer un autre s appelle le changement de contexte Dans le cas d un changement de contexte entre le processus actif A et un processus demandeur B cette op ration peut se d composer ainsi le distributeur interrompt le processus A il sauv
17. nient Un tube ou pipe symbolis par le caract re permet de rediriger la sortie d un processus sur l entr e d un autre Ainsi lors de la construction d une fonction complexe chaque traitement modifiera directement les r sultats du traitement pr c dent La syntaxe de ce mode de communication pour n processus est la suivante processus lprocessusz l lprocessus Jean Luc Damoiseaux L S LT V 11 Syst me d Exploitation G n ralit s ainsi la sortie du processus est directement connect e sur l entr e du processus qui lui m me voit sa sortie reli e l entr e du processus etc 3 4 Quelques commandes UNIX met la disposition d un utilisateur plus de 200 commandes Une commande est consid r e comme une suite de mots s par s par des blancs et peut tre d compos e comme suit nom_commande option parametre o apr s le nom de la commande on trouvera ventuellement la ou les options qui influenceront son ex cution suivis du ou des param tres sur lesquels elle agit Voici pour terminer quelques commandes faisant partie de la vie courante de l utilisateur du syst me UNIX passwd permet de changer le mot de passe de son login man sujet apporte une aide en ligne sur le sujet choisi date affiche la date et l heure courante echo arguments affiche sur la sortie standard le ou les arguments ps fournit des informations sur les processus du syst me z who affiche la lis
18. noyau et l utilisateur Il existe plusieurs interpr teurs de commandes les plus connus sont le Bourne Shell le premier historiquement le C Shell et le Korn Shell Quelque soit le shell utilis celui ci analyse la commande tap e au clavier par l utilisateur value le cas ch ant les caract res sp ciaux gt lt etc v rifie que la commande existe et assure son ex cution par la cr ation d un processus ad quat Une fois la commande ex cut e le contr le reviendra alors au Shell qui relancera le dialogue La derni re couche regroupe quant elle divers utilitaires des applications usuelles des logiciels de gestion de base donn e des interfaces graphiques etc 3 2 Les fichiers sous UNIX Au niveau physique le syst me UNIX consid re un fichier comme une suite non structur e d octets et lui associe un num ro unique appel i node Au niveau logique UNIX distingue trois types de fichiers les fichiers ordinaires comme les documents et les programmes 2 les fichiers sp ciaux comme les p riph riques les disques etc ces fichiers sp ciaux travaillent soit en mode caract re soit en mode bloc les r pertoires ou catalogues qui contiennent des informations sur d autres fichiers 3 2 1 Acc s un fichier Avant de d finir l acc s un fichier il convient de pr ciser une notion importante qui est celle de r pertoire Un r pertoire est un fichier sp cial qui contient le nom d autres
19. ou physiques rencontr es 1 2 1 Les algorithmes d ordonnancement du bras Les temps de lecture ou d criture d un bloc d pendent essentiellement des trois facteurs suivants le temps de recherche temps n cessaire pour positionner la t te de lecture sur le bon cylindre le temps de rotation temps n cessaire pour positionner la t te de lecture sur le bon secteur le temps de transfert temps n cessaire pour transf rer le bloc du disque dans la m moire du p riph rique En fait le temps de recherche tant le plus important sa r duction entra nera une am lioration sensible des performances du syst me Aussi il existe plusieurs algorithmes d ordonnancement du bras visant r duire ce temps de recherche figure n 2 Les principaux sont FCFS first come first served premier arriv premier servi le pilote satisfait les requ tes dans leur ordre d arriv e Tr s simple mettre en oeuvre cet algorithme est aussi le moins performant SATF shortest acces time first le d placement le plus court le pilote satisfait les requ tes concernant le cylindre le plus pr s de la position actuelle du bras puis se d place dans un sens ou dans l autre vers le cylindre le plus proche comportant des requ tes satisfaire Simple mettre en oeuvre cet algorithme est g n ralement deux fois plus performant que le pr c dent Toutefois comme une demande concernant un cylindre loign du cylindre co
20. pipe et dup la table des fichiers ouverts pour chaque fichier ouvert on y trouve en autres choses le nombre de descripteurs associ s le mode d ouverture la position courante et un pointeur sur le i node correspondant Une entr e dans cette table est obtenue lors de l utilisation des primitives open et pipe la table des i noeuds pr sents en m moire Pour chaque i node charg en m moire en plus des informations pr sentes sur le disque on trouve galement dans cette table des informations comme le nombre d ouvertures sur le fichier le disque logique auquel appartient le i node etc Jean Luc Damoiseaux I S LT V 48 Syst me d Exploitation La m moire secondaire Tables des Table des descripteurs i noeuds en m mo Table des fichiers ouverts compteurs de mode pointeur sur lt offset descripteurs ouverture i noeud Figure n 6 Organisation du syst me de gestion de fichiers Jean Luc Damoiseaux I S I T V 49 Syst me d Exploitation Bibliographie 1 2 Bibliographie Syst mes d exploitation UNIX Andrew Tanenbaum Les Syst mes d Exploitations InterEditions 1991 Architecture des Syst mes d Exploitations Michael Griffiths Michel Vayssade Hermes 1988 La programmation sous UNIX Jean Marie Rifflet Ediscience 1993 Programmer UNIX Richard Stoeckel Armand Colin 1992 UNIX Initiation et Utilisation Jean Paul Armspach Pierre Colin InterEditions 1994 Le syst me UNIX St
21. rable de disposer de plusieurs espaces m moires virtuels appel s des segments qui seront logiquement associ s des entit s d un seul type on parlera de segment des tables de symbole de segments proc dure de segments des constantes etc figure n 10 Jean Luc Damoiseaux I S LT V 37 Syst me d Exploitation Allocation de la m moire segment 0 segmentl segment 2 des symbole constante a F 8 a E des segments space m moir segment n r el space m moir virtuel Figure n 10 Principe de la segmentation Un segment est constitu d une suite lin aire d adresses virtuelles num rot es de z ro une valeur maximum la taille d un segment variant dans cet intervalle Chaque segment a donc son propre espace d adressage dans lequel les adresses virtuelles commencent z ro et n ont aucune relation d ordre d un segment l autre Pour sp cifier une adresse virtuelle dans une m moire segment e il est n cessaire de disposer d un num ro de segment n et d un d placement d dans le segment Lors de la traduction de l adresse virtuelle si le segment r f renc n est pas pr sent en m moire il sera alors charg depuis la m moire secondaire Contrairement la pagination la segmentation de l espace m moire r el est une technique qui doit tre connue du programmeur et ou du compilateur De ce fait la segmentation assure une grande protection de l information permet le partage de donn es et de proc
22. rable de travailler avec des pages de grande taille Afin d am liorer le rendement du m canisme de pagination il est souvent associ chaque entr e de la table des pages les informations suivantes un bit d invalidit qui lorsqu il est positionn 1 indique que a page virtuelle n est pas d j pr sente dans l espace r el des bits d utilisation qui permettent de conna tre l usage qui est fait de la page lecture criture des bits de protection qui indiquent si la page peut tre lue crite ex cut e 3 2 2 Le remplacement de pages Lorsqu un processus r f rence une page virtuelle absente de l espace m moire r el on dit q on a un d faut de page Le traitement d un d faut de page est r alis par le syst me qui avant de charger la nouvelle page virtuelle devra commencer par lib rer de la place dans l espace m moire r el en renvoyant en m moire secondaire une page r elle L algorithme qui consiste choisir la page renvoyer s appelle l algorithme de remplacement De nombreuses tudes ont t r alis es et elles se distinguent essentiellement par les informations prises en compte et relatives l utilisation pass e des pages Voici les principaux algorithmes de remplacement de page le tirage al atoire RAND la page ject e est choisie au hasard ordre chronologique de chargement FIFO la page ject e est la page la plus anciennement charg e ordre chronologique d
23. syst me d exploitation Sa gestion en est confi e un allocateur qui l attribuera tout ou partie au x processus demandeur s L objet de ce chapitre est donc l tude de l allocation de la ressource m moire au sein d un syst me d exploitation 1 D finitions 1 1 Espace m moire r el espace m moire virtuel Lorsqu un processus s ex cute il r f rence un ensemble de ressources situ es dans un espace m moire de travail et ceci sans se pr occuper de savoir quelle adresse physique de la m moire principale se trouvent ces ressources Cet espace m moire de travail par opposition la l espace m moire r el est appel l espace m moire virtuel dans l espace m moire virtuel les adresses m moires sont dites virtuelles 1 2 M moire virtuelle La m moire virtuelle est l ensemble des m canismes qui permettent d tablir la correspondance entre l espace m moire virtuel et l espace m moire r el figure n 1 Y M moire Espace m moire physique Espace m moire virtuel Figure n 1 Principe de la m moire virtuelle La m moire virtuelle assure comme fonctions la mise en correspondance entre les adresses virtuelles et les adresses physiques la gestion de l espace m moire r el allocation des emplacements transfert de l information le partage de l information entre processus Jean Luc Damoiseaux I S LT V 28 Syst me d Exploitation Allocation de la m moire la protection de
24. un appel cette fonction puis reprendra le cours de son ex cution l endroit m me o il l avait quitt un signal permet donc de r aliser un appel de fonction alors qu il n a pas t explicitement programmer La mise en place de ce Jean Luc Damoiseaux I S I T V 16 Syst me d Exploitation Les Processus m canisme dynamique de d routement est obtenue par la fonction signal dont le prototype est le suivant void signal int sig void p_ traitement int int o p_traitement sera initialis soit avec l une des constantes symboliques SIG_DFL et SIG_IGN soit avec l adresse de la fonction associ e au traitement du signal sig Le prototype de cette fonction est le suivant void traitement int sig Une fois le signal capt et trait le traitement associ au signal reste toujours en place sauf sur les versions ATT d UNIX o le comportement par d faut est r activ Attente d un signal Enfin la suspension d un processus dans l attente d un signal est r alis par la fonction pause dont le prototype est le suivant int pause void A la d livrance du signal le processus ex cutera le traitement pr vu Exemple A titre d exemple voici le changement du comportement par defaut d un processus lors de la r ception d un signal Ici notre processus au lieu de s arr ter imm diatement la r ception du signal SIGINT s arr tera seulement apr s en avoir capt 5
25. utilisateurs usr bin contient d autres utilitaires UNIX usr lib contient d autres biblioth ques utilis es par des langages de programmation usr include contient les fichiers d en t te des langages du syst me UNIX usr spool contient les fichiers n cessaire la gestion des imprimantes T T T T l bin dev etc usr lib tm bin include LI spool Figure n 3 Structure conventionnelle du syst me de gestion de fichiers d UNIX Jean Luc Damoiseaux I S LT V 45 Syst me d Exploitation La m moire secondaire 3 2 Les types de fichiers L une des caract ristiques du syst me de gestion de fichiers d UNIX est la grande vari t des types de fichiers On y retrouve principalement les fichiers ordinaires le contenu de ces fichiers est non structur ce qui fait d eux des suites d octets caract ris s uniquement par leur longueur Aucune interpr tation binaire ou texte et aucune organisation s quentielle directe index e ne sont associ es ces fichiers les applications sont donc libres de les traiter comme elles le souhaitent s les r pertoires les fichiers sp ciaux ils sont associ s des dispositifs physiques comme les imprimantes la m moire les disques etc Ces fichiers sont trait s comme les fichiers ordinaires mais les op rations de lecture ou d criture active des dispositifs physiques particuliers A un niveau plus fin on distingue les fichiers sp ciaux en mode bloc
26. variables d tat suivi ventuellement d une op ration V sur le s maphore priv sempriv V mutex Jean Luc Damoiseaux I S I T V 8 Syst me d Exploitation Les Processus Etudions maintenant ces sch mas au travers de l exemple des Philosophes et des Spaghetti Cinq philosophes se r unissent au cours d un repas au menu des spaghetti Les philosophes tant des hommes aussi ils ne peuvent penser et manger en m me temps et doivent donc alterner ces deux activit s Selon leur savoir vivre les spaghetti se mangent avec deux fourchettes et malheureusement le restaurateur n a pr vu qu une fourchette par personne Pour r soudre ce probl me ils d cident d adopter le rituel suivant chaque philosophe ne quittera pas sa place pendant le repas afin de ne pas se pencher au dessus de la table un philosophe pour manger utilisera les fourchettes situ es sa droite et sa gauche m me s il adore les spaghetti un philosophe doit manger raisonnablement 1 e pendant un temps limit m me s il a tr s faim un philosophe ne doit pas s emparer d une fourchette si l autre est prise au d but du repas tous les philosophes penseront Il s agit donc d laborer un m canisme de synchronisation qui permettent aux cinq philosophes processus de manger leur faim Les philosophes jouant le m me r le le m canisme de synchronisation sera identique pour tous L tat d un philosophe i est caract ris par une v
27. vue du cot de l utilisateur et ou les couches hautes du syst me de gestion de fichiers La structure logique d un fichier peut tre une suite d octets une suite d enregistrements de taille fixe chaque enregistrement tant constitu de champs de nature diverse on peut lire ou crire n importe quel enregistrement mais on ne peut pas ins rer ou d truire un enregistrement au milieu de la liste une arborescence de blocs du disque chaque bloc contenant n enregistrements index s l acc s aux enregistrements se fait par une cl et on peut ins rer un bloc n importe quel niveau de l arbre Les modes d acc s un fichier d pendent du type du fichier Pour les fichiers ordinaires il est possible de r aliser plusieurs types d acc s au fichier l acc s s quentiel on acc de une composante la suite de l acc s la composante pr c dente l acc s relatif ou directe on acc de une composante quelconque identifi e par son rang dans le fichier l acc s index on acc de une composante quelconque par la valeur d un de ces champs 2 1 2 Les types de fichiers La plupart des syst mes d exploitations poss de plusieurs types de fichiers Les principaux types de fichiers sont les fichiers ordinaires ils sont constitu s par les donn es et les programmes des utilisateurs les r pertoires ils constituent le moyen de hi rarchiser logiquement l ensemble des fichiers L
28. 6H d enseignement l IS LT V sur les syst mes d exploitations Ce polycopi n est toutefois pas un v ritable cours sur les syst mes d exploitation car seules les notions les plus importantes et les plus accessibles y sont trait es A chaque fois que cela sera possible un lien avec le syst me UNIX sera r alis et ce titre ce polycopi servira de support aux travaux pratiques sur UNIX Enfin les plus int ress s par cette mati re pourront consulter avec profit les nombreux ouvrages existant sur le domaine et notamment ceux cit s dans la bibliographie Jean Luc Damoiseaux L S LT V 4 Syst me d Exploitation G n ralit s Chapitre 1 G n ralit s Supposons que l ordinateur ex cute le programme suivant void main void G ar c getchar putchar c return et demandons nous ce que fait celui ci pour afficher le caract re tap au clavier Notre programme en arrivant sur l instruction getchar fait appel au syst me d exploitation pour l informer qu il attend un caract re au clavier Le syst me d exploitation interrompt donc notre programme et lance un programme capable de lire sur l unit d entr es sorties correspondant au clavier Lorsque l on frappe sur une touche du clavier le code correspondant la lettre tap e est envoy par le clavier l ordinateur Une fois capt et stock par le circuit lectronique g rant la communication entre le clavier et l ordinateur le progr
29. Les s maphores sont une des solutions les plus l gantes au probl me de l exclusion mutuelle Un s maphore s est constitu d une variable e et d une file d attente fs Lors de la cr ation du s maphore e re oit une valeur positive ou nulle et s est vide On ne peut agir sur un s maphore qu au travers des deux primitives indivisibles suivantes es lt es 1 si es lt 0 alors etat lt bloqu r processus ex cutant cette primitive mettre le processus r dans la file fs fin si es lt es 1 si es 0 alors sortir un processus q de la file F4 etatq lt actif fin si Un s maphore est donc un dispositif qui th saurise un certain nombre d autorisation de passage es est ce nombre et qui g re une file de processus en attente de passer L op ration Ps correspond une demande de passage tandis que l op ration Vs est une autorisation de passage Afin de ne pas retomber dans les travers pr c dents le syst me devra pour un s maphore s assurer l exclusion mutuelle de es et fs ainsi que l indivisibilit des proc dures Ps et Vs L exclusion mutuelle sera r alis e gr ce un s maphore appel mutex mutuelle exclusion initialis ainsi et utilis comme ceci Pmutex instructions formant la section critique Vmutex Jean Luc Damoiseaux I S I T V 5 Syst me d Exploitation Les Processus Comme on peut le constater d s lors qu un processus d sire utiliser une ressource critique
30. Syst me d Exploitation LS LT V SYSTEME D EXPLOITATION J L DAMOISEAUX Jean Luc Damoiseaux L S LT V 1 Syst me d Exploitation Table des mati res Tables des mati res Avertissements is atesn este a sde dascesesss entend t s e sde etes code devet anse D Chapitre 1 G n ralit s ceccocccoccoccoocc0c0000c000000000000000000000000000000000000000000000000000000000000000000 D 1 Historique des syst mes d exploitations 5 2 Fonctions d un syst me d exploitatiON ccccciiicciicccicciccccccceciccscccccccescccssecesenes 7 3 L syst me UNIX T ra nee ne R E eG A Td ane NE G n ane 7 3 1 Pr sentation et Structure du syst me UNIX 8 3 2 Les fichi rs sous UNIX 3 Sn 0 DA i AE Ends 9 3 3 La redirection des entr es SONrtieS cciccciccicssccsicsscssccsscsscssocsasscnaonas 11 3 4 Quelques commandes irris ose Era Ea anttsiee 12 Chapitre 2 Les ProcessUs co0cco0cc000c0000000000000000000000000000000000000000000000000000000000000000000000000000 L Vrt D MOS en e a E aa TS Ea A ERa E nE reaS 1 1 1 Instructions processeur processus LE Ne nn ne 1 1 2 Ressource tat d Un PrOCESSUS russere nace s E EEK ie ai 1 1 3 ACC S AUX TESSOUTCES nn nt nie ain int Nan dan tient nine 2 2s M XCHSION MUTUEL St ne a Se nn Tc Ness 2 2 1 Attente ACIVE 123520 IG ES T ARS EN a ee RS Sn SS T Ne 4 2 2 Les s maphor Senini AE EE EE E A 00064 5 3 Synchronisation entre process
31. Voici le code ex cut par notre processus include lt signal h gt int c 0 void capte int sig printf Aie GET if c gt 5 printf j en ai marre bye byeln exit 0 return l on me reveille n void main void signal SIGINT capte for printf je dors n sleep 5 return La fonction capte incr mente la variable c et lorsque sa valeur sera sup rieure 5 le programme s arr tera Cette fonction est associ e gr ce la fonction signal au traitement Jean Luc Damoiseaux I S LT V 17 Syst me d Exploitation par d faut du signal S Les Processus G NT ce qui implique que chaque fois que le processus recevra ce signal un appel la fonction capte sera imm diatement r alis Le programme principal de ce processus est une boucle infinie dans laquelle le processus affiche je dors avant de s endormir r ellement pendant 5 secondes fonction sleep Jean Luc Damoiseaux I S LT V Syst me d Exploitation Gestion des Processus Chapitre 3 Gestion des processus Dans le chapitre pr c dent nous avions trait les diff rents m canismes mettre en oeuvre soit pour prot ger des informations partag es entre plusieurs processus exclusion mutuelle soit pour permettre plusieurs processus de coop rer un m me but synchronisation L tude des processus tant fondamentale pour la compr hension d un
32. ace m moire r el un processus ne peut pas disposer d un espace m moire virtuel de taille sup rieure l espace m moire r el plus les processus sont nombreux moins ils disposent de place L utilisation d une m moire hi rarchis e r sout ces probl mes en multiplexant l espace m moire r el 3 1 Le Va et Vient Swapping La m thode du Va et Vient consiste vider sur une unit secondaire le contenu de la zone de l espace m moire r el attribu e un processus pour ensuite utiliser cette zone pour un autre processus lorsque l on d cide de reprendre l ex cution du premier processus il faut recharger les informations n cessaires en m moire centrale 2Bien que Window 95 change consid rablement les choses Jean Luc Damoiseaux I S LT V 30 Syst me d Exploitation Allocation de la m moire Que cette technique soit utilis e dans le cadre d un partitionnement fixe ou variable de l espace m moire r el deux probl mes se posent moins de disposer d un m canisme de r implantation dynamique la r activation d un processus interrompu implique qu on le replace au m me endroit ce qui peut entra ner le vidage de plusieurs autres processus il est n cessaire de m moriser en permanence l occupation de l espace m moire r el 3 1 1 Gestion de l espace m moire r el par table de bits Une premi re solution pour la gestion de l occupation de l espace m moire r el consiste utiliser une ta
33. aire toute demande nouvelle il est alors n cessaire de compacter la m moire Ce compactage se traduit par un d placement de toutes les zones allou es vers une extr mit de la m moire ce qui fait appara tre une zone libre dont la taille est la somme des tailles des zones libres primitives figure n 7 inutilis Figure n 7 Compactage de l espace m moire r el Cette m thode tr s co teuse en temps n est pas toujours applicable notamment lors de l absence de m canisme de r implantation dynamique Par ailleurs des simulations ont montr que lorsque l algorithme d allocation ne peut satisfaire une demande alors le taux de remplissage de l espace m moire r el est tel que m me apr s un compactage on retombera tr s vite dans la situation pr c dente le syst me passe alors son temps compacter la m moire Jean Luc Damoiseaux I S LT V 34 Syst me d Exploitation Allocation de la m moire 3 2 La pagination La pagination est un m canisme de mise en correspondance d un espace m moire virtuel lin aire avec un espace m moire r el discontinu Ce mode d allocation est certainement le plus courant sur bon nombre de machine Le principe de la pagination consiste d une part d couper l espace m moire virtuel en zones de taille fixe appel es pages virtuelles et l espace m moire r el en pages physiques de m me taille et d autre part utiliser un m canisme la table de pages assurant la correspondance en
34. amme charg de la lecture est inform que la donn e est disponible A ce moment l une copie de ce code est r alis e puis transmise syst me d exploitation Celui ci r active alors notre programme en lui fournissant le code du caract re Notre programme passe la seconde instruction qui consiste afficher ce caract re et un m canisme semblable sera mis en route pour afficher le caract re l cran Chacune de ces tapes pourrait tre d crite d une mani re encore plus pr cise Ainsi pour lancer le programme de lecture du clavier le syst me d exploitation d termine dans une table l adresse sur le disque du programme en question Puis il assure la rotation du disque positionne la t te de lecture cette adresse et transf re en m moire la suite de O et de 1 composant le fichier Enfin apr s avoir charg le contexte d ex cution du programme le syst me d exploitation lui donne la main et celui ci peut alors s ex cuter Comme le laisse entrevoir cet exemple le syst me d exploitation intervient de mani re coh rente tous les niveaux du fonctionnement d un ordinateur Aux deux extr mit s il interagit d une part avec le mat riel le temps d interaction est alors de quelques milliardi mes de seconde et d autre part avec l utilisateur le temps d interaction est de quelques secondes Le r le d un syst me d exploitation est donc de r duire et de dominer la complexit de la machine afin d en faciliter l usag
35. aphores priv s La synchronisation par s maphore priv s est un m canisme d action indirecte Un s maphore s est un s maphore priv d un processus p si seul ce processus peut ex cuter l op ration P s les autres processus pouvant agir sur le s maphore s uniquement par l op ration V s La synchronisation par s maphore priv pose alors comme principe qu un signal d activation sera envoy par la primitive V et attendu par la primitive P Ainsi un processus dont l volution d pend de l mission d un signal par un autre processus se bloque au moyen d une primitive P derri re son s maphore priv initialis z ro Le signal de r veil de ce processus bloqu est obtenu en faisant ex cuter par un autre processus une op ration V sur le m me s maphore Jean Luc Damoiseaux I S LT V 7 Syst me d Exploitation Les Processus Par exemple soit p un processus dont l volution d pend de l mission d un signal envoy par un processus q en introduisant le s maphore signal initialis z ro la solution du probl me se programme comme suit processus p processus q debut debut Tir LPF 4 ID Fi VISOR ir Tr P signal V signal Deux situations sont possibles le processus p est d j bloqu sur la primitive P signal lorsque le processus q ex cute la primitive V signal alors le r veil devient effectif le processus p est actif il ex cute par exemple l instruction Ip lorsque le
36. ariable le philosophe i pense le philosophe i voudrait manger mais il lui manque des fourchettes lorsque le philosophe i mange Pour un philosophe i le passage de l tat REFLEXION l tat RIPAILLE n est possible d apr s l hypoth se 2 que si les philosophes situ s sur sa droite et sur sa gauche sont dans un tat diff rent de RIPAILLE Si cette condition n est pas r alis e le philosophe i passe dans l tat ATTENTE cette transition sera r alis e gr ce un s maphore priv semprivlil initialis 0 La demande de fourchettes s crit donc P mutex si etat gauche i RI E et etat droite i RIPAILLI alors etat i lt RIPAILL V sempriv i sinon etat i lt ATT fin si V mutex P sempriv i Naturellement le test et l affectation des variables d tat constituent des sections critiques prot g es par un s maphore d exclusion mutuelle not mutex Jean Luc Damoiseaux I S I T V 9 Syst me d Exploitation LLE l tat REFLEXI Pour un philosophe i le passage de l tat RIPA des philosophes situ s sa droite et sa gauche si les conditions suivantes sont remplies d une part ces deux derniers sont dans l tat ATTENTE Les Processus ON entra ne le r veil d autre part on est s r qu ils disposeront de deux fourchettes c est dire que le philosophe situ
37. au plus que trois acc s disques pour trouver l adresse de n importe quel octet d un fichier Jean Luc Damoiseaux I S LT V 47 Syst me d Exploitation La m moire secondaire 3 3 2 Structure d un r pertoire La structure d un r pertoire UNIX est simple Un r pertoire est une table o chaque entr e contient un nom de fichier et le num ro de son noeud d information Un r pertoire UNIX peut contenir un nombre quelconque de ces entr es cod es sur 16 octets Pour trouver un fichier il suffit pour le syst me d encha ner la lecture du r pertoire et de la table des noeuds 3 3 3 Structure du syst me de gestion de fichiers La gestion des fichiers sous UNIX est principalement r alis e par l interm diaire de trois tables figure n 6 les tables de descripteurs chaque processus en poss de une table de descripteur et la manipulation d un fichier se fera par un indice un descripteur dans cette table un descripteur correspond dans la table les attributs dynamiques du fichier fermeture en cas de recouvrement etc plus un pointeur sur la table des fichiers ouverts Il est important de se rappeler que les trois premiers indices de cette table sont r serv s pour l entr e standard la sortie standard et la sortie d erreur standard Enfin un processus acquiert un descripteur soit par h ritage une recopie de la table des descripteurs de son p re est r alis e sa naissance soit par l utilisation des primitives open
38. ble de bits figure n 3 Syst me d exploitation Figure n 3 M morisation de l tat d occupation de la m moire par une table de bits l espace m moire r el est divis en unit s d allocation de taille fixe quelques mots plusieurs Koctets selon les syst mes et chaque unit correspond dans une table de bits un bit dont la valeur est O si l unit est libre et 1 sinon D une mise en place rapide cette technique relativement peu gourmande en place est lente l ex cution En effet lors de l introduction d un processus dont la taille est k unit s d allocation il est n cessaire de trouver dans la table k bits cons cutifs z ro ce qui est tr s difficile 3 1 2 Gestion de l espace m moire r el par liste cha n e Une deuxi me solution pour la gestion de l occupation de l espace m moire r el consiste utiliser une liste cha n e des zones libres et ou occup es figure n 4 Les informations composant la liste peuvent tre plac es soit dans un espace m moire r serv chaque maillon contient par exemple un pointeur vers la zone libre une indication de taille et le s lien s de cha nage soit dans la zone libre elle m me un en t te plac au d but de chaque espace libre tablit le lien avec la zone libre suivante Jean Luc Damoiseaux I S LT V 31 Syst me d Exploitation Allocation de la m moire Syst me d exploitation Figure n 4 M morisation de l tat d occupation de la m
39. cela il existe plusieurs m canismes acc l rateurs comme les m moires caches les m moires associatives etc dans lesquels on m morise g n ralement les num ros des pages les plus fr quemment utilis es La traduction d une adresse consiste alors consulter d abord ces m moires la consultation de la table n ayant lieu que si le num ro de page virtuelle ne s y trouve pas Jean Luc Damoiseaux I S LT V 35 Syst me d Exploitation Allocation de la m moire Les tailles des pages choisies par les constructeurs sont en g n ral du m me ordre de grandeur de 512 4096 octets Ce choix est motiv par les consid rations suivantes le ph nom ne de fragmentation interne des pages est courant dans la mesure o l on charge pour des raisons d efficacit ou de protection un programme ou des donn es t te des pages De plus statistiquement la derni re page virtuelle n est occup e moiti Donc plus la taille des pages est r duite plus la fragmentation l est la taille de la table des pages est proportionnel au nombre de pages de l espace m moire virtuel Il est donc pr f rable d avoir des pages de grande taille pour r duire la taille de la table ce qui permet de la placer dans des registres ou dans une m moire cache d o un gain de temps le temps de lecture d une page sur la m moire secondaire est pratiquement proportionnel temps de positionnement de la t te de lecture Pour r duire ce temps il est pr f
40. code de terminaison de celui ci 4 3 2 Synchronisation par signaux La synchronisation de processus par signaux est un m canisme assez subtil Un signal est une interruption logicielle informant un processus qu un v nement ext rieur particulier ou anormal s est produit dans son environnement Par exemple lors d une division par z ro le signal floating point exception est mis l adresse du processus ne sachant pas calculer lorsque vous interrompez un processus en tapant au clavier Ctrl C le signal SIGINT est envoy destination de celui ci lorsqu un processus viole la m moire le signal SIGSEGV lui est adress etc Il existe de nombreux signaux et tous sont identifi s par une constante symbolique La liste de ces constantes ainsi que toutes les fonctions permettant de manipuler les signaux sont d finies dans le fichier standard signal h A chaque signal est associ un v nement ext rieur et un comportement pr d fini du processus recevant le signal Toutefois un signal peut tre envoy sans que l v nement correspondant ne se soit produit la seule information v hicul e est alors le type du signal et de plus le comportement standard d un processus face un signal peut tre modifi Le tableau suivant pr sente quelques signaux leur type le comportement associ et le caract re modifiable ou non de ce comportement Jean Luc Damoiseaux I S LT V 15 Syst me d Exploitation Les Processus Nom
41. du signal Comportement associ Modifiable SIGFPE erreur arithm tique erminsimanpeenns A mimenenmeesns Envoi d un signal L envoi d un signal d un processus un autre se fait au travers de la fonction kill dont le prototype est le suivant int kill int pid int sig o pid repr sente le num ro du processus destinataire et sig le signal mis cette fonction renvoie O si elle s est correctement d roul e et 1 sinon Le processus metteur et le processus receveur doivent en principe appartenir au m me utilisateur R ception d un signal La prise en compte d un signal par un processus se traduit par un comportement par d faut d sign symboliquement par la constante SIG_DFL et d finissant l action r aliser lors de la r ception du signal Ainsi un processus recevant un signal pourra se terminer se terminer et engendrer une image m moire fichier core qui plus tard sera analys e ignorer le signal s interrompre reprendre son ex cution Toutefois il est possible pour certains signaux voir tableau pr c dent de changer ce comportement par d faut Ainsi la r ception d un signal un processus pourra ignorer celui ci constante symbolique STG_TGN ou adopter un autre comportement Dans ce cas une fonction d finie par l utilisateur sera associ e au signal et lors de la r ception du dit signal le processus r cepteur effectuera
42. e l utilisateur humain ou programme celui ci se retrouvant alors d barrasser de toutes les t ches trop proches de la machine 1 Historique des syst mes d exploitations L informatique n existe que depuis la deuxi me guerre mondiale et il est loin le temps des machines lampes lorsque l on parle des ordinateurs de la cinqui me g n ration L volution des fonctionnalit s et par cons quent la taille des syst mes d exploitations est all e de pair avec les progr s technologiques La p riode d crite s tale donc de 1940 1990 mais au del des ann es 1970 il est difficile de d gager dans le d veloppement des syst mes d exploitations autres choses que des tendances g n rales Jean Luc Damoiseaux L S LT V 5 Syst me d Exploitation G n ralit s Entre le d but des ann es 1940 et la fin des ann es 1950 les ordinateurs taient constitu s de lampes vide Outre une taille respectable les ordinateurs de l poque taient extr mement co teux fragiles et sensibles divers insectes consid r s comme nuisibles Aussi un seul groupe de personnes concevait construisait et utilisait une machine Les syst mes d exploitation taient alors inconnus et 1l fallait r server pendant un certain temps la salle machine pour au moyen cartes lectriques puis de cartes perfor es travailler sur un ordinateur L informaticien pr historique programmait donc un ordinateur en langage machine sur des cartes et assura
43. e contenu d un r pertoire est interpr t par un certain nombre de Jean Luc Damoiseaux I S LT V 43 Syst me d Exploitation La m moire secondaire fonctions du syst me Ils permettent d une part de structurer l ensemble des fichiers en arborescence et d autre part d finissent un m canisme de d signation ext rieure des fichiers ind pendants de leur localisation dans les tables du syst me et sur le disque A noter qu il existe galement d autres types de fichiers correspondant soit aux p riph riques soit des moyens de communication entre processus 2 2 L organisation du disque et la sauvegarde des fichiers Cet aspect de l exploitation d un disque concernent les couches basses du syst me de gestion des fichiers En effet ici on ne se pr occupe plus de savoir comment un fichier se nomme mais bien plut t comment on va organiser le disque et stocker les fichiers afin d obtenir un fonctionnement fiable et efficace du syst me de gestion des fichiers 2 2 1 L organisation du disque Il existe deux strat gies pour stocker un fichier de n octets on alloue n octets cons cutifs sur le disque le principal probl me de cette m thode est d aux augmentations de taille du fichier ce qui oblige d placer souvent le fichier de place on divise le fichier en plusieurs blocs pas n cessairement contigus Le premier probl me se poser est celui du choix de la taille d un bloc Ce choix est issu d un compromis entre la v
44. e gestion de m moire uniforme le PC Dans le cas o un seul processus la fois utilise les ressources du syst me la plus simple des gestions de l espace m moire r el est celle pratiqu e dans le monde de la micro Jean Luc Damoiseaux I S LT V 29 Syst me d Exploitation Allocation de la m moire informatique2 L espace m moire r el est ainsi partag entre le syst me d exploitation et l unique processus utilisateur Quand un processus demande s ex cuter le syst me d exploitation le charge dans l espace m moire r el l ex cute et sa terminaison reprend la main OxFFF inutilis Programme utilisateur Syst me d exploitation O Figure n 2 Organisation de la m moire sur un PC Une telle organisation peut conduire de graves probl mes d s lors qu un processus acc de intentionnellement virus ou non utilisation de structures de donn es dynamiques r cursivit infinie l espace m moire r el r serv au syst me d exploitation Ce probl me a conduit d velopper des solutions logicielles fonctions permettant de tester si une op ration est possible et mat rielles registres limites assurant une plus ou moins grande protection 3 Gestion de la m moire hi rarchis e Une m moire uniforme n est pas adapt e au multiplexage de l unit centrale entre un nombre important de processus et ce pour trois raisons les processus inactifs occupent inutilement une partie de l esp
45. e le contexte du processus A dans la table des processus il r actualise les registres de l unit centrale partir du contexte du processus B et enfin il r active le processus B S1 l on tudie ce sch ma de plus pr s on peut se demander comment le distributeur s y prend il pour sauver le contexte de A En effet si le distributeur sauvegarde le contexte du processus A c est donc le processus associ au distributeur est actif et donc occupe l unit centrale avec son propre contexte La solution ce probl me recourt au m canisme d interruption En fait le syst me d exploitation peut programmer l horloge pour que celle ci g n re une interruption mat rielle associ e une routine de changement de contexte Le sch ma pr c dent peut donc tre affin ainsi l horloge g n re une interruption qui est d tect e par le mat riel le fonctionnement normal du processeur est arr t le mat riel sauvegarde dans une pile le contexte du processus interrompu le code correspondant l interruption est fourni aux circuits de traitement des interruptions qui calculent l adresse de cette derni re l adresse de l interruption est recopi e dans le compteur ordinal le registre d tat est modifi l ordinateur passe alors en mode syst me l ex cution de la routine d interruption syst me entra ne la s lection d un processus et de son contexte la fin de l interruption provoque le chargement du nouveau co
46. essus2 E lt E processus3 VW N N parall lisme simul Figure n 1 Comparaison du temps d ex cution de trois processus n effectuant que du calcul Cependant rares sont les programmes qui ne font que du calcul et l avantage du parall lisme simul sur la monoprogrammation devient alors vident d s qu un processus est par exemple bloqu dans l attente de l ach vement d une entr e sortie change avec l utilisateur lecture sur le disque etc Ainsi condition de disposer d un dispositif d entr es sorties autonome d s qu un processus attend l ach vement d une entr e sortie le processeur lui est retir au profit d un autre processus Si tous les programmes font suffisamment d entr es sorties on arrive alors masquer l ex cution des calculs par les temps d attente des entr es sorties chaque utilisateur a l impression d un temps de r ponse quasiment identique celui obtenu s il tait le seul travailler sur la machine figure n 2 Jean Luc Damoiseaux I S LT V 21 Syst me d Exploitation Gestion des Processus processus2 processus3 parall lisme vrai processus1 processus2 processus3 t mono programmation processusli processus2 PERS bp es parall lisme simul Figure n 2 Comparaison du temps d ex cution de trois processus effectuant du calcul et des entr es sorties 3 Allocation du pr
47. est jld je peux d signer le fichier more appartenant au r pertoire bin en crivant bin more 3 2 2 Utilisation d un fichier L utilisation d un fichier est r gl par un principe de permissions d acc s Il existe quatre types de permissions qui d terminent le mode d emploi autoris pour un fichier E aucune permission nr read la lecture du fichier est possible w write l criture du fichier est possible a x execute l ex cution du fichier est possible Pour les r pertoires ces permissions ont un sens diff rent e r read il est possible de consulter le r pertoire e w write il est possible de cr er ou de d truire des fichiers dans ce r pertoire e x execute il est possible d acc der aux fichiers contenus dans ce r pertoire A ceci UNIX ajoute une classification des types d utilisateurs potentiels pour lesquels seront regroup s les modes d emploi possibles des fichiers Jean Luc Damoiseaux I S I T V 10 Syst me d Exploitation G n ralit s e user pourle propri taire e group pourle groupe propri taire e other pourle reste des utilisateurs du syst me Par type d utilisateur sont associ s les quatre modes d emploi possibles ce qui fait douze types de permissions par fichier 3 2 3 Nom g n rique des fichiers La cr ation de nom g n rique pour les fichiers permet d utiliser une commande sur un ou plusieurs fichiers qui r pondent au mod le labor Ces mod les sont constru
48. eve Bourne InterEditions 1985 Jean Luc Damoiseaux I S I T V 50
49. fichiers Gr ce cette notion de r pertoire et gr ce l introduction des deux fichiers que sont le et le le d signant le r pertoire lui m me et le d signant son p re le r pertoire auquel il appartient UNIX d finit une structure arborescente figure n 2 de l ensemble des fichiers la racine de cette arborescence tant conventionnellement repr sent e par le caract re 1 Nous travaillerons avec le C Shell dont le prompt est symbolis par le caract re Jean Luc Damoiseaux L S LT V 9 Syst me d Exploitation G n ralit s Figure n 2 Structure arborescente du syst me de fichiers sous UNIX Il existe donc pour tout fichier au moins un chemin partant de la racine de l arborescence et se terminant sur le fichier en question Ce chemin appel la r f rence absolue est constitu par la suite des diff rents r pertoires travers s pour Joindre le fichier chaque l ment de cette suite tant s par par un Par exemple le chemin suivant users profs jld essai c pr cise que le fichier essa c est situ dans le r pertoire j1d lui m me situ dans le r pertoire profs lui m me situ dans le r pertoire users appartenant au r pertoire racine Toutefois il est possible de construire des chemins d acc s un fichier partir du r pertoire o l on se trouve chemin relatif ces chemins d acc s commencent partir des r pertoires et Par exemple si le r pertoire courant
50. galement que c est cette poque que les techniques de gestion d une m moire hi rarchis e virent le jour tout ou partie d un programme oscillera entre la m moire primaire et la m moire secondaire Jean Luc Damoiseaux L S LT V 6 Syst me d Exploitation G n ralit s Au travers de cette histoire il appara t tr s clairement que l on a toujours cherch rentabiliser le mat riel en d veloppant un logiciel le syst me d exploitation permettant de l exploiter au mieux A l heure actuelle le co t du mat riel est devenu nettement moindre que celui du logiciel et la conception d un syst me d exploitation demande plus de temps que celle d une machine Les tendances mat rielles et ou logicielles en cours sont l int gration dans le silicium des fonctionnalit s des syst mes d exploitations la d finition d interfaces graphiques augmentant la convivialit des machines le d veloppement du parall lisme et des syst mes r partis 2 Fonctions d un syst me d exploitation Un syst me d exploitation a pour unique but de mettre la disposition d un ou plusieurs utilisateurs une machine virtuelle qui d une part lib re le programmeur de la complexit du mat riel et d autre part lui offre des fonctionnalit s plus importantes que celles de la machine physique Parmi les nombreuses fonctions assur es par un syst me d exploitation les principales sont la gestion de la m moire centrale comment partager la m moire e
51. isateurs disposant des sources peuvent facilement l tudier et le modifier L ann e 1978 marque un tournant dans l histoire d UNIX puisque la premi re version commerciale appel e V7 sort sur le march A partir de cette version deux familles d UNIX mergent Tout d abord les laboratoires ATT et BELL r alisent des d veloppements qui Jean Luc Damoiseaux L S LT V 7 Syst me d Exploitation G n ralit s conduiront aux versions SYSTEM V Ensuite les travaux r alis s l universit de Berkley aboutissent aux versions BSD A l heure actuelle en plus de toutes les versions mineures deux grandes familles d UNIX coexistent celle de l universit de Berkley BSD et celle de la compagnie AT amp T System V Gr ce des groupes de r flexions comme usr group OSF Unix International etc un effort de standardisation a t entrepris depuis 1984 Ainsi l acc s au noyau se fait au travers d interfaces comme X OPEN ou POSIX la gestion de l cran graphique se fait au travers de l interface X WINDOW elle m me accessible au travers d interfaces comme MOTIF ou OPEN LOOK L histoire d UNIX permet de tirer certaines conclusions quant ses qualit s et ses d fauts UNIX n est pas un syst me d exploitation jeune il a donc fait ses preuves r sultat du travail de nombreuses sources d am liorations il est attractif poss de toutes les fonctionnalit s d un syst me d exploitation moderne mais il manque t
52. it une gestion compl te du contexte d ex cution de son programme chargement entr es sorties etc Entre les ann es 1955 et 1965 l arriv e du transistor modifia compl tement la situation en rendant les ordinateurs fiables donc commercialisables Le chargeur devint le premier programme r sident les premiers compilateurs FORTRAN et Assembleur apparurent et les entr es sorties devinrent accessibles par des macro instructions et g r es par l ordinateur L arriv e des m moires secondaires disques bandes et tambours provoqua galement le d veloppement des syst mes de gestion des fichiers Enfin pour optimiser l acc s l ordinateur les moniteurs d encha nement des travaux virent le jour on soumettait l ordinateur des fourn es batch de travaux bacs de cartes chacuns pr c d s de cartes indiquant la nature du travail compilation ex cution etc Toutefois un probl me se posa rapidement le d bit d entr e et de sortie des donn es tait beaucoup plus faible que le d bit de leur traitement ce qui provoquait un non travail de l unit centrale Avec l arriv e des circuits int gr s l acuit de ces probl mes devint tr s importante On imagina donc vers 1965 des unit s d entr es sorties asynchrones l unit centrale activait l unit d entr es sorties et lui pr cisait le nombre d octets transf rer ainsi que leur adresse en m moire tandis que l unit centrale continuait son travail l unit d
53. itesse de transfert et le taux de remplissage souhait pour le disque l exp rience tend prendre 512 octets 1K ou 2K comme taille d un bloc Le deuxi me probl me qui se pose est celui de la m morisation des blocs libres G n ralement on utilise une liste cha n e des blocs libres ou une table de bits le i me bit de la table indiquant si le i me bloc du disque est libre ou non le choix de l une ou l autre des techniques tant principalement li la place disponible en m moire centrale 2 2 2 Le stockage des fichiers Un fichier tant constitu d un certain nombre de blocs le syst me doit m moriser la place des diff rents blocs le constituant L allocation de blocs cons cutifs bien que tr s simple mettre en oeuvre est totalement inadapt e au probl me du fait de l augmentation certaine de la taille des fichiers Aussi on utilise plut t une liste cha n e des blocs constitutifs du fichier en association ou non avec une table de pointeurs charg e en m moire centrale 3 Le syst me de gestion de fichiers d UNIX La notion de fichier sous UNIX ne se limite pas la notion usuelle du fichier disque Un fichier est un objet typ sur lequel est d fini un ensemble d op rations Ainsi un fichier peut tre une suite d octets sur le disque ou une ressource physique ou logique du syst me comme par exemple un terminal une imprimante la m moire etc D un point de vue interne chaque fichier correspond une en
54. its partir des caract res suivants e qui remplace un caract re quelconque e qui remplace une suite ventuellement vide de n importe quel caract re e qui remplace n importe quel caract re repris dans la liste de caract res inclus entre crochets cette liste peut tre form e par deux caract res s par s par un qui d termine alors un ensemble de caract re Ainsi le nom g n rique b 0 9 C d signe tous les fichiers dont le nom commence par un b dont le deuxi me caract re est un chiffre et se terminant par C 3 3 La redirection des entr es sorties Les processus n cessitant des donn es en entr e ou fournissant des r sultats en sortie les lisent ou les crivent sur leur entr e et leur sortie standard savoir le clavier et l cran Il est possible d affecter ces fichiers d entr e et de sortie d autres dispositifs que la console qui contr le le processus La redirection de l entr e standard d un processus depuis un fichier d entr e suit la syntaxe o commande lt fichier entree La redirection de la sortie standard d un processus dans un fichier suit la syntaxe o commande gt fichier sortie si fichier _ sortie existe d j il est pr alablement effac Cependant lors d une utilisation encha n e de plusieurs commandes le passage des r sultats par des fichiers interm diaires n est pas un mode de communication optimal La notion de tube palie cet inconv
55. ivers indicateurs de protection Les segments proc dures peuvent tre r entrants ex cut s par plusieurs processus ce qui vite une duplication du code Les segments donn es peuvent selon les situations appartenir un processus ou plusieurs 1 2 Informations utilis es par le syst me Les informations utilis es par le syst me servent g rer l attribution des ressources pour un processus donn Habituellement ces informations sont le contenu des registres g n raux ces registres sont adressables et modifiables par le processus Jean Luc Damoiseaux I S LT V 19 Syst me d Exploitation Gestion des Processus z le Mot d Etat du Processeur MEP ou en anglais PSW Program Status Word le MEP contient une copie des registres sp cialis s compteur ordinal registre d instruction etc ces registres sont en principe inaccessibles au processus l tat d ex cution du processeur le pouvoir du processus un processus s ex cute en mode ma tre ou en mode esclave le mode ma tre lui permet de r aliser les instructions d entr es sorties celles touchant aux interruptions et celles concernant la s curit et la protection la priorit du processus et pour finir les masques d interruptions le contenu de la m moire virtuelle Toutes ces informations sont situ es dans le bloc de contr le du processus PCB Process Control Bloc les blocs de contr le de tous les processus tant regroup s dans la table des proce
56. l information De nombreux m canismes de m moire virtuelle ont t labor s et on peut les s parer en trois grandes familles ceux o la correspondance entre l espace m moire virtuel et l espace m moire r el est r alis e lors de l criture de la compilation ou de l dition de liens du programme le r sultat est un module non translatable qui doit toujours tre charg la m me adresse r elle ceux o la correspondance entre l espace m moire virtuel et l espace m moire r el est r alis e au moment du chargement du programme le r sultat de la compilation ou de l dition de liens est un module translatable dont les adresses seront d finitivement fix es lors de son chargement en m moire r elle Le chargeur par r implantation statique peut placer le programme n importe o dans l espace m moire r el ceux o la correspondance entre l espace m moire virtuel et l espace m moire r el est r alis e lors de l ex cution du programme toute adresse virtuelle est transform e en une adresse r elle au moment o elle est utilis e Cette traduction dynamique des adresses autorise une r implantation dynamique d un programme au cours de son ex cution 1 3 M moire uniforme M moire hi rarchis e Lorsque l espace m moire r el est le seul support de l information adressable par le processeur celui ci est dit uniforme Dans une telle situation la taille de l espace m moire virtuel est inf rieure
57. le l utilisateur et ce qu il y a r ellement sur le support de m moire externe cet aspect est appel l interface syst me 2 1 La notion de fichier Un fichier est un ensemble de donn es que l on stocke et auxquelles on acc de de mani res diverses au hasard des traitements Les caract ristiques essentielles d un fichier sont le stockage d un volume quelconque d informations la permanence des donn es dont la dur e de vie n est pas li e celle d un programme l ordre d acc s aux informations impos par les n cessit s du traitement Les op rations possibles sur un fichier sont de nature Jean Luc Damoiseaux I S LT V 42 Syst me d Exploitation La m moire secondaire globale lorsque le fichier est consid r comme un tout parmi les op rations les plus courantes sur un fichier on trouve sa cr ation sa destruction sa copie etc partielle si l on s int resse individuellement ses l ments parmi les op rations les plus courantes sur un l ment on trouve sa recherche sa destruction sa lecture ou son criture etc 2 1 1 La structure et les modes d acc s d un fichier Pour les couches basses du syst me de gestion des fichiers celles qui traitent avec le mat riel la structure d un fichier est un ensemble d octets de par son niveau cette structure est dite physique Par opposition une structure logique d un fichier a t introduit pour pr ciser la notion de fichier
58. lut b t t te lors de la lib ration d 11 duit une sous utilisation de la m moire En effet les tailles des zones tant arrondies une puissance de deux il se produit un ph nom ne important de fragmentation interne 3 1 4 Lib ration d une zone Lors de la lib ration d une zone allou e trois situations diff rentes peuvent appara tre selon que la zone lib r e est entour e de deux zones libres d une zone allou e et d une zone libre ou de deux zones allou es figure n 6 Jean Luc Damoiseaux I S LT V 33 Syst me d Exploitation Allocation de la m moire CR et Na Figure n 6 Lib ration d une zone m moire Chaque fois que cela est possible cas a et b il est utile de regrouper d s la lib ration la zone lib r e avec les zones libres voisines pour cr er ainsi une zone libre de taille plus grande on vite ainsi le fractionnement de la m moire La rapidit de ce regroupement d pend de la mani re dont l espace m moire r el est allou pour les listes cha n es un ordonnancement efficace pour l allocation ne le sera pas pour la lib ration pour l allocation par subdivisions il suffit de fusionner les compagnons 3 1 5 Fragmentation et compactage Au bout d un certain temps d utilisation dans des syst mes d allocation du type demande de zone une fragmentation de l espace m moire r el se produit Cette situation emp chant l allocateur de trouver une zone de taille suffisante pour satisf
59. moire par une liste cha n e De l organisation de cette liste d pend l efficacit des algorithmes Le cha nage peut tre construit dans l ordre chronologique des lib rations mais le plus souvent on utilise les classements suivants classement par adresses croissantes ou d croissantes classement par tailles croissantes ou d croissantes le choix d pendant de l algorithme utilis pour satisfaire une demande Lorsqu une demande est mise plusieurs algorithmes de s lection d une zone sont possibles on prend la premi re zone possible first fit qui est d coup e en deux parties l une attribu e au processus demandeur l autre appel e r sidu inutilis e cet algorithme est rapide puisque pratiquement sans recherche on prend la plus petite zone possible best fit et on vite ainsi de fractionner une grande zone dont on pourrait avoir besoin ult rieurement on peut galement prendre la plus grande zone possible worst fit et ainsi obtenir le plus grand r sidu possible D une mani re g n rale le premier algorithme est le plus rapide de tous Toutefois selon l organisation de la liste les performances de ces algorithmes peuvent varier dans le cas de l algorithme de la plus petite zone possible le classement par tailles vite de parcourir toute la liste si le classement est fait par adresses ou s il n y a pas de classement une fois la zone allou e le r sidu reste sa place alors qu avec u
60. n classement par tailles 1l doit tre d plac Enfin ces techniques entra nent un ph nom ne d accumulation des r sidus en t te de liste ce qui ralentit les recherches On utilise souvent une liste circulaire qui permet de commencer l exploration partir de n importe quel point Jean Luc Damoiseaux I S LT V 32 Syst me d Exploitation Allocation de la m moire 3 1 3 Gestion de l espace m moire r el par subdivision buddy system Une troisi me solution pour la gestion de l occupation de l espace m moire r el consiste d couper celui ci en listes de blocs dont la taille est une puissance de deux variant de 1 octet jusqu la taille maximale de la m moire figure n 5 1024 Ko Introduction d un procesus de taille 80 Ko Figuren 5 Gestion de la m moire selon le principe de subdivision Au d part il n existe qu une seule liste contenant un bloc de la taille de l espace m moire r el Le principe de la m thode est le suivant si t est la taille de l espace m moire r el demand par un processus on recherche alors un bloc dont la taille est gale la plus petite puissance de deux qui est sup rieure t si un tel bloc n existe pas alors on le cr e par divisions successives de blocs de taille sup rieure la division en deux d un bloc cr deux blocs appel s les compagnons ou buddy ette solution bien que tr s int ressante lors de la lib ration d une zone allou e conduit Cett
61. n le programme suivant include lt stdio h gt include lt stdlib h gt void main void system sleep 60 return un appel la commande ps nous permet de mieux comprendre les m canismes mis en jeux Jean Luc Damoiseaux I S I T V 11 Syst me d Exploitation Les Processus PPID CP PRI TTY TIME 859 1 ttyp20 00 866 ttyp20 00 0 867 0 ttyp20 00 0 925 ttyp20 00 Au cours de son ex cution le processus essai appelle le noyau par la fonction systen Cet appel entraine la cr ation d un processus fils de nom sh c pid 925 Ce processus est son tour le p re du processus sleep pid 966 correspondant notre commande sleep 60 les processus essai et sh c seront bloqu s jusqu la fin du processus sleep 4 2 2 Les primitives exec UNIX propose d autres primitives pour cr er des processus Les primitives exec repr sentent une famille de primitives dont l objectif est la cr ation d un nouveau processus se substituant au processus appelant Par exemple la primitive execl dont le protoype est le suivant int execl char ref char argos char arg substitue au processus appelant le processus dont le lancement correspond l ex cution du programme argo dont la r f rence absolu dans l arborescence des fichiers est donn e par ref et dont les ventuels arguments de travail sont arg1 argn Donn es
62. nc 28 1 3 M moire uniforme M moire hi rarchis e 29 2 Un cas de gestion de m moire uniforme le PC da mena 29 3 Gestion de la m moire hi rarchis e anna res nat est tn Rue res 30 3 1 Le Va et Vient SWAppINg nina Antist 30 3 2 DAS MAO SA SA An LR Te nt Et nr 35 3 3 Lasegmentationt ms US en NS se 37 Chapitre 5 La m moire secondaire ccoccocccoccocco00000000000000000000000000000000000000000000000000000 39 1 Etude d disq e magn tighe same intenses E g 39 1 1 Structure physique d un disque sssssnsierindienenalnaninsantisnianit 39 1 2 Ee pilote du Squier te AC ECE SR ne nee A 40 2 Le syst me de gestion des TOMI TS Sn ETS RES ee ne SR Re CS 42 2 1 La notion de fichier 32e Mt ant dede nee ns here te 42 2 2 L organisation du disque et la sauvegarde des fichiers iiiiiie 44 3 Le syst me de gestion de fichiers d UNIX cccccccccccciccciicciiicciiicciicciiccicccccicceeeess 44 3 1 La structure arborescente 22220 M LAN LE RER QE D LE R es 45 3 2 Lestypes de FIchiers Sn nes ntre de 46 3 3 Organisation du disque rss rise intenses niet 46 1 6315 1163548211 4 11200022 0 A EP A2 0 A 4221224 157 en ete 19 E dette sn en ent AS 50 1 Syst mes d exploitation Sa SR a mess a Ries 50 D D E E 2022 A US 50 Jean Luc Damoiseaux L S LT V 3 Syst me d Exploitation Avertissements Avertissements Ce document est le support du cours consacr aux
63. ntexte et ainsi rend le processus s lectionner actif Il est important de se rappeler que la routine d interruption de changement de contexte m me si elle est c bl e fait partie du syst me d exploitation Les instructions qui s y trouvent s ex cutent en mode syst me le programme interrompu travaillant normalement en mode utilisateur Jean Luc Damoiseaux I S LT V 24 Syst me d Exploitation Gestion des Processus 3 4 Strat gie d allocation du processeur Les strat gies de choix d un processus par le distributeur sont nombreuses et visent souvent r duire le temps de r ponse pour des processus n cessitant un temps d ex cution court Toutefois d une mani re g n rale il est possible de classifier ces strat gies selon qu elles mettent en oeuvre les deux notions suivantes la pr emption ou r quisition du processeur lorsqu un processus important passe dans l tat demandeur l algorithme doit d cider ou non d interrompre le processus en cours pour donner la main au processus important et le cas ch ant il doit d terminer dans quel d lai on devra le faire la nature des informations utilis es pour d clencher le changement de contexte cot des strat gies enti rement fix es priori il en existent certaines utilisant les informations attach es au processus ou les informations recueillies au cours de l activit du syst me 3 4 1 Strat gie sans recyclage des travaux Ces strat gies sont g
64. ntre plusieurs utilisateurs comment faire partager des donn es entre plusieurs utilisateurs comment une machine dont la taille m moire est de n mots peut elle stocker un programme et des donn es dont la taille est plus grande que n mots m moire etc l ex cution des commandes d entr es sorties qui sont toujours lentes par rapport la vitesse du CPU comment synchroniser la CPU avec l unit d entr es sorties et si plusieurs utilisateurs d sirent imprimer un fichier etc la gestion du CPU comment ex cuter plusieurs programmes la fois d termination de l utilisateur qui la main que faire s il ne veut pas la rendre et s il y a une coupure de courant etc la gestion des m moires secondaires comment g rer le probl me de l acc s un m me fichier par plusieurs utilisateurs comment retrouver ou stocker de l information sur un disque comment optimiser l utilisation du disque etc fournir un environnement de travail l utilisateur l interpr tation d un langage de commande et l encha nement des travaux demand s etc 3 Le syst me UNIX Historiquement le syst me UNIX a t con u dans le laboratoire de la compagnie BELL ATT entre 1969 et 1971 par Ken Thompson Brian Kernigham Denis Ritchies Entre 1971 et 1975 il est r crit en C et continue d tre d velopp au sein de ce laboratoire Mis la disposition des universit s de l tat am ricain et des compagnies commerciales les util
65. ocesseur r el Nous allons donc voir maintenant comment est simul le parall lisme sur une machine monoprocesseur et plus exactement comment est allou le processeur dans un syst me multit ches 3 1 D finition du probl me Le probl me de l allocation du processeur peut tre sch matis comme suit au cours du temps suivant une certaine loi d arriv e des processus demandent utiliser le processeur figure n 3 Jean Luc Damoiseaux I S LT V 22 Syst me d Exploitation Gestion des Processus s lection d un processus par le distributeur Processus fin dgn cr ation d uy Processus rocessus processu demandeurs fin de la tranche de temps amp allou e au processus 2 e S P Q x2 A Figure n 3 Sch ma d allocation du processeur Dans ce sch ma on retrouve les divers tats possibles d un processus qui sont actif seul le processus utilisant le processeur est dans cet tat bloqu cet tat est attribu aux processus attendant la fin d une entr e sortie la lib ration d une ressource ou en communication synchronisation avec d autres processus attente cet tat est attribu aux processus qui ne sont plus bloqu s et ceux qui ont consomm leur quantum de temps dans les deux cas le processus pourrait reprendre son ex cution mais le processeur n est pas disponible Le probl me de l allocation du processeur revient donc d finir le r le du composant syst
66. oid main void fork printf j ai reussi n return printf Bonjour je vais me dupliquer n qui provoque l cran deux fois l affichage du message j ai reussi Une analyse plus d taill e nous montre qu au lancement du programme un processus essai a t cr UID PID PPID CP PRI NI VSZ 25 866 859 0 44 867 866 0 44 25 RSS WCHAN S TTY TIME 0 1 91M 400K pause S ttyp2 0 01 0 1 22M 88K R ttyp2 0 00 Puis au moment de l appel la primitive fork un deuxi me processus essai est cr Ce processus est conforme en tous points au premier ceci pr s qu il est son fils Ces deux processus ayant le m me code il est donc normal que l on voit s afficher l cran deux fois le message PID PPID CP PRI NI VSZ 866 859 0 44 44 44 867 866 0 900 867 0 RSS WCHAN S TTY TIME 0 1 91M 400K pause S ttyp2 0 01 0 1 22M 88K 0 1 22M 88K S ttyp2 0 00 Jean Luc Damoiseaux I S LT V R ttyp2 0 00 Syst me d Exploitation Les Processus 4 3 Synchronisation de processus 4 3 1 La primitive wait La primitive wait permet de synchroniser de mani re rudimentaire des processus en suspendant l ex cution du processus en cours tant que l un de ces fils ne s est pas termin Le prototype de cette fonction est int wait int code Lorsqu un processus fils meurt la fonction wait renvoie son num ro d identification et place dans code l adresse du
67. ommag s ce calcul est fauss ce qui entra ne un traitement ad quat Dans le cas d une poussi re on r p tera l op ration et on indiquera le cas ch ant que le bloc est endommag Dans le cas d un bloc endommag un traitement sp cial et maison permet d viter ce bloc liste cha n e des blocs endommag s pistes suppl mentaires accessible au seul syst me contr leurs utilisant des tables de substitution etc les erreurs de recherche positionnement du bras sur le mauvais cylindre dues aux probl mes m caniques un d calage entre la position de bras m moris e par le contr leur et sa position r elle peut se produire Certains contr leurs traitent l erreur d autres se contentent de la signaler obligeant ainsi le pilote effectuer une op ration de recalibrage du disque d placement du bras sa position extr me puis remise z ro de la position m moris e du bras 2 Le syst me de gestion des fichiers Le syst me de fichiers est l une des parties les plus importantes d un syst me d exploitation sur un certain syst me c est m me pratiquement la seule fonction Un premier aspect du syst me de gestion des fichiers est bas sur la notion de fichier et les fonctions qui lui sont associ es cet aspect est appel l interface utilisateur Le deuxi me aspect du syst me de gestion des fichiers est l ensemble des m canismes qui permettent au syst me d tablir la correspondance entre ce que manipu
68. ou gale la taille de l espace m moire r el En outre la gestion de l espace m moire virtuel se ram ne au choix d un algorithme de placement dans l espace m moire r el une fois plac es dans l espace m moire r el les informations y demeureront jusqu au moment o elles cesseront d tre utilis es Lorsqu on souhaite partager sur le principe de la r quisition l espace m moire r el entre plusieurs processus un espace m moire r el secondaire devient n cessaire pour conserver les informations provisoirement chass es de l espace m moire r el l espace m moire r el est alors dit hi rarchis Dans une telle situation la taille de l espace m moire virtuel peut tre sup rieure ou gale la taille de l espace m moire r el et la gestion de l espace m moire virtuel se ram ne au choix d un algorithme de placement et de remplacement dans l espace m moire r el Cette hi rarchisation comporte au moins deux niveaux dont les caract ristiques l un par rapport l autre sont un co t de stockage moindre une capacit plus grande et un temps d acc s plus important en g n ral le premier niveau est constitu par la m moire vive et le second par le disque dur Dans une telle organisation il s agira de r partir l information entre les diff rents niveaux de la hi rarchie pour obtenir un temps moyen d acc s l information proche de celui de l unit rapide avec un co t proche de celui de l unit lente 2 Un cas d
69. outefois d homog n it et de s ret crit 95 en C UNIX est un syst me portable 3 1 Pr sentation et Structure du syst me UNIX Le syst me UNIX est un syst me multi utilisateurs et multi taches Ses domaines de comp tences s tendent de la gestion au calcul scientifique en passant par les bases de donn es la bureautique etc Le syst me UNIX est une succession concentrique de couches logicielles figure n 1 RE d J LA gt Q SH Figure n 1 Vue g n rale du syst me UNIX La premi re de ces couches est le noyau Composant logiciel directement en contact avec le mat riel toutes les demandes des autres couches logicielles lui parviennent via une interface de fonctions d appel Le noyau cr l environnement UNIX pour une machine donn e et assure comme principales fonctions l organisation et la gestion des donn es du syst me Jean Luc Damoiseaux L S LT V 8 Syst me d Exploitation G n ralit s la protection du syst me et l acc s l information z la communication de l information entre les diff rents l ments du syst me le fonctionnement multi utilisateurs et multi tache en planifiant l utilisation des ressources mat riels processeur m moire etc l tablissement de statistiques quant son activit La seconde de ces couches est le Shell Le Shell est l interpr teur des commandes introduites par l utilisateur et ce titre il sert d interface entre le
70. p r par des marques le formatage d un disque consistant poser ces marques l Figure n 1 Structure d un disque On introduit galement les notions de bloc et de cylindre un bloc est la quantit minimale lue ou crite lors d un acc s au disque la taille d un bloc est g n ralement de 512 ou 1024 octets un cylindre correspond au nombre de pistes accessibles simultan ment lors d un acc s au disque un cylindre contient donc autant de pistes que de t tes de lecture criture Jean Luc Damoiseaux I S LT V 39 Syst me d Exploitation La m moire secondaire Enfin chaque disque poss de un contr leur de disque assurant le d placement du bras la rotation du disque et la commande des t tes le regroupement des s ries de bits lues etc Ce contr leur est un v ritable ordinateur avec sa m moire et ces registres En outre de nombreux contr leur permettent un acc s direct la m moire d chargeant ainsi l unit centrale du transfert de l information Le lien entre l utilisateur et le contr leur est assur par le syst me d exploitation au moyen d un logiciel appel le pilote driver Celui ci traduira les requ tes syst mes en un programme ex cut par le contr leur 1 2 Le pilote du disque L utilisation d un disque se fait donc au travers d un pilote de disque Celui ci doit d une part optimiser les temps d acc s au disque en fonction des demandes et d autre part g rer les erreurs logiques
71. r inaccessibles aux autres processus De nombreuses solutions ont t propos es pour r soudre ce probl me de l exclusion mutuelle Avant d tudier les principales d finissons les propri t s essentielles que toutes devront respecter tout instant un processus au plus peut se trouver en section critique si plusieurs processus sont bloqu s en attente de la ressource critique alors aucun processus ne se trouve en section critique et l un d eux doit pouvoir y rentrer au bout d un temps fini si un processus est bloqu hors d une section critique ce blocage ne doit pas emp cher l entr e d un autre processus dans sa section critique la solution doit tre la m me pour tous les processus Jean Luc Damoiseaux I S LT V 3 Syst me d Exploitation Les Processus 2 1 Attente active L attente active est une solution c bl e du probl me de l exclusion mutuelle et tous les ordinateurs ne disposent pas d un tel m canisme L emploi d une unique variable bool enne ne convient pas car entre le test de la variable bool enne et son affectation par un processus i un autre processus j avait la possibilit d acc der cette variable La solution la plus imm diate consiste donc r aliser ces deux op rations simultan ment la nouvelle op ration s appelant TAS Test And Set Cette instruction agissant sur une variable m peut se d crire ainsi instruction TAS m debut bloquer l acc s la cellule m moi
72. rch l argument print permet d afficher les r sultats de la recherche grep expression fichier permet de s lectionner dans un fichier les lignes contenant expression sort r fichier trie dans l ordre lexicographique les diff rentes lignes d un fichier wc lwc fichier compte pour chaque fichier ou l entr e standard si aucun fichier n est pr cis ce qu il contient Jean Luc Damoiseaux L S LT V 13 Syst me d Exploitation Les Processus Chapitre 2 Les Processus L analyse du fonctionnement d un syst me d exploitation montre la pr sence d un ensemble d activit s multiples simultan es ou non et pr sentant de nombreuses interactions mutuelles Pour d crire ce fonctionnement on introduit la notion de processus comme d finition d une activit l mentaire Un processus est une entit dynamique repr sentant l ex cution d un programme un processus na t vit et meurt Au cours de son existence un processus n est jamais totalement isol des autres il partage des donn es ou des ressources mat rielles change des signaux ou des informations arr te ou tue d autre processus etc Aussi l objet de ce chapitre est de pr ciser la notion de processus de montrer comment elle est mise en oeuvre et comment est programm e la coordination entre processus 1 D finitions 1 1 Instructions processeur processus Un programme est une suite ordonn e d instructions dont la nature est fonction du langage de
73. re 224Ko UID PID PPID CP PRI NI VSA RSS WCHAN S TTY IME 25 866 859 0 44 0 1 91M 392K pause S ttyp2 0 01 45 25 867 866 0 44 0 1 45M 224K R ttyp2 0 00 03 6 On notera galement que le message et maitenant je m arrete n appara tra jamais l cran 4 2 3 La primitive fork La primitive fork est utilis e pour la cr ation d un nouveau processus obtenu par duplication du processus appelant c est dire le processus p re le processus nouvellement cr s ex cute de mani re concurente au processus qui l a cr Le prototype de cette fonction est le suivant int fork void Cette primitive effectue donc une duplication du processus appelant copie des donn es du code des priorit s etc ce qui signifie que le nouveau processus appel le fils ex cute une copie du programme mise en oeuvre par le processus appelant nomm le p re La seule mani re de distinguer le p re du fils est que la valeur de retour de la fonction fork Dans le processus fils elle est nulle tandis qu elle est gale au num ro d identification du fils dans le processus p re figure n 2 Jean Luc Damoiseaux I S I T V 13 Syst me d Exploitation Donn es Figure n 2 Procesus P re Les Processus Donn es Procesus P re Illustration du m canisme de la fonction fork Prenons comme exemple l ex cution du programme suivant include lt stdio h gt include lt stdlib h gt v
74. re m lire le contenu de m si m est faux alors m lt vrai compteur_ordinal lt compteur_ordinal sinon compteur_ordinal lt compteur_ordinal fin si lib rer l acc s la cellule m moire m fin Soit p une variable bool enne indiquant que la ressource critique R est occup e ou non p est initialis e faux L entr e en section critique est r alis e par D apr s ce qui pr c de le processus ne pourra sortir de cette boucle c est dire ex cuter l instruction suivant le branchement que s il trouve p faux pendant l ex cution de l instruction TAS La sortie de la section critique est r alis e par p lt faux Sur l exemple du compte client dans un grand magasin le programme associ un processus est le suivant contexte commun compte_utilise FAUX compte_client 1000 corps du programme du processus i derniere_facture m E TAS compte utilise goto E compte_client compte client derniere _ facture compte utilise FAUX Jean Luc Damoiseaux I S I T V 4 Syst me d Exploitation Les Processus Il est important de remarquer que pour programmer l exclusion mutuelle d une ressource R on a recouru un m canisme c bl d exclusion mutuelle une autre ressource p Cette solution est appel e attente active car le processus bloqu sur p boucle sur l instruction de test et monopolise donc le processeur 2 2 Les s maphores
75. ssus 2 Le parall lisme Lorsque plusieurs processus existent en m me temps dans un syst me on parle alors de parall lisme Il existe deux sortes de parall lisme le parall lisme vrai o n processus s ex cutent sur m processeurs architecture multiprocesseur le parall lisme simul o n processus s ex cutent sur un processeur qui est successivement attribu par tranche de temps chacun des processus Livrons nous une petite tude entre le parall lisme vrai et le parall lisme simul Dans le parall lisme simul le processeur est allou par tranches de temps tranches de temps suffisamment courtes entre 1 50 et 1 10 de seconde pour donner l illusion aux utilisateurs de disposer de la machine pour eux seuls Essayons de voir pourquoi le pseudo parall lisme est une bonne mani re d utiliser une machine monoprocesseur Supposons que nous disposions de trois processus effectuant uniquement du calcul figure n 1 On remarque que le parall lisme simul n est pas un meilleur mode d exploitation du processeur que la monoprogrammation car que les processus se d roulent les uns la suite des autres ou alternativement le temps total d ex cution est le m me Jean Luc Damoiseaux I S LT V 20 Syst me d Exploitation Gestion des Processus processus o processus2 processus3 parall lisme vrai processusl processus2 processus3 t mono programmation processusl ES A proc
76. syst me d exploitation nous allons maintenant aborder les m canismes mis en jeu pour assurer plusieurs processus un d roulement simultan 1 Contexte d un processus De nombreuses d finitions ont t donn es la notion de processus La plus courante est qu un processus est une entit dynamique repr sentant l ex cution d un programme Il est important de bien comprendre qu un processus tant capable de recevoir de la part du syst me d exploitation le contr le du processeur pour un certain temps celui ci n est pas uniquement d fini par le code de son programme mais galement par un ensemble d informations n cessaires au syst me Cet ensemble d informations est appel g n ralement le contexte ou le vecteur d tat d un processus Il est form de deux parties les informations utilis es par le syst me les informations utilis es par le processus lui m me Lorsque le syst me passera la main d un processus un autre il le fera en r alisant une op ration appel e le changement de contexte 1 1 Informations utilis es par le processus Lorsqu un programme s ex cute les instructions et les donn es qui le composent sont situ es en m moire centrale Ces portions de m moire sont appel es des segments les instructions sont contenues dans le segment proc dure et les donn es dans le segment donn es Les informations utilis es par un processus sont donc la ou les tables de segments ainsi que d
77. te des utilisateurs connect s la machine Voici galement quelques commandes et leurs principales options Toutes aussi utiles que les pr c dentes ces commandes sont toutefois plus li es au syst me de gestion des fichiers gt pwd affiche la r f rence absolu du r pertoire o le se trouve cd chemin_relatif_ou_absolu permet de se d placer dans l arborescence Utilis e sans param tre le r pertoire priv de l utilisateur devient le r pertoire de travail S ls lasR nom fichier liste le contenu d un r pertoire et ou les caract ristiques de ces fichiers modes d acc s type etc z mkdir nom repertoire cr un r pertoire vide rmdir i nom repertoire efface un r pertoire pr alablement vid rm ir nom fichier efface un ou des fichiers cp src dest recopie de fichiers de la source vers la destination mv src dest d place le fichier de la source vers la destination Jean Luc Damoiseaux L S LT V 12 Syst me d Exploitation G n ralit s cat fichier crit les fichiers sur la sortie standard chmod arg fichier modifie les droits d acc s un fichier more fichier affiche page par page sur la sortie standard le contenu des fichiers find ref arg permet de rechercher r cursivement partir de la r f rence ref les fichiers satisfaisant l expression bool enne d duite des arguments arg L argument name nom _ fichier permet de sp cifier le nom du fichier che
78. thmes supposent que le pilote accepte de nouvelles requ tes pendant le traitement d une premi re requ te Ceci est rendu possible par l utilisation d une table index e par les num ros de cylindres o chaque entr e pointe sur le premier l ment d une liste cha n e des diff rentes requ tes concernant un cylindre En outre quelques contr leurs permettent au pilote de conna tre le num ro de secteur situ sous la t te autorisant alors une autre optimisation le pilote peut pour deux requ tes concernant le m me cylindre commencer par celle dont le secteur passera en premier sous la t te 1 2 2 Le traitement des erreurs Lors de l exploitation d un disque le pilote doit traiter des erreurs logiques ou physiques Les plus courantes sont Jean Luc Damoiseaux I S LT V 41 Syst me d Exploitation La m moire secondaire les erreurs de programmation par exemple la demande d un bloc qui n existe pas le positionnement sur un secteur ou un cylindre inexistant l utilisation d une t te inconnue etc en r gle g n rale le contr leur v rifie les param tres fournis par le pilote et ne les accepte pas s ils sont incorrects En th orie inexistantes ces erreurs lorsqu elles se produisent sont trait es lors de la mise jour du syst me les erreurs de total de contr le le contr leur v rifie par le calcul d un checksum la validit des informations transf r es Lors de la pr sence de poussi res ou de blocs end
79. tr e dans une table contenant ces attributs par exemple Jean Luc Damoiseaux I S LT V 44 Syst me d Exploitation La m moire secondaire son type ses propri taires ses droits d acc s etc Une telle entr e est appel e un noeud d information ou i node 3 1 La structure arborescente Gr ce la notion de r pertoire le syst me de gestion des fichiers d UNIX est organis sous la forme d une arborescence Cette arborescence repose essentiellement sur l association faite dans les r pertoires entre les noms des fichiers et leur num ro d index la d signation ext rieure d un fichier est r alis e en utilisant un lien associ ce fichier dans un r pertoire ce r pertoire tant lui m me d sign par le m me m canisme dans un autre r pertoire Pour tre op rationnelle cette organisation arborescente suppose une origine symbolique appel e la racine absolue not e et situ e un adresse fixe du disque Cette structure arborescente a t normalis e sous UNIX figure n 3 et se d compose en l ensemble des r pertoires suivants bin contient la plupart des utilitaires UNIX dev contient les fichiers sp ciaux etc contient les programmes et les tables d administration du syst me 1ib contient les biblioth ques utilis es par des langages de programmation tmp est utilis pour les fichiers temporaires usr contient des r pertoires utilis s par le syst me plus les r pertoires des
80. tre les pages virtuelles et les pages physiques Une telle organisation permet une page virtuelle qui passe le plus clair de son temps en m moire secondaire d tre implant e dans n importe quelle page physique 3 2 1 La pagination un niveau Dans le m canisme de pagination un niveau figure n 8 une adresse virtuelle est compos e de deux parties un num ro de page p et un d placement d l int rieur de la page les P bits de gauche d une adresse de N bits fournissent un num ro de page et les N P bits de droite le d placement dans la page La taille de la page est 2N P La traduction d une adresse virtuelle en une adresse r elle est r alis e par la table des pages situ e dans l espace m moire r el et dans laquelle les entr es successives correspondent aux pages virtuelles cons cutives La pi me entr e de cette table contient le num ro r de la page o est implant e la page virtuelle p L adresse r elle r d d un mot d adresse virtuelle p d est donc obtenue en rempla ant le num ro de page p par le num ro de case r trouv e dans la table pvl pv2 pv3 pv4 pv5 pv6 m A table a des pages space m moir r el space m moir virtuel Figuren 8 Principe de la pagination un niveau Lorsque le m canisme de traduction des adresses utilise des tables de pages situ es dans l espace m moire r el toute traduction ralentit consid rablement le processeur Pour viter
81. ues et inconnues Tr s simplement nous avons associ au compte du client la variable bool enne compte_utilise commune aux deux processus et prenant la valeur vraie ou faux selon qu un processus utilise ou non la ressource compte client Dans le cas d une machine multiprocesseurs et avec la variable compte utilise initialis e faux chaque processus acc de en m me temps celle ci et donc la teste avant que l autre ne lui ait affect la valeur vraie Pour chacun des processus la valeur m du compte est alors lue et la valeur finale du compte sera gale m m oum mo selon que le processus ou le processus modifie le compte en premier au lieu d tre gale m m M Dans le cas d une machine monoprocesseur et avec la variable compte_utilise initialis e faux le processus acc de la variable compte_utilise et la teste puis se trouve interrompu par le syst me qui donne la main au processus Le processus acc de alors la variable compte _ utilise et la teste Par cons quent les deux processus ont test la variable compte utilise avant que l un ou l autre des processus ne lui ait affect la valeur vraie ce qui conduit la situation pr c demment d crite L analyse de cet exemple montre que le probl me d crit vient d une part du fait qu un processus peut tre interrompu entre deux instructions et d autre part que des ressources critiques lorsqu elles sont utilis es par un processus doivent reste
82. urant peut tre ind finiment retard e si des demandes concernant des cylindres proches arrivent avec une fr quence suffisamment grande cette strat gie n est gu re utilis e dans la pratique En effet de part ce qui pr c de on en d duit que le temps moyen d ex cution d une demande est diminu alors que le temps maximum est Jean Luc Damoiseaux I S LT V 40 Syst me d Exploitation La m moire secondaire augment Il n y a pas quit entre tous les cylindres ce qui peut aller l encontre de certaines r gles de priorit s tablies entre plusieurs processus strat gie de l ascenseur dans cette m thode le bras du disque se d place dans un sens donn s arr te au dessus de chaque cylindre pour lequel des demandes existent et les traite Lorsque le dernier cylindre comportant une file non vide a t atteint et trait on change le sens de d placement et on recommence Les performances de cet algorithme sont en g n ral moins bonnes que celles de l algorithme SATF mais la contrainte d quit entre les cylindres est maintenant respect e 0 5 10 15 20 25 30 35 Hd BETTERETITITEETEEETETEE EE f Algorithme SATF Ordre des requ tes 11 1 36 16 34 9 12 0 5 10 15 20 25 30 35 Adii d P I I PETER c Algorithme de l ascenceur Ordre des requ tes 11 1 36 16 34 9 12 Figure n 2 D placement compar du bras du disque pour diff rents algorithmes d ordonnancement Il est noter que tous ces algori
83. us La anse natal rade end At AR ne 7 3 1 Synchronisation par s maphores priv s ss 7 32 Probl me des Philosophes et des Spaghetti 8 4 Les processus sous Unix aies ea e ne a E S 10 4 1 G n ralit s ht nl n E EE KEES ESEE E e E ESEE A TS 10 4 2 Cr ation de processus tos a i a a E a A aE aK S 11 4 3 Synchronisation de PIOCESSUS En amas en tte le ns ne 15 Chapitre 3 Gestion des processus 0ccooccccocccocccooccooccooccosocescccoccosccosccosccosvccesvccusccones 19 1 Contexte d un DrOC SSUS ne doi nn ten M nest niet 19 1 1 Informations utilis es par le processus 19 1 2 Informations utilis es par le syst me island 19 25 E Parall SMC E EN AN ne E ER RE N N Re ET 20 3 Allocation du processeur r el cccccccciccccccccccscccccccccccceccccseccssccssenesenenes 22 3 1 D finitron du promesse use nn ne Bee Cet denan En 22 Jean Luc Damoiseaux L S LT V 2 Syst me d Exploitation Table des mati res 3 2 Eedistributeur saene ne d AAA nn tnt 23 3 3 Changement de contexte entre deux processus 24 3 4 Strat gie d allocation du processeur 25 Chapitre 4 Allocation de la m moire ccocccoccoccooccocoooco0ce0c0o0c00ee00000000000000000000000000000e 28 P AIHONSES REINE EE CN ER ER ET 28 1 1 Espace m moire r el espace m moire virtuel 28 1 2 M moire Virtuelles es seules net nr oh Res
84. us sont trop courtes pour tre prises en compte dans la programmation d s l instant o plusieurs processus ont une ressource en commun l ordre dans lequel ils s ex cutent n est pas indiff rent Il appara t alors des probl mes de synchronisation et de communication entre les processus 2 Exclusion mutuelle L exclusion mutuelle est le probl me qui se pose lorsqu une ressource critique est n cessaire la continuation de plusieurs processus Pour mieux comprendre cette notion d exclusion mutuelle et les probl mes qui lui sont associ s tudions l exemple d un client d un magasin qui envoie deux commandes s par es pour deux articles diff rents le montant de l argent disponible sur le compte est m la premi re facture est d un montant m la seconde d un montant m Le service comptabilit traite ces commandes simultan ment gr ce au programme informatique suivant Jean Luc Damoiseaux I S LT V 2 Syst me d Exploitation Les Processus contexte commun compte_utilise FAUX compte_client 1000 corps du programme du processus i derniere _ facture m while compte utilise VRAI lt le probl me se situe ici compte utilise VRAI compte_client compte _ client derniere _ facture compte_utilise FAUX Chacune des factures tant associ e un processus i r alisant une facturation d un montant m Pour l instant nous supposerons que les deux processus ont des vitesses quelconq
85. utilisation LRU Least Recently Used la page ject e est la page la moins r cemment utilis e Jean Luc Damoiseaux I S LT V 36 Syst me d Exploitation Allocation de la m moire degr d utilisation LFU Least Frequently Used la page ject e est la page la moins fr quemment utilis e l algorithme optimal OPT s il existe des pages qui ne seront plus r f renc es alors remplacer l une de ces pages sinon remplacer la page qui sera le plus tardivement r f renc e Le dernier algorithme est totalement irr alisable car il est impossible de conna tre l avance le moment o les diff rents pages qui seront r f renc es Cependant cet algorithme sert de r f rence pour la comparaison des performances des autres algorithmes figure n 9 Toutefois au del de l ordre des performances il est important de noter que d une part les performances des algorithmes sont toutes proches de celles de l algorithme RAND et d autre part l influence de la taille m moire est tr s largement sup rieure celle de l algorithme de remplacement Nombre de d faut de page RAND FIFO LFU LRU OPT Taille de la m moire Figure n 9 Performances compar es des algorithmes de remplacement de page 3 3 La segmentation La pagination pr sente un espace m moire virtuel monodimensionnel puisque les adresses virtuelles sont continues entre les valeurs O et un nombre maximum Dans beaucoup de cas il est pr f

SYSTEME D`EXPLOITATION - Jean

Contents

Download Pdf Manuals

Related Search

Related Contents