精华内容
下载资源
问答
  • 页面置换算法流程图
    千次阅读
    2021-12-11 12:17:44

    声明:本篇博客参考书籍《计算机操作系统》(西安电子科技大学出版社)


    首先说说影响页面换进换出的效率的几个因素:
    (1)页面置换算法。该因素是影响页面换进换出效率的重要因素。一个好的页面置换算法可以使进程在运行过程中具有较低的缺页率,从而减少页面换进换出的频率。
    (2)写回磁盘的频率。对于已经被修改的页面,换出时,需要写入到磁盘,也就是I/O操作。如果一个被修改的页面被换出后,系统暂时不将其写回到磁盘,而是挂在已经修改的换出页面的链表上。仅当被换出页面的数目达到一定值时,再将它们一起写入到磁盘中。显著的减少了磁盘I/O操作。
    (3)读入内存的频率。设置了已修改换出页面链表后,在该链表上有一批换出且待写回磁盘的页面,如果有进程在这些页面被写回磁盘前再次需要访问该页面,那么可以直接从已修改的链表上获取该页面。可以减少从磁盘读取页面到内存的频率。

    一、最佳页面置换算法

    1、基本知识

    最佳页面置换算法是一种理想化的页面置换算法,具有最好的性能,但是实际上没办法实现,其他页面置换算法的好坏,通常以最佳页面置换算法为比较标准。

    2、算法思想

    该算法选择的被淘汰的页是以后永不使用或者是在最长未来时间内不再被访问的页面,故最佳置换算法保证了最低的缺页率。但是由于人们目前无法预知一个进程在内存中的哪个页面是未来最长时间内不再被访问的,所以该算法到目前为止还只是一个理论算法,没有被实现。下面用举例说明该算法。
    假设系统为某个进程分配了4个物理块,并且该进程的页面的引用顺序如下:
    1 ,0,2,3,4,3,2,1,4,5,3,4,0 …
    则各时刻页面被装入内存的情况如下:
    在这里插入图片描述
    当装入1,0,2之后,调用页面3时会发生缺页中断,需要将一个页面置换出去,将页面3置换进来,对于最佳置换算法,发现对于页面1,0,2来说,页面0是未来最久未使用到的页面,所以将页面0置换出去,将页面3置换进来。
    当调用页面4时会发生页面中断,需要将一个页面置换出去,将页面4置换进来,对于最佳置换算法,发现对于页面1,3,2来说,页面1是未来最久未使用到的页面,所以将页面1置换出去,将页面4置换进来
    . . . . .一直这样进行着页面置换,这就是最佳页面置换算法。由图可看出,画出来的部分进行了4次页面置换。

    二、先进先出(FIFO)页面置换算法

    1、基本知识

    先进先出置换算法是最早出现的算法,该算法实现简单,只需要将一个进程已调入内存的页面按照先后次序连接成一个队列,并且设置成一个指针,称为替换指针,总是指向该队列的头,即指向该进程已调入内存的页面中,最先调入的页面(即在内存中待的时间最长的页面)。
    该算法的性能比较差,因为它所依据的条件是各个页面在内存中驻留的时间的长短,而页面调入的先后并不能反应页面的使用情况。

    2、算法思想

    思想为总是淘汰最先进入内存的页面,即选择在内存中驻留时间最长的页面淘汰。
    以最佳置换算法中的页面和引用顺序举例:
    在这里插入图片描述
    当页面1,0,2装入内存后,调用页面3时,会发生页面中断,对于先进先出页面置换算法来说,由于1,0,2三个页面,页面1在内存中驻留时间最长,所以将页面1置换出去,将页面3置换进来。
    当需要调用页面4时,会发生页面中断,由于页面3,0,2中页面0在内存中驻留时间最长,所以将页面0置换出去,将页面4置换进来。
    . . . . . . 一直这样页面置换,总是将在内存中驻留时间最长的页面置换出去。从画出的图中可以看出进行了6次页面置换

    三、最近最久未使用(LRU)页面置换算法

    1、基本知识

    最近最久未使用页面置换算法是根据页面调入内存后的使用情况而做出决策的。由于无法预测页面未来的使用情况,所以只能根据页面最近的使用情况作为未来的使用情况的近似。

    2、算法思想

    最近最久未使用(LRU)页面置换算法是选择最近最久未使用的页面给予淘汰,该算法赋予每一个页面一个访问字段,用来记录一个页面自上次被访问以来所经历的时间t,当需要淘汰一个页面时,选择现有页面中t值最大的,即最近最久未使用的页面给予淘汰。
    在这里插入图片描述
    当第一次需要引用页面3时,会发生缺页中断,对于最近最久未使用算法来说,对于在内存中的页面1,0,2,页面1最近最久未使用,所以将页面1置换出,将页面3置换进内存。
    当第一次引用页面4时,会发生缺页中断,对于最近最久未使用算法来说,对于在内存中的页面3,0,2,页面0最近最久未使用,所以将页面0置换出,将页面4置换进内存。
    对于内存中驻留页面是3,4,2来说,需要引用页面1,发生缺页中断,对于最近最久未使用算法来说,对于在内存中的页面3,4,2,页面4最近最久未使用,所以将页面4置换出,将页面1置换进内存。
    . . . . . . 按照最近最久未使用规则一直这样置换下去。
    最近最久未使用置换算法是根据过去的使用情况来决定被置换出去的页,而最佳置换算法是根据未来的使用情况来决定被置换出去的页。也可以说最近最久未使用置换算法试图希望通过过去的页面使用情况来近似接近于未来页面的使用情况,而接近于最佳置换算法。但是这只是一种希望,因为页面过去的使用情况和未来的使用情况之间没有必然的联系。

    3、硬件支持

    为了了解一个进程在内存中的哪一个页面是最近最久未使用的,需要寄存器或者栈这两类硬件之一支持。
    (1)移位寄存器
    可以为在内存中的每个页面配置一个移位寄存器,假设该寄存器有n个位,每个位由R表示,最低位由R0表示,最高位由R(n-1)表示。
    当进程访问某个物理块时,将相应的寄存器的位R(n-1)置为1,定时信号将每隔一定时间(比如100ms)将寄存器右移一位(相当于数值以>>1的方式缩小),也就是越久未使用,该页面对应的寄存器的值越小(除非该寄存器的值已经为0了),那么值最小的移位寄存器对应的页面就是最近最久未使用的页面。
    (2)栈
    可以利用一个特殊的栈保存一个进程被调入内存的页面的页面号。当一个页面被访问时,将该页面从栈中移出,将该页面重新压入栈中。因此栈顶保存的总是最近被访问的页面的页面号,而栈底就是最近最久未使用的页面号。

    四、最少使用(LFU)页面置换算法

    1、基本知识

    使用最少使用(LFU)页面置换算法时,应该在内存中为每一个页面设置一个移位寄存器,用来记录被访问的频率。最少使用页面置换算法,顾名思义,选择使用频率最少的页面置换出去。

    2、算法思想

    思想即选择最近最少使用的页面淘汰。
    由于存储器具有较高的访问速度,例如100ns,在1ms内可能对一个页面访问成千上万次,所以,只能采用较大的时间间隔来记录对存储器某页的访问,在最少使用置换算法中也使用了移位寄存器。
    当某页被访问时,将该移位寄存器的最高位置为1,隔一定时间,将移位寄存器的值右移一位,故寄存器各个位值相加,值越小,说明该移位寄存器对应的页面在最近一段时间使用的次数最少。
    这种算法并不能真正反应页面的使用情况,因为在每一个时间间隔内,只是用寄存器的一个位来记录该页在该间隔被使用了,但是在该时间间隔内,页面被使用1次和被使用10000次完全是等效的。

    五、Clock页面置换算法

    1、基本知识

    最近最久未使用(LRU)算法是比较常见的页面置换算法,但是由于LRU置换算法需要较多的硬件支持,所以使用LRU算法的成本较高,所以在实际应用中大多采用LRU的近似算法,Clock就是其中一个用的较多的LRU近似算法。

    2、算法思想

    当利用Clock算法时,只需要将每一个页设置一个访问位,再将内存中的所有页面都通过指针连接成一个循环队列,当某页被访问时,访问位置为1。
    Clock置换算法在选择一个页置换出时,只需要检查页面的访问位,如果是0,就将该页换出;如果是1,则将访问位重新置为0,暂不换出,给予该页第二次驻留内存的机会,再按照Clock算法检查下一个页面。当检查到队列中的最后一个页面时,若其访问位仍然为1,则再去返回队首检查第一个页面…

    3、改进型Clock置换算法

    当一个页面换出时,如果该页面已经被修改,那么需要将这个页面重新写回到磁盘上,但是如果该页面没有被修改,那么不必将它拷回到磁盘。所以对于修改过的页面来说,没有修改的页面的换出时付出的代价要更小。所以在改进型Clock置换算法中在考虑页面的使用情况之外,又考虑了页面置换代价,即是否被修改了。所以每个页面有两个标志位,分别为访问为A和修改位M,可以组合成以下四种情况:
    (1)(A = 0, M = 0):表示该页最近既没有被访问也没有被修改,是最佳淘汰页。
    (2)(A = 0, M = 1):表示该页最近没有被访问,但是被修改了,并不是很好的淘汰页。
    (3)(A = 1, M = 0):表示该页最近被访问了,但是没有被修改,该页有可能会被再次访问。
    (4)(A = 1, M = 1):表示该页最近既被访问又被修改,该页有可能被再次访问。
    改进型Clock置换算法寻找淘汰页时,执行过程可以分为以下三步:
    (1)从指针所指示的当前位置开始,扫描循环队列,寻找A = 0且M = 0的第一类页面,将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不修改访问位A。
    (2)如果第一步失败,即查找一轮后未遇到第一类页面,则开始第二轮扫描,寻找A = 0且M = 1的第二类页面,将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间,将所有扫描过的页面的访问位都置为0。
    (3)如果第二步也失败,即第二类页面也没有找到,则将指针返回到开始位置,并且将所有的访问位都置为0,然后重复第一步,即寻找A=0且M=0的页面,如果仍然失败,必要时再重复第二步,寻找A=0且M=1的第二类页面,此时就一定能找到被淘汰的页。
    该算法与普通Clock置换算法相比,可以减少磁盘I/O操作次数。实现该算法的本身的开销将增加。

    六、页面缓冲(PBA)算法

    1、基本知识

    页面缓冲算法有以下两个特点:
    (1)显著的降低了页面换进换出的频率,使磁盘I/O操作次数大为减少。
    (2)由于磁盘I/O操作次数大为减少,使得页面换进换出的效率减少,所以使其可以采用较为简单的页面置换算法,比如先进先出页面置换算法。

    2、算法思想

    该算法主要由两类链表支撑,空闲页面链表和修改页面链表。页面缓冲算法主要是将换出的页面暂时不写回到磁盘中,而是将页面挂到相应的链表上。其一减少磁盘I/O操作次数,其二可以减少读入内存的频率。
    (1)空闲页面链表
    该链表是一个空闲物理块链表。是系统掌握的空闲物理块,用于分配给频繁发生缺页中断的进程,以降低该进程的缺页率。当这样的进程需要读入一个页面时,便可利用空闲物理块来装入该页。
    当有一个未被修改的页面要换出时,实际上并不将它换回到外村,而是把它们所在的物理块挂在空闲链表的末尾。这些挂在空闲链表中的物理块是有数据的,如果以后某个进程需要访问这些页面时,可以直接从空闲链表中取下,免除了从磁盘读入数据的操作,减少了页面换进的开销。其实也减少了页面换出的开销,因为这个换出页面到目前为止都没有写回到磁盘。
    (2)已修改页面的链表
    该链表是由已修改的页面所形成的链表。设置该链表的目的是减少修改页面换出的次数。当进程需要将一个已经修改的页面换出时,系统并不立即将它换出到磁盘上,而是将它所在的物理块挂在修改页面链表的末尾。
    当已修改页面的链表上的页面个数达到一定程度时,会一一起将这些页面写回到磁盘。如果这些被换出的页面在写回磁盘之前,有进程需要访问其中的页面,那么可以直接从已修改页面链表上获取该页面。所以可见,减少了磁盘I/O操作,并且减少了内存写入频率。

    更多相关内容
  • 包括了操作系统页面置换算法,其中有OPT,FIFO,LRU,CLOCK,改进型的CLOCK算法
  • 该工程具体是在codeblock上面实现了操作系统课程上讲解的页面置换算法,包括先进先出(FIFO)、最佳置换算法(OPT)、最久最近未使用算法(LRU)。 具体实现功能有: 1、建立相应的数据结构 2、在屏幕上显示页面...
  • 用LRU的思想实现缺页中断以及页面置换。C语言实现,按照最近最久未被访问的思想去实现这个算法。输出每一次页面置换之后的过程以及最后的缺页中断次数与缺页中断率。
  • C#源码
  • 实用文案 计算机科学系 实 验 报 告 书 课 程 名 操 作 系 统 题 目 虚拟存储器管理 页面置换算法模拟实验 班 级 学 号 姓 名 评语 成绩 指导教师 批阅时间 年 月 日 标准文档 实用文案 一实验目的与要求 1....
  • 页面置换算法(FIFO&LRU)

    万次阅读 多人点赞 2020-12-27 11:23:43
    页面置换算法 实验目的 1.通过模拟实现几种基本页面置换的算法,了解虚拟存储技术的特点。 2.通过置换算法的模拟和比较,进一步了解它们的优缺点。 3.锻炼知识的运用能力和实践能力 实验要求 编写程序实现:先进先出...

    页面置换算法

    实验目的

    1.通过模拟实现几种基本页面置换的算法,了解虚拟存储技术的特点。
    2.通过置换算法的模拟和比较,进一步了解它们的优缺点。
    3.锻炼知识的运用能力和实践能力

    实验要求

    编写程序实现:先进先出页面置换算法(FIFO)和最近最久未使用页面置换算法(LRU)
    说明:(1)关于页面走向的页地址流可利用随机数产生一个序列,模拟该页地址流,
    也可以手工键盘输入的方式或读取文件中的页地址流。(2)初始时,假定所有页面均
    不在内存。(3)计算并输出以上两种算法在分配不同内存物理块数时(讨论内存物理
    块数分配为3,4,5)的缺页率。(4)至少验证两组数据,即页地址流。

    实验内容概述

    首先,了解页面算法的功能。页面的算法的功能是当出现缺页异常且调入新页面而内存已满时,置换算法选择被置换的物理页面进行置换。因此对于如何科学地选取被置换的物理页面根据不同的页面置换算法不同而不同。

    其次,页面置换算法的设计目标是为了减少页面的调入调出次数,把未来不再访问或者短期内不访问的页面调出。常见的页面置换调度算法有先进先出页面置换算法(FIFO)、最近最久未使用页面置换算法(LRU)、最佳置换调度算法(OPT)、CLOCK置换算法等。

    本次实验针对FIFO和LRU两种算法进行详细分析和模拟实验,深刻理解页面调度算法原理。

    算法流程图

    总体流程:
    总体流程图FIFO流程:
    FIFO流程LRU流程图:
    LRU流程图

    程序代码

    #include <stdio.h>
    #define phy 100
    #define page 100//页面最大数
    #define phyBlock 100//物理块最大数
    //物理块的数量
    int phyBlockNum;
    //页面数量
    int pageNum;
    //保存页面号引用串
    int pageNumStrList[page];
    //初始化队列
    void initializeList(int list[], int number)
    {
        for (int i = 0; i < number; i++)
        {
            list[i] = -1;
        }
    }
    //展示队列状态
    void showList(int list[], int number)
    {
        for (int i = 0; i < number; i++)
        {
            printf("%2d", list[i]);
        }
        printf("\n");
    }
    
    //展示当前内存状态
    void showMemoryList(int list[], int phyBlockNum)
    {
        for (int i = 0; i < phyBlockNum; i++)
        {
            if (list[i] == -1)
            {
                break;
            }
            printf(" |%d|", list[i]);
        }
        printf("\n");
    }
    
    void informationCount(int missingCount, int replaceCount, int pageNum)
    {
        printf("***********结果展示***********\n");
        printf("缺页次数:%d\n", missingCount);
        printf("缺页率:%d/%d\n", missingCount, pageNum);
        double result = (double)(pageNum - missingCount) / (double)pageNum;
        printf("置换次数:%d\n", replaceCount);
        printf("******************************\n");
    }
    
    //找到该页面下次要访问的位置
    int getNextPosition(int currentPage, int currentPosition, int strList[], int pageNum)
    {
    
        for (int i = currentPosition + 1; i < pageNum; i++)
        {
            if (strList[i] == currentPage)
            {
                return i;
            }
        }
        return 100;
    }
    //先进先出置换算法
    void replacePageByFIFO(int memoryList[], int phyNum, int strList[], int pageNum) {
    
        //置换次数
        int replaceCount = 0;
        //缺页次数
        int missingCount = 0;
    
        //记录当前最早进入内存的下标
        int pointer = 0;
    
        //记录当前页面的访问情况: 0 未访问
        int isVisited = 0;
        for (int i = 0; i < pageNum; i++) {
            isVisited = 0;
    
            //判断是否需要置换->内存已满且需要访问的页面不在内存中
            for (int j = 0; j < phyNum; j++) {
                if (memoryList[j] == strList[i]) {
                    //该页面已经存在内存中
                    //修改访问情况
                    isVisited = 1;
                    //修改访问时间
                    //展示
                    printf("%d\n", strList[i]);
                    break;
                }
                if (memoryList[j] == -1) {
                    //页面不在内存中且内存未满->直接存入
                    memoryList[j] = strList[i];
                    //修改访问情况
                    isVisited = 1;
                    missingCount++;
                    //展示
                    printf("%d\n", strList[i]);
                    showMemoryList(memoryList, phyNum);
                    break;
                }
            }
    
            if (!isVisited) {
                //当前页面还未被访问过->需要进行页面置换
                //直接把这个页面存到所记录的下标中
                memoryList[pointer] = strList[i];
    
                //下标指向下一个
                pointer++;
    
                //如果到了最后一个,将下标归零
                if (pointer > phyNum - 1) {
                    pointer = 0;
                }
    
    
                missingCount++;
                replaceCount++;
    
                //展示
                printf("%d\n", strList[i]);
                showMemoryList(memoryList, phyNum);
            }
        }
        informationCount(missingCount, replaceCount, pageNum);
    }
    
    //最近最久未使用置换算法
    void replacePageByLRU(int memoryList[], int phyNum, int strList[], int pageNum) {
    
        //置换次数
        int replaceCount = 0;
        //缺页次数
        int missingCount = 0;
    
        //记录内存中最近一次访问至今的时间
        int timeRecord[phy];
        //初始化
        initializeList(timeRecord, phyNum);
    
        //记录当前页面的访问情况: 0 未访问
        int isVisited = 0;
    
        //记录已经在内存中的页面数量
        int pageCount = 0;
        for (int i = 0; i < pageNum; i++) {
            isVisited = 0;
    
            //时间加一
            for (int p = 0; p < pageCount; p++) {
                if (memoryList[p] != -1) {
                    timeRecord[p] ++;
                }
            }
    
            //是否需要置换
            for (int j = 0; j < phyNum; j++) {
                if (memoryList[j] != -1) {
                    timeRecord[j] ++;
                }
                if (memoryList[j] == strList[i]) {
                    //该页面已经存在内存中
                    //修改访问情况
                    isVisited = 1;
                    //重置访问时间
                    timeRecord[j] = -1;
                    //展示
                    printf("%d\n", strList[i]);
                    break;
                }
                if (memoryList[j] == -1) {
                    //页面不在内存中且内存未满->直接存入
                    memoryList[j] = strList[i];
                    pageCount++;
                    //修改访问情况
                    isVisited = 1;
                    //修改访问时间
                    timeRecord[j] ++;
    
                    missingCount++;
                    //展示
                    printf("%d\n", strList[i]);
                    showMemoryList(memoryList, phyNum);
                    break;
                }
            }
    
            if (!isVisited) {
                //需要置换
                //1.遍历时间记录表,寻找最久未访问的页面所在的内存下标
                int max = 0;
                for (int k = 0; k < phyNum; k++) {
                    if (timeRecord[max] < timeRecord[k]) {
                        max = k;
                    }
                }
    
                //2.将该位置的页面换出
                memoryList[max] = strList[i];
                timeRecord[max] = -1;
    
                missingCount++;
                replaceCount++;
    
                //展示
                printf("%d\n", strList[i]);
                showMemoryList(memoryList, phyNum);
    
            }
        }
        informationCount(missingCount, replaceCount, pageNum);
    }
    
    int main(int argc, const char* argv[])
    {
        printf("***********************************\n");
        printf("*            页面调度算法         *\n");
        printf("***********************************\n");
    
        printf("请输入物理块数量:\n");
        scanf("%d", &phyBlockNum);
        //生成内存队列
        int memoryList[phyBlock];
        //初始化内存状态
        initializeList(memoryList, phyBlockNum);
        //showMemoryList(memoryList,phyBlockNum);
        printf("请输入要访问的页面总数:\n");
        scanf("%d", &pageNum);
        printf("请输入要访问的页面号:\n");
        for (int i = 0; i < pageNum; i++) {
            scanf("%d", &pageNumStrList[i]);
        }
        printf("*******************************\n");
        showList(pageNumStrList, pageNum);
        printf("*******************************\n");
        int chose;
        while (1)
        {
            printf("请选择所需的置换算法(1.FIFO 2.LRU 3.退出):\n");
            scanf("%d", &chose);
            printf("*******************************\n");
            switch (chose)
            {
            case 1:
                showList(pageNumStrList, pageNum);
                printf("*******************************\n");
                replacePageByFIFO(memoryList, phyBlockNum, pageNumStrList, pageNum);
                //重新初始化内存
                initializeList(memoryList, phyBlockNum);
                break;
            case 2:
                showList(pageNumStrList, pageNum);
                printf("*******************************\n");
                replacePageByLRU(memoryList, phyBlockNum, pageNumStrList, pageNum);
                //重新初始化内存
                initializeList(memoryList, phyBlockNum);
                break;
            default:
                return 0;
                break;
            }
        }
        return 0;
    }
    

    实验结果截图

    • 测试数据1:物理内存块分别为{3,4,5},页面长度为20,页面地址流为{7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1}

    数据输入截图:物理内存块为3
    数据输入
    FIFO结果:
    FIFO
    LRU结果:
    LRU后面结果读者就自己去实验啦。

    实验分析

    本次实验通过对两种页面置换算法即先进先出置换算法(FIFO)以及最近最久未使用算法(LRU)进行了实验模拟,为了保证程序能够正常运行,系统必须从内存中调出一页内存放在磁盘上,以便将所需要的页调入内存,该过程称为页面调度,通过对以上两种算法的模拟,从中我深刻理解了两种算法的深层原理。本次实验要求基本达到,实验结果达到预期效果,下面是本次实验的收获以及心得:

    物理内存块数量的增大可能使缺页率不降反增,这与该算法不考虑程序的动态特征有关;

    影响缺页率的因素不是单一的,主存页框数,页面大小,页面替换算法、程序特征均会影响缺页率;

    每种算法各有各的优缺点,例如FIFO算法简单,但通常缺页率较高,而LRU通常缺页率较FIFO低,但算法比较复杂,选择时各有取舍。

    展开全文
  • 前提:设置三个内存块 1、FIFO页面置换算法 第一种: 第二种: 2、LRU页面置换算法 第一种: 第二种:

    前提:

    1.设置三个内存块;
    2. * 指的是缺页;
    3. / 指的是命中。

    1、先进先出页面置换算法(FIFO)

    总是淘汰在内存中停留时间最长的一页,,即先进入内存的一页,先被替换出。

    第一种:
    在这里插入图片描述
    第二种:
    在这里插入图片描述

    2、最近最久未使用页面置换算法(LRU)

    选择在最近一段时间里没有被使用过的页面,将其淘汰,也就是被其他页面替换。

    第一种:

    在这里插入图片描述
    第二种:

    在这里插入图片描述

    3、最佳置换算法(OPT)

    选择在将来不被使用,或者在最远的将来才被使用的老页面,也就是选择该页面后面较远才出现,甚至不出现的页面,将其淘汰,即被替换。

    第一种:
    在这里插入图片描述
    第二种:
    在这里插入图片描述

    一开始,我也搞不明白这两种表格有什么不同,还以为其中的一种是错的,后来才发现两种都是正确的,只不过略有不同。

    区别:
    第一种表格,例如数字2被替换出去,那么新进来的数字1 将被安排在刚刚被替换出去的数字2的原位置;
    第二种表格,例如数字2被替换出去,那么新进来的数字1依旧始终被安排在最上面第一个内存块,即内存块a,后面内存块中的数字依次向下移动,数字2的空位置在移动过程中被占据。

    展开全文
  • 页面置换算法课设 private void FIFO_button1_Click(object sender, EventArgs e) { if (page.Length == 0 || strsize.Length == 0) MessageBox.Show("输入得页面序列或物理块数不能为空", "提示", ...
  • 页面置换算法.doc

    2020-03-23 22:48:13
    深入掌握内存调度算法的概念原理和实现方法,编写程序实现: (1) 先进先出页面置换算法(FIFO) ...操作系统页面置换算法课程设计,完整的课设结构,有详细的流程图、Java源码,还有调试截图!!!
  • 页面置换算法, 三种算法编写的程序,支持随机数输入,也支持示例输入,自带PPT例子验证结果
  • 一、缺页异常(缺页中断) 当 CPU 访问的⻚⾯不在物理内存时,便会产⽣⼀个...缺⻚中断的处理流程,如下: 在 CPU ⾥访问⼀条 Load M 指令,然后 CPU 会去找 M 所对应的⻚表项。 如果该⻚表项的状态位是「有效的」.

    在这里插入图片描述

    一、缺页异常(缺页中断)

    当 CPU 访问的⻚⾯不在物理内存时,便会产⽣⼀个缺⻚中断,请求操作系统将所缺⻚调⼊到物理内存。那它与⼀般中断的主要区别在于:

    • 缺⻚中断在指令执⾏「期间」产⽣和处理中断信号,⽽⼀般中断在⼀条指令执⾏「完成」后检查和处理中断信号。
    • 缺⻚中断返回到该指令的开始重新执⾏「该指令」,⽽⼀般中断返回回到该指令的「下⼀个指令」执 ⾏。

    缺⻚中断的处理流程,如下图:

    在这里插入图片描述

    • 在 CPU ⾥访问⼀条 Load M 指令,然后 CPU 会去找 M 所对应的⻚表项。
    • 如果该⻚表项的状态位是「有效的」,那 CPU 就可以直接去访问物理内存了,如果状态位是「⽆效的」,则 CPU 则会发送缺⻚中断请求。
    • 操作系统收到了缺⻚中断,则会执⾏缺⻚中断处理函数,先会查找该⻚⾯在磁盘中的⻚⾯的位置。
    • 找到磁盘中对应的⻚⾯后,需要把该⻚⾯换⼊到物理内存中,但是在换⼊前,需要在物理内存中找空闲⻚,如果找到空闲⻚,就把⻚⾯换⼊到物理内存中。
    • ⻚⾯从磁盘换⼊到物理内存完成后,则把⻚表项中的状态位修改为「有效的」。
    • 最后,CPU 重新执⾏导致缺⻚异常的指令。

    第 4 步是能在物理内存找到空闲⻚的情况,那如果找不到呢?

    找不到空闲⻚的话,就说明此时内存已满了,这时候,就需要「⻚⾯置换算法」选择⼀个物理⻚,如果该物理⻚有被修改过(脏⻚),则把它换出到磁盘,然后把该被置换出去的⻚表项的状态改成「⽆效的」,最后把正在访问的⻚⾯装⼊到这个物理⻚中。

    ⻚表项通常有如下图的字段:

    在这里插入图片描述

    • 状态位:⽤于表示该⻚是否有效,也就是说是否在物理内存中,供程序访问时参考。
    • 访问字段:⽤于记录该⻚在⼀段时间被访问的次数,供⻚⾯置换算法选择出⻚⾯时参考。
    • 修改位:表示该⻚在调⼊内存后是否有被修改过,由于内存中的每⼀⻚都在磁盘上保留⼀份副本,因此,如果没有修改,在置换该⻚时就不需要将该⻚写回到磁盘上,以减少系统的开销;如果已经被修改,则将该⻚重写到磁盘上,以保证磁盘中所保留的始终是最新的副本。
    • 硬盘地址:⽤于指出该⻚在硬盘上的地址,通常是物理块号,供调⼊该⻚时使⽤。

    二、虚拟内存的管理流程

    在这里插入图片描述

    在这里插入图片描述

    所以,⻚⾯置换算法的功能是,当出现缺⻚异常,需调⼊新⻚⾯⽽内存已满时,选择被置换的物理⻚⾯, 也就是说选择⼀个物理⻚⾯换出到磁盘,然后把需要访问的⻚⾯换⼊到物理⻚。

    那其算法⽬标则是,尽可能减少⻚⾯的换⼊换出的次数,常⻅的⻚⾯置换算法有如下⼏种:

    • 最佳⻚⾯置换算法(OPT
    • 先进先出置换算法(FIFO
    • 最近最久未使⽤的置换算法(LRU
    • 时钟⻚⾯置换算法(Lock
    • 最不常⽤置换算法(LFU

    三、内存页面置换算法

    1、最佳页面置换算法

    最佳⻚⾯置换算法基本思路是,置换在「未来」最⻓时间不访问的⻚⾯

    所以,该算法实现需要计算内存中每个逻辑⻚⾯的「下⼀次」访问时间,然后⽐较,选择未来最⻓时间不访问的⻚⾯。

    举个例⼦,假设⼀开始有 3 个空闲的物理⻚,然后有请求的⻚⾯序列,那它的置换过程如下图:

    在这里插入图片描述

    在这个请求的⻚⾯序列中,缺⻚共发⽣了 7 次(空闲⻚换⼊ 3 次 + 最优⻚⾯置换 4 次),⻚⾯置换共发⽣了 4 次。

    这很理想,但是实际系统中⽆法实现,因为程序访问⻚⾯时是动态的,我们是⽆法预知每个⻚⾯在「下⼀次」访问前的等待时间。

    所以,最佳⻚⾯置换算法作⽤是为了衡量算法的效率,算法效率越接近该算法的效率,那么说明我们自己写的算法是⾼效的。

    2、先进先出置换算法

    既然我们⽆法预知⻚⾯在下⼀次访问前所需的等待时间,那我们可以选择在内存驻留时间很⻓的⻚⾯进⾏中置换,这个就是「先进先出置换」算法的思想。

    以前⾯的请求的⻚⾯序列作为例⼦,假设使⽤先进先出置换算法,则过程如下图:

    在这里插入图片描述

    在这个请求的⻚⾯序列中,缺⻚共发⽣了10 次,⻚⾯置换共发⽣了 7 次,跟最佳⻚⾯置换算法⽐较起来,性能明显差了很多。

    3、最近最久未使⽤的置换算法

    最近最久未使⽤(LRU)的置换算法的基本思路是,发⽣缺⻚时,选择最⻓时间没有被访问的⻚⾯进⾏置换,也就是说,该算法假设已经很久没有使⽤的⻚⾯很有可能在未来较⻓的⼀段时间内仍然不会被使⽤。

    这种算法近似最优置换算法,最优置换算法是通过「未来」的使⽤情况来推测要淘汰的⻚⾯,⽽ LRU 则是通过「历史」的使⽤情况来推测要淘汰的⻚⾯。

    假设使⽤最近最久未使⽤的置换算法,则过程如下图:

    在这里插入图片描述

    在这个请求的⻚⾯序列中,缺⻚共发⽣了 9 次,⻚⾯置换共发⽣了 6 次,跟先进先出置换算法⽐较起来,性能提⾼了⼀些。

    • 虽然 LRU 在理论上是可以实现的,但代价很⾼。为了完全实现 LRU,需要在内存中维护⼀个所有⻚⾯的链表,最近最多使⽤的⻚⾯在表头,最近最少使⽤的⻚⾯在表尾。

    • 困难的是,在每次访问内存时都必须要更新「整个链表」。在链表中找到⼀个⻚⾯,删除它,然后把它移动到表头是⼀个⾮常费时的操作。

    所以,LRU 虽然看上去不错,但是由于开销⽐较⼤,实际应⽤中⽐较少使⽤。

    4、时钟页面置换算法

    那有没有⼀种即能优化置换的次数,也能⽅便实现的算法呢?

    时钟⻚⾯置换算法就可以两者兼得,它跟 LRU 近似,⼜是对 FIFO 的⼀种改进。

    该算法的思路是,把所有的⻚⾯都保存在⼀个类似钟⾯的「环形链表」中,⼀个表针指向最⽼的⻚⾯。

    当发⽣缺⻚中断时,算法⾸先检查表针指向的⻚⾯:

    • 如果它的访问位位是 0 就淘汰该⻚⾯,并把新的⻚⾯插⼊这个位置,然后把表针前移⼀个位置;
    • 如果访问位是 1 就清除访问位,并把表针前移⼀个位置,重复这个过程直到找到了⼀个访问位为 0 的⻚⾯为⽌;

    时钟⻚⾯置换算法的⼯作流程图如下:

    在这里插入图片描述

    5、最不常⽤算法

    最不常⽤(LFU)算法,当发⽣缺⻚中断时,选择「访问次数」最少的那个⻚⾯,并将其淘汰

    它的实现⽅式是,对每个⻚⾯设置⼀个「访问计数器」,每当⼀个⻚⾯被访问时,该⻚⾯的访问计数器就累加 1。在发⽣缺⻚中断时,淘汰计数器值最⼩的那个⻚⾯。

    看起来很简单,每个⻚⾯加⼀个计数器就可以实现了,但是在操作系统中实现的时候,我们需要考虑效率和硬件成本的。

    • 要增加⼀个计数器来实现,这个硬件成本是⽐较⾼的,另外如果要对这个计数器查找哪个⻚⾯访问次数最⼩,查找链表本身,如果链表⻓度很⼤,是⾮常耗时的,效率不⾼。

    • 但还有个问题,LFU 算法只考虑了频率问题,没考虑时间的问题,⽐如有些⻚⾯在过去时间⾥访问的频率很⾼,但是现在已经没有访问了,⽽当前频繁访问的⻚⾯由于没有这些⻚⾯访问的次数⾼,在发⽣缺⻚中断时,就会可能会误伤当前刚开始频繁访问,但访问次数还不⾼的⻚⾯。

    那这个问题的解决的办法还是有的,可以定期减少访问的次数,⽐如当发⽣时间中断时,把过去时间访问的⻚⾯的访问次数除以 2,也就说,随着时间的流失,以前的⾼访问次数的⻚⾯会慢慢减少,相当于加⼤ 了被置换的概率。

    整理自小林coding所著的《图解系统》,仅做学习用,侵删

    展开全文
  • 操作系统实验五 虚拟内存页面置换算法(内含源代码和详细实验报告),详细介绍:http://blog.csdn.net/xunciy/article/details/79239096
  • (流程图)页面置换算法课程设计-页面置换算法模拟程序.doc
  • c++实现的页面置换算法模拟程序-附代码 有分析、流程图、源代码等
  • 页面置换算法实验报告,包括最佳置换算法,先进先出置换算法,最近最久未使用置换算法等等。
  • 页面置换算法实验报告_16281100_雷兵

    万次阅读 多人点赞 2019-05-28 14:35:35
    页面置换算法实验报告 1实验题目 设计和实现最佳置换算法、先进先出置换算法、最近最久未使用置换算法、页面缓冲置换算法;通过页面访问序列随机发生器实现对上述算法的测试及性能比较。 2实验要求 假设前提 ...
  • 页面置换算法的模拟,包含最佳置换算法、先进先出页面置换算法、最近最久未使用算法、最少使用置换算法、Clock置换算法的模拟
  • 操作系统(六) 页面置换

    千次阅读 2021-03-16 21:44:42
    知识导 一、页面置换概述 ...最佳页面置换算法基本思路是,置换在「未来」最长时间不访问的页面。 所以,该算法实现需要计算内存中每个逻辑页面的「下一次」访问时间,然后比较,选择未来最长时...
  • 模拟实现请求页式存储管理的几种基本页面置换算法,了解虚拟存储技术的特点,掌握虚拟存储请求页式存储管理
  • 【操作系统】页面置换算法(最佳置换算法)(C语言实现) #####(编码水平较菜,写博客也只是为了个人知识的总结和督促自己学习,如果有错误,希望可以指出) 1.页面置换算法: 在地址映射过程中,若在页面中发现所...
  • 计算并输出下述各种算法在不同内存容量下的命中率。 A. FIFO先进先出的算法 B. LRR最近最少使用算法 C. OPT最佳淘汰算法(先淘汰最不常用的页地址)
  • (1)加深对页面置换算法的理解。 (2)掌握几种页面置换算法的实现方法。 (3)通过实验比较各种置换算法的优劣。
  • 计算机操作系统之页面置换算法课程设计(python实现,可运行有界面程序exe)一、课程设计的目的和意义二、方案设计及开发过程1.... **算法流程图**(1) OPT页面置换算法流程图![OPT置换算法](https://i...
  • 大学课程操作系统会有很多实验,LRU页面置换也是其中的一部分,希望能够参考,此LRU内存最大块为五块,可以修改成最大块为输入限制。
  • 作者 |小林coding来源 |小林coding(CodingLin)最近,我偷偷潜伏在各大技术群,因为...所以,我这边总结了操作系统的三大调度机制,分别是「进程调度/页面置换/磁盘调度算法」,供大家复习,希望大家在秋招能斩获自...
  • 内存页面置换算法

    千次阅读 2021-12-13 21:39:09
    前面我们说过了进程的调度...最佳页面置换算法基本思路是,置换在「未来」最长时间不访问的页面。 所以,该算法实现需要计算内存中每个逻辑页面的「下一次」访问时间,然后比较,选择未来最长时间不访问的页面。 我们举
  • 操作系统页面置换算法实验报告.doc

    千次阅读 2021-05-21 02:18:17
    操作系统页面置换算法实验报告,页面置换算法实验报告,18,操作系统页面置换算法,页面置换算法,lru页面置换算法,最佳页面置换算法,fifo页面置换算法,页面置换算法代码,opt页面置换算法学 生 实 验 报 告姓名: 年级...
  • 包含五种基本算法,有算法的文字介绍,算法流程图,C语言代码。 本实验的程序设计基本上按照实验内容进行,用C语言编写程序。首先用srand( )和rand( )函数定义和产生指令序列,然后将指令序列变换成相应的页地址流,...
  • 本课程设计要求用高级语言编写和虚拟页式存储缺页计算模拟程序,掌握虚拟页式存储管理相关概念。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,451
精华内容 1,380
关键字:

页面置换算法流程图