20Тупиковые ситуации. Предотвращение возникновений тупиков. Обнаружение тупиков. Восстановление после тупиков.

Способы предотвращения тупиков

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

Способы предотвращения тупиков путем тщательного распределения ресурсов ♦Нарушение условия взаимоисключения♦Нарушение условия ожидания дополнительных ресурсов♦Нарушение принципа отсутствия перераспределения

♦Hарушение условия кругового ожидания

Обнаружение тупиков

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

Рассмотрим модельную ситуацию.

1. Процесс P1 ожидает ресурс R1.

2. Процесс P2 удерживает ресурс R2 и ожидает ресурс R1.

3. Процесс P3 удерживает ресурс R1 и ожидает ресурс R3.

4. Процесс P4 ожидает ресурс R2.

5. Процесс P5 удерживает ресурс R3 и ожидает ресурс R2.

Вопрос состоит в том, является ли данная ситуация тупиковой, и если да, то какие процессы в ней участвуют. Для ответа на этот вопрос можно сконструировать граф ресурсов, как показано на. Из рисунка видно, что имеется цикл, моделирующий условие кругового ожидания, и что процессы P2,P3,P5, а может быть, и другие находятся в тупиковой ситуации.

Визуально легко обнаружить наличие тупика, но нужны также формальные алгоритмы, реализуемые на компьютере.

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

Восстановление после тупиков

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

Сложность восстановления обусловлена рядом факторов.

В большинстве систем нет достаточно эффективных средств, чтобы приостановить процесс, вывести его из системы и возобновить впоследствии с того места, где он был остановлен.

Если даже такие средства есть, то их использование требует затрат и внимания оператора.

Восстановление после тупика может потребовать значительных усилий.

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

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

21.Физическая организация памяти компьютера. Уровни памяти. Свойство локальности.

Физическая организация памяти компьютера

Деятельность ОС по распределению памяти между пользовательскими процессами и компонентами ОС называется управлением памятью, а часть ОС, которая отвечает за управление памятью, называется менеджером памяти.

Запоминающее устройство компьютера разделяют как минимум на 2 уровня:

Основную (главную, оперативную, физическую)

вторичную (внешнюю)

Основная память представляет собой упорядоченный массив однобайтовых ячеек, каждая из которых имеет свой уникальный адрес (номер ячейки). ЦП извлекает команду из ОП, декодирует ее и выполняет. Для выполнения команды могут потребоваться обращения еще к нескольким ячейкам ОП.

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

1 нс Регистры процессора <1Кб

2 нс Кэш процессора 1Мб

10 нс Основная память 64-512МБ

10 мс Магнитные диски 20-200Гб

100 мс Магнитные ленты 20-300Гб

Информация, которая находится в памяти верхнего уровня, обычно хранится также на уровнях с большими номерами. Если ЦП не обнаруживает нужную информацию на i-м уровне, он начинает искать ее на следующем. Когда нужная информация найдена, она переносится на более быстрый уровень. Оказывается, при таком способе организации памяти по мере снижения скорости доступа к уровню памяти снижается также и частота обращения к нему.

Ключевую роль здесь играет свойство реальных программ в течение ограниченного отрезка времени работать с небольшим набором адресов памяти. Это эмпирически наблюдаемое свойство, известно, как принцип локальности и локализации обращений. Свойство локальности (соседние в пространстве и времени объекты характеризуются похожими свойствами), присущее не только функционированию ОС, но и природе, вообще. В случае ОС обычно в течение какого-то отрезка времени ограниченный фрагмент кода работает с ограниченным набором данных. Эту часть кода и данных удается разместить в памяти с быстрым доступом. В результате реальное время доступа к памяти определяется временем к верхним уровням, что и объясняет эффективность использования иерархической схемы.

КЭШ процессора является частью аппаратуры, поэтому менеджер ОС занимается распределением информации главным образом в основной и внешней физическими адресами. Набор физических адресов, с которыми работает программа, называют физическим адресным пространством.памяти. Адреса в основной памяти, характеризующие реальное расположение данных в физической памяти называются