存储

存储资源是一种宝贵的资源，无论存储器有多大，程序最终都能将其耗尽。

静态存储器SRAM：读写速度块、生产成本高、多用作Cache

动态存储器DRAM：读写速度慢、集成度高、生产成本低、多用作主存储器

存储组织

存储组织：在存储技术和CPU寻址技术许可的范围内组织合理的存储结构。

合理结合不同的存储器，达到各层次的存储器都处于均衡的繁忙状态的理想效果（命中率），营造又快又大的错觉。

典型的层次式存储组织：访问速度越来越慢，容量越来越大，价格越来越便宜

存储管理

存储管理的功能：

  • 存储分配和回收：存储管理的主要内容

    • 关注其算法和相应的数据结构

  • 地址变换：

    • 可执行文件生成中的链接技术
    • 程序加载时的重定位技术
    • 进程运行时硬件和软件的地址变换技术和机构

  • 存储共享和保护：代码和数据共享，对地址空间的访问权限（读、写、执行）。

  • 存储器扩充：涉及存储器的逻辑组织和物理组织；

    • 由==应用程序控制：覆盖==
    • 由==OS控制：交换==（整个进程空间），请求调入和预调入（部分进程空间）

编译、链接、装入

怎么从代码到可执行文件。

gcc的工作

GCC编译器驱动程序读取源程序文件*.c，并把它翻译成一个可执行目标文件*。

这个翻译过程分为四个阶段：预处理（Preprocessing）、编译（Compilation）、汇编（Assembly）、链接（Linking）。

执行这四个阶段的程序：预处理器、编译器、汇编器、链接器，一起构成了编译系统。

gcc调用包含的工具：

  • cc1：预处理器和编译器
  • as：汇编器
  • collect2：链接器

具体流程：

  1. 预处理阶段

    1. 处理所有的预处理，包括define，ifdefine
    2. 删除所有的注释。
    3. 添加行号和文件标识，以便编译时产生调试用的行号及编译错误警告行号。
    4. 保留所有的#pragma编译器指令，因为编译器需要使用它们。
    5. 使用gcc -E hello.c -o hello.i命令来进行预处理， 预处理得到的另一个程序通常是以.i作为文件扩展名。

  2. 编译阶段

    1. 编译器ccl将预处理完的文本文件hello.i翻译成文本文件hello.s，它包含一个汇编语言程序：为不同高级语言的不同编译器提供了通用的输出语言。
    2. 该程序包含函数main的定义。

  3. 汇编阶段：

    1. 汇编器as将hello.s翻译成机器语言指令
    2. 把这些指令打包成一种叫做可重定位目标程序的格式
    3. 并将结果保存在目标文件hello.o中，hello.o是一个二进制文件。

  4. 链接

    1. hello程序调用了printf函数，它存在于一个名为printf.o的单独的预编译好了的目标文件中，而这个文件必须以某种方式合并到我们的hello.o程序中。
    2. 连接器ld就负责处理这种合并。结果就得到了hello文件，它是一个可执行目标文件（或者称为可执行文件）
    3. 可执行文件可以被加载到内存中，由系统执行。

可执行文件

可执行文件的常见格式为ELF文件。

  1. ELF头：包括程序的基本信息，比如体系结构和操作系统，同时也包含了节头表和段头表相对文件的偏移量（offset）。

  2. 段头表（或程序头表，program header table）：主要包含程序中各个段（segment）的信息，段的信息需要在运行时刻使用。

    每一个表项，记录了该段数据载入内存时的目标位置等，记录了用于指导应用程序加载的各类信息。

  3. 节头表（section header table）：主要包含程序中各个节（section）的信息，节的信息需要在程序编译和链接的时候使用。

    每一个表项，记录了该节程序的代码段、数据段等各个段的内容，主要是链接器在链接的过程中需要使用。

段头表和节头表指向了同样的地方，这意味着两者只是程序数据的两种视图：

  1. 组成可重定位文件，参与可执行文件和可共享文件的链接。此时使用节头表。
  2. 组成可执行文件或者可共享文件，在运行时为加载器提供信息。此时使用段头表。
image-20240318203921231 image-20240318203948152

具体划分

一个程序本质上都是由bss段、data段、text段三个组成的。

  • bss段（bss segment）：属于静态内存分配
    1. 未初始化的全局变量
    2. 未初始化的static变量
    3. 未初始化的常量
  • data段（data segment）：数据段属于静态内存分配
    1. 已初始化的全局变量
    2. 已初始化的static变量
  • text段（code segment/text segment）：代码段用来存放程序执行代码。
    • 这部分区域的大小在程序运行前就已经确定
    • 通常属于只读（某些架构也允许代码段为可写，即允许修改程序）
    • 在代码段中，也有可能包含一些只读的常数变量，例如字符串常量等

text和data段都在可执行文件中，由系统从可执行文件中加载，而bss段不在可执行文件中，由系统初始化。

一个装入内存的可执行程序，除了bss、data和text段外，还需构建一个栈（stack）和一个堆（heap）。

  • 栈(stack)：存放、交换临时数据的内存区
    • 用户存放程序局部变量的内存区域、
    • 保存/恢复调用现场：在函数被调用时，其参数也会被压入发起调用的进程栈中，并且待到调用结束后，函数的返回值也会被存放回栈中。
    • 同一进程的不同线程可以通过指针访问栈上变量进行共享，不同进程间不可以
  • 堆（heap）：存放进程运行中动态分配的内存段
    • 它的大小并不固定，可动态扩张或缩减。
    • 当进程调用malloc等函数分配内存时，新分配的内存就被动态添加到堆上（堆被扩张）；
    • 当利用free等函数释放内存时，被释放的内存从堆中被剔除（堆被缩减）。

image-20240318210916389

text段和data段都在可执行文件中，bss段不再，由系统进行初始化

重定位

  1. 地址空间：源程序经过编译后得到的目标程序，存在于它所限定的地址范围内，这个范围称为地址空间。地址空间是逻辑地址的集合。
  2. 存储空间：存储空间是指主存中一系列存储信息的物理单元的集合，这些单元的编号称为物理地址或绝对地址。存储空间是物理地址的集合。

作业会有存储空间装入存储空间。重定位是在装入时对目标程序中的指令和数据地址的修改，或映射过程。

在编译后，原先的函数跳转变为了形如jal func_name的汇编指令，但是具体的跳转地址却是0。这是因为编译时函数定义在不同的文件中，无法知道准确的地址，因而需要重定位来填入具体的地址。

重定位的过程在连接中完成。链接将生成的机器码.o文件链接到一起，形成最终的可执行文件。在链接时，链接器会扫描各个目标文件，将之前未填写的地址填写上，从而生成一个真正可执行的文件。

在Mips体系结构中，Elf32_Rel给出了重定位的地点：

  • r_offest给出了使用重定位动作的地点。
    • 对重定位文件来说，值是从节起始处到受重定位影响的存储单元的字节偏移量；
    • 对可执行文件或共享目标文件来说，它的值是受重定位影响的存储单元的虚拟地址。
  • r_info给出了与重定位修改地点有关的符号表索引和所使用的重定位的类型。
1
2
3
4
typedef struct {
    Elf32_Addr r_offset;
    Elf32_Word r_info;	//(symbol:24; type:8)
} Elf32_Rel;

重定位/链接的本质：合并不同可执行文件中相同的节

image-20240318211052894

程序

程序的入口也写在ELF文件中，但是不是Main函数的地址。一般为_start函数，在这个入口函数中调用了main。

执行程序的过程：shell调用fork()系统调用，创建出一个子进程子进程调用Execve()加载program

  • 装载前的工作：shell调用fork()系统调用，创建出一个子进程。

  • 装载工作：子进程调用execve()加载program（即要执行的程序）。

  • 程序如何被加载：

    加载器在加载程序的时候只需要看ELF文件中和segment相关的信息即可。

    • 读出的信息分为两部分，一部分是各segment的具体信息，另一部分是section和segment之间的对应关系。类型为Type为Load的segment是需要被加载到内存中的部分。

    1. 读取ELF头部的魔数(Magic Number)，以确认该文件确实是ELF文件。

      ELF文件的头四个字节依次为0x7f、E、L、F。加载器会首先对比这四个字节，若不一致，则报错。

    2. 找到段表项。

      ELF头部会给出的段表起始位置在文件中的偏移，段表项的大小，以及段表包含了多少项。根据这些信息可以找到每一个段表项。

    3. 对于每个段表项解析出各个段应当被加载的虚地址，在文件中的偏移。以及在内存中的大小和在文件中的大小。（段在文件中的大小小于等于内存中的大小）。

    4. 对于每一个段，根据其在内存中的大小，为其分配足够的物理页，并映射到指定的虚地址上。再将文件中的内容拷贝到内存中。

      1. 若ELF中记录的段在内存中的大小大于在文件中的大小，则多出来的部分用0进行填充。
      2. 一个segment在文件中的大小是小于等于其在内存中的大小：如果在文件中的大小小于在内存中的大小，那么在载入内存时通过补零使其达到其在内存中应有的大小。

    5. 设置进程控制块中的PC为ELF文件中记载的入口地址。

    6. 各个segment都装入内存后，控制权交给应用，从应用入口开始，将控制权交给进程开始执行！

image-20240318205727189

存储管理

存储管理的基石：

  1. 地址独立：程序发出的地址与物理地址无关
  2. 地址保护：一个程序不能访问另一个程序的地址空间

存储管理要解决的问题：分配和回收

后续内容会产生一种虚拟存储系统的感觉，实际上，虚拟存储系统是在存储管理的基础上建立起来的。

存储分配

  1. 直接指定方式：程序员在编程序时，或编译程序(汇编程序)对源程序进行编译(汇编)时，所用的是实际地址（即为物理地址）。
  2. 静态分配(Static Allocation)：程序员编程时，或由编译程序产生的目的程序，均可从其地址空间的零地址（虚拟地址）开始；当装配程序对其进行连接装入时才确定它们在主存中的地址。
  3. 动态分配(Dynamic Allocation)：作业在存储空间中的位置，在其装入时确定,在其执行过程中可根据需要申请附加的存储空间，而且一个作业已占用的部分区域不再需要时，可以要求归还给系统。

单道程序

单道程序：整个内存中只有两个程序，一个用户程序（也是唯一的用户程序）和操作系统。

操作系统所占空间是固定的，因而可以将用户程序加载到同一个地址，即用户地址永远从同一个地方开始运行。

因为只有一个用户程序，故天然的有地址独立和地址保护。这样的操作不需要地址映射，可以直接使用物理地址。

优点：执行过程中无需任何地址翻译工作，程序运行速度快。

缺点：

  1. 比物理内存大的程序无法加载，因而无法运行。
  2. 造成资源浪费：小程序会造成空间浪费、I/O时间长会造成计算资源浪费。

多道程序

空间分配为分区式：把内存分为一些大小相等或不等的分区(partition)，每个应用程序占用一个或几个分区。操作系统占用其中一个分区。

支持多个程序并发执行，但难以进行内存分区的共享

分区方式

  • 固定（静态）式分区分配：程序适应分区。
  • 可变（动态）式分区分配：分区适应程序。
固定式分区

把内存划分为若干个固定大小的连续分区。

  • 分区大小相等：只适合于多个相同程序的并发执行（处理多个类型相同的对象）。
  • 分区大小不等：多个小分区、适量的中等分区、少量的大分区。根据程序的大小，分配当前空闲的、适当大小的分区。

优点：易于实现，开销小。

缺点：内碎片造成浪费，分区总数固定，限制了并发执行的程序数目。

采用的数据结构：分区表：记录分区的大小和使用情况

  1. 单一队列的分配方式

    当需要加载程序时，选择一个当前闲置且容量足够大的分区进行加载，可采用共享队列的固定分区（多个用户程序排在一个共同的队列里面等待分区）分配。

    image-20240318212212119

  2. 多队列分配方式

    由于程序大小和分区大小不一定匹配，有可能形成一个小程序占用一个大分区的情况，从而造成内存里虽然有小分区闲置但无法加载大程序的情况。这时，可以采用多个队列，给每个分区一个队列，程序按照大小排在相应的队列里。

    image-20240318212217725
可变式分区

可变式分区：分区的边界可以移动，即分区的大小可变。

==在程序装入时动态建立，大小量身定制。==

优点：没有内碎片

缺点：有外碎片

image-20240318212333066

闲置空间的管理

在管理内存的时候，OS需要知道内存空间有多少空闲。这就需要跟踪内存的使用。

跟踪的办法有两种：位图表示法（分区表）和链表表示法（分区链表）

image-20240318212909769

  1. 位图表示法

    给每个分配单元赋予一个字位，用来记录该分配单元是否闲置。例如，字位取值为0表示单元闲置，取值为1则表示已被占用，这种表示方法就是位图表示法。

    image-20240318212431295

  2. 链表表示法

    将分配单元按照是否闲置链接起来，这种方法称为链表表示法。

    image-20240318212442396

位图表示法：

  • 空间成本固定：不依赖于内存中的程序数量。
  • 时间成本低：操作简单，直接修改其位图值即可。
  • 没有容错能力：如果一个分配单元为1，不能肯定应该为1还是因错误变成1。

链表表示法：

  • 空间成本：取决于程序的数量。
  • 时间成本：链表扫描通常速度较慢，还要进行链表项的插入、删除和修改。
  • 有一定容错能力：因为链表有被占空间和闲置空间的表项，可以相互验证。

可变分区的管理

内存分配采用两张表：已分配分区表和未分配分区表。

每张表的表项为存储控制块MCB（Memory Control Block），包括已分配AMCB（Allocated）和未分配FMCB（Free）。

空闲分区控制块按某种次序构成FMCB链表结构。当分区被分配出去以后，前、后向指针无意义。

image-20240318213136617 image-20240318213150482

分配内存

有了对空闲空间的追踪，就可以对内存进行动态分配，让空余内存得到使用，同时不影响已分配内存区域的正常使用。

  1. 规定size是不再切割的剩余分区的大小。设请求的分区大小为u.size，空闲分区的大小为m.size。
  2. 若m.size-u.size ≤ size，将整个分区分配给请求者。
  3. 否则，从该分区中按请求的大小划分出一块内存空间分配出去，余下的部分仍留在空闲分区表/链中。

==基于顺序搜索的分配方法==

  1. 首次适应算法（First Fit）：每个空白区按其在存储空间中地址递增的顺序连在一起，在为作业分配存储区域时，从这个空白区域链的始端开始查找，选择第一个足以满足请求的空白块。

    1. 优点：

      1. 分配和释放的时间性能较好
      2. 较大的空闲分区保留在内存的高端

    2. 缺点：随着低端内存被不断分配，会产生很多小分区，开销会增大。

  2. 下次适应算法（Next Fit）：把存储空间中空白区构成一个循环链，每次为存储请求查找合适的分区时，总是从上次查找结束的地方开始，只要找到一个足够大的空白区，就将它划分后分配出去。

    1. 多余的地址会保留，下次从多余地址处开始搜索

  3. 最佳适应算法（Best Fit）：为一个作业选择分区时，总是寻找其大小最接近于作业所要求的存储区域。

  4. 最坏适应算法（Worst Fit）：为作业选择存储区域时，总是寻找最大的空白区。

算法特点：

  1. 首次适应：优先利用内存低地址部分的空闲分区。但由于低地址部分不断被划分，留下许多难以利用的很小的空闲分区（碎片或零头），而每次查找又都是从低地址部分开始，增加了查找可用空闲分区的开销。
  2. 下次适应：使存储空间的利用更加均衡，不致使小的空闲区集中在存储区的一端，但这会导致缺乏大的空闲分区。
  3. 最佳适应：若存在与作业大小一致的空闲分区,则它必然被选中，若不存在与作业大小一致的空闲分区，则只划分比作业稍大的空闲分区，从而保留了大的空闲分区。最佳适应算法往往使剩下的空闲区非常小，从而在存储器中留下许多难以利用的小空闲区（碎片）。
  4. 最坏适应：总是挑选满足作业要求的最大的分区分配给作业。这样使分给作业后剩下的空闲分区也较大，可装下其它作业。由于最大的空闲分区总是因首先分配而划分，当有大作业到来时，其存储空间的申请往往会得不到满足。

最佳适应算法是内存分配和释放平均时间之和最大的算法

基于索引搜索的分配方法

基于顺序搜索的动态分区分配算法一般只是适合于较小的系统，如果系统的分区很多，空闲分区表（链）可能很大，检索速度会比较慢。为了提高搜索空闲分区的速度，大中型系统采用了基于索引搜索的动态分区分配算法。

快速适应算法

快速适应算法，又称为分类搜索法，把空闲分区按容量大小进行分类，经常用到长度的空闲区设立单独的空闲区链表。系统为多个空闲链表设立一张管理索引表。

优点：

  1. 查找效率高，仅需要根据程序的长度，寻找到能容纳它的最小空闲区链表，取下第一块进行分配即可。
  2. 该算法在分配时，不会对任何分区产生分割，所以能保留大的分区，也不会产生内存碎片。

缺点：

  1. 在分区归还主存时算法复杂，系统开销较大。
  2. 在分配空闲分区时是以进程为单位，一个分区只属于一个进程，存在一定的浪费。空间换时间。

伙伴系统

固定分区方式不够灵活，当进程大小与空闲分区大小不匹配时，内存空间利用率很低。动态分区方式算法复杂，回收空闲分区时需要进行分区合并等，系统开销较大。

伙伴系统(buddy system)是介于固定分区与可变分区之间的动态分区技术。

伙伴：在分配存储块时将一个大的存储块分裂成两个大小相等的小块，这两个小块就称为“伙伴”。

image-20240318215024536

image-20240318215042332

系统中的碎片

内存中无法被利用的存储空间称为碎片。

内部碎片：

  • 指分配给作业的存储空间中未被利用的部分，如固定分区中存在的碎片。
  • 单一连续区存储管理、固定分区存储管理等都会出现内部碎片。
  • 内部碎片无法被整理，但作业完成后会得到释放。它们其实已经被分配出去了，只是没有被利用。

外部碎片：

  • 指系统中无法利用的小的空闲分区。如分区与分区之间存在的碎片。这些不连续的区间就是外部碎片。动态分区管理会产生外部碎片。
  • 外部碎片才是造成内存系统性能下降的主要原因。外部碎片可以被整理后清除。
  • 消除外部碎片的方法：紧凑技术。

紧凑技术

通过移动作业从把多个分散的小分区拼接成一个大分区的方法称为紧凑（拼接或紧缩）。

目标：消除外部碎片，使本来分散的多个小空闲分区连成一个大的空闲区。

紧凑时机：找不到足够大的空闲分区且总空闲分区容量可以满足作业要求时。

技术支撑：动态重定位：作业在内存中的位置发生了变化，这就必须对其地址加以修改或变换。

动态重定位的实现

多重分区分配

多重分区分配：一个作业往往由相对独立的程序段和数据段组成，将这些片断分别装入到存储空间中不同的区域内的分配方式。

image-20240318220631806

分区的存储保护

存储保护是为了防止一个作业有意或无意地破坏操作系统或其它作业。常用的存储保护方法有

  • 界限寄存器方法：

    • 上下界寄存器方法

    • 基址、限长寄存器（BR，LR）方法

      image-20240318220801094

  • 存储保护键方法：

    • 给每个存储块分配一个单独的保护键，它相当于一把锁。进入系统的每个作业也赋予一个保护键，它相当于一把钥匙。
    • 当作业运行时，检查钥匙和锁是否匹配，如果不匹配，则系统发出保护性中断信号，停止作业运行。

交换和覆盖

解决大作业在小内存中运行的问题：在运行过程中程序可能需要新的内存空间，原先分配的空间不够，如何继续分配：交换和覆盖

覆盖技术主要用在早期的OS 中，交换技术则用在现代OS 中。

覆盖

覆盖：把一个程序划分为一系列功能相对独立的程序段，让执行时不要求同时装入内存的程序段组成一组（称为覆盖段），共享主存的同一个区域，这种内存扩充技术就是覆盖。

程序段先保存在磁盘上，当有关程序段的前一部分执行结束，把后续程序段调入内存，覆盖前面的程序段（内存“扩大”了）。

一般要求作业各模块之间有明确的调用结构，==程序员要向系统指明覆盖结构==，然后由操作系统完成自动覆盖。

缺点：对用户不透明，增加了用户负担。

交换

交换：把暂时不用的某个（或某些）程序及其数据的部分或全部从主存移到辅存中去，以便腾出必要的存储空间；接着把指定程序或数据从辅存读到相应的主存中，并将控制转给它，让其在系统上运行。

优点：增加并发运行的程序数目，并且给用户提供适当的响应时间；编写程序时不影响程序结构

缺点：对换入和换出的控制增加处理机开销；程序整个地址空间都进行传送，没有考虑执行过程中地址访问的统计特性。

image-20240318221159076

交换VS覆盖

覆盖可减少一个程序运行所需的空间。交换可让整个程序暂存于外存中，让出内存空间。

覆盖是由程序员实现的，操作系统根据程序员提供的覆盖结构来完成程序段之间的覆盖。交换技术不要求程序员给出程序段之间的覆盖结构。

覆盖技术主要对同一个作业或程序进行。交换换主要在作业或程序间之间进行。

程序、进程和作业

程序

程序是一个静态对象，是存储在磁盘中的可执行文件。

程序本身没有任何意义，也是数据的一部分，只有被执行了程序才能产生意义：程序是进程的一个实体。

只要不主动删除，程序会一直留在磁盘中。

进程

进程是一个行为，是一个程序对某个数据集的执行过程，是分配资源的基本单位，是对执行过程的一种描述。进程包括程序和程序处理对象（数据集）才能产生意义。

  • 系统进程：完成操作系统功能的进程
  • 用户进程：完成用户功能的进程

进程是动态的作业过程，对进程的描述可以与计算机的执行过程等价，能够描述并发的状态。

进程具有一定的生命周期：执行完毕后即消失。

一个进程可以执行多个程序，一个程序也可以被多个进程执行，进程可以创建其他进程。

进程的执行需要连续的逻辑地址（实际物理地址经过映可以离散）。

==进程是资源分配的基本单元，线程是处理机调度的基本单元==

作业

作业是行为逻辑上的一个抽象，是计算机某次作业所需完成的特定对象。一个作业包含程序、数据和操作说明三个部分。

作业需要经过作业提交、作业收容、作业执行和作业完成4个阶段。一个作业至少由一个进程组成。

作业是用户向OS提交的任务实体，用户提交后，OS将其放入一个队列中等待执行。

页式内存管理

进程需要连续的（虚拟地址）空间，但是这会造成严重的内存浪费，于是试图使用虚拟地址，在物理地址和虚拟地址之间构建一个映射关系，把逻辑地址连续的程序分散存放在离散的内存区域中。

image-20240327102727612

基本概念

页：管理虚拟地址空间，把每个作业的地址空间分成一些大小相等的片，称之为页面（Page）或页，各页从0开始编号。

存储块：管理物理地址空间，把主存的存储空间也分成与页面相同大小的片，这些片称为存储块，或称为页框（Frame），同样从0开始编号。

页表：记录虚拟地址和物理地址的映射关系。分页系统中为每个进程配置一张页表，进程逻辑地址空间中的每一页，在页表中都对应有一个页表项

页表的作用就是在页和存储块之间构建一个映射

**每一个进程都有自己的页表，从0开始编址。**进程中的线程共享一个页表。

纯分页系统

纯分页系统：不支持页面调换的分页系统。每次需要将程序完整的内容调入内存，优点是构建了映射关系，可以实现程序的不连续存放，没有外碎片，内碎片不超过页的大小。

纯分页也称为基本分页管理，它不支持页面对换。当进程到来时一次性分配进程所需的所有物理内存。有多少页直接分配多少页框，并不是按需装入（相对应的按需装入称作请求分页）。

纯分页也是可以支持多级页表的，只不过此时的多级页表不能动态装入，所有级别的页表都同时装入内存

多级页表就是为了动态调入页表，但理论上还是可以实现多级页表的

页式内存管理需要的数据结构

进程页表：每个进程有一个页表，虚拟地址从0开始编制，页号使用地址直接表示，只记录物理页号即可。

物理页面表：整个系统有一个物理页面表，描述物理内存空间的分配使用状况。

  • 数据结构：位示图，空闲页面链表；

请求表：整个系统有一个请求表，描述系统内各个进程页表的位置和大小，用于地址转换，也可以结合到各进程的进程控制块PCB中；

页表存放在内存中，访问一个数据需要访问内存两次：页表+数据各一次

多级页表

多级页表的意义在于：在没有新增加页表的基础上（自映射保证），让页表不需要连续存放在内存中，利用动态调入（不是动态创建）实现对内存的高效利用。

指令中所给出的地址，除了地址偏移量以外，各部分均为各级页表的页表号或页号，而各级页表记录的全是物理页号，指向下级页表或真正的被访问页。

  1. 页目录+地址中一级页表对应的页号：得到二级页表的基地址
  2. 通过基地址处内容+地址中二级页表对应的页号：得到之后的地址
  3. 通过不断的求地址，直至地址被来到业内偏移量部分
  4. 同一了页表和普通内容的内存管理：页表不需要连续存放

快表TLB

快表就是Cache，记录常用的页表项。TLB采用全相联设计

TLB区分不同的进程，使用ASID来进行区分。

哈希页表

处理超过32位地址空间的常用方法是使用哈希页表（hashed page table），并以虚拟页码作为哈希值。

哈希页表的每一个哈希值对应一个条目。使用链表来处理哈希碰撞（哈希值相同）的问题，

每个元素有3个域：

  1. 虚拟页码
  2. 所映射的帧号
  3. 指向链表中下一个元素的指针。

该算法按照如下方式工作：

  1. 虚拟地址中的虚拟页号转换为哈希表号，用虚拟页号与链表中的每一个元素的第一个域相比较。
  2. 如果匹配，那么相应的帧号（第二个域）就用来形成物理地址；
  3. 如果不匹配，那么就对链表中的下一个节点进行比较，以寻找一个匹配的页号。

反置页表：用物理地址为基本

反置页表不是依据进程的逻辑页号来组织，而是依据该进程在内存中的物理页面号来组织。

反置页表按照物理页号排列，其表项的内容是逻辑页号P及隶属进程标志符pid。

反置页表的大小只与物理内存的大小相关，与逻辑空间大小和进程数无关。如: 64M主存,若页面大小为4K,则反向页表只需64KB。

==反置页表难以实现共享物理页面，每个物理帧只对应一个虚拟页条目。==

image-20240327105423076

利用反置页表进行地址变换：

  1. 用进程标志符和页号去检索反置页表。
  2. 如果检索完整个页表未找到与之匹配的页表项，表明此页此时尚未调入内存，对于具有请求调页功能的存储器系统产生请求调页中断，若无此功能则表示地址出错。
  3. 如果检索到与之匹配的表项，则表项的序号i便是该页的物理块号，将该块号与页内地址一起构成物理地址。

段式存储管理

页是存储信息的物理单位，段是存储信息的逻辑单位。页式存储方式难以实现内存的共享，段式存储是一种更合适的方式。

通常一个作业是由多个程序段和数据段组成的，用户一般按逻辑关系对作业分段，并能根据名字来访问程序段和数据段。段式存储可以更好地根据数据的含义（数据段、程序段）进行共享。

页式管理中页面地址是初始设定的，需要共享的内容可能占据多个页面，页可能与其他内容共享一个页面，在共享上不灵活。

段式管理中，可以以信息的逻辑单位进行保护。不必拘泥于设置的页的大小进行划分。

动态链接在程序运行时才把主程序和要用到的目标程序（程序段）链接起来。

基本概念

段

一个段可定义为一组逻辑信息，每个作业的地址空间是由一些分段构成的（由用户根据逻辑信息的相对完整来划分），每段都有自己的名字（通常是段号），且都是一段连续的地址空间，首地址为 0

段的地址是二维的

  • 页式：一个程序的各页是根据程序空间连续编址（逻辑地址）的，程序地址空间只有一维；
  • 段式：一个程序拆分成各段，独立编址（各段都从零开始编址），程序地址空间有两维。

按照页式获取地址，可以直接获取页号、业内偏移量，进而得到物理地址。

对于段式，必须给出段号，根据段表找出此段的起始地址，再根据段内地址进行定位。

本质是因为不同段的大小不同，没有一个统一的寻址方式，需要先按照段表找到段的起始地址，再根据段内地址寻找数据。不像页有相同的大小

不同的段

段表

段表记录了段和内存位置的对应关系。段表的基址和长度由段表寄存器给出。

  • 段表是一个表，每一个表项的大小相同。记录了对应段的地址。
  • 知道了段表的起始地址和段号后，可以按照相对段表起始地址的偏移量得到段表的表项，进而得到段的地址。
  • 表项：段号+段长SL+基址

段表的访存过程可类似于页表，区别就在于获取了段号和段内地址后，要按照段的方式进行访问。

  • 逻辑地址：段号+段内地址
  • 根据段号和段表的启示地址，得到对应的段表表项，段长和基址
  • 根据段长判断是否越界，未越界则按照基址+段内地址（偏移量）的方式进行访存

image-20240327111800320

信息共享

可重入代码（Reentrant Code) ：又称为纯代码（Pure Code) 是一种允许多个进程同时访问的代码。

为使各个进程所执行的代码完全相同绝对不允许可重入代码在执行中有任何改变。==可重入代码是一种不允许任何进程对其进行修改的代码 。==

优点：分段系统易于实现段的共享，对段的保护也十分简单。

缺点：

  • 处理机要为地址变换花费时间；要为表格提供附加的存储空间。
  • 为满足分段的动态增长和减少外零头，要采用拼接手段。
  • 在辅存中管理不定长度的分段困难较多。
  • 分段的最大尺寸受到主存可用空间的限制。

段页式存储

==用分段的方式来分配和管理虚拟存储器，用分页的方式来分配和管理实存储器。==

段页式存储管理是分段和分页原理的结合，即先将用户程序分成若干个段（段式），并为每一个段赋一个段名，再把每个段分成若干个页（页式） 。

  • 虚拟地址：段号S+段内页号P+业内地址W

image-20240327112250672

对于段页式系统，需要段表和页表，均存放在内存中，每个进程都有一张段表，每个段都有一张页表。

段表含段号、页表始址和页表长度。页表含页号和块号。

访问一次数据需要访问三次内存：段表+页表+数据。

image-20240327112633719

地址变换：

  1. 从PCB（每个进程有一张段表）中取出段表始址和段表长度，装入段表寄存器。
  2. 将地址的段号与段表长度进行比较，判断是否产生越界中断。
  3. 在段表中取出段表始址地址对应的页表始址和页表长度。
  4. 将该地址的页号与页表长度进行比较，判断是否产生越界中断。
  5. 利用页表始址与页号得到该地址对应的页表项在页表中的位置。
  6. 取出该页的物理块号，与页内地址拼接得到实际的物理地址。

虚拟内存管理

常规存储管理要求一个作业全部装入内存后方能运行，并且作业装入内存后一直驻留内存，直至结束。

可能出现的问题：

  • 有的作业很大，所需内存空间大于内存总容量，使作业无法运行。
  • 有大量作业要求运行，但内存容量不足以容纳下所有作业，只能让一部分先运行，其它在外存等待。

已有解决方法：

  • 增加内存容量：最简单、最有效的办法
  • 从逻辑上扩充内存容量：覆盖、对换

基本介绍

对于此问题，引入虚拟内存技术。虚拟内存是计算机系统存储管理的一种技术。它为每个进程提供了一个大的、一致的、连续可用的和私有的地址空间（一个连续完整的地址空间）。

借鉴覆盖技术：不必把程序的所有内容都放在内存中，因而能够运行比当前的空闲内存空间还要大的程序。

  • 与覆盖不同：由操作系统自动完成，对程序员是透明的。

借鉴交换技术：能够实现进程在内存与外存之间的交换，因而获得更多的空闲内存空间。

  • 与交换不同：只将进程的部分内容（更小的粒度，如分页）在内存和外存之间进行交换。

基本特征

离散性：物理内存分配的不连续，虚拟地址空间使用的不连续（数据段和栈段之间的空闲空间，共享段和动态链接库占用的空间）

多次性：作业被分成多次调入内存运行。正是由于多次性，虚拟存储器才具备了逻辑上扩大内存的功能。多次性是虚拟存储器最重要的特征，其它任何存储器不具备这个特征。

对换性：允许在作业运行过程中进行换进、换出。换进、换出可提高内存利用率。

虚拟性：虚拟存储器机制允许程序从逻辑的角度访问存储器（访问虚拟地址不知道真实的内存使用情况），而不考虑物理内存上可用的空间数量。

  • 范围大，但占用容量不超过物理内存和外存交换区容量之和。
  • 占用容量包括：进程地址空间中的各个段，操作系统代码。

虚拟性以多次性和对换性为基础，多次性和对换性必须以离散分配为基础。

和Cache的区别

侧重点不同：Cache 主要解决主存与 CPU 的速度差异问题；虚存主要解决存储容量问题，另外还包括存储管理、主存分配和存储保护等。

数据通路不同：CPU 与 Cache 和主存之间均有直接访问通路， Cache 不命中时可直接访问主存；而虚存所依赖的辅存与 CPU 之间不存在直接的数据通路，当主存不命中时只能通过调页解决， CPU 最终还是要访问主存。

请求分页（段）系统

在分页/段系统的基础上，增加了请求调页/段功能、页面/段置换功能所形成的页/段式虚拟存储器系统。

分页/段只是一种内存管理方式，没有页面调换前还不是虚拟内存管理系统。

允许只装入若干页/段的用户程序和数据，便可启动运行，以后在硬件支持下通过调页 段 功能和置换页/段功能，陆续将要运行的页面/段调入内存，同时把暂不运行的页面/段换到外存上，置换时以页面 段 为单位。

系统须设置相应的硬件支持和软件：

  • 硬件支持：请求分页/段的页/段表机制、缺页/段中断机构和地址变换机构。
  • 软件：请求调页/段功能和页/段置换功能的软件。

虚存机制要解决的关键问题：

  1. 地址映射问题：进程空间到虚拟存储的映射问题
  2. 调入问题：决定哪些程序和数据应被调入主存，以及调入机制。
  3. 替换问题：决定哪些程序和数据应被调出主存。
  4. 更新问题：确保主存与辅存的一致性。
  5. 其它问题：存储保护与程序重定位等问题

页表结构

image-20240329091737506
  • 驻留位：1表示该页位于内存当中，0表示该页当前还在外存当中。
  • 保护位：只读、可写、可执行。
  • 修改位：表明此页在内存中是否被修改过。
  • 访问（统计）位：用于页面置换算法。
image-20240330165933046

基本概念

建立了虚拟内存管理系统以后

进程空间

一个进程的逻辑空间的建立是通过链接器（Linker），将构成进程所需要的所有程序及运行所需环境，按照某种规则装配链接而形成的一种规范格式（布局）。

这种格式按字节从 0 开始编址所形成的空间也称为该进程的逻辑地址空间。其中OS所使用的空间称为系统空间，其它部分称为用户空间。系统空间对用户空间不可见。由于该逻辑空间并不是真实存在的，所以也称为进程的虚拟（地址）空间 。

image-20240329083614552

虚拟地址空间

进程的虚拟地址空间/虚拟内存空间即为进程在内存中存放的逻辑视图。因此，一个进程的虚拟地址空间的大小与该进程（占用的）的虚拟存储空间的大小相同 。且都从0 开始编址。

含有空白的虚拟地址空间称为稀疏地址空间。

交换分区/文件

在建立分页系统、交换系统后，可以将内存空间交换暂存到磁盘中，存到哪，即交换分区/文件。

是一段连续的磁盘空间（按页划分的），并且对用户不可见。它的功能就是在物理内存不够的情况下，操作系统先把内存中暂时不用的数据，存到硬盘的交换空间，腾出物理内存来让别的程序运行。

在Linux 系统中，交换分区为Swap；在 Windows 系统中则以文件的形式存在pagefile.sys。

交换器的大小：交换分区的大小应当与系统物理内存M的大小保持线性比例关系：

Swap={2∗M,M<2GM+2,else\text{Swap} = \begin{cases} 2*M ,\quad M<2G \\ M+2 ,\quad \text{else} \end{cases}

采用分段函数而不是连续函数：系统中的物理内存越大，对于内存的负荷可能也越大。

地址映射

进程空间到虚拟空间的映射：进程的虚存分配

分配是以段为单位的，需要进行页对齐

事实上，在每个进程创建加载时，内核只是建立好虚拟内存和磁盘文件之间的映射（叫做存储器映射），实际上并不立即就把虚拟内存对应位置的程序数据和代码（比如.text ，.data段）拷贝到物理内存中，等到运行到对应的程序时，才会通过缺页异常，来拷贝数据。

  • 用户可执行文件（如Hello World可执行文件）及共享库（如HelloWorld中调用的库文件中的printf函数）都是以文件的形式存储在磁盘中，初始时其在页表中的类型为file backed，地址为相应文件的位置。
  • 堆heap和栈 stack在磁盘上没有对应的文件 ，页表中的类型为anonymous，地址为空。
  • 未分配部分没有对应的页表项，只有在申请时（如使用malloc()申请内存或用mmap()将文件映射到用户空间）才建立相应的页表项。

页面的基本操作

页面调入

什么程序和数据调入主存：

  • OS的核心部分的程序和数据；
  • 正在运行的用户进程相关的程序及数据。

何时调入：

  • OS在系统启动时调入。
  • 用户程序的调入取决于调入策略。常用的调度策略有：
    • 预调页 ：事先调入页面的策略。
    • 按需调页 ：仅当需要时才调入页面的策略。

如何调入：缺页错误处理机制。

预调页

当进程开始时，所有页都在磁盘上，每个页都需要通过页错误来调入内存。预调页同时将所需要的所有页一起调入内存，从而阻止了大量的页错误。

实际应用中，可以为每个进程维护一个当前工作集合中的页的列表，如果进程在暂停之后需要重启时，根据这个列表使用预调页将所有工作集合中的页一次性调入内存。

预调页有时效果比较好，但成本不一定小于不使用预调页时发生页错误的成本，有很多预调页调入内存的页可能没有被使用。

按需调页

当且仅当需要某页时才将该页调入内存的技术称为按需调页（ demand paging ），被虚拟内存系统采用。

按需调页系统类似于使用交换的分页系统，进程驻留在二级存储器上（磁盘），进程执行时使用 懒惰交换（lazy swapper）换入内存。

按需调页需要使用备份存储，保存不在内存中的页。通常为快速磁盘，用于和内存交换页的部分空间称为交换空间。

缺页错误

当进程执行过程中需访问的页面不在物理内存中时，会引发发生缺页中断，进行所需页面换入，步骤如下：

  1. 现场保护：陷入内核态，保存必要的信息（OS 及用户进程状态相关的信息）。

  2. 页面定位：查找出来发生页面中断的虚拟页面（位于进程地址空间中）。

    • 产生缺页中断的虚拟页面的信息通常会保存在一个硬件寄存器中。
    • 如果没有的话，操作系统必须检索程序计数器，取出这条指令，通过软件分析找出发生页面中断的虚拟页面。

  3. 权限检查：检查虚拟地址的有效性及安全保护位。如果发生保护错误，则杀死该进程。

  4. 新页面调入：查找内存中一个空闲的页框。如果没有空闲页框，则需要通过页面置换算法将一个页面换出内存以腾出位置。

  5. 旧页面写回：如果决定替换的页框中的内容被修改了，则需要将修改的内容保存到磁盘上。

    此时需要将页框置为忙状态，以防页框被其它进程抢占掉

  6. 新页面调入：页框处理完毕后，操作系统将原先存储在磁盘上、对应的页面内容复制到该页框中。

  7. 更新页表：当磁盘中的页面内容全部装入页框后，向操作系统发送一个中断：操作系统更新内存中的页表项，将虚拟页面映射的页框号更新为写入的页框，并将页框标记为正常状态。

  8. 恢复现场：恢复缺页中断发生前的状态，将程序指针重新指向引起缺页中断的指令。

  9. 继续执行：程序重新执行引发缺页中断的指令，进行存储访问。

其中5、6会引发一个写磁盘调用，发起上下文切换：在等待磁盘写的过程会让其他进程先运行

页面替换

怎么选择对系统造成最小代价的页面进行替换？

  • 最优置换策略：最理想的情况，但是肯定无法实现，用作理论比较
  • 先进先出FIFO：总选择在主存中驻留最久的一页（哪怕被最频繁使用）
  • 最近最久不适用LRU：在最近一段时间中最久不使用的页面

最优置换OPT

理论上的最优情况，实际上不可能做到，用于理论比较。

从主存中移出永远不再需要的页面，如无这样的页面存在，则应选择未来最长时间不需要访问的页面。

它会将内存中的页P置换掉，页 P满足：从现在开始到未来某刻再次需要页 P，这段时间最长。也就是OPT算法会 置换掉未来最久不被使用的页 。

先进先出算法FIFO

总选择作业中在主存驻留时间最长的一页淘汰。

维护一个队列，记录页面的进入顺序，移出最早进入队列的页面。

  • 新访问的页面插入FIFO 队列尾部，页面在 FIFO 队列中顺序移动
  • 淘汰FIFO 队列头部的页面

==Belady现象==：在使用FIFO作为缺页置换算法时，分配的页面数增加，缺页率反而提高

改进的FIFO算法：Second Chance

每个页面会增加一个访问标志位，用于标识此数据放入缓存队列后是否被再次访问过。

A是 FIFO 队列中最旧的页面，且其放入队列后没有被再次访问，则 A被立刻淘汰；否则如果放入队列后被访问过，则将 A 移到 FIFO 队列头，并且将访问标志位清除。

将页面提前的机会只有在页面移动到队尾时，判断页面之前是否被访问过，判断页面是被淘汰还是移动到队首。并不是访问命中，就将页面提到队首。

LRU是只要命中就移到队首，SC是在淘汰时判断

如果所有的页面都被访问过，则经过一次循环后就会按照FIFO 的原则淘汰。

改进的FIFO算法：Clock

时钟算法和第二次机会算法的功能是完全一样的，只是在具体实现上有所不同，更易于硬件实现。

维护一个环形队列进行判断。

  • 如果没有缺页错误，将相应的页面访问位置1 ，指针不动
  • 如果指针指向页面的访问位位是0就淘汰，并且把新页面插入到这个位置，然后把表针前移一个位置；
  • 如果是1，则清除R位并把指针前移直到找到了一个R位为0的页面。
image-20240330190734999

最近最久不算法LRU

当需要置换一页面时，选择在最近一段时间内最久不用的页面予以淘汰。

  • 设置一个特殊的栈，保存当前使用的各个页面的页面号。
  • 每当进程访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶（与FIFO的区别）。栈底始终是最近最久未使用页面的页面号。
老化算法

用硬件支持LRU的花销太大，进行一定减法，使用移位寄存器来实现计数的功能。

  • 为每个页面设置一个移位寄存器，每个时钟周期向右移位一次。
  • 如果当前周期访问了该页面，则将寄存器最左位设置为1

image-20240330191314005

Page Cache与一致性

什么是Page Cache，怎么保持一致性。

基本概念

page 是内存管理分配的基本单位， Page Cache 由多个 page 构成。

page 在操作系统中通常为 4KB 大小（32bits/64bits），而 Page Cache 的大小则为 4KB 的整数倍。

Page Cache 的本质是由 Linux 内核管理的内存区域。通过 mmap 以及 buffered I/O 将文件读取到内存空间实际上都是读取到 Page Cache 中。

1
Page Cache = Buffers + Cached + SwapCached
img

Linux 系统上供用户可访问的内存分为两个类型，即：

  • File-backed pages：文件备份页。是存储在 Page Cache 中的 page，对应于磁盘上的若干数据块；对于这些页最大的问题是脏页回盘；
    • 有相应的备份存储在磁盘种，不需要担心完全丢失
  • Anonymous pages：匿名页不对应磁盘上的任何磁盘数据块，它们是进程的运行是内存空间（例如方法栈、局部变量表等属性）；
    • 这部分物理页面由于没有对应外部存储介质上的文件。
    • 在建立的时候只有虚按需分配拟地址，当它们真正被访问到的时候，内核才会为其分配物理页面。
    • Anonymous pages同page cache一样，也是可以被回收的，但由于没有对应的后备文件，因此在回收anonymous pages的时候，不能像可读写的page cache（比如data段）一样flush同步后discard，而是需要保存这些anonymous pages的内容，这样才能在以后再次访问这些页面的时候，获得它们被回收前所包含的数据。
    • 为此，磁盘上会开辟专门的swap space保存这些页面。swap space由若干的swap areas组成，swap area的最大数目由"MAX_SWAPFILES"确定。

主辅存一致性：更新问题

在虚存系统中，主存作为辅存（磁盘）的高速缓存，保存了磁盘信息的副本。因此，当一个页面被换出时，为了保持主辅存信息的一致性，必要时需要信息更新：

  • 如果页面有相应的磁盘备份，即file backed类型（用户可执行文件以及共享库）
    • 若未被修改，则直接丢弃，因为磁盘上保存有相同的副本。
    • 若已被修改，则直接写回原有位置。
  • 如果页面没有相应的磁盘备份，即anonymous类型（堆栈）
    • 若是第一次换出且未被修改，则写入 Swap 区，若非第一次则丢弃。
    • 若且已被修改，则写入Swap 区。

多进程下的虚拟内存管理

基本概念

基本定义：

  • 工作集：当前正在使用的页面的集合，可能位于磁盘中。
  • 驻留集：虚拟存储系统中每个进程驻留在内存的页面集合，或进程分到的物理页框集合。

工作集

引入工作集的目的：依据进程在过去的一段时间内访问的页面来调整驻留集大小。

工作集的定义：工作集是一个进程执行过程中所访问页面的集合，可用一个二元函数W(t,Δt)W(t,\Delta t)表示

  • tt是执行时刻
  • Δt\Delta t是窗口尺寸
  • 工作集是在[t−Δt,t][t-\Delta t,t]时间段内所访问的页面的集合
  • ∣W(t,Δt)∣|W(t,\Delta t)|指工作集大小，即页面数目；

工作集大小的变化：

  • 进程开始执行后，随着访问新页面逐步建立较稳定的工作集。
  • 当内存访问的局部性区域的位置大致稳定时，工作集大小也大致稳定；
  • 局部性区域的位置改变时，工作集快速扩张和收缩过渡到下一个稳定值。

驻留集

进程驻留集管理主要解决的问题是，系统应当为每个活跃进程分配多少个页框。

影响页框分配的主要因素：

  • 分配给每个活跃进程的页框数越少，同时驻留内存的活跃进程数就越多，进程调度程序能调度就绪进程的概率就越大。
  • 然而，这将导致进程发生缺页中断的概率较大；为进程分配过多的页框，并不能显著地降低其缺页中断率。

页面分配政策

  • ==固定分配政策==：为每个活跃进程分配固定数量的页框。即每个进程的驻留集尺寸在运行期间固定不变。
  • ==可变分配政策==：为每个活跃进程分配的页框数在其生命周期内是可变的。
    • 即系统首先给进程分配一定数量的页框，运行期间可以增减页框。系统可以根据进程的缺页率调整进程的驻留集。
    • 当进程的缺页率很高时，驻留集太小，需要增加页框；
    • 当缺页率一段时间内都保持很低时，可以在不会明显增加进程缺页率的前提下，回收其一部分页框，减小进程的驻留集。

可变分配策略比固定分配策略更灵活，既可以提高系统的吞吐量，又能保证内存的有效利用。

可变分配要求统计进程的缺页率，增加系统额外开销。而准确判断进程缺页率的高低，确定缺页率的阈值是非常困难的。可变分配策略不仅需要操作系统软件专门的支持，而且，还需要处理机平台提供的硬件支持。

内存块初始分配方法

  1. 等分法：为每个进程分配存储块的最简单的办法是平分，即若有m块、n个进程，则每个进程分[m/n][m/n]块。
  2. 比例法：分给进程的块数进程地址空间大小 /全部进程的总地址空间 * 可用块总数
  3. 优先权法：为加速高优先级进程的执行，可以给高优先级进程分较多内存。如使用比例分配法时，分给进程的块数不仅取决于程序的相对大小而且也取决于优先级的高低。

页面置换策略

当发生缺页中断且无足够的内存空间时，需要置换已有的某些（个）页面。应该解决的基本问题：

  1. 当系统欲把一个页面装入内存时，应当在什么范围内判断已经没有空闲页框供分配？
  2. 当指定的范围内没有空闲页框时，应当从哪里选择哪个页面移出内存？

局部置换：系统在进程自身的驻留集中判断当前是否存在空闲页框，并在其中进行置换。

全局置换策略：在整个内存空间内判断有无空闲页框，并允许从其它进程的驻留集中选择一个页面换出内存。

分配模式与置换模式的搭配

image-20240330194804932

全局置换算法：存在的一个问题是，程序无法控制自己的缺页率。一个进程在内存中的一组页面不仅取决于该进程的页面走向，而且也取决于其他进程的页面走向。因此，相同程序由于外界环境不同会造成执行上的很大差别。

使用局部置换算法就不会出现这种情况，一个进程在内存中的页面仅受本进程页面走向的影响。

  • 仅在自身的驻留集中选择页面进行替换

可变分配策略+局部置换策略：可增加或减少分配给每个活跃进程的页框数；当进程的页框全部用完，而需要装入一个新的页面时，系统将在该进程的当前驻留集中选择一个页面换出内存。

页面清除策略

页面清除策略需要决定系统何时把被置换页面写回外存。

若被选中的置换页面被修改过，则需要将该页面内容写回外存，然后装入新页内容。

一种有效的页面清除策略是结合页缓冲（Page Buffering ）技术。当发生缺页中断时，不必首先写出置换页，而是将被选中的置换页暂时保留在内存的一个缓冲区，在以后某个合适的时候将这些被置换页批量写出到外存。减少磁盘 I/O 的次数，提高处理机的效率。

负载与负载控制

==抖动问题：随着驻留内存的进程数目增加，或者说进程并发水平的上升，处理器利用率先是上升，然后下降。==这里处理器利用率下降的原因通常称为虚拟存储器发生“抖动”。

也就是：==每个进程的驻留集不断减小，当驻留集小于工作集后，缺页率急剧上升，频繁调页使得调页开销增大。== OS 要选择一个适当的进程数目，以在并发水平和缺页率之间达到一个平衡 。

抖动消除与预防：

  • 局部置换策略：如果一个进程出现抖动，它不能从另外的进程那里夺取内存块，从而不会引发其他进程出现抖动，使抖动局限于一个小的范围内。 然而这种方法并未消除抖动的发生。（微观层面）
  • 引入工作集算法（微观）
  • 预留部分页面（微观或宏观）
  • 挂起若干进程：当出现CPU 利用率、而磁盘 I/O 非常频繁的情况时，就可能因为多道程序度太高而造成抖动。为此，可挂起一个或几个进程，以便 腾出内存空间供抖动进程使用，从而消除抖动现象 。（宏观）

负载控制

多道程序系统允许多个进程同时驻留内存，以提高系统吞吐量和资源利用率。然而，如果同时驻留的进程数量太多，每个进程都竞争各自需要的资源，反而会降低系统效率。

  • 如果内存中进程太多，将导致每个进程的驻留集太小，发生缺页中断的概率很大，系统发生抖动的可能性就会很大。
  • 如果内存中保持太少的活动进程，那么所有活动进程同时处于阻塞状态的可能性就会很大，从而降低处理机的利用率。

负载控制主要解决系统应当保持多少个活动进程驻留在内存的问题，即控制多道程序系统的度。

  • 当内存中的活动进程数太少时，负载控制将增加新进程或激活一些挂起进程进入内存；
  • 当内存中的进程数太多时，负载控制将暂时挂起一些进程，减少内存中的活动进程数。

系统负载的判断：

  • L=S原则：通过调整多道程序的度，使得发生两次缺页之间的平均时间L等于处理依次缺页所需的平均时间S。这样处理机的利用率可以达到最大。
  • 50%原则：分页单元的利用率保持在50%左右，处理机的利用率达到最大。此时系统使用基于CLOCK置换算法的全局置换策略。

可挂起的进程

  • 优先级最低的进程；
  • 缺页进程：因为发生缺页中断的进程处于阻塞状态，暂时不需要竞争处理机的使用权。而且，挂起一个缺页进程时，挂起和激活操作需要的数据交换将消除页替换的开销；
  • 最后一个被激活的进程：因为为此类进程装入的页面较少，将其挂起的开销较小；
  • 驻留集最小的进程：将该类进程挂起以后，激活所需的开销较小；
  • 最大的进程：挂起最大的进程将获得最多的内存空间，可以满足内存中的进程申请空闲页框的需要，使它们能尽快执行完成。

写时复制技术

对于复制的内容，如果不进行修改，则共享一个指针（一个内容）。只有当一个进程想要修改时，才进行真正的复制。

资源的复制只有在需要写入的时候才进行。

  • 两个进程共享同一块物理内存，每个页面都被标志成了写时复制 。共享的物理内存中每个页面都是只读的。
  • 如果某个进程想改变某个页面时，就会与只读标记冲突，而系统在检测出页面是写时复制的，则会在内存中复制一个页面，然后进行写操作。
  • 新复制的页面对执行写操作的进程是私有的，对其他共享写时复制页面的进程是不可见的。

存储保护

  • 界限保护（上下界界限地址寄存器）：所有访问地址必须在上下界之间；

  • 用户态与内核态

  • 存取控制检查

  • 环保护：处理器状态分为多个环( ring)，分别具有不同的存储访问特权级别 ( privilege)，通常是==级别高的在内环，编号小（如 0 环）级别最高==；可访问同环或更低级别环的数据；可调用同环或更高级别环的服务。

    image-20240330201440073

页表自映射

自映射：页表占据的存储空间多后，也需要使用页表来进行管理。

页表建立了虚拟空间和物理空间的地址映射关系：

  • 对于32位系统，采用12位页内偏移量，则每个页大小为4KB，共1M页

  • 假设每个页表项大小为4B，则需要4MB的空间存放页表项，需要1K个页面

  • 记页表项为PDE

    image-20240330204705918

页表自映射：页表也需要有也来存储，一定有页的地址指向自身。使其为页目录基地址

  • 页表基址PTbase\text{PT}_{base}​，需要4M对齐：业内偏移量12+1K个页表项

    • 页表地址可以是OS改变的，唯一限制就是4M对齐

    PTbase=(PTbase>>22)<<22\text{PT}_{base} = (\text{PT}_{base}>>22)<<22

  • 页目录基地址PDbase\text{PD}_{base}​

    • >>10 是为了获得页表在整个内存中的相对位置：内存共4GB，页表占据4MB，是1/1K，获取>>10是为了获取页表在内存中的相对位置，以形成页目录的自映射

PDbase=PTbase∣(PTbase>>10) \text{PD}_{base}=\text{PT}_{base} | (\text{PT}_{base}>>10)

  • 自映射目录表项PDEself_mapping\text{PDE}_{self\_mapping}​

    • 和页表的自映射一样，页表共4MB，页目录共4KB，还是1/1K，本质应该是PD>>10，化简结果用PT表示

    PDEself_mapping=PDbase∣(PDbase>>10)=PTbase∣(PTbase>>10)∣(PTbase>>20)\text{PDE}_{self\_mapping} = \text{PD}_{base} | (\text{PD}_{base}>>10) \\ = \text{PT}_{base}|(\text{PT}_{base}>>10)|(\text{PT}_{base}>>20)

只要给定4M 对齐的页表基址（虚拟地址），就可以得到所有页表项对应的地址，也就包括页目录表基址和自映射页目录项在页目录表中的位置。因此页目录表基址和自映射页目录项在虚空间中是计算出来的。

页表主要供OS 使用的，因此页表和页目录表通常放置在 OS 空间中（如 Win 的高 2G 空间）；

“页目录自映射”的含义是页目录包含在页表当中，是采用的映射（或组织）方法的一个特征， 是虚拟地址空间内的映射，与虚拟地址到物理地址的映射无关。

支持“页目录自映射”可节省4K （虚拟地址）空间