大作业2单处理器系统的进程调度.pdf

《大作业2单处理器系统的进程调度.pdf》由会员分享，可在线阅读，更多相关《大作业2单处理器系统的进程调度.pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实验二单处理器系统的进程调度-编程实现采用优先数调度算法的进编程实现采用优先数调度算法的进程调度程调度1 1实验目的实验目的加深对进程概念的理解，明确进程和程序的区别；深入了解系统如何组织进程、创建进程；进一步认识如何实现处理器调度。2 2实验预备知识实验预备知识进程的概念；进程的组织方式；进程的创建；进程的调度。3 3实验内容实验内容编写程序完成单处理机系统中的进程调度，要求采用时间片轮转调度算法。实验具体包括：首先确定进程控制块的内容，进程控制块的组成方式；然后完成进程创建原语和进程调度原语；最后编写主函数对所作工作进程测试。4 4提示与讲解提示与讲解这个实验主要要考虑三个问题：如何组织进

2、程、如何创建进程和如何实现处理器调度。考虑如何组织进程，首先就要设定进程控制块的内容。进程控制块PCB 记录各个进程执行时的情况。不同的操作系统，进程控制块记录的信息内容不一样。操作系统功能越强，软件也越庞大，进程控制块记录的内容也就越多。这里的实验只使用了必不可少的信息。一般操作系统中，无论进程控制块中信息量多少，信息都可以大致分为以下四类：标识信息每个进程都要有一个惟一的标识符，用来标识进程的存在和区别于其他进程。这个标识符是必不可少的，可以用符号或编号实现，它必须是操作系统分配的。在后面给出的参考程序中，采用编号方式，也就是为每个进程依次分配一个不相同的正整数。说明信息用于记录进程的基本

3、情况，例如进程的状态、等待原因、进程程序存放位置、进程数据存放位置等等。实验中，因为进程没有数据和程序，仅使用进程控制块模拟进程，所以这部分内容仅包括进程状态。现场信息现场信息记录各个寄存器的内容。当进程由于某种原因让出处理器时，需要将现场信息记录在进程控制块中，当进行进程调度时，从选中进程的进程控制块中读取现场信息进行现场恢复。现场信息就是处理器的相关寄存器内容，包括通用寄存器、程序计数器和程序状态字寄存器等。在实验中，可选取几个寄存器作为代表。用大写的全局变量 AX、BX、CX、DX 模拟通用寄存器、大写的全局变量 PC 模拟程序计数器、大写的全局变量 PSW 模拟程序状态字寄存器。管理信

4、息管理信息记录进程管理和调度的信息。例如进程优先数、进程队列指针等。实验中，仅包括队列指针。因此可将进程控制块结构定义如下：struct pcbint name;int status;/*进程标识符*/*进程状态*/*进程现场信息，通用寄存器内容*/*进程现场信息，程序计数器内容*/*进程现场信息，程序状态字寄存器内容*/*下一个进程控制块的位置*/int ax,bx,cx,dx;int pc;int psw;int next;确定进程控制块内容后，要考虑的就是如何将进程控制块组织在一起。多道程序设计系统中，往往同时创建多个进程。在单处理器的情况下，每次只能有一个进程处于运行态，其他的进程处于

5、就绪状态或等待状态。为了便于管理，通常把处于相同状态的进程的进程控制块链接在一起。单处理器系统中，正在运行的进程只有一个。因此，单处理器系统中进程控制块分成一个正在运行进程的进程控制块、就绪进程的进程控制块组织成的就绪队列和等待进程的进程控制块组成的等待队列。由于实验模拟的是进程调度，没有对等待队列的操作，所以实验中只有一个指向正在运行进程的进程控制块指针和一个就绪进程的进程控制块队列指针。操作系统的实现中，系统往往在主存中划分出一个连续的专门区域存放系统的进程控制块，实验中应该用数组模拟这个专门的进程控制块区域，定义如下：#definen10struct pcbpcbarean;/*假定系统

6、允许进程个数为 10*/*模拟进程控制块区域的数组*/这样，进程控制块的链表实际上是数据结构中使用的静态链表。进程控制块的链接方式可以采用单向和双向链表，实验中，进程控制块队列采用单向不循环静态链表。为了管理空闲进程控制块，还应该将空闲控制块链接成一个队列。实验中采用时间片轮转调度算法，这种算法是将进程控制块按照进入就绪队列的先后次序排成队列。关于就绪队列的操作就是从队头摘下一个进程控制块和从队尾挂入一个进程控制块。因此为就绪队列定义两个指针，一个头指针，指向就绪队列的第一个进程控制块；一个尾指针，指向就绪队列的最后一个进程控制块。实验中指向运行进程的进程控制块指针、就绪队列指针和空闲进程控制

7、块队列指针定义如下：intrun;structinthead;inttail;/*定义指向正在运行进程的进程控制块的指针*/ready;intpfree;/*定义指向就绪队列的头指针 head 和尾指针 tail*/*定义指向空闲进程控制块队列的指针*/以上是如何组织进程，下面考虑如何创建进程。进程创建是一个原语，因此在实验中应该用一个函数实现，进程创建的过程应该包括：申请进程控制块：进程控制块的数量是有限的，如果没有空闲进程控制块，则进程不能创建，如果申请成功才可以执行第步；申请资源：除了进程控制块外，还需要有必要的资源才能创建进程，如果申请资源不成功，则不能创建进程，并且归还已申请的进程控

8、制块；如果申请成功，则执行第三步，实验无法申请资源，所以模拟程序忽略了申请资源这一步；填写进程控制块：将该进程信息写入进程控制块内，实验中只有进程标识符、进程状态可以填写，每个进程现场信息中的寄存器内容由于没有具体数据而使用进程（模拟进程创建时，需输入进程标识符字，进程标识符本应系统建立，并且是惟一的，输入时注意不要冲突），刚刚创建的进程应该为就绪态，然后转去执行第四步；挂入就绪队列：如果原来就绪队列不为空，则将该进程控制块挂入就绪队列尾部，并修改就绪队列尾部指针；如果原来就绪队列为空，则将就绪队列的头指针、尾指针均指向该进程控制块，进程创建完成。进程创建流程图如图 2.2 所示。多道程序设计

9、的系统中，处于就绪态的进程往往是多个，它们都要求占用处理器，可是单处理器系统的处理器只有一个，进程调度就是解决这个处理器竞争问题的。进程调度的任务就是按照某种算法从就绪进程队列中选择一个进程，让它占有处理器。因此进程调度程序就应该包括两部分，一部分是在进程就绪队列中选择一个进程，并将其进程控制块从进程就绪队列中摘下来，另一部分工作就是分配处理器给选中的进程，也就是将指向正在运行进程的进程控制块指针指向该进程的进程控制块，并将该进程的进程控制块信息写入处理器的各个寄存器中。开始Y 空闲进程控制 块队列为空？N取空闲进程控制块队列的第一个i=pfree进程创建失败pfree后移：pfree=pcb

10、areapfree.next填写该进程控制块内容：pcbareai.name=name;pcbareai.status=aready;初始化进程控制块内现场信息；就绪队列为 空？YN挂入就绪队列：pcbareaready.tail.next=i;ready.tail=i;pcbareaready.tail.next=-1;结束图 2.2进程创建流程图挂入就绪队列：ready.head=i;ready.tail=i;pcbareaready.tail.next=-1;实验中采用时间片轮转调度算法。时间片轮转调度算法让就绪进程按就绪的先后次序排成队列，每次总是选择就绪队列中的第一个进程占有处理器，

11、但是规定只能使用一个“时间片”。时间片就是规定进程一次使用处理器的最长时间。实验中采用每个进程都使用相同的不变的时间片。采用时间片轮转调度算法的进程调度流程图如图2.3 所示。完成上述功能后，编写主函数进行测试：首先建立一个就绪队列，手工输入信息建立几个进程；然后进行进程调度；最后将指向正在运行进程的指针指向的进程控制块的内容输出，察看结果。5.5.实验报告实验报告实验报告格式及报告内容：实验题目。（1）程序中使用的数据结构。（2）流程图。（3）附有源程序并附上必要的注释。6.6.参考提示参考提示为便于处理，程序中进程的运行时间以时间片为基本计算单位。1.进程控制块 PCB 的格式为：进程标识

12、数链指针优先数/轮转时间片数占用 CPU 时间片数进程所需时间片数进程状态2.优先数算法：进程就绪链按优先数大小排列，链首首先投入运行。每过一个时间片，运行进程所需运行的时间片数减 1，说明它已运行了一个时间片，优先数也减 3，理由是该进程如果在一个时间片中完成不了，优先数应降低一级。接着比较现行进程和就绪链首进程的优先数，如果仍是现行进程高或者相同，就让现行进程继续运行，否则，调度就绪链的链首进程投入运行。原运行进程再按照其优先数大小插入就绪链，且改变它们对应的进程状态，直至所有进程都运行完各自的时间片数。3.简单轮转法：进程就绪链按各进程进入的先后次序排列，进程每次占用处理机的轮转时间按其

13、重要程度登入进程控制块中的轮转时间片数记录项（相应于优先数法的优先数记录项位置）。每过一个时间片，运行进程占用处理机的时间片数加 1，然后比较占用处理机的时间片数是否与该进程的轮转时间片数相等，若相等说明已到达轮转时间，应将现运行进程排到就绪链末尾，调度链首进程占用处理机，且改变它们的进程状态，直至所有进程完成各自的时间片。4.进程控制块链结构：RUNHEADTAIL1.R3.W5.W2.W其中：RUN 当前运行进程指针；HEAD进程就绪链链首指针；TAIL 进程就绪链链尾指针。#include#includestruct Data char P10;int T;char S;int Q;ty

14、pedef struct PCB struct PCB*next;struct Data sj;JC;JC*Head=new PCB;void insert(JC*p)JC*tem;tem=Head-next;if(Head-next=NULL)Head-next=p;else while(p-sj.Qsj.Q&tem-next!=NULL)tem=tem-next;p-next=tem-next;tem-next=p;void run()JC*p;p=Head-next;cout调用进程sj.P，其优先数为sj.Q其剩余运行时间为sj.Tsj.Q-;p-sj.T-;Head-next=p-n

15、ext;if(p-sj.T=0)p-sj.S=E;p-next=NULL;cout进程sj.P运行结束,其运行状态为sj.Sendl;else insert(p);cout运行后，进程sj.P优先数为sj.Q，剩余运行时间为sj.T运行状态为sj.Sendl;void create(JC*p)p=new JC;coutp-sj.P;coutp-sj.Q;coutp-sj.T;p-sj.S=R;p-next=NULL;insert(p);void main()/JC*Head=new PCB;Head-next=NULL;JC p5;for(int i=0;inext!=NULL)run();cout执行完毕;