精华内容
下载资源
问答
  • Linux内核同步方式总结
    千次阅读
    2016-09-02 21:49:20

    有关linux内核同步的参考:

    memory barrier: http://www.wowotech.net/kernel_synchronization/memory-barrier.html


    阅读《深入理解linux内核》笔记

    内核抢占:如果进程正在执行内核函数时(即它在内核态运行时),允许发生内核切换(被替换的进程是正在执行内核函数的进程),这个内核就是抢占的。

    运行在内核态的进程可以自动放弃cpu,称为计划性进程切换,抢占式内核中,进程被迫放弃CPU,称为强制性进程切换。抢占内核的主要特点是:一个内核态运行的进程,可能在执行内核函数期间被另一个进程取代。

    内核抢占就会发生一种情况:两个或两个以上的交叉内核路径嵌套时,就可能出现竞争条件。还有一种情况,多核环境下,多个core上的进程同时进入内核,就会出现访问的竞争。因此内核需要同步。内核同步技术主要有以下方式:


    1.per-cpu 变量:将内核变量声明为per-cpu变量,它的数据结构是数组,系统的每个CPU对应数组中的一个元素,一个CPU只能修改自己对应的元素,不用担心竞争条件。per-cpu只能对来自不同CPU的并发访问提供保护,但对自身的异步函数(中断处理函数和可延迟函数)的访问不提供保护,需要同步原语

    2.原子操作(linux中有一个专门的atomic_t类型):操作在芯片级是原子的,原子操作必须以单个指令执行,中间不能中断,且避免其他的CPU访问同一存储器单元。

    3.优化屏障(optimization barrier)和内存屏障(memory barrier):现代编译器可能重新安排汇编语言指令的吮吸,CPU通常并行的执行多条指令,且可能重新安排内存访问,但是,当处理同步时,必须避免指令重新排序,如果放在同步原语之后的一条指令在同步原语之前被执行,就很糟糕!内存屏障:确保在原语之后的操作开始执行之前,原语之前的操作已经完成。mb(), smp_mb();

    简单的说,由于内存乱序以允许更好的性能,在某些情况下,需要内存屏障以强制保证内存顺序,否则将出现很糟糕的问题。

    程序在运行时内存实际的访问顺序和程序代码编写的访问顺序不一定一致,这就是内存乱序访问。内存乱序访问行为出现的理由是为了提升程序运行时的性能。内存乱序访问主要发生在两个阶段:

    1. 编译时,编译器优化导致内存乱序访问(指令重排)
    2. 运行时,多 CPU 间交互引起内存乱序访问

    Memory barrier 能够让 CPU 或编译器在内存访问上有序。一个 Memory barrier 之前的内存访问操作必定先于其之后的完成。Memory barrier 包括两类:

    1. 编译器 barrier
    2. CPU Memory barrier

    4.spin lock:当内核控制路径必须访问共享数据结构或进入临界区时,需要锁,spin lock的循环指令表示“忙等”,即使等待的内核控制路径无事可做,它也在CPU上保持运行

    5.读写spin lock:它的引入主要是为了增加内核的并发能力,只要没有内核路径对数据结构进行修改,读写spin lock允许多个内核控制路径同时读同一个数据结构。但是写者需要独占。

    6.顺序锁:读写spin lock中读者和写着有相同的优先级,当读者多的时候,可能出现一种情况,写着一直得不到服务,可能饥饿。引入顺序锁(seqlock),它与读写spin lock非常相似,但是它赋予写着较高的优先级。

    7.RCU(read-copy update):是为了保护在多数情况下被多个CPU读的数据结构而设计的另一种同步方式。RCU允许多个读者和写者并发执行,而且RCU不使用锁。但RCU的使用有限制:

    • RCU只能保护动态分配并通过指针引用的数据结构
    • 在被RCU保护的临界区中,任何内核控制路径都不能睡眠
    内核控制路径要读取被RCU保护的数据结构时,执行宏rcu_read_lock(),但是读者在完成对数据结构的读操作之前,是不能睡眠的,rcu读结束之后,调用宏rcu_read_unlock()标记临界区的结束。
    由于读者几乎不做任何事情来防止竞争条件的出现,所以写着必须多做一些。

    8.信号量

    更多相关内容
  • Linux内核同步机制

    2021-01-20 14:49:52
    Linux内核同步机制,挺复杂的一个东西,常用的有自旋锁,信号量,互斥体,原子操作,顺序锁,RCU,内存屏障等。这里说说它们的特点和基本用法。  自旋锁 :通用的 和读写的  特点:  1. 处理的时间很短。  2...
  • Linux内核同步操作详解,英文版,开发驱动必备。
  • Linux内核同步编程技术.doc
  • 浅析Linux内核同步机制(转)

    千次阅读 2018-07-30 23:50:19
     很早之前就接触过同步这个概念了,但是一直都很模糊,没有深入地学习了解过,近期有时间了,就花时间研习了一下《linux内核标准教程》和《深入linux设备驱动程序内核机制》这两本书的相关章节。...

    原文地址:https://blog.csdn.net/fzubbsc/article/details/37736683?utm_source=tuicool&utm_medium=referral

     很早之前就接触过同步这个概念了,但是一直都很模糊,没有深入地学习了解过,近期有时间了,就花时间研习了一下《linux内核标准教程》和《深入linux设备驱动程序内核机制》这两本书的相关章节。趁刚看完,就把相关的内容总结一下。为了弄清楚什么事同步机制,必须要弄明白以下三个问题:

     

    • 什么是互斥与同步?
    • 为什么需要同步机制?
    •  Linux内核提供哪些方法用于实现互斥与同步的机制?

     

    1、什么是互斥与同步?(通俗理解)

     

    • 互斥与同步机制是计算机系统中,用于控制进程对某些特定资源的访问的机制。
    • 同步是指用于实现控制多个进程按照一定的规则或顺序访问某些系统资源的机制。
    • 互斥是指用于实现控制某些系统资源在任意时刻只能允许一个进程访问的机制。互斥是同步机制中的一种特殊情况。
    • 同步机制是linux操作系统可以高效稳定运行的重要机制。

     

    2、Linux为什么需要同步机制?

            在操作系统引入了进程概念,进程成为调度实体后,系统就具备了并发执行多个进程的能力,但也导致了系统中各个进程之间的资源竞争和共享。另外,由于中断、异常机制的引入,以及内核态抢占都导致了这些内核执行路径(进程)以交错的方式运行。对于这些交错路径执行的内核路径,如不采取必要的同步措施,将会对一些关键数据结构进行交错访问和修改,从而导致这些数据结构状态的不一致,进而导致系统崩溃。因此,为了确保系统高效稳定有序地运行,linux必须要采用同步机制。

    3、Linux内核提供了哪些同步机制?

            在学习linux内核同步机制之前,先要了解以下预备知识:(临界资源与并发源)
            在linux系统中,我们把对共享的资源进行访问的代码片段称为临界区。把导致出现多个进程对同一共享资源进行访问的原因称为并发源。

            Linux系统下并发的主要来源有:

     

    • 中断处理:例如,当进程在访问某个临界资源的时候发生了中断,随后进入中断处理程序,如果在中断处理程序中,也访问了该临界资源。虽然不是严格意义上的并发,但是也会造成了对该资源的竞态。
    • 内核态抢占:例如,当进程在访问某个临界资源的时候发生内核态抢占,随后进入了高优先级的进程,如果该进程也访问了同一临界资源,那么就会造成进程与进程之间的并发。
    • 多处理器的并发:多处理器系统上的进程与进程之间是严格意义上的并发,每个处理器都可以独自调度运行一个进程,在同一时刻有多个进程在同时运行 。

     

    如前所述可知:采用同步机制的目的就是避免多个进程并发并发访问同一临界资源。 

    Linux内核同步机制:

    (1)禁用中断 (单处理器不可抢占系统)

            由前面可以知道,对于单处理器不可抢占系统来说,系统并发源主要是中断处理。因此在进行临界资源访问时,进行禁用/使能中断即可以达到消除异步并发源的目的。Linux系统中提供了两个宏local_irq_enable与 local_irq_disable来使能和禁用中断。在linux系统中,使用这两个宏来开关中断的方式进行保护时,要确保处于两者之间的代码执行时间不能太长,否则将影响到系统的性能。(不能及时响应外部中断)

    (2)自旋锁

    应用背景:自旋锁的最初设计目的是在多处理器系统中提供对共享数据的保护。

    自旋锁的设计思想:在多处理器之间设置一个全局变量V,表示锁。并定义当V=1时为锁定状态,V=0时为解锁状态。自旋锁同步机制是针对多处理器设计的,属于忙等机制。自旋锁机制只允许唯一的一个执行路径持有自旋锁。如果处理器A上的代码要进入临界区,就先读取V的值。如果V!=0说明是锁定状态,表明有其他处理器的代码正在对共享数据进行访问,那么此时处理器A进入忙等状态(自旋);如果V=0,表明当前没有其他处理器上的代码进入临界区,此时处理器A可以访问该临界资源。然后把V设置为1,再进入临界区,访问完毕后离开临界区时将V设置为0。

    注意:必须要确保处理器A“读取V,半段V的值与更新V”这一操作是一个原子操作。所谓的原子操作是指,一旦开始执行,就不可中断直至执行结束。

    自旋锁的分类:

    2.1、普通自旋锁

    普通自旋锁由数据结构spinlock_t来表示,该数据结构在文件src/include/linux/spinlock_types.h中定义。定义如下:

    typedef struct { raw_spinklock_t   raw_lock;
    
           #ifdefined(CONFIG_PREEMPT)  &&  defined(CONFIG_SMP)
    
                   unsigned int break_lock;
    
           #endif
    
    } spinlock_t;

    成员raw_lock:该成员变量是自旋锁数据类型的核心,它展开后实质上是一个Volatileunsigned类型的变量。具体的锁定过程与它密切相关,该变量依赖于内核选项CONFIG_SMP。(是否支持多对称处理器)

    成员break_lock:同时依赖于内核选项CONFIG_SMP和CONFIG_PREEMPT(是否支持内核态抢占),该成员变量用于指示当前自旋锁是否被多个内核执行路径同时竞争、访问。

    在单处理器系统下:CONFIG_SMP没有选中时,变量类型raw_spinlock_t退化为一个空结构体。相应的接口函数也发生了退化。相应的加锁函数spin_lock()和解锁函数spin_unlock()退化为只完成禁止内核态抢占、使能内核态抢占。

    在多处理器系统下:选中CONFIG_SMP时,核心变量raw_lock的数据类型raw_lock_t在文件中src/include/asm-i386/spinlock_types.h中定义如下:

    typedef struct {  volatileunsigned int slock;} raw_spinklock_t;

           从定义中可以看出该数据结构定义了一个内核变量,用于计数工作。当结构中成员变量slock的数值为1时,表示自旋锁处于非锁定状态,可以使用。否则,表示处于锁定状态,不可以使用。

    普通自旋锁的接口函数:

    spin_lock_init(lock)        //声明自旋锁是,初始化为锁定状态
    
    spin_lock(lock)             //锁定自旋锁,成功则返回,否则循环等待自旋锁变为空闲
    
    spin_unlock(lock)           //释放自旋锁,重新设置为未锁定状态
    
    spin_is_locked(lock)        //判断当前锁是否处于锁定状态。若是,返回1.
    
    spin_trylock(lock)          //尝试锁定自旋锁lock,不成功则返回0,否则返回1
    
    spin_unlock_wait(lock)      //循环等待,直到自旋锁lock变为可用状态。
    
    spin_can_lock(lock)         //判断该自旋锁是否处于空闲状态。 

    普通自旋锁总结:自旋锁设计用于多处理器系统。当系统是单处理器系统时,自旋锁的加锁、解锁过程分为别退化为禁止内核态抢占、使能内核态抢占。在多处理器系统中,当锁定一个自旋锁时,需要首先禁止内核态抢占,然后尝试锁定自旋锁,在锁定失败时执行一个死循环等待自旋锁被释放;当解锁一个自旋锁时,首先释放当前自旋锁,然后使能内核态抢占。

     

    2.2、自旋锁的变种

            在前面讨论spin_lock很好的解决了多处理器之间的并发问题。但是如果考虑如下一个应用场景:处理器上的当前进程A要对某一全局性链表g_list进行操作,所以在操作前调用了spin_lock获取锁,然后再进入临界区。如果在临界区代码当中,进程A所在的处理器上发生了一个外部硬件中断,那么这个时候系统必须暂停当前进程A的执行转入到中断处理程序当中。假如中断处理程序当中也要操作g_list,由于它是共享资源,在操作前必须要获取到锁才能进行访问。因此当中断处理程序试图调用spin_lock获取锁时,由于该锁已经被进程A持有,中断处理程序将会进入忙等状态(自旋)。从而就会出现大问题了:中断程序由于无法获得锁,处于忙等(自旋)状态无法返回;由于中断处理程序无法返回,进程A也处于没有执行完的状态,不会释放锁。因此这样导致了系统的死锁。即spin_lock对存在中断源的情况是存在缺陷的,因此引入了它的变种。

    spin_lock_irq(lock) 
    
    spin_unlock_irq(lock)

    相比于前面的普通自旋锁,它在上锁前增加了禁用中断的功能,在解锁后,使能了中断。

    2.3、读写自旋锁rwlock

    应用背景:前面说的普通自旋锁spin_lock类的函数在进入临界区时,对临界区中的操作行为不细分。只要是访问共享资源,就执行加锁操作。但是有时候,比如某些临界区的代码只是去读这些共享的数据,并不会改写,如果采用spin_lock()函数,就意味着,任意时刻只能有一个进程可以读取这些共享数据。如果系统中有大量对这些共享资源的读操作,很明显spin_lock将会降低系统的性能。因此提出了读写自旋锁rwlock的概念。对照普通自旋锁,读写自旋锁允许多个读者进程同时进入临界区,交错访问同一个临界资源,提高了系统的并发能力,提升了系统的吞吐量。

    读写自旋锁有数据结构rwlock_t来表示。定义在…/spinlock_types.h中

    读写自旋锁的接口函数:

    DEFINE_RWLOCK(lock)     //声明读写自旋锁lock,并初始化为未锁定状态
    
    write_lock(lock)        //以写方式锁定,若成功则返回,否则循环等待
    
    write_unlock(lock)      //解除写方式的锁定,重设为未锁定状态
    
    read_lock(lock)         //以读方式锁定,若成功则返回,否则循环等待
    
    read_unlock(lock)       //解除读方式的锁定,重设为未锁定状态

    读写自旋锁的工作原理:

             对于读写自旋锁rwlock,它允许任意数量的读取者同时进入临界区,但写入者必须进行互斥访问。一个进程要进行读,必须要先检查是否有进程正在写入,如果有,则自旋(忙等),否则获得锁。一个进程要进程写,必须要先检查是否有进程正在读取或者写入,如果有,则自旋(忙等)否则获得锁。即读写自旋锁的应用规则如下:

    (1)如果当前有进程正在写,那么其他进程就不能读也不能写。

    (2)如果当前有进程正在读,那么其他程序可以读,但是不能写。

    2.4、顺序自旋锁seqlock

    应用背景:顺序自旋锁主要用于解决自旋锁同步机制中,在拥有大量读者进程时,写进程由于长时间无法持有锁而被饿死的情况,其主要思想是:为写进程提高更高的优先级,在写锁定请求出现时,立即满足写锁定的请求,无论此时是否有读进程正在访问临界资源。但是新的写锁定请求不会,也不能抢占已有写进程的写锁定。

    顺序锁的设计思想:对某一共享数据读取时不加锁,写的时候加锁。为了保证读取的过程中不会因为写入者的出现导致该共享数据的更新,需要在读取者和写入者之间引入一个整形变量,称为顺序值sequence。读取者在开始读取前读取该sequence,在读取后再重新读取该值,如果与之前读取到的值不一致,则说明本次读取操作过程中发生了数据更新,读取操作无效。因此要求写入者在开始写入的时候更新。

    顺序自旋锁由数据结构seqlock_t表示,定义在src/include/linux/seqlcok.h

    顺序自旋锁访问接口函数:

    seqlock_init(seqlock)               //初始化为未锁定状态
    
    read_seqbgin()、read_seqretry()     //保证数据的一致性
    
    write_seqlock(lock)                 //尝试以写锁定方式锁定顺序锁
    
    write_sequnlock(lock)               //解除对顺序锁的写方式锁定,重设为未锁定状态。

    顺序自旋锁的工作原理:写进程不会被读进程阻塞,也就是,写进程对被顺序自旋锁保护的临界资源进行访问时,立即锁定并完成更新工作,而不必等待读进程完成读访问。但是写进程与写进程之间仍是互斥的,如果有写进程在进行写操作,其他写进程必须循环等待,直到前一个写进程释放了自旋锁。顺序自旋锁要求被保护的共享资源不包含有指针,因为写进程可能使得指针失效,如果读进程正要访问该指针,将会出错。同时,如果读者在读操作期间,写进程已经发生了写操作,那么读者必须重新读取数据,以便确保得到的数据是完整的。

     

    (3)信号量机制(semaphore)

    应用背景:前面介绍的自旋锁同步机制是一种“忙等”机制,在临界资源被锁定的时间很短的情况下很有效。但是在临界资源被持有时间很长或者不确定的情况下,忙等机制则会浪费很多宝贵的处理器时间。针对这种情况,linux内核中提供了信号量机制,此类型的同步机制在进程无法获取到临界资源的情况下,立即释放处理器的使用权,并睡眠在所访问的临界资源上对应的等待队列上;在临界资源被释放时,再唤醒阻塞在该临界资源上的进程。另外,信号量机制不会禁用内核态抢占,所以持有信号量的进程一样可以被抢占,这意味着信号量机制不会给系统的响应能力,实时能力带来负面的影响。

    信号量设计思想:除了初始化之外,信号量只能通过两个原子操作P()和V()访问,也称为down()和up()。down()原子操作通过对信号量的计数器减1,来请求获得一个信号量。如果操作后结果是0或者大于0,获得信号量锁,任务就可以进入临界区。如果操作后结果是负数,任务会放入等待队列,处理器执行其他任务;对临界资源访问完毕后,可以调用原子操作up()来释放信号量,该操作会增加信号量的计数器。如果该信号量上的等待队列不为空,则唤醒阻塞在该信号量上的进程。

    信号量的分类:

    3.1、普通信号量

    普通信号量由数据结构struct semaphore来表示,定义在src/inlcude/ asm-i386/semaphore.h中.

    信号量(semaphore)定义如下:

    <include/linux/semaphore.h>
    
    struct semaphore{
    
           spinlock_t       lock; //自旋锁,用于实现对count的原子操作
    
           unsigned int    count; //表示通过该信号量允许进入临界区的执行路径的个数
    
           struct list_head      wait_list; //用于管理睡眠在该信号量上的进程
    
    };

    普通信号量的接口函数:

    sema_init(sem,val)      //初始化信号量计数器的值为val
    
    int_MUTEX(sem)          //初始化信号量为一个互斥信号量
    
    down(sem)               //锁定信号量,若不成功,则睡眠在等待队列上
    
    up(sem)                 //释放信号量,并唤醒等待队列上的进程

    DOWN操作:linux内核中,对信号量的DOWN操作有如下几种:

    void down(struct semaphore *sem); //不可中断
    
    int down_interruptible(struct semaphore *sem);//可中断
    
    int down_killable(struct semaphore *sem);//睡眠的进程可以因为受到致命信号而被唤醒,中断获取信号量的操作。
    
    int down_trylock(struct semaphore *sem);//试图获取信号量,若无法获得则直接返回1而不睡眠。返回0则 表示获取到了信号量
    
    int down_timeout(struct semaphore *sem,long jiffies);//表示睡眠时间是有限制的,如果在jiffies指明的时间到期时仍然无法获得信号量,则将返回错误码。

    在以上四种函数中,驱动程序使用的最频繁的就是down_interruptible函数

    UP操作:LINUX内核只提供了一个up函数

    void up(struct semaphore *sem)

    加锁处理过程:加锁过程由函数down()完成,该函数负责测试信号量的状态,在信号量可用的情况下,获取该信号量的使用权,否则将当前进程插入到当前信号量对应的等待队列中。函数调用关系如下:down()->__down_failed()->__down.函数说明如下:

    down()功能介绍:该函数用于对信号量sem进行加锁,在加锁成功即获得信号的使用权是,直接退出,否则,调用函数__down_failed()睡眠到信号量sem的等待队列上。__down()功能介绍:该函数在加锁失败时被调用,负责将进程插入到信号量 sem的等待队列中,然后调用调度器,释放处理器的使用权。

    解锁处理过程:普通信号量的解锁过程由函数up()完成,该函数负责将信号计数器count的值增加1,表示信号量被释放,在有进程阻塞在该信号量的情况下,唤醒等待队列中的睡眠进程。 

    3.2读写信号量(rwsem)

    应用背景:为了提高内核并发执行能力,内核提供了读入者信号量和写入者信号量。它们的概念和实现机制类似于读写自旋锁。

    工作原理:该信号量机制使得所有的读进程可以同时访问信号量保护的临界资源。当进程尝试锁定读写信号量不成功时,则这些进程被插入到一个先进先出的队列中;当一个进程访问完临界资源,释放对应的读写信号量是,该进程负责将该队列中的进程按一定的规则唤醒。

    唤醒规则:唤醒排在该先进先出队列中队首的进程,在被唤醒进程为写进程的情况下,不再唤醒其他进程;在唤醒进程为读进程的情况下,唤醒其他的读进程,直到遇到一个写进程(该写进程不被唤醒)

    读写信号量的定义如下:

    <include/linux/rwsem-spinlock.h>
    
    sturct rw_semaphore{
    
           __s32      activity; //用于表示读者或写者的数量
    
           spinlock_t      wait_lock;
    
           struct list_head      wait_list;
    
    };

    读写信号量相应的接口函数

    读者up、down操作函数:

    void up_read(Sturct rw_semaphore *sem);
    
    void __sched down_read(Sturct rw_semaphore *sem);
    
    Int down_read_trylock(Sturct rw_semaphore *sem);

    写入者up、down操作函数:

    void up_write(Sturct rw_semaphore *sem);
    
    void __sched down_write(Sturct rw_semaphore *sem);
    
    int down_write_trylock(Sturct rw_semaphore *sem);

    3.3、互斥信号量

    在linux系统中,信号量的一个常见的用途是实现互斥机制,这种情况下,信号量的count值为1,也就是任意时刻只允许一个进程进入临界区。为此,linux内核源码提供了一个宏DECLARE_MUTEX,专门用于这种用途的信号量定义和初始化

    <include/linux/semaphore.h>
    
    #define DECLARE_MUTEX(name)  \
    
                  structsemaphore name=__SEMAPHORE_INITIALIZER(name,1)

    (4)互斥锁mutex

    Linux内核针对count=1的信号量重新定义了一个新的数据结构struct mutex,一般都称为互斥锁。内核根据使用场景的不同,把用于信号量的down和up操作在struct mutex上做了优化与扩展,专门用于这种新的数据类型。

    (5)RCU

    RCU概念:RCU全称是Read-Copy-Update(读/写-复制-更新),是linux内核中提供的一种免锁的同步机制。RCU与前面讨论过的读写自旋锁rwlock,读写信号量rwsem,顺序锁一样,它也适用于读取者、写入者共存的系统。但是不同的是,RCU中的读取和写入操作无须考虑两者之间的互斥问题。但是写入者之间的互斥还是要考虑的。

    RCU原理:简单地说,是将读取者和写入者要访问的共享数据放在一个指针p中,读取者通过p来访问其中的数据,而读取者则通过修改p来更新数据。要实现免锁,读写双方必须要遵守一定的规则。

    读取者的操作(RCU临界区)

    对于读取者来说,如果要访问共享数据。首先要调用rcu_read_lock和rcu_read_unlock函数构建读者侧的临界区(read-side critical section),然后再临界区中获得指向共享数据区的指针,实际的读取操作就是对该指针的引用。

    读取者要遵守的规则是:(1)对指针的引用必须要在临界区中完成,离开临界区之后不应该出现任何形式的对该指针的引用。(2)在临界区内的代码不应该导致任何形式的进程切换(一般要关掉内核抢占,中断可以不关)。

    写入者的操作

    对于写入者来说,要写入数据,首先要重新分配一个新的内存空间做作为共享数据区。然后将老数据区内的数据复制到新数据区,并根据需要修改新数据区,最后用新数据区指针替换掉老数据区的指针。写入者在替换掉共享区的指针后,老指针指向的共享数据区所在的空间还不能马上释放(原因后面再说明)。写入者需要和内核共同协作,在确定所有对老指针的引用都结束后才可以释放老指针指向的内存空间。为此,写入者要做的操作是调用call_rcu函数向内核注册一个回调函数,内核在确定所有对老指针的引用都结束时会调用该回调函数,回调函数的功能主要是释放老指针指向的内存空间。Call_rcu函数的原型如下:

    Void call_rcu(struct rcu_head *head,void (*func)(struct rcu_head *rcu));

    内核确定没有读取者对老指针的引用是基于以下条件的:系统中所有处理器上都至少发生了一次进程切换。因为所有可能对共享数据区指针的不一致引用一定是发生在读取者的RCU临界区,而且临界区一定不能发生进程切换。所以如果在CPU上发生了一次进程切换切换,那么所有对老指针的引用都会结束,之后读取者再进入RCU临界区看到的都将是新指针。

    老指针不能马上释放的原因:这是因为系统中爱可能存在对老指针的引用,者主要发生在以下两种情况:(1)一是在单处理器范围看,假设读取者在进入RCU临界区后,刚获得共享区的指针之后发生了一个中断,如果写入者恰好是中断处理函数中的行为,那么当中断返回后,被中断进程RCU临界区中继续执行时,将会继续引用老指针。(2)另一个可能是在多处理器系统,当处理器A上的一个读取者进入RCU临界区并获得共享数据区中的指针后,在其还没来得及引用该指针时,处理器B上的一个写入者更新了指向共享数据区的指针,这样处理器A上的读取者也饿将引用到老指针。

    RCU特点:由前面的讨论可以知道,RCU实质上是对读取者与写入者自旋锁rwlock的一种优化。RCU的可以让多个读取者和写入者同时工作。但是RCU的写入者操作开销就比较大。在驱动程序中一般比较少用。

    为了在代码中使用RCU,所有RCU相关的操作都应该使用内核提供的RCU API函数,以确保RCU机制的正确使用,这些API主要集中在指针和链表的操作。

    下面是一个RCU的典型用法范例:

    假设struct shared_data是一个在读取者和写入者之间共享的受保护数据
     
    Struct shared_data{
     
    Int a;
     
    Int b;
     
    Struct rcu_head rcu;
     
    };
     
     
     
    //读取者侧的代码
     
    Static void demo_reader(struct shared_data *ptr)
     
    {
     
           Struct shared_data *p=NULL;
     
           Rcu_read_lock();
     
           P=rcu_dereference(ptr);
     
           If(p)
     
                  Do_something_withp(p);
     
           Rcu_read_unlock();
     
    }
     
     
     
    //写入者侧的代码
     
     
     
    Static void demo_del_oldptr(struct rcu_head *rh) //回调函数
     
    {
     
           Struct shared_data *p=container_of(rh,struct shared_data,rcu);
     
           Kfree(p);
     
    }
     
    Static void demo_writer(struct shared_data *ptr)
     
    {
     
           Struct shared_data *new_ptr=kmalloc(…);
     
           …
     
           New_ptr->a=10;
     
           New_ptr->b=20;
     
           Rcu_assign_pointer(ptr,new_ptr);//用新指针更新老指针
     
           Call_rcu(ptr->rcu,demo_del_oldptr); 向内核注册回调函数,用于删除老指针指向的内存空间
     
    }
    
    
    (6)完成接口completion
    

    Linux内核还提供了一个被称为“完成接口completion”的同步机制,该机制被用来在多个执行路径间作同步使用,也即协调多个执行路径的执行顺序。在此就不展开了。

     

    展开全文
  • 操作系统同步研究——Linux内核同步机制.pdf
  • Linux操作系统内核同步机制分析.PDF
  • LINUX中断处理程序及内核同步;系统调用和中断(回顾上节课内容;中断处理程序的上下半部机制;上下半部怎样分开;下半部实现机制;软中断机制;软中断机制;软中断机制;软中断机制;软中断机制;Tasklets机制;Tasklets机制;...
  • Linux操作系统内核同步机制分析.pdf
  • 自旋锁是专为防止多处理器并发而引入的一种锁,它在内核中大量应用于中断处理等部分(对于单处理器来说,防止中断处理中的并发可简单采用关闭中断的方式,即在标志寄存器中关闭/打开中断标志位,不需要自旋锁)。
  • Linux内核同步机制

    2020-11-10 07:29:16
    一、引言 在现代操作系统里,同一时间可能有多个内核执行流在执行,因此内核其实象多进程多线程编程一样也需要一些同步机制来同步各执行单元对共享数据的访问。尤其是在多处理器系统上,更需要一些同步机制来同步...
  • linux 内核同步机制

    2011-11-29 16:22:06
    本文档介绍在linux内核中两个不同进程或者过程访问和使用同一...其中处理竟态条件的同步机制在不同内核过程中处理的应用(中断,softirq,tasklet,timer,用户上下文)。 然后介绍了内核抢占,内核可能睡眠的函数。
  • 本文主要介绍了linux内核自旋锁是如何工作的。
  • 深入理解linux内核,中文第三版,可随便复制粘贴,包含所有20章的内容
  • Linux内核同步机制之基本概念

    千次阅读 2020-11-17 12:57:47
    一、概述 近期深入的学习了 Linux 内核同步机制,将相关内容整理于此,既是一次梳理,也是一个分享,希望能帮助到读者一二。当然,所谓的深入也只是笔者现有的技术能力所能达到的程度而已。由于能力有限,有错误之处...

    一、概述

    近期深入的学习了 Linux 内核同步机制,将相关内容整理于此,既是一次梳理,也是一个分享,希望能帮助到读者一二。当然,所谓的深入也只是笔者现有的技术能力所能达到的程度而已。由于能力有限,有错误之处还请各位读者不吝指教,一起学习一起进步。

    常用的 Linux 内核同步机制有原子操作、Per-CPU 变量、内存屏障、自旋锁、Mutex 锁、信号量和 RCU 等,后面几种锁实现会依赖于前三种基础同步机制。在正式开始分析具体的内核同步机制实现之前,需要先澄清一些基本概念。

    二、基本概念

    2.1 同步

    既然是同步机制,那就首先要搞明白什么是同步。同步是指用于实现控制多个执行路径按照一定的规则或顺序访问某些系统资源的机制。所谓执行路径,就是在 CPU 上运行的代码流。我们知道,CPU 调度的最小单位是线程,可以是用户态线程,也可以是内核线程,甚至是中断服务程序。所以,执行路径在这里就包括用户态线程、内核线程和中断服务程序。执行路径、执行单元、控制路径等等,叫法不同,但本质都一样。那为什么需要同步机制呢?请继续往下看。

    2.2 并发与竞态

    并发是指两个以上的执行路径同时被执行,而并发的执行路径对共享资源(硬件资源和软件上的全局变量等)的访问则很容易导致竞态。例如,现在系统有一个 LED 灯可以由 APP 控制,APP1 控制灯亮一秒灭一秒,APP2 控制灯亮 500ms 灭 1500ms。如果 APP1 和 APP2 分别在 CPU1 和 CPU2 上并发运行,LED 灯的行为会是什么样的呢?很有可能 LED 灯的亮灭节奏都不会如这两个 APP 所愿,APP1 在关掉 LED 灯时,很有可能恰逢 APP2 正要打开 LED 灯。很明显,APP1 和 APP2 对 LED 灯这个资源产生了竞争关系。竞态是危险的,如果不加以约束,轻则只是程序运行结果不符合预期,重则系统崩溃。在操作系统中,更复杂、更混乱的并发大量存在,而同步机制正是为了解决并发和竞态问题。同步机制通过保护临界区(访问共享资源的代码区域)达到对共享资源互斥访问的目的,所谓互斥访问,是指一个执行路径在访问共享资源时,另一个执行路径被禁止去访问。关于并发与竞态,有个生活例子很贴切。假如你和你的同事张小三都要上厕所,但是公司只有一个洗手间而且也只有一个坑。当张小三进入厕所关起门的那一刻起,你就无法进去了,只能在门外侯着。当小三哥出来后你才能进去解决你的问题。这里,公司厕所就是共享资源,你和张小三同时需要这个共享资源就是并发,你们对厕所的使用需求就构成了竞态,而厕所的门就是一种同步机制,他在用你就不能用了。更多内容请查阅宋宝华老师的《Linux 设备驱动开发详解》一书中第七章第一节,书中详细列举了竞态发生的场景,总结如下图。

    2.3 中断与抢占

            中断本身的概念很简单,本文不予解释。当然,这并不是说 Linux 内核的中断部分也很简单。事实上,Linux 内核的中断子系统也相当复杂,因为中断对于操作系统来说实在是太重要了。以后有机会,笔者计划开专题再来介绍。对于同步机制的代码分析来说,了解中断的概念即可,不需要深入分析内核的具体代码实现。抢占属于进程调度的概念,Linux 内核从 2.6 版本开始支持抢占调度。进程调度(管理)是 Linux 内核最核心的子系统之一,异常庞大,本文只简单介绍基本概念,对于同步机制的代码分析已然足够。通俗地说,抢占是指一个正愉快地运行在 CPU 上的 task(可以是用户态进程,也可以是内核线程) 被另一个 task(通常是更高优先级)夺去 CPU 执行权的故事。中断和抢占之间有着比较暧昧的关系,简单来说,抢占依赖中断。如果当前 CPU 禁止了本地中断,那么也意味着禁止了本 CPU 上的抢占。但反过来,禁掉抢占并不影响中断。Linux 内核中用 preempt_enable() 宏函数来开启本 CPU 的抢占,用 preempt_disable() 来禁掉本 CPU 的抢占。这里,“本 CPU” 这个描述其实不太准确,更严谨的说法是运行在当前 CPU 上的 task。preempt_enable() 和 preempt_disable() 的具体实现展开来介绍的话也可以单独成文了,笔者没有深究过,就不班门弄斧了,感兴趣的读者可以去 RTFSC。不管是用户态抢占还是内核态抢占,并不是什么代码位置都能发生,而是有抢占时机的,也就是所谓的抢占点。抢占时机如下:
           用户态抢占:1、从系统调用返回用户空间时;2、从中断(异常)处理程序返回用户空间时。
           内核态抢占:1、当一个中断处理程序退出,返回到内核态时;2、task 显式调用 schedule();3、task 发生阻塞(此时由调度器完成调度)。
           以上情况是个人理解,欢迎补充其它 case。

    2.4 编译乱序与编译屏障

    参阅笔者转载的这篇文章 https://blog.csdn.net/weixin_43555423/article/details/113481578

    2.5 执行乱序与内存屏障

    《Linux 设备驱动开发详解》一书中第七章第二节对编译乱序和执行乱序都有简略的介绍,通俗易懂,不可不读。不管是编译乱序还是执行乱序,都是为了提升 CPU 的性能。执行乱序是处理器运行时的行为,和 CPU 内部设计架构有关。而对于从事在 Linux 内核的程序员来说,要真正的理解透执行乱序所带来的软件方面的影响,首先需要搞清楚 cache 的概念。强烈建议关注奔跑 Linux 社区这个公众号,里面有三篇关于 cache 的文章,分为上中下,作者笨叔讲解的非常透彻。内存屏障是为了解决执行乱序引入的问题,个人认为是同步机制里最难理解的一块。关于内存屏障,可以参阅 wowo 翻译的这几篇文章,链接如下:

    http://www.wowotech.net/kernel_synchronization/Why-Memory-Barriers.html  Why Memory Barriers?中文翻译(上)
    http://www.wowotech.net/kernel_synchronization/why-memory-barrier-2.html  Why Memory Barriers?中文翻译(下)
    http://www.wowotech.net/kernel_synchronization/memory-barrier-1.html  perfbook memory barrier(14.2章节)中文翻译(上)
    http://www.wowotech.net/kernel_synchronization/perfbook-memory-barrier-2.html  perfbook memory barrier(14.2章节)中文翻译(下)

    perbook 一书的全称是《Is Parallel Programming Hard And If So What Can You Do About It?》,是并行编程领域的权威著作,作者是大名鼎鼎的 Paul E. Mckenney。Paul 目前供职于 IBM Linux 技术中心,也是 Linux 社区 RCU 模块的领导者和维护者。perbook 的中文版本名称是 《深入理解并行编程》,由国产内核大神谢宝友倾情翻译。谢大神目前就职于阿里,他和 Linux 之间也有一段传奇经历。关于两位大神更多的趣闻轶事,感兴趣的读者可以上网搜寻。谢大神的翻译非常贴近原文,但读起来终觉比较晦涩,可能是笔者功力不够。wowo 的翻译则优先考虑的是汉语表述的流畅性,所以读起来会很顺畅,唯一美中不足的就是排版[笑哭]。笔者在学习过程中重新整理了排版,并删掉了英文原文,然后用红色字体加入了自己的一些读书笔记,有兴趣的读者朋友可以留言索取,欢迎一起交流。如果有的读者朋友英语很好,强烈建议你们去读原文。

    展开全文
  • 内核同步

    千次阅读 2014-03-12 11:00:13
    因此这些请求可能引起竞态条件,而我们必须采用适当的同步机制对这种情况进行控制。 一、内核如何为不同的请求提供服务  把内核看作必须满足两种请求的侍者:一种请求来自顾客,另一种请求来自数量有限的几个不同...

    内核的各个部分并不是严格按照顺序依次执行的,而是采用交错执行的方式。因此这些请求可能引起竞态条件,而我们必须采用适当的同步机制对这种情况进行控制。
    一、内核如何为不同的请求提供服务
            把内核看作必须满足两种请求的侍者:一种请求来自顾客,另一种请求来自数量有限的几个不同的老板。对不同的请求,侍者采用如下的策略:
            1、老板提出请求时,如果侍者正空闲,则侍者开始为老板服务。
            2、如果老板提出请求时侍者正在为顾客服务,那么侍者停止为顾客服务,开始为老板服务。
            3、如果一个老板提出请求时侍者正在为另一个老板服务,那么侍者停止为第一个老板提供服务,而开始为第二个老板服务,服务完毕再继续为第一个老板服务。
            4、一个老板可能命令侍者停止正在为顾客提供的服务。侍者在完成对老板最近请求的服务之后,可能会暂时不理会原来的顾客而去为新选中的顾客服务。(内核抢占)
            侍者提供的服务对应于CPU处于内核态时所执行的代码。如果CPU在用户态执行,则侍者被认为处于空闲状态。老板的请求相当于中断,而顾客的请求相当于用户态进程发出的系统调用或异常。
    1.1、内核抢占
            如果进程正执行内核函数时,即它在内核态运行时,允许发生内核切换(被替换的进程是正执行内核函数的进程),这个内核就是抢占的。在Linux中,情况要复杂的多。
            1、无论在抢占内核还是非抢占内核中,运行在内核态的进程都可以自动放弃CPU。
            2、所有的进程切换都是由宏switch_to来完成。在抢占内核和非抢占内核中,当进程执行完某些具有内核功能的线程,而且调度程序被调用后,就发生进程切换。不过,在非抢占内核中,当前进程是不可能被替换的,除非它打算切换到用户态。
            抢占内核的主要特点:一个在内核态运行的进程,可能在执行内核函数期间被另外一个进程取代。
            使内核可抢占的目的是减少用户态进程的分派延迟(dispatch laency),即从进程变为可执行状态到它实际开始运行之间的时间间隔。内核抢占对执行及时被调度的任务的进程确实有好处的,因为它降低了这种进程被另一个运行在内核态的进程延迟的风险。
            使Linux2.6内核具有可抢占的特性无需对支持非抢占的旧内核在设计上做太大的改变,当被current_thread_info()宏所引用的thread_info描述符的preempt_count字段大于0时,就禁止内核抢占。该字段的编码对应三个不同的计数器,因此它在如下任何一种情况发生时,取值都大于0:
            1、内核正在执行中断服务例程。
            2、可延迟函数被禁止(当内核正在执行软中断或tasklet时经常如此)。
            3、通过把抢占计数器设置为正数而显示地禁用内核抢占。
            上面的原则告诉我们:只有当内核正在执行异常处理程序(尤其是系统调用),而且内核抢占没有被显式地禁用时,才可能抢占内核。此外,本地CPU必须打开本地中断,否则无法完成内核抢占。
            内核抢占可能在结束内核控制路径(通常是一个中断处理程序)时发生,也可能在异常处理程序调用preempt_enable()重新允许内核抢占时发生。内核抢占也可能发生在启用可延迟函数的时候。
    1.2、什么时候同步是必须的
            当计算的结果依赖于两个或两个以上的交叉内核控制路径的嵌套方式时,可能出现竞争条件。临界区是一段代码,在其他的内核控制路径能够进入临界区前,进入临界区的内核控制路径必须全部执行完这段代码。
            交叉内核控制路径使内核开发者的工作变得复杂了:他们必须特别小心地识别出异常处理程序、中断处理程序、可延迟函数和内核线程中的临界区。一旦临界区被确定,就必须对其采用适当的保护措施,以确保在任意时刻只有一个内核控制路径处于临界区。
            例如,假设两个不同的中断处理程序要访问同一个包含了几个相关变量的数据结构,比如一个缓冲区和一个表示缓冲区大小的整型变量。所有影响该数据结构的语句都必须放入一个单独的临界区。如果是单CPU的系统,可以采取访问共享数据结构时关闭中断的方式来实现临界区,因为只有在开中断的情况下,才可能发生内核控制路径的嵌套。
            另外,如果相同的数据结构仅被系统调用服务例程所访问,而且系统中只有一个CPU,就可以非常简单地通过在访问共享数据结构时禁用内核抢占功能来实现临界区。
            在多处理器系统中,情况要复杂得多。由于许多CPU可能同时执行内核路径,因此内核开发者不能假设只要禁用内核抢占功能,而且中断、异常和软中断处理程序都没有访问过该数据结构,就能保证这个数据结构能够安全地被访问。
    1.3、什么时候同步是不必要的
            1、所有的中断处理程序响应来自PIC的中断并禁用IRQ线。此外,在中断处理程序结束之前,不允许产生相同的中断事件。
            2、中断处理程序、软中断和tasklet既不可以被抢占也不能被阻塞,所以它们不可能长时间处于挂起状态。在最坏的情况下,它们的执行将有轻微的延迟,因为在其执行的过程中可能发生其他的中断(内核控制路径的嵌套执行)。
            3、执行中断处理的内核控制路径不能被执行可延迟函数或系统调用服务例程的内核控制路径中断。
            4、软中断和tasklet不能在一个给定的CPU上交错执行。
            5、同一个tasklet不可能同时在几个CPU上执行。
            简化的例子:
            1、中断处理程序和tasklet不必编写成可重入的函数。
            2、仅被软中断和tasklet访问的每CPU变量不需要同步。
            3、仅被一种tasklet访问的数据结构不需要同步。
    二、同步原语
            下表列出了Linux内核使用的同步技术。“适用范围”一栏表示同步技术是适用于系统中的所有CPU还是单个CPU。例如,本地中断的禁止只适用于一个CPU(系统中的其他CPU不受影响);相反,原子操作影响系统中的所有CPU(当访问同一个数据结构时,几个CPU上的原子操作不能交错)。
            表:内核使用的各种同步技术
                技术                                说明                                                            适用范围
            每CPU变量                    在CPU之间复制数据结构                                        所有CPU
            原子操作                对一个计数器原子地“读-修改-写”的指令                           所有CPU
            内存屏障                            避免指令重新排序                                    本地CPU或所有CPU
            自旋锁                            加锁时忙等                                                       所有CPU
            信号量                             加锁时阻塞等待(睡眠)                                        所有CPU
            顺序锁                            基于访问计数器的锁                                            所有CPU
            本地中断的禁止                 禁止单个CPU上的中断处理                                  本地CPU
            本地软中断的禁止              禁止单个CPU上的可延迟函数处理                         本地CPU
            读-拷贝-更新(RCU)             通过指针而不是锁来访问共享数据结构                   所有CPU
    2.1、每CPU变量(per-cpu variable)
            最好的同步技术是把设计不需要同步的内核放在首位。
            内核控制路径应该在禁用抢占的情况下访问每CPU变量。
    2.2、原子操作
            Linux内核提供了一个专门的atomic_t类型(一个原子访问计数器)和一些专门的函数和宏,这些函数和宏作用于atomic_t类型的变量,并当做单独的、原子的汇编语言指令来使用。在多处理器系统中,每条这样的指令都有一个lock字节的前缀。
            另一类原子函数操作作用于位掩码。
    2.3、优化和内存屏障
            当处理同步时,必须避免指令重新排序。如果放在同步原语之后的一条指令在同步原语本身之前执行,事情很快就会变得失控。事实上,所有的同步原语起优化和内存屏障的作用。
            优化屏障(optimization barrier)原语保证编译程序不会混淆放在原语操作之前的汇编语言指令和放在原语操作之后的汇编语言指令,这些汇编语言指令在C中都有对应的语句。在Linux中,优化屏障(optimization barrier)就是barrier宏。它展开为asm volatile("":::"memory")。指令asm告诉编译程序要插入汇编语言片段(这种情况下为空)。volatile关键字禁止编译器把asm指令与程序中的其他指令重新组合。memory关键字强制编译器假定RAM中的所有内存单元已经被汇编语言指令修改;因此,编译器不能使用存放在CPU寄存器中的内存单元的值来优化asm指令前的代码。注意,优化屏障并不保证不使当前CPU把汇编语言指令混在一起执行–这是内存屏障的工作。
            在多处理器系统上,在前一节“原子操作”中描述的所有原子操作都起内存屏障的作用,因为它们使用了lock字节。
    2.4、自旋锁
            一种广泛应用的同步技术就是加锁(locking)。当内核控制路径必须访问共享数据结构或进入临界区时,就需要为自己获得一把“锁”。由锁机制保护的资源非常类似于限制于房间内的资源,当某人进入房间时,就把门锁上。如果内核控制路径希望访问资源,就试图获取钥匙“打开门”。当切仅当资源空闲时,它才能成功。然后,只要它还想使用这个资源,门就依然锁着。当内核控制路径释放了锁时,门就打开,另一个内核控制路径就可以进入房间。
            自旋锁(spin lock)是用来在多处理器环境中工作的一种特殊的锁。如果内核控制路径发现自旋锁“开着”,就获取锁并继续自己的执行。相反,如果内核控制路径发现锁由运行在另一个CPU上的内核控制路径“锁着”,就在周围“旋转”,反复执行一条紧凑的循环指令,直到锁被释放。
            自旋锁的循环指令表示“忙等”。即使等待的内核控制路径无事可做(除了浪费时间),它也在CPU上保持运行。不过,自旋锁通常非常方便,因为很多内核资源只锁1毫秒的时间片段;所以说,释放CPU和随后又获得CPU都不会消耗多少时间。
            一般来说,由自旋锁保护的每个临界区都是禁止内核抢占的。在单处理器系统上,这种锁本身并不起锁的作用,自旋锁原语仅仅是禁止或启用内核抢占。在自旋锁忙等期间,内核抢占还是有效的,因此,等待自旋锁释放的进程有可能被更高优先级的进程替代。
    2.4.1、具有内核抢占的spin_lock宏

    2.4.2、非抢占式内核中的spin_lock宏

    2.4.3、spin_unlock宏

    2.5、读/写自旋锁
            读/写自旋锁的引入是为了增加内核的并发能力。只要没有内核控制路径对数据结构进行修改,读/写自旋锁就允许多个内核控制路径同时读同一数据结构。如果一个内核控制路径想对这个结构进行写操作,那么它必须首先获取读/写锁的写锁,写锁授权独占访问这个资源。当然,允许对数据结构并发读可以提高系统性能。
            每个读/写自旋锁都是一个rwlock_t结构,其lock字段是一个32位的字段,分为两个不同的部分:
            * 24位计数器,表示对受保护的数据结构并发地进行读操作的内核控制路径的数目。这个计数器的二进制补码存放在这个字段的0~23位。
            * “未锁”标志字段,当没有内核控制路径在读或写时设置该位,否则清0。这个“未锁”标志存放在lock字段的第24位。
    2.5.1、为读获取和释放一个锁

    2.5.2、为写获取和释放一个锁

    2.6、顺序锁
            顺序锁(seqlock)与读/写自旋锁非常相似,只是它为写者赋予了较高的优先级。
            并不是每一种资源都可以使用顺序锁来保护。一般来说,必须在满足下述条件时才能使用顺序锁:
            * 被保护的数据结构不包括被写着修改和被读者间接引用的指针(否则,写着可能在读者的眼鼻下就修改指针)。
            * 读者的临界区代码没有副作用(否则,多个读者的操作会与单独的读操作有不同的结果)。
            此外,读者的临界区代码应该简短,而且写着应该不常获取顺序锁,否则,反复的读访问会引起严重的开销。在Linux2.6中,使用顺序锁的典型例子包括保护一些与系统时间处理相关的数据结构。
    2.7、读–拷贝–更新(RCU)
            读-拷贝-更新(RCU)是为了保护在多数情况下被多个CPU读的数据结构而设计的另一种同步技术。RCU允许多个读者和写着并发执行(相对于只允许一个写者执行的顺序锁有了改进)。而且,RCU是不使用锁的,就是说,它不使用被所有CPU共享的锁或计数器。
            RCU关键的思想包括限制RCP的范围,如下:
            1、RCU只保护被动态分配并通过指针引用的数据结构。
            2、在被RCU保护的临界区中,任何内核控制路径都不能睡眠。
            当内核控制路径要读取被RCU保护的数据结构时,执行宏rcu_read_lock(),它等同于preempt_disable()。接下来,读者间接引用该数据结构指针所对应的内存单元并开始读这个数据结构。正如在前面强调的,读者在完成对数据结构的读操作之前,是不能睡眠的。用等同于preempt_enable()的宏rcu_read_unlock()标记临界区的结束。
            当写者要更新数据结构时,它间接引用指针并生成整个数据结构的副本。接下来,写者修改这个副本。一旦修改完毕,写者改变指向数据结构的指针,以使它指向被修改后的副本。由于修改指针值 的操作是一个原子操作,所以旧副本和新副本对每个读者和写者都是可见的,在数据结构中不会出现数据崩溃。尽管如此,还需要内存屏障来保证:只有在数据结构被修改之后,已更新的指针对其他CPU才是可见的。如果把自旋锁与RCU结合起来以禁止写者的并发执行,就隐含地引入了这样的内存屏障。
            然而,使用RCU技术的真正困难在于:写者修改指针时不能立即释放数据结构的旧副本。实际上,写者开始修改时,正在访问数据结构的读者可能还在读旧副本。只有在CPU上的所有(潜在的)读者都执行完宏rcu_read_unlock()之后,才可以释放旧副本。内核要求每个潜在的读者在下面的操作之前执行rcu_read_unlock()宏:
            * CPU执行进程切换。
            * CPU开始在用户态执行。
            * CPU执行空循环。
            对上述每种情况,我们说CPU已经过了静止状态(quiescent state)。
            写者调用call_rcu()来释放数据结构的旧副本。当所有的CPU都通过静止状态之后,call_rcu()接受rcu_head描述符(通常嵌在要被释放的数据结构中)的地址和将要调用的回调函数的地址作为参数。一旦回调函数被执行,它通常释放数据结构的旧副本。
            函数call_rcu()把回调函数和其参数的地址存放在rcu_head描述符中,然后把描述符插入回调函数的每CPU(per-CPU)链表中。内核每经过一个始终滴答就周期性地检查本地CPU是否经过了一个静止状态。如果所有的CPU都经过了静止状态,本地tasklet(它的描述符存放在每CPU变量rcu_tasklet中)就执行链表中的所有回调函数。
    2.8、信号量
            内核信号量类似于自旋锁,因为当锁关闭着时,它不允许内核控制路径继续进行。然而,当内核控制路径试图获取内核信号量所保护的忙资源时,相应的进程被挂起。只有在资源被释放时,进程才再次变为可运行的。因此,只有可以睡眠的函数才能获取内核信号量。中断处理程序和可延迟函数都不能使用内核信号量
    2.8.1、获取和释放信号量

    2.9、读/写信号量
            内核以严格的FIFO顺序处理等待读/写信号量的所有进程。如果读者或写者进程发现信号量关闭,这些进程就被插入到信号量等待队列链表的末尾。当信号量被释放时,就检查处于等待队列链表第一个位置的进程。第一个进程常被唤醒。如果是一个写者进程,等待队列上其他进程就继续睡眠。如果是一个读者进程,那么紧跟第一个进程的其他所有读者进程也被唤醒并获得锁。不过,在写者进程之后排队的读者进程继续睡眠。
    2.10、补充原语
            类似于信号量的原语:补充(completion)。
            struct completion {
                unsigned int done;
                wait_queue_head_t wait;
            };
            与down()对应的函数叫做wait_for_completion()。wait_for_completion()接收completion数据结构的地址作为参数,并检查done标志的值。如果该标志的值大于0,wait_for_completion()就终止,因为这说明complete()已经在另一个CPU上运行。否则,wait_for_completion()把current作为一个互斥进程加到等待队列的末尾,并把current置为TASK_UNINTERRUPTIBLE状态让其睡眠。一旦current被唤醒,该函数就把current从等待队列中删除,然后,函数检查done标志的值:如果等于0函数就结束,否则,再次挂起当前进程。与complete()函数中的情形一样,wait_for_completion()使用补充等待队列中的自旋锁。
            补充原语和信号量之间的真正差别在于如何使用等待队列中包含的自旋锁。在补充原语中,自旋锁用来确保complete()和wait_for_completion()不会并发执行。在信号量中,自旋锁用于避免并发执行的done()函数弄乱信号量的数据结构。
    2.11、禁止本地中断
            确保一组内核语句被当作一个临界区处理的主要机制之一就是中断禁止,即使当硬件设备产生一个IRQ信号时,中断禁止也让内核控制路径继续执行,因此,这就提供了一种有效的方式,确保中断处理程序访问的数据结构也受到保护。然而,禁止本地中断并不保护运行在另一个CPU上的中断处理程序对数据结构的并发访问,因此,在多处理器系统上,禁止本地中断经常与自旋锁结合使用。
            宏local_irq_disable()使用cli汇编语言指令关闭本地CPU上的中断,宏local_irq_enable()使用sti汇编语言指令打开被关闭的中断。汇编语言指令cli和sti分别清除和设置eflags控制寄存器的IF标志。如果eflags寄存器的IF标志被清0,宏irqs_disabled()产生等于1的值;如果IF标志被设置,该宏也产生为1的值。
            保存和恢复eflags的内容是分别通过宏local_irq_save和local_irq_restore来实现的。local_irq_save宏把eflags寄存器的内容拷贝到一个局部变量中,随后用cli汇编语言指令把IF标志清0。在临界区末尾,宏local_irq_restore恢复eflags原来的内容。因此,只是在这个控制路径发出cli汇编语言指令之前,中断被激活的情况下,中断才处于打开状态。
    2.12、禁止和激活可延迟函数
            禁止可延迟函数在一个CPU上执行的一种简单方式就是禁止在那个CPU上的中断,因为没有中断处理程序被激活,因此,软中断操作就不能异步地开始。
            如果软中断计数器是正数,do_softirq()函数就不会执行软中断,而且,因为tasklet在软中断之前被执行,把这个计数器设置为大于0的值,由此禁止了在给定CPU上的所有可延迟函数和软中断的执行。
            宏local_bh_disable给本地CPU的软中断计数器加1,而函数local_bh_enbale()从本地CPU的软中断计数器中减掉1。内核因此能使用几个嵌套的local_bh_disable调用,只有宏local_bh_enable与第一个local_bh_disable调用相匹配,可延迟函数才再次被激活。
            递减软中断计数器之后,local_bh_enable()执行两个重要的操作以有助于保证适时地执行长时间等待的线程:
            1、检查本地CPU的preempt_count字段中硬中断计数器和软中断计数器,如果这两个计数器的值都等于0而且有挂起的软中断要执行,就调用do_softirq()来激活这些软中断。
            2、检查本地CPU的TIF_NEED_RESCHED标志是否被设置,如果是,说明进程切换请求是挂起的,因此调用preempt_schedule()函数。
    三、对内核数据结构的同步访问
            法则:把系统中的并发度保持在尽可能高的程序
            系统中的并发度又取决于两个主要因素:
            1、同时运转的I/O设备数。
            2、进行有效工作的CPU数。
            为了使I/O吞吐量最大化,应该使中断禁止保持在很短的时间
            为了有效地利用CPU,应该尽可能避免使用基于自旋锁的同步原语。当一个CPU执行紧指令循环等待自旋锁打开时,是在浪费宝贵的机器周期。由于自旋锁对硬件高速缓存的影响而使其对系统的整体性能产生不利影响
            既可以维持较高的并发度,也可以达到同步的两种方法:
            1、共享的数据结构是一个单独的整数值,可以把它声明为atomic_t类型并使用原子操作对其更新。原子操作比自旋锁和中断禁止都快,只有在几个内核控制路径同时访问这个数据结构时速度才会慢下来。
            2、把一个元素插入到共享链表的操作绝不是原子的,因为这至少涉及两个指针赋值。
    3.1、在自旋锁、信号量及中断禁止之间选择
            同步原语的选取取决于访问数据结构的内核控制路径的种类。只要内核控制路径获得自旋锁(还有读/写锁、顺序锁或RCU“读锁”),就禁止本地中断或本地软中断,自动禁用内核抢占。
    表:内核控制路径访问的数据结构所需要的保护
            访问数据结构的内核控制路径                单处理器保护                    多处理器进一步保护
            异常                                                      信号量                                无
            中断                                                本地中断禁止                            自旋锁
            可延迟函数                                            无                                    无或自旋锁
            异常与中断                                      本地中断禁止                            自旋锁
            异常与可延迟函数                            本地软中断禁止                          自旋锁
            中断与可延迟函数                            本地中断禁止                             自旋锁
            异常、中断与可延迟函数                   本地中断禁止                             自旋锁
    3.1.1、保护异常所访问的数据结构
            竞争条件可以通过信号量避免,因为信号量原语允许进程睡眠到资源变为可用。注意,信号量工作方式在单处理器系统和多处理器系统上完全相同。
            只有在访问每CPU变量的情况下,必须显示地禁用内核抢占
    3.1.2、保护中断所访问的数据结构
            假定一个数据结构仅被中断处理程序的“上半部分”访问,由于中断处理程序本身不能同时多次运行。因此,访问数据结构就无需任何同步原语
            如果多个中断处理程序访问一个数据结构,共享的数据就很容易被破坏
            在单处理器系统上,必须通过在中断处理程序的所有临界区上禁止中断来避免竞争条件。只能用这种方式进行同步,因为其他的同步原语都不能完成这件事。信号量能够阻塞进程,因此,不能用在中断处理程序上。另一个方面,自旋锁可能使系统冻结:如果访问数据结构的处理程序被中断,它就不能释放锁;因此,新的中断处理程序在自旋锁的紧循环上保持等待
            多处理器系统不能简单地通过禁止本地中断来避免竞争条件。因为即使在一个CPU上禁止了中断,中断处理程序还可以在其他CPU上执行,避免竞争条件最简单的方法是禁止本地中断(以便运行在同一个CPU上的其他中断处理程序不会造成干扰),并获取保护数据结构的自旋锁或读/写自旋锁。注意,这些附加的自旋锁不能冻结系统,因为即使中断处理程序发现锁被关闭,在另一个CPU上拥有锁的中断处理程序最终也会释放这个锁
    3.1.3、保护可延迟函数所访问的数据结构
            在单处理器系统上不存在竞争条件。这是因为可延迟函数的执行总是在一个CPU上串行进行–也就是说,一个可延迟函数不会被另一个可延迟函数中断,因此,根本不需要同步原语
            在多处理器系统上,竞争条件的确存在,因为几个可延迟函数并发运行。
            软中断和多个tasklet使用自旋锁保护,一个tasklet不需要
            由软中断访问的数据结构必须受到保护,通常使用自旋锁进行保护,因为同一个软中断可以在两个或多个CPU上并发运行。相反,仅由一种tasklet访问的数据结构不需要保护,因为同种tasklet不能并发运行。但是,如果数据结构被几种tasklet访问,那么就必须对数据结构进行保护
    3.1.4、保护由异常和中断访问的数据结构
            在单处理器系统上,竞争条件的防止是相当简单的,因为中断处理程序不是可重入的且不能被异常中断。只要内核以本地中断禁止访问数据结构,内核在访问数据结构的过程中就不会被中断。不过,如果数据结构正好是被一种中断处理程序访问,那么,中断处理程序不用禁止本地中断就可以自由地访问数据结构。
            在多处理器系统上,必须关注异常和中断在其他CPU上的并发执行。本地中断禁止还必须外加自旋锁,强制并发的内核控制路径进行等待,直到访问数据结构的处理程序完成自己的工作
            有时,用信号量代替自旋锁可能更好。因为中断处理程序不能被挂起,它们必须用紧循环和down_trylock()函数获得信号量;对这些中断处理程序来说,信号量起的作用本质上与自旋锁一样。另一方面,系统调用服务例程可以在信号量忙时挂起调用进程。对大部分系统调用而言,这是所期望的行为。在这种情况下,信号量比自旋锁更好,因为信号量使系统具有更高的并发度。
    3.1.5、保护由异常和可延迟函数访问的数据结构
            异常和可延迟函数都访问的数据结构与异常和中断处理程序访问的数据结构处理方式类似。可延迟函数本质上是由中断的出现激活的,而可延迟函数执行时不可能产生异常。因此,把本地中断禁止与自旋锁结合起来就足够了
            异常处理程序可以通过使用local_bh_disable()宏简单地禁止可延迟函数,而不禁止本地中断。仅禁止可延迟函数比禁止中断更可取,因为中断还可以继续在CPU上得到服务。在每个CPU上可延迟函数的执行都被串行化,因此,不存在竞争条件。
            同样,在多处理器系统上,要用自旋锁确保任何时候只有一个内核控制路径访问数据结构。
    3.1.6、保护由中断和可延迟函数访问的数据结构
            这种情况类似于中断和异常处理程序访问的数据结构。当可延迟函数运行时可能产生中断,但是,可延迟函数不能阻止中断处理程序。因此,必须通过在可延迟函数执行期间禁用本地中断来避免竞争条件。不过,中断处理程序可以随意访问被可延迟函数访问的数据结构而不用关中断,前提是没有其他的中断处理程序访问这个数据结构。
            在多处理器系统上,需要自旋锁禁止对多个CPU上数据结构的并发访问。
    3.1.7、保护由异常、中断和可延迟函数访问的数据结构
            禁止本地中断和获取自旋锁几乎总是避免竞争条件所必须的。没有必要显示地禁止可延迟函数,因为当中断处理程序终止执行时,可延迟函数才能被实质激活,因此,禁止本地中断就足够了。
    四、避免竞争条件的实例
    4.1、引用计数器
            引用计数器广泛地用在内核以避免由于资源的并发分配和释放而产生的竞争条件。引用计数器是一个atomic_t计数器,与特定的资源,如内存页、模块或文件相关。当内核控制路径开始使用资源时就原子地减少计数器的值,当内核控制路径使用完资源时就原子地增加计数器。当计数器变为0时,说明该资源未被使用,如果必要,就释放该资源。
    4.2、大内核锁
            在Linux2.6版本的内核中,用大内核锁来保护旧的代码(绝大多数是与VFS和几个文件系统相关的函数)。
    4.3、内存描述符/写信号量

    4.4、slab高速缓存链表的信号量

    4.5、索引节点的信号量

    展开全文
  • 系统内核同步

    2012-03-18 15:29:54
    有关linux操作系统系统的内核同步机制分析
  • 《深入理解linux内核中文第三版》,高清晰扫描,真正中文第三版,对Linux 2.6内核进行了详细而细致的讲解。由于之前的压缩包分卷太多,现提供每一章的单独下载文件。100%高清晰第三版!
  • 内核同步机制 关于同步理论的一些基本概念 临界区(critical area): 访问或操作共享数据的代码段 简单理解:synchronized大括号中部分(原子性) 竞争条件(race conditions)两个线程同时拥有临界区的执行权 数据...
  • Linux内核同步介绍及方法

    千次阅读 2016-11-06 18:50:56
    第9章内核同步介绍 (1)多个执行线程同时访问和操作数据,就有可能发生各线程之间相互覆盖共享数据的情况,造成共享数据处于不一致状态。并发访问共享数据是造成系统不稳定的一类隐患,而且这种错误一般难以跟踪...
  • 共享资源需要保护,防止被并发访问。共享资源之所以需要防止被并发访问,是因为如果多个执行线程同事访问和操作数据,就有可能发生个线程之间相互覆盖共享数据的情况,造成被访问数据处于不一直状态。...
  • 本文为大家介绍了Linux内核中的同步和互斥分析报告。
  • 内核同步.rar 致读者:深入理解LINUX内核第三版pdf版本扫描出来的,内容比较大,所以必须分章节才能上传。我上传比你下载要更长时间,请大家谅解和支持,但是本文可以确保是第三版内容,希望大家下载后好好学习,我...
  • linux2.6内核同步实例

    2011-06-20 18:25:05
    内核中的同步与调度综合实例代码 该源码来自http://www.kerneltravel.net/ 内核中的同步与调度综合实例代码 该源码来自http://www.kerneltravel.net/
  • Linux内核中的同步机制

    千次阅读 2018-08-26 15:54:06
    本文介绍Linux内核中的一些同步机制,通过本文,希望读者能够明白以下几点: 什么是同步 为什么要同步 同步的几种手段 1.什么是同步? 与其解释什么是同步,倒不如告诉读者同步的由来。在Linux内核中,同步技术...
  • 内核同步机制-优化屏障和内存屏障,linux内核。
  • Linux 内核是多进程、多线程的操作系统,它提供了相当完整的内核同步方法。内核同步方法列表如下: 中断屏蔽 原子操作 自旋锁 读写自旋锁 顺序锁 信号量 读写信号量 BKL (大内核锁) Seq 锁 一、并
  • 内核提供了一组同步方法来提供对共享数据的保护。 我们的重点不是介绍这些方法的详细用法,而是强调为什么使用这些方法和它们之间的差别。 Linux 使用的同步机制可以说从2.0到2.6以来不断发展完善。从最初的原子...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 257,932
精华内容 103,172
关键字:

内核同步