Projet de Systèmes (Licence 1998-1999)

Jean-Baptiste Yunès, Tristan Crolard, François Pottier

Résumé:

Simulation d'un système de fichiers, gestion de caches...

La simulation devra être réalisée entièrement sous Unix, en langage C et sur les machines de l'UFR. La réalisation pourra être faite par groupe de 3 personnes au plus.

Introduction

Le schéma suivant illustre l'architecture générale qui devra être réalisée.

$\psfig{file=schema.eps,width=15cm}$

Ici 4 processus Unix communiquent. Le premier processus réalise le calcul pour une certaine commande utilisant le système de fichiers. Ce processus aura été écrit en utilisant une bibliothèque qui utilisera un tube nommé pour communiquer avec le processus réalisant le système de caches. Des requêtes seront envoyés à ce dernier pour lire/écrire des blocs. L'interprétation de ces blocs sera réalisée par les fonctions de la bibliothèque.

Le système de caches utilisera un tube nommé pour renvoyer les réponses au premier processus. Le système de caches devra tenter de répondre au plus vite au processus demandeur ; si les données sont déjà présentes il les renvoient. Dans le cas contraire il devra s'adresser à l'un des disques pour réaliser l'opération. Mais le disque réalisera la requête de façon asynchrone, de façon que le système de caches puisse continuer (éventuellement) à servir d'autres requêtes (à condition qu'elles ne soient pas incompatibles avec celles en cours). Les caches devront être gérés en utilisant la politique de libération dite « moins récemment utilisé » (LRU). En tout cas les requêtes en entrée doivent être lues le plus rapidement possible.

Le pilote de disque reçoit les requêtes mais lit ou écrit les données dans un segment de mémoire partagée détenu par le système de caches. Chaque pilote n'effectue qu'une seule requête à la fois. On pourra considérer que l'un des deux disques contient les blocs logiques de numéro pair ; tandis que l'autre contient ceux de numéro impair. Pour simuler la « lenteur » des disques ceux-ci devront être rendus incapables de répondre à plus d'une requête par seconde.

Le système de fichiers

Le système de fichiers est à la Unix, c'est-à-dire constitué d'in $\oe$ uds. Le nombre d'in $\oe$ uds maximum qu'un disque logique puisse contenir est MAX_INOEUDS. Chaque in $\oe$ ud étant soit un fichier normal, soit un répertoire :

struct inoeud {
    short type;        // 0 pour répertoire et 1 pour fichier normal
    short numero;      // 0 si entrée libre, 2 pour racine du SGF
    short taille;      // taille des données mesurée en octets
    short liens;       // nombre de références pour cet inoeud
    short directs[11]; // 11 premiers blocs logiques de données
    short indirects;   // bloc contenant des numéros de blocs
};

Les blocs de données d'un in $\oe$ ud répertoire constituent une liste de couples :

struct entree_repertoire {
    short numero;    // 0 si entrée libre
    char  nom[30];   // . pour le répertoire lui-même et .. pour son père
};

Les premiers blocs du disque logique contiennent la table des in $\oe$ uds. L'in $\oe$ ud numéro 0 n'est pas utilisé. L'in $\oe$ ud numéro 1 permet de parcourir la liste des blocs inutilisés du système de fichiers : chaque bloc libre du disque logique (c'est-à-dire non occupé par la table des in $\oe$ uds ou par des données attachées à un in $\oe$ ud) contient le numéro du bloc libre suivant dans la liste (premier « short » dans le bloc).

struct bloc_libre {
    short suivant;
    char rien[TAILLE_BLOC-sizeof(short)];
};
struct bloc_table_inoeuds {
    struct inoeud inoeuds[TAILLE_BLOC/sizeof(struct inoeud)];
};
struct bloc_donnees {
    char donnees[TAILLE_BLOC];
};
union bloc {
    struct bloc_donnees       donnees;
    struct bloc_table_inoeuds table_inoeuds;
    struct bloc_libre         libre;
};

Le numéro du premier bloc de la liste se trouve dans le champ indirects de l'in $\oe$ ud numéro 1. Le nombre de blocs encore libres est disponible dans le champ taille de l'in $\oe$ ud numéro 1.

Le disque logique

Le support du système de fichiers sera un disque logique constitué de blocs logiques au nombre de N_BLOCS_LOGIQUES chacun de taille TAILLE_BLOC.

Les disques physiques

Un disque physique devra contenir N_BLOCS_PHYSIQUES_DISQUE blocs de taille TAILLE_BLOC octets.

Le système devra utiliser N_DISQUES_PHYSIQUES

Architecture de la simulation

La simulation devra être organisée de la façon suivante :

Simulation du disque logique

Le disque logique devra être implanté par un processus Unix ayant comme point d'entrée un tube nommé (de nom ¨entree_cache¨). Ce tube nommé est destiné à recevoir des requêtes de lecture ou d'écriture de bloc. Voici la structure d'une requête :

#define LECTURE 0
struct lecture_bloc {
    int taille;                // taille de la requête elle-même en octets
    short type;                // == LECTURE
    short numero;              // numéro du bloc logique à lire
};
#define ECRITURE 1
struct ecriture_bloc {
    int taille;                // taille de la requête elle-même en octets
    short type;                // == ECRITURE
    short numero;              // numéro du bloc logique à écrire
    union bloc le_bloc;        // données à écrire dans le bloc
};
#define SYNCHRONISATION 2          // requête provoquant le vidage des caches
struct synchronisation {
    int taille;                // taille de la requête
    short type;                // == synchronisation
};

Lorsqu'un processus Unix désire effectuer une lecture/ou une écriture de bloc sur le disque il doit envoyer la requête correspondante dans le tube. Le processus « disque logique » effectuera l'opération puis renverra la ou les valeurs de retour dans un tube nommé (de nom ¨REPONSE¨). Il existe deux valeurs de retour possible :

#define RETOUR_ECRITURE 1
#define OK 1
#define PAS_OK 0
struct reponse_ecriture {
    int taille;                // taille de la requête elle-même en octets
    short type;                // == RETOUR_ECRITURE
    short bloc;                // numéro du bloc logique concerné
    short retour;              // == OK ou PAS_OK
};
#define RETOUR_LECTURE 0
struct reponse_lecture {
    int taille;                // taille de la requête elle-même en octets
    short type;                // == RETOUR_LECTURE
    short bloc;                // numéro du bloc logique concerné
    short retour;              // == OK ou PAS_OK
    union bloc le_bloc;        // données lues si retour==OK
};
#define RETOUR_SYNCHRONISATION
struct reponse_synchronisation {
    int taille;
    short type;
};

Un système de caches doit être implanté dans le « disque logique ». Une opération de lecture ou d'écriture doit être réalisée immédiatement si les données sont disponibles dans le cache. Si ce n'est pas le cas le « disque logique » doit trouver un cache libre puis envoyer une requête de lecture ou d'écriture réelle au disque physique correspondant au bloc à lire ou écrire (chaque disque physique prends en charge un sous-ensemble de blocs, par exemple le premier disque physique peut prendre en charge les blocs logiques de numéro pair, le second les numéro impairs...). Mais attention : le « disque logique » ne doit pas être bloqué, autrement dit il ne doit pas attendre le résultat de l'opération physique pour essayer de continuer à traiter les autres requêtes. Il doit donc y avoir une concurrence (ou une parallélisation) des accès aux disques physiques. Le résultat d'une opération physique est rendu disponible lorsque le disque physique le signale.

#define B_SERVICE 0
#define B_LIBRE   1
#define B_PROPRE  2

#define CACHE_EST_EN_SERVICE(etat) ((etat)&(1<<(B_SERVICE)))
#define CACHE_EST_LIBRE(etat)      ((etat)&(1<<(B_LIBRE)))
#define CACHE_EST_OCCUPE(etat)     (!(CACHE_EST_LIBRE(etat)))
#define CACHE_EST_PROPRE(etat)     ((etat)&(1<<(B_PROPRE)))
#define CACHE_EST_A_VIDER(etat)    (!(CACHE_EST_PROPRE(etat)))

struct cache {
    union bloc *bloc;           // pointeur vers la mémoire partagée
    int temps;                  // utilisée pour le LRU
    int etat;                   // EN_SERVICE, A_VIDER, PROPRE, LIBRE
    short bloc;                 // numéro du bloc dans le cache
};

Simulation d'un disque physique

Un disque physique est un processus chargé d'effectuer des opérations de lecture ou d'écriture de blocs cachés par le « disque logique » depuis ou vers le fichier Unix correspondant. Les requêtes sont lues depuis un tube non nommé et sont de deux types :

#define LECTURE_PHYSIQUE 0
struct lecture_physique {
    short type;        // == LECTURE_PHYSIQUE
    short cache;       // numéro du bloc caché
    short bloc;        // numéro du bloc disque à lire
};
#define ECRITURE_PHYSIQUE 1
struct ecriture_physique {
    short type;        // == LECTURE_PHYSIQUE
    short cache;       // numéro du bloc caché
    short bloc;        // numéro du bloc disque à écrire
};

L'échange des données entre un disque physique et le disque logique se fait par l'intermédiaire d'un segment de mémoire partagée contenant l'ensemble des blocs cachés. Le champ cache indique quel est le numéro du cache dans le segment. Le champ bloc indique quel est le numéro de bloc physique à lire ou à écrire dans le cache.

Lorsque le disque physique a terminé son travail il doit prévenir le processus « disque logique » en envoyant un signal (différent pour chaque disque physique).

Implantation du SGF

Les opérations de manipulation du SGF doivent être implantées sous forme d'une bibliothèque de fonctions. Ces fonctions doivent utiliser le « disque logique » pour obtenir les informations nécessaires pour réaliser sys_open(), sys_read(), sys_write(), sys_close(), sys_lseek(), sys_opendir(), sys_readdir(), sys_closedir(), sys_mkdir(),sys_rmdir(), sys_creat(), sys_unlink().

Commandes externes

Quelques commandes externes sont à réaliser :

copy_from_unix < f1> < f2> qui permet de copier un fichier Unix < f1> dans sur le SGF simulé sous le nom < f2> .
copy_to_unix < f1> < f2> qui réalise l'inverse.
copy < f1> < f2> qui réalise une copie depuis et vers le SGF simulé.
dir < rep> qui permet de lister le contenu d'un répertoire du SGF simulé.
type < f> qui permet de lister le contenu d'un fichier normal du SGF simulé.
delete < f> qui permet de détruire un fichier normal du SGF simulé.
remove < rep> qui permet de détruire un répertoire du SGF (s'il est vide).
mkdir < rep> qui permet de créer un répertoire dans le SGF.
mkdisque qui permet de créer (formater) un disque vide.
videdisque qui permet de vider les caches sur les disques physiques.

Programme de réalisation

Sont à réaliser :

un programme de simulation de disque physique. L'exécutable devra se nommer ¨disque¨, et prendre trois arguments : ¨disque < clé> < signal> < fichier>¨. La < clé> sera utilisé par le disque physique pour accéder au segment de mémoire partagée contenant les données du cache. Le < signal> est le numéro de signal à utiliser pour prévenir le processus « cache » que l'opération est terminée. Le < fichier> est la référence Unix du fichier contenant les blocs gérés par le disque physique. Le programme « disque physique » lira ses requêtes sur son entrée standard (tube non nommé) hérité de son père (le cache). Rappel : le disque ne doit pas servir plus d'une requête par seconde.
un programme de simulation du cache. L'exécutable devra se nommer ¨cache¨. Son lancement devra provoquer la création des processus « disque physique ». Il devra en outre lire ses requêtes depuis un tube nommé ¨entree_cache¨ et renvoyer les réponses dans un tube nommé ¨sortie_cache¨.
une bibliothèque de bas niveau permettant d'accéder au disque logique. Cette bibliothèque devra implanter au moins trois fonctions : lire_bloc(), ecrire_bloc() et synchronisation(). Ces fonctions doivent permettre de formater le disque logique (disque vide : un répertoire racine !).
une bibliothèque de niveau intermédiaire permettant d'accéder aux objets du système de fichiers. On y trouvera des fonctions comme (liste non exhaustive) :
- ref_vers_inum() permettant de « traduire » une référence en numéro d'in $\oe$ ud.
- inum_vers_inoeud() permettant de récupérer un in $\oe$ ud à partir de son numéro.
- inud_libre() permettant de récupérer un in $\oe$ ud libre.
- libere_inud() permettant de libérer un in $\oe$ ud utilisé.
- bloc_libre() permettant de récupérer un bloc de données libre.
- libere_bloc() permettant de libérer un bloc de données utilisé par un in $\oe$ ud.
une bibliothèque de haut niveau implantant les fonctions « externes » du système de fichiers (sys_open()...).
quelques commandes « externes » en utilisant les fonctions de la/les bibliothèque(s).
un rapport devra être rédigé dans lequel devront être clairement décrits vos choix (relations entre les fichiers sources, bibliothèques, structures internes, ...). Il ne s'agit pas de recopier le sujet !!! Les critiques sont les bienvenues et surtout en ce qui concerne les problèmes rencontrés, les limites observées, les améliorations auxquelles on pourrait penser, le mode de travail utilisé, etc.

Conseils : ne vous lancez pas avec précipitation dans le codage ! Prenez le temps de bien comprendre le fonctionnement du système à simuler. Essayez de simuler quelques petites choses à la main (papier + crayon) en prenant des exemples. Échangez vos idées, consultez vos enseignants... Les choix que vous aurez à faire sont très importants et peuvent vous mener à des impasses.

Définitions

Les définitions suivantes ne sont pas contractuelles. Si vous désirez modifier certaines choses il reste nécessaire d'en conserver l'esprit.

#define MAX_INOEUDS 80

// Types possibles pour un inoeud
#define INOEUD_REPERTOIRE 0
#define INOEUD_NORMAL     1
#define EST_REPERTOIRE(i) ((i).type==INOEUD_REPERTOIRE)
#define EST_NORMAL(i)     ((i).type==INOEUD_NORMAL)

// Numéro des inoeuds spéciaux
#define INOEUD_LIBRE              0
#define INOEUD_LISTE_BLOCS_LIBRES 1
#define INOEUD_RACINE             2
#define EST_LIBRE(i) ((i).numero==INOEUD_LIBRE)

// Structure d'un inoeud
struct inoeud {
    short type;        // 0 pour répertoire et 1 pour fichier normal
    short numero;      // 0 si entrée libre, 2 pour racine du SGF
    short taille;      // taille des données mesurée en octets
    short liens;       // nombre de références pour cet inoeud
    short directs[11]; // 11 premiers blocs logiques de données
    short indirects;   // bloc logique contenant les numéros des blocs
                       // logiques suivants.
};

// Nombre de blocs logiques
#define N_BLOCS_LOGIQUES 1024

#define REFERENCE_LIBRE 0
// Une entrée de répertoire
struct entree_repertoire {
    short numero;    // 0 si entrée libre
    char  nom[30];   // . pour le répertoire lui-même et .. pour son père
};
// Un bloc logique libre
struct bloc_libre {
    short suivant;
    char rien[TAILLE_BLOC-sizeof(short)];
};
// Un bloc logique contenant un fragment de la table des inoeuds
struct bloc_table_inoeuds {
    struct inoeud inoeuds[TAILLE_BLOC/sizeof(struct inoeud)];
};
// Un bloc de données pour un fichier standard
struct bloc_donnees {
    char donnees[TAILLE_BLOC];
};
// Un bloc de répertoire contenant un fragment de ce répertoire
struct bloc_repertoire {
    struct entree_repertoire references[TAILLE_BLOC/sizeof(struct entree_repertoire)];
};
union bloc {
    struct bloc_donnees       donnees;
    struct bloc_table_inoeuds table_inoeuds;
    struct bloc_libre         libre;
};

// Taille d'un bloc logique et physique mesurée en octets
#define TAILLE_BLOC 256

// Nombre de disques physiques
#define N_DISQUES_PHYSIQUES 2

// Nombre de blocs physiques par disque
#define N_BLOCS_PHYSIQUES_DISQUE (N_BLOCS_LOGIQUES/N_DISQUES_PHYSIQUES)

// Type des requêtes pour le disque logique
#define LECTURE  0
#define ECRITURE 1
#define SYNCHRONISATION 2
struct lecture_bloc {
    int taille;                // taille de la requête elle-même en octets
    short type;                // == LECTURE
    short numero;              // numéro du bloc logique à lire
};
struct ecriture_bloc {
    int taille;                // taille de la requête elle-même en octets
    short type;                // == ECRITURE
    short numero;              // numéro du bloc logique à écrire
    union bloc le_bloc;        // données à écrire dans le bloc
};
struct synchronisation {
    int taille;                // taille de la requête
    short type;                // == SYNCHRONISATION
};


// Type des retours des requêtes effectuées par le disque logique
#define RETOUR_LECTURE  0
#define RETOUR_ECRITURE 1
#define RETOUR_SYNCHRONISATION
struct reponse_ecriture {
    int taille;                // taille de la requête elle-même en octets
    short type;                // == RETOUR_ECRITURE
    short bloc;                // numéro du bloc logique concerné
    short retour;              // == OK ou PAS_OK
};
struct reponse_lecture {
    int taille;                // taille de la requête elle-même en octets
    short type;                // == RETOUR_LECTURE
    short bloc;                // numéro du bloc logique concerné
    short retour;              // == OK ou PAS_OK
    union bloc le_bloc;        // données lues si retour==OK
};
struct reponse_synchronisation {
    int taille;
    short type;
};

// Qualité des valeurs de retour
#define PAS_OK 0
#define RATE   (PAS_OK)
#define OK     1

// Type des requêtes physiques
#define LECTURE_PHYSIQUE  0
#define ECRITURE_PHYSIQUE 1

// Signaux utilisés par les disques physiques
#define PREMIER_SIGNAL (SIGUSR1)
#define INTERRUPTION_PHYSIQUE_DISQUE_NUMERO(i) (PREMIER_SIGNAL+((i)-1)
#define INTERRUPTION_DISQUE(i) INTERRUPTION_PHYSIQUE_DISQUE_NUMERO(i)

// Pour les caches
#define N_CACHES 20

#define B_SERVICE 0
#define B_LIBRE   1
#define B_PROPRE  2
#define CACHE_EST_EN_SERVICE(etat) ((etat)&(1<<(B_SERVICE)))
#define CACHE_EST_LIBRE(etat)      ((etat)&(1<<(B_LIBRE)))
#define CACHE_EST_OCCUPE(etat)     (!(CACHE_EST_LIBRE(etat)))
#define CACHE_EST_PROPRE(etat)     ((etat)&(1<<(B_PROPRE)))
#define CACHE_EST_A_VIDER(etat)    (!(CACHE_EST_PROPRE(etat)))
struct cache {
    union bloc *bloc;           // pointeur vers la mémoire partagée
    int temps;                  // utilisée pour le LRU
    int etat;                   // EN_SERVICE, A_VIDER, PROPRE, LIBRE
    short bloc;                 // numéro du bloc dans le cache
};

// Fonction de la bibliothèque
int sys_creat(char *ref);
int sys_unlink(char *ref);

#define O_RDONLY 1
#define O_WRONLY 2
#define O_RDWR   3
int sys_open(char *ref,bib_mode mode);

short sys_read(int desc,void *tamp,short taille);
short sys_write(int desc,void *tamp,short taille);
#define DEBUT   0
#define RELATIF 1
#define FIN     2
short sys_lseek(int desc,bib_seek mode,short deplacement);

int sys_close(desc);

int sys_mkdir(char *ref);
int sys_rmdir(char *ref);

int sys_opendir(char *ref);
int sys_readdir(int desc,struct entree_repertoire &ent);
int sys_closedir(desc);

Jean-Baptiste Yunes 2001-04-23