- •Основы построения операционных систем
- •Введение
- •1. Основные аспекты операционных систем
- •1.1. Программные системы
- •1.2. Ресурсы вычислительных систем
- •1.3. Функции операционных систем
- •1.3.1. Упрощение доступа к компьютеру
- •1.3.2. Повышение эффективности использования ресурсов
- •1.4. Классификация операционных систем
- •2. Управление файлами
- •2.1. Файлы
- •2.1.1. Имя файла
- •2.1.2. Типы файлов
- •2.1.3. Атрибуты файла
- •2.2. Функции системы управления файлами
- •2.3. Способы организации файлов
- •2.3.1. Последовательное размещение
- •2.3.2. Размещение с помощью сцепленных блоков
- •2.3.3. Организация файлов на основе таблиц размещения
- •2.3.4. Размещение с использованием таблицы индексов
- •2.3.5. Индексно-последовательное размещение
- •2.3.6. Библиотечная структура данных
- •2.4. Методы доступа к содержимому файлов
- •2.4.1. Последовательный доступ
- •2.4.2. Прямой доступ
- •2.4.3. Другие методы доступа
- •2.5. Способы организации файловой структуры
- •2.6. Манипулирование файловой структурой
- •3. Управление памятью
- •3.1. Простое непрерывное распределение
- •3.2. Распределение с несколькими непрерывными разделами
- •3.2.1. Мультипрограммирование и разбиение на разделы
- •3.2.2. Разделы с фиксированными границами
- •3.2.3. Разделы с подвижными границами
- •3.2.4. Своппинг
- •3.3. Организация виртуальной памяти
- •3.3.1. Основные концепции виртуальной памяти
- •3.3.2. Страничная организация памяти
- •3.3.3. Сегментная организация памяти
- •3.3.4. Сегментно-страничная организация памяти
- •3.4. Управление виртуальной памятью
- •3.4.1. Алгоритмы выталкивания страниц
- •3.4.2. Подкачка страниц по запросу
- •3.4.3. Подкачка страниц с опережением
- •3.4.4. Освобождение страниц
- •3.4.5. Размер страниц
- •4. Управление процессами
- •4.1. Концепции процесса
- •4.1.1. Понятие последовательного процесса
- •4.1.2. Состояния процесса
- •4.1.3. Блок управления процессом
- •4.1.4. Планирование процессов
- •4.1.5. Обработка прерываний
- •4.2. Синхронизация параллельных процессов
- •4.2.1. Параллельная обработка
- •4.2.2. Взаимное исключение
- •4.2.3. Алгоритм Деккера
- •4.2.4. Аппаратная реализация взаимного исключения
- •4.2.5. Семафоры
- •4.2.6. Мониторы
- •4.2.7. Передача сообщений
- •4.3. Тупиковые ситуации
- •4.3.1. Условия возникновения дедлоков
- •4.3.2. Основные направления исследований по проблеме тупиков
- •4.3.3. Предотвращение тупиков
- •4.3.4. Обход дедлоков
- •4.3.5. Алгоритм банкира
- •4.3.6. Распознавание дедлоков
- •4.3.7. Восстановление после тупиков
- •5. Управление процессором
- •5.1. Диспетчеризация процессов
- •5.2. Приоритеты
- •5.3. Алгоритмы диспетчеризации с одной очередью
- •5.3.1. Алгоритм fcfs (первый пришедший обслуживается первым)
- •5.3.2. Алгоритм spn (кратчайший процесс - следующий)
- •5.3.3. Алгоритм srt (по наименьшему остающемуся времени)
- •5.3.4. Алгоритм hrrn (по наибольшему относительному времени ответа)
- •5.3.5. Алгоритм циклической диспетчеризации rr
- •5.3.6. Сравнение алгоритмов диспетчеризации с одной очередью
- •5.4. Многоуровневые очереди с обратными связями
- •6. Управление устройствами
- •6.1. Общая организация ввода-вывода
- •6.2. Методы управления периферийными устройствами
- •6.3. Действия по вводу-выводу
- •6.3.1. Буферизация : прочитать и записать
- •6.3.2. Блокирование : получить и поместить
- •6.3.3. Подготовка : открыть и закрыть
- •6.4. Управление магнитными дисками
- •6.4.1. Физическая структура магнитного диска
- •6.4.2. Физическая структура формата данных дискеты
- •6.4.3. Логическая структура магнитного диска
- •6.4.4. Планирование работы с магнитными дисками
- •Заключение
- •Список используемых источников
- •Оглавление
4.3.6. Распознавание дедлоков
Обнаружение тупика - это установление факта, что возникла тупиковая ситуация, и определение процессов и ресурсов, вовлеченных в эту тупиковую ситуацию. Алгоритмы обнаружения тупиков, как правило, применяются в системах, где выполняются первые три необходимых условия возникновения тупиковой ситуации. Эти алгоритмы затем определяют, не создался ли режим кругового ожидания.
Применение алгоритмов обнаружения тупиков сопряжено с определенными дополнительными затратами машинного времени. Таким образом, здесь снова приходится прибегать к компромиссным решениям, столь распространенным в операционных системах, т.к. необходимо определять, будут ли накладные расходы, связанные с реализацией алгоритмов обнаружения тупиковых ситуаций, в достаточной степени оправданы потенциальными выгодами от локализации и устранения тупиков.
Для выполнения вычислений по установлению, существуют ли процессы, находящиеся в состоянии дедлока, операционная система должна вести список тех ресурсов, которые ждет каждый заблокированный процесс, и список тех процессов, которые держат каждый недоступный ресурс.
Алгоритм распознавания замкнутых цепей можно выполнять с любой нужной частотой. Например, часто - всякий раз, когда запрос на ресурс отклоняется, или редко - раз в час. Можно избавиться от управляющей программы, необходимой для предотвращения, обхода и распознавания дедлоков, если положиться в этом на оператора. Если дедлоки возникают очень редко, например несколько раз в год, то это самое мудрое решение. Конечно, оператор может некоторое время не замечать дедлок, особенно если некоторые процессы продолжают исполняться. При этом потери состоят в задержке процессов и понижении возможностей системы, но это может быть вполне приемлемой ценой. Многие операционные системы применяют стратегию распознавания дедлоков и при этом рассчитывают на оператора, который выполняет это распознавание.
4.3.7. Восстановление после тупиков
Как только дедлок выявлен, должно быть выполнено восстановление. Это обязательно вызовет перезапуск одного или более процессов. Процессы, находящиеся в дедлоке, были заблокированы в некоторой точке. Их нужно вернуть в те условия, в которых они могут возобновить свое исполнение. Для большинства процессов перезапуск возможен только с самого начала, и даже в этом случае могут возникнуть некоторые трудности. Процесс может сделать снимок своего исполнения, т. е. запомнить информацию о своем состоянии в некоторой контрольной точке. В этом случае при повторном запуске этого процесса не требуется повторять все вычисления, предшествовавшие перераспределению. Контрольные точки обычно вводятся не для того, чтобы помочь восстановлению после дедлока, а для того, чтобы продолжить исполнение после возникновения ошибки, особенно при выполнении длинных работ в системах реального времени.
Самый простой метод восстановления - это принудительное завершение всех процессов и запуск операционной системы заново.
Менее радикальный метод - принудительное завершение всех процессов, находящихся в дедлоке. В этом случае пользователи могут ввести их когда-нибудь снова.
Третий метод - принудительно завершать процессы, находящихся в дедлоке, по одному и после каждого завершения вызывать алгоритм выявления дедлока (или обращаться для этого к оператору) до тех пор, пока дедлок не исчезнет.
Четвертый метод применим, если есть контрольные точки. При этом процессы, находящиеся в дедлоке, запускаются со своих контрольных точек в предположении, что дедлок больше не возникнет.
Пятый метод перераспределяет ресурсы одного или нескольких процессов, среди которых могут быть даже такие, которые не находятся в дедлоке. Ресурсы назначаются одному из оставшихся процессов, находящихся в дедлоке, и он возобновляет исполнение.
Шестой метод теоретически применим, если в момент, когда дедлок выявлен, существует несколько пользовательских процессов, которые не находятся в дедлоке. Если этим процессам позволить доработать до конца и запретить образование новых процессов, то они могут освободить достаточно ресурсов, чтобы разорвать дедлок. В некоторых системах это может происходить незаметно.