[PDF] Travaux Dirigés 15 déc. 2016 considé

View - Download Travaux Dirigés

Previous PDF

Next PDF

Révision

Amine DHRAIEF

Mastère professionnel en

Modélisation, Bases de Données et

Intégration des Systèmes

ESEN, Univ. ManoubaSystèmes d'Exploitation Avancés

GESTION DE LA MÉMOIRE

Exercice I

•Considérez un système de gestion de mémoire qui a les caractéristiques suivantes : -Un adressage virtuel sur 32 bits (dont 14 bits pour les numéros de segments et 6 bits pour les numéros de pages) -Une taille de Page de 4Ko -Une mémoire physique de 1 Mo •Supposez que le système utilise la segmentation paginée

Exercice I

1.Quelle est la taille du plus grand

segment (en pages/Ko)?

2.Quelles sont les données manquantes à ce

problème pour traduire l'adresse virtuelle de

32 bits suivante : 0xAE854C9C en adresse

physique ? Si vous aviez ces informations, identifiez brièvement les étapes à suivre pour effectuer cette translation.

Exercice I

•Supposons maintenant que le système considéré utilise une pagination à deux niveaux, où les entrées du de la table de page de premier niveau sont sur 4 octets •La structure de l'adresse virtuelle est composée de #page niveau 1 (10bits)#page niveau 2 (10bits)Déplacement page (12 bits)

EXERCICE I

Exercice I

3.Si un processus utilise tout l'espace adressable qui lui est

fourni, combien de pages seront-elles nécessaires pour contenir toutes les tables de pages de ce processus

4.Un second processus nécessite 22Mo pour s'exécuter

entièrement (son code, ses données, pile...). La partie contenant son code est disposée dans sa mémoire virtuelle aux adresses suivantes [2Mo à 6Mo-1], les données sont quant à elles dans l'intervalle [12Mo à 21Mo-1]. Si nous devons charger les tables de pages associées à ces deux parties, combien de pages de niveaux 2 seront chargées en mémoire centrale.

Correction exercice I

1.@virtuelle : #seg. (14bits) | #p (6bits) | depl. (12 bits)

@ physique: #case (20bits) | depl. (12 bits) Plus grand segment : 26 =64 pages ou encore 26*212=256Ko

2.Il manque la table des segments qui va nous

indiquer la table de pages associée au segment désiré. Cette table des pages nous permettra d'obtenir le cadre associé à notre adresse. L'adresse physique est obtenue en remplaçant les numéros de segment et de page par le numéro du cadre

Correction exercice I

3. Table de premier niveau : nombre d'entrées = 210 entrées

•Nombre de table de second niveau = 210 tables •Chaque entrée d'une table de second niveau pointe sur un cadre de page •Nombre d'entrée par table de second niveau 210 entrées •→ nombre de cadres de pages = (210 tables de second niveau)*(210 entrées par table de second niveau) = 220 •Un déplacement de 12 bits = taille max d'une page 212 bits = 4* 210 bits = 4 Koctets •→ Taille totale en KOctets = 4 * 220 KO= 4* 210 * 210 KO = 4Go

Correction exercice I

4. Chaque entrée de la table des pages de niveau 2 est

associée à un cadre de 4Ko (212). Sachant qu'une table de pages de niveau 2 contient 210 entrées, elle référence 210 *

212 o =4Mo de la mémoire virtuelle. La première table de

niveau 2 référence la mémoire virtuelle comprise entre [0,

4Mo-1], la seconde [4Mo, 8Mo-1] et ainsi de suite.....

•pour le code → 2 tables de pages de niveaux 2 seront nécessaires (c-à-d 2 pages) •pour les données 3 tables de pages de niveaux 2 seront nécessaires (c-à-d 3 pages).

Exercice II: Taille de cache

•Soit la suite d'accès aux pages suivantes {0,1,2,3,1,2,3,4,2,3,4,5,1,0,2,3,2,5} •Une mémoire tampon de 3 pages •Faites l'analyse des fautes de pages pour les algorithmes PAPS et LRU •Lequel semble préférable ? •Si la mémoire tampon est portée à 4 pages, la conclusion change-t-elle?

Correction Exercice II

012312342345102325

0000333333333111333

1-11111144444400005

2--2222222225552222

L'analyse des fautes de pages pour les algorithmes

PAPS : la page la plus ancienne est remplacé

→ 11 défaut de pages

Correcition Exercice II

012312342345102325

0000333333333111333

1-11111144444400005

2--2222222225552222

LRU: La page qui n'a pas été uitilisée pendant le plus de temps qui est reitirée → 11 défaut de pages

Correction Exercice II

012312342345102325

0000000044444442222

1-11111111115555333

2--2222222222111115

3-333333333300000

L'analyse des fautes de pages pour les algorithmes PAPS : la page la plus ancienne est remplacé → 11 défaut de pages bien qu'on dispose plus de mémoire ANOMALIE DE BELADY: le taux de défaut de page PEUT CROITRE en même temps que le nombre de cadre de page alloués Fournir plus de mémoire à un processus n'accroit pas forcément ses performances

Correcition Exercice II

012312342345102325

0000000044444442222

1-11111111115555333

2--2222222222111115

3-333333333300000

LRU: La page qui n'a pas été utilisée pendant le plus de temps qui est retirée 11 défaut de pages bien qu'on dispose plus de mémoire ANOMALIE DE BELADY: le taux de défaut de page PEUT CROITRE en même temps que le nombre de cadre de page alloués Fournir plus de mémoire à un processus n'accroit pas forcément ses performances

Exercice III: algorithme LRU dans le pire cas

•Soit la suite d'accès aux pages suivantes: {0,1,2,3, 0,1,2,3,

0,1,2,3,....} et une mémoire tampon de 3 pages

1.Proposez une méthodologie d'échange qui soit optimale

pour ce cas précis

2.En moyenne, pour une longue séquence de ce genre, quel

est le nombre de fautes de pages de LRU par rapport à la solution optimal ?

3.Que se passe-t-il si on passe à la séquence {0,1,2,3,4,

0,1,2,3,4, 0,1,2,3,4, ...} avec un tampon de 4 pages ? Qu'en

déduire pour les performances de LRU par rapport à l'algorithme optimal ?

Correction Exercice III

•Avec LRU : il y a un défaut de page à chaque accès012301230123012301

0032103

1103210

2210321

Correction Exercice III

1.Avec MRU : Most Recently Used, on remplace la page utilisée la plus

récemment

2.Pour une séquence infinie de ce genre, il y a en moyenne une faute pour 3

accès. -Une page reste en mémoire pour 9 accès successifs, et il y a 3 pages en cache -LRU est 3 fois pire que l'algorithme MRU

3.avec une séquence {0,1,2,3,4, 0,1,2,3,4, 0,1,2,3,4, ...} avec un tampon de 4 pages

, LRU présentera toujours une faute par accès, MRU, une faute pour 4 accès.012301230123012301

001 1123
2230

Exercice IV

Une mémoire virtuelle à une taille de page de 1024 mots, 8 pages virtuelles et 4 pages physiques. Sa table des pages est la suivante :

1- Donner la liste des adresses qui provoquent un défaut de page.

2- Quelles sont les adresses physiques de 0, 3727, 1023, 1024,

7425, et 4196.

Correction Exercice IV

La taille de la page est 1024, Calculons pour

commencer les plages d'adresses de chaque page :

Correction Exercice IV

La table des pages indique que seules les

pages virtuelles 2, 3, 5, 7 provoqueront un défaut de pages. Ce qui correspond donc aux plages d'adresses 2048 à 3071, 3072

à 4095, 3072 à 4095 et 7168 à 8191.

@ physique = Taille de la page * n° de page réelle + Offset

Examen janvier 2012

Question de cours

1.Quels sont les deux dispositifs matériels qui permettent au

système d'exploitation la protection des processus en exécution ? les décrire brièvement.

2.Dire quelle est la différence principale entre les termes de

chacune des paires suivantes :

1.Une segmentation et une pagination

2.Une fragmentation interne et une fragmentation externe

3.Un évitement d'un interblocage et une prévention d'interblocage

4.Un ordonnancement préemptif et un ordonnancement non

préemptif

3.Citez 4 moyens de synchronisation multithread

Question de cours

1.Dans un système de gestion mémoire virtuelle à

pagination

1.Quand est-ce qu'un défaut de page se produit

2.Dans quel cas est-il nécessaire de réécrire la page sur l'espace

de swap

3.En déduire son coût en termes entrées/sorties disque

2.Dans le graphe d'allocation de ressources qui suit, dire

s'il apparaît un interblocage? Justifiez votre réponse.

CORRECTION QUESTION DE

COURS •Quels sont les deux dispositifs matériels qui permettent au système d'exploitation la protection des processus en exécution ? les décrire brièvement. -L'unité de gestion de la mémoire (MMU) empêche les processus d'écrire n'importe où dans la mémoire. -Les modes kernel/user empêchent les processus d'exécuter certaines instructions.

CORRECTION QUESTION DE

COURS •Une segmentaition et une paginaition ? •paritiitionnement de l'espace d'adressage logique/physique ; •La segmentaition considère la mémoire comme des espaces, ou des régions, dédiés à une uitilisaition pariticulière par exemple : le code d'un programme, les données, la pile, un ensemble de sous-programmes, des modules, un tableau, etc. La segmentaition relflète cettte organisaition. •la paginaition est un paritiitionnement qui exige les même tailles de pages et de cases.

CORRECTION QUESTION DE

COURS •Une fragmentaition interne et une fragmentaition externe?

-suite aux allocaitions mémoire des fragments très peitits ne seront jamais suiÌifiÌisant pour

contenir un processus (frag. Interne) alors que la fragmentaition externe apparaît suite à une demande d'espace conitigüe qui n'est pas disponible bien la somme des fragments séparés dépasse la taille demandée.

•Un évitement d'un interblocage et une prévenition d'interblocage ? -l'évitement garanitit qu'il ne peut y avoir d'interblocage suite à des restricitions alors que

la prévenition vériifie si l'état suivant est sécurisant ou pas. •Un ordonnancement préempitif et un ordonnancement non préempitif ?

-Si la cpu est allouée à un processus, elle peut lui être réquisiitionnée à tout moment

avant sa ifin alors que l'ordonnancement non préempitif garde le processeur alloué au processus du début à sa ifin.

CORRECTION QUESTION DE

COURS •Citez 4 moyens de synchronisation multithread ? - join (pthread_join()), mutex, sémaphore, et variable conditionnelle. •Dans un système de gestion mémoire virtuelle à pagination -Quand est-ce qu'un défaut de page se produit ? si bit de présence =0 dans la table des page ; c-à-d que la page demandée est absente en mémoire. -Dans quel cas est-il nécessaire de réécrire la page sur l'espace de swap ? si le bit de modification = 1 dans la table des pages ; c-à-d que la page demandée a été modifiée depuis son chargement. -En déduire son coût en termes entrées/sorties disque ? meilleur cas 1 E/S et au pire cas 2 E/S.

CORRECTION QUESTION DE

COURS •Dans le graphe d'allocation de ressources qui suit, dire s'il apparaît un interblocage? Justifiez votre réponse. -Pas d'interblocage car P2 (resp. P4) peut terminer et libérer une copie R1 (resp. R2) qui peut être allouée à P1 (resp. P3). De sa part P1 (resp. P3) termine et libère R1 et R2. En conclusion, le graphe est réduit de la des noeuds isolés.

12/15/16Systèmes d'Exploitaition et Programmaition

Concurrente 29

SYNCHRONISATION &

CONCURRENCE

Coiffeur endormie

•Soit un salon de coiffure avec -un coiffeur, -un fauteuil de coiffure -et n chaises pour les clients qui attendent. • En l'absence de clients, le coiffeur s'assoit dans le fauteuil et s'endort. •Le premier client qui arrive réveille le coiffeur. •Les clients suivants doivent s'asseoir sur une chaise (s'il y en a de libres) ou partir (si toutes les chaises sont occupées). •Completer le programme du coiffeur et des clients en évitant les interblocages

Coiffeur endormie

Coiffeur endormie

Define CHAIRS 5

typedef int semaphore ; semaphore customers==............... ; semaphore barbes==............... ; semaphore mutex=............... ; int waiting==............... ;

Coiffeur endormie

void barber(void){ while(TRUE){ down(&customers) ; /*go to sleep if # of customers is 0*/ ............... ; /*acquire access to 'waiting'*/ waiting=waiting 1 ; /*decrement count of waiting customers*/ up(&barabers) ; /*one barber is now ready to cut hair*/ ............... ;/*release 'waiting'*/ cut_hair() ;/*cut hair (outside critical region*/

Coiffeur endormie

void customer (void) down(&mutex) ; /*enter critical region*/ if(waiting ............... CHAIRS){ /* if there are no free chairs, leave*/ waiting=waiting +1 ; /*increment count of waiting customers*/ ............... ; /*wake up baber if necessary*/ up(&mutex) ; /*release access to 'waiting'*/ ............... ; /*go to sleep if # of free barbers is 0*/ get_haircut() ; /* be seated and be serviced*/ }else{ down(&mutex) ; /*shop is full, do not wait */

Solution Coiffeur endormie

Define CHAIRS 5

typedef int semaphore ; semaphore customers=0 ; semaphore barbes=0 ; semaphore mutex=1 ; int waiting=0

Solution Coiffeur endormie

void baraber(void){ while(TRUE){ down(&customers) ; /*go to sleep if # of customers is 0*/ down(&mutex) ; /*acquire access to 'waiting'*/ waiting=waiting 1 ; /*decrement count of waiting customers*/ up(&barabers) ; /*one barber is now ready to cut hair*/ up(&mutex) ;/*release 'waiting'*/ cut_hair() ;/*cut hair (outside critical region*/

Solution Coiffeur endormie

void customer (void) down(&mutex) ; /*enter critical region*/ if(waiting < CHAIRS){ /* if there are no free chairs, leave*/ waiting=waiting +1 ; /*increment count of waiting customers*/ up(&customers) ; /*wake up barber if necessary*/ up(&mutex) ; /*release access to 'waiting'*/ down(&barabers) ; /*go to sleep if # of free barbers is 0*/ get_haircut() ; /* be seated and be serviced*/ }else{ down(&mutex) ; /*shop is full, do not wait */

Rendez-vous

Le problème à traiter concerne la mise au point d'un rendez-vous de travail entre N personnes.

Chaque personne doit se rendre au lieu du rendez-

vous et attendre le début de travaux qui ne peut commencer que lorsque tout le monde est présent. Le dernier arrivé donc débloquera la situation et les travaux de l'assemblée peuvent démarrer. Résoudre ce problème en utilisant des sémaphores et considérant que les personnes sont des processus citoyens.

Correction Rendez-vous

Gestion des

processus/threads

Exercice I

Répondre par OUI ou NON en justifiant

vos réponses. -1. Un processus est une enitité produite après compilaition -2. Un processus est une enitité produite après chargement d'un binaire en mémoire -3. Le pseudo-parallélisme impose aux processus de se connaître mutuellement

Correction Exercice I

1. Un processus est une entité produite après

compilation -Non, car un processus est une image d'un programme en exécuition

2. Un processus est une enitité produite après chargement d'un binaire en mémoire

-Oui, car une fois terminé le chargement d'un programme en mémoire un processus est créé

3. Le pseudo-parallélisme impose aux processus de se connaître mutuellement

-Non, car en pseudo-parallélisme les processus perdent la main au proifit du système d'exploitaition qui allouera le CPU pour un processus éligible

Exercice II

Écrire un programme qui crée 10 processus ifils.

Chacun d'entre eux devra aiÌifiÌicher dix fois d'aiÌifiÌilé son numéro d'ordre entre 0 et 9 ainsi

que son PID.

Correction Exercice II

Exercice III

Considérez le code suivant :

Exercice III

Dessinez l'arbre généalogique des processus engendrés par ce programme.

Décrivez en quelques mots quels sont tous les possibles aiÌifiÌichages à l'écran de ce programme.

Que se passe t-il si l'on déplace la ligne 10 à la ligne 7 ? Jusitiifiez votre réponse. Sans modiifier les lignes de 8 à 11, modiifiez le programme de façon à ce que les processus fassent leur aiÌifiÌichage par ordre alphabéitique inversé du nom.

Correction Exercice III

Dessinez l'arbre généalogique des processus

engendrés par ce programme.

Correction Exercice III

Décrivez en quelques mots quels sont tous les

possibles aiÌifiÌichages à l'écran de ce programme.

-La chaîne de caractères Mon nom est j ' ai dormi n secondes s'aiÌifiÌichera 5 fois, avec c = A,B,C,D,E et n un nombre arbitraire entre 0 et 3 (inclus). L'ordre de la aiÌifiÌichage dépendra seulement du temps choisi pour dormir (et l'ordonnancement), et donc il sera arbitraire.

Correction Exercice III

Que se passe t-il si l'on déplace la ligne 10 à la ligne 7 ? Jusitiifiez votre réponse.

-Chaque processus s'endormira le même nombre de seconds. En efffet, le générateur de nombres aléatoires est iniitialisé une fois seule, par le processus ancêtre (appel à la

foncition srand avec en paramètre le valeur de retour de l'appel système getpid, i.e. le pid du processus ancêtre). Par conséquence tous les processus choisiront (avec rand à la ligne 11) le premier nombre de la même suite aléatoire inifinie.

Correction Exercice III

Sans modiifier les lignes de 8 à 11, modiifiez le

programme de façon à ce que les processus fassent leur aiÌifiÌichage par ordre alphabéitique

inversé du nom.

-Nous pouvons forcer chaque père à atttendre la morts de son enfant avant faire son aiÌifiÌichage. Pour cela nous pouvons ajouter à la ligne 12. : wait ( NULL );

Exercice IV

Qu'est e qu'un mulitithreading et quelle est la

diférence avec la mulitiprogrammaition ? Dans une applicaition qui partage des données en mémoire, faut-il privilégier les processus ou les threads ? Jusitiifiez votre réponse ?

Correction Exercice IV

Qu'est e qu'un mulitithreading et quelle est la diférence avec la mulitiprogrammaition ? -Mulitithreading: exécuition concurrente/parallèle de plusieurs threads à l'intérieur d'un même processus alors que la

mulitiprogrammaition c'est l'exécuition concurrente de plusieurs processus sur un monoprocesseur. Dans une applicaition qui partage des données en mémoire, faut-il privilégier les processus ou les threads ? Jusitiifiez votre réponse ?

-On privilégie les threads par rapport aux processus aifin de gagner en performance en pariticulier la commutaition est moins coûteuse.

FINquotesdbs_dbs44.pdfusesText_44

[PDF] difference entre pagination et segmentation

[PDF] conversion adresse logique adresse physique

[PDF] pagination et segmentation pdf

[PDF] pagination systeme d'exploitation

[PDF] telecharger un livre de grammaire pdf

[PDF] larousse conjugaison pdf

[PDF] telecharger larousse difficultés grammaticales pdf

[PDF] larousse grammaire francais

[PDF] larousse orthographe pdf

[PDF] larousse livre de bord orthographe pdf

[PDF] introduction grammaire generative

[PDF] chomsky théorie

[PDF] chomsky linguistique pdf

[PDF] aspects de la théorie syntaxique pdf

[PDF] grammaire grecque ancien