绝对装入：在编译时，如果知道程序将放到内存中的哪个位置，编译程序将产生绝对地址的目标地址。装入程序按照装入模块中的地址，将程序和数据装入内存。
静态重定位：又称可重定位装入。编译、链接后的装入模块的地址是从0开始的，指令中使用的地址、数据存放的地址都是相对于起始地址而言的逻辑地址。
动态重定位：又称动态运行时装入。编译、链接后的装入模块的地址是从0开始的，并不会立即把逻辑地址转换为物理地址，而是把地址转换推迟到程序真正要执行时才进行。
链接的三种方式：
静态链接：装入前链接成一个完整装入模块
装入时动态链接：运行前边装入边链接
运行时动态链接：运行时需要目标模块才装入并链接
内存保护方法：
采用重定位寄存器、界地址寄存器进行越界检查
设置上下限寄存器
覆盖技术的思想：将程序分为多个段。常用的段常驻内存，不常用的段在需要时才调入内存
交换技术：内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中某些具备运行条件的进程调入内存
可重入系统是通过减少对换数量方法来改善系统性能。

连续分配管理方式

单一连续分配

在单一连续分配方式中，内存被分为系统区和用户区。系统区通常位于内存的低地址部分，用于存放操作系统相关数据；用户区用于存放用户进程相关数据。
内存中只能有一道用户程序，用户程序独占整个用户区空间。

优点：实现简单；无外部碎片；可以采用覆盖技术扩充内存；不一定需要采取内存保护。
缺点：只能用于单用户、单任务的操作系统中；有内部碎片；存储器利用率极低。

固定分区分配

将整个用户空间划分为若干个固定大小的分区，在每个分区中只装入一道作业（分区大小不同但预先固定）
分区大小相等：缺乏灵活性，但是适合用于一台计算机控制多个相同对象的集合。
分区大小不等：增加了灵活性，可以满足不同大小的进程需求。根据常在系统运行的作业大小情况进行划分。
建立分区说明表。每个表项包括对应分区的大小、起始地址、状态（是否已分配）

优点：实现简单，无外部碎片
缺点：当用户程序太大，可能所有的分区都不能满足需求，此时不得不采用覆盖技术来解决；会产生内部碎片，内存利用率低。

动态分区分配

可变分区分配：不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区。
系统会采用空闲分区表或空闲分区链来记录内存的使用情况。
存在动态分区分配算法对多空闲分区进行分配
空闲分区表中空闲分区地址相邻则需要进行合并
动态分区分配没有内部碎片，但是有外部碎片。采用紧凑技术来解决外部碎片

首次适应算法（FF）

每次从低地址开始查找，找到第一个能满足大小的空闲分区。（空闲分区以地址递增地次序排列。每次分配内存时顺序查找空闲分区链）

最佳适应算法

为了保证当“大进程”到来时能有连续的大片空间，可以尽可能多地留下大片的空闲区，优先使用更小的空闲区。
空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区数据结构，找到大小能满足要求的第一个空闲分区。
缺点：每次都选最小的分区进行分配，会留下越来越多的、很小的、难以利用的内存块。因此这种方法会产生很多的外部碎片。

最坏适应算法

空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链，找到大小能满足要求的第一个空闲分区。
缺点：每次都选最大的分区进行分配，虽然可以让分配后留下的空闲区更大，更可用，但是这种方式会导致较大的连续空闲区被迅速用完。如果之后有“大进程”到达，就没有内存分区可用了。

邻近适应算法

空闲分区以地址递增的顺序排列。每次分配内存时从上次查找结束的位置开始查找空闲分区链，找到大小能满足要求的第一个空闲分区。

非连续分配管理

分页存储

将内存空间分为一个个大小相等的分区，每个分区就是一个“页框”。将进程的逻辑地址空间也分为与页框大小相等的一个个部分，每个部分称为一个“页”或“页面”。操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分别放入一个页框中。各个页面不必连续存放，可以放到不相邻的各个页框中。每个进程拥有一张页表，且进程的页表驻留在内存中
$逻辑地址对应的物理地址号页面在内存中的起始地址页内偏移量$
$页号逻辑地址页面长度$
$逻辑地址逻辑地址$
页表寄存器：存放页表在内存中的起始地址F和页表长度M。进程未执行时，页表的起址和页表长度放在进程控制块（PCB）中
快表：联想寄存器，是一种访问速度比内存快很多的高速缓存，用来存放最近访问的页表项的副本，可以加速地址变换的速度。
采用多级页表机制，则各级页表的大小不能超过一个页面。
两级页表的访存次数为3次

分段存储

引入段式存储管理方式，主要是为了满足用户方便编程、分段共享、分段保护、动态链接和动态增长
进程的地址空间按照程序自身的逻辑关系划分为若干个段，每个段都有一个段名。以段为单位进行分配，每个段在内存中占据连续空间，但各段之间可以不相邻。
段号的位数决定了每个进程最多可以分几个段；段内地址位数决定了每个段的最大长度是多少

每个段对应一个段表项，其中记录了该段在内存中的起始位置和段的长度
各个段表项的长度是相同的
共享段表是用来实现多个进程共享同一段物理内存空间
分段、分页的对比：
页是信息的物理单位。分页的主要目的是为了实现离散分配，提高内存利用率。分页仅仅是系统管理的需要，完全是系统行为，对用户不可见
段是信息的逻辑单位。分段的主要目的是更好的满足用户需求，分段对用户是可见的。
页的大小固定且由系统决定；段的大小不固定由用户决定
分页的用户进程地址空间是一维的；分段的用户进程地址空间是二维的
分段比分页更容易实现信息的共享和保护

段页式存储

每个段对应一个段表项，每个段表项由段号、页表长度、页表存放块号组成。

虚拟内存

传统存储管理方式的特征：

一次性：作业必须一次性全部装入内存后才能运行
- 大作业无法运行
- 多道程序并发度下降
驻留性：一旦作业被装入内存，就会一直驻留内存中，浪费内存资源
虚拟内存： 当程序执行时，访问信息不在内存时，由操作系统负责将所需信息从外存调入内存，若内存空间不够，由操作系统负责将内存中暂时不用的信息换出到外存。（虚拟内存实现需要建立在离散分配的内存管理方式基础；请求分页存储、请求分段存储、请求段页式存储。比传统存储管理增加了请求调入和请求置换功能）
多次性：程序可以被多次调入内存
对换性：作业经常被换入、换出
虚拟性：从逻辑上扩充了内存的容量
请求分页存储管理的页表五个字段：
内存块号
状态位：是否已调入内存
访问字段：可记录最近被访问过几次，或记录上次访问的时间，供置换算法选择换出页面时参考
修改位：页面调入内存后是否被修改过

外存地址：页面在外存中的存放位置
缺页中断机制（内中断）：在请求分页系统中，每当要访问的页面不在内存时，便产生一个缺页中断，然后由操作系统的缺页中断处理程序处理中断。此时缺页的进程阻塞，放入阻塞队列，调页完成后再将其唤醒，放回就绪队列。

graph TB
  subgraph 地址变换
      B((开始)) -->C{页号>页表长度?}
      C -- 是 -->A((越界中断))
      C -- 否 -->D[CPU检索快表]
      D-->E{页表项在快表中？}
      E -- 否 -->F[访问页表]
      E -- 是 -->G[修改访问位和修改位]
      F-->H{页在内存？}
      H -- 是 -->J[修改快表]
      J-->G
      G-->K[形成物理地址]
      K-->L((地址变换结束))
  end
  H -- 否 -->I[保留CPU现场]
  subgraph 缺页中断
      I-->M[从外存中找到缺页]
      M-->N{内存满否}
      N -- 是 -->O[选择一页换出]
      O-->P{该页是否被修改}
      P -- 是 -->Q[将该页写回外存]
      Q-->R[OS命令CPU从外存读缺页]
      N -- 否 -->R
      P -- 否 -->R
      R-->S[启动I/O硬件]
      S-->T[将一页从外存换入内存]
      T-->U[修改页面]
      U-->J
  end

页面置换算法

最佳置换算法

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

先进先出算法（FIFO）

每次选择淘汰的页面是最早进入内存的页面
belady异常：当为进程分配的物理块数增大时，缺页次数不减反增的异常现象

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

每次淘汰的页面是最近最久未使用的页面
需要专门的硬件支持，算法开销大。

时钟置换算法（CLOCK）

进行两轮扫描，最开始的内存块的作业的访问位为1，扫描一遍会让访问位减一，如果扫描访问位为0，则被置换。
进行四轮扫描，查找最近未使用以及最近未修改的页面
- 第一优先级：最近没访问，且没修改的页面
- 第二优先级：最近没访问，但修改过的页面
- 第三优先级：最近访问过，但没修改的页面
- 第四优先级：最近访问过，且修改过的页面

页面分配策略

驻留集：指请求分页存储管理中给进程分配的物理块的集合
工作集：指在某段时间间隔里，进程实际访问页面的集合。
固定分配：操作系统为每个进程分配一组固定数目的物理块，驻留集大小不变
可变分配：先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况做适当的增加或减少，驻留集大小可变。
局部置换：发生缺页时只能选进程自己的物理块进行置换。
全局置换：可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程。

固定分配局部置换
可变分配全局置换
可变分配局部置换
何时调入页面：
预调页策略：主要用于进程的首次调入
请求调页策略：进程在运行期间发现缺页时才将所缺页面内存
何处调入页面
系统拥有足够的对换区空间
系统缺少足够的对换取空间
UNIX方式
频繁的页面调度行为称为抖动。产生抖动的主要原因时进程频繁访问的页面数目高于可用的物理块数。驻留集大小不能小于工作集大小

XYX Blog

第三章-内存管理