40°

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

现在主流的多处理器架构都在硬件水平上提供了对并发同步的支持。
今天我们讨论两个很重要的硬件同步指令:Test-and-Set和Compare-and-Swap

Test and Set

一个Test-and-Set(TAS)指令包括两个子步骤,把给定的内存地址设置为1,然后返回之前的旧值。
这两个子步骤在硬件上实现为一个原子操作,执行期间不会被其他处理器打断。
(一个CPU可以使用诸如Dual-port RAM电子原件提供的TAS指令,此外,CPU自身也可以提供CAS指令)
值得注意的是,TAS指令是在1位(bit)上实现,这限制了变量非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

本文转载自博客园,原文链接:https://www.cnblogs.com/upnote/p/13193856.html

全部评论: 0

    我有话说: