Аппаратная реализация синхронизации

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

Инструкция "проверить и установить"

В наборе инструкций процессора Motorola 68000 существует инструкция tas (test and set), которая имеет следующую реализацию:

int tas(int& target)

int temp;

temp =target;

target= 1;

returntemp;

}

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

int lock =0; // переменная, которая запирает вход в критическую

// секцию

void thread() {

while(true) {

while(tas(lock)); // ждать, пока замок закрыт
critical_section(); // критическая секция
lock =0; // открыть замок

non_critical_section(); // остальной код

}

}

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

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

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

Инструкция "обменять содержимое переменных"

В наборе инструкций процессоров семейства Intel x86 существует инструкция xchg (exchange), которая имеет следующую реализацию:

void xchg(register int r, int x) {

int temp;
temp = r;
r = x;
x = temp; }

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

int lock =0; // переменная, которая запирает вход в критическую

// секцию

void thread()

{

while(true)

{

register int key; // ключ к замку

key = 1;

while(key == 1) // ждать, пока замок закрыт

xchg(key, lock);

critical section(); // критическая секция
lock =0; // открыть замок

non_critical_section(); // остальной код

}

}

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

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

Во-первых, аппаратные алгоритмы синхронизации могут использоваться любым количеством параллельных потоков. Во-вторых, как программные, так аппаратные алгоритмы синхронизации имеют один существенный недостаток: впустую тратится процессорное время в циклах while, ждущих разрешения на вход в критическую секцию. Поэтому все эти алгоритмы получили общее на­звание алгоритмы, занимающиеся ожиданием (busy waiting algorithms), или алгоритмы активного ожидания.

Семафоры

Семафор или общий семафор (semaphore) - это целая переменная, значение которой можно опрашивать и менять только при помощи специальных неделимых (как команда testandset) операций P и V.

Двоичный семафор может принимать только значения 0 или 1.

Мьютекс (mutex, mutual exclusion semaphore) – семафор взаимного исключения. Основная задача – организация взаимного исключения для потоков из одного или разных процессов. Мьютекс является двоичным семафором.

P Proberen (гол) проверить (down)

V Verhogen (гол)увеличить (up)

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

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

P(S): S:= S-1;

If S< 0 then {ожидание к S}

V(S): if S<0 then {один процесс в готовые}

S:=S+1;

Будем предполагать, что очередь процессов, ожидающих на семафоре, обслуживается в соответствии с дисциплиной FIFO.

Приведем пример алгоритма обеспечения взаимоисключения при помощи семафора. Инициализацию семафора будем производить с помощью операции, условно обозначенной Инициализация_S(S,1), которая устанавливает для семафора начальное значение 1 или Иницилизация_S(S,0),

- соответственно, 0.

var S : семафор;

procedure процесс_Х;

begin

while (true) do

begin

{Предшествующая критическому участку

часть процесса_Х}

P(S);{если в семафоре 1, то S:=S-1, иначе ожидать}

{Критический участок процесса_Х}

V(S);{если процесс ожидает на S, то разрешить работу, иначе S:=S+1}

{Остальная часть процесса_Х}

end

end;

procedure процесс_Y;

begin

while (true) do

begin

{Предшествующая критическому участку

часть процесса_Y}

P(S); {вход взаимоисключения, процесс ожидает выполнения операции V(S) процессом_Х }

{Критический участок процесса_Y}

V(S); {выход взаимоисключения}

{Остальная часть процесса_Y}

end

end;

begin

Инициализация_S(S,1);

Parbegin

процесс_Х;

процесс_Y;

Parend

end.