操作系统第三章-内存管理

操作系统第三章 内存管理

计算机学科基础：操作系统第三章内存管理的学习笔记

一.内存管理的概念（✪）

1.内存管理的基本原理与要求

• 存储管理的目的：方便用户和提高内存利用率
  对内存的访问以字或字节为单位

• 逻辑地址与物理地址

  • 逻辑地址
    • 编译后，每个目标模块都从0号单元开始编址，这称为该目标模块的相对地址（或逻辑地址）。
    • 当链接程序将各个模块链接成一个完整的可执行目标程序时，
      链接程序顺序依次按各个模块的相对地址构成统一的从0号单元开始编址的逻辑地址空间（或虚拟地址空间）
    • 进程在运行时，看到和使用的地址都是逻辑地址。用户程序和程序员只需知道逻辑地址，
      而内存管理的具体机制则是完全透明的。
    • 不同进程可以有相同的逻辑地址，因为这些相同的逻辑地址可以映射到主存的不同位置。
  • 物理地址
    • 物理地址空间是指内存中物理单元的集合，它是地址转换的最终地址，进程在运行时执行指令和访问数据，最后都要通过物理地址从主存中存取。
    • 当装入程序将可执行代码装入内存时，必须通过地址转换将逻辑地址转换成物理地址，这个过程称为地址重定位。
    • 操作系统通过内存管理部件(MMU)将进程使用的逻辑地址转换为物理地址。进程使用虚拟内存空间中的地址，操作系统在相关硬件的协助下，将它“转换”成真正的物理地址。
    • 逻辑地址通过页表映射到物理内存，页表由操作系统维护并被处理器引用。

• 程序的链接和装入

  • 创建进程首先要将程序和数据装入内存。将用户源程序变为可在内存中执行的程序，有以下三个步骤：
  • 编译：由源代码文件生成目标模块(高级语言“翻译”为机器语言)
  • 链接：由链接程序将编译后形成的一组目标模块及它们所需的库函数链接在一起，形成一个完整的装入模块，形成逻辑地址
    • 静态链接：在程序运行之前，先将各目标模块及它们所需的库函数连接成一个完整的可执行文件（装入模块），
      之后不再拆开。
    • 装入时动态链接：将各目标模块装入内存时，边装入边链接的链接方式
      其优点是便于修改和更新，便于实现对目标模块的共享
    • 运行时动态链接：对某些目标模块的链接，是在程序执行中需要该目标模块时才进行的。凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上。
      其优点是能加快程序的装入过程，还可节省大量的内存空间
  • 装入：将装入模块装入内存，装入后形成物理地址（实现将逻辑地址转换为物理地址）
    • 绝对装入
      • 在编译时，如果知道程序将放到内存中的哪个位置，编译程序将产生绝对地址的目标代码。
        此时编译、链接后得到的装入模块的指令直接就使用了绝对地址，装入程序按照装入模块中的地址，将程序和数据装入内存。
      • 绝对装入只适用于单道程序环境。
      • 程序中使用的绝对地址，可在编译或汇编时给出，也可由程序员直接赋予。
        通常情况下都是编译或汇编时再转换为绝对地址
    • 静态重定位（可重定位装入，装入时转换为物理地址）
      • 编译、链接后的装入模块的地址都是从0开始的，指令中使用的地址、数据存放的地址都是相对于起始地址而言的逻辑地址。
      • 可根据内存的当前情况，将装入模块装入到内存的适当位置。装入时对地址进行“重定位”，将逻辑地址变换为物理地址（地址变换是在装入时一次完成的）
      • 适用于早期多道批处理系统
      • 静态重定位的特点
        • 在一个作业装入内存时，必须分配其要求的全部内存空间，如果没有足够的内存，就不能装入该作业。
        • 作业一旦进入内存后，在运行期间就不能再移动，也不能再申请内存空间。
    • 动态重定位（动态运行时装入，执行时转换为物理地址）
      • 程序在内存中若发生移动，则需要采用动态的装入方式。装入程序把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。
      • 装入内存后的所有地址均为相对地址。这种方式需要一个重定位寄存器的支持，在运行时将逻辑地址转换为物理地址
        • 重定位寄存器：存放装入模块存放的起始位置
      • 动态重定位的优点：
        • 可以将程序分配到不连续的存储区；
        • 在程序运行之前可以只装入部分代码即可投入运行，然后在程序运行期间，根据需要动态申请分配内存
          可以向用户提供一个比存储空间大得多的地址空间
        • 便于程序段的共享。
  • 图片
    • 
• 进程的内存映像
  • 组成
    • 只读代码段：即程序的二进制代码或由const关键字修饰的常变量，代码段是只读的，可以被多个进程共享。
    • 读/写数据段：即程序运行时加工处理的对象，包括定义在函数外的全局变量、由static关键字修饰的静态变量
    • 堆：用来存放动态分配的变量。通过调用malloc函数动态地向高地址分配空间
    • 共享库的存储映射区：是被调用的库函数
    • 栈：用来实现函数调用。从用户空间的最大地址往低地址方向增长，在函数大括号内定义的局部变量、函数调用时传入的参数
    • 进程控制块(PCB):存放在系统区。操作系统通过PCB来控制和管理进程，在操作系统内核区。
  • 图片
    • 

• 内存管理的主要功能

  • 内存空间的分配与回收

    • 由操作系统完成主存储器空间的分配和管理，使程序员摆脱存储分配的麻烦，提高编程效率
    • 包括连续分配的管理方式和非连续分配的管理方式
      • 连续分配管理方式包括：单一连续分配、固定分区分配、动态分区分配（可变分区分配）
      • 非连续分配管理方式包括：基本分页存储管理、基本分段存储管理、段页式存储管理

  • 地址转换

    • 在多道程序环境下，程序中的逻辑地址与内存中的物理地址不可能一致，因此存储管理必须提供地址变换功能，
      把逻辑地址转换成相应的物理地址（地址重定位）

  • 内存空间的扩充

    • 利用虚拟存储技术或自动覆盖技术、交换技术，从逻辑上扩充内存
    • 覆盖技术适用于单一连续分配和固定分区分配

  • 内存共享

    • 指允许多个进程访问内存的同一部分。例如，多个合作进程可能需要访问同一块数据，因此必须支持对内存共享区域进行受控访问。

  • 内存保护（界地址保护）

    • 保证各道作业在各自的存储空间内运行，互不干扰，不会越界访问，需要操作系统与硬件合作
    • 方法一：在CPU中设置一对上、下限寄存器，存放进程的上、下限地址。进程的指令要访问某个地址时，
      CPU检查是否越界。
    • 方法二：采用重定位寄存器（又称基址寄存器）和界地址寄存器（又称限长寄存器）进行越界检查。
      重定位寄存器中存放的是进程的起始物理地址。界地址寄存器中存放的是进程的最大逻辑地址。

2.连续分配管理方式

• 连续分配：指为用户进程分配的必须是一个连续的内存空间。
• 内部碎片与外部碎片
  • 内部碎片，程序小于固定分区的大小时，有些部分没有用上，会存在空间浪费
  • 外部碎片，是指内存中的某些空闲分区由于太小而难以利用，内存的利用率下降
  • 如果内存中空闲空间的总和本来可以满足某进程的要求，但由于进程需要的是一整块连续的内存空间，
    因此这些“碎片”不能满足进程的需求。可以通过紧凑(拼凑)技术来解决外部碎片。
• 三种连续分配方式
  • 单一连续分配
    • 只支持单道程序，内存被分为系统区和用户区。系统区通常位于内存的低地址部分，用于存放操作系统相关数据；
      用户区用于存放用户进程相关数据。内存中只能有一道用户程序，用户程序独占整个用户区空间。
    • 优点：实现简单；无外部碎片；可以采用覆盖技术扩充内存；无须采取内存保护
    • 缺点：只能用于单用户、单任务的操作系统中；有内部碎片；存储器利用率极低。
  • 固定分区分配
    • 最简单的一种多道程序存储管理方式，它将用户内存空间划分为若干固定大小的区域，每个分区只装入一道作业。
      当有空闲分区时，便可再从外存的后备作业队列中选择适当大小的作业装入该分区，如此循环。
    • 固定分区划分分区的两种方法
      • 分区大小相等：程序太小会造成浪费，程序太大又无法装入，缺乏灵活性。
        适合用于用一台计算机控制多个相同对象的场合
      • 分区大小不等：划分为多个较小的分区、适量的中等分区和少量大分区。
    • 分区使用表
      • 概述（一个数据结构，实现各个分区的分配与回收）
        • 每个表项对应一个分区，通常按分区大小排列。每个表项包括对应分区的大小、起始地址、状态（是否已分配）
        • 分配内存时，便检索该表，以找到一个能满足要求且尚未分配的分区分配给装入程序，并将对应表项的状态置为“已分配”，若找不到这样的分区，则拒绝分配。
        • 回收内存时，只需将对应表项的状态置为“未分配”即可。
      • 图片
        • 
    • 优点：实现简单，无外部碎片。
    • 缺点：当用户程序太大时，可能所有的分区都不能满足需求，此时不得不采用覆盖技术来解决，但这又会降低性能 ；
      会产生内部碎片，内存利用率低
  • 动态分区分配（可变分区分配）
    • 支持多道程序，不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。因此系统分区的大小和数目是可变的。
    • 记录空闲内存分区的两种数据结构
      • 空闲分区表：每个空闲分区对应一个表项。表项中包含分区号分区大小、分区起始地址等信息
      • 空闲分区链：每个分区的起始部分和末尾部分分别设置前向指针和后向指针。起始部分处还可记录分区大小等信息
      • 分配内存和回收内存时，修改相应的表项，回收时出现相邻的空闲分区要合并（采用拼接技术）
      • 图片
        • 
    • 特点：会产生外部碎片（可用紧凑来解决），不会产生内部碎片
    • 动态分区分配算法：在动态分区分配中，当内存中很多个空闲分区都能满足需求时，应该选择哪个分区进行分配
      • 首次适应算法 (First Fit)
        • 算法思想：每次都从低地址开始查找，找到第一个能满足大小的空闲分区。
        • 如何实现：空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链（或空闲分区表），
          找到大小能满足要求的第一个空闲分区。、
        • 优点：算法开销小，性能最优（回收分区后不需要重新进行空闲分区的排序）
        • 缺点：会使内存的低地址部分产生很多小的空闲分区，每次查找时都要经过这些分区，增加了开销
      • 最佳适应算法 (Best Fit)
        • 算法思想：保证当“大进程”到来时能有连续的大片空间，可以尽可能多地留下大片的空闲区，即优先使用更小的空闲区。
        • 如何实现：空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链（或空闲分区表），
          找到大小能满足要求的第一个空闲分区；
        • 缺点
          • 每次都选最小的分区进行分配，会留下越来越多的、很小的、难以利用的内存块，产生很多的外部碎片
          • 在发生次序变动时需要对链表进行重新排列，开销大
      • 最坏/大适应算法 (Worst Fit)
        • 算法思想：为了解决最佳适应算法的问题一一即留下太多难以利用的小碎片，可以在每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，更方便使用。
        • 如何实现：空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链（或空闲分区表），
          找到大小能满足要求的第一个空闲分区；在发生次序变动时需要对链表进行重新排列
        • 缺点：
          • 每次都选最大的分区进行分配，虽然可以让分配后留下的空闲区更大，更可用，但是这种方式会导致较大的连续空闲区被迅速用完。如果之后有“大进程”到达，就没有内存分区可用了。
          • 在发生次序变动时需要对链表进行重新排列，开销大
      • 邻近适应算法 (Next Fit)
        • 算法思想：首次适应算法每次都从链头开始查找的。这可能会导致低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，因此也增加了查找的开销。
          如果每次都从上次查找结束的位置开始检索，就能解决上述问题。
        • 如何实现：空闲分区以地址递增的顺序排列（可排成一个循环链表）。每次分配内存时从上次查找结束的位置开始查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。
        • 优点：开销小（回收分区后不需要重新进行空闲分区的排序）
        • 缺点：邻近适应算法的规则可能会导致无论低地址、高地址部分的空闲分区都有相同的概率被使用，
          也就导致了高地址部分的大分区更可能被使用，划分为小分区，最后导致无大分区可用（最大适应算法的缺点）
      • 四种算法的区别
        • 
      • 例题
        • 
        • 

4.基本分页存储管理（♚）

• 分页存储的基本概念
  • 内存空间与进程空间的划分
    • 内存空间中的概念
      • 页框、页帧：将内存划分为一个个大小相等的分区，即内存中的块（也称为内存块、物理块、物理页面）
      • 页框号：每个页框的编号，从0开始（又称为页帧号、内存块号、物理块号、物理页号）
    • 进程中的概念
      • 页、页面：将进程的逻辑地址空间也分为与页框大小相等的一个个部分
      • 页号、页面号：每个页面的编号，从0开始
      • 页面大小由多种因素决定，一旦决定就是等长的
        • 页面小，用于管理页面的页表就大，但是页内碎片小
        • 页面大，用于管理页面的页表就小，但是页内碎片大
    • 操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分别放入一个页框中。
      进程的页面与内存的页框存在着一一对应的关系，但各个页面不必连续存放，可以放在不相邻的各个页框中
    • 注：分页管理不会产生外部碎片；进程只会在为最后一个页面申请一个主存块空间时，才可能会产生内部碎片，
      但这种碎片相对于进程来说也是很小的，每个进程平均只产生半个块大小的内部碎片（也称页内碎片）
  • 页表的概念（页号与物理块号的映射）
    • 为了便于在内存中找到进程的每个页面所对应的物理块，系统为每个进程建立一张页表，
      它记录页面在内存中对应的物理块号，页表一般存放在内存的PCB中。
    • 一个进程对应一张页表，页表由页表项组成，每个页表项由页号和块号（页框号）组成
      页号由0到1，块号是与之对应的在内存中的物理地址。
    • 每个页表项的长度是相同的
    • 图片
      • 
  • 确定页表的相关数据
    • 确定页表项的大小（页面长度）
      • 页表项连续存放，因此页号可以是隐含的，不占存储空间（类比数组）
      • 可通过计算机中内存块的数量$\rightarrow$ 页表项中的块号至少占多少个字节
      • 假设某系统物理内存大小为4GB，页面大小为4KB，则每个页表项至少应该为多少字节？
        • 内存块大小=页面大小=4KB=$2^{12}$B
        • 4GB的内存总共会被分为$2^{32}/2^{12}=2^{20}$个内存块
        • 内存块号的范围应该是${0 \sim 2^{20}-1}$
        • 内存块号至少要用 20 bit 来表示
        • 即至少要用3B来表示块号${(3 * 8=24 \mathrm{bit})}$
          • 
          • 页表记录的只是内存块号，而不是内存块的起始地址
          • $j$号内存块的起始地址=$j*内存块大小$
        • 由于页号是隐含的，因此每个页表项占3B，存储页号为n的整个页表至少需要$3*(n+1)B$
    • 找到页号所对应的块号的存储地址
      • 假设页表中的各页表项从内存地址为X的地方开始连续存放，此时ⅰ号页表项的存放地址=$X+内存块大小*i$
  • 实现逻辑地址到物理地址的转换
    • 1.计算出逻辑地址对应的[页号，页内偏移量]
      • 页号=逻辑地址/页面长度（取除法的整数部分）
      • 页内偏移量=逻辑地址%页面长度（取除法的余数部分）
    • 2.找到对应页面在内存中的起始地址（查页表）
    • 3.物理地址=页面起始始址+页内偏移量
    • 假设在某计算机系统中，页面大小是50B。某进程逻辑地址空间大小为200B，则逻辑地址110对应的页号、页内偏移量是多少？
      • 页号=110/50=2
      • 页内偏移量=110%50=10
      • 通过页号查询页表，可知页面在内存中物理块号，从而知道页面的起始地址
      • 页面在内存中的起始地址+页内偏移量=实际的物理地址
  • 逻辑地址结构（页号P，页内偏移量W）
    • 如果页面大小刚好是2的整数幂，则计算机硬件可快速拆分逻辑地址，
    • 如果每个页面的大小为$2^{k}$B，用二进制数表示逻辑地址，则末尾K位即为页内偏移量，其余部分为页号
    • 地址长度为 32 位时，其中${0 \sim 11}$位为页内地址，即每页大小为${4 \mathrm{KB} 、 12 \sim 31}$位为页号, 即最多允许${2^{20}}$页
    • 计算机直接将页号所对应的块的起始地址与页内偏移量的二进制拼接起来即可得到物理地址
      • 注：这里的块号与页号的关系需要查询相应的页表
    • 页面大小<->页内偏移量位数->逻辑地址结构
      • 如果有K位表示“页内偏移量”，则说明该系统中一个页面的大小是$2^k$个内存单元
      • 如果有M位表示“页号”，则说明在该系统中，一个进程最多允许有$2^M$个页面
    • 特点
      • 在分页存储管理（页式管理）的系统中，只要确定了每个页面的大小，逻辑地址结构就确定了。因此，页式管理中地址是一维的。
      • 即只要给出一个逻辑地址，系统就可以自动地算出页号、页内偏移量两个部分，并不需要显式地告诉系统这个逻辑地址中，页内偏移量占多少位。
• 基本地址变换机构
  • 基本地址变换机构的构成
    • 通常会在系统中设置一个页表寄存器(PTR)，存放页表在内存中的起始地址F和页表长度M
    • 进程未执行时，页表的始址和页表长度放在进程控制块(PCB)中
    • 当进程被调度时，操作系统内核会把它们放到页表寄存器中
  • 逻辑地址到物理地址的转换过程（由硬件自动完成）
    • 将页表始址和页表长度装入页表寄存器中。设页面大小为L，逻辑地址A到物理地址E的变换过程如下
      • ①计算页号P (P=A/L) 和页内偏移量W (W=A%L).
      • ②比较页号P和页表长度M，若P≥M，则产生越界中断，否则继续执行。
      • ③页表中页号P对应的页表项地址=页表始址F+页号P×页表项长度，取出该页表项内容b，即为物理块号。
        注意区分页表长度和页表项长度。页表长度是指一共有多少页，页表项长度是指页地址占多大的存储空间。
      • ④计算E=b×L+W，用得到的物理地址E去访问内存。
    • 实例
      • 若页面大小L为1KB，页号2对应的物理块为b=8，计算逻辑地址A=2500的物理地址E的过程如下
        • P=2500/1K=2，W=2500%1K=452，查找得到页号2对应的物理块的块号为8，E=8×1024+452=8644。
    • 图片
      • 重定位寄存器：整个系统中设置一个即可
      • 
  • 关于页表项的大小问题
    • 理论上，页表项长度为3B即可表示内存块号的范围，但是，为了方便页表的查询，
      常常会让一个页表项占更多的字节，使得每个页面恰好可以装得下整数个页表项，因此选择长度为4B
  • 如何加快地址转换
    • 设置快表（TLB）并增大快表容量
    • 让页表常驻内存

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

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

  • 快表的工作过程

    • 过程

      • ①CPU给出逻辑地址，由某个硬件算得页号、页内偏移量，将页号与快表中的所有页号进行比较。
      • ②如果找到匹配的页号，说明要访问的页表项在快表中有副本，则直接从中取出该页对应的内存块号，
        再将内存块号与页内偏移量拼接形成物理地址，最后访问该物理地址对应的内存单元。
        因此，若快表命中，则访问某个逻辑地址仅需一次访存即可。
      • ③如果没有找到匹配的页号，则需要访问内存中的页表，找到对应页表项，得到页面存放的内存块号，
        并且将页表项复制到快表中，再将内存块号与页内偏移量拼接形成物理地址，最后访问该物理地址对应的内存单元。
        因此，若快表未命中，则访问某个逻辑地址需要两次访存
      • 在找到页表项后，应同时将其存入快表，以便后面可能的再次访问。
        但若快表已满，则必须按照一定的算法对旧的页表项进行替换

    • 图片

      • 

    • 例子

      • 

  • 局部性原理

    • 由于查询快表的速度比查询页表的速度快很多，因此只要快表命中，就可以节省很多时间。
      因为局部性原理，一般来说快表的命中率可以达到90%以上。
    • 图片
      • 

• 两级页表

  • 单机页表的问题
    • 问题一：页表必须连续存放，因此当页表很大时，需要占用很多个连续的页框。
      • 多级页表可以减少页表所占的连续内存空间
    • 问题二：没有必要让整个页表常驻内存，因为进程在一段时间内可能只需要访问某几个特定的页面。
      • 可以由虚拟存储器解决：作业不必全部装入内存且不用一直驻留在内存
  • 两级页表的原理、地址结构
    • 把页表再分页并离散存储，然后再建立一张页表记录页表各个部分的存放位置，称为页目录表，或称外层页表，或称顶层页表
    • 再把原来的逻辑地址结构的页号划分为为10位的一级页号与10位的二级页号
    • 图片
      • 
    • 两级页表的访问过程
      • 按照地址结构将逻辑地址拆分成三部分
      • 从PCB中读出页目录表始址，根据一级页号查页目录表，找到下一级页表在内存中的存放位置
      • 根据二级页号查表，找到最终想访问的内存块号
      • 结合页内偏移量得到物理地址
      • 图片
        • 
  • 多级页表
    • 多级页表中，各级页表的大小不能超过一个页面。若两级页表不够，可以分更多级
    • 多级页表的访存次数（假设没有快表机构）N级页表访问一个逻辑地址需要N+1次访存
    • 图片
      • 
    • 例题
      • 
      • 

5.基本分段存储管理（♚）

• 分段存储管理的概述

  • 引入分段存储管理可以满足：方便编程、分段共享、分段保护、动态链接与动态增长
  • 进程的地址空间：按照程序自身的逻辑关系划分为若干个段，每个段都有一个段名，每段从0开始编址
    一个程序如何分段在用户编程时决定
  • 内存分配规则：以段为单位进行分配，每个段在内存中占据连续空间，但各段之间可以不相邻
    分段不会产生内部碎片，会产生外部碎片
  • 分段的逻辑地址结构
    • 由段号（段名）和段内地址（段内偏移量）所组成。
    • 段号的位数决定了每个进程最多可以分几个段
    • 段内地址位数决定了每个段的最大长度是多少
  • 分段存储管理将程序按照逻辑段进行划分，有利于程序的动态链接
  • 图片
    • 

• 段表

  • 程序分多个段，各段离散地装入内存，为了保证程序能正常运行，就必须能从物理内存中找到各个逻辑段的存放位置。
    需为每个进程建立一张段映射表，简称“段表”。
  • 每个段对应一个段表项，其中记录了该段在内存中的起始位置（又称“基址”）和段的长度。
  • 各个段表项的长度是相同的。由于段表项长度相同，因此段号可以是隐含的，不占存储空间。
    若段表存放的起始地址为M，则K号段对应的段表项存放的地址为M+K*6（段表项长度为6字节）

• 地址转换

  • 

• 分段地址变换机构

  • 过程
    • ①从逻辑地址A中取出前几位为段号S，后几位为段内偏移量W。
      注意，在地址变换的题目中，要注意逻辑地址是用二进制数还是用十进制数给出的。
    • ②比较段号S和段表长度M，若S≥M，则产生越界中断，否则继续执行。
    • ③段表中段号S对应的段表项地址=段表始址F+段号S×段表项长度，取出该段表项的前几位得到段长C。
      若段内偏移量≥C，则产生越界中断，否则继续执行。
    • ④取出段表项中该段的始址b，计算E=b+W，用得到的物理地址E去访问内存。
  • 图片
    • 

• 分页和分段的对比

  • 页是信息的物理单位。分页的主要目的是为了实现离散分配，提高内存利用率。分页仅仅是系统管理上的需要，完全是系统行为，对用户是不可见的。
  • 段是信息的逻辑单位。分段的主要目的是更好地满足用户需求。一个段通常包含着一组属于一个逻辑模块的信息。分段对用户是可见的，用户编程时需要显式地给出段名。
  • 分页会产生内部碎片，不会产生外部碎片（段页式有内部碎片）
    分段会产生外部碎片，不会产生内部碎片
  • 页的大小固定且由系统决定。段的长度却不固定，决定于用户编写的程序。
  • 分页的用户进程地址空间是一维的，程序员只需给出一个记忆符即可表示一个地址。
  • 分段的用户进程地址空间是二维的，程序员在标识一个地址时，既要给出段名，也要给出段内地址。
  • 分段比分页更容易实现信息的共享和保护。
    • 在分段系统中，段的共享是通过两个作业的段表中相应表项指向被共享的段的同一个物理副本来实现的。
    • 分段管理的保护方法主要有两种：一种是存取控制保护，另一种是地址越界保护。
      • 地址越界保护将段表寄存器中的段表长度与逻辑地址中的段号比较，若段号大于段表长度，则产生越界中断
      • 再将段表项中的段长和逻辑地址中的段内偏移进行比较，若段内偏移大于段长，也会产生越界中断。
      • 分页管理只需要判断页号是否越界，页内偏移是不可能越界的。
    • 关于可重入程序
      • 当一个作业正从共享段中读取数据时，必须防止另一个作业修改此共享段中的数据。
      • 不能被修改的代码称为纯代码或可重入代码（不属于临界资源），可重入代码是可以共享的。
      • 可修改的代码是不能共享的（比如，有一个代码段中有很多变量，各进程并发地同时访问可能造成数据不一致）
    • 可重入程序主要是通过共享来使用同一块存储空间的，或通过动态链接的方式将所需的程序映射到相关进程中去
      可以减少对程序段的调入与调出，因此减少了对换数量
  • 访问一个逻辑地址需要几次访存？
    • 分页（单级页表）：第一次访存一一查内存中的页表，第二次访存一一访问目标内存单元。总共两次访存
    • 分段：第一次访存一一查内存中的段表，第二次访存一一访问目标内存单元。总共两次访存
    • 与分页系统类似，分段系统中也可以引入快表机构，将近期访问过的段表项放到快表中，这样可以少一次访问，加快地址变换速度。

6.段页式管理

• 分页与分段的优缺点分析
  • 分页管理
    • 内存空间利用率高，不会产生外部碎片，只会有少量的页内碎片
    • 不方便按照逻辑模块实现信息的共享和保护
  • 分段管理
    • 很方便按照逻辑模块实现信息的共享和保护，不会产生内部碎片
    • 如果段长过大，为其分配很大的连续空间会很不方便。另外，段式管理会产生外部碎片
  • 段页式管理会产生内部碎片

• 段页式管理

  • 段页式系统中，进程首先划分为段，每段再进一步划分为页，每个进程一张段表，每个段一张页表
  • 将地址空间按照程序自身的逻辑关系划分为若干个段，在将各段分为大小相等的页面
  • 将内存空间分为与页面大小相等的一个个内存块，系统以块为单位为进程分配内存
  • 图片
    • 

• 段页式管理的逻辑地址结构

  • 段页式系统的逻辑地址结构由段号、页号、页内地址（页内偏移量）组成。
    • 
  • 段号的位数决定了每个进程最多可以分几个段，页号位数决定了每个段最大有多少页
  • 页内偏移量决定了页面大小、内存块大小是多少
  • 若系统是按字节寻址的，则段号占16位，因此在该系统中，每个进程最多有$2^{16}=64K$个段
  • 页号占4位，因此每个段最多有$2^4=16$页
    页内偏移量占12位，因此每个页面/每个内存块大小为$2^{12}=4096=4KB$
• 段页式管理中的段表与页表
  • 每个段对应一个段表项，每个段表项由段号、页表长度、页表存放块号（页表起始地址）组成。
    每个段表项长度相等，段号是隐含的。
  • 每个页面对应一个页表项，每个页表项由页号、页面存放的内存块号组成。每个页表项长度相等，页号是隐含的。
  • 图片
    • 
• 段页式管理的逻辑地址转换
  • 过程（需进行三次访存，也可用快表解决）
    • 1.由逻辑地址得到段号、页号、页内偏移量
    • 2.段号与段表寄存器中的段长度比较，检查是否越界
    • 3.由段表始址、段号找到对应段表项
    • 4.根据段表中记录的页表长度，检查页号是否越界
    • 5.由段表中的页表地址、页号得到查询页表，找到相应页表项
    • 6.由页面存放的内存块号、页内偏移量得到最终的物理地址
    • 7.访问目标单元
  • 图片
    • 

二.虚拟内存管理（✪）

1.虚拟内存的基本概念

• 传统存储管理方式的缺点
  • 许多在程序运行中不用或暂时不用的程序（数据）占据了大量的内存空间，而一些需要运行的作业又无法装入运行，显然浪费了宝贵的内存资源。
  • 一次性
    • 作业必须一次性全部装入内存后，才能开始运行。
    • 当作业很大而不能全部被装入内存时，将使该作业无法运行
    • 当大量作业要求运行时，由于内存不足以容纳所有作业，只能使少数作业先运行，导致多道程序度的下降。
  • 驻留性
    • 作业被装入内存后，就一直驻留在内存中，其任何部分都不会被换出，直至作业运行结束。
    • 运行中的进程会因等待I/O而被阻塞，可能处于长期等待状态。

• 虚拟内存的概述

  • 概述

    • 虚拟内存在物理上扩展内存相对有限的条件下，在逻辑上扩充内存，实际的物理内存大小没有变
    • 虚拟内存使用外存上的空间来扩充内存空间，通过一定的换入/换出，使得整个系统在逻辑上能够使用一个远远超出其物理内存大小的内存容量。
    • 因为虚拟内存技术调换页面时需要访问外存，会导致平均访存时间增加，若使用了不合适的替换算法，则会大大降低系统性能。

  • 虚拟内存空间的大小限制（区分实际容量和最大容量的决定因素）

    • 虚存的实际容量 ≤ 内存容量和外存容量之和
      • 这是硬件的硬性条件规定的，若虚存的实际容量超过了这个容量，则没有相应的空间来供虚存使用。
    • 虚存的最大容量 ≤ 计算机的地址位数能容纳的最大容量
      • 虚拟内存的最大容量由计算机的地址结构决定
      • 假设地址是32位的，按字节编址，一个地址代表1B存储空间，则虚存的最大容量≤4GB($2^{32}$B)。
      • 这是因为若虚存的最大容量超过4GB，则32位的地址将无法访问全部虚存，也就是说4GB以后的空间被浪费了，相当于没有一样，没有任何意义。
    • 实际虚存的容量是取条件以上两种情况的交集，即两个条件都要满足，仅满足一个条件是不行的。
• 虚拟内存的特征
  • 多次性：无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存。
  • 对换性：在作业运行时无需一直常驻内存，而是允许在作业运行过程中，将作业换入、换出。
  • 虚拟性：从逻辑上扩充了内存的容量，使用户看到的内存容量，远大于实际的容量。
  • 注：还有离散性（基于非连续分配方式）

• 虚拟内存技术的实现（只能基于非连续分配的技术）

  • 虚拟内存管理方式的基础

    • 虚拟内存的实现需要建立在离散分配的内存管理方式的基础上
    • 局部性原理（虚拟存储管理系统的基础，实现多次性）
      • 在程序装入时，可以将程序中很快会用到的部分装入内存，暂时用不到的部分留在外存，就可以让程序开始执行。
      • 概念
        • 时间局部性：如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行；
          如果某个数据被访问过，不久之后该数据很可能再次被访问。（因为程序中存在大量的循环）
        • 空间局部性：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问。
          (因为很多数据在内存中都是连续存放的，并且程序的指令也是顺序地在内存中存放的)
        • 高速缓存技术：使用频繁的数据放到更高速的存储器中

  • 虚拟内存技术的三个方式：

    • 请求分页存储管理
    • 请求分段存储管理
    • 请求段页式存储管理
  • 实现虚拟内存中操作系统提供的功能
    • 请求调页（或请求调段）功能
      • 在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。
    • 页面置换（或段置换）的功能
      • 若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。
  • 实现虚拟内存的硬件支持
    • 一定容量的内存和外存。
    • 页表机制（或段表机制），作为主要的数据结构。
    • 中断机构，当用户程序要访问的部分尚未调入内存时，则产生中断。
    • 地址变换机构，逻辑地址到物理地址的变换。

2.缺页中断

• 缺页中断是访存指令引起的，说明所要访问的页面不在内存中，进行缺页中断处理并调入所要访问的页后，访存指令显然应该重新执行被中断的那一条指令
• 关于缺页中断的次数
  • 缺页中断的次数等于其访问的页帧数。若页面尺寸增大而可容纳的最大页数不变，存放程序需要的页帧数就会减少，因此缺页中断的次数也会减少。
  • 在请求分页存储管理中，若采用FIFO页面置换算法，则当可供分配的页帧数增加时，缺页中断的次数可能增加也可能减少
    其它页面置换算法的缺页中断次数则会随着可供分配的页帧数的增加而减少
  • 无论采用什么页面置换算法，每种页面第一次访问时不可能在内存中，必然发生缺页，所以缺页次数大于或等于页号数量。
• 影响缺页率的因素
  • 页置换算法
    • 页缓冲队列是将淘汰的页面缓存下来，暂时不写回磁盘，队列长度会影响页面置换的长度，但是不会影响缺页率
  • 工作集的大小
  • 进程的数量

3.请求分页管理方式

• 引入的原因

  • 与基本分页管理相比，请求分页管理中，为了实现“请求调页”，操作系统需要知道每个页面是否已经调入内存；如果还没调入，那么也需要知道。并且还需要页面在外存中存放的位置

  • 当内存空间不够时，要实现“页面置换”，操作系统需要通过某些指标来决定到底换出哪个页面；有的页面没有被修改过，就不用再浪费时间写回外存。有的页面修改过，就需要将外存中的旧数据覆盖，因此，需要记录各个页面是否被修改的信息。

• 请求分页存储管理的主要特点

  • 请求分页存储管理就是为了解决内存容量不足而使用的方法，它基于局部性原理实现了以时间换取空间的目的。
  • 主要特点是间接扩充了内存。

• 请求页表项的结构

  • 新增四个字段
    • 状态位P（合法位）。用于指示该页是否已调入内存，供程序访问时参考。
      决定了是否会发生页面故障
    • 访问字段A。用于记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问，
      供置换算法换出页面时参考。
    • 修改位M。标识该页在调入内存后是否被修改过，以确定页面置换时是否写回外存。
    • 外存地址。用于指出该页在外存上的地址，通常是物理块号，供调入该页时参考。
  • 图片
    • 

• 缺页中断机构

  • 过程
    • 在请求分页系统中，每当要访问的页面不在内存时，便产生一个缺页中断，然后由操作系统的缺页中断处理程序处理中断
    • 此时缺页的进程阻塞，放入阻塞队列，调页完成后再将其唤醒，放回就绪队列。
    • 如果内存中有空闲块，则为进程分配一个空闲块（分配页框），将所缺页面从外存装入该块（磁盘I/O），并修改页表中相应的页表项。
    • 如果内存中没有空闲块，则由页面置换算法选择一个页面淘汰，若该页面在内存期间被修改过，则要将其写回外存。
      未修改过的页面不用写回外存。
  • 特点
    • 在指令执行期间而非一条指令执行完后产生和处理中断信号，属于内部异常（故障）。
    • 一条指令在执行期间，可能产生多次缺页中断。

• 地址变换机构

  • 与基本分页存储管理的不同之处
    • 需要检查所需页面是否在内存中，查看快表和请求页表
    • 若页面不在内存中则产生缺页中断，需要请求调页
    • 若内存空间不够，还需换出页面
    • 页面调入内存后，需要修改相应页表项
  • 基本流程
    • 
  • 注意事项
    • 在具有快表机构的请求分页系统中，访问一个逻辑地址时，若发生缺页，则地址变换步骤是
      • 查快表（未命中）一一查慢表（发现未调入内存）一一调页（调入的页面对应的表项会直接加入快表）一一查快表（命中）一一访问目标内存单元
    • ①只有“写指令”才需要修改“修改位”。并且，一般来说只需修改快表中的数据，只有要将快表项删除时才需要写回内存中的慢表。这样可以减少访存次数。
    • ②和普通的中断处理一样，缺页中断处理依然需要保留CPU现场。
    • ③需要用某种“页面置换算法”来决定一个换出页面
    • ④换入/换出页面都需要启动慢速的I/O操作，可见，如果换入/换出太频繁，会有很大的开销
    • ⑤页面调入内存后，需要修改慢表，同时也需要将表项复制到快表中。
    • ⑥快表中有的页面一定是在内存中的。若某个页面被换出外存则快表中的相应表项也要删除，否则可能访问错误的页面

4.页框分配

• 驻留集
  • 指请求分页存储管理中给进程分配的物理块的集合。
  • 在采用了虚拟存储技术的系统中，驻留集大小一般小于进程的总大小。
  • 若驻留集太小，会导致缺页频繁，系统要花大量的时间来处理缺页，实际用于进程推进的时间很少：
  • 驻留集太大，又会导致多道程序并发度下降，资源利用率降低。所以应该选择一个合适的驻留集大小。
• 分配策略
  • 固定分配：操作系统为每个进程分配一组固定数目的物理块，在进程运行期间不再改变。即驻留集大小不变
  • 可变分配：先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况做适当的增加或减少。即驻留集大小可变
• 置换策略
  • 局部置换：发生缺页时只能选进程自己的物理块进行置换。
  • 全局置换：可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程。
    • 全局置换意味着一个进程拥有的物理块数量必然会改变，因此不可能是固定分配
• 三种内存分配置换策略
  • 固定分配局部置换
    • 系统为每个进程分配一定数量的物理块，在整个运行期间都不改变。若进程在运行中发生缺页，则只能从该进程在内存中的页面中选出一页换出，然后再调入需要的页面。
    • 缺点：很难在刚开始就确定应为每个进程分配多少个物理块才算合理。
    • 采用这种策略的系统可以根据进程大小、优先级、或是根据程序员给出的参数来确定为一个进程分配的内存块数
  • 可娈分配全局置换
    • 过程
      • 刚开始会为每个进程分配一定数量的物理块。操作系统会保持一个空闲物理块队列。
      • 当某进程发生缺页时，从空闲物理块中取出一块分配给该进程；
      • 若已无空闲物理块，则可选择一个未锁定的页面换出外存，再将该物理块分配给缺页的进程。
        • 系统会锁定一些页面，这些页面中的内容不能置换出外存（如：重要的内核数据可以设为锁定）
    • 缺点：采用这种策略时，只要某进程发生缺页，都将获得新的物理块，仅当空闲物理块用完时，系统才选择一个未锁定的页面调出。
      被选择调出的页可能是系统中任何一个进程中的页，因此这个被选中的进程拥有的物理块会减少，缺页率会增加。
  • 可变分配局部置换
    • 刚开始会为每个进程分配一定数量的物理块。当某进程发生缺页时，只允许从该进程自己的物理块中选出一个进行换出外存。
    • 如果进程在运行中频繁地缺页，系统会为该进程多分配几个物理块，直至该进程缺页率趋势适当程度；
      反之，如果进程在运行中缺页率特别低，则可适当减少分配给该进程的物理块。
    • 区别
      • 可变分配全局置换：只要缺页就给分配新物理块
      • 可变分配局部置换：要根据发生缺页的频率来动态地增加或减少进程的物理块
• 页面调入的时机
  • 预调页策略
    • 根据局部性原理，一次调入若干个相邻的页面可能比一次调入一个页面更高效。但如果提前调入的页面中大多数都没被访问过，则测又是低效的。（主要是空间局部性原理）
      因此可以预测不久之后可能访问到的页面，将它们预先调入内存，但目前预测成功率只有50%左右
    • 这种策略主要用于进程的首次调入，由程序员指出应该先调入哪些部分，在运行前调入
  • 请求调页策略
    • 进程在运行期间发现缺页时才将所缺页面调入内存。由这种策略调入的页面一定会被访问到，在运行时调入
    • 但由于每次只能调入一页，而每次调页都要磁盘I/O操作，因此I/O开销较大。
• 页面调入的区域
  • 外存中的交换区与文件区
    • 交换区：读/写速度更快，采用连续分配方式
    • 文件区：读/写速度更慢，采用离散分配方式
    • 若交换区的磁盘利用率过高，说明物理内存非常短缺，此时的处理策略如下
      • 增大物理内存容量，使每个程序得到更多的页框，能减少缺页率，进而减少换入换出过程，提高CPU的利用率
      • 减少多道程序的度数，可减少主存中的进程数，减少换入换出频率，可以提高CPU的利用率
      • 使用更快的磁盘交换区和更快速的CPU没有用
  • 三种调入调出区域处理
    • 系统拥有足够的对换区空间
      • 在进程运行前，需将进程相关的数据从文件区复制到对换区。
      • 页面的调入、调出都是在内存与对换区之间进行，这样可以保证页面的调入、调出速度很快。
    • 系统缺少足够的对换区空间
      • 凡是不会被修改的数据都直接从文件区调入，由于这些页面不会被修改，因此换出时不必写回磁盘，下次需要时再从文件区调入即可。
      • 对于可能被修改的部分，换出时需写回磁盘对换区，下次需要时再从对换区调入。
    • UNIX方式
      • 运行之前进程有关的数据全部放在文件区，故未使用过的页面，都可从文件区调入。
      • 若被使用过的页面需要换出，则写回对换区，下次需要时从对换区调入。
  • 页面调入的方法
    • 当进程所访问的页面不在内存中时(存在位为0)，便向CPU发出缺页中断，中断响应后便转入缺页中断处理程序。
    • 该程序通过查找页表得到该页的物理块，此时如果内存未满，则启动磁盘I/O，将所缺页调入内存，并修改页表。
    • 如果内存已满，则先按某种置换算法从内存中选出一页准备换出
      • 如果该页未被修改过(修改位为0)，则无须将该页写回磁盘
      • 如果该页已被修改(修改位为1)，则必须将该页写回磁盘
    • 然后将所缺页调入内存，并修改页表中的相应表项，置其存在位为1。
      调入完成后，进程就可利用修改后的页表形成所要访问数据的内存地址。

5.页面置换算法（♚）

• 页面置换的概述
  • 进程运行时，若其访问的页面不在内存中而需将其调入，但内存已无空闲空间时，就需要从内存中调出一页程序或数据，送入磁盘的对换区。
  • 选择调出页面的算法就称为页面置换算法。好的页面置换算法应有较低的页面更换频率，也就是说，应将以后不会再访问或以后较长时间内不会再访问的页面先调出。
• 最佳置换算法（OPT）
  • 概述
    • 选择的被淘汰页面是以后永不使用的页面，或是在最长时间内不再被访问的页面，以便保证获得最低的缺页率。
  • 图片
    • 
  • 特点
    • 最佳置换算法可以保证最低的缺页率
    • 但实际上，操作系统无法提前预判页面访问序列。因此，最佳置换算法是无法实现的。但可利用该算法去评价其他算法
• 先进先出页面置换算法（FIFO）
  • 概述
    • 每次选择淘汰的页面是最早进入内存的页面
    • 把调入内存的页面根据调入的先后顺序排成一个队列，需要换出页面时选择队头页面即可。
      队列的最大长度取决于系统为进程分配了多少个内存块。
  • 图片
    • 
  • 特点
    • Belady异常一一当为进程分配的物理块数增大时，缺页次数不减反增的异常现象。只有FIFO算法会产生Belady异常。
    • FIFO算法虽然实现简单，但是该算法与进程实际运行时的规律不适应，因为先进入的页面也有可能最经常被访问。
      算法性能差
• 最近最久未使用置换算法（LRU）
  • 概述
    • 每次淘汰的页面是最近最久未使用的页面
    • 赋予每个页面对应的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间t
    • 当需要淘汰一个页面时，选择现有页面中访问值最大的，即最近最久未使用的页面（进行排序）。
    • 在手动做题时，若需要淘汰页面，可以逆向检查此时在内存中的几个页面号。在逆向扫描过程中最后一个出现的页号就是要淘汰的页面。
  • 图片
    • 
  • 特点
    • 该算法的实现需要专门的硬件支持，虽然算法性能好，但是实现困难，开销大（需要对所有页进程排序）

• 时钟置换算法（CLOCK）

  • 简单CLOCK置换算法（又称最近未用算法_NRU）
    • 概述
      • 为每个页面设置一个访问位，将内存中的所有页面视为一个链式循环队列，并有一个替换指针与之相关联。
        访问位为1，表示最近访问过，访问位为0，表示最近没访问过
      • 当某页首次被装入或被访问时，其访问位置为1，访问时在内存中存在页面则指针不动
      • 在选择一页淘汰时，只需检查页的访问位。
        • 若为0，就选择该页换出
        • 若为1，则将它置为0，暂不换出，给予该页第二次驻留内存的机会，再依次顺序检查下一个页面。
        • 当检查到队列中的最后一个页面时，若其访问位仍为1，则返回到队首去循环检查。
      • 当某一页被替换时，该指针被设置指向被替换页面的下一页。
    • 图片
      • 访问序列：7、0、1、2、0、3、0、4
        
    • 特点
      • 若第一轮扫描中所有页面都是1，则将这些页面的访问位依次置为0后，再进行第二轮扫描
      • 第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK算法选择一个淘汰页面最多会经过两轮扫描

  • 改进的时钟置换算法

    • 改进位与修改位
      • 简单的时钟置换算法仅考虑到一个页面最近是否被访问过。如果被淘汰的页面没有被修改过，就不需要执行I/O操作写回外存。只有被淘汰的页面被修改过时，才需要写回外存。
      • 因此，除了考虑一个页面最近有没有被访问过之外，操作系统还应考虑页面有没有被修改过。在其他条件都相同时，应优先淘汰没有修改过的页面，避免I/O操作。
      • 修改位=0，表示页面没有被修改过；修改位=1，表示页面被修改过。
      • 用(访问位，修改位)的形式表示各页面状态。如(1,1)表示一个页面近期被访问过，且被修改过。

    • 规则

      • 将所有可能被置换的页面排成一个循环队列

      • 第一轮：从当前位置开始扫描到第一个(0,0)的帧用于替换。本轮扫描不修改任何标志位

        • 第一优先级：最近没访问且没修改的页面
      • 第二轮：若第一轮扫描失败，则重新扫描，查找第一个(0,1)的帧用于替换。本轮将所有扫描过的帧访问位设为0
        • 第二优先级：最近没访问但修改过的页面
      • 第三轮：若第二轮扫描失败，则重新扫描，查找第一个(0,0)的帧用于替换。本轮扫描不修改任何标志位
        • 第三优先级：最近访问过但没修改的页面
      • 第四轮：若第三轮扫描失败，则重新扫描，查找第一个(0,1)的帧用于替换。
        • 第四优先级：最近访问过且修改过的页面
      • 由于第二轮已将所有帧的访问位设为0，因此经过第三轮、第四轮扫描一定会有一个帧被选中，因此改进型CLOCK置换算法选择一个淘汰页面最多会进行四轮扫描
  • 例
    • 首先处理这个16进程数，后缀为H，1个数字为4位，此时前后12位为偏移量（页面大小4KB），此时页号为02，在表中存在位为0需要从外存调入，此时内存大小不够采用置换算法优先置换页号为3的（1,0），此时选C
      
• 四种算法的比较
  • 

6.抖动与工作集

• 抖动（颠簸，高缺页率）
  • 刚刚换出的页面马上又要换入内存，刚刚换入的页面马上又要换出外存，这种频繁的页面调度行为称为抖动，或颠簸。
  • 频繁的置换页面导致大部分时间都花在页面置换之上，导致系统性能下降
  • 产生抖动的主要原因是页面置换算法不合理，进程频繁访问的页面数目高于可用的物理块数
  • 撤销部分进程可以防止产生抖动
• 驻留集与工作集
  • 驻留集：指请求分页存储管理中给进程分配的内存块的集合。
  • 工作集：指在某段时间间隔里，进程实际访问页面的集合。
  • 驻留集大小需要大于工作集大小，否则进程运行过程中将频繁缺页
• 工作集的特点
  • 在进程运行时，若其工作集页面都在主存储器内，则能够使该进程有效地运行，否则会出现频繁的页面调入调出现象
  • 操作系统会根据“窗口尺寸”来算出工作集，工作集大小可能小于窗口尺寸
    • 
  • 实际应用中，操作系统可以统计进程的工作集大小，根据工作集大小给进程分配若干内存块。
    • 如窗口尺寸为5，经过一段时间的监测发现某进程的工作集最大为3，
    • 那么说明该进程有很好的局部性，可以给这个进程分配3个以上的内存块即可满足进程的运行需要。
  • 基于局部性原理可知，进程在一段时间内访问的页面与不久之后会访问的页面是有相关性的。
    因此，可以根据进程近期访问的页面集合（工作集）来设计一种页面置换算法一一选择一个不在工作集中的页面进行淘汰。

7.内存映射文件

• 概述

  • 将磁盘文件的全部或部分内容与进程虚拟地址空间的某个区域建立映射关系，便可以直接访问被映射的文件，
    而不必执行文件I/O操作，也无须对文件内容进行缓存处理。这种特性非常适合用来管理大尺寸文件。
  • 进程可使用系统调用，请求操作系统将文件映射到进程的虚拟地址空间，以访问内存的方式读写文件
  • 进程关闭文件时，操作系统负责将文件数据写回磁盘，并解除内存映射
  • 多个进程可以映射同一个文件，方便共享

• 传统的文件文件访问方式

  • 

• 内存映射文件访问方式

  • 

• 多个进程允许并发地内存映射同一个文件，实现数据共享

  • 

• 优点

  • 程序员编程更简单，已建立映射的文件，只需按访问内存的方式读写即可
  • 文件数据的读入/写出完全由操作系统负责，I/O效率可以由操作系统负责优化