École Polytechnique de Montréal
Département de Génie Informatique
Cours INF3600 : Systèmes d’exploitation
Contrôle périodique – Automne 2001
• Date : 1er novembre 2001 de 18h à 20h
• Pondération : 30 %
• Professeurs : Kerly Titus, Hanifa Boucheneb
• Nombre de questions : 3
• Documentation : Notes + livre du cours
• Total : 20 points
Question 1 : (6 pts) Création de processus (appels système d’UNIX)
1) Dans le cas d’UNIX, la création de processus est réalisée par duplication.
a) Citez un avantage et un inconvénient. (1 pt)
b) Citez en deux ou trois lignes les avantages des processus légers (threads)
par rapport aux processus. (1 pt)
a) Facilite la duplication des processus exécutant un même programme.
Complique la création des processus exécutant des programmes
différents.
b) Meilleur partage des ressources
Gain en temps et en espace
Meilleur réactivité
2) Considérez un fichier nommé COURS. Pour accélérer la recherche du mot
INF3600 dans le fichier COURS, le processus de départ crée quatre
processus. Chaque processus fils créé effectue la recherche dans une des
quatre parties du fichier en appelant la fonction Recherche suivante :
bool Recherche (char Fichier, char Mot, int Partie) où :
- Fichier est le nom du fichier, c'est-à-dire COURS,
- Mot est le mot recherché, c'est-à-dire INF3600 et
- Partie est la partie 1, 2, 3 ou 4 du fichier.
Cette fonction retourne 1 en cas de succès et 0 sinon.
Au retour de la fonction Recherche, le processus fils transmet, en utilisant
l’appel système exit, au processus père le résultat de la recherche (exit(0)
en cas de succès, exit(1) en cas d’échec). Lorsque le processus père est
informé du succès de l’un de ses fils, il tue tous les autres fils.
a) Ecrivez un programme C/C++ qui réalise le traitement ci-dessus. (4 pts)
Attention : n’écrivez pas le code de la fonction Recherche.
……
int main ( )
{
int pid[4], status, x;
Advertisement
for (int i=0; i<4; i++)
{
// creation du (i+1) ième fils
if ((pid[i] = fork() ) == 0)
if( Recherche( “COURS”, “INF3600”, i+1 )
exit(0);
else exit(1);
}
while ((x=wait(&status))>0)
if ( status>>8 ==0)
{ for(i=0;i<4 ; i++)
if(pid[i]!=x) kill (pid[i], SIGKILL);
exit(0);
};
exit(1);
}
Question 2 : Ordonnancement des processus (6 pts)
Considérez un système d’exploitation qui ordonnance les processus selon
l’algorithme du tourniquet. La file des processus prêts contient des pointeurs vers
les entrées de la table des processus (les descripteurs des processus).
1) Citez deux problèmes qui peuvent survenir si la file contient des éléments
identiques (deux ou plusieurs pointeurs égaux). (2 pts)
Il existe, dans la file des processus prêts, un pointeur sur un processus déjà
terminé.
Il existe, dans la file des processus prêts, un pointeur sur un processus
bloqué.
2) Supposez que le système d’exploitation est composé de deux unités de
contrôle (deux processeurs CPU1 et CPU2) et d’une unité d’E/S. Chaque
processeur exécute l’algorithme du tourniquet avec un quantum de trois unités
de temps (qt = 3). Tous les processus prêts sont dans une même file
d’attente. La commutation de contexte est supposée de durée nulle.
Considérez trois processus A, B et C décrits dans le tableau suivant :
Processus
Instant
d’arrivée
Temps d’exécution
A
B
Advertisement
C
0
2
3.5
4 unités de CPU, 2 unités d’E/S, 2 unités de CPU
3 unités de CPU, 4 unités d’E/S, 2 unités de CPU
5 unités de CPU
La première ligne signifie que le processus A arrive dans le système à l’instant
0, son exécution nécessite dans l’ordre 4 unités de temps CPU, 2 unités de
temps d’E/S et 2 unités de temps CPU. Au départ le processus A est élu par le
processeur CPU1.
Si plusieurs événements surviennent en même temps, vous supposerez les
priorités suivantes :
- Le CPU1 a la priorité d’accès à la file des processus prêts par rapport
au CPU2.
- A la fin d’un quantum, le processus non terminé en cours est
suspendu uniquement si la file des processus prêts n’est pas vide. Le
traitement réalisé à la fin d’un quantum est plus prioritaire que celui d’une fin
d’E/S qui, à son tour, est plus prioritaire que l’arrivée de nouveaux processus
dans le système.
a) Donnez
les diagrammes de Gantt montrant
l’allocation des deux
processeurs, de l’unité d’E/S et l’évolution des états des files d’attente
(celle des processus prêts et celle des processus en attente de l’unité
d’E/S) (3 pts).
CPU1 :(0,A,4) (4,C,7) (7,C,9) (10,B,12)
CPU2 : (2,B,5) (6,A,8)
File : (3.5,C)(4,vide)
E/S : (4,A,6) (6,B,10)
File E/S : (5,B) (6,vide)
b) Calculez le temps moyen de virement (temps moyen de séjour) (1 pt).
TVM = (8+(12-2) + (9-3.5))/3 = 7.8
Question 3 : Synchronisation de processus (8 pts)
Considérez un système multicouche composé de trois couches P0, P1 et P2. Les
couches sont des processus concurrents qui communiquent au moyen de deux
tampons T0 et T1 de même taille N :
- P0 et P1 partagent le tampon T0 et
- P1 et P2 partagent le tampon T1.
Advertisement
Chaque couche se charge d’un traitement particulier :
- Le processus P0 se charge de lire du clavier des messages qu’il traite avant
de les déposer dans le tampon T0. Le traitement d’un message par la couche
P1 consiste à l’encrypter. Il est réalisé par la fonction Encrypter suivante :
Message Encrypter (Message);
La fonction Message Lire (); permet de lire un message du clavier.
- Le processus P1 se charge de transférer directement les messages du
tampon T0 vers le tampon T1.
- Le processus P2 récupère les messages du tampon T1 pour les envoyer à un
destinataire. L’envoi d’un message est réalisé par la fonction Envoyer :
Envoyer (Message );
Clavier
P0
P1
P2
T0
T1
Envoyer(m)
a) Expliquez comment les processus peuvent utiliser les sémaphores pour
tampons partagés (exclusion mutuelle, pas
les accès aux
contrôler
d’interblocage) (2 pts).
Les sémaphores :
Mutex0 et mutex1 pour contrôler les accès aux tampons.
Vide1, Vide0, Plein1 et Plein0 pour bloquer un processus si le tampon est
vide ou plein.
b) Donnez les pseudocodes des trois processus (6 pts).
Semaphore
mutex1=1, mutex0=1, Vide0=N, Vide1=N, Plein0 = 0, Plein1 = 0;
P0
Message m, mc;
int ip=0;
Répéter
{
m= lire();
mc = Encrypter(m);
P(Vide0);
Advertisement
P(mutex0);
T0[ip] = mc;
V(mutex0);
ip = ip+1 mod(N)
V(Plein0);
}
P1
int icp=0;
Répéter
{
P(Plein0);
P(Vide1)
P(mutex0);
P(mutex1)
T1[icp] = T0[icp];
V(mutex1);
V(mutex0)
icp = icp+1 mod(N)
V(Plein1);
V(Vide0);
}
P2
Message mc;
int ic=0;
Répéter
{
P(Plein1)
P(mutex1);
mc = T1[ic];
V(mutex1);
ic = ic+1 mod(N)
V(Vide1);
Envoyer(mc);
}