Учебный курс Операционные среды, системы и оболочки Лекция 7 Лекции читает доктор технических наук, профессор Назаров Станислав Викторович

Методы взаимоисключений 1.Запрещение прерываний при входе в критическую область и разрешение прерываний после выхода из критической области. Достоинства: простота реализации. Недостатки: монополизация процессора, возможный крах ОС при сбое процесса, невозможность использования в многопроцессорных системах. 2.Блокирующие переменные (программный подход) F(D)=1? Да, свободен Нет, занят Попытка доступа к разделяемому ресурсу D Занять ресурс F(D)=0 Критическая секция (работа с ресурсом D) Освободить ресурс F(D)=1 Неделимая операцияпроверка-установка Команды TC, BTR, BTS процессора Pentium (анализ и присвоение значения логической переменной) Недостатки: необходимость постоянного опроса другими потоками, требующими тот же ресурс, блокирующей переменной; дополнительные затраты процессорного времени.

3 3.Использование системных функций входа в критическую секцию Системный вызов EnterCriticalSection() Попытка доступа к разделяемому ресурсу D F(D )= 1? Нет Да Перевести данный поток в ожидание D Установить блокирующую переменную в состояниеЗанято, F(D) = 0 Критическая секция (работа с ресурсом D) Установить блокирующую переменную в состояниеСвободно, F(D) = 1 Перевести поток, ожидающий ресурс D, в состояние Готовность Системный вызов LeaveCriticalSection() Достоинство: исключается потеря времени процессора на циклическую проверку освобождения занятого ресурса. Недостаток: растут накладные расходы ОС на по реализации функции входа в критическую секцию и выхода из нее

4 4. Семафоры Дийкстры (Dijkstra) Семафор : переменная S, примитивы P (proberen – проверка; down) и V (verhogen – увеличение, up) V(S) – переменная S увеличивается на 1 единым действием. Выборка, наращивание и запоминание не могут быть прерваны. К переменной S нет доступа во время выполнения этой операции. P(S) – переменная S уменьшается на 1, если это возможно, составясь в области неотрицательных значений. Если S уменьшить невозможно, поток, выполняющий операцию P, ждет, пока это уменьшение станет возможным. Операция P неделима. В частном случае семафор S может принимать двоичные значения 0 и 1, превращаясь в блокирующую переменную (двоичный семафор). Операция P заключает в себе потенциальную возможность перехода процесса, который ее выполняет, в состояние ожидания (если S = 0). Операция V может при некоторых обстоятельствах активизировать процесс, приостановленный операцией P. Для хранения процессов, ожидающих семафоры, используется очередь, работающая по принципу FIFO.

5 f e N Начальные значения семафоров e = N; f = 0 P(e) Работа с разделяемым ресурсом (e=e-1) V(f) ( f=f+1) Потоки-писатели Потоки-читатели Буферный пул e > 0 P(f) f > 0 Работа с разделяемым ресурсом (f=f-1) V(e) (e=e+1) e – пустые буферы, f – занятые буферы

Взаимоблокировки (тупики) Условия возникновения взаимоблокировки (тупиковой) ситуации: 1.Взаимное исключение. Каждый ресурс в данный момент или отдан ровно одному процессу, или недоступен. 2.Условие удержания и ожидания. Процессы, в данный момент удерживающие полученные ранее ресурсы, могут запрашивать новые ресурсы. 3.Отсутствие принудительной выгрузки ресурсов. У процесса нельзя забрать принудительно ранее полученные ресурсы. 4.Условие циклического ожидания. Существует круговая последовательность из двух и более процессов, каждый из которых ждет доступа к ресурсу, удерживаемому следующим членом последовательности. Стратегии борьбы с взаимоблокировками: 1. Пренебрежение проблемой в целом. 2. Обнаружение и устранение взаимоблокировок (восстановление). 3. Недопущение тупиковых ситуаций с помощью аккуратного распределения ресурсов. 4. Предотвращать с помощью структурного опровержения одного из четырех условий, необходимых для взаимоблокировки

7 Методы обнаружения взаимоблокировок 1.В системе один ресурс каждого типа. Например, пусть система из семи процессов (A, B, C, D, E, F, G) и шести ресурсов (R, S, T, V, W, U) в некоторый момент соответствует следующему списку: Процесс A занимает ресурс R и хочет получить ресурс S. Процесс B ничего не использует, но хочет получить ресурс T. Процесс C ничего не использует, но хочет получить ресурс S. Процесс D занимает ресурс U и хочет получить ресурсы S и T. Процесс E занимает ресурс T и хочет получить ресурс V. Процесс F занимает ресурс W и хочет получить ресурс S. Процесс G занимает ресурс V и хочет получить ресурс U. ВОПРОС: Заблокирована ли эта система и если да, то какие процессы в этом участвуют? ОТВЕТ МОЖНО ПОЛУЧИТЬ, ПОСТРОИВ ГРАФ РЕСУРСОВ И ПРОЦЕССОВ.

8 цикл RA CS F D B TE U W G V Граф ресурсов и процессов

9 2. В системе несколько ресурсов каждого типа. P = {P 1, P 2,..., P n } – множество процессов, n – число процессов; E = {E 1, E 2,..., E m } – множество ресурсов, m – число типов ресурсов; A = {A 1, A 2,..., A m } – вектор свободных ресурсов; A J

10 Алгоритм обнаружения тупиков Основан на сравнении векторов ресурсов. В исходном состоянии все процессы не маркированы (не отмечены). По мере реализации алгоритма на процессы будет ставиться отметка, обозначающая, что они могут закончить свою работу, т. е. не находятся в тупике. После завершения алгоритма любой немаркированный процесс находится в тупиковой ситуации. Алгоритм 1.Ищется процесс P i, для которого i – я строка матрицы R меньше вектора A, т. е. R i

11 Методы устранения тупиков 1.Принудительная выгрузка ресурсов. Изъятие ресурса у процесса, передача его другому процессу, а затем возврат ресурса таким образом, что исходный процесс этого не замечает (сложно и чаще всего невозможно). 2.Восстановление через откат. Прцессы периодически создают контрольные точки, позволяющие запустить процесс с предыстории. При возникновении тупика процесс, занимающий необходимый ресурс откатывается к контрольной точке, после которой он получил ресурс. Если возобновленный процесс вновь попытается получить данный ресурс, он переводится в режим ожидания освобождения этого ресурса. 3.Восстановление путем уничтожения процессов. Недопущение тупиков путем безопасного распределения ресурсов. Подобные алгоритмы базируются на концепции безопасных состояний. Например, Дейкстрой был разработан алгоритм планирования, позволяющий избегать взаимоблокировок (алгоритм банкира).

Синхронизирующие объекты ОС Для синхронизации потоков, принадлежащих разным процессам, ОС должна предоставлять потокам системные объекты синхронизации. К таким объектам относятся события (event), мьютексы (mutex – mutual exclusion – взаимное исключение), системные семафоры и др. Объект-событие используется для того, чтобы оповестить потоки о том, что некоторые действия завершены. Мьютекс (простейший двоичный семафор) используется для управления доступом к данным. Семафоры используются для оповещения свершения последовательности событий. Для синхронизации используются также обычные объекты ОС: файлы, процессы, потоки Все объекты синхронизации могут находиться в сигнальном и несигнальном (свободном) состоянии. Поток с помощью системного вызова WAIT(X) может синхронизировать свое выполнение с объектом синхронизации X. С помощью системного вызова SET(X) поток может перевести объект X в сигнальное состояние. Кроме того, в ОС определен набор сигналов для логической связи меду процессами, а также процессами и пользователями (терминалами).

Аппаратно-программные средства поддержки мультипрограммирования Системы прерываний Классы прерываний: внешние, внутренние, программные 1. Внешние прерывания – результат действий пользователя, сигналы от периферийных устройств компьютера и управляемых объектов. 2. Внутренние прерывания – результат появления аварийных ситуаций при выполнении инструкции программы. 3. Программные прерывания – результат выполнения запланированных в программе особых инструкций (системный вызов). Принципы построения систем прерываний: аппаратная поддержка (контроллер прерываний, контроллер DMA, контроллеры внешних устройств, шины подключения внешних устройств, средства микропроцессора); векторный, опрашиваемый и комбинированный способы прерываний; приоритетный механизм обслуживания (с абсолютными и относительными приоритетами); маскирование прерываний; диспетчер прерываний и процедуры обслуживания прерываний.