操作系统课程设计-通用请求分页调度算法演示程序.docx

操作系统课程设计-通用请求分页调度算法演示程序.docx

《操作系统课程设计-通用请求分页调度算法演示程序.docx》由会员分享，可在线阅读，更多相关《操作系统课程设计-通用请求分页调度算法演示程序.docx（25页珍藏版）》请在冰点文库上搜索。

东莞理工学院城市学院

《计算机操作系统》课程设计

题 目：

通用请求分页调度算法演示程序

专 业：

软件工程

年 级：

2012级3班

小组成员：

指导教师：

时 间：

2014.12.24——2014.12.26

地 点：

东莞理工学院城市学院计算机与信息科学系制

2014年12月

25

摘要

操作系统是管理计算机系统的全部硬件资源包括软件资源及数据资源，控制程序运行改善人机界面，为其它应用软件提供支持等，使计算机系统所有资源最大限度地发挥作用，为用户提供方便的、有效的、友善的服务界面。

操作系统是一个庞大的管理控制程序，大致包括4个方面的管理功能：

处理机管理、存储管理、设备管理、文件管理。

在地址映射过程中，若在页面中发现所要访问的页面不在内存中，则产生缺页中断。

当发生缺页中断时操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。

而用来选择淘汰哪一页的规则叫做页面置换算法。

本次课程设计应用的页面调度算法有先进先出的算法（FIFO）、最佳置换算法（OPT）、近期最久未使用算法（LRU）、近期最少使用算法（LFU）、CLOCK置换算法

目录

1.概述 4

2.课程设计任务及要求 5

2.1设计任务 5

2.2设计要求 5

3.算法及数据结构 7

3.1算法的总体思想（流程） 7

3.2FIFO模块 10

3.2.1功能 10

3.2.2数据结构 10

3.2.3算法 10

3.3OPT模块 11

3.3.1功能 11

3.3.2数据结构 11

3.3.3算法 11

3.4LRU模块 12

3.4.1功能 12

3.4.2数据结构 12

3.4.3算法 12

3.5LFU模块 13

3.5.1功能 13

3.5.2数据结构 13

3.5.3算法 13

3.6CLOCK置换算法模块 14

3.6.1功能 14

3.6.2数据结构 14

3.6.3算法 15

4.程序设计与实现 16

4.1程序流程图 16

4.2程序代码（要注释） 16

4.3实验结果 20

5.结论 23

6.收获、体会和建议。

24

7.参考文献。

25

1.概述

在存储器管理方式中，有一个特点，就是当要求作业全部装入内存才能运行。

但是这样存在两种情况：

有的作业很大，不能全部装入内存，致使作业无法运行。

有大量作业要求运行时，内存容量不足容纳所有的作业，而虚拟内存技术正是在逻辑上扩充内存容量，将会解决以上的两个问题。

所以，当进程开始运行时，先一部分程序装入内存，另一部分暂时留在外存；当没有足够的内存空间时系统自动选择部分内存空间，将其中原来的内容交换到磁盘上，并释放这些内存空间供其它进程使用。

通常，把选择换出页面的算法称为页面置换算法，模拟页面置换算法用以客观解决内存不足的矛盾.

2.课程设计任务及要求

2.1设计任务

2.1.1了解linux的命令及使用格式，熟悉linux的常用基本命令，练习并掌握linux

提供的gedit编辑器来编译c（c++）程序，学会利用gcc（g++）编译、调试c（c++）程序。

2.1.2设计一个虚拟存储区和内存工作区，并使用先进先出的算法（FIFO）、最佳置换算法（OPT）、近期最久未使用算法（LRU）、近期最少使用算法（LFU）、CLOCK置换算法计算命中率。

（命中率=缺页数/页地址流长度*100%）

2.1.3分工：

时间

组员

任务

完成情况

12.24

张乔粤、丁就平

了解设计需求；了解各算法的设计思想；

良好

12.25

张乔粤、丁就平

依照设计要的需求编写各算法的代码。

良好

12.26

张乔粤、丁就平

丁就平画程序流程图以及各算法的思想流程图，整理文档，作好测试；张乔粤继续

完善代码；

良好

2.2设计要求

1）演示实现下列五种请求分页存储管理方式的页面置换算法：

先进先出的算法（FIFO）

最佳置换算法（OPT）

近期最久未使用算法（LRU）近期最少使用算法（LFU）

CLOCK置换算法

2）内存物理块数固定为3个，对多个作业采用固定分配局部置换的策略分配物理块

3）作业数量与作业大小（10-20页）可在界面进行设置

4）所有作业按RR算法进行调度，时间片长度为1秒

5）可为每个作业随机产生引用的页面串，也可以人工输入引用的页面串，页面串长度

50---100，要求必须包括作业所有的页面，可作为样例数据保存

6）可读取样例数据（要求存放在外部文件中）进行作业数量、作业大小、页面串长度的初始化

7）要求对每种算法采用可视化界面，模拟内存分配和使用情况图，可在运行过程中随时暂停，查看当前内存物理块使用情况。

有性能比较功能，可比较同一组数据在不同页面置换算法下的命中率

3.算法及数据结构

3.1算法的总体思想（流程）

结束

Y

N>100

所有已经存入页面的内存time[i]++，n++

Y 比较所有物理块的

time[i]，找到最大值，将

页面调入最大值所在物理块，该物理块time[i]=0

将页面调入空物理块中，该物理块time[i]=0

N

Y

用户内存中是否已存在要调用的页面

N

用户内存中是否存在空物理块

N

将页面page[n]调入内存

N=0

开始

内存数据初始化，物理块

0

选择页面置换算法。

先输入所有的页面号（可随机产生），为系统分配物理块，依次进行置换：

1.先进先出的算法（FIFO）

开始

内存数据初始化，物理块

0

N=0

将页面page[n]调入内存

Y 用户内存中是否已存在要调用的页面

N

存在该页面的物理块time[i]=0

N

用户内存中是否存在空物理块

N



将页面调入空物理

Y 块中，该物理块

time[i]=0

比较所有物理块的time[i]，找到最大值，将页面调入最大值所在物理块，该物理块time[i]=0

所有已经存入页面的内存time[i]++，n++

N>100 Y 结束

2.近期最久未使用算法（LRU）

开始

将页面page[n]调入内存

n>m1 N

按照LRU页面置换算法调入页面

N

Y

比较所有物理块中页

Y面在之前的m1次调入中出现的次数，将页面page[n]调入使用最少的页面占用的物理

块

n++

N<100Y

结束

N=0

内存数据初始化，物理块0

3.近期最少使用算法（LFU）

N

Y

开始

内存数据初始化，物理块0

N=0

将页面page[n]调入内存

调入的页面是否在物理块中

N

物理块中是否

满 N

Y

比较所有页面的顺序号与调入的页面做差值比较把最大的置换

n++

N>100 Y

4. 最佳置换算法（OPT）

直接插入到物理块中

结束

开始

查询指针前进一步指向下一个表目

页面访问位

=0？

是

选择该页面淘汰

结束

clock置换算法

否

置页面访问位

＝”0”

3.2FIFO模块

3.2.1功能

调用该算法实现页面置换调度

3.2.2数据结构

数组：

定义了Memery、time、temp、page。

数组memery规定物理块中的页号；数组time记录物理块中对应页面的进入时间，每次需要置换时换出进入时间最小的页面；temp记录page数组的页面串号在运行过程中进行置换后得出在页面号在物理块被置换的结果；

3.2.3算法

/*先进先出页面置换算法*/voidFIFO（）

{

intmemery[15]={-1};/*物理块数组*/

inttime[15]={0};/*记录进入物理块的时间*/inti,j,k,m,z;/*局部变量*/

intmax=0;/*记录换出*/

intcount1=0;/*记录置换次数变量1*//*修改*/intcount=0;/*记录置换次数变量2*/

intjungle=0;/*物理块是否置换的标记*/

/*修改*/

intwulikuai=0;/*记录前三个物理块进入页面数*/

/*前三个页面字符串置换的算法*/for（i=0;i

{

for（z=0;z

{ if（memery[z]==page[i]）{jungle=1;break;}/*判断进入物理块的页面字符串与已进入物理块数组的页面是否相同*/

}

if（jungle==0）/*不相同时进行插入*/

{

memery[wulikuai]=page[i];/*页面字符串数组插入到物理块数组中*/

count1++;/*记录前三个物理块的置换次数*/

wulikuai++;/*记录已经进入物理块数组的页面数*/

time[i]=wulikuai;/*记录物理块的时间*/

//if（i==mSIZE-1&&wulikuai!

=3）{memery[i]=-1;}/*判断物理块为第三块并且物理块数组被用数不为3时，使未满的物理块数组其它组员为-1*/

}

else{memery[i]=-1;}/*相同时候不进行重复插入*/

/*将物理块数组插入辅助数组中*/for（j=0;j

temp[i][j]=memery[j];/*将物理块数组插入到辅助数组中*/

jungle=0;/*使得页面插入标志置为0*/

}

/*后3个页面字符串的置换算法*/for（i=mSIZE;i

{

/*判断新页面号是否在物理块中*/for（j=0,k=0;j

{

if（memery[j]!

=page[i]） /*处理msize块未满的if（memery[j]!

=page[i]&&memery[j]!

=-1）

*/

k++;

// else if（memery[j]!

=page[i]&&memery[j]==-1&&count1!

=mSIZE）{ memery[j]=page[i];time[2]=i; count++;}

}

if（k==mSIZE）/*如果不在物理块中*/

{

count++;/*换出页面次数+1*/

/*计算换出页*/

max=time[0]

0:

1;/*判断记录访问时间值的大小真则为0假为1赋予记录换出的

变量*/

for（m=2;m

max=m;

memery[max]=page[i];/*页面字符串数组插入到物理块数组中*/time[max]=i;/*记录该页进入物理块的时间*/

/*将物理块数组插入辅助数组中*/for（j=0;j

temp[i][j]=memery[j];

}

else

{ /*将物理块数组插入辅助数组中*/for（j=0;j

temp[i][j]=memery[j];/*物理块数组插入到辅助数组中*/

}

}

compute（）;/*计算过程延迟输出*/

print（count,count1）;//*输出结果函数*/

}

3.3OPT模块

3.3.1功能

调用该算法实现页面置换调度

3.3.2数据结构

数组：

定义了memery，next，temp，page数组。

数组page[pSIZE]存储页面号序列，memery[mSIZE]是存储装入物理块中的页面。

数组next[mSIZE]记录物理块中对应页面的最后访问时间。

每当发生缺页时，就从物理块中找出最后访问时间最大的页面，调出该页，换入所缺的页面。

}

if（jungle==0）

{ memery[wulikuai]=page[i];/*页面字符串数组插入到物理块数组中*/

count1++;/*记录前三个物理块的置换次数*/

wulikuai++;/*记录已经进入物理块数组的页面数*/if（i==mSIZE-1&&wulikuai!

=3）{memery[i]=-1;}

}

else{memery[i]=-1;}/*修改*/for（j=0;j

temp[i][j]=memery[j];/*物理块数组插入到辅助数组中*/jungle=0;

break;}

intjungle=0;/*置换标记*/

intcount1=0;/*记录置换次数*/

intmemery[15]={-1};/*物理块数组*/

intnext[10]={0};/*记录下一次访问时间*/inti,j,k,l,m,z;/*局部变量*/

intmax;/*记录换出页*/

intcount=0;/*记录置换次数*/

intwulikuai=0;/*记录进入物理块数*/for（i=0;i

{

for（z=0;z

{ if（memery[z]==page[i]）{jungle=1;

}

{

/*最佳置换算法*/voidOPT（）

3.3.3算法

count++;}

}

if（k==mSIZE）/*如果不在物理块中*/{

count++;/*得到物理快中各页下一次访问时间*/for（m=0;m

{

for（l=i+1;l

break;next[m]=l;

}/*计算换出页*/max=next[0]>=next[1]?

0:

1;for（m=2;m

if（next[m]>next[max]）max=m;/*下一次访问时间都为pSIZE,则置换物理块中第一个*/memery[max]=page[i];

for（j=0;j

else{

for（j=0;j

print（count,count1）;/*输出结果函数*/

}

memery[j]=page[i];

/*for（i=0;i

{ memery[i]=page[i];/*页面字符串数组插入到物理块数组中*/for（j=0;j

temp[i][j]=memery[j];/*物理块数组插入到辅助数组中*/

}*/

for（i=mSIZE;i

{ /*判断新页面号是否在物理块中*/for（j=0,k=0;j

{ if（memery[j]!

=page[i]）//if（memery[j]!

=page[i]&&memery[j]!

=-1）k++;

// else if（memery[j]!

=page[i]&&memery[j]==-1&&count1!

=mSIZE）{

3.4LRU模块

3.4.1功能

调用该算法实现页面置换调度

3.4.2数据结构

数组：

定义了memery、flag、page、temp数组。

数组page[pSIZE]存储页面号序列，memery[mSIZE]是存储装入物理块中的页面。

数组flag[mSIZE]记录物理块中对应页面的最后访问时间。

每当发生缺页时，就从物理块中找出最后访问时间最大的页面，调出该页，换入所缺的页面。

/*最近最久未使用置换算法*/voidLRU（）

{

intmemery[15]={0};/*物理块数组*/

intflag[10]={0};/*记录页面的访问时间*/inti,j,k,m;/*局部变量*/

intmax=0;/*记录换出页*/

intcount=0;/*记录置换次数*/

/*前mSIZE个数直接放入*/for（i=0;i

{

memery[i]=page[i];/*页面字符串数组插入到物理块数组中*/flag[i]=i;

for（j=0;j

}

3.4.3算法

for（i=mSIZE;i

{

/*判断新页面号是否在物理块中*/for（j=0,k=0;j

{

if（memery[j]!

=page[i]）k++;

else

flag[j]=i;/*刷新该页的访问时间*/}if（k==mSIZE）/*如果不在物理块中*/

{

count++;/*记录置换次数变量+1*/

/*计算换出页*/max=flag[0]

0:

1;for（m=2;m

if（flag[m]

memery[max]=page[i];/*将页面字符串数组插入到物理块数组中*/flag[max]=i;/*记录该页的访问时间*/

for（j=0;j

temp[i][j]=memery[j];/*物理块数组插入到辅助数组中*/

}

else

{

for（j=0;j

temp[i][j]=memery[j];/*物理块数组插入到辅助数组中*/

}

}

compute（）;/*计算过程延迟输出*/

print（0,count）;/*输出结果函数*/

}

3.5LFU模块

3.5.1功能

调用该算法实现页面置换调度

3.5.2数据结构

数组：

定义了memery、flag、page、temp数组。

flag[]数组是一个计数器，记录页面的访问时间。

用一维数组page[pSIZE]存储页面号序列，memery[mSIZE]是存储装入物理块中的页面。

当要调用的页在内存帧中时，调用该页，修改该页的flag值；若要调用的页不在内存帧中，选择page[]中引用次数最少的页进行置换，同时将该页的flag值更新为该页的i值。

依次进行，直到引用页序列为空。

/*最少使用页面算法（LFU）*/voidLFU（）

{

intjungle=0;/*置换标记*/

intcount1=0;/*记录前物理块数的页面置换次数*/intmemery[15]={-1};/*物理块数组*/

intflag[10]={0};/*记录页面的访问时间*/inti,j,k,m,z;/*局部变量*/

intmax=0;/*记录换出页*/

intcount=0;/*记录置换次数*/

intwulikuai=0;/*记录进入物理块数*/for（i=0;i

{

for（z=0;z

{ if（memery[z]==page[i]）{jungle=1;break;}

}

if（jungle==0）

3.5.3算法

}

{

memery[wulikuai]=page[i];/*页面字符串数组插入到物理块数组中*/

count1++;/*记录前三个物理块的置换次数*/

wulikuai++;/*记录已经进入物理块数组的页面数*/

flag[i]=wulikuai;/*记录访问时间*/if（i==mSIZE-1&&wulikuai!

=3）{memery[i]=-1;}

}

else{memery[i]=-1;}/*修改*/for（j=0;j

temp[i][j]=memery[j];/*物理块数组插入到辅助数组中*/jungle=0;

}*/

/*for（i=0;i

{

memery[i]=page[i];/*页面字符串数组插入到物理块数组中*/flag[i]=i;

for（j=0;j

temp[i][j]=memery[j];/*物理块数组插入到辅助数组中*/

for（i=mSIZE;i

{

/*判断新页面号是否在物理块中*/for（j=0,k=0;j

{

if（memery[j]!

=page[i]）/*if（memery[j]!

=page[i]&&memery[j]!

=-1）*/k++;

/*else if（memery[j]!

=page[i]&&memery[j]==-1&&count1!

=mSIZE）{count++;}*/

}

if（k==mSIZE）/*如果不在物理块中*/

{

count++;

/*计算换出页*/max=flag[0]

0:

1;for（m=2;m

if（flag[m]

memery[max]=page[i];/*页面字符串数组插入到物理块数组中*/flag[max]=0;/*记录该页进入物理块的时间*/for（j=0;j

temp[i][j]=memery[j];/*物理块数组插入到辅助数组中*/

}

else

{

for（j=0;j

temp[i][j]=memery[j];/*物理块数组插入到辅助数组中*/

}

}

compute（）;/*计算过程延迟输出*/

print（count,count1）;/*输出结果函数*/

memery[j]=page[i];

}

3.6CLOCK置换算法模块

3.6.1功能

调用该算法实现页面置换调度

3.6.2数据结构

当某一页首次装入内存中时，则将该页框的使用位设置为1；当该页随后被访问到时（在访问产生缺页中断之后），它的使用位也会被设置为1。

对于页面置换算法，用于置换算法，用于置换的候选页框集合（当前进程：

局部范围；整个内存；全局范围）被看做是一个循环缓冲区，并且有一个指针与之相关联。

当一页被置换时，该指针被设置成指向缓冲区中的下一页框。

当需要置换一页时，操作系统扫描缓冲区，以

查找使用位被置为0的一页框。

每当遇到一个使用位为1