主存管理

主存管理概述

现代操作系统将主存区分为物理主存和逻辑主存2类。

物理主存是共享的物质基础。由多个物理地址构成。

主存共享方式—-分片共享

分片的方式

(1) 大小不等的区域—根据用户程序的实际需要决定分区的大小

①分区存储管理

②段式存储管理

(2) 大小相等的区域—以块为单位，根据用户程序的实际需要决定应分配的块数

页式存储管理

(3) 二者结合

段页式存储管理

由于不同程序的物理地址的首地址都是乱七八糟的，不方便用户使用。所以采用逻辑地址（虚地址）将首地址设置为0。逻辑地址和物理地址之间的映射就是地址映射。

程序的逻辑组织

一维地址结构

一个程序是一个连续、线性的地址结构；确定线性地址空间中的指令地址或操作数地址只需要一个信息。

二维地址结构

一个程序由若干个分段组成（数据段、代码段、栈段······），每个分段是一个连续的地址区；

确定线性地址空间中的指令地址或操作数地址需要两个信息，一是该信息所在的分段，另一个是该信息在段内的偏移量。

主存管理功能

实现的功能：主存分配、主存保护、虚拟主存

• 地址映射—-将逻辑地址映射成物理地址
• 主存分配—-在多用户之间分配物理主存
• 存储保护—-对各用户区的信息提供保护措施
• 主存扩充/虚拟主存—-扩充逻辑主存区

地址映射

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

地址重定位就是操作系统将逻辑地址转变为物理地址的过程。。。也就是对目标程序中的指令和数据进行修改的过程

将逻辑地址空间重定位到物理地址空间的时机有三种：

1、程序编译连接时。

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

2、程序装入内存时。

​ 在程序装入过程中随即进行的地址变换方式称为静态地址映射。

3、程序执行时。

​ 在程序执行期间，随着每条指令和数据的访问自动地连续地进行地址映射，这种地址变换方式称为动态地址映射。

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

静态地址映射	动态地址映射
在程序装入过程中在程序执行期间进行地址映射	在程序执行期间进行地址映射进行地址映射
需软件(重定位装入程序)	需硬件地址变换机构( 重定位寄存器)
需花费较多CPU时间	地址变换快
不灵活	灵活

一、静态重定位
　　静态重定位是在程序执行之前进行重定位，它根据装配模块将要装入的内存起始位置，直接修改装配模块中的有关使用地址的指令。
　　例如，一个以“0”作为参考地址的装配模块，要装入以100为起始地址的存储空间。显然，在装入之前要做某些修改，程序才能正确执行。例如，MOV　 EAX，[500]这条指令的意义，是把相对地址为500的存储单元内容1234装入EAX号累器。现在内容为1234的存储单元的实际地址为1500， 即为相对地址(500)加上装入的地址(1000),因此，MOV　EAX，[500]这条指令中的直接地址码也要相应地加上起始地址，而成为MOV　 EAX，[1500]。
　　程序中涉及直接地址的每条指令都要进行这样的修改。需要修改的位置称为重定位项，所做的加实际装入模块起始地址修改中的块起始地址称为重定位因子。
　　为支持静态重定位，连接程序在生成统一地址空间和装配模块时，　应产生一个重定位项表，连接程序此时还不知道装配模块将要装入的实际位置，故重定位表 所给出的需修改位置是相对地址所表示的位置。
　　操作系统的装入程序要把装配模块和重定位项表一起装入内存。由装配模块的实际装入起始地址得到重定位因子，然后实施如下两步：
　　（1）取重定位项，加上重定位因子而得到欲修改位置的实际地址；
　　（2）对实际地址中的内容再做加重定位因子的修改，从而完成指令代码的修改。
　　对所有的重定位项实施上述两步操作后，静态重定位才完成，尔后可启动程序执行。使用过的重定位项表内存副本随即被废弃。

　　静态重定位有着无需硬件支持的优点，但存在着如下的缺点：一是程序重定位之后就不能在内存中搬动了；二是要求程序的存储空间是连续的，不能把程序放在若干个不连续的区域内。

二、动态重定位
　　动态重定位是指，不是在程序执行之前而是在程序执行过程中进行地址重定位。更确切地说，是在CPU每次访问内存单元前才进行地址变换。动态重定位可使装配模 块不加任何修改而装入内存，但是它需要硬件——定位寄存器的支持。
　　程序的目标模块装入内存时，与地址有关的各项均保持原来的相对地址不进行任何修改。如MOV　1，[500]这条指令仍是相对地址500。当此模块被 操作系统调度到处理机上执行时，操作系统将把此模块装入的实际起始起始地址减去目标模块的相对基地址，然后将其差值装入定位寄存器中。当CPU取得一条访问内存的指令时，地址变换硬件逻辑自动将指令中的相对地址与定位寄存器中的值相加，再依此和值作为内存绝对地址去访问该单元中的数据。
　　由此可见，进行动态重定位的时机是在指令执行过程中，每次访问内存前动态地进行。采取动态重定位可带来两个好处：
　　（1）目标模块装入内存时无需任何修改，因而装入之后再搬迁也不会影响其正确执行，这对于存储器紧缩、解决碎片问题是极其有利的；
　　（2）一个程序由若干个相对独立的目标模块组成时，每个目标模块各装入一个存储区域，这些存储区域可以不是顺序相邻的，只要各个模块有自己对应的定位寄存器就行。

　　动态重定位技术所付出的代价是需要硬件支持。

主存分配

用于主存分配的数据结构：主存资源信息块、空闲区队列；

主存管理器的一些策略

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

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

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

淘汰策略——在主存中没有可用的空闲区(对某一程序而言)时，决定哪些信息从主存中移走，即确定淘汰已占用的内存区的原则。

调入策略对页式系统或非页式系统没有多大区别，但是淘汰策略和放置策略在页式和非页式系统中是不同的。（页式的页的大小是固定的）

主存扩充

实现的方法：

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

虚拟存储器

由操作系统和硬件相配合来完成主存和辅存之间的信息的动态调度。这样的计算机系统好像为用户提供了一个其存储容量比实际主存大得多的存储器，这个存储器称为虚拟存储器。本质的大小其实是没有变的，但是给用户的感觉就是变大了，1元钱看成了100元，这100元就是虚拟存储器

虚拟存储器的核心是将程序的访问地址和主存的物理地址分离。为什么这么说？我们知道访问地址其实是逻辑地址（虚地址），它会去进行地址映射找到主存地址（这个功能由操作系统实现，所以用户不用管）。但是引入了虚存后（不要和虚地址搞混淆了），我们不需要了解主存的物理地址，我们只在虚存中运行（当然，真正运行的时候还是调入一部分进主存的）。这样就把访问地址和虚存互相对应（也就说成了和主存的物理地址分离）

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

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

• 有相当容量的辅存：足以存放应用程序的虚地址空间
• 有一定容量的主存：存放进入主存的多进程的信息
• 地址变换机构

存储保护

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

界地址保护

上、下界保护

比较的是物理地址。

硬件为分给应用程序的每一个连续的主存空间设置一对上下界寄存器—–分别指向该存储空间的上界和下界。

基地址、限长保护

比较的是逻辑地址

基地址存放的是逻辑地址—段的首地址

存储键保护

分区存储管理

对应的是主存分配

动态分区分配

在处理程序的过程中，建立分区，依用户请求的大小分配分区。

很明显，空闲区被切碎会产生内存碎片。

动态分区的分配方法中，对用户程序进行动态分配并实现动态地址映射（这个不难理解，由于在动态分区中，系统是根据程序的大小再决定分给程序内存空间的大小，在地址映射中，事先根本就不可能有物理地址让你静态地址映射）

分区分配数据结构

主存资源信息块(M_RIB)

分区描述器(PD)

flag：为0 ——空闲区
为1 ——已分配区

size：分区大小

next：空闲区——自由主存队列中的勾链字
已分配区——此项为零

分区的分配和回收

注意：动态地址映射只是决定了用户程序什么时候将虚地址映射到物理地址中。但是主存分配给用户程序的地址还没有决定。

分区分配

动态分区的策略如下：“放置策略”

①寻找空闲块
依申请者所要求的主存区的大小，分区分配程序在自由主存队列中找一个满足用户需要的空闲块；

②若找到了所需的空闲区，有两种情况
i 空闲区与要求的大小相等，将该空闲区分配并从队列中摘除；
ii 空闲区大于所要求的的大小，将空闲区分为两部分：一部分成为已分配区，建立已分配区的描述器；剩下部分仍为空闲区。返回所分配区域的首址；

③否则，告之不能满足要求。

分区回收

①检查释放分区(即为回收分区)在主存中的邻接情况
若上、下邻接空闲区，则合并，成为一个连续的空闲区

②若回收分区不与任何空闲区相邻接
建立一个新的空闲区，并加入到空闲区队列中。

放置策略

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

本质上是空闲区队列的排序问题：
如上述提到的从高地址到低地址的分配方式：对应的就是按照地址增加、减少的次序分类排序
其他的排序还有：按照区的大小增加、减少的次序排序

常用的放置策略——

• 首次匹配(首次适应算法)
• 最佳匹配(最佳适应算法)
• 最坏匹配(最坏适应算法)

首次适应

首次适应算法是将输入的程序放置到主存里第一个足够装入它的地址最低的空闲区中。

空闲区队列结构：

空闲区地址由低到高排序

首次适应算法的特点

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

最佳适应

最佳适应算法是将输入的程序放置到主存中与它所需大小最接近的空闲区中。

空闲区队列结构

空闲区大小由小到大排序

最佳适应算法的特点

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

最坏适应

最坏适应算法是将输入的程序放置到主存中与它所需大小差距最大的空闲区中。

空闲区队列结构

空闲区大小由大到小排序

最坏适应算法的特点

尽可能地利用存储器中大的空闲区。

碎片问题及拼接技术

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

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

页式存储管理

程序的存放将不再是连续的。

程序的地址空间被等分成大小相等的片，称为页面，又称为虚页。
一般页面的大小为1KB、2KB、4KB

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

主存的块和页面的大小是相等的并且为2的幂次

好处：可以方便的支持虚拟存储，扩充内存。因为它可以只将一部分页面装入主存中即可。也直接解决了碎片问题。

但是在按区分配中，

需要解决的问题：

• 页式系统的地址映射—–动态地址映射
• 请调策略—-当装入部分页面的时候，需要询问当前访问的信息是否在主存中。不在的话，系统会从辅存中调入请求的页面。
• 放置策略—-确定程序的各个页面分配到主存的哪些块中，以及什么原则挑选主存块
• 淘汰策略—-当主存块用完后，确定哪些页面被淘汰出主存。

页式地址变换

页表

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

页表的组成：

​ i 如果选择高速缓冲存储器：地址变换速度快，但成本较高

​ ii 如果选择主存区域：地址变换速度比硬件慢，成本较低主存管理——页式存储管理

虚地址结构

页号+页内位移。

当CPU给出一个虚地址（指令地址或者操作数地址），将其拆分成页号和页内位移表示该地址对应于物理地址中的具体位置（哪个页面和页面中的哪个位置）

页式地址变换

页式地址变换步骤

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

通过页表将虚地址（也就是逻辑地址）中的页号对应到物理地址中的块号。由于页面的大小和内存块的大小是一样的，所以虚地址的页内位移就是物理地址中的块内位移。

分区管理的地址映射：

每个进程在分区说明表（ 为了管理分区，设置一张不属于任何进程的分区说明表，也就是放置策略章节对应的分区表）找到自己对应的表项目，根据表中的物理起始地址+自己的逻辑地址，就得到了实际的物理地址！目前为止需要注意的是，分区分配中，每个进程的分配的物理空间仍然是连续的!

换一个说法：

作业装入内存时，是将该用户的程序和数据原封不动地装入到内存中。当调度该进程在cpu上执行时，操作系统就自动将该进程在内存的起始地址装入基址寄存器，将进程的大小装入限长寄存器
。当执行指令时，如果地址合法，则将相对地址与基址寄存器中的地址相加，所得结果就是真正要访问的内存地址；如果地址越界，则发出相应中断，进行处理。

虚实地址映射极为简单。

联想存储器LSB

高速、小容量半导体存储部件，又称缓冲存储器

快表

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

具体可以参见《组成原理》中《存储系统》章节。

注意一点：页表查询只在联想映像不匹配时进行

请调页面的机制

①简单页式系统：装入一个程序的全部页面才能投入运行。

②请求页式系统：装入一个程序的部分页面即可投入运行。

Q：如何发现所要访问的页面不在主存？

A：扩充页表功能

Q：如何确认所要访问的页面不在主存时如何处理？

A：缺页处理

扩充页表功能

中断位i：标识该页是否在主存

​ 若i=1，表示此页不在主存；
​ 若i=0，表示该页在主存

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

缺页处理

• 当从虚地址中得到页号，判断页号不在主存的时候，会发送缺页中断。

• 接下来要将缺页的部分拉回到主存中：

  • 判断时候有空闲块：
    • 有的话就从辅存读入所需的页，并且调整存储分配表和页表，然后重新启动被中断的指令
    • 没有的话根据淘汰算法选择一页淘汰（淘汰掉的页如果还有用就将其放回辅存，没有用就丢掉），调整存储分配表和页表。然后从辅存中读入所需的页

淘汰机制和策略

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

Q：如何确定那一页被淘汰？

A：根据最近有没有使用、使用频率等

扩充页表功能

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

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

颠簸(thrashing)，又称为“抖动”

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

缺页中断率

假定程序p共有n页，系统分配m块，有1≤m≤n；若程序p在运行中：成功的访问次数为s，不成功的访问次数为f；缺页中断率：
$$
f′=f/ (s+ f)\
f′= f (r，m，p)；\
r：置换算法；m：系统分配的块数；p：程序特征
$$

常用的置换算法

最佳算法（OPT算法）

当要调入一新页而必须先淘汰一旧页时，所淘汰的那一页应是以后不再要用的，或者是在最长的时间以后才会用到的那页。

简单说，就是不肯可能实现的（你怎么知道那页是以后不用的）

站在现在，往未来看

先进先出淘汰算法（FIFO算法）

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

实现

• 建立一个页面进入主存的先后次序表；
• 建立一个替换指针，指向最早进入主存的页面；
• 当需要置换一页时，选择替换指向的那一页，然后调整替换指针的内容（指向替换后最早进入主存的页面，因为之前最早进入的被替换出去了）。

在存储分块表中记录页面进入主存的先后次序：4→5→1→2 当要调入第6页时：如何处理? 5→1→2 →6

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

总是选择最长时间未被使用的那一页淘汰。

实现

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

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

• 当要淘汰一页时，选择时间最长的一页淘汰。

  要精确实现很困难

  • 硬件方法：采用计数器
  • 软件方法：采用页号栈

段式、段页式存储管理

段式地址空间

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

程序地址空间

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

段式地址结构

段式地址变换

步骤：

• 取出程序地址(s，w)；
• 用s检索段表；
• 如w＜0或w≥L则主存越界；
• (B＋w)即为所需主存地址（B是基址）

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

用户地址空间的区别

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

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

分段和页面的区别

分段	页面
信息的逻辑划分	信息的物理划分
段长是可变的	页的大小是固定的
用户可见	用户不可见
w字段的溢出将产生越界中断	w字段的溢出自动加入到页号中

段页式系统

在段式存储管理中结合分页存储管理技术，在一个分段内划分页面，就形成了段页式存储管理。

程序地址空间

地址结构=段号+段内页号+页内位移

每一个程序一张段表，每个段对应一张页表，段表中的地址是页表的起始地址

段页式地址变换要得到物理地址需要经过3次主存访问（当段表、页表都在主存中）：

1. 访问段表，得到页表起始地址
2. 访问页表，得到主存块号
3. 将主存块号与页内位移组合得到物理地址

问题

第七章 习题及解答

7-11如图7.45所示，主存中有两个空白区。现有如下程序序列：程序1要求50KB；程序2要求60KB；程序3要求70KB。若用首次适应算法和最佳适应算法来处理这个程序序列，试问：哪一种算法可以分配得下 ? 简要说明分配过程 (假定分区描述器所占用的字节数已包含在程序所要求的主存容量中) 。

答：(1) 首次适应法：

程序1要求50KB，在起始地址为150KB，大小为120 KB的空白区进行分割。120KB-50KB=70KB，分割后剩70KB 的空白区。

程序2要求60KB，在剩余的70KB空白区进行分割。70KB-60KB=10KB，分割后剩 10KB的空白区。

程序3要求70KB，在起始地址为300KB，大小为78KB的空白区进行分割。78KB-70KB=8KB，分割后剩8KB 的空白区。

因此首次适应法可满足该程序序列的需求。

(2) 最佳适应法

程序1要求50KB，在起始地址为300KB，大小为78 KB的空白区进行分割。78KB-50KB=28KB，分割后剩28KB 的空白区。

程序2要求60KB，在起始地址为150KB，大小为120KB的空白区进行分割。120KB-60KB=60KB，分割后剩60KB的空白区。

程序3要求70KB，。此时系统中有大小为 28KB 和60KB 的两个空白区，它们均不能满足程序3 的需求。

因此最佳适应法不能满足该程序序列的需求。