第3章内存管理 计算机的存储系统主要包括内存储器和外存储器。内存储器(Memory)即俗称的内存或主存,是处理器能直接寻址的存储空间,由半导体器件制成,用来存放处理器执行时所需要的程序和数据,以及与硬盘等外存储器交换的数据,程序和数据只有在内存中才能被处理器直接访问,因此内存管理的优劣直接影响系统的性能。内存对数据的存取相比处理器处理数据的速度要慢得多,通过高速缓存可以部分缩小这种差距,但高效的内存管理仍然是操作系统设计必须考虑的关键问题。 外存储器也称辅助存储器,用来存放需要长期保存的数据,外存储器的管理属于文件系统的范畴。 内存储器一般分为两部分: 一部分是系统区,用来存放操作系统内核代码以及一些标准子程序、例行程序等,这些是操作系统长驻内存的部分,用户不能使用系统区; 另一部分称为用户区,分配给用户使用,用来存放用户的程序和数据。内存管理的主要工作就是对内存储器中的用户区进行管理。 3.1内存管理概述 3.1.1内存管理的功能 操作系统的内存管理部分应包含以下功能。 1. 内存的分配和回收 操作系统根据用户程序的请求,在内存中按照一定算法找到一块空闲区,将其分配给申请者; 当内存中的某个作业完成后,负责收回它所占用的全部或部分内存空间,使之变为空闲区以便再次分配。 2. 实现地址转换 现代操作系统均采用多道程序设计技术,在内存中往往同时存放多个作业的程序,各程序在内存中的位置用户是无法预知的。因此,在用户程序中使用逻辑地址,而CPU访问内存时则按物理地址进行。为了保证程序能够正确执行,内存管理必须进行地址转换工作,把逻辑地址转换成物理内存中与之对应的物理地址,这种地址转换工作也称为地址重定位。 3. 内存的共享和保护 共享内存可以提高内存空间的利用率,内存空间的共享有如下两种情况。 (1) 在多道程序系统中,若干作业同时装入内存,各自占用某些内存区域,共享同一个内存。 (2) 不同的作业可能有共同的程序段或数据段,把这些共同的程序段或数据段存放在一个内存区域中,各个作业执行时都可以访问该区域。 内存中不仅有系统程序,还有多个用户程序,为了防止各用户程序相互干扰和保护各用户区的信息不被破坏,系统必须负责隔离分配给各用户的内存区,保证各个用户程序或进程在各自规定的存储区域内操作,不破坏操作系统区的信息,并且互不干扰。 4. 内存扩充 由于物理内存的容量有限,有时候无法满足用户程序运行的需要,内存管理允许通过虚拟存储技术“扩充”内存容量。在计算机软硬件系统的支持下,可以把磁盘等辅助存储器作为内存的扩充部分使用,使用户程序在所需内存比实际物理内存容量大的情况下,也能在内存中运行。 3.1.2计算机存储系统的结构 按照计算机的体系结构,计算机存储系统可以划分为3个层次,分别是: 处理器寄存器和高速缓存、内存储器、外存储器,如图3.1 所示。越往上,存储介质的访问速度越快,价格也越高; 越往下,存储介质的存储空间越大。 图3.1计算机存储系统层次 1. 处理器寄存器和高速缓存 处理器寄存器主要包括通用寄存器、指令寄存器、地址寄存器和数据缓冲寄存器等一系列寄存器,用于存储处理器中与控制流和数据流相关的信息。寄存器访问速度最快,完全可以与CPU协调工作,但价格昂贵、容量小,一般以字(word)为单位。一个计算机系统一般包括几十个甚至上百个寄存器。 高速缓存(Cache)是为了解决处理器与内存之间速度不匹配问题而引入的。其存储容量比处理器寄存器大,访问速度比寄存器慢,但远比内存快。当处理器要读取数据时,首先访问高速缓存,如果所要访问的数据已经在高速缓存中,则直接从高速缓存中读取信息; 如果要访问的数据不在高速缓存中,则需要从内存中读取信息。随着硬件技术的发展,现在已经将高速缓存封装在处理器芯片中,所以常将高速缓存与处理器寄存器归到一个层次。 2. 内存储器 内存储器也称为内存或者主存,属于主机范畴。内存中存储处理器执行时所需要的代码和数据。内存的空间远大于高速缓存,但内存中的数据断电即消失,无法永久存储。一个计算机系统中所配备的内存容量是衡量计算机性能的一个重要指标,计算机最大内存容量受到计算机系统结构的限制。 3. 外存储器 外存储器是计算机系统中最大规模的存储器,用来存储各种数据和程序。外存储器容量巨大并能够永久存储信息,断电后数据不会丢失。外存储器的价格低但是访问速度慢。外存储器包括各种磁盘、磁带、光盘以及其他移动存储设备。磁盘中的硬盘是计算机系统中大量联机信息的保存者,硬盘常常作为内存的补充,用来实现虚拟存储系统。 例如,某台计算机的存储系统可以按层次配置: CPU中的寄存器 100B,存取周期10ns; 高速缓存16MB,存取周期 15ns; 主存储器8GB,存取周期60ns; 磁盘容量500GB,存取周期毫秒级。这台计算机足够胜任日常工作,其多层次的存储体系有很高的性价比。 3.1.3地址的表示与地址转换 用户的源程序通常用高级语言编写,通常需要经过以下几个步骤才能执行: 首先编译,由编译程序将用户源代码编译成若干目标模块; 然后链接,由链接程序将编译后的一组目标模块以及它们所需要的库函数链接在一起,形成一个完整的可装入模块; 最后装入,由装入程序将装入模块装入内存中,直到此时程序才能运行,如图3.2所示。 图3.2用户程序的处理过程 1. 物理地址空间 内存的存储单元以字节(每字节占8个二进制位)为单位编制,每个存储单元都有一个地址与其相对应,假定某计算机内存的容量为n,则该主存就有n字节的存储空间,其地址编号为0、1、2、…、n-1。 当程序运行时,它将被装入物理内存中的某段空间内,此时程序和数据的实际地址不可能同原来的逻辑地址一致,程序在物理内存中的实际存储位置称为物理地址,也叫绝对地址,物理地址的总体构成了用户程序实际运行的物理地址空间。不同程序的物理地址空间绝对不能冲突。 在以下章节中,如无特别说明,地址编址和地址长度的单位都是字节(Byte)。 2. 逻辑地址空间 经过编译、链接后得到的目标程序必须装入内存才能运行,由操作系统根据内存的使用情况自动为用户的目标程序分配内存空间,每个用户无法预知其目标程序存放在内存的具体位置。因此,在用户程序中不能使用内存的物理地址。 为方便起见,每个用户均认为自己的程序和数据存放在一组从0开始的连续的内存地址空间中,用户程序中所使用的地址称为逻辑地址,也叫相对地址,一个用户作业目标程序的逻辑地址集合称为该作业的逻辑地址空间。作业的逻辑地址空间可以是一维的,这时逻辑地址限制在从0开始顺序排列的地址空间内; 也可以是二维的,这时整个用户作业被分为若干段,每段有不同的段号,每段内的地址都从0开始。 3. 地址转换 只有把程序和数据的逻辑地址转换为物理地址,程序才能正确运行,该过程称为地址转换或地址重定位。地址重定位有静态重定位和动态重定位两种方式。 静态重定位: 在用户作业装入内存时由装入程序(装配程序)实现从逻辑地址到物理地址的转换,地址转换在作业执行前一次完成。 图3.3为静态重定位的例子,图中有3个待装入内存的目标模块,其逻辑地址从0开始,到(a+b+c-1)结束。在装入内存时,如果只能从内存地址2000开始容纳该作业,则在静态重定位装入方式下该程序装入内存时的物理地址为从2000开始,到(2000+a+b+c-1)结束。 图3.3静态重定位 静态重定位的优点是实现简单,从逻辑地址到物理地址的转换不需要专门的硬件便能完成; 缺点是必须为程序分配一段连续的存储空间,并且程序在执行过程中不能在内存中移动。 动态重定位: 在程序执行过程中,CPU在访问程序和数据之前才实现从逻辑地址到物理地址的转换,称为动态重定位。动态重定位必须借助于硬件地址转换机构来实现。硬件系统中设置了一个定位寄存器,当操作系统为某程序分配了一块内存区域后,装入程序直接把用户程序装入所分配的区域中,然后把该内存区域的起始地址置入定位寄存器中。在程序执行过程中随着每条指令或数据的访问,需要进行地址转换时,只需将逻辑地址与定位寄存器中的值相加就可得到物理地址。这种地址转换方式是在程序执行过程中动态进行的,所以称为动态重定位。 采用动态重定位时,由于装入内存的用户程序仍保持逻辑地址,所以可实现程序在内存中的移动。在程序执行过程中,若把程序移动到另一块内存区域后,只要改变定位寄存器中的内容,该程序仍可正确执行。但采用静态重定位时,程序在执行过程中是不能移动的。 动态重定位的优点是内存的使用更加灵活,容易实现内存的动态扩充和共享; 缺点是实现过程中需要附加硬件支持,内存的管理也更加复杂。 当使用C++、Java、Deiphi等高级语言编程时,用户已不必关心逻辑地址空间与实际物理地址空间的关系,它们之间的地址转换由编译系统和操作系统共同完成。 3.1.4覆盖与交换技术 当用户程序所需要的内存超过实际物理内存大小时,除了后面将要介绍的虚拟存储技术外,操作系统可以采取覆盖(Overlay)或交换(Swapping)技术来扩充内存,覆盖技术主要用于早期的操作系统中,而交换技术在现代操作系统中仍有使用。 1. 覆盖技术 一个程序通常由若干功能上独立的程序段组成,在运行时,并不是所有的程序段都同时进入内存运行。可以按照程序自身的逻辑结构,让不同时运行的程序段先后共享同一块内存区域,这就是覆盖技术。 覆盖技术先将程序必需的部分代码和数据调入内存,其余部分先放在外存中,当要访问的程序或数据不在内存时,由操作系统负责将其从外存中调入,这就解决了在较小的内存空间中运行较大程序的问题。 覆盖技术首先将大的用户程序划分为一个个相对独立的程序单位,将程序运行时不需要同时装入内存的程序单位组成一个个覆盖段,每个覆盖段的长度不能超过已有内存空间的大小。各个覆盖段分先后顺序进入所分配的内存空间中,后进入内存的覆盖段将先进入的覆盖段覆盖。 例如,某程序由A、B、C、D、E、F六个程序段组成,它们之间的调用关系如图3.4左图所示。其中,程序段A只调用B和C,程序段B只调用F,而程序段C只调用D和E。由于B和C之间没有相互调用,所以它们可以共享同一覆盖区。覆盖区的大小以能装入所有共享的程序段为准。本例中,与B、C对应的覆盖区的大小为50KB。类似地,D、E、F也可以共享一大小为40KB的覆盖区,如图3.4右图所示。 图3.4覆盖技术 虽然该进程所需要的总的内存空间为20KB+50KB+30KB+30KB+20KB+40KB=190KB,但是在采用了覆盖技术之后,只需要110KB的内存就够了。 在程序执行的全过程都要使用的部分不能对其进行覆盖,真正能够被覆盖的是程序分阶段使用的部分。目前,这一技术仅应用于小型系统中系统程序的内存管理,例如,MSDOS的启动过程中多次使用了覆盖技术。 覆盖技术的缺点有如下两点。 (1) 覆盖技术对用户不透明,用户在编程时必须划分程序模块和确定程序模块之间的覆盖关系,增加了编程复杂度。 (2) 从外存装入覆盖文件,是以时间的延长来换取空间的节省。 2. 交换技术 为了释放部分内存空间,由操作系统根据需要,将某些暂时不运行的进程或程序段从内存移到外存的交换区中; 当内存空间富余时再给被移出的进程或程序段重新分配内存,让其进入内存,这就是交换技术,又称为“对换”或“滚进/滚出(RollIn/RollOut)”技术。 交换技术能够提高系统的性能和多道度,从内存到外存的交换为换出,从外存到内存的交换为换入。通过不断地换入、换出,使得用户看来好像内存扩大了,从而实现了内存扩充的目的。 根据每次交换的单位不同,交换技术在实现中有如下两种情况。 (1) 以整个进程为单位的交换: 每次换入或换出的是一个进程,此策略多用于早期的分时系统中,以实现在小型机上的分时运行。 (2) 以进程的一部分为单位的交换: 在现代操作系统中,借助于页式或段式内存管理,先将进程的内存空间划分为若干页面或段,然后以页面或段为基本单位进行交换。在操作系统中,常见的有页面置换(在页式存储管理中介绍)和段置换(在段式存储管理中介绍),这也是虚拟存储技术的基础。 需要指出的是,习惯上说的交换技术是指以整个进程为单位的交换。 在分时系统如UNIX系统中,当活跃用户进程数目超过系统的进程阈值时,存储管理器会将一些进程交换到外存。最早采用交换技术的是美国麻省理工学院(MIT)的兼容分时系统(CTSS),在当时内存空间非常有限的情况下,为了增加系统的多道度,将内存中处于输入输出操作的作业或运行时间片用完的作业换出内存,同时再调入一个作业进入内存运行,从而在有限的内存空间中实现了多道程序同时运行。 3. 覆盖技术和交换技术的比较 (1) 与覆盖技术相比,交换技术不要求用户给出程序段之间的逻辑覆盖结构。 (2) 交换发生在进程或作业之间,而覆盖发生在同一进程或作业内。 (3) 覆盖只能覆盖那些与覆盖段无关的程序段。 3.2分区内存管理 3.2.1单一连续内存管理 1. 基本思想 单一连续内存管理适用于单用户单任务操作系统,是最简单的内存管理方式。单一连续内存管理将内存空间分为系统区和用户区,系统区存放操作系统常驻内存的代码和数据,用户区全部分配给一个用户作业使用。在这种方式下,任一时刻主存储器最多只有一道程序,各个作业只能按次序一个一个地装入主存储器运行。 通常,系统区位于内存底部的低地址部分,用户区位于内存顶部的高地址部分。 2. 内存的分配与回收 由于内存中的用户区只能装入一个程序运行,因此该程序被装入内存时,就从内存用户区的基地址开始,连续存放。在运行过程中,该程序独占内存,直到退出,操作系统收回内存再分配给下一个程序使用。 3. 地址转换与内存保护 单一连续内存管理多采用静态重定位来进行地址转换。操作系统设置一个界限寄存器用来设置内存中系统区和用户区的地址界限,通过装入程序把目标模块装入从界限地址开始的区域,如图3.5所示。 图3.5采用静态重定位的单一连续内存管理 内存保护由装入程序来执行,装入时由装入程序检查物理地址是否超过界限地址,超过则可以装入; 否则产生地址错误,不能装入。这样,用户的程序总是被装入合法的用户区域内,而不会进入系统区。 采用静态重定位的优点是实现简单,无须硬件地址变换机构支持; 缺点是作业只能分配到一个连续存储区域中,程序执行期间不能在内存中移动,无法实现程序共享。 单一连续内存管理也可以采用动态重定位方式来转换地址。系统设置一个定位寄存器,它既用来指出内存中的系统区和用户区的地址界限,又作为用户区的基地址; 装入程序把程序装入从界限地址开始的区域,但不同时进行地址转换; 而是在程序执行过程中动态地将逻辑地址与定位寄存器中的界限地址相加就可得到绝对地址,如图3.6所示。 图3.6采用动态重定位的单一连续内存管理 单一连续内存管理非常简单,系统开销小,其主要缺点如下。 (1) 内存利用率低。用户程序所需空间一般均小于内存用户区空间,剩余的内存空间也不能被其他用户使用。 (2) CPU利用率低。当运行中的程序进行I/O操作时,CPU会处于空闲等待状态。 (3) 外部设备利用率低。用户控制所有资源,有些资源在运行期间可能并不使用,也不能为其他用户使用。 (4) 不能进行内存扩充。当内存容量小于某一程序所需要的内存空间时,该程序便无法运行。 20世纪70年代诞生的小型计算机和微型计算机系统,如IBM7094的 FORTRAN监督系统、IBM1130磁盘监督系统、MIT兼容分时系统CISS以及微型计算机cromemco的CDOS系统、Digital Research和Dyhabyte的CP/M系统、DJS0520的0520FDOS等均采用单一连续内存管理。 3.2.2固定分区内存管理 1. 基本思想 图3.7固定分区内存管理示意 固定分区内存管理是预先把可分配的内存空间分割成若干大小固定的连续区域,每个区域的大小可以相同,也可以不同,每个区域称为一个分区。每个分区可以装入且只能装入一个用户作业。这样,分区后的内存中就可以装入多道程序,从而支持多道程序并发设计,如图3.7所示。 2. 分区的划分 分区划分的方法有分区大小相等和分区大小不等两种方式。 1) 分区大小相等 所有分区的大小都相等,这种方式适合计算机工业控制系统。因为在计算机工业控制系统中,所有控制对象都具有相同的条件,完成相同的控制任务和控制指标。该方式的缺点是: 因为分区大小都一样,所以较小的进程装在分区里会浪费内存,而较大的进程则无法装入内存运行。 2) 分区大小不等 把可分配的内存空间分割为大小不等的多个分区,大的分区可以分配给大的进程,小的分区可以分配给小的进程。与分区大小相等的分配方式比较,分区大小不等的分配方式使内存的分配更加灵活,内存的浪费更少。 3. 固定分区的内存分配 为了说明各分区的分配和使用情况,系统设置了一张内存分配表,如表3.1所示。 表3.1固定分区内存管理的内存分配表 分区号起 始 地 址长度占 用 标 志 15KB5KB0 2 10KB 10KB 0 3 20KB 10KB Job1 4 30KB 20KB 0 5 50KB 20KB Job2 6 70KB 30KB 0 内存分配表指出了各分区的起始地址和分区的长度,占用标志位指示该分区是否被使用,当占用的标志位为“0”时,表示该分区尚未被占用。只能将那些占用标志为“0”的分区分配给用户作业使用,当某一分区被分配给一个作业后,就在占用标志栏填上占用该分区的作业名,如表3.1中,第3分区和第5分区分别被作业Job1和Job2占用,而其余分区为空闲。 固定分区方式的内存回收很简单,只需将内存分配表中相应分区的占用标志位置成“0”即可,表示该分区现在是空闲区,可以装入新的作业。 4. 地址转换与内存保护 静态重定位: 装入程序在进行地址转换时检查其绝对地址是否在指定的分区中,若是,则可把程序装入; 否则不能装入。 动态重定位: 如图3.8所示,计算机系统设置了一对地址寄存器——上限/下限寄存器,当一个进程占有CPU执行时,操作系统就从内存分配表中取出相应的地址放进上限/下限寄存器; 硬件的地址转换机构根据下限寄存器中保存的基地址B1与逻辑地址L相加就得到绝对地址; 硬件的地址转换机构同时把绝对地址与上限/下限寄存器中保存的地址进行比较,就可以实现内存保护。 图3.8固定分区内存管理的地址转换和内存保护 5. 固定分区分配的优点和缺点 固定分区的划分在操作系统初始化时完成。在系统启动时,系统管理员根据系统要运行的作业的需要来划分分区。当用户作业进入分区时,按照用户作业的大小从分区表中选择适当的空闲分区。与单一连续分配方式比较,固定分区分配方式使得系统资源的利用率和吞吐量有一定的提高。 固定分区分配的缺点如下。 (1) 内存空间的利用率不高: 较小的进程如果装入较大的分区,易造成内存“碎片”。例如表3.1中Job1和Job2两个作业可能实际只需要8KB和16KB的内存,但它们却占用了10KB和20KB的两个分区,分别浪费了2KB和4KB的内存空间。 (2) 由于每个分区大小固定,这样就限制了可容纳的程序的大小。在装入一个程序时,若找不到足够大的分区,则无法装入。 早期的 IBM 操作系统OS/MFT(Multiprogramming with a Fixed Number of Tasks)就使用了固定分区内存管理。 3.2.3可变分区内存管理 1. 基本思想 可变分区是指事先不确定分区的大小,也不确定分区的数目。当某一用户作业申请内存时,检查内存中是否有一块能满足该作业的连续存储空间,若有则把这一空间划出一块区域给该用户使用,这种方式称为可变分区内存管理。由于分区的大小是按作业的实际需要量来定的,且分区的个数是随机的,因此可变分区内存分配可以克服固定分区方式中的内存浪费现象。 可变分区克服了固定分区内存利用率低的问题,更适合多道程序环境。 2. 可变分区内存的分配和回收 采用可变分区方式的内存分配示例如图3.9所示。随着作业的装入、撤离,内存空间被分成许多个分区,有的分区被占用,有的分区空闲。当一个新的作业要求装入时,必须找一个足够大的空闲区,能够容纳该作业,如果找到的空闲区大于作业需要量,则作业装入后又把原来的空闲区分成两部分,一部分被作业占用; 另一部分又成为一个较小的空闲区。当一个作业运行结束撤离时,它归还的区域如果与其他空闲区相邻,则可合成一个较大的空闲区,以利于大作业的装入。 图3.9可变分区内存的分配示例 为了完成内存的分配和回收,需要构建对分区信息进行描述的数据结构,一张是已分配区的情况表,另一张是未分配区的情况表,如表3.2所示。 表3.2可变分区内存管理的内存分配表 (a) 已分配区情况表 分区号起 始 地 址长度标志 14KB6KBJob1 246KB6KBJob2 (b) 未分配区情况表 分区号起 始 地 址长度标志 110KB36KB未分配 252KB76KB未分配 表3.2的两张表的内容是根据图3.9最左边的情况生成的。当要装入长度为30KB的作业3时,首先从未分配区情况表中寻找一个能够容纳它的空闲区,长度为36KB的空闲区就适合此作业; 然后将该区分成两部分,一部分30KB,用来装入作业3,成为已分配区,另一部分为6KB,仍是空闲区。这时,应从已分配区情况表中找一个空栏目登记作业3所占用的区的起始地址和长度,同时修改未分配区情况表中空闲区的长度和起始地址。当作业撤离时则已分配区情况表中的相应状态应改成“空”,而将收回的分区登记到未分配情况表中,若有相邻空闲区则将其连成一片后登记。 操作系统也可以通过链表方式来管理空闲分区,将所有的空闲分区通过前向和后向指针串在一起组成双向空闲分区链表,如图3.10所示。双向空闲分区链表管理比空闲分区表格管理较为复杂,但其优点是链表自身不占用存储单元。为了方便检索双向空闲分区链表,每个空闲分区的尾部还设置分区状态和分区大小标志,系统查找双向空闲分区链表时可直接得知分区的大小和分配情况,省去了查询空闲分区表的时间。 图3.10双向空闲分区链表 不论是双向空闲分区链表管理还是空闲分区表格管理,链表和表格中的空闲区都可按一定规则排列。例如,按空闲区从大到小排列或从小到大排列,以方便空闲区的查找和回收。 3. 可变分区的内存分配算法 1) 最先适应分配算法 每次分配时,总是从开始顺序查找未分配区情况表或双向空闲分区链表,将找到的第一个能满足长度要求的空闲分区分配给用户作业使用。从该空闲分区中分割一部分给作业,另一部分仍作为空闲分区; 如果空闲分区全部查找完也不能满足该作业的要求,则系统不能为该作业分配内存。 最先适应分配算法首先利用内存中的低地址空闲分区,保留了高地址空闲分区,以便能容纳大的用户作业。该算法的缺点是系统每次都是从未分配区情况表或双向空闲分区链表的开始查找空闲分区,低地址段的空闲分区被不断分割,形成了许多小的、难以利用的空闲分区,这样的小空闲分区称为“碎片”; 同时每次都从开始查找,查找过程花费的时间较长。 2) 循环首次适应分配算法 循环首次适应分配算法是对最先适应分配算法的改进。为作业分配内存时,系统不是从空闲分区表的开始处查找,而是从上次为作业分配分区后的位置开始查找,找到第一个满足作业大小的空闲分区,分配并分割该空闲分区。 循环首次适应分配算法克服了最先适应法的缺点,使得空闲分区的分布更加均匀,查找空闲分区所需要的时间更短。但是,小分区或“碎片”问题仍然没有解决。 3) 最优适应分配算法 最优适应分配算法是从空闲分区中挑选一个能满足作业要求的最小分区,这样可以避免分割一个更大的区域,使大作业比较容易被装入。采用这种分配算法时可把空闲分区按长度以递增顺序排列,查找时总是从最小的一个分区开始,直到找到一个满足要求的分区为止。按这种方法,在收回一个分区时也必须对双向空闲分区链表重新排列。 最优适应分配算法找出的分区一般都无法正好满足作业的内存要求,分割后剩下的空闲区很小,无法再次使用,成为“碎片”。另外,这些小的空闲分区占据了空闲分区表格的开始部分,增加了查找空闲分区表格或双向空闲分区链表的时间开销。 4) 最坏适应分配算法 最坏适应分配算法的思想是: 从空闲分区中挑选一个最大的分区给作业使用,这样可以使分割后剩下的空闲分区仍然比较大,仍然能满足之后作业被装入的要求,也减少了内存中“碎片”的大小和个数。采用这种分配算法时可把空闲分区按长度以递减顺序排列,查找时只要看第一个分区能否满足作业要求,若能满足,则分配给该作业使用。这样使最坏适应分配算法的查找效率很高,这种算法对中、小作业是有利的。 最坏适应分配算法的缺点是: 随着系统的运行,大空闲区会不断减少,这样,大的作业可能无法装入内存。 5) 快速适应分配算法 快速适应分配算法把不同长度的空闲分区归类,为每种长度的空闲分区设立单独的双向空闲分区链表。这样,系统中就存在多个双向空闲分区链表。例如,有一个N项的双向空闲分区链表,该链表第一项指向长度为2KB的双向空闲分区链表表头的指针; 第二项指向长度为4KB的双向空闲分区链表表头的指针; 第三项指向长度为8KB的双向空闲分区链表表头的指针; 以此类推。为作业分配内存时,根据作业大小查找双向空闲分区链表,找到能够容纳该作业的最小双向空闲分区链表的起始指针,然后从相应的双向空闲分区链表中取第一个空闲分区分配给该作业即可。 快速适应分配算法的优点是: 查找空闲分区迅速,找到的空闲分区是能够容纳它的最小空闲分区,这样能够保留大的空闲分区。快速适应分配算法的缺点是: 回收分区较困难,算法复杂,系统开销大。 为了更好地理解这5种内存分配算法,下面作简单的对比分析。从搜索空闲分区的速度及内存利用率来看,最先适应分配算法、循环首次适应分配算法和最优适应分配算法比最坏适应分配算法性能好。如果空闲分区按从小到大排列,则最先适应分配算法等于最优适应分配算法; 反之,如果空闲分区按从大到小排列,则最先适应分配算法等于最坏适应分配算法。空闲分区按从小到大排列时,最先适应分配算法能尽可能使用低地址区,从而,在高地址空间有较多较大的空闲分区来容纳大的作业。循环首次适应分配算法会使存储器空间得到均衡使用。最优适应分配算法的内存利用率最好,因为,它把刚好或最接近申请要求的空闲分区分给作业; 但是它可能会导致空闲分区分割下来的部分很小。 4. 地址转换与内存保护 可变分区内存管理是采用动态重定位方式来装入作业的,其地址转换由硬件机构完成。硬件机构设置了两个专门的寄存器: 基址寄存器和限长寄存器。基址寄存器存放分配给作业使用的分区起始地址,限长寄存器存放该分区内存空间的长度。 当用户作业占有CPU运行时,操作系统把分配给该作业的分区起始地址和长度送入基址寄存器和限长寄存器,执行作业时由硬件机构根据基址寄存器进行地址转换得到绝对地址。地址转换如图3.11所示。 图3.11可变分区内存管理的地址转换和内存保护 当逻辑地址小于限长值时,由逻辑地址加基址寄存器的基址就可得到绝对地址; 当逻辑地址大于限长值时,表示作业欲访问的内存地址超出了所分得的内存区域,禁止访问该地址,起到了内存保护的目的。 在多道程序系统中,只需要一对基址寄存器和限长寄存器就足够了。因为当作业在执行过程中出现等待时,操作系统把基址寄存器和限长寄存器的内容随同该作业的其他信息(如PSW)和通用寄存器的内容等一起保存起来。当作业被选中执行时,把选中作业的基址和限长值再送入基址寄存器和限长寄存器。世界上最早的巨型机 CDC6600 采用的便是这一方案。 5. 紧凑技术 当系统运行一段时间后,内存被多次分配和回收,会产生许多不连续的空闲分区。有可能出现这样的现象: 内存中每一块空闲分区都不能满足某一作业的内存请求,而所有空闲分区的总和却能满足该作业。这时可采用紧凑技术把内存中的作业改变存储区域,使分散的空闲分区能够汇聚成一个大的空闲分区,从而有利于大作业的装入。紧凑技术的示例如图3.12所示。 图3.12紧凑技术的示例 紧凑技术可以汇聚内存中的空闲分区,但也增加了系统的开销,而且不是任何时候都能对一道程序进行移动的。例如,当外围设备正在与内存进行信息交换时,会按照已经确定的内存物理地址完成信息传输,所以此时不能移动。 3.3页式存储管理 前面内容介绍了各种分区式的内存管理方式,都具有一个共同的特点——连续性。每道程序都要占用内存中一块连续的存储区域,当系统运行一段时间后,会在内存中产生许多“碎片”。虽然紧凑技术能够将内存中的“碎片”再利用,但是紧凑技术的系统开销非常大。 为了解决这一问题,出现了非连续的内存分配方式,也叫离散分配方式。其基本出发点是打破程序装入的整体性和存储分配的连续性,将用户进程的逻辑地址空间划分成多个子部分,以子部分为单位装入物理内存,这些子部分可以分布在若干非连续的内存块上,实现了离散储存,以充分利用内存。 内存的非连续分配方式主要包括页式存储管理和段式存储管理两种方式,下面先介绍页式存储管理。 3.3.1页式存储管理的基本原理 页: 将用户进程的逻辑地址空间划分为大小相等的区,每个区称为一页或一个页面,并对各页从0开始编号,如第0页、第1页等。 物理块: 将物理内存划分成与页大小相等的区,每个区称为一个物理块(block),或称为块、页框,也同样对它们加以编号,如0号块、1号块等。物理块的尺寸大小通常会取2的n次幂。物理块的大小由计算机硬件系统决定,页的大小由物理块的大小决定。如Intel 80386系列处理器系统和Motorola 68030处理器系统的块的大小为4096B,IBM AS/400处理器系统的块的大小为512B。 内存分配的基本单位是页,当装入一个用户程序时,按页为单位,每页装入一个物理块中,一个用户进程装入内存中时各个物理块之间不需要连续。 图3.13页式存储的逻辑地址 进程的最后一页经常装不满一块,所以会在最后一块内形成不可利用的碎片,称为“页内碎片”。而其他页在装入内存时,都能填满所在的物理块。 逻辑地址形式: 进程的逻辑地址可以用页号和页内偏移表示,页的大小与物理块的大小相等。逻辑地址格式如图3.13所示。 例如,32位操作系统的逻辑地址是32位,采用页式存储管理,如果每页大小为4096B,那么页内偏移要占用其逻辑地址的低12位,从0位开始到11位结束。逻辑地址剩余的高20位用来表示页号,从12位开始到31位结束,这样最多允许220 (1MB)个页面。页面的编号从0开始,分别为0,1,2,3,…,220-1。 如果进程的逻辑地址是A,页面大小是L,则页号P和页内偏移d为 P=INT[A/L] d=[A]MOD L 其中,INT表示求整数; MOD表示求余数。 例如,某计算机系统每页大小为1KB(1024),计算逻辑地址2345(十进制)的页号和页内偏移。 解: L=1024,A=2345 P=INT[2345/1024]=2 D=[2345]MOD 1024=297 这就表示逻辑地址2345处于2号页面,页内偏移为297。 还可以通过计算地址位得到页号和页内偏移量: 2345所对应的二进制数为100100101101,页号的大小为1024,即页内偏移占用低10位地址: 0100101101,相当于十进制的297,即页内偏移量为297; 页号占用剩余22位高地址段,即页号为10,相当于十进制的2。 所以,逻辑地址2345对应于2号页面,页内偏移为297。 需要注意的是: 采用页式存储管理时,逻辑地址仍然是连续的。因此,用户在编程时不必考虑如何去分页,分页的工作由操作系统完成。 3.3.2页式存储管理的内存分配与回收 页式存储管理在进行内存分配时,以物理块为单位进行分配,一个作业有多少页,在装入内存时就必须给它分配多少个物理块。但是,和分区式内存管理不同的是分配给作业的物理块可以是不连续的。 在进行内存分配时,操作系统为进入内存的每个用户作业建立一张页表,页表用来指出逻辑地址中的页号与内存中物理块号的对应关系。 同时,在页式存储管理系统中还存在一张作业表,作业表中的每个登记项登记了每个作业的页表起始地址和长度。页表和作业表的一般格式如图3.14所示。 图3.14页表和作业表的一般格式 某进程的页表如图3.15所示,页面大小为1KB,则逻辑地址2345在第2号页面,页内偏移为297。 图3.15进程的页表 查找页表,得到该页在内存中的块号为4,块号乘以块长为4096,该逻辑地址在内存中的物理地址为4096加上块内偏移,页内偏移等于块内偏移,为297。所以,物理地址为4096加297,即4393。 页表的表项中除了有页号和块号外,还有存取控制字段,用于实现对内存物理块的保护。页表的长度由用户进程的长度决定,每个在内存中的用户进程都会建立一张页表。如果进程不处于运行状态,页表的起始地址和长度存放在进程的PCB中。只有某一进程被调度运行时,系统才会从运行进程的PCB中将页表起始地址和长度装入页表寄存器。因此,一个处理器只需要一个页表寄存器。 3.3.3页式存储管理的地址转换 在页式存储管理中,进程的逻辑地址到物理地址的转换需要硬件来完成,该硬件为地址转换机构。 当处理器给出某个需要访问的逻辑地址时,地址转换机构自动地从逻辑地址的低地址部分得到页内偏移,从高地址部分得到页号。将页号与页表寄存器中的页表长度进行比较,如果页号大于页表长度,表示该页在页表中没有相应项,本次所访问的地址已经超越进程的地址空间,会产生地址越界中断; 否则,从页表寄存器得到页表在内存中的起始地址,然后用页号作为索引查找页表,得到该页的页表项在页表中的位置,从而可以查到该页在内存中的物理块号。最后,将页内偏移装入物理地址寄存器的低位字段中,将物理块号装入物理地址寄存器的高位字段中,此时物理地址寄存器中的内容就是地址转换机构给出的物理地址,如图3.16所示。 图3.16页式存储管理的地址转换机构 由地址转换的过程可见,处理器每运行一条指令总是先根据指令的逻辑地址,通过访问内存中的页表才能得到物理地址,根据物理地址再去访问内存才能得到需要的指令,即处理器需要两次访问内存。同样地,处理器要访问一个数据也需要两次访问内存。 3.3.4快表 为了提高存取速度,计算机系统中通常都设置一个专用的高速缓冲存储器,用来存放页表的一部分,这种高速缓冲存储器称为相联存储器(Associative Memory),存放在相联存储器中的页表称为快表。相联存储器的访问速度比内存快,但造价高,故一般都是小容量的,如8~16个单元。由于高速缓冲存储器由半导体存储器实现,其工作周期与处理器的工作周期接近,速度上能够很好地匹配处理器,因此访问快表的速度远远快于访问内存中页表的速度。 根据程序执行的局部性特点,即在一定时间内总是反复访问某些页,若把这些页登记在快表中,无疑将大大加快指令或数据的访问速度,快表的格式如下。 页号块号 …… 页号块号 快表里登记了已在相联存储器中的页及所对应的内存物理块号。 借助于快表,物理地址形成的过程是: 按逻辑地址中的页号查快表,若该页已登记在快表中,则由块号和块内偏移形成绝对地址; 若快表中查不到页号,则只能再查内存中的页表来形成绝对地址,同时将该页登记到快表中。当快表填满后,要在快表中登记新页时,需在快表中按一定策略淘汰一个旧的登记项,最简单的策略是“先进先出”,即总是淘汰最先登记的那一页。 采用快表可以使地址转换时间极大地下降,例如,假定访问内存的时间为200ns,访问快表的时间为40ns,相联存储器为16个单元时查快表的命中率可达90%,于是按逻辑地址进行存取的平均时间为 (200+40)×90%+(200+200+40)×10%=260ns 平均时间比两次访问内存的时间200×2=40ns下降了35%。 整个系统只有一个相联存储器,只有占用CPU的进程才能占有相联存储器。在多道程序中,当某道程序让出处理器时,应同时让出相联存储器。由于快表是动态变化的,因此让出相联存储器时应把快表保护好以便再执行时使用。当一道程序占用处理器时,除设置页表寄存器外还应将它的快表存入相联存储器中。 3.3.5页的共享和保护 页式存储管理有利于实现多个作业共享程序和数据。在多道程序系统中,编译程序、编辑程序、解释程序、公共子程序、公用数据等都是可共享的,这些共享的信息在内存中只需要保留一个副本。 在实现共享时,必须区分数据的共享和程序的共享。 实现数据共享时,不同的作业对共享数据页可以使用不同的页号,只要让各自页表中的有关表目指向共享数据物理块即可。 实现程序共享时,由于页式存储的逻辑地址空间是连续的,因此程序运行前它们的页号应该是确定的。 现假定有一个共享的编辑程序,其中含有转移指令,转移指令中的转移地址必须指出页号和页内偏移,如果是转向本页,则页号应与本页的页号相同。如果有两个作业共享这个编辑程序,假定一个作业定义它的页号为3,另一个作业定义它的页号为5,然而在内存中只有一个编辑程序,于是转移地址中的页号不能按作业的要求随机地改成3或5,因此对共享的程序必须规定一个统一的页号。当共享程序的作业数增多时,要规定一个统一的页号是比较困难的。 实现信息共享必须解决共享信息的保护问题。常用的办法是在页表中增加一些标志位,用来指出该页的信息,包括读写、只读、只可执行、不可访问等,在指令执行时进行核对。例如,要想向只读块写入信息则指令停止,产生错误中断。 3.3.6多级页表 随着计算机技术的发展,具备32位、64位逻辑地址空间的计算机系统已经很普遍,这样的计算机系统可以支持 232~264B容量的逻辑地址空间,当采用页式存储管理时,其页表所需的存储空间也是相当大的。以 Windows 2000/XP 为例,其运行的Intel x86 CPU具有32位地址,若规定每页大小4KB(212),则4GB(232)的逻辑地址空间共有1M(220)个页,共需1M条页表项。若每个页表项占用4B,则共需占用 4MB的内存空间,每页中可以存放1K个页表项,1M条页表项共需要1K个页面,这1K个页面要占用1K个内存物理块,这些物理块可以离散地分布于内存中。如此存放页表的存储开销太大,而且在进行页表查找时,时间开销也非常大。为此,把页表也进行分页,提出了多级页表的概念。 为了能够快速查找页表页在内存中的物理块号,为这些页表页再设计一个地址索引表,即页目录表。页目录表的表项中包含每个页表页所在的内存物理块号和相关信息。这样,系统将页表分为两级: 一级为页目录表,二级为页表页。页表页中的每个表项记录了每个页的页号和对应的物理块号,如图3.17所示。 图3.17二级页表结构 二级页表的逻辑地址被划分为页目录、页表页、页内偏移三部分。 首先,由页目录表寄存器(相当于页表寄存器)提供当前运行进程的页目录表(一级页表)在内存中的起始地址; 其次,由页目录表(一级页表)在内存中的起始地址加上页目录号(即需要查找的页表某页在页目录中的编号), 得到页表某页的物理块号; 再次,通过页表某页的物理块号得到该页表页(二级页表中的一页),由页表页号(某页在页表页中的编号)查询该页表页(二级页表中的一页)项,得到对应的物理块号; 最后,将该物理块号加上页内偏移,最终得到物理地址。 二级页表的地址转换过程如图3.18所示。 图3.18二级页表的地址转换过程 二级页表的地址转换获取内存信息需要三次访问内存: 第一次访问的是页目录表,第二次访问的是页表页,第三次访问的是通过物理地址获取的内存信息。为了节约时间,系统也可以采用快表获取内存信息。 当逻辑地址的位数更多时,系统会采用三级、四级,甚至更多级的页表。级别更多,灵活性越大,但是管理也更复杂。 例如,SUN公司的Solaris操作系统基于SPACE的处理器,采用了三级页表,如图3.19所示。32位逻辑地址分为四部分: 高8位部分作为第一级页表,之后的6位作为第二级页表,再向后6位作为第三级页表,最后12位作为页内地址,页面大小为4KB。 图3.19SUN公司的Solaris的三级页表结构 在地址转换之前,操作系统会给每个新进程分配一个上下文号,进程保留自己的上下文号直到结束。系统硬件支持高达4096个上下文号。地址转换过程是将上下文号与逻辑地址一起输入地址变换机构。 首先用上下文号作为上下文表的索引得到进程的第一级页表起始地址; 然后用逻辑地址中的高8位作为索引查找一级页表,得到第二级页表的起始地址; 再用逻辑地址中的高8位之后的6位作为索引查找第二级页表,得到第三级页表的起始地址; 接着再用逻辑地址中的再后面6位作为索引得到第三级页表中的物理块号; 最后将逻辑地址中的低12位作为块内偏移,得到物理地址。 3.4段式存储管理 3.4.1段式存储管理的基本原理 1. 逻辑地址空间分段 前面所讨论的内存管理方法都是假设用户程序从“0”开始编址,逻辑地址空间都是一维的。事实上,如图3.20所示,一个程序往往由一个程序段、若干子程序数组段和工作区段组成,每个段都从“0”开始编址,段内地址是连续的。因此,可以按照程序的逻辑段结构,将一个程序按段为单位来分配内存,一段占用一块连续的内存地址空间,段与段之间不需要连续。 图3.20程序的分段结构 2. 段地址结构 段式存储管理是以段为单位进行内存分配,逻辑地址空间是一个二维空间,分为段号和段内偏移两部分,如下所示。 段号段 内 偏 移 在页式存储管理中,逻辑地址如何分页用户是不可见的,连续的逻辑地址空间根据内存物理块的大小自动分页; 而在段式存储管理中,则是由用户来决定逻辑地址如何分段的。用户在编程时,每个段的最大长度受到地址结构的限制,每个程序中允许的最多段数也可能受到限制。例如,PDP11/45的段址结构为: 段号占3位,段内地址占13位; 也就是一个作业最多可分为8段,每段的长度最大8KB。 分段存储管理与分页存储管理有许多相似之处。在分段存储管理中操作系统为每个作业创建一张段表,每个段在段表中占有一项。段表中有段号、段长、段在内存的起始地址和存取控制字段等信息。同时,段式存储管理系统还包括一张作业表,将这些作业的段表进行登记,每个作业在作业表中有一个登记项。段表和作业表的一般格式如图3.21所示。 图3.21段表和作业表的一般格式 在段式存储管理中,对内存的分配类似于可变分区内存分配方式,因此其内存分配算法可以参照可变分区内存分配算法来设计,如最先适应法、最优适应法或最坏适应法等,此处不再赘述。 3.4.2段式存储管理的地址转换和内存保护 段地址转换借助于段表完成。段表寄存器用来存放当前占用处理器的作业的段表起始地址和长度,查询段表得到每段在内存的起始地址,将段的起始地址加上段内偏移则得到物理地址,段式存储管理的地址转换和内存保护流程如图3.22所示。 图3.22段式存储管理的地址转换和内存保护 段地址转换过程如下: (1) 将CPU给出的逻辑地址由地址转换机构分为段号和段内地址(即段内偏移); (2) 查询段表寄存器得到段表在内存的起始地址; (3) 将段号带入查询段表,得到该段在内存的起始地址和段长; (4) 将段内地址与段长比较,如果段内地址大于段长,则发出越界中断; 否则合法。段在内存的起始地址与段内地址相加,就得到该逻辑地址对应的内存物理地址。 同样地,借助于联想寄存器,在快表中保存最近使用过的段表项,可以更快地实现地址转换。 比较段表寄存器中的段表长度与逻辑地址中的段号,若段号超过段表长度则产生越界中断; 再比较段表项中的段长与逻辑地址中的段内偏移,检查是否产生越界中断。 对段的越权保护可通过在段表中增加相应的存取控制权限字段来实现。权限字段显示对段的读写是否允许,用它来检查对该段内地址的访问操作是否合法。只有当每次操作都在合法的权限范围内,才能正常完成访问操作,否则出错。 3.4.3段的共享 在段式存储管理中,所谓段的共享,事实上就是共享分区,为此计算机系统要提供多对基址寄存器和限长寄存器。这样,几个作业所共享的例行程序就可放在一个公共的分区中,只要让各作业的共享部分有相同的基址和限长值即可。 由于段号仅用于段之间的相互访问,段内程序的执行和访问只使用段内地址,因此不会出现页共享时出现的问题,对数据段和代码段的共享都不要求段号相同。当然对共享区的信息必须进行保护,如规定只能读出不能写入,欲想往该区域写入信息时将遭到拒绝并产生中断。 3.4.4分段和分页的比较 段是信息的逻辑单位,由源程序的逻辑结构决定,用户可见; 段长可根据用户需要来规定; 段起始地址可以从任何地址开始。在分段方式中,源程序(段号、段内偏移)经连接装配后仍保持二维结构。 页是信息的物理单位,与源程序的逻辑结构无关,用户不可见; 页长由系统确定; 页面只能以页大小的整倍数地址开始。在分页方式中,源程序(页号、页内偏移)经连接装配后变成了一维结构。 3.4.5段页式存储管理 页式存储基于存储器的物理结构,存储利用率高,便于管理,但难以实现存储共享、保护和动态扩充; 段式存储基于应用程序的结构,有利于模块化程序设计,便于段的扩充、动态链接、共享和保护,但往往会形成段之间的碎片,浪费存储空间。可以把两者结合起来,在分段式存储管理的基础上实现分页式存储管理,这就是段页式存储管理,是目前应用最多的一种存储管理方式。 下面介绍段页式存储管理的基本原理。 (1) 程序根据自身的逻辑结构划分成若干段,这是段页式存储管理的段式特征。 (2) 内存的物理地址空间划分成大小相等的物理块,这是段页式存储管理的页式特征。 (3) 将每段的线性地址空间划分成与物理块大小相等的页面,于是形成了段页式存储管理。 段号(s)段内页号(p)页内位移(d) (4) 逻辑地址分3个部分: 段号、段内页号和页内位移,其形式如上。 对于用户来说,虚拟地址应该由段号s和段内位移d′组成,用户看不到如何分页。而是由操作系统自动把d′解释成两部分: 段内页号p和页内位移d,也就是说,d′=p×块长+d。 (5) 段页式存储管理的数据结构包括段表和页表。 段表中包括段号、该段页表的起始地址、页表长度等信息,页表中包括页号、对应的物理块号等信息。段表、页表和内存的关系如图3.23所示。 图3.23段表、页表和内存的关系 (6) 动态地址转换。 段页式存储管理的动态地址转换机构由段表、页表和快表构成,其动态地址转换过程如下。 操作系统把正在运行作业的段表起始地址装入段表寄存器中,操作系统从逻辑地址中取出段号和段内页号,用段号和页号作为索引去查询快表,如果找到,则立即可以得到该页所对应的内存物理块号,将该物理块号与页内位移拼接,即得到所需要的物理地址。若查找快表失败,则需要用段号作为索引查询内存中的段表,得到页表长度和页表的起始地址。再以页号作为索引查询页表,得到该页所对应的物理块号,同时将段表中的相应段信息和页表中的相应信息写入快表,并将物理块号与页内位移拼接,从而得到物理地址。 图 3.24是段页式存储管理地址转换和内存保护示意图。 图 3.24段页式存储管理地址转换和内存保护 3.5虚拟存储技术 3.5.1虚拟存储技术的提出 由于受到计算机体系结构和成本的限制,计算机的内存容量总是有限的。在传统的存储管理中,如果一个作业要运行,必须将该作业的全部信息装入内存,并在整个作业运行结束后,才能释放内存。如果一个作业的信息大于内存容量,则无法装入内存,也无法运行; 如果系统有大量的作业申请进入内存,则系统只能接纳相当有限的作业,系统的多道度和性能都难以得到提高。 但绝大部分的作业在执行时实际上不是同时使用这些信息的,作业的某部分信息,如异常处理,可能从来不会使用; 也可能运行完一次后,再也不会使用。既然作业的全部信息是分阶段需要,则可以分阶段将作业信息调入内存,而不需要一次将作业的全部信息调入内存。于是,提出了这样的问题: 能否将作业不执行的部分暂时存放在外存,当进程需要时,再将其从外存调入内存?将外存作为内存的补充,从逻辑上扩充内存,这就是虚拟存储技术。 3.5.2程序的局部性原理 1968年,Denning发现了程序的局部性原理: 即在一段时间内,整个程序的执行仅限于程序中的某一部分。相应地,执行所访问的存储空间也局限于某个内存区域。局部性原理表现在时间局部性和空间局部性两个方面。 时间局部性是指如果程序中的某条指令一旦被执行,则不久之后该指令可能再次被执行; 如果某数据被访问,则不久之后该数据可能再次被访问。例如,很多程序中存在大量的循环、临时变量和子程序调用等。 空间局部性是指一旦程序访问了某个存储单元,则不久之后其附近的存储单元也将被访问。例如,程序中对数组、链表或堆栈进行操作。 程序的局部性原理说明: 程序的一次性装入内存与全部驻留内存都是不必要的,只装入一部分的假设是合理的,只要操作系统调度得当,不仅程序可以正确运行,而且可以在内存中装入更多程序,充分利用处理器和内存空间。 3.5.3虚拟存储技术的基本思想 虚拟存储技术的思想是: 将外存作为内存的扩充,作业运行不需要将作业的全部信息放入内存,将暂时不运行的作业信息存放在外存,通过内存与外存之间的对换,使系统逐步将作业信息放入内存,最终达到能够运行整个作业,从逻辑上扩充内存的目的。 虚拟存储器定义: 虚拟存储器是指具有请求调入功能和置换功能,能够从逻辑上对内存空间进行扩展,允许用户的逻辑地址空间大于物理内存地址空间的存储器系统。虚拟存储器的组织形式如图3.25所示。 图3.25虚拟存储器的组织形式 虚拟存储器的容量由计算机的地址结构和辅助存储器的容量决定,与实际的主存储器的容量无关。如果计算机系统的地址为32位,则可寻址的范围为0~4GB; 如果计算机系统的地址为20位,则可寻址的范围为0~1MB。计算机系统的可寻址范围为虚拟存储器的最大容量。虚拟存储器的实现对用户来说是感觉不到的,他们总以为有足够的内存空间可容纳他们的作业。 虚拟存储技术的实现基础是内存的分页或分段管理,采用的是进程的分页或分段在内存与外存之间对换。 虚拟存储技术允许进程的逻辑地址空间比物理内存空间大,即小空间能够运行大程序,打破了程序运行受内存空间的约束,使操作系统不但能够接纳更大的作业,而且能够接纳更多的作业,提高了系统的多道度和性能。 1962年,英国Atlas计算机系统中最早引入了虚拟存储技术。自1970年开始,IBM和MIT陆续将虚拟存储技术用在了自己的操作系统上,并从理论上阐述了分页虚拟存储技术在商业计算机中应用的可行性。到了1990年之后,绝大多数操作系统都支持虚拟存储技术,如各种版本的UNIX系统和Windows系统都采用了虚拟存储技术。 3.6请求页式虚拟存储管理 3.6.1请求页式虚拟存储管理的基本原理 请求页式虚拟存储管理是在页式存储管理的基础上增加了请求调页和页面置换功能,其基本原理如下。 (1) 物理的内存空间被划分为等长的物理块,并对块编号。同时,用户程序也进行分页,这些与页式存储管理相同。 (2) 在用户程序开始执行前,不将该程序的所有页都一次性装入内存,而是先放在外存。当程序被调度投入运行时,系统先将少数页装入内存,随着程序运行,如果所访问的页在内存中,则对其管理与分页存储管理情况相同。 (3) 若发现所要访问的数据或指令不在内存中,则会产生缺页中断,到外存寻找包含所需数据或指令的页,并将其装入内存的空闲块中。 (4) 在装入一页的过程中,若发现内存无空闲块或分配给该进程的物理块已用完,则需要通过页面置换功能从已在内存的页中挑选一个将其淘汰,释放所占用的物理块后将新的页面装入该块,进程继续执行。 (5) 被淘汰的页面如果刚才被修改过,则还需要将其回写到外存,以保留其最新内容。 从上面的基本原理可以看出,请求分页虚拟存储管理与页式存储管理在许多地方相似,区别是增加了请求调页和页面置换等功能,因此需要解决如下问题。 (1) 需要提供一个全新的页表机制来记录任一页是在内存或在外存的位置、是否被修改过等信息。 (2) 在请求分页虚拟存储管理方式下,内存中允许装入多个进程,每个进程占用一部分物理块,问题在于: 为每个进程分配多少个物理块才合适?采用何种分配方式才合理? (3) 进程执行过程中发现所要访问的数据或指令不在内存时,便会产生缺页中断,到外存寻找该页,此时缺页中断如何处理? (4) 一个页面或者是一开始就装入内存,或者是在执行中被动态地装入内存,如何进行地址重定位? (5) 在动态装入一个页面时,若发现内存当前无空闲块或分配给该进程的物理块已经用完,则需要从已在内存的页面中选出一个将其淘汰。问题在于: 在什么范围内选择要淘汰的页面?淘汰哪个页面?这就需要合适的页面置换算法。 这些问题,将在随后的内容中逐个解决。 IBM/370系统的VS/1、VS/2和VM/370,Honeywell 6180的MOLTICS以及UNIVAC系列70/64的VMS等都采用请求分页虚拟存储系统。 3.6.2请求页式虚拟存储管理的硬件支持 请求分页虚拟存储的硬件支持包括请求分页的页表机制、缺页中断机构和地址转换机构。 1. 请求分页的页表机制 在虚拟存储管理中,页表除了要完成从逻辑地址到物理地址的转换外,还需要提供页面置换的相关信息。因此,页表中除了有页号和物理块号等信息外,还增加了页的状态位、外存地址、修改位、访问字段等信息,如图3.26所示。 图3.26页式虚拟存储管理的页表 状态位: 用于标志一页是否已装入内存。如果该页已在内存,则该页所对应的状态位置“1”; 否则置“0”。 外存地址: 页在外存中的地址。当需要将某页调入内存时,需要查询页表中的外存地址项得到该页在外存的地址,在外存找到该页。 修改位: 页在内存中是否被修改过的标志,用来确定如果该页被换出内存时,是否需要再回写入外存。如果该页在内存里没有被修改过,那么该页中的内容和在外存中的内容是一致的,则被换出内存时不需要再写入外存,节约了写入外存的时间; 如果该页在内存中已经被修改过了,被换出内存时需要再写入外存。 访问字段: 标志该页在内存时是否被访问过,用于进行页面置换时考虑是否将该页换出内存。如果该页被访问过,在进行页面置换时,系统会考虑该页可能以后会被再次访问而不将其换出。 2. 缺页中断机构 在进程执行过程中,当发现所访问的页不在内存时,缺页中断机构便产生一个缺页(Page Fault)中断信号,操作系统接到此信号后,就运行缺页中断处理程序,将所需要的页调入内存。缺页中断与一般中断类似,都需要经历保护CPU环境、分析中断原因、转入中断程序处理、中断处理后恢复CPU环境等步骤。但缺页中断与一般中断也有不同。 (1) CPU检测中断的时间不同。对一般的中断信号,CPU是在一条指令执行完后检测其是否存在,检测时间以一个指令周期为间隔。而对缺页中断信号,CPU在一条指令执行期间,只要有中断信息就可检测,不需要等待一个指令周期。因此,CPU检测缺页中断更及时。 (2) CPU可以多次处理。如果在一个指令周期中多次检测到缺页中断,CPU都会及时处理。 缺页中断的处理过程如图3.27所示。 图3.27缺页中断的处理流程 操作系统缺页中断的处理流程是: 先查看内存是否有空闲块,若有则按该页在外存中的地址将该页找出并装入内存,在页表中填上它占用的块号且修改标志位; 若内存已没有空闲块,则必须先淘汰已在内存中的某一页,再将所需的页装入,对页表和内存分配表做相应的修改。淘汰某页时,要查看该页的修改位来判断该页是否修改过,若该页在执行过程中没有被修改过,则不必重新写回存储器中,而已修改过的页调出时必须再将该页写回外存中。 另外,需要注意的是: 如果要调出的页正在与外围设备交换信息,那么该页暂时不能调出,这时要么另选一页调出,要么等待该页与外围设备信息交换结束后再调出。 3. 地址转换机构 请求分页虚拟存储技术是在程序执行过程中逐步将程序页面调入内存的,所以从逻辑地址到物理地址的转换是在程序运行过程中完成的,是动态重定位装入,地址转换机构如图3.28所示。 图3.28请求分页虚拟存储的地址转换机构 当进程被调度时,操作系统将进程PCB中的页表起始地址和长度装入页表寄存器中。 CPU从逻辑地址中取得页号,根据页号查询快表,如果快表中有该页的内存块号,则将内存块号与页内偏移一起作为该页在内存的物理地址; 如果快表中没有该页的内存块号,则CPU从页表寄存器得到页表在内存中的起始地址,查询页表,得到该页的内存物理块号,将该块号与页内偏移一起作为内存中的物理地址,同时将该页的页号和内存块号写入快表,以备下次查询时使用。如果查询页表没有得到该页的内存块号,即表示该页不在内存,产生一个缺页中断信号,请求操作系统将该页调入内存。 在调入一页的过程中,如果进程空间没有空闲的物理块,则系统需要调出一页后再将该新页调入内存。同时系统修改页表,从页表中去除调出的页面,加上调入的页面。当这些工作完成后,处理器返回用户进程,继续执行被中断的指令。 请求分页虚拟存储管理采用请求页面调入方式,其实现需要硬件支持,增加了机器成本和系统开销。这些开销主要包括: 用于地址变换和各种数据结构的存储开销、执行地址变换指令的时间开销、内存与外存之间对换页面的I/O开销等。 3.6.3页面分配策略与页面调度算法 请求分页虚拟存储管理支持多个进程同时装入内存,操作系统为各个进程分别分配部分物理块,并将各自的部分页调入内存,在实施中涉及以下3个策略。 (1) 页面分配策略: 分配策略决定系统应该给一个进程分配多少物理块,进程才能被执行。 (2) 页面调入策略: 页面调入策略决定如何将进程所需要的页面调入内存。 (3) 页面置换策略: 页面置换策略决定内存中的哪些页面被换出内存。 1. 页面分配策略 页面分配负责为多个进程分配相应的物理块,分配时需要综合考虑系统的并发性、吞吐量和缺页中断率等因素,通常分为固定分配和可变分配两种不同的方式。 1) 固定分配方式 固定分配方式是指为每个进程分配固定数量的物理块,其数量在进程创建时由进程的类型(交互性、批处理或应用性)或根据用户的要求确定,在进程的整个执行期间都不再改变。具体的分配方式包括按进程平均分配法、进程按比例分配法和进程优先权分配法等。 (1) 进程平均分配法。 将内存中所有可分配的物理块平均分配给进入系统的各个进程。如果有m个内存物理块,n个进程,则每个进程分得的内存物理块数为m/n取整数(如果有小数,则小数部分不计)。 该分配方法实现简单,但没有考虑各个进程大小不一的因素,常常会造成内存的浪费。例如,现有150个空闲内存物理块,并发进程有13个,则每个进程分得的内存物理块数为11,还剩余7个物理块。但这时若有一个进程,其长度为9个页面,则它浪费了2个物理块; 若有另一个进程,其长度为30个页面,则很可能会经常发生缺页中断。 该分配方式的另一个特点是: 分配给每个进程的物理块数会随着内存中进程数的多少而变化。假如此时并发进程增加到16个,则每个进程分得的内存物理块数减少到9个。 (2) 进程按比例分配法。 进程按比例分配法的思想是: 根据进程的大小,进程按比例分配内存物理块数。如果系统中有m个内存物理块,n个并发进程,每个进程的页面数为Si,则系统中每个进程能够分得的内存物理块数bi为(bi取整)为 bi=(mSi)/∑ni=1Si 例如,如果内存能够提供62个内存物理块,并发进程有P1(10个页面)和P2(127个页面),则进程P1和P2分配到的物理块分别为 b1=(62×10)/(10+127)≈4 b2=(62×127)/(10+127)≈57 (3) 进程优先权分配法。 高优先级的、时间要求紧迫的进程,操作系统给其分配较多的内存物理块,使其能够快速完成。在实际应用中,将按比例分配法和进程优先级结合起来考虑,系统把内存中可以分配的物理块分为两部分,一部分按照比例分配给各并发进程,另一部分根据进程的优先级进行适当增加。 2) 可变分配方式 可变分配方式是指分配给进程的物理块数,在该进程的运行期间可以动态变化。它用来解决由于事先分配给进程的物理块太少而导致频繁缺页的问题。 具体实现时,先为每一进程分配必要数量的物理块,使之可以开始运行,系统中余下的空闲物理块组成一个空闲物理块队列,当某一进程在运行过程中发生缺页时,系统从空闲物理块队列中取出一个空闲块分配给该进程。只要该空闲队列中还有物理块,凡发生缺页的进程都可以在该队列中申请并获得物理块。 进程的最小物理块数是保证进程正常执行所需要的最小内存块数。进程需要的最小物理块数与计算机的硬件结构有关,取决于计算机的指令格式、功能和寻址方式。如果计算机采用单地址指令的直接寻址方式,则只需要用于存放指令的页面和存放数据的页面,最小物理块数为2; 如果采用间接寻址方式,则至少需要3个物理块。对于功能较强大的计算机,指令长度可能会超过多字节,指令本身需要跨过多个页面,则物理块的最小需要数会更大。 2. 页面调入策略 页面调入策略有两种: 请求页(Demand Paging)调入和预先页(Prepaging)调入。 1) 请求页调入 请求页调入简称请调,是指在CPU需要访问进程某页面时,发现所访问的页面不在内存中,CPU发出缺页中断信号,请求将该页调入内存。操作系统接收到缺页中断请求后,为之分配物理块并从外存将该页调入内存。 每个进程在刚开始执行时,所需的页面很多,会产生多次缺页中断,页面被逐一调入内存。根据程序的局部性原理,当进程执行一段时间后,所需要的页面会逐步减少,缺页中断次数会逐渐下降,最后趋向于很低的水平,进程运行进入相对平稳阶段。 请求页调入策略的优点是只有在需要时才将页面调入内存,节省了内存空间。 请求页调入策略的缺点如下。 (1) 在进程初次执行时,开始阶段会有大量的页调入内存,这时的进程切换开销很大。 (2) 发生缺页中断时操作系统会调入页面,而每次又仅调入一个页面,启动磁盘做I/O的频率很高。由于每次启动磁盘时会产生一个时间延迟,因此会造成系统用于I/O的时间增长,系统效率降低。 (3) 对于执行顺序跳跃性大的程序,缺页情况变化大,难以趋向稳定的水平,从而引起系统不稳定。 2) 预先页调入 预先页调入简称预调,是指由操作系统根据某种算法,预先估计进程可能要访问的页面,并在处理器需要访问页面之前先将页面预先调入内存。 预先页调入策略的优点是: 一次可将多个页面调入内存,减少了缺页中断的次数和I/O操作次数,系统付出的开销减少。如果预先动态估计准确率高,该调入策略会大大提高系统效率。 预先页调入策略的缺点如下。 (1) 如果预先动态估计准确率较低,调入的页面不被使用的可能性大,系统效率较低。 (2) 如果程序员不能预先提供所需程序部分的信息,则该调度策略难以实施。 在实际应用中,页面调入会将请求页调入和预先页调入结合起来。在进程刚开始执行时或每次缺页中断时,采用预先页调入。在进程运行稳定后,如果发现缺页,系统可采用请求页调入。 3. 页面置换策略 当需要从外存调入页到内存时,如果当前内存没有空闲物理块,则操作系统需要将某些页置换出内存,再将新的页面换入内存。选择被置换出的页有两种策略: 全局置换和局部置换。 1) 全局置换 全局置换是指操作系统从当前所有位于内存的页面中选择一个页面淘汰,释放其物理块,而不是仅从需要该页进程的物理块换出。这种置换方法会影响大多数进程的执行,是一种动态方法。 2) 局部置换 局部置换是指当某进程有页面需要换入内存时,只能从该进程目前已在内存的页面中选择一页淘汰,该置换方法对其他进程没有影响。 局部置换与全局置换相比有明显的缺点: 如果进程在执行期间所需要的内存物理块数发生变化,页面置换发生频繁,即使系统有空闲的物理块,也不可能增加给该进程; 另外,如果系统给某进程分配的物理块数太多,则系统不会收回,最终造成内存空间浪费。 4. 页面置换与页面分配的关联 1) 固定分配局部置换 为每个进程分配固定数量的物理块,在进程的整个运行期间都不再改变。当一个进程运行中发生缺页中断时,操作系统只从该进程在内存的页面中选择一页淘汰。 该策略的不足在于: 应为每个进程分配多少物理块数难以确定。如果分配给进程的物理块太少,缺页中断率高,进而导致整个多道程序系统运行缓慢; 给多了,会使内存中能同时执行的进程数减少,进而造成处理器空闲和其他设备空闲,浪费资源。 2) 可变分配全局置换 先为每一进程分配必要数量的物理块,使之可以开始运行,系统中余下的空闲物理块组成一个空闲物理块队列,当某一进程在运行中发生缺页时,系统从空闲物理块队列中取出一个空闲块分配给该进程。直到系统拥有的空闲物理块耗尽,才会从内存中选择一页淘汰,该页可以是内存中任一进程的页面。 该策略易于实现,且可以有效地减少缺页中断率,是采用较多的一种分配和置换策略。 3) 可变分配局部置换 新进程装入内存时,根据应用类型、程序要求,先分配给它一定数目的物理块。当产生缺页中断时,系统只能从产生缺页中断的进程页面中选一个页面淘汰,不能影响其他进程的执行。操作系统要不时重新评价进程的物理块分配情况,增加或减少分配给进程的物理块以改善系统总的性能。 3.6.4页面置换算法 请求分页虚拟存储管理规定,当需要从外存调入一个新的页面时,如果此时物理内存无空闲块,系统必须按照一定的算法选择内存中的一些页面调出,并将所需的页面调入内存,这个过程叫页面置换。页面置换算法决定从内存中置换出哪一个页面。 衡量页面置换算法的重要指标是缺页率。 一个进程或一个作业在运行中成功的页面访问次数为S,即所访问的页面在内存中; 不成功的页面访问次数为F,即访问的页面不在内存,需要缺页中断并调入内存; 需要访问的页面总次数为A=S+F,则缺页率f为f=F/A。 影响缺页率的因素如下。 (1) 进程分得的内存物理块数越多,缺页率越低。 (2) 划分的页面越大,缺页率越低。 (3) 如果程序局部性好,则缺页率低。 (4) 如果选取的置换算法优,则缺页率低。 在进程分得的内存物理块数和页面大小不能改变的情况下,要减少缺页率,就要考虑选择合适的页面置换算法。下面介绍4种采用局部置换策略的页面置换算法。 1. 先进先出页面置换算法 先进先出(Fist in First out,FIFO)算法的基本思想是: 总是选择最先进入内存的页面或驻留时间最长的页面先淘汰。该算法最早出现,易于实现。 先进先出算法在实现时,可以将所有页面按照进入内存的次序排成一个队列,设置一个替换指针指向队头的一页。当需要进行页面淘汰时,替换指针指向的即为当前最先进入内存的页面,该页被淘汰,然后修改指针指向淘汰页后一个页面即可,新调入的页面排入队尾。 例如,某进程的页面访问序列为6 0 1 2 0 3 0 5 2 3 0 3 2 1 2 0 1 1 6 0 1,操作系统为该进程分配了3个内存物理块。FIFO页面置换过程如图3.29所示。 图3.29FIFO页面置换算法 按照FIFO页面置换算法,缺页12次(最先进入的3个页面是正常调入,不是缺页调入),缺页率为12/21。 先进先出页面置换算法开销低、容易编程实现,适合于线性顺序特性好的程序。但是该算法没有考虑页面的访问频率,很可能刚被换出的页面马上又要被访问,使得缺页率偏高。 为了改善FIFO算法,减少缺页率,科学家尝试在进程发生缺页时给进程增加物理块。在实验中,Belady发现了一个奇怪的现象,该现象也被称为Belady异常现象。即当页数在一定范围内时,缺页率反而随分配给进程的物理块数的增加而增加。如图3.30所示,当内存物理块数从4增加到6时,缺页率增加了。该现象说明,如果要改善系统性能,不能只靠给进程增加内存物理块。 图3.30Belady异常现象 2. 最佳页面置换算法 最佳(Optimal,OPT)页面置换算法由Belady在1966年提出,其基本思想是: 在选择页面置换时应该考虑该页面将来使用的情况,且将来最长时间不用的页面被淘汰。在进程采用固定页面分配的情况下,最佳页面置换算法具有最低的缺页率。 例如,某进程的页面访问序列为6 0 1 2 0 3 0 5 2 3 0 3 2 1 2 0 1 1 6 0 1,操作系统为该进程分配了3个内存物理块。OPT页面置换过程如图3.31所示。 图3.31OPT页面置换算法 按照最佳页面置换算法,则缺页6次,缺页率为6/21。 最佳页面置换算法的难点在于很难准确预知进程在内存的页面,哪些会在未来最长时间不会被访问。因此,最佳页面置换算法只是一种理想化的页面调度算法,很难实现。但是,该算法可以作为评判其他置换算法的准则。 3. 最近最少使用页面置换算法 最近最少使用(Least Recently Used,LRU)页面置换算法的基本思想是: 进行页面置换时,选择过去最长时间内没有被使用的页面淘汰。 LRU页面置换算法淘汰的页面是在最近一段时间里较久未被访问的那一页。它是根据程序的局部性来考虑的,即那些刚被使用过的页面,可能马上还要被使用,而那些在较长时间里未被使用的页面,一般来说可能不会马上用到。 具体的实现方法是: 系统需要维护一个页面淘汰队列,该队列中存放当前在内存中的页号,每当访问一页时就调整一次,使队列尾部总指向最近访问的页,而队列头部就是最近最少用的页,发生缺页中断时总淘汰队列头部所指示的页; 而执行一次页面访问后,需要从队列中把该页调整到队列尾部。 例如,某进程的页面访问序列为6 0 1 2 0 3 0 5 2 3 0 3 2 1 2 0 1 1 6 0 1,操作系统为该进程分配了3个内存物理块。LRU页面置换过程如图3.32所示。 图3.32LRU页面置换算法 按照LRU页面置换算法,缺页9次,缺页率为9/21。 LRU算法能够合理地预测程序运行状态,具有很好的置换性能,被公认为是一种性能好且可以实现的页面置换算法,但是LRU算法在实现起来比较复杂。 图3.33时钟置换算法 4. 时钟置换算法 时钟(Clock)置换算法的基本思想如下。 (1) 将内存中所有的页面组织成一个循环队列,形成一个类似于时钟表面的环形表,循环队列指针类似于钟的指针,用来指向可能被淘汰的页面,指针开始时指向最先进入内存的页面,如图3.33所示。 (2) 时钟置换算法需要在页表中为每页增加一个访问标志位R。当页面首次装入内存时,R的初值设置为“0”,当页面被访问过后,R的值被设置为“1”。 (3) 选择淘汰页面的方法是从指针当前指向的页面位置开始扫描时钟环,如果某个页面页表中的R位为“1”,表明该页被访问过,将R清“0”,并跳过该页; 如果某个页面页表中的R为“0”,表明该页没有被访问过,该页被淘汰,指针推进一步; 如果所有的页面都被访问过,指针绕环一圈,将所有页面的R清“0”,指针回到起始位置,选择该页被淘汰,指针推进一步。 为了提高置换效率,在页面置换时,如果被淘汰的页面没有被修改过,则不需要写回外存。这样,将页表中的访问标志位R和页表中的修改标志位M配合,形成改进的时钟置换算法。 访问位R和修改位M的组合有下面4种情况。 (1) 最近没有被访问(R=0),没有被修改(M=0)。 从指针当前位置开始,选择第一个R=0、M=0的页面淘汰。 (2) 最近没有被访问(R=0),但是被修改过(M=1)。 如果没有R=0、M=0的页面,则从开始位置重新开始查找第一个R=0、M=1的页面,并将其淘汰。 (3) 最近被访问(R=1),没有被修改(M=0)。 如果没有R=0、M=1的页面,表示所有的页面R=1。再次回到开始位置时,所有页面的访问位R都被清“0”。从开始位置查找第一个M=0的页面,并将其淘汰,此时不用将淘汰页面写回外存。 (4) 最近被访问(R=1),被修改(M=1)。 当前面3种情况都不存在时才考虑R=1、M=1的情况。 该策略的主要优点是没有被修改过的页面会被淘汰,但不必写回外存,节省了I/O时间。但是查找淘汰页面可能需要多次扫描时钟,增加了算法的开销。 Macintosh操作系统就采用了这种既考虑访问位,又考虑修改位的改进时钟页面置换算法。 3.6.5影响请求页式存储管理性能的因素 虚拟存储技术以增加进程执行的时间为代价换来系统更多的虚拟内存,现分析分配给进程的物理块数量、页面大小等因素对其性能的影响。 1. 分配给进程的内存块数量与缺页率的关系 一般说来,分配给进程的物理块数量越多,缺页率越小。例如,若某进程逻辑地址共需30个页面,取极端情况,为其分配30个物理块,则所有页面全部进入内存,缺页率自然为0。不过,此时请求页式存储管理已变成了页式存储管理。如果取另一个极端,即只分给进程一个物理块,只能容纳下一页,这种情况下毫无疑问会频繁发生缺页中断,缺页率最大。实验结果表明,对每个进程来说,为其分配进程空间页面数约一半的物理块时,请求页式存储管理的效果最好。 2. 页面大小对系统性能的影响 1) 从页表大小考虑 如果页面较小,页数就要增加,页表也随之扩大,为了控制页表所占的内存空间,应选择较大的页面尺寸。 2) 从内存利用率考虑 内存以块为单位,一般情况下进程的最后一个页面总是装不满一个物理块,会产生内部碎片,为了减少内部碎片,应选择小的页面尺寸。 3) 从读写一个页面所需的时间考虑 作业存放在辅助存储器上,从磁盘读入一个页面的时间包括等待时间(移臂时间+旋转时间)和传输时间,通常等待时间远大于传输时间。显然,加大页面的尺寸,有利于提高 I/O 的效率。 综合考虑以上三点,现代操作系统中,页面大小大多选择在 512B~4KB。如Atlas为512B、IBM370系列机为2048B或4096B、VAX为512B、IBM AS/400为512B、Intel x86为4096B、MIPS R4000 提供4096B~16MB共7种页面长度。页面长度是由 CPU 中的MMU 规定的,操作系统通过特定寄存器的指示位来指定当前选用的页面长度。 3. 缺页率对系统性能的影响 用p表示缺页率,如果p=0,则不缺页; 如果p=1,则始终缺页。 抖动: 抖动是由于缺页而引起的一种系统现象,即处理器频繁地处理页面退出和调入,处理器实际处理程序的能力大大减小。“抖动”现象常在缺页率非常高时发生。 用st表示缺页处理时间,缺页处理时间包括从外存取相关页面,并将其放入内存的时间。 用ma表示对内存一个页面的总访问时间。 用vt表示有效访问时间。 在非缺页的情况下: vt=ma。 在缺页率为p的情况下: vt=(1-p)×ma+p×st。 在任何情况下,缺页处理时间由下面3个主要部分构成。 (1) 缺页中断服务时间。 (2) 读页面时间。 (3) 恢复进程时间。 缺页中断服务和恢复进程所花费的时间约为1~100ms,磁盘寻道时间约为15ms,磁盘延迟时间约为8ms,传输时间约为1ms,则包括硬件和软件在内的整个缺页处理时间st最少为25ms。内存访问时间ma为100ns,则在缺页率为p的情况下,有效访问时间vt为 vt=(1-p)ma+pst =(1-p)×100+p×25 000 000 =100+24 999 900×p(ns) 可见,有效访问时间直接正比于缺页率。 如果缺页率为1/1000,则缺页时的有效访问时间约为25μs,而没有缺页时的页面访问时间仅为0.1μs,可见缺页造成有效访问时间增加很多。 在实际应用中,缺页不只使得缺页的进程执行减慢,还会影响到其他进程的执行。如果一个进程队列阻塞等待某个设备,而该设备正用于一个缺页的进程,则等待设备的进程会等待更长的时间才能得到请求的设备。 可见,缺页不仅使得缺页进程本身的运行减慢,还会使得整个系统的运行效率降低,系统性能下降。 3.7请求分段虚拟存储管理 3.7.1请求分段虚拟存储管理的基本原理 请求分段虚拟存储管理的基本思想是: 将用户程序的所有段首先放在辅助存储器中,当用户程序被调度投入运行时,首先把当前需要的一段或几段装入内存,在运行过程中访问到不在内存的段时再把它们从外存装入。 请求分段中的段表在段式存储管理的基础上需要增加相应的字段,其段表包括段号、段长、存取权限、在内存中的起始地址、在外存中的起始地址、是否在内存、修改标志、共享标志和扩充位等。 段表中的这些字段用来说明哪些段已在内存,存放在什么位置,段长是多少; 哪些段不在内存,它们在辅助存储器的位置; 该段是否被修改过,是否能移动,是否可扩充,是否能共享等。 当程序在运行中需要访问某段时,需要查段表,若该段在内存中,则按段式存储管理进行地址转换得到绝对地址。若该段不在内存中,则硬件发出一个缺段中断。操作系统处理这个缺段中断时,先查找内存分配表,找出一个足够大的连续区域容纳该分段。如果找不到足够大的连续区域则检查空闲区的总和,若空闲区总和能满足该分段要求,则进行适当移动后,再将该段装入内存; 若空闲区总和不能满足要求,则可调出一个或几个分段在辅助存储器上,再将该分段装入内存。 在执行过程中,有些数据段的大小会随输入数据多少而变化。这就需要在该分段尾部添加新信息,但添加后的段的总长度应不超过硬件允许的每段最大长度。对于这种变化的数据段,当要往其中添加新数据时,由于欲访问的地址超出原有的段长,硬件首先会产生一个越界中断。操作系统处理这个越界中断时,先去判断该段的“扩充位”标志,如果可以扩充,则允许增加段的长度; 如果该段不允许扩充,则这个越界中断就表示程序出错。 缺段中断和段扩充处理流程如图3.34所示。 图3.34缺段中断和段扩充处理流程图 3.7.2请求分段虚拟存储管理段的共享和保护 请求分段虚拟存储管理是为了实现段的共享,除了原有的进程段表外,还要在系统中建立一张段共享表,每个共享分段占一个表项,每个表项包含如下两部分内容。 第1部分包含共享段名、段长、内存起始地址、状态位(如在不在内存)、辅存地址、共享进程个数计数器。 第2部分包含共享该段的所有进程名、状态、段号、存取控制位(通常为只读)。 当出现第一个要使用某个共享段的进程时,操作系统为此共享段分配一块内存,再将共享段装入该区。同时将共享段在内存的起始地址填入共享段表中对应项的内存起始地址处,共享进程个数计数器加1,修改状态位为1(在内存),填写使用该共享段进程的有关信息,包括进程名、使用共享段的段号、存取控制等。而进程段表中共享段的表项指向内存中共享段表地址。此后,当又有进程要使用该共享段时,仅需直接填写共享段表和进程段表,再把共享进程个数计数器加1。当进程不再使用共享段时,应释放该共享段,除了在共享段表中删去进程占用项外,还要把共享进程个数计数器减1。共享进程个数计数器为0时,说明已没有进程使用此共享段了,系统需要回收该共享段的物理内存,并把占用表项也取消。 这样做的优点是: 不同进程可以用不同段号使用同一个共享段; 由于进程段表中共享段的表项指向内存共享段表地址,因此每当共享段被移动、调出或再装入时,只要修改共享段表的项目,不必修改共享该段每个进程的段表。 请求分段存储系统中,由于每个分段在逻辑上是独立的,可通过越界检查和存取控制检查,实现存储保护。 一是越界检查。在段表寄存器中存放段长信息,在进程段表中存放每个段的段长。在存储访问时,首先,把指令逻辑地址中的段号与段表长度进行比较,如果段号大于或等于段表长度,将发出地址越界中断; 其次,还需检查段内地址是否大于段长,若是,则将产生地址越界中断,从而确保每个进程只在自己的地址空间内运行。 二是存取控制检查。在段表的每个表项中,均设有存取控制字段,用于规定此段的访问方式,通常设置的访问方式有只读、读写、只执行等。 3.7.3请求段页式虚拟存储管理 请求段页式虚拟存储管理是在段页式存储管理的基础上增加了用以实现虚拟存储的缺页中断机制、缺段中断机制来实现的。 与传统的段页式存储管理一样,用户的逻辑地址空间被划分为段号、段内页号与页内偏移。但是,请求段页式管理并没有将一个作业的所有段在作业运行前全部装入内存,只是部分段装入内存。因此,还需要有作业表来记载进入内存的作业段情况。 作业表中登记了进入系统中的所有作业及该作业的段表起始地址等信息,段表中至少包括该段是否在内存中、该段页表的起始地址等信息,页表中包括该页是否在内存中、对应的物理块号等信息。 请求段页式虚拟存储管理的动态地址转换机构由段表、页表和快表构成。在地址转换过程中如果所访问的段内页在内存中,则对其处理与段页式存储管理的情况相同。如果不能从内存段表中查询出所需要的段,则表示该段不在内存,系统发出请求调段中断信号; 如果段表中存在该段信息,但是没有所在的页面信息,则表示该页不在内存中,系统发出请求调页中断信号。 同样地,如果发出请求调段或请求调页后,如果没有内存空间,则需要在内存和外存之间进行置换。置换算法思想与页面置换算法思想类似。 3.8Windows 10 操作系统内存管理技术 3.8.1虚拟地址空间分布与地址转换机制 1. 基于x86 Windows系统的地址空间布局 基于x86 32位Windows系统采用请求页式虚拟存储器管理,提供32位的虚拟地址,为每个进程提供一个受保护的4GB虚拟地址空间。默认情况下,低2GB的地址空间为用户程序区,高2GB的地址空间为操作系统区,如图3.35所示。 图3.35基于x86 32位的Windows系统虚拟存储器地址布局 系统区又分为固定页面区、页对换区和操作系统驻留区。固定页面区中存放关键的系统代码,页面不可与外存对换; 页对换区存放非常驻系统代码和数据,可以与外存进行页面对换; 操作系统驻留区存放操作系统内核、执行体和引导驱动程序以及硬件抽象代码层,为了加快运行速度,该区的寻址由硬件直接映射。 另外,在操作系统引导时,也可以选择3GB用户程序区和1GB操作系统区的地址分配方式。这种情况主要用于运行大的用户程序。 2. 基于x86 Windows系统的逻辑地址到物理地址的转换 基于x86 Windows系统采用二级页表结构(运行物理地址扩展PAE的内核采用三级页表结构),32位的逻辑地址被划分为页目录索引、页表索引和页内位移三部分。其中,页目录索引占10位; 页表索引占10位; 页内位移占12位; 进程的逻辑地址到物理地址的变换,如图3.36所示。 图3.36基于x86的Windows系统的二级页表结构 页目录索引指出虚拟逻辑地址中页目录项在页目录中的位置,页表索引用来确定页表项在页表中的具体位置,页内位移指出该页在内存物理存储块中的具体地址。页内位移占12位,所以一页的大小最大是4KB。 每个进程都拥有自己的页目录,进程页目录的物理地址被保存在进程PCB中。当该进程执行时,该进程页目录的物理地址被复制到Intel x86的一个专用寄存器CR3中。每次进程切换都会导致寄存器CR3内容的刷新。对于多线程而言,如果同一进程的多个线程共享同一进程的地址空间,则同一进程不同线程之间的切换不会导致页目录物理地址的更新。 在基于x86 Windows系统中,页目录由页目录项(Page Directory Entry, PDE)组成,页目录占10位,因此最多允许有1024个页表项。每个页目录项占4B,描述了该进程所有页表的状态和位置,即通过页目录可以得到页表。当一页的大小是4KB时,每张页表中可以包含1024个页表项,可以指向1024个页面,每张页表可映射的地址空间为4MB,因此需要1024张页表才能映射4GB的虚拟地址空间。 页表由页表项(PageTable Entry, PTE)构成,页表项占4B,其结构如图3.37所示。 图3.37基于x86的Windows系统的页表项 页表中包括内存物理块号(占第12~31位)、修改位、访问位、有效位、禁用缓冲标志和进程的拥有者标志符等信息。具体各位含义见表3.3。 表3.3页表项各位的含义 标志位名称含义 U(第11位)转换在该内存的后备链表或修改链表中,不是有效页 F(第10位)原型表示该页为共享页 Cw(第9位)保留 Gl(第8位)全程符变换对全部进程有效,0表示该页是私有页,1表示该页是共享页 L(第7位)保留 D(第6位)修改位此页是否已被修改过,0为未被修改过,1为被修改过 A(第5位)访问位此页是否已被访问过,0为未被访问过,1为被访问过 Cd(第4位)禁用高速缓存禁止访问此页的高速缓存 Wt(第3位)通写再多处理环境下可写,写入此页时禁用高速缓存,内存页面数据修改时立即刷新磁盘对应数据 O(第2位)所有者此页可否在用户态下访问,还是只能在核心态下访问 W(第1位)写0表示页只读,1表示页可读写 V(第0位)有效表示变换是否映射到物理内存的实际页面,0为无效,1为有效。访问无效页时产生缺页中断 在地址变换时,操作系统从运行进程的进程控制块中得到进程页目录的起始地址,并将该地址放入页目录寄存器中。通过页目录寄存器寻址到页目录,查询页目录表得到页表的起始地址,再通过查询页表得到逻辑地址中的页面号所对应的物理块号,最后将物理块号与页内偏移一起构成物理地址。 3. x64 Windows系统的虚拟地址空间分布 64位的虚拟地址空间理论上允许最大可达16EB(艾字节)的虚拟内存,相对于32位x86 Windows系统的4GB寻址空间来说是很大的改进。不过,当前及短时期的未来计算机暂不需要支持这么大的内存。 为了简化芯片体系结构并避免不必要的负担,目前AMD公司和Intel公司的x64处理器只实现了256TB的虚拟地址空间,也就是说64位的虚拟地址中,只使用了低48位。虚拟地址仍然占64位,其高16位被设置为与最高的被实现的位(位47)相同的值。其虚拟地址空间低地址的一半空间(下半段)开始于0x0000000000000000,结束于0x00007FFFFFFFFFFF。高地址的一半空间(上半段)开始于0xFFFF800000000000,结束于0xFFFFFFFFFFFFFFFF。这两部分每个都是128TB。随着处理器更新换代实现了越来越多的地址位以后,下半段内存将会向上扩展,直到0x7FFFFFFFFFFFFFFF为止,而上半段内存将会向下扩展,直到0x8000000000000000为止。 x64 Windows 10系统目前只允许使用略微超过16TB的空间,这一空间被分割成两个8TB的区域: 在用户模式下每个进程的区域,从0开始向上到达较高地址(结束于0x000007FFFFFFFFFF); 在内核模式下系统范围的区域,从0xFFFFFFFFFFFFFFFF向下到达较低地址,对绝大多数用户来说,结束于0xFFFFF80000000000。 4. 基于x64 Windows 10系统的逻辑地址到物理地址的转换 x64的地址转换机制类似于x86 的PAE模式,但是增加了第四级。每个进程有一个顶级的、扩展的页目录(称为四级页映射表),其包含512个第三级结构的物理位置信息,这些结构称为页面父目录(Page Parent Directory)。页面父目录类似于x86 PAE的页目录指针表,这样的表有512个,并且每个页面父目录是一整个页面,包含512个表项。页面父目录的表项含有第二级页目录的物理位置信息; 每个页目录包含512个指针,指向单独的页表。最后,页表(每个页表包含512个页表项)包含内存中页面的物理位置信息。 当采用48位的虚拟地址时,构成48位虚拟地址的各个部分,如图3.38所示。 图3.38x64的虚拟地址 基于x64 Windows 10系统的多级页表结构如图3.39所示,图3.40显示了x64硬件页表项的格式。 图3.39基于x64 Windows 10系统的多级页表结构 图3.40x64硬件页表项的格式 3.8.2虚拟存储管理 1. 页面调入与置换策略 当发生缺页时,系统首先检查所需页是否在后备链表或修改链表中。若在,则将其移出,放入进程的工作集中,不再分配新的物理块。若不在,如果需要一个零初始化页,则内存管理程序在零页链表中取出第一页; 如果零页链表为空,则从空闲链表中取出一页并对它进行初始化; 如果需要的不是零初始化页,则从空闲页表中取出第一页; 如果空闲链表为空,则从零初始化页中取出一页; 如果以上任一情况中零页链表和空闲表均为空,则使用后备链表。 Windows 10系统采用请求页调入和预调入两种调页方式。当一个线程发生缺页时,内存管理器引发中断的页面及后继的少量页面一起装入内存。为了防止进程损失太多内存,系统采用局部FIFO算法淘汰页面。 2. 进程的工作集管理 Windows系统的进程工作集为进程当前在内存中的页面集合。每个进程都有一个默认工作集的最大值和最小值,如表3.4所示。系统初始化时,所有进程的默认工作集是相同的。当物理内存大于32MB时,进程默认最小工作集为50页,最大工作集为345页。在进程执行过程中,内存管理器会对进程工作集大小进行自动调整。 表3.4默认工作集的最大值和最小值 内 存 大 小默认最小工作集/页默认最大工作集/页 小于19MB2045 20~32MB30145 大于32MB50345 当一个进程的工作集降到最小后,如果该进程再发生缺页中断,并且内存并不满,系统会自动增加该进程的工作集尺寸。 当一个进程的工作集升到最大后,如果没有足够的内存可用,该进程每发生一次缺页中断,系统都要从该进程工作集中淘汰一页,再调入所请求的页面。如果有足够内存可用,系统允许一个进程的工作集超过它的最大工作集尺寸。 当物理内存剩余不多时,系统将检查内存中的每个进程,查看其当前工作集是否大于其最大工作集。如果是,则淘汰该进程工作集中的一些页,直到空闲内存数量足够或每个进程都达到最小工作集。 为了测试和调整进程当前工作集的合适尺寸,系统会定时从进程中淘汰一个有效页,观察其是否会发生缺页中断。如果进程没有发生缺页中断,则该进程工作集减1,并回收该页框到空闲链表中。 因此,Windows 系统的虚拟内存管理总是为每个进程提供尽可能好的性能,而无须用户或系统管理员的干预。 3.8.3Windows操作系统的内存空间分配 基于x86 Windows 系统的内存管理器采用请求页式调度算法将页面调入内存,当进程要访问的逻辑地址引发缺页中断时,内存管理器才将所缺的页调入,页表的建立也是当进程实际访问时进行。系统通过虚拟地址描述符(Virtual Address Descriptor,VAD)来描述进程地址空间的状态,从而得知一个进程的虚拟地址空间中哪些使用、哪些没有使用。虚拟地址描述符信息构成一颗自平衡二叉树,如图3.41所示。 图3.41虚拟地址信息自平衡二叉树 当进程的某段虚拟地址空间被使用时,内存管理器创建一个VAD来存储分配请求所提供的信息,包括该段虚拟地址空间是共享的还是私有的、子进程是否可以继承该段地址空间、该段地址空间应用于页面的保护措施(如只执行、只读或可读可写)。 当进程首次访问该段地址空间的一个地址时,内存管理器为包含这个地址的页创建页表项。如果进程访问的地址在VAD覆盖的地址范围之外,内存管理器就知道这个进程试图使用没有分配的内存,就会产生地址越界中断。 进程地址空间中的页面处于空闲、保留或提交三种状态之一。保留页面是为进程将来使用所保留的一块虚拟地址空间; 提交页面是指已分配物理内存的页面; 提交页面可以是私有的,也可以是映射到映射文件的某一部分。 如果页面是私有的,且以前从来没有被访问过,第一次被访问时,它们被当作零初始化页面创建。私有提交页面不允许其他进程访问。如果提交页面映射到映射文件的某一部分,且其他拥有该映射文件的进程还没有访问过该页面,首次访问该页面的进程需要从磁盘读出该页面。 地址空间先保留,需要时再提交,分两步的目的是为了减少内存的使用。保留内存是使Windows系统快捷地操作,因为它不消耗任何物理内存,只需要更新或创建进程的虚拟地址描述符。先保留、再提交,对于需要大量连续内存缓冲区的应用程序非常有用。 3.8.4内存页面级保护机制 Windows系统提供了4种保护机制,防止用户破坏其他进程或操作系统。 (1) 区分内核态和用户态,只有核心态线程才能访问核心态下组件使用的数据结构和内存缓冲池,用户态线程不能访问核心态下组件使用的数据结构和内存缓冲池。 (2) 系统通过虚拟地址映射机制保证每个进程有独立、私有的虚拟地址空间,禁止其他进程的线程访问。 (3) 以页面为单位的保护机制,页表中包含了页级保护标志,如只读、读写等,以决定用户态和核心态可访问的类型,实现访问监控。 (4) 以对象为单位的保护机制,每个区域对象具有附加的标准存取控制,当一个进程试图打开它时,系统会检查其存取控制,以确保该进程是否被授权访问对象。 3.9Linux操作系统存储管理技术 3.9.1Linux操作系统存储管理概述 Linux系统中每个用户进程可以访问4GB的虚拟内存地址空间。其中,0~3GB的虚拟内存地址是用户空间,用户进程独占并可以直接访问; 3~4GB的虚拟内存地址是内核态空间,由所有核心态进程共享,存放仅供内核态进程访问的代码和数据,用户进程处于用户态时不能访问。当中断或系统调用发生时,用户进程进行运行模式切换(处理器特权级别从3 转为0),进程从用户态切换到内核态后可以访问。 Linux系统采用请求页式虚拟存储管理。页表分为三层: 页目录(Page Directory,PGD)、中间页目录(Page Middle Directory,PMD)和页表(Page Table,PT)。在Pentium 计算机上实现时它被简化成两层,将PGD和PMD合二为一。 每个进程都有一个页目录,其大小为一个页面,页目录中的每一项指向中间页目录的一页,每个活动进程的页目录都在主存中。中间页目录可能跨多个页,它的每一项指向页表中的一页。页表也可能跨多个页,每个页表项指向该进程的一个虚页。 当使用系统调用fork()函数创建一个进程时,为其分配内存页面的情况如下。 (1) 进程控制块 1 页。 (2) 内核态堆栈 1 页。 (3) 页目录 1 页。 (4) 页表若干页。 而使用exec()函数进行系统调用时,分配内存页面的情况如下。 (1) 可执行文件的文件头1页。 (2) 用户堆栈的1页或几页。 这样,当进程开始执行时,如果执行代码不在内存中,将产生第1 次缺页中断,让操作系统参与分配内存,并将执行代码装入内存中。此后,按照需要,不断地通过缺页中断调进代码和数据。当系统内存资源不足时,由操作系统决定是否调出一些页面。 3.9.2虚拟地址空间的组织和管理 Linux系统将每个用户进程4GB 的虚拟地址空间划分成2KB 或4KB(默认方式为4KB)大小的固定页面,采用分页方式进行管理。但由此带来的管理开销相当大,仅一个进程 4GB 空间的页表将占用4MB的物理内存。事实上,几乎没有应用进程大到如此规模,因此,有必要显式地表示真正被进程使用到的那部分虚拟地址空间(也称为段)。这样一来,虚拟地址空间就由许多个连续虚地址区域构成,Linux中采用了虚存段(Virtual Memory Area,VMA)及其链表来表示。 一个VMA是某个进程的一段连续的虚存空间,在这段虚存空间里的所有单元拥有相同特征,如属于同一进程、相同的访问权限、同时被锁定、同时受保护等。VMA由如下数据结构vm_area_struct 描述。 struct vm_area_struct { struct mm-struct *vm_mm; /*虚存段所在的mm-struct 指针*/ unsigned long vm_start; /*虚存段起始地址*/ unsigned long vm_end; /*虚存段末端地址*/ pgprot_t vm_page_prot; /*虚存段存取权限*/ unsigned short vm_flags; /*虚存段操作标志位*/ shrot vm_avl_height; /*虚存段的AVL树的高度*/ struct vm_area_struct *vm_avl_left; /*虚存段的AVL树的左节点*/ struct vm_area_struct *vm_avl_right; /*虚存段的AVL树的右节点*/ struct vm_area_struct *vm_next; /*按地址排列的链接下一个VMA的指针*/ struct vm_area_struct *vm_next_share;/*共享同一文件的下一个VMA*/ struct vm_area_struct *vm_prev_share;/*共享同一文件的上一个VMA*/ struct vm_operations_struct vm_ops; /*VMA上所定义的操作集*/ unsigned long vm_offset; /*相对文件中共享内存起点的位移*/ struct inode *vm_inode; /*指向文件inode 或NULL*/ unsigned long vm_pte; /*pte表*/ … }; 进程通常会占用几个VMA,分别用于代码段、数据段、堆栈段等。在Linux系统中对VMA按照如下规则管理: 每当创建一个进程时,系统便为其建立一个PCB,称为task_struct 结构,在这个结构中内嵌了一个包含此进程存储管理有关信息的mm_struct 结构。 从每个进程控制块的内嵌mm_struct 可以找到内存管理数据结构,从内存管理数据结构的指向VMA的链接指针mmap就可找到用vm_next 链接起来的进程的所有VMA。此外,每个进程都有一个页目录PGD和存储该进程所使用的内存页面情况,Linux系统根据“惰性”按页调度原则只分配到的内存页面,从而避免页表占用过多的物理内存空间。 3.9.3物理内存空间的管理 在Linux操作系统控制下,物理内存划分成页框,其长度与页面相等。系统中的所有物理页框都由men_map 表描述,它在系统初始化时通过free_area_init()函数创建。men_map表是由men_map_t 构成的一个数组,每个men_map_t 描述一个物理页框,其定义如下。 typedef struct page { struct list_head list; /*list_head是通用双向链队列结构,链接page*/ struct page *next_hash; /*page cache的hash 表中的后继指针*/ atomic_t count; /*访问此页框的进程计数*/ unsigned long flags; /*一些标志位*/ unsigned dirty; /*页框修改标志*/ struct list_head lru; /*页面换出链表或活跃链表*/ unsigned age ; /*页框年龄,越小越先换出*/ unsigned long map_nr; /*页框在mem_map 表中的下标*/ struct page **pprev_hash; /*pager 快存的hash 表中的链表前向指针*/ struct buffer_head *buffers; /*若页框作为缓冲区,则指示地址*/ struct inode *inode; /*页框主存放代码或数据所属文件的inode*/ unsigned long offset; /*若该页框内容为文件,则指定文件的位移*/ … } mem_map_t; 在物理内存的低端,紧靠mem_map 表的bitmap 以位示图方式记录了所有物理页框的空闲状况,该表也在系统初始化时由free_area_init()函数创建。与一般位示图不同的是,bitmap分割成NR_MEM_LISTS(默认时为6)个组。 首先是第0 组,初始化时设定长度为(end_mem-start_mem/PAGE_SIZE/20+3),每位表示20 个页框的空闲状况,置1表示已被占用。 接着是第1组,初始化时设定长度为(end_mem-start_mem/PAGE_SIZE/21+3),每位表示21 个页框的空闲状况,置1表示其中1 个或2 个页框已被占用。 类似地,对于第i组,初始化时设定长度为(end_mem-start_mem/PAGE_SIZE/2i+3),每位表示连续2i个页框的空闲状况,置1表示其中1个或几个页框已被占用。 Linux系统用free_area数组记录空闲物理页框,该数组由NR_MEM_LISTS 个free_area_struct 结构类型的数组元素构成,每个元素均作为一条空闲链表头。 struct free_area_struct{ struct page *next ,*prev ; /*此结构的next 和prev 指针与struct page 匹配*/ unsigned int *map; /*指向bitmap 表*/ };free_area_t; 与bitmap 的分配方法一样,所有单个空闲页框组成的链表挂到free_area数组的第0 项后面,连续2i个空闲页框被挂到free_area数组的第i项后面。Linux系统采用buddy算法分配空闲块,块长可以是2i个(0≤i<NR_MEM_LISTS)页框,页框的分配由_get_free_pages()函数执行,释放页框可以用free_pages()函数执行。 当分配长度是2i页框的块时,从free_area数组的第i条链表开始搜索,找不到再搜索第i+1条链表,以此类推。若找到的空闲块长正好等于需求的块长,则直接将它从free_area中删除,返回第一个页框的地址。若找到的空闲块大于需求的块长,则将空闲块前半部分插入free_area中的前一条链表,取后半部分,若还大,则继续对半分,留一半取一半,直到相等。同时,bitmap表从第i组到第NR_MEM_LISTS组的对应的bit置1。 回收空闲块时,change_bit()函数根据bitmap 表的对应组,判断回收块的前后邻块是否也为空闲。若为空闲则要合并,并修改bitmap 表的对应位,并从free_area 的空闲链表中取下该相邻块。这一算法可递归进行,直到找不到空闲相邻块为止,将最后合并成的最大块插入free_area 的相应链表中。 3.9.4用户态内存的申请与释放 用户进程可以使用 vmalloc()和vfree()函数申请和释放大块存储空间,分配的存储空间在进程的虚地址空间中是连续的,但它对应的物理页框仍需经缺页中断后,由缺页中断处理例程分配,所分配的页框也不是连续的。 可分配的虚地址空间由vmlist 表管理,3GB是内核态可以访问的虚拟内存起始地址,high_memory是安装在机器中实际可用的物理内存的最高地址。因而,3GB+high_memory也就是进程虚拟地址空间中的内存上限。HOLE_8M则为长度8MB的“隔离带”,起到越界保护作用。这样,vmlist管辖的虚地址空间既不与进程用户态0~3GB虚地址空间冲突,也不与进程内核映射到物理空间的3~3GB+high_memory的虚地址空间冲突。 vmlist链表的节点类型vm_struct 定义如下。 struct vm-struct{ unsigned long flags; /*虚拟内存块占用标志位*/ void *addr; /*虚拟内存块的起始地址*/ unsigned long size; /*虚拟内存块的长度*/ struct vm-struct *next /*下一个虚拟内存块*/ }; static struct vm-struct *vmlist=NULL; 初始时,vmlist 仅一个节点,vmlist.addr 置为VMALLOC_START(段地址为3GB,位移为high_memory+HOLE_8MB)。动态管理过程中,vmlist 的虚拟内存块按起始地址从小到大排序,每个虚拟内存块之后都有一个4KB大小的“隔离带”,用以检测访问指针的越界错误,如图3.42所示。 图3.42vmlist虚拟内存 用户进程申请和释放块连续虚拟内存分别使用vmalloc()函数和vfree()函数,其执行过程为: 申请时需给出申请的长度,然后调用set_vm_area()内部函数向vmlist 索取虚存段。如果申请成功,将会在vmlist 中插入一个vm_struct 结构,并返回首地址,为申请到的虚地址空间更改页目录和页表。释放时需给出虚拟空间首地址,找到表示该虚拟内存块的vm_struct 结构,并从vmlist 表中删除,同时清除与释放虚存段有关的目录项和页表项。 3.9.5内存的共享和保护 Linux系统中内存共享是以页共享的方式实现的,共享该页各个进程的页表项直接指向共享页,这种共享不需要建立共享页表,节省内存空间,但效率较低。当共享页状态发生变化时,共享该页的各进程页表均需要修改,要多次访问页表。 Linux系统可以对虚存段中的任一部分加锁或保护,对进程的虚拟地址加锁,实质就是对VMA的vm_flags 属性与VM_LOCKED 进行或操作。虚存地址加锁后,它对应的物理页框驻留内存,不再被页面置换程序换出。加锁操作共有4 种: 对指定的一段虚拟地址空间加锁或解锁(mlock 和munlock); 对进程所有的虚拟地址空间加锁或解锁(mlockall 和munlockall)。 对进程的虚拟地址空间实施保护操作,就是重新设置VMA的访问权限,实质就是对VMA的vm_flags重置PROT_READ、PROT_WRITE 和PROT_EXEC 参数,并重新设定vm_page_prot 属性。与此同时,对虚拟地址范围内所有页表项的访问权限也做调整,保护操作由系统调用mprotect 实施。 3.9.6交换空间、页面的换出和调入 1. 交换空间 在Linux系统中,内核态内存空间的内容不允许对换,道理很简单,因为驻留该空间的函数和数据结构都用于系统管理,有的甚至是为虚拟存储管理服务的,必须时刻准备着给CPU 引用。 Linux系统采用两种方式保存换出的页面。一种是使用整个块设备,如硬盘的一个分区,称为交换设备; 另一种是使用文件系统的一个固定长度的文件,称为交换文件。两者统称为交换空间。 交换设备和交换文件的内部格式是一致的。前4096B是一个以字符串“SWAP_SPACE”结尾的位图。位图的每一位对应于一个交换空间的页面,置位表示对应的页面可以用于换页操作,第4096B之后是真正存放换出页面的空间。这样每个交换空间最多可以容纳(4096-10)×8-1=32 687 个页面。如果一个交换空间不够用,Linux系统最多允许管理MAX_SWAPFILES(默认值为8)个交换空间。 交换设备远比交换文件更加有效。在交换设备中,属于同一页面的数据总是连续存放的,第一个数据块地址一经确定,后续的数据块可以按照顺序读出或写入。而在交换文件中,属于同一页面的数据虽然在逻辑上是连续的,但数据块的实际存储位置可能是分散的,需要通过交换文件的inode 检索。在大多数文件系统中,交换这样的页面,必须多次访问磁盘扇区,这意味着磁头的反复移动、寻道时间的增加和效率的降低。可以使用swapon 系统调用向内核注册一个交换设备或交换文件。 2. 页交换进程和页面换出 当物理页面不够用时,Linux存储管理系统必须释放部分候选替换物理页面,把它们的内容写到交换空间。内核态交换线程kswapd专门负责完成这项功能,注意内核态线程是没有虚拟空间的线程,它运行在内核态,直接使用物理地址空间。kswapd不仅能够把页面换出到交换空间,也能保证系统中有足够的空闲页面以保持存储管理系统高效运行。 kswapd在系统初启时由init创建,然后调用init_swap_timer()函数进行设定时间间隔,并马上转入睡眠。以后每隔10ms swap_tick()响应函数被周期性激活,它首先察看系统中空闲页面是否变得太少,利用free_pages_high 和free_pages_low两个变量做评判标准。如果空闲页面足够,kswapd 继续睡眠,否则kswapd 进行页面换出处理。kswapd 线程依次从如下三条途径缩减系统使用的物理页面。 (1) 缩减page cache 和buffer cache。 (2) 换出共享内存占用的页面。 (3) 换出或丢弃进程占用的页面。 3. 缺页中断和页面调入 磁盘中的可执行文件映像一旦被映射到一个进程的虚拟空间,就开始执行。由于一开始只有该映像区的开始部分被调入内存,因此进程迟早会执行那些未被调入内存的部分。当一个进程访问了一个还没有有效页表项的虚拟地址时,处理器将产生缺页中断,通知操作系统,并把缺页的虚拟地址(保存在CR2 寄存器中)和缺页时访问虚存段的模式一并传给Linux系统的缺页中断处理程序。 系统初始化时,首先设定缺页中断处理程序为do_page_fault()函数。根据控制寄存器CR2传递的缺页地址,Linux系统必须找到用来表示出现缺页的虚拟存储区vm_area_struct结构,如果没有找到,则说明进程访问了一个非法存储区,系统将发出一个信号告知进程出错。然后系统检测缺页时访问模式是否合法,如果进程对该页的访问超越权限,系统也将发出一个信号,通知进程的存储访问出错。通过以上两个步骤的检查,可以确定缺页中断是否合法,进而进程进一步通过页表项中的位P来区分缺页对应的页面是在交换空间(P=0且页表项非空),还是在磁盘中某一执行文件映像的一部分。最后进行页面调入操作。 Linux系统的页面替换算法在Clock算法基础上作了改进,访问位被一个8位的age变量取代,每当一页被访问时,age增加1; 在后台,内核周期性地扫描全局页面池,并且当它在主存中所有页间循环时,对每个页的age变量减1; age为0的页是一个“旧”页,已有一段时间未被访问过,因而,可用作页替换的候选者。age值越大,该页最近被使用的频率越高,也就越不适宜于被替换。因此,Linux系统的页面替换算法是一种最少使用频率策略。 3.9.7缓冲机制 Linux系统虚存管理的缓冲机制主要包括swap cache、page cache和kmalloc cache。 1. swap cache 如果以前被换出到交换空间的页面由于进程再次访问而调入物理内存,只要该页面调入后未被修改过,那么它的内容与交换空间中内容是一样的。这种情况下,交换空间中的备份是有效的。因此,该页面再度被换出时,就没有必要执行写操作。 Linux系统采用swapcache表描述的swap cache来实现这种思想。swap cache实质上是关于页表项的一个列表,表的首地址为: Vnsigned long *swap-cache; 每一物理页框都在swapcache 中占有一个表项,该表项的总数就是物理页框总数。若该页框的内容是新创建的; 或虽然曾被换出过,但换出后,该页框已被修改过时,则该表项清0。内容非0 的表项,正好是某个进程的页表项,描述了页面在交换空间中的位置。当一个物理页框换出到交换空间时,它先查swap cache。如果其中有与该页面对应有效的页表项,则不需要将该页写出,因为原有空间中内容与待换出的页面是一致的。 2. page cache 页缓冲的作用是加快对磁盘文件的访问速度。文件被映射到内存中,每次读取一页,而这些页就保存到page cache中,Linux系统用hash表page_hash_table来访问page cache,它是指向由page类型节点组成的链表指针。 每当需要读取文件的一页时,总是先通过page cache读取。如果所需页面就在其中,就通过指向表示该页面的mem_map_t的指针; 否则必须申请一个页框,再将该页从磁盘文件中调入。 如果可能的话,Linux还将发出预读一页的读操作请求,根据程序局部性原理,进程在读当前页时,它的下一页很可能被用到。 随着越来越多的文件被读取、执行,page cache会越来越大。进程不再需要的页面应从page cache中删除。当系统发现内存中的物理页框越来越少时,它将缩减page cache。 3. kmalloc cache 进程可用kmalloc()函数和kfree()函数向系统申请较小的内存块,而这两个函数共同维护了一个称作kmalloc cache的缓冲区,其主要目的是加快释放物理内存的速度。 3.10Android操作系统内存管理机制 Android操作系统基于Linux 2.6内核,采用了“应用程序关闭而不退出”的设计概念。Android系统在内存管理方面不同于Linux系统的是: Android操作系统中并未采用虚拟内存技术,故Android系统在进行管理区页面回收时并不采用页面交换方法,而是采用直接丢弃页面或将页面写入外部设备的方法。 一方面,Android系统的内核线程kswapd会周期性地检查系统空闲内存,一旦发现内存短缺,就会进行管理区页面回收和缓存收缩。同时,在Dalrik虚拟机(Dalvik Virtual Machine,DVM)内部也会进行空闲内存检测,当空闲内存较低时,启动垃圾回收机制。 另一方面,当应用程序申请内存失败时,也会触发内存紧缺回收机制。通常,在应用程序申请内存时,若DVM中空闲内存不足,会首先尝试DVM垃圾回收,若无法回收到足够的内存,则要判定DVM是否达到动态扩展内存的最大限值。若达到最大限制,则DVM抛出“内存溢出”(out of memory)错误,随后进程异常终止,等待操作系统进程调度时被回收。若未达到最大限制,则DVM继续向操作系统申请内存。若此时操作系统也处于内存紧缺状态,就会触发操作系统内存紧缺回收机制,即管理区页面回收和缓存收缩。若操作系统经过管理区页面回收和缓存收缩后,仍处于内存紧缺的状态,则启动oomkiller机制,强制结束系统进程。 Android系统采用了“程序关闭而不退出”的设计理念,即应用程序将会常驻内存。但是,除了当前正在运行的前台进程及后台服务外,其他应用程序不会占用CPU时间。由于启动与运行一个应用程序需要一定的时间开销,为了加快运行速度,Android系统并不会立即终止一个退出的程序,而是让它驻留在内存中,以便下次运行时迅速启动。但是,随着程序越来越多,内存会出现不足。当Android系统需要某一进程释放资源为其他进程所用时,系统会使用“Low Memory Killer”机制终止进程释放内存。Low Memory Killer在Linux内核中实现,按应用程序的重要性来决定终止哪一个。因此,必须合理设置进程的优先级,否则该进程可能在执行过程中被系统强制终止。 Android系统中每个程序都有一个oom_adj值,其值越小,优先级越高,被终止的可能性越低。 (1) 前台进程(Active Process): oom_adj值为0。前台进程为正在与用户交互的应用程序。为响应前台进程,Android系统可能要终止其他进程以释放内存。前台进程分为以下三类。 ① 活动,正在前台接收用户输入事件。 ② 活动,服务与广播接收器正在执行一个onReceive()事件处理函数。 ③ 服务正在执行onStar、onCreate()或onDestroy()事件处理函数。 (2) 已启动服务的进程(Started Service Process): oom_adj值为0。这类进程包含一个已启动的服务。服务并不直接与用户输入交互,因此服务的优先级低于可见活动的优先级。但是,已启动服务的进程仍然被认为是前台进程,只有在活动及可见活动需要资源时,已启动服务的进程才会被终止。 (3) 可见进程(Visible Process): oom_adj值为1。活动(Activity)是可见的,但并不在前台,或者不响应用户的输入。例如,Activity被非全屏的Activity或透明的Activity所遮挡,包含此类可见Activity的进程被称为可见进程。只有在非常罕见的极端情况下,此类进程才会被终止以释放内存。 (4) 后台进程(Background Process): oom_adj值为2。这类进程不包含任何可见的活动与启动的服务。通常大量后台进程存在时,系统会采用后见先杀(LastSeenFirestKilll)的方式,释放内存供前台进程使用。 (5) 主界面(Home Process): oom_adj值为4。 (6) 隐藏进程(Hidden Process): oom_adj值为7。 (7) 内容提供者(Content Provider): oom_adj值为14。 (8) 空进程(Empty Process): oom_adj值为15。既不提供服务,也不提供内容的进程。 Android系统通常有一个内存警戒值与oom_adj值的对应表: 每个内存警戒值对应一个oom_adj值。当系统内存低于警戒值时,所有大于oom_adj值的进程都可被终止。内存警戒与oom_adj值对应关系如表3.5所示。 表3.5内存警戒值表 各 类 进 程oom_adj值内存警戒值(以4KB为单位) 前台进程/服务进程 0 1536 可见进程 1 2048 后台进程 2 4094 隐藏进程 7 5120 内容提供者 14 5632 空进程 15 6144 当可用内存小于6144×4KB=24MB时,系统开始终止所有的空进程,当可用内存小于5632×4KB=22MB时,系统开始终止所有内容提供者与空进程。 当过多进程在内存中未被释放时,系统反应速度会降低,用户可以自行使用如task killer与task manager之类的工具软件手动终止不必要的后台进程与空进程,强制释放资源。 3.11Windows、Linux与Android操作系统内存管理的比较 Linux系统和Windows系统在面对相同的进程地址空间大小时,对内存布局的使用方式不同。基于x86 Windows系统在一般情况下为进程分配了2GB虚拟地址空间,Linux系统的进程虚拟地址空间是4GB,而基于x64 Windows 10系统则最多允许用户进程寻址16TB的虚拟地址空间。 Linux系统和Windows系统均提供了内存共享技术,但它们的实现细节有所差别。Linux系统提供给用户的接口非常简单,只需将自己的虚拟内存空间区域附加到共享内存对象即可; Windows系统则是通过内存映射文件提供共享内存机制,较Linux系统复杂一些。 Linux系统的内存交换管理很灵活,用户可以在普通的文件系统上建立扇区连续的文件作为交换空间,还可以使用多个交换文件,从而可以动态增加交换文件。Linux系统也提供了利用交换分区作为交换空间的方法。Windows系统的页面文件很难逃脱碎片化的危险,从而可能降低交换操作的性能,为了保证 Windows系统采用无碎片的页面文件,必须采取一定的措施。 Android系统主要运行在嵌入式设备上,内存相对较小。同Linux系统类似,Android系统使用页式虚拟内存管理技术,但是不支持内存交换。Android系统为每个进程分配内存时,采用了弹性分配方式,也就是刚开始并不会一下分配很多内存给每个进程,而是给每个进程分配一个“够用”的虚拟内存范围。这个范围是根据每个设备实际的物理内存大小来决定的,并且可以随着应用的后续需求而增加,但最多也只能达到系统为每个应用定义的上限。Android系统会为每个应用程序分配一定的内存空间,并且创建一个独立的dalvik虚拟机运行程序,也就是让每个程序运行在自己的进程中。 Android系统对内存的使用思想是“尽最大限度的使用”,这一点继承了Linux系统的优点。只不过有所不同的是,Linux系统侧重于尽可能多地缓存磁盘数据以降低磁盘I/O,进而提高系统的访问性能,而Android系统侧重于尽可能多地缓存进程以提高应用启动和切换的速度。Linux系统在进程活动停止后就结束该进程,而Android系统则会在内存中尽量长时间地保持应用进程,直到系统内存紧张为止。这些保留在内存中的进程,通常情况下不会影响系统整体运行速度,反而会在用户再次激活这些进程时,加快进程的启动速度,因为不用重新加载界面资源。 小结 内存管理和虚拟存储技术是操作系统的重要功能之一。 内存管理分为连续管理和离散管理。连续管理分为单一连续管理和分区式内存管理; 离散管理分为页式存储管理、段式存储管理和段页式存储管理。 连续管理中的单一连续管理是最简单的内存管理方式,该方式只适合单道程序环境。分区存储管理适合多道程序环境。在分区存储管理中,可变分区分配算法包括最先适应分配算法、循环首次适应分配算法、最优适应分配算法、最坏适应分配算法和快速适应分配算法。 页式存储管理采用了对进程的逻辑地址空间分页,对内存的物理空间分块,页的大小等于块大小等基本思想,通过页表和地址转换机构实现逻辑地址到物理地址的转换,能够有效地利用内存空间。 段式存储管理的实现思想与分页存储管理相似。分段存储管理体现了程序设计思想,易于实现段的共享和保护。 段页式存储管理将分段与分页结合,发挥了分页和分段存储器管理的优势。 虚拟存储管理是为解决内存扩充问题而提出的,程序运行不需要调入程序的全部信息到内存便可运行,使得计算机能够运行更大、更多的用户作业,提高了系统的吞吐量。 虚拟存储管理包括: 请求分页虚拟存储管理、请求分段虚拟存储管理和请求段页式虚拟存储管理。 为了实现虚拟存储管理思想,将内存中的页面或分段与外存中的页面或分段进行置换。主要的页面置换算法有先进先出页面置换算法、最佳页面置换算法、最近最少使用页面置换算法、时钟置换算法等。本章在讲述虚拟存储管理的基础上,从应用出发,分别分析了Windows操作系统、Linux操作系统和Android操作系统的存储管理的实现方法和相互之间的区别。 习题 1. 内存管理的基本功能是什么? 2. 什么是逻辑地址,什么是物理地址,为什么要实现地址转换? 3. 可变分区存储管理中有哪些内存分配方法?比较它们的优缺点。 4. 什么是紧凑技术,什么情况下采用? 5. 什么是移动技术?什么情况下采用? 6. 请简述页式存储管理系统中的地址转换过程。 7. 比较分页与分段存储管理的差异。 8. 页式存储管理中,试分析大页面与小页面各自的优缺点。 9. 段页式存储管理中怎样划分逻辑地址空间? 10. 如果一个分页系统能够向用户提供的逻辑地址最大为16页,页面大小为2KB,内存总共有8个存储块。请问逻辑地址应该为多少位?内存空间为多大? 11. 什么是虚拟存储技术?简述实现虚拟存储管理的基本思想。 12. 请求页式虚拟存储管理中的页面置换算法有哪几种?各有何特点? 13. 请指出缺页中断和一般中断的区别。 14. 某计算机系统采用页式内存管理技术,每页2048B,某进程的页表如下所示,请计算逻辑地址5500(十进制)所对应的物理地址是多少? 页号块号 02 1 3 2 8 3 10 4 20 15. 一个32位地址的计算机系统使用二级页表,虚拟地址为: 顶级页表占9位,二级页表占11位。请问: 页面长度为多少?虚拟地址空间一共有多少个页面? 16. 在一个请求分页的虚拟存储器管理中,一个程序的运行页面走向为1、2、3、4、2、3、5、6、3、1、4、6、7、5、2、4、1、3、2,如果为程序分配的物理块分别为3个、4个,请分别用FIFO、OPT和LRU算法求出缺页中断次数和缺页率。 17. 一个有快表的请求页式虚存系统,设内存访问周期为1μs,内外存传送一个页面的平均时间为5ms。如果快表命中率为75%,缺页中断率为10%。忽略快表访问时间,试求内存的有效存取时间。 18. 某请求页式存储管理系统中,页的大小为100B,一个程序的大小为1200B,可能的访问序列为10、205、110、40、314、432、320、225、80、130、272、420、128,若系统采用LRU置换算法,当分配给该进程的物理块数为3时,给出该进程的页面淘汰情况及缺页次数。 19. 假设计算机有2MB内存,其中,操作系统占用512KB,每个用户程序也使用512KB内存。如果所有程序都有70%的I/O等待时间,那么再增加1MB内存,吞吐率增加多少? 20. 请求分页管理系统中,假设某进程的页表内容如下表所示。页面大小为4KB,一次内存的访问时间是100ns,一次快表(TLB)的访问时间是10ns,处理一次缺页的平均时间为10 000ns(已含更新TLB和页表的时间),进程的驻留集大小固定为2,采用最近最少使用置换算法(LRU)和局部淘汰策略。假设: (1) TLB初始为空; (2) 地址转换时先访问TLB,若TLB未命中,再访问页表(忽略访问页表之后的TLB更新时间); (3) 有效位为0表示页面不在内存,产生缺页中断,缺页中断处理后,返回到产生缺页中断的指令处重新执行。 设有逻辑地址访问序列2362H、1565H、25A5H,请问: 依次访问上述三个逻辑地址,各需多少时间? 页号页框号有效位(存在位) 0101H11— 02254H1