Skip to content

Latest commit

 

History

History
249 lines (126 loc) · 8.42 KB

锁的实现（原子操作）.md

File metadata and controls

249 lines (126 loc) · 8.42 KB

锁的实现（原子操作）

要防止一段代码在执行过程中被别的进程插入，就需要考虑一个线程在执行过程中被切换的途径。

切换进程的方式：

  • 通过调用 yield 之类的系统调用自愿放弃 CPU 而将控制权交给操作系统调度。

  • 通过中断来实现强制放弃 CPU 而失去控制权。

由于原语执行过程中，线程不会自动放弃 CPU 控制权。因此要防止进程切换，就要在原语执行过程中不能发生中断。

所以可以通过禁止中断，并且不自动调用 yield 之类的系统调用来防止进程切换，从而使操作变成原子操作。

PS：禁用中断和启用中断都是硬件原子操作

1、简单中断

  • 适用于临界区比较短
  • 类似的信号的处理函数就是使用了简单屏蔽信号，所以当信号处理的逻辑很长时，需要将主要处理逻辑放到主线程中处理。
    • 信号处理函数只进行将信号传给主函数**（统一事件源）**
      • 管道
      • I/O复用

2、软件处理

3、更高级别的抽象（硬件支持）

image-20210126204624120

  • 抽象出锁，只用获得锁和释放锁
抽象锁的实现

对于PC，使用硬件支持的互斥（进入临界区退出临界区）更常见

可以根据临界区的长短，进行忙等和非忙等的改进

锁无法实现次序同步（竞态条件）

  • test_and_set
    • 一条机器指令完成了通常读写操作的两条指令的功能
      • 1、从内存中读取值
      • 2、测试该值是否为1（然后返回真或假）
      • 3、内存值设为1
    • 只能开始为0时才可能跳出
  • exchange
  • compare_exchange_strong 如何要么更改原子对象的值，要么将变量用于比较。更改成功返回真，否则返回假

image-20210126205126363

image-20210126205433528

  • 被封装成机器指令
  • test_and_set返回了先前值

image-20210126210008260

  • 只能开始为0时才可能跳出
  • 由于是忙等，当临界区较长时，消耗的CPU资源较多

image-20210126210124160

改进
  • 利用等待某个事件时，进行阻塞睡眠，将其挂到相应的等待队列中，即可以让出CPU，让其他线程或进程使用
  • 当处于临界区的线程退出时，其会将相应的value值赋值为0，同时还做一个唤醒操作，使得等待的线程可以重新判断是否可以跳过循环。
自旋与快用户模式
  • 对于临界区时间较短的情况下，根据愿意选择忙等，不需要进行线程的切换（上下文切换），因为上下文切换也需要耗费较多的时间
  • 而临界区很长，远远大于上下文切换的开销时，使用快用户模式，非忙等

image-20210126210831350

exchange实现锁

image-20210126211754123

  • 相应的也可以改进为阻塞唤醒
优点image-20210126211931142
  • 对于PC，使用硬件支持的互斥锁更常见
  • 适用于多核CPU，不适用于单核CPU
缺点
  • 忙等销毁处理器的时间（可以改进）
  • 当多个进程离开临界区并且多个进程在等待的时候可能导致饥饿
  • 死锁 当处于优先级调度时，如果一个低优先级的进程拥有临界区并且一个高优先级进程出现需求，那么高优先级进程会获得处理器并且忙等待临界区，就会造成死锁
    • 可以使用计算机反转来处理解决

image-20210127001356771

自旋锁原理

  • 自旋锁的原理比较简单，如果持有锁的线程能在短时间内释放锁资源，那么等待竞争锁的线程就不需要做内核态和用户态之间的切换进入阻塞状态，只需要等一等(自旋)，等到持有锁的线程释放锁后即可获取，避免用户进程和内核切换的消耗。
  • 自旋锁避免了操作系统进程调度和线程切换，通常适用在时间极短的情况，因此操作系统的内核经常使用自旋锁。但如果长时间上锁，自旋锁会非常耗费性能。线程持有锁时间越长，则持有锁的线程被 OS调度程序中断的风险越大。如果发生中断情况，那么其它线程将保持旋转状态(反复尝试获取锁)，而持有锁的线程并不打算释放锁，导致结果是无限期推迟，直到持有锁的线程可以完成并释放它为止。
  • 自旋锁的目的是占着CPU资源不进行释放，等到获取锁立即进行处理。如果自旋执行时间太长，会有大量的线程处于自旋状态占用CPU资源，进而会影响整体系统的性能，因此可以给自旋锁设定一个自旋时间，等时间一到立即释放自旋锁。
  • 我们一般使用mutex，等待睡眠锁

忙等的锁可以实现FIFO的特点吗？

信号量

使用信号量和管程实现多个线程进入临界区执行？

  • 当进行读操作时，不用只限制一个线程或进程执行
  • 次序同步
  • -互斥

抽象数据类型

image-20210127001817207

  • lock只允许一个列车进入临界区，这就是抽象的锁的局限
  • 最早期操作系统的同步原语

image-20210127003007998

V操作

  • sem+1，若当前小于等于0，唤醒一个等待的线程

  • V不会被阻塞

  • 忙等的锁可以实现FIFO的特点吗？

P操作
  • P操作会被阻塞，所以需要小心设置加锁顺序死锁
  • sem-- ,若小于等于0则会被阻塞

image-20210127003138512

  • 间接制约，进入临界区可能有多个线程

信号量的使用

  • 直接制约关系

image-20210127003408702

  • 间接制约关系

image-20210127003451577

  • 同步次序

image-20210127003656045

  • 互斥操作
  • 同步操作

image-20210127003857756

  • 每个约束用一个单独的信号量

信号量的实现

image-20210127001817207

根据抽象的数据类型

  • 一个整形
  • 两个原子操作，即对该整形的原子操作
  • 等待队列

image-20210127005650118

  • V（N） 可以直接释放多个，在V的最外层加while

条件变量的实现

条件变量 wait的实现

1、计数++  numwait++;

2、将线程挂在等待的条件变量上（加入到队列）

3、解锁  release(lock);

4、schedule调度，自身阻塞，切换其他线程

5、当该线程变为运行态时获得锁  require(lock);

signals的实现

if（numwait>0）
{
	1、将挂在条件变量上的线程剥离（从队列中取出）
	2、将剥离的线程唤醒，变为就绪态
   	3、计数-- numwait--
}

image-20210131191242787

信号量可以提前知道资源数 环形队列

条件变量，也算是知道有多少资源的