en mode ma??
Contents
1. Une ex cution c est une volution discr te de l tat de la machine Un processus est un programme en cours d ex cution Il est d fini par Evolution des registres de la C P U des zones m moire code pile et donn es CO R1 R2 Code en cours M moire d un processus d ex cution 23 i 34 23 Doa LOAD RI 10 PILE CODE CST DATA K PILE SYSTEME 123 LOAD R1 25 10 34 N Eidi 124 10 5 I INC R1 R 125 INC R1 k 126 ADD R1 R2 26 11 34 L la valeur des registres de la CPU un MEP SR ADD RI1 R2 7e Fi un ensemble de ressources allou es Le tout forme le contexte d ex cution du processus Notion de points observables gt gt Les interruptions lt lt gt Rendez vous asynchrones Rendez vous asynchrone Interruption d un processus Interruption mat rielle Les appels syst me Les d routements Attente active Solution l attente active Soit F un indicateur qui signale l v nement si F 1 alors F 0 lt traiter l v nement gt fin si le test explicite est p nible et peu s curis perte de temps C P U Probl me Prise en compte rapide d un v nement tout en effectuant un travail Exemple Le travail ex cuter un processus consommateur de CPU pas d entr e sortie Les v nements g rer un paquet arrive sur la carte r s2. Les interblocages Un exemple d interblocage D finition Attente sans fin pour plusieurs processus d une ou plusieurs Un interblocage repr sent par un graphe d allocation des ressources ressources d tenues par d autres processus a Conditions d apparition La ressource 1 est d tenue par Le processus B r clame la les ressources ne sont pas partageables le processus ressource 1 Fe NI processus processus les ressources ne sont pas r quisitionnables A B chaque processus utilise simultan ment plusieurs ressources Le processus A Treo ue 2 est d tenue par le processus B r clame la ressource 2 il existe un ensemble de processus P1 P tel que P attend P 1 pour 1 lt i lt n 1 Ph attend P Pa P 1 prendre R 2 prendre R2 3 prendre R2 i 4 prendre R 5 6 Comment traiter les interblocages Pr vention des interblocages La politique de l autruche Diminuer le nombre de ressources qui ne peuvent tre r quisitionn es La Pr vention On impose des r gles strictes qui vitent l apparition interdire l acc s direct la ressource d un interblocage remplacer la ressource r elle par une ressource virtuelle L vitement On surveille l apparition d un interblocage en imposant des contraintes moins strictes exemple La d tection Un algorithme la charge de d
3. Il y a donc un branchement vers le code de traitement des interruptions le traitant avec un changement de mode gt Les appels syst mes principe lt Si les processus s ex cutent en mode utilisateur les entr es sorties directes leurs sont interdits gt Pour r aliser des E S les processus doivent envoyer des requ tes au syst me d exploitation gt L appel de fonction classique pose des probl mes le nombre de points d entr e est important le mode d ex cution reste esclave le code du syst me d exploitation est accessible en lecture LL gt Les appels syst mes moyens Les appels syst mes Avantages Les trappes Trap Appel explicite du syst me par le biais d une instruc tion qui d clenche une interruption Code utilisateur Librairie standard Processus en mode esclave en mode esclave en mode maitre switch RO LOAD RO SVC_OPEN LOAD Rl mon fic LOAD R2 WRITE SVC CMP RO 0 x open ficA WRITE case SVC_OPEN lt ouverture gt break RTS RTI Code du syst me d exploitation 12 gt Les appels syst mes Structure du traitant 1 sauvegarde du contexte 2 v rifier la conformit de la requ te v rifier la nature de la requ te v rifier la nature des arguments v rifier les droits du processus demandeur 3 ex cuter la requ
4. Soit libre une variable partag e de type bool enne pour coder l exclusion mutuelle init 1 libre vrai prologue 2 si libre faux aller en 2 3 libre faux 4 section critique pilogue 5 libre vrai Critiques Consommation de temps processeur L exclusion mutuelle n est pas toujours respect e 2 interruption 2 3 4 retour au rouge 3 4 La proc dure embpiler devient proc dure embpiler var p pile d entier prologue p sommet p sommet 1 p data p sommet d pilogue Nouvelle ex cution thread1 empiler p 10 thread1 prologue thread1 p sommet p sommet 1 interruption thread2 empiler p 20 thread2 prologue blocage du thread 2 retour au thread 1 thread1 p data p sommet 10 thread1 pilogue reprise du thread 2 thread2 p sommet p sommet 1 thread2 p data p sommet 20 thread2 pilogue blocage des interruptions init 1 libre vrai prologue 2 soit p une variable priv e 3 r p ter 4 masquer les interruptions 5 p libre 6 libre faux 7 r tablir les interruptions 8 pilogue 9 Critiques jusqu p vrai section critique libre vrai L ordre d arriv e n est pas respect Risque de privation C est une solution mono processeur Utilisable uniquement en mode ma t
5. Implantation au niveau utilisateur Java une librairie se charge de la gestion des threads cr ation la commutation entre threads d un m me processus est plus rapide la r partition de la CPU n est pas quitable la mise en attente d un processus entra ne le blocage de tous ses threads 13 Allocation de la CPU gt Allocation du processeur 4 lt Allocation de la CPU Strat gies d allocation Les algorithmes d allocation FIFO SJF SRT HRN Le tourniquet Le tourniquet multi niveaux 14 Il y a perte de la CPU dans trois cas interruption ext rieur d routements appels syst me Quel type d allocation le long terme variation du degr de multi programmation par swapping out les processus sont copi s en m moire secondaire swapping in les processus sont rapatri s en m moire centrale le moyen terme d termine et classe les processus pr ts le court terme r partition de la CPU 15 gt Strat gies d allocation Objectifs quit d bit maximum maximum de processus interactifs rationaliser la gestion des ressources favoriser les bons processus am liorer les temps de r ponse moyen Crit res le taux d E S le taux d utilisation de la CPU le type et la priorit du processus temps CPU cumul temps CPU restant tau
6. a M moire centrale A ML MC MI Moniteur Pr paration du lot 1 t t Pr paration du lot 2 Ex cution du lot 1 R RL Pr paration du lot 3 Ex cution du lot 2 Impression du lot 1 Cycles de CPU et d entr e sortie Chaque processus encha ne des cycles de CPU ex cution de code et des cycles d entr e sortie Attente CPU k H E S cu Hit 4 h E S h 10 Apparition des terminaux 60 70 Int gration des terminaux les terminaux sont connect s au serveur les utilisateurs travaillent devant le terminal ils partagent leur temps entre r flexion et action Hypoth se 1 Le temps de r flexion est de 90 donc sur 100 utilisateurs 10 sont actifs Hypoth se 2 Les utilisateurs actifs r clament des actions simples prise en compte du travail interactif 12 Multiprogrammation D but 60 Multiprogrammation Pr sence simultan e de plusieurs pro grammes en m moire centrale Unit d E S P riph riques Unit d E S Y M moire centrale RAM Nouvelles caract ristiques E S tamponn es d finition d un canal d E S r implantation du code protection de la m moire 11 60 70 Le temps partag Le temps d ex cution de la CPU est d coup en tranches PO P1 P2 PO P1 P2 PO PU lt a a Temps Quanta Quanta 50 millise
7. Objectifs quilibrage de la charge homog n it des taux d utilisation de la C P U vitez les effets de pompage Syst me simple le S E s ex cute toujours sur la m me C P U Syst me plus sophistiqu le S E est capable de s ex cuter en parall le sur plusieurs processeurs Il faut g rer les probl mes de synchronisation 27 gt M lange Temps R el et temps machine lt Le temps C P U peut tre divis en une partie fixe r serv e au processus Temps R el et une partie reserv e aux autres processus v nement attente TR Autres TR Autres Les algorithmes pr c dents s appliquent dans la partie T R Les algorithmes classiques sont utilis s par la partie Autres 26 gt gt Pr sentation g n rale lt lt Le probl me Acc s des ressources partag es Les sections critiques Le probl me de l exclusion mutuelle Solutions d attente active Une solution d attente active blocage des interruptions Algorithme de Peterson 2 processus Solution mat rielle Solutions de manipulation des processus Les verrous Les s maphores Le producteur et le consommateur Les s maphores messages Les r gions critiques Les sections critiques Les ressources logicielles ou mat rielles qui posent des probl mes sont dites critiques Les portions de code qui manipulent ces ressources
8. critiques sont appel es des sections critiques Les notions de ressource critique et section critique sont utiles pour les threads d un processus utilisateur pour les donn es du syst me d exploitation partag es par les processus Acc s des ressources partag es Soit une pile partag e par plusieurs threads pile structure sommet entier data tableau 1 Max de entier proc dure embpiler var p pile d entier p sommet p sommet 1 p data p sommet d Il est possible que nous ayons threadi embpiler p 10 threadi p sommet p sommet 1 interruption thread2 embpiler p 20 thread2 p sommet p sommet 1 thread2 p data p sommet 20 retour au thread 1 threadi p data p sommet 10 Le probl me de l exclusion mutuelle Contraintes Forme des programmes initialisation ex cut une seule fois prologue section critique pilogue Il existe au plus un processus en section critique Les processus ne sont pas bloqu s sans raison absence de privation Les sections prologue et pilogue sont les m mes pour tous les processus uniformit Conflit avec deux threads Le prologue et l pilogue encadrent la section critique Le probl me est r gl en augmentant la dur e d ex cution du prologue Une solution d attente active Nouvelle formulation
9. dessous s ex cutent en exclusion mutuelle proc dure P var s s maphore S C S C 1 si s c lt 0 alors soit P le processus appelant entrer le processus P dans la file s f suspendre le processus P fin si proc dure V var s s maphore S C S C 1 si s c lt 0 alors sortir un processus Q de la file s f reprendre le processus Q fin si P pour proberen tester ou wait V pour verhogen incr menter ou signal 18 Les s maphores simul s par des verrous s maphore structure blocage verrou mutex verrou c entier proc dure init var s s maphore co entier v rifier que co gt 0 S C co init s blocage init s mutex 20 Les s maphores simul s par des verrous proc dure P var s s maphore prendre s mutex S C S C 1 si s c 1 alors lib rer s mutex prendre s blocage prendre s blocage sinon si s c lt 0 alors lib rer s mutex prendre s blocage sinon lib rer s mutex fin si proc dure V var s s maphore prendre s mutex SC s c 1 lib rer s blocage lib rer s mutex 21 Le probl me du producteur et du consommateur Les s maphores priv es Il existe un tampon de taille limit entre le producteur et le consommateur Algorithme du producteur r p ter produire un message le d poser dans le tampon jusqu Algorithme du consommateur r p
10. du syst me d E S Y LA Gestion des interruptions ja Drivers de p riph riques interface vers le mat riel y y Machine physique 21 gt gt Pr sentation des processus lt lt Notion de programmes Notion de machine Ex cution d un programme Processus Notion de machine Notion de programme Une machine Processeur CPU M moire Organes d E S Contr leurs Canaux L tat d une machine c est l tat de ses composants Un programme est une suite d instructions rang es en m moire void main 2048 gt 2052 2056 2060 privil gi es Instructions ordinaires Description du processeur LOAD RI 01001001011101101 10011111001010100 INCRI ADDRI R2 11101010001100101 Lancement des E S Contr le des interruptions Contr le du mat riel mouvement de donn es structure de contr le calcul appel du syst me d exploitation Registres sp cialis s Un Mot d tat A Entier processeur MEP Registres processeur TS Flottant g n raux Adresse Unit de calcul UAL compteur ordinal CO Registres _ sp cialis s mode d ex cution MODE pointeur de pile SP masque d interruptions codes de conditions en mode esclave les instructions privil gi es sont interdites en mode ma tre les restrictions disparaissent Ex cution d un programme Notion de processus
11. gt gt Chapitre 1 Pr sentation g n rale lt lt Notion de Syst me Informatique D finition fonctionnelle Machine de traitement de l information qui assure Notion de Syst me Informatique le stockage des donn es l ex cution des programmes Les fonctions d un syst me d exploitation Structure en couches Historique et volutions Structure interne d un syst me d exploitation Logiciels d application Les 2 Outils et Services EA Syst me d Exploitation Composantes d un syst me d exploitation Logiciel de base Machine physique 2 3 Les fonctions d un syst me d exploitation gt gt Historique des S E lt lt Gestion de l information Fin 40 Organisation en porte ouverte Structuration codage fichiers Conservation fichiers m moire Le temps d acc s la machine est structur en p riode de 30 minutes Transfert E S transparentes Chaque p riode est allou e un utilisateur Partage entre plusieurs t ches FA A la fin de la p riode la machine est r initialis e Sean des Re GRS L utilisateur doit attendre la p riode suivante Allocation Arbitrage Partage diminution des co ts Abstraction simplification de s f Avantage Chaque utilisateur a la machine pour lui tout seul Autres services S curit traitement des erreurs valuation Statistique Facturation Outils dive
12. s c 1 si s c lt 0 alors sortir un processus Q de la file s demandeurs reprendre le processus Q fin si 27 D finition s ma mesg structure c entier demandeurs file FIFO de processus messages file FIFO de messages 26 Les r gions critiques Soit une pile partag e par plusieurs threads pile structure partag e sommet entier data tableau 1 Max de entier proc dure embpiler var p pile d entier r gion p quand sommet lt Max sommet sommet 1 data sommet d fin de r gion proc dure d piler var p pile var d entier r gion p quand sommet gt 0 d data sommet sommet sommet 1 fin de r gion 28 Les r gions critiques simul es par s maphores L instruction r gion p quand condition r gion critique fin de r gion peut se coder par var mutex s maphore 1 blocage s maphore 0 nbEnAttente entier 0 29 P mutex tant que non condition nbEnAttente nbEnAttente 1 V mutex P blocage P mutex r gion critique r p ter nbEnAttente fois V blocage nbEnAttente 0 V mutex gt Gestion des ressources lt D finition d une ressource Allocation de ressources D finition d une ressource Objectif de l allocation de ressources Le graphe de l allocation de ressources Les interblocages D finition Comment traiter le
13. RS z5 R5 R4 R2 lazi azi a l Ci TT TT N N R4 R2 P3 lazi lazi a l Ci ae fazi N N 14
14. ads est une op ration plus simple Les processus monolithiques 10 Il existe un conflit entre entr es sorties synchrones bloquantes interface homme machine IHM E i i i 1 g r seau Boucle des v nements l Gestionnaire disque de la file 1 i i des v nements i i e cd r cup rer un i v nement i i i i i i Y i i 1 4 a 1 Ev nements Traiter asynchrones i i Processus monolithique Solution d attente active E S asynchrones non bloquantes structure avec boucle d v nements Les processus multi threads Il existe un autre solution bas e sur le d coupage en plusieurs threads une utilisation des E S synchrones un module de communication i r seau gt Thread Gestion r seau T d disque 1 Thread Gestion disque m Communication et Thread Gestion de l IHM m synchronisation Thread Gestion de la m moire DE Ev nements asynchrones g Processus multi threads Avantages plus grande simplicit du code ind pendance entre les modules LT 12 Implantation des threads Implantation au niveau du S E le S E conna t et ordonnance les threads la r partition de la CPU est bonne les structures du S E sont alourdies
15. age de l exclusion mutuelle avec une variable partag e mutex et une variable priv e p initialisation 1 mutex 1 prologue 2 r p ter 3 TAS p mutex 4 jusqu p 1 5 section critique pilogue 6 mutex 1 Critiques Consommation de temps processeur Risque de privation cela peut s arranger Le processeur doit garantir l exclusion mutuelle C est une solution utilisable uniquement sur des s quences br ves 12 Les verrous Objectifs ne plus perdre de temps CPU simplicit de la solution D finition des verrous verrou Structure libre bool en f file FIFO de processus proc dure init var v verrou v libre vrai v f Un verrou est une structure de donn e partag e du syst me d exploitation 13 L exclusion mutuelle avec les verrous soit var mutex verrou le code de l exclusion mutuelle s crit initialisation 1 init mutex prologue 2 prendre mutex section critique pilogue 3 lib rer mutex 15 Les verrous 2 Pour un verrou donn les deux proc dures ci dessous s ex cutent en exclu sion mutuelle proc dure prendre var v verrou si v libre faux alors soit P le processus appelant entrer P dans la file v f suspendre le processus P sinon v libre faux fin si proc dure lib rer var v verrou si la file v f est vide alors v libre vrai s
16. ang es dans un PCB Process Control Block 3 Repr sentation des processus Gestion des processus Les PCB sont rang s dans des files r quisition allocation de la CPU processus file des processus pr ts actifs fin de l E S file des processus en attente de fin d E S demande d E S appel de exit file des processus morts gt Les threads processus de poids l ger Un thread fil est un programme en cours d ex cution qui partage son code et ses donn es Processus TE Thread 1 i Ex cution CODE MEP PILE Banes eaae aa a A Thread 2 i DATA Ex cution i IMEP PILE AEE EE E E A Fichiers Aa Thread Sen CES E i ouverts Ex cution i et Ressources MEP PILE ep br etes ag ini Lens tel rte s fe red ed def 2e de ed de D ms Se Chaque thread a une pile d ex cution autonome Un processus est compos de threads Cr ation de processus gt chaque processus peut cr er des processus ses fils il est possible de figer et de reprendre des processus il est possible de tuer des processus ou demander leur arret Communication entre processus gt pr voir des outils de communication fichier tube socket m moire partag e envoi d
17. condes et une requ te lt 1 quanta alors S N Temps de r ponse 10 x 50 ms Contraintes multiprogrammation temps de commutation faible possibilit d interruption propre 13 Les syst mes r partis 1980 Syst mes r partis R partition d une activit entre plusieurs ma chines reli es par r seau lent ou rapide Exemple Le Cluster La somme de plusieurs machines est vue comme une seule machine simplicit volutivit robustesse Un r sum de l historique 1950 1960 1970 1980 pas de traitement multi r Gros logiciels par lots utilisateurs syst mes ordinateurs f r partis moniteurs temps compilateurs partag pas de temps multi Mini logiciels partag utilisateurs ordinateurs i moniteurs compilateurs multi pas de compilateurs utilisateurs Les Micros compilateurs et temps moniteurs p 5 partag 14 Organisation en machines Une machine c est des objets des actions possibles des r gles de composition des actions Dans une structure en couches le S E est concu comme un empilement de machines MO MO MO i i Fa K M1 M1 M1 M2 4 X Z M2 M2 M3 M4 i i F M3 M3 M5 a b Avantages S curit et modularit 16 gt gt Structure interne d un syst me 44 15 Utilit des machines Ancienne machine MO et son sy
18. e messages Synchronisation de processus gt pr voir des outils de synchronisation verrou s maphore moniteur gt Programmation des threads begin void travail Instruction 1 int t co begin instruction1 if t thread 0 instruction3 Instruction 2 Instruction 3 co end thread exit Instruction 4 end instruction2 thread _join t instruction4 Trace de l ex cution CPUO lt Ins 1 gt lt Ins 2 gt lt Ins 4 gt CPU lt Ins 3 gt gt Utilit des threads tude des d pendances et d coupage CS d pend de C2 et C4 T C1 C2 C3 C4 cs C2 d pend de C1 C4 d pend de C3 1 c5 Thread 1 C3 C4 Thread2 Avantages r cup ration des temps d E S exploitation des machines multi processeurs coop ration entre threads gt Utilit des threads pour les serveurs Application serveur e Processus fils Processus gt Processus fils principal 1 Processus fils e Processus fils Processus serveur Thread fils Thread Thread fils principal Thread fils Thread fils Donn es globales La commutation et la communication entre thre
19. eau d placement de la souris activation du clavier apparition d une alarme gt Attente active suite pas de r action imm diate lt latence gt risque de collision lt cart gt lt latence gt cart minimum gt latence Interruption d un processus Principe Interruption op ration indivisible effectu e par la C P U qui change le Co et le MODE Les interruptions sont d clench es uniquement sur les points observables points interruptibles Chaque interruption a une cause identifi e par un entier Le vecteur d interruptions VI est une table log e dans les adresses basses de la m moire PUSH CO MODE MODE ma tre CO vi k interruption de cause k reprise apr s interruption POP MODE instruction RTI POP CO 5 Code Code du Vecteur utilisateur syst me d interruptions T o 0 123 LOAD RI 100 1 124 10 101 2 100 125 INCR1 102 8 126 ADDRI R2 103 RTI SE SA Evolution des registres de la C P U Evolution de la pile co MODE SP R1 R2 123 esclave 200 34 LOAD R1 10 f 125 esclave 200 10 34 lt interruption de cause n 2 gt 100 ma tre 201 10 34 lt 125 e gt 103 ma tre 201 10 34 RTI 125 esclave 200 10 34 lt 125 e gt INC RI SP 126 escla
20. inon v libre faux sortir un processus Q de la file v f r veiller le processus Q fin si 14 Difficult s des verrous soit deux processus qui partagent deux ressources var mutexli verrou mutex2 verrou init mutex1 init mutex2 P 1 prendre mutex1 2 prendre mutex2 3 section critique 4 lib rer mutex2 5 lib rer mutex1 P2 1 prendre mutex2 2 prendre mutex1 2 section critique 4 lib rer mutex1 5 lib rer mutex2 Il y a blocage pour la s quence Loris L ror use 16 Les s maphores Un verrou ne sait pas compter donc il faut remplacer le drapeau par un compteur Dijkstra Un s maphore est une structure de donn e partag e du syst me d exploi tation s maphore structure c entier f file FIFO de processus proc dure init var s s maphore co entier v rifier que co gt 0 S C Co sf f 17 Utilisation des s maphores Agir sur les s maphores Soient trois processus qui exploitent la m me ressource Pi F5 P3 1 PO 2 P S 3 4 vs 5 V s 6 v s P s La trace de l ex cution donne action 2 P1 Pi P 1 P s 1 SC A 2 P s 0 ISC SC A 3 P s 1 P3 h SC SC S 4 V s 0 A SC SC 5 V s 1 4 A A SC 6 V s 2 A A A 19 Pour un s maphore donn les deux proc dures ci
21. r e du quanta Tourniquet round robin c est FIFO plus un m canisme de r quisition arriv e F CPU sortie r quisition pr emption Temps de r ponse moyen quantum 21 22 gt Tourniquet Muilti niveaux gt Tourniquet Multi niveaux avec priorit s r quisition pr emption niveau 0 puna niveau 1 m 7 niveau2 l niveau n 1 m l LA niveau n arriv e gt CPU sortie I existe des classes de processus processus syst mes processus temps r el processus interactifs processus d dition interactive processus batch Chaque classe et absolument prioritaire sur celles de niveau inf rieur A l int rieur de chaque classe les processus sont rang s dans un syst me de files multi niveaux 23 24 Le cas des processus temps r el Prise en compte d un v nement v nement Prise en compte temps 4 Lt attente si n est le nombre de processus temps r el s le temps pris par l ordonnanceur t le temps moyen pris par les processus T R alors n 1 x s t lt attente 25 Allocation multi processus Hypoth se on dispose de N processeurs identiques
22. re Solution pour deux processus Soit tour une variable enti re partag e var tour entier Voila le codage pour le processus P initialisation 1 tour 0 prologue 2 r p ter 3 jusqu tour i pilogue 4 tour 1 i Critiques L ordre est fix priori avec alternance Risque de privation blocage inutile Il n y a pas de m moire de l tat des processus Solution mat rielle On introduit une nouvelle instruction Test and Set pour garantir l atomicit d une modification construire une solution bas e sur l attente active valable en multi processeurs D finition de Test and Set instruction TAS var m entier var verrou entier bloquer la case m moire verrou m verrou verrou 0 d bloquer la case m moire verrou CO CO taille de l instruction TAS LT Algorithme de Peterson pour deux processus On ajoute une variable demande pour repr senter l tat des processus var tour entier demande tableau 0 1 de bool en Voila le codage pour le processus P initialisation 1 tour 0 2 demande faux faux prologue 3 demandeli vrai 4 tour 1 i 5 r p ter 6 jusqu tour i ou demande 1 i faux pilogue 7 demandeli faux C est une solution correcte pour le probl me de l exclusion mutuelle deux processus 10 Utilisation de Test and Set Cod
23. rocesseur 68000 chaque point interruptible la C P U g n re un d routement le syst me r cup re donc le contr le entre chaque instructions il peut visualiser l volution des registres 16 gt Gestion des processus lt lt gt tat d un processus tat d un processus Chaque processus est dans l un des tats op rationnels suivants Repr sentation d un processus pa nn pr t R le du PCB i i Repr sentation des processus L 1 initialisation Les threads processus de poids l ger connu 2 ex cution nat 4 2 3 ach vement Utilit des threads 4 pr emption termin 5 attente Implantation des threads 6 signal 5 y 3 actif 1 gt Repr sentation d un processus lt gt R le du PCB Pour chaque processus le syst me maintient Le r le du PCB dans la commutation entre deux processus un identifiant pid PO P1 un tat op rationnel l 1 I un contexte d ex cution E 1 amp a des informations diverses sauvegarde restauration priorit s ER l filiations propri taire z o us amp PCBO PCB1 F des statistiques 5 temps CPU t nombre d E S nombre de d fauts de page restauration sauvegarde D amp 5 S l i Ces informations sont r
24. rs sauvegarde recherche Inconv nient Le travail doit tre d coup en tranche de 30 minutes Le moniteur humain de gestion des travaux Le moniteur logiciel d encha nement des travaux Apparition d un op rateur de gestion des travaux D but 50 Moniteur logiciel d encha nement s quentiel des travaux Il assure les fonctions Utilisateurs y de compilation des travaux Travaux de chargement en m moire d enchainement des travaux Moniteur File des travaux en attente Travail courant chargement du moniteur compilateur compilation en m moire du travail 1 ex cution du travail 1 chargement du moniteur compilateur compilation en m moire du travail 2 ex cution du travail 2 Il r cup re les travaux g re la file d attente et enchaine les ex cutions 6 7 Le moniteur logiciel r sidant Le traitement par lots Milieux des ann es 50 Moniteur logiciel r sidant d encha nement s quen Fin des ann es 50 Traitement par lots Apparition du parall lisme des tiel des travaux Il assure les fonctions t ches entre lecture calcul et impression d encha nement automatique des travaux f f Machine Machine Machine de protection de la m moire de lecture de calcul d impression de limitation de dur e de supervision des entr es sorties Bandes magn tiques Bandes magn tiques d entr e de sortie
25. s interblocages Pr vention des interblocages vitement des interblocages L algorithme des Banquiers D tection des interblocages Gu rison des interblocages Objectifs de l allocation de ressources Les allocateurs de ressources doivent tre quitables en respectant les priorit s viter la privation attente sans fin d une ressource viter l apparition d un interblocage viter une congestion en veillant identifier une demande excessive de ressources ne pas accepter de demandes quand le syst me est en surcharge Une ressource est un objet utilisable par une t che Elle est caract ris e par un tat libre ou allou e l existence d un mode d emploi l existence d un allocateur qui r pond aux requ tes On distingue les ressources banalis es qui ont des occurences multiples imprimantes canaux d E S r quisitionnables CPU m moire physiques ou logicielles partageables o r entrantes pour le code d un programme Le graphe de l allocation de ressources L tat des ressources allou es est d crit au moyen d un graphe de l alloca tion de ressources Un processus P et une ressource Rj ayant 3 occurrences sont d crits par Pi Rj Les demandes d allocations et les ressources allou es sont d crits par R1 P1 r clame a P1 une ressource de type R1 R2 Une ressource b O gt P1 de type R2 a t allou e P1
26. source suppl mentaire Cons quences solution parfaite tr s mauvaise utilisation des ressources programmes difficile crire 10 L algorithme des Banquiers e Un processus P peut s ex cuter ssi Vj 1 M max alloc j lt dispo e Les indices k1 kn forment un ordre d ex cution si et seulement si les processus P avec i 1 n peuvent s ex cuter dans cet ordre les uns apr s les autres e Un syst me d allocation de ressources est dit sain si il existe un ordre d ex cution Il n y aura pas d interblocages dans un syst me sain Algorithme d allocation de Rj P dispo gt 0 les annonces sont elles respect es si R est allou e P l tat est il sain si la r ponse est n gative suspendre le processus P SSL SEE 12 D tection des interblocages P7 P8 P9 er 1 P7 O R6 P8 R6 C8 P9 Gu rison des interblocages he R duction par P9 fo R duction par P8 P7 P8 R6 R7 P9 R duction par P7 P7 i P8 R6 O R7 P9 13 D tection des interblocages suite Solution Tuer un processus pour lib rer des ressources mais quel processus Introduction des transactions 15
27. st me S0 On souhaite d velopper un syst me S1 sur une nouvelle machine M1 M1 S1 Un simulateur de M1 sur MO est utilis Simulateur M1 S1 dev 17 Organisation objet Un objet c est une repr sentation interne externe des fonctions d acc s M moire Sp cialisation Pi LL Abstraction M moire M moire centrale secondaire M moire M moire Disques Disquettes Virtuelle physique Avantages S curit modularit abstraction et sp cialisation 18 Un deuxi me exemple L architecture Micro noyau par opposition aux structures monolithiques des syst mes x lt 2 ae q rs LA N amp Ale S S 6 S A 72 Q O mA A A Micro Noyau MACH du M IT Tache ES Mem Virt Mat riel Avantages Portabilit Qualit 20 Un premier exemple Les machines virtuelles d IBM VM CMS N Nn Nn N Nn H H H mi 5 5 i 5 2 2 2 2 2 S 5 S S S A 2 2 A 4 2 5 a E O EE a E 5 D 5 Z 5 Noyau Noyau Noyau Noyau Noyau Noyau Machine virtuelle Mat riel 19 Composantes d un S E processus utilisateur interpr teur de commandes interface d appel au syst me SVC y Gestion des processus m Gestion des fichiers y y Gestion de la m moire centrale a Gestion
28. te 4 choisir le prochain processus p ex cuter 5 restaurer le contexte de p 6 relancer le processus p 14 Avantages des appels par interruption Changement de mode gt Le nombre de points d entr e est limit On obtient un sas qui isole le syst me d exploitation gt D finition d une nouvelle machine ajout d instructions gt Une librairie standard offre une interface syst me agr able et simplifi e une interface ind pendante du syst me d exploitation l implantation r elle des appels syst mes en assembleur 13 gt D routements Principe L objectif des d routements est double gt traitement syst matique des erreurs ou des situations anormales d faut de page gt protection et bonne utilisation de la machine les processus s ex cutent sous surveillance Si l ex cution d une instruction produit une erreur alors il y a interruption et branchement vers le code de traitement des erreurs du syst me Les causes possibles sont donn es incorrectes division par z ro op ration interdite instruction privil gi e instruction inconnue acc s une zone m moire interdite erreur de bus m moire 15 gt D routements Exemples lt gt Implantation d une gestion utilisateur des erreurs fonction signal gt Gestion de la m moire virtuelle Ajout de nouvelles instructions par simulation logicielle Le mode TRACE sur le p
29. tecter les interblocages processeur processus m moire m moire virtuelle imprimante queue d impression cran double buffer display machine machine virtuelle La gu rison Suppression ventuelle de l un des processus Pr vention des interblocages Contrainte 1 Classer les ressources suivant un ordre et respecter cet ordre lors des demandes de ressources La condition d attente circulaire est impossible donc pas d interblocage possible Cet ordre doit respecter une certaine logique mais laquelle La contrainte est tr s lourde La portabilit des applications est m diocre Que faire quand on ajoute une nouvelle ressource vitement des interblocages On vite les interblocages en adoptant un comportement prudent C est l algorithme des banquiers le S E conna t les demandes maximales les allocations lib rations sont libres Structures de donn es M nombre de classes de ressources N nombre de processus dispo pour i 1 M MaX j pour i 1 N j 1 M alloc pour i 1 N j 1 M 11 Pr vention des interblocages suite Contrainte 2 Annoncer les demandes de ressources avant de d marrer un processus Contrainte 3 chaque demande d allocation d une ressource suppl mentaire il faut lib rer toutes les ressources d tenues et les redemander en y ajoutant la res
30. ter pr lever un message depuis le tampon le consommer jusqu 23 Soit sempriv un s maphore priv de P4 et mutex un s maphore ordinaire P P mutex si le blocage est inutile alors V sempriv fin si V mutex P sempriv Ps P mutex si le processus P doit tre d bloqu alors V sempriv fin si V mutex 22 Codage du producteur consommateur Le consommateur consomme si le tampon n est pas vide NPlein s maphore 0 producteur r p ter produire un message le d poser dans le tampon V NPlein jusqu Consommateur r p ter P NPlein consommer jusqu 24 Codage du producteur consommateur 2 Les s maphores messages D finition des s maphores NPlein s maphore 0 NVide s maphore n Le producteur produit si le tampon n est pas plein r p ter P NVide produire un message le d poser dans le tampon V NPlein jusqu Le consommateur consomme si le tampon n est pas vide r p ter P NPlein consommer V NVide jusqu 25 Proc dures proc dure Pm var s s ma mesg var m donn es S C s c 1 si s c lt 0 alors soit P le processus appelant entrer le processus P dans la file s demandeurs suspendre le processus P fin si sortir m de la file s messages proc dure Vm var s s ma mesg m donn es entrer m dans la file s messages S C
31. ve 200 11 34 Interruption d un processus Exemple Structure g n rale d un traitant Le code ex cut apr s une interruption est appel le traitant de cette interruption Les traitants ont la structure suivante 1 sauvegarde du contexte 2 traitement de la cause 3 restauration du contexte 4 retour au processus interrompu instruction RTI gt Utilisation des interruptions Interruption mat rielle principe lt Il existe trois types d interruptions Interruption mat rielle r action aux v nements ext rieurs Appel au superviseur appel explicite d une routine syst me D routement traitement des erreurs et des situations anormales Interruption mat rielle caract ristiques Le num ro associ chaque interruption mat rielle indique une priorit int int int int int niv5 niv 4 nivi niv3 niv 0 N OO O1 amp NN nm prise en compte de l int niv 3 Des instructions privil gi es permettent de masquer des niveaux armer ou d sarmer des niveaux d clencher des niveaux 10 Un signal lectrique est mis vers le processeur qui provoque une inter ruption Clavier C P U Souris C vid o Controleur diskO disk1 disk2
32. x de r quisition 16 Algorithme d allocation FIFO lt FIFO First In First Out absence de r quisition et croissance rapide du temps de r ponse arriv e gt sortie temps de r ponse temps d attente temps d ex cution temps d attente taille de la file FIFO x dur e moyenne d ex cution 17 gt Algorithmes d allocation SRT lt SRT Shortest Remaining Time c est SJF un m canisme de r quisition M mes contraintes que SJF On choisit le processus qui a le temps restant d ex cution le plus petit L arriv e d un nouveau processus peut interrompre le processus courant Cons quences On favorise les travaux courts Co ts d exploitation importants 19 gt Algorithme d allocation SJF SJF Short Job First absence de r quisition et risque de privation Temps 4 SJF de r ponse FIFO a Temps de service demand Il faut estimer le temps d ex cution des processus 18 gt Algorithmes d allocation HRN HRN Highest Response Ratio Next Le choix est bas sur le ratio w t ts ts p t avec w t t ta temps d attente ta date d arriv e ts temps d ex cution estim Si w t 0 les travaux les plus courts ts sont privil gi s 20 gt Algorithmes d allocation du tourniquet lt Comment fixer la du
Download Pdf Manuals
Related Search