Ресурс – это абстрактная структура, имеющая множество атрибутов, характеризующих способы доступа к ресурсу и его физическое представление в системе 4 страница

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

Очереди сообщений являются более удобным средством обмена сообщениями, чем конвейеры, но имеют более сложную реализацию. Они предоставляют возможность использовать несколько дисциплин работы с сообщениями: FIFO, LIFO, приоритетный доступ и произвольный доступ.

Второй особенностью очереди сообщений является сохранение в ней прочитанных записей, в то время как из конвейера они удаляются. Третьей особенностью очереди является присутствие в очереди не сообщений, а их адреса в памяти и размер. Эти данные хранятся в области памяти, которая является общей для процессов, обменивающихся сообщениями. Каждый процесс, пользующийся очередью должен получить доступ к общему разделу памяти через системные запросы API, т.к. очередь – это системный механизм.

Контрольные вопросы

Что такое мультипрограммный и мультизадачный режимы работы операционной системы?

Что такое дескриптор процесса? Какова его роль при прерывании процесса?

В каких состояниях могут находиться процессы в операционной системе?

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

Что такое планирование и диспетчеризация процессов?

Что такое стратегия планирования? На каких принципах она основана?

Что означает термин "Задача переднего плана"?

Что такое бесприоритетные дисциплины обслуживания? Какие они бывают?

Поясните линейные дисциплины обслуживания.

Поясните циклические дисциплины обслуживания.

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

Что такое дисциплины с фиксированным приоритетом?

Что такое дисциплины с динамическим приоритетом?

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

Что такое вытесняющие и невытесняющие дисциплины обслуживания?

Что такое дисциплины SJN и SRT?

Что такое карусельная дисциплина обслуживания? Как она реализуется?

Чем отличается планирование процессов от диспетчеризации?

Какими способами обеспечивается гарантированное обслуживание процесса?

4. ПРОБЛЕМА ТУПИКОВ И ЕЁ РЕШЕНИЕ

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

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

При рассмотрении проблемы разделяемые ресурсы делятся на два класса:

повторно используемые (RR) ресурсы, они же системные ресурсы (SR);

потребляемые (они же расходуемые) ресурсы (CR).

Системные ресурсы SR представляют собой множество идентичных единиц некоторого вида ресурсов. Это множество единиц конечно и неизменно в операционной системе. Каждая единица ресурса либо доступна, либо выделена какому-либо процессу. Никакой процесс не может влиять на ресурс (или на его единицу), который ему не принадлежит. К системным ресурсам относятся основная и внешняя память, периферийные устройства, иногда процессоры, программное обеспечение, файлы данных, таблицы и разрешение войти в критическую секцию.

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

Для исследования параллельных процессов в целях предотвращения и обнаружения тупиков разработано несколько моделей параллельных процессов. К ним относятся:

модель повторно используемых ресурсов Хольта;

сети Петри;

модель пространства состояний системы.

4.2. Модель повторно используемых ресурсов Холта [7]

Модель Холта представляет собой граф состояний ресурсов и процессов, имеющий вершины двух типов и направленные дуги (стрелки), показывающие запрос и выделение ресурса процессу. Вершинами графа являются процессы и ресурсы. Процессы обозначаются прямоугольниками (квадратами), а ресурсы – кружками. Число точек в кружке показывает количество единиц ресурса. Условные обозначения модели Хольта приведены в табл. 4.1. Пример модели Хольта [1] для двух процессов, в которой возможен тупик, показан на рис. 4.1. На модели показано ситуация, в которой процесс ПР1 запрашивает две единицы ресурса R1 и одну единицу ресурса R2. В то же время процесс ПР2 уже захватил две единицы ресурса R1 и запросил единственную единицу ресурса R2. На долю процесса ПР1 осталась только одна единица ресурса R1 и процесс может перейти в режим ожидания.

Таблица 4.1. Условные обозначения модели Холта

Обозначение	Смысл обозначения
ПР	Процесс ПР
	Ресурс R с четырьмя единицами
	Запрос единицы ресурса
	Выделение единицы ресурса

Рис. 4.1. Пример модели Холта с тупиком

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

При обмене процессами сообщениями через почтовые ящики по кольцевой схеме (рис. 4.2) возможно возникновение тупика. Процессы ПР1, Пр2, Пр3 создают сообщения М1, М2 и М3 соответственно. Посылка сообщения является запросом разделяемого ресурса типа CR, приём сообщения – освобождением запрошенного ресурса. Следует помнить, что процесс может послать сообщение только в почтовый ящик при наличии свободного гнезда.

Рис. 4.2. Кольцевая схема обмена сообщениями через почтовые ящики

Взаимодействие процессов осуществляется посредством получения сообщений от предшествующего процесса и посылкой сообщения последующему. Текст программы, обеспечивающей отсутствие тупика, приведён на рис. 4.3.

...
Parbegin
ПР1:	Начало описания процесса ПР1
SAND_MASSAGE(ПР2, М1, ПЯ2);	Посылка сообщения процессу ПР2
WAIT_MASSAGE(ПР3, М3, ПЯ1);	Ожидание сообщения от процесса ПР3
...
ПР2:	Начало описания процесса ПР2
SAND_MASSAGE(ПР3, М2, ПЯ3);	Посылка сообщения процессу ПР3
WAIT_MASSAGE(ПР1, М1, ПЯ2);	Ожидание сообщения от процесса ПР1
...
ПР3:	Начало описания процесса ПР3
SAND_MASSAGE(ПР1, М3, ПЯ1);	Посылка сообщения процессу ПР1
WAIT_MASSAGE(ПР2, М2, ПЯ3);	Ожидание сообщения от процесса ПР2
...
Parend

Рис. 4.3. Текст программы при кольцевой схеме обмена сообщениями

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

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

Примером другого тупика являетс тупик на ресурсах CR и SR. Два процесса ПР1 и ПР2 запрашивают у ресурса R1, имеющего тип CR, три и две единицы соответственно, а ресурс их имеет только четыре. Процессы обмениваются сообщениями, которые являются системными ресурсами SR и проходят через почтовый ящик ПЯ.

Рис. 4.4. Модель Холта, иллюстрирующая тупик

Процесс ПР1 использует ресурс для своей работы, а ПР2 – только на время обработки сообщения. Модель Хольта для такого взаимодействия процессов показана на рис. 4.4, текст программы, реализующей взаимодей­ствие процессов процессы с помощью мониторов, приведён на рис. 4.5.

Мониторы реализованы с помощью операторов REQUEST (запрос ресурса) и RELEASE (освобождение ресурса). Первый процесс захватывает ресурс R1 в самом начале работы и освобождает в конце. Второй ресурс ждёт прихода сообщения от процесса ПР1, затем запрашивает ресурс R1, затем обрабатывает сообщение и только после этого освобождает ресурс.

...
Parbegin
ПР1:	Начало описания процесса ПР1
REQUEST(R1,3);	Запрос 3-х единиц ресурса R1
...
SAND_MASSAGE(ПР2, М1, ПЯ);	Посылка сообщения М1 процессу ПР2
WAIT_ANSWER(М2, ПЯ);	Ожидание ответа М2 от процесса ПР2
...
RELEASE(R1,3);	Освобождение 3-х единиц ресурса R1
ПР2:	Начало описания процесса ПР2
...
WAIT_MASSAGE(ПР1, М1, ПЯ2);	Ожидание сообщения от процесса ПР1
REQUEST(R1,2);	Запрос 3-х единиц ресурса R1
...;	Обработка сообщения
RELEASE(R1,2);	Освобождение 3-х единиц ресурса R1
SAND_ANSWER(М1, ПЯ);	Посылка ответа процессу ПР1
...
Parend

Рис. 4.5. Текст программы при кольцевой схеме обмена сообщениями

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

Возникновение тупика возможно и на ресурсах системных ресурсах типа SR. Пусть два процесса ПР1 и ПР2 обращаются к ресурсам R1 и R2. Взаимное исключение доступов к ресурсам реализуется на семафорах S1 и S2. Работа процессов с семафорами показана на рис. 4.6, граф Хольта – на рис. 4.5, анализ состояний с помощью пространства состояний – на рис. 4.7.

...
Parbegin
ПР1:	Начало описания процесса ПР1	ПР2:	Начало описания процесса ПР1
...		...
1: P(S2);	Закрытие S2	5: P(S1);	Закрытие S1
...		...
2: P(S1);	Закрытие S1	6: P(S2);	Закрытие S2
...		...
3: V(S1);	Открытие S1	7: V(S1);	Открытие S2
...		...
4: V(S2);	Открытие S2	8: V(S2);	Открытие S1
...		...
		Parend

Рис. 4.6. Управление семафорами в примере тупика на системных ресурсах SR

На рис. 4.6 метками 1 – 4 показаны номера операторов процесса ПР1, а метками 4 – 8 – номера операторов процесса ПР2. На рис. 4.7 стрелки, направленные к ресурсам показывают запрос ресурса, а направленные от ресурсов – захват ресурсов. Из рис. 4.7. видно, что возможно возникновение тупиков, т.к. процессы могут одновременно запросить одни и те же ресурсы. Всё зависит от последовательности работы семафоров во времени.

Рис. 4.7. Граф модели Холта для примера тупика на ресурсах SR

ПР2               ПР1   Рис. 4.8. Пространство состояний процессов ПР1 и ПР2

На рис. 4.8 пунктирные линии 1 – 4 и 5 – 8 соответствуют операторам процессов ПР1 и ПР2 соответственно. Изменение состояний процессов показано жирными направленными линиями Т1 и Т2. Эти линии называются траекториями. Пересечение пунктирных линий траекториям показывает моменты выполнения операторов. В исходных состояниях обе траектории начинаются из прямоугольника, находящегося в нижнем левом углу системы координат, т.е. ни один из операторов не выполнен.

Траектория Т1 безопасна, т.е. к моменту запроса процессом ПР2 ресурсов R1 (точка В) оба ресурса захвачены процессом ПР1, и процесс ПР2 окажется в режиме ожидания (поэтому траектория Т1 не пересекает линию 5). Пересечение траекторией Т1 линии 3 показывает освобождение ресурса S1, и процесс ПР2 выполняется до оператора 6, однако, в точке С процесс ПР2 опять заблокирован, потому что ещё не освобождён ресурс R2. После выполнения оператора 4 процесс ПР2 окончательно деблокируется, и процесс ПР2 выполняется до конца, освобождая ресурсы R1 и R2.

Траектория Т2 приводит к тупику. В точке Х процессы ПР1 и ПР2 благополучно захватили ресурсы R2 и R1 соответственно, а в точке Y они обратились к уже захваченным ресурсам, процессы заблокировали друг друга.

Тупики возможны, если на графах модели Холта присутствуют обращения двух и более процессов к одним и тем же ресурсам. Тогда ответ на вопрос "Возникнет ли тупик" даст анализ траекторий процессов в пространстве их состояний.

В [1] отмечено, что для появления тупиков должны одновременно выполняться четыре условия:

· взаимное исключение не запрещает монопольный доступ к разделяемым ресурсам (условие взаимного исключения);

· удержание процессом захваченного ресурса на время ожидания доступа к недостающим для продолжения его работы разделяемым ресурсам (условие ожидания);

· невозможность перераспределения ресурсов, захваченных процессами находящимися в режиме ожидания (условие отсутствия перераспределения);

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

4.3. Сети Петри

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

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

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

Кроме вершин и дуг сети Петри содержат еще один объект – фишки (метки) позиций. Переход считается активным, если в каждой его входной позиции находится хотя бы одна фишка. Расположение фишек называется разметкой сети. Пример изображения сети Петри при двух разметках приведен на рис. 4.9.

а)	б)
Рис. 4.9. Пример изображения сети Петри при двух разметках

В аналитической форме сеть Петри представляется в виде 5 компонент:

P = (B, D, I, O, M),

где	B	– конечное непустое множество позиций,
	D	– конечное непустое множество переходов,
	I	– входная функция, задающая для каждого перехода множество его входных позиций,
	O	– выходная функция, задающая для каждого перехода множество его входных позиций,
	M	– разметка сети.

Компоненты B и D являются перечнями вершин-позиций и вершин переходов, в которых обозначения вершин разделены запятыми. Для рис. 4.9 эти компоненты имеют вид: b1,b2,b3,b4,b5 и d1,d2,d3,d4.

Входные и выходные функции являются матрицами, в которых столбцы соответствуют переходам, а строки – позициям. В матрицах I и О элементы, находящиеся на пересечении столбцов, соответствующих переходам, и строк, соответствующих входным вершинам-позициям перехода, равны единице, в противном случае – нулю. Для рис. 4.9 эти матрицы показаны на рис. 4.10, а,б.

Разметка сети для рис. 4.9,а описывается последовательностью чисел (1,0,0,0,1), а для рис. 4.9,б – последовательностью (0,1,1,0,1). Единицы показывают наличие фишек в вершинах-позициях, а нули – их отсутствие. На рис. 4.9,а активен только переход d2, т.к. он имеет только одну входную вершину b1, в которой находится фишка. Переход d3 пассивен, т.к. он имеет две входных вершины и только в одной из них находится фишка. Осуществление события d2 сделало активным переход d1 и d3, т.к. фишка из вершины b1 перешла в вершины b2и b3. Смена разметки из М₀ в М₁ обозначается следующим образом:

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

Правило изменения разметки: При срабатывании перехода фишки изымаются по одной из всех входных позиций и добавляются по одной в каждую выходную позицию.

d1 d2 d3 d4 b1         b2         b3         b4         b5         Fа)	d1 d2 d3 d4 b1         b2         b3         b4         b5         б)
Рис. 4.10. Входная (а) и выходная (б) функции для сети Петри (для рис. 4.9).

При анализе сети Петри исследования ведутся, как правило, в трех направлениях:

исследование достижимости конкретной разметки М₁ при наличии некоторой стартовой разметки М₀ (т.е. исследование возможности достижения конкретного состояния системы при определенных начальных условиях);

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

исследование безопасности сети – выявление невозможности появления в любой позиции более одной фишки (т.е. возможность работы сети в стационарном режиме).

Основным недостатком сетей Петри является невозможность моделиро­вать временные характеристики объектов.

Ниже приведены примеры исследования параллельных процессов с помощью сетей Петри. Первый пример описан в разделе 4.2 (рис. 4.4, 4.5). Для удобства изучения материала рисунки примера повторены ниже (рис. 4.11).

Рис. 4.11. Граф модели Холта	Рис. 4.13. Сеть Петри для первого примера
...
Parbegin
ПР1:
1: REQUEST(R1,3);
...
2: SAND_MASSAGE(ПР2, М1, ПЯ);
3: WAIT_ANSWER(М2, ПЯ);
...
4: RELEASE(R1,3);
ПР2:
...
5: WAIT_MASSAGE(ПР1, М1, ПЯ2);
6: REQUEST(R1,2);
...;
7: RELEASE(R1,2);
8: SAND_ANSWER(М1, ПЯ);
...
Parend Рис. 4.12. Код программы процессов

Позиция Р₁ соответствует началу процесса ПР1, а Р₉ – началу процесса ПР2. Позиция Р₂ соответствует выполнению оператора 1 и получению процессом 3-х единиц ресурса R, который изображает позиция Р₆. Прохождение перехода t₂ соответствует выполнению оператора 2, т.е. посылке сообщения процессу ПР2. Позиция Р3 соответствует ситуации "выполнен оператор 2". Процесс остановлен до получения сообщения от процесса ПР2. Если это сообщение придёт, то процесс продолжится, выполнится оператор 4 и процесс ПР1 освободит ресурс R (переход t₄). Однако процесс ПР2 ожидает сообщения от ПР1. Сообщение вызовет прохождение через переход t₅ в позицию Р₁₀. В ней процесс остановится, т.к. у ресурса R свободна только одна единица, а нужно две. Процесс ПР2 остановлен и не может послать сообщение процессу ПР1, а тот, в свою очередь, не получив сообщение, не может освободить ресурс R. Возник тупик.

Второй пример, иллюстрировавший возникновение тупика на ресурсах SR также рассматривался разделе 4.2 (рис. 4.6 и 4.7). Исследование возникновения тупика проиллюстрировано на рис. 4.14 – 4.15.

Рис. 4.14. Граф модели Холта	Р3 Рис. 4.16. Сеть Петри для первого примера
...
Parbegin
Parbegin
ПР1:
1: P(S2);...
2: P(S1);...
3: V(S1);...
4: V(S2);...
ПР2:
5: P(S1);...
6: P(S2);...
7: V(S1);...
8: V(S2);...
Parend   Рис. 4.15. Код программы процессов

На рис. 4.16 номера переходов соответствуют номерам отмеченных операторов управления семафорами, позиции Р₁ и Р₂ – семафорам S₁ и S₂. Из него видно, при прохождении перехода t₁ процесс ПР1 захватывает ресурс Р₂, а процесс ПР2 при прохождении перехода t₅ захватывает ресурс Р₁. Дальнейшие попытки выполнить переходы t₂ и t₆ переводят процессы в состояние ожидания, поэтому t₃, t₄, t₇ и t₈ никогда не будут выполнены.

Сети с выполняющимися переходами называются живыми. С этой точки зрения сети, показанные на рис. 4.13 и 4.16 не являются живыми.

Графическое представление сетей Петри позволяет придать наглядность процессу исследования процессов на возникновение тупиков. Применение математического описания сети Петри позволяет автоматизировать процесс исследования. Можно считать также перспективной автоматизацию процесса исследования на основе математического описания сети Петри с визуализацией процесса исследования посредством графического представления сети.

4.4. Модель пространства состояний системы

В этой модели состояние операционной системы характеризуется состоянием её различных ресурсов (свободны или выделены конкретным процессам). Процессы изменяют состояние системы посредством запросов ресурсов, их захвата и освобождения. Это приводит к двум формальным определениям:

система описывается парой <σ,π>,

где σ – множество состояний системы {S₁,S₂, …, S_n};