vllm中的llm_engine主要由两个模块构成，Scheduler和Executor，其中Executor负责管理并行推理时的多个设备、模型的推理计算和KV Cache的显存分配和管理，而Scheduler负责请求的调度。接下来，我将详细介绍vllm的Scheduler模块和其调度策略。
前置知识
llm是自回归的模型，在一个请求的完整处理过程中需要进行多次推理，每次推理由llm_engine.py中LLMEngine类的step函数完成，step可以是一次prefill，也可以是一次decode，总之step函数执行一次代表模型进行了一次推理。
在vllm中，一个请求，也就是Sequence会被包装成SequenceGroup，这个设计是为了支持Parellel Sampling和Beam Search等复杂的decoding策略。在这种策略下，一个请求的prompt会产生多个ouput，prompt与每个output都构成一个seq，显而易见这些seq共享同一个prompt，共享了相同的前缀KV Cache，为了提高显存利用效率、方便管理共享prompt的多个seq，SequenceGroup的设计就是必要的。
Scheduler
调度器的结构如下图所示，其中包含三个存放SeqGroup的队列，分别是waiting、running和sweped，请求的调度本质上就是请求在三个队列间的增加、移动或删除。
- waiting 队列：存放尚未进行prefill阶段的SeqGroup，此时，队列中的SeqGroup只有一个seq（prompt）
- running队列：以每次调度为分界点，调度前存放的是上一次被送去做推理的SeqGroup，调度后会对running队列进行更新，存放的是即将被送去做推理的SeqGroup
- swapped队列：存放在之前的调度中被抢占的SeqGroup，此时每个SeqGroup中的seq数量至少为1
调度策略
- 对swapped队列的检查是调度程序的入口，如果swapped队列为空，1将优先调度waiting中的请求，如果非空，2将调度running和3swapped中的请求。
- 在调度waiting队列前，满足waiting非空且_passed_delay为True时，1-1进入waiting列队，否则，1-2将直接处理running队列。
- 进入waiting队列，取出到达时间最早的seq group，使用can allocate函数检查是否有足够空间来调度，可能有三种状态：
- 1-1-1返回Nerver，意味着prompt太长，GPU上所有的KV Cache空间都无法容纳，标记为FINISHED，直接跳过，回到1-1。
- 1-1-2返回Later，意味着本次调度已达到上限，结束对waiting的调度，进入对1-1-4scheduler output和preempted非空的判断。
- 1-1-3返回OK，意味着空间足够容纳该seqgroup的prefill需求，为其分配物理块，从waiting中移动到running中，同时添加到本次调度的输出中，然后回到1-1继续处理waiting中的下一个seqgroup。
- 1-1-4判断scheduler output或者ignored seq group是否非空，如果非空，结束waiting调度，返回调度结果；如果为空，进入2running调度。
- 在调度running前，初始化new running和preempted用来存放本次送去推理的seqgroup和被抢占的seqgroup，2判断running是否非空，如果非空，2-1弹出running中最早到达的seqgroup，判断是否可以分配空间，如果可以，2-1-1，为其分配物理块，从running中弹出，加入new running，回到2继续判断，如果不可以，2-1-2抢占running中最后一个seqgroup，将其从running中移动到preempted中。
- 如果running为空，2-2将new running赋值给running，判断preempted是否为空，若非空，输出调度结果，若为空，进入3调度swapped中的请求。
- 进入3，首先判断swapped是否为空，若非空，弹出到达时间最早的seqgroup，并判断空间是否足够换入gpu，若足够，则换入并分配物理块，从swapped移动到running，回到3继续判断下一个seqgroup。
- 若swapped为空，或者空间不足以换入，或者超过了token、seq总数，则直接输出调度结果。
整体的调度流程图如下(原图见附件)：
参考：
图解大模型计算加速系列：vLLM源码解析2，调度器策略(Scheduler) – 知乎
附件：
