Об
авторах 12
Предисловие
14
От
издательства 16
Глава
1. Введение 17
1.1.
Что такое операционная система? 19
1.1.1. Операционная система как расширенная машина 19
1.1.2. Операционная система как менеджер ресурсов 21
1.2.
История операционных систем 21
1.2.1. Первое поколение(1945–1955): электронные лампы и коммутационные панели 22
1.2.2. Второе поколение(1955–1965): транзисторы и системы пакетной обработки 23
1.2.3. Третье поколение(1965–1980): интегральные схемы и многозадачность 25
1.2.4. Четвертое поколение (с 1980 года по наши дни): персональные компьютеры 30
1.2.5. История MINIX 31
1.3.
Понятия операционной системы 33
1.3.1. Процессы 34
1.3.2. Файлы 36
1.3.3. Оболочка 39
1.4.
Системные вызовы 40
1.4.1. Системные вызовы для управления процессами 43
1.4.2. Системные вызовы для управления сигналами 46
1.4.3. Системные вызовы для управления файлами 48
1.4.4. Системные вызовы для управления каталогами 53
1.4.5. Системные вызовы для защиты 55
1.4.6. Системные вызовы для работы со временем 57
1.5.
Структура операционной системы 57
1.5.1. Монолитные системы 57
1.5.2. Многоуровневые системы 59
1.5.3. Виртуальные машины
60
1.5.4. Модель клиент-сервер 63
1.6.
Краткий обзор следующих глав 65
Резюме
65
Вопросы
66
Глава 2. Процессы и нити 68
2.1. Процессы 68
2.1.1. Модель процесса 68
2.1.2. Реализация процессов 73
2.1.3. Нити 75
2.2. Межпроцессное взаимодействие 78
2.2.1. Состояние
состязания 78
2.2.2. Критические
области 80
2.2.3. Взаимное
исключение с активным ожиданием 80
2.2.4. Примитивы
межпроцессного взаимодействия 85
2.2.5. Семафоры 88
2.2.6. Мониторы 90
2.2.7. Передача
сообщений 94
2.3.
Классические проблемы межпроцессного взаимодействия 97
2.3.1. Проблема
обедающих философов 97
2.3.2. Проблема
читателей и писателей 100
2.3.3. Проблема спящего
брадобрея 101
2.4.
Планирование 104
2.4.1. Циклическое
планирование 106
2.4.2. Планирование
согласно приоритетам 107
2.4.3. Планирование с
несколькими очередями 108
2.4.4. “Самый короткий
процесс — следующий” 109
2.4.5. Гарантированное
планирование 111
2.4.6. Лотерейное
планирование 111
2.4.7. Планирование в
системах реального времени 112
2.4.8. Двухуровневый
механизм 114
2.4.9. Политика и
механизм планирования 115
2.5.
Обзор процессов в MINIX 115
2.5.1. Внутренняя
структура MINIX 116
2.5.2. Управление
процессами в MINIX 118
2.5.3. Взаимодействие
между процессами в MINIX 119
2.5.4. Планирование
процессов в MINIX 120
2.6.
Реализация процессов в MINIX 121
2.6.1. Структура
исходного кода MINIX 121
2.6.2. Общие
заголовочные файлы 124
2.6.3. Заголовочные
файлы MINIX 129
2.6.4. Структуры данных
процессов и заголовочные файлы 134
2.6.5. Начальная
загрузка MINIX 141
2.6.6. Инициализация
системы 144
2.6.7. Обработка
прерываний в MINIX 150
2.6.8. Взаимодействие
между процессами в MINIX 158
2.6.9. Планирование
процессов в MINIX 161
2.6.10.
Аппаратно-зависимая поддержка в ядре 163
2.6.11. Утилиты и
библиотека ядра 166
Резюме
169
Вопросы
170
Глава
3. Ввод/вывод 175
3.1.
Принципы аппаратуры ввода/вывода 175
3.1.1. Устройства
ввода/вывода 176
3.1.2. Контроллеры
устройств 177
3.1.3. Прямой доступ к
памяти (DMA) 179
3.2.
Принципы программного обеспечения ввода/вывода 182
3.2.1. Задачи
программного обеспечения ввода/вывода 182
3.2.2. Обработчики
прерываний 184
3.2.3. Драйверы
устройств 184
3.2.4. Независимое от
устройств программное обеспечение
ввода/вывода 185
3.2.5. Программное
обеспечение ввода/вывода пространства
пользователя 188
3.3.
Взаимоблокировка 189
3.3.1. Ресурсы 190
3.3.2. Понятие взаимной
блокировки 192
3.3.3. Страусовый
алгоритм 196
3.3.4. Обнаружение и
устранение взаимоблокировок 197
3.3.5. Предотвращение
взаимоблокировок 197
3.3.6. Избежание
взаимоблокировок 200
3.4.
Обзор ввода/вывода в MINIX 205
3.4.1. Обработчики
прерываний в MINIX 205
3.4.2. Драйверы
устройств в MINIX 207
3.4.3.
Аппаратно-независимый код ввода/вывода в MINIX 211
3.4.4. Программы
ввода/вывода пользовательского
уровня в MINIX 211
3.4.5. Тупики в MINIX 212
3.5.
Блочные устройства в MINIX 213
3.5.1. Обзор драйверов
блочных устройств в MINIX 213
3.5.2. Общие программы
драйверов блочных устройств 216
3.5.3. Библиотека
поддержки драйверов 219
3.6.
RAM-диски 221
3.6.1. Аппаратное и
программное обеспечение RAM-диска 222
3.6.2. Обзор драйвера
RAM-диска в MINIX 223
3.6.3. Реализация
драйвера RAM-диска в MINIX 224
3.7.
Диски 226
3.7.1. Аппаратная часть
дисков 226
3.7.2. Программное
обеспечение жестких дисков 228
3.7.3. Обзор драйверов
жестких дисков в MINIX 235
3.7.4. Реализация
драйвера жесткого диска в MINIX 239
3.7.5. Работа с
дисководом для гибких дисков 247
3.8.
Часы 250
3.8.1. Аппаратное
обеспечение часов 250
3.8.2. Программное
обеспечение часов 251
3.8.3. Обзор драйвера
часов в MINIX 255
3.8.4. Реализация
драйвера часов в MINIX 259
3.9.
Терминалы 263
3.9.1. Аппаратное
обеспечение терминала 264
3.9.2. Программное
обеспечение терминала 270
3.9.3. Обзор драйвера
терминала в MINIX 279
3.9.4. Реализация
аппаратно-независимого драйвера терминала 294
3.9.5. Реализация
драйвера клавиатуры 313
3.9.6. Реализация
драйвера экрана 318
3.10.
Задача системы в MINIX 326
Резюме
334
Вопросы
335
Глава
4. Управление памятью 341
4.1.
Простые способы управления памятью 342
4.1.1. Однозадачная
система без подкачки на диск 342
4.1.2. Многозадачность с
фиксированными разделами 343
4.2.
Подкачка 346
4.2.1. Управление
памятью с помощью битовых массивов 349
4.2.2. Управление
памятью с помощью списков 350
4.3.
Виртуальная память 353
4.3.1. Страничная
организация памяти 354
4.3.2. Таблицы страниц 357
4.3.3. Буферы быстрого
преобразования адреса (TLB) 363
4.3.4. Инвертированные
таблицы страниц 366
4.4.
Алгоритмы замещения страниц 367
4.4.1. Оптимальное
замещение страниц 367
4.4.2. Алгоритм
NRU — не использовавшаяся
в последнее время
страница 368
4.4.3. Алгоритм FIFO:
первым прибыл — первым обслужен 369
4.4.4. Алгоритм “вторая
попытка” 370
4.4.5. Алгоритм “часы” 371
4.4.6. Алгоритм
LRU — страница, не использовавшаяся
дольше всего 372
4.4.7. Программное
моделирование алгоритма LRU 373
4.5.
Разработка систем со страничной организацией памяти 375
4.5.1. Модель “рабочий
набор” 375
4.5.2. Политики
распределения памяти: локальная и глобальная 377
4.5.3. Размер страницы 379
4.5.4. Интерфейс
виртуальной памяти 381
4.6.
Сегментация 382
4.6.1. Реализация
сегментации 386
4.6.2. Сегментация с
использованием страниц: MULTICS 386
4.6.3. Сегментация с
использованием страниц: Intel Pentium 390
4.7.
Обзор управления памятью в MINIX 396
4.7.1. Распределение
памяти 397
4.7.2. Обработка
сообщений 400
4.7.3. Структуры данных
и алгоритмы менеджера памяти 402
4.7.4. Системные вызовы
fork, exit и wait 406
4.7.5. Системный вызов
exec 407
4.7.6. Системный вызов
brk 411
4.7.7. Обработка
сигналов 412
4.7.8. Прочие системные
вызовы 418
4.8.
Реализация управления памятью в MINIX 419
4.8.1. Заголовочные
файлы и структуры данных 419
4.8.2. Основная
программа 421
4.8.3. Системные вызовы
fork, exit и wait 422
4.8.4. Реализация
системного вызова exec 425
4.8.5. Реализация вызова
brk 426
4.8.6. Реализация
сигналов 427
4.8.7. Прочие системные
вызовы 433
4.8.8. Утилиты менеджера
памяти 434
Резюме
436
Вопросы
437
Глава
5. Файловые системы 442
5.1. Файлы 443
5.1.1. Именование файлов 443
5.1.2. Структура файла 444
5.1.3. Типы файлов 446
5.1.4. Доступ к файлам 448
5.1.5. Атрибуты файла 449
5.1.6. Операции с файлами 450
5.2. Каталоги 452
5.2.1. Иерархические системы
каталогов 452
5.2.2. Пути 454
5.2.3. Операции с каталогами 456
5.3. Реализация файловой системы 457
5.3.1. Реализация файлов 457
5.3.2. Реализация каталогов 461
5.3.3. Организация дискового
пространства 464
5.3.4. Надежность файловой системы 467
5.3.5. Производительность файловой
системы 473
5.3.6. Файловые системы с журнальной структурой, LFS 476
5.4. Безопасность 478
5.4.1. Понятие безопасности 479
5.4.2. Знаменитые дефекты систем безопасности
480
5.4.3. Атака системы безопасности 484
5.4.4. Принципы проектирования
систем безопасности 487
5.4.5. Аутентификация пользователей 488
5.5. Механизмы защиты 493
5.5.1. Домены защиты 493
5.5.2. Списки управления доступом 495
5.5.3. Мандаты 497
5.5.4. Секретные каналы 498
5.6. Обзор файловой системы MINIX 500
5.6.1. Сообщения 501
5.6.2. Структура файловой системы 503
5.6.3. Битовые карты 506
5.6.4. I-узлы 508
5.6.5. Кэш блоков 509
5.6.6. Каталоги и пути 511
5.6.7. Дескрипторы файлов 513
5.6.8. Захват файлов 515
5.6.9. Каналы ввода/вывода и специальные файлы 516
5.6.10. Пример: системный вызов read 517
5.7. Реализация файловой системы MINIX 518
5.7.1. Заголовочные файлы и глобальные структуры
данных 519
5.7.2. Таблицы 523
5.7.3. Основная программа 531
5.7.4. Работа с отдельными файлами 534
5.7.5. Каталоги и пути 543
5.7.6. Прочие вызовы файловой
системы 547
5.7.7. Интерфейс устройств
ввода/вывода 550
5.7.8. Инструменты
общего назначения 552
Резюме
552
Вопросы
553
Глава 6. Библиография 557
6.1.
Литература, рекомендуемая для дальнейшего чтения 557
6.1.1. Введение и общие
труды 557
6.1.2. Процессы 559
6.1.3. Ввод/вывод 559
6.1.4. Управление
памятью 560
6.1.5. Файловые системы 561
6.2.
Алфавитный список литературы 562
Алфавитный указатель 568