- •Основы построения операционных систем
- •Введение
- •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.3. Предотвращение тупиков
При предотвращении тупиковых ситуаций должно гарантироваться, что ни одно из четырех условий, необходимых для дедлока, не может возникнуть.
Условие взаимного исключения подавляется путем разрешения неограниченного разделения ресурсов. Хотя это очень удобно для таких ресурсов, как повторно входимые программы или драйверы дисков, обеспечивающие доступ к разным наборам данных, это совершенно неприменимо к совместно используемым переменным в критических интервалах или к магнитным лентам.
Условие ожидания можно подавить, предварительно выделяя ресурсы. Процесс должен потребовать все ресурсы заранее, и он не сможет начать исполнение до тех пор, пока они ему не будут выделены. Следовательно, общее число ресурсов, необходимое параллельным процессам, не может превышать возможностей системы. Хотя предварительное выделение используется часто, оно влечет за собой существенные издержки, вызнанные неэффективностью использования ресурсов. Каждый процесс должен ждать до тех пор, пока не получит всех необходимых ресурсов, даже если один из них используется только в конце исполнения. Процесс может не использовать все выделенные ему ресурсы, если среди них есть такие, которые требуются только в исключительных обстоятельствах. В результате другие процессы, которым необходимы эти ресурсы, вынуждены ждать. Еще одним недостатком является тот факт, что трудно сформулировать запросы на ресурсы в тех случаях, когда требуемые процессу ресурсы становятся известны только после начала исполнения.
Условие отсутствия перераспределения можно исключить, позволяя операционной системе отнимать у процесса ресурсы. Это выполнимо, если можно запомнить состояние процесса для его последующего восстановления. Перераспределение процессора сравнительно легко реализовать, и оно обычно выполняется так, как это будет описано в гл. 5 (при рассмотрении алгоритмов распределения процессора между процессами). Перераспределение устройств ввода-вывода или магнитофона может быть чрезвычайно неприятным. Для легко перераспределяемых ресурсов "ценой" перераспределения является необходимое для этого время. Для перераспределения ресурсов можно использовать две различные дисциплины. Одна них требует, чтобы работа, запросившая дополнительный ресурс, предварительно отказалась от любого количества этого ресурса, которое она уже имеет. На самом деле полностью это не исключает условие отсутствия перераспределения. Чтобы понять это, достаточно предположить, что ресурсы являются независимыми ресурсами. Другая дисциплина - общее исключение - отнимает у работы, заблокированной при запросе дополнительного ресурса, все ресурсы.
Условие кругового ожидания можно исключить, предотвращая образование цепи. Это обеспечивается иерархическим выделением ресурсов. Все ресурсы образуют некоторую иерархию. Процесс, затребовавший ресурс на одном уровне, может затем потребовать ресурсы только на более высоком уровне. Он может освободить ресурсы на данном уровне только после освобождения всех ресурсов на всех более высоких уровнях. После того как процесс получил, а потом освободил ресурсы данного уровня, он может снова запросить, ресурсы на том же самом уровне. Предварительное выделение ресурсов можно считать специальным случаем иерархического выделения, имеющего единственный уровень. Иерархическое выделение несколько дороже, но оно может снизить потери, связанные с полным предварительным выделением. Однако этот метод не дает никакого выигрыша, если порядок, в котором процессам необходимы ресурсы, отличается от порядка уровней в иерархии. Например, если графопостроитель нужен в начале выполнения, а магнитофон - только в конце, а последний по уровню ниже, чем графопостроитель, то магнитофон придется выделить достаточно рано, и он долгое время не будет использоваться.