OS-3.1 内存

3.1 内存

一.内存的基础知识

内存有什么用？

==程序从硬盘调入内存，在内存中被CPU处理。==

==如何区分内存中的多个程序放置的位置呢？ →需要对内存进行编址。==

从写程序到程序运行(4)

① 编写源代码 –→

② 编译（高级语言（高级代码）到机器语言（机器指令）–→

③ 链接（把code连接到一起，加上库函数，且==形成逻辑地址==）–→

④ 装入（装入内存，==形成物理地址==）

链接的三种方式(3)

静态链接：程序运行前一次性链接，之后不拆开。
装入时动态链接：边装入内存边链接。
运行时动态链接：程序运行时才链接。（便于修改和更新，便于实现对目标模块的共享）

机器指令的工作原理

结构：操作码+若干参数（可能包含地址参数）

指令告诉CPU从哪个地址读/写数据。

或者告诉CPU对数据进行什么处理。

物理地址 VS 逻辑地址

程序经过编译、链接后生成的指令中指明的地址是逻辑地址。

逻辑地址→物理地址【3种装入方式】⭐

（代码中的）逻辑地址→（内存中的）物理地址

==绝对装入==
==可重定位装入（静态重定位）==
==动态运行时装入（动态重定位）==

① 绝对装入：

编程阶段就把物理地址计算好。

只适用于单道程序环境。（灵活性低，不可迁移）

② 静态重定位：

==在装入时一次完成逻辑地址转为物理地址。==

进程装入内存时，分配进程要求的全部连续地址空间。

==进程一旦进入内存，就不可以移动位置了。==

③ 动态重定位：

**系统 ==只有一个== **==重定位寄存器==，保存存入该模块存放的==（物理）==起始位置（又叫==基址寄存器==）。

【==物理地址== = 重定位寄存器的值+逻辑地址，==这一步就是硬件地址变化机构做的==】

==在程序真正要执行的时候才进行==，逻辑地址转物理地址。

只装入部分代码，根据需要动态调入调出内存。

允许程序在内存中发生移动。

Note：还有一个叫可重定位装入程序的东西。

回顾

二.==内存==管理的概念⭐

OS负责：

① 对内存空间的==分配与回收==（==连续分配和非连续分配方式==）
② 对内存空间的==扩展==（覆盖，交换和==虚拟内存技术==）
③ 提供==地址转换功能==，程序的逻辑地址与物理地址之间的转换。（==三种装入方式==）
④ 提供==内存保护==功能。（==保证各自进程==在自己的空间运行，==不会越界访问==）
- ①：CPU中的上下限寄存器，进行越界检查
- ②：重定位寄存器和界地址寄存器进行越界检查
  - 重定位寄存器存放的是进程的起始物理地址。
  - 界地址寄存器保存进程的最大逻辑地址。
- Note：内存保护由OS和硬件一起完成，硬件主要进行安全性的设置。

回顾

三.进程的内存映像

进程的都是虚址。（eg malloc分配的）

②内存扩展 – 覆盖，交换，虚存

覆盖技术
交换技术
虚拟存储技术（之后学到）

覆盖技术

把程序分成多个段。

==把内存分为一个固定区和多个覆盖区==

常用的段放在固定区，调入之后不再调出。

不常用的段放在覆盖区，需要时调入内存，不需要时调出内存。

必须由程序员实现，==对用户不透明，增加编程负担。==

交换技术

==进程在内存和磁盘之间动态调度。==

when内存空间紧张时，系统将内存中的某些进程暂时调出外存，把外存中已具备条件的进程换入内存。

Note：==中级调度==，就是决定把哪一个处于挂起状态的进程重新调入内存。

回顾

**==覆盖==**，是在==同一个进程或程序中==进行的。

**==交换==**，是在==不同进程（或作业）之间的==。

①内存空间的分配 – 连续分配管理方式

连续分配：==系统给进程分配的==必须==是一个连续的内存空间==。

==分区存储管理==，比分页分段等存储管理实现简单。（不需要特定的数据结构如页表段表）

单一连续分配
固定分区分配
动态分区分配

连续分配的缺点是：内部碎片和外部碎片都有。

A.单一连续分配

==内存被分为系统区和用户区。==

==内存中只能有一道用户程序==，即用户程序独占整个用户区。

缺点：有内部碎片。且只能用于单用户、单任务的操作系统。

B.固定分区分配

==内存分为多个分区。==（分区大小可以相等，可以不等）

（OS需要建立一个==分区说明表==）

==每一个分区只能装入一道程序==，【故无法实现多个进程共享同一个内存区域】

缺点：有内部碎片。

C.动态分区分配

==不会预先划分内存区==，（在进程装入内存==时==），==根据进程大小建立合适的分区。==

1.OS建立一个空闲分区表或者空闲分区链。
2.OS用动态分区分配算法（选择某一个分区进行分配）。
3.相邻的空闲分区合并。

没有内部碎片，==有外部碎片。==

外部碎片：内存中某些内存分区太小难以利用。
解决外部碎片：紧凑技术。（挪移拼接）

1.建立空闲分区表或者空闲分区链

2.用动态分区分配算法（之后介绍）

3.两个相邻的空闲分区合并。

回顾

C.动态分区分配算法(4+3)

==基于顺序搜索的分配算法：== 首次适应，最佳适应，最坏适应，邻近适应算法
==基于索引搜索的算法：== 快速适应，伙伴系统，哈希算法。

a.基于顺序搜索的分配算法

首次适应：==按低地址开始寻找==（在空闲分区表/分区链找到第一个大小满足的空闲分区）

邻近适应：每次分配内存**==从上次结束位置==**开始查找空闲分区表/链。（空闲分区以地址递增的顺序排列（可以是循环链表）

最佳适应：优先==使用更小的空闲分区==。（把空闲分区按大小递增链接，如果有删去的得全部重新排序）

缺点：会留下很多很小的内部碎片。（eg10给了9）

最坏适应：优先==使用最大的空闲区==。

缺点：之后有大进程来的话，没有空闲分区可用。

b.基于索引搜索的分配算法

事先建立索引表（如链表数组、位图、哈希表），按分区大小分类管理空闲分区，分配时直接索引到合适大小的分区，避免遍历整个空闲链表，从而提高分配速度。

算法	索引方式	分配速度	合并难度	碎片情况
快速适应	按固定大小分类	极快（O(1)）	困难	内部碎片
伙伴系统	按 2 的幂分类	较快（对数级）	简单（合并伙伴）	内部碎片
哈希算法	哈希函数映射	较快（+链内查找）	取决于链表管理	较灵活