Практическое занятие №2. Синхронизация потоков в ОС Windows

Цель работы

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

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

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

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

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

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

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. Задача о больнице. В больнице два врача принимают пациентов, выслушивают их жалобы и отправляют их или к стоматологу или к хирургу или к терапевту. Стоматолог, хирург и терапевт лечат пациента. Каждый врач может принять только одного пациента за раз. Пациенты стоят в очере­ди к врачам и никогда их не покидают. Создать многопоточное приложение, моделирующее рабочий день клиники.

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

14. Задача о гостинице-2 (умные клиенты). В гостинице 10 номеров с ценой 200 рублей, 10 номеров с ценой 400 рублей и 5 номеров с ценой 600 руб. Клиент, зашедший в гостиницу, обладает некоторой суммой и получает номер по своим финансовым возможностям, если тот свободен. Если среди доступных клиенту номеров нет свободных, клиент уходит искать ночлег в другое место. Создать многопоточное приложение, моделирующее работу гостиницы.

15. Задача о клумбе. На клумбе растет 40 цветов, за ними непрерывно следят два садовника и поливают увядшие цветы, при этом оба садовника очень боятся полить одни и тот же цветок. Создать многопоточное приложе­ние, моделирующее состояния клумбы и действия садовников. Для измене­ния состояния цветов создать отдельный поток.