Linux 并发控制

一.概念
    1.并发（concurrency）指多个执行单元同时，并行被执行。
    2.并发的执行单元对共享资源，（比如说，硬件资源，全局变量，静态变量等）访问很容易导致竞态（race conditions）。
    3.造成竞态的主要原因：
        1.对称多处理器（SMP）
            多个CPU使用共同的系统总线，访问共同的外设和存储器。
        2.单CPU内进程与抢占它的进程
            高优先级抢占低优先级
        3.中断与进程之间
        4.中断与中断之间
    4.解决方案
        保证对共享资源的互斥访问。
        访问共享资源的代码区域称为临界区。
    5.方法：中断屏蔽，原子操作，自旋锁，信号量等
二、解决方法
    1.中断屏蔽（定义于 "#include"）
        在单CPU范围内避免竞态的一个简单方法。
        注意：
            中断对系统正常运行很重要，长时间屏蔽很危险，所以中断屏蔽后应尽可能快的执行完毕。
            宜与自旋锁联合使用。
        使用：      

/* 只能禁止和使能本地CPU的中断，所以不能解决多CPU引发的竞态 */
    local_irq_disable()
    local_irq_enable()

/* 除了能禁止和使能中断外，还保存和还原目前的CPU中断位信息 */
    local_irq_save(flags)
    local_irq_restore(flags)

/* 如果只是想禁止中断的底半部，这是个不错的选择 */
    local_bh_disable()
    local_bh_disable()

 
    2.原子操作
        在执行过程中不会被别的代码路径所中断的操作。
        分为两类：整型原子操作 和 位原子操作。
        特点：
            1.任何情况下操作都是原子的。
            2.都依赖底层的CPU的原子操作来实现，所以和CPU架构密切相关。
        注意：
            1.原子操作在不同体系架构实现的方法不同，基本采用汇编实现
            2.上述的整数原子函数集仅针对32位，内核中关于64位有另一套函数
            3.对于SMP系统，内核还提供了local_t数据类型，实现对单个CPU的整数原子操作，接口函数仅将atomic_替换成local_即可，定义于"linux/asm-generic/local.h"。
        I.整型原子操作
            定义于#include，分为 定义，获取，加减，测试，返回。

    void atomic_set(atomic_t *v,int i);     /* 设置原子变量v的值为i */
    atomic_t v = ATOMIC_INIT(0);            /* 定义原子变量v,并初始化为0 */

    atomic_read(atomic_t* v);               /* 返回原子变量v的值 */

    void atomic_add(int i, atomic_t* v);    /* 原子变量v增加i */
    void atomic_sub(int i, atomic_t* v);

    void atomic_inc(atomic_t* v);           /* 原子变量增加1 */
    void atomic_dec(atomic_t* v);


    int atomic_inc_and_test(atomic_t* v);   /* 先自增、自减和减操作后（没有加）,测试其值是否为0,若为0,则返回true,否则返回false */
    int atomic_dec_and_test(atomic_t* v);
    int atomic_sub_and_test(int i, atomic_t* v);


    int atomic_add_return(int i, atomic_t* v);    /* v的值加/减i和自增/自减操作后返回新的值 */
    int atomic_sub_return(int i, atomic_t* v);
    int atomic_inc_return(atomic_t* v);
    int atomic_dec_return(atomic_t* v);

        II.位原子操作
            定义于#include,分为 设置，清除，改变，测试           

    void set_bit(int nr, volatile void* addr);            /* 设置地址addr的第nr位,所谓设置位,就是把位写为1 */
    void clear_bit(int nr, volatile void* addr);          /* 清除地址addr的第nr位,所谓清除位,就是把位写为0 */

    void change_bit(int nr, volatile void* addr);         /* 对地址addr的第nr位反转 */

    int test_bit(int nr, volatile void* addr);            /* 返回地址addr的第nr位 */

    int test_and_set_bit(int nr, volatile void* addr);    /* 等同于先执行test_bit(nr,voidaddr)，然后在执行xxx_bit(nr,voidaddr) */
    int test_and_clear_bit(int nr, volatile void* addr);
    int test_and_change_bit(int nr, volatile void* addr);

        举个简单例子：      

static atomic_t xxx_available = ATOMIC_INIT(1);        /* init atomic */

int scull_open(struct inode *inode, struct file *filp)
{
    ...
    if(!atomic_dec_and_test(&xxx_available)){
        atomic_inc(&xxx_available);
        return -EBUSY;
    }
    ...
                   return 0;
}

int scull_release(struct inode *inode, struct file *filp)
{
    atomic_inc(&xxx_available);
    return 0;
}

    3.自旋锁
        I.自旋锁
            自旋锁是一种对临界资源进行互斥访问的典型手段，其名来源于它的工作方式。通俗的讲，自旋锁就是一个变量，该变量把一个临界区标记为“我当前在运行，请等待”或者标记为“我当前不在运行，可以被使用”：如果A执行单元首先获得锁，那么当B进入同一个例程时将获知自旋锁已被持有，需等待A释放后才能进入，所以B只好原地打转（自旋）。
            特点：
                1.自旋锁主要针对SMP或单CPU且内核可抢占的情况，对于单CPU且内核不可抢占的系统自旋锁退化为空操作
                2.尽管自旋锁可以保证临界区不受别的CPU和本CPU的抢占进程打扰，但是得到锁的代码路径在执行临界区的时候还可能受到中断和底半部影响，此时应该使用 自旋锁的衍生操作
            注意：
                1.自旋锁实际上是等于忙等待锁，所以要求占用锁的时间极短
                2.对于同一CPU或进程，不可递归使用自旋锁
                3.自旋锁锁定期间不能调用可能引起进程调度的函数，比如，copy_from_user(),copy_to_user(), kmalloc()，msleep()
            操作：
                定义于"#include"
点击(此处)折叠或打开

    spinlock_t lock;       /* 定义自旋锁 */

    spin_lock_init(&lock); /* 初始化自旋锁 */

    spin_lock(&lock);      /* 如不能获得锁，原地打转 */
    spin_trylock(&lock);   /* 尝试获得，如能获得锁返回真，不能获得返回假，不在原地打转 */

    spin_unlock(&lock);    /* 与spin_lock()和spin_trylock()配对使用 */

/* 自旋锁衍生操作 = 自旋锁+ 中断屏蔽 */
    spin_lock_irq()
    spin_unlock_irq()
    spin_lock_irqsave()
    spin_unlock_irqrestore()
    spin_lock_bh()
    spin_unlock_bh()

        II.读写自旋锁
            对共享资源并发访问时，多个执行单元同时读取它是不会有问题的，自旋锁的衍生锁读写自旋锁可允许读的并发。读写自旋锁（rwlock）是一种比自旋锁粒度更小的自旋锁机制，它保留了“自旋”的概念，但是在写操作方面，只能最多有一个写进程，在读方面，同时可拥有多个执行单元，当然读和写也不能同时进行。
            操作：定义于"#include"或"#include"

/* 定义和初始化读写自旋锁 */
    rwlock_t x;
    rwlock_init(&x);                    /* 动态初始化 */
    rwlock_t x=RW_LOCK_UNLOCKED;        /* 静态初始化 */

/* 读锁定 */
    void read_lock(rwlock_t *lock);     /* 如果不能获得，它将自旋，直到获得该读写锁 */
    void read_lock_irq(lock);           /* 读者获取读写锁，并禁止本地中断 */
    void read_lock_irqsave(rwlock_t *lock, unsigned long flags);    /* 读者获取读写锁，同时保存中断标志，并禁止本地中断 */
    void read_lock_bh(lock);            /* 读者获取读写锁，并禁止本地软中断 */

/* 读解锁 */
    void read_unlock(rwlock_t *lock);
    void read_unlock_irq(rwlock_t *lock);        /* 读者释放读写锁，并使能本地中断 */
    void read_unlock_irqrestores(rwlock_t *lock, unsigned long flags);    /* 读者释放读写锁，同时恢复中断标志，并使能本地中断 */
    void read_unlock_bh(rwlock_t *lock);
    /* 在对共享资源进行读取之前,应该先调用读锁定函数锁定共享资源,完成之后再调用读解锁函数释放共享资源 */

/* 写锁定 */
    void write_lock(rwlock_t *lock);            /* 如果不能获得，它将自旋，直到获得该读写锁 */
    void write_lock_irq(rwlock_t *lock);        /* 写者获取读写锁，并禁止本地中断 */
    void write_lock_irqsave(rwlock_t *lock, unsigned long flags);        /* 写者获取读写锁，同时保存中断标志，并禁止本地中断 */
    void write_lock_bh(rwlock_t *lock);         /* 写者获取读写锁，并禁止本地软中断 */
    void write_trylock(rwlock_t *lock);

/* 写解锁 */
    void write_unlock(rwlock_t *lock);
    void write_unlock_irq(rwlock_t *lock);
    void write_unlock_irqstore(rwlock_t *lock, unsigned long flags);
    void write_unlock_bh(rwlock_t *lock);
    /* 在对共享资源进行写操作之前,应该先调用写锁定函数锁定共享资源,完成之后再调用写解锁函数释放共享资源 */

 
         III.顺序锁
            顺序锁是对读写锁的一种优化。
                1.读执行单元绝对不会被写执行单元阻塞。即读执行单元可以在写执行单元对被顺序锁保护的共享资源进行写操作的同时仍然可以继续读,而不必等待写执行单元完成之后再去读,同样,写执行单元也不必等待所有的读执行单元读完之后才去进行写操作
                2.写执行单元与写执行单元之间仍然是互斥的
                3.如果读执行单元在读操作期间,写执行单元已经发生了写操作,那么,读执行单元必须重新去读数据,以便确保读到的数据是完整的
                4.要求共享资源中不能含有指针
            注意：
                1.顺序锁：允许读和写操作之间的并发,也允许读与读操作之间的并发,但写与写操作之间只能是互斥的、串行的
                2.读写自旋锁：只允许读操作与读操作之间的并发,而读与写操作，写与写操作之间只能是互斥的、串行的
                3.自旋锁：不允许任何操作之间并发

    seqlock_init(x);             /* 动态初始化 */
    DEFINE_SEQLOCK(x);           /* 静态初始化 */

    void write_seqlock(seqlock_t* sl);      /* 写加锁 */
    int write_tryseqlock(seqlock_t* sl);    /* 尝试写加锁 */
    write_seqlock_irqsave(lock, flags);     /* local_irq_save() + write_seqlock() */
    write_seqlock_irq(lock);                /* local_irq_disable() + write_seqlock() */
    write_seqlock_bh(lock);                 /* local_bh_disable() + write_seqlock() */

    void write_sequnlock(seqlock_t* sl);    /* 写解锁 */
    write_sequnlock_irqrestore(lock, flags);/* write_sequnlock() + local_irq_restore() */
    write_sequnlock_irq(lock);              /* write_sequnlock() + local_irq_enable() */
    write_sequnlock_bh(lock);               /* write_sequnlock() + local_bh_enable() */

            A.读操作:

    unsigned int read_seqbegin(const seqlock_t* sl);
    read_seqbegin_irqsave(lock, flags);     /* local_irq_save() + read_seqbegin() */

                读执行单元在访问共享资源时要调用顺序锁的读函数,返回顺序锁s1的顺序号;该函数没有任何获得锁和释放锁的开销,只是简单地返回顺序锁当前的序号;
            B.重读操作:

    int read_seqretry(const seqlock_t* sl, unsigned start);
    read_seqretry_irqrestore(lock, iv, flags);

                在顺序锁的一次读操作结束之后,调用顺序锁的重读函数,用于检查是否有写执行单元对共享资源进行过写操作;如果有,则需要重新读取共享资源;iv为顺序锁的顺序号;
            用例：

    write_seqlock(&seqlock);
    ...... /* 写操作代码 */
    write_sequnlock(&seqlock);

    unsigned int seq_num = 0;
    do
    {
      seq_num = read_seqbegin(&seqlock);
      /* 读操作代码 */
      ......
    } while(read_seqretry(&seqlock, seq_num));

                注：如果写执行单元在操作被顺序锁保护的共享资源时已经保持了互斥锁保护对共享资源的写操作,即:写执行单元与写执行单元之间已经是互斥的,但是读执行单元仍然可以与写执行单元同时访问,那么这种情况下仅需要使用顺序计数(struct seqcount)即可,而不必使用spinlock。使用顺序计数必须非常小心,只有确定在访问共享资源时已经保持了互斥锁才可以使用;即:只有写操作与写操作之间已经是互斥的、串行的时,才可以使用顺序计数。

        IV.RCU
             参照http://blog.csdn.net/williamwang2013/article/details/8524519

    4.信号量
        I.信号量
            信号量(semaphore)是用于保护临界区的一种常用方法,它的使用方式与自旋锁类似与自旋锁相同的是,只有得到信号量的进程才能执行临界区的代码与自旋锁不同的是,当获取不到信号量的时候,进程不会在原地打转,而是进入休眠等待状态;
            理解：
                定义于"#include"

/* 定义信号量 */
    struct semaphore sem;

/* 初始化信号量 */
    void sema_init(struct semaphore *sem, int val);        /* 尽管信号量可以初始化为大于1的值从而成为一个计数信号量，但是通常不被这样使用 */
    #define init_MUTEX(sem)           sema_init(sem, 1)    /* 初始化一个值为1的互斥信号量 */
    #define init_MUTEX_LOCKED(sem)    sema_init(sem, 0)    /* 初始化一个信号量，值为0 */
    DECLARE_MUTEX(name)                /* 初始化信号量的"快捷方式" */
    DECLARE_MUTEX_LOCKED(name)

/* 获得信号量 */
    void dowm(struct semaphore *sem);                      /* 会导致睡眠，不能用于上下文 */
    int down_interruptible(struct semaphore *sem);         /* 进入睡眠状态的进程能被信号打算。也会导致该函数返回。返回非0 */
    int down_trylock(struct semaphore *sem);               /* 立刻返回，不会导致睡眠，能用于上下文 */

/* 释放信号量 */
    void up(struct semaphore *sem);

        II.同步
            如果信号量被初始化为0，则它可以用于同步，同步意味着一个执行单元的继续执行需要等待另一执行单元完成某事，保证执行的先后顺序。
                            执行单元A                                        执行单元B
                            struct semaphore sem
                            init_MUTEX_LOCKED(&sem);
                            代码区域a                                
                            down(&sem);
                            代码区域b                                        代码区域c
                                                                            up(&sem);
            执行单元A执行代码区域b之前，必须等待执行单元B执行完成代码单元c，信号量可辅助这一同步过程。

        III.完成量
            表示一个执行单元需要等待另一个执行单元完成某事后方可执行。
                1.它是一种轻量级机制，为了完成进程间的同步而设计
                2.使用完成量等待时，调用进程是以独占睡眠方式进行等待的
                3.不是忙等待
            操作：

/* 定义完成量 */
    struct completion my_completion;       /* 定义名为my_completion的完成量 */

/* 初始化completion */
    init_completion(my_completion);        /* 初始化my_completion的完成量 */
    DECLARE_COMPLETION(my_completion);     /* 定义和初始化的快捷方式 */

/* 等待完成量 */
    void wait_for_completion(struct completion *c);    /* 等待一个completion被唤醒 */

/* 唤醒完成量 */
    void comlpetion(struct completion *c);
    void completion_all(struct comp;etion *c);
    /* 前者只唤醒一个等待的执行单元，后者释放所有等待同一完成量的执行单元 */

        IV.读写信号量
            读写信号量与信号量之间的关系类似于自旋锁与读写自旋锁。读写信号量可能会引起进程阻塞,但是它允许N个读执行单元同时访问共享资源,而最多只允许有一个写执行单元访问共享资源;因此,读写信号量是一种相对放宽条件的、粒度稍大于信号量的互斥机制。
            操作：

/* 定义和初始化读写信号量 */
    struct rw_semaphore rw_sem;                    /* 定义读写信号量 */
    void init_rwsem(struct rw_semaphore* rw_sem);  /* 初始化读写信号量 */

/* 读信号获取 */
    void down_read(struct rw_semaphore* rw_sem);
    int down_read_trylock(struct rw_semaphore* rw_sem);

/* 读信号量释放 */
    void up_read(struct rw_semaphore* rw_sem);

/* 写信号获取 */
    void down_write(struct rw_semaphore* rw_sem);
    int down_write_trylock(struct rw_semaphore* rw_sem);

/* 写信号释放 */
    void up_write(struct rw_semaphore* rw_sem);

            读写信号量一般这样被使用：

    rw_semaphore sem; /* 定义读写信号量 */
    init_rwsem(&sem); /* 初始化读写信号量 */

    /*读时获取信号量*/
    down_read(&sem);
    ...... /* 临街资源 */
    up_read(&sem);

    /*写时获取信号量*/
    down_write(&sem);
    ...... /* 临街资源 */
    up_write(&sem);

       
        V.互斥体
            尽管信号量已经实现了互斥的功能，但是“正宗”的mutex在Linux中还是真实地存在的。
            下面代码定义my_mutex的互斥体并初始化：

    struct mutex my_mutex;
    mutex_init(&my_mutex);

            下面的两个函数用于获取互斥体：

    void inline __sched mutex_lock(struct mutex *lock);
    int __ sched mutex_lock_interruptible(struct mutex *lock);
    int __ sched mutex_trylock(struct mutex *lock);

        下列函数用于释放互斥体：

    void __sched nutex_unlock(struct mutex *lock);

        mutex的使用方法和信号量用于互斥的场合完全一样：

    struct mutex my_mutex;     /* 定义mutex */
    mutex_init(&my_mutex);     /* 初始化mutex */


    mutex_lock(&my_mutex);     /* 获取mutex */
    ...... /* 临街资源 */
    mutex_unlock(&my_mutex);   /* 释放mutex */