- •Часть I. Общие сведения 5
- •Глава 4. Кооперация процессов и основные аспекты ее логической организации 43
- •Глава 5. Алгоритмы синхронизации 54
- •Глава 6. Механизмы синхронизации 66
- •Глава 7. Тупики 74
- •Часть III. Управление памятью. 85
- •Глава 8. Введение. Простейшие схемы управления памятью. 85
- •Глава 9. Виртуальная память. Архитектурные средства поддержки виртуальной памяти 94
- •Глава 10. Аппаратно-независимый уровень управления виртуальной памятью 106
- •Часть IV. Файловые системы 119
- •Глава 11. Файлы с точки зрения пользователя 119
- •Глава 12. Реализация файловой системы 131
- •Часть V. Ввод-вывод 150
- •Глава 13. Система управления вводом-выводом 150
- •Введение в операционные системы Часть I. Общие сведения Глава 1. Введение
- •1.1 Что такое операционная система.
- •1.1.1 Структура вычислительной системы
- •1.1.2 Что такое ос
- •1.2 Краткая история эволюции вычислительных систем
- •1.3 Основные понятия, концепции ос.
- •1.4 Архитектурные особенности ос.
- •1.4.1 Монолитное ядро
- •1.4.2 Слоеные системы (Layered systems)
- •1.4.3 Виртуальные машины
- •1.4.4 Микроядерная архитектура.
- •1.4.5 Смешанные системы
- •1.5 Классификация ос
- •Часть II. Процессы и их поддержка в операционной системе Глава 2. Процессы
- •2.1. Понятие процесса
- •2.2. Состояния процесса
- •2.3. Операции над процессами и связанные с ними понятия
- •2.3.1. Набор операций
- •2.3.2. Process Control Block и контекст процесса
- •2.3.3. Одноразовые операции
- •2.3.4. Многоразовые операции
- •2.3.5. Переключение контекста
- •Глава 3. Планирование процессов
- •3.1. Уровни планирования
- •3.2. Критерии планирования и требования к алгоритмам
- •3.3. Параметры планирования
- •3.4. Вытесняющее и невытесняющее планирование
- •3.5. Алгоритмы планирования
- •3.5.4. Гарантированное планирование
- •3.5.5. Приоритетное планирование
- •3.5.6. Многоуровневые очереди (Multilevel Queue)
- •3.5.7. Многоуровневые очереди с обратной связью (Multilevel Feedback Queue)
- •Глава 4. Кооперация процессов и основные аспекты ее логической организации
- •4.1. Взаимодействующие процессы
- •4.2. Категории средств обмена информацией
- •4.3. Логическая организация механизма передачи информации
- •4.3.1. Как устанавливается связь?
- •4.3.2. Информационная валентность процессов и средств связи
- •4.3.3. Особенности передачи информации с помощью линий связи
- •4.3.3.1 Буферизация
- •4.3.3.2. Поток ввода/вывода и сообщения
- •4.3.4. Надежность средств связи
- •4.3.5. Как завершается связь?
- •4.4. Потоки исполнения
- •Глава 5. Алгоритмы синхронизации
- •5.1. Interleaving, race condition и взаимоисключения
- •5.2. Критическая секция
- •5.3. Программные алгоритмы организации взаимодействия процессов
- •5.3.1. Требования, предъявляемые к алгоритмам
- •5.3.2. Запрет прерываний
- •5.3.3. Переменная-замок
- •5.3.4. Строгое чередование
- •5.3.5. Флаги готовности
- •5.3.6. Алгоритм Петерсона
- •5.3.7. Алгоритм булочной (Bakery algorithm)
- •5.4. Аппаратная поддержка взаимоисключений
- •5.4.1. Команда Test-and-Set (Проверить и присвоить 1)
- •5.4.2. Команда Swap (Обменять значения)
- •Глава 6. Механизмы синхронизации
- •6.1. Семафоры
- •6.1.1. Концепция семафоров
- •6.1.2. Решение проблемы producer-consumer с помощью семафоров
- •6.2. Мониторы
- •6.3. Сообщения
- •6.4. Эквивалентность семафоров, мониторов и сообщений
- •6.4.1. Реализация мониторов и передачи сообщений с помощью семафоров
- •6.4.2. Реализация семафоров и передачи сообщений с помощью мониторов
- •6.4.3. Реализация семафоров и мониторов с помощью очередей сообщений
- •Глава 7. Тупики
- •7.1 Введение
- •7.2 Концепция ресурса
- •7.3 Условия возникновения тупиков
- •7.4 Основные направления борьбы с тупиками.
- •7.5 Алгоритм страуса
- •7.6 Обнаружение тупиков
- •7.7 Восстановление после тупиков
- •7.7.1 Восстановление при помощи перераспределения ресурсов
- •7.7.2 Восстановление через откат назад
- •7.7.3 Восстановление через ликвидацию одного из процессов
- •7.8 Способы обхода тупиков путем тщательного распределения ресурсов.
- •7.8.1 Алгоритм банкира.
- •7.8.2 Недостатки алгоритма банкира
- •7.9 Предотвращение тупиков за счет нарушения условий возникновения тупиков.
- •7.9.1 Нарушение условия взаимоисключения
- •7.9.2 Hарушение условия ожидания дополнительных ресурсов
- •7.9.3 Нарушение принципа неперераспределяемости.
- •7.9.4 Нарушение условия кругового ожидания
- •7.10 Родственные проблемы
- •7.10.1 Двухфазная локализация
- •7.10.2 Тупики не ресурсного типа
- •7.10.3 Голод (starvation)
- •7.11 Заключение.
- •Часть III. Управление памятью.
- •Глава 8. Введение. Простейшие схемы управления памятью.
- •8.1 Введение.
- •8.2 Связывание адресов.
- •8.3 Простейшие схемы управления памятью.
- •8.3.1 Схема с фиксированными разделами.
- •8.3.1.1 Один процесс в памяти
- •8.3.1.2 Оверлейная структура
- •8.3.2 Свопинг
- •8.3.3 Мультипрограммирование с переменными разделами.
- •Глава 9. Виртуальная память. Архитектурные средства поддержки виртуальной памяти
- •9.1 Проблема размещения больших программ. Понятие виртуальной памяти.
- •9.2 Архитектурные средства поддержки виртуальной памяти.
- •9.2.1 Страничная память
- •9.2.2 Сегментная и сегментно-страничная организации памяти
- •9.2.3 Таблица страниц
- •9.2.4 Ассоциативная память.
- •9.2.5 Иерархия памяти
- •9.2.6 Размер страницы
- •Глава 10. Аппаратно-независимый уровень управления виртуальной памятью
- •10.1 Исключительные ситуации при работе с памятью.
- •10.2 Стратегии управления страничной памятью
- •10.3 Алгоритмы замещения страниц
- •10.3.1 Fifo алгоритм. Выталкивание первой пришедшей страницы.
- •10.3.2 Оптимальный алгоритм
- •10.3.3 Выталкивание дольше всего не использовавшейся страницы. Lru (The Least Recently Used) Algorithm .
- •10.3.4 Выталкивание редко используемой страницы. Nfu (Not Frequently Used) алгоритм.
- •10.3.5 Другие алгоритмы
- •10.4. Thrashing. Свойство локальности. Модель рабочего множества.
- •10.4.1 Концепция локальности
- •10.4.2 Модель рабочего множества (Working Set)
- •10.5 Демоны пейджинга
- •10.6 Аппаратно-независимая модель памяти процесса.
- •10.6.1 Структуры данных, используемые для описания сегментной модели
- •10.7 Отдельные аспекты функционирования менеджера памяти.
- •Часть IV. Файловые системы
- •Глава 11. Файлы с точки зрения пользователя
- •11.1 Введение
- •11.2 Имена файлов
- •11.3 Структура файлов
- •11.4 Типы и атрибуты файлов
- •11.5 Доступ к файлам
- •11.6 Операции над файлами.
- •11.7 Директории. Логическая структура файлового архива.
- •11.8 Операции над директориями
- •11.9 Защита файлов.
- •11.9.1 Контроль доступа к файлам
- •11.9.2 Списки прав доступа
- •Глава 12. Реализация файловой системы
- •12.1 Интерфейс файловой системы.
- •12.2 Общая структура файловой системы
- •12.3 Структура файловой системы на диске.
- •12.3.1 Методы выделения дискового пространства
- •12.3.2 Управление свободным и занятым дисковым пространством.
- •12.3.3 Размер блока
- •12.3.4 Структура файловой системы на диске
- •12.4 Реализация директорий
- •12.4.1 Примеры реализация директорий в некоторых ос
- •12.4.2Поиск в директории
- •12.5 Монтирование файловых систем.
- •12.6 Кооперация процессов при работе с файлами.
- •12.7 Надежность файловой системы.
- •12.7.1 Целостность файловой системы.
- •12.7.2 Управление плохими блоками.
- •12.8 Производительность файловой системы
- •12.9 Современные архитектуры файловых систем
- •Часть V. Ввод-вывод Глава 13. Система управления вводом-выводом
- •13.1 Физические принципы организации ввода-вывода.
- •13.1.1. Общие сведения об архитектуре компьютера.
- •13.1.2. Структура контроллера устройства.
- •13.1.3. Опрос устройств и прерывания. Исключительные ситуации и системные вызовы
- •13.1.4. Прямой доступ к памяти (Direct Memory Access – dma).
- •13.2. Логические принципы организации ввода-вывода.
- •13.2.1. Структура системы ввода-вывода.
- •13.2.2. Систематизация внешних устройств и интерфейс между базовой подсистемой ввода-вывода и драйверами.
- •13.2.3. Функции базовой подсистемы ввода-вывода.
- •13.2.3.1. Блокирующиеся, не блокирующиеся и асинхронные системные вызовы.
- •13.2.3.2. Буферизация и кэширование.
- •13.2.3.3. Spooling и захват устройств.
- •13.2.3.4. Обработка прерываний и ошибок.
- •13.2.3.5. Планирование запросов.
- •13.2.4. Алгоритмы планирования запросов к жесткому диску.
- •13.2.4.1. Строение жесткого диска и параметры планирования.
- •13.2.4.2. Алгоритм First Come First Served (fcfs)
- •13.2.4.3. Алгоритм Short Seek Time First (sstf).
- •13.2.4.4. Алгоритмы сканирования (scan, c-scan, look, c-look)
3.5.6. Многоуровневые очереди (Multilevel Queue)
Для систем, в которых процессы могут быть легко рассортированы на разные группы, был разработан другой класс алгоритмов планирования. Для каждой группы процессов создается своя очередь процессов, находящихся в состоянии готовность (см. рисунок3.3). Этим очередям приписываются фиксированные приоритеты. Например, приоритет очереди системных процессов устанавливается больше, чем приоритет очередей пользовательских процессов. А приоритет очереди процессов, запущенных студентами, — ниже, чем для очереди процессов, запущенных преподавателями. Это значит, что ни один пользовательский процесс не будет выбран для исполнения, пока есть хоть один готовый системный процесс, и ни один студенческий процесс не получит в свое распоряжение процессор, если есть процессы преподавателей, готовые к исполнению. Внутри этих очередей для планирования могут применяться самые разные алгоритмы. Так, например, для больших счетных процессов, не требующих взаимодействия с пользователем (фоновых процессов), может использоваться алгоритм FCFS, а для интерактивных процессов – алгоритм RR. Подобный подход, получивший название многоуровневых очередей, повышает гибкость планирования: для процессов с различными характеристиками применяется наиболее подходящий им алгоритм.
Рис. 3.3. Несколько очередей планирования.
3.5.7. Многоуровневые очереди с обратной связью (Multilevel Feedback Queue)
Дальнейшим развитием алгоритма многоуровневых очередей является добавление к нему механизма обратной связи. Здесь процесс не постоянно приписан к определенной очереди, а может мигрировать из очереди в очередь, в зависимости от своего поведения.
Для простоты рассмотрим ситуацию, когда процессы в состоянии готовность организованы в 4 очереди, как на рисунке3.4. Планирование процессов между очередями осуществляется на основе вытесняющего приоритетного механизма. Чем выше на рисунке располагается очередь, тем выше ее приоритет. Процессы в очереди 1 не могут исполняться, если в очереди 0 есть хотя бы один процесс. Процессы в очереди 2 не будут выбраны для выполнения, пока есть хоть один процесс в очередях 0 и 1. И, наконец, процесс в очереди 3 может получить процессор в свое распоряжение только тогда, когда очереди 0, 1 и 2 пусты. Если при работе процесса появляется другой процесс в какой-либо более приоритетной очереди, исполняющийся процесс вытесняется появившимся. Планирование процессов внутри очередей 0—2 осуществляется с использованием алгоритма RR, планирование процессов в очереди 3 основывается на алгоритме FCFS.
Рис. 3.4.Схема миграции процессов в многоуровневых очередях планирования с обратной связью. Вытеснение процессов более приоритетными процессами и завершение процессов на схеме не показано.
Родившийся процесс поступает в очередь 0. При выборе на исполнение он получает в свое распоряжение квант времени размером 8 единиц. Если продолжительность его CPU burst меньше этого кванта времени, процесс остается в очереди 0. В противном случае, он переходит в очередь 1. Для процессов из очереди 1 квант времени имеет величину 16. Если процесс не укладывается в это время, он переходит в очередь 2. Если укладывается — остается в очереди 1. В очереди 2 величина кванта времени составляет 32 единицы. Если и этого мало для непрерывной работы процесса, процесс поступает в очередь 3, для которой квантование времени не применяется, и, при отсутствии готовых процессов в других очередях, он может исполняться до окончания своего CPU burst. Чем больше значение продолжительности CPU burst, тем в менее приоритетную очередь попадает процесс, но тем на большее процессорное время он может рассчитывать для своего выполнения. Таким образом, через некоторое время все процессы, требующие малого времени работы процессора окажутся размещенными в высокоприоритетных очередях, а все процессы, требующие большого счета и с низкими запросами к времени отклика,—в низкоприоритетных.
Миграция процессов в обратном направлении может осуществляться по различным принципам. Например, после завершения ожидания ввода с клавиатуры процессы из очередей 1, 2 и 3 могут помещаться в очередь 0, после завершения дисковых операций ввода-вывода процессы из очередей 2 и 3 могут помещаться в очередь 1, а после завершения ожидания всех других событий из очереди 3 в очередь 2. Перемещение процессов из очередей с низкими приоритетами в очереди с большими приоритетами позволяет более полно учитывать изменение поведения процессов с течением времени.
Многоуровневые очереди с обратной связью представляют собой наиболее общий подход к планированию процессов из числа подходов, рассмотренных нами. Они наиболее трудоемки в реализации, но в то же время они обладают наибольшей гибкостью. Понятно, что существует много других разновидностей такого способа планирования помимо варианта, приведенного выше. Для полного описания их конкретного воплощения необходимо указать:
Количество очередей для процессов, находящихся в состоянии готовность.
Алгоритм планирования, действующий между очередями.
Алгоритмы планирования, действующие внутри очередей.
Правила помещения родившегося процесса в одну из очередей.
Правила перевода процессов из одной очереди в другую.
Изменяя какой-либо из перечисленных пунктов, мы можем существенно менять поведение вычислительной системы.