内存的基础知识

什么是内存？有何作用？

  • 内存可存放数据。程序执行前需要先放到内存中才能被 CPU 处理——缓和 CPU 与硬盘之间的速度矛盾
    • 内存中有一个一个的 “小房间”，每个小房间就是一个 “存储单元”
    • 为了区分各个程序的数据，需要给内存的存储单元编地址，每个 地址对应一个存储单元
    • 如果计算机 “按字节编址”， 则每个存储单元大小为 1 字节，即 1B，即 8 个二进制位
    • 如果字长为 64 位的计算机 “按字编址”，则每个存储单元大小为 1 个字；每个字的大小为 64 个二进制位

      数量单位：2^10=1K；2^20=1M；2^30=1G

进程运行的基本原理

指令的工作原理

  • 我们写的代码要翻译成 CPU 能识别的指令。这些指令会告诉 CPU 应该去内存的哪个地址读 / 写数据， 这个数据应该做什么样的处理
  • 指令的工作基于 “地址”。 每个地址对应一个数据的存储单元

具体内容可见计算机组成原理 - 指令系统：传送门

逻辑地址与物理地址

  • 程序经过编译、链接后生成的指令中指明的是逻辑地址（相对地址），即：相对于进程的起始地址而言的地址

    • 编译：由编译程序将用户源代码编译成若干个目标模块（编译就是把高级语言翻译为机器语言）
    • 链接：由链接程序将编译后形成的一组目标模块，以及所需库函数链接在一起，形成一个完整的装入模块
    • 装入：由装入程序将装入模块装入内存，装入后形成物理地址

      如何实现地址转换🌟

      如何将指令中的逻辑地址 (相对地址) 转换为物理地址(绝对地址)？

  • 策略：三种装入方式，

    • 绝对装入
    • 可重定位装入（静态重定位）
    • 动态运行时装入（动态重定位）
      绝对装入
      image.png

  • 装入内存前确定物理地址

    可重定位装入

    image.png

  • 装入内存时确定物理地址

    动态运行时装入

    image.png

  • 装入后仍是逻辑地址，在运行时靠寄存器转换为物理地址后执行

    从写程序到程序运行

    image.png

    小结

    image.png

    内存管理的概念

    操作系统作为系统资源的管理者，需要提供以下服务：

  • 负责内存空间的分配与回收

  • 提供某种技术从逻辑上对内存空间进行扩充
  • 提供地址转换功能，负责程序的逻辑地址与物理地址的转换

  • 提供内存保护功能。保证各进程在各自存储空间内运行，互不干扰

    内存空间的分配与回收

  • 连续分配管理方式

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

  • 非连续分配管理方式

    • 基本分页存储管理
    • 基本分段存储管理
    • 段页式存储管理

      内存空间的扩充

  • 覆盖技术

  • 交换技术

  • 虚拟存储器技术

    地址转换

  • 为了使编程更方便，程序员写程序时应该只需要关注指令、数据的逻辑地址。而逻辑地址到物理地址的转换（这个过程称为地址重定位 - 三种装入方式）应该由操作系统负责，这样就保证了程序员写程序时不需要关注物理内存的实际情况

image.png

存储保护

image.png image.png

小结

image.png

内存空间的分配与回收🌟

连续分配管理方式

  • 连续分配：指为用户进程分配的必须是一个连续的内存空间

  • 连续分配管理方式也就是分区式存储管理

    单一连续分配

    image.png

  • 系统区通常位于内存的低地址部分，用于存放操作系统相关数据

  • 用户区用于存放用户进程相关数据

  • 内存中只能有一道用户程序

    固定分区分配

    image.png

  • 内存的用户区划分为若干个固定大小的分区，

  • 内存中能装入多道程序

用分区说明表记录各个固定分区的分配与回收：
image.png

动态分区分配

image.png image.png image.png
如何进行分区的分配与回收操作？

  • 动态分区分配算法，修改分区表 / 分区链
  • 相邻的空闲分区合并为一个，修改分区表 / 分区链
  • 若回收区的前、后都没有相邻的空闲分区，则修改分区表 / 分区链新增一个表项 / 结点

image.png

  • 交换（对换）技术的设计思想：内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存（进程在内存与磁盘间动态调度）

    中级调度 (内存调度)：就是要决定将哪个处于挂起状态的进程重新调入内存

  • 动态运行时装入：运行时才进行地址转换

    小结🌟

    image.png

    动态分区分配算法🌟

    image.png

    首次适应算法

    image.png

    最佳适应算法

    image.png

    最坏适应算法

    image.png

    邻近适应算法

    image.png

    小结

    image.png

    非连续分配管理方式

  • 连续分配：为用户进程分配的必须是一个连续的内存空间

  • 非连续分配：为用户进程分配的可以是一些分散的内存空间

    分页式存储管理

    image.png

  • 将内存空间分为为一个个大小相等的分区，每个分区叫做：页框 / 内存块 / 物理块，从 0 开始

  • 将进程的逻辑地址空间分为与页框大小相等的一个个部分，每个部分叫做：页 / 页面，从 0 开始
  • 进程的页面与内存的页框有一一对应的关系
  • 各个页面不必连续存放，可以放到不相邻的各个页框中

image.png

  • 页表通常保存在 PCB（进程控制块）中
  • 一个进程对应一张页表
  • 进程的每个页面对应一个页表项
  • 页表记录进程页面和实际存放的内存块之间的映射关系

image.png image.png

  • 物理地址 = 页面在内存中的起始地址 + 页内偏移量

image.png

  • 页号 = 逻辑地址 / 页面长度 （取除法的整数部分）
  • 页内偏移量 = 逻辑地址 % 页面长度（取除法的余数部分）

image.png

  • 如果每个页面大小为 2KB，用二进制数表示逻辑地址，末尾 K 位即为页内偏移量，前面其他部分就是页号

image.png

  • 如果页面大小刚好是 2 的整数幂，则只需把页表中记录的物理块号拼接上页内偏移量就能得到对应的物理地址
  • 如果有 K 位表示 “页内偏移量”，则说明该系统中一个页面的大小是 2K 个内存单元
  • 如果有 M 位表示 “页号”，则说明在该系统中，一个进程最多允许有 2M 个页面
  • 页面大小 ↔ 页内偏移量位数 → 逻辑地址结构

image.png image.png

  • 基本地址变换机构：用于实现逻辑地址到物理地址转换的一组硬件机构

image.png

  • 页式管理中地址是一维的。即，只要给出一个逻辑地址，系统就可以自动地算出页号、页内偏移量两个部分，并不需要显式地告诉系统这个逻辑地址中，页内偏移量占多少位

image.png

  • 快表，又称联想寄存器（TLB， translation lookaside buffer ），是一种访问速度比内存快很多的高速缓存（TLB 不是内存！），用来存放最近访问的页表项的副本，可以加速地址变换的速度。
  • 与此对应，内存中的页表常称为慢表。

image.png

  • 时间局部性：如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行；如果某个数据被访问过，不久之后该数据很可能再次被访问。（因为程序中存在大量的循环）
  • 空间局部性：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问。（因为很多数据在内存中都是连续存放的）

image.png

  • 快表命中，只需一次访存
  • 快表未命中，需要两次访存

image.png

分段式存储管理

image.png

  • 进程的地址空间：按照程序自身的逻辑关系划分为若干个段，每个段都有一个段名（在低级语言中，程序员使用段名来编程），每段从 0 开始编址
  • 内存分配规则：以段为单位进行分配，每个段在内存中占据连续空间，但各段之间可以不相邻

image.png

  • 段号的位数决定了每个进程最多可以分几个段
  • 段内地址位数决定了每个段的最大长度是多少

image.png image.png image.png image.png

段页式存储管理

image.png
image.png

  • 先分段，再对段分页

image.png

  • 段号的位数决定了每个进程最多可以分几个段
  • 页号位数决定了每个段最大有多少页
  • 页内偏移量决定了页面大小、内存块大小是多少

image.png image.png

内存空间的扩充

覆盖技术🌟

image.png

  • 覆盖技术的思想：将程序分为多个段（多个模块）
  • 常用的段常驻内存，不常用的段在需要时调入内存
  • 内存中分为一个 “固定区” 和若干个 “覆盖区”
  • 需要常驻内存的段放在 “固定区” 中，调入后就不再调出（除非运行结束）

  • 不常用的段放在 “覆盖区”，需要用到时调入内存， 用不到时调出内存

    交换技术🌟

    image.png

  • 交换（对换）技术的设计思想：内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存（进程在内存与磁盘间动态调度）

中级调度 (内存调度)：就是要决定将哪个处于挂起状态的进程重新调入内存
image.png

  • 暂时换出外存等待的进程状态为挂起状态 (挂起态，suspend)
  • 挂起态又可以进一步细分为就绪挂起、阻塞挂起两种状态

image.png

  • 对换区：存放被换出内存的进程的数据

  • 文件区：存放文件

    小结

    image.png

    虚拟存储技术🌟

    image.png

  • 离散性：在内存分配时，采用离散分配方式

    请求分页管理方式

    请求分页存储管理与基本分页存储管理的主要区别：

  • 操作系统要提供请求调页功能，将缺失页面从外存调入内存

  • 操作系统要提供页面置换的功能，将暂时用不到的页面换出外存

image.png
image.png

  • 在具有快表机构的请求分页系统中，访问一个逻辑地址时，若发生缺页，则地址变换步骤是：
  • 查快表 (未命中)——查慢表 (发现未调入内存)——调页 (调入的页面对应的表项会直接加入快表)——查快表 (命中)——访问目标内存单元

image.png

页面置换算法🌟

  • 若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存
  • 用页面置换算法决定应该换出哪个页面

  • 页面的换入、换出需要磁盘 I/O，会有较大的开销，因此好的页面置换算法应该追求更少的缺页率

    最佳置换算法 (OPT)

    image.png

  • 最佳置换算法可以保证最低的缺页率，但实际上，只有在进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面访问序列。因此，最佳置换算法是无法实现的。

    先进先出置换算法 (FIFO)

    image.png

  • 要按调入次序看，不要按访问次序看

  • 画个队列，去掉队头
    最近最久未使用置换算法 (LRU)
    image.png
    时钟置换算法 (CLOCK)
    image.png image.png

    页面分配策略

    image.png