操作系统课程设计-莫黎

课 程 设 计 报 告

课程名称 操作系统 课题名称 进程调度算法的设计

专 业 通信工程 班 级 1101 学 号 201103020135 姓 名 莫 黎 指导教师 颜国风

2014年 6 月 29 日

湖南工程学院 课 程 设 计 任 务 书

课程名称 操作系统 课 题 进程调度算法的设计

专业班级 通信1101 学生姓名 莫 黎 学 号 201103020135 指导老师 颜国风 审 批

任务书下达日期 2014 年 6 月 23 日 任务完成日期 2014 年 6 月 29 日

1设计内容与设计要求

1.1设计内容

1.1.1 进程调度算法的设计 ● 设计要求：

①设计进程控制块PCB表结构，分别适用于优先数调度算法和循环轮转调度算法。

②建立进程就绪队列。对两种不同算法编制入链子程序。 ③编制两种进程调度算法：1）优先数调度；2）循环轮转调度 ● 设计技术参数:

①本程序用两种算法对五个进程进行调度，每个进程可有三个状态，并假设初始状态为就绪状态。

②为了便于处理，程序中的某进程运行时间以时间片为单位计算。各进程的优先数或轮转时间数以及进程需运行的时间片数的初始值均由用户给定。

③在优先数算法中，优先数的值为50与运行时间的差值，即P_TIME-process->needtime。进程每执行一次，优先数减3，CPU时间片数加1，进程还需要的时间片数减1。在轮转算法中，采用固定时间片（即：每执行一次进程，该进程的执行时间片数为已执行了2个单位），这时，CPU时间片数加2，进程还需要的时间片数减2，并排列到就绪队列的尾上。

④对于遇到优先数一致的情况，采用FIFO策略解决。 1.1.2 银行家算法设计 ● 设计要求：

编制银行家算法通用程序，并检测所给状态的系统安全性。设进程I提出请求Request[N]，则银行家算法按如下规则进行判断。

(1)如果Request[N]<=NEED[I，N]，则转(2)；否则，出错。 (2)如果Request[N]<=AVAILABLE，则转(3)；否则，出错。 (3)系统试探分配资源，修改相关数据： AVAILABLE=AVAILABLE-REQUEST ALLOCATION=ALLOCATION+REQUEST NEED=NEED-REQUEST

(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。 ● 设计技术参数：

假设有n个进程m类资源，则有如下数据结构：

可利用资源向量Available。这是一个含有m个 元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。Available[j]=K，则表示系统中现有Rj 类资源K个。

最大需求矩阵Max。这是一个n*m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i，j]=K，则表示进程i需要Rj类资源的最大数目为K。

分配矩阵Allocation。这也是一个n*m的矩阵，它定义了系统中每一类资源 当前已分配给每一进程的资源数。如果Allocation[i，j]=K，则表示 进程i当前已分得Rj类资源的数目为K。

需求矩阵Need。这也是一个n*m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i，j]=K，则表示进程i还需要Rj类资源K个，方能完成其任务。

上述三个矩阵存在如下关系：Need[i,j]= Max[i，j]- Allocation[i，j]。 1.1.3页面置换算法模拟设计 ● 设计要求：

计算并输出下述各种算法在不同内存容量下的命中率。

A. FIFO先进先出的算法 B. LRR最近最少使用算法

C. OPT最佳淘汰算法（先淘汰最不常用的页地址） D. LFR最少访问页面算法 E. NUR最近最不经常使用算法

● 设计技术参数：

（1）命中率=1-页面失效次数/页地址流长度

（2）本实验中，页地址流长度为320，页面失效次数为每次访问相应指令时，该指令所对应的页不在内存的次数。

（3）随机数产生方法，采用系统提供函数SRAND()和RAND ()来产生

● 实验过程：

(1)．过随机数产生一个指令序列，共320条指令，具体的实施方法是： A. [0，319]的指令地址之间随机选取一起点M; B. 顺序执行一条指令，即执行地址为M+1的指令；

C. 在前地址[0，M+1]中随机选取一条指令并执行，该指令的地址为M’;

D. 顺序执行一条指令，其地址为M’+1；

E. 在后地址[M‘+2，319]中随机选取一条指令并执行； F. 重复A—E，直到执行320次指令。 (2)．指令序列变换成页地址流，设：

① 页面大小为1K；

② 用户内存容量为4页到32页； ③ 用户虚存容量为32K。

在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：

第0条—第9条指令为第0页（对应虚存地址为[0，9]）； 第10条—第19条指令为第1页（对应虚存地址为[10，19]）； 。。。。。。。。。。。。。。。。。。。。。

第310条—第319条指令为第31页（对应虚存地址为[310，319]）； 按以上方式，用户指令可组成32页。

(3). 计算并输出下述各种算法在不同内存容量下的命中率。 1.1.4 作业调度模拟 ● 设计要求：

① 加深对作业概念地理解。 ② 掌握短作业优先调度算法。

③ 深入了解批处理系统如何组织作业、管理作业和调度作业。 ④ 了解作业控制块的作用，以及作业控制块的内容和组织方式。 ● 设计技术参数：

① 利用作业控制块将系统中的作业组织起来；

为了将系统中的作业组织起来，需要为每个进入系统的作业建立档案以记录和作业相关的信息，例如作业名、作业所需要的资源、作业执行的时、作业进入系统的时间、作业信息在存储器中的位置、指向下一个作业控制块的指针等信息。这个记录作业相关信息的数据块称为作业控制块（JCB）,并将系统中等待作业调度的作业控制块组织成一个队列，这个队列称为后备队列。当一个作业全部信息进入系统后，就为其建立作业控制块，并挂入后备队列中。当一个作业全部进入系统后，就为其建立作业控制块，并挂入后备队列中。当进行作业调度时，从后备队列中查找选择作业。

② 利用短作业优先算法进行作业调度；

在从后备队列中查找选择作业时，先根据作业控制块中的信息，选中一个短作业，也就是执行时间最短的作业，将它们调入内存运行。 1.1.5 临界区资源模拟 ● 设计要求：

建立三个进程，模拟进入临界区，然后用一个进程进行管理。 ● 设计技术参数:

① 实现UP、DOWN原语

② 产生3个进程，两个进程模拟需要进入临界区的用户进程。

当需要进入临界区时，显示：“进程x请求进入临界区?”，同时向管理进程提出申请；申请返回，表示进入了临界区。在临界区中等待一段随机时间，并显示：“进程x正在临界区?”；当时间结束，显示：“进程x退出临界区?”,同时向管理进程提出退出申请；

当申请返回，显示：“进程x已退出临界区。”

③ 一个进程作为原语的管理进程，接受其他进程的临界区进入请求： 如果允许进入，则根据DOWN 原语的操作步骤设置相应变量，然后返回； 如果不允许进入，则进入循环等待，直到允许为止； 退出时模拟UP 操作。

④ 进程间通信可以采用信号、消息传递、管道或网络通信方式。

1.2 选题方案：

所选题目根据学号确定，学号模5加1，即（学号%5+1）。如你的学号为10，则所选题目号为：10%5+1＝1（题目1）。注意，所有的课题都要求用图形方式演示步骤和结果。有兴趣的同学可以自己针对通信系统课程的要求，设计一个简单的通信系统，但要预先告知老师，经过审批，方可确定课题，并且每班的自拟题目的总数量不能超过4个，每个课题只能一人单独完成。

1.3设计要求：

1.3.1 课程设计报告规范

（1）系统分析

a. 系统功能分析； b. 数学理论分析； c. 输入输出的要求。 （2）系统设计

a. 系统由哪些模块（组件/元件）组成以及模块之间的关系，每个模块

的功能；

b. 采用C语言设计；

c. 画出各函数的调用关系图、主要函数的流程图。 （3）调试分析以及设计体会

a. 测试数据：准备典型的测试数据和测试方案，包括正确的输入及

输出结果和含有错误的输入及输出结果。 b. 程序调试中遇到的问题以及解决问题的方法。 c. 课程设计过程经验教训、心得体会。 （4）使用说明

用户使用手册：说明如何使用你编写的系统，详细列出每一步的操作步骤。 （5）书写格式

a. 设计报告要求用A4纸打印成册：

b. 一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;

行距为22。

（7）附录

a. 源程序清单（带注释）

1.3.2 考核方式

指导老师负责验收程序的运行结果，并结合学生的工作态度、实际动手能力、创新精神和设计报告等进行综合考评，并按优秀、良好、中等、及格和不及格五个等级给出每位同学的课程设计成绩。具体考核标准包含以下几个部分：

（1）平时出勤 （占10%）

（2）系统需求分析、功能设计、数据结构设计及程序总体结构合理与否（占10%）

（3）程序能否完整、准确地运行，个人能否独立、熟练地调试程序（占40%） （4）设计报告（占30%）

注意：不得抄袭他人的报告（或给他人抄袭），一旦发现，成绩为零分。 （5）独立完成情况（占10%）。 1.3.3 课程验收要求

（1）运行所设计的系统。 （2）回答有关问题。 （3）提交课程设计报告。

（4）提交软盘（源程序、设计报告文档）。

（5）依内容的创新程度，完善程序情况及对程序讲解情况打分。

2 进度安排

2.1 通信工程1101/02/81班：

第 18 周：

星期二 14:30——18：30 上课，讲解课题；

星期三 8：00——12：00；14：30——18：30上机； 星期四 14：30——18：30 上机

附：

课程设计报告装订顺序：封面、任务书、目录、正文、评分、附件（A4大小的图纸及程序清单）。 正文的格式:一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为22。

正文的内容:一、课题的主要功能；二、课题的功能模块的划分（要求画出模块图）；三、主要功能的实现（至少要有一个主要模块的流程图）；四、程序调试；五、总结；六、附件（所有程序的原代码，要求对程序写出必要的注释）。

目 录

一.设计目的................................................................................................................... 9 二.设计内容................................................................................................................... 9 三.设计原理................................................................................................................... 9

3.1 循环轮转调度算法 .......................................................................................... 9 3.2优先数调度算法 ............................................................................................. 10 四．设计步骤.............................................................................................................. 10

4.1 任务分析 ........................................................................................................ 10 4.2 概要设计 ........................................................................................................ 11 4.3 详细设计 ........................................................................................................ 11 4.4 流程图 ............................................................................................................ 12 4.5 源程序 ............................................................................................................ 12 4.6 程序测试数据及结果 .................................................................................... 17 五.设计总结................................................................................................................. 19 六.附录......................................................................................................................... 19

一.设计目的

①设计进程控制块PCB表结构，分别适用于优先数调度算法和循环轮转调度算法。

②建立进程就绪队列。对两种不同算法编制入链子程序。 ③编制两种进程调度算法：1）优先数调度；2）循环轮转调度

二.设计内容

①本程序用两种算法对五个进程进行调度，每个进程可有三个状态，并假设初始状态为就绪状态。

②为了便于处理，程序中的某进程运行时间以时间片为单位计算。各进程的优先数或轮转时间数以及进程需运行的时间片数的初始值均由用户给定。

③在优先数算法中，优先数的值为50与运行时间的差值，即P_TIME-process->needtime。进程每执行一次，优先数减3，CPU时间片数加1，进程还需要的时间片数减1。在轮转算法中，采用固定时间片（即：每执行一次进程，该进程的执行时间片数为已执行了2个单位），这时，CPU时间片数加2，进程还需要的时间片数减2，并排列到就绪队列的尾上。

④对于遇到优先数一致的情况，采用FIFO策略解决。

三.设计原理

3.1 循环轮转调度算法

时间片轮转调度是一种最古老，最简单，最公平且使用最广的算法。每个进程被分配一个时间段，称作它的时间片，即该进程允许运行的时间。如果在时间片结束时进程还在运行，则CPU将被剥夺并分配给另一个进程。如果进程在时间片结束前阻塞或结束，则CPU当即进行切换。调度程序所要做的就是维护一张就绪进程列表，当进程用完它的时间片后，它被移到队列的末尾。

时间片轮转调度中唯一有趣的一点是时间片的长度。从一个进程切换到另一个进程是需要一定时间的--保存和装入寄存器值及内存映像，更新各种表格和队列等。在早期的时间片轮转法中,系统将所有的就绪进程按先来先服务的原则,排

成一个队列,每次调度时,把CPU分配给队首进程,并令其执行一个时间片.时间片的大小从几ms到几百ms.当执行的时间片用完时,由一个计时器发出时钟中断请求,调度程序便据此信号来停止该进程的执行,并将它送往就绪队列的末尾;然后,再把处理机分配给就绪队列中新的队首进程,同时也让它执行一个时间片.这样就可以保证就绪队列中的所有进程,在一给定的时间内,均能获得一时间片的处理机执行时间.

3.2优先数调度算法

优先数调度算法常用于批处理系统中。在进程调度中，每次调度时，系统把处理机分配给就绪队列中优先数最高的进程。它又分为两种：非抢占式优先数算法和抢占式优先数算法。

在非抢占式优先数算法下，系统一旦把处理机分配给就绪队列中优先数最高的进程后，这个进程就会一直运行，直到完成或发生某事件使它放弃处理机，这时系统才能重新将处理机分配给就绪队列中的另一个优先数最高的进程。 在抢占式优先数算法下，系统先将处理机分配给就绪队列中优先数最高的进程度让它运行，但在运行的过程中，如果出现另一个优先数比它高的进程，它就要立即停止，并将处理机分配给新的高优先数进程。

四．设计步骤

4.1 任务分析

(1)PCB结构通常包括以下信息：进程名，进程优先数，轮转时间片，进程已占用的CPU时间，进程还需要的CPU时间，进程的状态，当前队列指针等。可根据实验的不同，PCB结构的内容可以作适当的增删

(2)本程序用两种算法对五个进程进行调度，每个进程可有三个状态：就绪、执行、完成。并假设初始状态为就绪状态。

(3)为了便于处理，程序中的某进程运行时间以时间片为单位计算。各进程的优先数或轮转时间数以及进程需运行的时间片数的初始值均由用户给定。 (4)在优先数算法中，优先数可以先取值为一个常数减去进程所需要的时间片数目，进程每执行一次，优先数减3，CPU时间片数加1，进程还需要的时间片

数减1。在轮转算法中，采用固定时间片（即：每执行一次进程，该进程的执行时间片数为已执行了2个单位），这时，CPU时间片数加2，进程还需要的时间片数减2，并排列到就绪队列的尾上。

(5)对于遇到优先数一致的情况，采用FIFO策略解决。

4.2 概要设计

1.本程序用两种算法对五个进程进行调度，每个进程可有三个状态，并假设初始状态为就绪状态。

2.为了便于处理，程序中的某进程运行时间以时间片为单位计算。各进程的优先数或轮转时间数以及进程需运行的时间片数的初始值均由用户给定。 3.在优先数算法中，优先数的值为50与运行时间的差值，即P_TIME-process->needtime。进程每执行一次，优先数减3，CPU时间片数加1，进程还需要的时间片数减1。在轮转算法中，采用固定时间片（即：每执行一次进程，该进程的执行时间片数为已执行了2个单位），这时，CPU时间片数加2，进程还需要的时间片数减2，并排列到就绪队列的尾上。 4.对于遇到优先数一致的情况，采用FIFO策略解决。

4.3 详细设计

1.struct pcb（） // 定义pcb块 2.Void display（） //显示结果信息函数 3.int process_finished(pcb *q) //进程完成标示

4.void display_round（） //显示循环轮转调度算法运行结果 5.priority_call() //优先数调度算法 6.void cpu_round（）//处理器的工作状态

4.4 流程图

开始 生成并按生成次序排列进程控制块链 链首进程运行 时间片到，进程时间片-1，优先级-3 时间片=0？ 优先级>队列中优先级最高的进程？ 撤销该进程 运行进程退出，取 链首进程运行 进程队列=null？ 结束

4.5 源程序

源程序过程如下： #include #include …

#define P_TIME 50 enum state{ ready, execute, block, finish }; struct pcb{

// 定义pcb块

char name[4]; …

pcb * next; };

pcb * get_process(); pcb * get_process(){ pcb *q; pcb *t; pcb *p; … } i++; } //while return p; }

void display(pcb *p){ //显示结果信息函数

cout<<\ \ cout<<\ \ … } }

int process_finish(pcb *q){ //进程完成标示 int bl=1;

\

while(bl&&q){

bl=bl&&q->needtime==0; q=q->next; } return bl; }

void cpuexe(pcb *q){ pcb *t=q; int tp=0; …

t->cputime++; } }

void priority_call(){ pcb * p; p=get_process(); int cpu=0; … \

getch(); }

void display_menu(){

//显示菜单

//优先数调度算法

cout<<\ cout<<\ cout<<\ cout<<\}

pcb * get_process_round(){ //显示循环轮转调度算法运行结果 pcb *q; pcb *t; pcb *p;

int i=0;

cout<<\…

return p; }

void cpu_round(pcb *q){ //处理器的工作状态 q->cputime+=2; q->needtime-=2; …

q->process=execute; }

pcb * get_next(pcb * k,pcb * head){ pcb * t; t=k; … } return t; }

void set_state(pcb *p){ while(p){

if (p->needtime==0){ p->process=finish; }

if (p->process==execute){ p->process=ready; } p=p->next; } }

void display_round(pcb *p){

cout<<\ \\

\ \ \ …

p=p->next; } }

void round_cal(){ pcb * p; …

set_state(p); } }

void main(){ display_menu(); int k;

scanf(\ switch(k){

case 1:priority_cal();break; case 2:round_cal();break; case 3:break; display_menu(); scanf(\ } }

4.6 程序测试数据及结果

图 1程序测试数据

图 1运用循环轮转调度算法的执行结果1

图 2运用循环轮转调度算法的执行结果2

图 3运用循环轮转调度算法的执行结果3

图 4运用优先数调度算法的执行结果1

图5运用优先数调度算法的执行结果2

图 6运用优先数调度算法的执行结果3

五.设计总结

通过本次试验，我了解到优先数算法是一种以进程优先级作为参考来调度进

程的一种算法。这个算法的好处是能够让优先级高的进程得到更多的CPU占用时间，缺点是那些优先级低的进程可以永远得不到执行。对于轮转法是一种比较公平的算法，所有的进程都有机会得到执行。

六.附录.

#include #include #include #include #include #define P_NUM 5 #define P_TIME 50 enum state{ ready, execute,

block, finish };

struct pcb{ char name[4]; int priority; int cputime; int needtime; int count; int round; state process; pcb * next; };

pcb * get_process(); pcb * get_process(){ pcb *q; pcb *t; pcb *p; int i=0;

cout<<\

while (i

q=(struct pcb *)malloc(sizeof(pcb)); cin>>q->name; cin>>q->needtime; q->cputime=0;

q->priority=P_TIME-q->needtime; q->process=ready; q->next=NULL; if (i==0){ p=q;

t=q; } else{

t->next=q; t=q; } i++; } //while return p; }

void display(pcb *p){

cout<<\ \ \ \ while(p){

cout<name; cout<<\ \ cout<cputime; cout<<\ \ cout<needtime; cout<<\ \ cout<priority; cout<<\ \ switch(p->process){

case ready:cout<<\ case execute:cout<<\ case block:cout<<\ case finish:cout<<\ } p=p->next; }

\

}

int process_finish(pcb *q){ int bl=1; while(bl&&q){

bl=bl&&q->needtime==0; q=q->next; } return bl; }

void cpuexe(pcb *q){ pcb *t=q; int tp=0; while(q){

if (q->process!=finish){ q->process=ready; if(q->needtime==0){ q->process=finish; } }

if(tppriority&&q->process!=finish){ tp=q->priority; t=q; } q=q->next; }

if(t->needtime!=0){ t->priority-=3; t->needtime--; t->process=execute;

t->cputime++; } }

void priority_cal(){ pcb * p; p=get_process(); int cpu=0;

while(!process_finish(p)){ cpu++;

cout<<\ cpuexe(p); display(p); }

printf(\ getch(); }

void display_menu(){

cout<<\ cout<<\ cout<<\ cout<<\}

pcb * get_process_round(){ pcb *q; pcb *t; pcb *p; int i=0;

cout<<\

while (i

q=(struct pcb *)malloc(sizeof(pcb)); cin>>q->name; cin>>q->needtime; q->cputime=0; q->round=0; q->count=0; q->process=ready; q->next=NULL; if (i==0){ p=q; t=q; } else{

t->next=q; t=q; } i++; } //while return p; }

void cpu_round(pcb *q){ q->cputime+=2; q->needtime-=2; if(q->needtime<0) { q->needtime=0; }

q->count++; q->round++; q->process=execute;

}

pcb * get_next(pcb * k,pcb * head){ pcb * t; t=k; do{ t=t->next; }

while (t && t->process==finish); if(t==NULL){ t=head;

while (t->next!=k && t->process==finish){ t=t->next; } } return t; }

void set_state(pcb *p){ while(p){

if (p->needtime==0){ p->process=finish;

}

if (p->process==execute){ p->process=ready; } p=p->next; } }

void display_round(pcb *p){

cout<<\ \ \ \ \ \ while(p){

cout<name; cout<<\ \ cout<cputime; cout<<\ \ cout<needtime; cout<<\ \ cout<count; cout<<\ \ cout<round; cout<<\ \ switch(p->process){

case ready:cout<<\ case execute:cout<<\ case finish:cout<<\ } p=p->next; } }

void round_cal(){ pcb * p; pcb * r;

p=get_process_round(); int cpu=0; r=p;

while(!process_finish(p)){ cpu+=2;

cpu_round(r); r=get_next(r,p);

cout<<\ display_round(p); set_state(p); } }

void main(){ display_menu(); int k;

scanf(\ switch(k){

case 1:priority_cal();break; case 2:round_cal();break; case 3:break; display_menu(); scanf(\ } }

计算机与通信学院课程设计评分表

课程名称： 操作系统

项 目 设计方案的合理性与创造性 设计与调试结果 设计说明书的质量

评 价 答辩陈述与回答问题情况 课程设计周表现情况 综合成绩

教师签名： 日 期：

本文来源：https://www.bwwdw.com/article/riv3.html