#include <stdio.h>
#include <stdlib.h>
#define MAX_PROCESS 5   // 进程数量
#define TIME_SLICE 1    // 时间片大小(单位时间)

// 进程状态
enum State{
	READY,
	RUNNING,
	FINISHED
};

// 进程控制块
typedef struct{
	int pid;            // 进程ID
	int priority;       // 优先级
	int need_time;      // 剩余需要运行时间
	int total_time;     // 总运行时间
	int arrival_time;   // 到达时间
	int start_time;     // 开始运行时间
	int finish_time;    // 完成时间
	enum State state;   // 进程状态
}PCB;

// 全局进程数组
PCB processes[MAX_PROCESS];

// 当前时间
int current_time = 0;

// 初始化5个进程
void init_processes(){
	// 正确初始化所有进程
	processes[0] = (PCB){1, 3, 4, 4, 0, -1, 0, READY};
	processes[1] = (PCB){2, 5, 2, 2, 1, -1, 0, READY};
	processes[2] = (PCB){3, 2, 1, 1, 2, -1, 0, READY};
	processes[3] = (PCB){4, 4, 3, 3, 3, -1, 0, READY};
	processes[4] = (PCB){5, 1, 2, 2, 4, -1, 0, READY};
}

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

// 选择当前就绪队列中优先级最高的进程（若优先级相同，选择ID较小的）
// 返回进程在数组中的下标，若没有就绪进程则返回-1
int select_highest_priority(){
	int selected = -1;
	int max_priority = -1;
	for(int i=0; i<MAX_PROCESS; i++){
		if(processes[i].state == READY){
			if(processes[i].priority > max_priority){
				max_priority = processes[i].priority;
				selected = i;
			}else if(processes[i].priority == max_priority){
				// 优先级相同，选择ID更小的
				if(selected == -1 || processes[i].pid < processes[selected].pid){
					selected = i;
				}
			}
		}
	}
	return selected;
}

int main(){
	init_processes();
	printf("-----进程调度模拟过程-----\n");
	printf("调度算法:最高优先数优先（抢占式，动态优先级）\n");
	printf("动态规则:每获得一次CPU，优先数减1\n\n");
	
	int last_selected = -1;
	
	while(!all_finished()){
		int selected = select_highest_priority();
		
		// 无就绪进程，时间流逝
		if(selected == -1){
			current_time++;
			continue;
		}
		
		// 记录首次运行时间
		if(processes[selected].start_time == -1){
			processes[selected].start_time = current_time;
		}
		
		// 进程切换时打印信息
		if(last_selected != selected){
			printf("->时刻%d: 选中进程P%d (优先级=%d, 剩余时间=%d)\n",
			       current_time, processes[selected].pid, processes[selected].priority, processes[selected].need_time);
		}
		
		// 运行一个时间片
		processes[selected].state = RUNNING;
		processes[selected].need_time--;
		current_time++;
		
		// 动态优先级：运行一次优先级-1
		processes[selected].priority--;
		
		// 进程完成
		if(processes[selected].need_time == 0){
			processes[selected].state = FINISHED;
			processes[selected].finish_time = current_time;
			printf("进程P%d已完成！（完成时刻=%d）\n", processes[selected].pid, current_time);
		}else{
			processes[selected].state = READY;
		}
		
		last_selected = selected;
	}
	
	// 输出调度结果统计
	printf("\n-----调度完成-----\n");
	printf("进程\t到达时间\t开始时间\t总运行时间\t完成时间\t周转时间\n");
	int total_turnaround = 0;
	for(int i=0; i<MAX_PROCESS; i++){
		int turnaround = processes[i].finish_time - processes[i].arrival_time;
		total_turnaround += turnaround;
		printf("P%d\t%d\t\t%d\t\t%d\t\t%d\t\t%d\n",
		       processes[i].pid,
		       processes[i].arrival_time,
		       processes[i].start_time,
		       processes[i].total_time,
		       processes[i].finish_time,
		       turnaround);
	}
	
	printf("\n平均周转时间=%.2f\n", (float)total_turnaround / MAX_PROCESS);
	return 0;
}