7

Операционные системы. Лекция 06 (Дедлоки. Управление ресурсами)

Дедлок (тупиковая ситуация).

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

Условия возникновения дедлока.

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

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

2. Ожидание. Процесс, запросивший ресурс, будет ждать, пока запрос не будет удовлетворен, продолжая удерживать все остальные ресурсы, которые он уже получил.

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

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

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

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

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

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

Решение проблемы дедлоков.

Стратегия предотвращения дедлоков.

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

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

Методы предотвращения взаимоблокировок можно разбить на два класса.

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

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

Условие взаимного исключения подавляется путем неограниченного разделения ресурсов (это совершенно неприемлемо к совместно используемым переменным в критических интервалах и к последовательно используемым ресурсам)

Условие ожидания можно подавить, предварительно выделяя ресурсы. Процесс должен потребовать все ресурсы заранее, и он не сможет начать исполнение до тех пор, пока они ему не будут выделены. Неэффективность использования ресурсов (каждый процесс должен ждать, пока не получит всех необходимых ресурсов, даже если один из них используется к концу исполнения. Трудно сформулировать запросы на ресурсы в тех случаях, когда требуемые ресурсы становятся известны только после начала выполнения.

Отсутствие перераспределения можно исключить, позволяя ОС отнимать у процесса ресурсы. Для перераспределения можно использовать две различные дисциплины:

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

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

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

1. Все ресурсы образуют иерархию

2. Процесс, затребовавший ресурс на одном уровне, может затем потребовать ресурс только на более высоком уровне;

3. Процесс может освободить ресурс на данном уровне только после освобождения всех ресурсов на более высоких уровнях;

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

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

Стратегия обхода дедлоков.

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

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

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

Существуют методы эффективного выполнения такого просмотра. Данный подход является примером контролируемого выделения ресурсов.

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

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

Классическое решение этой задачи «алгоритм банкира»

1. Банкир ссужает денежные суммы (в одной валюте), некоторому числу клиентов.

2. Каждый клиент заранее сообщает банкиру максимальную сумму, которая ему нужна.

3. Клиент может занимать эту сумму по частям, и нет никаких гарантий, что он возвратит часть денег до того, как сделает весь заём.

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

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

Решение:

1. Банкир предполагает, что он выполнил запрос, и оценивает сложившуюся ситуацию

2. Он определяет клиента, чей текущий заём наиболее близок к максимальному.

3. Если банкир не может ссудить оставшуюся сумму этому клиенту, то он отклоняет первоначальный запрос.

4. Если же он сможет ссудить эту сумму, то он удовлетворяет первоначальный запрос.

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

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

Для n процессов и m ресурсов простое решение требует время вычисления, пропорциональное mn² . Было предложено решение, требующее время, пропорциональное mn, но при этом для хранения информации необходим объем памяти, больший, чем при использовании медленного алгоритма.

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

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

Стратегия распознавания дедлоков.

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

Чтобы выполнить эти вычисления, ОС должна:

• вести список тех ресурсов, которые ждет каждый заблокированный процесс

• вести список тех процессов, которые держат каждый заблокированный ресурс.

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

• например часто – всякий раз, когда запрос на ресурс отклоняется

• через заданные интервалы времени

Стоимость стратегии распознавания дедлока зависит от того, насколько часто выполняется алгоритм распознавания

Методы восстановления:

Как только дедлок выявлен, должно быть выполнено восстановление.

Самый простой метод восстановления – принудительное завершение всех процессов и запуск ОС заново.

Менее радикальный метод – принудительное завершение всех процессов, находящихся в дедлоке.

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

. Основная «цена» восстановления от дедлока – это потеря времени, которые могут быть существенными.

1. Управление ресурсами в ос

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

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

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

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

1. Воспроизводимые (повторно используемые (Reusable Resource, RR), последовательно используемые или системные (System Resource, SR), ресурсы)

При использовании допустимо многократное выполнение действий запрос-использование-освобождение.

Ресурс SR – конечное множество идентичных единиц со следующими свойствами:

• число единиц ресурса постоянно

• каждая единица ресурса или доступна, или распределена одному и только одному процессу

• процесс может освободить единицу ресурса (сделать ее доступной), только если он ранее получил эту единицу

Примеры: ОП, ВП, периферийные устройства, процессоры, программное и информационное обеспечение (файлы данных, таблицы)

2. Потребляемые (или расходуемые, ресурсы (Consumable Resource, CR)).

После выполнения действий освобождение-запрос-использование ресурс изымается из потребления

Расходуемые ресурсы (CR) отличаются от ресурсов типа SR в нескольких важных отношениях

• Число доступных единиц некоторого ресурса типа CR изменяется по мере того, как выполняющимися процессами они расходуются (приобретаются) и освобождаются (производятся).

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

• Процесс-потребитель уменьшает число единиц ресурса, сначала запрашивая и затем приобретая (потребляя) одну или более единиц. Единицы ресурса, которые приобретены, в общем случае не возвращаются ресурсу, а потребляются (расходуются). Эти свойства потребляемых ресурсов присущи многим синхронизирующим сигналам, сообщениям и данным, порождаемым как аппаратурой, так и программным обеспечением, и могут рассматриваться как ресурсы типа CR. В их число входят: прерывания от таймера и устройств ввода-вывода; сигналы синхронизации процессов; сообщения, содержащие запросы на различные виды обслуживания или данные, а также соответствующие ответы.

Дескриптор ресурса

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

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

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

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

Для каждого класса сообщений в данный момент времени существуют:

Имя ресурса	Символическое или числовое имя сообщения
Список сообщений	Список сообщений, которые были выданы, но не было получены (потреблены)
Очередь ожидания процессов	Содержит список (возможно пустой) процессов с неудовлетворенными запросами на ресурс
Указатель на распределитель	Распределяет сообщения получателям

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

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

Это приводит к общему определению:

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

Операции над семафорами ресурсов.

Определены четыре примитива, работающие с семафорами ресурсов: