一、线程为什么需要互斥同一进程中的多个线程共享进程的地址空间因此多个线程可能同时访问同一份数据。例如int ticket 100;如果创建多个线程共同执行售票逻辑if (ticket 0) { printf(sell ticket:%d\n, ticket); ticket--; }多个线程都会访问和修改同一个ticket。如果这些线程的执行过程发生交叉就可能造成数据不一致。因此在学习互斥锁之前需要先理解几个基本概念。讲义首先给出了共享资源、临界资源、临界区、互斥和原子性的概念。1. 共享资源可以被多个执行流共同访问的资源就是共享资源。例如int ticket 100;多个线程都可以访问ticket所以ticket是共享资源。2. 临界资源需要受到保护、不能被多个线程随意并发访问的共享资源称为临界资源。例如售票程序中的ticket就是临界资源。3. 临界区线程中访问临界资源的那部分代码称为临界区。例如if (ticket 0) { printf(ticket %d\n, ticket); ticket--; }这段代码访问和修改了ticket所以它属于临界区。简单记ticket ↓ 临界资源 访问 ticket 的代码 ↓ 临界区4. 互斥互斥指的是同一时刻只允许一个执行流进入临界区访问临界资源。例如线程1 ──→ 进入临界区 线程2 ──→ 等待 线程3 ──→ 等待 线程4 ──→ 等待需要特别注意互斥并不是让整个程序变成单线程而只是保证临界区同一时刻只能由一个线程执行。5. 原子性原子操作指的是一个操作在执行过程中不能被其他执行流看到“执行一半”的状态。简单理解要么完全没执行 要么已经全部执行完成不存在中间状态。二、为什么抢票程序会出问题先看没有加锁的版本int ticket 100; void* route(void* arg) { char* id (char*)arg; while (true) { if (ticket 0) { usleep(1000); printf(%s sells ticket:%d\n, id, ticket); ticket--; } else { break; } } return nullptr; }创建多个线程同时运行后可能出现thread 4 sells ticket:1 thread 2 sells ticket:0 thread 1 sells ticket:-1 thread 3 sells ticket:-2讲义中的抢票实验就出现了票数变成0、-1、-2的情况。问题的关键就在ticket--;看起来只有一行但它并不是原子操作。三、ticket--为什么不是原子的从底层汇编角度看ticket--大致可以分成三步mov ticket, %eax sub $1, %eax mov %eax, ticket分别对应1. load 从内存读取 ticket 到寄存器 2. update 寄存器中的值减 1 3. store 把结果重新写回内存讲义也正是通过load → update → store三个步骤说明--ticket不是原子操作。所以 CPU 完全可能在这三步之间发生线程切换。假设ticket 1线程 A读取 ticket 1此时 CPU 把 A 切走。线程 B 开始运行也读取ticket 1于是线程A认为还有1张票 线程B也认为还有1张票最终两个线程都可能执行售票。问题的本质就是多个线程对共享数据的操作发生了交叉。四、为什么if(ticket 0)也没用有人可能会觉得if (ticket 0) { ticket--; }不是已经检查过了吗但是if (ticket 0)和ticket--;并不是一个不可分割的整体。例如线程A 判断 ticket 0 ↓ 成立 ↓ CPU切换 线程B 判断 ticket 0 ↓ 成立 ↓ 卖票并 ticket-- CPU重新切回线程A 线程A继续卖票因此判断时条件成立不代表真正执行修改时条件仍然成立。所以售票中的判断 输出 ticket--必须作为一个整体进行保护。五、使用 mutex 实现线程互斥Linux pthread 库提供了互斥量pthread_mutex_t基本使用结构就是pthread_mutex_lock(mutex); // 临界区 pthread_mutex_unlock(mutex);多个线程竞争同一把锁时mutex │ ┌────────┼────────┐ ↓ ↓ ↓ thread1 thread2 thread3 │ 抢锁成功 │ ↓ 临界区 thread2、thread3等待当一个线程已经进入临界区后其他线程就不能再进入。讲义总结互斥要求时指出临界区执行过程中不能让其他线程进入多个线程同时申请进入临界区时只能有一个线程成功。Linux 中通过互斥量完成这种保护。六、pthread mutex基本接口1. 定义互斥量pthread_mutex_t mutex;2. 初始化动态初始化pthread_mutex_init(mutex, nullptr);完整接口int pthread_mutex_init( pthread_mutex_t* mutex, const pthread_mutexattr_t* attr );学习阶段第二个参数一般使用nullptr也可以静态初始化pthread_mutex_t mutex PTHREAD_MUTEX_INITIALIZER;这两种方式都是讲义介绍的标准初始化方法。3. 加锁pthread_mutex_lock(mutex);如果锁当前没有被其他线程持有锁空闲 ↓ 当前线程抢锁成功 ↓ 进入临界区如果锁已经被其他线程持有锁被占用 ↓ 当前线程抢锁失败 ↓ 阻塞等待讲义指出如果 mutex 已经被其他线程锁定pthread_mutex_lock可能使当前线程进入阻塞状态等待锁被释放。4. 解锁pthread_mutex_unlock(mutex);表示当前线程已经完成临界区操作可以让其他线程继续竞争这把锁。5. 销毁pthread_mutex_destroy(mutex);一般在线程全部结束并且确定后面不会继续使用该 mutex 时销毁。七、使用mutex改造抢票程序核心代码如下int ticket 100; pthread_mutex_t mutex; void* route(void* arg) { const char* id static_castconst char*(arg); while (true) { pthread_mutex_lock(mutex); if (ticket 0) { usleep(1000); printf(%s sells ticket:%d\n, id, ticket); ticket--; pthread_mutex_unlock(mutex); } else { pthread_mutex_unlock(mutex); break; } } return nullptr; }整个过程lock ↓ 判断 ticket ↓ 售票 ↓ ticket-- ↓ unlock讲义中的改进版本也是通过这种方式保护整个售票临界区。这里有一个很重要的细节else { pthread_mutex_unlock(mutex); break; }不能写成else { break; }因为在执行break之前当前线程仍然持有 mutex。如果直接退出线程A获得锁 ↓ 发现没票 ↓ 直接break ↓ 线程退出 ↓ 锁没有释放 ↓ 其他线程一直抢不到锁所以要记住成功 lock 以后最终一定要有对应的 unlock。八、加锁以后线程还能被CPU切走吗当然可以。例如pthread_mutex_lock(mutex); ticket--; pthread_mutex_unlock(mutex);假设线程 A 获得 mutex线程A获得锁 ↓ 开始执行临界区 ↓ CPU把A切走这时候线程 B 开始运行并调用pthread_mutex_lock(mutex);但是 mutex 仍然属于 A因此线程B抢锁失败 ↓ 等待等 A 再次被调度线程A继续运行 ↓ 完成临界区 ↓ unlockB 才有机会继续竞争锁。因此mutex 不是禁止线程调度。mutex 真正保证的是即使持锁线程被 CPU 切换出去其他线程也不能进入同一个临界区。九、为什么锁本身必须依赖原子操作假设我们自己设计一把锁mutex 1锁空闲 mutex 0锁被占用然后if (mutex 1) { mutex 0; }看起来似乎可以抢锁。实际上还是不安全。例如mutex 1 线程A 线程B │ 发现mutex1 发现mutex1 │ mutex0 mutex0两个线程最终都认为我获得锁了问题在于检查 mutex和修改 mutex仍然是两个独立操作。所以锁最重要的一步是“检查锁状态”和“修改锁状态”必须一次性完成。这就需要 CPU 提供原子指令。十、exchange / xchg如何实现互斥讲义介绍了利用swap/exchange原子交换指令实现 mutex 的基本思想。假设mutex 1锁空闲 mutex 0锁被占用简化后的加锁伪代码lock: movb $0, %al xchgb %al, mutex if (%al 0) return 0; 挂起等待; goto lock;首先movb $0, %al表示AL 0然后xchgb %al, mutex原子交换AL 和 mutex第一个线程抢锁原来AL 0 mutex 1交换后AL 1 mutex 0AL 1说明 mutex 原来处于空闲状态因此当前线程抢锁成功同时mutex 0表示锁已经被占用。第二个线程抢锁第二个线程同样先执行AL 0但是现在mutex 0交换AL 0 mutex 0于是AL 0说明这把锁之前就已经被其他线程持有。所以抢锁失败 ↓ 等待多个线程竞争时mutex 1 │ 原子 xchg │ ┌──────────┼──────────┐ ↓ ↓ ↓ thread1 thread2 thread3 │ │ │ 成功 失败 失败 │ mutex 0 │ ↓ 临界区所以互斥锁底层最核心的一点就是使用原子操作一次性完成“检查锁状态 修改锁状态”。这样无论多少线程同时竞争也只有一个线程能够成功。十一、为什么unlock可以直接释放锁释放锁时不需要再次竞争。因为执行 unlock 的线程本身已经持有这把锁。所以只需要把mutex 0恢复成mutex 1例如movb $1, mutex过程线程持有mutex ↓ 完成临界区 ↓ mutex 1 ↓ 锁重新空闲 ↓ 唤醒等待线程需要注意被唤醒的线程并不是直接获得锁。它只是重新进入lock ↓ xchg ↓ 重新竞争mutex因此lock负责竞争锁unlock负责释放锁。另外同一个临界资源如果在多个地方被访问都应该遵守同一套加锁规则否则仍然可能发生数据竞争。十二、使用RAII管理互斥锁使用 pthread 时我们经常手动写pthread_mutex_lock(mutex); // 临界区 pthread_mutex_unlock(mutex);最大的风险就是忘记 unlock。例如pthread_mutex_lock(mutex); if (error) { return nullptr; // 忘记解锁 } pthread_mutex_unlock(mutex);因此可以把 mutex 封装起来。讲义中首先封装了Mutex类再通过LockGuard实现 RAII 风格的锁管理。例如class LockGuard { public: LockGuard(Mutex mutex) : _mutex(mutex) { _mutex.Lock(); } ~LockGuard() { _mutex.Unlock(); } private: Mutex _mutex; };使用LockGuard guard(mutex);创建对象时构造函数 ↓ Lock()对象离开作用域时析构函数 ↓ Unlock()这就是 RAII利用对象生命周期自动管理资源。这样即使return; break;提前离开作用域guard的析构函数仍然会自动调用从而释放 mutex。十三、C11中的标准互斥锁C11 已经提供了#include mutex std::mutex mutex;以及std::lock_guardstd::mutex例如std::mutex mutex; void func() { std::lock_guardstd::mutex guard(mutex); // 临界区 }执行过程创建 guard ↓ 自动 lock ↓ 执行临界区 ↓ 离开作用域 ↓ guard 析构 ↓ 自动 unlock互斥题分析第一题if中应该判断是否有锁即lockfalse第二题: 左边swap只有一条语句交换具有原子性右边有3条语句实现每一条语句在实现时都有可能被其他线程切换走不具备原子性所以不能
一、线程为什么需要互斥同一进程中的多个线程共享进程的地址空间因此多个线程可能同时访问同一份数据。例如int ticket 100;如果创建多个线程共同执行售票逻辑if (ticket 0) { printf(sell ticket:%d\n, ticket); ticket--; }多个线程都会访问和修改同一个ticket。如果这些线程的执行过程发生交叉就可能造成数据不一致。因此在学习互斥锁之前需要先理解几个基本概念。讲义首先给出了共享资源、临界资源、临界区、互斥和原子性的概念。1. 共享资源可以被多个执行流共同访问的资源就是共享资源。例如int ticket 100;多个线程都可以访问ticket所以ticket是共享资源。2. 临界资源需要受到保护、不能被多个线程随意并发访问的共享资源称为临界资源。例如售票程序中的ticket就是临界资源。3. 临界区线程中访问临界资源的那部分代码称为临界区。例如if (ticket 0) { printf(ticket %d\n, ticket); ticket--; }这段代码访问和修改了ticket所以它属于临界区。简单记ticket ↓ 临界资源 访问 ticket 的代码 ↓ 临界区4. 互斥互斥指的是同一时刻只允许一个执行流进入临界区访问临界资源。例如线程1 ──→ 进入临界区 线程2 ──→ 等待 线程3 ──→ 等待 线程4 ──→ 等待需要特别注意互斥并不是让整个程序变成单线程而只是保证临界区同一时刻只能由一个线程执行。5. 原子性原子操作指的是一个操作在执行过程中不能被其他执行流看到“执行一半”的状态。简单理解要么完全没执行 要么已经全部执行完成不存在中间状态。二、为什么抢票程序会出问题先看没有加锁的版本int ticket 100; void* route(void* arg) { char* id (char*)arg; while (true) { if (ticket 0) { usleep(1000); printf(%s sells ticket:%d\n, id, ticket); ticket--; } else { break; } } return nullptr; }创建多个线程同时运行后可能出现thread 4 sells ticket:1 thread 2 sells ticket:0 thread 1 sells ticket:-1 thread 3 sells ticket:-2讲义中的抢票实验就出现了票数变成0、-1、-2的情况。问题的关键就在ticket--;看起来只有一行但它并不是原子操作。三、ticket--为什么不是原子的从底层汇编角度看ticket--大致可以分成三步mov ticket, %eax sub $1, %eax mov %eax, ticket分别对应1. load 从内存读取 ticket 到寄存器 2. update 寄存器中的值减 1 3. store 把结果重新写回内存讲义也正是通过load → update → store三个步骤说明--ticket不是原子操作。所以 CPU 完全可能在这三步之间发生线程切换。假设ticket 1线程 A读取 ticket 1此时 CPU 把 A 切走。线程 B 开始运行也读取ticket 1于是线程A认为还有1张票 线程B也认为还有1张票最终两个线程都可能执行售票。问题的本质就是多个线程对共享数据的操作发生了交叉。四、为什么if(ticket 0)也没用有人可能会觉得if (ticket 0) { ticket--; }不是已经检查过了吗但是if (ticket 0)和ticket--;并不是一个不可分割的整体。例如线程A 判断 ticket 0 ↓ 成立 ↓ CPU切换 线程B 判断 ticket 0 ↓ 成立 ↓ 卖票并 ticket-- CPU重新切回线程A 线程A继续卖票因此判断时条件成立不代表真正执行修改时条件仍然成立。所以售票中的判断 输出 ticket--必须作为一个整体进行保护。五、使用 mutex 实现线程互斥Linux pthread 库提供了互斥量pthread_mutex_t基本使用结构就是pthread_mutex_lock(mutex); // 临界区 pthread_mutex_unlock(mutex);多个线程竞争同一把锁时mutex │ ┌────────┼────────┐ ↓ ↓ ↓ thread1 thread2 thread3 │ 抢锁成功 │ ↓ 临界区 thread2、thread3等待当一个线程已经进入临界区后其他线程就不能再进入。讲义总结互斥要求时指出临界区执行过程中不能让其他线程进入多个线程同时申请进入临界区时只能有一个线程成功。Linux 中通过互斥量完成这种保护。六、pthread mutex基本接口1. 定义互斥量pthread_mutex_t mutex;2. 初始化动态初始化pthread_mutex_init(mutex, nullptr);完整接口int pthread_mutex_init( pthread_mutex_t* mutex, const pthread_mutexattr_t* attr );学习阶段第二个参数一般使用nullptr也可以静态初始化pthread_mutex_t mutex PTHREAD_MUTEX_INITIALIZER;这两种方式都是讲义介绍的标准初始化方法。3. 加锁pthread_mutex_lock(mutex);如果锁当前没有被其他线程持有锁空闲 ↓ 当前线程抢锁成功 ↓ 进入临界区如果锁已经被其他线程持有锁被占用 ↓ 当前线程抢锁失败 ↓ 阻塞等待讲义指出如果 mutex 已经被其他线程锁定pthread_mutex_lock可能使当前线程进入阻塞状态等待锁被释放。4. 解锁pthread_mutex_unlock(mutex);表示当前线程已经完成临界区操作可以让其他线程继续竞争这把锁。5. 销毁pthread_mutex_destroy(mutex);一般在线程全部结束并且确定后面不会继续使用该 mutex 时销毁。七、使用mutex改造抢票程序核心代码如下int ticket 100; pthread_mutex_t mutex; void* route(void* arg) { const char* id static_castconst char*(arg); while (true) { pthread_mutex_lock(mutex); if (ticket 0) { usleep(1000); printf(%s sells ticket:%d\n, id, ticket); ticket--; pthread_mutex_unlock(mutex); } else { pthread_mutex_unlock(mutex); break; } } return nullptr; }整个过程lock ↓ 判断 ticket ↓ 售票 ↓ ticket-- ↓ unlock讲义中的改进版本也是通过这种方式保护整个售票临界区。这里有一个很重要的细节else { pthread_mutex_unlock(mutex); break; }不能写成else { break; }因为在执行break之前当前线程仍然持有 mutex。如果直接退出线程A获得锁 ↓ 发现没票 ↓ 直接break ↓ 线程退出 ↓ 锁没有释放 ↓ 其他线程一直抢不到锁所以要记住成功 lock 以后最终一定要有对应的 unlock。八、加锁以后线程还能被CPU切走吗当然可以。例如pthread_mutex_lock(mutex); ticket--; pthread_mutex_unlock(mutex);假设线程 A 获得 mutex线程A获得锁 ↓ 开始执行临界区 ↓ CPU把A切走这时候线程 B 开始运行并调用pthread_mutex_lock(mutex);但是 mutex 仍然属于 A因此线程B抢锁失败 ↓ 等待等 A 再次被调度线程A继续运行 ↓ 完成临界区 ↓ unlockB 才有机会继续竞争锁。因此mutex 不是禁止线程调度。mutex 真正保证的是即使持锁线程被 CPU 切换出去其他线程也不能进入同一个临界区。九、为什么锁本身必须依赖原子操作假设我们自己设计一把锁mutex 1锁空闲 mutex 0锁被占用然后if (mutex 1) { mutex 0; }看起来似乎可以抢锁。实际上还是不安全。例如mutex 1 线程A 线程B │ 发现mutex1 发现mutex1 │ mutex0 mutex0两个线程最终都认为我获得锁了问题在于检查 mutex和修改 mutex仍然是两个独立操作。所以锁最重要的一步是“检查锁状态”和“修改锁状态”必须一次性完成。这就需要 CPU 提供原子指令。十、exchange / xchg如何实现互斥讲义介绍了利用swap/exchange原子交换指令实现 mutex 的基本思想。假设mutex 1锁空闲 mutex 0锁被占用简化后的加锁伪代码lock: movb $0, %al xchgb %al, mutex if (%al 0) return 0; 挂起等待; goto lock;首先movb $0, %al表示AL 0然后xchgb %al, mutex原子交换AL 和 mutex第一个线程抢锁原来AL 0 mutex 1交换后AL 1 mutex 0AL 1说明 mutex 原来处于空闲状态因此当前线程抢锁成功同时mutex 0表示锁已经被占用。第二个线程抢锁第二个线程同样先执行AL 0但是现在mutex 0交换AL 0 mutex 0于是AL 0说明这把锁之前就已经被其他线程持有。所以抢锁失败 ↓ 等待多个线程竞争时mutex 1 │ 原子 xchg │ ┌──────────┼──────────┐ ↓ ↓ ↓ thread1 thread2 thread3 │ │ │ 成功 失败 失败 │ mutex 0 │ ↓ 临界区所以互斥锁底层最核心的一点就是使用原子操作一次性完成“检查锁状态 修改锁状态”。这样无论多少线程同时竞争也只有一个线程能够成功。十一、为什么unlock可以直接释放锁释放锁时不需要再次竞争。因为执行 unlock 的线程本身已经持有这把锁。所以只需要把mutex 0恢复成mutex 1例如movb $1, mutex过程线程持有mutex ↓ 完成临界区 ↓ mutex 1 ↓ 锁重新空闲 ↓ 唤醒等待线程需要注意被唤醒的线程并不是直接获得锁。它只是重新进入lock ↓ xchg ↓ 重新竞争mutex因此lock负责竞争锁unlock负责释放锁。另外同一个临界资源如果在多个地方被访问都应该遵守同一套加锁规则否则仍然可能发生数据竞争。十二、使用RAII管理互斥锁使用 pthread 时我们经常手动写pthread_mutex_lock(mutex); // 临界区 pthread_mutex_unlock(mutex);最大的风险就是忘记 unlock。例如pthread_mutex_lock(mutex); if (error) { return nullptr; // 忘记解锁 } pthread_mutex_unlock(mutex);因此可以把 mutex 封装起来。讲义中首先封装了Mutex类再通过LockGuard实现 RAII 风格的锁管理。例如class LockGuard { public: LockGuard(Mutex mutex) : _mutex(mutex) { _mutex.Lock(); } ~LockGuard() { _mutex.Unlock(); } private: Mutex _mutex; };使用LockGuard guard(mutex);创建对象时构造函数 ↓ Lock()对象离开作用域时析构函数 ↓ Unlock()这就是 RAII利用对象生命周期自动管理资源。这样即使return; break;提前离开作用域guard的析构函数仍然会自动调用从而释放 mutex。十三、C11中的标准互斥锁C11 已经提供了#include mutex std::mutex mutex;以及std::lock_guardstd::mutex例如std::mutex mutex; void func() { std::lock_guardstd::mutex guard(mutex); // 临界区 }执行过程创建 guard ↓ 自动 lock ↓ 执行临界区 ↓ 离开作用域 ↓ guard 析构 ↓ 自动 unlock互斥题分析第一题if中应该判断是否有锁即lockfalse第二题: 左边swap只有一条语句交换具有原子性右边有3条语句实现每一条语句在实现时都有可能被其他线程切换走不具备原子性所以不能
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
