0%

操作系统-内存管理

Posted on Edited on

DaintreeRiver_ZH-CN2284362798_1920x1080.jpg

进制转换

$$
1 B = 8 Bit \
1 KB = 1024 B \
1 MB = 1024 KB \
1 GB = 1024 GB
$$

存储

  • CPU 寄存器
    • CPU 中包含算数逻辑单元（ALU）、内存管理单元（MMU）、寄存器、高速缓存和控制逻辑
  • 内存
  • 外存（虚拟内存）：存储在磁盘中
  • 磁盘

内存

  • 抽象：将物理地址抽象成逻辑地址
  • 保护：各个进程拥有独立的地址空间，每个进程拥有的内存不会被其他进程破坏
  • 共享：进程共享内核地址空间，减少内存使用
  • 虚拟：将物理内存抽象成更大的逻辑内存

内存分配

连续内存分配

给进程分配一块不小于指定大小的连续的物理内存区域

方法：

  • 最先匹配策略：搜索到第一个匹配的连续物理区域
  • 最佳匹配策略：搜索到比指定大小大并且大的最少的连续物理区域
  • 最差匹配策略：搜索到最大的连续物理内存区域

缺点：会产生内存碎片

  • 内部碎片：进程内存内部存在没有被利用的空间
  • 外部碎片：不同进程内存之间存在没有被利用的空间

非连续内存分配

  • 分页
  • 分段
  • 段页式

虚拟内存

虚拟内存简介

虚拟内存是为了让物理内存扩充成更大的逻辑内存，从而让程序获得更多的可用内存

操作系统将内存抽象成地址空间，16位操作系统的地址空间大小是$2^{16}B (0 \sim 64K)$；32位操作系统的地址空间大小是$2^{32}B(0 \sim 4G)​$

地址空间被划分成多个块，每一块称为一页，一页的大小通常为$4K$ ，16位操作系统共有$16$个页；32位操作系统共有$2^{20}​$个页。这些页通过内存管理单元被映射到物理内存，但不需要映射到连续的物理内存，也不需要所有的页都在物理内存中

每个程序都拥有自己的地址空间，程序在运行时不需要将全部的页调入内存。当程序引用到不在物理内存中的页时，会发生缺页中断，将缺失的部分载入物理内存并重新执行失败的指令

pic

上图是具有$32K​$ 物理内存的16位操作系统的虚拟地址空间和物理内存的关系。虚拟地址空间每一块称为一页，物理内存的每一块称为一个页框，页和页框的大小都为$4K​$

地址空间划分

通常32位 Linux 操作系统将 $0 \sim 3G-1​$ 划分为用户空间，将 $3G \sim 4G-1​$ 划分为内核空间；操作系统程序和驱动程序运行在内核空间，应用程序运行在用户空间

每个进程的虚拟地址空间是$4G$，进程在用户态只能访问$0 \sim 3G-1$，只有通过系统调用进入内核态才能访问$3G \sim 4G-1​$

地址映射模型

分页

内存管理单元

内存管理单元（MMU）是 CPU 硬件的功能，管理虚拟地址空间和物理内存的转换。内存管理单元负责虚拟地址和物理地址的映射，并提供硬件机制的内存访问权限检查。内存管理单元使得每一个进程都拥有自己的地址空间，并通过内存访问权限检查保证每一个进程所用的内存不被其他进程破坏

页表

页表存储着虚拟地址空间（逻辑地址）和物理地址的映射

  • 逻辑地址

    虚拟地址空间由两部分构成：页面号和偏移量
    $$
    页面号 = 虚拟地址 / 4K \
    偏移量 = 虚拟地址 % 4K
    $$
    32位操作系统的地址空间为$4G$，页的大小为$4K​$，需要20位存储页面号，需要12位存储偏移量。32位操作系统的逻辑地址高20位存储页面号，低12位存储偏移量

  • 物理地址

    物理地址也由两部分构成：物理页框号和偏移量
    $$
    页框号 = 物理地址 / 4K \
    偏移量 = 物理地址 % 4K
    $$
    $2G$内存的操作系统，页的大小为$4K$，共有$2^{19}$个页框，$2G$ 内存的操作系统，至少需要19位存储页框号，剩下的12位存储偏移量

页表实际上是页面号和页框号的映射，因为偏移量相等。页表由页框号和标记位构成，标记位用来表示页是否在内存中，1 表示在内存中。如果不在内存中会发生缺页中断，内核缺页异常处理程序将缺失的页载入内存中；如果内存空间不足，将调用页面置换算法将需要的页置换进内存，并重新执行失败的命令

pic

应用进程使用的都是逻辑地址，每个进程都会维护一个单独的页表。当进程未执行时，页表起始地址和页表长度的信息在进程控制块（PCB）中存储，进程执行时会将页表起始地址和页表长度存储在 CPU 的页表寄存器中

映射流程：

  • 计算虚拟地址的页面号和偏移量
    $$
    页面号 = 虚拟地址 / 4K \
    页内偏移量 = 虚拟地址 % 4K
    $$

  • 页表寄存器中存储页表起始地址和页表长度，将页面号和页表长度对比，确认在页表范围内

  • 根据页表起始地址和偏移量找到对应的页框号

  • 将页框号与偏移量拼接即为物理地址，即
    $$
    页框号页表长度+页内偏移量
    $$
    $页框号    页表长度$ 可以理解为页框号向左移动”页表长度“个位

内存管理笔记(分页，分段，逻辑地址，物理地址与地址转换方式)

页表的存储方式

每个进程都有独立的页表，由于页表比较大所以它存储在内存中，并且页表的起始地址和页表长度存储在进程控制块中。当进程执行时，将页表的起始地址和页表长度存储在 CPU 的页表寄存器中

由于页表存储在内存中，所以访问数据需要访问两次内存：获取页表项算一次，访问数据算一次。为了减少内存访问次数加入了 TBL（快表，在 CPU 中存储），TBL中存储了页表的一小部分条目

pic

多级页表

一个32位操作系统，页的大小为$4K​$，那么共有$2^{32}B / 4K = 2^{20}​$ 个页，需要20位作为页面号，则$32-20=12​$位作为偏移量。假设页表项大小是$4B​$，则存储页表需要$4B*2^{20}=4MB​$

使用多级页表可以减少表所占的空间，比如32位操作系统使用两级页表，则可以将20位页面号再次划分成：10位页面号+10位偏移量

pic

页表的优缺点

  • 分页不会产生外部碎片，但可能产生内部碎片

分段

由于分页的机制，使得应用进程以页为单位进程内存分配，并且页不必存储在连续的内存空间。从编程者的角度考虑，一段程序的内存应该是连续的，分页造成了用户视角和实际视角的分离。分段机制将地址空间划分成段，段的大小不固定并且可以动态增长

逻辑地址由两部分构成：段号和偏移量

段表由两部分构成：界限和基址

映射流程：

pic

分页 & 分段

  • 对程序员的透明性：分页透明，但是分段需要程序员显式划分每个段

  • 地址空间的维度：分页是一维地址空间，分段是二维的

    • 分页：虽然逻辑地址包括页号和偏移量，但是分页对程序员不透明，由系统完成，只需给定逻辑地址就可以了，所以是一维地址

    • 分段：分段对程序员不透明，好处是程序模块化，需要程序员指定段号和偏移量，所以是二维地址

    • 段页式：先分段再分页，所以是二维地址

  • 大小是否可以改变：页的大小不可变，段的大小可以动态改变

  • 出现的原因：分页主要用于实现虚拟内存，从而获得更大的地址空间；分段主要是为了使程序和数据可以被划分为逻辑上独立的地址空间并且有助于共享和保护

段页式

地址空间划分成大小不等的段，每个段又划分成大小相等的页

映射过程：逻辑地址 -> 线性地址 -> 物理地址

  • 逻辑地址：16位选择符+16位偏移量
  • 选择符：选择符中包含13位索引，1位TI和2位保护位
    • 段描述符一般有$8B$，需要64位，记录了段的位置和大小的信息；可以通过索引找到描述符表中的段描述符

pic

页面置换算法

为了便于内存管理，操作系统将内存抽象成地址空间，每个程序都有自己的地址空间，这些地址空间又被分成多个块，每一块称为一页。程序运行时不需要将所有的页都载入内存中，当程序引用一个不在内存中的页时，会发生缺页中断，由内核执行缺页异常处理程序，将缺失的页载入内存。如果内存空间不足，使用页面置换算法将内存中的页置换出去，为需要的页腾出空间。页面置换算法的目的是为了使缺页率最少

最佳（OPT）

将未来最久不会再次被访问的页置换出去，能够保证最低的缺页率，是一种理论上的算法，无法实现

例：一个系统为某进程分配 3 个物理块

1
7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1

进程开始运行时，将7、0、1载入内存；当进程需要访问页面 2 时，将 7 置换出去；进程访问页面 0 时，不需要置换；访问页面 3 时，将页面 1 置换出去…

最近最久未使用（LRU）

将过去最近最久没有被访问的页面置换出去

实现方式：

  • 使用双向链表实现，链表中存储着曾经被访问的所有页的页号。如果当前页的页号在链表中，将其移动到链表的头部；如果当前页的页号不在链表中，将其插入到链表的头部；在进行置换时，从尾节点向上遍历，直到遍历到一个在内存中的页面号为止，将所对应的页从内存中置换出去
  • 使用双向链表实现，链表中存储着在内存中的页号的最近最久使用情况。如果当前页的页号在链表中，将其移动到链表的头部；如果当前页的页号不在链表中，将其插入到链表的头部，将尾节点删除，并将尾节点对应的页从内存中置换出去
  • 使用HashMap和循环链表实现，降低遍历链表的时间复杂度

每次都要移动链表，造成性能开销

最近未使用（NRU）

操作系统为每个页面设置两个标记位：R 和 W 。当页面被访问时 R 位置 1，当页面被修改时 W 位置 1。

R 和 W 可以存储在页表中。当启动一个进程时，将所有的页标记为不在内存中。当进程引用不在内存中的页时发生缺页中断，此时操作系统将页表项的 R 位置 1，设置为 read only 模式；当进程需要修改页面时再次引起缺页中断，此时操作系统将 W 位置 1，设置为read/write模式

  • R 位会被定期清零，这样能够区别最近被使用的页面和未被使用的页面
  • W 位置 1 后不清零，操作系统需要通过 W 位判断页是否需要写入磁盘中

当发生缺页中断时，操作系统根据 R 和 W 位将页分为 4 类：

  • 00：未被访问，未被修改
  • 01：未被访问，已被修改（脏页）
  • 10：已被访问，未被修改（干净页）
  • 11：已被访问，未被修改

NRU 随机地从类编号最小的非空类中挑选一个页并将其淘汰

先进先出（FIFO）

将最先进入内存的页面置换出去

可以使用队列实现，经常被使用的页也会被置换出去，导致缺页率升高

第二次机会算法

FIFO 可能将经常使用的页置换出去，造成缺页率增加。第二次机会算法是对 FIFO 算法的改进，在发生缺页中断并需要进行页面置换的时候，查看最老页面的 R 位。如果 R 位是 0，可以将其置换出去；如果 R 位是 1，将其 R 位置 0 并将其 push 进队列，将其认为是刚装入的页面，然后再 pop 出队列头继续搜索能被置换的页面

时钟

第二次机会算法需要进行节点的移动，降低了效率。时钟算法使用循环链表将页面连接起来，使用一个指针指向最老的页面

第二次机会算法是对 FIFO 算法的改进，防止置换出经常使用的页面；时钟算法是对第二次机会算法的改进，防止频繁移动节点