操作系统原理，地址重定位；物理内存数据，分配，回收；内存管理，固定分区和可变分区存储，页式段式存储

截图来自b站北大陈教授网课

地址重定位

一、内存地址中多个进程被分割在不同的独立的地址空间中
1、程序通常以可执行文件的格式保存在磁盘上，将程序从磁盘装载内存中后才可以运行。
2、多道程序设计模型中允许多个程序同时进入内存
3、操作系统为了将各个进程隔离开，在内存中为每个进程分配了自己的地址空间，一个进程执行时不能访问另一个进程的地址空间，进程也不能对内存执行不合适的操作，例如：访问不属于自己地址空间的内存地址，比如数组访问越界。

二、进程需要的空间

1、在进程空间中的地址不是最终的物理地址，可以理解为是逻辑地址或者相对地址，首地址为0
2、进程运行前无法计算出物理地址，因为并不知道会被加载到内存的什么地方
3、将进程中的逻辑地址装换位可以直接访问的物理内存地址，需要地址重定位的支持，又有地址变换，翻译，映射等术语名称
4、地址重定位就是将进程中逻辑地址装换位内存实际的地址的过程

三、地址重定位种类
1、静态重定位
用户程序加载到内存中时，一次性将逻辑地址转换为物理内存地址，一般由软件完成，但是如果进程改变了位置，就必须重新重定位
2、动态重定位
在进程执行时逐条指令的完成地址转换，需要硬件部件支持，是常用的方法，例如下图

物理内存管理

一、物理内存划分与数据结构
1、物理内存可以在逻辑上被等长划分或者不等长划分，并由相应的数据结构进行管理
2、等长划分的内存块可以使用位图进行管理，每个分配单元对应于位图中的一位，分别用0或1表示空闲与占用，等长划分示例

3、不等长划分的内存可以使用空闲区表（已分配区表）进行管理，表中的每一项记录了空闲区的起始地址，长度，标志

4、或者用空闲区链表，链表可以管理任意划分的物理内存，但是本身节点会占用一些位置，消耗大一点

二、内存分配算法
1、首次适配first fit，在空闲区表中找到第一个能满足进程要求的空闲区
2、下次适配next fit，从上次找到的空闲区处接着查找
3、最佳适配best fit，查找整个空闲区表，找到能够满足进程要求的最小空闲区
4、最差适配worst fit，总是分配满足进程要求的最大空闲区
5、空闲区分配给进程使用后，将进程需要大小的空间给进程使用，多出来的部分成为新的空闲区

三、内存回收算法
1、当某一块物理内存归还后，前后空闲空间合并，修改内存空闲区表
2、结合四种情况进行管理：上相邻，下相邻，上下相邻，上下不相邻

四、内存系统举例：伙伴系统（Linux内存管理采用的方案）
1、将内存按照2的幂进行划分，组成若干空闲块链表，查找链表找到能满足进程的最佳空闲块
2、分配算法：
2.1、将整个可用空间看作一块，大小为2^u
2.2、假设进程申请的空间大小为s，空间块满足2^(u-1)<s<2u，是分配整个空闲块给进程，不满足此条件则将空闲块平分为两个大小为2^(u-1)的空闲块，从同一个块
2.3、继续比较和划分，直到找到大于或等于s的最小空闲块
3、回收算法
当被回收的空闲块和相邻的空闲块组成了伙伴关系时，将两个伙伴合并为大的空闲区，合并得出的空闲区也有空闲伙伴时，继续合并，直到同时空闲的伙伴空闲区全部合并完。

系统进程的内存管理方案

一、进程装载到内存后，占用内存的方式
1、连续性占用内存的方式包括：单一连续分区，固定分区，可变分区，
2、非连续性占用内存的方式包括：页式，段式，段页式

二、单一连续区
一段时间内只有一个进程在内存中，简单但是内存利用率低，进程和操作系统在内存中的分布如下

三、固定分区
1、把内存空间分割陈若干区域，称为分区
2、每个分区大小等或不等，但大小固定不变
3、每个分区只能装一个进程
4、可以为每个分区分配一个进程等待队列，让进程等待在符合条件的分区队列中；或者分区使用同一个进程等待队列，将进程装载到符合条件的分区，二者图示如下

四、可变分区
1、根据进程的需要，吧内存空闲空间分割出一个分区，分配给该进程
2、剩余部分成为新的空闲区
3、分配图示如下

4、洞的出现表明了有内存碎片，这种进程间的碎片称为外碎片，会导致内存的利用率下降
5、解决内存碎片需要压缩技术，使用内存移动程序移动进程在内存中的位置，将所有小的空闲区合并为较大的空闲区，又有搬家技术等术语名词，使用时需要考虑开销和时机，

五、页式存储
1、页式存储思路：
1.1、将进程地址空间划分为大小相等的部分，称为页或页面，从0开始编号
1.2、将内存空间划分为大小相等的区域，称为页框，从0开始编号，页框又称页面，页帧，内存块
1.3、内存分配规则：以页为单位进行分配，按照进程需要的页数分配，逻辑上相邻的页，物理上不一定相邻
1.4、典型的页面尺寸：4K或4M

2、逻辑地址组成
2.1、逻辑地址被分为两部分，分别是页号和页内地址
2.2、在32位计算机中，逻辑地址是32位的整型，第0-11位存放页内偏移，页内偏移的最大数就是页面尺寸，32位计算机中的页面大小是4K，图示如下

2.3、对进程逻辑地址的划分是由系统完成的，用户对此无感知

3、地址重定向
3.1、逻辑相邻的页面在物理页面中可以是不相邻的
3.2、逻辑页面到物理页面的映射关系存放在页表中，

3.3、页表由页表项组成，每个页表项存放了逻辑页号和页框号的对应关系，每个进程有一个页表，存放在内存中。
3.4、物理内存因为是连续的登场空间，使用位图就可以管理
3.5、地址转换，由硬件支持，CPU取到逻辑地址，自动划分为页号和业内地址，用页号查页表得到页框号，再与页内偏移拼接成为物理地址
3.6、内碎片，页框是分配内存资源的最小单位，如果某进程需要5页框+1条指令，就会为其分配6个页框，最后那一页浪费了大量空间，称为内碎片

六、段式存储
1、段式存储思路
1.1、用户进程地址空间：按程序自身的逻辑关系划分为若干个程序段，每个程序段都有一个段名
1.2、内存空间被动态划分为若干长度不同的区域，称为物理段，每个物理段有起始地址和长度确定。
1.3、内存分配规则：以段为单位进行分配，每个段在内存中占据着连续的空间，逻辑段相邻的物理段可以不相邻。

3、逻辑地址与重定位
3.1、逻辑地址由段号和端内偏移组成，但段号和段内地址必须显式给出，而不是由系统自动划分

3.2、主程序段的划分示例

3.3、逻辑段通过段表映射到物理内存的段中，段表中的每项记录了段号，段首和段长度之间的关系，每个进程一个段表，存放在内存中

3.4、段式存储是不等长的内存划分，管理时可以使用空闲区表或者空闲区链表
3.5、地址转换：硬件完成，CPU取到逻辑地址，用段号查段表，得到该段在内存的起始地址，与端内偏移地址计算出物理地址

七、段页式存储
1、段页式存储的思路，结合段式和页式的有点，克服二者的缺点
1.1、先按段划分，每一段按页划分
1.2、逻辑地址结构是段号+端内地址（页号+页内地址）

1.3、内存划分同页式存储方案
1.4、内存分配以页为单位分配

2、数据结构与相关操作
2.1、段表：记录每一段的页表起始地址和页表长度
2.2、页表：记录逻辑页号与页框号的对应关系
2.3、一个进程有一个段表，每一段有一个页表，一个进程可以有多个页表
2.4、空闲区管理，内存分配回收同页式管理
2.5、地址转换，过程比较复杂，消耗比较高