《奔跑吧Linux内核（第2版）卷2：调试与案例分析》- 并发与同步知识点总结

oxlm_1

《奔跑吧Linux内核（第2版）卷2：调试与案例分析》- 并发与同步知识点总结 [复制链接]

本帖最后由 oxlm_1 于 2024-3-20 15:21 编辑

前言

本来想看完第一章后，以RTOS和Linux互斥锁机制之间的差异的角度来解析为何两种系统存在差异，RTOS是否有必要实现Linux这类复杂的锁机制。但阅读完后发现Linux锁机制因为迭代版本多，内容较为复杂，前置知识较多，因此改为写第一章使用角度的知识点总结。

原子操作
1. 原子变量定义

<include/linux/types.h>

typedef struct {
    int counter;
}atomic_t;

atomic_t类型的原子操作函数可以保证一个操作的原子性和完整性。而要原子的保证操作的完整性和原子性，通常需要“原子地”（不间断地）完成“读-修改-回写”机制，中间不能被打断。如果其他CPU同时对该原子变量进行操作，则会影响数据完整性。

原子操作函数

处理器必须提供原子操作地汇编指令来完成原子操作，如arm64处理器地cas，x86的cmpxchg指令等。

<include/asm-generic/atomic.h>

#define ATOMIC_INIT(i)    //将原子变量初始化为i
#define atomic_read(v)    //读取原子变量的值
#define atomic_set(v, i)   //设置原子变量v的值为i

// 不带返回值的原子操作
atomic_inc(v)  // 原子地增1
atomic_dev(v)  // 原子地减1
atomic_add(i, v)// 原子地给v加i
atomic_and(i, v) // 原子地给v和i做“与”操作
atomic_or(i, v)// 原子地给v和i做“或”操作
atomic_xor(i, v)// 原子地给v和i做“异或”操作

// 带返回值的原子操作
// 返回值为新值的原子操作
atomic_add_return(int i, atomic_t *v) // 原子地给v加i并返回v的新值
atomic_sub_return(int i，atomic_t *v) // 原子地给v减i并返回v的新值
atomic_inc_return(v) // 原子地给v加1并返回v的新值
atomic_dec_return(v) // 原子地给v减1并返回v的新值

//返回值为旧值的原子操作
atomic_fetch_add(int i, atomic_t *v) // 原子地给v加i并返回v的旧值
atomic_fetch_sub(int i，atomic_t *v) // 原子地给v减i并返回v的旧值
atomic_fetch_and(int i，atomic_t *v) // 原子地给v和i做与操作并返回v的旧值
atomic_fetch_or(int i，atomic_t *v) // 原子地给v和i做或操作并返回v的旧值
atomic_fetch_xor(int i，atomic_t *v) // 原子地给v和i做异或操作并返回v的旧值

//原子交换函数
atomic_cmpxchg(ptr, old, new) // 原子地比较ptr的值是否与old的值相等，若相等，则把new的值设置到ptr地址中，返回old的值
atomic_xchg(ptr, new) // 原子地把new的值设置到ptr地址中并返回ptr的原值
atomic_try_cmpxchg(ptr, old, new) // 与atomic_cmpxchg()函数类似，但返回值发生变化，防火一个bool值，用于判断cmpxchg()函数的返回值是否与old的值相等

//内嵌内存屏障原语的原子操作函数 
// {}代表前面出现的函数名
// 内存屏障相关知识，在《卷1》中有介绍
{}_relaxed  // 不内嵌内存屏障原语
{}_anquire  // 内置了加载-获取内存屏障原语
{}_release  // 内置了存储-释放内存屏障原语

自旋锁
自旋锁使用前提：1. 临界区不允许发生抢占
自旋锁的作用：实现一个忙时等待的锁
在中断上下文中可以毫不犹豫的使用自旋锁，如果临界区有睡眠、隐含睡眠的动作及内核接口函数，应避免选择自旋锁。
1. 经典自旋锁
  1. 最初版本的自旋锁
    由于只有一个锁标记表示锁是否被持有，在锁争用的情况下可能会导致高优先级的任务一直获取锁，而低优先级的任务长时间获取不到锁。
  2. 基于排队的自旋锁
    为了解决最初版本自旋锁的问题，将32字节的锁标记拆分为owner标记和next标记，owner标记表征当前自旋锁执行到的位置，而next自旋锁表示目前排队的任务所拿到的最大编号。当owner执行完毕后，owner加1，此时将锁传递为持有新owner值的任务。
2. MCS锁
  由于基于排队的自旋锁没法解决高速缓存行颠簸问题，因此设计了MCS锁。该锁实现的核心思想为：每个锁的申请者只能在本地CPU的变量上自旋，而不是全局的变量上。MCS锁本质上是一种基于链表结构的自旋锁。
3. 排队自旋锁（OSQ锁）
  MCS锁机制会导致spinlock数据结构变大，在内核中很多数据结构内嵌了spinlock数据结构，这些数据结构对大小很敏感，这导致了MCS锁机制一直没能在spinlock数据结构上应用，只能屈就于互斥锁和读写信号量。在Linux 4.2内核中，基于排队自旋锁机制比基于排队机制在性能方面高20%，特别是在锁征用激烈的场景下，文件系统的测试性能会有116%的提升。OSQ非常适用于NUMA架构的服务器，特别是又大量的CPU内核且锁争用激烈的场景。
信号量

信号量允许无数据时，进程进入睡眠状态，其适用于一些情况复杂、加锁时间比较长的应用场景，如内核与用户空间复杂的交互行为等。
信号量的定义结构如下：

<include/linux/semaphore.h>

struct semphore {
    raw_spinlock_t lock;
    unsigned int count;
    struct list_head wait_list;
};

从数据结构上看，信号量的本质是一个计数器count，当计数器为0时，消费端进入睡眠状态，直到生产端提升计数器计数时唤醒消费端处理消息。而wait_list表示的是当前在等待的消费者信息，lock则为保护count和wait_list数据准确性的锁。
信号量的使用方法：

<include/linux/semaphore.h>

static inline void sema_init(struct semaphore *sem, int val) // 将信号量sem初始化为val

// down函数 (消费者)
void down(struct semaphore *sem)  // 在争用信号量失败是不进入可中断的睡眠状态
int down_interruptible(struct semaphore *sem) // 在争用信号量失败是进入可中断的睡眠状态
int down_killable(struct semaphore *sem)
int down_trylock(struct semaphore *sem) // 返回0，表示成功获取锁；返回1，则表示获取锁失败
int down_timeout(struct semaphore *sem, long jiffies)

// up函数 （生产者）
void up(struct semaphore *sem)

使用场景：无法使用互斥锁的场景下使用

互斥锁

从功能理解上，互斥锁是个特殊的信号量（计数值只有0和1两个值的信号量）。而互斥锁引入的缘由，也是因为互斥锁相对于信号量更为简单轻便，在锁争用激烈的测试场景下，互斥锁比信号量执行速度更快，可扩展性更好，且数据结构定义比信号量小。
互斥锁的定义及使用：

<include/linux/mutex.h>

struct mutex {
    atomic_long_t owner; // 0表示未被持有，非0值则表示锁持有者的task_struct指针的值。其低三位有特殊含义：
                         // #define MUTEX_FLAG_WAITERS 0x01 // 表示互斥锁的等待队列里有等待着，解锁的时候必须唤醒这些等候的进程
                         // #define MUTEX_FLAG_HANDOFF 0x02 // 对互斥锁的等待队列中的第一个等待着会设置这个标志位，锁持有这在解锁时把锁直接传递给第一个等待者
                         // #define MUTEX_FLAG_PICKUP 0x04 // 表示锁的传递已经完成
                         // #define MUTEX_FLAGS 0x07
    spinlock_t wait_lock;  // 用于保护wait_list睡眠等待队列
#ifdef CONFIG_MUTEX_SPIN_ON_OWNER
    struct optimistic_spin_queue osq; // 当发现锁持有者正在临界区执行并且没有高优先级的进程要调度时，当前进程坚信锁持有者会很快离开临界区并释放锁，因此与其睡眠
                                      // 等待不如乐观自旋等待，以减少睡眠唤醒的开销
#endif
    struct list_head wait_list;
};

//初始化
void mutex_init(struct mutex *lock, const char *name, struct lock_class_key *key)

#define DEFINE_MUTEX(mutexname) \
    struct mutex mutexname = __MUTEX_INITIALIZER(mutexname)
    
#define __MUTEX_INITIALIZER(lockname) \
    {.owner = ATOMIC_LONG_INIT(0) \
    , .wait_lock = __SPIN_LOCK_UNLOCKED(lockname.wait_lock) \
    , .wait_list = LIST_HEAD_INIT(lockname.wait_list) }
    
// 获取锁
void __sched mutex_lock(struct mutex *lock)

// 释放锁
void __sched mutex_unlock(struct mutex *lock)

互斥锁使用场景：

同一时刻只有一个线程可以持有互斥锁
只有锁持有者可以解锁
不允许递归地加锁和解锁
当进程持有互斥锁时，进程不可退出
互斥锁必须使用官方的接口函数来初始化
互斥锁可以睡眠，因此不允许在中断处理程序或者中断上下部（tasklet、定时器等）中使用

读写锁
信号量有一个明显的缺点，没有区分临界区的读写属性。读写锁通常允许多个线程并发地读访问临界区，但写访问只限制一个线程。读写锁能有效地提高并发性，在多处理器系统中允许有多个读者同时访问共享资源，但写者是排他性的。
读写锁具有以下特性：
- 允许多个读者同时进入临界区，但同一时刻写者不能进入
- 同一时刻只允许一个写者进入临界区
- 读者和写者不能同时进入临界区
1. 读写自旋类型

<include/linux/rwlock_types.h>

typedef struct {
    arch_rwlock_t raw_lock;
}rw_lock_t;

<include/asm-generic/qrwlock_types.h>

typedef struct qrwlock {
    union {
          atomic_t cnts;
          struct {
              u8 wlocked;
              u8 __lstate[3];          
          };
    };
    arch_apinlock_t wait_lock;
} arch_rwlock_t;

// 常用函数：
rwlock_init() // 初始化rwlock
write_lock()  // 申请写者锁
write_unlock()// 释放写者锁
read_lock()   // 申请读者锁
read_unlock() // 释放读者锁
read_lock_irq()//关闭中断并申请读者锁
write_lock_irq()//关闭中断并申请写者锁
write_unlock_irq()// 打开终端并释放写者锁

读写信号量

<include/linux/rwsem.h>

struct rw_semaphore {
    long count;//表示读写信号量的计数
               // 0x0000 0000:初始化值，表示没有读者和写者
               // 0x0000 000X:表示有X个活跃的读者或者正在申请的读者，没有写者干扰
               // 0xFFFF 000X:表示有可能有X个活跃读者，还有写者正在等待；或者表示有一个写者持有锁，还有多个读者在等待
               // 0xFFFF 0001:表示当前只有一个活跃的写者；或者表示一个活跃或者申请中的读者，还有写者正在睡眠等待
               // 0xFFFF 0000:表示WAITING_BIAS，有读者或者写者正在等待，但是它们都没成功获取锁
    struct list_head wait_list; // 用于管理所有在该信号量上睡眠的进程，没有成功获取锁的进程会睡眠在这个链表中
    raw_spinlock_t wait_lock; // 用于实现对count变量的原子操作和保护
#ifdef CONFIG_RWSEM_SPIN_ON_OWNER
    struct optimistic_spin_queue osq;
    struct task_struct *owner; //写者获取锁时，只想锁持有者的task_struct数据结构
#endif
};

//常用接口
void down_read(struct rw_semaphore *sem) //申请读者锁，若一个进程持有读者锁，则允许继续申请多个读者锁，申请写者锁则需要等待
void down_write(struct rw_semaphore *sem)//申请写者锁，若一个进程持有写者锁，则第二个进程申请写者锁则需自旋等待，申请读者锁则需等待
void up_write(struct rw_semaphore *sem)//释放写者锁，若等待队列中第一个成员是写者，则唤醒该写者，否则，唤醒排在等待队列中最前面连续的几个读者
void up_read(struct rw_semaphore *sem)//释放读者锁，若等待队列中第一个成员是写者，则唤醒该写者，否则，唤醒排在等待队列中最前面连续的几个读者

RCU

RCU实现的目标：读者线程没有同步开销，或者说同步开销变得很小，甚至可以忽略不计，不需要额外的锁，不需要使用原子操作指令和内存屏障指令，即可畅通无阻地访问；而把需要同步地任务交给写者线程，写者线程等待所有读者线程完成后才会把旧数据销毁。

//常用接口
rcu_read_lock()/rcu_read_ublock() // 组成一个RCU读者临界区
rcu_dereference() //获取被RCU保护地指针，读者线程要访问RCU保护地共享数据，需要使用该函数创建一个新指针，并且只想被RCU保护的指针
rcu_assign_pointer() //通常用于写者线程。在写者线程完成新数据的修改后，调用该接口可以让被RCU保护的指针指向新创建的数据，用RCU的术语是发布了更新后的数据
synchronize_rcu() //同步等待所有现存的读访问完成
call_rcu() //注册一个回调函数，当所有现存的读访问完成后，调用这个回调函数销毁旧数据

内核中锁机制的特点和使用规则

锁机制	特点	使用规则
原子操作	使用处理器的原子指令，开销小	临界区的数据变量、位等简单的数据结构
内存屏障	使用处理器的内存屏障指令或GCC的屏障指令	读写指令时序的调整
自旋锁	自旋等待	中断上下文，短期持有锁，不可递归，临界区不可睡眠
信号量	可睡眠的锁	可长时间持有锁
读写信号量	可睡眠的锁，多个读者可同时持有锁，同一个时刻只能有一个写者，读者和写者不能同时存在	程度员定出临界区后读/写属性才有作用
互斥锁	可睡眠的互斥锁，比信号量快速和简洁，实现自旋等待机制	同一时刻只有一个线程可持有互斥锁，由锁持有者负责解锁，即同一个上下文中解锁，不能递归持有锁，不适合内核和用户空间复杂的同步场景
RCU	读者持有锁没有开销，多个读者和写者可同时共存，写者必须等待所有读者离开临界区后才能销毁相关数据	受保护资源必须通过指针访问，如链表等

相关代码详解

书中对以上各个模块的相关代码逻辑以及版本迭代过程有详细讲解，但受限于版面，涉及到linux内核源码部分，需自行查阅源码。

源码路径:文件列表 - runninglinuxkernel_5.0/runninglinuxkernel_5.0 - 公开仓库 (coding.net)

《奔跑吧Linux内核（第2版）卷2：调试与案例分析》- 并发与同步 知识点总结 [复制链接]

《奔跑吧Linux内核（第2版）卷2：调试与案例分析》- 并发与同步知识点总结 [复制链接]