Цель состоит в том, чтобы реализовать генератор порядкового номера в современном C ++.Контекст находится в параллельной среде.
Требование № 1 Класс должен быть одноэлементным (общим для всех потоков)
Требование № 2 Theдля чисел используется 64-разрядное целое число.
Требование № 3 Вызывающий абонент может запросить более одного числа
Требование № 4 ЭтоКласс будет кэшировать последовательность чисел, прежде чем сможет обслуживать звонки.Поскольку он кэширует последовательность, он также должен хранить верхнюю границу -> максимальное число, которое можно вернуть.
Требование № 5 Последнее, но не менее важное, при запуске (конструктор) икогда нет доступных чисел для предоставления (n_requested> n_avalaible), класс синглтона должен запросить базу данных, чтобы получить новую последовательность.Эта загрузка из БД обновляет и seq_n_, и max_seq_n _.
Краткий черновик его интерфейса выглядит следующим образом:
class singleton_sequence_manager {
public:
static singleton_sequence_manager& instance() {
static singleton_sequence_manager s;
return s;
}
std::vector<int64_t> get_sequence(int64_t n_requested);
private:
singleton_sequence_manager(); //Constructor
void get_new_db_sequence(); //Gets a new sequence from DB
int64_t seq_n_;
int64_t max_seq_n_;
}
Пример только для пояснения варианта использования.Предположим, что при запуске DB устанавливает seq_n_ на 1000, а max_seq_n_ на 1050:
get_sequence.(20); //Gets [1000, 1019]
get_sequence.(20); //Gets [1020, 1039]
get_sequence.(5); //Gets [1040, 1044]
get_sequence.(10); //In order to serve this call, a new sequence must be load from DB
Очевидно, что реализация с использованием блокировок и std :: mutex довольно проста.
Что меня интересуетреализует версию без блокировки, используя std :: atomic и атомарные операции.
Моя первая попытка следующая:
int64_t seq_n_;
int64_t max_seq_n_;
были изменены на:
std::atomic<int64_t> seq_n_;
std::atomic<int64_t> max_seq_n_;
Получить новую последовательность из БД просто устанавливает новые значения в атомарных переменных:
void singleton_sequence_manager::get_new_db_sequence() {
//Sync call is made to DB
//Let's just ignore unhappy paths for simplicity
seq_n_.store( start_of_seq_got_from_db );
max_seq_n_.store( end_of_seq_got_from_db );
//At this point, the class can start returning numbers in [seq_n_ : max_seq_n_]
}
А теперь функция get_sequence, использующая метод атомарного сравнения и обмена:
std::vector<int64_t> singleton_sequence_manager::get_sequence(int64_t n_requested) {
bool succeeded{false};
int64_t current_seq{};
int64_t next_seq{};
do {
current_seq = seq_n_.load();
do {
next_seq = current_seq + n_requested + 1;
}
while( !seq_n_.compare_exchange_weak( current_seq, next_seq ) );
//After the CAS, the caller gets the sequence [current_seq:next_seq-1]
//Check if sequence is in the cached bound.
if( max_seq_n_.load() > next_seq - 1 )
succeeded = true;
else //Needs to load new sequence from DB, and re-calculate again
get_new_db_sequence();
}
while( !succeeded );
//Building the response
std::vector<int64_t> res{};
res.resize(n_requested);
for(int64_t n = current_seq ; n < next_seq ; n++)
res.push_back(n);
return res;
}
Мысли:
Я действительно беспокоюсь за версию без блокировки.Безопасна ли реализация?Если мы игнорируем часть загрузки БД, очевидно, да.Проблема возникает (по крайней мере, в моей голове), когда класс должен загрузить новую последовательность из БД.Безопасно ли обновление с БД?Два атомарных хранилища?
Моя вторая попытка состояла в том, чтобы объединить seq_n_ и max_seq_n_ в структуру, называемую последовательностью, и использовать одну атомарную переменную std :: atomic, но компилятор не удался.Поскольку размер последовательности структуры превышает 64-битный.
Можно ли каким-либо образом защитить часть БД, используя атомарный флаг для маркировки, если последовательность еще готова: flagустановите значение false в ожидании завершения загрузки базы данных и обновления обеих атомарных переменных.Следовательно, get_sequence необходимо обновить, чтобы дождаться, пока флаг не установит значение true.(Использование спин блокировки?)