|
|
|
存储管理是操作系统的重要组成部分，它负责管理计算机系统的重要资源——主存储器。由于任何程序、数据必须占用主存空间后才能执行，因此存储管理直接影响系统的性能。主存储空间一般分为两部分：一部分是系统区，存放操作系统以及一些标准子程序，例行程序等；另一部分是用户区，存放用户的程序和数据等。存储管理主要是对主存储器中的用户区域进行管理，当然也包括对辅存储器的管理。目的是要尽可能地方便用户使用和提高主存储器的效率。具体地说，存储管理有下面几个方面的功能。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
目前，计算机系统均采用分层结构的存储子系统，以便在容量大小、速度快慢、价格高低诸因素中取得平衡点，获得较好的性能价格比。计算机系统的存储器可以分为寄存器、高速缓存、主存储器、磁盘缓存、固定磁盘、可移动存储介质等7个层次结构。如下图所示，越往上，存储介质的访问速度越快，价格也越高。其中，寄存器、高速缓存、主存储器和磁盘缓存均属于操作系统存储管理的管辖范畴，掉电后它们存储的信息不再存在。固定磁盘和可移动存储介质属于设备管理的管辖范畴，它们存储的信息将被长期保存。而磁盘缓存本身并不是一种实际存在的存储介质，它依托于固定磁盘，提供对主存储器存储空间的扩充。
|
|
|
|
|
|
|
|
可执行的程序必须被保存在计算机的主存储器中，与外围设备交换的信息一般也依托于主存储器地址空间。由于处理器在执行指令时主存访问时间远大于其处理时间，寄存器和高速缓存被引入以加快指令的执行。
|
|
|
|
寄存器是访问速度最快但最昂贵的存储器，它的容量小，一般以字（word）为单位。一个计算机系统可能包括几十个甚至上百个寄存器，用于加速存储访问速度，如寄存器存放操作数，或用地址寄存器加快地址转换速度。
|
|
|
|
高速缓存的容量稍大，其访问速度快于主存储器，利用它存放主存中一些经常访问的信息可以大幅度提高程序执行速度。
|
|
|
|
由于程序在执行和处理数据时存在顺序性、局部性、循环性和排他性，因此在程序执行时有时并不需要把程序和数据全部调入内存，而只需先调入一部分，待需要时逐步调入。这样，计算机系统为了容纳更多的算题数，或是为了处理更大批量的数据，就可以在磁盘上建立磁盘缓存以扩充主存储器的存储空间。算题的程序和处理的数据可以装入磁盘缓存，操作系统自动实现主存储器和磁盘缓存之间数据的调进调出，从而向用户提供了比实际主存存储容量大得多的存储空间。
|
|
|
|
|
|
用户编写应用程序时，是从0地址开始编排用户地址空间的，把用户编程时使用的地址称为逻辑地址（相对地址）。而当程序运行时，它将被装入主存储器地址空间的某些部分，此时程序和数据的实际地址一般不可能同原来的逻辑地址一致，把程序在内存中的实际地址称为物理地址（绝对地址）。相应地构成了用户编程使用的逻辑地址空间和用户程序实际运行的物理地址空间。
|
|
|
|
为了保证程序的正确运行，必须把程序和数据的逻辑地址转换为物理地址，这一工作称为地址转换或重定位。地址转换有两种方式，一种方式是在作业装入时由作业装入程序实现地址转换，称为静态重定位；另一种方式是在程序执行时实现地址转换，称为动态重定位。动态重定位必须借助于硬件的地址转换部件实现。
|
|
|
|
|
|
分区存储管理的基本思想是给进入主存的用户进程划分一块连续存储区域，把进程装入该连续存储区域，使各进程能并发执行，这是能满足多道程序设计需要的最简单的存储管理技术。
|
|
|
|
|
|
固定分区（fixed partition）存储管理如下图所示，是预先把可分配的主存储器空间分割成若干个连续区域，每个区域的大小可以相同，也可以不同。
|
|
|
|
|
|
|
|
为了说明各分区的分配和使用情况，存储管理需设置一张“主存分配表”，该表如下图所示。
|
|
|
|
|
|
|
|
主存分配表指出各分区的起始地址和长度，表中的占用标志位用来指示该分区是否被占用了，当占用的标志位为“0”时，表示该分区尚未被占用。进行主存分配时总是选择那些标志为“0”的分区，当某一分区分配给一个作业后，则在占用标志栏填上占用该分区的作业名，如下图所示，第2、5分区分别被作业Jobl和Job2占用，而其余分区为空闲。
|
|
|
|
|
|
可变分区（Variable Partition）存储管理是按作业的大小来划分分区。系统在作业装入主存执行之前并不建立分区，当要装入一个作业时，根据作业需要的主存量查看主存中是否有足够的空间，若有，则按需要量分割一个分区分配给该作业；若无，则令该作业等待主存空间。由于分区的大小是按作业的实际需要量来定的，且分区的个数也是随机的，所以可以克服固定分区方式中的主存空间的浪费，有利于多道程序设计，实现了多个作业对内存的共享，进一步提高了内存资源利用率。
|
|
|
|
随着作业的装入、撤离，主存空间被分成许多个分区，有的分区被作业占用，而有的分区是空闲的。当一个新的作业要求装入时，必须找一个足够大的空闲区，把作业装入该区，如果找到的空闲区大于作业需要量，则作业装入后又把原来的空闲区分成两部分，一部分被作业占用了；另一部分又分成为一个较小的空闲区。当一个作业运行结束撤离时，它归还的区域如果与其他空闲区相邻，则可合成一个较大的空闲区，以利于大作业的装入。采用可变分区方式的主存分配示例如下图所示。
|
|
|
|
|
|
|
|
|
|
（1）最先适用分配算法：对可变分区方式可采用最先适用分配算法，每次分配时，总是顺序查找未分配表或链表，找到第一个能满足长度要求的空闲区为止。分割这个找到的未分配区，一部分分配给作业，另一部分仍为空闲区。这种分配算法可能将大的空间分割成小区，造成较多的主存“碎片”。作为改进，可把空闲区按地址从小到大排列在未分配表或链表中，于是为作业分配主存空间时，尽量利用了低地址部分的区域，而可使高地址部分保持一个大的空闲区，有利于大作业的装入。
|
|
|
|
（2）最优适应分配算法：可变分区方式的另一种分配算法是最优适应分配算法，它是从空闲区中挑选一个能满足作业要求的最小分区，这样可保证不去分割一个更大的区域，使装入大作业时比较容易得到满足。采用这种分配算法时可把空闲区按长度以递增顺利排列，查找时总是从最小的一个区开始，直到找到一个满足要求的分区为止。按这种方法，在回收一个分区时也必须对分配表或链表重新排列。
|
|
|
|
（3）最坏适应分配算法：最坏适应分配算法是挑选一个最大的空闲区分割给作业使用，这样可使剩下的空闲区不至于太小，这种算法对中、小作业是有利的。
|
|
|
|
|
|
|
|
用分区方式管理的存储器，每道程序总是要求占用主存的一个或几个连续存储区域，作业或进程的大小仍受到分区大小或内存可用空间的限制，因此，有时为了接纳一个新的作业而往往要移动已在主存的信息。这不仅不方便，而且开销不小。采用分页存储器既可免去移动信息的工作，又可尽量减少主存的碎片。分页式存储管理的基本原理如下：
|
|
|
|
（1）页框：物理地址分成大小相等的许多区，每个区称为一块（又称页框Page Frame）。
|
|
|
|
（2）页面：逻辑地址分成大小相等的区，区的大小与块的大小相等，每个区称一个页面（page）。
|
|
|
|
（3）逻辑地址形式：与此对应，分页存储器的逻辑地址由两部分组成（页号和单元号）。逻辑地址格式如下：
|
|
|
|
|
|
采用分页式存储管理时，逻辑地址是连续的。所以，用户在编制程序时仍只需使用顺序的地址，而不必考虑如何去分页。由地址结构和操作系统管理的需要来决定页面的大小，从而，也就确定了主存分块的大小。用户进程在内存空间中每个页框内的地址是连续的，但页框和页框之间的地址可以不连续。存储地址由连续到离散的变化，为以后实现程序的“部分装入、部分对换”奠定了基础。
|
|
|
|
（4）页表和地址转换：在进行存储分配时，总是以块（页框）为单位进行分配，一个作业的信息有多少页，那么在把它装入主存时就给它分配多少块。但是，分配给作业的主存块可以是不连续的，即作业的信息可按页分散存放在主存的空闲块中，这就避免了为得到连续存储空间而进行的移动。那么，当作业的程序和数据被分散存放后，作业的页面与分给的页框如何建立联系呢？页式虚拟地址如何变换成页框物理地址呢？作业的物理地址空间由连续变成分散后，如何保证程序正确执行呢？采用的办法是动态重定位技术，让程序的指令执行时作地址变换，由于程序段以页为单位，所以，给每个页设立一个重定位寄存器，这些重定位寄存器的集合便称为页表（Page Table）。页表是操作系统为每个用户作业建立的，用来记录程序页面和主存对应页框的对照表，页表中的每一栏指明了程序中的一个页面和分得的页框的对应关系。通常为了减少开销，不是用硬件，而是在主存中开辟存储区存放页表，系统中另设一个页表主存起址和长度控制寄存器（Page Table Control Register）,存放当前运行作业的页表起址和页表长，以加快地址转换速度。每当选中作业运行时，应进行存储分配，为进入主存的每个用户作业建立一张页表，指出逻辑地址中页号与主存中块号的对应关系，页表的长度随作业的大小而定。同时页式存储管理系统还建立一张作业表，将这些作业的页表进行登记，每个作业在作业表中有一个登记项。作业表和页表的一般格式如下图所示。然后，借助于硬件的地址转换部件，在作业执行过程中按页动态定位。调度程序在选择作业后，从作业表的登记项中得到被选中作业的页表始址和长度，将其送入硬件设置的页表控制寄存器。地址转换时，就可以从页表控制寄存器中找到相应的页表，再以逻辑地址中的页号为索引查页表，得到对应的块号，根据关系式：
|
|
|
|
|
|
|
|
|
|
计算出欲访问的主存单元的地址。因此，虽然作业存放在若干个不连续的块中，但在作业执行中总是能按正确的地址进行存取。
|
|
|
|
|
|
页表可以存放在一组寄存器中，地址转换时只要从相应寄存器中取值就可得到块号，这虽然方便了地址转换，但硬件花费代价太高，如果把页表放在主存中就可降低计算机的成本。但是，当要按给定的逻辑地址进行读／写时，必须访问两次主存。第一次按页号读出页表中相应栏内容的块号，第二次根据计算出来的绝对地址进行读／写，降低了运算速度。
|
|
|
|
为了提高运算速度，通常都设置一个专用的高速存储器，用来存放页表的一部分，这种高速存储器称为相联存储器（Associative Memory）,存放在相联存储器中的页表称为快表。相联存储器的存取时间是远小于主存的，但造价高，故一般都是小容量的，例如Intel 80486的快表为32个单元。
|
|
|
|
根据程序执行局部性的特点，即它在一定时间内总是经常访问某些页，若把这些页登记在快表中，无疑将大大加快指令的执行速度。快表的格式如下：
|
|
|
|
|
|
它指出已在快表中的页及其对应主存的块号。有了快表后，绝对地址形成的过程是，按逻辑地址中的页号查快表，若该页已登记在快表中，则由块号和单元号形成绝对地址；若快表中查不到对应页号，则再查主存中的页表而形成绝对地址，同时将该页登记到快表中。当快表填满后，又要在快表中登记新页时，则需在快表中按一定策略淘汰一个旧的登记项，最简单的策略是“先进先出”，总是淘汰最先登记的那一页。
|
|
|
|
采用相联存储器的方法后，地址转换时间大大下降。假定访问主存的时间为100×10-9s，访问相联存储器的时间为20×10-9s，相联存储器为32个单元时查快表的命中率可达90%，于是按逻辑地址进行存取的平均时间为：
|
|
|
|
（100+20）×90%+（100+100+20）×（1-90%）=130×10-9s
|
|
|
|
比两次访问主存的时间100×10-9s×2+20×10-9s=220×10-9s下降了四成多。
|
|
|
|
同样，整个系统也只有一个相联存储器，只有占用CPU者才占有相联存储器。在多道程序中，当某道程序让出处理器时，应同时让出相联存储器。由于快表是动态变化的，所以让出相联存储器时应把快表保护好以便再执行时使用。当一道程序占用处理器时，除置页表控制寄存器外还应将它的快表送入相联存储器。
|
|
|
|
|
|
分段式存储管理是以段为单位进行存储分配，为此提供如下形式的两维逻辑地址：
|
|
|
|
|
|
在分页式存储管理中，页的划分——即逻辑地址划分为页号和单元号是用户不可见的，连续的用户地址空间将根据页框架（块）的大小自动分页；而在分段式存储管理中，地址结构是用户可见的，即用户知道逻辑地址如何划分为段号和单元号，用户在程序设计时，每个段的最大长度受到地址结构的限制，进一步，每一个程序中允许的最多段数也可能受到限制。例如，PDP-11/45的段址结构为：段号占3位，单元号占13位，也就是一个作业最多可分8段，每段的长度可达8KB。
|
|
|
|
分段式存储管理的实现可以基于可变分区存储管理的原理，为作业的每一段分配一个连续的主存空间，而各段之间可以不连续。在进行存储分配时，应为进入主存的每个用户作业建立一张段表，各段在主存的情况可用一张段表来记录，它指出主存储器中每个分段的起始地址和长度。同时段式存储管理系统包括一张作业表，将这些作业的段表进行登记，每个作业在作业表中有一个登记项。作业表和段表的一般格式如下图所示。
|
|
|
|
|
|
|
|
段表表目实际上起到了基址／限长寄存器的作用。作业执行时通过段表可将逻辑地址转换成绝对地址。由于每个作业都有自己的段表，地址转换应按各自的段表进行。类似于分页存储器那样，分段存储器也设置一个段表控制寄存器，用来存放当前占用处理器的作业的段表始址和长度。段式存储管理的地址转换和存储保护流程如下图所示。
|
|
|
|
|
|
|
|
|
|
在前面介绍的各种存储管理方式中，必须为作业分配足够的存储空间，以装入有关作业的全部信息，当然作业的大小不能超出主存的可用空间，否则这个作业是无法运行的。但当把有关作业的全部信息都装入主存储器后，作业执行时实际上不是同时使用全部信息的，有些部分运行一遍便再也不用，甚至有些部分在作业执行的整个过程中都不会被使用到（如错误处理部分）。进程在运行时不用的，或暂时不用的，或某种条件下才用的程序和数据，全部驻留于内存中是对宝贵的主存资源的一种浪费，大大降低了主存利用率。于是，提出了这样的问题：作业提交时，先全部进入辅助存储器，作业投入运行时，能否不把作业的全部信息同时装入主存储器，而是将其中当前使用部分先装入主存储器，其余暂时不用的部分先存放在作为主存扩充的辅助存储器中，待用到这些信息时，再由系统自动把它们装入到主存储器中，这就是虚拟存储器的基本思路。如果“部分装入、部分对换”这个问题能解决的话，那么当主存空间小于作业需要量时，这个作业也能执行；更进一步，多个作业存储总量超出主存总容量时，也可以把它们全部装入主存，实现多道程序运行。这样，不仅使主存空间能充分地被利用，而且用户编制程序时可以不必考虑主存储器的实际容量，允许用户的逻辑地址空间大于主存储器的绝对地址空间。对于用户来说，好像计算机系统具有一个容量很大的主存储器，把它称做为“虚拟存储器”（Virtual Memory）。
|
|
|
|
对虚拟存储器的定义如下：具有部分装入和部分对换功能，能从逻辑上对内存容量进行大幅度扩充，使用方便的一种存储器系统。实际上是为扩大主存而采用的一种设计技巧。虚拟存储器的容量与主存大小无关。虚拟存储器的实现对用户来说是感觉不到的，他们总以为有足够的主存空间可容纳他的作业。
|
|
|
