Ci après le corrigé partiel de l'EMD de SE des Masters 1 GSI. La solution de l'exo 2 sera complétée après pour donner aux étudiants un source qui marche bien (et non juste un algorithme vague).
Université
Saad Dahlab Blida CORRIGE
EMD « Systèmes d’exploitation »
Faculté
des Sciences 2e
année LMD GSI, S3, 2012-2013
Département
d’Informatique
La note de
contrôle continue sera calculée ainsi : (note de l'exo le mieux fait de
l'EMD + Exposé)/2.
La moyenne
du module : (CC+ 2*EMD)/3
La
consultation de copie aura lieu ce mercredi à 9h.
Exercice 1
: (6 pts)
Toute bonne
réponse est comptée 0,5, toute mauvaise réponse, -0,5. Si la somme des points
est négative, elle devient 0. (ne répondez que par Vrai/ Faux, Oui/non, ou
alors le ou les numéros de la ou les bonne(s) réponse(s).
Q1 : Un
système d'exploitation monolithique est un système composé de 5 couches.
R :
Non
Q2 : Un
pilote de périphérique est élément permettant de piloter un périphérique. Cet
élément est :
1 – une mémoire
2 - une programme
3 – un canal d'E/S
R :
2
Q3 : Un
sémaphore dont l'entier est initialisé 0 est un sémaphore :
1 – de synchronisation
2 – d'exclusion mutuelle
R :
1
Q4 : Les
threads d'un processus utilisent chacun un quantum de temps égal au processus
père de ces threads.
R :
Faux
Q5 :
Dans une architecture à processeurs à deux cœurs, les programmes utilisant les
threads s'exécutent plus vite que ceux séquentiels.
R :
Vrai
Q6 :
Quelle que soit l'architecture physique, un programme qui lance plusieurs
processus pour effectuer chacun une sous tâche d'une tâche globale s'exécute
plus rapidement que son équivalent séquentiel (sans processus crées).
R :
Vrai (s'il existe des tâche parallèles au sein de la tache initiale, sinon,
c'est faux).
Q7 : Un
sémaphore est un objet composé d'un entier, d'un autre élément et de deux
opérations P et V. Quel est cet autre élément :
1 - une file avec priorité
2 - une file simple
3 - une pile
R :
2
Q8 : Un
thread consomme plus de mémoire qu'un processus.
R :
Faux
Q9 : Les
moniteurs sont plus difficiles à manipuler que les sémaphores
R :
Faux
Q10 :
Les disques utilisent le protocole de communication par :
1 – caractères
2 – par blocs
R :
2
Q11 :
Sous C/Linux, la bibliothèque des fonction de manipulation de threads ne
comporte pas de moyen de synchronisation de ces derniers. On est obligé de
faire appel aux fonctions de la bibliothèque des sémaphores. Vrai ou
faux ?
C'est faux. L'exposé fait par M.
Manave et M. Bakkari le montre bien. On dispose en effet des fonctions ...
Q12 : Un
thread peut-il exécuter un fork ?
La question avait l'allure d'un
piège. Il n'y en avait cependant aucun.
Un thread peut bien évidemment
exécuter un fork (et créer ainsi un process) tout comme un process peux créer
un thread ou un autre process. Il n'y a aucun raison logique à ce qu'il ne
puisse pas le faire.
Exemple (non demandé aux étudiants.
Je le joins pour que les étudiants puissent vérifier et mieux comprendre.)
#include <stdio.h>
#include <pthread.h>
typedef
struct
{int oui;} Param;
void *routine(void *param)
{
pid_t
p;
printf("\nJe
suis le thread en train de m'exécuter\n");
Param
*par = (Param *) param;
p
= fork();
if
(p>0)
par->oui++;
else
printf("\nJe
suis le process de pid %d créé par le thread\n", getpid());
}
int main(void)
{
pthread_t
p; int res;
Param
par;
printf("\nJe
suis le process créateur du thread. Mon pid est %d\n", getpid());
par.oui
= 1;
res
= pthread_create(&p, NULL, routine, (void *) &par);
pthread_join(p,
NULL);
sleep(2);
if
(res == 0)
printf("\nLa valeur de l'entier envoyée
au thread était à 1 et est passée à %d\n", par.oui);
return
0;
}
Exercice
2 : (7 pts)
Ecrire un
algorithme (ou un programme dans un pseudo C) qui évalue une expression
arithmétique représentée par un arbre binaire. Si le nœud parcouru est un
opérateur, le programme crée deux threads qui calculent chacun la valeur de
l'expression du sous arbre (Gauche pour le premier, droit pour le second).
On supposera
les opérations suivantes de manipulation d'un thread :
p :
thread (déclare un thread)
CreerThread(p) :
crée un thread et retourne son numéro dans P.
AttendreThread(p) :
attend le thread de pid P.
LancerThread(P,
F, param) ou p est le numéro du thread créé, F la fonction qu'il exécute, param
une structure composé des paramètres d'entrée et de sortie de la fonction)
Si besoin
est, on utilisera les sémaphores et les opérations P et V pour synchroniser les
threads.
Solution
L'expression transformée en arbre binaire complet ne
pouvait être évaluée que récursivement. Comme chaque thread créé devait
s'occuper de calculer la valeur d'un sous-arbre, il fallait que la routine
qu'exécute le thread crée elle même des threads et au retour de l'exécution de
ces threads-là, récolter les résultats pour calculer l'opération.
Exercice
3 : (7 pts)
Ecrire un programme qui crée une
liste linéaire de n arbres binaires complets de profondeur 2 de processus
(chaque élément de la liste ou de l'arbre est un processus.)
Exemple :
5 → 6 → 8
3 1 4 2 7 0
a b
c d e
f g g
i j k l
Solution
En parlant de liste de processus ou
d'arbre de processus, il ne s'agissait pas de créer une liste et des arbres
explicites. Lorsqu'un process en crée un autre, que cet autre crée un troisième
que le troisième crée un quatrième etc., c'est la une liste
« implicite ». Il ne fallait pas dont créer des listes au sens que
nous avions l'habitude de manipuler en algorithmique.
La solution consistait en ce que
chaque process crée un autre puis va créer son propre arbre (chaque processus
créé faisant de même sauf le nième qui ne créera pas d'autre mais créera son
arbre.
Pour rappel, en TD nous avons
résolu l'exercice de la liste de processus et du process qui crée un arbre de
processus. Il suffisait de les combiner intelligemment.
Voilà la solution :
#include <stdio.h>
#include <sys/types.h>
//ce programme crée une liste de n
arbres binaires parfaits de profondeur 2
int main(void)
{
int i,j,n; pid_t p;
printf("Donnez le nombre d'arbres a créer : ");
scanf ("%d", &n);
for (i=1;i<=n;i++)
{ printf("Process L%d
(%d)\n",i, getpid());
p = fork();
//le père doit engendrer un fils (dans la liste) et aller créer ses fils
de l'arbre
if (p>0)
{ for (j=1; j<=2;j++)
{
//chaque
fils créera deux fils-feuilles
//le
père ne devra plus créer, donc sortir des boucles.
p
= fork();
if
(p>0)
{
p = fork();
if (p>0)
break;
else
printf("Process
A-%d fils de %d\n",getpid(), getppid());
}
else
printf("Process
A-%d fils de %d\n",getpid(), getppid());
}
break;
}
}
sleep(1);
}
Commentaires
Enregistrer un commentaire