第五章--并发和竞态

        两个重要概念：

        1、临界区

        2、原子

        信号量：睡眠锁

        自旋锁：忙等待

        阻塞：就是指在执行设备操作时若不能获得资源则挂起操作，直到满足可操作的条件后再进行操作，被挂起的进程进入休眠状态，被从调度器的运行队列移走，直到等待的条件满足。

        非阻塞：就是反过来，进程在不能进行设备操作时并不挂起，它或者放弃，或者不停的查询，直到可以进行为止。

一、并发及其管理

        仔细编写的内核代码应该具有最少的共享，这种思想的最明显应用就是避免使用全局变量。

        资源共享的硬规则：在单个执行线程之外共享硬件或软件资源的任何时候，因为另外一个线程可能产生对该资源的不一致观察，因此必须显示地管理对该资源的访问。

        在对象尚不能正确工作时，不能将其对内核可用，也就是说，对这类对象的应用必须得到跟踪。在大多数情况下，内核会为我们处理引用计数，然而总是会有例外。

        建立临界区：在任意给定的时刻，代码只能被一个线程执行。

        当进程在等待对临界区的访问时，锁机制可让进程进入休眠状态。         

        down_interruptible()：需要检查返回值，如果操作被中断，该函数返回非零值，此函数可以被信号中断。       
        正确使用锁定机制的关键是：明确指定需要保护的资源，并确保每一个对这些资源的访问使用正确的锁定。

        down会将调用进程置于不可中断的休眠状态；相反，down_interruptible可被信号中断。down_trylock不会休眠，并且会在信号量不可用时立即返回。锁定信号量的代码最后必须使用up解锁该信号量。

二、completion机制

        completetion()：完成接口，是一种轻量级的机制，它允许一个线程告诉另一线程某个工作已经完成。

        #include
        创建completion：
        DECLARE——COMPLETION(my_completion);
        如果必须动态地创建和初始化completion，则使用下面的方法：
        struct completion my_completion;
        init_completion(&my_completion);
        等待completion，调用：

        void wait_for_completion(struct completion *c);

        上面一个函数执行一个非中断的等待，如果代码调用了上面一个函数，且没有人会完成该人物，则将产生一个不可杀的进程。

三、自旋锁

        可在不能休眠的代码中使用，比如中断处理函数。

        一个自旋锁是一个互斥设备，它只能有两个值：“锁定”和“解锁”。它通常实现为某个整数值中的单个位。希望获得某特定锁的代码测试相关位。如果锁可用，则“锁定”位被设置，而代码继续进入临界区；相反，如果锁被其他人获得，则代码进入忙循环并重复检查这个锁，直到该锁可用为止。这个循环就是自旋锁的“自旋”部分。
        当存在自旋锁时，等待执行忙循环的处理器做不了任何有用的工作。
        所有的自旋锁等待在本质上都是不可中断的。一旦调用了spin_lock，在获得锁之前将一直处于自旋状态。

        核心规则：

        1、任何拥有自旋锁的代码都必须是原子的，它不能休眠，不能因为任何原因被放弃处理器，除了服务中断以外。

        2、内核代码拥有自旋锁，处理器的抢占就会被禁止。

        3、当编写需要在自旋锁下执行的代码时，必须注意每一个所调用的函数，防止调用函数睡眠。比如copy_frome_user和kmalloc等。

        4、在拥有自旋锁时禁止中断。

        5、自旋锁必须在可能的最短时间内拥有，拥有自旋锁的时间越长，其他处理器不得不自旋以等待释放该自旋锁的时间就越长。

        spin_lock_irqsave()：获得自旋锁之前禁止中断(只在本地处理器上)，先前的中断状态保存在flags中。

        必须在同一个函数中调用spin_lock_irqsave()和spin_unlock_irqrestore()。

        spin_lock_bh(spinlock_t *lock)：在获得锁之前禁止软件中断，但是会让硬件中断保持打开。

        规则：
        1、如果某个获得锁的函数要调用其他同样试图获取这个锁的函数，代码就会死锁。可以通过变量来标识是否拥有了锁。由系统调用直接调用的函数需要获得信号量。

        2、在必须获取多个锁时，应该始终以相同的顺序获得，可以避免获取多个锁时死锁。

        3、如果我们必须获得一个局部锁(比如一个设备锁)，以及一个属于内核更中心位置的锁，则必须首先获取自己的局部锁，如果我们拥有信号量和自旋锁的组合，必须首先获得信号量，在拥有自旋锁时调用down(可导致休眠)是个严重的错误。

        在任何情况下使用spin_lock_irq都是安全的。因为它既禁止本地中断，又禁止内核抢占。

        spin_lock比spin_lock_irq速度快，但是它并不是任何情况下都是安全的。

        举个例子：进程A中调用了spin_lock(&lock)然后进入临界区，此时来了一个中断(interrupt)，该中断也运行在和进程A相同的CPU上，并且在该中断处理程序中恰巧也会spin_lock(&lock)试图获取同一个锁。由于是在同一个CPU上被中断，进程A会被设置为TASK_INTERRUPT状态，中断处理程序无法获得锁，会不停的忙等，由于进程A被设置为中断状态，schedule()进程调度就无法再调度进程A运行，这样就导致了死锁！但是如果该中断处理程序运行在不同的CPU上就不会触发死锁。 因为在不同的CPU上出现中断不会导致进程A的状态被设为TASK_INTERRUPT，只是换出。当中断处理程序忙等被换出后，进程A还是有机会获得CPU，执行并退出临界区。所以在使用spin_lock时要明确知道该锁不会在中断处理程序中使用。

        经常用于免锁的生产者/消费者任务的数据结构之一是循环缓冲区(circular buffer)。在这个算法中，一个生产者将数据放入数组的末尾，而消费者从数组的另一端移走数据。在达到数组尾部的时候，生产者绕回到数组的头部。因此，一个循环缓冲区需要一个数组以及两个索引值，一个用于下一个要写入新值的位置，而另一个用于应下一个从缓冲区中移走值的位置。在没有多个生产者或消费者的情况下，循环缓冲区不需要锁。

        当读取和写入指针相等时，表明缓冲区是空的，而只要写入指针马上要跑到读取指针的后面时(需谨慎处理交换)，就表明缓冲区已满。
        自旋锁常用函数如下：

spinlock_t slock;
spin_lock_init(&gsc->slock);
unsigned long flags = 0;
spin_lock_irqsave(&gsc->slock, flags);
spin_unlock_irqrestore(&gsc->slock, flags);

四、原子变量         

        原子整数类型：atomic_t

        ，不能记录大于24位的整数。

        这种类型的操作在SMP计算机的所有处理器上都确保是原子的。这种操作速度非常快，因为只要可能，它们就会被编译成单个机器指令。

        void atomic_set(atomic_t *v, int i);

        atomic_t v = ATOMIC_INIT(0);

        将原子变量v的值设置为整数值i。也可以在编译时利用ATOMIC_INIT宏来初始化原子变量的值。

        int atomic_read(atomic_t *v);

        返回v的当前值。

        void atomic_add(int i, atomic_t *v);

        将i累加到v指向的原子变量。返回值是void，这是因为返回新的值将带来额外的成本，而大多数情况下没有必要知道累加后的值。

        void atomic_sub(int i, atomic_t *v);

        从*v中减去i。

        void atomic_inc(atomic_t *v);

        void atomic_dec(atomic_t *v);

        增加或缩减一个原子变量。

        int atomic_add_return(int i, atomic_t *v);

        int atomic_sub_return(int i, atomic_t *v);

        atomic_t数据项必须只能通过上述函数来返回。如果将原子变量传递给了需要整型参数的函数，则会遇到编译错误。

        只有原子变量的数目是原子的，atomic_t变量才能工作。

五、位操作

        内核提供了一组可原子地修改和测试单个位的函数来实现位操作。

        除test_bit(nr, void *addr)以外都是原子的。

        void set_bit(nr, void *addr);
        设置addr指向的数据项的第nr位。

        void clear_bit(nr, void *addr);
        清除addr指向的数据项的第nr位，其原语和set_bit相反。

        void change_bit(nr, void *addr);
        切换指定的位。

        test_bit(nr, void *addr);

        该函数是唯一一个不必以原子方式实现的位操作函数，它仅仅返回指定位的当前值。
        int test_and_set_bit(nr, void *addr);

        int test_and_clear_bit(nr, void *addr);

        int test_and_change_bit(nr, void *addr);

        像前面列出的函数一样具有原子化的行为，例外之处是它同时返回这个位的先前值。上述函数相应位为0时，锁空闲，在非零时忙。

六、读取-复制-更新(RCU)

        RCU针对经常发生读取而很少写入的情形做了优化。被保护的资源应该通过指针访问，而对这些资源的引用必须仅由原子代码拥有。在需要修改该数据结构时，写入线程首先复制，然后修改副本，之后用新的版本替代相关指针，这也是该算法名称的由来。当内核确信老的版本上没有其他引用时，就可以释放老的版本。

        在读取端，代码使用受RCU保护的数据结构时，必须将引用数据结构的代码包括在rcu_read_lock和rcu_read_unlock调用之间，如下：

        struct my_stuff *stuff;

        rcu_read_lock();

        stuff = find_the_stuff(args...);

        do_something_with(stuff);

        rcu_read_unlock();

        rcu_read_lock调用非常快，它会禁止内核抢占，但不会等待任何东西。用来检验读取“锁”的代码必须是原子的。在调用rcu_read_unlock之后，就不应该存在对受保护结构的任何引用。

        RCU所做的就是，设置一个回调函数并等待所有的处理器被调度，之后由回调函数执行清除工作。