《第4章存储管理》由会员分享，可在线阅读，更多相关《第4章存储管理（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早期单用户单任务系统早期单用户单任务系统
5、动态重定位动态重定位0地址转换推迟到最后的可能时刻，即进程执行时才完地址转换推迟到最后的可能时刻，即进程执行时才完成；成；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
8、+50004000+10004000+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下限寄存器下限寄存器逻
10、辑地址逻辑地址CPUCPU绝对地址绝对地址操作系统区操作系统区用户分区用户分区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空闲区空闲区4KB4KB10KB10KB46KB46KB52KB52KB128KB
12、128KB操作系统操作系统作业作业1 1空闲区空闲区作业作业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限长寄存器限长寄存器
19、1 1重定位寄存器重定位寄存器2 2限长寄存器限长寄存器2 2 多对重定位寄存器支持主存共享多对重定位寄存器支持主存共享254.2.3 4.2.3 伙伴系统伙伴系统伙伴原理伙伴原理伙伴系统是一种固定分区和可变分区折中的主存管理算法，伙伴系统是一种固定分区和可变分区折中的主存管理算法，基本原理：任何尺寸为基本原理：任何尺寸为2 2i i的空闲块可以被分为两个尺寸为的空闲块可以被分为两个尺寸为2 2i-1i-1的空闲块，这两个空闲块称为伙伴。的空闲块，这两个空闲块称为伙伴。伙伴通过对大块的物理主存划分而获得伙伴通过对大块的物理主存划分而获得0假如从第假如从第0 0个页面开始到第个页面开始到第3 3
20、个页面结束的主存个页面结束的主存0每次都对半划分，那么第一次划分获得大小为每次都对半划分，那么第一次划分获得大小为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 A
21、B 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 10241024272.Linux2.Linux伙伴系统伙伴系统1) 1) 以以pagepage结构为数组元素的结构为数组元素的mem_mapmem_map 数组数组2) 2) 以以free_area_structfree_area_struct结构为数组元素的结构为数组元素的free_areafree_a
22、rea数组数组3) 3) 位图数组位图数组(bitmap) (bitmap) 283.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-cach
23、e-grow() -cache-grow() 与与kmemkmem-cache-reap()-cache-reap()0kmalloc()kfreekmalloc()kfree()()0kmem-getpageskmem-getpages() () 与与kmem-frepageskmem-frepages()()29LinuxLinux基于伙伴的基于伙伴的slabslab分配器分配器(2)(2)slabslab分配器组成分配器组成cachecacheslabslabslabslabslabslabslabslabslabslabslabslabslabslabcachecachecacheca
24、cheslabslabslabslab满满slabslab半满半满slabslab空空slabslab存存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移动算法（假设进程移动算法（假
26、设进程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 KBx KB主存；修改主存分配表的有关项；设主存；修改主存分配表的有关项；设置进程置进
27、程A A的基址寄存器；有申请者等待时予以释放，算的基址寄存器；有申请者等待时予以释放，算法结束。法结束。开销非常大，极少使用开销非常大，极少使用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紧缩
29、（紧缩（compactioncompaction）：）：移动内存内容，以便所有空闲移动内存内容，以便所有空闲空间合并成一整块空间合并成一整块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 反置页表
30、反置页表374.3.1 4.3.1 分页式存储管理分页式存储管理l为什么要引进分页技术为什么要引进分页技术? ?l基本原理基本原理页面：进程逻辑地址空间分成大小相等的区；页面：进程逻辑地址空间分成大小相等的区； 页框（帧）：主存物理地址空间分成大小相等页框（帧）：主存物理地址空间分成大小相等的区，其大小跟页面大小相等；的区，其大小跟页面大小相等；逻辑地址形式：页号页内位移逻辑地址形式：页号页内位移 页表和地址转换（后面图）页表和地址转换（后面图） 基本原理基本原理(1)38基本原理基本原理(2)(2)l作业的页面与分给的页框如何建立联系呢？作业的页面与分给的页框如何建立联系呢？l逻辑地址逻辑地
31、址( (页面页面) )如何变换成物理地址如何变换成物理地址( (页框页框) )呢？呢？l作业的物理地址空间由连续变成分散后，如作业的物理地址空间由连续变成分散后，如何保证程序正确执行呢？何保证程序正确执行呢？使用动态重定位技术，给每个页面设立重定使用动态重定位技术，给每个页面设立重定位寄存器，重定位寄存器的集合便称位寄存器，重定位寄存器的集合便称页表页表。页表是操作系统为每个用户作业建立的，用页表是操作系统为每个用户作业建立的，用来记录程序页面和主存对应页框的对照表。来记录程序页面和主存对应页框的对照表。39页页0 0页页1 1页页2 2页页3 31 14 43 37 70 1 2 3页页0
32、0页页2 2页页1 1页页3 30 1 2 3 4 5 6 7逻辑内存逻辑内存页表页表物理内存物理内存页号页号 帧号帧号帧号帧号物理内存和逻辑内存的分页模型物理内存和逻辑内存的分页模型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
33、 64+0=244/4=10 64+0=2413/4=31 24+1=913/4=31 24+1=941练习：逻辑地址到物理地址的转换练习：逻辑地址到物理地址的转换说明：页大小为说明：页大小为1024B1024B，页表如图所示，页表如图所示，将逻辑地址将逻辑地址10111011、21482148、30003000、40004000、50125012转换为相应物理地址转换为相应物理地址23160 1 2 3页表页表答案：答案：30593059、11241124、19761976、70727072、逻、逻辑地址非法辑地址非法1011/1024=01011 21024+1011=30591011/1
34、024=01011 21024+1011=30592148/1024=2100 11024+100=11242148/1024=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 tr
35、anslation look-aside bufferlook-aside buffer，TLBTLB）：关联的快速内存）：关联的快速内存TLBTLB与页表一起工作（了解工作过程）与页表一起工作（了解工作过程）43采用相联存储器的地址转换采用相联存储器的地址转换假假定定访访问问主主存存时时间间为为100100毫毫微微秒秒，访访问问相相联联存存储储器器时时间间为为2020毫毫微微秒秒，相相联联存存储储器器为为3232个个单单元元时时快快表表命中率可达命中率可达90%90%，按逻辑地址存取的平均时间为：，按逻辑地址存取的平均时间为：（1001002020）90%90%(100+100+20)(1-
36、90%)(100+100+20)(1-90%)130130比比两两次次访访问问主主存存的的时时间间1002+201002+20200200下下降降了了三三成多。成多。444.3.3 4.3.3 分页式存储空间的分配和去配分页式存储空间的分配和去配(1)(1)位示图法位示图法0每位与一帧相对应，用每位与一帧相对应，用0/10/1表示对应块为空闲表示对应块为空闲/ /已占用，用另一专门字记录当前空闲块数。已占用，用另一专门字记录当前空闲块数。链表方法链表方法0每个表项包含：每个表项包含：x进程占用区（进程占用区（P P）还是空闲区（）还是空闲区（H H）x起始地址起始地址x长度长度x指向下一表项的
37、指针指向下一表项的指针45主存分配的位示图和链表方法主存分配的位示图和链表方法464.3.4 4.3.4 分页存储空间的页面共享和保护分页存储空间的页面共享和保护(1)(1)数据共享数据共享0允许不同进程对共享的数据页用不同的页号，允许不同进程对共享的数据页用不同的页号，只要让各自页表中的有关表项指向共享的数据只要让各自页表中的有关表项指向共享的数据页框；页框；程序共享程序共享0指令包含指向其它指令或数据的地址。指令包含指向其它指令或数据的地址。标志位保护方法标志位保护方法0在在页页表表中中增增加加标标志志位位，指指出出此此页页的的信信息息只只读读/ /读写读写/ /只可执行只可执行/ /不可
38、访问等。不可访问等。键保护方法键保护方法47分页存储空间的页面共享和保护分页存储空间的页面共享和保护(2)(2)共享库共享库 0包含共享函数的目标代码块包含共享函数的目标代码块动态链接器动态链接器0负责动态链接。负责动态链接。0动态链接：共享库运行时可加载到任意的主存动态链接：共享库运行时可加载到任意的主存区域，并在主存中和一个程序链接起来。区域，并在主存中和一个程序链接起来。编译和动态链接共享库的过程编译和动态链接共享库的过程48分页存储空间的页面共享和保护分页存储空间的页面共享和保护(3)(3) WindowsWindows动态链接动态链接编译后的目标文件编译后的目标文件引入库引入库(DL
39、L(DLL函数的定位信息函数的定位信息) )链接器链接器可执行程序可执行程序 主存主存重要定位重要定位信息信息动态链动态链接库接库调用调用DLLDLL中的函数中的函数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
42、)上下文表上下文表第一级第一级第二级第二级第三级第三级4K4K页面页面0 040954095页表页表54多级页表结构的本质多级页表结构的本质多级不连续导致多级索引。多级不连续导致多级索引。以二级页表为例，用户程序的页面不连续以二级页表为例，用户程序的页面不连续存放，要有页面地址索引，该索引是进程存放，要有页面地址索引，该索引是进程页表；进程页表又是不连续存放的多个页页表；进程页表又是不连续存放的多个页表页，故页表页也要页表页地址索引，该表页，故页表页也要页表页地址索引，该索引就是页目录。索引就是页目录。页目录项是页表页的索引，而页表页项是页目录项是页表页的索引，而页表页项是进程程序的页面索引。
43、进程程序的页面索引。554.3.5 4.3.5 反置页表反置页表(1)(1) 页框号页框号 位移位移进程标识进程标识 页号页号 位移位移 进程标识进程标识 页号页号 特征位特征位 链指针链指针 序号序号反置页表反置页表物理地址物理地址逻辑地址逻辑地址哈希哈希函数函数哈希表哈希表反置页表及其地址转换反置页表及其地址转换56反置页表反置页表(2)(2)IPTIPT是为主存中的每一个物理块建立一个页是为主存中的每一个物理块建立一个页表并按照块号排序表并按照块号排序, ,该表每个表项包含正在访问该页框的进程该表每个表项包含正在访问该页框的进程标识、页号及特征位标识、页号及特征位, ,用来完成主存页框到
44、用来完成主存页框到访问进程的页号、即物理地址到逻辑地址访问进程的页号、即物理地址到逻辑地址的转换。的转换。57反置页表反置页表(3)(3)反置页表地址转换过程如下反置页表地址转换过程如下: :逻逻辑辑地地址址给给出出进进程程标标识识和和页页号号, ,用用它它们们去去比比较较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 程序的分段结构程序的分段
46、结构分段存储管理引入的主要原因分段存储管理引入的主要原因0满足用户（程序员）编程和使用上的要求。满足用户（程序员）编程和使用上的要求。模块化程序设计的分段结构（下页图）模块化程序设计的分段结构（下页图）分页存储管理分页存储管理-一维地址结构一维地址结构分段存储管理分段存储管理-二维地址结构二维地址结构61模块化程序设计的分段结构模块化程序设计的分段结构 子程序段子程序段X X数组段数组段A Acall Xcall X( (调用调用X X段的入口段的入口E)E)call Ycall Y( (调用调用Y Y段的入口段的入口F)F)load 1,Aload 1,A ( (调用数组段调用数组段AG)A
47、G)主程序段主程序段E E：F F：子程序段子程序段Y YG G：工作区段工作区段624.4.2 4.4.2 分段式存储管理的基本原理分段式存储管理的基本原理(1)(1)l两维逻辑地址两维逻辑地址l段号：段内地址段号：段内地址l段表段表l段表指出主存中各分段的段号、段起始地址和段表指出主存中各分段的段号、段起始地址和段长度，起到基址段长度，起到基址/ /限长寄存器的作用。限长寄存器的作用。l段式存储管理的地址转换和存储保护段式存储管理的地址转换和存储保护 63分段式存储管理的基本原理分段式存储管理的基本原理(2)(2) 段控制寄存器段控制寄存器 段表始址段表始址 段表长度段表长度 段号段号s
48、s 位移位移d d 段长段长 基址基址 物理地址物理地址越界越界? ? 段表段表64段表：将二维的逻辑地址映射为一维物理地址段表：将二维的逻辑地址映射为一维物理地址段基地址：包含该段在内存中的开始物理地址段基地址：包含该段在内存中的开始物理地址段界限：指定该段的长度段界限：指定该段的长度逻辑地址：段号逻辑地址：段号s s段内偏移段内偏移d d逻辑地址到物理地址的转换逻辑地址到物理地址的转换1)1)段号与段表长度进行比较，若段号超过了段表长度，段号与段表长度进行比较，若段号超过了段表长度，则越界（非法地址），否则转则越界（非法地址），否则转2 2）2)2)根据段表始址和段号计算出该段对应段表项的
49、位置，根据段表始址和段号计算出该段对应段表项的位置，从中读出该段在内存的起始地址，检查段内地址是从中读出该段在内存的起始地址，检查段内地址是否超过该段的段长，若超过则越界（非法地址），否超过该段的段长，若超过则越界（非法地址），否则转否则转3 3）3)3)将该段的起始地址与段内位移相加，从而得到要访将该段的起始地址与段内位移相加，从而得到要访问的物理地址问的物理地址逻辑地址到物理地址转换逻辑地址到物理地址转换65逻辑地址到物理地址转换例逻辑地址到物理地址转换例说明：段表如表说明：段表如表1 1所示，将表所示，将表2 2所示逻辑地址转换为相应所示逻辑地址转换为相应物理地址物理地址答案：见表答案：
50、见表3 3段号段号 内存起始内存起始地址地址段长段长0 02192196006001 12300230014142 290901001003 3132713275805804 4195219529696段段号号段内位段内位移移2 288884 4100100178178非法非法 表表1 表表2 表表390+881009666说明：段表如表说明：段表如表1 1所示，将表所示，将表2 2所示逻辑地址转换为相应所示逻辑地址转换为相应物理地址物理地址答案：见表答案：见表3 3逻辑地址到物理地址转换练习逻辑地址到物理地址转换练习段号段号段内位移段内位移0 04304301 110102 25005003
51、 34004004 41121125 53232段号段号内存起始地址内存起始地址段长段长0 02102105005001 12350235020202 210010090903 3135013505905904 4193819389595 表表1 表表264064023602360非法非法17501750非法非法非法非法表表3210+4302350+10500901350+40011295段号段号5不存在不存在674.4.3 4.4.3 段的共享段的共享多对基址多对基址/ /限长寄存器限长寄存器 段的共享，是通过不同作业段表中的项指段的共享，是通过不同作业段表中的项指向同一个段基址来实现。向同
52、一个段基址来实现。几道作业共享的例行程序就可放在一个段几道作业共享的例行程序就可放在一个段中，只要让各道作业的共享部分有相同的中，只要让各道作业的共享部分有相同的基址基址/ /限长值。限长值。对共享段的信息必须进行保护。对共享段的信息必须进行保护。 684.4.4 4.4.4 分段和分页的比较分段和分页的比较(1)(1) 分分段段是是信信息息的的逻逻辑辑单单位位，由由源源程程序序的的逻逻辑辑结构所决定，用户可见，结构所决定，用户可见，段段长长可可根根据据用用户户需需要要来来规规定定，段段起起始始地地址址可从任何主存地址开始。可从任何主存地址开始。分分段段方方式式中中，源源程程序序( (段段号号
53、，段段内内位位移移) )经经连结装配后地址仍保持二维结构。连结装配后地址仍保持二维结构。69分段和分页的比较分段和分页的比较(2)(2) 分分页页是是信信息息的的物物理理单单位位，与与源源程程序序的的逻逻辑辑结构无关，用户不可见，结构无关，用户不可见，页页长长由由系系统统确确定定，页页面面只只能能以以页页大大小小的的整整倍数地址开始。倍数地址开始。分分页页方方式式中中，源源程程序序( (页页号号，页页内内位位移移) )经经连结装配后地址变成了一维结构。连结装配后地址变成了一维结构。704.5 4.5 虚拟存储管理虚拟存储管理4.5.1 4.5.1 虚拟存储管理的概念虚拟存储管理的概念4.5.2
54、 4.5.2 请求分页虚拟存储管理请求分页虚拟存储管理4.5.3 4.5.3 请求分段虚拟存储管理请求分段虚拟存储管理4.5.4 4.5.4 请求段页式虚拟存储管理请求段页式虚拟存储管理714.5.1 4.5.1 虚拟存储管理的概念虚拟存储管理的概念虚拟内存（虚拟内存（virtual memoryvirtual memory）：）：允许进程的执行允许进程的执行不必完全在内存中，程序可以比物理内存大。不必完全在内存中，程序可以比物理内存大。在许多情况下不需要将整个程序放到内存中：在许多情况下不需要将整个程序放到内存中：0处理异常错误条件的代码（几乎不执行）处理异常错误条件的代码（几乎不执行）0数
55、组、链表和表通常分配了比实际所需更多的内存数组、链表和表通常分配了比实际所需更多的内存0程序的某些选项或特点可能很少使用程序的某些选项或特点可能很少使用能够执行只有部分在内存中的程序的好处能够执行只有部分在内存中的程序的好处0程序不再受现有的物理内存空间限制程序不再受现有的物理内存空间限制0更多程序可同时执行，更多程序可同时执行，CPUCPU利用率相应增加利用率相应增加0用户程序会运行的更快用户程序会运行的更快72虚拟存储器虚拟存储器虚拟存储器的定义：虚拟存储器的定义：0在具有层次结构存储器的计算机系统中，在具有层次结构存储器的计算机系统中，采用自动实现部分装入和部分对换功能，采用自动实现部分
56、装入和部分对换功能，为用户提供一个比物理主存容量大得多为用户提供一个比物理主存容量大得多的，可寻址的一种的，可寻址的一种“主存储器主存储器”。 73虚拟存储器的概念图虚拟存储器的概念图 逻辑地址空间逻辑地址空间处理器处理器虚地址虚地址存储存储管理管理部件部件实地址实地址主存主存辅存辅存物理地址空间物理地址空间74程序的局部性原理程序的局部性原理 指程序在执行过程中的一个较短时间内，所指程序在执行过程中的一个较短时间内，所执行的指令地址或操作数地址分别局限于一执行的指令地址或操作数地址分别局限于一定的存储区域中。又可细分时间局部性和空定的存储区域中。又可细分时间局部性和空间局部性。间局部性。时间
57、局部性：最近访问过的程序代码和数据很快时间局部性：最近访问过的程序代码和数据很快又被访问。又被访问。空间局部性：某存储单元被使用之后，其相邻的空间局部性：某存储单元被使用之后，其相邻的存储单元也很快被使用。存储单元也很快被使用。75实现虚拟存储器须解决的问题实现虚拟存储器须解决的问题l 主存辅存统一管理问题主存辅存统一管理问题l 逻辑地址到物理地址的转换问题逻辑地址到物理地址的转换问题l 部分装入和部分对换问题部分装入和部分对换问题76虚拟存储管理实现技术虚拟存储管理实现技术l 请求分页虚拟存储管理请求分页虚拟存储管理l 请求分段虚拟存储管理请求分段虚拟存储管理l 请求段页式虚拟存储管理请求段
58、页式虚拟存储管理774.5.2 4.5.2 请求分页虚拟存储系统请求分页虚拟存储系统1.1.请求分页虚拟存储系统的硬件支撑请求分页虚拟存储系统的硬件支撑(1)(1)主存管理单元主存管理单元MMUMMU完成逻辑地址到物理地址完成逻辑地址到物理地址的转换功能，它接受虚拟地址作为输入，的转换功能，它接受虚拟地址作为输入，物理地址作为输出，直接送到总线上，对物理地址作为输出，直接送到总线上，对主存单元进行寻址。主存单元进行寻址。 78分页式虚拟存储系统的硬件支撑分页式虚拟存储系统的硬件支撑(2)(2) CPUCPUMMUMMU内内存存CPUCPU把逻辑地把逻辑地址送至址送至MMUMMUMMUMMU把物
59、理地址送至主存把物理地址送至主存 MMUMMU的的位位置置、功功能能和和1616个个4KB4KB页页面情况下面情况下MMUMMU的内部操作的内部操作CPUCPU送入的送入的逻辑地址逻辑地址(8196)(8196)0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 00 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 01 1 0 0 0 0 0 0 0 0 0 0 1 0 0MMUMMU送出的物理地址送出的物理地址0 010 10 010 11 001 11 001 12 110 12 110 13 000 13 00
60、0 14 100 14 100 15 011 15 011 16 000 06 000 07 000 07 000 08 101 18 101 19 000 09 000 0页号页号 页框号页框号 在主存否在主存否79MMUMMU主要功能主要功能(1)(1)管理硬件页表基址寄存器。管理硬件页表基址寄存器。(2)(2)分解逻辑地址。分解逻辑地址。(3)(3)管理快管理快表表TLBTLB。(4)(4)访问页表。访问页表。(5)(5)发出缺页中断或越界中断，并将控制权交给内发出缺页中断或越界中断，并将控制权交给内核存储管理处理。核存储管理处理。(6)(6)设置和检查页表中各个特征位。设置和检查页表中
61、各个特征位。802.2.请求分页虚拟存储系统的基本原理请求分页虚拟存储系统的基本原理分页式虚存不把作业信息分页式虚存不把作业信息( (程序和数据程序和数据) )全部装入全部装入主存，仅装入立即使用的页面，在执行过程中访主存，仅装入立即使用的页面，在执行过程中访问到不在主存的页面时，产生缺页中断，再从磁问到不在主存的页面时，产生缺页中断，再从磁盘动态地装入盘动态地装入 。 怎样才能发现页面不在主存中呢怎样才能发现页面不在主存中呢? ?怎样处理这种怎样处理这种情况呢情况呢? ?0采用的办法是：扩充页表的内容采用的办法是：扩充页表的内容, ,增加驻留标志位和页增加驻留标志位和页面辅存的地址等信息面辅
62、存的地址等信息。81页式虚拟存储管理页表扩展页式虚拟存储管理页表扩展其它标志：其它标志：访问权限位访问权限位 修改位（修改位（ModifiedModified）引用位（引用位（RenferencedRenferenced）页号页号 驻留标志驻留标志 页框号页框号 辅存地址辅存地址 其它标志其它标志82请求分页虚存地址转换过程请求分页虚存地址转换过程(1)(1) 逻辑空间地址逻辑空间地址主存主存( (用户区用户区) )CPUCPU逻辑地址逻辑地址快表快表主存主存( (系统区系统区) )运行进程页运行进程页表表辅存辅存缺页中断处理缺页中断处理分解地分解地址址访访问问MMUMMU查快表查快表命中命中
63、不命中不命中页表命中页表命中发缺页中断发缺页中断调页调页装入、装入、改表改表查页表查页表运行进程页表基址运行进程页表基址装入快表装入快表运行进运行进程映象程映象进程切换时装入进程切换时装入物理地址物理地址页框页框 页内地址页内地址页号页号 页内地址页内地址83请求分页虚存地址转换过程请求分页虚存地址转换过程(2)(2)查快表查快表有登记有登记无登记无登记查页表查页表登记入快表登记入快表发缺页中断发缺页中断在主存在主存在辅存在辅存形成绝对地址形成绝对地址继续执行指令继续执行指令重新执行重新执行被中断指令被中断指令恢复现场恢复现场调整页表和调整页表和主存分配表主存分配表装入所需页面装入所需页面主存
64、有空闲块主存有空闲块保护现场保护现场有有选择调出页面选择调出页面该页是否修改该页是否修改未修改未修改已修改已修改把该页写回把该页写回辅存相应位置辅存相应位置操作系统操作系统硬件硬件逻辑地址逻辑地址无无84请求页式虚拟存储系统优缺点请求页式虚拟存储系统优缺点l优优点点：作作业业的的程程序序和和数数据据可可按按页页分分散散存存放放在在主主存存中中，减减少少移移动动开开销销，有有效效解解决决了了碎碎片片问问题题; ;既既有有利利于于改改进进主主存存利利用用率率，又又有有利利于多道程序运行。于多道程序运行。l缺缺点点：要要有有硬硬件件支支持持，要要进进行行缺缺页页中中断断处处理，机器成本增加，系统开销
65、加大。理，机器成本增加，系统开销加大。853.3.页面装入策略和页面清除策略页面装入策略和页面清除策略l页面装入主存页面装入主存, ,有两种策略：有两种策略：l请页式调度：仅调入所需页面请页式调度：仅调入所需页面l预调式调度：使用前预先调入若干页预调式调度：使用前预先调入若干页l何时把一个修改过的页面写回辅存储器，何时把一个修改过的页面写回辅存储器，有两种策略：有两种策略：l请页式清除：仅当一页被选中进行替换且被请页式清除：仅当一页被选中进行替换且被修改过，才写回磁盘。修改过，才写回磁盘。l预清除：成批进行，所有预清除：成批进行，所有 被更改过的页面，被更改过的页面，在需要替换前把它们都写回磁
66、盘。在需要替换前把它们都写回磁盘。864.4.页面分配策略页面分配策略系统为进程分配主存系统为进程分配主存, ,需考虑因素需考虑因素: :分分给给进进程程的的空空间间越越小小, ,同同一一时时间间处处于于主主存存的的进进程程就就越越多多，至至少少有有一一个个进进程程处处于于就就绪绪态态的的可可能能性性就就越大越大如如果果进进程程只只有有小小部部分分在在主主存存里里, ,即即使使局局部部性性很很好好, ,缺页中断率还会相当缺页中断率还会相当因因程程序序的的局局部部性性原原理理，分分给给进进程程的的主主存存超超过过一一定定限限度度后后，再再增增加加主主存存空空间间, ,不不会会明明显显降降低低进进
67、程程的的缺页中断率缺页中断率。87页面分配策略：固定分配页面分配策略：固定分配进程保持页框数固定不变进程保持页框数固定不变, ,称固定分配称固定分配; ;进程创建时进程创建时, ,根据进程类型和程序员的要求根据进程类型和程序员的要求决定页框数决定页框数, ,只要有一个缺页中断产生只要有一个缺页中断产生, ,进进程就会有一页被替换。程就会有一页被替换。88页面分配策略：可变分配页面分配策略：可变分配进程分得的页框数可变进程分得的页框数可变, , 称可变分配称可变分配; ;进程执行的某阶段缺页率较高进程执行的某阶段缺页率较高, ,说明目前局说明目前局部性较差，系统可多分些页框以降低缺页部性较差，系
68、统可多分些页框以降低缺页率，反之说明进程目前的局部性较好率，反之说明进程目前的局部性较好, ,可减可减少分给进程的页框数少分给进程的页框数89页面替换策略页面替换策略：局部替换和全局替换局部替换和全局替换如果页面替换算法的作用范围是整个系统，如果页面替换算法的作用范围是整个系统，称全局页面替换算法称全局页面替换算法, ,它可以在运行进程间它可以在运行进程间动态地分配页框。动态地分配页框。如果页面替换算法的作用范围局限于本进如果页面替换算法的作用范围局限于本进程，称为局部页面替换算法程，称为局部页面替换算法, ,它实际上需要它实际上需要为每个进程分配固定的页框。为每个进程分配固定的页框。 90固
69、定分配和局部替换策略配合使用固定分配和局部替换策略配合使用(1)(1)l 进进程程分分得得的的页页框框数数不不变变，发发生生缺缺页页中中断断，只只能能从从进进程程的的页页面面中中选选页页替替换换，保保证证进进程程的页框总数不变。的页框总数不变。l策策略略难难点点：应应给给每每个个进进程程分分配配多多少少页页框框? ?给给少少了了, ,缺缺页页中中断断率率高高; ;给给多多了了, ,使使主主存存中中能能同同时时执执行行的的进进程程数数减减少少，进进而而造造成成处处理理器器和和其它设备空闲。其它设备空闲。91固定分配和局部替换策略配合使用固定分配和局部替换策略配合使用(2)(2)采采用用固固定定分
70、分配配算算法法，系系统统把把页页框框分分配配给给进进程，采用：程，采用：平均分配平均分配按比例分配按比例分配优先权分配优先权分配92可变分配和全局替换策略配合使用可变分配和全局替换策略配合使用l先先每每个个进进程程分分配配一一定定数数目目页页框框, ,osos保保留留若若干干空空闲闲页页框框, ,进进程程发发生生缺缺页页中中断断时时，从从系系统统空空闲闲页页框框中中选选一一个个给给进进程程, ,这这样样产产生生缺缺页页中中断断进进程程的的主主存存空空间会逐渐增大间会逐渐增大, ,有助于减少系统的缺页中断次数。有助于减少系统的缺页中断次数。l系系统统拥拥有有的的空空闲闲页页框框耗耗尽尽时时 ，会
71、会从从主主存存中中选选择择一一页页淘淘汰汰，该该页页可可以以是是主主存存中中任任一一进进程程的的页页面面，这这样样又又会会使使那那个个进进程程的的页页框框数数减减少少，缺缺页页中中断断率率上升。上升。93可变分配和局部替换配合使用可变分配和局部替换配合使用其实现要点如下其实现要点如下: :(1)(1)新新进进程程装装入入主主存存时时，根根据据应应用用类类型型、程程序序要要求求，分分配配给给一一定定数数目目页页框框, ,可可用用请请页页式式或或预预调调式式完完成成这个分配。这个分配。(2)(2)产产生生缺缺页页中中断断时时, ,从从该该进进程程驻驻留留集集中中选选一一个个页页面面替换。替换。(3
72、)(3)不不时时重重新新评评价价进进程程的的分分配配，增增加加或或减减少少分分配配给给进程的页框以改善系统性能。进程的页框以改善系统性能。945.5.缺页中断率缺页中断率l页面替换页面替换l当主存空间已满又必须装入新页时，选择主存当主存空间已满又必须装入新页时，选择主存中某页淘汰。中某页淘汰。l页面淘汰算法页面淘汰算法l选择哪页被淘汰的算法。选择哪页被淘汰的算法。l“抖动抖动”(Thrashing)(Thrashing)现象现象l刚刚被被淘淘汰汰的的页页面面立立即即又又要要调调用用，调调入入不不久久又又被被淘淘汰汰，淘淘汰汰不不久久再再被被调调入入如如此此反反复复，整整个个系系统频繁调页，使得
73、几乎无时间进行计算任务。统频繁调页，使得几乎无时间进行计算任务。95影响缺页中断率的因素影响缺页中断率的因素(1) 假假定定作作业业p p共共计计n n页页，系系统统分分配配给给它它的的主主存存块块只只有有m m块块（mnmn）。如如果果作作业业p p在在运运行行中中成成功功的的访访问问次次数数为为S S， 不不成成功功的的访访问问次数次数为为F F，则总的访问次数为：则总的访问次数为：A = S + FA = S + F 又定义：又定义：f = F / Af = F / A 称称f f为缺页中断率。为缺页中断率。96影响缺页中断率的因素影响缺页中断率的因素(2) 影响缺页中断率影响缺页中断率
74、f f的因素有：的因素有：(1)(1)主存页框数。主存页框数。(2)(2)页面大小。页面大小。(3)(3)页面替换算法。页面替换算法。(4)(4)程序特性。程序特性。976.6.全局页面替换策略全局页面替换策略1) 1) 最佳页面替换算法最佳页面替换算法OPT OPT 2) 2) 先进先出页面替换算法先进先出页面替换算法FIFO FIFO 3) 3) 最近最少用页面替换算法最近最少用页面替换算法LRU LRU 4) 4) 第二次机会页面替换算法第二次机会页面替换算法SCR SCR 5) 5) 时钟页面替换算法时钟页面替换算法ClockClock注：所有算法例子中采用请页时调度，即最注：所有算法
75、例子中采用请页时调度，即最初假设主存中没有页面。初假设主存中没有页面。 981)1)最佳替换算法最佳替换算法调调入入一一页页而而必必须须淘淘汰汰一一个个旧旧页页时时，所所淘淘汰汰的的页页应应该该是是以以后后不不再再访访问问的的页页或或距距现现在在最最长时间后再访问的页。长时间后再访问的页。OPTOPT算算法法（OptimalOptimal） ，可可用用来来作作为为衡衡量量各各种具体算法的标准种具体算法的标准。99OPTOPT例例（可用帧数量（可用帧数量3 3）引用串如下：）引用串如下：07 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 7 0 1 2 0 3 0 4 2 3 0
76、3 2 1 2 0 1 7 0 11 7 0 1107107R107102102102R102302302R302342342R342302R302102R102F107F07F7置换帧3帧2帧1引用串10710212303240302107缺页率缺页率 p=9/20=45%p=9/20=45%1002)2)先进先出页面替换算法先进先出页面替换算法基于程序总是按线性顺序来访问物理空间基于程序总是按线性顺序来访问物理空间这一假设。这一假设。算法总是淘汰最先调入主存的那一页，或算法总是淘汰最先调入主存的那一页，或者说在主存中驻留时间最长的那一页（常者说在主存中驻留时间最长的那一页（常驻的除外）。驻
77、的除外）。实现技术实现技术 (1)(1)设置具有设置具有m m个元素的页号表，控制换页个元素的页号表，控制换页 (2)(2)引入指针链成队列引入指针链成队列101FIFOFIFO例例容易理解和实现，性能并不总是很好容易理解和实现，性能并不总是很好例（可用帧数量例（可用帧数量3 3）引用串如下：）引用串如下：07 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 11 7 0 1R107R207R217210210R210R310320320R320R324R024R034R032R132102R102F107
78、F07F7置换帧 3帧 2帧 110710212303240302107引用串缺页率缺页率 p=15/20=75%p=15/20=75%102 BeladyBelady异常：页错误率随着所分配的帧数增加而增加的现异常：页错误率随着所分配的帧数增加而增加的现象，例：象，例：123412512345帧1111444555555帧222211111333帧33332222244缺页:FFFRRRRRR123412512345帧1111111555544帧222222211115帧33333332222帧4444444333缺页:FFFFRRRRRR可用帧数可用帧数3 3，9 9次缺页次缺页可用帧数可
79、用帧数4 4， 1010次缺次缺页页1033)3)最近最少用页面替换算法最近最少用页面替换算法算算法法淘淘汰汰的的页页面面是是在在最最近近一一段段时时间间里里较较久久未被访问的那页。未被访问的那页。根根据据程程序序局局部部性性原原理理，那那些些刚刚被被使使用用过过的的页页面面，可可能能马马上上还还要要被被使使用用，而而在在较较长长时时间间里里未未被被使使用用的的页页面面，可可能能不不会会马马上上使使用用到。到。104LRULRU例例思想：置换过去最长时间没有使用的页思想：置换过去最长时间没有使用的页例（可用帧数量例（可用帧数量3 3）引用串如下：）引用串如下：07 0 1 2 0 3 0 4
80、2 3 0 3 2 1 2 0 1 7 0 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 1701701R701201R201231R231230230R230R234R204R304302R302102R102F107F07F7缺页率缺页率 p=12/20=60%p=12/20=60%置换帧3帧2帧1引用串10710212303240302107105LRULRU算法实现：页面淘汰队列算法实现：页面淘汰队列队队列列中中存存放放当当前前在在主主存存中中的的页页号号，每每当当访访问问一一页页时时就就调调整整一一次次，使使队队列列尾尾总总指指向向最最近访问的页，队
81、列头就是最近最少用的页。近访问的页，队列头就是最近最少用的页。发发生生缺缺页页中中断断时时总总淘淘汰汰队队列列头头所所指指示示的的页页；执执行行一一次次页页面面访访问问后后，需需要要从从队队列列中中把把该该页调整到队列尾。页调整到队列尾。106LRULRU算法实现：标志位算法实现：标志位法法每页设置一个引用标志每页设置一个引用标志位位R R，访问某页时，访问某页时，由硬件将页标志位由硬件将页标志位R R置置1 1，隔一定时间，隔一定时间t t将所将所有页的标志有页的标志R R均清均清0 0。发生缺页中断时，从标志发生缺页中断时，从标志位位R R为为0 0的页中挑的页中挑选一页淘汰。挑选到要淘汰
82、的页后，也将选一页淘汰。挑选到要淘汰的页后，也将所有页的标志所有页的标志位位R R清清0 0。 107LRULRU算法实现：多位计数器算法实现：多位计数器法法每个页面设置一个多位计数器，又叫最不每个页面设置一个多位计数器，又叫最不常用页面替换算法常用页面替换算法LFULFU。每当访问一页时，每当访问一页时，就使它对应的计数器加。就使它对应的计数器加。当发生缺页中断时，可选择计数值最小的当发生缺页中断时，可选择计数值最小的对应页面淘汰，并将所有计数器全部清。对应页面淘汰，并将所有计数器全部清。 108LRULRU算法实现：多位计时器算法实现：多位计时器法法为每个页面设置一个多位计时器，每当页为每
83、个页面设置一个多位计时器，每当页面被访问时，系统的绝对时间记入计时器。面被访问时，系统的绝对时间记入计时器。比较各页面的计时器的值，选最小值的未比较各页面的计时器的值，选最小值的未使用的页面淘汰，因为，它是最使用的页面淘汰，因为，它是最“老老”的的未使用的页面。未使用的页面。1094)4)第二次机会页面替换算法第二次机会页面替换算法l改改进进FIFOFIFO算算法法, ,把把FIFOFIFO与与页页表表中中的的”引引用用位位”结结合起来使用；合起来使用；l检检查查FIFOFIFO中中的的队队首首页页面面( (最最早早进进入入主主存存的的页页面面),),如如果果它它的的”引引用用位位”是是0,0
84、,这这个个页页面面既既老老又又没没有有用用，选择该页面淘汰选择该页面淘汰; ; l如如果果”引引用用位位”是是1,1,说说明明它它进进入入主主存存较较早早，但但最最近近仍仍在在使使用用。把把它它的的”引引用用位位”清清0,0,并并把把这这个个页页面移到队尾，把它看作是一个新调入的页。面移到队尾，把它看作是一个新调入的页。l算算法法含含义义：最最先先进进入入主主存存的的页页面面，如如果果最最近近还还在在被被使使用用的的话话, ,仍仍然然有有机机会会作作为为像像一一个个新新调调入入页页面面一样留在主存中。一样留在主存中。1105 5）时钟页面替换算法）时钟页面替换算法算法实现要点：算法实现要点：l
85、一个页面首次装入主存，其一个页面首次装入主存，其“引用位引用位”置置0 0 。l主存中的任何页面被访问时主存中的任何页面被访问时, “, “引用位引用位”置置1 1。l淘淘汰汰页页面面时时, ,从从指指针针当当前前指指向向的的页页面面开开始始扫扫描描循循环环队队列列，把把迁迁到到的的“引引用用位位”是是1 1的的页页面面的的“引引用用位位”清清0,0,跳跳过过这这个个页页面面; ; 把把所所迁迁到到的的“引引用用位位”是是0 0的页面淘汰掉的页面淘汰掉, ,指针推进一步。指针推进一步。l扫扫描描循循环环队队列列时时，如如果果迁迁到到的的所所有有页页面面的的“引引用用位位”为为1 1，指指针针就
86、就会会绕绕整整个个循循环环队队列列一一圈圈，把把碰碰到到的的所所有有页页面面的的“引引用用位位”清清0;0;指指针针停停在在起起始始位位置置，并淘汰掉这一页并淘汰掉这一页, ,然后，指针推进一步。然后，指针推进一步。111时钟页面替换改进算法时钟页面替换改进算法(1)(1)把把”引引用用位位”和和”修修改改位位”结结合合起起来来使使用用，共共组组合成四种情况：合成四种情况：(1)(1)最近没有被引用最近没有被引用, ,没有被修改没有被修改(r=0,m=0)(r=0,m=0)(2)(2)最近被引用最近被引用, ,没有被修改没有被修改(r=1,m=0)(r=1,m=0)(3)(3)最近没有被引用最
87、近没有被引用, ,但被修改但被修改(r=0,m=1)(r=0,m=1)(4)(4)最近被引用过最近被引用过, ,也被修改也被修改过过(r=1,m=1)(r=1,m=1)112时钟页面替换改进算法时钟页面替换改进算法(2)(2)步步1 1：选选择择最最佳佳淘淘汰汰页页面面，从从指指针针当当前前位位置置开开始始, ,扫扫描描循循环环队队列列。扫扫描描过过程程中中不不改改变变”引引用用位位”，把迂到的第一把迂到的第一个个r=0,m=0r=0,m=0的页面作为淘汰页面。的页面作为淘汰页面。步步2 2：如如果果步步1 1失失败败，再再次次从从原原位位置置开开始始，查查找找r=0r=0且且m=1m=1的的
88、页页面面，把把把把迂迂到到的的第第一一个个这这样样的的页页面面作作为为淘淘汰汰页页面面，而而在在扫扫描描过过程程中中把把指指针针所所扫扫过过的的页面的页面的”引用引用位位”r r置置0 0。步步3 3：如如果果步步2 2失失败败，指指针针再再次次回回到到了了起起始始位位置置，由由于于此此时时所所有有页页面面的的”引引用用位位”r r均均己己为为0 0，再再转转向向步步1 1操操作作，必必要要时时再再做做步步2 2操操作作，这这次次一一定定可可以以挑出一个可淘汰的页面。挑出一个可淘汰的页面。113页置换算法练习页置换算法练习1.1.已知页面走向为已知页面走向为1 1、2 2、1 1、3 3、1
89、1、2 2、4 4、2 2、1 1、3 3、4 4，且开始执行时内存中没有页面。若只给该，且开始执行时内存中没有页面。若只给该作业分配作业分配2 2个物理块。个物理块。1)1)当采用当采用FIFOFIFO、OPTOPT、LRULRU页置换算法时缺页率为多页置换算法时缺页率为多少？少？2)2)假定现有一种置换算法，该算法淘汰页面的策略假定现有一种置换算法，该算法淘汰页面的策略为当需要淘汰页面时，就把刚使用过的页面作为为当需要淘汰页面时，就把刚使用过的页面作为淘汰对象，试问就相同的页面走向，其缺页率又淘汰对象，试问就相同的页面走向，其缺页率又为多少？为多少？3)3)假如分配假如分配3 3个物理块呢
90、？个物理块呢？1141133221142211443311114442322131111411423222331131113422242221 2 1 3 1 2 4 2 1 3 4FIFO 9/11=81.8%OPT 7/11=63.6%LRU 8/11=72.7%NEW 8/11=72.7% 2 2个物理块个物理块1151114422213331111322223441111112222434331111112242233341 2 1 3 1 2 4 2 1 3 4 3 3个物理块个物理块FIFO 5/11=45.5%OPT 5/11=45.5%LRU 6/11=54.5%NEW 6/1
91、1=54.5%1167.7.局部页面替换算法局部页面替换算法1) 1) 局部最佳页面替换算法局部最佳页面替换算法 2) 2) 工作集模型和工作集置换算法工作集模型和工作集置换算法 3) 3) 模拟工作集替换算法模拟工作集替换算法4) 4) 缺页频率替换算法缺页频率替换算法1171) 1) 局部最佳页面替换算法局部最佳页面替换算法实现思想：实现思想： 进程在时刻进程在时刻t t访问某页面，如果该页面不在访问某页面，如果该页面不在主存中，导致一次缺页，把该页面装入一主存中，导致一次缺页，把该页面装入一个空闲页框。不论发生缺页与否，算法在个空闲页框。不论发生缺页与否，算法在每一步要考虑引用串，如果该
92、页面在时间每一步要考虑引用串，如果该页面在时间间隔间隔( (t,t+t,t+) )内未被再次引用，那么就移内未被再次引用，那么就移出页面；否则，该页被保留在进程的驻留出页面；否则，该页被保留在进程的驻留集中，直到再次被引用。集中，直到再次被引用。 118局部最佳页面替换算法例局部最佳页面替换算法例时刻时刻t t0 01 12 23 34 45 56 67 78 89 91010引用串引用串P4P4P3P3P3P3P4P4P2P2P3P3P5P5P3P3P5P5P1P1P4P4P1P1- - - - - - - - - - -P2P2- - - - - - - - - - -P3P3- - -
93、- -P4P4- - - - - - -P5P5- - - - - - - - -InInt tP3P3P2P2P5P5P1P1P4P4OutOutt tP4P4P2P2P3P3P5P5P1P11192)2)工作集模型和工作集置换算法工作集模型和工作集置换算法 进程工作集指进程工作集指“在某一段时间间隔内进程在某一段时间间隔内进程运行所需访问的页面集合运行所需访问的页面集合”。实现思想：实现思想： 工作集模型用来对局部最佳页面替换算法工作集模型用来对局部最佳页面替换算法进行模拟实现，不向前查看页面引用串，进行模拟实现，不向前查看页面引用串，而是基于程序局部性原理向后看，在任何而是基于程序局部性
94、原理向后看，在任何给定时刻，一个进程不久的将来所需主存给定时刻，一个进程不久的将来所需主存页框数，可通过考查其过去最近的时间内页框数，可通过考查其过去最近的时间内的主存需求做出估计。的主存需求做出估计。120工作集替换示例工作集替换示例时刻时刻t t0 01 12 23 34 45 56 67 78 89 91010引用串引用串P4P4P3P3P3P3P4P4P2P2P3P3P5P5P3P3P5P5P1P1P4P4P1P1- - - - - -P2P2- - - - - - - -P3P3- -P4P4- - - -P5P5- - - - -InInt tP3P3P2P2P5P5P1P1P4P
95、4OutOutt tP5P5P1P1P4P4P2P21213) 3) 模拟工作集替换算法模拟工作集替换算法老化老化(Aging)(Aging)算法算法 例如，时间间隔例如，时间间隔T T定为定为10001000次存储器引用，次存储器引用，页面页面P P在时刻在时刻t+0t+0时寄存器为时寄存器为“1000”1000”，在时，在时刻刻t+1000t+1000时寄存器为时寄存器为“0100”0100”，在时刻，在时刻t+2000t+2000时寄存器为时寄存器为“0010”0010”，在时刻，在时刻t+3000t+3000时寄存器为时寄存器为“0001”0001”，在时刻，在时刻t+4000t+40
96、00时寄存时寄存器为器为“0000”0000”，此时，页面，此时，页面p p被移出工作集，被移出工作集，时间戳算法时间戳算法 若若t_offt_off t_maxt_max，把页面从工作集中移出，把页面从工作集中移出 1224)4)缺页频率替换算法缺页频率替换算法缺页频率替换算法根据连续的缺页之间的缺页频率替换算法根据连续的缺页之间的时间间隔来对缺页频率进行测量，每次缺时间间隔来对缺页频率进行测量，每次缺页时，利用测量时间调整进程工作集尺寸。页时，利用测量时间调整进程工作集尺寸。规则：如果本次缺页与前次缺页之间的时规则：如果本次缺页与前次缺页之间的时间超过临界值间超过临界值，那么，所有在这个时
97、间，那么，所有在这个时间间隔内没有引用的页面都被移出工作集。间隔内没有引用的页面都被移出工作集。123PFFPFF替换示例替换示例时刻时刻t t0 01 12 23 34 45 56 67 78 89 91010引用串引用串P4P4P3P3P3P3P4P4P2P2P3P3P5P5P3P3P5P5P1P1P4P4P1P1- - - - - -P2P2- - - - - - -P3P3- -P4P4- -P5P5- - -InInt tP3P3P2P2P5P5P1P1P4P4OutOutt tP1 P1 P5P5P2 P2 P4P41248.8.请求分页虚拟存储管理的几个设计问题请求分页虚拟存储管
98、理的几个设计问题1)1)页面大小页面大小考虑页表大小考虑页表大小大页大页内存利用内存利用小页小页（减少碎片）（减少碎片）页读写所需时间页读写所需时间大页大页精度精度小页小页降低页错误数量降低页错误数量大页大页分析：没有最佳答案，趋向于分析：没有最佳答案，趋向于大页大页 1252)2)页面交换区页面交换区替替换换算算法法要要挑挑选选页页面面淘淘汰汰出出主主存存，但但被被淘淘汰汰出出去去的的页页面面可可能能很很快快使使用用，又又要要被被重重新新装装入入主主存存。操操作作系系统统必必须须保保存存被被淘淘汰汰的的页页面面, ,例例如如UNIX/LinuxUNIX/Linux使使用用交交换换区区临临时时
99、保保存存页页面面，系系统统初初始始化化时时, ,保保留留一一定定盘盘空空间间作作交交换换区。区。1263)3)写时复制写时复制(1)(1)写写时时复复制制(copy-on-write)(copy-on-write)是是存存储储管管理理节节省省物物理理主主存存( (页页框框) )的的一一种种页页面面级级优优化化技技术术, ,已已被被UNIXUNIX和和WindowsWindows等等采采用用，能能减减少少主主存存页页面面内内容容的的复复制制操操作作, ,减减少少相相同同内内容容页页面面在在主主存存的副本数目。的副本数目。127写时复制写时复制(2)(2) 原始数据原始数据原始数据原始数据原始数据
100、原始数据进程地址空间进程地址空间物理地址空间物理地址空间原始数据原始数据原始数据原始数据原始数据原始数据进程地址空间进程地址空间物理地址空间物理地址空间原始数据原始数据原始数据原始数据原始数据原始数据进程地址空间进程地址空间原始数据原始数据原始数据原始数据原始数据原始数据进程地址空间进程地址空间页面页面2 2副本副本 页面页面1 1页面页面2 2页面页面3 3页面页面1 1页面页面2 2页面页面3 31284.5.3 4.5.3 请求分段虚拟存储系统请求分段虚拟存储系统分段式虚拟存储系统把作业的所有分段的分段式虚拟存储系统把作业的所有分段的副本都存放在辅助存储器中，当作业被调副本都存放在辅助存
101、储器中，当作业被调度投入运行时，首先把当前需要的一段或度投入运行时，首先把当前需要的一段或几段装入主存，在执行过程中访问到不在几段装入主存，在执行过程中访问到不在主存的段时再把它们装入。主存的段时再把它们装入。 129段式虚拟存储管理的段表扩展段式虚拟存储管理的段表扩展 段表中增加供管理使用的一些表项：段表中增加供管理使用的一些表项：0特征位特征位x 00(00(不在主存不在主存) )x 01( 01(在主存在主存) )x 11( 11(共享段共享段) )；0存取权限存取权限x 00(00(可执行可执行) )x 01( 01(可读可读) )x 11( 11(可写可写) )130段表中增加供管理
102、使用的一些表项：段表中增加供管理使用的一些表项：0扩充位扩充位x 0(0(固定长固定长) )x 1( 1(可扩充可扩充) )；0标志位标志位x 00(00(未修改未修改) )x 01( 01(已修改已修改) )x 11( 11(不可移动不可移动) )；131 S S段在主存段在主存否否是是BSBS段长度段长度发越界中断发越界中断是是否否形成绝对地址形成绝对地址继续执行指令继续执行指令操作系统操作系统硬件硬件符合存取权限符合存取权限发保护中断发保护中断是是否否发缺段中断发缺段中断移动或调移动或调出分段出分段S S段末端相邻空段末端相邻空闲区长度满足闲区长度满足要求要求地址错地址错S S段可扩充段
103、可扩充是是装入装入S S段段重新启动指令重新启动指令调整调整S S段段表及主段段表及主存分配表存分配表否否非法存取非法存取否否主存中有满足主存中有满足S S段段长度的连续空闲区长度的连续空闲区是是否否是是移动或调移动或调出分段出分段请请求求分分段段虚虚存存管管理理的的地地址址转转换换 132请求分段虚拟存储管理实现分段的共享和保护请求分段虚拟存储管理实现分段的共享和保护 段共享表段共享表 段的共享段的共享段的保护段的保护 1334.5.4 4.5.4 请求段页式虚拟存储管理请求段页式虚拟存储管理段式存储是基于用户程序结构的存储管理技术，段式存储是基于用户程序结构的存储管理技术，有利于模块化程序
104、设计，便于段的扩充、动态链有利于模块化程序设计，便于段的扩充、动态链接、共享和保护接、共享和保护, ,但会生成段内碎片浪费存储空但会生成段内碎片浪费存储空间间页式存储是基于系统存储器结构的存储管理技术页式存储是基于系统存储器结构的存储管理技术, , 存储利用率高存储利用率高, ,便于系统管理，但不易实现存便于系统管理，但不易实现存储共享、保护和动态扩充储共享、保护和动态扩充把两者结合起来就是段页式存储管理把两者结合起来就是段页式存储管理 1341.1.虚虚地地址址以以程程序序的的逻逻辑辑结结构构划划分分成成段段( (段段页页式式存存储储管理的段式特征管理的段式特征) )2.2.实实地地址址划划
105、分分成成位位置置固固定定、大大小小相相等等的的页页框框( (段段页页式存储管理的页式特征式存储管理的页式特征) )3.3.将将每每一一段段的的线线性性地地址址空空间间划划分分成成与与页页框框大大小小相相等等的页面，于是形成了段页式存储管理的特征。的页面，于是形成了段页式存储管理的特征。4.4.逻辑地址形式为：逻辑地址形式为：请求段页式存储管理的基本原理请求段页式存储管理的基本原理段号段号(s) (s) 段内页号段内页号 (p) (p) 页内位移页内位移(d)(d)135请求段页式存储管理的数据结构请求段页式存储管理的数据结构 段页式存储管理的数据结构包括：段页式存储管理的数据结构包括：作作业业
106、表表：登登记记进进入入系系统统中中的的所所有有作作业业及及该该作业段表的起始地址，作业段表的起始地址，段段表表：至至少少包包含含这这个个段段是是否否在在主主存存，以以及及该段页表的起始地址该段页表的起始地址, ,页页表表：包包含含该该页页是是否否在在主主存存( (中中断断位位) )、对对应主存块号。应主存块号。136请求段页式存储管理的动态地址转换请求段页式存储管理的动态地址转换(1)(1)从从逻逻辑辑地地址址出出发发，先先以以段段号号s s和和页页号号p p作作索索引引去去查查快快表表, ,如如果果找找到到, ,那那么么立立即即获获得得页页p p的的页页框框号号p,p,并并与与位位移移d d
107、一一起起拼拼装装得得到到访访问问主主存存的的实实地地址址, ,从从而而完成了地址转换。完成了地址转换。若若查查快快表表失失败败, ,就就要要通通过过段段表表和和页页表表作作地地址址转转换换了了，用用段段号号s s作作索索引引, ,找找到到相相应应表表目目, ,由由此此得得到到s s段段的的页页表表起起址址s,s,再再以以p p作作索索引引得得到到s s段段p p页页对对应应的的表表目目, ,得得到到页页框框号号p;p;这这时时一一方方面面把把s s段段p p页页和和页页框框号号pp置置换换进进快快表表，另另一一方方面面用用pp和和d d生生成成主主存实地址存实地址, ,从而完成地址转换。从而完
108、成地址转换。137请求段页式存储管理的动态地址转换请求段页式存储管理的动态地址转换(2)(2)如查段表时，发现如查段表时，发现s s段不在主存，产生段不在主存，产生“缺段中缺段中断断”，引起系统查找，引起系统查找s s段在辅存的位置，将该段段在辅存的位置，将该段页表调入主存；页表调入主存；如查页表时，发现如查页表时，发现s s段的段的p p页不在主存，产生页不在主存，产生“缺缺页中断页中断”，引起系统查找，引起系统查找s s段段p p页在辅存的位置，页在辅存的位置，并将该页调入主存，当主存已无空闲页框时，就并将该页调入主存，当主存已无空闲页框时，就会导致淘汰页面。会导致淘汰页面。138 段表控
109、制寄存器段表控制寄存器段段表表始始址址 段段表表长长度度段号段号s s 页号页号p p 位移位移d d段超长段超长? ?页框号页框号 位移位移段表段表页表页表请求段页式存储管理的动态地址转换请求段页式存储管理的动态地址转换(3)(3)1394.6 Intel x864.6 Intel x86分段和分页存储结构分段和分页存储结构1)1)Intel x86Intel x86系列系列CPUCPU提供三种工作模式：实地址提供三种工作模式：实地址模式、保护模式和虚拟模式、保护模式和虚拟80868086模式模式2)2)Intel x86Intel x86上虚拟存储管理核心表上虚拟存储管理核心表 ：LDTL
110、DT和和GDT GDT 3)3)段寄存器和虚拟地址段寄存器和虚拟地址(b) (b) 段寄器高段寄器高1313位为段选择符位为段选择符(a)(a)虚拟地址虚拟地址段选择符段选择符 偏移量偏移量47 32 31 047 32 31 0index T RPLindex T RPL15 2 1 015 2 1 00=GDT / 1=LDT0=GDT / 1=LDT特权级特权级Intel x86Intel x86虚拟地址和段选择符虚拟地址和段选择符140虚拟地址空间大小虚拟地址空间大小虚拟地址空间共包含虚拟地址空间共包含16K16K个存储器分段，其中个存储器分段，其中GDTGDT映射一半（映射一半（81
111、928192个）全局虚拟地址空间，由个）全局虚拟地址空间，由LDTLDT映射另一半（映射另一半（81928192个）局部虚拟地址空间，个）局部虚拟地址空间，发生进程切换时，发生进程切换时，LDTLDT更新为待执行进程的更新为待执行进程的LDTLDT，而而GDTGDT保持不变。保持不变。由于每段偏移量由于每段偏移量3232位、即位、即=4GB=4GB，整个虚存地址空，整个虚存地址空间间=16K4GB=64TB=16K4GB=64TB。1414.7 Linux4.7 Linux虚拟存储管理虚拟存储管理4.7.1 Linux4.7.1 Linux虚拟存储管理概述虚拟存储管理概述在在LinuxLinu
112、x中，进程可访问中，进程可访问4GB4GB虚拟地址空间，其中，虚拟地址空间，其中，从从0 0到到3GB3GB被用户进程独占并可直接进行访问；从被用户进程独占并可直接进行访问；从3GB3GB到到4GB4GB是内核空间，由所有核心态进程共享，是内核空间，由所有核心态进程共享，存放系统代码和数据。存放系统代码和数据。进程有一个页目录，大小为一个页，页目录的起进程有一个页目录，大小为一个页，页目录的起始地址存放在进程始地址存放在进程mm_structmm_struct结构中，工作时被结构中，工作时被装入寄存器装入寄存器CR3CR3。页目录项为。页目录项为4 4字节，共有字节，共有10241024项，项
113、，用来保存页表的起始地址。每张页表也用一个页用来保存页表的起始地址。每张页表也用一个页面存储，每项为面存储，每项为4 4字节，共有字节，共有10241024项，用来保存项，用来保存页框基地址。页框基地址。 142页表项的格式页表项的格式 0 0位为页面在位为页面在/ /不在主存；不在主存；1 1位若置位，页面可读可写，否位若置位，页面可读可写，否则只读；则只读；2 2位为选择用户级访问许可位为选择用户级访问许可/ /内核级访问许可；内核级访问许可；3 3位为若置位表示页面位为若置位表示页面cachecache采用采用“直写直写”，否则回写缓存；，否则回写缓存；4 4位为若置位，禁用高速缓存；位
114、为若置位，禁用高速缓存；5 5位为置位表示该页面最近位为置位表示该页面最近曾被访问过；曾被访问过；6 6位为被置位，表示页面在上次该位被清除位为被置位，表示页面在上次该位被清除之后页面内容被改变过；之后页面内容被改变过；7 7位为页面大小；位为页面大小；8 8位为全局页面；位为全局页面；1212至至3131位是页框基地址。位是页框基地址。页框基址页框基址 p pD DA ACDCDWTWT U/SU/S R/WR/W P P31 12 8 7 6 5 4 3 2 1 01434.7.2 4.7.2 存储管理数据结构存储管理数据结构1.1.物理主存数据结构物理主存数据结构 物理主存分三个层次管理
115、：物理主存分三个层次管理： 1)1)存储节点存储节点 2)2)管理区管理区 3)3)页框页框1441) 1) 页框管理页框管理物理主存划分成页框，其长度与页面相等，系统物理主存划分成页框，其长度与页面相等，系统中所有页框都由中所有页框都由mem_mapmem_map表描述，它在初始化时表描述，它在初始化时通过通过free_area_initfree_area_init( )( )函数创建。函数创建。mem_mapmem_map本身是由本身是由mem_map_tmem_map_t组成的数组，每个组成的数组，每个mem_map_tmem_map_t描述一个页框，整个数组就代表系统描述一个页框，整个
116、数组就代表系统中的全部页框，数组下标就是物理页框的序号，中的全部页框，数组下标就是物理页框的序号，用于对页框进行管理。用于对页框进行管理。 1452) 2) 管理区管理管理区管理主存被划分成三个区：主存被划分成三个区：ZONE_DMAZONE_DMA区，专供区，专供DMADMA使用；使用；ZONE_NORMALZONE_NORMAL区，被常规使用；区，被常规使用；ZONE_HIGHMEMZONE_HIGHMEM区，区，内核不能直接映射区。内核不能直接映射区。设置设置ZONE_DMAZONE_DMA是保证磁盘是保证磁盘I/OI/O所需的连续物理页所需的连续物理页框，框，ZONE_NORMALZO
117、NE_NORMAL里的页框用作通常的主存分配。里的页框用作通常的主存分配。146管理区数据结构管理区数据结构zone_structzone_struct含有一组空闲区队列，含有一组空闲区队列，typedeftypedef structstruct free_area_structfree_area_struct /*/*空闲区队列头部结空闲区队列头部结构构* */ / structstruct list_headlist_head free_listfree_list； /*/*指向空闲区队列指向空闲区队列* */ / unsigned unsigned intint *map *map；/*
118、/*指向指向bitmapbitmap表表* */ / free_area_tfree_area_t；147存储节点管理数据结构存储节点管理数据结构 typedeftypedef structstruct pglist_datapglist_data /* /*存储节点的结构存储节点的结构* */ / zone_tzone_t node_zonesnode_zonesMAX_NR_ZONESMAX_NR_ZONES; ; /* /*该节点的管理区数组该节点的管理区数组* */ / zonelist_tzonelist_t node_zonelistsnode_zonelistsNR_GFPIND
119、EXNR_GFPINDEX； structstruct page * page *node_mem_mapnode_mem_map; /*; /*存储节点的主存映射表存储节点的主存映射表* */ / intint nr_zonesnr_zones; ; /* /*存储节点的管理区数目存储节点的管理区数目* */ / unsigned long * unsigned long * valid_addr_bitmapvalid_addr_bitmap; ; /* /*位图表示的有效地址位图表示的有效地址* */ / structstruct bootmem_databootmem_data * *
120、 bdatabdata; /*; /*存放位图的数据结构存放位图的数据结构* */ / unsigned long unsigned long node_start_paddrnode_start_paddr;/*;/*存储节点起始物理地址存储节点起始物理地址* */ / unsigned long unsigned long node_start_mapnrnode_start_mapnr;/*;/*在在mem_mapmem_map中的下标中的下标* */ / unsigned long unsigned long node_sizenode_size; /*; /*存储节点物理主存大小存储
121、节点物理主存大小* */ / intint node_idnode_id; ; /* /*存储节点标识符存储节点标识符* */ / structstruct pglist_datapglist_data * * node_nextnode_next; /*; /*下一存储节点指针下一存储节点指针* */ / pg_data_tpg_data_t; ;1482.2.虚拟主存管理虚拟主存管理 1) 1) 虚存区虚存区vm_area_structvm_area_struct 内核将进程的每个虚存区作为一个单独的主存对内核将进程的每个虚存区作为一个单独的主存对象管理，每个虚存区都拥有一致的属性，比如访
122、象管理，每个虚存区都拥有一致的属性，比如访问权限等，采用虚存区问权限等，采用虚存区vma(virtualvma(virtual memory memory area)area)来描述进程的虚拟主存的一个区域，而来描述进程的虚拟主存的一个区域，而vmavma链表用来表示该进程实际用到的虚拟地址空间。链表用来表示该进程实际用到的虚拟地址空间。1492)2)主存描述符主存描述符mm_structmm_struct进程有一个进程有一个mm_structmm_struct结构，在进程的结构，在进程的task_structtask_struct结构中有指针结构中有指针mmmm指向该进程的指向该进程的mm_
123、structmm_struct结构，结构，mm_structmm_struct结构是进程整个虚拟结构是进程整个虚拟地址空间的抽象。地址空间的抽象。结构中的前三个虚存区指针：结构中的前三个虚存区指针：mmapmmap用来建立一个用来建立一个虚存区间结构的链接队列；虚存区间结构的链接队列；mmap_avlmmap_avl用来建立一用来建立一个虚存区结构的个虚存区结构的AVLAVL树；树；mmap_cachemmap_cache用来指向最用来指向最近一次用到的那个虚存区结构，因为程序具有的近一次用到的那个虚存区结构，因为程序具有的局部性，很可能这就是下次要用到的区间，以便局部性，很可能这就是下次要用
124、到的区间，以便提高效率。提高效率。指针指针pgdpgd指向该进程的页表目录，当进程被调度指向该进程的页表目录，当进程被调度时，该指针被转换成物理地址，写入控制寄存器时，该指针被转换成物理地址，写入控制寄存器CR3CR3。150进程虚存管理数据结构进程虚存管理数据结构进程任务结构进程任务结构task_structtask_struct* *mmmm虚存区结构虚存区结构vm_area_strucvm_area_struct t* *vm_mmvm_mmvm_startvm_startvm_endvm_end* *vm_opsvm_ops* *vm_nextvm_next页目录表页目录表pgdpgd
125、主存管理结构主存管理结构mm_structmm_struct* *mmapmmap* *pgdpgd封封装装的的操操作作集集vm_operations_structvm_operations_structopen( )open( )close( )close( )unmapunmap( )( )swapinswapin( )( )页表页表PTEPTE页框页框PFPF ( (共享库共享库) )进程虚拟主存进程虚拟主存虚拟主存段虚拟主存段(0x40000000)(0x40000000) (data)(data)虚拟主存段虚拟主存段(0x0804a020)(0x0804a020) (text)(te
126、xt)虚拟主存段虚拟主存段(0x08048000)(0x08048000)虚存区结构虚存区结构vm_area_strucvm_area_struct t* *vm_mmvm_mmvm_startvm_startvm_endvm_end* *vm_opsvm_ops* *vm_nextvm_next虚存区结构虚存区结构vm_area_structvm_area_struct* *vm_mmvm_mmvm_startvm_startvm_endvm_end* *vm_opsvm_ops* *vm_nextvm_next 1514.7.3 4.7.3 主存页框调度主存页框调度主存页框调度有两项工作：
127、主存页框调度有两项工作：一是页框分配、使用和回收；一是页框分配、使用和回收；二是盘交换区管理，并非所有的主存页都可交换二是盘交换区管理，并非所有的主存页都可交换出去，只有映射到用户空间的页才会被换出。出去，只有映射到用户空间的页才会被换出。0页框分配时，为了提高效率，采用伙伴系统，把连续页框分配时，为了提高效率，采用伙伴系统，把连续的页映射到连续的页框中。的页映射到连续的页框中。0主存页框由的主存页框由的pagepage数据结构描述和管理；与此类似，数据结构描述和管理；与此类似，交换设备（磁盘）的每个物理页面也要在主存中有相交换设备（磁盘）的每个物理页面也要在主存中有相应数据结构，用以表示该页
128、面是否已被分配，以及有应数据结构，用以表示该页面是否已被分配，以及有几个用户在共享该页面，内核定义几个用户在共享该页面，内核定义swap_info_structswap_info_struct数据结构，用来描述和管理用于页面交换的设备。数据结构，用来描述和管理用于页面交换的设备。1524.7.4 4.7.4 进程虚存空间映射进程虚存空间映射1 1 mmapmmap( )( )2 2 mummapmummap( )( )1534.7.5 4.7.5 缺页异常处理缺页异常处理(1)(1)页面替换基于最少使用频率策略页面替换基于最少使用频率策略: :使用一个使用一个8 8位的位的ageage变量，每
129、当一页被访问时，变量，每当一页被访问时，ageage变量增变量增1 1；在后台，内核周期性地扫描全局页；在后台，内核周期性地扫描全局页池，且当它在主存中所有页间循环时，对每页的池，且当它在主存中所有页间循环时，对每页的ageage变量减变量减1 1；ageage为为0 0的页是一个的页是一个“老老”页，有一页，有一段时间没有被访问过，因而是可用于替换的最佳段时间没有被访问过，因而是可用于替换的最佳候选页；候选页；ageage值越大，该页最近被使用过的频率值越大，该页最近被使用过的频率越高，也就越不适合于替换。越高，也就越不适合于替换。 154缺页异常处理缺页异常处理(2)(2)缺页中断处理步骤
130、：缺页中断处理步骤：1 1 读取引起缺页的线性地址。读取引起缺页的线性地址。2 2 检查异常发生时检查异常发生时CPUCPU是否正在处理中断，或者执行内核线是否正在处理中断，或者执行内核线程，如是则进行出错处理。程，如是则进行出错处理。3 3 调用调用find_vmafind_vma找到发生页面错误的虚拟地址所在的找到发生页面错误的虚拟地址所在的vm_area_structvm_area_struct结构，以确定该错误的线性地址是否包含结构，以确定该错误的线性地址是否包含在进程地址空间中，或堆栈的合理扩展区。在进程地址空间中，或堆栈的合理扩展区。4 4 若异常是由读或执行访问引起的，则函数检查
131、该页是否已若异常是由读或执行访问引起的，则函数检查该页是否已经在经在RAMRAM中，若不在且该线性地址区的访问权限与引起异中，若不在且该线性地址区的访问权限与引起异常的访问类型相匹配，则执行常的访问类型相匹配，则执行“请求调页请求调页”处理。处理。5 5 检查进程页表项中的位检查进程页表项中的位P P，区分缺页对应的页面是在交换，区分缺页对应的页面是在交换空间（空间（P=0P=0且页表项非空）还是在磁盘中某执行文件映像且页表项非空）还是在磁盘中某执行文件映像中。最后，进行页面调入操作。中。最后，进行页面调入操作。 155作业作业P303 1P303 1（只做（只做4 4个页框和个页框和6 6个页框）个页框）P303 5P303 5P304 11P304 11156补充补充1 1设页大小为设页大小为1k1k（1024B1024B），页表如图所示，页表如图所示，将逻辑地址将逻辑地址3739037390、4640246402转换为相应物理转换为相应物理地址。地址。8485959636 37 38 39页表页表157对下图所示的程序结构，试用覆盖的方法分配空间，对下图所示的程序结构，试用覆盖的方法分配空间，使得空间最小。使得空间最小。A(20KB)F(40KB)G(30KB)B(50KB)D(20KB)C(30KB)E(40KB)H(40KB)I(30KB)补充补充2 2158
