/////////////////////////////////進程多隊列輪轉法調度算法
//文檔中有更詳細的注釋

#include "stdio.h"
#include <stdlib.h>
#include <conio.h>

# define getpcb(type) (type*)malloc(sizeof(type))
# define N 5//隊列數

struct pcb{//進程結構體
    char state;//狀態
    char name[10];//名字
    int total_time;//服務時間
    int run_time;//已運行時間
	int arrive_time;//到達時間
    int count;//所在隊列級數
    struct pcb *next;
}*p,*ready[N]={NULL};

typedef struct pcb PCB;

sort()//進程按到達時間先后存儲
{
    int flag=1,i;
    PCB *tm1,*tm2;
	if(p->count<N-1)
		i=p->count;
	else i=N;
    if(ready[i]==NULL)
    {
        ready[i]=p;
        ready[i]->next=NULL;
    }
	else if(p->arrive_time<ready[i]->arrive_time)
	{
		p->next=ready[i];
		ready[i]=p;
	}
    else
    {
        tm1=ready[i];
        tm2=ready[i]->next;
        while(tm2)
        {
			if(p->arrive_time<tm2->arrive_time)
			{
				p->next=tm2;
				tm1->next=p;
				flag=0;
				break;
			}
			tm1=tm1->next;
			tm2=tm2->next;            
        }
        if(flag)
        {
            tm1->next=p;
            p->next=NULL;
        }
    }
}

input()//進程信息的輸入
{
    int i,num;
    printf("\n 請輸入進程數:");
    scanf("%d",&num);
    for (i=0;i<num;i++)
    {
        printf("\n 進程號：No.%d:\n",i+1);
        p=getpcb(PCB);
        printf("\n 輸入進程名：");
        scanf("%s",p->name);
		printf("\n 輸入進程到達時間：");
		scanf("%d",&p->arrive_time);
        printf("\n 輸入進程運行時間：");
        scanf("%d",&p->total_time);	
        p->run_time=0;
        p->state='w';
        p->next=NULL;
        p->count=0;
        sort();
    }
}

display(PCB *q)//顯示所有進程的狀態
{
    printf("\n name\t state\t arrive_time\t total_time\t run_time\n");
    printf(" %s\t %c\t %d\t\t %d \t\t%d\n",
		q->name,q->state,q->arrive_time,q->total_time,q->run_time);
}

destroy()//撤消進程 
{
    printf("\n 進程[%s]已完成.\n",p->name);
    free(p);
    p=NULL;
}

running()//進程運行
{
    p->count++;
    if(p->count<N)
        p->run_time=p->run_time+p->count;
    else
        p->run_time=p->run_time+N;
    if(p->run_time>=p->total_time)
        destroy();
    else
		p->state='w';
    if(p)
        sort();
}

check()//查看進程的狀態
{
    int i;
    PCB *pr;
    if(p->count<N)
        printf("\n 當前執行的就緒隊列分配的CPU時間片為：%d",p->count+1);
    else
        printf("\n 當前執行的就緒隊列分配的CPU時間片為：%d",N);
    printf("\n 當前正在運行的進程是：%s",p->name);
    display(p);
    for(i=0;i<N-1;i++)
    {
		pr=ready[i];
        printf("\n第%d就緒隊列狀態為：\n",i+1);
        while(pr)
        {
            display(pr);
            pr=pr->next;
        }
    }
    printf("\n第%d就緒隊列狀態為：\n",N);
	pr=ready[N];
    while(pr)
    {
        display(pr);
        pr=pr->next;
    }
}

main()
{//主函數
    int h=0,i;
	system("cls");
	printf("\n模擬進程調度系統——多隊列輪轉法調度算法\n");
    input();
	for(i=0;i<=N;i++)
	{
		while(ready[i])
		{
			getchar();
			h++;
			printf("\n The execute number:%d \n",h);
			p=ready[i];
			ready[i]=p->next ;
			p->next=NULL;
			p->state='R';
			check();
			running();
			printf("\n 按任鍵繼續......");
		}
	}
    printf("\n\n 所有進程已經完成.\n");
}