2.6 操作系统 并发与互斥

一、同步与异步

• 同步：用来保证调用方和被调用方顺序执行。调用方需要等待被调用方执行完成之后，自身才能继续执行，调用方的逻辑控制流被阻塞。同步不一定要阻塞，只是逻辑控制流被阻塞。阻塞只是同步最常用的手段。
• 异步：调用方和被调用方各自执行。调用方发出请求之后，无需等待被调用方执行完毕就可以继续执行，被调用方的执行结果通过回调、信号等方式返回给调用方。
• 核心区别：调用方的逻辑控制流是否阻塞等待被调用方执行结束。

二、同步：有锁、无锁、无等待

• 锁的概念：核心目的是解决并发（多个操作同时进行）时，争抢共享资源（如数据、文件等）导致的混乱问题。
• 上锁（加锁）：申请独占使用权。如果资源空闲，就可获得锁并开始操作。
• 解锁（释放）：归还使用权，让其他任务可以申请。

（1）有锁 (Lock-Based)

核心思想：保证同一时间只有一个线程能进入临界区（访问共享资源）。

特点：

阻塞：未获得锁的线程会挂起等待，导致上下文切换的开销。

确定性：保证了最强的正确性（安全性）。

（2）无锁 (Lock-Free)

核心思想：不使用传统的互斥锁，通过原子操作来保证并发安全。它保证系统整体的进度不会停滞。

特点：

非阻塞：至少有一个线程能在有限步内完成操作，不会出现所有线程都卡死的情况。

高性能：在高竞争环境下，避免了线程挂起和调度的巨大开销。

活性：可能发生活锁（线程不断重试但都无法完成操作），但某个线程最终总会成功。

保证：它只保证系统整体不会卡死，不保证每一个线程都能立刻取得进展。

（3）无等待 (Wait-Free)

核心思想：是无锁的一个更强保证的子集。要求每一个线程都能在有限步内完成自己的操作，不管其他线程的行为和速度。

特点：

非阻塞：是所有非阻塞算法中最高级别的保证。

线程级进步：每个线程都独立取得进展，绝对不会出现“饿死”现象。

实现难度极高。

最强保证：提供了最强的进度保证和公平性。

三、自旋锁

自旋锁只有锁定和解锁两个状态。自旋锁不会导致休眠，会一直尝试获取锁。自旋锁只适合短期持有。如果自旋时间过长，会浪费处理器的时间，降低系统性能。自旋锁同时会禁止本处理机的抢占，如果没有禁止中断，则只有中断程序能够运行。在用户态下应尽量避免使用自旋锁。

（1）加锁

（2）解锁

直接原子将 lock 清零。

四、自旋锁和信号量可以用于中断吗？

自旋锁可以用于中断，但在获取自旋锁前，需要先禁止本地中断。因为如果获取了锁，此时又一个中断程序来了，也想要获取该自旋锁，就会导致死锁。

信号量不可以，因为会导致睡眠，而中断不可以睡眠。

五、互斥锁

（1）加锁过程：

• 如果锁未被占用（__lock = 0），则修改 __lock = 1（多线程原子修改），如果修改成功就返回。
• 如果锁的状态不是 0 或者上述修改失败（在修改前的转瞬间已被别的线程抢先获得锁），则会将__lock 修改为 2，并再一次检查 __lock 的旧值，如果旧值是 0，则加锁成功并返回；否则，执行sys_futex 系统调用（会再一次检查 __lock 的值是不是 2，如果不是 2，则说明锁的状态已经发生了改变，返回继续执行上面的逻辑；否则，将该线程添加到 sleep 队列）

结论：

• 首先加锁的线程一定不会进入内核态。
• 不管加锁还是解锁过程，__lock 的修改全都在用户态。
• 线程在加锁失败睡眠前，会对 __lock 进行三次判断（两次在用户态，一次在内核态）。所以，加锁是否进入内核态，取决于能否在 __lock = 0 的时候修改成功。

（2）解锁过程：

• 先将 __lock 的值修改为 0 判断 __lock 旧值是否小于等于1，如果是，则不需要唤醒其他线程（因为只有当前线程正确加锁 __lock 才为1）；否则，执行系统调用，唤醒一个线程。

结论：

当前线程以外的线程如果加、解过锁，那当前线程解锁一定会进入内核态（因为__lock的值会被改为2），如果确实有其他线程还在等待加锁则会进行真实唤醒，否则浅进入内核态进行虚假唤醒。

六、读写锁

读锁时共享的，写锁是独占的。

七、条件变量

本质原因：是因为需要先等待，再唤醒，要不然唤醒丢失。

1、之所以需要使用互斥锁是因为防止 唤醒丢失，假如没有互斥锁，一个消费者线程可能还没有进入阻塞，唤醒的生产者线程就已经完成了唤醒，这样就会导致唤醒丢失。

2、唤醒的时候需要先解锁再唤醒，因为如果先唤醒，阻塞的消费者线程被调度运行，但它还需要尝试获取锁，但此时获取不到就又会阻塞。

3、消费者线程需要循环等待条件满足，不能只是简单的 if 判断，因为会有虚假唤醒的发生。

八、死锁

死锁本质原因：1、系统资源有限；2、进程推进顺序不合理。

死锁的四个必要条件：互斥条件、不可剥夺条件、请求和保持条件、循环等待条件。

死锁的处理方式：预防死锁、避免死锁、检测与解除死锁。

预防死锁：1、破坏请求和保持条件：资源一次性分配。

2、破坏不可剥夺条件：当进程新的资源不能满足时，释放其已有的资源。

3、破坏循环等待条件：资源要有序分配，系统给每类资源赋予一个编号，每一个进程按编号递增的顺序请求资源。

避免死锁：系统在进行资源分配之前预先计算资源分配的安全性，若分配会导致系统不安全，则不会分配资源。（银行家算法）

检测死锁：为每个进程和资源指定一个唯一的号码，然后建立进程等待表和资源分配表。

解除死锁：1、剥夺其他进程的资源给死锁进程；2、撤销代价最小的死锁进程。

九、单核机器上写多线程程序，是否需要考虑加锁？

需要。在抢占式操作系统中，会为每一个线程分配时间片（即使是线程库创建的用户线程，也会分时运行），如果多个线程需要访问共享资源，就可能导致冲突。

十、活锁

线程不断的释放和获取资源，不断调整自身状态，导致线程无法推进，看起来是在活跃的执行，实则没有任何实质性的工作完成。

产生原因：多个进程在竞争资源的时候过于谦让。

解决策略：引入随机等待时间（不要立即进行谦让）；设置资源获取的优先级：优先级高的进程先获取资源。