Skip to content

1448: CPU 任务调度问题(20年期末考T3)

题目

题目描述

时间限制:1000ms,空间限制:256MB

请一定认真阅读题目最后的注意事项!

在本题中,你只需要实现 src.hppTODO 标识符后面的部分,其余代码文件(包括 task.hppmain.cpp)请不要改动。

在你写代码的时候,你可能同时打开了 Clion、QQ、浏览器等许多应用,可是你的计算机可能只有一个 CPU,这时候就需要 CPU 进行进程调度来解决每个进程所发送的任务请求。一般来说,CPU 会维护一个任务列表包含需要完成的任务,并且在每个时间段都会选择下面两项中的一项:

  • 做一个任务列表中需要完成的任务;
  • 空闲(此时当前任务列表中的所有任务都已完成)。

所谓 CPU 任务调度,就是安排 CPU 在每个时间段内做哪一个任务。也就是说,你的计算机可能前一个单位时间在执行 Clion 的编译任务,后一个单位时间在执行 QQ 的实时聊天任务。在计算机中,由于时间段非常小,所以你通常感觉不到这种调度的存在。

言归正传,我们提供如下三种 CPU 任务调度问题的方法,而你需要实现这三个方法。

FCFS 方法:CPU 在下个时间段(时间单位)执行先加入任务列表的任务。

SRTF 方法:CPU 在下个时间段(时间单位)执行任务列表中剩余时间最少的任务;如果有多个任务剩余时间相同,则执行先加入任务列表的那个。

Priority 方法:CPU 在下个时间段(时间单位)内执行优先级最高的任务;如果有多个任务优先级相同,则执行先加入任务列表的那个。

题目解释

具体来说,我们在 task.hpp 中提供了一个 Task 类来描述任务(在下文代码中 uint 代表 unsigned int):

```c++

ifndef SJTU_CPP_FINAL_TASK_HPP

define SJTU_CPP_FINAL_TASK_HPP

typedef unsigned int uint;

namespace sjtu { // Description for each task: // task_id: uint, unique for each task; // priority: uint; // time: uint, (remaining) time of the task. struct Task { uint task_id; uint priority; uint time;

    explicit Task(uint _task_id = 0, uint _priority = 0, uint _time = 0) {
        task_id = _task_id;
        priority = _priority;
        time = _time;
    }

    Task(const Task &rhs) {
        task_id = rhs.task_id;
        priority = rhs.priority;
        time = rhs.time;
    }

    ~ Task() = default;
};

// CPUState: idle and busy.
enum CPUState {
    idle = 0, busy = 1
};

}

endif

```

其中,

  • task_id 是每个任务的编号,为一个 unsigned int 范围内的非 0 整数
  • priority 是每个任务的优先级,为一个 unsigned int 范围内的整数,优先级越高的任务 priority 值越小
  • time 是每个任务需要的时间,为一个 unsigned int 范围内的整数,最小单位为 1。

然后,我们提供了一个 CPU 基类:

```c++

ifndef SJTU_CPP_FINAL_CPU_HPP

define SJTU_CPP_FINAL_CPU_HPP

include

include "task.hpp"

using namespace std;

typedef unsigned int uint;

namespace sjtu { // CPU base class, modifications is not allowed. class CPU { protected: CPUState state; vector tasks;

public:
    CPU() : tasks() {
        state = idle;
    }

    // Add a new task.
    int addTask(const Task &t) {
        tasks.push_back(t);
        return 1;
    }

    // Change the priority of one process, return 1 if success and return 0 if fail.
    int changePriority(uint task_id, uint priority) {
        for (auto &task: tasks)
            if (task.task_id == task_id) {
                task.priority = priority;
                return 1;
            }
        return 0;
    }

    virtual pair<CPUState, uint> run() = 0;

    virtual ~ CPU() = default;
};

// FCFS method based CPU.
class CPU_FCFS : public CPU {
    // TODO: complete the FCFS method.

};

// SRTF method based CPU.
class CPU_SRTF : public CPU {
    // TODO: complete the SRTF method.

};

// priority method based CPU.
class CPU_PRIORITY : public CPU {
    // TODO: complete the priority method.

};

}

endif

```

其中,

  • state 表示目前 CPU 的状态,有 idlebusy 两种状态;
  • tasks 是一个任务列表,包含 CPU 当前的所有任务;
  • 对于不会使用 vector 的同学,将 tasks 看成一个长度为 tasks.size() 的数组即可,其中的元素都是 Task 类型的。使用该知识即可完成本题。
  • addTask(t) 已为你写好,表示向 CPU 的任务列表中加入 t
  • changePriority(task_id, priority) 已为你写好,表示将 CPU 的任务列表中,编号为 task_id 的任务的优先级修改为 priority
  • run()你需要在派生类中实现的部分,你需要从当前的任务列表中,根据指定的方法找到下个时间单位 CPU 需要执行的任务(时间单位为 1)。并返回一个 pair <CPUState, unsigned int>,前者表示 CPU 的状态 (busy/idle),后者表示正在执行的任务编号 task_id
  • 如果 CPU 处于忙碌 (busy) 状态,则 task_id 不会是 0;
  • 如果 CPU 处于空闲 (idle) 状态,则返回的 task_id 必须为 0(此时没有任务在执行)。
  • 对于不会使用 pair 的同学,假设你需要返回的两个值为 x, y,只需使用 make_pair(x, y) 即可产生一个 pair 类型。

而你需要实现的部分,就是下面三个由基类派生的来的派生类,你至少需要实现每个派生类中的 run() 接口;当然,你也可以对 addTask(t)changePriority(task_id, priority) 在派生类中进行修改,但是不能改变这两个函数的参数接口。我们将会模拟 1000​ 个连续时间单位,调用 1000 次 run() 来评估你的代码的实现情况。

```c++ // FCFS method based CPU. class CPU_FCFS : public CPU { // TODO: complete the FCFS method.

};

// SRTF method based CPU. class CPU_SRTF : public CPU { // TODO: complete the SRTF method.

};

// priority method based CPU. class CPU_PRIORITY : public CPU { // TODO: complete the priority method.

}; test.cpp 如下:c++

include

include

include "cpu.hpp"

include "task.hpp"

using namespace std;

namespace cpu_testing { enum operationType {AddTask, ChangePriority};

struct Operation {
    operationType type;
    uint trig_time;
    sjtu::Task task;

    Operation(operationType _type, uint _trig_time, const sjtu::Task &_task) : task(_task) {
        type = _type;
        trig_time = _trig_time;
    }

    ~ Operation() = default;
};

vector <Operation> readInputs() {
    vector<Operation> operations;
    int m, op;
    uint trig_time, task_id, priority, time;
    cin >> m;
    for (int i = 0; i < m; ++i) {
        cin >> op >> trig_time;
        if (op == 0) {
            cin >> task_id >> priority >> time;
            operations.emplace_back(Operation(AddTask, trig_time, sjtu::Task(task_id, priority, time)));
        } else {
            cin >> task_id >> priority;
            operations.emplace_back(Operation(ChangePriority, trig_time, sjtu::Task(task_id, priority)));
        }
    }
    return operations;
}

void processOutputs(const vector<pair<sjtu::CPUState, uint> > &ans) {
    for (auto log: ans) {
        if (log.first == sjtu::busy && log.second == 0) {
            cerr << "[Error] Busy CPU is not processing any task.\n";
            exit(1);
        }
        if (log.first == sjtu::idle && log.second != 0) {
            cerr << "[Error] Idle CPU is still processing tasks.\n";
            exit(1);
        }
        cout << log.first << ' ' << log.second << endl;
    }
}

}

int main() { ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);

vector<cpu_testing::Operation> operations(cpu_testing::readInputs());

sjtu::CPU *processor;
int CPUType;
cin >> CPUType;
switch (CPUType) {
    case 0:
        processor = new sjtu::CPU_FCFS();
        break;
    case 1:
        processor = new sjtu::CPU_SRTF();
        break;
    case 2:
        processor = new sjtu::CPU_PRIORITY();
        break;
    default:
        cerr << "[Error] Unexpected CPU type.";
        return 1;
}

vector<pair<sjtu::CPUState, uint> > ans;
int time = 0, cur = 0;
while (time <= 1000) {
    while (cur < operations.size() && operations[cur].trig_time == time) {
        int success = 0;
        if (operations[cur].type == cpu_testing::AddTask)
            success = processor->addTask(operations[cur].task);
        if (operations[cur].type == cpu_testing::ChangePriority)
            success = processor->changePriority(operations[cur].task.task_id, operations[cur].task.priority);
        if (success == 0) {
            cerr << "[Error] Fail to execute operation " << cur << ".\n";
        }
        ++ cur;
    }
    ans.push_back(processor->run());
    ++ time;
}

cpu_testing::processOutputs(ans);
delete processor;
return 0;

} ```

输入格式

输入包含若干行。第一行为一个数 m,表示任务数量。

接下来 m 行,每行前两个数 op, trig_time,表示操作类型与操作的时间。

  • 操作类型为 0 表示为添加任务;操作类型为 1 表示更改任务优先级;
  • 操作的时间需要是一个 $[0,999]$ 内的整数。

接下来,如果操作类型为 0,接下来三个数 task_id, time, priority 描述一个任务;如果操作类型为 1,接下来两个数 task_id, priority 表示将编号为 task_id 的任务的优先级值修改为 priority

保证操作时间按照升序排序

最后一行,一个数 CPUType 表示 CPU 所采取的方法:

  • CPUType = 0 表示采用 FCFS 方法;
  • CPUType = 1 表示采用 SRTF 方法;
  • CPUType = 2 表示采用 Priority 方法。

输出格式

输出包含 1000 行,每行两个数,表示 $[0,999]$ 这 1000 个连续时间单位内 CPU 的任务安排情况。第一个数表示 CPU 状态,0 表示 idle,1 表示 busy;第二个数表示下个时间单位 CPU 执行的进程的 task_id,如果当前 CPU 空闲,则这个数应该为 0。并且从添加任务到执行任务我们认为可以在一个时间单位内完成。

样例输入

输入样例 1

3 0 1 1 10 3 0 1 2 10 1 0 1 3 10 1 0

输出样例 1

0 0 1 1 1 1 1 1 1 2 1 3 0 0 ... (后面均为 0 0)

输入样例 2

3 0 1 1 10 3 0 2 2 10 1 0 3 3 10 1 1

输出样例 2

0 0 1 1 1 2 1 3 1 1 1 1 0 0 ... (后面均为 0 0)

输入样例 3

4 0 1 1 10 3 0 2 2 9 2 1 3 1 8 0 3 3 11 1 2

输出样例 3

0 0 1 1 1 2 1 1 1 1 1 2 1 3 0 0 ... (后面均为 0 0)

样例输出

见样例输入

数据范围

$1 \leq m \leq 200$

测试数据中,满足

  • 30% 的数据,测试 FCFS 方法;

  • 30% 的数据,测试 SRTF 方法;

  • 40% 的数据,测试 Priority 方法。

注意事项

  1. 不能改动基类中的任何代码
  2. 不能向 src.hpp 中添加头文件
  3. 不能改动 task.hpp 中的任何代码
  4. 输入和输出已经在 main.cpp 中为你写好,你不需要、且不应该考虑这两个部分(这两个部分的格式仅提供作调试用)。你可以直接在 src.hpp 中实现代码
  5. 可以在三个派生类中加入成员与成员函数;
  6. 我们的测试代码会在每个时间单位开始时调用 run()
  7. CPU 是抢占式的,也就是说,在 SRTF/Priority 方法中,上个时间单位执行的未执行完的任务,在下个时间单位不一定继续执行(比如来了一个优先级更高的任务,或来了一个剩余时间更短的任务);
  8. 优先级越高的任务,priority 值越小

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!