Алгоритм банкиров Дейкстры
Может ли кто-нибудь предоставить пошаговый подход к решению следующей проблемы с использованием алгоритма банкира? Как определить, существует ли "безопасное состояние"? Что имеется в виду, когда процесс может "завершиться"?
В этом примере у меня есть четыре процесса и 10 экземпляров одного и того же ресурса.
Resources Allocated | Resources Needed
Process A 1 6
Process B 1 5
Process C 2 4
Process D 4 7
2 ответа
В Википедии,
Состояние (как в приведенном выше примере) считается безопасным, если все процессы могут завершиться (завершиться). Поскольку система не может знать, когда процесс завершится или сколько ресурсов будет запрошено к тому времени, система предполагает, что все процессы в конечном итоге попытаются получить свои заявленные максимальные ресурсы и вскоре завершатся. В большинстве случаев это разумное предположение, так как система не особо заботится о том, как долго выполняется каждый процесс (по крайней мере, не с точки зрения предотвращения тупиков). Кроме того, если процесс завершается без получения максимальных ресурсов, это только облегчает работу системы.
Процесс может завершиться до конца, когда число каждого типа ресурса, которое ему нужно, доступно между собой и системой. Если процессу требуется 8 единиц данного ресурса, и он выделил 5 единиц, он может завершиться до завершения, если есть еще как минимум 3 единицы, которые он может выделить.
В вашем примере система управляет одним ресурсом с 10 доступными единицами. Запущенные процессы уже выделили 8 (1+1+2+4) единиц, поэтому осталось 2 единицы. Сумма, которую должен завершить любой процесс, - это его максимум меньше того, что он уже выделил, поэтому в начале A нужно еще 5 (6-1), B нужно еще 4 (5-1), C нужно еще 2 (4-2), а D нужно еще 3 (7-4). Доступно 2, поэтому процесс C может быть запущен до завершения, что освобождает 2 блока (оставляя 4 доступных). В этот момент можно запустить B или D (предположим, D). После завершения D будет доступно 8 единиц, после чего можно запустить A или B (предположим, A). После завершения A будет доступно 9 единиц, а затем можно будет запустить B, что оставит все 10 единиц для дальнейшей работы. Поскольку мы можем выбрать порядок процессов, который позволит запускать все процессы, состояние считается "безопасным".
Resources Allocated | Resources Needed claim
Process A 1 6 5
Process B 1 5 4
Process C 2 4 2
Process D 4 7 3
Общее количество выделенных ресурсов равно 8. Следовательно, 2 ресурса еще предстоит распределить, следовательно, которые выделены для процесса С., а процесс с после завершения освобождает 4 ресурса, которые могут быть переданы процессу В, Процесс В после завершения восстанавливает 5 ресурсов, которые выделены для ПРОЦЕССА А n процесс A после завершения выделяет 2 ресурса для процесса D