/*
 * 实验二：处理器调度模拟
 * 编译：gcc -o scheduler scheduler.c
 * 运行：./scheduler
 */

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

#define MAX_PROCESS 10

typedef struct {
    int pid;           // 进程ID
    int arrival;       // 到达时间
    int burst;         // 运行时间（CPU区间）
    int remaining;     // 剩余运行时间（RR用）
    int completion;    // 完成时间
    int turnaround;    // 周转时间
    float w_turnaround;// 带权周转时间
} Process;

// 打印结果
void print_result(Process p[], int n, char *algo) {
    printf("\n========== %s ==========\n", algo);
    printf("PID\t到达\t运行\t完成\t周转\t带权周转\n");
    float avg_tat = 0, avg_wtat = 0;
    for (int i = 0; i < n; i++) {
        printf("%d\t%d\t%d\t%d\t%d\t%.2f\n",
               p[i].pid, p[i].arrival, p[i].burst,
               p[i].completion, p[i].turnaround, p[i].w_turnaround);
        avg_tat += p[i].turnaround;
        avg_wtat += p[i].w_turnaround;
    }
    avg_tat /= n;
    avg_wtat /= n;
    printf("平均周转时间：%.2f\n", avg_tat);
    printf("平均带权周转时间：%.2f\n", avg_wtat);
}

// 先来先服务
void fcfs(Process p[], int n) {
    Process q[MAX_PROCESS];
    memcpy(q, p, sizeof(Process) * n);
    int time = 0;
    for (int i = 0; i < n; i++) {
        if (time < q[i].arrival) time = q[i].arrival;
        q[i].completion = time + q[i].burst;
        time = q[i].completion;
        q[i].turnaround = q[i].completion - q[i].arrival;
        q[i].w_turnaround = (float)q[i].turnaround / q[i].burst;
    }
    print_result(q, n, "FCFS");
}

// 短作业优先（非抢占）
void sjf(Process p[], int n) {
    Process q[MAX_PROCESS];
    memcpy(q, p, sizeof(Process) * n);
    int completed = 0, time = 0;
    int finish[MAX_PROCESS] = {0};
    while (completed < n) {
        int idx = -1;
        int min_burst = 99999;
        // 找已到达且未完成的最短作业
        for (int i = 0; i < n; i++) {
            if (!finish[i] && q[i].arrival <= time && q[i].burst < min_burst) {
                min_burst = q[i].burst;
                idx = i;
            }
        }
        if (idx == -1) { // 没有进程到达，时间推进
            time++;
            continue;
        }
        time += q[idx].burst;
        q[idx].completion = time;
        q[idx].turnaround = q[idx].completion - q[idx].arrival;
        q[idx].w_turnaround = (float)q[idx].turnaround / q[idx].burst;
        finish[idx] = 1;
        completed++;
    }
    print_result(q, n, "SJF（非抢占）");
}

// 时间片轮转（RR），时间片=2
void rr(Process p[], int n, int quantum) {
    Process q[MAX_PROCESS];
    memcpy(q, p, sizeof(Process) * n);
    for (int i = 0; i < n; i++) q[i].remaining = q[i].burst;

    int time = 0, completed = 0;
    int queue[MAX_PROCESS * 10], head = 0, tail = 0;
    int in_queue[MAX_PROCESS] = {0};

    // 初始化：把到达时间<=0的进程加入队列
    for (int i = 0; i < n; i++) {
        if (q[i].arrival <= time && !in_queue[i]) {
            queue[tail++] = i;
            in_queue[i] = 1;
        }
    }

    while (completed < n) {
        if (head == tail) { // 队列空，时间推进
            time++;
            // 检查新到达进程
            for (int i = 0; i < n; i++) {
                if (q[i].arrival <= time && !in_queue[i]) {
                    queue[tail++] = i;
                    in_queue[i] = 1;
                }
            }
            continue;
        }
        int idx = queue[head++];
        int exec = (q[idx].remaining < quantum) ? q[idx].remaining : quantum;
        time += exec;
        q[idx].remaining -= exec;

        // 执行期间检查新到达进程（模拟到达）
        for (int i = 0; i < n; i++) {
            if (q[i].arrival <= time && !in_queue[i] && i != idx) {
                queue[tail++] = i;
                in_queue[i] = 1;
            }
        }

        if (q[idx].remaining == 0) {
            completed++;
            q[idx].completion = time;
            q[idx].turnaround = q[idx].completion - q[idx].arrival;
            q[idx].w_turnaround = (float)q[idx].turnaround / q[idx].burst;
        } else {
            // 未完成，重新入队
            queue[tail++] = idx;
        }
    }
    print_result(q, n, "RR（时间片=2）");
}

int main() {
    // 示例进程：PID, 到达时间, 运行时间
    Process p[MAX_PROCESS] = {
        {1, 0, 5},
        {2, 1, 3},
        {3, 2, 8},
        {4, 3, 2},
        {5, 4, 4}
    };
    int n = 5;

    printf("进程列表：\n");
    printf("PID\t到达\t运行\n");
    for (int i = 0; i < n; i++) {
        printf("%d\t%d\t%d\n", p[i].pid, p[i].arrival, p[i].burst);
    }

    fcfs(p, n);
    sjf(p, n);
    rr(p, n, 2);

    return 0;
}