Матричное представление графа
m – число классов ресурсов. E – вектор существующих ресурсов, где Ei – количество ресурсов класса i (пр. E1=2 – означ., что в системе есть два диска). В любой момент времени некоторые из ресурсов могут оказаться занятыми и, соответственно, недоступными. Пусть А будет вектором доступных ресурсов, где Аi равно количеству экзампляров ресурса i, доступных в текущий момент.
Два массива: C – матрица текущего распределения и R – матрица запросов. i-я строка в матрице С говорит о том, сколько представителей каждого класса ресурсов в данный момент использует процесс Pi. Сij – это количество экземпляров ресурса j, которые занимает процесс i. Rij – это количество экземпляров ресурса j, которые хочет получить процесс i.
А
лгоритм
обнаружения тупиков состоит из следующих
шагов:
Ищем немаркированный процесс Pi для которого i-я строка матрицы R меньше вектора А или равна ему.
Если такой процесс найден, прибавляем i-ю строку матрицы С к вектору А, маркируем процесс и возвращаемся к шагу 1.
Если таких процессов не существует, работа алгоритма заканчивается.
Завершение алгоритма означает, что все немаркированные процессы, если такие есть, попали в тупик.
Алгоритм банкира, предложенный Дейкстрой
Когда при описании алгоритма банкира мы будем говорить о ресурсах, мы будем подразумевать ресурсы одного и того же типа, однако этот алгоритм можно легко распространить на пулы ресурсов нескольких различных типов. Рассмотрим, например, проблему распределения некоторого количества t идентичных лентопротяжных устройств. Операционная система должна обеспечить распределение некоторого фиксированного числа t одинаковых лентопротяжных устройств между некоторым фиксированным числом пользователей и каждый пользователь заранее указывает максимальное число устройств, которые ему потребуются во время выполнения своей программы на машине. Операционная система примет запрос пользователя в случае, если максимальная потребность этого пользователя в лентопротяжных устройствах не превышает t.
Пользователь может занимать или освобождать устройства по одному. Возможно, что иногда пользователю придется ждать выделения дополнительного устройства, однако операционная система гарантирует, что ожидание будет конечным. Текущее число устройств, выделенных пользователю, никогда не превысит указанную максимальную потребность этого пользователя. Если операционная система в состоянии удовлетворить максимальную потребность пользователя в устройствах, то пользователь гарантирует, что эти устройства будут использованы и возвращены операционной системе в течение конечного периода времени.
Поэтому выделять лентопротяжные устройства пользователям можно только в случае, когда после очередного выделения устройств состояние системы остается надежным. Надежное состояние — это состояние, при котором общая ситуация с ресурсами такова, что все пользователи имеют возможность со временем завершить свою работу.
Восстановление после тупиков
Сложность восстановления обусловлена рядом факторов.
в большинстве систем нет достаточно эффективных средств для приостановки процесса, вывода его из системы и возобновления впоследствии;
если даже такие средства есть, то их использование требует затрат и внимания оператора;
восстановление после серьезного тупика может потребовать много работы.
Восстановление при помощи перераспределения ресурсов
Один из способов восстановления - принудительный вывод некоторого процесса из системы для последующего использования его ресурсов. Для определения того, какой процесс выводить из системы зачастую требуются усилия оператора. В некоторых случаях может оказаться возможным временно забрать ресурс у его текущего владельца и передать его другому процессу.
Восстановление через откат назад
Это, по всей вероятности, самый эффективный способ приостановки и возобновления.
Если проектировщики системы знают, что тупик вероятен, они могут периодически организовывать для процессов контрольные точки. Когда тупик обнаружен, видно какие ресурсы вовлечены в цикл кругового ожидания. Чтобы осуществить восстановление, процесс, который владеет таким ресурсам, должен быть отброшен к моменту времени, предшествующему его запросу на этот ресурс.
Восстановление через ликвидацию одного из процессов
Грубый, но простейший способ устранить тупик - убить один или более процессов. Например, убить процесс, который в цикле. Тогда при удаче остальные процессы смогут выполняться. Если это не помогает, то можно ликвидировать еще один процесс.
Иерархия памяти: уровни иерархии, вертикальное и горизонтальное управление, распределение основной памяти, особенности основной памяти как ресурса ВС, алгоритмы распределения памяти, защита памяти.
Память - функциональная часть компьютера, предназначенная для записи, хранения и считывания информации. Технически память реализуется в виде запоминающих устройств.
В самом простейшем случае можно выделить основную память и внешнюю память. Основные классы памяти, которые могут присутствовать на современных компьютерах.
В основе иерархии памяти современных компьютеров лежат два принципа.
Принцип локальности обращений. Большинство запросов процессов на обращение к памяти имеет, как правило, неравномерный характер с высокой степенью локальной концентрации, как временной, так и пространственной;
Соотношение скорость доступа - объем памяти. Чем быстрее может быть осуществлен доступ к памяти, тем она более дорогая. Следовательно, тем менее она практична с точки зрения использования и тем меньше будет ее объем, который разумно устанавливать в компьютер.
Распределение памяти может быть:
статическим, когда привязка к конкретным ячейкам памяти выполняется либо до, либо во время загрузки модуля;
динамическим, когда задание может перемешаться в памяти, допуская настройку и получение абсолютных значений ячеек памяти при каждом обращении к ним.
Существуют следующие основные способы реализации отображения памяти:
оверлеи (overlay) - возможность расположить модули в памяти таким образом, чтобы один из них (корневой) постоянно находился там, а остальные - попеременно загружались в ходе выполнения программы в одну и ту же область, сменяя и перекрывая друг друга;
свопинг (swapping) - разрешение системе вводить в память и выводить из нее задания целиком;
поблочное отображение - возможность группировать элементы информации в блоки (если блоки имеют одинаковый размер, то это страницы, если разный, то сегменты).