操作系统原理 第7章 主存管理

1(一)

主存的共享方式

(二)

主存管理的功能

(三)分区存储管理技术

(四)

页式存储管理技术

(五)

段式及段页式存储管理技术第七章主存管理2

(一)主存的共享方式主存共享方式——空间分片

大小不等的区域——分区存储管理分段存储管理

大小相等的片——页式存储管理

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

(二)主存管理功能一.几个概念

1.物理地址(绝对地址、实地址)

物理地址是计算机主存单元的真实地址，又称为绝对地址或实地址。

2.主存空间物理地址的集合所对应的空间组成了主存空间。

3.区域物理地址集合的一个递增整数序列子集n，n+1，┄，n＋m所对应的主存空间。4

4.逻辑地址(相对地址、虚地址)

用户的程序地址(指令地址或操作数地址)均为逻辑地址。

5.作业地址空间

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

6.作业地址空间与主存空间主存空间01m-1作业1地址空间01n-1作业i地址空间01k-1

┇

┇6

二.主存管理功能

1.实现逻辑地址到物理主存地址的映射

2.主存分配

3.存储保护

4.主存扩充7

三.主存映射

1.什么是地址映射

(1)为什么要进行地址映射作业的相应进程在处理机上运行时，所要访问的指令和数据的实际地址和作业地址空间中的地址是不同的。这种情况可用图7.1来说明。movr1,[500]123movr1,[500]123010050059901000110015001599256k-1作业地址空间存储空间8

(2)什么是地址映射将程序地址空间中使用的逻辑地址变换成主存中的物理地址的过程，称为地址映射。

2.地址映射的时机与类别

(1)编程或编译时确定地址映射关系在程序编写或程序编译时确定虚、实地址之间的对应关系，结果是一个不能浮动的程序模块。9

(2)在作业装入时确定地址映射关系——静态地址映射在作业装入过程中随即进行的地址变换方式称为静态重定位或静态地址映射。movr1,[500]1230100500599作业地址空间重定位装入程序movr1,[500+m]256k-1存储空间0mm+100m+50012310

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

movr1,[500]123存储空间01000256k-1110015001600作业地址空间0100500599逻辑地址重定位寄存器1000500+11

3.静态地址映射与动态地址映射的区别

静态地址映射动态地址映射

在作业装入过程中在程序执行期间进行地址映射进行地址映射

需软件需硬件地址变换机构重定位装入程序重定位寄存器

需花费较多CPU时间地址变换快

不灵活灵活12

四.主存分配

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

2.制定分配策略

(1)主存分配策略在众多个请求者中选择一个请求者的原则。

(2)放置策略选择一个空闲区或若干空闲区的原则。13

(3)调入策略决定信息装入主存的时机预调策略：预先将信息调入主存请调策略：当需要信息时，将信息调入主存

(4)淘汰策略在主存中没有任何可用的空闲区时，决定哪些信息从主存中移走，即确定淘汰已占用的内存区的原则。3.实施主存分配与回收14

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

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

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

2.解决问题的思路

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

3.实现方法

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

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

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

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

4.虚拟存储器的核心

逻辑地址与物理地址分开

主存空间与地址空间分开

提供地址变换机构

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

有相当容量的辅存足以存放多用户的作业的地址空间

有一定容量的主存存放运行进程的当前信息

地址变换机构17

六.存储保护

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

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

界地址保护存储键保护18

3.界地址保护

(1)上、下界防护movr1,[500]123020KB256KB1存储空间24KB下界寄存器20KB上界寄存器24KB

如何设置上下界寄存器内容

如何判断是否越界

满足

20KB≤D＜24KB

允许访问否则发生越界中断19

(2)基地址、限长防护movr1,[500]123020KB256KB1存储空间24KB基址寄存器20KB限长寄存器4KB

如何设置基址寄存器和限长寄存器内容

如何判断是否越界

满足逻辑地址＜4KB

允许访问否则发生越界中断20

7.3分区存储管理一.动态分区分配

1.什么是动态分区分配在处理作业的过程中，建立分区，依用户请求的大小分配分区。

2.动态分区的分配、回收过程

21

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

os

作业1

作业2

作业3

作业4

52KB66KB130KB230KB256KB1主存20KB0

os

作业1

作业2

作业3

52KB66KB130KB256KB1主存20KB0

os

作业1

52KB256KB1主存0

os

256KB1主存20KB20KB0

os

作业1

作业2

52KB66KB256KB1主存作业1申请

32KB作业2申请

14KB作业3申请

64KB作业4申请

100KB作业5申请

50KB22

(2)动态分区的回收过程20KB052KB66KB130KB230KB256KB1主存

os

作业1

作业2

作业3

作业4

20KB0

os

作业1

作业2

作业3

作业4

52KB66KB130KB230KB256KB1主存20KB0

os

作业1

作业2

作业3

作业4

52KB66KB130KB230KB256KB1主存作业2完成作业4完成23

二.分区分配机构

1.分区描述器

分配标志flag

大小size

勾链字nextflag：为0——空闲区为1——已分配区size：分区大小next：空闲区——自由主存队列中的勾链字已分配区——此项为零24

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

作业1

作业3

作业4

52KB66KB130KB230KB256KB1主存52KBm-rib

014KB230KB

026KB

自由主存队列25

三.分区的分配与回收

1.分区分配

(1)分区分配思路

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

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

•若找到，以空闲块与请求的主存块大小之间的关系进行相应的处理，并返回所分配区域的首址；

•否则，告之不能满足要求。算法见P167MODULE7.126

2.分区回收(算法见P169MODULE7.2)

回收主存块的四种情况

r上邻空闲区rf1作业2

r上下邻空闲区rf1f2

r上下邻已分配区r作业1作业2

r下邻空闲区r作业1f227

回收分区r上邻空闲区

rf1作业2

f1作业2r与f1合并成为一个大的空闲区f1

回收分区r下邻空闲区

r作业1f2

作业1f2r与f2合并成为一个大的空闲区f2

28

回收分区r上、下邻空闲区r与f1、

f1

合并成为一个大的空闲区f1

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

rf1f2

f1

r作业1作业2

f作业1作业229

四.放置策略

1.什么是放置策略选择空闲区的策略，称为放置策略。空闲区队列建立方法体现了放置策略常用的放置策略——

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

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

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

三种放置策略见P171图7.11，P172图7.1230

2.首次适应算法

(1)什么是首次适应算法首次适应算法是将输入的作业放置到主存里第一个足够装入它的可利用的空闲区中。

(2)特点

自由主存队列结构——

空闲区地址由低到高排序尽可能地利用存储器中低地址的空闲区，而尽量保存高地址的空闲区。31

3.最佳适应算法

(1)什么是最佳适应算法最佳适应算法是将输入的作业放置到主存中与它所需大小最接近的空闲区中。

(2)特点自由主存队列结构——

空闲区大小由小到大排序尽可能地利用存储器中小的空闲区，而尽量保存大的空闲区。32

4.最坏适应算法

(1)什么是最坏适应算法最坏适应算法是将输入的作业放置到主存中主存中最不适合它的空闲区中。

(3)特点

自由主存队列结构——

空闲区大小由大到小排序尽可能地利用存储器中大的空闲区。33

五.碎片问题及拼接技术

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

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

P172图7.1334

(四)页式存储管理一.页式系统的基本概念

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

2.主存块主存被等分成大小相等的片，称为主存块，又称为实页。35

3.页表

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

(2)页表的组成

高速缓冲存储器组成地址变换速度快，但成本较高。

主存区域地址变换速度比硬件慢，成本较低。36

4.分页映像存储的例01KB01KB2KB3KB1主存作业2地址空间2KB3KB4KB5KB6KB7KB8KB9KB10KB101KB2KB1作业1地址空间01KB1作业3地址空间0516页号块号02140827作业1页表作业2页表作业3页表osos37

二.页式地址变换

1.页表记录页与块之间对应关系的地址变换的机构

2.虚地址结构当CPU给出的虚地址长度为16位，页面大小为1KB时，在分页系统中地址结构的格式如下。pw151090页号P页内位移Wmovr1,[2500]12301KB2KB3KB1作业2地址空间38

3.页式地址变换

(1)页式地址变换的例作业2地址空间中，设100号单元处有如下指令：movr1,[2500]。当这条指令执行时，如何进行正确的地址变换。movr1,[2500]12301KB1KB3KB1作业2地址空间2500→2*1024+452p=2w=4520000100111000100000010011100010039

(2)页式地址变换过程

151090块号b块内位移W页表始址寄存器movr1,[2500]12301KB2KB3KB1作业2地址空间+021427页表00001001110001001090p=2w=452页号P页内位移W250001KB主存2KB3KB4KB5KB6KB7KB8KB9KB10KB1ososmovr1,[2500]123第1页7*1024+452=7620000111011100010040

(3)

页式地址变换的步骤

CPU给出操作数地址(为2500)；

由分页机构自动地把逻辑地址分为两部分，得到页号p和页内相对位移w(p=2，w=452)；

根据页表始址寄存器指示的页表始地址，以页号为索引，找到第2页所对应的块号(为7)；

最后，将块号b和页内位移量w拼接在一起，就形成了访问主存的物理地址

(7*1024+452=7620)。41

4.采用联想存储器加快查表速度

(1)什么是联想存储器高速、小容量半导体存储部件，又称缓冲存储器。

(2)快表在缓冲存储器中存放正在运行的进程当前用到的页号和对应的块号，又称为快表。42

三.请调策略

1.两种页式系统

(1)简单页式系统装入一个作业的全部页面才能投入运行。

(2)请求页式系统只装入一个作业的部分页面即可投入运行。

(1)简单页式系统需要解决什么问题？

(2)请求分页系统需要解决什么问题?43

2.请求页式系统需解决的问题

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

(2)当发现所需访问的页面不在主存时如何处理?

3.扩充页表功能

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

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

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

4.缺页处理

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

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

缺页中断执行完该指令

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

从外存读入所需的页

调整存储分配表和页表

重新启动被中断的指令

调整存储分配表和页表要重写入?该页写入外存YNNY硬件软件YN45

四.淘汰策略

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

如何决定淘汰哪一页？根据页面在系统中的表现如：使用的频繁程度进入系统时间的长短46

2.扩充页表功能

页号主存块号中断位辅存地址引用位改变位

引用位——标识某页最近是否被访问为“0”——该页没有被访问为“1”——该页已被访问

改变位——表示某页是否被修改为“0”——该页未被修改为“1”——该页已被修改47

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

下面讨论常用的页面淘汰算法48

4.先进先出淘汰算法(FIFO算法)

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

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

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

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

当需要置换一页时，选择替换指向的那一页，然后调整替换指针的内容。49

5.最久未使用淘汰算法(LRU算法)

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

(2)最久未使用淘汰算法的实现方法

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

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

当要淘汰一页时，选择时间最长的一页淘汰。要精确实现很困难硬件方法：采用寄存器软件方法：采用页号栈50

(3)LRU近似淘汰算法

入口读出替换指针指向的块号移动指针指向下一个存储块

引用位为0?选择该页淘汰，记录该页的页号、块号将该页所在的块号送到替换指针返回置引用位为0YN51

(五)段页式存储管理一.段式地址空间

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

2.作业地址空间由若干个逻辑分段组成，每个分段有自己的名字，对于一个分段而言，它是一个连续的地址区。52

3.段式地址空间code_addr4KB10代码分段data_addr3KB10数据分段stack_addr2KB10栈段

段号s段内位移w53

二.页式系统与段式系统的区别

1.用户地址空间的区别

页式系统中用户地址空间——一维地址空间

段式系统中用户地址空间——二维地址空间

2.分段与页面的区别分段页面

信息的逻辑划分信息的物理划分

段长是可变的