采用优先数算法模拟进程调度程序

1、肇庆学院计算机科学与软件学院 操作系统课程设计报告 设计题目：采用优先数算法模拟进程调度程序 完成日期：2008年6月3日 设计题目 米用优先数调度算法的模拟进程调度程序 设计目的 解 m 二 理 的 容 内 分 咅 各 m 二 理 管 程 设计预备知识 O O mi 1Erlp 管 数 程 先 进 优 1 2 z( z( 设计内容 17? o 、Z他 写卸 扁 圧 应 M序 采程 小组成口贝分工 采用优先数算法模拟进程调度程序分析、设计与实现 、设计理论描述 进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。 另有一种定义方法是“程序在处理器上的执行” 。为了模拟的方便，本设

2、计采用 这种定义。 简单地说，进程包括三种状态：运行状态、就绪状态、完成状态。 通常操作系统用一个称为进程控制块（PCB）的数据结构来记录进程的属性信 息。PCB 一般应包含以下信息：进程标识信息（本进程的标志ID、父进程的标志 ID、用户标识）；处理机状态信息（用户使用的寄存器、控制和状态寄存器、堆栈 指针）；进程调度和控制信息 （进程的状态、进程的调度优先级、程序和数据的地 址、进程同步和通信机制、进程已等待时间、已使用的处理器时间、进程在有关 队列中的链接指针、 分给进程的主存大小和位置、 进程使用的其他资源信息、 进 程得到有关服务的优先级、进程调度所需的其他信息 ）。 优先级调度算法

3、： 按照进程的优先级大小来调度， 是高优先级进程得到优先 的处理的调度策略，可使用非抢占或可抢占两种策略。 二、设计思想、设计分析及数据结构模型 这个设计需要考虑两个问题：如何组织进程、如何实现进程模拟调度。 考虑如何组织进程，首先就要设置进程控制块的内容。进程控制块 PCB 记 录各个进程执行时的情况。 不同的操作系统，进程控制块记录的信息内容不一样。 操作系统功能越强， 软件也越庞大， 进程控制块记录的内容也就越多。 这里的设 计只使用了必不可少的信息。一般操作系统中，无论进程控制块中信息量多少， 信息都可以大致分为以下四类： （1）标识信息 每个进程都要有一个唯一的标识符，用来标识进程的

4、存在和区别于其他进 程。这个标识符是必不可少的， 可以用符号或编号实现， 它必须是操作系统分配 的。在后面给出的参考程序中， 采用符号方式， 也就是为每个进程依次分配一个 不相同符号。 （2）说明信息 用于记录进程的基本情况，例如，进程的状态、等待原因、进程程序存放位 置、进程数据存放位置等。设计中，因为进程没有数据和程序，仅使用进程控制 块模拟进程，所以这部分内容仅包括进程状态。 （4）管理信息 管理信息记录进程管理和调度的信息。例如进程优先数和进程队列指针等。 设计中，包括队列指针、进程优先数、已运行时间、还需运行时间。 因此可将进程控制块结构定义如下： Class PCB String

5、proname;/进程标识符 String state;/ 进程状态 Int pri;/ 进程优先数 Int runtime;/进程已运行时间 Int needtime; / 还需要运行时间 PCB *next; /下一个进程控制块的指针 确定进程控制块内容后， 要考虑的就是如何将进程控制块组织在一起。 多道 程序设计系统， 往往同时创建多个进程。 在单处理机的情况下， 每次只能有一个 进程处于运行态， 其他的进程处于就绪状态或等待状态。 为了便于管理， 通常把 处于相同状态的进程的进程控制块链接在一起。 单处理机系统中， 正在运行的进 程只有一个， 因此，单处理机系统中进程控制块分成一个正在

6、运行进程的进程控 制块、就绪进程的进程控制块组织成的就绪队列和等待进程的进程控制块组成的 等待队列。 由于设计模拟的是进程调度， 没有对等待队列的操作， 所以设计中只 有一个指向正在运行进程的进程控制块指针和一个就绪进程的进程控制块队列 指针和一个指向已完成进程的进程控制块队列指针。 这样，进程控制块的链表实际上是数据结构中使用的静态链表。 进程控制块 的链接方式可以采用单向和双向链表， 设计中，进程控制块队列采用单向不循环 静态链表。 在各队列中， 各进程按照进程的优先数进行排列， 队首指向的是优先数最高 的进程，每次向各队列中插入一个进程时都会先按照插入排序法按优先数从高到 低把进程插入到

7、队列的相应位置。 以上是如何组织进程， 下面考虑如何调度进程， 一开始， 调度程序将就绪队 列的队首进程加入到运行队列， 运行一周期后用当前正在运行的进程的优先数与 就绪队列队首进程的优先数对比， 如果当前运行的进程的优先数小于就绪队列队 首的进程，则把当前运行的进程按照按优先数的顺序插入到就绪队列的相应位 置，把就绪队列队首的进程加入到运行队列中。 三、程序流程图 是 结束 延时1秒： 当前运行进程优先数减 1 当前运行进程运行时间加1 当前运行进程还需时间减 1 所需时间是否为 否 是 就绪队列是否为 空？ 否 否 就绪队列队首进程的 优先数是否大于当前 运行进程的优先数? 是 0 ？ 当

8、前运行的进程状态设为就绪.将当前运行 的进程插入就绪队列.将就绪队列的队首进 程插入到运行队列. 四、源代码 #include stdafx.h #include #include #include using namespace std; int n; class PCB public: string procname;/ 进程名 int pri;/ 进程优先数 string state;/ 进程状态 int runtime;/ 进程已运行 CPU 时间 int needOftime;/ 还需要时间 PCB *next;/ 指针 ; PCB *run = NULL;/ 运行队列头指针 PCB

9、 *ready = NULL;/ 就绪队列头指针 PCB *finish = NULL;/ 完成队列头指针 void Dtime(int t) time_t current_time; time_t start_time; time( do time( while(current_time-start_time)next=NULL; cout 当前正在运行的进程： endl; cout 进 程 名 称 t 优 先 数 t 还 需 要 时 间 t 已 运 行 时 间 t 状态 :endl; while(p!=NULL) coutprocnamettpritneedOftimettruntimet

10、t statenext; coutendlendl; cout 当前的就绪队列： endl; cout 进 程 名 称 t 优 先 数 t 还 需 要 时 间 t 已 运 行 时 间 t 状态 :endl; p=ready; while(p!=NULL) coutprocnamettpritneedOftimettruntimett statenext; coutendlendl; cout 当前已经完成的进程： endl; cout 进 程 名 称 t 优 先 数 t 还 需 要 时 间 t 已 运 行 时 间 t 状态 :endl; p=finish; while(p!=NULL) cou

11、tprocnamettpritneedOftimettruntimett statenext; void insert(PCB *p)/ 按 Pri 大小插入就绪队列 PCB *S1,*S2; if(ready=NULL) p-next = NULL; ready = p; else S1 = ready; S2 = S1; while(S1!=NULL) if(S1-pri = p-pri) S2 = S1; S1 = S1-next; else break; if(S2-pri = p-pri) S2-next = p; p-next = S1; else p-next = ready;

12、ready = p; void priority() run = ready; ready = ready-next; run-state = 运行 ; while(run!=NULL) /* 当运行队列不空时，有进程正在运行 */ Dtime(1);/ 延时 1 秒 run-runtime=run-runtime+1; run-needOftime=run-needOftime-1; run-pri=run-pri-1; /* 每运行一次优先数降低 1 个单位 */ if(run-needOftime=0) /* 如所需时间为 0 将其插入完成队列 */ run-state = 完成 ; r

13、un-next = finish; finish = run; run=NULL; /* 运行队列头指针为空 */ if(ready!=NULL) /* 如就绪队列不空 */ run = ready; run-state = 运行 ; ready = ready-next; else if(ready!=NULL) insert(run); run = ready; run-state = 运行 ; ready = ready-next; Prinft(); /* 输出进程 PCB 信息*/ void CTProcessOfPri()/ 创建进程 PCB * Node; string c5=P

14、1,P2,P3,P4,P5; srand(int)time(0); for(int j = 0;j procname=cj; Node-needOftime=1+(int)(15.0*rand()/(RAND_MAX+1.0);/ 为 进 程 随 机 分 配 占 用 CPU 时间 . Node-runtime = 0; Node-state =就绪 ; Node-pri =1+(int)(20.0*rand()/(RAND_MAX+1.0);/ 为进程随机分配优先数 . insert(Node); void main() cout * vvendl; cout * 优先数调度算法 *vvend

15、l; cout vv “* vvendl; cout vv按任意键开始创建进程 vvendl; CTProcessOfPri(); 新建进程 Prinft(); coutvvendl; cout vv按任意键开始运行进程模拟调度程序 vvendl; getchar(); priority。;/运行模拟进程调度。 五、程序运行结果及分析 x C:Doc uments and SettingsAdministrator面processDebugprocess.exe 还需要时间 已运行时间 状态: 进程名 P2 P5 P1 P3 P4 优先数 20 20 16 8 1 还需要时间 8 3 15 8

16、 8 己运行时间 0 0 0 0 0 S-者者者者者 一 .2 *二.2 *二 勰廉完成的进務数 还需要时间 已运行时间 状态: 胺任意键开始运行进程模拟调度程序 c： C:Doc uments and SettingsAdministrator面processDebugprocess.exe 图5.1系统运行的初始画面 麗舔运行叫数 P518 还需要时间 1 已运行时间 进程名 P2 P1 P3 P4 优先数 17 16 8 1 还需要时间 15 8 8 已运行时间 3 0 0 0 勰需完成的进麒数 还需要时间 已运行时间 -I 图5.2按任意键后开始执行的画面 图5.3执行一段时间时的画面 c： C:Doc