// 時(shí)間片輪轉(zhuǎn)調(diào)度算法
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>

using namespace std;
enum STATUS {RUN,READY,WAIT,FINISH};

struct PCBNode
{        
    int  processID;              //進(jìn)程ID
    STATUS  status;              //進(jìn)程狀態(tài)
    int  priorityNum;          //優(yōu)先數(shù)
    int  reqTime;             //總的需要運(yùn)行時(shí)間
    int  remainTime;          //剩下需要運(yùn)行時(shí)間
    int  arriveTime;          //進(jìn)入就緒隊(duì)列時(shí)間
    int  startTime;           //開始運(yùn)行時(shí)間
    int  finishTime;          //結(jié)束運(yùn)行時(shí)間
    int  totalTime;           //周轉(zhuǎn)時(shí)間
    float  weightTotalTime;      //帶權(quán)周轉(zhuǎn)時(shí)間    
};

struct QueueNode 
{
    int ID;          //進(jìn)程ID
    struct QueueNode * next;   //隊(duì)列中下一個(gè)進(jìn)程指針
};

struct LinkQueue
{
    QueueNode *head;//隊(duì)首
};
void Fcfs(LinkQueue& Q, int& totalTimeSum, int& weightTotalTimeSum,PCBNode * ProcessTable);
bool RR_Run(LinkQueue& Q,QueueNode* q, QueueNode* p, const int Round,int& currentTime,PCBNode * ProcessTable);
//分配時(shí)間片給q所指進(jìn)程,p為剛退出的進(jìn)程
void RoundRobin(LinkQueue& Q,const int Round, int& totalTimeSum, int& weightTotalTimeSum,PCBNode * ProcessTable);
//時(shí)間片輪轉(zhuǎn)調(diào)度,調(diào)用RR_Run(),時(shí)間片大小設(shè)為Round
void InitialQueue(LinkQueue& Q,PCBNode * ProcessTable,const int processnum);
//初始化就緒隊(duì)列
void Input(PCBNode * ProcessTable, const int processnum);
//從input.txt文件輸入數(shù)據(jù)

int main()
{
    LinkQueue Q;//就緒隊(duì)列
    Q.head = NULL;
    const int processnum = 16;//進(jìn)程數(shù)
    const int Round = 1;      //時(shí)間片大小
    int totalTimeSum = 0;     //周轉(zhuǎn)時(shí)間
    int    WeightTotalTimeSum = 0;//帶權(quán)周轉(zhuǎn)時(shí)間
    PCBNode * ProcessTable=new PCBNode[processnum];   //進(jìn)程表

    Input(ProcessTable, processnum);
    InitialQueue(Q, ProcessTable, processnum);
    RoundRobin(Q, Round, totalTimeSum,WeightTotalTimeSum,ProcessTable);    
    cout<<"時(shí)間片輪調(diào)度的平均周轉(zhuǎn)時(shí)間為:"<<totalTimeSum/processnum<<endl;
    cout<<"時(shí)間片輪調(diào)度的平均帶權(quán)周轉(zhuǎn)時(shí)間為:"<<WeightTotalTimeSum/processnum<<endl;

    Input(ProcessTable, processnum);
    InitialQueue(Q, ProcessTable, processnum);
    Fcfs(Q, totalTimeSum,WeightTotalTimeSum,ProcessTable);
    cout<<"先來先服務(wù)的平均周轉(zhuǎn)時(shí)間為:"<<totalTimeSum/processnum<<endl;
    cout<<"先來先服務(wù)的平均帶權(quán)周轉(zhuǎn)時(shí)間為:"<<WeightTotalTimeSum/processnum<<endl;

    delete [] ProcessTable;
    return 0;
}

void RoundRobin(LinkQueue& Q,const int Round, int& totalTimeSum, int& weightTotalTimeSum,PCBNode * ProcessTable)
{
    totalTimeSum = 0;   //總的周轉(zhuǎn)時(shí)間
    weightTotalTimeSum = 0;//平均周轉(zhuǎn)時(shí)間
    int currentTime = 0;   //當(dāng)前時(shí)間
    QueueNode* p;
    QueueNode* q;
    QueueNode* r;
    bool finish = false;//調(diào)用RR_Run()后,該進(jìn)程是否已經(jīng)做完退出
    
    p = Q.head;
    q = p->next;
    while (q != NULL)//從隊(duì)首開始依次分配時(shí)間片
    {
        do
        {        
            cout<<"**********************"<<endl;
            cout<<"在時(shí)間片"<<(currentTime+1)/Round<<"內(nèi),活動(dòng)進(jìn)程為:  "<<q->ID<<endl;
            cout<<"進(jìn)程"<<q->ID<<" 現(xiàn)在需要的時(shí)間片為:  "<<ProcessTable[q->ID].remainTime<<endl;
            finish = RR_Run(Q, q, p, Round, currentTime, ProcessTable);//分配時(shí)間片給q進(jìn)程
            cout<<endl;
            
            if (!finish)//若是進(jìn)程在本時(shí)間片內(nèi)做完,則跳出do…while循環(huán)
            {            
                if (q->next == NULL) 
                {
                    r = Q.head->next;
                }
                else
                {
                    r = q->next;
                }
            }
            else //否則計(jì)算周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間
            {
                totalTimeSum += ProcessTable[q->ID].totalTime;
                weightTotalTimeSum += ProcessTable[q->ID].weightTotalTime;

                delete q; //從隊(duì)列中刪除q進(jìn)程
                q = p;
            }
        }while (!finish &&  (ProcessTable[r->ID].arriveTime > currentTime + Round));
        //下一個(gè)進(jìn)程很晚才來,則繼續(xù)給當(dāng)前進(jìn)程分配時(shí)間片
        
        p = q;
        q = q->next;

        if (q == NULL && Q.head->next!=NULL)
        {
            p = Q.head;
            q = p->next;
        } 
    } 
    delete Q.head;
    Q.head = NULL;
}

bool RR_Run(LinkQueue& Q,QueueNode* q, QueueNode* p, const int Round,int& currentTime,PCBNode * ProcessTable)
{
    if (ProcessTable[q->ID].remainTime <= Round)//在此時(shí)間片內(nèi)能夠做完,之后退出進(jìn)程調(diào)度
    {
        ProcessTable[q->ID].finishTime = currentTime + ProcessTable[q->ID].remainTime;
        ProcessTable[q->ID].totalTime += ProcessTable[q->ID].remainTime;
        ProcessTable[q->ID].weightTotalTime = ProcessTable[q->ID].totalTime/ProcessTable[q->ID].reqTime;        

        currentTime = ProcessTable[q->ID].finishTime;
        
        p->next = q->next;
        cout<<endl;
        cout<<"進(jìn)程"<<q->ID<<"完成!"<<endl;

        return true;
    }
    else//此時(shí)間片內(nèi)做不完
    {
        ProcessTable[q->ID].remainTime = ProcessTable[q->ID].remainTime - Round;
        ProcessTable[q->ID].totalTime += Round;
        currentTime += Round;
        
        return false;
    }
}


void Fcfs(LinkQueue& Q, int& totalTimeSum, int& weightTotalTimeSum,PCBNode * ProcessTable)
{
    totalTimeSum = 0;
    weightTotalTimeSum = 0;//平均周轉(zhuǎn)時(shí)間
    QueueNode* p;
    QueueNode* q;
    
    p = Q.head->next;
    if (p !=NULL ) 
    {
        ProcessTable[p->ID].startTime = ProcessTable[p->ID].arriveTime;
        ProcessTable[p->ID].finishTime = ProcessTable[p->ID].arriveTime + ProcessTable[p->ID].reqTime;
    }
    
    for(q=p->next; q!=NULL; q=q->next)
    {
        
        if (ProcessTable[q->ID].arriveTime < ProcessTable[p->ID].finishTime)
        {
            ProcessTable[q->ID].startTime = ProcessTable[p->ID].finishTime;
            ProcessTable[q->ID].finishTime = ProcessTable[p->ID].finishTime + ProcessTable[q->ID].reqTime;
        }
        else//下個(gè)進(jìn)程到達(dá)時(shí)間較晚
        {
            ProcessTable[q->ID].startTime = ProcessTable[q->ID].arriveTime;
            ProcessTable[q->ID].finishTime = ProcessTable[q->ID].arriveTime + ProcessTable[q->ID].reqTime;
        }
        p = q;
    }
    
    for(q=Q.head->next; q!=NULL; q=q->next)
    {
        ProcessTable[q->ID].totalTime = ProcessTable[q->ID].finishTime - ProcessTable[q->ID].arriveTime;
        ProcessTable[q->ID].weightTotalTime = ProcessTable[q->ID].totalTime/ProcessTable[q->ID].reqTime;        
        totalTimeSum += ProcessTable[q->ID].totalTime;
        weightTotalTimeSum += ProcessTable[q->ID].weightTotalTime;
    }    
    
    int t = 0;
    for(q=Q.head->next; q!=NULL; q=q->next)
    {
        cout<<"*********************"<<endl;
        while ( t<ProcessTable[q->ID].finishTime )
        {
            cout<<"時(shí)刻"<<t<<":  進(jìn)程"<<q->ID<<"活動(dòng)"<<endl;
            t++;
        }
        if (q->next != NULL)
        {    
            cout<<"時(shí)刻"<<t<<":  進(jìn)程"<<q->ID<<"結(jié)束活動(dòng),開始下一個(gè)進(jìn)程."<<endl;
            cout<<"進(jìn)程"<<q->ID<<"的周轉(zhuǎn)時(shí)間為: "<<ProcessTable[q->ID].totalTime<<endl;
            cout<<"進(jìn)程"<<q->ID<<"的帶權(quán)周轉(zhuǎn)時(shí)間為: "<<ProcessTable[q->ID].weightTotalTime<<endl<<endl;
        }
        else
        {
            cout<<"時(shí)刻"<<t<<":  進(jìn)程"<<q->ID<<"結(jié)束活動(dòng)."<<endl<<endl;
            cout<<"進(jìn)程"<<q->ID<<"的周轉(zhuǎn)時(shí)間為: "<<ProcessTable[q->ID].totalTime<<endl;
            cout<<"進(jìn)程"<<q->ID<<"的帶權(quán)周轉(zhuǎn)時(shí)間為: "<<ProcessTable[q->ID].weightTotalTime<<endl<<endl;            
        }
    }
    cout<<"所有進(jìn)程結(jié)束活動(dòng)."<<endl<<endl;

    p = Q.head;
    for(q=p->next; q!=NULL; q=q->next)
    {
        delete p;
        p = q;
    }
}


void InitialQueue(LinkQueue& Q, PCBNode * ProcessTable,const int processnum)
{
    //初始化
    
    for (int i=0;i<processnum;i++)
    {
        ProcessTable[i].processID=i;
        ProcessTable[i].reqTime=ProcessTable[i].remainTime;
        ProcessTable[i].finishTime=0;
        ProcessTable[i].startTime=0;    
        ProcessTable[i].status=WAIT;
        ProcessTable[i].totalTime=0;
        ProcessTable[i].weightTotalTime=0;        
    }
    
    Q.head = new QueueNode;
    Q.head->next = NULL;
    QueueNode * p;
    QueueNode * q;
    for (i=0;i<processnum;i++)
    {    
        p = new QueueNode;
        p->ID = i;
        p->next = NULL;
        if (i == 0)
        {
            Q.head->next = p;            
        }
        else
            q->next = p;
        
        q = p;
    }
}


void Input(PCBNode * ProcessTable, const int processnum)
{
    FILE *fp;        //讀入線程的相關(guān)內(nèi)容
    if((fp=fopen("input.txt","r"))==NULL)
    {
        cout<<"can not open file!"<<endl;
        exit(0);
    }        
    for(int i=0;i<processnum;i++)
    {
        fscanf(fp,"%d %d %d",&ProcessTable[i].arriveTime,&ProcessTable[i].remainTime,&ProcessTable[i].priorityNum);
    }
    fclose(fp);
}