Nсвоб := Nсвоб + n;
Temp := Nсвоб;
While Очередь не пуста Do Begin
If Для первого в очереди n <= Temp Then Begin
Процесс, первый в очереди, перевести в очередь готовых
процессов;
Temp := Temp - n;
End Else Begin
Break;
End {If};
End {While};
Возможность бесконечного ожидания процесса, ждущего большого количества ресурсов, когда все время появляются процессы, запрашивающие и получающие небольшое количество ресурсов, устраняется в данном решении следующим образом:
- процесс встает в очередь, если есть уже в очереди другие процессы;
- выделение ресурсов процессам при их активизации осуществляется исключительно, начиная с первого в очереди, если первому в очереди не хватает свободных ресурсов, то активизация
процессов не производится.
В данной задаче учащимся необходимо создать объект-наследник объекта Process мультизадачного ядра MultiObj, добавив в дескриптор поле, где будет храниться количество запрошенных
процессом ресурсов.
Задача 5. МОДЕЛЬ ОБЕДАЮЩИХ ФИЛОСОФОВ
Пять философов сидят за круглым обеденным столом. Между каждыми двумя философами есть одна вилка, которая может быть общей для них.
Каждый философ может либо думать, не требуя вилок, либо есть, используя две соседние вилки, расположенные по одну и по другую стороны от него. Время обеих фаз "думать" и "есть" - произвольная конечная величина. При отсутствии двух свободных вилок, необходимых философу для еды, последний переходит в состояние ожидания.
Требуется решить задачу, написав монитор "Вилки", реализующий выделение вилок философам и обеспечивающий возможность их перехода от состояния "думать" к состоянию "есть" без бесконечного ожидания.
Методика решения
Примем следующую нумерацию философов и вилок:
- будем нумеровать философов от 0 до 4;
- будем нумеровать вилки от 0 до 4;
- будем считать, что у философа с номером i слева лежит вилка с номером i, а справа - вилка с номером (i+1) mod 5.
Если философов интерпретировать как процессы, а вилки – как общие ресурсы, то общую структуру программы можно представить следующим образом.
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
{случайное время в фазе "думать"}
- 25 -
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;
- 27 -
End {If};
If Процесс с номером (i+4)mod5 в очереди
И
Вилка[(i+4)mod5] свободна
Then Begin
Вилка[(i+4)mod5] := занята;
Вилка[i] := занята;
Активизировать процесс с номером (i+4)mod5;
End {If};
В данной задаче учащимся необходимо создать объект-наследник
объекта Process мультизадачного ядра MultiObj, добавив в
дескриптор поле, где будет храниться номер процесса-философа.
Задача 6. МОДЕЛЬ КЛИЕНТ-СЕРВЕР
Имеется N процессов-клиентов и один процесс-сервер. Процессы-клиенты в случайные моменты времени запрашивают обслуживание у процесса-сервера. Если процесс-сервер свободен, то
он выполняет обслуживание клиента и переходит в состояние ожидания запроса.
Если процесс-клиент запрашивает обслуживание, когда процесс-сервер занят, то клиент приостанавливает свое выполнение и ждет обслуживания в очереди.
Требуется запрограммировать задачу, написав монитор "Сервер", реализующий обслуживание клиентов в порядке очередности их запросов.
Методика решения
Ведем дополнительные условия:
- процесс-сервер запускается первым и ждет запросов на обслуживание;
- процесс-клиент блокируется не только при ожидании обслуживания, но и на время самого обслуживания.
Структура программы для описанных условий может выглядеть следующим образом.
Program Lab6;
Uses MultiObj;
Type
PMonitor = ^TMonitor;
- 28 -
TMonitor = Object
Cl_List, {очередь клиентов, ждущих обслуживания}
Cl_s_List, {очередь из одного клиента, обслуживаемого
в данный момент}
Sr_List : List; {очередь, в которой сервер ждет
запросов на обслуживание}
Constructor Init;
Destructor Done;
Procedure Request; {запрос клиента на обслуживание}
Procedure Waiting; {ожидание сервером запросов}
End {TMonitor};
{--Методы монитора разрабатываются учащимися--}
Var
Monitor : PMonitor;
Procedure Client_1;
Begin
While True Do Begin
{случайное время до запроса на обслуживания}
Monitor^.Request;
End {While};
End {Client_1};
Procedure Client_2;
Begin
While True Do Begin
{случайное время до запроса на обслуживания}
Monitor^.Request;
End {While};
End {Client_2};
Procedure Client_3;
Begin
While True Do Begin
{случайное время до запроса на обслуживания}
Monitor^.Request;
End {While};
End {Client_3};
{Процессы-клиенты отличаются друг от друга только координатами
вывода на экран своих состояний - "работа вне обслуживания",
"ожидание обслуживания", "обслуживание"}
Procedure Server;
- 29 -
Begin
While True Do Begin
Monitor^.Waiting;
{случайное время обслуживания клиента}
End {While};
End {Server};
Procedure KeyManager;
{Процедура KeyManager аналогична с задачами 3, 4 и 5}
End {KeyManager};
Begin
Monitor := New(PMonitor, Init);
Создать процесс из процедуры Server;
Создать процесс из процедуры KeyManager;
Создать процесс из процедуры Client_1;
Создать процесс из процедуры Client_2;
Создать процесс из процедуры Client_3;
Начать работу ядра;
Dispose(Monitor, Done);
End {Lab6}.
Структура метода TMonitor.Request, который выполняется
клиентом, может быть представлена следующим образом.
If Сервер свободен Then Begin
Активизация сервера;
End {If};
Встать в очередь ожидания обслуживания;
Передача управления;
Структура метода TMonitor.Waiting, который выполняется
сервером, может выглядеть следующим образом:
If Обслужен процесс Then Begin
Активизировать обслуженный процесс;
End {If};
If Нет клиентов, запрашивающих обслуживание Then Begin
Блокирование процесса-сервера;
Передача управления;
End {If};
Перевод процесса, первого в очереди ожидания обслуживания, в
очередь обслуживаемых процессов;
Учащемуся предстоит реализовать программу, выводя на экран
- 30 -
состояния всех процессов и время, оставшееся до перехода в другое
состояние. А также решить задачу с учетом нескольких
обслуживающих процессов.
Задача 7. МОДЕЛЬ ФУНКЦИОНИРОВАНИЯ ЛИФТА
В двухэтажном доме имеется лифт. Пассажиры, появляющиеся на первом этаже, желают подняться на второй этаж, а пассажиры, появляющиеся на втором этаже, желают спуститься на первый этаж. Пассажиры, появляющиеся во время движения лифта, должны ожидать его освобождения в очереди. Лифт могут занимать N пассажиров.
Требуется запрограммировать задачу, написав монитор "Лифт" и обеспечив справедливое выделения лифта пассажирам в зависимости от их появления в системе. Лифт следует рассматривать как процесс-сервер.