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


    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

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

    下载pdf到电脑,查找使用更方便

    pdf的实际排版效果,会与网站的显示效果略有不同!!

    需要 2 香币 [ 分享pdf获得香币 ]

    下载pdf

    相关文档

    操作系统实验报告C语言实现银行家算法

    实 验 报 告题 目名 称C语言实现银行家算法院 系信息科学与工程学院班 级完成时间指导老师本次实验成绩组长联系电话邮件地址组员(姓名,学号)主要任务程序算法的编写、实现、运行调...

    3年前   
    458    0

    操作系统实验三磁盘调度算法的实现

    XX大学计算机与通信工程学院实验报告2013 至 2014 学年 第 一 学期课程名称操作系统学号 学生姓名 年级 专业 教学班号 实验地点 实验时间 2013年 月 日 ...

    3年前   
    472    0

    操作系统实验心得

    操作系统实验心得  每一次课程设计度让我学到了在平时课堂不可能学到的东西。所以我对每一次课程设计的机会都非常珍惜。不一定我的课程设计能够完成得有多么完美,但是我总是很投入的去研究去学习。所以在...

    12年前   
    967    0

    操作系统 七次实验报告 常用页面置换算法模拟实验

    操作系统课程第七次实验报告姓名学号系计算机任课教师指导教师评阅教师实验地点 综合楼B102 实验时间2012-9-26实验课表现出勤和个人表现Q1(15+15(组长评分)=30分)得...

    3年前   
    733    0

    计算机操作系统实验三页面置换算法模拟实验

    计算机工程学院实验报告书课程名:《 操作系统原理A 》 题 目: 虚拟存储器管理 页面置换算法模拟实验...

    3年前   
    625    0

    实验6FFT算法的应用

    实验6 FFT算法的应用实验目的:加深对离散信号的DFT的理解及其FFT算法的运用。实验原理:N点序列的DFT和IDFT变换定义式如下: , 利用旋转因子具有周期性,可以得到快速算法(FF...

    1年前   
    350    0

    进程调度算法的实现计算机操作系统课程设计

    题目2 进程调度算法的实现2.1 题目的主要研究内容及预期达到的目标(1)设计进程控制块; (2)设计多个进程队列; (3)设计多个进程(≥20); (4)动态生成时间片、执行时间和优先级,...

    2年前   
    573    0

    操作系统课程设计银行家算法的模拟实现

    操作系统课程设计报告专业计算机科学与技术学生姓名班级学号指导教师完成日期信息工程学院题目: 银行家算法的模拟实现 一、设计目的本课程设计是学习完“操作系统原理”课程后进...

    3年前   
    665    0

    操作系统课程设计磁盘调度算法

    操作系统课程设计磁盘调度算法目 录1 课程设计目的及要求……………………………………………………12 相关知识…………………………………………………………………13 ...

    3年前   
    531    0

    操作系统课程设计银行家算法报告

    《操作系统--银行家算法》课程设计报告姓 名: 学 号: 班 级:计科班 ...

    3年前   
    613    0

    操作系统课程设计磁盘调度算法

    《计算操作系统》课程设计报告 姓名: ...

    3年前   
    447    0

    《操作系统 银行家算法》课程设计报告

    《操作系统--银行家算法》课程设计报告姓 名: 学 号: 班 级: 计科班 ...

    3年前   
    800    0

    合工大页面置换算法操作系统课程设计报告

    计算机与信息学院《操作系统综合设计》报告设计题目:页面置换算法学生姓名:学 号:专业班级:计算机科学与技术班2015 年 X月一、设计题目 3二、开发环境与工具 3三、设计原理 31....

    3年前   
    544    0

    银行家算法《操作系统》课程设计报告

    《操作系统》课程设计报告课题: 银行家算法 专业计算机科学与技术学生姓名班级计算机学号指导教师信息工程...

    3年前   
    680    0

    嵌入式操作系统实验指导

    嵌入式操作系统实验指导书目 录实验一 Linux命令使用实验二 vi编辑器的使用实验三 shell编程实验(一)实验四 shell编程实验(二)实验五 Linux开发工具...

    1年前   
    339    0

    操作系统实验心得(精选多篇)

    操作系统实验心得(精选多篇)第一篇:操作系统实验心得每一次课程设计度让我学到了在平时课堂不可能学到的东西。所以我对每一次课程设计的机会都非常珍惜。不一定我的课程设计能够完成得有多么完美,但是我...

    12年前   
    559    0

    操作系统进程管理实验报告

    操作系统进程管理实验报告实验一 进程管理1.实验目的:(1)加深对进程概念的理解,明确进程和程序的区别;(2)进一步认识并发执行的实质;(3)分析进程争用资源的现象,学习解决进程互斥的方法;...

    1年前   
    338    0

    操作系统实验(进程调度+存储管理+磁盘调度++银行家算法+文件系统设计)

    操作系统实验(进程调度+存储管理+磁盘调度++银行家算法+文件系统设计)实验三 进程调度一、 实验目的多道程序设计中,经常是若干个进程同时处于就绪状态,必须依照某种策略来决定那个进程优先占有处...

    3年前   
    635    0

    图象处理算法实验指导书

     图象处理算法实验指导书 实验一 静态图像采集 一、 实验目的 1. 了解DSK的工作原理。 2...

    5年前   
    834    0

    操作系统课程设计编程序模拟银行家算法

    课程设计报告书 课程名称: 操作系统原理 题 目: 编程序模拟银行家算法 系 名: 信息工程系 专业班级: ...

    3年前   
    705    0
    下载需要 2 香币 [香币充值 ]
    亲,您也可以通过 分享原创pdf 来获得香币奖励!
    该文档为用户出售和定价!

    该用户的其他文档