Алгоритм Банкира. Алгоритм_банкира_Осипова_Анастасия. Алгоритм банкира Алгоритм банкира
 Скачать 33.37 Kb.
|
|
Алгоритм банкира Алгоритм банкира для безопасного распределения ресурсов операционной системой (с избежанием тупиков) был предложен Э. Дейкстрой и впервые реализован в операционной системе THE в конце 1960-х гг. Алгоритм базируется на так называемых безопасных или надёжных состояниях. Безопасное состояние — это такое состояние, для которого имеется по крайней мере одна последовательность событий, которая не приведёт к тупику. Происхождение названия связано с тем, что поведение алгоритма напоминает осторожную стратегию банкира при проведении банковских операций. Принципы алгоритма банкира следующие: · Каждый процесс должен априорно обозначить свои потребности в ресурсах по максимуму. · Когда процесс запрашивает ресурс, ему, возможно придется подождать (выделение ресурсов по запросу не всегда может произойти немедленно). · Когда процесс получает требуемые ресурсы, он должен их вернуть системе за ограниченный период времени. Процессы в компьютере используют ресурсы, выделяемые им операционной системой. Так как ресурсы не бесконечны, то каждый процесс в определённый момент владеет лишь некоторым количеством ресурсов, так как другие ресурсы удерживаются другими процессами. Для завершения задачи необходимо некоторое количество ресурсов, а если такого нет, то возникает тупиковая ситуация. Тупик - момент, когда процессы ожидают высвобождения ресурсов другого процесса и так далее (круг - процесс, квадрат - ресурс).  Из картинки видно, что: Процесс P1 ожидает высвобождения ресурса R1. Ресурс R1 захвачен (используется) процессом P2. Процесс P2 ожидает высвобождения ресурса R2. Ресурс P1 захвачен (используется) процессом P1. Таким образом, граф распределения ресурсов имеет циклическую структуру, что говорит о наличии тупика в системе. Данный алгоритм обладает тем достоинством, что при его использовании нет необходимости в перераспределении ресурсов и откате процессов назад. Однако использование этого метода требует выполнения ряда условий: Число процессов и число ресурсов должно быть фиксировано. Число работающих процессов не должно не увеличиваться. И не должно появляться новых процессов. Алгоритм требует, чтобы клиенты гарантированно возвращали ресурсы. Должны быть заранее указаны максимальные требования процессов к ресурсам. Чаще всего данная информация отсутствует. Кроме того, во многих случаях гарантия завершения любого процесса в течение конечного времени является недостаточной. Требуется более точная и предсказуемая оценка времени завершения. Сегодня проблема тупиков стоит все острее т.к.: Увеличивается количество одновременно выполняющихся процессов. Ресурсы распределяются динамически (во время выполнения программы). Увеличивается количество типов ресурсов (сейчас данные рассматриваются как ресурс). Каждый раз, когда какой-то остаток, может быть выделен процессу из числа свободных устройств, предполагается, что соответствующий процесс работает до завершения, а затем его устройства освобождаются. Если, в конце концов, все устройства освободятся, значит все процессы могут завершиться и система находится в безопасном состоянии. Кроме того, алгоритм имеет ряд существенных недостатков: · исходит из фиксированного числа распределяемых ресурсов · требует, чтобы число процессов оставалось постоянным · требует, чтобы процессы гарантированно возвращали выделенные им ресурсы в течение некоторого конечного времени · требует, чтобы пользователи заранее указывали свои максимальные потребности в ресурсах Вывод: Алгоритм банкира – алгоритм распределения ресурсов операционной системой, обеспечивающий избежание тупиков. Его условия и принципы: возможны множественные экземпляры ресурсов; каждый процесс должен априорно обозначить свои максимальные потребности в ресурсах; при запросе ресурса возможно ожидание процесса; после получения ресурсов процесс должен вернуть их за ограниченный период времени. Для работы алгоритма используются вектордоступности ресурсов каждого вида, матрица максимальных потребностей процессов, матрица фактического выделения системой ресурсов процессам, матрица оставшихся потребностей процессов в ресурсах. |