进程调度算法

进程调度算法：采用最高优先数优先的调度算法（即把处理机分配给优先数最高的进程）和先来先服务算法。 　　每个进程有一个进程控制块（ PCB）表示。进程控制块可以包含如下信息：进程名、优先数、到达时间、需要运行时间、已用CPU时间、进程状态等等。 　　进程的优先数及需要的运行时间可以事先人为地指定（也可以由随机数产生）。进程的到达时间为进程输入的时间。 　　进程的运行时间以时间片为单位进行计算。 　　每个进程的状态可以是就绪 W（Wait）、运行R（Run）、或完成F（Finish）三种状态之一。 　　就绪进程获得 CPU后都只能运行一个时间片。用已占用CPU时间加1来表示。 　　如果运行一个时间片后，进程的已占用 CPU时间已达到所需要的运行时间，则撤消该进程，如果运行一个时间片后进程的已占用CPU时间还未达所需要的运行时间，也就是进程还需要继续运行，此时应将进程的优先数减1（即降低一级），然后把它插入就绪队列等待CPU。 　　每进行一次调度程序都打印一次运行进程、就绪队列、以及各个进程的 PCB，以便进行检查。 　　 重复以上过程，直到所要进程都完成为止。 编写并调试一个模拟的进程调度程序，采用“最高优先数优先”调度算法对五个进程进行调度。 “最高优先数优先”调度算法的基本思想是把CPU分配给就绪队列中优先数最高的进程。 静态优先数是在创建进程时确定的，并在整个进程运行期间不再改变。 动态优先数是指进程的优先数在创建进程时可以给定一个初始值，并且可以按一定原则修改优先数。例如：在进程获得一次CPU后就将其优先数减少1。或者，进程等待的时间超过某一时限时增加其优先数的值，等等 #include "stdafx.h" #define error 0 #define ok 1 #define NULL 0 #include <iostream> using namespace std; enum process_state{W,R,F}; //状态枚举类型 typedef struct PCBNode //PCB结构体 { char name; int priority; int arrive; int demand; int use; process_state state; }PCBNode,*pcb; InitPcb(pcb &L) //初始化PCB指针 { L=(PCBNode*)malloc(sizeof(PCBNode)); if(!L) return error; return ok; } typedef struct PNode //PCB链表结点结构体 { pcb process; struct PNode *next; }PNode; typedef struct //带头结点的PCB链表指针 { PNode* head; }pcblist; InitPcbList(pcblist &L) //初始化PCB链表 { L.head=(PNode*)malloc(sizeof(PNode)); if (L.head) L.head->next=NULL; else return error; return ok; } int pcblistinsert(pcblist &L,pcb e) //PCB链表中插入新的结点 { PNode *p,*s; p=L.head; while (p->next&&e->priority < p->next->process->priority) { p=p->next; } s=(PNode*)malloc(sizeof(PCBNode)); s->process=e; s->next=p->next; p->next=s; return ok; } int main() { pcblist L; InitPcbList(L); pcb x; x=(pcb)malloc(sizeof(PCBNode)); char c,d; int i=1,j; PNode* h; pcb P[5]; for (j=0;j<5;j++) InitPcb(P[j]); cout<<"Please enter the information of the process"<<endl; for (j=0;j<5;j++) { cout<<"进程名:";cin>>P[j]->name; cout<<"优先级:";cin>>P[j]->priority; cout<<"到达时间:";cin>>P[j]->arrive; cout<<"需要运行时间:";cin>>P[j]->demand; P[j]->use=0; P[j]->state=W; /* cout<<"use:";cin>>P[j]->use; cout<<"state:";cin>>(int&)P[j]->state;*/ //枚举类型的输入 cout<<endl; } while (P[0]->state!=F||P[1]->state!=F||P[2]->state!=F||P[3]->state!=F||P[4]->state!=F) { h=L.head; c='a'; for (j=0;j<5;j++) if (P[j]->arrive==i) pcblistinsert(L,P[j]); if(h->next==NULL) { i++; continue; } x=h->next->process; x->state=R; cout<<"------------------------------------------------"<<endl<<endl; cout<<"进程名 优先级 到达时间 需要时间 已用 状态 "<<endl; for (j=0;j<5;j++) { switch (P[j]->state) { case W:d='W';break; case R:d='R';break; case F:d='F';break; } cout<<P[j]->name<<" "<<P[j]->priority<<" "<<P[j]->arrive<<" "<<P[j]->demand<<" "<<P[j]->use<<" "<<d<<endl; } x->priority--; x->use++; if(x->use==x->demand) x->state=F; else x->state=W; L.head=L.head->next; if(x->state!=F) { pcblistinsert(L,x); } i++; //时间片加1 cout<<"按任意键继续"<<endl; c=getchar(); //控制时间片间隔显示 } return 0; }