写在前面:我是【程序员宝藏】的宝藏派发员,致力于创作原创干货。我热爱技术、热爱开源与分享,创作的【计算机基础面试问题】系列文章和【计算机基础主干知识】系列文章广受好评!后期会创作更多优质原创系列文章!如果您对计算机基础知识、编程等感兴趣,可以关注我,我们一起成长!
本人力荐:如果觉得CSDN排版不够美观,欢迎来我的个人原创公zong号【程序员宝藏】(号如其名,诚不欺你!)查看有红色重点标记和排版美观的全系列文章(不细你来找我要红包)
好多同学问我要pdf版,我干脆把全部文章都整理成了pdf直接打印版,在公zong号后台回复关键字【宝藏】即可免费带回家慢慢看!
觉得有收获?希望老铁们来个三连击(点赞、评论、转发),让更多的人看到这篇文章!顺便也激励下我,嘿嘿!
相关系列文章:
- TCP三次握手和四次挥手加拓展面试题(全网最细)
- 介质访问控制全网最细没有之一
- 路由算法(全网最细)
- 各层网络协议加面试拓展(全网最细)
- 各层网络设备加拓展(全网最细)
- 线程|进程|程序比较总结(全网最细)
- 死锁加拓展问题(全网最细)
文章目录
- @[toc]
- 1.前导知识简述
- 链接和装入
- 连续分配管理方式
- 非连续分配方式
- 2.页式虚拟内存
- 页表机制
- 缺页中断机构
- 地址变换机构
- 页面置换算法
- 3.段式虚拟内存
- 4.段页式虚拟内存
文章目录
- @[toc]
- 1.前导知识简述
- 链接和装入
- 连续分配管理方式
- 非连续分配方式
- 2.页式虚拟内存
- 页表机制
- 缺页中断机构
- 地址变换机构
- 页面置换算法
- 3.段式虚拟内存
- 4.段页式虚拟内存
1.前导知识简述
【问】:为什么要进行内存管理?
答:在单道批处理系统阶段,一个系统在一个时间段内只执行一个程序,内存的分配极其简单,即仅分配给当前运行的进程。引入多道程序的并发执行后,进程之间共享的不仅仅是处理机,还有主存储器。然而,共享主存会形成一些特殊的挑战(越界、缺页等)。若不对内存进行管理,则容易导致内存数据的混乱,以至于限制进程的并发执行。因此,为了更好地支持多道程序并发执行,必须进行内存管理。
链接和装入
创建进程首先要将程序和数据装入内存。将用户源程序变为可在内存中执行的程序,通常需要以下几个步骤:
- 编译。由编译程序将用户源代码编译成若干目标模块。
- 链接。由链接程序将编译后形成的一组目标模块及所需的库函数链接在一起,形成一个完整的装入模块。
- 装入。由装入程序将装入模块装入内存运行。
程序的链接有以下三种方式:
- 静态链接:程序运行前,先将各目标模块及他们所需要的库函数链接成一个完整的可执行程序,以后不再拆开。
- 装入时动态链接:在装入时,边装入边链接。
- 运行时动态链接:对某些目标模块的链接,是在程序执行中需要该目标模块时才进行的。其优点是便于修改和更新,便于实现对目标模块的共享。
程序的装入有以下三种方式:
- 绝对装入:单道程序环境下,逻辑地址和物理地址完全相同,不需要地址变换。
- 静态重定位:装入时一次性将逻辑地址转换为物理地址(重定位)
- 动态重定位:运行时才把逻辑地址转换为物理地址,适合程序在内存中会发生移动的情况。
【问】:覆盖与交换?
答:覆盖与交换技术是用来扩充内存的两种方法。
覆盖的【基本思想】如下:由于程序运行时并非任何时候都要访问程序及数据的各个部分(尤其是大程序),因此可把用户空间分成一个固定区和若干覆盖区。将经常活跃的部分放在固定区,其余部分按调用关系分段。首先将那些即将要访问的段放入覆盖区,其他段放在外存中,在需要调用前,系统再将其调入覆盖区,替换覆盖区中原有的段。覆盖技术的特点是,打破了必须将一个进程的全部信息装入主存后才能运行的限制,但当同时运行程序的代码量大于主存时仍不能运行,此外,内存中能够更新的地方只有覆盖区的段,不在覆盖区中的段会常驻内存。
交换(对换)的【基本思想】是,把处于等待状态(或在CPU 调度原则下被剥夺运行权利)的程序从内存移到辅存,把内存空间腾出来,这一过程又称换出;把准备好竞争CPU 运行的程序从辅存移到内存,这一过程又称换入。中级调度采用的就是交换技术。
【区别】交换技术主要在不同进程(或作业)之间进行,而覆盖则用于同一个程序或进程中。由于覆盖技术要求给出程序段之间的覆盖结构,使得其对用户和程序员不透明,所以对于主存无法存放用户程序的矛盾,现代操作系统是通过虚拟内存技术来解决的,覆盖技术则已成为历史;而交换技术在现代操作系统中仍具有较强的生命力。
连续分配管理方式
- 单一连续分配
- 固定分区分配
- 动态分区分配
非连续分配方式
固定分区会产生内部碎片,动态分区会产生外部碎片,这两种技术对内存的利用率都比较低。我们希望内存的使用能尽量避免碎片的产生,这就引入了分页的思想:把主存空间划分为大小相等且固定的块,块相对较小,作为主存的基本单位。每个进程也以块为单位进行划分,进程在执行时,以块为单位逐个申请主存中的块空间。
- 基本分页存储管理方式
- 基本分段存储管理方式
- 基本段页式管理方式
2.页式虚拟内存
基于局部性原理,在程序装入时,将程序的一部分装入内存,而将其余部分留在外存,就可
启动程序执行。在程序执行过程中,当所访问的信息不在内存时,由操作系统将所需要的部分调入内存,然后继续执行程序。另一方面,操作系统将内存中暂时不使用的内容换出到外存上,从而腾出空间存放将要调入内存的信息。这样,系统好像为用户提供了一个比实际内存大得多的存储器,称为虚拟存储器。
【局部性原理】:快表、页高速缓存及虚拟内存技术从广义上讲,都属于高速缓存技术。这个技术所依赖的原理就是局部性原理。
局部性原理表现在以下两个方面:1) 时间局部性。程序中的某条指令一旦执行,不久后该指令可能再次执行;某数据被访问过,不久后该数据可能再次被访问。产生时间局部性的典型原因是程序中存在着大量的循环操作。2) 空间局部性。一旦程序访问了某个存储单元,在不久后,其附近的存储单元也将被访问,即程序在一段时间内所访问的地址,可能集中在一定的范围之内,因为指令通常是顺序存放、顺序执行的,数据也一般是以向量、数组、表等形式簇聚存储的。
时间局部性通过将近来使用的指令和数据保存到高速缓冲存储器中,并使用高速缓存的层次
结构实现。空间局部性通常使用较大的高速缓存,并将预取机制集成到高速缓存控制逻辑中实现。虚拟内存技术实际上建立了“内存-外存”的两级存储器结构,利用局部性原理实现高速缓存。
请求分页系统建立在基本分页系统基础之上,为了支持虚拟存储器功能而增加了请求调页功能和页面置换功能。请求分页是目前最常用的一种实现虚拟存储器的方法。
为了实现请求分页,系统必须提供一定的硬件支持。除了需要一定容量的内存及外存的计算
机系统,还需要有页表机制、缺页中断机构和地址变换机构。
页表机制
请求分页系统的页表机制不同于基本分页系统,请求分页系统在一个作业运行之前不要求全部一次性调入内存,因此在作业的运行过程中,必然会出现要访问的页面不在内存中的情况,如何发现和处理这种情况是请求分页系统必须解决的两个基本问题。为此,在请求页表项中增加了4 个字段,如图所示:
缺页中断机构
在请求分页系统中,匈当所要访问的页面不在内存中时,便产生一个缺页中断,请求操作系
统将所缺的页调入内存。此时应将缺页的进程阻塞(调页完成唤醒),若内存中有空闲块,则分配一个块,将要调入的页装入该块,并修改页表中的相应页表项,若此时内存中没有空闲块,则要淘汰某页(若被淘汰页在内存期间被修改过,则要将其写回外存)。
【注意】:缺页中断作为中断,同样要经历诸如保护CPU 环境、分析中断原因、转入缺页中断处理程序、恢复CPU 环境等几个步骤。但与一般的中断相比,它有以下两个明显的【区别】:
1)在指令执行期间而非一条指令执行完后产生和处理中断信号,属于内部中断。
2)一条指令在执行期间,可能产生多次缺页中断。
地址变换机构
一张流程图一目了然:
页面置换算法
- 最佳(OPT) 置换算法
最佳(Optimal, 0PT) 置换算法选择的被淘汰页面是以后永不使用的页面,或是在最长时间内不再被访问的页面,以便保证获得最低的缺页率。然而,由于人们目前无法预知进程在内存下的若干页面中哪个是未来最长时间内不再被访问的,因而该算法无法实现。
- 先进先出(FIFO) 页面置换算法
优先淘汰最早进入内存的页面,即在内存中驻留时间最久的页面。该算法实现简单,只需把
调入内存的页面根据先后次序链接成队列,设置一个指针总指向最早的页面。但该算法与进程实际运行时的规律不适应,因为在进程中,有的页面经常被访问。
FIFO 算法还会产生所分配的物理块数增大而页故障数不减反增的异常现象,称为Belady 异常。只有FIFO 算法可能出现Belady 异常, LRU 和OPT 算法永远不会出现Belady 异常。
- 最近最久未使用(LRU)置换算法
选择最近最长时间未访问过的页面予以淘汰,它认为过去一段时间内未访问过的页面,在最
近的将来可能也不会被访问。该算法为每个页面设置一个访问字段,来记录页面自上次被访问以来所经历的时间,淘汰页面时选择现有页面中值最大的予以淘汰。
LRU 算法的性能较好,但需要寄存器和栈的硬件支持。LRU 是堆栈类的算法。理论上可以
证明,堆栈类算法不可能出现Belady 异常。FIFO 算法基于队列实现,不是堆栈类算法。
- 时钟(CLOCK) 置换算法
简单的CLOCK 算法给每帧关联一个附加位,称为使用位。当某页首次装入主存时,将该帧
的使用位设置为1; 当该页随后再被访问到时,其使用位也被置为1 。对于页替换算法,用于替换的候选帧集合可视为一个循环缓冲区,并有一个指针与之相关联。当某一页被替换时,该指针被设置成指向缓冲区中的下一帧。当需要替换一页时,操作系统扫描缓冲区,以查找使用位被置为0 的一帧。每当遇到一个使用位为1 的帧时,操作系统就将该位重新置为0; 若在这个过程开始时,缓冲区中所有帧的使用位均为0, 则选择遇到的第一个帧替换;若所有帧的使用位均为1,则指针在缓冲区中完整地循环一周,把所有使用位都置为0, 并停留在最初的位置上,替换该帧中的页。由于该算法循环检查各页面的情况,因此称CLOCK算法,又称最近未用(Not Recently
Used, NRU) 算法。
在使用位的基础上再增加一个修改位,则得到改进型CLOCK 置换算法。这样,每帧都处于以下4种情况之一:
1)最近未被访问,也未被修改(u= 0, m = 0) 。
2)最近被访问,但未被修改(u=l,m=0) 。
3)最近未被访问,但被修改(u=0,m= 1) 。
4)最近被访问,被修改(u=l,m=l)
算法执行步骤如下:
- 从指针的当前位置开始,扫描帧缓冲区。在这次扫描过程中,对使用位不做任何修改。选择遇到的第一个帧(u = 0, m = 0) 用于替换。
- 若第1) 步失败,则重新扫描,查找(u=0,m= 1) 的帧。选择遇到的第一个这样的帧用于替换。在这个扫描过程中,对每个跳过的帧,把它的使用位设置成0 。
- 若第2) 步失败,则指针将回到它的最初位置,且集合中所有帧的使用位均为0 。重复第
- 步,并且若有必要,重复第2) 步,以便可以找到供替换的帧。
【注意】:改进型CLOCK 算法优于简单CLOCK 算法的地方在于替换时首选没有变化的页。由于修改过的页在被替换之前必须写回,因而这样做会节省时间。
【抖动】:在页面置换过程中,一种最糟糕的情形是,刚刚换出的页面马上又要换入主存,刚刚换入的页面马上又要换出主存,这种频繁的页面调度行为称为抖动或颠簸。若一个进程在换页上用的时间多于执行时间,则这个进程就在颠簸。频繁发生缺页中断(抖动)的主要原因是,某个进程频繁访问的页面数目高于可用的物理页帧数目。
虚拟内存是怎么解决问题的?会带来什么问题?
答:虚拟内存使用外存上的空间来扩充内存空间,通过一定的换入/换出,使得整个系统在逻辑上能够使用一个远远超出其物理内存大小的内存容量。因为虚拟内存技术调换页面时需要访问外存,会导致平均访存时间增加,若使用了不合适的替换算法,则会大大降低系统性能。
【问】:多级页表解决了什么问题?又会带来什么问题?
答:多级页表解决了当逻辑地址空间过大时,页表的长度会大大增加的问题。多级页表是为了节省空间。(单级页表为了随机访问必须连续存储,如果虚拟内存空间很大,就需要很多页表项,就需要很大的连续内存空间【你能想象页表比分配的页(“运行页”)还多吗?】;但是多级页表不需要,最开始只需一页。)
【问题】:而采用多级页表时,一次访盘需要多次访问内存甚至磁盘,会大大增加一次访存的时间。
3.段式虚拟内存
段式虚拟存储器中的段是按程序的逻辑结构划分的,各个段的长度因程序而异。把虚拟地址
分为两部分:段号和段内地址。虚拟地址到实地址之间的变换是由段表来实现的。段表是程序的逻辑段和在主存中存放位置的对照表。段表的每行记录与某个段对应的段号、装入位、段起点和段长等信息。由于段的长度可变,所以段表中要给出各段的起始地址与段的长度。
段式虚拟存储器的优点是,段的分界与程序的自然分界相对应,因而具有逻辑独立性,使得它易于编译、管理、修改和保护,也便于多道程序的共享;缺点是因为段长度可变,分配空
间不便,容易在段间留下碎片,不好利用,造成浪费。
4.段页式虚拟内存
把程序按逻辑结构分段,每段再划分为固定大小的页,主存空间也划分为大小相等的页,程
序对主存的调入、调出仍以页为基本传送单位,这样的虚拟存储器称为段页式虚拟存储器。在段页式虚拟存储器中,每个程序对应一个段表,每段对应一个页表,段的长度必须是页长的整数倍,段的起点必须是某一页的起点。
虚地址分为段号、段内页号、页内地址三部分。CPU 根据虚地址访存时,首先根据段号得到段表地址;然后从段表中取出该段的页表起始地址,与虚地址段内页号合成,得到页表地址;最后从页表中取出实页号,与页内地址拼接形成主存实地址。
段页式虚拟存储器的优点是,兼具页式和段式虚拟存储器的优点,可以按段实现共享和保护。缺点是在地址变换过程中需要两次查表,系统开销较大。
不要忘记去我的个人原创公zong号【程序员宝藏】----专注于计算机基础、编程、分享,获取【宝藏】哦!
作为过来人,有考研的小伙伴可以加我好友(公zong号有二维码,备注【考研】),免费解答相关问题,做你的知心大哥哥!我们一研为定!
觉得有收获?希望老铁们来个三连击(点赞、评论、转发),让更多的人看到这篇文章!顺便也激励下我,嘿嘿!