4.5. Монитор как средство реализации взаимного исключения

Логика прикладных процессов, а также виды ресурсов и правил доступа к ним безграничны. Поэтому понятие семафора может быть трансформировано в более обобщенный объект. Этот обобщенный объект называется монитором.

После того как мы рассмотрим понятие «монитор», мы увидим, что семафор является частным случаем монитора.

Монитор представляет собой совокупность данных и процедур работы с этими данными.

Процедуры монитора, которые доступны пользователям монитора - процессам, называются внешними.

Монитор по определению представляет собой совокупность данных и процедур работы с этими данными. Причем, в качестве данных монитора могут выступать и очереди процессов.

Процессы не имеют непосредственного доступа к данным, а только через внешние процедуры монитора.

Процедуры монитора содержат операции, позволяющие на основе анализа данных монитора, ставить процессы в очереди и активизировать их.

Алгоритмы анализа данных зависят от содержательной стороны задачи.

Процедуры монитора выполняются в режиме взаимного исключения. Причем, вопрос реализации взаимного исключения – это вторичный вопрос. Вопрос реализации самого монитора тоже является вторичным вопросом.

Свойства монитора, перечисленные выше, могут быть реализованы как в модуле, так и в объекте. Шаблон модуля, который может рассматриваться как монитор, представлен ниже.

Class Monitor

{

//методы, доступные пользователю

void M1(); //точки входа в монитор

void M2();

Monitor();

~Monitor();

//данные и методы, не доступные пользователю

void DisableInterrupt();

void EnableInterrupt();

}

void Monitor::DisableInterrupt() //внутренние процедуры монитора

{

cli;

}

void Monitor::EnableInterrupt()

{

sti;

}

//внутренних процедур может быть сколько угодно

void Monitor::M1() //процедура, связанная с входом в критический участок

{

DisableInterrupt();

...

EnableInterrupt();

}

void Monitor::M2() //процедура, связанная с выходом из критического участка

{

DisableInterrupt();

...

EnableInterrupt();

}

Использование монитора выглядит следующим образом:

Monitor M;

void P1()

{

while (1) {

...

M.M1();

Критический участок;

M.M2();

...

}

}

void P2()

{

while (1) {

...

M.M1();

Критический участок;

M.M2();

...

}

}

int main()

{

создать процесс из процедуры P1();

создать процесс из процедуры P2();

}

Процедура М1 монитора, анализируя данные, выполняет следующие действия:

1. Проверяет условия входа в критический участок; при выполнении этих условий процесс, вызвавший процедуру М1, продолжает выполняться, войдя в критический участок; при невыполнении - процесс блокируется в очереди монитора;

2. Устанавливает необходимые значения данных монитора при блокировании процесса и при продолжении выполнения в критическом участке.

Процедура М2 монитора выполняет следующие действия:

1. Устанавливает необходимые значения данных монитора при выходе из критического участка;

2. Проверяет условия возможной активизации ждущих процессов и активизирует их при выполнении этих условий.

Количество различающихся процедур входа в критический участок и методов выхода из него определяется количеством разновидностей процессов в каждой прикладной задаче.

Как видно из приведенного описания, семафоры можно рассматривать как монитор с конкретным алгоритмом функционирования.

Реальным примером монитора служат библиотечные модули Модулы-2, которым присвоен приоритет. В Модуле-2 существуют два вида модулей - программные и библиотечные.

Структура программы на Модуле-2 выглядит следующим образом.

MODULE Name;

IMPORT LIB_MODULE;

...

BEGIN

...

END Name.

Библиотечный модуль имеет следующее описание.

DEFINITION MODULE LIB_MODULE; {модуль определений}

Procedure M1;

Procedure M2;

END LIB_MODULE.

IMPLEMENTATION MODULE LIB_MODULE; {модуль реализации}

{реализация всех процедур модуля}

END LIB_MODULE.

Есть и другие тонкости модульного принципа построения программ на Модуле-2, в частности - локальные модули, описанные внутри других модулей, но они не имеют прямого отношения к рассматриваемым вопросам.

Важно, что с библиотечным модулем можно связать ПРИОРИТЕТ. Это делается следующим образом.

IMPLEMENTATION MODULE LIB_MODULE[Pr];

За именем модуля в модуле реализации в квадратных скобках может стоять число. Это число определяет приоритет модуля. Интерпретация приоритета зависит от системы.

По правилам Модулы-2, если модуль имеет приоритет, то модуль является монитором и его процедуры выполняются в режиме взаимного исключения, т. е. одновременно может выполняться только одна процедура монитора.

Это достигается включением инструкций запрета и разрешения прерываний на входе и выходе внешних процедур монитора самим компилятором. Это большое достоинство системы Модула-2, что пользователь не манипулирует низкоуровневыми инструкциями, а использует понятие приоритет для построения монитора.

В системе Модула-2 приоритет модуля трактуется компилятором как маска прерываний. Т. е., если приоритет 1, то маскируется первый вход контроллера прерываний - вход от таймера, если приоритет 2, то маскируются прерывания от клавиатуры, если приоритет 3, то т. к. в двоичном виде это число 11, то маскируются как прерывания от таймера, так и от клавиатуры. Т.е. используется по возможности более тонкий вариант, чем просто запрет прерываний.

Существует большое количество прикладных задач, которые могут быть решены с помощью мониторов. Решение некоторого набора таких задач является предметом лабораторных работ по дисциплине «Системы реального времени».

Указанные задачи относятся к задачам двух типов:

1. Задачи, которые по своей физической природе относятся к программированию параллельных процессов, что соответствует содержанию данной дисциплины;

2. Задачи, которые моделируют параллельными вычислительными процессами некоторые реальные ситуации, что соответствует названию дисциплины "Системы реального времени.

К первому классу задач относятся:

1. Задача назначения однородных ресурсов;

2. Задача с процессами «читателями» и «писателями».

Ко второму классу задач относятся:

1. Модель железнодорожного перегона;

2. Модель обедающих философов.

Здесь мы рассмотрим задачи первого класса, иллюстрирующие более сложные условия блокировки и активизации процессов, чем в семафорах. Цель рассмотрения - показать, как ставятся подобные задачи, и каковы подходы к их решению.

Задача с процессами «читателями» и «писателями»

Здесь есть два типа процессов с разными правами доступа к ресурсу.

Есть некоторый ресурс, например, файл. Есть несколько процессов-читателей, которые могут только читать содержимое файла, и есть несколько процессов-писателей, которые могут модифицировать содержимое файла.

В любой момент с файлом может работать или один писатель или любое количество читателей.

По количеству типов процессов - два, монитор имеет две процедуры доступа к файлу и две процедуры освобождения файла.

Class TMonitor {

int Nr; //количество читателей, работающих с файлом

int Nw; //количество писателей, работающих с файлом

TList* RList; // Список читателей, ждущих чтения файла

TList* WList; // Список писателей, ждущих редактирования файла

TMonitor();

~TMonitor();

void Enter_R();

void Enter_W();

void Exit_R();

void Exit_W();

}

void Reader() void Writer()

{ {

while (1) { while (1) {

... ...

M->Enter_R(); M->Enter_W();

... ...

M->Exit_R(); M->Exit_W();

... ...

} }

} }

Требуется формализовать условия доступа к файлу читателя и писателя и правила активизации процессов при освобождении файла.

Условие доступа к файлу писателя:

Если файл занят писателем или читателями, то блокировка;

Данное условие формализуется следующим образом:

if ((Nw > 0) || (Nr > 0)) { ... .

Условие доступа к файлу читателя:

Если файл занят писателем, то {читателей может быть несколько} блокировка;

Данное условие формализуется следующим образом:

if (Nw > 0) { ... .

Предположим, что читатели захватили файл. Добавление других читателей возможно, если файл захвачен читателями. Поэтому появляется опасность, что писатель бесконечно долго будет ждать доступа к файлу, если к нему будут все время обращаться читатели.

Ограничить доступ читателей к файлу можно, усложнив условие доступа:

Если файл занят писателем ИЛИ есть писатели в очереди, то блокировка;

Выходы из критического участка для читателя и писателя выглядят следующим образом.

Читатель:

Если нет читателей, работающих с файлом, И есть писатель в очереди, то активизация писателя;

Писатель:

Как быть писателю, если есть и писатели, и читатели в очередях. Интуитивно кажется, что у писателя должен быть приоритет перед читателями. Поэтому писатель должен активизировать писателя же. Однако в этом случае появляется опасность бесконечного ожидания читателей. Поэтому лучше, если писатель будет активизировать читателей, а если их нет в очереди, то можно активизировать писателя.

Возможен вариант реализации монитора с одной очередью. Если первым в очереди стоит писатель, то активизируется он. Если читатель, то активизируются все читатели до первого писателя. В дескрипторах должна быть раскраска процессов на читателей и писателей.

Этот пример также иллюстрирует возможности попадания процессов в режим бесконечного ожидания при неудачном выборе алгоритмов входа в критический участок и выхода из него.

Ниже представлен вариант монитора «Читатели - писатели», реализованный на условных переменных в сопоставлении с рассмотренным вариантом монитора.

TProcess curproc; TList ReadyList; void swt(TProcess from,TProcess to); int ar; int aw; TList WList; TList RList; void reader_enter() { запрет_прерываний(); TProcess oldproc; if (aw > 0) { oldproc = curproc; RList.insert(oldproc); curproc = ReadyList.at(0); ReadyList.remove(curproc); swt(oldproc,curproc); } ar++; разрешение_прерываний(); } void reader_exit() { запрет_прерываний(); TProcess oldproc; ar--; if (ar == 0) { if (WList.getCount() > 0) { oldproc = curproc; ReadyList.insert(oldproc); curproc = WList.at(0); WList.remove(curproc); swt(oldproc,curproc); } } разрешение_прерываний(); } void writer_enter() { запрет_прерываний(); TProcess oldproc; if (aw > 0)||(ar > 0) { oldproc = curproc; WList.insert(oldproc); curproc = ReadyList.at(0); ReadyList.remove(curproc); swt(oldproc,curproc); } aw++; разрешение_прерываний(); } void writer_exit() { запрет_прерываний(); TProcess oldproc; aw--; if (RList.getCount() > 0) { while (RList.getCount() > 0) { oldproc = RList.at(0); Rlist.remove(oldproc); ReadyList.insert(oldproc); } }else{ if (WList.getCount() > 0) { oldproc = curproc; ReadyList.insert(oldproc); curproc = WList.at(0); WList.remove(curproc); swt(oldproc,curproc); } } разрешение_прерываний(); }

Монитор «Читатели – Редакторы» int ar; int aw; int wr; int ww; TCondVar ReadCondVar; TCondVar WriteCondVar; Tmutex mutex; void reader_enter() { mutex.lock(); while (aw > 0) wr++; ReadCondVar.wait(mutex); wr--; } ar++; mutex.unlock(); } void reader_exit() { mutex.lock(); ar--; if (ar == 0) { if (ww > 0) { WriteCondVar.signal(); } } mutex.unlock(); } void writer_enter() { mutex.lock(); while ((aw > 0)||(ar > 0)) { ww++; WriteCondVar.wait(mutex); ww--; } aw++; mutex.unlock(); } void writer_exit() { mutex.lock(); aw--; if (wr > 0) { ReadCondVar.signalAll(); }else{ if (ww > 0) { WriteCondVar.signal(); } } mutex.unlock(); }

Задача назначения однородных ресурсов

Задача назначения однородных ресурсов формулируется следующим образом.

Имеется N единиц ресурса и М процессов.

Каждый из процессов может запросить любое количество R ресурса от 1 до N единиц.

Если нужное количество R ресурса имеется, то оно предоставляется процессу, а количество свободных ресурсов уменьшается на величину R.

Если требуемого количества свободных ресурсов нет в наличие, то процесс блокируется до их появления.

Освобождая ресурсы, процесс возвращает их в число свободных ресурсов и активизирует процессы, которые стоят в очереди и которым хватает свободных ресурсов.

Считается, что все процессы равноправны.

Посмотрим, как может выглядеть монитор в этом случае. Опишем его в условной объектно-ориентированной структуре.

class TMonitor {

int N; //общее количество единиц ресурсов

int Nf; //текущее количество свободных ресурсов

TList* List; //очередь, в которой процессы ждут ресурсы

TMonitor(int AN);

~TMonitor();

void Request(int R);

void Release();

}

Отметим, что для решения данной задачи в дескрипторе процесса следует выделить поле, в котором будет храниться количество запрашиваемых (когда процесс ждет) и используемых (когда процесс получил и выполняется) ресурсов.

Использование монитора внешне выглядит следующим образом:

TMonitor* M;

int main()

{

M = new TMonitor(10);

...

delete M;

End.

void Proc1()

{

while (1) {

...

M->Request(R); //случайное число от 1 до N

...

M->Release();

...

}

}

Раскроем содержание методов монитора.

TMonitor::TMonitor(int AN)

{

N = AN;

Nf = N;

List = new TList();

}

TMonitor::~ TMonitor()

{

delete List;

}

void TMonitor::Request(int R)

{

Запрет_прерываний;

Записать в дескриптор процесса значение R;

if (R > Nf) {

List->Insert(Текущий_процесс);

ПЕРЕНАЗНАЧИТЬ_ПРОЦЕССОР;

}

Nf = Nf - R;

Разрешение_прерываний;

}

Условие предоставления ресурсов процессу мы записали следующим образом:

Если количество свободных ресурсов больше или равно количеству запрашиваемых ресурсов, то процесс захватывает требуемое количество ресурсов и продолжает выполняться;

Если количество свободных ресурсов меньше, чем количество запрашиваемых ресурсов, процесс блокируется в очереди монитора.

Вроде бы все логично, но может иметь место, например, следующая ситуация. Предположим, что есть процесс, стоящий в очереди, которому требуется большое количество ресурсов, а свободных ресурсов все время оказывается меньше, чем требуемое. При этом свободные ресурсы все время занимаются и освобождаются процессами, которым требуется малое количество ресурсов.

Это приводит к тому, что процесс, запрашивающий большое количество ресурсов, может оказаться в состоянии «бесконечного ожидания». Это серьезный недостаток алгоритма монитора.

Как устранить этот недостаток?

Например, усложнить условие блокировки процесса, добавив в него следующее:

if ((R > Nf) || (Есть процессы в очереди монитора)) {

...

}

В этом случае, процессы, требующие малого количества ресурсов, не смогут получать их в обход процесса, требующего большого количества ресурсов.

Хотя процессы, требующие малого количества ресурсов, будут нести непроизводительные потери, т.к. будут ситуации, когда свободных ресурсов достаточно, но они не будут выделяться, т.к. есть процессы в очереди монитора.

Аналогичные ситуации могут иметь место при освобождении ресурсов.

Запишем вариант метода TMonitor::Release().

void TMonitor::Release()

{

Запрет_прерываний;

Nf = Nf + R;

Перевести в очередь готовых все процессы, для которых сумма

требуемых ресурсов меньше или равна сумме свободных

ресурсов, не зависимо от их места в очереди;

Разрешение_прерываний;

}

В этом случае, если в начале очереди находится процесс, ждущий большого количества ресурсов, он также может не активизироваться бесконечно долго.

Чтобы устранить указанный недостаток, можно правило активизации процессов записать следующим образом:

while (очередь не пустая) {

if (первому в очереди процессу хватит свободных ресурсов)

{

перевести этот процесс в очередь готовых процессов;

}else{

break;

}

}

Т.е. активизацию в любом случае следует начинать с первого процесса.

Данный пример показывает характер проблем, возникающих при доступе процессов к ресурсам, и способов их устранения. Важной проблемой является опасность оказаться в режиме бесконечного ожидания некоторыми процессами в очередях монитора. Бесконечное ожидание устраняется использованием подходящих алгоритмов активизации, может быть даже путем отказа от лежащих на поверхности преимуществ.

Ниже представлен вариант реализации монитора «Назначение однородных ресурсов» на условных переменных в сопоставлении с рассмотренным вариантом.

int n; TList list; void request(int R) { запрет_прерываний(); TProcess oldproc; if (R > n) { oldproc = curproc; oldproc.R = R; list.insert(oldproc); curproc = ReadyList.at(0); ReadyList.remove(curproc); swt(oldproc,curproc); } n = n – R; разрешение_прерываний(); } void release() { запрет_прерываний(); TProcess tmpproc; n = n + curproc.R; int tmpn = n; while (list.getCount() > 0) { tmpproc = list.at(0); if (tmpproc.R <= tmpn) { list.remove(tmpproc); tmpn = tmpn – tmpproc.R; ReadyList.insert(tmpproc); }else{ break; } } разрешение_прерываний(); }

Монитор «Назначение однородных ресурсов» Количество процессов N; typedef struct { int R; int p; }TRes; int n; Tmutex mutex; TCondVar condvar[N]; TList <TRes> list; void request(int R, int p) { mutex.lock(); TRes res; while (R > n) { res.R = R; res.p = p; list.insert(res); condvar[p].wait(mutex); } n = n – R; mutex.unlock(); } void release(int R) { mutex.lock(); n = n + R; int tmpn = n; while (list.getCount() > 0) { TRes res = list.at(0); if (res.R <= tmpn) { list.remove(res); tmpn = tmpn – res.R; condvar[res.p].signal(); }else{ break; } } mutex.unlock(); }