五、存储器管理

1、存储器的层次结构

■  多层结构存储器系统：通用计算机而言，存储层次至少应具有三级：最高层为CPU寄存器，中间为主存，最底层是辅存。

■  存储管理的任务和功能

1.主要任务：为多道程序的并发提供良好的环境、提高存储器的利用率、逻辑上扩充主存空间、方便用户使用存储器。

2.存储管理必须具备的功能：存储空间的分配和回收、地址映射、存储共享与保护、主存扩充。

2、存储分配形式

存储分配解决多道程序之间共享主存的存储空间。
1.直接存储分配方式：程序员使用存储器的物理地址进行编程，以确保各程序之间互不重叠。

缺点：用户编程不方便；存储器的利用率不高。

2.静态存储分配方式：程序员使用存储器的逻辑地址进行编程，当连接程序对它们进行装入、连接时，才确定它们在主存中的物理地址，从而产生可执行程序。这种分配方式在进行装入、连接时，要求系统必须分配其要求的全部存储空间，否则不能装入该用户程序。一旦装入，直到程序结束时才释放。

缺点：存储器不能有效共享；不能实现对存储器的动态扩展。

3.动态存储分配方式：现代操作系统通常采用的存储管理方法。动态存储分配通常可采用覆盖和交换技术实现。

特点：在进行装入、连接时，不要求一次性将整个程序装入主存中，可根据执行需要一部分一部分的装入；同时，已装入主存的程序不在执行时，系统可以回收该程序占据的存储空间。

3、重定位：将逻辑地址转换称物理地址。

■   地址空间和存储空间：源程序经过编译或是汇编之后，产生了目标程序，而编译程序总是从0号地址单元开始，为目标程序指令顺序分配地址，我们称为相对地址或逻辑地址，这些地址的集合称为地址空间。存储空间就是指主存中一系列存储信息的物理单元的集合，这些物理单元的编号称为物理地址或绝对地址。

■  重定位：

 (1)静态地址重定位：指用户程序在装入是由装配程序一次完成，即地址变换只是在装入时一次完成，以后不在改变。

特点：实现简单。

不足：必须分配一个连续的存储空间；难以实现程序和数据共享。

 (2)动态地址重定位

必须有硬件地址变换机构的支持，即须在系统中增设一个重定位寄存器，用它来存放程序(数据)在内存中的起始地址。程序在执行时，真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的。

特点：1.执行时程序可以在主存中移动，对于移动后的程序，

只需将新的起始地址写入重定位寄存器即可。2.利于程序段共享。3.为实现虚拟存储管理提供了基础。

缺点：1.实现存储管理的软件比较复杂。2.需要硬件支持。

4、覆盖与交换

覆盖与交换技术是从逻辑上扩充主存的二种方法。

1.覆盖技术：把程序划分成若干功能相互独立的程序段，并且让那些不会同时被CPU执行的程序段共享同一主存区。通常这些程序段保存在外存中，当CPU要求某一程序段执行时，才将该程序段调入主存并覆盖某程序段。从用户的角度看，主存扩大了。

2.交换技术：也称为对换技术，最早用于麻省理工学院的单用户分时系统CTSS中。由于当时计算机的内存都非常小，为了使该系统能分时运行多个用户程序而引入了交换技术。系统把所有的用户作业存放在磁盘上，每次只能调入一个作业进入内存，当该作业的一个时间片用完时，将它调至外存的后备队列上等待，再从后备队列上将另一个作业调入内存。这就是最早出现的分时系统中所用的交换技术。

交换分为如下两类：(1) 整体交换。(2) 页面(分段)交换。

3. 交换空间的分配与回收

由于交换分区的分配采用的是连续分配方式，因而交换空间的分配与回收与动态分区方式时的内存分配与回收方法雷同。其分配算法可以是首次适应算法、循环首次适应算法或最佳适应算法等。

3、单道环境下的存储管理

  

在单道程序环境下，存储器管理方式是把内存分为系统区、用户区和剩余空闲区3部分，系统区仅提供给OS使用，它通常是放在内存的低址部分。而在用户区内存中，仅装有一道用户程序，即整个内存的用户空间由该程序独占。这样的存储器分配方式被称为单一连续分配方式。

特点：1.管理简单，只需很少的软件硬件支持。2.便于用户了解使用。

缺点： 1. 存储空间浪费大。2. CPU效率低。3. 程序和数据不能共享。4. I/O设备利用率低。

  

 

4、分区存储管理

■   固定分区法

1.分区方法：

(1) 分区大小相等(指所有的内存分区大小相等)。(2) 分区大小不等。

2. 内存分配：为了便于内存分配，通常将分区按其大小进行排队，并为之建立一张分区使用表，其中各表项包括每个分区的起始地址、大小及状态(是否已分配)

3. 缺点：固定分区存储分配技术，分区的大小是在系统初始化时进行的。但用户作业占据的存储空间，不可能刚好等于某个分区的大小，所以在分配的分区中，通常都有一部分未被进程占用浪费的存储空间，我们称这部分空间“碎片”

■   动态分区法

1. 基本概念：采用动态分区分配方式，在系统启动时，除了操作系统常驻主存部分外，只存在一个空闲分区，分配程序将该依次划分给调度程序选中的进程，并且分配的大小可随用户进程对主存的要求而改变，这种分配方式不会产生“碎片” 现象，从而大大提高的主存的利用率。

2. 动态分区分配与回收

动态分区的分配方式：

（1）首次适应(first fit，FF)算法：分配第一个大小满足要求分区

（2）最佳适应(best fit，BF)算法：分配满足要求的最小分区

（3）最坏适应(worst fit，WF)算法：与最佳适应算法相反，挑选一个最大空闲区，从中分一部分存储空间给作业使用

■   动态分区的回收

■   地址转换与存储保护

■   移动技术

■   分区存储管理优缺点

优点：

1. 实现了多道程序设计，从而提高了系统资源的利用率。

2. 系统要求的硬件支持少，管理简单，实现容易。

缺点：

1. 由于作业装入时的连续性，导致主存的利用率不高，采用移动技术可以提高主存的利用率，但增加了系统的开销。

2. 主存的扩充只能采用覆盖与交换技术，无法真正实现虚拟存储。

5、页式存储管理

■   基本原理：

1. 将主存划分成多个大小相等的页框。

2. 受页架尺寸限制，程序的逻辑地址也自然分成页。

3. 不同的页可以放在不同的页框中，不需要连续。

■   优越性：

1. 实现连续存储到非连续存储的飞跃，为实现虚拟存储打下了基础。

2. 解决了主存中的“碎片”问题。

■  缺点：

（1）要求有硬件支持，如动态地址变换，缺页中断处理机构；

（2）必须提供相应的数据结构来管理存储器，而这些数据结构不仅占用了部分储存空间，同时它们的建立和管理也要花费CPU的时间。

（3）虽能解决了分区管理中区间的零头问题，但在页式存储管理系统中的页内的零头问题仍然存在。

（4）对于静态页式存储管理系统，用户作业要求一次性装入主存，将给用户作业的运行带来一定的限制。

（5）在请求页式存储管理中，需要进行缺页中断处理，特别是请求调页的算法，若选择不当，还有可能出现“抖动” 现象，增加了系统开销，降低了系统的效率。

■   分类：静态页式存储管理、虚拟页式存储管理

■  静态页式存储管理

用户作业执行前，将该作业的程序和数据全部装入到主存中，然后，操作系统通过页表和硬件地址变换机构实现逻辑地址到物理地址的转换。

5.1主存页架的分配与回收

1、页表：在页式系统中，允许将进程的各个页离散地存储在内存的任一物理块中，为保证进程仍然能够正确地运行，即能在内存中找到每个页面所对应的物理块，系统又为每个进程建立了一张页面映像表，简称页表。

2、请求表：当系统有多个作业或进程时，系统必须知道每个作业或进程的页表起始地址和长度，才能进行主存分配和地址变换。

3、存储页框表：描述主存空间的分配情况，页框表指出了各页框是否已分配，以及未被分配的页框总数。

4、页框分配与回收算法：

1）分配：首先，从请求表中查出作业和进程数要求的页框数，然后由存储页框表检查是否有足够的空闲页框，若没有，则本次无法分配；如果有，则分配并设置页表，并填写请求表中的相应表项（页表起址、页表长度和状态），之后，再按一定的查询算法搜索出所要求的空闲页框，并将对应的页框号填入页表中。

2）回收：页框的回收算法也较为简单，当进程执行完毕时，根据进程页表中登记的页框号，将这些页框插入到存储页框表中，使之成为空闲页框，最后拆除该进程所对应的页表即可。

5.2页式地址变换

进程在运行期间，需要对程序和数据的地址进行变换，即将用户地址空间中的逻辑地址变换为内存空间中的物理地址，由于它执行的频率非常高，每条指令的地址都需要进行变换，因此需要采用硬件来实现。页表功能是由一组专门的寄存器来实现的。一个页表项用一个寄存器。

5.3快表

为提高地址转换速度，设置一个专用的高速存储器（Cache），用来存放页表的一部分，我们称这部分页表为快表。

有效访问时间(Effective Access Time，EAT)：假设λ表示查找快表所需时间，а表示命中率，t表示访问内存所需时间。

那么只用页表：EAT = t + t = 2t

引入快表后：EAT=а×λ+(t+λ)(1—а)+t=2t+λ—t×а

5.4虚拟页式存储器

1. 常规存储管理方式的特征

(1) 一次性：在作业运行前，要求将全部的内容一次性装入主存。

(2) 驻留性：作业装入主存后，一直占据主存的部分空间，一直要等作业运行结束。

2. 局部性原理

(1) 时间局限性。表现在如果程序中某一条指令一旦执行，则在不久以后还可能被继续执行，同样，若某一个数据被访问后不久，还可能被继续访问，其典型的情况是程序中存在着大量的循环。

(2) 空间局限性。表现在如果程序访问了某一个程序单元，其附近的存储单元则不久也会被访问，即程序在一段时间内访问的地址，可能集中在一定的范围内，其典型的情况是程序顺序执行。

3. 虚拟存储器的基本思想

基于局部性原理可知，应用程序在运行之前没有必要将之全部装入内存，而仅须将那些当前要运行的少数页面或段先装入内存便可运行，其余部分暂留在盘上。

4. 虚拟存储器的特征

(1) 多次性。用户程序在运行前并不是一次将全部内容装入到内存中，而是在程序的运行过程中，系统不断的对程序和数据部分的调入调出，完成程序的多处装入工作。

(2) 对换性。程序在运行期间，允许将暂时不用的程序和数据调出主存（换出），放入外存的对换区中，但以后需要时再将他调了主存（换入），这便是虚拟存储器的换入、换出操作。

5.4页式存储管理技术实现虚拟存储器

1.技术支持

(1)硬件支持：请求分页的页表机制、缺页中断机构、地址变换机构

(2)实现请求分页的软件

2.两级页表(Two-Level Page Table)

3.多级页表：对于32位的机器，采用两级页表结构是合适的，但对于64位及以上的机器，可能需要使用多级页表结构。

4.缺页中断机构：在页式虚拟存储系统中，每当要访问的页面不在内存时，便产生一个缺页中断，请求操作系统将所缺的页调入内存，此时应将缺页的进程阻塞，如果内存中有空闲块，则分配一个块，将要调入的页装入该块，并修改页表中相应的页表项，若此时内存中没有空闲块，只要淘汰某页。缺页中断与一般中断区别在于：(1) 在指令执行期间产生和处理中断信号。(2) 一条指令在执行期间可能产生多次缺页中断

5.地址变换机构：地址变换机构是在页式系统地址变换机构的基础上，为实现虚拟存储器，再增加了某些功能所形成的，如产生和处理缺页中断，以及从内存中换出一页的功能等等。

5.5页面置换

1.调页策略

(1) 预调页策略

预调页策略的优点在于，当在外存上查找一页时需经历较长时间，如果进程的许多页是存放在外存的一个连续区域中，一次调入若干相邻的页，要比每次调入一页更高效。
(2) 请求调页策略

当进程运行中需要访问某部分程序和数据，而其所在页面又不在主存时，立即提出请求，由系统将其所需页面调入主存，请求调页策略比较容易实现，故在目前的页式虚拟存储系统当中，大多采用此策略，也称之为请求分页系统。

2.分配策略

在请求分页系统中，可采取两种内存分配策略，即固定和可变分配策略。在进行置换时，也可采取两种策略，即全局置换和局部置换。于是可组合出以下三种适用的策略。

1) 固定分配局部置换(Fixed Allocation，Local Replacement)

2) 可变分配全局置换(Variable Allocation，Global Replacement)

3) 可变分配局部置换(Variable Allocation，Local Replacement)

3.缺页率

假设一个进程的逻辑空间为n页，系统为其分配的内存物理块数为m(m≤n)。如果在进程的运行过程中，访问页面成功(即所访问页面在内存中)的次数为S，访问页面失败(即所访问页面不在内存中，需要从外存调入)的次数为F，则该进程总的页面访问次数为A = S + F，那么该进程在其运行过程中的缺页率即为：

4. 页面置换算法

（1）最佳(Optimal)置换算法：最佳置换算法是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法通常可保证获得最低的缺页率。但由于人们目前还无法预知，一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，但可以利用该算法去评价其它算法。

发生缺页中断的次数为9，页面置换的次数为6，缺页中断率为：9/20=45%

（2）先进先出(FIFO)页面置换算法：该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。

发生缺页中断的次数为15，页面置换的次数为12，缺页中断率为：15/20=75%

（3） 最近最久未使用置换算法LRU

发生缺页中断的次数为12，页面置换的次数为9，缺页中断率为：12/20=60%

5.6虚拟页式存储管理系统的性能分析

（1）多道程序度与处理机的利用率

由于虚拟存储器系统能从逻辑上扩大内存，这时，只需装入一个进程的部分程序和数据便可开始运行，故人们希望在系统中能运行更多的进程，即增加多道程序度，以提高处理机的利用率。

（2）产生“抖动”的原因：同时在系统中运行的进程太多，由此分配给每一个进程的物理块太少，不能满足进程正常运行的基本要求，致使每个进程在运行时，频繁地出现缺页，必须请求系统将所缺之页调入内存。这会使得在系统中排队等待页面调进/调出的进程数目增加。显然，对磁盘的有效访问时间也随之急剧增加，造成每个进程的大部分时间都用于页面的换进/换出，而几乎不能再去做任何有效的工作，从而导致发生处理机的利用率急剧下降并趋于0的情况。我们称此时的进程是处于“抖动”状态。

4）“抖动”的预防方法

采取局部置换策略：在页面分配和置换策略中，如果采取的是可变分配方式，则为了预防发生“抖动”，可采取局部置换策略。

5.6段式及段页式存储管理

分页管理方式是从计算机的角度考虑设计的，以提高内存的利用率，提升计算机的性能，且分页通过硬件机制实现，对用户完全透明。

分段管理方式的提出则是考虑用户和程序员，以满足方便编程，信息保护和共享，动态增长以及动态链接等方多方面的需要。

■   段式存储管理

1. 分段

分段地址中的地址具有如下结构：

2. 段表

3. 地址变换机构

4. 信息共享和保护

      在分段系统中，由于是以段为基本单位的，不管该段有多大，我们都只需为该段设置一个段表项，因此使实现共享变得非常容易。我们以共享editor为例，此时只需在(每个)进程1和进程2的段表中，为文本编辑程序设置一个段表项，让段表项中的基址(80)指向editor程序在内存的起始地址。

5、段页式虚拟存储管理

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

■   基本原理：

■  地址映射：

■  地址变换过程：

■  分页管理和管理的比较分段