学海网

操作系统课程设计 存储管理

以下是课程设计题目：
一、实验目的
存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。
本实验的目的是通过请求页式存储管理中页面置换算法模拟设计 , 了解虚拟存储技术的特点 , 掌握请求页式存储管理的页面置换算法。
二、实验内容
通过随机数产生一个指令序列,共320条指令。指令的地址按下述原则生成 :
① 50% 的指令是顺序执行的；
② 25% 的指令是均匀分布在前地址部分；
③ 25% 的指令是均匀分布在后地址部分。
具体的实施方法是 :
①在 [0,319] 的指令地址之间随机选取一起点 m;
②顺序执行一条指令;
③在前地址[0,m+1]中随机选取一条指令并执行 , 该指令的地址为 m′;
④顺序执行一条指令 , 其地址为 m′+1;
⑤在后地址 [m′+2,319] 中随机选取一条指令并执行 ;
⑥重复上述步骤② ~ ⑤ , 直到执行 320 次指令。
(1) 将指令序列变换成为页地址流
设：①页面大小为 1K;
②用户内存容量为 4 页到 32 页 ;
③用户虚存容量为 32K 。
在用户虚存中 , 按每 K 存放 10 条指令排列虚存地址 , 即 320 条指令在虚存中的存放方式为 :
第 0 条 ~ 第 9 条指令为第 0 页 ( 对应虚存地址为 [0,9]);
第 10 条 ~ 第 19 条指令为第 1 页 ( 对应虚存地址为 [10,19] ) ;
┇
┇
第 310 条 ~ 第 319 条指令为第 31 页 ( 对应虚存地址为 [310,319]) 。
按以上方式 , 用户指令可组成 32 页。
(2) 计算并输出下述各种算法在不同内存容量下的命中率。
① 先进先出的算法 (FIFO)；
② 最近最少使用算法 (LRR);
③ 最少访问页面算法 (LFR)；
④ 最近最不经常使用算法 (NUR)。

命中率 = 1 - 页面失效次数∕页地址流长度

在本实验中 , 页地址流长度为 320, 页面失效次数为每次访问相应指令时 , 该指令所对应的页不在内存的次数。
三、随机数产生办法
关于随机数产生办法 ,Linux 或 UNIX 系统提供函数 srand( ) 和 rand( ), 分别进行初 始化和产生随机数。例如 :
srand （）;
语句可初始化一个随机数 ;
a[o]=10 * rand( ) / 32767 * 319 + 1;
a[1]= 10 * rand( ) / 32767 * a[o];
┇
语句可用来产生 a[0] 与 a[1] 中的随机数。


以下是实验指导：

【实验内容】
〈任务〉
设计一个虚拟存储区和内存工作区 , 并使用下述算法计算访问命中率。
(1) 先进先出的算法 (FIFO)
(2 )最近最少使用算法 (LRU)
(3) 最佳淘汰算法 (OPT)
(4) 最少访问页面算法 (LFU)
(5 )最近最不经常使用算法 (NUR)

命中率 =(1 一页面失效次数 )/ 页地址流长度

〈程序设计〉
本实验的程序设计基本上按照实验内容进行。即首先用Srand（）和rand（）函数定义
和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算出相应的命中率。相关定义如下：
1. 数据结构
(1) 页面类型
typedef struct{
int pn,pfn,counter,time;
}pl_type;
其中 pn 为页号 ,pfn 为面号 ,counter 为一个周期内访问该页面次数 ,time 为访问时间。
(2) 页面控制结构
struct pfc_struct{
int pn,pfn;
struct pfc_struct *next;
};
typedef struct pfc_struct pfc_type;
pfc_type pfc[total_vp],*freepf_head,*busypf_head,*busypf_tail;
其中 pfc[total_vp] 定义用户进程虚页控制结构 ,
*freepf_head 为空页面头的指针 ,
*busypf_head 为忙页面头的指针 ,
*busypf_tail 为忙页面尾的指针。

2. 函数定义
(1)void initializd(): 初始化函数 , 给每个相关的页面赋值。
(2)void FIFO(): 计算使用 FIFO 算法时的命中率。
(3)void LRU(): 计算使用 LRU 算法时的命中率。
(4)void OPT(): 计算使用 OPT 算法时的命中率。



以下是部分源代码：
// test_1.cpp : 定义控制台应用程序的入口点。
//
/**************************************************************
*此程序为页面调度程序，用于模拟虚存与主存之间的页面置换
*并同时采用FIFO,LRU,OPT,LFT,NUR几种算法
*并比较在不同算法下及不同的主存页面状态下，主存的命中率的高低
**************************************************************
*/
#include "stdlib.h"
#include "stdio.h"
#include "time.h"

#define TRUE 1
#define FALSE 0
#define INVALID -1 /*页面失效符*/
#define null 0

#define total_instruction 320 /*指令流长*/
#define total_vp 32 /*虚页长*/
#define clear_period 50 /*清零周期*/

typedef struct
{ /*页面结构*/
int pn,pfn,counter,time;
}pl_type;
/*--pn为页面队列号,pfn为页面控制结构中的页号，counter为访问次数--*/
pl_type pl[total_vp]; /*页面结构数组;建立虚存页面空间*/