操作系统课程设计35285158

中北大学中北大学 操作系统课程设计操作系统课程设计 说说 明明 书书 学学 院院 系系 软件学院 专专 业业 软件工程 学学 生生 姓姓 名 名 吕国宏 学学 号 号 0921010830 设设 计计 题题 目目 基于 Linux 的模拟存储器管理的设计 与 实现 起起 迄迄 日日 期期 2011 年 12 月 22 日 2012 年 1 月 5 日 指指 导导 教教 师师 康珺 1 2012 年 1 月 5 日 1 需求分析需求分析 通过模拟实现请求页式存储管理的几种基本页面置换算法 了解虚拟存储技术的特点 掌 握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程 并比较它 们的效率 1 在内存开辟两块存储空间 分别模拟内存和外存 大小分别是 8M 25M 2 给定三个文件 A B C 大小分别是 4 2M 8M 和 9 8M 模拟其并发执行过程 3 每个进程在内存中固定分配 4 个页面 缺页时分别采用四种置换算法 FIFO LRU NUR OPT 进行置换 4 假定页面大小为 512K 进程执行时页面调度顺序要求手动输入 要求 要求在屏幕上输出各进程页面置换过程 以图表形式描述 以及每种页面置换算法的缺 页率和置换率 并对比各算法的优劣 2总体设计总体设计 在进程运行过程中 若其所要访问的页面不在内存而需把它们调入内存 但内存已无空闲 空间时 为了保证该进程能正常运行 系统必须从内存中调出一页程序或数据 送磁盘的 对换区中 但应将哪个页面调出 须根据一定的算法来确定 一个好的页面置换算法 应 具有较低的页面更换频率 从理论上讲 应将那些以后不再会访问的页面换出 或将那些 在较长时间内不会再访问的页面调出 本程序是在 linux 环境下进行调试 采用 C 语言进行设计 模拟三个进程执行时系统 内存页面的四种置换算法 FIFO 先进先出置换算法 OPT 最佳置换算法 LRU 最近最 久未使用算法 NUR 最近最少使用算法 先建立全局变量 num 存入内存中程序访问序列 建立 block 结构体模拟内存物理块 对 访问的页面序列 先检测 block 中是否存在要访问的页面 若不存在则检测内存是否有空 闲的物理块 若有则直接将要访问的页面加入 block 若不存在则根据选择不同的算法进行 页面置换 依次进行遍历 num 直至结束 2 3 3 详细设计 详细设计 FIFO 初始化内存单元及缓冲区 输入页面串 该页面存于缓冲区中 并设置相应的时间 该页存于内存中 记录当前内存单元中的页面 结果输出 退出 是 是 否 是 否 输入物理块数 i 否 是 判断页面是否在内存中 判断 0 i 10 LRU 读入页面 查找应予置换的页 面 替换掉页面 是否还有未读页面 否 是否继续 开始 入口 OPTNUR 3 程序源代码 include include define pagesize 4 页面尺寸大小 物理块数 typedef struct BLOCK 声明一种新类型 物理块类型 int pagenum 页号 int accessed 访问量 其值表示多久未被访问 BLOCK int pc 程序计数器 用来记录对应的页号 int n 缺页计数器 用来记录缺页的次数 static int num 10 用来存储 320 条随机数 BLOCK block pagesize 定义一大小为 8 的物理块数组 void init 程序初始化函数 int findExist int curpage 查找物理块中是否有该页面 int findSpace 查找是否有空闲物理块 4 int findReplace 查找应予置换的页面 void display 显示 void pagestring 显示调用的页面队列 void OPT void LRU void FIFO void input void NUR int main int select printf 请输入第一个随机数 0 320 randam input printf 对应的调用页面队列 n pagestring do printf n printf 1 OPT 吕国宏 n printf 2 LRU 段子彧 n printf 3 FIFO 卜一川 n printf 4 NUR 雷旭东 n printf n printf 请选择一种页面置换算法 scanf d printf n 5 init switch select case 1 printf 最佳置换算法 OPT n printf n OPT break case 2 printf 最近最久未使用置换算法 LRU n printf n LRU break case 3 printf 先进先出置换算法 FIFO n printf n FIFO break case 4 printf 最近最少使用算法 NUR n printf n NUR break while select 5 return 0 6 void init int i for i 0 i pagesize i block i pagenum 1 block i accessed 10 pc n 0 int findExist int curpage int i for i 0 i pagesize i if block i pagenum curpage return i 检测到内存中有该页面 返回 block 中的位置 return 1 int findSpace 7 int i for i 0 i pagesize i if block i pagenum 1 return i 找到空闲的 block 返回 block 中的位置 return 1 int findReplace int pos 0 int i for i 0 i block pos accessed pos i 找到应该置换页面 返回 BLOCK 中位置 return pos void display int i for i 0 i pagesize i 8 if block i pagenum 1 printf 2d block i pagenum printf n void input 输入访问序列 int i printf 请输入访问序列 可以输入 10 个 用空格隔开 n for i 0 i 10 i scanf d void pagestring 显示调用的页面队列 页面号取法为随机数除 10 取整 int i printf 您刚才输入的调度队列 取前 10 个 n for i 0 i 10 i printf 2d num i printf n 9 void NUR 最近最少使用算法 int exist space position int curpage i k j for i 0 i 10 i pc num i curpage pc exist findExist curpage if exist 1 space findSpace if space 1 当内存中有空闲物理块时 block space pagenum curpage display n n 1 else for k 0 k pagesize k for j i j 10 j if block k pagenum num j 当前块号不等于预备队列的块号 10 block k accessed 将来不会用 设置为一个很大数 else block k accessed j 将当前块号访问量赋上预备队列的序 号 block k accessed 越小说明访问次数越多 break position findReplace block position pagenum curpage display n printf 缺页次数 d n n printf 缺页率 f n n 10 0 100 程序运行结果 11