重庆理工大学操作系统课程设计
《操作系统原理及应用》课程设计报告
题目:虚拟存储区和内存工作区
学院(系): 计算机科学与工程学院
班 级: 学号
学生姓名:
指导教师:
1
重庆理工大学操作系统课程设计
时间: 从 2009 年 12 月 21 日 到 2009 年 12 月 26 日
目录
一、课程设计的目的 .................................................................3
二、课程设计内容及要求.............................................. 3
三、实现原理............................................................ 3
四、流程图............................................................ 16
五、软件运行环境及限制............................................. 23
六、结果输出及分析.................................................. 23
七、心的体会.......................................................... 27
八、参考文献.......................................................... 27
2
重庆理工大学操作系统课程设计
虚拟存储器和内存工作区
一、 课程设计的目的
本课程设计是学生学习完《计算机操作系统》课程后,进行的一次全面的综合训练,
通过课程设计,让学生更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和
重要算法的理解,加强学生的动手能力。
二、 课程设计内容及要求
设计一个虚拟存储区和内存工作区,编程序演示下述算法的具体实现过程,并计算访问
命中率。
要求设计主界面以灵活选择某算法,且以下算法都要实现:
1、先进先出算法(FIFO)
2、最近最久未使用算法(LRU)
3、最佳置换算法(OPT)
三、 实现原理
设计思想:
在进程运行过程中,若其所要访问的页面不在内存需把它们调入内存,但内存已无空闲
空间时,为了保证该进程能正常运行,系统必须从内存中调出一页程序或数据,送磁盘的
对换区中。但应将哪个页面调出,所以需要根据一定的算法来确定。以下分别是三个算法
的设计思想。
OPTIMAL:最佳置换算法。其所选择的被淘汰页面,将是以后永不使用的,或是在最长
(未来)时间内不再被访问的页面。
FIFO:先进先出置换算法。该算法总是淘汰最先进入内存的页面,既选择在内存中驻留时
间最久的页面予以淘汰。
LRU:最近最久未使用置换算法。该算法赋予每个页面一个访问字段,用来记录一个页面
自上次被访问以来所经历的时间数组,当须淘汰一个页面时,选择现有页面中其记录数组
中值最大的给予淘汰。
先进先 出 算 法 ( FIFO),最 佳 置 换 算 法( OPT)后 考 虑 最 近 最 久未 使 用 算 法
(LRU),有两种思路
1) 如果从 FIFO 算法的思路考虑,LRU 算法是一种特殊的 FIFO 算法,区别在于,FIFO
算法记录页面在内存中的时间是从页面进入内存开始计算,只要页面未被置换出,便一直
3
重庆理工大学操作系统课程设计
累加,而 LRU 算法计算页面在内存的时间是以页面最近一次被调用为准,当内存中的某个
页面被调用一次后它在内存中的时间便需初始化。
2) 如果从 OPT 算法的思路考虑,LRU 算法又是一种特殊的 OPT 算法。OPT 算法是从现
在开始往将来考虑,寻找将来使用离现在时间最远的。LRU 算法是从现在开始往之前考虑,
寻找之前使用离现在最远的。
本题程序实现的是第一种算法
源代码如下:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<malloc.h>
int bsize; //物理块大小
int psize; //进程大小
int phb[20]; //物理块
int pro[100]; //进程序列
int i = 0, j = 0,k = 0; //,循环变量,i 表示进程序列号,j 表示物理块号
int m = -1, n = -1; //物理块空闲和进程是否相同判断标志
int count = 0; //统计页面缺页次数
//
*******************************************************************************
********
//随机产生序列号函数
//
*******************************************************************************
********
void create()
{
int i = 0;
for(i=0; i<psize; i++)
{
pro[i] = 10*rand()/(RAND_MAX+1)+1;
printf("%d ",pro[i]);
}
printf("\n");
}
//
*******************************************************************************
********
//查找空闲物理块
//
*******************************************************************************
4
重庆理工大学操作系统课程设计
********
int searchpb()
{
int j;
for(j=0; j<bsize; j++)
{
if(phb[j] == -1)
{
m = j;
return m;
}
}
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++)
5