Семафорное решение задачи о философах

Обозначим через Р₁, Р₂, Р₃, Р₄ - процессы-философы; b₁, b₂, b₃, b₄ - вилки. Для еды философу необходимо использовать две соседние вилки одновременно (рис. 3.12).

 

Алгоритм работы каждого философа предполагает использование пяти семафоров (S_i, i =1,4; S). Семафор S предназначен для взаимного исключения процессов при получении доступа к массиву b, отвечающему за вилки. Каждый семафор S_i предназначен для подвешивания i-го философа в том случае, если в результате проверки вилок он обнаружит, что нужных ему вилок в наличии нет. Приведем алгоритм работы первого философа, остальные работают аналогично.

P1: P(S[1]); P(S); if (b1>0)&(b2>0) then begin b1:=0; b2:=0; V(S);

{питание} P(S);

b1:=1; b2:=1; V(S);

for i:=1 to 4 do V(S[i]); {философствование} end else

V(S); goto P1;

Лабораторная работа № 21. Семафоры: защита критических секций, условная синхронизация

Цели и задачи:

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

Время: 4 часа

http://www.e-reading.club/chapter.php/141823/364/Hart_-_Sistemnoe_programmirovanie_v_srede_Windows.html

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

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

Синхронизация потоков носит иногда более сложный характер. Например, при наступлении какого-то условия необходимо приостановить поток до изменения ситуации (другим процессом) или, наоборот, при наступлении какого-то условия следует запустить поток. Одним из механизмов условной синхронизации процессов также являются семафоры.

Порядок выполнения лабораторной работы

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

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

Пример

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

Обсуждение.

Пусть для определенности буфер – это целочисленный массив из 100 элементов. Задача обладает двумя критическими секциями.

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

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

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

 

Рисунок 0‑1. Схема потоков

Решение задачи о кольцевом буфере с помощью функций WinAPI.

#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;

HANDLE hSemFull, hSemEmpty, // семафоры для условной синхронизации

hMutexD, hMutexF; // мьютексы для исключительного доступа

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

DWORD WINAPI Producer(PVOID pvParam)

{

int num;

long prev;

num = *((int *)pvParam);

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

while (true)

{

WaitForSingleObject(hSemEmpty, INFINITE);

WaitForSingleObject(hMutexD, INFINITE);

buf[rear] = rand() % n;

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

rear = (rear + 1) % n;

Sleep(1000);

ReleaseMutex(hMutexD);

ReleaseSemaphore(hSemFull, 1, &prev);

} return 0;

}

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

DWORD WINAPI Consumer(PVOID pvParam)

{

int num, data;

long prev;

num = *((int *)pvParam);

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

while (true)

{

WaitForSingleObject(hSemFull, INFINITE);

WaitForSingleObject(hMutexF, INFINITE);

data = buf[front];

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

front = (front + 1) % n;

Sleep(1000);

ReleaseMutex(hMutexF);

ReleaseSemaphore(hSemEmpty, 1, &prev);

}

return 0;

}

int main(int argc, char** argv)

{

int i, x[k + m];

DWORD dwThreadId[k + m], dw;

HANDLE hThread[k + m];

hSemEmpty = CreateSemaphore(NULL, n, n, L"Empty");

hSemFull = CreateSemaphore(NULL, 0, n, L"Full");

hMutexD = CreateMutex(NULL, FALSE, L"MutexD");

hMutexF = CreateMutex(NULL, FALSE, L"MutexF");

 

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);

// закрытие описателей событий

CloseHandle(hSemFull);

CloseHandle(hSemEmpty);

CloseHandle(hMutexF);

CloseHandle(hMutexD);

return 0;

}

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

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

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

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

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

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

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

7. Военная задача. Анчуария и Тарантерия – два крохотных латиноамериканских государства, затерянных в южных Андах. Диктатор Анчуарии, дон Федерико, объявил войну диктатору Тарантерии, дону Эрнандо. У обоих диктаторов очень мало солдат, но очень много снарядов для минометов, привезенных с последней американской гуманитарной помощью. Поэтому армии обеих сторон просто обстреливают наугад территорию противника, надеясь поразить что-нибудь ценное. Стрельба ведется по очереди до тех пор, пока либо не будут уничтожены все цели, либо стоимость потраченных снарядов не превысит суммарную стоимость всего того, что ими можно уничтожить. Создать многопоточное приложение, моделирующее военные действия.

8. Задача о читателях и писателях-2 («грязное чтение»). Базу данных разделяют два типа потоков – читатели и писатели. Читатели выполняют транзакции, которые просматривают записи базы данных, транзакции писателей и просматривают и изменяют записи. Предполагается, что в начале БД находится в непротиворечивом состоянии (т.е. отношения между данными имеют смысл). Транзакции выполняются в режиме «грязного чтения», то есть процесс-писатель не может получить доступ к БД только в том случае, если ее занял другой процесс-писатель, а процессы-читатели ему не мешают. Создать многопоточное приложение с потоками-писателями и потоками-читателями. Реализовать решение, используя семафоры, и не используя блокировки чтения-записи.

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

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

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

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

34ди к врачам и никогда их не покидают. Создать многопоточное приложение, моделирующее рабочий день клиники.

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

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

15. Задача о гостинице - 3 (дамы и джентльмены). В гостинице 10 номеров рассчитаны на одного человека и 15 номеров рассчитаны на двух человек. В гостиницу приходят клиенты дамы и клиенты джентльмены, и конечно они могут провести ночь в номере только с представителем своего пола. Если для клиента не находится подходящего номера, он уходит искать ночлег в другое место. Создать многопоточное приложение, моделирующее работу гостиницы.

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

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

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

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

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

Содержание отчета

1. Титульный лист.

2. Наименование и цель работы.

3. Краткое теоретическое описание.

4. Задание на лабораторную работу.

5. Схема алгоритма.

6. Листинг программы.

7. Результаты выполнения программы.

16. Создание и использование DLL (Microsoft Visual C++).

При разработке программ часто оказывается, что разным программным приложениям требуются одни и те же объекты, их свойства методы, процедуры и функции. Например, почти все программы выводят информацию на экран и пользуются стандартными объектами интерфейса Windows (окна, кнопки, меню…) Было бы в высшей степени неразумно запихивать код отрисовки каждого такого элемента во все программы.

Таким образом, возникает задача разделения большой программы на отдельные независимые модули, каждый из которых содержит определенный набор процедур и функций. Процедуры и функции такого модуля может вызывать любая другая программа. Подобные модули получили название динамически подключаемых библиотек (DLL – dynamically linked library, Рис. 20.1). Слово "динамический" указывает на то, что подключение библиотеки происходит не на этапе компиляции, а уже после запуска программы.

 

Рис. 20.1 DLL – библиотеки.

 

DLL-библиотеки нашли самое широкое применение в большинстве программ. Скажем, сама операционная система Windows включает в свой состав несколько сотен DLL, и заключенная в них функциональность может использоваться нашими программами во избежание очередного изобретения велосипеда.

Создание повторно используемого кода (C++)

С помощью Visual C++ можно создавать библиотеки трех следующих типов:

· библиотеки динамической компоновки (DLL);

· статические библиотеки;

· управляемые сборки.

Как правило, если необходимо создать библиотеку, которая могла бы использоваться машинным кодом C++, то следует предпочесть библиотеку динамической компоновки или статическую библиотеку. Если необходимо создать библиотеку, которая могла бы использоваться кодом на языках C++/CLI или на любом ином языке.NET, например C# или Visual Basic, то следует предпочесть управляемую сборку.

Создание и использование библиотеки DLL (C++)

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

В этом пошаговом руководстве рассматриваются следующие действия:

· создание проекта библиотеки динамической компоновки (DLL);

· добавление класса в библиотеку динамической компоновки;

· создание приложения, ссылающегося на библиотеку динамической компоновки;

· использование функциональных возможностей библиотеки классов в консольном приложении;

· запуск приложения.

Обязательные компоненты