Операционные системы. Лекция 5
Синхронизация параллельных процессов
1. Назначение синхронизации
2. Типичные задачи синхронизации
- задача взаимного исключения
- задача производители-потребители
- задача «читатели-писатели»
- задача кругового распределения ресурсов
3. Механизмы синхронизации
- аппаратная реализация взаимоисключений
1
Назначение синхронизации процессов
упорядочение развития процессов во
времени в зависимости от типа отношения
между процессами
(отношение предшествования, отношение
приоритетности,
отношение
взаимного
исключения)
взаимодействие
между
процессами,
выражающееся в передаче информации
между ними
(отношение
«производитель-потребитель»,
отношение «читатель-писатель»
2
Отношения между процессами, влияющие
на синхронизацию процессов
Отношение
предшествования
Для двух процессов это означает, что первый процесс
должен переходить в состояние выполнения всегда
раньше второго
Отношение
приоритетности
Процесс с приоритетом Р может быть переведен в
состояние выполнения только при соблюдении двух
условий:
в состоянии готовности к рассматриваемому
процессору нет процессов с большим приоритетом;
процессор либо свободен, либо используется
процессом с меньшим, чем Р приоритетом
Отношение взаимного
исключения
Устанавливается для процессов, использующих
общий ресурс. При этом совокупность действий над
этим ресурсом в составе одного процесса называют
критическим интервалом. Критический интервал
одного
процесса
не
должен
выполняться
одновременно с критическим интервалом над этим
же ресурсом в составе другого процесса
Отношение
«производительпотребитель»
Устанавливается для двух процессов с жестко
распределенными между ними функциями. Один
процесс вырабатывает сообщения, предназначенные
для восприятия и обработки другим.
Отношение «читателиписатели»
процессы-писатели могут записывать информацию в
область памяти
процессы-читатели считывают информацию из
3
области памяти
Задача взаимного исключения
Необходимо
согласовать
работу
параллельных
процессов при использовании критического ресурса,
чтобы удовлетворить следующим требованиям:
•Одновременно внутри критического интервала должно
находиться не более одного процесса
•Освобождение критического ресурса и выход из
критического интервала должно быть произведено за
конечное время
P1
t1
t2
t
R
t
t
3
4
P2
t
R – критический ресурс(воспроизводимый, последовательноиспользуемый)
t1 – t2 критический интервал процесса P1
t3 – t4 критический интервал процесса P2
4
Задача производители-потребители
Необходимо согласовать выполнение параллельных процессов при
обмене сообщениями таким образом, чтобы удовлетворить следующим
требованиям:
Выполнять требования задачи взаимного исключения по
отношению к критическому ресурсу – общей области памяти для
хранения сообщения
Учитывать состояние общей области памяти, характеризующее
возможность или невозможность посылки(принятия) очередного
сообщения
P1
t1
t2
t5
t
S
P2
S - потребляемый ресурс
t3
t4
t6
t
P1 – процесс-производитель
P2 – процесс-потребитель
5
Задача писатели-читатели
Необходимо согласовать работу процессов-писателей и
процессов читателей:
•Выполняя требования задачи взаимного исключения по
отношению к критическому ресурсу – общей области памяти
для хранения информации
•Учитывая приоритетность использования общей области
памяти различными типами процессов
P1
P2
t1
t4
t1
R
P3
P4
t4
t2
t2
t3
t
t
t
t
S – критический ресурс P1, P2 – процессы-писатели P3,P4 – процессы-читатели
6
Задача кругового распределения ресурсов
Необходимо
обеспечить
максимально
параллельное
и
правильное развитие процессов при круговом распределении
ресурсов, упорядочивая действия процессов по захвату
ресурсов во избежание возможных блокировок одними
процессами других и тупиковых ситуаций
P2
R1
P1
R2
P3
R3
P1, P2, P3 - параллельные процессы
R1,R2, R3 - последовательно-используемые ресурсы
Процессу P1 требуются ресурсы
Процессу P2 требуются ресурсы
Процессу P3 требуются ресурсы
R1,R3
R1,R2
R2,R3
7
Аппаратная реализация задачи взаимного
исключения
1)блокировка памяти.
ВС имеют основную форму аппаратной
реализации взаимного исключения- блокировка
памяти.
Блокировка памяти - запрет одновременного
исполнения двух и более команд, которые
обращаются к одной и той же ячейке памяти.
Если в этой ячейке хранится значение
критической переменной, то получить доступ к ней
может только один процесс.
8
Аппаратная реализация задачи взаимного
исключения
2)команда проверка и установка(test&set, TS).
Операция «ПРОВЕРКА И УСТАНОВКА» является, как и блокировка памяти,
одним из аппаратных средств решения задачи критического интервала.
Команда TS является аппаратно-поддерживаемой составной командой.
Команда TS является неделимой операцией, то есть между ее началом и концом
не могут выполняться никакие другие команды.
F(D) – блокирующая переменная ресурса D( 0- свободен, 1 – занят
Выполнение команды:
Перед входом в критический интервал процесс выполняет команду TS:
1. Циклически проверяется F(D)=0 (TEST)
2. Если F(D)=0 то F(D)=1 (SET)
3. Процесс входит в критическую секцию
4. После выполнения критической секции F(D)=0
Если все процессы выполняют вышеописанных соглашений, то взаимное
исключение гарантируется. При этом процессы могут быть прерваны операционной
системой в любой момент и в любом месте, в том числе в критическом интервале.
Нельзя прерывать процесс только между выполнением операций проверки и
установки блокирующей переменной.
(например, команды BТС, STR и BTS процессора Pentium),
9
Аппаратная реализация задачи взаимного
исключения
3)запрещение обработки прерываний.
t2
t1
P
t
R
t1 – блокирование обработки прерываний
t2 – деблокирование обработки
прерываний
2) использование переменной состояния.
P
t2
t1
t3
t4
t
S=0
S=1
R
t1 – t2 – вспомогательный критический интервал(блокирование
обработки прерываний и занятие переменной состояния)
t2 – t3 – основной критический интервал(прерывания разрешены)
t3 – t4 – вспомогательный критический интервал(блокирование
обработки прерываний и освобождение переменной состояния)
10
