linux内核同步问题

　　linux内核同步问题
　　Linux内核设计与实现十、内核同步方法
　　手把手教Linux驱动5自旋锁、信号量、互斥体概述
　　基础概念：
　　并发：多个执行单元同时进行或多个执行单元微观串行执行，宏观并行执行
　　竞态：并发的执行单元对共享资源（硬件资源和软件上的全局变量）的访问而导致的竟态状态。
　　临界资源：多个进程访问的资源
　　临界区：多个进程访问的代码段
　　并发场合：
　　1、单CPU之间进程间的并发：时间片轮转，调度进程。A进程访问打印机，时间片用完，OS调度B进程访问打印机。
　　2、单cpu上进程和中断之间并发：CPU必须停止当前进程的执行中断；
　　3、多cpu之间
　　4、单CPU上中断之间的并发
　　使用偏向：
　　需求
　　建议加锁方式
　　低开销、短期加锁
　　优先自旋锁
　　长期锁定
　　优先互斥锁
　　中断上下文加锁
　　自旋锁
　　需要睡眠的持有锁（单线程）
　　互斥锁
　　需要睡眠的持有锁（多线程）
　　信号量1、信号量（semaphore）
　　信号量用于进程之间的同步，进程在信号量保护的临界区代码里面是可以睡眠的（需要进行进程调度），这是与自旋锁最大的区别。
　　信号量又称为信号灯，它是用来协调不同进程间的数据对象的，而最主要的应用是共享内存方式的进程间通信。本质上，信号量是一个计数器，它用来记录对某个资源（如共享内存）的存取状况。它负责协调各个进程，以保证他们能够正确、合理的使用公共资源。它和spinlock最大的不同之处就是：无法获取信号量的进程可以睡眠，因此会导致系统调度。1。1、特点
　　1、用于进程与进程之间的同步
　　2、允许多个进程进入临界区代码执行，临界区代码允许睡眠；
　　3、信号量本质是基于调度器的，在UP和SMP下没有区别；进程获取不到信号量将陷入休眠，并让出CPU；
　　4、不支持进程和中断之间的同步
　　5、进程调度也是会消耗系统资源的，如果一个int型共享变量就需要使用信号量，将极大的浪费系统资源
　　6、信号量可以用于多个线程，用于资源的计数（有多种状态）1。2、常用函数
　　信号量加锁以及解锁过程：
　　semainit（spdeadsem，0）；初始化
　　down（sema）；
　　临界区代码
　　up（sema）；
　　信号量定义：structsemaphore｛rawspinlocktlock；unsignedintcount；structlistheadwaitlist；｝；
　　信号量初始化：staticinlinevoidsemainit（structsemaphoresem，intval）｛staticstructlockclasskeykey；sem（structsemaphore）SEMAPHOREINITIALIZER（sem，val）；lockdepinitmap（semlock。depmap，semaphorelock，key，0）；｝
　　dowm函数实现：staticinlineintscheddowncommon（structsemaphoresem，longstate，longtimeout）｛structtaskstructtaskcurrent；当前进程代表的结构体structsemaphorewaiterwaiter；listaddtail（waiter。list，semwaitlist）；waiter。tasktask；waiter。upfalse；for（；；）｛if（signalpendingstate（state，task））gotointerrupted；if（unlikely（timeout0））gototimedout；settaskstate（task，state）；rawspinunlockirq（semlock）；timeoutscheduletimeout（timeout）；rawspinlockirq（semlock）；if（waiter。up）return0；｝timedout：listdel（waiter。list）；returnETIME；interrupted：listdel（waiter。list）；returnEINTR；｝staticnoinlinevoidscheddown（structsemaphoresem）｛downcommon（sem，TASKUNINTERRUPTIBLE，MAXSCHEDULETIMEOUT）；｝voiddown（structsemaphoresem）｛unsignedlongflags；rawspinlockirqsave（semlock，flags）；自旋锁if（likely（semcount0））semcount；elsedown（sem）；rawspinunlockirqrestore（semlock，flags）；｝
　　up函数实现：voidup（structsemaphoresem）｛unsignedlongflags；rawspinlockirqsave（semlock，flags）；自旋锁if（likely（listempty（semwaitlist）））semcount；elseup（sem）；rawspinunlockirqrestore（semlock，flags）；｝1。3、实现原理
　　信号量一般可以用来标记可用资源的个数。
　　举2个生活中的例子：我们要坐火车从南京到新疆，这个任务特别的耗时，只能在车上等着车到站，但是我们没有必要一直睁着眼睛等着车到站，最好的情况就是我们上车就直接睡觉，醒来就到站，这样从人（用户）的角度来说，体验是最好的，对比于进程，程序在等待一个耗时的任务的时候，没有必须要占用CPU，可以暂停当前任务使其进入休眠状态，当等待的事件发生之后再由其他任务唤醒，这种场景采用信号量比较合适。我们在等待电梯、等待洗手间，这种场景需要等待的事件并不是很多，如果我们还要找个地方睡一觉，然后等电梯到了或者洗手间可以用了再醒来，那很显然这也没有必要，我们只需要排好队，刷一刷抖音就可以了，对比于计算机程序，比如驱动在进入中断例程，在等待某个寄存器被置位，这种场景需要等待的时间很短暂，系统开销远小于进入休眠的开销，所以这种场景采用自旋锁比较合适。
　　dowm函数实现原理解析：
　　（1）down
　　判断semcount是否0，大于0则说明系统资源够用，分配一个给该进程，否则进入down（sem）；
　　（2）down
　　调用downcommon（sem，TASKUNINTERRUPTIBLE，MAXSCHEDULETIMEOUT）；其中TASKUNINTERRUPTIBLE2代表进入睡眠，且不可以打断；MAXSCHEDULETIMEOUT休眠最长LONGMAX时间；
　　（3）listaddtail（waiter。list，semwaitlist）；
　　把当前进程加入到semwaitlist中；
　　（3）先解锁后加锁；
　　进入downcommon前已经加锁了，先把解锁，调用scheduletimeout（timeout），当waiter。up1后跳出for循环；退出函数之前再加锁；2、原子变量（atomic）
　　Linux内核ARM构架中原子变量的底层实现研究
　　rk3288原子操作和原子位操作
　　原子变量适用于只共享一个int型变量；2。1、特点
　　1、原子操作是指不被打断的操作，即它是最小的执行单位。
　　2、最简单的原子操作就是一条条的汇编指令（不包括一些伪指令，伪指令会被汇编器解释成多条汇编指令）2。2、常用函数
　　常见函数：defineATOMICINIT（i）｛（i）｝初始化原子变量defineatomicinc（v）atomicadd（1，v）原子变量加1defineatomicdec（v）atomicsub（1，v）原子变量减1defineatomicincandtest（v）（atomicaddreturn（1，v）0）原子变量加1并测试是否等于0defineatomicdecandtest（v）（atomicsubreturn（1，v）0）原子变量减1并测试是否等于02。3、实现原理
　　以atomicinc为例介绍实现过程
　　在Linux内核文件archarmincludeasmatomic。h中。执行atomicread、atomicset这些操作都只需要一条汇编指令，所以它们本身就是不可打断的。需要特别研究的是atomicinc、atomicdec这类读出、修改、写回的函数。
　　但是atomicadd在内核中是很难找到的，因为没有这个直接的声明。而是一种宏实现。
　　所以atomicadd的原型是下面这个宏：defineATOMICOPS（op，cop，asmop）ATOMICOP（op，cop，asmop）ATOMICOPRETURN（op，cop，asmop）ATOMICFETCHOP（op，cop，asmop）ATOMICOPS（add，，add）defineATOMICOP（op，cop，asmop）staticinlinevoidatomicop（inti，atomictv）｛unsignedlongtmp；intresult；prefetchw（vcounter）；asmvolatile（atomicop1：ldrex0，〔3〕asmop0，0，4strex1，0，〔3〕teq1，0bne1b：r（result），r（tmp），Qo（vcounter）：r（vcounter），Ir（i）：cc）；｝
　　atomicadd等效于：staticinlinevoidatomicadd（inti，atomictv）｛unsignedlongtmp；intresult；prefetchw（vcounter）；asmvolatile（atomicop1：ldrex0，〔3〕asmop0，0，4strex1，0，〔3〕teq1，0bne1b：r（result），r（tmp），Qo（vcounter）：r（vcounter），Ir（i）：cc）；｝
　　result（0）tmp（1）（vcounter）（2）（vcounter）（3）i（4）
　　注意：根据内联汇编的语法，result、tmp、vcounter对应的数据都放在了寄存器中操作。如果出现上下文切换，切换机制会做寄存器上下文保护。
　　（1）ldrex0，〔3〕
　　意思是将vcounter指向的数据放入result中，并且（分别在Localmonitor和Globalmonitor中）设置独占标志。
　　（2）add0，0，4
　　resultresulti
　　（3）strex1，0，〔3〕
　　意思是将result保存到vcounter指向的内存中，此时Exclusivemonitors会发挥作用，将保存是否成功的标志放入tmp中。
　　（4）teq1，0
　　测试strex是否成功（tmp0？？）
　　（5）bne1b
　　如果发现strex失败，从（1）再次执行。3、自旋锁（spinlock）
　　Spinlock是内核中提供的一种比较常见的锁机制，自旋锁是原地等待的方式解决资源冲突的，即，一个线程获取了一个自旋锁后，另外一个线程期望获取该自旋锁，获取不到，只能够原地打转（忙等待）。由于自旋锁的这个忙等待的特性，注定了它使用场景上的限制自旋锁不应该被长时间的持有（消耗CPU资源），一般应用在中断上下文。3。1、特点
　　1、spinlock是一种死等机制
　　2、信号量可以允许多个执行单元进入，spinlock不行，一次只能允许一个执行单元获取锁，并且进入临界区，其他执行单元都是在门口不断的死等
　　3、由于不休眠，因此spinlock可以应用在中断上下文中；
　　4、由于spinlock死等的特性，因此临界区执行代码尽可能的短；3。2、常用函数
　　spinlock加锁以及解锁过程：
　　spinlock（deviceslock）；
　　临界区代码
　　spinunlock（deviceslock）；
　　spinlock初始化definespinlockinit（lock）do｛spinlockcheck（lock）；rawspinlockinit（（lock）rlock）；｝while（0）
　　进程和进程之间同步staticalwaysinlinevoidspinlock（spinlocktlock）｛rawspinlock（lockrlock）；｝
　　本地软中断之间同步staticalwaysinlinevoidspinlockbh（spinlocktlock）｛rawspinlockbh（lockrlock）；｝
　　本地硬中断之间同步staticalwaysinlinevoidspinlockirq（spinlocktlock）｛rawspinlockirq（lockrlock）；｝
　　本地硬中断之间同步并且保存本地中断状态definespinlockirqsave（lock，flags）do｛rawspinlockirqsave（spinlockcheck（lock），flags）；｝while（0）
　　尝试获取锁staticalwaysinlineintspintrylock（spinlocktlock）｛returnrawspintrylock（lockrlock）；｝3。3、实现原理
　　archspinlockt结构体定义如下：defineTICKETSHIFT16typedefstruct｛union｛u32slock；unionstructrawtickets｛ifdefARMEB大端模式u16next；u16owner；else小端模式u16owner；u16next；endif｝tickets；｝；｝archspinlockt；
　　archspinlock的实现如下：staticinlinevoidarchspinlock（archspinlocktlock）｛unsignedlongtmp；u32newval；archspinlocktlockval；prefetchw（lockslock）；从lock中取出slockasmvolatile（1：ldrex0，〔3〕add1，0，4strex2，1，〔3〕teq2，0bne1b：r（lockval），r（newval），r（tmp）：r（lockslock），I（1TICKETSHIFT）：cc）；while（lockval。tickets。next！lockval。tickets。owner）｛wfe（）；等待，系统开销很大lockval。tickets。ownerACCESSONCE（locktickets。owner）；｝smpmb（）；｝
　　lockval（0）newval（1）tmp（2）lockslock（3）1TICKETSHIFT（4）
　　（1）ldrex0，〔3〕
　　把lockslock的值赋值给lockval；并且（分别在Localmonitor和Globalmonitor中）设置独占标志。
　　（2）add1，0，4
　　newvallockval（116）；相当于next1；
　　（3）strex2，1，〔3〕
　　newvallockval（116）；相当于next1；
　　意思是将newval保存到lockslock指向的内存中，此时Exclusivemonitors会发挥作用，将保存是否成功的标志放入tmp中。
　　（4）teq2，0
　　测试strex是否成功
　　（5）bne1b
　　如果发现strex失败，从（1）再次执行。
　　通过上面的分析，可知关键在于strex的操作是否成功的判断上。而这个就归功于ARM的Exclusivemonitors和ldrexstrex指令的机制。
　　（6）while（lockval。tickets。next！lockval。tickets。owner）
　　如何lockval。tickets的next和owner是否相等。相同则跳出while循环，否则在循环内等待判断；
　　（7）wfe（）和smpmb（）最终调用definebarrier（）asmvolatile（：：：memory）
　　阻止编译器重排，保证编译程序时在优化屏障之前的指令不会在优化屏障之后执行。
　　archspinunlock的实现如下：staticinlinevoidarchspinunlock（archspinlocktlock）｛smpmb（）；locktickets。owner；dsbsev（）；｝
　　退出锁时：tickets。owner3。4、死锁以及解决办法
　　出现死锁的情况：
　　1、拥有自旋锁的进程A在内核态阻塞了，内核调度B进程，碰巧B进程也要获得自旋锁，此时B只能自旋转。而此时抢占已经关闭，（单核）不会调度A进程了，B永远自旋，产生死锁。
　　2、进程A拥有自旋锁，中断到来，CPU执行中断函数，中断处理函数，中断处理函数需要获得自旋锁，访问共享资源，此时无法获得锁，只能自旋，产生死锁。
　　如何避免死锁：
　　1、如果中断处理函数中也要获得自旋锁，那么驱动程序需要在拥有自旋锁时禁止中断；
　　2、自旋锁必须在可能的最短时间内拥有
　　3、避免某个获得锁的函数调用其他同样试图获取这个锁的函数，否则代码就会死锁；不论是信号量还是自旋锁，都不允许锁拥有者第二次获得这个锁，如果试图这么做，系统将挂起；
　　4、锁的顺序规则（a）按同样的顺序获得锁；b）如果必须获得一个局部锁和一个属于内核更中心位置的锁，则应该首先获取自己的局部锁；c）如果我们拥有信号量和自旋锁的组合，则必须首先获得信号量；在拥有自旋锁时调用down（可导致休眠）是个严重的错误的；）3。5、其他类型的spinlock
　　rw（readwrite）spinlock：
　　加锁逻辑：
　　1、假设临界区内没有任何的thread，这个时候任何的读线程和写线程都可以键入
　　2、假设临界区内有一个读线程，这时候信赖的read线程可以任意进入，但是写线程不能进入；
　　3、假设临界区有一个写线程，这时候任何的读、写线程都不可以进入；
　　4、假设临界区内有一个或者多个读线程，写线程不可以进入临界区，但是写线程也无法阻止后续的读线程继续进去，要等到临界区所有的读线程都结束了，才可以进入，可见：rw（readwrite）spinlock更加有利于读线程；
　　seqlock（顺序锁）：
　　加锁逻辑：
　　1、假设临界区内没有任何的thread，这个时候任何的读线程和写线程都可以键入
　　2、假设临界区内没有写线程的情况下，read线程可以任意进入；
　　3、假设临界区有一个写线程，这时候任何的读、写线程都不可以进入；
　　4、假设临界区内只有read线程的情况下，写线程可以理解执行，不会等待，可见：seqlock（顺序锁）更加有利于写线程；3。6、spinlock的不足之处
　　读写速度：CPU一级缓存二级缓存内存，因此某一个CPU0的lock修改了，其他的CPU的lock就会失效；那么其他CPU就会依次去L1L2和主存中读取lock值，一旦其他CPU去读取了主存，就存在系统性能降低的风险；4、互斥体（mux）
　　mutex用于互斥操作。
　　互斥体只能用于一个线程，资源只有两种状态（占用或者空闲）4。1、特点
　　1、mutex的语义相对于信号量要简单轻便一些，在锁争用激烈的测试场景下，mutex比信号量执行速度更快，可扩展
　　性更好，
　　2、另外mutex数据结构的定义比信号量小；、
　　3、同一时刻只有一个线程可以持有mutex
　　4、不允许递归地加锁和解锁
　　5、当进程持有mutex时，进程不可以退出。
　　mutex必须使用官方API来初始化。
　　mutex可以睡眠，所以不允许在中断处理程序或者中断下半部中使用，例如tasklet、定时器等4。2、常用函数
　　常见操作：
　　structmutexmutex1；
　　mutexinit（mutex1）；
　　mutexlock（mutex1）
　　临界区代码；
　　mutexunlock（mutex1）
　　常见函数：mutexlock（structmutex）为指定的mutex上锁，如果不可用则睡眠mutexunlock（structmutex）为指定的mutex解锁mutextrylock（structmutex）尝试获取指定的mutex，如果成功则返回1；否则锁被获取，返回值是0mutexislock（structmutex）如果锁已被征用，则返回1；否则返回0