Lock

导言

在PTA开发时，其中的多线程加速经常要用锁来隔离资源和逻辑。

互斥与同步¶

在进程/线程并发执行的过程中，进程/线程之间存在协作的关系，例如有互斥、同步的关系。

为了实现进程/线程间正确的协作，操作系统必须提供实现进程协作的措施和方法，主要的方法有两种：

锁：加锁、解锁操作；
- 自旋锁(spin lock，忙等待锁)，基于原子操作指令 —— 测试和置位（Test-and-Set）指令
- 无等待锁：思想，把当前线程放入到锁的等待队列，然后执行调度程序
信号量：P、V 操作；

这两个都可以方便地实现进程/线程互斥，而信号量比锁的功能更强一些，它还可以方便地实现进程/线程同步。

常见问题¶

共享内存加锁之后释放锁，别的进程是如何知道锁释放的
1. 常用的方法是在共享内存中设置标志位或信号量等，并在共享内存中保证这个标志位或信号量只有在锁被释放时才会被更新。这样，其它进程可以通过轮询或者等待通知的方式来获取锁并开始修改共享内存，从而避免冲突。在共享内存中设置的标志位或信号量通常需要原子操作的支持，以确保并发修改时的正确性。
  1. 轮询：轮询是指线程反复检查某个条件是否成立，直到条件成立为止。在锁机制中，当一个线程持有锁时，其他线程会不断地轮询锁的状态，直到该锁被释放。这种方式的优点是实现简单，不需要额外的通知机制，缺点是占用CPU资源，效率较低。
  2. 等待通知：等待通知是指线程在某个条件不满足时挂起等待，当条件满足时由其他线程通知它继续执行。在锁机制中，当一个线程持有锁时，其他线程会进入等待状态，直到该锁被释放，此时其他线程会被通知并继续执行。这种方式的优点是占用CPU资源少，效率高，缺点是实现稍微复杂一些，需要额外的通知机制。
2. 另外，也可以使用一个中央锁服务器或者等待队列来管理锁，当一个进程获取锁时，会向中央锁服务器或等待队列发出请求，直到锁被成功获取，并在共享内存中记录锁的状态。当锁被释放时，中央锁服务器或等待队列会通知其它进程，并让其它进程开始自由修改共享内存。
如何保证操作的原子性
1. 操作系统提供的原子操作：一些操作系统会提供线程安全的原子操作接口，如Compare-And-Swap（CAS）等，它们能够确保指令的原子性，从而保证线程安全。
2. 事务：事务是指一组操作被视为一个不可分割的操作序列，要么全部执行成功，要么全部失败，具有原子性和一致性保证。常用于数据库操作等场景。
3. 锁机制：锁机制是一种常用的多线程同步机制，能够确保同一时刻只有一个线程（或进程）可以访问共享资源，从而保证原子性。
如何避免死锁
1. 避免使用多把锁并且同时持有多个锁。当需要持有多个锁时，可以通过加锁的顺序来避免死锁。如果所有可能的锁按照固定的顺序加锁，那么可以避免死锁。
2. 设置请求超时时间。当一个进程请求锁时，如果在超时时间内没有获得锁，可以释放之前持有的锁，并尝试重新获取。这样可以避免某一个进程一直持有锁而导致死锁。
3. 引入随机性。在获取锁的时候加入一些随机因素，让不同的程序在不同的时间获取锁。这样可以防止程序之间在自己的重试过程中的饥饿状态导致的死锁。

悲观锁¶

读写操作时，需要预先加锁，防止其他进程对资源的访问。
通过互斥锁（Mutex）和信号量（Semaphore）来实现。

乐观锁¶

在读取或修改共享资源时，并不先进行加锁操作，而是先读取资源，然后在对资源进行写操作时再进行一次比较，看看在这个时间间隔内是否发生了竞争。如果没有发生竞争，就可以将更新后的值写入共享资源，并结束操作；如果发生了竞争，则需要放弃本次更新，并进行重试
通过版本号的方式来实现。在共享资源中记录该资源的版本号，当一个进程想要修改共享资源时，需要先获取当前资源的版本号。如果当前版本号与自己保存的版本号相符，说明没有其他进程在这段时间内修改该资源，则可以进行写操作；如果版本号已经发生变化，则说明有其他进程对该资源进行了修改，当前进程需要放弃本次写操作，更新版本号，重新获取新的资源，并重新执行操作。

常见锁的优缺点和实现¶

自旋锁(spinlock)¶

多线程同步的一种忙等待锁，线程反复检查锁变量是否可用。

优点：避免了操作系统进程调度和线程切换，所以自旋锁通常适用在时间比较短的情况下。由于这个原因，操作系统的内核经常使用自旋锁。
缺点：如果长时间上锁的话，自旋锁会非常耗费性能，它阻止了其他线程的运行和调度
- 线程持有锁的时间越长，则持有该锁的线程将被 OS(Operating System) 调度程序中断的风险越大。
解决办法： TicketLock 是采用排队叫号的机制。CLHLock和MCSLock通过链表的方式避免了减少了处理器缓存同步，极大的提高了性能，区别在于CLHLock是通过轮询其前驱节点的状态，而MCS则是查看当前节点的锁状态。

互斥锁(mutex)¶

把自己阻塞起来（内核态和用户态之间的切换进入阻塞状态，可能上下文切换），等待重新调度请求。

互斥锁的实现
1. 软件实现：软件互斥锁需要借助操作系统提供的原子操作（如Compare-And-Swap，CAS）来实现优点是灵活性高缺点是性能较低，
2. CAS操作需要三个参数，内存地址A，期望值V，新值N。执行过程如下：
  - 读取内存地址A的原始值，保存在临时变量Value中
  - 比较Value和期待值V是否相等，如果相等则将内存地址A的值更新为新值N
  - 如果内存地址A的值已经被其他线程改变，则不进行更新操作
TAS（test and set）
- 一个TAS指令包括两个子步骤，把给定的内存地址设置为1，然后返回之前的旧值。
- 硬件实现：硬件互斥锁使用计算机硬件提供的特殊指令（如锁总线指令）来实现。当线程要获取锁时，它会发出一个锁总线指令，这个指令会占用系统总线，使得其他CPU无法读写内存。
  1. 当lock前缀指令执行时，它将锁定处理器总线，确保其他处理器无法同时访问同一内存区域，

代码实例：lock_guard

std::lock_guard<std::mutex> 是 C++ 标准库中的一个 RAII（Resource Acquisition Is Initialization）类，它用于在作用域内自动锁住一个 std::mutex，并在作用域结束时自动解锁。它可以帮助你避免手动管理锁，减少死锁和忘记解锁的风险。

用法

std::lock_guard 通过构造时自动锁住互斥量，并且在作用域结束时自动释放互斥量的锁。因此，你不需要手动调用 mutex.unlock()。只需要确保 lock_guard 的生命周期结束时，互斥量会被自动解锁。

示例代码

#include <iostream>
#include <mutex>
#include <thread>

std::mutex init_mutex_;  // 互斥量，防止多个线程同时初始化

void some_function() {
    // 创建一个 lock_guard 对象，自动锁住 init_mutex_
    std::lock_guard<std::mutex> lock(init_mutex_);

    // 在此作用域内，init_mutex_ 被锁定
    std::cout << "Doing some work inside the critical section...\n";

    // lock_guard 在作用域结束时会自动解锁 mutex
}

int main() {
    std::thread t1(some_function);
    std::thread t2(some_function);

    t1.join();
    t2.join();

    return 0;
}

解释

std::lock_guard<std::mutex> lock(init_mutex_);：
在这行代码中，lock_guard 对象被创建，并立即锁住 init_mutex_。
std::lock_guard 的构造函数会调用 mutex.lock() 来锁定互斥量。
lock 变量在作用域结束时自动销毁，这会触发析构函数 lock_guard::~lock_guard()，并自动解锁互斥量（即调用 mutex.unlock()）。
在 some_function 中，互斥量在整个函数内都是被锁定的，因此其他线程无法进入这段代码，避免了并发冲突。

为什么使用 std::lock_guard？

避免死锁：std::lock_guard 会自动解锁互斥量，减少了忘记解锁的风险。
简洁易懂：它为你管理锁，减少了显式的锁管理代码，使代码更简洁。
线程安全：当多个线程访问同一资源时，std::lock_guard 可以确保每次只有一个线程能够访问临界区，防止数据竞争。

适用场景

通常用于在函数、代码块中保护共享资源。它适合需要访问互斥量的代码块，但不想手动管理锁和解锁时。

代码实例：cv.wait 实现多线程的先后顺序

使用 std::thread 和 std::mutex + std::condition_variable

如果你希望在销毁环境的 Final 函数中等待某些子线程完成，可以使用 std::mutex 和 std::condition_variable 来同步子线程的完成状态。

示例代码：假设你有一个主线程（执行 Final 函数）和一个子线程，主线程需要等待子线程完成后才能销毁环境。

#include <iostream>
#include <thread>
#include <mutex>
#include <condition_variable>
#include <atomic>

std::mutex mtx;
std::condition_variable cv;
std::atomic<bool> thread_done{false};

void worker_thread() {
    std::this_thread::sleep_for(std::chrono::seconds(2)); // 模拟工作
    std::cout << "Worker thread finished." << std::endl;
    thread_done = true;  // 设置线程完成标志
    cv.notify_one();     // 通知主线程
}

void Final() {
    std::cout << "Final: Waiting for worker thread to finish..." << std::endl;

    // 等待子线程完成
    std::unique_lock<std::mutex> lock(mtx);
    cv.wait(lock, [] { return thread_done.load(); });
    // cv.wait(lock, [this] { return thread_done.load(); }); // in class

    std::cout << "Final: Worker thread finished. Proceeding with cleanup." << std::endl;
}

int main() {
    // 启动子线程
    std::thread t(worker_thread);

    // 在主线程中调用 Final
    Final();

    t.join();  // 等待子线程结束

    return 0;
}

关键点：

std::mutex mtx: 用于锁住条件变量，确保线程间的同步。
std::condition_variable cv: 用于实现主线程等待子线程的完成。
std::atomic<bool> thread_done: 用于标记子线程是否完成。
cv.wait(lock, condition): 主线程会等待子线程设置 thread_done 为 true，然后才会继续执行。

读写锁（ReadWrite Lock）¶

在读操作和写操作之间提供了更细粒度的同步控制。
多个线程可以同时获取读锁，但只有一个线程能够获取写锁。
- 读写锁有三种状态：读加锁状态、写加锁状态和不加锁状态
- 规则
- 当读写锁在写加锁模式下，任何试图对这个锁进行加锁的线程都会被阻塞，直到写进程对其解锁。
- 当读写锁在读加锁模式先，任何线程都可以对其进行读加锁操作，但是所有试图进行写加锁操作的线程都会被阻塞，直到所有的读线程都解锁。
缺点：当读者源源不断到来的时候，写者总是得不到读写锁，就会造成不公平的状态。
- 避免方法：当处于读模式的读写锁接收到一个试图对其进行写模式加锁操作时，便会阻塞后面对其进行读模式加锁操作的线程。这样等到已经加读模式的锁解锁后，写进程能够访问此锁保护的资源。
优点：
- 读写锁可以提高并发性，允许多个线程同时读取数据，而只有在需要修改数据时才会互斥。
- 适合对数据结构读的次数远远大于写的情况。

RCU（Read-Copy-Update）¶

对读写锁的一种改进。适用于读多写少场景的数据同步机制。
具体内容
- 并发读取数据不再需要加锁
- 写数据时，RCU机制通过创建一个副本来实现读写分离，确保在更新过程中没有线程正在读取旧的数据。
  - 写者修改数据前首先拷贝一个被修改元素的副本，然后在副本上进行修改，修改完毕后它向垃圾回收器注册一个回调函数以便在适当的时机执行真正的修改操作。
  - 读者必须提供一个信号给写者以便写者能够确定数据可以被安全地释放或修改的时机。
  - 有一个专门的垃圾收集器来探测读者的信号，一旦所有的读者都已经发送信号告知它们都不在使用被RCU保护的数据结构，垃圾收集器就调用回调函数完成最后的数据释放或修改操作。

概念题¶

RedStar (小红书) 笔试：图中有依赖的任务的，需要几个信号量来实现同步

如CSDN，有一条依赖线，需要一个信号量

在使用信号量(Semaphore)进行线程同步时,P(proberen)和V(verhogen)操作是非常重要的概念。

P操作（也称为Wait操作或Down操作）：
表示获取或等待信号量。
如果信号量内部计数值大于0,获取信号量并将计数值减1。
如果计数值等于0,线程将等待,直到计数值大于0。如果信号量的值大于0，表示资源可用，进程可以继续执行。如果信号量的值为0，表示资源不可用，P操作将阻塞（即等待）进程，直到该信号量的值大于0为止。

伪代码表示为：

P(S):
  while S <= 0:
    // 等待，直到S大于0
  S = S - 1

V操作（也称为Signal操作或Up操作）：
表示释放或增加信号量。
将信号量内部计数值加1。
如果存在等待线程,唤醒其中一个线程继续执行。

伪代码表示为：

V(S):
  S = S + 1

P和V操作保证了对共享资源的互斥访问。

一个线程使用P操作等待获取信号量,V操作在使用完共享资源后释放信号量。

信号量的值通常用于控制共享资源的数量，它可以是非负整数。当信号量被初始化为1时，称为二进制信号量（Binary Semaphore），因为它只能取0或1的值，通常用于实现互斥访问临界区。如果信号量的值大于1，称为计数信号量，可用于限制对资源的并发访问数。

在实际编程中，P操作和V操作通常是原子操作，确保在多线程或多进程环境下的正确同步和竞争条件的安全处理。

TP-link笔试:设计的程序在多个CPU上运行时，不应使用哪个实现多个CPU间的数据访问同步？

参考文献¶

https://www.cswiki.top/pages/f398f1/#blocking-i-o

原文链接：https://blog.csdn.net/qq_15437629/article/details/79116590

https://zhuanlan.zhihu.com/p/161936748