存储管理是指存储器资源

1、会计学1存储管理是指存储器资源存储管理是指存储器资源外存(secondary storage)DOS核心命令处理程序内存(primary storage)快速缓存(cache)寄存器(register)内存分配按分配的时机不同，可分为静态存储方式和动态存储方式。静态存储分配：指内存分配是在作业运行之前各目标模块连接后，把整个作业一次性全部装入内存，并在作业运行过程中，不允许作业再申请其它内存空间，或是在内存中移动位置。内存分配在作业运行前一次性完成。模块 AC AL L B ；R eturn；0L 1模块 BC AL L C ；R eturn；0M 1模块 CR eturn；0N 10模块 A

2、JSR “L ”R eturn；L 1模块 BJSR “L M ”R eturn；LL M 1L ML M N 1模块 CR eturn；( a ) 目标模块( b ) 装入模块返回逻辑地址、物理地址和地址映射地址映射地址映射BA=1000Mov R1 200 3456 。 。 。1200物理地址空间物理地址空间Mov R1, data3456源程序源程序Mov R1 200 34560100200编译连接编译连接逻辑地址空间逻辑地址空间地址映射3000100200.Mov R1 2003456逻辑地址空间逻辑地址空间100012001300物理地址空间物理地址空间200VR+1000BRMo

3、v R1 120011003456地址重定位分为：静态地址重定位和动态地址重定位。静态地址重定位：在可执行文件中，列出各个需要重定位的地址单元和相对地址值。当用户程序被装入内存时，一次性实现逻辑地址到物理地址的转换，以后不再转换（一般在装入内存时由软件完成）。即：装入时根据所定位的内存地址去修改每个重定位地址项，添加相应偏移量。可执行文件在内存中的重定位o说明：重定位表中列出所有修改的位置。如：重定位表的150表示相对地址150处的内容为相对地址(即100为从0起头的相对位置)。在装入时，要依据重定位后的起头位置(2000)修改相对地址。n重定位修改：重定位表中的150-绝对地址2150(=2

4、000+150)n内容修改：内容100变成2100(=100+2000)。jmp150100150.RelocationTable0jmp215021002150.2000动态重定位动态重定位 动态运行时的装入程序，在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行,通过硬件机构来完成，硬件机构一般采用的是重定位寄存器，完成虚拟地址到实际内存地址的变换。因此， 装入内存后的所有地址都仍是相对地址。 动态重定位的实现动态重定位的实现 在每次进行存储器访问时，对取出的逻辑地址加上重定位寄存在每次进行存储器访问时，对取出的逻辑地址加上

5、重定位寄存器的内容，形成内存地址，重定位寄存器的内容是程序装入内器的内容，形成内存地址，重定位寄存器的内容是程序装入内存的起始地址。存的起始地址。LOAD1,25003650100250050002500相对地址10000重定位寄存器LOAD1,250036510000101001250015000作业J主存返回1. 问题的引出 返回2. 虚拟存储的基本原理3. 虚拟存储器定义虚拟存储器定义 所谓虚拟存储器， 是指具有请求调入功能和置换功能,能从逻辑上对内存容量加以扩充的一种存储器系统。其运行速度接近于内存速度，而每位的成本却又接近于外存。可见，虚拟存储技术是一种性能非常优越的存储器管理技术，

6、故被广泛地应用于大、 中、 小型机器和微型机中。 在虚拟存储管理中,一般将硬盘作为外存,并且其逻辑地址空间大小与物理内存大小没有直接关系,由计算机系统的地址结构决定.为了进行分区的分配和回收，在固定分区存储管理系统为了进行分区的分配和回收，在固定分区存储管理系统中，有一张记录中，有一张记录 内存配和使用情况的说明表，分区说明内存配和使用情况的说明表，分区说明表用来记录各分区的起始地址、分区大小和分区分配状表用来记录各分区的起始地址、分区大小和分区分配状态。态。固定分区分配中的分区表 Operating System128 K896 KOperating SystemProcess 1320 K

7、576 KOperating SystemProcess 1320 KProcess 2224 K352 KOperating SystemProcess 1320 KProcess 2Process 3224 K288 K64 KOperating SystemProcess 1320 KProcess 3224 K288 K64 KOperating SystemProcess 1320 KProcess 3288 K64 KProcess 4128 K96 KOperating System320 KProcess 3288 K64 KProcess 4128 K96 KOperatin

8、g SystemProcess 3288 K64 KProcess 4128 K96 KProcess 2224 k96 K在可变式存储管理中，常把空闲区组织成空闲分区表和空闲在可变式存储管理中，常把空闲区组织成空闲分区表和空闲分区链表分区链表 。(1) 空闲分区表。 空闲分区包括分区序号、分区起始地址、分区大小的数据，空闲分区表要占用一定数量的存储单元存放表，增加了系统开销。(2) 空闲分区链表。 空闲分区链表的组织形式：在每个空闲分区的起始部分开辟出一个单元，存放一个链表指针和该分区的大小，链表指针指向下一个空闲分区。系统中用一个固定单元作为空闲分区链表的链表头指针，指向第一块空闲分区首指

9、针，最后一块空闲分区的链表指针存放链尾标志。链表按空闲分区在内存的位置顺序由小到大链接起来。空闲分区链表的组织时，空闲分区的信息放在空闲区内，不会额外增加系统开销。 1. 空闲分区的组织形式空闲分区的组织形式分区回收分区回收返回内存紧凑基本原理基本原理 1. 页面页面 (1) 页面和物理块 分页存储管理，是将一个进程的逻辑地址空间分成若干个大小相等的页，称为页面或页，并为各页加以编号，从0开始，如第0页、第1页等。程序加载时，分配其所需的所有页，这些页不必连续。需要CPU的硬件支持。相应地，也把内存空间分成与页面相同大小的若干个存储块，称为(物理)块或页框(frame)， 也同样为它们加以编号

10、，如0块、1块等等。在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为“页内碎片”。 分页式存储管理分页式存储管理 (2) 页面大小 在分页系统中的页面其大小应适中。页面若太小，一方面虽然可使内存碎片减小，从而减少了内存碎片的总空间， 有利于提高内存利用率，但另一方面也会使每个进程占用较多的页面，从而导致进程的页表过长，占用大量内存； 此外，还会降低页面换进换出的效率。然而，如果选择的页面较大，虽然可以减少页表的长度，提高页面换进换出的速度，但却又会使页内碎片增大。因此，页面的大小应选择得适中，且

11、页面大小应是2的幂，通常为512 B4MB。 小内碎片小；大页表短，管理开销小，交换时对外存I/O效率高。2. 地址结构地址结构 分页地址中的地址结构如下： 页号P页内地址W151090 对某特定机器，其地址结构是一定的。若给定一个逻辑地址空间中的地址为A，页面的大小为L，则页号P和页内地址d可按下式求得： MODLAdLAINTP页表页表 用于记录进程的一个页面和对应的内存物理块号用于记录进程的一个页面和对应的内存物理块号.借助于页表可以实现逻辑地址与物理地址之间的转换借助于页表可以实现逻辑地址与物理地址之间的转换.图 4-11 页表的作用 用户程序0 页1 页2 页3 页4 页5 页n 页

12、页表页号块号02132638495内存0123456789103. 地址变换机构地址变换机构 基本的地址变换机构基本的地址变换机构 页表寄存器页表始址页表长度页号(3)页内地址逻辑地址L越界中断1块号b页表页号012物理地址3页表长度页表地址控制寄存器页号页面号有效地址02132821C4物理地址81C4页式地址变换举例具有快表的地址变换机构具有快表的地址变换机构页表寄存器页表始址页表长度页号页内地址逻辑地址L越界中断块号b页表页号页号输入寄存器块号bb快表d物理地址将最近访问的页面的页表信息存放在高速缓存中,其中的页表就是快表.访问快表的速度远远大于访问内存中页表的速度.分段存储管理方式的引

13、入分段存储管理方式的引入 引入分段存储管理方式， 主要是为了满足用户和程序员的下述一系列需要： 1) 方便编程 2) 信息共享 3) 信息保护 4) 动态增长 5) 动态链接 4.3.4 分段式存储管理返回页式管理是把内存视为一维线性空间；而段式管理是把内存视为二维空间，与进程逻辑相一致。每个作业由若干个逻辑分段组成，每一分段是一组逻辑意义完整的信息集合。简单段式管理的基本原理分段存储管理是以段为基本存储单位分配内存，每一段必须是连续的内存空间，将程序的地址空间划分为若干个段(segment)，程序加载时，分配其所需的所有段（内存分区），这些段长度不一致且不必连续；物理内存的管理采用动态分区。

14、需要CPU的硬件支持。返回段号段内地址31 16 15 0分段存储管理中的逻辑地址具有如下结构： 1. 段表内存分配:以段为单位分配,每段各占一块内存区,各段可以离散的放入内存.作业空间(MAIN)0030K(X)1020K(D)2015K(S)3010K30K20K15K10K40K80K120K150K段长基址段号(MAIN)030K(X)120K(D)215K(S)310K040K80K120K150K段表内存空间01232. 段表段表 地址变换机构 段表控制寄存器段表始址段表长度2100段号S越界1 K段长600段号01236 K4 K5002008 K9200基址位移量W82928K

15、82928692主存物理地址逻辑地址页式管理和段式管理的比较 (1) 页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头， 提高内存的利用率。或者说，分页是出于系统管理的需要，分段是出于用户应用的需要。段则是信息的逻辑单位，它含有一组意义相对完整的信息。 分段的目的是为了能更好地满足用户的需要。一条指令或一个操作数可能会跨越两个页的分界处，而不会跨越两个段的分界处。 (2) 页的大小固定且由系统决定，由系统把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而在系统中只能有一种大小的页面；而段的长度却不固定， 决定于用户所编写的程序，通常由编译程序在对源程序进行编译时，根

16、据信息的性质来划分。 (3)逻辑地址表示：分页的作业地址空间是一维的，各个模块在链接时必须组织成同一个地址空间；而分段的作业地址空间则是二维的，既需给出段名， 又需给出段内地址。返回1. 问题的引出 返回虚拟存储器定义虚拟存储器定义 所谓虚拟存储器， 是指具有请求调入功能和置换功能， 能从逻辑上对内存容量加以扩充的一种存储器系统。其运行速度接近于内存速度，而每位的成本却又接近于外存。可见，虚拟存储技术是一种性能非常优越的存储器管理技术。 在虚拟存储管理中,一般将硬盘作为外存,并且其逻辑地址空间大小与物理内存大小没有直接关系,由计算机系统的地址结构决定.动态地址重定位动态地址重定位请求分页中的硬

17、件支持请求分页中的硬件支持 1. 页表机制页表机制 o需要在进程页表中添加若干项状态位(present bit）：指示该页是否在内存，状态位为0，该页不在内存，状态位为1，该也在内存。引用位 ：用于标志页面在内存时是否被访问；置换算法换出页面时作为参考修改位(modified bit) ：指示该页调入内存是否被修改过。外存地址：用于指出该页在外存的地址，供调入该页时使用。在简单页式存储管理的基础上，增加请求调页和页面置换功能。页号 物理块号 状态位P 引用位 修改位M外存地址 请求分页存储管理中的地址重定位和缺页中断由处理器的地址变换机构产生缺页中断，然后调用操作系统提供的中断处理例程。缺页中

18、断处理保留CPU现场从外存中找到缺页内存满否？选择一页换出该页被修改否？将该页写回外存OS命令CPU从外存读缺页启动I/O硬件将一页从外存换入内存修改页表否是是否页表项在快表中？CPU检索快表访问页表否页在内存？修改访问位和修改位形成物理地址地址变换结束否页号页表长度?开始程序请求访问一页产生缺页中断请求调页修改快表是越界中断是是返回1. 调入策略 (fetch policy)调入策略确定在外存中的页面调入时机。在虚拟页式管理中有两种常用策略。2. 从何处调入页面从何处调入页面 在请求分页系统中的外存分为两部分：用于存放文件的文件区和用于存放对换页面的对换区。通常，由于对换区是采用连续分配方式

19、，而事件是采用离散分配方式，故对换区的磁盘I/O速度比文件区的高。这样，每当发生缺页请求时，系统应从何处将缺页调入内存，可分成如下三种情况： (1) 系统拥有足够的对换区空间，这时可以全部从对换区调入所需页面，以提高调页速度。为此，在进程运行前， 需要将与该进程有关的文件，从文件区拷贝到对换区。 (2) 系统缺少足够的对换区空间，这时凡是不会被修改的文件，都直接从文件区调入；而当换出这些页面时，由于它们未被修改而不必再将它们换出，以后再调入时，仍从文件区直接调入。但对于那些可能被修改的部分，在将它们换出时，便须调到对换区，以后需要时，再从对换区调入。 (3) UNIX方式。由于与进程有关的文件

20、都放在文件区，故未运行过的页面，都应从文件区调入。而对于曾经运行过但又被换出的页面，由于是被放在对换区，因此在下次调入时，应从对换区调入。由于UNIX系统允许页面共享，因此，某进程所请求的页面有可能已被其它进程调入内存，此时也就无须再从对换区调入。 3. 页面调入过程页面调入过程 每当程序所要访问的页面未在内存时，便向CPU发出一缺页中断，中断处理程序首先保留CPU环境，分析中断原因后， 转入缺页中断处理程序。该程序通过查找页表，得到该页在外存的物理块后， 如果此时内存能容纳新页，则启动磁盘I/O,将所缺的页调入内存，然后修改页表。如果内存已满，则须先按照某种置换算法从内存中选出一页准备换出；

21、如果该页未被修改过，可不必将该页写回磁盘；但如果此页已被修改， 则必须将它写回磁盘，然后再把所缺的页调入内存， 并修改页表中的相应表项，置其存在位为“1”，并将此页表项写入快表中。在缺页调入内存后，利用修改后的页表，形成所要访问数据的物理地址，再去访问内存数据。 缺页率表示“缺页次数 / 内存访问次数”(比率)或“缺页的平均时间间隔的倒数”；是衡量页面置换算法的指标。下面我们用到的是局部范围内的置换算法，即系统为每个作业规定最大的内存占有数，当已占满规定的内存块数而又有新页面调入时，就从自身空间中置换一个页面，不允许替换别的作业的页面。返回 页面置换：把一个页面从内存调换到磁盘的对换区。 1.

22、 最佳最佳(Optimal)置换算法置换算法 最佳置换算法所选择的被淘汰页面，选择“未来不再使用的”或“以后最长时间内不需要访问的页”或“在离当前最远位置上出现的”页面被置换。采用最佳置换算法，通常可保证获得最低的缺页率。 这是一种理想情况，是实际执行中无法预知的，因而不能实现。可用作性能评价的依据。 假定系统为某进程分配了三个物理块， 并考虑有以下的页面号引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1 进程运行时， 先将7，0，1三个页面装入内存。 以后， 当进程要访问页面2时， 将会产生缺页中断。此时OS根据最佳置换算法， 将选择页面7予以淘汰。 引

23、用串70770170122010320304243230321201201770101页框(物理块）203选择最先进入内存或驻留时间最长的页面,应该首先被淘汰，性能较差。引用串70770170122010323104430230321013201770201页框2304204230230127127011进程P有5页程序访问页的顺序为：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5；如果在内存中分配3个页面，则缺页情况如下：12次访问中有缺页9次；FIFO123412512345页 0123412555344页 112341222533页 21234111255缺 页xx

24、xxxxxxX如果在内存中分配4个页面，则缺页情况如下：12次访问中有缺页10次；FIFO123412512345页 0123444512345页 112333451234页 21222345123页 3111234512缺 页xxxxxxxxxx选择内存中最近一段时间最久未使用的页面被置换。这是局部性原理的合理近似，性能接近最佳算法。引用串70770170122010320304403230321132201710701页框402432032102LRU置换算法的硬件支持置换算法的硬件支持 (1) 计数器方式计数器方式 为了记录某进程在内存中各页的使用情况，须为每个在内存中的进程的页表添加一

25、项,用于记录该页已经使用过的时间。每使用一次页面,逻辑时钟或计数器的内容被烤贝到页表时间记录中。由于需要记录页面使用时间的先后关系，硬件开销太大(2) 堆栈方式堆栈方式 用栈保存当前使用页面时栈的变化情况 4474707407047170410174010741210742120741210742621076把被访问的页面移到栈顶，于是栈底的是最久未使用页面。4 Clock置换算法置换算法 1. 简单的简单的Clock置换算置换算法法 入口查寻指针前进一步，指向下一个表目页面访问位0?选择该页面淘汰是返回置页面访问位“0”否块号页号访问位指针0124034215650711替换指针2. 改进型

26、改进型Clock置换算法置换算法 由引用位R和修改位M可以组合成下面四种类型的页面： 1类(R=0, M=0): 表示该页最近既未被访问， 又未被修改， 是最佳淘汰页。 2类(R=0, M=1)： 表示该页最近未被访问， 但已被修改， 并不是很好的淘汰页。 3类(R=1, M=0)： 最近已被访问， 但未被修改， 该页有可能再被访问。 4类(R=1, M=1): 最近已被访问且被修改， 该页可能再被访问。 其执行过程可分成以下三步： (1) 从指针所指示的当前位置开始， 扫描循环队列， 寻找R=0且M=0的第一类页面， 将所遇到的第一个页面作为所选中的淘汰页。 在第一次扫描期间不改变引用位R。

27、 (2) 如果第一步失败，即查找一周后未遇到第一类页面， 则开始第二轮扫描，寻找R=0且M=1的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的引用位都置0。 (3) 如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，并将所有的引用位复0。 然后重复第一步，如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰的页。 5. 置换算法举例某程序在内存中分配三个页面，初始为空，页面走向为4，3，2，1，4，3，5，4，3，2，1，5。 OPT 4 3 2 1 4 3 5 4 3 2 1 5页页1 4 3 2 1 1 1 5 5 5 2 1 1页

28、页2 4 3 3 3 3 3 3 3 5 5 5页页3 4 4 4 4 4 4 4 4 4 4 x x x x 3 3 x 3 3x x 3 共缺页中断共缺页中断7次次 LRU 4 3 2 1 4 3 5 4 3 2 1 5页页1 4 3 2 1 4 3 5 4 3 2 1 5页页2 4 3 2 1 4 3 5 4 3 2 1页页3 4 3 2 1 4 3 5 4 3 2 x x x x x x x 3 3x x x共缺页中断共缺页中断10次次FIFO 4 3 2 1 4 3 5 4 3 2 1 5页页1 4 3 2 1 4 3 5 5 5 2 1 1页页2 4 3 2 1 4 3 3 3 5 2 2页页3 4 3 2 1 4 4 4 3 5 5 x x x x x x x 3 3x x 3共缺页中断