操作系统 第三章 内存管理
这一章与计算机组成原理的内存管理基本是相同的,正因如此,会出现计算机组成原理和操作系统结合的题目,属于很重要的部分,仅次于进程部分。
3.1 内存管理概念
内存管理指的是操作系统对内存的划分和动态分配。内存管理包括内存空间的分配与回收、地址转换、内存空间的扩展和存储保护。
首先,创建进程需要几个步骤:
①编译:将代码编译为目标模块,这部分属于编译原理的知识。
②链接:将目标模块以及库函数连接在一起,形成一个完整的装入模块。
③装入:由装入模块将装入模块装入内存运行。
简单来说,这个过程指的就是将代码转换成许多个模块,之后模块加上引用的库函数组成一整个模块,之后将整个模块放入内存。
下面详细整理一下其中的连接和装入。
程序的连接,就像是串糖葫芦,把许多个小模块组装在一起,将内部的逻辑地址转换为连接在一起的完整地址。程序的连接有以下三种方式:
①静态链接:
在程序运行之前,先将各个目标模块及需要的库函数连接在一起,之后不再拆开。
②装入时动态链接:
推迟连接的过程,等到装入内存的时候才连接,即采用边装入边链接的方式。装入内存就是一个完整的模块。
③运行时动态链接:
再推迟链接的时机,只有程序执行时需要目标模块才进行连接,更加有利于修改和更新。装入的时候不一定是一个完整的模块,可以根据需要动态连接。
程序的装入是指将连接好的模块放入内存,不放入内存就无法运行。内存的装入模块在装入内存时有以下的三种方法:
①绝对装入:
在编译时,如果提前就知道装入后会放在内存的哪个位置,那么产生的地址就直接是绝对地址。绝对装入程序按照装入模块中的地址,将程序和数据装入内存。这种方式下,直接把代码放在提前设置好的地址上,逻辑地址和物理地址是一致的。这种方式只适合于单道程序环境,因为在多道程序环境下装在哪个位置是不确定的,只有在单道程序环境下才可以采用这种方式。
②可重定位装入:
多道程序环境下,可以根据当前内存的情况下,将装入模块装入内存的合适的位置,这种逻辑地址和物理位置的转换叫做重定位。进程知道的是自己内部的逻辑地址,即自己知道的世界,而实际上逻辑地址并不是全部的世界,需要通过重定位将逻辑地址换成物理地址。
地址变换如果是在装入时一次性完成的,称这种方式为静态重定位。这种方式要求作业装入内存时,必须一次性分配全部的内存空间,一旦进入内存就不允许移动。可以理解为将整个的模块拿进内存,并且将里面的逻辑地址直接全部换成物理地址。
如果装入模块装入内存时不立即全部换成绝对地址而是等到真正要用的时候才转换,这种方式就称为动态重定位,这种方式下,装入后地址仍然保持逻辑地址,只有运行时才转换为物理地址。这种方式需要一个重定位寄存器(一台设备一个即可)。动态重定位可以将程序分配到不同的位置上,根据需要动态加载代码,程序运行期间根据需要动态申请内存分配。
这个过程中所提到的两种地址,逻辑地址空间指的是编译后模块的内部地址,可以看作是进程自己以为自己的地址,模块从0号单元开始编址,物理地址空间指的是真正在内存上存放的位置,运行时存取指令和数据都要从真正的物理地址上进行存取。程序员和程序只知道逻辑地址而内存的管理机制对其完全透明,不同的进程可以有相同的逻辑地址,二者互不相干,在映射到物理位置上时就映射在不同的物理位置上。
内存在分配之前,需要保证操作系统不受到用户进程的影响,同时还需要保证用户进程之间不会越界干扰。这种措施称为内存保护,内存保护可以采用两种方法:
①设置一对上下限寄存器,存放作业的上限地址和下限地址。
②采用重定位寄存器和界地址寄存器。分别保存进程的起始位置和进程的长度。当CPU传过来进程的逻辑地址时,首先与界地址寄存器比较,如果地址大于寄存器的内容,直接认为越界。之后将逻辑地址与重定位寄存器中的内容相加,得到的地址即在内存上真正的位置。这样做的目的首先是比较逻辑地址的长度是不是已经超过了进程的长度,如果超了直接没有再去访问地址的必要。重定位寄存器是用来加的,界地址寄存器是用来比较的。
一台计算机配备一个重定位寄存器即可,一方面是因为寄存器本身很昂贵,不可能拿出来很多给地址转换来使用,另一方面是因为同一时刻只有一个进程在CPU上运行,所以只有一个重定位寄存器能用到,在进程切换时派遣程序会修改重定位寄存器的内容,从而实现基地址的转换,所以一个重定位完全可以解决问题。
内存空间的扩展也是内存管理一个需要考虑的内容,可以采用覆盖与交换两种方式。
早期计算机主存容量有限,主存中即使只有一道用户程序也有可能满足不了内存需求,所以出现了覆盖技术。覆盖技术将用户空间分为一个固定区和若干覆盖区,经常活跃的部分放在固定区,其余部分按照调用关系分段,首先将即将访问的段放在覆盖区,其他段放在外存,后序随着需要调入覆盖区并将前面的内容给覆盖掉。这种方式的出现打破了前面必须要将程序完整拿入内存的限制,但是能替换的只有覆盖区,对于固定区的代码仍然是常驻内存。
对换思想是将处于等待状态的程序从内存中拿到外存,从而空出内存,这叫换出,相对的将准备好竞争CPU的程序从外存拿进内存称为换入,第二章中的中级调度就属于一种交换技术。需要注意这种技术是在不同的进程之间进行的,而覆盖则是针对一个进程的操作。现在覆盖技术已经基本被淘汰,交换技术还很有生命力。
内存的分配管理指的是按照怎样的规则将内存进行分配。根据是否必须给进程分配连续的内存空间分为连续分配管理方式和非连续分配管理方式,同时又将是否一次性全部拿入内存将管理方式分为传统存储管理方式和虚拟存储器。3.1节介绍的都是一次性全部拿入内存的传统存储管理方式。
连续分配方式指的是需要给用户分配一个连续的内存空间,让程序的全部直接一口气放在一起。连续分配方式主要包括三种方式:
①单一连续分配:
内存在此方式下分为系统区和用户区,系统区完全是操作系统的地盘,通常在低地址部分,用户区则为是为用户准备的空间。这种方式适合单道程序环境,内存中的用户区完全是一个进程的地盘,无需进行内存保护。这种方法优点是简单、无外部碎片,可以采用覆盖技术,但是有内部碎片而且利用率极低。
②固定分区分配:
是最简单的多道程序存储管理方式,将用户内存空间划分为若干固定大小的区域,每个分区只放一道作业。当有空闲分区的时候才可以从外存加载作业到内存。分区的大小可以完全相等也可以不等。当采用不等分区时,为了方便内存分配一般将分区按照大小排队,并建立一张分区说明表表示分区的分配情况。采用这种分区方式,主要存在两个问题,一个是程序可能太大无法一次性放下,此时需要用覆盖技术,另一个是主存的利用率低,极易产生内部碎片。而且分区的数目限制了操作系统的并发能力,现在的操作系统一般不采用这种方式,对于一些控制对象全部一样的嵌入式系统有时会采用这类系统来保证系统的简单。
③动态分区分配:
又称可变分区分配,是一种动态划分内存的方法。这种方法不预先划分内存,而是在进程装入内存时根据进程的大小来建立分区,因此分区的大小和数目都是可变的。这种方法在刚开始分配的时候是好的,但是随着内存空间的不断分配,碎片越来越多,会出现一些过小以至于无法利用的小碎片,此时内存的利用率会下降很多,解决方式是采用紧凑技术,将进程进行调整和移动从而将小碎片整合成大碎片。但是这种方法需要动态重定位寄存器的支持,而且费时。所以尽可能在装入时选择尽可能少产生碎片的方法进行装入,一般主要考虑以下几种算法:
几种方法各有利弊。首次适应算法会让内存低地址部分出现很多小的空闲分区,从而增加了查找这些分区的时间,但相应的高地址上的大的空闲分区更有机会被保留。邻近适应算法则是首次适应的修改,但是这种方法常常会导致在内存的末尾分配空间,实际效果比首次适应更差。最佳适应算法看似最佳,但是会很容易产生极小的无法利用的碎片,从而增加了紧凑的时间。最坏适应算法虽然看似最坏,但是却最不容易产生碎片,相应的会让大的内存空间不足。
非连续分配管理方式指的是允许一个程序分散地装入不相邻的内存分区,这种方式可以充分利用内存空间。根据分区的大小是否固定,可以分为分页存储管理方式和分段存储管理方式。
分页存储管理方式根据是否将作业的全部页面一次性拿入内存分为基本分页存储管理方式和请求分页存储管理方式。请求分页存储管理方式将放在虚拟存储器中总结。
分页的思想是将内存和进程划分为等大的块,从而让进程以块为单位去申请主存空间。这种方式看起来很像是固定分区技术,其优点在于不会产生外部碎片,但是会在最后一个块时产生内部碎片,但是内部碎片一般不会太大,处在可以接受的范围内。
分页的相关知识,包括页表、分页、快表等在计算机组成原理部分已经总结过了,这里直接上截图。
这里需要注意,每个进程有自己的一张页表,会有一张总的页表记录每个进程的页表位置。有关页表以及页表项的计算题是这部分常考的内容,也属于操作系统和计算机组成原理的交叉部分。
操作系统中还补充了多级页表,即页表的套用,这里并不难理解,主要是为了压缩页表,采用层次结构的页表,逐层映射即可。当拿到一个虚拟地址时,先按照一级页号,找对应的页表项,这个页表项指向一个二级页表,再用二级页号去访问这个二级页表,查到的才是真正的物理块号,换头就可以得到真正的物理位置。
当分区的大小不固定时,采用的方式就称为分段,分段主要是从用户的角度来考虑的,分页站在计算机的角度,从方便管理的目的出发,将程序不管内容硬拆成等大的页,这个过程其实破坏了程序的逻辑性,而分段则是由用户根据进程中的自然段来进行划分,此时需要给出段号以及段内偏移量来确定具体的位置。这里提到段式所提供的地址是二维的,页式的地址是一维的,这种说法是因为段式需要用户来提供两部分地址,即段的号和偏移量,操作系统自身不知道每个段的大小,所以无法直接进行计算,而对于页式,用户提供的只是一个完整的逻辑地址,操作系统负责拆开成两部分再查找页表后得到物理块号,由于每个物理块的大小一样,可以直接用块号乘以块大小加上块内偏移得到物理地址,而段式每个段大小不一定一样,无法采用这种相乘的方法,所以页式中的虚拟地址对用户而言就是一个地址,所以称其为一维地址。
段表的其余知识与页表是相通的,这里便不再赘述,基本思想完全一致。
在段的知识中,由于其性质,非常方便共享。在分段系统中,段的共享是通过两个作业的段表中相应表项指向被共享的段的同一个物理副本来实现的。当一个作业正从共享段中读取数据时,必须防止另 一个作业修改此共享段中的数据。不能修改的代码称为纯代码或可重入代码(它不属于临界资源),这样的代码和不能修改的数据可以共享,而可修改的代码和数据不能共享。
在这两种方式的基础上,又延伸出了段页式,段页式结合了两种方法的优点,对作业的地址空间分段,在段内分页。这种情况下,逻辑地址就变成了三部分:段号、页号和页内偏移量。相应的地址也是二维的,需要一张段表和一张页表来实现地址的转换,一个进程中段表只有一个而页表可以有很多个。其余的操作和段式页式是一样的。
3.2 虚拟内存管理
上一节介绍的存储方式都要求一次性将程序运行所需要的模块全部加入到内存中,这一节介绍的则都是不要求全部拿入内存的管理方式。
结合计算机组成原理中的程序运行的局部性原理,程序装入时,只需要将一部分装入内存,而多余的完全可以留在外存,等需要的时候再拿进内存。这样子像是形式上给了用户一个更大的内存空间,但是实际上并没有任何扩大。称为虚拟存储器。
虚拟存储器允许作业分成多次加入内存,允许作业运行过程中进行换入和换出,这种方式从逻辑上扩充了内存的容量。
虚拟内存技术主要分为三类,请求分页存储管理、请求分段存储管理和请求段页式存储管理。不管采用哪种方式,都需要一定的硬件支持,包括内存外存、页表段表机制、中断机构和地址变换机构。
三种方式与第一节介绍的传统存储管理方式基本相似,这里只总结一下不一样的部分。
请求分页管理方式建立在基本分页系统基础之上,当需要的部分在内存上时就可以启动作业开始运行,如果不在,就需要去外存将对应的页面加载到内存上,同时还可以将不用的页面换出去。
虚拟内存管理由于并不是每次访问都在内存上,所以需要一个状态位来记录是否调入了内存,需要一个访问字段来供置换算法选择置换出去的页面,需要一个修改位标志是否对内容做出了修改从而方便写回时的判断,所以在虚拟存储器中页表项应该变成以下的样子
在请求分页系统中,每当所要访问的页面不在内存中时,便产生一个缺页中断,请求操作系统将所缺的页调入内存。如果内存没有满则直接加载到内存,如果内存已经满了,则选择一个页面置换算法将一个页面换出。缺页中断作为中断,也要满足中断的相关步骤,但是缺页中断的处理时间并不在一条指令的末端而是在内部,另外一条指令执行期间可能产生多次缺页中断。
请求分页的地址处理机构由于引入了调页等操作,所以也需要相应的做出改变。
换页算法属于请求分页中很重要的一部分,因为这是基本分页系统中所没有的部分。
进程在运行时,如果访问的页面不在内存就需要选一个页调入内存,但内存已经满了的话就只能拿一个页面出去送入磁盘的对换区,选择哪一个页面调出就属于换页算法的考虑内容了。常用的页面置换算法有四种:
①最佳置换算法(OPT)
置换算法选择的被淘汰页面是以后永不使用的页面,或是在最长时间内不再被访问的页面,以便保证获得最低的缺页率。这种算法属于对未来的预测,所以是无法实现的,但是可以用来评价其他算法。
②先进先出页面置换算法(FIFO)
优先淘汰最早进入内存的页面,即在内存中驻留时间最久的页面。该算法实现简单,只需把调入内存的页面根据先后次序链接成队列,设置一个指针总指向最早的页面。缺点在于这种算法完全考虑到达时间,这是不符合程序运行规律的。另外还会产生所分配的物理块数增大而缺页故障不减反增的现象,这种现象称为BELADY异常,属于FIFO特有的异常
③最近最久未使用置换算法(LRU)
选择最近最忙时间未访问过的页面予以淘汰,它认为过去一段时间内未问过的页面,在最近的将来可能也不会被访问 。该算法为每个页面设置一个访问字段,来记录页面自上次被访问以来所经历的时间, 淘汰页面时选择现有页面中值最大的予以淘汰。这种算法实际上是以最近的过去来推测最近的未来。
④CLOCK置换算法
简单的CLOCK置换算法需要给每个帧关联一个附加位称为使用位。当某页首次装入主存时,将该帧的使用位设置为1,当该页随后再被访问到时,其使用位也被置为1。 当需要替换一页时,操作系统扫描缓冲区,以查找使用位被置为0的一1帧。每当遇到一个使用位为1的帧时,操作系统就将该位重新置为0,若在这个过程开始时,缓冲区中所有帧的使用位均为0,则选择遇到的第一个帧替换;若所有帧的使用位均为1,则指针在缓冲区中完整地循环一周,把所有使用位都置为0,并停留在最初的位置上,替换该帧中的页。简单来说就是循环扫描,如果使用位为0就置换,如果不是0,就将1改为0并留给这个帧一个机会,循环完一轮就再来一轮。由于该算法循环检查各页面的情况,所以又称最近未用算法(NRU)。
在使用位的基础上增加一个修改位,得到的就是改进型的CLOCK置换算法,增加一位修改位后,每帧总是处于下面的四个状态之中:
改进型CLOCK置换算法也采用相似的步骤:
对比两种CLOCK置换算法,不难发现改进型其实是增加了对写回耗时的考虑,优先选择没有修改的页面,这样子不需要换出时写回,从而进一步减少了换页所用的时间。
对于分页式的虚拟内存,进程准备进行时不需要全部加载到内存,所以,操作系统必须决定读取多少页,即决定给特定的进程分配几个页框。给一个进程分配的物理页框的集合就是这个进程的驻留集。
一般采用三种策略:
①固定分配局部置换
它为每个进程分配一定数目 的物理块,在整个运行期间都不改变。若进程在运行中发生缺页,则只能从该进程在内存中的页面中选出一页换出,然后调入需要的页面。简单来说就是加载到内存时就划定好分配给进程几块,换页也只允许换掉自己的块,不允许换掉别人的块。实现这种策略时,难以确定应为每个进程分配的物理块数目:太少会频繁出现缺页中断,太多又会使CPU和其他资源利用率下降。
②可变分配全局置换
为系统中的每个进程分配一定数目的物理块,操作系统自身也保持一个空闲物理块队列。当某进程发生缺页时,系统从空闲物理块队列中取出一个物理块分配给该进程,并将欲调入的块装入其中。简单来说就是单独维护一个备用空间,将缺页时从备用空间取空页分给进程。这种方法比固定分配局部置换更加灵活,可以动态增加进程的物理块,但也存在弊端, 如它会盲目地给进程增加物理块,从而导致系统多道程序的井发能力下降。
③可变分配局部置换
属于前面两种方法的综合,它为每个进程分配一定数目的物理块,当某个进程发生缺页时,只允许从该进程在内存的页面中选出一页换出,因此不会影响其他进程的运行。若进程在运行中频繁地缺页, 则系统再为该进程分配若干物理块,直至该进程缺页率趋于适当程度;反之,若进程运行中的缺页率特别低,则可适当减少分配给该进程的物理块。这种方法动态的增加分配的块数,效果好但是实现复杂,需要更大的开销。
调入页面的时机分为两种:预调页策略(将预计会用到的页面提前加载到内存)和请求调页策略(不在内存时发出请求,缺页时从外存加载到内存)。
外存分为两部分,一部分用于存放文件,称为文件区,一部分用于存放对换页面,称为对换区。当系统用够足够的对换区空间时,可以全部从对换区调换文件。当对换区空间不足时,凡是不会被修改的文件都从文件区调入,对于可能会修改的部分,换出时调到对换区,需要时再从对换区调入。
在页面置换的过程中,会出现刚刚换出的页面马上又被换入,即频繁进行页面置换操作,这种现象被称为抖动。抖动产生的主要原因是进程频繁访问的页面数目高于可以用的物理帧数目。
工作集是指某段时间间隔内,进程要访问的页面的集合,可以用最近访问过的页面来确定工作集。
实际应用中,工作集窗口会设置得很大,即对于局部性好的程序,工作集大小一般会比工作集窗口A小很多。工作集反映了进程在接下来的一段时间内很有可能会频繁访问的页面集合,因此,若分配给进程的物理块小于工作集大小,则该进程就很有可能频繁缺页,所以为了防止这种抖动现象,一般来说分配给进程的物理块数(即驻留集大小)要大于工作集大小。
最后总的来说一下虚拟存储系统的工作流程,结合计算机组成原理完整的走一遍,一切步骤按照最复杂的情况进行。
CPU发出的虚拟地址,首先查找快表TLB,TLB不命中转而查找内存上的页表,检查页表上的标记位,看是否加载到了内存上,没有则产生缺页中断,将外存上的对应页加载到内存上,修改页表和快表之后,重新执行指令,查快表命中,直接访问内存上的对应位置。
典型题
如果在IO操作时进行了交换,会导致IO的数据丢失,从而影响进程的后序运行,所以不允许在IO操作时进行交换。
这里考察了一个细节,页表和段表也需要存储在内存中,内存减去页表和段表的空间才是留给用户的空间,而页表和段表的大小是不确定的,所以二者谁剩余的空间更多也是不确定的。
分段和分页都需要额外的数据结构段表页表来辅助,而分区却不需要,所以分区的代价最小。
从题干分析,页的大小为2的10次方B,所以页内偏移量占10位,同时,作为二级页表本身也是一页,所以二级页表最多能容纳2的9次方项,所以让二级页表项最多,就可以让一级页表页表项最少,总页数为2的16次方,所以需要的页表项数为2的7次方即128.
题目考查现学现卖的能力。10GB分配完相当于2.5M个簇,一个簇对应1位,那么2.5M个簇需要320KB的空间,即位图为320KB,再将这个位图存放在簇里,所以是80个簇。
这种地址的转换是这部分大题最喜欢考察的内容,其中涉及了进制的转换、查页表的过程、地址的转换,属于这部分很全面的题目。根据题目,一页是1KB,即10位的内部偏移,用户的编程空间是32个页,即逻辑地址需要5位的虚页号,而主存只有16KB,所以实际的物理块号需要4位。把握好这一点就可以进行后面地址的转换。
0AC5H对应的二进制位00010 1011000101,其虚拟页号为前五位,即2,转换为物理块号是四位二进制0100,所以转换后的地址为0100 10 1100 0101,即十六进制的12C5H。
同理1AC5H转换后虚页号为6,不在映射表中,所以会产生缺页中断。
3AC5H转换后页号为14,而用户程序只有10页长,超过了上限,所以会产生越界中断。
这种多级页表的计算属于比较抽象的题目,页面大小为4KB,所以很容易确定页内偏移为12位,多重页表也是页表,一个页表项为8B,所以一个页表最多存储2的9次方个页表项,而虚拟地址扣去页内偏移的12位,剩下的36位全部用于表示页表项的话,会产生2的36次方个页表项,所以需要4级的页表。
这种题目考察的是利用率来分析目前系统出现的问题。CPU利用率低而磁盘利用率高,说明磁盘忙于处理调页CPU受限于缺页从而利用率低,这种情况下就是出现了抖动现象。CPU利用率高而磁盘利用率低,说明CPU忙于计算而且基本没有出现缺页错误,此时是系统的正常状态,也是最好的状态。CPU利用率和磁盘利用率如果都低,说明没有充分利用CPU的资源,应该增加并发的进程数来提高CPU利用率。
这道题就属于这部分的大综合题了。首先分析题干,页面大小为4KB,说明页内偏移需要12位,虚拟地址为48位,所以虚页号为36位,实地址为32位所以物理块号为20位,页表项为8B,则一个页最多可以容纳2的9次方个页表项。
第一问考的是多级页表的划分,虚页号36位即最多有2的36次方个页,而一个页最多放2的9次方个页,所以至少要采用4级页表才能容纳所有页。页内偏移直接是12位。
第二问和第三问都是考察时间计算,这种题目只需要按照比例分配时间即可,没什么难度,稍微有点难度的是第三问的二级页表结合TLB,此时如果TLB不命中则查二级页表,如果TLB命中了直接就可以访问物理内存上的数据。计算如下:
第四问也是考察时间计算,但是考查角度换成了命中率,此时可以假设命中率,通过列方程的方法来求出最小命中率。计算如下:
第五问换成考段式分配,每段最大是4GB级2的32次方,虚拟地址为2的48次方,所以剩下16位可以对应到不同的段,即最多可以有2的16次方个段。4GB的段再分页,就是将第一问的题目换了换数据,4GB抛去页内偏移还剩下20位,会产生最多2的20次方个页表项,而一个页表最多放2的9次方个页表项,所以需要3级页表才能实现。