存储模型

发表于 | 分类于
字数统计: 8.5k

一.基本概念：地址重定位

1.要解决的问题

要解决的问题是：如何把一个进程的地址空间的内容装载到内存，然后合理地来分配使用内存，使得每一个进程能够正确地执行。

2.为什么引入

  • 进程中的地址不是最终的物理地址
  • 在进程运行前无法计算出物理地址
    • 因为不能确定进程被加载到内存什么地方

综上，引出了地址重定位的支持。

3.地址重定位

  • 进程地址空间的地址不是最终的物理地址，而是逻辑地址，有时也叫相对地址或者叫虚拟地址。

用户程序经过编译、汇编后形成目标代码，目标代码通常采用相对地址的形式，其首地址为0，其余地址都相对于首地址而编址。不能用逻辑地址在内存中读取信息

  • 物理地址(绝对地址，实地址)： 内存中存储单元的地址，可直接寻址。

为了保证CPU执行指令时可正确访问内存单元，需要将用户程序中的逻辑地址转换为运行时可由机器直接寻址的物理地址，这一过程称为地址重定位。

4.静态重定位和动态重定位

(1).静态重定位

当用户程序加载到内存时，一次性实现逻辑地址到物理地址的转换。一般可以由软件完成。

  • 优点：在程序的执行过程中，地址就直接可以拿来去到内存中取指令或者取数据。
  • 缺点：程序在内存的位置不能改变，一旦改变就要重新计算这个转换过程 。

(2).动态重定位

在进程执行过程中进行地址变换。 →→ 即逐条指令执行时完成地址转换。为了加快速度，需要硬件部件支持。

假设起始的地址是在重定位寄存器(基址寄存器)中，会把逻辑送到了这个寄存器进行计算， CPU在执行时会取到一个逻辑地址，然后就把这个地址送到了这个重定位寄存器来完成地址转换的工作，得到真正的物理地址。

所以逻辑地址经过这样一个部件的转换就会得到物理地址，然后用这个物理地址到内存中去存取相关的指令或者数据。

二.物理内存管理

1.空闲内存管理

管理方式主要分为：等长划分和不等长划分。

(1).等长划分

主要使用的数据结构是 位图。

每个分配单元对应于位图中的一位，0表示空闲，1表示占用(或者相反)

(2).不等长划分

主要使用的数据结构是 空闲区表，已分配区表和空闲块链表。

  • 空闲区表，已分配区表

    表中每一项记录了空闲区 (或已分配区)的起始地址、长度、标志

  • 空闲块链表

    每一个表项用链串联起来

2.内存分配算法

以空闲区表和已分配区表为例介绍内存分配的算法。

  • 首次适配 first fit

    • 在空闲区表中找到第一个满足进程要求的空闲区

  • 下次适配 next fit

    • 从上次找到的空闲区处接着查找

  • 最佳适配 best fit

    • 查找整个空闲区表，找到能够满足进程要求的最小空闲区

  • 最差适配 worst fit

    • 总是分配满足进程要求的最大空闲区

当找到了满足要求的空闲区后，将该空闲区分为两部分，一部分供进程使用，另一部分形成新的空闲区。

示例：

3.回收问题

内存回收算法主要考虑的就是合并。

  • 当某一块归还后，前后空闲空间合并，修改内存空闲区表

  • 四种情况

    • 上相邻、下相邻、上下都相邻、上下都不相邻

三.伙伴系统

伙伴系统是Linux低层内存管理采用的一种经典的内存分配方案。它是一种特殊的 “分离适配”算法。

主要思想：将内存按2的幂进行划分，组成若干空闲块链表;查找该链表找到能满足进程需求的最佳匹配块。

算法：

  • 首先将整个可用空间看作一块: $2^U$
  • 假设进程申请的空间大小为 s，如果满足$2^{U-1} < s <= 2^U$，则分配整个块。

  • 否则，将块划分为两个大小相等的伙伴，大小为$2^{U-1}$

  • 一直划分下去直到产生大于或等于 s 的最小块

示例：

四.基本内存管理方案

单一连续区、固定分区和可变分区，它们的特点进程作为一个整体进入一片连续的区域。

页式，段式和段页式这三种方案不是整个进程进入内存的，而是进入内存的若干个区域，而且这些区域也不连续。

1.单一连续区

基本思想：一段时间内只有一个进程在内存。

特点：简单，内存利用率低

有三种不同的布局：

2.固定分区

  • 把内存空间分割成若干区域，称为分区
  • 每个分区的大小可以相同也可以不同
  • 分区大小固定不变
  • 每个分区装一个且只能装一个进程

示例：

3.可变分区

(1).基本概念

  • 根据进程的需要，把内存空闲空间分割出一个分区，分配给该进程

  • 剩余部分成为新的空闲区

缺点：

  • 外碎片
  • 导致利用率降低

(2).碎片问题的解决

碎片：很小的、不易利用的空闲区，会导致内存利用率下降。

解决方案：

紧缩技术(memory compaction)：在内存移动程序，将所有小的空闲区合并为较大的空闲区。

不是所有进程都可以随便的搬家移动的，需要考虑两个问题：

  • 开销。如果有很多进程都需要移动，这会导致时间，空间上的开销。

  • 移动的时机。 比如一个进程正在做磁盘的IO操作 ，那这时此进程就不能够移动去别处，因为这样会影响IO的结果。

4.页式存储管理方案

(1).基本概念

设计思想

  • 用户进程地址空间被划分为大小相等的部分，称为页(page) 或页面，从0开始编号。
  • 内存空间按同样大小划分为大小相等的区域，称 为页框(page frame)，从0开始编号;也称为物理页面，页帧，内存块。

内存分配(规则)

  • 以页为单位进行分配，并按进程需要的页数来分配；逻辑上相邻的页，物理上不一定相邻。

  • 典型页面尺寸：4K 或 4M

逻辑地址

逻辑地址实际上由两部分组成，页号和页内地址。

这种划分是系统硬件自动完成的。 对用户来讲实际上是透明的，这是页式存储管理方案的一个特点。

(2).内存分配的过程

页表会把逻辑上的某一页和物理上的某一页框的对应关系记录下来， 通过页表记录的这样一个映射关系。页表里的一行叫做页表项。

(3).相关数据结构与地址转换

  • 页表
    • 页表项：记录了逻辑页号与页框号的对应关系
    • 每个进程一个页表，存放在内存
    • 页表起始地址保存在系统的寄存器中，或者可能是在PCB中，我也不清楚。
  • 空闲内存管理
    • 用 bitmap位图这个数据结构可以管理物理内存
  • 地址转换(硬件支持)
    • CPU取到逻辑地址，自动划分为页号和页内地址；用页号查页表，得到页框号，再与页内偏移拼接成为物理地址

(4).问题

会产生内碎片问题。

假设一个进程需要五页，然后加一条指令，尽管只有还剩一条指令，但还是得要给它分六页，所以实际上还是得给它分成六页，假设最后一条指令在这个第六页上，只占了很小很小的空间，整个大部分的页面都是空的，而这些空的内存空间就是内碎片。

5.段式存储管理方案

(1).基本概念

设计思想

  • 用户进程地址空间:按程序自身的逻辑关系划分为若干个程序段，每个程序段都有一个段名
  • 内存空间被动态划分为若干长度不相同的区域，称为物理段，每个物理段由起始地址和长度确定。

内存分配(规则)

  • 以段为单位进行分配，每段 在内存中占据连续空间，但各段之间可以不相邻

逻辑地址

逻辑地址和页式不一样的地方是：段号和段内地址不是自动划分的，必须显示给出。

(2).内存分配的过程

示例：

要把逻辑地址和物理地址对应关系记录下来就需要一个数据结构，这就是段表。

(3).相关数据结构与地址转换

  • 段表:

    • 每项记录了段号、段首地址和段长度之间的关系
    • 每个进程一个段表，存放在内存
    • 段表起始地址保存在何处?与页表一样

  • 物理内存管理：

    • 可以用不等长的物理内存管理方法，可以用空闲区表来管理这个物理内存

  • 地址转换(硬件支持)

    • **CPU取到逻辑地址，用段号查段表，得到该段在内存的起始地址，与段内偏移地址计算出物理地址**

6.段页式存储管理方案

(1).基本概念

产生背景

  • 综合页式、段式方案的优点，克服二者的缺点

设计思想

  • 用户进程划分：先按段划分，每一段再按页面划分

逻辑地址

  • 由三部分组成：第一部分是段号，然后是原来的段内地址又划分成页号和页内地址，所以由三部分组成。

内存划分

  • 同页式存储管理方案

内存分配

  • 以页为单位进行分配

(2).段页式存储管理

数据结构及有关操作

  • 段表：记录了每一段的页表始址和页表长度
  • 页表：记录了逻辑页号与页框号的对应关系。每一段有一张页表，一个进程有多个页表

每个进程由一张段表和多个页表组成的。

  • 空闲区管理：同页式管理
  • 内存分配、回收：同页式管理

地址转换

首先拿到逻辑地址，逻辑地址是由两部分组成：段号和段内地址。用段号去查段表，得到了所对应的页表的起始地址和长度，然后再把段内地址自动划分成两部分：页号页内地址，用页号去查对应的页表，得到页框号，然后再和页内地址拼接成最后的物理地址。

整个这个过程比较复杂，成本也比较高。

7.基本内存管理方案小结

五.交换技术SWAPPING

1.为什么引入SWAPPING

为了解决在较小的内存空间运行较大的进程。采用了内存”扩充”技术。

  • 内存紧缩技术(例如:可变分区)
  • 覆盖技术 overlaying
  • 交换技术 swapping
  • 虚拟存储技术 virtual memory

2.覆盖技术

(1).基本概念

解决的问题：程序大小超过物理内存总和

  • 程序执行过程中，程序的不同部分在内存中相互替代

    • 按照其自身的逻辑结构，将那些不会同时执 行的程序段共享同一块内存区域

    • 要求程序各模块之间有明确的调用结构

  • 程序员声明覆盖结构，操作系统完成自动覆盖

主要用于早期的操作系统

(2).示例

3.交换技术

(1).基本概念

  • 设计思想

    • 内存空间紧张时，系统将内存中某些进程暂时移到外存，把外存中某些进程换进内存，占据前者所占用的区域(进程在内存与磁盘之间的动态调度)

  • 讨论：实现时遇到的问题

    • 进程的哪些内容要交换到磁盘?会遇到什么困难?
      • 运行时创建或修改的内容:栈和堆
    • 在磁盘的什么位置保存被换出的进程?
      • 交换区:一般系统会指定一块特殊的磁盘区域作为交换空间(swap space)，包含连续的磁道， 操作系统可以使用底层的磁盘读写操作对其高效访问。
    • 交换时机?
      • 只要不用就换出(很少再用);
      • 内存空间不够或有不够的危险时换出
    • 如何选择被换出的进程?
      • 考虑进程的各种属性;不应换出处于等待I/O状态的进程
    • 如何处理进程空间增长?
      • 预留空间向上增长
      • 预留空间同向增长

六.虚拟存储技术

1.基本概念

  • 虚拟存储技术是指:当进程运行时，先将其一部分装入内存，另一部分暂留在磁盘，当要执行的指令或访问的数据不在内存时，由操作系统自动完成将它们从磁盘调入内存的工作。

  • 虚拟地址空间：引入了虚拟存储技术之后每个进程的地址空间

  • 虚拟地址：是在虚拟内存中指令或数据的位置，该位置可以被访问，仿佛它是内存的一部分

产生疑问：虚拟内存的地址究竟在哪里？

2.存储器的层次结构

3.虚存与存储体系

  • 把内存与磁盘有机地结合起来使用，从而得到一个容量很大的“内存”，即虚存。
  • 虚存是对物理内存的抽象，构建在存储体系之上，由操作系统协调各存储器的使用
  • 虚存提供了一个比物理内存空间大得多的地址空间

虚存的大小受到了计算机系统的寻址机制还有磁盘空间中可用空间的这两方面的限制。

4.地址保护

  • 确保每个进程有独立的地址空间
  • 确保进程访问合法的地址范围
  • 确保进程的操作是合法的

防止地址越界，防止访问越权。

示例

5. 虚拟页式

把虚拟存储技术应用到页式存储管理方案就得到了虚拟页式存储管理系统

(1).概念

基本思想

  • 进程开始运行之前，不是装入全部页面，而是装入一个或零个页面
  • 之后，根据进程运行的需要，动态装入其 他页面
  • 当内存空间已满，而又需要装入新的页面 时，则根据某种算法置换内存中的某个页 面，以便装入新的页面

(2).两种方式

1、请求调页(demand paging)

当需要这个页面，这个页面还没在内存，这时操作系统把它调入内存。

2、预先调页(prepaging)

预测猜测哪些页面即将会被用到，提前把它调入内存

虚拟存储技术其实以CPU时间和磁盘空间换取昂贵内存空间， 这是操作系统中的资源转换技术。

六.页表及页表项的设计

当进程运行的过程中如果要访问一些页面，那就要通过一个页表，页表记录哪些页面已经加载到内存。

1.页表表项设计

(1).基本概念

页表由页表项组成，包含页框号、有效位、访问位、修改位、保护位。

  • 页框号 (内存块号、物理页面号、页帧号)

  • 有效位(驻留位、中断位)：表示该页是在内存还是在磁盘

    • 有效位是0表示这个页面还没有读进内存，这时页框号是无效的；如果有效位为1 ，表示相应的虚页面的内容已经读入内存。

  • 访问位：引用位

    • 引用位为1表示被引用
  • 修改位：此页在内存中是否被修改过
    • 修改过则为1
  • 保护位：读/可读写

通常，页表项是硬件设计的。

(2).关于页表

32位虚拟地址空间的页表规模

  • 页面大小为4K;页表项大小为4字节
  • 则:一个进程地址空间有 $2^{20}$页
  • 其页表需要占 1024页

64位虚拟地址空间的页表规模

  • 页面大小为4K;页表项大小为8字节

  • 页表规模: 32,000 TB

页表页在内存中若不连续存放，则需要引入页表页的 地址索引表 → 页目录

(3).二级页表结构及地址映射

(4).CORE17页表结构

虚拟地址空间$2^{48}$

(5).1386页目录项和页表项

  • PFN(Page Frame Number)：页框号
  • P(Present)：有效位
  • A(Accessed)：访问位
  • D(Dirty)：修改位
  • R/W(Read/Write)：只读/可读写
  • U/S(User/Supervisor)：用户/内核
  • PWT(Page Write Through)：缓存写策略
  • PCD(Page Cache Disable)：禁止缓存
  • PS(Page Size):大页4M

2.反转页表

(1).基本概念

地址转换

  • 从虚拟地址空间出发：虚拟地址 → 查页表 → 得到页框号 → 形成物理地址 每个进程一张页表

解决思路

  • 从物理地址空间出发，整个系统建立一张页表

  • 页表项记录进程i的某虚拟地址(虚页号)与页框号的映射关系

(3).反转页表设计

  • PowerPC、UltraSPARC和IA-64 等体系结构采用

  • 将虚拟地址的页号部分映射到一个散列值

  • 散列值指向一个反转页表

  • 反转页表大小与实际内存成固定比例，与进程个数无关

七.地址转换过程及TLB的引入

1.地址转换过程

整个过程是由MMU内存管理单元完成的。

内存管理单元的作用将CPU取到的虚拟地址转换成物理地址。

MMU的位置如下：

2.快表TLB的引入

(1).问题：

  • 页表 → 两次或两次以上的内存访问

  • CPU的指令处理速度与内存指令的访问速度差异大，CPU的速度得不到充分利用

如何加快地址映射速度，以改善系统性能?

利用程序访问的局部性原理→引入快表(TLB)→加快地址转换的速度

(2).基本概念

快表(Translation Look-aside Buffers)：实际上是一个缓冲区。

特点：

  • 在CPU中引入的高速缓存(Cache)，可以匹配CPU的处理 速率和内存的访问速度

  • 一种随机存取型存储器，除连线寻址机制外，还有接线逻辑，能按特定的匹配标志在一个存储周期内对所有的字同时进行比较

  • 快表通常称为相联存储器，特点是按内容并行查找。

  • 快表容量有限，保存正在运行进程的页表的子集(部分页表项)

快表的大小：像高速缓存一样分成几级，每一级的大小不一样。

快表的位置：在CPU片上

(3).引入快表后地址转换过程示意

八.页错误

(1).基本概念

页错误又称页面错误、页故障、页面失效。指的是地址转换过程中硬件产生的异常。

具体原因：

  • 所访问的虚拟页面没有调入物理内存 → 缺页异常

  • 页面访问违反权限(读/写、用户/内核)

  • 错误的访问地址

    代码，数据呀，以及引用的一些共享库是有内容的，但是在访问过程当中的虚拟地址指向了没有 内容的位置，这相当于错误的访问地址。

(2).缺页异常处理

  • 是一种PageFault

  • 在地址映射过程中，硬件检查页表时发现所要访 问的页面不在内存，则产生该异常——缺页异常

  • 由操作系统执行缺页异常处理程序，主要工作：获得磁盘地址， 启动磁盘，将该页调入内存

    • 第一种可能性：如果内存中有空闲页框，则分配一个页框， 将新调入页装入，并修改页表中相应页表项 的有效位及相应的页框号
    • 第二种可能性：若内存中没有空闲页框，则要置换内存中某一页框；若该页框内容被修改过，则要将其写回磁盘

可以增加预取的功能。 也就是在把页面调入内存的同时，顺带的把相关的一些页面也都调进内存。 比如Windows就会这么做，当要读入一段页面，这个页面是代码内容的话，就会接着多读入几个页面。 数据的话，它也会多读入几个页面，这就可以在一定程度上防止缺页的再发生。

九.软件相关策略

1.驻留集

驻留集大小：给每个进程分配多少页框。

分配策略：

  • 固定分配策略

    • 进程创建时确定 可以根据进程类型(交互、批处理、应用类)或者基于程序员或系统管理员的需要来确定。

  • 可变分配策略

    • 根据缺页率评估进程局部性表现
    • 缺页率高→增加页框数
    • 缺页率低→减少页框数
    • 系统开销

2.置换问题

当一个内存已经用完，没有空闲页框时，就需要挑一些页框把它内容换出去，这就是置换。

置换范围

  • 计划置换页面的集合是局限在产生缺页中断的进程，还是所有进程的页框?

置换策略

  • 在计划置换的页框集合中，选择换出哪一个页框?

(1).置换范围

  • 局部置换策略

    • 仅在产生本次缺页的进程的驻留集中选择

  • 全局置换策略

    • 将内存中所有未锁定的页框都作为置换的候选

(2).置换策略

  • 所有策略的目标

    →置换出的页框是最近最不可能访问的页

  • 根据局部性原理，最近的访问历史和最近将要 访问的模式间存在相关性，因此，大多数策略都基于过去的行为来预测将来的行为

注意：置换策略设计得越精致、越复杂，实现 的软硬件开销就越大

约束：不能置换被锁定的页框

(3).页框锁定

为什么要锁定页面?

  • 采用虚存技术后
    • 开销 → 使进程运行时间变得不确定
  • 给每一页框增加一个锁定位
  • 通过设置相应的锁定位，不让操作系统将进程使用的页面换出内存，避免产生由交换过程带来的不确定的延迟。

例如:操作系统核心代码、关键数据结构、I/O缓冲

3.清除策略

(1).基本概念

  • 清除：从进程的驻留集中收回页框

  • 虚拟页式系统工作的最佳状态：发生缺页异常时，系统中有大量的空闲页框

  • 结论：在系统中保存一定数目的空闲页框供给比使用所有内存并在需要时搜索一个页框有更好的性能

(2).设计策略

  • 设计一个分页守护进程(paging daemon)，多数时间睡眠着，可定期唤醒以检查内存的状态

  • 如果空闲页框过少，分页守护进程通过预定的页面置换算法选择页面换出内存

  • 如果页面装入内存后被修改过，则将它们写回磁盘。分页守护进程可保证所有的空闲页框是“干净”的

(3).页缓存技术

当进程需要使用一个已置换出的页框时，如果该页框还没有被新的内容覆盖，系统将它从空闲页框集 合中移出即可恢复该页面。

页缓冲技术:

  • 不丢弃置换出的页，将它们放入两个表之一：如果未被修改，则放到空闲页链表中，如果修改了，则放到修改页链表中

  • 被修改的页定期写回磁盘(不是一次只写一个，大大减 少I/O操作的数量，从而减少了磁盘访问时间)

  • 被置换的页仍然保留在内存中，一旦进程又要访问该页，可以迅速将它加入该进程的驻留集合(代价很小)

十.页面置换算法

1.最佳页面置换算法 OPT

设计思想:

  • 置换以后不再需要的或最远的将来才会用到的页面

这个算法的实现是要建立在已经知道页面的走向序列的基础之上才能够实施这个算法。所以通常作为一种标准来衡量其他算法的性能。

2.先进先出算法 FIFO

设计思想

  • 选择在内存中驻留时间最长的页并置换它

实现：页面链表法

3.第二次机会算法 SCR

在先进先出基础上做的改进

设计思想

  • 按照先进先出算法选择某一页面，检查其访问位R，如果为0，则置换该页；如果为1，则给第二次机会，并将访问位置0

4.时钟算法 CLOCK

第二次机会算法问题：摘链、 挂链都需要花一些开销。

时钟算法是把所有的页框组织成一个环形，然后用一个指针，通过移动指针来选择下一个要淘汰的页框。

5.最近未使用算法 NRU

(1).基本思想

设计思想：

  • 选择在最近一段时间内未使用过的一页并置换

实现：

  • 设置页表，表项的两位：访问位(R)， 修改位(M

如果硬件没有这 些位，则可用软 件模拟(做标记)

启动一个进程时，R、M位置0。R位被定期清零(复位)

发生缺页中断时，操作系统检查R，M:

  • 第1类：无访问，无修改
  • 第2类：无访问，有修改
  • 第3类：有访问，无修改
  • 第4类：有访问，有修改

算法思想: 随机从编号最小的非空类中选择一页置换

(2).时钟实现

  1. 从指针的当前位置开始，扫描页框缓冲区，选择遇到的第一个页框 (r=0;m=0) 用于置换( 本扫描过程中，对使用位不做任何修改)

  2. 如果第1步失败，则重新扫描，选择第一个(r=0; m=1)的页框(本次扫描过程中，对每个跳过的页框，将其使用位设置成0)

  3. 如果第2步失败，指针将回到它的最初位置，并且集合中所有页框的使用位均为0。重复第1步，并且，如果有必要，重复第2步。这样将可以找到供置换的页框

6.最近最少使用算法 LRU

(1).基本概念

设计思想：

  • 选择最后一次访问时间距离当前时间最长的一页并置换。即置换未使用时间最长的一页

优点：

  • 性能接近OPT

实现:

  • 时间戳或维护一个访问页的栈 → 开销大

(2).硬件实现

7.最不经常使用算法 NFU

设计思想：

  • 选择访问次数最少的页面置换

实现:

  • 软件计数器，一页一个，初值为0
  • 每次时钟中断时，计数器加R
  • 发生缺页中断时，选择计数器值最小的一页置换

8.老化算法 AGING

改进(模拟LRU)：计数器在加R前先右移一位，R位加到计数器的最左端

9.页面置换算法的应用

(1).例子

  • 系统给某进程分配3个页框(固定分配策略)，初始为空

  • 进程执行时，页面访问顺序为: 2 3 2 1 5 2 4 5 3 2 5 2

要求：

  • 计算应用FIFO、LRU、OPT算法时的缺页次数

(2).BELADY现象

例子:系统给某进程分配 m个页框，初始为空

页面访问顺序为：1 2 3 4 1 2 5 1 2 3 4 5

采用FIFO算法，计算当 m=3 和 m=4 时的缺页中断次数：

十一.工作集算法

1.影响缺页次数的因素

  • 页面置换算法
  • 页面本身的大小
  • 程序的编制方法
  • 分配给进程的页框数量

颠簸(Thrashing，抖动) ：虚存中，页面在内存与磁盘之间频繁调度，使得调度页面所需的时间比进程实际运行的时间还多， 这样导致系统效率急剧下降，这种现象称为颠簸或抖动。

(1).页面尺寸问题

  • 确定页面大小对于分页的硬件设计非常重要 而对于操作系统是个可选的参数。

Intel80x86/Pentium:4096或4M。

  • 引用多种页面尺寸，为有效使用TLB带来灵活性，但给操作系统带来复杂性。

  • 页面尺寸考虑的因素：

    • 内部碎片
    • 页表长度
    • 辅助的物理特性

  • 最优页面大小：$P = \sqrt{2se}$

(2).程序编制方法对缺页次数的影响

例子:分配了一个页框；页面大小为128个整数; 矩阵$A_{128 \times 128}$按行存放

左边的编制方法导致的缺页次数比右边多很多。

(3).分配给进程的页框数与缺页率的关系

2.工作集(WORKING SET)模型

(1).基本思想

根据程序的局部性原理，一般情况下，进程在一段时间内总是集中访问一些页面，这些页面称为活跃页面，如果分配给一个进程的物理页面数太少了，使该进程所需的活跃页面不能全部装入内存，则进程在运行过程中将频繁发生中断。如果能为进程提供与活跃页面数相等的物理页面数，则可减少缺页中断次数。

  • 工作集：一个进程当前正在使用的页框集合

工作集是需要随时调整的，所以要计算当前的一个工作集是多少。

  • 工作集$W (t,\Delta)$=该进程在过去的$Δ$个虚拟时间单位中访问到的页面的集合。

工作集内容取决于三个因素：

  • 访页序列特性

  • 时刻 t

  • 工作集窗口长度 $(Δ)$

    窗口越大，工作集就越大

(2).示例

3.工作集算法

(1).基本思路

找出一个不在工作集中的页面并置换它

思路：

  • 每个页表项中有一个字段：记录该页面最后一次 被访问的时间

  • 设置一个时间值T

  • 判断：根据一个页面的访问时间是否落在 “当前时间-T” 之前或之中决定其在工作集之外还是之内

(2).实现

扫描所有页表项，执行操作

  1. 如果一个页面的R位是1，则将该页面的最后一 次访问时间设为当前时间，将R位清零

  2. 如果一个页面的R位是0，则检查该页面的访问时间是否在 “当前时间-T” 之前

    (1). 如果是，则该页面为被置换的页面;

    (2). 如果不是，记录当前所有被扫描过页面的最后访问时间里面的最小值。扫描下一个页面并重复1、2

4.页面置换算法小结

十二.内存映射文件

1.基本思想

  • 进程通过一个系统调用(mmap)将一个文件(或部分)映射到其虚拟地址空间的一部分，访问这个文件就象访问内存中的一个大数组，而不是对文件进行读写

  • 在多数实现中，在映射共享的页面时不会实际 读入页面的内容，而是在访问页面时，页面才 会被每次一页的读入，磁盘文件则被当作后备存储

    是利用了虚拟存储机制中的缺页异常，来把相应文件内容读入内存的

  • 当进程退出或显式地解除文件映射时，所有被修改页面会写回文件

2.支持写时复制技术

例如:两个进程共享三个页，每页都标志成写时复制

当某一个进程试图要改变其中一个页面的内容时，它要做一个写操作，那么和只读就产生了冲突，就会产生Page Fault。进入了操作系统后，操作系统检查出它是一个写时复制操作，就会在内存里另开辟一个页面把相应的内容写到这个页面里。而新复制的这个页面对于执行写操作的这个进程来讲是一个私有的，对于其他的进程是共享写时复制页面的进程，看不到这样一个结果。这是写时复制技术的一个基本的实现。

0%