Les processus, à quoi ça sert ?

Ça sert à faire plusieurs activités en "même temps".
Par exemple :
Faire travailler plusieurs utilisateurs sur la même machine. Chaque utilisateur a l'impression d'avoir la machine à lui tout seul.
Par exemple :
Compiler tout en lisant son mail.
Problème : Un processeur ne peut exécuter qu'une seule instruction à la fois.
But : Partager un (ou plusieurs) processeur entre différents programmes (les processus).
Attention ! ne pas confondre Processus avec Processeur =

Notes sur les champs d'application des processus

Parties de programme indépendantes

Exemple 1 : évaluation de (a + b) * (c + d) - (e / f).
Évaluation séquentielle :

t1 = a + b;
t2 = c + d;
t3 = t1 * t2;
t4 = e / f;
t5 = t3 - t4;

Évaluation parallèle :

début
  par_début
    début
      par_début
        t1 = a + b;
        t2 = c + d;
      par_fin
      t3 = t1 * t2;
    fin
    t4 = e / f;
  par_fin
  t5 = t3 - t4;
fin

Les actions entre par_début et par_fin peuvent s'exécuter en parallèle.
Exemple 2 : évaluation du produit de deux matrices : C = A x B.
Tous les éléments de C peuvent être calculés en parallèle.

Simulation

Exemple 3 : étude de l'extension de traffic dans un port, le comportement de chaque bateau est matérialisé par un processus.

Contrôle des processus industriels

Exemple 4 : chaque capteur d'une machine industrielle est commandé par un processus.

Systèmes d'exploitation

Utilisation du parallélisme matériel pour une augmentation des performances.
Structuration des programmes pour en maîtriser la complexité.

Une définition d'un processus

Un processus est l'activité résultant de l'exécution d'un programme séquentiel, avec ses données, par un processeur.

La vie intime des processus

Allocation du processeur

Il existe différentes stratégies :

avec ou sans réquisition du processeur (stratégies prémptives ou non-préemptives),
fixées à priori en utilisant des informations sur le processus et l'activité du système.

méthode FIFO (First In, First Out) Aussi appelé traitement par "train", par "lot" ou "batch".
Les processus accèdent au processeur, chacun à leur tour, dans l'ordre d'arrivée, et monopolisent le processeur jusqu'à leur terminaison.

Travaux courts pénalisés

Temps de Réponse fonction de la Charge du système

Stratégie indépendante du temps d'exécution des processus

Cette méthode est non-préemptive, c'est-à-dire qu'un processus monopolise le processeur jusqu'à sa terminaison.
Une amélioration de la stratégie FIFO est d'ordonner la file en fonction du temps estimé d'exécution des processus. Dans ce cas, le temps de réponse des travaux courts est diminué, et celui des travaux long est augmenté.

Méthode du tourniquet (Round Robin) Aussi appelé "balayage cyclique".
Les processus accèdent au processeur, chacun à leur tour, pour un temps déterminé à l'avance (le quantum).
Un processus en attente d'une entrée-sortie sera placée dans une file des bloqués.

Plus court d'abord (SJF : Shortest Job First)

Priorité = Ordonnancement de la file

Privation des travaux longs
Cette méthode est préemptive, c'est-à-dire que le processeur est retiré à un processus au bout d'un certain quantum.
Le quantum est calculé par tâtonements :

si le quantum est très grand, on obtient une file d'attente simple;
si le quantum est très petit, les processus n'auront pas le temps d'être exécuté en partie avant d'être réinsérés dans la file.

Méthode du tourniquet multiniveaux Avant d'accéder au processeur, les processus sont rangés dans les files correspondant à leur niveau de priorité. Un processus ne peut accéder au processeur que s'il n'existe plus de processus dans les files de plus haute priorité.

Amélioration du tourniquet simple

Priorité = 1 priorité différente par niveau
Les priorités peuvent être :

externes, fixées avant la prise en compte du processus,
internes, ajustées par le système,
mixtes.

Une amélioration du système par le swap

Un processus peut être rangé (swapped) sur disque s'il reste trop longtemps dans la file des bloqués.

Quelques caractéristiques des processus

Voici un résultat possible de la commande ps sous Unix.
Chaque ligne concerne un processus et chaque colonne donne une caractéristique des processus. Par exemple PID est l'IDentificateur du Processus.
Pour plus d'information, reportez-vous aux man pages en tapant la commande man ps.

USER	PID	%CPU	%MEM	SZ	RSS	TT	STAT	START	TIME	COMMAND
billard	9343	5.4	1.3	316	756	p1	S	15:58	0:00	-local/bin/tcsh
solana	29087	2.7	7.0	3196	4212	co	S	Jan 4	81:53	lemacs
solana	10113	0.0	0.0	104	0	co	IW	Dec 22	0:01	-csh (csh)
bin	60	0.0	0.0	36	0	?	IW	Nov 15	0:01	ypbind
root	0	0.0	0.0	0	0	?	D	Nov 15	19:23	swapper
root	78	0.0	0.1	60	60	?	I	Nov 15	5:25	syslogd
ncsa	18010	0.0	0.0	1976	0	?	IW	Jan 9	0:01	/net/bin/sp

STAT	Signification
S	Sleeping <= 20s
I	Idle > 20s
W	Swapped
D	Non-interruptible

Le contexte d'un processus

Le contexte d'un processus est l'ensemble des informations dynamiques qui représente l'état d'exécution d'un processus (e.g. où est-ce que le processus en est de son exécution).

Le contexte

état courant d'un processus.
On définit aussi le vecteur d'état d'un processus (PSW : Program Status Word) comme l'ensemble des bits de condition, priorité, etc. au moment de la commutation de contexte.

La commutation de contexte (context switching)

La commutation de contexte est le mécanisme qui permet au système d'exploitation de remplacer le processus élu par un autre processus éligible.

Le temps nécessaire à la commutation de contexte doit être inférieur au quantum.

Les processus sous Unix

Aussi appelés processus lourds.
La création d'un processus :

Sous l'interpréteur de commande (shell).
Dans un programme : instruction fork().

Action de fork()

duplication du processus père ;
retour de la valeur pid (numéro du fils) dans le processus père ;
retour de la valeur 0 dans le processus fils.

Lors du démarrage de Unix, deux processus sont créés :

le Swapper (pid = 0) qui gère la mémoire;
le Init (pid = 1) qui crée tous les autres processus.

La communication entre processus

La communication entre père et fils par tubes (pipe)

Un processus hérite de son père les descripteurs de tubes.
Un tube est composé de deux entrées (lecture / écriture).
Chaque entrée est FIFO.
Création d'un tube : int pipe(p) avec int p[2].
p[0] = accès en lecture ; p[1] = accès en écriture.

La communication par tubes nommés

Un tube nommé est un fichier spécial créé avec la commande mknod ou mkfifo.

-rw-r-----   1 billard  telecom    15001 fév   4 13:59 fichier_normal
prw-r-----   1 billard  telecom        0 fév   4 13:58 mon_tube
-rw-r-----   1 billard  telecom    45876 fév   4 13:59 un_autre_fichier

La taille de mon_tube = 0, sauf lors de l'utilisation du tube.
Le tube s'utilise comme un fichier normal avec les primitives open, read, write, close.

La communication par IPC (Inter Process Communication)

Les IPC font partie de l'interface Unix System V.
Les IPC comprennent :

les files de messages ;
la mémoire partagée ;
les sémaphores.

Les files de messages et la mémoire partagée sont des outils de communication.
Les sémaphores sont des outils de synchronisation.

Les files de messages

1 file de message

1 boîte aux lettres.
Un processus peut déposer et retirer des messages. Les messages sont typés.

Un processus peut retirer :

le premier message de la file ( type) ;
le premier message de type t ;
le premier message de type t (t étant une valeur entière > 0).

La mémoire partagée

1 mémoire partagée

1 espace d'adressage commun à plusieurs processus.
Un processus peut lire et écrire en mémoire partagée, comme s'il s'agissait de ses propres variables.

Les IPC - Inconvénients

Table des IPC (donnée par la commande ipcs).

Message Queues:
T     ID     KEY      MODE       OWNER    GROUP
q  28050 19466732 --rw-rw-rw- cbronner     sys2
Shared Memory:
T     ID     KEY      MODE       OWNER    GROUP
m  10601     4353 --rw-rw-rw-  marchal     sys2
Semaphores:
T     ID     KEY      MODE       OWNER    GROUP
s    811     8765 --ra-ra-ra-  marchal     sys2

Les IPC font partie du système d'exploitation.
Chaque opération sur un IPC implique donc un appel système, très couteux, i.e. lent.

Les threads - processus légers

Idée : plusieurs threads à l'intérieur du même processus.
Chaque thread accède au même segment de données (donc aux mêmes variables).
1 thread =

Une thread qui interagit avec une autre au sein du même processus n'utilise pas le système d'exploitation.

une thread est plus légère à gérer et sa gestion peut être personalisée.
La commutation de contexte est plus simple entre threads.
États uniques pour chaque thread :

identificateur de thread ;
état des registres ;
pile ;
masques de signaux (décrivent à quels signaux la thread répond) ;
priorité ;
données privées à la thread.

Attention : par défaut, la méthode d'allocation du processeur est NON-préemptive dans les anciens systèmes, et préemptive dans tous les sytèmes récents.

Les problèmes liés à la concurrence

Le maintien de la cohérence

La mise à jour concurrente des données peut se dérouler sans problème, comme dans la figure suivante, où la variable cpt, initialement à 2000, a comme valeur finale 1000 (2000 + 1000 - 2000).

Malheureusement, la mise à jour concurrente peut aussi générer des incohérences, comme dans la figure suivante, où la variable cpt, initialement à2000, a comme valeur finale 0 après l'exécution du même code.

Section Critique & Exclusion mutuelle

La mise-à-jour de cpt doit s'effectuer en exclusion mutuelle (e.g. seule à l'exclusion de toute autre action) car il s'agit d'une section critique. Une seule thread à la fois modifie cpt. L'autre doit attendre que la thread en cours ait fini.

Solution logicielle à l'exclusion mutuelle

Première solution :Utiliser un booléen c initialisé à vrai.

tant que (non c) faire rien;
c := faux;
< Début Section Critique (DSC) >
< SC >
< Fin Section Critique (FSC) >
c := vrai;

Solution logicielle (fausse) à l'exclusion mutuelle

Solution logicielle (juste) à l'exclusion mutuelle

L'algorithme de Deckker. Soit i le numéro (0 ou 1) de la thread courante et j le numéro de l'autre thread.initialisations :

int c[2];
int tour;
c[0] = FALSE;
c[1] = FALSE;
tour = 0;

algorithme :

c[i] = TRUE; 
tour = j;
while ((c[j]) && (tour == j)) {};
< SC >
c[i] = FALSE;

L'inconvénient majeur des solution logicielle : l'attente active

Même si une thread ne fait rien (i.e. elle attend pour la section critique), elle monopolise le processeur !L'attente active ne devrait pas être permise !

Solutions matérielles (justes) à l'exclusion mutuelle

Le masquage des interruptions.

Une thread qui veut rentrer en section critique inhibe les interruptions pour conserver le processeur jusqu'à ce qu'elle les rétablisse.

L'instruction Test&Set.

procédure Test&Set(var a,b : entier);
début
   a := b;
   b := 1;
fin;

Test&Set(test_i, verrou);
tant que test_i = 1 faire 
   Test&Set(test_i, verrou);
< SC >
verrou := 0;

Problème = attente active !

Les Sémaphores

Définition

Introduits par Dijkstra en 1965.Les sémaphores sont un outil élémentaire de synchronisation qui évitent l'attente active.
Un sémaphore s =

un entier e(s) ;
une file d'attente f(s) ;
deux primitives P(s) et V(s).

Soit p le processus qui effectue P(s) ou V(s).

P(s)
e(s) = e(s) - 1; si e(s) < 0 alors `.` état(p) = bloqué; `.` entrer(p, f(s));

V(s)
e(s) = e(s) + 1; si e(s) <= 0 alors `.` sortir(q, f(s)); `.` état(q) = éligible; `.` entrer(q, f(éligibles));

Sémaphores d'Exclusion Mutuelle

But : protéger l'accès à une ressource unique (e.g. variable, imprimante, ...).e(s) est initialisée à 1.
Utilisation :
P(s)
< Section Critique >
V(s)
Tous les processus doivent suivre la même règle.

Sémaphores de Synchronisation

But : un processus doit en attendre un autre pour continuer (ou commencer) son exécution.e(s) est initialisée à 0.
Utilisation :

Processus 1	Processus 2
1er travail V(s) // réveil processus 2	P(s) // attente processus 1 2ème travail

Autres utilisations des sémaphores

Le rendez-vous (généralisation du problème précédent).Un processus doit attendre que n autres processus soient parvenus à un endroit précis pour poursuivre son exécution.
On utilise :

un sémaphore Ssync initialisé à 0 ;
un sémaphore mutex initialisé à 1 ;
un sémaphore Sattend initialisé à 0 ;
un entier nb initialisé à 0.

Processus i	Processus RdV
... P(mutex); nb = nb + 1; si nb = n alors V(Ssync); nb = 0; V(mutex); P(Sattend); ...	... ... P(Ssync); V(Sattend, n); ... ... ...

Interblocage

SemA et SemB sont deux sémaphores d'exclusion mutuelle.

Processus i	Processus j
... P(semA); P(semB); < SC > V(semB); V(semA); ...	... P(semB); P(semA); < SC > V(semA); V(semB); ...

Il existe deux remèdes différents pour s'affranchir des interblocages.
Prévention :

exécuter les P() toujours dans le même ordre ;
utiliser un algorithme tel que l'algorithme du banquier et déclarer quelles sont les ressources que l'on va utiliser.

Détection--Guérison :

construire le graphe des conflits (périodiquement) ;
si un circuit interblocage ;
tuer un processus effectuer les V() manquants.

Le modèle Producteur - Consommateur

Définition

Le producteur et le consommateur sont deux processus cycliques.

Producteur	Consommateur
... produire(messageP); déposer(case, messageP); ...	... retirer(case, messageC); consommer(messageC); ...

Problèmes : déposer un message alors que le consommateur n'a pas retiré le prédent ou retirer un message alors que le producteur n'a rien déposé.

Solution à une case

On utilise 2 sémaphores plein et vide initialisé à 0 et 1.plein indique si la case est pleine et vide ...

Producteur	Consommateur
P(vide) produire(messageP); déposer(case, messageP); V(plein)	P(plein) retirer(case, messageC); consommer(messageC); V(vide)

Amélioration :

Producteur	Consommateur
produire(messageP); P(vide) déposer(case, messageP); V(plein)	P(plein) retirer(case, messageC); V(vide) consommer(messageC);

Solution à n cases

Hypothèse : tampon à n cases.

Il faut gérer le tampon. C'est-à-dire :

si le tampon est vide, le consommateur ne peut rien retirer ;
si le tampon est plein, le producteur ne peut rien déposer ;
le tampon est circulaire, il faut empêcher que les indices tête et queue se chevauchent.

On utilise 2 sémaphores plein et vide initialisé à 0 et n.Les indices tête et queue sont initialisés à 0.
plein indique le nombre de cases pleines et vide ...

Producteur	Consommateur
produire(messageP); P(vide); tampon[tête] = messageP; tête = (tête + 1) mod n; V(plein);	P(plein); messageC = tampon[queue]; queue = (queue + 1) mod n; V(vide); consommer(messageC);

Solution à p producteurs et c consommateurs

Hypothèses :

tampon à n cases ;
p producteurs (e.g. utilisateurs déposant des requètes d'impression) ;
c consommateurs (e.g. spool d'imprimantes banalisées).

Il faut protéger l'utilisation des indices.On utilise 2 sémaphores mutexprod et mutexcons d'exclusion mutuelle initialisés à 1.

Producteur	Consommateur
produire(messageP); P(vide); P(mutexprod); tampon[tête] = messageP; tête = (tête + 1) mod n; V(mutexprod); V(plein);	P(plein); P(mutexcons); messageC = tampon[queue]; queue = (queue + 1) mod n; V(mutexcons); V(vide); consommer(messageC);

Le problème des Philosophes

Philosophe i
penser(); manger();

5 philosophes sont réunis autour d'une table pour manger des spaghetti. Chaque philosophe doit utiliser 2 fourchettes pour manger.
Problème : modéliser le comportement de chaque philosophe pour éviter les privations et les blocages.

Solution (fausse)

Philosophe i
penser(); P(fourchette i); P(fourchette (i+1) mod 5); manger(); V(fourchette i); V(fourchette (i+1) mod 5);

Si tous les philosophes prennent en même temps leur fourchette i, il y a interblocage.

Solution (juste)

Philosophe i
penser(); prendre_fourchette(i); manger(); poser_fourchette(i);

prendre_fourchette(i)
P(mutex); état[i] = FAIM; test(i); V(mutex); P(s[i]);

poser_fourchette(i)
P(mutex); état[i] = PENSE; test(GAUCHE); test(DROITE); V(mutex);

test(i)
si (état[i] == FAIM && état[GAUCHE] != MANGE && état[DROITE] != MANGE) alors `.` état[i] = MANGE; `.` V(s[i]);

Les Moniteurs

Définition

Un moniteur est un outil évolué de synchronisation.Introduits par Brinch & Hansen en 1972-73 et Hoare en 1974. Un moniteur =

des variables d'état ;
des procédures internes ;
des procédures externes (points d'entrée) ;
des conditions ;
des primitives de synchronisation.

Les variables d'état sont manipulables par les procédures externes seulement (encapsulation).

Un exemple simple de moniteur

Moniteur incr_decr
incr_decr : moniteur ; var i : entier ; procédure incrémente ; début i := i + 1 ; fin ; procédure décrémente ; début i := i - 1 ; fin ; début i := 0 ; fin fin incr_decr.

Chaque procédure du moniteur est exécutée en exclusion mutuelle.

l'accès au moniteur s'effectue en exclusion mutuelle. Sauf si un processus exécute la primitive attendre.

Les instructions spéciales des moniteurs

Les variables de type condition.Les primitives vide, attendre et signaler.
Soit c une condition.

c.attendre : bloque le processus et le place en attente de c.
c.vide : vrai si aucun processus n'est en attente de c, faux sinon.
c.signaler : si non c.vide alors réveiller un processus en attente de c.

Rendez-vous entre N processus

Moniteur de Rendez-vous
rendez_vous : moniteur ; `.` var n : entier ; `.` tous_là : condition ; procédure arriver ; début n := n + 1 ; si n < N alors `.` tous_là.attendre ; tous_là.signaler ; fin ; début n := 0 ; fin fin rendez_vous.

À l'intérieur des moniteurs

Chaque moniteur possède une file d'attente globale.Chaque variable condition référence une file d'attente.

c.attendre placer le processus dans la file d'attente associée à c.
c.signaler sortir le processus suivant de la file d'attente associée à c.
c.vide teste si la file d'attente associée à c est vide.

Problème : un seul processus actif à la fois au sein d'un moniteur, donc comment implémenter la primitive signaler ?Note 1 : un moniteur est en général implémenté avec des ... sémaphores !
Note 2 : c'est tout à fait logique, un système est bâti par niveaux d'abstraction successifs, un niveau i étant implémenté par les primitives du niveau i-1.

Problème des producteurs-consommateurs

processus producteur	processus consommateur
... produire(message_produit) ; tampon.déposer(message_produit) ; ...	... tampon.retirer(message_à_consommer) ; consommer(message_à_consommer) ; ...

À quoi ressemble le moniteur tampon ?

Moniteur tampon
tampon : moniteur ; `.` var n : 0..N ; `.` non_plein, non_vide : condition ; procédure déposer(m : message) ; début si n = N alors `.` non_plein.attendre ; n := n + 1 ; entrer(m) ; non_vide.signaler ; fin ; procédure retirer( var m : message) ; début si n = 0 alors `.` non_vide.attendre ; sortir(m) ; n := n - 1 ; non_plein.signaler ; fin ; `.` type message : ... ; `.` var file : tableau[0..N-1] de message ; `.` tête, queue : 0..N-1 ; procédure entrer(m : message) ; début file[queue] := m ; queue := (queue + 1) mod N ; fin ; procédure sortir( var m : message) ; début m := file[tête] ; tête := (tête + 1) mod N ; fin ; début n := 0 ; tête := 0 ; queue := 0 ; fin fin tampon.

Moniteur tampon

tampon : moniteur ;

. var n : 0..N ;
. non_plein, non_vide : condition ;

procédure déposer(m : message) ;
début
si n = N alors
. non_plein.attendre ;
n := n + 1 ;
entrer(m) ;
non_vide.signaler ;
fin ;

procédure retirer( var m : message) ;
début
si n = 0 alors
. non_vide.attendre ;
sortir(m) ;
n := n - 1 ;
non_plein.signaler ;
fin ;

. type message : ... ;
. var file : tableau[0..N-1] de message ;
. tête, queue : 0..N-1 ;

procédure entrer(m : message) ;
début
file[queue] := m ;
queue := (queue + 1) mod N ;
fin ;

procédure sortir( var m : message) ;
début
m := file[tête] ;
tête := (tête + 1) mod N ;
fin ;

début
n := 0 ;
tête := 0 ;
queue := 0 ;
fin

fin tampon.

Problème des lecteurs-rédacteurs

Soit un fichier (SGBD, ...) manipulé par deux sortes de processus différents :

les lecteurs qui consultent le fichier sans en modifier le contenu ;
les rédacteurs qui peuvent en modifier le contenu.

Soient nlect et nred le nombre de lecteurs et rédacteurs accédant au fichier à un instant donné.Il faut respecter les contraintes d'intégrité (maintien de la cohérence) :

nred = 0 et nlect 0 ;
nred = 1 et nlect = 0 ;

Moniteur lecteur_rédacteur
lecteur_rédacteur : moniteur ; `.` var ecr : booléen ; `.` nl : entier ; `.` c_ecr, c_lect : condition ; procédure début_lire ; début nl := nl + 1; si ecr alors `.` c_lect.attendre ; `.` c_lect.signaler ; fin ; procédure fin_lire ; début nl := nl - 1; si nl = 0 alors `.` c_ecr.signaler ; fin ; procédure début_écrire ; début si ecr ou nl > 0 alors `.` c_ecr.attendre ; ecr := vrai ; fin ; procédure fin_écrire ; début ecr := faux ; si nl > 0 alors `.` c_lect.signaler ; sinon `.` c_ecr.signaler ; fin ; début ecr := faux ; nl := 0 ; fin fin lecteur_rédacteur.

Moniteur lecteur_rédacteur

lecteur_rédacteur : moniteur ;

. var ecr : booléen ;
. nl : entier ;
. c_ecr, c_lect : condition ;

procédure début_lire ;
début
nl := nl + 1;
si ecr alors
. c_lect.attendre ;
. c_lect.signaler ;
fin ;

procédure fin_lire ;
début
nl := nl - 1;
si nl = 0 alors
. c_ecr.signaler ;
fin ;

procédure début_écrire ;
début
si ecr ou nl > 0 alors
. c_ecr.attendre ;
ecr := vrai ;
fin ;

procédure fin_écrire ;
début
ecr := faux ;
si nl > 0 alors
. c_lect.signaler ;
sinon
. c_ecr.signaler ;
fin ;

début
ecr := faux ;
nl := 0 ;
fin

fin lecteur_rédacteur.

Critiques :
La priorité est donnée aux lecteurs.

La mémoire virtuelle

Définition

Mémoire virtuelle = support de l'ensemble des informations potentiellement accessibles.

Ensemble des emplacements dont l'adresse peut être engendrée par le processeur.

Mémoire physique = Ensemble des emplacements RAM physiquement présents dans l'ordinateur.

Pourquoi une mémoire virtuelle ?

Mémoire physique coûteuse.Mémoire secondaire (disques, mémoire étendue, ...) peu coûteuse.
Programmes gourmands en mémoire et qui ne "tiennent pas" toujours en RAM.

Utiliser la mémoire secondaire "comme" mémoire RAM.

Idée générale

Il s'agit de conserver en mémoire une "partie" des programmes en cours d'exécution. Si un programme A veut s'exécuter alors qu'il n'y a plus de place en mémoire, un "bout" d'un autre programme est "viré" en mémoire secondaire et remplacé par un "bout" de A.Donc, un programme est decoupé en bouts que l'on nomme pages, de taille fixe. La mémoire physique est elle aussi découpée en pages, de même taille, ainsi que la mémoire secondaire.

Les problèmes de l'allocation mémoire

correspondance entre adresses virtuelles et adresses physiques ;
gestion de la mémoire physique ;

Et si multi-processus :

partage de l'information ;
protection mutuelle.

Correspondance adresses virtuelles - adresses physiques

On utilise une fonction topographique qui associe à une adresse virtuelle, une adresse réelle.Voici l'architecture classique d'accès à la mémoire :

Voici la fonction topographique :
Fonction topo(x : adresse_virtuelle) : adresse_réelle;
début
topo := f(x);
fin
Et voici l'architecture avec réimplantation dynamique :

La mémoire virtuelle, avec sa table des pages, est une implémentation possible de la fonction topographique.

La table des pages virtuelles

Présent	Modifié	Protection	Num page physique
... oui ...	... non ...	... rx ...	... 18 ...

Présent : page virtuelle présente en mémoire physique ?
Modifié : page modifiée ?
Protection : droits d'accès.
Num page physique : page physique correspondante.

La table des pages virtuelles est une implémentation particulière d'une fonction de pagination (il en existe d'autres).En général, c'est un bit dans le PSW (Program Status Word) qui indique si l'on utilise ou non la mémoire virtuelle.

Principes et mécanismes de base de la pagination

Soit un processeur avec un bus d'adresse sur 32 bits, il peut addresser 2^32 octets, soit 4 Go. L'ordinateur a une mémoire physique de 8 Mo.L = taille de la page ou de la case, par exemple 4096 octets, soit 2^12.
N = nombre de pages de la mémoire virtuelle, par exemple 1 Méga de pages, soit 2^20.
n = nombre de cases de la mémoire physique, par exemple 2048 cases, soit 2^11.

La mémoire virtuelle linéaire

Pourquoi mémoire virtuelle linéaire ?

L'adresse du 1er octet de la page n = l'adresse du dernier octet de la page (n-1) + 1.
Avantage : organisation identique à celle d'une mémoire physique.

Adresse Virtuelle Adresse Physique

Le calcul de l'adresse réelle à partir de l'adresse virtuelle se réalise ainsi :

le numéro de page virtuelle donne l'entrée de la TPV dans laquelle se trouve le numéro de page physique ;
le déplacement est le même (les pages physiques et virtuelles ont la même taille) ;
si la page virtuelle n'est pas présente en mémoire physique, alors il se produit un défaut de page.

Pour accélérer le processus, on utilise des mémoires associatives qui recencent les dernières pages utilisées :

Le défaut de page

L'adresse virtuelle référence une page qui n'est pas présente en mémoire physique. Le mécanisme d'adressage génère un défaut de page.Si la mémoire physique est pleine :

virer de la mémoire physique une page (remplacement) :
- choisir une page "victime",
- si elle a été modifiée, la réécrire sur disque,
- modifier les indicateurs de présence en TPV ;

Puis, dans tous les cas :

charger la page référencée en mémoire physique (placement) ;
modifier les indicateurs de présence en TPV.

Le choix d'une victime - remplacement

De nombreux algorithmes :

FIFO - First In First Out : ordre chronologique de chargement ;
LRU - Least Recently Used : ordre chronologique d'utilisation ;
FINUFO - First In Not Used, First Out (algorithme de l'horloge ou Clock) : approximation du LRU ;
LFU - Least Frequently Used ;
Random : au hasard ;
MIN : algorithme optimal.

Performances : MIN, LRU, FINUFO, [FIFO, Random].

Le préchargement - La localité

Optimisation du système : tenir compte de la localité en préchargeant des pages avant d'en avoir besoin.Localité : à un instant donné, les références observées dans un passé récent sont (en général) une bonne estimation des prochaines références.
En moyenne, 75% des références intéressent moins de 20% des pages. C'est la non-uniformité.

on va essayer d' anticiper la demande.

Le problème de la taille de la TPV

Pour être utilisée, la TPV doit être placée en mémoire physique.Par exemple, si on a 2^20 pages virtuelles, la TPV aura une taille d'à peu près 2^20 * taille d'une entrée = 10 Mo si une entrée tient sur 10 octets.
C'est à dire plus que la taille de la mémoire physique !!!!
Solution :

on va paginer la TPV.

Pagination à deux niveaux

La mémoire virtuelle est divisée en Hyperpages qui sont elles-mêmes divisées en pages.Une adresse virtuelle = numéro d'hyperpage ; numéro de page ; déplacement.
Attention ! L'accès à la mémoire est plus lent d'une indirection (utilisation de mémoires associatives).
La mémoire est toujours linéaire.

Structure d'un programme

Un programme destiné à être chargé en mémoire virtuelle se décompose ainsi :

En-tête : < nom, taille (en nombre de pages) >
Table de couplage :
- < page_virtuelle, nombre_de_pages, texte > (texte est en général une référence à un secteur disque qui contient le code)
- < page_virtuelle', nombre_de_pages', texte' >
- ...
Table des points d'entrées :
- < Entrée, adresse_exec >
- < Entrée, adresse_exec >
- ...

Problème : le code d'un programme est "absolu", c'est à dire qu'on ne peut pas le déplacer dans la mémoire virtuelle (il a une adresse fixe).Solution : posséder une fonction de couplage dynamique et un vecteur de translation. Mais celà coûte cher en performance.
Pour éviter les conflits d'implantation en mémoire virtuelle et la fragmentation, on associe une mémoire virtuelle à chaque utilisateur.

Avantages / Inconvénients de la pagination

Avantages :

Meilleure untilisation de la mémoire physique (programmes implantés par fragments, dans des pages non-consécutives).
Possibilité de ne charger des pages que lorsqu'elles sont référencées (chargement à la demande).
Indépendance de l'espace virtuel et de la mémoire physique (mémoire virtuelle généralement plus grande).
Possibilité de ne vider sur disque que des pages modifiées.
Possibilité de recouvrement dynamique (couplage).

Inconvénients :

Fragmentation interne (toutes les pages ne sont pas remplies).
Impossibilité de lier deux (ouo plusieurs) procédures liées aux mêmes adresses dans l'espace virtuel.

Mémoire virtuelle segmentée

La mémoire virtuelle = ensemble de segments.Un segment = suite d'emplacements consécutifs.
Adresse virtuelle = numéro de segment ; déplacement.
En général, les segments correspondent à un découpage logique d'un programme (segment de pile, de données, de code, ...).
L'algorithme de remplacement remplace un (ou plusieurs) segments entiers par le segment référencé.
Évidemment, il existe une table des segments.

Les segments

Options : le segment doit-il rester le plus longtemps possible en mémoire physique ?
Contenu : donne des informations à l'algorithme de remplacement. Si contenu = données modifiées

écriture sur disque (cher). Si code

rien à faire.

Problèmes

Un segment = des zone de mémoire contigües, d'où une gestion difficile de la mémoire (utilisation de "ramasse-miettes" - garbage collector).Idée : Paginer les segments !
On a une TPV par segment.
Une adresse segmentée = numéro de segment + déplacement dans le segment.
Un déplacement dans le segment = numéro de page virtuelle + déplacement dans la page.

Le partage de l'information en mémoire virtuelle linéaire

Le partage de l'information en mémoire segmentée

Les systèmes répartis

Qu'est-ce qu'un système réparti ?

Exemples de systèmes :

service de courrier électronique ;
systèmes de fichiers distants montés localement (NFS) ;
systèmes de réservations (voyage + hotel + vehicule) ;
...

Soit un système informatique constitué d'un ensemble de stations reliées entres elles par un moyen de communication.On veut implémenter un système de messagerie.
Un usager doit pouvoir émettre ou retirer des messages de n'importe quelle station.
Plusieurs implémentations possibles.

structure centralisée ;
structure décentralisée - ou répartie ;
structure mixte.

Structure centralisée

Tous les courriers sont stockés sur C (station centrale).
1 usager = 1 boîte aux lettres sur C.

volume de stockage important sur C.

disponibilité du service = disponibilité de C.

1 opération = 1 transfert d'informations.

Structure répartie

1 usager = 1 boîte aux lettres = 1 station de rattachement

Retrait d'un message sur station de rattachement = opération locale.
Dep\^ot ou retrait sur une autre station

échange d'informations.

dictionnaire Usager/Station-de-rattachement.
Disponibilité du système accrue.

Panne d'une station = empêche la réception des messages pour les usagers de cette station.

Volume de stockage global réparti sur l'ensemble des stations.

Une copie du répertoire sur chaque machine (attention à la mise-à-jour).

Structure mixte

On ajoute des stations relais.
Une station est reliée à une station relai et une seule.
Le relai stocke les messages des stations qui lui sont rattachées.
Tout usager dépend donc d'un seul relai.
Un message passe forcement par un relai.
Seuls les relais possèdent un dictionnaire.
Panne d'un relai

pénalise un ensemble d'usagers.
Moins de répertoires à mettre à jour.
Avantage : si une fraction importante du nombre de messages est échangée entre les utilisateurs d'un même relai.
Un station peut être un simple terminal.
En résumé : on préfère définir un système réparti par les services qu'il offre :

Structure modulaire.
Disponibilité accrue (même si un module tombe en panne, le service est rendu).
Décentralisation, destinée à accroître la localité du traitement avec la création de copies multiples, la multiplication des allocateurs et le changement d'implémentation du code et des données.

La notion du temps

Un processus P_1 sur une station A veut coopérer avec un processus P_2 sur une station B.Comment faire pour savoir qu'un evènement e de P_1 s'est déroulé avant (ou après) un evènement e' de P_1 ?

Il n'existe pas d'horloge commune (ou temps global).
À un instant donné, quel est l'état du système ?

Il faut que les processus échangent des messages.

Exemple

Soit un parking. Les usagers sont en compétition pour l'utilisation des places.1. Parking avec un accès unique, surveillé par un seul gardien : connaissance partielle de la situation

refus d'entrer alors qu'une voiture est en route vers la sortie.
2. Plusieurs accès avec un gardien à chaque accès : chaque gardien connaît avec retard les actions des autres gardiens

2 voitures sont autorisées à rentrer alors qu'il y a 1 seule place libre.

les gardiens doivent coopérer.

L'ordre partiel

Ordre local des évènements :
A1  A2  A3  A4  A5
B1  B2  B3  B4
Échanges de messages :
A2  B2 et B3  A4
Transitivité :
A1  A2  B2  B3  B4
B1  B2  B3  A4  A5
A1  A2  B2  B3  A4  A5
Exemples d'évènements incomparables :
B1 et A1, A2, A3
A3 et B2, B3, B4

Utilisation de l'ordre partiel

Hypothèses :

tout site communique avec tout autre site (maillage logique) ;
pas d'erreur de transmission ni de perte / duplication de messages ;
ordre de réception = ordre d'émission ;
une panne d'un site est détectée et signalée aux autres sites.

Producteur - Concommateur

Le producteur P et le concommateur C sont sur des sites différents (S_1 et S_2).NP = nombre de productions et NC = nombre de consommations.
C peut consommer ssi NP-NC > 0.
P peut produire ssi NP-NC < N.
Implémentation :

sur S_1, NP = le nombre de productions faîtes et NC', image de NC, incrémenté à chaque reception d'un message de C.
sur S_2, NC = le nombre de consommations faîtes et NP', image de NP, incrémenté à chaque reception d'un message de P.

Utilisation des compteurs d'évènements 1 compteur = variable entière non-décroissante, associée à une classe E.Primitives :

avancer(E) : augmente de 1 la valeur du compteur (arrivée d'un évènement de classe E) ;
consulter(E) : fournit la valeur du compteur ;
attendre(E, n) : suspend le processus tant que la valeur du compteur est inférieure à n.

- 2 compteurs d'évènements NP' et NC' initialisés à 0.- 2 variables entières NP et NC initialisées à 0.

Producteur P
attendre(NC', NP-N+1); { passage lorsque NP-NC' } production; avancer(NP'); NP := NP+1;

Consommateur C
attendre(NP', NC+1); { passage lorsque NP'-NC'>0 } consommation; avancer(NC'); NC := NC+1;

Ordre Total Strict

Ordre partiel dès fois insuffisant.On doit pouvoir avoir un ordre total strict.
Par exemple : allocation de ressources.
En centralisé : les requêtes et avis de libération sont ordonnés dans une file manipulée en Exclusion-Mutuelle, puis traitées en séquence.
En réparti :

si un seul message à la fois arrive, l'ordonnancement est strict ;
si plusieurs messages arrivent en même temps, il faut les ranger en EM dans une file locale ;
si on veut conserver ordre de réception = ordre d'émission, il faut pouvoir ordonner globalement l'émission des messages.

Exemple

Parking avec 3 gardiens G1, G2 et G3. état initial = 100 places libres.Les trois gardiens diffusent les messages suivants :

M1 : 20 places de plus sont libres ;
M2 : 10 places de plus sont occupées ;
M3 : je réserve 10% des places pour le nettoyage.

Résultat (exemples) :

Ordre d'envoi	Séquence 1 (msg, valeur)	Séquence 2 (msg, valeur)	Séquence 3 (msg, valeur)	Séquence 4 (msg, valeur)
init	-, 100	-, 100	-, 100	-, 100
1	M1, 120	M1, 120	M3, 90	M2, 90
2	M3, 108	M2, 110	M1, 110	M3, 81
3	M2, 98	M3, 99	M2, 100	M1, 101
final	-, 98	-, 99	-, 100	-, 101

Ordonancement au moyen d'estampilles

À chaque message, on associe un numéro appelé estampille.Cette estampille est la valeur instantannée, sur le site d'émission, d'une horloge logique locale à ce site.
Les horloges des différents sites sont recalées grâce à un dialogue.
Construction d'un ordre total strict [Lamport 78] :
Chaque site s est munie d'un compteur à valeurs entières H_s, appelé horloge logique.
H_s est incrémenté entre deux évènements successifs.
Un site e qui émet un message le marque d'une estampille E égale à la valeur courante de H_e.
À la réception du message, le site récepteur r met-à-jour H_r ainsi :
si H_r < E alors H_r := E+1 finsi
L'évènement << réception du message >> est daté par H_r.
On a une relation d'ordre total

Soient a et b deux évènements des sites (resp.) i et j alors :
a

H_i(a) < H_j(b)
Pour avoir un ordre total et strict

On associe le numéro du site à l'estampille.
a

(H_i(a) < H_j(b)) ou (H_i(a) < H_j(b) et i < j)

L'exclusion mutuelle - Algorithme

Solution centralisée : un site central reçoit les requêtes d'EM, les met dans une file FIFO.On veut répartir l'algorithme ( i.e. pas de site central).

une file par site.
Chaque site reçoit les requêtes et avis de libération de tous les autres sites.
On veut un ordre total strict (estampillage par horloge logique + numéro de site).
Pour qu'un site puisse prendre sa décision, il doit avoir reçu un message de chaque autre site (pas de message en transit).
Les envois de messages :

Messages (REQ, H_i, i) (de i vers tous) = le site i veut entrer en SC.
Messages (REL, H_i, i) (de i vers tous) = le site i sort de SC.
Messages (ACQ, H_i, i) (de i à j) = le site i a reçu du site j un (REQ, H_j, j).

Chaque site i maintient une file de messages avec 1 message par site. Au départ, chaque file contient M_i = (REL, H_init, i).H_init est la même pour tous les sites.
Si un site reçoit (REQ, H_i, i) ou (REL, H_i, i), ce message remplace M_i.
Si un site reçoit (ACQ, H_i, i), ce message remplace M_i sauf si M_i est un (REQ, H_i, i).
Le site i peut rentrer en SC si sa requête (REQ, H_i, i) précède tous les autres messages de la file d'attente.

Ordonnancement des évènements

Ordonnancement par séquenceur

Le séquenceur évite les trous dans la numérotation.Un séquenceur S délivre une valeur entière 0.
Fonction ticket(S).
Deux propriétés :
P1 : si a et b deux opérations ticket(S) alors a > b ou b > a.
P2 : si a est une exécution de t = ticket(S) alors t est le nombre d'opérations ticket(S) qui ont précédé a.
P1 est l'EM sur ticket(S) et P2 est l'absence de trous.

Le privilège

Mise en oeuvre générale d'un séquenceur = faire circuler un privilège entre les sites.Privilège = valeur courante du séquenceur.
Quand site i possède le privilège, il peut faire ticket(S).

Séquenceur circulant.

Séquenceur sur une voie à diffusion.

Séquenceur circulant - Anneau virtuel

Définir un itinéraire pour le parcours du privilège.Méthode simple = chaque site communique avec 2 sites voisins.
Un numéro unique est attribué à chaque site.
Chaque site i a un voisin successeur suiv(i) et un prédécesseur pred(i).

anneau virtuel.

suiv[i]=i+1 mod Npred[i]=i-1 mod N

Le privilège tourne toujours dans le même sens.
En cas de panne d'un site

reconstruction de l'anneau

reconfiguration (mise à jour des variables suiv et pred).
Site défaillant remis en route

réinsertion.

Séquenceur circulant - Variables d'état

1- Fonctionnement sans pannes.Soit K (K > 1).
Sur chaque site i, P_i assure la circulation du privilège.
Chaque P_i a une variable S[i] (0 S[i] K-1).
S[i] peut être modifiée par P_i et lue par P_suiv(i).
P_i possède le privilège quand :

S[i] S[i-1] pour i 0S[0] = S[N-1] pour i = 0

Lorsque P_i possède le privilège il doit l'abandonner au bout d'un temps fini :

S[i] := S[i-1] pour i 0S[0] := S[0] + 1 mod K pour i = 0

Équité = chaque processus reçoit le privilège à tour de rôle.
Exemple avec N=3, K=2 et S=000.
Évolution du système = 000 - 1 00 - 11 0 - 111 - 0 11 - 00 1

Séquenceur circulant - Panne d'un processus

Processus P_0

1- aucun nouveau front est créé.
2- disparition d'un front

regénération par P_0.
Processus P_0.

impossible de regénérer le front.
Le processus qui joue le rôle de P_0 est le seul tel que pred[i] > i.
Chaque processus est programmé pour jouer le rôle de P_0.

si (pred[i] > i) 
alors
  << Comportement selon P_0 >>
sinon
  << Comportement selon P_i >>

Séquenceur circulant - Réinsertion d'un processus

1- Reconfigurer l'anneau virtuel.2- réinitialiser S[i].
Il faut que j (j = suiv(i)) n'autorise pas la lecture de S[j] pendant la SC.

si (j < i) alors
  S[i] := S[j]-1 mod K
sinon
  S[i] := S[j]

Séquenceur circulant - Le jeton

Variable d'état = théorie.Le privilège = 1 jeton qui circule sur l'anneau.
Le jeton porte la valeur v.
Avant la transmission du jeton :

S[j]:=v pour j 0v := v+1 mod K; S[j]:=v pour j = 0

À chaque passage du jeton sur j, une horloge de garde est armée.
Si l'horloge se déclenche, j consulte S[i] (i = pred(j)).

si (j > i) et (S[j] S[i])
ou si (j < i) et (S[j] = S[i])
Alors le jeton est considéré comme perdu.

j le regénère avec S[i] et réarme son horloge.

Séquenceur sur une voie à diffusion

1 site accède au médium grâce à un communicateur.1 message envoyé par i est diffusé à tous les sites (y compris i).
Tous les communicateurs classent les messages dans le même ordre.

ordonnancement global.

Chaque site i a un compteur local cpt_i.

ticket(S) = requête dans file d'entrée.
i attend que la requête apparaisse dans la file de sortie.
le site i traite toutes les requêtes ticket(S).
Si site = j alors cpt_i++ sinon utiliser ticket puis cpt_i++.

En cas de panne du site i

Les autres sites continuent à fonctionner.Pour se réinsérer, i envoie une requête de réinsertion à j.
j renvoie un message de synchronisation.
Quand le message apparaît dans la file de sortie :

j envoie à i la valeur de cpt_j ;
i :

ignore tous les messages < synchro,
conserve tous les messages qui suivent (sans les traiter) jusqu'à la valeur de cpt_j,
met à jour son compteur.

Le Network File System de Sun (NFS)

Network File System de Sun (NFS)

NFS = système de fichiers distribué.Idée de base = pouvoir partager entre plusieurs clients et serveurs hétérogènes un même système de fichiers.
Une machine peut être à la fois client et serveur.
Un serveur NFS exporte ses directories pour qu'elles soient accessibles par des clients.
Si une directory est exportée, c'est tout le sous-arbre qui est exporté.
Liste des directories exportées dans /etc/exports.

Architecture

Un client qui veut accéder à une directory distante doit la monter dans sa propre hierarchie.Une station cliente sans disque (diskless) peut faire "comme si" elle avait un disque en montant des systèmes distants.
Une station avec un disque local aura une hierarchie en partie locale et distante.
Pour les programmes du client

pas de différence entre fichiers locaux ou distants.
Si deux clients ont monté la même directory, ils en partagent les fichiers.

simplicité de NFS.

Protocoles

NFS doit supporter des systèmes hétérogènes (clients DOS utilisant des processeurs Intel, serveurs tournant sur Sun Sparc, ...).

clients et serveurs utilisant différents OS et différentes machines.
Il est impératif de définir une bonne interface client/serveur.
Avantage d'une interface clairement définie : possibilité d'écrire de nouveaux clients et serveurs compatibles.
2 protocoles sont définis.
1 protocole pour le mounting et 1 protocole pour la directory et l' accès aux fichiers.

Mounting

Soit C le client et S le serveur.C envoie à S un chemin d'accès (le nom de la directory à monter) et demande la permission de monter la directory chez lui.
L'endroit où C va monter la directory n'est pas important pour S.
Si le chemin d'accès est correct et si la directory se trouve dans /etc/exports, S renvoie un file handle à C.
Le handle est composé :

du type du système de fichiers ;
du disque ;
du numéro de i-node de la directory ;
d'infos de sécurité (droits d'accès).

Pour lire ou écrire dans la directory montée, il faut utiliser ce handle.Un client peut monter des directory sans intervention humaine.
Ces clients ont un fichier /etc/rc shell script qui contient les commandes de mount et lancé automatiquement au boot.
C'est le static mounting.
Les versions récentes de Sun Unix ont l' automounting :
Des directory distantes sont associées à des directories locales, mais elles ne sont pas montées, et leurs serveurs ne sont pas contactés au boot.
La première fois qu'un client accède à un fichier distant, les serveurs sont contactés. Le premier qui répond gagne.

Automounting vs Static mounting

Avantages de l'automounting sur le static mounting :

si un des serveurs NFS nommé dans /etc/rc est down difficile de mettre en route le client ;
dans le static mounting, on ne contacte qu'un serveur pour chaque directory, alors qu'on peut en contacter plusieurs dans le automounting tolérance aux fautes.

Inconvénient : tous les serveurs "alternatifs" pour une même directory doivent être cohérents

surtout utilisé pour des systèmes de fichiers read-only.

Directory et accès aux fichiers

2ème protocole.Les clients envoient des messages pour manipuler des directories, lire et écrire des fichiers et leurs attributs (taille, date de modification, propriétaire, etc.).
Tous les appels systèmes sont pris en charge par NFS sauf OPEN et CLOSE.
OPEN et CLOSE ne sont pas utiles :

pour chaque opération read ou write, le client d'abord envoie une demande LOOKUP qui renvoie un file handle, le serveur ne garde pas trace de cette demande ;
une opération read ou write est accompagné du handle.

Si le serveur crashe

aucune info sur les fichiers ouvert est perdue (puisqu'il n'y en a pas).Un serveur NFS est stateless.

Problèmes

Un fichier Unix peut être ouvert et verrouillé (locked) pour empêcher les autres processus de l'utiliser.Fichier fermé

verrous relachés.
NFS est stateless, on ne peut pas associer de verrous à l'ouverture d'un fichier.
Il faut un mécanisme externe à NFS pour gérer le verouillage.
NFS utilise quand même le système de protection Unix (bits rwx pour le owner, group et world).
MAIS : le serveur NFS croit toujours le client pour valider un accès.
Que faire si le client ment ?
Utilisation de la cryptographie pour valider les requêtes.
Problème : les données, elles, ne sont pas cryptées.
Les clés sont gérées par le NIS ( Network Information Service, ou yellow pages)

Implémentation

La couche VFS maintient une table pour chaque fichier ouvert.
Chaque entrée est un v-node (virtual i-node). On indique si le fichier est local ou distant.
Exemple : la séquence < MOUNT, OPEN, READ >.

MOUNT

MOUNT :

le sysop envoie mount + remote directory + local directory + other ;
le programme mount parcours le nom de la remote dir et trouve le nom de la machine distante associée ;
mount contacte la machine et demande un handle pour cette directory ;
le serveur renvoie le handle si la requête est correcte ;
mount fait un appel système MOUNT (kernel).

Le kernel a la main :

il construit un v-node pour la remote dir ;
demande au client NFS de créer un r-node (remote i-node) dans sa table pour le file handle ;
le v-node pointe sur le r-node.

OPEN

OPEN :

le kernel parcours le nom du chemin d'accès, trouve la directory, voit qu'elle est distante et dans le v-node de la directory trouve le pointeur sur le r-node ;
le kernel demande au client NFS d'ouvrir le fichier ;
le client NFS récupère le nom du serveur dans le nom du chemin d'accès et un handle ;
le client crée un r-node et averti la VFS qui crée un v-node pointant sur le r-node ;
le processus appelant récupère un file descriptor, relié au v-node de la VFS.

Côté serveur, rien n'est créé.

READ

READ :

la VFS trouve le v-node correspondant ;
la VFS détermine si c'est local ou distant et quel est le i-node ou r-node à utiliser ;
le client NFS envoie une commande READ, avec le handle + l'offset.

Les transferts se font normalement 8ko / 8ko, même si moins d'octets sont demandés.Automatiquement, dès que le client a reçu les 8ko demandés, une nouvelle requête de 8ko est envoyée.
C'est le read ahead.

WRITE

Les transferts se font aussi 8ko / 8ko.Tant que les données écrites sont < 8ko, elles sont accumulées localement.
Dès que le client a écrit 8ko, les 8ko sont envoyé au serveur.
Quand un fichier est fermé, ce qui reste à écrire est envoyé au serveur.
Utilisation du caching :
les clients ont 2 caches : attributs et données.

problèmes de cohérences.

Cohérence du cache

Pas de solution "propre" : on essaie de réduire le risque au maximum, mais sans l'éviter tout à fait.

Un timer est associé à chaque entrée du cache. Quand le timer expire, l'entrée est annulée. Normallement 3s pour les données et 30s pour les attributs.
Quand un fichier "caché" est ouvert, le serveur est contacté pour savoir la date de la dernière mise-à-jour. Si MAJ plus récente que la copie, l'entrée est annulée.
Chaque 30s un timer expire et toutes les entrées sales sont envoyées au serveur.

Le Distributed Computing Environment de OSF

Définition

DCE = Distributed Computing Environment, de l'OSF (Open Software Foundation).OSF est un consortium de fabricants d'ordinateurs (IBM, DEC, HP, ...).
DCE n'est PAS un OS. C'est un ensemble de services et d'outils, qui tournent sur un OS existant, qui servent à la création et au déroulement d'applications distribuées.
DCE est indépendant des machines et des OS. On peut l'utiliser sur AIX, SunOS, Unix System V, Windows, OS/2, ...
DCE supporte aussi de nombreux matériels et logiciels réseaux (TCP/IP, X.25, ...).
L'approche DCE est l'inverse de l'approche micro-kernel.
Historique : DCE n'a pas été écrit "from scratch" (à partir de rien), il a été conçu à partir d'un "call for technology", pour obtenir les meilleures solutions aux problèmes de distribution.

L'architecture de DCE

Il y a 6 composants :

Threads package, la gestion des threads ;
Remote Procedure Call facility, la gestion des RPCs et du paradigme client/serveur ;
Distributed Time Service, la notion de temps global ;
Name services, la gestion des noms :
- Cell Directory Service,
- Global Directory Service,
- Global Directory Agent ;
Security Service, la gestion de la sécurité (authentification et autorisation) ;
Distributed File Service, le système distribué de gestion de fichiers.

L'organisation en cellules

DCE est un système qui peut être fortement étendu (il est "highly scalable").On peut rajouter des machines et des utilisateurs sans (trop) nuire aux performances.
Organisation en cellules, qui sont des unités manageables de taille raisonnable.
Une cellule = un ensemble d'utilisateurs, de machines ou autres qui ont un but en commun et partagent des services DCE communs.
Chaque cellule comprend au minimum : un server de répertoires de cellules, un serveur de sécurité et un serveur de temps global + des machines clientes.
Chaque client DCE a des processus clients pour gérer les facilités DCE.

Comment former une cellule

Par but commun, les personnes travaillant à un même but gagnent à être regroupées dans la même cellule.
Par intérêt administratif, il est plus facile d'administrer des utilisateurs si ceux-ci sont regroupés dans une seule cellule.
Par souci de sécurité, on préfèrera mettre dans une même cellule les machines d'utilisateurs qui ont le même degré de fiabilité.
Par coût d'utilisation, les usagers qui interagissent fortement entre eux seront placés dans une même cellule.

Les RPC sous DCE

RPC = la base de toute communication dans DCE.Les RPC-DCE dérivent du Network Computing System (NCS) développé par Apollo (partie de HP).
LES RPC-DCE utilisent la génération automatique de stubs :

Le "stub" client

Deux tâches :

CALL REQUEST.
- reçoit un "call request" du client,
- forme un message (pack) avec les spécifications de la procédure distante et les paramètres,
- demande au RPCRuntime de les transmettre au stub serveur.
RESULT.
- reçoit le résultat de l'exécution de la procédure du RPCRuntime,
- décode le message (unpack),
- transmet les données au client.

Le RPCRuntime

Gère la transmission des messages entre le client et le serveur.Responsable des retransmissions, acknowledges, etc.
Reçoit les messages du stub client et les envoie au stub serveur.
Reçoit les résultats du stub serveur et les envoie au stub client.

Le "stub" serveur

Deux tâches :

CALL REQUEST.
- reçoit un "call request" du RPCRuntime,
- décode le message (unpack),
- exécute l'appel de procédure locale (normalement) dans le serveur.
RESULT.
- reçoit le résultat de l'exécution de la procédure du serveur,
- forme un message (pack) avec les résultats,
- transmet les données au RPCRuntime.

Génération des stubs

Les stubs peuvent être générés de 2 façons :

manuellement, le concepteur des RPC offre un ensemble de fonctions pour que l'utilisateur fabrique ses propres stubs. Avantage : simple à implémenter (pour le concepteur) et peut gérer des paramètres de type complexe.
automatiquement, dans ce cas il faut utiliser un IDL (Interface Description Language) pour définir l'interface entre le client et le serveur. Cette interface est une liste de procédure, avec le type des paramètres et des résultats.

Exemple d'une interface écrite avec un IDL :

[uuid (bfsdfw345-345-3245-qwef-356-we45-ew54w-e4-5w-345)
 version (1.0)]
 
interface stateless_fs
{
  const long FILE_NAME_SIZE = 16
  const long BUFFER_SIZE = 1024
  typedef char FileName[FILE_NAME_SIZE];
  typedef char Buffer[BUFFER_SIZE];
  
  void read (
    [in] FileName   filename;
    [in] long       position;
    [in,out] long   nbytes;
    [out] Buffer    buffer;
  );
  
  void write (
    [in] FileName   filename;
    [in] long       position;
    [in,out] long   nbytes;
    [in] Buffer    buffer;
  );
}

Distributed File System

DFS est un système distribué de gestion de fichiers.Comme sous Unix, les fichiers ne sont pas structurés, et sont vus comme une suite de bytes.
DFS possède 4 niveaux d'agrégation :

Un fileset est un groupe de fichier semblable à un file system Unix.
Pourtant, à la différence d'Unix, un fileset est un sous-ensemble d'un file system (plusieurs filesets dans un aggregate).
Facilite la gestion des fichiers (un fileset = tous les fichiers d'un utilisateur ou d'un groupe d'utilisateurs, ...).
Lorsqu'une partition devient pleine, on peut dynamiquement faire migrer un fileset de cette partition vers une autre (avec plus d'espace).

L'accès aux fichiers DFS

Paradigme client / serveur et utilisation d'un cache de données (comme NFS).Une machine peut être soit client, soit serveur, soit les deux.
Du côté du serveur, on trouve :

Au niveau du Kernel :
1. Episode, c'est le file system local ;
2. Token manager, les jetons sont utilisés pour gérer les problèmes de cohérence du cache ;
3. File exporter, accepte les requêtes des clients et leur répond. Les interactions se font grâce aux RPC. Accepte aussi les demandes d'authentification pour l'établissement de connexions sûres.
Au niveau de l'espace utilisateur :
1. Fileset server, gère les filesets locaux ;
2. Fileset location server, conserve les informations sur quel DFS server gère quels filesets. ;
3. Replication server, maintient la consistance des filesets répliqués.

Note 1 : la taille d'une unité de transfert est de 64 Ko, à comparer avec les 8 Ko de NFS.Note 2 : DFS n'a pas de mécanisme de read-ahead.

La gestion de la cohérence

Caractéristique principale de DFS : chaque opération "read" voit les effets des précédentes opérations write.

Il existe différents types de token, suivant l'opération à effectuer :

type-specific tokens, il existe des tokens spécifiques pour les opérations : read, write, open, lock, check, ...
Fine-grained tokens, pour minimiser le false sharing, les tokens (pour read, write ou lock) ne concernent qu'une partie du fichier.

Chaque token a un délai d'expiration de 2 mn.

La mémoire partagée distribuée

Pourquoi une mémoire partagée distribuée ?

Limite physique des processeurs et mémoires.

utilisation de multi-processeurs pour accroître la puissance de calcul.
2 sortes de processeurs parallèles :

tightly coupled shared-memory multiprocessors;
distributed-memory multiprocessors.

Tightly coupled shared-memory multiprocessors

Distributed-memory multiprocessors

Avantages / inconvénients de la mémoire distribuée

Avantages :

Illusion d'une mémoire physique partagée, sans bottleneck.
Scalability (on peut étendre le système sans trop de difficulté).
coût moindre.

Inconvénients :

Topologie du réseau très importante.
Gestion du réseau.

Implémentation d'une mémoire distribuée

Accès mémoire partagé

Communication Inter-processus.Aucun processeur ne peut directement accèder à la mémoire d'un autre processeur

NORMA (NO Remote Memory Access) systems.
Les processeurs référencent leur propre mémoire locale. Il faut rajouter du software pour que lorsqu'un processeur référence une page distante, cette page soit récupérée.
L'espace d'adressage commun est découpé en morceaux.
Chaque morceau est situé sur une station.
Quand un processeur référence une page non-locale

"trap" (page fault)

DSM va récupérer la page.

Granularité des pages

Page de granularité importante, avantages :

réduction du traffic sur le réseau ;
propriété de localité.

Inconvénient :Problème du false sharing :

Partage des objets

Pour partager des objets, un processus doit pouvoir :

trouver l'objet ;
le récupérer.

Si l'objet reste toujours au même endroit (même station)

facile (répertoire).Si l'objet peut migrer

plus compliqué.

Solution centralisée

On a un serveur central qui garde trace de tous les déplacements d'objets.

on veut éviter ça.

tolérance aux fautes minime (disponibilité minime) ;
surcharge du serveur (performance minime) :
1. réduction du parallélisme (sérialisation des requêtes),
2. ralentissement de tout le système.

Autres solutions

Diffuser des messages de "Data Location".Problème : la diffusion ne se prête pas à la scalability.
De plus, la latence du réseau peut engendrer des délais de transmission importants.

les systèmes utilisent un schéma de distribution basé sur le site propriétaire.

Site propriétaire

1 objet = 1 site propriétaire (qui possède la copie primaire de l'objet).Le propriétaire change quand l'objet se déplace.
Au départ, les propriétaires sont connus (broadcast). Quand un site a besoin d'un objet

requête au propriétaire. Si le propriétaire n'a plus l'objet, il fait suivre la requête.
Problème : si l'objet bouge souvent

beaucoup de "sauts".

Amoeba

Définition

Amoeba = Système d'exploitation distribué.Projet commencé en 1981 a l'Université de Vrije (Pays-Bas).
But du projet = OS distribué pour le calcul parallèle (plusieurs processeurs) et distribué.
L'utilisateur se logge, édite des programme, les compile, lit son mail, etc.
Ces actions font intervenir différentes machines.
L'utilisateur ne le voit pas.
Un utilisateur ne se logge pas sur une machine particulière, mais au système entier.
Il n'y a pas de "home machine".
Le shell s'exécute sur une machine quelconque.
Les commandes s'exécutent sur des machines quelconques (en général différente de celle du shell).

le système recherche à chaque fois la machine la moins chargée.

Amoeba est très "location transparent".
Exemple de commande : amake (amoeba's make).
C'est le système qui détermine les compilations qui peuvent s'exécuter en parallèle ou en série et sur quelle(s) machine(s).
Un langage spécifique qui tient compte du parallélisme et de la distribution a été créé : Orca.

Architecture matérielle

Systèmes avec nombreux CPUs.
Chaque CPU mémoire de dizaines de Mo.

Pari : plus rentable d'avoir quelques systèmes multi-processeurs que des stations individuelles.

Utilisation maximum des processeurs (pas de stations dormantes dans les placards, cf. "big router is watching you").
Les CPUs dans un pool peuvent être de natures différentes. Théoriquement, le fils d'un processus peut tourner sur un processeur différent que son père.

Un pool de processeurs est moins cher qu'un ensemble de stations.Ce sont des cartes avec une connexion réseau.
Pas d'écran, de clavier ou de souris et partage de la même source d'énergie.
Si on a pas de pool de processeurs, on peut utiliser un pool de stations, éventuellement délocalisées.
On accède à Amoeba à travers un terminal X banalisé.

Architecture logicielle

2 parties distinctes :

un micro-noyau (1 par processeur) ;
un ensemble de serveurs qui implémentent les opérations classiques d'un SE.

Fonctionalités du micro-kernel :

gestion des processus et threads ;
gestion de base de la mémoire ;
gestion des communications ;
gestion des E/S de base.

Fonctionalités du micro-kernel

Notion de processus : x processus = x espaces d'adressage distincts.Notion de threads : x threads dans 1 processus = 1 seul espace d'adressage.
Gestion basique de la mémoire : les threads peuvent allouer et libérer des segments de mémoire.
Gestion des communications : paradigme client / serveur et diffusion. Le protocole de communication est FLIP.
Gestion des E/S : pour chaque chaque périphérique est associé un pilote (driver) dans le noyau.

Serveurs

Tout ce qui n'est pass fait par le kernel est fait par des serveurs.

Minimiser la taille du kernel.

Accroître la flexibilité : changer un serveur ou une version de serveur est facile.
On peut avoir en même temps plusieurs versions différentes pour des utilisateurs différents.
Au coeur de Amoeba = notion d' objet.

Objets

Objet = Abstract Data Type pour Amoeba.Données encapsulées + Opérations.
Un processus crée un objet

le serveur qui gère cela retourne une capacité ( capability) protégée par cryptage.
Touts les objets du système (objets physiques ou logiques) sont : nommés, protégés et gérés par des capabilities.
Exemple : fichiers, directories, segments mémoire, fenêtres, processeurs, disques, etc.
Interface uniforme

généricité et simplicité.

Serveur de fichiers

C'est le bullet server (bullet car il doit être rapide).Une fois créé, un fichier ne peut pas être modifié.

Moins de problèmes de cohérence des données.

Duplication facilitée.
Il y a le directory server qui gère les directories et le replication server.
L'utilisateur est libre d'utiliser les serveurs d'origine ou de créer ses propres serveurs.

Objets et capabilities

Une opération sur un objet = RPC sur le serveur qui le gère.Adresse des objets non-importante (même machine ou a l'autre bout du pays, ...).
Capacité =

Un client veut faire une opération :

Appel d'une stub-procedure qui construit un message contenant la capability ; passe la main au kernel.
Le kernel extrait le server port, regarde son cache pour savoir ou le serveur se trouve.
Si le port n'est pas dans le cache broadcast "où est-il ?".
Le port est une adresse logique.
La capability est envoyée au serveur.
Le champ object est utilisé par le serveur pour localiser l'objet.

Protection des objets

Quand un objet est créé, le champ Check est choisi au hasard est stocké dans la capability et dans les tables.La capability est renvoyé au client avec tous les droits ON.
Si le client veut utiliser lui-seul l'objet, il resttreint les droits.
Quand le serveur reçoit une capability

XOR avec les nouveaux droits

fonction one-way.
y = f(x) avec x facile de trouver y. Avec y, parcours exhaustif de toutes les valeurs possibles de x.