By

Contents
  1. 1. Lock的实现
    1. 1.1. Test and Set
    2. 1.2. compare-and-exchange
    3. 1.3. Fetch-And-Add
  2. 2. sleep代替spin
  3. 3. Two-Phase Locks

并发问题中我们需要对一系列的指令进行“原子操作”，但是由于中断和多处理器的存在，这无法保证，因此引入了Lock的概念。我们将critical section用Lock标注包围，从而使之成为原子操作。

比如说要对以下代码进行原子操作

1
balance = balance + 1

以上代码包含三个基本指令：取值、相加、存储，因而有可能中途被打断，我们可以执行如下的操作。

1
2
3
4
5
lock_t mutex; // some globally-allocated lock ’mutex’
...
lock(&mutex);
balance = balance + 1;
unlock(&mutex);

代码中的mutex就是Lock，如果mutex是available，那么就会立即返回线程进入执行被保护代码，如果当前是acquired，那么就会被block一直等待，直到mutex状态变为available。mutex意为mutual exclusive，它也包含其它信息，如当前拥有它的线程，以及预定该Lock的队列等，但对用户并不可见。

1
2
3
4
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_lock(&lock); 
balance = balance + 1;
pthread_mutex_unlock(&lock);

Lock的实现

操作系统要实现Lock，需要硬件的支持，在设计实现方式时，需要考虑以下几点

1、mutual exclusion 基本功能，必须保证排它性
2、fairness 有相等的机会获取锁，不能有线程starve
3、performance

假设没有硬件支持，直接使用普通变量作为mutex，那么在测试与获取之间，就有可能发生“错误”操作：线程1和线程2可能交替地测试lock为可获取并进入critical section。所以要实现mutex，必须test and set是一个原子操作，需要由硬件提供。同时在等待lock的wait阶段，如果没有硬件支持，线程必须不停地spin，会占用大量的CPU资源，特别在单处理器系统中，会导致持有lock的线程难以运行，造成效率的极大浪费。

Test and Set

硬件提供基本指令，获取当前值当更新为指定值，一个指令内完成，自然也是原子操作。用伪代码示意如下：

1
2
3
4
5
int TestAndSet(int* old_ptr, int new) {
    int old = *old_ptr; // fetch old value at old_ptr
    *old_ptr = new; // store ’new’ into old_ptr
    return old; // return the old value
}

使用方法如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typedef struct __lock_t {
    int flag;
} lock_t;
void init(lock_t *lock) {
    // 0 indicates that lock is available, 1 that it is held
    lock->flag = 0;
}
void lock(lock_t *lock) {
    while (TestAndSet(&lock->flag, 1) == 1)
    ; // spin-wait (do nothing)
}
void unlock(lock_t *lock) {
    lock->flag = 0;
}

这种方法可以保证mutex，但是却依然有spin消耗CPU的问题。

compare-and-exchange

整体来说与test and set有些类似，不过使用了指针。伪代码表示如下：

1
2
3
4
5
6
7
int CompareAndSwap(int *ptr, int expected, int new) {
    int actual = *ptr;
    if (actual == expected)
        *ptr = new;
    return actual;
}
Figure 28.4: Compare-and-swap

如果ptr指向值与expected相等，则更新为指向值为new，否则不操作，返回值为*ptr。
使用方法也与test and set相同

Fetch-And-Add

简单地说，就是将i++做成一个基本指令。

1
2
3
4
5
int FetchAndAdd(int *ptr) {
int old = *ptr;
*ptr = old + 1;
return old;
}

使用方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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;
}

这种方式使用了两个变量组成一个结构体来构成锁，其中一个代表自己的ticket，另一个代表轮盘。lock操作即取票并与轮盘比对，符合即进入执行，否则spin。unlock则将轮盘前拨1位（+1）。

这种方式，较之前方案有一个明显特点，就是可以防止Stare。每个线程都会轮番地得到资源。

sleep代替spin

上述的方案，都在解决mutex问题（互斥）,但是没有改善spin消费CPU的问题。思路很简单，也是由硬件和OS提供支持，在线程获取lock失败后，让其进行休眠，并加入OS管理的队列，在lock被释放后，由OS来依次唤醒队列中休眠的线程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
typedef struct __lock_t {
	int flag;
	int guard;
	queue_t *q;
} lock_t;
void lock_init(lock_t *m) {
	m->flag = 0;
	m->guard = 0;
	queue_init(m->q);
}
void lock(lock_t *m) {
	while (TestAndSet(&m->guard, 1) == 1)
	; //acquire guard lock by spinning
	if (m->flag == 0) {
    	m->flag = 1; // lock is acquired
    	m->guard = 0;
    } else {
    	queue_add(m->q, gettid());
    	m->guard = 0;
    	park();
    }
}
void unlock(lock_t *m) {
	while (TestAndSet(&m->guard, 1) == 1)
	; //acquire guard lock by spinning
	if (queue_empty(m->q))
		m->flag = 0; // let go of lock; no one wants it
	else
		unpark(queue_remove(m->q)); // hold lock (for next thread!)
	m->guard = 0;
}

上述方式为了能让等待线程能尽快进行sleep（park)，使用了一个guard来保证mutex，同时用flag来代表真正的lock。获得gurad之后，可以实现原子操作，但不代表可以执行critical section。如果flag（lock）可用，将flag置位，进入执行。如果不可用，则将线程加入队列并休眠。两种情况下都会在获得gurad独占后将gurad及时复位，因而理论上不会造成其它线程的长时间spin。

需要注意的是unlock的过程，当有线程在队列中时，unlock并没有释放falg(lock)，因为unpark之后，被唤醒的线程会直接进入执行(从lock返回）,因而无需也不能释放lock。只有在无线程处于等待时，才释放lock。

但这也引入了一个race condition的问题。假设只有两个线程，其中一线程在park前被context switch到拥有lock的线程，然后lock被释放，那么获取lock的线程将立即进入park，从而永久沉睡。此称为wakeup/waiting race.

一个解决方案是增加一个system call：setpark()。表示将要执行park，但如果期间被中断并有其它线程调用了unpark，那么setpart会立即返回，并不进行park.

另一个解决方案是将guard置于kernel中，当上述情况发生时kernel可以释放lock并dequeue运行中的线程。

Two-Phase Locks

Linux使用了较老风格的tow-phase lock, 在第一个phase，它会spin等待lock，如果获取失败，进入Phase 2，则开始sleep，直到Lock可用。

总之lock的实现需要硬件+OS的支持，而设计一个通用性强的lock则是富有挑战的。

Contents
  1. 1. Lock的实现
    1. 1.1. Test and Set
    2. 1.2. compare-and-exchange
    3. 1.3. Fetch-And-Add
  2. 2. sleep代替spin
  3. 3. Two-Phase Locks