1. 对并发的管理是操作系统编程的核心的问题之一。
2. 早期并发的惟一原因是对硬件的中断服务，没有抢占和SMP。
Scull的缺陷
1. 竞态会导致对共享数据的非控制访问。
2. 竞态是一种极端可能性的事件，因此程序员往往忽视竞态。但在计算机的世界里，百万分之一的事件可能在几秒内发生，而且结果
是灾难性的。
并发及其管理
1. SMP系统甚至可以在不同的处理器上同时执行我们的代码、内核代码是可以抢占的、中断随时会发生。因此我们的驱动代码可能
在任何时候丢失对处理器的独占，而拥有处理器的进程可能正在调用我们的驱动程序代码。
内核代码中还提供了可延迟的代码执行机制比如workqueue(工作队列）、tasklet(小任务）、以及timer（定时器）等，这些机制可以使
代码可在任何时刻执行。
2. 在现代的热拔插世界中，设备可能会在我们正在使用时消失。
3. 竟态通常作为对资源的共享访问的结果而产生。当两个执行线程需要访问相同的数据结构（或硬件资源时），混合的可能性永远存在。
第一个要记住的规则是，只要可能，就应该避免资源的共享。仔细编写的内核代码应该具有最少的共享，这种思想明显的就是避免使用
全局变量。
4. 硬件的资源的本质就是共享的，而软件资源经常需要对其他线程可用。我们还有清楚地是全局变量并不是共享资源的唯一途径，只要我们
将一个指针传递给内核的其他部分，一个新的共享就可能建立。
5. 管理常见的技术成为锁定或者互斥-确保一次只要一个执行线程可操作共享资源。
6. 当内核代码创建了一个可能和其他内核部分共享的对象时，该对象必须在还有其他组件引用自己时保持存在（并正确工作）。
在对象尚不能正确工作时，不能将其对内核可用，也就是说，对这类对象的应用必须得到跟踪。
信号量和互斥体
1. 对scull数据结构操作是原子的，这意味着在涉及到其他执行线程之前，整个操作就已经结束。
2. 我们必须建立临界区在任意给定代码时刻，代码只能被一个线程执行。
3. scull并不拥有任何其他关键的系统资源，这一切意味着，在scull驱动程序在等待访问数据结构而进入休眠时，不需要考虑其他
内核组件。
4. kmalloc可在也可能休眠，次休眠可能在任何时刻发生。
5. 一个信号量本质就是一个整数值，它和一对函数联合使用，这一对函数通常称为P和V。
6. 当信号量用于互斥时（即避免多个进程同时在一个临界区使用运行），信号量的值应初始化为1。
LINUX信号量的实现
1. 直接创建信号量，这通过sema_init完成。
void sema_init(struct semaphore *sem, int val);
其中val是赋予一个信号量的初始值。
2. 声明和初始化一个互斥体。
DECLARE_MUTEX(name);
DECLARE_MUTEX_LOCKED(name);
3. 如果互斥体必须在运行时初始化。
void init_MUTEX(struct semaphore *sem);
void init_MUTEX_LOCKED(struct semaphore *sem);
4.在linux世界中P函数称为down,down是指该函数减少了信号量的值，它也许会至于调用者休眠状态，然后等待信号量变得可用
之后授予调用者对保护资源的访问。
void down(struct semaphore *sem);
int down_interruptible(struct semaphore *sem);
int down_try_lock(struct semaphore *sem);
down减少信号量的值，并在必要时等待。down_interruptible完成相同的工作，但操作时可中断的。可中断的版本几乎是我们始终
要使用的版本，它允许在等待某个信号量的用户空间可被用户中断。
5. 非中断操作是建立不可杀死进程（ps输出中的D state的好方法，但会让用户感到懊恼。使用时需要始终检查返回值，并作出
相应的响应。
6. down_trylock永远不会休眠：如果信号量在调用不可获得，down_trylock返回一个非0值。
7. 当获取了信号量，该线程就被赋予访问由该信号量保护临界区的权利。互斥操作完成后，必须返回该信号量。
LINUX等价V的函数是up:
void up(struct semaphore *sem);
在scull中使用信号量
1. 正确使用锁机制的关键是，明确指明需要保护的资源，并确保每一个对这些资源的访问使用正确的锁定。
2. 信号量在使用前必须被锁定。信号量必须在使用前被初始化。
3. 注意代码中对down_interruptible返回值的检查：如果它返回0，则说明操作被中断。如果我们返回-ERESTARTSYS，则必须首先
撤销已经作出的任何用户修改，这样系统调用可正确重试，如果无法撤销这些操作，则应该返回-EINTR。
if(down_interruptible(&dev->sem)
return -ERESTARTSYS;
out:
up(&dev->sem);
return retval;
读取者和写入者信号量
1. 信号量对所有的调用者执行互斥，而不管每个线程到底做什么。但许多任务都划分两种不同的类型：一些任务只需要读取
受保护的数据结构，而其他的则必须做出修改。
2. rwsem (或者reader/writer semaphore 读取者/写入者信号量。相关的数据类型是struct rw_semaphore.
初始化
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);
3. 一个rwsem可以允许一个写入者或无限多个读取者拥有该信号量。写入者具有更高的权限。当某个给定的写入者试图
进入临界区时，在所有的写入者完成其工作之前，不会允许其他读取者访问。
4. 如果有大量的写入者竞争该信号量，则导致读取者“饿死”，即可能长期拒绝读取者的访问。
Completion
1. completion是一种轻量级的机制，它允许一个线程告诉另一个线程某个工作已经完成。
2. <linux/completion.h> 利用下面接口创建completion:
DECLARE_COMPLETION(my_completion)
或者，动态创建和初始化completion：
struct completion my_completion;
init_completion(&my_completion);
要等待completion，调用：
void wait_for_completion(struct completion *c);
该函数执行了一个非中断的等待，产生一个不可杀死的进程。
触发completion
void complete(struct completion *c); 唤醒一个等待线程
void complete_all(struct completion *c);唤醒所有的等待线程。
3. 一个completion通常是一个单次（one_shot)设备；也就是说它只会使用一次后被丢弃。
如果没有使用complete_all，则我们可以重复使用completion结构，只要那个触发的事件是明确的而不含糊。
如果使用了complete_all， 则需要使用
INIT_COMPLETION(struct completion c); 重新初始化。
自旋锁
1. 自旋锁可以在可能休眠的代码中使用，在正确使用自旋锁的情况下，自旋锁可以提供比信号量更高的性能。
2. 一个自旋锁是一个互斥设备，它只能有两个值：锁定 和 解锁。 它通常实现某个整数值正的单个位。如果锁可用
则锁定位被设置，而代码继续进入临界区，相反，如果锁被其他人获得，则代码进入忙循环并重复检查这个锁。
这个锁就是自旋锁的自旋部分。
3. 测试并设置必须以原子的方式完成，这样，即使是多个线程在给定时间自旋，也只有一个线程可用获得锁。
4. 如果非抢占式的单处理器进入某个锁上的自旋锁，则永远会自旋下去；也就是说没有任何其他线程能够获取
CPU来释放这个锁。
自旋锁的API介绍
1. 初始化自旋锁
spinlock_t 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);
自旋锁和原子上下文
1. 适用于自旋锁的核心规则是：任何拥有自旋锁的代码都是原子的，它不能休眠，它不能因为任何原因放弃处理器，除了
服务于中断以外。
2. 内核抢占的情况是自旋锁代码本身处理，任何时候，只要内核代码有自旋锁，在相关的处理器上的抢占就会被禁止。
3. 在中断例程自旋时，非中断代码将没有任何机会来释放这个锁，处理器将永远自旋下去。
4. 自旋锁使用上的最后一个重要的规则是：自旋锁必须在可能最短的时间内拥有，拥有自旋锁的时间越长，其他处理器
不得不自旋等待释放该锁的实际就越长，而它不得不自旋的时间可能性就越大。
自旋锁函数
1. 能锁定一个自旋锁的函数实际有4个：
void spin_lock(spinlock_t *lock);
void spin_lock_irqsave(spinlock_t *lock, unsigned long flags);
会获得自旋锁之前禁止中断（只在本地处理器上），而先前的中断状态保持在flags中。
void spin_lock_irq(spinlock_t *lock);
无需跟踪标志。
void spin_lock_bh(spinlock_t *lock);
在获得锁之前，禁止软件中断，但是会让硬件中断保持打开。
2. 如果一个自旋锁被运行在了（硬件或软件）中断上下文中的代码获得，则必须使用某个禁止中断形式的spin_lock。
3. 释放自旋锁
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);
4. 非阻塞的自旋操作
int spin_trylock(spinlock_t *lock);
int spin_trylock_bh(spinlock_t *lock);
读取者和写入者自旋锁
1. 这种锁允许任意数量的读取者同时进入临界区，但写入者必须互斥访问。读取者/写入者具有rwlock_t类型
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_irqrestore(rwlock_t *lock, unsigned long flags);
void read_unlock_irq(rwlock_t *lock);
void read_unlock_bh(rwlock_t *lock);
这里没有read_trylock函数可用。
2. 写入者的函数类似于读取者
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);
void write_unlock(rwlock_t *lock);
void write_unlock_irqrestore(rwlock_t *lock, unsigned long flags);
void write_unlock_irq(rwlock_t *lock);
void write_unlock_bh(rwlock_t *lock);
它们的与rwsem相似，有可能造成读取者饥饿。
锁陷阱
不明确的规则
1. 不论是信号量还是自旋锁，都不允许第二次获得这个锁，如果试图这么做，系统将挂起。
锁的顺序获取
1. 在必须获取多个锁时，应该始终以相同的顺序获得。如果我们必须获得一个局部锁，以及一个属于内核更中心的位置的锁，
则应该首先获取自己的局部锁。
细粒度锁和粗粒度锁的对比
除了锁之外的办法
面锁算法
1. 如果写入者看到的数据和读取者看到的数据始终一致，就有可能构造一种免锁的数据结构。经常用于免锁的生产者/消费者任务的
数据结构之一是循环缓冲区。
一个循环缓冲区需要一个数组以及两个索引值，一个用于要写入新值的位置，另一个用于下一个从缓冲区移走值的位置。
只要写入者在更新写入索引之前将新的值保存到缓冲区中，则读取者将始终看到一致的数据结构。将flag最后更新。
原子变量
1. 一个atomic_t的变量在所有的内核支持的架构上保存一个int值。
位操作
1。
void set_bit(nr, void *addr)
void clear_bit(nr, void *addr)
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);
设置同时返回这个位的先期值。
2。要以原子的方式获得锁并访问某个共享数据的代码，可以使用test_and_set_bit或者test_and_clear_bit。
Seqlock
1.seqlock会允许读取者对资源的自由访问，但需要读取者坚持是否和写入者发生冲突，当发生冲突时，就需要重试对资源的访问。
2. seqlock通常不能用于保护包含有指针的数据结构，因为写入者修改该数据的同时，读取者可能会追随一个无效的指针。
读取-复制-更新
1。读取-复制-更新(read-copy-update RCU)也是一种高级的互斥机制。
2。 rcu_read_lock调用非常快，它会禁止内核抢占，但不会等待任何东西。
3。 写入代码必须等待直到能够确信不存在这样的引用。
