计算机操作系统(第五章)

第五章存储管理主要内容5.1存储管理的功能5.2分区存储管理5.3覆盖与交换技术5.4页式管理5.5段式与段页式管理5.6局部性原理和抖动问题31一月2023第2页OperatingSystem操作系统第五章存储管理存储器介绍存储器的层次寄存器高速缓存主存储器磁盘缓存磁盘可移动存储介质访问速度趋慢制造成本趋高第3页OperatingSystem操作系统第五章存储管理Programmustbebrought(fromdisk)intomemoryandplacedwithinaprocessforittoberunMainmemoryandregistersareonlystorageCPUcanaccessdirectlyRegisteraccessinoneCPUclock(orless)MainmemorycantakemanycyclesCache

sitsbetweenmainmemoryandCPUregistersProtectionofmemoryrequiredtoensurecorrectoperation什么是存储管理？存储管理是操作系统的重要组成部分，负责管理计算机系统的重要资源——主存储器。存储管理的主要内容包括：主存储空间的分配和回收地址转换和存储保护主存储空间共享主存储空间扩充31一月2023第5页OperatingSystem操作系统第五章存储管理5.1存储管理的功能虚拟存储器：在硬件的支持下完成统一管理内存与外存之间数据和程序段自动交换的虚拟存储器功能地址变换：将多个虚拟的一维线性空间或多维线性空间变换到内存的唯一的一维物理线性地址空间。控制内外存之间的数据传输（存储器扩充）：存储器的逻辑组织和物理组织；由应用程序控制：覆盖；由OS控制：交换（整个进程空间），虚拟存储的请求调入和预调入（部分进程空间）内存的分配和回收：分配和回收算法及相应的数据结构。内存信息的共享和保护：代码和数据共享地址空间访问权限（读、写、执行）31一月2023第6页OperatingSystem操作系统第五章存储管理存储管理的功能存储分配和回收：分配和回收算法及相应的数据结构。地址变换：可执行文件生成中的链接技术程序加载(装入)时的重定位技术进程运行时硬件和软件的地址变换技术和机构存储共享和保护：代码和数据共享地址空间访问权限（读、写、执行）存储器扩充：存储器的逻辑组织和物理组织；由应用程序控制：覆盖；由OS控制：交换（整个进程空间），虚拟存储的请求调入和预调入（部分进程空间）返回5.1.1虚拟存储器

进程中的目标代码、数据等的虚拟地址组成的虚拟空间称为虚拟存储器。虚拟存储器不考虑物理存储器的大小和信息存放的实际位置，只规定每个进程中互相关连的信息的相对位置。每个进程都拥有自己的虚拟存储器。31一月2023OperatingSystem操作系统第五章存储管理5.1.2地址变换

1.逻辑地址（相对地址，虚地址）：用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式。（用户的程序地址(指令地址或操作数地址)）其首地址为0，其余指令中的地址都相对于首地址来编址。不能用逻辑地址在内存中读取信息。2.物理地址（绝对地址，实地址）：内存中存储单元的地址。物理地址是计算机主存单元的真实地址，又称为绝对地址或实地址，物理地址可直接寻址。3.地址变换（映射）：将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址。当程序装入内存时,操作系统要为该程序分配一个合适的内存空间，由于程序的逻辑地址与分配到内存物理地址不一致,而CPU执行指令时，是按物理地址进行的，所以要进行地址转换。

4.内存空间

物理地址的集合所对应的空间组成了内存空间。31一月2023第10页OperatingSystem操作系统第五章存储管理

5.作业地址空间

用户程序所有的逻辑地址集合对应的空间。作业地址空间01n-1

6.作业地址空间与内存空间

内存空间01m-1作业1地址空间01n-1作业i地址空间01k-1┇┇31一月2023第11页OperatingSystem操作系统第五章存储管理8.什么是地址映射（地址重定位）

将程序地址空间中使用的逻辑地址变换成内存中的地址的过程称为地址映射。有时也称为地址重定位。31一月2023第12页OperatingSystem操作系统第五章存储管理一个用户程序的多步处理重定位：在可执行文件装入时需要解决可执行文件中地址（指令和数据）和内存地址的对应。由操作系统中的装入程序loader来完成。程序在成为进程前的准备工作编辑：形成源文件(符号地址)编译：形成目标模块(模块内符号地址解析)链接：由多个目标模块或程序库生成可执行文件(模块间符号地址解析)装入：构造PCB，形成进程(使用物理地址)重定位方法：静态地址重定位动态地址重定位地址映射LoadA2003456

。。1200物理地址空间LoadAdata1data13456源程序LoadA20034560100200编译连接逻辑地址空间BA=1000逻辑地址、物理地址和地址映射1.静态地址重定位当用户程序被装入内存时，一次性实现逻辑地址到物理地址的转换，以后不再转换。

一般在装入内存时由软件完成由于静态地址重定位是在程序装入内存时完成从逻辑地址到物理地址的转换的。评价:

执行速度快，不需要硬件的支持。

缺点：是程序一旦装入内存，移动就比较困难。不能实现虚拟存储器；必须占有连续的内存空间；不能实现程序和数据的共享。31一月2023第17页OperatingSystem操作系统第五章存储管理31一月2023OperatingSystem操作系统第五章存储管理第18页2.动态地址重定位在程序运行过程中要访问数据时再进行地址变换（即在逐条指令执行时完成地址映射。一般为了提高效率，此工作由硬件地址映射机制来完成。硬件支持，软硬件结合完成）。

需要硬件（CPU）的支持movr1,[500]123movr1,[500+m]12301005005990mm+100256k-1作业地址空间存储空间m+500重定位装入程序31一月2023第19页OperatingSystem操作系统第五章存储管理

(3)动态地址重定位在程序执行期间，随着每条指令和数据的访问自动地连续地进行地址映射。movr1,[500]123

movr1,[500]123010050059901000256k-1作业地址空间存储空间重定位寄存器1100150016005001000逻辑地址++31一月2023第20页OperatingSystem操作系统第五章存储管理动态地址重定位是由硬件地执行时完成的，程序中不执行的程序就不做地址映射的工作，这样节省了CPU的时间。重定位寄存器的内容由操作系统用特权指令来设置，比较灵活。实现动态地址重定位必须有硬件的支持，并有一定的执行时间延迟。现代计算机系统中都采用动态地址映射技术。动态地址重定位技术能满足以下目标：（1）具有给一个用户程序任意分配内存区的能力；（2）可实现虚拟存储；（3）具有重新分配的能力（4）对于一个用户程序，可以分配到多个不同的存储区31一月2023第21页OperatingSystem操作系统第五章存储管理

3.静态地址重定位与动态地址重定位的区别静态地址重定位动态地址重定位

在作业装入过程中在程序执行期间进行地址映射进行地址映射需软件需硬件地址变换机构重定位装入程序重定位寄存器需花费较多CPU时间地址变换快不灵活灵活31一月2023第22页OperatingSystem操作系统第五章存储管理5.1.3内外存数据传输控制（主存扩充）

主存扩充也就是提供虚拟存储器

1.问题的提出主存容量始终显得十分紧张

如何使用户使用计算机不受主存容量的限制？

2.解决问题的思路

装入部分程序地址空间，它还能正确地执行？

3.实现方法

程序的全部代码和数据存放在辅存中；

将程序当前执行所涉及的那部分程序代码放入主存中；程序执行时，当所需信息不在主存，由操作系统和硬件相配合来完成主存从辅存中调入信息，程序继续执行。

31一月2023第23页OperatingSystem操作系统第五章存储管理

4.什么是虚拟存储器由操作系统和硬件相配合来完成主存和辅存之间的信息的动态调度。这样的计算机系统好像为用户提供了一个其存储容量比实际主存大得多的存储器，这个存储器称为虚拟存储器。

5.虚拟存储器的核心

逻辑地址与物理地址分开主存空间与地址空间分开提供地址变换机构

6.实现虚拟存储器的物质基础

有相当容量的辅存足以存放多用户的作业的地址空间有一定容量的主存存放运行进程的当前信息地址变换机构31一月2023第24页OperatingSystem操作系统第五章存储管理5.1.4内存的分配与回收在多道程序设计的环境中，主存分配的功能包括：制定分配策略、构造分配用的数据结构、响应系统的内存分配的请求和回收系统释放的内存区。

1.构造分配用的数据结构主存资源信息块：等待队列头指针自由主存队列头指针主存分配程序地址

31一月2023第25页OperatingSystem操作系统第五章存储管理2.制定分配策略(2)放置策略决定内存中放置信息的区域（或位置），即如何在若干个空闲区中选择一个或几个空闲区的原则；(4)调入策略决定信息装入内存的时机，有两种：在用户请求时调入，称为请调；根据某种算法，确定系统将要使用的信息，并在执行前预先调入内存，称为预调；(3)淘汰策略当内存不足时，决定将某些信息调出内存的策略。3.实施主存分配与回收31一月2023第26页OperatingSystem操作系统第五章存储管理5.1.5内存信息的共享与保护

常用的内存信息保护方法有硬件法、软件法和软硬件结合三种.

1.什么是存储保护在多用户环境中，主存储器按区分配给各用户程序使用。为了互不影响，必须由硬件(软件配合)保证每道程序只能在给定的存储区域内活动，这种措施叫做存储保护。

2.存储保护方法通常的存储保护方法——

界地址保护保护键保护31一月2023第27页OperatingSystem操作系统第五章存储管理

3.界地址保护

(1)上、下界防护

下界寄存器20KB

movr1,[500]123020KB256KB1存储空间24KB上界寄存器24KB设置上下界寄存器内容判断是否越界满足

20KB≤D＜24KB

允许访问否则发生越界中断31一月2023第28页OperatingSystem操作系统第五章存储管理

(2)基地、限长防护

基址寄存器20KB

movr1,[500]123020KB256KB1存储空间24KB限长寄存器4KB设置基址、限长寄存器内容判断是否越界满足

逻辑地址＜4KB

允许访问否则发生越界中断31一月2023第29页OperatingSystem操作系统第五章存储管理保护键法为每一个被保护存储块分配一个单独的保护键.在程序状态字中则设置相应的保护键开关字段，对不同的进程赋予不同的开关代码和与被保护的存储块中的保护键匹配。保护键可设置成对读写同时保护的或只对读，写进行单项保护的.例如，图5.5中的保护键0，就是对2K到4K的存储区进行读写同时保护的，而保护键2则只对4K到6K的存储区进行写保护。图5.5保护键保护法(2保护键保护法31一月2023第30页OperatingSystem操作系统第五章存储管理另外一种常用的内存保护方式是：界限寄存器与CPU的用户态或核心态工作方式相结合的保护方式31一月2023第31页OperatingSystem操作系统第五章存储管理5.2分区存储管理

一.概述分区存储管理是满足多道程序设计的最简单的一种存储管理方法，它允许多个用户程序同时存在系统内存中，即共享内存空间。最早期的分区存储管理采用固定分区的方法，把内存空间分成若干个大小不等的区域，称为分区。每个用户程序（作业、进程）调入内存后，占用其中一个分区，程序运行完成后释放该分区。这种存储管理的方法的主要问题是内存使用效率极低，很快就被淘汰了。31一月2023第32页OperatingSystem操作系统第五章存储管理分区管理的基本原理是给每一个内存中的进程划分一块适当大小的存储区,以连续存储各进程的程序和数据，使各进程得以并发执行。按分区的时机，分区管理可以分为固定分区和动态分区两种方法。固定分区可变分区5.2.1分区存储管理的基本原理1.固定分区法存储管理技术

把内存分为一些大小相等或不等的分区(partition)，每个应用进程占用一个或几个分区。操作系统占用其中一个分区。系统对内存的管理和控制通过数据结构——分区说明表进行，分区说明表说明各分区号、分区大小、起始地址和是否是空闲区(分区状态)。内存的分配释放、存储保护以及地址变换等都通过分区说明表进行。图5.6给出了固定分区时分区说明表和对应内存状态的例子。图5.6固定分区法31一月2023第34页OperatingSystem操作系统第五章存储管理内碎片动态分区存储管理技术

系统生成后，操作系统占用内存的一部分，一般在物理内存的开始处，比如，一个操作系统占20KB，装入系统后占用0～20KB的内存空间，剩下的部分作为一个空闲区，当一个用户程序（作业、进程）调入内存时，把这个空闲区的低地址部分的区域分配给它，如图所示。31一月2023第35页OperatingSystem操作系统第五章存储管理

当有作业完成后释放所占用的存储区。在系统运行的过程中，系统中形成多个空闲的不连续的存储区。31一月2023第36页OperatingSystem操作系统第五章存储管理外碎片图5.8内存分配变化过程用基址寄存器实现动态地址映射

在这种存储管理技术中，系现设置一个专用寄存器，称为基地址寄存器，当一个进程（或程序、作业）被调度运行时，系统首先从PCB中取出该进程的首地址装入基地址寄存器中，在该进程运行的过程中实现动态地址映射。31一月2023第39页OperatingSystem操作系统第五章存储管理分区分配机构

1.分区描述器

分配标志flag

大小size

勾链字nextflag：为0——空闲区为1——已分配区size：分区大小next：空闲区——自由主存队列中的勾链字已分配区——此项为零31一月2023第40页OperatingSystem操作系统第五章存储管理

2.自由主存队列(或空闲区队列)结构20KB

0

os

作业1

作业3

52KB66KB130KB230KB256KB1主存52KBm-rib

014KB230KB

026KB

自由主存队列31一月2023第41页OperatingSystem操作系统第五章存储管理5.2.2分区的分配与回收1.分区分配

•用户请求分配一个主存块

•分区分配程序在自由主存队列中找一个满足用户需要的空闲块

•若找到，则返回所分配区域的首址，否则，告之不能满足要求。31一月2023第42页OperatingSystem操作系统第五章存储管理5.2.2分区的分配与回收

1.固定分区时的分配与回收固定分区法时的内存分配与回收较为简单，当用户程序要装入执行时，通过请求表提出内存分配要求和所要求的内存空间大小。存储管理程序根据请求表查询分区说明表，从中找出一个满足要求的空闲分区，并将其分配给申请者.当进程执行完毕，不再需要内存资源时，管理程序将对应的分区状态置为未使用即可固定分区分配算法2.动态分区时的分配与回收动态分区时的分配与回收主要解决三个问题:(1)对于请求表中的要求内存长度，从可用表或自由链中寻找出合适的空闲区分配程序。(2)分配空闲区之后，更新可用表或自由链。(3)进程或作业释放内存资源时，和相邻的空闲区进行链接合并，更新可用表或自由链。

动态分区时的分配方法从可用表或自由链中寻找空闲区的常用方法有三种。它们是最先适应法(firstfitalgorithm),最佳适应法(bestfitalgorithm)和最坏适应法(worstfitalgorithm)。这三种方法要求可用表或自由链按不同的方式排列分配算法什么是放置策略

选择空闲区的策略，称为放置策略。常用的放置策略——

首次匹配(最先适应算法)

最佳匹配(最佳适应算法)

最坏匹配(最坏适应算法)

31一月2023第46页OperatingSystem操作系统第五章存储管理最先适应算法

(1)什么是最先适应算法

最先适应算法要求可用表按起始地址递增的次序排列，是将输入的作业放置到主存里第一个足够装入它的可利用的空闲区中。

(2)最先适应算法的例(3)特点

尽可能地利用存储器的低地址部分的空闲区，而尽量保存高地址部分的大空闲区。

作业

A18KB

os在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB-131一月2023第47页OperatingSystem操作系统第五章存储管理

(1)最先适应算法中的自由主存队列

(a)最先适应算法中的自由主存队列20KB

030KB100KB

020KB

160KB

05KB

210KB

046KB

os在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB-131一月2023第48页OperatingSystem操作系统第五章存储管理最佳适应算法

(1)什么是最佳适应算法最佳适应算法要求从小到大的次序组成空闲区可用表或自由链，是将输入的作业放置到主存中与它所需大小最接近的空闲区中。

(2)最佳适应算法的例(3)特点尽可能地利用存储器中小的空闲区，而尽量保存大的空闲区。

作业

A18KB

os在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB-131一月2023第49页OperatingSystem操作系统第五章存储管理

(2)最佳适应算法中的自由主存队列

(b)最佳适应算法中的自由主存队列160KB

05KB100KB

020KB20KB

030KB

210KB

046KB

os在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB-131一月2023第50页OperatingSystem操作系统第五章存储管理最坏适应算法

(1)什么是最坏适应算法最坏适应算法要求空闲区按其大小递减的顺序组成空闲区，是将输入的作业放置到主存中主存中最不适合它的空闲区中。

(2)最坏适应算法的例(3)特点尽可能地利用存储器中大的空闲区，而尽量保存小的空闲区。

作业

A18KB

os在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB-131一月2023第51页OperatingSystem操作系统第五章存储管理

(2)最坏适应算法中的自由主存队列

(b)最坏适应算法中的自由主存队列210KB

05KB^

020KB160KB

030KB

100KB

0

46KB

20k

os在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB-131一月2023第52页OperatingSystem操作系统第五章存储管理4.几种分配算法的比较最先适应算法的另一个优点就是尽可能地利用了低地址空间，从而保证高地址有较大的空闲区来放置要求内存较多的进程或作业。最佳适应法找到的空闲区是最佳的。不过,在某些情况下并不一定提高内存的利用率。最坏适应算法正是基于不留下碎片空闲区这一出发点的。它选择最大的空闲区来满足用户要求，以期分配后的剩余部分仍能进行再分配。

5.关于二种放置策略的讨论

作业A要求18KB；作业B要求25KB；作业C要求30KB。用最先适应算法、最佳适应算法来处理该作业序列，看哪种算法合适。

os在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB-131一月2023第54页OperatingSystem操作系统第五章存储管理(a)首次适应算法中的自由主存队列20KB

030KB100KB

020KB

160KB

05KB

210KB

046KB

(b)最佳适应算法中的自由主存队列160KB

05KB100KB

020KB

20KB

030KB

210KB

046KB

作业A要求18KB作业B要求25KB作业C要求30KB31一月2023第55页OperatingSystem操作系统第五章存储管理3.动态分区的回收与拼接(3)进程或作业释放内存资源时，和相邻的空闲区进行链接合并，更新可用表或自由链。

回收主存块的四种情况

f1r

作业2r上邻空闲区r

作业1r

f2r下邻空闲区r

f1r

f2r上下邻空闲区r

作业1r

作业2r上下邻已分配区r31一月2023第56页OperatingSystem操作系统第五章存储管理

回收分区r上邻空闲区r与f1合并成为一个大的空闲区f1

回收分区r下邻空闲区r与f2合并成为一个大的空闲区f2

作业2

f1

作业2

f1r

作业2

r

f2

作业2

f2r31一月2023第57页OperatingSystem操作系统第五章存储管理

回收分区r上、下邻空闲区r与f1、f2合并成为一个大的空闲区f1

回收分区r上、下邻已分配区r成为一个新的空闲区f

r

f1

f1

f2

f2r

作业1

作业2r

作业1

作业2

fr31一月2023第58页OperatingSystem操作系统第五章存储管理碎片问题及拼接技术

1.什么是碎片问题在已分配区之间存在着的一些没有被充分利用的空闲区。20KB

os

作业1

作业3

作业4

52KB66KB130KB230KB256KB1主存180KB

02.拼接技术所谓拼接技术是指移动存储器中某些已分配区中的信息，使本来分散的空闲区连成一个大的空闲区。

如何解决碎片问题？31一月2023第59页OperatingSystem操作系统第五章存储管理

解决碎片问题的图示

20KB

0

os

作业1

作业3

作业4

52KB116KB166KB256KB1主存20KB

os

作业1

作业3

作业4

52KB66KB130KB230KB256KB1主存180KB

031一月2023第60页OperatingSystem操作系统第五章存储管理5.2.3有关分区管理其他问题的讨论1.关于虚存的实现利用分区式管理，也同样存在有每个用户可以自由编程的虚拟空间。但是,分区式管理方式无法实现那种用户进程所需内存容量只受内存和外存容量之和限制的虚拟存储器。如果不采用内存扩充技术，每个用户进程所需内存容量是受到分区大小限制的。2.关于内存扩充由于分区式管理时各用户进程或作业所要求的内存容量受到分区大小的限制,如果不采用内存扩充技术，将会极大地限制分区式管理技术的使用。在分区式管理中，可以使用覆盖或交换技术来扩充内存。3.关于地址变换和内存保护静态地址重定位和动态地址重定位技术，都可用来完成分区式内存管理的地址变换。显然，动态分区时分区大小不固定，而空闲区的拼接会移动内存中的程序和数据，因此，使用静态地址重定位的方法来完成动态分区时的地址变换是不妥当的。在进行动态地址重定位时，每个分区需要一对硬件寄存器的支持，即基址寄存器和限长寄存器，分别用来存放作业或进程在内存分区的起始地址和长度。这一对硬件寄存器除了完成动态地址重定位的功能之外，还具有保护内存中数据和程序的功能。这由硬件检查CPU执行指令所要访问的虚拟地址完成。即设CPU指令所要访问的虚拟地址为D，若D>VR(VR是限长寄存器中的限长值)，则说明地址越界,所要访问的内存地址超出了该作业或进程所占用的内存空间。这时将产生保护中断。系统转去进行出错处理。若D<=VR，则该地址是合法的，由硬件完成对该虚拟地址的动态重定位。保护键法也可用来对内存各分区提供保护。4.分区存储管理的主要优缺点分区存储管理的主要优点如下:(1)实现了多个作业或进程对内存的共享，有助于多道程序设计，从而提高了系统的资源利用率。(2)该方法要求的硬件支持少，管理算法简单，因而实现容易。主要缺点有:(1)内存利用率仍然不高。和单一连续分配算法一样，存储器中可能含有从未用过的信息。而且，还存在着严重的碎小空闲区(碎片)不能利用的问题。(2)作业或进程的大小受分区大小控制，除非配合采用覆盖和交换技术。(3)难以实现各分区间的信息共享。分区存储管理技术的实现地址映射动态存储管理的机构（数据结构）分区的分配和回收三种基本的放置策略31一月2023第65页OperatingSystem操作系统第五章存储管理5.3覆盖与交换技术覆盖与交换技术是在多道环境下用来扩充内存的两种方法。覆盖技术主要用在早期的操作系统中，而交换技术则在现代操作系统中仍具有较强的生命力31一月2023第66页OperatingSystem操作系统第五章存储管理5.3.1覆盖技术覆盖技术：一个程序并不需要一开始就把它的全部指令和数据都装入内存后再执行，把程序划分为若干个功能上相对独立的程序段，按照程序的逻辑结构让不会同时执行的程序段共享同一块内存区。通常，这些程序段都被保存在外存中，当有关程序段的先头程序段已经执行结束后，再把后续程序段调入内存覆盖前面的程序段。从而达到了内存扩充的目的优点：内存得到了扩充缺点：程序员负担较重。要求对操作系统的虚空间和内部结构比较熟悉31一月2023第67页OperatingSystem操作系统第五章存储管理例如，设某进程的程序正文段由A，B，C，D，E和F等6个程序段组成。它们之间的调用关系如图5.13(a)所示，程序段A调用程序段B和C，程序段B又调用程序段F,程序段C调用程序段D和E。图5.13覆盖示例31一月2023第68页OperatingSystem操作系统第五章存储管理该进程正文段所要求的内存空间是：A(20K)+B(50K)+F(30K)+C(30K)+D(20K)+E(40K)=190K采用了覆盖技术所需内存空间是：A(20K)+B(50K)+E(40K)=110K可见采用覆盖技术，内存空间得到了节省31一月2023第69页OperatingSystem操作系统第五章存储管理5.3.2交换技术交换：指先将内存某部分的程序或数据写入外存交换区，再从外存交换区中调入指定的程序或数据到内存中来，并让其执行的一种内存扩充技术。优点：内存得到了扩充缺点：换出过程和换入过程都要完成与外存设备管理进程通信的任务31一月2023第70页OperatingSystem操作系统第五章存储管理覆盖技术与交换技术的关系1.覆盖技术要求程序员给出程序段之间的覆盖结构;交换技术不要求程序员给出程序段之间的覆盖结构。2.交换主要是在进程或作业之间进行；而覆盖则主要在同一个作业或进程内进行。3.覆盖只能覆盖那些与覆盖程序段无关的程序段。31一月2023第71页OperatingSystem操作系统第五章存储管理5.4页式存储管理

一.页式系统应解决的问题

1.问题的提出

分区存储管理的主要问题是碎片问题。在采用分区存储管理的系统中，会形成一些非常小的分区，最终这些非常小的分区不能被系统中的任何用户（程序）利用而浪费。造成这样问题的主要原因是用户程序装入内存时是整体装入的，为解决这个问题，提出了分页存储管理技术。31一月2023第72页OperatingSystem操作系统第五章存储管理

2.页式系统的基本概念

（1）页程序的地址空间被等分成大小相等的片，称为页，又称为虚页。

（2)主存块主存被等分成大小相等的片，称为主存块，又称为实页。31一月2023第73页OperatingSystem操作系统第五章存储管理3.页式存储管理要解决如下问题页式存储管理系统的地址映射；调入策略；淘汰策略；放置策略。31一月2023第74页OperatingSystem操作系统第五章存储管理5.4.1页式管理的基本原理（1）等分主存：把物理内存划分为大小相同的块，称为页面或页架（Frames)(大小为2的指数次方，介于512bytes和8,192bytes之间)并给个页从0开始编号：0，1，…,n（2）用户的逻辑地址空间分页：把用户的逻辑地址空间按照物理内存页面相同的大小划分，把虚空间划分为逻辑块，称为页(Pages)，并对其页从页从0开始编号：0，1，…,n逻辑地址的表示：每个虚地址用一个数对（p,d)来表示，p是页号，d是页内地址。P=int(A/L)d=mod(A,L)的的表示

二.页式地址变换

1.页表为了实现从地址空间到物理主存的映象，系统建立的记录页与内存块之间对应关系的地址变换的机构称为页面映像表，简称页表。

31一月2023第76页OperatingSystem操作系统第五章存储管理记录页号和页面号的对应关系页号（Page）页面号（Frame）页表（pagetable)地址变换的实例01KB01KB2KB3KB1主存作业2地址空间2KB3KB4KB5KB6KB7KB8KB9KB10KB101KB2KB1作业1地址空间01KB1作业3地址空间0516页号块号02140827作业1页表作业2页表作业3页表osos

分页映像存储的例

31一月2023第78页OperatingSystem操作系统第五章存储管理

2.虚地址结构(程序字)

虚地址是用户程序中的逻辑地址，它包括页号和页内地址（页内位移）。区分页号和页内地址的依椐是页的大小，页内地址占虚地址的低位部分，页号占虚地址的高位部分。由地址结构可知，每页长度为1K（210

），允许地址空间最多有16K（214）页

页号页内地址（位移量）

Pd23109031一月2023第79页OperatingSystem操作系统第五章存储管理

3.页式地址变换

(1)页式地址变换的例作业2地址空间中，设100号单元处有如下指令：movr1,[2500]。当这条指令执行时，如何进行正确的地址变换。movr1,[2500]12301KB1KB3KB1作业2地址空间2500→2*1024+452p=2w=4520000100111000100000010011100010031一月2023第80页OperatingSystem操作系统第五章存储管理地址变换1、根据逻辑地址2500，计算出该地址对应在页号和页内偏移地址

页号为2，页内偏移地址为4522、根据页表始址寄存器找到页表，查表可知第2页被安排到了第8个页框中。3、算出第8个页框的首地址，再加上偏移地址，即可得到逻辑地址2500对应的物理地址：

7*1024+452=76205、访问内存中地址为8644的存储单元

100111000100对于指令loadAX,[2500]如何找到逻辑地址2500对应的物理存储单元？

(2)页式地址变换过程

0001110111000100151090页号P页内位移W页表始址寄存器movr1,[2500]12301KB2KB3KB1作业2地址空间+021427页表

0000100111000100151090页号P页内位移W250001KB主存2KB3KB4KB5KB6KB7KB8KB9KB10KB1ososmovr1,[2500]123第1页7*1024+452=762031一月2023第82页OperatingSystem操作系统第五章存储管理

(3)页式地址变换的步骤

CPU给出操作数地址(为2500)；由分页机构自动地把逻辑地址分为两部分，得到页号p和页内相对位移w(p=2，w=452)；根据页表始址寄存器指示的页表始地址，以页号为索引，找到第2页所对应的块号(为7)；最后，将块号b和页内位移量w拼接在一起，就形成了访问主存的物理地址

(7*1024+452=7620)。31一月2023第83页OperatingSystem操作系统第五章存储管理

例：有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、10、5块，试将虚地址7145，3412转换成内存地址。虚地址3412P＝3412％2048＝1W＝3412mod2048＝1364MR=9*2048+1364=19796虚地址3412的内存地址是：19796虚地址7145P＝7145％2048＝3W＝7145mod2048＝1001MR=5*2048+1001=11241虚地址7145的内存地址是：1124131一月2023第84页OperatingSystem操作系统第五章存储管理例：若在一分页存储管理系统中，某作业的页表如下所示。已知页面大小为1024字节，试将逻辑地址1011，2148，3000，5012转化为相应的物理地址（注：此处块号即为页面号）。

页号块号02132136解：本题中，为了描述方便，设页号为P，页内位移为W，逻辑地址为A，内存地址为M，页面大小为L，则P=int(A/L)W=AmodL对于逻辑地址1011P=int(1011/1024)=0W=1011mod1024=1011A=1101查页表第0页在第2块，所以物理地址为M=1024*2+1101=3059。31一月2023OperatingSystem操作系统第五章存储管理对于逻辑地址为2148P=2148/1024=2W=2148mod1024=100A=2148=(2,100)查页表第2页在第1块，所以物理地址为M=1024*1+100=1124。对于逻辑地址为3000P=3000/1024=2W=3000mod1024=952A=3000=(2,952)查页表第2页在第1块，所以物理地址为M=1024*1+952=1976对于逻辑地址5012P=5012/1024=4W=5012mod1024=916因页号超过页表长度，该逻辑地址非法。31一月2023第86页OperatingSystem操作系统第五章存储管理连续的页在物理内存中可能处于不连续在页框中没有外碎片问题，存在内部碎片问题不需要把全部的页放入内存进程的虚空间（逻辑地址）怎么变换成页对用户是透明的。MMU把逻辑地址的高位解释为页号，低位解释为页内地址。0111231页号P页内位移量W编号0~1048575相对地址0~4095记录页号和页面号的对应关系页号（Page）页面号（Frame）页表（pagetable)地址变换的实例

三.请调策略

1.问题的提出

在页式存储管理提高了内存的利用效率，但并不为用户提供虚存，换句话说，当一个用户程序的页数大于当前总空闲内存块数时，系统就不能将该程序装入运行。即用户程序将受到物理内存大小的限制。为了解决这个问题，人们提出请求分页存储管理技术。

2.请求分页概念

请求分页技术当一个用户程序要调入内存时，不是将该程序全部装入内存，而是只装入部分页到内存，就可启动程序运行，在运行的过程中，如果发现要运行的程序或要访问数据不在内存，则向系统发出缺页中断请求，系统在处理这个中断时，将在外存相应的页调入内存，该程序继续运行。31一月2023第90页OperatingSystem操作系统第五章存储管理3.请求分页要解决的问题采用这种技术要解决以下问题：(1)怎样发现所访问的页面在不在主存？(2)当发现所需访问的页面不在主存时如何处理?31一月2023第91页OperatingSystem操作系统第五章存储管理4.数据结构为了实现请求分页技术，页表应增加相应的内容，反映该页是否在内存，在外存的位置，在内存的时间的长短等。中断位：0表示该页在内存，

1示该页不在内存

引用位：0表示最近没有进程访问，

1示最近有进程访问

修改位：0该页调入内存后没有修改，

1页调入内存后修改过31一月2023第92页OperatingSystem操作系统第五章存储管理

5.缺页处理

(1)作业2在请求分页系统中的存储映像

01KB主存2KB3KB4KB5KB6KB7KB8KB9KB10KB102142作业2页表osos作业2第1页作业2第0页3页号辅存地址中断位块号

0011地址地址地址地址01KB2KB4KB1作业2地址空间movr1,[2120]addr1,[3410]006251

006802

3KB31一月2023第93页OperatingSystem操作系统第五章存储管理

(2)缺页处理的例

作业2的主存块数为m2=3

当程序执行“movr1，[2120］”时

CPU产生的虚地址为2120分页机构得p=2，w=72

查页表。该页中断位i=1，发生缺页中断

01KB2KB4KB1作业2地址空间movr1,[2120]addr1,[3410]006251

006802

3KB如主存中有空白块，且nm则直接调入如主存中无空白块，或n

m，则需淘汰该作业在主存中的一页31一月2023第94页OperatingSystem操作系统第五章存储管理地址变换机构31一月2023OperatingSystem操作系统第五章存储管理第97页

四.淘汰策略

1.什么是淘汰策略用来选择淘汰哪一页的规则就叫做置换策略，或称淘汰算法。

2.淘汰算法的性能衡量

颠簸(thrashing)，又称为“抖动”。简单地说，导致系统效率急剧下降的主存和辅存之间的频繁页面置换现像称为“抖动”。

以页面置换的频率的高低(缺页中断率)来衡量一个算法的优劣

31一月2023第98页OperatingSystem操作系统第五章存储管理(2)先进先出淘汰算法(FIFO算法)

总是选择在主存中居留时间最长(即最老)的一页淘汰。

先进入内存的页，先退出内存。实质上是淘汰在内存驻留时间最长的页。

其理由是：最早调入内存的页，不再被使用的可能性比近期调入内存的大。这种算法简单，实现容易。31一月2023第99页OperatingSystem操作系统第五章存储管理(3)最久未使用淘汰算法(LRU算法)

总是选择最长时间未被使用的那一页淘汰。依据的理论是如果某页被访问，它可能马上还要被访问；相反，如果某页长时间未被访问，它可能最近也不可能被访问。算法的实现（软件）：设置一个活动页面栈，当访问某页时，将此页号压入栈顶，然后，考察栈内是否有与此页面相同的页号，若有则抽出。淘汰一页时，总是从栈底抽出一个页号，它就是最久未使用的。31一月2023第100页OperatingSystem操作系统第五章存储管理

3.常用的淘汰算法

(1)理想型算法(OPT)算法

淘汰在将来再也不被访问或者是在最远的将来才被访问的页。此算法的缺页中断率是所有算法中最小的。由于程序在运行过程中无法对后面要使用的页面作出精确的断言，因此这个算法是无法实现的。但此算法可以用来作为衡量各种具体算法优劣的标准。

31一月2023第101页OperatingSystem操作系统第五章存储管理例:某作业有a,b,c,d四个页面,作业在运行过程中的访问次序为:a,b,c,a,d,a,试计算采用FIFO和LRU淘汰算法,各会产生几次缺页中断?(注：系统为该作业分配３个内存块)

缺页中断次数淘汰的页面进入主存的页面1-a2-b3-c4ad5ba缺页中断次数淘汰的页面进入主存的页面1-a2-b3-c4bdLRUFIFO31一月2023第102页OperatingSystem操作系统第五章存储管理例:若某进程分得4个内存块，现访问串有1、2、3、4、5、3、4、1、6、7、8、7、8、9、7、8、9、5、4、5、4、2，解答如下问题：

(1).求在FIFO算法下的页面缺页中断次数；

(2).求在LRU算法下的页面缺页中断数。31一月2023OperatingSystem操作系统第五章存储管理页面号√√√√√

√√√√

√

√√

√

1234534167878978954542B11111555555888888888882B2

22222211111199999999

B3

3333336666666665555

B4

444444777777777444

页面号√√√√√

√√√√

√

√√

√

1234534167878978954542B11111555566666666655552B2

22222211111199999999

B3

3333333777777777444

B4

444444488888888888

解：在FIFO算法LRU算法页面号√√√√√

√√√

√

√

√

1234534167878978954542B11111111111888888888882B2

222555555555555555555B3

33333367777777774444B4

4444444444999999999解：在OPT算法31一月2023OperatingSystem操作系统第五章存储管理例:设进程P共有8页，且已在内存中分配有3个页面，程序访问内存的顺序(访问串)为7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1。701203042303212017772222444000000000003332222211111111000333332227012030423032120177777333333333222000000444444444411111111000000022222222221111分配三个页面，缺页中断12次分配四个页面，缺页中断9次例:设进程P共有8页，且已在内存中分配有3个页面，程序访问内存的顺序(访问串)为7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1。按FIFO算法正常换页，计算缺页数和缺页率70120304230321201777222244400000000000333222221111111100033333222进程在一个执行过程中，实际上发生了17-5=12次缺页。如果设缺页率为缺页次数与访问串的访问次数之比则该例中的缺页率为12/17=70.5%。例：设进程P可分为5页，访问串为1，2，3，4，1，2，5，1，2，3，4，5。FIFO页面置换算法举例（非正常）分配三个页面，缺页中断9次分配四个页面，缺页中断10次123412512345111444555555222111113333332222244123412512345111111555544222222111153333332222444444333FIFO算法的Belady现象5.4.6页式管理的优缺点优点:(1)由于它不要求在内存中连续存放，从而有效地解决了外碎片问题。(2)提供了内存和外存统一管理的虚存实现方式，不需要为进程分配全部空间。主要缺点:(1)要求有相应的硬件支持。(2)增加了系统开销，例如缺页中断处理等。(3)请求调页的算法如选择不当，有可能产生抖动现象。(4)虽然消除了外碎片，但仍会出现内碎片。内存划分内存空间被动态的划分为若干个长度不相同的区域，称为物理段，每个物理段由起始地址和长度确定。内存分配以段为单位分配内存，每一个段在内存中占据连续空间（内存随机分割，需要多少分配多少），但各段之间可以不连续存放。5.5段式及段页式存储管理段式管理的基本思想是:把程序按内容或过程(函数)关系分成段，每段有自己的名字段式管理程序以段为单位分配内存，然后通过地址映射机构把段式虚拟地址转换成实际的内存物理地址31一月2023第112页OperatingSystem操作系统第五章存储管理

一.段式系统

1.什么是段分段是程序中自然划分的一组逻辑意义完整的信息集合。分段的例：代码分段、数据分段、栈段。

2.什么是段式系统

作业地址空间由若干逻辑分段组成,在内存中每个段占一个分区。31一月2023第113页OperatingSystem操作系统第五章存储管理段式管理的逻辑视图13241423用户空间物理内存...0S工作区段[B]主程序段[M]......0EP子程序段[X]0K...CALL[X][E].........CALL[Y][F]CALL[A]116......0FL子程序段[Y]0116N数组[A]12345...操作系统.....B0SA0NY0LX0PM0K逻辑段号01234进程的地址空间10003200500060008000PKSLN主存K3200P1500L6000N8000S5000长度段始址01234操作系统3.段式地址变换(1)段式地址结构(2)段表

段号s段内位移w段号始址长度存取方式内外访问位31一月2023第117页OperatingSystem操作系统第五章存储管理段表记录了段号，段的首（地）址和长度之间的关系；每一个程序设置一个段表，放在内存；属于进程的现场信息。图5.31段式地址变换过程31一月2023第119页OperatingSystem操作系统第五章存储管理(3)变换过程段式地址变换的步骤如下：取出程序地址(s，w)。用s检索段表。如w＜0或w≥l则主存越界。

(B＋w)即为所需主存地址。

长度基址

LB

sw

B+w第S段段号段内位移31一月2023第120页OperatingSystem操作系统第五章存储管理

L

B+段号S段内地址D比较SB+D段表S>=L快表物理地址段表始址寄存器段表长度寄存器逻辑地址SBSL...SSBSL地址越界D>=SL地址映射及存储保护机制地址越界比较S硬件支持系统设置一对寄存器段表始址寄存器：

用于保存正在运行进程的段表的始址段表长度寄存器：

用于保存正在运行进程的段表的长度

相联存储器——快表快表项目：段号；段始址；段长度；标识（状态）位；访问位（淘汰位）例：某段式存储管理系统中，有一作业的段表（SMT）如下表所示，求逻辑地址[0，65]，[1，55]，[2，