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

Рассмотрим методы взаимного исключения

Запрещение прерываний

Заключается в запрещении всех прерываний при входе процесса в критическую область.

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

Переменные блокировки

Вводится понятие переменной блокировки, т.е. если значение этой переменной равно, например 1, то ресурс занят другим процессом, и второй процесс переходит в режим ожидания (блокируется) до тех пор, пока переменная не примет значение 0.

метод блокирующих переменных

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

Строгое чередование

В этой модели, процессы могут выполняться строго по очереди, используя переменную.

Строгое чередование

Недостатки метода:

o Заблокированный процесс постоянно находится в цикле, проверяя, не изменилась ли переменная.

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

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

Примитивы взаимодействия процессов

Вводится понятия двух примитивов.

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

wakeup - системный запрос, в результате которого блокированный процесс будет запущен.

Применение примитивов

Основное преимущество - это отсутствие активного ожидания..

Проблема заключается в следующем, если спулер пуст, то wakeup срабатывает в пустую.

Проблема переполненного буфера (проблема производителя и потребителя)

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

Чтобы первый процесс не писал, когда буфер полный, а второй не считывал, когда он пуст, вводится переменная count для подсчета количества элементов в буфере.

Проблема переполненного буфера

В этой ситуации оба процесса могут попасть в состояние ожидания, если пропадет сигнал активации.

Алгоритм такой ситуации:

1. Процесс В, считал count=0 (заблокироваться он еще не успел)

2. Планировщик передал управление процессу А

3. Процесс А, выполнил все вплоть до wakeup, пытаясь разблокировать процесс В (но он не заблокирован, wakeup срабатывает впустую)

4. Планировщик передал управление процессу В

5. И он заблокировался, и больше сигнала на разблокировку не получит

6. Процесс А в конце концов заполнит буфер и заблокируется, но сигнала на разблокировку не получит.

Семафоры

Семафоры - переменные для подсчета сигналов запуска, сохраненных на будущее.

Были предложены две операции down и up (аналоги sleep и wakeup).

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

up увеличит значение семафора на 1 или разблокирует процесс находящийся в ожидании..

down уменьшает значение семафора на 1 или блокирует процесс, если семафор =0.

down и up выполняются как элементарное действие, т.е. процесс не может быть блокирован во время выполнения этих операций. Значит, у операционной системы должен быть запрет на все прерывания, и перевод процесса в режим ожидания.

Решение проблемы переполненного буфера с помощью семафора

Применим три семафора:

full - подсчет заполненных сегментов (в начале = 0)

empty - подсчет пустых сегментов (в начале = количеству сегментов)

mutex - для исключения одновременного доступа к буферу двух процессов. (в начале = 1)

Мьютекс упрощенная версия семафора, он управляет доступом к ресурсу. Показывает, блокирован или нет ресурс.

Решение проблемы переполненного буфера с помощью семафора

⇐ Предыдущая6789101112131415Следующая ⇒

Поделиться:

Популярное:

1. ВЗАИМНОЕ ВЛИЯНИЕ АТОМОВ В МОЛЕКУЛАХ БИООРГАНИЧЕСКИХ СОЕДИЕНИЙ. ЭЛЕКТРОННЫЕ ЭФФЕКТЫ ЗАМЕСТИТЕЛЕЙ. КИСЛОТНЫЕ И ОСНОВНЫЕ СВОЙСТВА БИООРГАНИЧЕСКИХ МОЛЕКУЛ
2. Взаимное расположение двух плоскостей.
3. Взаимное расположение собеседников
4. ДВОРНЯЖКА ИЛИ ИСКЛЮЧЕНИЕ ИЗ ПРАВИЛ
5. Из предложений 7–10 выпишите слово, в котором правописание суффикса не определяется общим правилом (является исключением).
6. Круг № 2: «Математические науки чужды движению, за исключением тех, которые относятся к астрономии»
7. Начало страхования в России. — Страховые общества. — Правила страхования от огня по уставам обществ. — Общество перестрахования. — Взаимное страхование. — Морское страхование. — Страхование жизни
8. Ничто, за исключением моих мыслей, мне не способно повредить.
9. Обработка частиц наполнителя специальными поверхностно-активными веществами, благодаря которым он вступает в химическую связь с полимерной матрицей.
10. По всем объектам ОС за исключением ОС, потребительские свойства которых с течением времени не изменяются, амортизация начисляется линейным способом.
11. Татары уничтожили и демократическую систему самоуправления в русских городах (вече, посадник, ополчение), за исключением Новгорода и Пскова.