Потоки и производительность
Программы grepMP и grepMT по своей структуре и сложности сопоставимы друг с другом, однако, как и следовало ожидать, программа grepMT характеризуется более высокой производительностью, так как переключение между потоками осуществляется ядром намного эффективнее, чем переключение между процессами. В приложении В показано, что эти теоретические ожидания отвечают действительности, и это особенно заметно в тех случаях, когда файлы размещены на различных дисках. Оба варианта реализации способны работать в SMP-системах, существенно улучшая показатели производительности в терминах общего времени выполнения (истекшего времени); потоки, независимо от того, принадлежат ли они одному и тому же или разным процессам, параллельно выполняются на различных процессорах. Измеренное пользовательское время в действительности превышает общее время выполнения, поскольку рассчитывается в виде суммарной величины для всех процессоров.
В то же время, существует весьма распространенное заблуждение, суть которого состоит в том, что отмеченный параллелизм, независимо от того, касается ли он использования нескольких процессов, как в случае grepMP, или же применения нескольких потоков, как в случае grepMT, способен приводить к повышению производительности лишь в случае SMP-систем. Выигрыш в производительности можно получить и при использовании нескольких дисков, а также при любом другом распараллеливании в системе хранения. Во всех подобных случаях операции ввода/вывода с участием нескольких файлов будут осуществляться в параллельном режиме.
Модель "хозяин/рабочий" и другие модели многопоточных приложений
Программа grepMT демонстрирует модель многопоточных приложений, носящую название модели "хозяин/рабочий" ("boss/worker"), а рис. 6.3, после замены в нем термина "процесс" на термин "поток", может служить графической иллюстрацией соответствующих отношений. Главный поток (основной поток в данном случае) поручает выполнение отдельных задач рабочим потокам. Каждый рабочий, поток получает файл, в котором она должна выполнить поиск, а полученные рабочим потоком результаты передаются главному потоку во временном файле.
Существуют многочисленные вариации этой модели, одной из которых является модель рабочей группы (work crew model), в которой рабочие потоки объединяют свои усилия для решения одной задачи, причем каждый отдельный поток выполняет свою небольшую часть работы. Модель рабочей группы используется в нашем следующем примере (рис. 7.2). Рабочие группы даже могут самостоятельно распределять работу между собой без получения каких-либо указаний со стороны главного потока. В многопоточных программах может быть применена практически любая из схем управления, разработанных для коллективов в человеческом обществе.
Рис. 7.2. Выполнение сортировки слиянием с использованием нескольких потоков
Двумя другими основными моделями являются модель "клиент/сервер" (client/server) (проиллюстрирована на рис. 7.1, а пример ее практической реализации рассматривается в главе 11) иконвейерная модель (pipeline model), в которой выполнение задания передается от одного потока к другому (пример многоступенчатого конвейера рассматривается в главе 10 и иллюстрируется на рис. 10.1).
При проектировании многопоточных систем эти модели обладают целым рядом преимуществ, к числу которых можно отнести следующие:
• Большинство проблем многопоточного программирования могут быть разрешены с использованием одной из стандартных моделей, облегчающих проектирование, разработку и отладку программ.
• Применение понятных и проверенных моделей не только позволяет избежать многих ошибок, которые легко допустить при написании многопоточных программ, но и способствует повышению производительности результирующих приложений.
• Эти модели естественным образом соответствуют структуре большинства обычных задач программирования.
• Программистам, сопровождающим программу, будет гораздо легче понять ее устройство, если она будет описана в документации на понятном языке.
• Находить неполадки в незнакомой программе гораздо легче, если ее можно анализировать в терминах моделей. Очень часто главную причину неполадок удается установить на основании видимых нарушений базовых принципов одной из моделей.
• Многие распространенные дефекты программ, например, нарушение условий состязаний задач и их блокирование, также можно описать с использованием простых моделей, к числу которых относятся эффективные методы использования объектов синхронизации, описанные в главах 9 и 10.
Эти классические модели потоков реализованы во многих ОС. В модели компонентных объектов (Component Object Model, COM), широко используемой во многих Windows-системах, применяется другая терминология, и хотя рассмотрение модели СОМ выходит за рамки данной книги, об этих моделях говорится в конце главы 11, где они сравниваются с другими примерами программ.
Пример: применение принципа "разделяй и властвуй" для решения задачи сортировки слиянием в SMP-системах
Этот пример демонстрирует возможности значительного повышения производительности за счет использования потоков, особенно в случае SMP-систем. Основная идея заключается в разбиении задачи на более мелкие составляющие, распределении выполнения подзадач между отдельными потоками и последующем объединении результатов для получения окончательного решения. Планировщик Windows автоматически назначит потокам отдельные процессоры, в результате чего задачи будут выполняться параллельно, снижая общее время выполнения приложения.
Эта стратегия, которую часто называют стратегией "разделяй и властвуй" (divide and conquer), илимоделью рабочей группы (work crew model), оказалась весьма полезной и в качестве средства повышения производительности, и в качестве метода проектирования алгоритмов. Одним из примеров ее применения служит программа grepMT (программа 7.1), в которой для каждой файловой операции ввода/вывода и для поиска шаблона создается отдельный поток. Как показано в приложении B, в случае SMP-систем производительность повышается, поскольку планировщик может распределять выполнение потоков между различными процессорами.
Далее мы рассмотрим другой пример, в котором задача сортировки содержимого файла разбивается на ряд подзадач, выполнение которых делегируется отдельным потокам.
Решение задачи сортировки слиянием (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; /* Общее число записей. */
nRecTh = nRec / NPr; /* Количество записей на один поток. */
/* Распределить память для аргументов потока и массива дескрипторов и выделить в памяти место для файла. Считать весь файл. */
ThArg = malloc(NPr * sizeof(THREADARG));
/* Аргументы потоков. */
ThreadHandle = malloc(NPr * sizeof(HANDLE));
pRecords = malloc(FsLow + sizeof(TCHAR));
ReadFile(hFile, pRecords, FsLow, &nRead, NULL);
CloseHandle(hFile);
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] = (HANDLE)_beginthreadex (NULL, 0, ThSort, &ThArg[iTh], CREATE_SUSPENDED, &ThId);
}
for (iTh = 0; iTh < NPr; iTh++) /* Запустить все потоки сортировки. */
ResumeThread(ThreadHandle [iTh]);
WaitForSingleObject(ThreadHandle[0], INFINITE);
for (iTh = 0; iTh < NPr; iTh++) CloseHandle(ThreadHandle [iTh]);
StringEnd = (LPTSTR)pRecords + FsLow;
*StringEnd = '\0';
if (!NoPrint) printf("\n%s", (LPCTSTR)pRecords);
free(pRecords);
free(ThArg);
free(ThreadHandle);
return 0;
} /* Конец 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;
qsort(First, RecsInGrp, RECSIZE, KeyCompare);
while ((MyNumber % GrpSize) == 0 && RecsInGrp < nRec) {
/* Объединить слиянием отсортированные массивы. */
WaitForSingleObject(ThreadHandle[MyNumber + TwoToI], INFINITE);
MergeArrays(First, First + RecsInGrp);
RecsInGrp *= 2;
GrpSize *= 2;
TwoToI *= 2;
}
_endthreadex(0);
return 0; /* Подавить вывод предупреждающих сообщений. */
}
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;
}