華為機試：作業系統任務調度——優先級佇列與時間片輪轉的 C 實現

題目需求

模擬簡單 OS 任務調度：

• 任務屬性：pid、priority（0-99，數值越大優先級越高）、burst_time。
• 調度規則：優先級佇列 + 時間片輪轉。同優先級按 FCFS，時間片耗盡或任務完成則調度下一任務。
• 系統任務（priority ≥ 50）與用戶任務（priority < 50）分離統計。

資料結構設計

typedef struct {
    int pid;
    int priority;
    int burst_time;
    int remaining_time;
} Task;

#define MAX_TASKS 100
Task *tasks;           // 所有任務
Task *sys_queue[MAX_TASKS];   // 系統任務就緒佇列
Task *usr_queue[MAX_TASKS];   // 用戶任務就緒佇列
int sys_head=0, sys_tail=0;
int usr_head=0, usr_tail=0;

核心調度邏輯

#define TIME_SLICE 10

void schedule() {
    // 1. 按優先級降序、到達順序排序所有任務
    qsort(tasks, n, sizeof(Task), cmp_priority);

    // 2. 分離入佇列
    for (int i = 0; i < n; ++i) {
        tasks[i].remaining_time = tasks[i].burst_time;
        if (tasks[i].priority >= 50)
            sys_queue[sys_tail++] = &tasks[i];
        else
            usr_queue[usr_tail++] = &tasks[i];
    }

    // 3. 處理系統任務佇列
    while (sys_head < sys_tail) {
        Task *t = sys_queue[sys_head++];
        run_task(t);
        if (t->remaining_time > 0)
            sys_queue[sys_tail++] = t;  // 重入佇尾
    }

    // 4. 處理用戶任務佇列（同邏輯）
    while (usr_head < usr_tail) {
        Task *t = usr_queue[usr_head++];
        run_task(t);
        if (t->remaining_time > 0)
            usr_queue[usr_tail++] = t;
    }
}

void run_task(Task *t) {
    int exec = (t->remaining_time < TIME_SLICE) ? t->remaining_time : TIME_SLICE;
    t->remaining_time -= exec;
    printf("PID %d runs %d units, remaining %d\n", t->pid, exec, t->remaining_time);
}

關鍵點解析

1. 優先級排序：qsort 配合比較函數 return b->priority - a->priority; 實現降序。
2. 佇列實現：環形陣列或簡單頭尾指針，MAX_TASKS 需足夠大（題目 n ≤ 100）。
3. 時間片邏輯：min(remaining, TIME_SLICE)，剩餘時間歸零則任務結束，否則重入佇尾。
4. 系統/用戶分離：兩組獨立佇列，系統任務優先耗盡後再跑用戶任務。

完整可編譯代碼

#include <stdio.h>
#include <stdlib.h>

#define MAX_TASKS 100
#define TIME_SLICE 10
#define SYS_THRESHOLD 50

typedef struct {
    int pid, priority, burst_time, remaining_time;
} Task;

int cmp_priority(const void *a, const void *b) {
    Task *ta = (Task *)a, *tb = (Task *)b;
    return tb->priority - ta->priority;  // 降序
}

int main() {
    int n;
    if (scanf("%d", &n) != 1 || n <= 0 || n > MAX_TASKS) return 1;

    Task *tasks = malloc(n * sizeof(Task));
    Task *sys_q[MAX_TASKS], *usr_q[MAX_TASKS];
    int sys_h=0, sys_t=0, usr_h=0, usr_t=0;

    for (int i = 0; i < n; ++i) {
        scanf("%d %d %d", &tasks[i].pid, &tasks[i].priority, &tasks[i].burst_time);
    }

    qsort(tasks, n, sizeof(Task), cmp_priority);

    for (int i = 0; i < n; ++i) {
        tasks[i].remaining_time = tasks[i].burst_time;
        if (tasks[i].priority >= SYS_THRESHOLD)
            sys_q[sys_t++] = &tasks[i];
        else
            usr_q[usr_t++] = &tasks[i];
    }

    // 調度循環
    while (sys_h < sys_t || usr_h < usr_t) {
        if (sys_h < sys_t) {
            Task *t = sys_q[sys_h++];
            int exec = t->remaining_time < TIME_SLICE ? t->remaining_time : TIME_SLICE;
            t->remaining_time -= exec;
            printf("System PID %d exec %d rem %d\n", t->pid, exec, t->remaining_time);
            if (t->remaining_time > 0) sys_q[sys_t++] = t;
        } else if (usr_h < usr_t) {
            Task *t = usr_q[usr_h++];
            int exec = t->remaining_time < TIME_SLICE ? t->remaining_time : TIME_SLICE;
            t->remaining_time -= exec;
            printf("User PID %d exec %d rem %d\n", t->pid, exec, t->remaining_time);
            if (t->remaining_time > 0) usr_q[usr_t++] = t;
        }
    }

    free(tasks);
    return 0;
}

擴展方向

• 引入多級反饋佇列：動態調整優先級，防止餓死。
• 支持阻塞/喚醒：I/O 等待狀態，需等待佇列與事件驅動。
• 統計指標：周轉時間、帶權周轉時間、響應時間。