第4章_存储管理

1、11第第 四四 章章谌谌 卫卫 军军清华大学清华大学操作系统操作系统22第四章第四章 存储管理存储管理1. 单道程序存储管理单道程序存储管理2. 分区存储管理分区存储管理3. 页式和段式存储管页式和段式存储管理理4. 覆盖技术与交换技覆盖技术与交换技术术5. 虚拟存储技术虚拟存储技术33即使是简单的、老的存储管理方案仍然即使是简单的、老的存储管理方案仍然有必要掌握。有必要掌握。 有些老的概念仍然有用有些老的概念仍然有用使用何种存储管理方案取决于硬件平台使用何种存储管理方案取决于硬件平台 有些方案需要有些方案需要硬件支持硬件支持； 手持设备和嵌入式系统等新的硬件平台可手持设备和嵌入式系统等新的硬

2、件平台可能只有基本的硬件支持。能只有基本的硬件支持。44理想中的存储器：理想中的存储器：更大、更快、更便宜的更大、更快、更便宜的非易失性非易失性存储器存储器。实际中的存储器实际中的存储器：存储器层次结构存储器层次结构（本图摘自（本图摘自Andrew S. Tanenbaum： “Modern Operating Systems” ）实际中的存储器实际中的存储器：存储管理？存储管理？55我们主要考察我们主要考察内存内存（Main Memory）的）的管理。管理。664.1 单道程序存储管理单道程序存储管理内存分为两个区域：内存分为两个区域：系统区系统区，用户区用户区。每次把一个应用程序装入到用户

3、区运行，每次把一个应用程序装入到用户区运行，由它和操作系统来共享内存。当它运行由它和操作系统来共享内存。当它运行结束后，操作系统再装入一个新的程序结束后，操作系统再装入一个新的程序把它覆盖；把它覆盖；优点：优点：简单简单、开销小，易于管理；、开销小，易于管理；适合于单用户、单任务的适合于单用户、单任务的OS。77BIOS（本图摘自（本图摘自Andrew S. Tanenbaum： “Modern Operating Systems” ）三种实现方式三种实现方式单道程序存储管理的缺点？单道程序存储管理的缺点？88n每次只能运行一个程序每次只能运行一个程序n内存资源的使用效率不高内存资源的使用效率

4、不高程序程序较小较小时，会浪费大量的内存空间时，会浪费大量的内存空间nOS的保护的保护应用程序的应用程序的bug会破坏会破坏OSn地址空间有限地址空间有限即为物理内存的大小即为物理内存的大小99如何实现多道存储管理，即在内如何实现多道存储管理，即在内存中同时有多个进程运行，有哪存中同时有多个进程运行，有哪些问题需要考虑？些问题需要考虑？1010 内存空间的管理内存空间的管理 整个内存区域如何划分？整个内存区域如何划分？ 用什么数据结构来管理内存？用什么数据结构来管理内存？ 如何在有限的内存空间中容纳尽可能多如何在有限的内存空间中容纳尽可能多的进程？的进程？ 内存的分配内存的分配 新进程到达时，

5、如何给它分配内存？新进程到达时，如何给它分配内存？ 内存的回收内存的回收 进程运行结束时，如何回收其内存？进程运行结束时，如何回收其内存？1111 地址重定位地址重定位 程序员不知道当他的程序被执行时，将程序员不知道当他的程序被执行时，将会被放在内存的什么位置；会被放在内存的什么位置； 当一个程序正在执行时，可能被交换到当一个程序正在执行时，可能被交换到磁盘上，后来再返回内存时，可能存放磁盘上，后来再返回内存时，可能存放在不同的位置；在不同的位置； 对内存的访问必须转换为实际的物理内对内存的访问必须转换为实际的物理内存地址。存地址。1212 内存保护内存保护 一个进程不能未经许可去访问其他进程

6、一个进程不能未经许可去访问其他进程或或OS的内存地址；的内存地址； 内存共享内存共享 允许多个进程访问相同的一段内存空间；允许多个进程访问相同的一段内存空间； 最好允许每个进程访问一个程序的同一最好允许每个进程访问一个程序的同一份拷贝，而不是每个进程都有自己独立份拷贝，而不是每个进程都有自己独立的一份拷贝。的一份拷贝。1313 逻辑组织逻辑组织 程序的编写是以模块为单位；程序的编写是以模块为单位； 每个模块的保护级别可能是不同的（只每个模块的保护级别可能是不同的（只读、只可执行、可读写等）；读、只可执行、可读写等）； 模块的共享。模块的共享。 物理组织物理组织 分配给一个程序（包括其数据）的内

7、存分配给一个程序（包括其数据）的内存空间可能不够用；空间可能不够用； 磁盘存储器更便宜、容量更大、且永久磁盘存储器更便宜、容量更大、且永久保存。保存。1414Now，如何实现多道存储管理？，如何实现多道存储管理？n内存的分配；内存的分配；n内存的回收；内存的回收；n内存的管理（数据结构）。内存的管理（数据结构）。15154.2 分区存储管理分区存储管理内存分为两大区域：系统区，用户区。内存分为两大区域：系统区，用户区。又把用户区划分为若干分区又把用户区划分为若干分区(partition)，分区大小可以相等，也可以不等。一个分区大小可以相等，也可以不等。一个进程占用一个分区。进程占用一个分区。特

8、点：适合于多道程序系统和分时系统，特点：适合于多道程序系统和分时系统，支持多个程序并发执行；支持多个程序并发执行；16164.2.1 固定分区存储管理固定分区存储管理各个用户分区的个数、位置和大小一旦确定以后，各个用户分区的个数、位置和大小一旦确定以后，就就固定不变固定不变。为了满足不同程序的存储需要，各分。为了满足不同程序的存储需要，各分区的大小可相等，也可不等。区的大小可相等，也可不等。 分区大小相等：只适合于多个相同程序的并发执分区大小相等：只适合于多个相同程序的并发执行（处理多个类型相同的对象）；行（处理多个类型相同的对象）； 分区大小不等：多个小分区、适量的中等分区、分区大小不等：多

9、个小分区、适量的中等分区、少量的大分区；少量的大分区； 当进程到来时，根据它的大小，把它放置到相应当进程到来时，根据它的大小，把它放置到相应的输入队列当中，等待合适的空闲分区。两种实的输入队列当中，等待合适的空闲分区。两种实现方式：现方式：多个输入队列多个输入队列和和单个输入队列单个输入队列。1717多个输入队列多个输入队列分区分区4分区分区3分区分区2分区分区1操作系统操作系统700K400K100K0200K800K对于每一个用户分区，对于每一个用户分区，都有一个都有一个输入队列输入队列。当。当一个新的进程到来时，一个新的进程到来时，把它加入到某个输入队把它加入到某个输入队列当中，该输入队

10、列所列当中，该输入队列所对应的分区，是能够装对应的分区，是能够装下该进程的最小分区。下该进程的最小分区。缺点：可能出现小分区缺点：可能出现小分区的输入队列是满的，而的输入队列是满的，而大分区的输入队列却空大分区的输入队列却空着（着（如分区如分区1和分区和分区3的的的情形的情形），从而造成资），从而造成资源的浪费。源的浪费。180K1818单个输入队列单个输入队列分区分区4分区分区3分区分区2分区分区1操作系统操作系统700K400K100K0200K800K对于所有的用户分对于所有的用户分区，只有一个统一区，只有一个统一的输入队列。当一的输入队列。当一个新进程到来时，个新进程到来时，把它加入到

11、该输入把它加入到该输入队列当中，然后当队列当中，然后当某个分区空闲时：某个分区空闲时： 离队首最近的、离队首最近的、能装入该分区的能装入该分区的进程被选中；进程被选中； 搜索整个队列，搜索整个队列，选择能装入该分选择能装入该分区的最大进程。区的最大进程。1919如何实现固定分区存储管理？如何实现固定分区存储管理？数据结构、分配、回收。数据结构、分配、回收。2020固定分区的实现固定分区的实现数据结构：设置数据结构：设置内存分配表内存分配表内存分配：先放入输入队列，然后采用内存分配：先放入输入队列，然后采用 最先匹配法、最佳匹配法最先匹配法、最佳匹配法 等算法。等算法。内存回收：简单内存回收：简

12、单分区号分区号 起始地址起始地址长度长度状态状态进程名进程名2121固定分区的缺点：固定分区的缺点： 内存利用率不高，内碎片造成很大浪费。内存利用率不高，内碎片造成很大浪费。所谓所谓内碎片内碎片，即进程所占用分区之内的未，即进程所占用分区之内的未被利用的空间（再小的进程都要占用一整被利用的空间（再小的进程都要占用一整个分区）。个分区）。 分区的总数固定，限制了并发执行的程序分区的总数固定，限制了并发执行的程序个数，不够灵活。个数，不够灵活。 进程的保护（应用程序可能破坏进程的保护（应用程序可能破坏OS和其他和其他应用程序）应用程序）固定分区的优点：易于实现，固定分区的优点：易于实现，开销小开销

13、小。2222 地址空间的大小有限：不能超过物理内存地址空间的大小有限：不能超过物理内存的大小。的大小。 如何提高内存的利用效率？如何提高内存的利用效率？如何确定分区的大小？如何确定分区的大小？分区太小怎么办？分区太小怎么办？分区太大怎么办（内碎片）？分区太大怎么办（内碎片）？为此，人们又提出了为此，人们又提出了可变分区（动态分区）可变分区（动态分区）的存储管理技术。的存储管理技术。23234.2.2 可变分区存储管理可变分区存储管理分区不是预先划分好的固定区域，而是动态创建的。分区不是预先划分好的固定区域，而是动态创建的。在装入一个程序时，根据它的需求和内存空间的使用在装入一个程序时，根据它的

14、需求和内存空间的使用情况来决定是否分配。具体来说，系统生成后，操作情况来决定是否分配。具体来说，系统生成后，操作系统会占用内存的一部分（一般在内存地址低端），系统会占用内存的一部分（一般在内存地址低端），其余空间为一个完整的大空闲区。当一个程序要求装其余空间为一个完整的大空闲区。当一个程序要求装入内存运行时，系统从这个空闲区中划分一块分配给入内存运行时，系统从这个空闲区中划分一块分配给它，当程序完成后释放所占用的存储区。随着一系列它，当程序完成后释放所占用的存储区。随着一系列的内存分配和回收，原来的一整块大空闲区就形成了的内存分配和回收，原来的一整块大空闲区就形成了若干占用区和空闲区相间的布局

15、。若干占用区和空闲区相间的布局。2424操作系统操作系统 128K01024K128K空闲区空闲区 896K操作系统操作系统 128K01024K128K空闲区空闲区 576K进程进程1 320K448K2525操作系统操作系统 128K01024K128K空闲区空闲区 352K进程进程1 320K448K进程进程2 224K672K操作系统操作系统 128K01024K128K空闲区空闲区 64K进程进程1 320K448K进程进程2 224K672K进程进程3 288K960K空闲区空闲区 224K250K？2626操作系统操作系统 128K01024K128K空闲区空闲区 64K进程进程

16、1 320K448K进程进程4 128K672K进程进程3 288K960K576K空闲区空闲区 96K空闲区空闲区 320K 可变分区的特点：可变分区的特点： 在可变分区当中，分区的个在可变分区当中，分区的个数、位置和大小都是随进程数、位置和大小都是随进程的进出而的进出而动态变化动态变化的，非常的，非常灵活，避免了在固定分区中灵活，避免了在固定分区中因分区大小不当所造成的因分区大小不当所造成的内内碎片碎片，提高了内存利用率。，提高了内存利用率。 有有外碎片外碎片，即各个占用分区，即各个占用分区之间难以利用的空闲分区之间难以利用的空闲分区（通常是小空闲分区）；（通常是小空闲分区）； 使得内存的

17、分配、回收和管使得内存的分配、回收和管理更为复杂。理更为复杂。2727如何实现可变分区的存储管理技术？如何实现可变分区的存储管理技术？1. 内存管理的数据结构；内存管理的数据结构；2. 内存的分配算法内存的分配算法3. 内存的回收方法内存的回收方法4. 碎片问题碎片问题4.2.3 可变分区的实现可变分区的实现28281. 分区链表分区链表系统维护一个有序的分区链表，来跟踪记录每一个内系统维护一个有序的分区链表，来跟踪记录每一个内存分区的情况，包括该分区的状态（已分配或空闲）存分区的情况，包括该分区的状态（已分配或空闲）起始地址、长度等信息。起始地址、长度等信息。ABCDE0581418 202

18、62932占占 0 5空空 5 3占占 8 6占占144空空182占占206占占263空空293X空闲空闲起始起始 长度长度占用占用29292. 分区分配算法分区分配算法分区分配算法：当一个新的进程来到时，需分区分配算法：当一个新的进程来到时，需为它寻找某个空闲分区，其大小必须大于或为它寻找某个空闲分区，其大小必须大于或等于该进程的要求。若是大于要求，则将该等于该进程的要求。若是大于要求，则将该分区分割成两个分区，其中一个分区为要求分区分割成两个分区，其中一个分区为要求的大小并标记为的大小并标记为“占用占用”，而另一个分区为余，而另一个分区为余下部分并标记为下部分并标记为“空闲空闲”。分区的先

19、后次序通。分区的先后次序通常是从内存低端到高端。常是从内存低端到高端。分区分配算法主要有：最先匹配法、下次匹分区分配算法主要有：最先匹配法、下次匹配法、最佳匹配法、最坏匹配法。配法、最佳匹配法、最坏匹配法。3030最先匹配法最先匹配法 (first-fit) ：假设新进程对内存大小的：假设新进程对内存大小的要求为要求为M，那么从分区链表的首结点开始，将每，那么从分区链表的首结点开始，将每一个一个“空闲空闲”结点的长度与结点的长度与M进行比较，看是否进行比较，看是否大于或等于它，直到找到第一个符合要求的结点大于或等于它，直到找到第一个符合要求的结点。然后把它所对应的空闲分区分割为二个小分区。然后

20、把它所对应的空闲分区分割为二个小分区，一个用于装入该进程，另一个仍然空闲。与之，一个用于装入该进程，另一个仍然空闲。与之相对应，相对应，把该结点也一分为二把该结点也一分为二，并修改相应内容，并修改相应内容。F查找的结点很少，因而查找的结点很少，因而速度快速度快；F算法的实质是尽可能利用低地址部分的空闲算法的实质是尽可能利用低地址部分的空闲区，而尽量地保证高地址部分的大空闲区，区，而尽量地保证高地址部分的大空闲区，使其不被分割成小的区，这样当以后有大的使其不被分割成小的区，这样当以后有大的进程到来时，有足够大的空闲区来满足它。进程到来时，有足够大的空闲区来满足它。3131下次匹配法下次匹配法 (

21、next-fit) ：与最先匹配法的思路是相：与最先匹配法的思路是相似的，只不过每一次当它找到一个合适的结点（似的，只不过每一次当它找到一个合适的结点（分区）时，就把当前的位置记录下来。然后等下分区）时，就把当前的位置记录下来。然后等下一次新进程到来的时候，就从这个位置开始继续一次新进程到来的时候，就从这个位置开始继续往下找（到链表结尾时再回到开头），直到找到往下找（到链表结尾时再回到开头），直到找到符合要求的第一个分区。而不是象最先匹配法那符合要求的第一个分区。而不是象最先匹配法那样，每次都是从链表的首结点开始找。样，每次都是从链表的首结点开始找。F查找的结点很少，因而速度快；查找的结点很少

22、，因而速度快；F该算法使空闲分区分布得更均匀，但较大的该算法使空闲分区分布得更均匀，但较大的空闲分区不易保留。从性能上略逊于最先匹空闲分区不易保留。从性能上略逊于最先匹配法。配法。3232最佳匹配法最佳匹配法 (best-fit) ：将申请内存的进程装入到：将申请内存的进程装入到与其大小最接近的空闲分区当中。算法的性能最与其大小最接近的空闲分区当中。算法的性能最差，最大缺点是分割后剩余的空闲分区将会很小差，最大缺点是分割后剩余的空闲分区将会很小，直至无法使用，从而造成浪费（，直至无法使用，从而造成浪费（与固定分区是与固定分区是不同的不同的）。）。最坏匹配法最坏匹配法(worst-fit)：每次

23、分配时，总是将最大：每次分配时，总是将最大的空闲区切去一部分分配给请求者，其依据是当的空闲区切去一部分分配给请求者，其依据是当一个很大的空闲区被切割了一部分后可能仍是一一个很大的空闲区被切割了一部分后可能仍是一个较大的空闲区，从而避免了空闲区越分越小的个较大的空闲区，从而避免了空闲区越分越小的问题。这种算法基本不留下小的空闲分区，但较问题。这种算法基本不留下小的空闲分区，但较大的空闲分区也不被保留。大的空闲分区也不被保留。3333Lastallocatedblock (14K)BeforeAfter8K8K12K12K22K18K6K6K8K8K14K14K6K2K36K20KNext Fit

24、Free blockAllocated blockBest FitFirst Fit16K16K16KWorst Fit地址低端地址低端地址高端地址高端16K新进程新进程34343. 分区回收算法分区回收算法分区回收算法分区回收算法：当一个进程运行结束，释放它所占：当一个进程运行结束，释放它所占用的分区后，需要将相邻的几个空闲分区合并为一用的分区后，需要将相邻的几个空闲分区合并为一个大的空闲分区。具体来说，可分以下四种情况：个大的空闲分区。具体来说，可分以下四种情况：在分区回收后，可以很方便地更新分区链表。在分区回收后，可以很方便地更新分区链表。3535占占 0 5占占 5 3占占 8 6(a

25、)进程进程A进程进程X进程进程B空空空闲区空闲区50占占35占占68空空(b)进程进程A进程进程X空闲区空闲区50占占95空空进程进程A空闲区空闲区50空空35占占68空空(d)空闲区空闲区进程进程X空闲区空闲区140空空空闲区空闲区(c) 略略36364. 碎片问题碎片问题经过一段时间的分配与回收后，内存中存在着很多经过一段时间的分配与回收后，内存中存在着很多不连续的很小的空闲分区（外碎片）。当一个新进不连续的很小的空闲分区（外碎片）。当一个新进程到来时，这些小的空闲区都不足以满足分配要求，程到来时，这些小的空闲区都不足以满足分配要求，但其总和满足分配要求。这就是（外）碎片问题。但其总和满足

26、分配要求。这就是（外）碎片问题。内存紧缩内存紧缩（Compaction）：把所有的进程尽可能）：把所有的进程尽可能地往地址低端移动，相应的，那些空闲的小分区就地往地址低端移动，相应的，那些空闲的小分区就会往地址的高端移动，从而形成一个大的空闲区。会往地址的高端移动，从而形成一个大的空闲区。 所有进程的移动需要大量的所有进程的移动需要大量的CPU时间；时间； 如何解决程序移动后，地址的重定位问题？如何解决程序移动后，地址的重定位问题？37374.2.5 内存中的程序执行内存中的程序执行进程执行时的进程执行时的内存分区布局内存分区布局栈栈动态堆空间动态堆空间(malloc)数据数据代码代码低地址低

27、地址高地址高地址PCSP3838变量的存储与作用域/* 全局变量，固定地址，其他源文件可见全局变量，固定地址，其他源文件可见 */int global_static;/* 静态全局变量，固定地址，但只在本文件中可见静态全局变量，固定地址，但只在本文件中可见 */static int file_static;/* 函数参数：位于栈帧当中，动态创建，动态释放函数参数：位于栈帧当中，动态创建，动态释放 */int foo(int auto_param)/ 代码代码 /*静态局部变量，固定地址，只在本函数中可见静态局部变量，固定地址，只在本函数中可见 */ static int func_static

28、; /* 普通局部变量，位于栈帧当中，只在本函数可见普通局部变量，位于栈帧当中，只在本函数可见 */ int auto_i, auto_a10; /* 动态申请的内存空间，位于堆当中动态申请的内存空间，位于堆当中 */ double *auto_d = malloc(sizeof(double)*5); return auto_i;39394.2.5 重定位和存储保护重定位和存储保护1. 地址映射（重定位）地址映射（重定位）1）物理地址物理地址也叫内存地址、绝对地址，实地址；也叫内存地址、绝对地址，实地址；把内存分成很多个大小相等的存储单元，每个把内存分成很多个大小相等的存储单元，每个单元给一

29、个编号，这个编号称为物理地址；单元给一个编号，这个编号称为物理地址；物理地址可以直接寻址；物理地址可以直接寻址；物理地址的集合称为物理地址空间（内存地址物理地址的集合称为物理地址空间（内存地址空间），它是一个一维的线性空间。空间），它是一个一维的线性空间。40402 2）逻辑地址逻辑地址也叫相对地址，虚地址；也叫相对地址，虚地址；用户程序经过汇编或编译后形成目标代码，目用户程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式，其首地址为标代码通常采用相对地址的形式，其首地址为0，其余指令中的地址都是相对首地址来编址；，其余指令中的地址都是相对首地址来编址；不能用逻辑地址在内存中读取

30、信息。不能用逻辑地址在内存中读取信息。3 3）地址映射）地址映射为了保证为了保证CPU执行指令时可正确访问存储单元，执行指令时可正确访问存储单元，需要将用户程序中的逻辑地址转换为运行时由需要将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址，这一过程称为地址机器直接寻址的物理地址，这一过程称为地址映射。映射。4141int x, y;x = 5;y = x + 3;源程序源程序编译编译链接链接装入装入分区分区0100200300.str 5, 200ldr R1, 200add R2,R1,3str R2, 204逻辑地址空间逻辑地址空间204xy1000.110012001300物理

31、地址空间物理地址空间str 5, 200ldr R1, 200add R2,R1,3str R2, 2041204xy有无问题？有无问题？4242为了保证为了保证CPU执行指令时可正确访问存储单元，执行指令时可正确访问存储单元，在装入程序时必须进行地址映射，将程序中的在装入程序时必须进行地址映射，将程序中的逻辑地址转换为物理地址。这主要有两种方式：逻辑地址转换为物理地址。这主要有两种方式：& 静态地址映射（静态重定位）：当用户程序静态地址映射（静态重定位）：当用户程序被装入内存时，直接对被装入内存时，直接对指令代码指令代码进行修改，进行修改，一次性实现逻辑地址到物理地址的转换，以一次性实现逻辑

32、地址到物理地址的转换，以后不再转换。后不再转换。 在可执行文件中，需在可执行文件中，需列出列出各个需要重定位各个需要重定位的地址单元的位置。在装入时，由一个装的地址单元的位置。在装入时，由一个装入程序（加载程序）来完成；入程序（加载程序）来完成； 实现简单，不需要硬件的支持；实现简单，不需要硬件的支持； 程序装入内存后程序装入内存后不能移动不能移动。4343装入分区装入分区0100200300.str 5, 200ldr R1, 200add R2,R1,3str R2, 204逻辑地址空间逻辑地址空间204xy1000.110012001300物理地址空间物理地址空间str 5, 1200l

33、dr R1,1200add R2,R1,3str R2,12041204xy4444& 动态地址映射（动态重定位）：当用户程序被装动态地址映射（动态重定位）：当用户程序被装入内存时，不对指令代码做任何修改。而是在程入内存时，不对指令代码做任何修改。而是在程序序运行运行过程中，当需要访问内存单元时再来进行过程中，当需要访问内存单元时再来进行地址转换（即在逐条执行指令时完成转换）。地址转换（即在逐条执行指令时完成转换）。 为提高效率，此工作一般由硬件地址映射机为提高效率，此工作一般由硬件地址映射机制来完成，通常的做法是设置一个基地址寄制来完成，通常的做法是设置一个基地址寄存器（重定位寄存器），并把

34、进程所在分区存器（重定位寄存器），并把进程所在分区的起始地址装入到该寄存器当中；的起始地址装入到该寄存器当中； 在程序运行过程中，当需要访问内存单元时在程序运行过程中，当需要访问内存单元时,硬件就自动地将其中的相对地址加上基地址硬件就自动地将其中的相对地址加上基地址寄存器的内容，形成实际的物理地址，然后寄存器的内容，形成实际的物理地址，然后按该地址去执行。按该地址去执行。4545装入装入分区分区0100200300.str 5, 200ldr R1, 200add R2,R1,3str R2, 204逻辑地址空间逻辑地址空间204xy1000.110012001300物理地址空间物理地址空间s

35、tr 5, 200ldr R1, 200add R2,R1,3str R2, 2041204xy+基地址寄存器基地址寄存器相对地址相对地址10002001.基地址寄存器基地址寄存器 在哪？在哪？2.何时填入何时填入1000？4646为了防止一个用户程序去访问其他用户程序为了防止一个用户程序去访问其他用户程序的内存分区，保护操作系统免受用户程序的的内存分区，保护操作系统免受用户程序的破坏，须进行存储保护。破坏，须进行存储保护。如何实现？如何实现？能否与动态地址映射集成在一起？能否与动态地址映射集成在一起？2. 存储保护存储保护4747最简单的做法：在基地址寄存器的基础上，再增加最简单的做法：在基

36、地址寄存器的基础上，再增加一个限长寄存器，记录分区的长度。这两者在一起，一个限长寄存器，记录分区的长度。这两者在一起，就定义了进程所在的分区（就定义了进程所在的分区（寄存器的值存放在哪？寄存器的值存放在哪？）进程进程B进程进程A操作系统操作系统100K100K基地址寄存器基地址寄存器限长寄存器限长寄存器逻辑地址必须逻辑地址必须小于限长寄存小于限长寄存器的值。硬件器的值。硬件保护这两个寄保护这两个寄存器，用户程存器，用户程序不能修改。序不能修改。0100K200K300K4848CPUMMU内存内存磁盘磁盘控制器控制器总线总线CPU组件组件存储管存储管理单元理单元CPU发送逻辑地址给发送逻辑地址

37、给MMUMMU发送物理地址给内存发送物理地址给内存动态地址映射动态地址映射49494.3 页式和段式存储管理页式和段式存储管理页式存储管理页式存储管理段式存储管理段式存储管理页式管理与段式管理的比较页式管理与段式管理的比较段页式存储管理段页式存储管理50504.3.1 页式存储管理页式存储管理分区存储管理方案的一个特性是连续性，这将会分区存储管理方案的一个特性是连续性，这将会导致导致碎片问题（内碎片和外碎片）碎片问题（内碎片和外碎片）。为有效地解决。为有效地解决这些问题，人们又提出了页式存储管理方案，其基这些问题，人们又提出了页式存储管理方案，其基本出发点是打破存储分配的连续性，使得一个程序本

38、出发点是打破存储分配的连续性，使得一个程序的逻辑地址空间可以分布在若干个离散的内存块上，的逻辑地址空间可以分布在若干个离散的内存块上，从而达到充分利用内存，提高内存利用率的目的。从而达到充分利用内存，提高内存利用率的目的。51511. 基本原理基本原理把物理内存划分为许多个固定大小的内存块，称把物理内存划分为许多个固定大小的内存块，称为为物理页面物理页面，或，或页框页框（page frame）；）；把逻辑地址空间划分为大小相同的块，称为把逻辑地址空间划分为大小相同的块，称为逻辑逻辑页面页面，或简称，或简称页面页面（page）；）；页面大小为页面大小为2n，一般在，一般在512字节到字节到8K字

39、节之间；字节之间；当一个用户程序装入内存时，以页面为单位进行当一个用户程序装入内存时，以页面为单位进行分配。若要运行一个大小为分配。若要运行一个大小为n个页面的程序，需个页面的程序，需要有要有n个空闲的物理页面把它装入，这些页面不个空闲的物理页面把它装入，这些页面不必是连续的。必是连续的。生活中的例子生活中的例子5252进程进程3 第第0页页进程进程2 第第2页页进程进程1 第第1页页进程进程1 第第0页页进程进程2 第第1页页进程进程2 第第0页页操作系统操作系统操作系统操作系统0K1K2K3K4K5K6K7K8K9K10K0K1K2K进程进程1 地址空间地址空间进程进程2 地址空间地址空间

40、0K1K2K3K0K1K进程进程3 地址空间地址空间内存内存5353用于存储管理的用于存储管理的数据结构数据结构是什么？是什么？当一个进程到来时，如何给它当一个进程到来时，如何给它分配分配内存？内存？当一个进程运行结束，当一个进程运行结束，释放释放它所占用的内它所占用的内存空间后，如何回收内存？存空间后，如何回收内存？当一个进程被加载到内存以后，它如何正当一个进程被加载到内存以后，它如何正确运行（确运行（地址重定位地址重定位）？）？页式存储管理要解决如下问题：页式存储管理要解决如下问题：54542. 数据结构数据结构页表页表：系统为每一个进程都建立了一个页：系统为每一个进程都建立了一个页表，页

41、表给出了逻辑页面号和具体内存块表，页表给出了逻辑页面号和具体内存块号（物理页面号）之间的对应关系。号（物理页面号）之间的对应关系。逻辑页号逻辑页号内存块号内存块号页表页表01n-1如何实现页表？如何实现页表？5555（本图摘自（本图摘自Silberschatz, Galvin and Gagne： “Operating System Concepts”） 逻辑逻辑地址空间地址空间页表页表物理内存物理内存物理页面号物理页面号5656物理页面表物理页面表：在系统中设立一张物理页面：在系统中设立一张物理页面表，用来描述内存空间当中，各个物理页表，用来描述内存空间当中，各个物理页面的分配使用状况。具体

42、实现：位示图，面的分配使用状况。具体实现：位示图，空闲页面链表。空闲页面链表。0310/10/10/10/10/1017空闲页数空闲页数位示图位示图内存中共有内存中共有256个物理个物理页面，可以页面，可以用字长为用字长为32位的位的8个字个字来构成位示来构成位示图。图。57573. 内存的分配与回收内存的分配与回收内存的分配与回收算法与物理页面表的具内存的分配与回收算法与物理页面表的具体实现方法有关。这里以位示图为例。体实现方法有关。这里以位示图为例。内存的分配：内存的分配： 计算一个进程所需要的计算一个进程所需要的页面数页面数N，并查，并查看位示图，看是否还有看位示图，看是否还有N个空闲页

43、面个空闲页面； 若有，则申请一个页表，其长度为若有，则申请一个页表，其长度为N，并并把页表的起始地址填入把页表的起始地址填入PCB； 分配分配N个空闲的物理页面，将其编号填个空闲的物理页面，将其编号填入页表；入页表； 修改位示图（修改位示图（01，空闲页面数，空闲页面数N）5858内存的回收：当一个进程运行结束，释放内存的回收：当一个进程运行结束，释放它所占用的内存空间后，需要对这些物理它所占用的内存空间后，需要对这些物理页面进行回收。页面进行回收。 对于每一个物理页面，对于每一个物理页面，根据它的编号计根据它的编号计算出它在位示图当中的相应位置算出它在位示图当中的相应位置，并将，并将相应位的

44、值从相应位的值从1改成改成0； 修改位示图中的空闲页面数：加上修改位示图中的空闲页面数：加上N。59594. 地址映射地址映射为什么要进行地址映射？为什么要进行地址映射？一个进程的各个连续的逻辑页面，被分散地一个进程的各个连续的逻辑页面，被分散地装入到内存的各个物理页面当中，在这种情装入到内存的各个物理页面当中，在这种情形下，怎样才能保证程序能够正确地运行？形下，怎样才能保证程序能够正确地运行？能否采用静态地址映射方法？能否采用静态地址映射方法？能否采用动态地址映射方法？能否采用动态地址映射方法？如何实现？如何实现？60601. 对于给定的对于给定的逻辑地址逻辑地址，找到逻辑页，找到逻辑页面号

45、和页内偏移地址；面号和页内偏移地址；2. 查找页表，找到相应的物理页面号查找页表，找到相应的物理页面号；3. 计算最终的物理地址。计算最终的物理地址。6161逻辑地址的划分逻辑地址的划分把逻辑地址划分为两部分：逻辑页面号和把逻辑地址划分为两部分：逻辑页面号和页内偏移地址。这种划分是由系统自动完页内偏移地址。这种划分是由系统自动完成的，对用户是透明的。由于页面的大小成的，对用户是透明的。由于页面的大小一般为一般为2 2的整数次幂，因此，地址的高位部的整数次幂，因此，地址的高位部分即为页号，低位部分即为页内偏移地址。分即为页号，低位部分即为页内偏移地址。例如，页面大小为例如，页面大小为4KB4KB

46、。页号页号 页内地址页内地址6262逻辑地址为十六进制的形式逻辑地址为十六进制的形式6363逻辑地址为逻辑地址为十进制十进制的形式的形式计算方法：计算方法：页号页号 虚地址虚地址 / 页大小页大小位移量位移量 虚地址虚地址 % 页大小页大小例如：假设页面大小为例如：假设页面大小为2KB，计算逻辑地址，计算逻辑地址7145和和3412的逻辑页面号和页内偏移地址。的逻辑页面号和页内偏移地址。页号：页号：3412 / 2048 1页内偏移：页内偏移： 3412 % 2048 1364页号：页号：7145 / 2048 3页内偏移：页内偏移： 7145 % 2048 1001Why?6464X 页表保

47、存在内存当中（页表保存在内存当中（用户用户/内核空间内核空间?）;X 设置一个设置一个页表基地址寄存器页表基地址寄存器（Page-table base register，PTBR），用来指向页表的），用来指向页表的起始地址；起始地址；X 设置一个设置一个页表长度寄存器页表长度寄存器（Page-table length register，PTLR），用来指示页表的），用来指示页表的大小。大小。页表的具体实页表的具体实现现1. 硬件寄存器位于什么地方？硬件寄存器位于什么地方？2. 其内容何时更新？谁更新？如何更新？其内容何时更新？谁更新？如何更新？6565ProgramPagingMain Mem

48、oryVirtual AddressRegisterPage TablePageFrameOffsetP#Frame #Page Table PtrPage #OffsetFrame #Offset+页式地址映射页式地址映射叠加叠加1.需访问几次内存？需访问几次内存？2.页表页表？页表页表？6666页表长度页表地址控制寄存器页号页面号有效地址02132821C4物理地址81C4页式地址映射举例页式地址映射举例页号页号页内偏移量页内偏移量6767X 在现有的方案中，每一次访问内存（数据在现有的方案中，每一次访问内存（数据/指令）时，都要做指令）时，都要做两次访问两次访问内存的工作。内存的工作。这

49、样，降低了存取速度，将会影响整个系这样，降低了存取速度，将会影响整个系统的使用效率。统的使用效率。X 为缩短页表的查找时间，可以采用一种特为缩短页表的查找时间，可以采用一种特殊的快速查找硬件：殊的快速查找硬件：TLBTLB (Translation Lookaside Buffer) 或称或称associative memory,用来存放那些最常用的页表项。用来存放那些最常用的页表项。如何加快页表的查询速度？如何加快页表的查询速度？6868带有带有TLB的页式地址映射的页式地址映射（本图摘自（本图摘自Silberschatz, Galvin and Gagne： “Operating Syst

50、em Concepts”）先先后后为什么管用？为什么管用？69695. 优缺点优缺点优点：优点： 没有外碎片，内碎片的大小不超过页面没有外碎片，内碎片的大小不超过页面的大小；的大小； 一个程序不必连续存放；一个程序不必连续存放； 便于管理；便于管理；缺点：缺点： 程序必须程序必须全部全部装入内存；装入内存； 系统必须为系统必须为每个进程每个进程维护一张页表。维护一张页表。70704.3.2 段式存储管理段式存储管理 Why 段式存储管理？段式存储管理？页式存储管理（和分区存储管理）只有一个页式存储管理（和分区存储管理）只有一个逻辑地址空间，即一维的线性逻辑地址空间，即一维的线性连续空间连续空间

51、，从，从 0 到某个最大的逻辑地址。但是从程序员或到某个最大的逻辑地址。但是从程序员或系统管理的角度来说，一个程序是由一组模系统管理的角度来说，一个程序是由一组模块（片段）所组成的，每个片段是一个逻辑块（片段）所组成的，每个片段是一个逻辑单元，如：主程序、全局变量、栈、库函数单元，如：主程序、全局变量、栈、库函数等。等。7171存储保护存储保护： 代码段：一条条指令组成，代码段：一条条指令组成，只读，可执只读，可执行行，无需写回磁盘无需写回磁盘； 数据段：全局变量，可修改，可读写，数据段：全局变量，可修改，可读写，需写回磁盘；需写回磁盘； 栈：行参、局部变量、栈：行参、局部变量、CPU寄存器、

52、返寄存器、返回地址，可读写回地址，可读写，是否可执行？是否可执行？存储共享：存储共享：在多个进程之间，共享代码和数据。在多个进程之间，共享代码和数据。72721. 基本原理基本原理对于程序当中的每一个逻辑单元，设立一个完全对于程序当中的每一个逻辑单元，设立一个完全独立的地址空间，称为独立的地址空间，称为“段段”。在每个段的内部。在每个段的内部，是一维的线性连续地址，从，是一维的线性连续地址，从0一直到某个最大的一直到某个最大的地址。每个段的大小一般是不相等的，它所包含地址。每个段的大小一般是不相等的，它所包含的的内容内容也是不一样的；也是不一样的；对于物理内存来说，采用可变分区（动态分区）对于

53、物理内存来说，采用可变分区（动态分区）的管理方法；的管理方法；当一个程序需要装入内存时，以段为单位进行分当一个程序需要装入内存时，以段为单位进行分配，配，把每一个段装入到一个内存分区当中把每一个段装入到一个内存分区当中，这些，这些内存分区不必是连续的。内存分区不必是连续的。73731423物理内存空间物理内存空间用户空间用户空间1324子函数子函数主函数主函数栈栈符号表符号表0n74742. 具体实现具体实现在段式存储管理中，用户空间的地址为二元地址在段式存储管理中，用户空间的地址为二元地址：(段号，段内偏移段号，段内偏移)。实现方式：。实现方式：(1)地址高端为地址高端为段号、低端为偏移；段

54、号、低端为偏移；(2)指令中显式地给出段号和指令中显式地给出段号和段内偏移。段内偏移。段表：系统为每一个进程都建立了一个段表，它段表：系统为每一个进程都建立了一个段表，它给出了进程当中的每一个段与它所对应的内存分给出了进程当中的每一个段与它所对应的内存分区之间的映射关系。区之间的映射关系。7575所对应内存分区的起始地址所对应内存分区的起始地址段长度段长度1400100063004004300400段号段号012段表段表比较页比较页表表7676段表的具体实现：段表的具体实现：段表保存在内存当中；段表保存在内存当中；设置一个设置一个段表基地址寄存器段表基地址寄存器（Segment-table b

55、ase register，STBR），用来指向内），用来指向内存当中段表的起始地址；存当中段表的起始地址；设置一个设置一个段表长度寄存器段表长度寄存器（Segment-table length register，STLR），用来指示段表的），用来指示段表的大小，即程序当中的段的个数；大小，即程序当中的段的个数；7777段式地址映射段式地址映射Base + dProgramSegmentationMain MemoryVirtual AddressRegisterSegment TableSegmentdS#Length BaseSeg Table PtrSeg #Offset = dSegme

56、nt Table+Physical Address与页式地址映射的区别？与页式地址映射的区别？7878段式地址映射举例段式地址映射举例段表起始地址段表地址寄存器虚拟地址11C4段号段内地址段表段号始址015001340035C4内存7979X 逻辑地址逻辑地址32位：位：16位段号位段号16位段内偏移位段内偏移;X 整数为整数为32位；位；X 地址以地址以16进制描述。进制描述。段式存储管理举例段式存储管理举例16位位16位位段号段号段内偏移段内偏移8080段段基地址基地址长度长度保护保护01000018C0只读只读1119003FF只读只读211D001FF读写读写300禁止访问禁止访问41

57、1F001000读写读写500禁止访问禁止访问600禁止访问禁止访问713000FFF读写读写mainSin240push X 10108360mov 4(sp), r2244call Sin364push r2248366488ret段表段表代码代码段段81818282X X在哪？（在哪？（Sin函数的参数）函数的参数）X 栈指针的当前地址是栈指针的当前地址是70FF0，物理地址是多少？，物理地址是多少？X 第一条指令在哪？第一条指令在哪？X Push X指令：将指令：将SP减减4，然后存储，然后存储X的值，那么的值，那么X被存储在什么地方？被存储在什么地方？X Call Sin指令：指令：

58、(1)当前当前PC值入栈；值入栈；(2)在在PC内装入内装入目标目标PC值。哪个值被压入栈了？新的栈指针的值值。哪个值被压入栈了？新的栈指针的值是多少？新的是多少？新的PC值是多少？值是多少？X “mov 4+(sp), r2”的功能是什么？的功能是什么？83833. 优缺点优缺点优点：优点： 程序通过分段来划分多个模块，每个模程序通过分段来划分多个模块，每个模块可以分别编写和编译，可以针对不同块可以分别编写和编译，可以针对不同类型的段采取不同的保护，可以按段为类型的段采取不同的保护，可以按段为单位来进行共享；单位来进行共享； 一个程序不必连续存放，没有内碎片。一个程序不必连续存放，没有内碎片

59、。缺点：缺点：程序必须全部装入内存、外碎片等。程序必须全部装入内存、外碎片等。848485854.3.3 页式管理与段式管理的比较页式管理与段式管理的比较分页与分段的出发点不同分页与分段的出发点不同F页式：为减少碎片，提高内存的使用效率，页式：为减少碎片，提高内存的使用效率，因此把内存划分为许多个固定大小的物理页因此把内存划分为许多个固定大小的物理页面。相应的，把逻辑地址空间也划分为大小面。相应的，把逻辑地址空间也划分为大小相同的逻辑页面；相同的逻辑页面；F段式：为了实现程序当中的各个逻辑单元的段式：为了实现程序当中的各个逻辑单元的独立性，便于它们的共享、保护和修改，从独立性，便于它们的共享、

60、保护和修改，从而为每一个逻辑单元设立一个单独的而为每一个逻辑单元设立一个单独的“段段”。相应的，在物理内存的分配和回收上，采。相应的，在物理内存的分配和回收上，采用可变分区的存储管理方法。用可变分区的存储管理方法。8686程序员对所采用的存储管理技术的关注：程序员对所采用的存储管理技术的关注：F页式：对于程序员而言，页式存储管理完全页式：对于程序员而言，页式存储管理完全是透明的，不必关心。对逻辑地址空间的分是透明的，不必关心。对逻辑地址空间的分页，是由系统自动完成的。页，是由系统自动完成的。程序员甚至不知程序员甚至不知道分页的发生道分页的发生。F段式：程序员知道各个逻辑单元的存在，因段式：程序