操作系统专业课程设计.doc

《操作系统原理及应用》课程设计报告

虚拟存储区和内存工作区

学院（系）： 计算机科学与工程学院
班 级： 学号 26
学生姓名： 许永顺
指引教师： 周 敏

时间： 从 年 12 月21日 到 年12月26日
目录

一、课程设计的目的 3
二、课程设计内容及要求 3
三、实现原理 3
四、流程图 14
五、软件运行环境及限制 23
六、结果输出及分析 23
七、心的体会 28
八、参考文献 28

虚拟存储器和内存工作区

一、 课程设计目
本课程设计是学生学习完《计算机操作系统》课程后，进行一次全面综合训练，通过课程设计，让学生更好地掌握操作系统原理及实现办法,加深对操作系统基本理论和重要算法理解，加强学生动手能力。

二、 课程设计内容及规定
设计一种虚拟存储区和内存工作区,编程序演示下述算法详细实现过程,并计算访问命中率。
规定设计主界面以灵活选取某算法，且如下算法都要实现：
1、先进先出算法（FIFO）
2、近来最久未使用算法（LRU）
3、最佳置换算法（OPT）

三、 实现原理
设计思想：
在进程运营过程中，若其所要访问页面不在内存需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运营，系统必要从内存中调出一页程序或数据，送磁盘对换区中。但应将哪个页面调出，因此需要依照一定算法来拟定。如下分别是三个算法设计思想。
OPTIMAL：最佳置换算法。其所选取被裁减页面，将是后来永不使用，或是在最长（将来）时间内不再被访问页面。
FIFO：先进先出置换算法。该算法总是裁减最先进入内存页面，既选取在内存中驻留时间最久页面予以裁减。
LRU：近来最久未使用置换算法。该算法赋予每个页面一种访问字段，用来记录一种页面自上次被访问以来所经历时间数组flag[psize]，当须裁减一种页面时，选取既有页面中其flag[psize]数组中值最大予以裁减。

源代码如下:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define bsize 3 //物理块大小
#define psize 8 //进程大小

int phb[bsize]={0}； //物理块标号
int pro[psize]={0}； //进程序列号

int flag[bsize] = {0}； //进程等待次数(存储最久未被使用进程标志)
int i = 0，j = 0,k = 0； //i表达进程序列号,j表达物理块号
int m = -1，n = -1； //物理块空闲和进程与否相似判断标志
int max = -1,maxflag = 0；//标记替代物理块进程下标
int count = 0； //记录页面缺页次数

//***************************************************************************************
//随机产生序列号函数
//***************************************************************************************
void build()
{
int i = 0;
for(i=0；i<psize；i++)
{
pro[i] = 10*rand()/(RAND_MAX+1)+1;
printf("%d ",pro[i]);
}
printf("\n");
}

//***************************************************************************************
//查找空闲物理块
//***************************************************************************************
int searchpb()
{
for(j=0；j<bsize；j++)
{
if(phb[j] == 0)
{
m = j；
return m；
break;
}
}
return -1;
}

//***************************************************************************************
//查找相似进程
//***************************************************************************************
int searchpro()
{
for(j = 0；j < bsize；j++)
{
if(phb[j] == pro[i])
{
n = j;
return j;
}
}
return -1;
}

//***************************************************************************************
//初始化内存
//***************************************************************************************
void empty()
{
for(i=0;i<bsize;i++)
phb[i]=0;
count=0； //计数器置零
}

//***************************************************************************************
//最佳置换算法
//***************************************************************************************
void Optimal()
{
for(i = 0；i<psize；i++)
{
m=searchpb()； //查找空闲物理块,返回-1则不存在空闲物理块
n=searchpro()； //查找相似进程，返回值-1则不存在相似进程

if(n == -1) //不存在相似进程
{
if(m != -1) //存在空闲物理块
{
phb[m] = pro[i]； //进程入驻物理块
count++;
m = -1； //再度初始化m
}
else //不存在空闲物理块（就需给被替代物理块做标记）
{
for(int k=0；k<bsize；k++)
{
for(int j=i；j<psize；j++)
{
if(phb[k] != pro[j]) //找不到相似进程
{ flag[k] = 1000;} //将来不会用，设立flag为一种很大数
else //找到相似进程
{
flag[k] = j;
break;
}
}
}

//找flag值最大（就是找到要被替代物理块）
for(j = 0；j < bsize;j++)
{
if(flag[j]>maxflag)
{
maxflag = flag[j]； //要替代物理块
max = j； //要替代物理块下标号
}
}
phb[max]=pro[i]； //置换
count++;

//再度初始化flag
for(j=0;j<bsize;j++)
{
flag[j]=0;
}

flag[max]=0； //置换完毕，初始化该标志（以便下次判断）
max = -1;
maxflag = 0;
n=-1;
}
}
else //存在相似进程
{
phb[n] = pro[i]； //直接调入进程
max = -1;
maxflag = 0;
n = -1;
}

for(j = 0 ;j < bsize；j++)
{
printf("%d ",phb[j]);
}
printf("\n");
}
printf("页面缺页次数为:%d\n",count);
printf("\n");
}

//***************************************************************************************
//先进先出页面置换算法
//***************************************************************************************
void FIFO()
{
for(i = 0；i<psize；i++)
{
m=searchpb();
n=searchpro();

//找flag值最大
for(j = 0；j < bsize;j++)
{
if(flag[j]>maxflag)
{
maxflag = flag[j];
max = j;
}
}

if(n == -1) //不存在相似进程
{
if(m != -1) //存在空闲物理块
{
phb[m] = pro[i]； //进程号填入该空闲物理块
count++;
flag[m] = 0;
for(j = 0;j <= m；j++)
{
flag[j]++;
}
m = -1;
}
else //不存在空闲物理块
{
phb[max] = pro[i];
flag[max] = 0;
for(j = 0;j < bsize；j++)
{
flag[j]++;
}
max = -1;
maxflag = 0;
count++;
}
}
else //存在相似进程
{
phb[n] = pro[i];
for(j = 0;j < bsize；j++)
{
flag[j]++;
}
n = -1;
}

for(j = 0 ;j < bsize；j++)
{
printf("%d ",phb[j]);
}
printf("\n");
}
printf("缺页次数为：%d\n",count);
printf("\n");
}

//***************************************************************************************
//最久未使用算法
//***************************************************************************************
void LRU()
{
for(i = 0；i<psize；i++)
{
m=searchpb();
n=searchpro();

//找flag值最大
for(j = 0；j < bsize;j++)
{
if(flag[j]>maxflag)
{
maxflag = flag[j];
max = j;
}
}

if(n == -1) //不存在相似进程
{
if(m != -1) //存在空闲物理块
{
phb[m] = pro[i];
count++;
flag[m] = 0;
for(j = 0;j <= m；j++)
{
flag[j]++;
}
m = -1;
}
else //不存在空闲物理块
{
phb[max] = pro[i];
flag[max] = 0;
for(j = 0;j < bsize；j++)
{
flag[j]++;
}
max = -1;
maxflag = 0;
count++； //置换
}
}
else //存在相似进程
{
phb[n] = pro[i];
flag[n] = 0； //刚进入物理块进程等待次数重设
if(m != -1) //若存在空闲物理块
{
flag[m] = 0； //进程等待次数重设
}
for(j = 0;j < bsize；j++)
{
flag[j]++;
}
max = -1;
maxflag = 0;
n = -1;
}

for(j = 0 ;j < bsize；j++)
{
printf("%d ",phb[j]);
}
printf("\n");
}
printf("页面缺页次数为:%d\n",count);
printf("\n");
}

//***************************************************************************************
//主函数
//***************************************************************************************
void main()
{
int sel;
do{
printf("\t\t\t--------------------------------------\t\t\t");
printf("\t\t\t ☆☆^-^欢迎进入操作系统界面^-^☆☆ \t\t\t");
printf("\t\t\t--------------------------------------\t\t\t\n");
printf("\t\t\t☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\t\t\t");
printf("\t\t\t☆ 虚拟内存 ☆ \t\t\t");
printf("\t\t\t☆--------------------------------☆\t\t\t");
printf("\t\t\t☆ 1、最佳置换(Optimal) ☆ \t\t\t");
printf("\t\t\t☆--------------------------------☆\t\t\t");
printf("\t\t\t☆ 2、先进先出(FIFO) ☆ \t\t\t");
printf("\t\t\t☆--------------------------------☆\t\t\t");
printf("\t\t\t☆ 3、最久未使用(LRU) ☆ \t\t\t");
printf("\t\t\t☆--------------------------------☆\t\t\t");
printf("\t\t\t☆ 4、初始化内存 ☆ \t\t\t");
printf("\t\t\t☆--------------------------------☆\t\t\t");
printf("\t\t\t☆ 0、退出(Exit) ☆ \t\t\t");
printf("\t\t\t☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆\t\t\t\n");
printf("随机产生一种进程序列号为：\n");
build();
printf("请选取置换算法(0/1/2/3):");
scanf("%d",&sel);
switch(sel)
{
case 0:printf("\t\t\t ^-^再会！^-^ \t\t\t\n");break;
case 1:printf("置换算法\n");Optimal();system("pause");break;
case 2:printf("先进先出算法\n");FIFO();system("pause");break;
case 3:printf("最久未使用法\n");LRU();system("pause");break;
case 4:empty();system("pause");printf("\n");break;
default:printf("请输入对的选项号！");printf("\n\n");break;
}
}while(sel!=0);
}

四、 流程图

查找空闲物理块流程图

查找相似进程流程图

产生随机数流程图

查找空闲物理块流程图

查找相似进程流程图

最佳置换算法流程图

先进先出置换算法流程图

最久未使用流程图

主函数流程图

五、 软件运营环境及限制
实验软件平台：Windows xp ,Viso
实现语言：C语言

六、 成果输出及分析
运营成果截图如下：

最佳置换算法实现成果输出截图
成果分析：
i=0时，存在空闲块，调入页面直到i=3，物理块满，采用最佳置换算法，由于进程9和8与物理块页面相似，因此不需要调入9和8页面；当i=5时，由于物理块中不存在与进程6相似页面，且物理块中2最久未被使用，因而6代替2；同理，可得到以上成果。

先进先出置换算法成果截图

成果分析：
i=0到i=2物理块存在空闲，直接调入页面，当i=3时，物理块满，采用先进先出页面置换算法，5先进来，7替代5，如此，直至程序结束。

成果分析：
i=0和i=2时，存在空闲物理块，直接调入缺页进入内存，i=1时，由于进程与物理块中进程相似，则不调入；i=4时，4替代9，如此，直至程序运营结束。

最久未使用置换算法截图

退出系统截图

七、 心得体会
通过一学期学习，对操作系统基本知识有了一定掌握，特别是对内存分派、内存管理和页面置换等有了更好掌握。特别时最后这几种星期，完毕了操作系统课程设计，对这些知识可以说较好巩固了一遍，对某些不太清晰理解不透彻知识盲点有了更清晰结识。在这过程中，我深深体会了团队协作重要性，一种人思维终归时有局限性，多一种人多一份力量，多一种解决办法，哪怕只是一次小小课程设计，也可以让咱们受益良久。

八、 参照文献
一、计算机操作系统 西安电子科技大学出版社 汤小丹 梁红兵 哲凤屏 汤子赢 编著
二、C语言程序设计 清华大学出版社