|
|
在多道程序环境下,程序要运行必须为之创建进程,而创建进程的第一件事就是要将程序和数据装入内存。要达到尽可能方便用户使用和充分利用内存以提高内存利用率的目的,就要求存储管理解决以下几个重要问题,也就是存储管理的功能。
|
|
|
(1)内存空间的分配和回收。内存分配的主要任务是将进入内存的每一道程序变为进程并为其分配内存空间;进程运行结束时,操作系统应将其所占用的内存空间收回。
|
|
|
(2)内存空间的共享。内存共享是指两个或多个进程共用内存中相同的区域,其目的是节省内存空间、实现进程间通信、提高内存空间的利用效率。
|
|
|
(3)提高内存的利用率。减少碎片(也称零头),允许多道程序动态共享内存。
|
|
|
(4)存储保护。存储保护的任务是确保每道程序都在自己的内存空间运行,互不干扰。
|
|
|
(5)内存扩充。内存扩充的任务是从逻辑上扩充内存容量,使用户认为系统所拥有的内存空间远比其实际的内存空间(RAM)大得多。
|
|
|
|
连续分配是指为一个用户程序分配一个连续的内存空间。连续分配存储管理方式主要有单一连续分配、固定分区分配、动态分区分配和动态重定位分区分配等。
|
|
|
(1)单一连续分配。单一连续分配是最简单的一种存储管理方式,但只能用于单用户、单任务的操作系统中。采用这种存储管理方式时,内存分为系统区和用户区两个分区。
|
|
|
(2)固定分区分配。固定分区分配的方法是将内存空间划分为若干个固定大小的分区,可用分区大小相等和分区大小不相等两种方法。
|
|
|
内存分配时建立一张分区使用表,表项包含有每个分区的起始地址、大小及状态(是否已分配)。
|
|
|
(3)动态分区分配。动态分区分配是根据进程的实际需要,动态地为之分配连续的内存空间。在动态分区存储管理方式中,主要的操作是分配和回收内存。在实现可变分区分配存储管理方式时,必须解决下述3个问题。
|
|
|
|
|
|
分区分配中的数据结构有空闲分区表和空闲分区链。分区分配算法有以下几种。
|
|
|
①首次适应算法。每当用户作业申请一个空间时,系统总是从内存的低地址开始选择一个能装入作业的空白区。当用户释放空间时,该算法更易实现相邻的空白区合并。
|
|
|
②循环首次适应算法。与首次适应算法的不同之处是,每次分配都是从刚分配的空闲区开始寻找一个能满足用户要求的空闲区。
|
|
|
③最佳适应算法。假设系统中有X1,X2,X3, …,Xi,…,Xn个空闲区(自由区),每当用户申请一个空间时,将从这n个空闲区中找到一个最接近用户需求的分区。这种算法能保留较大的空白区。但缺点是空闲区不可能刚好等于用户要求的区,所以必然要将一个分区一分为二。随着系统不断地分配和释放空间,可能会使产生的小分区小到无法再继续分配,人们将这样的无用小分区称为外碎片。
|
|
|
④最差适应算法。系统总是将用户作业装入最大的空闲区。这种算法将一个最大的分区一分为二,所以剩下的空闲区通常也很大,不容易产生外碎片。
|
|
|
(4)动态重定位分区分配。动态重定位分区分配是解决碎片问题的简单而又行之有效的方法。其基本思想是移动所有已分配好的分区,使之成为连续区域。由于移动分区是要付出代价的,所以通常是在用户请求空间得不到满足时进行。当移动已分配的分区时会导致地址发生变化,所以会产生地址重定位问题。解决程序重定位问题可以采取以下两种方法。
|
|
|
①使用模块装入程序。将该程序的装配模块重新装入到指定位置,使程序重新开始执行。
|
|
|
②采用动态重定位技术。利用一个重定位寄存器,自动修改访问存储器的地址。
|
|
|
|
(1)基本原理。页式存储管理将内存空间划分成等长的若干区域,每个区域称为一个物理页面,有时也称为内存块或块。内存的所有物理页面从0开始编号,称为物理页号或内存块号。每个物理页面内也从0开始依次编址,称为页内地址。
|
|
|
系统将用户程序的逻辑空间按照同样大小也划分成若干页面,称为逻辑页面,有时也简称为页。程序的各个逻辑页面从0开始依次编号,称为逻辑页号或相对页号。每个逻辑页面内也从0开始编号,称为页内地址。用户程序的逻辑地址由逻辑页号和页内地址两部分组成:
|
|
|
|
若给定一个逻辑地址空间中的地址为A,页面的大小为L,则页号P和页内地址d可按下式求得:
|
|
|
|
|
例如,某系统的页面大小为1KB,设A=2170 H,则由上式可以求得P=2,d=122。
|
|
|
页面大小一般取2的整数次幂。页面大小直接影响地址转换和页式存储管理的性能,如果页面太大,以至于和作业地址空间相差无几,这种方法就变成了可重定位分区方法的翻版;反之,如果页面太小,则增加了系统的开销。
|
|
|
存储分配时,以页面(块)为单位,按用户程序的页数多少进行分配。逻辑上相邻的页面在内存中不一定相邻,即分配给用户程序的内存块不一定连续。
|
|
|
对用户程序地址空间的分页是系统自动进行的,即对用户是透明的。由于页面大小选为2的整数次幂,故系统可将地址的高位部分定义成页号,低位部分定义成页内地址。
|
|
|
(2)地址映射。系统为每个用户程序建立一张页表,用于记录用户程序逻辑页面与内存物理页面之间的对应关系,如下表所示。用户程序的地址空间有多少页,该页表里就登记多少行,且按逻辑页的顺序排列。页表存放在内存系统区内。系统中设立一张内存空闲页面表,记录内存物理页面空闲情况,用于内存分配和回收。
|
|
|
|
|
系统提供一对硬件寄存器,即页表始址寄存器和页表长度寄存器。
|
|
|
①页表始址寄存器。用于保存正在运行进程的页表在内存的首地址。当进程被调度程序选中并投入运行时,系统将其页表首地址从进程控制块中取出并送入该寄存器。
|
|
|
②页表长度寄存器。用于保存正在运行进程的页表的长度。当进程被选中并投入运行时,系统将它从进程控制块中取出并送入该寄存器。
|
|
|
进行地址转换时先将页号与页表长度进行比较,如果页号大于或等于页表长度,则表示所访问的地址已超出进程的地址空间,产生越界中断。如果未出现错误,则将页表起始地址与页号和页表项长度的乘积相加,便得到该表项在页表中的位置,于是可得到该页的物理块号,将之装入物理寄存器中。同时再将有效地址寄存器中的页内地址直接送入物理地址的块内地址字段中。
|
|
|
在地址映射过程中,共需两次访问内存。第一次访问页表,得到数据的物理地址,第二次才是存取数据。显然,这样就增加了访问的时间。提高存取速度有两种方法:一种是在地址映射机制中增加一组高速寄存器保存页表,这需要大量的硬件开销,经济上不可行;另一种方法是在地址映射机制中增加一个小容量的联想寄存器(相连存储器),它由高速寄存器组成一张快表(快表用来存放当前访问最频繁的少数活动页的页号)。在快表中,除了逻辑页号、物理页号对应外,还增加了以下几个标志位:特征位表示该行是否为空,用0表示空,用1表示有内容;访问位表示该页是否被访问过,用0表示未访问,用1表示已访问,这是为了淘汰那些用得很少甚至不用的页面而设置的。
|
|
|
|
引入分段管理方式主要是为了满足用户的编程方便、分段共享、分段保护、动态链接和动态增长的要求。它与分页式存储管理方式的区别在于以下几点。
|
|
|
|
②页的大小固定且由系统确定,段的长度不固定,决定于用户所编写的程序。
|
|
|
③分页的作业地址空间是一维的,分段的作业地址空间是二维的。
|
|
|
(1)基本原理。在分段存储管理方式中,作业的地址空间被划分为若干个段,每个段定义了一组完整的逻辑信息。例如,有主程序段MAIN、子程序段X、数据段D及堆栈段S等,每个段都有自己的名字,通常可用一个段号来代替段名,每个段名都是从零开始编址,并采用一段连续的地址空间,各段长度是不等的。分段系统的逻辑地址由段号(名)和段内地址两部分组成:
|
|
|
|
在该地址结构中,允许一个作业最多有64K段,每个段的最大长度为64KB。
|
|
|
在分段式存储管理系统中,系统为每个段分配一个连续的分区,而进程中的各个段可以离散地分配到内存不同的分区中。在系统中为每个进程建立一张段映射表,简称为"段表"。每个段在表中占有一表项,在其中记录了该段在内存中的起始地址(又称为"基址")和段的长度。进程在执行中,通过查段表来找到每个段所对应的内存区。所以说,段表实现了从逻辑段到物理内存区的映射。
|
|
|
(2)地址映射。在进行地址变换时,系统将逻辑地址中的段号S与段表的长度TL进行比较,如果S≥TL,表示段号太大,访问越界,产生越界中断信号;若未越界,根据段表的起始地址和该段的段号计算出该段对应段表项的位置,从中读出该段在内存的起始地址,然后,再检查段内地址d是否超过该段的段长SL,若超过则越界;否则将该段的起始地址d与段内地址相加,即得到要访问的内存物理地址。
|
|
|
像分页系统一样,当段表放在内存时,每访问一个数据,都需两次访问内存,从而降低了计算机的速率。解决的方法也和分页系统类似,再增设一个联想存储器。
|
|
|
|
分页系统能有效地提高内存利用率,而分段系统则能很好地满足用户需要。对两种存储管理方式各取所长,则形成一种新的存储管理方式,即段页式存储管理方式。
|
|
|
(1)基本原理。先将用户程序分为若干个段,再把每个段划分成若干页,并为每个段赋予一个段名。程序的逻辑地址由3部分组成,其形式如下:
|
|
|
|
内存是以页为基本单位分配给每个程序的,在逻辑上相邻的页面内存不一定相邻。系统为每个进程建立一张段表,为进程的每一段各建立一张页表。地址转换过程,要经过查段表、页表后才能得到最终的物理地址。
|
|
|
(2)地址映射。首先也要配置一段表寄存器,用来集中存放段表起始地址和段长TL。先将逻辑地址中的段号S与段表的长度TL进行比较,如果S≥TL,表示段号太大,访问越界,产生越界中断信号;若未越界,利用段表起始地址和段号来求出该段对应的段表项在段表中的位置,从中得到该段的页表地址,并利用逻辑地址中的段内页号P来获得对应页的页表项位置,从中读出该页所在的物理块号b,再用块号b和页内地址构成物理地址。
|
|
|
|
前面介绍的各种存储管理方案有一个共同的问题,即当一个参与并发执行的进程运行时,其整个程序必须都在内存,因而存在以下缺点:若一个进程的程序比内存可用空间还大,则该程序无法运行;由于程序运行的局部特性,一个进程在运行的任一阶段只需使用所占存储空间的一部分,因此,未用到的内存区域就被浪费。引进虚拟存储技术,其基本思想是利用大容量的外存来扩充内存,产生一个比有限的实际内存空间大得多的、逻辑的虚拟内存空间,以便能够有效地支持多道程序系统的实现和大型作业运行的需要,从而增强系统的处理能力。
|
|
|
(1)基本原理。当进程要求运行时,不是将它的全部信息装入内存,而是将其一部分先装入内存,另一部分暂时留在外存。进程在运行过程中,要使用的信息不在内存时就发中断,由操作系统将它们调入内存,以保证进程的正常运行。虚拟存储管理分为虚拟页式、虚拟段式和虚拟段页式。
|
|
|
虚拟页式存储管理又称为请求页式存储管理。其基本思想是,在进程开始执行之前,不是装入全部页面,而是只装入一个(甚至零个)页面,然后根据进程执行的需要,动态地装入其他页面。页表中将增加若干项:驻留位(又称中断位或特征位)指示该页在内存还是在外存;外存地址给出该页在外存的地址;修改位指示该页在内存驻留期间是否被修改过。地址映射时,当从页表中查出此页信息不在内存,则发缺页中断。此时,暂停进程执行,CPU转去执行缺页中断处理程序。该程序负责把所需的页从外存调入内存,并把物理页号填入页表,更改驻留位,然后再返回继续执行被中断的进程。
|
|
|
虚拟段式存储管理的基本思想是,在进程开始执行之前,不是装入全部段,而是只装入一部分,以后再通过调段功能和置换功能将不运行的段调出,同时调入将要运行的段。
|
|
|
虚拟段页式存储管理和前两种一样,在段页式系统的基础上加入了请求调页和页面置换功能。
|
|
|
(2)对换。对换即置换,是指把内存中暂不能运行的进程,或暂时不用的程序和数据,换出到外存上,以腾出足够的内存空间,把已具备运行条件的进程,或进程所需要的程序和数据换入内存。对换是提高内存利用率的有效措施。
|
|
|
如果对换是以整个进程为单位,便称之为"整体对换"或"进程对换";如果对换是以"页"或"段"为单位进行,则分别称之为"页面对换"或"分段对换",又统称为"部分对换"。
|
|
|
在具有对换功能的OS中,通常把外存分为文件区和对换区。由于对对换区的分配是采用连续分配方式,因而对对换区空间的分配与回收和动态分区方式时内存的分配与回收方法雷同。其分配算法可以是首次适应算法、循环首次适应算法和最佳适应算法。
|
|
|
(3)页面淘汰算法。当内存空间已被占满而又要调入新页时,必须把已在内存的某一页面淘汰。如果被淘汰的页面曾被修改过,还要将此页写回到外存,再换进新的页面。这一过程称为页面淘汰。页面淘汰可以在整个内存空间范围内进行,也可以只在一个进程空间范围内考虑。但为了对有关算法作比较准确的评估,以下限制在局部范围内考虑,并假定系统限定每个进程占有的最大页面数。当空间已满,而又有新的页面要装入时,则淘汰自己的一个页面而不能淘汰别的进程的页面。
|
|
|
用来选择被淘汰页面的算法称为页面淘汰算法,主要有以下几种。
|
|
|
①最佳淘汰算法(OPT)。淘汰以后不再需要的,或者在最长时间以后才会用到的页面。这一算法不可能实现,但它可以作为衡量其他页面淘汰算法优劣的一个标准。
|
|
|
②先进先出淘汰算法(FIFO)。淘汰进入内存时间最长的页面,这是一种最简单的页面淘汰算法。FIFO算法有可能产生异常现象,即当分给一个进程的页面数增多时,缺页中断次数反而增加。
|
|
|
③最近最久未使用淘汰算法(LRU)。淘汰最后一次访问时间距当前时间间隔最长的页面。其出发点是用最近的过去估计最近的将来:一个已在内存的页面,如果在本次缺页中断前的最近一段时间内未被使用的时间最长,那么将来它很可能不再被使用,故应淘汰。LRU算法的实现开销很大,需要有硬件支持。
|
|
|
④最近最少使用淘汰算法(LFU)。淘汰最近一段时间内访问次数最少的页面。
|
|
|