Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Алгоритм банкира

Алгоритм банкира (Э. Дейкстра) – алгоритм распределения ресурсов операционной системой, обеспечивающий избежание тупиков. Его условия и принципы: возможны множественные экземпляры ресурсов; каждый процесс должен априорно обозначить свои максимальные потребности в ресурсах; при запросе ресурса возможно ожидание процесса; после получения ресурсов процесс должен вернуть их за ограниченный период времени. Для работы алгоритма используются вектор доступности ресурсов каждого вида, матрица максимальных потребностей процессов, матрица фактического выделения системой ресурсов процессам, матрица оставшихся потребностей процессов в ресурсах.

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

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

Другая возможная стратегия – обнаружение тупиков: позволить системе войти в состояние тупика, применить алгоритм обнаружения тупиков и выполнить схему восстановления после тупика.

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

После обнаружения тупиков система определяет, какое минимальное число процессов необходимо прекратить для ликвидации тупика. Для выбора процесса-жертвы существует ряд критериев, например, приоритет процесса или оставшееся время его выполнения. При прекращении процесса его ресурсы освобождаются.

Комбинированный подход к обработке тупиков сочетает в себе все три рассмотренных стратегии – предотвращение, избежание и обнаружение. Система подразделяет ресурсы на иерархически упорядоченные классы. Для каждого класса используется наиболее оптимальная стратегия.