- •Часть 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)
13.1.4. Прямой доступ к памяти (Direct Memory Access – dma).
Использование механизма прерываний позволяет разумно загружать процессор в то время, когда устройство ввода-вывода занимается своей работой. Однако запись или чтение большого количества информации из адресного пространства ввода-вывода (например, с диска) приводят к большому количеству операций ввода-вывода, которые должен совершать процессор. Для разгрузки процессора от операций последовательного вывода данных из оперативной памяти или последовательного ввода в нее был предложен механизм прямого доступа внешних устройств к памяти – ПДП или Direct Memory Access – DMA. Давайте кратко рассмотрим, как работает этот механизм.
Для того чтобы какое-либо устройство помимо процессора могло записать информацию в память или прочитать ее из памяти, необходимо чтобы это устройство могло забрать у процессора управление локальной магистралью для выставления соответствующих сигналов на шины адреса, данных и управления. Для централизации эти обязанности обычно возлагаются не на каждое устройство в отдельности, а на специальный контроллер – контроллер прямого доступа к памяти. Контроллер прямого доступа к памяти имеет несколько спаренных линий – каналов DMA, которые могут подключаться к различным устройствам. Перед началом использования прямого доступа к памяти этот контроллер необходимо запрограммировать, записав в его порты информацию о том, какой канал или каналы предполагается задействовать, какие операции они будут совершать, какой адрес памяти является начальным для передачи информации, и какое количество информации должно быть передано. Получив по одной из линий каналов DMA сигнал запроса на передачу данных от внешнего устройства, контроллер по шине управления сообщает процессору о желании взять на себя управление локальной магистралью. Процессор, возможно через некоторое время, необходимое для завершения его действий с магистралью, передает управление ею контроллеру DMA. известив его специальным сигналом. Контроллер DMA выставляет на адресную шину адрес памяти для передачи очередной порции информации и по второй линии канала прямого доступа к памяти сообщает устройству о готовности магистрали к передаче данных. После этого, используя шину данных и шину управления, контроллер DMA, устройство ввода-вывода и память осуществляют процесс обмена информацией. Затем контроллер прямого доступа к памяти извещает процессор о своем отказе от управления магистралью, и тот берет руководящие функции на себя. При передаче большого количества данных весь процесс повторяется циклически.
При прямом доступе к памяти процессор и контроллер DMA по очереди управляют локальной магистралью. Это, конечно, несколько снижает производительность процессора, так как при выполнении некоторых команд или при чтении очередной порции команд во внутренний кэш он должен поджидать освобождения магистрали, но в целом производительность вычислительной системы существенно возрастает.
При подключении к системе нового устройства, которое умеет использовать прямой доступ к памяти, обычно необходимо программно или аппаратно задать номер канала DMA, к которому будет приписано устройство. В отличие от прерываний, где один номер прерывания мог соответствовать нескольким устройствам, каналы DMA всегда находятся в монопольном владении устройств.