基于阵列的排队锁定 - 尾部溢出

Question

我正在就我的大学给出的有关实施基于阵列的排队锁定的练习开展工作。

我的问题是：如果tail变量负责给每个等待线程各自的位置溢出会发生什么？我不是指在数组的大小上增长的tail变量，我说的是整数溢出。

使用mod，只要尾部没有溢出，就可以找到线程在阵列中必须具有的正确位置。一旦它溢出了，使用mod就可能指向一个已经被占用的位置，或者它可能导致在前一个tail元素未被使用之后离开下一个位置，从而使得线程无法连续地解锁数组并且有一个正常的执行。

有关解决此问题的任何建议？

Answer 1

我认为，对于设定的线程数计算tail的最大值，当没有问题时，即当tail mod num_threads为0时最大值为tail。然后如果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;