Методы решения проблем синхронизации

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

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

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

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

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

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

Семафоры Дейкстры.

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

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

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

Операция P(S) – проверка значения семафора, если 1, то переход к следующей за примитивом операции, иначе процесс снимается с выполнения и переводится в состояние пассивного ожидания.

Операция V(S) - увеличение значения семафора на 1 и перевод одного или несколких процессов в состояние готовности.