- •Введение
- •Управление ресурсами: общие сведения
- •Управление процессами
- •2.1 Состояния процессов и переходы между ними
- •Стратегии и дисциплины планирования загрузки процессоров
- •Стратегия одинакового среднего времени ожидания
- •Дисциплина планирования fifo
- •Справедливая стратегия
- •Дисциплина планирования rr
- •Влияние величины кванта времени на величину средней задержки ответа
- •Стратегия максимальной пропускной способности
- •Дисциплина планирования sjf
- •Дисциплина планирования srt
- •Дисциплина планирования hrrn
- •Стратегия приоритетного планирования
- •Дисциплина лотерейного планирования
- •Дисциплины планирования с множеством очередей
- •Планирование с последовательным прохождением очередей
- •Дисциплина планирования vrr
- •Планирование на основе множества очередей с обратными связями
- •2.3 Планирование в многопользовательской системе – справедливое планирование
- •2.4 Планирование загрузки процессоров в операционных системах реального времени – частотно-монотонное планирование
- •2.5 Планирование загрузки процессоров в многопроцессорных системах
- •Многопроцессорная система с главным процессором
- •Организация с собственным планировщиком для каждого процессора
- •Симметричная многопроцессорная организация (smp)
- •Разбиение системных таблиц
- •Смещение моментов прерывания таймера
- •Стратегия планирования загрузки процессоров в многопроцессорной системе
- •Стратегия распределения загрузки
- •Стратегия максимальной производительности при параллельных вычислениях – бригадное планирование
- •Метод расщепление цикла
- •Метод редукции высоты дерева
- •Параллельное вычисление по альтернативным ветвям
- •Бригадное планирование процессов в многопроцессорной системе
- •2.6 Синхронизация выполнения процессов
- •Алгоритмы взаимоисключения с активным ожиданием
- •Алгоритм 1
- •Алгоритм 2
- •Алгоритм 3
- •Алгоритм 4
- •Алгоритм 5
- •Алгоритм Деккера
- •Алгоритм Петерсона
- •Алгоритм на основе команды процессора "проверить и установить"
- •Алгоритм на основе команды процессора "обменять данные"
- •Недостатки алгоритмов с активным ожиданием
- •Алгоритмы взаимоисключения с блокировкой процессов
- •Открытие объекта синхронизации
- •Закрытие объекта синхронизации
- •Вхождение в критическую секцию
- •Выход из критической секции
- •Замечания по реализации примитивов синхронизации
- •Мониторы
- •2.7 Взаимная блокировка процессов (тупики)
- •Необходимые условия возникновения тупика
- •Методы борьбы с тупиками
- •Предотвращение тупиков
- •Нарушение ожидания дополнительных ресурсов
- •Нарушение неперераспределимости ресурсов
- •Нарушение условия кругового ожидания
- •Устранение тупиков
- •Обнаружение тупиков
- •Управление памятью
- •3.1 Иерархическая модель памяти
- •Оценка среднего времени доступа к данным при использовании многоуровневой модели памяти
- •Локализация ссылок при обращении к памяти
- •3.2 Виртуальная память
- •Предпосылки создания виртуальной памяти
- •Архитектура виртуальной памяти
- •Подсистема трансляции адресов
- •Метод прямого отображения
- •Метод ассоциативного отображения
- •Метод комбинированного отображения
- •Архитектура виртуального адресного пространства
- •Сегментная организация виртуальной памяти
- •Страничная организация виртуальной памяти
- •Сегментно-страничная организация виртуальной памяти
- •Отображение файла на виртуальное адресное пространство
- •Совместное использование данных в оперативной памяти
- •3.3 Основные стратегии управления памятью
- •Стратегии выборки данных
- •Стратегии размещения данных
- •Выделение памяти по стратегии первого подходящего
- •Выделение памяти по стратегии наиболее подходящего
- •Выделение памяти по стратегии наименее подходящего
- •Стратегии замещения данных
- •Замещение с немедленной перезаписью и замещение с буферизацией
- •Замещение с локальной и глобальной областью видимости
- •3.4 Управление виртуальной памятью
- •Выборка в системе виртуальной памяти
- •Реализация выборки по требованию
- •Размещение в системе виртуальной памяти
- •Замещение в системе виртуальной памяти
- •Стратегия выталкивания случайной страницы
- •Оптимальная стратегия
- •Дисциплина fifo – выталкивание наиболее старой страницы
- •Дисциплина lru – выталкивание дольше всего неиспользуемой страницы
- •Дисциплина lfu – выталкивание страницы с наименьшей частотой обращений
- •Дисциплина nru – выталкивание страницы, не используемой в последнее время
- •Часовой алгоритм
- •Управление резидентным множеством страниц процесса
- •Понятие рабочего множества страниц процесса
- •Управление резидентными множествами на основе рабочих множеств
- •Глобальное замещение, динамическое резидентное множество
- •Локальное замещение, фиксированное резидентное множество
- •Локальное замещение, динамическое резидентное множество
- •Алгоритм на основе оценки частоты прерываний – дисциплина pff (Page Fault Frequency)
- •Алгоритм с переменным пробным интервалом – дисциплина vsws
- •Влияние размера страницы
- •Оптимизация работы дискового накопителя
- •Оптимизация механических перемещений головок диска
- •Основы устройства и функционирования дисковых накопителей
- •Стратегии оптимизации механических перемещений головок диска
- •Стратегия fcfs – Fist Come First Served
- •Стратегия sstf – Shortest Seek Time First
- •Стратегия scan – Scanning
- •Стратегия n-step scan – n-step Scanning
- •Системный дисковый кэш
- •Структура системного дискового кэша
- •Хэширование, хэш-функции и хэш-очереди
- •Структура блока и очередей дискового кэша
- •Работа системного дискового кэша
- •Упреждающее чтение
- •Реализация дискового кэша на основе виртуальной памяти
- •3.6 Надежность операционной системы при использовании системного дискового кэша
- •Буферизация ввода-вывода на пользовательском уровне
- •3.7 Процессорный кэш
- •Отображение участков озу на процессорный кэш
- •Случайное отображение участков озу в процессорный кэш
- •Детерминированное отображение участков озу в процессорный кэш
- •Комбинированное отображение участков озу в процессорный кэш
- •Работа процессорного кэша в режиме записи данных
- •3.8 Динамическое распределение памяти
- •Куча (heap)
- •Алгоритмы динамического распределения памяти
- •Отложенное объединение свободных блоков
- •Оптимизация списка свободных блоков
- •Метод парных меток для поддержания списка блоков кучи
- •Специальные алгоритмы динамического распределения памяти из кучи
- •Метод близнецов (или метод двойников)
- •Алгоритм выделения блоков памяти одинакового размера
- •Заключение
- •Библиографический список
- •Оглавление
- •394026 Воронеж, Московский просп., 14
Устранение тупиков
Методы предотвращения тупиков накладывают ограничения на возможности процессов при запросе ресурсов, что неудобно и приводит к снижению производительности.
Основная идея концепции устранения тупиков состоит в том, чтобы, не накладывая дополнительных ограничений на поведение процессов, проверять потенциальную возможность возникновения тупика при каждом выделении ресурсов. Если выделение ресурса не грозит тупиком, то ресурсы выделяются, в противном случае операционная система отказывает процессу в выделении ресурса.
Получив отказ, процесс может повторить свой запрос через некоторое время, когда ситуация станет более благоприятной.
Очевидно, что основная проблема при реализации этого подхода состоит в том, чтобы определить, грозит ли тупиком удовлетворение очередного запроса на ресурсы.
Для ответа на этот вопрос необходимо знать максимальные потребности в ресурсах каждого из процессов, общее количество каждого из ресурсов в системе и количество уже распределенных ресурсов. Сопоставляя эту информацию, можно определить, существует ли возможность безтупикового завершения процессов при любом сценарии запроса ресурсов.
Алгоритм, запрещающий выделение ресурсов при угрозе тупика впервые был предложен Дейкстрой в середине 60-х гг. XX века и известен как алгоритм банкира.
Пусть вектор определяет общее количество каждого ресурса в системе, матрица определяет максимальную потребность процесса в ресурсе , а матрица определяет количество ресурса , распределенное процессу .
Также введем понятие безопасного состояния. Состояние является безопасным, если за счет оставшихся свободных ресурсов можно полностью удовлетворить потребности хотя бы одного процесса.
Количество свободного -го ресурса можно определить по формуле (0).
( 0 )
Потребности процесса можно удовлетворить за счет оставшихся свободных ресурсов, если для любого выполняется условие (0).
( 0 )
Из выражения (0) с учетом формулы (0) можно легко получить достаточное условие безопасности текущего состояния (0).
( 0 )
Таким образом, если выполняется условие (0), то состояние является безопасным и тупика в данной ситуации возникнуть не может.
Алгоритм банкира состоит в следующем. В ответ на запрос о выделении ресурсов проверяется, останется ли система в безопасном состоянии после выделения ресурсов. Для этого матрица заполняется в соответствии с распределением ресурсов, которое будет после удовлетворения запроса, и проверяется условие (0).
Если условие (0) выполняется, то запрос на выделение ресурсов удовлетворяется.
Алгоритм банкира не накладывает никаких ограничений на количество и порядок запроса ресурсов процессами, однако, он требует сразу же указать максимальную потребность процесса в ресурсах, что неудобно, а иногда и невозможно. Поэтому методы устранения тупиков не получили развития в современных системах.
Обнаружение тупиков
Данный подход не предполагает выполнения каких-либо действий, направленных на предупреждение возникновения тупика. Предполагается только выявление возникших тупиков и их разрешение с минимальными потерями.
Для разрешения тупика наиболее простым решением является принудительное завершение хотя бы одного процесса, вовлеченного в круговое ожидание ресурсов. При этом операционная система должна освободить все ресурсы, удерживаемые этим процессом. Для минимизации среднего ущерба от тупиков целесообразно выбирать, какой из вовлеченных в тупик процессов выгоднее завершить. Например, можно выбирать процесс, удерживающий за собой больше всего ресурсов, или процесс, использовавший меньше всего процессорного времени.
Использование описанного подхода к разрешению тупиков оправдано тем, что при исполнении корректных программ в реальных операционных системах тупики случаются редко. Снятый с выполнения процесс может быть легко перезапущен и вероятность его вовлечения в новый тупик очень низка. Таким образом, потери от возможного аварийного завершения процесса с лихвой компенсируются отменой значительных накладных расходов на выявление опасных состояний.
Таким образом, если тупики в системе возникают достаточно редко, то с ними вполне можно мириться. Важно только вовремя распознать тупик и освободить вовлеченные в него ресурсы. Несложно предложить формальный алгоритм обнаружения тупика. Для этого операционная система должна поддерживать списки распределения и ожидания ресурсов, например в формате, показанном на рис. 18.
Каждый процесс содержит список указателей на ожидаемые ресурсы, а каждый ресурс содержит указатель на процесс, которому он в данный момент принадлежит. Задача алгоритма распознавания тупика состоит в том, чтобы найти в списке замкнутый цикл ожидания ресурсов. При использовании структуры данных, показанной на рис. 18, может быть реализован рекурсивный алгоритм поиска замкнутого цикла ожидания, показанный на рис. 19.
Рис.18. Список распределения и ожидания ресурсов
Рис.19. Алгоритм поиска тупика
Указанный алгоритм реализует последовательный просмотр процессов и ожидаемых ими ресурсов, как показано на рис. 20.
Рис.20. Граф просмотра процессов ресурсов