操作系统

cccs7 Lv5
  2023-01-04 17:02:22 2023-01-04 17:02 Created   2023-06-29 23:11:40 2023-06-29 23:11 Updated      65.5k Words  221 Mins  

#操作系统

南京大学 - 蒋炎岩老师 操作系统的设计与实现

哈尔滨工业大学 - 李治军老师 操作系统

王道考研 - 408操作系统

参考教材： 现代操作系统 原书第四版 **王道考研408 - 操作系统教材 **

操作系统（Operating System，简称 OS）是一种控制和管理计算机硬件和软件资源的系统软件，它充当计算机系统与用户之间的接口，管理计算机的硬件、软件和资源，并提供基本的服务和功能，使计算机能够执行各种应用程序。

操作系统通常执行以下几个主要功能：

  1. 管理计算机的硬件资源，包括处理器、内存、硬盘、输入输出设备等。

  2. 提供用户和应用程序的接口，允许用户和应用程序与计算机系统进行交互。

  3. 管理和分配计算机的软件资源，包括操作系统本身和各种应用程序。

  4. 提供安全和保护机制，以确保计算机系统的安全性和稳定性。

  5. 提供各种系统服务和功能，如文件管理、网络通信、进程管理、内存管理等。

常见的操作系统包括 Windows、macOS、Linux、Unix 等。它们有各自的特点和优势，在不同的场景和需求下可以选择不同的操作系统。

操作系统的发展可以分为几个阶段，最早的操作系统是单道批处理系统，它能够处理一批作业，但只能处理一个作业，没有多任务处理能力。后来出现了多道批处理系统，它允许多个作业同时进入系统，提高了系统的效率。随着计算机技术的发展，出现了分时系统和实时系统，提供了更加高效和实时的计算机服务。现代操作系统还包括了图形用户界面、多任务处理、虚拟内存、网络通信等功能，提供了更为丰富的计算机服务和应用。

总体而言，操作系统是计算机系统的核心组成部分，它提供了基本的服务和功能，使计算机能够执行各种应用程序和任务。操作系统的不断发展和改进，为计算机技术的进步和发展提供了坚实的基础。

计算机系统概述

知识框架

image-20230520195652009

操作系统的概念、功能和目标

知识总览

操作系统的概念、功能和目标

  • 概念（定义）
    • 什么是 操作系统
  • 功能和目标
    • 操作系统要做些什么

操作系统的概念

image-20230520200945754

操作系统（Operating System，OS） 是指 控制和管理 整个计算机系统的 $硬件和软件^1$资源，并合理地组织调度计算机的工作和资源的分配；以 $提供给用户和其他软件方便的接口和环境^2$；它是计算机系统中 最基本的 $系统软件^3$

:one: 操作系统是系统资源的管理者

:two:向上层提供方便易用的服务

:three:是最接近硬件的一层软件

功能和目标

操作系统的功能和目标： 作为系统资源的管理者

提供的功能

  • 处理机管理
  • 存储器管理
  • 文件管理
  • 设备管理

目标

  • 安全、高效

补充：执行一个 程序之前，需要将该程序放到内存中，才能被 CPU 处理

image-20230520201236144
向上层提供方便易用的服务

操作系统的功能和目标： 向上层提供方便易用的服务

封装思想

操作系统把一些 丑陋的硬件功能封装成简单易用的服务，使用户能更方便地使用计算机，用户无需关心底层 硬件的原理，只需要对操作系统发出命令即可

GUI

图形化用户接口（Graphical User Interface）

用户可以使用形象的图形界面进行操作，而不需要记忆复杂的命令、参数

联机命令接口

联机命令接口 = 交互式 命令接口

特点：用户说一句，系统就跟着做一句

脱机命令接口

脱机命令接口 = 批处理 命令接口

特点：用户说一堆，系统跟着做一堆

eg: bat 脚本

image-20230520205817531
程序接口

可以在 程序中进行 系统调用 来使用程序接口。普通用户不能直接使用程序接口，只能通过程序代码 间接 调用

image-20230520205945357
总结
image-20230520210338199
作为最接近硬件的层次
image-20230520210423627

需要实现 对硬件机器的扩展

没有任何软件支持的 计算机成为 裸机 。在 裸机上安装的操作系统可以提供资源管理的功能和方便用户的服务功能，将裸机改造成更强、使用更方便的机器

通常把 覆盖了软件的机器 称为 扩充机器 ，又称之为 虚拟机

操作系统对硬件机器的扩展： 将 CPU 、内存、键盘、显示器、磁盘 等的硬件结合起来，让各种硬件能够相互协调配合，实现更多复杂的功能

普通用户不用关心这些硬件在底层是怎么组织起来工作的，只需直接使用操作系统提供的接口即可

知识回顾与重要考点

image-20230520211139824

操作系统的特征

知识总览

image-20230520212301869

并发 与 并行

指两个或者多个事件在同一时间间隔内发生。 这些事情 宏观上是同时发生的，但 微观上是交替发生的。

易混 ： 并行： 指两个或 多个时间在同一时刻同时发生

并发和并行是计算机领域中经常被提到的两个概念，它们都与多任务处理有关，但是含义却不同。

并发指的是在同一时间段内，有多个任务在交替执行，这些任务之间不一定是同时执行的，而是通过操作系统的调度算法分时使用 CPU 资源，让用户感觉多个任务同时在运行。例如，现在常见的多线程编程就是一种并发的实现方式。

而并行是指在同一时刻，有多个任务同时执行，这些任务可以通过多个处理器或多个计算机实现并行执行。并行处理通常用于处理大规模的数据或者需要进行高性能计算的任务，例如，科学计算、图像处理和机器学习等。

可以说，并发是在同一个处理器上同时运行多个任务，而并行是在多个处理器上同时执行多个任务。并发通常是通过时间片轮转等算法实现，而并行则需要更多的硬件资源和更复杂的算法。

总之，虽然并发和并行都是实现多任务处理的方法，但是它们的实现方式和应用场景是不同的。并发主要针对单个处理器的多任务处理，通过时间片轮转等算法实现，应用于多线程编程、操作系统等领域；而并行主要针对多处理器或多计算机的多任务处理，通过分布式算法等实现，应用于高性能计算、科学计算等领域。

image-20230520212635124

操作系统的并发性 指计算机系统中 “同时” 运行着多个程序，这些程序宏观上看是同时运行着的，而微观上看 是 交替运行的

操作系统就是伴随着 “多道程序技术” 而出现的。因此，操作系统和程序并发是一起诞生的

注意： **单核 CPU ** 同一时刻只能执行 一个程序，各个程序只能 并发 执行

多核CPU 同一时刻可以同时执行 多个程序，多个程序可以 并行地 执行

image-20230520213110286

共享

共享即 资源共享，是指系统中的资源可供内存中多个并发执行的进程共同使用

image-20230520213342336

所谓的 “同时” 往往是宏观的，而在微观上，这些进程可能是交替的对该资源进行访问的（即 分时共享）

image-20230520213447584
并发和共享的关系

并发性是指计算机系统中同时存在着多个运行着的程序

共享性是指系统中的资源可供内存中运行着的多个程序共同使用

使用 QQ 发送A，同时微信发送B

  1. 两个进程正在并发执行（并发性）
    • 如果失去并发性，则系统中只有一个程序正在执行，则共享性失去存在的意义
  2. 需要共享地访问硬盘资源
    • 如果 失去共享性，则QQ 和 微信 不能同时访问硬盘资源，就无法实现同时发送文件，也就无法并发

虚拟

虚拟是指把一个物理上的实体 变成若干个逻辑上的对应物。物理实体（前者）是 实际存在的，而逻辑上对应物（后者）是用户感受到的、image-20230520214139041

虚拟技术中的 “时分复用技术” 和 “空分复用技术”

虚拟技术是指通过软件或硬件技术，将一个物理资源分割成多个逻辑资源，从而实现资源共享和提高资源利用率的技术。在虚拟技术中，空分复用技术和时分复用技术是两种常见的资源复用技术。

空分复用技术（Space Division Multiplexing，简称SDM）是指将一个物理资源按照空间维度进行分割，将不同的逻辑资源分配到不同的物理空间中，从而实现资源的共享。例如，在服务器虚拟化中，可以将一个物理服务器划分为多个虚拟服务器，在不同的虚拟服务器上运行不同的应用程序，从而提高服务器的利用率和资源利用效率。

时分复用技术（Time Division Multiplexing，简称TDM）则是将一个物理资源按照时间维度进行分割，将不同的逻辑资源分配到不同的时间段中，从而实现资源的共享。例如，在计算机网络中，可以将一个物理网络线路按照时间分割为多个时间段，在不同的时间段内传输不同的数据，从而提高网络带宽的利用率和数据传输效率。

需要注意的是，空分复用技术和时分复用技术都是通过将一个物理资源分割成多个逻辑资源来实现资源的共享和提高资源利用效率，但是它们的分割维度不同。空分复用技术是按照空间维度进行分割，将逻辑资源分配到不同的物理空间中，而时分复用技术是按照时间维度进行分割，将逻辑资源分配到不同的时间段中。在实际应用中，需要根据具体的场景选择合适的技术来实现资源的共享和提高资源利用效率。

image-20230520214431521

异步

异步是指，在多道程序环境下，允许多个程序并发执行，但由于资源有限，进程的执行并不是一贯到底的，而是走走停停，以 不可预知的 速度向前推进，这就是 异步性

如果失去了 并发性，即系统只能串行的运行各个程序，那么每个程序的执行会一贯到底。 只有系统拥有并发性，才有可能导致异步性

异步性是一种计算机编程中常用的概念，它指的是在程序执行过程中，不需要等待一个操作完成才能进行下一个操作，而是可以同时执行多个任务，程序可以在等待某些操作完成的同时，继续执行其他任务，从而提高程序的执行效率和响应速度。

异步编程通常使用回调函数、事件处理程序、协程等技术来实现。例如，当需要从网络上获取数据时，如果使用同步方式，程序需要等待数据下载完成才能继续执行下面的代码，这可能会导致程序出现卡顿或者阻塞的情况。而异步方式则可以在数据下载的同时，继续执行下面的代码，当数据下载完成后，再回调相应的处理函数进行数据处理。这种方式可以避免程序的阻塞和卡顿，提高程序的响应速度和执行效率。

在异步编程中，需要注意处理异步操作的返回值和异常等问题，同时需要考虑多个异步操作之间的依赖关系和执行顺序。总之，异步性是指程序可以同时执行多个任务，不需要等待一个操作完成才能进行下一个操作的特性。异步编程可以提高程序的响应速度和执行效率，但也需要注意处理异步操作的返回值和异常，以及多个异步操作之间的依赖关系和执行顺序。

知识回顾与重要考点

image-20230521102636700

操作系统的发展和分类

知识总览

image-20230521103013433

手工操控阶段

image-20230521103057849

主要缺点： 用户独占全机、人机速度矛盾导致资源利用率低

批处理阶段

单道批处理系统

引入 脱机输入/输出技术 (用外围机 + 磁带) ，并由 监督程序 负责控制作业的输入、输出

image-20230521103303121

主要优点： 缓解了一定程度上的人机速度矛盾，资源利用率有所提升

主要缺点： 内存中仅有一道程序运行， 只有该程序结束之后才能调入下一道程序。 CPU 有大量的时间是在空闲等待 I/O 完成。资源利用率依然很低

image-20230521103700724
多道批处理系统
image-20230521104042666

每次往内存中读入多道程序。操作系统正式诞生，用于支持多道程序并发运行

主要优点：多道程序 并发执行，共享 计算机的资源。 资源利用率大幅增加 ，CPU 和其他资源更能保持 忙碌状态，系统吞吐量增大

主要缺点： 用户响应时间长， 没有人机交互功能（用户提交自己的作业之后，就只能等待计算机处理完成，中间不能 控制自己的程序执行）

分时操作系统

计算机 以 时间片 为单位 轮流为各个用户/作业 服务，各个用户可以通过终端与计算机进行交互。

主要优点： 用户请求可以被及时响应，解决了人机交互的问题。允许多个用户同时使用一台计算机，并且用户对计算机的操作相互独立，感受不到别人的存在

主要缺点： 不能优先处理一些紧急的任务。 操作系统对于各个用户/作业 都是完全公平的，循环地 为每个用户/作业 服务一个时间片，不区分任务的紧急性

实时操作系统image-20230521104508838

主要优点： 能够优先响应一些紧急 任务，某些紧急任务不需时间片排队

在 实时操作系统的控制下，计算机系统接收到外部信号后及时进行处理，并且 要在严格的时限内处理完事件。实时操作传统的 主要特点就是 及时性和可靠性

其他几种操作系统

网络操作系统

是伴随着 计算机网络的发展而诞生的，能把网络中各个计算机有机的结合起来，实现数据传送等功能，实现网络中各种资源的共享（如文件共享）和各台计算机 之间的通信

分布式操作系统

主要特点是 分布性和并行性。系统中的各台计算机地位相同， 任何工作都可以分布在这些计算机上，由他们并行、协同的完成这个任务

个人计算机操作系统

如 Windows、MacOS。方便个人使用

知识回顾与重要考点

image-20230521105148016

操作系统的运行机制

知识总览

image-20230521110449386

程序是如何运行起来的

image-20230521110616938

程序运行的过程其实就是 CPU 执行 一条一条的机器指令的 过程

指令就是 CPU（处理器）能识别、执行的 最基本的命令

很多人习惯把 Linux、Windows、MacOS 的 “小黑框” 中使用的命令也称为 “指令”，其实这是 “交互式命令接口”，本节中的指令 指的是 二进制机器指令

交互式命令接口（Interactive Command Interface，简称ICI）是一种计算机命令行界面，它允许用户通过键盘输入命令，并实时地查看命令的输出结果。ICI主要用于用户与计算机交互，执行各种操作和任务，如文件管理、系统配置、软件安装等。

ICI通常包括两个主要部分：命令提示符和命令执行器。命令提示符是一个特殊的符号或字符串，通常表示系统已经准备好接收用户输入的命令，例如在Windows系统中的命令提示符为 “C:>” 或者 “C:\Users\username>” 等。命令执行器则是用于执行用户输入的命令的程序组件，它将用户输入的命令解析并执行相应的操作，并将结果输出到屏幕上。

内核程序 Vs 应用程序

我们普通程序员写的就是 $应用程序^1$

微软和苹果 有一部分人负责实现操作系统，他们写的是 $内核程序^2$。 由很多内核程序 组成了 操作系统内核，或者 简称 内核（kernel）。

:one:：应用程序 只能使用 “非特权指令”

:two::操作系统内核作为 “管理者”，有时会让 CPU 执行一些 “特权指令”，这些指令影响重大，只允许 管理者 – 即操作系统内核来使用

特权指令 与 非特权指令

在计算机系统中，特权指令和非特权指令是两种指令的分类。特权指令是只能由操作系统或者其它特定的系统软件运行的指令，而非特权指令则可以被普通的程序运行。

特权指令通常具有访问系统资源、修改系统状态等特殊权限，例如控制中断、修改内存映射表、访问硬件设备等。这些指令需要特定的权限和访问控制才能执行，因此只能由操作系统或者其它特定的系统软件运行。这样可以保证系统的安全性和稳定性，防止用户程序对系统进行非法操作。

与特权指令相对应的是非特权指令，它是可以被普通的程序直接执行的指令，例如算术运算、逻辑运算、内存读写等。这些指令不需要特殊的权限和访问控制，可以被用户程序直接调用，用于完成各种计算和数据处理任务。

需要注意的是，特权指令和非特权指令的执行权限是由处理器硬件和操作系统内核共同控制的。处理器硬件通过特权级别（Privilege Level）来划分指令的执行权限，通常分为用户态和内核态两种特权级别。用户态只能执行非特权指令，而内核态可以执行所有的指令，包括特权指令和非特权指令。操作系统内核通过特殊的机制来控制程序的特权级别和指令的执行权限，保证特权指令只能由操作系统或者其它特定的系统软件运行。

总之，特权指令和非特权指令是计算机指令的分类，特权指令只能由操作系统或者其它特定的系统软件运行，具有访问系统资源、修改系统状态等特殊权限；而非特权指令则可以被普通的程序直接执行，用于完成各种计算和数据处理任务。特权指令和非特权指令的执行权限是由处理器硬件和操作系统内核共同控制的，通过特殊的机制来保证系统的安全性和稳定性。

内核 是操作系统最重要最核心的部分，也是 最接近硬件的部分，甚至说，一个操作系统有一个内核就够了，操作系统的功能未必都在内核中，如 图形化页面 GUI

内核态与用户态

CPU 有两种状态： 内核态和用户态

内核态和用户态是指计算机处理器的运行状态。在计算机系统中，处理器可以运行在两种不同的特权级别（Privilege Level）下，分别是内核态和用户态。

内核态是处理器运行在最高特权级别下的状态，它可以访问系统的所有资源和硬件设备，并且可以执行所有指令，包括特权指令和非特权指令。在内核态下，操作系统内核可以直接访问系统资源和硬件设备，并且可以进行各种系统管理和控制任务。

用户态是处理器运行在较低特权级别下的状态，它只能访问用户空间的资源和数据，并且只能执行非特权指令。在用户态下，用户程序无法直接访问系统资源和硬件设备，需要通过操作系统提供的系统调用接口来访问。

操作系统内核在运行时可以切换处理器的特权级别，将处理器从用户态切换到内核态，从而让内核可以访问系统资源和硬件设备，并进行各种系统管理和控制任务。例如，在用户程序需要进行文件读写、网络通信等操作时，需要通过系统调用接口向操作系统内核发起请求，在内核态下执行相应的操作，然后再将结果返回给用户程序。

需要注意的是，由于内核态具有更高的特权级别和更大的系统权限，因此在内核态下执行的操作需要谨慎处理，避免对系统的安全性和稳定性产生影响。同时，由于从用户态切换到内核态需要进行上下文切换，会带来一定的开销，因此需要尽量减少内核态的使用，提高系统的运行效率和响应速度。

总之，内核态和用户态是指计算机处理器的运行状态，内核态具有更高的特权级别和更大的系统权限，可以访问系统的所有资源和硬件设备，并执行所有指令，包括特权指令和非特权指令；用户态则只能访问用户空间的资源和数据，并且只能执行非特权指令。操作系统内核可以在运行时切换处理器的特权级别，将处理器从用户态切换到内核态，从而让内核可以访问系统资源和硬件设备，并进行各种系统管理和控制任务。

处于内核态时，说明此时正在运行的是内核程序，此时可以执行特权指令

处于用户态时，说明此时正在运行的是应用程序，此时只能执行非特权指令

拓展： CPU 中有一个 寄存器 叫 程序状态字寄存器（PSW），其中有个二进制位，1表示 内核态，0 表示用户态

别名： 内核态 = 核心态 = 管态； 用户态 = 目态

操作系统内核在让出 CPU 之前，会 用一条特权指令把 PSW 的标志位设置为 用户态

非法事件会引发 中断信号，CPU 检测到中断信号后，会立即 变为 核心态，并停止运行当前的应用程序，转而运行处理中断信号的内核程序

内核态、用户态的切换

内核态 -> 用户态： 执行一条特权指令 —— 修改 PSW 的标志位 为用户态，这个动作 意味着操作系统将主动让出 CPU 使用权

用户态 -> 核心态：由 中断 引发，硬件自动完成变态过程，触发中断信号意味着操作系统将强制夺回 CPU 的使用权

除了 非法使用特权指令外，还有很多事情会触发 中断信号。一个共性是 但凡需要操作系统介入的地方，都会触发中断信号

image-20230522100402149

知识回顾与重要考点

image-20230522100449684
两种指令、两种处理器状态、两种程序

新的问题：

有的指令人畜无害。比如 加减等这些普通的运算指令

有的指令有很高的权限，比如内存清零 指令，如果用户程序可以 使用这个指令，就意味着一个用户可以将其他用户的内存数据随意清零，这样做 显然是很危险的

image-20230522100833914

问题： CPU 如何判断当前是否可以 执行特权指令

image-20230522100955816

PSW 的标志位 反映当前状态

image-20230522101525226
操作系统内核
image-20230522101622254

内核 是计算机配置的 底层软件，是操作系统最基本、最核心的部分

实现操作系统内核功能的那些程序就是 内核程序

image-20230522101741196 image-20230522101827252
操作系统的体系结构
image-20230522101904323
知识回顾与重要考点
image-20230522102019074

中断和异常

知识总览

image-20230522102529191

中断和异常是计算机系统中的两种事件处理机制。

中断是一种硬件事件，通常由外部设备（如键盘、鼠标、网卡等）向处理器发出信号，请求处理器暂停当前执行的程序，转而执行相应的中断处理程序。中断分为外部中断和内部中断两种类型。外部中断是由外部设备发出的中断请求，例如键盘输入、网络数据传输等；内部中断则是由处理器内部的事件触发的中断请求，例如除零、内存访问异常等。

异常是一种软件事件，通常由正在执行的程序产生，例如访问未分配的内存、执行非法指令等。异常也会导致处理器暂停当前执行的程序，转而执行相应的异常处理程序。在处理异常时，处理器通常会尝试修复异常导致的错误，并恢复程序的执行状态，使程序能够继续执行。

中断和异常的处理机制都可以让处理器在执行程序时及时地响应外部和内部事件，并进行相应的处理。两者的主要区别在于中断是由硬件事件触发，而异常是由软件事件触发。此外，处理中断和异常的处理程序也不同。中断处理程序通常需要处理外部设备的输入输出、网络通信等任务，而异常处理程序则需要处理程序的错误、内存访问异常等。同时，中断处理程序和异常处理程序都需要保证系统的安全性和稳定性，避免对系统产生负面影响。

总之，中断和异常是计算机系统中的两种事件处理机制。中断是由硬件事件触发的事件处理机制，而异常是由软件事件触发的事件处理机制。处理中断和异常的处理程序不同，需要针对不同的事件类型进行处理，保证系统的安全性和稳定性。

image-20230522104559935

中断的作用

中断会使 CPU 从 用户态 变成 核心态，使操作系统重新夺回 对 CPU 的控制权

CPU 上会运行两种程序，一种是 $OS kernel程序^1$ ，一种是 应用程序

:one: : 是整个系统的管理者

在合适的情况下，操作系统会把 CPU 的使用权主动的 让给应用程序

“中断 ” 是 让操作系统内核夺回 CPU 使用权的 唯一途径

如果没有中断机制，那么一旦应用程序上 CPU 运行，CPU 就会一直运行这个程序， 如果如此，就没有 并发 了。

内核态 - > 用户态：  执行一条 特权指令 —— 修改 PSW 标志位 为 用户态，这个动作意味着 操作系统将主动让出 CPU 使用权

用户态 -> 内核态： ： 由 中断 引发，硬件自动完成变态过程，触发中断信号 意味着操作系统将强行夺走 CPU 的使用权

中断的类型

image-20230522103659558
内中断

若当前执行的指令是非法的，则会引发 中断信号

有时候，应用程序想请求 操作系统内核的服务，此时会执行一条 特殊的指令 —— 陷入指令，该 指令会引发一个 内部中断信号。

执行 “陷入指令”，意味着应用程序主动的将 CPU 的使用权交给了 操作系统内核。 系统调用就是通过 陷入指令 完成的

内中断（也称为软件中断）是一种由正在执行的程序产生的中断。内中断通常是由程序中的指令执行产生的，例如执行系统调用、软件中断指令等。与硬件中断不同，内中断不需要外部设备的干预，可以直接由程序产生。

在处理器中，内中断通常通过中断向量表来进行处理。中断向量表是一张由处理器硬件预定义的表格，用于存储中断处理程序的入口地址。当程序产生内中断时，处理器会根据中断向量表中相应的入口地址，跳转到对应的中断处理程序中执行，处理完毕后再返回到原来的程序中继续执行。

内中断通常用于实现操作系统的各种功能，例如系统调用、异常处理等。在进行系统调用时，用户程序通过软中断指令（如int 0x80）向操作系统发起请求，操作系统内核会根据请求的类型，调用相应的系统调用处理程序进行处理。在进行异常处理时，程序产生异常（如除零异常、内存访问异常等），处理器会暂停当前程序的执行，跳转到相应的异常处理程序中进行处理。

需要注意的是，由于内中断是由程序直接产生的，因此程序需要保证内中断的正确性和安全性，避免对系统产生负面影响。同时，由于内中断的处理通常需要进行上下文切换和状态保存等操作，因此需要尽量减少内中断的产生，提高系统的运行效率和响应速度。

总之，内中断是一种由正在执行的程序产生的中断。内中断不需要外部设备的干预，可以直接由程序产生。内中断通常用于实现操作系统的各种功能，例如系统调用、异常处理等。在进行内中断处理时，处理器会根据中断向量表中相应的入口地址，跳转到对应的中断处理程序中执行，处理完毕后再返回到原来的程序中继续执行。

外中断

每一条指令执行结束时，CPU 都会例行检查 是否有外中断信号，与当前执行的 指令无关， 中断信号来自 CPU 外部

image-20230522104344367

外中断（也称为硬件中断）是一种由外部设备产生的中断。外中断通常是由外设（例如键盘、鼠标、网卡等）向处理器发出信号，请求处理器暂停当前执行的程序，转而执行相应的中断处理程序。

在处理器中，外中断通常通过中断控制器（如8259A芯片）来进行管理和处理。中断控制器负责接收和转发外设的中断请求信号，并将中断请求转发到相应的处理器核心上进行处理。在处理外中断时，处理器会根据中断向量表中相应的入口地址，跳转到对应的中断处理程序中执行，处理完毕后再返回到原来的程序中继续执行。

外中断通常用于实现计算机系统与外部设备的交互。例如，在进行网络通信时，网卡会向处理器发送中断请求，通知处理器有新的数据包到达；在进行输入输出操作时，键盘、鼠标等外设也会向处理器发送中断请求，通知处理器有新的输入事件发生。处理器在接收到外中断请求后，会停止当前程序的执行，转而执行相应的中断处理程序，进行相应的数据处理和操作。

需要注意的是，由于外中断是由外部设备产生的，因此需要对外设产生的中断请求进行及时处理，避免数据丢失或者系统崩溃。同时，外中断的处理通常需要进行上下文切换和状态保存等操作，因此需要尽量减少外中断的产生，提高系统的运行效率和响应速度。

总之，外中断是一种由外部设备产生的中断。外中断通常是由中断控制器接收和转发外设的中断请求信号，并将中断请求转发到相应的处理器核心上进行处理。外中断通常用于实现计算机系统与外部设备的交互，例如网络通信、输入输出操作等。在进行外中断处理时，处理器会根据中断向量表中相应的入口地址，跳转到对应的中断处理程序中执行，处理完毕后再返回到原来的程序中继续执行。

中断机制的基本原理

不同的中断信号，需要用不同的中断处理程序来处理。当 CPU 检测到中断信号后，会根据 中断信号的类型去查询 中断向量表，以此来找到 相应的 中断处理程序在内存中的存放位置

image-20230522104824119

知识回顾与重要考点

image-20230522104914807

没有中断机制，就不可能实现操作系统，不可能实现 程序并发

系统调用

知识总览

image-20230522145342025

什么是系统调用

知识点回顾： 操作系统作为用户和计算机硬件之间的接口，需要向上层提供一些简单易用的服务。主要包括 命令接口和 程序接口。 其中 ，程序接口由一组 系统调用 组成。

image-20230522145551059

“系统调用” 是操作系统提供给 应用程序 （程序员或者编程人员） 使用的 接口，可以理解为 一种可供 应用程序 调用的 特殊函数， 应用程序可以通过 系统调用来 请求获得操作系统 内核的  服务

系统调用是操作系统提供给用户程序的一组接口，用户程序可以通过这些接口向操作系统请求服务和资源，并进行各种系统管理和控制操作。系统调用通常是在用户态下执行的，但是它们会触发内核态的代码执行，从而让操作系统内核可以访问系统资源和硬件设备，完成相应的操作任务。

系统调用一般由操作系统内核提供，包括文件操作、进程管理、内存管理、网络通信等一系列服务。用户程序可以通过系统调用的接口，向操作系统内核发起各种请求，例如读写文件、创建进程、分配内存、进行网络通信等。在进行系统调用时，用户程序需要将请求的参数传递给操作系统内核，并通过系统调用的返回值获取操作的结果。

在进行系统调用时，用户程序通常需要使用特殊的指令（例如int 0x80）来触发系统调用，将处理器的特权级别从用户态切换到内核态。在内核态下，操作系统内核可以直接访问系统资源和硬件设备，并执行各种系统管理和控制任务。系统调用处理完成后，处理器会将特权级别从内核态切换回用户态，用户程序可以继续执行其他任务。

需要注意的是，系统调用的执行会触发内核态的代码执行，因此需要谨慎处理，避免对系统的安全性和稳定性产生影响。同时，由于系统调用的执行通常需要进行上下文切换和状态保存等操作，因此需要尽量减少系统调用的使用，提高系统的运行效率和响应速度。

总之，系统调用是操作系统提供给用户程序的一组接口，用户程序可以通过这些接口向操作系统请求服务和资源，并进行各种系统管理和控制操作。通过系统调用，用户程序可以访问内核态的代码和资源，从而完成各种系统级别的任务。系统调用的执行需要谨慎处理，避免对系统的安全性和稳定性产生影响。同时，需要尽量减少系统调用的使用，提高系统的运行效率和响应速度。

系统调用和库函数的区别

image-20230522145822469

系统调用和库函数都是用于完成特定任务的编程接口，但它们之间存在着一些区别。

系统调用是操作系统提供的一组接口，用于让用户程序可以请求操作系统内核的服务和资源。通过系统调用，用户程序可以访问内核态的代码和资源，从而完成各种系统级别的任务。系统调用通常是在用户态下执行的，但是它们会触发内核态的代码执行，从而让操作系统内核可以访问系统资源和硬件设备，完成相应的操作任务。

库函数则是一组由程序员编写的函数库，包含许多常用的功能函数。库函数通常是在用户态下执行的，它们不直接访问系统资源和硬件设备，而是通过系统调用来实现相应的功能。库函数通常是由编译器链接到程序中，也可以通过动态链接库的方式进行调用。

因此，系统调用和库函数的区别在于：

  1. 级别不同：系统调用是操作系统内核提供的接口，用于访问内核态的资源和硬件设备，而库函数是由用户程序编写的函数库，通常在用户态下执行。

  2. 功能不同：系统调用提供的是一些系统级别的服务和资源，例如文件操作、进程管理、网络通信等，而库函数提供的是一些常用的功能函数，例如字符串操作、数学计算、图形界面等。

  3. 实现方式不同：系统调用是由操作系统内核提供的接口，需要通过特殊的指令（例如int 0x80）触发执行，并涉及到用户态和内核态的上下文切换和状态保存等操作。而库函数通常是由编译器链接到程序中，或者通过动态链接库的方式进行调用，不需要进行上下文切换和状态保存等操作。

总之，系统调用和库函数都是编程接口，但是它们的功能、实现方式和级别等方面存在明显的区别。在编写程序时，需要根据实际需求选择适合的编程接口，以便更好地完成相应的任务。

为什么系统调用是必须的

image-20230522150350980

系统调用是操作系统提供给用户程序的一组接口，用户程序可以通过这些接口向操作系统请求服务和资源，并进行各种系统管理和控制操作。系统调用是必须的，主要有以下几个原因：

  1. 访问受限资源：操作系统负责管理计算机系统中的各种资源，例如文件、内存、硬件设备等。这些资源通常是受限的，只有经过操作系统的授权才能进行访问。用户程序需要通过系统调用的方式，向操作系统请求相应的资源访问权限，以便完成相应的任务。

  2. 实现安全保护：操作系统负责保护计算机系统的安全性和稳定性，避免用户程序对系统产生负面影响。通过系统调用，操作系统可以对用户程序进行严格的检查和控制，确保用户程序的安全性和稳定性。

  3. 实现系统管理：操作系统负责管理计算机系统中的各种任务和进程，以及对系统资源的分配和回收等管理任务。用户程序需要通过系统调用的方式，向操作系统请求相应的管理操作，例如创建新的进程、释放系统资源等。

  4. 实现系统扩展：操作系统需要不断地进行功能扩展和升级，以满足不断变化的需求。通过系统调用，操作系统可以向外部开放接口，让用户程序可以利用新的功能和服务，从而实现系统的扩展和升级。

总之，系统调用是操作系统提供给用户程序的一组接口，用户程序可以通过这些接口向操作系统请求服务和资源，并进行各种系统管理和控制操作。系统调用是必须的，它可以让用户程序访问受限资源、实现安全保护、实现系统管理和实现系统扩展等功能，保证计算机系统的安全性、稳定性和可靠性。

什么功能要用到 系统调用

应用程序 通过 系统调用 请求 操作系统的服务。而系统中的 各种资源都由 操作系统内核同一掌管，因此 凡是与共享资源有关的操作（如 存储分配、IO 操作、文件管理等），都必须通过系统调用的方式向操作系统内核提出服务请求，由 操作系统内核代为完成。这样 可以保证系统的稳定性和安全性，防止用户进行非法操作。

image-20230522151039238

系统调用是操作系统提供给用户程序的一组接口，用户程序可以通过这些接口向操作系统请求服务和资源，并进行各种系统管理和控制操作。以下列举几个常见的功能需要用到系统调用：

  1. 文件操作：用户程序需要通过系统调用来访问操作系统提供的文件系统，进行文件的读写、创建、删除等操作。

  2. 进程管理：用户程序需要通过系统调用来创建、终止、暂停、恢复进程等操作，以便对进程进行管理和控制。

  3. 内存管理：用户程序需要通过系统调用来分配、释放内存，以便进行内存管理和优化。

  4. 网络通信：用户程序需要通过系统调用来进行网络通信，包括建立连接、发送和接收数据等操作。

  5. 系统信息获取：用户程序需要通过系统调用获取系统信息，例如系统时间、CPU使用率、内存使用率等信息。

  6. 安全保护：用户程序需要通过系统调用来实现安全保护，例如访问控制、进程隔离等操作，以保证系统的安全性和稳定性。

总之，系统调用是操作系统提供给用户程序的一组接口，用户程序可以通过这些接口向操作系统请求服务和资源，并进行各种系统管理和控制操作。文件操作、进程管理、内存管理、网络通信、系统信息获取和安全保护等功能都需要用到系统调用。通过系统调用，用户程序可以访问操作系统提供的各种资源和服务，从而实现更加复杂和丰富的功能

系统调用的过程

image-20230522151344666

传递系统调用参数 -> 执行 陷入指令（用户态A) -> 执行相应的 内请求核程序处理系统调用 （核心态） -> 返回应用程序

注意：

  1. **陷入指令 ** 是在 用户态 执行的，执行陷入指令之后立即引发一个 内中断，使 CPU 进入 核心态
  2. **发出系统调用请求 ** 是在 用户态，而 对系统调用的相应处理 在 核心态 下进行

系统调用是操作系统提供给应用程序的接口，允许应用程序请求操作系统内核提供的服务和资源。系统调用的过程可以概括为以下几个步骤：

  1. 应用程序通过调用标准C库提供的系统调用函数，如read、write、open等，向操作系统发起系统调用请求。

  2. 系统调用函数将系统调用号和参数传递给操作系统内核，操作系统内核通过系统调用号来确定应该执行哪个系统调用服务。

  3. 操作系统内核根据系统调用号和参数，执行对应的系统调用服务，并返回执行结果给调用进程。

  4. 如果系统调用执行失败，操作系统内核会返回错误码给应用程序，应用程序可以根据错误码来处理错误情况。

  5. 应用程序继续执行，并根据系统调用的返回值来判断系统调用是否成功完成。

在执行系统调用时，应用程序需要切换到内核模式，这是由于系统调用需要访问操作系统内核的资源和服务，而这些资源和服务只能在内核模式下访问。因此，操作系统会将应用程序的执行权限从用户态切换到内核态，以便执行系统调用。在系统调用完成后，操作系统会将执行权限重新切换回用户态，应用程序可以继续执行。

总的来说，系统调用提供了一种安全、可靠、标准化的方式，让应用程序能够访问操作系统提供的资源和服务，是操作系统和应用程序之间进行交互的重要手段。

知识回顾与重要考点

image-20230522151924136

操作系统的体系架构

知识总览

image-20230522152125818

操作系统的内核

image-20230522152150388

内核 是操作系统最基本、最核心的 部分

实现操作系统内核 功能的 那些程序 就是 内核程序

image-20230522152340580

注意：

  • 操作系统内核 需要运行在内核态
  • 操作系统的 非内核 功能运行在 用户态
image-20230522152506175

一个场景：现在，应用程序想要请求操作系统的服务，这个服务的出咯同时涉及到进程管理、存储管理、设备管理

注意： 变态的过程是需要成本，要消耗不少时间， 频繁的变态会降低系统性能

知识回顾与重要考点

image-20230522152842351

典型的 大内核、宏内核、单内核 操作系统 ： Linux、Unix

典型的微内核 操作系统： Windows NT

知识回顾

image-20230522153121907

进程管理

知识框架

image-20230522153458615

进程管理是操作系统中最基本的功能之一，它负责管理正在运行的程序或应用程序，主要包括进程的创建、调度、同步、通信和销毁等操作。

  1. 进程的创建：进程的创建通常是由操作系统内核发起的，当用户启动一个程序或应用程序时，操作系统会为该程序或应用程序创建一个进程，并为该进程分配必要的资源，如内存空间、文件描述符等。

  2. 进程的调度：进程调度是指操作系统如何为多个进程分配CPU时间片，以实现进程的并发执行。操作系统通常会采用各种调度算法来调度进程，如先来先服务（FCFS）、短作业优先（SJF）、时间片轮转等。

  3. 进程的同步：进程同步是指多个进程之间如何协调和同步它们的执行。操作系统提供了各种同步机制，如信号量、互斥锁、条件变量等，以保证进程之间的互斥、同步和协作。

  4. 进程的通信：进程通信是指不同进程之间如何进行数据的传输和共享。操作系统提供了多种进程通信机制，如管道、消息队列、共享内存等，以满足不同进程之间的数据交换和共享需求。

  5. 进程的销毁：进程的销毁是指进程执行完毕或出现错误时，操作系统如何释放该进程所占用的资源。操作系统通常会在进程执行完毕或出现错误时，向该进程发送一个信号，以触发进程的销毁和资源的释放。

总的来说，进程管理是操作系统中最基本的功能之一，它负责管理进程的创建、调度、同步、通信和销毁等操作，是操作系统实现进程并发和资源管理的重要手段。

进程与线程

进程的概念、组成、特征

知识总览

image-20230522153920671
进程的概念

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

进程（progress）：是 动态的，是程序的一次执行过程

同一个程序多次执行会对应多个进程

进程的组成

当进程被创建时，操作系统会为该进程 分配一个 唯一的、不重复的 身份证号 —— PID(Progress ID )

  • 操作系统要记录 PID、进程所属用户ID（UID
    • UID ：基本进程描述信息，可以让操作系统区分各个进程
  • 还要记录给 进程分配了哪些资源
    • 如 分配了多少内存、正在使用哪些 IO 设备、正在使用哪些文件
      • 可用于实现操作系统对资源的 管理
  • 还要记录进程的运行情况
    • 如 CPU 使用时间，磁盘使用情况，网络流量使用情况）
      • 可用于 实现操作系统 对进程的控制与调度

这些 信息都被保存在 一个数据结构 **PCB ** (Progress Control Block) 中，即 进程控制块

操作系统需要对 各个并发运行的进程进行管理， 但凡管理时 所需要的信息，都会被放在 PCB 中

进程的组成 ： PCB
image-20230522154900873
进程的组成：程序段、数据段
image-20230522155208911

**PCB ** 是给操作系统用的

程序段、数据段 是给 进程自己用的

程序是怎么运行的

image-20230522201128980 image-20230522201227604
进程的特征

程序是静态的，进程是动态的，相比于程序，进程拥有 以下特征

image-20230522201455067
知识回顾与重要考点
image-20230522201538987
进程的组织
image-20230522201954967
进程的组织：链接方式
image-20230522201726108
进程的组织：索引方式
image-20230522201915131

进程的状态与切换

知识总览

image-20230522202255514

进程的状态

image-20230522204216554

进程 PCB 中，会有一个变量 state 来表示 进程的 当前状态。如 1 表示 创建态、2 表示 就绪态、3 表示 运行态…

为了对同一个状态下的各个进程进行统一的管理，操作系统会将各个进程的 PCB 组织起来

进程是程序的一次执行。在这个执行过程中，有时 CPU 正在被 CPU 处理，有时又需要等待 CPU 服务，可见，进程的状态有各种变化。为了方便对各个进程的管理，操作系统需要将进程合理地划分为几种状态

image-20230522204747611 image-20230522204815780
创建态、就绪态
image-20230522202339744

在操作系统中，进程的状态通常可以分为五种，分别是创建态、就绪态、执行态、阻塞态和终止态。其中，进程的创建态和就绪态是进程执行过程中的前两个状态。

  1. 进程的创建态：当操作系统内核接收到一个进程的创建请求时，会为该进程分配必要的资源，如内存空间、文件描述符等，并初始化进程的状态和属性。此时，进程处于创建态，表示进程正在被创建，但还没有开始执行。在创建完成后，进程将会被转换成就绪态，等待被调度执行。

  2. 进程的就绪态：当进程被创建后，如果操作系统已经为该进程分配了必要的资源，并且该进程已经准备好执行，但是还没有被调度到CPU上执行时，该进程就处于就绪态。此时，进程已经准备好执行，只需要等待操作系统将其调度到CPU上执行即可。

总的来说，进程的创建态和就绪态是进程执行过程中非常重要的两个状态，它们标志着进程的创建和准备就绪，为进程的执行奠定了基础。进程的创建态是指进程正在被创建，还没有开始执行，而进程的就绪态是指进程已经准备好执行，只需要等待操作系统将其调度到CPU上执行。在操作系统中，进程的状态会不断地发生变化，进程的状态转换取决于进程当前的执行情况和操作系统对进程的管理和调度策略。

运行态

如果一个进程此时在 CPU 上运行，那么这个 进程处于 运行态

进程的运行态，也称为执行态，是指进程正在被CPU执行的状态。进程在运行态下，会占用CPU资源，执行程序代码，完成相应的计算任务和数据处理等操作。

进程从就绪态转换到运行态，是由操作系统根据其调度算法和优先级，从就绪队列中选择一个进程，并将CPU资源分配给该进程，使其开始执行。进程在运行态下，会一直占用CPU资源，直到完成相应的计算任务或被操作系统调度到阻塞态或终止态。

在运行态下，进程需要完成以下几个方面的任务：

  1. 执行程序代码：进程会根据程序代码中的指令，进行相应的计算和数据处理操作。

  2. 访问系统资源：进程可能需要访问操作系统提供的各种资源，如文件、网络、设备等。

  3. 处理中断和异常：进程需要处理各种可能发生的中断和异常情况，如IO中断、内存访问异常等。

  4. 进行同步和通信：进程在运行态下，也可能需要与其他进程进行同步和通信，以完成共享数据和协同计算等操作。

当进程完成了相应的计算任务或被操作系统调度到阻塞态或终止态时，它就会从运行态转换到其他状态。例如，如果进程需要等待某个事件的发生，如IO操作的完成，它就会被操作系统调度到阻塞态，等待事件的发生。如果进程执行完毕，或者出现错误或异常情况，它就会被操作系统调度到终止态，释放占用的资源。

总的来说，进程的运行态是指进程正在被CPU执行的状态，它是进程执行过程中最重要的状态之一。进程在运行态下，会占用CPU资源，执行程序代码，完成相应的计算任务和数据处理等操作。了解进程的运行态可以帮助我们更好地理解操作系统的进程管理和调度机制。

阻塞态

在进程运行的过程中，可能会 请求等待某个事件的发生 （如等待某种系统资源的分配，或者等待其他进程的响应）

在这个事件发生之前，进程无法继续 往下执行，此时操作系统让这个 进程 下 CPU，并让他进入 阻塞态。当 CPU 空间时，又会选择另一个 “就绪态” 的进程上 CPU

进程的阻塞态是指进程在等待某个事件发生时被操作系统暂停执行的状态。当进程需要等待某些事件的发生，如IO操作的完成、信号量的变化等，它就会被操作系统调度到阻塞态，等待事件的发生。此时，进程不再占用CPU资源，直到等待的事件发生后，操作系统将其重新调度到就绪态，等待执行。

进程在阻塞态下，会执行相应的阻塞操作，并等待操作系统通知其相关事件的发生。阻塞操作通常是由系统调用触发的，例如读操作时，如果没有数据可读，进程就会被阻塞，等待数据的到来。在阻塞态下，进程需要等待操作系统完成相应的操作，才能重新被调度到就绪态。

进程从就绪态转换到阻塞态，通常是由以下几种事件触发：

  1. IO操作：进程需要执行IO操作时，如果没有可用的数据或设备资源，就会被阻塞。

  2. 等待事件：进程需要等待某些事件的发生，如信号量的变化、定时器的到期等。

  3. 锁竞争：多个进程需要竞争同一个资源时，如果某个进程没有获得资源的锁，就会被阻塞。

  4. 信号处理：进程需要等待信号的到来或处理信号时，也可能会被阻塞。

当等待的事件发生后，操作系统会将进程从阻塞态重新调度到就绪态，等待执行。此时，进程会继续从上次中断的地方开始执行。

总的来说，进程的阻塞态是指进程在等待某个事件发生时被操作系统暂停执行的状态。当进程需要等待某些事件的发生时，它就会被调度到阻塞态，并执行相应的阻塞操作。了解进程的阻塞态可以帮助我们更好地理解操作系统的进程管理和调度机制。

终止态
image-20230522203232706

进程的终止态是指进程执行完毕或出现错误或异常情况时被操作系统终止执行的状态。当进程完成了相应的计算任务或出现了错误或异常情况时，它就会被操作系统调度到终止态，释放占用的资源。

进程在终止态下，不再占用CPU资源，但仍保留其相关的进程控制块（PCB），以便操作系统可以在必要时查询该进程的相关信息。当进程被终止时，操作系统会释放该进程所占用的资源，包括内存空间、文件描述符、设备资源等。此外，操作系统还会向进程的父进程发送一个信号，以通知其进程的终止情况。

进程从执行态转换到终止态，通常是由以下几种情况触发：

  1. 进程执行完毕：当进程完成了相应的计算任务后，它就会被终止。

  2. 进程出错：当进程出现错误或异常情况，如访问非法内存、除以零等，就会被终止。

  3. 进程被杀死：当操作系统接收到终止进程的命令，或者进程收到了相应的信号时，它就会被终止。

当进程被终止时，操作系统会执行相应的清理工作，包括释放占用的资源、回收进程控制块等。此外，操作系统还会向进程的父进程发送一个信号，以通知其进程的终止情况。

总的来说，进程的终止态是指进程执行完毕或出现错误或异常情况时被操作系统终止执行的状态。进程在终止态下，不再占用CPU资源，但仍保留其相关的进程控制块，以便操作系统可以在必要时查询该进程的相关信息。了解进程的终止态可以帮助我们更好地理解操作系统的进程管理和资源回收机制。

进程的切换

image-20230522203453139

进程在执行过程中，其状态会不断地发生变化，通常可以分为五种状态：创建态、就绪态、运行态、阻塞态和终止态。这些状态之间的切换是操作系统中非常重要的一个机制，可以实现多任务的并发执行和资源的高效利用。

进程的状态之间的切换通常包括以下几种情况：

  1. 创建态到就绪态：当操作系统接收到一个进程的创建请求时，会为该进程分配必要的资源，并初始化进程的状态和属性。此时，进程处于创建态。当进程完成初始化后，就会被转换成就绪态，等待被调度执行。
  2. 就绪态到运行态：当进程处于就绪态时，表示进程已经准备好执行，但还没有被调度到CPU上执行。当操作系统根据其调度算法和优先级，从就绪队列中选择一个进程，并将CPU资源分配给该进程时，该进程就会从就绪态转换到运行态，开始执行。
  3. 运行态到阻塞态：当进程在执行过程中需要等待某些事件的发生，如IO操作的完成、信号量的变化等，就会被操作系统调度到阻塞态，等待事件的发生。此时，进程不再占用CPU资源，处于阻塞态。当等待的事件发生后，操作系统会将进程重新调度到就绪态，等待执行。
  4. 运行态到终止态：当进程完成了相应的计算任务或出现了错误或异常情况时，它就会被操作系统调度到终止态，释放占用的资源。此时，进程不再占用CPU资源，但仍保留其相关的进程控制块，以便操作系统可以查询其相关信息。
  5. 阻塞态到就绪态：当等待的事件发生后，操作系统会将进程从阻塞态重新调度到就绪态，等待执行。
  6. 运行态到就绪态：当进程处于运行态时，表示进程正在执行任务，并且已经占用了CPU资源。当操作系统需要将CPU分配给其他进程执行时，当前进程就会从运行态切换到就绪态，等待重新被调度执行。

总的来说，进程的状态之间的切换是操作系统中非常重要的一个机制，它可以实现多任务的并发执行和资源的高效利用。进程的状态之间的切换通常包括创建态到就绪态、就绪态到运行态、运行态到阻塞态、运行态到终止态和阻塞态到就绪态等情况。了解进程状态之间的切换可以帮助我们更好地理解操作系统的进程管理和调度机制，从而更好地优化系统性能和资源利用率。

知识回顾与重要考点

image-20230522204517650

进程控制

知识总览

image-20230523134455230

进程控制的概念

什么是 进程控制

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

简化理解： 进程控制就是 实现进程状态转换

image-20230523134709970

进程控制是操作系统中非常重要的一个机制，用于管理和控制进程的运行。进程控制包括进程的创建、撤销、挂起、恢复、调度等操作，可以实现多任务的并发执行和资源的高效利用。

进程控制通常包括以下几个方面：

  1. 进程的创建：当用户提交一个新的进程创建请求时，操作系统会为该进程分配必要的资源，并初始化进程的状态和属性。此时，进程处于创建态。进程的创建可以通过系统调用或其他机制来实现。

  2. 进程的撤销：当进程完成了相应的计算任务或出现了错误或异常情况时，它就会被操作系统调度到终止态，释放占用的资源。此时，进程不再占用CPU资源，但仍保留其相关的进程控制块，以便操作系统可以查询其相关信息。

  3. 进程的挂起与恢复：当进程需要等待某些事件发生时，如IO操作的完成、信号量的变化等，就会被操作系统调度到阻塞态，等待事件的发生。此时，进程不再占用CPU资源，处于阻塞态。当等待的事件发生后，操作系统会将进程重新调度到就绪态，等待执行。进程的挂起与恢复可以通过操作系统提供的相应API来实现。

  4. 进程的调度：进程调度是指操作系统根据其调度算法和优先级，从就绪队列中选择一个进程，并将CPU资源分配给该进程的过程。进程调度可以实现多任务的并发执行和资源的高效利用，从而提高系统的性能和可靠性。

  5. 进程的同步与通信：当多个进程需要共享数据或资源时，就需要实现进程之间的同步和通信。进程同步和通信可以通过共享内存、消息队列、套接字等机制来实现，从而实现进程之间的数据共享和通信。

总的来说，进程控制是操作系统中非常重要的一个机制，它可以实现多任务的并发执行和资源的高效利用。进程控制涉及到进程的创建、撤销、挂起、恢复、调度等操作，以及进程之间的同步和通信。了解进程控制可以帮助我们更好地理解操作系统的进程管理机制，从而优化系统性能和资源利用率。

如何实现进程控制

用 原语 实现

image-20230523134938494

操作系统原语是操作系统提供的一组基本操作，用于实现进程同步和通信。操作系统原语通常是一些不可分割的操作，可以保证进程之间的同步和通信的正确性和安全性。

为什么进程控制的状态 要 “一气呵成”

如果不能一气呵成，就有可能导致操作系统中的某些关键数据结构信息不统一的情况，这会影响 操作系统 进行别的 工作

image-20230523135306826
如何实现 原语的 “原子性”

原语 的执行具有原子性，即执行过程只能一气呵成，期间 不允许被中断。

可以用 关中断 指令 和 开中断指令 这两个 **特权指令 ** 实现 原子性

image-20230523135553244 image-20230523135647748 image-20230523140810356

实现进程控制需要操作系统提供一系列API或者系统调用，用于管理和控制进程的创建、撤销、挂起、恢复、调度等操作。下面简单介绍几种实现进程控制的方式：

  1. 进程控制块（PCB）：操作系统通常会为每个进程分配一个进程控制块（PCB），用来记录进程的基本信息和状态，并维护进程的运行环境和资源。PCB 中包含了进程的标识符、状态、程序计数器、寄存器、内存映像、打开文件列表等信息。操作系统可以通过PCB来管理和控制进程的创建、撤销、挂起、恢复、调度等操作。

  2. 系统调用：系统调用是操作系统提供的一组API，用于实现进程控制和管理。例如，fork() 系统调用可以创建一个新的进程，exit() 系统调用可以终止一个进程，suspend() 系统调用可以挂起一个进程等。系统调用通常是通过软件中断或异常来实现的，可以在用户程序中调用，从而实现对进程的控制和管理。

  3. 调度算法：调度算法是操作系统用于管理和调度进程的一种机制，可以根据不同的调度策略来分配CPU资源，实现多任务的并发执行。调度算法通常包括先进先出（FIFO）、短作业优先（SJF）、时间片轮转等多种算法，可以根据具体的应用场景和需求来选择合适的算法。

  4. 进程同步和通信：当多个进程需要共享数据或资源时，就需要实现进程之间的同步和通信。进程同步和通信可以通过共享内存、消息队列、信号量等机制来实现，从而实现进程之间的数据共享和通信。

总的来说，实现进程控制需要操作系统提供一系列API或者系统调用，用于管理和控制进程的创建、撤销、挂起、恢复、调度等操作。同时，还需要实现调度算法和进程同步和通信机制，从而实现多任务的并发执行和资源的高效利用。

进程控制相关的原语

进程的创建
image-20230523135836451
进程的终止
image-20230523135916635
进程的阻塞与唤醒
image-20230523140032587
进程的切换
image-20230523140144442

程序是怎么运行的

image-20230523140318700

注意：另一个进程在运行过程中也会使用各个寄存器

在进程切换时，先在 PCB 中保存这个进程的 运行环境（保存一些必要的寄存器信息）

当原来的进程再次投入运行时，可以通过 PCB 恢复它的运行环境

image-20230523140636626

知识回顾与重要考点

image-20230523140716965

进程通信

知识总览

image-20230523165903644

什么是进程通信

进程通信就是 进程之间的信息交换

进程是分配系统资源的单位（包括内存地址空间），因此 各进程 拥有的 内存地址空间相互独立

image-20230523170116821

为了保证安全， 一个进程不能直接访问另一个进程的地址空间

但是进程之间的信息交换又是必须要实现的。为了保证进程间的安全通信，操作系统提供了一些办法

  • 共享存储
  • 消息传递
  • 管道通信

进程通信是指在多进程并发执行的系统中，不同进程之间进行信息交换的过程。进程通信是操作系统中非常重要的一个机制，可以实现不同进程之间的协作和合作，从而提高系统的性能和可靠性。

进程通信通常包括以下几种常见的方式：

  1. 管道通信：管道通信是一种半双工的通信方式，通过在进程间共享一个内核缓冲区来实现通信。管道通信只能在具有亲缘关系的进程之间使用，例如父子进程之间。
  2. 共享内存通信：共享内存通信是一种高效的通信方式，多个进程可以访问共享的内存区域，从而实现数据共享。共享内存通信需要使用信号量等同步机制来保证数据的一致性和安全性。
  3. 消息队列通信：消息队列通信是一种异步的通信方式，可以在不同进程之间发送和接收消息。消息队列通信需要使用一组API来创建、发送和接收消息，它支持有序和无序的消息传递。

总的来说，进程通信是多任务操作系统中非常重要的一个机制，可以实现不同进程之间的协作和合作，从而提高系统的性能和可靠性。根据具体的应用场景和需求，可以选择不同的进程通信方式来实现进程之间的数据交换和通信。

进程通信：共享存储

image-20230523170353006

两个进程对于 共享空间的访问 必须是 互斥 的（互斥访问通过操作系统提供的工具实现）。操作系统只负责共享空间和同步互斥工具

  • 基于数据结构 的共享：
    • 比如共享空间里面只能放一个长度为 10 的数组。这种 共享方式速度慢、限制多，是一种 低级通信 方式
  • 基于存储区 的共享：
    • 在内存中划出一块共享存储区，数据的形式、存储位置都由进程控制，而不是操作系统。相比之下，这种方式速度更快，是一种 高级通信 方式

进程通信：管道通信

image-20230523171523016
  • 管道只能采用 半双工通信，某一时间段内只能实现 单向的传输。如果要实现 双向同时通信，则 需要设置两个管道
  • 各进程要 互斥 的访问管道
  • 数据以字符流的形式写入管道，当 管道写满 时，写进程 的 write() 系统调用将被阻塞，等待 读进程将数据取走。当读进程将数据全部取走后， 管道变空，此时 读进程 的 read() 系统调用 将被 阻塞
  • 如果 没写满，就不允许读。 如果 没读空，就不允许写
  • 数据一旦被读出，就从管道中被抛弃，这就意味着 读进程最多只能有一个，否则可能会有读错数据的情况

管道通信是一种进程间通信方式，它是基于文件描述符的通信方式。管道通信是一种半双工的通信方式，它只能在具有亲缘关系的进程之间使用，例如父进程和子进程之间。

在管道通信中，操作系统会创建一个内核缓冲区，而进程之间可以通过这个内核缓冲区来进行单向的通信。管道通信的数据流动方向通常是单向的，因此在需要进行双向通信时，需要使用两个管道。

管道通信的创建需要使用pipe()系统调用，该调用会返回两个文件描述符，一个用于读取数据，一个用于写入数据。父进程和子进程之间可以通过这两个文件描述符来实现通信。例如，父进程可以使用fork()系统调用创建一个子进程，并使用pipe()系统调用创建一个管道。子进程可以继承父进程的文件描述符，从而可以直接使用管道进行通信。

管道通信的优点是简单易用，速度较快，适合于小规模的数据通信。但是，管道通信只能在具有亲缘关系的进程之间使用，且数据流方向单向，无法进行双向通信。同时，管道通信也存在一定的局限性，例如缓冲区大小有限，无法进行随机访问等。

总的来说，管道通信是一种基于文件描述符的进程间通信方式，它可以实现进程之间的单向通信，适合于小规模的数据通信。在具有亲缘关系的进程之间，管道通信是一种简单易用的通信方式，但是在其他情况下，需要使用其他进程通信方式来实现进程之间的数据交换和通信。

进程通信：消息传递

进程间的数据交换 以 格式化的信息（Message） 为单位。进程通过操作系统提供的 “发送消息/接收消息” 两个原语 进行数据交换

image-20230523173015228

消息传递是一种进程间通信方式，它可以在不同进程之间进行数据传递和通信。消息传递通常由发送和接收两个操作组成，发送进程可以将消息发送给接收进程，接收进程可以从消息队列中接收消息，从而实现进程间的通信。

消息传递通信的实现需要使用一组API或者系统调用，例如System V IPC和POSIX IPC等。在Linux系统中，可以使用msgget()、msgsnd()和msgrcv()等系统调用来实现消息传递通信。

消息传递通信的优点是灵活多样，可以在不同进程之间进行通信和数据传递。消息传递通信还支持有序和无序的消息传递，可以根据具体的应用场景和需求来选择合适的方式。

但是，消息传递通信也存在一定的局限性，例如在消息传递过程中，需要使用一定的同步机制来保证消息的一致性和安全性。同时，由于消息传递通信是通过系统调用来实现的，因此会增加一定的系统开销和额外的复杂度。

消息传递通信有多种形式，常见的有：

  1. 队列消息传递：队列消息传递是一种有序的消息传递方式，发送进程将消息放入队列中，接收进程从队列中取出消息。队列通常是先进先出（FIFO）的结构，在保证消息的有序性的同时，也可以实现多个进程之间的并发传输。

  2. 套接字消息传递：套接字消息传递是一种基于网络协议的消息传递方式，可以在不同主机上的进程之间进行通信。套接字消息传递支持TCP或UDP等协议，可以保证数据的可靠性和安全性。

  3. 信号消息传递：信号消息传递是一种异步的消息传递方式，可以向其他进程发送信号以通知其发生了某些事件。信号消息传递可以用于进程间的同步和异步通信，例如进程间的中断处理等。

总的来说，消息传递通信是一种灵活多样的进程间通信方式，可以在不同进程之间进行通信和数据传递。消息传递通信适用于多进程并发执行的系统中，并可以根据具体的应用场景和需求来选择合适的方式。

知识回顾与重要考点

image-20230523173115393

线程、多线程模型

知识总览

image-20230523181330267

什么是线程

还没引入线程之前，系统中各个程序只能串行执行。

进程是程序的一次执行。但是这些功能显然不可能是由一个程序顺序处理就能实现的，有的进程可能需要同时做很多事，而传统的进程只能串行的执行一系列的程序。为此引入了 线程，来增加并发度引入线程之后， 线程就成为了程序执行流的最小单位

可以把 线程 理解为 轻量级进程。

线程 是 一个 基本的CPU 执行单元，也是 程序执行流的最小单位。引入线程之后，不仅是进程之间可以并发，进程内的 各线程之间 也可以并发，从而进一步 提升了系统的并发度，使得一个进程内也可以并发执行各种任务

引入 线程 之后，进程 只作为 除 CPU 之外的系统资源的分配单元。 线程 则作为 处理机的分配单元

image-20230523182058103

线程是操作系统中的一种基本执行单元，它是进程中的一个独立执行流程。与进程不同的是，线程是在同一进程内执行的，它们共享进程的地址空间和资源，因此线程之间的切换和通信代价较小，可以提高程序的效率和性能。

引入线程后的变化

  • 资源分配、调度
    • 传统进程机制中，进程是资源分配、调度的基本单位
    • 引入线程之后，进程是资源分配的基本单位，线程是调度的基本单位
  • 并发性
    • 传统进程机制中，只能进程并发
    • 引入线程之后，各线程间也能并发，提升了并发性
  • 系统开销
    • 传统的进程并发，需要切换进程的运行环境，系统开销很大
    • 线程间并发，如果是同一进程之间切换，则不需要切换进程环境，系统开销小
    • 引入线程之后，并发所带来的系统开销小

线程的属性

  • 线程是处理机调度的基本单位

  • 多 CPU 计算机中，各个线程可占用不同的 CPU

  • 每个线程都有一个 线程 ID、线程控制块（TCB）

  • 线程也有就绪、阻塞、运行三种基本状态

  • 线程几乎不拥有系统资源

    • 线程是操作系统中的基本执行单元，它是进程中的一个独立执行流程。线程与进程的最大区别在于它们共享进程的地址空间和资源。

      因为线程共享进程的资源，所以线程几乎不拥有系统资源。线程在创建时不需要分配独立的地址空间，也不需要拥有独立的文件描述符、内存空间等系统资源。相反，它们共享进程内的这些资源，因此线程的创建和销毁代价较小，可以提高程序的效率和性能。

      对于线程而言，它们所需要的系统资源通常只包括线程栈、寄存器和一些与线程相关的元数据等。这些资源都是由操作系统内核来管理和分配的，线程在创建时可以直接从操作系统内核中获取这些资源，而不需要进行额外的分配和释放。

      因此，线程几乎不拥有系统资源，它们只是对进程内共享资源的一种利用和管理。这也是线程相比进程更加轻量级的原因之一。由于线程的创建和销毁代价较小，因此可以更高效地利用系统资源，提高程序的效率和性能。

  • 同一进程的不同线程之间共享进程的资源

  • 由于共享内存地址，同一进程中的线程间通信甚至不需要系统干预

  • 同一进程中的线程切换，不会引起进程切换

  • 不同的进程中的线程切换，会引起线程切换

  • 切换同一进程内的线程，系统开销很小

  • 切换进程，系统开销很大

线程的实现方式

知识总览

image-20230523185405732
用户级线程

用户级线程（User-Level Thread，ULT）：早期的操作系统 只支持进程，不支持线程。当时的 ”线程“ 是通过 线程库 实现的

早期的用户级线程是由用户程序自己实现的线程，不需要操作系统的支持，在用户态下进行线程的创建、切换和销毁等操作。早期的用户级线程是在操作系统内核不支持线程的情况下出现的，它们是一种用于提高程序并发性和效率的解决方案

很多编程语言提供了强大的 线程库，可以实现 线程的创建、销毁、调度 等 强大的功能

四个问题

  • 线程的管理由谁来完成？
    • 用户级线程由 应用程序通过 线程库实现，所有的 线程管理工作都由 应用程序负责（包括 线程切换）
  • 线程切换是否需要 CPU 变态
    • 用户级线程中，线程切换 可以在 用户态下即可完成，无需操作系统干预
  • 操作系统能否意识到 用户级线程的存在
    • 在用户看来，是有多个 线程。但是 在操作系统内核看来，并意识不到线程的存在。 用户级线程 就是 从用户视角看能看到的线程
  • 这种线程实现有什么缺点和优点
    • 优点： 用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管路的系统开销小，效率高
    • 缺点： 当一个用户级线程被阻塞后，整个 进程都会被阻塞，并发度不高。多个线程之间不可再多核处理器上 并行运行
内核级线程

内核级线程（Kernel-Level Thread，KLT）:又称 内核支持的线程，由 操作系统支持的线程

大多数的现代操作系统都实现了 内核级线程

内核级线程是由操作系统内核支持的线程，需要通过系统调用来实现线程的创建、切换和销毁等操作。与用户级线程不同的是，内核级线程是由操作系统内核来管理和调度的，可以获得更多的系统资源和服务，从而提高程序的效率和性能

四个问题

  • 线程的管理工作由谁来完成？
    • **内核级线程的管理工作 ** 由 操作系统 完成
  • 线程切换是否需要CPU变态？
    • 线程调度、切换等工作都由 内核负责，因此 内核级线程的切换 必然需要在 核心态 下才能完成
  • 操作系统是否能意识到内核级线程的存在？
    • 操作系统会为每个 内核级线程建立相应的 TCB，通过 TCB 对线程进行管理。 内核级线程 就是通过 从操作系统内核视看能看到的线程
  • 这种线程的实现方式有什么优点和缺点？
    • 优点：当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并发执行
    • 缺点：一个用户进程会占用 多个 内核级线程，线程切换由操作系统内核来完成，需要切换到核心态，因此 线程的管理的成本高，开销大

多线程模型

在支持内核级线程 的系统中，根据用户级线程与 内核级线程的映射关系，可以划分出好几种 多线程模型

一对一模型
image-20230523191325084

一个用户线程 映射到一个内核级线程。每个 用户级线程有与用户级线程同数量的内核级线程

优点： 当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行

缺点： 一个用户级线程会占用多个 多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此 线程管理的成本高，开销大

多对一模型
image-20230523191648441

多个用户级线程 映射到一个内核级线程。且一个进程只被分配一个内核级线程

优点： 用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高

缺点： 当一个 用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在 多核处理机上并行运行

多个用户级线程共享同一个内核级线程，因此阻塞一个用户级线程会导致整个线程被阻塞

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

多对多模型
image-20230523192150374

n 用户级线程 映射到 m 个 内核级线程（n >= m)。每个 用户进程 对应 m 个内核级线程

克服了 多对一模型 并发度不高的缺点（一个阻塞，全部阻塞），又克服了 一对一模型中一个用户进程占用太多内核级线程，开销太大的缺点

可以这么理解：

  • 用户级线程是 “代码逻辑” 的载体
  • 内核级线程是 “运行机会” 的载体

内核级线程才是 处理机分配的单位。例如 ： 多核 CPU 下，上图的 这个进程最多能被分配两个核

在多对多模型中，一个2核的CPU最多能给一个进程分配2个核，因为每个核都可以独立地运行一个线程。在多对多模型中，操作系统将多个用户级线程映射到多个内核级线程上，可以利用多核处理器的并行处理能力，提高程序的效率和性能。如果一个进程需要更多的核心来执行任务，可以将该进程分解成多个线程，分别运行在不同的核上，从而实现并行处理。但是，在使用多对多模型时，需要注意同步和竞争问题，从而保证数据的一致性和安全性。

一段 “代码逻辑” 只有获得了 “运行机会” 才能够被 CPU 执行

内核级线程 中可以运行 任意一个 有映射关系的用户级线程代码，只有两个内核级线程中 正在运行的代码逻辑都被阻塞时，这个 进程才会被 阻塞

知识回顾与重要考点

image-20230523193254131

处理机调度

处理机调度是指操作系统将处理机分配给各个进程的过程。在一个多道程序系统中，可能有多个进程同时运行，这些进程需要共享有限的处理机资源，因此需要对处理机进行调度，以实现公平、高效的资源利用。

处理机调度的目标是提高系统的吞吐量和响应时间，以及提高处理机的利用率和效率。为了实现这些目标，处理机调度需要考虑以下因素：

  1. 进程的优先级：进程的优先级是指进程在系统中的重要程度和紧急程度。处理机调度需要考虑进程的优先级，优先调度优先级高的进程，以保证系统的响应时间和服务质量。

  2. 进程的资源需求：进程的资源需求是指进程对处理机资源的需求量，包括CPU时间、内存空间、I/O等。处理机调度需要考虑进程的资源需求，避免进程因为资源不足而被阻塞或者占用过多的资源而影响其他进程的运行。

  3. 进程的状态：进程的状态是指进程在运行、就绪、阻塞等不同状态之间的转换。处理机调度需要考虑进程的状态，优先调度就绪状态的进程，避免进程的等待和阻塞。

  4. 处理机的负载：处理机的负载是指处理机当前的工作量和负荷情况。处理机调度需要考虑处理机的负载，避免给过度负载的处理机分配更多的进程，从而影响系统的性能和响应时间。

常见的处理机调度算法有以下几种：

  1. 先来先服务（FCFS）调度算法：按照进程提交的顺序进行调度，即先提交的进程先执行。该算法简单易实现，但是可能会出现进程等待时间过长的情况。

  2. 短作业优先（SJF）调度算法：按照进程的执行时间进行调度，即执行时间短的进程先执行。该算法可以最大限度地减少平均等待时间，但是可能会出现长作业等待时间过长的情况。

  3. 优先级调度算法：按照进程的优先级进行调度，即优先级高的进程先执行。该算法可以保证高优先级进程的及时响应，但是可能会出现低优先级进程长时间等待的情况。

  4. 时间片轮转调度算法：按照时间片的大小进行调度，即每个进程在执行一段时间后被强制停止，转而执行下一个进程。该算法可以平衡各个进程之间的资源竞争，但是可能会出现进程响应时间不稳定的情况。

  5. 多级反馈队列调度算法：将进程按照优先级分成多个队列，每个队列按照时间片轮转的方式进行调度，进程的优先级随着等待时间的增加而提高。该算法可以平衡各个进程之间的资源竞争，同时提高高优先级进程的响应速度，适用于多种不同类型的工作负载。

调度的概念、层次

知识总览

image-20230523194015634

当有一堆任务要处理，但由于资源有限，这些任务没有办法同时处理。这就需要 确定某种规则 来 决定 处理这些 任务 的 顺序，这就是 调度 研究的问题

调度的三个层次

在操作系统中，调度通常分为三个层次：长期调度（高级调度）、中期调度（中级调度）和短期调度（低级调度）。

  1. 长期调度：也称作作业调度。长期调度的主要工作是从作业池中选择适当的作业，将其调入内存，并为其创建进程。长期调度的目的是控制系统中的作业数量，避免过多的作业导致系统负载过重。长期调度的时间间隔比较长，通常以分钟或小时为单位。

  2. 中期调度：也称作内存调度。中期调度的主要工作是根据系统的内存使用情况，将一些暂时不活跃的进程从内存中调出到外存中，以释放内存资源，同时保留进程的状态，以备后续调入内存中运行。中期调度的目的是优化内存的使用，避免过多的进程占用内存，从而导致系统性能下降。中期调度的时间间隔比较短，通常以秒或分钟为单位。

  3. 短期调度：也称作进程调度。短期调度的主要工作是根据进程的优先级、状态、资源需求等因素，从就绪队列中选择一个进程，将其调入处理机中执行。短期调度的目的是保证系统的响应时间和吞吐量，同时保证处理机的利用率和效率。短期调度的时间间隔比较短，通常以毫秒或微秒为单位。

这三个调度层次相互协作，共同实现对系统资源的合理分配和调度。长期调度控制系统的作业数量，中期调度优化内存的使用，短期调度保证系统的响应时间和吞吐量。三个调度层次的目的都是提高系统的性能和效率，以满足用户的需求。

高级调度
image-20230523195003676

高级调度（作业调度）。按一定的原则从 外存的作业后备队列中挑选一个作业调入内存，并创建进程。 每个作业只调入一次，调出一次。作业调入时会建立 PCB，调出时才撤销 PCB

简化理解 ： 好几个程序要启动，到底先启动哪个

低级调度
image-20230523194940398

低级调度（进程调度、处理调度） —— 按照某种策略从 就绪队列中 选取一个进程，将 处理机分配给他

进程调度是操作系统中 最基本的一种调度，在一般的操作系统中都 必须配置进程调度。 进程调度的 频率很高，一般 几十毫秒一次

中级调度
image-20230523195036808

内存不够时，可将某些进程的数据 调出外存。等内存空闲 或者 进程需要运行的时候再重新调入内存

暂时调到 外存等待 的 进程状态是 挂起状态。被挂起的进程 PCB 会组织成 挂起队列

中级调度（内存调度） —— 按照某种策略决定某个 处于 挂起状态的 进程重新 调入内存。一个进程可能会被多次调出、调入内存，因此 中级调度 发生的频率 要比 高级调度 更高

补充：进程的挂起状态与七状态模型

暂时调到 外存等待的进程状态是 挂起状态（挂起态，suspend）

挂起态又可以进一步细分为 就绪挂起、阻塞挂起 两种状态

五状态模型 -> 七状态模型

image-20230523195621378
三层调度的对比与联系
image-20230523195712085
知识回顾与重要考点
image-20230524133756662

进程调度的时机、切换与过程、调度方式

知识总览

image-20230524134004841

​

进程调度的时机

进程调度（低级调度），就是按照某种算法从就绪队列中选择一个进程为其分配处理机

image-20230524134138472

进程在 操作系统内核程序临界区 中

进程访问操作系统内核程序的时候，需要进入临界区。临界区是指一段代码，在同一时刻只能被一个进程访问执行的区域。这是为了防止多个进程同时访问内核程序时发生竞态条件（race condition）等问题，导致数据不一致或者程序出现异常。在进入临界区之前，进程需要获得相应的锁，以保证只有一个进程可以进入临界区。当进程完成对内核程序的访问后，它需要释放锁，以便其他进程可以进入临界区。这种机制可以保证内核程序的正确性和稳定性，同时提高了系统的并发性能。

进程在 操作系统内核程序临界区中  不能  进行调度与切换

进程处于 临界区 时可以进行处理机调度？

在进程进入临界区时，它获得的是内核程序的锁，这个锁通常是不会释放的，直到进程完成对内核程序的访问后才会释放。在进程持有锁的情况下，操作系统是不会对该进程进行处理机调度的，因为如果进行调度可能会导致进程在临界区内被中断，从而破坏临界区的互斥性。因此，一般情况下，进程在临界区时是不会被调度的，直到它完成对内核程序的访问并释放锁后，才会重新加入到处理机调度队列中

进程在普通临界区 可以 进 行调度、切换

在普通临界区内，进程是可以被调度和切换的。普通临界区是指没有使用专门的同步机制（如锁）来保证临界区的互斥性。因此，多个进程可以同时进入普通临界区，这会导致这些进程可能会相互干扰，破坏数据的一致性。为了避免这种情况，操作系统会对这些进程进行调度和切换，以保证系统的稳定性和性能。当一个进程在普通临界区内时，它可能会被其他进程所抢占，从而被挂起，等待重新被调度。因此，在编写程序时，需要注意对临界区的保护，以避免不必要的干扰和竞争，提高程序的正确性和可靠性。

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

非剥夺调度方式，又称 非抢占方式 。即，只允许 进程主动放弃处理机。在运行过程中即便有更紧迫的 任务到达，当前进程依然会继续使用处理机，直到该进程终止或主动要求进入阻塞态

实现简单，系统开销小但是无法及时处理紧急任务，适合于早期的 批处理系统

非剥夺调度方式是指当一个进程已经被分配了处理器资源后，它将一直占用该资源直到完成或者主动释放。在这种方式下，操作系统不会强制剥夺进程的处理器资源，除非该进程自己主动让出处理器或者发生了某些特殊的情况（如中断、异常等）。因此，非剥夺调度方式可以保证进程的执行不会被中断或者影响，提高了系统的稳定性和可靠性。但是，在长时间运行的进程占用处理器资源的情况下，其他进程无法获得处理器资源，可能会导致系统的响应性降低，因此需要合理设置进程的优先级和调度算法，以平衡系统的性能和稳定性。

剥夺调度方式，又称 抢占方式，当一个进程在处理机上执行时，如果有一个更紧迫的、更重要的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要、更紧迫的那个进程

可以优先处理更紧急的进程，也可以实现让各进程按时间片 轮流执行的功能（通过时钟中断）。适合分时操作系统、实时操作系统

剥夺调度方式是指操作系统可以强制剥夺一个进程的处理器资源，让其他进程获得执行的机会。在这种方式下，操作系统会根据一定的调度算法，动态地调整进程的优先级，以保证系统的响应性和性能。剥夺调度方式可以有效地避免长时间运行的进程占用处理器资源，导致其他进程无法获得执行的情况，提高了系统的并发性和可靠性。但是，频繁的进程切换可能会导致系统的开销增大，因此需要根据系统的实际情况选择合适的调度算法和策略，以达到最佳的性能和稳定性平衡。同时，剥夺调度方式也要考虑进程的数据一致性和安全性问题，避免进程在执行过程中出现异常或者错误。

进程 的切换与过程

“狭义的进程调度”与“进程切换”的区别：

狭义的进程调度指的是从就绪队列中选中一个要运行的进程。（这个进程可以是刚刚被暂停执行的进程也可能是另一个进程，后一种情况就需要进程切换）进程切换是指一个进程让出处理机，由另一个进程占用处理机的过程。

广义的进程调度包含了选择一个进程和进程切换两个步骤。

进程切换的过程主要完成了：

  • 对原来运行进程各种数据的保存
  • 对新的进程各种数据的恢复(如：程序计数器、程序状态字、各种数据寄存器等处理机现场信息，这些信息一般保存在进程控制块

注意：进程切换是有代价的，因此如果过于频繁的进行进程调度、切换，必然会使整个系统的效率降低，使系统大部分时间都花在了进程切换上，而真正用于执行进程的时间减少。

知识回顾与重要考点
image-20230524140457427

调度算法的评价指标

知识总览

image-20230524142144246
CPU 利用率
image-20230524142221758
系统吞吐量
image-20230524170425260
周转时间

周转时间 ，是指 作业被提交给系统开始，到 作业完成为止 的这段时间间隔

它包括四个部分

  • 作业在外存后备队列上等待作业调度（高级调度）的时间
  • 进程在 就绪队列上等待 进程调度（低级调度） 的时间
  • 进程在 CPU 上执行的时间
  • 进程等待 I/O 操作完成的时间

后三项在整个作业处理过程中，可能发生多次

image-20230524170915989 image-20230524170949614

对于周转时间相同的两个作业，实际运行的时间长的作业在相同的时间内被服务的时间更多，带权周转时间更小，用户满意度更高

对于实际运行时间相同的两个作业，周转时间短的带权周转时间更小，用户满意度更高

等待时间

等待时间，指进程/作业 处于等待处理机状态时间之和，等待时间越长，用户满意度越低

image-20230524171506604

对于 进程 来说，等待时间就是指 进程建立好后 等待被服务的时间之和，在等待 I/O 完成的期间其实 进程也是被服务的，所以不计入等待时间

对于 作业 来说，不仅要考虑 建立进程后的等待时间， 还要加上作业在外存后备队列等待的时间

一个作业总共需要被 CPU 服务多久，被 I/O 设备 服务多久一般是不变的，因此调度算法其实只会影响 作业/ 进程的 等待时间。当然，也有 平均等待时间 来评价整体性能

响应时间

响应时间，指 从用户 提交请求 到 首次产生响应 所用的时间

知识回顾与重要考点
image-20230524172007583

调度算法（上）

知识总览

image-20230524172111816

Tips：各种调度算法的学习思路

  • 算法思想
  • 算法规则
  • 这种调度算法 是用于 作业调度 还是 进程调度
  • 抢占式？非抢占式
  • 优点和缺点
  • 是否会导致饥饿
    • 某线程/ 作业 长期得不到服务
先来先服务（FCFS）

First Come First Serve

  • 算法思想
    • 主要是 公平 角度
  • 算法规则
    • 按照 作业/ 进程到达的先后顺序 进行服务
  • 用于 作业/进程 调度
    • 用于 作业调度，考虑的是 哪个作业先到达后备队列；
    • 用于 进程调度时，考虑的是 哪个 进程先到达 就绪队列
  • 是否可抢占
    • 非抢占的算法
  • 优缺点
    • 优点：公平、算法实现简单
    • 缺点： 排在 长作业（进程）后面的 短队列需要等待很长时间，带权周转时间很大，对于短作业用户 不友好
  • 是否 会导致饥饿
    • 不会

image-20230524173611300

短作业优先（ SJF，Shortest Job First)
  • 算法思想
    • 最求最小的 平均等待时间，最少的 平均周转时间、最少的平均带权周转时间
  • 算法规则
    • 最短的 作业/进程 优先得到服务（所谓 最短，是指 要求服务时间 最短）
  • 用于 作业/进程调度
    • 两者都可，用于进程时，为 短进程优先（SPF，Shortest Progress First）
  • 是否可抢占
    • 都是 非抢占 的算法，但是也有抢占式的 版本 - 最短剩余时间优先算法（SRTN，Shortest Remaining Time Next）
  • 优缺点
    • 优点：’最短的’ 平均等待时间、平均周转时间
    • 缺点：不公平，对 短作业 有利，对 长作业 不利。可能产生 饥饿 现象。另外，作业/进程 的 运行时间是由用户提供的，并不一定真实，不一定能做到真正的 短作业优先
  • 是否会饥饿
    • 会，如果 源源不断的有 短作业 到来，可能使长作业 长时间得不到服务，产生饥饿现象。如果一直得不到服务，则 称为 饿死
image-20230525120449533 image-20230525120526737 image-20230525120559656

注意几个细节

  1. 如果 题目中 未特别说明， 所提到的 “短进程/作业优先算法” ，默认 是 非抢占式的

  2. 在 所有 进程同时可运行时，采用 SJF 调度算法的平均等待时间、平均周转时间最少

    或者 说： 在 所有进程都几乎同时到达时， 采用 SJF 调度算法的 平均等待时间、平均周转时间最少

    如果不加上述条件，则 应该说 抢占式 的 短作业/进程 调度算法 的最少

  3. 虽然严格来说，SJF 的 平均等待时间 、平均周转 时间并不一定最少，但相比于其他的算法（FCFS）。SJF 依然可以获得 较少的 平均等待时间和 平均周转时间

  4. 如果选择题中 遇到 “SJF 的 平均等待时间、平均周转时间最少 ” 的 选择，最好判断其他的选项是不是有明显的 错误

高响应比优先（HRRN，Highest Response Ratio Next）
  • 算法思想
    • 要综合考虑作业/进程 的等待时间 和 要求服务的时间
  • 算法规则
    • 在每次调度时 先计算各个作业的 响应比，选择 响应比最高 的作业 为其服务
  • 用于 作业/进程 调度
    • 两者都可
  • 是否可抢占
    • 非抢占式 的算法，印制只有当前的 作业主动放弃处理机时，才需要调度，才需要计算响应比
  • 优缺点
    • 综合考虑了 等待时间和运行时间（要求服务时间）
    • 等待时间相同时，要求服务时间短的优先（SJF 的优点）
    • 要求服务时间相同时，等待时间长的优先（FCFS 的优点）
    • 对于长作业来说，随着等待时间的 越来越久，其响应比越来越大，从而避免了 长作业饥饿的问题
  • 是否会导致饥饿
    • 不会
image-20230525121806869
知识回顾与重要考点
image-20230525122112277

调度算法（下）

知识总览

image-20230525122452456
时间片轮转（RR，Round-Robin)
  • 算法思想
    • 公平的、轮流的 为各个进程服务，让每个进程在一定 时间间隔内可以得到响应
  • 算法规则
    • 按照 各进程到达 就绪队列的 顺序，轮流的让 各个 进程执行一个 时间片，若进程未在一个时间片内 执行完，则剥夺处理机，江金城放到就绪队列队尾重新排队
  • 用于 作业/进程 调度
    • 用于进程调度（只有作业放入内存后，建立了 相应 的进程后，才能被分配处理机时间片）
  • 是否可抢占
    • 若进程未在时间片内运行完，将被强行剥夺处理机的使用权，因此 时间片轮转算法 属于 抢占式的 算法。由时钟装置发出 时钟中断 来通知 CPU 时间片已到
  • 优缺点
    • 优点 ： 公平，响应快，适用于 分时操作系统
    • 缺点： 由于 高频率的进程切换，因此有一定开销；不区分任务的紧急程度
  • 是否会导致 饥饿
    • 不会
image-20230525123024591 image-20230525123112216
优先级调度算法
  • 算法思想
    • 随着计算机的发展，特别是实时操作系统的出现，越来越多的应用场景需要根据任务的紧急程度来决定处理顺序
  • 算法规则
    • 每个作业/进程有各自的优先级，调度时选择优先级最高的作业/进程
  • 用于 作业/进程 调度
    • 既可用于作业调度，也可用于进程调度。甚至，还会用于在之后会学习的I/O调度中
  • 是否可抢占
    • 抢占式、非抢占式都有。做题时的区别在于：非抢占式只需在进程主动放弃处理机时进行调度即可，而抢占式还需在就绪队列变化时，检查是否会发生抢占。
  • 优缺点
    • 优点：用 优先级区分紧急程度、重要程度，适用于 实时操作系统。可灵活的调整对各种作业/进程 的 偏好程度
    • 缺点：若源源不断地有高优先级的进程到来，则可能会导致饥饿
  • 是否会导致 饥饿
    • 会
image-20230525123354383 image-20230525123418662
多级反馈队列调度算法
  • 算法思想
    • 对其它调度算法的折中权衡
  • 算法规则
    1. 设置 多级就绪队列，各级队列优先级从高到低，时间片从小到大
    2. 新进程到达时 先进入 第1 级队列，按照 FCFS 的原则 排队等待被分配时间片，若用完时间片进程还没结束，则进程进入下一级队列队尾。如果此时已经是最下级的队列，则重新放回该队列队尾
    3. 只有第 K 级队列为空时，才会为 K + 1 级队头的进程分配时间片
  • 用于 作业/进程 调度
    • 用于 进程调度
  • 是否可抢占
    • 抢占式的算法，在 K级队列的进程运行时，若更上级的队列（1~k-1) 中进入了一个新的进程，则由于新进程处于优先级更高的队列中，因此 新进程会抢占处理机，原来运行的进程放回 k 级队列
  • 优缺点
    • 优点：
      • 对各类进程相对公平（FCFS 的优点）
      • 每个新到达的进程都可以很快得到响应（RR 的优点）
      • 短进程只用较少的时间就可以完成工作（SPF 的优点）
      • 不必实现 估计进程的运行时间（避免用户作假）
      • 可灵活的调整对各类进程的偏好程度，比如 CPU 密集型进程、IO 密集型进程（可以将 因IO 阻塞的进程重新放回原队列，这样IO 型进程就可以保持高优先级）
  • 是否会导致 饥饿
    • 会
    • 在多级反馈队列调度算法中，如果一个进程被分配到了低优先级的队列中，而且该队列中有大量的优先级较高的进程，那么该进程就可能会长时间地等待，等待时间片用完后才能继续被调度。这种情况下，该进程就会发生饥饿现象，无法得到足够的资源去执行自己的任务，导致系统的性能和可靠性下降。
image-20230525133210363
知识回顾与重要考点
image-20230525133730207

进程同步、互斥

知识总览

image-20230527111843294

进程同步与互斥是操作系统中的两个重要概念，用于协调多个进程或线程之间的访问和操作，以避免出现竞争条件和数据不一致的问题。下面是对进程同步与互斥的简要介绍：

进程同步：当多个进程或线程共享同一个资源时，为了避免出现争用和竞争条件，需要对它们的访问和操作进行协调和同步。进程同步的主要目的是确保多个进程或线程之间的操作按照一定的顺序和规则进行，从而保证系统的正确性和稳定性。

进程互斥：进程互斥是指多个进程或线程对同一个资源的访问和操作是互斥的，即同一时刻只能有一个进程或线程访问和操作该资源。进程互斥的主要目的是防止多个进程或线程同时对同一个资源进行修改或访问，从而导致数据不一致和系统崩溃等问题。

在实际应用中，进程同步和互斥可以通过多种方式来实现，例如：

  1. 信号量：信号量是一种计数器，用于控制多个进程或线程对同一个资源的访问和操作。当一个进程或线程想要访问该资源时，需要先获取信号量，如果信号量的计数器为 0，则该进程或线程需要等待，直到其他进程或线程释放了该资源。当一个进程或线程完成对该资源的访问和操作后，需要释放信号量，使其计数器加 1。

  2. 互斥锁：互斥锁是一种特殊的信号量，用于实现进程互斥。当一个进程或线程想要访问该资源时，需要先获取互斥锁，如果互斥锁已被其他进程或线程占用，则该进程或线程需要等待，直到其他进程或线程释放了该锁。当一个进程或线程完成对该资源的访问和操作后，需要释放互斥锁，使其可以被其他进程或线程获取。

  3. 条件变量：条件变量是一种用于进程同步的机制，它允许一个进程或线程等待另一个进程或线程满足特定的条件。当一个进程或线程需要等待某个条件满足时，它可以调用条件变量的等待函数，同时释放对该资源的占用权，直到其他进程或线程满足该条件并通知它后再继续执行。

需要注意的是，进程同步和互斥的实现方式各有优缺点，应根据实际应用场景来选择合适的方式。同时，进程同步和互斥也是多线程编程中的重要概念，了解进程同步和互斥的原理和实现方式，有助于编写高效、稳定和可靠的多线程程序。

什么是进程同步、互斥

什么是进程同步

进程具有 异步性 的特点。 异步性是指，各并发执行的进程以各自独立的、不可预知的 速度向前推进

image-20230527112042118

读进程与写进程 并发地运行，由于并发 、必然导致异步性，因此 写数据 和 读数据 两个操作执行的先后顺序是不确定的。而 实际应用中，又必须按照 “写数据 -> 读数据” 的顺序来执行。如何解决这种 异步性问题，就是 进程同步 所要讨论的问题

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

什么是进程互斥

进程的 “并发” 需要 “共享” 的支持。各个并发执行的进程不可避免的需要共享一些系统资源。

image-20230527112521989

我们把 一段时间段内只允许一个进程使用的 资源 称为 临界资源。许多的物理设备都属于临界资源，此外还有许多变量、数据、内存缓冲区都属于临界资源

对于临界资源的访问，必须 互斥 的进行。互斥 ，也被称为 间接制约关系 。 进程互斥 指 当一个进程访问某 临界资源的时候，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问该资源

对于临界资源的访问可以在 逻辑上 分为以下四个部分

image-20230527113126614

注意：

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

为了实现对临界资源的 互斥访问，同时保证系统整体的性能，需要遵守以下原则：

  1. 空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入 临界区
  2. 忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待
  3. 有限等待。对请求访问的进程，应保证能在有限的时间内进入临界区（保证不会饥饿）
  4. 让权等待。当进程不能进入临界区时，应当立即释放处理机，防止进程忙等待。
知识回顾与重要考点
image-20230527113609243

进程互斥的软件实现方法

知识总览

image-20230527113930996
如果没有注意到进程互斥
image-20230527114249459
单标志法

算法思想： 两个进程 在 访问完临界区后 会把使用临界区的权限转交给另一个进程。也就是说 每个进程进入临界区的权限只能被另一个进程赋予

image-20230527121440481

因此，该算法 可以实现 “同一时刻最多只允许一个进程访问临界区

image-20230527121543854
双标志先检查法

算法思想 ：设置一个 布尔数组 flag[]，数组中各个元素用来 标记各进程想进入临界区的意愿，比如 flag[0] = true 意味着 进程 P0 现在想要进入临界区。每个进程在进入之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的 标志 flag[i] 设为 true ，之后开始访问临界区

image-20230527121916768

image-20230527121934181

双标志后检查法

算法思想： 双标志先检查法的改进版。前一个算法的问题是 先 检查 后 上锁，但是这两个操作不是原子性的，因此导致了两个进程同时进入临界区的问题。因此 又想到了 先上锁，后 检查的 方法 来避免上述的问题

image-20230527122140735

image-20230527122225157

Peterson 算法

算法思想：结合 双标志法、单标志法的思想。如果双方都争着想进入 临界区，那么可以尝试让进程 尝试 谦让 。做一个 有礼貌 的进程

image-20230527122402362

Peterson 算法用软件方法解决了 进程互斥问题， 遵循了 空闲让进、忙则等待、有限等待 三个原则，但是 依然 未遵循让权等待 的原则

知识回顾与重要考点

image-20230527122546978

进程互斥的硬件实现方法

知识总览

image-20230527122847975
中断屏蔽方法

利用 开、关中断指令 实现（与 原语的实现思想一致，即 在某进程开始访问临界区到结束访问临界区为止都不允许被中断，也就不能发生进程切换，因此也不可能发生两个同时访问临界区的情况

image-20230527123043453
TestAndSet 指令

简称 TS 指令，也有地方 称为 TestAndSetLock 指令，或 TSL 指令

TSL 指令 使用硬件实现的，执行过程中，不允许被中断，只能一气呵成。

TSL 指令是 Test and Set Lock 的缩写，它是一种用于实现互斥锁的机制，可以在多线程或多进程环境下确保某个共享资源同时只能被一个线程或进程访问和操作。

TSL 指令的作用是将一个指定的内存单元的值与 1 进行比较，如果该内存单元的值为 0，则将其设置为 1 并返回 0，表示获取锁成功；如果该内存单元的值为 1，则返回 1，表示获取锁失败。在多线程或多进程环境下，当一个线程或进程需要访问和操作共享资源时，它可以先执行 TSL 指令尝试获取锁，如果获取成功则可以访问和操作共享资源，否则需要等待其他线程或进程释放锁后再进行尝试。

需要注意的是，TSL 指令的实现需要保证原子性，即在多线程或多进程环境下，任何时刻只能有一个线程或进程执行 TSL 指令，避免出现竞争条件和数据不一致的问题。因此，在实际应用中，TSL 指令通常会与其他机制结合使用，例如自旋锁、信号量等，从而实现更加高效和可靠的互斥锁机制。

image-20230527123216117

Swap 指令

有的地方也叫作 Exchange 指令，或简称 XCHG 指令

Swap 指令 使用 硬件实现的，执行的过程不允许被中断，只能一气呵成

Swap 指令是一种用于实现原子性操作的机制，它可以在多线程或多进程环境下保证某个内存单元的操作是原子性的，避免出现竞争条件和数据不一致的问题。

Swap 指令的作用是将一个指定的内存单元的值与另一个值进行交换，同时返回原始值。在多线程或多进程环境下，当一个线程或进程需要执行原子性操作时，可以先执行 Swap 指令将该内存单元的值与另一个值进行交换，从而实现原子性操作。例如，在实现互斥锁机制时，可以使用 Swap 指令将锁的状态从未锁定到已锁定进行原子性切换。

image-20230527123359613

知识回顾与重要考点

image-20230527123556067

信号量机制

知识总览

image-20230527123649298

用户进程可以通过使用操作系统 提供的一对原语 来对 信号量 进行操作，从而很方便的实现了进程互斥、进程同步

信号量 其实就是一个变量（可以是一个整数，也可以是更复杂的记录型变量），可以用一个信号量来 表示系统中的某种资源的数量，比如：系统中只有一个打印机，就可以设置一个初值为 1 的信号量

原语 是一种特殊的程序段，其 执行只能一气呵成，不可被中断。原语 是由 开关中断指令 实现的。软件解决方法的主要问题是由 “进入区的操作无法一气呵成”，因此如果能把进入区、退出区的操作都用 原语实现，使这些操作都能一气呵成，就能避免问题

一对原语：wait(s) 和 signal(S) ，可以把原语理解为我们自己写的函数，函数名分别为 wait 、signal，括号里的 信号量S 其实就是函数调用是传入的一个参数

wait 、signal 常 简称为 P、V 操作。因此 常写为 P(S)、V(S)

整形信号量
image-20230527130407717
记录型信号量
image-20230527130442042

image-20230527130525528

知识回顾与重要考点

image-20230527130838049

用信号量机制实现 进程互斥、同步、前驱

知识总览

image-20230527130944482
信号量机制实现 进程互斥
image-20230527131036817
信号量机制实现进程同步

进程同步： 要让各进程按要求有序的 推进

信号量是一种用于进程同步的机制，它可以用于控制多个进程或线程对共享资源的访问和操作，以避免出现竞争条件和数据不一致的问题。

信号量机制通常由两个操作组成：wait 和 signal。wait 操作用于获取信号量，如果信号量的计数器大于 0，则将其减 1 并继续执行，否则将当前进程或线程挂起等待其他进程或线程释放信号量。signal 操作用于释放信号量，将其计数器加 1，并通知等待的进程或线程可以继续执行。

image-20230527131410408

用信号量实现 进程同步

  1. 分析什么地方需要实现 “同步关系”，即 必须保证 一前一后的 执行的两个操作
  2. 设置 同步信号量 S，初始 为 0
  3. 在 前操作之后 执行 V(S)
  4. 在 后 操作 之前执行 P(S)

前 V 后 P

image-20230527131611796

理解 ： 信号量 S 代表 “某种资源” ，刚开始是没有这种资源的。P2 需要使用这种资源，而又只能由 P1产生这种资源

image-20230527131817401
信号量机制实现 前驱关系
image-20230527131921463
知识回顾与重要考点

image-20230527132001315

生产者消费者问题

好的，进程中的生产者消费者问题是一种经典的多线程同步和互斥问题，它的主要目的是协调生产者和消费者之间的生产和消费过程，避免出现竞争条件和数据不一致的问题。

生产者消费者问题通常由两个线程组成：生产者和消费者。生产者的主要任务是生产产品并将其放入共享缓冲区中，而消费者的主要任务是从共享缓冲区中取出产品并进行消费。在多线程环境下，生产者和消费者对共享缓冲区的访问和操作需要进行同步和互斥，以避免出现竞争条件和数据不一致的问题。

在实现生产者消费者问题时，可以使用多种同步和互斥机制，例如：

  1. 信号量机制：可以使用两个信号量来控制生产者和消费者之间的同步。一个信号量表示生产者可以继续生产，另一个信号量表示消费者可以继续消费。当生产者生产一个新的产品时，需要通过信号量机制通知消费者可以消费；当消费者消费一个产品时，需要通过信号量机制通知生产者可以继续生产。同时，需要对共享缓冲区的访问和操作进行互斥，避免出现多个生产者或消费者同时访问和操作的情况。可以使用互斥锁或二元信号量来实现互斥。

  2. 条件变量机制：可以使用两个条件变量来控制生产者和消费者之间的同步。一个条件变量表示共享缓冲区不为空，另一个条件变量表示共享缓冲区不为满。当生产者生产一个新的产品时，需要通知消费者条件变量表示共享缓冲区不为空；当消费者消费一个产品时，需要通知生产者条件变量表示共享缓冲区不为满。同时，需要对共享缓冲区的访问和操作进行互斥，避免出现多个生产者或消费者同时访问和操作的情况。可以使用互斥锁来实现互斥。

  3. 信号机制：可以使用 POSIX 信号机制来实现生产者消费者问题。生产者和消费者分别注册一个信号处理函数，当生产者生产一个新的产品时，向消费者发送信号；当消费者消费一个产品时，向生产者发送信号。同时，需要对共享缓冲区的访问和操作进行互斥，避免出现多个生产者或消费者同时访问和操作的情况。可以使用互斥锁来实现互斥。

需要注意的是，在实现生产者消费者问题时，需要考虑多个生产者和消费者之间的同步和互斥，避免出现竞争条件和数据不一致的问题。同时，需要考虑性能和效率的问题，避免出现死锁和饥饿等问题。因此，在实际应用中，应根据具体的应用场景和需求选择合适的同步和互斥机制，并进行适当的优化和调优。另外，需要注意共享缓冲区的大小和缓冲区满或空的情况，避免出现死锁和饥饿等问题。

问题描述
image-20230527133932879
问题分析
image-20230527134003085

image-20230527134033631

image-20230527134048641 image-20230527134105776
知识回顾与重要考点
image-20230527134140051

多生产者-多消费者问题

多消费者多生产者问题是一种更加复杂的多线程同步和互斥问题，它的主要目的是协调多个生产者和多个消费者之间的生产和消费过程，避免出现竞争条件和数据不一致的问题。

在多消费者多生产者问题中，存在多个生产者和多个消费者同时访问和操作共享缓冲区的情况，因此需要采用更加复杂的同步和互斥机制来保证其正确性和稳定性。

在实现多消费者多生产者问题时，可以采用以下几种方法：

  1. 基于信号量机制的实现：可以使用多个信号量来控制多个生产者和多个消费者之间的同步。需要为每个生产者和消费者分配一个信号量，表示其可以继续生产或消费。同时，需要使用互斥锁来对共享缓冲区进行互斥访问和操作，避免出现多个生产者或消费者同时访问和操作的情况。需要注意的是，多个生产者和多个消费者之间的同步需要采用更加复杂的信号量机制，例如使用多个二元信号量或多个计数信号量来实现。

  2. 基于条件变量机制的实现：可以使用多个条件变量来控制多个生产者和多个消费者之间的同步。需要为每个生产者和消费者分配一个条件变量，表示共享缓冲区不为空或不为满。同时，需要使用互斥锁来对共享缓冲区进行互斥访问和操作，避免出现多个生产者或消费者同时访问和操作的情况。需要注意的是，多个生产者和多个消费者之间的同步需要采用更加复杂的条件变量机制，例如使用多个条件变量来实现。

  3. 基于消息队列的实现：可以使用消息队列来实现多个生产者和多个消费者之间的通信和同步。每个生产者将生产的产品放入消息队列中，每个消费者从消息队列中取出产品进行消费。消息队列可以使用 POSIX 消息队列或 System V 消息队列等机制，这些机制可以保证消息的有序和可靠传输。需要注意的是，在使用消息队列时，需要考虑消息队列的大小和缓冲区满或空的情况，避免出现死锁和饥饿等问题。

需要注意的是，多消费者多生产者问题的实现需要考虑多个生产者和消费者之间的同步和互斥，避免出现竞争条件和数据不一致的问题。同时，需要考虑性能和效率的问题，避免出现死锁和饥饿等问题。因此，在实际应用中，应根据具体的应用场景和需求选择合适的同步和互斥机制，并进行适当的优化和调优。

问题描述
image-20230527134338823
问题分析
image-20230527134657152 image-20230527134715600

即使 不设置专门的 mutex ，也不会出现多个进程同时访问盘子的现象

原因在于：本题中的缓存为 1 ，在任何时刻，apple、orange、plate 三个同步信号量中最多只有一个是1,。因此任何时刻，最多只有一个进程的 P 操作不会被阻塞，并且顺利的进入 临界区

如果 盘子（缓冲区容量 ）为2

父母都可以同时往盘子里放东西。于是就出现了 两个进程同时访问缓冲区的情况，有可能导致两个进程写入缓冲区的数据相互覆盖的情况。 如果缓冲区大于1，就必须专门设置一个 互斥信号量mutex 来保证互斥访问缓冲区

知识回顾与重要考点
image-20230527135232207 image-20230527135247042

吸烟者问题

吸烟者问题是一种经典的多线程同步和互斥问题，它的主要目的是协调三个线程之间的行为，以避免出现竞争条件和数据不一致的问题。这三个线程分别代表三个吸烟者和一个服务员，服务员随时准备提供两种材料中的一种，这些材料是吸烟者需要的。吸烟者需要拥有三个不同的材料才能吸烟，因此他们需要协调以获得所需的材料。

在实现吸烟者问题时，可以使用多种同步和互斥机制，例如：

  1. 信号量机制：可以使用三个二元信号量来控制三个吸烟者之间的同步。每个吸烟者分别拥有两个二元信号量，一个表示其拥有的一个材料，另一个表示其拥有的另一个材料。服务员拥有一个二元信号量，表示服务员可以提供一种材料。当服务员提供一种材料时，需要通知拥有另一种材料的吸烟者可以开始吸烟。同时，需要对共享缓冲区的访问和操作进行互斥，避免出现多个吸烟者同时访问和操作的情况。可以使用互斥锁或二元信号量来实现互斥。

  2. 条件变量机制：可以使用三个条件变量来控制三个吸烟者之间的同步。每个吸烟者分别需要拥有两个条件变量，一个表示其拥有的一个材料，另一个表示其拥有的另一个材料。服务员需要拥有一个条件变量，表示服务员可以提供一种材料。当服务员提供一种材料时，需要通知拥有另一种材料的吸烟者可以开始吸烟。同时，需要对共享缓冲区的访问和操作进行互斥，避免出现多个吸烟者同时访问和操作的情况。可以使用互斥锁来实现互斥。

  3. 信号机制：可以使用 POSIX 信号机制来实现吸烟者问题。每个吸烟者和服务员分别注册一个信号处理函数，当服务员提供一种材料时，向拥有另一种材料的吸烟者发送信号。同时，需要对共享缓冲区的访问和操作进行互斥，避免出现多个吸烟者同时访问和操作的情况。可以使用互斥锁来实现互斥。

需要注意的是，在实现吸烟者问题时，需要考虑多个线程之间的同步和互斥，避免出现竞争条件和数据不一致的问题。同时，需要考虑性能和效率的问题，避免出现死锁和饥饿等问题。因此，在实际应用中，应根据具体的应用场景和需求选择合适的同步和互斥机制，并进行适当的优化和调优。另外，需要注意共享缓冲区的大小和缓冲区满或空的情况，避免出现死锁和饥饿等问题。在吸烟者问题中，需要考虑如何避免出现死锁和饥饿的情况，例如使用随机算法或轮询算法来选择下一个吸烟者或服务员，避免出现某个吸烟者或服务员一直被忽略的情况。

问题描述
image-20230527135448119
问题分析
image-20230527135512968 image-20230527135546969 image-20230527135606051
知识回顾与重要考点
image-20230527135656731

读者-写者问题

读者-写者问题是一种经典的多线程同步和互斥问题，它的主要目的是协调多个读者和多个写者之间的访问和操作，避免出现竞争条件和数据不一致的问题。

在读者-写者问题中，存在多个读者和多个写者同时访问和操作共享资源的情况，因此需要采用更加复杂的同步和互斥机制来保证其正确性和稳定性。

在实现读者-写者问题时，可以使用以下几种方法：

  1. 基于信号量机制的实现：可以使用两个信号量来控制多个读者和多个写者之间的同步。一个信号量表示写者可以开始写入，另一个信号量表示读者可以开始读取。当写者开始写入时，需要对共享资源进行互斥访问和操作，避免出现多个写者同时写入的情况。当读者开始读取时，需要对共享资源进行共享访问，避免出现写者正在写入的情况下读者读取到不一致的数据。需要注意的是，需要使用计数信号量或互斥信号量来实现多个读者和多个写者之间的同步。

  2. 基于条件变量机制的实现：可以使用多个条件变量来控制多个读者和多个写者之间的同步。一个条件变量表示写者可以开始写入，另一个条件变量表示读者可以开始读取。当写者开始写入时，需要对共享资源进行互斥访问和操作，避免出现多个写者同时写入的情况。当读者开始读取时，需要对共享资源进行共享访问，避免出现写者正在写入的情况下读者读取到不一致的数据。需要使用互斥锁来实现对共享资源的互斥访问和操作。

  3. 基于读写锁机制的实现：可以使用读写锁来实现多个读者和多个写者之间的同步。读写锁可以允许多个读者同时读取共享资源，但只允许一个写者写入共享资源。当写者开始写入时，需要对共享资源进行互斥访问和操作，避免出现多个写者同时写入的情况。当读者开始读取时，可以使用读写锁来实现对共享资源的共享访问。需要注意的是，读写锁机制需要考虑读者和写者之间的优先级问题，避免出现写者一直等待的情况。

需要注意的是，在实现读者-写者问题时，需要考虑多个读者和写者之间的同步和互斥，避免出现竞争条件和数据不一致的问题。同时，需要考虑性能和效率的问题，避免出现死锁和饥饿等问题。因此，在实际应用中，应根据具体的应用场景和需求选择合适的同步和互斥机制，并进行适当的优化和调优。另外，需要注意共享资源的大小和访问模式的问题，避免出现死锁和饥饿等问题。在读者-写者问题中，需要考虑如何平衡读者和写者之间的优先级和权重，以避免出现某个线程一直等待的情况。可以通过使用优先级队列或轮询算法来选择下一个读者或写者线程，避免出现某个线程被长时间忽略的情况。

问题描述
image-20230527135805534
问题分析
image-20230527135907297
实现
image-20230527135939771
知识回顾与重要考点
image-20230527140032829

哲学家进餐问题

好的，哲学家进餐问题是一种经典的多线程同步和互斥问题，它的主要目的是协调五个哲学家之间的行为，以避免出现竞争条件和死锁的问题。

在哲学家进餐问题中，有五个哲学家坐在圆桌旁，每个哲学家需要思考和进餐。圆桌上有五个餐叉，每个哲学家需要两个餐叉才能进餐。因此，需要协调哲学家之间的行为，避免出现死锁的情况。

在实现哲学家进餐问题时，可以使用以下几种方法：

  1. 基于信号量机制的实现：可以使用五个二元信号量来控制五个哲学家之间的同步。每个哲学家需要先拥有左边的餐叉，再拥有右边的餐叉，才能开始进餐。当一个哲学家拥有左边的餐叉时，需要等待右边的餐叉可用。当一个哲学家进餐完成后，需要释放左边和右边的餐叉，以便其他哲学家可以使用。需要注意的是，需要使用互斥信号量来实现对共享资源的互斥访问和操作，避免出现多个哲学家同时竞争同一个餐叉的情况。

  2. 基于条件变量机制的实现：可以使用五个条件变量来控制五个哲学家之间的同步。每个哲学家需要先拥有左边的餐叉，再拥有右边的餐叉，才能开始进餐。当一个哲学家拥有左边的餐叉时，需要等待右边的餐叉可用。当一个哲学家进餐完成后，需要释放左边和右边的餐叉，以便其他哲学家可以使用。需要使用互斥锁来实现对共享资源的互斥访问和操作，以及条件变量来实现哲学家之间的同步和等待。

  3. 基于管程机制的实现：可以使用管程来实现哲学家进餐问题。管程中包含五个条件变量和一个互斥锁，每个哲学家需要调用管程中的方法来获取和释放左右两个餐叉。当一个哲学家无法获取到所需的餐叉时，需要进入等待队列中等待其他哲学家释放餐叉。需要注意的是，管程的实现需要考虑各个哲学家之间的优先级和公平性问题，避免出现某个哲学家一直等待的情况。

需要注意的是，在实现哲学家进餐问题时，需要考虑多个哲学家之间的同步和互斥，避免出现竞争条件和死锁的问题。同时，需要考虑性能和效率的问题，避免出现饥饿和优先级不公平的情况。因此，在实际应用中，应根据具体的应用场景和需求选择合适的同步和互斥机制，并进行适当的优化和调优。需要注意的是，哲学家进餐问题是一个经典的同步和互斥问题，可以帮助我们理解多线程编程中的重要概念和技术，如互斥锁、条件变量、信号量、管程等。

问题描述
image-20230527142107680
问题分析
image-20230527142146043
实现

如何防止 死锁的发生呢

  1. 可以对哲学家进程施加一些限制条件，比如最多允许 4 个哲学家同时用餐
  2. 要求奇数号 哲学家先拿左边的筷子，然后再拿右边的。用这种方法可以保证 如果相邻的两个哲学家都想吃饭，那么只有一个可以拿起第一只筷子，另一个会直接阻塞。这就避免了 占有一只后，再等待另一只的情况
  3. 仅当一个哲学家左右两个筷子都可用时才允许他拿筷子
image-20230527142715666

更准确的说法应该是：各哲学家拿筷子这件事必须互斥的执行。这就保证了即使一个哲学家在拿筷子拿到一半时被阻塞，也不会有别的哲学家会继续尝试拿筷子。这样的话，当前正在吃饭的哲学家放下筷子后，被阻塞的哲学家就可以获得等待的筷子了。

知识回顾与重要考点

image-20230527142801176

管程

知识总览

image-20230527142932291
为什么引入管程
image-20230527142959069
管程的定义和基本特征

管程是一种 特殊的软件模块，有这些部分组成

  1. 局部于 管程的 共享数据结构 说明
  2. 对该数据结构 进行操作的 一组过程
  3. 对局部与管程的 共享数据设置初始值的语句
  4. 管程有一个名字

可以理解为 封装

Java 之中的 类成员，构造器，方法

管程的基本特征

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

引入管程的目的 无非就是 更方便的实现进程同步与互斥

  1. 需要在管程中定义 共享数据（如生产者消费者问题中的 缓冲区）
  2. 需要在管程中定义用于访问 这些共享数据的入口 —— 其实就是一些函数
  3. 只有 通过这些特定的 入口 才能访问这些共享数据
  4. 管程中 有多个 入口，但是 每次只能开放其中一个入口， 并且 只能让一个进程或者 线程进入。 注意 ： 这种 互斥特性是由编译器负责实现的，程序员不用担心
  5. 可在 管程中设置 条件变量 及 等待/唤醒操作 以解决同步问题。可以让一个线程或者进程在条件变量上等待（此时，该进程应先释放管程的使用权，也就是 让出 出口。可以通过 唤醒操作将等待在条件变量上的进程或者线程 唤醒
知识回顾与重要考点
image-20230527144002726

死锁

死锁是指在多个进程或线程中，每个进程或线程持有一些资源，并且等待其他进程或线程释放它所需要的资源，导致所有进程或线程都无法继续执行的一种状态。在死锁状态下，进程或线程之间的相互等待会形成一个闭环，无法通过简单的资源回收来解决。

死锁通常发生在多个进程或线程之间共享有限的资源时，例如共享内存、文件、设备等。当多个进程或线程同时请求这些资源时，如果它们的请求顺序不当或者资源分配不当，就可能导致死锁的发生。

死锁的主要特征是进程或线程之间的相互等待，这种等待是永久性的，直到外部干预才能解除。在死锁状态下，系统会出现停滞的情况，无法继续执行。为了避免死锁的发生，需要采取一些措施，如避免循环等待、加锁顺序、超时机制、死锁检测等。此外，死锁的解决还需要考虑到锁粒度、资源分配和竞争等问题，需要在程序设计和实现时进行合理的规划和调整。

总之，死锁是一种常见的多线程编程问题，需要在程序设计和实现时充分考虑到各种可能发生的情况和异常，并采用合适的同步和互斥机制，以确保程序的正确性和稳定性。同时，需要进行充分的测试和调试，及时发现和解决各种问题和异常，以确保程序能够正确、稳定地运行。

死锁的概念

知识总览

image-20230527145220390
什么是死锁

死锁是指在多个进程或线程中，每个进程或线程持有一些资源，并且等待其他进程或线程释放它所需要的资源，导致所有进程或线程都无法继续执行的一种状态

在 并发环境下，各进程因 竞争资源而造成的一种 互相等待对方手里的资源，导致各进程都阻塞，都无法向前推进 的现象，就是 死锁

死锁、饥饿、死循环的区别

死锁：各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象。

饥饿：由于长期得不到想要的资源，某进程无法向前推进的现象。比如：在短进程优先（SPF)算法中，若有源源不断的短进程到来，则长进程将一直得不到处理机，从而发生长进程“饥饿”。

死循环：某进程执行过程中一直跳不出某个循环的现象。有时是因为程序逻辑bug导致的，有时是程序员故意设计的。

image-20230527145518789
死锁的产生条件

产生死锁必须 满足一下四个条件，只要其中一个条件不满足，死锁就不会发生

互斥条件： 只有对 必须互斥访问使用的资源的争抢 才会导致死锁

不剥夺条件： 进程所获得的资源在未使用完之前， 不能由其他进程强行夺走，只能主动释放

请求和保持条件：进程 已经保持了至少一个资源，但又提出了新的资源请求，而该资源被其他进程所占有，此时请求进程被阻塞，但又对自己已有的资源 保持 不放

循环等待条件：存在一种进程 资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求

注意 ：发生死锁时 一定有 循环等待，但是发生循环等待时 ，未必 死锁

如果同类资源数大于1，则即使有循环等待，也未必发生死锁。但如果系统中每类资源都只有一个，那循环等待就是死锁的 充分必要条件 了

什么时候会发生死锁
  1. 对系统资源的竞争。各进程对不可剥夺的资源（如打印机）的竞争可能引起死锁，对可剥夺的资源（CPU)的竞争是不会引起死锁的。
  2. 进程推进顺序非法。请求和释放资源的顺序不当，也同样会导致死锁。例如，并发执行的进程P1P2分别申请并占有了资源R1、R2,之后进程P1又紧接着申请资源R2,而进程P2又申请资源R1,两者会因为申请的资源被对方占有而阻塞，从而发生死锁。
  3. 信号量的使用不当也会造成死锁。如生产者消费者问题中，如果实现互斥的P操作在实现同步的P操作之前，就有可能导致死锁。（可以把互斥信号量、同步信号量也看做是一种抽象的系统资源）

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

死锁的处理策略
  1. 预防死锁。破坏死锁产生的 四个必要条件中的一个或几个
  2. 避免死锁。用某种方法防止系统进入不安全状态，从而避免死锁（银行家算法）
  3. 死锁的检测与解除。允许死锁的发生，不过操作系统会负责检测出 死锁的 发生，然后采取某种措施解除死锁
知识回顾与重要考点
image-20230527150559364

死锁的处理策略

预防死锁

知识总览

image-20230527150812033

死锁的产生 必须满足四个必要条件，只要其中一个或者几个不满足，死锁就不会发生

破坏互斥条件

互斥条件： 只有对必须互斥使用 的资源的争抢 才会导致死锁

如果把 只能互斥使用的资源改造为 允许共享访问，则系统就不会进入死锁状态

image-20230527151150679

该策略的 缺点 ： 并不是锁头的资源都可以改造成 可共享使用的 资源。并且为了系统安全，很多地方必须保护这种互斥性。因此，很多时候都无法破坏互斥条件

破坏不剥夺条件

不剥夺条件： 进程所获得 的资源在未使用完成之前，不能由其他的进程强行夺走，只能主动释放

破坏不剥夺条件：

  1. 当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时再重新申请。也就是说，即使某些资源尚未使用完成，也需要主动释放，从而破坏了 不剥夺条件
  2. 当某个进程需要的资源被其他的进程所占用时，可以由操作系统协助，将想要的资源强行剥夺。这种方式一般需要考虑各进程的优先级

该策略的 缺点：

  1. 实现起来比较复杂
  2. 释放已经得到的资源 可能造成之前的工作失效。因此这种方法只适合 易保存和恢复状态的 资源
  3. 反复的申请和释放资源会增加系统的开销，降低系统的吞吐量
  4. 若 采用 1，意味着 只要暂时得不到某个资源，之前获得的那些资源就需要放弃，以后再重新申请。如果一直发生这样的情况，就会导致进程的饥饿
破坏请求和保持条件

请求和保持条件： 进程 已经保持了至少一个资源，但又提出了 新的资源，而该资源又被其他的进程所占有，此时请求进程被阻塞，但又对自己已有的资源 保持 不放

可以采用 静态分配方法，即 进程在运行前 一次申请完它所需要的全部资源，在他的资源未满足前，不让他投入使用。一旦投入运行后，这些资源就一直归他所有，该进程就不会再请求别的资源了

该策略实现起来简单，但也有明显的 缺点：

有些资源可能就需要使用很短的时间，因此如果进程的整个运行期间 都一直保持着所有的资源，就会造成严重的资源浪费， 资源利用率极低。另外，该策略也有 可能导致某些进程饥饿

破坏循环等待条件

循环等待条件： 存在一种进程 资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求

可采用 顺序资源分配法。首先给 系统中的资源编号，规定每个进程 必须按照编号递增的顺序请求资源，同类资源（即编号相同的资源）一次申请完

原理分析： 一个进程只有已经 占有小编号的资源时，才有资格其申请更大 编号的资源。按此规则，已持有大编号资源的进程不能 逆向地 回来申请小编号的资源，从而就不会产生循环等待的现象

image-20230527154509748

该策略的 缺点：

  1. 不方便增加新的设备，因为可能需要重新分配所有的编号
  2. 进程实际使用资源的顺序可能 递增的顺序不一致，会导致资源的浪费
  3. 必须按照规定次序 申请资源，用户编程麻烦
知识回顾与重要考点
image-20230527154651632
避免死锁

知识总览

image-20230527154743340
什么是 安全序列

安全序列是指在进程请求资源之前，先计算出一种安全序列的算法，以保证进程能够顺利地获得其所需要的资源而不会发生死锁。

安全序列算法的基本思路是通过模拟进程请求资源的过程，判断系统是否处于一种安全的状态。如果存在一种安全序列，即所有进程都能够获得其所需的全部资源而不会发生死锁，则该系统是安全的。否则，如果不存在安全序列，即至少有一个进程无法获得其所需的所有资源，那么该系统是不安全的。

安全序列算法通常分为银行家算法和安全状态检测算法两种。其中，银行家算法是一种比较经典的安全序列算法，它通过对进程请求资源的预测和分析，判断系统是否处于安全状态。安全状态检测算法则是通过遍历系统所能达到的所有状态，判断是否存在一种安全状态序列。

在实际应用中，安全序列算法可以用于操作系统中的进程调度和资源分配中，以保证系统的稳定性和安全性。例如，在进程调度中，操作系统可以通过安全序列算法来判断当前系统是否可以上线新的进程，以避免因资源竞争而导致的死锁。在资源分配中，操作系统可以通过安全序列算法来判断当前进程是否能够获得其所需的全部资源，以避免资源竞争和浪费。

需要注意的是，安全序列算法只能判断系统是否处于一种安全状态，但并不能保证在系统运行的过程中，不会出现资源竞争等问题。因此，在实际应用中，还需要结合其他技术和策略，来保证系统的稳定性和安全性。

image-20230527154900575

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

如果分配了资源之后，系统找不到任何一个安全序列，系统就进入了 不安全状态。这就意味着之后 可能 所有的进程都无法顺利地执行下去。当然如果有进程提前归还了一些资源，那 系统也有可能重新回到安全状态，不过我们在分配资源之前总是要考虑到最坏的情况

如果系统处于安全状态，就 一定不会 发生 死锁。如果系统进入 不安全状态，也未必就是发生了死锁，但发生死锁一定是在不安全状态。因此 可以在 资源分配之前预先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应资源的分配请求。 这也是 银行家算法 的核心思想

银行家算法

image-20230527155725149

image-20230527155801079

知识回顾与重要考点

image-20230527155822507

系统处于 不安全状态未必死锁，但死锁时一定 处于不安全状态。系统处于安全状态 一定不会死锁

检测和接触

知识总览

image-20230527163131671

如果系统中既不采取预防死锁的措施，也不采取避免死锁的措施，系统就很可能 发生死锁。在这种情况下，系统应当提供两个算法：

  1. 死锁检测算法：用于检测系统状态，以确定系统中是否发生了 死锁
  2. 死锁解除算法：当 认定系统中已经发生了死锁，利用该算法可将系统从死锁状态中 解脱出来
死锁的检测

为了能对系统是否已经发生了死锁进行检测，必须：

  1. 用某种数据结构 来保存资源的请求和分配信息
  2. 提供 一种算法，利用上述信息来检测系统中是否已进入死锁状态

image-20230527164142251

如果系统中剩余的可用资源数足够满足进程的需求，那么这个进程暂时是不会阻塞的，可以顺利地执行下去。如果这个进程执行结束了把资源归还系统，就可能使某些正在等待资源的进程被激活，并顺利地执行下去。

相应的，这些被激活的进程执行完了之后又会归还一些资源，这样可能又会激活另外一些阻塞的进程…

如果按上述的过程分析，最终 能消除所有边，就称 这个图 可完全简化 的。此时一定 没有发生死锁（相当于找到一个安全序列）

如果最终 不能消除所有的边，那么此时就是发生了 死锁

检测死锁的算法：

  1. 在资源分配图中，找出既不阻塞又不是孤点的进程Pi(即找出一条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量。如下图中，R1没有空闲资源，R2有一个空闲资源。若所有的连接该进程的边均满足上述条件，则这个进程能继续运行直至完成，然后释放它所占有的所有资源）。消去它所有的请求边和分配变，使之称为孤立的结点。在下图中，P1是满足这一条件的进程结点，于是将P1的所有边消去。
  2. 进程Pi所释放的资源，可以唤醒某些因等待这些资源而阻塞的进程，原来的阻塞进程可能变为非阻塞进程。在下图中，P2就满足这样的条件。根据1)中的方法进行一系列简化后，若能消去途中所有的边，则称该图是可完全简化的。
image-20230527165759652

死锁定理： 如果某时刻系统的资源分配图是 不可完全简化的，那么此时 系统 死锁

死锁的解除

一旦检测到死锁的产生，就应该立即解除死锁

补充：并不是系统中所有的进程都是死锁状态，用死锁检测算法 简化资源分配图后，还连着边的那些进程就是死锁进程

解除死锁的主要办法有：

  1. 资源剥夺法： 挂起（暂时放到外存上） 某些死锁进程，并抢占他们资源，将这些资源分配给其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿
  2. 撤销进程法：（或称 终止进程法），强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源。这种方式的优点是 实现简单，但付出的代价可能会很大。因为有些进程可能已经运行了很长时间，已经接近结束了，一旦被终止可谓功亏一篑，以后还得重头再来
  3. 进程回退法： 让一个或多个死锁进程回退到 足以避免死锁的地步。这就要求系统要记录进程的历史信息，设置还原点
知识回顾与重要考点

image-20230527170503014

内存

操作系统中的内存是指计算机中用于存储程序和数据的物理存储器，它是计算机中最基本的存储介质之一。在操作系统中，内存扮演着非常重要的角色，它不仅是进程运行和数据存储的基础，也是操作系统实现各种功能的重要基础之一。

在操作系统中，内存通常被划分为多个逻辑部分，每个部分都有不同的作用和管理方式。其中，最基本的划分方式是将内存分为内核空间和用户空间两部分。内核空间是操作系统内核运行的区域，拥有最高的权限，可以直接访问系统的硬件资源和各种驱动程序，主要用于实现操作系统的各种功能。用户空间则是应用程序运行的区域，通常被划分为多个进程，每个进程拥有自己独立的内存空间，用于存储进程的代码、数据和堆栈等信息。

在操作系统中，内存管理是一项非常重要的工作，它主要包括内存分配、内存回收和内存保护等功能。内存分配是指操作系统将可用的内存分配给进程使用，通常通过动态分配内存块的方式来实现。内存回收则是指当进程不再需要使用内存时，操作系统将其回收并重新分配给其他进程使用，以避免内存空间的浪费。内存保护则是指操作系统通过各种技术和策略，保护进程的内存空间不被其他进程或非法程序所访问和修改，以确保系统的稳定性和安全性。

在实际应用中，内存管理还涉及到很多其他的问题和挑战，例如内存碎片、内存泄漏、内存映射等问题，需要通过各种技术和算法来解决。同时，操作系统还需要考虑内存的物理结构和硬件特性，以优化内存访问的效率和速度。

内存的基础知识

知识总览

image-20230527205841491

什么是内存

内存可存放数据。程序执行前 需要放在内存中才能被 CPU 处理 —— 缓和 CPU 与 硬盘之间的速度矛盾

思考: 在多道程序环境下，系统中会有多个程序并发执行，也就是说会有多个程序的数据需要同时放到内存中，那么如何区分 各个程序的数据时 放在什么地方呢

方案： 给内存的存储单元编地址

image-20230527210537701

装入模块的三种方式

  1. 绝对装入
  2. 可重定位装入（静态重定位）
  3. 动态运行时装入（动态重定位）
绝对装入

绝对装入：在编译时，如果知道 程序将放到内存的那个位置，编译程序将产生 绝对地址的 目标代码。装入程序按照装入模块中的地址，将程序和数据装入内存

绝对装入 只适用于单道程序环境

程序中使用的绝对地址，可在编译或者汇编时给出，也可由程序员直接赋予。通常情况下都是编译或者汇编时在转换为 绝对地址

可重定位装入

静态重定位： 又称可重定位装入。编译、链接后的装入模块的地址都是从 0 开始的，指令中使用的地址、数据存放的地址都是相对于起始地址而言的逻辑地址。可根据内存的当前情况，将装入模块装入到内存的适当位置。装入时对地址进行 重定位，将逻辑地址变换为 物理地址（地址变化是在装入时一起完成的）

image-20230527211053902
动态运行时装入

动态重定位：又称 动态运行时装入。编译、链接后的装入模块的地址都是从0 开始的，装入程序 把装入模块装入内存后，并不会立即把逻辑地址转换为 物理地址，而是把 地址转换延迟到程序真正要执行时才进行。因此 装入内存后所有的地址 依然是逻辑地址。这种方式需要一个重定位寄存器的支持

image-20230527211644637 image-20230527211716811 image-20230527212040776
三种方式
image-20230527212119280
知识回顾与重要考点

image-20230527212148643

内存管理的概念

内存管理

image-20230527212319134

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

  1. 内存空间的分配与回收
  2. 操作系统负责 提供某种技术从逻辑上 对内存空间进行扩充
  3. 操作系统需要提供地址转换功能，负责程序的 逻辑地址 与 物理地址 的转换
    • 为了使 编程更方便，程序员写应用时应该只需要关注 指令、数据的逻辑地址。而 逻辑地址到物理地址的转换（这个过程称为 地址重定位） 应该由 操作系统负责
  4. 操作系统需要提供 内存保护 功能。保证各功能进程在 各自存储空间上运行，互不干扰
    1. 在 CPU中 设置 一对 上、下限寄存器，存放进程的上下限地址。进程的指令要访问某个地址时，CPU 需要检查是否越界
    2. 采用 重定位寄存器（又称 基址寄存器） 和 界地址寄存器（又称 限长寄存器） 进行越界检查。重定向寄存器存放的是 进程的 起始物理地址。界地址寄存器中存放的是进程的 最大逻辑地址

操作系统中内存空间的分配与回收是内存管理的核心功能之一，主要是为了合理地利用内存空间，避免浪费，提高内存利用率。一般来说，内存分配与回收是由操作系统的内存管理模块来负责的

知识回顾与重要考点

image-20230527213516761

覆盖与交换

知识总览

image-20230527213551861

覆盖技术

覆盖技术是一种内存管理方法，用于解决内存空间有限的情况下，进程需要使用较大的内存空间的问题。其基本思想是将进程的代码和数据划分为若干个逻辑段，并在程序运行时，将同一时间不需要使用的段从内存中交换出去，以腾出空间来加载其他段。

覆盖技术主要有两种实现方式：静态覆盖和动态覆盖。静态覆盖是在编译时就确定好哪些代码和数据需要交换出去，并生成相应的链接程序，这种方式可以提高程序的执行效率，但灵活性较差。动态覆盖则是在程序运行时根据需要进行内存交换，可以实现更灵活的内存管理，但需要付出更高的运行开销。

需要注意的是，虽然覆盖技术可以有效地解决内存空间不足的问题，但也会带来一些额外的开销和问题，如内存交换和数据丢失等。因此，在实际应用中，需要根据具体的需求和情况，综合考虑各种因素，并采用合适的内存管理技术来保证系统的稳定性和性能。

引入 覆盖技术，用来解决 程序大小 超过物理内存总和 的问题

image-20230527213715964

image-20230527213840088

必须由程序员声明覆盖结构，操作系统完成自动覆盖。 缺点： 对用户不透明，增加了 用户编程的负担。覆盖技术只用于早期的操作系统中。

交换技术

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

image-20230527214141434

中级调度（内存调度）： 就是要决定哪个处于挂起状态而进程重新回 内存

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

挂起态又可以进一步细分为 就绪挂起、阻塞挂起 两个状态

image-20230527214322980
  1. 应该在外存（磁盘） 的什么位置保存被换出的进程
    • 具有对换功能的操作系统中，通常把磁盘空间分为 文件区 和 对换区 两部分。文件区 主要用于存放文件，主要追求存储空间的利用率，因此对文件区空间的管理采用 离散分配方式； 对换区 空间只占磁盘空间的小部分， 被换出的进程数据就存放在对换区。由于 对换的速度直接影响到系统的整体速度，因此对换区的管理 主要要求换入换出速度，因此主要采用 连续分配方式。总之， 对换区的 I/O 速度比文件区 更快
  2. 什么时间应该交换
    • 交换通常在许多进程运行且内存吃紧的时候进行，而系统负荷降低就停止。如果缺页率明显下降，就暂停换出
  3. 应该换出哪些进程
    • 可优先换出 阻塞进程；可优先换出 优先级低的进程；为了防止优先级低的进程在调入内存后很快被换出，有的系统还会考虑金成宰内存中的 驻留时间

PCB 会常驻 内存，不会被换出外存

知识回顾与重要考点

image-20230527215727070

连续分配管理方式

知识总览

image-20230527220949841

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

单一连续分配

在 单一连续分配中，内存被分为 系统区 和 用户区

系统区通常位于 内存的低地址部分，用于存放操作系统的相关数据； 用户区用于存放用户进程相关的数据

内存中 只能有一道用户程序，用户程序独占整个用户区空间

优点：实现简单； 无外部碎片；可以采用 覆盖技术扩充内存；不一定需要采取内存保护

缺点： 只能用于单用户、单任务的操作系统； 有内部碎片；存储器利用率极低

固定分区分配

在多道程序系统中，为了能在内存中装入多道程序，且这些程序之间又不会相互干扰，于是将整个 用户空间 划分为 若干个固定大小的分区，在 每个分区中只装入一道作业，这样就形成了最早的、最简单的一个可运行多道程序的内存管理方式

image-20230527221524323 image-20230527221537387
  • 分区大小相等 ： 缺乏灵活性，但是很 适用用于 用一台计算机控制多个相同对象的场合
  • 分区大小不等 ：增加了灵活性，可以满足不同大小的进程需求。根据在系统中运行的作业大小情况进行划分
image-20230527221716385

动态分区分配

动态分区分配 又称为 可变分区分配。这种分配方式 不会预先划分内存分区，而是在进程装入内存时， 根据进程的大小 动态地建立分区，并使分区的大小正好适合进程的需要。因此系统分区的大小和数目是可变的

image-20230527222349655 image-20230527222403219 image-20230527222434738

动态分区分配 没有内部碎片，但是有 外部碎片

  • 内部碎片： 分配给某进程的内存区域中，如果有些部分没有用上
  • 外部碎片： 是指 内存中的某些空闲分区由于太小而难以利用

如果内存中空闲空间的总和本来可以满足某进程的要求，但由于 进程需要的是一整块连续的空间，因此这些 碎片 不能满足进程的需求

可以通过 紧凑（拼凑，Compaction) 技术 来解决碎片问题

动态分配算法

知识总览

image-20230527223209464

在动态分区分配方式中，当有很多个空闲的分区都能满足需求，应该选择那个分区进行分配

首次适应算法

算法思想： 每次都从地址开始查找，找到第一个能满足大小的空闲分区

如何实现： 空闲分区以地址递增的次序排列。每次分配内存时 顺序查找 空闲分区链（或者 空闲分区表），找到大小能满足需求的第一个空闲分区

image-20230527223423432
最佳适应算法

算法思想： 由于动态分区分配是一种连续分配的方式，为各进程分配的空间必须是连续的一整片的区域。因此为了保证 当 大进程到来时 能有连续的大片空间，可以尽可能多的留下 大片的空闲区，即 优先使用小的空闲区

如何实现： 空闲分区 按容量递增次序链接。每次分配内存时顺序查找 空闲分区链（空闲分区表），找到大小能满足要求的第一个空闲的分区

image-20230527223731250
最坏适应算法

又称 最大适应算法

算法思想： 为了解决最佳适应算法的问题 —— 即 留下太多难利用的小碎片，可以在每次分配时 优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，更方便使用

如何实现： 空闲分区 按 容量递减次序链接。每次分配内存是顺序查找 空闲分区链或者空闲分区表，找到大小能满足的第一个空闲分区

image-20230527224140983
邻近适应算法

算法思想： 首次适应算法每次都要从 链头开始查找。这可能导致低地址出现很多很小的空闲分区，而每次分配查找时，都要经过这些分区，因此也增加了 查找的开销。如果每次都从结束的位置开始检索，就能解决以上问题

如何实现： 空闲分区以地址递增的顺序排列（可排成一个循环链表）。每次分配内存时 从上次查找结束的位置开始 查找 空闲分区链（或者 空闲分区表），找到第一个满足的分区

image-20230527224527470
知识回顾与重要考点
image-20230527224549783

知识回顾与重要考点

image-20230527223002616

基本分页存储管理的基本概念

知识总览

image-20230527225058750

什么是 地址空间

image-20230527225201530

什么是分页存储

分页存储是一种常用的内存管理方式，其基本思想是将进程的逻辑地址空间划分为固定大小的页面（Page），将物理地址空间划分为相同大小的页框（Page Frame），并通过页表将进程的页面映射到物理页框中。每个页表项包含了相应页面的物理地址和一些控制信息，用于实现地址转换和内存保护等功能。

在分页存储中，每个页面的大小通常为2的幂次方，如2KB、4KB、8KB等，页框的大小也与页面相同。当进程需要访问某个页面时，操作系统将其对应的页表项加载到内存中，并将其映射到相应的物理页框中。如果物理页框数量不足，则需要将一部分页面置换到磁盘上，以腾出空间来加载新的页面。当需要访问被置换出的页面时，操作系统会将其从磁盘中读取并重新映射到内存中。

分页存储的优点是可以实现虚拟内存和内存保护等功能，同时可以避免外部碎片的问题。通过合理地设置页面大小和页框数量，可以提高内存利用效率，同时也可以降低程序的开发难度和内存管理的复杂度。但其缺点是需要额外的页表和页表项来管理映射关系，同时对于大块内存的分配和回收，也需要进行额外的处理。

在实际应用中，分页存储通常与其他内存管理技术相结合使用，如页面置换、页面预取等。同时，还需要注意分页存储对系统性能和开销的影响，以及对于进程的地址空间和访问模式的影响，避免因错误的设置或使用导致系统的不稳定性和安全性问题。****

image-20230527225239220

重要的数据结构 —— 页表

为了能知道 进程的每个页面在内存中的位置，操作系统要为 每个进程建立一张 页表 页表通常存在 PCB 中

image-20230527225629903
每个页表项占多少个字节
image-20230527225822669

页表项连续存放，因此页号可以是隐含的，不占存储空间（类比数组）

如何实现地址的转换

进程在内存中 连续存放时，操作系统是如何实现 逻辑地址到 物理地址的 转换的

image-20230527230036421 image-20230527230056577

如何确定一个逻辑地址 对应的页号、页内偏移量

image-20230527230144693 image-20230527230206160

image-20230527230307382

为何页面大小要取 2 的整数幂

image-20230527230334355

逻辑地址结构
image-20230527230714650

知识回顾与重要考点

image-20230527230759130

基本地址变换机构

知识总览

image-20230528153808465

基本地址变换机构可以借助进程的页表将逻辑地址转换为物理地址

通常会在系统中设置一个 页表寄存器（PTR） ，存放 页表在内存中的起始地址F 和 页表长度M。

进程未执行时，页表的始址 和 页表长度 放在进程控制块（PCB）中，当进程被调度时，操作系统内核会把他们放到页表寄存器中

注意： 页面大小是 2 的整数幂

设页面大小是 L，逻辑地址A 到 物理地址 E 的变换过程如下：

image-20230528154216151 image-20230528154659414

image-20230528154715866

image-20230528154836488

知识回顾与重要考点

image-20230528154905214

具有快表的地址变换机构

知识总览

image-20230528155240090

什么是快表

快表，又称 联想寄存器（TLB，translation lookaside buffer),是一种 访问速度比内存快很多的 高速缓存（TLB 不是内存），用来存放 最近访问的页表项的副本，可以加速地址变换的速度，与此对应，内存中的 页表被称为 慢表

image-20230528155451734

image-20230528155505928

引入快表后，地址的变换过程

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

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

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

    由于查询快表的速度比查询页表的速度快很多，因此只要快表命中，就可以节省很多时间。因为局部性原理，一般来说快表的命中率可以达到90%以上。

    例：某系统使用基本分页存储管理，并采用了具有快表的地址变换机构。访问一次快表耗时1us,访问一次内存耗时100us。若快表的命中率为90%,那么访问一个逻辑地址的平均耗时是多少？(1+100)*0.9+(1+100+100)*0.1=111us有的系统支持快表和慢表同时查找，如果是这样，平均耗时应该是（1+100)*0.9+(100+100)*0.1=110.9us

    若未采用快表机制，则访问一个逻辑地址需要100+100=200us

    显然，引入快表机制后，访问一个逻辑地址的速度快多了。

image-20230528155815933

既然存不下整个页表，那么 万一 TLB 满了怎么办

选择淘汰 一些页表项 —— 置换算法

局部性原理

时间局部性

如果执行了 程序中的某条指令，那么不久后这条指令很有可能再次执行；如果某个数据被访问过，不久之后该数据很可能再次被访问（因为程序存在大量的循环）

空间局部性

一旦程序访问了某个存储单元，在不久之后，其附近的存储单元 也很有可能被访问（因为很多数据在内存中都是连续存放的）

上一小节的 基本地址变换机构中， 每次都要访问一个逻辑地址，都需要查询内存中的页表。由于局部性原理，可能连续多次查询到的都是同一个表项

知识回顾与重要考点

image-20230528160256824

TLB 与 普通 cache 的区别 —— TLB 中只有 页表项，而普通 cache 中可能会有其他数据的副本

两级页表

知识总览

image-20230528160408013

单页表存在的问题

image-20230529222058022

根据局部性原理可知， 很多时候， 进程在一段时间内只需要访问某几个页面 就可以正常运行了。因此 没有必要让整个页面都常驻内存

如何解决
  1. 页表必须连续存放，因此当页表很大时， 需要占用很多个连续的页框
  2. 没有必要让整个页表常驻内存，因为进程在一段时间内可能只需要访问某几个特定的页面

把 页表再分页 并离散存储，然后再建立一张页表记录页 记录页表各个部分的存放位置，称为 页目录表， 或 称 外层页表，或称 顶级页表

两级页表的原理、地址结构

image-20230529222540229 image-20230529222724110

如何实现地址变换

image-20230529222812169

如何解决单机页表的问题

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

可以在需要访问页面时才把 页面调入内存（虚拟存储技术），可以在页表项中增加一个标志位，用于表示该页面是否已经调入内存。

image-20230529223040126

需要注意的问题

image-20230529223058798

知识回顾与重要考点

image-20230529223235471

基本分段存储管理方式

知识总览

image-20230529223321246

分段

进程的地址空间：按照程序 自身逻辑 关系 划分为若干个段，每个段都有一个段名（在低级语言中，程序员使用段名来编程），每段从 0 开始编址

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

image-20230529224804442

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

image-20230529224857003

段表

问题： 程序分多个段，各段离散的装入内存，为了保证程序能正常运行，就必须从物理内存中找到各个逻辑段的存放位置。为此，需为每个进程建立一张 段映射表，简称 段表

image-20230529225232815

地址变换

image-20230529225309212

image-20230529225507401

分段、分页管理的对比

页 是 信息的物理单位。 分页的目的是为了实现离散，提高 内存的利用率。分页仅仅是系统管理上的需要，完全是系统行为， 对用户是不可见的

段 是 信息的逻辑单位。分段的主要目的是为了更好的满足用户需求。一个段通常包含一组属于一个逻辑模块的信息。 分段对用户是可见的，用户编程时需要显式的给出段名

页的大小固定且由系统决定。段的长度不固定，决定于用户编写的地址

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

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

image-20230529230025229

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

不能被修改的代码称为 纯代码 或者 可重入代码（不属于临界资源），这样的代码是可以共享的。可修改的代码是不能共享的

image-20230529230201722 image-20230529230233401

访问一个逻辑地址需要几次访存

  • 分页（单机页表）：
    • 第一次访存 —— 查内存中的快表，第二次访存 —— 访问目标内存单元。 总共两次
  • 分段
    • 第一次访存 —— 查内存中的 段表，第二次访存 —— 访问目标内存单元，总共 两次
  • 与分页系统类似，分段系统中 也可以引入 快表机制，将近期访问过的段表放到快表中，这样可以 减少一次访问，加快速度

知识回顾与重要考点

image-20230529230747318

段页式管理方式

知识总览

image-20230529230822269

分页、分段的优缺点分析

image-20230529230846122

分段 + 分页 = 段页式管理

image-20230529230925591

段页式管理的逻辑地址

image-20230529230958632

段表、页表

image-20230529231128063

每个段对应一个段表项，每个段表项由 段号、页表长度、页表存放块号（页表起始地址） 组成。每个 段表项长度相等，段号是隐含的

每个页面对应一个页表项，每个页表项由 页号、页面 存放的内存块号组成。每个页表项的长度相等，页号是隐含的

image-20230529231355094

知识回顾与重要考点

image-20230529231422176

虚拟内存

知识总览

image-20230529231806214image-20230529231826750

传统存储管理方式的特征、缺点

image-20230529232037935

一次性 ： 作业必须一次性全部装入内存后才能开始运行。这会造成两个问题：

  1. 作业很大时，不能全部装入内存，导致 大作业无法运行
  2. 当大量作业要求运行时，由于内存无法容纳所有的作业，因此只有少量的作业能运行，导致 多道程序并发度下降

驻留性： 一旦作业被装入内存，就会 一致驻留在内存中，直至作业运行结束。事实上，在一个时间段内，只需要访问作业的一部分数据即可 正常运行，这就导致了 内存中会驻留大量的、暂时用不到的 数据。浪费了宝贵的内存资源

局部性定理

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

虚拟内存的定义与特征

image-20230529233111543
定义

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

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

若内存不够， 由 操作系统负责 将内存中 暂时用不到的信息换出外存

在操作系统 的管理下，在用户看来似乎有一个比 实际内存大得多的内存， 这就是 虚拟内存

操作系统 虚拟性的一个体现，实际的物理内存大小没有变，只是逻辑上进行了 扩充

易混知识点

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

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

image-20230529233530266
特征

虚拟内存头以下三个主要特征

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

如何实现虚拟内存技术

虚拟内存技术，允许一个作业分多次调入内存。如果采用连续分配方式，会不方便实现。因此，虚拟内存的实现需要 建立在 离散分配 的内存管理方式基础上

image-20230529233907035image-20230529233916524

主要区别：

  • 在程序执行的过程中，当 所 访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存， 然后再继续执行程序
  • 若内存空间不够，由操作系统负责 将内存中暂时用不到的信息换出外存
    • 操作系统要提供页面置换（或 段置换） 的功能

知识回顾与重要考点

image-20230529234148234

请求分页管理方式

知识总览

image-20230530095553000

注意与基本分页存储管理页表机制、地址变换的流程 对比学习

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

在程序执行过程中，当 访问的信息不在内存中时，由操作系统从外存调入内存中，然后执行程序

操作系统要提供请求调页 功能，将 缺失的页面 从外存调入内存

若内存空间不够，由操作系统负责 将内存中暂时用不到的信息换出外存

操作系统要提供 页面置换功能，将暂时用不到的信息调出外存

页表机制

image-20230530100652546

与基本分页管理相比，请求分页管理中，为了实现 “请求调页” 。操作系统需要知道每个页面是否已经调入内存；如果还没调入，那么 也需要知道该页面在外存中存放

当内存空间不够时，要实现 “页面置换” ，操作系统需要通过 某些指标来决定到底换出那个页面；有的页面没有被修改过，就不用再 浪费时间写回外存。有的页面修改过，就需要将外存中的旧数据覆盖，因此，操作系统也需要记录各个页面是否被修改的 信息

缺页中断机构

在请求分页系统中，每当要访问 的 页面不存在时，内存便产生一个 缺页中断，然后由操作系统的 缺页中断处理程序 处理中断

此时 缺页的进程阻塞，放入阻塞队列，调页 完成后再将其唤醒，放回就绪队列

如果内存中 有空闲块，则为进程 分配一个空闲块，将所缺页面装入页面，并修改页表中 相应的页表项

如果内存中 没有空闲块，则由 页面置换算法选择一个页面淘汰，若该页面在内存期间被修改过，则要将其 写回外存。未修改过的页面就不用写回外存

image-20230530101258168

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

一条指令 在执行期间， 可能产生多次缺页中断。如 ：copy a to b ,即将逻辑地址a 中的数据复制到逻辑地址 b ，而 a b 属于不同的 页面，则有可能产生两次中断

地址变换机构

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

  • 在程序执行过程中，当所 访问的信息不在内存中时，由操作系统负责将所需信息从外存调入内存，然后执行程序
  • 若 内存不够，由 操作系统负责 将内存中暂时用不到的信息换出外存

​ image-20230530101818654

image-20230530101846198

请求分页地址变换过程

image-20230530101931080

知识回顾与重要考点

image-20230530102054142

页面置换算法

知识总览

image-20230530102237250

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

  • 在 程序执行过程中，当 所访问的信息不在内存的时候，由操作系统负责将所需要的信息由外存调入内存，然后执行程序
  • 若内存空间不够的时候，由操作系统负责 将内存中 暂时用不到的信息换出外存
    • 用页面 置换算法决定换出哪个页面

最佳置换算法

最佳置换算法（OPT，Optional）：每次选择 淘汰的页面 将是 以后不再使用的，或者在长时间内不再被访问的页面，这样可以保证最低的 缺页率

image-20230530123928003

最佳置换算法（OPT) 可以保证最低的缺页率，但实际上，只有在进程执行的过程中才有可能知道 接下来要访问的页面是哪个。操作系统无法提前预判页面访问序列。因此 **最佳置换算法是无法实现的 **

先进先出算法

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

实现方法： 把调入内存的页面根据调入的先后顺序排列成一个队列，需要换出 页面时选择队头页面即可

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

image-20230530124505232

image-20230530124530138

Belady 异常 —— 当为进程分配的物理块数增大时，缺页次数不减反增的异常现象

只有 FIFO 算法会产生 Belady 异常。另外 FIFO 实现虽然非常简单，但是该算法与进程实际运行的 规律不适应，因为先进入的页面 也有可能最经常被访问，因此 算法性能差

最近最久未使用置换算法

最近最久未使用置换算法（LRU、Least recently used): 每次**淘汰的页面 ** 都是 最近最久未使用的页面

实现方法：赋予每个页面对应的页表项中，用 访问字段记录该页面自上次以来被访问所经历的时间t。 该算法的实现需要专门的硬件支持，虽然算法 性能好，但是实现困难，开销大

当需要淘汰一个页面时，选择现有页面中 t 最大的，即 最近最久未使用的页面

image-20230530130701898

image-20230530130646062

时钟置换算法

最佳置换算法性能最好，但是无法实现；先进先出置换算法实现简单，但算法性能差；最近最久未使用置换算法性能好，是最接近 OPT 算法性能的，但是实现起来需要专门的 硬件支持，算法开销大。

时钟置换算法 是一种 性能和开销比较均衡的算法，又称 CLOCK 算法，或最近未用 算法（NRU，Not Recently Used）

**简单的 CLOCK 算法 ** 实现方法：为每个页面设置一个 访问位，再将内存中的页面都通过 链接指针 链接成一个简单的循环队列。当某页被访问时，其访问位置为1。当需要淘汰一个页面时，只需检查页的访问位。如果是 0，就选择该页换出；如果是1，则将它置为0，暂不换出，继续检查下一个页面，若第一轮扫描中所有的页面都是1，则将这些页面的访问位都置为0，再进行第二轮扫描（第二轮扫描中一定会有 访问位为0 的页面，因此 简单的 CLOCK 算法 选择一个淘汰页面 最多会经过两轮扫描

image-20230530131735164

改进型的时钟置换算法

简单的时钟置换算法 仅考虑一个页面是否最近被访问过，事实上，如果被淘汰的页面没有被修改过，就不需要执行 I/O 操作写回外存。 只有被淘汰的页面被修改过，才需要写回外存

因此，除了考虑一个页面最近有没有被访问过之外，操作系统还应该考虑 页面有没有被修改过。在其他的条件都相同时，应优先淘汰没有被修改过的页面，避免 I/O 操作。这就是 改进型的 时钟置换算法的思想。

修改位 = 0，表示页面没有被修改过；

修改位 = 1，表示页面被修改过

为方便讨论，用（访问位，修改位）的形式表示各页面状态。如（1,1)表示一个页面近期被访问过，1.被修改过。

image-20230530132314532

image-20230530132350459

知识回顾与重要考点

image-20230530132409065

页面分配策略

知识总览

image-20230530132457639

页面分配

驻留集： 指请求分页存储管理中给进程分配的物理块的集合

在采用了 虚拟存储技术的系统中，驻留集的大小一般小于进程的总大小。

若驻留集太小，会导致缺页频繁，系统要花大量的时间处理缺页。 驻留集太大，又会导致多道程序并发下降，资源利用率降低

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

置换策略

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

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

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

系统会锁定一些页面，这些页面中的内容不能被换出外存

可变分配局部置换（Variable Partitioning with Local Replacement）是一种内存管理方式，与可变分配全局置换类似，也是将内存空间划分为多个大小不同的分区，每个分区可以分配给一个进程使用。但不同的是，在内存不足时，可变分配局部置换只会考虑当前进程内部的页面置换，即只会将该进程中的一部分页面置换到磁盘中，以腾出空间来加载其他页面或进程。可变分配局部置换通常使用局部置换算法，如FIFO、LRU等。当进程需要访问被置换出的页面时，系统会将其从磁盘中读取并重新映射到内存中。与全局置换不同的是，局部置换只会影响当前进程，不会影响其他进程的内存使用。

何时调入页面

  • 预调页机制：根据局部性原理，一次调入若干个相邻的界面可能比一次调入一个页面更加有效。但如果调入的页面大多数没被访问过，则又是低效的 。因此可以预测不久之后可能访问到的页面，将他们预先调入内存，但目前预测成功率只有 50% 左右。故这种策略 主要用于 进程的首次调入，由程序员指出 应该先调入哪些部分
  • 请求调页策略： 进程 在运行期间发现缺页时才将所需要的页面调入内存。由这种 策略调入的页面一定会被访问到，但由于每次只能调入一次，而每次调入都要 访问 I/O 操作，因此 I/O 开销比较大

何处调入页面

image-20230530205608343image-20230530205825077

  1. 系统拥有 足够的对换区空间 ：页面的调入、调出 都是在 内存与 对换区 之间进行的，这样可以保证页面的 调入 、调出 速度很快。在进程运行之前，需将进程相关的数据从文件区复制到 对换区
  2. 系统缺少足够的 对换区： 凡是不会被修改的数据都直接从文件区调入，由于这些页面不会被修改，因此 换出时不需要写回磁盘，下次需要时再从 文件区调即可。对于可能被修改的部分，换出时 需要写回磁盘对换区，下次需要时再从对换区 调入
  3. UNIX 方式 ：运行之前 进程有关的数据全都放在 文件区，故 未使用过的 页面，都可从文件区调入。若被使用过的页面需要换出，则 写回对换区，下次需要时 再从对换区调入

抖动（颠簸）现象

刚刚换出的页面 马上又要 换入内存，刚刚换出的页面马上又要调入内存，这种 频繁的 页面调度行为 称为 抖动 或称 颠簸。 产生抖动的主要原因 是 进程频繁访问的 页面数高于可用的物理块数（分配给进程的物理块数不够）

为了研究为每个进程应该分配多少个物理块， Denning 提出了 进程工作集 概念

工作集

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

操作系统会根据 窗口尺寸 来算出工作集

image-20230530210809375

知识回顾与重要考点

image-20230530211043460

文件

操作系统中的文件管理是指操作系统对文件进行管理和操作的一系列功能。文件是计算机系统中存储数据的基本单位，操作系统需要负责对文件进行创建、读取、写入、修改、删除等操作，同时也需要对文件进行保护、备份、恢复等操作，以保证文件的安全性、完整性和可靠性。

文件管理通常包括以下几个方面的功能：

  1. 文件的创建和删除：操作系统提供相应的系统调用，使得用户可以方便地创建和删除文件。

  2. 文件的读取和写入：操作系统提供相应的系统调用和文件指针等机制，使得用户可以方便地对文件进行读取和写入操作。

  3. 文件的修改和更新：操作系统需要对文件进行版本控制、锁定等操作，以保证文件的完整性和一致性。

  4. 文件的保护和权限控制：操作系统需要对文件进行访问控制，设置相应的权限和保护策略，以保证文件的安全性和保密性。

  5. 文件的备份和恢复：操作系统需要对文件进行备份和恢复操作，以防止因文件损坏或丢失而导致的数据丢失问题。

  6. 文件的索引和检索：操作系统需要对文件进行索引和检索，以方便用户快速找到所需文件。

在实现文件管理功能时，操作系统通常会涉及到文件系统、目录结构、文件访问控制和文件操作等方面的问题。文件系统是指操作系统对文件进行组织和管理的方式，包括FAT、NTFS、EXT等不同的文件系统类型。目录结构是指操作系统对文件进行分类和组织的方式，包括树形目录结构、平面目录结构等不同的结构类型。文件访问控制是指操作系统对文件进行权限控制和保护的方式，包括基于用户、组、角色等不同的访问控制模型。文件操作是指操作系统提供的对文件进行读取、写入、修改、删除等操作的接口和实现方式。

需要注意的是，在实际应用中，文件管理涉及到许多细节和技术，如缓存管理、磁盘空间管理、文件系统优化等问题。操作系统需要根据具体的需求和应用场景，选择合适的文件管理策略和技术，以满足用户的需求和系统的性能要求。同时，还需要注意文件管理对系统的安全性和稳定性的影响，避免因文件访问控制不当、文件损坏等问题导致数据丢失、程序崩溃等问题。

初识文件管理

一个文件有哪些属性

  • 文件名： 由 创建文件的 用户决定文件名，主要是为了 方便用户找到文件， 同一文件夹下不允许有重名文件
  • 标识符： 一个系统内的各文件标识符唯一，对用户来说毫无可读性，因此标识符只是操作系统用于区分各个文件的一种内部名字
  • 类型： 指明文件的类型
  • 位置： 文件存放的路径（让用户使用）、在外存中的地址（操作系统使用，用户不可见）
  • 大小： 指明文件大小
  • 创建时间、上次修改时间、文件所有者信息
  • 保护信息： 对文件进行保护的 访问控制信息

image-20230530212113463image-20230530212126652

操作系统向上提供哪些功能

image-20230530212842237
  • 可以 创建文件， 点击新建文件后，背后调用 create 系统调用
  • 可以 读文件，将文件数据读入内存，才能让 CPU 处理，（应用程序 通过操作系统调用 读文件功能， 即 read 系统调用，将文件数据从 外存读入 内存
  • 可以 写文件，将更改过的文件数据写回外存，编辑文件点保存后， 记事本 通过 操作系统 提供的 写文件 功能，即 write 系统调用，将文件 写回 外存
  • 可以 删除文件，点击删除之后，通过系统提供的 删除功能， 即 delete 系统调用，将文件从外存删除

image-20230530213003374image-20230530213019202

其他需要操作系统 实现的 文件管理功能

  • 文件共享：使多个用户可以共享一个文件
  • 文件保护：如何保证不同用户对文件有不同的操作权限

知识回顾与重要考点

image-20230530213159063

文件的逻辑结构

知识总览

image-20230530213442888

无结构文件

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

无结构文件：文件内部的数据就是一系列二进制流或字符流组成。 又称 流式文件

文件内部的数据就是 一系列的字符流，没有明显的结构特性

有结构文件

image-20230530214555497

有结构文件： 由一组 相似的记录组成，又称 记录式文件。每条记录又由 若干个数据项组成。 如 数据库表

一般来说，每条记录有一个数据项可作为 关键字。根据各条记录的长度（占用的空间) 是否相等，可分为 定长记录 和 可变长记录 两种

image-20230530214500474

image-20230530214525917

顺序文件

顺序文件： 文件中的一个记录一个接一个地顺序排列（逻辑上），记录可以是 定长 的 或者是 可变长 的。各个记录在物理上可以 顺序存储 或 链式存储

image-20230530214915520

image-20230530215022451

索引文件

索引是指操作系统对文件进行索引和检索的一种方法。索引通常包括文件名、文件属性、文件位置等信息，以便用户可以方便地查找和访问所需的文件。

image-20230530220147339

索引顺序文件

索引文件的缺点：每个记录对应一个索引表项，因此索引表可能会很大。比如：文件的每个记录平均只占8B,而每个索引表项占32个字节，那么索引表都要比文件内容本身大4倍，这样对存储空间的利用率就太低了。

image-20230530220548566

若一个顺序文件有10000个记录，则根据关键字检索文件，只能从头开始顺序查找（这里指的并不是定长记录、顺序结构的顺序文件）,平均须查找5000个记录。

若采用索引顺序文件结构，可把10000个记录分为V10000=100组，每组100个记录。则需要先顺序查找索引表找到分组（共100个分组，因此索引表长度为100,平均需要查50次）,找到分组后，再在分组中顺序查找记录（每个分组100个记录，因此平均需要查50次）。可见，采用索引顺序文件结构后，平均查找次数减少为50+50=100次。同理，若文件共有106个记录，则可分为1000个分组，每个分组1000个记录。根据关键字检索一个记录平均需要查找500+500=1000次。

这个查找次数依然很多，如何解决呢？

多级索引顺序文件

为了进一步提高检索效率，可以为顺序文件建立多级索引表。例如，对于一个含106个记录的文件，可先为该文件建立一张低级索引表，每100个记录为一组，故低级索引表中共有10000个表项（即10000个定长记录）,再把这10000个定长记录分组，每组100个，为其建立顶级索引表，故顶级索引表中共有100个表项。

image-20230530220722634

知识回顾与重要考点

image-20230530220744310

image-20230530220800261

文件目录

知识总览

image-20230530220906409

文件控制块

image-20230530220938747

image-20230530221012343

FCB的有序集合称为“文件目录”，一个FCB就是一个文件目录项。FCB中包含了文件的基本信息（文件名、物理地址、逻辑结构、物理结构等）,存取控制信息（是否可读/可写、禁止访问的用户名单等）,使用信息（如文件的建立时间、修改时间等）。最重要，最基本的还是文件名、文件存放的物理地址。

FCB 实现了 文件名和 文件之间的映射。使用户（用户程序）可以实现 按名存取

需要对目录进行哪些操作？

  • 搜索：当用户要使用一个文件时，系统要根据文件名搜索目录，找到该文件对应的目录项
  • 创建文件：创建一个新文件时，需要在其所属的目录中增加一个目录项
  • 删除文件：当删除一个文件时，需要在目录中删除相应的目录项
  • 显示目录：用户可以请求显示目录的内容，如显示该目录中的所有文件及相应属性
  • 修改目录：某些文件属性保存在目录中，因此这些属性变化时需要修改相应的目录项（如：文件重命名）

目录结构

单级目录结构

早期操作系统并不支持多级目录，整个系统中只建立一张目录表，每个文件占一个目录项

image-20230530221312503

单极目录 实现了 按名存取，但是 不允许文件重名

在创建一个文件时，需要先检查目录表中有没有重名文件，确认没有之后才允许 创建文件，并将新文件对应的目录项插入目录表中

显然，单级目录结构不适用与多用户操作系统

两级目录结构

早期的多用户操作系统，采用 两级目录结构。分为 主文件目录（MFD，Master File Directiory) 和 用户文件目录（UFD，User File Directory）

image-20230530221657398

多级目录结构

又称 树形目录结构

image-20230530221732834

用户（或用户进程）要访问某个文件时要用文件路径名标识文件，文件路径名是个字符串。各级目录之间用“/”隔开。从根目录出发的路径称为绝对路径。例如：自拍.jpg的绝对路径是“/照片/2015-08/自拍.jpg”

系统根据绝对路径一层一层地找到下一级目录。刚开始从外存读入根目录的目录表；找到“照片”目录的存放位置后，从外存读入对应的目录表；再找到“2015-08”目录的存放位置，再从外存读入对应目录表；最后才找到文件“自拍.jpg”的存放位置。整个过程需要3次读磁盘I/O操作。很多时候，用户会连续访问同一目录内的多个文件（比如：接连查看“2015-08”目录内的多个照片文件）,显然，每次都从根目录开始查找，是很低效的。

因此可以设置一个“当前目录”。

例如，此时已经打开了“照片”的目录文件，也就是说，这张目录表已调入内存，那么可以把它设置为“当前目录”。当用户想要访问某个文件时，可以使用从当前目录出发的“相对路径”。

在Linux中，“.”表示当前目录，因此如果“照片”是当前目录，则”自拍.jpg”的相对路径为：“./2015-08/自拍.jpg”。从当前路径出发，只需要查询内存中的“照片”目录表，即可知道”2015-08”目录表的存放位置，从外存调入该目录，即可知道“自拍.jpg”存放的位置了。可见，引入“当前目录”和“相对路径”后，磁盘1/0的次数减少了。这就提升了访问文件的效率。

树形目录结构 可以很方便对文件进行分类，层次清晰，也能够更有效地进行文件的管理和保护。但是，树形结构 不便于实现文件的共享。为此，提出了 无环图目录结构

无环图目录结构

image-20230530222142597

可以用不同的文件名 指向同一个文件，甚至可以指向同一个记录（共享同一目录下的所有内容）

需要为 每个共享节点设置一个共享计数器，用于记录此时有多少个地方在共享该节点，用户提出删除结点的请求时，只是删除该用户的 FCB，并使 计数器 减1 ，并不会直接删除共享节点

只有共享计数器减为0 的时候，才删除节点

注意：共享文件不同于 复制文件。 在 共享文件中，由于各用户指向的是同一个文件，因此只要其中一个用户修改了数据，那么所有的用户都可以看到该文件 的变化

索引结点（FCB 的改进）

image-20230530222619853

当找到文件名对应的目录项时，才需要将索引结点调入内存，索引结点中记录了文件的各种信息，包括文件在外存中的存放位置，根据“存放位置”即可找到文件。

存放在外存中的索引结点称为“磁盘索引结点”，当索引结点放入内存后称为“内存索引结点”。相比之下内存索引结点中需要增加一些信息，比如：文件是否被修改、此时有几个进程正在访问该文件等。

知识回顾与重要考点

image-20230530222756495

文件的物理结构 （文件的分配方式）

知识总览

image-20230530225515287image-20230530225531098

文件块、磁盘块

image-20230530225558242 image-20230530225630062

在内存管理中，进程的逻辑地址被分为一个一个页面

同样的，在外存管理中，为了方便对文件数据的管理， 文件的逻辑地址空间也被分为了一个一个 的文件 “块”

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

文件分配方式

连续分配
image-20230530225931924

连续分配 方式 要求 每个文件在磁盘上占有一组连续的块

连续分配方式 支持顺序访问和直接访问（即 随机访问）

image-20230530230045520

连续分配的文件 在 顺序读写 时 速度最快

image-20230530230118344

连续分配的文件不方便扩展

image-20230530230150841

连续分配的存储空间利用率低，会产生难以利用的磁盘碎片

总结

连续分配 方式要求 每个文件在磁盘上占有一组连续的块

  • 优点：支持顺序访问和直接访问（即 随机访问)； 连续分配在 顺序访问时速度最快
  • 缺点：不方便文件扩展；存储利用率低，会产生磁盘碎片
链接分配

链接分配 采用离散分配的方式，可以为文件分配离散的磁盘块。 分为 隐式链接 和 显式链接

隐式链接
image-20230530230753826 image-20230530230809221

采用 隐式链接分配， 很方便 扩展。 所有空闲的磁盘块都可以被利用， 不会有碎片问题，外存利用率高

隐式链接 —— 除文件的 最后一个盘块之外，每个盘块中都存有指向下一个盘块的指针。文件目录包括文件第一块的指针 和 最后一块的指针

  • 优点：很方便 文件扩展，不会有碎片问题，外存利用率高
  • 缺点：只支持顺序访问，不支持随机访问，查找效率低，指向下一个盘块的指针需要少量的存储空间
显式链接

把用于链接文件 各物理块的指针显式的存放在一张表中。即 文件分配表（FAT，File Allocation Table)

image-20230530231307533 image-20230530231326484

结论：采用链式分配（显式链接）方式的文件，支持顺序访问，也支持随机访问（想访问i号逻辑块时，并不需要依次访问之前的0~i-1号逻辑块）,由于块号转换的过程不需要访问磁盘，因此相比于隐式链接来说，访问速度快很多。

显然，显式链接也不会产生外部碎片，也可以很方便地对文件进行拓展。

总结

image-20230530231633629

索引分配

索引分配 允许文件离散地分配在 各个磁盘块中，系统会为 每个文件建立一张索引表，索引表中 记录了文件的各个逻辑块对应的物理块（索引表的功能类似内存管理中的页表 —— 建立 逻辑页面到物理页面之间的映射）。索引表存放的磁盘 成为 索引块。文件数据存放的 磁盘块 称为 **数据块 **

image-20230530232002912

如何实现文件逻辑块号到物理块号的转换

用户给出要访问的逻辑块号i,操作系统找到该文件对应的目录项（FCB)…从目录项中可知索引表存放位置，将索引表从外存读入内存，并查找索引表即可只i号逻辑块在外存中的存放位置。

可见，索引分配方式可以支持随机访问。文件拓展也很容易实现（只需要给文件分配一个空闲块，并增加一个索引表项即可）但是索引表需要占用一定的存储空间

image-20230530232200835
链接方案

链接方案： 如果索引表太大，一个索引模块装不下，那么可以将多个索引块连接起来存放

image-20230530232341345
多层索引

多层索引： 建立多层索引（原理类似 多层页表）。使第一层索引块指向第二层的索引块。还可根据文件的大小再建立 第三层、第四层

image-20230530232528099

若采用多层索引，则 各层索引表大小不能超过一个磁盘块

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

混合索引

混合索引： 多种索引分配方式的结合。例如一个文件的顶级索引表中，既包含 直接地址索引（直接指向数据块），又包含一级间接索引（指向单层索引表），还包括 两级间接索引（指向两级索引表）

image-20230530232908275

总结

image-20230530232929480

知识回顾与重要考点

image-20230530233305030

易混考点

image-20230530233419799

逻辑结构 vs 物理结构

image-20230530233552927

文件的基本操作

知识总览

image-20230530233618197

创建文件

image-20230530233646252

删除文件

image-20230530233704793

打开文件

image-20230530233731172

image-20230530233831840

关闭文件

打开计数器： 记录此时有多少个进程打开 此文件

image-20230530233851211

读文件

image-20230530233928460

写文件

image-20230530233947356

知识回顾与重要考点

image-20230530234008913

文件存储管理

知识总览

image-20230530234407526image-20230530234421209

存储空间的划分与初始化

image-20230530234453591

存储空间管理

空闲表法

适用于 连续分配方式

image-20230530234534758

  • 如何分配磁盘块：与内存管理中的动态分区分配很类似，为一个文件分配连续的存储空间。同样可采用 首次适应、最佳适应、最坏适应等算法来决定要为文件分配哪个区间。
  • 如何回收磁盘块：与内存管理中的动态分区分配很类似，当回收某个存储区时需要有四种情况
    1. 回收区的前后都没有相邻空闲区；
    2. 回收区的前后都是空闲区；
    3. 回收区前面是空闲区；
    4. 回收区后面是空闲区。总之，回收时需要注意表项的合并问题。
空闲链表法

image-20230530234729787

空闲盘块链
image-20230530234844194
空闲盘区链
image-20230530234905013
位示图法
image-20230530234953946

位示图法是一种常用的文件管理方式，主要用于表示磁盘上每个块的使用情况。在位示图法中，操作系统使用一个位示图（BitMap）来记录磁盘上每个块的使用情况，其中每一位表示一个块的使用状态，1表示已经被占用，0表示未被占用。

位示图法的优点是简单、快速，使用类似于二进制的位运算操作，同时可以快速地判断一个块是否被占用，提高了系统的性能。同时，位示图法还可以有效地避免外部碎片的问题，提高了系统的可靠性和稳定性。缺点是需要占用一定的磁盘空间存储位示图，当磁盘空间较大时，位示图的大小也会相应增加。

在实际应用中，位示图法通常与其他文件管理技术相结合使用，如文件分配表（FAT）、索引节点（Inode）等。同时，还需要注意位示图对系统的性能和可靠性的影响，如位示图的大小和操作系统对位示图的管理等问题。如果位示图管理不当，可能会导致位示图损坏、空间浪费、碎片问题等一系列问题，影响系统的性能和稳定性

image-20230530235115083

成组链接法

空闲表法、空闲链表法 不适用于大型文件，因为空闲表或者 空闲链表可能过大。 UNIX 系统使用了 成组链接法 对磁盘空闲块进行管理

文件卷的目录区 专门用一个 磁盘块 作为 超级块，当系统启动时需要将 超级块读入内存。并且要保证 内存与外存 中的 超级块的数据要一致

image-20230530235359863 image-20230530235421202

如何分配

image-20230530235450289

如何回收

image-20230530235528078

知识回顾与重要考点

image-20230530235616451

文件共享

知识总览

image-20230531160911803

注意：多个用户共享同一个文件，意味着系统中只有“一份”文件数据。并且只要某个用户修改了该文件的数据，其他用户也可以看到文件数据的变化。如果是多个用户都“复制”了同一个文件，那么系统中会有“好几份”文件数据。其中一个用户修改了自己的那份文件数据，对其他用户的文件数据并没有影响。

基于索引节点的共享方式

硬链接

索引结点：是一种文件目录瘦身策略。由于 检索文件只需要用到 文件名，因此可以将 文件名之外的其他信息 放到索引结点中。这样目录项就只需要包含文件名、索引结点 指针image-20230531161119210

索引结点中设置一个链接计数变量count,用于表示链接到本索引结点上的用户目录项数。

  • 若count=2,说明此时有两个用户目录项链接到该索引结点上，或者说是有两个用户在共享此文件。若某个用户决定“删除”该文件，则只是要把用户目录中与该文件对应的目录项删除，且索引结点的count值减1。
  • 若count>0,说明还有别的用户要使用该文件，暂时不能把文件数据删除，否则会导致指针悬空。
  • 当count=0时系统负责删除文件。
软链接
image-20230531161223321

快捷方式

知识回顾

image-20230531161302679

文件保护

知识回顾

image-20230531161344600

口令保护

为文件设置一个口令，用户访问时 必须提供口令

  • 优点：保存口令的空间开销不大，验证口令的时间开销也很小
  • 缺点 ：正确的 “口令” 存放在 系统内部，不够安全

加密保护

使用某个密码 对文件进行 加密，在访问时需要 提供正确的 密码 才能对文件进行正确的 解密

image-20230531161601073

  • 优点：保密性强，不需要在系统中 存储 密码
  • 缺点：编码、译码，或者说 加密 解密 需要一定时间

访问控制

在每个文件的 FCB （或索引结点） 中 增加一个 访问控制表 （Access-Control List ACL），该表记录了各个用户可以对该文件执行哪些操作

image-20230531161808157

image-20230531161830131

知识回顾与重要考点

image-20230531161859099

文件系统的层次结构

知识总览

image-20230531162028298

文件系统的层次结构

image-20230531162112002

知识回顾与重要考点

用一个例子来辅助记忆文件系统的层次结构：假设某用户请求删除文件“D:/工作目录/学生信息.xlsx”的最后100条记录。

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

磁盘的结构

知识总览

image-20230531162247029

磁盘、磁道、扇区

image-20230531162322582

如何在磁盘中读写数据

image-20230531162423511

盘面、柱面

image-20230531162444591

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

磁盘的物理地址

image-20230531162555675

磁盘的分类

image-20230531162622662 image-20230531162636693

知识回顾与重要考点

image-20230531162703776

磁盘调度算法

知识总览

image-20230531162744475

一次磁盘读写需要的时间

image-20230531162812741image-20230531162834246

image-20230531162847855

延迟时间和传输时间都与磁盘转速相关，且为线性相关。而转速是硬件的固有属性，因此操作系统也无法优化延迟时间和传输时间

先来先服务算法（FCFS

image-20230531162938543

最短寻找时间优先（SSTF）

image-20230531163008045

扫描算法（SCAN）

image-20230531163029213

LOOK 调度算法

image-20230531163044154

循环扫描算法

image-20230531163111582

C-LOOK 调度算法

image-20230531163137063

知识回顾与重要考点

image-20230531163155864

减少延迟时间的方法

前情回顾

image-20230531165240506

交替编号

image-20230531165300045

磁盘地址结构的设计

image-20230531165338589

读取地址连续的磁盘块时，采用（柱面号，盘面号，扇区号） 的地址结构可以减少磁头移动消耗的时间

错位命名

image-20230531165504513

知识回顾与重要考点

image-20230531165522905

磁盘的管理

知识总览

image-20230531165545259

磁盘的初始化

image-20230531165600185

引导块

计算机开机时 需要进行一系列初始化的工作，这些初始化工作是通过执行 初始化程序（自举程序） 完成的

自举程序 放在 ROM 中存在什么问题： 万一需要更新自举程序，将会很不方便，因为 ROM 中的数据无法更改

初始化程序可以放在 ROM 中，ROM 中的数据在出厂时就写入了，并且不能 更改

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

image-20230531170002486

坏块的管理

坏了、无法正常使用的扇区就是“坏块”。这属于硬件故障，操作系统是无法修复的。应该将坏块记出来，以免错误地使用到它

对于简单的磁盘，可以在逻辑格式化时（建立文件系统时）对整个磁盘进行坏块检查，标明哪些扇区是坏扇区，比如：在FAT表上标明。（在这种方式中，坏块对操作系统不透明）

对于复杂的磁盘，磁盘控制器（磁盘设备内部的一个硬件部件）会维护一个坏块链表。在磁盘出厂前进行低级格式化（物理格式化）时就将坏块链进行初始化。会保留一些“备用扇区”，用于替换坏块。这种方案称为扇区备用。且这种处理方式中，坏块对操作系统透明。

知识回顾与重要考点

image-20230531170123650

I/O

I/O是指输入/输出，它是计算机系统中的一个重要组成部分。在计算机系统中，I/O是指将数据从输入设备（如键盘、鼠标、磁盘等）输入到计算机中，或将计算机处理的数据输出到输出设备（如显示器、打印机、磁盘等）上的过程。

I/O的实现需要涉及到硬件、驱动程序和操作系统等方面的问题。在硬件方面，计算机系统需要提供相应的输入/输出设备，并通过总线、控制器等部件与计算机系统进行连接。在驱动程序方面，计算机系统需要提供相应的驱动程序，以便操作系统可以与输入/输出设备进行交互。而在操作系统方面，计算机系统需要提供相应的I/O管理机制，以实现对输入/输出设备的控制、调度和管理，并确保输入/输出操作的正确性和安全性。

在实际应用中，I/O的实现需要考虑到许多细节和技术，如缓存管理、中断处理、DMA传输、打印队列等问题。缓存管理是指操作系统需要对I/O数据进行缓存，以提高I/O操作的效率和性能。中断处理是指操作系统需要对I/O中断进行处理，以保证I/O操作的正确性和稳定性。DMA传输是指操作系统通过DMA控制器实现数据的直接内存访问，以提高I/O操作的效率和性能。打印队列是指操作系统需要对打印任务进行队列管理，以保证打印任务的顺序和正确性。

需要注意的是，在实际应用中，I/O的实现也需要考虑到不同的应用场景和需求，如高并发环境下的I/O、实时数据处理环境下的I/O、分布式环境下的I/O等问题。操作系统需要根据具体的需求和应用场景，选择合适的I/O策略和技术，以满足用户的需求和系统的性能要求。同时，还需要注意I/O操作对系统的安全性和稳定性的影响，避免因I/O访问控制不当、I/O传输错误等问题导致数据丢失、程序崩溃等问题。

I/O 设备的基本概念和分类

知识总览

image-20230531172348462

什么是 I/O 设备

I/O 就是 Input/Output 输入/输出

I/O 设备就是 可以将数据 输入到计算机，或者可以 接收计算机输出数据的外部设备，属于计算机的硬件设备

image-20230531172543154

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

  • write 操作：向外部设备写出数据
  • read 操作：从 外部设备写入数据

I/O 设备的分类 —— 按使用特性

image-20230531172807327

I/O 设备的分类 —— 按传输速率分类

image-20230531172840687

I/O 设备的分类 —— 按信息交换的单位分类

image-20230531172910167

知识回顾与重要考点

image-20230531172930788

I/O 控制器

知识总览

image-20230531173008193

I/O 设备

I/O设备的机械部件主要用来执行具体I/O操作。如我们看得见摸得着的鼠标/键盘的按钮；显示器的LED屏；移动硬盘的磁臂、磁盘盘面。

I/O设备的电子部件通常是一块插入主板扩充槽的印刷电路板。

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

CPU 无法直接 控制 I/O 设备的机械部件，因此 I/O 设备还要有一个电子部件作为 CPU 和 I/O 机械设备之间的 中介，实现 CPU 对于 设备的 控制

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

image-20230531173645828
I/O 控制器的组成
image-20230531173732888 image-20230531173751887

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

image-20230531173835532

知识回顾与重要考点

image-20230531174024378

I/O 控制方式

知识总览

image-20230531210245381

程序直接控制方式

image-20230531210312387

image-20230531210354428

中断驱动方式

image-20230531211114470image-20230531211135777

引入 中断机制。 由于 I/O 设备速度很慢，因此 在 CPU 发出 读写 命令后，可 将等待 I/O 的进程阻塞，先切换到 别的进程执行。当 I/O 完成后，控制器会想CPU 发出一个 中断信号，CPU 检测到中断信号后，会保存当前进程的运行环境信息，转去执行中断处理程序处理该中断。 处理中断的过程中，CPU 从 I/O 控制器读一个字的数据 传送到CPU 寄存器，再写入主存。接着， CPU 恢复等待 I/O 的进程（或 其他进程）的运行环境，然后继续执行

注意：

  1. CPU 会在每个指令周期的末尾检查中断
  2. 中断处理过程中 需要保存、恢复进程的 运行环境

这个过程是需要一定时间开销的。可见，如果中断发生的频率太高，也会降低系统性能

DMA 方式

与 中断驱动方式 相比，DMA （Direct Memory Access, 直接存储器存储)方式 。主要用于 块设备的的 I/O 设备控制。 有这样几个改动：

  1. 数据的传送单位是 块。不再是一个字、一个字的 传送
  2. 数据的流向是直接从 设备到 内存，或者从内存到设备。不再需要cpu 作为快递小哥
  3. 仅在 传送一个或多个数据块的开始和结束时，才需要 CPU 干预
image-20230531211724759 image-20230531211740243
  • DR： Data Register ，数据寄存器 ： 暂存 从设备到内存，或从 内存到设备的 数据
  • MAR： Memory Address Register ，内存地址寄存器 ： 在输入时，MAR 表示数据应该放到内存的什么位置；输出的时候， MAR 表示 要输出的数据放在内存的什么位置
  • DC： Data Counter，数据计数器 ：表示 剩余 要 读/写 的字节数
  • CR：Command Register，命令/状态 寄存器： 用于存放 CPU 发来的 I/O 指令，或 设备的 状态信息
image-20230531212112998

通道控制方式

通道： 一种硬件，可以理解为 弱鸡版的CPU，通道可以 识别并执行 一系列的通道指令

image-20230531212323285

与 CPU 相比，通道可以执行的指令很单一，并且通道程序是放在主机内存中的，也就是通道与 CPU 共享内存

image-20230531212450204

知识回顾与重要考点

image-20230531212516613

I/O 软件层次

知识总览

image-20230531214339534

用户层软件

image-20230531214621094

设备独立性软件

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

image-20230531214644010

主要实现的功能：

  1. 向上一层提供统一的调用接口
  2. 设备的保护
    • 原理与文件保护相似。设备被看做是一种特殊的文件，不同用户对各个文件的访问权限是不一样的，同理，对设备的访问权限也不一样
  3. 差错处理
    • 设备独立性软件需要对一些设备的错误进行 处理
  4. 设备的分配与回收
  5. 数据缓冲区管理
    • 可以通过缓冲技术 屏蔽设备之间数据交换单位大小和传输速度的差距
  6. 建立 逻辑设备名到 物理设备名的映射关系；根据设备类型选择调用 相应的驱动程序

image-20230531215341363

设备驱动程序

image-20230531215410702

中断处理程序

当 I/O 任务完成时，I/O 控制器会发送一个中断信号，系统根据 中断信号类型 找到 相应的 中断处理程序并执行。中断处理程序流程如下：

image-20230531215550328

知识回顾与重要考点

image-20230531215621224

image-20230531215652972

I/O 核心子系统

知识总览

image-20230531215728131

这些功能在哪里实现

image-20230531215849798

I/O 调度

image-20230531215903575

I/O 调度： 用某种算法确定一个好的顺序 来处理各个请求

如：磁盘调度（先来先服务算法、最短寻道优先算法、SCAN算法、C-SCAN算法、LOOK算法、C-LOOK算法）。当多个磁盘I/O请求到来时，用某种调度算法确定满足I/O请求的顺序。

同理，打印机等设备也可以用先来先服务算法、优先级算法、短作业优先等算法来确定1/0调度顺序。

设备保护

image-20230531220005379

操作系统 需要实现 文件保护功能，不同的用户对各个文件有不同的访问权限

在UNIX系统中，设备被看做是一种特殊的文件，每个设备也会有对应的FCB。当用户请求访问某个设备时，系统根据FCB中记录的信息来判断该用户是否有相应的访问权限，以此实现“设备保护”的功能。

知识总览

image-20230531220110251

假脱机技术（SPOOLing 技术）

知识总览

image-20230531220156966

什么是脱机技术

手工操作阶段：主机直接从1/0设备获得数据，由于设备速度慢，主机速度很快。人机速度矛盾明显，主机要浪费很多时间来等待设备

批处理阶段引入了 脱机输入、输出技术，引入脱机技术后，缓解了CPU与慢速1/0设备的速度矛盾。另一方面，即使CPU在忙碌，也可以提前将数据输入到磁带：即使慢速的输出设备正在忙碌，也可以提前将数据输出到磁带。

为什么称为 脱机 —— 脱离主机的控制进行的 输入 、输出

假脱机技术

输入井、输出井

假脱机技术 又称 SPOOLing 技术，是用软件的方式模拟脱机技术。SPOOLing 系统的组成如下

假脱机技术是指一种虚假的数据处理方式，即将数据从计算机系统中取出，进行离线处理，但实际上并没有真正离线处理。假脱机技术通常是指在计算机系统中使用一些缓存或内存等技术，以模拟离线处理的效果，从而提高系统的性能和效率。

在假脱机技术中，用户将待处理的数据通过输入设备输入到计算机系统中，并进行相应的处理操作。处理过程中，计算机系统将数据缓存到内存中，以模拟数据已经被取出进行离线处理的效果。处理完成后，计算机系统将处理结果输出到输出设备中，并将其返回给用户。

image-20230531220723634

输出进程、输入进程

image-20230531221028672image-20230531220807012

要实现 SPOOLing 技术，必须要有多道程序技术的支持。系统会建立 输入进程与 输出进程

输入、输出缓冲区

image-20230531221107226

共享打印机原理分析

  • 独占式设备 —— 只允许各个进程串行使用的设备。一段时间内只能满足一个进程的请求。
  • 共享设备 —— 允许多个进程“同时”使用的设备（宏观上同时使用，微观上可能是交替使用）。可以同时满足多个进程的使用请求。

image-20230531221151253

image-20230531221236541

虽然系统中只有一个台打印机，但每个进程提出打印请求时，系统都会为在输出井中为其分配一个存储区（相当于分配了一个逻辑设备）,使每个用户进程都觉得自己在独占一台打印机，从而实现对打印机的共享。SPOOLing技术可以把一台物理设备虚拟成逻辑上的多台设备，可将独占式设备改造成共享设备。

知识回顾与重要考点

image-20230531221310544

设备的分配与回收

知识回顾

image-20230531221504942

设备分配时应考虑的因素

image-20230531221524413

设备的固有属性可分为三种：独占设备、共享设备、虚拟设备。

  • 独占设备 —— 一个时段只能分配给一个进程（如打印机）
  • 共享设备 —— 可同时分配给多个进程使用（如磁盘）,各进程往往是宏观上同时共享使用设备，而微观上交替使用。
  • 虚拟设备 —— 采用SPOOLing技术将独占设备改造成虚拟的共享设备，可同时分配给多个进程使用（如采用SPOOLing技术实现的共享打印机）

设备的分配算法：

  • FCFS
  • 优先级高者优先
  • 短任务优先
  • … …

从进程运行的安全性上考虑，设备分配有两种方式

  • 安全分配方式 ：为进程分配一个设备后就将进程阻塞，本次I/O 完成后 才将进程唤醒

    一个时段内只能 使用一个设备

    • 优点：破坏了 保持和请求 条件，不会死锁
    • 缺点：对于一个进程来说，CPU 和 I/O 只能串行工作

  • 不安全分配方式：进程发出 I/O 请求后，系统为其分配 I/O 设备，进程可继续执行，之后还可以发出新的 I/O 请求。只有某个 I/O 请求得不到 满足时 才会被阻塞

    一个进程可以同时使用多个设备

    • 优点： 进程的计算任务 和 I/O 可以并行处理，使进程迅速推进
    • 缺点：有可能发生死锁（死锁避免、死锁的检测与解除）

静态分配与动态分配

  • 静态分配： 进程运行前 为其分配 全部所需资源，运行结束后 归还资源

    破坏了 请求保持条件，不会发生死锁

  • 动态分配：进程运行过程中动态申请设备资源

设备管理中的数据结构

image-20230531222307784

设备控制表（DCT）：系统为每个设备配置一张 DCT，用于记录设备的情况

image-20230531222402598

进程管理中 曾提到 系统会根据阻塞原因的不同，将 进程 PCB 挂到不同的阻塞队中

控制器控制表（COCT）： 每个设备控制器对应一张 COCT。操作系统 根据 COCT 的信息进行操作和管理

image-20230531222816887

通道控制表（CHCT）：每个通道都会对应一张 CHCT。操作系统根据 CHCT 的信息对 通道 进行操作和管理

image-20230531222923174

系统设备表（SDT）： 记录了 系统中全部设备 的情况，每个设备对应一个 表目

image-20230531223010638

设备分配的步骤

  1. 根据进程请求 的 物理设备名 查找 SDT

    image-20230531223107663

  2. 根据SDT 找到 DCT，若 设备忙碌 则将 进程挂到 设备等待队列中，不忙碌则分配

    image-20230531223202534

  3. 根据 DCT 找到 COCT，若 控制器忙碌，则将进程挂到 控制器等待队列中，不忙碌则分配

    image-20230531223308447

  4. 根据 COCT 找到 CHCT，若 通道忙碌，则将进程挂到 **通道等待队列 **中，不忙则分配

    image-20230531223402998

只有 设备、控制器、通道 三者都分配成功时，这次设备分配 才算成功，之后便可以启动I/O 设备 进行数据传送

改进
image-20230531223523408 image-20230531223541681

逻辑设备表（LUT)建立了逻辑设备名与物理设备名之间的映射关系。

某用户进程第一次使用设备时使用逻辑设备名向操作系统发出请求，操作系统根据用户进程指定的设备类型（逻辑设备名）查找系统设备表，找到一个空闲设备分配给进程，并在LUT中增加相应表项。

如果之后用户进程再次通过相同的逻辑设备名请求使用设备，则操作系统通过LUT表即可知道用户进程实际要使用的是哪个物理设备了，并且也能知道该设备的驱动程序入口地址。

逻辑设备表的设置问题：

  • 整个系统只有一张LUT: 各用户所用的逻辑设备名不允许重复，适用于单用户操作系统
  • 每个用户一张LUT: 不同用户的逻辑设备名可重复，适用于多用户操作系统

知识总览

image-20230531223713100

缓冲区管理

知识总览

image-20230531223755044

什么是缓冲区、有什么作用

缓冲区是一个存储区域，可以由专门的硬件寄存器组成，也可利用内存作为缓冲区。

使用硬件作为缓冲区的成本较高，容量也较小，一般仅用在对速度要求非常高的场合（如存储器管理中所用的联想寄存器，由于对页表的访问频率极高，因此使用速度很快的联想寄存器来存放页表项的副本）

一般情况下，更多的是利用内存作为缓冲区，“设备独立性软件”的缓冲区管理就是要组织管理好这些缓冲区

image-20230531223910796

单缓冲

假设某用户进程请求某种块设备读入若干块的数据。若采用单缓冲的策略，操作系统会在主存中为其分配一个缓冲区（若题目中没有特别说明，一个缓冲区的大小就是一个块）。

注意：当缓冲区数据非空时，不能往缓冲区冲入数据，只能从缓冲区把数据传出；当缓冲区为空时，可以往缓冲区冲入数据，但必须把缓冲区充满以后，才能从缓冲区把数据传出。

image-20230531224024941

image-20230531224038619

image-20230531224101368

image-20230531224121204

双缓冲

假设某用户进程请求某种块设备读入若干块的数据。若采用双缓冲的策略，操作系统会在主存中为其分配两个缓冲区（若题目中没有特别说明，一个缓冲区的大小就是一个块）

双缓冲题目中，假设初始状态为：工作区空，其中一个缓冲区满，另一个缓冲区空假设T>C+M

image-20230531224213419

image-20230531224234418

结论：采用双缓冲策略，处理一个数据块的平均耗时为Max(T,C+M)

使用 单、双 缓冲在通信时的区别

两台机器之间通信时，可以配置缓冲区用于 数据的发送与接收

image-20230531224343156

显然，若两个相互通信的机器只设置单缓冲区，在任一时刻只能实现数据的单向传输。

image-20230531224427180

若两个相互通信的机器设置双缓冲区，则同一时刻可以实现双向的数据传输。

注：管道通信中的“管道”其实就是缓冲区。要实现数据的双向传输，必须设置两个管道

循环缓冲区

将多个大小相等的 缓冲区 链接为 一个 循环队列

image-20230531224522895

橙满，绿空

缓冲池

缓冲池由系统中共用的缓冲区组成。这些缓冲区按使用状况可以分为：空缓冲队列、装满输入数据的缓冲队列（输入队列）、装满输出数据的缓冲队列（输出队列）。

另外，根据一个缓冲区在实际运算中扮演的功能不同，又设置了四种工作缓冲区：用于收容输入数据的工作缓冲区（hin)、用于提取输入数据的工作缓冲区（sin)、用于收容输出数据的工作缓冲区（hout)、用于提取输出数据的工作缓冲区（sout)

image-20230531224823270

知识回顾与重要考点

image-20230531224845916

  • Title: 操作系统
  • Author: cccs7
  • Created at: 2023-01-04 17:02:22
  • Updated at: 2023-06-29 23:11:40
  • Link: https://blog.cccs7.icu/2023/01/04/操作系统/
  • License: This work is licensed under CC BY-NC-SA 4.0.
 Comments
On this page
操作系统
  1. 计算机系统概述
    1. 操作系统的概念、功能和目标
      1. 操作系统的概念
      2. 功能和目标
        1. 向上层提供方便易用的服务
          1. GUI
          2. 联机命令接口
          3. 脱机命令接口
          4. 程序接口
          5. 总结
        2. 作为最接近硬件的层次
      3. 知识回顾与重要考点
    2. 操作系统的特征
      1. 并发 与 并行
      2. 共享
        1. 并发和共享的关系
      3. 虚拟
      4. 异步
      5. 知识回顾与重要考点
    3. 操作系统的发展和分类
      1. 手工操控阶段
      2. 批处理阶段
        1. 单道批处理系统
        2. 多道批处理系统
      3. 分时操作系统
      4. 实时操作系统
      5. 其他几种操作系统
        1. 网络操作系统
        2. 分布式操作系统
        3. 个人计算机操作系统
      6. 知识回顾与重要考点
    4. 操作系统的运行机制
      1. 程序是如何运行起来的
      2. 内核程序 Vs 应用程序
      3. 内核态与用户态
        1. 内核态、用户态的切换
      4. 知识回顾与重要考点
        1. 两种指令、两种处理器状态、两种程序
        2. 操作系统内核
        3. 操作系统的体系结构
        4. 知识回顾与重要考点
    5. 中断和异常
      1. 中断的作用
      2. 中断的类型
        1. 内中断
        2. 外中断
      3. 中断机制的基本原理
      4. 知识回顾与重要考点
    6. 系统调用
      1. 什么是系统调用
      2. 系统调用和库函数的区别
      3. 为什么系统调用是必须的
      4. 什么功能要用到 系统调用
      5. 系统调用的过程
      6. 知识回顾与重要考点
    7. 操作系统的体系架构
      1. 操作系统的内核
      2. 知识回顾与重要考点
    8. 知识回顾
  2. 进程管理
    1. 进程与线程
      1. 进程的概念、组成、特征
        1. 进程的概念
        2. 进程的组成
          1. 进程的组成 ： PCB
          2. 进程的组成：程序段、数据段
        3. 进程的特征
        4. 知识回顾与重要考点
        5. 进程的组织
          1. 进程的组织：链接方式
          2. 进程的组织：索引方式
    2. 进程的状态与切换
      1. 进程的状态
        1. 创建态、就绪态
        2. 运行态
        3. 阻塞态
        4. 终止态
      2. 进程的切换
      3. 知识回顾与重要考点
    3. 进程控制
      1. 进程控制的概念
        1. 什么是 进程控制
        2. 如何实现进程控制
          1. 如何实现 原语的 “原子性”
      2. 进程控制相关的原语
        1. 进程的创建
        2. 进程的终止
        3. 进程的阻塞与唤醒
        4. 进程的切换
      3. 知识回顾与重要考点
    4. 进程通信
      1. 什么是进程通信
      2. 进程通信：共享存储
      3. 进程通信：管道通信
      4. 进程通信：消息传递
      5. 知识回顾与重要考点
    5. 线程、多线程模型
      1. 什么是线程
      2. 引入线程后的变化
      3. 线程的属性
      4. 线程的实现方式
        1. 用户级线程
        2. 内核级线程
      5. 多线程模型
        1. 一对一模型
        2. 多对一模型
        3. 多对多模型
      6. 知识回顾与重要考点
    6. 处理机调度
      1. 调度的概念、层次
        1. 调度的三个层次
          1. 高级调度
          2. 低级调度
          3. 中级调度
          4. 三层调度的对比与联系
        2. 知识回顾与重要考点
      2. 进程调度的时机、切换与过程、调度方式
        1. 进程调度的时机
        2. 进程调度的方式
        3. 进程 的切换与过程
        4. 知识回顾与重要考点
      3. 调度算法的评价指标
        1. CPU 利用率
        2. 系统吞吐量
        3. 周转时间
        4. 等待时间
        5. 响应时间
        6. 知识回顾与重要考点
      4. 调度算法（上）
        1. 先来先服务（FCFS）
        2. 短作业优先（ SJF，Shortest Job First)
        3. 高响应比优先（HRRN，Highest Response Ratio Next）
        4. 知识回顾与重要考点
      5. 调度算法（下）
        1. 时间片轮转（RR，Round-Robin)
        2. 优先级调度算法
        3. 多级反馈队列调度算法
        4. 知识回顾与重要考点
    7. 进程同步、互斥
      1. 什么是进程同步、互斥
        1. 什么是进程同步
        2. 什么是进程互斥
        3. 知识回顾与重要考点
      2. 进程互斥的软件实现方法
        1. 如果没有注意到进程互斥
        2. 单标志法
        3. 双标志先检查法
        4. 双标志后检查法
        5. Peterson 算法
        6. 知识回顾与重要考点
      3. 进程互斥的硬件实现方法
        1. 中断屏蔽方法
        2. TestAndSet 指令
        3. Swap 指令
        4. 知识回顾与重要考点
      4. 信号量机制
        1. 整形信号量
        2. 记录型信号量
        3. 知识回顾与重要考点
      5. 用信号量机制实现 进程互斥、同步、前驱
        1. 信号量机制实现 进程互斥
        2. 信号量机制实现进程同步
        3. 信号量机制实现 前驱关系
        4. 知识回顾与重要考点
      6. 生产者消费者问题
        1. 问题描述
        2. 问题分析
        3. 知识回顾与重要考点
      7. 多生产者-多消费者问题
        1. 问题描述
        2. 问题分析
        3. 知识回顾与重要考点
      8. 吸烟者问题
        1. 问题描述
        2. 问题分析
        3. 知识回顾与重要考点
      9. 读者-写者问题
        1. 问题描述
        2. 问题分析
        3. 实现
        4. 知识回顾与重要考点
      10. 哲学家进餐问题
        1. 问题描述
        2. 问题分析
        3. 实现
        4. 知识回顾与重要考点
      11. 管程
        1. 为什么引入管程
        2. 管程的定义和基本特征
        3. 知识回顾与重要考点
    8. 死锁
      1. 死锁的概念
        1. 什么是死锁
        2. 死锁、饥饿、死循环的区别
        3. 死锁的产生条件
        4. 什么时候会发生死锁
        5. 死锁的处理策略
        6. 知识回顾与重要考点
      2. 死锁的处理策略
        1. 预防死锁
          1. 破坏互斥条件
          2. 破坏不剥夺条件
          3. 破坏请求和保持条件
          4. 破坏循环等待条件
          5. 知识回顾与重要考点
        2. 避免死锁
          1. 什么是 安全序列
          2. 银行家算法
          3. 知识回顾与重要考点
        3. 检测和接触
          1. 死锁的检测
          2. 死锁的解除
          3. 知识回顾与重要考点
  3. 内存
    1. 内存的基础知识
      1. 什么是内存
        1. 绝对装入
        2. 可重定位装入
        3. 动态运行时装入
        4. 三种方式
        5. 知识回顾与重要考点
    2. 内存管理的概念
    3. 覆盖与交换
      1. 覆盖技术
      2. 交换技术
      3. 知识回顾与重要考点
    4. 连续分配管理方式
      1. 单一连续分配
      2. 固定分区分配
      3. 动态分区分配
      4. 动态分配算法
        1. 首次适应算法
        2. 最佳适应算法
        3. 最坏适应算法
        4. 邻近适应算法
        5. 知识回顾与重要考点
      5. 知识回顾与重要考点
    5. 基本分页存储管理的基本概念
      1. 什么是 地址空间
      2. 什么是分页存储
        1. 重要的数据结构 —— 页表
          1. 每个页表项占多少个字节
          2. 如何实现地址的转换
        2. 逻辑地址结构
      3. 知识回顾与重要考点
    6. 基本地址变换机构
      1. 知识回顾与重要考点
    7. 具有快表的地址变换机构
      1. 什么是快表
      2. 引入快表后，地址的变换过程
      3. 局部性原理
        1. 时间局部性
        2. 空间局部性
      4. 知识回顾与重要考点
    8. 两级页表
      1. 单页表存在的问题
        1. 如何解决
      2. 两级页表的原理、地址结构
      3. 如何实现地址变换
      4. 如何解决单机页表的问题
      5. 需要注意的问题
      6. 知识回顾与重要考点
    9. 基本分段存储管理方式
      1. 分段
      2. 段表
      3. 地址变换
      4. 分段、分页管理的对比
      5. 知识回顾与重要考点
    10. 段页式管理方式
      1. 分页、分段的优缺点分析
      2. 分段 + 分页 = 段页式管理
      3. 段页式管理的逻辑地址
      4. 段表、页表
      5. 知识回顾与重要考点
    11. 虚拟内存
      1. 传统存储管理方式的特征、缺点
      2. 局部性定理
      3. 虚拟内存的定义与特征
        1. 定义
        2. 特征
      4. 如何实现虚拟内存技术
      5. 知识回顾与重要考点
    12. 请求分页管理方式
      1. 页表机制
      2. 缺页中断机构
      3. 地址变换机构
      4. 知识回顾与重要考点
    13. 页面置换算法
      1. 最佳置换算法
      2. 先进先出算法
      3. 最近最久未使用置换算法
      4. 时钟置换算法
      5. 改进型的时钟置换算法
      6. 知识回顾与重要考点
    14. 页面分配策略
      1. 页面分配
      2. 置换策略
      3. 何时调入页面
      4. 何处调入页面
      5. 抖动（颠簸）现象
      6. 工作集
      7. 知识回顾与重要考点
  4. 文件
    1. 初识文件管理
      1. 知识回顾与重要考点
    2. 文件的逻辑结构
      1. 无结构文件
      2. 有结构文件
        1. 顺序文件
        2. 索引文件
        3. 索引顺序文件
        4. 多级索引顺序文件
      3. 知识回顾与重要考点
    3. 文件目录
      1. 文件控制块
      2. 目录结构
        1. 单级目录结构
        2. 两级目录结构
        3. 多级目录结构
        4. 无环图目录结构
        5. 索引结点（FCB 的改进）
      3. 知识回顾与重要考点
    4. 文件的物理结构 （文件的分配方式）
      1. 文件块、磁盘块
      2. 文件分配方式
        1. 连续分配
          1. 总结
        2. 链接分配
          1. 隐式链接
          2. 显式链接
          3. 总结
        3. 索引分配
          1. 链接方案
          2. 多层索引
          3. 混合索引
          4. 总结
      3. 知识回顾与重要考点
      4. 易混考点
        1. 逻辑结构 vs 物理结构
    5. 文件的基本操作
      1. 创建文件
      2. 删除文件
      3. 打开文件
      4. 关闭文件
      5. 读文件
      6. 写文件
      7. 知识回顾与重要考点
    6. 文件存储管理
      1. 存储空间的划分与初始化
      2. 存储空间管理
        1. 空闲表法
        2. 空闲链表法
          1. 空闲盘块链
          2. 空闲盘区链
        3. 位示图法
        4. 成组链接法
      3. 知识回顾与重要考点
    7. 文件共享
      1. 基于索引节点的共享方式
        1. 硬链接
        2. 软链接
      2. 知识回顾
    8. 文件保护
      1. 口令保护
      2. 加密保护
      3. 访问控制
      4. 知识回顾与重要考点
    9. 文件系统的层次结构
      1. 文件系统的层次结构
      2. 知识回顾与重要考点
    10. 磁盘的结构
      1. 磁盘、磁道、扇区
      2. 如何在磁盘中读写数据
      3. 盘面、柱面
      4. 磁盘的物理地址
      5. 磁盘的分类
      6. 知识回顾与重要考点
    11. 磁盘调度算法
      1. 一次磁盘读写需要的时间
      2. 先来先服务算法（FCFS
      3. 最短寻找时间优先（SSTF）
      4. 扫描算法（SCAN）
      5. LOOK 调度算法
      6. 循环扫描算法
      7. C-LOOK 调度算法
      8. 知识回顾与重要考点
    12. 减少延迟时间的方法
      1. 交替编号
      2. 磁盘地址结构的设计
      3. 错位命名
      4. 知识回顾与重要考点
    13. 磁盘的管理
      1. 磁盘的初始化
        1. 引导块
      2. 坏块的管理
      3. 知识回顾与重要考点
  5. I/O
    1. I/O 设备的基本概念和分类
      1. 什么是 I/O 设备
      2. I/O 设备的分类 —— 按使用特性
      3. I/O 设备的分类 —— 按传输速率分类
      4. I/O 设备的分类 —— 按信息交换的单位分类
      5. 知识回顾与重要考点
    2. I/O 控制器
      1. I/O 设备
        1. I/O 设备的电子部件（I/O控制器）
          1. I/O 控制器的组成
      2. 内存映像 I/O vs 寄存器独立编址
      3. 知识回顾与重要考点
    3. I/O 控制方式
      1. 程序直接控制方式
      2. 中断驱动方式
      3. DMA 方式
      4. 通道控制方式
      5. 知识回顾与重要考点
    4. I/O 软件层次
      1. 用户层软件
      2. 设备独立性软件
      3. 设备驱动程序
      4. 中断处理程序
      5. 知识回顾与重要考点
    5. I/O 核心子系统
      1. 这些功能在哪里实现
      2. I/O 调度
      3. 设备保护
      4. 知识总览
      5. 假脱机技术（SPOOLing 技术）
      6. 什么是脱机技术
      7. 假脱机技术
        1. 输入井、输出井
        2. 输出进程、输入进程
        3. 输入、输出缓冲区
      8. 共享打印机原理分析
      9. 知识回顾与重要考点
    6. 设备的分配与回收
      1. 设备分配时应考虑的因素
      2. 静态分配与动态分配
      3. 设备管理中的数据结构
      4. 设备分配的步骤
        1. 改进
      5. 知识总览
    7. 缓冲区管理
      1. 什么是缓冲区、有什么作用
      2. 单缓冲
      3. 双缓冲
      4. 使用 单、双 缓冲在通信时的区别
      5. 循环缓冲区
      6. 缓冲池
      7. 知识回顾与重要考点