Задачу требуется решить для фиксированного количества редакторов и читателей, например, количество редакторов - 2, количество читателей - 3, при этом реально с файлом можно не работать, а достаточно обозначить факты входа в критический участок и выхода из него для каждого процесса.
Методика решения
Методика решения включает в себя общую структуру программы и словесное описание условий входа в критический участок и выхода из него для процесса-редактора и процесса-читателя.
Общая структура программы выглядит следующим образом:
Program Lab3;
Uses MultiObj;
Type
PMonitor = ^TMonitor;
TMonitor = Object
Nrf, {число читателей, работающих с файлом}
Nwf, {число редакторов, работающих с файлом}
Nrw, {число читателей, ждущих допуска к файлу}
Nww : Integer;{число редакторов, ждущих допуска к файлу}
R_List, {очередь читателей}
W_List : List;{очередь редакторов}
Сonstructor Init;
Destructor Done; Virtual;
Procedure Enter_R;
Procedure Enter_W;
Procedure Exit_R;
Procedure Exit_W;
End {TMonitor};
{--Реализация методов монитора возлагается на учащегося--}
Var
Monitor : PMonitor;
Procedure Reader_1;
Begin
While True Do Begin
{Случайное время работы без ресурса}
Monitor^.Enter_R;
{Случайное время работы с ресурсом}
Monitor^.Exit_R;
End {While};
End {Reader_1};
Procedure Reader_2;
Begin
While True Do Begin
{Случайное время работы без ресурса}
Monitor^.Enter_R;
{Случайное время работы с ресурсом}
Monitor^.Exit_R;
End {While};
End {Reader_2};
Procedure Reader_3;
Begin
While True Do Begin
{Случайное время работы без ресурса}
Monitor^.Enter_R;
{Случайное время работы с ресурсом}
Monitor^.Exit_R;
End {While};
End {Reader_3};
{Процедуры Reader_1, Reader_2 и Reader_3 структурно одинаковы, но
различаются, например, координатами вывода на экран своего статуса -
"работает с файлом", "ждет доступа к файлу", "не требует доступа к
файлу".}
Procedure Writer_1;
Begin
While True Do Begin
{Случайное время работы без ресурса}
Monitor^.Enter_W;
{Случайное время работы с ресурсом}
Monitor^.Exit_W;
End {While};
End {Writer_1};
Procedure Writer_2;
Begin
While True Do Begin
{Случайное время работы без ресурса}
Monitor^.Enter_W;
{Случайное время работы с ресурсом}
Monitor^.Exit_W;
End {While};
End {Writer_2};
{Процедуры Writer_1 и Writer_2 структурно одинаковы, но
различаются, например, координатами вывода на экран своего статуса -
"работает с файлом", "ждет доступа к файлу", "не требует доступа к
файлу".}
Procedure KeyManager;
Begin
While True Do Begin
If Клавиша нажата Then Begin
Чтение клавиши;
Case Клавиша Of
'Esc' : Остановить работу ядра;
Else
End {Case};
End {If};
End {While};
End {KeyManager};
Begin
Monitor := New(PMonitor, Init);
Создать процесс из процедуры KeyManager;
Создать процесс из процедуры Reader_1;
Создать процесс из процедуры Reader_2;
Создать процесс из процедуры Reader_3;
Создать процесс из процедуры Writer_1;
Создать процесс из процедуры Writer_2;
Начать работу ядра;
Dispose(Monitor, Done);
End {Lab3}.
Все разнообразие алгоритмов доступа читателей и редакторов к файлу реализуется в методах монитора. Ниже представлено словесное описание условий входа в критический участок и выхода из него для читателей и редакторов, которые могут быть реализованы учащимися.
Условие входа в критический участок читателя может выглядеть следующим образом:
If Файл занят редактором Or Есть редакторы в очереди Then Begin
Инкремент числа читателей в очереди;
Постановка читателя в очередь;
Передача управления;
Декремент числа читателей в очереди;
End {If};
Инкремент числа читателей, работающих с файлом;
Условие входа в критический участок редактора может выглядеть следующим образом:
If Файл занят редактором Or Файл занят читателями Then Begin
Инкремент числа редакторов в очереди;
Постановка редактора в очередь;
Передача управления;
Декремент числа редакторов в очереди;
End {If};
Инкремент числа редакторов, работающих с файлом;
Условие выхода читателя из критического участка может выглядеть следующим образом:
Декремент числа читателей, работающих с файлом;
If Нет читателей, работающих с файлом And Есть редактор в очереди Then Begin
Активизация редактора;
End {If};
Условие выхода редактора из критического участка может выглядеть следующим образом:
Декремент числа редакторов, работающих с файлом;
If Есть читатели в очереди Then Begin
Активизация всех читателей из очереди;
End Else Begin {нет читателей, ждущих доступа к файлу}
Активизация первого редактора из очереди,если таковая имеется;
End {If};
Устранение возможного бесконечного ожидания редактора, когда постоянно подходят читатели к критическому ресурсу, в данном случае устраняется следующим условием:
- читатель встает в очередь, если уже есть очередь из редакторов;
- последний из читателей, работающих в данный момент с ресурсом, активизирует редактора;
а устранение возможного бесконечного ожидания читателей устраняется тем, что выходящий из критического участка редактор в первую очередь активизирует читателей, ждущих ресурса, и если
таковых нет, то только тогда делается попытка активизировать редактора.
Таким образом обеспечивается достаточно справедливое выделение ресурса-файла процессам двух видов:
- после отработки редактора с файлом, последний предоставляется всем читателям, стоящим в очереди к моменту окончания работы с файлом редактора; а после отработки с файлом всех этих читателей, файл предоставляется одному редактору и т.д.
Вторым вариантом справедливого распределения ресурса является запись редакторов и читателей в одну очередь и предоставление ресурса в порядке очередности, но с учетом особенностей процессов:
- редактор активизируется один, а читатели активизируются все стоящие в очереди перед редактором.
Учащемуся рекомендуется реализовать на выбор один из предлагаемых алгоритмов или реализовать свой собственный.
Задача 4. МОДЕЛЬ НАЗНАЧЕНИЯ ОДНОРОДНЫХ РЕСУРСОВ
Имеется N единиц однородного ресурса и М процессов. Каждый процесс может запросить нужное ему количество ресурсов от 1 до N единиц. Если в свободных ресурсах нет запрашиваемого им количества, то процесс вынужден приостановиться и ждать их освобождения. Требуется запрограммировать задачу, написав монитор "Ресурс", реализующий выделение запрашиваемого количества ресурсов и свободный от бесконечного ожидания.
Методика решения
Если обозначить через n, количество единиц ресурса, запрашиваемое текущим процессом, и обозначить через Nсвоб количество свободных в данный момент ресурсов, то условие выделения ресурса процессу будет выглядеть следующим образом:
n <= Nсвоб.
Невыполнение данного условия должно приводить к блокированию процесса.
Общая структура программы выглядит следующим образом.
Program Lab4;
Uses MultiObj;
Type
PMonitor = ^TMonitor;
TMonitor = Object
N,
Nсвоб : Integer;
RList : List;
Constructor Init(...);
- 21 -
Destructor Done;
Procedure Request;
Procedure Free;
End {TMonitor};
{--Реализация методов монитора возлагается на учащегося--}
Var
Monitor : PMonitor;
Procedure Process_1;
Begin
While True Do Begin
{случайное времы работы без ресурса}
Monitor^.Request;
{случайное время работы с ресурсом}
Monitor^.Free;
End {While}:
End {Process_1};
Procedure Process_2;
Begin
While True Do Begin
{случайное времы работы без ресурса}
Monitor^.Request;
{случайное время работы с ресурсом}
Monitor^.Free;
End {While}:
End {Process_2};
Procedure Process_3;
Begin
While True Do Begin
{случайное времы работы без ресурса}
Monitor^.Request;
{случайное время работы с ресурсом}
Monitor^.Free;
End {While}:
End {Process_3};
{Процедуры Process_1, Process_2 и Process_3 структурно одинаковы,
но различаются, например, координатами вывода на экран своего
статуса - "не требует ресурса", "ждет данного количества
ресурса", "работает с данным количеством ресурса"}
Procedure KeyManager;
- 22 -
{Процедура KeyManager аналогична с задачей 3}
End {KeyManager};
Begin
Monitor := New(PMonitor, Init);
Создать процесс из процедуры KeyManager;
Создать процесс из процедуры Process_1;
Создать процесс из процедуры Process_2;
Создать процесс из процедуры Process_3;
Начать работу ядра;
Dispose(Monitor, Done);
End {Lab4}.
Управление доступом к ресурсам осуществляется методами
Request и Free объекта TMonitor.
Исходя из условий задачи, структура метода Request может выглядеть следующим образом:
Определить случайное число n в диапазоне от 1 до N - количество
единиц ресурса, запрашиваемых текущим процессом;
Записать значение n в дескриптор процесса;
If n > Nсвоб ИЛИ Есть процессы, стоящие в очереди
Тhen Begin
Инкремент числа процессов, стоящих в очереди;
Включение процесса в очередь;
Передача управления;
Декремент числа процессов, стоящих в очереди;
End {If};
Ncвоб := Nсвоб - n;
Структура метода Free может выглядеть следующим образом: