Task scheduling (priority queue)

Schedulers often pick the highest-priority ready task first. A priority queue is ideal for this because it always returns the best candidate quickly.

1) Scheduling policy

2) Example in C

#include <stdio.h>

#define MAX 32

typedef struct {
    int id;
    int pr;  // Priority (higher value = higher priority)
    int at;  // Arrival time (smaller value = earlier)
} Task;

Task heap[MAX];
int n = 0;

// Compare two tasks for max-heap ordering
int better(Task a, Task b) {
    if (a.pr != b.pr) return a.pr > b.pr;
    return a.at < b.at;
}

void swap(Task *a, Task *b) {
    Task t = *a;
    *a = *b;
    *b = t;
}

// Insert new task into heap
void push(Task t) {
    int i = n++;
    heap[i] = t;

    // Sift up
    while (i > 0) {
        int p = (i - 1) / 2;
        if (better(heap[p], heap[i])) break;
        swap(&heap[p], &heap[i]);
        i = p;
    }
}

// Remove top-priority task from heap
Task pop(void) {
    Task out = heap[0];
    heap[0] = heap[--n];

    // Sift down
    int i = 0;
    while (1) {
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        int best = i;

        if (l < n && better(heap[l], heap[best])) best = l;
        if (r < n && better(heap[r], heap[best])) best = r;
        if (best == i) break;

        swap(&heap[i], &heap[best]);
        i = best;
    }

    return out;
}

int main(void) {
    // (id, priority, arrival_time)
    push((Task){1, 2, 0});
    push((Task){2, 5, 1});
    push((Task){3, 3, 2});
    push((Task){4, 5, 3});

    printf("Scheduling order:\n");
    while (n > 0) {
        Task t = pop();
        printf("Run T%d (pr=%d, at=%d)\n", t.id, t.pr, t.at);
    }

    return 0;
}

Expected order

3) Complexity

• Insert task: O(log n)
• Pick next task: O(log n)
• Peek highest priority: O(1)