由于配置限制，本题只允许使用 C++ 进行提交，且评分方式进行修改。此外，本题工程文件编译时间较长，请耐心等待，且不要滥用评测资源~

时间限制： 1.0 秒

空间限制： 100 MB

题目背景

调度器是操作系统的一部分，它决定计算机何时运行什么任务。通常，调度器能够暂停一个运行中的任务，将它放回到等待队列当中，并运行一个新任务，这一机制称为抢占（preemption）。抢占的实现往往需要通过硬件时钟（timer）定时发起中断（interrupt）信号，告知调度器一定时间周期已经过去，并由调度器决定下一个运行的任务。

调度器可能会针对不同的目标设计，例如：吞吐率最大化、响应时间最小化、延迟最小化或公平性最大化。在实践中，这些目标通常存在冲突；因此，调度器会实现一个权衡利弊的折中方案，根据用户的需求和目的，侧重以上一个或多个方面。

在实时（realtime）环境，例如工业上用于自动控制（如机器人）的嵌入式系统，调度器必须保证进程的调度不能超过最后期限——这是保持系统稳定运行的关键因素。

题目描述

要求

本题要求设计一个面向单核的调度策略，并实现调度器对应接口。本题要求调度策略尽可能达到实时系统的要求（即所谓“准实时”调度），并根据接口实现的正确性与任务及时完成率进行评分。本题根据选手全场最优成绩评分，选手可通过实时提交评估调度策略性能。

任务假设

• 任务包含完成截止时间（deadline），调度器应尽可能在截止时间前完成任务。
• 任务分为高优先级与低优先级，调度器应倾向优先完成高优先级任务。
• 每个任务包括一段以上 CPU 计算与零或多段 IO 操作，分别使用计算机的 CPU 资源和 IO 资源。调度器可以执行任务 $T_{cpu}$ 的 CPU 计算时，并行执行任务 $T_{io}$ 的 IO 操作。
• 在一个任务使用 IO 资源时，不允许其同时使用 CPU 资源。
• 每个任务都以 CPU 计算开始与结束。

调度规则

使用系统资源： 任何时刻，最多只有一个任务 $T_{cpu}$ 使用系统 CPU 资源进行计算，最多只有一个任务 $T_{io}$ 使用系统 IO 资源进行操作。系统 CPU 资源可以在任意时刻被调度器切换并执行新任务的 CPU 计算；系统 IO 资源必须完成当前 IO 操作后，才能执行新任务的 IO 操作。

调度新任务： 调度器在新任务到达、任务结束、任务请求 IO 操作、任务结束 IO 操作、时钟中断到来时被唤醒并收到通知，并调用选手实现的策略接口决定接下来被调度的任务。策略将输出任务 $T'_{cpu}$ 以抢占当前 CPU 资源。$T'_{cpu}$ 可以等于 $T_{cpu}$，即继续将 CPU 资源分配给旧任务；$T'_{cpu}$ 可以为空，即将 CPU 资源空置。当不存在能够进行 CPU 计算的任务时，空置 CPU 资源是合理的。当 IO 资源空闲时，策略可输出任务 $T'_{io}$ 以使 IO 资源服务新的任务。注意，因为 IO 资源无法实时切换，当旧任务 $T_{io}$ 未完成时，不能开始新的 IO 操作。

子任务

本题共 16 个测试点：

测试点编号	任务特征相似度	截止时间早晚程度	优先级分布	任务出现分布
$1\sim 3$	相似	宽裕	随机	随机
$4\sim 6$	差异较大
$7\sim 8$	特征分布随时间变化
$9\sim 10$	差异较大	紧张
$11\sim 12$		宽裕	截止时间紧张的任务倾向于有高优先级
$13\sim 14$			随机	在特定时刻会更频繁出现
$15\sim 16$	特征分布随时间变化	紧张	截止时间紧张的任务倾向于有高优先级

答题接口

本题要求选手实现调度策略 policy 接口，此函数将在上述描述的事件发生时被调用，此函数的输出将决定调度器接下来的操作。此处将描述该函数输入、输出参数语义，编程语言相关的细节将在后文具体描述。

policy 函数接收三个参数：

第一个参数为事件列表，包含此时刻同时发生的所有事件信息，绝大部分时候此列表长度为 $1$。事件包括下列类型：

• 时钟中断到来（Timer）；
• 新任务到达（TaskArrival），表示一个用户发起了新任务；
• 任务请求 IO 操作（IoRequest），表示一个任务需要进行 IO 操作；
• 任务结束 IO 操作（IoEnd），表示一个任务完成了一次 IO 操作，并需要使用 CPU 资源；
• 任务完成（TaskFinish），表示一个任务完成了它所有的 CPU 和 IO 操作。

除事件类型、时间外，与任务相关的事件信息还有相应的任务信息，包括任务 ID、到达时间、截止时间与优先级。

第二、三个参数为此时刻 CPU 与 IO 分别服务的任务的任务 ID。注意，当调度策略输出非法操作指令以及任务当前 CPU、IO 操作完成时，这两个参数可能会与上次 policy 指定的任务 ID 不同。

policy 函数输出调度策略的操作指令，即 CPU、IO 资源接下来分别服务任务的任务 ID。

根据调度规则，在 IO 资源未空闲时指定其他任务 ID 是非法的；在一个任务占用 IO 资源时，试图让其占用 CPU 资源也是非法的。进行任何非法操作会导致你在该测试点获得 0 分。

任务 ID 值的说明

所有任务的任务 ID 大于 0。policy 函数输入参数中为0的任务 ID 代表对应资源空闲；输出操作指令中为0的 CPU 资源任务 ID 代表不使用 CPU 资源（即到下一个事件来临之前，CPU 将处于空闲状态），为0的 IO 资源任务 ID 代表不进行 IO 资源调度（即到下一个事件来临之前，IO 将保持当前状态）。

C++接口

C++ 工程文件与下发样例见 down.zip。

C++ 接口定义以下结构、函数。

struct Event {
  enum class Type {
      kTimer, kTaskArrival, kTaskFinish, kIoRequest, kIoEnd
  };
  struct Task {
    enum class Priority { kHigh, kLow };

    int arrivalTime;
    int deadline;
    Priority priority;
    int taskId;
  };

  Type type;
  int time;
  Task task;
};

struct Action {
  int cpuTask, ioTask;
};

Action policy(const std::vector<Event>& events, int currentCpuTask,
              int currentIoTask);

请在 policy.cc 中实现 policy 函数。其他辅助性结构、函数可定义、实现在同一文件中。本文件将使用 C++20 语言标准进行编译。

将下发文件代码放在同一个文件夹中，在 Linux 系统中输入以下命令行即可编译：

g++ sim.cc task.cc event.cc policy_wrapper.cc policy.cc -Wall -std=c++20 -o foo -lm -O2 -I/include

下发文件中的时钟周期文件为 sim_config_sample.json，样例为 trace-1.json 至 trace-16.json。

在 Linux 下执行：

./foo sim_config_sample.json trace-1.json

在 Windows 下执行：

.\foo.exe sim_config_sample.json trace-1.json

即可查看对应样例的本地评测结果。16 个白盒样例与 16 个黑盒评测数据在数据生成原理上一致。

评分方式

正确性

考虑以下 FIFO 调度策略：维护任务队列 Q，当任务到达时将任务加入 Q，当且仅当上一任务完成时推出队首任务并开始执行。 令 FIFO 调度下所有任务完成所需时间为 $t_{FIFO}$，当选手实现策略完成所有任务用时 $t$ 小于等于 $t_{FIFO}$ 时，认为选手策略实现正确。

性能指标：综合完成率

综合完成率 $r$ 为高、低优先级任务在截止时间内及时完成率的加权平均。假设高优先级任务完成率为 $r_{hi}$，低优先级任务完成率为 $r_{lo}$，则综合完成率 $r$ 满足：

$$r=70\%\times r_{hi} + 30\%\times r_{lo}$$

总分

本评测链接的计算方式相较于实际比赛有所调整。

每个测试点策略实现错误得 $0$ 分，实现正确则获得 $100$ 分，在此基础上加上 $100\times r$，即每个测试点会获得 $[100,200]$ 之间的分数，并以此计算分数加和。

在评测结果中，我们会公布你的 $r_{hi},r_{lo}$ 以及实际得分。

当且仅当所有测试点的策略实现均正确时，获得 Accepted 的评测结果。

提示

本题通过模拟方式评估选手调度策略性能，请选手不要以现实世界的时间单位来认知事件的时间（time）属性。

模拟过程中的时钟中断间隔长度固定，且大于 1。