L4(操作系统：存储管理)

Fundamentals

of

Software

软件技术基础

自动化学院仪器科学与技术系徐生林Email:xusl@Tel:86919131(O)、

88915606(O)MP/p>

QQ群:40048788周一上午3-5：3教301周四下午6-8：3教211Part1:OperatingSystem

第4讲:存储管理

一、存储器的存储结构Part1:OperatingSystem

Lecture4:MemoryManagement二、存储管理的任务1、主存空间的分配作业进入内存后放在哪里，运行进程申请内存如何分配2、地址映射程序中的逻辑地址如何转换成内存物理地址3、地址保护保护进程的物理地址空间不被非法访问4、内存的“扩充”“扩充”物理内存Part1:OperatingSystem

Lecture4:MemoryManagement三、地址定位1、地址静态定位Part1:OperatingSystem

Lecture4:MemoryManagement三、地址定位(续)2、地址与地址空间逻辑地址由处理机(CPU)分析指令时产生,就是指令中的地址,或者说是用户程序空间中的地址物理地址内存中的地址，通过对该地址的译码找到内存单元逻辑地址空间用户程序空间，所有逻辑地址的集合，地址范围：0-max物理地址空间内存物理地址的集合，大小由地址总线决定用户程序处理逻辑地址，用户都认为他的程序在地址范围0—max进行运行，这里的max为逻辑地址的最大值。Part1:OperatingSystem

Lecture4:MemoryManagement三、地址定位(续)3、动态重定位程序中的地址是逻辑地址，该地址程序运行时转换为内存物理地址的，程序可“搬家”用基地址寄存器或重定位寄存器实现动态重定位Part1:OperatingSystem

Lecture4:MemoryManagementPart1:OperatingSystem

Lecture4:MemoryManagement四、内存管理方法(Memorymanagementscheme)1、单一连续分区在操作系统起动后，内存被分成两个区域，一个区域存放操作系统，另一区域存放用户的程序,该方法只适用于单道程序的运行优点：实现简单;操作系统开销小缺点：只适用于单道程序，内存利用率低Part1:OperatingSystem

Lecture4:MemoryManagement四、内存管理方法(续)2、固定分区在操作系统起动后，内存被分成一系列固定不变的分区(partition)，一次内存分配以一块分区为单位，进程被装入到一块或连续的几块分区（进程大于一块分区）优点：实现简单;操作系统开销小缺点：由于产生内部碎片，内存利用率低Part1:OperatingSystem

Lecture4:MemoryManagement四、内存管理方法(续)2、固定分区(续)内部碎片Part1:OperatingSystem

Lecture4:MemoryManagement四、内存管理方法(续)3、动态分区(Dynamicpartitioning)除了操作系统占用的内存外，刚开始内存是一片连续的空间（一块分区），进程装入内存或进程申请空间，要求多少给多少，从而一点都不浪费，申请一次，产生一块分区。但经过多次的申请和释放，就出现一些很小的不连续的分区，这些小分区都暂时小于申请空间，也就产生了外部碎片（不是分区内部的）优点：无内部碎片;比固定分区的内存使用率高缺点：要通过中央处理机去把这些不连续的外部碎片连在一起，使得这些外部碎片变成一块大的分区，增加了中央处理机的负担。Part1:OperatingSystem

Lecture4:MemoryManagement动态分配空间的效果Part1:OperatingSystem

Lecture4:MemoryManagement动态分配空间的过程Part1:OperatingSystem

Lecture4:MemoryManagement动态分配空间的外碎片Part1:OperatingSystem

Lecture4:MemoryManagement四、内存管理方法(续)3、动态分区(续)空闲分区分配算法*首次适应算法（FirstFit）分配首个符合要求的空闲区，如申请13K，第一行满足要求最佳适应算法（BestFit）分配符合要求的最小空闲区，如申请36K，第二行满足要求最坏适应算法（WorstFit）分配符合要求的最大空闲区，如申请36K，第三行满足要求Part1:OperatingSystem

Lecture4:MemoryManagement紧凑或压缩Part1:OperatingSystem

Lecture4:MemoryManagement四、内存管理方法(续)4、分页管理物理内存被划分成大小相等的块，称作物理帧（Frame）用户程序逻辑空间被划分成与物理块一样大小的页（pages）分页管理允许一个进程在内存的物理地址是不连续的，从而压缩（compaction）不再需要，因此，外部碎片消失但是，内部碎片出现（页内碎片），每一进程的碎片平均是半页（出现在进程的最后一页）此外，分页的方法需要硬件的支持，如，页表（包含页号，页内偏移量）。每一进程有自己的页表，记录物理内存中那些块是分配给它的。Part1:OperatingSystem

Lecture4:MemoryManagementAddressspace1p0p1p2p3p4p1p1p2Addressspace2p0p1Addressspace3p4p2p1p0p1p3p0p1p0p2PhysicalAddressLogicalViewPhysicalViewFigure4.5Memoryisdividedintofixed-sizepages分页p4p2p1p0p1p3p0p1p0p2Part1:OperatingSystem

Lecture4:MemoryManagement

PhysicalAddressFramenumber:FPageoffset:D页号:P页内偏移量:DLogicalAddress页表20bits12bits4KpagesFigure4.6Translatelogicaladdressintophysicaladdressinpaging地址映射Part1:OperatingSystem

Lecture4:MemoryManagementPagePFrameFDPDLogicalAddressFDPhysicalAddressIDPDLBPageNumberRegisterBaseaddressinPT(ID)P>=L?Trap!☻Yes+P+B……F……Pagetable(PT)01P-1Figure4.7MappingoflogicaladdresstophysicaladdressNoInternalfragmentationPart1:OperatingSystem

Lecture4:MemoryManagement

4.PagingPagePFrameFDPDLogicalAddressFDPhysicalAddressIDPDLBPageNumberRegisterBaseaddressinPT(ID)P>=L?Trap!☻Yes+P+B……F……Pagetable(PT)01P-1Figure4.8AddressmappinginpagingWithFFTNo快速页表

(FPT)PFN-flagA-flagPart1:OperatingSystem

Lecture4:MemoryManagement四、内存管理方法(续)5、分段管理（Segmentation）物理内存与动态分区管理一样（申请多少给多少）用户程序逻辑空间被划分成段（Segmentation）分段管理允许一个进程在内存的物理地址是不连续的。由于申请多少给多少，从而内部碎片消失但经过多次的申请和释放，就出现一些很小的不连续的分区，这些小分区都暂时小于申请空间，也就产生了外部碎片，需要压缩（compaction)此外，分段的方法需要硬件的支持，如，段表（包含段号，段内偏移量）每一进程有自己的段表，记录物理内存中那些分区是分配给她的Part1:OperatingSystem

Lecture4:MemoryManagementAddressspace1S0S1S2S3S0S1S2Addressspace2S2S0S1S3S0S1S2PhysicalAddressLogicalViewPhysicalViewFigure4.9Memoryisdividedintologicalsegments分段Part1:OperatingSystem

Lecture4:MemoryManagementPhysicalAddressSegmentnumber:S’Segmentoffset:D段号:S段内偏移量:DLogicalAddressSegmentTableFigure4.10TranslatelogicaladdressintophysicaladdressinSegmentation地址映射Part1:OperatingSystem

Lecture4:MemoryManagement

SegmentSSegmentS’DSDLogicalAddressS’DPhysicalAddressIDSDLBSegmentNumberRegisterBaseaddressofST(ID)S>=L?Trap!☻Yes+S+BFrametable(FT)01F-1Figure4.7MappingoflogicaladdresstophysicaladdressNoSBSL……s’s’L……D>=S’L?YesNoExternalfragmentationPart1:OperatingSystem

Lecture4:MemoryManagement四、虚拟存储管理1、虚拟存储管理（Virtualmemorymanagement）前面的内存管理方法（1）（5）都要求：在进程运行时，要求整个进程的代码和数据被一次装入内存。但是，在大多数情况下，一次运行一个程序时，不会运行进程所有的代码，如，你执行你的程序不会调用所有的子程序。其次，由于存在时间局部性（一条指令被执行，不久又可能被执行，称程序的局部性原理）和空间局部性（一个数据被访问，不久又可能被访问，称数据的局部性原理），在进程内存的页不是被访问一次就不再被访问了，而是可能经常被访问。如循环体。基于以上特点，考虑利用外存作为虚拟的内存，只有需要执行的代码和数据才装入内存，否则存储在比内存大得多的外存上，这就是虚拟存储管理技术的总体思想。Part1:OperatingSystem

Lecture4:MemoryManagement四、虚拟存储管理(续)2、请求式分页管理(DemandPaging)核心问题还是解决逻辑地址到物理地址的转换，与分页管理的不同在于请求分页不需要一个进程所有的页一次装入内存由于不是进程所有的页调入内存，在进程执行时，就会出现下一条要执行的指令不在内存的情况，此时，操作系统就请求把包括该指令的页从磁盘调入内存,故称请求分页管理。请看下图，请求分页与分页的区别在于页表，一个进程的那些页在内存，那些也不在内存。Part1:OperatingSystem

Lecture4:MemoryManagement地址映射与缺页中断Part1:OperatingSystem

Lecture4:MemoryManagement四、虚拟存储管理(续)2、请求式分页管理(续)页面替换算法（Pagereplacementalgorithms）由于内存可能无空的页，就要把其他进程的页换出到磁盘，得到的空页给申请缺页的进程。替换算法的好坏主要体现在页面缺页率低先进先出算法（Firstinfirstout–FIFOpagereplacement）依据：在内存最长时间的也可能不再被用到，即程序执行的时间上的局部性特点Part1:OperatingSystem

Lecture4:MemoryManagementFIFO页面置换算法案例Part1:OperatingSystem

Lecture4:MemoryManagement四、虚拟存储管理(续)2、请求式分页管理(续)对有些页面替换算法，当内存的空页增加时，缺页率反而增加，该现象称为Belady’现象。FIFO算法就是其中之一同学们可以对访问页的顺序为：1，2，3，4，1，2，5，1，2，3，4，5。在内存总数分别为1、2、3、4、5、6页的情况下，求FIFO算法的缺页率。Part1:OperatingSystem

Lecture4:MemoryManagement四、虚拟存储管理(续)2、请求式分页管理(续)最近最少使用换页算法(Least-recently-unusedreplacement)选择内存中最长时间未被使用的页换到磁盘。Unix采用之。依据：程序执行的空间局部性特点Part1:OperatingSystem

Lecture4:MemoryManagementLRU页面置换算法案例共访问20页面，12次缺页Part1:OperatingSystem

Lecture4:MemoryManagement四、虚拟存储管理(续)2、请求式分页管理(续)最佳页面换页算法(OptimalAlgorithm)选择内存中将在最长时间内不会使用的页换到磁盘。不幸的是，很难判断最佳页面3、抖动（thrashing

）过高缺页率的现象，系统用于交换页面的时间远远大于CPU执行的时间影响缺页率的主要因素分配的页面数，一般的，moreframes⇒lesspagefaultsPart1:OperatingSystem