-
2019-03-28 00:24:06
概述
我们知道当我们使用内存管理策略时,我们编程中使用的地址在0-4G之间(对于32位机器来说),但是往往实际的内存没有那么大,可能只有1G左右。当pc指针移动取址时,发现取出的虚拟地址无法映射到实际的内存页上,这种情况就称为缺页。发生缺页的原因通常是一个程序的程序段在虚拟内存上排列的较为分散,起始范围与末梢范围太大,这种情况下,每次执行到不同的段时容易发生缺页。
请求调页
- 如果本身的程序很大,请求调页时,会由于申请不到空闲页而造成调页失败现象。
- 请求调页发生在虚拟地址无法映射到有效的物理页时。
- 请求调页时如果成功申请到物理页,则将从磁盘拷贝当前进程中可执行文件的一段内容到刚申请到的物理页。
调页换入代码分析
1、当mmu从虚拟地址中无法映射到有效的物理页时,发生页错误,会进入也错误中断:
// linux-0.11/kernel/traps.c void trap_init(void) {... set_trap_gate(14,&page_fault);... }
上面的初始化代码就是设置页错误中断入口的。
2、page_fault是也错误中断入口,这中断函数就是实现了调页换入的功能:
// linux-0.11/mm/page.s page_fault: xchgl %eax,(%esp) pushl %ecx pushl %edx push %ds push %es push %fs movl $0x10,%edx // 进入内核 mov %dx,%ds mov %dx,%es mov %dx,%fs movl %cr2,%edx // 将映射失败的虚拟地址保存到edx寄存器中 pushl %edx // 压栈edx中的内容,为了后面调用do_no_page提供参数 pushl %eax testl $1,%eax jne 1f call do_no_page // 开始调用这个函数,这个函数会实现调页功能 jmp 2f 1: call do_wp_page 2: addl $8,%esp pop %fs pop %es pop %ds popl %edx popl %ecx popl %eax iret
上面一段代码是汇编代码,主要之后进入了 do_no_page这个c函数,并且提供了那个映射失败的虚拟地址参数,提供这个参数也是为了之后将换入的页重新与该地址建立映射。
3、do_no_page的实现:// linux-0.11/mm/memory.c void do_no_page(unsigned long error_code,unsigned long address) { int nr[4]; unsigned long tmp; unsigned long page; int block,i; address &= 0xfffff000; tmp = address - current->start_code; if (!current->executable || tmp >= current->end_data) { get_empty_page(address); return; } if (share_page(tmp)) return; if (!(page = get_free_page())) // 申请空闲页,此页是要拷贝磁盘中的程序段的 oom(); /* remember that 1 block is used for header */ block = 1 + tmp/BLOCK_SIZE; for (i=0 ; i<4 ; block++,i++) nr[i] = bmap(current->executable,block); bread_page(page,current->executable->i_dev,nr); // 从磁盘拷贝程序段到page i = tmp + 4096 - current->end_data; tmp = page + 4096; while (i-- > 0) { tmp--; *(char *)tmp = 0; } if (put_page(page,address)) // 将物理page与虚拟地址建立映射关系 return; free_page(page); oom(); }
从上面的注释可以发现put_page是建立映射关系的。
4、put_page的代码实现分析:// linux-0.11/mm/memroy.c unsigned long put_page(unsigned long page,unsigned long address) { unsigned long tmp, *page_table; /* NOTE !!! This uses the fact that _pg_dir=0 */ if (page < LOW_MEM || page >= HIGH_MEMORY) printk("Trying to put page %p at %p\n",page,address); if (mem_map[(page-LOW_MEM)>>12] != 1) printk("mem_map disagrees with %p at %p\n",page,address); page_table = (unsigned long *) ((address>>20) & 0xffc); // 从页目录项获取页表 if ((*page_table)&1) page_table = (unsigned long *) (0xfffff000 & *page_table); else { if (!(tmp=get_free_page())) // 申请一个物理页用来建立页表 return 0; *page_table = tmp|7; page_table = (unsigned long *) tmp; } page_table[(address>>12) & 0x3ff] = page | 7; // 将物理页框号映射到虚拟地址中 /* no need for invalidate */ return page; }
上面的代码就是重新将换入的物理页的页框号与虚拟地址建立映射关系的,到此时请求换页已完成。
更多相关内容 -
操作系统请求调页 FIFO LRU OPT
2018-01-12 22:45:21c++实现操作系统请求调页功能 分别有FIFO LRU 和OPT 算法 -
请求分页管理方式及页面分配策略
2021-08-30 21:10:15①、在程序执行过程中,当所访问的信息不在内存时,由操作系统负责将所需信息从外存调入内存【操作系统要提供请求调页功能,将缺失页面从外存调入内存】,然后继续执行程序。 ②、若内存空间不够,由操作系统负责将...一、请求分页管理方式
- 请求分页 存储管理与基本分页存储管理的主要区别:
①、在程序执行过程中,当所访问的信息不在内存时,由操作系统负责将所需信息从外存调入内存【操作系统要提供请求调页功能,将缺失页面从外存调入内存】,然后继续执行程序。
②、若内存空间不够,由操作系统负责将内存中暂时用不到的信息换出到外存【操作系统要提供页面置换的功能,将暂时用不到的页面换出外存】。
(一)页表机制
(二)缺页中断机构
- 假设此时要访问逻辑地址=(页号,页内偏移量)=(0, 1024)
- 在请求分页系统中,每当要访问的页面不在内存时,便产生一个缺页中断,然后由操作系统的缺页中断处理程序处理中断。
- 此时缺页的进程阻塞,放入阻塞队列,调页完成后再将其唤醒,放回就绪队列。
1. 内存存在空闲块
- 如果内存中有空闲块,则为进程分配一个空闲块,将所缺页面装入该块,并修改页表中相应的页表项。
2. 内存中不存在空闲块
- 如果内存中没有空闲块,则由页面置换算法选择一个页面淘汰,若该页面在内存期间被修改过,则要将其写回外存。未修改过的页面不用写回外存。
(三)缺页中断机构
- 缺页中断**是因为当前执行的指令想要访问的目标页面未调入内存而产生的,因此属于内中断一条指令在执行期间,可能产生多次缺页中断。(如:copy A to B,即将逻辑地址A中的数据复制到逻辑地址B,而A、B属于不同的页面,则有可能产生两次中断)
(四)地址变换机构
- 请求分页存储管理与基本分页存储管理的主要区别:
在程序执行过程中,当所访问的信息不在内存时,由操作系统负责将所需信息从外存调入内存,然后继续执行程序。
若内存空间不够,由操作系统负责将内存中暂时用不到的信息换出到外存。
- 新增步骤1:请求调页(查到页表项时进行判断)
- 新增步骤2:页面置换(需要调入页面,但没有空闲内存块时进行)
- 新增步骤3:需要修改请求页表中新增的表项
二、页面分配策略
(一)驻留集
- 驻留集:指请求分页存储管理中给进程分配的物理块的集合。
- 在采用了虚拟存储技术的系统中,驻留集大小一般小于进程的总大小。
- 考虑一个极端情况,若某进程共有100个页面,则该进程的驻留集大小为100时进程可以全部放入内存,运行期间不可能再发生缺页。若驻留集大小为1,则进程运行期间必定会极频繁地缺页
- 若驻留集太小,会导致缺页频繁,系统要花大量的时间来处理缺页,实际用于进程推进的时间很少;
- 驻留集太大,又会导致多道程序并发度下降,资源利用率降低。所以应该选择一个合适的驻留集大小。
- 固定分配:操作系统为每个进程分配一组固定数目的物理块,在进程运行期间不再改变。即,驻留集大小不变
- 可变分配:先为每个进程分配一定数目的物理块,在进程运行期间,可根据情况做适当的增加或减少。即,驻留集大小可变。
- 局部置换:发生缺页时只能选进程自己的物理块进行置换。
- 全局置换:可以将操作系统保留的空闲物理块分配给缺页进程,也可以将别的进程持有的物理块置换到外存,再分配给缺页进程。
(二)页面分配、置换策略
- 固定分配局部置换 :系统为每个进程分配一定数量的物理块,在整个运行期间都不改变。若进程在运行中发生缺页,则只能从该进程在内存中的页面中选出一页换出,然后再调入需要的页面。这种策略的缺点是:很难在刚开始就确定应为每个进程分配多少个物理块才算合理。(采用这种策略的系统可以根据进程大小、优先级、或是根据程序员给出的参数来确定为一个进程分配的内存块数)
- 可变分配全局置换 :刚开始会为每个进程分配一定数量的物理块。操作系统会保持一个空闲物理块队列。当某进程发生缺页时,从空闲物理块中取出一块分配给该进程;若已无空闲物理块,则可选择一个未锁定的页面换出外存,再将该物理块分配给缺页的进程。采用这种策略时,只要某进程发生缺页,都将获得新的物理块,仅当空闲物理块用完时,系统才选择一个未锁定的页面调出。被选择调出的页可能是系统中任何一个进程中的页,因此这个被选中的进程拥有的物理块会减少,缺页率会增加。
【系统会锁定一些面,这些页面中的内容不能置换出外存(如:重要的内核数据可以设为“锁定”)】
- 可变分配局部置换 :刚开始会为每个进程分配一定数量的物理块。当某进程发生缺页时,只允许从该进程自己的物理块中选出一个进行换出外存。如果进程在运行中频繁地缺页,系统会为该进程多分配几个物理块,直至该进程缺页率趋势适当程度;反之,如果进程在运行中缺页率特别低,则可适当减少分配给该进程的物理块。
- 可变分配全局置换 :只要缺页就给分配新物理块
- 可变分配局部置换 :要根据发生缺页的频率来动态地增加或减少进程的物理块
(三)何时调入页面?
- 预调页策略:根据局部性原理
【局部性原理:主要指空间局部性,即:如果当前访问了某个内存单元,在之后很有可能会接着访问与其相邻的】
,一次调入若干个相邻的页面可能比一次调入一个页面更高效。但如果提前调入的页面中大多数都没被访问过,则又是低效的。因此可以预测不久之后可能访问到的页面,将它们预先调入内存,但目前预测成功率只有50%左右。故这种策略主要用于进程的首次调入【运行前调入】
,由程序员指出应该先调入哪些部分。 - 请求调页策略:进程在运行期间发现缺页时才将所缺页面调入内存
【运行时调入】
。由这种策略调入的页面一定会被访问到,但由于每次只能调入一页,而每次调页都要磁盘I/O操作,因此I/O开销较大。
- 系统拥有足够的对换区空间:页面的调入、调出都是在内存与对换区之间进行,这样可以保证页面的调入、调出速度很快。在进程运行前,需将进程相关的数据从文件区复制到对换区。
- 系统缺少足够的对换区空间:凡是不会被修改的数据都直接从文件区调入,由于这些页面不会被修改,因此换出时不必写回磁盘,下次需要时再从文件区调入即可。对于可能被修改的部分,换出时需写回磁盘对换区,下次需要时再从对换区调入。
- UNIX 方式:运行之前进程有关的数据全部放在文件区,故未使用过的页面,都可从文件区调入。若被使用过的页面需要换出,则写回对换区,下次需要时从对换区调入。
(四)抖动(颠簸)现象
(五)工作集
- 驻留集 :指请求分页存储管理中给进程分配的内存块的集合。
- 工作集 :指在某段时间间隔里,进程实际访问页面的集合。
- 工作集大小可能小于窗口尺寸,实际应用中,操作系统可以统计进程的工作集大小,根据工作集大小给进程分配若干内存块。如:窗口尺寸为5,经过一段时间的监测发现某进程的工作集最大为3,那么说明该进程有很好的局部性,可以给这个进程分配3个以上的内存块即可满足进程的运行需要。一般来说,驻留集大小不能小于工作集大小,否则进程运行过程中将频繁缺页。
- 拓展:基于局部性原理可知,进程在一段时间内访问的页面与不久之后会访问的页面是有相关性的。因此,可以根据进程近期访问的页面集合(工作集)来设计一种页面置换算法——选择一个不在工作集中的页面进行淘汰。
- 请求分页 存储管理与基本分页存储管理的主要区别:
-
操作系统 请求分页存储管理方式(含页面置换算法)
2022-01-14 16:18:01请求分页系统是建立在基本分页基础上的,为了能支持虚拟存储器功能,而增加了请求调页功能和页面置换功能。 相应地,每次调入和换出的基本单位都是长度固定的页面。因此,请求分页便称为目前最常用的一种实现虚拟...1. 请求分页存储管理方式
请求分页系统是建立在基本分页基础上的,为了能支持虚拟存储器功能,而增加了请求调页功能和页面置换功能。
相应地,每次调入和换出的基本单位都是长度固定的页面。因此,请求分页便称为目前最常用的一种实现虚拟存储器的方式。
1.1 请求分页中的硬件支持
为了实现请求分页,系统必须提供一定的硬件支持。计算机系统除了要求一定容量的内存和外存外,还需要有请求页表机制、缺页中断机制以及地址变换机构。
1.1.1 请求页表机制
在请求分页系统中需要的主要数据结构是请求页表,其基本作仍然是将用户地址空间中的逻辑地址映射为内存空间中的物理地址。
为了满足页面换进换出的需要,在请求页表中又增加了四个字段。
-
状态位(存在位)P:用于指示该页是否已调入内存
-
访问字段A:用于记录本页在一段时间内被访问的次数
-
修改位M:标识该页在调入内存后是否被修改过
-
外存地址:用于指出该页在外存上的地址
1.1.2 缺页中断机构
在请求分页系统中,每当所要访问的页面不在内存时,便产生一缺页中断,请求OS将所缺之页调入内存。
缺页中断是一种特殊的中断,它与一般的中断相比有着明显的区别,主要表现在两个方面:
- 在指令执行期间产生和处理中断信号
- 一条指令在执行期间可能产生多次缺页中断
1.1.3 地址变换机构
如图展示请求分页系统中的地址变换过程
2. 页面置换算法
2.1 介绍
在进程运行过程中,若其所要访问的页面不在内存,而需把它们调入内存,但内存已无空闲空间时,为了保证该进程能正常运行,系统必须从内存中调出一页程序或数据送到磁盘的对换区中。但应将哪个页面调出,须根据一定的算法来确定。通常,把选择换出页面的算法称为页面置换算法(Page-Replacement Algorithm)。
不适当的算法可能会导致进程发生“抖动”(Thrashing),即刚被换出的页很快又要被访问,需要将它重新调入,此时又需要再选一页调出,而此刚被换出的页很快又要被访问,又需将它调入,因此我们称该进程发生了“抖动”。
2.2 最佳(Optimal)置换算法
介绍:
最佳置换算法是一种较为极端,理想化的算法,它具有最好的性能,但实际上是无法实现的。通常以其为标准,来衡量其它算法的优劣。
原理:
其所选择的被淘汰页面将是以后永不使用的,或许是在最长(未来)时间内不再被访问的页面。
特点:
-
可保证获得最低的缺页率
-
因人们无法预知一个进程在内存的若干个页面中,究竟哪个是未来最长时间内不再被访问的,故该算法无法实现
2.3 先进先出页面置换算法(FIFO)
原理:
总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单,只需把一个进程已调入的页面按先后次序链接成一个队列,并设置一个指针,称为替换指针,使它总指向最老的页面。
特点:
通常与进程实际运行的规律不相适应,因为有些页面会经常被访问,如全局变量、常用函数等,故可能是性能最差的算法,实际应用极少。
2.4 最近最久未使用置换算法(LRU,Least Recently Used)
原理:
该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问以来所经历的时间t。当需淘汰一个页面时,选择现有页面中其t值最大的,即最近最久未使用的页面予以淘汰。
特点:
-
该算法是根据页面调入内存后的使用情况做出决策的
-
要求系统有较多的支持硬件,为了了解一个进程在内存中的各个页面各有多少时间未被进程访问,以及如何快速地知道哪一页是最近最久未使用的页面,须有寄存器和栈两类硬件之一的支持。
2.5 最少使用置换算法(LFU, Least Frequently Used)
原理:
该算法为在内存中的每个页面设置一个移位寄存器,用来记录该页面被访问的频率。每次访问某页时,便将该移位寄存器的最高位置1,再每隔一定时间(例如100ms)右移一次。LFU置换算法的页面访问图与上面的LRU置换算法的访问图完全相同。
或者说,利用一套硬件既可实现LRU算法,又可实现LFU算法。
特点:
这种算法并不能真正反映出页面的使用情况,因为在每一时间间隔内,只是用寄存器的一位来记录页的使用情况。因此,在该时间间隔内,对某页访问一次和访问100次效果等效。
2.6 简单的Clock置换算法
介绍:
LRU算法需要较多硬件支持,成本较高,实际应用中,大多采用LRU的近似算法。Clock算法就是用得较多的一种LRU近似算法。
原理:
当利用简单的Clock置换算法时,只需为每页设置一位访问位,再将内存中的所有页面都通过链接指针链接成一个循环队列。
当某页被访问时,其访问位被置1。置换算法在选择一页淘汰时,只需检查页的访问位。如果是0,选择该页换出;若为1,则重新将它置0,暂不换出,给予该页第二次驻留内存的机会,
再按照FIFO算法检查下一个页面。当检查到队列中的最后一个页面,若其访问为仍为1,则再返回到队首去检查第一个页面。
特点:
该算法是循环地检查各页面的使用情况,故称为Clock算法
因该算法只有一位访问位,只能用其表示该页是否已经使用过,而置换是将未使用过的页面换出去,故该算法又称为最近未用算法或者NRU(Not Recently Used)算法。
2.7 页面缓冲算法(PBA,Page Buffering Algorithm)
内存分配策略上采用了可变分配和局部置换方式,系统为每个进程分配一定数目的物理块,系统自己保留一部分空闲物理块。
为了能显著地降低页面换进、换出地频率,在内存中设置了如下两个链表:
实际上该链表是一个空闲物理块链表,是系统掌握地空闲物理块,用于分配给频繁发生缺页的进程,已降低该进程的缺页率。
当进程需要读入一个页面时,便可利用空闲物理链表中的第一个物理块来装入该页;
当有一个未被修改的页要换出时,实际上并不将它换出到外存,而是把它们所在的物理块挂在空闲链表的末尾。
该链表是由已修改的页面所形成的链表。设置该链表的目的是为了减少已修改页面换出的次数。
当进程需要将一个已修改的页面换出时,系统并不立即把它换出到外存上,而是将它所在的物理块挂在修改页面链表的末尾。
- 显著地降低了页面换进、换出的频率,使磁盘I/O的操作次数大为减少,减少了页面换进、换出的开销。
- 正是由于换入换出的开销大幅度减小,才能使其采用一种较简单的置换策略,如先进先出(FIFO)算法,它并不需要特殊硬件的支持,实现起来非常简单。
参考:《计算机操作系统》(第四版,汤小凤)
看教材枯燥,码字记录提神,根据计算机操作系统(第四版,汤小凤)个人整理,仅作学习记录 :)
-
-
请求分页系统中的置换算法(FIFO、LRU、Optimal)
2021-05-06 07:31:48题目描述:请求分页系统中的置换算法 1.通过如下方法产生一指令序列,共 320 条指令。 A. 在[1,32k-2]的指令地址之间随机选取一起点M,访问 M; B. 顺序访问M+1; C. 在[0,M-1]中随机选取M1,访问 M1; D. 顺序...操作系统实验导航
实验一:银行家算法 https://blog.csdn.net/weixin_46291251/article/details/115384510
实验二:多级队列调度和多级反馈队列调度算法 https://blog.csdn.net/weixin_46291251/article/details/115530582
实验三:动态分区式内存管理 https://blog.csdn.net/weixin_46291251/article/details/115772341
实验四:Linux下多进程通信 https://blog.csdn.net/weixin_46291251/article/details/116274665
实验五:进程通信的三种方式 https://blog.csdn.net/weixin_46291251/article/details/116301250
实验六:Linux文件系统实验 https://blog.csdn.net/weixin_46291251/article/details/116423798
实验七:自制简单U盘引导程序 https://blog.csdn.net/weixin_46291251/article/details/116427629
实验八:磁盘调度算法 https://blog.csdn.net/weixin_46291251/article/details/116431907
实验九:请求分页系统中的置换算法 https://blog.csdn.net/weixin_46291251/article/details/116443021
学习笔记:操作系统复习笔记 https://blog.csdn.net/weixin_46291251/article/details/117086851背景
- 先进先出(FIFO)页面置换算法
该算法总是淘汰最新进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单,只需把一个进程已调入内存的页面,按先后次序链接成一个队列,并设置一个指针,称为替换指针,使它总是指向最老的页面。 - 最近最久未使用(LRU)页面置换算法
最近最久未使用(LRU)页面置换算法,是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况,只能利用“最近的过去”作为“最近的将来”的近似, 因此,LRU 置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问以来所经历的时间 t,当需淘汰一个页面时,选择现有页面中其 t 值最大的,即最近最久未使用的页面予以淘汰。 - 最佳(Optimal)页面置换算法
该算法选择的被淘汰页面,将是以后永远不使用的,或许是在最长(未来)时间内不再被访问的页面。采用该算法,通常可保证获得最低的缺页率。但由于人们目前还无法预知一个进程在内存的若干个页面中,哪一个页面是未来最长时间内不再被访问的,因而该算法是无法实现的,但可以利用该算法去评价其他算法。
题目描述:请求分页系统中的置换算法
1.通过如下方法产生一指令序列,共 320 条指令。
- A. 在[1,32k-2]的指令地址之间随机选取一起点M,访问 M;
- B. 顺序访问M+1;
- C. 在[0,M-1]中随机选取M1,访问 M1;
- D. 顺序访问M1+1;
- E. 在[M1+2,32k-2]中随机选取M2,访问 M2;
- F. 顺序访问M2+1;
- G. 重复 A—F,直到执行 320 次指令。
- H.指令序列变换成页地址流设:(1)页面大小为 1K;(2)用户虚存容量为 32K。
2. 计算并输出下述各种算法在不同内存页块(页块个数范围:8-32)下的命中率。
- A. 先进先出(FIFO)页面置换算法
- B. 最近最久未使用(LRU)页面置换算法
- C. 最佳(Optimal)页面置换算法
提示:
- A.命中率=1-页面失效次数/页地址流长度
- B.本实验中,页地址流长度为 320,页面失效次数为每次访问相应指令时,该指令所对应的页不在内存的次数。
算法设计
整体设计
设置全局变量保存指令的个数和指令数组,在
make_instruct()
函数中生成随机数填充这个数组。
内存这里用链表来组织,表示如下:struct node { int instruct = 0; int time = 0; node* next = NULL; };
instruct表示指令号,time在不同算法中有具体含义。
三种算法对于三个函数,每个函数都是如:double f(int a);
的格式,其中参数表示当前内存块大小(8-32),返回值是命中率。
主函数只需对不同的内存块大小调用三个函数并输出结果即可。产生指令序列
首先写一个函数生成给定范围内的一个随机数,由于需要连续获得多个随机数,这里先在main函数srand一个种子,然后不断调用函数即可。
srand((unsigned int)time(NULL)); int rand(int min, int max)//产生指定范围[min,max]的随机数。 { return rand() % (max - min + 1) + min; }
构造指令序列,只需要简单的按照题目要求一步步做并且循环即可,注意这里只在循环开始处有一次判断,而每次循环会产生6个指令,所以这里将指令数组开大了一点,省去了多次判断。
const int instruct_num = 320; int instruct_arr[instruct_num + 6];
另外,为了输出结果的美观用cout << setw(8)
设置输出的宽度以对齐。void make_instruct() {//产生指令序列 int n = 0; while (n < instruct_num) { int M = rand(1,30); instruct_arr[n++] = M; instruct_arr[n++] = M + 1; int M1 = rand(0, M - 1); instruct_arr[n++] = M1; instruct_arr[n++] = M1 + 1; int M2 = rand(M1 + 2, 30); instruct_arr[n++] = M2; instruct_arr[n++] = M2 + 1; } }
先进先出(FIFO)
这是最基础的,以下的算法都继承这种思想,只是用于淘汰的策略有所变化。
首先新建两个节点Head
和Tail
Head为头节点,其数据域Head->instruct
表示当前内存中实际有多少被占用,其next指向第一块被占用的内存。Tail为尾指针,指向内存的尾部。
算法首先是一层循环,遍历所有的(320个)指令。对于每个指令判断是否在内存中,若在则hit
置为1。如果在内存中则不做任何操作,不在则要让failure_times
加一,然后判断内存是否被占满,若未被占满则直接加入链表,若被占用则要淘汰当前队列中的一个指令,并将当前指令插入内存的合适位置。
这里用到的淘汰算法:先进先出,即找到最先进来的即可,这里我是每次插入到链表尾,故链表头是最先进来的,所以每次都删除链表头后面的第一个指令并将新指令加到链表尾即可,注意每次更新Tail的位置。最近最久未使用(LRU)
这里只介绍与FIFO不同之处。
- 设立一个变量
clock
表示时钟,初始值为999,主循环一次clock就减1. - 如果当前指令在内存中则将其时间刷新为当前的时钟。
- 淘汰算法:遍历内存队列找到time最大的,将其替换为新的节点即可,新加入的节点time为当前时钟clock
最佳(Optimal)
- 淘汰算法:每次遍历内存队列,对于每个指令,再次遍历全部指令集,找到将来还要多久这条指令会再被执行(下一个出现的位置减去当前位置)。
代码实现
#include <iostream> #include <time.h> #include <iomanip> using namespace std; const int instruct_num = 320; int instruct_arr[instruct_num + 6]; struct node { int instruct = 0; int time = 0; node* next = NULL; }; int rand(int min, int max)//产生指定范围[min,max]的随机数。 { return rand() % (max - min + 1) + min; } void make_instruct() {//产生指令序列 int n = 0; while (n < instruct_num) { int M = rand(1,30); instruct_arr[n++] = M; instruct_arr[n++] = M + 1; int M1 = rand(0, M - 1); instruct_arr[n++] = M1; instruct_arr[n++] = M1 + 1; int M2 = rand(M1 + 2, 30); instruct_arr[n++] = M2; instruct_arr[n++] = M2 + 1; } } double C_FIFO(int block_size) { int failure_times = 0; node* Head = new node; node* Tail = Head; for (int i = 0; i < instruct_num; i++) { int cur_instruct = instruct_arr[i]; int hit = 0; for (node* p = Head->next; p != NULL; p = p->next) if (p->instruct == cur_instruct) hit = 1; if (!hit){ failure_times++; if (Head->instruct >= block_size) //内存已满 Head->next = Head->next->next; else Head->instruct++; Tail->next = new node; Tail = Tail->next; Tail->instruct = cur_instruct; Tail->next = NULL; } } return 1.0 - (double)failure_times / instruct_num; } double C_LRU(int block_size) { int failure_times = 0; node* Head = new node; node* Tail = Head; int clock = 999; for (int i = 0; i < instruct_num; i++) { clock--; int cur_instruct = instruct_arr[i]; int hit = 0; for (node* p = Head->next; p != NULL; p = p->next) if (p->instruct == cur_instruct) { hit = 1; p->time = clock;//刷新时钟 } if (!hit) { failure_times++; if (Head->instruct >= block_size) { //内存已满 node* t = new node; t->time = -1; for (node* p = Head->next; p != NULL; p = p->next)//遍历找到最久未使用的 if (p->time > t->time) t = p; t->instruct = cur_instruct; t->time = clock; } else { Head->instruct++; Tail->next = new node; Tail = Tail->next; Tail->instruct = cur_instruct; Tail->time = clock; Tail->next = NULL; } } } return 1.0 - (double)failure_times / instruct_num; } double C_Optimal(int block_size) { int failure_times = 0; node* Head = new node; node* Tail = Head; for (int i = 0; i < instruct_num; i++) { int cur_instruct = instruct_arr[i]; int hit = 0; for (node* p = Head->next; p != NULL; p = p->next) if (p->instruct == cur_instruct) hit = 1; if (!hit) { failure_times++; if (Head->instruct >= block_size) { //内存已满 //找到每个请求还有多久会被用到 for (node* p = Head->next; p != NULL; p = p->next) { p->time = 999; for (int j = i + 1; j < instruct_num; j++) if (p->instruct == instruct_arr[i]) { p->time = j - i; break; } } //找到最久不被用到的淘汰 node* t = new node; t->time = -1; for (node* p = Head->next; p != NULL; p = p->next)//遍历找到最久未使用的 if (p->time > t->time) t = p; t->instruct = cur_instruct; } else { Head->instruct++; Tail->next = new node; Tail = Tail->next; Tail->instruct = cur_instruct; Tail->next = NULL; } } } return 1.0 - (double)failure_times / instruct_num;; } int main() { srand((unsigned int)time(NULL)); make_instruct(); cout << "指令序列为:" << endl; int i = 0; while (i++ < instruct_num) { cout << instruct_arr[i] << "\t"; if (i % 20 == 0)cout << endl; }cout << endl << endl; cout << "SIZE\t\t" << "FIFO\t\t" << "LRU\t\t" << "Optimal" << endl; for (int disk_block_size = 8; disk_block_size <= 32; disk_block_size++) { cout << disk_block_size << "\t"; cout << setw(8) << C_FIFO(disk_block_size) << "\t"; cout << setw(8) << C_LRU(disk_block_size) << "\t"; cout << setw(8) << C_Optimal(disk_block_size) << "\t"; cout << endl; } }
运行结果
- 先进先出(FIFO)页面置换算法
-
存储管理系统课程设计——C语言实现请求页式存储管理模拟系统
2021-02-13 10:11:09在为进程分配内存时,以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。虚拟内存的作用内存在计算机中的作用很大,电脑中所有运行的程序都需要经过内存来执行,如果执行的程序很大或很多,就会... -
虚拟存储器——调页策略
2018-12-03 16:49:41何时调入页面 1.预调页策略: 以预测为基础,将预计不久后便会被访问的若干页面,预先调入内存。 优点:一次调入若干页,效率较好 ...优点:由请求调页策略所确定调入的页,一定会被访问;比较容易实现。 缺点:... -
13 操作系统第三章 内存管理 虚拟内存 请求分页管理方式 页面置换算法 页面分配策略
2020-06-18 16:20:36文章目录1 虚拟内存1.1 传统存储管理方式的特征、缺点1.2 局部性原理1.3 虚拟内存主要特征1.4 如何实现虚拟内存技术1.5 虚拟内存的基本概念小结2 请求分页管理方式2.1 页表机制2.2 缺页中断机构2.3 地址变换机构2.4 ... -
OS- -请求分页系统、请求分段系统和请求段页式系统(二)
2020-07-30 18:10:54OS- -请求分页系统、请求分段系统和请求段页式系统(二) 文章目录OS- -请求分页系统、请求分段系统和请求段页式系统(二)一、基本分段存储管理方式1.分段系统的组成:2.段表3.查找过程4.分段和分页的对比二、段页式内存... -
实现请求分页系统中页面置换算法(FIFO和LRU置换算法)——操作系统实验
2020-06-11 20:16:32例:已知 进程页面走向如下: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 供该进程使用的内存块数为3, 采用 请求 调页 策略。 (1) 画出访问各页时内存块中页号情况 (2) 求缺页率... -
请求调页存储管理方式的模拟(安排上了!)
2018-12-21 22:35:18通过对页面、页表、地址转换和页面置换过程的模拟,加深对请求调页系统的原理和实现过程的理解。 2、实验内容 (1)假设每个页面中可存放10条指令,分配给一作业的内存块数为4。 (2)用C语言模拟一作业的执行... -
操作系统知识点总结(十一)虚拟内存,请求分页,页面置换算法,页面抖动
2018-10-31 02:13:09上一节所讨论的各种内存管理策略都是为了同时将多个进程保存在内存中以便允许多道程序设计。它们都具有以下两个共同的特征: 1) 一次性 作业必须一次性全部装入内存后,方能开始运行。这会导致两种情况发生: 当... -
【题集】测得某个采用按需调页策略的系统部分状态数据为:CPU利用率为20%,对换空间的磁盘利用率为98%,...
2019-07-08 20:07:10测得某个采用按需调页策略的系统部分状态数据为:CPU利用率为20%,对换空间的磁盘利用率为98%,其他设备的利用率为5%,由此断定系统出现异常。此种情况下( )能提高利用率。 A.安装一个更快的硬盘 B.通过扩大硬盘... -
请求分页系统中的内存分配策略
2020-07-22 08:29:21局部置换:如果进程在运行期间发现缺页,则只能从分配给该进程的n个页面中选出一页换出,再调如一页,以保证分配给该进程的内存空间不变。 缺点:为每个进程分配多少个物理块难以确定。太少,会频繁出现缺页中断,... -
操作系统 请求分页管理(续)
2020-12-23 13:19:19页分配和页置换策略 最小物理块数的确定 指保证进程正常运行所需的最小物理块数。当系统分配的物理块数少于此值时,进程将无法运行 进程应获得的最小物理块数与计算机的硬件结构有关,取决于指令的格式、 功能和... -
页面调入策略
2020-07-22 09:30:56请求调页策略 当进程在运行中需要访问某部分程序和数据时,发现其所在的页面不在内存,便立即提出请求,由OS将所需的页面调入内存,这种策略每次仅调入一页 从何处调入页面 请求分页系统中的外存分为两部分:用于... -
操作系统复习题(持续更新)
2020-05-26 20:23:46在请求调页系统中有着多种置换算法:(1)选择最先进入内存的页面予以淘汰的算法称为(FIFO);(2)选择在以后不再使用的页面予以淘汰的算法称为(OPT);(3)选择自上次访问以来所经历时间最长的页面予以淘汰的算法称为... -
虚拟存储器与请求分页系统详解
2022-03-15 14:44:55驻留性:作业装入内存后,便一直驻留在内存中,直至作业运行结束 问题:一次性及驻留性在程序运行时是否是必须的? 2、程序运行的局部性原理 3、虚拟存储器的定义 基于局部性原理,应用程序在运行前,没有必要... -
考研OR工作----计算机操作系统简答题及疑难知识点总结(第五章 虚拟存储器)
2020-05-30 22:59:12在第五章的学习中,主要理解虚拟存储器的基本概念和它的具体实现方法,当然也需要朋友们对请求分页系统的基本原理知识有所了解,看这篇文章的时候,会更加能够吸收相应的“简答”题型或者是会“计算”相应的题型。... -
操作系统 请求分页存储管理
2020-12-22 13:06:04当主存中没有空闲的页框时,为了要接受一个新页,需要把老的一页淘汰出去,根据什么策略选择欲淘汰的页面 页表机制 页描述子的扩充(页表机制 ) 状态位P(中断位)指示该页是在内存还是在外存 访问位A 用于记录本... -
第五章 虚拟存储器,请求页式管理
2020-04-30 11:27:00文章目录5.1 虚拟存储器概述# 5.1.1 常规存储器管理方式的特征和局部性原理# 1. 常规存储器管理方式的特征# 2. 程序运行的局部性原理# 5.1.2 虚拟存储器的定义... 请求段页式系统,PPT没有5.2 请求分页存储管理方式5... -
操作系统 请求分页式存储管理(FIFO、LRU)
2021-07-16 13:58:41通过编写分页式存储管理的模拟程序,加深对页式存储管理方式的理解,熟悉逻辑地址到物理地址的转换过程,掌握虚拟存储管理中的页面调度算法,认识分页式虚拟存储系统中缺页中断的处理过程。 实验内容 设计一个分页... -
计算机操作系统第五章测试题及答案
2018-06-12 15:22:24大项 1 of 4 - 选择题24.0/ 24.0 得分题目 1 of 274.0/ 4.0 得分Belady现象是指( )。... 引起系统抖动的现象答案:B 题目 2 of 274.0/ 4.0 得分作业在执行中发生了缺页中断,经操作系统处理后,应让其执行... -
请求分页
2018-12-09 16:59:38请求分页存储管理方式: 内存分配策略和分配算法:需解决三个问题:最小物理块的确定、物理块的分配策略,物理块的分配...在请求分页系统中,可采取两种内存分配策略,即固定和可变策略。在进行置换式也可以采取两... -
计算机操作系统实验之页面置换算法(C语言)
2019-12-08 17:25:19在进程运行过程中,如果它需要访问的页面不在内存,需要把它调入内存,但是内存已满时,需要把内存中的某页数据送到磁盘的对换区中。而选择哪个页面,则由固定的算法来决定,称为页面置换算法 -
请求分页存储管理方式
2021-04-29 16:39:41请求分页中的硬件支持 1.页表机制 ●基本作用:地址转换 ●增加页表字段,供程序在换入换出时参考 状态位P:用于指示该页是否已调入内存 访问字段A:记录本页在一段时间内被访问的次数 修改位M:该页在调入内存后是否被... -
通知系统(回调)设计
2019-09-28 14:44:31一,背景的提出 任何有接入第三方支付(如微信支付,支付宝等)经验的...一般第三方支付会通过两个方向通知商户用户在他们系统的支付情况,一个是及时的前端回调,还有一个异步的后台回调,两者的机制和目的都不... -
【操作系统】请求分页存储管理方式
2016-12-19 17:45:35请求页表机制 状态位 P:指示该页是否已调入内存。 供程序访问时参考 访问字段 A:记录本页在一段时间内被访问的次数或最近未...缺页中断机构在请求分页系统中,当访问的页不在内存,便产生一个缺页中断。缺页中断与一 -
调页系统;分页存储管理;快表是什么?计算指令操作数地址;有效存储访问时间,缺页次数,缺页率;
2019-05-26 12:14:50目录 填空题: 选择题: 简答题: ... 1. 在动态分区式内存分配算法中,倾向于... 在请求调页系统中的调页策略有 预调页策略,它是以预测为基础的;另一种是 请求调页策略 由于较易实现,故目前使用较多。 3. ... -
微信报错:请确认授权入口页所在域名,与授权后回调页所在域名相同,授权入口页所在域名:为空的问题解决
2019-03-10 16:42:01微信报错:请确认授权入口页所在域名,与授权后回调页所在域名相同,授权入口页所在域名:为空的问题解决 1、先按照微信官方给的错误提示,确定在三方平台配置的域名是否和调用页的域名一致。 2、这一步非常要...