Single Core CPU Scheduling Algorithm by Using a Priority Queue

You are given a two-dimensional list of integers tasks. Each element contains [id, queue_time, duration] which represents a CPU task with id id, queued at time queue_time, that will run for duration amount of time. All tasks have unique ids.

Given that the CPU scheduler will run a job that is currently in the queue with the lowest duration first, return the order of job ids that will be processed. If there’s more than one job with the lowest duration, then it will run the job with lowest id first.

Constraints

n ≤ 100,000 where n is the length of tasks
Example 1
Input

1 2 3 4 5

tasks = [     [0, 1, 5],     [1, 1, 5],     [2, 2, 2] ]

tasks = [
    [0, 1, 5],
    [1, 1, 5],
    [2, 2, 2]
]

Output
[0, 2, 1]
Explanation
At time 1 we run task 0 since it’s the only one that’s queued. It runs for 5 units of time. Then we have tasks 1 and 2 that are queued. We run task 2 first because it has lower duration.

Example 2
Input

1 2 3 4

tasks = [     [0, 1, 5],     [1, 1, 5] ]

tasks = [
    [0, 1, 5],
    [1, 1, 5]
]

Output
[0, 1]
Explanation
Both tasks are queued up at the same time and both of them have the same duration. Since task 0 has lower id, we run it first.

CPU Scheduling Algorithm by using a Priority Queue

We understand that the CPU is single core meaning that at a time it can only process a task. We can sort the given tasks by the start time, then, we process the task one by one: if the priority queue is empty, we update the current timestamp. The next key algorithm is to push the tasks that have smaller or equal timestamp into the priority queue (waiting list).

At each iteration, we pop a task from the priority queue (shorter duration tasks are popped first, and if there are multiple tasks that are of same duration, we can consider process the job with a smaller ID).

Don’t forget that we need to update the current (global) CPU time.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

vector<int> CPUschedulor(vector<vector<int>>& tasks) {
    struct Task {
        int id;
        int startTime;
        int duration;
        Task(int id, int startTime, int duration): 
            id(id), startTime(startTime), duration(duration) {}
    };
    // convert a input task into the Task
    function<Task(vector<int>&)> convertToTask = [](vector<int> &task) {
        Task curTask(task[0], task[1], task[2]);        
        return curTask;
    };    
    vector<int> ans;
    auto whichTaskFirst = [](auto &t1, auto &t2) {
        return (t1.duration > t2.duration) || 
              ((t1.duration == t2.duration) && (t1.id > t2.id));
    };
    sort(begin(tasks), end(tasks), [](auto &t1, auto &t2) {
        // sort the tasks in descending order of startTime
        // so the last task arrives first.
        return t1[1] > t2[1];
    });
    priority_queue<Task, vector<Task>, decltype(whichTaskFirst)> pq(whichTaskFirst);
    int curTime = 0;
    int totalTasks = tasks.size();
    while (ans.size() < totalTasks) {
        if (pq.empty()) {
            curTime = max(curTime, tasks.back()[1]);
        }
        while (!tasks.empty() && (tasks.back()[1] <= curTime)) {
            pq.push(convertToTask(tasks.back()));
            tasks.pop_back();
        }
        ans.push_back(pq.top().id);
        curTime += pq.top().duration;
        pq.pop();        
    }
    return ans;
}

vector<int> CPUschedulor(vector<vector<int>>& tasks) {
    struct Task {
        int id;
        int startTime;
        int duration;
        Task(int id, int startTime, int duration): 
            id(id), startTime(startTime), duration(duration) {}
    };
    // convert a input task into the Task
    function<Task(vector<int>&)> convertToTask = [](vector<int> &task) {
        Task curTask(task[0], task[1], task[2]);        
        return curTask;
    };    
    vector<int> ans;
    auto whichTaskFirst = [](auto &t1, auto &t2) {
        return (t1.duration > t2.duration) || 
              ((t1.duration == t2.duration) && (t1.id > t2.id));
    };
    sort(begin(tasks), end(tasks), [](auto &t1, auto &t2) {
        // sort the tasks in descending order of startTime
        // so the last task arrives first.
        return t1[1] > t2[1];
    });
    priority_queue<Task, vector<Task>, decltype(whichTaskFirst)> pq(whichTaskFirst);
    int curTime = 0;
    int totalTasks = tasks.size();
    while (ans.size() < totalTasks) {
        if (pq.empty()) {
            curTime = max(curTime, tasks.back()[1]);
        }
        while (!tasks.empty() && (tasks.back()[1] <= curTime)) {
            pq.push(convertToTask(tasks.back()));
            tasks.pop_back();
        }
        ans.push_back(pq.top().id);
        curTime += pq.top().duration;
        pq.pop();        
    }
    return ans;
}

The algorithm runs at O(nLogN) where N is the number of tasks as we are sorting the tasks at the begining.

Follow up: how about there are N cpus, does this algorithm still work/apply?
One greedy strategy is to choose a next CPU which is idle or otherwise has a least current CPU time.

–EOF (The Ultimate Computing & Technology Blog) —