Решаем проблему конкурентного доступа с помощью Lock-Free

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

Блокировка

Самое простое, на первый взгляд, решение. Мы разрешаем пользоваться системой бронирования лишь одному человеку единовременно. Второй пользователь в этом случае не сможет войти в систему до того момента, пока первый пользователь не обновит данные путём сохранения внесённых изменений. Всё бы ничего, но номеров много, причём каждый из них независим от других. А если у нас целая сеть отелей и большой штат сотрудников, которые находятся в разных точках гостиничного комплекса? Кому-нибудь вечно придётся ожидать доступа? Пожалуй, вариант априори неприемлем. Очередной пример сверхсуровой атомарности — монопольный доступ, когда бронирование осуществляет только администратор. Тут вообще без комментариев.

Подход Lock-Free

При его реализации можно сделать так, чтобы операции не мешали друг другу. Но чтобы всегда можно было понять, что что-то пошло не так. Лучший способ это реализовать — выполнить проверку наличия параллельных операций, например, с помощью счётчика изменений. Но вот тут-то и кроется подвох. Дело в том, что процесс проверки тоже неатомарен, ведь он состоит из двух действий: проверка, как таковая, плюс непосредственно внесение изменений. И между выполнением этих двух действий всегда может кто-то «вклиниться», что сведёт на нет наши усилия.

Compare and Swap

Наилучший вариант в нашем случае — Compare and Swap (CaS) — та самая операция, которая является краеугольным камнем Lock-Free алгоритмов. CaS — это операция замены значения элемента с проверкой его предыдущего значения. Если наше предположение о предыдущем значении верно (то есть никто не успел поменять значение элемента до нас), то замена происходит. Иначе — операция CaS выполнена не будет, и мы поймем, что что-то пошло не так — элемент имеет какое-то другое значение.

Здесь важно то, что проверка и замена представляют собой единое действие, то есть процесс является атомарным, а между проверкой и заменой никто вклиниться не сможет. В этом и заключается смысл Compare and Swap.

Ознакомиться с подробностями работы Lock-Free алгоритмов на примере рабочего кода вы сможете на наших занятиях по курсу «Разработчик С++». Ждём вас в ближайшей группе!