АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

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

Наиболее благоприятные условия для незаблокированного процесса pj могут быть представлены редукцией (сокращением) графа повторно используемых ресурсов (см. первый раздел данной главы, описание модели Холта). Редукция графа мо­жет быть описана следующим образом:

Q Граф повторно используемых ресурсов сокращается процессом Р_ь который не является ни заблокированной, ни изолированной вершиной, с помощью удаления всех ребер, входящих в вершину pj и выходящих из pj. Эта процеду­ра является эквивалентной приобретению процессом pj неких ресурсов, на которые он ранее выдавал запросы, а затем освобождению всех его ресурсов. Тогда pj становится изолированной вершиной.

О Граф повторно используемых ресурсов несокращаем (не редуцируется), если он не может быть сокращен ни одним процессом.

Q Граф ресурсов типа RS является полностью сокращаемым, если существует последовательность сокращений, которая удаляет все дуги графа.

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

Лемма. Для ресурсов типа SR порядок сокращений несуществен; все последова­тельности ведут к одному и тому же несокращаемому графу.

Доказательство. Допустим, что лемма неверна. Тогда должно существовать не­которое состояние S, которое сокращается до некоторого несокращаемого со­стояния Si с помощью последовательности seq_t и до несокращаемого состояния S₂ — с помощью последовательности seq₂ так, что S(# S₂ (то есть все процессы в состояниях 5]И S₂ или заблокированы, или изолированы).

Если сделать такое предположение, то мы приходим к противоречию, которое устраняется только при условии, что S₍ - S₂. Действительно, предположим, что последовательность seqj состоит из упорядоченного списка процессов (Р₍,?2i -I Pfc)- Тогда последовательность seqj должна содержать процесс Р, который не содержится в последовательности seq₂. В противном случае S_t = S₂, потому что редукция графа только удаляет дуги, уже существующие в состоянии S, a если последовательности seql и seq₂ содержат одно и то же множество процес­сов (пусть и в различном порядке), то должно быть удалено одно и то же множе­ство дуг. И доказательство по индукции покажет, что Р * P_iF (i - 1, 2,..., k) приво­дит к указанному нами противоречию.

Q Р * pj, так как вершина S может быть редуцирована процессом Р₁₍ а состоя­ние S₂ должно, следовательно, также содержать процесс Р,.

Q Пусть Р Ф Р_ь (i = 1,2,..., j). Однако, поскольку после редукции процессами pj, (i = 1, 2,..., j) возможно еще сокращение графа процессом Pj₊₁, это же самое должно быть справедливо и для последовательности seq₂ независимо от по­рядка следования процессов. То же самое множество ребер графа удаляется с помощью процесса Р;. Таким образом, Р # Pj₊₁.

Следовательно, Р * Р, для i = 1,2,..., k и Р не может существовать, а это противо­речит нашему предположению, что S₍ * S₂. Следовательно, S_f - S₂.

Теорема о тупике. Состояние S есть состояние тупика тогда и только тогда, когда граф повторно используемых ресурсов в состоянии S не является полностью со­кращаемым.

Доказательство.

а) Предположим, что состояние S есть состояние тупика и процесс pj находится
в тупике в S. Тогда для всех Sj, таких что S —-— > Sj, процесс Р, заблокирован
в Sj (по определению). Так как сокращения графа идентичны для серии опе­
раций процессов, то конечное несокращаемое состояние в последовательно­
сти сокращений должно оставить процесс pj блокированным. Следовательно,
граф не является полностью сокращаемым.

б) Предположим, что S не является полностью сокращаемым. Тогда существует
процесс pj, который остается заблокированным при всех возможных последо­
вательностях операций редукции в соответствие с леммой. Так как любая по­
следовательность операций редукции графа повторно используемых ресурсов,
оканчивающаяся несокращаемым состоянием, гарантирует, что все ресурсы
типа SR, которые могут когда-либо стать доступными, в действительности ос­
вобождены, то процесс р! навсегда заблокирован и, следовательно, находится
в тупике.

Следствие 1. Процесс Р_{ не находится в тупике тогда и только тогда, когда серия сокращений приводит к состоянию, в котором pj не заблокирован.

Следствие 2. Если S есть состояние тупика (по ресурсам типа SR), то по крайней мере два процесса находятся в тупике в S.

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

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

Рассмотрим вариант с матричным представлением. Поскольку граф двудольный, он представляется двумя матрицами размером nxm. Одна матрица — матрица

распределения D = ||dy||, в которой элемент dy отражает количество единиц rj ре­сурса, распределенного процессу pj, то есть dy = |(Rj, Pj)|, где (Rj, Р,) — это дуга между вершинами rj и pj, ведущая из rj в Р|. Вторая матрица — матрица запро­сов N - ||пу||, где пу - |(Р„ Rj)|.

В случае использования связанных списков для отображения той же структу­ры можно построить две группы списков. Ресурсы, распределенные некоторому процессу P_it связаны с pj указателями:

pj------- >(R_X, d_x)--------- KR_y, d_y)---------- >...-------- >(R_Z, d_z), где rj — вершина, представ­
ляющая ресурс, и dj — вес дуги, то есть dj = |(Rj, P|)|.

Подобным образом и ресурсы, запрошенные процессом Р₍, связаны вместе.

Аналогичные списки создаются и для ресурсов (списки распределенных и запро­шенных ресурсов).

ri------- >(Р_Ц, ⁿu)---------- KPv, n_v)------- >...-------- KPw.n_w), где hj - |(Pj, rj)|.

Для обоих представлений удобно также иметь одномерный массив доступных единиц ресурсов (г\, г₂,..., r_m), где г_: указывает число доступных (нераспределен­ных единиц ресурса rj, то есть fj = |Rj| — £|(Rj, Pk)|.

Простой метод прямого обнаружения тупика заключается в просмотре по поряд­
ку списка (или матрицы) запросов, причем, где возможно, производятся сокра­
щения дуг графа до тех пор, пока нельзя будет сделать более ни одного сокраще­
ния. При этом самая плохая ситуация возникает, когда процессы упорядочены в
некоторой последовательности Р,, Р₂,..., Р„, а единственно возможным поряд­
ком сокращений является обратная последовательность, то есть Р„, P_n.j Р₂, pi,

а также в случае, когда процесс запрашивает все m ресурсов. Тогда число прове­рок процессов равно

п + (п-1) +... + 1 = пх(п+1)/2,

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

Более эффективный алгоритм может быть получен за счет хранения некоторой дополнительной информации о запросах. Для каждой вершины процесса pj оп­ределяется так называемый счетчик ожиданий Wj, отображающий количество ре­сурсов (не число единиц ресурса), которые в какое-то время вызывают блоки­ровку процесса. Кроме этого, можно сохранять для каждого ресурса запросы, упорядоченные по размеру (числу единиц ресурса). Тогда следующий алгоритм сокращений, записанный на псевдокоде, имеет максимальное время выполнения, пропорциональное mxn.

For all P e L do

Begin for all Rj э |(Rj.P)| > 0 do Begin r,:- r, * |(Rj.P)|:

For all P, э 0 < |(P,.Rj)| <- r-j do Begin w,:- w, - 1;

If w, - 0 then L:- L U {Pi} End End

End

Deadlock:- Not (L = {PI, P2.... Pn}):

Здесь L — это текущий список процессов, которые могут выполнять редукцию графа. Можно сказать, что L:- {Pj | Wj - 0}. Программа выбирает процесс Р из списка L, процесс Р сокращает граф, увеличивая число доступных единиц tj всех ресурсов rj, распределенных процессу Р, обновляет счетчик ожидания w_; каждо­го процесса pj, который сможет удовлетворить свой запрос на частный ресурс rj, и добавляет pj к L, если счетчик ожидания становится нулевым.

Дата добавления: 2015-01-18 | Просмотры: 874 | Нарушение авторских прав