1、 并发及其管理
竞态通常作为对资源的共享访问结果而产生。
资源共享的硬规则：在单个执行线程之外共享硬件或软件资源的任何时候，因为另外一个线程可能产生对该资源的不一致观察，因此必须显式地管理对该资源的访问。
一个重要的规则：当内核代码创建了一个可能和其他内核部分共享的对象时，该对象必须在还有其他组件引用自己时保持存在（并正确工作）。
2、 信号量和互斥体
临界区：在任意给定的时刻，代码只能被一个线程执行；
进入休眠：当一个linux进程到达某个时间点，此时它不能进行任何处理时，它将进入休眠（或“阻塞”）状态，这将把处理器让给其他执行线程直到将来它能够继续完成自己的处理为止。
互斥体：当信号量用于互斥时（即避免多个进行同时在一个临界区中运行），信号量的值应初始化为1。这种信号量在任何给定时刻只能由单个进程或线程拥有。
Linux内核中几乎所有的信号量均用于互斥。
a) Linux信号量的实现
信号量的创建：void sema_init(struct semaphore *sem, int val);
互斥体的初始化：
DECLARE_MUTEX(name);
DECLARE_MUTEX_LOCKED(name);
void init_MUTEX(struct semaphore *sem);
void init_MUTEX_LOCKED(struct semaphore *sem);
相关函数：
void down(struct semaphore *sem);
int down_interruptible(struct semaphore *sem);
iInt down_trylock(struct semaphore *sem);
void up(struct semaphore *sem);
注：down减小信号量的值，并在必要时一直等待；down_interruptible完成相同的工作，但操作是可中断的，对其的正确使用需要始终检查返回值，并作出相应的响应；down_trylock永远不会休眠，若信号量在调用时不可获取，它会立即返回一个非零值。
如果在拥有一个信号量时发生错误，必须在将错误状态返回给调用者之前释放该信号量。
正确使用锁定机制的关键是：明确指定需要保护的资源，并确保每一个对这些资源的访问使用正确的锁定。
b) 读取者/写入者信号量
读取者/写入者信号量包含在中；
初始化：void init_rwsem(struct rw_semaphore *sem);
相关函数：
void down_read(struct rw_semaphore *sem);
iInt down_read_trylock(struct rw_semaphore *sem);
void up_read(struct rw_semaphore *sem);
void down_write(struct rw_semaphore *sem);
void down_write_trylock(struct rw_semaphore *sem);
void up_write(struct rw_semaphore *sem);
void downgrade_write(struct rw_semaphore *sem);
注：down_read可能会将调用进程置于不可中断的休眠；down_read_trylock不会在读取访问不可获得时等待；它在授予访问时返回非零，其他情况下返回零。
当某个快速改变获得了写入者锁，而其后是更长时间的只读访问，可在结束修改之后调用downgrade_write，来允许其他读取者的访问。
最好在很少需要写访问且写入者只会短期拥有信号量的时候使用rwsem。
3、 Completion
Completion是一种轻量级的机制，它允许一个线程告诉另一个线程某个工作已经完成。
其包含在中；
创建：
DECLARE_COMPLETION(my_completion);
struct completion my_completion;
init_completion(my_completion);
等待completion：void wait_for_completion(struct completion *c);
调用的函数：
void complete(struct completion *c);
void complete_all(struct completion *c);
complete唤醒一个等待线程；complete_all唤醒所有等待线程；
如果使用了complete_all，则必须在重复使用该结构之前重新初始化它。
初始化：INIT_COMPLETION(struct completion c);
Completion机制的典型使用是模块退出时的内核线程终止。
void complete_and_exit(struct completion *c, long retval);通过调用complete并调用当前线程的exit函数而发出completion事件信号。
4、 自旋锁
a) 定义：一个自旋锁是一个互斥设备，它只能有两个值：“锁定”和“解锁”。它通常实现为某个整数值中的单个位。它可在不能休眠的代码中使用。
b) 自旋锁API介绍
其包含在头文件；
编译时初始化：spinlock_t my_lock = SPIN_LOCK_UNLOCKED;
运行时初始化：void spin_lock_init(spinlock_t *lock);
获取锁：void spin_lock(spinlock_t *lock);
释放锁：void spin_unlock(spinlock_t *lock);
c) 自旋锁和原子上下文
自旋锁的核心原则：任何拥有自旋锁的代码都必须是原子的。它不能休眠，事实上，它不能因为任何原因放弃处理器，除了服务中断以外（某些情况下此时也不能放弃处理器）。
为了避免因为中断造成的死锁，需要在拥有自旋锁时禁止中断（仅在本地CPU上）。
自旋锁的另一个重要规则：自旋锁必须在可能的最短时间内拥有。
d) 自旋锁函数
四个锁定自旋锁的函数：
void spin_lock(spinlock_t *lock);
void spin_lock_irqsave(spinlock_t *lock, unsigned long flags);
void spin_lock_irq(spinlock_t *lock);
void spin_lock_bh(spinlock_t *lock);
spin_lock_irqsave会在获得自旋锁之前禁止中断（只在本地处理器上），先前中断状态保存在flags中；
spin_lock_irq用于能够确保没有任何其他代码禁止本地处理器的中断（即能够确保在释放自旋锁时应该启用中断）；
spin_lock_bh在获得锁之前禁止软件中断，保持硬件中断打开；
四个释放自旋锁的函数：
void spin_unlock(spinlock_t *lock);
void spin_unlock_irqsave(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);
注：这两个函数成功返回非0值，否则返回0。对于禁止中断的情况，没有对应的“try”版本。
e) 读取者/写入者自旋锁
两种声明和初始化方式：
rwlock_t my_rwlock = RW_LOCK_UNLOCKED;
rwlock_t my_rwlock;
rwlock_init(&my_rwlock);
对于读取者有如下函数：
void read_lock(rwlock_t *lock);
void read_lock_irqsave(rwlock_t *lock, unsigned long flags);
void read_lock_irq(rwlock_t *lock);
void read_lock_bh(rwlock_t *lock);
void read_unlock(rwlock_t *lock);
void read_unlock_irqsave(rwlock_t *lock, unsigned long flags);
void read_unlock_irq(rwlock_t *lock);
void read_unlock_bh(rwlock_t *lock);
注：没有read_trylock函数。
对于写入者有如下函数：
void write_lock(rwlock_t *lock);
void write_lock_irqsave(rwlock_t *lock, unsigned long flags);
void write_lock_irq(rwlock_t *lock);
void write_lock_bh(rwlock_t *lock);
int write_trylock(rwlock_t *lock);
void write_unlock(rwlock_t *lock);
void write_unlock_irqsave(rwlock_t *lock, unsigned long flags);
void write_unlock_irq(rwlock_t *lock);
void write_unlock_bh(rwlock_t *lock);
5、 锁陷阱
a) 不明确的规则
创建一个可被并行访问的对象时，应同时定义用来控制访问的锁。
若某个获得锁的函数要调用其他同样试图获取这个锁的函数，代码就会死锁。
通常，内部的静态函数可通过这种方式（假定调用者已获取相关锁）编写，而提供给外部调用的函数则必须显示地处理锁定。在编写假定调用者已处理了锁定的内部函数时，应该显式说明这种假定。
b) 锁的顺序规则
在必须获取多个锁时，应始终以相同的顺序获得。
两个规则：若必须获取一个局部锁和一个属于内核更中心位置的锁，应该首先获取自己的局部锁；若拥有信号量和自旋锁的组合，则必须首先获得信号量，在拥有自旋锁时调用down（可导致休眠）是个严重的错误。
最后的办法是避免出现需要多个锁的情况。
c) 细粒度锁和粗粒度锁的对比
通常的规则：应该在最初使用粗粒度的锁，除非有真正的原因相信竞争会导致问题。
Lockmeter工具可度量内核花费在锁上的时间。
6、 除了锁之外的办法
a) 免锁算法
经常用于免锁的生产者/消费者任务的数据结构之一是循环缓冲区，其可用于多读取者/单个写入者情况。
b) 原子变量
内核提供了一种原子的整数类型，称为atomic_t，定义在；
在atomic_t变量中不能记录大于24位的整数。
atomic_t变量必须通过相应函数访问。
初始化：void atomic_set(atomic_t *v, int i); atomic_t v =ATOMIC_INIT(0);
获取值：int atomic_read(atomic_t *v);
加法：void atomic_add(int i, atomic_t *v);
减法：void atomic_sub(int i, atomic_t *v);
递增：void atomic_inc(atomic_t *v);
递减：void atomic_dec(atomic_t *v);
执行特定操作并测试结果：
int atomic_inc_and_test(atomic_t *v);
int atomic_dec_and_test(atomic_t *v);
int atomic_sub_and_test(int i, atomic_t *v);
注：操作结束后，原子值为0，返回true，否则返回false。
将整数变量i累加到v：int atomic_add_negative(int i, atomic_t *v);返回值在结果为负时为true，否则为false。
类似于atomic_add及其变种：
int atomic_add_return(int i, atomic_t *v);
int atomic_sub_return(int i, atomic_t *v);
int atomic_inc_return(atomic_t *v);
int atomic_dec_return(atomic_t *v);
将院子变量传递给需要整型参数的函数，会出现编译错误。
只有原子变量的数目是原子的，atomic_t变量才能工作。需要多个atomic_t变量的操作，仍需要某种类型的锁。
c) 位操作
原子位操作非常快，只要底层硬件允许，这种操作就可以使用单个机器指令来执行，并且不需要禁止中断。这些函数依赖于具体的架构，因此在中声明。
设置第nr位：void set_bit(nr, void *addr);
清除第nr位：void clear_bit(nr, void *addr);
切换第nr位：void change_bit(nr, void *addr);
返回指定位的当前值：test_bit(nr, void *addr);
返回第nr位的当前值：
int test_and_set_bit(nr, void *addr);
int test_and_clear_bit(nr, void *addr);
int test_and_change_bit(nr, void *addr);
d) Seqlock
Seqlock用于要保护的资源很小，很简单，会频繁被访问而且写入访问很少发生且必须快速时。
Seqlock通常不能用于保护包含有指针的数据结构，因为在写入者修改该数据结构的同时，读取者可能会追随一个无效的指针。
Seqlock在中定义。
其初始化有两种方式：
seqlock_t lock1 = SEQLOCK_UNLOCKED;
seqlock_t lock2;
seqlock_init(&lock2);
读取锁相关函数：
unsigned int read_seqbegin(seqlock_t *lock);
int read_seqretry(seqlock_t *lock, unsigned int seq);
unsigned int read_seqbegin_irqsave(seqlock_t *lock, unsigned long flags);
int read_seqretry_irqstore(seqlock_t *lock, unsigned int seq, unsigned long flags);
写入锁相关函数：
void write_seqlock(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(seqlock_t *lock);
void write_sequnlock_irqsave(seqlock_t *lock, unsigned long flags);
void write_sequnlock_irq(seqlock_t *lock);
void write_sequnlock_bh(seqlock_t *lock);
如果write_tryseqlock可以获得自旋锁，它也会返回非零值。
e) 读取-复制-更新(read-copy-update,RCU)
RCU针对经常发生读取而很少写入的情形。在需要修改该数据结构时，写入线程首先复制，然后修改副本，之后用新的版本替代相关指针。
其包含在中。
RCU很少用于驱动程序。
相关函数：
void rcu_read_lock();
void rcu_read_unlock();
void call_rcu(struct rec_head *head, void (*func)(void *arg), void *arg);
call_rcu准备用于安全释放受RCU保护的资源的回调函数，该函数将在所有的处理器被调度后运行。
