操作系统课程3_1.ppt

1、第三章 存储管理 Memory Management,存储器是计算机系统的重要组成部分，虽然内存容量在不断扩大，但内存仍是宝贵资源，如何提高主存储器利用率，并扩充主存，对主存信息实现有效保护是存储器管理主要任务，也是各种不同存储管理方法的目标 本章主要介绍内（主）存储器的管理,教学要求,熟悉存储管理目的和功能，掌握地址重定位的概念。 熟悉单一连续分配、固定分区分配、动态分区分配实现原理；掌握可变分区分配的数据结构和分配回收算法，熟悉可变分区零头和拼接技术 。 熟练掌握分页存储管理原理，熟练掌握分页存储管理基本的地址变换机构和具有快表的地址变换机构。 掌握分段存储管理原理和分段地址变换机构，掌握

2、分页和分段比较，熟悉分页和分段的共享，掌握段页式存储管理原理和地址变换机构。 掌握虚拟存储器的理论基础和定义，熟悉虚拟存储器实现方式和特征。 掌握请求分页的页表机制、缺页中断机构和地址变换机构，熟悉页面的分配和置换策略、页面的分配的算法。 熟练掌握最佳置换算法、先进先出（FIFO）置换算法、最近最久未使用置换算法LRU，熟悉Clock置换算法和页面缓冲算法。 掌握请求分段的段表机制、缺段中断机构和地址变换机构，熟悉分段的共享和保护。,本章目录,31 存储管理概述 32 存储器的连续分配 33存储器的离散分配 34虚拟存储器管理技术 35 Windows2000内存的管理 36 实验与习题,存储

3、层次结构,存储器的功能是保存数据，存储器的发展方向是高速、大容量和小体积。 内存在访问速度方面的发展：DRAM、SDRAM、SRAM等； 硬盘技术在大容量方面的发展：接口标准、存储密度等； 存储组织是指在存储技术和CPU寻址技术许可的范围内组织合理的存储结构。 其依据是访问速度匹配关系、容量要求和价格。 “寄存器-内存-外存”结构 “寄存器-缓存-内存-外存”结构； PC中的存储层次组织： 访问速度越慢，容量越大，价格越便宜； 最佳状态应是各层次的存储器都处于均衡的繁忙状态（如：缓存命中率正好使主存读写保持繁忙）；,3.1 存储管理概述,3.1.1存储层次结构,3.1.2 存储管理的功能,操作

4、系统为了有效地管理计算机的内存资源，应该具备以下四大功能：内存分配、内存保护、地址映射、内存扩充。 内存分配:为每一道程序分配内存空间，使它们“各得其所”；当程序撤消时，则收回它占用的内存空间。分配时注意提高存储器的利用率。 存储保护:确保每道程序都在自己的内存空间运行，互不干扰。保护系统程序区不被用户侵犯（有意或无意的），不允许用户程序读写不属于自己地址空间的数据（系统区地址空间，其他用户程序的地址空间）。 地址映射:用于把程序地址空间中的逻辑地址转换为内存空间中对应的物理地址。 内存扩充:从逻辑上来扩充内存容量，使用户认为系统所拥有的内存空间远比其实际的内存空间（硬件RAM）大的多。,3.

5、1.3 地址重定位,1、概念 程序在成为进程前的准备工作 编辑：形成源文件(符号地址) 编译：形成目标模块(模块内符号地址解析) 链接：由多个目标模块或程序库生成可执行文件(模块间符号地址解析) 装入：构造PCB，形成进程(使用物理地址) 逻辑地址Logical address （相对地址，虚地址）：用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式。 其首地址为0，其余指令中的地址都相对于首地址来编址。 不能用逻辑地址在内存中读取信息。 物理地址Physical address （绝对地址，实地址）：内存中存储单元的地址。物理地址可直接寻址,逻辑地址、物理地址和地址映射,

6、地址映射， Address binding,逻辑地址、物理地址和地址映射,地址映射Address binding,编译时期Compile time ：如果内存位置已知，可生成绝对代码；如果开始位置改变，需要重新编译代码 装入时期Load time : 如果内存位置在编译时不知道，则必须生成可重定位代码 relocatable code 执行时期Execution time : 如果进程在执行时可以在内存中移动，则地址绑定要延迟到运行时。需要硬件对地址映射的支持MMU (例如基址和限长寄存器),指令和数据地址绑定到内存地址可以在三个不同的阶段发生。,Multistep Processing of

7、 a User Program,2 地址重定位,重定位（地址映射， Address binding ） 把相对地址转换成内存中的物理地址，这个过程称为地址映射（map）。按照重定位的时机，可分为静态重定位和动态重定位。 静态重定位 静态重定位是在程序执行之前进行重定位（ Compile time ， Load time ）。它根据执行程序将要装入的内存起始地址，直接修改执行程序中的有关使用地址的指令。 在图中以“0”作为参考地址的执行程序，要装入以1000为起始地址的存储空间。显然在装入程序之前，程序必须做一些修改才能正确运行。,重定位,0： 10000： 100： LOAD 1，2500 1

8、0100： LOAD 1，12500 2500： 365 12500： 365 2600： 12600： (程序的地址空间) (内存的地址空间) 例如：LOAD 1，2500 这条指令是把相对地址为2500的存储单元的内容365装入1号累加器。而这时内容为365的存储单元的实际物理地址为12500（起始地址10000+相对地址2500），所以LOAD 1，2500 这条指令中的直接地址码要作相应的修改，即改为LOAD 1，12500。,重定位,动态重定位 动态重定位是指在程序执行过程中进行地址重定位（Execution time），即在每次访问内存单元前才进行地址变换。需要硬件重定位寄存器的支

9、持。 下图给出了动态重定位的示意图。,Dynamic relocation using a relocation register,3.链接,静态链接(static-linking)是在生成可执行文件时进行的。在目标模块中记录符号地址(symbolic address)，而在可执行文件中改写为指令直接使用的数字地址。,动态链接,动态链接(dynamic-linking)在装入或运行时进行链接。通常被链接的共享代码称为动态链接库(DLL, Dynamic-Link Library)或共享库(shared library)。 优点：共享：多个进程可以共用一个DLL，节省内存，减少文件交换。 部分装

10、入：一个进程可以将多种操作分散在不同的DLL中实现，而只将当前操作相应的DLL装入内存。 便于局部代码修改：即便于代码升级和代码重用；只要函数的接口参数（输入和输出）不变，则修改函数及其DLL，无需对可执行文件重新编译或链接。 便于运行环境适应：调用不同的DLL，就可以适应多种使用环境和提供不同功能。如：不同的显示卡只需厂商为其提供特定的DLL，而OS和应用程序不必修改。 缺点：链接开销：增加了程序执行时的链接开销； 管理开销：程序由多个文件组成，增加管理复杂度。,3.2 存储器的连续分配,3.2.1单一连续分配 这是一种最简单的存储管理方式，但只能用于单用户、单任务的操作系统，如在8位和16

11、位微机上CP/M和MS-DOS操作系统。它将内存分为两个区： 系统区：仅供操作系统使用，通常设置在内存的低段； 用户区：指除系统区以外的全部内存空间，提供给用户使用。 这种存储分配方式用在单用户、单任务的操作系统中。,单一连续分配,系统区 操作系统 用户区 用户程序,0 下限 上限,基址 长度,3.2.2固定分区(Fixed Partitioning)分配,分区存储管理是能够满足多道程序运行的最简单的存储器管理方案，其基本思想是将内存划分成若干个连续的区域，称为分区。每个分区只能存放一个程序，而且程序也只能在它所驻留的分区中运行。 固定分区是在作业装入之前，内存就被划分成若干个分区。划分工作可

12、以由系统管理员完成，也可以由操作系统实现。然而一旦划分完成，在系统运行期间不再重新划分，即分区的个数不可变，分区的大小不可变。 固定分区一般将内存的用户区域划分成大小不等的分区，以适应不同大小的作业的需要。系统有一张分区说明表，每个表目说明一个分区的大小、起始地址和是否已分配的使用标志。分区说明表和内存分配图如下所示。,固定分区分配,区号 大小 起址 标志 1 16KB20K已分配 2 32KB36K已分配 3 64KB68K已分配 4 124KB 132K 未分配 分区说明表,3.2.3可变（动态）分区 Dynamic Partitioning,动态地划分内存。即在作业装入内存时把可用内存“

13、切出”一个连续的区域分配给该作业，且分区大小正好适合作业的需要。,动态分区的数据结构,空闲区表形式 空闲分区表为每个尚未分配的分区设置一个表项，包括分区的序号、大小、始址和状态。 空闲区链形式 为了实现对空闲分区的分配和链接，在每个分区的起始部分，设置一些用于控制分区分配的信息（如分区的大小和状态位），以及用于链接其它分区的前向指针；在分区尾部，则设置了一个后向指针，为了检索方便也设置了控制分区分配的信息。然后，通过前、后向指针将所有的分区链接成一个双向链表。,分配和释放,在分配时，首先找到一个足够大的空闲分区，即这个空闲区的大小比作业要求的要大，系统则将这个空闲分区分成两部分：一部分成为已分

14、配的分区，剩余的部分仍作为空闲区。 在回收撤除作业所占领的分区时，要检查回收的分区是否与前后空闲的分区相领接，若是，则加以合并，使之成为一个连续的大空间。,动态分区分配算法,First-fit （首次适应） :从空闲分区表的第一个表目起查找该表，把最先能够满足要求的空闲区分配给作业，这种方法目的在于减少查找时间。为适应这种算法，空闲分区表（空闲区链）中的空闲分区要按地址由低到高进行排序。该算法优先使用低址部分空闲区，在低址空间造成许多小的空闲区，在高地址空间保留大的空闲区。 设作业分配序列： A：12K， B：10K ，C： 3K,分区分配算法：首次适应、最佳适应、最差适应法、下次适应,动态分

15、区分配算法,Best-fit （最佳适应） :它从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区，这种方法能使碎片尽量小。为适应这种算法，空闲分区表（空闲区链）中的空闲分区要按大小从小到大进行排序，自表头开始查找到第一个满足要求的自由分区分配。该算法保留大的空闲区，但造成许多小的空闲区。 作业分配序列： A：12K ，B： 3K ，C： 10K,动态分区分配算法,Worst-fit （最差适应） :从所有未分配的分区中挑选最大的且大于和等于作业大小的分区分给要求的作业；空闲分区按大小由大到小排序。该算法使小的空闲区减少，但造成大的空闲区不够大 作业分配序列： A：12K， B：3K，

16、C：10K,在速度和存储的利用上，首次适应和最佳适应要比最差适应好。,动态分区分配算法,Next Fit（下次适应）：类似首次适应，每次分区时，总是从上次查找结束的地方开始，只要找到一 个足够大的空白区，就把它划分后分配出去。 作业分配序列： A：12K， B：10K， C： 3K,动态分区回收算法,当一个作业运行完毕释放内存时，系统根据释放区的首地址，从空闲区说明表中找到相应的插入点，此时可能出现下列四种情况（如图3-9所示，其中F1，F2表示回收区的前、后空闲区）： 当回收区既不与F1领接，又不与F2领接时（如图3-9（a），应为回收区单独建立一项新表目，填写回收区的起址和大小，并根据其起

17、址，插入到空闲区说明表的适当位置。 当回收区只与插入点的前一个分区F1相领接时（如图3-9（b），应将回收区与插入点的前一个分区合并，不再为回收区分配新的表目，而只需修改F1分区表目的大小即可。,动态分区回收算法,当回收区只与插入点的后一个分区F2相领接时（如图3-9（c），将把两个空闲区合并，修改F2分区的表目，把回收区的起址作为新空闲区的起址，大小为两个分区之和。 当回收区与插入点的前、后两个分区（F1和F2）都相领接时（如图3-9（d），合并三个分区，用F1表目的起址作为新空闲区的起址，修改其大小为三块分区之和，最后取消F2的表目。,A,动态分区零头和拼接技术,动态分区也有零头问题。在系

18、统不断地分配和回收中，必定会出现一些不连续的小的空闲区，称为外零头或外碎片。虽然可能所有零头的总和超过某一个作业的要求，但是由于不连续而无法分配。 解决零头的方法是拼接或紧缩（Compaction），即向一个地址方向（例如向低地址端）移动已分配的作业，使那些零散的小空闲区在另一方向连成一片。 分区的拼接技术，一方面是要求能够对作业进行重定位，另一方面系统在拼接时要耗费较多的时间。采用拼接技术的可变分区又称可重定位分区。 什么时候紧缩？ 紧缩的开销。,内存保护Memory Protection,重定位（基址base）寄存器Relocation-register策略用来保护用户进程同其他进程和改变

19、的操作系统代码和数据分开，重定位寄存器包含最小物理地址的值。 界限（限长）寄存器limit register包含逻辑地址的范围，每个逻辑地址必需比限长寄存器的值小。,3.3 存储器的离散分配,连续分配会形成许多“碎片”，为了减少碎片提高存储器的利用率而引入了离散分配方式,它将一个用户的程序划分成若干个大小相等的页再离散地分配到内存的多个不相邻的区域中。 存储管理方法： 分页 分段 段页式,3.3.1纯分页(Paging)存储管理,1分页存储管理原理 将物理内存空间划分成大小相等的块，称为帧frames，或物理块或页框（size is power of 2, between 512 bytes

20、and 8192 bytes ） 。如：Linux、Windows for x86: 4K/帧。 将一个进程的地址空间划分成与帧相同大小的块，称为页pages 。 在为进程分配内存时，将进程中的若干页离散地装入不相邻接的物理块中。 每个进程只有最后一页可能装不满一物理块，平均产生半页“页内碎片”。 分页存储管理基本解决了“碎片”问题，提高了存储器的利用率。 纯分页存储管理是指一个进程的所有页全部装入内存的物理块中才能运行。,分页存储管理原理,分页系统的地址结构如图所示，它由两部分组成： 前一部分为页号P（ Page number ）； 后一部分为页内位移量W（ Page offset ），即页

21、内地址。 图中的地址长度为31位，其中011位为页内地址（每页的大小为4KB），1231位为页号，所以允许地址空间的大小最多为1M个页。,p d,31 Page number 12 11 page offset 0,地址结构,2页表,系统设置一个页表用于把逻辑地址转换为物理地址。 页表page table列出了进程的逻辑页与其在主存中的物理帧间的对应关系。 每个页在页表中占一个表项，记录该页在内存中对应的物理块号（页号可以省略）。 进程在执行时，通过查找页表，就可以找到每页所对应的物理块号。,Paging Example,Paging Example,Paging example for a

22、32-byte memory with 4-byte page,0 1 2 3 4 5 6 7,地址 页号,3地址变换机构,地址变换机构的基本任务是利用硬件实现查页表把用户进程中的逻辑地址变换成内存中的物理地址。 系统中设置页表寄存器，用来存放页表的始址和页表的长度。 在进程未执行时，每个进程对应的页表的始址和长度存放在进程的PCB中，当该进程被调度时，就将它们装入页表寄存器。,Address Translation Architecture,例：指令 LOAD 1,2500 的地址变换过程。16位地址结构，p：6位,d：10位,地址变换实现,越界中断,块号5 块内地址452,页 号2 页内地

23、址452,页表始址页表长度,2 4 5,页表寄存器,页号,块 号,0 1 2,2500（逻辑地址）=5*1024+452=5572（物理地址）,分页存储管理逻辑地址到物理地址地址变换的计算,假设页长为1KB(1024字节)，逻辑地址为2500(十进制)。利用页表把逻辑地址变换成物理地址计算步骤如下： (1)将虚地址分离成页号P和页内地址d： 页号P（逻辑地址页大小）取整（2500/1024）取整2 页内地址d逻辑地址 mod 页大小=2500 mod 1024=452 (2)根据页号查页表，由页表项读出块号： 由页号 P2查页表得块号为5 (3)块号和页内地址构成物理地址： 物理地址块号页大小

24、页内地址= 5*1024+452 =5572,分页存储管理逻辑地址到物理地址地址变换的计算例,逻辑地址09C4H转换成物理地址： 10进制与进制16关系 0 0 0 0页 1KB 1024 400H 1页 2KB 2048 800H 2页 3KB 3072 C00H3页 4KB 4096 1000H4页 5KB 5120 1400H 5页 6KB 6144 1800H 6页 C00H09C4H800H页号P=2 页内位移W逻辑地址该页起始地址09C4H800H1C4H 查页表：页2 块号5 物理地址该物理块起始地址 +页位移 = 1400H + 1C4H = 15C4H 计算逻辑地址 3000

25、（10进制）、0560H、4025的物理地址？,4快表,如果页表存放在内存中，则每次访问内存时，都要先访问内存中的页表，然后根据所形成的物理地址再访问内存。这样CPU必须访问两次内存，从而使计算机的处理速度降低了1/2。 为提高地址变换的速度，在地址变换机构中增设了一个具有按内容查找、并行查询功能的特殊的高速缓冲存储器，称为“联想存储器(AssosiativeMemory) ” 或“快表”，或称为“关联存储器(TLB, Translation Look-aside Buffer)”，用以存放当前访问的那些页表项，每个页表项包括页号和相应的块号（页号不能省略）。 由于成本的原因，快表不可能做得很

26、大，通常只能存放16-512个页表项。例如，在Intel80486中有32个。这对中、小型进程来说，已可能把全部页表项放入快表中；但对于大进程来说，则只能将一部分页表放入快表中。,Paging Hardware With TLB,有效访问时间,由于对程序和数据的访问往往带有局限性，所以快表的命中率可以达到80%99%。例如，假设检索联想存储器的时间为20ns，访问内存的时间t为100ns，访问联想存储器的的命中率为90%。 有效访问时间Effective Access Time (EAT) EAT = (t + ) + (2t + )(1 ) =(100+20)*90%+(2*100+20)*

27、10% = 130ns 如果不引入快表，其访问时间为200ns。,页表结构,分级页表 Hierarchical Page Tables 哈希页表 Hashed Page Tables 反向(反置)页表 Inverted Page Tables,Shared Pages,In a time-sharing environment 40 users execute a text editor. The text editor process consists 150KB code and 50 KB data. Without sharing (150KB + 50KB)*40 = 200KB *

28、 40 = 8000KB sharing 150KB + 50KB*40 = 2000KB + 150KB = 2150KB Other heavily used programs can also be shared compilers, window systems, run-time libraries, database systems, and so on. Reentrant Code(重入代码)、 Pure Code(纯代码)。它是一种允许多个进程同时访问的代码，但是不允许任何进程对其进行修改的代码。,Shared Pages Example,3.3.2 分段(Segmentat

29、ion)存储管理,1分段存储管理的引入 从固定分区到可变分区，进而又发展到分页系统的原因都是为了提高内存的利用率，然而分段存储管理的引入，是为了满足用户需要。 用户观点：把内存看作一组不同长度的段的集合 A program is a collection of segments. A segment is a logical unit ,such as: main program, procedure, function, method, object, local variables, global variables, common block, stack, symbol table,

30、arrays 没有内碎片 外碎片可以通过内存紧缩来消除,Users View of a Program,Logical View of Segmentation,2分段系统的基本原理,在分段存储管理方式中，作业的地址空间被划分为若干个段，每个段定义了一组完整的逻辑信息，每个段都有自己的名字，编译后都是从零开始编址的一段连续的地址空间，段的长度由相应逻辑信息组的长度决定，因而各段长度是不等的。 分段系统的地址结构如图所示，逻辑地址由段号和段内地址两部分组成。在该地址结构中，允许一个作业最多有64 K个段，每个段的最大长度为64 KB。,31 16 15 0,3段表,与分页式存储管理相似，在分段式

31、存储管理系统中为每个进程建立一张段映射表，简称为“段表”。 每个段在表中占有一表项，在其中记录了该段在内存中的起始地址（又称为“基址”）和段的长度。 进程在执行中，通过查段表来找到每个段所对应的内存区。可见，段表实现了从逻辑段到物理内存区的映射。,Example of Segmentation,4地址变换机构,为了实现从逻辑地址到物理地址的变换功能，系统中设置了段表寄存器，用于存放段表始址和段表长度。 在进行地址变换时，系统将逻辑地址截成段号S与段内地址d，将逻辑地址中的段号S与段表长度TL进行比较。 若 STL，表示段号太大，访问越界，于是产生越界中断信号； 若STL,未越界，则根据段表的始

32、址和该段的段号，计算出该段对应段表项的位置，从中读出该段在内存中的起始地址，然后再检查段内地址d是否超过该段的段长SL。 若超过，即dSL，同样发出越界中断信号； 若dSL，未越界，则将该段的基址与段内地址d相加，得要访问的内存物理地址。,Segmentation Hardware,地址变换过程,段号 段长SL 基址,（2，400）=120k+400 （3，852）=50k+852 （1，12220）=trap，addressing error,5共享,段是信息的逻辑单位,因此分段系统的一个突出的优点是易于实现段的共享。即允许若干个进程共享一个或多个段，而且对段的保护也十分简单。 在实现段共享时，需要用到可重入代码(Reentrant Code)又称为“纯代码”(Pure Code)。它是一种允许多个进程同时访问的代码，是一种不允许任何进程对其进行修改的代码。但在每个进程中，配以局部数据区，将在执行中可能改变的部分，拷贝到该数据区，这样，程序在执行时，只对该数据区(属于该进程私有)中的内容进行修改，而不去改变共享的代码，这时的可共享代码即成为可重入代码。,Sharing of Segments,页式管理和段式管理的比较,分