operating system

存储器是计算机的重要组成部分,分为外存和内存。外存就是我们常见的磁盘,用来存储数据,即使断电也不会丢失。内存是 CPU 读写数据的地方,CPU 要想使用外存的数据,必须先将外存数据读取到内存后再使用。

操作系统中提及的存储器管理,其主要对象就是内存管理,而文件系统才会涉及到比较多的外存知识。

1. 多层结构的存储器结构

内存三要素:速度快,容量大、便宜。显然便宜限制了前面两个因素,因此提出了多层结构的存储器结构。一般分为三类:寄存器、主存、辅存。现在的计算机又细分了一些,如下

名字 类型
寄存器 CPU 寄存器
高速缓存 主存
主存储器 主存
磁盘缓存 主存
固定磁盘 辅存
可移动存储介质 辅存

越前面的速度越快,容量越小,价格越高。

  1. 可执行存储器

    寄存器和主存被称为可执行存储器,存放于其中的信息,CPU 可以通过一条指令(load 或者 store)就可以读取,而辅存需要通过 I/O 设备实现,这里就涉及了 I/O 中断,速度自然很慢(相差 3 个数量级)。我们存储管理主要讲可执行存储器管理,辅存知识归为设备和文件管理。

  2. 主存储器和寄存器

    主存储器 简称内存,用来保存进程运行时的程序和数据。一开始 CPU 是直接读取内存的数据或者指令运行的,后来 CPU 的执行速度远大于内存的读写速度,因此在中间加入了寄存器和高速缓存。常用的数据或指令放到寄存器和高速缓存中,CPU 从寄存器中读取数据,如果没有想要的数据,再从下一层存储器中读取。

    寄存器 具有和处理器相同的速度,但很贵,因此容量有限,主要用来存放处理机运行时的数据(运行指针、返回地址等等)。

  3. 高速缓存和磁盘缓存

    高速缓存 在第二层,因此访问速度比主存快,主要用来备份主存中比较常用的数据。以减少处理机对主存的访问次数,提高执行速度。层次结构的形成和程序执行的局部性原理有关,也就是 CPU 接下来执行的指令和需要的数据往往和当前指令或者数据相近。高速缓存可能分为好几层,但是原理都一样,因此这里合并为一层讲解。

    磁盘缓存 其实属于主存的一部分(而不是独立的一部分),主要存放一些常用的磁盘数据和信息。减少访问磁盘的次数。这里要区分于高速缓存,高速缓存是实际存在的。文件通常存储在磁盘中,要使用的时候会调入主存或者磁盘缓存。

2. 程序的装入和连接

用户程序要在系统中运行,必须先调入主存,然后再将其转变为一个可以执行的程序,一般经过以下步骤:

  1. 编译(Compiler):形成若干目标模块
  2. 链接(Linker):将编译后的若干目标模块和它们所需的库函数链接一起形成装入模块(Load Module)。使用 readelf 指令可以查看。
  3. 装入:由装入程序(Loader)将装入模块装入内存。

我们主要将程序(含数据)的链接和装入过程。编译交给编译器,例如 C 的编译器 gcc

2.1 程序装入

为了易于阐述,这里介绍无需链接的单个目标模块的装入过程(所有指令和数据都自己搞定了)。将该装入模块装入内存有三种方式

  1. 绝对装入方式(Absolute Loading Mode)

    • 环境:只适用于单道程序环境。
    • 事先知道程序驻留在内存的什么位置。

    • 绝对装入程序(Loader)按照装入模块中的地址,将程序和数据装入内存。
    • 程序中的逻辑地址与实际内存地址完全相同,不须对程序和数据的地址进行修改。
    • 特点:内存大小限制,能装入内存并执行的进程数大大减少。
  2. 可重定位装入方式(Relocation Loading Mode)

    • 环境:多道程序环境
    • 装入模块的起始地址通常都是从 0 开始的,程序中的其他地址也都是相对于起始地址计算的。
    • 根据内存的当前情况,将装入模块装入到内存的适合位置。
    • 地址变换通常是在装入时一次完成的,以后都不再改变,所以是静态重定位。
    • 特点:无需硬件支持;程序不能在内存中移动;要求程序的存储空间是连续的,不能把程序放在若干个不连续的区域中。
  3. 动态运行时的装入方式(Dynamic Run-time Loading)

    • 环境:多道程序环境
    • 程序在运行过程中在内存中的位置可能改变(对换功能中进程的换进换出),装入程序把装入模块装入内存后,并不立即把装入模块中的相对地址转换为绝对地址,而是把这种地址转换推迟到程序真正要执行时才进行
    • 特点:程序在内存中可以浮动,不要求整个应用程序占用连续空间;为使地址转换不影响指令的进行速度,这种方式需要一个重定位寄存器的支持。

2.2 程序的链接

源程序经过编译后,可得到一组目标模块。链接程序的功能就是将这组目标模块以及它们所需要的库函数装配成一个完整的装入模块。在对目标模块进行链接时,根据进行链接的时间不同,可把链接分成如下三种。

  1. 静态链接方式(Static Linking)

    在程序运行之前,先将各目标模块及它们所需的库函数链接成一个完整的装配模块,以后不再拆开。我们把这种事先进行链接的方式称为静态链接方式。例如下面三个目标模块

    目标模块 调用模块 起始地址变化
    A(0~L-1) {CALL B; return} 不变
    B(0~M-1) {CALL C; return} (L~L+M-1)
    C(0~N-1) { return; } (L+M~L+M+N-1)

    A、B 和 C 三个目标模块进行链接的时候,如果以 A 为基址进行链接,那么 B、C 的起始地址都会相应的改变,对应的外部调用符号都要变换为相对地址,然后将合成的一整个装入模块装入内存。

  2. 装入时动态链接(Load-time Dynamic Linking)

    • 用户源程序编译后所得到的一组目标模块,在装入内存时,采用边装入边链接的链接方式。

    • 若发生一个外部模块调用事件,将引起装入程序去找相应的外部目标模块,并将它装入内存。同时按照静态链接的方式修改目标模块中的相对地址。

    优点:1)便于修改和更新。由于目标模块分开存放,所以要修改和更新各目标模块是件非常容易的事。

    2)便于实现目标模块的共享。采用静态链接方式时,每个应用模块都必须含有其目标模块的拷贝,无法实现对目标模块的共享。如果采用装入时动态链接方式,OS 就很容易将一个目标模块链接到几个应用模块上,实现多个应用程序对该模块的共享

  3. 运行时动态链接(Run-time Dynamic Linking)

    在多数情况下,应用程序在运行时,每次要运行的模块可能是不相同的。典型例子就是错误处理用的目标模块,如果程序整个运行过程正常,就不会用到该模块

    这是对装入时动态链接的一种改进,将目标模块的装入推迟到程序执行时才进行,因此凡是执行过程没使用的目标模块都不会被装入内存。

    优点是不仅加快装入速度,还节省内存空间。

3. 连续分配存储管理方式

为了能够将用户程序装入内存,必须为它分配一定大小的内存空间。连续分配方式是最早出现的一种存储器分配方式(任何一种新事物的发展,都是由直接转化到抽象的,如果不理解新事物的发展历程,很难接受其抽象形式)。顾名思义,给一个用户分配一个连续的内存空间,代码或数据的逻辑地址相邻,体现在内存空间分配时物理地址的相邻。

连续分配方式可以分为四种:单一连续分配、固定分区分配、动态分区分配以及动态可重定位分配算法。

  1. 单一连续分配

    • 环境:单道程序环境
    • 一个用户独占机器,内存被分为系统区和用户区,用户区仅装有一道用户程序,这样也就不需要包含机构了,大不了重启电脑。
  2. 固定分区分配

    • 环境:多道程序环境

    • 整个用户空间划分为若干个固定大小的区域,每个分区只能装入一道作业,这是最早也是最简单的一种可运行多道程序的分区式存储管理方式

    • 若有空闲分区,从后备作业队列中选择一个适当大小的作业,装入该分区。

    • 划分分区的方法有两种

      分区大小相同:缺点是缺乏灵活性,程序太小浪费内存,程序太大装不进去。尽管如此,还是有些场合需要处理多个相同程序的时候,这种方法还是很实用简单的。

      分区大小不等:增加存储器分配灵活性。分配之前需要对常在该系统运行的作业大小进行调查统计,然后再适当分配。

    • 内存分配方式

      为了便于内存分配,通常将分区按其大小进行排队,并建立一张分区使用表如下

      分区号 大小(KB) 起址(K) 状态
      1 12 20 已分配
      2 32 32 已分配
      3 64 64 未分配
      4 128 128 已分配

      固定分区分配必然会造成存储空间的浪费,现在不怎么用了,但是还是要了解一下的。

  3. 动态分区分配

    • 数据结构:

4. 基本分页存储管理

内存离散分配方式:将一个进程分散地分配到许多不相邻接的分区中的内存分配方式。

  1. 页面

    逻辑空间分片。

    页面和物理内存块的区别是:逻辑和物理。

    页面大小一般为 4094 KB。

  2. 页表

    页号与块号之间的映射。

页表存放在内存中,每个进程一个。开始地址存在 PTR 寄存器中。

5. 虚拟存储

具有一次性、驻留性的存储器管理方法称为实存管理。

实存管理的缺点是逻辑空间不超过实际内存大小,同时存在的进程数目受限较大。

5.1. 定义

将大容量的外存作为内存的直接延伸,对内存、外存(交换区)实施统一管理。

虚拟存储器具有多次性和对换性。仅把进程的一部分调入内存即可运行。

5.2 页面分配

  1. 固定页面分配

    按比例、考虑优先权。

  2. 平均分配算法

  3. 可变页面分配

  4. 局部页面置换策略

  5. 全局页面置换策略

    缺页时,系统从空闲物理块中分配一物理内存,如果没有,将内存页置换到外存。

5.3 页面置换算法

  1. 最佳页面置换算法

    选择被置换的页面,将是永不使用的页面,或最长时间不适用的页面。

  2. 先进先出页面置换算法

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

  3. 最近最久未使用(LRU)页面置换算法

    选择最近最久未被使用的页面淘汰。利用移位寄存器实现

  4. clock 置换算法

    循环链表,如果为 1 则置零,如果为 0 换出。

  5. 改进型 clock 置换算法

    多了访问位 A 和修改位 M

    1. 都为零则是最佳算法
    2. 否则找 A 为零的,同时置 A 为零。