并发与竞态

并发（concurrency）指的是多个执行单元同时、并行被执行。

竞态因并发的执行单元对共享资源（1.硬件资源如寄存器，2.软件的全局变量、静态变量等）的访问所致。

 

竞态发生的情况：

1、对称多处理"（Symmetrical Multi-Processing）系统的多个CPU之间

对称多处理"（Symmetrical Multi-Processing）又叫SMP，是指在一个计算机上汇集了一组处理器(多CPU),各CPU之间共享内存子系统以及总线结构。它是相对非对称多处理技术而言的、应用十分广泛的并行技术。

2、单CPU内进程与抢占它的进程间

虽然CPU只有一个，但是如Linux2.6内核支持抢占调度，一个进程在内核执行的时候可能被另一更高的优先级的进程打断，如果这个抢占进程也访问该进程正在访问的资源的话，发生竞态。

3、中断（包括硬中断、软中断、Tasklet、底半部）与进程之间

中断可以打断你正在执行的进程，如果中断处理程序访问进程正在访问的资源，则竞态也会发生。

 

解决竞态问题的途径

是保证对共享资源的互斥访问。所谓互斥访问是指一个执行单元在访问共享资源的时候，其他的执行单元被禁止访问。

访问共享资源的代码区域称为临界区，临界区需要以某种互斥机制加以保护。

互斥机制：中断屏蔽、原子操作、自旋锁和信号量等。

中断屏蔽

中断屏蔽将使得中断与进程之间的并发不再发生，而且，由于Linux内核的进程调度等操作都依赖中断来实现，内核抢占进程之间的并发也就得以避免了。但是，需要注意是的是长时间的中断是危险的，有可能导致数据丢失或着系统崩溃。

local_irq_disable()和local_irq_enable()都只能禁止和使能本CPU内的中断，不能解决SMP多CPU引发的竞态。

local_irq_save(flags)除了进行禁止中断操作以外，还保存目前CPU的中断位信息，local_irq_restore(flags)进行相反的操作。

如果只想禁止中断的底半部，应使用local_bh_disable(),使能底半部使用local_bh_enable()。

原子操作

原子操作指的是能够顺序执行而不被中断的操作。也就是说它是最小的执行单元，这里的原子实际上是使用了物理学中的物质微粒的概念。

Linux内核提供了一系列函数来实现内核中的原子操作，这些函数又分为两类，分别针对位和整型变量进行原子操作。

 

整型原子操作

1. 设置值 void atomic_set(atomic_t *v,int i); Atomic_t v = ATOMIC_INT(0);

2. 获取值 atomic_read(atomic_t *v);

3. 加/减 void atomic_add(int i,atomic_t *v); void atomic_sub(int i,atomic_t *v);

4. 自增/自减 void atomic_inc(atomic_t *v); void atomic_dec(atomic_t *v);

5. 操作测试 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，为0返回true，否则返回false

6. 操作返回int atomic_inc_and_return(atomic_t *v); int atomic_dec_and_return(atomic_t *v); int atomic_sub_and_return(int i, atomic_t *v); int atomic_add_and_return(int i, atomic_t *v);

操作后返回新值。

 

位原子操作

1. 设置位 void set_bit(nr,void *addr); 设置addr地址的第nr位，即将位写1。

2. 清除位 void clear_bit(nr,void *addr); 将位写为0。

3. 改变位 void change_bit(nr,void *addr); 将位进行反置。

4. 测试位test_bit(nr,void *addr); 返回第nr位。

5. 测试操作int test_and_set_bit(nr,void *addr); int test_and_clear_bit(nr,void *addr); int test_and_change_bit(nr,void *addr);

先测试返回，后操作。

 

例子：使用原子变量使设备只能被一个进程打开

static atomic_t xxx_available =ATOMIC_INIT(1);

xxx_open

{

if(!atomic_dec_and_test(&xxx_available))

{

atomic_inc(&xxx_available);

return - EBUSY;

}

}

xxx_release

{

atomic_inc(&xxx_available);

}

 

自旋锁

自旋锁是是为了解决对某项资源的互斥使用。在任何时刻，最多只能有一个保持者，也就说，在任何时刻最多只能有一个执行单元获得锁。如果资源已经被占用，自旋锁不会引起调用者睡眠，如果自旋锁已经被别的执行单元保持，调用者就一直循环在那里看是否该自旋锁的保持者已经释放了锁。

1. 定义 spinlock_t lock;

2. 初始化 spin_lock_init(&lock);

3 获得 spin_lock(&lock); 自旋等待 spin_trylock(&lock); 非阻塞，立即返回。

4. 释放 spin_unlock(&lock);

5. 防止中断和底半部的影响

spin_lock_irq(lock)
该宏获得自旋锁lock的同时关中断。相当于：spin_lock()+local_irq_disable()
spin_unlock_irq(lock)
该宏释放自旋锁lock的同时，开中断。它与spin_lock_irq配对应用。相当于: spin_unlock()+local_irq+enable()

spin_lock_irqsave(lock, flags)
该宏获得自旋锁的同时把标志寄存器的值保存到变量flags中并失效本地中断。相当于：spin_lock()+local_irq_save()
spin_unlock_irqrestore(lock, flags)
该宏释放自旋锁lock的同时，也恢复标志寄存器的值为变量flags保存的值。它与spin_lock_irqsave配对使用。
相当于：spin_unlock()+local_irq_restore()

spin_lock_bh(lock)
该宏在得到自旋锁的同时失效本地软中断。相当于：spin_lock()+local_bh_disable()
spin_unlock_bh(lock)
该宏释放自旋锁lock的同时，也使能本地的软中断。它与spin_lock_bh配对使用。相当于：spin_unlock()+local_bh_enable()

注意：自旋锁实际是忙等锁；自旋锁可能导致系统死锁；自旋锁锁定期间不能调用可能引起进程调度的函数。

 

读写自旋锁

“读写自旋锁”用来解决读者/写者问题。如果有多个线程（进程、中断处理程序、底半部例程）以只读的方式访问一个临界区数据，读/写自旋锁允许多个线程同时读取数据。如果一个线程需要对临界区数据进行写操作，它必须获取写锁，只有在没有读者或写者进行操作时，写者才独占临界区数据进行写操作。读操作时需要获取读锁，写操作时需要获取写锁。读写自旋锁可允许读的并发。

操作：

1. 定义初始化 rwlock_t my_rwlock = RW_LOCK_UNLOCKED;

rwlock_t my_rwlock;

rwlock_init(&my_rwlock);

2. 读锁定 void read_lock(rw_lock_t *lock);

3. 读解锁 void read_unlock(rw_lock_t *lock);

4. 写锁定 void write_lock(rw_lock_t *lock);

void write_trylock(rw_lock_t *lock);

5. 写解锁 void write_unlock(rw_lock_t *lock);

 

顺序锁

顺序锁是对读写锁的一种优化，读执行单元绝不会被写执行单元阻塞。读执行单元可以在写执行单元对被顺序锁保护的共享资源进行写操作时还可以继续读，而不必等待写执行单元完成写操作，写执行单元也不需要等待所有读执行单元完成读操作才进行写操作。

注：顺序锁要求被保护的共享资源不含有指针，因为写执行单元可能使指针失效，但读执行单元如果正要访问该资源，导致Oops。

读执行单元访问共享资源时，如果有写操作执行完成，读执行单元就需要重新进行读操作。

顺序锁中读或写单元都不会被对方阻塞，但是写写仍然互斥。

操作：1. 获得锁void write_seqlock(seqlock_t *sl);

void write_tryseqlock(seqlock_t *sl);

2. 释放锁void write_sequnlock(seqlock_t *sl);

读完后需要进行检查在读期间是否有写操作，如果有则需要重新进行读操作。

 

读-拷贝-更新

RCU(Read-Copy Update)，顾名思义就是读-拷贝-修改，它是基于其原理命名的。对于被RCU保护的共享数据结构，读执行单元不需要获得任何锁就可以访问它，不需要锁也使得使用更容易，因为死锁问题就不需要考虑。但使用RCU写执行单元在访问它前需首先复制一个副本，然后对副本进行修改，最后使用一个回调机制（callback）在适当的时机把指向原来数据的指针重新指向新的被修改的数据，这个时机就是所有引用该数据的CPU都退出对共享数据的操作的时候。

 

操作：1. 读锁定 rcu_read_lock() rcu_read_lock_bh()

2. 读解锁 rcu_read_unlock() rcu_read_unlock_bh()

3. 同步RCU synchronize_rcu()

4 挂接回调 void fastcall call_rcu(struct rcu_head *head, void (*func)(struct_rcu_head *rcu) );

RCU还增加了链表操作函数的RCU版本。

 

信号量

如果有一个任务试图获得一个已经被占用的信号量时，信号量会将其推到一个等待队列中，这时处理器会重获自由从而去执行其它代码，当持有信号量的进程将信号量释放后，处于等待队列中的那个任务将会被唤醒，并将获得该信号量。

对某个互斥资源的访问会收到信号量的保护，在访问之前需要获得信号量，在操作完共享资源后，需释放信号量，以便另外的进程来获得资源。获得和释放应该成对出现。
获得信号量集，需要注意的是，获得的是一个集合，而不是一个单一的信号量。

信号量分为互斥信号量，以及计数信号量，区别在于 count的值，若为1，则为互斥信号量，若大于1 则为计数信号量。

与自旋锁不同的是，当获取不到信号量时，进程不会原地打转而是进入休眠等待状态。

操作：

1. 定义 struct semaphore sem;

2. 初始化 void sema_init(struct semaphore *sem, int val);

void init_MUTEX(struct semaphore *sem); //信号量sem的值设置为1

void init_MUTEX_LOCKED(struct semaphore *sem); //信号量sem的值设置为0

DECLARE_MUTEX(name) //name的信号量初始化为1

DECLARE_MUTEX_LOCKED(name) //name的信号量初始化为0

3.获取 void down(struct semaphore *sem); //休眠

int down_interruptible(struct semaphore *sem);

Int down_trylock(struct semaphore *sem); //不会休眠 可在中断上下文使用

4. 释放 void up(struct semaphore *sem);

 

信号量用于同步

如果信号量被初始化为0，则它可以用于同步，同步意味着一个执行单元的继续执行需等待另一执行单元完成某事，保证执行的先后顺序。

完成量用于同步

Linux提供了一种比信号量更好的同步机制，即完成量(completion)。

操作：1. 定义 struct completion my_completion;

2. 初始化 init_completion(&my_completion);

DECLARE_COMPLETION(my_completion);

3. 等待 void wait_for_completion(struct completion *c);

4. 唤醒void complete(struct completion *c);

void complete_all(struct completion *c);

 

自旋锁vs信号量

 

严格意义上说，信号量和自旋锁属于不同层次的互斥手段，前者的实现依赖于后者。

信号量是进程级的，用于多个进程之间对资源的互斥，所以适用于进程占用资源时间比较长的时候，而自旋锁不能在临界区长时间停留。

信号量所保护的临界区可包含可能引起阻塞的代码，而自旋锁则绝对要避免用来保护包含这样代码的临界区。因为阻塞意味着要进行进程间的切换，如果进程被切换出去后，另一个进程企图获取本自旋锁，死锁就会发生。

如果被保护的共享资源需要在中断或软中断情况下使用，则只能选择自旋锁。如果一定要使用信号量，则只能通过down_trylock()进行，以避免阻塞。

 

读写信号量

它可允许N个读执行单元同时访问共享资源，而最多只能有一个写执行单元。

操作：1. 定义初始化 struct rw_semaphore my_rws;

void init_rwsem(struct rw_semaphore *sem);

2. 读信号量获取 void down_read(struct rw_semaphore *sem);

int down_read_trylock(struct rw_semaphore *sem);

3. 读信号量释放void up_read(struct rw_semaphore *sem);

4. 写信号量获取 void down_write(struct rw_semaphore *sem);

int down_write_trylock(struct rw_semaphore *sem);

3. 写信号量释放void up_write(struct rw_semaphore *sem);

 

互斥体

操作：1. 定义初始化 struct mutex my_mutex;

Mutex_init (&my_mutex);

2. 获取 void fastcall mutex_lock(struct mutex *lock);

int fastcall mutex_lock_interruptible(struct mutex *lock);

int fastcall mutex_trylock (struct mutex *lock);

3.释放void fastcall mutex_unlock(struct mutex *lock);

 

死锁

死锁： 是指两个或两个以上的进程在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。 由于资源占用是互斥的，当某个进程提出申请资源后，使得有关进程在无外力协助下，永远分配不到必需的资源而无法继续运行。 

1.竞争资源引起进程死锁

1）可剥夺资源和不可剥夺资源

2）竞争不可剥夺资源

3）竞争临时资源

2.进程推进顺序不当引起死锁

产生死锁的四个必要条件

（1）互斥条件：一个资源每次只能被一个进程（线程）使用。
（2）请求与保持条件：一个进程（线程）因请求新的资源而阻塞时，对已获得的资源保持不放。
（3）不剥夺条件 : 此进程（线程）已获得的资源，在末使用完之前，不能被剥夺，只能自己释放。
（4）循环等待条件 : 多个进程（线程）之间形成一种头尾相接的循环等待资源关系。

处理死锁的基本方法

　　1) 预防死锁。

　　事先设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或者几个，来预防发生死锁。

　　2) 避免死锁。

　　在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁。

　　3)检测死锁。

　　通过系统所设置的检测机构，及时地检测出死锁的发生，并精确地确定与死锁有关的进程和资源，然后采取适当措施，从系统中将已发生的死锁清除掉。

　　4)解除死锁。

　　撤销或挂起一些进程，以便回收一些资源，再将这些资源分配给已处于阻塞状态的进程，使之转为就绪状态，以继续运行。