Работа №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, являющаяся
экземпляром указанного объекта.
Количество различающихся методов входа в критический участок и методов выхода из него определяется количеством разновидностей процессов в каждой прикладной задаче.
В представленной ниже задаче требуется создать свой монитор. Основой решения каждой задачи является формирование и формализация условий входа в критический участок и условий активизации ждущих процессов при выходе из критического участка.
Методика решения задачи предлагает один вариант решения, что конечно же, не исключает возможности решения задачи с помощью других алгоритмов.
Для тех, кто затрудняется создать свой монитор, рекомендуется запрограммировать условия, предлагаемые в методике решения каждого задания в виде отдельных процедур.
Практическое решение задачи оформляется в виде отчета. Отчет должен содержать:
- спецификацию задачи;
- обоснование условий входа в критический участок и активизации ждущих процессов при выходе из него для каждой разновидности процессов;
- текст программы с комментариями.
Требования к программам, реализующим задания:
- программа должна выглядеть как законченный продукт - иметь средства, отображающие на экране действия и состояния всех процессов.
Задача 1. МОДЕЛЬ ЖЕЛЕЗНОДОРОЖНОГО ПЕРЕГОНА
Железная дорога, соединяющая два города А и В, включает участок, на котором имеется только единственный путь, см. схему.
Движение поездов на единственном пути подчиняется следующим ограничениям:
- на свободный единственный путь может войти поезд любого направления;
- пока на единственном пути находится поезд некоторого направления, на него не может войти поезд другого направления, но может войти поезд того же направления.
--->--------- ------>----
v ^
А ------>------<------- B
v ^
---<--------- ------<----
Требуется запрограммировать задачу, написав монитор, для двух вариантов условий:
1) нет ограничений на количество поездов одного направления, находящихся на единственном пути;
2) ограничить количество поездов одного направления, находящихся на единственном направлении значением N и решить проблему "бесконечного ожидания", свойственную первому варианту, когда поезда одного направления, захватив единственный путь, не позволяют поездам другого направления пройти по этому пути. При этом необходимо реализовать рациональный порядок выделения единственного пути поездам обоих направлений.
Методика решения
В данной задаче "единственный путь" является общим ресурсом для поездов, которые должны моделироваться процессами. Регламентация доступа процессов к этому общему ресурсу осуществляется средством "монитор".
Поскольку в задаче имеется два вида процессов - поезда, движущиеся слева направо, и поезда, движущиеся справа налево, то методов входа в критический участок и выходов из него будет в мониторе по два, на каждый вид процесса, то есть внутри объекта TMonitor должны быть объявлены следующие методы:
Procedure Enter_L_R; вход поезда, движущегося слева направо, в критический участок
Procedure Enter_R_L; вход поезда, движущегося справа налево, в критический участок
Procedure Exit_L_R; выход поезда, движущегося слева направо, из критического участка
Procedure Exit_R_L; выход поезда, движущегося справа налево, из критического участка.
Методы входа проверяют условия входа в критический участок. При выполнении этих условий процесс продолжает выполняться, входя в критический участок, а при невыполнении - процесс приостанавливается в очереди. При этом в обоих случаях устанавливаются необходимые данные, например, увеличивается количество движущихся в критическом участке поездов данного направления или увеличивается количество ждущих входа в критический участок поездов данного направления.
Методы выхода проверяют условия возможной активизации блокированных процессов, активизируют их при выполнении этих условий и устанавливаю необходимые данные, например, уменьшают количество движущихся в критическом участке поездов данного направления и уменьшают количество ждущих поездов.
Условия блокировки и активизации процессов-поездов позволяют определить те данные, которые необходимо анализировать в мониторе, а именно,
- количество поездов, движущихся по единственному пути слева направо, Nmlr;
- количество поездов, движущееся по единственному пути справа налево, Nmrl;
- количество поездов, ждущих входа на единственный путь слева направо, Nwlr;
- количество поездов, ждущих входа на единственный путь справа налево, Nwrl.
Кроме того, при ожидании выполнения условий входа на единственный путь процесс должен находиться в специально созданной для этого очереди. Поэтому в качестве данных в мониторе должны существовать следующие переменные:
R_L_List - очередь, в которой ждут освобождения
единственного пути поезда, движущиеся справа налево;
L_R_List - очередь, в которой ждут освобождения
единственного пути поезда, движущиеся слева направо.
C учетом приведенных выше описаний данных и методов объекта "Монитор" можно представить следующую структуру программы, реализующей задание:
Program Lab1;
Type
PMonitor = ^TMonitor;
TMonitor = Object
Nmlr,
Nmrl,
Nwlr,
Nwrl: Word;
L_R_List,
R_L_List: TList;
Constructor Init;
Destructor Done; Virtual;
Procedure Enter_L_R;
Procedure Enter_R_L;
Procedure Exit_L_R;
Procedure Exit_R_L;
End TMonitor;
--Реализация методов монитора возлагается на учащегося--
Var
Monitor: PMonitor;
Procedure L_R_Train;
Begin
движение до входа в критический участок
Monitor^.Enter_L_R;
движение в критическом участке
Monitor^.Exit_L_R;
движение после выхода из критического участка
самоуничтожение
End L_R_Train;
Procedure R_L_Train;
Begin
движение до входа в критический участок
Monitor^.Enter_R_L;
движение в критическом участке
Monitor^.Exit_R_L;
движение после выхода из критического участка
самоуничтожение
End R_L_Train;
Procedure KeyManager;
Begin
While True Do Begin
If Клавиша нажата Then Begin
Чтение клавиши;
Case Клавиша Of
'Esc': Остановить работу ядра;
'L','l': Создать процесс из процедуры L_R_Train;
'R','r': Создать процесс из процедуры R_L_Train;
Else
End Case;
End If;
End While;
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 блокировки и активизации процессов.
Учащийся по согласованию с преподавателем выбирает для программирования вариант входа в критический участок и выхода из него или создает собственный алгоритм.