第5章 并发和竞态

1、,1,3,2,4,第5 章 并发和竞态,原子操作,自旋锁,信号量,scull的缺陷,在scull中使用信号量,5,原子操作,考虑将整数变量加1的操作i+怎么实现？ 得到当前变量i的值并且拷贝到一个寄存器中 将寄存器中的值加1 把i的新值写回到内存中 设i为全局变量，初始值为7，有两个线程欲对其施行i+操作，结果会怎样？,期望的结果！,可能出现的结果！,若能把读、加与写回指令作为一个不可分割的整体执行，也能得到正确结果,错误的结果！,原子操作,这种“不可分割”的操作即为“原子操作” 一些处理器架构提供了进行读、加与回写操的单条指令,原子操作,linux提供了进行这类操作的方法，称为原子操作，定义

2、在中 原子操作是非常快的, 因为它们在可能时会编译成一条机器指令 Linux的原子操作包括原子整数操作与原子位操作，整数类型atomic_t，24位。,因sparc没有单条指令进行这类操作，故用32位中的低8位来做锁。为了兼容，其他架构也如此。,get i (7) increment i (7-8) write back i (8),lock,unlock,临界区,原子操作,原子操作不是指加一的操作，而是指不被中断的操作。即要么不做，一做就要做完，其间决不停顿。原子操作分为整数操作与位操作两种类型 1. 原子整数操作 atomic_t v; /* define v */ atomic_t u

3、= ATOMIC_INIT(0); /* define u and initialize it to zero */ atomic_set( /* v = v + 1 = 7 (atomically) */ int atomic_dec_and_test(atomic_t *v),原子操作,原子操作接口列表,原子操作,原子操作,2. 原子位操作 atomic_t 类型在进行整数算术操作时是不错的. 但是当你需要以原子方式操作单个位时, 它无法工作。 为此, 内核提供了一套函数来原子地修改或测试单个位，整个操作发生在单步内, 没有中断(或者其他处理器)能干扰 原子位操作执行很快, 因为它们使用单

4、条机器指令来进行操作, 而在任何低层平台做的时候不用禁止中断 位操作函数在 中声明 位操作是对内存地址进行的操作，参数是一个指针和一个位号，指针指向内存地址，位号指明操作的位,原子操作,位操作接口： void set_bit(nr, void *addr); 设置 addr 指向的数据项的第 nr 位. void clear_bit(nr, void *addr); 清除 addr 指向的数据项的第nr位. void change_bit(nr, void *addr); 翻转指定的位.,原子操作,test_bit(nr, void *addr); 返回指定位的当前值. int test_an

5、d_set_bit(nr, void *addr); 设置指定的位，并返回其原先的值 int test_and_clear_bit(nr, void *addr); 清除指定的位，并返回其原先的值 int test_and_change_bit(nr, void *addr); 翻转指定的位，并返回其原先的值,原子操作,例 可以使用位操作来管理一个锁变量以控制对某个共享数据项的访问。假定这个位是 0时锁空闲,非零时锁忙。,while (test_and_set_bit(nr, addr) != 0) wait_for_a_while(); if (test_and_clear_bit(nr,

6、addr) = 0) something_went_wrong();,共享数据项,1,3,2,4,第5 章 并发和竞态,原子操作,自旋锁,信号量,scull的缺陷,在scull中使用信号量,5,自旋锁,自旋锁是一个互斥设备, 它只能有 2 个值:“上锁”和“解锁”. 它通常实现为某个整数值中的单个位. 希望获取特定锁的代码测试相关的位， 如果锁是可用的, 这个“上锁”位被置位并且代码继续进入临界区；相反, 如果这个锁已经被别人获得, 代码进入一个忙循环中反复检查这个锁, 直到它变为可用. 这个循环就是自旋锁的“自旋”部分。自旋意味着“抱着CPU空转”,也可不“自旋”,即让出CPU,自已睡眠等待

7、,钥匙放出来时让别人唤醒。此即为“信号量”,其可被称为“睡眠锁”,自旋锁与信号量孰优孰劣？,短时用自旋锁，长时用信号量,自旋锁,在单处理器系统上，若停用内核抢占，自旋锁定义为空操作，因为不存在几个CPU同时进入临界区的情况；若启用了内核抢占，就跟SMP系统类似，可能存在多个内核控制路径同时进入临界区的情况，自旋锁不能定义为空操作，但spin_lock(基本上）等价于preempt_disable，而spin_unlock则等价于preempt_enable 自旋锁原语要求头文件 . 数据类型为 spinlock_t，,自旋锁,与其他数据结构一样, 自旋锁必须初始化。 可以在编译时完成（静态初如

8、化）, 也可以在运行时完成（动态初始化）。 静态初始化 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);,自旋锁,自旋锁的使用 spinlock_t mr_lock = SPIN_LOCK_UNLOCKED; spin_lock( 自旋锁使用规

9、则 拥有自旋锁的代码必须是原子的 拥有自旋锁时不能够睡眠 在中断处理程序中可使用自旋锁，但拥有前必须禁止本地中断 拥有自旋锁的时间必须尽可能短,自旋锁,内核提供了获取锁前禁止中断的接口 接口一，禁止中断、保存中断当前状态、获取锁 spinlock_t mr_lock = SPIN_LOCK_UNLOCKED; unsigned long flags; spin_lock_irqsave(,自旋锁,自旋锁函 void spin_lock(spinlock_t *lock); void spin_lock_irqsave(spinlock_t *lock, unsigned long flags)

10、; void spin_lock_irq(spinlock_t *lock); void spin_lock_bh(spinlock_t *lock) ；获得锁前禁止软中，硬中保开 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);,自旋锁,读-写自旋锁 对于读、写可分开的场合，内核提

11、供了读-写锁，允许任意数量的读者同时进入临界区，但写者仍必须互斥访问临界区，类型为 rwlock_t，定义在 中。为何要造这种锁？ 初始化 静态 rwlock_t my_rwlock = RW_LOCK_UNLOCKED; 动态 rwlock_t my_rwlock; rwlock_init(,自旋锁,读-写自旋锁函数 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_

12、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); v

13、oid 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_irqrestore(rwlock_t *lock, unsigned long flags); void write_unlock_irq(rwlock_t *lock); void write_unlock_bh(rwlock_t *lock);,自旋锁,顺序锁seqlock

14、 读/写锁中，执行read_lock的读者与执行write_lock的写者具有相同的优先级：读者必须等待，直到写操作完成；同样，写者也必须等待，直到读操作完成。若读者多，写者得长时等待。 顺序锁中赋予写者较高的优先级：即使读者正在读的时候也允许写者继续运行 顺序锁定义在 中，数据类型为seqlock_t，包括两个字段：一个类型为spinlock_t的lock字段与一个整型的sequence字段顺序计数器,typedef struct unsigned sequence;spinlock_t lock; seqlock_t;,写者进入临界区时通过write_seqlock（）获取锁，同时使顺序计

15、数器加1；退出时通过write_seqlock()释放锁，同时再使顺序计数器加1 读者在进入/退出临界区时均要读取顺计器的值，若两次读到的值不同或为奇数，说明读操作中有写者进入，因而数据无效，必须再次读取 读者代码有如下面的形式: unsigned int seq; do seq = read_seqbegin(,static _always_inline int read_seqretry(const seqlock_t *sl, unsigned start) smp_rmb(); return (sl-sequence != start); ,自旋锁,写者必须获取一个排他锁来进入由一个

16、seqlock 保护的临界区. 为此, 调用: void write_seqlock(seqlock_t *lock); 写锁由一个自旋锁实现, 因此所有的通常的限制都适用调用下面函数来释放锁: void write_sequnlock(seqlock_t *lock);,自旋锁,seqlock 适宜要保护的资源小、简单、读多、写少的场合。 seqlock 用 2 种通常的方法来初始化: 静态初始化 seqlock_t lock1 = SEQLOCK_UNLOCKED; 动态初始化： seqlock_t lock2; seqlock_init(,自旋锁,其他顺序锁函数 void write_s

17、eqlock_irqsave(seqlock_t *lock, unsigned long flags); void write_seqlock_irq(seqlock_t *lock); void write_seqlock_bh(seqlock_t *lock); void write_sequnlock_irqrestore(seqlock_t *lock, unsigned long flags); void write_sequnlock_irq(seqlock_t *lock); void write_sequnlock_bh(seqlock_t *lock); unsigned

18、int read_seqbegin_irqsave(seqlock_t *lock, unsigned long flags); int read_seqretry_irqrestore(seqlock_t *lock, unsigned int seq, unsigned long flags);,1,3,2,4,第5 章 并发和竞态,原子操作,自旋锁,信号量,scull的缺陷,在scull中使用信号量,5,信号量,Linux 中的信号量是一种睡眠锁，如果一个任务试图获得一个已经被占用的信号量时，信号量会将其推进一个等待队列，然后让其睡眠 中断处理程序中不能使用信号量 信号量定义在，类型是

19、struct semaphore 信号量初始化 void sema_init(struct semaphore *sem, int val); val=1时为二值信号量、互斥体，类似锁 val=0时同上，但初始状态为锁定 val1时，信号量数量,信号量,互斥体的另一种初始化（静态） DECLARE_MUTEX(name); 1 DECLARE_MUTEX_LOCKED(name);0 互斥体的动态初始化 void init_MUTEX(struct semaphore *sem); void init_MUTEX_LOCKED(struct semaphore *sem); 信号量的申请 vo

20、id down(struct semaphore *sem); int down_interruptible(struct semaphore *sem);中断返非0 int down_trylock(struct semaphore *sem); 不休眠,返非0,信号量,信号量的释放 void up(struct semaphore *sem); 信号量的使用 /* 定义并申明一个信号量，名为mr_sem,初始值为1 */ static DECLARE_MUTEX(mr_sem); if (down_interruptible(,信号量,读-写信号量 允许多个读者拥有该信号量，但写者有更高优

21、先权：当一个写者进入临界区时, 就不会允许读者进入直到写者完成了它们的工作。如果有大量的写者竞争该信号量，则这种实现可能导致读者“饿死” ，长时间拒绝读者访问。 为此, 最好用在写者少且占用时间短的场合。 定义在，数据类型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

22、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); void downgrade_write(struct rw_semaphore *sem);,信号量,读-写信号量使用 static DECLARE_RWSEM(mr_rwsem); down_read(,完成变量completion,如果在内核中一个任务需要发出信号通知

23、另一个任务发生了某个特定事件，利用完成变量是使两个任务得以同步的简单方法。如果一个任务要执行一些工作时，另一个任务就会在完成变量上等待。当这个任务完成工作后，会使用完成变量去唤醒在等待的任务。 定义在，类型struct completion 初始化 DECLARE_COMPLETION(mr_comp); init_completion() ;,1,3,2,4,第5 章 并发和竞态,原子操作,自旋锁,信号量,scull的缺陷,在scull中使用信号量,5,Scull的缺陷,Scull_write中设有A、B两进程同时到达下面的if语句 if (!dptr-datas_pos) dptr-dat

24、as_pos = kmalloc(quantum, GFP_KERNEL); if (!dptr-datas_pos) goto out; ,struct scull_qset void *data; struct scull_qset *next; ;,如果dptr-datas_pos=NULL，两者都会申请分配内存，结果都赋给dptr，后者将覆盖前者，前者分配到的内存将丢失，造成内存泄漏,struct scull_qset *dptr,Scull的缺陷,Scull中用什么工具来保护临界区？ 信号量？ 自旋锁？ scull只适合用信号量 struct scull_dev struct scu

25、ll_qset *data; /* Pointer to first quantum set */ int quantum; /* the current quantum size */ int qset; /* the current array size */ unsigned long size; /* amount of data stored here */ unsigned int access_key; /* used by sculluid and scullpriv */ struct semaphore sem; /* mutual exclusion semaphore

26、*/ struct cdev cdev; /* Char device structure */ ;,1,3,2,4,第5 章 并发和竞态,原子操作,自旋锁,信号量,scull的缺陷,在scull中使用信号量,5,在scull中使用信号,信号量在使用前必须初始化。 scull 在加载时进行这个初始化: for (i = 0; i scull_nr_devs; i+) scull_devicesi.quantum = scull_quantum; scull_devicesi.qset = scull_qset; init_MUTEX( ,在scull中使用信号,ssize_t scull_wr

27、ite(struct file *filp, const char _user *buf, size_t count, loff_t *f_pos) if (down_interruptible( ,快速参考,#include 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_interru

28、ptible(struct semaphore *sem); int down_trylock(struct semaphore *sem); void up(struct semaphore *sem); struct rw_semaphore; 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); v

29、oid down_write(struct rw_semaphore *sem); int down_write_trylock(struct rw_semaphore *sem); void up_write(struct rw_semaphore *sem); #include DECLARE_COMPLETION(name); init_completion(struct completion *c); INIT_COMPLETION(struct completion c);,快速参考,void wait_for_completion(struct completion *c); vo

30、id complete(struct completion *c); void complete_all(struct completion *c); void complete_and_exit(struct completion *c, long retval); #include spinlock_t lock = SPIN_LOCK_UNLOCKED; spin_lock_init(spinlock_t *lock); void spin_lock(spinlock_t *lock); void spin_lock_irqsave(spinlock_t *lock, unsigned

31、long flags); void spin_lock_irq(spinlock_t *lock); void spin_lock_bh(spinlock_t *lock);,快速参考,int spin_trylock(spinlock_t *lock); int spin_trylock_bh(spinlock_t *lock); void spin_unlock(spinlock_t *lock); void spin_unlock_irqrestore(spinlock_t *lock, unsigned long flags); void spin_unlock_irq(spinloc

32、k_t *lock); void spin_unlock_bh(spinlock_t *lock); rwlock_t lock = RW_LOCK_UNLOCKED rwlock_init(rwlock_t *lock);,快速参考,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(r

33、wlock_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 w

34、rite_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);,快速参考,#include atomic_t v = ATOMIC_INIT(value); void atomic_set(atomic_t *v, int i); int ato

35、mic_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); int atomic_add_negativ

36、e(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);,快速参考,#include 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);,快速