Использование блокировки памяти при синхронизации параллельных процессов

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

Рассмотрим следующую модель двух взаимодействующих процессов.

Рис. 1. Модель взаимодействующих процессов

Пусть имеется два циклических процесса, в которых есть критические секции, т.е. каждый из процессов состоит из двух частей:

· некоторого критического интервала;

· оставшаяся часть кода, в которой нет работы с общими переменными.

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

Рассмотрим вариант решения взаимного исключения, использующий только блокировку памяти. Это известный алгоритм, предложенный математиком Деккером. Алгоритм Деккера основан на использовании 3-х переменных: перекл 1, перекл 2 и ОЧЕРЕДЬ. С каждым из процессов CS ₁ и CS ₂ будут связаны соответственно переменные перекл 1 и перекл2, по смыслу являющиеся переключателями, которые принимают значение true, когда соответствующий процесс находится в своем критическом интервале, и false – в противном случае. Переменная целого типа ОЧЕРЕДЬ указывает, чье сейчас право сделать попытку входа, при условии, что оба процесса хотят выполнить свои критические интервалы.

Если перекл 2= true и перекл1= false, то выполняется критический интервал для процесса CS ₂ независимо от значения переменной ОЧЕРЕДЬ. Аналогично для случая перекл 1= true и перекл 2= false. Если же оба процесса хотят выполнить свои критические интервалы, т.е. перекл 2= true и перекл 1= true, то выполняется критический интервал того процесса, на который указывало значение переменной ОЧЕРЕДЬ, независимо от скоростей развития процесса.

2. Синхронизация процессов посредством операции «ПРОВЕРКА И УСТАНОВКА»

Операция «ПРОВЕРКА И УСТАНОВКА» является, как и блокировка памяти, одним из аппаратных средств решения задачи критического интервала. Данная операция реализована во многих компьютерах. Так в IBM 360 эта команда называлась TS (test and set). Действие этой двухоперандной команды заключается в том, что процессор присваивает значение второго операнда первому, после чего второму операнду присваивается значение, равное единице. Эта команда является неделимой, то есть между ее началом и концом не могут выполняться никакие другие команды.

Чтобы использовать команду TS для решения проблемы критического интервала, свяжем с ней переменную CS ₁, которая будет общей для всех процессов, использующих некоторый критический ресурс. Данная переменная будет принимать единичное значение, если какой-либо из взаимодействующих процессов находится в своем критическом интервале. С каждым процессом связана своя локальная переменная local, которая принимает значение, равное единице, если данный процесс хочет войти в свой критический интервал. Операция TS будет присваивать значение common переменной local и устанавливать common в единицу.

Пусть значение common равно нулю. Предположим, что первым захочет войти в свой критический интервал процесс CS ₁. В этом случае значение local 1установится в единицу, а после цикла проверки с помощью команды TS (local 1, common) – в ноль. При этом значение common станет равным единице. Процесс CS ₁ войдет в свой критический интервал. После выполнения этого критического интервала common примет значение равное нулю, что даст возможность второму процессу CS ₂ войти в свой критический интервал.

В микропроцессорах i80386 и старше есть специальные команды BTC, BTS (bit test and reset – проверка бита и установка), BTR, которые как раз и являются вариантами реализации команды типа «ПРОВЕРКА И УСТАНОВКА».

Несмотря на то, что и алгоритм Деккера и операция «ПРОВЕРКА И УСТАНОВКА» пригодны для реализации взаимного исключения, оба эти приема очень неэффективны. Всякий раз, когда один из процессов выполняет свой критический интервал, любой другой процесс, который пытается войти в свою критическую секцию, попадает в цикл проверки соответствующих переменных-флагов, регламентирующих доступ к критическим переменным (находится в активном ожидании). В результате имеем общее замедление вычислительной системы процессами, которые реально не выполняют никакой полезной работы.

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

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

Таким образом, мы подошли к одному из главных механизмов решения проблемы взаимного исключения – семафорам Дейкстры.