USTHB
Faculté d’Electronique et Informatique
Département Informatique
Epreuve partielle
(Algorithmique des systèmes et applications réparties) Le 18/05/2010 - Année 10/11
Questions : (15 pts= 1.5 *10)
1) Quelles sont les conséquences des caractéristiques physiques des systèmes distribués ?
Absence de mémoire commune : - Communication par messages
- Délais de transmission imprévisibles
Absence de référentiel global : - Pas d’état global réel
- Difficulté de synchronisation d’horloge
Panne de nœuds : - Difficulté de tolérances aux pannes
2) Quelle est l’utilité de l’approche micro - noyau dans un système distribué ?
o Simplification dans la conception des systèmes distribués (SDs)
o Séparation entre les services de bases communs des SDs et des services implémentés
par des serveurs spécifiques au besoin
3) Citer 6 différents types de transparences dans un système distribué.
Localité, migration, accès, relocation, migration, réplication, concurrence, persistance.
4) Définir succinctement l’appel de procédure à distance.
L’appel de procédure à distance est un mécanisme qui permet à un processus p, s’exécutant sur un site
C, d’exécuter une procédure sur un site S avec un effet global identique à celui qui serait obtenu par
l’exécution locale de P (i.e. transparence de localité).
5) Pourquoi les Horloges de Mattern sont une approximation des horloges vectorielles globales
idéales ? Donner un exemple justificatif.
Les horloges vectorielles globales idéales sont régies par un observateur idéal qui se rend compte
instantanément des événements qui se produisent au niveau de tous les sites et répercute sur la date
correspondant à cette occurrence. Il permet de dater convenablement (sans retard) tous les événements
d u système. Ce qui n’est pas le cas des horloges de Mattern.
e11 e12
P1 e11 e12
e21 e22 P1
e21 e22
P2
e31 P2
e31
P3
P3
1 1 1 2 2 1 1 0 2 1
0 1 1 1 2 0 1 0 0 2
0 0 1 1 1 0 0 1 0 1
Retard !
Datation avec observateur idéal Datation avec horloges de Mattern
M. Benchaïba – USTHB 10/11
6) Est-ce qu’une coupure consistante représente toujours un état global consistant admissible ?
Donner un exemple justificatif.
- Une coupure consistante représente un état global consistant correct mais pas toujours admissible par
certaines applications, telle que la vérification de propriétés dépendant d’un état global ‘’vertical’’.
P1
e11 e12 C1 est admissible
e21 e22 e23 e24 e25
mais pas C2
P2
e31 e32
P3
C1 C2
- P4
7) Pourquoi les horloges partielles de Lamport ont été étendues à l’ordre total ? Donner un exemple
d’utilisation.
- Afin de répondre aux exigences de certaines applications qui nécessitent un ordre total entre tous les
événements du système.
- Par exemple les applications qui affectent un privilège équitable, telle que l’exclusion mutuelle.
8) Quelle est la différence entre la diffusion parallèle et la diffusion séquentielle ?
- La diffusion parallèle permet de propager un message spécifique dans le réseau à chaque étape à tous
les voisins simultanément.
- La diffusion séquentielle permet le même but mais procède de manière séquentielle ou par jeton, càd.,
à chaque étape un seul voisin est choisi à la fois pour être destinataire du message.
9) Si on considère l’algorithme de calcul du nombre de sites qui se termine en informant tous les
sites du résultat du calcul. Donner la complexité en messages de cet algorithme.
2*c-(N-1) messages explore() + 2*c-(N-1) messages réponse() + (N-1) messages d’information
= 4*c –(N-1), où N est le nombre de nœuds du réseau et c est le nombre de canaux.
10) Si on considère un processus particulier qu’on appelle ‘’serveur d’exclusion mutuelle’’ et un
ensemble de processus qui concourent l’accès à une ressource critique, comment à votre avis il
peut servir ces processus pour gérer l’accès à cette ressource critique ?
Le serveur est considéré comme un coordinateur central, il reçoit les requêtes des processus. Il donne
l’autorisation d’accès à cette ressource à un seul processus à la fois. Quand celui-ci termine de
l’utiliser, il en informe le coordinateur. Celui-ci choisi un autre parmi ceux dont la requête est présente
localement dans la file d’attente selon le principe d’ancienneté.
M. Benchaïba – USTHB 10/11
