Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Структуры данных для алгоритма банкира
Пусть в системе имеется n процессов и m типов ресурсов. Вектор Available длины m содержит информацию о доступных ресурсах. Если Avaliable[j] = k,то в системе в данный момент доступно k единиц ресурса j. Матрица Max (n * m) отображает максимальные потребности процессов в ресурсах. Если Max [i, j] = k,то процесс i может запросить, самое большее, k единиц ресурса j. Матрица Allocation (n * m) отображает фактическое выделение системой ресурсов. Если Allocation [i, j] = k,то процессу i в данный момент выделено системой k единиц ресурса j. Матрица Need (n * m) отображает оставшиеся потребности процессов в ресурсах. Если Need [i, j] = k,то процессу i могут потребоваться еще k единиц ресурса j для завершения работы. Имеет место следующее соотношение между элементами матриц: Need [i, j] = Max [i, j] – Allocation [i, j]. Алгоритм проверки состояния системы на безопасность В обозначениях раздела Структуры данных для алгоритма банкира, рассмотрим алгоритм проверки состояния системы на то, является ли оно безопасным. Введем целочисленный вектор Work (длины m) и булевский вектор Finish (длины n). Вектор Work отображает пробные выделения ресурсов. Вектор Finish представляет информацию о завершаемости процессов при данном состоянии системы. Алгоритм безопасности. Шаг 1. Инициализация. Work = Available Finish [i] = false для i = 1, …, n. Здесь и в дальнейшем все присваивания и сравнения, в которых участвуют векторы или матрицы, выполняются поэлементно. Шаг 2. Находим i, такое, что: Finish [i] = false Need [i] <= Work Если такого i нет, переходим к шагу 4. Шаг 3. Work = Work + Allocation [i] Finish [i] = true Переход к шагу 2. Шаг 4. Если Finish[i] = true для всех i = 1, …, n, то система в безопасном состоянии. Необходимые пояснения к алгоритму: · Алгоритм строит безопасную последовательность номеров процессов i, если она существует. На каждом шаге, после обнаружения очередного элемента последовательности, алгоритм моделирует освобождение i - м процессом ресурсов после его завершения. · На шаге 1 присваивание векторов выполняется поэлементно. · На шаге 2, Need – матрица потребностей (n * m); Need[i] - строка матрицы, представляющая вектор потребностей (длины m) процесса i. Сравнение выполняется поэлементно, и его результат считается истинным, если соотношение выполнено для всех элементов векторов. Проверяемое условие означает, что потребности процесса i с найденным номером могут быть удовлетворены немедленно, и процесс может получить их и завершиться.
· На шаге 3, Allocation [i] – строка матрицы Allocation, обозначающая текущие ресурсы, выделенные процессу i. С помощью вектора Work моделируется освобождение ресурсов i – м процессом, после чего процессу присваивается признак завершаемости. Формальное доказательство корректности алгоритма и оценку его сложности предоставляем студенту. Алгоритм запроса ресурсов для процесса Pi – основная часть алгоритма банкира Для основного алгоритма введем вектор Requesti (длины m) – вектор запросов для процесса Pi. Если Requesti [j] = k,то процесс Pi запрашивает k экземпляров ресурса Rj. Шаг 1. Если Requesti <= Need[i], перейти к шагу 2. Иначе – сгенерировать исключительную ситуацию (процесс превысил свои максимальные потребности). Шаг 2. Если Requesti <= Available, перейти к шагу 3. Иначе процесс должен ждать, так как ресурс недоступен. Шаг 3. Спланировать выделение ресурса процессу Pi, модифицируя состояние системы следующим образом: Available = Available - Requesti Allocation = Allocation + Requesti Need [i] = Need [i] - Requesti Вызвать алгоритм проверки безопасности полученного состояния. Если состояние безопасно, выделить ресурс процессу Pi. Выход. Если состояние небезопасно, восстановить предыдущее состояние; процесс должен ждать. Пример использования алгоритма банкира Пусть имеется 5 процессов – P0, …, P4, и 3 типа ресурсов – ресурс A (10 экземпляров), ресурс B (5 экземпляров) и ресурс C (7 экземпляров). Пусть состояние системы в момент T0 следующее:
Вычислим матрицу потребностей Need = Max – Allocation:
Нетрудно видеть, что система – в безопасном состоянии. Последовательность процессов <P1, P3, P4, P2, P0> удовлетворяет критерию безопасности. Проверку предоставляем студенту.
В продолжение примера, предположим, что процесс P1 сделал запрос (1 0 2). Проверяем, что Request <= Available: <(1 0 2) <= (3 3 2) = true. Удовлетворяем запрос. Состояние системы принимает вид:
Исполнение алгоритма безопасности показывает, что последовательность процессов <P1, P3, P4, P0, P2> удовлетворяет критерию безопасности. Предоставляем студенту проверку корректности данных преобразований и предлагаем ответить на следующие дополнительные вопросы: · может ли быть удовлетворен запрос (3 3 0) для процесса P4? · может ли быть удовлетворен запрос (0 2 0) для процесса P0? Методы обнаружения тупиков Альтернативным подходом к решению проблемы тупиков является обнаружение тупиков. При таком подходе система может позволить себе войти в состояние тупика. После этого применяется алгоритм обнаружения тупиков. После обнаружения тупика применяется схема восстановления после тупика. Граф wait-for В дополнение к графу распределения ресурсов, введем более простой по струтуре граф wait-for: вершины в нем соответствуют процессам, и дуга проводится из вершины Pi в вершину Pj, если процесс Pi ожидает процесса Pj. Если каждый тип ресурса в системе существует в единственном экземпляре, то очевидно, что цикл в данном графе означает тупик. Система для обнаружения тупиков должна периодически проверять отсутствие циклов в графе wait-for. Как известно, алгоритм обнаружения цикла в графе требует O(n2) операций, где n – число вершин в графе. На рис.3 приведен пример графа распределения ресурсов и соответствующего ему графа wait-for для системы с тупиком. Рис. 3. Граф распределения ресурсов и граф wait-for.
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2016-12-30; просмотров: 278; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.148.102.142 (0.011 с.) |