赞
踩
目录
- Linux中,为了提高内存利用率,提供了内外存进程对换机制;内存空间的分配和回收均以页为单位进行;一个进程只需将其一部分(段或页)调入内存便可运行;还支持请求调页的虚拟存储管理方式。
- 请求调页:当进程在运行中需要访问某部分程序和数据时,发现其所在页面不在内存,就立即提出请求(向CPU发出缺中断),由系统将其所需页面调入内存。
- 为实现请求调页,核心配置了四种数据结构:页表、页框号、访问位、修改位、有效位、保护位等。
- 页面调入/清除策略:请求式调入/清除,预测式调入/清除。
- 页面分配策略:固定分配和动态分配。
- 页面置换策略:局部置换和全局置换。
- 固定分配与局部置换结合:分配给每个进程的页框数一定。
- 动态分配与全局置换结合:先为每个进程分配初始页框,随缺页中断增加分配。
- 当CPU接收到缺页中断信号,中断处理程序先保存现场,分析中断原因,转入缺页中断处理程序。该程序通过查找页表,得到该页所在外存的物理块号。
- 如果此时内存未满,能容纳新页,则启动磁盘I/O将所缺之页调入内存,然后修改页表。
- 如果内存已满,则须按某种置换算法从内存中选出一页准备换出,是否重新写盘由页表的修改位决定,然后将缺页调入,修改页表。利用修改后的页表,去形成所要访问数据的物理地址,再去访问内存数据。整个页面的调入过程对用户是透明的。
采用局部性原理进行预测,常用固定分配页框数的条件下对算法进行评估。下面将用实例说明介绍一些经典算法。假设某进程有5页代码,系统给其分配3个页框,其运行过程可以用固定的12次访页轨迹来描述。
- 前提:预先知道进程的运行轨迹。
- 条件:无法实现,用于评价其它算法。
- 主要思想:将永不使用,或在最长时间内不被使用的页面换出内存。
- 淘汰最长时间未被使用的页面。需设置页面访问记录(常采用移位寄存器或栈来实现)。
- 移位寄存器:访问某页时,将其寄存器最高位置1,定期向右移动寄存器,高位补0。选择淘汰寄存器值最低的页面。
- 栈:访问某页时将该页号从栈中移出,并将其压入栈顶。淘汰栈底的页。
如果是在给定该进程4个页框的情况下:
- 是LRU和FIFO的折衷。
- 设置1位访问位,将内存中的页面循环链接。
- 按照一段时间内对页面的访问频率大小来选择淘汰。
- 与LRU采用同样的寄存器机制。
1.先进先出(FIFO)置换算法
(1)描述:FIFO算法是最早出现的置换算法。该算法总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。
(2)优点:该算法实现简单,只需要把一个进程已调入内存的页面按先后次序链接成一个队列,并设置一个指针,称为替换指针,使它总是指向最老的页面。
(3)缺点:该算法与进程实际运行的规律不相适应,因为在进程中,有些页面经常被访问,比如:含有全局变量、常用函数、例程等的页面,FIFO算法并不能保证这些页面不被淘汰。
2.最佳(Optimal)置换算法
(1)描述:最佳置换算法是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰的页面将是以后永不使用的,或许是在最长(未来)时间内不再被访问的页面。
(2)优点:采用最佳置换算法通常可以保证获得最低的缺页率。
(3)缺点:人们目前通常还无法预知,一个进程在内存的若干个页面中,哪一个页面是未来最长时间内不再被访问的,因此,该算法是无法实现的,但可以利用该算法去评价其他算法。
3.LRU(Least Recently Used)置换算法
(1)描述:最近最久未使用(LUR)的页面置换算法是根据页面调入内存后使用情况做出决策的。由于无法预测各页面将来的使用情况,只能利用“最近的过去”做“最近的将来”的近似,因此,LUR置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问以来所经历的时间t。当需要淘汰一个页面时,选择现有页面中t值最大的,及最近最久未使用的页面予以淘汰。
(2)优点:考虑程序访问的时间局部性,一般能有较好的性能,实际应用多。
(3)缺点:实现会需要较多的硬件支持,会增加硬件成本。
原文链接:https://blog.csdn.net/qq_43341807/article/details/110724999
如有错误,敬请指正。
您的收藏与点赞都是对我最大的鼓励和支持!
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。