1 基本概念
1.1 定义与作用
就绪队列是操作系统调度机制中的核心结构，用于保存那些已经满足运行条件、只差获得 CPU 的进程或线程。它并不表示这些实体正在执行，而是表示它们随时可以被调度器选中进入运行态。
就绪队列的主要作用，是为调度器提供一个统一的候选集合。调度器通过查找或比较其中的元素，决定下一次由谁占用处理器资源。由于这一过程直接影响任务切换速度、系统吞吐量以及交互响应，就绪队列在进程管理中具有基础地位。
1.2 就绪态与其他状态的区别
就绪态指的是执行实体已经拥有所需资源中的大部分条件，但暂时还没有获得 CPU 时间。它与运行态、阻塞态相互区分，共同构成进程状态变化的主要环节。
1.2.1 运行态
运行态表示进程或线程正在 CPU 上实际执行。与就绪态相比，运行态的区别在于“已经被选中”。二者之间的转换通常由调度器控制，前者代表占用处理器，后者代表等待处理器。
1.2.2 阻塞态
阻塞态表示执行实体因等待某种事件而暂时不能运行，例如等待 I/O 完成、等待锁释放或等待信号到达。阻塞态与就绪态的关键差别在于：前者不仅没有 CPU，还缺少继续执行所需的条件；后者则仅仅是等待调度机会。
1.3 就绪队列在调度系统中的位置
在调度系统中，就绪队列位于“可运行集合”的中心位置。新建进程在满足条件后会进入该队列，等待调度器选择；运行中的进程在被抢占或时间片结束后，也可能重新回到队列中；而从阻塞中恢复的进程，通常同样会被放入其中。
因此，就绪队列既是状态转换的汇聚点，也是调度策略落地的关键入口。不同系统对它的组织方式不同，但其核心功能始终一致：管理待运行实体，并为 CPU 分配提供依据。
2 数据结构与实现
2.1 线性链表实现
早期或结构较简单的系统中，就绪队列常以链表方式实现。新到达的进程可按顺序插入链表尾部，调度时从表头取出目标对象。
这种实现方式直观、便于维护，适合规则较简单的调度场景。不过，当系统负载较高、调度规则更复杂时，链表在查找、排序和优先级比较方面的效率会受到限制。
2.2 优先级队列实现
优先级队列按照某种优先级规则组织就绪实体。调度器通常从最高优先级位置取出下一执行对象，因而能够更直接地支持优先级调度。
这类结构适合需要区分任务紧急程度的环境。它的优点是选择效率较高，缺点则在于维护成本可能上升，特别是当优先级频繁变化时，队列更新会变得更复杂。
2.3 多级队列实现
多级队列将就绪实体划分到多个独立队列中，每个队列可以对应不同类别、不同优先级或不同调度规则。调度器先在高层队列中查找，必要时再向低层队列推进。
这种方式的组织性较强，便于对不同类型任务采取不同策略。例如，交互任务与后台任务可分别管理，从而改善系统整体体验。不过，多级队列对分类标准依赖较大，若划分不合理，可能导致资源分配不均。
2.4 多级反馈队列实现
多级反馈队列是一种更具动态性的组织方式。它通常包含多个层次的队列，并允许进程根据行为特征在不同层级之间流动，以便更灵活地兼顾响应性与公平性。
2.4.1 队列分层原则
多级反馈队列的分层，通常依据任务的运行历史、占用 CPU 的时长或响应需求来设置。短时间内能完成的任务更容易留在较高优先级队列，而持续占用处理器较久的任务则会逐步进入较低层级。
这种设计的目的，是让系统优先照顾更“轻量”的任务，从而提升交互体验，并避免长任务长期垄断处理器。
2.4.2 动态提升与降级机制
动态提升与降级机制是多级反馈队列的重要特点。若某个任务长时间得不到运行机会，系统可能提升其优先级，以减少等待过久的问题；若某任务持续消耗 CPU，则可能被降级到更低层级，以平衡其他任务的执行机会。
这种动态调整使得队列结构不再完全依赖静态分类，而是能随着任务行为变化而修正调度顺序。
2.5 内核中的典型组织方式
在实际内核中，就绪队列通常并非单一“列表”概念，而是结合了多种结构。常见做法包括按 CPU 分离队列、按优先级分组、按任务类型组织，以及为实时任务设置独立通道等。
为了提高效率，内核往往会把队列管理与进程控制块、负载统计和调度器状态紧密结合，使插入、删除与选择操作尽可能高效。不同操作系统实现各异，但总体目标都是降低调度成本并提高运行稳定性。
3 调度过程中的作用
3.1 进程进入就绪队列的时机
进程并不是从创建开始就直接运行，通常需要在满足条件后才进入就绪队列。这个时机取决于其状态变化和系统资源准备情况。
3.1.1 创建完成后
当进程创建完成并完成必要初始化后，如果尚未获得 CPU，便会进入就绪队列等待调度。此时它已经具备执行条件，只是还没有被分配时间。
3.1.2 从阻塞态唤醒后
当等待的事件完成后，例如 I/O 返回或同步条件满足，原本处于阻塞态的进程会被唤醒，并重新放入就绪队列。随后它将再次参与调度竞争。
3.1.3 时间片用尽被抢占后
在时间片轮转或抢占式调度中，运行中的进程若用尽分配到的 CPU 时间，可能被暂停并重新放回就绪队列。这样可以让其他任务获得执行机会。
3.2 进程从就绪队列被选中的过程
调度器会根据当前策略，从就绪队列中筛选下一个可运行对象。这个过程可能只需取出队首元素，也可能涉及优先级比较、权重计算或多层队列间的选择。
选中的进程会从“等待调度”转入“正在运行”，并由 CPU 开始执行。若系统同时管理多个处理器，还可能结合负载情况，将任务分配到不同核心上。
3.3 上下文切换与队列更新
当进程被切换出去时，系统需要保存其运行现场，包括寄存器、程序计数器和相关状态信息。随后，若该进程仍可继续执行，通常会重新加入就绪队列或进入其他适当状态。
上下文切换期间，队列也会同步更新，以反映当前可运行集合的变化。由于这一过程涉及保存和恢复状态，因此会带来额外开销，队列设计越复杂，维护成本往往越高。
3.4 抢占式调度与非抢占式调度中的差异
在抢占式调度中，系统可以在任意合适时刻打断当前运行的进程，并将其重新放回就绪队列。这样有利于提高响应速度，尤其适合交互场景。
而在非抢占式调度中，进程一旦获得 CPU，通常会一直运行到主动让出处理器或进入阻塞状态。此时就绪队列仍然存在，但其作用更多体现在等待下一次自然调度，而不是随时被抢占。
4 调度策略相关性
4.1 先来先服务调度
先来先服务调度通常按进入就绪队列的顺序分配 CPU。越早到达的任务越早执行，规则简单，易于理解。
这种方式实现成本低，但对短任务不够友好。如果较长任务排在前面，后续任务可能等待较久，导致平均响应时间变差。
4.2 短作业优先调度
短作业优先调度倾向于先执行预计运行时间较短的任务。若就绪队列能按照任务长度或近似指标排序，就可以较快选出短任务。
这种策略往往能降低平均等待时间，但需要对任务长度做出估计。若短任务持续插入，也可能让长任务等待较久。
4.3 时间片轮转调度
时间片轮转调度常与就绪队列紧密配合。每个任务轮流获得固定时长的 CPU 使用权，时间片结束后重新进入队列末尾，等待下一轮。
这种方式兼顾了公平性和交互响应，适合多任务并发环境。其效果很大程度上取决于时间片大小：过短会增加切换频率，过长则会降低响应速度。
4.4 优先级调度
优先级调度根据任务的重要程度决定执行顺序。就绪队列通常会按照优先级组织，以便调度器快速取出更重要的任务。
4.4.1 静态优先级
静态优先级在任务创建后基本固定，除非系统手动调整。它的优点是规则清晰，适合结构稳定的调度场景；缺点是对运行中的行为变化反应不足。
4.4.2 动态优先级
动态优先级会根据任务历史、等待时间或 CPU 占用情况不断变化。这样做可以让长期等待的任务获得更多机会，也能抑制过度占用处理器的进程。
4.5 公平性与响应时间权衡
就绪队列的组织方式往往需要在公平性与响应时间之间做平衡。若过于强调公平，所有任务轮流等待，系统可能显得“均匀”但不够灵敏；若过于强调响应，则某些任务会被长期压后，影响整体一致性。
因此，不同调度系统会根据目标不同，选择不同的队列结构和取出策略。交互式系统更重视响应，批处理系统则更关注吞吐和完成率。
5 性能与设计考量
5.1 队列长度与系统负载
就绪队列长度通常能够反映系统当前压力。队列越长，说明等待 CPU 的任务越多，调度竞争也越激烈。此时平均等待时间往往会上升，系统响应可能变慢。
不过，队列长度并不总能单独说明问题，还需要结合任务性质、CPU 数量与调度策略综合判断。
5.2 调度开销
调度开销包括队列插入、删除、查找以及上下文切换等成本。若队列维护逻辑过于复杂，系统可能把更多资源消耗在“挑选任务”本身，而不是实际执行任务。
因此，优秀的实现通常会在结构复杂度与运行效率之间做折中，尽量减少不必要的遍历和排序操作。
5.3 饥饿问题与解决方法
饥饿问题指某些任务长期得不到 CPU 机会，即使它们一直处于就绪状态。常见原因包括优先级过低、长时间被新任务插队，或者调度规则偏向某一类任务。
解决方法通常包括老化机制、动态优先级调整、时间片限制以及多级反馈策略等。其核心思想是避免少数任务被无限期搁置。
5.4 线程数增长对队列管理的影响
当线程数量迅速增加时，就绪队列会承受更大的维护压力。更多实体意味着更频繁的状态变化，也意味着更高的插入、删除和选择成本。
在这类情况下，系统通常需要更高效的索引方式、分片管理或按 CPU 拆分队列，以降低单点竞争并减少锁冲突。
5.5 实时系统中的就绪队列要求
实时系统对就绪队列的要求更严格，重点不只是“能否运行”，而是“能否在限定时间内运行”。因此，队列结构必须支持快速、可预测的选择过程。
这类系统往往强调确定性和时限保障，调度策略需要尽量减少不可预期的延迟。就绪队列在此不仅是管理工具，更是满足时序约束的关键组件。
6 相关概念与扩展
6.1 进程控制块
进程控制块是操作系统用于记录进程信息的核心数据单元，通常包含状态、优先级、寄存器内容、内存信息等。就绪队列中的每个进程，往往都会通过其控制块进行标识和管理。
6.2 运行队列
运行队列常与就绪队列密切相关，有些系统中二者几乎可以视为同一概念的不同称呼。广义上，它指的是那些可供 CPU 选择的任务集合，强调的是调度视角。
6.3 等待队列
等待队列用于保存因事件未完成而无法继续执行的进程或线程。与就绪队列不同，它面向的是“缺少条件”的任务，而不是“等待 CPU”的任务。
6.4 CPU 亲和性
CPU 亲和性指任务倾向于在特定处理器上继续运行。若调度器考虑亲和性，就绪队列的管理可能会按核心进行分组，以减少缓存失效并提高运行效率。
6.5 负载均衡
负载均衡是多处理器系统中的重要问题，目标是让各个 CPU 承担相对均匀的工作量。就绪队列在其中扮演分配源的角色，任务可能在不同核心的队列之间迁移，以避免某些处理器过载而另一些空闲。
6.6 调度延迟
调度延迟是指任务进入就绪状态到真正开始运行之间的等待时间。它是衡量调度质量的重要指标之一，过长的延迟会降低交互体验，也可能影响实时任务的时限满足情况。