页面调度实验报告
- 格式：doc
- 大小：113.00 KB
- 文档页数：15
设计
题目 操作系统 页面调度
成 绩
课
程
设
计
主
要
内
容
一、课程设计的性质、目的和作用
页式虚拟存储器实现的一个难点是设计页面调度（置换）算法，即将新页面调入内存时，如果内存中所有的物理页都已经分配出去，就要按某种策略来废弃某个页面，将其所占据的物理页释放出来，供新页面使用。本实验的目的是通过编程实现几种常见的页面调度（置换）算法，加深读者对页面思想的理解。
二、课程设计的具体内容
<1>先进先出调度算法
<2>最近最少调度算法
<3>最近最不常用调度算法
<4>SECOND 二次机会调度算法
<5>各种算法同时显示
三、课程设计的要求
用自己熟悉的一种数据库开发工具，,VC++等。
指
导
教
师
评
估 建议：从学生的工作态度、工作量，设计（论文）的创造性、学术性、实用性及书面表达能力等方面给出评价。
签名： 200 年 月 日 一、实验内容
（1）页面调度算法
目前有许多页面调度算法，本实验主要涉及先进先出调度算法、最近最少调度算法、最近最不常用调度算法。本实验使用页面调度算法时作如下假设，进程在创建时由操作系统为之分配一个固定数目物理页，执行过程中物理页的数目和位置不会改变。也即进程进行页面调度时只能在分到的几个物理页中进行。
下面对各调度算法的思想作一介绍。
<1> 先进先出调度算法
先进先出调度算法根据页面进入内存的时间先后选择淘汰页面，先进入内存的页面先淘汰，后进入内存的后淘汰。本算法实现时需要将页面按进入内存的时间先后组成一个队列，每次调度队首页面予以淘汰。
<2>最近最少调度算法
先进先出调度算法没有考虑页面的使用情况，大多数情况下性能不佳。根据程序执行的局部性特点，程序一旦访问了某些代码和数据，则在一段时间内会经常访问他们，因此最近最少用调度在选择淘汰页面时会考虑页面最近的使用，总是选择在最近一段时间以来最少使用的页面予以淘汰。算法实现时需要为每个页面设置数据结构记录页面自上次访问以来所经历的时间。
<3>最近最不常用调度算法
由于程序设计中经常使用循环结构，根据程序执行的局部性特点，可以设想在一段时间内经常被访问的代码和数据在将来也会经常被访问，显然这样的页面不应该被淘汰。最近最不常用调度算法总是根据一段时间内页面的访问次数来选择淘汰页面，每次淘汰访问次数最少的页面。算法实现时需要为每个页面设置计数器，记录访问次数。计数器由硬件或操作系统自动定时清零。
（2）缺页调度次数和缺页中断率、缺页置换率计算
缺页中断次数是缺页时发出缺页中断的次数。
缺页中断率=缺页中断次数/总的页面引用次数*100%
缺页调度次数是调入新页时需要进行页面调度的次数
缺页置换率=缺页调度次数/总的页面引用次数*100%
二、总体设计
1、 算法的原理说明
FIFO 先进先出调度算法：
当页面框满时，最早进来的页面调出；
LRU 最近最少使用调度算法：
当页面框满时，最近最少使用的页面调出
LFU 最近最不常用调度算法：
当页面框满时，最近最不常用的页面调出 SECOND 二次机会调度算法：
当页面框满时，页面调入时R=0，当被访问时R = 1。发生替换时，先检查最老的页面的R,如果为0则调出，若为1，则令R = 0，修改装入时间，如刚被装入一样。然后继续搜索可替换页面
2、 设计思路
本设计模拟实现中有以下几点：
1：数据由data.txt和data2.txt.文档中提取。Txt文档必须放入与程序dubug相同的目录。如果想添加数据，可以在此目录下新添文本文档。
2：输入txt文件名自动获取页面号
3：用队列来表示内存，且最多只能存放3个页面
4：每次执行算法结束，第一行输出每次淘汰的页面号，若未淘汰则用*表示。第二行显示缺页的总次数。
5：本程序涉及4个类，页面类，算法类，队列结点类，队列类。
三、模拟实现
1：程序所需C++的类库
#include
#include
#include
#include //文件输入输出函数库
#include //异常处理
2：从Txt文档中提取页面号
If stream infile(T_name);
while(!infile.eof()){ //eof()，infile的文件尾状态
infile>>Array_data; //读数据的时候因为数据间有一个空格//才能完整的读出，
T_data[i] = Array_data;
if(infile.eof()) break;
i++;
T_num++;
if(infile.eof()) break;
}
3:页面类定义
class page{ //页面类
public:
int pagenumber; //页面号
int R; //此页面被调入时间，初次调入为零。每次调度R值加1；若命中则变回0；
int hit; //命中次数
page(){
pagenumber = 0;
R = 0;
hit = 0;
}
};
4:队列结点类定义
class Node{
public:
page data;
Node *link;
};
5算法类
class Algorithm{
public:
Node *next0;
int total; //缺页的总页数
int total_hit;//命中次数
public: Algorithm(){
total = 0;
total_hit = 0;
}
void FIFO(int T_data[],int T_num); //先进先出算法
void LRU(int T_data[],int T_num); //最近最少使用调度算法
void LFU(int T_data[],int T_num); //最近最不常用调度算法
void SECOND(int T_data[],int T_num);//二次机会算法
};
6队列类
class Queue{
public:
int num; //队列中元素个数
Node *front; //指向头节点指针
Node *rear; // 指向尾节点指针
public:
Queue(){
front = NULL;
rear = NULL;
num = 0;
}
~Queue();
void add(page add_data); //入队
page putout(); //出队
void Exchange(page data); //若队列中含有此页，则将此页与队尾交换位置
bool look(page datas); //查看是否有相同项
void output(); //输出矩阵
page ChooseOut(page N1); //将队中某项出队
};
7：算法实现函数
void Algorithm::FIFO(int T_data[],int T_num){ //先进先出算法
Queue Q1; //内存中的页面
Queue Q2; //被置换出去的页面
Queue FIFO_Q; //将文档中的数构成的矩阵转到队列中
Node *next;
page out;
page T_x;
//-------
for(int i = 0;i<=T_num;i++){//将文档中的数构成的矩阵转到队列中
T_x.pagenumber = T_data[i]; FIFO_Q.add(T_x);
}
//-------
next = FIFO_Q.front;
while(next != NULL){
if(Q1.num <= 2){
if(Q1.num == 0){
Q1.add(next->data);
total = total + 1;
}
else{
if(Q1.look(next->data) == false){
Q1.add(next->data);
total = total + 1;
}
else{
total_hit = total_hit + 1;
}
}
out.pagenumber = -1;//*********
Q2.add(out);
}
else{
if(Q1.look(next->data) == false){
out = Q1.putout();
Q2.add(out);
Q1.add(next->data);
total = total + 1;
}
else{
total_hit = total_hit + 1;
out.pagenumber = -1;//*********
Q2.add(out);
}
}
next = next->link;
}
cout<<"--------------------------------------------------------------"<
cout<<"FIFO算法:"<
cout<<"每次淘汰的页面号:";
Q2.output();
cout<
