- •Часть 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 Физические принципы организации ввода-вывода.
Существует много разнообразных устройств, которые могут взаимодействовать с процессором и памятью: таймер, жесткие диски, клавиатура, дисплеи, мышь, модемы и т.д., вплоть до устройств отображения и ввода информации в авиационно-космических тренажерах. Часть этих устройств может быть встроена внутрь корпуса компьютера, часть - вынесена за его пределы, и общаться с компьютером через различные линии связи: кабельные, оптоволоконные, радиорелейные, спутниковые и т.д. Конкретный набор устройств и способы их подключения определяются целями функционирования вычислительной системы, желаниями и финансовыми возможностями пользователя. Несмотря на все многообразие устройств, управление их работой и обмен информацией с ними строятся на относительно небольшом количестве принципов, которые мы постараемся разобрать в этом разделе.
13.1.1. Общие сведения об архитектуре компьютера.
В простейшем случае процессор, память и многочисленные внешние устройства связаны большим количеством электрических соединений - линий, которые в совокупности принято называть локальной магистралью компьютера. Внутри локальной магистрали линии, служащие для передачи сходных сигналов и предназначенные для выполнения сходных функций, принято группировать в шины. При этом понятие шины включает в себе не только набор проводников, но и набор жестко заданных протоколов, определяющий перечень сообщений, который может быть передан с помощью электрических сигналов по этим проводникам. В современных компьютерах выделяют, как минимум, три шины:
Шину данных, состоящую из линий данных и служащую для передачи информации между процессором и памятью, процессором и устройствами ввода-вывода, памятью и внешними устройствами.
Адресную шину, состоящую из линий адреса и служащую для задания адреса ячейки памяти или указания устройства ввода-вывода, участвующих в обмене информацией.
Шину управления, состоящую из линий управления локальной магистралью и линий ее состояния, определяющих поведение локальной магистрали. В некоторых архитектурных решениях линии состояния выносятся из этой шины в отдельную шину состояния.
Количество линий, входящих в состав шины, принято называть разрядностью (шириной) этой шины. Ширина адресной шины, например, определяет максимальный размер оперативной памяти, которая может быть установлена в вычислительной системе. Ширина шины данных определяет максимальный объем информации, которая за один раз может быть получена или передана по этой шине.
Операции обмена информацией осуществляются при одновременном участии всех шин. Рассмотрим, к примеру, действия, которые должны быть выполнены для передачи информации из процессора в память. В простейшем случае необходимыми являются три действия:
На адресной шине процессор должен выставить сигналы, соответствующие адресу ячейки памяти, в которую будет осуществляться передача информации.
На шину данных процессор должен выставить сигналы, соответствующие информации, которая должна быть записана в память.
После выполнения действий 1 и 2 на шину управления выставляются сигналы, соответствующие операции записи и работе с памятью, что приведет к занесению необходимой информации по требуемому адресу.
Естественно, что приведенные выше действия являются необходимыми, но недостаточными при рассмотрении работы конкретных процессоров и микросхем памяти. Конкретные архитектурные решения могут требовать дополнительных действий, например, выставления на шину управления сигналов частичного использования шины данных (для передачи меньшего количества информации, чем позволяет ширина этой шины), выставления сигнала готовности магистрали после завершения записи в память, разрешающего приступить к новой операции, и т.д., однако общие принципы выполнения операции записи в память остаются одинаковыми.
В то время как память легко можно представить себе в виде последовательности пронумерованных адресами ячеек, локализованных внутри одной микросхемы или набора микросхем, подобный подход неприменим к устройствам ввода-вывода. Внешние устройства разнесены пространственно и могут подключаться к локальной магистрали в одной точке или множестве точек, получивших название портов ввода-вывода. Тем не менее, точно так же, как ячейки памяти взаимно однозначно отображались в адресное пространство памяти, порты ввода-вывода можно взаимно однозначно отобразить в другое адресное пространство – адресное пространство ввода-вывода. При этом каждый порт ввода-вывода получает свой номер или адрес в этом пространстве. В некоторых случаях, когда адресное пространство памяти (размер которого определяется шириной адресной шины) задействовано не полностью (остались адреса, которым не соответствуют физические ячейки памяти), и протоколы работы с внешним устройством совместимы с протоколами работы с памятью, часть портов ввода-вывода может быть отображена непосредственно в адресное пространство памяти (так, например, поступают с видеопамятью дисплеев), правда тогда эти порты уже не принято называть портами. Надо отметить, что при отображении портов в адресное пространство памяти для организации доступа к ним в полной мере могут быть задействованы существующие механизмы защиты памяти без организации специальных защитных устройств.
В ситуации прямого отображения портов ввода-вывода в адресное пространство памяти действия, требуемые для записи информации и управляющих команд в эти порты или для чтения данных из них и их состояний, ничем не отличаются от действий, производимых для передачи информации между оперативной памятью и процессором, и для их выполнения применяются те же самые команды. Если же порт отображен в адресное пространство ввода-вывода, то процесс обмена информацией инициируется специальными командами ввода-вывода и включает в себя несколько другие действия. Например, для передачи данных в порт необходимо выполнить следующее:
На адресной шине процессор должен выставить сигналы, соответствующие адресу порта, в который будет осуществляться передача информации, в адресном пространстве ввода-вывода.
На шину данных процессор должен выставить сигналы, соответствующие информации, которая должна быть передана в порт.
После выполнения действий 1 и 2 на шину управления выставляются сигналы, соответствующие операции записи и работе с устройствами ввода-вывода (переключение адресных пространств!), что приведет к передаче необходимой информации в требуемый порт.
Существенным отличием памяти от устройств ввода-вывода является то, что занесение информации в память является окончанием операции записи, в то время как занесение информации в порт зачастую является инициализацией реального совершения операции ввода-вывода. Что именно должны совершать устройства, приняв информацию через свой порт, и каким именно образом они должны поставлять информацию для чтения из порта, определяется электронными схемами устройств, получившими названия контроллеров. Контроллер может непосредственно управлять отдельным устройством (например, контроллер диска), а может управлять несколькими устройствами, связываясь с их контроллерами посредством специальных шин ввода-вывода (шина IDE, шина SCSI и т.д.).
Современные вычислительные системы могут иметь разнообразную архитектуру, множество шин и магистралей, мосты для перехода информации от одной шины к другой и т.п. С точки зрения нашего рассмотрения важными является только следующие моменты:
Устройства ввода-вывода подключаются к системе через порты.
Могут существовать два адресных пространства: пространство памяти и пространство ввода-вывода.
Порты, как правило, отображаются в адресное пространство ввода-вывода и, иногда, непосредственно в адресное пространство памяти.
Использование того или иного адресного пространства определяется типом команды, выполняемой процессором, или типом ее операндов.
Физическим управлением устройством ввода-вывода, передачей информации через порт, и выставлением некоторых сигналов на магистрали занимается контроллер устройства.
Именно единообразие подключения внешних устройств к вычислительной системе является одной из составляющих идеологии, позволяющих добавлять новые устройства без перепроектирования всей системы.