Université BORDEAUX 1 U.F.R. Mathématiques et Informatique
Epreuve de J.Bétréma 27 mai 1999


Maîtrise d'Informatique
Architecture Unix-NT

Durée: 2 heures
Tous documents interdits.

Le barème indicatif indique l'importance relative des questions ; une règle de trois sera appliquée lors de la correction pour obtenir des notes échelonnées entre 0 et 20.

1. Système de fichiers Unix

Note : cet exercice est simple, mais seules les réponses apportant des précisions techniques claires rapporteront des points. Eviter de perdre du temps avec des développements fumeux.
  1. (5 points) Le manuel de la commande Unix fsck (file system consistency check) explique que cette commande peut fonctionner en mode non interactif, et que dans ce cas seules les incohérences bénignes suivantes sont corrigées :
    1. inodes non référencés,
    2. compteur de liens trop élevé dans un inode,
    3. blocs manquants dans la liste des blocs libres,
    4. blocs figurant à la fois dans la liste des blocs libres et dans un fichier,
    5. comptes incorrects dans le super-bloc.
    Pour chacune de ces incohérences :
  2. (2 points) D'autre part les fichiers orphelins (alloués mais non référencés) sont placés dans le répertoire lost+found. Expliquer précisément de quoi il s'agit.
  3. (2 points) Donner un exemple d'incohérence grave, dont la réparation peut conduire à une perte ou à une altération de données.

2. Brins (threads)

Vous trouverez en annexe un programme de tri par fusion écrit pour l'API Win32 de Windows-NT. Les caractères gras désignent les parties essentielles pour la compréhension de la structure du programme.

On suppose qu'on exécute la commande

SortMT 4 essai

essai désigne un fichier de 1024 enregistrements.

  1. (8 points) Simuler l'exécution des 4 brins : pour chaque brin, et chaque variable intervenant dans l'exécution de la fonction ThSort, donner les valeurs successives prises par la variable. Expliquer la synchronisation entre les brins.
  2. (2 points) Expliquer brièvement la stratégie d'allocation mémoire adoptée pour la fonction MergeArrays ; où se trouvent, en fin de fusion, les enregistrements triés ?
  3. (2 points) Les brins sont créés en mode suspendu, puis leur exécution est lancée par la fonction ResumeThread. Expliquer les deux étapes du point de vue de l'ordonnanceur.
    (3 points) Exécuter les brins dès leur création pourrait faire apparaître un bug : lequel ?
  4. (4 points) Le fichier à trier est chargé en mémoire par la fonction ReadFile. Quelle autre solution serait-elle envisageable (on ne demande pas le code exact) ? Quelles sont les différences fondamentales entre les deux solutions ?

Annexe : programme

/* Chapter 10 SortMT.
    File sorting with multiple threads and merge sort.
    Syntax: sortMT nt file  */

/* LIMITATIONS:
    1.  The number of threads must be a power of 2
    2.  The number of 64-byte records must be a multiple
        of the number of threads. */

#define DATALEN 56
#define KEYLEN 8
typedef struct _RECORD {
    TCHAR Key [KEYLEN];
    TCHAR Data [DATALEN];
} RECORD;
#define RECSIZE sizeof (RECORD)
typedef RECORD * LPRECORD;

typedef struct _THREADARG { /* Thread argument */
    DWORD iTh;      /* Thread number: 0, 1, 3, ... */
    LPRECORD LowRec;    /* Low Record */
    LPRECORD HighRec;   /* High record */
} THREADARG, *PTHREADARG;

static DWORD WINAPI ThSort (PTHREADARG pThArg);
static int KeyCompare (LPCTSTR, LPCTSTR);

static DWORD nRec;  /* Total number of records to be sorted. */
static HANDLE * ThreadHandle;

int _tmain (int argc, TCHAR *argv[])
{
    HANDLE hFile;
    LPRECORD pRecords = NULL;
    DWORD FsLow, nRead, LowRecNo, nRecTh, NPr, ThId, iTh;
    BOOL NoPrint;
    int iFF, iNP;
    PTHREADARG ThArg;
    LPTSTR StringEnd;

    iNP = 1;
    iFF = 2;
    NPr = _ttoi (argv [iNP]);

    if (argc <= iFF)
        ReportError (_T ("Usage: sortMT nTh files."), 1, FALSE);

    hFile = CreateFile (argv[iFF], GENERIC_READ | GENERIC_WRITE,
            0, NULL, OPEN_EXISTING, 0, NULL);
    if (hFile == INVALID_HANDLE_VALUE)
        ReportException (_T ("Failure to open input file."), 2);
    
    FsLow = GetFileSize (hFile, NULL);
    if (FsLow == 0xFFFFFFFF)
        ReportException (_T ("Error getting file size."), 3);

    nRec = FsLow / RECSIZE; /* Total number of records. */
    nRecTh = nRec / NPr;    /* Records per thread. */
    ThArg = malloc (NPr * sizeof (THREADARG));  /* Array of thread args. */ 
    ThreadHandle = malloc (NPr * sizeof (HANDLE));
    
    pRecords = malloc (FsLow + sizeof (TCHAR)); /* Read the entire file. */
    
    if (!ReadFile (hFile, pRecords, FsLow, &nRead, NULL))
        ReportException (_T ("Error reading sort file."), 4);
    CloseHandle (hFile);
 /* Create the sorting threads. */

    LowRecNo = 0;
    for (iTh = 0; iTh < NPr; iTh++) {
        ThArg [iTh].iTh = iTh;
        ThArg [iTh].LowRec = pRecords + LowRecNo;
        ThArg [iTh].HighRec = pRecords + (LowRecNo + nRecTh);
        LowRecNo += nRecTh;
        ThreadHandle [iTh] = CreateThread (
                NULL, 0, ThSort, &ThArg [iTh], CREATE_SUSPENDED, &ThId);
    }

    /* Resume all the initially suspended threads. */

    for (iTh = 0; iTh < NPr; iTh++)
        ResumeThread (ThreadHandle [iTh]);

    /* Wait for the sort-merge threads to complete. */

    WaitForSingleObject (ThreadHandle [0], INFINITE);
    for (iTh = 0; iTh < NPr; iTh++)
        CloseHandle (ThreadHandle [iTh]);

    /*  Print out the entire sorted file. Treat it as one single string. */

    StringEnd = (LPTSTR) pRecords + FsLow;
    *StringEnd ='\0';
    if (!NoPrint) printf ("%s", (LPCTSTR) pRecords); 
    free (pRecords); free (ThArg); free (ThreadHandle);
    return 0;

} /* End of _tmain. */

static VOID MergeArrays (LPRECORD, LPRECORD);

DWORD WINAPI ThSort (PTHREADARG pThArg)
{
    DWORD GrpSize = 2, RecsInGrp, MyNumber, TwoToI = 1;
    LPRECORD First;

    MyNumber = pThArg->iTh;
    First = pThArg->LowRec; 
    RecsInGrp = pThArg->HighRec - First; 

    /* Sort this portion of the array. */

    qsort (First, RecsInGrp, RECSIZE, KeyCompare);
 /* Either exit the thread or wait for the adjoining thread. */

    while ((MyNumber % GrpSize) == 0 && RecsInGrp < nRec) {
        WaitForSingleObject (ThreadHandle [MyNumber + TwoToI], INFINITE);
        MergeArrays (First, First + RecsInGrp);
        RecsInGrp *= 2;
        GrpSize *= 2;
        TwoToI *=2;
    }
    ExitThread (0);
    return 0;   /* Suppress a warning message. */
}

static VOID MergeArrays (LPRECORD p1, LPRECORD p2)
{
    DWORD iRec = 0, nRecs, i1 = 0, i2 = 0;
    LPRECORD pDest, p1Hold, pDestHold;

    nRecs = p2 - p1;
    pDest = pDestHold = malloc (2 * nRecs * RECSIZE);
    p1Hold = p1;

    while (i1 < nRecs && i2 < nRecs) {
        if (KeyCompare ((LPCTSTR)p1, (LPCTSTR)p2) <= 0) {
            memcpy (pDest, p1, RECSIZE);
            i1++; p1++; pDest++;
        }
        else {
            memcpy (pDest, p2, RECSIZE);
            i2++; p2++; pDest++;
        }
    }
    if (i1 >= nRecs)
        memcpy (pDest, p2, RECSIZE * (nRecs - i2));
    else    memcpy (pDest, p1, RECSIZE * (nRecs - i1));

    memcpy (p1Hold, pDestHold, 2 * nRecs * RECSIZE);
    free (pDestHold);
    return;
}

int KeyCompare (LPCTSTR pRec1, LPCTSTR pRec2)
{
    DWORD i;
    TCHAR b1, b2;
    LPRECORD p1, p2;
    int Result = 0;

    p1 = (LPRECORD)pRec1;
    p2 = (LPRECORD)pRec2;
    for (i = 0; i < KEYLEN && Result == 0; i++) {
        b1 = p1->Key [i];
        b2 = p2->Key [i];
        if (b1 < b2) Result = -1;
        if (b1 > b2) Result = +1;
    }
    return  Result;
}

Annexe : documentation

Description des arguments des fonctions CreateFile, CreateThread et ReadFile :
HANDLE CreateFile(  LPCTSTR lpFileName,          // pointer to name of the file
  DWORD dwDesiredAccess,       // access (read-write) mode
  DWORD dwShareMode,           // share mode
  LPSECURITY_ATTRIBUTES lpSecurityAttributes,
                               // pointer to security attributes
  DWORD dwCreationDisposition,  // how to create
  DWORD dwFlagsAndAttributes,   // file attributes
  HANDLE hTemplateFile          // handle to file with attributes to 
                                //  copy);

HANDLE CreateThread(
  LPSECURITY_ATTRIBUTES lpThreadAttributes,  // pointer to security attributes
  DWORD dwStackSize,                         // initial thread stack size
  LPTHREAD_START_ROUTINE lpStartAddress,     // pointer to thread function
  LPVOID lpParameter,                        // argument for new thread
  DWORD dwCreationFlags,                     // creation flags
  LPDWORD lpThreadId                         // pointer to receive thread ID
);
 
BOOL ReadFile(
  HANDLE hFile,                // handle of file to read
  LPVOID lpBuffer,             // pointer to buffer that receives data
  DWORD nNumberOfBytesToRead,  // number of bytes to read
  LPDWORD lpNumberOfBytesRead, // pointer to number of bytes read
  LPOVERLAPPED lpOverlapped    // pointer to structure for data
);