文章目录

程序的链接与装入

程序的装入

目的：是将代码装入内存准备执行

  1. 绝对装入方式
  2. 可重定位装入方式：
  3. 动态运行时的装入方式：增加一个重定位寄存器，通过硬件完成地址的修正。真实地址等于逻辑地址+重定位寄存器上的地址

程序的链接

目的：将目标模块相对独立的地址空间合并成一个地址空间。

​

  1. 静态链接方式
    • 对相对地址进行修改
    • 变换外部调用符号
  2. 装入时动态链接
  3. 运行时动态链接

连续存储分配方式

目的：给每一个程序分配一片连续的存储空间，容量为程序运行时所需的最大空间。

指标：碎片率，越小越好。

单一连续分配

内存分为系统区和用户区

  • 用户区一次只能装入一个程序运行
  • 系统区装入操作系统

固定分区分配方式

将内存划分成固定数目的区域，如图所示：

为了实现内存的管理，需要建立固定分区表（数组实现）：

程序的大小和分区大小不能完全匹配，所以需要分配大于等于程序大小的内存，分区中浪费的空间称为内碎片

动态分区分配（***）

操作系统不预设固定数目分区，按照程序内存需求为其划分，内存中分区数目动态变化。

数据结构：

分配算法：

  • 首次适应算法：空闲分区以地址递增的顺序排列，每次从链首开始顺序查找，直到找到一个大小能满足要求的空闲分区为止。然后再按照程序的要求大小，从该空闲分区中划分出一块内存空间给请求者，余下的空闲部分仍留在空闲链表中。特点是低端或高端地址空间被频繁使用。
  • 循环首次适应算法：在首次适应算法的基础上，每次查找时从上次找到空闲分区的下一个空闲分区开始查找。特点是空闲分区使用均匀，但是会缺乏大的空闲分区。
  • 最佳适应算法：能满足要求、又是最小的空闲分区分配给作业，避免"大材小用”。特点:分区按照大小顺序排列。
  • 最差适应算法：每次从空闲分区中选择最大的空闲分区分配给程序，以便切割剩余的空闲分区空间更大。

切割操作会产生一些空间过小，总是不会分配给程序，这些空间被称作外碎片。

### 可重定位分区分配

紧凑：通过移动程序，将外碎片合并一个大的空闲分区

基本分页存储管理方式

离散分配的基本单位是页

页表

解决了逻辑地址到物理地址的转换的问题：

  • 将程序逻辑地址空间划分成固定大小的页面;
  • 内存划分成等大小的页框;
  • 页表实现页面到页框的索引;
  • 页表项个数由程序的逻辑地址空间决定，页表项位数由页框起始物理地址位数决定。

记录了页面和页框号（每个页框的起始地址）的对应关系，如下图所示：

页表存储了页框的起始物理地址，需要一个连续的存储空间实现随机访问，对于逻辑地址相当于页号+页内偏移。

地址变换机构（***）

  • 先让页号与页表基址相加得到页框号
  • 再让页框号与页内偏移相加得到物理地址

基本分段存储管理方式

  • 离散分配的基本单位是端
  • 采用二维逻辑地址结构，由段号加段内偏移构成

段表

地址变换机构（***）

分页和分段的主要区别

  • 页是信息的物理单位；段是信息的逻辑单位。
  • 页大小固定；段大小不固定。
  • 分页采用一维线性逻辑地址，分段采用二维逻辑地址。

虚拟存储器（***）

概念：虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器，其逻辑容量由内存容量和外存容量之和决定，运行速度接近于内存速度,每位成本接近外存。

虚拟存储器实现方法的硬件支持

分页请求系统

  1. 请求分页的页表机制
  2. 缺页中断机构
  3. 地址变换机构

分段请求系统

  1. 请求分段的端表机制
  2. 缺段中断机构
  3. 地址变换机构

页面置换算法（***）

页面中断：发生页面的置换

最佳置换算法（理想化）

置换以后永不使用或者最长时间不使用的页面

  • 发生3次缺页中断和页面中断

先进先出页面置换算法

淘汰最先进入的页面，即选择在内存中驻留时间最久的页面予以淘汰。

最近最久未使用置换算法（LRU）

选择最近最久未使用的页面予以淘汰，即当前使用次数最少的页面。

实现方式：

  • 利用栈保存当前使用的各个页面的页面号,每当进程访问某页面时，便将该页面的页面号从栈中弹出，并将它压入栈顶。因此，栈底是最近最久未使用的页面。
  • 使用寄存器，每一次访问都会在寄存器加一，每次置换选择寄存器中次数最少的页面

clock置换算法

简单clock置换算法（最近未访问页面置换算法）
  • 将所有的页面组成一个循环链表,并为每个页面添加一个访问位A。
  • 当一个页面被访问时，将其A位设置为1。
  • 置换过程是从pointer开始，若该页面的A位为1,将其设置为0,并使pointer指向下一个页面，直到找到A位为0的页面;若该页面的A位为0，则将其置换出内存，并用换入的页面占用换出页面的页框，使pointer指向下一个页面。
  • 如果第一轮没有找到，则执行第二轮，由于第一轮将所有页面的A都设置为0，则一定能在第二轮找到
改进型clock置换算法

增加一个修改为M，页面状态可以分为四类：

  • 1类(A=0，M=0) ，未访问未修改;
  • 2类(A=0，M= 1)，未访问.已修改;
  • 3类(A=1，M=0)，已访问未修改;
  • 4类(A=1, M= 1) ，已访问已修改;

置换过程：

  1. 从pointer开始寻找1类页面，直到找到1类页面结束，或者扫描完一遍进入第II步。
  2. 从pointer开始寻找2类页面， 直到找到2类页面结束，或者扫描完一遍进入第I步。在本步每扫描完一个页面，须将页面的访问位修改为0。
  3. 重复l和II。(一 定可以找到置换的页。)

最近最少未使用（LFU）

在最近时期内选择使用次数最少的页面作为淘汰页

练习题目