1、1第第4 4章章 存储管理存储管理 重要内容重要内容0存储器存储器0连续存储空间管理连续存储空间管理0分页存储管理分页存储管理0分段存储管理分段存储管理0虚拟存储管理虚拟存储管理0Intel x86Intel x86分段和分页存储结构分段和分页存储结构0LinuxLinux虚拟存储管理虚拟存储管理0Windows 2003Windows 2003虚拟存储管理虚拟存储管理2存储管理的功能存储管理的功能 分配和去配分配和去配0请求和释放主存空间请求和释放主存空间 抽象和映射抽象和映射0抽象成一维数组或二维地址空间抽象成一维数组或二维地址空间0地址转换地址转换 隔离和共享隔离和共享0隔离实现存储保护
2、功能隔离实现存储保护功能0超越隔离机制，提高主存利用率超越隔离机制，提高主存利用率 存储扩充存储扩充0虚拟，允许进程虚拟地址空间大于主存空间虚拟，允许进程虚拟地址空间大于主存空间34.1 4.1 存储器存储器4.1.1 4.1.1 存储器的层次存储器的层次 4.1.2 4.1.2 地址转换与存储保护地址转换与存储保护 44.1.1 4.1.1 存储器的层次存储器的层次寄存器寄存器高速缓存高速缓存主存储器主存储器磁盘缓存磁盘缓存固定磁盘固定磁盘可移动存储介质可移动存储介质54.1.2 4.1.2 地址转换与存储保护地址转换与存储保护(1)(1)链接链接动态动态重定重定位位静态静态重定重定位位源程
3、序源程序模块模块1 1源程序源程序模块模块2 2源程序源程序模块模块n n目标目标代码代码1 1目标目标代码代码2 2目标目标代码代码n n可重定位可重定位目标代码目标代码( (装载代装载代码码)()(辅存辅存) )编译编译装入装入执行执行程序名字程序名字空间空间逻 辑 地逻 辑 地址址空间空间物理地址物理地址空间空间可执行可执行二进代二进代码码( (主存主存) )库代码库代码可执行可执行二进代二进代码码( (主存主存) ) 程序的编译、链接、装入和执行程序的编译、链接、装入和执行6地址转换与存储保护地址转换与存储保护(2)(2) 逻辑地址（虚地址）：逻辑地址（虚地址）：CPUCPU所生成的地
4、址所生成的地址 物理地址（实地址）：内存单元所看到的地址物理地址（实地址）：内存单元所看到的地址 逻辑地址空间：由程序所生成的所有逻辑地址的逻辑地址空间：由程序所生成的所有逻辑地址的集合集合 物理地址空间：由逻辑地址所对应的所有物理地物理地址空间：由逻辑地址所对应的所有物理地址的集合址的集合 地址转换或重定位：把逻辑地址转换为物理地址地址转换或重定位：把逻辑地址转换为物理地址7 静态重定位静态重定位0地址转换工作在进程执行前一次完成；地址转换工作在进程执行前一次完成；0无须硬件支持，易于实现，但不允许程序在执行过程无须硬件支持，易于实现，但不允许程序在执行过程中移动位置。中移动位置。0早期单用
5、户单任务系统早期单用户单任务系统 动态重定位动态重定位0地址转换推迟到最后的可能时刻，即进程执行时才完地址转换推迟到最后的可能时刻，即进程执行时才完成；成；0允许程序在主存中移动、便于主存共享、主存利用率允许程序在主存中移动、便于主存共享、主存利用率高。高。地址转换与存储保护地址转换与存储保护(3)(3)8例：使用重定位寄存器的动态重定位例：使用重定位寄存器的动态重定位9存储保护存储保护 问题：保护操作系统不受用户进程所影响，保护用户进程问题：保护操作系统不受用户进程所影响，保护用户进程不受其他用户进程所影响不受其他用户进程所影响 方法方法1)1)存储键保护存储键保护v系统将主存划分成大小相等
6、的若干存储块，并给每个存系统将主存划分成大小相等的若干存储块，并给每个存储块都分配一个单独的保护键（锁）；在程序状态字储块都分配一个单独的保护键（锁）；在程序状态字PSWPSW中设置有保护键字段，对不同的作业赋予不同的代中设置有保护键字段，对不同的作业赋予不同的代码（钥匙）；钥匙和锁相配才允许访问码（钥匙）；钥匙和锁相配才允许访问2)2)界限寄存器（下页图）界限寄存器（下页图）v上、下界防护上、下界防护：硬件为分给用户作业的连续的主存空间：硬件为分给用户作业的连续的主存空间设置一对上、下界，分别指向该存储空间的上、下界设置一对上、下界，分别指向该存储空间的上、下界v基址、限长防护基址、限长防护
7、：基址寄存器存放当前正执行者的程序：基址寄存器存放当前正执行者的程序地址空间所占分区的始址，限长寄存器存放该地址空间地址空间所占分区的始址，限长寄存器存放该地址空间的长度的长度地址转换与存储保护地址转换与存储保护(4)(4)10下限寄存器下限寄存器20002000上限寄存器上限寄存器35003500基址寄存器基址寄存器20002000限长寄存器限长寄存器15001500进程进程idid下限下限+ +上限寄存器上限寄存器基址基址+ +限长寄存器限长寄存器1 11000+19991000+19991000+9991000+9992 22000+35002000+35002000+15002000+
8、15003 34000+50004000+50004000+10004000+1000内存映像内存映像进程1进程2进程3100019992000350040005000正运行的进程是进程正运行的进程是进程2 2114.2 4.2 连续存储空间管理连续存储空间管理4.2.1 4.2.1 固定分区存储管理固定分区存储管理 4.2.2 4.2.2 可变分区存储管理可变分区存储管理 4.2.3 4.2.3 伙伴系统伙伴系统4.2.4 4.2.4 主存不足的存储管理技术主存不足的存储管理技术124.2.1 4.2.1 固定分区存储管理固定分区存储管理 固定分区存储管理的基本思想固定分区存储管理的基本思想
9、0主存空间被分成数目固定不变的分区，各分区主存空间被分成数目固定不变的分区，各分区的大小不等，每个分区只装入一个作业。的大小不等，每个分区只装入一个作业。 固定分区存储管理的数据结构固定分区存储管理的数据结构0主存分配表：指出各分区的起始地址和长度；主存分配表：指出各分区的起始地址和长度；0占用标志：指示此分区是否被使用。占用标志：指示此分区是否被使用。 作业进入固定分区排队策略作业进入固定分区排队策略0每个分区有单独的作业等待队列；每个分区有单独的作业等待队列；0所有等待处理的作业排成一个等待队列。所有等待处理的作业排成一个等待队列。13固定分区存储管理的地址转换和存储保护固定分区存储管理的
10、地址转换和存储保护 B B下限寄存器下限寄存器逻辑地址逻辑地址CPUCPU绝对地址绝对地址操作系统区操作系统区用户分区用户分区1 1用户分区用户分区2 2用户分区用户分区3 3B+L2B+L2上限寄存器上限寄存器B+L2B+L2越界中断越界中断用户分区用户分区4 4用户分区用户分区5 5用户分区用户分区6 614固定分区的优缺点固定分区的优缺点 优点优点0能够解决单道程序运行在并发环境下不能与能够解决单道程序运行在并发环境下不能与CPUCPU速度匹速度匹配的问题配的问题0解决了单道程序运行时主存空间利用率低的问题解决了单道程序运行时主存空间利用率低的问题0实现简单实现简单 缺点缺点0大作业可能
11、无法装入大作业可能无法装入0主存空间利用率不高，会出现内碎片主存空间利用率不高，会出现内碎片0扩充困难扩充困难0限制多道运行程序的个数限制多道运行程序的个数154.2.2 4.2.2 可变分区存储管理可变分区存储管理 可变分区存储管理是按作业的实际大小来划可变分区存储管理是按作业的实际大小来划分分区，且分区个数也是随机的分分区，且分区个数也是随机的, ,实现多个实现多个作业对主存的共享，进一步提高主存资源利作业对主存的共享，进一步提高主存资源利用率。用率。 16可变分区方式主存分配示例可变分区方式主存分配示例操作系统操作系统作业作业1 1空闲区空闲区作业作业2 2空闲区空闲区4KB4KB10K
12、B10KB46KB46KB52KB52KB128KB128KB操作系统操作系统作业作业1 1空闲区空闲区作业作业2 2空闲区空闲区4KB4KB10KB10KB40KB40KB46KB46KB52KB52KB128KB128KB作业作业3 3操作系统操作系统作业作业1 1空闲区空闲区4KB4KB10KB10KB40KB40KB128KB128KB作业作业3 317可变分区存储管理数据结构可变分区存储管理数据结构 可变分区主存分配表可由两张表格组成，可变分区主存分配表可由两张表格组成， 已分配区表已分配区表 未分配区表未分配区表18可变分区回收算法可变分区回收算法A AX XA AX XB BX
13、XB BA AX XA AB BB B19链表空闲区管理方法链表空闲区管理方法 空闲区开头单元存放本空闲区长度及下个空闲区开头单元存放本空闲区长度及下个空闲区起始地址空闲区起始地址, ,把所有空闲区都链接起来把所有空闲区都链接起来, ,设置第一块空闲区地址指针设置第一块空闲区地址指针, ,让它指向第让它指向第一块空闲区地址。一块空闲区地址。 申请空闲区：沿链查找并取一个长度能满申请空闲区：沿链查找并取一个长度能满足要求的空闲区；足要求的空闲区； 归还空闲区：把此空闲区链入空闲区链表归还空闲区：把此空闲区链入空闲区链表的相应位置。的相应位置。20可变分区管理分配算法可变分区管理分配算法1 1）最
14、先适应分配算法）最先适应分配算法空闲区通常按空闲区通常按地址地址从小到大排列，分配第从小到大排列，分配第一个满足长度要求的空闲区；一个满足长度要求的空闲区；优点：分配从低地址开始，使高地址部分优点：分配从低地址开始，使高地址部分比较少用，以保持一个大空闲区，有利于比较少用，以保持一个大空闲区，有利于大作业的装入；大作业的装入；缺点：分区利用不均衡，回收分区比较麻缺点：分区利用不均衡，回收分区比较麻烦。烦。 212 2）下次适应分配算法）下次适应分配算法1 1）的变种，每次分配时从未分配区的上次扫描）的变种，每次分配时从未分配区的上次扫描结束处顺序查找。结束处顺序查找。可以解决可以解决1 1）的
15、缺点。）的缺点。3) 3) 最优适应分配算法最优适应分配算法分配能满足要求的最小区。分配能满足要求的最小区。可以将空闲区按照可以将空闲区按照大小大小从小到大排列，查找第一从小到大排列，查找第一个满足要求的。个满足要求的。优点：主存利用率好。优点：主存利用率好。缺点：分割剩下的空闲区比较小，难以利用；查缺点：分割剩下的空闲区比较小，难以利用；查找时间比较长。找时间比较长。224 4）最坏适应分配算法）最坏适应分配算法分配能满足要求的最大区；分配能满足要求的最大区；可以将空闲区按照可以将空闲区按照大小大小从大到小排列，查找第一从大到小排列，查找第一个满足要求的。个满足要求的。效率大致等同于最先适应
16、法。效率大致等同于最先适应法。5) 5) 快速适应分配算法快速适应分配算法为经常用到的长度的空闲区设置单独的链表。为经常用到的长度的空闲区设置单独的链表。优点：查找快速；优点：查找快速；缺点：归还时与相邻空闲区的合并即复杂又费时缺点：归还时与相邻空闲区的合并即复杂又费时。 23下表为某系统中的空闲分区表，系统采用可变式分区存储管下表为某系统中的空闲分区表，系统采用可变式分区存储管理策略。现有以下作业序列：理策略。现有以下作业序列：96KB96KB，20KB20KB，200KB200KB，分别使，分别使用首次适应、最佳适用和最坏适用算法来处理这个作业序列用首次适应、最佳适用和最坏适用算法来处理这
17、个作业序列，试问哪一种算法可以满足该作业序列的请求，为什么？，试问哪一种算法可以满足该作业序列的请求，为什么？分区号分区号大小大小起始地址起始地址1 132KB32KB100KB100KB2 210KB10KB150KB150KB3 35KB5KB200KB200KB4 4218KB218KB220KB220KB5 596KB96KB530KB530KB例题：例题：FF(N)FF(N)BF(Y)BF(Y)WF(N)WF(N)2/20/122/20/122/20/122/20/121/96/1221/96/122 3/200/183/200/181/96/1221/96/1222/20/1022
18、/20/1021/96/01/96/024可变分区地址转换与存储保护可变分区地址转换与存储保护 基址基址基址寄存器基址寄存器逻辑地址逻辑地址CPUCPU绝对地址绝对地址操作系统区操作系统区空闲分区空闲分区1 1用户作业用户作业1 1空闲分区空闲分区2 2限长限长限长寄存器限长寄存器 限长限长越界中断越界中断25多对基址多对基址/ /限长寄存器限长寄存器 进程进程B B虚虚CPUCPU进程进程A A虚虚CPUCPU物理主存物理主存进程进程A A私有空间私有空间进程进程B B私有空间私有空间共享区共享区重定位寄存器重定位寄存器1 1限长寄存器限长寄存器1 1重定位寄存器重定位寄存器2 2限长寄存器
19、限长寄存器2 2重定位寄存器重定位寄存器1 1限长寄存器限长寄存器1 1重定位寄存器重定位寄存器2 2限长寄存器限长寄存器2 2 多对重定位寄存器支持主存共享多对重定位寄存器支持主存共享264.2.3 4.2.3 伙伴系统伙伴系统伙伴原理伙伴原理 伙伴系统是一种固定分区和可变分区折中的主存管理算伙伴系统是一种固定分区和可变分区折中的主存管理算法，基本原理：任何尺寸为法，基本原理：任何尺寸为2 2i i的空闲块可以被分为两个尺的空闲块可以被分为两个尺寸为寸为2 2i-1i-1的空闲块，这两个空闲块称为伙伴。的空闲块，这两个空闲块称为伙伴。 伙伴通过对大块的物理主存划分而获得伙伴通过对大块的物理主
20、存划分而获得0假如从第假如从第0 0个页面开始到第个页面开始到第3 3个页面结束的主存个页面结束的主存0每次都对半划分，那么第一次划分获得大小为每次都对半划分，那么第一次划分获得大小为2 2页的伙页的伙伴，如伴，如0 0、1 1和和2 2、3 30进一步划分，可以获得大小为进一步划分，可以获得大小为1 1页的伙伴，例如页的伙伴，例如0 0和和1 1，2 2和和3 30123012327伙伴系统原理伙伴系统原理128k 256k 384k 512k 640k 768k 896k 1M128k 256k 384k 512k 640k 768k 896k 1M A A 128128 256256 5
21、12 512 A AB B6464 256256 512512 A AB B6464 C C 128128 512512 128128B B6464 C C 128128 512512 128128B BD D C C 128128 512512 1281286464D D C C 128128 512512 256256 C C 128128 512512 10241024282.Linux2.Linux伙伴系统伙伴系统1) 1) 以以pagepage结构为数组元素的结构为数组元素的mem_mapmem_map 数数组组2) 2) 以以free_area_structfree_area_st
22、ruct结构为数组元素的结构为数组元素的free_areafree_area数组数组3) 3) 位图数组位图数组(bitmap) (bitmap) 293.Linux3.Linux基于伙伴的基于伙伴的slabslab分配器分配器(1)(1) 为什么要使用为什么要使用slabslab分配器分配器? ?0缓冲机制，能够提高效率缓冲机制，能够提高效率 slabslab的结构的结构0见下页图见下页图 slabslab的操作的操作0kmemkmem-cache-create()-cache-create()0kmem-cache-alockmem-cache-aloc() () 与与kmemkmem-c
23、ache-free()-cache-free()0kmemkmem-cache-grow() -cache-grow() 与与kmemkmem-cache-reap()-cache-reap()0kmalloc()kfreekmalloc()kfree()()0kmem-getpageskmem-getpages() () 与与kmem-frepageskmem-frepages()()30LinuxLinux基于伙伴的基于伙伴的slabslab分配器分配器(2)(2)slabslab分配器组成分配器组成cachecacheslabslabslabslabslabslabslabslabsla
24、bslabslabslabslabslabcachecachecachecacheslabslabslabslab满满slabslab半满半满slabslab空空slabslab存存pcbpcb存存inodeinode存存vmavma314.2.4 4.2.4 主存不足的存储管理技术主存不足的存储管理技术 操作系统操作系统作业作业1 1空闲区空闲区作业作业2 2空闲区空闲区作业作业3 3空闲区空闲区操作系统操作系统作业作业1 1作业作业2 2作业作业3 3空闲区空闲区操作系统操作系统作业作业1 1作业作业2 2作业作业3 3空闲区空闲区作业作业4 41.1.移动技术移动技术32有关移动问题讨论
25、有关移动问题讨论 移动条件移动条件0在可变分区算法中，随着进程不断的装入和撤销，导致在可变分区算法中，随着进程不断的装入和撤销，导致主存中常常出现分散的小空闲区，称为主存中常常出现分散的小空闲区，称为碎片碎片。0当在未分配区中找不到足够大的空闲区来装入新进程时当在未分配区中找不到足够大的空闲区来装入新进程时，可采用移动技术，将分散的空闲空闲区汇集成片。，可采用移动技术，将分散的空闲空闲区汇集成片。 移动时机移动时机0进程撤销之后释放分区时，如果它不与空闲区邻接，立进程撤销之后释放分区时，如果它不与空闲区邻接，立即实施移动。即实施移动。0进程装入分区时，如果它不与空闲区邻接，立即实施引进程装入分
26、区时，如果它不与空闲区邻接，立即实施引动。动。33 移动算法（假设进程移动算法（假设进程A A请求分配请求分配x KBx KB主存）主存）0步骤步骤1 1：查主存分配表，若有大于：查主存分配表，若有大于x KBx KB的空闲区，转步的空闲区，转步骤骤4 4；0步骤步骤2 2：若空闲区总和小于：若空闲区总和小于x KBx KB，则令进程，则令进程A A等待主存等待主存资源；资源；0步骤步骤3 3：移动主存的相关分区信息；修改主存分配表的：移动主存的相关分区信息；修改主存分配表的有关表项；修改被移动者的基础寄存器等信息；有关表项；修改被移动者的基础寄存器等信息；0步骤步骤4 4：分配：分配x KB
27、x KB主存；修改主存分配表的有关项；设主存；修改主存分配表的有关项；设置进程置进程A A的基址寄存器；有申请者等待时予以释放，算的基址寄存器；有申请者等待时予以释放，算法结束。法结束。 开销非常大，极少使用开销非常大，极少使用342.2.对换技术对换技术 对换的作用对换的作用0通过将主存和磁盘的进程移出移入，解决主存通过将主存和磁盘的进程移出移入，解决主存容量不足的问题。容量不足的问题。 对换进程的选择对换进程的选择0选择哪个进程换出；选择哪个进程换出；0决定把进程的哪些信息移出去；决定把进程的哪些信息移出去；0需要确定对换时机。需要确定对换时机。 UNIXUNIX对换器对换器 Window
28、sWindows对换器对换器35在任何时候只在内存中保留所需的指令和数据在任何时候只在内存中保留所需的指令和数据由用户实现，由用户实现，让不会同时调用的子模块共同使用让不会同时调用的子模块共同使用同一内存区同一内存区F20KD22KE24KB12KC15KA30K常驻常驻A A（30KB30KB）覆盖区覆盖区0 0（15KB15KB）覆盖区覆盖区1 1（24KB24KB）A占用占用BC共用共用DEF共用共用3.3.覆盖技术覆盖技术36碎片碎片 外部碎片外部碎片：存在分区外，所有内存之和可以满足：存在分区外，所有内存之和可以满足请求，但不连续请求，但不连续 内部碎片内部碎片：存在分区内，但已不能
29、满足任何请求：存在分区内，但已不能满足任何请求 解决外部碎片问题的方法解决外部碎片问题的方法0紧缩（紧缩（compactioncompaction）：移动内存内容，以便所有空闲）：移动内存内容，以便所有空闲空间合并成一整块空间合并成一整块0允许物理地址空间为非连续允许物理地址空间为非连续x 分页分页x 分段分段374.3 4.3 分页式存储管理分页式存储管理4.3.1 4.3.1 分页式存储管理的基本原理分页式存储管理的基本原理 4.3.2 4.3.2 快表快表4.3.3 4.3.3 分页式存储空间的分配和去配分页式存储空间的分配和去配4.3.4 4.3.4 分页式存储空间的页面共享和保护分页
30、式存储空间的页面共享和保护4.3.5 4.3.5 多级页表多级页表4.3.6 4.3.6 反置页表反置页表384.3.1 4.3.1 分页式存储管理分页式存储管理l为什么要引进分页技术为什么要引进分页技术? ?l基本原理基本原理 页面：进程逻辑地址空间分成大小相等的区；页面：进程逻辑地址空间分成大小相等的区； 页框（帧）：主存物理地址空间分成大小相等页框（帧）：主存物理地址空间分成大小相等的区，其大小跟页面大小相等；的区，其大小跟页面大小相等； 逻辑地址形式：页号页内位移逻辑地址形式：页号页内位移 页表和地址转换（后面图）页表和地址转换（后面图） 基本原理基本原理(1)39基本原理基本原理(2
31、)(2)l作业的页面与分给的页框如何建立联系呢？作业的页面与分给的页框如何建立联系呢？l逻辑地址逻辑地址( (页面页面) )如何变换成物理地址如何变换成物理地址( (页框页框) )呢？呢？l作业的物理地址空间由连续变成分散后，如作业的物理地址空间由连续变成分散后，如何保证程序正确执行呢？何保证程序正确执行呢？使用动态重定位技术，给每个页面设立重定使用动态重定位技术，给每个页面设立重定位寄存器，重定位寄存器的集合便称位寄存器，重定位寄存器的集合便称页表页表。页表是操作系统为每个用户作业建立的，用页表是操作系统为每个用户作业建立的，用来记录程序页面和主存对应页框的对照表。来记录程序页面和主存对应页
32、框的对照表。40页页0 0页页1 1页页2 2页页3 31 14 43 37 70 1 2 3页页0 0页页2 2页页1 1页页3 30 1 2 3 4 5 6 7逻辑内存逻辑内存页表页表物理内存物理内存页号页号 帧号帧号帧号帧号物理内存和逻辑内存的分页模型物理内存和逻辑内存的分页模型41逻辑地址到物理地址的转换逻辑地址到物理地址的转换56120 1 2 3页表页表例：例：说明：页大小为说明：页大小为4B4B，页表如图所示，页表如图所示，将逻辑地址，将逻辑地址0 0、3 3、4 4、1313转换为相转换为相应物理地址应物理地址答案：答案：2020、2323、2424、9 90/4=00/4=0
33、0 50 54+0=204+0=203/4=03/4=03 53 54+3=234+3=234/4=14/4=10 60 64+0=244+0=2413/4=313/4=31 21 24+1=94+1=942练习：逻辑地址到物理地址的转换练习：逻辑地址到物理地址的转换 说明：页大小为说明：页大小为1024B1024B，页表如图所示，页表如图所示，将逻辑地址，将逻辑地址10111011、21482148、30003000、40004000、50125012转换为相应物理地址转换为相应物理地址23160 1 2 3页表页表 答案：答案：30593059、11241124、19761976、7072
34、7072、逻、逻辑地址非法辑地址非法1011/1024=01011/1024=01011 21011 21024+1011=30591024+1011=30592148/1024=22148/1024=2100 1100 11024+100=11241024+100=11243000/1024=23000/1024=2952 1952 11024+952=19761024+952=19764000/1024=34000/1024=3928 6928 61024+928=70721024+928=70725012/1024=45012/1024=4916 916 页号页号4 4不存在不存在434
35、.3.2 4.3.2 快表快表 相联存储器（翻译后备缓冲（相联存储器（翻译后备缓冲（translation translation look-aside bufferlook-aside buffer，TLBTLB）：关联的快速内存）：关联的快速内存 TLBTLB与页表一起工作（了解工作过程）与页表一起工作（了解工作过程）44采用相联存储器的地址转换采用相联存储器的地址转换假定访问主存时间为假定访问主存时间为100100毫微秒，访问相联存储器毫微秒，访问相联存储器时间为时间为2020毫微秒，相联存储器为毫微秒，相联存储器为3232个单元时快表个单元时快表命中率可达命中率可达90%90%，按逻辑
36、地址存取的平均时间为：，按逻辑地址存取的平均时间为：（1001002020）90%90%(100+100+20)(100+100+20)(1-90%)(1-90%)130130比两次访问主存的时间比两次访问主存的时间1001002+202+20200200下降了三下降了三成多。成多。454.3.3 4.3.3 分页式存储空间的分配和去配分页式存储空间的分配和去配(1)(1) 位示图法位示图法0每位与一帧相对应，用每位与一帧相对应，用0/10/1表示对应块为空闲表示对应块为空闲/ /已占用，用另一专门字记录当前空闲块数。已占用，用另一专门字记录当前空闲块数。 链表方法链表方法0每个表项包含：每个
37、表项包含：x进程占用区（进程占用区（P P）还是空闲区（）还是空闲区（H H）x起始地址起始地址x长度长度x指向下一表项的指针指向下一表项的指针46主存分配的位示图和链表方法主存分配的位示图和链表方法474.3.4 4.3.4 分页存储空间的页面共享和保护分页存储空间的页面共享和保护(1)(1) 数据共享数据共享0允许不同进程对共享的数据页用不同的页号，允许不同进程对共享的数据页用不同的页号，只要让各自页表中的有关表项指向共享的数据只要让各自页表中的有关表项指向共享的数据页框；页框； 程序共享程序共享0指令包含指向其它指令或数据的地址。指令包含指向其它指令或数据的地址。 标志位保护方法标志位保
38、护方法0在页表中增加标志位，指出此页的信息只读在页表中增加标志位，指出此页的信息只读/ /读写读写/ /只可执行只可执行/ /不可访问等。不可访问等。 键保护方法键保护方法48分页存储空间的页面共享和保护分页存储空间的页面共享和保护(2)(2) 共享库共享库 0包含共享函数的目标代码块包含共享函数的目标代码块 动态链接器动态链接器0负责动态链接。负责动态链接。0动态链接：共享库运行时可加载到任意的主存动态链接：共享库运行时可加载到任意的主存区域，并在主存中和一个程序链接起来。区域，并在主存中和一个程序链接起来。 编译和动态链接共享库的过程编译和动态链接共享库的过程49分页存储空间的页面共享和保
39、护分页存储空间的页面共享和保护(3)(3) WindowsWindows动态链接动态链接编译后的目标文件编译后的目标文件引入库引入库(DLL(DLL函数的定位信息函数的定位信息) )链接器链接器可执行程序可执行程序 主存主存重要定位重要定位信息信息动态链动态链接库接库调用调用DLLDLL中的函数中的函数504.3.5 4.3.5 多级页表多级页表 多级页表的概念多级页表的概念 多级页表的具体做法多级页表的具体做法 逻辑地址结构逻辑地址结构 逻辑地址到物理地址转换过程逻辑地址到物理地址转换过程51多级页表的概念多级页表的概念 系统为每个进程建一张页目录表系统为每个进程建一张页目录表, ,它的每个
40、表项它的每个表项对应一个页表页对应一个页表页, ,而页表页的每个表项给出了页而页表页的每个表项给出了页面和页框的对应关系面和页框的对应关系, ,页目录表是一级页表页目录表是一级页表, ,页表页表页是二级页表。页是二级页表。 逻辑地址结构有三部分组成：页目录、页表页和逻辑地址结构有三部分组成：页目录、页表页和位移。位移。 52多级页表地址转换过程多级页表地址转换过程 页框号页框号 页内位移页内位移 页目录位移页目录位移 页表页位移页表页位移 页内位移页内位移B BF F进程一级页表进程一级页表进程二级页表进程二级页表物理地址物理地址逻辑地址逻辑地址页目录表页目录表控制寄存器控制寄存器53解决页表
41、页占用主存空间的问题解决页表页占用主存空间的问题 进程运行涉及页面的页表页应放在主存进程运行涉及页面的页表页应放在主存, ,其其他页表页使用时再调入他页表页使用时再调入, , 在页目录表中增加特征位在页目录表中增加特征位, ,指示对应的页表指示对应的页表页是否已调入主存页是否已调入主存, , 地址转换机构根据逻辑地址中的地址转换机构根据逻辑地址中的dir,dir,去查去查页目录表对应表项页目录表对应表项, ,如未调入如未调入, ,应产生一个应产生一个”缺页表页缺页表页”中断信号，请求操作系统将中断信号，请求操作系统将页表页调入主存。页表页调入主存。54SUN SPARCSUN SPARC计算机
42、三级分页结构计算机三级分页结构 上下文号上下文号索引索引1(8) 1(8) 索引索引2(6) 2(6) 索引索引3(6) 3(6) 偏移偏移(12)(12)上下文表上下文表第一级第一级第二级第二级第三级第三级4K4K页面页面0 040954095页表页表55多级页表结构的本质多级页表结构的本质 多级不连续导致多级索引。多级不连续导致多级索引。 以二级页表为例，用户程序的页面不连续以二级页表为例，用户程序的页面不连续存放，要有页面地址索引，该索引是进程存放，要有页面地址索引，该索引是进程页表；进程页表又是不连续存放的多个页页表；进程页表又是不连续存放的多个页表页，故页表页也要页表页地址索引，该表
43、页，故页表页也要页表页地址索引，该索引就是页目录。索引就是页目录。 页目录项是页表页的索引，而页表页项是页目录项是页表页的索引，而页表页项是进程程序的页面索引。进程程序的页面索引。564.3.5 4.3.5 反置页表反置页表(1)(1) 页框号页框号 位移位移进程标识进程标识 页号页号 位移位移 进程标识进程标识 页号页号 特征位特征位 链指针链指针 序号序号反置页表反置页表物理地址物理地址逻辑地址逻辑地址哈希哈希函数函数哈希表哈希表反置页表及其地址转换反置页表及其地址转换57反置页表反置页表(2)(2) IPTIPT是为主存中的每一个物理块建立一个页是为主存中的每一个物理块建立一个页表并按照
44、块号排序表并按照块号排序, , 该表每个表项包含正在访问该页框的进程该表每个表项包含正在访问该页框的进程标识、页号及特征位标识、页号及特征位, ,用来完成主存页框到用来完成主存页框到访问进程的页号、即物理地址到逻辑地址访问进程的页号、即物理地址到逻辑地址的转换。的转换。58反置页表反置页表(3)(3)反置页表地址转换过程如下反置页表地址转换过程如下: :逻辑地址给出进程标识和页号逻辑地址给出进程标识和页号, ,用它们去比较用它们去比较IPT,IPT,若整个反置页表中未能找到匹配的页表项若整个反置页表中未能找到匹配的页表项, ,说明该页不在主存说明该页不在主存, ,产生请页中断产生请页中断, ,
45、请求操作系统请求操作系统调入调入; ;否则，该表项的序号便是页框号否则，该表项的序号便是页框号, ,块号加上块号加上位移位移, ,便形成物理地址。便形成物理地址。59 分页技术分页技术不会不会产生产生外部碎片外部碎片，但，但会会产生产生内内部碎片部碎片 分页的重要特点是用户观点的内存和实际分页的重要特点是用户观点的内存和实际的物理内存的分离的物理内存的分离 分页可以共享共同代码分页可以共享共同代码分页内存管理方案小结分页内存管理方案小结604.4 4.4 分段式存储管理分段式存储管理4.4.1 4.4.1 程序的分段结构程序的分段结构4.4.2 4.4.2 分段式存储管理的基本原理分段式存储管
46、理的基本原理4.4.3 4.4.3 段的共享和保护段的共享和保护4.4.4 4.4.4 分段和分页的比较分段和分页的比较614.4.1 4.4.1 程序的分段结构程序的分段结构 分段存储管理引入的主要原因分段存储管理引入的主要原因0满足用户（程序员）编程和使用上的要求。满足用户（程序员）编程和使用上的要求。 模块化程序设计的分段结构（下页图）模块化程序设计的分段结构（下页图） 分页存储管理分页存储管理-一维地址结构一维地址结构 分段存储管理分段存储管理-二维地址结构二维地址结构62模块化程序设计的分段结构模块化程序设计的分段结构 子程序段子程序段X X数组段数组段A Acall Xcall X
47、( (调用调用X X段的入口段的入口E)E)call Ycall Y( (调用调用Y Y段的入口段的入口F)F)load 1,Aload 1,A ( (调用数组段调用数组段AG)AG)主程序段主程序段E E：F F：子程序段子程序段Y YG G：工作区段工作区段634.4.2 4.4.2 分段式存储管理的基本原理分段式存储管理的基本原理(1)(1)l两维逻辑地址两维逻辑地址l段号：段内地址段号：段内地址l段表段表l段表指出主存中各分段的段号、段起始地址和段表指出主存中各分段的段号、段起始地址和段长度，起到基址段长度，起到基址/ /限长寄存器的作用。限长寄存器的作用。l段式存储管理的地址转换和存
48、储保护段式存储管理的地址转换和存储保护 64分段式存储管理的基本原理分段式存储管理的基本原理(2)(2) 段控制寄存器段控制寄存器 段表始址段表始址 段表长度段表长度 段号段号s s 位移位移d d 段长段长 基址基址 物理地址物理地址越界越界? ? 段表段表65段表：将二维的逻辑地址映射为一维物理地址段表：将二维的逻辑地址映射为一维物理地址段基地址：包含该段在内存中的开始物理地址段基地址：包含该段在内存中的开始物理地址段界限：指定该段的长度段界限：指定该段的长度逻辑地址：段号逻辑地址：段号s s段内偏移段内偏移d d逻辑地址到物理地址的转换逻辑地址到物理地址的转换1)1) 段号与段表长度进行
49、比较，若段号超过了段表长度段号与段表长度进行比较，若段号超过了段表长度，则越界（非法地址），否则转，则越界（非法地址），否则转2 2）2)2) 根据段表始址和段号计算出该段对应段表项的位置根据段表始址和段号计算出该段对应段表项的位置，从中读出该段在内存的起始地址，检查段内地址，从中读出该段在内存的起始地址，检查段内地址是否超过该段的段长，若超过则越界（非法地址）是否超过该段的段长，若超过则越界（非法地址），否则转，否则转3 3）3)3) 将该段的起始地址与段内位移相加，从而得到要访将该段的起始地址与段内位移相加，从而得到要访问的物理地址问的物理地址逻辑地址到物理地址转换逻辑地址到物理地址转换6
50、6逻辑地址到物理地址转换例逻辑地址到物理地址转换例说明：段表如表说明：段表如表1 1所示，将表所示，将表2 2所示逻辑地址转换为相应所示逻辑地址转换为相应物理地址物理地址答案：见表答案：见表3 3段号段号 内存起始内存起始地址地址段长段长0 02192196006001 12300230014142 290901001003 3132713275805804 4195219529696段段号号段内位段内位移移2 288884 4100100178178非法非法 表表1 表表2 表表390+881009667说明：段表如表说明：段表如表1 1所示，将表所示，将表2 2所示逻辑地址转换为相应所示逻
