Гордеев А.В. Операционные системы (2-е изд., 2004) (1186250), страница 69

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 69)

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

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

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

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

В противном случае S не есть состояние тупика.Обнаружение тупика посредством редукции графаповторно используемых ресурсовНаиболее благоприятные условия для незаблокированного процесса Р; могут бытьпредставлены редукцией (сокращением) графа повторно используемых ресурсов(см. описание модели Холта ранее в разделе «Понятие тупиковой ситуации привыполнении параллельных вычислительных процессов»). Редукция графа можетбыть описана Следующим образом.•Граф повторно используемых ресурсов сокращается процессом Р;, который неявляется ни заблокированной, ни изолированной вершиной, путем удалениявсех ребер, входящих в вершину Р; и выходящих из Р;. Эта процедура являетсяэквивалентной приобретению процессом Р( неких ресурсов, на которые он ра-~нее выдавал запросы, а затем освобождению всех его ресурсов.

Тогда Pj стано­вится изолированной вершиной.Q Граф повторно используемых ресурсов несокращаем (не редуцируется), еслион не может быть сокращен ни одним процессом.•Граф ресурсов типа SR является полностью сокращаемым, если существуетпоследовательность сокращений, которая удаляет все дуги графа.Лемма: для ресурсов типа SR порядок сокращений дуг графа повторно используе­мых ресурсов несуществен; все последовательности ведут к одному и тому же не­сокращаемому графу.Допустим, что лемма неверна. Тогда должно существовать некоторое состояние S,которое сокращается до некоторого несокращаемого состояния S, с помощью пос­ледовательности seq, и до несокращаемого состояния S2 с помощью последователь­ности seq2 так, что S, Ф S2 (то есть все процессы в состояниях S, и S2 или заблокиро­ваны, или изолированы).Если сделать такое предположение, то мы приходим к противоречию, котороеустраняется только при условии, что S, = S2.

Действительно, предположим, чтопоследовательность seq, состоит из упорядоченного списка процессов (Pi, Рг< ••"Р к ). Тогда последовательность seq, должна содержать процесс Р, который не содер­жится в последовательности seq2. В противном случае S, = S2, потому что редукШ1Яграфа только удаляет дуги, уже существующие в состоянии S, а если последовательности seq! и seq2 содержат одно и то же множество процессов (пусть и в раз-Методы борьбы с тупиками«го»яичном порядке), то должно быть удалено одно и то же множество дуг. И доказа­тельство по индукции покажет, что Р Ф Р;, (i = 1,2,.... к) приводит к нашему проти­воречию.Имеет место соотношение Р Ф Р„ так как вершина S может быть редуцированаапроцессом Р[, а состояние S2 должно, следовательно, также содержать процесс Р,.р Пусть Р Ф Р|, (i = 1, 2, ..., j). Однако поскольку после редукции процессами Р„(i - 1, 2,..., j) возможно еще сокращение графа процессом P j+1 , это же самое дол­жно быть справедливо и для последовательности seq, независимо от порядкаследования процессов.

То же самое множество ребер графа удаляется с помо­щью процесса Р : . Таким образом, Р Ф P j+1 .Следовательно, Р Ф Р: для i = 1,2,..., к и Р не может существовать, а это противоре­чит нашему предположению, что Sj Ф S2. Следовательно, S, = S2.Теорема о тупике: Состояние S есть состояние тупика тогда и только тогда, когдаграф повторно используемых ресурсов в состоянии S не является полностью со­кращаемым.Q Для доказательства предположим, что состояние S есть состояние тупика, ипроцесс Pi находится в тупике в S. Тогда для всех S» таких что S•—> Sj про­цесс Р| заблокирован в состоянии Sj (по определению).

Так как сокращения гра­фа идентичны для серии операций процессов, то конечное несокращаемоесостояние в последовательности сокращений должно оставить процесс Р, бло­кированным. Следовательно, граф не является полностью сокращаемым.• Предположим теперь, что состояние S не является полностью сокращаемым.Тогда существует процесс Р„ который остается заблокированным при всех воз­можных последовательностях операций редукции в соответствии с леммой(см. выше). Так как любая последовательность операций редукции графа по­вторно используемых ресурсов, оканчивающаяся несокращаемым состоянием,гарантирует, что все ресурсы типа SR, которые могут когда-либо стать доступ­ными, в действительности освобождены, то процесс Р; навсегда заблокировани, следовательно, находится в тупике.Первое следствие: процесс Р, не находится в тупике тогда и только тогда, когдасерия сокращений приводит к состоянию, в котором Р| не заблокирован.Второе следствие: если S есть состояние тупика (по ресурсам типа SR), то по край­ней мере два процесса находятся в тупике в S.Из теоремы о тупике непосредственно следует и алгоритм обнаружения тупиков.Нужно просто попытаться сократить граф по возможности эффективным спосо­бом; если граф полностью не сокращается, то начальное состояние было состояни­ем тупика для тех процессов, вершины которых остались в несокращенном графе.Рассмотренная нами лемма позволяет предложить алгоритмы обнаружения тупи­ка.

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

В обоих случаях экономия памяти может быть достигнута за счет взве-270Глава 8. Проблема тупиков и методы борьбы с нимишенных ориентированных мультиграфов (слиянием определенных дуг полученияили дуг запроса между конкретным ресурсом и данным процессом в одну дугу ссоответствующим весом, определяющим количество единиц ресурса).Рассмотрим вариант с матричным представлением. Поскольку граф двудольныйон представляется двумя матрицами размером n x m. Одна матрица — матрицараспределения D = ||су|, в которой элемент d,, отражает количество единиц R.

ре_сурса, выделенного процессу P i ; то есть с1у = |(R|, Р,)|, где (R,, Р,) — это дуга междувершинами R( и Pj, ведущая из Rj в Pj. Вторая матрица — матрица запросов N = |jn|где п„ = |(Р,, R,)|.В случае использования связанных списков для отображения той же структурыможно построить две группы списков. Ресурсы, выделенные некоторому процессуР;, связаны с Р; указателями:Р:» (Rx> d x )> (Ry, d y )> ...> (R, d z ).Здесь Rj — вершина, представляющая ресурс, d, — вес дуги, то есть d| = |(R|, Pj)|.Подобным образом и ресурсы, запрошенные процессом Pj, связаны вместе.Аналогичные списки создаются и для ресурсов (списки распределенных и запро­шенных ресурсов):Ri> (Р„. п „)> (Р ¥ .

О>> (p„>nJ-Здесь п, = KPj, R : )|.Для обоих представлений удобно также иметь одномерный массив доступных еди­ниц ресурсов (г,, г2, ..., г,„), где Г; обозначает число доступных (нераспределенныхединиц) ресурса Rj, то есть г, = |Rj - £|(Rj, Pk)|.Простой метод прямого обнаружения тупика заключается в просмотре по порядкусписка (или матрицы) запросов, причем, где возможно, производятся сокращениядуг графа до тех пор, пока нельзя будет сделать более ни одного сокращения. Приэтом самая плохая ситуация возникает, когда процессы упорядочены в некоторойпоследовательности Р ( , Р 2 ,..., Р„, а единственно возможным порядком сокращенийявляется обратная последовательность, то есть Р,„ Р„.„ ..., Р 2 , Р„ а также в случае,когда процесс запрашивает все m ресурсов.

Тогда число проверок процессов равно:n + ( n - l ) + ...+ l = n - ( n + l)/2.Таким образом, время выполнения такого алгоритма в наихудшем случае пропор­ционально m х п2, поскольку каждая проверка требует испытания m ресурсов.Более эффективный алгоритм может быть получен за счет хранения некоторойдополнительной информации о запросах. Для каждой вершины процесса Р, опре­деляется так называемый счетчик ожиданий Wj, отображающий количество ресур­сов (не число единиц ресурса), которые в какое-то время вызывают блокировкупроцесса.

Характеристики

Список файлов книги