Файл: А. В. Гордеев А. Ю. Молчанов системное программное обеспечение электронный вариант книги издательства Питер СанктПетербург Челябинск юургу каф. Автоматика и управление 2002 2 Предисловие Настоящий учебник.pdf

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

369
точно легко, в то время как перераспределение устройств ввода/вывода крайне не- желательно.
Условие кругового ожидания можно исключить, предотвращая образование цепи запросов. Это можно обеспечить с помощью принципа иерархического выде-
ления ресурсов. Все ресурсы образуют некоторую иерархию. Процесс, затребовав- ший ресурс на одном уровне, может затем потребовать ресурсы только на более высоком уровне. Он может освободить ресурсы на данном уровне только после ос- вобождения всех ресурсов на всех более высоких уровнях. После того как процесс получил, а потом освободил ресурсы данного уровня, он может запросить ресурсы на том же самом уровне. Пусть имеются процессы ПР1 и ПР2, которые могут иметь доступ к ресурсам R1 и R2, причем R2 находится на более высоком уровне иерархии. Если ПР1 захватил R1, то ПР2 не может захватить R2, так как доступ к нему проходит через доступ к R1, который уже захвачен ПР1. Таким образом, соз- дание замкнутой цепи исключается. Иерархическое выделение ресурсов часто не дает никакого выигрыша, если порядок использования ресурсов, определенный в описании процессов, отличается от порядка уровней иерархии. В этом случае ре- сурсы будут использоваться крайне неэффективно.
В целом стратегия предотвращения тупиков – это очень дорогое решение про- блемы, и она используется нечасто.
Обход тупиков
Обход тупика можно интерпретировать как запрет входа в опасное состояние.
Если ни одно из упомянутых четырех условий не исключено, то вход в опасное со- стояние можно предотвратить при наличии у системы информации о последова- тельности запросов, связанных с каждым параллельным процессом. Доказано [92],
что если вычисления находятся в любом неопасном состоянии, то существует по крайней мере одна последовательность состояний, которая обходит опасное. Сле- довательно, достаточно проверить, не приведет ли выделение затребованного ре- сурса сразу же к опасному состоянию. Если да, то запрос отклоняется. Если нет,
его можно выполнить. Определение того, является ли состояние опасным или нет,
требует анализа последующих запросов процессов.

370
Рассмотрим следующий пример. Пусть имеется система из трех вычислитель- ных процессов, которые потребляют некоторый ресурс R типа SR, который выде- ляется дискретными взаимозаменяемыми единицами, причем существует всего де- сять единиц этого ресурса. В табл. 7.2 приведены сведения о текущем распределе- нии процессами этого ресурса R, об их текущих запросах на этот ресурс и о макси- мальных потребностях процессов в ресурсе R.
Последний столбец в табл. 7.2 показывает, сколько ещё единиц ресурса может затребовать каждый из процессов, если получит ресурс на свой текущий запрос.
Если запрос процесса А будет удовлетворен первым, то он в принципе может запросить еще одну единицу ресурса R, и уже в этом случае мы тогда получим ту- пиковую ситуацию, поскольку ни один из процессов не сможет продолжить свои вычисления. Следовательно, при выполнении запроса процесса А мы попадаем в
ненадежное
1
состояние.

371
перь уже можно будет выполнить запрос либо процесса В, либо процесса А, но не обоих сразу.
Часто бывает так, что последовательность запросов, связанных с каждым про- цессом, неизвестна заранее. Но если заранее известен общий запрос на ресурсы каждого типа, то выделение ресурсов можно контролировать. В этом случае необ- ходимо для каждого требования, предполагая, что оно удовлетворено, определить,
существует ли среди общих запросов от всех процессов некоторая последователь- ность требований, которая может привести к опасному состоянию. Данный подход является примером контролируемого выделения ресурса.
Классическое решение этой задачи известно как алгоритм банкира Дейкстры
[89]. Алгоритм банкира напоминает процедуру принятия решения, может ли банк безопасно для себя дать взаймы денег. Принятие решения основывается на инфор- мации о потребностях клиента (текущих и максимально возможных) и учёте те- кущего баланса банка. Несмотря на то, что этот алгоритм нигде практически не ис- пользуется, рассмотрим его, так как он интересен с методической и академической точек зрения. Текст программы алгоритма банкира приведен в листинге 7.4.
Пусть существует N процессов, для каждого из которых известно максималь- ное количество потребностей в некотором ресурсе R (обозначим эти потребности через
Max(i)
). Ресурсы выделяются не сразу все, а в соответствии с текущим запро- сом. Считается, что все ресурсы i-го процесса будут освобождены по его заверше- нии. Количество полученных ресурсов для i-го процесса обозначим
Получ(i)
. Оста- ток в потребностях i-го процесса на ресурс R обозначим через
Остаток(i)
. Признак того, что процесс может не завершиться – это значение false для переменной
За- верш(i)
. Наконец, переменная
Своб_рес будет означать количество свободных еди- ниц ресурса R, а максимальное количество ресурсов в системе определено значе- нием
Всего_рес
Листинг 7.4. Алгоритм банкира Дейкстры
Begin
Своб_рес := Всего_рес;
For i := 1 to N do
Begin

372
Своб_рес := Своб_рес – Получ(i);
Остаток(i) := Мах(i) – Получ(i);
Заверш(i) := false: { процесс может не завершиться }
end flag := true; ( признак продолжения анализа }
while flag do begin flag := false;
for i := 1 to N do begin if ( not ( За верш(i) )) and ( Остаток(i) <= Своб_рес )
then begin
Заверш(i) := true;
Своб_рес := Своб_рес + Получ(i);
Flag := true end end end;
If Своб_рес = Bcero_pec then Состояние системы безопасное и можно выдать ресурс else Состояние не безопасное и выдавать ресурс нельзя end.
Каждый раз, когда какой-то остаток может быть выделен из числа остающихся незанятыми ресурсов, предполагается, что соответствующий процесс работает, по- ка не окончится, а затем его ресурсы освобождаются. Если, в конце концов, все ре- сурсы освобождаются, значит, все процессы могут завершиться и система находит- ся в безопасном состоянии. Другими словами, согласно алгоритму банкира система удовлетворяет только те запросы, при которых её состояние остается надёжным.
Новое состояние безопасно тогда и только тогда, когда каждый процесс все же мо- жет окончиться. Именно это условие и проверяется в алгоритме банкиpa. Запросы процессов, приводящие к переходу системы в ненадёжное состояние, не выполня- ются и откладываются до момента, когда его всё же можно будет выполнить.

373
Алгоритм банкира позволяет продолжать выполнение таких процессов, кото- рым в случае системы с предотвращением тупиков пришлось бы ждать. Хотя алго- ритм банкира относительно прост, его реализация может обойтись довольно доро- го. Основным накладным расходом стратегии обхода тупика с помощью контроли- руемого выделения ресурса является время выполнения алгоритма, так как он вы- полняется при каждом запросе. Причем алгоритм работает медленнее всего, когда система близка к тупику. Необходимо отметить, что обход тупика неприменим при отсутствии информации о требованиях процессов на ресурсы.
Рассмотренный алгоритм примитивен, в нём учитывается только один вид ре- сурса, тогда как в реальных системах количество различных типов ресурсов бывает очень большим. Были опубликованы варианты этого алгоритма для большого чис- ла различных типов системных ресурсов. Однако все равно алгоритм не получил распространения. Причин тому несколько:
♦ Алгоритм исходит из того, что количество распределяемых ресурсов в сис- теме фиксировано, постоянно. Иногда это не так, например, вследствие неисправ- ности отдельных устройств.
♦ Алгоритм требует, чтобы пользователи заранее указывали свои максималь- ные потребности в ресурсах. Это чрезвычайно трудно реализовать. Часть таких сведений, конечно, могла бы подготавливать система программирования, но всё
равно часть информации о потребностях в ресурсах должны давать пользователи.
Однако, поскольку компьютеры становятся всё более дружественными по отноше- нию к пользователям, всё чаще встречаются пользователи, которые не имеют ни малейшего представления о том, какие ресурсы им потребуются.
♦ Алгоритм требует, чтобы число работающих процессов оставалось посто- янным. Это возможно только для очень редких случаев. Очевидно, что выполнение этого требования в общем случае не реально, особенно в мультитерминальных сис- темах либо если пользователь может запускать по несколько процессов параллель- но.

374
Обнаружение тупика
Чтобы распознать тупиковое состояние, необходимо для каждого процесса определить, сможет ли он когда-либо снова развиваться, то есть изменять свои со- стояния. Так как нас интересует возможность развития процесса, а не сам процесс смены состояния, то достаточно рассмотреть только самые благоприятные измене- ния состояния.
Очевидно, что незаблокированный процесс (он только что получил ресурс и поэтому не заблокирован) через некоторое время освобождает все свои ресурсы и затем благополучно завершается. Освобождение ранее занятых ресурсов может
«разбудить» некоторые ранее заблокированные процессы, которые, в свою оче- редь, развиваясь, смогут освободить другие ранее занятые ресурсы. Это может продолжаться до тех пор, пока либо не останется незаблокированных процессов,
либо какое-то количество процессов всё же останется заблокированными. В по- следнем случае (если существуют заблокированные процессы при завершении ука- занной последовательности действий) начальное состояние S является состоянием тупика, а оставшиеся процессы находятся в тупике в состоянии S. В противном случае S не есть состояние тупика.
Обнаружение тупика посредством редукции графа повторно используемых ресурсов
Наиболее благоприятные условия для незаблокированного процесса Р
i могут быть представлены редукцией (сокращением) графа повторно используемых ресур- сов (см. первый раздел данной главы, описание модели Холта). Редукция графа мо- жет быть описана следующим образом:
♦ Граф повторно используемых ресурсов сокращается процессом Рр который не является ни заблокированной, ни изолированной вершиной, с помощью удале- ния всех ребер, входящих в вершину Р
i и выходящих из Р
i
. Эта процедура является эквивалентной приобретению процессом Р
i неких ресурсов, на которые он ранее выдавал запросы, а затем освобождению всех его ресурсов. Тогда P
i становится изолированной вершиной.
♦ Граф повторно используемых ресурсов несокращаем (не редуцируется), ес- ли он не может быть сокращен ни одним процессом.

375
♦ Граф ресурсов типа RS является полностью сокращаемым, если существует последовательность сокращений, которая удаляет все дуги графа.
Приведем лемму, которая позволяет предложить алгоритмы обнаружения ту- пика.
Лемма. Для ресурсов типа SR порядок сокращений несуществен; все последо- вательности ведут к одному и тому же несокращаемому графу.
Доказательство. Допустим, что лемма неверна. Тогда должно существовать некоторое состояние S, которое сокращается до некоторого несокращаемого со- стояния S
1
с помощью последовательности seq
1
и до несокращаемого состояния S
2
– с помощью последовательности seq
2
так, что S
1
≠ S
2
(то есть все процессы в со- стояниях S
1
и S
2
или заблокированы, или изолированы).
Если сделать такое предположение, то мы приходим к противоречию, которое устраняется только при условии, что S
1
= S
2
. Действительно, предположим, что по- следовательность seq
1
состоит из упорядоченного списка процессов (P
1
, P
2
, ... , P
k
).
Тогда последовательность seq
1
должна содержать процесс Р, который не содержит- ся в последовательности seq
2
. В противном случае S
1
= S
2
, потому что редукция графа только удаляет дуги, уже существующие в состоянии S, а если последова- тельности seq
1
и seq
2
содержат одно и то же множество процессов (пусть и в раз- личном порядке), то должно быть удалено одно и то же множество дуг. И доказа- тельство по индукции покажет, что Р
≠ Р
i
(i = 1,2,..., k) приводит к указанному нами противоречию.
♦ Р ≠ P
1
, так как вершина S может быть редуцирована процессом P
1
, а состоя- ние S
2
должно, следовательно, также содержать процесс P
1
♦ Пусть Р ≠ P
i
, (i = 1, 2, ... , j). Однако, поскольку после редукции процессами
P
i
(i = 1, 2, ... , j) возможно ещё сокращение графа процессом P
j+1
, это же самое должно быть справедливо и для последовательности seq
2
независимо от порядка следования процессов. То же самое множество рёбер графа удаляется с помощью процесса P
i
.
Таким образом, Р
≠ P
j+1
Следовательно, Р
≠ P
i для i = 1, 2, ..., k и Р не может существовать, а это про- тиворечит нашему предположению, что S
1
≠ S
2
. Следовательно, S
1
= S
2