搜索
1《计算机操作系统》实验题目进程调度模拟程序实验形式小组合作□独立完成□设计目的（1）加深对进程、进程控制块及进程队列等概念的理解。（2）了解优先数和时间片轮转调度算法的具体实施办法，加深对进程管理各部分内容的理解。设计预备知识（1）进程管理。（2）优先数调度算法、时间片轮转算法。设计内容设计一个采用优先数调度算法(按优先数轮转)的模拟进程调度程序。设计具体包括：①确定进程控制块的内容和组织方式；②完成进程创建原语和进程调度原语；③编写程序及对所做工作进行测试。一、设计理论描述进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。另有一种定义方法是“程序在处理器上的执行”。简单地说，进程包括三种状态：运行状态(Running)、就绪状态(Ready)、等待状态或阻塞状态(Blocked)；严格地说，进程除了上面的三个状态，还有挂起就绪(Readya)和挂起等待(Blocked)等状态。进程控制块(PCB)的数据结构来记录进程的属性信息。PCB一般应包含以下信息：进程标识信息(本进程的标志ID、父进程的标志ID、用户标识)；处理机状态信息(用户使用的寄存器、控制和状态寄存器、堆栈指针)；进程调度和控制2信息(进程的状态、进程的调度优先级、程序和数据的地址、进程同步和通信机制、进程已等待时间、已使用的处理器时间、进程在有关队列中的链接指针、分给进程的主存大小和位置、进程使用的其他资源信息、进程得到有关服务的优先级、进程调度所需的其他信息)。进程调度算法：（1）先进先出调度算法(FIFO)：按照进程的到达顺序调度进程，属于不可抢占策略。（2）优先级调度算法：按照进程的优先级大小来调度，是高优先级进程得到优先的处理的调度策略，可使用非抢占或可抢占两种策略。二、设计思想、设计分析及数据结构模型这个设计需要考虑三个问题：如何组织进程、如何创建进程和如何实现处理机调度。考虑如何组织进程，首先就要设置进程控制块的内容。进程控制块PCB记录各个进程执行时的情况。一般操作系统中，无论进程控制块中信息量多少，信息都可以大致分为以下四类：（1）标识信息每个进程都要有一个唯一的标识符，用来标识进程的存在和区别于其他进程。这个标识符是必不可少的，可以用符号或编号实现，它必须是操作系统分配的。在后面给出的参考程序中，采用编号方式，也就是为每个进程依次分配一个不相同的正整数。（2）说明信息用于记录进程的基本情况，例如，进程的状态、等待原因、进程程序存放位置、进程数据存放位置等。设计中，因为进程没有数据和程序，仅使用进程控制块模拟进程，所以这部分内容仅包括进程状态。（3）现场信息现场信息记录各个寄存器的内容。当进程由于某种原因让出处理机时，需要将现场信息记录在进程控制块中，当进行进程调度时，从选中进程的进程控制块中读取现场信息进行现场恢复。现场信息就是处理机的相关寄存器内容，包括通用寄存器、程序计数器和程序状态字寄存器等。在设计中，可选取几个寄存器作为代表。用大写的全局变了量AX、BX、CX、DX模拟通用寄存器，大写的全局变量PC模拟程序计数器，大写的全局变量PSW模拟程序状态字寄3存器。（4）管理信息管理信息记录进程管理和调度的信息。例如进程优先数和进程队列指针等。设计中，仅包括队列指针。因此可将进程控制块结构定义如下：typedefstructnode{charname[10];/*进程标识符*/intprio;/*进程优先数*/intcputime;/*进程占用CPU时间*/intneedtime;/*进程到完成还要的时间*/charstate;/*进程的状态*/structnode*next;/*链指针*/}PCB;PCB*finish,*ready,*run;/*队列指针*/intN;/*进程数*/确定进程控制块内容后，要考虑的就是如何将进程控制块组织在一起。多道程序设计系统，往往同时创建多个进程。在单处理机的情况下，每次只能有一个进程处于运行态，其他的进程处于就绪状态或等待状态。为了便于管理，通常把处于相同状态的进程的进程控制块链接在一起。单处理机系统中，正在运行的进程只有一个，因此，单处理机系统中进程控制块分成一个正在运行进程的进程控制块、就绪进程的进程控制块组织成的就绪队列和等待进程的进程控制块组成的等待队列。由于设计模拟的是进程调度，没有对等待队列的操作，所以设计中只有一个指向正在运行进程的进程控制块指针和一个就绪进程的进程控制块队列指针。操作系统的实现中，系统往往在内存中划分出一个连续的专门区域存放系统的进程控制块，设计中应该用数组模拟这个专门的进程控制块区域，定义如下：#definenl0//假定系统允许进程个数为104structpcbpcbarea[n]；//模拟进程控制块区域的数组这样，进程控制块的链表实际上是数据结构中使用的静态链表。进程控制块的链接方式可以采用单向和双向链表，设计中，进程控制块队列采用单向不循环静态链表。为了管理空闲进程控制块，还应该将空闲控制块链接成一个队列。设计中指向运行进程的进程控制块指针、就绪队列指针和空闲进程控制块队列指针定义如下：intrun；//定义指向正在运行进程的进程控制块的指针{inthead;Inttail;}ready;//定义指向就绪队列的头指针head和尾指针tailIntpfree;//定义指向空闲进程控制块队列的指针以上是如何组织进程，下面考虑如何创建进程。进程创建是一个原语，因此在设计中应该用一个函数实现，进程创建的过程应该包括：(1)申请进程控制块。进程控制块的数量是有限的，如果没有空闲进程控制块，则进程不能创建，如果申请成功才可以执行第二步。(2)申请资源。除了进程控制块外，还需要有必要的资源才能创建进程，如果申请资源不成功，则不能创建进程，并且归还已申请的进程控制块；如果申请成功，则执行第三步，设计无法申请资源，所以模拟程序忽略了申请资源这一步。(3)填写进程控制块。将该进程信息写入进程控制块内，设计中只有进程标识符、进程状态可以填写，每个进程现场信息中的寄存器内容由于没有具体数据而使用进程（模拟进程创建时，需输入进程标识符字，进程标识符本应系统建立，并且是唯一的，输入时注意不要冲突），刚刚创建的进程应该为就绪态，然后转去执行第四步。(4)挂入就绪队列。如果原来就绪队列不为空，则将该进程控制块挂入就绪队列尾部，并修改就绪队列尾部指针：如果原来就绪队列为空，则将就绪队列5的头指针、尾指针均指向该进程控制块，进程创建完成。多道程序设计的系统中，处于就绪态的进程往往是多个，它们都要占用处理机，但是，单处理机系统的处理机只有一个，进程调度就是解决这个处理机竞争问题的。进程调度的任务就是按照某种算法从就绪进程队列中选择一个进程，让它占有处理机。因此进程调度程序就应该包括两部分，一部分是在进程就绪队列中选择一个进程，并将其进程控制块从进程就绪队列中摘下来，另一部分工作就是分配处理机给选中的进程，也就是将指向正在运行进程的进程控制块指针指向该进程的进程控制块，并将该进程的进程控制块信息写入处理机的各个寄存器中。在每次运行调度程序之前，为每个进程任意确定它的“优先数”和“需要运行的时间数”，五个进程按给定的优先数从大到小连成队列，调度总是选队首进程运行。每个进程可有三种状态：R——运行状态（RUN）；W——就绪状态（READY）和F——完成状态（FINISH）。并假定初始状态为就绪状态。PCB结构包括以下信息：进程名、进程优先数（或轮转时间片），进程所占用的CPU时间，进程的状态，当前队列指针等。根据调度算法的不同，PCB结构的内容可以作适当的增删。PCB结构：NAME——进程标识符；PRIO——进程优先数；CPUTIME——进程占用CPU时间；NEEDTIME——进程到完成还需要的CPU时间；STATE——进程的状态；NEXT——链指针。本实验是模拟进程调度程序，被选中的进程并不实际启动运行，进程每执行一次，优先数减3，CPU时间片数加1，进程还需要的时间片数减1。在轮转法中，采用固定时间片，时间片数为2，进程每执行一次，CPU时间片数加2，进程还需要的时间片数减2，并排到就绪队列的尾上。被选中运行的进程，进程状态置为“R”，进程运行一次后，若需要运行时间≠0，进程从运行状态变为就绪状态，状态置为“W”，并按优先数大小插入到队列中，若需要运行时间=0，则把它的状态置为完成状态（F）。若“就绪”状态的进程队列不为空，则重复上面的（4）、（5）执行步骤，直到所有进程运行完毕（都为“完成”状态）。设计的程序中能显示或打印进程控制块的动态变化过程。6三、程序流程图(省略)四、源代码#includestdio.h#includestdlib.h#includestring.h#includeconio.htypedefstructnode{charname[10];/*进程标识符*/intprio;/*进程优先数*/intcputime;/*进程占用CPU时间*/intneedtime;/*进程到完成还要的时间*/charstate;/*进程的状态*/structnode*next;/*链指针*/}PCB;PCB*finish,*ready,*run;/*队列指针*/intN;/*进程数*//*将就绪队列中的第一个进程投入运行*/voidfirstin(){run=ready;/*就绪队列头指针赋值给运行头指针*/run-state='R';/*进程状态变为运行态*/ready=ready-next;/*就绪对列头指针后移到下一进程*/}voidprt1()/*标题输出函数*/{printf(namecputimeneedtimeprioritystate\n);}7voidprt2(PCB*q)/*进程PCB输出*/{printf(%-10s%-10d%-10d%-10d%c\n,q-name,q-cputime,q-needtime,q-prio,q-state);}voidprt()/*输出函数*/{PCB*p;prt1();/*输出标题*/if(run!=NULL)/*如果运行指针不空*/prt2(run);/*输出当前正在运行的PCB*/p=ready;/*输出就绪队列PCB*/while(p!=NULL){prt2(p);p=p-next;}p=finish;/*输出完成队列的PCB*/while(p!=NULL){prt2(p);p=p-next;}getch();/*按任意键继续*/}voidinsert(PCB*q)/*优先数的插入算法*/{PCB*p1,*s,*r;8intb;s=q;/*待插入的PCB指针*/p1=ready;/*就绪队列头指针*/r=p1;/*r做p1的前驱指针*/b=1;while((p1!=NULL)&&b)/*根据优先数确定插入位置*/if(p1-prio=s-prio){r=p1;p1=p1-next;}elseb=0;if(r!=p1)/*如果条件成立说明插入在r与p1之间*/{r-next=s;s-next=p1;}else{s-next=p1;/*否则插入在就绪队列的头*/ready=s;}}voidcreate()/*优先数创建初始PCB信息*/{PCB*p;inti,time;charna[10];9ready=NULL;/*就绪队列头指针*/finish=NULL;/*完成队列头指针*/run=NULL;/*运行队列指针*/printf(Enternameandtimeofprocess\n);/*输入进程标识和所需时间创建PCB*/for(i=1;i=N;i++){p=(PCB*)malloc(sizeof(PCB));scanf(%s,na);scanf(%d,&time);strcpy(p-name,na);p-cputime=0;p-needtime=time;p-state='w';p-prio=50-time;if(ready!=NULL