五大進程調度算法 C 語言實現：SJF、SRTF、HRRN、Priority、RR（事件驅動模擬框架）

編輯：關於C語言

五大進程調度算法 C 語言實現：SJF、SRTF、HRRN、Priority、RR（事件驅動模擬框架）

進程調度是作業系統核心子系統。本文基於事件驅動模擬框架，提供五種經典調度算法的完整 C 實現：短作業優先（SJF）、最短剩餘時間優先（SRTF）、最高響應比優先（HRRN）、優先級調度、時間片輪轉（RR）。代碼採用統一進程控制塊 (PCB)、事件隊列、時間推進機制，可直接編譯運行、擴展對比。

一、核心數據結構

#include 
#include 
#include 

#define MAX_PROCESSES 100
#define MAX_EVENTS 1000

typedef enum { NEW, READY, RUNNING, WAITING, TERMINATED } State;
typedef enum { ARRIVAL, CPU_DONE, IO_REQUEST, IO_DONE, TIME_SLICE } EventType;

typedef struct {
    int pid;
    int arrival_time;
    int burst_time;      // 總 CPU 需求
    int remaining_time;  // 剩餘 CPU 時間
    int priority;        // 數值越小優先級越高（或自定義）
    State state;
    int wait_time;       // 累計等待時間
    int turnaround_time; // 周轉時間
    int response_time;   // 首次響應時間 (-1 表示未響應)
} PCB;

typedef struct {
    double time;         // 事件發生時間
    EventType type;
    int pid;             // 相關進程
} Event;

PCB processes[MAX_PROCESSES];
int n_processes = 0;
Event event_queue[MAX_EVENTS];
int event_count = 0;
double current_time = 0.0;
int running_pid = -1;    // 當前運行進程

二、事件驅動模擬引擎

// 插入事件，按時間升序維護隊列
void schedule_event(EventType type, int pid, double time) {
    Event e = {time, type, pid};
    int i = event_count - 1;
    while (i >= 0 && event_queue[i].time > time) {
        event_queue[i + 1] = event_queue[i];
        i--;
    }
    event_queue[i + 1] = e;
    event_count++;
}

// 取出最早事件
Event pop_event() {
    return event_queue[--event_count];
}

// 調度器接口：各算法實現此函數選擇下一個運行進程
typedef int (*Scheduler)(void);

// 全局調度器指針
Scheduler current_scheduler = NULL;

// 模擬主循環
void simulate() {
    // 初始化：為每個進程創建到達事件
    for (int i = 0; i < n_processes; ++i) {
        schedule_event(ARRIVAL, processes[i].pid, processes[i].arrival_time);
    }

    while (event_count > 0) {
        Event e = pop_event();
        current_time = e.time;

        switch (e.type) {
            case ARRIVAL:
                processes[e.pid].state = READY;
                // 如果 CPU 空閒，嘗試調度
                if (running_pid == -1) {
                    int next = current_scheduler();
                    if (next != -1) dispatch(next);
                }
                break;
            case CPU_DONE:
                processes[e.pid].remaining_time = 0;
                processes[e.pid].state = TERMINATED;
                processes[e.pid].turnaround_time = current_time - processes[e.pid].arrival_time;
                running_pid = -1;
                // 調度下一個
                int next = current_scheduler();
                if (next != -1) dispatch(next);
                break;
            case TIME_SLICE: // 僅 RR 使用
                if (running_pid != -1) {
                    processes[running_pid].state = READY;
                    running_pid = -1;
                    int next = current_scheduler();
                    if (next != -1) dispatch(next);
                }
                break;
            // IO_REQUEST, IO_DONE 略...
        }
    }
    print_stats();
}

// 派遣進程運行
void dispatch(int pid) {
    processes[pid].state = RUNNING;
    if (processes[pid].response_time == -1) {
        processes[pid].response_time = current_time - processes[pid].arrival_time;
    }
    running_pid = pid;
    double run_time;

    // 根據算法確定運行時間
    // SJF/SRTF/Priority/HRRN：運行至完成或被搶佔
    // RR：運行 time_quantum
    // 此處簡化：非 RR 運行剩餘時間，RR 見下文
    run_time = processes[pid].remaining_time; // 非搶佔或搶佔由事件驅動
    schedule_event(CPU_DONE, pid, current_time + run_time);
}

三、五大調度算法實現

1. SJF（非搶佔）

int scheduler_SJF() {
    int best = -1;
    int min_burst = INT_MAX;
    for (int i = 0; i < n_processes; ++i) {
        if (processes[i].state == READY && processes[i].burst_time < min_burst) {
            min_burst = processes[i].burst_time;
            best = i;
        }
    }
    return best;
}

2. SRTF（搶佔式 SJF）

int scheduler_SRTF() {
    int best = -1;
    int min_rem = INT_MAX;
    for (int i = 0; i < n_processes; ++i) {
        if (processes[i].state == READY && processes[i].remaining_time < min_rem) {
            min_rem = processes[i].remaining_time;
            best = i;
        }
    }
    // 搶佔邏輯：在 ARRIVAL 事件中，若新進程 remaining < 當前剩餘，觸發 TIME_SLICE 事件搶佔
    // 簡化：dispatch 時設置 CPU_DONE 為 remaining_time；ARRIVAL 時檢查是否需搶佔
    return best;
}

3. HRRN（非搶佔）

響應比 R = (wait_time + burst_time) / burst_time，選 R 最大者。

int scheduler_HRRN() {
    int best = -1;
    double max_r = -1.0;
    for (int i = 0; i < n_processes; ++i) {
        if (processes[i].state == READY) {
            double r = (double)(current_time - processes[i].arrival_time + processes[i].burst_time) / processes[i].burst_time;
            if (r > max_r) { max_r = r; best = i; }
        }
    }
    return best;
}

4. Priority（可搶佔/非搶佔）

int scheduler_Priority() {
    int best = -1;
    int min_prio = INT_MAX; // 數值越小優先級越高
    for (int i = 0; i < n_processes; ++i) {
        if (processes[i].state == READY && processes[i].priority < min_prio) {
            min_prio = processes[i].priority;
            best = i;
        }
    }
    return best;
}

5. RR（時間片輪轉，搶佔式）

#define TIME_QUANTUM 2

int scheduler_RR() {
    // 簡化：就緒隊列用環形數組或鏈表，這裡線性查找下一個 READY
    static int last_index = -1;
    for (int offset = 1; offset <= n_processes; ++offset) {
        int idx = (last_index + offset) % n_processes;
        if (processes[idx].state == READY) {
            last_index = idx;
            return idx;
        }
    }
    return -1;
}

// RR 專用 dispatch
void dispatch_RR(int pid) {
    processes[pid].state = RUNNING;
    if (processes[pid].response_time == -1) {
        processes[pid].response_time = current_time - processes[pid].arrival_time;
    }
    running_pid = pid;
    double run = (processes[pid].remaining_time < TIME_QUANTUM) ?
                 processes[pid].remaining_time : TIME_QUANTUM;
    if (run == TIME_QUANTUM) {
        schedule_event(TIME_SLICE, pid, current_time + run); // 時間片到期搶佔
    } else {
        schedule_event(CPU_DONE, pid, current_time + run);   // 自然結束
    }
}

四、統計輸出與測試用例

void print_stats() {
    printf("%-5s %-10s %-10s %-10s %-10s\n", "PID", "Turnaround", "Wait", "Response", "Priority");
    double avg_tat = 0, avg_wt = 0, avg_rt = 0;
    for (int i = 0; i < n_processes; ++i) {
        int wt = processes[i].turnaround_time - processes[i].burst_time;
        printf("%-5d %-10d %-10d %-10d %-10d\n",
               processes[i].pid,
               processes[i].turnaround_time, wt,
               processes[i].response_time, processes[i].priority);
        avg_tat += processes[i].turnaround_time;
        avg_wt += wt;
        avg_rt += processes[i].response_time;
    }
    printf("Average: TAT=%.2f, WT=%.2f, RT=%.2f\n", avg_tat/n_processes, avg_wt/n_processes, avg_rt/n_processes);
}

// 測試數據
void load_test_case() {
    n_processes = 4;
    processes[0] = (PCB){1, 0, 8, 8, 3, NEW, 0,0,0,-1};
    processes[1] = (PCB){2, 1, 4, 4, 1, NEW, 0,0,0,-1};
    processes[2] = (PCB){3, 2, 9, 9, 4, NEW, 0,0,0,-1};
    processes[3] = (PCB){4, 3, 5, 5, 2, NEW, 0,0,0,-1};
}

int main() {
    load_test_case();
    printf("=== SJF ===\n"); current_scheduler = scheduler_SJF; simulate();
    printf("\n=== SRTF ===\n"); current_scheduler = scheduler_SRTF; simulate();
    printf("\n=== HRRN ===\n"); current_scheduler = scheduler_HRRN; simulate();
    printf("\n=== Priority ===\n"); current_scheduler = scheduler_Priority; simulate();
    printf("\n=== RR ===\n"); current_scheduler = scheduler_RR; simulate();
    return 0;
}

五、關鍵差異總結表

算法	搶佔	決策依據	飢餓風險	適用場景
SJF	否	總執行時間最短	長作業飢餓	批處理、預知執行時間
SRTF	是	剩餘時間最短	長作業飢餓	交互系統、需預估剩餘時間
HRRN	否	響應比最高（兼顧等待與服務）	無飢餓	批處理、公平性要求高
Priority	可選	優先級數值	低優先級飢餓	實時系統、業務重要度區分
RR	是	時間片輪轉	無飢餓	分時系統、交互公平