Université BORDEAUX 1 | U.F.R. Mathématiques et Informatique |
Epreuve de J.Bétréma | 27 mai 1999 |
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.
On suppose qu'on exécute la commande
SortMT 4 essai
où essai désigne un fichier de 1024 enregistrements.
/* 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; }
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 );