include <stdio.h>

include <stdlib.h>

include <malloc.h>

define TRUE 1

define FALSE 0

//作業(yè)數(shù)組大小

define LEN 5

/*
**
** 各種調(diào)度算法模擬仿真（鏈?zhǔn)酱鎯?chǔ)的隊(duì)列實(shí)現(xiàn)版）：
** 短作業(yè)優(yōu)先調(diào)度算法 （SJF）、先來(lái)先服務(wù)調(diào)度算法 （FCFS）
** 時(shí)間片輪轉(zhuǎn)調(diào)度算法 （RR） 、最高響應(yīng)比調(diào)度算法（HRRN）
** Author:賈志洋
** version:1.0
** Create Time: 2020/4/05 22:09
** Modified Time:
*/

/進(jìn)程PCB結(jié)點(diǎn)結(jié)構(gòu)體/
typedef struct job
{
int PID; //進(jìn)程的PID
int arrival_time; //進(jìn)程到達(dá)系統(tǒng)時(shí)間
int require_time_slice; //要求服務(wù)時(shí)間
int used_time_slice; //已經(jīng)使用的時(shí)間片(短作業(yè)優(yōu)先用不到該值)
int ended_time; //進(jìn)程完成時(shí)間 ，初始值為-1，表示進(jìn)程未完成，如果該進(jìn)程已經(jīng)完成則>=0
int waited_time; //等待時(shí)間，等待時(shí)間=周轉(zhuǎn)時(shí)間-要求服務(wù)時(shí)間
int cycle_time; //周轉(zhuǎn)時(shí)間，周轉(zhuǎn)時(shí)間=結(jié)束時(shí)間-到達(dá)時(shí)間
float weight_cycle_time; //帶權(quán)周轉(zhuǎn)時(shí)間，帶權(quán)周轉(zhuǎn)時(shí)間=周轉(zhuǎn)時(shí)間/要求服務(wù)時(shí)間
struct job * next; //所在隊(duì)列的下一個(gè)作業(yè)
}job;

/作業(yè)隊(duì)列的結(jié)構(gòu)體/
typedef struct linked_queue
{
job * front; //隊(duì)頭指向結(jié)點(diǎn)的指針
job * rear; //隊(duì)尾指向結(jié)點(diǎn)的指針
int count; //隊(duì)列當(dāng)前長(zhǎng)度
}linked_queue;

//作業(yè)數(shù)組全局變量
struct job job_array[LEN];

//后備隊(duì)列
linked_queue * created_queue;
//就緒隊(duì)列
linked_queue * ready_queue;
//完成隊(duì)列
linked_queue * ended_queue;

//初始化作業(yè)數(shù)組的每個(gè)作業(yè)信息
void init_jobs();
//初始化各個(gè)隊(duì)列
void init_queues();
//打印菜單
void print_menu();
//短作業(yè)優(yōu)先調(diào)度算法 （SJF）
void sjf_jobs();
//先來(lái)先服務(wù)調(diào)度算法 （FCFS）
void fcfs_jobs();
//時(shí)間片輪轉(zhuǎn)調(diào)度算法 （RR）
void rr_jobs(int q);
//最高響應(yīng)比調(diào)度算法（HRRN）
void hrrn_jobs();

//打印輸出所有作業(yè)的各種時(shí)間平均值
void print_average_value();
//作業(yè)出隊(duì)列函數(shù)
job * de_queue(linked_queue * queue);
//返回隊(duì)頭作業(yè)（不出隊(duì)）
job * peek_queue(linked_queue * queue);
//計(jì)算該作業(yè)的各種時(shí)間
void record_job_time(job * record_job);
//作業(yè)結(jié)點(diǎn)入隊(duì)
void en_queue_node(linked_queue * queue,job * en_queue_pcb_node);

/程序入口/
int main()
{
//記錄用戶(hù)鍵盤(pán)輸入的選擇鍵
char user_opt;
while(1)
{
//初始化作業(yè)數(shù)組中每個(gè)作業(yè)
init_jobs();
//初始化各個(gè)隊(duì)列
init_queues();
//打印菜單
print_menu();
scanf("%c", &user_opt);
getchar();
switch(user_opt)
{
case '1' :
sjf_jobs();
break;
case '2':
fcfs_jobs();
break;
case '3':
rr_jobs(1);
break;
case '4':
rr_jobs(4);
break;
case '5':
hrrn_jobs();
break;
case 'q':
exit(0);
break;
}
}

return 0;

}

void print_menu()
{
printf("\n======================\n");
printf("按1鍵SJF \n");
printf("按2鍵FCFS\n");
printf("按3鍵RR時(shí)間片輪轉(zhuǎn)（q=1）\n");
printf("按3鍵RR時(shí)間片輪轉(zhuǎn)（q=4）\n");
printf("按3鍵HRRN\n");
printf("按q鍵退出 \n");
printf("您的選擇： \n");
printf("\n======================\n");
}

void init_jobs()
{
//根據(jù)題目要求的表格初始化每個(gè)進(jìn)程的信息（也可以通過(guò)控制臺(tái)輸入）
job_array[0].PID = 0; job_array[0].require_time_slice = 3; job_array[0].arrival_time = 0; job_array[0].ended_time =-1; job_array[0].used_time_slice = 0;
job_array[1].PID = 1; job_array[1].require_time_slice = 6; job_array[1].arrival_time = 2; job_array[1].ended_time =-1; job_array[1].used_time_slice = 0;
job_array[2].PID = 2; job_array[2].require_time_slice = 4; job_array[2].arrival_time = 4; job_array[2].ended_time =-1; job_array[2].used_time_slice = 0;
job_array[3].PID = 3; job_array[3].require_time_slice = 5; job_array[3].arrival_time = 6; job_array[3].ended_time =-1; job_array[3].used_time_slice = 0;
job_array[4].PID = 4; job_array[4].require_time_slice = 2; job_array[4].arrival_time = 8; job_array[4].ended_time =-1; job_array[4].used_time_slice = 0;
}

void init_queues()
{
//釋放原來(lái)的
free(created_queue);
free(ready_queue);
free(ended_queue);
//后備隊(duì)列
created_queue = (linked_queue)malloc(sizeof(linked_queue));
//初始化隊(duì)列
created_queue->front = created_queue->rear = NULL;
//就緒隊(duì)列
ready_queue = (linked_queue)malloc(sizeof(linked_queue));
//初始化隊(duì)列
ready_queue->front = ready_queue->rear = NULL;
//完成隊(duì)列
ended_queue = (linked_queue*)malloc(sizeof(linked_queue));
//初始化隊(duì)列
ended_queue->front = ended_queue->rear = NULL;

//將作業(yè)數(shù)組中所有作業(yè)放入后備隊(duì)列
int i;
for(i=0;i<LEN;i++)
    en_queue_node(created_queue,&job_array[i]);

}

void record_job_time(job * record_job)
{
//計(jì)算該作業(yè)的各種時(shí)間
record_job->cycle_time = record_job->ended_time - record_job->arrival_time;
record_job->waited_time = record_job->cycle_time - record_job->require_time_slice;
record_job->weight_cycle_time = (float)record_job->cycle_time / (float)record_job->require_time_slice;

}

void print_average_value()
{
//平均周轉(zhuǎn)時(shí)間
float avg_cycle_time = 0;
//平均等待時(shí)間
float avg_waited_time = 0;
//平均帶權(quán)周轉(zhuǎn)時(shí)間
float avg_weight_cycle_time = 0;
//遍歷作業(yè)數(shù)組，求和值
int i;
for(i=0;i<LEN;i++)
{
avg_cycle_time += (float) job_array[i].cycle_time;
avg_waited_time += (float) job_array[i].waited_time;
avg_weight_cycle_time += job_array[i].weight_cycle_time;
}
//計(jì)算均值
avg_cycle_time = avg_cycle_time / (float) LEN;
avg_waited_time = avg_waited_time / (float) LEN;
avg_weight_cycle_time = avg_weight_cycle_time / (float) LEN;

printf("平均周轉(zhuǎn)時(shí)間：%05.2f平均等待時(shí)間：%05.2f平均帶權(quán)周轉(zhuǎn)時(shí)間：%05.2f\n",avg_cycle_time,avg_waited_time,avg_weight_cycle_time);

}

void fcfs_jobs()
{

//先來(lái)先服務(wù)調(diào)度算法

int current_time = 0;
//當(dāng)前運(yùn)行的作業(yè) 
job * running_job = NULL;

//后備隊(duì)列不為空 或 就緒隊(duì)列不為空 或 正在有作業(yè)運(yùn)行  則進(jìn)行調(diào)度 
while (!is_queue_empty(created_queue)||!is_queue_empty(ready_queue)||running_job!=NULL)
{
    //把后備隊(duì)列中，到達(dá)時(shí)間為當(dāng)前系統(tǒng)時(shí)間的作業(yè)掛入就緒隊(duì)列
    while (!is_queue_empty(created_queue))
    {
        job * front_job = peek_queue(created_queue);
        if (front_job->arrival_time==current_time)
        {
            //后備隊(duì)列出隊(duì)一個(gè)作業(yè)并掛入就緒隊(duì)列
            en_queue_node(ready_queue,de_queue(created_queue) );
        }
        else
        {
            //一定要有else，表示后備隊(duì)列中的當(dāng)前隊(duì)頭作業(yè)的到達(dá)系統(tǒng)時(shí)間大于系統(tǒng)當(dāng)前時(shí)間，需要退出while循環(huán) 
            break;
        }
        
    }
    
    //判斷當(dāng)前是否有進(jìn)程使用CPU
    if (running_job == NULL)
    {
        //無(wú)作業(yè)使用CPU，將就緒隊(duì)列隊(duì)頭出隊(duì)，去使用CPU
        if (!is_queue_empty(ready_queue))
            running_job = de_queue(ready_queue);
        else
        {
            //為了增加程序的健壯性，可以用某些其它數(shù)據(jù)測(cè)試（本題目要求沒(méi)有出現(xiàn)這種情況）
            //需要考慮，當(dāng)前就緒隊(duì)列為空，但后備隊(duì)列仍舊有未到達(dá)系統(tǒng)的作業(yè)，系統(tǒng)時(shí)間空轉(zhuǎn)1個(gè)時(shí)間片 
            printf("系統(tǒng)%d時(shí)刻就緒隊(duì)列空\(chéng)n", current_time);
            current_time++;
            continue; 
            
        }
        //printf("調(diào)度新的作業(yè)使用CPU：%d\n",running_job->PID);
    } 
    else
    {
        //如果有作業(yè)正在使用CPU，判斷其使用CPU時(shí)間是否已經(jīng)滿(mǎn)足其要求服務(wù)時(shí)間
        if (running_job->used_time_slice==running_job->require_time_slice) 
        {
            //該作業(yè)要求服務(wù)時(shí)間已滿(mǎn)足
             
            //記錄作業(yè)完成時(shí)間 
            running_job->ended_time = current_time;
            //將該作業(yè)掛入完成隊(duì)列
            en_queue_node(ended_queue,running_job);
            //計(jì)算并存儲(chǔ)各種時(shí)間
            record_job_time(running_job); 
            printf("調(diào)作業(yè)%d已完成，完成時(shí)間：%d\n",running_job->PID,running_job->ended_time);
            //從就緒隊(duì)列調(diào)度新的作業(yè)使用CPU 
            if (!is_queue_empty(ready_queue))
                running_job = de_queue(ready_queue);
            else
                running_job = NULL;
        }
        else
        {
            //空實(shí)現(xiàn) 
        } 
    }
    
    //系統(tǒng)時(shí)間步進(jìn) 
    current_time++;
    //當(dāng)前正在運(yùn)行的作業(yè)的使用的時(shí)間片++ 
    if (running_job!=NULL)
        running_job->used_time_slice++;
}

printf("FCFS的調(diào)度信息：\n");
//打印該調(diào)度算法的各種時(shí)間的平均值 
print_average_value();

}

void sjf_jobs()
{
//請(qǐng)實(shí)現(xiàn)，SJF算法
}
void rr_jobs(int q)
{
//請(qǐng)實(shí)現(xiàn)，時(shí)間片輪轉(zhuǎn)RR算法，傳入?yún)?shù)為時(shí)間片q的大小
}
void hrrn_jobs()
{
//請(qǐng)實(shí)現(xiàn) ，最高響應(yīng)比優(yōu)先算法HRRN（非搶占），
}

//作業(yè)結(jié)點(diǎn)入隊(duì)
void en_queue_node(linked_queue * queue,job * en_queue_pcb_node)
{
//將傳入的Job作業(yè)結(jié)點(diǎn)入隊(duì)
if (is_queue_empty(queue)){
queue->front = en_queue_pcb_node;
queue->rear = en_queue_pcb_node;
}else{
//隊(duì)列非空，
queue->rear->next = en_queue_pcb_node;
queue->rear = en_queue_pcb_node;
}
}

//判斷隊(duì)列是否為空
int is_queue_empty(linked_queue * queue)
{
if ((queue->front==NULL)&&(queue->rear==NULL))
return TRUE;
else
return FALSE;
}

/遍歷隊(duì)列，按順序?qū)㈥?duì)列中每個(gè)元素的值打印輸出/
void show_queue_all_job(linked_queue * queue){
if (is_queue_empty(queue)){
printf("隊(duì)列為空，遍歷結(jié)束\n");
return;
}
//游標(biāo)指針
job * cursor_pcb_pointer;
cursor_pcb_pointer = queue->front;
printf("---------------\n");
printf("隊(duì)列為：\n");
/順序遍歷隊(duì)列每個(gè)結(jié)點(diǎn)/
while (cursor_pcb_pointer!=NULL){
//打印當(dāng)前結(jié)點(diǎn)信息，
printf("結(jié)點(diǎn)PID：%d，時(shí)間片需求為：%d\n",cursor_pcb_pointer->PID,cursor_pcb_pointer->require_time_slice);
//后移游標(biāo)指針
cursor_pcb_pointer=cursor_pcb_pointer->next;
}
printf("---------------\n");

}

job * de_queue(linked_queue * queue)
{
job * return_job;
if (is_queue_empty(queue)){
printf("隊(duì)列為空，無(wú)法出隊(duì)\n");
return NULL;
}

return_job = queue->front;
if (queue->front==queue->rear){
    //只有一個(gè)結(jié)點(diǎn)時(shí)候
    queue->front=queue->rear=NULL;
}else{
    //多于一個(gè)結(jié)點(diǎn)時(shí)
    queue->front = queue->front->next;  
}
return_job->next = NULL;
return return_job;

}
//返回隊(duì)頭作業(yè)，但不出隊(duì)
job * peek_queue(linked_queue * queue)
{
return queue->front;
}