存贮器管理虚拟存贮器管理基本概念

1、会计学1存贮器管理虚拟存贮器管理基本概念存贮器管理虚拟存贮器管理基本概念 基基 本本 概概 念念 (1)为用户使用存贮器提供方便，这包含两个含义：一是，每个用户都以独立的方式编程，即用户只需在各自的逻辑空间内编程，而不必关心他的程序在内存空间上的物理位置；其次是，为用户提供充分大的存贮空间，使得用户程序的大小不受实际内存容量的限制，即用户不必关心内存空间的物理分配。 (2)充分发挥内存的利用率，既要为每个用户程序提供足够大的内存空间，使它们得以有效地运行，又要不浪费内存空间，在合理的前提下，让尽可能多的用户程序进驻内存运行。第1页/共84页.内存分配内存分配 （）静态分配：作业要求的内存空间是

2、在目标模块连接装入内存时确定并分配之，且在作业的整个运行过程中不允许再申请，即分配工作是在作业运行前一次性完成。 (2)动态分配：作业要求的基本内存空间是在目标模块装入时确定并分配的，但在作业运行过程中允许申请附加的内存空间，即分配工作可以在作业运行前及运行过程中逐步完成。第2页/共84页. 地址映射地址映射 高级语言或汇编语言程序形成的逻辑空间是符号名空间，其中的地址是符号地址。源语言程序经编译或汇编后产生的逻辑空间称之为该程序的地址空间，也叫虚空间。地址空间中的地址都是相对地址(相对于地址“0”)，称作逻辑地址。任一程序的地址空间都是以地址0起始的逻辑地址之集合，且可以是一维空间或二维空间

3、。不同程序的地址空间可以相同或局部重叠。整个内存 是个一维的物理空间，程序必须被装入内存才能执行。一程序在执行时所占用的存贮空间称作它的内存空间。一个内存空间是若干绝对地址(即物理地址)之集合，它是一维空间。显然，不同程序的内存空间不能冲突。第3页/共84页 逻辑地址是一个“虚”的概念，处理机不能直接访问逻辑地址，而物理地址则是“实”的。因而，操作系统必须提供这样的功能，把程序执行时要访问的地址空间中的逻辑地址变换成内存空间中对应的物理地址。这种把虚地址变换成实地址的过程称作地址映射。若用A表示地址空间，用M表示内存空间，则地址映射可表示成：f：第4页/共84页 (1)静态映射：地址映射是在程

4、序装入时一次性进行，由软机构一重定位装入程序完成。它把分配给二进制目标程序的内存区的起始地址B作为基地址，在把该程序装入指定内存区的同时，将程序中的所有逻辑地址翻译成相对于基地址B的物理地址，即（）这里a是地址空间中的任一逻辑地址，f(a)为a相应的物理地址。经静态映射后的程序便可在内存空间f(A)=M中执行了。第5页/共84页(2)动态映射：图图- 动态地址映射动态地址映射第6页/共84页 3内存保护内存保护 保护为多个程序共存内存提供保证，有共存才需要保护，有保护才能正确地实现共存。内存保护就是为各程序的内存空间提供保护，以防他人侵犯。内存分配和地址映射不能完全解决保护问题，必须在程序执行

5、时随机检查对内存的所有访问，以保证各个程序都在自己所属的内存空间里工作，互不干扰，特别是要防止用户程序侵犯操作系统的内存区。第7页/共84页 内存扩充内存扩充 内存容量总是有限的。为了既满足大作业的存贮需求，又能实现在内存中存放尽可能多的用户程序，给它们分配得以有效运行的足够的内存空间，从而充分发挥整个系统的效率，比较高级的计算机系统，特别是中、大型的通用计算机系统通常都需要扩充内存。这种扩充不是物理的增大内存容量，而是对内存空间的逻辑扩充，即通过软件方法将内存空间扩充成比实际容量更大的逻辑存贮空间。虚拟存贮器是广泛采用且有效的内存扩充技术。第8页/共84页 分分 区区 管管 理理 (1) 首

6、次适应算法FF(First Fit) (2) 最佳适应算法BF(Best Fit） (3) 最坏适应算法WF(Worst Fit)第9页/共84页. 固定分区管理固定分区管理图- 固定分区例第10页/共84页. 可变分区概念可变分区概念图图- 可变分区示例可变分区示例第11页/共84页. 可变分区分配可变分区分配图- 双向空区链结构第12页/共84页 .分配程序分配程序 本程序的调用参数是请求容量（字节数），返回参数为所分配的分区起始地址，若，则表示分配失败。常量为规定的空闲区最小容量值，如果所选择的空闲区的容量大于请求容量，且剩余空间大于，则该剩余部分作为较小的空闲区仍留在空区链中，否则一起

7、分配之。第13页/共84页第14页/共84页第15页/共84页. 回收程序回收程序 回收一个分区的主要工作是：检查回收区是否有邻接空闲区，若有则进行合并 ，否则将回收区插入空区链中的适当位置。一个回收区邻接空闲区的情况有三 种，对它们分别处理：回收区的前邻是空闲区，合并后仍为空闲区 ，其起址不变，但其大小为原容量与的容量之和；回收区的的后邻是空闲区，合并后变成，的起址是的起址，的大小为与的容量之和；回收区的前后邻均是空闲区，设为和，把从链中删除，但保留，1的起址不变，其大 小再加上和的容量。第16页/共84页第17页/共84页第18页/共84页第19页/共84页第20页/共84页. 地址映射与

8、保护地址映射与保护图- 分区管理的地址映射与保护第21页/共84页 覆覆 盖盖 与与 交交 换换. 覆盖覆盖 所谓覆盖（）是指同一内存区可以被不同的程序段重复使用，这些相对独立的程序段可以属于同一作业，也可以是不同作业的。当某程序段 不再需要时，另一程序段可以占用它的位置。把可以在其上进行覆盖的内存区 称为“覆盖区”，而可以相互覆盖的程序段称为“覆盖”。第22页/共84页图- 覆盖示例第23页/共84页图4-7 分页管理的地址映射及保护第24页/共84页 我们用的提供的覆盖描述语言来描述图-给出的覆盖结 构，它可表示为 （，（，）其中，说明是根段，同一覆盖段中各覆盖之间用逗号分隔， 并括在同一

9、括号内，表示结束行。命令行构成一个覆盖描述文件。第25页/共84页. 交换交换 无论是哪一种交换式存贮管理都涉及到下述三个问题： （）对需换进的进程分配的内存空间必须是它原先占据过的空间，或者允许分配一个新的空间。 （）对进程实体是整体还是部分交换。 （）关于交换时间。第26页/共84页 对于采用交换技术的分时系统，交换时间是影响时间片设置的因素之一。为了有效利用，时间片值一般应大于交换时间。例如 ，若外存是标准的硬磁盘，其传输率为兆字节秒，平均寻址定位时间是，又假定用户进程实体的平均大小为 字节，则换进或换出一个进程 的平均时间为：msmssmssKK588)20/ 1 (8)1000/50

10、(第27页/共84页 分分 页页 管管 理理. 实现原理实现原理 系统将作业地址空间划分成一些大小相等的块，称之为“页”。设地址空间有页，则这页被顺序编号为、，称之为页号，这是相对页号。每个页内部相对于连续编址，即页内是连续的。于是作业地址空间构成一个二维地址空间，其中的任一逻辑地址都表示成有序偶（，），其中是页号，是页内位移量即相对地址。第28页/共84页 同样，系统将内存空间也分成大小与页相等的若干块，称为内存块，简称“块”。通常，页长总是取的整数次幂，例如为或等等 。设内存空间的容量为，页长为r，则内存共划分成块，这块从低地址开始依次编号为、，称之为块号，这是绝对块号。 假定机器地址部分

11、有位，若规定页长为，则地址的高位为页号，低位为位移量，页 号位 移 量18980第29页/共84页图- 利用快表的分页地址映射第30页/共84页. 数据结构与存贮分配数据结构与存贮分配 （）内存分块表 整个系统一个，用以记录所有内存块的使用情况，表目数等于内存块总数，各内存块按序对应一个表目，表目号即块号。表目项可以是占用者名和页号。 若则表示该块为空闲块，记录该块被分配后所对应的地址空间中的页号。第31页/共84页 （）页表 每个用户进程一个，用以记录进程实体的地址空间与内存空间的映射关系。地址空间中的各页按序对应页表中的一个表目，表目号等于页号，表长等于页数。在一些分页系统中，为了便于管理

12、，每个页表的长度是相等的，于是全部页表被构成一个二维数组，为页表个数，它等于用户进程的最大个数，是规定的页表最大长度。若有，表示第号页表为空闲。进程的中记录着相应页表的起始地址和表长。当进程调度程序启动某个进程执行时，将该进程中的页表始址和表长装入页表控制器。第32页/共84页 （）计数变量freeblocks 它记录当前空闲块的数目。 、及freeblocks均放在系统区。分配程序的调用参数为申请者名name和申请长度x（以字节计）；返回参数是页表的起始地址和实际长度（实际表目数），若分配失败，则；常量pagesize是规定页长（字节数）。回收程序的调用参数是页表的始址和实际长度。第33页/

13、共84页第34页/共84页第35页/共84页. 关于碎片关于碎片 碎片量取决于两个因素： （）块或页的大小。直观上，块越小内碎片越小，但这要增加系统的其他开销，比如页表增长就要占用更多的内存空间，在实现虚存的请求分页系统中还要增加内外存交换次数。许多分页系统都取页长为 字，如 和及n-等。但近来的文献资料表明，对页长有取较小的趋势，如和取字，取字。第36页/共84页 (2) 内存中同时运行的作业数J。设系统把用户内存区划分成m块，则碎片率约为（）。 例如，设，用户区为兆字节且被划分成 块，即块长为 ，于是该系统的最大碎片率约为（ ）.，故最大碎片量约为.兆字节 字节。第37页/共84页 分分

14、段段 管管 理理 分页技术有效地实现了内存分配的非连续性，解决了碎片问题，从而大大提高了内存利用率。但是对用户作业地址空间进行分页，使之从一个一维地址空间变成二维地址空间是完全由系统进行的。这种分页并不是依据作业内在的逻辑关系，而是对连续的地址空间的一种固定长度的连续划分。一页通常不是一个完整的程序或数据逻辑段。一个逻辑段可能被分成若干页，不同的逻辑段也可能在同一页内。本质上，作业地址空间仍然是从开始顺序编址的线性地址空间，它没有明显的逻辑结构关系。因此，分页并不是出于用户使用上的需要，它对用户是透明的，而是系统出于管理上的需要，目的是使作业地址空间与内存空间的管理在结构上一致。第38页/共8

15、4页. 实现实现原理原理图- 分段管理的地址映射及保护第39页/共84页 系统为每个运行作业在内存建立一张段映射表（ ），简称段表。根据作业的分段数，段表建有个表目 ，表目序号对应于段号，每个表目包含“段长”和“内存起始地址”两项。 系统还设置一个公共的段表控制寄存器，作业进程进入执行时，系统将它的段表内存地址及表长装入。每当进程访问逻辑地址（，）时，分段地址映射机构自动完成如下工作：第40页/共84页 比较段号和段表长： 若，则为非法访问，发出越界中断。 若，则根据，找到段在段表中的相应表目，然后，检查位移量是否超过段长，超过则发越界中断；否则将段的内存起始地址加上，形成物理地址。段号段长内

16、存起址访问值状态第41页/共84页. 分段与分页的区别分段与分页的区别 （）段是信息的逻辑单位，分段是出于作业逻辑上的要求，对用户来说，分段是可见的；页是信息的物理单位，分页并不是用户作业的要求，而仅仅是为了系统管理内存的方便，分页活动对用户是不可见的。 （）页的大小固定，由系统决定；段的大小不固定，由用户决定。 （）把逻辑地址分解成页号和页内位移量是机器硬件的功能，而定义成段号和段内位移量是由用户决定的，故页内没有地址越界问题，而段内位移量存在地址越界问题。 （）从用户角度，分页的地址空间是个一维地址空间，而分段的地址空间则是二维地址空间。第42页/共84页. 分段与分页的共享分段与分页的共

17、享图- 段的共享 第43页/共84页 图- 页的共享第44页/共84页 段段 页页 式式 管管 理理图图-12 段页式管理的数据结构与存贮分配段页式管理的数据结构与存贮分配第45页/共84页图- 段页式管理的地址映射及保护第46页/共84页 虚拟存贮器管理基本概念虚拟存贮器管理基本概念 （）一级存贮器概念。虚存管理系统把大容量的外存作为内存的直接延伸，对内存和外存实施统一的管理，使这两级存贮器变成面向用户的、逻辑上可统 一编址的虚拟内存空间。因此，用户作业的大小可不受实际内存容量的严格限制。从用户角度，系统提供了一个使用方便的、海量的一级存贮器。第47页/共84页 （）作业地址空间概念。一个作

18、业的地址空间就是一个虚拟存贮器，每个作业都处于各自的虚存中，虚存中统一编址。一个虚地址可能被映射成内存地址 ，也可能被映射外存地址，即一个作业虚存可能被装配成内存空间和外存空间两部分。但这对用户是透明的，用户亦不必关心虚、实地址之间的实际映射。第48页/共84页 虚拟并不是无限的，它主要取决于具体机器的地址结构。例如，若的地址结构长度为位，则虚存空间中可寻址的范围从到，即虚存最大容量为 ；若地址为位，则虚存最大容量为 。当然，虚存是不能大于外存容量的。 虚拟存贮管理策略考虑的出发点是基于程序局部性原理在一段时间内，一 个程序的执行往往呈现出高度的局部性，它对内存的访问是很不均匀的。局部性又表现

19、为时间局部性和空间局部性。第49页/共84页 时间局部性时间局部性 是指一旦某个位置被访问了，那么它往往很快要再次被访问。我们在程序设计中经常使用的循环、子程序、堆栈、计数或累积变量等程序结构都反映了这个特性。 空间局部性空间局部性 是指一旦某个位置被访问了，那么它附近的位置很可能也要立即被访问。程序代码的顺序执行，对线性数据结构的访问或处理，以及程序中往往把常用变量存放在一起等都反映出该特性。第50页/共84页 （）作业中的某些程序段在作业的整个运行过程中可能根本就不用它。例如出错处理程序仅当数据或计算处理出错时才会用到，而在作业的正常运行情况下，没有必要把它调入内存。 （）许多表格占用固定

20、数量的内存空间，而事实上只用到其中一部分。 （）许多程序段是顺序执行的，还有一些程序段是互斥执行的，在一些运行活动中只可能用到其中之一，它们没有必要同时驻留在内存。 （）在作业的一次运行中，有些程序段执行之后，从某个时刻起不再用到。第51页/共84页 一个作业进程在某段时间内只需当前需要的局部实体存在内存便可执行局部性；在进程运行过程中，当前暂不使用的或今后不再使用的那部分实体可以换出内存， 若以后需要时再换进内存交换性； 作业进程所占据的内存空间可不必完全连续，只需局部的或分段连续离散性。可见，这是对整体性、驻留性及连续性的否定。需要指出的是，这里的交换性显然是指部分交换，而非整体交换。第5

21、2页/共84页 局部性、交换性和离散性是虚拟存贮器管理的基本思想，下面是基于这三种思想而提出的三种虚存管理策略： （）调入策略 （）分配策略 （）淘汰策略 第53页/共84页 请求分页管理请求分页管理. 请求调入及缺页中断处理请求调入及缺页中断处理驻留位内存块号外存地址控制信息虚页号第54页/共84页图- 缺页中断处理第55页/共84页. 淘汰算法淘汰算法. 先进先出算法先进先出算法 顾名思义，（ ）算法的出发点是先进内存者先被淘汰，即选择在内存中驻留时间最长的一页淘汰之。理由是，最早调入的页在近期不再被使用的可能 性要大于最近调入 的页。实现这种算法的基本方法是，为调入内存的每一页以递增方式

22、标明调入次序，淘汰时选择次序值最小的那一页，或者建立一个先进先出队列，总是淘汰队首的那一第56页/共84页图- 异常现象第57页/共84页 . 最近最少使用算法最近最少使用算法 （ ）算法所依据的理由是：在发生本次缺页中断之前的最近一段时间内未被使用的时间最长的实页，在最 近的将来被使用的可能性最小，故可淘汰之。 最少使用算法（ ）是的一种近似算法。它所关心的是每一实页被使用的频繁程度，选择淘汰的是最近一段时间内访问次数最少的页。第58页/共84页 假定系统给每个用户进程至多分配个内存实页，于是设置个公共的位寄存器，（，），称为访问寄存器。它们记录现行进程的访页情况。在进程的中保留有这个寄存器

23、的值，每个对应该进程的一个内存实页，实页的相对实页号为，亦即在快表中的相应表目号。当进程调度选中某个进程执行时，将其中的各访问寄存器的保留值装入访问寄存器中。在进程执行过程中，每当访问第个实页时，便置，为，每隔时间将个Rk均右移一位。当需要淘汰时，LRU算法选择的是相应的Rk值为最小的实页，而LFU算法选择的是10.njjkR的值为最小的实页。第59页/共84页第60页/共84页 . 最近未使用算法最近未使用算法 （ ）是一种最为流行的、低开销的近似算法。它所依据的理由是：在最近一段时间内未使用过的实页在最近的将来不大可能被使用。在具体实现中，系统为每个实页增加两个硬件位（逻辑上可以认为它们被

24、设置在页表和快表中）：第61页/共84页 设置修改位的意义在于，如果被淘汰的页没被修改过，由于每页在外存都有副本，因此不必把它再写回外存，否则必须写回外存。显然最好的选择是淘汰没修改过的页，这样可以减少系统开销。初始时，所有实页的引用位和修改位都置为，当访问某页时，该页的引用位置为，一旦修改了某页，便置其修改位为。当要淘汰时按下列页类的次序选择： 类：未引用过，未修改过 类：未引用过，修改过 类：引用过，未修改过 类：引用过，修改过第62页/共84页 首先选择类实页进行淘汰，然后次之。为了避免到某一时刻大多数甚至所有实页的引用位都为，从而无法区别哪一页最应该被淘汰，系统需要周期性地（设周期为）

25、将所有引用位都置。问题是的大小不易选定，太大所有引用位可能都为；太小，引用位为的页可能相当多，这样就很难确定哪一页是最近未使用的页。第63页/共84页. 抖动与工作集抖动与工作集 抖动现象与内存中并发的用户进程数以及系统分配给每个进程的实页数有关。图- 利用率曲线第64页/共84页 图- 进程的缺页率曲线第65页/共84页 所谓工作集（ ），粗略地说，是进程在某个时间段里要访问的页集合。 把一个进程在时间到这个时间段所访问的页集合称为该进程在时间的工作集，记为（，），变量称为“工作集窗口尺寸”。 工作集尺寸即工作集所含的页数，记为。第66页/共84页图- 是的函数第67页/共84页 进程的初始

26、工作集是无法确定的。通常，一进程在初始装入内存时，系统为其分配个实页，是该进程虚存空间所含总页数，是系统规定的比例系数，。然后将该进程虚存空间中页号最小的页装入内存（一般规定主程序从第页开始），并将诸页的引用位清。在进程执行过程中，若发生缺页则调进该页，每当访问一实页时，便将该页的引用位置，到 时刻1时，淘汰所有引用位为的实页，而将引用位为的诸页作为时刻的工作集（，）并将这些页的引用位重新清，到时刻便可获得新的工作集。第68页/共84页图4-20 工作集形成第69页/共84页 例如 设B内存用户区总实页数，Vi是运行进程Pi的虚存总页数，Mi是Pi的初始工作集尺寸，Mi=aVi,也称标准工作集

27、尺寸。为了保证各进程能够在工作集上有效运行，系统应维持 。于是，第70页/共84页10 动态分段管理动态分段管理 动态分段管理提供了段式虚拟存贮器。每个作业存于一个虚拟存贮器中，虚拟存贮器与内存之间的映射由段表来实现。段表的表目结构为：驻留位段长内存地址外存地址控制信息虚页号第71页/共84页10.1 管理策略管理策略图- 缺段中断处理第72页/共84页. 段的动态连接段的动态连接图- 间接寻址与间接字第73页/共84页 连接标志，表示直接地址不在本段中，要进行连接；，则仅作间接地址处理。在图-中，一源程序的主段中用符号名对另一段进行访问，例如“，”，这里是段名，是地址标号，汇编程序将其翻译成一条间接寻址指令“，”，其中是的段号，是存放间接字的直接地址，该间接字中，并指向单元，那里存放连接地址的符号名“”。第74页/共84页图- 段的动态连接示例第75页/共84页 基基 本本 概概 念念 (1)为用户使用存贮器提供方便，这包含两个含义：一是，每个用户都以独立的方式编程，即用户只需在各自的逻辑空间内编程，而不必关心他的程序在内存空间上的物理位置；其次是，为用户提供充分大的存贮空间，使得用户程序的大小不受实际内存容量的限制，即用户不必关心内存空间的物理分配。 (2)充分发挥内存的利用率，既要为每个用户程序提供足够大的内存空间，使它们得以有效地运行，又要不浪费