лаборотоная 3. Лаб_3. Лабораторная работа Синхронизация потоков в Win32 api

Название	Лабораторная работа Синхронизация потоков в Win32 api
Анкор	лаборотоная 3
Дата	27.02.2021
Размер	110.5 Kb.
Формат файла
Имя файла	Лаб_3.doc
Тип	Лабораторная работа #180081

Лабораторная работа № 3. Синхронизация потоков в Win32 API

Цель работы

Изучение основных механизмов синхронизации потоков, реализованных в операционных системах семейства Windows.
Получение навыков по реализации синхронизации потоков при разработке приложений Windows.
Овладение методами обнаружения взаимоблокировок.

Краткие теоретические сведения

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

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

Для синхронизации потоков системы, базирующиеся на Win32, предлагают несколько синхронизирующих объектов, основными из которых являются: критические секции (critical section), взаимные исключения (mutex – сокращение от mutual exclusion), семафоры и события. Все они кроме критических секций являются объектами ядра. Кроме того, в качестве синхронизирующих объектов могут использоваться процессы, потоки, файлы, консольный ввод, уведомления об изменении файлов.

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

Взаимное исключение (mutex) – это объект ядра операционной системы, который позволяет только одному потоку в данное время владеть им.

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

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

К основным функциям Win32 API по управлению синхронизацией относятся:

void InitializeCriticalSection(LPCRITICAL_SECTION lpCriticalSection) – инициализировать критическую секцию; в функцию необходимо передать адрес структуры CRITICAL_SECTION.

void DeleteCriticalSection(LPCRITICAL_SECTION lpCriticalSection) – освободить все ресурсы, включенные в критическую секцию (удалить критическую секцию); в функцию необходимо передать адрес структуры CRITICAL_SECTION.

void EnterCriticalSection(LPCRITICAL_SECTION lpCriticalSection) – захватить блокировку для критической секции; в функцию необходимо передать адрес переменной-структуры CRITICAL_SECTION.

void LeaveCriticalSection(LPCRITICAL_SECTION lpCriticalSection) – освободить блокировку для критической секции; в функцию необходимо передать адрес переменной-структуры CRITICAL_SECTION.

HANDLE CreateMutex(LPSECURITY_ATTRIBUTES lpsa, BOOL fInitialOwner, LPTSTR lpszMutexName) – создать новый мьютекс; возвращает описатель, идентифицирующий новый объект mutex. Параметр lpsa указывает на структуру SECURITY_ATTRIBUTES (можно передать NULL). Параметр fInitialOwner определяет: должен ли поток, создающий mutex, быть первоначальным владельцем этого объекта. Если он равен TRUE, данный поток становится его владельцем, и, следовательно, объект mutex оказывается в занятом состоянии. Передача FALSE в параметре fInitialOwner подразумевает, что объект mutex не принадлежит ни одному из потоков и поэтому “рождается свободным”. Параметр lpszMutexName содержит либо NULL, либо адрес нуль терминированной строки, содержащей имя мьютекса, используемое для получения его описателя из других процессов.

HANDLE OpenMutex(DWORD fdwAccess, BOOL fInherit, LPTSTR lpszName) – открыть существующий мьютекс; возвращает описатель объекта mutex по его имени. Параметр fdwAccess может быть равен либо SYNCHRONIZE либо MUTEX_ALL_ACCESS. Параметр fInherit определяет: должен ли любой порожденный процесс наследовать данный описатель данного объекта mutex. Параметр lpszName – это имя объекта mutex в виде строки с нулевым символом на конце.

BOOL ReleaseMutex(HANDLE hMutex) –освободить мьютекс, чтобы другой поток мог его захватить; функции необходимо передать описатель объекта mutex. При успешном завершении возвращает ненулевое значение (TRUE), при ошибке – 0 (FALSE).

HANDLE CreateSemaphore(LPSECURITY_ATTRIBUTES lpsa, LONG cSemInitial, LONG cSemMax, LPTSTR lpszSemName)– создать новый семафор; возвращает дескриптор вновь созданного семафора. Параметр lpsa указывает на структуру SECURITY_ATTRIBUTES (можно передать NULL). Параметр cSemInitial устанавливает начальное значение счетчика. Параметр cSemMax устанавливает максимальное значение счетчика. Параметр lpszSemName содержит либо NULL, либо адрес нуль терминированной строки, содержащей имя семафора, используемое для получения его описателя из других процессов.

HANDLE OpenSemaphore(DWORD fdwAccess, BOOL fInherit, LPTSTR lpszName) – открыть существующий семафор; возвращает описатель объекта семафор по его имени. Параметр fdwAccess может быть равен либо SYNCHRONIZE (в Windows NT) либо SEMAPHORE_ALL_ACCESS, либо SEMAPHORE_MODIFY_STATE. Параметр fInherit определяет: должен ли любой порожденный процесс наследовать данный описатель данного объекта семафор. Параметр lpszName – это имя объекта семафор в виде строки с нулевым символом на конце. Используется для получения описателя семафора по его имени из другого процесса, создавшего его.

BOOL ReleaseSemaphore(HANDLE hSemaphore, LONG cRelease, LPLONG lplPrevious) – увеличить счетчик семафора на величину, указанную в параметре cRelease, чтобы другой поток мог его захватить. В параметр hSemaphore передается описатель семафора. Параметр lplPrevious – указатель на переменную типа long, куда заносится значение счетчика ресурсов, предшествующее тому, что получится после увеличения его на cRelease. Если это значение не нужно, то в параметр можно передать NULL. При успешном завершении возвращает ненулевое значение (TRUE), при ошибке – 0 (FALSE).

HANDLE CreateEvent(LPSECURITY_ATTRIBUTES lpsa, BOOL fManualReset, BOOL fInitialState, LPTSTR lpszEventName) – создать новое событие; возвращает процессно-зависимый описатель события. Параметр lpsa указывает на структуру SECURITY_ATTRIBUTES (можно передать NULL). Параметр fManualReset определяет: создавать ли событие с ручным сбросом (TRUE) или с автоматическим сбросом (FALSE). Параметр fInitialState указывает начальное состояние события: свободное (TRUE) или занятое (FALSE). Параметр lpszEventName содержит либо NULL, либо адрес нуль терминированной строки, содержащей имя события, используемое для получения его описателя из других процессов.

HANDLE OpenEvent(DWORD fdwAccess, BOOL fInherit, LPTSTR lpszName) – получить доступ к событию; возвращает описатель объекта событие по его имени. Параметр fdwAccess может быть равен либо SYNCHRONIZE (в Windows NT) либо EVENT_ALL_ACCESS, либо EVENTE_MODIFY_STATE. Параметр fInherit определяет: должен ли любой порожденный процесс наследовать данный описатель данного объекта событие. Параметр lpszName – это имя объекта событие в виде строки с нулевым символом на конце. Используется для получения описателя события по его имени из другого процесса, создавшего его. Получить описатель события из другого процесса можно также вызовом функции CreateEvent, передав в него тоже имя семафора, что и при создании в другом процессе.

BOOL SetEvent(HANDLE hEvent) – перевести событие в свободное состояние. Функция принимает в качестве аргумента описатель события и возвращает TRUE в случае успешного завершения.

BOOL ResetEvent(HANDLE hEvent) – перевести событие в занятое состояние. Функция принимает в качестве аргумента описатель события и возвращает TRUE в случае успешного завершения.

BOOL PulseEvent(HANDLE hEvent) – перевести событие в сигнализирующее (свободное) состояние, а затем вернуть в несигнализирующее (занятое) . Функция принимает в качестве аргумента описатель события и возвращает TRUE в случае успешного завершения.

Для закрытия объектов мьютекс, семафор, событие используется функция CloseHandle, в которую в качестве аргумента необходимо передать дескриптор закрываемого объекта.

DWORD WaitForSingleObject(HANDLE hObject, DWORD dwTimeout) – блокироваться на одном объекте (семафоре, мьютексе и т.д.). Возвращаемые значения: WAIT_OBJECT_0 – объект перешел в состояние свободного; WAIT_TIMEOUT – объект не перешел в состояние свободного за указанный в dwTimeout период времени; WAIT_ABANDONED – объект mutex стал свободен из-за отказа от него (когда поток занял его и завершился); WAIT_FAILED – произошла ошибка, для получения развернутой информации об ошибке нужно вызвать (сразу же) функцию GetLastError. Параметр hObject указывает на описатель объекта ядра, освобождение которого ожидает поток. Параметр dwTimeout определяет, сколько времени (в миллисекундах) поток готов ждать освобождение объекта. В параметре dwTimeout можно передать два особых значения: 0 – означает, что нужно не ждать, а выяснить, занят объект или нет (если функция возвратит WAIT_OBJECT_0, то объект свободен, а если возвратит WAIT_TIMEOUT, то объект – занят); INFINITE – означает, что нужно пока объект не освободится столько времени, сколько придется.

DWORD WaitForMultipleObject(DWORD cObjects, LPHANDLE lpHandles, BOOL bWaitAll, DWORD dwTimeout) – блокироваться на множестве объектов, чьи дескрипторы перечисляются. В параметре cObjects передается количество объектов, освобождение которых ждет поток (не должно превышать MAXIMUM_WAIT_OBJECTS). Параметр lpHandles – указатель на массив описателей, идентифицирующих эти объекты. Параметр bWaitAll определяет: поток ждет освобождения всех объектов (TRUE) или лишь одного объекта (FALSE). Параметр dwTimeout определяет, сколько времени (в миллисекундах) поток готов ждать освобождение объекта. Если освобождается сразу несколько объектов, функция возвращает индекс описателя в массиве, идентифицирующего первый освобожденный объект. Функция возвращает одно из следующих значений: от WAIT_OBJECT_0 до (WAIT_OBJECT_0+cObject-1) – при ожидании всех объектов это значение указывает на то, что ожидание закончилось успешно; при ожидании одного из объектов это значение представляет собой индекс того описателя в массиве lpHandles, что принадлежит освобожденному объекту; WAIT_TIMEOUT – объект или объекты не освободились за указанный в dwTimeout период времени; от WAIT_ABANDONED_0 до (WAIT_ ABANDONED_0+cObject-1) – при ожидании всех объектов это значение указывает на то, что ожидание закончилось успешно и что по крайней мере один объект был объектом mutex, который освобожден из-за отказа от него; при ожидании одного из объектов это значение представляет собой индекс того описателя в массиве lpHandles, что принадлежит объекту mutex, освобожденному по причине от него; WAIT_FAILED – произошла ошибка, для получения развернутой информации об ошибке нужно вызвать (сразу же) функцию GetLastError.

Осуществление синхронизации потоков создает дополнительные проблемы. Одна из них взаимоблокировки (тупики). Взаимная блокировка – это состояние, когда каждый из двух потоков ждет освобождения ресурса, заблокированного другим потоком.

Пусть имеется множество процессов P={P₁, P₂, …, P_n}, всего n процессов и множество ресурсов E={E₁, E₂, …, E_m}, где m – число классов ресурсов. В любой момент времени некоторые из ресурсов могут быть заняты и, соответственно, недоступны. Пусть A – вектор доступных ресурсов A={A₁, A₂, …, A_m}. Очевидно, что A_j≤E_j, j=1, 2, …, m.

Введем в рассмотрение две матрицы:

C={c_ij| i=1, 2,…,n; j=1, 2,…,m} – матрица текущего распределения ресурсов, где c_ij – количество ресурсов j-го класса, которые занимает процесс P_i;

R={r_ij| i=1, 2,…,n; j=1,2,…,m} – матрица требуемых (запрашиваемых) ресурсов, где r_ij – количество ресурсов j-го класса, которые хочет получить процесс P_i.

Справедливо m соотношений по ресурсам:

, j=1, 2, …, m.

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

Ищется процесс P_i, для которого i-я строка матрицы R меньше вектора A, то есть R_i ≤ A, или r_ji ≤ A_j, j =1, 2, …, m.

Если такой процесс найден, это означает, что он может завершиться, а, следовательно, освободить занятые ресурсы. Найденный процесс маркируется, и далее прибавляется i-я строка матрицы C к вектору A, то есть A_j= A_j+c_ij, j=1,2,…,m. Возвращаемся к первому шагу.

Если таких процессов не существует, работа алгоритма заканчивается. Немаркированные процессы попадают в тупик.

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОГО ВЫПОЛНЕНИЯ

Задание 1.

В среде Visual C++6.0 создайте проект CrtSec – приложение, имитирующее изъятие шаров из корзины тремя потоками. Первоначальное их количество хранится в глобальной переменной (задайте 1000). Каждый поток декрементирует эту переменную на единицу пока она не примет значение 0 (изъяты все шары). Одновременно каждый поток инкрементирует на единицу переменную, в которой хранится количество шаров, изъятых этим потоком. Для синхронизации потоков используйте критическую секцию. После изъятия потоками всех шаров из урны на экране должно отобразиться количество шаров, изъятых каждым из потоков. Проварьируйте величины задержек каждого из потоков и сравните результаты работы программы.

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

Задание 2.

В среде Visual C++6.0 создайте проект Mutex. Выполните предыдущее задание, используя для синхронизации потоков вместо критической секции мьютекс.

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

Задание 3.

В среде Visual C++6.0 создайте проект Semaphores – приложение, в котором три потока записывают случайные числа (по 4 за раз) в один и тот же буфер данных (для задания буфера используйте массив) с указанием номера (1, 2, 3) записавшего потока. Два других потока считывают данные из этого буфера и рисуют, соответственно, прямоугольники и эллипсы со считанными параметрами расположения и размера каждый в свою четверть окна приложения. Цвет закраски фигуры – синий, если размер записан потоком-писателем с номером 1, красный – с номером 2 и зеленый – с номером 3. Для синхронизации потоков используйте семафоры. Проварьируйте величины задержек каждого из потоков и сравните результаты работы программы.

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

Задание 4.

В среде Visual C++6.0 создайте проект EventAuto – приложение с одним рабочим потоком. Этот поток рисует 1000 случайных закрашенных прямоугольников (эта процедура повторяется в цикле). Поток создается в обработчике сообщения WM_CREATE и завершается в обработчике сообщения WM_DESTROY. Запуск процедуры рисования потоком должен осуществляться нажатием кнопки. Синхронизацию рабочего потока организуйте с первичным потоком с помощью события с автоматическим сбросом. В рабочем потоке необходимо осуществить лишь генерацию параметров рисуемых фигур. Процедура рисования должна выполняться в первичном потоке. Информирование первичного потока рабочим потоком о завершении генерации параметров очередного прямоугольника должно выполняться посредством пользовательского сообщения, обработчик которого в первичном потоке должен рисовать прямоугольники.

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

Задание 5.

В среде Visual C++6.0 создайте проект EventManual – приложение с тремя рабочими потоками. Первый поток имитирует чтение из файла в буфер – генерирует случайные числа в диапазоне [0; 1] и записывает их в массив размера 1000. Второй и третий потоки считывают данные из этого массива. Второй поток подсчитывает число элементов в массиве, лежащих в интервале [0; 0,3], а третий поток подсчитывает число элементов, лежащих в интервале [0,7; 1]. Эти данные выводятся в окно приложения первичным потоком. Первый поток, закончив заполнение буфера, информирует об этом остальные потоки. По окончании ими своей работы первый поток вновь заполняет буфер случайными числами и вновь информирует об этом остальные потоки и т.д. Синхронизацию потоков организовать с помощью события с ручным сбросом.

Сравните Ваше решение с имеющимся вариантом выполнения. Видоизмените приложение следующим образом. Добавьте четвертый читающий поток. Второй поток должен подсчитывать число элементов в массиве, лежащих в интервале [0; 0,2], третий поток – в интервале [0,4; 0, 6], четвертый поток – в интервале [0,8; 1].

Задание 6.

В системе есть 3 процесса и 4 ресурса, которые можно предоставить этим процессам. Текущее распределение ресурсов и максимальное их количество следующее:

Процесс	Предоставлено R₁ , R₂ , R₃ , R₄	Требуется R₁ , R₂ , R₃ , R₄	Максимально R₁ , R₂ , R₃ , R₄
A	0 0 1 0	2 0 0 1	4 2 3 2
B	2 0 0 1	1 0 1 0
C	0 1 2 0	2 1 0 0

Будет ли в системе тупиковая ситуация?

Задание 7.

Пусть система из семи процессов (A, B, C, D, E, F, G) и шести ресурсов по одному каждого вида (R, S, T, V, W, U) в некоторый момент времени соответствует следующему списку:

процесс A занимает ресурс R и хочет получить ресурс S;
процесс B ничего не использует, но хочет получить ресурс T;
процесс C ничего не использует, но хочет получить ресурс S;
процесс D занимает ресурс U и хочет получить ресурсы S и T;
процесс E занимает ресурс T и хочет получить ресурс V;
процесс F занимает ресурс W и хочет получить ресурс S;
процесс G занимает ресурс V и хочет получить ресурс U.

Определить, заблокирована ли эта система и если да, то какие процессы в этом участвуют? Ответ получить, построив граф ресурсов и процессов.

Контрольные вопросы

В каких случаях требуется синхронизация потоков, которым требуется доступ к одному и тому же ресурсу?
Какие объекты синхронизации потоков Вы знаете?
Какими функциями Win32 API обеспечивается синхронизация потоков критическими секциями? В каких случаях для синхронизации потоков используют критические секции?
Какими функциями Win32 API обеспечивается синхронизация потоков мьютексами? В каких случаях для синхронизации потоков используют мьютексы? В чем их отличие от критических секций?
Какими функциями Win32 API обеспечивается синхронизация потоков семафорами? В каких случаях для синхронизации потоков используют семафоры?
В чем отличие и в чем сходство мьютексов и семафоров?
Какими функциями Win32 API обеспечивается синхронизация объектов событиями? В каких случаях для синхронизации потоков используются объекты? В чем их отличие от других объектов синхронизации?
В каких случаях для синхронизации потоков применяются объекты с автоматическим сбросом, а в каких случаях – объекты с ручным сбросом?
Что такое взаимоблокировки (тупики) потоков (процессов)?
Какие алгоритмы обнаружения взаимоблокировок Вы знаете? Опишите их?