Глава_3 (1085731), страница 6

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

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

D 0 7 D 4 7 D 4 7

С вободно 10 Свободно 2 Свободно 1

а б в

Рис. 3.9. Три состояния распределения ресурсов: безопасное (а); безопасное (б); небезопасное (в)

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

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

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

Алгоритм банкира для нескольких видов ресурсов

Алгоритм банкира можно обобщить для управления системой с несколькими ви­дами ресурсов. На рис. 3.10 показано, как он работает.

Е = (6342) Р = (5322) А = (1020)

Распределенные ресурсы

Ресурсы, которые еще нужны

Рис. 3.10. Алгоритм банкира в системе с несколькими типами ресурсов

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

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

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

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

2. Допускаем, что процесс, строку которого выбрали в пункте 1, запрашивает
   все необходимые ресурсы (гарантируется, что это возможно) и заканчивает
   работу. Отмечаем этот процесс как завершенный и прибавляем все его ресур­-
   сы к вектору А.

3. Повторяем шаги 1 и 2 до тех пор, пока или все процессы будут помечены как завершенные — и состояние в этом случае является безопасным, или произойдет взаимоблокировка — тогда состояние небезопасно.

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

Теперь вернемся к примеру на рис. 3.10. Текущее состояние является безопас­ным. Предположим, что процесс В в данный момент запрашивает принтер. На этот запрос можно ответить положительно, потому что получающееся в результате со­стояние все еще будет безопасным (процесс D может доработать до конца, затем процесс А или Е, затем остальные).

Теперь представим, что после того, как процесс В получил один из двух остав­шихся принтеров, процесс E потребует последний принтер. Удовлетворение этого запроса сократит вектор доступных ресурсов до (1 0 0 0), что приведет к взаимо­блокировке процессов. Ясно, что следует отложить на время запрос процесса Е.

Дейкстра (Dijkstra) впервые опубликовал алгоритм банкира в 1965 году. С тех пор практически каждая книга по операционным системам описывает его в дета­лях. Различным аспектам этого алгоритма было посвящено бессчетное количество статей. К сожалению, мало у кого из авторов хватило смелости показать, что хотя алгоритм замечателен в теории, на практике он, по существу, бесполезен, потому что нечасто можно определить заранее, сколько ресурсов потребуется процессам в будущем. Кроме того, количество процессов не фиксировано, оно динамически изменяется по мере входа пользователей в систему и выхода из нее. И, более того, ресурсы, про которые считалось, что они доступны, могут внезапно исчезнуть (например, накопитель на магнитной ленте может сломаться). Таким образом, на практике немногие системы, если это вообще имеет место, используют алгоритм банкира для уклонения от взаимоблокировок.

Предотвращение взаимоблокировок

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

Атака условия взаимного исключения

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

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

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

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

Атака условия удержания и ожидания

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

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

¹ Подкачка или спулинг (spooling) — процесс обработки посылаемых на печать документов, кото­рые сохраняются на диске до момента, когда печатающее устройство сможет ИХ обработать. —

¹ ДемОН — скрытая от пользователя служебная программа, работающая в фоновом режиме.

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

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

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

Атака условия отсутствия принудительной выгрузки ресурса

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

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

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