西安交通大学操作系统原理课件第八章.ppt

《西安交通大学操作系统原理课件第八章.ppt》由会员分享，可在线阅读，更多相关《西安交通大学操作系统原理课件第八章.ppt（122页珍藏版）》请在三一办公上搜索。

1、Chapter8 Memory Management,Background（背景）Contiguous Allocation（连续分配）Paging（分页）Segmentation（分段）Segmentation with Paging（段页式）Examples,存储层次结构,8.1 Background,计算机存储系统的设计主要考虑三个问题：容量、速度和成本。,8.1 Background,Program must be brought into memory and placed within a process for it to be executed.（程序要得以运行:必须创建一个进

2、程，并且送入内存）User programs go through several steps before being executed. （用户程序在执行之前必需经历很多步骤）,程序的装入和链接,源程序,编译,目标模块,库,.,链接程序,装入模块,装入程序,内存,Multistep Processing of a User Program,Logical vs. Physical Address Space,Address Space地址空间:一个目标程序所限定的地址范围地址空间是逻辑地址的集合Logical/Virtual address:An address viewed by the

3、 user processThe abstraction provided by the OS存储空间是物理地址的集合Physical addressAn address viewed by the physical memory,地址重定位,将程序装入到与其地址空间不一致的物理空间，所引起的一系列地址变换过程。静态地址重定位在装入一个作业时，把作业中的指令地址全部转换为绝对地址,在作业执行过程中就无须再进行地址转换工作。动态地址重定位在程序执行过程中，在CPU访问内存之前,将要访问的程序或数据地址转换成内存地址. 动态重定位依靠硬件地址变换机构完成。,Dynamic Address Tran

4、slation,UserProcess,Translator(MMU),Physicalmemory,Virtualaddress,Physicaladdress,Binding of Instructions and Data to Memory,Address binding of instructions and data to memory addresses can happen at three different stages.（指令和数据绑定到内存地址可以在3个不同的阶段发生。）,Compile time（编译时期）: If memory location known a pr

5、iori, absolute code can be generated; must recompile code if starting location changes.（如果内存位置已知，可生成绝对代码；如果开始位置改变，需要重新编译代码）,Load time（装入时期）: Must generate relocatable code if memory location is not known at compile time.（如果存储位置在编译时不知道，则必须生成可重定位代码）,Execution time（执行时期）: Binding delayed until run time

6、 if the process can be moved during its execution from one memory segment to another. Need hardware support for address maps (e.g., base and limit registers). （如果进程在执行时可以在内存中移动，则地址绑定要延迟到运行时。需要硬件对地址映射的支持，例如基址和限长寄存器）,Memory-Management Unit (MMU),Hardware device that maps virtual to physical address.（实

7、现虚拟地址映射到物理地址的硬件）In MMU scheme, the value in the relocation register is added to every address generated by a user process at the time it is sent to memory.（在MMU策略中，当用户进程被装入内存时,基址寄存器中的值被加入到用户进程所产生的每个地址中。）,Memory-Management Unit (MMU),内外存间的数据交换,overlay覆盖由用户程序控制要求用户清楚地了解程序的结构，并指定各程序段调入内存的先后次序，它是一种早期的主存

8、扩充的方式swapping交换由操作系统控制利用外存空间（进程交换区），通过对进程实体的整体交换，来满足用户进程的内存需要。它的主要特点是打破了进程运行的驻留性,overlay,主程序(30K),Swapping,A process can be swapped temporarily out of memory to a backing store, and then brought back into memory for continued executionMajor part of swap time is transfer time; total transfer time is

9、directly proportional to the amount of memory swappedModified versions of swapping are found on many systems (i.e., UNIX, Linux, and Windows),Swapping,操作系统,B,C,D,操作系统,D,C,操作系统,A,D,C,Schematic View of Swapping,常用的内存信息保护方法有：1 上下界地址寄存器2 存储键,内存保护,界地址寄存器,界地址寄存器是广泛使用的一种存储保护技术,机制简单,易于实现实现方法：在CPU中设置一对下限寄存器和

10、上限寄存器存放用户作业在主存中的下限和上限地址也可将一个寄存器作为基址寄存器，另一寄存器作为限长寄存器（指示存储区长度）每当CPU要访问主存，硬件自动将被访问的主存地址与界限寄存器的内容进行比较，以判断是否越界如果未越界，则按此地址访问主存，否则将产生程序中断越界中断（存储保护中断）,Base and Bounds,Process has illusion of running on its own dedicated machine with memory 0, bound),Physical memory,0,base,base + bound,physical memory size,v

11、irtual memory,0,bound,存储键,每个存储块有一个由二进制位组成的存储保护键一用户作业被允许进入主存，OS分给它一个唯一的存储键号,并将分配给该作业各存储块的存储键也置成同样键号当OS挑选该作业运行时，OS将它的存储键号放入程序状态字PSW存储键（“钥匙”）域中每当CPU访问主存时，都将该主存块的存储键与PSW中的“钥匙”进行比较如果相匹配，则允许访问，否则，拒绝并报警,8.2 存储器管理方式,连续分配方式：为一个程序分配一段连续的内存空间，主要有：单一连续区管理方式；多分区管理方式，是一种可用于多道程序的较简单的存储管理方式，又分为:固定分区方式可变分区方式,8.2 存储器

12、管理方式,离散分配方式：减少连续分配所产生的碎片，提高内存的利用率，将一个用户程序离散地分配到内存中的多个不相连接的区域中分页存储管理方式分段存储管理方式段页式存储管理方式,虚拟存储管理方式：满足用户对大容量内存的需要，提高内存利用率。请求分页管理方式 请求分段管理方式请求段页式管理方式,8.2 存储器管理方式,8.2.1Contiguous Allocation,Main memory usually divided into two partitions:（主存通常被分为两部分）Resident operating system, usually held in low memory wi

13、th interrupt vector.（为操作系统保留的部分，通常与中断矢量保存在内存低端。）User processes then held in high memory.（用户进程保存在内存高端）,8.2.1 Contiguous Allocation,Single-partition allocation单一分区分配Multiple-partition allocation多分区分配Fixed Partitioning固定分区Dynamic Partitioning可变分区/动态分区Dynamic Relocationable Partitioning动态可重定位分区,Single-p

14、artition allocation（单一分区分配）,内存分成两部分:OS区用户区用户区只能容纳一道作业,存储保护:Relocation-register scheme used to protect user processes from each other, and from changing operating-system code and data. （基址寄存器策略用来保护用户进程（同操作系统代码和数据分开。）Relocation register contains value of smallest physical address; limit register conta

15、ins range of logical addresses each logical address must be less than the limit register. （基址寄存器包含最小物理地址的值；限长寄存器包含逻辑地址的范围，每个逻辑地址必须小于限长寄存器的值。）,Single-partition allocation（单一分区分配）,Hardware Support for Relocation and Limit Registers,Fixed Partitioning,固定分区是在作业装入之前，内存就被划分成若干个固定大小的连续分区。划分工作可以由系统管理员完成，也可以

16、由操作系统实现。一旦划分完成，在系统运行期间不再重新划分，即分区的个数不可变，分区的大小不可变，又称为静态分区。,Fixed Partitioning,划分分区的方法如下：分区大小相等：只适用于多个大小相同程序的并发执行，缺乏灵活性。分区大小不等：多个小分区、适量的中等分区、少量的大分区。根据程序的大小，分配当前空闲的、适当大小的分区。,固定分区(大小相同),固定分区(多种大小),Fixed Partitioning,一般将内存的用户区域划分成大小不等的分区，可适应不同大小的作业需要。 系统有一张分区说明表，每个表目说明一个分区的大小、起始地址和是否已分配的使用标志,Fixed Partiti

17、oning,分区说明表,内存分配图,Fixed Partitioning,优点：易于实现，开销小。缺点：分区大小固定: 内碎片分区总数固定: 限制并发执行的进程数目,要求Xk大小分区,取分区说明表第一项,状态位置正在使用,取下一表项,无法分配,该分区空闲？,分区长度Xk?,表结束？,返回分区号,否,否,否,是,是,是,固定分区分配算法,Dynamic Storage-Allocation,Multiple-partition allocation（多分区分配）分区的划分是动态的,不是预先确定的When a process arrives, it is allocated memory from

18、 a hole large enough to accommodate it.（当一个进程到来的时候，它将从一个足够容纳它的分区中分配内存。）,OS,process 5,process 8,process 2,OS,process 5,process 2,OS,process 5,process 2,OS,process 5,process 9,process 2,process 9,process 10,空闲分区的管理,空闲分区表,前向指针,后向指针,空闲分区链,可变分区分配算法,分区分配算法：寻找某个空闲分区，若大于要求，则将该分区分割成两个分区，其中一个分区为要求的大小并标记为“占用”，

19、而另一个分区为余下部分并标记为“空闲”。分区分配的先后次序通常是从内存低端到高端。分区释放算法：需要将相邻的空闲分区合并成一个空闲分区。(这时要解决的问题是：合并条件的判断),可变分区分配算法框图,Dynamic Storage-Allocation Problem,First-fit（首次适应）: Allocate the first hole that is big enough.（分配最先找到的合适的分区。）Best-fit（最佳适应）: Allocate the smallest hole that is big enough; must search entire list, unl

20、ess ordered by size. Produces the smallest leftover hole. （搜索整个序列，找到适合条件的最小的分区进行分配。）Worst-fit（最差适应）: Allocate the largest hole; must also search entire list. Produces the largest leftover hole.（搜索整个序列，寻找最大的分区进行分配。）,首次适应算法（First Fit）,从空闲分区表的第一个表目开始查找，把找到的第一个满足要求的空闲区分配给作业，目的在于减少查找时间。通常将空闲分区表（空闲区链）中的空闲

21、分区按地址由低到高进行排序。特点：分配和释放的时间性能较好，较大的空闲分区可以被保留在内存高端。随着低端分区不断划分而产生较多小分区，每次分配时查找时间开销会增大。,从该空闲区中截取所需大小，修改调整分区表,从空闲分区表第一表目顺序查找,从分区表中移去该表目，调整分区表,取下一表项,无法分配,该 空闲区长度SIZE？,该 空闲区长度=SIZE？,表目查完？,返回分配起始地址,否,否,否,是,是,是,First-fit,循环首次适应算法(Next Fit),循环首次适应算法：是首次适应算法的变种。在分配内存空间时，不再每次从表头（链首）开始查找，而是从上次找到的空闲区的下一个空闲区开始查找（并采

22、用循环查找的方式），直到找到第一个能满足要求的空闲区为止，并从中划出一块与请求大小相等的内存空间分配给作业。特点：算法的分配和释放的时间性能较好，使空闲分区分布得更均匀较大的空闲分区不易保留,最佳适应算法（Best Fit）,从全部空闲区中找出能满足作业要求的、且最小的空闲分区.能使碎片尽量小为提高查找效率，空闲分区表（空闲区链）中的空闲分区要按从小到大进行排序，自表头开始查找到第一个满足要求的自由分区分配特点：从个别来看，外碎片较小，但从整体来看，会形成较多无法利用的碎片。较大的空闲分区可以被保留。,动态分区分配算法举例,Lastallocatedblock (14K),分配前,分配后,8K

23、,8K,12K,12K,22K,18K,6K,6K,8K,8K,14K,14K,6K,2K,36K,20K,Best Fit,First Fit,例：需分配一个16KB分区,Next Fit,动态重定位分区分配,动态分区的碎片问题:在系统不断地分配和回收中，必定会出现一些不连续的小的空闲区，称为外碎片。虽然可能所有碎片的总和超过某一个作业的要求，但是由于不连续而无法分配。解决碎片的方法是拼接（或称紧凑），即向一个方向（例如向低地址端）移动已分配的作业，使那些零散的小空闲区在另一方向连成一片。分区的拼接技术，一方面要求能够对作业进行重定位，另一方面系统在拼接时要耗费较多的时间。,Fragment

24、ation,动态重定位分区分配,实现紧凑的技术必须获得硬件支持只有具有动态重定位硬件机构的计算机系统，才有可能采用动态重定位可变分区管理技术，系统的硬件包括重定位寄存器和加法器。,8.2.2 Paging,分页存储管理是解决存储碎片的一种方法。动态重定位是解决存储碎片问题的一种途径，但要移动大量信息从而浪费处理机时间,代价比较高,这是因为这种分配要求把作业必须安置在一连续存储区内的缘故,而分页存储管理正是要避开这种连续性要求。,8.2.2 Paging,Divide physical memory into fixed-sized blocks called frames (size is p

25、ower of 2, between 512 bytes and 8192 bytes).（物理内存分成大小固定的块,称为物理块或页框)Divide logical memory into blocks of same size called pages.（逻辑内存也分为固定大小的块，叫做页。）To run a program of size n pages, need to find n free frames and load program.（运行一个有N页大小的程序，需要找到N个空的页框装入程序。）Set up a page table to translate logical to

26、physical addresses. （建立一个页表，把逻辑地址转换为物理地址。）Internal fragmentation.（内碎片。）,Paging Model of Logical and Physical Memory,Paging Example,Paging,Address Translation Scheme,Address generated by CPU is divided into:Page number (p) used as an index into a page table which contains base address of each page in

27、 physical memoryPage offset (d) combined with base address to define the physical memory address that is sent to the memory unit,page number,page offset,p,d,m - n,n,Paging Hardware,地址结构,图中的地址长度为32位，允许地址空间的大小最多为1M个页。,程序经过编译链接后形成逻辑地址，对某特定机器其地址结构是一定的。,Page table,实现从页号到物理块号的映射,Implementation of Page Tab

28、le,Page table is kept in main memoryPage-table base register (PTBR) points to the page tablePage-table length register (PRLR) indicates size of the page tableIn this scheme every data/instruction access requires two memory accesses:One for the page table One for the data/instruction,Implementation o

29、f Page Table (Cont.),The two memory access problem can be solved by the use of a special fast-lookup hardware cache called associative memory or translation look-aside buffers (TLBs),Associative Memory,Associative memory parallel search Address translation (p, d)If p is in associative register, get

30、frame # outOtherwise get frame # from page table in memory,Page #,Frame #,Paging Hardware With TLB,Effective Access Time,Associative Lookup = time unit（设联想寄存器的查找需要时间为）Assume memory cycle time is 1 microsecond（假设内存一次存取要1微秒）Hit ratio percentage of times that a page number is found in the associative r

31、egisters; ration related to number of associative registers.（命中率在联想寄存器中找到页号的几率，与联想寄存器的大小有关。）Hit ratio = Effective Access Time (EAT)（有效存取时间）EAT = (1 + ) + (2 + )(1 )= 2 + ,Effective Access Time,例如，假设检索联想存储器的时间为20ns，访问内存的时间为100ns，访问联想存储器的命中率为85%，则CPU存取一个数据的平均时间:T=0.85*120+0.15*220=135ns，访问时间只增加35%。如果不

32、引入联想存储器，其访问将延长一倍（达200ns）。,基本的地址变换机构,实现从逻辑地址到物理地址的转换:将用户程序中的页号变换成内存中的物理块号地址变换机构：页表寄存器有效地址寄存器（逻辑地址寄存器）物理地址寄存器页表PCB中增加存放页表始址和页表长度的项,地址变换过程,按页的大小分离出页号和位移量，放入有效地址寄存器中将页号与页表长度进行比较，如果页号大于页表长度，越界中断；以页号为索引查找页表:将页表始址与页号和页表项长度的乘积相加，便得到该表项在页表中的位置，于是可从中得到该页的物理块号；将该物理块号装入物理地址寄存器的高址部分；将有效地址寄存器中的位移量直接复制到物理地址寄存器的低位部

33、分，从而形成内存地址。,分页地址变换机构工作原理,页式地址变换举例,页式地址变换,虚地址（逻辑地址、程序地址）以十六进制、八进制、二进制的形式给出将虚地址转换成二进制的数；按页的大小分离出页号和位移量（低位部分是位移量，高位部分是页号）；将位移量直接复制到内存地址寄存器的低位部分；以页号查页表，得到对应页装入内存的块号，并将块号转换成二进制数填入地址寄存器的高位部分，从而形成内存地址。,页式地址变换,虚地址以十进制数给出页号虚地址页大小位移量虚地址 mod 页大小以页号查页表，得到对应页装入内存的块号内存地址块号页大小位移量,页式地址变换举例,例1：有一系统采用页式存储管理，有一作业大小是8K

34、B，页大小为2KB，依次装入内存的第7、9、A、5块，试将虚地址0AFEH，1ADDH转换成内存地址。虚地址0AFEH0000 1010 1111 1110P1 W010 1111 1110MR0100 1010 1111 1110 4AFEH,页式地址变换举例,虚地址1ADDH0001 1010 1101 1101P3W010 1101 1101MR0010 1010 1101 11012ADDH,页式地址变换举例,例2：有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、10、5块，试将虚地址7145，3412转换成内存地址。,页式地址变换举例,虚地址

35、3412P3412 2048 1W 3412 mod 2048 1364MR=9*2048+1364=19796虚地址3412的内存地址是：19796,页式地址变换举例,虚地址 7145P7145 2048 3W7145 mod 2048 1001MR=5*2048+1001=11241虚地址7145的内存地址是：11241,Memory Protection,Memory protection implemented by associating protection bit with each frame.（内存的保护由与每个页框相连的保护位来实现。）保护位指出对某一页的访问权限:读写Va

36、lid-invalid bit attached to each entry in the page table（有效-无效位附在页表的每个表项中）:“valid” indicates that the associated page is in the process logical address space, and is thus a legal page.（“有效”表明相关的页在进程的逻辑地址空间，是一个合法的页。）“invalid” indicates that the page is not in the process logical address space.（“无效”表明

37、页不在进程的逻辑地址空间中。）,Memory Protection,Structure of the Page Table,Hierarchical PagingHashed Page TablesInverted Page Tables,Hierarchical Page Tables,Break up the logical address space into multiple page tablesA simple technique is a two-level page table,Two-Level Page-Table Scheme,Intel 80386的逻辑地址有232B，

38、如页面大小为4KB（212B），则页表项达1M个，设每个页表项占用4B，则每个进程的页表占用4MB内存空间，还要求是连续的，显然这是不现实的。解决:在80386中，为了减少页表所占用的连续的内存空间，采用了两级页表机制.,Two-Level Page-Table Scheme,将页表进行分页,并进行编号页表分页存放在不同的物理块中外层页表（页表目录），即第一级页表，指出页表分页的物理地址第二级页表（即页表分页），指出每个页对应的物理块号,Two-Level Page-Table Scheme,Two-Level Paging Example,A logical address (on 32-b

39、it machine with 4K page size) is divided into（一个逻辑地址被分为）:a page number consisting of 20 bits.（一个20位的页号。）a page offset consisting of 12 bits.（一个12位的偏移。）Since the page table is paged, the page number is further divided into（页号被分为）:a 10-bit page number. （一个10位的页号。）a 10-bit page offset.（一个10位的偏移。）,page

40、number,page offset,p1,p2,d,10,10,12,Address-Translation Scheme,Address-translation scheme for a two-level 32-bit paging architecture（一个两级32位分页结构的地址转换机制）,Three-level Paging Scheme,Multilevel Paging and Performance,多级页表的引入，使逻辑地址到物理地址的变换时间增加了许多:二级页表需三次访存,三级页表需四次访存,四级页表需五次访存Cache hit rate of 98 percent

41、yields（如果TLB的命中率有98%）:effective access time = 0.98 x 120 + 0.02 x 520= 128 nswhich is only a 28 percent slowdown in memory access time.（这只把内存存取时间降低了28%。）,Hashed Page Tables,Common in address spaces 32 bitsThe virtual page number is hashed into a page tableThis page table contains a chain of elements

42、 hashing to the same locationVirtual page numbers are compared in this chain searching for a matchIf a match is found, the corresponding physical frame is extracted,Hashed Page Table,Inverted Page Table,通常的页表为每个进程设置一张页表，其不足为浪费内存空间解决：倒置页表，按照整个物理内存建造一张表One entry for each real page of memory.（内存中的每一块在表

43、中占一项。）Entry consists of the virtual address of the page stored in that real memory location, with information about the process that owns that page.（每项包含进程的逻辑页号和进程标示。）,Inverted Page Table,Decreases memory needed to store each page table, but increases time needed to search the table when a page refe

44、rence occurs. 减少了页表占用的内存空间量,但是增加了查找表的时间，因为页表是按物理块的顺序组织的，而查找是按虚地址进行的。,Inverted Page Table Architecture,Shared Pages Example,Three processes share ed1,ed2 and ed3,优点：没有外碎片，每个内碎片不超过页大小。一个程序不必连续存放。缺点：程序全部装入内存。,纯分页的特点,8.2.3 Segmentation,Memory-management scheme that supports user view of memory. （分段内存管理机

45、制是从用户观点出发的，即为了方便用户。）A program is a collection of segments. A segment is a logical unit such as（一个程序是一些段的集合，一个段是一个逻辑单位，如：）:main program,procedure, function,local variables, global variables,common block,stack,symbol table, arrays,Users View of a Program,Logical View of Segmentation,1,3,2,4,user space

46、,physical memory space,Segmentation,data,stack,code,Physical memory,Virtual memorysegment 1,Virtual memorysegment 3,Virtual memorysegment 0,6ff0,4ff0,fff0,46ff4000,2fff2000,4ff0,Segmentation Architecture,Logical address consists of a two tuple:,Segment table maps two-dimensional physical addresses;

47、each table entry has:base contains the starting physical address where the segments reside in memorylimit specifies the length of the segmentSegment-table base register (STBR) points to the segment tables location in memorySegment-table length register (STLR) indicates number of segments used by a p

48、rogram; segment number s is legal if s STLR,Segmentation Hardware,Example of Segmentation,地址变换过程,系统将逻辑地址中的段号S与段表长度TL进行比较。若 STL，访问越界；若未越界，则根据段表的始址和该段的段号，计算出该段对应段表项的位置，从中读出该段在内存中的起始地址；然后再检查段内地址d是否超过该段的段长SL。若超过，即 dSL，同样发出越界中断信号；若未越界，则将该段的基址与段内地址d相加，得到要访问的内存物理地址。,地址变换,Segmentation Architecture (Cont.),P

49、rotection. With each entry in segment table associate（保护，每个段表的表项有）:validation bit（有效位） = 0 illegal segmentread/write/execute privileges（读/写/执行权利）Since segments vary in length, memory allocation is a dynamic storage-allocation problem.（由于段的各个长度不同，内存分配是一个动态存储分配问题。）,Segmentation Architecture (Cont.),Re

50、location.（重定位）dynamic（动态）by segment table （通过段表来执行）Sharing.（共享）shared segments: code segment, data segmentcode segment : same segment number （同样的段号）Allocation.（分配）first fit/best fit（首次/最佳适配）external fragmentation（外碎片）,程序通过分段(segmentation)划分为多个模块，如代码段、数据段、共享段。可以分别编写和编译可以针对不同类型的段采取不同的保护可以按段为单位来进行共享，包括