Алгоритмы синхронизации

системах с распределенной памятью
Барьер

строго определенном состоянии
Синхронизация необходима для того, чтобы гарантировать непротиворечивость (консистентность

файла данные, записанные процессом 1 и работает с ними
Проблема
Чтобы процесс

a на 1 a=2
Поток1 : записывает a назад a=2
Поток2 : считываем

Поток1 : считываем a a=1
Поток2 : считываем a a=1
Поток1 : увеличивает a на 1 a=2
Поток2 : увеличивает a на 1 a=2
Поток 2: записывает a назад a=2
Поток1: записывает a назад a=2
Результат - неправильный

используемыми данными
Состояние конкуренции за ресурс (race condition) – ситуация в

к данным, которые могут привести к их разрушению выполнялись строго

не перекрываясь.
Две атомарные операции с одними и теми же данными

2
Поток 2
Удаляет элемент 2
Проблема
Если не принять соответствующих мер, то элемент

Элемент 1

Элемент 2

Элемент 3

Элемент new

к общим данным –> возможность конкуренции за ресурс
Очень часто

в ячейке памяти
Битовые операции
Для сложных операций необходимо использовать программные средства

(mandatory) – при обращении к ресурсу блокировка захватывается обязательно
Рекомендуемые

блокировку может удерживать только один поток (процесс)‏
После освобождения блокировку снова

связанный список

Поток 1
Захватить(lock)‏
Если захват успешный, то все остальные

lock – общая переменная
List - общий связанный список

Поток 2
Захватить(lock)‏
Если захват успешный, то все остальные будут ждать захвата
Удаление (list)‏
Освободить(lock)‏

участках необходимо использовать блокировки
Блокировать необходимо данные, а не код!
Блокировки

lock_b не может быть освобождена, процесс 2 застрял на lock_a


Общие

освобождаемую блокировку приведет к зависанию

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

состоянию конкуренции
Процесс
Захват()‏
…
Освобождение()‏
Освобождаем захваченную нами блокировку (ресурс свободен)‏
Освобождение()‏
Освобождаем захваченную кем-то другим

доступа к ресурсу
Самый быстрый тип блокировки
Используется, когда время выполнения критической

предыдущее значение из области памяти addr и устанавливает значение этой

static int lock_var=0;

void lock(int* var){
while(tas(var,1));
}

void unlock(int* var){
*var=0;
//или
//atomic_set(var,0);
}

переменных
Алгоритм Петерсона
Два процессора 0 и 1
me() – номер текущего

int flag[2]={0,0};
Int victim;

void lock(){
flag[me()]=1;
victim = me();
while(flag[!me()] && victim==me());
}

void unlock(){
flag[me()]=0;
}

отсутствие бесконечного ожидания

в критический раздел
Пусть для определенности процессор 0 записал значение переменной

тогда flag[1]=1 и victim=0
Такая ситуация может возникнуть только когда процессор

на захват блокировки назначается уникальная комбинация его номера и целочисленной

процессами одновременно
Когда за захват блокировки состязаются потоки – блокировка находится

проверок в состоянии конфликта
При увеличении количества потоков время выполнения может

может выполняться не сразу, а буферизироваться процессором
Компилятор может пытаться оптимизировать

той же переменной
Операции записи должны быть строго последовательными
При записи чтение

//доступ на запись
insert(list);
write_unlock(&lock);

//Общая переменная
rw_lock lock;
//общий связанный список
Llist list;
Поток 2

read_lock(&lock);
//параллельный //доступ

write_lock(){
while(1){
lock(l);
if(!writers && !readers) {
writers++;
unlock();
break;
}
unlock(l);
}
}

Void write_unlock(){
lock(l);
writers--;
unlock(l)
}

поток чтения захватывает блокировку
Все потоки чтения ею пользуются
1 поток записи

каждой операции записи значение счетчика увеличивается на 1
После окончания записи

seq;
seq = read_seqbegin(lock);
//считываем время

} while(read_seqretry(&lock,seq));

(c^ iv);
}

увеличения/уменьшения на 1
Если значение семафора становится меньшем нуля, то процесс,

на 1) – down()‏
Требование нулевого значение (есть не во всех

атомарного счетчика
Semaphore a(1);
Поток 1 Поток 2
Up(a); read(a);

защищается спин-блокировкой
Как только семафор становится меньшим нуля, процессы при захвате

}
}



//процесс из очереди
proc

Up() {
lock(l);
proc=queue.relese();
count++;
unlock();
start(proc);
}

– «тяжелая» операция, требующая много времени

о наступлении некоторого события
Пример – срабатывание будильника

сигнализирующие о событиях

e.signal();
// все ожидающие потоки возвращаются к выполнению

в отличие от всех предыдущих способов
Counter{
int c;
semaphore s;
public:
int

выполнены всеми потоками, процессами
Операции до барьера
Чтение 1
Запись 2
Запись 3
Чтение 3
Операции

Барьер – выполняем
все предыдущие операции

Операции после барьера

нет необходимости
Иногда необходимо гарантировать, что все процессы программы выполняют

данных от всех остальных процессов