第七讲存储器管理

1、第七讲第七讲 存储器管理存储器管理中国科学技术大学计算机系中国科学技术大学计算机系 陈香兰陈香兰2013Fall内容提要内容提要v存储器的层次结构v程序执行的基础知识、程序的装入和链接v连续分配存储管理方式v分页存储管理方式v分段存储管理v段页式存储管理连续内存分配方式连续内存分配方式（contiguous memory allocation）vReading：Operating System Concepts，p284-v连续分配存储管理方式单一连续固定分区动态分区v对换v内存通常被划分为两个分区（partitions）:系统区：常驻操作系统系统区：常驻操作系统，通常位于内存低端用户区：提供

2、给用户（进程）使用，用户区：提供给用户（进程）使用，常位于内存高端v连续内存分配是指：从用户区中为每个进程分配一个单独的、连续从用户区中为每个进程分配一个单独的、连续的内存空间的内存空间。v主要有以下两种方式单一连续分配方式多分区式分配方式l固定分区式l动态分区式（可变分区式）单一连续分配方式单一连续分配方式v最简单v只能用于单用户、单任务系统v存储保护机制存储管理单元，MMU或者不采用任何存储保护机制l出于信任，或采用再启动方式，多分区式分配方式多分区式分配方式v支持多道程序，用户区被进一步划分为若干个分区每一个分区装载一个进程多道程序度与分区的个数有关v根据分区大小是固定的还是可变的固定分

3、区方式l大小固定；等大小 or 不等大小动态分区方式（可变分区方式）l动态&可变：内存的划分是动态的，分区的大小随进程的大小确定，分区的数目随系统的运行而不断变化固定分区分配方式固定分区分配方式v支持多道程序，用于60年代IBM360的MFT中v分区的划分方法，两种等大小不等大小但分区的大小一旦确定就不再发生变化v分配算法：按大小顺序建立分区使用表0分区号 大小（KB） 起始地址(K) 状态11530已分配23045已分配35075已分配4100125已分配操作系统作业A作业B作业C30K45K75K125K225K固定分区使用表固定分区使用表v分配算法v缺点内存利用率低v定义：内部碎片和外部

4、碎片内部碎片：已经分配出去但得不到利用的存储区域外部碎片：不能被利用的小分区v解决方案：动态分区动态分区分配方式动态分区分配方式v能根据进程实际需要的内存大小，动态分配能减少内部碎片v关键数据结构：记录内存的使用情况，特别是空闲内存分配算法分配和回收操作数据结构数据结构v 空闲分区表空闲分区表，占用额外的空间v 空闲分区链空闲分区链，利用空闲分区序号 分区大小起始地址 状态前向指针N个字节可用后向指针N2N200分区分配算法分区分配算法v在将一个新作业装入内存时，要从空闲分区表或空闲分区链中，选出一个分区分配给该作业，有三种常见的分配算法首次适应算法FF：First Fit循环首次适应算法最佳

5、适应算法：Best Fit=smallest最差适应算法：Worst Fist largest分区分配操作分区分配操作v 分配 设请求的分区大小为u.size； 利用某种分配算法，找到待分配的分区，大小为m.size 根据上述分区分配算法，有m.sizeu.size 判断m.size-u.size与min_size的大小min_size为事先约定的最小分区大小l ，分割，分割出来的分配出去，余下的加入空闲数据结构l 否则，直接分配 将分配到的分区的首地址返回可以看出，动态分区分配方式中内部碎片最大不超过min_sizev回收，要考虑合并向前合并l只需修改前一个空闲分区表项中的大小向后合并（图）

6、l只需修改后一个空闲分区表项中的起始地址和大小与前后同时合并l修改前一个空闲分区表项中的大小，并取消后一个分区表项无相邻空闲分区，无需合并l建立一个新的表项，填写相关信息，插入上述过程中，根据链表的维护规则，可能需要调整相应表项在空闲链表中的位置动态分区分配分析动态分区分配分析v随着分配的进行，空闲分区可能分散在内存的各处尽管有回收，但内存仍然被划分的越来越碎，形成大量的外部碎片OSprocess 5process 8process 2OSprocess 5process 2OSprocess 5process 2OSprocess 5process 9process 2process 9pr

7、ocess 10解决方案之一：紧凑解决方案之一：紧凑Compactionv针对外部碎片：采用紧凑的方法v紧凑：通过移动进程在内存中的位置，把多个分散的小分区拼成大分区v需要动态重定位技术支持v动态重定位分区分配算法：引入紧凑和动态重定位技术的动态分区分配算法v基本与动态分区分配算法相同Swapping 对换对换v最早用于MIT的CTSS中单用户时间片对换v对换是指把内存中暂时不能运行的进程，或暂时不用的程序和数据，换出到外存上，以腾出足够的内存空间，把已具备运行条件的进程，或进程所需要的程序和数据，换入内存v能提高内存利用率v对换的单位：进程：整体对换；进程对换页、段：部分对换v对换技术需要实

8、现三个方面的功能对换空间的管理进程的换出进程的换入Backing store，对换空间，对换空间vFast disk, large enough to accommodate copies of all memory images for all users; must provide direct access to these memory images.为提高速度，考虑连续分配方式，忽略碎片问题需提供数据结构对空闲盘块进行管理l方法类似动态分区分配方法进程的换出进程的换出v第一步：选择被换出的进程Some approacheslRR scheduling: swapped out whe

9、n a quantum expireslPriority-based scheduling: Roll out, roll inlLower-priority process is swapped out so higher-priority process can be loaded and executed.v第二步：换出确定要换出的内容l非共享的程序和数据段的换出l共享的程序和数据段的换出：计数器申请对换空间，换出，并修改相关数据结构进程的换入进程的换入v第一步：选择被换入的进程考虑“静止就绪状态”的进程其他原则v第二部：申请内存并换入申请成功申请失败：利用对换技术腾出内存Schemat

10、ic View of SwappingSwapping (cont.)v Context switch Swapped in & out cost too much Assume: process size 1MB, disk transfer rate 5MB/sec, average latency 8msl Transfer time =1MB / (5MB/sec) = 1/5 sec = 200 msl Swap time = 208 msl Swap out & in = 416 Major part of swap time is transfer time v For RR s

11、cheduling, time quantum should 416msv Problems exist for pending I/O processes swapping内容提要内容提要v存储器的层次结构v程序执行的基础知识、程序的装入和链接v连续分配存储管理方式v离散分配方式（离散分配方式（Discrete Memory Allocation）分页存储管理方式分页存储管理方式l碎片碎片页页分段存储管理分段存储管理l从逻辑上进行分段从逻辑上进行分段段页式存储管理段页式存储管理内容提要内容提要v存储器的层次结构v程序执行的基础知识、程序的装入和链接v连续分配存储管理方式v离散分配方式（离散分

12、配方式（Discrete Memory Allocation）分页存储管理方式分页存储管理方式l碎片碎片3bvEffective memory-access time, time needed for every data/instruction access需要2次访存Access the page table & Access the data/instructionvSolution:A special fast-lookup hardware cache called associative registers or translation look-aside buffers (TL

13、Bs)联想存储器，快表联想存储器，快表v Associative registers Each register : a key & a value Parallel search (high speed) Expensive, typically 82048 entriesv Address translation (A, A) If A is in associative register, get frame # out. Otherwise get frame # from page table in memory联想存储器，快表联想存储器，快表v TLB miss（TLB缺失） If

14、 the page number is not in the associative registersl Get & storev Hit ratio（命中率） The percentage of times that a page number is found in the associative registersv Context switch TLB flushedv TLB replacement algorithm具有块表的地址变换机构具有块表的地址变换机构页表寄存器页表始址页表长度页号页内 地 址逻辑地址L越界中断块号b页表页号页号输入寄存器块号bb快表d物理地址+Effec

15、tive Access Time 有效存取时间有效存取时间v 设： Associative Lookup = time unit;memory cycle time = t time unit;Hit ratio = v Effective Access Time (EAT)EAT = (t + ) + (2t + )(1 )= 2t + tv If (20 ns), t(100 ns), 1(80%), 2(98%):lTLB hit: 20+100=120 nslTLB miss: 20+100+100=220 nslEAT1 = 120*0.8 + 220 * 0.2 = 140 nsl

16、EAT2 = 120*0.98 + 220 * 0.02 = 122 nsMemory Protection 内存保护内存保护vIf page size 2n, page & frame is aligned at 2n, so vMemory protection implemented by associating protection bit with each frameProvide read only, read-write, execute-only protection orValid-invalidl“valid”: the associated page is in the

17、 process logical address space, and is thus a legal page.l“invalid”: the page is not in the process logical address space.Valid/invalid bit examplev Address space 214v Page size 2KBv Process size (010468) v Page 5 has internal fragmentationv PTLR=6v Page 6 & 7 are invalid104861024012287两级和多级页表两级和多级页

18、表v考虑：地址空间：32位；页大小4KB；有220即1M个页需要页表项：1M个设，每个页表项使用32位表示，需要4MB的空间v解决方案：进一步离散两级页表两级页表v 对页表分页，建立外层页表（页目录）v 则上述4MB的页表，进一步分为1K个页需要1K个页目录项假设每个页目录项使用32位表示，需要4KBv 因此，逻辑地址where p1 is an index into the outer page table, and p2 is the displacement within the page of the outer page table.page numberpage offsetp1p

19、2d101012两级页表举例两级页表举例具有两级页表的地址变换机构具有两级页表的地址变换机构外部页号P1P2外部页内地址 页内地址d逻辑地址外部页表寄存器外部页表db页表页表物理地址+多级页表及其性能多级页表及其性能vLevel number = L, effect memory accesses time = (L+1)t考虑高速缓存技术：vCache hit rate of 98 percent yields:effective access time = 0.98 120 + 0.02 520= 128 nanoseconds.which is only a 28 percent slo

20、wdown in memory access time.内容提要内容提要v存储器的层次结构v程序执行的基础知识、程序的装入和链接v连续分配存储管理方式v离散分配方式（离散分配方式（Discrete Memory Allocation）分页存储管理方式分页存储管理方式l碎片碎片页页分段存储管理分段存储管理l从逻辑上进行分段从逻辑上进行分段段页式存储管理段页式存储管理分段存储管理方式分段存储管理方式v 引入分段的目的，是为了满足用户在编程和使用上的需求（逻辑上）v 在用户看来：A program is a collection of segments. A segment is a logical

21、 unit such as:lmain program,lprocedure, lfunction,lmethod,lObjectllocal variables,lglobal variables,lcommon block,lstack,lsymbol table逻辑地址空间逻辑地址空间v A collection of segments each segment Two dimensional address spacev A logical address v Compiler automatically constructs segments reflecting the input

22、 program. Pascal compiler FORTRAN compiler C compiler, such as gcc, 段号段号段内段内地址地址3116 150Logical view of segmentation分段的硬件支持分段的硬件支持v段表2-D logical address 1-D physical addresses; v每个段表项包括段在内存中的基地址段的长度vSegment-table base register (STBR) Points to the segment tables location in memory.vSegment-table len

23、gth register (STLR)Indicates number of segments used by a program; Segment number s is legal if s STLR.段表举例段表举例作业空间(MAIN)0030K(X)1020K(D)2015K(S)3010K30K20K15K10K40K80K120K150K段长基址段号(MAIN)030K(X)120K(D)215K(S)310K040K80K120K150K段表内存空间0123分段的地址变换机构分段的地址变换机构控制寄存器段表始址段表长度2100段号S越界1 K段长600段号01236 K4 K50

24、02008 K9200基址位移量W82928K82928692主存物理地址有效地址段表始址段表始址段表段表长度长度+段号段号S 位移量位移量W分页和分段的主要区别分页和分段的主要区别v角度和目的不同分页：面向系统，物理上离散，减少外部和内部碎片，提高内存利用率l页是信息的物理单位分段：面向用户，逻辑上离散，满足用户的需求l段是信息的逻辑单位，意义相对完整v大小不同分页：大小固定，由硬件决定分段：不固定，划分由程序决定，在编译时确定v地址空间的维数不同分页：1维分段：2维，段名段内偏移分段举例分段举例 4300 + 53 = 4353 3200 + 852 = 4052How about ?分段的好处分段的好处v Relocation，可重定位，方便编程 Dynamic, by segment table v Sharing shared segments same segment number v Protection Use segment table entry Protection bitl Read-only, execute-only, read/writel Validatio