Блокировка очередей на основе массива - переполнение хвоста

Question

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

Мой вопрос следующий: что произойдет, если переменная tail, ответственная за предоставление каждой ожидающей нити своей соответствующей позиции, переполнения? Я не имею в виду переменную tail, растущую по размеру массива, я говорю о переполнении как целого.

Используя mod, вы найдете нужную позицию, которую должен иметь поток в массиве, если хвост не переполнен. Как только он переполняется, использование мода на нем может указывать на позицию, которая уже занята, или это может привести к тому, что она оставит следующую позицию после того, как предыдущий элемент хвоста не будет использован, тем самым не позволяя потокам последовательно разблокировать массив и иметь нормальный выполнение.

Любые советы по решению этого вопроса?

Answer 1

Думаю, для заданного количества потоков вычисления максимального значения для tail, когда никаких проблем не будет, то есть максимальное tail, когда tail mod num_threads является 0. И потом, если tail удастся его, установить хвост 0

в конструкторе я определить максимальное число для tail

for(unsigned i = UINT32_MAX; ; --i) // UINT32_MAX - max unsigned type value 
    if(i % size == 0)//size - max number of concurrent threads 
    { 
     max_tail = i; 
     break; 
    } 

и lock метод проверить его

unsigned max = max_tail;//otherwise, may overwrite max_tail 
tail.compare_exchange_strong(max, 0); 

полный код (C + +17)

class arr_lock 
{ 
    std::atomic<unsigned> tail; 
    static thread_local unsigned slotInd; 
    bool* flag; 
    unsigned size;//max number of concurrent threads 
    static constexpr size_t L1_cache = std::hardware_destructive_interference_size; 
    static constexpr size_t mult = L1_cache/sizeof(bool); 
    unsigned max_tail; 

public: 
    arr_lock(unsigned size_) : 
     tail(0), 
     size(size_), 
    { 
     unsigned arr_size = mult * size;//padded for disable false sharing 
     flag = new bool[arr_size]; 
     for(unsigned i = 0; i < arr_size; ++ i) 
      flag[i] = false;   
     flag[0] = true; 

     for(unsigned i = UINT32_MAX; ; --i) 
      if(i % size == 0) 
      { 
       max_tail = i; 
       break; 
      } 
    } 

    ~arr_lock() 
    { 
     delete [] flag; 
    } 

    void lock() 
    { 
     unsigned max = max_tail;//otherwise, may overwrite max_tail 
     tail.compare_exchange_strong(max, 0); 
     unsigned slotInd = tail.fetch_add(1) % size; 
     unsigned ind = mult * slotInd; 
     while(!flag[ind]); 
    } 

    void unlock() 
    { 
     flag[mult * slotInd] = false; 
     flag[mult * (slotInd + 1) % (mult * size)] = true; 
    } 
}; 

thread_local unsigned arr_lock::slotInd = 0;