Pil0tXia 的书房 Pil0tXia 的书房
首页
  • 第一章 操作系统引论
  • 第二章 进程的描述与控制
  • 第三章 处理机调度与死锁
  • 第四章 存储器管理
  • 第五章 虚拟存储器
  • 期末考试备考
汇编语言课程笔记
GitHub (opens new window)
首页
  • 第一章 操作系统引论
  • 第二章 进程的描述与控制
  • 第三章 处理机调度与死锁
  • 第四章 存储器管理
  • 第五章 虚拟存储器
  • 期末考试备考
汇编语言课程笔记
GitHub (opens new window)
  • 关于本文档

    • 操作系统课程笔记
  • 第一章 操作系统引论

    • 单道批处理
    • 多道批处理
    • 并发与并行的区别
    • 分时操作系统
    • 实时操作系统
    • 操作系统的四个基础特性
    • 现代OS的基本单位
    • 作业1
    • 内核
    • 中断和异常
    • 系统调用
    • 冷启动和热启动
    • 补充资料
    • 作业2
    • 附言
  • 第二章 进程的描述与控制

    • 程序的基本概念
    • 进程的基本概念
    • 作业
    • 进程控制
    • 进程的特征
    • 进程同步
    • 进程通信
    • 线程
  • 第三章 处理机调度与死锁

    • 处理机调度的层次
    • 队列调度模型
    • 选择调度算法的原则
    • 调度算法
    • 死锁
  • 第四章 存储器管理

    • 多级存储器结构
    • 程序的装入与链接
    • 连续内存分配
    • 非连续内存分配
      • 基本分页存储管理
        • 基本思路
        • 页面、页框
        • 地址转换的思路
        • 十进制地址
        • 二进制地址
        • 例题
        • 页表
        • 地址变换机构
        • 基本地址变换机构
        • 例题1
        • 具有快表的地址变换机构
        • 例题2
        • 页表项的大小
        • 两级页表
        • 单级页表占用过大的连续内存空间的问题
        • 引入两级页表
        • 单级页表常驻内存的问题
        • 多级页表
        • 习题
      • 基本分段存储管理
        • 基本思路
        • 逻辑地址
        • 段表
        • 段表项的大小
        • 地址转换
        • 分页和分段的对比
        • 划分的角度和维度
        • 信息的共享和保护
        • 访存次数
      • 段页式存储管理
        • 基本思路
        • 逻辑地址
        • 段表
        • 地址转换
        • 访存次数
  • 第五章 虚拟存储器

    • 虚拟存储器概述
    • 请求分页存储管理方式
    • 页面置换算法
    • 内存分配策略和分配算法
    • 抖动与工作集
  • 第六章 输入输出系统

  • 第七章 文件管理

  • 期末考试备考

    • 考试题型
  • 操作系统
  • 第四章 存储器管理
Pil0tXia
2023-01-05
目录
基本分页存储管理
基本思路
页面、页框
地址转换的思路
十进制地址
二进制地址
例题
页表
地址变换机构
基本地址变换机构
例题1
具有快表的地址变换机构
例题2
页表项的大小
两级页表
单级页表占用过大的连续内存空间的问题
引入两级页表
单级页表常驻内存的问题
多级页表
习题
基本分段存储管理
基本思路
逻辑地址
段表
段表项的大小
地址转换
分页和分段的对比
划分的角度和维度
信息的共享和保护
访存次数
段页式存储管理
基本思路
逻辑地址
段表
地址转换
访存次数

非连续内存分配

# 非连续内存分配

固定分区分配容易产生内部碎片,动态分区分配容易产生外部碎片(虽然可以用紧凑技术解决,但是有一定的成本),都不是理想的解决方案。

# 基本分页存储管理

# 基本思路

在连续分配中,一个进程不可被分割,只能整体放入一块连续的内存空间中;但在基本分页存储管理中,允许把一个进程按照固定大小 X 分割为多个部分,同时把内存也按照固定大小 X 分割为多个部分,并把前者对应地放到后者中(不要求连续存放)。通常来说,一个进程的最后一部分会小于 X ,这部分若放到内存的某个 X 空间中,仍然会产生碎片(这种碎片称为页内碎片)。

# 页面、页框

  • 页框 (Page Frame):具体来说,把内存分割为多个固定大小 X 的部分,这些部分就叫做页框 / 页帧 / 物理块 / 内存块,每个页框会有一个数字编号,第一个页框就从 0 开始

  • 页面 (Page):同样,进程被分割为多个固定大小 X 的部分,这些部分就叫做页面 / 页,每个页面会有一个数字编号,第一个页面就从 0 开始

image-20221128191916596

若页面太小,虽然可使页内碎片减小、提高内存利用率,但是会使页表过长、降低页面换进换出的效率;若页面太大,则相反。因此页面的大小应是 2 的整数幂,通常为 1KB~8KB。

系统以页框为单位为各个进程分配内存空间,一个页面就对应一个页框,它具体放到哪个页框是随意的,无需顾虑是否连续和先后顺序。

# 地址转换的思路

假设我们采用动态重定位方式进行模块装入,程序中是逻辑地址,但在程序执行到需要访问地址的时候,需要进行逻辑地址到物理地址的转换。

# 十进制地址

左边进程按照 50B 的大小分为 4 个页面,右边内存按照 50B 的大小分为若干个页框:

image-20221128192409450

在程序执行到指令 1 的时候,需要访问地址 80,这是一个逻辑地址,需要转换成对应的物理地址。转换步骤如下:

  • 计算逻辑地址的页号
  • 根据页号找到页号对应页面在内存中的起始地址
  • 计算逻辑地址在当前页面内的偏移量(页内偏移量)
  • 物理地址 = 起始地址 + 页内偏移量

从左图可以看出,逻辑地址 80 在 1 号页面内,而 1 号页面对应的是右图中的红色页框,起始地址为 450;逻辑地址 80 在 1 号页面内的偏移量为 30;所以 物理地址 = 450 + 30 = 480

也可以用计算的方法,在已知逻辑地址的情况下:

  • 页号 = 逻辑地址 / 页面大小 ,即 80/50 = 1 (取整数部分)
  • 页内偏移量 = 逻辑地址 % 页面大小 ,即 80%50 = 30

# 二进制地址

地址实际上是用 32 位二进制数表示的。这时候计算页号 P 和页内偏移量 W 实际上更加简单,因为地址本身已经包含了这两者的信息。

以页面 / 页框大小 4KB 为例,用地址的前 20 位(红色部分,也叫高 20 位)表示页号 P,用地址的后 12 位(黑色部分,也叫低 12 位)表示页内偏移量 W。页内偏移量的位数可以表明每个页面的大小,即 212 = 4KB。0 号页、1 号页、2 号页的表示如下:

image-20221128192830159

若页面 / 页框大小为 1KB,也即 210B = 1024B,那么地址的前 22 位表示页号,剩余的 10 位表示页内偏移量:

image-20221128192842511

# 例题

IMG_20221201_110859

IMG_20221201_111601

# 页表

根据地址,就已经可以知道页号和页内偏移量,还有一个工作是根据页号找到对应页面在内存中的物理地址。

每一个进程都有一张页表来记录页面号(页号)与页框号(块号)的映射关系,可以根据页号找到内存中对应页框的编号。其中页号是隐含的,相当于从 0 开始的下标,不占存储空间,页表实际只保存了块号。

image-20221128192853911

根据地址知道页号后,从页表中找出页号对应的块号,再用 块号 * 页框大小 ,即可算出块的起始地址。用 起始地址 + 偏移量 ,即可算出物理地址。

# 地址变换机构

# 基本地址变换机构

上述的地址转换是通过基本地址变换机构这个硬件实现的,它借助页表将逻辑地址转换为物理地址。转换过程如下:

image-20221128192904519

在程序未执行的时候,PCB 中存放程序对应页表的初始地址 F 以及页表长度 M(页表项个数)。程序一旦开始执行,F 和 M 会被送到页表寄存器中。在需要访问地址的时候,基本地址变换机构开始运行:

  • 首先将逻辑地址 A 拆分为页号和页内偏移量两个部分,然后将页号与页表寄存器中的页表长度作比较。页表长度即页表项个数,即页面个数,因此页号是不能大于等于(不能等于,因为页号从 0 开始计算)页表长度的,如果页号越界就会发生越界中断。
  • 由于页表中每个页表项的大小是一样的(假设为 size),且已经知道了页表在内存中连续分配的起始地址(假设为 X),所以页号 P 对应的页表项的存放地址等于 X + P*size ,在这个地址保存着页号对应的块号
  • 将块号与偏移量的二进制数拼接,就得到了物理地址,得以访问目标

例子中涉及到的都是二进制数,要计算物理地址,只需要将块号二进制数与偏移量二进制数拼接即可。如果例子给出的是十进制数,则应用 块起始地址 + 页内偏移量 进行相加,计算结果再转化为二进制数。

# 例题 1

若给定的是十进制:

页面大小 1KB,块号 2,偏移量 1023。

块起始地址等于 2 * 1KB = 2 * 1024B = 2048B ,又偏移量 1023,所以物理地址等于 2048 + 1023 = 3071 ,转化为 32 位二进制数,就是 0000000000000000000010,1111111111

若给定的是二进制:

页面大小 1KB,块号 2,偏移量 1111111111。

块号 2 转化为 22 位二进制数就是 0000000000000000000010 ,与偏移量拼接,就得到 0000000000000000000010,1111111111 ,与十进制的结果是一样的。

# 具有快表的地址变换机构

在前面的基本地址变换机构中,存在两个问题:

  • 每次存取数据都需要访问内存两次:第一次访问内存中的页表,找到块号,并将块号与偏移量拼接得到物理地址;第二次根据物理地址访问内存中存放的数据。第二次访存肯定是不能避免的,但是第一次访存可以想办法避免
  • 若多条指令涉及到的逻辑地址的页号都相同,就都必须经历第一次访存,找到该页号对应的块号

这两个问题可以通过引入快表来解决。

快表(联想寄存器)是一种访问速度比内存快很多的高速缓冲存储器,用以存放访问过的页表项的副本,从而加快地址转换的过程。引入快表后,地址转换大概率不需要经历第一次访存,而是直接从快表中拿到需要的页表项。于是内存中原本的页表被称为慢表。

此时的地址变换机构的运行过程和之前还是差不多的,只是多了一个快表的处理过程:

image-20221128192914850

在程序未执行的时候,PCB 中存放程序对应页表的初始地址 F 以及页表长度 M(页表项个数)。程序一旦开始执行,F 和 M 会被送到页表寄存器中。在需要访问地址的时候,地址变换机构开始运行:

  • 首先将地址拆分为页号和页内偏移量两个部分,然后将页号与页表寄存器中的页表长度作比较。若越界,则发生越界中断。
  • 该页号被送往快表,并与其中的页表项比较,寻找是否有匹配的页号。因为这里我们是第一次查询,所以是没有的,即未命中,页号被送往慢表。
  • 第一次访存,在慢表中找到页号对应的页表项的地址,意味着找到了页号对应的块号
  • 将该页表项拷贝一份副本放到快表中
  • 将块号与偏移量的二进制数拼接,就得到了物理地址,得以访问目标

我们需要继续访问某个地址,并且与上次访问的地址的页号一样:

  • 首先将地址拆分为页号和页内偏移量两个部分,然后将页号与页表寄存器中的页表长度作比较。若越界,则发生越界中断。
  • 该页号被送往快表,并与其中的页表项比较,寻找是否有匹配的页号。因为快表中已经存放了一份页表项的副本,所以找到了匹配的页号,即命中。
  • 从快表中读出该页号对应的块号,并与偏移量拼接,就得到了物理地址,得以访问目标

# 例题 2

某系统使用基本分页存储管理,并采用了具有快表的地址变换机构。假设访问一次快表耗时 1us,访问一次内存耗时 100us,快表的命中率为 90%。

  • 若未引入快表,则访问一个逻辑地址耗时 100 + 100 = 200us

  • 若引入快表,则访问一个逻辑地址耗时 (1+100) * 0.9 + (1+100+100) * 0.1 = 111 us

  • 若引入快表,且该系统支持同时查询快表和慢表,则访问一个逻辑地址耗时 (1+100) * 0.9 + (100+100) * 0.1 = 110.9us

IMG_20221201_112527

# 页表项的大小

假设某系统物理内存大小为 4GB,页面大小为 4KB,则每个页表项至少应该为多少字节?

一条页表项的大小取决于块号的位数。的 4GB=232B, 4KB=212B,因此 4GB 的内存总共会被分为 232/212 = 220 个内存块,因此内存块号的范围应该是 0~220-1。因此对于单个页表项,它要用一个 20 位二进制数才能表示这样的一个内存块号,而一个字节 8 位,所以至少要 3B 才可以表示这样的一个内存块号。

但是一个页表项用 3 个字节其实会出现一些问题。类似于进程被拆分为多个页面存储在内存中一样,页表也是被拆分为多个页表项存储在内存中的。假设页面 / 页框大小为 4KB,也即 4096B,由于一个页表项 3B,所以一个页框至多可以放 4096/3=1365 个页表项,并且这个页框剩余 1B 的空间。由于 1B 不足以再存放一个页表项,所以第 1366 个页表项(1365 号页表项)只能放在下一个页框中了。

这就会导致,前面 1365 个页表项的地址依然可以采用 X + 3*P 的方式计算,但是第 1366 个页表项,它的地址却应该是 X + 3*P + 1 ,也就是说,我们无法以一个通用的式子去计算页表项的存放地址。

因此,一个页表项的大小通常应选取 2 的整数幂。如果页表项大小为 4B,那么一个页框就刚好可以放 4096/4=1024 个页表项,余下的页表项可以依次放在下一个页框中。这样,涉及到页表项地址的计算都可以用通用的式子 X + 4*P ,就无需考虑由于页框无法得到完全利用而带来的查询麻烦的问题了。当然,为了这个式子能够通用,页表通常也应该连续地存放在内存块中,中间不出现断节。

Q: 首先,在 页表项的大小 中,按照您的讲述,第 1366 个页表项的地址应为 X + 3*(P+1) 。另外,我对 “一个页表项的大小应同样选取 2 的整数幂” 的说法抱有疑问,因为 “一个页框能否在没有剩余空间的情况下装入足够多的页表项” 并不会影响到 “利用页号在页表中找到对应的块号”。即使页表项大小为 3B 时,第 1366 个页表项会被装入下一个页框,但是当页表项大小为 4B 时,第 4097 个页表项也同样会被装入下一个页框,不是吗?请问您是怎么理解的呢?

A: 页表项的地址≠块号,页表项的存放地址的数据内容才是块号。同样的,块号≠内存块的物理地址,块号是内存块在内存中组织顺序的索引, 块号 * 页框大小 才等于内存块的起始物理地址。

问题不在于 “如何从已经找到地址的页表项中读取块号”,而在于 “如何根据隐含的页号找到页表项的存放地址”。页号是隐含的,页表中并没有储存页号,我们无法根据页号直接读取到页表项存储的块号,必须先根据 X + P*size 这个式子来确定页表项的存放地址。页表项大小为 3B 时,第 1365 个页表项和第 1366 个页表项之间间隔了未分配的 1B,先前 X + 3*P 的寻址规律就被打破了。 X + 3*P + 1 中的 +1 是前一个页框剩余的 1B,而不是 “下一个页框” 的意思。

# 两级页表

# 单级页表占用过大的连续内存空间的问题

假设页面 / 页框大小 4KB,页表项大小 4B,一个页表占用的空间:

  • 计算页表一共有多少个页表项:4KB = 212B,所以 32 位逻辑地址中,后 12 位表示偏移量,前 20 位表示页号。总共有 220 个页面,也就是有 220 个页表项需要存放。
  • 计算一个页框可以放多少个页表项:一个页框 4KB,一个页表项 4B,所以一个页框可以放 4096/4 = 1024 个页表项
  • 计算存放所有页表项需要多少个页框:220/1024 = 1024

需要 1024 个页框才能放下整个页表,而且为了以通用的式子计算页表项地址,页表必须是连续存放的,这违背了分页存储的初衷。

# 引入两级页表

就像进程拆分为多个页面一样,页表也可以进行拆分:将长的单级页表分为多个子页表,再将每每个子页表离散地存放到各个内存块中。在之前的例子中,一个页框可以放 1024 个页表项,那么每 1024 个页表项就拆分出一个子页表,因为页表一共有 220 个页表项,所以一共可以拆分出 1024 个子页表,这些子页表再各自存放到内存块中。

于是,我们需要一张页目录表(一级页表 / 顶层页表 / 外层页表)来记录页目录表和子页表(二级页表)之间的映射关系,如下图:

image-20221128192925065

同时,之前的逻辑地址的含义也发生了改变。在单级页表中,前 20 位表示页号;而在两级页表中,前 10 位表示一级页号(一级页表的页号),紧跟着的 10 位表示二级页号(二级页表的页号)。这么划分之后,一级页号共有 210=1024 种可能的取值,即页目录表的 1024 个页表项;二级页号也有 210=1024 种可能的取值,即子页表的 1024 个页表项。

在需要进行地址转换时:

  • 首先将逻辑地址分为三个部分:一级页号、二级页号、页内偏移量
  • 然后从 PCB 中读出页目录表的初始地址,结合一级页号以及每个页表项的大小,找到一级页号对应页表项的地址,即读取到了一级页号对应的块号
  • 根据块号到内存中找到对应的二级页表
  • 在二级页表中,根据二级页号找到对应的块号
  • 块号 * 页框大小 + 偏移量 得到物理地址

上面的过程也可以直接看这幅图理解:

image-20221128192933032

# 单级页表常驻内存的问题

执行程序时,往往只需要访问特定的几个页面,但整个单级页表是常驻在内存中的。[虚拟存储技术](# 第五章 虚拟存储器) 可以在需要访问页面的时候才把对应的页表项调入内存。

# 多级页表

某系统按字节编址,采用 40 位逻辑地址,页面大小为 4KB,页表项大小为 4B,假设采用纯页式存储,则要采用多少级页表?页内偏移量为多少位?

4KB = 4*1024B = 212B,根据之前讲过的,页面偏移量应该是 12 位。40 - 12 = 28,所以前面 28 位用来表示页号。

因为采用多级页表后,各级页表的大小不能超过一个页面,而一个页面最多只能放 1024 个页表项,所以应该限制页表最多只能包含 1024 个页表项(否则就放不下多余的页表项,导致页表超过一个页面),即逻辑地址中的 10 位二进制数。

在逻辑地址的前 28 位中,可以选择 10 位用于表示某一级的页号(这一级的页表假设页表项可能有 1024 个这么多),再用 10 位表示某一级的页号(这一级的页表假设页表项可能有 1024 个这么多),再用剩下的 8 位表示某一级的页号(这一级的页表假设页表项远远少于 1024 个)。

也可以考虑前面 8 位作为一级页号,紧接着的 10 位作为二级页号,再紧接着的 10 位作为三级页号,这样刚好就用完了逻辑地址前 28 位。所以题目需要采用三级页表。

那如果这里不采用三级页表,强行使用二级页表,则必定有某一级的页号位数超过了 10,说明页表的页表项个数超过了 210=1024 个,很显然就会导致一个页框放不下这一级的页表,需要跨页,这与规定 “采用多级页表后,各级页表的大小不能超过一个页面” 是相悖的。

# 习题

  1. 若系统采用两级分页存储方式,物理内存 64MB,页面大小 1KB,页表项大小 2B,则顶级页表有多少个页表项?

这里我们可以参考之前求页表项大小的思路。物理内存 64MB = 226B,表示这么多内存需要 26 位逻辑地址。这 26 位中,一部分表示一级页号,一部分表示二级页号,剩下的表示页内偏移量。

因为页面大小 1KB = 210B,所以页内偏移量需要 10 位来表示,余下 16 位供一、二级页号使用。一个页面大小 210B,一个页表项 2B,所以一个页框可以最多可以放 210/2 = 29 个页表项,又由于各级页表不能超过一个页面,所以各级页表都不能超过 29 个页表项。在余下的 16 位中,用 9 位表示二级页表的页号(此时该页表的页表项个数取满)。剩下的 7 位表示一级页表的页号,可以包含 27 = 128 个页表项。

  1. 若系统采用分页存储方式,物理内存 256MB,页面大小 1KB,页表如下:

页号 0,1,2,3,4,5,6,7,8,9,10 分别对应块号 15,16,20,28,29,30,31,32,36,38,39

则逻辑地址 1A68(16 进制)对应的物理地址是多少?

为了方便计算,我们先统一用十进制计算,得到十进制的物理地址后再转换为十六进制。

1A68 按权展开转化为对应的十进制数字是 6760,对于逻辑地址 6760,可以计算它的页号和页内偏移量:

  • 页号 = 6760/1024 = 6(取整数部分)
  • 页内偏移量 = 6760%1024 = 616

根据页号 6 找到块号 31,根据块号 31 计算块初始地址为 31*1024 = 31744,偏移量和初始地址相加得到的物理地址为 31744+616 = 32360。32360 是十进制的物理地址,短除法转化为对应的十六进制物理地址就是 7E68。

若统一使用二进制计算:

256MB = 228B 逻辑地址共 28 位

1A68 转换为二进制:0001 1010 0110 1000

页内偏移量 10 位

28-10=18 页号位数

补齐位数 0000 0000 0000 0001 1010 0110 1000

即 000000000000000110,1001101000

页号为 6,起始地址 31*1024=31744

出题者想让你用十进制做,因为给的是十进制的页表

  1. 若系统采用分页存储方式,物理内存 1MB,共有 32 个页面,一个页面 2KB,则逻辑地址一共多少位?

因为物理内存 1MB = 220B,所以逻辑地址 20 位。

根据上面的经验,我们可能会这么做,但是这是错误的做法。上面的习题都没有告诉我们程序具体被划分为多少个页面,所以我们认为物理地址需要多少位,逻辑地址也需要多少位。但是这道题已经告诉了我们程序具体被划分为 32 个页面 —— 显然,仅仅 32 个页面是不需要 20 这么多位的逻辑地址的。

逻辑地址包括两部分,页号和页内偏移量:

  • 考虑页内偏移量位数。由于一个页面 2KB,也即 211B,所以页内偏移量占 11 位(注意这点是不变的)
  • 考虑页号位数。由于页面仅仅被划分为 32 = 25 个,所以页号只需要 5 位

11 + 5 = 16,所以逻辑地址一共 16 位。

当题目明确给出分页个数的时候,按照页号位数 + 偏移量位数计算逻辑地址总位数。

# 基本分段存储管理

# 基本思路

在基本分页存储管理中,我们将程序分为多个大小相等的物理单元(页面)。而在基本分段存储管理中,我们倾向于从逻辑功能的角度去考虑,将程序分为多个逻辑功能段,每个段都有自己的段名,并且都从 0 开始编址。分配内存时以段为单位进行分配,段内所占内存空间是连续的,但是各个段之间可以不相邻,如下图:

image-20221128192944911

编写程序时可以将程序按照逻辑功能模块进行划分,会更加方便,可读性会更高,比如:

LOAD 1,[D]|<A>
STORE 1,[X]|<B>
1
2
1
2

分别表示:将分段 D 中 A 单元内的值读入寄存器 1,以及将寄存器 1 的值存入分段 X 的 B 单元中。这里的分段 D 和 X 都是段名,程序员在编程的时候只需要使用段名,编译时段名会转化为对应的段号。同理,A、B 单元编译时也会转化为寄存器地址。

# 逻辑地址

分段存储管理中逻辑地址的含义与分页存储管理不同。假设仍然是用 32 位二进制数表示逻辑地址,地址的前 16 位表示段号,后 16 位表示段内偏移量:

  • 段号是 16 位二进制数,有 216 种取值,即每个进程最多可以被分为 216 个段
  • 段内偏移量也是 16 位二进制数,在一个段内,段内地址可能有 216 种取值,所以一个段的最大长度为 216

# 段表

类似的,我们需要用段表来记录某个编号段与实际物理存放位置之间的映射关系。在分段存储管理中,程序被分为大小不等的多个段,且不连续,没法像之前一样只凭借块号来推导块的初始地址。为了准确地找出段存放在内存中的位置,我们要将段号、段长、基址 这三者作为段表的三列。这样,根据段号可以在段表中找到对应段在内存中的基址(即起始地址,不是块号),再结合段长,可以知道这个段具体占用了哪里的空间。

如下图所示:

image-20221128192954137

# 段表项的大小

每个段表项由段号、段长、基址构成,我们可以依次考虑每一列可能占用的空间(假设物理内存 4GB,按字节寻址):

  • 基址:因为物理内存 4GB,也就是 232B,那么内存中的地址最多可能取到 232 种值。为了让基址列足够表示这些值,基址列占用了 32 位。
  • 段长:前面讲过,在逻辑地址中,段号和段内偏移量都是 16 位,所以段内偏移量最多可能取到 216 种值,为了让段长列足够表示这些值,段长列占用了 16 位
  • 段号:和页表一样,在段表中同样隐含段号,因为段表也是连续的,我们只需要知道段表的起始地址和每个段表项的大小就能定位一个段表项的地址,而无需去维护一个从段号到段表项的映射。

因此,每个段表项占用了 16+32=48 位,一个字节 8 位,占用了 6 个字节, 即 6B。

# 地址转换

转换过程我们可以直接看下图理解:

image-20221128193010730

可以联系分页存储的地址转换过程。在需要将逻辑地址转换为物理地址的时候:

  • 首先将逻辑地址分为段号和段内偏移量两个部分,段表寄存器中的段表长度保存了程序总共被分为了多少段,因此段号不应该超过段表长度,若超过则发生越界中断。
  • 根据段号、段表初始地址和段表项的大小,找到段号对应的段表项。比较段表项中的段长 C 和逻辑地址中的段内偏移量 W,若 W >= C 则发生越界中断(此处比分页存储多一次越界判断,因为页表的页框大小固定,且受页内偏移量位数限制不会越界,而段长可变)
  • 在段表项中找到段号对应的基址,将该基址与段内偏移量拼接,得到物理地址,得以访问目标

# 分页和分段的对比

# 划分的角度和维度

image-20221128193022033

# 信息的共享和保护

在分段存储方式中,更容易实现信息共享和保护:

image-20221128193032194

可重入代码 (Reentry code) 也叫纯代码 (Pure code) 是一种允许多个进程同时访问的代码。为了使各进程所执行的代码完全相同,故不允许任何进程对其进行修改。程序在运行过程中可以被打断,并由开始处再次执行,并且在合理的范围内(多次重入,而不造成堆栈溢出等其他问题),程序可以在被打断处继续执行,且执行结果不受影响。

在分页存储方式中,则很难:

image-20221128193042146

# 访存次数

两者的访存次数是一样的:

  • 若不引入快表,两者的第一次访存都是访问内存中的页 / 段表,第二次是访问内存中的目标。
  • 若引入快表,则两者的第一次访存有可能因为命中而省去。

# 段页式存储管理

# 基本思路

  • 采用分页存储管理,内存利用率高,不会产生外部碎片,仅会产生少量内部碎片;但是不方便按照逻辑模块实现信息的共享和保护
  • 采用分段存储管理,可以按照逻辑模块实现信息的共享和保护,但是若逻辑过多则会导致段过长,另外,这种方式也会产生外部碎片

所以结合二者之长,出现了段页式存储管理方式。

如下图,段页存储管理会首先将进程按照逻辑模块划分为多个段,针对每个段再划分为多个页;同时也把内存划分为多个页框。分配内存的时候,一个页面就对应了一个页框。

image-20221128193050234

# 逻辑地址

在分段存储管理中,给出一个逻辑地址,可以划分为段号和段内地址两个部分;而在段页存储管理中,段内地址还要继续细分成页号和页内偏移量两个部分。所以逻辑地址由段号、页号和页内偏移量三个部分组成。

段号的位数仍然决定了一个进程可以被划分为多少个段,而页号的位数则决定了一个段可以被划分为多少个页面,页内偏移量则决定了一个页面可以有多大,即页面 / 页框大小。

和分段存储管理一样,段页存储管理的地址结构也是二维的。

# 段表

段页存储管理中的段表不同于分段存储管理中的段表。程序被划分为多个段,每个段都会再被划分为多个页面,因此每一个段都维护着属于自己的一张页表。段表需要记录的是段号与段号对应段的页表之间的映射关系,包括段号、页表长度和存放页表的块号(块号 * 页框大小 = 页表所在块的起始地址)。段号是隐含的。

image-20221128193058929

# 地址转换

image-20221128192331085

段页式存储的地址转换机构结合了分页存储和分段存储的方式,在需要将逻辑地址转换为物理地址的时候:

  • 首先将逻辑地址分为段号、页号和页内偏移量三个部分,段表寄存器中的段表长度仍代表程序总共被分为多少个段,因此段号不应该超过段表长度,若超过则越界中断(同段式存储第一次越界检查)
  • 根据段号、段表初始地址以及段表项的大小,找到段号对应的段表项。可以从这个段表项读取到该段号对应的页表的位置和大小。这里同样要比较段表项中的页表长度和逻辑地址中的页号 P,若页号大于等于页表长度则越界中断(同页式存储唯一一次越界检查,不同于段式存储第二次越界检查)
  • 找到了段表项就是找到了该段的页表所在块的块号。根据块号,在内存中找到这个块,再从块中找到页表
  • 根据逻辑地址中的页号,在页表中找到页号对应的块号,将块号和逻辑地址中的页内偏移量拼接,得到物理地址,得以访问目标

# 访存次数

不采用快表时,段页式存储管理需要经历三次访存:第一次访存,访问内存中的段表,找到段表中记录的页表信息;第二次访存,访问内存中的页表,找到目标所在的块;第三次访存,访问内存中的目标。

如果采用快表,会利用段号和页号去寄存器中检索,若命中,则无需经历第一次和第二次访存,可以直接拿到块号并和偏移量进行拼接,得到物理地址。同样只需要一次访存。

上次更新: 2023/01/06, 19:28:46

← 连续内存分配 虚拟存储器概述→

Copyright © 2022-2025 Pil0tXia | CC BY-NC-SA 4.0 Licensed | 苏ICP备2023001491号-1
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式