操作系统课程设计报告
操作系统课程设计报告
题 目：页面置换算法模拟程序设计
专 业：软件工程
院 系：信息管理学院
年 级：大三软件Q1141
学 号：11150038
姓 名：李艳平
指导教师：李红艳
职 称：副教授
湖北经济学院教务处 制
目录
第一部分概述
第二部分设计的基本概念和原理
第三部分总体设计
3.1算法流程图
3.2算法的简要实现方法
3.2.1 OPT页面置换算法
3.2.2 FIFO页面置换算法
3.2.3 LRU页面置换算法
3.2.4 LFU页面置换算法
第四部分详细设计
4.1 main函数
4.2 OPT函数
4.2 FIFO函数
4.3 LRU函数
4.5 LFU函数
4.6辅助函数
4.6.1 Designer函数
4.6.2 mDelay函数
4.6.3 Download函数
4.6.4 Compute函数
4.6.5 showTable函数
第五部分实现源代码
第六部分简要的使用说明及主要运行界面
第七部分总结
第八部分参考文献
第一部分 概述
设计任务：
页面置换算法是虚拟存储管理实现的关键，通过本次课程设计理解内存页面调度的机制，在模拟实现OPT、FIFO、LRU和LFU几种经典页面置换算法的基础上，比较各种置换算法的效率及优缺点，从而了解虚拟存储实现的过程。
第二部分 设计的基本概念和原理
(1)．页面淘汰机制
页面淘汰又称为页面置换。若请求调页程序要调进一个页面，而此时该作业所分得的主存块已全部用完，则必须淘汰该作业已在主存中的一个页。这时，就产生了在诸页面中淘汰哪个页面的问题，这就是淘汰算法（或称为置换算法）。
置换算法可描述为，当要索取一个页面并送入主存时，必须将该作业已在主存中的某一页面淘汰掉，用来选择淘汰哪一页的规则就叫做置换算法。
(2)．各种页面置换算法的实现思想
OPT算法是当要调入一新页而必须先淘汰一旧业时，所淘汰的那一页应是以后不要再用的或是以后很长时间才会用到的页。
FIFO算法的实质是，总是选择在主存中居留时间最长（即最老）的一页淘汰。其理由是最先调入主存的页面，其不再被使用的可能性比最近调入主存的页的可能性大。
LRU算法的实质是，当需要置换一页时，选择最长时间未被使用的那一页淘汰。如果某一页被访问了，它很可能马上还要被访问；相反，如果它很长时间未曾用过，看起来在最近的未来是不大需要的。
LFU即最不经常使用页置换算法，要求在页置换时置换在一定时期内引用计数最小的页，因为经常使用的页应该有一个较大的引用次数。本次设计取整个页面访问时期为计算周期，实际问题中应根据页面数量多少来确定周期。
第三部分 总体设计
3.1算法流程图
3.2算法的简要实现方法
选择置换算法，先输入所有页面号，为系统分配物理块，依次进行置换：
最佳置换算法（OPT）：
是用一维数组page[PSIZE]存储页面号序列，memery[MSIZE]是存储装入物理块中的页面，用pflag[PSIZE]数组标记缺页中断处。数组next[MSIZE]记录物理块中对应页面的最后访问时间。每当发生缺页时，就从物理块中找出最后访问时间最大的页面，调出该页，换入所缺的页面，然后初始化next[MSIZE]，便于下次使用。
【特别声明】
若物理块中的页面都不再使用，则每次都置换物理块中第一个位置的页面。
先进先出置换算法（FIFO）：
是用一维数组page[PSIZE]存储页面号序列，memery[MSIZE]是存储装入物理块中的页面，用pflag[PSIZE]数组标记缺页中断处。采用队列的思想，总是把最先进入物理块中的页面放在第一个位置，当发生缺页时，就从队头删除一页，而从队尾加入缺页。
最久未使用置换算法（LRU）：
是用一维数组page[PSIZE]存储页面号序列，memery[mSIZE]是存储装入物理块中的页面，用pflag[PSIZE]数组标记缺页中断处。总是把最长时间内未被使用的页放在最后一块，当发生缺页时，就删掉最后一页，将当前所缺页面放入第一块。
最不经常使用淘汰算法（LFU）：
是用一维数组page[PSIZE]存储页面号序列，memery[mSIZE]是存储装入物理块中的页面，用pflag[PSIZE]数组标记缺页中断处。用use[MSIZE]数组记录当前各页已使用次数，其中use[0]中存放使用次数最少的页的次数，当发生缺页时，就在已放入物理块的页中查找当前使用次数最少的页，将之删掉，并引入当前缺页页面。
第四部分 详细设计
main函数：
void main()
{
int i, k, code;
int mSize, pSize, page[PSIZE];
system("color 0A");
Designer();
printf("┃请按任意键继续... ┃\n");
printf("┖─────────────────────────┚\n");
printf(" >>> ");
getchar();
system("cls"); //DOS命令，清除屏幕上的所有文字
system("color 0B"); //改变控制台的前景和背景色
printf("请输入物理块的个数[mSize <= 10]：");
scanf("%d", &mSize);
printf("请输入页面数[pSize <= 50]：");
scanf("%d", &pSize);
printf("请输入页面序列[1~10之间]：\n");
for (i = 0; i < pSize; i ++)
scanf("%d", &page[i]);
Download(pSize, mSize);
system("cls");
system("color 0E");
do
{
printf("即将进入物理块的页面序列为:\n");
for (i = 0; i < pSize; i ++)
printf("%3d", page[i]);
printf("\n");
printf("* * * * * * * * * * * * * * * * * * * * * * * * * * * * *\n");
printf("* 请选择页面置换算法： *\n");
printf("* ━━━━━━━━━━━━━━━━━━━━━━━━━━━*\n");
printf("* 1.最佳(OPT) 2.先进先出(FIFO) 3.最近最久未使用(LRU)*\n");
printf("* 4.最不经常使用(LFU,当前使用次数最少) 5.退出 *\n");
printf("* * * * * * * * * * * * * * * * * * * * * * * * * * * * *\n");
printf("请选择操作：[ ]\b\b");
scanf("%d",&code);
switch (code)
{
case 1:
OPT(page, pSize, mSize);
break;
case 2:
FIFO(page, pSize, mSize);
break;
case 3:
LRU(page, pSize, mSize);
break;
case 4:
LFU(page, pSize, mSize);
break;
case 5:
system("cls");
system("color 0A");
Designer(); //显示设计者信息后退出
printf("┃谢谢使用页面置换算法演示器! 正版授权 ㊣┃\n");
printf("┗━━━━━━━━━━━━━━━━━━━━━━━━━┛\n");
exit(0);
default:
printf("输入错误，请重新输入：");
}
//printf("按任意键重新选择置换算法：>>>");
getchar();
system("pause"); //冻结屏幕
system("cls");
} while (code != 5);
getchar ();
}
OPT函数：
void OPT(int page[], int pSize, int mSize)
{
int i, j, k;
int count = 0; //计数器
int memery[MSIZE] = {0}; //存储装入物理块中的页面
int next[MSIZE] = {0}; //记录物理块中对应页面的最后访问时间
sum = 0;
for (i = 0; i < pSize; i ++)
{
j = 0;
while ((j < mSize) && (page[i] != memery[j])) //查页表，看是否缺页
j ++;
if (j == mSize)
{
flag = '*'; //缺页，则置标志flag为'*'
sum += 1; //记录缺页次数
if (sum <= mSize) //如果物理块中有空余，则将当前页面直接放入
{
for (j = 0; j < mSize; j ++)
{
if (memery[j] == 0)
{
memery[j] = page[i];
break;
}
}
}
else //物理块已满的情况下
{
for (j = i + 1; j < pSize; j ++) //查找以后不再使用或在最长时间以后才会用到的页
{
for (k = 0; k < mSize; k ++)
{
if (page[j] == memery[k])
{
next[k] += 1; //记录将被使用的次数，可以不用累加
count ++; //记录物理块中以后将即被使用的页面个数
break;
}
}
if (count == mSize - 1) break; //如果已有mSize-1个页面即将被使用，则剩下最后一个页面一定是最长时间后才会用到的页
}
if (count == 0)
memery[0] = page[i];
else
{
count = 0;
for (k = 0; k < mSize; k ++)
{
if (next[k] == 0) //总是置换出第一个可以换出的页
memery[k] = page[i];
next[k] = 0; //初始化next[]数组
}
}
}
}
else flag = ' ';
pflag[i] = flag; //记录当前页的缺页情况
for (k = 0; k < mSize; k ++) //记录每一次的置换情况
table[k][i] = memery[k];
}
Compute();
showTable(page, pSize, mSize);
}
FIFO函数：
void FIFO(int page[], int pSize, int mSize)
{
int i, j;
int memery[MSIZE] = {0}; //存储装入物理块中的页面
sum = 0;
for(i = 0; i < pSize; i++) //查页表，看是否缺页
{
j = 0;
while ((j < mSize) && (page[i] != memery[j]))
j++;
if (j == mSize)
{
flag = '*'; //缺页，则置标志flag为'*'
sum += 1;
for (j = mSize-1; j > 0; j --) //淘汰最先调入的页面，并调入当前页面
memery[j] = memery[j-1];
memery[0] = page[i];
}
else flag = ' ';
pflag[i] = flag;
for (j = 0; j < mSize; j++)
table[j][i] = memery[j];
}
Compute();
showTable(page, pSize, mSize);
}
LRU函数：
void LRU(int page[], int pSize, int mSize)
{
int i, j, k;
int memery[MSIZE] = {0}; //存储装入物理块中的页面
sum = 0;
for (i = 0; i < pSize; i ++)
{
j = 0;
while ((j < mSize) && (page[i] != memery[j])) //查页表，看是否缺页
j ++;
if (j == mSize)
{
flag = '*'; //缺页，则置标志flag为'*'
sum += 1;
k = j - 1;
}
else
{
flag = ' ';
k = j;
}
pflag[i] = flag; //记录当前页的缺页情况
while (k > 0) //总是把最长时间内未被使用的页放在最后一页
{
memery[k] = memery[k-1];
k --;
}
memery[0] = page[i]; //调入当前页面
for (k = 0; k < mSize; k ++) //记录每一次的置换情况
table[k][i] = memery[k];
}
Compute();
showTable(page, pSize, mSize);
}
LFU函数：
void LFU(int page[], int pSize, int mSize)
{
int i, j, replace; //replace标记使用次数最少的页
int use[MSIZE] = {0}; //记录当前各页已使用次数, 其中use[0]中存放使用次数最少的页的次数
int memery[MSIZE] = {0}; //存储装入物理块中的页面
sum = 0;
for (i = 0; i < pSize; i ++)
{
use[page[i]] += 1; //下标即为页号
j = 0;
while ((j < mSize) && (page[i] != memery[j])) //查页表，看是否缺页
j ++;
if (j == mSize)
{
flag = '*'; //缺页，则置标志flag为'*'
sum += 1;
if (sum <= mSize) //如果物理块中有空余，则将当前页面直接放入
{
for (j = 0; j < mSize; j ++)
{
if (memery[j] == 0)
{
memery[j] = page[i];
break;
}
}
}
else //物理块已满的情况下
{
use[0] = 100;
for (j = 0; j < mSize; j ++) //在已放入物理块的页中查找当前使用次数最少的页
{
if (use[memery[j]] < use[0])
{
use[0] = use[memery[j]];
replace = j; //标记页号
}
}
memery[replace] = page[i];
}
}
else
flag = ' ';
pflag[i] = flag; //记录当前页的缺页情况
for (j = 0; j < mSize; j ++) //记录每一次的置换情况
table[j][i] = memery[j];
}
Compute();
showTable(page, pSize, mSize);
}
辅助函数
Designer函数：
void Designer()
{
printf("┏━━━━━━━━━━━━━━━━━━━━━━━━━┓\n");
printf("┃◎◎◎ 课题：页面置换算法 ◎◎◎┃\n");
printf("┃◎◎◎ 学号：11150038 ◎◎◎┃\n");
printf("┃◎◎◎ 姓名：李艳平 ◎◎◎┃\n");
printf("┃◎◎◎ <Visual C++ 6.0> ◎◎◎┃\n");
printf("┗━━━━━━━━━━━━━━━━━━━━━━━━━┛\n");
}
mDelay函数：
void mDelay(unsigned int Delay)
{
unsigned int i;
while (Delay > 0)
{
for (i = 0; i < 125; i++)
printf(" \b");
Delay--;
}
}
Download函数：
void Download(int pSize, int mSize)
{
int i;
system("color 0D");
printf("┏┅┅┅┅┅┅┅┅┅┅┅┅┓\n");
printf("┇正在载入数据，请稍后... ┇\n");
printf("┗┅┅┅┅┅┅┅┅┅┅┅┅┛\n");
printf("Loading...\n");
printf(" 0\n");
for (i = 0; i < 51; i++)
printf("\b");
for (i = 0; i < 50; i++)
{
mDelay((pSize+mSize)/2);
printf(">");
}
printf("\nFinish.\n载入成功，按任意键进入置换算法选择界面：>>>");
getchar();
}
Compute函数：
void Compute()
{
int i;
printf("正在进行相关计算，请稍候...\n");
for(i=1;i<20;i++)
{
mDelay(15);
if(i%4==0)
printf("\b\b\b\b\b\b \b\b\b\b\b\b");
else
printf(">>>");
}
for(i=0;i++<30;printf("\b"));
for(i=0;i++<30;printf(" "));
for(i=0;i++<30;printf("\b"));
}
showTable函数：
void showTable(int page[], int pSize, int mSize)
{
int i, j;
/*printf("即将进入物理块的页面序列为:\n");
for (i = 0; i < pSize; i ++)
printf("%3d", page[i]);
printf("\n输出置换过程，“*”标记缺页中断处\n");*/
for (i = 0; i < mSize; i ++)
{
for (j = 0; j < pSize; j ++)
printf("%3d", table[i][j]);
printf("\n");
}
for (i = 0; i < pSize; i ++)
printf("%3c", pflag[i]);
printf("\n━━━━━━━━━━━━━━━━━━━━━━━━━━━━\n");
printf("总的缺页次数为：%d\n", sum);
printf("缺页中断率为：%.2lf%%\n", 100.0 * sum / pSize);
printf("◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ ◆ \n");
}
第五部分 实现源代码
#include <stdio.h>
#include <stdlib.h>
/*宏定义*/
#define MSIZE 10 //最大物理块数
#define PSIZE 50 //最大页面数
/*全局变量*/
char flag, pflag[PSIZE]; //缺页标志
int table[MSIZE][PSIZE]; //存放置换记录
int sum = 0; //记录每个算法的缺页次数
/*置换算法函数*/
void OPT(int page[], int pSize, int mSize); //最佳置换算法
void FIFO(int page[], int pSize, int mSize); //先进先出置换算法
void LRU(int page[], int pSize, int mSize); //最久未使用置换算法
void LFU(int page[], int pSize, int mSize); //最不经常使用淘汰算法(当前使用次数最少)
/*辅助函数*/
void Designer(); //显示设计者信息
void mDelay(unsigned int Delay); //设置延迟
void Download(int pSize, int mSize); //载入数据
void Compute(); //计算过程延迟
void showTable(int page[], int pSize, int mSize); //输出置换过程
【主函数及其他函数详见第四部分】
第六部分 简要的使用说明及主要运行界面
主要运行界面：
【运行环境——Visual C++ 6.0】
(1)按任意键继续：
（2）载入数据：
（3）进入置换算法选择界面：
（4）运算中延迟操作：
（5）四种算法演示结果：
（6）退出界面：
第七部分 总结（特色、经验、教训和感受）
两周的课程设计结束了，在这次的课程设计中不仅检验了我所学习的知识，也培养了我如何去把握一件事情，如何去做一件事情，如何去坚持一件事情，又如何完成一件事情。
在这次设计过程中，体现出自己单独设计模具的能力以及综合运用知识的能力，体会了学以致用、突出自己劳动成果的喜悦心情，从中发现自己平时学习的不足和薄弱环节，从而加以弥补，同时对页面置换算法有了更深入的了解。虽然在写算法的过程中遇到了一些麻烦，但经过我的坚持不懈最终解决了问题。
同时感谢对我帮助过的同学们，谢谢你们对我的帮助和支持，让我感受到同学的友谊。由于本人的设计能力有限，在设计过程中难免出现错误，恳请老师们多多指教,我十分乐意接受你们的批评与指正，本人将万分感谢。
第八部分 参考文献
C语言程序设计 中国水利水电出版社
计算机操作系统 庞丽萍编著 人民邮电出版社
-
计算机操作系统课程设计报告
《操作系统原理》实验报告院（部）：管理工程学院专业：信息管理与信息系统实验项目：实验一二三五班级：信管102姓名：学号：目录引言.…
-
操作系统课程设计报告模板
西安郵電大學操作系统设计报告题目进程线程互斥锁院系名称计算机学院班级1104学生姓名赵大伟学号8位04113124指导教师舒新峰设…
- 操作系统课程设计总结报告(白雪娇20xx3823)
-
操作系统课程设计报告范例
操作系统课程论文院系班级姓名学号指导教师完成时间东莞理工学院摘要本文分析面向对象教学操作系统EOS的系统结构和代码构成通过源代码分…
-
操作系统课程设计实验报告
操作系统课程设计实验报告姓名学号班级地点20xx年月日任务说明共完成四个任务任务一IO系统调用开销比较任务二实现一个简单的shel…
-
操作系统课程设计试验报告格式
四川大学操作系统课程设计报告学院专业年级组编号组成员软件学院第X组乔心轲姓名0743111340学号张雯姓名XXXXXXXX学号康…
-
计算机操作系统课程设计报告
《操作系统原理》实验报告院（部）：管理工程学院专业：信息管理与信息系统实验项目：实验一二三五班级：信管102姓名：学号：目录引言.…
-
操作系统课程设计报告
操作系统课程设计报告专业学号姓名提交日期操作系统课程设计报告设计目的1本实验的目的是通过一个简单多用户文件系统的设计加深理解文件系…
-
操作系统课程设计报告
上海电力学院计算机操作系统原理课程设计报告题目名称编写程序模拟虚拟存储器管理姓名杜志豪学号20xx1798班级20xx053班同组…
-
操作系统课程设计报告
课程设计说明书设计题目操作系统课程设计班级信管学号姓名山东科技大学20xx年12月15日课程设计任务书学院信息学院专业信息管理与信…
- 操作系统课程设计总结报告(白雪娇20xx3823)