认识操作系统

操作系统目标及作用

现代计算机中的计算机硬件:输入设备+输出设备+存储器+运算器+控制器

image-20200908184220320

  • 操作系统（Operating System，OS）：是管理计算机硬件与软件资源的系统软件，也是计算机系统的内核与基石。
    • 操作系统处理管理与配置内存
    • 决定系统资源供需的优先次序
    • 控制输入与输出设备
    • 操作网络与管理文件系统等基本事务
    • 提供一个让用户与系统交互的操作界面

操作系统的目标

  1. 方便性
  2. 有效性
  3. 可扩充性
  4. 开放性

操作系统的作用

  1. 作为用户与计算机硬件系统之间的接口：OS 处于用户与计算机硬件系统之间，用户通过 OS 来使用计算机系统。image-20200909195136530
  2. 作为计算机系统资源的管理者：管理计算机资源，这些资源包括 CPU、内存、磁盘驱动器、打印机等。
  3. 实现了对计算机资源的抽象：为其他软件软件提供服务，操作系统与软件进行交互，以便为其分配运行所需的任何必要资源。

操作系统发展过程

未配置操作系统计算机系统

  1. 人工操作
  2. 脱机输入/输出（Off-Line I/O）方式
    1. 脱机 IO：事先将装有用户程序和数据的纸带装入纸带输入机，在一台外围机的控制下，把纸带上的数据输入到磁带上。当 CPU 需要这些程序和数据时，再从磁带上高速地调入内存；
    2. 联机 IO：在主机的直接控制下进行输入/输出的方式，称为联机输入/输出（On-Line I/O）方式

单道批处理系统

  • 具体的工作过程是首先由监督程序将磁带上的第一个作业装入内存，并把运行控制权交给作业；该作业处理完时，又把控制权交给监督程序，再由监督程序把磁带的第二个作业调入内存等等。可以看成是串行的。

  • 优点：解决人机矛盾和 CPU 与 IO 设备速度不匹配问题，提高系统资源的利用率和系统吞吐量。

  • 缺点：不能充分的利用系统资源，现很少使用。

多道批处理系统

  • 用户所提交的作业先放在外存上，并排成一个队列（后备队列），由作业调度程序按照一定的算法，从后备队列中选择若干个作业调入内存，使其共享 CPU 和系统中的各种资源。同时在内存中装入若干程序，这样可以在 A 程序运行时，利用其 IO 操作而暂停的 CPU 空挡时间，再调度另一道程序 B 运行，同样可以利用 B 程序在 IO 操作时调用 CPU 空档调用程序 C 运行，使用多道程序交替运行，始终保持 CPU 忙碌的状态。
  • 优势：资源利用率高，使 CPU 始终处于忙碌的状态，提高内存的利用率，提高 IO 利用率；系统吞吐量大（CPU 和其资源始终保持忙碌的状态，仅在作业完成时或者运行不下去的时候才切换，系统开销小）。
  • 缺点：平均周转时间长，无交互能力。

分时系统（Time Sharing System)

分时系统概念

在一台主机上连接了多个配有显示器和键盘的终端并由此所组成的系统，该系统允许多个用户同时通过自己的终端，以交互方式使用计算机，共享主机中的资源。

分时系统特征

  1. 多路性：多用户同时在各自终端上使用同一 CPU。
  2. 独立性：用户可彼此独立操作，互不干扰，互不混淆。
  3. 及时性：用户在短时间内可得到系统的及时回答。
  4. 交互性：用户与系统进行人机对话。

实时系统（Real Time System）

image-20201219170212997

实时系统概念

系统能及时响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致地运行。

实时系统的类型

  1. 工业（武器）控制系统
  2. 信息查询系统
  3. 多媒体系统
  4. 嵌入式系统

实时任务的类型

  1. 周期性实行任务和非周期性实时任务。
  2. 硬实时任务和软实时任务。

实时任务特征

  1. 多任务：由于真实世界的事件的异步性，能够运行许多并发进程或任务是很重要的。多任务提供了一个较好的对真实世界的匹配，因为它允许对应于许多外部事件的多线程执行。系统内核分配 CPU 给这些任务来获得并发性。
  2. 抢占调度：真实世界的事件具有继承的优先级，在分配 CPU 的时候要注意到这些优先级。基于优先级的抢占调度，任务都被指定了优先级，在能够执行的任务（没有被挂起或正在等待资源）中，优先级最高的任务被分配 CPU 资源。换句话说，当一个高优先级的任务变为可执行态，它会立即抢占当前正在运行的较低优先级的任务。
  3. 任务间的通讯与同步：在一个实时系统中，可能有许多任务作为一个应用的一部分执行。系统必须提供这些任务间的快速且功能强大的通信机制。内核也要提供为了有效地共享不可抢占的资源或临界区所需的同步机制。
  4. 任务与中断之间的通信：尽管真实世界的事件通常作为中断方式到来，但为了提供有效的排队、优先化和减少中断延时，我们通常希望在任务级处理相应的工作。所以需要在任务级和中断级之间存在通信。

操作系统的基本特征

image-20200913173604664

并发（Concurrence）

  • 并行：指两个或多个事件在同一时刻发生；

  • 并发：指两个或多个事件在同一时间间隔内发生

  • 具体地说：并发指在一段时间内宏观上有多个程序在同时运行，但在单处理机系统中，每一时刻却仅能有一道程序执行，故在微观上这些程序是分时地交替执行。
    若计算机系统有多个处理机，这些可以并发执行的程序便可以被分配到多个处理机上，实现并行执行。即利用每一个处理机来处理一个可并发执行的程序。

  • 引入概念【进程】：指在系统中能独立运行 并作为资源分配的基本单位，它是由一组机器指令、数据和堆栈等组成的，是一个能独立运行的活动实体。

  • 在一个没有引入进程的系统中，属于同一个应用程序的计算机程序和 I/O 程序之间只能是顺序执行，也就是计算机程序执行告一段落后，才允许 I/O 程序执行；反之，在程序执行 I/O 操作时，计算程序也不能执行。———–为计算程序和 I/O 程序分别建立一个进程（Process）后，这两个程序就可以 并发执行。

image-20200913161252525

共享（Sharing）

  • 在 OS 环境下的资源共享或称为资源复用，指的是系统中的资源可供内存中多个并发执行的进程共同使用。 ——-在宏观上既限定了时间（进程在内存期间），也限定了地点（内存）。
  • 实现资源共享的两种方式
    • 互斥共享方式：系统中的某些资源：如打印机、磁带机等，虽然可以提供给多个进程（线程）使用，但是应规定在一段时间内，只允许一个进程访问该资源。
      ——-“临界资源”：一段时间内只允许一个进程访问的资源
    • 同时共享方式：系统中还有另外一些资源，允许在一段时间内由多个进程“同时”对它们进行访问。 ——这里的“同时”也就是前面讲的在微观下交替进行的。
      典型的例子：磁盘设备！

*并发和共享是 OS 的两个最基本的特征！没有并发和共享就谈不上虚拟和异步； *

虚拟（Virtual）

虚拟和异步是依赖于并发特性的。

所谓虚拟（Virtual）是指通过某种技术把一个物理实体变成为若干个逻辑上的对应物。
物理实体是实际存在的东西，逻辑实体是虚的，它并不存在，但是用户却感觉它存在。
用于实现虚拟的技术称为虚拟技术，在操作系统中利用了两种方式实现虚拟技术：时分复用技术和空分复用技术。

时分复用技术

时分复用技术概念:将资源在不同的时间片内分配给各进程以使该资源被重复利用，从而提高资源的利用率。如采用时分复用的虚拟处理机，能够在不同的时间片内处理多个用户的请求，从而使得用户感觉自己独占主机，而处理机在这期间也被充分的利用。

  1. 虚拟处理机技术：一台处理机，通过时分复用的方法，能实现同时（宏观上）为多个用户服务，亦即，利用多道程序设计技术，可将一台物理上的处理机虚拟为多台逻辑上的处理机 —- 虚拟处理机。
  2. 虚拟设备技术：通过时分复用的方法，将一台物理 I/O 设备虚拟为多台逻辑上的 I/O 设备，并允许每个用户占用一台逻辑上的 I/O 设备。

  • 这样可使原来仅允许在一段时间内由一个用户访问的设备（即临界资源），变为允许多个用户“同时”访问的共享设备

  • 当一种资源在时间上复用时，不同的程序或用户轮流使用它。时分复用技术通过利用处理及的空闲时间运行其他程序，提高了处理机的利用率

空分复用技术

  • 实质上就是每次只把用户程序的一部分调入内存运行，运行完成后将该部分换出，再换入另一部分到内存中执行，通过这样的置换功能，实现了用户程序的各个部分分时地进入内存运行。

  • 让同一个频段在不同的空间内得到重复利用。空分复用技术利用存储器的空闲空间分区域分存放和运行其他多道程序，以此来提高内存的利用率。

注意：采用分时复用技术，每台虚拟设备的平均速度必然等于或低于物理设备速度的 1/N，同理，采用空分复用技术，一台虚拟设备平均占用的空间必然等于或低于物理设备所拥有空间的 1/N

异步

  • 由于资源等因素的限制，使进程的执行通常都不可能“一气呵成”，而是以“走走停停”的方式运行。

    对于内存中的每个进程，在何时能获得处理机执行，何时又因提出某种资源请求而暂停，以及进程以怎样的速度向前推进，每道程序总共需要多少时间才能完成等等，都是不可预知的。

    进程是以人们不可预知的速度向前推进的，此即进程的异步性。

操作系统的主要功能

image-20201022162226039

处理机管理功能

操作系统关于进程方面管理任务有如下几种：进程控制，进程同步，进程通信，调度

进程控制

  • 为作业创建进程、撤销（终止）已结束的进程，控制进程在运行过程中的状态转换。

进程同步

  • 为了使多进程同时运行时协调，有两种方式
    • 进程互斥方式：进程在对临界资源进行访问时，应采用互斥方式。（临界资源加锁实现，关锁时禁止访问；锁开时允许访问。）
    • 进程同步方式：相互合作去完成共同任务的进程间，由同步机构对他们的执行次序加以协调。（信号量机制）

进程通信

  • 实现相互合作进程之间的信息交换。

调度

  1. 作业调度：从后备队列中按照一定算法选择出若干个作业，为他们分配运行所需资源，讲作业调入内存后，分别建立与之对应的进程，使它们成为可能获得处理机的就绪进程，并将他们插入就绪队列中。
  2. 进程调度：从进程就绪队列中按照一定算法选出一个进程，将处理机分配给他，并为他设置运行现场，使其投入执行。

存储器管理功能

内存管理主要功能：内存分配，内存保护，地址映射，内存扩充

内存分配

  1. 作用：为每道程序分配内存空间；提高存储器利用率，尽量减少内存空间碎片。
  2. 两种内存分配方式：
    1. 动态内存分配：每个作业所要求的基本内存空间也是在装入时确定的，但允许作业在运行过程中继续申请新的附加内存空间，以适应程序和数据的动态增长，也允许作业在内存中“移动”。
    2. 静态内存分配：每个作业的内存空间是在作业装入时确定的；在作业装入后的整个运行期间，不允许该作业再申请新的内存空间，也不允许作业在内存中“移动”。
  3. 内存分配机制应具有的结构和功能：内存分配数据结构、内存分配功能、内存回收功能。

内存保护

  1. 主要作用：确保每道用户程序都只在自己的内存空间内运行，彼此互不干扰；绝不允许用户程序访问操作系统的程序和数据；也不允许用户程序转移到非共享的其它用户程序中去执行。
  2. 内存保护机制：设置两个界限寄存器，分别用于存放正在执行程序的上界和下界。系统对每条指令所要访问的地址进行检查，如果发生越界，产生越界中断请求，停止该程序的执行。

地址映射

  • 程序的逻辑地址通常从 0 开始，而物理地址不从 0 开始，因此需要一个映射转换过程。主要功能即为：将地址空间的逻辑地址转换为内存空间与之对应的物理地址。

内存扩充

  1. 借助于虚拟存储技术，从逻辑上去扩充内存容量。
  2. 为了能在逻辑上扩充内存，系统必须具有内存扩充机制，用于实现下述各功能：
    1. 请求调入功能:允许在装入一部分用户程序和数据的情况下，便能启动该程序运行。在程序运行过程中，若发现要继续运行时所需的程序和数据尚未装入内存，可向 OS 发出请求，由 OS 从磁盘中将所需部分调入内存，以便继续运行。
    2. 置换功能：若发现在内存中已无足够的空间来装入需要调入的程序和数据时，系统应能将内存中的一部分暂时不用的程序和数据调至盘上，以腾出内存空间，然后再将所需调入的部分装入内存。

设备管理功能

  • 主要任务：
    • 完成用户进程提出的 I/O 请求；为用户进程分配其所需的 I/O 设备；
    • 提高 CPU 和 I/O 设备的利用率；提高 I/O 速度；方便用户使用 I/O 设备。
  • 为此，设备管理应具有缓冲管理、设备分配和设备处理等功能。

缓冲管理

  • CPU 运行的高速性和 I/O 低速性间的矛盾自计算机诞生时起便已存在。
    如果在 I/O 设备和 CPU 之间引入缓冲，则可有效地缓和 CPU 和 I/O 设备速度不匹配的矛盾，提高 CPU 的利用率，进而提高系统吞吐量。
    因此，在现代计算机系统中， 都毫无例外地在内存中设置了缓冲区，而且还可通过增加缓冲区容量的方法，来改善系统的性能。

设备分配

  • 设备分配的基本任务，是根据用户进程的 I/O 请求、系统的现有资源情况以及按照某种设备分配策略，为之分配其所需的设备。如果在 I/O 设备和 CPU 之间，还存在着设备控制器和 I/O 通道时，还须为分配出去的设备分配相应的控制器和通道。

设备处理

  • 设备处理程序又称为设备驱动程序。基本任务是用于实现 CPU 和设备控制器之间的通信，即由 CPU 向设备控制器发出 I/O 命令，要求它完成指定的 I/O 操作；反之，由 CPU 接收从控制器发来的中断请求，并给予迅速的响应和相应的处理。
  • 处理过程是：设备处理程序首先检查 I/O 请求的合法性，了解设备状态是否是空闲的，了解有关的传递参数及设置设备的工作方式。然后向设备控制器发出 I/O 命令，启动 I/O 设备去完成指定的 I/O 操作。

文件管理功能

  • 文件管理的主要任务是对用户文件和系统文件进行管理以方便用户使用，并保证文件的安全性。
    为此，文件管理应具有对文件存储空间的管理、目录管理、文件的读/写管理以及文件的共享与保护等功能。

文件存储空间的管理

  • 由文件系统对诸多文件及文件的存储空间，实施统一的管理。其主要任务是为每个文件分配必要的外存空间，提高外存的利用率，进而提高文件系统的存、取速度。
  • 为此，系统中应设置用于记录文件存储空间使用情况的数据结构，以供分配存储空间时参考，还应具备对存储空间进行分配和回收的功能。

目录管理

  • 目录管理的主要任务，是为每个文件建立一个目录项，并对众多的目录项加以有效的组织，以实现方便的按名存取。
  • 通常由系统为每个文件建立一个目录项。目录项包括文件名、文件属性、文件在磁盘上的物理位置等。由若干个目录项又可构成一个目录文件。即用户只须提供文件名， 即可对该文件进行存取。

文件的读/写管理

  • 该功能是根据用户的请求，从外存中读取数据；或将数据写入外存。由于读和写操作不会同时进行，故可合用一个读/写指针。

文件的共享与保护

  • 防止未经核准的用户存取文件；防止冒名顶替存取文件；防止以不正确的方式使用文件。

操作系统与用户之间的接口

  • 引题：image-20200913171719035

  • 包含关系:image-20200913172420937

用户接口

  • 为了方便用户直接/间接控制自己的作业，操作系统提供了命令接口，该接口又分为联机用户接口、脱机用户接口和图形用户接口3 种
联机用户接口
  • 用户说一句，系统做一句。用户可通过先后键入不同命令的方式，来实现对作业的控制，直至作业完成。
  • image-20200913170246761
脱机用户接口
  • 用户说一堆，系统做一堆。该接口是为批处理image-20200913170618948
图形用户接口
  • 采用图形化操作界面。

程序接口

  • 由一组系统调用命令（简称系统调用，也称广义指令）组成。
  • 系统调用的目的：请求系统服务
  • 系统调用/程序接口/程序接口 是操作系统提供给编程人员的接口 选 Cimage-20200913175632848
  • 系统调用 ≠ 库函数 选 Aimage-20200913175227658

注意事项:

image-20200913171920463

操作系统的运行机制与结构

运行机制

简单这么理解：一个程序要跑，需要调用一定的指令对吧？但是并不是所有指令都能为我们所用，有一些特定指令需要有特定的权限身份

也就是处理机状态，比如说 我要跑一个内核程序，需要调用特权指令，那么我能在用户态下进行吗？显然不可以，需要在核心态中执行。

指令

要明白操作系统的运行机制，首先需要有一个关于指令的相关知识储备

指令要与代码区分开，一个代码可能会被翻译成多个机器语言指令

简单来说，指令是让（CPU）能识别、执行的最基本命令（比如加法指令 就是让 CPU 进行加法运算）

处理机状态

由于有一些指令涉及到了内核，如果让操作计算机的用户去使用就很危险，于是我们设立了权限

将处理机分为两种状态，让一些指令只允许特定的状态处理机调用

image-20201219170801720

程序状态

有了两种处理机状态，相应的就有两种程序状态：

也就是内核程序和应用程序

image-20201219170850126

体系结构

操作系统内核

image-20201219172008907

  • 操作系统内核是计算机上配置的底层软件，是操作系统最基本、最核心的部分
  • 实现操作系统内核功能的那些程序我们称之为内核程序

一般来说操作系统的内核可分为以下几部分：

  1. 时钟管理：实现计时功能
  2. 中断处理：实现中断机制
  3. 原语
    1. 是一种特殊的程序
    2. 处于操作系统最底层，最接近硬件的部分
    3. 这种程序的运行具有原子性，也就是运行只能够一气呵成，不可中断
    4. 运行时间短，使用频繁
  4. 为系统资源进行管理的功能
    1. 进程管理
    2. 存储器管理
    3. 设备管理

传统 OS 结构

无结构 OS
  • OS 的各部分是以最基本的过程存在，每个过程都可随意地调用其他过程
模块化结构 OS
基本概念
  • 对 OS 的各部分经过了划分，行程若干个具有一定独立性和大小的模块

image-20200914164420048

模块独立性
  • 模块划分过小 → 降低本身复杂性，但会引起模块之间联系过多，造成系统混乱
  • 模块划分过大 → 增加模块内部复杂性，使内部联系增加
  • 内聚性：指模块内部各部分间联系的亲密程度。内聚性高 → 模块独立性强
  • 耦合度：指模块间相互联系和相互影响的程度。耦合度低 → 模块独立性强。
模块接口法的优缺点
  • 优点
    • 提高 OS 设计的正确性、可理解性和可维护性
    • 增强 OS 的可适应性
    • 加速 OS 的开发过程
  • 不足/存在的问题
    • 接口规定困难
    • 存在无序性
分层式结构 OS
分层式结构概念
  • 目标系统 An 和裸机系统 A0 之间有许多层次软件：A1，A2，A3….An-1，使 An 通过这几层最终能在 A0 上运行。

image-20200914170157431

分层结构的优缺点
  • 优点
    • 易保证系统的正确性：自下而上的设计方式使所有设计的决定都是有序的或者说是建立在较为可靠的基础上的，这样比较容易保证整个系统的正确性。
    • 具有易扩充和易维护性：在系统中增加、修改或替换一个层次中模块或整个层次时，只要不改变相应层次间接口，就不会影响其他层次，这就使得维护和扩充变得 easy。
  • 缺点
    • 系统效率降低：由于层次结构是分层单项依赖的，必须在每层间都建立层次间的通信机制，OS 执行一个功能就得由上到下穿越多层次，就会增加系统通信开销，从而导致系统效率降低。

客户端/服务端

客户/服务器模式由来、组成和类型
  • 客户机：每台客户机都是一个自主计算机，具有一定处理能力，客户进程在其上运行，平时处理一些本地业务，也可以发送一个消息给服务器用以请求某项服务
  • 服务器：通常是一台规模较大的机器，含有网络文件系统或数据库系统，应能为网上所有用户提供一种或多种服务。
  • 网络系统：用于连接所有客户机和服务器，实现他们之间通信和网络资源共享的系统
客户/服务器之间交互

一次完整的交互过程可以分成以下四步：

  1. 客户发送请求消息
  2. 服务器接收消息
  3. 服务器回送信息
  4. 客户机接收消息
客户/服务器模式优点
  1. 数据的分布处理和存储
  2. 便于集中管理
  3. 灵活性和可扩充性
  4. 便于改编应用软件

ps：经常会问到 在微内核 OS 中，为什么要采用客户/服务器模式？我们答客户/服务器模式的优点即可

微内核

为什么要有微内核，肯定是由于大内核不够好

image-20201219172044943

微内核 OS 的基本概念

微内核技术——把操作系统中更多的成分和功能放到更高的层次（用户模式）中去运行，而留下一个尽量小的内核，用它来完成操作系统最基本的核心功能。

基于微内核 OS 结构是建立在模块化和层次化结构的基础上的；

  1. 足够小的内核：微内核 ≠ 一个完整的 OS，含有：
    1. 与硬件处理紧密相关的部分
    2. 一些较基本的功能
    3. 客户和服务器之间的通信
  2. 基于【客户/服务器模式】image-20200914173409746
  3. 应用”机制和策略分离”原理
    1. 机制：是指在实现某一功能时的具体规定或说原则
    2. 策略：在机制的基础上，借助某些参数和算法，用以实现该功能的优化，或达到不同的目标
  4. 采用面向对象技术
微内核的基本功能

基于【机制与策略分离】的原理，将机制部分以及与硬件紧密相关的部分放入微内核中。由此微内核通常具有如下几个方面功能：

  1. 进程（线程）管理
  2. 低级存储器管理
  3. 中断和陷入处理
微内核操作系统的优点
  1. 提高了系统的可扩展性
  2. 增强了系统的可靠性
  3. 可移植性强
  4. 提供了对分布式系统的支持
  5. 新技术——融入了面向对象技术
微内核操作系统存在的问题
  1. 缺点:微内核操作系统的运行效率相较早期操作系统有所降低
  2. 改进方法:可以把一些常用的操作系统基本功能由服务器移入微内核中

进程和线程

前趋图和程序执行

前趋图

  • 前趋图(Precedence Graph)是指一个有向无循环图，可记为 DAG，用于描述进程之间执行的先后顺序

程序执行

程序顺序执行

  • 特征：
    • 顺序性：所谓顺序性是指，处理机严格的按照程序所规定的顺序执行，一个操作的开始必须在其前一个操作结束之后。
    • 封闭性：所谓封闭性是指，程序在执行的时候独占全机的资源。
    • 可再现性：所谓可再现性是指，只要初始条件和运行环境系统相同，其运行结果一定是一样的。

程序并发执行

  • 事实上，只有不存在前趋关系的程序之间才有可能并发执行，否则无法并发执行

  • 特征：

    • 间断性：所谓间断性指的是，由于多个程序对资源的要求产生的制约性，而导致的某一个程序在运行时等待资源的情况。 比如有两个程序都需要使用打印机这个资源，如果其中的一个程序已经占用，而另一个必须等待。这样后者表现出来的就是程序运行时的间断性。
    • 失去封闭性：所谓失去封闭性指的是，由于多个程序并发执行会共享资源，从而导致各个程序运行环境会失去封闭性。
    • 不可再现性：所谓不可再现性是指相同的输入，由于资源的共享，导致最后的输出结果不同。

进程的描述

image-20201022161832422

进程的定义和特征

定义

  • 程序：是静态的，是一个存放在磁盘里的可执行文件，是一系列的指令集合

  • 进程：是动态的，是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。

    其中，进程实体包含三部分：程序段，相关的数据段和PCB。

  • 程序进程关系:一个程序多次执行会对应多个进程，比如说 QQ 可以登录三个账号。那么既然都是 QQ，那 OS 是怎么区分不同进程的呢？当进程被创建的时候，OS 会为该进程分配一个唯一的，不重复的身份证——PID（Process ID，进程 ID）image-20200916193516137

  • 进程控制块（PCB）：OS 需要记录进程 PID，分配了哪些资源，运行情况，那么这些信息需要记录到哪里呢？答案就是进程控制块——PCB。image-20200916192007658

    • 作用：PCB 的作用是使一个在多道程序环境下不能独立运行的程序（含数据）成为一个能独立运行的基本单位，一个能与其他进程并发执行的进程。下面是具体作用：
      • 作为独立运行基本单位的标志：在进程的整个生命周期中，系统总是通过 PCB 对进程进行控制的，亦即系统是根据 进程的 PCB 感知该进程的存在的，所以，PCB 是进程存在的唯一标志。
      • 能实现间断性运行方式
      • 提供进程管理所需要的信息
      • 提供进程调度所需要的信息
      • 实现与其他进程的同步与通信

特征

  • 主要由：动态性，并发性，独立性，异步性，结构性组成。

image-20200916193752881

进程的基本状态及转换

image-20201022161752742

进程的状态

进程状态有五种:创建状态，就绪状态，执行状态，阻塞状态，终止状态；其中就绪、执行、阻塞是三种基本状态。

创建态、就绪态

  • 创建状态:对于处于创建态的进程，当其获得了所需的资源以及对其 PCB 的初始化工作完成后，便可由创建态转入就绪态
  • 就绪状态：进程已经处于准备好运行的状态了，只需要 CPU 临门一脚便可以立即执行。

运行态

  • 运行态：指进程已经获 CPU，其程序正在执行的状态。在单处理机系统中，只有一个进程处于执行状态，而在多处理机系统中，有多个进程处于执行状态。

image-20200916195133485

阻塞态

  • 阻塞态：指正在执行的进程由于发生某事件（I/O 请求，申请缓冲区失败等）暂时无法继续执行时的状态，亦即进程的执行收到阻塞。image-20200916203322409

终止态

  • 终止态：即一个进程达到了自然结束点，或是出现了无法克服的错误，或是被操作系统所终结，或是被其他有终止权的进程所终结，它将进入终止状态。

    image-20200916204018353

进程的转换

三态模型

  • 基本的三态模型

image-20201213161914285

五态模型

  • 未引入挂起的五态模型:

image-20200916204307618

引起进程状态转换的具体原因如下：

  • NULL→ 新建态：执行一个程序，创建一个子进程。

  • 新建态 → 就绪态：当操作系统完成了进程创建的必要操作，并且当前系统的性能和虚拟内存的容量均允许。

  • 就绪态 → 运行态：进程被调度

  • 运行态 → 终止态：当一个进程到达了自然结束点，或是出现了无法克服的错误，或是被操作系统所终结，或是被其他有终止权的进程所终结。

  • 运行态 → 就绪态：运行时间片到；出现有更高优先权进程。

  • 运行态 → 阻塞态：等待使用资源；如等待外设传输；等待人工干预。

  • 阻塞态 → 就绪态：申请资源被分配，或等待的事件已经发生了

  • 就绪态 → 终止态：未在状态转换图中显示，但某些操作系统允许父进程终结子进程。

  • 阻塞态 → 终止态：未在状态转换图中显示，但某些操作系统允许父进程终结子进程。

  • 终止态 →NULL：完成善后操作。

七态模型

接下来，我们引入了两个操作：挂起和激活

当挂起操作作用于某个进程时，该进程将被将被挂起，意味着此时该进程处于静止状态；

假如进程正在执行，他将暂停执行。

假如进程原本就处于就绪状态，则该进程此时暂不接受调度。

与挂起操作对应的就是激活啦。

  • 引入挂起后的进程状态转换五态模型:

image-20201213161938789

  • 引入创建和终止——七态模型:

    image-20201005151351838

这里写图片描述

引起进程状态转换的具体原因如下：

  • 等待态—→ 挂起等待态：如果当前不存在就绪进程，那么至少有一个等待态进程将被对换出去成为挂起等待态；操作系统根据当前资源状况和性能要求，可以决定把等待态进程对换出去成为挂起等待态。
  • 挂起等待态—→ 挂起就绪态：引起进程等待的事件发生之后，相应的挂起等待态进程将转换为挂起就绪态。
  • 挂起就绪态—→ 就绪态：当内存中没有就绪态进程，或者挂起就绪态进程具有比就绪态进程更高的优先级，系统将把挂起就绪态进程转换成就绪态。
  • 就绪态—→ 挂起就绪态：操作系统根据当前资源状况和性能要求，也可以决定把就绪态进程对换出去成为挂起就绪态。
  • 挂起等待态—→ 等待态：当一个进程等待一个事件时，原则上不需要把它调入内存。但是在下面一种情况下，这一状态变化是可能的。当一个进程退出后，主存已经有了一大块自由空间,而某个挂起等待态进程具有较高的优先级并且操作系统已经得知导致它阻塞的事件即将结束，此时便发生了这一状态变化。
  • 运行态—→ 挂起就绪态：当一个具有较高优先级的挂起等待态进程的等待事件结束后，它需要抢占 CPU，，而此时主存空间不够，从而可能导致正在运行的进程转化为挂起就绪态。另外处于运行态的进程也可以自己挂起自己。
  • 新建态—→ 挂起就绪态：考虑到系统当前资源状况和性能要求，可以决定新建的进程将被对换出去成为挂起就绪态。

进程的组织

线性方式

  • 不论进程的状态如何，将所有的 PCB 连续地存放在内存的系统区。这种方式适用于系统中进程数目不多的情况。

链接方式

  • 系统按照进程的状态将进程的 PCB 组成队列，从而形成就绪队列、阻塞队列、运行队列等。image-20200919213505282

索引方式

  • 该方式是线性表方式的改进，系统按照进程的状态分别建立就绪索引表、阻塞索引表等。image-20200919213530758

进程控制

进程控制的主要功能是对系统中的所有进程实施有效的管理，它具有创建新进程，撤销已有进程，实现进程状态转换等功能；

简单来说，进程控制 → 实现进程状态转换。

image-20201022161725493

  • 简单的流程图：

    image-20201005155458987

OS 内核

image-20200919214807617

与硬件紧密相关的模块、各种常用的设备的驱动程序以及运行频率较高的模块，安排在紧靠硬件的软件层次中，将它们常驻内存，通常被称为OS 内核；也就是 OS 内核其实本质上是各个模块。

原语

  • 我们知道原语的执行具有原子性，它执行过程只能一气呵成，不允许被打断，那么为什么要一气呵成呢？下图即为解释，假如不一气呵成，就会导致操作系统某些关键的数据结构信息不统一，就会影响操作系统进行别的管理工作。image-20200919215018317
  • 如何实现原语的原子性呢？其实是利用了“关中断指令“和”开中断指令“;
  • CPU 执行了关中断指令后，不会再 check 中断信号，直到遇到了开中断指令才会再去 check；
  • 因此关——开中断之间的指令是连续的，不可中断的，这就实现了原子性；image-20200919215955758

进程的创建

创建原语：

  1. 申请空白 PCB
  2. 为新进程分配所需的资源
  3. 初始化 PCB
  4. 将 PCB 插入就绪队列

哪里会用到进程创建呢？

  1. 用户登录
  2. 作业调度
  3. 提供服务
  4. 应用请求

image-20200919220556546

进程的终止

终止/撤销原语:

  1. 从 PCB 集合中找到终止进程的 PCB
  2. 若该进程正在运行，立刻剥夺 CPU，将 CPU 分配给其他进程
  3. 终止其所有子进程
  4. 将该进程所拥有的所有资源还给父进程或操作系统
  5. 删除 PCB

哪里会用到进程终止呢？

  1. 正常结束：进程自己请求终止
  2. 异常结束：非法使用特权指令
  3. 外界干预：用户自己选择杀某进程

image-20200919222346641

进程的阻塞和唤醒

被什么事件所阻塞就会被该事件所唤醒

image-20200919222900878

进程的切换

切换原语:

  1. 将运行环境信息存入 PCB
  2. PCB 移入相应队列
  3. 选择另一个进程执行，并更新其 PCB
  4. 根据 PCB 恢复进程所需的运行环境

这里有一个地方：进程所需的运行环境是什么东西呢?

image-20200920180827278

首先回顾一下我们程序是如何运行的：是通过把我们的代码保存到硬盘然后转入内存，然后 CPU 去从内存中读取一条条指令，然后我们的程序就跑起来了。

那么 CPU 中有个东西 叫做寄存器。它们有不同的功能，比如可以存放下一条指令地址，也可以存放正在执行的指令，也可以保存暂时运算得到的结果；

然而我们知道寄存器并不是很专一的，他有可能会随时被其他的进程使用，那我们之前运算的结果啊，什么保存的指令啊，岂不是都不见了吗？

这个时候就会用到我们的 PCB 了，它能够保持关键的一些信息，也就是运行环境，这样等我们的寄存器又空闲下来了的时候，我们就可以继续我们未完成的指令啦。image-20200920181231409

进程同步

image-20201022160937233

进程同步与互斥

首先，我们回顾一下我们之前学的进程异步问题，由于并发执行的进程以各自独立，不可预知速度向前推进，我们所得到的结果往往也会不一样，而我们往往有时候需要控制一个事件的发生在一个事件前，那么就需要进程同步啦

同步也称为直接制约关系，是指为了完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调他们的工作次序而产生的制约关系。

image-20200924203323774

有进程同步就有进程互斥，那么进程互斥又是什么呢？

要明白互斥，就引入了一个概念：临界资源

  • 临界资源，即一个时间段内只允许一个进程使用的资源。对于该资源我们必须互斥的访问，也就是我访问，你不能访问，反之亦然；因此
  • 进程互斥，即指当一个进程访问某临界资源时，另一个想访问此临界资源的进程必须要等待，只有当我正在访问该资源的进程访问结束了，释放掉了，下一个进程才能去访问该资源。

image-20200924203831680

那么我们一般是如何进行对临界资源的访问的呢?image-20200924204737502

  • 进入区：负责检查是否可以进入临界区（上锁）
  • 临界区：访问临界资源的那段代码
  • 退出区：用于将临界区正被访问的标志恢复为未被访问的标志
  • 剩余区：做其他处理

ps：临界区是进程中访问临界资源的代码段；进入区和退出区是负责实现互斥的代码段；临界区也被称为”临界段“

同步机制遵循的规则

  • 空闲让进：多中选一
  • 忙则等待：互斥访问
  • 有限等待：避免死等
  • 让权等待：避免忙等

image-20200924205632915

硬件同步机制

让硬件同步即为进程互斥的硬件实现方法：中断屏蔽方法，TestAndSet，Swap 指令

image-20201022160746350

中断屏蔽方法

  • 在进入锁测试之前关闭中断，直到完成锁测试并上锁之后才能打开中断。

image-20200924211536165

TestAndSet

简称 TS 指令，也有称 TestAndSetLock 指令，或 TSL 指令

用 TS 指令管理临界区的时候，为每个临界资源设置一个布尔变量 lock；

用 lock 的布尔值就可以判断资源是否空闲，进程能否访问。

  • 优点:实现简单；适用于多处理机的环境
  • 缺点:不满足让权等待

image-20201005153906850

Swap 指令

有的地方称为 Exchange 指令，或 XCHG 指令；Swap 指令用硬件实现，不允许被中断

Swap 指令与 TS 指令在逻辑上其实差不多，但 Swap 需要两个参数，不需要返回值，TS 需要一个共享的变量实现互斥，因此在不同的地方就要用不同的方式去进行进程互斥。

image-20201005153942707

信号量

image-20201022160710930

信号量机制

image-20200927175523422

由于之前的措施方案无法实现进程的“让权等待”问题，因此我们引出了信号量这个概念进行解决；

image-20200927220306063

整型信号量

  • Dijkstra 把整型信号量定义为一个用于表示资源数目的整形量 S，它仅能通过 P\V 操作进行访问。（P\V 即 wait ＆ signal）这两个操作是原子操作，是不可以在执行过程中被中断的。
  • 整形信号量存在的问题:不满足让权等待原则

image-20201204172546935

记录型信号量

  • 对于每次的wait操作，意味着进程请求一个单位的该类资源，使系统中可供分配的该类资源数减少一个，因此描述为S→value–;当S→value < 0时，表 示该类资源已分配完毕，因此进程应调用block 原语进行自我阻塞，放弃处理机，并插入到信号量链表 S→list 中；
  • 对于每次的signal操作，意味着执行进程释放一个单位资源，使系统中可供分配的该类资源数增加一个，故S→value++操作表示资源数目+1。若+1 后还是S→value <= 0,表示在该信号量链表中仍有等待该资源的进程被阻塞了，故应该调用wakeup原语，将S→list 链表中的第一个等待进程唤醒。(被唤醒进程从阻塞态 → 就绪态)

image-20201005154049852

ps：记录型信号量可实现进程互斥、进程同步；如果出现了 P(S),V(S)的操作，除非默认说明，默认 S 为记录型信号量

信号量应用

image-20201022160633374

实现进程互斥

image-20201204172456487

  • 为使得多个进程互斥访问某临界资源【目的】，为该资源设置 互斥信号量【mutex】，初始值为 1
  • 将该资源置于 P、V 操作之间；
  • 注意：利用信号量机制去实现进程互斥时必须保证我们的 P\V 操作是成对出现的
    • 缺少 P 会导致系统混乱，不能保证对临界资源互斥访问
    • 缺少 V 将会使临界资源永远不被释放，导致临界资源永远不被释放，从而使因等待该资源的阻塞的进程不能被唤醒
实现进程同步
  • 进程同步：要让各并发进程按要求有序地推进

image-20200928160518569

现在 P1,P2 并发执行，由于存在异步性，二者交替推进次序无法控制，是不确定的；

假如我 P2 的代码 4 需要用到 P1 的代码 1、2、3 运行结果才能执行的话，我就得保证代码 4 是在代码 3 后执行；

此即进程同步问题：让本异步并发的进程互相配合，有序推进。

重点：在前操作之后执行 V（S），在后操作之前执行 P（S）；

技巧口诀：前 P 后 V

理解：信号量 S 表示某种资源，一开始没有这种资源；一开始的时候 P2 需要使用该资源，但是没有，只能由 P1 来产生（释放）该资源

image-20201204171002706

实现前趋关系

每一对的前趋关系都是一个进程同步的问题（为了保证一前一后的操作）

为了实现这个目标，我们需要做的事情

  1. 为每一对前趋关系各设置一个同步信号量
  2. 在【前操作】的之后相对应的同步信号量执行V
  3. 在【后操作】的之前相对应的同步信号量执行P

image-20201204171026404

管程

image-20201022160532798

引子

  • 为什么要引入管程？因为信号量机制存在一定的问题:编写程序困难，容易出错（那是肯定的，这么多 PV 操作，想不错都难）因此我们在 1973 年引入管程机制进行处理；

管程的定义

代表资源的数据结构以及由对该共享数据结构实施操作的一组过程所造成的资源管理程序共同构成了一个操作系统的资源管理模块——管程。

管程是一种特殊的软件模块，由以下部分组成：

  1. 局部于管程的共享数据结构说明；
  2. 对该数据结构进行操作的一组过程（就是函数）
  3. 对局部于管程的共享数据设置初始值的语句【对数据结构初始化的语句】
  4. 管程有一个名字

发现了吗，管程和我们面向对象的类有点相似——可以定义一些数据，可以定义一些对这些数据操作的函数，对属性初始化的语句。

管程的基本特征

  1. 局部于管程的数据只能被局部于管程的过程所访问
  2. 一个进程只有通过调用管程内的过程才能进入管程访问共享数据
  3. 每次仅允许一个进程在管程内执行某个内部过程

什么意思呢？通过1+2我们可以知道，假如我们要修改管程内的数据结构，我们只能够通过调用管程内封装好的方法（函数）去修改数据结构；而3 则实现了进程互斥；

管程中的条件变量

我们使用管程实现进程同步需要用到同步工具，如 wait，signal；

但仅仅有这两个是不够的，我们知道，每次仅能有一个进程进入管程，假如某进程在管程中被挂起或阻塞就得等很久了，那么解决这问题就引入了——条件变量 condition。

怎么用呢？管程中对每个条件变量以说明：condition x，y；条件变量的操作是 wait，signal；

每个条件变量保存一个链表，用以记录因为这条件变量所阻塞的所有进程，提供 2 个操作：

x.wait 和 x.signal

  • x.wait：正在调用管程的进程因为x 条件需要被阻塞或者挂起，调用x.wait将自己插入到 x 条件的等待队列上，并释放管程，直到 x 条件变化。此时其他进程可以使用该管程——让出了入口。
  • x.signal：若正在调用管程的进程发现 x 条件发生了变化，则调用x.signal，重新启动一个因 x 条件而阻塞或挂起的进程，如果存在多个这样的进程，则选择一个，如果没有，则继续执行原进程，而不产生任何结果。
    • 注意了 这与信号量机制的 signal 操作不能混为一谈，信号量中的 signal 需要 s++操作，信号量改变了。

管程解决生产者消费者问题

管程中设置条件变量和等待唤醒操作，以解决同步问题。（condition xxx）

image-20201204171155511

  1. 假如两个生产者进程并发执行，依次调用 insert 过程的话：
    1. 第一个生产者进程可以顺利执行完 insert 函数
    2. 假如在第一个生产者进程还未结束的时候，第二个生产者进程插入进来了，就会把第二个进程阻塞在 insert 函数后面，排队
  2. 假如两个消费者进程先执行，生产者进程后执行的话：
    1. 第一个进程进来，发现 count = 0，那么就执行 wait 操作，就等待在 empty 变量相关的队列中
    2. 同样的，第二个就排在了 empty 变量相关的队列中
    3. 此时假如有个生产者进程进来了，进行生产，把生产品放在了缓冲区当中，假如发现自己的产品是第一个产品，那么此时有可能有别的消费者进程在等待产品，就执行一个唤醒操作，唤醒一个消费者进程。
    4. 然后 count- -，同时检查拿走前缓冲区是否是满的，假如之前是满的，那么现在取走了一个，代表着可以再放一个（再由生产者生产一个），那生产者进程需要被唤醒了，就来一个 signal（full）操作。

Java 中类似管程的机制

Java 中，如果用关键字【synchronized】描述一个函数，那么这个函数同一个时间段只能被一个线程调用。

image-20201001164432414

经典的进程同步问题

生产者-消费者问题

问题描述

image-20201005154151145

问题分析
  • 缓冲区未空（有产品）V→P 消费者消费
  • 缓冲区未满 V→P 生产者生产

image-20200928204830509

问题的解法步骤
  1. 关系分析，找出题目中描述的各个进程，分析他们之间的同步、互斥关系
  2. 根据各进程的操作流程去确定 P、V 的大致顺序
  3. 设置信号量，根据题目条件设信号量初值
    1. 互斥信号量初值一般为 1
    2. 同步信号量的初值看对应的资源初值值（0/n…)
具体实现
  1. 设置好信号量
    1. 互斥信号量 = 1：实现对缓冲区的互斥访问
    2. 同步信号量empty = n：实现空闲缓冲区的数量
    3. 同步信号量full = 0：代表产品的数量，也即非空缓冲区的数量
  2. 分别在生产者，消费者中放置 P、V 操作（注意顺序，以及操作的哪个信号量）

image-20201204171241240

思考
  • 想一想 能不能改变相邻 P、V 操作的顺序呢？

image-20201005154232845

得出结论了：实现互斥的 P 操作必须放在实现同步的 P 操作之后；由于V 操作并不会导致进程阻塞，因此两个 V 操作顺序可以交换；

多生产者-多消费者问题

问题描述

image-20201204171306215

注意 这里的多生产者的多 代表的不是数量 而是多个类型

问题分析
  • 找出题目描述的各进程，分析它们之间同步、互斥关系；
    • 互斥关系:对缓冲区(盘子)的访问要互斥的进行
    • 同步关系：父亲放苹果，女儿才能取苹果；母亲放橘子，儿子才能取橘子；盘子为空时，父/母才能放水果，因此需要儿/女进行从盘子取水果；
  • 根据进程的操作流程确定 P、V 操作大致顺序
    • 实现互斥:在临界区前后分别 P、V
    • 实现同步:前操作后 V，后操作前 P
  • 设置信号量
具体实现
  • 实现互斥访问盘子:mutex = 1
  • 多少个苹果 apple = 0
  • 多少个橘子 orange = 0
  • 盘子中还能放多少水果 plate = 1

image-20201204171402041

以父亲和女儿举例：

父亲首先应该 P 盘子，查看是否为空，如果为空，则 V 苹果（苹果++)；女儿首先 P 苹果，查看是否准备好了，有的话就取出，V 盘子（盘子++)；为了保证互斥，必须在 P、V 操作之中加入对互斥信号量 mutex 的 P、V 操作。

思考

可不可以不要互斥信号量 mutex？

image-20201005153712342

由于缓冲区大小为 1，因此 orange，apple，plate 三者中最多只有一个是 1；这样的话最多只有一个进程的 P 操作不会被阻塞，可以顺利进入临界区，因此可以顺利执行；

那么假如缓冲区（plate）数量为 2 呢？

那么父亲和母亲都能访问盘子，有可能出现不同进程写入缓冲区的数据相互覆盖的问题；

得出结论:如果缓冲区的大小大于 1，那么就必须专门设置一个互斥信号量 mutex来保证互斥的访问缓冲区

吸烟者问题

问题描述

image-20201204171447979

问题分析
  • 找出题目描述的各进程，分析它们之间同步、互斥关系；
    • 同步关系:桌上有组合 1→ 第一个抽烟者取走；组合 2→ 第二个抽烟者取走；组合 3→ 第三个抽烟者取走
    • 互斥关系:桌子只有一个，可以理解为容量为 1 的缓冲区需要互斥访问
  • 根据进程的操作流程确定 P、V 操作大致顺序
  • 设置信号量

image-20201204171522562

具体实现
  • 桌上组合 1、2、3 分别为 offer1 offer2 offer3，他们的初值都是 0
  • 设置一个信号量 i，用于实现三个抽烟者轮流吸烟

image-20201010163817853

以 smoker1 为例，首先 P（offer1）检查是否有需要的组合 1，有的话就拿走去抽，并且告诉供给者抽完了，然后供给者 i++，p 一下 finish，并将下一个组合放在桌上然后 v 下一个组合；

读者-写者问题

问题描述

image-20201010165136258

问题分析
  • 找出题目描述的各进程，分析它们之间同步、互斥关系；
    • 互斥关系：写进程-写进程 写进程-读进程 这两者存在互斥关系。而读进程-读进程不存在互斥
  • 根据进程的操作流程确定 P、V 操作大致顺序
  • 设置信号量
    • 一个互斥信号量 RW：写者访问文件的前后执行 PV，读者访问前后执行 PV
    • 整型变量 count 记录当前有几个读进程在访问文件
    • 一个互斥信号量 mutex ：保证对 count 变量的互斥访问
    • 一个互斥信号量 w ：用于实现写优先

image-20201010165807840

具体实现

image-20201010171424288

哲学家进餐问题

问题描述

image-20201010171711073

问题分析
  • 找出题目描述的各进程，分析它们之间同步、互斥关系；
    • 互斥关系：五位哲学家与左右邻居对其中间筷子的访问是互斥的
  • 根据进程的操作流程确定 P、V 操作大致顺序
  • 设置信号量
    • 一个互斥信号量组 chopstick[5]：用于实现对五个筷子的互斥访问。其中哲学家编号[0…4]，各哲学家 i 的左边筷子编号为i，右边筷子编号为（i+1）%5

然而我们发现 这样子会导致死锁的现象

image-20201010172704302

具体分析

按照之前的方法会发生死锁现象，那我们怎么解决呢？

有三种方法:

  1. 最多允许四个哲学家同时进餐，这样可以保证至少有一个哲学家是可以拿到左右两只筷子的
  2. 要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子；偶数号哲学家相反。这种方法可以保证如果相邻的两个奇偶号哲学家都想吃饭的话，只有有其中一个可以拿起第一只筷子，而另一个因为拿不到第一个筷子就直接阻塞了。
  3. 仅当一个哲学家左右两只筷子都可用时才允许他抓筷子【这也是后面的破坏请求和保持条件 方法】

下面以第三种方法为例，进行解决

image-20201010174404648

进程通信

image-20201022161648794

进程通信概念

  • 进程通信是指进程之间的信息交换。
  • 进程所拥有的内存地址空间相互独立，换而言之，进程不能直接访问另一个进程的地址空间，然而有时候有需要信息交换，那该怎么办呢？OS 提供了一些方法给我们。

image-20201204171611497

共享存储

前提：两个进程对于共享空间的访问必须是互斥的。

  • 基于数据结构共享：各进程公用某些数据结构，实现各进程的信息交换：如生产者-消费者问题中的有界缓冲区。是低级通信方式。
  • 基于存储区共享：在内存中画一片共享存储区，数据形式和存放位置由进程控制而非 OS。是高级通信方式。

image-20201204171629840

管道通信

  • 【管道 pipe 文件】是指用于连接读写进程的一个共享文件，本质是内存空间中开辟的一个固定大小的缓冲区
  • 管道采取半双工通信，一个时间段内只能实现单向传输；
  • 进程互斥访问管道
  • 管道写满时，写进程的系统调用被阻塞；管道为空时，读进程的系统调用被阻塞
  • 没写满不准读，没读空不准写。
  • 管道数据被读出后被抛弃，意味着读进程最多只能有一个，不然可能会读错数据。

image-20201005154325305

消息传递

进程通过【格式化的消息】为单位，将通信的数据封装在消息中，通过 OS 提供的发送接收原语，在进程间进行消息传递，完成进程的数据交换。是一种高级通信方式。

  • 直接通信方式:发送进程利用 OS 提供的发送原语直接把消息发给接收进程/消息直接挂到接收方的消息队列中。

  • 间接通信方式/信箱通信方式:发送进程先发送到中间实体（信箱）中，接受进程再去接收，完成进程间的通信。

    image-20201005154353653

线程

image-20201022161600061

线程的概念和特点

  • 什么是线程?为什么要引入线程?

假设现在有三个进程，他们所占用不同的空间内存和系统资源；假如我们要切换进程的时候，需要用保存/恢复运行环境，还需要切换内存地址空间（更新快表、更新缓存）开销非常大，因此，人们引入了线程机制。

image-20201204171755001

  • 引入了线程之后，线程是CPU 调度的基本单位。一个进程里面可以包含多个线程。线程之间可以并发进行。
  • 但是进程依旧是资源分配的基本单位，从属一进程的各线程共享使用进程的资源。
  • 同一个进程内各个线程程间并发，不需要切换进程运行环境和内存地址空间，省时省力。

image-20201001180053003

引入线程后的变化

image-20201005154628052

线程的属性

image-20201005154719829

线程的特性与优点

  • 进程间并发，开销很大；线程间并发，开销很小

  • 引入线程机制之后，并发带来的系统开销降低，系统并发性提升

ps：从属于不同进程的线程间切换，也会导致进程间切换，开销也会很大。

  • 从属于同一进程的各个线程共享进程所拥有的资源。
  • 进程间通信必须请求操作系统服务（CPU 需要切换到核心态），开销大；同进程下线程通信，无需 OS 干预，开销更小；

image-20201001193612876

线程实现方式

用户级线程

image-20201204172035911

  1. 线程的管理工作是由谁完成的？
    1. 答 线程的管理工作由应用程序通过线程库来完成的，不是通过 OS 完成的
  2. 线程切换是否需要 CPU 从用户态转换为内核态?
    1. 答 在用户态下，由应用程序通过线程库就可以进行线程切换了
  3. OS 是否能意识到用户级线程的存在?
    1. 答 意识不到，只有用户能意识到有多个线程
  4. 用户级线程有什么优点和缺点？
    1. 答 优点：用户级线程的切换在用户态可以完成，不需要切换到核心态，系统开销小，效率高
    2. 缺点：假如其中某一个线程被阻塞了，其他线程都会被阻塞，并发度不高；

内核级线程

image-20201204172104616

  1. 线程的管理工作由谁来完成?
    1. 答 由 OS 内核完成
  2. 线程切换是否需要 CPU 从用户态转换到内核态？
    1. 答 由于线程调度、切换工作由内核负责，因此在内核级线程的线程切换时需要从用户态转换到内核态的。
  3. OS 能否意识到内核级线程的存在?
    1. 答 OS 会为每个内核级线程建立对应 TCB，然后通过 TCB 对线程进行管理，因此，OS 能够意识到内核级线程的存在
  4. 内核级线程的实现方式的优缺点？
    1. 答 优点:内核级线程是处理机调度的基本单位，而进程只作为资源分配的基本单位；因此在多核 CPU 中，这几个线程可以被分配在多个不同 cpu 中并发执行，其中一个线程被阻塞了，其他的也能正常执行；
    2. 缺点:一个用户进程会占用多个内核级线程，线程切换由 OS 内核完成，由于用户态到核心态的转换需要开销，因此线程管理成本高，开销大。

多线程模型

  • 一对一模型

image-20201204172255596

  • 多对一模型

操作系统只能看的见内核级线程，因此只有内核级线程才是处理机分配的单位

image-20201204172233221

  • 多对多模型

image-20201003171220652

处理机调度与死锁

处理机调度

image-20201022161521827

调度基本概念

  • 当有一堆任务需要处理，但由于资源有限，这些事情没法同时处理。这就需要确定某种规则来决定处理这些任务的顺序，这就是调度所研究的问题，简单来说就是：按照某种算法选择一个进程将处理机分配给他

image-20201204172349110

处理机调度的层次

高级调度

image-20201005154801232

  • 高级调度/长程调度/作业调度，调度对象为作业；

  • 高级调度主要用于多道批处理系统中，什么是多道批系统呢？虽然前面讲过了 再复习一遍吧：

    image-20201005144635558

  • 高级调度根据某种算法/一定的原则从处于后备队列的作业中挑选一个/多个作业，分配内存等资源，建立 PCB，使他们获得竞争处理机的权利。

  • 高级调度是外存与内存之间的调度，每个作业只调入一次，调出一次。调入时创建相应 PCB，作业调出时又撤销 PCB。由于调出的时机一定是作业运行结束的时候，因此高级调度主要是解决调入的问题。

中级调度

image-20201005154819601

  • 中级调度/内存调度，引入这个调度的目的是为了提高内存的利用率和系统的吞吐量。

  • 引入虚拟存储技术后，将那些暂时不能运行的进程调至外存等待，此时进程的状态称为：就绪驻外存状态（挂起状态），等它们已具备运行条件且内存又稍有空闲时，由中级调度决定，重新调入内存，并修改状态为就绪状态，挂在就绪队列上等待。

    ps：PCB 并不会一起被调到外存，而是常驻内存。OS通过内存中的 PCB保持对各进程的监控和管理。

低级调度

image-20201005151550183

  • 低级调度/进程调度/短程调度：调度对象是进程（或内核级线程）；
  • 主要功能是根据某种算法/方法/策略，决定就绪队列中哪个进程应该获得处理机，将处理机分配给它。
  • 这种调度方式是 OS 中最基本的一种调度，在多道批、实时和分时三种类型 OS 中必须配置这级调度；
  • 低级调度的频率很高，一般几十毫秒一次；

三种调度方式的联系、对比

image-20201005152354921)image-20201005152256817

进程调度

进程调度的时机

image-20201005160523382

  • 这个地方有人会说:那么进程处于临界区时，不能进行处理机调度咯? 这个说法是错的 为什么呢？

    • 临界资源：一个时间段内只允许一个进程使用的资源，各进程需要互斥地访问临界资源。
    • 临界区：访问临界资源的那段代码
    • 内核程序临界区：一般是用来访问某种内核数据结构的（比如进程的就绪队列，由各就绪队列 PCB 租成）

    image-20201005160815845

进程调度的方式

非剥夺调度方式

image-20201005161431904

在采用这种方式时，可能引起进程调度的因素归结为:

  1. 正在执行的进程运行完毕，或因发生某事件而使其无法再继续执行；
  2. 正在执行中的进程因提出 I/O 请求而暂停执行；
  3. 在进程通信/同步过程中，执行某原语操作；
剥夺调度方式

image-20201005161437212

抢占并非是任意的，必须遵循一定原则。包括：

  1. 优先权原则：指允许优先级高的新进程抢占当前进程的处理机；
  2. 短进程优先原则：指允许新的短进程可以抢占当前长进程的处理机；
  3. 时间片原则：即各进程按时间片轮转运行时，当正在执行的进程一个时间片用完时，便停止该进程的执行而重新进行调度；

进程调度的切换与过程

image-20201005162732619

调度算法

调度算法的评价指标

image-20201022161204191

CPU 利用率

image-20201005163718195

系统吞吐量

image-20201005163838042

周转时间

image-20201005164349602

  • 对于每个用户而言，都希望自己作业的周转时间短一点，然而对于 OS，则向作业周转时间平均值小；那么引入了概念：带权周转时间，平均带权周转时间；

    image-20201005164734068

等待时间

image-20201005165031694

响应时间

image-20201005165627506

调度算法种类

image-20201022161053467

image-20201022161135651

FCFS-先来先服务算法

  • FCFS 例题：

    image-20201007173555912

SJF-短作业优先算法

image-20201007174950265

HRRN-高相应比优先算法

image-20201007175748653

  • HRRN 例题：

image-20201007180105263

RR 时间片轮转调度算法

image-20201008150220842

补充:

  • 时间片太大的影响：如果时间片太大，使得每个进程都可以在一个时间片内完成，则时间片轮转调度算法会退化为先来先服务调度算法，并且会增大进程响应时间。因此时间片不能太大。
  • 时间片太小的影响：如果时间片太小，我们知道，进程调度、切换是有时间代价的（保存、恢复运行环境），因此这样的话会导致进程切换过于频繁，系统会花大量时间来处理进程切换，从而导致实际用于进程执行的时间比例减少。
  • 因此时间片的大小应该取略大于一次典型交互的时间
优先级调度算法

image-20201008152411598

extra：

  • 就绪队列未必是只有一个的，可以按照不同优先级来组织；另外也可以把优先级高的进程排在更靠近对头的位置
  • 根据优先级是否可以动态改变，可将优先级分为静态优先级和动态优先级两种；
    • 静态优先级:创建进程时确定，之后一直不变
    • 动态优先级:创建进程时有一个初始值，之后根据情况动态地调整优先级
  • 如何合理设置各进程优先级呢？通常来说
    • 系统进程优先级高于用户进程
    • 前台进程优先级高于后台进程
    • I/0 进程优先级高于计算型进程
  • 若采用动态优先级，什么时候该调整？
    • 如果某进程在就绪队列中等待了很久，适当提升优先级
    • 如果某进程占用处理机运行了很久，适当降低优先级
    • 如果发现一个进程频繁进行 I/0 操作，适当提升优先级
多级反馈队列调度算法

image-20201008153258694

  • 例题：

    image-20201008153117802

死锁

image-20201022160457079

死锁的概念

image-20201009145923563

  • 简单来说，当一组进程发生死锁的情况下，这组死锁进程中的每个进程，都在等待另一个死锁进程所占有的资源，或者说每个进程所等待的事件是该组中其他进程释放所占有的资源。

死锁，饥饿，死循环

  • 死锁：各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象。
  • 饥饿：由于长期得不到想要的资源，某进程无法向前推进的现象。eg.SPF 算法中的如果短进程一直进来，长进程得不到处理机就会饥饿。
  • 死循环：某进程执行过程中一直跳不出某个循环的现象。有时是因为程序 bug，有时候是故意写出来的。(pv 操作)

image-20201009150936475

死锁产生的必要条件

image-20201009151437016

  1. 互斥条件：在一段时间内，某资源只能被一个进程所占有，若其他进程请求该资源，那就只能等待，直到占有该资源的进程用完释放
  2. 不可抢占条件：进程已获得的资源在未使用完之前不能被抢占，只能在进程使用完时由自己释放
  3. 请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放。
  4. 循环等待条件：在发生死锁时，必然存在一个【进程-资源】的循环链，即进程集合{P0,P1,P2…..Pn}中：P0 等待 P1 占用的资源，P1 等待 P2 占用的资源…..Pn 等待 P0 占用的资源；

image-20201009152417463

  • 对不可剥夺资源的不合理分配，可能导致死锁

死锁的处理方法

预防死锁

整体思路：破坏死锁产生的四个必要条件中的一个或几个

image-20201022160437390

破坏互斥条件
  • 互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁
  • 破坏策略：把只能互斥使用的资源改造为允许共享使用，则系统不会进入死锁状态。
  • 缺点：并不是所有的资源都可以改造成共享使用的资源，并且为了系统安全，很多地方还必须保护这种互斥性。因此很多的时候是无法破坏互斥条件的。

image-20201009153658886

破坏不可剥夺条件
  • 不可剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放
  • 破坏策略：
    • 当某个进程请求新的资源得不到满足的时候，必须立刻释放保持的所有资源，待以后需要时候再重新申请，即：即使某些资源尚未用完，也需要主动释放，从而破坏了不可剥夺条件。
    • 当某个进程需要的资源被其他进程所占有的时候，可以由操作系统协助，将想要的资源强行剥夺。这种方法需要考虑各进程的优先级。
  • 缺点：
    • 实现起来复杂
    • 释放已获得的资源可能造成前一阶段的失效，因此这种方法一般只适用于容易保存和恢复状态的资源（CPU）
    • 反复申请和释放资源增加系统开销，降低系统吞吐量
    • 使用第一个方案，表示只要暂时得不到某资源，前面所获得资源全都得需要放弃，以后再申请。假如这种情况常发生，进程会饥饿。

image-20201009154244423

破坏请求和保持条件
  • 请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放。
  • 破坏策略：采用静态分配方法，即进程在运行前一次申请完所需要的全部资源，在它资源尚未满足前，不让它投入运行。一旦投入运行，这些资源就一直归他所有，该进程就不会再请求别的任何资源。
  • 缺点：有些资源可能只需要用很短时间，因此如果进程的整个运行期间都一直保持着所有资源，就会造成严重的资源浪费，资源利用率极低。另外，该策略也可能导致某些进程饥饿。

image-20201009154702673

正因为这种方法缺点太明显，因此衍生出了第二种方法:

它允许一个进程只获得初期所需的资源后，便开始运行。在运行过程中逐步释放已分配给自己的、且用毕的全部资源，然后再请求新的所需资源。

破坏循环等待条件
  • 循环等待条件：存在一种进程资源的循环等待链，链中每个进程已获得的资源同时被下一个进程所请求
  • 破坏策略：采用顺序资源分配法
    • 给系统中资源编号
    • 规定每个进程必须按照编号递增的顺序请求资源，同类资源（编号相同资源）一次申请完
    • 一个进程只有占有了小编号资源才有资格申请大编号资源
  • 缺点:
    • 不方便添加新设备，有可能要重新分配编号嘛
    • 进程实际使用资源顺序可能与编号递增顺序不同，会导致资源浪费
    • 必须按规定次序申请资源，用户编程麻烦（谢谢你啊 还替我考虑那么多

image-20201009155649878

避免死锁

  • 用某种方法防止系统进入不安全状态，从而避免死锁（银行家算法）
安全序列

安全序列：是指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个安全序列，系统就是安全状态。当然，安全序列可能会有多个

image-20201009160734369

  • 不安全状态：如果分配了资源之后系统找不出任何一个安全序列，系统就进入了不安全状态。意味着之后可能所有进程都无法顺利执行下去了。为什么说是可能呢？因为假如存在进程提前归还了资源，那么系统也有可能重新回到安全状态。
  • 安全状态、不安全状态、死锁
    • 系统处于安全状态一定不会发生死锁
    • 系统处于不安全状态，有可能发生了死锁
    • 如果发生了死锁，一定处于不安全状态
银行家算法
  • 核心思想：在资源分配之前预先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应资源分配请求
  • 引例：

image-20201009221753621

image-20201009221808544

那么对于上述这个例子，OS 是怎么做的呢？

image-20201009222819458

  • 准备的数据结构:

    • 长度为 m的一维数组 Available表示还有多少可用资源
    • n*m 矩阵 Max表示各进程对资源的最大需求数
    • n*m 矩阵 Allocation表示已经给各进程分配了多少资源
    • Max - Allocation = Need 矩阵表示各进程最多还需要多少资源
    • 长度为 m的一维数组 Request表示进程此次申请的各种资源数

  • 银行家算法步骤:

    • 检查此次申请是否超过之前声明的最大需求数
    • 检查此次系统剩余的可用资源是否还能满足此次请求
    • 试探着分配，更改各数据结构
    • 用安全性算法检查此次分配是否会导致系统进入不安全状态

  • 安全性算法步骤：

    检查当前剩余的可用资源是否能够满足某个进程的最大需求，如果可以，就把该进程加入安全序列，并把该进程持有的资源全部回收

例题:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
     Allocation　　　Max　　　Available
 　　 ＡＢＣＤ　　  ＡＢＣＤ　　ＡＢＣＤ
 P1   ００１４　　  ０６５６　　１５２０　
 P2　 １４３２　　  １９４２　
 P3　 １３５４　  　１３５６
 P4 　１０００　　  １７５０
我们会看到一个资源分配表，要判断是否为安全状态，首先先找出它的Need，Need即Max(最多需要多少资源)减去Allocation(原本已经分配出去的资源)，计算结果如下：

   NEED
 ＡＢＣＤ
 ０６４２　
 ０５１０
 ０００２
 ０７５０
然后加一个全都为false的字段

 FINISH
 false
 false
 false
 false
接下来找出need比available小的(千万不能把它当成4位数 他是4个不同的数)

   NEED　　  Available
 ＡＢＣＤ　　ＡＢＣＤ
 ０６４２　　１５２０
 ０５１０<-
 ０００２
 ０７５０
P2的需求小于能用的，所以配置给他再回收

  NEED　　   Available
 ＡＢＣＤ　　ＡＢＣＤ
 ０６４２　　１５２０
 ００００　＋１４３２
 ０００２－－－－－－－
 ０７５０　　２９５２
此时P2 FINISH的false要改成true(己完成)

 FINISH
 false
 true
 false
 false
接下来继续往下找，发现P3的需求为0002，小于能用的2952，所以资源配置给他再回收

 　NEED　　    Available
 ＡＢＣＤ　　Ａ　Ｂ　Ｃ　Ｄ
 ０６４２　　２　９　５　２
 ００００　＋１　３　５　４
 ００００－－－－－－－－－－
 ０７５０　　３　12　10　6

依此类推，做完P4→P1，当全部的FINISH都变成true时，就是安全状态。

检测和解除死锁

  • 允许死锁的发生，不过 OS 会负责检测出死锁的发生，然后采取某种措施解决死锁

image-20201022160411857

检测死锁

  • 检测死锁的算法

简单来说就是依次消除与不阻塞进程相连的边，直到无边可消；但你要是非说严谨的话就是下面几步

  1. 在资源分配图中，找出既不阻塞又不是孤点的进程Pi （不阻塞—— 所申请的资源数量必须小于等于系统中已有空闲资源数量；不是孤点——与该进程至少有一个边相连）。然后消去它的所有请求边，分配边，使之变为孤点
  2. 进程 Pi 释放的资源，可以唤醒某些因为等待这些资源而阻塞的进程——原来阻塞进程可能变为非阻塞进程；
  3. 若剩下进程都能按照如上操作，消去图中所有的边，所有的进程结点都变成孤点，那称该图是 可完全简化 的；反之则称该图是 不可完全简化的
  • 死锁定理：如果某时刻系统的资源分配图是 不可完全简化的，那么此时系统死锁
解除死锁

解除死锁的方法：

  1. 资源剥夺法：挂起某些死锁进程，并抢夺它的资源，将这些资源分配给其他的死锁进程
  2. 撤销进程法/终止进程法：强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源
  3. 进程回退法：让一个或多个死锁进程回退到足以避免死锁的地步

内存

内存基础知识

image-20201022160329434

  • 什么是内存？内存是用于存放数据的硬件。程序执行前需要先放到内存中才能被 CPU 处理。

    image-20201013164419312

进程运行原理-指令

image-20201013165458590

由 x = x + 1 这个代码为例，它被编译后为三条指令；

第一条指令是让 CPU 进行数据传送，把内存单元为01001111的数据取出来取到地址为00000011的寄存器当中

第二条指令是让地址为00000011的寄存器上的数据+1

第三条指令是让 CPU 进行数据传送，把地址为00000011上的数据传送到地址为01001111的地方.

于是实现了 x = x + 1 操作

ps：上述指令不是严谨的二进制指令，仅供参考。

单位换算

由于后续的学习，经常要进行内存之间的运算，而我们的单位往往需要统一，那么接下来就讲讲单位换算

  • 1B=8b=2^3b

  • 1KB=1024B=2^10B

  • 1MB=1024KB=2^10^KB= 2^20^B

  • 1GB=1024MB = 2^10^MB= 2^20^KB= 2^30^B

  • 1TB=1024GB=2^10^GB= 2^20^MB= 2^30^KB= 2^40^B

逻辑地址

上面的指令操作提到了逻辑地址，那么什么是逻辑地址呢？

image-20201013171208992

eg. 0 号同学入住的是房号为 5（N=5）的房间，那么 3（M=3）号同学入住的就是 8（N+M=5+3=8）号房间；

写程序-运行程序

image-20201013172103828

  • 编辑：程序员编辑代码
  • 编译：代码编译成若干个目标模块（把高级语言翻译为机器语言）
  • 链接：由链接程序把 目标模块与所需库函数 连接在一起，形成一个完整的装入模块
  • 装入\装载：由装入程序将装入模块装入内存运行

链接

静态链接
  • 装入前链接成一个完整装入模块
  • 在程序执行之前，先将目标模块以及它们所需的库函数连接成一个完整的可执行文件（装入模块），之后不再拆开。

image-20201013191036437

装入时动态链接
  • 运行前边装入边链接
  • 将各目标模块装入内存时，边装入边链接的链接方式

image-20201013191117077

运行时动态链接
  • 运行时需要目标模块才装入并链接
  • 在程序执行中需要该目标模块时，才对它进行链接。其优点是便于修改和更新，便于实现对目标模块的共享。

image-20201013191223728

装入\装载

绝对装入
  • 编译时产生绝对地址
  • 地址由编译器产生，而不是 OS

image-20201013183938535

静态重定位
  • 装入时逻辑地址转换为物理地址/绝对地址
  • 转换过程由装入程序负责进行，装入程序是 OS 的一部分

image-20201013190449917

动态重定位
  • 运行时将逻辑地址转换为物理地址，并设置重定位寄存器
  • 采用动态重定位方式装入的作业，其地址变换工作是在每执行一条指令时完成的
  • 执行中允许OS 有条件地将其移动

image-20201013190842596

内存管理概念

image-20201022160304377

内存空间的分配与回收

  • OS 需要负责内存空间的分配与回收
    • 记录哪些内存区域已经被分配出去了，哪些又属于空闲状态
    • 当进程运行结束之后，将进程占用的内存空间回收
    • 内存这么大，有很多位置可以放置内存，那么又该怎么分配内存空间？

image-20201015211348937

连续分配管理方式

  • 连续分配：指为用户进程分配的必须是一个连续的内存空间

image-20201022160222327

单一连续分配
  • 在这种分法中，内存被分为系统区和用户区
  • 系统区：用于存放 OS 相关数据
  • 用户区：存放用户进程相关数据
  • 内存中只能有一道用户程序，用户程序独占整个用户区空间
  • 优点:实现简单，无外部碎片；
  • 缺点:只能用于单用户、单任务的 OS 中，有内部碎片，存储区利用率极低

image-20201017155052815

固定分区分配
  • 固定分区目的：为了能在内存中装入多道程序，且这些程序之间又不会相互打扰
  • 如何实现：将整个用户空间划分为若干个固定大小的分区，在每个分区中只装入一道作业
  • 固定分区分配有两种方法
    • 分区大小相等：缺乏灵活性，但适合用于用一台计算机控制多个相同对象的场合
    • 分区大小不等：增加灵活性，可以满足不同大小的进程需求。根据常在系统中运行的作业大小情况进行划分

image-20201017155506303

那么固定分区分配又是如何实现的呢？

  • 操作系统需要建立一个数据结构 —— 分区说明表，实现各个分区的分配与回收。每个表象对应一个分区，通常按照分区大小排列。每个表包含对应分区的：大小、起始地址、状态

    image-20201017162252431

  • 当某用户程序要装入内存的时候，由 OS 内核程序根据用户程序大小检索该表，从中找到一个能满足大小、未分配的分区。将之分配给该程序，然后修改状态为“已分配”

  • 优点：实现简单，无外部碎片

  • 缺点：

    • 当用户程序太大的时候，可能所有的分区都不能满足需求，此时不得不采用覆盖技术来解决，但这会降低性能
    • 会产生内部碎片，内存利用率低
动态分区分配

  • 动态分区分配又称为可变分区分配。

  • 这种分配方式不会预先划分内存分区，而是在进程装入内存的时候，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。

  • 系统分区的大小和数目是可变的

  • 缺点：会产生很多外部碎片，虽然可以用【紧凑】技术去处理，但紧凑的时间代价很高

    image-20201017163335963

下面思考三个问题：

  1. 系统要用什么样的数据结构记录内存的使用情况?

    通常使用 空闲分区表或者是空闲分区链

    空闲分区表：每个空闲分区对应一个表项

    空闲分区链：每个分区的起始部分和末尾部分分别设置前向指针和后向指针

    image-20201017163635023

  2. 当很多个空闲分区都能满足需求的时候，应该选择哪个分区进行分配呢？

    把一个新作业装入内存的时候，需要按照一定的动态分区分配算法，从空闲分区表（空闲分区链）中选出一个分区分配给该作业。

  3. 如何进行分区的分配与回收操作？

    分配:

    在上面的图示中，假如我们把一个 4mb 进程分配在了 20MB 处的话，我们只需要修改分区大小和起始地址即可

    image-20201017164819366

    假如我们分配在了 4MB 处的话，状态由空闲变为忙碌，则该行应该被删除，假如用空闲分区链的话，就把该节点删除

    image-20201017165013499

    回收：

    假设一开始有个进程占据了 14MB 处（10+4），跑完了需要回收，回收区的后面/前面有一个相邻的空闲分区，那么就合并

    image-20201017165628159

    假如回收区的前、后各有一个相邻的空闲分区的话

    例：在 20 和 10mb 中间有一个 4mb 的进程需要进行回收

    image-20201017165906305

    假如回收区的前后都没有相邻的空闲分区的话

    假设有一个进程占满了 14mb 的地方，此进程需要被回收

    image-20201017170134212

  • 内部碎片，外部碎片

    • 内部碎片：位于一个操作系统分配的用于装载进程的内存区域或页面内部的空闲区域。
    • 外部碎片：位于任何两个操作系统分配的用于装载进程的内存区域或页面之间的空闲区域，可以用紧凑技术进行解决

    image-20201017170829341

首次适应算法
  • 算法思想:每次都从低地址开始查找，找到第一个能满足大小的空闲分区
  • 如何实现:空闲分区以地址递增的次序排列，每次分配内存的时候顺序查找空闲分区链（or空闲分区表），找到大小能满足要求的第一个空闲分区

image-20201019154035820

最佳适应算法
  • 算法思想:动态分区分配是一种连续分配的管理方式，因此为各进程分配的空间必须也是连续的一整片区域。因此为了保证当大进程进来的时候有能连续的大片空间，可以尽可能多的留下大片空闲区，换句话说，就是大片的先不用，优先的把小空闲区给用了先。
  • 如何实现:空闲分区按容量递增次序链接，每次分配内存的时候顺序查找空闲分区链（or空闲分区表），找到大小能满足要求的第一个空闲分区
  • 缺点：会产生很多的外部碎片

image-20201019155759288

最坏适应算法

为了解决上述出现的 产生很多外部碎片 这个问题，我们衍生出了新的与之相对的算法：最坏适应算法

  • 算法思想：每次分配的时候优先使用最大的连续空闲区，使得分配后剩余的空闲区不会太小，方便使用；
  • 如何实现：空闲分区容量递减次序链接。每次分配内存时候按照顺序查找空闲分区链（or空闲分区表），找到大小能满足要求的第一个空闲分区。
  • 缺点：每次都选最大的分区进行分配，会导致较大的连续空闲区被迅速消耗掉，有大进程来了，就没内存空间可以用了。

image-20201019160300060

临近适应算法

我们每次算法讲到最后一个都是综合类的算法，结合了前面算法的特点综合的算法

不例外，我们这次也一样：临近适应算法

  • 算法思想:回想一下 ，首次适应算法是从链头开始找，低地址部分会出现小的空闲分区（外部碎片），而这些空闲分区部分我们往往用不上，因此会增加查找的开销。那么加入我们查找不从头开始，而是从上次查找结束的位置开始检索（因为后面是还没用到的部分，可以用的几率大点)，就能减少查找开销。
  • 如何实现：空闲分区以递增递增的顺序排列（可排成一个循环链表），每次分配内存的时候从上次查找结束的位置开始查找空闲分区链（or空闲分区表），找到大小能满足要求的第一个空闲分区。

image-20201019161625044

四种算法总结

image-20201019162144683

非连续分配管理方式

基本分页存储管理

image-20201022160151687

基本概念

  • 分页存储管理其实就是将一个进程的逻辑地址空间分成若干个大小相等的片；

    这些片称为页或者页面 从零开始编号

    相应的把内存空间分成与页面相同大小的若干个存储块 - 物理块/页框 同样 从 0 开始编号

image-20201019163349804

如何实现地址的转换

回想我们之前所学的，进程在内存中连续存放的时候，OS 是如何实现逻辑地址到物理地址的转换的呢？

是通过重定位寄存器去保存 装入模块存放的 起始位置 + 目标内存单元相对于起始位置的偏移量

我们就能得到该在物理地址（绝对地址）中，我们的目标存放的地址了，同理，我们把这种思想转移到了分页技术中地址的转换

结合之前的同学去住酒店问题，可以这么理解：

A 同学是个傻子，只知道自己要住在离 B 同学 X 个房号的房间，这个 X 就是偏移量，A 同学如何才能顺利的住进自己的房间呢？只需要 B 同学先找到自己的房间（起始位置），然后 A 同学就能顺藤摸瓜找到自己的房间啦。

以下面为例：

  • 页号：逻辑地址 / 页面长度 取整 （本题中：页号=80/50 = 1
  • 业内偏移量：逻辑地址 % 页面长度 （本题中：页内偏移量=80 % 50 = 30
  • 页面在内存中的起始位置：OS 用某种数据结构去进行记录的 （本题中一号页在内存中存放的起始位置=450

image-20201019165134603

为了方便计算页号、业内偏移量，页面大小一般取 2 的整数幂，那么接下来我们就来看看这种情况是什么样子的

红色部分前 20 位，表示了是第几页；（这里的前指的是从左往右数，如果严格按照二进制来说应该是后 20 位

后面 12 位是偏移值（这的后指的是从左往右数，如果严格按照二进制来说应该是前 12 位

加入我们知道了 N 号页在内存中的起始地址（假设为 X），那么我就知道我们已知的逻辑地址所对应的物理地址了

  • 结论:若每个页面大小为2^K B,用二进制数表达逻辑地址，那么末尾 K 位是页内偏移量。其余部分代表页号；

image-20201019170219137

逻辑地址结构

  • 分页存储管理的逻辑地质结构由：页内偏移量和页号组成

  • 若由 K 位表示页内偏移量，说明系统中一个页面大小是 2^K 个内存单元

  • 若由 M 位表示页号，说明系统中，一个进程最多允许 2^M 个页面

image-20201019171609549

页表

上述我们有个遗留问题，我们如何知道页号对应页面 在 内存中的起始地址呢？

其实是通过页表知道的，下面看看什么是页表

其实页表可以结合之前的住酒店问题一起理解：

还是那个傻子 A 同学，之前说了，他只知道自己住在某同学（假设 B 同学）的旁边 X 位，他需要知道 B 同学住哪才能找到自己的房间。而这个页表可以帮助 A 同学找到那个B 同学；

image-20201019202912635

  1. 一个进程对应一张页表

  2. 进程的每一页对应一个页表项

  3. 每个页表项由【页号】和【块号】组成

  4. 页表记录进程页面和实际存放的内存块之间的对应关系

  5. 物理内存大小 / 页面大小 = 内存块 / 页表项（多少个 也就是能分成多少页号）

  6. 页表项 × 页表项长度 = 页表的大小（页表在内存中占用的大小）

  7. 页表的大小 / 页面大小 = 页表项个数（页框个数）

  8. 页面的数目 = 进程的大小 / 页面的大小 = 逻辑地址表示的大小 / 页面的大小

  9. 每个页表项的长度是相同的，页号是隐含的

    这句话是说明意思呢？意思是说 我们能够通过页表存放的起始地址和页表项长度，就可以找到各页号所对应的页表存放的位置

image-20201019203053285

是不是说的很绕呢？那么可以这么理解：

  • 页 - 一个数组

    页的大小 表现为 2^N 这 N 位叫做页内偏移量 = 业内地址用 N 位来表示

  • 页表项 - 构成数组的最小单位，页号相当于下标，块号相当于存的值

  • 页表项 × 页表项大小 = 页表大小 等价于

    数组个数 × 单个元素大小 = 整个数组大小

  • 物理地址 / 页面大小 = 物理块的个数 → 知道了内存块号的取值范围

  • 逻辑地址 / 页面大小 = 页面的数目 → 知道了页号的取值范围

再结合那个例子理解：页面大小 决定了 页内偏移量（不是等于，因为是通过取余运算得到的），也就是距离 B 同学多远；而页号就是那个 B 同学了，B 同学只需要找到自己房间号，A 同学就能通过页内偏移量找到自己房间了。

基本地址变换机构

image-20201022160101385

  • 基本地址变换机构可以借助进程的页表将逻辑地址转换为物理地址
  • 通常会在系统中设置一个页表寄存器(PTR),存放页表在内存中的起始地址 F和页表长度 M；
  • 进程未执行的时候，页表的起始地址和页表长度放在进程控制块 PCB中，当进程被调度的时候，OS 内核会把他们放在页表寄存器中

（页面大小为 2 的整数幂）

设页面大小为 L，逻辑地址 A 到物理地址 E 的变换过程:

image-20201025172149372

  1. 计算页号 P和页内偏移量 W（以十进制为例：*页号 P = 逻辑地址 A / 页面大小 L ;页内偏移量 W = 逻辑地址 A % 页面大小 L * 但计算机实际运行的时候，逻辑地址结构是固定不变的，因此计算机硬件可以更快得到二进制表示的页号和页内偏移量）

  2. 比较页号 P和页表长度 M，如果P>=M，就产生越界中断，否则继续执行 （为什么等号也会算作越界中断呢?因为页号是从 0 开始的，而页表长度至少是 1，因此 P = M 也会中断哦 类似于数组越界）

  3. 页表中页表 P对应的页表项地址 = 页表起始地址 F + 页号 P * 页表项长度；取出该页表项内容 b，即为内存块号。

    页表长度：指的是这个页表中总共有几个页表项，就是有多少页

    页表项长度：指的是每个页表项占据了多大的存储空间

    页面大小：一个页面占多大的存储空间

  4. 计算物理地址 E = 内存块号 b * 页面大小 L + 页内偏移量 W ,用得到的物理地址 E 去访存

说了那么多，感觉是不是云里雾里的，知道了一堆名词，计算方式，但真正计算的时候仍然不会用？下面就来一道例题去实践一下

image-20201022154324120

  • 页号 P = 逻辑地址 A / 页面大小 L = 2500 / 1024 = 2 ； 页内偏移量 W = 逻辑地址 A % 页面大小 L = 2500 % 1024 = 452
  • 判断越界:页号 P 对应内存块号为 8 没越界
  • 物理地址 E = 内存块号 _ 页面大小 + 页内偏移量 = 8 _ 1024 + 452 = 8644 就是最后结果了
具有快表的地址变换机构

要去了解具有快表的地址变换机构前，首先要去理解一个概念 ： 局部性原理

  • 局部性原理
    • 时间局部性：如果执行了程序中的某条指令，那么不久之后这条指令很有可能被再次执行；如果某个数据被 访问过，不久之后该数据很可能被再次访问。（程序中存在大量循环）
    • 空间局部性：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问（许多数据在内存中是连续存放的）
    • 那么我们具有快表的地址变换机构与这局部性原理又有什么关系呢？我们上面介绍的基本地址变换机构中，每次要访问一个逻辑地址，都需要查询内存中的页表。而由于局部性原理，可能连续很多次查到的都是同一个页表项；当我们认识到了局部性原理之后，我们能否结合这个特性减少访问

在了解完局部性原理后，我们就可以正式开始学习快表了

  • 快表，又称联想寄存器（TLB）,是一种访问速度比内存块很多的高速缓冲寄存器（存放在更高速存储器中）

    用于存放当前访问的若干项页表项，以加速地址变换的过程

    与此对应，内存中的页表常被称为慢表（存放在内存中）

image-20201024151157653

下面我们根据上方图，仔细理顺一下 引入快表之后，地址的变换过程

  1. CPU 给出逻辑地址，由某硬件算出页号、页内偏移量，由地址变换机构自动地将页号 P送入高速缓冲寄存器，并将此页号与高速缓冲寄存器/快表中的所有页号进行比较
  2. 若其中有与此相匹配的页号，说明要访问的页表项在快表中有副本，于是直接从快表中读出该页对应的内存块号/物理块号，再将内存块号与页内偏移量拼接成物理地址，然后访问该物理地址对应的内存单元。（一次）
  3. 若其中没有与此匹配的页号，则需要访问内存中的页表，（第一次访问内存）找到对应的页表项，得到页面存放的内存块号/物理块号，访问该物理对应的内存单元（第二次访问内存）；（找到页表项后，应同时将其存入快表的一个寄存器单元中，假如联想寄存器已经满了，OS 必须找到一个老的且已经被认为是不再需要的页表项，将他换出来）
  4. 发现了吗？如果快表命中了，则访问某个逻辑地址只需要一次访存。如果没命中，则需要两次访存

image-20201024152935605

  • 有无快表的地址变换机构区别

    image-20201024153201118

两级页表

image-20201025152405530

  • 我们为什么要引入新的存储管理方式呢？往往都是因为之前的多多少少存在一点问题，那么与两级页表对应的就是单级页表了，单机页表存在什么问题呢？

    首先：页表必须连续存放，因此当页表很大的时候，需要占用多个连续页框

    其次：没必要让整个页表常驻内存，因为进程在一段时间内可能只需要访问几个特定页面

  • 解决方案：将页表进行分组，使每个内存块刚好放入一个分组（比如，页面大小 4KB，页表项大小 4B，那么可以存 1K 个页表项，那么把连续的 1K 个页表项认定为一组），把各组离散存放到各内存块中

    然后为离散分配的页表再额外建立一张页表，我们称之为:页目录表/外层页表/顶层页表

我们把中间这个大页表拆分成了左边这个小页表 1024 个页表项为一组

为什么要这么分呢？我们知道一个分页存储管理是把一个进程分成若干个页面然后存储 对吧？那么就有可能出现页号特别特别多的情况，因此我们把这些页号又再分一次，形成了一个二级页表；

image-20201024162203398

我们现在知道了 二级页表的来由了 那么二级页表又是如何实现地址转换的呢？

  1. 按照地址结构将逻辑地址拆成三个部分
    1. 一级页号
    2. 二级页号
    3. 页内偏移量
  2. 从 PCB 中读取页目录起始地址，根据一级页号查页目录表，找到下一级页表（二级页表）在内存中存放的位置
  3. 根据二级页号查表，找到最终想要访问的内存块号
  4. 结合页内偏移量得到物理地址

也就是需要 3 次的访存：第一次是访问内存中页目录表 第二次是访问内存中二级页表 第三次才是访问目标内存单元

有点套娃的意思；

img

下面来一道例题来看看一些细节问题

image-20201025152348367

基本分段存储管理

image-20201025202529712

分段

  • 进程的地址空间：按照程序自身的逻辑关系划分成了若干个段，每个段有一个段名

    编译程序会将段名转换为段号

    每段从 0 开始编制

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

image-20201025152836465

  • 分段细节

分段系统的逻辑地址结构由段号和段内地址（段内偏移量）所组成

image-20201025153507064

  • 段号的位数：决定了每个进程最多可以分几个段

  • 段内地址位数：决定了每个段的最大长度是多少

  • 以上图为例：段号与段内地址都是 16 位，因此每个进程最多有2^16=64K 个段，每个段的最大长度是2^16=64KB

    image-20201025153813924

    image-20201025153804900

段表

上面我们学习了基本分页存储管理，有提到页表一概念，那么与之对应的，我们的基本分段存储管理是否也有段表一概念呢？答案是肯定的

  • 段表:程序分成多个段，直接离散地装入内存，为了保证程序可以正常运行，就必须能从物理内存中找到各逻辑段存放的位置，为此，需要为每个进程建立一张段映射表. 这个段映射表就是我们的段表
  • 每个段在表中占有一个表项，记录了该段在内存中的起始位置（基址）和段的长度；各表项长度是相同的

image-20201025171024271

地址变换

image-20201025194631660

根据上方流程图我们来理一下地址变换的思路，其实是与分页存储管理的地址变换差不太多的

  1. 根据逻辑地址 A得到段号 S和段内地址 W
  2. 判断段号 S是否越界，如果段号 S≥ 段表长度 M，就发生越界中断，否则继续
  3. 查询段表，找到对应的段表项，段表项的存放地址为段表起始地址 F+段号 S× 段表项长度
  4. 检查段内地址 W是否超过段号所对应的段长 C，如果段内地址 W≥ 段长 C，则产生越界中断，否则继续
  5. 计算得到物理地址 = 段基址 b + 段内地址 w
  6. 访问目标内存单元
分段分页管理对比

image-20201025200044600

  • 页是信息的物理单位；分页的主要目的是为了实现离散分配，提高内存利用率；

    分页仅仅是系统管理上的需要，完全是系统行为，对于用户是不可见的；

    分页的用户进程地址空间是一维的，程序员只需要给出一个记忆符即可表示一个地址；

    页的大小固定，且由系统决定。

  • 段是信息的逻辑单位；分段的主要目的是更好地满足用户需求。

    一个段通常包含着一组属于一个逻辑模块的信息。

    分段对用户是可见的，用户编程的时候需要显示给出段名；

    分段的用户进程地址空间是二维的，程序员在标识一个地址时，既要给出段名，也要给出段名地址。

    段的长度不固定，决定于用户编写的程序。

  • 访问一个逻辑地址需要几次访问内存呢？

    • 分页（单级页表）：第一次访问内存——查询内存中的页表，第二次访问内存——访问目标内存单元
    • 分段：第一次访问内存——查内存中段表，第二次访问内存——访问目标内存单元
信息共享

分段比分页更容易实现信息的共享和保护

首先引入一个概念叫做纯代码，纯代码/可重入代码 是 不能被修改的代码；这种类型的代码是可以共享的，而可修改的代码是不能进行共享的（比如一个代码段有很多变量，多进程并发地同时访问会导致数据地不一致）

那么如果进程是分段存储管理的 几句可以很好的进行信息地共享了，因为只需要改变进程地段表项，指向同一个段即可；

image-20201025201533670

段页式存储管理

image-20201026171616190

优点
  • 段页式存储，顾名思义，肯定是利用到了页式存储+段式存储，那么既然是两者结合，肯定取其精华，去其糟粕吧，那我们先复习一下段式存储和页式存储各自优缺点都有什么

image-20201026154027329

概念
  • 那么我们的段页存储管理又是如何进行的呢？究竟是先分段还是先分页呢？
  • 我们的进程首先按照逻辑模块分段，再将分成的段分页
  • 将内存空间分为大小相同的内存块/页框/页帧/物理块
  • 进程将各页面分别装如个内存块中

image-20201026161147295

逻辑地址结构

image-20201026162123383

  • 段页式系统的逻辑地址结构由段号、页号、页内地址（页内偏移量）所组成
  • 段号：段号的位数决定了每个进程最多可以分几个段
  • 页号：页号的位数决定了每个段最大有多少页
  • 页内偏移量：页内偏移量决定了页面大小、内存块大小是多少
段表、页表

看下面这张图是否感觉有点眼熟？感觉与二级页表类似；

只不过把中间的那个页表替换成了一个段表，借此机会我们再来理顺一次思路:

一个进程对应一个段表 一个段表对应多个页表 换而言之，进程对应了多个页表

image-20201026163818291

地址变换过程

image-20201026165005382

像之前的两种存储管理的地址变换过程一样 ，我们也来理一次过程：

  1. 根据逻辑地址 A得到段号 S、页号 P和页内偏移量 W
  2. 判断段号 S与段表长度 M关系，如果 S≥M，发生越界中断，否则继续进行（第一次检查越界）
  3. 查询段表，进行运算：段表项 = 段表始址 F + S × 段表项长度 → 找到对应的段表项（第一次访问内存）
  4. 判断页号 P 与页表长度的关系，如果页号 P≥ 页表长度，发生越界中断，否则继续进行（第二次检查越界）
  5. 根据页表存放块号和页号 P计算得到查询页表，找到对应的页表项（第二次访问内存）
  6. 页表项存储着该页所在的物理块号 b，再利用物理块号 b和页内偏移量 W构成最终的物理地址
  7. 最后访问目标内存单元（第三次访问内存）

内存空间的扩展

  • 操作系统需要提供某种技术从逻辑上对内存空间进行扩充
  • 通常有三种技术：
    • 覆盖技术
    • 交换技术
    • 虚拟存储技术

image-20201015213523284

地址转换

  • OS 需要提供地址转换功能，负责程序的逻辑地址与物理地址的转换
  • 绝对装入-编译时产生绝对地址
  • 可重定位装入-装入时将逻辑地址转换为物理地址
  • 动态运行时装入-运行时将逻辑地址转换为物理地址，需要设计重定位寄存器

image-20201015214304047

内存保护

内存保护可采取两种办法

  • 方法一：在 CPU 种设置一对上、下限寄存器，寄存进程的上、下限地址。进程的指令要访问某个地址的时候，CPU 检查是否越界

    image-20201015215116282

  • 方法二：采用重定位寄存器（基址寄存器）和界地址寄存器（限长寄存器）进行越界检查。其中，重定位寄存器中存放的是进程的起始物理地址，界地址寄存器中存放的是进程的最大逻辑地址。

    image-20201015215232038

覆盖与交换

image-20201022160240209

覆盖技术

  • 覆盖是在同一个进程或程序中的

  • 思想：将程序分为多个段（多个模块），常用的段常驻内存，不常用的段在需要的时候才调入内存

    内存分为一个固定去和若干个覆盖区

    需要常驻内存的段放在固定区中，调入后就不再调出

    不常用的段放在覆盖区，需要用的时候调入内存，用不到的时候调出内存

image-20201015220730717

  • 如下图所示，假如程序 A 执行需要走如下几个程序 B、C….
  • B、C 不能同时执行，我们就在物理内存中设置一个覆盖区 用于存放 B 或者 C，其中其大小是 B、C 中较大内存决定
  • 同理 D、E、F 也不能同时执行，因此也设立一个覆盖区用于存储

image-20201017150834371

交换技术

  • 交换是在不同进程(作业)之间的

  • 设计思想：内存空间紧张的时候，系统将内存中某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存（进程在内存与磁盘间动态调度）

  • 这种技术其实在上面的处理机调度一节层次调度中的中级调度我们也有了解过了

    image-20201017152832202

  • 暂时换出外存等待的进程状态为挂起状态（挂起态）

  • 挂起态可以细分为就绪挂起和阻塞挂起两种状态 - 复习下 7 态模型吧

    image-20201017152921895

下面思考三个问题

  1. 应该在外存（磁盘）的什么位置保存被换出的进程？

    答：具有兑换功能的操作系统中，通常把磁盘空间分为文件区和对换区两部分；

    文件区主要用于存放文件，主要追求存储空间的利用率，因此对文件区空间的管理采用离散分配方式

    对换区空间只占磁盘空间的小部分，被换出的进程数据就存放在对换区，由于对换的速度直接影响到系统的整体速度，因此对换区空间的管理主要追求换入换出速度，因此通常采用连续分配方式

    对换区的 I/O 速度比文件区的更快

  2. 什么时候应该交换？

    答：交换通常在许多进程运行且内存吃紧时进行，而系统负荷降低就暂停。例如：在发现许多进程运行时经常发生缺页，就说明内存紧张，此时可以换出一些进程；如果缺页率明显下降，就可以暂停换出。

  3. 应该换出哪些进程？

    1. 可优先换出阻塞进程
    2. 可换出优先级低的进程
    3. 为了放置优先级低的进程在被调入内存后很快又被换出，有的系统还会考虑进程在内存的驻留时间
    4. PCB 会常驻内存，是不会被换出外存的

虚拟存储器

虚拟存储器概述

image-20201029202753739

传统存储管理方式的特征

image-20201029162940481

  • 一次性：是指作业必须一次性地全部装入内存后方能开始运行
    • 造成问题
      • 作业很大的时候，不能全部装入内存，导致大作业无法运行
      • 当大量作业要求运行的时候，由于内存无法容纳所有作业，因此只有少量作业能运行，导致多道程序并发度下降
  • 驻留性：是指作业被装入内存之后，整个作业都一直驻留在内存中，其中任何部分都不会被换出，直至作业运行结束。
    • 造成问题
      • 往往在一个时间段内，只需要访问作业的一小部分数据就可以正常运行，但偏偏会把其他不需要的部分也强行装入内存，这就导致了内存中会驻留大量、暂时用不到的数据，浪费了宝贵的内存资源。

局部性原理

而要解决传统存储管理的这些特征带来的问题，我们就引入了虚拟存储技术，而虚拟存储技术依靠【局部性原理】

关于局部性原理，在上述已经说过了，这里直接照搬上面的内容：

局部性原理

  • 时间局部性：如果执行了程序中的某条指令，那么不久之后这条指令很有可能被再次执行；如果某个数据被 访问过，不久之后该数据很可能被再次访问。（程序中存在大量循环）
  • 空间局部性：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问（许多数据在内存中是连续存放的）

高速缓冲技术

高速缓冲技术其实就算应用了局部性原理

  • 高速缓冲技术的思想： 将近期会频繁访问到的数据放到更高速的存储器中，暂时用不到的数据放在更低速的存储器中；

    image-20201029172212611

虚拟内存的定义和特征

定义

虚拟内存/虚拟存储器，是指具有请求调入功能和置换功能，能从逻辑上(而不是物理上)对内存容量加以扩充的一种存储器系统。

那么虚拟内存是如何”增大”内存的呢？

image-20201029195651658

基于局部性原理，在程序装入的时候，将程序中很快会用到的部分装入内存，暂时用不到的部分就留在外存，就可以让程序开始执行；

在程序执行的过程中，当所访问的信息不在内存时候，由 OS 负责将所需的信息从外存调入内存，然后继续执行程序；

假如内存空间不够，由OS负责将内存中暂时用不到的信息换出到外存；

你看 有用的在内存中，暂时用不到的在外存，是不是在用户看来是把整个程序塞入内存里了呢？

注意：

  • 虚拟内存的最大容量由计算机的地质结构（CPU 的寻址范围）确定的

    比如某计算机地址结构为 32 位，按照字节编址，内存大小位 512MB，外存大小为 2GB；

    则虚拟内存的最大容量 2^32^B= 4GB

  • 虚拟内存的实际容量 = min(内存和外存容量之和， CPU 寻址范围)

    依旧是上述例子

    则虚拟内存的实际容量=min（2^32^B, 512MB + 2GB）= 2GB +512MB；

特征

  • 多次性：是相对于传统存储管理方式的一次性而言的，是指一个作业中程序和数据无需在作业运行的时候一次性全部装入内存，而是允许被分成多次调入内存运行。多次性是虚拟存储器最重要的特征，是任何其他的存储管理方式所不具有的。因此，虚拟存储器其实是具有多次性特征的存储器管理系统。
  • 对换性：是相对于传统存储管理方式的常驻性而言的，是指一个作业中的程序和数据，无须在作业运行的时候一直常驻内存，而是允许在作业的运行过程中进行换入换出。
  • 虚拟性：虚拟性是指能够从逻辑上扩充内存容量，使得用户所看到的内存容量远远大于实际的内存容量。虚拟性是以多次性和对换性为基础的，正是由于系统允许将作业多次调入内存，并且能把内存中暂时不允许程序、数据、进程调至外存，才有可能实现了虚拟存储器；

虚拟内存的实现方法

image-20201029205625258

我们知道，管理系统要实现虚拟性必须满足对换性和多次性，那么如何要满足对换性和多次性，又有什么要求呢？答案是必须建立在离散分配的内存管理方式基础上。那么现在有什么管理方式能实现虚拟存储器呢？

分页请求系统

  • 分页请求系统 = 分页系统的基础 + 请求调页功能 + 页面置换功能
  • 用户程序装入少数页面程序和数据就能运行，之后再通过上述两个功能把即将运行页面 → 内存，暂时不运行的页面 → 外存
  • 为了实现这两个功能，系统需要提供必要硬件支持和实现请求分页的软件
    • 硬件支持：
      • 请求分页的页表机制
      • 缺页中断机构
      • 地址变换机构
    • 请求分页软件：
      • 在硬件支持下，将程序正在运行时所需页面 → 内存，内存中不用的页面从内存 → 磁盘。

请求分段系统

  • 分页请求系统 = 分段系统的基础 + 请求调段功能 + 分段置换功能
  • 用户程序装入少数段的程序和数据就能运行，之后再通过上述两个功能把即将运行的段→ 内存，暂时不运行的段 → 外存
  • 为了实现这两个功能，系统需要提供必要硬件支持和实现请求分段的软件
    • 硬件支持
      • 请求分段的段表机制
      • 缺页中断机构
      • 地址变换机构
    • 软件支持
      • 在硬件支持下，将内存中暂时不用的段从内存 → 磁盘，程序运行时所需要的段 → 内存。

请求分页存储管理方式

请求分页中的硬件支持

image-20201029220042435

请求页表机制

image-20201029205653568

页号 物理块号 状态位 P 访问字段 A 修改位 M 外存地址

状态位 P：该页是否已调入内存 0 表示没有被调入 1 表示被调入

访问字段 A：本页在一段时间内被访问的次数，供页面置换算法使用

修改位 M：标识该页在调入内存后是否被修改过

外存地址：该页在外存上的地址，供调入该页时参考

缺页中断机构

缺页中断机构的大致流程如下：

image-20201030200249404

  • 缺页中断是因为当前指令想要访问的目标页面未调入内存而产生的，因此属于内中断

  • 一条指令在执行期间，可能产生多次缺页中断

    比如 copy A to B，而 A、B 属于不同页面，那就有可能产生多次的中断：因为指令本身跨多个页面，A、B 又是分别一个数据块；

    image-20201029212923663

  • 中断的分类如下

    image-20201029212844294

地址变换机构

image-20201029213124769

由于逻辑地址到物理地址映射过程写过很多次了，这里不再赘述；

但这里需要注意的点是：

快表中有的页面一定是在内存中的，如果某个页面被换出外存，则快表中的相应表项也要删除，否则可能访问错误的页面；

找到对应的页表项之后，假如对应页面还没有调入内存，那就产生缺页中断，之后由 OS 的缺页中断处理程序进行处理

image-20201029213649586

细节补充:

  • 只有写指令才需要修改【修改位】，而且一般来说只需要修改快表中的数据，只有要将快表项删除的时候才需要写回内存中的慢表；

    这样可以减少访存次数

  • 缺页中断处理依旧需要保持 CPU 现场

  • 换入/换出页面都需要启动慢速的 I/O 操作，可见，如果换入/换出太频繁，会有很大的开销

  • 页面调入内存中，需要修改慢表，同时也需要将表项复制到快表中

页面置换算法

请求分页管理存储与基本分页存储管理的主要区别:

程序执行的过程中，当所访问的信息不在内存的时候，由 OS 负责将所需要的信息从外存调入内存，然后继续执行

假如内存空间不够，就由 OS 负责将内存中暂时用不到的信息换出到外存

而由于我们的页面换入、换出需要磁盘 I/O，有较大开销，因此好的页面置换算法的评价指标就是更少的缺页率

我们主要学习五种页面置换算法：最佳置换算法、先进先出置换算法、最近最久未使用置换算法、时钟置换算法、改进型的时钟置换算法

最佳置换算法(OPT)

image-20201030184237366

  • 最佳置换算法：每次选择淘汰的页面将是以后永不使用，或者再最长时间内不再被访问的页面，这样可以保证最低的缺页率；
  • 缺页中断未必一定会发生页面置换，假如有空闲的内存块就不用进行页面置换
  • 缺页率的计算 :缺页率 = 缺页中断发生的次数 / 访问页面的总次数 × 100 ％
  • 最佳置换算法是理想算法，因为只有在进程执行的过程中才能知道接下来会访问什么页面，OS 无法提前预判页面访问序列，因此最佳置换算法是无法实现的。

先进先出置换算法（FIFO）

image-20201030185335274

  • 先进先出置换算法（FIFO）：每次选择淘汰的页面是最早进入内存的页面

  • 如何实现的呢？先进先出，学过数据结构的朋友们都清楚，应该使用队列这种数据结构。把调入内存的页面按调入的先后顺序排成一个队列，当新来的页面需要进行页面置换的时候，poll 掉头页面即可；

    ps：队列的最长长度取决于系统为进程分配多少内存块

  • Belady（贝莱迪）异常： 一般来说，缓存越大，命中率越高，缺页率越低。但有一个计算机学者，名字叫 Belady。在 1969 年研究 FIFO 算法时，发现了一个反例，使用 4 个页框时的缺页次数比 3 个页框时的缺页多，因此这种奇怪的情况称为 Belady 异常。

    这种异常的原因是对于 FIFO 算法来说，在同一时刻，使用 4 个页框时缓存中保存的页面并不完全包含使用 3 个页框时保存的页面，二者不是超集子集关系，造成都某些特殊的页面请求序列，4 个页框命中率反而低。

    只有 FIFO 算法会产生这个异常，此外，FIFO 实现简单，但是有可能先进入的进程也会被经常访问，因此算法性能差。

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

image-20201030191211411

  • 最近最久未使用置换算法（LRU）：每次淘汰的页面是最近最久未使用的页面

  • 实现方法：赋予每个页面对应的页表项，用访问字段记录该页面自上次被访问以来所经历的时间 t

    如果需要淘汰页面，就选择现有的页面中 t 值最大的，即最近最久没有使用的页面

  • 该算法需要专门的硬件支持（寄存器，栈），虽然算法性能好，但是实现也很困难，开销也很大

时钟置换算法(CLOCK)

image-20201030202108812

简单的 CLOCK 算法

image-20201030193731094

  • 时钟置换算法/最近未用算法：通过循环队列将未访问页面置换的算法
  • 简单的 CLOCK 实现方法：为每个页面设置一个访问位——用于标志最近是否访问过（如果该进程被访问了就从 0 被标志为 1），然后将内存中各页面通过链接指针链接成一各循环队列；当访问新页面，需要置换页面的时候，通过检查页的访问位去置换：如果是 0 → 换该页面，同时指针指向下一个页面；如果是 1 → 置为 0，给第二次留在内存的机会。

改进型的 CLOCK 算法

image-20201030202052642

  • 改进型 CLOCK 置换算法:我们将一个页面换出的时候，假如它是修改过的，那么其修改后的数据需要重新写回外存中，如果没有被修改过，就不需要拷回外存。

    说人话就是：对于一个换出的页面，如果其被修改过，那么它换出的开销比没有被修改过的要大，那么换他出去就划不来了。

  • 那我们以什么为指标去评判一个页面该不该被置换呢？显然易见：有没有被访问过 + 有没有被修改过

    • （访问位 A， 修饰位 M）
    • （A = 0，M = 0）= 最近既没被访问 + 又没被修改过 ，被置换的优先级最高
    • （A = 0，M = 1）= 最近没被访问 + 已经被修改了，并不是很好的置换选项，优先级第二
    • （A = 1，M = 0）= 最近已经被访问了 + 但没被修改过 ，那么这个页面有可能还会被访问，优先级低三
    • （A = 1，M = 1）= 最近已经被访问 + 已经被修改，被置换的优先级最低（第四）

  • 那这个访问位，修饰位凭什么作为依据呢？这与我们的扫描过程有关

    • 第一轮去找（0，0），不改变标志位
    • 第一轮没找到，找第二轮，把扫描过的访问位置 0，我们这轮找第一个（0，1）
    • 第二轮没找到，找第三轮，我们找（0，0），也不改变标志位
    • 第三轮没找到，我们找第四轮，找第一个（0，1）

    发现了吗，这与我们上面的优先级正好是吻合的，优先级低的相当于有多一次的免死金牌，多在内存里苟活一段时间；

页面分配策略

image-20201102132105189

页面分配、置换策略

  • 驻留集：指请求分页存储管理中给进程分配的物理块的集合，在采用了虚拟存储技术的系统中，驻留集大小一般小于进程的总大小

由上面的概念我们可以发现：

  • 如果我们的驻留集太小了，会导致缺页非常的频繁，而这会导致系统要花大量时间处理缺页，开销就很大，而且用于进程推进的时间就很少了；
  • 如果我们的驻留集太大了，又会导致多道程序的并发度下降，资源的利用率就降低了

因此，不难发现，选择一个合适的驻留集大小就是非常必要的了，因此我们有了两种选择驻留集大小的分配方式

  • 固定分配：OS 为每一个进程分配一组固定数目的物理块，在进程运行期间不再改变；即，驻留集大小不变
  • 可变分配：先为每个进程分配一定数目的物理块，在进程运行期间，可以根据情况做适当的增加或减少；即，驻留集大小可变

置换策略：

  • 局部置换：发生缺页的时候只能选择进程自己的物理块进行置换
  • 全局置换：可以将 OS 保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程

image-20201101153719062

我们下面对三种分配置换组合进行讲解：

  1. 固定分配局部置换：系统为每个进程分配一定数量物理块，在整个运行期间都不改变；若进程在运行过程中发生缺页，只能从该进程在内存中的页面选出一页换出，然后再调入需要的页面；

    缺点：很难在刚开始就确定应该为每个进程分配多少个物理块才合理（采用这种策略的系统可以根据进程大小、优先级、或是根据程序员给出的参数来确定为一个进程分配的内存块数）

    image-20201101154502336

  2. 可变分配全局置换：刚开始会给每个进程分配一定数量物理块。OS 会保持一个空闲物理块队列，当某进程发生缺页的时候，从空闲物理块取出一块分配给该进程；

    若没有空闲物理块，就选择一个未锁定（系统会锁定一些页面，这些页面中的内容不能被置换出外存 比如，重要的内核数据就可以设置为“锁定”）的页面换出外存，再将该物理块分配给缺页的进程。使用这种策略的话，只要某个进程发生了缺页，都将获得新的物理块，仅当空闲物理块用完的时候，系统才选择一个未锁定的页面调出。被选择调出的页可能是系统中任何一个进程的页，因此这个被选中的进程所拥有的物理块会减少，缺页率也会增加。

    image-20201101155052393

  3. ==可变分配全局置换==：刚开始会给每个进程分配一定数量的物理块。当某进程发生缺页的时候，只允许从该进程自己的物理块选出一个换出外存。

    缺点：如果进程在运行中频繁地缺页，系统会给该进程多分配几个物理块，直至该进程缺页率趋势适当程度；反之，如果进程在运行中缺页率特别低，则可以适当减少分配给该进程的物理块 也就是说 这点体现出了可变分配的概念

    image-20201101215351728

不难发现：

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

何时调入页面

  1. 预调页策略：根据局部性原理（空间局部性），一次调入若干个相邻地页面可能比一次调入一个页面更高效。但如果提前调入的页面中大多数都没被访问过，则又是低效的。因此可以预测不久之后可能访问到的页面，将他们预先调入内存，但目前预调页的成功率仅仅只有 50%；

    故这种策略主要用于进程的首次调入（运行前调入），由程序员指出应该先调入哪些部分；

  2. 请求调页策略：进程在运行期间发现缺页的时候才将所缺页面调入内存（运行时调入），由这种策略调入的页面一定会被访问到，但由于每次只能调入一页，每次调页都需要磁盘的 I/O 操作，因此 I/O 开销大。

何处调入页面

  1. 系统拥有足够对换区空间：页面的调入、调出都是在内存与对换区之间进行，这样可以保证页面的调入、调出的速度很快；

    在进程运行前，需要将进程相关的数据从文件区复制到对换区。

    image-20201102125345951

  2. 系统缺少足够对换区空间：

    凡是不会被修改的数据都直接从文件区调入，由于这些页面不会被修改，因此换出的时候是不必被写回磁盘的，下次需要的时候再从文件区调入即可。

    对于可能被修改的部分，换出的时候需要写回磁盘对换区，下次需要的时候再从对换区调入。

    image-20201102125517438

  3. UNIX 方式：运行之前进程有关的数据全部放在文件区，故未使用过的页面，都可以从文件区调入。

    若被使用过的页面需要换出，则写回对换区，下次需要的时候从对换区调入；

    image-20201102125945650

抖动（颠簸）现象

刚刚换出的页面马上又要换入内存，刚刚换入的页面马上又要换出内存，这种频繁的页面调度行为称为抖动，或颠簸；

产生抖动主要原因是进程频繁访问的页面数量高于可用的物理块数

抖动的发生与页面置换算法、页的大小和分配的内存页面数有关，与内存大小无关

上面我们提到了，分配的物理块太少和太多带来的影响，因此为了研究每个进程分配多少个物理块这个问题，引入新概念工作集

  • 驻留集：指的是请求分页存储管理中给进程分配的内存块的集合；
  • 工作集：指的是某段时间间隔内，进程实际访问页面的集合；

image-20201102131739128

OS 根据窗口尺寸来算出工作集

image-20201102132004226

文件系统

初识文件管理

image-20201103194047847

文件

  • 一个文件应该有哪些属性呢？
  1. 文件名：由创建文件的用户决定文件名，主要是为了方便用户找到文件，同一目录下不允许有重名文件
  2. 标识符：OS 用于区分各个文件的一种内部名称
  3. 文件类型：可以用不同的角度来规定文件的类型，如源文件、目标文件以及可执行文件等
  4. 文件的位置：文件存放的路径、在外存中的地址
  5. 文件的大小/长度：指的是文件的大小或是长度，长度单位可以是字节、字或块
  6. 文件的的建立时间：指最后一次的修改时间等
  7. 文件的保护信息：对文件进行保护的访问控制信息

文件内部数据组织

image-20201103171557320

  • 无结构文件（如文本文件： 由一些二进制或者是字符组成，又称为“流式文件”
  • 有结构文件（如数据库表)：由一组相似的记录（记录是一组相关数据项的集合（数据项是文件系统中最基本的数据单位））组成，又称为”记录式文件”

文件是如何组织起来的

image-20201103194753217

  • 用户可以创建一层一层的目录，各层目录中存放相应的文件，系统中的各个文件就通过一层层的目录合理有序的组织起来了
  • 所谓目录 即我们熟悉的文件夹，是一种特殊的有结构文件

OS 向上提供的功能

image-20201103195126301

文件存放在外存的方法

image-20201103195845754

文件的逻辑结构

按照文件是否有结构分类，可以分为无结构文件，有结构文件两种

无结构文件

  • 文件内部的数据就是一系列二进制流或是字符流组成，又称为流式文件

    如 Window 操作系统种的.txt 文件

image-20201109222307176

有结构文件

  • 由一组相似的记录组成，又称为记录式文件。每条记录由若干个数据项组成

    如：数据库表文件（一般来说每条记录有一个数据项作为关键字去识别不同记录的 ID）

image-20201109222534791

根据各条记录的长度（占用的存储空间）是否相等，又可以细分为：定长记录 和 可变长记录两种

  • 定长记录：

    每条记录的长度都是相同的，各数据项都处在记录中相同的位置，具有相同的顺序和长度

    image-20201109222721478

  • 可变长记录:

    由于记录的数据项的长度是不确定的，因此各记录条的长度同样也是不确定的；

    image-20201109222809031

有结构文件的逻辑结构

image-20201110210117983

顺序文件

  • 文件种的记录一个接一个地顺序排列（逻辑上)，记录可以是定长的或是可变长的

  • 各个记录在物理上可以是顺序存储或是链式存储

    • 顺序存储：逻辑上相邻的记录，物理上也相邻（类似于顺序表）

      对于**可变长记录**，无法实现随机存取，每次都只能从第一个记录开始依次往后找

对于**定长记录**，可以做到随机存取，若记录的长度为L（每个记录的长度模块是L）,那么第i个记录存放的相对位置就是**i×L**

![image-20201109223441980](

      https://er11.oss-cn-shenzhen.aliyuncs.com/img/image-20201109223441980.png)

    • 链式存储：逻辑上相邻的记录，物理上不一定相邻（类似于链表）

      无论是定长或是可变长记录，都是无法实现随机存取的，每次都只能从第一个记录开始依次往后找

![image-20201109223453210](

      https://er11.oss-cn-shenzhen.aliyuncs.com/img/image-20201109223453210.png)

索引文件
  • 索引表其实很像之前学习的页表，就是通过索引号去快速映射到我们需要的逻辑文件上

image-20201110204932034

索引顺序文件
  • 可以把索引顺序文件这种管理方式看成前面学习的二级页表的管理方式
  • 把键值那一栏看成目录，查找目录总比查找一项项内容要来得快
  • 打个比方，我们都查过字典吧？我们需要查一个字，不可能直接就翻页翻到那一页，而是先翻目录，确定那个字大概在哪，然后再翻到那一部分，第二次查找，去找那个字

image-20201110205536840

有时候，我们只分两层还是不够，需要多级索引

因此衍生出来了：多级索引顺序文件

image-20201110210047209

文件目录

image-20201112201410070

文件控制块 FCB

image-20201217211254729

目录文件中的一条条记录就是一个个的文件控制块（FCB）

同理：FCB的有序集合称为文件目录，一个FCB就是一个文件目录项

FCB实现了文件名和文件之间的映射，使得用户可以实现【按名存取】

FCB中包含了：

  1. 文件的基本信息
    1. 文件名
    2. 物理地址
    3. 逻辑结构
    4. 物理结构
    5. ….
  2. 存取控制信息
    1. 是否可读/可写
    2. 禁止访问的用户名
    3. …
  3. 实用信息
    1. 文件的建立时间
    2. 修改时间
    3. …

单级目录结构

  • 单机文件目录其实非常好理解：就是在文件系统中只建立一张目录表，目录表存放多个文件，然后各文件各占一个目录项，目录项中又包含文件名、文件类型等等属性
文件名 文件类型 文件长度
文件名 1 … …
文件名 2 … …
文件名 3 … …

是简单，但仅仅只能做到按名存取，他有着三个缺点：

  • 查找速度慢

  • 不允许重名

  • 不便于实现文件共享

    image-20201110211948655

两级目录结构

image-20201110212749873

多级（树形）目录结构

image-20201110213226336

路径名 和 当前目录

  • 路径名（path name）：多级目录（树形目录）中，从根目录出发，找到一项数据文件的路径是唯一的。在该路径上，从树的根开始，直到遍历到数据文件结束，途中经历的全部目录文件名和数据文件名用 /进行连接，就构成了数据文件唯一的路径名了

  • 当前目录（Current Directory）：由于每个文件的路径名是唯一的，那难道每次访问它都得从根开始吗？显然不可能。

    因此衍生出当前目录这个概念帮我们解决这个问题。

无环图目录结构

  • 树形目录结构可以方便对文件进行分类，层次结构清晰，也能够有效的进行文件的管理和保护

    但是，树形结构不便于实现文件的共享，为此，提出了无环图目录结构

image-20201112195220519

索引结点（FCB 的改进）

image-20201112195928484

OS 书上还说明了另外一个原因 阐明为什么要引入索引结点

当一个文件被多个文件共享的时候，假如我在其中一个目录访问该文件，并向该文件添加新内容，必须要增加相应的盘块；

而这些新增加的盘块只会出现在我位于的目录中，其他目录是不会相应增加的；

因此这新增的部分是不能被共享的，因此引入了索引结点；

索引结点中记录了文件的各种信息：包括文件在外存中的存放位置和其他的文件属性等信息；

这些信息之前是放在目录项中的，而如今放在索引结点中。

当任何用户对共享的文件进行修改的时候，其相应节点内容都会改变，由于是目录存储了指针，那这些变化对于所有用户都是可见的，因此可以实现共享；

  • 存放在外存中的索引结点我们称为磁盘索引结点，当索引结点放入内存后称为内存索引结点

  • 相比之下，内存索引结点中需要增加一些信息，比如：文件是否被修改，此时有几个进程正在访问该文件。

文件的物理结构

文件块、磁盘块

类似于我们的内存分配，磁盘（外存）中的存储单元也会被分成一个个的块/磁盘块/物理块

而在很多操作系统中，磁盘块的大小通常与内存块、页面的大小相同

  • 内存与磁盘之间的数据交换：

image-20201112204211931

于是文件的逻辑地址也可以表示为（逻辑块号，块内地址）的形式

操作系统为文件分配存储空间都是以块为单位

而用户通过逻辑地址来操作自己的文件，操作系统负责实现从逻辑地址到物理地址的映射

文件分配方式

image-20201117213342204

连续分配

image-20201112204626251

用户通过逻辑地址来操作自己的文件；

（逻辑块号，块内地址） → （物理块号，块内地址），只需要转换块号即可，块内地址保持不变

用户给出了要访问的逻辑块号，操作系统找到该文件对应的目录项（FCB）

物理块号 = 起始块号 + 逻辑块号（逻辑块号 需要小于 长度）

由于可以直接算出逻辑块号对应的物理块号，因此连续分配支持顺序访问和直接访问（随机访问）

  • 连续分配方式的优点：由于读取某个磁盘块的时候，需要移动磁头；因此访问的两个磁盘块相隔越远，那么移动磁头所需要的时间就越长；而如果文件采取连续分配方式，那么文件就是连续的，因此连续分配的文件在顺序读/写时速度最快

  • 连续分配方式的缺点：如果文件 A 需要拓展，而其后面没有相邻的空闲块，那么就需要举家迁移到一个可以放下连续磁盘块的空闲区域

    因此，连续分配的缺点 1：文件不方便拓展

    image-20201113170336498

假如磁盘中空闲区域并不是连续的，那么就算空闲区域加起来足够放下文件，文件也不能放入磁盘中

因此，连续分配的缺点 2：存储空间利用率低，会产生难以利用的磁盘碎片（虽然可以用紧凑处理，但耗费很大时间代价）

image-20201113170652168

链接分配

image-20201113174225789

链接分配优点：（其实和链表的优点大同小异）

  • 消除了磁盘的外部碎片，提高外存的利用率
  • 对插入、删除和修改记录都非常容易
  • 能适应文件的动态增长，无需事先知道文件的大小
隐式分配

image-20201113172110369

采用链式分配（链表形式/隐式链接）方式的文件，只支持顺序访问，不支持随机访问，查找效率低

同时，指向下一个盘块的指针也需要消耗少量的存储空间；

但是，采用隐式链接这个方式，可以方便的拓展文件，如果学过链表的同学就知道，我们可以使用尾插法，在这里就是修改结束块号

因此，所有的空闲磁盘块都可以被利用，不会有碎片问题，外村利用率提高

显式链接

image-20201113173221037

显式链接类似于数据结构中的静态链表，也就是利用数组去存储下一个块号的下标；

这样子的话，我们只需要知道起始块号，就能找到该文件包含的所有磁盘块了。

  • 那么如何实现逻辑块号到物理块号的转变呢？

假设用户需要访问逻辑块号 i，OS 会找到该文件对应的目录项（FCB），FCB 中存储了很多信息，其中就包含起始块号

接着查询内存中的文件分配表 FAT，往后找 i 到 i 号逻辑块对应的物理块号。（相当于查询数组下标了）

这里需要注意，逻辑块号转换到物理块号这一过程是不需要读磁盘操作的

链式分配（显示链接）的文件，支持顺序访问和随机访问，由于块号转换过程不需要访问磁盘，因此相比于隐式链接，访问速度要快很多

索引分配

image-20201117204230180

  • 索引分配允许文件离散分配在各磁盘块之中，系统会为每个文件建立一张索引表
  • 索引表记录了文件的各个逻辑块对应的物理块
    • 索引表的功能类似于内存管理中的页表——建立逻辑页面到物理页面之间的映射关系
  • 索引表存放的磁盘块称为索引块
  • 文件数据存放的磁盘称为数据块
  • 区别于显式链接，索引分配的表是一个文件一张，而显式链接中是一个磁盘对应一张（磁盘中包含多个文件，也就是说可能磁盘采取索引分配的话，可能会有多张索引表）
  • 索引分配方式支持随机访问，文件拓展也容易实现（给文件分配一个空闲块，再加一个索引表项即可）
  • 但是索引表需要占用一定的存储空间
索引分配方案

想一想，假如一个文件太大了，一个单独的磁盘块（索引块）装不下文件的整张索引表，那该怎么办呢？

我们有三种解决方案：链接方案、多层索引、混合索引

  • 链接方案

    image-20201117210500055

    其实其基本思想与数据结构中的链表无二，就是将块离散的 存储，而后通过链接的方式串起来

    但这个方式也与链表的弊端一样，就是我们的查找非常的麻烦，极端一点想，我们只想访问文件最后一个索引块

    就不得不遍历整个索引块，十分麻烦且低效

    而且中小型文件，本身就不大了，还得为他分配索引块，可见，小文件采用这种方式，索引块利用率很低；

  • 多层索引

    image-20201117211041743

    为解决上述问题，我们类如了类似于多级页表的多层索引；

    也就是用顶级索引表去查次级索引表，以此类推

    其访问方式是：用逻辑块号 ÷ 表项数 得到次级表是哪一块，用逻辑块号%表项数得到偏移地址

    采用 K 层索引结构，且顶级索引表未调入内存的时候，访问一个数据块需要 ==k+1==次读磁盘操作

    这种方式的优点是：大大加快了对大型文件的查找速度

    缺点是：假如文件很小，但其所在的索引技术很大，我访问这个盘块的时候依旧得按照这种方式，太麻烦了；

  • 混合索引

    image-20201117212311990

    我们知道 OS 最喜欢干的事情就是把各种方法的优点结合起来，然后美名其曰叫“混合 xxxx“ 呵呵

    混合索引就是既采用了直接地址索引，又采用了多层索引

    这样的话，小文件用直接地址索引；大文件用多层索引；十分方便

image-20201117213253389

文件存储空间管理

存储空间的划分与初始化

image-20201117214435447

存储空间管理方法

空闲表法

空闲表法 属于 连续分配方式

与内存的动态方式差不太多，为每个内存分配一块连续的存储空间

同时为外存上的所有空闲区建立一张空闲表：

每个空闲区对应一个空闲表项——空闲表项又包括：表项序号、该空闲区第一个盘块号、该区的空闲盘块数

而文件分配在哪个区间的方法与内存分区（动态）分配方式类似:

采用：首次适应、最佳适应、最坏适应等算法

对于文件系统来说，文件较小（盘块 1-4 个时），采用连续分配方式，为文件分配相邻接的几个盘块；

当文件较大的时候，采用离散分配方式；此外，对于多媒体文件，为减少磁头寻道时间，采用连续分配方式

image-20201120170855920

空闲链表法

空闲链表法中，形成链表的结点有两种组成形式:盘块和盘区

  • 盘区：每个盘区可包含若干个盘块
  • 空闲链表法：把空闲的结点串在一起，当有文件申请 N 个盘块的时候，从链表头开始检索，之后的分配方式根据结点是盘块还是盘区决定

image-20201120172927583

空闲盘块链
  • OS 保存链头链尾指针
  • 分配方式：从链头开始，边遍历边分配指针
  • 回收方式：将回收的盘块依次使用尾插法

空闲盘区链

  • OS 保存链头、链尾指针

  • 分配方式：与上一种方式不同，不会边遍历边分配，而是依旧不同算法规则找到一个合适的盘区分配给文件

    若是不存在这种盘区，则将不同盘区的盘块摘取同时分配给一个文件

  • 回收方式：若回收区与某空闲盘相邻，则合并到空闲盘区中；若不相邻，则作为单独结点（盘区）使用尾插法

image-20201120174129662

位示图法

位示图使用 0/1 其中一位表示对应盘块空闲，另一位表示已分配

位示图形如二维数组，那么行列肯定有其代表的意义

  • 行：字号
  • 列：位号
  • map[m,n]表示盘块号

若盘块号、字号、位号由 0 开始：

  • 字号（行号）i，位号（列号）j 的二进制位对应的盘块号 b = n（一个字的字长）× i + j
  • b 盘块号对应的字号 i = b / n，

若从 1 开始：

  • 字号（行号）i，位号（列号）j 的二进制位对应的盘块号 b = n（一个字的字长）× （i - 1） + j
  • 分配方式：若文件需要 K 个块
    • 顺序扫描位示图，找到 K 个相邻或不相邻的 0（这里 0 表示空闲，有可能在另外一种表达方式里 1 代表空闲）
    • 根据字号、位号(行、列)计算出对应盘块号，将相应盘块分配给文件
    • 将相应位设置为“1”
  • 回收方式：根据回收的盘块号计算出对应字号位号，设置为 0

image-20201121130707136

文件的基本操作

image-20201124220831037

创建文件

image-20201124221136257

删除文件

image-20201124221532748

打开文件

image-20201124222804765

通常来说，打开文件表又分为两种：系统的打开文件表和用户进程的打开文件表

用户进程的打开文件表包含:读写指针 用于 记录该进程对文件的读/写操作进行到的位置

image-20201124223414879

关闭文件

image-20201125211157912

读文件

image-20201125211417892

写文件

image-20201125211550210

总结

image-20201125211631423

文件共享

image-20201125215953551

文件共享的意义:让多个用户共享地使用同一个文件

ps：多个用户共享同一个文件，表示系统中只有一份文件数据，只要某一用户修改该文件数据，其他用户也可以看到文件数据的变化

而假如多个用户复制同一份文件，在各自复制的文件上修改，是对其他用户的文件数据无影响的

文件共享分为两种方式

  • 基于索引结点的共享方式 - 硬链接
  • 基于符号链的共享方式 - 软链接

基于索引结点的共享方式 - 硬链接

将文件的物理地址以及其他的文件属性等信息 不再放在目录项之中，而是放在索引结点中；

这样的话，文件目录就只会包含：文件名 和 指向索引结点的指针（二级目录？

用户对于文件的修改，是改变了结点内容的改变，而没影响到指针的指向，因此实现了用户的文件共享功能

image-20201125213642244

基于符号链的共享方式 - 软链接

利用符号链实现文件共享的基本思想是：是允许一个文件或子目录有多个父目录，但其中仅有一个作为主父目录

其他的父目录是通过符号链接方式与该文件进行链接

image-20201125214428159

比如说快捷方式，就是一种软链接

当我们启动快捷方式的时候，一层层检索目录结构，最后运行实质上的真正程序。

文件保护

文件保护有三种方式：口令保护、加密保护、访问控制

image-20201126174955785

口令保护

基本思想：为文件设置一个口令（密匙？）用户请求访问该文件时需要提供该口令

口令存储位置：一般来说存放在文件对应的FCB(文件控制块，包含了文件各种信息)或者索引结点中。用户访问文件之前输入口令，OS 根据用户所输入的口令与 FCB 中口令进行对比；若正确，则允许该用户访问文件

优点：保存口令的空间开销不多，验证口令的时间开销也小

缺点：正确的口令存放在系统内部，不够安全

加密保护

加密保护的实质是运用了加密算法，对原始数据进行处理，使之成为新数据；

只有使用对应的解密算法才能把数据还原成原始数据；

比如下例用的是异或运算（相同为 0，不一样为 1）

image-20201126173619641

优点：保密性强，不需要在系统中存储密码

缺点：编码/译码，加密/解密 需要一定时间

访问控制

在文件的 FBC 或索引结点中 + 一个访问控制列表（玩权限）

记录各用户能对该文件进行的操作

image-20201126174324167

精简访问列表:

image-20201126174800002

文件系统层次结构

文件系统层次结构由上至下分别为:

用户接口 → 文件目录系统 → 存取控制模块 → 逻辑文件系统与文件系统缓冲区 → 物理文件系统 →（辅助分配模块/设备管理模块 → 设备）

image-20201126205049927

用户接口：文件系统需要向上层的用户提供一些简单易用的功能接口；这层就是用于处理用户发出的系统调用请求（Read、Write、Open、Close 等系统调用）

文件目录系统：用户是通过文件路径来访问文件的，==因此这一层需要根据用户给出的文件路径找到相应的==FCB或者索引结点

所有的目录、目录项相关的管理工作都在本层完成。如：管理活跃的文件目录表、管理打开文件表等。

存取控制模块：为了保证文件数据的安全，还需要验证用户是否有访问权限。这一层主要完成了文件保护相关功能

逻辑文件系统与文件信息缓冲区：用户指明想要访问文件记录号，这一层需要将记录号转换为对应的逻辑地址。

物理文件系统：这一层需要把上一层提供的文件逻辑地址 → 实际的物理地址

辅助分配模块：负责文件存储空间的管理，即负责分配和回收存储空间

设备管理模块：直接与硬件交互，负责和硬件直接相关的一些管理工作。如：分配设备、分配设备缓冲区、磁盘调度、启动设备、释放设备等。

用一个例子进行记忆的话：

假设某用户需要删除D:/工作目录/学生信息.xlsx 的最后 100 条记录

则：

  1. 用户需要通过 OS 提供的接口发出上述请求 —— 用户接口
  2. 由于用户提供的是文件的存放路径，因此需要 OS 一层层查找目录，找到对应的目录项 —— 文件目录系统
  3. 不同的用户对文件有不同的操作权限，因此为了保证安全，需要检查用户是否有访问权限 —— 存取控制模块（存取控制验证层）
  4. 验证了用户的访问权限之后，需要把用户提供的”记录号”转变为对应的逻辑地址 —— 逻辑文件系统与文件信息缓冲区
  5. 知道了目录记录对应的逻辑地址之后，需要转换成实际的物理地址 —— 物理文件系统
  6. 要删除记录，需要与磁盘设备发出请求 —— 设备管理程序模块
  7. 删除记录后，那么就会有一些盘块变为空闲状态，因此要将空闲盘块进行回收 —— 辅助分配模块

磁盘

磁盘的结构

image-20201127165917726

磁盘 磁道 扇区

image-20201127155825907

  • 磁盘：磁盘的表面由一些磁性物质组成，可以用这些磁性物质来记录二进制数据

  • 磁道：磁盘的盘面呗划分成一个个磁道，一个圈（环）就是一个磁道。

    磁道类似跑道，可以这样记忆。

  • 扇区：一个磁道又被划分成一个个扇区，每个扇区就是一个磁盘块。各个扇区存放的数据量相同

如何读写数据

内部结构：

image-20201127155902299

读取数据的过程是这样的：

首先把磁头移动到想要读/写扇区的所在的磁道上。然后转动磁盘，目标扇区从磁头下划过的时候，就完成了对扇区的读/写操作了。

有点类似于留声机?

盘面、柱面

  • 盘面：一个盘片可能有 2 各盘面

  • 柱面：所有盘面中相对位置相同的磁道组成柱面

    什么意思呢？想象一下空间内有一个盘面（圆）从内到外分成很多个圆环。这些圆环各向垂直于面的方向延申，形成了一个个圆柱面

    这就是柱面

磁盘的物理地址

image-20201127162936159

上述我们提到了柱面、扇面、扇区

那就有对应的柱面号，扇面号和扇区号了。磁盘块的物理地址就是靠这三个属性进行定位

定位过程:

  1. 首先磁臂内外移动 —— 定位柱面
  2. 激活相应的磁头 —— 定位扇面
  3. 旋转磁盘，扇区从磁头下划过 —— 定位扇区号

磁盘分类

  • 按照磁头可不可以移动来分
    • 磁头可移动：活动头磁盘，磁臂可以来回伸缩带动磁头定位磁道
    • 磁头不可移动：固定头磁盘，磁盘中每个磁道都有一个磁头
  • 按照盘片可不可以更换来分
    • 盘片可以更换：可换片磁盘
    • 盘片不可更换：固定盘磁盘

磁盘调度算法（重点)

image-20201128175628500

一次磁盘读/写操作需要的时间

要明白算法的调优方式，必须先明白读写的时间开销在哪，才能对症下药

总花费时间 = 寻找时间/寻道时间 + 延迟时间 + 传输时间

  • 寻道时间：磁头定位磁道所花时间
  • 延迟时间：旋转转盘，磁头定位到扇区所花时间
  • 传输时间：从磁盘读出/向磁盘写入数据所花时间

image-20201128170619688

先来先服务算法（FCFS）

这种算法就是按照进程的请求到达顺序，磁头依次移动；

  • 优点：公平，假如请求访问的磁道较为集中，算法性能不算太差
  • 缺点：若有大量进程竞争使用磁盘，请求访问磁道分散，则磁头需要移动的磁道数将会很大，此算法性能就会很差。

image-20201128171229955

最短寻找时间优先算法（SSTF）

这个算法只会着眼于眼前的最近磁道（贪心算法），保证单次寻道时间最短。

  • 优点:性能好，平均寻道时间短

  • 缺点:可能造成【饥饿】现象

    什么意思呢？假如处理某处磁道的访问请求时，本来应该处理下一个磁道请求了，但来了一个更近的，就不得不先处理更近的了。这种情况一旦多了，就会导致一些磁道访问请求迟迟得不到处理，造成了饥饿现象。

image-20201128171832768

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
package 磁盘调度算法;
import java.util.List;
import java.util.Scanner;

//最短寻道时间优先
public class SSTF{
	private int visit[];
	private int nearIndex=0;
	public int[] sstf(int queue[],int start){
		int nearNum=9999;
		visit=new int[queue.length];
		for(int i=0;i<queue.length;i++){
			for(int j=0;j<queue.length;j++){
				if(queue[j]!=-1){
					if(Math.abs(nearNum-start)>Math.abs(queue[j]-start)){
						nearNum=queue[j];
						nearIndex=j;
					}
				}
			}
			visit[i]=nearNum;
			queue[nearIndex]=-1;
			start=nearNum;
			nearNum=9999;
		}
	return visit;
	}
	public void print(int visit[],int start){
		double sum=0;
		System.out.print("访问序列：");
		for(int i=0;i<visit.length;i++){
			System.out.print(visit[i]+" ");
			sum=Math.abs(visit[i]-start)+sum;
			start=visit[i];
		}
		System.out.println();
		System.out.println("经过的磁道总数："+sum);
		System.out.println("平均寻道长度："+sum/visit.length);
	}

	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		System.out.println("请输入磁盘请求序列长度：");
		int a=sc.nextInt();
		System.out.println("请输入磁盘请求访问序列：");
		int[] queue=new int[a];
		for(int i=0;i<a;i++){
			queue[i]=sc.nextInt();
		}
		SSTF sstf=new SSTF();
		System.out.println("请输入读写头起始位置：");
		int start=sc.nextInt();
		sstf.print(sstf.sstf(queue, start),start);
	}
}

扫描算法（SCAN）

扫描算法是用于解决 SSTF 算法产生的饥饿问题的。

SSTF 算法的饥饿问题是由于磁头有可能仅在一个小区域内移动，因此，扫描算法规定了扫描的方式：

只有磁头移动到最外侧磁道的时候才能往内移动，移动到最内侧磁道的时候才能向外移动

  • 优点：性能较好，平均寻道时间短，不会产生饥饿现象(不会发生磁头只在一个小区域内移动的问题)

  • 缺点：只有到达最边上的磁道时才能改变磁道移动方向（有时候外侧磁道是没有请求的，因此移动是无意义的）

    SCAN 算法对各位置磁道的相应频率不平均，有一些磁道刚被从左往右移动磁头访问了，没过多久就又会被从右往左返回的磁头再次访问，而有一些磁道就得等很久才能被再次访问。

image-20201128172906549

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
package 磁盘调度算法2;
import java.util.List;
import java.util.Scanner;

public class SCAN{
	private int visit[];
	private int nearIndex=0;
	public int[] scan(int queue[],int start,int direction){
		int nearNum=9999;
		int index=0;
		visit=new int[queue.length];
		for(int i=0;i<queue.length;i++){
			index=-1;
			for(int j=0;j<queue.length;j++){
				if(queue[j]!=-1){
					if((direction==1)&&(queue[j]>start)&&(Math.abs(nearNum-start)>Math.abs(queue[j]-start))){
						nearNum=queue[j];
						nearIndex=j;
						index=0;
					}
					else if((direction==0)&&(queue[j]<start)&&(Math.abs(nearNum-start)>Math.abs(queue[j]-start))){
						nearNum=queue[j];
						nearIndex=j;
						index=0;
					}
				}
			}
			if((direction==1)&&(index==-1)){
				direction=0;
				i=i-1;
			}
			else if((direction==0)&&(index==-1)){
				direction=1;
				i=i-1;
			}
			if(index==0){
				visit[i]=nearNum;
				queue[nearIndex]=-1;
				start=nearNum;
				nearNum=9999;
			}
		}
		return visit;
	}

	public void print(int visit[],int start){
		double sum=0;
		System.out.print("访问序列：");
		for(int i=0;i<visit.length;i++){
			System.out.print(visit[i]+" ");
			sum=Math.abs(visit[i]-start)+sum;
			start=visit[i];
		}
		System.out.println();
		System.out.println("经过的磁道总数："+sum);
		System.out.println("平均寻道长度："+sum/visit.length);
	}

	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		System.out.println("请输入磁盘请求序列长度：");
		int a=sc.nextInt();
		System.out.println("请输入磁盘请求访问序列：");
		int[] queue=new int[a];
		for(int i=0;i<a;i++){
			queue[i]=sc.nextInt();
		}
		SCAN scan=new SCAN();
		System.out.println("请输入读写头起始位置：");
		int start=sc.nextInt();
		System.out.println("磁道增加的方向：（0向磁道号减少的方向移动,1向磁道号增加的方向移动）");
		int direction=sc.nextInt();
		scan.print(scan.scan(queue, start,direction),start);
	}
}

LOOK 调度算法

扫描算法虽然解决了饥饿问题，但是出现了有一些没必要的移动问题。

那么 LOOK 算法就是解决这个问题的：

若磁头行进路径方向上没有其他请求了，就立刻改变磁头移动方向，减少了无意义的移动。

image-20201128174043814

循环扫描算法（C-SCAN）

扫描算法还有一个问题，就是各个位置磁道的响应频率不平均

循环扫描算法就是解决这一问题：

它规定了一个方向，只有沿着这个方向移动的磁头才会对磁道访问请求进行处理，而反方向时只快速移动，而不做任何处理

  • 优点：各个位置磁道的响应频率很平均
  • 缺点：还是老问题，它到达最边上磁道才会反向移动，多了无意义的移动。

image-20201128174540760

C-LOOK 调度算法

回想一下之前的 LOOK 算法，假如磁头行进路径方向上没有其他请求了，就立刻返回。

那么 C-LOOK 算法也是如此，而且它加上了循环扫描算法的特点：它规定了一个方向，只有沿着这个方向移动的磁头才会对磁道访问请求进行处理，而反方向时只快速移动，而不做任何处理

也就是 C-SCAN 算法 + LOOK 算法 = C-LOOK 算法

image-20201128175558729

减少磁盘延迟时间的方法

image-20201128182703444

  • 延迟时间：将目标扇区转到磁头下面所花的时间

由于磁头读入扇区数据后需要一定时间处理，而在这时间段内，磁盘并不会因此而停下，而是接着旋转。

因此逻辑相邻的扇区恰好在物理上也相邻，那么想处理连续逻辑扇区的时候，就不得不等磁盘转到下一个扇区，因此有可能需要很长的延迟时间。

image-20201128180104677

解决方案 1:

可以采取交替编号策略，使得逻辑上相邻的扇区在物理上不一定要相邻，而是有一定的间隔，这样的话，有可能磁头在转到下一个扇区的时候，上一个扇区的数据已经读取完毕，准备好读下一个了。

解决方案 2：

采取错位命名的策略，使得相邻盘面的相对位置相同的扇区编号不同；

image-20201128182645509

磁盘地址结构设计

思考一个问题，为什么磁盘的物理地址是（柱面号，盘面号，扇区号）而非（盘面号，柱面号，扇区号）呢？

image-20201128181834131

image-20201128181851581

根据之前的学习，我们知道磁头臂之所以要移动是为了切换柱面，也就是切换磁道号；

盘面号，柱面号，扇区号 ：这种记录方式，需要移动磁头臂

柱面号，盘面号，扇区号：这种记录方式只需要激活不同盘面的磁头，不需要移动磁头臂

而上一节我们也知道了，移动磁头笔的时间我们称为寻道时间，

磁盘管理

image-20201128193846941

磁盘初始化

磁盘初始化分为三步：低级格式化 磁盘分区 逻辑格式化

  • 低级格式化/物理格式化：将磁盘各磁道划分为扇区，扇区包含三个区域—— 头、数据区域、尾三部分

    其中，头尾用于存储管理扇区的数据结构（如扇区校验码）

  • 分区：第一步分好了扇区，第二部则是用若干柱面将扇区填充好（磁盘分盘：C 盘、D 盘、E 盘）

  • 逻辑格式化：创建文件系统 —— 创建文件系统的根目录、初始化存储管理空间所用的数据结构

image-20201128192121698

引导块

ROM：初始化程序可以放在 ROM（只读存储器）中。ROM 中的数据在厂的时候就写入了，并且之后不能再修改

ROM 一般是出厂的时候，就集成在主板上

image-20201128193411250

坏块的管理

坏块：即坏了，无法使用的扇区；属于硬件故障，OS 无法修复，针对坏块能做的只有标记坏块，避免使用到。

IO 设备

IO 设备概念和分类

image-20201130220130343

概念

  • 什么是 IO 设备?

IO 设备就是可以将数据输入到计算机，或者可以接受计算机输出数据的外部设备，是计算机中的硬件部件

UNIX 系统将外部设备抽象为一种特殊的文件，用户可以使用与文件操作相同的方式对外部设备进行操作。

比如:Write 操作——向外部设备写出数据；Read 操作:从外部设备读入数据

image-20201130214951871

分类

  • 按照使用特性分类：
    • 人机交互类外部设备：数据传输速度慢
    • 存储设备：数据传输速度快
    • 网络通信设备：数据传输速度介于两者之间

image-20201130215834935

  • 按照传输速率分类：
    • 低速设备
    • 中速设备
    • 高速设备

image-20201130215811961

  • 按照信息交换的单位分类
    • 块设备：传输速率较高，可寻址，对它可以随机地读/写任一块
    • 字符设备：传输速率较慢，不可寻址，在输入/输出时常采用中断驱动方式

image-20201130220114190

I-O 控制器

  • I/O 设备分为两部分：机械部件和电子部件（I/O 控制器、设备控制器）

机械部件

image-20201130220615924

电子部件（I/O 控制器）

image-20201202131444915

由于 CPU 无法直接控制 I/O 设备地机械部件，解决这种问题 经典方案：加一层

让电子部件充当 CPU 和 I/O 设备机械部件之间的中介，用于实现 CPU 对设备地控制

这个电子部件就是I/O 控制器，又称为设备控制器，CPU 可以控制这个 I/O 控制器，由这个来控制设备的机械部件

I/O 控制器功能

  • 接受和识别 CPU 发出的命令

    image-20201130222052883

  • 向 CPU 报告设备的状态

    image-20201130222059739

  • 数据交换

    image-20201130222106107

  • 地址识别

    image-20201130222210248

  • 数据缓冲

    I/O 设备的速率较低，而 CPU 和内存速率很高，因此在控制器中要设置一个缓冲区。（好像就是数据寄存器？）

  • 差错控制

    对于 I/O 设备传过来的数据，设备管理器还需要进行差错检测。如果有错误，就需要将差错检测码置位，并向 CPU 报告，CPU 会把这次传过来的数据作废，并重新进行一次传送，以保证数据输入的正确性。

I/O 控制器组成

image-20201130223413367

  1. 一个 I/O 控制器可能会对应多个设备
  2. 数据寄存器、控制寄存器、状态寄存器可能会有多个（如：每个控制/状态寄存器会对应一个具体的设备），且这些寄存器都需要有相应的地址，才能方便 CPU 操作。有的计算机会让这些寄存器占用内存地址的一部分，称为内存映像 I/O；另一些计算机则采用 I/O 专用地址，即寄存器独立编址。

内存映像 I/O | 寄存器独立编址

左图是内存映像（映射）I/O ，右图采用寄存器独立编址；

  • 内存映射 I/O：编址上不再区分内存单元和设备控制器中的寄存器地址，都用 N 记录；

    当地址处于 0 ~ (N - 1) 范围 被认为是内存地址，大于等于 N 时候，认为是某控制器的寄存器地址

  • 寄存器独立编址：这种方法采用特定的 I/O 指令:

    • cpu-reg是 CPU 某个寄存器 dev-no是指定设备，即控制器地址；dev-reg指定控制器中的寄存器
    • CPU 寄存器中的内容复制到控制寄存器中指令:io-store cpu-reg, dev-no,dev-reg
    • CPU 寄存器中内容存入内存某单元指令:Store cpu-reg,k

    这种方法的主要缺点就是：访问内存和访问设备需要两种不同指令。

image-20201202130124223

I/O 控制方式

image-20201202221506579

  • I/O 控制方式分为:程序直接控制方式、中断驱动方式、DMA 方式、通道控制方式

程序直接控制方式

image-20201202133214862

image-20201202133541738

  • CPU 干预的频率：非常频繁，I/O 操作开始之前、完成之后需要 CPU 接收，并且在等待 I/O 完成的过程中 CPU 需要不停地轮询检查
  • 数据传送的单位：每次读/写一个字
  • 数据的流向
    • 读操作（数据输入）：I/O 设备 → CPU（CPU 的寄存器） → 内存
    • 写操作（数据输出）：内存 → CPU（CPU 的寄存器）→ I/O 设备
  • 主要优缺点
    • 优点：实现简单。在读/写指令后，加上实现循环检查的一系列指令即可
    • 缺点：CPU 和 I/O 只能串行工作（也就是不能并行工作）；CPU 需要已知轮询检查，长期处于忙等状态,CPU 利用率低。

中断驱动方式

image-20201202134152591

  • CPU 干预的频率：每次 I/O 操作开始之前、完成之后需要 CPU 介入；等待 I/O 完成的过程中 CPU 可以切换到别的进程执行。
  • 数据传送的单位：每次读/写一个字
  • 数据的流向
    • 读操作（数据输入）：I/O 设备 → CPU（CPU 的寄存器） → 内存
    • 写操作（数据输出）：内存 → CPU（CPU 的寄存器）→ I/O 设备
  • 主要优缺点
    • 优点：与程序直接控制方式相比，在中断驱动方式中，I/O 控制器会通过中断信号主动报告 I/O 已完成，CPU 不再需要不停轮询
    • 缺点：每个字在 I/O 设备与内存之间的传输，都需要经过 CPU。而频繁的中断处理会消耗较多的 CPU 时间。

DMA 方式

image-20201202135117348

DMA 控制器

DMA 控制器包含以下部分:

  • DR（Data Register ， 数据寄存器）：暂存从设备到内存，或从内存到设备的数据。
  • MAR（Memory Address Register，内存地址寄存器）：在输入时，MAR 表示数据应放在内存中的什么位置；输出的时候，MAR 表示要输出的数据放在内存中的上面位置
  • DC（Data Counter， 数据计数器）：表示剩余要读/写的字节数
  • CR（Command Register，命令/状态寄存器）：用于存放 CPU 发来的 I/O 命令，或设备的状态信息。

image-20201202215012157

  • CPU 干预的频率：仅在传送一个或多个数据块的开始和结束时，才需要 CPU 干预
  • 数据传送的单位：每次读/写一个或多个块（ps：每次读写的只能是连续的多个块，且这些块读入内存后在内存中也必须是连续的）
  • 数据的流向（不需要流经 CPU）
    • 读操作（数据输入）：I/O 设备 → 内存
    • 写操作（数据输出）：内存 → I/O 设备
  • 主要优缺点
    • 优点：数据传输以块为单位，CPU 介入频率进一步降低。数据的传输不再需要先经过 CPU 再写入内存，数据传输效率进一步增加。CPU 和 I/O 设备的并行性得到提升。
    • 缺点：CPU 每发出一条指令，只能读/写一个或多个连续的数据块。如果要读/写多个离散存储的数据块，或者要将数据分别写到不同的内存区域时，CPU 要分别发出多条 I/O 指令，进行多次中断处理才能完成。

通道控制方式

image-20201202221208007

  • CPU 干预的频率：极低，通道会根据 CPU 的指示执行相应的通道程序，只有完成一组数据块的读/写后才需要发出中断信号，请求 CPU 的干预
  • 数据传送的单位：每次读/写一组数据块
  • 数据的流向（在通道的控制下进行）
    • 读操作（数据输入）：I/O 设备 → 内存
    • 写操作（数据输出）：内存 → I/O 设备
  • 主要优缺点
    • 优点：CPU、通道、I/O 设备可并行工作，资源利用率很高。
    • 缺点：实现复杂，需要专门的通道硬件支持

I/O 软件层次结构

大体从上至下分为:用户层软件，设备独立性软件，设备驱动程序，中断处理程序和硬件

image-20201202221809697

用户层软件

image-20201202222126442

设备独立性软件

设备独立性软件（又称为设备无关性软件）。与设备硬件特性无关的功能几乎都在这一层实现

它所主要实现的功能如下：

  1. 向上层提供统一的调用接口（如 read/write 系统调用）

  2. 设备的保护：原理类似于文件保护。设备被看作是一种特殊的文件，不同用户对于各文件的访问权限也是不同的。同理，对设备的访问权限也不一样。

  3. 差错处理：设备独立性软件需要对一些设备的错误进行处理

  4. 设备的分配与回收：很多设备是临界资源，不能同时分配给多个进程，需要回收。

  5. 数据缓冲区管理：可以通过缓冲技术屏蔽设备之间数据交换单位大小和传输速度的差异

  6. 建立逻辑设备名到物理设备名的映射关系；根据设备类型选择调用相应的驱动程序。（打印店打印的时候，一台电脑可以对应多个打印机（打印机 1，打印机 2…，这些就是逻辑设备名）

    设备独立性软件需要通过逻辑设备表（LUT,Logical Unit Table）来确定逻辑设备对应的物理设备；并找到该设备对应的设备驱动程序

    image-20201202223154354

设备驱动程序

由于不同的 I/O 设备有不同的硬件特性，因此需要根据设备不同硬件特性提供相应的驱动程序。

这些驱动程序将上层传达下来的命令翻译成下层特定设备能听得懂的操作。

image-20201203161331778

中断处理程序

image-20201203161549430

硬件

  • 执行 I/O 操作，由机械部件、电子部件组成。

I/O 核心子系统

I/O 核心子系统属于操作系统的内核部分；

I/O 调度

  • I/O 调度:用某种算法确定一个好的顺序来处理各个 I/O 请求。

  • 如:磁盘调度(先来先服务算法、最短寻道优先算法、SCAN 算法、C-SCAN 算法、LOOK 算法、C-LOOK 算法)。当多个磁盘 I/O 请求到来时,用某种调度算法确定满足 I/O 请求的顺序。
    冋理,打卬机等设备也可以用先来先服务算法、优先级算法、短作业优先等算法来确定 I/O 调度顺序。

设备保护

操作系统需要实现文件保护功能,不同的用户对各个文件有不同的访问权限(如:只读、读和写等在 UNIX 系统中,设备被看做是一种特殊的文件,每个设备也会有对应的 FCB。当用户请求访问某个设备时,系统根据 FCB 中记录的信息来判断该用户是否有相应的访问权限,以此实现“设备保护”的功能。(参考“文件保护”小节)

假脱机技术（SPOOLing 技术）

image-20201203171706471

要知道什么是假脱机技术，就得先了解脱机技术：

  • 脱机 IO 技术：事先将装有用户程序和数据的纸带装入纸带输入机，在一台外围控制机的控制下，把纸带上的数据输入到磁带上。当 CPU 需要这些程序和数据时，再从磁带上高速地调入内存；

image-20201203164159076

那么假脱机技术又是什么呢?

在脱机技术中，用户程序和数据是预先存在了磁带中，进而通过控制机来输入和输出数据，

因此假脱机技术就是仿造这种方式：

  • 用 输入进程 模拟 脱机输入时的外围控制机

  • 用 输出进程 模拟 脱机输出时的外围控制机

  • 用 输入井 模拟 脱机输入时的磁带，用于收容 I/O 设备输入的数据

  • 用 输出井 模拟 脱机输出时的磁带，用于收容用户进程输出的数据

image-20201203165450142

在内存中不仅仅有输入和输出进程，还有输入缓冲区和输出缓冲区

缓冲区相当于一个中转站，给数据传输的进行喘一口气

  • 输入缓冲区：暂存从输入设备输入的数据，之后转存到输入井中
  • 输出缓冲区：暂存从输出井送进来的数据，之后再传送到输出设备上

image-20201203165501947

共享打印机原理

  • 独占式设备一一只允许各个进程串行使用的设备。一段时间内只能满足一个进程的请求
  • 共享设备一一允许多个进程“同时”使用的设备(宏观上同时使用,微观上可能是交替使用)。可以同时满足多个进程的使用请求。

image-20201203171351378

通过这种方式，虽然系统中只有一台打印机，但每个进程提出打印请求的时候，系统都会为在输出井中为其分配一个存储区（相当于分配了一个逻辑设备），使得每个用户进程都觉得自己在独占一台打印机，从而实现对打印机的共享。

SPOOLing 技术把一台物理设备虚拟成了逻辑上的多台设备，可将独占式设备改造成了共享设备。

设备的分配与回收

image-20201203180248315

设备分配时应考虑的因素

考虑因素分三大因素:设备的固有属性、设备分配算法、设备分配中的安全性

设备固有属性因素

设备的固有属性可分为三种：独占设备、共享设备、虚拟设备

独占式设备：一个时间段只能分配给一个进程
共享式设备：可同时分配给多个进程使用，各个进程往往是宏观上同时共享使用设备，微观上交替使用。
虚拟设备：采用假脱机技术将独占式设备改造成虚拟共享设备，可同时分配给多个进程使用。（如采用 SPOOLing 技术实现的共享打印机）

设备分配算法因素

先来先服务算法、短作业优先算法，优先级高优先算法等。

设备分配安全性因素

从进程运行的安全性上考虑，设备分配有两种方式：

  • 安全分配方式：为进程分配一个设备后就将进程阻塞，本次 IO 完成后才将这个进程唤醒。(打印机例子)
    • 优点：这种方式是安全的破坏了“请求和保持条件”，不会发生死锁。
    • 缺点：但是对于一个进程来说，CPU 和 IO 设备只能串行工作。系统资源利用率低，进程执行效率低。
  • 不安全分配方式：进程发出 IO 请求后，系统为其分配 IO 设备，进程可以继续执行，之后还可以发出新的 IO 请求。只有某个 IO 请求得不到满足的情况下才将进程阻塞。
    • 优点：进程的计算任务和 I/O 任务可以并行处理，使进程迅速推进
    • 缺点：有可能发生死锁（就需要：死锁避免、死锁的检测和解除）

设备分配方式

分为：静态分配和动态分配 两种分配方式

  • 静态分配：进程运行前为其分配全部所需资源，运行结束后归还资源（破坏了请求和保持条件，不会发生死锁）
  • 动态分配：进程运行过程中动态申请设备资源

设备分配管理中的数据结构

设备与控制器通道之间的关系。
一个通道可以有多个控制器，一个控制器又能控制多台设备。所以他们三者之间是一对多的关系，也就可以用树状结构来描述。image-20201203174336130

设备控制表 DCT

  • 设备控制表 - Device Control Table - DCT

image-20201203174727508

控制器控制表 COCT

  • 控制器控制表 - Controller Control Table - COCT

image-20201203174925206

通道控制表 CHCT

  • 通道控制表 - Channel Control Table - CHCT

image-20201203175015208

系统设备表 SDT

  • 系统设备表 - System Device Table - SDT

image-20201203175109971

设备分配的步骤

  • 自下到上的查表，分配
  1. 按照进程请求的物理设备名查找SDT（系统设备表）
  2. 根据系统设备表找到DCT（设备控制表），若设备忙碌则将进程挂到设备等待队列中，不忙碌则将设备分配给进程。
  3. 根据设备控制表找到COCT（控制器控制表），若控制器忙碌则将进程 PCB 挂到控制器等待队列中，不忙碌则将控制器分配给进程。
  4. 根据COCT（控制器控制表）找到CHCT（通道控制表），若通道忙碌则将 PCB 挂到通达等待队列中，不忙碌则将通道分配给进程。

只有设备、控制器、通道三者都分配成功时，这次设备分配才算成功，之后便可以启动 IO 设备进行数据传送

缺点：

  1. 用户编程时必须使用物理设备名，底层细节对用户不透明，不方便编程
  2. 若换了一个物理设备，则程序无法执行
  3. 若进程请求的物理设备正在忙碌，则即使系统中还有同类型的设备，进程也必须阻塞等待

设备分配的改进方式

改进思想：通过建立逻辑设备名与物理设备名的映射机制，用户编程只需要提供逻辑设备名就可以找到物理设备名。

① 根据进程请求的逻辑设备名查找 SDT（注：用户编程时提供的逻辑设备名其实就是“设备类型”）
② 查找 SDT，找到用户进程指定类型的、并且空闲的设备，将其分配给该进程。操作系统在逻辑设备表（LUT）中新增一个表项。
③ 根据 DCT 找到 COCT，若控制器忙碌，则将 PCB 挂到控制器等待队列中；不忙碌，则将控制器分配给进程。
④ 根据 COCT 找到 CHCT，若通道忙碌，则将进程 PCB 挂到通道等待队列中，不忙碌则将通道分配给进程

上述步骤提到了一个逻辑设备表 LUT。那么什么是 LUT 呢？

还记得改进思想吗？建立映射，这个 LUT 就是用来建立映射（将逻辑设备名映射为物理设备名）的。

用户编程时使用逻辑设备名申请设备，操作系统负责实现从逻辑设备名到物理设备名的映射。LUT（逻辑设备表）
如果整个系统只有一张LUT：各个用户所用的逻辑设备名不能重复，如果每个用户一张LUT：各个用户的逻辑设备名可以重复。

image-20201203175918544

上面步骤是第一次通过逻辑设备名申请使用一个设备，假如之后进程再以相同的逻辑设备名来请求使用设备的话:

image-20201203180225450

缓冲区管理

image-20201204165851742

缓冲区概述

缓冲区是一个存储区域，可以由专门的硬件寄存器组成，也可利用内存作为缓冲区。

使用硬件作为缓冲区的成本较高，容量小，一般仅用在对速度要求非常高的场合（如存储器管理中所用的联想寄存器，由于对页表的访问频率极高，因此使用速度很快的联想寄存器来存放页表项的副本）

一般情况，更多是利用内存作为缓冲区，设备独立性软件的缓冲区管理就是要组织管理好这些缓冲区。

缓冲区作用

缓冲区有什么作用呢？

  1. 缓和 CPU 与 I/O 设备之间速度不匹配的矛盾
  2. 减少对 CPU 的中断频率，放宽对 CPU 中断相应时间的限制
  3. 解决数据粒度不匹配的问题
  4. 提高 CPU 与 I/O 设备之间的并行性

image-20201203215628038

缓冲区管理策略

单缓冲

背景/什么时候需要用到缓冲：假设某用户进程请求某种块设备读入若干块的数据

此时若采用单缓冲的策略：操作系统会在主存中为其分配一个缓冲区

其中要注意:

  1. 当缓冲区数据非空（满）时，不能往缓冲区冲入数据，只能从缓冲区把数据传出
  2. 当缓冲区为空时，可以往缓冲区冲入输入，但必须把缓冲区充满之后，才能从缓冲区当数据传出

image-20201204160730604

假设输入数据的时间为T，CPU 处理数据的时间为C，缓冲区传送数据到工作区的时间为M

若T>C（输入数据时间比 CPU 处理时间开销长）：由限制 2我们可以知道 CPU 处理完数据后并不能将下一块数据从缓冲区传送到工作区，必须等缓冲区中冲满数据才可以进行下一组数据的处理

若T<C（CPU 处理时间比输入数据时间开销长）：由限制 1我们可以知道当缓冲区的数据被冲满后，并不能继续冲入下一块数据，必须等待 CPU 处理结束后，才能将数据从缓冲区传送到工作区。

image-20201204155830464

双缓冲

背景/什么时候需要用到缓冲：假设某用户进程请求某种块设备读入若干块的数据

此时若采用单缓冲的策略：操作系统会在主存中为其分配两个缓冲区

image-20201204162120223

假设初始状态为：工作区空，其中一个缓冲区满，另一个缓冲区空

假设输入数据的时间为T，CPU 处理数据的时间为C，缓冲区传送数据到工作区的时间为M

  • 若T > C + M（数据输入时间大于 CPU 处理时间加上缓冲区传送数据时间）

    首先满缓冲区开始传送数据到工作区，交由 CPU 处理；传送数据开始的时候，设备向空缓冲区冲入数据；新的满缓冲区向工作区传送数据，交由 CPU 处理；同理，另一个空缓冲区也同步冲入数据；由此反复…

处理一块数据的平均用时为 T

image-20201204163502759

  • 若T < C + M（数据输入时间小于 CPU 处理时间加上缓冲区传送数据时间）

    设备向空缓冲区输入数据和满缓冲区向工作区传数据同步进行，当然了，后者进行完后 CPU 会接力完成数据处理；

    我们知道，由于限制 1的约束，有可能做不到 2T = 2M + C，也就是说，一个缓冲区是满的，另一个还有点参与数据没取完，就必须等待另一个 M 的进行。

处理一块数据的平均用时为 C + M

image-20201204163508555

综合来说：采用双缓冲策略，处理一个数据块的平均耗时为 Max (T, C+M)

使用单/双缓冲在通信时的区别

image-20201204164935982

循环缓冲区

image-20201204165050655

缓冲池

缓冲池由系统中共用的缓冲区组成。这些缓冲区按使用状况可以分为：空缓冲队列、装满输入数据的缓冲队列（输入队列）、装满输出数据的缓冲队列（输出队列）。

另外，根据一个缓冲区在实际运算中扮演的功能不同，又设置了四种工作缓冲区：

  • 用于收容输入数据的工作缓冲区（hin）
  • 用于提取输入数据的工作缓冲区（sin）
  • 用于收容输出数据的工作缓冲区（hout）
  • 用于提取输出数据的工作缓冲区（sout）

操作系统根据不同的进程请求，将不同队列中的缓冲区提取一块出来 作为上述四种工作缓冲区的一种；

然后将其交付给程用于执行，缓冲区的状态将会进行一定的改变，之后会挂回到对应状态的队列队尾；

image-20201204165820255