C++队列之时间片轮转调度（两种实现）

There are n processes in a queue. Each process has namei and timei. The round-robin scheduling handles the processes in order. A round-robin scheduler gives each process a quantum (a time slot) and interrupts the process if it is not completed by then. The process is resumed and moved to the end of the queue, then the scheduler handles the next process in the queue.

For example, we have the following queue with the quantum of 100ms.

5 100
p1 150
p2 80
p3 200
p4 350
p5 20

p2 180
p5 400
p1 450
p3 550
p4 800

现在有名字为 n a m e i name_i namei​且处理时间为 t i m e i time_i timei​的n个任务按顺序拍成一列。CPU通过时间片轮转调度来处理，每次CPU只能处理 q q q毫秒(时间片)。如果 q q q毫秒后任务没有完成，则移动至队伍尾部。

首先要明白队列的实现原理，先进先出。
其次我们需要一些代码实现的基本流程。一个队列有一个队头 h e a d head head，一个队尾 t a i l tail tail，我们首先要确定CPU循环轮转的条件是当队列种没有任务，此时 h e a d head head等于 t a i l tail tail。然后用一个数组来模拟一个队列，为了最大化利用数组的空间，我们采用了循环数组的方式

head = （head+1）%（数组最大长度）
tail = （tail+1）%（数组最大长度）

这样一来我们就实现了如图所示的队列，

Task dequeue()
{
    Task item = tk[head];
    head = (head + 1) % LEN;
    return item;
}
void enqueue(Task t)
{
    tk[tail] = t;
    tail = (tail + 1) % LEN;
}

最后是我们处理逻辑

while (head != tail)
    {
        Task t = dequeue();
        cur_time = min(t.time, slice);
        t.time -= cur_time;
        Time += cur_time;
        if (t.time > 0)
            enqueue(t);
        else
            cout << t.name << " " << Time << endl;
    }

首先判断当前任务的剩余时间与时间片的大小，若剩余时间大于时间片，则 t . t i m e t.time t.time减去 s l i c e slice slice后重新入队，并且总时间加上一个 s l i c e slice slice。若剩余时间小于时间片，则说明任务可以完成，不需要重新进入队列，打印输出，并总时间加上当前任务的剩余时间。所以总时间应该加上 t . t i m e t.time t.time和 s l i c e slice slice的最小值。
最后附上完整代码

#include 
using namespace std;
struct Task
{
    string name;
    int time;
    bool state;
};
const int LEN = 1e6 + 5;
Task tk[LEN];
int head, tail;
Task dequeue()
{
    Task item = tk[head];
    head = (head + 1) % LEN;
    return item;
}
void enqueue(Task t)
{
    tk[tail] = t;
    tail = (tail + 1) % LEN;
}
int main()
{
    int n, slice;
    scanf("%d %d", &n, &slice);
    for (int i = 0; i < n; i++)
    {
        cin >> tk[i].name >> tk[i].time;
    }
    head = 0;
    tail = n;
    int Time = 0;
    int cur_time = 0;
    while (head != tail)
    {
        Task t = dequeue();
        cur_time = min(t.time, slice);
        t.time -= cur_time;
        Time += cur_time;
        if (t.time > 0)
            enqueue(t);
        else
            cout << t.name << " " << Time << endl;
    }
}

这是使用C++模板库的代码

#include 
using namespace std;
int main()
{
    int n, slice, Time, t, p;
    string name;
    queue> task;
    cin >> n >> slice;
    for (int i = 0; i < n; i++)
    {
        cin >> name >> t;
        task.push(make_pair(name, t));//将name和t打包成一个pair后入队
    }
    pair cur_task;
    while (!task.empty())
    {
        cur_task = task.front();
        p = min(cur_task.second, slice);
        cur_task.second -= p;
        Time += p;
        if (cur_task.second > 0)
        {
            task.push(cur_task);
        }
        else
        {
            cout << cur_task.first << " " << Time << endl;
        }
    }
    return 0;
}

题目网址：AOJ-Queue练习