Практическое занятие №1 . Создание многопоточных приложений в ОС Windows

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ №1. СОЗДАНИЕ МНОГОПОТОЧНЫХ ПРИЛОЖЕНИЙ В ОС WINDOWS

Цель работы

Научиться создавать простые многопоточные приложения на базе операционной системы Windows.

Порядок выполнения практических заданий

Рассмотреть представленные примеры, и разработать приложения на их основе.

Разработать алгоритм решения третьего задания, с учетом разделения вычислений между несколькими потоками. Избегать ситуаций изменения одних и тех же общих данных несколькими потоками.

Реализовать алгоритм с применением функций WinAPI и протестировать его на нескольких примерах.

Литературные источники

1. Рихтер Дж. Windows для профессионалов: создание эффективных Win32 приложений с учётом специфики 64-разрядной версии Windows/ Рихтер Дж. — СПб.:Питер, 2001. — 752с.

2. Эндрюс Г.Р. Основы многопоточного, параллельного и распределённого программирования/ Эндрюс Г.Р. — М.: «Вильямс», 2003. — 512с.

3. Хованский Е.П. “Лабораторные работы по курсу Параллельные и распределённые вычисления” /

Теоретическая часть

Во многих задачах можно выделить ряд подзадач, каждую из которых возможно решить или независимо от других подзадач, или с их минимальной кооперацией. При этом подзадачи выполняются конкурентно (в однопроцессорной системе) или параллельно в многопроцессорной системе. В многопоточной модели каждая такая подзадача существует как индивидуальный поток выполнения внутри одного и того же процесса. При этом процесс делится на две части. Одна часть содержит ресурсы, используемые через всю программу, такие как программный код и глобальные данные. Другая содержит информацию, относящуюся к состоянию выполнения, например, программный счётчик и стек. Таким образом, мы вплотную подходим к определению потока.

Кратко поток (thread, нить выполнения) можно определить как исполняемую сущность процесса.

Выделим основные причины, которые подталкивают программистов создавать многопоточные приложения:

1. Повышение надежности программы. Зацикливание основного потока приложения полностью блокирует его работу, при этом приложение может быть завершено лишь при помощи диспетчера задач (Task Manager), что, как правило, сопровождается потерей несохраненных данных. Поэтому «неблагонадежные» вычислительные фрагменты рекомендуется переносить из основного потока в отдельные дополнительные потоки, предусмотрев возможность их досрочного завершения.

2. Повышение быстродействия, экономия ресурсов и расширение функциональных возможностей программы. Многопоточность позволяет параллельно выполнять отдельные участки программы на ЭВМ с несколькими процессорами, или выполнять их на одном процессоре «псевдопараллельно», используя механизм вытесняющей многозадачности Windows. Например, различные потоки в Microsoft Word одновременно принимают пользовательский ввод, проверяют орфографию в фоновом режиме и печатают документ. Microsoft Excel строит диаграммы и выполняет математические расчеты в фоновом режиме. Сервер баз данных для ответа на каждый запрос клиента запускает отдельный поток, в противном случае пришлось бы либо запускать отдельную копию сервера, напрасно расходуя ресурсы, либо чрезвычайно усложнять логику его работы. Интерфейс прикладных программ разнообразят анимация, воспроизведение звука и т.п., выполняемые отдельными потоками.

Напомним, что при вытесняющей многозадачности потоки выполняются попеременно, время процессора выделяется потокам квантами (около 19 мс). ОС вытесняет поток, когда истечет его квант или когда на очереди поток с большим приоритетом. Приоритеты постоянно пересчитываются, чтобы избежать монополизации процессора одним потоком.

Создание потока

Создание потока в Windows происходит с помощью вызова API фукнции:

HANDLE CreateThread(PSECURITY_ATTRIBUTES psa, DWORD cbStack,

PTHREAD_START_ROUTINE pfnStartAddr, PVOID pvParam, DWORD tdwCreate, PDWORD pdwThreadID);

Вызов этой функции создает объект ядра “поток” и возвращает его дескриптор. Система выделяет память под стек нового потока из адресного пространства процесса, инициализирует структуры данных потока и передает управление потоковой функции. Новый поток выполняется в контексте того же процесса, что и родительский поток. Поэтому он имеет доступ ко всем дескрипторам процесса, адресному пространству. Поэтому все потоки могут легко взаимодействовать друг с другом.

Параметры функции CreateThread следующие:

• psa – указатель на структуру SECURITY_ATTRIBUTES. Если вы хотите, чтобы потоку были присвоены параметры защиты по умолчанию – передайте сюда NULL.
• cbStack – размер стека потока. Если параметр равен нулю – используется размер по умолчанию. Если вы передаете не нулевое значение, система выберет большее между настройками текущего исполняемого файла и вашим значением. Этот параметр резервирует только адресное пространство, а физическая память выделяется по мере необходимости.
• pfnStartAddr – это указатель на потоковую функцию. Прототип функции мы рассмотрели выше.
• pParam – произвольное значение. Этот параметр идентичен параметру потоковой функции. CreateThread передаст этот параметр в потоковую функцию. Это может быть число, либо указатель на структуру данных. Можно создавать несколько потоков с одной и той же потоковой функцией. Каждому потоку можно передавать свое значение.

Внимание, не передавайте сюда указатель на локальные переменные! Т.к. родительский поток работает одновременно с новым – локальные переменные могут выйти из области видимости и разрушиться компилятором. В то время, как новый поток будет пытаться получить к ним доступ.

• tdwCreate – дополнительные параметры создания потока. Может принимать значение 0 если надо начать выполнение потока немедленно, либо CREATE_SlJSPENDED. В последнем случае система выполняет всю инициализацию, но не запускает выполнение потока. Поток можно запустить в любой момент, вызвав WinAPI функцию ResumeThread.
• pdwThreadID – указатель на переменную, которая на выходе будет содержать идентификатор потока. Windows 2k+ позволяет передавать сюда NULL, если Вам не нужно это значение. Однако, рекомендуется всегда передавать адрес переменной для совместимости с более ранними ОС.

Завершение потока

Поток может завершиться в следующих случаях:

• Поток самоуничтожается с помощью вызова ExitThread (не рекомендуется)
• функция потока возвращает управление (рекомендуемый способ)
• один из потоков данного или стороннего процесса вызывает функцию TerminateThread (нежелательный способ)
• завершается процесс, содержащий данный поток (тоже нежелательно).

Функцию потока следует проектировать так, чтобы поток завершался только после того, как она возвращает управление. Это единственный способ, гарантирующий корректную очистку всех ресурсов, принадлежавших Вашему потоку. При этом:

• любые С++-объекты, созданные данным потоком, уничтожаются соответствующими деструкторами;
• система корректно освобождает память, которую занимал стек потока;
• система устанавливает код завершения данного потока (поддерживаемый объектом ядра "поток») — его и возвращает Ваша функция потока;
• счетчик пользователей данного объекта ядра "поток" уменьшается на 1

Вызов ExitThread выполняет аналогичные действия, за исключением первого пункта. Поэтому могут быть проблемы.

Завершение потока принудительным образом извне (TerminateThread, завершение процесса) может вызвать проблемы не только с корректным освобождением ресурсов, но и с логикой работы программы. Например, “убиенный” поток не освободит доступ к занятым ресурсам и объектам синхронизации. В результате остальная часть программы может повести себя непредсказуемым образом.

Практическая часть

Пример 1

В первом примере разработаем диалоговое многопоточное приложение.

Сначала напишем функцию, которая будет сигнализировать системным динамиком. Её будем вызывать при создании потока.

DWORD WINAPI OurFunction (PVOID pParam)

{

Beep (200, 1000); //первый параметр–частота, второй – длительность

return (0);

}

Вызов создания потока можно интегрировать в функцию нажатия кнопки или на любое другое событие по вашему выбору. Для вызова потока по кнопке достаточно в код вставить следующий фрагмент:

DWORD dwID;

CreateThread(NULL, 0, OurFunction, NULL, NULL, &dwID);

После запуска собранного приложения и нажатия на требуемую кнопку мы можем услышать характерное «пищание» системного динамика (в случае если динамик подключён и активирован).

Все способы, за исключением рекомендуемого, являются нежелательными и должны использоваться только в форс-мажорных обстоятельствах.

Функция потока, возвращая управление, гарантирует корректную очистку всех ресурсов, принадлежащих данному потоку. При этом:

- любые С++ объекты, созданные данным потоком, уничтожаются соответствующими деструкторами;

- система корректно освобождает память, которую занимал стек потока;

- система устанавливает код завершения данного потока. Его функция и возвращает;

- счетчик пользователей данного объекта ядра (поток) уменьшается на 1.

При желании немедленно завершить поток изнутри используют функцию ExitThread(DWORD dwExitCode).

При этом освобождаются все ресурсы ОС, выделенные данному потоку, но С С++ ресурсы (например, объекты классов С++) не очищаются. Именно поэтому не рекомендовано завершать поток, используя эту функцию.

Если появилась необходимость уничтожить поток снаружи, то это может сделать функция TeminateThread.

Пример 2

Дана последовательность натуральных чисел a 0, …, a 99. Создать многопоточное приложение для поиска суммы квадратов Σai Вычисления должны независимо выполнять четыре потока.

Обсуждение. Разобьем последовательность чисел на четыре части и создадим четыре потока, каждый из которых будет вычислять суммы квадратов элементов в отдельной части последовательности. Главный поток создаст дочерние потоки, соберет данные и вычислит окончательный результат, после того, как отработают четыре дочерних потока (рис. 1.1). Приложение сделаем консольным.

Рис. 1.1 Схема потоков для примера 2

#include <stdio.h>

#include <conio.h>

#include <windows.h>

const int n = 4;

int a[100];

DWORD WINAPI ThreadFunc(PVOID pvParam)

{

int num,sum = 0,i;

num = 25*(*((int *)pvParam));

for(i=num;i<num+25;i++) sum += a[i]*a[i];

*(int*)pvParam = sum;

DWORD dwResult = num;

return dwResult;

}

int main(int argc, char** argv)

{

int x[n];

int i,rez = 0;

DWORD dwThreadId[n],dw,dwResult[n];

HANDLE hThread[n];

for (i=0;i<100;i++) a[i] = i;

//создание n дочерних потоков

for (i =0; i < n; i ++)

{

x[i] = i;

hThread[i] = CreateThread(NULL,0,ThreadFunc,(PVOID)&x[i], 0, &dwThreadId[i]);

if(!hThread) printf("main process: thread %d not execute!",i);

}

// ожидание завершения n потоков

dw = WaitForMultipleObjects(n,hThread,TRUE,INFINITE);

// получение значений, переданных потоком в return

for (i=0;i<n;i++)

{

GetExitCodeThread(hThread[i],&dwResult[i]);

printf("%d\n",(int)dwResult[i]);

}

for(i=0;i<n;i++) rez+=x[i];

printf ("\ n Сумма квадратов = % d ", rez);

getch ();

return 0;

}

Варианты заданий

1. Даны последовательности символов А = {а0…аn–1} и С = {с0…ск–1}. В общем случае n ≠ k. Создать многопоточное приложение, определяющее, совпадают ли посимвольно строки А и С. Количество потоков является входным параметром программы, количество символов в строках может быть не кратно количеству потоков.

2. Дана последовательность символов С = {с0…сn–1} и символ b. Создать многопоточное приложение для определения количество вхождений символа b в строку C. Количество потоков является входным параметром программы, количество символов в строке может быть не кратно количеству потоков.

3. Дана последовательность натуральных чисел {a0…an–1}. Создать многопоточное приложение для поиска суммы Σai. Количество потоков является входным параметром программы, потоки проводят вычисления независимо друг от друга, количество символов в строке может быть не кратно количеству потоков.

4. Дана последовательность натуральных чисел {a0…an–1}. Создать многопоточное приложение для поиска произведения чисел a0*а1*…*an–1. Количество потоков является входным параметром программы, потоки проводят вычисления независимо друг от друга, количество символов в строке может быть не кратно количеству потоков.

5. Дана последовательность натуральных чисел {a0…an–1}. Создать многопоточное приложение для поиска максимального ai. Количество потоков является входным параметром программы, потоки проводят вычисления независимо друг от друга, количество символов в строке может быть не кратно количеству потоков.

6. Дана последовательность натуральных чисел {a0…an–1}. Создать многопоточное приложение для поиска минимального ai. Количество потоков является входным параметром программы, потоки проводят вычисления независимо друг от друга, количество символов в строке может быть не кратно количеству потоков.

7. Дана последовательность натуральных чисел {a0…an–1}. Создать многопоточное приложение для поиска всех ai, являющихся простыми числами. Количество потоков является входным параметром программы, потоки проводят вычисления независимо друг от друга, количество символов в строке может быть не кратно количеству потоков.

8. Дана последовательность натуральных чисел {a0…an–1}. Создать многопоточное приложение для поиска всех ai, являющихся квадратами, любого натурального числа.

9. Дана последовательность натуральных чисел {a0…an–1}. Создать многопоточное приложение для вычисления выражения a0-а1+a2-а3+a4-а5+...

10. Дана последовательность натуральных чисел {a0…an–1}. Создать многопоточное приложение для поиска суммы Σai, где ai – четные числа.

11. Изготовление знаменитого самурайского меча – катаны происходит в три этапа. Сначала младший ученик мастера выковывает заготовку будущего меча. Затем старший ученик мастера закаливает меч в трех водах – кипящей, студеной и теплой. И в конце мастер собственноручно изготавливает рукоять меча и наносит узоры. Требуется создать многопоточное приложение, в котором мастер и его ученики представлены разными потоками. Изготовление меча представить в виде разных арифметических операций над глобальной переменной.

12. Командиру N-ской ВЧ полковнику Кузнецову требуется перемножить два секретных числа. Полковник Кузнецов вызывает дежурного по части лейтенанта Смирнова и требует в течение получаса предоставить ему ответ. Лейтенант Смирнов будит старшего по караулу сержанта Петрова и приказывает ему в 15 минут предоставить ответ. Сержант Петров вызывает к себе рядового Иванова, бывшего студента, и поручает ему ответственное задание по определению произведения. Рядовой Иванов успешно справляется с поставленной задачей и ответ по цепочке передается полковнику Кузнецову. Требуется создать многопоточное приложение, в котором все военнослужащие от полковника до рядового моделируются потоками одного вида.

13. Даны результаты сдачи экзамена по курсу «Параллельные и распределённые вычисления» по группам. Требуется создать многопоточное приложение, вычисляющее средний балл. Потоки должны осуществлять вычисления параллельно по группам. Количество потоков является входным параметром программы, потоки проводят вычисления независимо друг от друга, количество групп может быть не кратно количеству потоков.

14. Охранное агентство разработало новую систему управления электронными замками. Для открытия двери клиент обязан произнести произвольную фразу из 25 слов. В этой фразе должно встречаться заранее оговоренное слово, причем только один раз. Требуется создать многопоточное приложение, управляющее замком. Потоки должны осуществлять сравнение параллельно по словам.

15. Среди студентов нашего университета проведен опрос с целью определения процента студентов, знающих точную формулировку правила Буравчика. В результате собраны данные о количестве знатоков на каждом направлении по группам. Известно, что всего в филиале обучается 500 студентов. Требуется создать многопоточное приложение для определения процента знающих правило Буравчика студентов. Потоки должны осуществлять поиск количества знатоков по факультету. Искомый процент определяет главный поток. Количество потоков является входным параметром программы, потоки проводят вычисления независимо друг от друга, количество направлений может быть не кратно количеству потоков.

16. Руководство заготовительной компании «Рога и Копыта» проводит соревнование по заготовке рогов среди своих региональных отделений. Все данные по результатам заготовки рогов (заготовитель, его результат) хранятся в общей базе данных по отделениям. Требуется создать многопоточное приложение для поиска лучшего заготовителя. Потоки должны осуществлять поиск победителя параллельно по отделениям. Главный поток определит победителя. Количество потоков является входным параметром программы, потоки проводят вычисления независимо друг от друга, количество отделений может быть не кратно количеству потоков.

 

Цель работы

Изучить работу с критическими секциями. Научиться выделять «проблемные» фрагменты алгоритма и защищать их с помощью критических секций.

Литературные источники

1. Рихтер Дж. Windows для профессионалов: создание эффективных Win32 приложений с учётом специфики 64-разрядной версии Windows/ Рихтер Дж. — СПб.:Питер, 2001. — 752с.

2. Эндрюс Г.Р. Основы многопоточного, параллельного и распределённого программирования/ Эндрюс Г.Р. — М.: «Вильямс», 2003. — 512с.

3. Хованский Е.П. “Лабораторные работы по курсу Параллельные и распределённые вычисления” /

4.Гергель В.П. Теория и практика параллельных вычислений /Гергель В.П. — М.: ИНТУИР.РУ Интернет-Университет Информационных Технологий, 2007.

Теоретическая часть

Критические секции

Критическая секция (critical section) (рис.2.1) — это небольшой участок кода, требующий монопольного доступа к каким-то общим данным. Она позволяет сделать так, чтобы единовременно только один поток получал доступ к определенному ресурсу. Естественно, система может в любой момент вытеснить Ваш поток и подключить к процессору другой, но ни один из потоков, которым нужен занятый Вами ресурс, не получит процессорное время до тех пор, пока Ваш поток не выйдет за границы критической секции.

Ниже приведён фрагмент кода, который демонстрирует, что может произойти без критической секции:

const int MAX_TIMES = 1000,

int g_nIndex - 0,

DWORD g_dwTimes[MAX_TIMES];

DWORD WINAPI FirstThread(PVOID pvParam)

{

while (g_nIndex < MAX_TIMES)
{

g_dwTimes[g__nIndex] = GetTickCount();
g_nIndex++;

}

return(0),
}

DWORD WINAPI SecondThread(PVOID pvParam)
{

while Cg_nIndex < MAX_TIMES)
{

g_nIndex++;

g_dwTimes[g_nIndex - 1] = GetTickCount();
}

return (0);
}

Здесь предполагается, что функции обоих потоков дают одинаковый результат, хоть они и закодированы с небольшими различиями. Если бы исполнялась только функция FirstThread, она заполнила бы массив g _ dwTimes набором чисел с возрастающими значениями. Это верно и в отношении SecondThread - если бы она тоже исполнялась независимо. В идеале обе функции даже при одновременном выполнении должны бы по-прежнему заполнять массив тем же набором чисел. Но в нашем коде возникает проблема: масив g _ dwTimes не будет заполнен, как надо, потому что функции обоих потоков одновременно обращаются к одним и тем же глобальным переменным. Вот как это может произойти.

Допустим, мы только что начали исполнение обоих потоков в системе с одним процессором. Первым включился в работу второй поток, т.e. функция SecondThread (что вполне вероятно), и только она успела увеличить счетчик g _ nIndex 1, как система вытеснила ее поток и перешла к исполнению FtrstThread Та заносит в g _ dwTimes [1] показания системного времени, и процессор вновь переключается на исполнение второго потока. SecondThread теперь присваивает элементу g _ dwTtmes [1 - 1] новые показания системного времени. Поскольку эта операция выполняется позже, новые показания, естественно, выше, чем записанные в элемент g _ dwTimes [1]ф y нк цией FirstThread. Отметьте также, что сначала заполняется первый элемент массива и только потом нулевой. Таким образом, данные в массиве оказываются ошибочными.

Пример приведённый выше в значительной степени надуман, но прост. Рассмотрим пример с управлением связанным списком объектов. Если доступ к связанному списку не синхронизирован, один поток может добавить элемент в список в тот момент, когда другой поток пытается найти в нём какой-то элемент. Ситуация станет еще более угрожающей, если оба потока одновременно добавят в список новые элементы. Так что, используя критические секции, можно и нужно координировать доступ потоков к структурам данных.

Важно отметить, что критические секции – это механизм для синхронизации потоков внутри одного процесса. Для работы с критическими секциями есть ряд функций API и тип данных CRITICAL _ SECTION.

Для использования критической секции нужно создать переменную данного типа, и проинициализировать ее перед использованием с помощью функции InitializeCriticalSection ().

CRITICAL_SECTION g_cs;

InitializeCriticalSection(&g_cs);

Для того, чтобы войти в секцию нужно вызвать функцию EnterCriticalSection(), а после завершения работы LeaveCriticalSection().

EnterCriticalSection(&g_cs);

LeaveCriticalSection (&g_cs);

Что будет, если поток обратится к секции, в которой сейчас другой поток? Тот поток, который обратится будет блокирован пока критическая секция не будет освобождена. Саму критическую секцию можно удалить функцией DeleteCriticalSection ().

DeleteCriticalSection (& g _ cs);

Для того, чтобы обойти блокировку потока при обращении к занятой секции есть функция TryEnterCriticalSection (), которая позволяет проверить критическую секцию на занятость.

Практическая часть

Пример 1

Рассмотрим использование критических секций и полезность такого решения. Для начала посмотрим, что случится, если мы попробуем обратиться к одному ресурсу двумя потоками. Создадим два потока, которые одновременно захотят “пищать” системным динамиком. Сначала нарисуем две функции, которые будут выполняться потоками, а потом и сами потоки.

DWORD WINAPI firstFunc(LPVOID lpParam)

{

Beep(100, 500);

return (0);

}

DWORD WINAPI secondFunc(LPVOID lpParam)

{

Beep (400, 500);

return (0);

}

Вызовы CreateThread можно интегрировать, например, в функцию нажатия на кнопку.

DWORD dwFirst;

HANDLE firstThread = CreateThread(NULL, 0, firstFunc, NULL, NULL, dwFirst);

DWORD dwSecond;

HANDLE secondThread = CreateThread(NULL, 0, secondFunc, NULL, NULL, dwSecond);

/* Когда описатели нам больше не требуются, удалим их */

CloseHandle(firstThread);

CloseHandle(secondThread);

Как вы думаете, что произойдёт? Правильно, ничего того, что мы ожидали. Потоки будут драться и т.к. приоритеты у них одинаковы, то “пищать” будет только один – какой, не известно, но с большей вероятностью первый вызванный. Можете сами прослушать.

Разрешить данную ситуацию можно с помощью критической секции. Обычно структуры CRITICAL_SECTION создаются как глобальные переменные, доступные всем потокам процесса. Однако вы можете сузить область видимости данной структуры, исходя из специфики задач. Главное, чтобы структура CRITICAL_SECTION была в области видимости тех потоков, которые будут обращаться к разделяемому ресурсу. Следует выполнять два условия. Во-первых, все потоки, которым может понадобиться данный ресурс, должны знать адрес структуры CRITICAL_SECTION, которая защищает этот ресурс. Во-вторых, элементы структуры CRITICAL_SECTION следует инициализировать до обращения какого-либо потока к защищённому ресурсу.

CRITICAL _ SECTION csOurSection; // это объявление структуры Критическая секция

Помня про условия использования критической секции, мы её инициализируем. Эту операцию провернём в функции OnInitDialog. Не забываем, что критическую секцию следует инициализировать до какого-либо к ней обращения.

InitializeCriticalSection (& csOurSection);

Теперь перепишем наши функции, учитывая наличие критической секции.

DWORD WINAPI firstFunc(LPVOID lpParam)

{

EnterCriticalSection(&csOurSection);

Beep(100, 500);

LeaveCriticalSection(&csOurSection);

return (0);

}

DWORD WINAPI SecondFunc(LPVOID lpParam)

{

EnterCriticalSection(&csOurSection);

Beep(400, 500);

LeaveCriticalSection(&csOurSection);

return (0);

}

Вызовы создания потоков, естественно, такие же.

Когда мы понимаем, что критическая секция нам больше не нужна, мы должны её удалить. Сделать это можно, например, в функции OnClose. (Создать её можно с помощью MFC Class Wizard, по сообщению WM_CLOSE нашего диалогового окна.). Для этого надо сделать вызов:

DeleteCriticalSection (& csOurSection);

Теперь первым выполняется поток, который первым вошёл в критическую секцию. Второй ждёт, а затем и сам выполняется. Сигнализируют потоки по очереди.

Пример 2

Задача о кольцевом буфере. Потоки производители и потребители разде­ляют кольцевой буфер, состоящий из 100 ячеек. Производители передают со­общение потребителям, помещая его в конец очереди буфера. Потребители сообщение извлекают из начала очереди буфера. Создать многопоточное приложение с потоками писателями и читателями. Предотвратить такие си­туации как, изъятие сообщения из пустой очереди или помещение сообщения в полный буфер. При решении задачи использовать критические секции.

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

Для защиты обоих проблемных участков воспользуемся критической секцией. Она сделает возмож­ным запись в буфер только одного потока-писателя. И она же сделает возможным чтение из буфера только одного потока-читателя. Операция чтения должна быть защищена, потому что она является и операцией записи тоже, так как поток, прочитавший ячейку буфера, обязан ее как-то пометить. Иначе, через определенное время выполнения программы, операция записи может стать невозможной или некорректной, в силу того, что буфер конечен. Операции чтения и записи могут проходить параллельно, так как всегда происходят в разных ячейках.

За условную синхронизацию будет отвечать та же самая критическая секция. Также, должна присутствовать переменная, отображающая, сколько ячеек в буфере свободно. Ячей­ка свободна, когда в нее еще не осуществлялась запись или ячейка была про­читана. Вторая переменная должна показывать, сколько ячеек в буфере заня­то. Естественно, операция записи не может быть выполнена, пока количество занятых ячеек равно 100 (или количество свободных ячеек равно 0), и операция чтения не может быть выполнена, пока количество свободных ячеек рав­но 100 (или количество занятых ячеек равно 0).

#include <stdio.h>

#include <stdlib.h>

#include <conio.h>

#include <windows.h>

const int n = 100, // блина буфера

m = 7, // количество производителей

k = 3; // количество потребителей

int buf [ n ], front = 0, rear = 0;//кольцевой буфер его голова и хвост

CRITICAL_SECTION ArraySection;//секция на доступ к буферу

//процесс, пополняющий буфер

DWORD WINAPI Producer(PVOID pvParam)

{

int num;

num = *((int *)pvParam);

printf("thread %d (producer): start!\n",num);

while(true)

{

EnterCriticalSection(&ArraySection);

buf[rear] = rand()%n;

printf("\nproducer %d: data = %d to %d", num, buf[rear], rear);

rear = (rear+1)%n;

LeaveCriticalSection(&ArraySection);

Sleep (1000);

}

return 0;

}

//процесс, берущий данные из буфера

DWORD WINAPI Consumer(PVOID pvParam)

{

int num=0;

int data=0;

long prev=0;

num = *((int *)pvParam);

printf("thread %d (consumer): start!\n",num);

while(true)

{

EnterCriticalSection(&ArraySection);

data = buf[front];

printf("\nconsumer %d: data = %d from %d", num, data, front);

front = (front+1)%n;

LeaveCriticalSection(&ArraySection);

Sleep(1000);

}

return 0;

}

int main(int argc, char* argv)

{

int i, x[k+m];

DWORD dwThreadId[k+m];

HANDLE hThread[k+m];

InitializeCriticalSection(&ArraySection);

for(i=0;i<k;i++)

{

x[i] = i;

hThread[i] = CreateThread(NULL,0,Producer,(PVOID)&x[i], 0, &dwThreadId[i]);

if(!hThread) printf("main process: thread %d not execute!", i);

}

for(i=k;i<k+m;i++)

{

x[i] = i;

hThread[i] = CreateThread(NULL,0,Consumer,(PVOID)&x[i], 0, &dwThreadId[i]);

if(!hThread) printf("main process: thread %d not execute!", i);

}

WaitForMultipleObjects(k+m,hThread,TRUE,INFINITE);

// закрытие критической секции

DeleteCriticalSection(&ArraySection);

return 0;

}

Варианты заданий

1. Задача о napикмахере. В тихом городке есть парикмахерская. Салон парикмахерской мал ходить там может только парикмахер и один посети­тель. Парикмахер всю жизнь обслуживает посетителей. Когда в салоне нико­го нет, он спит в кресле. Когда посетитель приходит и видит спящего парик­махера, он будет его, садится в кресло и спит, пока парикмахер занят стриж­кой. Если посетитель приходит, а парикмахер занят, то он встает в очередь и засыпает. После стрижки парикмахер сам провожает посетителя. Если есть ожидающие посетители, то парикмахер будит одного из них, и ждет пока тот сядет в кресло парикмахера и начинает стрижку. Если никого нет, он снова садится в свое кресло и засыпает до прихода посетителя. Создать многопо­точное приложение, моделирующее рабочий день парикмахерской. Услов­ную синхронизацию потоков выполнить с помощью критических секций или событий.

2. Задача о Винни-Пухе или правильные пчелы. В одном лесу живут n пчел и один медведь, которые используют один горшок меда, вместимостью Н глотков. Сначала горшок пустой. Пока горшок не наполнится, медведь спит. Как только горшок заполняется, медведь просыпается и съедает весь мед, после чего снова засыпает. Каждая пчела многократно собирает по од­ному глотку меда и кладет его в горшок. Пчела, которая приносит послед­нюю порцию меда, будит медведя. Создать многопоточное приложение, моделирующее поведение пчел и медведя. Условную синхронизацию потоков выполнить с помощью критических секций.

3. Задача о читателях и писателях. Базу данных разделяют два типа процессов - читатели и писатели. Читатели выполняют транзакции, которые просматривают записи базы данных, транзакции писателей и просматривают и изменяют записи. Предполагается, что в начале БД находится в непротиво­речивом состоянии (т.е. отношения между данными имеют смысл). Каждая отдельная транзакция переводит БД из одного непротиворечивого состояния в другое. Для предотвращения взаимного влияния транзакций процесс-писатель должен иметь исключительный доступ к БД. Если к БД не обраща­ется ни один из процессов-писателей, то выполнять транзакции могут одно­временно сколько угодно читателей. Создать многопоточное приложение с потоками-писателями и потоками-читателями. Реализовать решение, исполь­зуя критические секции.

4. Задача об обедающих философах. Пять философов сидят возле круг­лого стола. Они проводят жизнь, чередуя приемы пищи и размышления. В центре стола находится большое блюдо спагетти. Спагетти длинные и запу­танные, философам тяжело управляться с ними, поэтому каждый из них. чтобы сьесть порцию, должен пользоваться двумя вилками. К несчастью, философам дали только пять вилок. Между каждой парой философов лежит одна вилка, поэтому эти высококультурные и предельно вежливые люди догово­рились, что каждый будет пользоваться только теми вилками, которые лежат рядом с ним (слева и справа). Написать многопоточную программу, модели­рующую поведение философов с помощью критических секций. Программа должна избегать фатальной ситуации, в которой все философы голодны, но ни один из них не может взять обе вилки (например, каждый из философов держит по одной вилки н не хочет отдавать ее). Решение должно быть симметричным, то есть все потоки-философы должны выполнять один и тот же код.

5. Задача о каннибалах. Племя из п дикарей ест вместе из большого горшка, который вмешает т кусков тушеного миссионера. Когда дикарь хо­чет обедать, он ест из горшка один кусок, если только горшок не пуст, иначе дикарь будит повара и ждет, пока тот не наполнит горшок. Повар, сварив обед, засыпает. Создать многопоточное приложение, моделирующее обед дикарей. При решении задачи пользоваться критическими секциями.

6. Задача о курильщиках. Есть три процесса-курильщика и один про­цесс-посредник. Курильщик непрерывно скручивает сигареты и курит их. Чтобы скрутить сигарету, нужны табак, бумага и спички. У одного процесса-курильщика есть табак, у второго - бумага, а у третьего - спички. Посредник кладет на стол по два разных случайных компонента. Тот процесс-курильщик, у которого есть третий компонент, забирает компоненты со сто­ла, скручивает сигарету и курит. Посредник дожидается, пока курильщик за­кончит, затем процесс повторяется. Создать многопоточное приложение, моделируюшее поведение курильщиков и посредника. При решении задачи использовать критические секции.

7. Задача о картинной галерее. Вахтер следит за тем, чтобы в картинной галерее было не более 50 посетителей. Для обозрения представлены 5 картин. Посетитель ходит от картины к картине. Посетитель может покинуть гале­рею. Создать многопоточное приложение, моделирую шее работу картинной галереи.

8. Задача о Винни-Пухе - 2 пли неправильные пчелы. N пчел живет в улье, каждая пчела может собирать мед и сторожить улей (N>3). Ни одна пчела не покинет улей, если кроме нее в нем нет других пчел. Каждая пчела приносит за раз одну порцию меда. Всего в улей может войти тридцать порций меда. Винни-Пух спит пока меда в улье меньше половины, но как только его становится достаточно, он просыпается и пытается достать весь мед из улья. Если в улье находится менее чем три пчелы, Винни-Пух забирает мед убегает, съедает мед и снова засыпает. Если в улье пчел больше, они кусают Винни-Пуха, он убегает, лечит укус, и снова бежит за медом. Создать много­поточное приложение, моделирующее поведение пчел и медведя.

9. Задача о нелюдимых садовниках. Имеется пустой участок земли (двумерный массив) и план сада, который необходимо реализовать. Эту зада­чу выполняют два садовника, которые не хотят встречаться друг с другом. Первый садовник начинает работу с верхнего левого угла сада и перемешает­ся слева направо, сделав ряд, он спускается вниз. Второй садовник начинает работу с нижнего правого угла сада и перемещается снизу вверх, сделав ряд, он перемещается влево. Если садовник видит, что участок сада уже выполнен другим садовником, он идет дальше. Садовники должны работать параллель­но. Создать многопоточное приложение, моделирую шее работу садовников. При решении задачи использовать критические секции.

10. Задача о супермаркете. В супермаркете работают два кассира, по­купатели заходят в супермаркет, делают покупки и становятся в очередь к случайному кассиру. Пока очередь пуста, кассир спит, как только появляется покупатель, кассир просыпается. Покупатель спит в очереди, пока не подой­дет к кассиру. Создать многопоточное приложение, моделирующее рабочий день супермаркета.

11. Задача о магазине. В магазине работают три отдела, каждый отдел обслуживает один продавец. Покупатель, зайдя в магазин, делает покупки в произвольных отделах, и если в выбранном отделе продавец не свободен, покупатель становится в очередь и засыпает, пока продавец не освободится. Создать многопоточное приложение, моделирующее рабочий день магазина.

12. Задача о больнице. В больнице два врача принимают пациентов, выслушивают их жалобы и отп<