并发与竞态
什么是并发和竞态
并发
多个执行单元（进程与线程）同时进行，并行被操作。由于虚拟设备机制，每一个执行单元都认为自己独占了CPU和硬件资源。
竞态发生的条件
- 对称多处理器SMP的多个CPU。SMP是紧耦合、共享存储的系统模型。特点是其多个CPU能够使用共同的系统总线，可以访问共同的外设和存储器。
- 单核CPU，抢占的进程。从Linux2.6开始支持内核抢占调度，一个进程 在内核执行 的过程中可能被另一个高优先级进程大端。
- 中断（硬中断，软中断，tasklet，底半部）与进程之间：中断可以打断正在执行的进程，处理中断的程序和被打断的进程间也可能发生竞态。
竞态解决的方法
对共享资源的互斥访问。访问共享资源的代码段成为临界区，进入临界区时要进行互斥保护。
Linux下常见的互斥保护为：
- 中断屏蔽（禁止中断抢占）
- 原子操作（只能对整数操作）
- 自旋锁
- 信号量
竞态解决方法
中断屏蔽
- 单CPU中，在进入临界区之前将进程状态设置为中断屏蔽状态，进入临界区之后将不会被抢占。
- 注意：linux的异步IO，进程调度（时间片轮转）等都是通过中断来实现的。使用中断屏蔽会产生中断信号丢失，中断不响应等问题。所以临界区必须尽快完成，代码量要少。
原子操作
提供一套API使得在原子操作在执行的过程中不会被其他进程终端操作。主要分为整形原子操作和位原子操作。依赖CPU底层原子操作实现。
自旋锁
自旋锁是一个可以执行原子操作的内存变量。进程在进入临界区之前要先尝试获得自旋锁。
- 如果进程获得自旋锁，则进程进入临界区执行。
- 自旋锁被占用，进程将在一个小循环内不断检查自旋锁状态。
- 注意事项：*
- 自旋锁是忙等待，占用CPU时间。只有在占用锁消耗小于进程切换消耗的时候才适用。
- 自旋锁可能会导致死锁。（递归调用的时候，获得锁之后继续尝试获得锁）
- 自旋锁期间不能调用任何引起进程调度的函数。
具体操作： #include <linux/spinlock.h>
- 定义自旋锁
spinlock_t lock; - 初始化自旋锁
spin_lock_init(lock); - 获得自旋锁
spin_lock(lock);spin_trylock(lock); //如果获取不到返回false，不在原地打转 - 释放自旋锁
spin_unlock(lock); - 为了保证不被中断打断，衍生
spin_lock_irq() = spin_lock() + local_irq_disable()spin_unlock_irq() = spin_unlock() + local_irq_enable()spin_lock_irqsave() = spin_lock() + local_irq_save()spin_unlock_irqrestore() = spin_unlock() + local_irq_restore()spin_lock_bh() = spin_lock() + local_bh_disable()spin_unlock_bh() = spin_unlock() + local_bh_disable()
基于自旋锁衍生成：
读写锁
- 允许读并发
- 不允许写并发
顺序锁
- 读写锁的优化
- 读进程在写进程对共享资源操作时仍然可以读取，但不保证读取是正确的
RCU read-copy-update
多个读，多个写。
写的时候先复制，再在复制内容上写，在该共享资源被最后一个进程释放后对共享资源进行更新。
信号量semaphore
信号量也是一个可以执行原子操作的内存变量，进程在进入临界区之前试图获取信号量。经典的PV操作。信号量为正时，可以获得。信号量为非正时，不可获得
- 进程获取信号量，进入临界区执行。
- 进程获取失败，进程将自己挂起，让出CPU。等待其他进程唤醒。
基本操作：
- 定义信号量：
struct semaphore sema; - 初始化信号量：
void sema_init(struct semaphore *sem, int val); - 获取信号量：
void down(struct semaphore *sem);//获得信号量sem，其会导致睡眠，并不能被信号打断int down_interruptible(struct semaphore *sem);//进入睡眠可以被信号打断int down_trylock(struct semaphore *sem);//不会睡眠 - 释放信号量：
void up(struct semaphore *sem);//释放信号量，唤醒等待进程
基于信号量衍生：
Completion
用于linux中的同步