Функції, їхні властивості і графіки. 1 страница

В [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};

π – множество процессов {Р₁,Р₂, …, Р_k};

при выполнении процесса Р_i система переходит в непустое подмножество своих состояний, что обозначается следующим образом: Р_i: σ→{σ}.

Если процесс P_i определён на состоянии S_j, т.е. может вывести систему из этого состояния каким-либо способом, то область его значений обозначается как Р_i(S_j) и равна {S_m,S_n, …, S_q}, т.е. подмножеству состояний системы. Если процесс Р_i никак не может вывести систему из состояния S_j, то Р_i(S_j)=0.

При описании переходов системы из одного состояния в другое применяются обозначения, приведенные в табл. 4.2.

Таблица 4.2. Условные обозначения в модели пространства состояний системы

Обозначение	Смысловое содержание
	Процесс Pi может перевести систему из состояния Se в состояние Sk
	Переход системы из состояния Se в состояние Sk конечным множеством последовательно выполняющихся процессов.

Справедливы следующие суждения:

система может быть переведена из состояния S_e в состояние S_w посредством n ≥ 0 операций m ≥ 0 процессами;

если процесс заблокирован в состоянии S_e, т.е. не может ни требовать, ни получать, ни освобождать ресурсы, то не существует ни одного состояния S_k, в которое система может быть переведена процессом P_i, и P_i(S_e) = 0;

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

В [1] рассмотрен следующий пример. Система <σ,π> определена следующим образом:

σ = {S₁,S₂, S₃, S₄}; π = {Р₁,Р₂, …, Р_k};

Р₁(S₁)={S₂,S₃}; (1) Р₂(S₁)={S₃}; (2)

Р₁(S₂)=0; (3) Р₂(S₂)={S₁,S₄}; (4)

Р₁(S₃)={S₄}; (5) Р₂(S₃)=0; (6)

Р₁(S₄)={S₃}; (7) Р₂(S₄)=0. (8)

Диаграмма переходов такой системы показана на рис. 4.17. В соответствии с (1) из состояния S₁ выходят две дуги процесса Р₁ в состояния S₂ и S₃. Выражение (2) изображается дугой P₂, выходящей из S₁ и входящей в S₂, выражению (3) соответствует отсутствие дуг процесса Р1, входящих из S₂. Согласно (4) дуги процесса Р₂ соединяют вершину S₂ с S₁ и S₄. В соответствии с (5) и (7) две дуги процесса Р1 соединяют S₃ и S­₄, образуя замкнутый контур, и, наконец, (6) и (8) указывают на отсутствие дуг процесса Р₂, выходящих из S₃ и S₄.

Рис. 4.17. Диаграмма переходов системы к примеру

Из рис. 4.17 следует, что для процесса Р2 существуют тупики в вершинах S₃ и S₄. Состояние S называется тупиковым, если существует процесс, находящийся в тупике в этой вершине. Состояние S называется опасным, если система может перейти из неё посредством конечной цепочки процессов в тупиковое состояние.

4.5. Борьба с тупиками

Существует три основных стратегии борьбы с тупиками:

предотвращение тупиков;

обход тупиков;

распознавание тупика с последующим восстановлением.

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

4.5.1. Предотвращение тупиков

Предотвратить тупик можно посредством нарушения условий его возникновения (раздел 4.2): условия взаимного исключения, условия ожидания, условие отсутствия перераспределения и условия кругового ожидания.

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

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

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

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

В целом стратегия предотвращения тупиков является дорогой и используется нечасто [1].

4.5.2. Обход тупиков

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

Пример такого анализа приведён в табл. 4.3. В текущий момент времени процессу Р1 выделено три единицы ресурса R, а процессу Р2 – 2 единицы. В этот же момент процессом Р1 запрошена 1 единица, а процессом Р2 – 2 единицы. Полная потребность процессов Р1 и Р2 – 5 и 4 единицы соответственно.

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

Таблица 1. Анализ возможности возникновения тупика в текущий момент времени

Процесс	Выделено единиц R	Запрошено единиц R	Предельная потребность единиц R	Можно запросить ещё единиц R	Всего в системе единиц R
Р1
Р2

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

Классическое решение проблемы обхода тупика предложил Дейкстра. Его алгоритм называется алгоритмом банкира. Он похож на алгоритм принятия банком решения о возможности выдачи кредита заёмщику без ущерба для своей безопасности (рис. 4.18).

Рис. 4.18. Р-граф алгоритма банкира

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

Вс_Р – общее количество единиц ресурса, которые может предоставить операционная система;

Св_Р – число свободных единиц ресурса;

Прод – флаг, указывающий на необходимость продолжения анализа;

Пол – массив, хранящий количества единиц ресурса, полученных процессами;

Max – максимальные количества единиц, которые вообще могут быть затребованы процесами;

ОСТ – количества единиц ресурса, которые могут быть ещё затребованы процессами;

Зав – признаки завершения процессов.

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

· количество свободных единиц ресурса Св_Р;

· количества единиц ресурса, которые ещё могут быть затребованы процессами;

· признаки завершения процесса (присваивается значение False для подготовки к анализу возможности завершения процессов в цикле между узлами 8 и 11).

Между узлами 6 и 12 организован цикл до получения переменной Прод значения False. В этом цикле вычисляется количество свободных единиц ресурса, с учётом единиц, возвращённых процессами после их завершения. Собственно вычисления осуществляются в цикле, организованном между узлами 7 и 11. Процесс считается завершённым, а единицы ресурса возвращаются в переменную Св_Р,если количество единиц Ост (i), которые ещё может затребовать процесс, не больше количества свободных единиц ресурса. Если все процессы могут завершиться, то переменная Св_Р примет первоначальное значение и станет равной переменной Вс_Р. В этом случае система не придёт в опасное состояние и заявка процесса может быть удовлетворена.

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

· допущение о фиксированном числе единиц ресурса, что не всегда соответствует истине;

· нереальность требования постоянства числа параллельных работающих процессов (в реальных условиях число параллельных процессов всё время меняется);

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

4.5.3. Обнаружение тупика

Существует несколько методов обнаружения тупика. Наиболее доступен для понимания метод редукции (сокращения) графа модели Холта. Редукция графа Холта выполняется по следующим правилам:

Граф модели Холта сокращается процессом P_i, который не является ни заблокированной, ни уединённой вершиной, посредством удаления всех дуг, входящих в вершину и исходящих из неё;

Граф ресурсов не сокращаем, если он не может быть сокращён ни одним процессом.

Граф ресурсов типа SR является полностью редуцируемым, если существует последовательность сокращений, удаляющая все дуги графа.

Если в результате редукции графа Холта осталась хотя бы одна не удалённая дуга, то возникнет тупик.

Ниже приведён пример редукции графа, исследовавшего тупик на ресурсах SR в разделе 4.2 (рис. 4.19).

а)	б)	в)
Рис. 4.19. Граф Холта в исходном состоянии (а), стадии захвата процессом ПР1 ресурса R2 (б) и в стадии захвата ресурса R1 процессом ПР2 (в)

На рис. 4.19,б показан граф после захвата процессом Р1 ресурса R2. Из вершины R2 исчезла единица ресурса, и исчезли выходящая из вершины ПР1 и входящая в него дуги. Процесс ПР2 может захватить ресурс R1. Тогда с графа исчезнут дуги исходящая из вершины ПР2 и входящая в неё. Поскольку процесс ПР2 захватил ресурс R1, то из вершины R1 исчезла единица ресурса R1. Это состояние системы показано на рис. 4.19,в. Оба процесса запрашивают ресурсы, которые уже не имеют свободных единиц. Поэтому оба процесса заблокированы и не могут никак освободить захваченные ресурсы. Налицо тупик.

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

Что такое тупик? Приведите примеры.

Каковы условия возникновения тупика?

Какова классификация разделяемых ресурсов в модели Холта?

В чем разница между системными ресурсами и расходуемыми ресурсами?

Из каких элементов состоит граф Холта? Приведите пример графа и интерпретируйте его.

Что обозначает следующий фрагмент графа Холта?

Что обозначает следующий фрагмент графа Холта?

Объясните следующий граф Холта.

Поясните как возникновение тупика при кольцевом обмене процессов сообщениями через почтовые ящики.

Приведите пример возникновения тупика в системе с семафорами.

Приведите пример возникновения тупика в системе с мониторами.

Что такое сеть Петри? Из каких элементов она состоит?

На рисунке показан фрагмент сети Петри. Может ли завершиться процесс ПР1? Почему?

На рисунке показан фрагмент сети Петри. Может ли завершиться процесс ПР1? Почему?

На рисунке показан фрагмент сети Петри. Может ли завершиться процесс ПР1? Почему?

Как нейтрализовать условие взаимного исключения для предотвращения тупика?

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

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

Как исключить условие кругового ожидания для предотвращения тупика?

5. ЖЁСТКИЙ ДИСК

5.1. Устройство накопителя жесткого диска (HDD)
и адресация элементов дискового пространства

Схема устройства накопителя на жёстком диске показана на рис. 5.1. Два носителя информации, имеющие форму дисков, помещены на шпиндель, который вращается с высокой скоростью. Рабочие поверхности носителей покрыты намагничивающимся материалом. Они пронумерованы, нумерация ведётся с нуля. На рис. 5.1 носители имеют четыре рабочих поверхности с номерами
0 – 3. Запись и чтение информации осуществляется головками чтения/записи, которые вследствие высокой скорости вращения парят над поверхностями на воздушной подушке. Позиционирование головок относительно поверхностей носителей производится перемещением основания головок специальными механизмами перемещения головок.

Рис. 5.1. Схема устройства накопителя на жёстком диске

На поверхности носителей нанесены концентрические дорожки, которые разбиты на секторы. Эта разбивка сделана потому, что на дорожке помещается слишком много информации для одной операции чтения/записи данных. Множество дорожек одинакового диаметра называются цилиндрами, а несколько подряд идущих секторов на дорожке называются кластерами. Кластеры на части при записи файлов не делятся, поэтому часть дискового пространства пропадает из-за того, что файл может не заполнять кластер целиком. Кластер явля­ется минимально адресуемой частью дискового пространства.

Для обращения к кластерам, секторам и блокам данных имеется две системы физических адресов элементов дискового пространства: CHS и LBA. В системе CHS координатами сектора являются: номер цилиндра (C ylinder), номер рабочей поверхности носителей (Н ead), он же номер дорожки в цилиндре, номер сектора на дорожке (S ector).