时间片轮转调度算法.doc

/ 时间片轮转调度算法 #include #include #include #include using namespace std; enum STATUS RUN,READY,WAIT,FINISH; struct PCBNode int processID; /进程ID STATUS status; /进程状态 int priorityNum; /优先数 int reqTime; /总的需要运行时间 int remainTime; /剩下需要运行时间 int arriveTime; /进入就绪队列时间 int startTime; /开始运行时间 int finishTime; /结束运行时间 int totalTime; /周转时间 float weightTotalTime; /带权周转时间 ; struct QueueNode int ID; /进程ID struct QueueNode * next; /队列中下一个进程指针 ; struct LinkQueue QueueNode *head;/队首 ; 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); /分配时间片给q所指进程,p为刚退出的进程 void RoundRobin(LinkQueue& Q,const int Round, int& totalTimeSum, int& weightTotalTimeSum,PCBNode * ProcessTable); /时间片轮转调度,调用RR_Run(),时间片大小设为Round void InitialQueue(LinkQueue& Q,PCBNode * ProcessTable,const int processnum); /初始化就绪队列 void Input(PCBNode * ProcessTable, const int processnum); /从input.txt文件输入数据 int main() LinkQueue Q;/就绪队列 Q.head = NULL; const int processnum = 16;/进程数 const int Round = 1; /时间片大小 int totalTimeSum = 0; /周转时间 int WeightTotalTimeSum = 0;/带权周转时间 PCBNode * ProcessTable=new PCBNodeprocessnum; /进程表 Input(ProcessTable, processnum); InitialQueue(Q, ProcessTable, processnum); RoundRobin(Q, Round, totalTimeSum,WeightTotalTimeSum,ProcessTable); cout 时间片轮调度的平均周转时间为: totalTimeSum/processnum endl; cout 时间片轮调度的平均带权周转时间为: WeightTotalTimeSum/processnum endl; Input(ProcessTable, processnum); InitialQueue(Q, ProcessTable, processnum); Fcfs(Q, totalTimeSum,WeightTotalTimeSum,ProcessTable); cout 先来先服务的平均周转时间为: totalTimeSum/processnum endl; cout 先来先服务的平均带权周转时间为: WeightTotalTimeSum/processnum next; while (q != NULL)/从队首开始依次分配时间片 do cout * endl; cout 在时间片 (currentTime+1)/Round 内,活动进程为: ID endl; cout 进程 ID 现在需要的时间片为: ID.remainTime endl; finish = RR_Run(Q, q, p, Round, currentTime, ProcessTable);/分配时间片给q进程 cout next = NULL) r = Q.head- next; else r = q- next; else /否则计算周转时间和带权周转时间 totalTimeSum += ProcessTableq- ID.totalTime; weightTotalTimeSum += ProcessTableq- ID.weightTotalTime; delete q; /从队列中删除q进程 q = p; while (!finish & (ProcessTabler- ID.arriveTime currentTime + Round); /下一个进程很晚才来,则继续给当前进程分配时间片 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 (ProcessTableq- ID.remainTime ID.finishTime = currentTime + ProcessTableq- ID.remainTime; ProcessTableq- ID.totalTime += ProcessTableq- ID.remainTime; ProcessTableq- ID.weightTotalTime = ProcessTableq- ID.totalTime/ProcessTableq- ID.reqTime; currentTime = ProcessTableq- ID.finishTime; p- next = q- next; cout endl; cout 进程 ID 完成! ID.remainTime = ProcessTableq- ID.remainTime - Round; ProcessTableq- ID.totalTime += Round; currentTime += Round; return false; void Fcfs(LinkQueue& Q, int& totalTimeSum, int& weightTotalTimeSum,PCBNode * ProcessTable) totalTimeSum = 0; weightTotalTimeSum = 0;/平均周转时间 QueueNode* p; QueueNode* q; p = Q.head- next; if (p !=NULL ) ProcessTablep- ID.startTime = ProcessTablep- ID.arriveTime; ProcessTablep- ID.finishTime = ProcessTablep- ID.arriveTime + ProcessTablep- ID.reqTime; for(q=p- next; q!=NULL; q=q- next) if (ProcessTableq- ID.arriveTime ID.finishTime) ProcessTableq- ID.startTime = ProcessTablep- ID.finishTime; ProcessTableq- ID.finishTime = ProcessTablep- ID.finishTime + ProcessTableq- ID.reqTime; else/下个进程到达时间较晚 ProcessTableq- ID.startTime = ProcessTableq- ID.arriveTime; ProcessTableq- ID.finishTime = ProcessTableq- ID.arriveTime + ProcessTableq- ID.reqTime; p = q; for(q=Q.head- next; q!=NULL; q=q- next) ProcessTableq- ID.totalTime = ProcessTableq- ID.finishTime - ProcessTableq- ID.arriveTime; ProcessTableq- ID.weightTotalTime = ProcessTableq- ID.totalTime/ProcessTableq- ID.reqTime; totalTimeSum += ProcessTableq- ID.totalTime; weightTotalTimeSum += ProcessTableq- ID.weightTotalTime; int t = 0; for(q=Q.head- next; q!=NULL; q=q- next) cout * endl; while ( t ID.finishTime ) cout 时刻 t : 进程 ID 活动 next != NULL) cout 时刻 t : 进程 ID 结束活动,开始下一个进程. endl; cout 进程 ID 的周转时间为: ID.totalTime endl; cout 进程 ID 的带权周转时间为: ID.weightTotalTime endl endl; else cout 时刻 t : 进程 ID 结束活动. endl endl; cout 进程 ID 的周转时间为: ID.totalTime endl; cout 进程 ID 的带权周转时间为: ID.weightTotalTime endl endl; cout 所有进程结束活动. endl next; q!=NULL; q=q- next) delete p; p = q; void InitialQueue(LinkQueue& Q, PCBNode * ProcessTable,const int processnum) /初始化 for (int i=0;i next = NULL; QueueNode * p; QueueNode * q; for (i=0;i 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; /读入线程的相关内容 if(fp=fopen( input.txt , r )=NULL) cout can not open file! endl; exit(0); for(int i=0;i processnum;