Синхронизация¶

Презентация¶

Синхронизация процессов¶

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

Семафоры¶

Семафоры являются одной из первых концепций синхронизации процессов. Они придуманы в 1965–м году Эдсгером Вайбом Дейкстрой.

Семафор представляет из себя целую неотрицательную переменную, доступ процессов к которой (за исключением момента инициализации) осуществляется с помощью двух атомарных операций: P (от датского слова proberen — проверять) и V (от verhogen – увеличивать).

P(S):   пока S == 0 процесс блокируется; 
        S = S – 1; 
V(S):   S = S + 1;

Мониторы¶

Мониторы были придуманы Хоаром (C. A. R. Hoare) как более безопасный примитив синхронизации. Они проще в использовании, так как не требуют столь высокого внимания, как семафоры.

Монитор представляет собой объект, содержащий один или несколько методов. Примечательной особенностью является то, что в один конкретный момент времени только одна нить может находиться в мониторе, то есть исполнять один из его методов. Ещё одним важным свойством является то, что нити могут на время лишаться эксклюзивного доступа в ожидании некоего события (это реализуется с помощью условных переменных — conditional variables).

Некоторые языки (например, Java) имеют встроенные реализации мониторов. Впрочем, их несложно реализовать и самим, используя, например, библиотеку POSIX Threads (pthread) с её эксклюзивными замќами (mutal lock, mutex — тип pthread_mutex_t) и условными переменными (тип pthread_cond_t).

Передача сообщений¶

Передача сообщений является интуитивно понятным методом синхронизации процессов, объединяющем в себе и синхронизацию, и межпроцессное взаимодействие — IPC (InterProcess Communication). Он базируется на понятии очереди сообщений и двух методах — send(), позволяющем отсылать сообщения, и receive(), позволяющем их принимать. В стандарте POSIX существует собственный интерфейс для работы с очередями, рассматриваемый, например, в mq_overview(7)

STM¶

STM является самым высокоуровнёвым и современным методом синхронизации. Идея впервые появилась в 1986 и окончательно трансформировалась в современный STM в 1995–м.

Суть метода транзакций заключается в том, что изменения данных не станут видны другим нитям до тех пор, пока не будет выполнен коммит (commit). После коммита система пытается применить сделанные изменения к общему участку памяти. Если сделать это не удаётся (например, если кто–то другой тоже сделал коммит), производится откат до начального состояния и повторная попытка (retry).

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

Аппаратные инструкции для синхронизации (Rad-Modify-Write)¶

Уровень консенсуса:
∞ — memory-to-memory move and swap, augmented queue, compare-and-swap, fetch-and-cons, sticky byte, Load-Link/Store-Conditional¹
2n-2 — n-register assignment
2 — test-and-set, swap, fetch-and-add, queue, stack
1 — atomic read and atomic write

Невозможно реализовать операцию, которая имеет больше участников, чем уровень консенсуса атомарной инструкции.

TSL (test-and-set lock)

Запись в память и возврат предыдущего значения по этому адресу.

#define LOCKED 1
int TestAndSet(int* lockPtr) {
    int initial = *lock;
    *lock = LOCKED;
    return initial;
}

volatile int lock = 0;

void Critical() {
    while (TestAndSet(&lock) == 1) /* busy waiting */;
    /* critical section */
    lock = 0; //release lock when finished with the critical section
}

CAS (compare-and-swap)

Запись в память, при условии, что значение в ней совпадает с заданным.

int compare_and_swap (int* register, int oldval, int newval) { 
    int old_reg_val = *register;
    if (old_reg_val == oldval) *register = newval;
    return old_reg_val;
}

void acquire_mutex(int *mutex) {
    while (cas(mutex, 1, 0)) /* busy waiting */;
}

void release_mutex(int *mutex) {
    *mutex =  1;
}

В x86 архитекуре — инструкция CMPXCHG.

LL/SC (load-link/store-conditional)

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

Особенность: проблематичная реализация.

Литература¶

• http://mailinator.blogspot.com/2009/06/beautiful-race-condition.html