# 锁

# 基于标志的锁

以下是基于标志（flag）的锁的实现方式：

typedef struct __lock_t {int flag;} lock_t;

void init(lock_t *mutex){
    // 0 -> lock is available, 1 -> held
    mutex -> flag = 0;
}

void lock(lock_t *mutex){
    while(mutex -> flag == 1) // TEST the flag
        ;// spin-wait(do nothing)
    mutex -> flag = 1;
}

void unlock(lock_t *mutex){
    mutex -> flag = 0;
}

# 1.1

第 10 行的注释，spin-wait，是什么意思？

答： spin-wait 是指自旋等待， flag 为 1 时，线程反复检查锁变量是否可用； flag 为 0 时，说明锁变量可用，设置 flag 为 1 表示保持该锁。

# 1.2

假设没有底层硬件或者操作系统的相关支持，该锁用于进程间的互斥，则其实现方式会有什么问题？请详细说明。

答：获取、释放锁，实际上是读写存储内存或寄存器，因此这种读写操作必须是原子的。如果没有底层硬件或者操作系统的支持，那么就无法保证其操作的原子性。对于 lock函数 ， flag 检测和设置本该是一体的，但由于无法保证原子性，那么 while 和 mutex -> flag = 1 之间就可能混入其他线程的操作，例如线程 A 执行到 mutex->flag = 1 语句之前，另一个线程 B 运行到 while ，由于 mutex->flag 还未被赋值为 1，线程 B 也可以跳出 while ，于是线程 A 和 B 都拿到了这把锁。

---

# 基于 Test-and-Set 原子指令的锁

以下是 Test-and-Set 原子指令的实现逻辑：

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
}

以下是基于 Test-and-Set 指令的锁实现方式：

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;
}

# 2.1

"基于 Test-and-Set" 指令的锁实现方式，是否可以解决 1.2 中，“基于标志 （flag）的锁实现方式” 所存在的问题，为什么？

答：可以。“返回旧值” 和 “设置新值” 这两个操作共同组成了一个原子操作，执行期间不会被打断。当线程 A 执行 TestAndSet 原语时，会把 lock->flag 设置为 1，并返回之前的值。若返回值是 0，那么线程 A 就可以退出 while ，此时若线程 B 也进入 while ，由于 TestAndSet 原语已把 lock->flag 设置为 1，线程 B 无法退出 while ，也就不会出现有多个线程同时拿到同一把锁的情况。

# 2.2

假设系统中有 2 个线程 X 和 Y（优先级相同），它们之间通过 “CPU 时间片轮转调度策略” 来分享底层唯一的一个 CPU 资源。其中，X 在某个时刻通过图 3 的 lock () 获取到了锁，并且需要运行 10 个时间片才会调用 unlock () 来释放锁。请问，在此时间段内，Y 会分到时间片吗？如果可以分到，那么 Y 是个什么运行形态？此运行形态会带来什么样的负面效果？

答：Y 会分到时间片。按照时间片轮转调度策略，X 的时间片结束之后，就会被移动到就绪队列尾部，这时 Y 分到时间片并开始执行，但是锁还被 X 占据，所以 Y 即使分到了时间片，也只能一直停留在 while 中，直到 Y 的时间片结束，然后轮到 X 继续执行…… 实际上 Y 除了循环判断 lock->flag ，并没有做什么有用的工作。这样的运行形态会使得 CPU 运行效率变得比较低，因为 Y 实际上并没有做什么工作，造成资源浪费。

---

# 基于 Linux 的 Futex 锁

以下是基于 Linux 的 Futex 锁实现方式：

void mutex_lock (int *mutex) {
	int v;
	/* Bit 31 was clear, we got the mutex (this is the fastpath) */
	if (atomic_bit_test_set (mutex, 31) == 0)
     	return;
	atomic_increment (mutex);
	while (1) {
 		if (atomic_bit_test_set (mutex, 31) == 0) {
 			atomic_decrement (mutex);
 			return;
 		}
 		/* We have to wait now. First make sure the futex value
 		We are monitoring is truly negative (i.e. locked). */
 		v = *mutex;
 		if (v >= 0)
			continue;
 		futex_wait (mutex, v);
 	}/*end while*/
}

void mutex_unlock (int *mutex) {
	/* Adding 0x80000000 to the counter results in 0 if and only if
     there are not other interested threads */
     if (atomic_add_zero (mutex, 0x80000000))
         return;

     /* There are other threads waiting for this mutex,
     wake one of them up. */
     futex_wake (mutex);
}

# 3.1

该图中的第 4～5 行，和图中的第 8～11 行，具体实现什么作用？它们是否有功 能冗余和冲突？可以去掉当中的一个吗？为什么？

答：

• 4-5 行：判断锁是否被占用并置 1，若能获取锁，则直接退出 mutex_lock() 。
• 8-11 行：被 futex_wait 的线程被 futex_wake 唤醒后，判断能否获取锁，若能则占用锁并退出 while 。
• 不能去掉任何一个。对于 4-5 行，若能直接获取锁，则无需被 wait ；若去掉 8-11 行，则被 wake 后也无法跳出 while 。这两段代码是配合 atomic_increment 和 atomic_decrement 使用的，能够统计在等待的线程数，缺一不可。

# 3.2

在第 24～25 行中的 if 语句是用来干什么的？如果条件语句 atomic_add_zero (mutex, 0x80000000) 为真，为什么要直接 return，为什么不直接执行第 29 行程序呢？

答：

• if 语句是为了确保锁可用时，不会执行 wait 。假设没有 if 语句，A 没有获取到锁，在 A 执行 wait 之前，B 执行了 unlock ，此时 atomic_add_zero 返回 true ，也就不会执行 wake ，然后 A 执行了 wait ，此时如果没有新的线程加入，那么 A 就永远不会被唤醒。
• 如果条件语句 atomic_add_zero (mutex, 0x80000000) 为真，说明在等待的线程数为 0，没有线程需要被 wake ，直接 return 能提高效率。

# 3.3

Futex 锁实现方式是否改进了 2.2 问题中提到的负面效果，为什么？

答：改进了 2.2 问题中的负面效果， futex_wait 可以让正在执行但没有获得锁的线程睡眠，让出 CPU 给别的线程，避免了无用的等待，能提高 CPU 的使用效率。