Работа №2
Задание, представленное ниже, представляют собой задачу на организацию доступа к общему (разделяемому, критическому) ресурсу некоторого числа параллельных процессов.
Для управления доступом к общему ресурсу наиболее целесообразно создать объект - монитор. Монитор состоит из множества переменных состояния и множества процедур, которые используют эти переменные. Некоторые из этих процедур, называемые внешними, доступны пользователю и называются точками входа в монитор. Процессы, которые используют монитор для синхронизации, не имеют прямого доступа к переменным состояния. Они могут воспользоваться монитором только путем вызова внешних процедур. Процедуры монитора включают операции, которые позволяют блокировать и активизировать процессы в соответствие со спецификацией задачи. Условия установки и снятия блокировки записываются в виде функций переменных состояния и механизм работы монитора гарантирует, что все преобразования этих переменных происходят при взаимном исключении.
Монитор может иметь следующее общее описание (в терминах объектно-ориентированного языка Pascal):
Type
TMonitor = Object
данные - переменные состояния
Constructor Init(...);
Destructor Done; Virtual;
Procedure Enter;
Procedure Exit; End TMonitor.
В качестве данных выступают параметры спецификации задачи и очереди ожидания процессов.
Метод TMonitor.Enter, анализируя данные, выполняет следующие действия:
- проверяет условия входа в критический участок; при выполнении этих условий процесс, вызвавший метод, продолжает выполняться, войдя в критический участок; при невыполнении - процесс блокируется в очереди монитора;
- устанавливает необходимые значения переменных состояния при блокировании процесса и при продолжении выполнения в критическом участке.
Метод TMonitor.Exit выполняет следующие действия:
- устанавливает необходимые значения переменных состояния при выходе из критического участка;
- проверяет условия возможной активизации ждущих процессов и активизарует их при выполнении этих условий.
Структура процедуры, реализующей процесс, осуществляющий доступ к критическому ресурсу с помощью монитора, будет выглядеть следующим образом:
Procedure Process;
Begin
действия процесса до входа в критический участок
Monitor.Enter;
действия процесса в критическом участке
Monitor.Exit;
действия процесса после выхода из критического участка
End Process;
здесь Monitor - это переменная типа TMonitor, являющаяся
экземпляром указанного объекта.
Количество различающихся методов входа в критический участок и методов выхода из него определяется количеством разновидностей процессов в каждой прикладной задаче.
В представленной ниже задаче требуется создать свой монитор. Основой решения каждой задачи является формирование и формализация условий входа в критический участок и условий активизации ждущих процессов при выходе из критического участка.
Методика решения задачи предлагает один вариант решения, что конечно же, не исключает возможности решения задачи с помощью других алгоритмов.
Для тех, кто затрудняется создать свой монитор, рекомендуется запрограммировать условия, предлагаемые в методике решения каждого задания в виде отдельных процедур.
Практическое решение задачи оформляется в виде отчета. Отчет должен содержать:
- спецификацию задачи;
- обоснование условий входа в критический участок и активизации ждущих процессов при выходе из него для каждой разновидности процессов;
- текст программы с комментариями.
Требования к программам, реализующим задания:
- программа должна выглядеть как законченный продукт - иметь средства, отображающие на экране действия и состояния всех процессов.
Задача 5. МОДЕЛЬ ОБЕДАЮЩИХ ФИЛОСОФОВ
Пять философов сидят за круглым обеденным столом. Между каждыми двумя философами есть одна вилка, которая может быть общей для них.
Каждый философ может либо думать, не требуя вилок, либо есть, используя две соседние вилки, расположенные по одну и по другую стороны от него. Время обеих фаз "думать" и "есть" - произвольная конечная величина. При отсутствии двух свободных вилок, необходимых философу для еды, последний переходит в состояние ожидания.
Требуется решить задачу, написав монитор "Вилки", реализующий выделение вилок философам и обеспечивающий возможность их перехода от состояния "думать" к состоянию "есть" без бесконечного ожидания.
Методика решения
Примем следующую нумерацию философов и вилок:
- будем нумеровать философов от 0 до 4;
- будем нумеровать вилки от 0 до 4;
- будем считать, что у философа с номером i слева лежит вилка с номером i, а справа - вилка с номером (i+1)mod5.
Если философов интерпретировать как процессы, а вилки - как общие ресурсы, то общую структуру программы можно представить следующим образом:
Program Lab5;
Uses MultiObj;
Type
PMonitor = ^TMonitor;
TMonitor = Object
V: Array[0..4] Of Boolean; данные, описывающие
состояние вилок - сободна/занята PHList: List;
Constructor Init(...);
Destructor Done; Virtual;
Procedure Enter_Eat;
Procedure Exit_Eat; End TMonitor;
--Реализация методов монитора возлагается на учащегося--
Var
Monitor: PMonitor;
Procedure Phil_1;
Begin
While True Do Begin
случайное время в фазе "думать"
Monitor^.Enter_Eat;
случайное время в фазе "есть"
Monitor^.Exit_Eat;
End While;
End Phil_1;
Procedure Phil_2;
Begin
While True Do Begin
случайное время в фазе "думать"
Monitor^.Enter_Eat;
случайное время в фазе "есть"
Monitor^.Exit_Eat;
End While;
End Phil_2;
Procedure Phil_3;
Begin
While True Do Begin
случайное время в фазе "думать"
Monitor^.Enter_Eat;
случайное время в фазе "есть"
Monitor^.Exit_Eat;
End While;
End Phil_3;
Procedure Phil_4;
Begin
While True Do Begin
случайное время в фазе "думать"
Monitor^.Enter_Eat;
случайное время в фазе "есть"
Monitor^.Exit_Eat;
End While;
End Phil_4;
Procedure Phil_5;
Begin
While True Do Begin
случайное время в фазе "думать"
Monitor^.Enter_Eat;
случайное время в фазе "есть"
Monitor^.Exit_Eat;
End While;
End Phil_5;
Процедуры Phil_1.. Phil_5 структурно одинаковы, но различаются,
например, координатами вывода состояния философа на экран
Procedure KeyManager;
Процедура KeyManager аналогична с задачами 3 и 4
End KeyManager;
Begin
Monitor:= New(PMonitor, Init);
Создать процесс из процедуры KeyManager;
Создать процесс из процедуры Phil_1;
Создать процесс из процедуры Phil_2;
Создать процесс из процедуры Phil_3;
Создать процесс из процедуры Phil_4;
Создать процесс из процедуры Phil_5;
Начать работу ядра;
Dispose(Monitor, Done);
End Lab5.
Бесконечное ожидание процессов может возникнуть, если организовать монитор таким образом, что философы могут брать вилки по одной. Тогда, если каждый философ захватит, например, правую от себя вилку и перейдет в состояние ожидания левой вилки, то вся система перейдет в состояние тупика. Поэтому введем ограничение, состоящее в том, что i-й философ может перейти в состояние "есть" только при наличии двух свободных вилок с номерами i и (i+1)mod5. Если философ захотел "есть" и только одна из необходимых ему вилок свободна (или ни одной), то он переходит в состояние ожидания.
Структура метода монитора, реализующего вход в критический участок может тогда выглядеть следующим образом:
Определение номера i философа, соответствующего текущему процессу;
If Вилка[i] или Вилка[(i+1)mod5] заняты Then Begin
Поставить процесс в очередь;
Передать управление;
End If;
Вилка[i]:= занята;
Вилка[(i+1)mod5]:= занята;
При освобождении вилок философом с номером i монитор делает проверку, есть ли философы, связанные с данными вилками в очереди (это философы с номерами (i+1)mod5 и (i+4)mod5), и свободны ли дополнительные для этих философов вилки (это вилки с номерами (i+2)mod5 и (i+4)mod5). При положительном ответе данные философы активизируются.
Структура метода монитора, реализующего выход из критического участка может тогда выглядеть следующим образом:
Определение номера i философа, соответствующего текущему
процессу;
Вилка[i]:= свободна;
Вилка[(i+1)mod5]:= свободна;
If Процесс с номером (i+1)mod5 в очереди
И
Вилка[(i+2)mod5] свободна
Then Begin
Вилка[(i+1)mod5]:= занята;
Вилка[(i+2)mod5]:= занята;
Активизировать процесс с номером (i+1)mod5;
End If;
If Процесс с номером (i+4)mod5 в очереди
И
Вилка[(i+4)mod5] свободна
Then Begin
Вилка[(i+4)mod5]:= занята;
Вилка[i]:= занята;
Активизировать процесс с номером (i+4)mod5;
End If;
В данной задаче учащимся необходимо создать объект-наследник объекта Process мультизадачного ядра MultiObj, добавив в дескриптор поле, где будет храниться номер процесса-философа.