Systèmes d'Exploitation Avancés

L’analyse des fautes de pages pour les algorithmes

PAPS : la page la plus ancienne est remplacé

→ 11 défaut de pages

Correction Exercice II

0

0

-

-

1

0

1

-

2

0

1

2

3

3

1

2

1

3

1

2

2

3

1

2

3

3

1

2

4

3

4

2

2

3

4

2

3

3

4

2

4

3

4

2

5

3

4

5

1

1

4

5

0

1

0

5

2

1

0

2

3

3

0

2

0

1

2

2

3

0

2

5

3

5

2

LRU: La page qui n'a pas été utilisée pendant le plus de

temps qui est retirée

→ 11 défaut de pages

Correction Exercice II

0

0

-

-

1

0

1

-

2

0

1

2

-

3

0

1

2

3

1

0

1

2

3

2

0

1

2

3

3

0

1

2

3

4

4

1

2

3

2

4

1

2

3

3

4

1

2

3

4

4

1

2

3

5

4

5

2

3

1

4

5

1

3

0

4

5

1

0

2

2

5

1

0

3

2

3

1

0

0

1

2

3

2

2

3

1

0

5

2

3

5

0

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

Correction Exercice II

0

0

-

-

1

0

1

-

2

0

1

2

-

3

0

1

2

3

1

0

1

2

3

2

0

1

2

3

3

0

1

2

3

4

4

1

2

3

2

4

1

2

3

3

4

1

2

3

4

4

1

2

3

5

4

5

2

3

1

4

5

1

3

0

4

5

1

0

2

2

5

1

0

3

2

3

1

0

0

1

2

3

2

2

3

1

0

5

2

3

5

0

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

0

0

1

1

2

2

3

3

0

0

1

1

2

2

3

3

0

0

0

1

2

1

1

2

2

0

0

3

3

3

3

1

2

1

2

0

0

1

1

• Avec LRU : il y a un défaut de page à

chaque accès

Correction Exercice III

0

0

1

1

0

1

2

2

3

0

1

3

0

1

1

2

2

2

3

2

3

0

1

2

3

0

1

3

0

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.

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 segmentation et une pagination ?

• partitionnement de l’espace d’adressage

logique/physique ;

• La segmentation considère la mémoire comme des

espaces, ou des régions, dédiés à une utilisation

particulière par exemple : le code d'un programme, les

données, la pile, un ensemble de sous-programmes, des

modules, un tableau, etc. La segmentation reflète cette

organisation.

la pagination est un partitionnement qui exige les même

tailles de pages et de cases.

•

CORRECTION QUESTION DE

COURS

• Une fragmentation interne et une fragmentation externe?

– suite aux allocations mémoire des fragments très petits ne seront jamais suffisant pour

contenir un processus (frag. Interne) alors que la fragmentation externe apparaît suite à

une demande d’espace contigü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évention d’interblocage ?

– l’évitement garantit qu’il ne peut y avoir d’interblocage suite à des restrictions alors que

la prévention vérifie si l’état suivant est sécurisant ou pas.

• Un ordonnancement préemptif et un ordonnancement non préemptif ?

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

avant sa fin alors que l’ordonnancement non préemptif garde le processeur alloué au

processus du début à sa fin.

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 nœuds isolés.

12/15/16

Systèmes d’Exploitation et Programmation

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){

leave*/

/* if there are no free chairs,

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) ;

is 0*/

down(&mutex) ;

/*go to sleep if # of customers

/acquire access to ‘waiting’

/

waiting=waiting

customers*/

up(&barabers) ;

­1 ;

/*decrement

count of waiting

/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){

leave*/

/* if there are no free chairs,

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 entité produite après compilation

– 2. Un processus est une entité 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écution

● 2. Un processus est une entité 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 profit du

système d’exploitation qui allouera le CPU pour un processus éligible

Exercice II

● Écrire un programme qui crée 10 processus fils.

Chacun d’entre eux devra afficher dix fois

d’affilé 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 affichages à l’écran de ce programme.

● Que se passe t-il si l’on déplace la ligne 10 à la

ligne 7 ? Justifiez votre réponse.

● Sans modifier les lignes de 8 à 11, modifiez le

programme de façon à ce que les processus

fassent leur affichage par ordre alphabétique

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 affichages à l’écran de ce

programme.

– La chaîne de caractères Mon nom est <c > j ’ ai dormi n

secondes s’affichera 5 fois, avec c = A,B,C,D,E et n un

nombre arbitraire entre 0 et 3 (inclus). L’ordre de la

affichage 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 ? Justifiez votre réponse.

– Chaque processus s’endormira le même nombre de

seconds. En effet, le générateur de nombres aléatoires est

initialisé une fois seule, par le processus ancêtre (appel à la

fonction 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

infinie.

Correction Exercice III

● Sans modifier les lignes de 8 à 11, modifiez le

programme de façon à ce que les processus

fassent leur affichage par ordre alphabétique

inversé du nom.

– Nous pouvons forcer chaque père à attendre la morts de

son enfant avant faire son affichage. Pour cela nous

pouvons ajouter à la ligne 12. : wait ( NULL );

Exercice IV

● Qu'est e qu'un multithreading et quelle est la

diférence avec la multiprogrammation ?

● Dans une application qui partage des données

en mémoire, faut-il privilégier les processus ou

les threads ? Justifiez votre réponse ?

Correction Exercice IV

● Qu'est e qu'un multithreading et quelle est la

diférence avec la multiprogrammation ?

– Multithreading: exécution concurrente/parallèle de plusieurs

threads à l'intérieur d'un même processus alors que la

multiprogrammation c'est l'exécution concurrente de plusieurs

processus sur un monoprocesseur.

● Dans une application qui partage des données en

mémoire, faut-il privilégier les processus ou les

threads ? Justifiez votre réponse ?

– On privilégie les threads par rapport aux processus afin de gagner

en performance en particulier la commutation est moins coûteuse.

FIN