东南大学操作系统实验替换算法

1 9
操作系统实验报告

实验容
编写程序实现 LRU 算法似算法分析算法时间复杂度空间复杂度实现难
度通机生成页面访问序列测试实现算法页错误率加较分析
实验目
通实验理解 LRU 页面置换算法算法思想实现方法较种实现算法复杂度
实现难度体会 LRU 算法种似算法间区进加深虚拟存概念理解
设计思路流程图
函数根实验材料提供思路形式运行：
while(已测页面数<求测试页面数)
{
1）机产生新访问页号
2）调算法决定否需置换页面需调整存相关状态更新页错误数
}
中机访问页号 srand 函数根时间等生成机种子然产生伪机数
程序流程图： 2 9


数结构说明
LRU 计数器实现
定义结构 LRU_w_counter 实现帧项目数结构里面存储页面 ID 号计
数器值运行时遍历结构数组 lru_w_counter_list 实现换算法
程序入口
户输入
存帧数
初始化变量容器
已测页面数<
求测试页面数？
机产生访问页号
调算法决定否
换页面
统计换结果写入
log
程序结束
Y
N 3 9

LRU 栈实现

定义结构 LRU_s_Item 实现帧项目数结构里面存储页面 ID 号头
指针尾指针实现双链表结构
容器定义结构 LRU_s_Container 实现栈作帧容器结构中栈顶
栈底指针容量实际量函数 Push 栈顶增加元素(果空间没填满)
函数 Replace 栈底元素（少访问元素）换某新元素函数 TryAccess 实现尝
试页面访问果出现页错误换增加相关页出现页错误时返回 true
统计没页错误返回 false

AdditionalRefBits 算法
数结构 LRU 计数器实现类似 Item 中计数器值换成 unsigned char 类型实现
8 位 Reference Bits增加右移(>>1)置位(|0x80)函数
运行时采类似计数器实现 LRU 算法函数结构较时候 unsigned char
较需外写函数

Second Chance 算法
根算法原理首先设定单链表项结构 LRU_AA_Frame里面存储 1 位访问位
( bool 类型)继节点指针
第二构造容器 LRU_AA_Container 存储帧容器采循环单链表结构
设定头指针访问项目指针列表尾部继节点指表头实现循环单链
表

Item
…
Item
Item
…
Item

栈顶指针
栈底指针
Head 4 9

源程序注释
LRUh 负责数结构存储
#pragma once
#include
using namespace std

struct LRU_w_counter
{
计数器实现LRU
int counter
int ID

LRU_w_counter()
{
ID 1 空槽
counter 65536
}
}

struct LRU_ARB
{
AdditionalRefBits实现LRU
unsigned char refBits
int ID

LRU_ARB()
{
ID 1 空槽
refBits 0x0
}

void MoveRight()
{
refBits >> 1
}

void Access()
{
refBits | 0x80
}
}

struct LRU_s_Item
{
int ID
LRU_s_Item *head
LRU_s_Item *tail

LRU_s_Item()
{
ID 1
head NULL
tail NULL
}

}

struct LRU_s_Container
{
容器
LRU_s_Item *pFront 栈顶指针
LRU_s_Item *pEnd 栈底指针
int capacity 容量
int size

LRU_s_Container(int _capacity)
{
capacity _capacity
size 0
pFront NULL
pEnd NULL
}

LRU_s_Item* Push(int pageID)
{
if(size > capacity)
{
Need replace
return NULL
}
LRU_s_Item *newHeadItem new LRU_s_Item
newHeadItem>ID pageID
newHeadItem>tail pFront

if (pFront NULL)
pFront>head newHeadItem
if (pEnd NULL)
pEnd newHeadItem End
pFront newHeadItem
size ++
return pFront
}

LRU_s_Item* Replace(int pageID)
{
抽出栈底然push新进完事
LRU_s_Item *oldEnd pEnd
pEnd pEnd>head
if (pEnd NULL)
pEnd>tail NULL
size

return Push(pageID)
}

bool TryAccess(int pageID)
返回值 ： pagefault 返回true
{
LRU_s_Item * pItem pFront
while(pItem NULL)
{
if(pageID pItem>ID)
{
HIT
需指针浮顶
if(pItem pFront)
return false 栈
顶移动
pItem>head>tail
pItem>tail 5 9

if(pItem>tail NULL) 防止
栈底情况
pItem>tail>head
pItem>head
else
{
改动栈底修改栈底
指针
pEnd pItem>head
}
pFront>head pItem
pItem>head NULL
pItem>tail pFront
pFront pItem
return false
}
pItem pItem>tail 路找
}
找
if(size < capacity)
{
没满push行
Push(pageID)
return true
}
Replace(pageID) 换
return true
}
}

struct LRU_AA_Frame
{
bool ref_bit
int ID
LRU_AA_Frame *pNext
LRU_AA_Frame ()
{
ref_bit false
ID 1
}
}

struct LRU_AA_Container
{
Secondchance Pagerep Algorithm
LRU_AA_Frame *pHead
LRU_AA_Frame *pLastAccess
int capacity
int size

LRU_AA_Container(int _capacity)
{
capacity _capacity
size 0
pHead NULL
pLastAccess NULL
}

LRU_AA_Frame* Insert(int pageID)
{
if (size > capacity)
{
cerr << ERROR Container
oversize << endl
return NULL
}
LRU_AA_Frame *pItem pHead
LRU_AA_Frame *newFrame new
LRU_AA_Frame
newFrame>ID pageID
if (pItem NULL)
{
空容器
newFrame>pNext newFrame
pHead newFrame
size ++
return newFrame
}
while(pItem>pNext pHead)
pItem pItem>pNext 找末尾
newFrame>pNext pHead
pItem>pNext newFrame
size ++
return newFrame
}

void Replace(LRU_AA_Frame *pFrame int pID)
{
pFrame>ID pID
pFrame>ref_bit true
}

bool TryAccess(int pageID)
返回值：否发生页错误true>页错误
{
LRU_AA_Frame *pItem pLastAccess
if(pItem NULL)
{
pItem Insert(pageID)
pItem>ref_bit true
pHead pItem
pLastAccess pItem
return true
}
do
{
if(pageID pItem>ID)
{
HIT
pItem>ref_bit true
pLastAccess pItem
return false
}
pItem pItem>pNext
}while(pItem pLastAccess)

没命中果新增新增
if(size < capacity)
{
pItem Insert(pageID)
pItem>ref_bit true
pLastAccess pItem
return true
}
法新增换
pItem pLastAccess
while(true)
{
if(pItem>ref_bit false)
{
victim
Replace(pItempageID)
pLastAccess pItem
return true
}
else
{
pItem>ref_bit false ref 6 9

bit置0
}
pItem pItem>pNext继续

}
}
}

源cpp 程序
#include LRUh
#include
#include time
#include srandrand
#include
using namespace std

typedef enum
{
LRU_C LRU_S ARB SC
}
int MAX_MEM_FRAME 存帧数
const int MAX_PAGE_NUM 10 页数量
const int TEST_PAGE_NUM 3000 测试页面数

int page_falut_time[4] {0} 页错误数量
LRU_w_counter *lru_w_counter_list
LRU_s_Container *lru_s_container
LRU_ARB *lru_arb_list
LRU_AA_Container *lru_aa_container

void replace_lru_counter(int int) 计数器方法换页
void replace_lru_arb(int )
ofstream ofs

int main()
{
char fileName[255]
cout << 输入日志文件名：
cin >> fileName
ofsopen(fileName)

cout << 输入存帧数
cin >> MAX_MEM_FRAME
if( MAX_MEM_FRAME < 0)
exit(1)

初始化
lru_w_counter_list new LRU_w_counter[MAX_MEM_FRAME]
lru_s_container new LRU_s_Container(MAX_MEM_FRAME)
lru_arb_list new LRU_ARB[MAX_MEM_FRAME]
lru_aa_container new LRU_AA_Container(MAX_MEM_FRAME)

开始运行
int access_page_id 访问页号
for(int i0 i {
cout << << endl
ofs << << endl
机产生新访问页号
srand(time(NULL) + i)
access_page_id rand()MAX_PAGE_NUM
LRU方法进行页换(计数器)
ofs << LRU counter implementation < replace_lru_counter(access_page_id i)
ofs << ＼tPFR of LRU_counter << page_falut_time[LRU_C] << << (i+1) << <<
page_falut_time[LRU_C](float)(i+1)<< endl
cout << ＼tPFR of LRU_counter << page_falut_time[LRU_C] << << (i+1) << << 7 9

page_falut_time[LRU_C](float)(i+1)<< endl
LRU方法进行换（栈）
ofs << LRU counter implementation < bool have_fault lru_s_container>TryAccess(access_page_id)
if(have_fault)
page_falut_time[LRU_S]++
ofs << ＼tPFR of LRU_stack << page_falut_time[LRU_S] << << (i+1) << <<
page_falut_time[LRU_S](float)(i+1)<< endl
cout << ＼tPFR of LRU_stack << page_falut_time[LRU_S] << << (i+1) << <<
page_falut_time[LRU_S](float)(i+1)<< endl
LRUARB方法
ofs << LRU ARB Algorithm < replace_lru_arb(access_page_id)
ofs << ＼tPFR of LRU_ARB << page_falut_time[ARB] << << (i+1) << <<
page_falut_time[ARB](float)(i+1)<< endl
cout << ＼tPFR of LRU_ARB << page_falut_time[ARB] << << (i+1) << <<
page_falut_time[ARB](float)(i+1)<< endl
LRUAA
have_fault lru_aa_container>TryAccess(access_page_id)
if(have_fault)
page_falut_time[SC] ++
ofs << ＼tPFR of LRU_SC << page_falut_time[SC] << << (i+1) << <<
page_falut_time[SC](float)(i+1)<< endl
cout << ＼tPFR of LRU_SC << page_falut_time[SC] << << (i+1) << <<
page_falut_time[SC](float)(i+1)<< endl
}

ofsclose()
return 0
}

void replace_lru_counter(int pageID int timeCount)
{
cout << Accessing [ << pageID << ]
ofs << Accessing [ << pageID << ]
for(int i0 i {
LRU_w_counter *lruFrame &(lru_w_counter_list[i])
if(lruFrame>ID pageID)
{
lruFrame>counter timeCount
cout << HIT
ofs << HIT
return hit
}
}
cout << MISS
ofs << MISS
page_falut_time[LRU_C] ++ Increase page fault count
int min_time_count 65535
int min_index 1
for(int i0 i {
LRU_w_counter *lruFrame &(lru_w_counter_list[i])
if(lruFrame>ID 1)
{
空frame
lruFrame>ID pageID
lruFrame>counter timeCount
return
}
if(lruFrame>counter < min_time_count)
{
min_time_count lruFrame>counter
min_index i
}
}
replace
lru_w_counter_list[min_index]ID pageID 8 9

lru_w_counter_list[min_index]counter timeCount
}

void replace_lru_arb(int pageID)
{
循环遍ref_bit右移
for(int i0 i {
LRU_ARB *lruFrame &(lru_arb_list[i])
lruFrame>MoveRight()
}

cout << Accessing [ << pageID << ]
ofs << Accessing [ << pageID << ]
for(int i0 i {
LRU_ARB *lruFrame &(lru_arb_list[i])
if(lruFrame>ID pageID)
{
lruFrame>Access()
cout << HIT
ofs << HIT
return hit
}
}
cout << MISS
ofs << MISS
page_falut_time[ARB] ++ Increase page fault count
int min_ref_val 0x100
int min_index 1
for(int i0 i {
LRU_ARB *lruFrame &(lru_arb_list[i])
if(lruFrame>ID 1)
{
空frame
lruFrame>ID pageID
lruFrame>Access()
return
}
if(lruFrame>refBits < min_ref_val)
{
min_ref_val lruFrame>refBits
min_index i
}
}
replace
lru_arb_list[min_index]ID pageID
lru_arb_list[min_index]Access()
}
程序运行时初值运行结果
初始值：
测试页面数：3000
模拟访问页号：012…9 中取机数
存帧数：2 10

运行结果：
程序运行输出结果见 30006log该次测试时帧数 6

统计结果： 9 9
帧数量 LRU LRUARB LRUSC
2 0987 0987 0957
3 021 021 0332
4 0206 0206 02763
5 02056 02056 0275
6 02056 01656 0249
7 02056 0125 02373
8 0206 00853 02337
9 0206 00443 02036
10 00033 00033 00033
帧数量页面错误率统计表
帧数量页面错误率统计图
实验体会
统计结果帧数量升定书目页错误率会明显降次实验
测试问题没考虑程序局部性原理页面访问调实际中完全机
LRU 类算法实际中应更性LRU 两似算法空间复
杂度方面 LRU 原始算法少
程序实现中遇两问题第根时间设定 srand 种子系统时
间秒定义秒机出页号样增加访问次数作种子解决问
题第二 AdditionalRefBits 实现开始没 char 加 unsigned 限定符导致
较时候出错页错误率正常
0
02
04
06
08
1
12
0 2 4 6 8 10 12
Pagefault Rate (Random Page Access)
LRU LRUARB LRUSC

《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档