End {Case};
End {If};
End {While};
- 9 -
End {KeyManager};
Begin
Monitor := New(PMonitor, Init);
Создать процесс из процедуры KeyManager;
Начать работу ядра;
Dispose(Monitor, Done);
End {Lab1}.
Наиболее важным этапом решения задачи является определение структуры методов TMonitor.Enter_L_R, TMonitor.Enter_R_L, TMonitor.Exit_L_R, а также условий входа в критический участок и выхода из него для процессов всех типов. Ниже предлагаются варианты данных методов для случая, когда нет ограничений на количество поездов одного направления, находящихся на
единственном пути.
Структура метода входа в критический участок имеет следующий вид:
Запрет прерываний;
If На единственном пути есть поезда противополжного направления
Then Begin
Увеличение числа процессов, ждущих в очереди, на единицу;
Включение процесса в очередь, ждущих входа на единственный
путь;
Передача управления процессу, первому в очереди готовых
процессов;
Уменьшение числа процессов, ждущих в очереди, на единицу;
End {If};
Увеличение числа процессов, находящихся на единственном пути, на единицу;
Разрешение прерываний;
Структура метода выхода из критического участка имеет
следующий вид:
Запрет прерываний;
Уменьшение числа процессов, находящихся на единственном пути, на
единицу;
If Единственный путь свободен Then Begin
While Очередь не пуста Do Begin
Исключить первый процесс из очереди процессов, ждущих
входа на единственный путь с противоположного
направления;
Включить этот процесс в очередь готовых процессов;
End {While};
End {If};
Разрешение прерываний;
Замечания
1) Методы монитора должны выполняться в режиме взаимного исключения, поэтому на входе любого метода выполняется запрет прерываний, а на выходе - разрешение прерываний.
2) Методы входа на критический участок и выхода из него для поездов обоих направлений идентичны по структуре и различаются лишь параметрами.
3) Представлена именно структура методов, их полная реализация возлагается на учащегося.
4) Предполагается, что учащийся освоил курс лабораторных работ, связанных с построением многозадачного ядра управления процессами, и знаком с реализацией механизмов исключения процессов из очередей, включения процессов в очереди, передачи управления и т.п.
Представленные алгоритмы входа в критический участок и выхода из него обладают тем недостатком, что приводят к бесконечному ожиданию выхода поездов одного направления на
единственный путь, если последний захвачен поездами другого направления.
Устранить данный недостаток можно различными способами, примеры которых перечислены ниже.
1) Заявки на прохождение единственного пути устанавливать в одну очередь и выпускать поезда на единственный путь согласно этой очереди. При этом, если следующим в очереди за выпускаемым находится поезд того же направления, то можно выпустить и его, вплоть до некоторого значения N. В последнем случае направление поезда следует писать в дескриптор процесса, его реализующего.
2) Сохранить две очереди в соответствие с направлениями движения поездов, но фиксировать момент времени постановки процесса в очередь и первым активизировать процесс, у которого момент постановки в очередь меньший не зависимо от очереди, в которой этот процесс находится. В этом случае время постановки в очередь следует писать в дескриптор процесса.
3) Не пропускать дополнительные поезда на единственный путь, а ставить их в очередь, если в очереди противоположного направления уже есть поезда, и не активизировать поезда текущего направления при выходе из критического участка, если есть поезда противоположного направления в очереди, а активизировать их, когда единственный путь окажется свободным.
В любом варианте не меняются структуры процедур монитора, реализующих вход в критический участок и выход из него, а меняется лишь вид условий If ... Then блокировки и активизации процессов.
Учащийся по согласованию с преподавателем выбирает для программирования вариант входа в критический участок и выхода из него или создает собственный алгоритм.
Задача 2. МОДЕЛЬ ДОРОЖНОГО ПЕРЕКРЕСТКА
Две автомобильные дороги В-Н и Л-П образуют перекресток, как показано схеме.
Автомобили могут двигаться через перекресток по дорогам В-Н и Л-П со следующими ограничениями:
- на свободный перекресток может выехать автомобиль с любого направления;
- если на территории перекрестка появился автомобиль направления В-Н или Н-В (Л-П или П-Л), то на ней не может появиться автомобиль направления Л-П или П-Л (В-Н или Н-В). Последний должен быть приостановлен и может возобновить свое движение только после освобождения перекрестка, автомобили же "своих" направлений могут въезжать в это время на перекресток.
В
¦ ^ ¦ ¦
¦ ¦ ¦ ¦
¦ ¦ ¦ ¦
===========- ¦ ¦ L==========
-------------+-+-----------> П
Л <------------+-+------------
===========¬ ¦ ¦ г==========
¦ ¦ ¦ ¦
¦ ¦ ¦ ¦
¦ ¦ v ¦
Н
Требуется запрограммировать задачу, написав монитор "Перекресток" для следующих условий:
- ограничить число автомобилей данного направления, допускаемых на перекресток, значением N;
- преодолеть проблему бесконечного ожидания, когда захватив перекресток, автомобили "своих" направлений не дают возможности выйти на перекресток автомобилям других направлений сколь угодно долго.
Методика решения
Методика решения включает в себя общую структуру программы и словесное описание условий входа в критический участок (перекресток) и условий выхода из него.
Общая структура программы выглядит следующим образом:
Program Lab2;
Uses MultiObj;
Type
PMonitor = ^TMonitor;
TMonitor = Object
{данные - количество автомобилей, ждущих и
движущихся по перекрестку по каждому нарправлению}
{данные - очереди ожидания выхода на перекресток по
каждому направлению}
Сonstructor Init(...);
Destructor Done; Virtual;
Procedure Enter_L_R;
Procedure Enter_R_L;
Procedure Enter_U_D;
Procedure Enter_D_U;
Procedure Exit_L_R;
Procedure Exit_R_L;
Procedure Exit_U_D;
Procedure Exit_D_U;
End {TMonitor};
{--Реализация методов монитора возлагается на учащегося--}
Var
Monitor : PMonitor;
Procedure Move_L_R;
Begin
{движение до входа в критический участок}
Monitor^.Enter_L_R;
{движение в критическом участке}
Monitor^.Exit_L_R;
{движение после выхода из критического участка}
{самоуничтожение}
End {Move_L_R};
Procedure Move_R_L;
Begin
{движение до входа в критический участок}
Monitor^.Enter_R_L;
{движение в критическом участке}
Monitor^.Exit_R_L;
{движение после выхода из критического участка}
{самоуничтожение}
End {Move_R_L};
Procedure Move_U_D;
Begin
{движение до входа в критический участок}
Monitor^.Enter_U_D;
{движение в критическом участке}
Monitor^.Exit_U_D;
{движение после выхода из критического участка}
{самоуничтожение}
End {Move_U_D};
Procedure Move_D_U;
Begin
{движение до входа в критический участок}
Monitor^.Enter_D_U;
{движение в критическом участке}
Monitor^.Exit_D_U;
{движение после выхода из критического участка}
{самоуничтожение}
End {Move_D_U};
Procedure KeyManager;
Begin
While True Do Begin
If Клавиша нажата Then Begin
Чтение клавиши;
Case Клавиша Of
- 14 -
'Esc' : Остановить работу ядра;
'L','l' : Создать процесс из процедуры Move_L_R;
'R','r' : Создать процесс из процедуры Move_R_L;
'U','u' : Создать процесс из процедуры Move_U_D;
'D','d' : Создать процесс из процедуры Move_D_U;
Else
End {Case};
End {If};
End {While};
End {KeyManager};
Begin
Monitor := New(PMonitor, Init);
Создать процесс из процедуры KeyManager;
Начать работу ядра;
Dispose(Monitor, Done);
End {Lab2}.
Условие входа в критический участок на уровне словесного описания может выглядеть следующим образом:
If На критическом участке находятся автомобили пересекающих
направлений OR
Автомобилей своего направления больше, чем N, OR
Есть очередь из автомобилей своего направления OR
Есть очереди из автомобилей пересекающих направлений
Then Begin
Инкремент числа стоящих в очереди автомобилей;
Включение автомобиля в очередь;
Передача управления;
Декремент числа стоящих в очереди автомобилей;
End {If};
Инкремент числа находящихся на перекрестке автомобилей;
Условие выхода из критического участка на уровне словесного описания выглядит следующим образом:
Декремент числа находящихся на перекрестке автомобилей;
If Есть очереди из автомобилей пересекающих направлений
Then Begin
If Перекресток свободен от автомобилей непересекающих
направлений
Then Begin
Активизировать автомобили из очередей пересекающих
- 15 -
направлений, в количестве не более N для каждого;
End {If};
End Else Begin {нет очередй из автомобилей пересекающих
направлений}
Выпустить один автомобиль своего направления на перекресток,
если таковой есть в очереди;
End {If};
Учащемуся необходимо реализовать алгоритмы входа в критический участок и выхода из него, представленные выше в форме словесного описания, или реализовать собственные алгоритмы, обеспечивающие ограничение на количество автомобилей одного направления на перекрестке не более N и отсутствие бесконечного ожидания.
Задача 3. МОДЕЛЬ ЧИТАТЕЛЕЙ И РЕДАКТОРОВ
Имеется файл, управляемый процессами двух типов:
- читателями, которые могут просматривать файл без изменения его содержания;
- редакторами, которые могут изменять файл.
Требуется реализовать программу, которая обеспечивала бы следующую дисциплину доступа к файлу:
- в произвольный момент времени работать с файлом может только один редактор и ни одного читателя;
- одновременно работать с файлом могут несколько читателей и ни одного редактора;
- отсутствует бесконечное ожидание, когда редактор не может получить доступ к файлу из-за постоянного появления читателей, обращающихся к файлу и наоборот, когда читатели не могут получить доступ к ресурсу из-за постоянного появления запросов редакторов.