操作系统课件前四章作业答案

1、第四章 存储管理 第四章 存储管理 4.1 存储管理的基本概念存储管理的基本概念 4.2 早期的存储管理早期的存储管理 4.3 分页存储管理分页存储管理 4.4 请求分页存储管理请求分页存储管理 4.5 分段存储管理分段存储管理 4.6 段页式存储管理段页式存储管理 4.7 WindowsNT虚拟内存管理虚拟内存管理 第四章 存储管理 4.1 存储管理的基本概念存储管理的基本概念 4.1.1 存储管理研究的四个问题存储管理研究的四个问题 (1) 存储分配问题存储分配问题=存储器被多个进程共享的问题。重点是研究如何对进程分配存储器空间的算法。处理器共享通过在时间上的划分来实现，而存储器共享通过在

2、空间上的划分来实现。 (2) 装配模块的地址再定位问题装配模块的地址再定位问题。研究各种地址变换机构， 以及静态和动态再定位方法。 (3) 存储保护问题存储保护问题。 研究保护各类程序、 数据区的方法。 (4) 存储扩充问题存储扩充问题。 主要研究虚拟存储器问题及其各种调度算法。 第四章 存储管理 4.1.2 地址再定位地址再定位 1. 地址空间和存储空间地址空间和存储空间 装配模块 源程序 进程编译，链接加载符号指令变量类型高级语言结构二进制指令对存储空间的引用字节大小以及排列方式变成顺序结构装配模块内容+进程环境Transform内存管理：内存管理：Transform：LASpace -

3、PASpace第四章 存储管理 2. 地址定位发生的时态地址定位发生的时态 时间程序设计时或叫做编写程序时编译或汇编时加载模块产生时加载时运行时第四章 存储管理 2. 地址的静态再定位，发生在地址的静态再定位，发生在加载时加载时 80 KB50 KB030 KOSOS作业A地址空间作业A地址空间030 KB0110 KB主存主存80 KBLoaderLoaderTransform：LA - LA + Allocation Start Address 第四章 存储管理 动态地址再定位动态地址再定位发生在发生在运行时运行时 L 1，5001 2 3 4 5作业地址空间0100500600L 1，5

4、001 2 3 4 5010001100150016001000500处理机一侧 存储器一侧+BR有效地址再定位寄存器600LR界限寄存器主存Transform：LA - LA + BR如果LA + BR BR+LR，则地址访问时安全的第四章 存储管理 静态再定位与动态再定位的区别Load 1, 500123450100500Load 1, 150012345100011001500Start Address=1000静态Load 1, 500123450100500Load 1, 50012345100011001500BR=1000动态在加载时解析地址在运行时解析地址第四章 存储管理 Lo

5、ad 1, 500123450100500Load 1, 50012345100011001500BR=1000动态Load 1, 50012345200021002500BR=2000第四章 存储管理 程序能否在程序能否在内存中移动内存中移动程序在存储程序在存储空间中是否空间中是否连续存储连续存储是否有利于是否有利于程序共享程序共享执行效率执行效率应用领应用领域域静态不能。除非再装载一次，这对已经开始运行的程序不可行需要不利于高。因为物理地址是在装载时得到解析的，因此执行每条指令时，不需要再解析嵌入式控制器，DSP，Cray超级计算机动态可以。只需修改寄存器BR的内容即可不需要。为每个分散的

6、内存区域增加一对寄存器利于低。因为物理地址是在运行中边解析边执行，但是可以通过硬件来加速PC，服务器静态地址再定位与动态地址在定位比较第四章 存储管理 4.1.3 虚拟存储器概念的引入虚拟存储器概念的引入 虚拟存储器的基本思想是把作业地址空间和实际主存的存储空间， 视为两个不同的概念。一个计算机系统为程序员提供了一个足够大的地址空间，而完全不必考虑实际主存的大小。 由此，可以引出虚拟存储器更一般的概念， 即把系统提供的这个地址空间，想象成有一个存储器(虚存)与之对应，正像存储空间有一个主存与之对应一样。这就是说，虚虚拟存储器实际上是一个地址空间拟存储器实际上是一个地址空间。 第四章 存储管理

7、根据地址空间结构不同， 虚拟存储器有两种形式。 一种是单段式虚存单段式虚存， 它是一个连续的线性地址空间，其地址顺序为：0，1，2，n-1。其中n=2k, k为CPU给出的有效地址的长度。另一种是多段式虚存多段式虚存，它是把地址空间分成若干段，而每一段Si是一个连续的线性地址空间。每个地址可用Si, W来表示，Si为段名或段号，W为段内的相对地址。 VA = Bi + W第四章 存储管理 私有用户地址空间（程序、数据）用户栈进程控制信息处理器状态信息进程标识符共享地址空间Linux进程的虚拟地址空间0 x080480000 xffffffffVAS=232=4GCPUMMUVAMemoryPA

8、CPU chip动态地址再定位第四章 存储管理 4.2 早期的存储管理早期的存储管理 4.2.1 单一连续分配单一连续分配 作业操作系统未用32 KB64 KB160 KB分配给用户作业的空间图图 4.4 单一连续分配单一连续分配 特点特点：p 单道处理系统p 作业起始地址固定p 内存资源和处理器 没有得到充分使用p 作业需要的内存 物理内存时， 作业无法运行第四章 存储管理 4.2.2 分区分配分区分配 (a)分区号12345容量8 KB32 KB32 KB120 KB520 KB位置312 KB320 KB352 KB384 KB504 KB状态在使用在使用在使用未用未用(b)操作系统50

9、4 KB384 KB352 KB320 KB312 KB0520 KB120 KB32 KB32 KB8 KB312 KB特点：特点：p 分区大小固定，不能改变p 当存在一个分区：状态=“未用” / capacity Required Memory 则分配给作业，否则作业不能运行p 内存资源利用率低第四章 存储管理 表 4 1 固定式分区举例 分区号分区号 分区容量分区容量 作业容量作业容量 剩余容量剩余容量 123458KB32KB32KB120KB520KB1KB9KB9KB33KB121KB7KB23KB23KB87KB399KB合 计 712 KB 173 KB 539 KB 第四章

10、存储管理 2. 可变式分区法可变式分区法（ b）（ c）作业6256 KB作业5128 KB作业424 KB作业3 (120 KB)作业2 (32 KB)作业1 (8 KB)OS1024 KB504 KB384 KB352 KB320 KB312 KB0作业6 (256 KB)作业5 (128 KB)作业4 (24 KB)888 KB632 KB376 KB（ a）作业3 (120 KB)作业2 (32 KB)作业1 (8 KB)OS1024 KB504 KB384 KB352 KB320 KB312 KB0作业1 (8 KB)OS0作业6 (256 KB)作业5 (128 KB)作业4 (2

11、4 KB)1624 KB504 KB352 KB320 KB312 KB888 KB632 KB376 KB图 4.6 可变式分区的例子合并合并第四章 存储管理 表 4 - 2(a) 已分配已分配的分区状态表 分区号 分区容量 分区位置 状 态 123458KB32KB-120KB-321KB320KB-384KB-已分配 已分配 空 项 已分配 空 项 分区号 分区容量 分区位置 状 态 12-32KB520KB-352KB504KB-可用 可用-表 4 - 2(b) 未分配未分配的分区状态表第四章 存储管理 申请分配一个xKB大小的分区置空白区号f =1f 大于最后一个空白区号？空白区可用

12、？保存空白区的起始地址空白区 f的大小xKB空白区的状态=空项修改空白区的大小和起始地址在已分配表中找一个状态=空项的分区号 P置分区P的大小为 xKB置分区起始地址置分区状态为已分配返回一个分区号此次无法分配f +1 fYYNN=判断空白区是否可用判断空白区是否可用判断空白区大小判断空白区大小是否满足要求是否满足要求修改内存修改内存分配状态分配状态第四章 存储管理 请求释放一个分区 P保存分区P的大小和起始地址置分区的状态为空项分区P有邻接的空白区?修改新空白区的大小起始地址和状态返回修改空白区的状态修改新空白区的大小和起始地址在未分配表中找一空表目置新空白区大小和起始地址置空白区状态为可用

13、在两个空白区之间有一个空白区N图 4.8 可变式分区中释放一个分区的流程 第四章 存储管理 可变式分区分配法分配分区的算法当有多个空白区都可以满足作业内存需求时，究竟该选当有多个空白区都可以满足作业内存需求时，究竟该选择哪个分区予以分配？有如下几种策略择哪个分区予以分配？有如下几种策略p 最佳适应算法（Best Fit） min xi | xi RM 其中xi是分区的容量，RM是作业请求内存分配的大小p 最差适应算法（Worst Fit） max xi | xi RMp 最先适应算法（First Fit） xi | start address of xi is min / xi RM第四章 存

14、储管理 3. 可再定位式分区分配可再定位式分区分配 图 4.9 可再定位式分区分配的靠拢过程 作业7(256 KB)(a)(b)(c)作业6 (256 KB)作业5 (128 KB)作业4 (24 KB)作业1 (8 KB)OS作业7 (256 KB)作业6 (256 KB)作业5 (128 KB)作业4 (24 KB)作业1(8 KB)OS01024 KB504 KB352 KB320 KB312 KB888 KB652 KB376 KB作业6 (256 KB)作业5 (128 KB)作业4 (24 KB)作业1 (8 KB)OS第四章 存储管理 图 4.10 利用浮动寄存器进行地址变换 L

15、 1， 352 K + 980001557100352 KB352 KB + 50352 KB + 9800376 KB352 KB + 9800 -32 KB+L 1， 352 KB + 980001557100320KB320 KB + 50320 KB + 9800344 KB计算地址地址变换有效地址浮动寄存器第四章 存储管理 图图 4.11 可再定位式分区分配算法流程可再定位式分区分配算法流程 请求分配一个大小为xKB的分区有大于xKB的空白区吗？空白区的总和xKB？执行靠拢操作并修改状态表分配一个分区并修改状态表返回一个分区号此时无法分配YYNN没有足够空白区时再靠拢没有足够空白区时

16、再靠拢第四章 存储管理 4. 多重分区分配多重分区分配 如果我们不想采用靠拢的办法，又想使存储器分区的碎片问题适当地得到解决，那么可以采用多重分区分配方案。通常一个作业由一些相对独立的程序段和数据段组成，如主程序、子程序、数据组等。这些程序段中的每一个在逻辑上必须是连续的， 但是相应的各分区却不要求是连续的，只要有足够的保护措施就可以了。例如一个要求 100 KB存储空间的作业，实际上由五个 20 KB的段组成时，则可以分配给该作业一个100 KB的分区或者五个20 KB的分区，或者两个 40 KB的分区和一个 20 KB的分区等等。这种给一个作业分配一个以上分区给一个作业分配一个以上分区的方

17、法，称为多重分区分配的方法，称为多重分区分配。采用这种方法时，作业可以在其执行期间申请附加的分区。 第四章 存储管理 5. 分区的保护措施分区的保护措施 作业 2的分区60 KB124 KB256 KB060 KB基址寄存器64 KB限长寄存器作业 2的分区60 KB124 KB256 KB060 KB下界寄存器124 KB上界寄存器图 4.12 分区的界地址寄存器保护 分区保护的特点：分区保护的特点： 在运行过程中，每次访问存储器 时进行越界检查 只需要一组一组寄存器组就可以第四章 存储管理 6. 分区分配方案的评价分区分配方案的评价 分区分配方案的主要优点可归纳如下： (1) 实现了主存的

18、共享实现了主存的共享，因而有助于多道程序设计，更有效地利用了处理机和I/O设备，从而使系统的吞吐量和作业周转时间得到了相应的改善。至于主存利用率，可变式分区比固定式分区高些， 可再定位式分区则更高些。 (2) 相对于后面介绍的存储管理方式，本方案为实现分区分配所使用的表格、占用的存储容量相对较少，算法也相对简单。 (3) 实现存储保护的措施也比较简单。 (4) 多重分区分配方案能实现对子程序、 数据段的共享。 第四章 存储管理 分区分配的主要缺点有： (1) 主存仍不能充分利用，除了可再定位式分区法外，都存在着严重的碎片问题碎片问题。另外，即使不把存储器分碎，整个空白区也可能因容纳不下一个作业

19、而造成浪费空白区也可能因容纳不下一个作业而造成浪费。 例如，有 156 KB的存储空间可用，而某个作业序列是由 100 KB和 60 KB的作业组成的。如果分配了一个 100 KB的分区后，则剩下的 56 KB存储空间就要浪费掉。 第四章 存储管理 (2) 不能实现对主存的扩充不能实现对主存的扩充。 因此， 作业的大小受到主存可用空间的限制。 (3) 和单一连续分配一样，要求一个作业在执行之前必须全部全部装入主存，因此在主存中可能包含从未使用过的信息。 (4) 采用靠拢方法，虽然能解决碎片问题，但有时需移需移动大量信息动大量信息，从而损失了处理机时间。 (5) 除多重分区外，几个共行作业之间不

20、能共享不能共享存入主存的单一信息副本(如公用子程序、数据段等)。 第四章 存储管理 回顾回顾1、可执行文件（装载模块）三个地址空间、可执行文件（装载模块）三个地址空间Load 1, 500123450100500Load 1, 50012345磁盘空间逻辑(相对)地址空间Load 1, 50012345x100+x500+x物理地址空间所有地址从程序入口地址开始编号程序在内存中占据的地址空间映射映射第四章 存储管理 回顾回顾2、静态再定位和动态在定位、静态再定位和动态在定位Load 1, 500123450100Jmp 400500Load 1, 500+x12345x100+xJmp 400

21、+x500+x静态定位发生在装载时发生在装载时一旦装载，程序不能一旦装载，程序不能再浮动，否则会出现再浮动，否则会出现地址引用错乱地址引用错乱400400+x第四章 存储管理 Load 1, 500123450100Jmp 400500Load 1, 50012345x100+xJmp 400500+x动态定位发生在某条代码执行时，发生在某条代码执行时，当这条代码引用了当这条代码引用了某个地址时，才进行某个地址时，才进行地址的定位地址的定位400400+xJmp 400得到逻辑地址400再定位寄存器 x+400+x物理地址当运行这条指令时，才进行逻辑地址到物理地址的转换第四章 存储管理 4.3

22、 分页存储管理分页存储管理 4.3.1 分页原理分页原理 解决作业的内存空间必须连续的问题解决作业的内存空间必须连续的问题进程地址空间(3K+10)B0kB1kB2kB3kBP0P1P2P3OSOS内存地址空间B0B1B2B3B4B5B6B7B8B9 PMTP0 - B3P1 - B4P2 - B6P3 - B810第四章 存储管理 分页管理的特点分页管理的特点：1、页面的大小是固定的，通常是2k，如256B，1KB，4KB2、内存块的大小 = 页面的大小3、连续页所分配的块不需要连续分页管理的优点分页管理的优点：1、内存碎片小内存碎片小。内存碎片只能发生在分配给进程地址空间的最后一页的内存块

23、中，而块的大小通常很小，因此可以想象碎片也很小。2、不用浮动程序的内存空间就可以实现空闲空间的利用不用浮动程序的内存空间就可以实现空闲空间的利用。因为只要内存中有空闲块，无论这些块是否相邻，总可以进行分配。当然，付出的代价是需要建立一个PMT。第四章 存储管理 分页管理需要付出的代价分页管理需要付出的代价1、维护大页表需要一定的内存空间。2、逻辑地址到物理地址的转换更复杂。【例子】设某进程地址空间大小为16MB。页面大小为1KB。问保存该进程的页表需要多大内存空间？（1）16MB的程序可以划分出：224/ 210 = 212个页面（2）要编码212个页面，至少需要12 bits（3）考虑到字节

24、对齐，保存12 bits需要2 Bytes，也就是用2Bytes 保存一个页面编号（4）共需要212 X 2 Bytes=213 Bytes = 8KB第四章 存储管理 分页管理的关键分页管理的关键 地址转换：地址转换：LAddr - PAddr步骤：（1）把逻辑地址LAddr分解为形式： 假定 pagesize=1KB，那么： 400 = 1024 = 2049 = PageNum = LAddr / Pagesizeoffset = LAddr mod Pagesize第四章 存储管理 分页管理的关键分页管理的关键 地址转换地址转换步骤：（2）查PMT表，把PageNum映射到BlockN

25、um。一般通过硬件实现。（3）通过BlockNum和offset构造物理地址PAddr： PAddr= BlockNum* Blocksize + offset 【例子】假定pagesize=blocksize=1KB。页表如下。求逻辑地址2049转换的物理地址？(1) 2049 = (2) Page 2 对应 Block 6(3) 6*1kB + 1= 6145031526310PMT第四章 存储管理 地址转换的硬件实现地址转换的硬件实现上面的地址转换需要使用算法除法和乘法，比较复杂。实际上采用二进制表示页号和块号时，这个转换很容易。【定理】对于一个 n 位的逻辑地址，假如页面的大小为2k，

26、则高 (n-k) 位表示该逻辑地址所在的页号，低 k 位表示该逻辑地址的页面偏移量。nkn-koffsetPageNum逻辑地址逻辑地址低位高位第四章 存储管理 地址转换过程：offsetPageNum逻辑地址逻辑地址PMT： PageNum - BlockNum查表查表offsetBlockNum物理地址物理地址第四章 存储管理 【例子】用24位表示一个逻辑地址，pagesize = 4KB。求地址0000,0000,0010,0000,1001,0000的页号和页内偏移地址。【解答】因为4KB=212B，因此表示212个页内偏移地址需要12位。0000,0000,0010, 0000,10

27、01,0000PageNum = 2Offset =144第四章 存储管理 剩下的问题：如何高效的查页表？剩下的问题：如何高效的查页表？1、页表保存在内存中还是寄存器中？2、页表要不要与进程关联？ 2 4 7作业2（0 页）作业2（1 页）作业2（2 页）34160长度PMT 起始地址0页1页2页0 KB4 KB8 KB12 KB作业2的地址空间04 KB4160操作系统用块 2块 4块 7PMTAR4 字节页表地址寄存器页表地址寄存器第四章 存储管理 页表与进程的关系：1、页表的生命周期页表的生命周期：页表随着进程程序和数据的装载而建立，随着进程的消亡而消亡。因此 LifeCycle(PMT

28、) Block2.请求I/O通道完成磁盘文件到内存块的 数据传输3. 调度其它就绪进程并执行等待当页面装载完毕时，产生一个中断，OS在处理这个中断时，发现P正在等待这个事件的发生，于是将P从Block -Ready。如果P被调度，则从Ready- Run，这样得以继续运行下去。第四章 存储管理 这里一个遗留问题是：如何建立磁盘文件块与页面之间的关系？表 4-3 (b)辅助页表 虚页号辅存地址保护信息第四章 存储管理 4、当把新页载入内存，而内存不够用时，需要换出一部分页面，这时，被换出的页面是被简单的覆盖还是需要回写磁盘？Page n内存块Page mPage n磁盘块回写辅助页表第四章 存储

29、管理 表 4-3 (a) 扩充后的PMT表 虚页号 主存块号 改变位 引进位 状态位 辅存地址 标识该页面是否被修改过标识该页面是否被映射到内存该页面在外存介质中的物理位置第四章 存储管理 5、当把新页载入内存，而内存不够用时，需要换出的页面是在分配给当前进程中挑选，还是在整个内存中挑选？OSOS进程1.P0B0B1B2B3B4B5B6B7B8B9进程1.P1进程1.P2进程2.P0进程2.P1进程2.P2进程2.P3进程3.P0进程2.P4请求分配置换范围置换范围局部置换局部置换全局置换全局置换第四章 存储管理 6、置换策略问题 FIFO, LRU 例例 1 设页面走向为P=4, 3, 2,

30、 1, 4, 3, 5, 4, 3, 2, 1, 5，主存容量M=3，置换算法采用FIFO，则缺页中断次数及缺页率按表 4 - 4 给出。 表4-4 FIFO性能分析例(M=3) 第四章 存储管理 例例 3 设页面走向如上，M=3，置换算法为LRU，则系统模型如表 4-6 所示。在表 4-6 中，由于采用LRU算法，M中各列按访问的时间顺序排列，最近被访问的页面在最前。由表 4-6 算出缺页中断次数F=10， 缺页率f=10/12=83%。 表4-6 LRU性能分析例(M=3) 第四章 存储管理 内存大小与缺页中断次数的关系内存大小与缺页中断次数的关系图 4.26 存储容量与缺页中断次数的关系

31、 016KB 32KB 48KB 64KB 80KB 96KB 112KB100020003000400050006000700080009000MF24 KB932132 KB512648 KB245664 KB129580 KB69696 KB441112 KB329128 KB271160 KB144192 KB62缺页次数F主存大小M第四章 存储管理 不同置换策略与内存大小的关系不同置换策略与内存大小的关系表4-4 FIFO性能分析例(M=3,4) 第四章 存储管理 表4-6 LRU性能分析例(M=3，4) 第四章 存储管理 由表 4-6， 表 4-7 可得如下事实： 设G(P, M,

32、 t)表示当页面走向为P，主存容量为M，在时刻t的页面集合，对于LRU算法，存在如下关系，即 ), 1,(),(tMPGtMPG成立。即对于任何时刻t(t=1, 2, , 12),G(P, M, t)所选中的页号必定包含在G(P, M+1, t)之中。这种关系说明了增加主存容量不会增加缺页中断次数，然而对FIFO算法， 此关系并不成立。 第四章 存储管理 执行一条指令形成有效地址计算页号该页在实存吗？缺页中断入口有空闲的实页码？出页修改PMT MBTC=1？复制到辅存取出保存的页号入页找出磁盘地址修改PMT MBT表重新执行被中断的指令取下一条指令取数据完成该指令硬件软件YNNYYN图 4.2

33、1缺页中断的发生及其处理 第四章 存储管理 4.4.4 请求分页存储管理方案的评价请求分页存储管理方案的评价 (1) 它提供了大容量的多个虚拟存储器， 作业地址空间不再受实存容量的限制； (2) 更有效地利用了主存，一个作业的地址空间不必全部同时都装入主存， 只装入其必要部分，其它部分根据请求装入， 或者根本就不装入(如错误处理程序等)； (3) 更加有利于多道程序的运行， 从而提高了系统效率； (4) 方便了用户，特别是大作业用户。 第四章 存储管理 但请求分页还存在以下缺点： (1) 为处理缺页中断，增加了处理机时间的开销， 即请求分页系统是用时间的代价换取了空间的扩大； (2) 可能因作

34、业地址空间过大或多道程序道数过多以及其它原因而造成系统抖动； (3) 为防止系统抖动所采取的各种措施会增加系统的复杂性。 第四章 存储管理 作业：P1352,3,13,21,22第四章 存储管理 4.5 分段存储管理分段存储管理 细分用户程序的方案分页（分页（paging）分段分段采用分段技术，可以把程序和其相关的数据划分到几个段段中。值得注意的是：分段分段是程序设计语言提供给程序员的一种组织是程序设计语言提供给程序员的一种组织程序和数据的手段程序和数据的手段。在FORTRAN等语言中有对段的支持，但在C语言中没有段的概念。第四章 存储管理 大小是否固定大小是否固定是否对程序员是否对程序员透明

35、透明是否需要连续是否需要连续存储存储表示逻辑地址表示逻辑地址的方法的方法分页分页是是不需要分段分段否否不需要分页与分段的比较分页与分段的比较第四章 存储管理 4.5 分段存储管理分段存储管理 4.5.1 分段原理分段原理 OSXAMAIN实存空间346038004000L 1，A |6ST ,B|MAIN=00160X=3A=5B=6C:虚存空间34000100060160E0400034010060ERR/W001346038000123456SMT容量存取权限状态始址图 4.27 分段管理概念图第四章 存储管理 逻辑地址到物理地址的映射：LA - PAoffsetSegmentNum（1）

36、LA:mn（2）查段表，得到对应段号的内存起始地址start（3）PA = start + offset第四章 存储管理 【例子】在上图中，指令L 1，A | 6中引用了地址 A | 6中的数据。在那样的段表下，求逻辑地址 A | 6的物理地址。1、数组段A的段号为5, 地址 A | 6的偏移量是62、在SMT中，对应A的起始地址为38003、因此，逻辑地址 A | 6对应的物理地址为3800+6=3806第四章 存储管理 图 4.28 段式地址变换过程请求访问S段中的B单元段S在实存吗?BS段容量在访问权限之内?置访问位为1。若为写访问，则置改变位为1求段的始址L，加上段内地址B，便得实存地

37、址A=L+B返回访问地址S段号B段内地址缺段中断越界中断保护中断NNN由处理机产生由分段管理机构实 现第四章 存储管理 4.5.3 分段存储管理方案的评价分段存储管理方案的评价 分段管理的优点如下：(1) 消除了碎片。 (2) 提供了大容量的虚存。 (3) 允许动态增加段的长度。因为 (4) 便于动态装入和链接。 (5) 便于共享。当两个或两个以上的作业要使用同一子程序时，在实存上就要有两个或两个以上的程序副本，这样一来，实存的地址空间就可能被这些共用的子程序或标准应用程序所塞满。 (6) 便于实现存储保护。 第四章 存储管理 图 4.29 两个作业对SQRT的共享 第四章 存储管理 分段存储

38、管理的缺点有： (1) 进行地址变换和实现靠拢操作要花费处理机时间，为管理各分段， 要设立若干表格，提供附加的存储空间； (2) 在辅存上管理可变长度的段比较困难； (3) 段的最大长度受到实存容量的限制； (4) 会出现系统抖动现象。 第四章 存储管理 4.6 段页式存储管理段页式存储管理 4.6.1 段页式存储管理的实现段页式存储管理的实现 在段页存储管理系统中，处理机给出的有效地址被划分为三部分：段号、 页号和页内地址。在某计算机系统中，24 位有效地址的划分是： 段号S 页号P 页内地址W 0 7 8 15 16 19 20 31 第四章 存储管理 处理机给出的有效地址长度确定了作业地

39、址空间的范围。 换言之，它确定了虚存的容量。一个具体的地址结构，确定了一个作业最多能有几段， 每段最多能有几页以及每页的大小。 上述的 24 位有效地址确定了虚存的容量为 16 MB。 8 位的段号确定了一个作业地址空间最多有 256 个段，段号为 0255， 每个段最多为 16 页，页号为015，每页的大小为4 KB。 第四章 存储管理 现在假定有一个作业，它有三段：第 0 段段长为 15 KB， 占 4页(最后一页有 1 KB未用)；第 1 段为 8 KB，占2 页；第 2 段为 10 KB，占 3 页(最后2 KB未用)。该作业的地址空间如图 4.30 所示。 04 KB8 KB12 K

40、B15 KB16 KB0 段1 段04 KB8 KB04 KB8 KB10 KB2 段图 4.30 段页式管理的作业地址空间例 第四章 存储管理 程序的分段，可由程序员或编译程序按信息的逻辑结构来划分，而分页与程序员无关，它是由操作系统自动完成的。这就是说，程序员所使用的编址方式或编译程序给出的目标程序其地址形式仍是二维的，即(S，W)，其中S为段号，W为段内地址。而段内地址W则由地址变换机构把W的高 4 位解释为页号P， 把低 12 位解释为页内地址W。 对主存而言，和分页管理一样，划分为许多和页面大小相等的存储块(也称为实页)。因此，一个段可装入不连续的存储块一个段可装入不连续的存储块中，

41、于是就用不着再用靠拢的办法来消除碎片了。通常把超出页面大小的碎片称为外碎片(或大碎片)，而小于页面大小的碎片称为内碎片(或小碎片)。 第四章 存储管理 图 4.31 地址变换中所用表格的关系 段表长度段表地址0L0110L300000000控制寄存器 1状态页表长度 页表地址段号0123页号状态 实存页号01230123L0L3段表页表实存OS第四章 存储管理 图 4.32 段页式系统地址变换过程 控制寄存器 1（S，P）主存块号SPW不匹配S块号（S，P，W）PW联想存储器虚地址主存中的存储块段表页表（页面）第四章 存储管理 4.6.2 段页式存储管理的评价段页式存储管理的评价 段页存储管理

42、方案保留了分段存储管理和请求分页存储管理的全部优点。其主要优点是它提供了大量的虚存空间，能有效地利用主存，为组织多道程序运行提供了方便。 当然，段页存储管理也有缺点，主要缺点是增加了硬件成本、系统的复杂性和管理上的开销；页面使用不充分(和请求分页一样，存在着内碎片)； 各种表格(如SMT、 PMT等)占用主存空间； 存在着系统发生抖动的危险。 第四章 存储管理 4.7 Windows NT虚拟内存管理虚拟内存管理 4.7.1 进程的虚拟地址空间进程的虚拟地址空间 图图 4.33 虚拟地址空间虚拟地址空间 非页交换区页交换区直接映射地址页面交换区FFFFFFFFhC0000000h8000000

43、0h00000000h系统存储区(2 GB)用户存储区(2 GB)第四章 存储管理 4.7.2 虚拟存储的实现虚拟存储的实现 图图 4.34 二级页表地址变换结构二级页表地址变换结构 页表地址页帧地址代码或数据页目录(每进程一个)页表页帧表目录位移页表位移页位移3121110页目录地址虚拟地址第四章 存储管理 图 4.35 地址变换过程举例 0030020080044000626代码或数据00C00800400000800400000800400000C02000168#00440#00626#0016831110控制寄存器页目录页表页帧虚拟地址第四章 存储管理 我们计算一下，分页管理和分级页

44、管理下，页表所占内存大小。p 在分页管理下，一个进程的虚拟空间共需要 232/ 212 = 220=1M个页表项，假定用一个word（即4 Bytes）保存一个页表项，那么共需4MB来保存一个页表。p 在分级页管理下，一个进程的虚拟空间被分为一个页目录，其中包含1K个页目录项，每个页目录项包括1K个页表。这样保存页目录需要1K*4B=4KB，保存页表需要1K*1K*4B=4MB所以共需4KB+4MB。p 尽管分级页管理保存页目录和页表的内存大于分页管理的页表内存，但是搜索效率得到了提高：O(1K) + O(1K) O(1M)第四章 存储管理 采用两级页表的缺点是降低了访问主存的速度。 因为每进

45、行一次地址变换要有三次访问主存：查页目录访问一次，查页表访问一次，到主存中存取目标数据又访问一次。但实际上Windows NT的访问主存速度并不慢， 相对来说还比较快，这主要是因为它采取了如下两个措施： (1) 使用快表，即使用联想存储器加快了查表速度， 在Windows NT中称其为变换查找缓冲区TLB。 (2) 使用高速缓冲存储器cache，在处理机和主存间设置了 32 KB或 64 KB的高速缓冲存储器，大部分的指令和数据取自高速缓存(命中率达98%)，所以存取数据和指令速度相当快，与处理机的速度完全匹配。 第四章 存储管理 2. 页面调度页面调度 页面调度策略包括取页、置页和淘汰策略。

46、 Windows NT的取页策略分为两种，一种是按进程需要的“请求取页”，另一种是提前取页。前一种方法是在请求分页存储管理中普遍采用的方法，而后一种是Windows NT所独有的，采取集群方法把一些页面提前装入主存。集群方法提前取页的意思是，当一个线程在发生缺页时，不仅把它需要的那一页装入主存，而且还把该页附近的一些页也一起装入。这样做的主要依据就是程序行为的局部性。因此采取提前装入取页会减少缺页次数，尤其在一个线程开始执行时，请求取页会造成频繁缺页，降低系统的性能。 第四章 存储管理 置页策略是指把虚页放入主存的哪个页帧， 这个问题在线性存储结构中比较简单，只要找到一个未分配的页帧即可。 置

47、换(淘汰)策略，是为每个进程分配一个固定数量的页面(但可动态调整这个数量)，当发生缺页中断时，从本进程从本进程的范围内的范围内进行替换。在Windows NT中采用了局部置换策略了局部置换策略。Windows NT采用先进先出(FIFO)页面置换算法， 即把在主存中驻留时间最长的页面淘汰出去，采用这种方法的出发点是算法实现简单。 第四章 存储管理 第一章作业：T6ABCI/O30A:10101050B:30201020C:40第一种情况：第一种情况：A，B，C共用一个共用一个I/O10T=190ms第四章 存储管理 第一章作业：T6ABCI/O130A:10101050B:302020C:40

48、第二种情况：第二种情况：A，B，C拥有不同拥有不同I/OI/O2T=180ms第四章 存储管理 ABCI/O130A:10101050B:302020C:40假如考虑调度器调度时间假如考虑调度器调度时间I/O2T=msSched10第四章 存储管理 ABCI/O130A:10101050B:302020C:40假如考虑调度器调度时间假如考虑调度器调度时间I/O2T=msSched10问题：1、调度程序的执行通常发生在什么时刻？调度程序的执行是怎样触发的？2、下图中，在什么时段系统状态是：第四章 存储管理 第二章补充题：给定一组作业给定一组作业J1, J2, , Jn，其执行时间依次为，其执行时

49、间依次为R1,R2,Rn。假定。假定这些作业同时到达，并且在同一台处理机上按单道方式执行。这些作业同时到达，并且在同一台处理机上按单道方式执行。试证明：按最短作业优先算法调度时，其平均周转时间最短。试证明：按最短作业优先算法调度时，其平均周转时间最短。假定按照J1,J2,Jn的顺序来调度，则周转时间为：T1=R1T2=T1+R2=R1+R2T3=T2+R3=R1+R2+R3Tn=Tn-1+Rn=R1+R2+Rn-1+Rn总周转时间：T= Sigma_i=1,nTi = nR1+(n-1)R2+(n-2)R3+2Rn-1+Rn = niiRin1) 1(平均周转时间：niiRinn1) 1(1第

50、四章 存储管理 第三章作业：T12LOCK：while(w = =1) skip;w:=1;UNLOCK:w:=0;要点：1、从进程调度和状态变化方面来说明。2、与P，V操作进行对比Critical regionP1 P2 CPULOCKP1 P2 第四章 存储管理 第三章作业：T12LOCK：while(w = =1) skip;w:=1;UNLOCK:w:=0;要点：1、从进程调度和状态变化方面来说明。2、与P，V操作进行对比Critical regionP1 P2 CPULOCKP1 P2 第四章 存储管理 第三章作业：T231、如果每次只允许一个进程进入互斥段，信号量初值为1，变化 范

51、围是1,0,-1, -(n-1)，即1-n, 12、如果最多允许m（mn）个进程同时进入互斥段，信号量初值 为m，变化范围是：m, m-1, , 0, -1, , -(n-m)思考：在第（2）问中，当信号量值是-(n-m)时，这些进程分别处于什么状态？第四章 存储管理 第三章作业：T24为描述读者的动作，需要编写三个程序：p实现登记操作Checkin()p实现进入阅览室之后的阅读操作Read()p实现读者离开时的注销动作Checkout()。如果阅览室最多允许n个读者进入的话，那么就会为每一个读者i创建一个进程Pi，每个进程按照Pi：Checkin();Read();Checkout()的次序依次顺序三个程序执行。这里存在的并发问题主要有：p最多只能允许n个读者（即n个进程）进入阅览室（即关键区）p每个读者在进行Checkin和Checkout时对于登记表关键区必须互斥。为此，我们有如下算法：