Linux操作系统--8--操作系统中锁的实现

1 线程状态线程的基本状态简化操作系统中的线程通常有以下几种状态运行线程正在 CPU 上执行指令。就绪线程可以运行但暂时没有分配到 CPU等待调度。阻塞等待线程因为等待某个事件如锁、I/O而主动放弃 CPU不会参与调度直到被唤醒。终止线程结束。自旋和睡眠对应的是不同的状态切换。2 等待队列 与 就绪队列就绪队列存放对象处于就绪状态的线程已经具备运行条件只等 CPU 分配时间片。作用调度器从就绪队列中选择下一个要运行的线程如 FIFO、优先级队列等。与锁的关系线程成功获取锁后继续运行如果线程被抢占但没在等锁它仍在就绪队列中。存放对象处于阻塞状态的线程正在等待某个事件/资源比如锁、I/O、信号量。作用当事件发生时比如锁被释放内核从等待队列中唤醒相应线程将其移入就绪队列。与锁的关系互斥锁实现中加锁失败并选择睡眠的线程会被挂到该锁的等待队列上。在互斥锁中的具体体现加锁失败线程 A 调用系统调用将自己从就绪队列中移除加入到互斥锁的等待队列。解锁时互斥锁持有者线程 B 释放锁内核从该锁的等待队列中取一个线程如线程 A将其状态改为就绪并放回全局就绪队列或某个 CPU 的就绪队列。调度时机之后调度器从就绪队列中选中线程 A它才能继续运行并重新尝试获取锁。3 锁 原理操作系统中锁的核心原理是通过硬件提供的原子操作结合数据结构和调度机制保证在同一时刻只有一个线程或进程能进入临界区。锁的实现可以分三个层面来理解硬件基础、核心算法、操作系统封装。3.1 1硬件基础原子操作锁机制的最底层必须依赖硬件提供的原子指令。所谓原子就是执行过程中不可打断。关键指令典型的如 Test-and-SetTAS测试并设置、Compare-and-SwapCAS比较并交换、Load-Linked / Store-ConditionalLL/SC链接加载/条件存储。工作原理以 Test-and-Set 为例它会原子地完成两步读取一个内存变量如锁标记的值然后将该变量设为1。在这两步之间不会被其他CPU核心或线程打断。为什么需要硬件只用高级语言如 if (flag 0) flag 1;是做不到原子的——可能在判断完 flag0 后、赋值前另一个线程也判断成功导致两个线程都认为自己拿到了锁。原子指令从根本上杜绝了这种竞争。3.1 自旋锁基于硬件原子操作可以直接实现最简单的锁——自旋锁。实现逻辑锁被一个整数变量表示0表示空闲1表示占用。加锁时线程不断循环执行原子指令如 Test-and-Set尝试将0改为1。如果返回旧值为0说明原先是空闲当前线程成功拿到锁。如果返回旧值为1说明锁被占用线程就继续循环“自旋”反复尝试。特点优点没有线程上下文切换的开销响应快。缺点如果锁被长时间占用自旋的线程会一直忙等忙等待浪费CPU时间片。3.2 互斥锁【操作系统封装】互斥锁 硬件原子操作 自旋短暂 等待队列 系统调用睡眠/唤醒3.2.1 加锁过程线程尝试获取锁假设线程 A 想要获取这个互斥锁。步骤 1快速路径——尝试原子加锁执行一个原子操作如 test_and_set 或 compare_and_swap试图把 lock_value 从 0 改为 1。如果成功旧值为 0设置 owner 当前线程ID。加锁完成线程 A 进入临界区。不进入后续任何系统调用开销极小。步骤 2慢速路径——锁已被占用原子操作失败旧值为 1说明别人比如线程 B持有锁。此时不会立即让线程 A 去睡觉而是会短时间自旋几十到几百个 CPU 周期反复尝试原子操作。为什么自旋 因为线程 B 可能很快释放锁比如执行几条指令就解锁自旋能避免进入内核的开销比睡眠唤醒轻量得多。如果自旋期间拿到了锁 → 直接返回。步骤 3自旋超时准备睡眠自旋若干次后仍没拿到锁 → 判断“锁可能会被持有较长时间”。线程 A 调用系统调用例如 Linux 的 futex 中的 FUTEX_WAIT陷入内核。步骤 4内核中的阻塞操作内核模式下的动作将当前线程 A 的状态从 “运行” 改为 “睡眠”准确说是“可中断睡眠”或“不可中断睡眠”。【为什么从运行改为睡眠因为没有拿到锁也就没有拿到资源需要阻塞等待获取锁拿资源阻塞状态的线程需要放到等待队列】把线程 A 的控制块task_struct加入到该互斥锁的等待队列 waitq 中通常是 FIFO 队列保证公平。调用调度器选择另一个就绪线程比如线程 C运行让出 CPU。【就绪线程C已经拿到了所有资源只需要获取到cpu控制权就可以直接运行避免了cpu资源的浪费】。此处的误解是以为线程C运行也需要该锁其实就绪队列的线程已获取到所有资源也就是说线程C是一个已获取到该锁或根本该锁没关系的一个就绪线程。此时线程 A 不再占用 CPU也不会被调度直到被唤醒。注意在进入睡眠前可能还需要二次检查锁的状态防止唤醒丢失但原理上是这样。在线程 A 自旋期间它仍然处于“运行”状态更准确说是“就绪/运行”状态正在 CPU 上执行指令。3.2.3 解锁过程线程释放锁假设线程 B 是当前锁的持有者它执行完临界区现在要解锁。步骤 1快速路径——原子释放线程 B 执行一个原子操作把 lock_value 从1 改回 0。如果此时等待队列为空解锁完成不需要进内核。步骤 2慢速路径——存在等待者原子释放前或释放后检查 waitq 是否非空。如果有等待的线程例如线程 A 在队列里那么调用系统调用如 futex 的 FUTEX_WAKE进入内核。或者在释放锁的代码中直接调用内核函数取决于实现。步骤 3内核中的唤醒操作内核模式下的动作从等待队列中取出一个或多个等待线程通常是队首的一个。将那个线程线程 A的状态从“睡眠”改为“就绪”或“运行”把它放回调度器的运行队列。通常不会立即抢占当前线程 B除非设置了高优先级而是等待下一次调度时机。但线程 A 已经可被调度了下一次 CPU 空闲时就会执行它。步骤 4被唤醒的线程重新竞争锁线程 A 从内核中的 futex_wait 系统调用返回回到用户态。它会再次尝试原子加锁回到加锁过程的步骤 1。注意如果线程 B 解锁后另一个线程 C 恰好也在自旋抢锁A 可能依然要排队或重试但通常等待队列保证了公平性例如唤醒 让队首优先拿锁。