LINUX内核信号量设计与实现.pdf

该【LINUX内核信号量设计与实现 】是由【知识徜徉土豆】上传分享，beplayapp体育下载一共【19】页，该beplayapp体育下载可以免费在线阅读，需要了解更多关于【LINUX内核信号量设计与实现 】的内容，可以使用beplayapp体育下载的站内搜索功能，选择自己适合的beplayapp体育下载，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此beplayapp体育下载到您的设备，方便您编辑和打印。:..GeneratedbyFoxitPDFCreator?******@2008/08/18一LINUX内核信号量简介为了同步对内核共享资源的访问,内核提供了down函数和up函数用于获取和释放资源。down和up所保护的访问资源的内核代码区域,就构成一个临界区。在等待获取资源进入临界区的过程中,代表进程运行的内核控制路径可以睡眠。我们从LINUX内核信号量最直观的设计/实现出发,通过一步步改进,揭示在x86平台上完整的信号量设计/实现,然后探讨在不同平台上通用的信号量设计/实现。二LINUX内核信号量的初步设计与实现1数据结构我们首先分析信号量semphore应具备的数据结构。它需要一个计数count,表示能进入临界区的进程个数。conut一般初始化为1,表示信号量是互斥信号量,一次只允许一个进程进入临界区。它也能被初始化为其他正值,表示可有多个进程同时进入临界区。当进程不能进入临界区时,它必须在信号量上睡眠,因此需要一个表示“等待队列头”的字段wait。在SMP中,等待队列需要自旋锁来保护,因此wait结构中应含有自旋锁lock,和指向等待队列链表的指针task_list。而插入等待队列的“等待元素”,其字段中应含有指向进程结构的指针task,及能够链入等待队列的指针task_list。:..GeneratedbyFoxitPDFCreator?:structwait_queue_t{structtask_struct*task;structlist_headtask_list;};/*等待元素结构*/structwait_queue_head_t{spinlock_tlock;structlist_headtask_list;};/*等待队列头结构*/structsemphore{intcount;wait_queue_head_twait;}/*信号量结构*/2算法当进程需要获取信号量时,它调用down函数进入临界区。down将semphore的count字段减1,若count非负,则可进入临界区;否则,加入睡眠队列。当进程离开临界区时,它调用up函数。up将semphore的count字段加1,若count非正,表示有进程睡眠,则将进程从wait等待队列中移走并唤醒它。这里有一个问题:当up唤醒等待队列中睡眠进程时,是唤醒所有等待进程,还是只唤醒一个?如果唤醒所有进程,它们醒来后,就会去竞争一个获得信号量的机会,竞争失败的进程只能再度睡眠,这就使得系统有许多无谓的schedule切换,降低了系统性能。所以,up只唤醒一个进程。为了保持FIFO的唤醒顺序,down会将新进程以独占方式(表示唤醒时只唤醒一个)加在等待队列尾部,up则去唤醒等待队列头部的第一个独占进程。3实现由于信号量的实现效率与系统性能息息相关,为了达到高效的信号量实现,不同的cpu系统根据各自特点,提供了不同版本。我们以x86平台为例,介绍信号量的实现与优化。我们要注意一点:由于x86平台对原子指令有很好的支持,而并发的多个进程可能:..GeneratedbyFoxitPDFCreator?,所以对count的修改与读取都要使用原子指令。为了达到高效,down函数与up函数都使用汇编语言实现。down函数特别要保证:进程能以最快的速度,判断出能否进入临界区。这样才能保证高效的系统性能。按上述算法,其实现过程是很直接的。设sem是类型为structsemphore的信号量地址。down:movl$sem,%ecxlock;decl(%ecx);jns1f/*如非负,则往前跳到标号1处进入临界区*//*调用者堆栈保存约定*/pushl%eaxpushl%edxpushl%ecxcall__down/*如为负,调用__down加入睡眠队列*/popl%ecxpopl%edxpopl%eax1:void__down(structsemaphore*sem){structtask_struct*tsk=current;/*申明“等待元素结构”,并将结构中的进程指针初始化为tsk*/DECLARE_WAITQUEUE(wait,tsk);tsk->state=TASK_UNINTERRUPTIBLE;/*将wait表示的“等待元素”以独占方式加在sem->wait表示的等待队列尾部*/add_wait_queue_exclusive(&sem->wait,&wait);schedule();}up:movl$sem,%ecxlock;incl(%ecx);jg1f/*如为正,则往前跳到标号1处执行up后第一条指令*//*调用者堆栈保存约定*/pushl%eaxpushl%edxpushl%ecxcall__up/*如为非正,调用__up唤醒睡眠进程*/popl%ecxpopl%edxpopl%eax1::..GeneratedbyFoxitPDFCreator?(structsemaphore*sem){/*在sem->wait表示的等待队列中,获取其第一个“等待元素”wait*/structwait_queue_t*wait=list_entry(&sem->,structwait_queue_t,task_list);remove_wait_queue(&sem->wait,&wait);/*在等待队列中删除“等待元素”*/wake_up(sem->wait);/*唤醒等待队列中的第一个“等待元素”所表示的独占进程*/}三一步步改进信号量的设计与实现前面提到过,信号量的实现效率与系统性能息息相关。下面,我们围绕如何提高性能,对上述信号量的设计/实现进行改进。1分析上述实现中的性能问题我们设想这样的情景:当wait等待队列不空时,up出现,它唤醒wait队列的第一个进程prev。与此同时,有一个进程next(通过内核控制路径)调用down试图进入临界区。但prev原来调用down试图进入临界区时对count减1,在未能进入临界区而睡眠时并未恢复,直到prev被唤醒并调度执行进入临界区,而且执行完临界区代码,再调用up时才会对count增1。所以,进程next只可能在prev之后,进入临界区。也就是说:进程完全是按照发出down调用的次序,以FIFO方式进入临界区,这非常公平。但我们要注意一点:当up出现时,说明可有一个进程进入临界区。如果prev的优先级较低,它被唤醒后,很可能长时间都不能获得调度,在这段时间内,尽管允许进程进入临界区,而且进程next又试图进入临界区,但任何试图进入临界区的进程发只能睡眠!我们从系统性能的角度来考察是否允许next在prev之前进入临界区。对内核信号量的争用,影响系统性能的关键就是进程上下文切换schedule的代价。如果不允许next在prev之前进入临界区,则next必须被shedule切换掉。而允许next在prev之前进入临界区,则prev“至多”再次被shedule。而在以下两种情形下,prev无须被再次shedule切换掉。a在单cpu上,up唤醒prev后,由于进程next在prev之前获得调度运行,prev无须再次进行shedule切换。:..GeneratedbyFoxitPDFCreator?,如果next在prev获得调度之前,执行完临界区代码,则也可减少一次对prev的shedule切换。所以,如果允许进程next在up后,但在prev获得调度前进入临界区,能减少系统进行schedule切换的次数,则系统的性能就会获得提高,系统会更有效率。其弊端是:后发出down调用的进程可能先获取信号量,一定程度上违背了公平原则。如果允许next提前进入临界区,则原来的代码必须进行修改:当进程不能获取信号量而睡眠时,count要增1,抵消调用down时的无条件减1。当进程睡眠醒来时,相当于进程调用down之前的状态:可能与新进入的调用down的进程竞争信号量。它再次尝试进入临界区的方式也应该与down一致:count先减1,再判断能否进入临界区。因此__down将被改写为:void__down(structsemaphore*sem){structtask_struct*tsk=current;DECLARE_WAITQUEUE(wait,tsk);for(;;){/*被唤醒后,还需再次判断能否进入临界区*/atomic_inc(&sem->count);/*睡眠前恢复count*/tsk->state=TASK_UNINTERRUPTIBLE;add_wait_queue_exclusive(&sem->wait,&wait);schedule();tsk->state=TASK_UNINTERRUPTIBLE;atomic_dec(&sem->count);/*尝试进入临界区前,先减1*/if(atomic_read((&sem->count)>=0)/*重新判断能否进入临界区*/break;}tsk->state=TASK_RUNNING;}在上述实现中,进程不一定按FIFO进入临界区。而在进程尝试进入临界区时,总是无条件先减1,直到不能进入临界区时,才恢复count值。这种对count“优先减1”的处理方法,使得在一些局部的时段,count的值会比“能进入临界区的”进程个数要小。这种实现上的特点,使得它能确保同时进入临界区的进程不会超过count初值所限定的数目,但可能导致本来能进入临界区的进程无法进入临界区,特别是导致唤醒事件的丢失或延迟,这是我们在下面要尤其关注的。:..GeneratedbyFoxitPDFCreator?,上述实现其实存在错误。考察下述情景:假设进程A已进入临界区,进程B在等待队列。A调用up增加sem->count,唤醒进程B,同时进程C也调用__down试图进入临界区。假设事件发生的时序如下(表示形式:指令[所属进程顺序]):lock;decl(%ecx)[C1]lock;incl(%ecx)[A2]atomic_dec(&sem->count)[B3]if(atomic_read((&sem->count)>=0)[B4]atomic_inc(&sem->count)[B5]atomic_inc(&sem->count)[C6]注:上述%ecx的值就是&sem->count显然,如果按照这个时序,不管进程B还是C都会睡眠。只有下一个up才能将它们唤醒,这就相当于丢失了一次唤醒事件。出现这个问题的原因是:进程B对sem->count进行修改与判断时,进程C对sem->count的修改与判断也同时进行。要解决这个问题,必须把对sem->count的修改与判断放在一个自旋锁保护的“原子块”中,使得在同一个原子块中,对sem->count的判断与修改是一致的,而后一个原子块只能看到一致结果。我们引入专门用于信号量的全局自旋锁semaphore_lock,因此__down将被改写为:void__down(structsemaphore*sem){structtask_struct*tsk=current;DECLARE_WAITQUEUE(wait,tsk);spin_lock(&semaphore_lock);/*原子化sem->count的修改与判断*/for(;;){atomic_inc(&sem->count);spin_unlock(&semaphore_lock);tsk->state=TASK_UNINTERRUPTIBLE;add_wait_queue_exclusive(&sem->wait,&wait);schedule();tsk->state=TASK_UNINTERRUPTIBLE;spin_lock(&semaphore_lock);/*原子化sem->count的修改与判断*/atomic_dec(&sem->count);if(atomic_read((&sem->count)>=0)/*重新判断能否进入临界区*/break;}tsk->state=TASK_RUNNING;}但上述实现仍有问题。我们还是沿用同样的情景,假设进程B比进程C先获得semaphore_lock,则原来的时序也依然有效::..GeneratedbyFoxitPDFCreator?;decl(%ecx)[C1]lock;incl(%ecx)[A2]atomic_dec(&sem->count)[B3]if(atomic_read((&sem->count)>=0)[B4]atomic_inc(&sem->count)[B5]atomic_inc(&sem->count)[C6]不管进程B还是C仍旧会睡眠。不过,现在的原因是非常明显的:进程C获得semaphore_lock时,sem->count已经发生变化,但进程C并未读取判断sem->count,而是直接睡眠。只要将对sem->count的判断放在schedule之前,进程C就可以进入临界区。这种改变使得任何情形下执行的原子块都含有对sem->count的读取判断,因而就能“看到“前一个原子块对sem->count的一致修改。因此__down将被改写为:void__down(structsemaphore*sem){structtask_struct*tsk=current;DECLARE_WAITQUEUE(wait,tsk);spin_lock(&semaphore_lock);/*原子化sem->count的修改与判断*/for(;;){if(atomic_read((&sem->count)>=0)/*将判断放在schedule之前*/break;atomic_inc(&sem->count);spin_unlock(&semaphore_lock);tsk->state=TASK_UNINTERRUPTIBLE;add_wait_queue_exclusive(&sem->wait,&wait);schedule();tsk->state=TASK_UNINTERRUPTIBLE;spin_lock(&semaphore_lock);/*原子化sem->count的修改与判断*/atomic_dec(&sem->count);}tsk->state=TASK_RUNNING;}在下面的讨论中,我们还会将自旋锁所保护的代码区域称作一个“原子块”。为了对上述实现有一个更好的直观理解,我们来做一个小测试:假设count的初值为1。进程A已在临界区,进程B在等待队列,C,D,E同时调用__down试图进入临界区(即同时调用lock;decl(%ecx))。然后,C发现不能进入临界区,首先获取自旋锁,此时进程A调用up唤醒进程B,它们按B,D,E的顺序获取自旋锁。那么,B,C,D,E中的哪一个进程将进入临界区?:..GeneratedbyFoxitPDFCreator?。考察下述情景:假设进程A已进入临界区,进程B调用__down试图进入临界区,同时,A调用up增加sem->count,唤醒睡眠进程。假设事件发生的时序如下:lock;decl((%ecx)[B1]if(atomic_read((&sem->count)>=0)[B2]lock;incl(%ecx)[A3]wake_up(sem->wait)[A4]add_wait_queue_exclusive(&sem->wait,&wait)[B5]注:上述%ecx的值就是&sem->count结果是:进程B无法进入临界区而睡眠,但进程A却没有唤醒它!也是相当于丢失了一次唤醒事件。引起这个问题的原因,是因为进程B先判断sem->count,如果为负,然后加入睡眠队列。而进程A的唤醒事件在进程B“判断sem->count是否为负”和“加入睡眠队列”之间到来。如果将原代码改成:先加入等待队列,然后再判断sem->count,则不会出现上述竞态条件,问题迎刃而解。在LDD“中断处理”一章“无竞争地睡眠”一节也讲到了类似内容,将其称作“半睡眠状态时的检查”。在内核中,引入wait_event,wait_event_interruptible,就是为了解决由sleep_on,sleep_on_interrupitle引发的同样的唤醒丢失问题,而down进入睡眠的方式与wait_event一致。因此__down将被改写为:void__down(structsemaphore*sem){structtask_struct*tsk=current;DECLARE_WAITQUEUE(wait,tsk);tsk->state=TASK_UNINTERRUPTIBLE;spin_lock(&semaphore_lock);for(;;){/*将加入等待队列操作放在判断之前*/add_wait_queue_exclusive(&sem->wait,&wait);if(atomic_read((&sem->count)>=0)break;atomic_inc(&sem->count);spin_unlock(&semaphore_lock);schedule();tsk->state=TASK_UNINTERRUPTIBLE;spin_lock(&semaphore_lock);atomic_dec(&sem->count);}spin_unlock(&semaphore_lock);:..GeneratedbyFoxitPDFCreator?(&sem->wait,&wait);/*如能进入临界区,从等待队列中删除*/tsk->state=TASK_RUNNING;}考察这个实现,需要注意一点,add_wait_queue_exclusive函数需要获取sem->,它本身又在semaphore_lock自旋锁保护之内。如果获取sem->,就会使得由semaphore_lock自旋锁所保护临界区代码,执行时间过长,其他等待获得自旋锁的进程也会等待很长时间。另一方面,获取不同自旋锁的方式一般是:获取一把锁,释放后再获取另一把锁,以避免发生死锁。所以,需要在上述实现中将add_wait_queue_exclusive函数移到spin_lock(&semaphore_lock)之前,也即for循环之外。此时,会出现另一个问题:如果进程不能进入临界区而睡眠,当它被唤醒时,同时被__up从等待队列中删除,但由于add_wait_queue_exclusive在for循环之外,它不会重新加入等待队列!此时,需要我们改进__up:__up唤醒进程时,并不把它从等待队列中删除。这种改进还有一个额外的功效,能避免进程在尝试进入临界区的过程中,反复加入等待队列和从等待队列中删除,从而提高了性能。(但也会引发新的问题,我们在下一个步骤中就会看到)因此__down将被改写为:void__down(structsemaphore*sem){structtask_struct*tsk=current;DECLARE_WAITQUEUE(wait,tsk);tsk->state=TASK_UNINTERRUPTIBLE;/*将加入等待队列操作放在获取semaphore_lock之前*/add_wait_queue_exclusive(&sem->wait,&wait);spin_lock(&semaphore_lock);for(;;){if(atomic_read((&sem->count)>=0)break;atomic_inc(&sem->count);spin_unlock(&semaphore_lock);schedule();tsk->state=TASK_UNINTERRUPTIBLE;spin_lock(&semaphore_lock);atomic_dec(&sem->count);}spin_unlock(&semaphore_lock);remove_wait_queue(&sem->wait,&wait);tsk->state=TASK_RUNNING;}而__up将被改写为::..GeneratedbyFoxitPDFCreator?(structsemaphore*sem){wake_up(sem->wait);/*去掉从等待队列中删除进程的操作*/}4进入临界区前,弥补可能丢失的唤醒事件上述实现仍在问题。在上述实现中,进程一开始加入等待队列,被唤醒时仍然在等待队列里。直到获取sem,进入临界区之前,才从等待队列里删除。前面提到过,sem->count的初值一般为1,表示sem为互斥信号量。但sem的设计允许count的初值为任何正值,表示可有count个进程同时进入临界区。设想这样的情形:count的初值为2。进程A,B都在临界区里,进程C,D在睡眠队列里等待进入临界区,进程C在睡眠队列头部,进程A,B几乎同时调用up唤醒睡眠进程。假设事件发生的时序如下:wake_up(sem->wait)[A1]wake_up(sem->wait)[B2]remove_wait_queue(&sem->wait,&wait)[C3]这样,虽然有两次唤醒操作,但针对的都是进程C,进程D依然处于睡眠状态,相当于又丢失了一次唤醒事件。只有在进程C被调度执行并进入临界区,执行完临界区代码,然后调用up,进程D才能被唤醒。所以,严格来说,唤醒事件并未丢失,而是被严重延迟。引起这个问题的原因是:一个唤醒操作只能唤醒睡眠队列第一个进程,而且并未将其从等待队列中删除,使其仍然处在睡眠队列头,下一个唤醒操作可能又针对同一个进程。为了解决这个问题,在进程进入临界区之前,需再次调用wake_up(sem->wait),以弥补可能延迟的唤醒事件。需要额外注意的一点是,在linux中,还提供了一种down操作的非阻塞版本down_trylock:当不能获取信号量时,进程不睡眠而直接退出,它一般用在不能睡眠的中断服务例程和可延迟函数中。因此在上述实现中,如果在spin_lock保护的原子块中发生中断,而中断中又调用down_trylock,down_trylock也会调用spin_lock,就会导致死锁。因此,需将上述实现中涉及到spin_lock的地方,换成其带中断控制的版本。因此__down将被改写为:void__down(structsemaphore*sem){structtask_struct*tsk=current;DECLARE_WAITQUEUE(wait,tsk);:..GeneratedbyFoxitPDFCreator?->state=TASK_UNINTERRUPTIBLE;add_wait_queue_exclusive(&sem->wait,&wait);spin_lock_irq(&semaphore_lock);/*加上“禁止中断”功能*/for(;;){if(atomic_read(&sem->count)>=0)break;atomic_inc(&sem->count);spin_unlock_irq(&semaphore_lock);/*加上“允许中断”功能*/schedule();tsk->state=TASK_UNINTERRUPTIBLE;spin_lock_irq(&semaphore_lock);/*加上“禁止中断”功能*/atomic_dec(&sem->count);}spin_unlock_irq(&semaphore_lock);remove_wait_queue(&sem->wait,&wait);tsk->state=TASK_RUNNING;wake_up(&sem->wait);/*弥补可能丢失的唤醒事件*/}从直观上看,当存在“可能丢失的唤醒事件”时,sem->count的值应该大于0,那么,在__down最后对wake_up函数的调用能否改成条件判断,即:if(atomic_read(&sem->count)>0)wake_up(&sem->wait)当条件判断不满足时,就能减少对wake_up的调用,从而优化了程序性能。仔细一想,其实这是有问题的!设想这样的情形:count的初值为2。进程A正准备进入临界区,但尚未从等待队列中删除,依然位于等待队列头部。进程B已在临界区里,进程C在等待队列中,位于进程A之后。当进程A执行到__down的尾部spin_unlock_irq(&semaphore_lock)与remove_wait_queue(&sem->wait,&wait)之间时候,进程B调用up,与此同时,有一个进程D调用down试图进入临界区。假设事件发生时序如下:spin_unlock_irq(&semaphore_lock)[A1]lock;decl(%ecx)[D2]spin_lock_irq(&semaphore_lock)[D3]ifatomic_read(&sem->count)[D4]lock;incl(%ecx)[B5]wake_up(&sem->wait)[B6]remove_wait_queue(&sem->wait,&wait)[A7]if(atomic_read(&sem->count)>0)[A8]atomic_inc(&sem->count)[D9]按照这个时序,虽然进程B调用了up,但它不能唤醒进程C,也不能使进程D进入临界区,而[A8]处的判断,使得并不重新调用wake_up,因此,唤醒事件仍然丢失了!问题的根源在于:[A8]处的判断不在semaphore_lock的保护之下,这种判断是不可靠的,因而是无意义的。:..GeneratedbyFoxitPDFCreator?,尽量减少原子指令在上述实现中,用到了很多原子指令。而原子指令是很耗时的指令,并且在几乎所有系统中,它相当于memorybarrier,使得编译器和cpu都不能改变它前后的读写内存指令的顺序,因此也无法进行优化。因此,从程序性能的角度来讲,应该尽量避免使用原子指令。我们回忆一下:为避免“只有先调用down的进程才能先进入临界区”导致的系统性能损失,当进程无法进入临界区睡眠和被唤醒时,引入原子指令对count计数进行直接修改,使新调用down的进程有可能先进入临界区。在保证同样功能的前提下,要减少原子指令,关键是:当进程无法进入临界区而睡眠时,及当进程被唤醒时,尽量不要直接修改count的值,而且尽可能合并“修改与读取判断count的值”为一个原子指令。所以,我们可考虑一个两阶段修改count的方案:当进程无法进入临界区而睡眠时,不修改count,而是由下一个调用down的进程在count中将此1加上。具体实现中,我们在semphore结构