操作系统-第4章-存储管理课件.ppt

《操作系统-第4章-存储管理课件.ppt》由会员分享，可在线阅读，更多相关《操作系统-第4章-存储管理课件.ppt（158页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第4 4章章 存储管理存储管理重要内容重要内容0存储器存储器0连续存储空间管理连续存储空间管理0分页存储管理分页存储管理0分段存储管理分段存储管理0虚拟存储管理虚拟存储管理0Intel x86Intel x86分段和分页存储结构分段和分页存储结构0LinuxLinux虚拟存储管理虚拟存储管理0Windows 2003Windows 2003虚拟存储管理虚拟存储管理1存储管理的功能存储管理的功能分配和去配分配和去配0请求和释放主存空间请求和释放主存空间抽象和映射抽象和映射0抽象成一维数组或二维地址空间抽象成一维数组或二维地址空间0地址转换地址转换隔离和共享隔离和共享0隔离实现存储保护功能隔离实

2、现存储保护功能0超越隔离机制，提高主存利用率超越隔离机制，提高主存利用率存储扩充存储扩充0虚拟，允许进程虚拟地址空间大于主存空间虚拟，允许进程虚拟地址空间大于主存空间24.1 4.1 存储器存储器4.1.1 4.1.1 存储器的层次存储器的层次 4.1.2 4.1.2 地址转换与存储保护地址转换与存储保护 34.1.1 4.1.1 存储器的层次存储器的层次寄存器寄存器高速缓存高速缓存主存储器主存储器磁盘缓存磁盘缓存固定磁盘固定磁盘可移动存储介质可移动存储介质44.1.2 4.1.2 地址转换与存储保护地址转换与存储保护(1)(1)链接链接动态动态重定重定位位静态静态重定重定位位源程序源程序模块

3、模块1 1源程序源程序模块模块2 2源程序源程序模块模块n n目标目标代码代码1 1目标目标代码代码2 2目标目标代码代码n n可重定位可重定位目标代码目标代码(装载代码装载代码)()(辅存辅存)编译编译装入装入执行执行程序名字程序名字空间空间逻辑地址逻辑地址空间空间物理地址物理地址空间空间可执行可执行二进代二进代码码(主存主存)库代码库代码可执行可执行二进代二进代码码(主存主存)程序的编译、链接、装入和执行程序的编译、链接、装入和执行5地址转换与存储保护地址转换与存储保护(2)(2)逻辑地址（虚地址）：逻辑地址（虚地址）：CPUCPU所生成的地址所生成的地址物理地址（实地址）：内存单元所看到

4、的地址物理地址（实地址）：内存单元所看到的地址逻辑地址空间：由程序所生成的所有逻辑地址的逻辑地址空间：由程序所生成的所有逻辑地址的集合集合物理地址空间：由逻辑地址所对应的所有物理地物理地址空间：由逻辑地址所对应的所有物理地址的集合址的集合地址转换或重定位：把逻辑地址转换为物理地址地址转换或重定位：把逻辑地址转换为物理地址6静态重定位静态重定位0地址转换工作在进程执行前一次完成；地址转换工作在进程执行前一次完成；0无须硬件支持，易于实现，但不允许程序在执行过程无须硬件支持，易于实现，但不允许程序在执行过程中移动位置。中移动位置。0早期单用户单任务系统早期单用户单任务系统动态重定位动态重定位0地址

5、转换推迟到最后的可能时刻，即进程执行时才完地址转换推迟到最后的可能时刻，即进程执行时才完成；成；0允许程序在主存中移动、便于主存共享、主存利用率允许程序在主存中移动、便于主存共享、主存利用率高。高。地址转换与存储保护地址转换与存储保护(3)(3)7例：使用重定位寄存器的动态重定位例：使用重定位寄存器的动态重定位8存储保护存储保护问题：保护操作系统不受用户进程所影响，保护用户进程问题：保护操作系统不受用户进程所影响，保护用户进程不受其他用户进程所影响不受其他用户进程所影响方法方法1)1)存储键保护存储键保护v系统将主存划分成大小相等的若干存储块，并给每个存系统将主存划分成大小相等的若干存储块，并

6、给每个存储块都分配一个单独的保护键（锁）；在程序状态字储块都分配一个单独的保护键（锁）；在程序状态字PSWPSW中设置有保护键字段，对不同的作业赋予不同的代中设置有保护键字段，对不同的作业赋予不同的代码（钥匙）；钥匙和锁相配才允许访问码（钥匙）；钥匙和锁相配才允许访问2)2)界限寄存器（下页图）界限寄存器（下页图）v上、下界防护上、下界防护：硬件为分给用户作业的连续的主存空间：硬件为分给用户作业的连续的主存空间设置一对上、下界，分别指向该存储空间的上、下界设置一对上、下界，分别指向该存储空间的上、下界v基址、限长防护基址、限长防护：基址寄存器存放当前正执行者的程序：基址寄存器存放当前正执行者的

7、程序地址空间所占分区的始址，限长寄存器存放该地址空间地址空间所占分区的始址，限长寄存器存放该地址空间的长度的长度地址转换与存储保护地址转换与存储保护(4)(4)9下限寄存器下限寄存器20002000上限寄存器上限寄存器35003500基址寄存器基址寄存器20002000限长寄存器限长寄存器15001500进程进程idid下限下限+上限寄存器上限寄存器基址基址+限长寄存器限长寄存器1 11000+19991000+19991000+9991000+9992 22000+35002000+35002000+15002000+15003 34000+50004000+50004000+1000400

8、0+1000内存映像内存映像进程1进程2进程3100019992000350040005000正运行的进程是进程正运行的进程是进程2 2104.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 主存不足的存储管理技术主存不足的存储管理技术114.2.1 4.2.1 固定分区存储管理固定分区存储管理固定分区存储管理的基本思想固定分区存储管理的基本思想0主主存存空空间间被被分分成成数数目目固固定定不不变变的的分分区区，各各分分

9、区区的大小不等，每个分区只装入一个作业。的大小不等，每个分区只装入一个作业。固定分区存储管理的数据结构固定分区存储管理的数据结构0主存分配表：指出各分区的起始地址和长度；主存分配表：指出各分区的起始地址和长度；0占用标志：指示此分区是否被使用。占用标志：指示此分区是否被使用。作业进入固定分区排队策略作业进入固定分区排队策略0每个分区有单独的作业等待队列；每个分区有单独的作业等待队列；0所有等待处理的作业排成一个等待队列。所有等待处理的作业排成一个等待队列。12固定分区存储管理的地址转换和存储保护固定分区存储管理的地址转换和存储保护 B B下限寄存器下限寄存器逻辑地址逻辑地址CPUCPU绝对地址

10、绝对地址操作系统区操作系统区用户分区用户分区1 1用户分区用户分区2 2用户分区用户分区3 3B+L2B+L2上限寄存器上限寄存器B+L2B+L2越界中断越界中断用户分区用户分区4 4用户分区用户分区5 5用户分区用户分区6 613固定分区的优缺点固定分区的优缺点优点优点0能够解决单道程序运行在并发环境下不能与能够解决单道程序运行在并发环境下不能与CPUCPU速度匹速度匹配的问题配的问题0解决了单道程序运行时主存空间利用率低的问题解决了单道程序运行时主存空间利用率低的问题0实现简单实现简单缺点缺点0大作业可能无法装入大作业可能无法装入0主存空间利用率不高，会出现内碎片主存空间利用率不高，会出现

11、内碎片0扩充困难扩充困难0限制多道运行程序的个数限制多道运行程序的个数144.2.2 4.2.2 可变分区存储管理可变分区存储管理 可变分区存储管理是按作业的实际大小来划可变分区存储管理是按作业的实际大小来划分分区，且分区个数也是随机的分分区，且分区个数也是随机的,实现多个作实现多个作业对主存的共享，进一步提高主存资源利用业对主存的共享，进一步提高主存资源利用率。率。15可变分区方式主存分配示例可变分区方式主存分配示例操作系统操作系统作业作业1 1空闲区空闲区作业作业2 2空闲区空闲区4KB4KB10KB10KB46KB46KB52KB52KB128KB128KB操作系统操作系统作业作业1 1

12、空闲区空闲区作业作业2 2空闲区空闲区4KB4KB10KB10KB40KB40KB46KB46KB52KB52KB128KB128KB作业作业3 3操作系统操作系统作业作业1 1空闲区空闲区4KB4KB10KB10KB40KB40KB128KB128KB作业作业3 316可变分区存储管理数据结构可变分区存储管理数据结构 可变分区主存分配表可由两张表格组成，可变分区主存分配表可由两张表格组成，已分配区表已分配区表未分配区表未分配区表17可变分区回收算法可变分区回收算法A AX XA AX XB BX XB BA AX XA AB BB B18链表空闲区管理方法链表空闲区管理方法空空闲闲区区开开头

13、头单单元元存存放放本本空空闲闲区区长长度度及及下下个个空空闲闲区区起起始始地地址址,把把所所有有空空闲闲区区都都链链接接起起来来,设设置置第第一一块块空空闲闲区区地地址址指指针针,让让它它指指向向第第一块空闲区地址。一块空闲区地址。申申请请空空闲闲区区：沿沿链链查查找找并并取取一一个个长长度度能能满满足要求的空闲区；足要求的空闲区；归归还还空空闲闲区区：把把此此空空闲闲区区链链入入空空闲闲区区链链表表的相应位置。的相应位置。19可变分区管理分配算法可变分区管理分配算法1 1）最先适应分配算法）最先适应分配算法空闲区通常按空闲区通常按地址地址从小到大排列，分配第一从小到大排列，分配第一个满足长度

14、要求的空闲区；个满足长度要求的空闲区；优点：分配从低地址开始，使高地址部分比优点：分配从低地址开始，使高地址部分比较少用，以保持一个大空闲区，有利于大较少用，以保持一个大空闲区，有利于大作业的装入；作业的装入；缺点：分区利用不均衡，回收分区比较麻烦。缺点：分区利用不均衡，回收分区比较麻烦。202 2）下次适应分配算法）下次适应分配算法1 1）的变种，每次分配时从未分配区的上次扫描结）的变种，每次分配时从未分配区的上次扫描结束处顺序查找。束处顺序查找。可以解决可以解决1 1）的缺点。）的缺点。3)3)最优适应分配算法最优适应分配算法分配能满足要求的最小区。分配能满足要求的最小区。可以将空闲区按照

15、可以将空闲区按照大小大小从小到大排列，查找第一从小到大排列，查找第一个满足要求的。个满足要求的。优点：主存利用率好。优点：主存利用率好。缺点：分割剩下的空闲区比较小，难以利用；查缺点：分割剩下的空闲区比较小，难以利用；查找时间比较长。找时间比较长。214 4）最坏适应分配算法）最坏适应分配算法分配能满足要求的最大区；分配能满足要求的最大区；可以将空闲区按照可以将空闲区按照大小大小从大到小排列，查找第一从大到小排列，查找第一个满足要求的。个满足要求的。效率大致等同于最先适应法。效率大致等同于最先适应法。5)5)快速适应分配算法快速适应分配算法为经常用到的长度的空闲区设置单独的链表。为经常用到的长

16、度的空闲区设置单独的链表。优点：查找快速；优点：查找快速；缺点：归还时与相邻空闲区的合并即复杂又费时。缺点：归还时与相邻空闲区的合并即复杂又费时。22下表为某系统中的空闲分区表，系统采用可变式分区存储管下表为某系统中的空闲分区表，系统采用可变式分区存储管理策略。现有以下作业序列：理策略。现有以下作业序列：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/20/1021/96/01/96/023可变分区地址转换与存储保护可变分区地址转换与存储保护 基址基址基址寄存器基址寄存器逻辑地

18、址逻辑地址CPUCPU绝对地址绝对地址操作系统区操作系统区空闲分区空闲分区1 1用户作业用户作业1 1空闲分区空闲分区2 2限长限长限长寄存器限长寄存器 限长限长越界中断越界中断24多对基址多对基址/限长寄存器限长寄存器 进程进程B B虚虚CPUCPU进程进程A A虚虚CPUCPU物理主存物理主存进程进程A A私有空间私有空间进程进程B B私有空间私有空间共享区共享区重定位寄存器重定位寄存器1 1限长寄存器限长寄存器1 1重定位寄存器重定位寄存器2 2限长寄存器限长寄存器2 2重定位寄存器重定位寄存器1 1限长寄存器限长寄存器1 1重定位寄存器重定位寄存器2 2限长寄存器限长寄存器2 2 多对

19、重定位寄存器支持主存共享多对重定位寄存器支持主存共享254.2.3 4.2.3 伙伴系统伙伴系统伙伴原理伙伴原理伙伴系统是一种固定分区和可变分区折中的主存管理算法，伙伴系统是一种固定分区和可变分区折中的主存管理算法，基本原理：任何尺寸为基本原理：任何尺寸为2 2i i的空闲块可以被分为两个尺寸为的空闲块可以被分为两个尺寸为2 2i-1i-1的空闲块，这两个空闲块称为伙伴。的空闲块，这两个空闲块称为伙伴。伙伴通过对大块的物理主存划分而获得伙伴通过对大块的物理主存划分而获得0假如从第假如从第0 0个页面开始到第个页面开始到第3 3个页面结束的主存个页面结束的主存0每次都对半划分，那么第一次划分获得

20、大小为每次都对半划分，那么第一次划分获得大小为2 2页的伙页的伙伴，如伴，如0 0、1 1和和2 2、3 30进一步划分，可以获得大小为进一步划分，可以获得大小为1 1页的伙伴，例如页的伙伴，例如0 0和和1 1，2 2和和3 30123012326伙伴系统原理伙伴系统原理128k 256k 384k 512k 640k 768k 896k 1M128k 256k 384k 512k 640k 768k 896k 1M A A 128128 256256 512 512 A AB B6464 256256 512512 A AB B6464 C C 128128 512512 128128B

21、B6464 C C 128128 512512 128128B BD D C C 128128 512512 1281286464D D C C 128128 512512 256256 C C 128128 512512 10241024272.Linux2.Linux伙伴系统伙伴系统1)1)以以pagepage结构为数组元素的结构为数组元素的mem_mapmem_map 数组数组2)2)以以free_area_structfree_area_struct结构为数组元素的结构为数组元素的free_areafree_area数组数组3)3)位图数组位图数组(bitmap)(bitmap)283

22、.Linux3.Linux基于伙伴的基于伙伴的slabslab分配器分配器(1)(1)为什么要使用为什么要使用slabslab分配器分配器?0缓冲机制，能够提高效率缓冲机制，能够提高效率slabslab的结构的结构0见下页图见下页图slabslab的操作的操作0kmemkmem-cache-create()-cache-create()0kmem-cache-alockmem-cache-aloc()()与与kmemkmem-cache-free()-cache-free()0kmemkmem-cache-grow()-cache-grow()与与kmemkmem-cache-reap()-c

23、ache-reap()0kmalloc()kfreekmalloc()kfree()()0kmem-getpageskmem-getpages()()与与kmem-frepageskmem-frepages()()29LinuxLinux基于伙伴的基于伙伴的slabslab分配器分配器(2)(2)slabslab分配器组成分配器组成cachecacheslabslabslabslabslabslabslabslabslabslabslabslabslabslabcachecachecachecacheslabslabslabslab满满slabslab半满半满slabslab空空slabsla

24、b存存pcbpcb存存inodeinode存存vmavma304.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.移动技术移动技术31有关移动问题讨论有关移动问题讨论移动条件移动条件0在可变分区算法中，随着进程不断的装入和撤销，导致在可变分区算法中，随着进程不断的装入和撤销，导致主存中常常出现分散的小空闲区，称为主存中常常出

25、现分散的小空闲区，称为碎片碎片。0当在未分配区中找不到足够大的空闲区来装入新进程时，当在未分配区中找不到足够大的空闲区来装入新进程时，可采用移动技术，将分散的空闲空闲区汇集成片。可采用移动技术，将分散的空闲空闲区汇集成片。移动时机移动时机0进程撤销之后释放分区时，如果它不与空闲区邻接，立进程撤销之后释放分区时，如果它不与空闲区邻接，立即实施移动。即实施移动。0进程装入分区时，如果它不与空闲区邻接，立即实施引进程装入分区时，如果它不与空闲区邻接，立即实施引动。动。32移动算法（假设进程移动算法（假设进程A A请求分配请求分配x KBx KB主存）主存）0步骤步骤1 1：查主存分配表，若有大于：查

26、主存分配表，若有大于x KBx KB的空闲区，转步的空闲区，转步骤骤4 4；0步骤步骤2 2：若空闲区总和小于：若空闲区总和小于x KBx KB，则令进程，则令进程A A等待主存等待主存资源；资源；0步骤步骤3 3：移动主存的相关分区信息；修改主存分配表的：移动主存的相关分区信息；修改主存分配表的有关表项；修改被移动者的基础寄存器等信息；有关表项；修改被移动者的基础寄存器等信息；0步骤步骤4 4：分配：分配x KBx KB主存；修改主存分配表的有关项；设主存；修改主存分配表的有关项；设置进程置进程A A的基址寄存器；有申请者等待时予以释放，算的基址寄存器；有申请者等待时予以释放，算法结束。法结

27、束。开销非常大，极少使用开销非常大，极少使用332.2.对换技术对换技术对换的作用对换的作用0通过将主存和磁盘的进程移出移入，解决主存通过将主存和磁盘的进程移出移入，解决主存容量不足的问题。容量不足的问题。对换进程的选择对换进程的选择0选择哪个进程换出；选择哪个进程换出；0决定把进程的哪些信息移出去；决定把进程的哪些信息移出去；0需要确定对换时机。需要确定对换时机。UNIXUNIX对换器对换器WindowsWindows对换器对换器34在任何时候只在内存中保留所需的指令和数据在任何时候只在内存中保留所需的指令和数据由用户实现，由用户实现，让不会同时调用的子模块共同使用让不会同时调用的子模块共同

28、使用同一内存区同一内存区F20KD22KE24KB12KC15KA30K常驻常驻A A（30KB30KB）覆盖区覆盖区0 0（15KB15KB）覆盖区覆盖区1 1（24KB24KB）A占用占用BC共用共用DEF共用共用3.3.覆盖技术覆盖技术35碎片碎片外部碎片外部碎片：存在分区外，所有内存之和可以满足：存在分区外，所有内存之和可以满足请求，但不连续请求，但不连续内部碎片内部碎片：存在分区内，但已不能满足任何请求：存在分区内，但已不能满足任何请求解决外部碎片问题的方法解决外部碎片问题的方法0紧缩（紧缩（compactioncompaction）：）：移动内存内容，以便所有空闲移动内存内容，以便

29、所有空闲空间合并成一整块空间合并成一整块0允许物理地址空间为非连续允许物理地址空间为非连续x 分页分页x 分段分段364.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 分页式存储空间的页面共享和保护分页式存储空间的页面共享和保护4.3.5 4.3.5 多级页表多级页表4.3.6 4.3.6 反置页表反置页表374.3.1 4.3.1 分页式存储管理分页式存储管理l为什么要引进分页技术为什么要引进分

30、页技术?l基本原理基本原理页面：进程逻辑地址空间分成大小相等的区；页面：进程逻辑地址空间分成大小相等的区；页框（帧）：主存物理地址空间分成大小相等页框（帧）：主存物理地址空间分成大小相等的区，其大小跟页面大小相等；的区，其大小跟页面大小相等；逻辑地址形式：页号页内位移逻辑地址形式：页号页内位移 页表和地址转换（后面图）页表和地址转换（后面图）基本原理基本原理(1)38基本原理基本原理(2)(2)l作业的页面与分给的页框如何建立联系呢？作业的页面与分给的页框如何建立联系呢？l逻辑地址逻辑地址(页面页面)如何变换成物理地址如何变换成物理地址(页框页框)呢？呢？l作业的物理地址空间由连续变成分散后，

31、如作业的物理地址空间由连续变成分散后，如何保证程序正确执行呢？何保证程序正确执行呢？使用动态重定位技术，给每个页面设立重定使用动态重定位技术，给每个页面设立重定位寄存器，重定位寄存器的集合便称位寄存器，重定位寄存器的集合便称页表页表。页表是操作系统为每个用户作业建立的，用页表是操作系统为每个用户作业建立的，用来记录程序页面和主存对应页框的对照表。来记录程序页面和主存对应页框的对照表。39页页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逻辑内存逻辑内存页表页表物理内存物理内存页号页号 帧号帧号帧号

32、帧号物理内存和逻辑内存的分页模型物理内存和逻辑内存的分页模型40逻辑地址到物理地址的转换逻辑地址到物理地址的转换56120 1 2 3页表页表例：例：说明：页大小为说明：页大小为4B4B，页表如图所示，页表如图所示，将逻辑地址将逻辑地址0 0、3 3、4 4、1313转换为相应转换为相应物理地址物理地址答案：答案：2020、2323、2424、9 90/4=00 54+0=200/4=00 54+0=203/4=03 54+3=233/4=03 54+3=234/4=10 64+0=244/4=10 64+0=2413/4=31 24+1=913/4=31 24+1=941练习：逻辑地址到物理

33、地址的转换练习：逻辑地址到物理地址的转换说明：页大小为说明：页大小为1024B1024B，页表如图所示，页表如图所示，将逻辑地址将逻辑地址10111011、21482148、30003000、40004000、50125012转换为相应物理地址转换为相应物理地址23160 1 2 3页表页表答案：答案：30593059、11241124、19761976、70727072、逻、逻辑地址非法辑地址非法1011/1024=01011 21024+1011=30591011/1024=01011 21024+1011=30592148/1024=2100 11024+100=11242148/102

34、4=2100 11024+100=11243000/1024=2952 11024+952=19763000/1024=2952 11024+952=19764000/1024=3928 61024+928=70724000/1024=3928 61024+928=70725012/1024=4916 5012/1024=4916 页号页号4 4不存在不存在424.3.2 4.3.2 快表快表相联存储器（相联存储器（翻译后备缓冲（翻译后备缓冲（translation translation look-aside bufferlook-aside buffer，TLBTLB）：关联的快速内存）：

35、关联的快速内存TLBTLB与页表一起工作（了解工作过程）与页表一起工作（了解工作过程）43采用相联存储器的地址转换采用相联存储器的地址转换假假定定访访问问主主存存时时间间为为100100毫毫微微秒秒，访访问问相相联联存存储储器器时时间间为为2020毫毫微微秒秒，相相联联存存储储器器为为3232个个单单元元时时快快表表命中率可达命中率可达90%90%，按逻辑地址存取的平均时间为：，按逻辑地址存取的平均时间为：（1001002020）90%90%(100+100+20)(1-90%)(100+100+20)(1-90%)130130比比两两次次访访问问主主存存的的时时间间1002+201002+2

36、0200200下下降降了了三三成多。成多。444.3.3 4.3.3 分页式存储空间的分配和去配分页式存储空间的分配和去配(1)(1)位示图法位示图法0每位与一帧相对应，用每位与一帧相对应，用0/10/1表示对应块为空闲表示对应块为空闲/已占用，用另一专门字记录当前空闲块数。已占用，用另一专门字记录当前空闲块数。链表方法链表方法0每个表项包含：每个表项包含：x进程占用区（进程占用区（P P）还是空闲区（）还是空闲区（H H）x起始地址起始地址x长度长度x指向下一表项的指针指向下一表项的指针45主存分配的位示图和链表方法主存分配的位示图和链表方法464.3.4 4.3.4 分页存储空间的页面共享

37、和保护分页存储空间的页面共享和保护(1)(1)数据共享数据共享0允许不同进程对共享的数据页用不同的页号，允许不同进程对共享的数据页用不同的页号，只要让各自页表中的有关表项指向共享的数据只要让各自页表中的有关表项指向共享的数据页框；页框；程序共享程序共享0指令包含指向其它指令或数据的地址。指令包含指向其它指令或数据的地址。标志位保护方法标志位保护方法0在在页页表表中中增增加加标标志志位位，指指出出此此页页的的信信息息只只读读/读写读写/只可执行只可执行/不可访问等。不可访问等。键保护方法键保护方法47分页存储空间的页面共享和保护分页存储空间的页面共享和保护(2)(2)共享库共享库 0包含共享函数

38、的目标代码块包含共享函数的目标代码块动态链接器动态链接器0负责动态链接。负责动态链接。0动态链接：共享库运行时可加载到任意的主存动态链接：共享库运行时可加载到任意的主存区域，并在主存中和一个程序链接起来。区域，并在主存中和一个程序链接起来。编译和动态链接共享库的过程编译和动态链接共享库的过程48分页存储空间的页面共享和保护分页存储空间的页面共享和保护(3)(3)WindowsWindows动态链接动态链接编译后的目标文件编译后的目标文件引入库引入库(DLL(DLL函数的定位信息函数的定位信息)链接器链接器可执行程序可执行程序 主存主存重要定位重要定位信息信息动态链动态链接库接库调用调用DLLD

39、LL中的函数中的函数494.3.5 4.3.5 多级页表多级页表多级页表的概念多级页表的概念 多级页表的具体做法多级页表的具体做法 逻辑地址结构逻辑地址结构逻辑地址到物理地址转换过程逻辑地址到物理地址转换过程50多级页表的概念多级页表的概念系统为每个进程建一张页目录表系统为每个进程建一张页目录表,它的每个表项它的每个表项对应一个页表页对应一个页表页,而页表页的每个表项给出了页而页表页的每个表项给出了页面和页框的对应关系面和页框的对应关系,页目录表是一级页表页目录表是一级页表,页表页表页是二级页表。页是二级页表。逻辑地址结构有三部分组成：页目录、页表页和逻辑地址结构有三部分组成：页目录、页表页和

40、位移。位移。51多级页表地址转换过程多级页表地址转换过程 页框号页框号 页内位移页内位移 页目录位移页目录位移 页表页位移页表页位移 页内位移页内位移B BF F进程一级页表进程一级页表进程二级页表进程二级页表物理地址物理地址逻辑地址逻辑地址页目录表页目录表控制寄存器控制寄存器52解决页表页占用主存空间的问题解决页表页占用主存空间的问题进进程程运运行行涉涉及及页页面面的的页页表表页页应应放放在在主主存存,其其他页表页使用时再调入他页表页使用时再调入,在在页页目目录录表表中中增增加加特特征征位位,指指示示对对应应的的页页表表页是否已调入主存页是否已调入主存,地地址址转转换换机机构构根根据据逻逻辑

41、辑地地址址中中的的dir,dir,去去查查页页目目录录表表对对应应表表项项,如如未未调调入入,应应产产生生一一个个”缺缺页页表表页页”中中断断信信号号，请请求求操操作作系系统统将将页表页调入主存。页表页调入主存。53SUN SPARCSUN SPARC计算机三级分页结构计算机三级分页结构 上下文号上下文号索引索引1(8)1(8)索引索引2(6)2(6)索引索引3(6)3(6)偏移偏移(12)(12)上下文表上下文表第一级第一级第二级第二级第三级第三级4K4K页面页面0 040954095页表页表54多级页表结构的本质多级页表结构的本质多级不连续导致多级索引。多级不连续导致多级索引。以二级页表为

42、例，用户程序的页面不连续以二级页表为例，用户程序的页面不连续存放，要有页面地址索引，该索引是进程存放，要有页面地址索引，该索引是进程页表；进程页表又是不连续存放的多个页页表；进程页表又是不连续存放的多个页表页，故页表页也要页表页地址索引，该表页，故页表页也要页表页地址索引，该索引就是页目录。索引就是页目录。页目录项是页表页的索引，而页表页项是页目录项是页表页的索引，而页表页项是进程程序的页面索引。进程程序的页面索引。554.3.5 4.3.5 反置页表反置页表(1)(1)页框号页框号 位移位移进程标识进程标识 页号页号 位移位移 进程标识进程标识 页号页号 特征位特征位 链指针链指针 序号序号

43、反置页表反置页表物理地址物理地址逻辑地址逻辑地址哈希哈希函数函数哈希表哈希表反置页表及其地址转换反置页表及其地址转换56反置页表反置页表(2)(2)IPTIPT是为主存中的每一个物理块建立一个页是为主存中的每一个物理块建立一个页表并按照块号排序表并按照块号排序,该表每个表项包含正在访问该页框的进程该表每个表项包含正在访问该页框的进程标识、页号及特征位标识、页号及特征位,用来完成主存页框到用来完成主存页框到访问进程的页号、即物理地址到逻辑地址访问进程的页号、即物理地址到逻辑地址的转换。的转换。57反置页表反置页表(3)(3)反置页表地址转换过程如下反置页表地址转换过程如下:逻逻辑辑地地址址给给出

44、出进进程程标标识识和和页页号号,用用它它们们去去比比较较IPT,IPT,若若整整个个反反置置页页表表中中未未能能找找到到匹匹配配的的页页表表项项,说说明明该该页页不不在在主主存存,产产生生请请页页中中断断,请请求求操操作作系系统统调调入入;否否则则，该该表表项项的的序序号号便便是是页页框框号号,块块号号加加上上位移位移,便形成物理地址。便形成物理地址。58分页技术分页技术不会不会产生产生外部碎片外部碎片，但，但会会产生产生内内部碎片部碎片分页的重要特点是用户观点的内存和实际分页的重要特点是用户观点的内存和实际的物理内存的分离的物理内存的分离分页可以共享共同代码分页可以共享共同代码分页内存管理方

45、案小结分页内存管理方案小结594.4 4.4 分段式存储管理分段式存储管理4.4.1 4.4.1 程序的分段结构程序的分段结构4.4.2 4.4.2 分段式存储管理的基本原理分段式存储管理的基本原理4.4.3 4.4.3 段的共享和保护段的共享和保护4.4.4 4.4.4 分段和分页的比较分段和分页的比较604.4.1 4.4.1 程序的分段结构程序的分段结构分段存储管理引入的主要原因分段存储管理引入的主要原因0满足用户（程序员）编程和使用上的要求。满足用户（程序员）编程和使用上的要求。模块化程序设计的分段结构（下页图）模块化程序设计的分段结构（下页图）分页存储管理分页存储管理-一维地址结构一

46、维地址结构分段存储管理分段存储管理-二维地址结构二维地址结构61模块化程序设计的分段结构模块化程序设计的分段结构 子程序段子程序段X X数组段数组段A Acall Xcall X(调用调用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：工作区段工作区段624.4.2 4.4.2 分段式存储管理的基本原理分段式存储管理的基本原理(1)(1)l两维逻辑地址两维逻辑地址l段号：段内地址段号：段内地址l段表段表l段表指出主存中各分

47、段的段号、段起始地址和段表指出主存中各分段的段号、段起始地址和段长度，起到基址段长度，起到基址/限长寄存器的作用。限长寄存器的作用。l段式存储管理的地址转换和存储保护段式存储管理的地址转换和存储保护 63分段式存储管理的基本原理分段式存储管理的基本原理(2)(2)段控制寄存器段控制寄存器 段表始址段表始址 段表长度段表长度 段号段号s s 位移位移d d 段长段长 基址基址 物理地址物理地址越界越界?段表段表64段表：将二维的逻辑地址映射为一维物理地址段表：将二维的逻辑地址映射为一维物理地址段基地址：包含该段在内存中的开始物理地址段基地址：包含该段在内存中的开始物理地址段界限：指定该段的长度段

48、界限：指定该段的长度逻辑地址：段号逻辑地址：段号s s段内偏移段内偏移d d逻辑地址到物理地址的转换逻辑地址到物理地址的转换1)1)段号与段表长度进行比较，若段号超过了段表长度，段号与段表长度进行比较，若段号超过了段表长度，则越界（非法地址），否则转则越界（非法地址），否则转2 2）2)2)根据段表始址和段号计算出该段对应段表项的位置，根据段表始址和段号计算出该段对应段表项的位置，从中读出该段在内存的起始地址，检查段内地址是从中读出该段在内存的起始地址，检查段内地址是否超过该段的段长，若超过则越界（非法地址），否超过该段的段长，若超过则越界（非法地址），否则转否则转3 3）3)3)将该段的起始

49、地址与段内位移相加，从而得到要访将该段的起始地址与段内位移相加，从而得到要访问的物理地址问的物理地址逻辑地址到物理地址转换逻辑地址到物理地址转换65逻辑地址到物理地址转换例逻辑地址到物理地址转换例说明：段表如表说明：段表如表1 1所示，将表所示，将表2 2所示逻辑地址转换为相应所示逻辑地址转换为相应物理地址物理地址答案：见表答案：见表3 3段号段号 内存起始内存起始地址地址段长段长0 02192196006001 12300230014142 290901001003 3132713275805804 4195219529696段段号号段内位段内位移移2 288884 410010017817

50、8非法非法 表表1 表表2 表表390+881009666说明：段表如表说明：段表如表1 1所示，将表所示，将表2 2所示逻辑地址转换为相应所示逻辑地址转换为相应物理地址物理地址答案：见表答案：见表3 3逻辑地址到物理地址转换练习逻辑地址到物理地址转换练习段号段号段内位移段内位移0 04304301 110102 25005003 34004004 41121125 53232段号段号内存起始地址内存起始地址段长段长0 02102105005001 12350235020202 210010090903 3135013505905904 4193819389595 表表1 表表26406402