Тупики (deadlocks), методы предотвращения и обнаружения тупиков

Презентацию к данной лекции Вы можете скачать здесь.

Введение

Одна из важных задач операционной системы – распределение ресурсов компьютера между процессами. С данной задачей тесно связано понятие тупика (deadlock). В лекции введены базовые понятия, касающиеся распределения ресурсов и обнаружения тупиков. Рассмотрены следующие вопросы:

Проблема тупиков

Тупик (deadlock) – множество заблокированных процессов, каждый из которых владеет некоторым ресурсом и ожидает ресурса, которым владеет какой-либо другой процесс из этого множества.

Простой пример тупика легко смоделировать с помощью семафоров (см. ). Пусть в системе есть два внешних устройства A и B, к которым обращаются два процесса P1 и P2. С каждым из внешних устройств с целью синхронизации связан семафор, которые будем обозначать также A и B.Семафоры изначально открыты. Пусть каждому из процессов необходимы оба устройства, но они обращаются к ним в противоположном порядке:

P1: wait(A); wait (B)
P2: wait(B); wait (A).

В данном случае будет иметь место тупик: процесс P1, закрыв семафор A и заблокировав первое устройство, никогда не дождется, когда откроется семафор B,связанный со вторым устройством, так как его уже успел закрыть процесс P2.Аналогично, процесс P2 никогда не дождется, когда откроется семафор A.

Модель системы

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

Пусть в системе имеется m видов ресурсов (например, процессор, память, устройства ввода-вывода). Будем обозначать типы ресурсов в системе R1, R2, … Rm.Пусть каждый тип ресурса Ri имеет Wi экземпляров.

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

Тупик может возникнуть, если одновременно выполняются следующие четыре условия:

Граф распределения ресурсов

Введем в рассмотрение граф распределения ресурсов, состоящий из множества вершин V и множества дуг E. V подразделяется на два типа вершин: вершина-процесс и вершина-ресурс.Иначе говоря, V подразделяется на вершины типа P = {P1, P2, … ,Pn} множество всех процессов в системе, и вершины типа R = {R1, R2, … ,Rm}

Введем два типа дуг:

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

Уточним особенности вводимого графа и его вершин. В современной терминологии, граф данного вида называется reserved graph. Его вершина-процесс имеет обычный вид, а вершина-ресурс, соответствующая ресурсу Rj,состоит из Wj подвершин, каждая из которых обозначает конкретную единицу ресурса. В теории reserved graphs такие вершины иногда называют супервершинами (super-vertices).Таким образом, дуга запроса ведет из вершины-процесса в вершину-ресурс в целом, а дуга присваивания ведет из соответствующей подвершины вершины-ресурса в вершину-процесс.

Пример вершины-процесса приведен на рис 13.1.

(рис 13.1) Пример вершины-процесса в графе распределения ресурсов.

Пример (супер)вершины-ресурса с четырьмя экземплярами приведен на рис 13.2: каждому экземпляру ресурса соответствует своя подвершина.

(рис 13.2) Пример вершины-ресурса с четырьмя экземплярами.

Пример графа распределения ресурсов приведен на рис 13.3.

(рис 13.3) Пример графа распределения ресурсов.

Данный граф изображает систему с тремя процессами и четырьмя видами ресурсов: ресурсы видов 1 и 3 имеют по одному экземпляру, ресурс вида 2 – два экземпляра, ресурс вида 4 – три экземпляра. Процесс 1 претендует на ресурс 1, который занят процессом 2. Процесс 2 претендует на ресурс 3, который занят процессом 3. Две единицы ресурса 2 отданы процессам 1 и 2. Ресурс 4 не распределялся (все три единицы свободны).

Поиск тупиков по графу распределения ресурсов

Очевидно, что цикл в таком графе может означать наличие тупика. На рис 13.4 приведен пример графа с тупиком. Имеется ситуация циклического ожидания между процессами 1, 2 и 3. Процесс 1 претендует на ресурс, которым владеет процесс 2. Процесс 2 претендует на ресурс, которым владеет процесс 3. Процесс 3 претендует на ресурс, одна единица которого отдана процессу 1, а вторая – процессу 2.

(рис 13.4) Пример графа распределения ресурсов с тупиком.

Однако не всегда наличие цикла в графе распределения ресурсов означает наличие тупика. На рис 13.5 приведен пример графа распределения ресурсов с циклом, но без тупика.

(рис 13.5) Пример графа распределения ресурсов с циклом, но без тупика.

В данном случае (рис 13.5) имеется четыре процесса и два вида ресурсов. В цикле участвуют вершины-процессы 1 и 3. Однако, благодаря тому, что каждого ресурса имеется по две единицы, тупика удается избежать: процесс 1, ожидающий ресурса 1, сможет его получить, когда завершится процесс 2 (а не процесс 1), обладающий одной единицей данного ресурса и не входящий в цикл ожидания. Аналогично, процесс 3, претендующий на ресурс 2, сможет его получить после его освобождения процессом 4 (а не 1).

Таким образом, можно сформулировать следующие утверждения:

Методы обработки тупиков

Теоретически возможны следующие методы обработки тупиков:

К сожалению, на практике во многих ОС (включая UNIX) используется и третий "метод" борьбы с тупиками: проблема тупиков игнорируется, но авторы ОС без каких-либо обоснований претендуют на то, что в системе тупики невозможны.

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

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

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

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

Более разумной представляется стратегия перераспределения ресурсов при каждом ожидании процессом ресурса. Если процесс обладает некоторым ресурсом A и запрашивает другой ресурс B, который не может быть ему немедленно выделен, то процесс должен ждать. При этом ресурс A,занимаемый процессом, должен быть немедленно освобожден.Ресурс A добавляется к списку ресурсов, которые ожидает процесс. Процесс может быть возобновлен, только если ему могут быть выделены одновременно все старые ресурсы, которыми он обладал, и те новые ресурсы, которых он ожидает.

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

Избежание тупиков

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

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

Например, в ОС ДИСПАК для БЭСМ-6 (еще в 1960-х гг.) паспорт задания мог иметь вид:

ЛИСТ 0-37^ТРАК 50^ВРЕМ 240^АЦПУ 10^

где ЛИСТ – диапазон листов (страниц) основной памяти, ТРАК – требуемый объем внешней памяти на магнитном барабане, ВРЕМ – максимальное время выполнения (2 минуты 40 секунд, что соответствовало одному из быстрых классов заданий), АЦПУ – максимальный объем выдачи на печатающее устройство в листах.

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

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

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

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

Ключевые термины

Reserved graph – ориентированный граф, содержащий, кроме обычных вершин, также супервершины ; дуга в таком графе может вести из обычной вершины в супервершину или из подвершины супервершины в обычную вершину.

Вершина-процесс – вершина в графе распределения ресурсов, изображающая процесс.

Вершина-ресурс – супервершина в графе распределения ресурсов, изображающая каждую единицу ресурса какого-либо типа.

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

Граф распределения ресурсов – граф, описывающий состояние распределения ресурсов в системе, состоящий из множества вершин (типа вершина-процесс и вершина-ресурс) и множества дуг ( дуги типа запрос и дуги типа присваивание ).

Дуга типа "запрос" (request edge) – направленная дуга из вершины-процесса в вершину-ресурс.

Дуга типа "присваивание" (assignment edge) – направленная дуга из подвершины, изобращающей конкретную единицу ресурса, в вершину-процесс.

Запрос (request) - действие процесса по запросу к ОС о необходимости выделения ему ресурса какого-либо вида.

Использование (use) – владение и потребление процессом полученной от ОС единицей некоторого вида ресурса.

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

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

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

Супервершина (в составе reserved graph ) – структурированная вершина, содержащая одну или несколько подвершин, из которых могут вести дуги.

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

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

Циклическое ожидание – одно из необходимых условий тупика: существует множество {P0, P1, … P0},такое, что P0 ожидает ресурса, которым обладает P1; P1 ожидает ресурса, которым обладает P2 … Pn ожидает ресурса, которым обладает P0.

Краткие итоги

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

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

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

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

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

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

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

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

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

Набор для практики

Вопросы

Упражнения

Темы для курсовых работ, рефератов, эссе