8823

Взаимоблокировка процессов

Контрольная

Информатика, кибернетика и программирование

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

Русский

2013-02-17

181.5 KB

39 чел.

Взаимоблокировка процессов

5.1 Взаимоблокировка процессов

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

Ресурсы бывают выгружаемые и невыгружаемые, аппаратные и программные.

Выгружаемый ресурс - этот ресурс безболезненно можно забрать у процесса (например: память).

Невыгружаемый ресурс - этот ресурс нельзя забрать у процесса без потери данных (например: принтер).

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

Условия необходимые для взаимоблокировки:

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

5.2 Моделирование взаимоблокировок

Моделирование тупиков с помощью графов.

Условные обозначения

 

На такой модели очень хорошо проверить возникает ли взаимоблокировка. Если есть цикл, значит, есть и взаимоблокировка.

Рассмотрим простой пример:

три процесса A, B, C

три ресурса R, S, T

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

 

Рассмотрим циклический алгоритм:

три процесса A, B, C

три ресурса R, S, T

Возникает взаимоблокировка

 

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

 

 

Взаимоблокировка не возникает.

 

 

5.3 Методы борьбы с взаимоблокировками

Четыре стратегии избегания взаимоблокировок:

  1.  Пренебрежением проблемой в целом (вдруг пронесет).
  2.  Обнаружение и устранение (взаимоблокировка происходит, но оперативно ликвидируется).
  3.  Динамическое избежание тупиков.
  4.  Предотвращение четырех условий, необходимых для взаимоблокировок.

 

5.3.1 Пренебрежением проблемой в целом (страусовый алгоритм)

Если вероятность взаимоблокировки очень мала, то ею легче пренебречь, т.к. код исключения может очень усложнить ОС и привести к большим ошибкам. Также многие взаимоблокировки тяжело обнаружить.

Этот алгоритм используется как в UNIX, так и в Windows.

Поэтому (и не только) на серверах часто устанавливают автоматическую перезагрузку (раз в сутки, как правило ночью), если возникнет взаимоблокировка, то после перезагрузки ее не будет.

 

5.3.2 Обнаружение и устранение взаимоблокировок

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

 

Обнаружение взаимоблокировки при наличии одного ресурса каждого типа

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

Рассмотрим систему из 7-ми процессов и 6-ти ресурсов.

Обнаружение взаимоблокировки при наличии одного ресурса каждого типа

 

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

Для этого нужен алгоритм.

Рассмотрим один из алгоритмов.

Для каждого узла N в графе выполняется пять шагов.

  1.  Задаются начальные условия: L-пустой список, все ребра не маркированы.
  2.  Текущий узел добавляем вконец списка L и проверяем количество появления узла в списке. Если он встречается два раза, значит цикл и взаимоблокировка.
  3.  Для заданного узла смотрим, выходит ли из него хотя бы одно немаркированное ребро. Если да, то переходим к шагу 4, если нет, то переходим к шагу 5.
  4.  Выбираем новое немаркированное исходящее ребро и маркируем его. И переходим по нему к новому узлу и возвращаемся к шагу 3.
  5.  Зашли в тупик. Удаляем последний узел из списка и возвращаемся к предыдущему узлу. Возвращаемся к шагу 3. Если это первоначальный узел, значит, циклов нет, и алгоритм завершается.

Алгоритм обнаружения взаимоблокировок

 

Для нашего случая тупик обнаруживается в списке L=[B,T,E,V,G,U,D,T]

 

Обнаружение взаимоблокировки при наличии нескольких ресурсов каждого типа

Рассмотрим систему.

m - число классов ресурсов (например: принтеры это один класс)

n - количество процессов

P(n) - процессы

E - вектор существующих ресурсов

E(i) - количество ресурсов класса i

A - вектор доступных (свободных) ресурсов

A(i) - количество доступных ресурсов класса i

С - матрица текущего распределения (какому процессу, какие ресурсы принадлежат)

R - матрица запросов (какой процесс, какой ресурс запросил)

 

 

C(ij) - количество экземпляров ресурса j, которое занимает процесс P(i).

R(ij) - количество экземпляров ресурса j, которое хочет получить процесс P(i).

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

 

Рассмотрим алгоритм поиска тупиков.

Алгоритм поиска тупиков при наличии нескольких ресурсов каждого типа

 

 

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

Рассмотрим работу алгоритма на реальном примере.

 

 

 

Используем алгоритм:

  1.  Третий процесс может получить желаемые ресурсы, т.к. R (2 1 0 0) = A (2 1 0 0)
  2.  Третий процесс освобождает ресурсы. Прибавляем их к A. А = (2 1 0 0) + (0 1 2 0) =(2 2 2 0). Маркируем процесс.
  3.  Может выполняться процесс 2. По окончании А=(4 2 2 1).
  4.  Теперь может работать первый процесс.

Тупиков не обнаружено.

Если рассмотреть пример, когда второму процессу требуются ресурсы (1 0 3 0), то два процесса окажутся в тупике.

 

Когда можно искать тупики:

  •  Когда запрашивается очередной ресурс (очень загружает систему)
  •  Через какой то промежуток времени (в интерактивных системах пользователь это ощутит)
  •  Когда загрузка процессора слишком велика

 

Выход из взаимоблокировки

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

Как правило, требует ручного вмешательства (например: принтер).

 

Восстановление через откат

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

С принтером опять будут проблемы.

 

Восстановление путем уничтожения процесса

Самый простой способ.

Но с принтером опять будут проблемы.

 

В реальных системах они не годятся.

 

5.3.3 Динамическое избежание взаимоблокировок

В этом способе ОС должна знать, является ли предоставление ресурса безопасным или нет.

 

Траектории ресурсов

Рассмотрим модель из двух процессов и двух ресурсов.

А1 - запрос принтера процессом А

А2 - запрос плоттера процессом А

А3 - освобождение принтера процессом А

А4 - освобождение плоттера процессом А

В1 - запрос плоттера процессом В

В2 - запрос принтера процессом В

В3 - освобождение плоттера процессом В

В4 - освобождение принтера процессом В

Динамическое избежание взаимоблокировок

 

Т.к. процессор предоставляется поочередно, траектория может продолжаться только параллельно осям.

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

 

Безопасные и небезопасные состояния

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

Рассмотрим систему.

10 экземпляров ресурса

3 процесса

 

Процесс А занял 3 экземпляра, но ему необходимо 9.

В этой ситуации можно спланировать так, сначала запустить процесс В, потом С и потом А.

Процессы заканчивают работу без тупиковой ситуации.

 

Рассмотрим другую ситуацию.

Процесс А занял 4 экземпляра.

Возникает небезопасное состояние.

В принципе, процесс А может в какой то момент ресурс освободить и тупика не возникнет.

Видно, что в этом случае не стоило давать ресурс процессу А.

 

Алгоритм банкира для одного вида ресурсов

"Банкира", потому что аналогия такая, клиенты-процессы, кредиты-ресурсы.

Рассмотрим систему:

Банкир может дать 10 кредитов (ресурсы).

К нему попеременно обращаются 4-ре клиента.

Алгоритм банкира:

  1.  Банкиру поступает запрос от клиента на получение кредита
  2.  Банкир проверяет, приводит ли этот запрос к небезопасному состоянию.
  3.  Банкир в зависимости от этого дает или отказывает в кредите.

Алгоритм банкира

 

 

Алгоритм банкира для несколько видов ресурсов

 

Рассмотрим систему:

вектора:
E=(6342) - существующие ресурсы
P=(5322) - занятые ресурсы
A=(1020) - доступные ресурсы

 

Алгоритм поиска безопасного или небезопасного состояния:

 

Алгоритм банкира для несколько видов ресурсов

 

Если состояние безопасное то ресурс дать можно, если нет то нельзя.

На практике все эти алгоритмы тяжело реализовать.

 

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

Предотвращение условия взаимного исключения

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

Например, с помощью спулинга для принтера, когда только демон принтера работает с принтером.

 

Предотвращение условия удержания и ожидания

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

 

Предотвращение условия отсутствия принудительной выгрузки ресурса

Можно выгружать ресурсы, но могут быть проблемы с принтером.

 

Предотвращение условия циклического ожидания

Способы предотвращения:

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



PAGE  1


 

А также другие работы, которые могут Вас заинтересовать

74479. СТРАТЕГИЧЕСКОЕ ПЛАНИРОВАНИЕ 70 KB
  Выбор стратегии предприятия Стратегическое планирование задает перспективные направления развития предприятия определяет основные виды его деятельности позволяет увязать в единую систему маркетинговую проектную производственную и финансовую деятельность. Стратегический план обеспечивает адаптацию предприятия к внешней среде к распределению ресурсов и внутреннюю координацию деятельности с целью выявления сильных и слабых сторон. Стратегический план на крупных предприятиях как правило долгосрочный. Но временной период стратегического...
74480. ПЛАНИРОВАНИЕ ПРОИЗВОДСТВА И РЕАЛИЗАЦИИ ПРОДУКЦИИ 166 KB
  Планирование производства продукции работ и услуг должно удовлетворять на всех действующих предприятиях конкретные потребности покупателей заказчиков или потребителей и быть тесно связанным с разрабатываемой общей стратегией развития предприятия проведением маркетинговых исследований проектированием конкурентоспособной продукции организацией ее производства и реализации а также с выполнением других функций и видов внутрихозяйственной деятельности. В годовом плане производства каждого...
74481. ПЛАНИРОВАНИЕ ТЕХНИЧЕСКОГО РАЗВИТИЯ ПРОИЗВОДСТВА 149.5 KB
  Планирование технического развития производства состоит из комплекса технических организационных планово-экономических и социальных мероприятий направленных на повышение технического уровня производства увеличение выпуска высококачественной продукции роста производительности труда улучшение использования основных фондов производственных мощностей материальных и трудовых ресурсов совершенствование внутризаводской системы управления планирования экономического стимулирования улучшение...
74482. ПЛАНИРОВАНИЕ РЕСУРСНОГО ОБЕСПЕЧЕНИЯ ДЕЯТЕЛЬНОСТИ ПРЕДПРИЯТИЙ 98 KB
  Любое предприятие планируя величину прибыли должно взвешивать выгоды от приобретения каждой дополнительной единицы ресурсов позволяющей ему производить и продавать больше продукции. Предприятие принимает решение о приобретении дополнительных ресурсов на основе сравнения получаемого или планируемого предельного дохода от применения этого ресурса с его предельными издержками. Перспективное планирование потребности различных ресурсов на каждом предприятии должно ориентироваться на удовлетворение имеющегося спроса на продукцию и...
74483. ПЛАН ПО ТРУДУ И ЗАРАБОТНОЙ ПЛАТЕ 138.5 KB
  Основой составления плана по труду является учет всех ресурсов и факторов роста производительности труда определение оптимальной численности и структуры персонала обоснованный расчет фонда заработной платы. Исходными данными для разработки плана являются: Задания по росту производительности труда по численности работающих задание по сокращению ручного труда фонд заработной платы и норматив заработной платы на один рубль продукции.
74484. ПЛАНИРОВАНИЕ ИЗДЕРЖЕК ПРОИЗВОДСТВА И ЦЕН 120 KB
  Производственные издержки являются основой себестоимости продукции. Чтобы определить общие издержки производства различных видов продукции необходимо знать суммарные затраты ресурсов и объем выпуска товаров. Постоянными принято называть такие издержки величина которых не изменяется в зависимости от объема выпуска продукции арендная плата расходы на освещение отопление оплата административноуправленческого персонала и т. Переменными считаются такие издержки величина которых меняется в зависимости от объема выпуска продукции сырье...
74485. Финансовое планирование. Формирование и распределение прибыли на предприятии 159.5 KB
  Планирование финансовой деятельности предприятия тесно связано с конечными результатами производства важнейшим из которых в условиях рыночных отношений является общая прибыль или совокупный доход что требует усиления роли финансов в достижении этих показателей. Доход предприятия или прибыль является в условиях рынка основой самофинансирования всех видов производственнохозяйственной деятельности и социальнотрудовых отношений персонала. Валовая прибыль определяет величину общего совокупного дохода предприятия без...
74486. ТЕХНИКА ПЕРЕГОВОРНЫХ ПРОЦЕССОВ 72.5 KB
  При проведении переговоров важно понимать общие закономерности делового общения что позволит анализировать ситуацию учитывать интересы партнера говорить на общем языке. В процессе переговоров можно выделить три основные стадии: подготовка к переговорам; процесс их ведения; анализ результатов переговоров и выполнение достигнутых договоренностей. Основные этапы переговоров способы подачи позиции Исходный пункт любых управленческих действий это определение цели. Ошибается тот кто в качестве цели переговоров ставит безоговорочное...
74487. Особенности делового общения: деловая беседа, деловые переговоры, деловые совещания, деловые дискуссии 66 KB
  Структура деловой беседы: подготовка к деловой беседе; установление места и времени проведения встречи; начало беседы: вступление в контакт; постановка проблемы и передача информации информирование партнёров; аргументирование выдвигаемых положений; опровержение доводов собеседника; анализ альтернатив поиск оптимального или компромиссного варианта либо конфронтация участников; принятие решения; фиксация договорённостей; завершение беседы; анализ результатов беседы своей тактики общения. является трудным и ответственным делом...