本文关注内容:Linux内核的一种数据结构:等待队列。在这里,我们不太去关注等待队列细节的实现。主要从功能角度谈下等待队列在内核中的角色。
我的观点是,不管是内核,还是内核中的某个组件,理解其角色定位很重要,单纯是从实现细节上去理解某种机制,或许少了点乐趣。
你理解阻塞吗?
写程序的时候,我们常常说某个系统调用是阻塞调用。从用户层的角度,基本理解是:进程在执行某个系统调用的时候,因为需要的资源不满足(IO操作,加锁等等),导致进程“停”在那里。等到资源就绪了或者设置的timeout时间超时了,进程得以继续执行。
从内核的角度,面对用户层对阻塞调用的需求,需要实现哪些机制呢?
- 1.首先,进程陷入内核,内核发现进程所要求的资源暂时无法满足,需要将其设置为睡眠状态,然后调度其他进程执行。这里引出一个问题:(1)内核如何将一个进程睡眠?
- 2.再来,等待资源就绪时,我们需要唤醒等待在该资源上面的进程。这里存在两个问题:(2)内核是怎么知道资源就绪的?以及,(3)某个资源就绪了,内核怎么找到对应等待的进程的?
示例:
我们希望对某个socket fd进行阻塞write操作。发起写操作的时候,陷入内核,内核发现该socket fd的写缓冲区是满的,暂时不能写。这时,内核将进程设置为睡眠。
调用其他进程执行。等到该写缓冲区可以写的时候,内核将进程设置为执行状态,然后执行写操作,拷贝数据到内核写缓冲区。执行完,切换回用户态。
问题一:内核如何将一个进程睡眠
进程的task_struct结构有一个状态成员。将其设置为“睡眠”,并将task_struct结构从就绪队列中移走,内核就不会调度其执行,也就相当于睡眠。
问题二:内核怎么知道资源就绪的
中断。内核的所有的工作都是由中断驱动的。不管是系统调用陷入内核,还是调度,还是其他的内核活动,都是由各种各样的中断来触发执行的。对于设备IO,如果设备空闲了,会触发一个外部中断,该中断触发内核执行处理程序,通知等待进程、执行回调等等。
问题三:资源就绪了,内核怎么找到对应等待的进程
答案是等待队列。我们将一个资源和一个等待队列关联起来。如果进程所请求的资源还未就绪,就先加入到该资源的等待队列中。等到资源就绪了,就唤醒等待队列中的进程,加入到调度。
何为等待队列
等待队列就是一个普通的双向链表,该链表的每个节点都代表一个进程task_struct的封装。每个资源都会有相应的等待队列。
等待队列与“惊群”
“惊群”的基本行为是:有多个进程或者线程等待在同一个资源上,而且该资源一次只能有一个进程处理,比如文件描述符的写操作,accept一个新连接等。那么在资源就绪的时候。如果内核采取的策略是唤醒所有的进程。这样,只有一个进程获取了该资源,其他进程发现没有资源就绪,继续进入睡眠(所谓虚假唤醒)。这样的行为浪费了系统的CPU资源。
那是不是,内核在资源就绪的时候,就唤醒一个进程不就得了。其实也不是,因为不是所有资源都是互斥的。比如,某个文件的读操作。
那么,惊群问题怎么解决?
在用户态,可以有不同的解决方式。或者忽略惊群所带来的开销,或者使用锁方式保证一次只有一个进程来阻塞在一个资源上。而对于内核来说,在等待队列上增加了一个是否“互斥等待”的标志。
如果是互斥等待的,一次唤醒一个进程。如果不是互斥等待的,一次唤醒所有进程。
互斥等待的经典例子:accept。因为我们很明确知道,对一个listen fd的accept,肯定是一次只有一个进程可以处理。那么,我们在listen fd上的等待队列,就毫无疑问可以设置为“互斥等待”。所以,现今版本的linux内核,解决了accept的惊群问题。
但是像epoll_wait的惊群问题,就无法从等待队列的互斥等待来解决。首先,epoll fd上也有一个等待队列,代表epoll fd所监听的其他若干文件描述符(资源)就绪时,唤醒等待队列上的资源。因为我们无法确定,这些资源是不是都是互斥访问的,还是都不是。所以,只好唤醒所有进程。更多的惊群问题,可以查阅相关资料。
总结
等待队列是内核实现进程阻塞调用的机制。我们从概念上,浅谈了等待队列的用途,以及等待队列会出现的惊群问题。有说得不清楚的地方,还请见谅。