| 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
);