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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Часто используемый подход называется двухфазным блокированием. В первой фазе, то есть на первом этапе, процесс пытается заблокировать все требуемые записи по одной за раз. Если операция успешна, процесс переходит ко второму

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

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

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

3.4. Обзор ввода/вывода в MINIX

Структура системы ввода/вывода в MINIX показана на рис. 3.4. Четыре верхних уровня этой структуры соответствуют четырем уровням с рис. 2.14. В последующих разделах мы вкратце рассмотрим каждый из этих уровней, делая акцент на драйверах устройств. Обработка прерываний в MINIX была рассмотрена в предыдущей главе, а аппаратно-зависимый ввод/вывод будет обсуждаться в главе 5.

3.4.1. Обработчики прерываний в MINIX

Большинство драйверов инициируют ввод/вывод и переходят в состояние блокировки, ожидая, когда прибудет сообщение. Обычно это сообщение генерируется обработчиком прерываний устройства. Существуют другие драйверы, которые не запускают физических процессов ввода/вывода (пример - чтение с RAM-диска или вывод текста на отображаемый в память экран - видеопамять), не опираются на прерывания и не ждут сообщений от устройств. Механизм генерации сообщений и переключения задач, управляемый прерываниями, в предыдущей главе обсуждался очень подробно, и ниже нечего добавить. Но обработчики прерываний не только генерируют сообщения. Часто они делают некоторую обработку входных и выходных данных на самом низком уровне. Здесь мы рассмотрим это применение в общем, а детально мы вернемся к этой теме, когда будем демонстрировать код для различных устройств.

Обратимся теперь к некоторым реальным усфойствам ввода/вывода. Мы начнем с дисков. Затем мы также познакомимся с часами, клавиатурами и экранами.