第5章 并发和竞态

1324第5章并发和竞态原子操作自旋锁信号量scull的缺陷在scull中使用信号量5原子操作考虑将整数变量加1的操作i++怎么实现？得到当前变量i的值并且拷贝到一个寄存器中将寄存器中的值加1把i的新值写回到内存中设i为全局变量，初始值为7，有两个线程欲对其施行i++操作，结果会怎样？期望的结果！Thread1geti(7)incrementi(7->8)writebacki(8)------Thread2------geti(8)incrementi(8->9)writebacki(9)可能出现的结果！若能把读、加与写回指令作为一个不可分割的整体执行，也能得到正确结果错误的结果！原子操作Thread1geti(7)incrementi(7->8)--writebacki(8)--Thread2geti(7)--incrementi(7->8)--writebacki(8)Thread1get&increment&store(7->8)--Thread2--get&increment&storei(8->9)这种“不可分割”的操作即为“原子操作”一些处理器架构提供了进行读、加与回写操的单条指令原子操作linux提供了进行这类操作的方法，称为原子操作，定义在<asm/atomic.h>中原子操作是非常快的,因为它们在可能时会编译成一条机器指令Linux的原子操作包括原子整数操作与原子位操作，整数类型atomic_t，24位。因sparc没有单条指令进行这类操作，故用32位中的低8位来做锁。为了兼容，其他架构也如此。geti(7)incrementi(7->8)writebacki(8)lockunlock临界区原子操作原子操作不是指加一的操作，而是指不被中断的操作。即要么不做，一做就要做完，其间决不停顿。原子操作分为整数操作与位操作两种类型1.原子整数操作atomic_tv;/*definev*/

atomic_tu=ATOMIC_INIT(0);/*defineuandinitializeittozero*/

atomic_set(&v,4);/*v=4(atomically)*/

atomic_add(2,&v);/*v=v+2=6(atomically)*/

atomic_inc(&v);/*v=v+1=7(atomically)*/

intatomic_dec_and_test(atomic_t*v)原子操作AtomicIntegerOperationDescriptionATOMIC_INIT(inti)Atdeclaration,initializetoi.intatomic_read(atomic_t*v)Atomicallyreadtheintegervalueofv.voidatomic_set(atomic_t*v,inti)Atomicallysetvequaltoi.voidatomic_add(inti,atomic_t*v)Atomicallyadditov.voidatomic_sub(inti,atomic_t*v)Atomicallysubtractifromv.voidatomic_inc(atomic_t*v)Atomicallyaddonetov.voidatomic_dec(atomic_t*v)Atomicallysubtractonefromv.intatomic_sub_and_test(inti,atomic_t*v)Atomicallysubtractifromvandreturntrueiftheresultiszero;otherwisefalse.原子操作接口列表原子操作intatomic_add_negative(inti,atomic_t*v)Atomicallyadditovandreturntrueiftheresultisnegative;otherwisefalse.intatomic_add_return(inti,atomic_t*v)Atomicallyadditovandreturntheresultintatomic_sub_return(inti,atomic_t*v)Atomicallysubtractifromvandreturntheresult.intatomic_inc_return(inti,atomic_t*v)Atomicallyincrementvbyoneandreturntheresult.intatomic_dec_return(inti,atomic_t*v)Atomicallydecrementvbyoneandreturntheresult.intatomic_dec_and_test(atomic_t*v)Atomicallydecrementvbyoneandreturntrueifzero;falseotherwise.intatomic_inc_and_test(atomic_t*v)Atomicallyincrementvbyoneandreturntrueiftheresultiszero;falseotherwise.原子操作2.原子位操作atomic_t类型在进行整数算术操作时是不错的.但是当你需要以原子方式操作单个位时,它无法工作。为此,内核提供了一套函数来原子地修改或测试单个位，整个操作发生在单步内,没有中断(或者其他处理器)能干扰原子位操作执行很快,因为它们使用单条机器指令来进行操作,而在任何低层平台做的时候不用禁止中断位操作函数在<asm/bitops.h>中声明位操作是对内存地址进行的操作，参数是一个指针和一个位号，指针指向内存地址，位号指明操作的位原子操作位操作接口：voidset_bit(nr,void*addr);设置addr指向的数据项的第nr位.voidclear_bit(nr,void*addr);清除addr指向的数据项的第nr位.voidchange_bit(nr,void*addr);翻转指定的位.原子操作test_bit(nr,void*addr);返回指定位的当前值.inttest_and_set_bit(nr,void*addr);设置指定的位，并返回其原先的值inttest_and_clear_bit(nr,void*addr);清除指定的位，并返回其原先的值inttest_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,addr)==0)something_went_wrong();共享数据项

1324第5章并发和竞态原子操作自旋锁信号量scull的缺陷在scull中使用信号量5自旋锁自旋锁是一个互斥设备,它只能有2个值:“上锁”和“解锁”.它通常实现为某个整数值中的单个位.希望获取特定锁的代码测试相关的位，如果锁是可用的,这个“上锁”位被置位并且代码继续进入临界区；相反,如果这个锁已经被别人获得,代码进入一个忙循环中反复检查这个锁,直到它变为可用.这个循环就是自旋锁的“自旋”部分。自旋意味着“抱着CPU空转”也可不“自旋”,即让出CPU,自已睡眠等待,钥匙放出来时让别人唤醒。此即为“信号量”,其可被称为“睡眠锁”自旋锁与信号量孰优孰劣？短时用自旋锁，长时用信号量P5？自旋锁在单处理器系统上，若停用内核抢占，自旋锁定义为空操作，因为不存在几个CPU同时进入临界区的情况；若启用了内核抢占，就跟SMP系统类似，可能存在多个内核控制路径同时进入临界区的情况，自旋锁不能定义为空操作，但spin_lock(基本上）等价于preempt_disable，而spin_unlock则等价于preempt_enable自旋锁原语要求头文件<linux/spinlock.h>.数据类型为spinlock_t，自旋锁与其他数据结构一样,自旋锁必须初始化。可以在编译时完成（静态初如化）,也可以在运行时完成（动态初始化）。静态初始化spinlock_tmy_lock=SPIN_LOCK_UNLOCKED;动态初始化voidspin_lock_init(spinlock_t*lock);在进入一个临界区前,你的代码必须获得需要的锁:voidspin_lock(spinlock_t*lock);为释放一个已获得的锁,必须调用下面函数:voidspin_unlock(spinlock_t*lock);自旋锁自旋锁的使用<linux/spinlock.h>spinlock_tmr_lock=SPIN_LOCK_UNLOCKED;spin_lock(&mr_lock);

/*criticalregion*/

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

/*criticalregion...*/spin_unlock_irqrestore(&mr_lock,flags);接口二，禁止中断、获取锁（适用于中断打开的情况）spinlock_tmr_lock=SPIN_LOCK_UNLOCKED;spin_lock_irq(&mr_lock);/*criticalsection...*/spin_unlock_irq(&mr_lock);自旋锁自旋锁函voidspin_lock(spinlock_t*lock);voidspin_lock_irqsave(spinlock_t*lock,unsignedlongflags);voidspin_lock_irq(spinlock_t*lock);voidspin_lock_bh(spinlock_t*lock)；获得锁前禁止软中，硬中保开voidspin_unlock(spinlock_t*lock);voidspin_unlock_irqrestore(spinlock_t*lock,unsignedlongflags);voidspin_unlock_irq(spinlock_t*lock);voidspin_unlock_bh(spinlock_t*lock);自旋锁读-写自旋锁对于读、写可分开的场合，内核提供了读-写锁，允许任意数量的读者同时进入临界区，但写者仍必须互斥访问临界区，类型为rwlock_t，定义在<linux/spinlokc.h>中。为何要造这种锁？初始化静态rwlock_tmy_rwlock=RW_LOCK_UNLOCKED;动态rwlock_tmy_rwlock;rwlock_init(&my_rwlock);自旋锁读-写自旋锁函数voidread_lock(rwlock_t*lock);voidread_lock_irqsave(rwlock_t*lock,unsignedlongflags);voidread_lock_irq(rwlock_t*lock);voidread_lock_bh(rwlock_t*lock);

voidread_unlock(rwlock_t*lock);voidread_unlock_irqrestore(rwlock_t*lock,unsignedlongflags);voidread_unlock_irq(rwlock_t*lock);voidread_unlock_bh(rwlock_t*lock);

自旋锁voidwrite_lock(rwlock_t*lock);voidwrite_lock_irqsave(rwlock_t*lock,unsignedlongflags);voidwrite_lock_irq(rwlock_t*lock);voidwrite_lock_bh(rwlock_t*lock);intwrite_trylock(rwlock_t*lock);

voidwrite_unlock(rwlock_t*lock);voidwrite_unlock_irqrestore(rwlock_t*lock,unsignedlongflags);voidwrite_unlock_irq(rwlock_t*lock);voidwrite_unlock_bh(rwlock_t*lock);自旋锁顺序锁seqlock读/写锁中，执行read_lock的读者与执行write_lock的写者具有相同的优先级：读者必须等待，直到写操作完成；同样，写者也必须等待，直到读操作完成。若读者多，写者得长时等待。顺序锁中赋予写者较高的优先级：即使读者正在读的时候也允许写者继续运行顺序锁定义在<linux/seqlock.h>中，数据类型为seqlock_t，包括两个字段：一个类型为spinlock_t的lock字段与一个整型的sequence字段——顺序计数器typedefstruct{ unsignedsequence; spinlock_tlock;}seqlock_t;写者进入临界区时通过write_seqlock（）获取锁，同时使顺序计数器加1；退出时通过write_seqlock()释放锁，同时再使顺序计数器加1读者在进入/退出临界区时均要读取顺计器的值，若两次读到的值不同或为奇数，说明读操作中有写者进入，因而数据无效，必须再次读取读者代码有如下面的形式:unsignedintseq;do{seq=read_seqbegin(&the_lock);

/*Dowhatyouneedtodo*/

}whileread_seqretry(&the_lock,seq);static__always_inlineintread_seqretry(constseqlock_t*sl,unsignedstart){ smp_rmb(); return(sl->sequence!=start);}自旋锁写者必须获取一个排他锁来进入由一个seqlock保护的临界区.为此,调用:voidwrite_seqlock(seqlock_t*lock);写锁由一个自旋锁实现,因此所有的通常的限制都适用调用下面函数来释放锁:voidwrite_sequnlock(seqlock_t*lock);自旋锁seqlock适宜要保护的资源小、简单、读多、写少的场合。seqlock用2种通常的方法来初始化:静态初始化seqlock_tlock1=SEQLOCK_UNLOCKED;

动态初始化：seqlock_tlock2;seqlock_init(&lock2);自旋锁其他顺序锁函数voidwrite_seqlock_irqsave(seqlock_t*lock,unsignedlongflags);voidwrite_seqlock_irq(seqlock_t*lock);voidwrite_seqlock_bh(seqlock_t*lock);voidwrite_sequnlock_irqrestore(seqlock_t*lock,unsignedlongflags);voidwrite_sequnlock_irq(seqlock_t*lock);voidwrite_sequnlock_bh(seqlock_t*lock);unsignedintread_seqbegin_irqsave(seqlock_t*lock,unsignedlongflags);intread_seqretry_irqrestore(seqlock_t*lock,unsignedintseq,unsignedlongflags);1324第5章并发和竞态原子操作自旋锁信号量scull的缺陷在scull中使用信号量5信号量Linux中的信号量是一种睡眠锁，如果一个任务试图获得一个已经被占用的信号量时，信号量会将其推进一个等待队列，然后让其睡眠中断处理程序中不能使用信号量

信号量定义在<asm/semaphore.h>，类型是structsemaphore信号量初始化voidsema_init(structsemaphore*sem,intval);val=1时为二值信号量、互斥体，类似锁val=0时同上，但初始状态为锁定val>1时，信号量数量信号量互斥体的另一种初始化（静态）DECLARE_MUTEX(name);1DECLARE_MUTEX_LOCKED(name);0互斥体的动态初始化voidinit_MUTEX(structsemaphore*sem);voidinit_MUTEX_LOCKED(structsemaphore*sem);信号量的申请voiddown(structsemaphore*sem);intdown_interruptible(structsemaphore*sem);中断返非0intdown_trylock(structsemaphore*sem);不休眠,返非0信号量信号量的释放voidup(structsemaphore*sem);信号量的使用/*定义并申明一个信号量，名为mr_sem,初始值为1*/staticDECLARE_MUTEX(mr_sem);if(down_interruptible(&mr_sem)){

/*signalreceived,semaphorenotacquired...*/

}/*criticalregion...*/

up(&mr_sem);信号量读-写信号量允许多个读者拥有该信号量，但写者有更高优先权：当一个写者进入临界区时,就不会允许读者进入直到写者完成了它们的工作。如果有大量的写者竞争该信号量，则这种实现可能导致读者“饿死”，长时间拒绝读者访问。为此,最好用在写者少且占用时间短的场合。定义在<linux/rwsem.h>，数据类型structrw_semaphore初始化voidinit_rwsem(structrw_semaphore*sem);信号量只读访问接口voiddown_read(structrw_semaphore*sem);intdown_read_trylock(structrw_semaphore*sem);voidup_read(structrw_semaphore*sem);信号量写者接口voiddown_write(structrw_semaphore*sem);intdown_write_trylock(structrw_semaphore*sem);voidup_write(structrw_semaphore*sem);voiddowngrade_write(structrw_semaphore*sem);信号量读-写信号量使用staticDECLARE_RWSEM(mr_rwsem);down_read(&mr_rwsem);/*criticalregion(readonly)...*/

up_read(&mr_rwsem);/*...*/

down_write(&mr_rwsem);/*criticalregion(readandwrite)...*/up_write(&mr_sem);

完成变量completion如果在内核中一个任务需要发出信号通知另一个任务发生了某个特定事件，利用完成变量是使两个任务得以同步的简单方法。如果一个任务要执行一些工作时，另一个任务就会在完成变量上等待。当这个任务完成工作后，会使用完成变量去唤醒在等待的任务。定义在<linux/completion.h>，类型structcompletion初始化DECLARE_COMPLETION(mr_comp);init_completion();1324第5章并发和竞态原子操作自旋锁信号量scull的缺陷在scull中使用信号量5Scull的缺陷Scull_write中设有A、B两进程同时到达下面的if语句

if(!dptr->data[s_pos]){dptr->data[s_pos]=kmalloc(quantum,GFP_KERNEL);if(!dptr->data[s_pos])gotoout;}structscull_qset{void**data;structscull_qset*next;};…如果dptr->data[s_pos]=NULL，两者都会申请分配内存，结果都赋给dptr，后者将覆盖前者，前者分配到的内存将丢失，造成内存泄漏structscull_qset*dptrScull的缺陷Scull中用什么工具来保护临界区？信号量？自旋锁？scull只适合用信号量structscull_dev{structscull_qset*data;/*Pointertofirstquantumset*/

intquantum;/*thecurrentquantumsize*/

intqset;/*thecurrentarraysize*/

unsignedlongsize;/*amountofdatastoredhere*/

unsignedintaccess_key;/*usedbysculluidandscullpriv*/

structsemaphoresem;/*mutualexclusionsemaphore*/

structcdevcdev;/*Chardevicestructure*/

};1324第5章并发和竞态原子操作自旋锁信号量scull的缺陷在scull中使用信号量5在scull中使用信号信号量在使用前必须初始化。scull在加载时进行这个初始化:for(i=0;i<scull_nr_devs;i++){scull_devices[i].quantum=scull_quantum;scull_devices[i].qset=scull_qset;

init_MUTEX(&scull_devices[i].sem);

scull_setup_cdev(&scull_devices[i],i);}在scull中使用信号ssize_tscull_write(structfile*filp,constchar__user*buf,size_tcount,loff_t*f_pos){ …

if(down_interruptible(&dev->sem))return-ERESTARTSYS; … if(!dptr->data[s_pos]){dptr->data[s_pos]=kmalloc(quantum,GFP_KERNEL);if(!dptr->data[s_pos])gotoout; …out:

up(&dev->sem);returnretval;}快速参考#include<asm/semaphore.h>DECLARE_MUTEX(name);DECLARE_MUTEX_LOCKED(name);voidinit_MUTEX(structsemaphore*sem);voidinit_MUTEX_LOCKED(structsemaphore*sem);voiddown(structsemaphore*sem);intdown_interruptible(structsemaphore*sem);intdown_trylock(structsemaphore*sem);voidup(structsemaphore*sem);structrw_semaphore;init_rwsem(structrw_semaphore*sem);

快速参考voiddown_read(structrw_semaphore*sem);intdown_read_trylock(structrw_semaphore*sem);voidup_read(structrw_semaphore*sem);voiddown_write(structrw_semaphore*sem);intdown_write_trylock(structrw_semaphore*sem);voidup_write(structrw_semaphore*sem);#include<linux/completion.h>DECLARE_COMPLETION(name);init_completion(structcompletion*c);INIT_COMPLETION(structcompletionc);

快速参考voidwait_for_completion(structcompletion*c);voidcomplete(structcompletion*c);voidcomplete_all(structcompletion*c);voidcomplete_and_exit(structcompletion*c,longretval);#include<linux/spinlock.h>spinlock_tlock=SPIN_LOCK_UNLOCKED;spin_lock_init(spinlock_t*lock);voidspin_lock(spinlock_t*lock);voidspin_lock_irqsave(spinlock_t*lock,unsignedlongflags);voidspin_lock_irq(spinlock_t*lock);voidspin_lock_bh(spinlock_t*lock);快速参考intspin_trylock(spinlock_t*lock);intspin_trylock_bh(spinlock_t*lock);voidspin_unlock(spinlock_t*lock);voidspin_unlock_irqrestore(spinlock_t*lock,unsignedlongflags);voidspin_unlock_irq(spinlock_t*lock);voidspin_unlock_bh(spinlock_t*lock);rwlock_tlock=RW_LOCK_UNLOCKEDrwlock_init(rwlock_t*lock);快速参考voidread_lock(rwlock_t*lock);voidread_lock_irqsave(rwlock_t*lock,unsignedlongflags);voidread_lock_irq(rwlock_t*lock);voidread_lock_bh(rwlock_t*lock);voidread_unlock(rwlock_t*lock);voidread_unlock_irqrestore(rwlock_t*lock,unsignedlongflags);voidread_unlock_irq(rwlock_t*lock);voidread_unlock_bh(rwlock_t*lock);快速参考voidwrite_lock(rwlock_t*lock);voidwrite_lock_irqsave(rwlock_t*lock,unsignedlongflags);voidwrite_lock_irq(rwlock_t*lock);voidwrite_lock_bh(rwlock_t*lock);voidwrite_unlock(rwlock_t*lock);voidwrite_unlock_irqrestore(rwlock_t*lock,unsignedlongflags);voidwrite_unlock_irq(rwlock_t*lock);voidwrite_unlock_bh(rwlock_t*lock);快速参考#include<asm/atomic.h>atomic_tv=ATOMIC_INIT(value);voidatomic_set(atomic_t*v,inti);intatomic_read(atomic_t*v);voidatomic_add(inti,atomic_t*v);voidatomic_sub(inti,atomic_t*v);voidatomic_inc(atomic_t*v);voidatomic_dec(atomic_t*v);intatomic_inc_and_test(atomic_t*v);intatomic_dec_and_test(atomic_t*v);intatomic_sub_and_test(inti,atomic_t*v);intatomic_add_negative(inti,atomic_t*v);intatomic_add_return(inti,atomic_t*v);intatomic_sub_return(inti,atomic_t*v);intatomic_inc_return(atomic_