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

#define MAX_PROCESSES 10

// 进程状态枚举
typedef enum {
    READY,      // 就绪态
    RUNNING,    // 运行态
    FINISHED    // 完成态
} ProcessState;

// 进程控制块 PCB
typedef struct {
    char name[20];          // 进程名
    int priority;           // 优先数（数值越大优先级越高）
    int needTime;           // 需要运行的时间
    int runTime;            // 已运行时间
    int waitTime;           // 等待时间
    ProcessState state;     // 状态
    int arrivalTime;        // 到达时间
} PCB;

PCB processes[MAX_PROCESSES];
int processCount = 0;

// 显示进程信息表头
void printHeader() {
    printf("----------------------------------------------------------------\n");
    printf("| 进程名 | 优先数 | 需要时间 | 已用时间 | 等待时间 |  状态    |\n");
    printf("----------------------------------------------------------------\n");
}

// 显示单个进程信息
void printProcess(PCB *p) {
    char *stateStr;
    switch(p->state) {
        case READY:    stateStr = "就绪态"; break;
        case RUNNING:  stateStr = "运行态"; break;
        case FINISHED: stateStr = "完成态"; break;
        default:       stateStr = "未知";   break;
    }
    printf("| %6s | %6d | %8d | %8d | %8d | %6s |\n",
           p->name, p->priority, p->needTime, p->runTime, p->waitTime, stateStr);
}

// 显示所有进程
void printAllProcesses() {
    printHeader();
    for (int i = 0; i < processCount; i++) {
        printProcess(&processes[i]);
    }
    printf("----------------------------------------------------------------\n");
}

// 显示就绪队列
void printReadyQueue() {
    printf("\n【当前就绪队列状态】\n");
    printf("就绪队列: ");
    int hasReady = 0;
    for (int i = 0; i < processCount; i++) {
        if (processes[i].state == READY) {
            if (hasReady) printf(" -> ");
            printf("%s(优先级:%d)", processes[i].name, processes[i].priority);
            hasReady = 1;
        }
    }
    if (!hasReady) printf("空");
    printf("\n");
}

// 按优先级排序（冒泡排序，降序）
void sortByPriority() {
    for (int i = 0; i < processCount - 1; i++) {
        for (int j = 0; j < processCount - i - 1; j++) {
            // 只比较就绪态的进程，且按优先级降序排列
            if (processes[j].state == READY && processes[j+1].state == READY) {
                if (processes[j].priority < processes[j+1].priority) {
                    PCB temp = processes[j];
                    processes[j] = processes[j+1];
                    processes[j+1] = temp;
                }
            }
        }
    }
}

// 找到优先级最高的就绪进程
int findHighestPriority() {
    int maxPriority = -999;
    int index = -1;
    for (int i = 0; i < processCount; i++) {
        if (processes[i].state == READY && processes[i].priority > maxPriority) {
            maxPriority = processes[i].priority;
            index = i;
        }
    }
    return index;
}

// 增加等待进程的等待时间和优先级（可选：等待过久提升优先级）
void updateWaitingProcesses() {
    for (int i = 0; i < processCount; i++) {
        if (processes[i].state == READY) {
            processes[i].waitTime++;
            // 如果等待时间超过3个时间片，优先数加1（防止饥饿）
            if (processes[i].waitTime > 3 && processes[i].priority < 10) {
                processes[i].priority++;
                printf("  >> %s 等待过久，优先级提升为 %d\n", 
                       processes[i].name, processes[i].priority);
            }
        }
    }
}

// 调度一个时间片
void scheduleOneSlice() {
    int idx = findHighestPriority();
    
    if (idx == -1) {
        printf("\n没有就绪的进程，调度结束！\n");
        return;
    }
    
    // 将选中的进程设为运行态
    processes[idx].state = RUNNING;
    
    printf("\n========================================\n");
    printf("【调度进程: %s】 优先级: %d, 还需时间: %d\n", 
           processes[idx].name, processes[idx].priority, processes[idx].needTime);
    printf("========================================\n");
    
    // 运行一个时间片
    processes[idx].runTime++;
    processes[idx].needTime--;
    
    // 显示运行中的状态
    printAllProcesses();
    printReadyQueue();
    
    // 动态优先数：运行后优先数减1
    processes[idx].priority--;
    
    // 检查是否完成
    if (processes[idx].needTime <= 0) {
        processes[idx].state = FINISHED;
        printf("\n>>> 进程 %s 运行完毕！\n", processes[idx].name);
    } else {
        // 未完成，回到就绪态
        processes[idx].state = READY;
        printf("\n>>> 进程 %s 时间片用完，回到就绪队列（优先级降为 %d）\n", 
               processes[idx].name, processes[idx].priority);
    }
    
    // 更新等待进程
    updateWaitingProcesses();
}

// 检查是否所有进程都已完成
int allFinished() {
    for (int i = 0; i < processCount; i++) {
        if (processes[i].state != FINISHED) {
            return 0;
        }
    }
    return 1;
}

// 初始化进程（直接写入程序中，无需输入）
void initProcesses() {
    // 进程1: aa
    strcpy(processes[0].name, "aa");
    processes[0].priority = 5;
    processes[0].needTime = 8;
    processes[0].runTime = 0;
    processes[0].waitTime = 0;
    processes[0].state = READY;
    processes[0].arrivalTime = 0;
    
    // 进程2: bb
    strcpy(processes[1].name, "bb");
    processes[1].priority = 3;
    processes[1].needTime = 6;
    processes[1].runTime = 0;
    processes[1].waitTime = 0;
    processes[1].state = READY;
    processes[1].arrivalTime = 0;
    
    // 进程3: cc
    strcpy(processes[2].name, "cc");
    processes[2].priority = 8;
    processes[2].needTime = 10;
    processes[2].runTime = 0;
    processes[2].waitTime = 0;
    processes[2].state = READY;
    processes[2].arrivalTime = 0;
    
    processCount = 3;
}

int main() {
    printf("============================================================\n");
    printf("        进程调度模拟程序 - 最高优先数优先算法\n");
    printf("============================================================\n");
    printf("\n【算法说明】\n");
    printf("  - 采用动态优先数调度\n");
    printf("  - 每次调度优先级最高的就绪进程\n");
    printf("  - 运行一个时间片后优先数减1\n");
    printf("  - 等待超3个时间片的进程优先级+1（防止饥饿）\n\n");
    
    // 初始化进程
    initProcesses();
    
    printf("【初始进程信息】\n");
    printAllProcesses();
    printReadyQueue();
    
    // 开始调度
    int slice = 1;
    while (!allFinished()) {
        printf("\n\n******************** 第 %d 次调度 ********************", slice++);
        scheduleOneSlice();
    }
    
    printf("\n============================================================\n");
    printf("              所有进程调度完成！\n");
    printf("============================================================\n");
    
    printf("\n【最终进程状态】\n");
    printAllProcesses();
    
    return 0;
}