我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:六合特肖 > 访问局部性 >

内存管理

归档日期:06-10       文本归类:访问局部性      文章编辑:爱尚语录

  操作系统对有效的内存管理在多道程序设计中非常重要,不仅方便用户使用存储器、提高内存利用率,还可以通过虚拟技术从逻辑上扩充存储器。内存的划分和动态分配,就是内存管理的概念。

  (1)内存空间的分配与回收: 由操作系统完成主存储器空间的分配和管理,使程序员摆脱存储分配的麻烦,提高编程效率。 (2)地址转换: 在多道程序环境下,程序中的逻辑地址与内存中的物理地址不可能一致,因此存储管理必须提供地址变换功能,把逻辑地址转换成相应的物理地址。 (3)内存空间的扩充: 利用虚拟存储技术或自动覆盖技术,从逻辑上扩充内存。 (4)存储保护: 保证各道作业在各自的存储空间内运行,互不干扰。

  早期的计算机系统中,主存容量很小,虽然主存中仅存放一道用户程序,但是存储空间放不下用户进程的现象也经常发生,这一矛盾可以用覆盖技术来解决。

  覆盖的基本思想是:由于程序运行时并非任何时候都要访问程序及数据的各个部分(尤其是大程序),因此可以把用户空间分成一个固定区和若干个覆盖区。将经常活跃的部分放在固定区,其余部分按调用关系分段。首先将那些即将要访问的段放入覆盖区,其他段放在外存中,在需要调用前,系统再将其调入覆盖区,替换覆盖区中原有的段。

  覆盖技术的特点是打破了必须将一个进程的全部信息装入主存后才能运行的限制,但当同时运行程序的代码量大于主存时仍不能运行。

  交换(对换)的基本思想是,把处于等待状态(或在CPU调度原则下被剥夺运行权利) 的程序从内存移到辅存,把内存空间腾出来,这一过程又叫换出;把准备好竞争CPU运行的程序从辅存移到内存,这一过程又称为换入。第2章介绍的中级调度就是釆用交换技术。

  例如,有一个CPU釆用时间片轮转调度算法的多道程序环境。时间片到,内存管理器将刚刚执行过的进程换出,将另一进程换入到刚刚释放的内存空间中。同时,CPU调度器可以将时间片分配给其他已在内存中的进程。每个进程用完时间片都与另一进程交换。理想情况下,内存管理器的交换过程速度足够快,总有进程在内存中可以执行。

  (1)交换需要备份存储,通常是快速磁盘。它必须足够大,并且提供对这些内存映像的直接访问。 (2)为了有效使用CPU,需要每个进程的执行时间比交换时间长,而影响交换时间的主要是转移时间。转移时间与所交换的内存空间成正比。 (3)如果换出进程,必须确保该进程是完全处于空闲状态。 (4)交换空间通常作为磁盘的一整块,且独立于文件系统,因此使用就可能很快。 (5)交换通常在有许多进程运行且内存空间吃紧时开始启动,而系统负荷降低就暂停。 (6)普通的交换使用不多,但交换策略的某些变种在许多系统中(如UNIX系统)仍发挥作用。

  交换技术主要是在不同进程(或作业)之间进行,而覆盖则用于同一个程序或进程中。由于覆盖技术要求给出程序段之间的覆盖结构,使得其对用户和程序员不透明,所以对于主存无法存放用户程序的矛盾,现代操作系统是通过虚拟内存技术来解决的,覆盖技术则已成为历史;而交换技术在现代操作系统中仍具有较强的生命力。

  连续分配方式,是指为一个用户程序分配一个连续的内存空间。它主要包括单一连续分配、固定分区分配和动态分区分配。

  内存在此方式下分为系统区和用户区,系统区仅提供给操作系统使用,通常在低地址部分;用户区是为用户提供的、除系统区之外的内存空间。这种方式无需进行内存保护。

  这种方式的优点是简单、无外部碎片,可以釆用覆盖技术,不需要额外的技术支持。缺点是只能用于单用户、单任务的操作系统中,有内部碎片,存储器的利用率极低。

  固定分区分配是最简单的一种多道程序存储管理方式,它将用户内存空间划分为若干个固定大小的区域,每个分区只装入一道作业。当有空闲分区时,便可以再从外存的后备作业队列中,选择适当大小的作业装入该分区,如此循环。

  为便于内存分配,通常将分区按大小排队,并为之建立一张分区说明表,其中各表项包括每个分区的起始地址、大小及状态(是否已分配),如图所示。当有用户程序要装入时,便检索该表,以找到合适的分区给予分配并将其状态置为”已分配”;未找到合适分区则拒绝为该用户程序分配内存。存储空间的分配情况如图所示。

  固定分区是可用于多道程序设计最简单的存储分配,无外部碎片,但不能实现多进程共享一个主存区,所以存储空间利用率低。固定分区分配很少用于现在通用的操作系统中,但在某些用于控制多个相同对象的控制系统中仍发挥着一定的作用。

  动态分区分配又称为可变分区分配,是一种动态划分内存的分区方法。这种分区方法不预先将内存划分,而是在进程装入内存时,根据进程的大小动态地建立分区,并使分区的大小正好适合进程的需要。因此系统中分区的大小和数目是可变的。

  如图所示,系统有64MB内存空间,其中低8MB固定分配给操作系统,其余为用户可用内存。开始时装入前三个进程,在它们分别分配到所需空间后,内存只剩下4MB,进程4无法装入。在某个时刻,内存中没有一个就绪进程,CPU出现空闲,操作系统就换出进程2,换入进程4。由于进程4比进程2小,这样在主存中就产生了一个6MB的内存块。之后CPU又出现空闲,而主存无法容纳进程2,操作系统就换出进程1,换入进程2。

  动态分区在开始分配时是很好的,但是之后会导致内存中出现许多小的内存块。随着时间的推移,内存中会产生越来越多的碎片(图3-6中最后的4MB和中间的6MB,且随着进程的换入/换出,很可能会出现更多更小的内存块),内存的利用率随之下降。这些小的内存块称为外部碎片,指在所有分区外的存储空间会变成越来越多的碎片,这与固定分区中的内部碎片正好相对。克服外部碎片可以通过紧凑(Compaction)技术来解决,就是操作系统不时地对进程进行移动和整理。但是这需要动态重定位寄存器的支持,且相对费时。紧凑的过程实际上类似于Windows系统中的磁盘整理程序,只不过后者是对外存空间的紧凑。

  在进程装入或换入主存时,如果内存中有多个足够大的空闲块,操作系统必须确定分配哪个内存块给进程使用,这就是动态分区的分配策略,考虑以下几种算法:

  )算法:空闲分区以地址递增的次序链接。分配内存时顺序查找,找到大小能满足要求的第一个空闲分区。 (

  )算法:空闲分区按容量递增形成分区链,找到第一个能满足要求的空闲分区。 (

  )算法,空闲分区以容量递减的次序链接。找到第一个能满足要求的空闲分区,也就是挑选出最大的分区。 (

  )算法:又称循环首次适应算法,由首次适应算法演变而成。不同之处是分配内存时从上次查找结束的位置开始继续查找。

  在这几种方法中,首次适应算法不仅是最简单的,而且通常也是最好和最快的。在UNIX 系统的最初版本中,就是使用首次适应算法为进程分配内存空间,其中使用数组的数据结构 (而非链表)来实现。不过,首次适应算法会使得内存的低地址部分出现很多小的空闲分区,而每次分配查找时,都要经过这些分区,因此也增加了查找的开销。

  邻近适应算法试图解决这个问题,但实际上,它常常会导致在内存的末尾分配空间(因为在一遍扫描中,内存前面部分使用后再释放时,不会参与分配),分裂成小碎片。它通常比首次适应算法的结果要差。

  最佳适应算法虽然称为“最佳”,但是性能通常很差,因为每次最佳的分配会留下很小的难以利用的内存块,它会产生最多的外部碎片。

  最坏适应算法与最佳适应算法相反,选择最大的可用块,这看起来最不容易产生碎片,但是却把最大的连续内存划分开,会很快导致没有可用的大的内存块,因此性能也非常差。

  Kunth和Shore分别就前三种方法对内存空间的利用情况做了模拟实验,结果表明:

  首次适应算法可能比最佳适应法效果好,而它们两者一定比最大适应法效果好。另外注意,在算法实现时,分配操作中最佳适应法和最大适应法需要对可用块进行排序或遍历查找,而首次适应法和邻近适应法只需要简单查找;回收操作中,当回收的块与原来的空闲块相邻时(有三种相邻的情况,比较复杂),需要将这些块合并。在算法实现时,使用数组或链表进行管理。除了内存的利用率,这里的算法开销也是操作系统设计需要考虑的一个因素。

  以上三种内存分区管理方法有一共同特点,即用户进程(或作业)在主存中都是连续存放的。这里对它们进行比较和总结,见表。

  非连续分配允许一个程序分散地装入到不相邻的内存分区中,根据分区的大小是否固定分为分页存储管理方式和分段存储管理方式。

  分页存储管理方式中,又根据运行作业时是否要把作业的所有页面都装入内存才能运行分为基本分页存储管理方式和请求分页存储管理方式。下面介绍基本分页存储管理方式。

  固定分区会产生内部碎片,动态分区会产生外部碎片,这两种技术对内存的利用率都比较低。我们希望内存的使用能尽量避免碎片的产生,这就引入了

  分页的方法从形式上看,像分区相等的固定分区技术,分页管理不会产生外部碎片。但它又有本质的不同点:块的大小相对分区要小很多,而且进程也按照块进行划分,进程运行时按块申请主存可用空间并执行。这样,进程只会在为最后一个不完整的块申请一个主存块空间时,才产生主存碎片,所以尽管会产生内部碎片,但是这种碎片相对于进程来说也是很小的,每个进程平均只产生半个块大小的内部碎片(也称页内碎片)。

  ①页面和页面大小。进程中的块称为页(Page),内存中的块称为页框(Page Frame,或页帧)。外存也以同样的单位进行划分,直接称为块(Block)。进程在执行时需要申请主存空间,就是要为每个页面分配主存中的可用页框,这就产生了页和页框的一一对应。

  为方便地址转换,页面大小应是2的整数幂。同时页面大小应该适中,如果页面太小,会使进程的页面数过多,这样页表就过长,占用大量内存,而且也会增加硬件地址转换的开销,降低页面换入/换出的效率;页面过大又会使页内碎片增大,降低内存的利用率。所以页面的大小应该适中,考虑到耷间效率和时间效率的权衡。

  地址结构包含两部分:前一部分为页号P,后一部分为页内偏移量W。地址长度为32 位,其中0~11位为页内地址,即每页大小为4KB;12~31位为页号,地址空间最多允许有220页。

  ③页表。为了便于在内存中找到进程的每个页面所对应的物理块,系统为每个进程建立一张页表,记录页面在内存中对应的物理块号,页表一般存放在内存中。

  在配置了页表后,进程执行时,通过查找该表,即可找到每页在内存中的物理块号。可见,页表的作用是实现从页号到物理块号的地址映射,如图所示。

  地址变换机构的任务是将逻辑地址转换为内存中物理地址,地址变换是借助于页表实现的。图3-9给出了分页存储管理系统中的地址变换机构。

  在系统中通常设置一个页表寄存器(PTR),存放页表在内存的始址F和页表长度M。进程未执行时,页表的始址和长度存放在进程控制块中,当进程执行时,才将页表始址和长度存入页表寄存器。设页面大小为L,逻辑地址A到物理地址E的变换过程如下:

  由上面介绍的地址变换过程可知,若页表全部放在内存中,则存取一个数据或一条指令至少要访问两次内存:一次是访问页表,确定所存取的数据或指令的物理地址,第二次才根据该地址存取数据或指令。显然,这种方法比通常执行指令的速度慢了一半。

  为此,在地址变换机构中增设了一个具有并行查找能力的高速缓冲存储器——快表,又称联想寄存器(TLB),用来存放当前访问的若干页表项,以加速地址变换的过程。与此对应,主存中的页表也常称为慢表,配有快表的地址变换机构如图所示。

  (1)CPU给出逻辑地址后,由硬件进行地址转换并将页号送入高速缓存寄存器,并将此页号与快表中的所有页号进行比较。 (2)如果找到匹配的页号,说明所要访问的页表项在快表中,则直接从中取出该页对应的页框号,与页内偏移量拼接形成物理地址。这样,存取数据仅一次访存便可实现。 (3)如果没有找到,则需要访问主存中的页表,在读出页表项后,应同时将其存入快表,以便后面可能的再次访问。但若快表已满,则必须按照一定的算法对旧的页表项进行替换。

  注意:有些处理机设计为快表和慢表同时查找,如果在快表中查找成功则终止慢表的查找。

  一般快表的命中率可以达到90%以上,这样,分页带来的速度损失就降低到10%以下。快表的有效性是基于著名的局部性原理,这在后面的虚拟内存中将会具体讨论。

  第二个问题:由于引入了分页管理,进程在执行时不需要将所有页调入内存页框中,而只要将保存有映射关系的页表调入内存中即可。但是我们仍然需要考虑页表的大小。以32 位逻辑地址空间、页面大小4KB、页表项大小4B为例,若要实现进程对全部逻辑地址空间的映射,则每个进程需要220,约100万个页表项。也就是说,每个进程仅页表这一项就需要4MB主存空间,这显然是不切实际的。而即便不考虑对全部逻辑地址空间进行映射的情况,一个逻辑地址空间稍大的进程,其页表大小也可能是过大的。以一个40MB的进程为例,页表项共40KB,如果将所有页表项内容保存在内存中,那么需要10个内存页框来保存整个页表。整个进程大小约为1万个页面,而实际执行时只需要几十个页面进入内存页框就可以运行,但如果要求10个页面大小的页表必须全部进入内存,这相对实际执行时的几十个进程页面的大小来说,肯定是降低了内存利用率的;从另一方面来说,这10页的页表项也并不需要同时保存在内存中,因为大多数情况下,映射所需要的页表项都在页表的同一个页面中。

  将页表映射的思想进一步延伸,就可以得到二级分页:将页表的10页空间也进行地址映射,建立上一级页表,用于存储页表的映射关系。这里对页表的10个页面进行映射只需要10个页表项,所以上一级页表只需要1页就足够(可以存储210=1024个页表项)。在进程执行时,只需要将这1页的上一级页表调入内存即可,进程的页表和进程本身的页面,可以在后面的执行中再i周入内存。

  如图所示,这是Intel处理器80x86系列的硬件分页的地址转换过程。在32位系统中,全部32位逻辑地址空间可以分为220(4GB/4KB)个页面。这些页面可以再进一步建立顶级页表,需要210个顶级页表项进行索引,这正好是一页的大小,所以建立二级页表即可。

  举例,32位系统中进程分页的工作过程:假定内核已经给一个正在运行的进程分配的逻辑地址空间是0x20000000到0x2003FFFF,这个空间由64个页面组成。在进程运行时,我们不需要知道全部这些页的页框的物理地址,很可能其中很多页还不在主存中。这里我们只注意在进程运行到某一页时,硬件是如何计算得到这一页的页框的物理地址即可。现在进程需要读逻辑地址0x20021406中的字节内容,这个逻辑地址按如下进行处理:

  顶级页表字段的0x80用于选择顶级页表的第0x80表项,此表项指向和该进程的页相关的二级页表;二级页表字段0x21用于选择二级页表的第0x21表项,此表项指向包含所需页的页框;最后的页内偏移量字段0x406用于在目标页框中读取偏移量为0x406中的字节。

  这是32位系统下比较实际的一个例子。看似较为复杂的例子,有助于比较深入地理解,希望读者能自己动手计算一遍转换过程。

  建立多级页表的目的在于建立索引,这样不用浪费主存空间去存储无用的页表项,也不用盲目地顺序式查找页表项,而建立索引的要求是最高一级页表项不超过一页的大小。在 64位操作系统中,页表的划分则需要重新考虑,这是很多教材和辅导书中的常见题目,但是很多都给出了错误的分析,需要注意。

  我们假设仍然釆用4KB页面大小。偏移量字段12位,假设页表项大小为8B。这样,其上一级分页时,每个页框只能存储29(4KB/8B)个页表项,而不再是210个,所以上一级页表字段为9位。后面同理继续分页。64=12+9+9+9+9+9+7,所以需6级分页才能实现索引。很多书中仍然按4B页表项分析,虽然同样得出6级分页的结果,但显然是错误的。这里给出两个实际的64位操作系统的分页级别(注意:里面没有使用全部64位寻址,不过由于地址字节对齐的设计考虑,仍然使用8B大小的页表项),理解了表中的分级方式,相信对多级分页就非常清楚了。

  分页管理方式是从计算机的角度考虑设计的,以提高内存的利用率,提升计算机的性能, 且分页通过硬件机制实现,对用户完全透明;而分段管理方式的提出则是考虑了用户和程序员,以满足方便编程、信息保护和共享、动态增长及动态链接等多方面的需要。

  段式管理方式按照用户进程中的自然段划分逻辑空间。例如,用户进程由主程序、两个子程序、栈和一段数据组成,于是可以把这个用户进程划分为5个段,每段从0 开始编址,并分配一段连续的地址空间(段内要求连续,段间不要求连续,因此整个作业的地址空间是二维的)。其逻辑地址由段号S与段内偏移量W两部分组成。

  在图中,段号为16位,段内偏移量为16位,则一个作业最多可有216=65536个段,最大段长为64KB。

  在页式系统中,逻辑地址的页号和页内偏移量对用户是透明的,但在段式系统中,段号和段内偏移量必须由用户显示提供,在髙级程序设计语言中,这个工作由编译程序完成。

  每个进程都有一张逻辑空间与内存空间映射的段表,其中每一个段表项对应进程的一个段,段表项记录该段在内存中的起始地址和段的长度。段表的内容如图所示。

  在配置了段表后,执行中的进程可通过查找段表,找到每个段所对应的内存区。可见,段表用于实现从逻辑段到物理内存区的映射,如图所示。

  分段系统的地址变换过程如图3-15所示。为了实现进程从逻辑地址到物理地址的变换功能,在系统中设置了段表寄存器,用于存放段表始址F和段表长度M。其从逻辑地址A到物理地址E之间的地址变换过程如下:

  在分段系统中,段的共享是通过两个作业的段表中相应表项指向被共享的段的同一个物理副本来实现的。当一个作业正从共享段中读取数据时,必须防止另一个作业修改此共享段中的数据。不能修改的代码称为纯代码或可重入代码(它不属于临界资源),这样的代码和不能修改的数据是可以共享的,而可修改的代码和数据则不能共享。

  与分页管理类似,分段管理的保护方法主要有两种:一种是存取控制保护,另一种是地址越界保护。地址越界保护是利用段表寄存器中的段表长度与逻辑地址中的段号比较,若段号大于段表长度则产生越界中断;再利用段表项中的段长和逻辑地址中的段内位移进行比较,若段内位移大于段长,也会产生越界中断。

  页式存储管理能有效地提高内存利用率,而分段存储管理能反映程序的逻辑结构并有利于段的共享。如果将这两种存储管理方法结合起来,就形成了段页式存储管理方式。

  在段页式系统中,作业的地址空间首先被分成若干个逻辑段,每段都有自己的段号,然后再将每一段分成若干个大小固定的页。对内存空间的管理仍然和分页存储管理一样,将其分成若干个和页面大小相同的存储块,对内存的分配以存储块为单位,如图所示。

  在段页式系统中,作业的逻辑地址分为三部分:段号、页号和页内偏移量,如图所示。

  为了实现地址变换,系统为每个进程建立一张段表,而每个分段有一张页表。段表表项中至少包括段号、页表长度和页表起始地址,页表表项中至少包括页号和块号。此外,系统中还应有一个段表寄存器,指出作业的段表起始地址和段表长度。

  在进行地址变换时,首先通过段表查到页表起始地址,然后通过页表找到页帧号,最后形成物理地址。如图3-18所示,进行一次访问实际需要三次访问主存,这里同样可以使用快表以加快查找速度,其关键字由段号、页号组成,值是对应的页帧号和保护码。

  各种内存管理策略都是为了同时将多个进程保存在内存中以便允许多道程序设计。它们都具有以下两个共同的特征:

  ) 一次性 作业必须一次性全部装入内存后,方能开始运行。这会导致两种情况发生: 当作业很大,不能全部被装入内存时,将使该作业无法运行; 当大量作业要求运行时,由于内存不足以容纳所有作业,只能使少数作业先运行,导致多道程序度的下降。

  ) 驻留性 作业被装入内存后,就一直驻留在内存中,其任何部分都不会被换出,直至作业运行结束。运行中的进程,会因等待

  由以上分析可知,许多在程序运行中不用或暂时不用的程序(数据)占据了大量的内存空间,而一些需要运行的作业又无法装入运行,显然浪费了宝贵的内存资源。

  要真正理解虚拟内存技术的思想,首先必须了解计算机中著名的局部性原理。著名的 Bill Joy (SUN公司CEO)说过:”在研究所的时候,我经常开玩笑地说高速缓存是计算机科学中唯一重要的思想。事实上,髙速缓存技术确实极大地影响了计算机系统的设计。“快表、 页高速缓存以及虚拟内存技术从广义上讲,都是属于高速缓存技术。这个技术所依赖的原理就是局部性原理。局部性原理既适用于程序结构,也适用于数据结构(更远地讲,Dijkstra 著名的关于“goto语句有害”的论文也是出于对程序局部性原理的深刻认识和理解)。

  (1)时间局部性:如果程序中的某条指令一旦执行,不久以后该指令可能再次执行;如果某数据被访问过,不久以后该数据可能再次被访问。产生时间局部性的典型原因,是由于在程序中存在着大量的循环操作。 (2)空间局部性:一旦程序访问了某个存储单元,在不久之后,其附近的存储单元也将被访问,即程序在一段时间内所访问的地址,可能集中在一定的范围之内,这是因为指令通常是顺序存放、顺序执行的,数据也一般是以向量、数组、表等形式簇聚存储的。写代码片

  时间局部性是通过将近来使用的指令和数据保存到高速缓存存储器中,并使用高速缓存的层次结构实现。空间局部性通常是使用较大的高速缓存,并将预取机制集成到高速缓存控制逻辑中实现。虚拟内存技术实际上就是建立了 “内存一外存”的两级存储器的结构,利用局部性原理实现髙速缓存。

  基于局部性原理,在程序装入时,可以将程序的一部分装入内存,而将其余部分留在外存,就可以启动程序执行。在程序执行过程中,当所访问的信息不在内存时,由操作系统将所需要的部分调入内存,然后继续执行程序。另一方面,操作系统将内存中暂时不使用的内容换出到外存上,从而腾出空间存放将要调入内存的信息。这样,系统好像为用户提供了一个比实际内存大得多的存储器,称为虚拟存储器。

  之所以将其称为虚拟存储器,是因为这种存储器实际上并不存在,只是由于系统提供了部分装入、请求调入和置换功能后(对用户完全透明),给用户的感觉是好像存在一个比实际物理内存大得多的存储器。虚拟存储器的大小由计算机的地址结构决定,并非是内存和外存的简单相加。虚拟存储器有以下三个主要特征:

  虚拟内存中,允许将一个作业分多次调入内存。釆用连续分配方式时,会使相当一部分内存空间都处于暂时或“永久”的空闲状态,造成内存资源的严重浪费,而且也无法从逻辑上扩大内存容量。因此,虚拟内存的实需要建立在离散分配的内存管理方式的基础上。虚拟内存的实现有以下三种方式:

  请求分页系统建立在基本分页系统基础之上,为了支持虚拟存储器功能而增加了请求调页功能和页面置换功能。请求分页是目前最常用的一种实现虚拟存储器的方法。

  在请求分页系统中,只要求将当前需要的一部分页面装入内存,便可以启动作业运行。在作业执行过程中,当所要访问的页面不在内存时,再通过调页功能将其调入,同时还可以通过置换功能将暂时不用的页面换出到外存上,以便腾出内存空间。

  为了实现请求分页,系统必须提供一定的硬件支持。除了需要一定容量的内存及外存的计算机系统,还需要有页表机制、缺页中断机构和地址变换机构。

  请求分页系统的页表机制不同于基本分页系统,请求分页系统在一个作业运行之前不要求全部一次性调入内存,因此在作业的运行过程中,必然会出现要访问的页面不在内存的情况,如何发现和处理这种情况是请求分页系统必须解决的两个基本问题。为此,在请求页表项中增加了四个字段,如图所示。

  在请求分页系统中,每当所要访问的页面不在内存时,便产生一个缺页中断,请求操作系统将所缺的页调入内存。此时应将缺页的进程阻塞(调页完成唤醒),如果内存中有空闲块,则分配一个块,将要调入的页装入该块,并修改页表中相应页表项,若此时内存中没有空闲块,则要淘汰某页(若被淘汰页在内存期间被修改过,则要将其写回外存)。

  缺页中断作为中断同样要经历,诸如保护CPU环境、分析中断原因、转入缺页中断处理程序、恢复CPU环境等几个步骤。但与一般的中断相比,它有以下两个明显的区别:

  请求分页系统中的地址变换机构,是在分页系统地址变换机构的基础上,为实现虚拟内存,又增加了某些功能而形成的。

  进程运行时,若其访问的页面不在内存而需将其调入,但内存已无空闲空间时,就需要从内存中调出一页程序或数据,送入磁盘的对换区。

  选择调出页面的算法就称为页面置换算法。好的页面置换算法应有较低的页面更换频率,也就是说,应将以后不会再访问或者以后较长时间内不会再访问的页面先调出。

  最佳(Optimal, OPT)置换算法所选择的被淘汰页面将是以后永不使用的,或者是在最长时间内不再被访问的页面,这样可以保证获得最低的缺页率。但由于人们目前无法预知进程在内存下的若千页面中哪个是未来最长时间内不再被访问的,因而该算法无法实现。

  最佳置换算法可以用来评价其他算法。假定系统为某进程分配了三个物理块,并考虑有以下页面号引用串:

  进程运行时,先将7, 0, 1三个页面依次装入内存。进程要访问页面2时,产生缺页中断,根据最佳置换算法,选择第18次访问才需调入的页面7予以淘汰。然后,访问页面0时,因为已在内存中所以不必产生缺页中断。访问页面3时又会根据最佳置换算法将页面1淘汰……依此类推,如图3-26所示。从图中可以看出釆用最佳置换算法时的情况。

  优先淘汰最早进入内存的页面,亦即在内存中驻留时间最久的页面。该算法实现简单,只需把调入内存的页面根据先后次序链接成队列,设置一个指针总指向最早的页面。但该算法与进程实际运行时的规律不适应,因为在进程中,有的页面经常被访问。

  这里仍用上面的实例,釆用FIFO算法进行页面置换。进程访问页面2时,把最早进入内存的页面7换出。然后访问页面3时,再把2, 0, 1中最先进入内存的页换出。由图 3-27可以看出,利用FIFO算法时进行了 12次页面置换,比最佳置换算法正好多一倍。

  FIFO算法还会产生当所分配的物理块数增大而页故障数不减反增的异常现象,这是由 Belady于1969年发现,故称为Belady异常,如图3-28所示。只有FIFO算法可能出现Belady 异常,而LRU和OPT算法永远不会出现Belady异常。

  选择最近最长时间未访问过的页面予以淘汰,它认为过去一段时间内未访问过的页面,在最近的将来可能也不会被访问。该算法为每个页面设置一个访问字段,来记录页面自上次被访问以来所经历的时间,淘汰页面时选择现有页面中值最大的予以淘汰。

  再对上面的实例釆用LRU算法进行页面置换,如图3-29所示。进程第一次对页面2访问时,将最近最久未被访问的页面7置换出去。然后访问页面3时,将最近最久未使用的页面1换出。

  在图3-29中,前5次置换的情况与最佳置换算法相同,但两种算法并无必然联系。实际上,LRU算法根据各页以前的情况,是“向前看”的,而最佳置换算法则根据各页以后的使用情况,是“向后看”的。

  LRU性能较好,但需要寄存器和栈的硬件支持。LRU是堆栈类的算法。理论上可以证明,堆栈类算法不可能出现Belady异常。FIFO算法基于队列实现,不是堆栈类算法。

  LRU算法的性能接近于OPT,但是实现起来比较困难,且开销大;FIFO算法实现简单,但性能差。所以操作系统的设计者尝试了很多算法,试图用比较小的开销接近LRU的性能,这类算法都是CLOCK算法的变体。

  简单的CLOCK算法是给每一帧关联一个附加位,称为使用位。当某一页首次装入主存时,该帧的使用位设置为1;当该页随后再被访问到时,它的使用位也被置为1。对于页替换算法,用于替换的候选帧集合看做一个循环缓冲区,并且有一个指针与之相关联。当某一页被替换时,该指针被设置成指向缓冲区中的下一帧。当需要替换一页时,操作系统扫描缓冲区,以查找使用位被置为0的一帧。每当遇到一个使用位为1的帧时,操作系统就将该位重新置为0;如果在这个过程开始时,缓冲区中所有帧的使用位均为0,则选择遇到的第一个帧替换;如果所有帧的使用位均为1,则指针在缓冲区中完整地循环一周,把所有使用位都置为0,并且停留在最初的位置上,替换该帧中的页。由于该算法循环地检查各页面的情况,故称为CLOCK算法,又称为最近未用(Not Recently Used, NRU)算法。

  CLOCK算法的性能比较接近LRU,而通过增加使用的位数目,可以使得CLOCK算法更加高效。在使用位的基础上再增加一个修改位,则得到改进型的CLOCK置换算法。这样,每一帧都处于以下四种情况之一:

  (1)从指针的当前位置开始,扫描帧缓冲区。在这次扫描过程中,对使用位不做任何修改。选择遇到的第一个帧(u

  0, m=0)用于替换。 (2)如果第1)步失败,则重新扫描,查找(u=0, m=1)的帧。选择遇到的第一个这样的帧用于替换。在这个扫描过程中,对每个跳过的帧,把它的使用位设置成0。 (3)如果第2)步失败,指针将回到它的最初位置,并且集合中所有帧的使用位均为0。重复第1步,并且如果有必要,重复第2步。这样将可以找到供替换的帧。

  改进型的CLOCK算法优于简单CLOCK算法之处在于替换时首选没有变化的页。由于修改过的页在被替换之前必须写回,因而这样做会节省时间。

  对于分页式的虚拟内存,在准备执行时,不需要也不可能把一个进程的所有页都读取到主存,因此,操作系统必须决定读取多少页。也就是说,给特定的进程分配多大的主存空间,这需要考虑以下几点:

  (1)分配给一个进程的存储量越小,在任何时候驻留在主存中的进程数就越多,从而可以提高处理机的时间利用效率。 (2)如果一个进程在主存中的页数过少,尽管有局部性原理,页错误率仍然会相对较高。 (3)如桌页数过多,由于局部性原理,给特定的进程分配更多的主存空间对该进程的错误率没有明显的影响。

  (1)固定分配局部置换。它为每个进程分配一定数目的物理块,在整个运行期间都不改变。若进程在运行中发生缺页,则只能从该进程在内存中的页面中选出一页换出,然后再调入需要的页面。实现这种策略难以确定为每个进程应分配的物理块数目:太少会频繁出现缺页中断,太多又会使CPU和其他资源利用率下降。 (2)可变分配全局置换。这是最易于实现的物理块分配和置换策略,为系统中的每个进程分配一定数目的物理块,操作系统自身也保持一个空闲物理块队列。当某进程发生缺页时,系统从空闲物理块队列中取出一个物理块分配给该进程,并将欲调入的页装入其中。 (3)可变分配局部置换。它为每个进程分配一定数目的物理块,当某进程发生缺页时,只允许从该进程在内存的页面中选出一页换出,这样就不会影响其他进程的运行。如果进程在运行中频繁地缺页,系统再为该进程分配若干物理块,直至该进程缺页率趋于适当程度; 反之,若进程在运行中缺页率特别低,则可适当减少分配给该进程的物理块。

  为确定系统将进程运行时所缺的页面调入内存的时机,可釆取以下两种调页策略:

  )预调页策略。根据局部性原理,一次调入若干个相邻的页可能会比一次调入一页更高效。但如果调入的一批页面中大多数都未被访问,则又是低效的。所以就需要釆用以预测为基础的预调页策略,将预计在不久之后便会被访问的页面预先调入内存。但目前预调页的成功率仅约

  %。故这种策略主要用于进程的首次调入时,由程序员指出应该先调入哪些页。 (

  )请求调页策略。进程在运行中需要访问的页面不在内存而提出请求,由系统将所需页面调入内存。由这种策略调入的页一定会被访问,且这种策略比较易于实现,故在目前的虚拟存储器中大多釆用此策略。它的缺点在于每次只调入一页,调入调出页面数多时会花费过多的

  用于存放文件的文件区和用于存放对换页面的对换区。对换区通常是釆用连续分配方式,而文件区釆用离散分配方式,故对换区的磁盘I/O速度比文件区的更快。这样从何处调入页面有三种情况:

  (1)系统拥有足够的对换区空间:可以全部从对换区调入所需页面,以提髙调页速度。为此,在进程运行前,需将与该进程有关的文件从文件区复制到对换区。 (2)系统缺少足够的对换区空间:凡不会被修改的文件都直接从文件区调入;而当换出这些页面时,由于它们未被修改而不必再将它们换出。但对于那些可能被修改的部分,在将它们换出时须调到对换区,以后需要时再从对换区调入。 (3)UNIX方式:与进程有关的文件都放在文件区,故未运行过的页面,都应从文件区调入。曾经运行过但又被换出的页面,由于是被放在对换区,因此下次调入时应从对换区调入。进程请求的共享页面若被其他进程调入内存,则无需再从对换区调入

  在页面置换过程中的一种最糟糕的情形是,刚刚换出的页面马上又要换入主存,刚刚换入的页面马上就要换出主存,这种频繁的页面调度行为称为抖动,或颠簸。如果一个进程在换页上用的时间多于执行时间,那么这个进程就在颠簸。

  频繁的发生缺页中断(抖动),其主要原因是某个进程频繁访问的页面数目高于可用的物理页帧数目。虚拟内存技术可以在内存中保留更多的进程以提髙系统效率。在稳定状态,几乎主存的所有空间都被进程块占据,处理机和操作系统可以直接访问到尽可能多的进程。但如果管理不当,处理机的大部分时间都将用于交换块,即请求调入页面的操作,而不是执行进程的指令,这就会大大降低系统效率。

  工作集(或驻留集)是指在某段时间间隔内,进程要访问的页面集合。经常被使用的页面需要在工作集中,而长期不被使用的页面要从工作集中被丢弃。为了防止系统出现抖动现象,需要选择合适的工作集大小。

  工作集模型的原理是:让操作系统跟踪每个进程的工作集,并为进程分配大于其工作集的物理块。如果还有空闲物理块,则可以再调一个进程到内存以增加多道程序数。如果所有工作集之和增加以至于超过了可用物理块的总数,那么操作系统会暂停一个进程,将其页面调出并且将其物理块分配给其他进程,防止出现抖动现象。

  正确选择工作集的大小,对存储器的利用率和系统吞吐量的提嵩,都将产生重要影响。

  上一篇文章学习了中断的概念与意义,以及中断的应用-断点调试原理。点击链接复习上一篇文章:中断的概念与意义本片文章继续学习处理器相关的知识-内存管理。包括:内存管理单元MMU的作用,虚拟内存与物理内存之...博文来自:厚积薄发

  本宝宝从来没想过会去头条面试,但是莫名的收到了头条HR的电话,问我是否在找实习,什么时候有时间可以面试,既然已经约好面试的时间,那还是要好好准备一下,为了准备头条的面试,把网上关于头条的所有面...博文来自:xuejiao_lin的博客

  C++的动态内存管理是通过new和delete两个操作来完成的,即用new来申请空间,用delete来释放空间。在使用new和delete时,注意以下原则。(1)程序运行时,new操作和delete操...博文来自:Dablelv的博客专栏

  C++作为一门应用广泛的高级编程语言,但却没有像Java、C#等语言拥有垃圾回收(GarbageCollection)机制来自动地进行内存管理,这也是C++一直被诟病的一点。C++在发展的过程中,一直...博文来自:Dablelv的博客专栏

  Linux的虚拟内存管理有几个关键概念:每个进程有独立的虚拟地址空间,进程访问的虚拟地址空间并不是真正的物理地址虚拟地址可通过每个进程上页表与物理地址进行映射,获得真正的物理地址如果虚拟地址所对应的物...博文来自:喜欢恋着风

  介绍操作系统是如何来管理内存资源。层次化存储体结构计算机的存储体系寄存器(register)在CPU内部,非常快速,昂贵高速缓存(cache)非常快速,昂贵,容量小,易失性主存(RAM)中等速度,中等...博文来自:crazy_scott的博客

  收藏下来,慢慢看。[导语]内存管理是C++最令人切齿痛恨的问题,也是C++最有争议的问题,C++高手从中获得了更好的性能,更大的自由,C++菜鸟的收获则是一遍一遍的检查代码和对C++的痛恨,但内存...博文来自:caogenwangbaoqiang的博客

  一、问题提出:我们经常会使用malloc()以及free()函数进行堆区内存申请与释放。那么你是否会这样做:int*p=malloc(0);/*malloc分配了0个字节吗,如果是那么p指向谁呢,是N...博文来自:Apollon_krj的博客

  连续分配方式为一个用户程序分配一个连续的内存空间20世纪六、七十年代的OS中,分类:单一连续分配 固定分区分配 动态分区分配 动态重定位分区分配 其他(1)单一连续分配内存分为系统区和用户区两部分:系...博文来自:Marvin_Huoshan的博客

  摘要:本章首先以应用程序开发者的角度审视Linux的进程内存管理,在此基础上逐步深入到内核中讨论系统物理内存管理和内核内存的使用方法。力求从外到内、水到渠成地引导网友分析Linux的内存管理与使用。在...博文来自:CSDN_WHB的博客

  模拟内存管理设计与实现:模拟实现动态分区内存管理机制。设计和实现关于内存管理的内存布局初始化及内存申请分配、内存回收等基本功能操作函数,尝试对256MB的用户内存空间进行动态分区方式模拟管理。内存分配...博文来自:kawhi849

  在上一节,我们得知可用内存的大小后,我们就可以开发一个简单的管理算法去管理和分配可用用内存。...博文来自:tyler_download的专栏

  转自  一、Android内存基础物理内存与进程内存物理内存即移动设备上的RAM,当启动一个Andro...博文来自:飞翔的小鸟

  本文主要内容:1.基本概念:物理内存、虚拟内存;物理地址、虚拟地址、逻辑地址;页目录,页表2.Windows内存管理3.CPU段式内存管理4.CPU页式内存管理 一、基本概念1.两个内存概念物理内存:...博文来自:Like a lunatic

  面试题一:设置一个不能被继承的类思路:子类继承父类的时候,子类的构造函数会自动调用父类的构造函数;子类的析构函数会自动调用父类的析构函数。所以只要将父类的构造函数和析构函数设置成私有的即可。(一旦设置...博文来自:zhourong0511的博客

  多道程序设计技术是操作系统中最早引入的软件技术,引入它的目的是*充分利用内存,有利于数据共享*提高系统的实时响应速度*提高文件系统性能,减少内外存之间的信息传输量*充分利用CPU,提高CPU利用率下列...博文来自:水木今山的博客

  Spark作为一个以擅长内存计算为优势的计算引擎,内存管理方案是其非常重要的模块;Spark的内存可以大体归为两类:execution和storage,前者包括shuffles、joins、sorts...博文来自:我只是一个简单的Coder,为了兴趣和理想奋斗在生活的道路上

  需求系统的物理内存是有限的,而对内存的需求是变化的,程序的动态性越强,内存管理就越重要,选择合适的内存管理算法会带来明显的性能提升。比如nginx,它在每个连接accept后会malloc一块内存,作...博文来自:MyObject-C的专栏

  本文是任督二脉之内存管理课程第四节课的总结说明,由于水平有限,可能无法对宋老师所讲完全理解通透,如有错误,请及时指证。         发了前几天的总结后,有群里的朋友@jeff表示,我这样大篇幅的文...博文来自:每天进步一点点,月薪三千不是梦

  前言Linux利用x86的分段和分页机制将逻辑地址转换为物理地址。除了内核保留一部分空间存放代码和数据以外,剩余空间需要动态管理,给内核和进程使用。本讲讲述内存管理方法。本讲包含三个方面的内容:首先物...博文来自:weixin_37825861的博客

  本文以Linux内核4.9来做介绍。内存管理区(ZONE)结构体每个Node节点中的内存又划分为多个ZONE来进行管理,内核中一共定义有如下几种类型的ZONE。enumzone_type{#ifdef...博文来自:rikeyone的博客

  内部碎片的产生:因为所有的内存分配必须起始于可被4、8或16整除(视处理器体系结构而定)的地址或者因为MMU的分页机制的限制,决定内存分配算法仅能把预定大小的内存块分配给客户。假设当某个客户请求一个4...博文来自:Unique-You的博客

  授予成功创建个人博客专栏的用户。专栏中添加五篇以上博文即可点亮!撰写博客专栏浓缩技术精华,专栏达人就是你!

本文链接:http://shawntierney.com/fangwenjubuxing/494.html