Сделай Сам Свою Работу на 5

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

 

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

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

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

Третье условие - отсутствие перераспределения. Никакие ресурсы нельзя отобрать у процесса, если они ему уже выделены, до тех пор пока эти ресурсы не будут использованы для завершения работы.

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

 

Основные направления исследований по проблеме тупиков

 

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

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

- обход тупиков;

- обнаружение тупиков;

- восстановление после тупиков.

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

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

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

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

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

 

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

 

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

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

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

Условие отсутствия перераспределения можно исключить, позволяя операционной системе отнимать у процесса ресурсы. Это выполнимо, если можно запомнить состояние процесса для его последующего восстановления. Перераспределение процессора сравнительно легко реализовать, и оно обычно выполняется так, как это будет описано в гл. 5 (при рассмотрении алгоритмов распределения процессора между процессами). Перераспределение устройств ввода-вывода или магнитофона может быть чрезвычайно неприятным. Для легко перераспределяемых ресурсов "ценой" перераспределения является необходимое для этого время. Для перераспределения ресурсов можно использовать две различные дисциплины. Одна них требует, чтобы работа, запросившая дополнительный ресурс, предварительно отказалась от любого количества этого ресурса, которое она уже имеет. На самом деле полностью это не исключает условие отсутствия перераспределения. Чтобы понять это, достаточно предположить, что ресурсы являются независимыми ресурсами. Другая дисциплина - общее исключение - отнимает у работы, заблокированной при запросе дополнительного ресурса, все ресурсы.

Условие кругового ожидания можно исключить, предотвращая образование цепи. Это обеспечивается иерархическим выделением ресурсов. Все ресурсы образуют некоторую иерархию. Процесс, затребовавший ресурс на одном уровне, может затем потребовать ресурсы только на более высоком уровне. Он может освободить ресурсы на данном уровне только после освобождения всех ресурсов на всех более высоких уровнях. После того как процесс получил, а потом освободил ресурсы данного уровня, он может снова запросить, ресурсы на том же самом уровне. Предварительное выделение ресурсов можно считать специальным случаем иерархического выделения, имеющего единственный уровень. Иерархическое выделение несколько дороже, но оно может снизить потери, связанные с полным предварительным выделением. Однако этот метод не дает никакого выигрыша, если порядок, в котором процессам необходимы ресурсы, отличается от порядка уровней в иерархии. Например, если графопостроитель нужен в начале выполнения, а магнитофон - только в конце, а последний по уровню ниже, чем графопостроитель, то магнитофон придется выделить достаточно рано, и он долгое время не будет использоваться.

Обход дедлоков

 

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

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

 

Алгоритм обхода тупиковых ситуаций, названный алгоритмом банкира, впервые был предложен Дейкстрой. Свое название он получил потому, что он как бы имитирует действия банкира, который, располагая определенным источником капитала, выдает клиентам денежные ссуды и принимает платежи. Банкир ссужает денежные суммы некоторому числу клиентов, каждый из которых заранее сообщает банкиру максимальную сумму, которая ему будет нужна. Клиент может занимать эту сумму по частям, и нет никаких гарантий, что он возвратит часть денег до того, как сделает весь займ. Весь капитал банкира обычно меньше, чем суммарные требования клиентов, так как банкир не предполагает, что все клиенты сделают максимальные займы одновременно. Если в некоторый момент клиент запросит денежную сумму, банкир должен знать, сможет ли он ссудить ее без риска попасть в ситуацию, когда не будет достаточного количества денег, чтобы обеспечить дальнейшие займы, а именно это в конце концов позволяет клиентам возвратить долг. Чтобы ответить на этот вопрос, банкир предполагает, что он выполнил запрос и оценивает сложившуюся ситуацию. Он определяет клиента, чей текущий займ наиболее близок к максимальному. Если банкир не может ссудить оставшуюся сумму этому клиенту, то он отклоняет первоначальный запрос. Если же банкир может ссудить оставшуюся сумму, то он предполагает, что этот клиент полностью рассчитался (вернул выделенные ему денежные средства), и обращает свое внимание на того клиента из оставшихся, чей запрос ближе всего к своему лимиту. Просматривая таким образом всех клиентов, банкир каждый раз проверяет, будет ли у него достаточно денег, чтобы удовлетворить минимальный займ клиенту и предоставить последнему полную сумму. В случае, если это так, банкир удовлетворяет первоначальный займ. Если вместо «банкир», «клиент» и «денежные суммы» предполагать «операционная система», «процесс» и «ресурс», то можно применить этот алгоритм к вычислительным системам.

Пусть в вычислительной системе, имеющей m различных типов ресурсов, исполняется n процессов. Введем в рассмотрение следующие векторы и матрицы:

- вектор ресурсов R , определяющий полное количество каждого ресурса в системе

 

- вектор наличия AV (AVailable), устанавливающий количество каждого ресурса, не закрепленного за процессами

 

 

 

- матрицу требований C(Claim), задающую требуемое количество каждого типа ресурса для каждого процесса

 

 

 

- матрицу распределения A (Allocation), описывающую текущее распределение ресурсов между процессами

 

 

 

Указанные векторы и матрицы удовлетворяют следующим условиям:

- все ресурсы должны быть или распределены между процессами, или иметься в наличии;

- ни один процесс не может запросить больше ресурсов, чем их имеется в системе;

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

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

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

Рассмотрим действие алгоритма банкира на следующем примере. Пусть вычислительная система, в которой исполняется четыре процесса, содержит три вида ресурсов, а векторы ресурсов R, наличия AV и матрицы требований C и распределения A принимают значения как показано на рис.4.18,а.

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

 

Рис. 4.18. Пример распределения ресурсов согласно алгоритму банкира

 

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

При распределении ресурсов согласно алгоритму банкира, предложенному Дейкстрой, условия «взаимного исключения», «ожидания дополнительных ресурсов» и «неперераспределяемости» выполняются. Процессы могут претендовать на монопольное использование ресурсов, которые им требуются. Процессам реально разрешается удерживать за собой ресурсы, запрашивая и ожидая выделения дополнительных ресурсов, причем ресурсы нельзя отбирать у процесса, которому они выделены. Пользователи не став­ят перед системой особенно сложных задач, запрашивая в каждый момент времени только один ресурс. Система может либо удовлетворить, либо отклонить каждый запрос. Если запрос отклоняется, пользователь удерживает за собой уже выделенные ему ресурсы и ждет определенный конечный период времени, пока этот запрос в конце концов не будет удовлетворен. Система удовлетворяет только те запросы, при кото­рых ее состояние остается надежным. Запрос пользователя, приводящий к переходу системы в ненадежное состояние, откладывается до момента, когда его все же можно будет выполнить. Таким образом, поскольку система всегда поддерживается в надежном состоянии, рано или поздно (т. е. в течение конечного времени) все запросы можно будет удовлетворить, и все пользователи смогут завершить свою работу.

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

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

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

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

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

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

Распознавание дедлоков

 

Обнаружение тупика - это установление факта, что возникла тупиковая ситуация, и определение процессов и ресурсов, вовлеченных в эту тупиковую ситуацию. Алгоритмы обнаружения тупико­в, как правило, применяются в системах, где выполняются первые три необходимых условия возникновения тупиковой ситуации. Эти ал­горитмы затем определяют, не создался ли режим кругового ожидания.

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

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

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



©2015- 2017 stydopedia.ru Все материалы защищены законодательством РФ.