分类: LINUX
2010-10-25 16:00:06
并发(concurrency)指的是多个执行单元同时、并行被执行。而并发的执行单元对共享资源(硬件资源和软件上的全局、静态变量)的访问则容易导致竞态(race conditions)。
SMP是一种紧耦合、共享存储的系统模型,它的特点是多个CPU使用共同的系统总线,因此可访问共同的外设和存储器。
进程与抢占它的进程访问共享资源的情况类似于SMP的多个CPU.
中断可 打断正在执行的进程,若中断处理程序访问进程正在访问的资源,则竞态也会发生。中断也可能被新的更高优先级的中断打断,因此,多个中断之间也可能引起并发
而导致竞态。上述并发的发生情况除了SMP是真正的并行以外,其他的都是“宏观并行、微观串行”的,但其引发的实质问题和SMP相似。解决竞态问题的途径是保证对共享资源的互斥访问,即一个执行单元在访问共享资源的时候,其他的执行单元被禁止访问。
访问共享资源的代码区域成为临界区(critical sections),临界区需要以某种互斥机制加以保护。中断屏蔽、原子操作、自旋锁和信号量等是Linux设备驱动中可采用的互斥途径。
中断屏蔽的使用方法为:
local_irq_disable() // 屏蔽中断 |
... |
critical section // 临界区 |
... |
local_irq_enable() // 开中断 |
在屏蔽了中断后,当前的内核执行路径应当尽快执行完临界区代码。上述两个函数都只能禁止和使能本CPU内的中断,不能解决SMP多CPU引发的竞态。
local_irq_save(flags) 除禁止中断的操作外,还保存目前CPU的中断位信息;
local_irq_restore(flags) 进行的是local_irq_save(flags)相反的操作;
若只想禁止中断的底半部,应使用local_bh_disable(), 使能被local_bh_disable()禁止的底半部应调用local_bh_enable()。
原子操作指的是在执行过程中不会被别的代码路径所中断的操作。
整型原子操作:
// 设置原子变量的值 |
void atomic_set(atomic_t *v, int i); // 设置原子变量的值为i |
atomic_t v = ATOMIC_INIT(0); // 定义原子变量v,并初始化为0 |
|
// 获取原子变量的值 |
atomic_read(atomic_t *v); // 返回原子变量的值 |
|
// 原子变量加/减 |
void atomic_add(int i, atomic_t *v); // 原子变量加i |
void atomic_sub(int i, atomic_t *v); // 原子变量减i |
|
// 原子变量自增/自减 |
void atomic_inc(atomic_t *v); // 原子变量增加1 |
void atomic_dec(atomic_t *v); // 原子变量减少1 |
|
// 操作并测试:对原子变量进行自增、自减和减操作后(没有加)测试其是否为0,为0则返回true,否则返回false |
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); |
|
// 操作并返回: 对原子变量进行加/减和自增/自减操作,并返回新的值 |
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); |
位原子操作:
// 设置位 |
void set_bit(nr, void *addr); // 设置addr地址的第nr位,即将位写1 |
|
// 清除位 |
void clear_bit(nr, void *addr); // 清除addr地址的第nr位,即将位写0 |
|
// 改变位 |
void change_bit(nr, void *addr); // 对addr地址的第nr位取反 |
|
// 测试位 |
test_bit(nr, void *addr); // 返回addr地址的第nr位 |
|
// 测试并操作:等同于执行test_bit(nr, void *addr)后再执行xxx_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); |
原子变量使用实例,使设备只能被一个进程打开:
static atomic_t xxx_available = ATOMIC_INIT(1); // 定义原子变量 |
|
static int xxx_open(struct inode *inode, struct file *filp) |
{ |
... |
if(!atomic_dec_and_test(&xxx_available)) |
{ |
atomic_inc(&xxx_availble); |
return - EBUSY; // 已经打开 |
} |
... |
return 0; // 成功 |
} |
|
static int xxx_release(struct inode *inode, struct file *filp) |
{ |
atomic_inc(&xxx_available); // 释放设备 |
return 0; |
} |
自旋锁(spin lock)——“在原地打转”。若一个进程要访问临界资源,测试锁空闲,则进程获得这个锁并继续执行;若测试结果表明锁扔被占用,进程将在一个小的循环内重复“测试并设置”操作,进行所谓的“自旋”,等待自旋锁持有者释放这个锁。
自旋锁的相关操作:
// 定义自旋锁 |
spinlock_t spin; |
|
// 初始化自旋锁 |
spin_lock_init(lock); |
|
// 获得自旋锁:若能立即获得锁,它获得锁并返回,否则,自旋,直到该锁持有者释放 |
spin_lock(lock); |
|
// 尝试获得自旋锁:若能立即获得锁,它获得并返回真,否则立即返回假,不再自旋 |
spin_trylock(lock); |
|
// 释放自旋锁: 与spin_lock(lock)和spin_trylock(lock)配对使用 |
spin_unlock(lock); |
|
自旋锁的使用:
// 定义一个自旋锁 |
spinlock_t lock; |
spin_lock_init(&lock); |
|
spin_lock(&lock); // 获取自旋锁,保护临界区 |
... // 临界区 |
spin_unlock(); // 解锁 |
自旋锁持有期间内核的抢占将被禁止。
自旋锁可以保证临界区不受别的CPU和本CPU内的抢占进程打扰,但是得到锁的代码路径在执行临界区的时候还可能受到中断和底半部(BH)的影响。
为防止这种影响,需要用到自旋锁的衍生:
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_enable()
注意:自旋锁实际上是忙等待,只有在占用锁的时间极短的情况下,使用自旋锁才是合理的
自旋锁可能导致死锁:递归使用一个自旋锁或进程获得自旋锁后阻塞。
自旋锁使用实例,使设备只能被最多一个进程打开:
int xxx_count = 0; // 定义文件打开次数计数 |
|
static int xxx_open(struct inode *inode, struct file *filp) |
{ |
... |
spinlock(&xxx_lock); |
if(xxx_count); // 已经打开 |
{ |
spin_unlock(&xxx_lock); |
return - EBUSY; |
} |
xxx_count++; // 增加使用计数 |
spin_unlock(&xxx_lock); |
... |
return 0; // 成功 |
} |
|
static int xxx_release(struct inode *inode, struct file *filp) |
{ |
... |
spinlock(&xxx_lock); |
xxx_count--; // 减少使用计数 |
spin_unlock(&xxx_lock); |
|
return 0; |
} |
读写自旋锁(rwlock)允许读的并发。在写操作方面,只能最多有一个写进程,在读操作方面,同时可以有多个读执行单元。当然,读和写也不能同时进行。
// 定义和初始化读写自旋锁 |
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_irqrestore(rwlock_t *lock, unsigned long flags); |
void read_unlock_irq(rwlock_t *lock); |
void read_unlock_bh(rwlock_t *lock); |
|
// 写锁定:在对共享资源进行写之前,应先调用写锁定函数,完成之后调用写解锁函数 |
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); |
读写自旋锁一般用法:
rwlock_t lock; // 定义rwlock |
rwlock_init(&lock); // 初始化rwlock |
|
// 读时获取锁 |
read_lock(&lock); |
... // 临界资源 |
read_unlock(&lock); |
|
// 写时获取锁 |
write_lock_irqsave(&lock, flags); |
... // 临界资源 |
write_unlock_irqrestore(&lock, flags); |
顺序锁(seqlock)是对读写锁的优化。
使用顺序锁,读执行单元不会被写执行单元阻塞,即读执行单元可以在写执行单元对被顺序锁保护的共享资源进行写操作时仍然可以继续读,而不必等待写执行单元完成写操作,写执行单元也不需要等待所有读执行单元完成读操作才去进行写操作。
写执行单元之间仍是互斥的。
若读操作期间,发生了写操作,必须重新读取数据。
顺序锁必须要求被保护的共享资源不含有指针。
写执行单元操作:
// 获得顺序锁 |
void write_seqlock(seqlock_t *sl); |
int write_tryseqlock(seqlock_t *sl); |
write_seqlock_irqsave(lock, flags) |
write_seqlock_irq(lock) |
write_seqlock_bh() |
|
// 释放顺序锁 |
void write_sequnlock(seqlock_t *sl); |
write_sequnlock_irqrestore(lock, flags) |
write_sequnlock_irq(lock) |
write_sequnlock_bh() |
|
// 写执行单元使用顺序锁的模式如下: |
write_seqlock(&seqlock_a); |
... // 写操作代码块 |
write_sequnlock(&seqlock_a); |
读执行单元操作:
// 读开始:返回顺序锁sl当前顺序号 |
unsigned read_seqbegin(const seqlock_t *sl); |
read_seqbegin_irqsave(lock, flags) |
|
// 重读:读执行单元在访问完被顺序锁sl保护的共享资源后需要调用该函数来检查,在读访问期间是否有写操作。若有写操作,重读 |
int read_seqretry(const seqlock_t *sl, unsigned iv); |
read_seqretry_irqrestore(lock, iv, flags) |
|
// 读执行单元使用顺序锁的模式如下: |
do{ |
seqnum = read_seqbegin(&seqlock_a); |
// 读操作代码块 |
... |
}while(read_seqretry(&seqlock_a, seqnum)); |
RCU(Read-Copy Update 读-拷贝-更新)
RCU可看作读写锁的高性能版本,既允许多个读执行单元同时访问被保护的数据,又允许多个读执行单元和多个写执行单元同时访问被保护的数据。
但是RCU不能替代读写锁。因为如果写操作比较多时,对读执行单元的性能提高不能弥补写执行单元导致的损失。因为使用RCU时,写执行单元之间的同步开销 会比较大,它需要延迟数据结构的释放,复制被修改的数据结构,它也必须使用某种锁机制同步并行的其他写执行单元的修改操作。
RCU操作:
// 读锁定 |
rcu_read_lock() |
rcu_read_lock_bh() |
|
// 读解锁 |
rcu_read_unlock() |
rcu_read_unlock_bh() |
|
// 使用RCU进行读的模式如下: |
rcu_read_lock() |
rcu_dereference() ... // 读临界区 |
rcu_read_unlock() |
rcu_read_lock() 和rcu_read_unlock()实质是禁止和使能内核的抢占调度:
#define rcu_read_lock() preempt_disable() |
#define rcu_read_unlock() preempt_enable() |
|
rcu_read_lock_bh()、rcu_read_unlock_bh()定义为:
#define rcu_read_lock_bh() local_bh_disable() |
#define rcu_read_unlock_bh() local_bh_enable() |
修改RCU
rcu_assign_pointer()
同步RCU synchronize_rcu() ( call_rcu()为异步的调用,优先选择synchronize_rcu。) |
由RCU写执行单元调用,保证所有CPU都处理完正在运行的读执行单元临界区。
信号量的使用
信号量(semaphore)与自旋锁相同,只有得到信号量才能执行临界区代码,但,当获取不到信号量时,进程不会原地打转而是进入休眠等待状态。
信号量的操作:
// 定义信号量 |
struct semaphore sem; |
|
// 初始化信号量: |
// 初始化信号量,并设置sem的值为val |
void sema_init(struct semaphore *sem, int val); |
|
// 初始化一个用于互斥的信号量,sem的值设置为1。等同于sema_init(struct semaphore *sem, 1) |
void init_MUTEX(struct semaphore *sem); |
|
// 等同于sema_init(struct semaphore *sem, 0) |
void init_MUTEX_LOCKED(struct semaphore *sem); |
|
// 下面两个宏是定义并初始化信号量的“快捷方式”: |
DECLEAR_MUTEX(name) |
DECLEAR_MUTEX_LOCKED(name) |
|
// 获得信号量: |
// 用于获得信号量,它会导致睡眠,不能在中断上下文使用 |
void down(struct semaphore *sem); |
|
// 类似down(),因为down()而进入休眠的进程不能被信号打断,而因为down_interruptible()而进入休眠的进程能被信号打断, |
void down_interruptible(struct semaphore *sem); |
|
// 尝试获得信号量sem,若立即获得,它就获得该信号量并返回0,否则,返回非0.它不会导致调用者睡眠,可在中断上下文使用 |
int down_trylock(struct semaphore *sem); |
|
// 使用down_interruptible()获取信号量时,对返回值一般会进行检查,若非0,通常立即返回-ERESTARTSYS,如: |
if(down_interruptible(&sem)) |
{ |
return - ERESTARTSYS; |
} |
|
// 释放信号量 |
// 释放信号量sem, 唤醒等待者 |
void up(struct semaphore *sem); |
|
// 信号量一般这样被使用: |
DECLARE_MUTEX(mount_sem); |
down(&mount_sem); // 获取信号量,保护临界区 |
... |
critical section // 临界区 |
... |
up(&mount_sem); // 释放信号量 |
|
Linux自旋锁和信号量锁采用的“获取锁-访问临界区-释放锁”的方式存在于几乎所有的多任务操作系统之中。
用信号量实现设备只能被一个进程打开的例子:
static DECLEAR_MUTEX(xxx_lock) // 定义互斥锁 |
|
static int xxx_open(struct inode *inode, struct file *filp) |
{ |
... |
if(down_trylock(&xxx_lock)) // 获得打开锁 |
return - EBUSY; // 设备忙 |
... |
return 0; // 成功 |
} |
|
static int xxx_release(struct inode *inode, struct file *filp) |
{ |
up(&xxx_lock); // 释放打开锁 |
return 0; |
} |
信号量用于同步
若信号量被初始化为0,则它可以用于同步,同步意味着一个执行单元的继续执行需等待另一执行单元完成某事,保证执行的先后顺序。
完成量用于同步
完成量(completion)提供了一种比信号量更好的同步机制,它用于一个执行单元等待另一个执行单元执行完某事。
completion相关操作:
// 定义完成量 |
struct completion my_completion; |
|
// 初始化completion |
init_completion(&my_completion); |
|
// 定义和初始化快捷方式: |
DECLEAR_COMPLETION(my_completion); |
|
// 等待一个completion被唤醒 |
void wait_for_completion(struct completion *c); |
|
// 唤醒完成量 |
void cmplete(struct completion *c); |
void cmplete_all(struct completion *c); |
自旋锁和信号量的选择
当锁不能被获取时,使用信号量的开销是进程上下文切换时间Tsw,使用自旋锁的开销是等待获取自旋锁(由临界区执行时间决定)Tcs,若Tcs较小,应使用自旋锁,若Tcs较大,应使用信号量。
信号量保护的临界区可包含可能引起阻塞的代码,而自旋锁则绝对要避免用来保护包含这样代码的临界区。因为阻塞意味着要进行进程切换,若进程被切换出去后,另一个进程企图获取本自旋锁,死锁就会发生。
信号量存在于进程上下文,因此,若被保护的共享资源需要在中断或软中断情况下使用,则在信号量和自旋锁之间只能选择自旋锁。若一定要使用信号量,则只能通过down_trylock()方式进行,不能获取就立即返回避免阻塞。
读写信号量
读写信号量与信号量的关系与读写自旋锁和自旋锁的关系类似,读写信号量可能引起进程阻塞,但它可允许N个读执行单元同事访问共享资源,而最多只能有一个写执行单元。
读写自旋锁的操作:
// 定义和初始化读写信号量 |
struct rw_semaphore my_res; // 定义 |
void init_rwsem(struct rw_semaphore *sem); // 初始化 |
|
// 读信号量获取 |
void down_read(struct rw_semaphore *sem); |
void 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); |
|
// 读写信号量的使用: |
rw_semaphore rw_sem; // 定义 |
init_rwsem(&rw_sem); // 初始化 |
|
// 读时获取信号量 |
down_read(&rw_sem); |
... // 临街资源 |
up_read(&rw_sem); |
|
// 写时获取信号量 |
down_write(&rw_sem); |
... // 临界资源 |
up_writer(&rw_sem); |