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

3.8. МОНОПОЛЬНІ РЕСУРСИ. ПРОБЛЕМА ТУПИКІВ. ДИСЦИПЛІНИ РОЗПОДІЛУ РЕСУРСІВ. ПОШУК ТУПИКІВ ТА ЇХ ЗНИЩЕННЯ.

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

Пример тупика. Пусть двум процессам, выполняющимся в режиме мультипрограммирования, для выполнения их работы нужно два ресурса, например, принтер и диск. На рисунке 2.6,а показаны фрагменты соответствующих программ. И пусть после того, как процесс А занял принтер (установил блокирующую переменную), он был прерван. Управление получил процесс В, который сначала занял диск, но при выполнении следующей команды был заблокирован, так как принтер оказался уже занятым процессом А. Управление снова получил процесс А, который в соответствии со своей программой сделал попытку занять диск и был заблокирован: диск уже распределен процессу В. В таком положении процессы А и В могут находиться сколь угодно долго.

Проблема тупиков включает в себя следующие задачи:

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

Тупики могут быть предотвращены на стадии написания программ, то есть программы должны быть написаны таким образом, чтобы тупик не мог возникнуть ни при каком соотношении взаимных скоростей процессов. В некоторых случаях, когда тупиковая ситуация образована многими процессами, использующими много ресурсов, распознавание тупика является нетривиальной задачей. Существуют формальные, программно-реализованные методы распознавания тупиков, основанные на ведении таблиц распределения ресурсов и таблиц запросов к занятым ресурсам. Анализ этих таблиц позволяет обнаружить взаимные блокировки. Если же тупиковая ситуация возникла, то не обязательно снимать с выполнения все заблокированные процессы. Можно снять только часть из них, при этом освобождаются ресурсы, ожидаемые остальными процессами, можно вернуть некоторые процессы в область свопинга, можно совершить "откат" некоторых процессов до так называемой контрольной точки, в которой запоминается вся информация, необходимая для восстановления выполнения программы с данного места. Контрольные точки расставляются в программе в местах, после которых возможно возникновение тупика. Предотвратить тупик можно выделяя ресурсы последовательно(Любыми ресурсами может одновременно пользоваться только один процесс), залпово(Процесс должен запрашивать/освобождать все используемые им ресурсы сразу. Эта стратегия позволяет параллельно выполняться процессам, использующим непересекающиеся подмножества ресурсов), иерархически(Все классы ресурсов разбиваются по уровням с номерами от 1 до N, каждый уровень содержит только один класс. Процесс имеет право запрашивать ресурсы только из классов с более высокими номерами, чем у тех, которыми он уже владеет. Эта стратегия также предотвращает возникновение тупиков. В каждый момент времени в системе один или несколько процессов имеют класс закрепленных за ними ресурсов выше, чем у других. Эти процессы, обладающие ресурсами высокого уровня, могут беспрепятственно выполняться и завершиться без блокировки. Следовательно, в каждый момент времени имеется хотя бы один способный к выполнению процесс. Если не будут поступать новые процессы, то все процессы, уже имеющиеся в системе, в конце концов завершатся), по предварительным заявкам. Эта стратегия названа так потому, что действия ОС напоминают действия банкира, выдающего ссуды клиентам).

Задача «Обедающие философы». Пять философов сидят за круглым столом, в центре которого стоит блюдо с рисом. Между каждой парой философов лежит палочка для еды, палочек, следовательно, тоже пять. Для того, чтобы начать есть, философ должен взять две палочки - слева и справа от себя. Таким образом, если один из философов ест, его соседи справа и слева лишены такой возможности, так как им недостает палочек. Каждый философ "работает" по зацикленному алгоритму: сначала он некоторое время думает, затем берет палочки и ест, затем опять думает и т.д. Временные интервалы мышления и еды случайны, действия философов, следовательно не синхронизированы. Ничего не говорится в условии о том, каким образом философ берет палочки наша задача как раз и состоит в том, чтобы обеспечить такую стратегию выделения палочек, которая бы исключала тупики и голодание.

«Голодание» - Процессы, ожидающие ресурсов, встают в очереди к этим ресурсам. Такая очередь может обслуживаться любой невытесняющей стратегией планирования. Моментом, когда менеджер ресурса принимает решение об обслуживании, является освобождение ресурса.

Алгоритм «Банкира».

1.Клиент делает заем для совершения сделки, которая будет завершена за конечный промежуток времени.
2.Клиент должен заранее указать максимальную "потребность" во флоринах для этой сделки.
3.Пока "заем" не превышает заранее установленную "потребность", клиент может увеличивать или уменьшать свой заем флорин за флорином.
4.Клиент, который просит увеличить его текущий заем, обязуется принимать без недовольства следующий ответ: "Если бы я дал вам запрашиваемый флорин, вы еще не превысили бы свою установленную потребность, и поэтому вы имеете право на следующий флорин. Однако в настоящий момент мне, по некоторым причинам, неудобно его дать, но я обещаю вам флорин в должное время".
5.Гарантия для клиента в том, что этот момент действительно наступит, основана на предусмотрительности банкира и на том факте, что остальные клиенты подчиняются тем же условиям, что и он сам: как только клиент получает флорин, он приступает к своей сделке с ненулевой скоростью, т. е. в конечный промежуток времени он или запросит новый флорин, или возвратит флорин, или закончит сделку, что означает возвращение всего займа (флорин за флорином).

3.9. Параллельное выполнение процессов. Формулировка задачи «производитель-потребитель» и методы ее решения

3.9. ПАРАЛЕЛЬНЕ ВИКОНАННЯ ПРОЦЕСІВ. ФОРМУЛЮВАННЯ ЗАДАЧІ «ВИРОБНИКИ-СПОЖИВАЧІ» ТА МЕТОДИ ЇЇ ВИРІШЕННЯ.

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

Основной задачей управления параллельным выполнением является задача взаимного исключения (mutual exclusion, сокращенно - mutex): два процесса не могут выполнять одновременный доступ к разделяемым ресурсам. Взаимное исключение является расширением задачи транзактивности на любые ресурсы. Если процессор одновременно получает два запроса, то он выполняет их последовательно. Каждая процессорная команда имеет свойства транзакции: она или выполняется полностью, или вообще не выполняется. Задача семафоров использует блокировку ожидающего процесса - перевод его из списка процессов, планируемых на выполнение (готовых) в список ожидающих (заблокированных). Этим экономится процессорное время, в противном случае попусту растрачиваемое в занятом ожидании, а затраты сводятся к переключению процессов.

Такая возможность обеспечивается:

а).введением специальных целочисленных общих переменных, которые называются семафорами (semaphore);

б). добавлением к набору элементарных действий, из которых строятся процессы, операций над семафорами: V-операции и P-операции. V-операция есть операция с одним операндом, который должен быть семафором.

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

Несколько процессов могут начать одновременно P-операцию над одним и тем же семафором. Тогда при установке семафора в 1 только одна из P-операций завершится, какая именно - мы обсудим позже. Защита разделяемых ресурсов теперь выглядит следующим образом. Каждый ресурс защищается своим семафором, значение которого может быть 1 - свободен или 0 - занят.

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

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

Решение достигается при помощи единственного общего семафора, играющего роль счетчика числа порций в буфере. Исходное значение семафора 0. Производитель каждую итерацию своего цикла заканчивает V-операцией, увеличивающей значение счетчика. Потребитель каждую свою итерацию начинает P-операцией. Если буфер пуст, то потребитель задержится в своей P-операции до появления в буфере очередной порции. Таким образом, если потребитель работает быстрее производителя, он будет время от времени простаивать, если производитель работает быстрее - в буфере будут накапливаться порции.

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

Дата добавления: 2015-11-16