Заранее предупреждаю, для тех кто в теме, интересного будет не очень много. :)
У меня появилась актуальная задача реализовать базовые примитивы синхронизации(мьютекс, семафор и read/write lock), используя только синхронную очередь — единственный доступный примитив. Заодно по пути я расскажу как устроены спинлоки и мы даже соберём маленького франкенштейна.
Инициализация:
queue.post(0);
Захват:
queue.get(); //будем спать, если очередь пуста.
Освобождение:
queue.post(0); //вернём событие на место.
Инициализация:
инициализируем семафор максимальным количеством клиентов.
Захват на чтение :
захватываем семафор (количество клиентов уменьшается на 1)
Освобождение на чтение: отпускаем семафор (количество клиентов увеличивается на 1)
Захват на запись:
захватываем мьютекс, и захватываем максимальное количество клиентов на семафоре (будем ждать пока все читающие потоки не освободят лок.) Мьютекс нужен чтобы сериализовать локи на запись между записывающими потоками, иначе один поток может захапать часть счётчика на семафоре, а другой другую часть. Дедлок. Отпускаем мьютекс после полного захвата семафора. (счётчик в семафоре 0)
Освобождение:
Захватываем мьютекс, освобождаем семафор(счётчик снова равен максимальному количеству читающих клиентов, освобождаем мьютекс.
На двух очередях можно реализовать аналогичную схему, но без указания максимального количества клиентов:
создаём две очереди: очередь на чтение (read_queue) и очередь на запись (write_queue). В обе очереди посылаем нули. Захват на запись выглядит очень просто(как мьютекс в самом начале): мы вместо захвата делаем write_queue.get() и освобождаем с write_queue.post(0). Захват на чтение выглядит немного сложнее: сначала мы читаем наш номер из очереди turn = read_queue.get(), потом смотрим — если turn == 0, то захватываем ещё и write — write_queue.get(). Если это не удаётся, это ничего, следующие читающие потоки заснут на read_queue.get() и рейса не будет. Теперь посылаем в read_queue (turn+1). read_queue.post(turn+1). Write lock не возвращаем обратно. При освобождении такого лока делаем следующее: turn = read_event.get() — 1; если turn == 0, то надо вернуть write lock на место. После этого делаем read_event.post(turn);
Интереснее всего конечно же FAA и CAS. Fetch-And-Add &mdash это такая инструкция процессора, которая атомарно инкрементирует значение переменной в памяти на какое-то произвольное число и возвращает предыдущее значение. CAS A,B,C атомарно сравнивает значение в памяти [A] с нужным значением B, и если всё верно, выставляет значение в памяти на число C. На x86 процессорах CAS представлен инструкцией cmpxchg8b.
Спинлок в данном случае очень простая и быстрая штука. Мы вместо того чтобы вызывать операционную систему и тратить драгоценные такты процессора можем устроить синхронизацию сами. Простейший спинлок даже не возвращает время в систему — можно просто вертеться в цикле пока нужное число не появится в памяти. Есть разные усовершенствования этого способа, но они находятся за пределами этой вводной статьи. :)
Реализация при помощи CAS:
Инициализация:
value = 1
Захват:
while(__compare_and_swap(&value, 1, 0) != 1) { /*ждём пока ячейка памяти не будет содержать 1, что значит что ресурс свободен, если 1, то атомарно пишем туда 0 */ }
Освобождение:
value = 1; /*просто пишем 1 в ячейку памяти*/
Чуть сложнее на FAA:
Надо вводить два числа: билет(ticket) и очередность(turn), изначально оба содержат 0.
Захват мьютекса:
my_turn = __fetch_and_add(&ticket, 1); //получаем номер своего хода.
while(turn != my_turn) { /* ждём своего хода */ }
Освобождение:
__fetch_and_add(&turn, 1); //увеличиваем ход, следующий клиент получает лок.
Остальные примитивы пытливый читатель может придумать сам и даже получить нобелевскую премию!
Захват семафора (wait):
old_value = __fetch_and_add(&value, -1);
если тут old_value больше 0, то мы радуемся жизни, и никаких функций операционной системы не вызываем, ресурсов нам хватило, всё хорошо, иначе надо сделать queue.get() и заснуть.
Освобождение семафора (post) должно увеличить счётчик на 1: old_value = __fetch_and_add(&value, 1);.
Если old_value тут меньше ноля — то значит кто-то спал на семафоре и его надо разбудить event.post(0);.
Вуаля! Мы получили экстремально лёгкий, простой семафор, оптимистически не использующий операционную систему. Мьютекс получается из семафора со значением 1, а rw-lock получается из семафора и мьютекса из п. 1.3, например.
Спасибо что дочитали до конца! :)
У меня появилась актуальная задача реализовать базовые примитивы синхронизации(мьютекс, семафор и read/write lock), используя только синхронную очередь — единственный доступный примитив. Заодно по пути я расскажу как устроены спинлоки и мы даже соберём маленького франкенштейна.
Часть 1: Всё — очереди
Синхронная очередь работает так: queue.get() возвращает первое событие из очереди (число), если его нет — усыпляет поток. queue.post(число) посылает событие и будит один из потоков ждущих событие в get().1.1 Мьютекс
Итак, для начала самая простая задачка — мьютекс. Как видно из названия, он(мьютекс) обеспечивает эксклюзивный доступ до ресурса. Ресурс в данном случае — просто единичное событие в очереди. То есть:Инициализация:
queue.post(0);
Захват:
queue.get(); //будем спать, если очередь пуста.
Освобождение:
queue.post(0); //вернём событие на место.
1.2 Семафор
Наивным образом эту схему можно расширить до семафора — надо просто ничего не класть в очередь в инициализации, увеличение счётчика семафора будет queue.post(0), уменьшение queue.get().1.3 RWLock
Теперь самое сложное — read write lock. Простейший вариант решения можно построить из семафора и мьютекса. Недостаток этого варианта — надо изначально зафиксировать максимальное количество одновременно читающих потоков. Как это исполняется технически? Очень просто:Инициализация:
инициализируем семафор максимальным количеством клиентов.
Захват на чтение :
захватываем семафор (количество клиентов уменьшается на 1)
Освобождение на чтение: отпускаем семафор (количество клиентов увеличивается на 1)
Захват на запись:
захватываем мьютекс, и захватываем максимальное количество клиентов на семафоре (будем ждать пока все читающие потоки не освободят лок.) Мьютекс нужен чтобы сериализовать локи на запись между записывающими потоками, иначе один поток может захапать часть счётчика на семафоре, а другой другую часть. Дедлок. Отпускаем мьютекс после полного захвата семафора. (счётчик в семафоре 0)
Освобождение:
Захватываем мьютекс, освобождаем семафор(счётчик снова равен максимальному количеству читающих клиентов, освобождаем мьютекс.
На двух очередях можно реализовать аналогичную схему, но без указания максимального количества клиентов:
создаём две очереди: очередь на чтение (read_queue) и очередь на запись (write_queue). В обе очереди посылаем нули. Захват на запись выглядит очень просто(как мьютекс в самом начале): мы вместо захвата делаем write_queue.get() и освобождаем с write_queue.post(0). Захват на чтение выглядит немного сложнее: сначала мы читаем наш номер из очереди turn = read_queue.get(), потом смотрим — если turn == 0, то захватываем ещё и write — write_queue.get(). Если это не удаётся, это ничего, следующие читающие потоки заснут на read_queue.get() и рейса не будет. Теперь посылаем в read_queue (turn+1). read_queue.post(turn+1). Write lock не возвращаем обратно. При освобождении такого лока делаем следующее: turn = read_event.get() — 1; если turn == 0, то надо вернуть write lock на место. После этого делаем read_event.post(turn);
Часть 2: Спинлоки
Спинлоки это прекрасный способ сделать в пространстве процесса большую часть работы по синхронизации. Это будет работать если процессоры и/или ваша платформа поддерживает некоторые примитивы сихронизации аппаратно. Обычно семантику таких инструкций объединяют в несколько групп: Fetch-And-Add(FAA), Compare-And-Swap(CAS). Есть и другие, но они более экзотические и я их трогать не буду.Интереснее всего конечно же FAA и CAS. Fetch-And-Add &mdash это такая инструкция процессора, которая атомарно инкрементирует значение переменной в памяти на какое-то произвольное число и возвращает предыдущее значение. CAS A,B,C атомарно сравнивает значение в памяти [A] с нужным значением B, и если всё верно, выставляет значение в памяти на число C. На x86 процессорах CAS представлен инструкцией cmpxchg8b.
Спинлок в данном случае очень простая и быстрая штука. Мы вместо того чтобы вызывать операционную систему и тратить драгоценные такты процессора можем устроить синхронизацию сами. Простейший спинлок даже не возвращает время в систему — можно просто вертеться в цикле пока нужное число не появится в памяти. Есть разные усовершенствования этого способа, но они находятся за пределами этой вводной статьи. :)
2.1 Мьютекс
Сейчас я на простейших примерах покажу реализацию мьютекса на этих примитивах:Реализация при помощи CAS:
Инициализация:
value = 1
Захват:
while(__compare_and_swap(&value, 1, 0) != 1) { /*ждём пока ячейка памяти не будет содержать 1, что значит что ресурс свободен, если 1, то атомарно пишем туда 0 */ }
Освобождение:
value = 1; /*просто пишем 1 в ячейку памяти*/
Чуть сложнее на FAA:
Надо вводить два числа: билет(ticket) и очередность(turn), изначально оба содержат 0.
Захват мьютекса:
my_turn = __fetch_and_add(&ticket, 1); //получаем номер своего хода.
while(turn != my_turn) { /* ждём своего хода */ }
Освобождение:
__fetch_and_add(&turn, 1); //увеличиваем ход, следующий клиент получает лок.
Остальные примитивы пытливый читатель может придумать сам и даже получить нобелевскую премию!
Часть 3: Я устал, хочу спать и когда это всё кончится? Оптимизм.
Теперь собираем наш семафор-франкенштейн. Если подумать, то свободные ресурсы совсем не обязательно представлять в виде реальных сообщений в очереди и тратить на это драгоценные ресурсы. Нам поможет fetch-and-add.Захват семафора (wait):
old_value = __fetch_and_add(&value, -1);
если тут old_value больше 0, то мы радуемся жизни, и никаких функций операционной системы не вызываем, ресурсов нам хватило, всё хорошо, иначе надо сделать queue.get() и заснуть.
Освобождение семафора (post) должно увеличить счётчик на 1: old_value = __fetch_and_add(&value, 1);.
Если old_value тут меньше ноля — то значит кто-то спал на семафоре и его надо разбудить event.post(0);.
Вуаля! Мы получили экстремально лёгкий, простой семафор, оптимистически не использующий операционную систему. Мьютекс получается из семафора со значением 1, а rw-lock получается из семафора и мьютекса из п. 1.3, например.
Спасибо что дочитали до конца! :)
