Взаимное исключение с активным ожиданием

Межпроцессное взаимодействие в ОС. Состояние состязания процессов. Понятие критической области. Понятие взаимного исключения. Способы избегания попадания процессов в критическую область. Основные примитивы межпроцессного взаимодействия

Понятия процессов и потоков в ОС ЭВМ. Многозадачность. Создание и завершение процессов. Состояния процесса. Понятие прерывания и его необходимость для поддержания многопоточности. Отличия между процессом и потоком. Способы реализации потоков

Классическая архитектура ОС ЭВМ. Ядро и вспомогательные модули ОС. Пользовательский и привилегированный режимы. Понятие системного вызова. Микроядерная архитектура ОС. Реализация системного вызова в микроядерной архитектуре. Достоинства и недостатки микроядерной архитектуры

Большинство современных ОС – хорошо структурированные модульные системы, способные к развитию, расширению и переносу на новые платформы. Единой архитектуры ОС не существует, но есть универсальные подходы к структурированию ОС

Наиболее общий подход к структуризации ОС – разделение ее модулей на две группы:

- модули, выполняющие основные функции ОС (ядро)

- модули, выполняющие вспомогательные функции ОС

Модули ядра управляют процессами, памятью, УВВ. Ядро – сердцевина ОС, без него она неработоспособна

Ядро решает внутрисистемные задачи организации вычислительного процесса, недоступные для приложений – переключение контекстов, загрузка/выгрузка страниц, обработка прерываний. Другой класс функций ядра создает для приложений прикладную программную среду. Приложения обращаются к ядру с запросами – системными вызовами – для выполнения различных действий (открытие и чтение файла, вывод графической информации на дисплей, получение системного времени)

Интерфейс прикладного программирования (API, Application Programming Interface) – функции ядра ОС, которые могут вызываться приложениями

Функции модулей ядра – наиболее часто используемые функции ОС, поэтому скорость их выполнения определяет производительность системы в целом. Для обеспечения высокой скорости работы ОС все модули ядра или большая их часть постоянно находятся в ОП, то есть являются резидентными

Некоторые компоненты ОС оформлены как обычные приложения – в виде исполняемых модулей стандартного для данной ОС формата, поэтому сложно провести грань между ОС и такими приложениями:

Вспомогательные модули ОС:

- утилиты – программы, решающие отдельные задачи управления и сопровождения компьютерной системы

- системные обрабатывающие программы – текстовые и графические редакторы, компиляторы, компоновщики, отладчики

- программы предоставления дополнительных услуг – специальный вариант пользовательского интерфейса, калькулятор, игры

- библиотеки процедур упрощают разработку приложений (математические функции, функции ввода-вывода)

Для надежного управления выполнением приложений ОС имеет по отношению к приложениям определенные привилегии, иначе некорректно работающее приложение может вмешаться в работу ОС и, например, разрушить часть ее кодов. Обеспечить привилегии ОС невозможно без специальных средств аппаратной поддержки. Аппаратура компьютера должна поддерживать минимум два режима работы – пользовательский (user mode) и привилегированный – режим ядра (kernelmode)

Архитектура ОС с ядром в привилегированном режиме:

Приложения подчинены за счет запрета выполнения в пользовательском режиме критичных команд, связанных с переключением процессора с задачи на задачу, управлением УВВ, доступом к механизмам распределения и защиты памяти

Между количеством уровней привилегий, реализуемых аппаратно, и количеством уровней привилегий, поддерживаемых ОС, нет прямого соответствия. Например, на базе четырех уровней, обеспечиваемых процессорами Intel, ОС OS/2 строит трехуровневую систему привилегий, а Windows NT, UNIX и некоторые другие ОС ограничиваются двухуровневой системой. На основе двух режимов привилегий процессора ОС может построить сложную и гибкую систему индивидуальной защиты ресурсов, пример которой – типичная система защиты файлов и каталогов (позволяет задать для любого пользователя права доступа к каждому из файлов и каталогов)

Повышение устойчивости ОС, обеспечиваемое переходом ядра в привилегированный режим, достигается за счет некоторого замедления выполнения системных вызовов. Системный вызов привилегированного ядра инициирует переключение процессора из пользовательского режима в привилегированный, а при возврате к приложению – обратное переключение. Во всех типах процессоров из-за дополнительной двукратной задержки переключения переход на процедуру со сменой режима выполняется медленнее, чем вызов процедуры без смены режима

Смена режимов при выполнении системного вызова к привилегированному ядру:

ВС, работающую под управлением ОС на основе ядра, можно рассматривать как систему, состоящую из трех иерархически расположенных слоев: нижний – аппаратура, промежуточный – ядро, верхний – утилиты, обрабатывающие программы и приложения

Трехслойная схема ВС:

Каждый слой обслуживает вышележащий слой, выполняя для него некоторый набор функций, которые образуют межслойный интерфейс

Поскольку ядро представляет собой сложный многофункциональный комплекс, многослойный подход обычно распространяется и на структуру ядра

Ядро может состоять из следующих слоев:

- средства аппаратной поддержки ОС. ОС представляет собой комплекс программ, но часть ее функций может выполняться и аппаратными средствами. К ОС относят, естественно, не все аппаратные устройства компьютера, а только средства аппаратной поддержки ОС, то есть те, которые прямо участвуют в организации вычислительных процессов: средства поддержки привилегированного режима, система прерываний, средства переключения контекстов процессов, средства защиты областей памяти

- машинно-зависимые компоненты ОС – модули, в которых отражается специфика аппаратной платформы компьютера; в идеале этот слой полностью экранирует вышележащие слои ядра от особенностей аппаратуры

- базовые механизмы ядра – программное переключение контекстов процессов, диспетчеризация прерываний, перемещение страниц из памяти на диск и обратно

- менеджеры ресурсов (процессов, ввода-вывода, ФС, ОП)

- интерфейс системных вызовов – верхний слой ядра, взаимодействующий непосредственно с приложениями и системными утилитами, образуя прикладной программный интерфейс ОС. Функции API, обслуживающие системные вызовы, предоставляют доступ к ресурсам системы в удобной и компактной форме, без указания деталей их физического расположения

Приведенное разбиение ядра ОС на слои условное, в реальной системе количество слоев и распределение функций между ними может быть иным

Архитектура ОС, основанная на привилегированном ядре и приложениях пользовательского режима, стала, по существу, классической. Ее используют многие популярные ОС, в том числе многочисленные версии UNIX, IBM OS/390, OS/2 и с определенными модификациями – Windows NT

Микроядерная архитектура – альтернатива классическому способу построения ОС. В привилегированном режиме работает только очень небольшая часть ОС – микроядро, защищенное от остальных частей ОС и приложений. В состав микроядра обычно входят машинно-зависимые модули, а также модули, выполняющие базовые (но не все) функции ядра по управлению процессами, обработке прерываний, управлению виртуальной памятью, пересылке сообщений и управлению УВВ, связанные с загрузкой или чтением регистров устройств. Набор функций микроядра обычно соответствует функциям слоя базовых механизмов обычного ядра. Такие функции ОС невозможно выполнить в пространстве пользователя

Перенос основного объема функций ядра в пользовательское пространство:

Все остальные более высокоуровневые функции ядра оформляются в виде приложений, работающих в пользовательском режиме. Однозначного решения о том, какие из системных функций нужно оставить в привилегированном режиме, а какие перенести в пользовательский, не существует. В общем случае многие менеджеры ресурсов, являющиеся неотъемлемыми частями обычного ядра – ФС, подсистемы управления виртуальной памятью и процессами, менеджер безопасности – становятся «периферийными» модулями, работающими в пользовательском режиме

Серверы ОС – менеджеры ресурсов, вынесенные в пользовательский режим – модули, обслуживание запросы локальных приложений и других модулей ОС. Для реализации микроядерной архитектуры необходимо наличие в ОС удобного и эффективного способа вызова процедур одного процесса из другого. Поддержка такого механизма – одна из главных задач микроядра

Реализация системного вызова в микроядерной архитектуре:

Клиент (прикладная программа или другой компонент ОС) запрашивает выполнение некоторой функции у соответствующего сервера, посылая ему сообщение. Непосредственная передача сообщений между приложениями невозможна, так как их адресные пространства изолированы друг от друга. Микроядро в привилегированном режиме имеет доступ к адресным пространствам каждого из этих приложений и может быть посредником – передает серверу сообщение, содержащее имя и параметры вызываемой процедуры, сервер выполняет операцию, ядро возвращает результаты клиенту. Работа микроядерной ОС соответствует известной модели клиент-сервер, в которой роль транспортных средств выполняет микроядро

Достоинства микроядерной архитектуры:

- переносимость: весь машинно-зависимый код изолирован в микроядре, поэтому для переноса системы на новый процессор требуется меньше изменений

- расширяемость

- конфигурируемость: достаточно изменить файл с настройками начальной конфигурации системы или остановить не нужные больше серверы в ходе работы обычными для остановки приложений средствами

- надежность: каждый сервер выполняется в виде отдельного процесса в своей собственной области памяти, то есть защищен от других серверов ОС (в традиционной ОС модули ядра могут влиять друг на друга)

- подходит для распределенных вычислений: использует механизмы, аналогичные сетевым – взаимодействие клиентов и серверов путем обмена сообщениями

Недостаток микроядерной архитектуры – меньшая производительность: при классической организации ОС выполнение системного вызова сопровождается двумя переключениями режимов, при микроядерной – четырьмя:

Именно по этой причине микроядерный подход не получил такого широкого распространения, которое ему предрекали. Пример микроядерной ОС – VM/370 (используется в мейнфреймах)

Сейчас не существует ОС с чисто классической или микроядерной архитектурой. ОС образуют некоторый спектр, на одном краю которого – системы с минимально возможным микроядром, на другом – системы, в которых микроядро выполняет достаточно большой объем функций

В многозадачной системе процессор переключается между программами, предоставляя каждой от десятков до сотен миллисекунд. В каждый конкретный момент времени процессор работает только с одной программой, создавая псевдопараллелизм – иллюзию параллельной работы. Настоящая параллельная работа присутствует в многопроцессорных и многоядерных системах. Следить за работой параллельно идущих процессов трудно, поэтому разработчики ОС создали концептуальную модель последовательных процессов, в которой все ПО организовано в виде набора последовательных процессов. С позиции модели у каждого процесса есть собственный виртуальный ЦП

Схема компьютера, работающего с 4 программами в многозадачном режиме, и модель 4 независимых последовательных процессов (каждый со своим логическим счетчиком команд):

На самом деле физический счетчик команд один, он загружается и сохраняется при переключении процессов

В каждый момент времени активна только одна программа:

Состояние всех 4 процессов изменилось за достаточно большой промежуток времени

Поскольку процессор переключается между программами, скорость, с которой производятся вычисления, непостоянна, и, возможно, даже будет отличной при каждом новом запуске программы

Основные события, приводящие к созданию процессов: инициализация системы, системный запрос на создание процесса, запрос пользователя на создание процесса, инициирование пакетного задания

Действия, приводящие к завершению процесса: обычный выход (преднамеренно), выход по ошибке (преднамеренно), выход по неисправимой ошибке (непреднамеренно), уничтожение другим процессом (непреднамеренно)

Основное отличие структуры процессов в Windows и UNIX – связь между родительским и дочерним процессами. В UNIX существует иерархия процессов, в Windows все процессы равноправны. В Windows возможна ситуация, при которой родительский процесс получает дескриптор, позволяющий контролировать дочерний процесс, но маркер можно передать другому процессу, нарушая иерархию

Возможные состояния процесса:

- действие (использует процессор в данный момент)

- готовность (приостановлен, чтобы позволить выполняться другому процессу)

- блокировка (не может быть запущен прежде, чем произойдет некое внешнее событие)

Переходы между состояниями:

1: процесс блокируется, ожидая входных данных

2: планировщик (часть ОС) выбирает другой процесс

3: планировщик выбирает этот процесс

4: доступны входные данные

Для реализации модели процессов ОС содержит таблицу с одним элементом для каждого процесса. Элемент таблицы содержит информацию о состоянии процесса, счетчике команд, указателе стека, распределении памяти, состоянии открытых файлов, об использовании и распределении ресурсов, всю остальную информацию, которую необходимо сохранять при переключении в состояние готовности или блокировки для последующего запуска – как если бы процесс не останавливался

Большое значение для создания иллюзии многопоточности на компьютерах с одним процессором имеет значение понятия прерывания. Прерывание (interrupt) – сигнал, сообщающий процессору о совершении какого-либо асинхронного события. Выполнение текущей последовательности команд приостанавливается, управление передается обработчику прерывания, который выполняет работу по обработке события и возвращает управление в прерванный код

Вектор прерывания – область памяти, содержащая адрес процедуры обработки прерывания

Приложение – статический набор команд

Процесс – объект, которому принадлежат ресурсы приложения

Компоненты процесса в Windows:

- структура данных, содержащая всю информацию о процессе

- адресное пространство – диапазон адресов виртуальной памяти, которым может пользоваться процесс

- исполняемая программа и данные, проецируемые на виртуальное адресное пространство процесса

Поток, или нить, – независимый путь выполнения внутри процесса, разделяющий вместе с процессом общее адресное пространство, код и глобальные данные. У каждого потока имеются собственные регистры, стек и механизмы ввода, в том числе очередь скрытых сообщений. В одном процессе может быть несколько потоков (многопоточность).

В отличие от различных процессов, которые могут быть инициированы различными пользователями и преследовать несовместимые цели, один процесс всегда запущен одним пользователем, и потоки созданы таким образом, чтобы работать совместно, не мешая друг другу

Элементы процесса, общие для потоков: адресное пространство, глобальные переменные, открытые файлы, дочерние процессы, необработанные аварийные сигналы, сигналы и их обработчики, информация об использовании ресурсов

Индивидуальные элементы потока: счетчик команд, регистры, стек, состояние

Стек – структура данных с методом доступа к элементам LIFO

В качестве примера использования нескольких потоков в одном процессе можно привести ситуацию, когда приложению нужно записать большой файл на диск. При использовании одного потока доступ к другим функциям программы будет недоступен до окончания операции

Преимущества использования нескольких потоков перед несколькими процессами:

- возможность совместного использования параллельными объектами адресного пространства и всех содержащихся в нем данных

- создание и уничтожение потоков происходит в примерно в 100 раз быстрее, чем для процессов

- увеличивается производительность

Поток может находиться в одном из нескольких состояний; переходы между состояниями такие же, как у процессов

Основные способы реализации пакета потоков: в пространстве пользователя и в ядре:

В первом случае ядро ничего не знает о потоках и управляет обычными однопоточными процессами. «+»: это можно реализовать в ОС, не поддерживающей потоки (раньше так строились все ОС); относительно высокая производительность; возможность использовать процессом собственный алгоритм планирования. «–»: проблема добровольной отдачи процессора одним из потоков, или блокирование одного потока, что приводит к блокированию всего процесса. В большинстве известных ОС сегодня потоки реализуются в ядре или используется сочетание двух способов

Проблема межпроцессного взаимодействия разбивается на 3 пункта: передача информации от одного процесса другому, контроль над деятельностью процессов (например, гарантия, что два процесса не пересекутся в критических ситуациях), согласование действий процессов. Эти же проблемы, кроме первой, относятся к потокам

Состояние состязания: два или более процесса считывают и записывают данные одновременно, и конечный результат зависит от того, какой из них был первым. Для предотвращения такого состояния и любой другой ситуации, связанной с совместным использованием ресурсов, используется взаимное исключение – запрет одновременной записи и чтения разделенных данных более чем одним процессом

Критическая область, или секция, – часть программы, в которой есть обращение к совместно используемым данным

Для правильной совместной работы параллельных процессов и эффективного использования общих данных необходимо выполнение следующих условий:

- процессы не должны одновременно находиться в критических областях

- в программе не должно быть предположений о скорости и количестве процессоров

- процесс, находящийся вне критической области, не может блокировать другие процессы

- невозможна ситуация, в которой процесс постоянно ждет попадания в критическую область

Взаимное исключение с использованием критических областей:

Процесс А попадает в критическую область в момент времени T₁. В момент времени T₂ процесс Б пытается попасть в критическую область, но ему это не удается, поскольку в критической области уже находится процесс А, а два процесса не должны одновременно находиться в критических областях. Поэтому процесс Б приостанавливается до наступления момента времени T₃, когда процесс А выходит из критической области. В момент времени4 процесс Б также покидает критическую область, и происходит возвращение в исходное состояние, когда ни одного процесса в критической области не было

Способы реализации взаимного исключения с целью избежать вмешательства в критическую область одного процесса при нахождении там другого и связанных с этим проблем:

- запрещение прерывания – самое простое решение. Запрещение всех прерываний при входе процессоров в критическую область и разрешение прерываний по выходе из области. Это решение нецелесообразно. Если все прерывания отключились и возник какой-то сбой, ОС закончит свое существование. Если система многопроцессорная, второй процессор все равно может зайти в критическую область

- переменные блокировки. Программное решение проблемы. Пусть переменная блокировки равна 0, процесс, когда хочет попасть в критическую область изменяет ее на 1 и входит в критическую область. Тут также может возникнуть состояние состязания, когда два процесса одновременно считывают переменную блокировки, когда она равна 0 и оба входят в критическую область

- строгое чередование. Переменная отслеживает, чья очередь входить в критическую область. Постоянная проверка значения переменной в ожидании некоторого значения называется активным ожиданием, которое используется только при уверенности в небольшом времени ожидания. «–»: если один процесс существенно медленнее другого, то может возникнуть ситуация, когда оба процесса находятся вне критической области, однако один процесс блокирован, ожидая, пока другой войдет в критическую область. Это нарушает третье условие из вышеперечисленных

- алгоритм Петерсона:

#define FALSE 0

#define TRUE 1

#define N 2 //количество процессов

int turn; //чья сейчас очередь

int interested[N]; //все переменные изначально равны 0

void enter_region(int process) //процесс 0 или 1

{

int other; //номер второго процесса

other=1-process; //противоположный процесс

interested[process]=TRUE; //индикатор интереса

turn=process; //установка флага

while (turn==process && interested[other]==TRUE);

}

void leav_region(int process)

{

interested[process]=FALSE; //индикатор выхода из критической области

}

Перед входом в критическую область процесс вызывает процедуру enter_region со своим номером в качестве параметра. После выхода из критической области процесс вызывает leav_region. Исходно оба процесса находятся вне критических областей. Процесс 0 вызывает enter_region, задает элементы массива и устанавливает переменную turn равной 0. Поскольку процесс 1 не заинтересован в попадании в критическую область, процедура возвращается. Теперь, если процесс 1 вызовет enter_region, ему придется подождать, пока interested[0] примет значение FALSE, а это произойдет только в тот момент, когда процесс 0 вызовет процедуру leave_region, чтобы покинуть критическую область. Если оба процесса вызвали enter_region практически одновременно, то оба сохранят свои номера в turn. Сохранится номер того процесса, который был вторым, а предыдущий номер будет утерян. Предположим, что вторым был процесс 1, так что значение turn равно 1. Когда оба процесса дойдут до оператора while, процесс 0 войдет в критическую область, а процесс 1 останется в цикле и будет ждать, пока процесс 0 выйдет из критической области

- команда TSL (Test and Set Lock – проверить и заблокировать). Это решение требует участия аппаратного обеспечения. Многие компьютеры имеют команду: TSL RX, LOCK. В регистр RX считывается содержимое слова памяти LOCK, в ячейке памяти LOCK сохраняется некоторое ненулевое значение. Операция считывания слова неделима. Процессор, выполняющий команду TSL, блокирует шину памяти, чтобы остальные процессоры, если они есть, не могли обратиться к памяти

Дата добавления: 2014-01-05