基於陣列的排隊鎖定 - 尾部溢出

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;