【操作系统】内存管理

内存管理：

1. OS负责内存空间的分配与回收
2. OS需要提供某种技术从逻辑上对内存空间进行扩充
3. OS需要提供地址转换功能，负责程序的逻辑地址与物理地址的转换

• 绝对装入：编译时将逻辑地址转为物理地址（单道程序阶段）
• 可重定位装入：装入时将逻辑地址转为物理地址（早期多道批处理阶段）
• 动态运行时装入：运行时进行地址转换（现代操作系统）

4. OS需要提供内存保护功能，保证各程序在各自存储空间内运行，互不干扰

• 方法一：在CPU中设置一对上下限寄存器：存放进程的上下限地址，CPU直接判断是否越界
• 方法二：采用重定位寄存器和界地址寄存器：重定位寄存器存放进程的起始物理地址，界地址寄存器存放进程的最大逻辑地址。首先通过界地址寄存器判断是否越界，然后将其与重定位寄存器相加得到物理地址

内存空间的扩充：

覆盖技术：将程序分为多个段，常用的段常驻内存，不常用的段需要时调入内存。
缺点：对用户不透明，增加用户编程负担。因为必须由程序员声明覆盖结构

交换技术：系统将内存某些进程暂时换出外存，将外存中某些已具备运行条件的进程挂入内存。[[进程与线程1#调度|中级调度]]
通常将磁盘空间分为文件区和对换区。文件区主要存放文件，主要追求存储空间利用率，因此对文件区空间的管理采用离散分配方式。对换区只占磁盘小部分，被换出的进程数据存放在对换区，主要追求换入换出速度，因此采用连续分配。

Tip：PCB会常驻内存，不会被换出
覆盖是在同一程序或进程中的，而交换是在不同进程之间的。
局部性原理：时间局部性，如果执行了程序中某条指令或访问了某个数据，不久后很有可能再次执行。空间局部性，一旦程序访问了某个存储单元，在不久后，其附近存储单元也很有可能被访问。

虚拟存储技术：
虚拟内存：内存的实际物理量没有变，只是让用户觉得内存容量很大。它的实现需要建立在离散分配的内存管理方式上。在程序执行过程中，当所访问的信息不在内存时，由OS负责将所需信息从外存调入内存，若内存空间不够 ，OS负责将暂时用不到的信息换出内存。
虚拟内存特征：

• 多次性：无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存
• 对换性：作业运行时无需一直常驻内存，允许在运行过程中将作业换入换出
• 虚拟性：逻辑上扩充了内存容量，使用户看到的内存容量远大于实际容量
  请求分页管理方式：
  页表的改变：
  为了请求调页，操作系统需要知道每个页面是否已调入内存，如果在外存中，还需要知道在外存的位置。所以页表增加一列状态位，一列外存地址。
  为了页面置换，操作系统需要知道哪些页面未被修改过，哪些页面被经常访问，所以页表增加一列修改位，一列访问字段。
  当要访问的页面不在内存中，产生缺页中断，属于内中断。OS的缺页中断处理程序处理中断，此时缺页的进程阻塞。处理中断的方式是，保存现场，寻找到一个空闲的页框，将数据调入内存，然后修改页表和快表。
  页面置换算法
• 最佳置换算法OPT：在最长时间内不再被访问的页面，统计时间点之后最长时间才会被访问的。操作系统无法提前预判页面访问序列，无法实现。
• 先进先出置换算法FIFO：每次选择淘汰的页面是最早进入内存的页面。会产生belady异常——当为进程分配的物理块数增大时，缺页次数不减反增。
• 最近最久未使用置换算法LRU：根据页表项中的访问字段，每次选择访问字段最小且最久远的的页面淘汰。实现困难，开销大。
• 时钟置换算法CLOCK：又叫做最近未使用算法。为每个页面设置一个访问位，并将内存中的页面设置成循环队列，当某页被访问时，访问位置为1。当需要淘汰一个页面时，检查访问位如果是0，则换出，如果是1，则置为0。如果第一轮扫描所有页面都是1，则将其访问位依次置为0后进行第二轮扫描。
• 改进的时钟置换算法：为页面设置一个修改位，修改位=1，表示页面修改过。只有被淘汰的页面被修改过时，才需要写回外存。在CLOCK的基础上，应优先淘汰没有修改过的页面。
  第一轮：寻找访问位=0&&修改位=0的页面。没找到进行第二轮扫描。
  第二轮：寻找访问位=0&&修改位=1的页面，同时将所有扫描过的页面访问位置为0。没找到进行第三轮扫描。
  第三轮：寻找访问位=0&&修改位=0的页面。没找到进行第四轮扫描。
  第四轮：寻找访问位=0&&修改位=1的页面。
  页面分配策略
  驻留集：指请求分页存储管理中给进程分配的物理块的集合、
  驻留集的大小：
  固定分配：OS为每个进程分配一组固定数目的物理块
  可变分配：先为每个进程分配一定数目物理块，在进程于小宁期间，根据情况适当增加或减少。
  局部置换：发生缺页时只选择进程自己的物理块进行置换
  全局置换：将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程。

调入页面时机：

1. 预调页策略：根据局部性原理，一次调入若干个相邻的页面。主要用于进程的首次调入。
2. 请求调页策略：运行期间发现缺页时调入，I/O开销较大。
   调入页面位置：
3. 系统拥有足够的对换区空间时，内存与对换区进行，保证调入调出速度快。
4. 系统缺少足够对换区空间时，凡是不会被修改的数据直接从文件区调入，对可能被修改的部分，需借助对换区。

抖动：刚换出的页面又马上换入内存。刚换入的页面又马上换出内存。
工作集：指在某段时间间隔里，进程实际访问页面的集合。

内存空间的分配与回收

连续分配：

单一连续分配：

内存被分为系统区与用户区。系统区通常位于内存的低地址部分，存放操作系统的相关数据，用户区存放用户进程相关数据，内存中只有一道用户程序。
没有外部碎片，有内部碎片
优：实现简单，无外部碎片，可以采用覆盖技术扩充内存，不一定需要采取内存保护
缺：只能用于单用户、单任务的操作系统，由内部碎片，存储器利用率低

固定分区分配：

分区大小相等，或，分区大小不等。
分区说明表：一个记录分区情况的数据结构。每个表项对应一个分区，包括分区的大小、起始地址、状态。
没有外部碎片，有内部碎片
优：实现简单
缺：用户程序太大，所有分区都无法满足

动态分区分配

不会预先划定内存分区，而是在进程装入内存时，根据进程的大小动态建立分区。
空闲分区表、空闲分区链：一种记录内存使用情况的数据结构
没有内部碎片，但是有外部碎片
外部碎片可以用”紧凑“技术解决。将进程挪挪位。

内部碎片：分配给某进程的内存区域中，进程没用上的部分
外部碎片：内存的某些空闲分区由于太小而难以利用

动态分区分配算法
首次适应算法：
空闲分区以地址递增的次序排列。每次都从低地址开始查找，找到第一个能满足大小的空闲分区。
最佳适应算法：
为了保证当大进程到来时能有连续大片空间，可以尽可能多的留下大片空闲区。
空闲分区按照容量递增次序排列。找到大小能满足要求的第一个空闲分区。
缺：每次都选最小的分区进行分配，会留下越来越多、很小、难以利用的内存块。因此会产生很多外部碎片。
最坏适应算法：
空闲分区按容量递减次序链接。每次内配内存时按顺序查找到能满足要求的第一个空闲分区。
缺：较大的连续空闲分区被迅速用完。
邻近适应算法
空闲分区按地址递增次序排列，每次分配内存时从上一次查找结束的位置继续查找。
缺：高地址的大分区被用完。

非连续分配

分页存储

将内存空间分为大小相等的分区，每个分区是一个页框，每个页框有一个编号，叫做页框号，从0开始编。（页框号=页帧号=内存块号=物理块号=物理页号）
将进程逻辑地址空间分为与页框大小相等的部分，每个部分称为一个页面，每个页面有一个编号，叫做页号，从0开始编。
页表：操作系统为了知道进程的每个页面在内存中存放的位置，为每个进程建立一张页表，因此通常存在PCB中。页表记录的只是内存块号，而不是内存块的起始地址。每一个页表项是连续存放的，因此i号页表项的存放地址=X+3*i，X为起始地址。J号内存块的起始地址=J*内存块大小
逻辑地址A=P号页面在内存的起始地址+页内偏移量

1. 确定逻辑地址A对应的页号P。P=A/页面长度
2. 通过查找页表，找到页号P在内存的起始地址
3. 确定页内偏移量W。W=A%页面长度
   如果页的大小是2的整数次幂：
   逻辑地址分为两部分，前一部分是页号，后一部分为页内偏移地址。
   基本地址变换机构：
   借助进程的页表将逻辑地址转换为物理地址。
   页表寄存器PTR：存放页表在内存中的起始地址F和页表长度M。进程未执行时，F和M都放在PCB中，当进程被调度时，OS内核会把它们放在PTR中。
   因此地址变换步骤是：
4. 从逻辑地址A中计算出页号P和页内偏移量W
5. 根据PTR的页表长度M和页号P判断页号是否越界。如果P>=M，越界中断。
6. 根据PTR中的F与A的P相加，查询页表，找到对应的页表项，确定页面存放的内存块号
7. 内存块号与A的W相结合得到物理地址E
8. 根据E访问目标内存单元

页表长度：页表中总共有几个页表项
页表项长度：每个页表项占多大内存空间
页面大小：一个页面占多大存储空间
E=b*L+W，其中b是内存块号。将内存块号与页内偏移量拼接起来就是物理地址。

具有块表的地址变换机构：
块表：又称联想寄存器TLB，是一种访问速度比内存快很多的高速缓存，用来存放最近访问的页表项的副本，可加速地址变换的速度。
地址转换步骤：

1. 从逻辑地址A中计算出页号P和页内偏移量W
2. 根据PTR的页表长度M和页号P判断页号是否越界。如果P>=M，越界中断。
3. 进程刚开始运行，快表内容为空，因此系统未命中快表，访问慢表，也就是页表，同时将查询到的结果复制一份给快表。
4. 得到内存块号，与页内偏移量结合获得物理地址。
   如果快表命中，则访问某个逻辑地址仅需要一次访存操作，即访问该物理地址对应的内存单元。如果快表未命中，则访问某个逻辑地址需要两次访存。但如果快表已满，则需要按照一定算法对旧的页表项进行替换
   两级页表：
   单级页表要求所有页表项连续存放。如果页表很大时，需要占用很多连续的页框。且没有必要让整个页常驻内存，因为局部性原理。
   两级页表：将单级页表拆分为一个个小页表，然后就可以离散存放，再增加一级页表存储小页表的映射。
   可类比一本书的目录。

分段存储

逻辑地址由两部分组成：段号S和段内地址W。段号位数决定了每个进程最多可以分为多少个段，段内地址位数决定每个段的最大长度。
段表：为每个进程建立一张段映射表，能从物理位置找到各个逻辑段的存放位置。段表项包括段长C和基址b。各段表项长度是相同的，但是各段长度不同。
段表寄存器：段表始址F和段表长度M
与页式存储系统不一样的是，每段长度不同，所以增加了对段内地址是否越界中断的判断即W>=C。

分页与分段的区别
页是信息的物理信息，分页的主要目的是为了实现离散分配，提高内存利用率，分页仅仅是系统管理的需求，对用户不可见。页的大小固定且由系统决定。
段是信息的逻辑单位，分段的主要目的是为了更好地满足用户需求，分段对用户可见。段的长度不固定决定于用户编写的程序。
分段比分页更容易实现信息的共享和保护。因为分页时一个进程不能完全装入一个页中，因此不便操作。

段页式管理

段页式：将进程按逻辑分段，再将各段分页。
逻辑地址由三部分构成：段号，页号和页内偏移量。段号的位数决定每个进程可以分为几段，页号位数决定每个段最大有几页，页内偏移量位数决定页面大小、内存块大小是多少。

内存映射文件

特征：

• 进程可以使用系统调用，请求操作系统将文件映射到进程的虚拟地址空间
• 以访问内存的方式读写文件
• 进程关闭文件，操作系统自动将被修改的文件写回磁盘。
• 多个进程可以用页表映射同一个文件，实现共享。
  优：变成更简单，文件数据的读写完全由操作系统负责，I/O效率由OS负责优化