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

π – множество процессов {Р₁,Р₂, …, Р_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).

В системе LBA (Logical Block Addressing) используется линейная адресацию секторов, начиная с сектора 1, головки 0, цилиндра 0 и заканчивая последним физическим сектором диска. Адрес начального сектора диска обозначается как LBA 0. Номер сектора в системе LBA определяется выражением:

LBA = (СхH_max + H)xSmax + S – 1

где С, H, S – координаты сектора в системе CHS,
H_max – общее количество рабочих поверхностей дисков,
S_max – число секторов на дорожке.

5.2. Логическая структура диска

Дорожки, секторы и кластеры являются понятиями, относящимися к физической структуре диска. Однако пользователю удобнее работать с диском на логическом уровне, т.е. иметь дело с именованными элементами дискового пространства вместо численных адресов секторов и кластеров. Структура диска, описанная таким образом, называется логической. Схематически логическая структура диска [1] показана на рис. 5.2. Жирный прямоугольник в центре рисунка изображает дисковое пространство реального физического устройства. Оно разбито на разделы (Partition). Разделы бывают первичные (Primery) и расширенные (Extended). На диске может быть только один расширенный раздел, который в свою очередь может быть разбит на разделы. На всех разделах создаются логические диски[8]. На рис. 5.2 показаны один первичный раздел с логическим диском С: и расширенный раздел с логическими дисками D: и Е:. Один из разделов всегда активен, остальные – пассивны.

Главная таблица разделов
Адрес первичного раздела Адрес расширенного раздела Прочая информация NBS и Системный загрузчик		Загрузочный сектор диска С:		Первичный раздел с логическим диском С:
	Master Boot Record
Логический диск D:		Загрузочный сектор диска D:
Адрес таблицы для диска E: Прочая информация Системный загрузчик
	Secondary Master Boot Record
				Расширенный раздел с логическими дисками D: и Е:
Логический диск Е:		Загрузочный сектор диска Е:
0 – конец цепочки Прочая информация Системный загрузчик
	Secondary Master Boot Record
		Нераспределённое дисковое пространство

Рис. 5.2. Разделы жёсткого диска

На первом секторе каждого диска создаётся загрузочная запись Master Boot Record для логического диска первичного раздела и Secondary Master Boot Record для каждого логического диска расширенного раздела. На первом секторе логического диска С: располагается также специальная программа, которая называется внесистемным загрузчиком Non-Systeb Bootstrap (NSB). На любом из логических дисков может быть установлена операционная система.

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

· флаг активности раздела;

· номер головки начала раздела;

· номера сектора и цилиндра загрузочного сектора раздела (адрес начала раздела);

· кодовый идентификатор[9] операционной системы (например, 006h для FAT16);

· номер головки конца раздела;

· номера сектора и цилиндра последнего сектора раздела (адрес конца
раздела);

· младшее и старшее двухбайтовые слова относительного номера начального сектора раздела;

· младшее и старшее двухбайтовые слова размера раздела в секторах.

При старте операционной системы в оперативную память автоматически загружается загрузочный сектор диска С:, и управление передаётся внесистемному загрузчику NBS, который выявляет активный раздел и с него производит загрузку операционной системы посредством системного загрузчика. Адреса начал логических дисков D:, E: и т.д. операционная система определяет по адресу конца раздела предшествующего диска. При установке на диск нескольких операционных систем выбор загружаемой системы осуществляется менеджером загрузки.

5.3. Создание загрузочных дисков

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

При желании во время установки операционной системы на жёсткий диск можно заказать создание загрузочной дискеты, которая может оказаться полезной в аварийных случаях и содержит важнейшие системные файлы: загрузчик, Msdos.sys, IO.sys, и command.com, а также драйвер для работы с компакт-диском. В настоящее время дисководы гибких дисков вытесняются с компьютеров, поэтому создание загрузочной дискеты практически потеряло смысл.

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

Определите понятия: дорожка, цилиндр, сектор, кластер.

Поясните способы CHS и LBA адресации секторов на магнитном диске.

Поясните логическую структуру диска.

Каково содержимое Master Boot Record'а?

Каково содержимое Secondary Master Boot Record'а?

В чём проблема четырёх первичных разделов? Почему её желательно решить? Каковы способы решения этой проблемы?

Что такое внесистемный и системный загрузчики? Каковы их функции?

Опишите процесс загрузки операционной системы.

Каково содержимое таблиц разделов?

Какова процедура создания загрузочных дисков?

6. ФАЙЛОВЫЕ СИСТЕМЫ

6.1. Файлы и каталоги

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

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

Простые файлы по назначению можно разделить на исполняемые файлы, динамические библиотеки и наборы данных. Исполняемые файлы содержат программный код в двух видах: в виде команд операционной системы и в машинных кодах. На наличие программного кода указывает расширения имени (тип) файла. В частности расширение bat указывает, что файл содержит программу на языке операционной системы, например операционной системы MS DOS, состоящую из команд path, copy, type, dir, chdir и т.д. Сведущий пользователь может прочитать эту программу в среде простейшего текстового редактора и понять её без каких-либо проблем. Расширения exe и com указывают на наличие кода в машинных командах. Файлы первого из них типа содержат прикладные программы пользователей, второго – как правило, утилиты, драйверы и прочие служебные программы. Расширения ovl указывают, что эти файлы содержат программный код и подгружаются в оперативную память по мере надобности и выгружаются из неё после выполнения содержащейся в них программы.

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

Простые файлы, содержащие наборы данных имеют самые разные расширения имён. Иногда расширениенесёт информацию о назначении файла, например, jpeg указывает на графический файл, содержащий архивированную по специальному алгоритму информацию. В других случаях оно указывает на программное средство, в среде которого создан файл. Например, расширения bas и pas указывают на создание файлов среде систем программирования Basic и Pascal. Во многих случаях расширения имени (тип) файла ни о чём не говорит подавляющему большинству пользователей.

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

Операционные системы поддерживают специальные характеристики файлов (табл. 6.1), которые называются атрибутами [3]. Операционная система может поддерживать не все атрибуты, перечисленные в табл. 6.1.