Эта книга представляет собой полное и систематизированное введение в теорию операционных систем. Она содержит как обсуждение фундаментальных принципов проектирования, так анализ и важнейших особенностей современных ОС. Материал книги дает ясное представление об основных структурах и механизмах операционных систем, а также о важнейших соглашениях и конструктивных решениях, используемых при их разработке. Книга будет полезна как студентам, изучающим соответствующий курс в учебных заведениях высшей школы, так специалистам-профессионалам, интересующимся вопросами построения и функционирования операционных систем. Содержание Предисловие 21 Замысел 21 Примеры систем 22 Предполагаемый круг читателей 22 Услуги по Internet для преподавателей и студентов 23 Добавления к четвертому изданию 23 Благодарности 23 Глава О. Руководство читателя 25 0.1. Краткое содержание книги 26 Часть 1. Основные понятия 26 Часть 2. Процессы 26 Часть 3. Память 26 Часть 4. Планирование 26 Часть 5. Операции ввода-вывода и файлы 26 Часть 6. Распределенные системы 26 Часть 7. Безопасность 26 0.2. Порядок изложения тем 27 0.3. Ресурсы internet 28 Web-узлы, имеющие отношение к этой книге 28 Другие Web-узлы 29 Конференции USENET 30 Часть 1. Основные понятия 31 Глава 1. Обзор компьютерных систем 33 1.1. Основные элементы 34 1.2. Регистры процессора 35 Регистры, доступные пользователю 36 Управляющие регистры и регистры состояния 37 1.3. Исполнение команд 38 Выборка и исполнение команды 38 Функции ввода-вывода 41 1.4. Прерывания 42 Прерывания и цикл команды 43 Обработка прерываний 46 Множественные прерывания 49 Многозадачность 52 1.5. Иерархия запоминающих устройств 53 1.6. Кэш Обоснование 57 Принципы работы кэша 57 Внутреннее устройство кэша 60 1.7. Технологии ввода-вывода 61 1.8. Программируемый ввод-вывод 62 1.9. Ввод-вывод с использованием прерываний 62 Прямой доступ к памяти 64 1.10. Рекомендуемая литература 65 1.9. Задачи 66 Приложение А. Характеристики производительности двухуровневой памяти 68 Локализация 69 Функционирование двухуровневой памяти 72 Производительность 72 Приложение Б. Управление процедурами 76 Реализация стека 76 Вызов процедуры и возврат из нее 76 Реентерабельные процедуры 78 Глава 2. Обзор операционных систем 81 2.1. Предназначение и функции операционных систем 82 Операционная система как интерфейс между пользователем и компьютером 82 Операционная система как диспетчер ресурсов 84 Возможность развития операционной системы 85 2.2. Эволюция операционных систем 87 Последовательная обработка данных 87 Простые пакетные системы 88 Многозадачные пакетные системы 91 Системы, работающие в режиме разделения времени 94 2.3. Основные достижения 97 Процессы 97 Управление памятью 101 Защита информации и безопасность 104 Совместное использование ресурсов и управление ими 105 Структура системы 107 2.4. Характеристики современных операционных систем 111 2.5. Обзор операционной системы Windows 2000 115 История возникновения 115 Однопользовательская многозадачность 117 Модель клиент/сервер 122 Потоки и симметричная многопроцессорность 123 Объекты Windows 2000 124 2.6. Традиционные системы Unix 126 Историческая справка 126 Описание 128 2.7. Современные системы Unix 130 System V Release 4 (SVR4) 130 Solaris 2.x 131 4.4BSD 131 Linux 132 2.8. Рекомендуемая литература 135 2.9. Задачи 136 Часть 2. Процессы 139 Глава 3. Описание процессов и управление ими 143 3.1. Состояния процессов 144 Модель процесса с двумя состояниями 147 Создание и завершение процессов 148 Модель с пятью состояниями 151 Приостановленные процессы 156 3.2. Описание процессов 162 Управляющие структуры операционной системы 162 Структуры управления процессами 164 3.3. Управление процессами 172 Модели выполнения 172 Создание процессов 174 Переключение процессов 175 Выполнение кода операционной системы 178 3.4.Управление процессами в операционной системе Unix SVR4 182 Состояния процессов 182 Описание процессов 184 Управление процессами 187 3.5. резюме, ключевые термины и контрольные вопросы 188 Ключевые термины 189 Контрольные вопросы 189 3.6. Рекомендуемая литература 190 3.7. Задачи 190 Глава 4. Потоки, симметричная мультипроцессорная обработка и микроядра 195 4.1. Процессы и потоки 196 Много поточность 197 Функциональность потоков 200 Пример: Adobe PageMaker 203 Потоки на пользовательском уровне и на уровне ядра 205 Другие схемы 210 4.2. Симметричная многопроцессорная обработка 213 Архитектура SMP 213 Организация симметричной многопроцессорной системы 215 Архитектура многопроцессорных операционных систем 216 4.3. Микроядра 217 Архитектура микроядра 218 Достоинства архитектуры с микроядром 219 Производительность микроядра 221 Архитектура микроядер 222 4.4. Потоки и SMP в Windows 2000 224 Объекты процессов и потоков 226 Многопоточность 228 Состояния потоков 229 Поддержка подсистем операционной системы 230 Поддержка симметричной многопроцессорной обработки 231 4.5. Управление потоками и SMP в SOLARIS 231 Многопоточная архитектура 231 Мотивация 233 Структура процессов 234 Выполнение потоков 235 Прерывания в роли потоков 237 4.6. Управление процессами и потоками в Linux 238 Процессы в Linux 238 Потоки в Linux 239 4.7. Резюме, ключевые термины и контрольные вопросы 240 Ключевые термины 241 Контрольные вопросы 241 4.8. Рекомендуемая литература 242 4.9. Задачи 242 Глава 5. Параллельные вычисления: взаимоисключения и многозадачность 245 5.1. Принципы параллельных вычислений 247 Простой пример 248 Участие операционной системы 250 Взаимодействие процессов 251 Требования к взаимным исключениям 256 5.2. Взаимоисключения: программный подход 256 Алгоритм Деккера 257 Алгоритм Петерсона 262 5.3. Взаимоисключения: аппаратная поддержка 263 Отключение прерываний 263 Специальные машинные команды 264 5.4. Семафоры 267 Взаимные исключения 271 Задача производителя/потребителя 273 Реализация семафоров 279 Задача о парикмахерской 280 5.5. Мониторы 286 Мониторы с сигналами 286 Мониторы с оповещением и широковещанием 290 5.6. Передача сообщений 292 Синхронизация 293 Адресация 295 Формат сообщения 296 Принцип работы очереди 297 Взаимные исключения 297 5.7. Задача читателей/писателей 299 Приоритетное чтение 300 Приоритетная запись 301 5.8. Резюме, ключевые термины и контрольные вопросы 305 Ключевые термины 306 Контрольные вопросы 306 5.9. Рекомендуемая литература 307 5.10. Задачи 307 Глава 6. Взаимоблокировка и голодание 319 6.1. Принципы взаимного блокирования 320 Повторно используемые ресурсы 323 Расходуемые ресурсы 325 Условия возникновения взаимоблокировок 326 6.2. Предотвращение взаимоблокировок 327 Взаимоисключения 327 Удержание и ожидание 327 Отсутствие перераспределения 328 Циклическое ожидание 328 6.3. Устранение взаимоблокировок 328 Запрещение запуска процесса 329 Запрет выделения ресурса 330 6.4. Обнаружение взаимоблокировок 334 Алгоритм обнаружения взаимоблокировки 334 Восстановление 336 6.5.Интегрированные стратегии разрешения взаимоблокировок 337 6.6. Задача об обедающих философах 338 6.7. Механизмы параллельных вычислений в Unix 340 Каналы 340 Сообщения 341 Разделяемая память 341 Семафоры 341 Сигналы 342 6.8. Примитивы синхронизации потоков SOLARIS 343 Блокировки взаимоисключений 343 Семафоры 344 Блокировки читатели/писатель 344 Переменные условий 345 6.9. Механизмы параллельных вычислений в Windows 2000 345 6.10. Резюме, ключевые термины и контрольные вопросы 347 Ключевые термины 348 Контрольные вопросы 348 6.11. Рекомендуемая литература 348 6.12. Задачи 349 Часть 3. Память 355 Глава 7. Управление памятью 357 7.1. Требования к управлению памятью 358 Перемещение 358 Защита 359 Совместное использование 360 Логическая организация 360 Физическая организация 361 7.2. Распределение памяти 361 Фиксированное распределение 363 Динамическое распределение 366 Система двойников 370 Перемещение 373 7.3. Страничная организация 374 7.4. Сегментация 378 7.5. Резюме, ключевые термины и контрольные вопросы 380 Ключевые термины 381 Контрольные вопросы 381 7.6. Рекомендуемая литература 381 7.7.Задачи 382 Приложение. Загрузка и связывание 383 Загрузка 384 Компоновка 388 Глава 8. Виртуальная память 391 8.1. Аппаратное обеспечение и управляющие структуры 392 Локализация и виртуальная память 395 Страничная организация 397 Сегментация 408 Комбинация сегментации и страничной организации 409 Защита и совместное использование 411 8.2. Программное обеспечение операционной системы 412 Стратегия выборки 414 Стратегия размещения 415 Стратегия замещения 415 Управление резидентным множеством 423 Стратегия очистки 430 Управление загрузкой 431 8.3. Управление памятью в Unix и SOLARIS 433 Страничная система 434 Распределение памяти ядра 437 8.4. Управление памятью в LINUX 439 Виртуальная память Linux 440 Распределение памяти ядра 441 8.5. Управление памятью в Windows 2000 441 Карта виртуальных адресов W2K 441 Страничная организация W2K 442 8.6. Резюме, ключевые термины и контрольные вопросы 444 Ключевые термины 445 Контрольные вопросы 445 8.7. Рекомендуемая литература 445 8.8. Задачи 446 Приложение. Хеш-таблицы 450 Часть 4. Планирование 455 Глава 9. Планирование в системах с одним процессором 457 9.1. Типы планирования процессора 458 Долгосрочное планирование 461 Среднесрочное планирование 462 Краткосрочное планирование 462 9.2. Алгоритмы планирования 463 Критерии краткосрочного планирования 463 Использование приоритетов 465 Альтернативные стратегии планирования 465 Сравнение производительности 480 Справедливое планирование 485 9.3. Традиционное планирование Unix 489 9.4. Резюме, ключевые термины и контрольные вопросы 490 Ключевые термины 492 Контрольные вопросы 492 9.5. Рекомендуемая литература 492 9.6. Задачи 493 Приложение А. Время отклика 496 Приложение Б. Очереди 499 Очередь с одним сервером 499 Очередь со многими серверами 502 Глава 10. Многопроцессорное планирование и планирование реального времени 505 10.1. Многопроцессорное планирование 506 Зернистость 506 Вопросы разработки 508 Планирование процессов 510 Планирование потоков 511 10.2. Планирование реального времени 519 Введение 519 Характеристики операционных систем реального времени 520 Планирование реального времени 523 Планирование с предельными сроками 525 Частотно-монотонное планирование 530 10.3. Планирование в Linux 533 10.4. Планирование в Unix SVR4 534 10.5. Планирование Windows 2000 536 Приоритеты процессов и потоков 536 Многопроцессорное планирование 539 10.6. Резюме, ключевые термины и контрольные вопросы 539 Ключевые термины 539 Контрольные вопросы 540 10.7. Рекомендуемая литература 540 10.8. Задачи 540 Часть 5. Операции ввода-вывода и файлы 543 Глава 11. Управление вводом-выводом и дисковое планирование 545 11.1. Устройства ввода-вывода 546 11.2. Организация функций ввода-вывода 548 Эволюция функций ввода-вывода 548 Прямой доступ к памяти 549 11.3. Вопросы проектирования операционных систем 553 Цели проектирования 553 Логическая структура функций ввода-вывода 553 11.4. Буферизация операций ввода-вывода 556 Одинарный буфер 557 Двойной буфер 559 Циклический буфер 559 Использование буферизации 560 11.5. Дисковое планирование 560 Параметры производительности диска 560 Время поиска 561 Задержка из-за вращения 562 Время передачи данных 562 Оценка времени 562 Стратегии дискового планирования 563 Приоритеты 566 Последним вошел - первым вышел 566 SSTF 567 SCAN 567 C-SCAN 567 N-step-SCAN и FSCAN 568 11.6. RAID 568 RAID 0 571 RAID 1 574 RAID 2 575 RAID 3 575 RAID 4 576 RAID 5 577 RAID 6 577 11.7. Дисковый кэш 578 Вопросы разработки 578 Анализ проектирования 580 11.8. Ввод-вывод в Unix SVR4 582 Буфер кэша 583 Очередь символов 584 Небуферизированный ввод-вывод 585 Устройства UNIX 585 11.9. Ввод-вывод в Windows 2000 586 Основные модули ввода-вывода 586 Асинхронный и синхронный ввод-вывод 587 Программное обеспечение RAID 588 11.10. Резюме, ключевые термины и контрольные вопросы 588 Ключевые термины 589 Контрольные вопросы 589 11.11. Рекомендуемая литература 590 11.12. Задачи 591 Приложение. Дисковые устройства 593 Магнитный диск 593 Оптическая память 598 CD-ROM 598 CD с возможностью записи 600 CD-R с возможностью перезаписи 601 DVD 601 Магнитооптические диски 601 Глава 12. Управление файлами 603 12.1. Обзор 604 Файлы 604 Системы управления файлами 606 Архитектура файловой системы 607 Функции управления файлами 608 12.2. Организация файлов и доступ к ним 610 Смешанный файл 612 Последовательный файл 613 Индексно-последовательный файл 614 Индексированный файл 615 Файл прямого доступа 615 12.3. Каталоги файлов 616 Содержимое 616 Структура 617 Присвоение имен 618 12.4. Совместное использование файлов 621 Права доступа 621 Одновременный доступ 622 12.5. Записи и блоки 622 12.6. Управление внешней памятью 624 Размещение файлов 625 Управление свободным пространством 631 Надежность 633 12.7. Управление файлами в Unix 634 Индексные узлы 635 Размещение файлов 635 12.8. Файловая система Windows 2000 638 Ключевые возможности NTFS 638 Том NTFS и файловая структура 639 Схема тома NTFS 640 Главная файловая таблица 641 Способность восстановления данных 641 12.9. Резюме, ключевые термины и контрольные вопросы 643 Ключевые термины 643 Контрольные вопросы 644 12.10. Рекомендуемая литература 644 12.11. Задачи 645 Часть 6. Распределенные системы 647 Глава 13. Распределенные вычисления, архитектура клиент/сервер и кластеры 649 13.1. Вычисления в архитектуре клиент/сервер 651 Что такое архитектура клиент/сервер 651 Приложения клиент/сервер 653 Промежуточное программное обеспечение 661 13.2. Распределенная передача сообщений 663 Вопросы надежности 665 Вопросы блокировки 666 13.3. Вызов удаленных процедур 666 Передача параметров 668 Представление параметров 668 Связывание клиент/сервер 668 Синхронный и асинхронный вызовы 669 Объектно-ориентированный механизм 669 13.4. Кластеры 670 Конфигурации кластеров 671 Вопросы разработки операционных систем 674 Архитектура кластера 675 Сравнение кластеров и SMP 678 13.5. Windows 2000 Cluster Server 678 13.6. Sun Cluster 680 Поддержка объектов и коммуникаций 681 Управление процессами 681 Сеть 681 Глобальная файловая система 682 13.7. Кластеры Beowulf И Linux 683 Возможности Beowulf 683 Программное обеспечение Beowulf 684 13.8. Резюме, ключевые термины и контрольные вопросы 685 Ключевые термины 686 Контрольные вопросы 686 13.9. Рекомендуемая литература 686 13.10. Задачи 687 Глава 14. Управление распределенными процессами 689 14.1. Миграция процессов 690 Обоснование 690 Механизмы переноса процессов 691 Согласование переноса 695 Вытесняющие и невытесняющие переносы 697 14.2. Распределенные глобальные состояния 698 Глобальные состояния и распределенные снимки 698 Алгоритм распределенного снимка 701 14.3. Распределенные взаимоисключения 703 Концепции распределенных взаимоисключений 704 Упорядочение событий в распределенной системе 706 Распределенная очередь 709 Подход с передачей маркера 713 14.4. Распределенная взаимоблокировка 715 Взаимоблокировка, связанная с распределением ресурсов 716 Взаимоблокировки, возникающие при обмене сообщениями 724 14.5. Резюме, ключевые термины и контрольные вопросы 728 Ключевые термины 729 Контрольные вопросы 729 14.6. Рекомендуемая литература 729 14.7. Задачи 730 Часть 7. Безопасность 731 Глава 15. Безопасность 733 15.1. Угрозы для безопасности 734 Виды угроз 735 Компоненты компьютерной системы 736 15.2. Защита 740 15.3. Взломщики 745 Стратегии выбора паролей 753 Выявление вторжений 755 15.4. Зловредное программное обеспечение 758 Зловредные программы 759 Природа вирусов 763 Подходы к борьбе с вирусами 766 Вирусы, распространяющиеся по электронной почте 769 15.5. Системы с доверительными отношениями 770 Защита от троянских коней 772 15.6. Безопасность операционной системы Windows 2000 774 Схема контроля доступа 774 Маркер доступа 775 Дескрипторы безопасности 776 15.7. Резюме, ключевые термины и контрольные вопросы 780 Ключевые термины 780 Контрольные вопросы 781 15.8. Рекомендуемая литература 781 15.9. Задачи 782 Приложение. Шифрование 784 Стандартное шифрование 784 Шифрование с открытым ключом 788 Приложение А. Протокол TCP/IP 793 А.1. Необходимость архитектуры протоколов 794 А. 2. Архитектура протоколов TCP/IP 795 Уровни протокола TCP/IP 795 Работа протоколов TCP и IP 796 Протоколы TCP и UDP 799 Протоколы IP и IPv6 800 Приложения TCP/IP 802 Приложение Б. Объектно-ориентированный подход 803 Б.1. Мотивация 804 Б.2. Объектно-ориентированные концепции 805 Структура объектов 806 Классы объектов 808 Включение 809 Б.З. Преимущества объектно-ориентированного подхода 810 Словарь терминов 811