操作系统
课程设计说明书
班级：_______________ 学号：_______________ 姓名：_______________ 指导教师：___________
电子与信息工程学院计算机科学系
1
《操作系统》课程设计
1 设计题目
1.2 内存管理
设计并实现一个可完整演示操作系统中请求分页系统的内存分配、地址变换、页面置换等过程的演示系统。
1.2.1 实验目的
通过本设计：
理解内存分页机制 掌握页面置换算法
理解虚拟存储器的实现过程
1.2.2 准备知识
程序设计语言（C/C++/Java）
数据结构（结构体、链表、队列等） 基本分页存储管理方式 虚拟存储器概念 请求分页存储管理方式 页面置换算法
1.2.3 设计内容
设计和实现基本分页存储管理的数据结构（包括物理块、页、进程空间、页表等的模
拟）
实现基于固定分配局部置换策略的分页式存储分配
实现最佳、先进先出、LRU置换算法（栈式和寄存器方式任选其一） 用上面实现的算法以至少三组以上的页面请求序列，从缺页率角度比较页面置换算法的性能
设计必要的UI，接收用户输入的运行参数（页和物理课大小、逻辑和物理地址空间大小、进程驻留集大小、置换算法选择、页面请求序列等），输出运行过程及结果（每个页面请求前后页表情况、快表情况、内存使用情况、被置换页面的选择过程及结果等）。可采用命令行、桌面版或者Web版形式。
1
《操作系统》课程设计
2 设计思路
经过两天时间仔细研地究题目，我将本次设计划分为两部分，一部分为基本分页存储管
理系统的模拟，另一部分为基于固定分配局部置换的页面算法实现。
基本分页存储管理系统的模拟，我主要侧重于分页系统的地址变换机构的实现，即输入一个逻辑地址，将其所指向的逻辑空间中数据存入对应的物理地址所指向的空间，逻辑和物理空间大小采用输入逻辑和物理空间的地址大小控制。此外，本程序还用位示图显示内存存储状况，用以显示存入数据的结果。页表方面采用手工输入方式。块表更新采用类似最近最久未使用算法思想。
页面置换算法方面参考了《计算机操作系统》的算法思想。其中属最佳置换算法最难实现，耗费时间最长。先进先出置换算法采用队列结构，最近最久未使用置换算法采用栈结构。 最后的UI设计，采用的是VC++6.0自带的程序运行命令行形式。
3 功能模块图
3.1 opks1.c（基本分页管理系统）
基本分页存里管理系统 输入 输出 退出 存储
输出页表 输出块表 输出内存位示图
2
《操作系统》课程设计
3.2 opks2.c（页面置换算法模拟）
页面置换系输入数据
OPT算法 输出过程、结果及缺页率 统 FIFO算法 输出过程、结果及缺页率 LRU算法 输出过程、结果及缺页率 退出 3
《操作系统》课程设计
4 主要程序流程图
opks1.c main()
4
《操作系统》课程设计
create(): showyb():
showkb():
shownc();
5
《操作系统》课程设计
work():
6
《操作系统》课程设计
Opks2.c main():
creat():
in();
7
《操作系统》课程设计
print():
8
《操作系统》课程设计
OPT();
9
《操作系统》课程设计
10
《操作系统》课程设计
FIFO():
11
《操作系统》课程设计
LRU( ):
12
《操作系统》课程设计
5 程序说明
5.1 开发及运行环境
本程序的开发及运行环境为Microsoft Visual C++ 6.0。
5.2 代码结构
5.2.1 opks1.c（基本页面存储管理系统）
顶层目录：opks1.c：基本分页存储管理系统 二层目录：int main( )：主函数
三层目录：void CreatA(); 内存初始化 void showyb(); 显示页表 void showkb(); 显示快表
void shownc(); 显示内存块使用情况
5.2.1 opks2.c（页面置换算法模拟）
顶层目录：opks2.c：页面置换算法模拟 二层目录：int main( )：主函数 三层目录： void creat( ); 初始化
void OPT( ); 最佳置换算法
void FIFO( ); 先进先出置换算法
void LRU( ); 最近最久未使用置换算法 void in( ); 数据输入函数 void print( ); 数据输出函数
13
《操作系统》课程设计
6 主要代码
6.1 opks1.c（基本分页管理系统）
#include int max;//逻辑和物理地址空间大小 int * A;//内存物理块，0：未使用，非0：已使用 int count; //记录内存未使用物理块数 int kysize;//块页大小 int *yb;//页表 struct kb { int yh;//页号 int kh;//块号 struct kb *front; struct kb *next; }; int main() { //struct LNode *L = NULL; int i = 0; struct kb a,b,c,d,e,*head; void CreatA(); //内存初始化 void showyb();//显示页表 void showkb();//显示快表 void shownc();//显示内存块使用情况，不分进程 struct kb *work(struct kb *L); CreatA(); a.kh=0;a.yh=0; b.kh=0;b.yh=0; c.kh=0;c.yh=0; d.kh=0;d.yh=0; e.kh=0;e.yh=0; head=&a;a.next=&b;b.next=&c;c.next=&d;d.next=&e;e.next=NULL; a.front=NULL;b.front=&a;c.front=&b;d.front=&c;e.front=&d; printf(\"\\n******* 基本分页算法 *******\\n\"); do 14 《操作系统》课程设计 { printf(\"\\n***********菜单*************\\n\"); printf( \" 1 装入\\n\"); printf( \" 2 查看页表\\n\"); printf( \" 3 查看快表\\n\"); printf( \" 4 查看内存\\n\"); printf( \" 5 退出程序\\n\"); printf( \"****************************\\n\"); printf(\"请输入你的选择(select):\"); scanf(\"%d\ switch(i) { case 1: head=work(head); break; case 2: showyb(); break; case 3: showkb(head); break; case 4: shownc(); break; case 5: printf(\"谢谢使用\\n\\n\"); exit(0); break; } }while(i != 0); return 0; } //内存初始化 void CreatA() { int i; printf(\"请输入逻辑和物理地址空间大小：\\n\"); scanf(\"%d\ printf(\"请输入物理块大小：\\n\"); scanf(\"%d\ A=(int *)malloc((max-1)*sizeof(int)); count=max-1; yb=(int *)malloc((max/kysize)*sizeof(int)); 15 《操作系统》课程设计 printf(\"请手动输入页表\\n\"); for(i=0;i<(max/kysize);i++) scanf(\"%d\ for(i = 0;i<=max;i++) A[i]=0; } //装入 struct kb *work(struct kb *L ) { int lgad;//逻辑地址 int name;//代表了名，标志，数据 int k1,k2,k3;//k1为页号，k2为偏移地址,k3为物理地址 struct kb *p; printf(\"请输入逻辑地址：\\n\"); scanf(\"%d\ printf(\"请输入数据\\n\"); scanf(\"%d\ k1=lgad/kysize; k2=lgad%kysize; p=L; while(p->yh!=k1&&p->next!=NULL) {p=p->next;} if(p->yh!=k1) {p->front->next=NULL;p->front=NULL;p->next=L;L->front=p;p->yh=k1;p->kh=yb[k1];} else if(p->yh==k1&&p->next==NULL) {p->front->next=NULL;p->front=NULL;p->next=L;L->front=p;} else if(p->yh==k1&&p->front!=NULL) {p->front->next=p->next;p->next->front=p->front;p->front=NULL;p->next=L;L->front=p;} else if(p->front==NULL&&p->yh==k1) { k3=p->kh*kysize+k2; A[k3]=name; return L; } k3=p->kh*kysize+k2; A[k3]=name; return p; } //显示页表 void showyb() { int i; printf(\"\\n****************************\\n\"); printf(\"| 页表 |\\n\"); printf(\"****************************\\n\"); 16 《操作系统》课程设计 for(i=0;i<(max/kysize);i++) printf(\"%d \} //显示快表 void showkb(struct kb *L) { struct kb *p; printf(\"\\n****************************\\n\"); printf(\"| 快表 |\\n\"); printf(\"****************************\\n\"); p=L; while(p!=NULL) { printf(\"%d %d\\n\ p=p->next; } } //显示内存块使用情况，不分进程 void shownc() { int i = 0; printf(\"\\n****************************\\n\"); printf(\"| 内存物理块分配情况 |\\n\"); printf(\"****************************\\n\"); for(i = 0; i < max; i++) { printf(\"%d\\ if(i%10 == 9) printf(\"\\n\"); } } 6.2 opks2.c（页面置换算法模拟） #include 17 《操作系统》课程设计 int main() { int i; void creat();//初始化 void OPT(); void FIFO(); void LRU(); void in(); void print(); creat(); do { printf(\"\\n******************菜单******************\\n\"); printf( \" 1 请输入页面请求序列\\n\"); printf( \" 2 请选择最佳（Optimal）置换算法\\n\"); printf( \" 3 请选择先进先出置换（FIFO）置换算法\\n\"); printf( \" 4 请选择最近最久未使用（LRU）置换算法\\n\"); printf( \" 5 退出程序\\n\"); printf( \"****************************\\n\"); printf(\"请输入你的选择(select):\"); scanf(\"%d\ switch(i) { case 1: in(); break; case 2: OPT(); break; case 3: FIFO(); break; case 4: LRU(); break; case 5: printf(\"谢谢使用\\n\\n\"); return 0; break; } }while(i != 0); return 0; } //初始化 18 《操作系统》课程设计 void creat() { int i; printf(\"请输入驻留集大小：\\n\"); scanf(\"%d\ zl=(int *)malloc(znum*sizeof(int)); for(i=0;i printf(\"请输入页面请求序列大小：\\n\"); scanf(\"%d\ qq=(int *)malloc(qnum*sizeof(int)); printf(\"请输入页面请求序列：\\n\"); for(i=0;i for(i=0;i int cout=0;//记录缺页数 //float v;//缺页率 int i,j,q,max,t,y,z; int bz; int *jl=(int *)malloc(znum*sizeof(int)); y=i=0;z=znum; while(i 《操作系统》课程设计 y++; i++; }//将前znum个不同的页装入驻留集 for(;i int cout=0;//记录缺页数 int i,j,t,y,z; int bz; //int *jl=(int *)malloc(znum*sizeof(int)); y=i=0;z=znum; while(i 《操作系统》课程设计 y++; i++; }//将前znum个不同的页装入驻留集 for(;i int cout=0;//记录缺页数 int i,j,q,t; int bz; for(i=0;i for(j=0;j if(bz==0){for(j=j-1;j>0;j--){t=j-1;zl[j]=zl[t];}zl[j]=qq[i];cout++;}//若缺页 if(bz==1&&j!=0){q=zl[j];for(;j>0;j--){t=j-1;zl[j]=zl[t];}zl[j]=q;}//不缺页，且不为栈顶 printf(\"%d: \ print(); } printf(\"缺页率：%d分之%d\ 21 《操作系统》课程设计 for(j=0;j 因篇幅问题不能全部显示，请点此查看更多更全内容