Dr. Mohamed-Wassim YOUSSEF © 2010 [] Systèmes dexploitation Evolués M1 - ISI 1 ére année Mastere en Informatique Rappel // Basé sur

Dr. Mohamed-Wassim YOUSSEF 2010 [www.wassimyoussef.info] Systmes dexploitation Evolus M1 - ISI 1 re anne Mastere en Informatique Rappel // Bas sur le cours de Dr. Jaber Jemai Chapitre 01

2 Dr. Mohamed Wassim Youssef Systmes dexploitation volusM1- ISI 2010 Rappel Systmes dexploitation Avances 1. Dfinitions a. Processus / Threads b. Intrruption / Premption / Droutement 2. Le modle des processus a. Larborescence b. Le PCB c. Les tats dun processus d. Commutation de contexte 3. Ordonnancement des processus

Dr. Mohamed Wassim Youssef Systmes dexploitation volusM1- ISI 2010 Dfinition: Processus Le processus est un concept fondamental de tout systme dexploitation. Un processus est lunit systme qui permet lexcution dun programme. Un processus est un programme en excution. Il dfinit un objet dynamique tandis que le programme est un objet statique. Un processus est caractris par son pointeur de pile, ses instructions et ses donnes, Ces attributs dfinissent le contexte dun processus. 3 Pile dexcution (fonctions) Segment de code (instructions en langage machine) Segment de donnes (les variables) Composantes dun processus

Dr. Mohamed Wassim Youssef Systmes dexploitation volusM1- ISI 2010 Dfinition: Thread Un thread ou encore processus lger (lightweight process) est une unit dexcution de code. il est issu dun processus mais ne contenant que la pile dexcution. Un processus contient donc au moins un thread de contrle unique en plus de lespace dadressage (segments code et donnes). 4 Thread 1: remet en forme le document Thread 2: interaction avec lutilisateur Thread 3: crit priodiquement le contenu de la RAM sur le disque Exemple: traitement de texte multi-threaded: Disque Absbjshd Dnddjkjdq Hqdjlqdjl Jddmkm Djdlqjdjdq djdqkmkd Absbjshd Dnddjkjdq Hqdjlqdjl Jddmkm Djdlqjdjdq djdqkmkd Absbjshd Dnddjkjdq Hqdjlqdjl Jddmkm Djdlqjdjdq djdqkmkd clavier t1t1 t2t2 t3t3

Dr. Mohamed Wassim Youssef Systmes dexploitation volusM1- ISI 2010 Aspects matriels: Interruptions Les interruptions constituent une concept fondamental des systmes dexploitation. Une interruption est signal produit par un priphrique et envoy vers le processeur pour linformer de la fin dune E/S, la production dune erreur 5 ProcesseurContrleur dinterruptions Disque Horloge Clavier 1. Le priphrique a termin son E/S 4. Le processeur acquite linterrupt. 2. Interruption 3. Description de linterruption Comment se produit une interruption?

Dr. Mohamed Wassim Youssef Systmes dexploitation volusM1- ISI 2010 Intrruption / Premption / Droutement Une interruption est signal produit par un priphriques et envoy vers le processeur pour linformer de la fin dune E/S, la production dune erreur La premption est la capacit dun systme dexploitation multitche excuter ou stopper une tache planifi en cours dexcution en faveur dune autre tache Droutement : produit par une erreur interne au processus (prvisible, ex division par zro) 6

Dr. Mohamed Wassim Youssef Systmes dexploitation volusM1- ISI 2010 Modle des processus: Arborescence Les processus sont organiss sous forme dune arborescence ou chaque processus a un seul pre et peut avoir plusieurs fils. Un processus est identifi par un PID (Process IDentifier) et un PPID (Parent Process IDentifier). Exemple: Larborescence des processus sous Linux 7 init Login: Mot de passe: Login: Mot de passe: Terminal 1 Login: Mot de passe: Login: Mot de passe: Login: Mot de passe: Login: Mot de passe: Terminal 2Terminal n shell ls

Dr. Mohamed Wassim Youssef Systmes dexploitation volusM1- ISI 2010 Modle des processus: PCB Chaque processus est reprsent dans le systme dexploitation par une structure de donnes contenant toute information dcrivant le contexte du processus appel bloc de contrle (Process Control Bloc: PCB). Attributs dun PCB: PID et PPID, tat, Priorit, Compteur ordinal, Fichiers ouverts, Pointeurs: seg. code, seg. donnes, seg. Pile, Temps dexcution. 8

Dr. Mohamed Wassim Youssef Systmes dexploitation volusM1- ISI 2010 Modle des processus: tats Lorsquun processus sexcute; il change dtat. Il peut se trouver dans lun des trois tats principaux suivants: Prt (Ready) : le processus attend son tour pour sexcuter lu (Running) : les instructions sont en cours dexcution. Bloqu (Sleep) : le processus bloqu en attente dvnement: signal, E/S, 9 Nouveau Termin Bloqu Prt lu Graphe des tats dun processus

Dr. Mohamed Wassim Youssef Systmes dexploitation volusM1- ISI 2010 Modle des processus: Transitions 1. Cration du processus 2. Allocation du processeur 3. Fin du temps allou sur le processeur, lexcution du processus nest pas termine 4. Opration E/S 5. Fin opration E/S 6. Excution termine 10 Nouveau Termin Bloqu Prt lu Graphe des tats dun processus

Dr. Mohamed Wassim Youssef Systmes dexploitation volusM1- ISI 2010 Modle des processus: Commutation de contexte Sur un systme multiprogramm, le SE doit redonner le contrle du processeur dun processus un autre en effectuant des commutations de contexte. La commutation de contexte consiste a mmoriser le PCB du processus courant et charger le PCB du processus a lire. 11 Sauvegarde PCB 0 Sauvegarde PCB 1 Recharge PCB 1 Recharge PCB 0 P0P1 lu Inactif

Dr. Mohamed Wassim Youssef Systmes dexploitation volusM1- ISI 2010 Ordonnancement des processus tant donne un ensemble de processus prts, lOrdonnanceur (scheduler) du SE doit choisir quel processus lire en utilisant un algorithme dordonnancement. 12 P1 P2 P3 Pn Pi CPU Algo. dordonnancement

Dr. Mohamed Wassim Youssef Systmes dexploitation volusM1- ISI 2010 Quand invoquer lordonnanceur Chaque fois que le processus excutant est interrompu un processus excutant devient bloqu (4) un processus change dlu prt (3) un processus excutant se termine (6) Chaque fois quun nouveau processus est prt un processus se prsente en tant que nouveau (1) un processus change de bloqu prt (5) Lordonnanceur choisi un processus parmi les processus prts et lui alloue le processeur 13 Nouveau Termin Bloqu Prt lu

Dr. Mohamed Wassim Youssef Systmes dexploitation volusM1- ISI 2010 Ordonnancement des processus Un bon algorithme dordonnancement : 1. Chaque processus doit avoir sa part de temps CPU: quit. 2. Utiliser le temps processeur a 100%: efficacit. 3. Minimiser le temps de rponse en mode interactif. Il existe deux types dalgorithmes dordonnancement: 1. Ordonnancement sans rquisition (sans premption): excution dun processus jusqu sa terminaison. 2. Ordonnancement avec rquisition (avec premption): suspension possible dun processus lu mme sil na pas termin son excution. 14

Dr. Mohamed Wassim Youssef Systmes dexploitation volusM1- ISI 2010 Caractristiques des algorithmes dordonnancement Temps de rotation = date de fin date darrive Temps rotation moyen = temps rotation / nbr processus Temps attente = temps de rotation temps dexcution Temps attente moyen = temps attente / nbr processus 15

Dr. Mohamed Wassim Youssef Systmes dexploitation volusM1- ISI 2010 Algorithmes Ordonnancement 1. Premier Arrive Premier Servi (First Come First Served FCFS) Excution des processus dans leur ordre darrive chronologique. 2. Plus Court dAbord (Short Job First SJF): SJF sans rquisition: Le scheduler choisi le processus prt ayant le plus petit temps dexcution. Une fois un processus est lu, il nest jamais suspendu jusqu la fin de son excution. SJF avec rquisition (Short Next Remaining Time SNRT) A chaque instant, le scheduler cherche parmi les processus prts celui ayant le plus petit temps dexcution restant. 16

Dr. Mohamed Wassim Youssef Systmes dexploitation volusM1- ISI 2010 Premier arriv, premier servi (First come, first serve, FCFS) 17 Exemple:Processus Temps de cycle P124 P2 3 P3 3 Si les processus arrivent au temps 0 dans lordre: P1, P2, P3 Le diagramme Gantt est: Temps de rotation pour P1=(24-0), P2=(27-0), P3=(30-0) Temps de rotation moyen : (24+27+30)/3=17 Temps dattente pour P1= 24-0-24; P2= 27-0-3; P3= 30-0-3 Temps attente moyen: (0 + 24 + 27)/3 = 17 P1P1 P2P2 P3P3 2427300http://w3.uqo.ca/luigi/

Dr. Mohamed Wassim Youssef Systmes dexploitation volusM1- ISI 2010 Tenir compte du temps darrive! Dans le cas o les processus arrivent moment diffrents, il faut soustraire les temps darrive Exercice: rpter les calculs si: P1 arrive temps 0 et dure 24 P2 arrive temps 2 et dure 3 P3 arrive temps 7 et dure 3 Donc P1 attend 0 comme avant Mais P2 attend 24-2, etc. 18 P1P1 P2P2 P3P3 2427300 arrive P2arrive P3http://w3.uqo.ca/luigi/

Dr. Mohamed Wassim Youssef Systmes dexploitation volusM1- ISI 2010 Tenir compte du temps darrive! Exercice: rpter les calculs si: P1 arrive temps 0 et dure 24 P2 arrive temps 2 et dure 3 P3 arrive temps 7 et dure 3 FCFS Temps de rotation moyen = (24-0)+(27-2)+(30-7) /3= 24 Temps dattente moyen = ((24-0-24)+(27-2-3)+(30-7-3)/3 = (0 + 22 + 20 )/3 = 14 19 P1P1 P2P2 P3P3 2427300 arrive P2arrive P3http://w3.uqo.ca/luigi/

Dr. Mohamed Wassim Youssef Systmes dexploitation volusM1- ISI 2010 Exemple de SJF sans premption Exemple de SJF sans premption 20 ProcessusArriveCycle P107P107 P224 P224 P341 P341 P454 P454 SJF (sans premption) Temps de rotation moyen = (7-0)+(12-2)+(8-4)+(16-5) /4= 8 Temps dattente moyen = ((7-0-7)+(12-2-4)+(8-4-1)+(16-5-4))/4 = (0 + 6 + 3 + 7)/4 = 4 P1P1 P3P3 P2P2 7160 P4P4 812 P 2 arr. P 3 arr. P 4 arrhttp://w3.uqo.ca/luigi/

Dr. Mohamed Wassim Youssef Systmes dexploitation volusM1- ISI 2010 Exemple de SJF avec premption 21 ProcessusArriveCycle P107P107 P224 P224 P341 P341 P454 P454 SJF (premptive) Temps de rotation moyen = (16-0)+(7-2) + (5-4) + (11-7) /4 = 7 Temps moyen d`attente = (16-0-7)+(7-2-4)+(5-4-1)+(11-7-4)/4 = (9 + 1 + 0 + 2) /4= 3 P1 attend de 2 11, P2 de 4 5, P4 de 5 7 P1P1 P3P3 P2P2 4 2 11 0 P4P4 57 P2P2 P1P1 16 P 2 arr.P 3 arr. P 4 arrhttp://w3.uqo.ca/luigi/

Dr. Mohamed Wassim Youssef Systmes dexploitation volusM1- ISI 2010 Difficults majeures avec les mthodes discutes Premier arriv, premier servi, FCFS: Temps moyen dattente non-optimal Mauvaise utilisation des ressources sil y a apport continu de processus aux cycles longs (v. effet daccumulation) Plus court servi, SJF: Difficult de prvoir la dure du prochain cycle Famine possible des processus longs sil y a apport continu de processus aux cycles courts Donc besoin dune mthode systmatiquement premptive Le tourniquet si vous faites toujours les devoirs les plus courts en premier, vous pourriez avoir limpression de faire beaucoup mais vous pourriez ne jamais arriver aux plus longs si vous faites les devoirs dans lordre darrive, les longs pourraient vous bloquer pour longtemps donc votre solution est de donner un peu de temps chacun, cycliquement 22

Dr. Mohamed Wassim Youssef Systmes dexploitation volusM1- ISI 2010 Algorithmes Ordonnancement 3. Tourniquet (Round Robin RR, lalgorithme circulaire) Quantum Q Le temps processeur est diviser en intervalles de temps appels Quantum Q, chaque processus sexcutera exactement pendant son quantum. Le processeur sera rquisitionner: a. Le processus lu a puis son quantum, b. Le processus lu a fini son excution avant la fin de son quantum, c. Le processus lu demande une entre/sortie. 23

Dr. Mohamed Wassim Youssef Systmes dexploitation volusM1- ISI 2010 Exemple: Tourniquet tranche = 20 24 ProcessusCycle P 1 53 P 2 17 P 3 68 P 4 24 n Temps de rotation ? Temps attente moyen ? n Observez u temps de rotation et temps dattente moyens beaucoup plus levs que SJF u mais aucun processus nest favoris P1P1 P2P2 P3P3 P4P4 P1P1 P3P3 P4P4 P1P1 P3P3 P3P3 02037577797117121134154162

Dr. Mohamed Wassim Youssef Systmes dexploitation volusM1- ISI 2010 Algorithmes Ordonnancement 4. Ordonnancement avec priorit Le systme dexploitation ordonne les processus prts selon lordre dcroissant de leurs priorits et le processus a lire est celui avec la plus haute priorit. Les priorits utilises peuvent tre statiques ou dynamiques. Les priorits statiques ne changent pas au cours de lordonnancement. Les priorits dynamiques seront recalcules priodiquement aprs un intervalle de temps bien dfini. 25

Dr. Mohamed Wassim Youssef Systmes dexploitation volusM1- ISI 2010 A retenir Notions de processus et thread PCB Notions dintruption de premption et de droutement Etats dun processus Graphe dtats & transitions Algorithmes dordonnacement FCFS, SJF, SNRT, RR, avec Priorits 26

Documents

Dr. Mohamed-Wassim YOUSSEF © 2010 [] Systèmes dexploitation Evolués M1 - ISI 1 ére année Mastere en Informatique Rappel // Basé sur