[科普中国]-队列机制

定义

队列是一种数据结构，它具有先进先出的特点，是一种应用很广泛的结构。在计算机或计算机之间，为了提高计算机或计算机之间的工作效率，我们经常采用队列机制。队列机制简单来说是基于队列，利用某种方案来提高工作效率。例如操作系统中作业、进程和线程基于队列机制调度。

分类关于队列机制的分类有很多选择，这里主要从队列机制作用来分类，分为以下两类：

工作队列机制内核中提供了许多机制来提供延迟执行，如中断的下半部处理可延迟中断上下文中的部分工作；定时器可指定延迟一定时间后执行某工作；工作队列则允许在进程上下文环境下延迟执行等。除此之外，内核中还曾短暂出现过慢工作机制 (slow work mechanism)，还有异步函数调用 (asynchronous function calls) 以及各种私有实现的线程池等。在上面列出的如此多的内核基础组件中，使用最多则是工作队列。

下面是一些有关工作队列的短语

workqueues：所有工作项被 ( 需要被执行的工作 ) 排列于该队列，因此称作工作队列 (workqueues) 。

worker thread：工作者线程 (workerthread) 是一个用于执行工作队列中各个工作项的内核线程，当工作队列中没有工作项时，该线程将变为 idle 状态。

single threaded(ST):工作者线程的表现形式之一，在系统范围内，只有一个工作者线程为工作队列服务。

multi threaded(MT)：工作者线程的表现形式之一，在多 CPU 系统上每个 CPU 上都有一个工作者线程为工作队列服务。1

工作队列机制的准则如下：

面向用户的准则

(1) 周转时间短。通常把周转时间的长短作为评价批处理系统的性能、选择作业调度方式与算法的重要准则之一。所谓周转时间，是指从作业被提交给系统开始，到作业完成为止的这段时间间隔(称为作业周转时间)。它包括四部分时间：作业在外存后备队列上等待(作业)调度的时间，进程在就绪队列上等待进程调度的时间，进程在CPU 上执行的时间，以及进程等待I/O 操作完成的时间。其中的后三项在一个作业的整个处理过程中可能会发生多次。

(2) 响应时间快。常把响应时间的长短用来评价分时系统的性能，这是选择分时系统中进程调度算法的重要准则之一。所谓响应时间，是从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间，或者说，直到屏幕上显示出结果为止的一段时间间隔。它包括三部分时间：从键盘输入的请求信息传送到处理机的时间，处理机对请求信息进行处理的时间，以及将所形成的响应信息回送到终端显示器的时间。

(3) 截止时间的保证。这是评价实时系统性能的重要指标，因而是选择实时调度算法的重要准则。所谓截止时间，是指某任务必须开始执行的最迟时间，或必须完成的最迟时间。对于严格的实时系统，其调度方式和调度算法必须能保证这一点，否则将可能造成难以预料的后果。

(4) 优先权准则。在批处理、分时和实时系统中选择调度算法时，都可遵循优先权准则，以便让某些紧急的作业能得到及时处理。在要求较严格的场合，往往还须选择抢占式调度方式，才能保证紧急作业得到及时处理。

面向系统的准则

(1) 系统吞吐量高。这是用于评价批处理系统性能的另一个重要指标，因而是选择批处理作业调度的重要准则。由于吞吐量是指在单位时间内系统所完成的作业数，因而它与批处理作业的平均长度具有密切关系。对于大型作业，一般吞吐量约为每小时一道作业；对于中、小型作业，其吞吐量则可能达到数十道作业之多。作业调度的方式和算法对吞吐量的大小也将产生较大影响。事实上，对于同一批作业，若采用了较好的调度方式和算法，则可显著地提高系统的吞吐量。

(2) 处理机利用率好。对于大、中型多用户系统，由于CPU 价格十分昂贵，致使处理机的利用率成为衡量系统性能的十分重要的指标；而调度方式和算法对处理机的利用率起着十分重要的作用。在实际系统中，CPU的利用率一般在40%(系统负荷较轻)到90%之间。在大、中型系统中，在选择调度方式和算法时，应考虑到这一准则。但对于单用户微机或某些实时系统，则此准则就不那么重要了。

(3) 各类资源的平衡利用。在大、中型系统中，不仅要使处理机的利用率高，而且还应能有效地利用其它各类资源，如内存、外存和I/O 设备等。选择适当的调度方式和算法可以保持系统中各类资源都处于忙碌状态。但对于微型机和某些实时系统而言，该准则并不重要。2

消息队列机制消息队列机制是在多个不同的应用之间实现相互通信的一种异步传输模式，相互通信的应用可以分布于同一台机器上，也可以分布于相连的网络空间中的任一位置。

常用的通知机制中比较典型的有以下几种：

1. signal

这种机制下，我们向被通知进程发送一个特殊的signal（比如SIGUSR1），这样正在睡眠的读进程就会被信号中断，然后醒来。2

该方法的优点是：读进程不需要监听一个额外的eventfd，适合一些不方便使用eventfd的场景；另外，用户可以选择是使用实时信号（SIGRTMIN+1），还是使用非实时信号（SIGUSR1）。

该方法的缺点是：通知不实时。因为信号的检查只有在中断返回的时候才会进行，这个时间跟操作系统的HZ、jiffies有关。

2. socket

这种机制下，写进程往socket（domain socket）写一个字符，然后读进程通过epoll得到数据到达的通知。

3. fifo

这种机制跟socket类似，写进程往fifo中写一个字符，然后读进程通过epoll得到数据到达的通知。

4. pipe

跟2、3差不多。

5. eventfd/signalfd

跟前面差不多，不过是内核帮我们事先fifo、signal通知，只有比较新的内核版本才支持。这种方式存在的问题是需要在不同进程间传递句柄，非fork方式实现比较复杂。

上面这几种方式的共性是都需要陷入内核，被通知进程只有在内核态才能接收通知，对于处理性能要求高的场景，应该少用通知。所以，当然就看业务场景发送通知的开销是不是很大了。如果请求量很大，读进程一直忙于处理，不会频繁触发通知，那就很合适了。

实现

受控并发工作队列的实现

全局每CPU工作队列(gcwq) 如果计算机有N个CPU，则内核创建N + 1个gcwq，其结构如下所示：

structglobal_cwq{spinlock_tlock;unsignedintcpu;structlist_headworklist;intnr_workers;intnr_idle;structlist_headidle_list;structhlist_headbusy_hash[BUSY_WORKER_HASH_SIZE];structtimer_listidle_timer;structtimer_listmayday_timer;...}____cacheline_aligned_in_smp;

N个gcwq分别与N个CPU一一绑定，管理相关CPU上的工作者线程和中断产生的工作；第N + 1个gcwq称为unbound_global_cwq，其中的工作者线程未与特定的CPU绑定，WQ_UNBOUND为标志说明。虽然gcwq也称作“工作队列”，但是与用户创建的工作队列不同，它是内部管理结构，对用户不可见。gcwq中的cpu字段表示与其关联的CPU编号，worklist双向链表存储由中断提交到该CPU上的工作，lock字段为保护gcwq结构体的自旋锁。每个gcwq都维护管理一个工作者线程池，其中的工作者线程有idle（空闲）和busy（工作）两种状态；idle_list双向链表中管理处于idle状态的工作者线程，nr_idle记录其数量；为了快速检索，使用busy_hash哈希链表管理处于busy状态的工作者线程。这些线程负责处理worklist链表中工作。nr_workers记录工作者线程池中线程的数量。

工作队列机制的运行

当中断发生时，内核调用queue_work函数将工作序列提交到gcwq。若相关的线程池中没有线程，则内核创建工作者线程；否则唤醒一个工作者线程工作者线程调用worker_thread函数，该函数在执行中使用gcwq中的自旋锁进行保护，并完成以下动作：

1）线程从idle状态变为busy状态。

2）对所属的gcwq的线程池进行检查管理。设线程A是当前正在执行的线程，若worklist上有多个待处理的工作，则A检查线程池中是否还有处于idle状态的线程，如果存在，设选中的为线程B；否则A将创建并唤醒一个新线程B，B在创建后进入idle状态。因此在处理工作时，线程池中将保持至少一个处于idle状态的线程待命，以便迅速响应和处理worklist上的后继工作。

3）线程A从gcwq的worklist链表中依次取出未处理的工作进行处理。当处理完worklist中所有的工作后，将再一次对线程池进行检查管理，然后进入idle状态并休眠。

4）一旦线程A阻塞且worklist上还有待处理的工作，则线程B开始运行，它调用worker_thread函数重复以上过程。当工作者线程处理完全部工作后将对线程池进行一次检查管理。此时如果gcwq中空闲的工作者线程过多，其判断条件是nr_idle > 2且(nr_idle - 2) * 4 >= nr_idle，则gcwq将销毁idle状态持续时间超过5分钟的工作者线程。每个gcwq的线程池最终将维护两个处于idle状态的工作者线程。

特点

1）由内核根据处理需求，控制工作者线程的创建和销毁，避免创建过多的内核线程。在工作队列空闲时，新机制中的线程数大致为( N + 1 ) * 2，工作队列数量与内核线程数基本无关（除非工作队列设置WQ_RESCUER标志）。这个改进大大减少内核资源的消耗。

2）同一CPU上一个工作队列中的工作可以并发的处理。这种并发处理方式相比旧机制的严格串行，提高了处理效率。在每个CPU上，一个工作队列中可并发处理的工作数目是有限制的（见1.4节max_active参数），当达到限制时，将不再唤醒新的工作者线程。

3）创建工作队列时可以指定工作队列的属性。用户可以根据工作性质的不同创建不同的工作队列，如高优先级的（WQ_HIGHPRI）、未绑定的(WQ_UNBOUND)、不可重入的(WQ_NON_REENTRANT)、带救援者线程的（WQ_RESCUER）。gcwq的worklist链表中的工作分为高优先级的工作和普通优先级的工作两类，高优先级的工作排在链表头部，普通优先级的工作排在链表尾部，同一类别的工作之间按照提交的顺序排列。而在旧工作队列机制中则没有这些属性，工作按照提交的顺序被执行。

4）新工作队列机制提供4个预定义工作队列，方便用户使用工作队列。这四个预定义的工作队列分别为events、events_long、events_nrt、events_unbound。其中events 是普通工作队列，要求其中的工作执行时间尽量短；需要长时间处理的工作可以提交到events_long队列中；events_nrt是不可重入工作队列，其中的工作将不会在多个CPU上并发执行；events_unbound队列就是设置了WQ_UNBOUND标志的队列，只要处理的工作数量未达到限制，其中的工作就可以立即被处理。用户可以根据需要使用这4个预定义工作队列，当然也可以自己创建工作队列。3