Home

OSTEP笔记:Fetch-And-Add和排号自旋锁

posted at 2019-07-03
上次分享了如何使用test-and-set指令实现自旋锁。

test-and-set是指在将数据写入内存的同时返回之前内存中存储的旧值,test-and-set可以保证操作原子性。

这次要介绍的是用fetch-and-add指令实现一个排号自旋锁。

什么是排号自旋锁?

引用维基百科的定义:

排号自旋锁是计算机科学中的一种多线程同步机制。类似于自旋锁,但每一个申请排队自旋锁的线程获得一个排队号(ticket)。至多一个线程拥有自旋锁,当它释放锁时,把自身的ticket加1作为下一个可获得锁的ticket,持有该ticket的线程在自旋检查时就可发现已经获得了自旋锁。这种机制类似于一些提供社会服务的场所(如银行):进门的顾客从排号机获取一个等待号,然后不断检查当前可服务的号,直至轮到其手持的号。这是一种先进先出(FIFO)的公平性机制。 


实现代码:

typedef struct __lock_t { 
  int ticket; 
  int turn; 
} lock_t;

void lock_init(lock_t * lock) {
  lock->ticket = 0; 
  lock->turn = 0; 
}

void lock(lock_t * lock) {
  int myturn = FetchAndAdd(&lock->ticket); 
  while (lock->turn != myturn) 
    ; // spin 
}

void unlock(lock_t * lock) { 
  lock->turn = lock->turn + 1; 
}


排号自旋锁保证了公平性,但是它依然是自旋锁(spinning)的,排号自旋锁没有解决性能低下的问题。例如,线程一持锁,但是运行过程中被中断了,切换执行线程二,线程二此时无法获得锁,因此一直在轮询,直到定时器中断,运行线程一,线程一释放锁,线程二才可以继续运行。

光靠硬件是无法解决轮询这个问题的,我们需要借助操作系统来实现不使用轮训的锁。