进程管理及调度的算法.doc

进程管理与调度的算法实现一、 实验目的进程调度是处理机管理的核心内容。本设计要求用高级语言编写与调试一个简单的进程调度程序。通过本实验可以加深理解有关进程控制块、进程队列的概念，并体会与了解优先权调度算法与时间片轮转调度算法的具体实施办法。二、 实验内容1 设计进程控制块PCB表结构，分别适用于优先权调度算法与时间片轮转调度算法。2 PCB结构包括以下信息：进程名、进程优先数（或轮转时间片），进程所占用的CPU时间，进程的状态，当前队列指针等。根据调度算法的不同，PCB结构的内容可以作适当的增删。3 建立进程就绪队列。对两种不同算法编制入链子程序。4 编制两种进程调度算法：a）优先数调度；b）时间片轮转调度。允许用户在程序运行时选择使用某一种调度算法。三、 编程工具：C、Java、VC或其它可视化语言平台任选四、 具体设计要求及有关说明选用优先数算法与简单时间片轮转法对五个进程进行调度，每个进程可有三种状态：运行状态（RUN）、就绪状态（READY）与完成状态。并假定初始状态为就绪状态。1 设计进程控制块PCB结构如下：NAME/进程标识符；PRIO/ROUND/ PRIO表示进程优先数，ROUND表示进程轮转时间片大小；CPUTIME/进程占用CPU时间；COUNT/计数器；NEEDTIME/进程到完成还要的CPU时间；STATE/进程的状态；NEXT/链指针2 进程控制块链结构如图所示。READYFINISHRUNTAIL其中：RUN当前运行进程指针；READY就绪队列头指针；TAIL就绪队列尾指针；FINISH完成队列头指针。为了便于处理，程序中进程的运行时间以时间片为单位计算。各进程的优先数或轮转时间片数以及进程需运行的时间片数的初值均由用户给定。3 程序说明：a）在优先数算法中，进程每执行一次，优先数减3，CPU时间片数加1，进程还需要的时间片数减1。在轮转法中，采用固定时间片，时间片数为2，进程每执行一次，CPU时间片数加2，进程还需要的时间片数减2，并排到就绪队列的尾上。b）程序结构说明如下：整个程序由CREATE，FIRSTIN，INSERT1，INSERT2，PRINT，PRISCH与ROUNDSCH过程组成。其中：CREATE的功能是创建新的进程，即创立进程的PCB，并将此PCB链入到就绪队列中去。FIRSTIN的功能是将就绪队列中的第一个进程投入运行。INSERT1的功能是把还未完成且优先数小于别的进程PCB按进程优先数的顺序插入到就绪队列中。INSERT2是轮转法使用的过程，将执行了一个单位时间片数（为2）且还未完成的进程的PCB插入到就绪队列的队尾。PRINT打印每执行一次后的所有进程的状态，这里，就绪（等待）用“W”代表。PRISCH按优先数算法调度进程。ROUNDSCH按时间片轮转法调度进程。c）主程序中定义了PCB的结构与其它变量NUMBER进程数，ALGO为10个字符长的字符串，存放要求输入的算法的名，输入“PRIORITY”表示调用优先数算法，输入“ROUNDROBIN”表示调用循环轮转法，要求用户在程序运行时输入其中的一个。实现代码：#includeiostream #includestring #includecstring #includeiomanip using namespace std; #define N 50 /函数声明 void CREATE(); void INSERT1(struct PCB *,int); void INSERT2(struct PCB *); void INSERT3(struct PCB *); void FIRSTIN(); void PRISCH(); void ROUNDSCH(); void PRINT(); /定义进程PCB struct PCB char NAMEN; int PRIO; int ROUND; int CPUTIME; int COUNT; int NEEDTIME; char STATE; struct PCB *NEXT; ; struct PCB *READY,*TAIL,*RUN,*FINISH; int number; string ALGO; /主函数 int main() string name; int j=0; READY=NULL;TAIL=NULL;RUN=NULL;FINISH=NULL; /初始化各队列 loop: cout*endl; cout* 进程管理与调度 *endl; cout* PRIORITY (优先数法) *endl; cout* ROUNDROBIN (轮转法) *endl; cout* EXIT(退出) *endl; cout*endl; coutALGO; if(ALGO=priority|ALGO=PRIORITY|ALGO=roundrobin|ALGO=ROUNDROBIN) CREATE(); /创建进程PCB cin.get(); /吸收回车符 if(ALGO=priority|ALGO=PRIORITY) PRISCH(); /按优先数法调度进程 else ROUNDSCH(); /按时间片轮转法调度进程 else if(ALGO=exit|ALGO=EXIT) cout退出程序！endl; exit(0); /退出程序 else coutendl输入错误！请重新输入.endlPRIONEXT=READY; READY=q; else pt=READY; while(pt-NEXT!=NULL&pt-NEXT-PRIO=prio) pt=pt-NEXT; if(pt-NEXT=NULL) pt-NEXT=q; TAIL=q; q-NEXT=NULL; else q-NEXT=pt-NEXT; pt-NEXT=q; /按顺序将进程插入到队列队尾 void INSERT2(struct PCB *q) struct PCB *pt; pt=READY; while(pt-NEXT!=NULL) pt=pt-NEXT; pt-NEXT=q; q-NEXT=NULL; /TAIL=q-NEXT; /按顺序将进程插入到完成队列队尾 void INSERT3(struct PCB *q) struct PCB *pt; if(FINISH!=NULL) pt=FINISH; while(pt-NEXT!=NULL) pt=pt-NEXT; pt-NEXT=q; q-NEXT=NULL; else q-NEXT=FINISH; FINISH=q; FINISH-NEXT=NULL; /创建进程PCB void CREATE() struct PCB *p; int i; char nameN; int prio; int round; int needtime; int cputime; coutnumber; /按优先数创建进程 if(ALGO=priority|ALGO=PRIORITY) int k=0; for(i=0;inumber;i+) p=(struct PCB *)malloc(sizeof(struct PCB); cout请输入进程i+1名称(以#结束)：; for(k=0;knamek; if(namek=#)break; namek=0; strcpy(p-NAME,name); coutprio; p-PRIO=prio; coutneedtime; p-NEEDTIME=needtime; coutcputime; p-CPUTIME=cputime; p-COUNT=0; p-STATE=W; if(READY!=NULL)INSERT1(p,p-PRIO); else p-NEXT=READY; READY=p; READY-NEXT=NULL; TAIL=p; /按时间片创建进程 if(ALGO=roundrobin|ALGO=ROUNDROBIN) int k=0; for(i=0;inumber;i+) p=(struct PCB *)malloc(sizeof(struct PCB); cout请输入进程i+1名称(以#结束)：; for(k=0;knamek; if(namek=#)break; namek=0; strcpy(p-NAME,name); coutneedtime; p-NEEDTIME=needtime; coutround; p-ROUND=round; p-COUNT=0; p-STATE=W; p-CPUTIME=round; if(READY!=NULL)INSERT2(p); else p-NEXT=READY; READY=p; READY-NEXT=NULL; TAIL=p; /将就绪队列第一个进程投入运行 void FIRSTIN() RUN=READY; RUN-STATE=R; READY=READY-NEXT; /打印进程信息 void PRINT() struct PCB *pt; if(ALGO=priority|ALGO=PRIORITY) coutsetw(12)namesetw(10)countsetw(10)cputimesetw(10)needtime; coutsetw(9)priosetw(9)stateendl; if(RUN!=NULL) coutsetw(12)NAMEsetw(9)COUNTsetw(8)CPUTIMEsetw(11)NEEDTIME; coutsetw(9)PRIOsetw(9)STATEendl; pt=READY; while(pt!=NULL) coutsetw(12)NAMEsetw(9)COUNTsetw(8)CPUTIMEsetw(11)NEEDTIME; coutsetw(9)PRIOsetw(9)STATENEXT; pt=FINISH; while(pt!=NULL) coutsetw(12)NAMEsetw(9)COUNTsetw(8)CPUTIMEsetw(11)NEEDTIME; coutsetw(9)PRIOsetw(9)STATENEXT; if(ALGO=roundrobin|ALGO=ROUNDROBIN) coutsetw(12)namesetw(9)countsetw(10)cputimesetw(10)needtime; coutsetw(9)roundsetw(9)stateendl; if(RUN!=NULL) coutsetw(12)NAMEsetw(8)COUNTsetw(9)CPUTIMEsetw(10)NEEDTIME; coutsetw(10)ROUNDsetw(9)STATEendl; pt=READY; while(pt!=NULL) coutsetw(12)NAMEsetw(8)COUNTsetw(9)CPUTIMEsetw(10)NEEDTIME; coutsetw(10)ROUNDsetw(9)STATENEXT; pt=FINISH; while(pt!=NULL) coutsetw(12)NAMEsetw(8)COUNTsetw(9)CPUTIMEsetw(10)NEEDTIME; coutsetw(10)ROUNDsetw(9)STATENEXT; coutendlpress any key to continue.endl; cin.get(); /按优先数法调度进程 void PRISCH() coutendl开始状态.PRIO=RUN-PRIO-3; RUN-NEEDTIME=RUN-NEEDTIME-RUN-CPUTIME; RUN-CPUTIME=RUN-CPUTIME+1; RUN-COUNT=RUN-COUNT+1; PRINT(); if(RUN-NEEDTIME=0) RUN-STATE=F; INSERT3(RUN); RUN=NULL; else RUN-STATE=W; if(READY!=NULL)INSERT1(RUN,RUN-PRIO); else RUN-NEXT=READY; READY=RUN; RUN-NEXT=NULL; RUN=NULL; cout任务已完成.endl; PRINT(); /按时间片轮转法调度进程 void ROUNDSCH() coutendl开始状态.C