Шоу А.
Логическое проектирование операционных систем: Пер. с англ. —М: Мир, 1981.—-360 с., ил.
Монография по проектированию и разработке операционных систем, написанная американским специалистом. Материал ориентирован на подготовку специалистов по созданию математического обеспечения ЭВМ. Содержание книги близко известным монографиям по операционным системам С. Мэдника. Дж. До-нована (М.: Мир, 1978) и Д. Цикритзиса, Ф. Бернстайна (М.: Мир, 1977) и удачно дополняет их.
Для специалистов по математическому обеспечению, аспирантов и студентов.
Книга предназначена для студентов, изучающих вычислительную технику, и специалистов, владеющих основами знаний организации ЭВМ, языка ассемблера, языков программирования и структур данных. Необходимые знания могут быть получены после прослушивания вводного односеместрового курса по каждому из упомянутых выше предметов, приблизительно эквивалентного курсам В2, II, 12 и 13 учебной программы, предлагаемой Ассоциацией по вычислительным машинамг) в Программе 68. При написании книги я использовал ее как основной текст в односеместровом курсе в Корнеллском и Вашингтонском университетах. Книга может быть использована в одно-или двухсеместровом курсе для студентов как младших, так и старших курсов, и содержит почти все темы, предложенные в курсе 14 Программы 68 и в более позднем докладе COSINE ").
') ACM Curriculum Committee on Computer Science. Curriculum 68, recommendations for academic programs in computer science. Comm. ACM, 11, 3 (March 1968), 151—197.
2) COSINE' Committee of the Commission on Education. An undergraduate course on operating system principles (Denning P, 1., chairman). Commission on Education, National Academy of Engineering, Washington, D. C., 1971.
Предисловие
С моей точки зрения предмет операционных систем наиболее удобно разделять на три связанные области: управление процессами, управление ресурсами и файловые системы. Каждая из девяти глав этой книги касается некоторых аспектов одной или более из указанных областей. В главе 1 проводится обзор организации систем аппаратуры и программного обеспечения, включая историю вопроса. В главе 2 в качестве примера использована простая реализация системы пакетной обработки (по одному заданию во времени) для пояснения некоторых основных принципов работы связывающих загрузчиков и методов ввода-вывода. Модель взаимодействующих процессов как средство описания систем и как основа для решения проблем связи и синхронизации процессов (включая некоторые проблемы, введенные в главе 2) развита в главе 3. Глава 4 является введением в системы мультипрограммирования и построена на материале, разработанном в предыдущих главах; в ней обсуждаются требования к аппаратуре и программному обеспечению для мультипрограммирования, «виртуальные» машины, воспринимаемые пользователями и системными программистами," и методология проектирования. Методы управления реальной и виртуальной памятью исследованы в главе 5; в следующей главе (гл. 6) продолжается изучение ресурса основной памяти, обсуждаются проблемы разделения единственной копии информации в системах реальной и виртуальной памяти. Идеи управления ресурсами и процессами изложены в главе 7, где полное ядро системы рассматривается в качестве модели для изучения системных структур данных процессов ввода-вывода, управления прерываниями и методов распределения. В главе 8 подробно описываются системные тупики; методы определения, восстановления и предотвращения тупиков описаны как для последовательно используемых, так и для потребляемых ресурсов. В последней главе (гл. 9) рассматриваются основные элементы файловых систем, включая раздел о восстановлении из аварийных ситуаций.
Книга содержит много упражнений, которые настоятельно рекомендуется выполнить читателю. При изучении новых идей, связанных с системами ЭВМ, особенно важно, чтобы студентам была дана возможность практически реализовать эти идеи
с помощью программирования проектов. Составить нетривиальные, но объяснимые проекты нелегко; по этой причине в книгу включено приложение, содержащее подробную спецификацию большого, но управляемого мультипрограммного проекта, который я с успехом использовал несколько раз на практике.
Я старался оснастить весь материал точными ссылками, чтобы читатель мог глубже изучить интересующую его область или ознакомиться с другой точкой зрения, и поэтому указал источники каждого метода или идеи. Я искренне сожалею о любых ошибках или пропусках в указании этих источников. Все источники приведены в конце книги; ссылки на них в тексте даются по фамилии автора, сопровождаемой датой, например: Дейкстра, 1965Ь.
Благодарности
Я очень признателен ряду сотрудников за их помощь, поддержку и одобрение во время подготовки этой рукописи. В.Ф.Миллер первый открыл для меня мир радостей и удовлетворения научными исследеваниями и"* постижением знаний и оказал мне поддержку в самом начале работы над книгой по операционным системам. Я имел счастье быть ассистентом Н. Вирта по его курсу системного программирования в Стен-фордском университете в 1965/66 г. и сделал ряд заметок на основе его лекций1); эти заметки содержали ряд главных идей, на которых базируется проектирование и конструирование операционных систем и компиляторов. Я также признателен Вирту, указавшему мне, что системное проектирование и программирование могут быть научной дисциплиной.
Дж. Джордж и Дж. Хорнинг прочитали рукопись и внесли много конструктивных предложений. В основу книги были положены лабораторные работы курса операционных систем в Корнеллском и Вашингтонском университетах; я благодарен студентам, слушавшим этот курс, за их энергию, любознательность, чувство юмора и готовность помочь созданию новой научной области. Дж. Эндрюс, Р. Холт, Н. Вейдерман и Т. Уил-кокс оказали особенно большую помощь не только в указанном
') Shaw А. С., Lecture Notes on a Course in Systems Programming. Tech. Report No. 52, Computer Science Dept, Stanford, Calif. Dec. 1966,
Оглавление
Предисловие редактора перевода 5
Предисловие ^
1. Организация вычислительных систем
1.1. Некоторые определения
1.2. Нотация для алгоритмов Упражнение
1.3. Исторический аспект
1.3.1. Ранние системы
1.3.2. Второе поколение аппаратуры и программного обеспечения 20
1.3.3. Системы третьего и последующих поколений
1.4. Некоторые аспекты операционных систем 23
1.4.1. Виртуальные машины, трансляция и распределение ресурсов 24
1.4.2. Четыре ключевые проблемы 27
1.5. Организация систем 28
2. Системы пакетной обработки 31
2.1. Введение 31
2.2. Связывание и загрузка 32
2.2.1. Статическое перемещение 34
2.2.2. Процесс связывания 35
Упражнение 40
2.3. Методы ввода-вывода 40
2.3.1. Прямой ввод-вывод 42
2.3.2. Косвенный ввод-вывод 43
2.4. Программное обеспечение буферизации ввода-вывода 45
2.4.1. ЦОУ опрашивает канал 46
2.4.2. Составные буферы и сопрограммная структура программ 49
Упражнения 55
2.4.3. Канал прерывает ЦОУ 55
Упражнение 58
2.4.4. Объединение буферов в пул для ввода и вывода 58
Упражнения 65
2.5. Супервизор ввода-вывода 67
Я. Взаимодействующие процессы 69
3.1. Параллельное программирование 69
3.1.1. Применения 69
Упражнение 72
3.1.2. Некоторые программные конструкции для параллелизма 72
Упражнения 77
3.2. Концепция процесса 77
3.3. Проблема критической секции 79
3.3.1. Проблема
3.3.2. Программное решение (Дейкстра, 1965а, 1968Ь) 81
Упражнения 85
3.4. Семафорные примитивы 86
3.4.1. Р- и V-операции 86
3.4.2. Взаимное исключение с помощью семчфорных операций 87
3.4.3. Семафоры как счетчики ресурсов и синхронизаторы
в проблемах производителя и потребителя 88
Упражнения 101
3.5. Реализация семафорных операций 103
3.5.1. Реализация с «занятым» ожиданием 104
Упражнения 105
3.5.2. Устранение занятого ожидания 105
Упражнение 107
3.6. Другие синхронизирующие примитивы 107
Упражнения 111
4. Введение в системы мультипрограммирования 112
4.1. Доводы в пользу мультипрограммирования 112
4.2. Компоненты систем 114
4.2.1. Характеристики аппаратуры 114
4.2.2. Базовое программное обеспечение 117
4.3. Ядро операционной системы 122
4.4. Пользовательский интерфейс 129 4.4.1. Командный и управляющий языки 129 4.4.2
Управление заданием 131
4.5. Элементы методологии проектирования 133
5. Управление основной памятью 137
5.1. Статическая и динамическая настройка адресов 137
5.1.1. Аппаратурная настройка адреса 137
5.1.2. Аргументы в пользу статического и динамического перемещений 139
Упражнение ИЗ
5.1.3. Типы виртуальной памяти 143
5.2. Принципы сегментации и страничной организации 145
5.2.1. Односегментное пространство имен 145
Упражнение 147
5.2.2. Многосегментное пространство имен 152
5.3. Защита реальной и виртуальной памяти 155
Упражнения 163
5.4. Стратегии распределения памяти 163
5.4.1. Распределение памяти в нестраничных системах 163
Упражнение 171
5.4.2. Распределение в страничных системах 172
Упражнения 179
5.5. Оценка страничной организации 180
5.6. Иерархии памяти 184
6. Разделение процедур и данных в основной памяти 189
6.1. Необходимость разделения ресурсов 189
6.2. Условия разделения программ 191
6.3. Разделение в системах со статическим распределением" 194
Упражнение , jgg
6.4. Динамическое разделение
6.4.1. Форма процедурного сегмента
6.4.2. Связывание данных 201 ( 6.4.3. Обращения к процедурам 202
Оглавление
7. Управление процессами и ресурсами
7.1. Структуры данных для процессов и ресурсов
7.1.1. Дескрипторы процесса . 20Г|
7.1.2. Дескрипторы ресурсов ,211
7.2. Основные операции над процессами и ресурсами
7.2.1. Управление процессом 211 Упражнения 23
7.2.2. Примитивы ресурсов j 23 Упражнение 22}
7.2.3. Полномочия процесса 22>
7.3. Прерывания и процессы ввода-вывода 231
7.4. Организация планировщиков процессов 234
7.4.1. Ведущие и разделяемые планировщики 23f
7.4.2. Приоритетное планирование 239 Упражнения 24!
7.5. Методы планирования 24! Упражнение 248
S. Проблема тупиков 241
8.1. Примеры тупиков в вычислительных системах
25) Упражнение
8.2. Модель системы Упражнения
8.3. Тупик в случае повторно используемых ресурсов
8.3.1. Графы повторно используемых ресурсов 261
8.3.2. Распознавание тупика 263 Упражнения
8.3.3. Выход из тупика 273 Упражнения 275
8.3.4. Методы предотвращения тупиков 27! Упражнения 282
8.4. Системы с потребляемыми ресурсами 28i Упражнения 29)
8.5. Графы обобщенных ресурсов 29) Упражнения 29!
8.6. Динамическое добавление и удаление процессов и ресурсов
,
9. Файловые системы 295
9.1. Виртуальная и реальная файловая память 291 •
9.2. Компоненты файловой системы
9.3. Логическая и физическая организации
: 9.4. Процедуры доступа д,,
9.4.1. Файловые справочники Упражнение
9.4.2. Дескрипторы файлов
9.4.3. Управление доступом Упражнение
9.4.4. Стандартные программы открытия и закрытия
9.5. Управление пространством вспомогательной памяти
9.6. Иерархическая модель для файловых систем
Упражнение
9.7. Восстановление при отказах системы Упражнение
