FCFS先来先服务算法SPN短进程优先算法RR时间片轮转算法.doc

以下算法本人全是在vs2003环境下搞定的，望采纳先来先服务算法：#include#includetypedef struct process_FCFSchar name15;/进程名float arrivetime;/到达时间float servetime;/服务时间float finishtime;/完成时间float roundtime;/周转时间float daiquantime;/带权周转时间struct process_FCFS *link;/结构体指针FCFS; FCFS *p,*q,*head=NULL;struct process_FCFS a100;FCFS inital(struct process_FCFS a,int n);void print(struct process_FCFS a,int n);void Fcfs(struct process_FCFS a,int n);struct process_FCFS *sortarrivetime(struct process_FCFS a,int n);/按到达时间进行冒泡排序struct process_FCFS *sortarrivetime(struct process_FCFS a,int n)int i,j;struct process_FCFS t;int flag;for(i=1;in;i+)flag=0;for(j=0;jaj+1.arrivetime)t=aj;aj=aj+1;aj+1=t;flag=1;/交换if(flag=0)/如果一趟排序中没发生任何交换，则排序结束break;return a;/先来先服务算法void Fcfs(struct process_FCFS a,int n)int i;a0.finishtime=a0.arrivetime+a0.servetime; a0.roundtime=a0.finishtime-a0.arrivetime;a0.daiquantime=a0.roundtime/a0.servetime;for(i=1;in;i+)if(ai.arrivetimeai-1.finishtime)ai.finishtime=ai-1.finishtime+ai.servetime; ai.roundtime=ai.finishtime-ai.arrivetime; ai.daiquantime=ai.roundtime/ai.servetime;elseai.finishtime=ai.arrivetime+ai.servetime; ai.roundtime=ai.finishtime-ai.arrivetime; ai.daiquantime=ai.roundtime/ai.servetime;printf(先来先服务n);print(a,n);void print(struct process_FCFS a,int n)int i;for(i=0;in;i+)printf(进程名：%s,);printf(到达时间：%f,ai.arrivetime);printf(服务时间：%f,ai.servetime);printf(完成时间：%f,ai.finishtime);printf(周转时间：%f,ai.roundtime);printf(带权周转时间：%f,ai.daiquantime);printf(n);/主函数void main()int n,i;printf(请输入有几个进程n);scanf(%d,&n);for(i=0;in;i+)printf(print %d process name:,i+1);scanf(%s,&);printf(arrivetime);scanf(%f,&ai.arrivetime);printf(servetime);scanf(%f,&ai.servetime);*sortarrivetime(a,n);Fcfs(a,n);for(;);短进程优先算法在FCFS算法的基础上添加了一个排序分函数，在下面列出，冒泡排序可以无视掉-。-/按到达时间进行冒泡排序struct process_FCFS *sortarrivetime(struct process_FCFS a,int n)int i,j;struct process_FCFS t;int flag;for(i=1;in;i+)flag=0;for(j=0;jaj+1.arrivetime)t=aj;aj=aj+1;aj+1=t;flag=1;/交换if(flag=0)/如果一趟排序中没发生任何交换，则排序结束break;return a;/根据进程长短排序：struct process_SPN *sortSPN(struct process_SPN a,int n)int time=a0.arrivetime;struct process_SPN t;for(int i=0;in-1;i+)for(int j=i+1;jaj.servetime)t=ai;ai=aj;aj=t;for(int j=i+1;jn;j+)if(ai.arrivetime=time&aj.arrivetimeaj.servetime)t=ai;ai=aj;aj=t;if(ai.arrivetime=time)time=time+ai.servetime;elsetime=ai.arrivetime+ai.servetime;return a;这是一个完整的时间片轮转算法，不过时间片设定为pian=1；其他长度的时间片本人还在努力当中#include#include#includetypedef int QElemType;int MaxNume=100;typedef struct QNodeQElemType data;struct QNode *next;QNode,*QueuePtr;typedef structQueuePtr front;QueuePtr rear;LinkQueue;LinkQueue Queue;typedef struct process_FCFSchar name15;/进程名float arrivetime;/到达时间float servetime;/服务时间float needtime;/剩下需要的服务时间float finishtime;/完成时间float roundtime;/周转时间float daiquantime;/带权周转时间struct process_FCFS *link;/结构体指针FCFS; FCFS *p,*q,*head=NULL;struct process_FCFS a100;float pian=1;float time; int n;/进程个数bool flags=true;/标志小于时间片的时间片有无用过FCFS inital(struct process_FCFS a,int n);void print(struct process_FCFS a,int n);void Fcfs(struct process_FCFS a,int n);struct process_FCFS *sortarrivetime(struct process_FCFS a,int n);bool finished(struct process_FCFS a,int n);int InitQueue(LinkQueue &Q);int DestroyQueue(LinkQueue &Q);int EnQueue(LinkQueue &Q,QElemType e);int RollQueue(LinkQueue &Q);int getNextProcess(struct process_FCFS a,int n,float dTime);int killPian(int t,float timeRemaining,bool flag);struct process_FCFS *sortRR(struct process_FCFS a,int n);int InitQueue(LinkQueue &Q)Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);Q.front-next=NULL;return 1;int DestroyQueue(LinkQueue &Q)while(Q.front)Q.rear=Q.front-next;free(Q.front);Q.front=Q.rear;return 1;int EnQueue(LinkQueue &Q,QElemType e) /增加一个节点到队尾QueuePtr p=(QueuePtr)malloc(sizeof(QNode);if(Q.front =Q.rear )Q.front -next =p;p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return 1; int RollQueue(LinkQueue &Q)QueuePtr p;QElemType e;if(Q.front =Q.rear )return 0;/队列已空p=Q.front-next ;e=p-data ;if(ae.needtime 0)if(p=Q.rear )return 1;elseQ.front-next =p-next ;Q.rear -next =p;p-next =NULL;Q.rear =p;return 1;else if(ae.needtime =0)if(p=Q.rear )Q.front =Q.rear ;return 0;elseQ.front-next =p-next ;free(p);return 1;/if(Q.rear =p)/Q.front =Q.rear ;/free(p);/按到达时间进行冒泡排序struct process_FCFS *sortarrivetime(struct process_FCFS a,int n)int i,j;struct process_FCFS t;int flag;for(i=1;in;i+)flag=0;for(j=0;jaj+1.arrivetime)t=aj;aj=aj+1;aj+1=t;flag=1;/交换if(flag=0)/如果一趟排序中没发生任何交换，则排序结束break;return a;bool finished(struct process_FCFS a,int n)for(int k=0;k0)return false;return true;int killPian(int t,float timeRemaining,bool flag)if(pian0)flags=true;if(at.needtimetimeRemaining)at.needtime=at.needtime-timeRemaining;time=time+timeRemaining;if(flags)pian=1;if(flag)t=getNextProcess(a,n,timeRemaining);return t;else if(at.needtime=timeRemaining)time=time+timeRemaining;at.needtime=0;at.finishtime=time;at.roundtime=time-at.arrivetime;at.daiquantime=at.roundtime/at.servetime;if(flags)pian=1;if(flag)t=getNextProcess(a,n,timeRemaining);return t;else if(at.needtimetimeRemaining)at.finishtime=time+at.needtime;at.roundtime=at.finishtime-at.arrivetime;at.daiquantime=at.roundtime/at.servetime;timeRemaining=timeRemaining-at.needtime;time=time+at.needtime;t=getNextProcess(a,n,timeRemaining+at.needtime);if(flags)pian=1;if(t=-1)return -1;elsekillPian(t,timeRemaining,false);int getNextProcess(struct process_FCFS a,int n,float dTime) /返回下一个运行的进程号for(int l=0;ltime-dTime&al.arrivetime=time)EnQueue(Queue,l);int m=RollQueue(Queue);if(m=0&!finished(a,n) /越过长时间空白for(int r=0;rtime)for(int kk=0;kk=0;kk+)if(time+kk*pianar.arrivetime)break;pian=pian-(ar.arrivetime-time-kk*pian);time=ar.arrivetime;EnQueue(Queue,r);flags=false;else if(m=0&finished(a,n)return -1; /无剩余的需要执行的进程return Queue.front-next-data; struct process_FCFS *sortRR(struct process_FCFS a,int n)time=a0.arrivetime;int q=0;/q=getNextProcess(a,n,0);for(int pp=0;ppn;pp+)if(app.arrivetime=a0.arrivetime )EnQueue(Queue,pp);while(q!=-1)q=killPian(