实验二 存储理
实验目
通模拟实现请求页式存储理种基页面置换算法解虚拟存储技术特 点掌握虚拟存储请求页式存储理中种基页面置换算法基思想实现程 较效率
二 实验容
基虚拟存储区存工作区设计述算法计算访问命中率
1佳淘汰算法（OPT）
2先进先出算法（FIFO）
3久未算法（LRU）
4简单时钟(钟表)算法（CLOCK）
命中率＝１－页面失效次数／页址流(序列)长度
三 实验原理简述
UNIX中提高存利率提供外存进程换机制存空间分配回收均页单位进行进程需部分（段页）调入存便运行支持请求调页存储理方式
进程运行中需访问某部分程序数时发现页面存立提出请求（CPU发出缺中断）系统需页面调入存种页面调入方式请求调页
实现请求调页核心配置四种数结构：页表页帧（框）号访问位修改位效位保护位等
CPU接收缺页中断信号中断处理程序先保存现场分析中断原转入缺页中断处理程序该程序通查找页表该页外存物理块号果时存未满容纳新页启动磁盘IO缺页调入存然修改页表果存已满须某种置换算法存中选出页准备换出否重新写盘页表修改位决定然缺页调入修改页表利修改页表形成访问数物理址访问存数整页面调入程户透明
四 算法描述
实验程序设计基实验容进行srand( )rand( )函数定 义产生指令序列然指令序列变换成相应页址流针算 法计算出相应命中率
（1）通机数产生指令序列320条指令指令址述原生成：
A：50指令序执行
B：25指令均匀分布前址部分
C：25指令均匀分布址部分
具体实施方法：
A：[0319]指令址间机选取起点m
B：序执行条指令执行址m+1指令
C：前址[0m+1]中机选取条指令执行该指令址m’
D：序执行条指令址m’+1
E：址[m’+2319]中机选取条指令执行
F：重复步骤AE直320次指令
（2）指令序列变换页址流
设：页面1K
户存（页帧）容量4页~32页
户虚存容量32K
户虚存中K存放10条指令排列虚存址320条指令虚存中存放方式：
第 0 条第 9 条指令第0页（应虚存址[09]）
第10条第19条指令第1页（应虚存址[1019]）
………………………………
第310条第319条指令第31页（应虚存址[310319]）
方式户指令组成32页
五 算法实现分析
1常量变量
#define total_instruction 320 指令流长
#define total_vp 32 虚页长
#define clear_period 50 清周期
pfc_type pfc[total_vp] 存区页面控制结构数组
pfc_type *freepf_head 存区页面控制结构空闲页面头指针
pfc_type *busypf_head 存区页面控制结构忙页面头指针
pfc_type *busypf_tail 存区页面控制结构忙页面尾指针
int diseffect 页错误计数器初次页面载入存时做页错误
pl_type pl[total_vp] 页面结构数组
2数结构
typedef struct 页面结构
{
int pn 页面序号
pfn 页面存区帧号
counter 单位时间访问次数
time 次访问时间
}pl_type
struct pfc_struct{ 页面控制结构模拟存中页集
int pn 页面号
pfn 存区页面帧号
struct pfc_struct *next 页面指针维护存缓区链式结构
}
3函数定义
int initialize(int) 初始化页面结构数组页面控制结构数组
int FIFO(int) 先进先出算法
int LRU(int) 久未算法
int OPT(int) 佳置换算法
int CLOCK(int) 简单时钟(钟表)算法
六 实验结果分析
实验数结果：
机产生指令流
257 258 37 38
226 227 109 110
184 185 164 165
166 167 59 60
310 311 135 136
148 149 105 106
240 241 121 122
124 125 50 51
315 316 308 309
312 313 299 300
315 316 284 285
284 285 272 273
318 319 216 217
310 311 266 267
318 319 127 128
129 130 52 53
53 54 48 49
130 131 62 63
159 160 107 108
206 207 130 131
167 168 123 124
272 273 23 24
123 124 32 33
303 304 163 164
206 207 134 135
269 270 123 124
177 178 124 125
244 245 54 55
68 69 5 6
165 166 144 145
270 271 75 76
88 89 65 66
69 70 31 32
56 57 40 41
189 190 73 74
92 93 50 51
92 93 77 78
88 89 62 63
125 126 71 72
255 256 125 126
289 290 97 98
235 236 163 164
240 241 29 30
158 159 80 81
280 281 263 264
312 313 58 59
226 227 78 79
121 122 108 109
202 203 32 33
42 43 18 19
153 154 67 68
292 293 63 64
264 265 54 55
269 270 40 41
296 297 295 296
318 319 269 270
278 279 214 215
222 223 186 187
220 221 30 31
268 269 33 34
226 227 117 118
211 212 170 171
313 314 77 78
248 249 34 35
232 233 25 26
82 83 59 60
61 62 23 24
168 169 24 25
259 260 239 240
318 319 275 276
283 284 74 75
244 245 144 145
244 245 86 87
120 121 115 116
238 239 209 210
275 276 215 216
284 285 214 215
285 286 186 187
208 209 162 163
238 239 41 42
页面工作区种换策略命中率表
Page FIFO LRU OPT CLOCK
4 0550 0559 0669 0550
5 0566 0572 0700 0572
6 0578 0594 0722 0578
7 0591 0603 0741 0597
8 0631 0628 0756 0637
9 0637 0656 0772 0650
10 0641 0669 0787 0653
11 0656 0678 0800 0666
12 0688 0684 0813 0672
13 0703 0697 0822 0697
14 0713 0713 0831 0719
15 0722 0728 0841 0722
16 0731 0747 0850 0741
17 0744 0772 0856 0747
18 0769 0778 0863 0769
19 0778 0787 0869 0778
20 0781 0797 0875 0794
21 0787 0800 0881 0806
22 0816 0809 0887 0809
23 0822 0822 0891 0822
24 0838 0831 0894 0838
25 0844 0847 0897 0841
26 0847 0856 0900 0856
27 0847 0869 0900 0859
28 0856 0878 0900 0872
29 0859 0884 0900 0878
30 0881 0891 0900 0891
31 0897 0897 0900 0897
32 0900 0900 0900 0900
请意键继续
结果分析：
理四种换算法命中率高底排列应该OPT>LRU>CLOCK>FIFO实际实验数观测存种高低趋势page4时观测效果明显
效果明显原：
推测指令流产生方式关系指令流产生方式体现局部性原理该指令流产生设计：50指令序执25指令均匀分布前址部分25指令均匀分布址部分样指令流设计方式否佳体现局部性原理验证
时估计指令数量关系320条指令太少通常稍点程序千行指令
数产生具定波动性该命中率计算定波动性会局部实验数理符改进方法次实验取均值样减波动实验数更加滑
唯显著OPT算法命中率3调度算法保持较差距例page26时OPT算法达09命中率
期page越越越越容易命中换算法命中率差距变行命中率相似出
七 实验总结
次实验实定linux操作系统做windows操作系统样实现头文件稍作修改保险起见2操作系统编译没问题windows操作系统屏蔽#include句话linux操作系统启
次实验助老师提供函数main模板需写FIFOLRUOPTCLOCK等4换算法阻力没换算法必须弄懂中细节写起心应手 开始做实验时首先书先书换算法知识点弄明白明白种算法优缺点相互间衍生互补关系四算法中难实现LRU算法涉访问时间计算开销较OPT算法次难需计算访问时间换访问时间页FIFOCLOCK实现起较容易FIFO算法实现CLOCK算法实现相似FIFO视CLOCK退化版先写CLOCK算法删约束条件退化FIFO算法两者相处理CLOCK算法需维持循环存缓区需循环队列实现FIFO算法保持先进先出需先进先出队列实现两算法单链表数结构剩中指针握必须指针敏锐感觉
八 程序源码（两系统通）
#include
#include
#include window操作系统屏蔽条指令
#include
#ifndef _UNISTD_H
#define _UNISTD_H
#include
#include
#endif
#define TRUE 1
#define FALSE 0
#define INVALID 1
#define total_instruction 320 指令流长
#define total_vp 32 虚页长
#define clear_period 50 清周期
typedef struct 页面结构
{
int pn 页面序号
pfn 页面存区帧号
counter 单位时间访问次数
time 次访问时间
}pl_type
pl_type pl[total_vp] 页面结构数组
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 存区页面控制结构忙页面尾指针
int diseffect 页错误计数器初次页面载入存时做页错误
int a[total_instruction] 指令流数组
int page[total_instruction] 指令应页面号
int offset[total_instruction] 指令页面中偏移量
int initialize(int) 初始化页面结构数组页面控制结构数组
int FIFO(int) 先进先出算法
int LRU(int) 久未算法
int OPT(int) 佳置换算法
int CLOCK(int) 简单时钟(钟表)算法
int main( )
{
int s 机数
int i
srand(10*getpid()) *次运行时进程号作初始化机数队列种子*
s (int)((float)(total_instruction1)*(rand()(RAND_MAX+10)))
printf(＼n机产生指令流＼n)
for (i0 i {
a[i]s 选指令访问点m
a[i+1]a[i]+1 序执行条指令
a[i+2](int)((float)a[i]*(rand()(RAND_MAX+10))) 执行前址指令m＇
a[i+3]a[i+2]+1 序执行条指令
printf(6d6d6d6d＼n a[i]a[i+1]a[i+2]a[i+3])
s (int)((float)((total_instruction1)a[i+2])*(rand()(RAND_MAX+10))) + a[i+2]
}
printf(＼n)
for (i0i {
page[i]a[i]10
offset[i]a[i]10
}
printf(＼n页面工作区种换策略命中率表＼n)
printf(Page＼t FIFO＼t LRU＼t OPT＼t CLOCK＼n)
for(i4i<32i++) 户存工作区页面页面
{
printf( 2d ＼ti)
FIFO(i)
LRU(i)
OPT(i)
CLOCK(i)
printf(＼n)
}
return 0
}
初始化页面结构数组页面控制结构数组
total_pf 户进程存页面数
int initialize(int total_pf)
{
int i
diseffect0
for(i0i {
pl[i]pni
pl[i]pfnINVALID 置页面存区帧号1表示该页存中
pl[i]counter0 置页面结构中访问次数
pl[i]time1 置页面结构中次访问时间1
}
for(i0i {
pfc[i]next&pfc[i+1] 建立pfc[i1]pfc[i]间链接
pfc[i]pfni 初始化存区页面帧号
}
pfc[total_pf1]nextNULL
pfc[total_pf1]pfntotal_pf1
freepf_head&pfc[0] 存区页面控制结构空闲页面头指针指pfc[0]
return 0
}
久未算法
int total_pf 户进程存页面数
int LRU (int total_pf)
{
int MinT 访问时间久没访问
int MinPn 拥访问时间页页号
int ij
int CurrentTime 系统前时间
initialize(total_pf) 初始化页面结构数组页面控制结构数组
CurrentTime0
diseffect0
for(i0i {
if(pl[page[i]]pfnINVALID) 页面失效
{
diseffect++ 页错误次数加
if(freepf_headNULL) 空闲页面
{
MinT100000
for(j0j if(MinT>pl[j]time&&pl[j]pfnINVALID)
{
MinTpl[j]time
MinPnj
}
}
freepf_head&pfc[pl[MinPn]pfn] 久没访问页释放
pl[MinPn]pfnINVALID 久没访问页换出存
pl[MinPn]time1 久没访问页访问时间置效
freepf_head>nextNULL
}
pl[page[i]]pfnfreepf_head>pfn 空闲页面相应页面换入存pfn改相应帧号
pl[page[i]]timeCurrentTime 令访问时间前系统时间
freepf_headfreepf_head>next 减少空闲页面
}
else
pl[page[i]]timeCurrentTime 命中刷新该单元访问时间
CurrentTime++ 系统前时间加
}
printf(63f＼t1(float)diseffect320)
return 0
}
佳置换算法
int total_pf 户进程存页面数
int OPT(int total_pf)
{
int ij
int MaxD 次访问距离值（时间单元度量）
int MaxPn 次访问距离值页号
int dis 距离计数器
int dist[total_vp] 距离数组保存距离次访问时间差距数
initialize(total_pf) 初始化页面结构数组页面控制结构数组
diseffect0
for(i0i {
if(pl[page[i]]pfnINVALID) 页面失效
{
diseffect++ 页错误次数加
if(freepf_headNULL) 空闲页面
{
for(j0j {
if(pl[j]pfnINVALID) 果该页存中
dist[j]100000 该页关联距离值改值
else
dist[j]0 果该页存中该页关联距离值改
}
dis1 初始距离值
for(ji+1j {
if(pl[page[j]]pfnINVALID &&pl[page[j]]counter0) 果该页存中访问页
if(pl[page[j]]pfnINVALID && dist[page[j]]100000) 条语句原理相
{ dist[page[j]]dis 距离值改dis
pl[page[j]]counter1 访问次数标志加区第次访问第二次访问
}
dis++
}
MaxD1
for(j0j {
pl[j]counter0 重置访问次数
if(MaxD {
MaxDdist[j]
MaxPnj
}
}
freepf_head&pfc[pl[MaxPn]pfn] 换段时间久访问页
freepf_head>nextNULL
pl[MaxPn]pfnINVALID
}
pl[page[i]]pfnfreepf_head>pfn 前页换入存中前页pfn改换入页帧号
freepf_headfreepf_head>next 减少空闲页面
}if
}for
printf(63f＼t1(float)diseffect320)
return 0
}
简单时钟算法
int total_pf 户进程存页面数
int CLOCK(int total_pf)
{
int i
int use[total_vp] 位
int swap
swap0 发生换
initialize(total_pf)
pfc_type *pnext 时钟指针
pfc_type *head 队列头指针
pnextfreepf_head
headfreepf_head
for(i0i diseffect0
for(i0i {
if (pl[page[i]]pfnINVALID) 页面失效存中
{
diseffect++ 页错误次数加
if(freepf_headNULL) 空闲页面
{
while(use[pnext>pfn]1) 时钟指针指页位改跳
{
use[pnext>pfn]0
pnextpnext>next
if(pnextNULL) pnexthead 果时钟指针达队列尾部重新返回头部
}
换出换页
pl[pnext>pn]pfnINVALID
swap1
}
if(use[pnext>pfn]0){ 果位换入相应页
pl[page[i]]pfnpnext>pfn 页面结构中标记帧号
pnext>pnpage[i] 页面控制结构中标记页号
use[pnext>pfn]1 重置位
pnextpnext>next 时钟指针移
if(pnextNULL) pnexthead 果时钟指针达队列尾部重新返回头部
if(swap0){ freepf_headfreepf_head>next }
}
}else{页面存中
use[pl[page[i]]pfn]1 刷新位
}
}
printf(63f＼t1(float)diseffect320)
return 0
}
先进先出算法版
int total_pf 户进程存页面数
实现细节CLOCK算法退化FIFO效果
int FIFO(int total_pf)
{
int i
int use[total_vp]
int swap0
initialize(total_pf)
pfc_type *pnext*head
pnextfreepf_head
headfreepf_head
for(i0i diseffect0
for(i0i {
if (pl[page[i]]pfnINVALID) 页面失效存中
{
diseffect++
if(freepf_headNULL) 空闲页面
{
while(use[pnext>pfn]1)
{
use[pnext>pfn]0
pnextpnext>next
if(pnextNULL) pnexthead
}
换出换页
pl[pnext>pn]pfnINVALID
swap1
}
if(use[pnext>pfn]0){ 果位换入相应页
pl[page[i]]pfnpnext>pfn 页面结构中标记帧号
pnext>pnpage[i] 页面控制结构中标记页号
use[pnext>pfn]1 重置位
pnextpnext>next
if(pnextNULL) pnexthead
if(swap0){ freepf_headfreepf_head>next }
}
}
}
printf(63f＼t1(float)diseffect320)
return 0
}
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档
实验目
通模拟实现请求页式存储理种基页面置换算法解虚拟存储技术特 点掌握虚拟存储请求页式存储理中种基页面置换算法基思想实现程 较效率
二 实验容
基虚拟存储区存工作区设计述算法计算访问命中率
1佳淘汰算法（OPT）
2先进先出算法（FIFO）
3久未算法（LRU）
4简单时钟(钟表)算法（CLOCK）
命中率＝１－页面失效次数／页址流(序列)长度
三 实验原理简述
UNIX中提高存利率提供外存进程换机制存空间分配回收均页单位进行进程需部分（段页）调入存便运行支持请求调页存储理方式
进程运行中需访问某部分程序数时发现页面存立提出请求（CPU发出缺中断）系统需页面调入存种页面调入方式请求调页
实现请求调页核心配置四种数结构：页表页帧（框）号访问位修改位效位保护位等
CPU接收缺页中断信号中断处理程序先保存现场分析中断原转入缺页中断处理程序该程序通查找页表该页外存物理块号果时存未满容纳新页启动磁盘IO缺页调入存然修改页表果存已满须某种置换算法存中选出页准备换出否重新写盘页表修改位决定然缺页调入修改页表利修改页表形成访问数物理址访问存数整页面调入程户透明
四 算法描述
实验程序设计基实验容进行srand( )rand( )函数定 义产生指令序列然指令序列变换成相应页址流针算 法计算出相应命中率
（1）通机数产生指令序列320条指令指令址述原生成：
A：50指令序执行
B：25指令均匀分布前址部分
C：25指令均匀分布址部分
具体实施方法：
A：[0319]指令址间机选取起点m
B：序执行条指令执行址m+1指令
C：前址[0m+1]中机选取条指令执行该指令址m’
D：序执行条指令址m’+1
E：址[m’+2319]中机选取条指令执行
F：重复步骤AE直320次指令
（2）指令序列变换页址流
设：页面1K
户存（页帧）容量4页~32页
户虚存容量32K
户虚存中K存放10条指令排列虚存址320条指令虚存中存放方式：
第 0 条第 9 条指令第0页（应虚存址[09]）
第10条第19条指令第1页（应虚存址[1019]）
………………………………
第310条第319条指令第31页（应虚存址[310319]）
方式户指令组成32页
五 算法实现分析
1常量变量
#define total_instruction 320 指令流长
#define total_vp 32 虚页长
#define clear_period 50 清周期
pfc_type pfc[total_vp] 存区页面控制结构数组
pfc_type *freepf_head 存区页面控制结构空闲页面头指针
pfc_type *busypf_head 存区页面控制结构忙页面头指针
pfc_type *busypf_tail 存区页面控制结构忙页面尾指针
int diseffect 页错误计数器初次页面载入存时做页错误
pl_type pl[total_vp] 页面结构数组
2数结构
typedef struct 页面结构
{
int pn 页面序号
pfn 页面存区帧号
counter 单位时间访问次数
time 次访问时间
}pl_type
struct pfc_struct{ 页面控制结构模拟存中页集
int pn 页面号
pfn 存区页面帧号
struct pfc_struct *next 页面指针维护存缓区链式结构
}
3函数定义
int initialize(int) 初始化页面结构数组页面控制结构数组
int FIFO(int) 先进先出算法
int LRU(int) 久未算法
int OPT(int) 佳置换算法
int CLOCK(int) 简单时钟(钟表)算法
六 实验结果分析
实验数结果：
机产生指令流
257 258 37 38
226 227 109 110
184 185 164 165
166 167 59 60
310 311 135 136
148 149 105 106
240 241 121 122
124 125 50 51
315 316 308 309
312 313 299 300
315 316 284 285
284 285 272 273
318 319 216 217
310 311 266 267
318 319 127 128
129 130 52 53
53 54 48 49
130 131 62 63
159 160 107 108
206 207 130 131
167 168 123 124
272 273 23 24
123 124 32 33
303 304 163 164
206 207 134 135
269 270 123 124
177 178 124 125
244 245 54 55
68 69 5 6
165 166 144 145
270 271 75 76
88 89 65 66
69 70 31 32
56 57 40 41
189 190 73 74
92 93 50 51
92 93 77 78
88 89 62 63
125 126 71 72
255 256 125 126
289 290 97 98
235 236 163 164
240 241 29 30
158 159 80 81
280 281 263 264
312 313 58 59
226 227 78 79
121 122 108 109
202 203 32 33
42 43 18 19
153 154 67 68
292 293 63 64
264 265 54 55
269 270 40 41
296 297 295 296
318 319 269 270
278 279 214 215
222 223 186 187
220 221 30 31
268 269 33 34
226 227 117 118
211 212 170 171
313 314 77 78
248 249 34 35
232 233 25 26
82 83 59 60
61 62 23 24
168 169 24 25
259 260 239 240
318 319 275 276
283 284 74 75
244 245 144 145
244 245 86 87
120 121 115 116
238 239 209 210
275 276 215 216
284 285 214 215
285 286 186 187
208 209 162 163
238 239 41 42
页面工作区种换策略命中率表
Page FIFO LRU OPT CLOCK
4 0550 0559 0669 0550
5 0566 0572 0700 0572
6 0578 0594 0722 0578
7 0591 0603 0741 0597
8 0631 0628 0756 0637
9 0637 0656 0772 0650
10 0641 0669 0787 0653
11 0656 0678 0800 0666
12 0688 0684 0813 0672
13 0703 0697 0822 0697
14 0713 0713 0831 0719
15 0722 0728 0841 0722
16 0731 0747 0850 0741
17 0744 0772 0856 0747
18 0769 0778 0863 0769
19 0778 0787 0869 0778
20 0781 0797 0875 0794
21 0787 0800 0881 0806
22 0816 0809 0887 0809
23 0822 0822 0891 0822
24 0838 0831 0894 0838
25 0844 0847 0897 0841
26 0847 0856 0900 0856
27 0847 0869 0900 0859
28 0856 0878 0900 0872
29 0859 0884 0900 0878
30 0881 0891 0900 0891
31 0897 0897 0900 0897
32 0900 0900 0900 0900
请意键继续
结果分析：
理四种换算法命中率高底排列应该OPT>LRU>CLOCK>FIFO实际实验数观测存种高低趋势page4时观测效果明显
效果明显原：
推测指令流产生方式关系指令流产生方式体现局部性原理该指令流产生设计：50指令序执25指令均匀分布前址部分25指令均匀分布址部分样指令流设计方式否佳体现局部性原理验证
时估计指令数量关系320条指令太少通常稍点程序千行指令
数产生具定波动性该命中率计算定波动性会局部实验数理符改进方法次实验取均值样减波动实验数更加滑
唯显著OPT算法命中率3调度算法保持较差距例page26时OPT算法达09命中率
期page越越越越容易命中换算法命中率差距变行命中率相似出
七 实验总结
次实验实定linux操作系统做windows操作系统样实现头文件稍作修改保险起见2操作系统编译没问题windows操作系统屏蔽#include
次实验助老师提供函数main模板需写FIFOLRUOPTCLOCK等4换算法阻力没换算法必须弄懂中细节写起心应手 开始做实验时首先书先书换算法知识点弄明白明白种算法优缺点相互间衍生互补关系四算法中难实现LRU算法涉访问时间计算开销较OPT算法次难需计算访问时间换访问时间页FIFOCLOCK实现起较容易FIFO算法实现CLOCK算法实现相似FIFO视CLOCK退化版先写CLOCK算法删约束条件退化FIFO算法两者相处理CLOCK算法需维持循环存缓区需循环队列实现FIFO算法保持先进先出需先进先出队列实现两算法单链表数结构剩中指针握必须指针敏锐感觉
八 程序源码（两系统通）
#include
#include
#include
#include
#ifndef _UNISTD_H
#define _UNISTD_H
#include
#include
#endif
#define TRUE 1
#define FALSE 0
#define INVALID 1
#define total_instruction 320 指令流长
#define total_vp 32 虚页长
#define clear_period 50 清周期
typedef struct 页面结构
{
int pn 页面序号
pfn 页面存区帧号
counter 单位时间访问次数
time 次访问时间
}pl_type
pl_type pl[total_vp] 页面结构数组
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 存区页面控制结构忙页面尾指针
int diseffect 页错误计数器初次页面载入存时做页错误
int a[total_instruction] 指令流数组
int page[total_instruction] 指令应页面号
int offset[total_instruction] 指令页面中偏移量
int initialize(int) 初始化页面结构数组页面控制结构数组
int FIFO(int) 先进先出算法
int LRU(int) 久未算法
int OPT(int) 佳置换算法
int CLOCK(int) 简单时钟(钟表)算法
int main( )
{
int s 机数
int i
srand(10*getpid()) *次运行时进程号作初始化机数队列种子*
s (int)((float)(total_instruction1)*(rand()(RAND_MAX+10)))
printf(＼n机产生指令流＼n)
for (i0 i
a[i]s 选指令访问点m
a[i+1]a[i]+1 序执行条指令
a[i+2](int)((float)a[i]*(rand()(RAND_MAX+10))) 执行前址指令m＇
a[i+3]a[i+2]+1 序执行条指令
printf(6d6d6d6d＼n a[i]a[i+1]a[i+2]a[i+3])
s (int)((float)((total_instruction1)a[i+2])*(rand()(RAND_MAX+10))) + a[i+2]
}
printf(＼n)
for (i0i
page[i]a[i]10
offset[i]a[i]10
}
printf(＼n页面工作区种换策略命中率表＼n)
printf(Page＼t FIFO＼t LRU＼t OPT＼t CLOCK＼n)
for(i4i<32i++) 户存工作区页面页面
{
printf( 2d ＼ti)
FIFO(i)
LRU(i)
OPT(i)
CLOCK(i)
printf(＼n)
}
return 0
}
初始化页面结构数组页面控制结构数组
total_pf 户进程存页面数
int initialize(int total_pf)
{
int i
diseffect0
for(i0i
pl[i]pni
pl[i]pfnINVALID 置页面存区帧号1表示该页存中
pl[i]counter0 置页面结构中访问次数
pl[i]time1 置页面结构中次访问时间1
}
for(i0i
pfc[i]next&pfc[i+1] 建立pfc[i1]pfc[i]间链接
pfc[i]pfni 初始化存区页面帧号
}
pfc[total_pf1]nextNULL
pfc[total_pf1]pfntotal_pf1
freepf_head&pfc[0] 存区页面控制结构空闲页面头指针指pfc[0]
return 0
}
久未算法
int total_pf 户进程存页面数
int LRU (int total_pf)
{
int MinT 访问时间久没访问
int MinPn 拥访问时间页页号
int ij
int CurrentTime 系统前时间
initialize(total_pf) 初始化页面结构数组页面控制结构数组
CurrentTime0
diseffect0
for(i0i
if(pl[page[i]]pfnINVALID) 页面失效
{
diseffect++ 页错误次数加
if(freepf_headNULL) 空闲页面
{
MinT100000
for(j0j
{
MinTpl[j]time
MinPnj
}
}
freepf_head&pfc[pl[MinPn]pfn] 久没访问页释放
pl[MinPn]pfnINVALID 久没访问页换出存
pl[MinPn]time1 久没访问页访问时间置效
freepf_head>nextNULL
}
pl[page[i]]pfnfreepf_head>pfn 空闲页面相应页面换入存pfn改相应帧号
pl[page[i]]timeCurrentTime 令访问时间前系统时间
freepf_headfreepf_head>next 减少空闲页面
}
else
pl[page[i]]timeCurrentTime 命中刷新该单元访问时间
CurrentTime++ 系统前时间加
}
printf(63f＼t1(float)diseffect320)
return 0
}
佳置换算法
int total_pf 户进程存页面数
int OPT(int total_pf)
{
int ij
int MaxD 次访问距离值（时间单元度量）
int MaxPn 次访问距离值页号
int dis 距离计数器
int dist[total_vp] 距离数组保存距离次访问时间差距数
initialize(total_pf) 初始化页面结构数组页面控制结构数组
diseffect0
for(i0i
if(pl[page[i]]pfnINVALID) 页面失效
{
diseffect++ 页错误次数加
if(freepf_headNULL) 空闲页面
{
for(j0j
if(pl[j]pfnINVALID) 果该页存中
dist[j]100000 该页关联距离值改值
else
dist[j]0 果该页存中该页关联距离值改
}
dis1 初始距离值
for(ji+1j
if(pl[page[j]]pfnINVALID &&pl[page[j]]counter0) 果该页存中访问页
if(pl[page[j]]pfnINVALID && dist[page[j]]100000) 条语句原理相
{ dist[page[j]]dis 距离值改dis
pl[page[j]]counter1 访问次数标志加区第次访问第二次访问
}
dis++
}
MaxD1
for(j0j
pl[j]counter0 重置访问次数
if(MaxD
MaxDdist[j]
MaxPnj
}
}
freepf_head&pfc[pl[MaxPn]pfn] 换段时间久访问页
freepf_head>nextNULL
pl[MaxPn]pfnINVALID
}
pl[page[i]]pfnfreepf_head>pfn 前页换入存中前页pfn改换入页帧号
freepf_headfreepf_head>next 减少空闲页面
}if
}for
printf(63f＼t1(float)diseffect320)
return 0
}
简单时钟算法
int total_pf 户进程存页面数
int CLOCK(int total_pf)
{
int i
int use[total_vp] 位
int swap
swap0 发生换
initialize(total_pf)
pfc_type *pnext 时钟指针
pfc_type *head 队列头指针
pnextfreepf_head
headfreepf_head
for(i0i
for(i0i
if (pl[page[i]]pfnINVALID) 页面失效存中
{
diseffect++ 页错误次数加
if(freepf_headNULL) 空闲页面
{
while(use[pnext>pfn]1) 时钟指针指页位改跳
{
use[pnext>pfn]0
pnextpnext>next
if(pnextNULL) pnexthead 果时钟指针达队列尾部重新返回头部
}
换出换页
pl[pnext>pn]pfnINVALID
swap1
}
if(use[pnext>pfn]0){ 果位换入相应页
pl[page[i]]pfnpnext>pfn 页面结构中标记帧号
pnext>pnpage[i] 页面控制结构中标记页号
use[pnext>pfn]1 重置位
pnextpnext>next 时钟指针移
if(pnextNULL) pnexthead 果时钟指针达队列尾部重新返回头部
if(swap0){ freepf_headfreepf_head>next }
}
}else{页面存中
use[pl[page[i]]pfn]1 刷新位
}
}
printf(63f＼t1(float)diseffect320)
return 0
}
先进先出算法版
int total_pf 户进程存页面数
实现细节CLOCK算法退化FIFO效果
int FIFO(int total_pf)
{
int i
int use[total_vp]
int swap0
initialize(total_pf)
pfc_type *pnext*head
pnextfreepf_head
headfreepf_head
for(i0i
for(i0i
if (pl[page[i]]pfnINVALID) 页面失效存中
{
diseffect++
if(freepf_headNULL) 空闲页面
{
while(use[pnext>pfn]1)
{
use[pnext>pfn]0
pnextpnext>next
if(pnextNULL) pnexthead
}
换出换页
pl[pnext>pn]pfnINVALID
swap1
}
if(use[pnext>pfn]0){ 果位换入相应页
pl[page[i]]pfnpnext>pfn 页面结构中标记帧号
pnext>pnpage[i] 页面控制结构中标记页号
use[pnext>pfn]1 重置位
pnextpnext>next
if(pnextNULL) pnexthead
if(swap0){ freepf_headfreepf_head>next }
}
}
}
printf(63f＼t1(float)diseffect320)
return 0
}
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档
