Correction de l’examen du 21 mai 2003

0xC2

0xD3

0xA4

0xB5

0x86

0x97

0x68

0x79

-

-

-

-

-

-

R ponse 3 :

Lalgorithme de lib ration des pages est de type premier arriv , premier

enlev (FIFO). Un d faut de page est repr sent par le symbole *

On obtient avec 3 pages libres en m moire :

Num ro de page

d faut de page

0

*

0

1

*

0

1

4

*

0

1

4

2

*

2

1

4

0

*

2

0

4

1

*

2

0

1

3

*

3

0

1

0

3

0

1

1

3

0

1

4

*

3

4

1

2

*

3

4

2

3

3

4

2

Nombre de d fauts de pages : 9

• 1 -

Et avec 4 pages libres en m moire :

Num ro de page

d faut de page

0

*

0

1

*

0

1

4

*

0

1

4

2

*

0

1

4

2

0

0

1

4

2

1

0

1

4

2

3

*

3

1

4

2

0

*

3

0

4

2

1

*

3

0

1

2

4

*

3

0

1

4

2

*

2

0

1

4

3

*

2

3

1

4

Nombre de d fauts de pages : 10

On constate que lex cution du processus g n re 1 faute de page

suppl mentaire alors que la m moire physique disponible est plus grande.

Cest un des probl mes de lalgorithme FIFO : anomalie de Belady.

R ponse 4 :

Dans le cas dun adressage sur 8 bits, une entr e de la table des pages

peut tre cod e sur 6 bits : 3 bits d tat et 3 bits pour le num ro de page

physique.

Dans ce cas, la m moire physique est limit e 8 pages de 32 octets. Le

syst me ne sera pas tr s efficace : m me avec une m moire priv e pour

lex cution du syst me et dans le cas favorable de processus utilisant une

seule page, la m moire physique est satur e avec 8 processus...

Augmenter le nombre de bits pour coder le num ro de page physique dans la

table des pages permet daugmenter la m moire physique de la machine sans

rien changer lespace dadressage des processus : la m moire virtuelle

dun processus reste limit e 256 octets. Par contre, le syst me est

capable dex cuter beaucoup plus de processus en m moire sans avoir besoin

dutiliser lespace de pagination (swap), toujours tr s p nalisant en terme

de performances.

Le m me principe sapplique aux machines 32bits actuelles : la m moire

physique nest plus limit e 4Go alors que les processus continuent de

fonctionner avec des adresses 32bits donc avec une m moire de 4Go maximum.

Il faut par contre, pour que la machine soit performante, que le syst me et

surtout le mat riel soient adaptes.

B Probl me de cr ation de processus

Soit le fichier /user/toto contenant la cha ne de caract res :

abcdefghijklmnopqrst

On se propose d tudier le programme suivant :

main()

{

int PID;

int fd;

char buffer[20];

fd = open("/user/toto", O_RDWR);

read(fd, buffer, 10);

print(buffer);

PID = fork();

if (PID == 0)

{

read(fd, buffer, 5);

print(buffer);

}

else

{

read(fd, buffer, 5);

print(buffer);

}

}

• 2 -

Les fonctions open() et read() sont les appels syst mes vus en cours.

La fonction print() affiche sur le terminal le contenu du buffer pass en

param tre. On remarque que comme le fichier est ouvert AVANT l'appel la

fonction fork(), les structures internes au noyau utilis es pour l'acc s au

fichier sont PARTAGEES par le processus p re et le processus fils.

Question 1 :

Donnez l'encha nement des fonctions ex cut es par le processus p re et

l'encha nement des fonctions ex cut es par le processus fils.

processus p re

processus fils

open()

read()

print()

fork()

read() read()

print() print()

Question 2 :

En ex cutant plusieurs fois ce programme, on constate qu'il produit 2

affichages diff rents.

Donnez ces 2 affichages.

CAS 1

abcdefghij

klmno

pqrst

CAS 2

abcdefghij

pqrst

klmno

Question 3 :

Expliquez comment ces affichages sont produits et pourquoi ils sont

diff rents.

Le syst me UNIX ne garantie pas d'ordonnancement particulier entre

processus P re et Fils. Il se peut que l'un des processus soit lu apr s

que l'autre ait fait le read() mais avant le print(). Il effectuera alors

sa propre s quence read()/print(), mais en ayant eu le pointeur de position

du fichier affect par le read() de lautre processus :

Le cas 1 ci dessus correspond :

fils

ou

p re

fils

p re

open()

read()

print()

fork()

read()

print()

read()

print()

Le cas 2 ci dessus correspond :

open()

read()

print()

fork()

read()

print()

read()

print()

p re

open()

read()

print()

fork()

read()

print()

fils

ou

p re

fils

open()

read()

print()

fork()

read()

print()

read()

print()

read()

print()

• 3 -

Le programme pr c dent est modifi dans le but d'utiliser le d but du

fichier /usr/toto comme zone de communication entre les 2 processus. Le

processus p re sera en charge de lire des donn es sur un capteur et de les

crire au d but du fichier, et le processus fils sera en charge de lire ces

donn es en d but de fichier puis de les traiter et les afficher. On sait

que le traitement des donn es est plus long que lacquisition des donn es,

et que donc le processus fils ne trouvera pas 2 fois de suite les m mes

donn es dans le fichier.

Le programme devient :

main()

{

int PID;

int fd;

fd = open("/user/toto", O_RDWR);

read(fd, buffer, 10);

print(buffer);

PID = fork();

if (PID == 0)

{

do {

lseek(fd, 0, SEEK_SET);

count = read(fd, buffer, 5);

if (count == 5)

{

traiter_donn es(buffer);

print(buffer);

}

} while (1)

}

else

{

???????

}

}

Question 4 :

En prenant exemple sur la boucle de traitement du processus fils, crire la

boucle de code du processus p re.

Les donn es seront lues gr ce la fonction lire_capteur(buffer) qui lit 5

caract res et les place dans la variable buffer.

do {

lire_capteur(buffer);

lseek(fd, 0, SEEK_SET);

write(fd, buffer, 5);

} while (1)

Question 5 :

Le code ci dessus ne fonctionne pas bien. En effet, on constate que de

temps en temps, le processus fils ne lit pas le d but du fichier

(caract res 0 4) mais lit les caract res 5 9 du fichier.

Expliquer comment cela est possible.

De la m me fa on qu la question 3, cest un probl me dordre dex cution

des processus p re et fils. Si le processus fils perd le processeur apr s

avoir positionn le pointeur du fichier (lseek()), et que le p re ex cute

ce moment l lseek()/write(), puis perd lui m me le processeur, le fils va

effectuer son read() alors que le pointeur de position se trouve en 5.

• 4 -

Identifiez la ou les sections critiques.

Les sections critiques sont :

P re

lseek()

write()

Fils

lseek()

read()

A partir du moment o un processus ex cute le lseek, il doit ex cuter

lacc s fichier sans tre interrompu par lautre processus.

Proposez une solution ce probl me l'aide de s maphores que vous

manipulerez avec les fonctions init(semaphore), P(semaphore),

V(semaphore) vues en cours.

Les sections critiques seront simplement encadr es par un couple P()/V(),

en ayant initialis le s maphore 1 (1 seul processus la fois dans la

section critique) :

main()

{

int PID;

int fd;

init(semaphore, 1);

fd = open("/user/toto", O_RDWR);

read(fd, buffer, 10);

print(buffer);

PID = fork();

if (PID == 0)

{

do {

P(semaphore);

lseek(fd, 0, SEEK_SET);

count = read(fd, buffer, 5);

V(semaphore);

if (count == 5)

{

traiter_donn es(buffer);

print(buffer);

}

} while (1)

}

else

{

do {

lire_capteur(buffer);

P(semaphore) ;

lseek(fd, 0, SEEK_SET);

write(fd, buffer, 5);

V(semaphore)

} while (1)

}

}

Question 6 :

On souhaite maintenant modifier le programme ci dessus pour que les 2

boucles infinies s'arr tent sur r ception d'un signal SIG_USR1.

Proposer les modifications n cessaires.

La difficult est que nous navons pas 1, mais 2 processus en cours

dex cution. Il faut donc faire en sorte que les 2 processus re oivent

linformation darr t. Plusieurs solutions peuvent tre envisag es :

On envoie 2 signaux,

Un signal est envoy au p re, et le p re informe le fils,

• 5 -

Voici une solution 1 seul signal envoy au p re :

int cont = 1;

int PID;

usr1_handler()

{

cont = 0;

if (PID)

kill(PID, SIG_USR1);

}

main()

{

int fd;

char buffer[20];

int semaphore;

fd = open("/user/toto", O_RDWR);

read(fd, buffer, 10);

print(buffer);

signal(SIG_USR1, usr1_handler);

init(semaphore,1);

PID = fork();

if (PID == 0)

{

do {

P(semaphore);

lseek(fd, 0, SEEK_SET);

count = read(fd, buffer, 5);

V(semaphore);

if (count == 5)

{

traiter_donn es(buffer);

print(buffer);

}

} while (cont)

}

else

{

do {

lire_capteur(buffer);

P(semaphore);

lseek(fd, 0, SEEK_SET);

write(fd, buffer, 5);

V(semaphore);

} while (cont)

}

}

• 6 -