Системное программирование в среде Windows

Решение задачи сортировки слиянием (merge-sort), в которой сортируемый массив разбивается на несколько массивов меньшего размера, является классическим примером алгоритма, построенного на принципе "разделяй и властвуй". Каждый из массивов небольшого размера сортируется по отдельности, после чего отсортированные массивы попарно объединяются с образованием отсортированных массивов большего размера. Описанное слияние массивов попарно осуществляется вплоть до завершения всего процесса сортировки. В общем случае, сортировка слиянием начинается с массивов размерности 1, которые сами по себе не нуждаются в сортировке. В данном примере сортировка начинается с массивов большей размерности, чтобы на каждый процессор приходилось по одному массиву. Блок-схема используемого алгоритма показана на рис. 7.2.

Детали реализации представлены в программе 7.2. Число задач задается пользователем в командной строке. Временные показатели сортировки приведены в приложении В. В упражнении 7.9 вам предлагается изменить программу sortMT таким образом, чтобы она сначала определяла количество доступных процессоров, используя для этого функцию GetSystemInfo, а затем создавала по одному потоку для каждого процессора.

Заметьте, что эта программа эффективно выполняется в однопроцессорных системах, в которых имеется достаточно большой запас оперативной памяти, и обеспечивает значительное повышение производительности в SMP-системах. Предостережение. Представленный алгоритм будет корректно работать лишь при условии, что число записей в сортируемом файле нацело делится на число потоков, а число потоков выражается степенью 2. В упражнении 7.8 упомянутые ограничения снимаются.

Примечание

Изучая работу этой программы, постарайтесь отделить логику управления потоками от логики определения части массива, которую должна сортировать тот или иной поток. Обратите также внимание на использование функции qsort из библиотеки С, применение которой избавляет нас от необходимости самостоятельно разрабатывать эффективную функцию сортировки.

Программа 7.2. sortMT: сортировка слиянием с использованием нескольких потоков 

/* Глава 7. SortMT.

   Сортировка файлов с использованием нескольких потоков (рабочая группа).

   sortMT [параметры] число_задач файл */

#include "EvryThng.h"

#define DATALEN 56 /* Данные: 56 байт; ключ: 8 байт. */

#define KEYLEN 8

typedef struct _RECORD {

 CHAR Key[KEYLEN];

 TCHAR Data[DATALEN];

} RECORD;

#define RECSIZE sizeof (RECORD)

typedef RECORD * LPRECORD;

typedef struct _THREADARG { /* Аргумент потока */

 DWORD iTh; /* Номер потока: 0, 1, 2, … */

 LPRECORD LowRec; /* Младшая часть указателя записи */

 LPRECORD HighRec; /* Старшая часть указателя записи */

} THREADARG, *PTHREADARG;

static int KeyCompare(LPCTSTR, LPCTSTR);

static DWORD WINAPI ThSort(PTHREADARG pThArg);

static DWORD nRec; /* Общее число записей, подлежащих сортировке. */

static HANDLE* ThreadHandle;

int _tmain(int argc, LPTSTR argv[]) {

 HANDLE hFile;

 LPRECORD pRecords = NULL;

 DWORD FsLow, nRead, LowRecNo, nRecTh, NPr, ThId, iTh;

 BOOL NoPrint;

 int iFF, iNP;

 PTHREADARG ThArg;

 LPTSTR StringEnd;

 iNP = Options(argc, argv, _T("n"), &NoPrint, NULL);

 iFF = iNP + 1;

 NPr = _ttoi(argv[iNP]); /* Количество потоков. */

 hFile = CreateFile(argv[iFF], GENERIC_READ | GENERIC_WRITE, 0, NULL, OPEN_EXISTING, 0, NULL);

 FsLow = GetFileSize(hFile, NULL);

 nRec = FsLow / RECSIZE; /* Общее число записей. */