注册 登录
电子工程世界-论坛 返回首页 EEWORLD首页 频道 EE大学堂 下载中心 Datasheet 专题
oxlm_1的个人空间 https://home.eeworld.com.cn/space-uid-1076641.html [收藏] [复制] [分享] [RSS]
日志

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

已有 206 次阅读2024-3-20 15:10 |个人分类:读书笔记

  1. 前言
    本来想看完第一章后,以RTOS和Linux互斥锁机制之间的差异的角度来解析为何两种系统存在差异,RTOS是否有必要实现Linux这类复杂的锁机制。但阅读完后发现Linux锁机制因为迭代版本多,内容较为复杂,前置知识较多,因此改为写第一章使用角度的知识点总结。
  2. 原子操作
    1. 原子变量定义
      <include/linux/types.h>
      
      typedef struct {
          int counter;
      }atomic_t;

      atomic_t类型的原子操作函数可以保证一个操作的原子性和完整性。而要原子的保证操作的完整性和原子性,通常需要“原子地”(不间断地)完成“读-修改-回写”机制,中间不能被打断。如果其他CPU同时对该原子变量进行操作,则会影响数据完整性。
    2. 原子操作函数
      处理器必须提供原子操作地汇编指令来完成原子操作,如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  // 内置了存储-释放内存屏障原语

       

  3. 自旋锁
    自旋锁使用前提: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内核且锁争用激烈的场景。
  4. 信号量
    信号量允许无数据时,进程进入睡眠状态,其适用于一些情况复杂、加锁时间比较长的应用场景,如内核与用户空间复杂的交互行为等。
    信号量的定义结构如下:
    <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)

    使用场景:无法使用互斥锁的场景下使用
  5. 互斥锁
    从功能理解上,互斥锁是个特殊的信号量(计数值只有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)

    互斥锁使用场景:
    1. 同一时刻只有一个线程可以持有互斥锁
    2. 只有锁持有者可以解锁
    3. 不允许递归地加锁和解锁
    4. 当进程持有互斥锁时,进程不可退出
    5. 互斥锁必须使用官方的接口函数来初始化
    6. 互斥锁可以睡眠,因此不允许在中断处理程序或者中断上下部(tasklet、定时器等)中使用
  6. 读写锁
    信号量有一个明显的缺点,没有区分临界区的读写属性。读写锁通常允许多个线程并发地读访问临界区,但写访问只限制一个线程。读写锁能有效地提高并发性,在多处理器系统中允许有多个读者同时访问共享资源,但写者是排他性的。
    读写锁具有以下特性:
    1. 允许多个读者同时进入临界区,但同一时刻写者不能进入
    2. 同一时刻只允许一个写者进入临界区
    3. 读者和写者不能同时进入临界区
    4. 读写自旋类型
      <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()// 打开终端并释放写者锁

       

    5. 读写信号量
<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)//释放读者锁,若等待队列中第一个成员是写者,则唤醒该写者,否则,唤醒排在等待队列中最前面连续的几个读者

 

  1.    RCU

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

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

 

  1. 内核中锁机制的特点和使用规则
    锁机制 特点 使用规则
    原子操作 使用处理器的原子指令,开销小 临界区的数据变量、位等简单的数据结构
    内存屏障 使用处理器的内存屏障指令或GCC的屏障指令 读写指令时序的调整
    自旋锁 自旋等待 中断上下文,短期持有锁,不可递归,临界区不可睡眠
    信号量 可睡眠的锁 可长时间持有锁
    读写信号量 可睡眠的锁,多个读者可同时持有锁,同一个时刻只能有一个写者,读者和写者不能同时存在 程度员定出临界区后读/写属性才有作用
    互斥锁 可睡眠的互斥锁,比信号量快速和简洁,实现自旋等待机制 同一时刻只有一个线程可持有互斥锁,由锁持有者负责解锁,即同一个上下文中解锁,不能递归持有锁,不适合内核和用户空间复杂的同步场景
    RCU 读者持有锁没有开销,多个读者和写者可同时共存,写者必须等待所有读者离开临界区后才能销毁相关数据 受保护资源必须通过指针访问,如链表等
  2. 相关代码详
    书中对以上各个模块的相关代码逻辑以及版本迭代过程有详细讲解,但受限于版面,涉及到linux内核源码部分,需自行查阅源码。

本文来自论坛,点击查看完整帖子内容。

评论 (0 个评论)

facelist doodle 涂鸦板

您需要登录后才可以评论 登录 | 注册

热门文章