Системное программное обеспечение Лекция 5 Алгоритмы синхронизации

Interleaving 2

Пример interleaving 3

Детерминированность активностей 4

Наборы переменных 5

Условия Бернстайна 6

Взаимодействовать процессам или нет 7

Критическая секция 8

9 ВремяСтудент 1Студент 2Студент Приходит в комнату 17-07Обнаруживает, что хлеба нет 17-09Уходит в магазин Приходит в комнату Обнаруживает, что хлеба нет Уходит в магазин Приходит в комнату Обнаруживает, что хлеба нет Уходит в магазин 17-23Приходит в магазин 17-25Покупает 2 батона на всех 17-27Уходит из магазина Приходит в магазин Покупает 2 батона на всех Уходит из магазина Приходит в магазин Покупает 2 батона на всех Уходит из магазина 17-41Возвращается в комнату Возвращается в комнату Возвращается в комнату

Исключение race condition 10 ВремяСтудент 1Студент 2Студент Приходит в комнату 17-07Достает два батона хлеба Приходит в комнату Приходит в комнату

Структура процесса с race condition 11

Алгоритмы организации взаимодействия процессов 12

Требования, предъявляемые к алгоритмам 13

Запрет прерываний 14

Переменная-замок 15

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

Флаги готовности 17

Алгоритм Петерсона 18

Алгоритм булочной 19

Аппаратная поддержка взаимоисключений 20

Команда Test-and-Set 21

Test-and-Set на уровне CPU 22

Команда Swap 23

Заключение 24