内存

内存可存放数据。程序执行前需要先放到内存中才能被 cpu 处理。–缓和cpu和硬盘之间的速度矛盾

逻辑地址和物理地址

• 逻辑地址（相对地址）：相对于进程的起始地址而言的地址
• 物理地址（绝对地址）：内存中的地址

从程序到程序运行

• 编译：将若干个源代码文件（.c） 经过编译后得到目标模块（.o），每个目标模块中都是从 0 开始的逻辑地址。
• 链接：将若个各目标模块以及用到的库函数链接到一起，得到完整的装入模块文件（.exe），形成完整的逻辑地址。
• 运行：由装入程序将装入模块装入到内存运行，得到装入模块在内存中的地址（物理地址），装入模块中数据的逻辑地址 + 模块物理地址 = 数据的物理地址

链接的两种方式

• 静态链接：链接时将所有目标模块和库函数连接到一起，得到完整的装入模块文件
• 动态链接：只将包含 main 函数的模块装入到内存，运行时再将需要用的模块装入到内存中

内存的划分方式

• 固定分区分配：预先将内存分成若干固定大小的分区，当有新的程序装入内存时
  • 将内存分成若干固定的大小相等的区域
  • 将内存分为若干固定的大小不相等的区域
• 动态分区分配：这种方式不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态建立分区。

操作系统需要什么样的数据结构来记录内存的使用情况 ？

• 空闲分区表
• 空闲分区链

非连续存储管理

• 基本分页存储管理

  • 将 内存空间 分为若干大小相等的分区(比如：每个分区大小$4KB$)，每个分区就是一个 页框（页帧、内存块、物理块、物理页面、$frame$）。每个 页框 有一个编号，即 页框号。页框号从 0 开始。
  • 将 进程的逻辑地址空间 也分为与 页框大小相等 的若干分区，每个分区也称为一个 页/页面（$page$），每个页面也有一个编号，叫做 页号，页号也是 从 0 开始。
  • 操作系统以 页框为单位为各个进程分配 内存空间，进程的每个页面分别放入一个页框中。也就是说，进程的页面和内存的页框有一一对应的关系。
  • 为了知道进程的每个页面在内存中存放的位置，操作系统为每个进程创建了一张 页表。存放于 $PCB$ （进程控制块）中。
  • __页表__逻辑上存放每个页面号对应的内存块号，实际物理上只需要存放内存块号，进程的地址是连续的，可以利用公式直接算出来。
  • 分页存储下如何实现逻辑地址到物理地址的转换：

    如果要访问逻辑地址A的物理地址
    1.确定A的页号P
    2.在页表中查询页号P的内存块号，获得内存块的起始地址
    3.确定逻辑地址A相对于页面的便移动量W

    A的逻辑地址=A在内村中所在内存块的起始地址+W

• 基本地址变换机构：用于在基本分页存储管理下，用于实现逻辑地址到物理地址的硬件机构
  • 基本地址变换机构可以借助进程的页表将逻辑地址转换为物理地址
  • 通常会在系统中设置一个 页表寄存器（PTR），存放 页表 在 内存中的起始地址F 和 页表长度M。
  • 程序未执行时，页表的地址和页表长度存放在进程控制块（PCB）中，当进程被调度时，操作系统内核会把它们放到页表寄存器中
• 具有 快表 的地址变换机构
  • 快表（TLB）是一种访问速度比内存快很多的 高速缓存（TLB），用来存放 最近访问的页表项 的副本，可以加速地址变化的速度。与此对象，内存中的页表称为慢表。

    1.CPU给出逻辑地址，由某个硬件算得页号、页内偏移量，将页号与快表中的所有页号进行比较。

    2.如果找到匹配的页号，说明要访问的页表项在快表中有副本，则直接从中取出该页对应的内存块
    号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。因此
    若快表命中，则访问某个逻辑地址仅需一次访存即可。

    3.如果没有找到匹配的页号，则需要访问内存中的页表，找到对应页表项，得到页面存放的内存块号，
    再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。因此
    若快表未命中，则访问某个逻辑地址需要两次访存(注意:在找到页表项后，应同时将其存入快表
    以便后面可能的再次访问。但若快表已满，则必须按照一定的算法对旧的页表项进行替换)

• 请求分页存储管理

• 与基本分页存储管理的区别：在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。
  • 与基本分页管理相比，请求分页管理中，为了实现“请求调页”，操作系统需要知道每个页面是否已经调入内存: 如果还没调入，那么也需要知道该页面在外存中存放的位置。
  • 当内存空间不够时，要实现“页面置换”操作系统需要通过某些指标来决定到底换出哪个页面:有的页面没有被修改过，就不用再浪费时间写回外存。有的页面修改过，就需要将外存中的旧数据覆盖，因此，操作系统也需要记录各个页面是否被修改的信息。
• 请求 分页存储管理的页表（请求页表） 需要包含：
  • 内存块号：页面所在内存中的块的编号
  • 状态位：是否在内存中
  • 访问字段：可记录最近被访问过几次，或记录最近访问的时间戳，供页面置换算法换出页面参考
  • 修改位：页面调入后是否被修改过（脏页）
  • 外存地址：页面在外存中存放的位置
• 缺页中断 机构
  • 在请求分页系统中，每当要访问的页面不在内存时，便产生一个缺页中断，然后由操作系统的缺页中断处理程序处理中断。此时缺页的进程阻塞，放入阻塞队列，调页完成后再将其唤醒，放回就绪队列。
  • 如果内存中有空闲块，则为进程分配一个空闲块，将所缺页面装入该块，并修改页表中相应的页表项。
  • 如果内存中没有空闲块，则由页面置换算法选择一个页面淘汰，若该页面在内存期间被修改过，则要将其写回外存。未修改过的页面不用写回外存。
  • 缺页中断是因为当前执行的指令想要访问的目标页面未调入内存而产生的，因此属于 内中断
• 页面置换 算法
  • 最佳置换算法（OPT）：每次选择淘汰的页面是以后永不使用，或者未来最长时间没被访问的页面，保证缺页率最低。
  • 先进先出置换算法（FIFO）：每次选择淘汰的页面是最早进入的页面
  • 最近最久未使用置换算法（LRU）：每次淘汰的页面是内存中最久没有使用的页面 “废材，花这么多精力养着你，一点用都没有”
  • 时钟置换算法：
• 页面分配、置换策略
  • 驻留集：请求分页存储管理中给进程分配的内存块的集合。在采用了虚拟存储技术的系统中，驻留集合的大小一般小于进程的总大小。
  • 固定分配:操作系统为每个进程分配一组固定数目的物理块，在进程运行期间不再改变。即，驻留集大小不变
  • 可变分配:先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况做适当的增加或减少即，驻留集大小可变
  • 局部置换:发生缺页时只能选进程自己的物理块进行置换。
  • 全局置换: 可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程。

    固定分配局部置换:系统为每个进程分配一定数量的物理块，在整个运行期间都不改变。若进程在运
    行中发生缺页，则只能从该进程在内存中的页面中选出一页换出，然后再调入需要的页面。这种策略
    的缺点是，很难在刚开始就确定应为每个进程分配多少个物理块才算合理。 采用这种策略的系统可
    以根据进程大小、优先级、或是根据程序员给出的参数来确定为一个进程分配的内存块数)

    可变分配全局置换:刚开始会为每个进程分配一定数量的物理块。操作系统会保持一个空闲物理块队
    列。当某进程发生缺页时，从空闲物理块中取出一块分配给该进程:若已无空闲物理块，则可选择-
    个未锁定的页面换出外存，再将该物理块分配给缺页的进程。采用这种策略时，只要某进程发生缺页
    都将获得新的物理块，仅当空闲物理块用完时，系统才选择一个未锁定的页面调出。被选择调出的页
    可能是系统中任何一个进程中的页，因此这个被选中的进程拥有的物理块会减少，缺页率会增加。

    可变分配局部置换:刚开始会为每个进程分配一定数量的物理块。当某进程发生缺页时，只允许从该
    进程自己的物理块中选出一个进行换出外存。如果进程在运行中频繁地缺页，系统会为该进程多分配
    1个物理块，直至该进程缺页率趋势适当程度:反之，如果进程在运行中缺页率特别低，则可适当减
    少分配给该进程的物理块。

    可变分配全局置换:只要缺页就给分配新物理块
    可变分配局部置换:要根据发生缺页的频率来动态地增加或减少进程的物理块

• 何时调入页面
  • 预调页：一般在程序运行前。根据空间局部性原理，一开始选定调入页面的周围页面也可能被调入，一起调入。
  • 请求调页策略：进程运行时，发现缺页再调页
• 从何处调页
  • 对换区：采用连续存储方式，速度更快
  • 文件区：采用离线存储方式，速度更慢
  • 对换区间足够大：运行时将数据从文件区复制到对换区，之后所有的页面调入，调出都是在内存和对换区之间进行
  • 对换区间不够大：不会修改的数据每次从文件区调入；会修改的数据调出到对换区，需要时再从对换区调入
  • UNIX：第一次使用的页面都是从文件区调入；调出的页面都写回对换区，再次使用从对换区调入

内存管理

操作系统作为系统资源管理者，当然也需要对内存进行管理

操作系统负责内存空间的 分配与回收

• 采用动态分区分配的方式对进程进行分配内存，回收内存时，会合并相邻的空闲分区，合并成更大的内存，减少外部碎片。合并后相对地址会发生变化，所以需要配合动态重定位确认新的物理地址。
• 动态分配算法
  • 首次适应算法
  • 最佳适应算法
  • 最坏适应算法
  • 邻近适应算法

操作系统需要提供某种技术从逻辑上对内存空间进行扩充(例如 虚拟技术 )

操作系统需要提供 地址转换 功能，负责程序的 逻辑地址 与 物理地址 的转换

• 绝对装入：在编译时，如果就知道程序将放到内存中的哪个位置（进程的地址），编译程序将产生绝对地址的目标代码。装入程序按照装入模块中，将程序和数据装入内存。也就是在装入前就知道位置了
• 静态装入：装入时，才知道在内存中的位置，给进程中的所有数据的地址加上 物理地址（进程在内存中的地址）
• 动态装入：也叫 动态重定位。运行时才进行地址转换(现代操作系统)，，装入模块中数据的逻辑地址 + 模块物理地址 = 数据的物理地址。

操作系统需要提供 内存保护 功能。保证各进程在各自存储空间内运行，互不干扰

• 方法一：在 cpu 设置一对 上、下限寄存器，存放进程的上下限地址。进程的指令要访问某个地址时，cpu检查是否越界。
• 方法二：采用 重定位寄存器，和 界限寄存器 进行越界检查。重定位寄存器存放的是进程的起始物理地址。界限寄存器存放的是进程最大逻辑地址(偏移量)。

虚拟内存

传统存储管理方式的缺点

• 一次性:作业必须一次性全部装入内存后才能开始运行。这会造成两个问题作业很大时，不能全部装入内存，导致大作业无法运行;当大量作业要求运行时，由于内存无法容纳所有作业，因此只有少量作业能运行，导致多道程序并发度下降。
• 驻留性:一旦作业被装入内存，就会一直驻留在内存中，直至作业运行结束。事实上，在一个时间段内，只需要访问作业的一小部分数据即可正常运行，这就导致了内存中会驻留大量的、暂时用不到的数据，浪费了宝贵的内存资源。

虚拟内存的定义

• 基于局部性原理，在程序装入时，可以将程序中很快会用到的部分装入内存，暂时用不到的部分留在外存就可以让程序开始执行
• 在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然继续执行程序
• 若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存
• 在操作系统的管理下，在用户看来似乎有一个比实际内存大得多的内存，这就是虚拟内存

虚拟内存有一下三个主要特征:

• 多次性:无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存
• 对换性:在作业运行时无需一直常驻内存，而是允许在作业运行过程中，将作业换入、换出。
• 虚拟性:从逻辑上扩充了内存的容量，使用户看到的内存容量，远大于实际的容量。

如何实现虚拟内存技术

• 虚拟内存技术，允许一个作业分多次调入内存。如果采用连续分配方式，会不方便实现。因此,虚拟内存的实现需要建立在离散分配的内存管理方式基础上。比如分页存储管理
• 与传统非连续存储主要区别：在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。