Тема 10.Взаимоблокировки

Ресурс. Абстракция над объектом, к которому может быть предоставлен монопольный доступ

Ресурсы бывают:Выгружаемые и Невыгружаемые.

Запрос -> использование -> освобождение

Графическое изображение ресурсов

Защита ресурса мьютексом

• Для защиты ресурсов можно использовать мьютексы (семафоры).

Проблема при захвате ресурса

Взаимоблокировка - явление, при котором каждый процесс из заблокированного набора ожидает события, которое может вызвать только другой процесс из этой же группы.

Условия возникновения взаимоблокировок: 1) Каждый ресурс захвачен или свободен (условие взаимного исключения); 2) Процессы, владеющие ресурсами, могут запрашивать другие ресурсы (условие удержания и ожидания); 3) Выделенные ресурсы нельзя забрать (условие невыгружаемости); 4) Существует цикл из двух и более процессов на графе выделения ресурсов (условие циклического ожидания).

Способы обнаружения взаимоблокировок: 1) Алгоритм «страуса», 2) Поиск циклов на графе (По одному ресурсу каждого вида) или (По несколько ресурсов каждого вида).

Алгоритм поиска

1. Пустой список L, рёбра не маркированы

2. Текущий узел в конец списка, проверяем количество вхождений узла в список N: N>1 ? «Есть цикл» : 3

3. Ищем исходящие из текущего узла неотмеченные рёбра. Нашли => 4, нет => 5

4. Отмечаем случайное из найденных рёбер и переходим по нему, затем jmp 2

5. Удаляем последний узел из конца L и возвращаемся к предыдущему, jmp 3. Если предыдущий == начальному, заканчиваем

Поиск на графе (несколько ресурсов каждого вида)

• E — вектор существующих ресурсов

• A — вектор доступных ресурсов

• С — матрица текущего распределения

• R — матрица запросов

Алгоритм поиска

1. Все процессы неотмеченные

2. Ищем неотмеченный процесс

3. , маркируем процесс, jmp 1

4. Если процессов не найдено, заканчиваем

Когда искать взаимоблокировки? При каждом запросе ресурса; Периодически; При определённом состоянии внешней среды

Восстановление после обнаружения

• Принудительная выгрузка ресурса

• Откат состояния

• Уничтожение процесса

Избежание взаимоблокировок

• Алгоритм банкира:

• Атака условия взаимного исключения (спулинг)

• Атака условия удержания и ожидания

• Атака условия отсутствия принудительной выгрузки

• Атака условия циклического ожидания

Задачи ядра

• Обработка прерываний

• Управление процессами и потоками

• Обеспечение межпроцессного взаимодействия

• Управление памятью

• Управление вводом-выводом

• Обеспечение защиты

Тема 11.Управление памятью

Цели управления памятью:

• Координация множественного доступа к памяти

• Повышение эффективности использования памяти

• Повышение степени мультипрограммирования

Иерархия памяти

• Кэш (очень быстрая и дорогая)

• Оперативная (быстрая и недорогая)

• Вторичная (медленная и дешёвая)

Стратегии управления памятью

• Стратегии загрузки

  • Загрузка по требованию

  • Предварительная загрузка

• Стратегии размещения

  • В первом подходящем участке

  • В наиболее подходящих участках

  • В наименее подходящих участках

• Стратегии замены

Способы выделения памяти

• Выделение непрерывных участков

• Выделение фрагментированных участков

Выделение непрерывных участков (однозадачность)

Защита памяти в случае однозадачности

• Аппаратный регистр границы

• При выполнении операций в памяти проверяется адрес обращения

• Существуют привилегированные команды

Выделение непрерывных участков (многозадачность)

Перемещение

• Перемещаемость (relocationability) — свойство программы сохранять работоспособность вне зависимости от способа размещения в памяти.

Проблемы адресации в перемещаемом процессе

Защита памяти в случае многозадачности

• Аппаратные регистр верхней границы, регистр нижней границы и номер сегмента

• При переключении между задачами меняется содержимое этих регистров

Выделение непрерывных изменяемых участков

Фрагментация

• Фрагментация — явление дробления свободной памяти на произвольно расположенные куски, не формирующие последовательную область

Стратегии размещения

• Размещение в первых подходящих участках

• Размещение в наиболее подходящих участках

• Размещение в наименее подходящих участках

• Размещение в следующем подходящем участке

Своппинг (swapping)

• В памяти хранятся не все процессы

• ОС поочерёдно загружает и выгружает процессы из памяти

• Выгруженные процессы хранятся во вторичной памяти

Проблемы использования физической памяти Сложная адресация

• Перемещение

• Ограниченность объёма

  • Добавление памяти

  • Оверлеи

  • Своппинг