操作系统课件07主存管理

第七章主存管理（一）主存的共享方式（二）主存管理的功能（三）分区存储管理技术（四）页式存储管理技术（五）段式及段页式存储管理技术第七章主存管理（一）主存的共享方式2计算机系统存储结构2计算机系统存储结构内存管理的目的操作系统的“方便”性便于用户装入程序，无须了解底层细节可实现动态的存储空间伸缩，适应不同程序的需要操作系统的“合理”性合理分配内存空间，保证多道程序的顺利运行合理保护内存空间，防止各种可能的破坏泄漏操作系统的“有效性”有效保持内存空间的可用性，防止对资源的浪费有效实现“小空间大容量”，提高计算机的适应性有效配合CPU的调度过程，实现系统运行的稳定内存管理的目的操作系统的“方便”性（一）主存的共享方式内存储器（简称内存、主存、物理存储器）处理机能直接访问的存储器。用来存放系统和用户的程序和数据，其特点是存取速度快，断电信息丢失。（一）主存的共享方式内存储器（简称内存、主存、物理存储器）主存的共享方式包含三种：

大小不等的区域——

分区存储管理 分段存储管理大小相等的片——

页式存储管理两者结合 ——

段页式存储管理主存的共享方式包含三种：大小不等的区域——分区存储管理（二）主存管理的功能一.几个概念1、物理地址（绝对地址、实地址）：把内存分成若干个大小相等的存储单元，每个单元给一个编号，这个编号称为内存地址，是计算机主存单元的真实地址。存储单元占8位，称作字节（byte）。2.物理地址空间：物理地址的集合称为物理地址空间（主存地址空间），它是一个一维的线性空间。（二）主存管理的功能一.几个概念3.逻辑地址（相对地址、虚地址）:用户编程序时所用的地址。基本单位可与内存的基本单位相同，也可以不相同。4.逻辑地址空间（作业地址空间、虚地址空间）:用户的程序地址的集合称为逻辑地址空间，它的编址总是从0开始的。作业地址空间01n-13.逻辑地址（相对地址、虚地址）:作业地址空间01n-1二.主存管理的功能1.地址映射

将程序地址空间中使用的逻辑地址变换成主存中的地址的过程。2.主存分配

按照一定的算法把某一空闲的主存区分配给作业或进程。3.存储保护

保证用户程序(或进程映象)在各自的存储区域内操作，互不干扰。4.主存扩充（提供虚拟存储技术）

向用户提供一种不受物理存储器大小和结构限制的用户编程时使用的存储器。即使在用户程序比主存容量还要大的情况下，程序也能正确运行。二.主存管理的功能1.地址映射1.主存功能——地址映射主存空间01m-1作业1地址空间01n-1作业i地址空间01k-1┆

┆1.主存功能——地址映射主存空间01m-1作业1地址空间0（1）为什么要进行地址映射

作业的相应进程在处理机上运行时，所要访问的指令和数据的物理地址和作业地址空间中的地址是不同的。movr1,[500]123movr1,[500]123010050059901000110015001599256k-1作业地址空间存储空间将500号单元处的数据123送到寄存器r1中（1）为什么要进行地址映射0100500599010（2）地址映射的定义

将程序地址空间中使用的逻辑地址变换成主存中的地址的过程称为地址映射。有时也称为地址重定位。

（3）地址映射的方式编程或编译时确定地址映射关系静态地址映射动态地址映射（2）地址映射的定义静态地理映射定义：

在作业装入过程中随即进行的地址变换方式称为静态重定位或静态地址映射。movr1,[500]123movr1,[500+m]12301005005990mm+100256k-1作业地址空间存储空间m+500重定位装入程序静态地理映射定义：01005005990mm+100256动态地址映射定义：在程序运行时确定地址映射关系。在程序执行期间，随着每条指令和数据的访问自动地连续地进行地址映射。movr1,[500]1230100500599作业地址空间0

movr1,[500]1231000256k-1存储空间110015001600重定位寄存器

1000500逻辑地址+0100500599作业地址空间01000256k-1存储空静态地址映射与动态地址映射的区别静态地址映射动态地址映射在作业装入过程中进行地址映射在程序执行期间进行地址映射需软件变换机构重定位装入程序需硬件地址变换机构重定位装入程序需花费较多CPU时间地址变换快不灵活灵活静态地址映射与动态地址映射的区别静态地址映射动态地址映射在作构造分配用的数据结构主存资源信息块（M_RIB）、空闲区队列等等制定分配策略

2、主存功能——主存分配实施主存分配与回收构造分配用的数据结构2、主存功能——主存分配实施主存扩充也就是提供虚拟存储器

1）问题的提出3、主存扩充

物理存储器容量是有限的，用户程序的大小，可能比内存容量小，也可能比内存容量大，有时候要大得多。在主存容量十分紧张的情况下， 如何让用户使用计算机不受主存容量的限制？主存扩充也就是提供虚拟存储器3、主存扩充物理存储2）解决问题的思路

装入部分程序地址空间，它还能正确地执行？3）实现方法

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

将程序当前执行所涉及的那部分程序代码放入主存中；

程序执行时，当所需信息不在主存，由操作系统和硬件相配合来完成主存从辅存中调入信息，程序继续执行。

2）解决问题的思路4.什么是虚拟存储器

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

逻辑地址与物理地址分开

主存空间与地址空间分开

提供地址变换机构

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

有相当容量的辅存

足以存放多用户的作业的地址空间

有一定容量的主存

存放运行进程的当前信息

地址变换机构5.虚拟存储器的核心4、存储保护1）什么是存储保护

在多道程序设计的环境下，系统中有系统程序和多个用户程序同时存在，如何保证用户程序不破坏系统程序，用户程序之间不相互干扰？

——主存储器按区分配给各用户程序使用。为了互不影响，由硬件(软件配合)保证每道程序只能在给定的存储区域内活动，这种措施叫做存储保护。2）存储保护方法

通常的存储保护方法——

界地址保护和存储键保护（不介绍）4、存储保护1）什么是存储保护

(1)上、下界防护

movr1,[500]123020KB256KB1存储空间24KB下界寄存器

20KB上界寄存器

24KB下界寄存器：存放程序装入内存后的开始地址上界寄存器：存放程序装入内存后的末地址判别式：下界寄存器≤物理地址＜上界寄存器(1)上、下界防护

(2)基地址、限长防护

movr1,[500]123020KB256KB1存储空间24KB基址寄存器

20KB限长寄存器

4KB基址寄存器=下界寄存器

（首地址）限长寄存器：存放程序长度基址+限长=上界寄存器

（末地址）∴判别式：基址寄存器≤物理地址＜基址+限长寄存器(2)基地址、限长防护020KB256KB1存23作业第7章

第2题23作业第7章第2题（三）分区存储管理分区存储管理分为：1.固定分区2.动态分区（可变分区）（三）分区存储管理分区存储管理分为：25固定分区固定分区25固定分区固定分区一.动态分区分配1.什么是动态分区分配

在处理作业的过程中，建立分区，依用户请求的大小分配分区。思想：分区的大小、数量和位置随内存中进程的大小和数量动态变化（根据作业的实际需要在装入内存时动态地分配连续的内存空间）。一.动态分区分配

(1)动态分区的分配过程20KB

0

os

作业1

作业2

作业3

作业4

52KB66KB130KB230KB256KB1主存20KB

0

os

作业1

作业2

作业3

52KB66KB130KB256KB1主存20KB

0

os

作业1

52KB256KB1主存

0

os

256KB1主存20KB20KB

0

os

作业1

作业2

52KB66KB256KB1主存作业1申请

32KB作业2申请

14KB作业3申请

64KB作业4申请

100KB作业5申请

50KB(1)动态分区的分配过程20KB0o

(2)动态分区的回收过程20KB

0

os

作业1

作业2

作业3

作业4

52KB66KB130KB230KB256KB1主存20KB

0

os

作业1

作业3

作业4

52KB66KB130KB230KB256KB1主存作业2完成作业4完成20KB

0

os

作业1

作业3

52KB66KB130KB230KB256KB1主存(2)动态分区的回收过程20KB0o292、分区分配机构

1)主存资源信息块在动态分区方法中，描述主存资源的数据结构是主存资源信息块等待队列指针空闲区队列指针主存分配程序入口指针2)分区描述器和空闲队列主存中的每一个分区都有相应的分区描述器（pd）说明分区的特征信息。flag：为0—空闲区;为1—已分配区size：分区大小next：空闲区—自由主存队列中的勾链字;已分配区—此项为零m_ribpd分配标志flag分区大小size勾链字next292、分区分配机构等待队列指针空闲区队列指针主存分配程序入30自由主存队列(或空闲区队列)结构在主存分配中，主要讨论空闲区描述器和空闲区队列。下面是在t时刻的主存分布、空闲区描述器的内容和空闲区队列结构。

020KB

os

作业1

作业3

作业4

52KB66KB130KB230KB256KB1主存52KBm-rib

014KB230KB

026KB

空闲区队列结构 空闲区表的组织有两种方法：

1、按空闲区大小的升序（降序）组织；

2、按空闲区首址升序（降序）组织。30自由主存队列(或空闲区队列)结构020KB3、分区的分配与放置策略1）分区分配

•

用户请求分配一个主存块

•

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

•

若找到，则返回所分配区域的首址，否则，告之不能满足要求。3、分区的分配与放置策略1）分区分配2）放置策略

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

空闲区表的组织有两种方法：

1、按空闲区大小的升序（降序）组织；

2、按空闲区首址升序（降序）组织。

根据空闲区表组织的方法的不同，有不同的放置策略：首次适应算法、最佳适应算法和最坏适应算法三种。2）放置策略33

1）首次适应算法

空闲区按起始地址递增的顺序排列，将作业放到最先找到的空闲分区。331）首次适应算法34

2）最佳适应算法

空闲区按由小到大的顺序排列，将作业放到满足要求的最小的空闲分区。

342）最佳适应算法35

3）最坏适应算法

空闲区按由大到小的顺序排列，将作业放到满足要求的最大的空闲分区。353）最坏适应算法几种放置策略的比较

例如：某时刻系统中有三个空闲区，其大小和首址为：(35KB，100KB)、(12KB，156KB)、(28KB，200KB)

有一作业系列：

(JOB1，12KB)、(JOB2，30KB)、(JOB3，28KB)

用首次适应算法、最佳适应算法和最坏适应算法来处理该作业序列，看哪种算法合适？注：设分配时从空闲区的高地址分割，以保持剩余空闲区的起始地址不变。

os在使用在使用在使用在使用12KB28KB0KB100KB35KB156KB200KB228KB-1几种放置策略的比较 例如：某时刻系统中有三个空闲区，其大小和035KB156KB首次适应算法012KB200KB028KBNULL100KB作业1（12KB）放到首址100KB的空闲区023KB156KB012KB200KB028KBNULL100KB作业2（30KB）不能分配作业3（28KB）放到首址200KB的空闲区035KB156KB首次适应算法012KB200KB028K012KB200KB最佳适应算法028KB100KB035KBNULL156KB作业1（12KB）放到首址156KB的空闲区028KB100KB035KBNULL200KB作业2（30KB）放到首址100KB的空闲区作业3（28KB）放到首址200KB的空闲区05KB200KB028KBNULL100KB012KB200KB最佳适应算法028KB100KB035K035KB200KB最坏适应算法028KB156KB012KBNULL100KB作业1（12KB）放到首址100KB的空闲区作业2（30KB）不能继续分配作业3（28KB）放到首址200KB的空闲区028KB100KB023KB156KB012KBNULL200KB035KB200KB最坏适应算法028KB156KB012K四、碎片问题及拼接技术1.什么是碎片问题

在已分配区之间存在着的一些没有被充分利用的空闲区。

如何解决碎片问题？2.拼接技术

所谓拼接技术是指移动存储器中某些已分配区中的信息，使本来分散的空闲区连成一个大的空闲区。四、碎片问题及拼接技术1.什么是碎片问题41OS400KBJOB1(100KB)JOB2(200KB)0300KBJOB6(100KB)800KB700KB900KBJOB5(100KB)JOB4(100KB)JOB7(100KB)600KB1000KB1024KBOS400KBJOB2(200KB)0300KBJOB6(100KB)800KB700KB900KBJOB5(100KB)JOB4(100KB)JOB7(100KB)600KB1000KB空闲(24KB)1024KB空闲(100KB)OS400KBJOB2(200KB)0300KB800KB700KB900KBJOB5(100KB)JOB7(100KB)600KB1000KB空闲(24KB)1024KB空闲(100KB)空闲(100KB)空闲(100KB)有一大小为200K的作业需要运行!!!空闲(24KB)41OS400KBJOB1(100KB)JOB2(200KB分区管理的优缺点优点：实现了多道程序共享主存。实现分区管理的系统设计相对简单，不需要更多的系统软硬件开销。实现存储保护的手段也比较简单。缺点：主存利用不够充分。系统中总有一部分存储空间得不到利用，这部分被浪费的空间叫碎片。没有实现主存的扩充问题。当作业的地址空间大于存储空间时，作业无法运行。也即作业的地址空间受实际存储空间限制。分区管理的优缺点优点：（四）页式存储管理一.问题的提出

分区存储管理的主要问题是碎片问题。 在采用分区存储管理的系统中，会形成一些非常小的分区，最终这些非常小的分区不能被系统中的任何用户（程序）利用而浪费。 造成这样问题的主要原因是用户程序装入内存时是整体装入的，为解决这个问题，提出了分页存储管理技术。（四）页式存储管理一.问题的提出二.页式系统的基本概念1.页面

程序的地址空间被等分成大小相等的片，称为页面，又称为虚页。2.主存块

主存被等分成大小相等的片，称为主存块，又称为实页。二.页式系统的基本概念1.页面

作业页面与主存块的关系02KB4KB254KB256KB102KB4KB6KB0页1页2页3页主存作业地址空间页表地址映射作业页面与主存块的关系02KB4KB254KB23.页表（1）什么是页表

为了实现从地址空间到物理主存的映象，系统建立的记录页与内存块之间对应关系的地址变换的机构称为页面映像表，简称页表。包括用户程序空间的页面与内存块的对应关系、页面的存储保护和存取控制方面的信息。3.页表（1）什么是页表01KB01KB2KB3KB1主存作业2地址空间2KB3KB4KB5KB6KB7KB8KB9KB10KB101KB2KB1作业1地址空间01KB1作业3地址空间0516页号块号02140827作业1页表作业2页表作业3页表osos01KB01KB2KB3KB1主存作业2地址空间2KB3K三.页式地址变换1.虚地址结构

虚地址是用户程序中的逻辑地址，它包括页号和页内地址（页内位移）。 区分页号和页内地址的依椐是页的大小，页内地址占虚地址的低位部分，页号占虚地址的高位部分。

【例】设虚地址长度为16位，页面大小为1KB： 页号页内地址（位移量）

PW 151090三.页式地址变换49如何方便将逻辑地址线性分割求出页号P和页内位移W：逻辑地址以十进制数给出：

页号P=逻辑地址%页大小 页内位移W=逻辑地址mod页大小逻辑地址以十六进制、八进制、二进制的形式给出：将逻辑地址转换成二进制；按页的大小分离出页号P和位移量W（低位部分是位移量，高位部分是页号）；49如何方便将逻辑地址线性分割求出页号P和页内位移W：50【例】：有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB。解：求虚地址3412P＝3412％2048＝1W＝3412mod2048＝1364求虚地址7145：P＝7145％2048＝3W＝7145mod2048＝100150【例】：有一系统采用页式存储管理，有一作业大小是8KB，51【例】：有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB。虚地址0AFEH：0000

101011111110P＝1W＝01011111110虚地址1ADDH：0001101011011101P＝3W＝0101101110151【例】：有一系统采用页式存储管理，有一作业大小是8KB，例1页面大小是1KB，虚地址是3BADH例2页面大小是2KB，虚地址是3BADH例1页面大小是1KB，虚地址是3BADH532、地址变换根据逻辑地址求物理地址的步骤：1）将逻辑地址线性分割求出页号P和页内位移W：2）根据页号查页表得块号B；3）物理地址=块号B×页大小+页内位移W532、地址变换54页表始址寄存器movr1,[2500]12301KB2KB3KB1作业2地址空间+021427页表0000100111000100151090页号页内位移W250001KB主存2KB3KB4KB5KB6KB7KB8KB9KB10KB1ososmovr1,[2500]123第1页块号块内位移W

15109000011101110001007×1024+452=762054页表始址寄存器movr1,01KB2KB3KB155【例】：有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、10、5块，试将虚地址7145，3412转换成内存地址。解：求虚地址3412P＝3412％2048＝1W＝3412mod2048＝1364MR=9*2048+1364=19796求虚地址7145：P＝7145％2048＝3W＝7145mod2048＝1001MR=5*2048+1001=1124155【例】：有一系统采用页式存储管理，有一作业大小是8KB，56【例】：有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、A、5块，试将虚地址0AFEH，1ADDH转换成内存地址。解：求虚地址0AFEH的物理地址：0000

101011111110P＝1W＝01011111110MR＝0100

1010

11111110＝4AFEH求虚地址1ADDH的物理地址：0001101011011101P＝3W＝01011011101MR＝00101010

11011101＝2ADDH56【例】：有一系统采用页式存储管理，有一作业大小是8KB，57课堂练习：1、某作业J的逻辑空间为4页，每页2048B，已知该作业J的页表如下： 页号：0123

块号：2468

求：逻辑地址为0A65H的物理地址。2、某作业有4个页面，分别装入主存的3、4、6、8块中，设页面尺寸为1024B（1）、写出该作业的页表；（2）、求mov2100,3100指令中两个操作数的物理地址。57课堂练习：四.请调策略1、请调策略定义：

在页式系统中，允许一个作业程序只装入部分页面即可投入运行，需要信息时动态调入，这种装入信息的策略称为请调策略。

(1)怎样发现所访问的页面在不在主存？

(2)当发现所需访问的页面不在主存时如何处理?四.请调策略1、请调策略定义：2.扩充页表功能

中断位i——标识该页是否在主存 若i=1，表示此页不在主存 若i=0，表示该页在主存

辅存地址——该页面在辅存的位置

页号主存块号中断位辅存地址页号主存块号中断位辅存地址

3.缺页处理过程（举例说明）

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

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

006802

3KB3.缺页处理过程（举例说明）01KB主存2KB3作业2的主存块数为m2=3，页面大小为1KB。

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

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

查页表。该页中断位i=1，则发生缺页中断01KB2KB4KB1作业2地址空间movr1,[2120]addr1,[3410]006251

006802

3KB

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

m，则需淘汰该作业在主存中的一页（其中n代表作业已分配到的主存块数，m为内存为作业准备的物理块数）。01KB2KB4KB1作业2地址空间movr1,[212缺页处理流程

启动要处理的指令给出虚地址

得到页号该页在主存?有空闲块?

缺页中断执行完该指令

准备执行下条指令选一页淘汰

从外存读入所需的页

调整存储分配表和页表

重新启动被中断的指令

调整存储分配表和页表要重写入?该页写入外存YNNY硬件软件YN缺页处理流程启动要处理的指令给出虚地址得到4.淘汰策略1.什么是淘汰策略

用来选择淘汰哪一页的规则就叫做置换策略，或称淘汰算法。常用算法：1、最优算法OPT:(optimalreplacementalgorithm)置换在最长时间内不会使用的页)2、先进先出算法FIFO：淘汰先调入内存的页3、最近最少使用淘汰算法LRU：淘汰未被访问的页中时间最长的页;(LeastRecentlyUsed)

使用缺页中断率f’衡量页面淘汰算法的优劣：

f’＝f／a（a是总的页面访问次数，f是缺页中断次数）4.淘汰策略1.什么是淘汰策略2.扩充页表的功能页表应增加相应的内容，反映该页是否在内存，在外存的位置，在内存的时间的长短等。

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

1表示最近有进程访问

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

1该页调入内存后修改过页号主存块号中断位辅存地址改变位引用位2.扩充页表的功能页表应增加相应的内容，反映该页是否在内存3.颠簸颠簸(thrashing)，又称为“抖动”。

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

3.颠簸颠簸(thrashing)，又称为“抖动”。OPT原理（难实现）：当要调入一新页而必须先淘汰一旧页时，所淘汰的那一页应是以后不再要用的，或者是在最长的时间以后才会用到的那页。

缺页率

假定程序p共有n页，系统分配m块，有1≤m≤n若程序p在运行中:成功的访问次数：s

不成功的访问次数：f

则缺页中断率：f′=f/(s+f)*100%f′=f(r，m，p)

4.页面置换算法——OPT算法4.页面置换算法——OPT算法例：假设系统为某进程分配了3个物理块，并考虑有以下的访问串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1，求缺页率。7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1缺页率f′=(9/20)*100%=45%例：假设系统为某进程分配了3个物理块，并考虑有以下的访问串：

(2)先进先出淘汰算法(FIFO算法)1)什么是先进先出淘汰算法原理：总是选择在主存中居留时间最长(即最老)的一页淘汰。

2)先进先出淘汰算法的实现方法

建立一个页面进入主存的先后次序表；

建立一个替换指针，指向最早进入主存的页面；

当需要置换一页时，选择替换指向的那一页，然

后调整替换指针的内容。

69【例】某进程的页面访问序列：1、2、3、4、1、2、5、1、2、3、4、5，指出在驻留集大小分别为3和4时，使用FIFO置换算法的缺页率，结果说明了什么？（设驻留集M表示分给该作业的内存块数）解：FIFO

M＝3f’＝

f／a＝9／12＝75% M＝4f’＝10／12≈83%

69【例】某进程的页面访问序列：1、2、3、4、1、2、5、70123412512345t11111111222222223333334444455555512512341251345t1114334522244511332334432455122232234151112采用FIFO算法70123412512345t111111112222222

(3)最久未使用淘汰算法(LRU算法)总是选择最长时间未被使用的那一页淘汰。

LRU算法的实现方法

用引用位考察页面的使用情况；

当访问页面时，将引用位置1，并记时；

当要淘汰一页时，选择时间最长的一页淘汰。要精确实现很困难硬件方法：采用寄存器（计时法）软件方法：采用页号栈(3)最久未使用淘汰算法(LRU算法)72【例】某进程的页面访问序列：1、2、3、4、1、2、5、1、2、3、4、5，指出在驻留集大小分别为3和4时，使用LRU置换算法的缺页率，？（设驻留集M表示分给该作业的内存块数）解：

LRU

M＝3f’＝

f／a＝10／12≈83%M＝4f’＝

f／a＝8／12≈67%

72【例】某进程的页面访问序列：1、2、3、4、1、2、5、73123412512345t1111112522222511333334444455122231212341251345t1111112522222511333334444455122232444152312采用LRU算法73123412512345t111111252222251练习在分页虚拟存储管理系统中，假设系统为某进程分配了四个主存块（将开始4页先装入主存），进程执行时页的引用顺序为：7,1,2,0,3,0,4,2,3,0,3,2,7,0,1，求分别采用OPT、FIFO、LRU算法计算产生多少次缺页中断？产生多少次缺页置换？依次淘汰的页是什么？缺页率为多少？练习在分页虚拟存储管理系统中，假设系统为某进程分配了四个主第七章主存管理（一）主存的共享方式（二）主存管理的功能（三）分区存储管理技术（四）页式存储管理技术（五）段式及段页式存储管理技术第七章主存管理（一）主存的共享方式76计算机系统存储结构2计算机系统存储结构内存管理的目的操作系统的“方便”性便于用户装入程序，无须了解底层细节可实现动态的存储空间伸缩，适应不同程序的需要操作系统的“合理”性合理分配内存空间，保证多道程序的顺利运行合理保护内存空间，防止各种可能的破坏泄漏操作系统的“有效性”有效保持内存空间的可用性，防止对资源的浪费有效实现“小空间大容量”，提高计算机的适应性有效配合CPU的调度过程，实现系统运行的稳定内存管理的目的操作系统的“方便”性（一）主存的共享方式内存储器（简称内存、主存、物理存储器）处理机能直接访问的存储器。用来存放系统和用户的程序和数据，其特点是存取速度快，断电信息丢失。（一）主存的共享方式内存储器（简称内存、主存、物理存储器）主存的共享方式包含三种：

大小不等的区域——

分区存储管理 分段存储管理大小相等的片——

页式存储管理两者结合 ——

段页式存储管理主存的共享方式包含三种：大小不等的区域——分区存储管理（二）主存管理的功能一.几个概念1、物理地址（绝对地址、实地址）：把内存分成若干个大小相等的存储单元，每个单元给一个编号，这个编号称为内存地址，是计算机主存单元的真实地址。存储单元占8位，称作字节（byte）。2.物理地址空间：物理地址的集合称为物理地址空间（主存地址空间），它是一个一维的线性空间。（二）主存管理的功能一.几个概念3.逻辑地址（相对地址、虚地址）:用户编程序时所用的地址。基本单位可与内存的基本单位相同，也可以不相同。4.逻辑地址空间（作业地址空间、虚地址空间）:用户的程序地址的集合称为逻辑地址空间，它的编址总是从0开始的。作业地址空间01n-13.逻辑地址（相对地址、虚地址）:作业地址空间01n-1二.主存管理的功能1.地址映射

将程序地址空间中使用的逻辑地址变换成主存中的地址的过程。2.主存分配

按照一定的算法把某一空闲的主存区分配给作业或进程。3.存储保护

保证用户程序(或进程映象)在各自的存储区域内操作，互不干扰。4.主存扩充（提供虚拟存储技术）

向用户提供一种不受物理存储器大小和结构限制的用户编程时使用的存储器。即使在用户程序比主存容量还要大的情况下，程序也能正确运行。二.主存管理的功能1.地址映射1.主存功能——地址映射主存空间01m-1作业1地址空间01n-1作业i地址空间01k-1┆

┆1.主存功能——地址映射主存空间01m-1作业1地址空间0（1）为什么要进行地址映射

作业的相应进程在处理机上运行时，所要访问的指令和数据的物理地址和作业地址空间中的地址是不同的。movr1,[500]123movr1,[500]123010050059901000110015001599256k-1作业地址空间存储空间将500号单元处的数据123送到寄存器r1中（1）为什么要进行地址映射0100500599010（2）地址映射的定义

将程序地址空间中使用的逻辑地址变换成主存中的地址的过程称为地址映射。有时也称为地址重定位。

（3）地址映射的方式编程或编译时确定地址映射关系静态地址映射动态地址映射（2）地址映射的定义静态地理映射定义：

在作业装入过程中随即进行的地址变换方式称为静态重定位或静态地址映射。movr1,[500]123movr1,[500+m]12301005005990mm+100256k-1作业地址空间存储空间m+500重定位装入程序静态地理映射定义：01005005990mm+100256动态地址映射定义：在程序运行时确定地址映射关系。在程序执行期间，随着每条指令和数据的访问自动地连续地进行地址映射。movr1,[500]1230100500599作业地址空间0

movr1,[500]1231000256k-1存储空间110015001600重定位寄存器

1000500逻辑地址+0100500599作业地址空间01000256k-1存储空静态地址映射与动态地址映射的区别静态地址映射动态地址映射在作业装入过程中进行地址映射在程序执行期间进行地址映射需软件变换机构重定位装入程序需硬件地址变换机构重定位装入程序需花费较多CPU时间地址变换快不灵活灵活静态地址映射与动态地址映射的区别静态地址映射动态地址映射在作构造分配用的数据结构主存资源信息块（M_RIB）、空闲区队列等等制定分配策略

2、主存功能——主存分配实施主存分配与回收构造分配用的数据结构2、主存功能——主存分配实施主存扩充也就是提供虚拟存储器

1）问题的提出3、主存扩充

物理存储器容量是有限的，用户程序的大小，可能比内存容量小，也可能比内存容量大，有时候要大得多。在主存容量十分紧张的情况下， 如何让用户使用计算机不受主存容量的限制？主存扩充也就是提供虚拟存储器3、主存扩充物理存储2）解决问题的思路

装入部分程序地址空间，它还能正确地执行？3）实现方法

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

将程序当前执行所涉及的那部分程序代码放入主存中；

程序执行时，当所需信息不在主存，由操作系统和硬件相配合来完成主存从辅存中调入信息，程序继续执行。

2）解决问题的思路4.什么是虚拟存储器

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

逻辑地址与物理地址分开

主存空间与地址空间分开

提供地址变换机构

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

有相当容量的辅存

足以存放多用户的作业的地址空间

有一定容量的主存

存放运行进程的当前信息

地址变换机构5.虚拟存储器的核心4、存储保护1）什么是存储保护

在多道程序设计的环境下，系统中有系统程序和多个用户程序同时存在，如何保证用户程序不破坏系统程序，用户程序之间不相互干扰？

——主存储器按区分配给各用户程序使用。为了互不影响，由硬件(软件配合)保证每道程序只能在给定的存储区域内活动，这种措施叫做存储保护。2）存储保护方法

通常的存储保护方法——

界地址保护和存储键保护（不介绍）4、存储保护1）什么是存储保护

(1)上、下界防护

movr1,[500]123020KB256KB1存储空间24KB下界寄存器

20KB上界寄存器

24KB下界寄存器：存放程序装入内存后的开始地址上界寄存器：存放程序装入内存后的末地址判别式：下界寄存器≤物理地址＜上界寄存器(1)上、下界防护

(2)基地址、限长防护

movr1,[500]123020KB256KB1存储空间24KB基址寄存器

20KB限长寄存器

4KB基址寄存器=下界寄存器

（首地址）限长寄存器：存放程序长度基址+限长=上界寄存器

（末地址）∴判别式：基址寄存器≤物理地址＜基址+限长寄存器(2)基地址、限长防护020KB256KB1存97作业第7章

第2题23作业第7章第2题（三）分区存储管理分区存储管理分为：1.固定分区2.动态分区（可变分区）（三）分区存储管理分区存储管理分为：99固定分区固定分区25固定分区固定分区一.动态分区分配1.什么是动态分区分配

在处理作业的过程中，建立分区，依用户请求的大小分配分区。思想：分区的大小、数量和位置随内存中进程的大小和数量动态变化（根据作业的实际需要在装入内存时动态地分配连续的内存空间）。一.动态分区分配

(1)动态分区的分配过程20KB

0

os

作业1

作业2

作业3

作业4

52KB66KB130KB230KB256KB1主存20KB

0

os

作业1

作业2

作业3

52KB66KB130KB256KB1主存20KB

0

os

作业1

52KB256KB1主存

0

os

256KB1主存20KB20KB

0

os

作业1

作业2

52KB66KB256KB1主存作业1申请

32KB作业2申请

14KB作业3申请

64KB作业4申请

100KB作业5申请

50KB(1)动态分区的分配过程20KB0o

(2)动态分区的回收过程20KB

0

os

作业1

作业2

作业3

作业4

52KB66KB130KB230KB256KB1主存20KB

0

os

作业1

作业3

作业4

52KB66KB130KB230KB256KB1主存作业2完成作业4完成20KB

0

os

作业1

作业3

52KB66KB130KB230KB256KB1主存(2)动态分区的回收过程20KB0o1032、分区分配机构

1)主存资源信息块在动态分区方法中，描述主存资源的数据结构是主存资源信息块等待队列指针空闲区队列指针主存分配程序入口指针2)分区描述器和空闲队列主存中的每一个分区都有相应的分区描述器（pd）说明分区的特征信息。flag：为0—空闲区;为1—已分配区size：分区大小next：空闲区—自由主存队列中的勾链字;已分配区—此项为零m_ribpd分配标志flag分区大小size勾链字next292、分区分配机构等待队列指针空闲区队列指针主存分配程序入104自由主存队列(或空闲区队列)结构在主存分配中，主要讨论空闲区描述器和空闲区队列。下面是在t时刻的主存分布、空闲区描述器的内容和空闲区队列结构。

020KB

os

作业1

作业3

作业4

52KB66KB130KB230KB256KB1主存52KBm-rib

014KB230KB

026KB

空闲区队列结构 空闲区表的组织有两种方法：

1、按空闲区大小的升序（降序）组织；

2、按空闲区首址升序（降序）组织。30自由主存队列(或空闲区队列)结构020KB3、分区的分配与放置策略1）分区分配

•

用户请求分配一个主存块

•

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

•

若找到，则返回所分配区域的首址，否则，告之不能满足要求。3、分区的分配与放置策略1）分区分配2）放置策略

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

空闲区表的组织有两种方法：

1、按空闲区大小的升序（降序）组织；

2、按空闲区首址升序（降序）组织。

根据空闲区表组织的方法的不同，有不同的放置策略：首次适应算法、最佳适应算法和最坏适应算法三种。2）放置策略107

1）首次适应算法

空闲区按起始地址递增的顺序排列，将作业放到最先找到的空闲分区。331）首次适应算法108

2）最佳适应算法

空闲区按由小到大的顺序排列，将作业放到满足要求的最小的空闲分区。

342）最佳适应算法109

3）最坏适应算法

空闲区按由大到小的顺序排列，将作业放到满足要求的最大的空闲分区。353）最坏适应算法几种放置策略的比较

例如：某时刻系统中有三个空闲区，其大小和首址为：(35KB，100KB)、(12KB，156KB)、(28KB，200KB)

有一作业系列：

(JOB1，12KB)、(JOB2，30KB)、(JOB3，28KB)

用首次适应算法、最佳适应算法和最坏适应算法来处理该作业序列，看哪种算法合适？注：设分配时从空闲区的高地址分割，以保持剩余空闲区的起始地址不变。

os在使用在使用在使用在使用12KB28KB0KB100KB35KB156KB200KB228KB-1几种放置策略的比较 例如：某时刻系统中有三个空闲区，其大小和035KB156KB首次适应算法012KB200KB028KBNULL100KB作业1（12KB）放到首址100KB的空闲区023KB156KB012KB200KB028KBNULL100KB作业2（30KB）不能分配作业3（28KB）放到首址200KB的空闲区035KB156KB首次适应算法012KB200KB028K012KB200KB最佳适应算法028KB100KB035KBNULL156KB作业1（12KB）放到首址156KB的空闲区028KB100KB035KBNULL200KB作业2（30KB）放到首址100KB的空闲区作业3（28KB）放到首址200KB的空闲区05KB200KB028KBNULL100KB012KB200KB最佳适应算法028KB100KB035K035KB200KB最坏适应算法028KB156KB012KBNULL100KB作业1（12KB）放到首址100KB的空闲区作业2（30KB）不能继续分配作业3（28KB）放到首址200KB的空闲区028KB100KB023KB156KB012KBNULL200KB035KB200KB最坏适应算法028KB156KB012K四、碎片问题及拼接技术1.什么是碎片问题

在已分配区之间存在着的一些没有被充分利用的空闲区。

如何解决碎片问题？2.拼接技术

所谓拼接技术是指移动存储器中某些已分配区中的信息，使本来分散的空闲区连成一个大的空闲区。四、碎片问题及拼接技术1.什么是碎片问题115OS400KBJOB1(100KB)JOB2(200KB)0300KBJOB6(100KB)800KB700KB900KBJOB5(100KB)JOB4(100KB)JOB7(100KB)600KB1000KB1024KBOS400KBJOB2(200KB)0300KBJOB6(100KB)800KB700KB900KBJOB5(100KB)JOB4(100KB)JOB7(100KB)600KB1000KB空闲(24KB)1024KB空闲(100KB)OS400KBJOB2(200KB)0300KB800KB700KB900KBJOB5(100KB)JOB7(100KB)600KB1000KB空闲(24KB)1024KB空闲(100KB)空闲(100KB)空闲(100KB)有一大小为200K的作业需要运行!!!空闲(24KB)41OS400KBJOB1(100KB)JOB2(200KB分区管理的优缺点优点：实现了多道程序共享主存。实现分区管理的系统设计相对简单，不需要更多的系统软硬件开销。实现存储保护的手段也比较简单。缺点：主存利用不够充分。系统中总有一部分存储空间得不到利用，这部分被浪费的空间叫碎片。没有实现主存的扩充问题。当作业的地址空间大于存储空间时，作业无法运行。也即作业的地址空间受实际存储空间限制。分区管理的优缺点优点：（四）页式存储管理一.问题的提出

分区存储管理的主要问题是碎片问题。 在采用分区存储管理的系统中，会形成一些非常小的分区，最终这些非常小的分区不能被系统中的任何用户（程序）利用而浪费。 造成这样问题的主要原因是用户程序装入内存时是整体装入的，为解决这个问题，提出了分页存储管理技术。（四）页式存储管理一.问题的提出二.页式系统的基本概念1.页面

程序的地址空间被等分成大小相等的片，称为页面，又称为虚页。2.主存块

主存被等分成大小相等的片，称为主存块，又称为实页。二.页式系统的基本概念1.页面

作业页面与主存块的关系02KB4KB254KB256KB102KB4KB6KB0页1页2页3页主存作业地址空间页表地址映射作业页面与主存块的关系02KB4KB254KB23.页表（1）什么是页表

为了实现从地址空间到物理主存的映象，系统建立的记录页与内存块之间对应关系的地址变换的机构称为页面映像表，简称页表。包括用户程序空间的页面与内存块的对应关系、页面的存储保护和存取控制方面的信息。3.页表（1）什么是页表01KB01KB2KB3KB1主存作业2地址空间2KB3KB4KB5KB6KB7KB8KB9KB10KB101KB2KB1作业1地址空间01KB1作业3地址空间0516页号块号02140827作业1页表作业2页表作业3页表osos01KB01KB2KB3KB1主存作业2地址空间2KB3K三.页式地址变换1.虚地址结构

虚地址是用户程序中的逻辑地址，它包括页号和页内地址（页内位移）。 区分页号和页内地址的依椐是页的大小，页内地址占虚地址的低位部分，页号占虚地址的高位部分。

【例】设虚地址长度为16位，页面大小为1KB： 页号页内地址（位移量）

PW 151090三.页式地址变换123如何方便将逻辑地址线性分割求出页号P和页内位移W：逻辑地址以十进制数给出：

页号P=逻辑地址%页大小 页内位移W=逻辑地址mod页大小逻辑地址以十六进制、八进制、二进制的形式给出：将逻辑地址转换成二进制；按页的大小分离出页号P和位移量W（低位部分是位移量，高位部分是页号）；49如何方便将逻辑地址线性分割求出页号P和页内位移W：124【例】：有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB。解：求虚地址3412P＝3412％2048＝1W＝3412mod2048＝1364求虚地址7145：P＝7145％2048＝3W＝7145mod2048＝100150【例】：有一系统采用页式存储管理，有一作业大小是8KB，125【例】：有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB。虚地址0AFEH：0000

101011111110P＝1W＝01011111110虚地址1ADDH：0001101011011101P＝3W＝0101101110151【例】：有一系统采用页式存储管理，有一作业大小是8KB，例1页面大小是1KB，虚地址是3BADH例2页面大小是2KB，虚地址是3BADH例1页面大小是1KB，虚地址是3BADH1272、地址变换根据逻辑地址求物理地址的步骤：1）将逻辑地址线性分割求出页号P和页内位移W：2）根据页号查页表得块号B；3）物理地址=块号B×页大小+页内位移W532、地址变换128页表始址寄存器movr1,[2500]12301KB2KB3KB1作业2地址空间+021427页表0000100111000100151090页号页内位移W250001KB主存2KB3KB4KB5KB6KB7KB8KB9KB10KB1ososmovr1,[2500]123第1页块号块内位移W

15109000011101110001007×1024+452=762054页表始址寄存器movr1,01KB2KB3KB1129【例】：有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、10、5块，试将虚地址7145，3412转换成内存地址。解：求虚地址3412P＝3412％2048＝1W＝3412mod2048＝1364MR=9*2048+1364=19796求虚地址7145：P＝7145％2048＝3W＝7145mod2048＝1001MR=5*2048+1001=1124155【例】：有一系统采用页式存储管理，有一作业大小是8KB，130【例】：有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、A、5块，试将虚地址0AFEH，1ADDH转换成内存地址。解：求虚地址0AFEH的物理地址：0000

101011111110P＝1W＝01011111110MR＝0100

1010

11111110＝4AFEH求虚地址1ADDH的物理地址：0001101011011101P＝3W＝01011011101MR＝00101010

11011101＝2ADDH56【例】：有一系统采用页式存储管理，有一作业大小是8KB，131课堂练习：1、某作业J的逻辑空间为4页，每页2048B，已知该作业J的页表如下： 页号：0123

块号：2468

求：逻辑地址为0A65H的物理地址。2、某作业有4个页面，分别装入主存的3、4、6、8块中，设页面尺寸为1024B（1）、写出该作业的页表；（2）、求mov2100,3100指令中两个操作数的物理地址。57课堂练习：四.请调策略1、请调策略定义：

在页式系统中，允许一个作业程序只装入部分页面即可投入运行，需要信息时动态调入，这种装入信息的策略称为请调策略。

(1)怎样发现所访问的页面在不在主存？

(2)当发现所需访问的页面不在主存时如何处理?四.请调策略1、请调策略定义：2.扩充页表功能

中断位i——标识该页是否在主存 若i=1，表示此页不在主存 若i=0，表示该页在主存

辅存地址——该页面在辅存的位置

页号主存块号中断位辅存地址页号主存块号中断位辅存地址

3.缺页处理过程（举例说明）

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

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

006802

3KB3.缺页处理过程（举例说明）01KB主存2KB3作业2的主存块数为m2=3，页面大小为1KB。

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

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

查页表。该页中断位i=1，则发生缺页中断01KB2KB4KB1作业2地址空间movr1,[2120]addr1,[3410]006251

006802

3KB

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

m，则需淘汰该作业在主存中的一页（其中n代表作业已分配到的主存块数，m为内存为作业准备的物理块数）。01KB2KB4KB1作业2地址空间movr1,[212缺页处理流程

启动要处理的指令给出虚地址

得到页号该页在主存?有空闲块?

缺页中断执行完该指令

准备执行下条指令选一页淘汰

从外存读入所需的页

调整存储分配表和