**基址寄存器(B)**和 界限寄存器 (L) 限定了进程能访问地址的范围 $[B,B+L]$。

这两个值只能以特权指令加载。即必须是内核模式下加载,往往只有操作系统有此权限。

指令与数据绑定到内存地址的时机

编译时(compile time):生成绝对代码(absolute code)。

加载时(load time):生成可重定位代码(reloadable code)。

执行时(execution time):进程在执行时可以从一个内存段移到另一个内存段。绝大多数通用计算机操作系统采用这种方法。

CPU 生成的地址通常称为逻辑地址(logical address),而内存单元所看到的地址(即加载到内存地址寄存器(memory-address register)中的地址)通常称为物理地址(physical address)

从虚拟地址到物理地址的映射由被称为 内存管理单元(memory-management unit,MMU) 的硬件设备来完成

内部碎片与外部碎片

内部碎片

操作系统可以决定虚存的页面大小。当页面比较大的时候,平均的情况下, 最后一个页面中有一半是空的。 多余的空间就被浪费掉了, 这种浪费称为内部碎片(internal fragmentation) 。假设进程平均大小是 s 个字节, 页面大小是 p 个字节, 每个页表项需要 e 个字节。 那么每个进程需要的页数大约是 s/p, 占用了 se/p 个字节的页表空间。 内部碎片在最后一页浪费的内存是 p/2。 (《现代操作系统》P267)

内部碎片是已经被进程使用的,因此叫 “内部”。

除了内存,磁盘分块也会出现类似的情况,当下一帧填不满当前磁盘块的时候, 则磁盘块剩余的部分就保持空闲状态。 同样称为内部碎片。

外部碎片

在系统运行一段时间后内存被划分为许多块, 一些块包含着段, 一些则成了空闲区, 这种现象称为棋盘形碎片或外部碎片(external fragmentation) 。 (《现代操作系统》P289)

外部碎片是尚未使用,但是因为太小无法被分配的。所以称为 “外部”。

内存管理方案

固定分区(fixed partitions)

将物理内存分为固定的区域。不同的进程拥有不同的基地址。

硬件需求:基址寄存器

地址转换:物理地址 = 虚拟地址 + 基地址

优点:

  • 易于实现
  • 快速环境切换

缺点:

  • 容易产生内部碎片:一个进程内部使用的内存,如果是空闲的,无法被其它进程利用
    • 可以通过内存紧缩技术解决,但是性能堪忧
  • 大小固定,不灵活

动态分区(Variable Partitions)

将物理内存分区,但是允许进程中途改变占用内存的多少。

硬件需求:基址寄存器界限寄存器(用于保护)

地址转换:物理地址 = 虚拟地址 + 基地址

优点:

  • 无内部碎片:按需分配进程的内存

缺点:

  • 有外部碎片:作业加载和卸载会产生散布在内存中的空孔

分页(Paging)

分页解决了外部碎片问题。原理是在物理内存和虚拟内存都使用固定大小的单元。

对进程而言,虚拟地址空间是连续的,并且从 0 开始。

而实际上,页面时散布于物理内存的。映射由操作系统负责。

地址转换: 虚拟地址包括页号(virtual page number, VPN)偏移 (offset)

VPN 索引在页表中。页表将 VPN 转换为页框号(page frame number,PFN)

物理地址 = PFN + offset

后面会详细介绍页表。

优点:

  • 容易分配
    • 内存来源于空闲表固定大小区块(chunks)
    • 分配一页只需要从空闲表删除一个区块
    • 因此不存在外部碎片
  • 方便实现交换
    • 所有区块大小相等

缺点:

  • 内部碎片。因为分给程序的页,程序未必能用完。
  • 页表,尤其是多级页表,查询会增加访存次数。(解决方法:硬件缓存页表)
  • 页表项(PTE)占用太多空间(解决方法:对页表分页)

分段

分段就是把逻辑上相关的数据单元划分到一起。每个进程可以有很多段,如栈、数据、文件、函数。

image_up_1639893818afa66e78.jpg

分段可以实现共享内存

地址转换:

逻辑地址由段号偏移量组成。

段表项由 基地址界限 组成。

段表基地址寄存器 Segment-table base register (STBR) 指向内存中段的位置 段表长度寄存器 Segment-table length register (STLR) indicates 记录一个程序的段数

segment number s is legal if s < STLR

image_up_1639894195185ec525.jpg

缺点:

  • 大量外部碎片:在主存内找到空闲的槽块并插入段,会导致很多空洞利用不上。

空闲内存管理

两种基本管理方法

使用位图的管理:使用位图方法时, 内存可能被划分成小到几个字或大到几千字节的分配单元。 每个分配单元对应于位图中的一位, 0 表示空闲, 1 表示占用(或者相反) 。

使用链表的存储管理:维护一个记录已分配内存段和空闲内存段的链表。 其中链表中的一个结点或者包含一个进程, 或者是两个进程间的一个空的空闲区。

为进程分配内存的方法

如何为进程分配到合适大小的内存?

1)首次适配(first fit):简言之使用第一个空闲。

存储管理器沿着段链表进行搜索, 直到找到一个足够大的空闲区, 除非空闲区大小和要分配的空间大小正好一样, 否则将该空闲区分为两部分, 一部分供进程使用, 另一部分形成新的空闲区。

2)下次适配(next fit):简言之从上次结束的地方开始搜索。

和首次适配基本相同,不同点是每次找到合适的空闲区时都记录当时的位置。 以便在下次寻找空闲区时从上次结束的地方开始搜索, 而不是像首次适配算法那样每次都从头开始。

Bays(1977) 的仿真程序证明下次适配算法的性能略低于首次适配算法

3)最佳适配(best fit) :搜索整个链表, 找出能够容纳进程的最小的空闲区。

比首次适配算法或下次适配算法浪费更多的内存, 因为它会产生大量无用的小空闲区。

4)最差适配(worst fit):总是分配最大的可用空闲区。这样剩余区会比较大。

仿真表明,也不是个好办法

5)快速适配(quick fit) 为那些常用大小的空闲区维护单独的链表。

使用独立链表?

如果为进程和空闲区维护各自独立的链表, 那么这四个算法的速度都能得到提高。 缺点:复杂度变高、性能变差。

如果进程和空闲区使用不同的链表, 则可以按照大小对空闲区链表排序, 以便提高最佳适配算法的速度 。

伙伴分配