操作系统知识总结（三）——内存

1.内存管理

1.1 内存的基础知识

1、什么是内存

存储单元：每个地址对应一个存储单元

内存地址：

2、进程运行的基本原理

指令的工作原理：

逻辑地址vs物理地址：逻辑地址就是相对地址

从写程序到程序运行：编辑-编译-链接-装入

三种链接方式：

• 静态链接（在程序运行前，先将各目标模块及它们所需的库函数连接成一个完整的可执行文件）

• 装入时动态链接（将各目标模块装入内存时，边装入边链接的链接方式）

• 运行时动态链接（在程序执行中需要该模块时，才对它进行链接，其优点时便于修改和更新。）

三种装入方式：

• 绝对装入（在编译的时候就知道程序放在内存的哪个位置）

• 静态重定位（装入时将逻辑地址转表为物理地址，一次性分配所有要求的全部空间）

• 动态重定位（把地址转化推迟到程序真正要执行时才进行，需要重定位寄存器）

  • 需要基址寄存器和界限寄存器的硬件支持

1.2 内存管理的概念

1、内存空间的分配与回收

2、内存空间的扩充

内存的虚拟性

3、地址转换

逻辑地址和物理地址转换

4、内存保护

• 设置上下限寄存器

• 采用重定位寄存器（基址寄存器）存放起始物理地址和界地址寄存器（限长寄存器）存放最大逻辑地址

1.3 覆盖与交换!!!

内存空间的扩充

覆盖技术：将程序分为多个段，内存分为”固定区“和”覆盖区“，需要常驻的放在”固定区“，调入后就不再调出，不常用的段放在”覆盖区“，需要用到时调入内存，用不到时掉出内存

特点

• 只能发生在没有调用关系的模块间

• 程序员须给出模块间的逻辑覆盖结构

• 发生在运行程序的内部模块间

交换技术：内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存（PCB会常驻内存，不会被换出）

特点

• 以进程为单位

• 不需要模块间的逻辑覆盖结构

• 发生在内存进程间

虚拟存储技术：每个进程拥有自己的地址空间，这个空间被分割成多个大小相等的块，每一块称作页（页面page），让部分页面进驻内存也能顺利执行完成。

1.4 连续分配管理方式

连续分配方式：

单一连续分配：内存被分配为系统区和用户区，系统区在低地址，用户区是一个用户独享

固定分区分配：将用户区分割为若干固定分区给各道程序，分割策略有分区大小相等和分区大小不相等，可以建议一个分区说明表来管理各个分区

动态分区分配：可变分区分配，不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。

内部碎片：分配给某进程的内存区域中，如果有些部分没有用上

外部碎片：是指内存中的某些空闲分区由于太小而难以利用（如果有外部碎片，可以采用紧凑技术）

1.5 动态分区分配算法

1、首次匹配算法（First Fit)

算法思想：每次从低地址开始查找，找到第一个能满足大小的空闲分区

2、最佳匹配算法(Best Fit)

算法思想：为了保证“大进程”到来时能有连续的大片区域，可以尽可能留下大片的空闲区，优先使用更小的空闲区。

空闲分区按容量递增次序链接，分配内存时顺序查找空闲分区链

缺点：会留下小碎片

3、最坏匹配算法(Worst Fit)

算法思想：和最佳适应算法相反，按容量递减次序排列，每次尽可能用大的分区

4、领近/ 下次 匹配算法(Next Fit)

算法思想：每次从上次查找结束的位置开始检索

缺点：大空间容易被用完

1.6 基本分页存储管理的基本概念

允许一个进程分散地装入道许多不相邻的位置

连续分配：为用户进程分配连续的内存空间

非连续分配：为用户进程分配分散的内存空间

页（页面）：

将内存分为大小相等的小分区“页框”，将用户的进程空间也分为大小相等的一个个区域，以页框的基本单位分配给每个进程片

分页原理：

• 页（逻辑地址）到帧（物理地址）的映射

• 逻辑地址中的页号（页面号）是连续的

• 物理地址中的帧号是不连续的

• 不是所有的页都有对应的帧

分页管理：物理地址 = 页面的其实位置 + 页内偏移量

计算机中用2的整数倍表示页面的大小

页表：存放页号和物理块号的对应关系

1.7 基本地址变换机构

        页表寄存器（PTR），存放页表在内存中的起始地址F和页表长度M，进程未执行时，页表的起始地址和页表的长度放在进程控制块（PCB）中，当进程被调度时，操作系统内核会把它们放在页表寄存器中。

1.8 具有快表的地址变换机构

1、局部性原理（程序在执行过程中的一个较短时期，所执行的指令地址和指令的操作数地址，分别局限于一定区域）

时间局部性：访问某个变量后，在不久的将来还会被访问

空间局部性：程序访问了某个存储单元，不久之后，其附近的存储单元也很有可能被访问

分支局部性：一条跳转指令的两次执行很可能跳到相同的内存位置

2、什么是快表（TLB）

快表：又称联想寄存器（TLB），是一种访问速度比内存快很多的高速缓冲存储器，用来存放当前访问的若干页表项，以加速地址变换的过程。与此对应，内存中的页表常称为慢表。

• 如果TLB命中，物理页号可以很快被获取

• 若干TLB未命中，对应的表项被更新到TLB中

1.9 两级页表

1、单级页表存在什么问题？如何解决？

所有页表项必须连续存放，页表过大时需要很大的连续空间

在一段时间内并非所有页面都用得到，因此没必要让整个页表常驻内存

2、两级页表的原理、逻辑地址结构

将长长的页表再分页

逻辑地址结构：（一级页号、二级页号、页内偏移量）

页目录表、外层页表、顶级页表

3、如何实现地址变换？

按照地址结构将逻辑地址拆分成三部分

从PCB中读出页目录表始址，根据一级页号查页目录表，找到下一级页表在内存中的存放位置

根据二级页号查表，找到最终想访问的内存块号

结合页内偏移量得到物理地址

4、两级页表问题需要注意的几个细节

多级页表中，各级页表的大小不能超过一个页面。若两级页表不够，可以分更多级

多级页表的访问次数（假设没有快表结构）——N级页表访问一个逻辑地址需要N+1次访存

1.10 基本分段存储管理方式

1、什么是分段？

进程的地址空间：按照程序自身的逻辑功能划分为若干个段，每段有段名，每段从0开始编址

段号的位数决定了每个进程最多可以分几个段

段内地址位数决定了每个段的最大长度是多少

目的是为了方便实现共享

2、什么是段表

段表：段映射表

每个程序被分段后，用段表记录该程序在内存中存放的位置

段表：段号 段长 基址

3、如何实现地址变换

段访问：逻辑地址由二元组(s, addr)表示

s --- 段号

addr --- 段内偏移

4、分段、分页管理的对比

页：信息的物理单位，实现离散分配，提高内存利用率，地址是一维的，访存两次

段：信息的逻辑单位，对系统可见，地址是二维的，访存3次

分段比分页更容易实现信息的共享和保护（不能被修改的代码称为纯代码和可重入代码，不属于临界资源）

1.11 段页式的管理方式

1、分页、分段管理方式最大的优缺点

分页：利用率高，碎片少，不方便进行信息共享和保护

分段：方便信息共享和保护，如果段长大，容易产生外部碎片

2、分段+分页的结合——段页式管理方式

先分段再分页

段号+页号+页内偏移量

地址结构是二维的

3、段表、页表

4、如何实现地址变换

2.虚拟内存

2.1 虚拟内存的基本概念

思路： 将不常用的部分内存块暂存到外存

原理

装入程序时： 只将当前指令执行需要的部分页面或段装入内存

缺页（指令执行中需要的指令或数据不在内存）时： 处理器通知操作系统将相应的页面或段调入内存

操作系统将内存暂时不用的页面或段保存在外存

实现方法

虚拟页式存储

虚拟段式存储

1、传统存储管理方式的特征、缺点

之前讲的

一次性：作业必须全部装入内存后才能开始运行，并发性下降

驻留性：一旦作业被装入内存，就会一直驻留在内存

2、局部性原理

• 时间局部性

• 空间局部性

• 高速缓存技术

3、虚拟内存的定义和特征

虚拟内存最大容量是计算机地址结构确定的

虚拟内存的实际容量=min(内存和外存容量之和，CPU寻址范围)

eg：某计算机地址结构为32位，按字节编址，内存大小为512MB，外存大小为2DB.

则虚拟内存的最大容量为 2^32B=4GB

虚拟内存的实际容量=min(2^32B,512MB+2GB)=2GB+512MB

• 多次性：无需在作业运行时一次性全部装入内存，而是允许被分成多次调用内存

• 对换性：在作业运行时无需一直常驻内存，而是允许在作业运行过程中，将作业换入换出

• 虚拟性：从逻辑上扩充了内存的容量，使用户看到的内存容量，远大于实际的容量

4、如何实现虚拟内存技术

在程序执行过程中，当所访问的信息不再内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。

若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。

2.2 请求分页管理方式

1、页表机制

请求分页存储的页表：

内存块号 状态位 访问字段 修改位 外存地址

2、缺页中断机构

内中断，可被修复

3、地址变换机构

2.3 页面置换算法

1、最佳置换算法（OPT）

每次选择淘汰的页面是以后永不使用或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率。

实际上不知道后面的序列

2、先进先出置换算法（FIFO）

每次选择淘汰的页面是最早进入内存的页面

Belady异常，当分配的内存块增大时，缺页次数反而增加

3、最近最久未使用置换算法（LRU）

每次淘汰最近最久未使用的页面

4、时钟置换算法（最近未用算法，CLOCK）

简单的：最多经历两轮扫描，初始为1，扫一下为0，再扫一下被踢

5、改进型的时钟置换算法

优先淘汰没有被修改过的，因为没有修改过的不用进行IO操作00->01（改）->00->01

2.4 页面分配策略

1、驻留集

指请求分页存储管理中给进程分配的物理块的集合

2、页面分配、置换策略

• 固定分配局部替换：驻留集大小不可改变

• 可变分配全局替换：可以将操作系统保留的空闲物理块分配给缺页进程

• 可变分配局部替换：只能选进程自己的物理块置换

3、调入页面的时机

预调页策略：一次调用若干个相邻页面，运行前调入

请求调页策略：运行时缺页再调入

4、从何处调页

对换区：快，采用连续分配方式

文件区：慢，采用离散分配方式

5、抖动（颠簸）现象

当内存中已无足够的空间来运行新的进程时，系统会启动将内存暂时不能运行的进程放入外存，由此造成进程的频繁换入和换出。

原因：

随着驻留内存的进程数目增加，分配给每个进程的物理页面数不断减小，缺页率不断上升

6、工作集

指在某段时间间隔里，进程实际访问页面的集合

2.5CPU与并发进程数关系

CPU利用率与并发进程数存在相互促进和制约的关系：

• 进程数少时，提高并发进程数，可提高CPU利用率

• 并发进程导致内存访问增加

• 并发进程的内存访问会降低了访存的局部性特征

• 局部性特征的下降会导致缺页率上升和CPU利用率下降