Semaphores
Semaphores
Semaphores
Semaphores
EXERCICES
&
CORRIGES
Contenu
I. EXERCICES : ...................................................................................................................................... 2
Il s'agit de synchroniser les activités du coiffeur et de ses clients avec des sémaphores. Les
sémaphores utilisés sont initialisés ainsi :
Client() {
P(SX);
if(Attend < N) { Coiffeur(){
Attend = Attend + 1; while (1){
V (SP); P(SP);
V (SX); P(SX);
P (SCF); Attend = Attend -1;
SeFaireCoifferEtSortir(); V(SCF);
} V(SX);
else { Coiffer();
V(SX); }
Sortir(); }
}
}
a- Détailler le fonctionnement du coiffeur et de ses clients tels qu'ils sont représentés par les
deux fonctions Coiffeur et Client.
La circulation au carrefour de deux voies est réglée par des signaux lumineux (feu vert/rouge).
On suppose que les voitures traversent le carrefour en ligne droite et que le carrefour peut
contenir au plus une voiture à la fois.
Les arrivées sur les deux voies sont réparties de façon quelconque. Le fonctionnement de ce
système peut être modélisé par un ensemble de processus parallèles :
Remarque :
Le processus P doit attendre que la voiture engagée dans le carrefour en soit sortie avant
d'ouvrir le passage sur l'autre voie.
I.3 Exécutions atomiques
On suppose que sur Unix on peut définir des variables x et y communes à deux processus
comme suit :
shared long x = 0 ;
shared long y = 0 ;
Processus P1 Processus P2
*** ***
x = x + 1; x = x * 2;
y = y + 1; y = y * 2;
printf("x=%d,y=%d\n", x, y); printf("x=%d,y=%d\n", x, y);
*** ***
a- Ces processus s'exécutent sur un système UNIX dont la politique d'ordonnancement est du
type round robin . Quelles peuvent être les couples de valeurs affichées par chacun des deux
processus ?
b- En utilisant un sémaphore, modifier le code pour assurer que les printf affichent toujours
des valeurs identiques pour x et y.
I.4 Quantum de temps
1. q = [[infini]]
2. q = [[epsilon]]
3. q=s
4. q=t
5. s < q <t
6. q>t
Pour chaque question, étudier les cas où s compris dans le quantum ou non.
I.5Ordonnancement
Soit TS le temps de service d'un travail, c'est à dire le temps écoulé entre la soumission du
travail et sa fin. On considère un système de traitement séquentiel (batch ) dans lequel quatre
travaux arrivent dans l'ordre suivant :
a- Donner le TS moyen dans le cas où l'on adopte la politique PAPS (Premier Arrivé, Premier
Servi, ou encore FCFS, Fist Come Fisrt Served )
b- Donner le TS moyen dans le cas où l'on adopte la politique préemptive : PCA (le plus court
d'abord, ou encore SJN, Shortest Job Next)
Ecrire les procédures d'accès à un objet de type barrière, c'est à dire dont le fonctionnement
est le suivant :
struct
{
Sema Sema1; /* Sémaphore de section critique */
Sema Sema2; /* Sémaphore de blocage sur la barriere */
int Count; /* Compteur */
int Maximum; /* Valeur déclenchant l'ouverture */
} Barriere;
Question 1 :
Question 2 :
I.7 Synchronisation
Ces procédures pouvant être utilisées simultanément par plusieurs processus, il faudra être
particulièrement attentif aux problèmes de synchronisation.
On donne ci-dessous le canevas (pseudo C) de Wait et Set ainsi que les structures de données
utilisées.
/*------------------------------------------------------------------
Structure de données utilisée pour gerer P
-------------------------------------------------------------------*/
struct {
Sema Sema1; /* Semaphore pour gérer la section critique
*/
Sema Sema2; /* Semaphore d'attente de remise a jour */
int Count; /* Nombre de processus en attente */
int X; /* Donnee protegee */
} Protected;
La fonction Set :
/*------------------------------------------------------------------
Set fait passer la variable P a la valeur V
et libere ensuite tous les processus qui attendent le changement
de valeur de P.
-------------------------------------------------------------------*/
void Set (Protected *P; int Valeur)
{
int I;
***;
P->X = Valeur;
for (I=0 ; I < P->Count ; I++) ***;
P->Count = 0;
***;
}
La fonction Wait:
/*------------------------------------------------------------------
Wait bloque un processus tant que la variable X ne vaut pas V
Le nombre de processus bloques est memorise dans Count
-------------------------------------------------------------------*/
void Wait (Protected *P; int Valeur)
{
Boolean Do_Wait = True;
while Do_Wait
{
***;
if (P->X == Valeur) {
Do_Wait = ***;
} else {
P->Count++;
}
***;
if Do_Wait ***; /* (1) */
}
}
Question 1 :
Comment doivent être initialisés Sema1 et Sema2 ?
Question 2 :
Compléter Wait en remplaçant les *** par le code adéquat.
Question 3 :
Compléter Set en remplaçant les *** par le code adéquat.
Question 4 :
Que se passe-t-il dans ce scénario très particulier :
Suggérez une solution en utilisant un troisième sémaphore qui assure le bon fonctionnement
de l'instruction commentée (1).
I.8 Pagination
Sachant que les pages virtuelles et physiques font 1K octets, quelle est l'adresse mémoire
correspondant à chacune des adresses virtuelles suivantes codées en hexadécimal :
142A et 0AF1
Comment implanter le partage de code (code réentrant) dans un système qui gère la mémoire
par pagination ?
I.10 Pagination 2
Question :
1. S'il reste 3 pages libre en mémoire, indiquer la séquence des défauts de page, sachant
que l'algorithme de remplacement est FIFO,
2. Même question avec 4 pages disponibles en mémoire. Observation ?
I.11 Gestion de la pile
#include
int main (void){
short i, *P ;
short *Fonc (void);
P = Fonc ();
for (i=0; i <5 ;i++) printf ("P[%d] = %d\n", i, P[i]);
}
Question :
En exécutant le programme, on obtient l'affichage suivant, pourquoi ?
P[0] = 0
P[1] = -2856
P[2] = 1
P[3] = 1764
P[4] = 4
II.CORRIGES
a- Coiffeur
Client
incrémente Attend (accès exclusif)
Sémaphores utilisés :
Init (X1, 1), Init (X2, 1), Init (SF1, 1), Init (SF2, 0);
SX1 et SX2 sont introduits pour éviter que les voitures attendent sur SF1 et SF2 et bloquent
de ce fait les changements de feu effectués par Changement.
II.3 Exécutions atomiques
Réponse :
x = 1, y = 1
x = 2, y = 2
x = 1, y = 2
x = 2, y = 1
Processus P1 Processus P2
*** ***
P (S); P (S);
x = x + 1; x = x * 2;
y = y + 1; y = y * 2;
V (S); V (S);
printf("x=%d,y=%d\n", x, y); printf("x=%d,y=%d\n", x, y);
*** ***
Réponses :
1. Le processus garde le processeur tant qu'il en a besoin (comme FCFS, Fist Come Fisrt
Served ),
2. Le processus ne fait presque rien entre chaque changement de contexte, progression
très lente. Si s est compté dans q, aucun processus n'est exécuté.
3. Si s est compris dans q, il ne se passe rien, sinon exécution pendant au plus s,
4. Le quantum a tendance à favoriser les processus orientés entrées-sorties,
5. Le quantum est quelconque,
6. Le quantum favorise les processus qui ne font que du calcul,
II.5 Ordonnancement
Réponses :
on obtient :
( (17 - 0 + 1 ) + (4 - 1+ 1 ) + (9 - 3 + 1 ) + (25 - 2 + 1 ) ) / 4 = 53 /4
II.7 Synchronisation
Compléter Wait :
/*------------------------------------------------------------------
Wait bloque un processus tant que la variable X ne vaut pas V
Le nombre de processus bloques est memorise dans Count
-------------------------------------------------------------------*/
void Wait (Protected *P; int Valeur)
{
Boolean Do_Wait = True;
while Do_Wait
{
P (P->Sema1);
if (P->X == Valeur) {
Do_Wait = False;
} else {
P->Count++;
}
V (P->Sema1);
if Do_Wait P (P->Sema2); /* (1) */
}
}
Compléter Set :
/*------------------------------------------------------------------
Set fait passer la variable P a la valeur V
et libere ensuite tous les processus qui attendent le changement
de valeur de P.
-------------------------------------------------------------------*/
void Set (Protected *P; int Valeur)
{
int I;
P (P->Sema1);
P->X = Valeur;
P->Count = 0;
V (P->Sema1);
Question I-4 :
Solution :
dans Set :
...
for (I=0 ; I < P->Count ; I++)
{ V (P->Sema2); P (S3);}
...
dans Wait :
II.8 Pagination
Réponses :
1K = 1024 = 210, le déplacement dans une page est donc codé sur 10 bits.
page virtuelle 5, octet 2A dans cette page -> page mémoire 1, octet 2A dans cette page
page virtuelle 2, octet 2F1 dans cette page ->page mémoire 8, octet 2F1 dans cette page
Partage de code :
Réponse :
il suffit de faire pointer les pages virtuelles de deux processus sur les memes pages physiques.
II.10 Pagination 2:
Il utilise les pages dans l'ordre suivant :
012301401234
Réponses :
Avant l'appel à la fonction Fonc, le pointeur de pile (stack pointer), sp, contient l'adresse
de la première case libre sur la pile.
On schématise ci-dessous l'état de la pile avant l'appelà Fonc. Les cases libres sont en blanc,
les cases occupées sont en grisé.
Chaque case représente un octet, le pointeur de pile contient donc des adresses d'octets.
T est une variable locale de la fonction Fonc, l'espace mémoire réservé à ce tableau est donc
alloué sur la pile.