单核 CPU 可抢占优先级任务调度算法解析

单核 CPU 任务调度

题目描述

现有一个 CPU 和一些任务需要处理，已提前获知每个任务的任务 ID、优先级、所需执行时间和到达时间。 CPU 同时只能运行一个任务，请编写一个任务调度程序，采用'可抢占优先权调度'调度算法进行任务调度，规则如下：

• 如果一个任务到来时，CPU 是空闲的，则 CPU 可以运行该任务直到任务执行完毕。但是如果运行中有一个更高优先级的任务到来，则 CPU 必须暂停当前任务去运行这个优先级更高的任务；
• 如果一个任务到来时，CPU 正在运行一个比他优先级更高的任务时，新到达的任务必须等待；
• 当 CPU 空闲时，如果还有任务在等待，CPU 会从这些任务中选择一个优先级最高的任务执行，相同优先级的任务选择到达时间最早的任务。

输入描述

输入有若干行，每一行有四个数字（均小于 10^8）,分别为任务 ID，任务优先级，执行时间和到达时间。

每个任务的任务 ID 不同，优先级数字越大优先级越高，并且相同优先级的任务不会同时到达。

输入的任务已按照到达时间从小到大排序，并且保证在任何时间，处于等待的任务不超过 10000 个。

输出描述

按照任务执行结束的顺序，输出每个任务的任务 ID 和对应的结束时间。

示例 1

输入

1 3 5 1 2 1 5 10 3 2 7 12 4 3 2 20 5 4 9 21 6 4 2 22 

输出

1 6 3 19 5 30 6 32 4 33 2 35 

解题思路

问题本质

这是一个经典的"可抢占优先级调度"(Preemptive Priority Scheduling) 问题，模拟 CPU 如何根据优先级和到达时间处理多个任务。

核心思路

实现一个事件驱动的模拟器，通过优先队列维护待执行任务，并根据调度规则执行任务。主要步骤包括：

1. 数据结构设计：
   • 任务类 Task：存储 ID、优先级、执行时间和到达时间信息
   • 优先队列：维护待执行的任务，按优先级排序（优先级高的在前，同优先级按到达时间排）
2. 关键算法：
   • 事件驱动：模拟时间的推进，基于任务完成和新任务到达两种事件
   • 抢占式调度：当高优先级任务到达时中断当前任务
3. 模拟流程：
   • 将已到达的任务加入等待队列
   • 根据优先规则选择或更新当前执行任务
   • 计算下一个事件点并推进时间

详细步骤