（1）先进先出调度算法（FIFO）
先进先出调度算法根据页面进入内存的时间先后选择淘汰页面，先进入内存的页面先淘汰，后进入内存的后淘汰。本算法实现时需要将页面按进入内存的时间先后组成一个队列，每次调度队首页面予以淘汰。
（2）最近最少调度算法（LRU）
先进先出调度算法没有考虑页面的使用情况，大多数情况下性能不佳。根据程序执行的局部性特点，程序一旦访问了某些代码和数据，则在一段时间内会经常访问他们，因此最近最少用调度在选择淘汰页面时会考虑页面最近的使用，总是选择在最近一段时间以来最少使用的页面予以淘汰。算法实现时需要为每个页面设置数据结构记录页面自上次访问以来所经历的时间。
（3）最近最不常用调度算法（LFU）
由于程序设计中经常使用循环结构，根据程序执行的局部性特点，可以设想在一段时间内经常被访问的代码和数据在将来也会经常被访问，显然这样的页面不应该被淘汰。最近最不常用调度算法总是根据一段时间内页面的访问次数来选择淘汰页面，每次淘汰访问次数最少的页面。算法实现时需要为每个页面设置计数器，记录访问次数。计数器由硬件或操作系统自动定时清零。
（4）最优调度算法（OPT）
该算法所选择的被淘汰页面，将是以后永久不被访问，或者是在未来最长时间内不再被访问的页面。采用最优更新算法通常可以保证获得最低的缺页率。
页式虚拟存储器实现的一个难点是设计页面调度（置换）算法，即将新页面调入内存时，如果内存中所有的物理页都已经分配出去，就要按某种策略来废弃某个页面，将其所占据的物理页释放出来，供新页面使用。本实验的目的是通过编程实现几种常见的页面调度（置换）算法，加深读者对页面思想的理解
(1）设计程序实现以上三种页面调度算法，要求:
①.可以选择页面调度算法类型;
②.可以为进程设置分到物理页的数目，设置进程的页面引用情况，从键盘输入页面序列
③.随时计算当前的页面调度次数的缺页中断率;
④.使用敲键盘或响应WM-TIMER的形式模仿时间的流逝;
⑤.以直观的的形式将程序的执行情况显示在计算机屏幕上;
#include <iostream>
using namespace std;
const int DataMax=100;
const int BlockNum = 10;
int DataShow[BlockNum][DataMax]; // 用于存储要显示的数组
bool DataShowEnable[BlockNum][DataMax]; // 用于存储数组中的数据是否需要显示
int Data[DataMax]; // 保存数据
int Block[BlockNum]; // 物理块
int count[BlockNum]; // 计数器
int N ; // 页面个数
int M;//最小物理块数
int ChangeTimes;
void DataInput(); // 输入数据的函数
void DataOutput();
void FIFO(); // FIFO 函数
void Optimal(); // Optimal函数
void LRU(); // LRU函数
int main(int argc, char* argv[]) {
DataInput();
int menu;
while(true) {
cout<<endl;
cout<<"* 菜单选择 *"<<endl;
cout<<"*******************************************************"<<endl;
cout<<"* 1-FIFO *"<<endl;
cout<<"* 2-Optimal *"<<endl;
cout<<"* 3-LRU *"<<endl;
cout<<"* 0-EXIT *"<<endl;
cout<<"*******************************************************"<<endl;
cin>>menu;
switch(menu) {
case 1:
FIFO();
break;
case 2:
Optimal();
break;
case 3:
LRU();
break;
default:
break;
}
if(menu!=1&&menu!=2&&menu!=3) break;
}
}
//*/
void DataInput() {
cout<<"请输入最小物理块数：";
cin>>M;
while(M > BlockNum) { // 大于数据个数
cout<<"物理块数超过预定值，请重新输入：";
cin>>M;
}
cout<<"请输入页面的个数：";
cin>>N;
while(N > DataMax) { // 大于数据个数
cout<<"页面个数超过预定值，请重新输入：";
cin>>N;
}
cout<<"请输入页面访问序列："<<endl;
for(int i=0; i<N; i++)
cin>>Data[i];
}
void DataOutput() {
int i,j;
for(i=0; i<N; i++) { // 对所有数据操作
cout<<Data[i]<<" ";
}
cout<<endl;
for(j=0; j<M; j++) {
cout<<" ";
for(i=0; i<N; i++) { // 对所有数据操作
if( DataShowEnable[j][i] )
cout<<DataShow[j][i]<<" ";
else
cout<<" ";
}
cout<<endl;
}
cout<<"缺页中断次数: "<<ChangeTimes<<endl;
cout<<"缺页中断率: "<<ChangeTimes*100/N<<"%"<<endl;
if(ChangeTimes-M > 0){
cout<<"缺页调度次数: "<<ChangeTimes-M<<endl;
cout<<"缺页置换率: "<<(ChangeTimes-M)*100/N<<"%"<<endl;
}
else{
cout<<"缺页调度次数: 0"<<endl;
cout<<"缺页置换率: 0%"<<endl;
}
}
void FIFO() {
int i,j;
bool find;
int point;
int temp; // 临时变量
ChangeTimes = 0;
for(j=0; j<M; j++)
for(i=0; i<N; i++)
DataShowEnable[j][i] = false; // 初始化为false，表示没有要显示的数据
for(i=0; i<M; i++) {
count[i] = 0; // 大于等于BlockNum，表示块中没有数据，或需被替换掉
// 所以经这样初始化（3 2 1），每次替换>=3的块，替换后计数值置1，
// 同时其它的块计数值加1 ，成了（1 3 2 ），见下面先进先出程序段
}
for(i=0; i<N; i++) { // 对有所数据操作
// 增加count
for(j=0; j<M; j++)
count[j]++;
find = false; // 表示块中有没有该数据
for(j=0; j<M; j++) {
if( Block[j] == Data[i] ) {
find = true;
}
}
if( find ) continue; // 块中有该数据，判断下一个数据
// 块中没有该数据
ChangeTimes++; // 缺页次数++
if( (i+1) > M ) { // 因为i是从0开始记，而M指的是个数，从1开始，所以i+1
//获得要替换的块指针
temp = 0;
for(j=0; j<M; j++) {
if( temp < count[j] ) {
temp = count[j];
point = j; // 获得离的最远的指针
}
}
} else point = i;
// 替换
Block[point] = Data[i];
count[point] = 0; // 更新计数值
// 保存要显示的数据
for(j=0; j<M; j++) {
DataShow[j][i] = Block[j];
DataShowEnable[i<M?(j<=i?j:i):j][i] = true; // 设置显示数据
}
}
// 输出信息
cout<< endl;
cout<<"FIFO => "<< endl;
DataOutput();
}
void Optimal() {
int i,j,k;
bool find;
int point;
int temp; // 临时变量，比较离的最远的时候用
ChangeTimes = 0;
for(j=0; j<M; j++)
for(i=0; i<N; i++)
DataShowEnable[j][i] = false; // 初始化为false，表示没有要显示的数据
for(i=0; i<N; i++) { // 对有所数据操作
find = false; // 表示块中有没有该数据
for(j=0; j<M; j++) {
if( Block[j] == Data[i] )
find = true;
}
if( find ) continue; // 块中有该数据，判断下一个数据
// 块中没有该数据，最优算法
ChangeTimes++; // 缺页次数++
for(j=0; j<M; j++) {
// 找到下一个值的位置
find = false;
for( k =i; k<N; k++) {
if( Block[j] == Data[k] ) {
find = true;
count[j] = k;
break;
}
}
if( !find ) count[j] = N;
}
if( (i+1) > M ) { // 因为i是从0开始记，而BlockNum指的是个数，从1开始，所以i+1
//获得要替换的块指针
temp = 0;
for(j=0; j<M; j++) {
if( temp < count[j] ) {
temp = count[j];
point = j; // 获得离的最远的指针
}
}
} else point = i;// 替换
Block[point] = Data[i];// 保存要显示的数据
for(j=0; j<M; j++) {
DataShow[j][i] = Block[j];
DataShowEnable[i<M?(j<=i?j:i):j][i] = true; // 设置显示数据
}
}// 输出信息
cout<< endl;
cout<<"Optimal => "<< endl;
DataOutput();
}
void LRU() {
int i,j;
bool find;
int point;
int temp; // 临时变量
ChangeTimes = 0;
for(j=0; j<M; j++)
for(i=0; i<N; i++)
DataShowEnable[j][i] = false; // 初始化为false，表示没有要显示的数据
for(i=0; i<M; i++) {
count[i] = 0 ;
}
for(i=0; i<N; i++) { // 对有所数据操作
// 增加count
for(j=0; j<M; j++)
count[j]++;
find = false; // 表示块中有没有该数据
for(j=0; j<M; j++) {
if( Block[j] == Data[i] ) {
count[j] = 0;
find = true;
}
}
if( find ) continue; // 块中有该数据，判断下一个数据
// 块中没有该数据
ChangeTimes++; // 缺页次数++
if( (i+1) > M ) { // 因为i是从0开始记，而BlockNum指的是个数，从1开始，所以i+1
//获得要替换的块指针
temp = 0;
for(j=0; j<M; j++) {
if( temp < count[j] ) {
temp = count[j];
point = j; // 获得离的最远的指针
}
}
} else point = i;
// 替换
Block[point] = Data[i];
count[point] = 0;
// 保存要显示的数据
for(j=0; j<M; j++) {
DataShow[j][i] = Block[j];
DataShowEnable[i<M?(j<=i?j:i):j][i] = true; // 设置显示数据
}
}// 输出信息
cout<< endl;
cout<<"LRU => "<< endl;
DataOutput();
}
假定进程分配到3个物理块，对于下面的页面引用序列:
7-0-1-2-0-3-0-4-2-3-0-3-2-1-2-0-1-7-0-1
请分别用先进和先出调度算法，最近最少用调度算法，最优调度算法计算缺页中断次数，缺页中断率和缺页调度次数、缺页置换率。
文章出处登录后可见！
已经登录？立即刷新
