os7主存管理课件

主存管理主存管理主存管理概述主存管理的功能分区存储管理页式存储管理段式及段页式存储管理Linux系统的存储管理1主存管理——主要内容2主存管理——主存管理概述1.主存共享方式大小不等的区域分区存储管理段式存储管理大小相等的区域页式存储管理二者结合段页式存储管理3主存管理——主存管理概述2.程序的逻辑组织一维地址结构一个程序是一个连续、线性的地址结构；确定线性地址空间中的指令地址或操作数地址只需要一个信息。程序地址空间01n-1

4主存管理——主存管理概述二维地址结构一个程序由若干个分段组成，每个分段是一个连续的地址区；确定任一线性地址空间中的指令地址或操作数地址需要两个信息，一是该信息所在的分段，另一个是该信息在段内的偏移量。code_addr4KB

10代码分段data_addr3KB

10数据分段stack_addr2KB

10栈段11

51.几个概念物理地址(绝对地址、实地址)

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

物理地址的集合所对应的空间组成了主存空间。逻辑地址(相对地址、虚地址)

用户的程序地址(指令地址或操作数地址)均为逻辑地址。作业地址空间用户程序所有的逻辑地址集合对应的空间。主存管理——主存管理功能6作业地址空间与主存空间主存管理——主存管理功能主存空间01m-1作业1地址空间01n-1作业i地址空间01k-1

7主存管理——主存管理功能2.主存管理功能实现逻辑地址到物理主存地址的映射主存分配存储保护主存扩充8主存管理——地址映射3.地址映射什么是地址映射

将程序地址空间中使用的逻辑地址变换成主存中的物理地址的过程，称为地址映射。movr1,[500]1230100500599作业地址空间movr1,[500]12301000110015001599256k-1存储空间9主存管理——地址映射在作业装入时确定地址映射关系在作业装入过程中随即进行的地址变换方式称为静态地址映射。movr1,[500]movr1,[500+m]01005005990mm+100256k-1作业地址空间存储空间m+500重定位装入程序123123地址映射的时机和类别编程或编译时确定地址映射关系

在程序编写或程序编译时确定虚、实地址之间的对应关系，结果是一个不能浮动的程序模块。10主存管理——地址映射在程序运行时确定地址映射关系

在程序执行期间，随着每条指令和数据的访问自动地连续地进行地址映射，这种地址变换方式称为动态地址映射。重定位寄存器1000500逻辑地址+0

movr1,[500]

1000256k-1存储空间110015001600123movr1,[500]0100500599作业地址空间12311主存管理——地址映射静态地址映射与动态地址映射的区别

静态地址映射

动态地址映射

在作业装入过程中

在程序执行期间

进行地址映射

进行地址映射

需软件

需硬件地址变换机构

重定位装入程序

重定位寄存器

需花费较多CPU时间

地址变换快

不灵活

灵活

12主存管理——主存管理功能4.主存分配构造分配用的数据结构

主存资源信息块：等待队列；空闲区队列；主存分配程序制定策略主存分配策略

——在众多个请求者中选择一个请求者的原则放置策略

——在可用资源中，选择一个空闲区的原则调入策略

——决定信息装入主存的时机预调策略：预先将信息调入主存请调策略：当需要信息时，将信息调入主存淘汰策略

——在主存中没有可用的空闲区(对某一作业而言)时，决定哪些信息从主存中移走，即确定淘汰已占用的内存区的原则。实施主存分配与回收13主存管理——主存管理功能5.主存扩充可行性实现方法程序的全部代码和数据存放在辅存中；将程序当前执行所涉及的那部分程序代码放入主存中；程序执行时，当所需信息不在主存，由操作系统和硬件相配合来完成主存从辅存中调入信息，程序继续执行。什么是虚拟存储器

由操作系统和硬件相配合来完成主存和辅存之间的信息的动态调度。这样的计算机系统好像为用户提供了一个其存储容量比实际主存大得多的存储器，这个存储器称为虚拟存储器。局部性特征14主存管理——主存管理功能虚拟存储器的核心逻辑地址与物理地址分开存储空间与虚地址空间分开提供地址变换机构实现虚拟存储器的物质基础有相当容量的辅存足以存放应用程序的虚地址空间有一定容量的主存存放进入主存的多进程的信息地址变换机构15主存管理——主存管理功能6.存储保护什么是存储保护

在多用户环境中，主存储器按区分配给各用户程序使用。为了互不影响，必须由硬件(软件配合)保证各用户程序只能在给定的存储区域内活动，这种措施叫做存储保护。实现方法界地址保护存储键保护16主存管理——主存管理功能界地址保护上下界防护例：作业大小为4KB，主存首址为20KB。movr1,[500]123020KB256KB

1存储空间24KB下界寄存器

20KB上界寄存器

24KB如何设置上下界寄存器内容？如何判断是否越界？若20KB≤D＜24KB

允许访问；否则发生越界中断17主存管理——主存管理功能界地址保护基地址、限长防护例：作业大小为4KB，主存首址为20KB。如何设置基址、限长寄存器内容？如何判断是否越界？若逻辑地址＜4KB

允许访问；否则发生越界中断movr1,[500]123020KB256KB

1存储空间24KB基址寄存器

20KB限长寄存器

4KB181.动态分区分配什么是动态分区分配

在处理作业的过程中，建立分区，依用户请求的大小分配分区。动态分区的分配、回收过程动态分区的分配过程

主存管理——分区存储管理19主存管理——分区存储管理作业1申请

32KB0

256KB1主存20KBos20KB0

52KB256KB1主存os作业1作业2申请

14KB20KB0

52KB66KB256KB1主存os作业1作业2作业3申请

64KB20KB0

52KB66KB130KB256KB1主存os作业1作业2作业3作业4申请

100KB20KB0

52KB66KB130KB230KB256KB1主存os作业1作业2作业3作业4作业5申请

50KB20主存管理——分区存储管理动态分区的回收过程

作业2

完成作业4完成20KB0

52KB66KB130KB230KB256KB1主存作业1作业2作业3作业4os20KB0

52KB66KB130KB230KB256KB1主存作业1作业3作业4os20KB0

52KB66KB130KB230KB256KB1主存os作业1作业3211.动态分区分配什么是动态分区分配

在处理作业的过程中，建立分区，依用户请求的大小分配分区。分区分配结构主存资源信息块(M_RIB)分区描述器(PD)主存管理——分区存储管理

等待队列头指针空闲区队列头指针主存分配程序入口地址M_RIBflag：为0——空闲区为1——已分配区size：分区大小next：空闲区——自由主存队列中的勾链字已分配区——此项为零

分配标志flag

大小size

勾链字nextPD22空闲区队列结构主存管理——分区存储管理20KB0

52KB66KB130KB230KB256KB1主存os作业1作业3作业452KBm-rib

空闲区队列230KB014KB026KB

232.分区的分配与回收分区分配思路依申请者所要求的主存区的大小，分区分配程序在自由主存队列中找一个满足用户需要的空闲块；若找到了所需的空闲区，有两种情况空闲区与要求的大小相等，将该空闲区分配并从队列中摘除；空闲区大于所要求的的大小，将空闲区分为两部分：一部分成为已分配区，建立已分配区的描述器；剩下部分仍为空闲区。返回所分配区域的首址；否则，告之不能满足要求。主存管理——分区存储管理24分区回收思路检查释放分区(即为回收分区)在主存中的邻接情况；若上、下邻接空闲区，则合并，成为一个连续的空闲区；若回收分区不与任何空闲区相邻接，建立一个新的空闲区，并加入到空闲区队列中。主存管理——分区存储管理253.放置策略什么是放置策略选择空闲区的策略，称为放置策略。常用的放置策略——

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

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

最坏匹配(最坏适应算法)主存管理——分区存储管理26首次适应算法首次适应算法是将输入的作业放置到主存里第一个足够装入它的地址最低的空闲区中。主存管理——分区存储管理

作业A

18KB首次适应算法的例空闲区队列结构

空闲区地址由低到高排序首次适应算法的特点尽可能地利用存储器中低地址的空闲区，而尽量保存高地址的空闲区。

在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB-1主存os27最佳适应算法最佳适应算法是将输入的作业放置到主存中与它所需大小最接近的空闲区中。主存管理——分区存储管理

作业A

18KB最佳适应算法的例空闲区队列结构

空闲区大小由小到大排序最佳适应算法的特点尽可能地利用存储器中小的空闲区，而尽量保存大的空闲区。

在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB-1主存os28最坏适应算法最坏适应算法是将输入的作业放置到主存中与它所需大小差距最大的空闲区中。主存管理——分区存储管理

作业A

18KB最坏适应算法的例空闲区队列结构

空闲区大小由大到小排序最坏适应算法的特点尽可能地利用存储器中大的空闲区。

在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB-1主存os29三种放置策略的讨论作业A要求18KB；作业B要求25KB；作业C要求30KB。用首次适应算法、最佳适应算法、最坏适应算法来处理该作业序列，看哪种算法合适。

主存管理——分区存储管理30三种放置策略的讨论首次适应算法、最佳适应算法、最坏适应算法的队列结构。主存管理——分区存储管理

在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB-1主存os(a)首次适应算法的空闲区队列20KB030KB100KB020KB160KB05KB210KB046KB

(a)最佳适应算法的空闲区队列160KB05KB100KB020KB20KB030KB210KB046KB

(a)最坏适应算法的空闲区队列210KB046KB20KB030KB100KB020KB160KB05KB

31三种放置策略的讨论首次适应算法

主存管理——分区存储管理

作业A要求18KB

作业B要求25KB

作业C要求30KB

首次适应算法对该作业序列是不合适的

在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB-1主存os(a)首次适应算法的空闲区队列20KB030KB100KB020KB160KB05KB210KB046KB

32最佳适应算法

主存管理——分区存储管理

作业A要求18KB

作业B要求25KB

作业C要求30KB

最佳适应算法对该作业序列是合适的

在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB-1主存os(a)最佳适应算法的空闲区队列160KB05KB100KB020KB20KB030KB210KB046KB

33最坏适应算法

主存管理——分区存储管理

作业A要求18KB

作业B要求25KB

作业C要求30KB

最坏适应算法对该作业序列是不合适的

os在使用在使用在使用30KB5KB46KB0KB20KB100KB20KB160KB210KB256KB-1主存(a)最坏适应算法的空闲区队列210KB046KB20KB030KB100KB020KB160KB05KB

344.碎片问题及拼接技术什么是碎片问题在已分配区之间存在着的一些没有被充分利用的空闲区

主存管理——分区存储管理如何解决碎片问题？什么是拼接技术

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

54KB58KB135KB254KB256KB1主存138KB作业20os作业3作业１拼接前20KB0

54KB131KB247KB256KB1主存os作业１作业2作业3拼接后351.页式系统的基本概念页面

程序的地址空间被等分成大小相等的片，称为页面，又称为虚页。主存块主存被等分成大小相等的片，称为主存块，又称为实页。页面与主存块的关系主存管理——页式存储管理02KB4KB254KB256KB102KB4KB6KB0页1页2页3页主存作业地址空间36页表什么是页表为了实现从地址空间到物理主存的映象，系统建立的记录页与内存块之间对应关系的地址变换的机构称为页面映像表，简称页表。页表的组成高速缓冲存储器——地址变换速度快，但成本较高主存区域——地址变换速度比硬件慢，成本较低主存管理——页式存储管理37分页映像存储的例主存管理——页式存储管理01KB01KB2KB3KB1主存作业2地址空间2KB3KB4KB5KB6KB7KB8KB9KB10KB101KB2KB1作业1地址空间01KB1作业3地址空间0516页号块号02140827作业1页表作业2页表作业3页表osos382.页式地址变换页表记录页与块之间对应关系的地址变换的机构。虚地址结构当CPU给出的虚地址长度为16位，页面大小为1KB时，在分页系统中地址结构的格式如下：主存管理——页式存储管理pw151090页号P页内位移Wmovr1,[2500]12301KB2KB3KB1作业2地址空间391页式地址变换页式地址变换的例作业2地址空间中，设100号单元处有如下指令：

movr1,[2500]。当这条指令执行时，如何进行正确的地址变换。主存管理——页式存储管理2500→2×1024+452p=2w=45200001001110001000000100111000100movr1,[2500]12301KB2KB3KB1作业2地址空间40页式地址变换过程主存管理——页式存储管理页表始址寄存器movr1,[2500]12301KB2KB3KB1作业2地址空间+021427页表0000100111000100151090页号P页内位移W250001KB主存2KB3KB4KB5KB6KB7KB8KB9KB10KB1ososmovr1,[2500]123第1页页号P页内位移W

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

(7*1024+452=7620)主存管理——页式存储管理42采用联想存储器加快查表速度什么是联想存储器高速、小容量半导体存储部件，又称缓冲存储器。快表在缓冲存储器中存放正在运行的进程当前用到的页号和对应的块号，又称为快表。主存管理——页式存储管理43利用快表进行地址映射

主存管理——页式存储管理a

+Pw

仅在联想映像不匹配时进行页号bw首先选择联想存储器所有页表在主存中物理地址pb┇┇┇┇┇┇ba+pa443.请调页面的机制两种页式系统简单页式系统——装入一个作业的全部页面才能投入运行。请求页式系统——装入一个作业的部分页面即可投入运行。

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

(2)请求分页系统需要解决什么问题?主存管理——页式存储管理请求页式系统需解决的问题

扩充页表功能

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

——

标识该页是否在主存若i=1，表示此页不在主存；若i=0，表示该页在主存辅存地址

——该页面在辅存的位置45缺页处理

主存管理——页式存储管理作业2在请求分页系统中的存储映像01KB2KB4KB1作业2地址空间movr1,[2120]addr1,[3410]0062510068023KB01KB主存2KB3KB4KB5KB6KB7KB8KB9KB10KB102142作业2页表osos作业2

第1页作业2

第0页3页号辅存地址中断位块号

0011地址地址地址地址46主存管理——页式存储管理缺页处理的例作业2的主存块数为m2=3，讨论程序执行“movr1，[2120］”指令时的情况。CPU产生的虚地址为2120分页机构得p=2，w=72查页表。该页中断位i=1发生缺页中断！

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

m，则需淘汰该作业在主存中的一页01KB2KB4KB1作业2地址空间movr1,[2120]addr1,[3410]0062510068023KB47主存管理——页式存储管理缺页处理

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

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

缺页中断执行完该指令

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

从外存读入所需的页

调整存储分配表和页表

重新启动被中断的指令

调整存储分配表和页表要重写入?该页写入外存YNNY硬件软件YN484.淘汰机制与策略什么是淘汰策略用来选择淘汰哪一页的规则叫做置换策略，或称淘汰算法。

主存管理——页式存储管理如何决定淘汰哪一页？扩充页表功能

引用位——标识该页最近是否被访问

为“0”——该页没有被访问；为“1”——该页已被访问改变位——表示该页是否被修改

为“0”——该页未被修改；为“1”——该页已被修改

页号主存块号中断位辅存地址引用位改变位49颠簸颠簸(thrashing)，又称为“抖动”。简单地说，导致系统效率急剧下降的主存和辅存之间的频繁页面置换现像称为“抖动”。

主存管理——页式存储管理缺页中断率假定程序p共有n页，系统分配m块，有1≤m≤n；

若程序p在运行中：成功的访问次数为s，不成功的访问次数为f；缺页中断率：f′=f/(s+f)f′=f(r，m，p)；r：置换算法；

p：程序特征；m：系统分配的块数50主存管理——页式存储管理最佳算法(OPT算法)当要调入一新页而必须先淘汰一旧页时，所淘汰的那一页应是以后不再要用的，或者是在最长的时间以后才会用到的那页。

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

什么是先进先出淘汰算法总是选择在主存中居留时间最长(即最早进入主存)的一页淘汰。先进先出淘汰算法的实现建立一个页面进入主存的先后次序表；建立一个替换指针，指向最早进入主存的页面；当需要置换一页时，选择替换指向的那一页，然后调整替换指针的内容。51主存管理——页式存储管理页号表页面进入主存的先后次序：

2451

替换指针

指向最老的一页页号

24516

当要调入第6页时：置换第2页将第2页改为6替换指针指向第4页

52主存管理——页式存储管理在存储分块表中建立次序表页面进入主存的先后次序：

4512

当要调入第6页时：如何处理?51267102345642516

742替换指针块号页号指针710234566251

2746替换指针

块号页号指针53主存管理——页式存储管理最久未使用淘汰算法(LRU算法)什么是最久未使用淘汰算法总是选择最长时间未被使用的那一页淘汰。最久未使用淘汰算法的实现用引用位考察页面的使用情况；当访问页面时，将引用位置1，并记时；当要淘汰一页时，选择时间最长的一页淘汰。

要精确实现很困难硬件方法：采用计数器软件方法：采用页号栈54主存管理——页式存储管理软件方法：采用页号栈页面访问轨迹：4512

5

64512访问第5页访问第6页淘汰第4页41251256访问4、5、1、2页后栈的内容

访问第5页后，调整栈的内容

访问第6页后，栈的内容

55主存管理——页式存储管理LRU近似淘汰算法

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

引用位为0?选择该页淘汰，记录该页的页号、块号将该页所在的块号送到替换指针返回置引用位为0YN56主存管理——页式存储管理LRU近似淘汰算法举例71023456425141724替换指针

块号页号引用位指针600171023456425640727替换指针

块号页号引用位指针6011当要调入第6页时，如何处理?571.段式地址空间什么是段分段是程序中自然划分的一组逻辑意义完整的信息集合。分段的例：代码分段、数据分段、栈段页。作业地址空间

由若干个逻辑分段组成，每个分段有自己的名字，对于一个分段而言，它是一个连续的地址区。主存管理——段页式存储管理code_addr4KB

10代码分段data_addr3KB

10数据分段stack_addr2KB

10栈段58段式地址结构

主存管理——段页式存储管理

段号s段内位移w2.段式地址变换

LBswB+w第S段段号段内位移段号长度基址段式地址步骤取出程序地址(s，w)；用s检索段表；如w＜0或w≥L则主存越界；(B＋w)即为所需主存地址593.页式系统与段式系统的区别用户地址空间的区别页式系统中用户地址空间——一维地址空间段式系统中用户地址空间——二维地址空间

分段和页面的区别

分段页面

信息的逻辑划分

信息的物理划分

段长是可变的

页的大小是固定的

用户可见

用户不可见

w字段的溢出

w字段的溢出自动将产生越界中断加入到页号中

主存管理——段页式存储管理604.段页式系统

在段式存储管理中结合分页存储管理技术，在一个分段内划分页面，就形成了段页式存储管理。段页式地址结构的用户地址空间主存管理——段页式存储管理code_addr4KB

10代码分段data_addr3KB

10数据分段stack_addr2KB

10栈段61主存管理——段页式存储管理段页式系统中段表、页表与主存的关系01n段号页表长度页表始址23┆页号1块号其他0段页表主存段表┆

01块号其他1段页表2页号0621.Linux系统段页式地址变换Linux系统的分段Linux系统处在用户态时，使用用户代码段和用户数据段来对指令和数据寻址在核态时，使用内核代码段和内核数据段来对指令和数据寻址每个分段是一个连续的线性地址空间，从0开始直到

232−1的寻址长度。

主存管理——Linux系统存储管理6380x86分页结构

80x86微处理器的分页单元处理4KB的页。一个32位的线性地址分为3个域。主存管理——Linux系统存储管理

页目录页表页内位移31222112110页目录字段指向页目录项；页表字段指向进程的一个页表项；页内位移则是页内偏移量

64主存管理——Linux系统存储管理三级页表

第一级：全局目录(PGD)PGD中的表项指向页目录中的一个表项二级页表：页目录(PMD)PMD中的表项指向页表PTE中的一个表项三级：页表该表项指向物理页(页框)的主存地址65主存管理——Linux系统存储管理线性地址转换为物理地址地址转换过程

Linux系统通过三级页表完成线性地址到物理地址的转换页目录页表页内位移31222112110cr3+：+：页目录表页表物理页+++66主存管理——Linux系统存储管理地址变换步骤由cr3指示的当前页目录的物理地址与分页结构中的页目录字段的内容相加指向页目录表项；由页目录表项内容得到当前使用的页表的始地址，通过分页结构中的页表字段的内容找到该页表项；由页表项指示的该页的物理页(页框)的主存地址与分页结构中的页内位移相加，得到最终的物理地址。672.Linux系统动态内核管理物理页的描述Linux系统主存分配的基本单位是物理页(又称为页框)

主存管理单元MMU以页为单位进行分配和处理

32位体系结构支持4KB的页，64位体系结构支持8KB的页内核用structpage结构描述页框

structpage{flags;/*页的状态*/_count;/*该页被引用的次数*/

*virtual;/*页的虚拟地址，通常情况下记录页在虚拟主存中的地址*/};

主存管理——Linux系统存储管理68物理主存分区内核将系统中的所有页框划分为不同的区，具有相似特征的页框归为同一个分区。Linux系统共分为三种分区ZONE_DMA

这个分区包含的页只能用来执行DMA操作，大小为16MB；ZONE_NORMAL

这个分区包含的页都是能正常映射的页，大小为16MB

896MBZONE_HIGHMEM

这个分区包含的是“高端主存”，其中的物理页并不能永久地映射到内核地址空间，大小为896MB。主存管理——Linux系统存储管理69分区页框的分配

Linux内核通过页框和区对主存进行管理，实现了请求主存的底层机制；内核提供提供一组访问接口(函数或宏)可以直接的方式获得动态主存，注意这种方式只能由内核使用。

主存管理——Linux系统存储管理70主存管理——Linux系统存储管理分区页框分配器

分区页框分配器(Zonedpageframeallocator)是一个内核子系统，它负责对连续页框的主存分配。分区页框分配器的组成如下图

管理区分配器每CPU页框高速缓存每CPU页框高速缓存每CPU页框高速缓存

伙伴系统

伙伴系统

伙伴系统71主存管理——Linux系统存储管理伙伴系统算法

主存管理中的外碎片问题当频繁地请求和释放不同大小的连续页框，就会导致在已分配页框内产生许多小的、分散的空闲页框；

Linux系统采用伙伴系统算法记录当前空闲的连续页框块的情况，以尽量避免为满足小块的请求而分割大的空闲块。伙伴系统算法中页框的组织将所有的空闲页框分组为11个块链表；每个块链表分别包含大小为1、2、4、8、16、32