等待队列wait_queue

核心结论先行add_waitqueue是Linux内核中一个非常基础且核心的函数它的意思是将一个进程通过其wait_queue_t结构体添加到一个等待队列wait_queue_head_t中使该进程进入睡眠状态等待某个特定事件的发生。简单来说它就是实现**“进程等待”**这一功能的关键入口。一、 为什么需要add_wait_queue在操作系统中进程经常需要等待某些资源或事件。例如一个读文件的进程需要等待磁盘I/O完成。一个网络服务器进程需要等待客户端的连接请求。一个进程需要等待另一个进程释放它持有的锁。如果一个进程需要等待但它不主动放弃CPU就会进入**“忙等待”Busy Waiting**状态即不断地检查条件是否满足。这会浪费大量的CPU资源。二、 关键数据结构1.wait_queue_head_t(等待队列头)这是一个队列的“管理者”或“句柄”。它代表了一个特定的等待事件。任何想等待这个事件的进程都必须把自己加入到这个队列头所管理的队列中。// 简化的定义structwait_queue_head{spinlock_tlock;// 保护队列的自旋锁structlist_headtask_list;// 等待队列的链表头};typedefstructwait_queue_headwait_queue_head_t;lock因为可能有多个CPU上的进程同时尝试加入或离开队列所以必须有锁来保证操作的原子性。task_list这是一个双向链表用来链接所有等待在这个队列上的进程。2.wait_queue_entry(等待队列元素)这代表了一个正在等待的进程。每个想要等待的进程都必须创建一个wait_queue_entry结构并将其与自己关联起来。structwait_queue_entry{unsignedintflags;void*private;// 通常指向等待的进程 task_structwait_queue_func_tfunc;// 唤醒时要调用的回调函数structlist_headentry;// 用于链接到 wait_queue_head_t 的链表节点};private这是一个通用指针几乎总是被设置为指向当前进程的task_struct。func这是一个回调函数。当事件发生需要唤醒等待者时内核会调用这个函数。最常见的函数是autoremove_wake_function它会唤醒进程并将其从等待队列中自动移除。entry这是链表节点通过它wait_queue_t才能被挂接到wait_queue_head_t的task_list链表上。三、add_wait_queue的工作流程add_wait_queue函数的原型如下voidadd_wait_queue(wait_queue_head_t*q,wait_queue_t*wait);将wait_queue_entry结构通过其entry成员添加到wait_queue_head_t的task_list链表的尾部。add_wait_queue只负责将进程的“名片”wait_queue_entry放入队列它本身并不会让进程睡眠。让进程睡眠是在调用add_wait_queue之后由调用者自己完成的。四、 一个完整的等待-唤醒场景示例下面是一个典型的、简化的内核代码模式展示了add_wait_queue如何与其他函数协同工作。场景一个进程正在等待一个设备准备好。// 1. 定义一个等待队列头代表“设备准备好”这个事件wait_queue_head_tmy_device_waitq;init_waitqueue_head(my_device_waitq);// 等待者进程的代码voidmy_process_waiting(){// 2. 定义并初始化一个等待队列元素DEFINE_WAIT(wait);// 这是一个宏会自动创建并初始化 wait_queue_t// 3. 循环检查条件这是一个标准模式while(my_device_is_not_ready()){// 4. 将自己添加到等待队列中add_wait_queue(my_device_waitq,wait);// 5. 将进程状态设置为 TASK_INTERRUPTIBLE (可中断睡眠)// 如果设置为 TASK_UNINTERRUPTIBLE则不可被信号中断set_current_state(TASK_INTERRUPTIBLE);// 6. 再次检查条件。这是一个防止“竞态条件”的关键步骤。// 因为在 add_wait_queue 和 schedule() 之间设备可能已经准备好了。if(my_device_is_not_ready()){// 7. 放弃CPU进入睡眠状态schedule();}// 8. 被唤醒后将自己从等待队列中移除remove_wait_queue(my_device_waitq,wait);// 9. 检查是否是被信号唤醒例如用户按了CtrlCif(signal_pending(current)){// 如果是被信号中断则处理错误并退出return-ERESTARTSYS;}}// 10. 设备已经准备好继续执行...printk(Device is ready!\n);}//用wait_event_interruptible替代上述代码intmy_process_waiting(void){intret;retwait_event_interruptible(my_device_waitq,!my_device_is_not_ready());if(ret)returnret;printk(Device is ready!\n);return0;}// 唤醒者的代码 (例如设备驱动程序的中断处理函数)voidmy_device_interrupt_handler(){// ... 处理硬件中断 ...// 设备现在准备好了唤醒等待的进程wake_up(my_device_waitq);}在使用DEFINE_WAIT(wait)/init_waitqueue_entry(wait, current)中都使用初始化了wq_entry-func为autoremove_wake_functionintautoremove_wake_function(structwait_queue_entry*wq_entry,unsignedmode,intsync,void*key){intretdefault_wake_function(wq_entry,mode,sync,key);if(ret)list_del_init(wq_entry-entry);returnret;}#defineDEFINE_WAIT_FUNC(name,function)\structwait_queue_entryname{\.privatecurrent,\.funcfunction,\.entryLIST_HEAD_INIT((name).entry),\}#defineDEFINE_WAIT(name)DEFINE_WAIT_FUNC(name,autoremove_wake_function)-在使用wake_up(waitq_head)后流程如下 c/* Convenience macros for the sake of wake_up(): */#defineTASK_NORMAL(TASK_INTERRUPTIBLE|TASK_UNINTERRUPTIBLE)#definewake_up(x)__wake_up(x,TASK_NORMAL,1,NULL)void__wake_up(structwait_queue_head*wq_head,unsignedintmode,intnr_exclusive,void*key){__wake_up_common_lock(wq_head,mode,nr_exclusive,0,key);}staticvoid__wake_up_common_lock(structwait_queue_head*wq_head,unsignedintmode,intnr_exclusive,intwake_flags,void*key){unsignedlongflags;wait_queue_entry_tbookmark;bookmark.flags0;bookmark.privateNULL;bookmark.funcNULL;INIT_LIST_HEAD(bookmark.entry);do{spin_lock_irqsave(wq_head-lock,flags);nr_exclusive__wake_up_common(wq_head,mode,nr_exclusive,wake_flags,key,bookmark);spin_unlock_irqrestore(wq_head-lock,flags);}while(bookmark.flagsWQ_FLAG_BOOKMARK);}staticint__wake_up_common(structwait_queue_head*wq_head,unsignedintmode,intnr_exclusive,intwake_flags,void*key,wait_queue_entry_t*bookmark){wait_queue_entry_t*curr,*next;intcnt0;lockdep_assert_held(wq_head-lock);if(bookmark(bookmark-flagsWQ_FLAG_BOOKMARK)){currlist_next_entry(bookmark,entry);list_del(bookmark-entry);bookmark-flags0;}elsecurrlist_first_entry(wq_head-head,wait_queue_entry_t,entry);if(curr-entrywq_head-head)returnnr_exclusive;list_for_each_entry_safe_from(curr,next,wq_head-head,entry){unsignedflagscurr-flags;intret;if(flagsWQ_FLAG_BOOKMARK)continue;retcurr-func(curr,mode,wake_flags,key);//default_wake_functionif(ret0)break;if(ret(flagsWQ_FLAG_EXCLUSIVE)!--nr_exclusive)break;if(bookmark(cntWAITQUEUE_WALK_BREAK_CNT)(next-entry!wq_head-head)){bookmark-flagsWQ_FLAG_BOOKMARK;list_add_tail(bookmark-entry,next-entry);break;}}returnnr_exclusive;}intdefault_wake_function(wait_queue_entry_t*curr,unsignedmode,intwake_flags,void*key){returntry_to_wake_up(curr-private,mode,wake_flags);}总结与类比add_waitqueue的过程可以比作在餐厅排队等位。wait_queue_head_t是餐厅的“等位名单”。wait_queue_t是你填写的**“等位号牌”**上面有你的信息private指向task_struct。add_waitqueue()是你把号牌交给服务员服务员把它放到名单的末尾。set_current_state()是你告诉服务员你现在要去旁边的沙发上休息进入睡眠状态。schedule()是你闭上眼睛开始休息不再关注叫号。wake_up()是服务员叫到你的号把你从睡眠中唤醒。remove_wait_queue()是你听到叫号后从名单上取回自己的号牌准备去就餐。wait_event_interruptbookmark(书签)核心结论先行bookmark书签在这段代码中的意思是在遍历一个非常长的等待队列时为了避免单次唤醒操作耗时过长而设置的一个“断点”。当等待队列中的进程数量超过一个阈值WAITQUEUE_WALK_BREAK_CNT通常是16时唤醒操作会主动中断当前的遍历并将这个bookmark插入到队列中。当下一次唤醒操作发生时内核会从这个bookmark的位置继续遍历而不是从头开始。这是一种**“分而治之”**的策略用于处理可能包含成千上万个等待进程的极端场景。一、 为什么需要bookmark想象一个场景一个热门的网络服务器套接字socket上有成千上万个客户端进程在accept()调用中阻塞等待新的连接。当一个新的连接到达时内核会调用wake_up()来唤醒等待队列上的进程。如果没有bookmark会发生什么wake_up()会从头开始遍历整个等待队列。它会逐个调用每个wait_queue_t元素的func回调函数即try_to_wake_up。这个过程可能需要很长时间在此期间CPU被长时间占用唤醒操作本身变成了一个耗时的任务。等待队列锁被长时间持有在遍历期间wait_queue_head_t的自旋锁一直被持有。这会阻塞其他CPU上试图添加或移除等待者的操作可能成为系统的性能瓶颈。对于这种“惊群效应”Thundering Herd的场景一次性唤醒所有等待者是低效且不必要的通常只有一个进程能成功accept连接。bookmark机制就是为了缓解这个问题。二、bookmark的工作流程我们来逐行分析这段代码// curr: 当前遍历到的元素// next: 下一个要遍历的元素// wq_head: 等待队列头// entry: 链表节点成员名list_for_each_entry_safe_from(curr,next,wq_head-head,entry){// ... 省略部分代码 ...// 检查是否需要设置书签if(bookmark(cntWAITQUEUE_WALK_BREAK_CNT)(next-entry!wq_head-head)){// 1. 标记这是一个书签bookmark-flagsWQ_FLAG_BOOKMARK;// 2. 将书签插入到下一个元素之前list_add_tail(bookmark-entry,next-entry);// 3. 中断遍历break;}}阶段一触发书签if (bookmark ...)bookmark参数必须不为NULL。这通常在__wake_up_common函数中由调用者如wake_up提供。cnt WAITQUEUE_WALK_BREAK_CNTcnt是一个计数器记录本次遍历已经唤醒了多少个进程。当这个数量超过一个小的阈值如16时条件成立。next-entry ! wq_head-head确保我们还没有遍历完整个队列。阶段二设置书签bookmark-flags WQ_FLAG_BOOKMARK;这是最关键的一步。它将一个普通的wait_queue_t结构体bookmark标记为一个特殊的“书签”节点。在后续的遍历中代码会检查这个标志并跳过它。list_add_tail(bookmark-entry, next-entry);这行代码将bookmark节点插入到链表中位置正好在next节点的前面。效果它在当前遍历的位置“夹”了一个书签。break;立即中断list_for_each_entry_safe_from循环。本次唤醒操作到此结束。阶段三后续唤醒断点续传当下一次wake_up()被调用时或者在本次唤醒的后续逻辑中list_for_each_entry_safe_from宏会从它上次中断的地方继续list_for_each_entry_safe_from这个宏的_from版本非常重要。它告诉循环从curr指针指向的元素开始遍历而不是从头开始。跳过书签在循环的开头会有类似if (curr-flags WQ_FLAG_BOOKMARK) continue;的检查。当遍历到我们上次插入的bookmark节点时由于它的WQ_FLAG_BOOKMARK标志被设置循环会直接跳过它继续处理后面的节点。移除书签在遍历开始前内核通常会先检查队列中是否存在bookmark。如果存在会先将其从队列中移除然后再从该位置开始新的遍历。总结与类比bookmark机制就像是阅读一本厚厚的书没有书签你每次都必须从第一页开始读直到找到你上次读到的地方这非常耗时。使用书签你读到第16页WAITQUEUE_WALK_BREAK_CNT觉得累了就在第17页夹了一个书签bookmark。你合上书休息break循环。第二天你直接打开书签所在的第17页list_for_each_entry_safe_from然后扔掉书签list_del继续从第17页往下读。通过这种方式bookmark将一个潜在的长时间、高开销的唤醒操作分解成了多个小的、可管理的步骤从而显著提高了系统在高负载下的响应性和吞吐量。排他等待核心结论先行一个“排他等待状态的进程”是指一个进程在调用add_wait_queue_exclusive()函数将自己加入等待队列时通过一个特殊的标志位WQ_FLAG_EXCLUSIVE向内核声明了自己的“排他性”。这个声明的含义是“当我所等待的事件发生时内核只需要唤醒我一个就足够了。请不要唤醒其他也声明了排他性的进程。”一、 如何进入“排他等待状态”一个进程并不是天生就有“排他等待”这个属性的。它是通过调用特定的函数来主动申请的。非排他等待通过add_wait_queue()函数加入队列。排他等待通过add_wait_queue_exclusive()函数加入队列。这两个函数的核心区别在于add_wait_queue_exclusive()在将进程的wait_queue_t结构加入队列时会为其设置一个标志位// 内核源码简化版voidadd_wait_queue_exclusive(wait_queue_head_t*q,wait_queue_t*wait){unsignedlongflags;wait-flags|WQ_FLAG_EXCLUSIVE;// --- 关键在这里spin_lock_irqsave(q-lock,flags);__add_wait_queue_tail(q,wait);// 注意排他等待者被加到队列尾部spin_unlock_irqrestore(q-lock,flags);}关键点设置WQ_FLAG_EXCLUSIVE标志这是“排他性”的唯一凭证。添加到队列尾部排他等待的进程总是被添加到等待队列的末尾。这确保了在唤醒时排在前面的排他等待者会被优先考虑。二、 为什么需要“排他等待状态”这一切都是为了避免“惊群效应”Thundering Herd Problem。“惊群效应”场景想象有100个Web服务器进程worker都在accept()系统调用上阻塞等待同一个网络端口上的客户端连接。事件发生一个客户端连接请求到达。非排他唤醒如果所有进程都是非排他等待wake_up()会唤醒所有100个进程。激烈竞争这100个进程被同时唤醒它们会去争抢这个唯一的连接资源。资源浪费最终只有1个进程能成功accept()到连接其余99个进程发现资源已被抢占只能再次进入睡眠状态。这个过程浪费了大量的CPU时间和系统资源。“排他等待”如何解决这个问题如果这100个进程都是通过add_wait_queue_exclusive()进入排他等待状态事件发生一个客户端连接请求到达。排他唤醒wake_up()函数开始遍历等待队列。识别排他标志它看到队列中的进程都带有WQ_FLAG_EXCLUSIVE标志。唤醒一个然后停止wake_up()会唤醒它遇到的第一个排他等待进程然后立即break循环停止唤醒。高效处理只有这一个幸运的进程被唤醒它可以从容地accept()连接没有任何竞争。其余99个进程继续在队列中安静地睡眠等待下一个连接。三、 唤醒逻辑的精确解析现在我们回到__wake_up_common的核心唤醒循环看看它是如何处理这两种状态的// 伪代码简化了内核逻辑void__wake_up_common(...){// ...intnr_exclusivewq-nr_exclusive;// 通常是1list_for_each_entry_safe(curr,next,wq_head-head,entry){// 1. 如果是排他等待者if(curr-flagsWQ_FLAG_EXCLUSIVE){// 2. 如果我们还需要唤醒排他等待者if(nr_exclusive0){// 3. 唤醒它curr-func(curr,...);// 调用 try_to_wake_up// 4. 已经唤醒了一个计数器减1nr_exclusive--;}// 5. 无论是否唤醒只要遇到排他等待者就停止遍历break;}// 6. 如果是非排他等待者则直接唤醒else{curr-func(curr,...);}}}这个逻辑清晰地展示了对于非排他等待者没有WQ_FLAG_EXCLUSIVE标志wake_up会逐个唤醒它们直到遇到第一个排他等待者。对于排他等待者wake_up会唤醒一个然后立即break不再继续唤醒其他任何进程无论是排他的还是非排他的。总结与类比非排他等待像在一个开放式的广场上等待。一旦有消息大喇叭会通知所有人。所有人都听到了然后去抢一个东西。排他等待像在一个银行排队。大家都在排队WQ_FLAG_EXCLUSIVE标志保安wake_up函数只允许排在最前面的一个人进入窗口办理业务后面的人继续排队。“排他等待状态”是进程在进入睡眠前与内核之间达成的一个**“君子协定”**。进程告诉内核“我只需要一个机会请不要把所有同伴都吵醒。” 而内核则忠实地履行了这个协定从而极大地提升了系统在高并发场景下的性能和稳定性。