Skip to content

Latest commit

 

History

History
357 lines (194 loc) · 9.35 KB

9-同步原语.md

File metadata and controls

357 lines (194 loc) · 9.35 KB
Raw

同步原语

1. 生产者消费者问题

多生产者会出现会将新产生的数据放入到同一个缓冲区中，造成数据覆盖的问题

竞争条件

  • 当多个进程同时对共享的数据进行操作
  • 该共享数据最后的结果依赖于这些进程特定的执行顺序

解决临界区问题的三个要求

  1. 互斥访问：在同一时刻，有且仅有一个进程 可以进入临界区
  2. 有限等待：当一个进程申请进入临界区之后 ，必须在有限的时间内获得许可进入临界区 而不能无限等待
  3. 空闲让进：当没有进程在临界区中时，必须 在申请进入临界区的进程中选择一个进入临 界区，保证执行临界区的进展

2. 软件：皮特森算法

皮特森

书：P210

问题

  1. 只能应付两个线程的状况
  2. 现代CPU允许访存操作乱序执行，皮特森算法无法正常工作

3. 硬件：关闭中断

问题

  • 只适合单核，不适合多核

4. 软硬件协同：原子操作实现互斥锁

4.1 原子操作

原子操作

CAS：比较地址addr上的值和期望值expected是否相等，相等则置换为new_value，返回addr存放的旧值

FAA：读取addr上的旧值，将其加上add_value并存入，返回addr上的旧值

4.1.1 Intel硬件实现

🔺 锁总线：对任意地址的修改都要经过总线的，通过锁总线来实现原子操作

intel锁总线

4.1.2 arm

🔺 LL/SC : 在Load-Link时，CPU使用专门的监视器，记录当前访问的地址，而在store-conditional时，当前仅当监视的地址没有被其他核修改时，才执行存储操作，否则失败

LL-SC

4.2 自旋锁(spin lock)

▲ 利用CAS

实现

void lock(int *lock) {
	while(atomic_CAS(lock, 0, 1)!= 0)
		/* Busy-looping */ ;
}
void unlock(int *lock) {
	*lock = 0;
}

条件

  1. 互斥访问：√

  2. 有限等待

    • 🔺 自旋锁不能保证有线等待
    • 原子操作的成功与否完全取决于硬件特性。小核的运行频率低，在于大核竞争时，可能永远也无法获取锁

  3. 空闲让进：？

    依赖于硬件 => 当多个核同时对一个地址执行原子操作时，能否保证至少有一个能够成功

4.3 排号锁

▲ 利用FAA

void lock(int *lock) {
	volatile unsigned my_ticket =
	atomic_FAA(&lock->next, 1);
	while(lock->owner != my_ticket)
	/* busy waiting */;
}
void unlock(int *lock) {
	lock->owner ++;
}

条件

  1. 互斥访问 ✓

  2. 有限等待 ？

    按照顺序，在前序竞争者保证有限 时间释放时，可以达到有限等待

  3. 空闲让进 ✓

5. 读写锁

互斥锁：所有的进程均互斥，同一时刻只能有一个进程进入临界区对于部分只读取共享数据的进程过于严厉

读写锁：区分读者与写者，允许读者之间并行，读者与写者之间互斥

读写锁2读写锁1

5.1 读写锁的偏向性

考虑这种情况：

  • t0：有读者在临界区
  • t1：有新的写者在等待
  • t2：另一个读者能否进入临界区？

不能：偏向写者的读写锁

  • 后序读者必须等待写者进入后才进入
  • 更加公平

能：偏向读者的读写锁

  • 后序读者可以直接进入临界区
  • 更好的并行性

5.2 偏向读者的读写锁

偏向读者的读写锁

具体解析见书P231

为什么lock_reader中对reader的加一操作使用互斥锁而非原子指令FAA

因为后一句还要检查lock->reader==1要再次使用reader，要保证这两行操作的原子性

既然读者也要一个读者锁， 那怎么提高读者的效率？

额外的读者锁，在临界区开始之前就已经执行了放锁操作，其保护的是对reader_cnt的修改

6. RCU

读写锁：虽然允许多个读者同时进入读临界区，但是写会阻塞读者，且读者仍然需要在关键路径上添加读者锁

RCU：读者即使在有写者写的时候也能随意读

需求：：需要一种能够类似之前硬件原子操作的方式，让读者要么看到旧的值，要么看到新的值，不会读到任何中间结果

▲ 单拷贝原子性：对地址对齐的单一读写操作的原子性保证，其支持尾款往往与CPU位宽一致

6.1 操作

6.1.1 插入新的节点

RCU插入新的节点

6.1.2 删除

RCU删除

6.1.3 修改

RCU修改

6.2 宽限期

需求：在合适的时间，回收无用的旧拷贝

  • 写者必须区分出有可能观察到旧数据的读者
  • 读者必须标记自己的读临界区开始与结束的位置
    • 使用接口rcu_read_lock和rcu_read_unlock标记
void rcu_reader() {
	RCU_READ_START();				// 通知RCU，读者进临界区了
	/* Reader Critical Section */
	RCU_READ_STOP();				// 通知RCU，读者出临界区了
}

（可以使用不同的方式实现：如计数器）

6.3 同x步原语对比：读写锁 vs RCU

相同点：允许读者并行

不同点：

  • 读写锁：
    • 读者也需要上读者锁
    • 关键路径上有额外开销
    • 方便使用
    • 可以选择对写者开销不大的读写锁
  • RCU
    • 读者无需上锁
    • 使用较繁琐
    • 写者开销大

7. 死锁

7.1 死锁产生原因

死锁是由于资源有限以及线程的交错执行造成的

必要条件

  1. 互斥访问
  2. 持有并等待
  3. 资源非抢占
  4. 循环等待

7.2 出问题再处理：死锁的检测与恢复

出问题再处理-死锁的检测与恢复

什么时候运行死锁检测：

  1. 定时监测
  2. 超时等待检测

7.3 设计时避免：死锁预防

7.3.1 避免互斥访问：通过其他手段（如代理执行）

共享数据只能通过代理线程来操作

问题

  1. 大部分应用不容易修改成此模式
  2. 对于每一个共享资源，都需要一个代理线程，负担大

7.3.2 不允许持有并等待：一次性申请所有资源

在真正开始操作之前，一次性申请所有资源

一次性申请所有资源

问题：live lock

7.3.3 资源允许抢占：需要考虑如何恢复

允许一个线程抢占其他线程已经占有的资源

问题

只适用于易于保存和恢复的场景

7.3.4 打破循环等待：按照特定顺序获取资源

Ø 所有资源进行编号

Ø 所有进程递增获取

任意时刻：获取最大资源号的进程可以继续执行，然后释放资源

7.4 死锁避免：运行时检查是否会出现死锁

银行家算法

  • 所有进程获取资源需要通过管理者同意
  • 管理者预演会不会造成死锁
    • 如果会造成：阻塞进程，下次再给
    • 如果不会造成：给进程该资源

8. 优先级反转

出现原因：双重调度不协调

操作系统：基于优先级调度

锁：对于竞争同一个资源的进程按照锁使用的策略进行“调度“

如何解决？打通两重调度，给另一个调度hint

8.1 不可打断临界区协议 NCP

进入临界区后不允许其他进程打断：禁止操作系统调度

8.2 优先级继承协议 PIP

高优先级进程被阻塞时，继承给锁持有者自己的优先级

8.3 即时优先级置顶协议 IPCP

获取锁时，给持有者该锁竞争者中最高优先级

即时优先级置顶协议

8.4 原生优先级置顶协议

高优先级进程被阻塞时，给锁持有者该锁竞争者中最高优先级

原生优先级置顶协议

8.5 对比

不可打断临界区协议 (Non-preemptive Critical Sections, NCP)

  • 进入临界区后不允许其他进程打断：禁止操作系统调度
  • 易实现，但会阻塞系统正常运行（更高优先级的程序正常执行）

优先级继承协议 (Priority Inheritance Protocol, PIP)

  • 高优先级进程被阻塞时，继承给锁持有者自己的优先级：锁给操作系统调度hint
  • 难实现，且每次有更高优先级的竞争者出现时都会被打断然后重新继承

即时优先级置顶协议 (Immediate Priority Ceiling Protocols, IPCP)

  • 获取锁时，给持有者该锁竞争者中最高优先级：锁给操作系统调度hint
  • 易实现，但需要知道有哪些竞争者会竞争锁。直接给最高与NCP相同

原生优先级置顶协议 (Original Priority Ceiling Protocols, OPCP)

  • 高优先级进程被阻塞时，给锁持有者该锁竞争者中最高优先级：锁给操作系统调度hint
  • 难实现，需要知道有哪些竞争者会竞争锁，一旦发生置顶便不会再被其他竞争者打断

在课程中，我们了解了对读者友好的读写锁定的情况。 这种锁定会导致写者饿死，其原因是？ 请提供一种对写者友好的读写锁定设计（避免写者饥饿）

基本思想是：当写者等待锁时，它将阻止以后想要获取锁的读者。以下为代码样例这是一个代码模板：

写者友好的读写锁