os_内存

第八章 内存管理

内存管理背景

基本硬件

• 程序必须装入内存才能被执行

• CPU可以直接访问的存储器只有主存高速缓存和寄存器

• 寄存器通常可在 1 个（或少于 1 个） CPU 时钟周期内完成访问，完成主存访问可能需要多个 CPU 时钟周期

• CPU暂停（Stall）：在读取内存数据时，CPU空闲

• Cache位于主存和CPU寄存器之间，协调速度差异

• 内存保护需要保证正确的操作

内存管理的目的和功能

• 目的

  • 提高内存利用率
  • 提高指令执行速度
  • 保证指令安全运行

• 功能

  • 内存分配
  • 内存回收
  • 地址转换
  • 存储保护
  • 内存共享

逻辑地址和物理地址

• 逻辑地址空间的概念和物理地址空间相关联， 是正确内存管理的中心

• 逻辑地址 Logical address

  • 由CPU产生
  • 在进程内的相对地址
  • 虚拟地址/程序地址

• 物理地址 Physical address

  • 内存地址
  • 所有内存统一编址
  • 绝对地址/实地址

独立运行空间

• 基址寄存器 Base

  • 进程最小的合法物理内存地址

• 界限寄存器 Limit

  • 进程地址长度
• CPU在执行指令时，需要进行地址合法性验证

指令和数据绑定到内存

• 地址绑定（重定位）

  • 在程序装入内存时，把程序中的相对地址转换为内存中的绝对地址的过程

• 指令和数据绑定到内存地址可能的三个阶段

  • 编译时期 Compile time

    • 如果内存位置已知，可生成绝对代码
    • 如果开始位置改变，需要重新编译代码

  • 加载时期 Load time

    • 如果存储位置在编译时不知道，则必须生成可重定位的代码

  • 执行时期 Execution time

    • 如果进程执行时可在内存移动，则地址绑定可延迟到运行时
    • 需要硬件对地址映射的支持（例如基址和限长寄存器）

动态绑定（动态重定位）

• 动态地址绑定（动态重定位）

  • 在指令运行时，把程序中相对地址转换为内存中的绝对地址的过程
• 程序 a.exe：MOV AX, [0234H] 相对地址
• 基址 Base：1000H
• 内存：MOV AX, [1234H] 绝对地址

内存管理单元(MMU)

• Memory Management Unit
• 是虚拟地址映射到物理地址的硬件
• 是CPU用来管理内存的控制线路
• 在 MMU 策略中，基址寄存器中的值在其送入内存的时候被加入到由一个用户进程所产生的每个地址中
• 用户程序所对应到的是逻辑地址，物理地址对它从来都不可见

动态加载 Dynamic loading

• 例程在调用之前不加载
• 不需要操作系统的特别支持，通过程序设计实现
• 例如 Windows的动态链接库

• 优点

  • 提高内存空间利用率
  • 没有被使用的例程不被载入
  • 当需大量代码来处理不经常使用的功能时非常有用

动态链接 Dynamic Linking

• 链接

  • 将各种代码和数据片段收集并组合成为一个单一文件的过程

• 动态链接

  • 组成程序的目标文件等到程序要运行时才进行链接

    • 和库文件的链接被推迟到执行时期
    • 需要动态装载技术支持
    • 需要操作系统支持

连续内存分配

• 为一个用户程序分配一个连续的内存空间

  • 早期的分配内存模式，运用于内存较少的系统

• 分类

  • 单一连续分配
  • 固定分区分配
  • 可变分区分配

• 主存被分为

  • 操作系统

    • 通常驻留低端，因为中断向量保存在低端

  • 用户进程

    • 保存在内存高端

单一连续分配

• 分配方式

  • 单道程序环境下，仅装有一道用户程序，即整个内存的用户空间由该程序独占

• 特点

  • 内存管理简单
  • 内存利用率低

• 用于单用户，单任务操作系统

  • 例如CP/M，MS-DOS，RT11

• 未采取存储器保护措施

  • 节省硬件
  • 方案可行

固定分区分配

• 最早的、最简单的一种可运行多道程序的存储管理方式

• 预先把可分配的主存空间分割成若干个连续区域

  • 称为一个分区

• 每个分区的大小可以相同也可以不同

  • 但分区的大小固定不变，且每个分区只能装一个程序

• 内存分配

  • 如果有一个空闲分区，就分配给进程

划分分区的方法

• 分区大小一样

  • 缺乏灵活性
  • 有些场合适用，如利用一台计算机同时控制多个相同对象

• 分区大小不等

  • 多个小分区
  • 适量中分区
  • 少量大分区

内存分配

• 固定分区使用表

可变分区分配

• 分区/孔 Hole

  • 可用的内存块，不同大小的分区分布在整个内存中
• 当一个进程到来的时候，它将从一个足够容纳它分区中分配内存

• 操作系统包含以下信息

  • 已分配的分区—已分配分区表
  • 空的分区—空闲分区表

存储分配算法

• 首次适应 First-fit

  • 分配最先找到的合适的分区

• 最佳适应 Best-fit

  • 搜索整个列表，找到适合条件的最小的分区进行分配

• 最差适应 Worst-fit

  • 搜索整个列表，寻找最大的分区进行分配

在速度和存储空间的利用上，首次适应和最佳适应要好于最差适应

内存回收

• 四种情况

  1. 回收内存块前后无空闲块
  2. 前有后无
  3. 前无后有
  4. 前后均有

碎片

• 外碎片

  • 整个可用内存空间可以用来满足一个请求，但它不是连续的

• 内碎片

  • 分配的内存可能笔申请的内存大一点，这两者之间的差别是在分区内部，但又不被使用

• 可通过紧缩碎片来减少外碎片

  • 把一些小的空闲内存结合成大的块
  • 只有重定位是动态时，才有可能进行紧缩，紧缩在执行时期进行
• 紧缩例子

分页内存管理

• 离散内存管理方案

  • 分页内存管理方案 — 现代操作系统常用方案
  • 分段内存管理方案
  • 段页式内存管理方案

分页 Paging

• 进程物理地址空间可能不连续

  • 如果有可用的物理内存，将分给进程

• 把物理内存分成大小固定的快 — 帧 Frame

  • 大小为2的幂
  • 早期 512字节到8192自建
  • 现在 4K-64K
  • 系统保留所有空闲帧的记录

• 把逻辑内存也分成同样大小的块 — 页 Page

• 运行一个有N页大小程序，需要找到N个空帧来装入程序

• 建立一个页表，把逻辑地址转换为物理地址

• 存在内碎片

地址转换机制

• 页号 p

  • 包含每个页在物理内存中的基址，用来作为页表的索引

• 页偏移 d

  • 同基址相结合，用来确定送入内存设备的物理内存地址
• 给定逻辑地址空间2和页大小2

分页的硬件支持

1. 根据逻辑地址中的页号p，到页表中找到第p项，第p项内存储的f就是页框号
2. 页框号f和页内偏移d构成物理地址

页表的实现

• 页表被保存在主存中

• 页表基址寄存器 PTBR 指向页表

• 页表限长寄存器 PRLR 表明页表的长度

• 这个机制，每一次的数据/指令存取需要两次内存存取，一次是存取页表，一次是存取数据/指令

  • 为了解决这个问题，采用小但专用且快速的硬件缓冲，这种缓冲称为转换表缓冲器TLB或联想寄存器

• TLB

  • 并行查找

• 地址转换 (A ´ , A ´´)

  • 如果 A’ 在联想寄存器中，把帧号取出来
  • 否则从内存中的页表中取出帧号
• 使用TLB的分页硬件

• 有效访问时间

  • 联想寄存器的查找需要时间单位 a 微秒
  • 假设内存一次存取需要 b 微秒
  • 命中率 在联想寄存器中找到页号的百分比，比率与联想寄存器的大小有关
  • 命中率 = λ
  • 有效访问时间 EAT = λ (a + b ) + (1-λ ) (a+2b)

内存保护

• 简单方法

  • 把页号和页表限长寄存器PRLR比较
• 内存的保护由与每个帧相连的保护位来实现

• 有效/无效位附再页表的每个表项中

  • 有效表示相关的页在进程的逻辑空间，且是一个合法的页
  • 无效表示页不在进程的逻辑地址空间中

页共享

• 共享代码

  • 如果代码是可重入代码（只读），可以在进程间共享

    • 例如文本编辑器，编译器，数据库
  • 共享代码必须出现在所有进程的逻辑地址空间的相同位置

• 私有代码和数据

  • 每个进程保留一个代码和数据副本
  • 存有私有数据和代码的页能够出现在逻辑地址空间的任意位置

页表结构

• 例子

  • 32位逻辑地址，页大小4KB
  • 一个页表最多包含一百万个表项(2/2)
  • 每个页表项4个字节，需4MB空间放页表，1024个连续页面
  • 这么多连续页面不一定能实现

• 解决方法

  • 层次页表
  • 哈希页表
  • 反向页表

两级页表机制

两级分页例子

• 页大小为4K，32位系统，一个逻辑地址被分为

  • 一个20位的页号
  • 一个12位的页偏移

• 由于页表所在也也被分页，页号被进一步分为

  • 一个10位的页号
  • 一个10位的页偏移
• 因此逻辑地址表示为

• P1是外页表的索引，P2是外部页表的页偏移

地址转换机制

• 一个两级32位分页结构的地址转换机制

• 三级分页机制

• 例如Inter x86-64

  • 仅用48位
  • 页大小：4KB，2MB，1GB
  • 四级页表

哈希页表

• 通常地址空间 > 32位

• 虚拟页表被扩散到一个页表中

  • 这种页表的每一个条目都包含了一个链表元素

• 虚拟页号与链表中的每个元素比较，找到匹配项

  • 如果匹配，就取出对应的物理帧

反向页表

• 对于每个真正的内存页或帧有一个条目
• 每个条目保存在真正内存位置的页的虚拟地址，以及包括拥有这个页的进程的信息

• 反向页表

  • 减少了需要储存每个页表的内存，但是当访问一个页时，增加了寻找页表需要的时间
  • 使用哈希表来将查找限制在一个或少数几个页表条目
  • 实现共享内存很难

分段内存管理

• 分段 Segmentation

• 支持用户观点的内存管理机制

• 一个程序是一些段的集合，一个段是一个逻辑单位

• 分段的逻辑视图
  

分段机制

• 一个逻辑地址是两个向量的集合

• 段表 — 映射二位用户地址，每个表项包括

  • 基址

    • 包含内存中段物理地址的起始地址

  • 限长

    • 指定段的长度
• 段表基址寄存器 STBR 指向段表在内存中的地址

• 段表限长寄存器 STLR 表明被一个程序所使用的段的数目

  • 如果 s<STLR，段号s是合法的

• 由于段的长度各不相同，内存分配是一个动态存储—分配的过程

• 内存分配

  • 首先/最佳适应法
  • 外碎片问题

• 重定位

  • 动态
  • 由段表来执行

• 共享

  • 共享的段
  • 同样的段号

• 段共享的例子

  • 两个进程共享一个编辑器

• 保护，每个段表的表项有

  • 有效位 = 0 ：非分段
  • 读写执行的权利
• 保护位同段相联系，在段的级别进行代码共享

段页式原理

• 分段和分页原理的结合

• 先将用户程序分成若干个段，再把每个段分成若干个页，并为每个段赋予一个段号

• 逻辑地址

  • 段号，页号，页内偏移
• 存在内碎片，无外碎片

内存扩充技术

内存空间不足的解决办法

1. 紧缩 Compaction 可变分区
2. 覆盖技术 Overlaying
3. 交换技术 Swapping
4. 虚拟内存 Virtual Memory

覆盖

• 解决的问题

  • 程序大小查过物理内存总和

• 程序执行时

  • 只在内存中保留那些在任何时间都需要的指令和数据
  • 程序的不同部分在内存中相互替换
• 由程序员声明覆盖结构，不需要操作系统的特别支持
• 覆盖结构的程序设计很复杂
• 应用于早期的操作系统

交换

• 在多道程序环境下

  • 在内存中的某些进程由于某事件尚未发生而被阻塞运行，但它却占用了大量的内存空间
  • 有时可能出现在内存中所有进程都被阻塞而迫使CPU停止下来等待的情况
  • 又有许多作业在外存上等待，因无内存而不能进入内存运行的情况

• 存在问题

  • 浪费资源
  • 降低系统吞吐量

• 一个进程可以暂时被交换到内存外的一个备份区，随后可以被换回内存继续执行

  • 备份区是一个固定的足够大的可以容纳所有用户内存映像拷贝的快速磁盘，必须提供对这些内存映像的直接访问

• 滚入，滚出 Roll out, Roll in

  • 交换由于基于优先级的算法而不同，低优先级的进程被换出，这样高优先级的进程可以被装入和执行
• 交换时间的主要部分是转移时间，总的转移时间直接同交换的内存数量成正比

• 交换比较耗时

  • 100MB大约4s

• 标准交换技术在现代操作系统中很少使用

  • 常用策略：当空间内存不够时采用交换

简答题

• 进程的那些内存要交换到磁盘

  • 运行时创建或修改的内容：栈和堆

• 在磁盘的什么位置保存被换出的进程

  • 交换区（备份区）

    • 系统指定一块特殊的磁盘区域作为交换空间，包含连续的磁道，操作系统可以使用底层的磁盘读写操作对其进行高效访问

• 交换时机

  • 只要不用就换出
  • 内存空间不够或有不够的危险时患处

• 如何选择被换出的进行

  • 不应该换出处于等待IO状态的进程
• 如何处理进程空间增长

第九章 虚拟内存

虚拟存储技术

• 代码必须全部装入内存才能执行，但是并不是所有代码必须全部装入内存，例如

  • 错误代码
  • 不常用的函数
  • 大的数据结构

局部性原理

• 局部性原理：一个程序只要部分装入内存就可以运行

  • 整个程序不是同一时间都要运行

  • 程序在执行时呈现局部性规律

    • 在一较短的时间内，程序的执行仅局限于某个部分
    • 相应地，程序访问的存储空间也局限于某个区域

• 程序在执行时，除了少部分的转移和过程调用外，大多数情况下仍然顺序执行
• 过程调用将会使程序的执行轨迹由一部分区域转至另一部分区域，过程调用的深度一半小于5，在一段时间内程序都局限在这些过程的范围内
• 程序中存在许多循环结构，多次执行
• 对数据结构的处理局限于很小的范围

• 程序部分装入的优点

  • 进程大小不再受到物理内存大小限制
  • 每个进程需要的内存更小
  • 更多进程可以并发运行
  • I/O更少

• 虚拟存储技术：当进程运行时，先将其一部分装入内存，另一部分暂留在此磁盘。当要执行的指令或访问的数据不在内存时，由操作系统自动完成将它们从磁盘调入内存执行。

• 虚拟地址空间：分配给进程的虚拟内存

• 虚拟地址：在虚拟内存中由指令或数据的位置

• 虚拟内存：即虚存，把内存和磁盘有机结合起来使用，得到的容量很大的“内存”

  • 区分开物理内存和用户逻辑内存
  • 只有部分运行的程序需要在内存中
  • 逻辑地址空间能够比物理空间大
  • 允许多个进程共享同一地址空间
  • 允许更有效的进程创建

• 虚拟内存的大小由两个因素决定

  1. 操作系统字长
  2. 内存外存容量和

• 使用虚拟内存的共享库

写时复制 copy-on-write

• 写时复制允许父进程和子进程在初始化时共享页面

  • 如果其中一个进程修改了一个共享页面，会产生副本
  • 更加高效
  • 应用于XP，Linux等系统

• vfork：fork()变形，不使用写时复制

虚拟内存的实现

• 虚拟页式

  • 虚拟存储技术+页式存储管理

  • 两种方式

    1. 请求分页 demand paging
    2. 预调页 prepaging

• 虚拟段式

  • 虚拟存储技术+段式存储管理

✨请求分页

• 虚拟页式存储管理

  • 进程开始运行前不是装入全部页面，而是装入一个或零个页面
  • 运行后根据运行需要，动态装入其他页面
  • 当内存空间已满，而又需要装入其他新的页面时，则根据某种算法置换内存中的某个页面，以便装入新的页面

请求分页（按需调页）

• 只有在一个页需要的时候才把它换入内存

  • 需要很少的IO
  • 需要很少的内存
  • 快速响应
  • 多用户
• 类似交换技术，但粒度不同

• 懒惰交换：只有在需要页时，才将它调入内存

  • 交换程序(swapper)对整个进程进行操作
  • 调页程序(pager)只是对进程的单个页进行操作

有效—无效位(valid-invalid)

• 每一个页表的表项有一个有效—无效位相关联

  • 1表示在内存，0表示不在内存
• 所有的表项中，这个位初始化为0
• 一个页表映像的例子

• 有页不在内存的页表

  • 此时物理内存中只有A, C, F，其余各项均未载入内存，仍在外存中

缺页中断

• 对一个页的访问，首次访问该页需要陷入OS => 缺页中断
• Page-fault trap

• 步骤

  1. 访问指令或数据

  2. 检查该进程的内部表，以确定该引用时有效的还是无效的内存访问

     • 无效引用=>终止进程
     • 引诱有效但尚未调入页面=>现在调入
  3. 找到一个空闲帧
  4. 调度一个磁盘操作，将所需的页面读到刚分配的空帧中
  5. 当磁盘读取完成时，修改进程的内部表和页表，以指示该页现在处于内存中
  6. 重新启动被陷阱中断的指令。该进程现在能访问所需的页面，就好像它总是在内存中

✨处理缺页错误的步骤❗

• 极端情况：进程执行第一行代码时，内存中没有任何代码和数据

  • 进程创建时，没有为进程分配内存，仅建立PCB
  • 导致缺页中断
  • 纯请求分页

• 一条指令可能导致多次缺页(涉及多个页面)

  • 幸运的是程序具有局部性

• 请求分页需要硬件支持

  • 带有效无效位的页表
  • 交换空间
  • 指令重启

请求分页的性能

• 缺页率p

  • 如果p=0，没有缺页
  • 如果p=1，每次访问都缺页

• 有效访问时间EAT

  • EAT = (1-P) x 内存访问时间 +p x 页错误时间

• 页错误时间 = 处理缺页中断 + [页交换的时间] + 读入页的时间 + 重启进程的开销

• 例子

  • 存取内存的时间 = 200ns

  • 平均缺页处理时间 = 8ms

= 200 + p x 7999800

• 如果每1000次访问中有一个页错误，则

  • EAT = 8200 ns

    导致计算机速度减慢40倍

请求分页性能优化

• 页面转换时采用交换空间，而不是文件系统

  • 交换区的块大，比文件系统服务速度更快

• 在进程装载时，把整个进程拷贝到交换区

  • 基于交换区调页
  • 早期的BSD Unix

• 利用文件系统进行交换

  • Solaris和当前的BSD
  • 部分内容仍需交换区，如堆栈

页面置换

• 如果没有空闲帧=>页置换

• 页置换

  • 换出内存中没有使用的一些页

    同一个页可能会被装入内存多次

• 基本方法

  1. 查找所需页在磁盘上的位置

  2. 查找空闲页帧

     • 如果有空闲帧就使用
     • 没有空闲帧，使用页置换算法，牺牲一个帧
     • 将牺牲的帧的内容写到磁盘上，更新页表和帧表
  3. 将所需页读入新的空闲帧，更新页表和帧表
  4. 重启用户进程
• 页置换过程图示

• 如果发生页置换，则缺页处理时间加倍

• 使用修改位(modify bit)或者脏位(dirty bit)来防止页面转移过多

  • 只有被修改的页面才写入磁盘

• 页置换完善了逻辑内存和物理内存的划分

  • 在一个较小的物理内存基础之上可以提供一个大的虚拟内存

页置换算法

• 找出一个导致最小缺页率的算法

• 通过运行一个内存访问的特殊序列(访问序列)，计算这个序列的缺页次数

• 访问序列形式如

  • 1，2，3，4，1，2，5，1，2，3，4，5

• 最优置换算法 OPT

• 先进先出置换算法 FIFO

• 最近最少使用置换算法 LRU

• 类似LRU算法

  • 二次机会法

先进先出FIFO

• 置换在内存中驻留时间最长的页面
• 容易理解和实现，但性能不总是很好
• 实现：使用FIFO队列管理内存中的所有页

• 在这个过程中产生了15次缺页

• FIFO算法可能会产生Belady异常

  • 引用串1,2,3,4,1,2,5,1,2,3,4,5

    • 3个页框，9次缺页
    • 4个页框，10次缺页
  • 更多的页框=>更多的缺页

    理想情况应该是页框数更多的时候，缺页数会减少

最优置换算法OPT

• 被置换的页是将来不再需要的或最远的将来才会被使用的页

• 作用

  • 无法实现，仅作为一种标准来衡量其他算法的性能
  • 属于理论上页置换的最优解

• 说明在3个页框的情况下，这个访问序列最少会发生9次缺页

最近最少使用算法LRU

• 置换最长时间没有使用的页
• 性能接近OPT

• 实现

  • 计数器(时间戳)或栈
  • 开销大，需要硬件支持

LRU近似算法

• 在没有硬件支持的系统中，可使用LRU近似算法

• 访问位

  • 每个页都与一个位相关联，初始值为0
  • 当页访问时设为1

• 附加引用位算法

• 二次机会算法

• 增强型二次机会算法

NFU不经常使用算法

• Not Frequently Used

  • 需要一个初值位0的软件计数器和每页相联
  • 每次时钟中断时，操作系统扫描内存中的所有页面，将每页的R位加到其计数器上
  • 缺页时淘汰计数器值最小的页

• 实指

  • 跟踪每页被访问的频繁程度

老化算法

• 根据NFU算法修改，很好地模拟了LRU

  • 先将计数器右移一位
  • 把R位加到计数器的最左端

二次机会算法

• 需要访问位
• 如果访问位为0，直接置换

• 如果将要交换的页访问为是1，则

  • 把访问位设为0
  • 把页留存在内存中
  • 以同样的规则，替换下一个页
• 实现：时钟置换(顺时针方式)
• 属于FIFO的增强算法

系统颠簸

页框（帧）的分配

• 必须满足

  • 每个进程所需要最少的页数

• 例如IBM370-6处理SS MOVE指令

  • 指令是6个字节，可能跨越2页
  • 2页处理from
  • 2页处理to

• 两个主要分配策略

  • 固定分配
  • 优先级分配

固定分配

• 平均分配

  • 均分法
  • 100个帧，5个进程，每个进程分配20个页

• 按比例分配

  • 根据每个进程的大小来分配

    优先级分配

• 根据优先级而不是进程的大小来使用比例分配策略

• 如果Pi产生一个缺页

  • 选择替换其中的一个帧
  • 从一个较低优先级的进程中选择一个页面来替换

全局置换和局部置换

• 全局置换

  • 进程在所有的帧中选择一个替换页面
  • 一个进程可以从另一个进程中获得页框

• 局部置换

  • 每个进程只从属于它自己的帧中选择

颠簸

• Thrashing

• 如果一个进程没有足够的页，那么缺页率将很高，导致

  • CPU利用率低
  • 操作系统认为需要增加多道程序的道数
  • 系统中将加入一个新的进程
• 颠簸 ≡ 一个进程的页面经常换入换出

局部模型

• Locality model
• 进程从一个局部移到另一个局部
• 局部可能会重叠

• 颠簸发生的原因

  • 分配的帧数<局部大小之和

工作集模型

• working-set模型

• Δ ≡ 工作集窗口 ≡ 固定数目的页的引用

  • 例如10000个引用

• WSSi(进程Pi的工作集) = 最近Δ中所有页的引用

  • 会随时间变化

• 工作集大小

  • 如果Δ太小，那么就不能包含整个局部
  • 如果Δ太大，那么就可能包含多个局部
  • 如果Δ=+∞，那么工作集合就是进程执行所接触到的所有页的集合
• D = Σ WSSi = 总的帧需求量
• 如果D > m => 颠簸

• 策略

  • 当D>m时，暂停一个进程

• 难点

  • 跟踪工作集

缺页率策略

• 设置可接收的缺页率范围

  • 如果太低，就回收一些进程的帧
  • 如果太高，就分给进程一些帧

内核内存分配

• 通常从空闲内存池中获取

  • 内核需要为不同大小的数据结构分配内存
  • 一些内存需要连续的物理页

• 内核内存特点

  • 内存块尺寸小
  • 占用内存块时间短
  • 需要快速完成分配和回收
  • 不参与交换
  • 频繁使用相同尺寸的内存块，存放同一结构的数据
  • 要求动态分配和回收

伙伴(Buddy)系统

• 经典的内存分配方案

• 主要用于Linux早期版本中内核底层内存管理

• 从物理上连续的大小固定的段上分配内存

• 主要思想

  • 内存按2的幂的大小进行划分，即4KB,8KB等，组成若干空闲块链表

  • 查找链表找到满足进程需求的最佳匹配块

    • 满足要求是以2的幂为单位的
    • 如果请求的内存不是2的幂，就调整到下一个更大的2的幂
    • 当分配需求小于现在可用内存时，当前段就分为更小的2的幂段，继续上述操作

• 算法

  • 一开始把可用空间看作的是一整块，大小为2的内存
  • 假设进程申请的空间为s
  • 如果2<s<=2，就直接把整块内存分配给进程
  • 否则，就把这个内存划分为2块，每块大小2
  • 直到划分到大于等于s的最小块

Slab分配

• Slab由一个或多个物理上连续的页组成

• Cache有一个或多个slab

  • 每个cache含有内核数据结构的对象实例
• 每个内核数据结构都有一个cache

• 创建cache时，会包含若干个标记为空闲的对象
• 内核直接从cache上获取空闲内存，并标识为对象使用

• 当一个slab充满了已使用的对象时，下一个对象从空的slab开始分配

  • 如果没有空的slab，就从物理连续页上分配新的slab

• 优点

  • 没有因碎片而引起的内存浪费
  • 内存请求可以快速满足

• 使用系统

  • Solaris2.4内核
  • Linux2.2以后的内核

虚拟内存其他考虑

预调页

• 在进程启动的初期，减少大量的缺页中断
• 引用前，调入进程的所有或一些需要的页面
• 如果预调入的页面没有被使用，内存就会被浪费

页大小

• 需要小的页

  • 碎片
  • 程序局部

• 需要大的页

  • 表大小
  • I/O开销
  • 缺页次数
• 没有最佳答案，总体来说趋向大的页

TLB范围

• TLB

  • 转换表缓冲器或联想寄存器
  • 就是用来实现快表的硬件

• 通过TLC所访问的内存量

  • 范围 = TLB大小 x 页大小

• 理想情况下，一个进程的工作集应该存放在TLB中

  • 否则会有大量的缺页中断

• 增加页的大小

  • 对于不需要大页应用程序而言，会导致碎片的增加

• 提供多种页的大小

  • 允许大页的应用程序有机会使用大页，不增加碎片的大小

反向页表

• 降低了保存的物理内存
• 不在包括进程逻辑地址空间的完整信息
• 为了提供这种信息，进程必须保留一个外部页表
• 外部页表可根据需要换进或换出内存

I/O互锁

• 允许某些页在内存中被锁住
• I/O时，正在进行I/O的页面不允许被置换算法置换出内存

程序结构

• 程序结构可能影响系统性能

  • 将1024*1024的矩阵的每一行保存在一页

    for i in range(1024):
    for j in range(1024):
       A[i][j] = 0
    # 会产生1024*1024次缺页
    for j in range(1024):
    for i in range(1024):
       A[i][j] = 0
    # 会产生1024次缺页

• 其他因素（编译器、载入器、程序设计语言）都对调页有影响

✨64位和32位的操作系统的区别？

• 在标识内存地址空间上

  • 32位操作系统用32个bit来标识内存地址

    • 理论最大内存为2 = 4*2=4GB
    • 0x00000000~0xFFFFFFFF

  • 64位操作系统用64个bit来标识内存地址

    • 理论最大内存为2=16*2= 17179869184G(172亿G)
    • 0x0000000000000000~0xFFFFFFFFFFFFFFFF

• 在访问内存空间上

  • 32位系统，1个指针需要4字节的内存
  • 64位系统，1个指针需要8字节的内存

设计方案