硬件對同步的支持-TAS和CAS指令

目錄

• Test and Set
• Compare and Swap
  • 使用CAS實現線程安全的數據結構。

現在主流的多處理器架構都在硬件水平上提供了對併發同步的支持。
今天我們討論兩個很重要的硬件同步指令：Test-and-Set和Compare-and-Swap

Test and Set

一個Test-and-Set(TAS)指令包括兩個子步驟，把給定的內存地址設置為1，然後返回之前的舊值。
這兩個子步驟在硬件上實現為一個原子操作，執行期間不會被其他處理器打斷。
(一個CPU可以使用諸如Dual-port RAM电子原件提供的TAS指令，此外，CPU自身也可以提供CAS指令)
值得注意的是，TAS指令是在單個內存word(或字節)上實現，這限制了變量非0即1，並且TAS總是把變量設置為1。
可見，TAS生而為自旋鎖，下面是使用TAS實現自旋鎖的偽代碼[2]：

lock = 0 //shared state
while(test_and_set(lock)==0){ //try lock
       //do nothing   
}
// 臨界區代碼
lock = 0   //release 

當第一個線程執行這段代碼時，TAS指令會立即把lock設置為1，並返回0 ，線程退出while循環進入臨界區。
如果另一個線程嘗試進入臨界區，TAS會把lock設置為1，但是也會返回1(由第一個線程的TAS指令設置為1)，
此時第二個線程會一直while循環(忙等待)，直到第一個線程退出臨界區代碼，執行了lock=0，即釋放了鎖。
這種通過while-loop等待獲取鎖的實現稱為自旋鎖(spin lock)。

Compare and Swap

compare-and-swap(CAS)指令和TAS指令類似，但是比TAS要更複雜。
與TAS只有一個參數不同，CAS指令需要三個參數，一個內存位置(V)、一個期望舊值(A)、一個新值(B)。
CAS指令的執行過程：

1.比較內存V的值是否與A相等？
2.如果相等，則用新值B替換內存位置V的舊值
3.如果不相等，不做任何操作。
4.無論哪個情況，CAS都會把內存V原來的值返回。

偽代碼：

int CAS(int *ptr,int oldvalue,int newvalue)
{
   int temp = *ptr;
   if(*ptr == oldvalue)
       *ptr = newvalue
   return temp;
}

以上過程在CAS指令中是原子操作。
CAS支持32bit/64bit的數據類型，這使得CAS能夠實現一些更複雜的自旋鎖。

使用CAS實現線程安全的數據結構。

我們使用CAS實現一個併發的平衡二叉搜索樹。[1]
基本思路是，所有的更新操作都要在二叉樹的副本上進行，更新完成后，使用CAS指令把新的根節點引用替換舊的引用。

//共享變量
  root = pointer to the root of the tree
//插入操作
do
  old_root = root
  new_root = new Tree
  # copy old_root into new_root
  # do insertion into new_root
until compare_and_swap (root, old_root, new_root) == old_root
平衡操作:
do
  old_root = root
  new_root = balanced_copy_of (old_root)
until compare_and_swap (root, old_root, new_root) == old_root

如果并行的執行平衡操作和插入操作，插入操作完成後會把二叉樹的根節點指向新的引用。
等到平衡操作完成后，compare_and_swap將會失敗，因為此時根節點指向了插入操作產生的新地址，不再等於old_root，
平衡操作會重複循環執行，直到成功更新根節點。
同樣的，如果平衡操作先於插入操作完成，插入操作的CAS指令也會失敗（根節點已指向平衡操作產生的新地址），然後插入操作重複循環，直到成功。

基於CAS指令可以實現基礎的信號量、互斥量之外，還可以實現更複雜的lock-free和wait-free算法。

延伸閱讀:

1.康奈爾大學操作系統課件:Architectural support for synchronization
2.wiki:Test-and-Set指令
3.wiki:Compare-and-swap指令
4.TAS vs CAS

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※帶您來了解什麼是 USB CONNECTOR  ?

※自行創業缺乏曝光? 網頁設計幫您第一時間規劃公司的形象門面

※如何讓商品強力曝光呢? 網頁設計公司幫您建置最吸引人的網站，提高曝光率!

※綠能、環保無空污,成為電動車最新代名詞，目前市場使用率逐漸普及化

※廣告預算用在刀口上，台北網頁設計公司幫您達到更多曝光效益

※教你寫出一流的銷售文案?