综述

并发问题是编程中经常遇到的难题，我们需要学会针对并发产生的竞态进行编程

一、信号量和互斥体

Linux上信号量的实现

1.信号量:本质上是一个整数值，它和一对函数联合使用，这对函数通常称为P和V，希望进入临界区的进程将在相关信号量上调用P，如果信号量大于0，该值减1，进程可以进入临界区代码运行；相反，如果信号量的值<=0,进程必须等待其他人释放该信号量。解锁信号量调用V函数，该函数增加信号量的值，并在必要时唤醒等待的进程。

当信号量用于互斥时(即避免多个进程同时在一个临界区中运行)
信号量应初始化为1
这种信号量在任何时刻只能由单个进程或者线程拥有，这种模式下，
信号量也成为互斥体
2.声明和初始化
void sema_init(strcut semaphore *sem,int val);
sem代表信号量，val代表初始值，一般初始化为1.
DECLARE_MUTEX(name):一个名称为name的信号量被初始化为1
DECLARE_MUTEX_LOCKED(name):一个名称为name的信号量被初始化为0

void init_MUTEX(stuct semaphore *sem)：
void init_MUTEX_LOCKED(stuct semaphore *sem)：
LINUX2.6版本后已经被遗弃 无法使用

Linux中的P函数是down(),该函数会减少信号量的值，必要时会一直等待。
void down(struct semaphore *sem)
减少信号量的值 并在必要时一直等待，操作不可中断
void down_interruptible(struct semaphore *sem)
完成和down相同的工作，但是操作是可中断，通常推荐使用，如果操作被中断，该函数返回非零值，而调用者不会拥有该信号，使用时注意检查返回值，并且做出相应的操作。
int down_trylock(struct semaphore *sem)
永远不会休眠，如果信号量在调用时不可获得，该函数会立即返回一个非零值。

当一个函数成功调用上述的down函数，就称为该线程拥有(获得、拿到)了该信号量，这样该线程就被赋予访问由该信号量保护的临界区的权利，当互斥操作完成后，必须返回该信号量，即调用V函数

void up(strcut semaphore *sem);
调用后，调用者不在拥有该信号量。

使用信号量实例

步骤1:定义信号量
在自己的定义的结构体加入semaphore *sem;//互斥信号量
步骤2:初始化信号量
sema_init(sem,1)；
默认初始化信号量sem的值为1
步骤3:
在要保护的资源调用dowm_interruptible();
if(dowm_interruptible(&sem))
retrun -ERESTARTSYS;
//这里是要保护资源的代码
out:
up(&sem);
在函数调用up最后释放信号量

strcut hello_dev{
  int val;
  semaphore *sem;//互斥信号量
}
static hello_init()
{
//初始化信号量
sema_init(dev->sem,1);
}
/*读取寄存器设备 val的值*/
static ssize_t hello_read(struct file *filp,char __user *buf,
size_t count,loff_t *f_ops) {
    ssize_t err = 0;
    struct hello_dev *dev = filp->private_data;

    /*同步访问*/
    if(down_interruptible(&(dev->sem)));
        return -ERESTARTSYS;
    
    if(count < sizeof(dev->val)){
        goto out;
    }
    /*将寄存器val的值拷贝到用户提供的缓存区*/
    if(copy_to_user(buf,&(dev->val),sizeof(dev->val))){
        err = -EFAULT;
        goto out;
    }

    out:
    up(&(dev->sem));
    return err;
}

读取者/写入者信号量

许多任务可分为:
1.只需要读取受保护的数据（多个进程和线程可以同时并发访问）
2.写入受保护的数据
为此,Linux提供了特殊的信号量"rwsem"(或者reader/writer semaphore),rwsem使用很少，偶尔有用

相关定义包含在<linux/rwsem.h>头文件中
struct rw_semaphore *sem;
初始化:
void init_rwsem(struct rw_semaphore *sem);

对于只读访问，可用接口如下:
void down_read(struct rw_semaphore *sem);
int down_read_trylock(struct rw_semaphore *sem);;
void up_read(struct rw_semaphore *sem);
对于写入访问，可用接口如下：
void down_write(struct rw_semaphore *sem);
int down_write_trylock(struct rw_semaphore *sem);
void up_write(struct rw_semaphore *sem);
void downgrade_write(struct rw_semaphore *sem);
downgrade_write允许其他读取者访问

完成量

completion是一种轻量级的机制，它允许一个线程告诉另一个线程某个工作已经完成了，包含在<linux/completion.h>中
1.创建和初始化completion
DECLARE_COMPLETION(my_com);
或者动态创建和初始化
strcut completion my_com;
inti_completion(&my_com);
2.等待completion
void wait_for_completion(strcut completion *c);
注意，该函数执行一个非中断等待，如果代码调用了该函数且没人能完成该信号量，则会产生一个不可杀进程！
3.唤醒completion
void completion(struct completion *c);
void complete_all(struct completion *c);
快速重新初始化某个复用的completion
INIT_COMPLETION(struct completion c);

自旋锁

信号量在互斥中是非常有用的工具，内核还提供另一种工具--自旋锁。
和信号量不同，自旋锁可以在休眠的代码中使用，如中断处理例程，正确使用的情况下，自旋锁性能比信号量好！

自旋锁API

初始化
自旋锁相关定义包含在头文件<linux/spinlock.h>中
编译时初始化
strcuvt spinlock_t my_lock;
my_lock = SPIN_LOCK_UNLOCKED;
或者
运行时初始化
void spin_lock_init(spinlock_t *lock);
进入临界区之前，必须调用以下函数获取锁
void spin_lock(spinlock_t *lock);
注意：所以自旋锁本质上都是不可中断的，一旦调用了spin_lock，在获取锁之前一直处于自旋状态

释放锁函数
void spin_unlock(spinlock_t *lock);

注意:为了避免
在中断例程自旋时，非中断代码将没有机会释放这种个自旋锁，导致处理器将永远自旋下去的情况
我们需要在拥有自旋锁时禁止中断(仅本地CPU上)，下面的函数可以实现用于禁止中断的自旋锁函数。
另一个重要原则:自旋转必须的在尽可能短的时间内拥有！

自旋锁函数
void spin_lock(spinlock_t *lock):允许中断的自旋锁
void spin_lock_irqsave(spinlock_t *lock,unsigned long flags)
在获得自旋锁之前禁止中断(只在本地cup上),先前中断报错在flags中
void spin_lock_irq(spinlock_t *lock)
如果我们能确保没有任何其他代码禁止本地处理器的中断，则可以使用spin_lock_irq，而无需跟踪标志！
void spin_lock_bh(spinlock_t *lock)
在获得锁之前禁止软件中断，允许硬件中断打开
该函数可以安全的避免死锁问题，还能服务硬件中断
释放锁函数

void spin_unlock(spinlock_t *lock):
void spin_unlock_irqrestore(spinlock_t *lock,unsigned long flags)

void spin_unlock_irq(spinlock_t *lock)
void spin_unlock_bh(spinlock_t *lock)

非阻塞式自旋锁
int spin_trylock(spinlock_t *lock);
int spin_trylock_bh(spinlock_t *lock);
两个函数在成功获取自旋锁时，返回非零值，失败时返回零，对应禁止中断的情况没有对应的try版本
读取者/写入者自旋锁
和rwsem信号量很相似，但是可能会造成读取者饥饿，导致性能变低！

注意防止死锁情况
死锁1:当某个获得锁的函数要调用其他同样试图获取这个锁的函数，代码就会死锁，无论是信号量还是自旋锁，都不允许锁拥有者第二次获得这个锁

死锁2:线程1拥有锁1，线程2拥有锁2，这时候，当这两个线程都试图获取另外线程的的锁时，这两个线程将处于死锁状态
最好的办法是避免同时需要多个锁的情况

锁之外的办法

1.免锁算法

常用于免锁算法的生产者/消费者任务的数据结构就是循环缓冲区！

2.原子变量

共享资源是一个简单的整数型时，内核提供了一种原子的整数类型
称为atomic_t 定义在<asm/atomic.h>中
初始化
void atomic_set(atomic *v,int t);
或者
atomic_t v = ATOMIC_INIT(0);初始化为0
还有读写函数，运算操作函数，位操作函数就不一一列举了

3.seqlock

当要保护的资源很小、很简单、会被频繁读取访问且写入访问很少发生且必须快速时，就可以使用内核提供的seqlock
允许读取者自由访问，但是需要读取者检测是否和写入者冲突
seqlock通常不能包含在含有指针的数据结构中，因为在写入者修改数据结构的同时，读取者可能会追随一个无效的指针。

seqlock定义在<linux/seqlock.h>
初始化方法2种
1.seqlock_t lock1 = SEQLOCK_UNLOCKED;
2.seqlock_t lock2;
seqlock_init(&lock2);

读取时会访问通过一个(无符号的)整数顺序值而进入临界区，在退出时，该顺序值和当前值比较，如果不相等，必须重试读取访问。

unsigned int seq;
do {
  seq = read_seqbegin(&the_lock);
  /*完成需要做的工作*/
}while read_seqretry(&the_lock,seq);

如果在中断处理例程中使用seqlock,则应该使用IRQ安全的版本

unsigned int read_seqbegin_irqsave(seqlock_t *lock,unsigned long flags);
int read_seqretry_irqrestore(seqlock_t *lock,unsigned int seq,
                                                        unsigned long flags);

写入者必须进入由seqlock包含的临界区时获得一个互斥锁，因此要调用以下函数:
void write_sequnlock(seqlock_t *lock);
还有其他常见自旋锁的变种函数

void write_seqlock_irqsave(seqlock_t *lock,unsigned long flags);
void write_seqlock_irq(seqlock_t *lock);
void write_seqlock_bh(seqlock_t *lock);

void write_sequnlock_irqrestore(seqlock_t *lock,unsigned long flags);
void write_sequnlock_irq(seqlock_t *lock);
void write_sequnlock_bh(seqlock_t *lock);

另外
如果write_tryseqlock()可以获得自旋锁，它也会返回非0值。

读取-复制-更新（read-copy-update,RCU）

RCU是一种高级的互斥机制，正确使用下，也可获得很高的性能，但很少在驱动程序中使用。
RCU针对经常发生读取而很少写入的情形做了优化，被保护的资源应通过指针访问，而对这些资源的引用必须由原子代码拥有！

#include <linux/rcupdate.h>
使用读取-复制-更新(RCU)机制是需要包含的头文件
void rcu_read_lock();
void rcu_read_unlock();
获取对受RCU保护资源的读取访问的宏
void call_rcu(srcut rcu_head head,void (func)(void *arg),void *arg);
准备用于安全示范受RCU保护的资源的回调函数，该函数将在所有的处理器被调度后运行！