采用优先数算法模拟进程调度程序分析.docx

采用优先数算法模拟进程调度程序分析.docx

《采用优先数算法模拟进程调度程序分析.docx》由会员分享，可在线阅读，更多相关《采用优先数算法模拟进程调度程序分析.docx（13页珍藏版）》请在冰点文库上搜索。

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

肇庆学院计算机科学与软件学院

《操作系统》课程设计报告

设计题目：

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

完成日期：

2008年6月3日

设计题目

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

设计形式

小组合作

设计目的

加深对进程概念及进程管理各部分内容的理解

设计预备知识

（1）进程管理。

（2）优先数调度算法。

设计内容

采用动态优先数的方法，编写一进程调度程序模拟程序。

模拟程序只进行相应的调度模拟操作。

小组成员分工

采用优先数算法模拟进程调度程序分析、设计与实现

一、设计理论描述

进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。

另有一种定义方法是“程序在处理器上的执行”。

为了模拟的方便，本设计采用这种定义。

简单地说，进程包括三种状态：

运行状态、就绪状态、完成状态。

通常操作系统用一个称为进程控制块（PCB）的数据结构来记录进程的属性信息。

PCB一般应包含以下信息：

进程标识信息（本进程的标志ID、父进程的标志ID、用户标识）；处理机状态信息（用户使用的寄存器、控制和状态寄存器、堆栈指针）；进程调度和控制信息（进程的状态、进程的调度优先级、程序和数据的地址、进程同步和通信机制、进程已等待时间、已使用的处理器时间、进程在有关队列中的链接指针、分给进程的主存大小和位置、进程使用的其他资源信息、进程得到有关服务的优先级、进程调度所需的其他信息）。

优先级调度算法：

按照进程的优先级大小来调度，是高优先级进程得到优先的处理的调度策略，可使用非抢占或可抢占两种策略。

二、设计思想、设计分析及数据结构模型

这个设计需要考虑两个问题：

如何组织进程、如何实现进程模拟调度。

考虑如何组织进程，首先就要设置进程控制块的内容。

进程控制块PCB记录各个进程执行时的情况。

不同的操作系统，进程控制块记录的信息内容不一样。

操作系统功能越强，软件也越庞大，进程控制块记录的内容也就越多。

这里的设计只使用了必不可少的信息。

一般操作系统中，无论进程控制块中信息量多少，信息都可以大致分为以下四类：

（1）标识信息

每个进程都要有一个唯一的标识符，用来标识进程的存在和区别于其他进程。

这个标识符是必不可少的，可以用符号或编号实现，它必须是操作系统分配的。

在后面给出的参考程序中，采用符号方式，也就是为每个进程依次分配一个不相同符号。

（2）说明信息

用于记录进程的基本情况，例如，进程的状态、等待原因、进程程序存放位置、进程数据存放位置等。

设计中，因为进程没有数据和程序，仅使用进程控制块模拟进程，所以这部分内容仅包括进程状态。

（4）管理信息

管理信息记录进程管理和调度的信息。

例如进程优先数和进程队列指针等。

设计中，包括队列指针、进程优先数、已运行时间、还需运行时间。

因此可将进程控制块结构定义如下：

ClassPCB

{

Stringproname;//进程标识符

Stringstate;//进程状态

Intpri;//进程优先数

Intruntime;//进程已运行时间

Intneedtime;//还需要运行时间

PCB*next;//下一个进程控制块的指针

}

确定进程控制块内容后，要考虑的就是如何将进程控制块组织在一起。

多道程序设计系统，往往同时创建多个进程。

在单处理机的情况下，每次只能有一个进程处于运行态，其他的进程处于就绪状态或等待状态。

为了便于管理，通常把处于相同状态的进程的进程控制块链接在一起。

单处理机系统中，正在运行的进程只有一个，因此，单处理机系统中进程控制块分成一个正在运行进程的进程控制块、就绪进程的进程控制块组织成的就绪队列和等待进程的进程控制块组成的等待队列。

由于设计模拟的是进程调度，没有对等待队列的操作，所以设计中只有一个指向正在运行进程的进程控制块指针和一个就绪进程的进程控制块队列指针和一个指向已完成进程的进程控制块队列指针。

这样，进程控制块的链表实际上是数据结构中使用的静态链表。

进程控制块的链接方式可以采用单向和双向链表，设计中，进程控制块队列采用单向不循环静态链表。

在各队列中，各进程按照进程的优先数进行排列，队首指向的是优先数最高的进程，每次向各队列中插入一个进程时都会先按照插入排序法按优先数从高到低把进程插入到队列的相应位置。

以上是如何组织进程，下面考虑如何调度进程，一开始，调度程序将就绪队列的队首进程加入到运行队列，运行一周期后用当前正在运行的进程的优先数与就绪队列队首进程的优先数对比，如果当前运行的进程的优先数小于就绪队列队首的进程，则把当前运行的进程按照按优先数的顺序插入到就绪队列的相应位置，把就绪队列队首的进程加入到运行队列中。

三、程序流程图

四、源代码

#include"stdafx.h"

#include

#include

#include

usingnamespacestd;

intn;

classPCB

{

public:

stringprocname;//进程名

intpri;//进程优先数

stringstate;//进程状态

intruntime;//进程已运行CPU时间

intneedOftime;//还需要时间

PCB*next;//指针

};

PCB*run=NULL;//运行队列头指针

PCB*ready=NULL;//就绪队列头指针

PCB*finish=NULL;//完成队列头指针

voidDtime（intt）

{

time_tcurrent_time;

time_tstart_time;

time（&start_time）;

do

{

time（¤t_time）;

}while（（current_time-start_time）

}

voidPrinft（）

{

PCB*p;

system（"cls"）;//清屏

p=run;

if（p!

=NULL）

{

p->next=NULL;

}

cout<<"当前正在运行的进程：

"<

cout<<"进程名称"<<"\t"<<"优先数"<<"\t"<<"还需要时间"<<"\t"<<"已运行时间"<<"\t"<<"状态:

"<

while（p!

=NULL）

{

cout<procname<<"\t\t"<pri<<"\t"<needOftime<<"\t\t"<runtime<<"\t\t"<state<

p=p->next;

}

cout<

cout<<"当前的就绪队列：

"<

cout<<"进程名称"<<"\t"<<"优先数"<<"\t"<<"还需要时间"<<"\t"<<"已运行时间"<<"\t"<<"状态:

"<

p=ready;

while（p!

=NULL）

{

cout<procname<<"\t\t"<pri<<"\t"<needOftime<<"\t\t"<runtime<<"\t\t"<state<

p=p->next;

}

cout<

cout<<"当前已经完成的进程：

"<

cout<<"进程名称"<<"\t"<<"优先数"<<"\t"<<"还需要时间"<<"\t"<<"已运行时间"<<"\t"<<"状态:

"<

p=finish;

while（p!

=NULL）

{

cout<procname<<"\t\t"<pri<<"\t"<needOftime<<"\t\t"<runtime<<"\t\t"<state<

p=p->next;

}

}

voidinsert（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;

ready=p;

}

}

}

voidpriority（）

{

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="完成";

run->next=finish;

finish=run;

run=NULL;/*运行队列头指针为空*/

if（ready!

=NULL）/*如就绪队列不空*/

{

run=ready;

run->state="运行";

ready=ready->next;

}

}

elseif（（ready!

=NULL）&&（run->pripri））

{

run->state="就绪";

insert（run）;

run=ready;

run->state="运行";

ready=ready->next;

}

Prinft（）;/*输出进程PCB信息*/

}

}

voidCTProcessOfPri（）//创建进程

{

PCB*Node;

stringc[5]={"P1","P2","P3","P4","P5"};

srand（（int）time（0））;

for（intj=0;j<5;j++）

{

Node=newPCB;

if（Node==NULL）

{

return;

}

else

{

Node->procname=c[j];

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）;

}

}

voidmain（）

{

cout<<"*******************************************"<

cout<<"*优先数调度算法*"<

cout<<"*******************************************"<

cout<<"按任意键开始创建进程……"<

CTProcessOfPri（）;//新建进程

Prinft（）;

cout<

cout<<"按任意键开始运行进程模拟调度程序……"<

getchar（）;

priority（）;//运行模拟进程调度。

}

五、程序运行结果及分析

图5.1系统运行的初始画面

图5.2按任意键后开始执行的画面

图5.3执行一段时间时的画面

图5.4执行完毕后的画面

六、课程设计心得与体会（包括对课程设计的改进建议）

附录