本文最后更新于:1 小时前

#

# 基于标志的锁

以下是基于标志(flag)的锁的实现方式:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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 检测和设置本该是一体的,但由于无法保证原子性,那么 whilemutex -> flag = 1 之间就可能混入其他线程的操作,例如线程 A 执行到 mutex->flag = 1 语句之前,另一个线程 B 运行到 while ,由于 mutex->flag 还未被赋值为 1,线程 B 也可以跳出 while ,于是线程 A 和 B 都拿到了这把锁。


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

以下是 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
}

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

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

# 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 锁实现方式:

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
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_incrementatomic_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 的使用效率。


本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!