实验二_带优先级的时间片轮换的进程调度算法的实现.doc

幻灯片1带优先级的时间片轮换的进程调度算法的实现 幻灯片2一、实验目的（1）掌握进程状态转换过程（2）掌握时间片轮转的进程调度算法；（3）掌握带优先级的进程调度算法幻灯片3二、实验内容（1）自定义PCB的数据结构；（2）使用带优先级的时间片轮转法调度进程，每运行一 个时间片，优先级减半。（3）命令集A）create 随机创建进程，进程的优先级与所需要的时间片随机决定；B）round 执行1次时间片轮转操作，其方法为运行高优先级队列的 第1个，再降低其优先级，插入到相应的队列中。C）ps 查看当前进程状态D）sleep 命令将进程挂起E）awake 命令唤醒1个被挂起的进程F）kill 命令杀死进程G）quit命令退出（4）选用面向对象的编程方法。幻灯片4三、实验原理或算法 本实验结合了进程状态转换、优先级调度、时间片轮转调度三方面的内容，根据进程状态转换图，设置SLEEP命令，将1个进程挂起，AWAKE命令唤醒1个被挂起的进程（从阻塞状态到就绪状态）。1) 优先级 优先级体现了进程的重要程度或紧迫程度，在大多数现代操作系统中，都采用了优先级调度策略。优先级从小到大（如 0-127） 优先级最高，127 最低。在本实验中按数值大小决定优先级，数值大的优先级高。2) 基于时间片调度 将所有的就绪进程按照先来先服务的原则，排成一个队列，每次调度时，将 cpu 分配给队首进程，并令其执行一个时间片。当时间片用完时，由一个计时器发出时钟中断请求，调度程序把此进程终止，把该进程放到队尾。 在该实验中，时间片以 100ms 为单位（实际的要小得多）。在调度过程中，需要通过时间函数检测进程的执行时间，当该进程执行时间时间片大小时，进行调度。幻灯片53) 高优先级调度 优先级高的进程优先得到 cpu，等该进程执行完毕后，另外的进程才能执行。4) 基于时间片的高优先级调度 在调度算法中，只有处于就绪状态的进程才能被调度，调度算法结合了优先级调度和时间片轮转调度算法，约定：从最高优先级队列取第1个就绪状态的进程进行调度，时间片到后降低其优先级（降低一半），然后插入到低优先级队列的尾部，每次调度后，显示进程的状态。幻灯片6l 四、数据结构及符号说明l struct pcb /PCBl int ident;/标识符l int state;/状态 0-就绪，1运行，2堵塞l int pior;/优先级,MAXPIOR为最高优先级*/l int life;/生命期*/l struct pcb *next;/*指针*/l void init()/l int create()/l void ps()/l void awake(int x)/l void kill(int x)/l void process()/对输入命令的处理l void routine()/执行一次调度运行，将最高优先级队列的进程运行1个时间片，并降低其优先级幻灯片7l 六、实验源程序l #include l #include l #include l #define getpch(type) (type*)malloc(sizeof(type)l struct pcbl /* 定义进程控制块PCB */ l char name10; l char state; l int super; l int needtime; l int runtime; l struct pcb* link; l l *ready=NULL,*p; l typedef struct pcb PCB; l int ident;/标识符l int state;/状态 0-就绪，1运行，2堵塞l int pior;/优先级,MAXPIOR为最高优先级*/l int life;/生命期*/l struct pcb *next;/*指针*/l l int create()l l int i=0,pior=0;l struct pcb *p,*q,*s;l while (idlisti!=0&iident=i;l s-state=0;l s-pior=pior;l s-life=1+rand()%20;/进程有生命期假设为120l s-next=NULL;l life=life+(s-life);l 幻灯片9l void sleep(int x)l int i=0,test=0;l struct pcb *p=NULL,*q=NULL;l while(test=0&i!=MAXPIOR)l p=arrayi;l if (i!=MAXPIOR & p=NULL)l l i+;continue;l l while(p!=NULL)l l if (p-ident=x) l l test=1;killtest=1;break;l l else l l q=p;p=p-next;l l l if (test=0) i+;幻灯片10l p=arraypior;/建立同优先级队列（链表）l if (p=NULL)l arraypior=s;l else l l while(p!=NULL)l l q=p;l p=p-next;l l q-next=s;l l printf(success create process id=%d, current process state disp below:n,s-ident);l ps();l /printf(end displayn);l return 1;l l void ps()l int i=0;l struct pcb *p;l for (i=0;iident,p-state,p-pior,p-life);l p=p-next;l l l 幻灯片11l if (i=MAXPIOR) l printf(Invaild process number.);l elsel if (p-state=2)l printf(the process %d has blocked,cannot sleep again!,p-ident);l elsel p-state=2;l ps();l l void awake(int x)l int i=0,test=0;l struct pcb *p=NULL,*q=NULL;l while(test=0&i!=MAXPIOR)l p=arrayi;l if (i!=MAXPIOR & p=NULL)l l i+;continue;l l while(p!=NULL)l l if (p-ident=x) l 幻灯片12l test=1;killtest=1;break;l l else l l q=p;p=p-next;l l l if (test=0) i+;l /*找到X所在指针*/l if (i=MAXPIOR) l printf(Invaild process number.);l elsel if (p-state=0)l printf(the process %d is ready state,cannot awake again!,p-ident);l elsel p-state=0;l ps();l l void kill(int x)l int i=0,test=0;l struct pcb *p=NULL,*q=NULL;l while(test=0&i!=MAXPIOR)l p=arrayi;l 幻灯片13l if (i!=MAXPIOR & p=NULL)l l i+;continue;l l while(p!=NULL)l l if (p-ident=x) l l test=1;killtest=1;break;l l else l l q=p;p=p-next;l l l if (test=0) i+;l /*找到X所在指针*/l if (i=MAXPIOR) l printf(Invaild process number.);l else l l if (p=arrayi) l l arrayi=arrayi-next;l idlistx=0; l free(p);l l else幻灯片14l l q-next=p-next;l idlistx=0;l life=life-(p-life);l free(p);l l l l void process()/对输入命令的处理l int i=0,ii=0;l for (i=0;i=0 & arrayi=NULL)l i=i-;l if (istate!=0) pr=r;r=r-next;l i-;l l while(r=NULL);/从高优先队列中寻找就绪进程以调度它l printf(The one in the hightest piror process will execute 1 quantum.n);l r-state=1; /进程处于运行状态l printf(process id=%d is running.,r-ident);l for (int k=1;k600000;k+)l for(int k1=1;k1pior=(r-pior)/2;l r-state=0; /进程处于就绪状态l if(r-life-QUANTUM0)幻灯片17l l r-life=r-life-QUANTUM; /时间减少QUANTUMl life=life-QUANTUM;l l elsel l life=life-r-life;l r-life=0;l l if (r-life=0)/进程运行完成，KILL它l l printf(the process %d is successful run,and release it!n,r-ident);l kill(r-ident);l l elsel l if (pr=r) /将r结点从原队列中删除l arrayi+1=r-next;l elsel pr-next=r-next;l l t=r-pior; /将r进程加入到相应低优先级队列中的最后l pp=arrayt;l qq=NULL;l while (pp!=NULL)幻灯片18l l qq=pp;pp=pp-next;l l if(qq=NULL) /插入到队尾l arrayt=r;l elsel qq-next=r; l r-next=NULL;l l printf(after.n); l ps();l printf(n 1 quantum successful run!n);l l /*l void main()l init();l printf(Welcome to