- •Краткая история эволюции вычислительных систем.
- •Третий период (начало 60-х – 1980 г.). Компьютеры на основе интегральных микросхем. Первые многозадачные ос
- •Четвертый период (с 1980 г. По настоящее время). Персональные компьютеры. Классические, сетевые и распределенные системы
- •Основные понятия, концепции операционных систем.
- •Архитектурные особенности ос. Монолитное ядро. Многоуровневые системы. Виртуальные машины. Микроядерная архитектура. Смешанные системы.
- •1.4.1 Монолитное ядро
- •1.4.2 Слоеные системы (Layered systems)
- •1.4.3 Виртуальные машины
- •1.4.4 Микроядерная архитектура.
- •1.4.5 Смешанные системы
- •Классификация ос. Критерии классификации.
- •Процессы. Понятие процесса. Состояние процесса.
- •2.1. Понятие процесса
- •2.2. Состояния процесса
- •Операции над процессами. Набор операций. Process Control Block и контекст процесса.
- •Одноразовые и многоразовые операции. Переключение контекста.
- •2.3.3. Одноразовые операции
- •2.3.4. Многоразовые операции
- •2.3.5. Переключение контекста
- •Планирование процессов. Уровни планирования. Критерии планирования и требования к алгоритмам.
- •3.1. Уровни планирования
- •3.2. Критерии планирования и требования к алгоритмам
- •Планирование процессов. Параметры планирования. Вытесняющее и невытесняющее планирование.
- •3.3. Параметры планирования
- •3.4. Вытесняющее и невытесняющее планирование
- •Алгоритмы планирования процессов. First-Come, First-Served (fcfs).
- •Алгоритмы планирования процессов. Round Robin (rr).
- •Алгоритмы планирования процессов. Shortest-Job-First (sjf).
- •Гарантированное планирование процессов. Приоритетное планирование.
- •3.5.5. Приоритетное планирование
- •Многоуровневые очереди (Multilevel Queue), многоуровневые очереди с обратной связью (Multilevel Feedback Queue).
- •3.5.7. Многоуровневые очереди с обратной связью (Multilevel Feedback Queue)
- •Кооперация процессов. Взаимодействующие процессы. Категории средств обмена информацией.
- •4.1. Взаимодействующие процессы
- •4.2. Категории средств обмена информацией
- •Логическая организация механизма передачи информации. Информационная валентность процессов и средств связи.
- •Особенности передачи информации с помощью линий связи. Буферизация. Нити исполнения.
- •4.3.3.1 Буферизация
- •Механизмы синхронизации процессов. Семафоры. Концепция семафоров. Мониторы. Сообщения.
- •6.1. Семафоры
- •6.1.1. Концепция семафоров
- •6.3. Сообщения
- •Тупики. Условия возникновения. Обнаружение тупиков. Основные направления борьбы с тупиками.
- •7.2 Концепция ресурса
- •7.3 Условия возникновения тупиков
- •7.4 Основные направления борьбы с тупиками.
- •Физическая организация памяти компьютеров.
- •21.Логическая память. Связывание адресов.
- •Схемы управления памятью. Схема с фиксированными разделами.
- •Схемы управления памятью. Оверлейная структура.
- •24.Схемы управления памятью. Динамическое распределение. Свопинг. Схема с переменными разделами.
- •8.3.3 Мультипрограммирование с переменными разделами.
- •Страничная память. Сегментная и сегментно-страничная организация памяти.
- •9.2.1 Страничная память
- •Архитектурные средства поддержки виртуальной памяти. Страничная виртуальная память.
- •9.2.1 Страничная память
- •Архитектурные средства поддержки виртуальной памяти. Сегментно-страничная организация виртуальной памяти. Структура таблицы страниц.
- •9.2.3 Таблица страниц
- •Ассоциативная память. Размер страниц. Инвертированная таблица страниц.
- •Аппаратно-независимый уровень управления виртуальной памятью. Алгоритмы замещения страниц. Алгоритм fifo. Выталкивание первой пришедшей страницы. Аномалия Билэди.
- •10.3.1 Fifo алгоритм. Выталкивание первой пришедшей страницы.
- •10.3.2 Оптимальный алгоритм
- •Аппаратно-независимый уровень управления виртуальной памятью. Управление количеством страниц, выделенным процессу. Модель рабочего множества. Трешинг.
- •Файловая система. Имена файлов. Типы файлов. Атрибуты файлов. Организация файлов и доступ к ним. Операции над файлами.
- •11.2 Имена файлов
- •11.4 Типы и атрибуты файлов
- •11.5 Доступ к файлам
- •Директории. Логическая структура файлового архива. Операции над директориями. Реализация файловой системы. Структура файловой системы. Защита файлов
- •11.8 Операции над директориями
- •Управление внешней памятью. Методы выделения дискового пространства. Управление свободным и занятым дисковым пространством. Размер блока.
- •12.3.2 Управление свободным и занятым дисковым пространством.
- •12.3.3 Размер блока
- •Система управления вводом – выводом. Физические принципы организации ввода – вывода. Структура контроллера устройств. Прямой доступ к памяти (Direct Memory Access – dma).
- •13.1 Физические принципы организации ввода-вывода.
- •Структура контроллера устройства.
- •Прямой доступ к памяти (Direct Memory Access – dma).
- •Логические принципы организации ввода – вывода. Структура системы ввода – вывода. Буферизация и кэширование.
- •13.2.1. Структура системы ввода-вывода.
- •Буферизация и кэширование.
- •Сети и сетевые операционные системы. Сетевые и распределенные операционные системы. Понятие протокола. Структура сетевой операционной системы
- •Адресация в сети. Одноуровневые адреса. Двухуровневые адреса. Удаленная адресация и разрешение адресов. Локальная адресация. Понятие порта. Полные адреса
- •Безопасность операционных систем. Угрозы безопасности. Криптография – базовая технология безопасности операционных систем.
- •15.2 Классификация угроз
- •15.3 Формализация подхода к обеспечению информационной безопасности. Классы безопасности
- •15.4 Политика безопасности
- •15.5 Криптография, как одна из базовых технологий безопасности ос.
- •Защитные механизмы операционных систем. Идентификация и аутентификация. Пароли, уязвимость паролей. Авторизация. Разграничение доступа.
- •16.1 Идентификация и аутентификация
- •16.1.1 Пароли, уязвимость паролей
Механизмы синхронизации процессов. Семафоры. Концепция семафоров. Мониторы. Сообщения.
Рассмотренные в конце предыдущей главы алгоритмы хотя и являются корректными, но достаточно громоздки и не обладают элегантностью. Более того, процедура ожидания входа в критический участок включает в себя достаточно длительное вращение процесса в пустом цикле, вхолостую пожирая драгоценное время процессора. Существуют и другие серьезные недостатки у алгоритмов, построенных средствами обычных языков программирования. Допустим, что в вычислительной системе находятся два взаимодействующих процесса: один из них — H — с высоким приоритетом, другой — L — с низким приоритетом. Пусть планировщик устроен так, что процесс с высоким приоритетом вытесняет низкоприоритетный процесс всякий раз, когда он готов к исполнению, и занимает процессор на все время своего CPU burst (если не появится процесс с еще большим приоритетом). Тогда в случае, когда процесс L находится в своей критической секции, а процесс H, получив процессор, подошел ко входу в критическую область, мы получаем тупиковую ситуацию. Процесс H не может войти в критическую область, находясь в цикле, а процесс L не получает управления, чтобы покинуть критический участок.
Для того чтобы устранить возникновение подобных проблем были разработаны различные механизмы синхронизации более высокого уровня: семафоры, мониторы и сообщения, рассмотрению которых и посвящена данная глава.
6.1. Семафоры
Одним из первых механизмов, предложенных для синхронизации поведения процессов, стали семафоры, концепцию которых описал Дейкстра (Dijkstra) в 1965 году.
6.1.1. Концепция семафоров
Семафор представляет собой целую переменную, принимающую неотрицательные значения, доступ любого процесса к которой, за исключением момента ее инициализации, может осуществляться только через две атомарные операции: P (от датского слова proberen — проверять) и V (от verhogen — увеличивать). Классическое определение этих операций выглядит следующим образом:
P(S): |
пока S == 0 процесс блокируется; S = S – 1; |
V(S): |
S = S + 1; |
Эта запись означает следующее: при выполнении операции P над семафором S сначала проверяется его значение. Если оно больше 0, то из S вычитается 1. Если оно меньше или равно 0, то процесс блокируется до тех пор, пока S не станет больше 0, после чего из S вычитается 1. При выполнении операции V над семафором S к его значению просто прибавляется 1.
П одобные переменные-семафоры могут быть с успехом применены для решения различных задач организации взаимодействия процессов. В ряде языков программирования они были непосредственно введены в синтаксис языка (например, в ALGOL-68), в других случаях применяются через использование системных вызовов. Соответствующая целая переменная располагается внутри адресного пространства ядра операционной системы. Операционная система обеспечивает атомарность операций P и V, используя, например, метод запрета прерываний на время выполнения соответствующих системных вызовов. Если при выполнении операции P заблокированными оказались несколько процессов, то порядок их разблокирования может быть произвольным, например, FIFO.
Мониторы
Хотя решение задачи producer-consumer с помощью семафоров выглядит достаточно элегантно, программирование с их использованием требует повышенной осторожности и внимания, чем, отчасти, напоминает программирование на языке ассемблера. Допустим, что в рассмотренном примере мы случайно поменяли местами операции P, сначала выполняя ее для семафора mutex, а уже затем для семафоров full и empty. Допустим теперь, что потребитель, войдя в свой критический участок (mutex сброшен), обнаруживает, что буфер пуст. Он блокируется и начинает ждать появления сообщений. Но производитель не может войти в критический участок, для передачи информации, так как тот заблокирован потребителем. Получаем тупиковую ситуацию.
В сложных программах произвести анализ правильности использования семафоров с карандашом в руках становится очень непростым занятием. В то же время обычные способы отладки программ зачастую не дают результата, поскольку возникновение ошибок зависит от interleaving’а атомарных операций, и ошибки могут быть трудно воспроизводимы. Для того чтобы облегчить труд программистов, в 1974 году Хором (Hoare) был предложен механизм еще более высокого уровня, чем семафоры, получивший название мониторов. Мы с вами рассмотрим конструкцию, несколько отличающуюся от оригинальной.
Мониторы представляют собой тип данных, который может быть с успехом внедрен в объектно-ориентированные языки программирования. Монитор обладает своими собственными переменными, определяющими его состояние. Значения этих переменных извне монитора могут быть изменены только с помощью вызова функций-методов, принадлежащих монитору. В свою очередь, эти функции-методы могут использовать в своей работе только данные, находящиеся внутри монитора и свои параметры. На абстрактном уровне можно описать структуру монитора следующим образом:
monitor monitor_name {
описание переменных ; void m1(...){... } void m2(...){... } ... void mn(...){... } {
блок инициализации внутрениих переменных ;
}
}
Здесь функции m1,..., mn представляют собой функции-методы монитора, а блок инициализации внутренних переменных содержит операции, которые выполняются только один раз: при создании монитора или при самом первом вызове какой-либо функции-метода до ее исполнения.
Важной особенностью мониторов является то, что в любой момент времени только один процесс может быть активен, т. е. находиться в состоянии готовность или исполнение, внутри данного монитора. Поскольку мониторы представляют собой особые конструкции языка программирования, то компилятор может отличить вызов функции, принадлежащей монитору, от вызовов других функций и обработать его специальным образом, добавив к нему пролог и эпилог, реализующий взаимоисключение. Так как обязанность конструирования механизма взаимоисключений возложена на компилятор, а не на программиста, работа программиста при использовании мониторов существенно упрощается, а вероятность появления ошибок становится меньше.
Однако одних только взаимоисключений не достаточно для того, чтобы в полном объеме реализовать решение задач, возникающих при взаимодействии процессов. Нам нужны еще и средства организации очередности процессов, подобно семафорам full и empty в предыдущем примере. Для этого в мониторах было введено понятие условных переменных (condition variables), над которыми можно совершать две операции wait и signal, до некоторой степени похожие на операции P и V над семафорами.
Если функция монитора не может выполняться дальше, пока не наступит некоторое событие, она выполняет операцию wait над какой-либо условной переменной. При этом процесс, выполнивший операцию wait, блокируется, становится неактивным, и другой процесс получает возможность войти в монитор.
Когда ожидаемое событие происходит, другой процесс внутри функции-метода совершает операцию signal над той же самой условной переменной. Это приводит к пробуждению ранее заблокированного процесса, и он становится активным. Если несколько процессов дожидались операции signal для этой переменной, то активным становится только один из них. Что нам нужно предпринять для того, чтобы у нас не оказалось двух процессов, разбудившего и пробужденного, одновременно активных внутри монитора? Хор предложил, чтобы пробужденный процесс подавлял исполнение разбудившего процесса, пока он сам не покинет монитор. Несколько позже Хансен (Hansen) предложил другой механизм: разбудивший процесс покидает монитор немедленно после исполнения операции signal. Мы будем придерживаться подхода Хансена.
Давайте применим концепцию мониторов к решению задачи производитель-потребитель .
monitor ProducerConsumer {
condition full, empty; int count; void put() {
if(count == N) full.wait; put_item; count += 1; if(count == 1) empty.signal;
} void get() {
if (count == 0) empty.wait; get_item(); count -= 1; if(count == N-1) full.signal;
} {
count = 0;
}
}
Producer:
while(1) {
produce_item; ProducerConsumer.put();
}
Consumer:
while(1) {
ProducerConsumer.get(); consume_item;
}
Легко убедиться, что приведенный пример действительно решает поставленную задачу.
Реализация мониторов требует разработки специальных языков программирования и компиляторов для них. Мониторы встречаются в таких языках как параллельный Евклид, параллельный Паскаль, Java и т.д. Эмуляция мониторов с помощью системных вызовов для обычных широко используемых языков программирования не так проста, как эмуляция семафоров. Поэтому можно пользоваться еще одним механизмом со скрытыми взаимоисключеньями, механизмом, о котором мы уже упоминали, — передачей сообщений.