Operating System

Operating System

This is for test takers to quickly review Operating System. Credit to 《Operating System, 9th Edition》。操作系统的知识看起来非常得杂乱无章，需要重点关注任务调度算法，内存管理分配算法，以及地址变换机制。

催更｜辅导｜私塾兼职｜联系偷偷：LifeGoesOn_Rio

1. Introduction to Operating System

计算机系统可以划分为4个主要组件：

  1. 硬件(hardware)：指的是物理设备，包括计算机的处理器、内存、硬盘、输入输出设备等。硬件如中央处理单元(CPU)、内存(memory)、输入输出设备(I/O device)为系统提供基本的计算资源。

  2. 操作系统(Operating System)：软件层次上管理硬件资源并提供基本服务的平台，例如 Windows、Linux 等。

  3. 应用程序(application)：运行在操作系统之上的软件，提供具体的功能和服务，如浏览器、文字处理软件等。

  4. 用户(user)：使用计算机系统进行操作和执行任务的人员。

单处理器系统（Single-Processor System） 是指只有一个中央处理单元（CPU）的计算机系统。其特点如下：

  1. 核心数量：只有一个处理器核心，用于执行所有的指令和任务。
  2. 任务调度：通过时间分片等方法实现多任务操作，但实际上每个时刻只能执行一个任务。
  3. 适用场景：适合资源需求较低的应用场景，如传统的个人计算机和嵌入式系统。
  4. 优点：结构简单，成本较低，软件开发难度小。
  5. 缺点：处理能力有限，无法充分利用多核架构的优势。

多处理系统（multiprocessing system）(也称为并行系统（parallel system）) 是指拥有多个处理器（或多个核心）的计算机系统，允许多个任务同时运行。其特点如下：

  1. 核心数量：包含两个或更多处理器（或多核），每个核心可以独立执行任务。
  2. 任务并行：支持真正的并行计算，显著提高计算速度和效率。
  3. 架构类型：分为对称多处理（Symmetric MultiProcessing, SMP）和非对称多处理（Asymmetric MultiProcessing, AMP）：
    • SMP：所有处理器平等共享内存和任务。
    • AMP：不同处理器有专门的任务分工。
  4. 适用场景：高性能计算、服务器、多任务处理（如图像处理、机器学习等）。

多处理器系统的主要优点有：

  1. 增加吞吐量

    • 多处理器系统通过并行处理任务显著提高了整体计算吞吐量。
    • 多个处理器可以同时执行不同的任务，减少任务队列的等待时间，提高系统的运行效率。
    • 特别适用于计算密集型任务，如科学计算、数据处理和复杂的仿真。
    • 采用N个处理器的加速比不是N，而是小于N（考虑资源共享竞争）

  2. 规模经济

    • 多处理器系统通过共享内存、I/O设备等资源，降低了每个处理器独立配备资源的成本。
    • 随着处理器数量增加，系统性能可以线性甚至超线性提升，使整体成本效益更高。
    • 常见于需要扩展性强的大型系统，如云计算和服务器集群。

  3. 增加可靠性

    • 多处理器系统具备更高的容错能力，当一个处理器发生故障时，其他处理器可以接管任务，保证系统的连续运行。
    • 提供了冗余机制，使关键任务系统（如航空、医疗设备）在出现硬件问题时仍能保持稳定。比如10个处理器中的1个出了故障，剩下的9个会分担器故障处理器的那部分工作。
    • 通过任务分配策略，还可有效防止单点故障的影响。

操作系统（Operating System，OS）是计算机系统中最基础且最重要的软件，它负责管理硬件资源并为用户和应用程序提供接口。其主要功能和定义如下：

  1. 资源管理者 : 操作系统负责管理和分配计算机的硬件资源，包括CPU、内存、存储设备和外部设备，以确保各类任务高效运行。

  2. 用户与硬件之间的桥梁 : 操作系统提供用户与硬件交互的接口，使用户可以通过简单的命令或图形界面与计算机进行操作，而无需直接了解硬件的底层细节。

  3. 程序执行的控制中心 : 操作系统负责调度和协调应用程序的运行，提供多任务处理和资源分配功能，保证系统的稳定性和性能。

  4. 服务提供者 : 它为应用程序提供基本的服务，如文件管理、内存管理、进程调度和网络通信，简化了软件开发。

操作系统是计算机系统的核心，它连接硬件和用户，为软件运行提供支持，同时确保系统的高效性和可靠性。

中断机制是操作系统中一个关键的功能，用于处理异步事件和高效管理硬件资源。它使得计算机可以响应各种外部或内部事件，如硬件故障、输入输出操作的完成、定时器到期等。下面详细介绍中断机制的各个方面：

1.中断的基本概念： 中断（Interrupt）是指计算机在执行程序的过程中，由于某些突发事件（如硬件设备请求、异常情况等），使得CPU暂时中止当前正在执行的程序，转而去处理这些事件的过程。当中断事件处理完毕后，CPU再回到中断前的程序继续执行。

2.中断的分类：

  1. 硬件中断（Hardware Interrupt）：由外部硬件设备触发，如键盘按键、鼠标点击、网络数据包到达等。
  2. 软件中断（Software Interrupt）：由软件触发的中断，如系统调用、程序异常等。
  3. 定时器中断（Timer Interrupt）：由系统定时器触发，用于时间片轮转调度等操作。

3.中断处理过程： 中断处理过程一般包括以下几个步骤：

  1. 中断请求：外部设备或软件发出中断请求信号。
  2. 中断响应：CPU检查中断信号，并保存当前执行的上下文（如程序计数器、寄存器等）。
  3. 中断向量：根据中断类型，CPU查找中断向量表以获取相应的中断服务程序（Interrupt Service Routine，ISR）的入口地址。
  4. 执行中断服务程序：CPU跳转到ISR，执行相应的中断处理逻辑。
  5. 恢复上下文：中断处理完成后，CPU恢复先前保存的上下文，继续执行被中断的程序。

4.中断优先级：
在多种中断同时发生时，需要确定哪个中断优先处理。中断优先级机制用于决定中断处理的顺序。一般来说，硬件中断优先级较高，而软件中断优先级较低。中断控制器（Interrupt Controller）用于管理中断优先级。

5.中断屏蔽： 中断屏蔽是指在某些关键操作期间，暂时禁止某些中断的发生，以防止中断打断正在进行的重要操作。通常使用中断屏蔽寄存器来实现。屏蔽中断可以避免在执行关键代码段时被中断打断，但也需要注意不能长时间屏蔽，以免丢失重要的中断信号。

6.中断的优点:

  1. 响应及时：中断机制可以在事件发生时立即响应，提高系统的实时性。
  2. 资源高效利用：通过中断机制，可以在硬件设备准备好时才进行处理，而不需要轮询，节省CPU资源。
  3. 多任务处理：中断机制支持多任务并发处理，增强系统的灵活性和效率。

7.中断的缺点:

  1. 中断延迟：如果中断处理程序过多或过长，可能会导致系统响应延迟。
  2. 复杂性增加：中断机制需要维护中断向量表和中断控制器，增加了系统的复杂性。
  3. 上下文切换开销：每次中断处理都涉及上下文切换，带来一定的性能开销。

以下是一个简单的中断处理流程示例：假设这是一个简单的汇编代码，演示中断处理

ORG 100H
MOV AX, 0          ; 初始化AX寄存器

INTERRUPT_HANDLER:
PUSH AX            ; 保存AX寄存器
MOV AX, 1234H      ; 中断处理逻辑
POP AX             ; 恢复AX寄存器
IRET               ; 返回中断前的程序

MAIN:
MOV AX, 1
INT 0              ; 触发中断
MOV AX, 2
HLT                ; 停止程序

在这个示例中，当执行到 INT 0 指令时，会触发中断并调用 INTERRUPT_HANDLER 来处理中断。在中断处理程序中，保存了AX寄存器的值，并进行了简单的处理后恢复AX寄存器，然后返回到中断前的程序继续执行。通过中断机制，计算机系统可以高效处理各种异步事件，保证系统的稳定性和响应性。

轮询（Polling） 是一种通过主动检查设备或资源状态来判断是否需要处理某个事件的机制。操作系统或程序会周期性地访问设备或资源，以确定是否需要执行相关操作。

轮询的特点：

  1. 主动查询 : 系统不断循环检查设备或资源的状态，而不是等待设备主动通知。

  2. 简单易实现 : 轮询机制实现起来比较简单，通常只需要循环读取设备的状态寄存器即可。

  3. 低效 : 如果设备状态没有发生变化，CPU可能会浪费大量时间在无意义的查询上，无法高效利用资源。

轮询的工作流程：

  1. 系统通过读取设备状态寄存器获取设备当前状态。
  2. 如果发现设备准备好（例如I/O操作完成），则进行相应的处理。
  3. 如果设备未准备好，则继续轮询，直到设备状态发生变化。

轮询的缺点：

  • 资源浪费：占用CPU时间，即使设备未准备好也会不断查询。
  • 实时性差：对于需要快速响应的事件，轮询可能无法及时处理。
  • 不适合频繁事件：当事件发生较多时，轮询会影响系统整体性能。

轮询的优点：

  • 简单性：实现简单，不需要复杂的硬件支持。
  • 适用性：适合事件发生频率较低或硬件复杂度较低的场景。

轮询对比中断机制：

特性 轮询 中断
响应方式 主动查询设备状态 被动响应设备的中断信号
资源利用效率 较低，可能浪费CPU资源 高效，只在事件发生时占用资源
实现复杂度 简单，不需要硬件支持 复杂，需要硬件和软件配合
实时性 较差 较强

轮询虽然简单，但在现代操作系统中已逐渐被更高效的中断机制取代。

在操作系统中，“异常(exception)” 指的是一种特殊的事件或情况，它们会导致当前正在执行的程序或系统行为发生中断。这些异常可能来自于硬件或软件，通常需要操作系统进行处理，以确保系统的稳定性和安全性。

异常的分类：

  1. 硬件异常：由于硬件故障或特殊硬件条件引起，例如内存访问违规、除零错误等。
  2. 软件异常：由于软件执行过程中出现的非法操作或异常情况引起，例如非法指令、系统调用错误等。

异常处理过程：

  1. 检测异常：当异常发生时，硬件或操作系统检测到异常情况。
  2. 保存状态：当前处理器状态（例如寄存器值、程序计数器）被保存，以便后续恢复。
  3. 调用异常处理程序：操作系统根据异常类型，调用相应的异常处理程序（Exception Handler）。
  4. 处理异常：异常处理程序执行特定的操作，以处理或缓解异常情况。
  5. 恢复状态：异常处理完成后，恢复处理器状态并继续执行被中断的程序。

常见的异常类型：

  • 访问违例：试图访问未授权的内存区域。
  • 非法指令：执行了无效或未定义的指令。
  • 除零错误：在计算过程中出现除数为零的情况。
  • 系统调用：用户程序请求操作系统提供服务时产生的异常。

异常处理的优点：

  • 提高系统稳定性：通过有效的异常处理机制，操作系统可以检测并处理各种错误，避免系统崩溃。
  • 增强安全性：异常处理可以防止非法操作，保护系统和用户数据的安全。

异常处理是操作系统中的一个关键机制，用于管理和处理各种意外事件和错误情况。通过异常处理，操作系统能够保持系统的稳定性和安全性，确保用户和应用程序的正常运行。

在操作系统中，中断（Interrupt）和异常（Exception） 是两种重要的事件，它们都会导致CPU暂停当前的任务，转而去处理这些事件。再总结一下就是：

  • 中断（Interrupt）：中断是由硬件设备（如键盘，鼠标，网络接口卡等）发出的信号，通知操作系统有一些重要的事件发生，需要立即处理。例如，当你按下键盘上的一个键时，键盘会向CPU发送一个中断信号，CPU会暂停当前的任务，转而去处理这个按键事件。处理完这个事件后，CPU会返回到被中断的任务，继续执行。
  • 异常（Exception）：异常是由CPU在执行指令过程中发现的问题，如除以零，访问无效的内存地址等。当发生异常时，CPU会暂停当前的任务，转而去执行一个特殊的异常处理程序。处理完这个异常后，CPU可能会返回到被中断的任务，也可能会终止这个任务，这取决于异常的类型和严重性。

总体来说，中断和异常都是操作系统用来响应和处理重要事件的机制。它们都会导致CPU暂停当前的任务，但来源和处理方式有所不同。中断通常由外部硬件或定时器触发，表示系统需要对外部事件进行响应，而异常则由程序内部的特殊或错误行为引发，表示需要操作系统介入进行修复或处理。发生中断或异常时，操作系统都会介入并展开管理工作；用户态和内核态的切换是通过中断或异常实现的，而中断是实现这种切换的唯一途径，通过修改程序状态字（PSW）来完成状态转换。

内存管理 是操作系统的一项重要功能，负责管理计算机的主存储器，并为应用程序分配和释放内存。内存管理的主要目标是提高内存的使用效率，保证系统的稳定性和安全性。以下是内存管理的一些关键概念和机制：

内存管理的主要任务:

  1. 内存分配：为进程分配所需的内存资源，包括动态分配和静态分配。
  2. 内存保护：确保进程只能访问自己合法的内存区域，防止进程之间相互干扰。
  3. 内存回收：回收不再使用的内存，以便分配给其他进程。

内存管理机制:

1.分段和分页:

  • 分页：内存被划分成大小相同的页，每个进程的地址空间也被划分成相同大小的页。通过页表（Page Table）映射进程页和物理内存页，实现内存的管理。
  • 分段：内存被划分成不同大小的段，每个段包含一段逻辑地址空间。通过段表（Segment Table）管理和映射各段地址。

2.虚拟内存:

虚拟内存技术允许操作系统将实际物理内存与进程的逻辑内存分离，使得进程可以使用比实际物理内存更大的地址空间。虚拟内存通过页表和交换空间（Swap Space）管理，将不常用的页临时存储在磁盘上，需要时再调入内存。

3.内存保护:

  • 基址寄存器和界限寄存器：通过设置每个进程的基址和界限，确保进程只能访问自己的内存区域，防止越界访问。
  • 页面保护：通过页表中的保护位控制每个页的访问权限（读、写、执行），保证进程的内存访问安全。

4. 内存回收:

  • 垃圾回收：通过自动检测和回收不再使用的内存，释放资源供其他进程使用。
  • 内存压缩：通过内存整理和压缩，减少内存碎片，提高内存利用率。

内存管理的重要性:

  1. 提高系统性能：通过有效的内存分配和回收机制，保证进程的高效运行。
  2. 增强系统稳定性：通过内存保护机制，防止进程之间的相互干扰，保证系统的稳定运行。
  3. 优化资源利用：通过虚拟内存和分页技术，最大化内存资源的利用率，使得系统能够同时运行更多的进程。

内存管理是操作系统的一项核心功能，涉及内存的分配、保护和回收等多个方面。通过有效的内存管理，操作系统能够提高系统性能、增强稳定性，并优化资源利用，为应用程序提供稳定可靠的运行环境。

操作系统的进程管理是指对系统中所有进程的创建、调度、执行、和终止进行管理和协调的过程。它是操作系统的核心功能之一，负责保证多个任务能够高效、公平地共享CPU和其他资源。

进程管理的主要功能：

  1. 进程创建与终止

    • 创建新进程：为程序分配必要的资源（如内存、文件句柄）并初始化进程控制块（PCB）。
    • 终止进程：释放进程所占用的资源并清理PCB。

  2. 进程调度

    • 负责决定哪一个进程可以使用CPU。
    • 常用的调度算法包括：
      • 先来先服务（FCFS）
      • 最短作业优先（SJF）
      • 时间片轮转（RR）
      • 多级队列调度等。

  3. 进程同步

    • 保证多个进程在访问共享资源时不会产生冲突。
    • 使用机制：信号量（Semaphore）、互斥锁（Mutex）、条件变量等。

  4. 进程通信

    • 提供进程之间交换数据的手段。
    • 常用方式：管道（Pipe）、消息队列（Message Queue）、共享内存（Shared Memory）、信号（Signal）等。

  5. 进程状态管理

    • 维护进程的状态：
      • 新建（New）
      • 就绪（Ready）
      • 运行（Running）
      • 阻塞（Blocked）
      • 终止（Terminated）
    • 根据状态变化完成任务切换。

  6. 多线程支持

    • 管理线程的创建、调度和同步，支持多线程模型（如用户线程和内核线程）。

进程与线程的区别

  • 进程(Process) 是资源分配的最小单位，每个进程有独立的地址空间。进程的实质是程序在多道程序系统中的一次执行过程，进程是动态产生，动态消亡的。
  • 线程(Thread) 是CPU调度的最小单位，线程共享进程的地址空间。线程是进程中的一条执行路径，是进程的一个实体，可作为系统独立调度和分派的基本单位。

进程：就像一家物业管理公司，它独立运营，有自己的一套管理系统（相当于进程的独立地址空间）。这个公司可以接多个任务，但所有任务最终都需要公司的资源来完成。

单线程：假设你是这家公司的唯一员工。初期，业务量很小，每个任务都需要你亲自去完成。比如，给老张家修完暖气管道，然后再去老李家换电灯泡。这个过程类似于单线程执行——每次只能处理一个任务，必须按顺序进行。

  • 示例：修暖气管道 -> 换电灯泡

多线程：随着业务的发展，你雇佣了多个工人。这时，你的公司可以同时为多户人家提供服务。每个工人就是一个线程，他们可以独立处理自己的任务，但仍然共享公司的资源（如工具、交通工具等）。

  • 示例：工人A修暖气管道，工人B换电灯泡，工人C修水管

主线程：你作为公司的老板和主线程，负责分配任务、协调工作，确保所有工人（线程）能顺利开展工作。如果某个工人遇到问题（冲突或需要协同），你可以及时介入解决，保持公司的正常运行。

通过这个类比，进程就像是一个独立的公司，每个线程就像是公司的员工，他们共享公司的资源，并共同完成任务。多线程能提高效率，但需要有效的管理和协调，确保资源的合理使用和任务的顺利完成。

进程管理是操作系统的核心功能之一，它通过对进程的调度和控制，实现了多任务并发，保证系统资源的高效利用和任务的公平执行。

API（Application Programming Interface, 应用程序编程接口） 是一种允许不同软件系统之间进行通信的接口。API 定义了一组函数、方法、协议或工具，使开发者可以利用这些接口来访问另一种软件的功能或数据，而无需了解其内部实现细节。

API重要特点：

  • 抽象层（Abstraction Layer）：API 提供了对底层复杂操作的简化抽象，开发者不需要了解底层实现细节。
  • 功能封装（Function Encapsulation）：API 将常用功能封装为可复用的接口，方便开发者调用。
  • 互操作性（Interoperability）：不同的软件系统可以通过 API 进行互操作，提高系统的兼容性和可扩展性。

系统调用（System Call） 是操作系统内核提供的接口，允许应用程序请求操作系统提供服务。系统调用是程序与操作系统之间的桥梁，使应用程序可以执行底层硬件操作，如文件操作、进程管理和网络通信等。系统调用可以被看作是操作系统API的一部分。当你在编程时使用API，你可能会间接地使用系统调用。例如，当你使用C++的文件流对象（如std::fstream）来读写文件时，这些对象内部可能会使用到操作系统的系统调用来进行实际的文件操作。

系统调用重要特点：

  • 内核模式（Kernel Mode）：系统调用将程序从用户模式切换到内核模式，以便执行特权操作。
  • 服务访问（Service Access）：通过系统调用，应用程序可以访问操作系统内核提供的服务。
  • 安全和稳定（Security and Stability）：系统调用由操作系统内核管理，确保了系统的安全性和稳定性。

总结：

  • API（应用程序编程接口） 是软件之间进行通信的接口，通过提供预定义的函数和方法，使开发者能够利用现有功能来构建应用程序。
  • 系统调用（System Call） 是操作系统提供的接口，使应用程序可以请求操作系统执行底层硬件操作和特权任务。

API 是一种更高层次的抽象，而系统调用是更底层的接口，两者都在不同层次上为软件开发提供了便利和功能。总的来说，API和系统调用都是使程序员能够更容易地编写代码和交互系统的工具。API提供了更高级别的抽象，而系统调用则提供了对操作系统服务的直接访问。

操作系统的四个重要特征包括：

1.并发（Concurrency） 并发是指两个或多个事件在同一时间间隔内发生。在操作系统中，并发可以通过多线程或多进程实现，线程或进程可以在一个处理器上交替执行，或者在多个处理器上同时执行。

  • 并发（Concurrency） 是指多个任务在同一时间段内交替进行，给人的感觉是同时发生，但实际上每个任务并不是同时进行的。
  • 并行（Parallelism） 与并发不同，并行是指两个或多个事件在同一时刻同时发生。例如：多线程下载文件，多个进程同时处理不同任务。

2.共享（Sharing） 共享是指系统中的资源可以被多个并发进程共同使用。共享的方式有两种：同时访问（同时共享）和在一段时间内交替访问（互斥共享）。

  • 同时共享（Concurrent Sharing）：多个进程同时访问同一资源。
  • 互斥共享（Mutual Exclusion Sharing）：多个进程轮流访问同一资源，以避免冲突。例如：多个进程共享打印机资源，互斥访问临界区。

3.虚拟化（Virtualization） 虚拟化是指把一个物理资源（如处理器、内存或磁盘）抽象为多个逻辑资源，或把多个物理资源抽象为一个逻辑资源。虚拟化使得用户感觉有更多的资源可用，或使得资源使用更加高效。

  • 空分复用（Space Division Multiplexing）：如虚拟存储器，使4GB内存的计算机能够运行需要超过4GB内存的程序。
  • 时分复用（Time Division Multiplexing）：时分复用通过将时间划分为多个时间片，每个时间片分配给不同的任务执行。通过CPU时间片轮转技术实现多任务并行，使得每个任务在短时间内轮流占用CPU资源，给人一种同时执行多个任务的感觉。如虚拟处理器和多任务操作系统，通过CPU时间片轮转技术实现多任务并行。

4.异步性（Asynchronism） 异步性是指由于进程间的并发性，使得进程交替执行，进程的执行不是一贯的，也不是在固定的时间间隔内发生。这意味着进程可能走走停停，取决于系统资源的可用性和调度策略。

  • 示例：异步I/O操作，操作系统在等待I/O操作完成时可以执行其他任务。

这些特征共同作用，使操作系统能够有效地管理计算机资源，提供稳定和高效的运行环境。

以上就是操作系统主要关注的内容，后续章节就是扩展讲解上述内容中重要的技术细节和实现思想

2. Process Management

本章主要讲解操作系统里面的进程管理部分。理解进程和线程，掌握进程调度相关的各种策略算法，并且熟悉信号量的互斥机制是非常重要的。

2.1 操作系统的用户交互

操作系统的用户交互主要分为两种类型：

2.1.1 命令解释程序（Command Interpreter）

  • 又称为 命令行界面（CLI，Command Line Interface）。
  • 用户通过输入文本命令与操作系统进行交互。
  • 常见的命令解释程序包括 Unix/Linux 系统的 Bash、Windows 的 CMD 和 PowerShell。
  • 优点：灵活性高，适合自动化脚本和高级用户。
  • 缺点：需要记住大量命令和语法，不直观。

以下是一个简单的 shell 指令示例：

# 创建一个新的目录
mkdir my_new_directory

# 进入新创建的目录
cd my_new_directory

# 创建一个新的空文件
touch new_file.txt

# 将一段文本写入文件中
echo "Hello, World!" > new_file.txt

# 显示文件内容
cat new_file.txt

# 复制文件并重命名
cp new_file.txt copy_of_new_file.txt

# 显示当前目录中的文件和子目录列表
ls -l

# 删除复制的文件
rm copy_of_new_file.txt

# 返回上一级目录
cd ..

# 删除新创建的目录及其内容
rm -r my_new_directory

2.1.2 图形用户界面（GUI，Graphical User Interface）

  • 用户通过图形化元素（如窗口、图标、按钮）与操作系统进行交互。
  • 常见的图形用户界面包括 Windows 的资源管理器（Windows Explorer）、macOS 的 Finder 以及 GNOME 和 KDE 等 Linux 桌面环境。
  • 优点：直观易用，适合初学者和普通用户。
  • 缺点：灵活性相对较低，复杂操作可能效率不高。

这两种交互方式各有优缺点，通常操作系统会同时提供这两种方式，以满足不同用户的需求和使用场景。通过结合命令行界面和图形用户界面，用户可以在不同情况下选择最合适的交互方式，提高工作效率和使用体验。

2.2 操作系统中的系统调用

系统调用（System Call） 是操作系统提供的一组接口，允许应用程序与操作系统内核交互，以请求内核执行特权操作。系统调用是程序与操作系统之间的桥梁，使应用程序可以执行低级别的系统功能，如文件操作、进程管理和网络通信等。

系统调用主要功能:

  • 文件操作：创建、打开、读取、写入和关闭文件。
  • 进程管理：创建、终止进程，分配资源，进程间通信等。
  • 内存管理：分配和释放内存，内存映射等。
  • 设备管理：访问和控制硬件设备，如磁盘、网络接口等。
  • 网络通信：发送和接收网络数据，设置网络连接等。

工作原理

  1. 用户模式到内核模式切换：当应用程序发出系统调用时，CPU将从用户模式切换到内核模式。
  2. 内核执行请求：操作系统内核接收系统调用请求，并执行相应的特权操作。
  3. 返回结果：操作系统内核完成操作后，将结果返回给应用程序，并切换回用户模式。

系统调用示例:

  • open：打开文件的系统调用。
  • read：读取文件内容的系统调用。
  • write：写入文件内容的系统调用。
  • fork：创建新进程的系统调用。
  • exec：执行新程序的系统调用。

通过系统调用，应用程序可以安全、高效地访问操作系统提供的底层资源和服务，实现丰富的功能。

系统调用

在后台，API 函数(Application Programming Interface, API
) 通常为应用程序开发人员提供了调用实际系统调用的函数。API 函数为开发人员提供了一个更高层次的抽象，使他们能够以更简单和统一的方式访问底层操作系统的功能，而不需要了解系统调用的具体实现细节。

通过调用 API 函数，开发人员可以间接地进行文件操作、进程管理、内存管理、设备控制等操作，这些 API 函数在后台会触发相应的系统调用来完成实际的操作。例如：

  • 文件操作：fopen API 函数会调用 open 系统调用。
  • 进程管理：fork API 函数直接对应 fork 系统调用。
  • 内存管理：malloc API 函数可能会调用 brk 或 mmap 系统调用。

总之，API 提供了一种方便的方式，使开发人员能够利用操作系统的功能，而不必处理系统调用的复杂性和底层细节。

在后台，API函数通常为应用程序员调用实际的系统调用

2.3 进程的概念

进程是计算机中一个正在运行的程序的实例。它不仅包括可执行程序的代码，还包含了该程序的运行状态信息，包括程序计数器、寄存器和变量的值。

进程的主要特点:

  1. 独立性：每个进程在其自己的内存空间中运行，独立于其他进程。
  2. 资源拥有：进程拥有自己的系统资源，如文件句柄和内存段。
  3. 并发性：操作系统可以在同一时间段内允许多个进程并发执行（即使在单个处理器系统中，通过时间分片实现）。
  4. 状态：进程有多种状态，包括新建、就绪、运行、等待和终止。

进程的组成部分:

  • 可执行代码：实际的程序代码。
  • 进程控制块（PCB）：存储进程的状态信息，如程序计数器、寄存器、内存分配等。
  • 堆栈：存储临时数据（函数参数、返回地址、局部变量）。
  • 堆：动态分配的内存，用于存储运行时需要的数据。
  • 数据段：全局变量和静态变量。

进程状态切换：

  1. 新建（New）：进程正在被创建。

    • 当一个程序被启动时，操作系统会为其创建一个新进程。此时进程处于新建状态。

  2. 就绪（Ready）：进程已经创建完毕，等待被调度执行。

    • 进程创建完成后，进入就绪队列，等待调度器将其调度到 CPU 上执行。
    • 切换方式：从新建状态切换到就绪状态。

  3. 运行（Running）：进程正在执行。

    • 当调度器选择一个就绪状态的进程并将其分配给 CPU 时，该进程进入运行状态，开始执行。
    • 切换方式：
      • 从就绪状态切换到运行状态。
      • 当等待的事件完成后，进程返回就绪状态，待调度器再次分配 CPU。

  4. 等待（Waiting）：进程在等待某些事件（如I/O操作）完成。

    • 如果进程在执行过程中需要等待某些事件（如 I/O 操作、资源可用等），它会进入等待状态。
    • 切换方式：从运行状态切换到等待状态（当进程请求的 I/O 操作开始执行时）。

  5. 终止（Terminated）：进程已经完成执行或被强制终止。

    • 当进程完成其全部工作或被强制终止时，进入终止状态，等待操作系统回收资源。
    • 切换方式：从运行状态切换到终止状态（当进程正常完成或遇到无法恢复的错误时）。

示例流程:

  1. 创建一个新进程：新进程从新建状态切换到就绪状态。
  2. 调度器选择进程：调度器将一个就绪进程分配给 CPU，进程从就绪状态切换到运行状态。
  3. 进程请求 I/O 操作：进程在运行过程中请求 I/O 操作，切换到等待状态。
  4. I/O 操作完成：I/O 操作完成，进程从等待状态返回就绪状态。
  5. 进程重新获得 CPU：调度器再次选择该进程，进程切换到运行状态。
  6. 进程完成执行：进程完成所有任务或被强制终止，进入终止状态。

这种状态切换机制是多任务操作系统有效管理和调度进程的重要方式，确保系统资源的合理分配和使用。

进程状态图

当一个程序被加载到内存并开始执行时，操作系统为其创建一个进程，并分配所需的系统资源。操作系统通过进程调度程序管理和调度进程的执行，确保每个进程可以合理地使用 CPU 时间和其他资源。

进程是多任务操作系统的基础，允许多个程序同时运行，提高系统的效率和资源利用率。

PCB（Process Control Block）是操作系统中用于管理进程的一个数据结构。每个正在运行的进程都有一个对应的 PCB，用于存储进程的各种信息。PCB是进程存在的唯一标志。常见的 PCB 内容包括：

  1. 进程状态：记录进程当前的状态（如运行、就绪、阻塞等）。
  2. 程序计数器：指向下一条将执行的指令地址。
  3. CPU寄存器：保存进程执行时的 CPU 寄存器内容，包括通用寄存器、程序计数器等。
  4. 内存管理信息：如进程的内存分配、页表等。
  5. 进程标识符：进程的唯一标识（PID）。
  6. 调度信息：包括优先级、调度队列指针等。
  7. I/O信息：包括进程使用的输入输出设备信息和相关状态。

PCB 是操作系统调度和管理进程的重要工具，确保操作系统能够有效地保存和恢复进程的状态。

2.3.1 线程的概念

线程(Thread) 是操作系统中的基本调度单位，是进程中的一个执行单元。一个进程可以包含多个线程，多个线程共享进程的资源（如内存空间、文件描述符等），但每个线程都有自己的程序计数器、寄存器和堆栈。线程被用来执行并发任务。

线程的特点：

  1. 轻量级：相比进程，线程的创建和销毁成本较低，切换速度较快。
  2. 共享资源：同一进程内的多个线程共享进程的地址空间、全局变量等资源。
  3. 独立执行：每个线程有自己的程序计数器、栈和局部变量，可以独立执行任务。
  4. 并发执行：多个线程可以并发或并行地执行，适用于多核处理器和多任务环境。

线程与进程的区别：

  • 进程是资源分配的基本单位，每个进程都有独立的内存空间。
  • 线程是 CPU 调度的基本单位，同一进程内的多个线程共享内存资源，但有独立的执行路径。

2.3.2 操作系统中的多线程模型（Multithreading Models）

操作系统中的多线程模型决定了用户线程与内核线程之间的映射关系。主要有以下几种模型：

1. 一对一模型（One-to-One Model）

  • 每个用户线程映射到一个内核线程。
  • 优点：可以充分利用多处理器的并行性，因为每个线程可以在不同的处理器上独立运行。
  • 缺点：每个线程需要一个内核线程，导致线程的创建和管理开销较大，可能影响性能。

2. 多对一模型（Many-to-One Model）

  • 多个用户线程映射到一个内核线程。
  • 优点：线程的创建和管理开销较小，因为内核只需要管理一个内核线程。
  • 缺点：由于所有用户线程都在同一个内核线程上运行，无法利用多处理器的并行性。如果一个线程阻塞，整个进程都会被阻塞。

3. 多对多模型（Many-to-Many Model）

  • 多个用户线程映射到多个内核线程。
  • 优点：结合了前两种模型的优点，既可以利用多处理器的并行性，又能控制线程的创建和管理开销。
  • 缺点：需要复杂的调度和管理机制来平衡用户线程与内核线程之间的映射关系。

4. 二级模型（Two-Level Model）

  • 是多对多模型的变体，允许多个用户线程映射到同一个内核线程，也允许一个用户线程映射到多个内核线程。
  • 优点：允许更灵活的线程管理，结合了多对多模型和一对一模型的优点。
  • 缺点：需要更复杂的调度机制，增加了系统的实现复杂性。
多线程模型

2.4 进程控制

进程控制是操作系统管理和调度进程的关键任务。它包括创建、调度、终止进程等操作，以确保系统中的进程能高效、按需执行。

1. 进程的创建

  • 创建新进程：操作系统通过系统调用（如 fork 在 Unix 系统中）创建一个新进程。新进程通常是当前进程的副本，称为子进程。
  • 资源分配：当创建新进程时，操作系统为其分配必要的资源（如内存、文件句柄等），并初始化进程控制块（PCB）以存储进程信息。

2. 进程调度

  • 进程状态：进程在执行过程中会经历不同的状态（如就绪、运行、阻塞等）。操作系统调度器负责决定进程在何时进入哪种状态。
  • 调度算法：操作系统使用各种调度算法（如先来先服务 FCFS、时间片轮转 RR、最短作业优先 SJF 等）来决定哪个进程应该获得 CPU 时间。
  • 多任务处理：操作系统允许多个进程并发运行，通过上下文切换在多个进程间分配 CPU 时间。

3. 进程同步与通信

  • 进程同步：在并发执行的多个进程间，操作系统提供同步机制（如信号量、互斥锁、条件变量等）以确保共享资源的正确使用，避免数据竞争和死锁。
  • 进程通信：进程之间可以通过多种方式进行通信，如管道、消息队列、共享内存等。操作系统提供通信机制以允许进程间交换数据。

4. 进程终止

  • 进程终止：进程执行完毕或由于错误发生时，会通过系统调用（如 exit）终止。操作系统会回收进程所占用的资源，关闭文件、释放内存等。
  • 父子进程的终止：当子进程终止时，操作系统会向父进程发送信号（如 Unix 系统中的 SIGCHLD），父进程可选择等待子进程的终止并回收子进程资源。

5. 进程控制块（PCB）

  • PCB（Process Control Block）：每个进程在操作系统中都有一个对应的 PCB，用于存储进程的状态、程序计数器、CPU 寄存器、内存信息等。
  • 进程调度：PCB 是进程调度和管理的核心数据结构，操作系统通过它来实现上下文切换和进程状态的转换。

进程控制是操作系统的重要功能，涉及进程的创建、调度、同步、通信以及终止等方面。通过有效的进程控制，操作系统能够确保多任务环境下的进程按预期运行，资源得到合理分配。

2.5 进程间调度

操作系统中的进程调度是管理CPU资源分配的一项重要功能。它决定了哪些进程何时运行，以及如何在多个进程间切换，以实现系统资源的高效利用和响应。

常见的调度算法主要有：

1. 先到先服务（First-Come First-Served, FCFS）

  • 简单且直观，进程按照到达顺序执行。
  • 优点：实现简单。
  • 缺点：容易导致长进程阻塞短进程（队头阻塞），可能增加平均等待时间。

2. 短作业优先（Shortest-Job-First, SJF）

  • 优先执行预计运行时间最短的进程。
  • 优点：减少平均等待时间。
  • 缺点：需要准确预测进程运行时间，长作业可能会长期得不到调度（饥饿现象）。

3. 优先级调度算法（Priority Scheduling）

  • 根据进程的优先级调度，优先级高的进程先执行。
  • 优点：灵活性高，可以根据需求调整优先级。
  • 缺点：低优先级进程可能会长期得不到调度（饥饿现象）。

4. 轮转调度（Round-Robin，RR）算法

  • 每个进程分配一个固定的时间片，时间片到后切换到下一个进程。
  • 优点：公平，适用于时间共享系统。
  • 缺点：时间片过大或过小会影响系统性能。

5. 多级反馈队列调度算法（Multilevel Feedback Queue）

  • 结合多个优先级队列和时间片调度。
  • 进程根据其行为动态调整优先级和队列位置。
  • 优点：灵活性高，能够较好地平衡响应时间和系统吞吐量。

通过这些调度算法，操作系统能够高效管理和分配CPU资源，保证系统的稳定性和用户体验。下面分别分析上述调度算法.

2.5.1 先到先服务（First-Come First-Served, FCFS）

先到先服务（First-Come, First-Served，FCFS） 是一种简单的进程调度算法，它的工作原理是：当进程到达系统时，它们被放入就绪队列。调度器选择队列中的第一个进程进行执行，直到该进程完成或发生阻塞事件，然后调度器选择下一个进程。

  • 优点：
    • 公平性（Fairness）：FCFS算法对所有进程都是公平的，因为它按照进程到达的顺序进行调度。
    • 简单性（Simplicity）：FCFS算法非常简单和易于实现。
  • 缺点：
    • 无法充分利用CPU（Poor CPU Utilization）：如果当前正在运行的进程需要大量的I/O操作，那么CPU可能会在等待I/O操作完成时处于空闲状态。
    • 平均等待时间可能较长（Long Average Waiting Time）：在FCFS算法中，短的进程可能会被长的进程阻塞，这种现象被称为“饥饿”（Starvation）或“拖尾效应”（Convoy Effect）。
    • 无法支持优先级（Lack of Priority Support）：FCFS算法不支持优先级，因此无法保证重要的进程能够优先执行。

总的来说，虽然FCFS算法简单且公平，但由于其无法有效地利用CPU和支持优先级，所以在需要高效率或优先级调度的系统中，通常不会使用FCFS算法。

先到先服务调度算法

在操作系统中，饥饿（Starvation） 是指某些进程长时间得不到所需资源，从而无法执行的情况。这通常发生在资源分配机制不公平或不完善的情况下。饥饿现象主要出现在以下几种情况下：

  • 优先级调度：在优先级调度算法中，如果某些低优先级的进程始终被高优先级进程抢占，低优先级进程可能会一直得不到执行机会，从而陷入饥饿状态。
  • 资源竞争：当多个进程竞争有限的资源时，某些进程可能持续无法获得资源，导致无法继续执行。
  • 长作业排队：在先到先服务（FCFS）或短作业优先（SJF）等调度算法中，长时间运行的进程可能会因其他短作业的持续到达而长期得不到调度。

解决饥饿问题的一种常见方法是老化机制（Aging），即逐渐提高长期未被调度进程的优先级，使其最终能够获得资源并执行。

2.5.2 短作业优先（Shortest-Job-First, SJF）

在这种算法中，调度器选择就绪队列中预计运行时间最短的进程进行执行。预计运行时间可以是进程的CPU突发时间（CPU burst time）或者是进程的剩余执行时间。（这里就要看是非抢占式的还是抢占式的了，可以直观理解）

短作业优先调度算法的主要优点是它最小化了平均等待时间。因为短的进程总是优先于长的进程，所以它们的等待时间会更短，从而使得平均等待时间最小。

然而，这种算法也有一些缺点。首先，它需要知道进程的预计运行时间，但在实际的系统中，这通常是无法预知的。其次，这种算法可能会导致 “饥饿”（Starvation） 现象，即长的进程可能会被无限期地推迟，因为总是有短的进程到来。
总的来说，短作业优先调度算法在理论上是非常有效的，但在实际的系统中，由于需要预知进程的运行时间以及可能导致的饥饿问题，它的应用受到了一些限制。

短作业优先调度算法

2.5.3 优先级调度算法（Priority-Scheduling）

优先级调度算法是一种操作系统中的进程调度算法。在这种算法中，每个进程都有一个优先级，操作系统总是选择优先级最高的进程来运行。这种算法的主要特点如下：

  • 优先级：每个进程都有一个优先级，优先级高的进程优先执行。（抢占式，preemptive）
  • 动态调整：系统可以根据需要动态调整进程的优先级。例如，为了防止低优先级的进程永远得不到执行，系统可能会随着时间的推移提高等待进程的优先级。
  • 饿死问题：如果总是有新的高优先级进程出现，那么低优先级的进程可能永远得不到执行，这就是所谓的饿死问题。为了解决这个问题，系统可能会采取一些策略，比如老化（随着时间的推移提高等待进程的优先级）。

这种算法在实时系统中特别有用，因为在这些系统中，有些任务（比如控制飞机的自动驾驶仪）比其他任务更重要，因此需要优先执行。但是，这种算法也有一些缺点，比如可能会导致低优先级的进程饿死。因此，设计一个好的优先级调度算法需要权衡各种因素。

优先级调度算法

2.5.4 轮转调度（Round-Robin，RR）算法

轮转调度（Round-Robin，RR）算法是一种非常常见的操作系统进程调度算法。以下是对其的简要解释：

  • 时间片（Time Quantum）：在轮转调度算法中，每个进程被分配一个固定长度的时间片来执行。当一个进程的时间片用完时，它将被移出CPU，下一个进程将开始执行。
  • 公平性（Fairness）：由于每个进程都有相同长度的时间片来执行，因此这种算法被认为是公平的。没有进程会因为优先级低而被饿死。
    上下文切换（Context Switch）：当一个进程的时间片用完，操作系统需要进行上下文切换，将CPU从当前进程切换到下一个进程。这会产生一定的开销。
  • 响应时间（Response Time）：轮转调度算法通常能提供良好的响应时间，因为每个进程都会定期得到CPU时间。

这种算法适用于时间共享系统，但如果时间片设置得不合适，可能会导致过多的上下文切换，从而降低系统性能。因此，选择合适的时间片长度是实现轮转调度算法的关键。如果时间片过长，那么系统的响应时间可能会变差；如果时间片过短，那么上下文切换的开销可能会变大。

同一时刻两个进程 A 和 B, A 刚下处理机, B 刚进入队列, 默认 B 先轮转时间片。

  • 如果时间片太大, 退化为FCFS, 会增大进程响应时间
  • 如果时间片太小, 进程切换频繁, 切换进程会花费大量时间

一般来说, 设计时间片要让切换进程的开销占比不超过 1%

轮转调度算法

2.5.5 多级反馈队列调度算法（Multilevel Feedback Queue）

多级反馈队列调度算法（Multilevel Feedback Queue Scheduling）是一种操作系统中的进程调度算法。以下是对其的简要解释：

  • 多级队列（Multilevel Queues）：在这种算法中，存在多个队列，每个队列都有自己的优先级。优先级最高的队列中的进程首先得到执行。（也就是前一队列为空的时候，才能执行当前队列！！）
  • 反馈（Feedback）：如果一个进程在其分配的时间片内没有完成，那么它将被移动到优先级较低的队列。这就是所谓的“反馈”机制。
  • 公平性和灵活性（Fairness and Flexibility）：这种算法旨在结合优先级调度和轮转调度的优点，以实现公平性和灵活性。它可以确保高优先级的进程快速执行，同时也不会饿死低优先级的进程。
  • 动态优先级（Dynamic Priorities）：进程的优先级不是固定的，而是可以根据其行为动态改变。例如，如果一个进程经常阻塞等待I/O操作，那么它的优先级可能会提高，以便在I/O操作完成后能够快速得到执行。

这种算法在许多操作系统中都得到了应用，因为它既可以处理交互式进程（这些进程需要快速响应），也可以处理批处理进程（这些进程需要长时间运行）。然而，它的实现相对复杂，需要维护多个队列，并动态调整进程的优先级。此外，选择合适的队列数量和时间片长度也是一个挑战。如果设置不当，可能会导致某些进程得不到公平的CPU时间，或者系统的上下文切换开销过大。因此，实现这种算法需要权衡各种因素。

这个算法无明显缺点，但是会导致饥饿！考虑一种情况：长时间运行的进程一直被降级到低优先级队列，而新到达的高优先级进程源源不断地占用CPU资源，那么低优先级的进程可能会长期得不到调度，导致饥饿。

多级反馈队列调度算法

2.6 进程间通信

进程间通信（IPC，Inter-Process Communication）是操作系统中的一项重要机制，用于让不同进程之间交换数据或同步操作。操作系统提供了多种进程间通信方式，每种方式有其特点和适用场景。以下是几种常见的进程间通信方式的详细讲解：

2.6.1 管道（Pipe）

管道是一种最基本的进程间通信方式，允许数据在一个进程与另一个进程之间单向流动。它适用于父子进程之间的通信。

  • 匿名管道（Anonymous Pipe）：不具备名字，一般用于有亲缘关系的进程（如父子进程）。匿名管道是半双工的，即数据只能单向流动。
  • 命名管道（Named Pipe）：有名字，可以在无亲缘关系的进程间使用，因此适用于不同进程间的通信。命名管道是全双工的，即可以双向传输数据。
管道通信

匿名管道通常用于父子进程之间的通信。它是半双工的，只能进行单向数据流动。在下面这个示例中，父进程通过匿名管道发送数据给子进程，子进程接收并打印出来。

import os

# 创建一个匿名管道
pipe_read, pipe_write = os.pipe()

# 创建子进程
pid = os.fork()

if pid > 0:  # 父进程
    # 关闭读端，只写
    os.close(pipe_read)

    # 向管道中写入数据
    os.write(pipe_write, b"Hello from parent process!")

    # 关闭写端
    os.close(pipe_write)
    
elif pid == 0:  # 子进程
    # 关闭写端，只读
    os.close(pipe_write)

    # 从管道中读取数据
    message = os.read(pipe_read, 1024)
    print(f"Child process received message: {message.decode()}")

    # 关闭读端
    os.close(pipe_read)

命名管道可以用于不同进程之间的通信。命名管道通过文件系统提供了一个可以由多个进程访问的接口。

import os
# *****父进程写数据******* #
# 创建命名管道（FIFO）
fifo_path = "/tmp/my_named_pipe"
try:
    os.mkfifo(fifo_path)
except FileExistsError:
    pass  # 如果管道已经存在，跳过创建

# 向命名管道写数据
with open(fifo_path, 'w') as fifo:
    fifo.write("Hello from parent process!")

print("Parent process has written the message.")

# 父进程使用 mkfifo() 创建一个命名管道 /tmp/my_named_pipe。然后，父进程通过写操作将消息写入管道。

import os
# ****子进程读数据**** #
fifo_path = "/tmp/my_named_pipe"

# 从命名管道读取数据
with open(fifo_path, 'r') as fifo:
    message = fifo.read()
    print(f"Child process received message: {message}")

# 子进程打开相同的管道文件并从中读取消息。这说明命名管道是全双工的，可以在不同的进程间进行通信。

2.6.2 消息队列（Message Queue）

消息队列是由内核维护的一种数据结构，用于在进程间传递消息。消息队列中的消息按照优先级或发送顺序排队，可以支持多个进程进行通信。

  • 消息队列是一种基于消息的通信机制，可以支持多对多的通信模式。
  • 通过消息队列，进程可以通过发送消息和接收消息来进行数据交换。
  • 它的优势是，进程间通信不需要共享内存，但也会有一定的性能开销。
消息队列

2.6.3 共享内存（Shared Memory）

共享内存是一种效率较高的进程间通信方式，多个进程可以直接访问同一块内存区域。一个进程创建并映射这块共享内存，其他进程可以直接访问该内存区域。

  • 共享内存允许多个进程共享数据，因此可以显著提高进程间的数据交换效率。
  • 但由于多个进程可能同时读写共享内存，必须通过信号量等同步机制来保证数据一致性，避免竞争条件和冲突。
共享内存

2.6.4 信号量（Semaphore）

信号量是一种同步工具，通常用于控制多个进程对共享资源的访问。信号量内部包含一个计数器，该计数器控制访问共享资源的进程数目。

  • 信号量常用于控制对共享内存、文件等资源的访问，它可以防止资源竞争。
  • 信号量有两种类型：计数信号量（控制资源的数量）和二值信号量（类似于锁，只允许一个进程访问资源）。
  • 信号量通常与共享内存结合使用，用于保证对临界区的同步和互斥。

信号量机制非常重要，随后仔细讲解这个内容。

信号量机制

2.6.5 信号（Signal）

信号是一种异步通知机制，用于向进程发送通知，告知其某个事件已经发生。例如，操作系统可以向进程发送 SIGINT 信号来中断它，或者使用 kill 命令向一个进程发送信号。

  • 信号是一种非常轻量级的进程间通信方式，适用于通知进程发生了某种事件或请求处理。
  • 信号通常不会携带大量数据，主要用于进程间的控制和通知。
信号通信

2.6.6 套接字（Socket）

套接字是一种广泛用于进程间通信的机制，尤其适用于不同主机之间的通信。通过网络协议，套接字允许不同机器上的进程进行通信。

  • 套接字不仅可以用于不同主机间的进程间通信，也可以用于本地主机上的进程间通信。
  • 套接字可以是面向连接的（如 TCP 套接字）或无连接的（如 UDP 套接字），适用于不同的应用场景。
  • 它是进程间通信中最为通用和灵活的一种方式，尤其在分布式系统中具有重要作用。
套接字

总的来说，这些通信方式有下面的应用场景。

  • 管道适用于父子进程的单向通信。
  • 消息队列适合需要按消息传递数据的多进程场景。
  • 共享内存提供高效的跨进程数据共享，但需要同步机制来保证数据一致性。
  • 信号量用于控制对共享资源的访问，并且用于进程间的同步与互斥。
  • 信号是一种简单的异步通信机制，用于进程间的通知。
  • 套接字是最通用的进程间通信机制，尤其在网络编程中得到广泛应用。

2.7 进程间的并发和同步

操作系统中的并发控制主要涉及多个进程或线程在共享资源时如何协调与管理，以避免冲突和问题。首先需要熟悉下面的几个概念：

2.7.1. 临界区（Critical Section）

  • 背景： 多个进程或线程需要访问共享资源（如内存、文件、设备等）时，为了防止并发访问导致数据错误，需要对访问过程进行限制。临界区是程序中可能发生资源竞争的部分，需要特殊保护。
临界区

2.7.2 互斥（Mutual Exclusion）

  • 背景： 为了解决共享资源访问冲突的问题，互斥保证任何时刻只有一个进程或线程可以进入临界区。
  • 常见的实现方式：
    • 锁（Locks）
    • 信号量（Semaphores）
    • 监视器（Monitors）

2.7.3 死锁（Deadlock）

  • 背景： 死锁问题发生在资源分配和进程调度的场景中。当多个进程在相互等待对方释放资源时，系统进入无法继续运行的状态。
  • 避免死锁需要使用特定的资源分配算法和机制：
    • 银行家算法（Banker’s Algorithm）

2.7.4 饥饿（Starvation）

  • 背景： 在资源分配和调度策略不公平的情况下，有些进程可能长时间得不到资源，无法执行。这种问题称为饥饿。
  • 为了避免饥饿，需要使用公平的调度算法，确保每个进程都有机会进入临界区：
    • 先到先服务（FCFS）调度
    • 动态优先级调整

2.7.5 信号（Signals）

  • 背景： 信号是一种异步通信机制，用于通知进程某个事件的发生。例如，使用kill命令发送信号。
  • 应用： 常用于进程终止、定时器中断、资源耗尽等场景。

2.7.6 线程同步（Thread Synchronization）

  • 背景： 在多线程环境中，线程之间的同步与进程同步类似，但由于线程共享相同的内存地址空间，面临的问题和解决方案略有不同。
  • 实现方式：
    • 互斥锁（Mutexes）
    • 条件变量（Condition Variables）
    • 读写锁（Read-Write Locks）

2.7.7 条件变量（Condition Variables）

  • 背景： 条件变量用于在线程之间实现复杂的同步机制，通过等待某一条件为真后再继续执行。
  • 应用： 常与互斥锁配合使用，解决生产者-消费者问题等。

2.7.8 自旋锁（Spin Locks）

  • 背景： 自旋锁是一种忙等待的锁机制，用于保护短时间临界区。
  • 应用： 适用于临界区非常短且线程切换开销较大的情况。

2.7.9 信号量（Semaphores）

  • 背景： 信号量用于控制对资源的访问，支持同步和互斥机制。
  • 类型：
    • 二进制信号量（Binary Semaphores）： 类似于互斥锁。
    • 计数信号量（Counting Semaphores）： 允许多个线程访问一定数量的资源。

以上概念是操作系统中并发程序设计和同步机制的核心问题，旨在协调多进程或线程的资源访问，确保系统的正确性和高效性。有了以上的背景，我们再来解决操作系统中进程同步互斥的经典问题如：

  • 生产者-消费者问题（Producer-Consumer Problem）
  • 读者-写者问题（Readers-Writers Problem）
  • 哲学家进餐问题（Dining Philosophers Problem）

2.7 进程互斥

在操作系统中，进程互斥（Mutual Exclusion） 是确保多个进程在访问共享资源时不发生冲突的关键概念。互斥的目的是防止并发进程同时进入临界区（Critical Section），以避免数据不一致和其他错误。

2.7.1 进程互斥的软件实现方法

在操作系统中，为了解决多个进程共享资源时的互斥问题，可以通过标志检查算法实现互斥控制。以下是几种经典的软件实现方法：

1️⃣ 单标志法（Single Flag Method）

  • 使用一个共享的布尔标志表示是否有进程正在执行临界区。
  • 如果标志为真，则其他进程必须等待，直到标志变为假。

代码示例：

// P0:
{
    while (turn != 0);   // 等待临界区空闲
    critical section;    // 进入临界区
    turn = 1;            // 交出控制权
    remainder section;   // 进入剩余区
}

// P1:
{
    while (turn != 1);
    critical section;
    turn = 0;
    remainder section;
}

单标志法存在的问题是：

  • 访问顺序固定为 0 → 1 → 0 → 1…，不满足空闲让进原则。
  • 当临界区空闲且 P0 未进入时，P1 仍无法进入，导致资源浪费。

2️⃣ 双标志先检查法（Two Flags, Check First Method）

  • 每个进程都有一个标志，表示它是否希望进入临界区。
  • 进程在进入临界区前检查对方的标志，确保对方不需要进入临界区时才进入。

代码示例：

bool flag[2] = {false, false};  // flag[i] = true 表示进程 i 想进入临界区

// P0:
{
    while (flag[1]);   // 检查对方标志
    flag[0] = true;    // 设置自己的标志
    critical section;  // 进入临界区
    flag[0] = false;   // 离开时清除标志
    remainder section;
}

// P1:
{
    while (flag[0]);
    flag[1] = true;
    critical section;
    flag[1] = false;
    remainder section;
}

双标志先检查法存在的问题是：

  • 如果 P0 在退出 while 循环后，标志尚未设置为 true 时被切换，P1 也可能进入临界区，导致不满足忙则等待原则。

3️⃣ 双标志后检查法（Two Flags, Check Afterwards Method）

  • 在设置自己的标志后，再检查对方的标志。
  • 如果对方不需要进入临界区，当前进程即可进入。

示例代码：

bool flag[2] = {false, false};

// P0:
{
    flag[0] = true;     // 先设置自己的标志
    while (flag[1]);    // 后检查对方标志
    critical section;
    flag[0] = false;
    remainder section;
}

// P1:
{
    flag[1] = true;
    while (flag[0]);
    critical section;
    flag[1] = false;
    remainder section;
}

双标志后检查法存在的问题是：

  • 可能导致饥饿问题：如果两个进程交替设置标志，低优先级进程可能一直无法进入临界区。

4️⃣ Peterson 算法（Peterson’s Algorithm）

  • 通过两个共享变量实现互斥：
    • flag[2] 表示每个进程是否希望进入临界区。
    • turn 表示轮到哪个进程进入临界区。
  • 设置自己的标志后，将进入权交给对方，主动等待对方进入临界区。

代码示例：

bool flag[2] = {false, false};
int turn = 0;

// P0:
{
    flag[0] = true;        // 设置自己的标志
    turn = 1;              // 让出优先权
    while (flag[1] && turn == 1);  // 等待对方离开或轮到自己
    critical section;      // 进入临界区
    flag[0] = false;       // 离开时清除标志
    remainder section;
}

// P1:
{
    flag[1] = true;
    turn = 0;
    while (flag[0] && turn == 0);
    critical section;
    flag[1] = false;
    remainder section;
}

Peterson 算法的优缺点有：

  • 优点
    • 满足互斥性：任意时刻只有一个进程能进入临界区。
    • 避免死锁：两个进程不会无限等待。
    • 满足空闲让进原则：当临界区空闲时，进程可立即进入。
  • 缺点
    • 仅适用于两个进程的场景。
    • 扩展到多进程环境时，算法会变得复杂。

简单总结一下以上进程互斥的软件实现方法

方法 优点 问题或缺点
单标志法 简单易实现 可能导致竞态条件，不满足空闲让进原则
双标志先检查法 避免竞态条件 不满足忙则等待原则，可能导致数据竞争
双标志后检查法 避免死锁 可能导致饥饿问题
Peterson 算法 满足互斥性、避免死锁和饥饿，符合互斥原则 仅适用于两个进程的互斥场景

2.7.2 进程互斥的硬件实现方法

1.禁止中断（Disable Interrupts）

  • 机制：
    在单处理器系统中，进程在进入临界区之前，通过禁用中断来保证它不被打断。这意味着在执行关键代码时，不会发生上下文切换，也就避免了其他进程同时访问共享资源的可能性。
  • 优点：
    • 简单且易于实现。
    • 在单处理器环境下，可以有效地防止竞态条件（Race Condition）。
  • 缺点：
    • 仅适用于单处理器系统：在多处理器系统中，禁止一个处理器的中断并不能阻止其他处理器访问共享资源。
    • 影响系统响应性：如果进程在临界区花费较长时间，系统将无法及时响应硬件中断（如 I/O 事件），可能导致性能问题。
    • 不适合用户程序：只有操作系统（内核）才能控制中断，普通用户进程无法使用这一方法。
  • 适用场景：小型、实时性要求不高的单处理器系统。

禁止中断通常由操作系统的内核代码实现。以下是一个伪代码示例：

// 单处理器系统伪代码
void critical_section() {
    disable_interrupts();  // 禁止中断
    
    // 临界区代码
    shared_resource++;
    
    enable_interrupts();   // 恢复中断
}

注意：

  • disable_interrupts() 和 enable_interrupts() 是硬件相关的低级操作，不适用于用户态程序。
  • 这种方法仅用于单处理器环境。

2.特殊机器指令（Special Machine Instructions）

机制：

  • 现代硬件通常提供特殊指令来帮助实现进程互斥。这些指令能够在单个不可中断的原子操作中完成对共享内存位置的读取和修改。
  • 常见的指令包括：
    • 测试并设置（Test and Set）：
      • 功能：检查一个变量的值是否为 0（或特定值），如果是则设置为 1，并返回原来的值。
      • 应用：可以用它来实现一个简单的锁。
    • 交换（Swap）：
      • 功能：交换两个内存单元的值，保证操作是原子的。
      • 应用：常用于实现信号量或互斥锁。

优点：

  • 高效：不需要禁用中断，能在多处理器系统中使用。
  • 硬件支持：这些指令的设计初衷就是为了解决同步问题。

缺点：

  • 忙等待（Busy Waiting）：使用这些指令实现的锁通常基于自旋锁（Spinlock），可能导致等待进程一直占用 CPU（忙等），浪费计算资源。
  • 增加硬件复杂性：硬件必须支持这些指令。
  • 适用场景：
    • 多处理器系统。
    • 临界区很短、避免禁用中断的情况下。

以下是使用 Test and Set 指令实现锁的示例：

// 使用 Test and Set 指令实现的锁
typedef int lock_t;

lock_t lock = 0; // 0 表示未加锁，1 表示已加锁

int test_and_set(int *lock) {
    int old = *lock;
    *lock = 1; // 将锁设置为 1
    return old; // 返回原来的值
}

void acquire_lock(lock_t *lock) {
    while (test_and_set(lock) == 1) {
        // 自旋等待
    }
}

void release_lock(lock_t *lock) {
    *lock = 0; // 解锁
}

void critical_section() {
    acquire_lock(&lock); // 加锁
    
    // 临界区代码
    shared_resource++;
    
    release_lock(&lock); // 解锁
}

说明：

  • test_and_set() 是一个不可中断的原子操作，硬件确保其操作的原子性。
  • 如果锁已被占用，进程会在循环中等待（自旋锁）。

3.原子操作（Atomic Operations）

机制：

  • 原子操作指的是在执行时不会被中断的一系列操作。这些操作通常是通过硬件或特殊指令实现的，确保即使多个进程或线程同时访问共享变量，操作的结果仍然是可预测的。
  • 应用中最常见的是信号量和互斥锁的实现。
  • 原子操作的核心是“不可分割性”：一次性完成对共享资源的修改，防止竞态条件。

常见例子：

  • 增/减操作：如 atomic_increment() 或 atomic_decrement()。
  • 比较并交换（Compare and Swap, CAS）：
    • 功能：比较内存中的值和给定值，如果相等，则将内存中的值替换为新值。
    • 应用：用于实现无锁数据结构。

优点：

  • 不需要禁用中断，适用于多处理器系统。
  • 性能高效：适合在时间关键的并发操作中使用。

缺点：

  • 与忙等待类似，使用不当可能导致资源浪费。
  • 需要硬件支持，且某些复杂的原子操作可能受限于硬件实现。

适用场景：

  • 多线程或多进程的同步场景，特别是当需要实现高性能无锁数据结构时。

使用Compare and Swap (CAS) 指令实现锁：

// 使用 Compare and Swap 实现锁
typedef int lock_t;

lock_t lock = 0; // 0 表示未加锁，1 表示已加锁

int compare_and_swap(int *addr, int expected, int new_value) {
    int old = *addr;
    if (old == expected) {
        *addr = new_value; // 将值替换为 new_value
    }
    return old; // 返回旧值
}

void acquire_lock(lock_t *lock) {
    while (compare_and_swap(lock, 0, 1) != 0) {
        // 自旋等待
    }
}

void release_lock(lock_t *lock) {
    *lock = 0; // 解锁
}

void critical_section() {
    acquire_lock(&lock); // 加锁
    
    // 临界区代码
    shared_resource++;
    
    release_lock(&lock); // 解锁
}

说明：

  • compare_and_swap() 是一个硬件提供的原子操作。
  • 当 lock 的值是期望值（expected）时，才会将其更新为新值（new_value）。
  • CAS 在实现无锁数据结构时非常常用。

总结一下：

方法 关键代码 优点 缺点
禁止中断 disable_interrupts() 简单，适合单处理器系统 不适合多处理器，影响响应性
Test and Set test_and_set(lock) 高效，适合多处理器系统 忙等待，自旋可能浪费资源
Compare and Swap compare_and_swap(lock) 强大灵活，可用于无锁数据结构 忙等待，需要硬件支持

2.8 信号量机制

信号量（Semaphore） 是一种用于同步进程或线程的机制，确保多个进程或线程可以安全、协调地访问共享资源。它通常用于解决临界区（Critical Section）问题。

信号量是一种整型变量，表示资源的可用数量。信号量分为两种类型：

  • 计数信号量（Counting Semaphore）：其值可以任意增减，通常用于管理多个相同的资源。
  • 二进制信号量（Binary Semaphore）：其值只能为0或1，类似于互斥锁（Mutex）。

2.8.1 信号量机制中的PV操作

1. P操作（Proberen，Test）：

  • 功能：试图获取信号量。将信号量的值减1。
  • 逻辑：如果信号量的值大于0，表示有可用资源，继续执行。否则，进程进入等待状态，直到信号量的值大于0。
P(S):
    while S <= 0:
        wait
    S = S - 1

2. V操作（Verhogen，Increment）：

  • 功能：释放信号量。将信号量的值加1。
  • 逻辑：表示释放一个资源。如果有进程在等待信号量，该操作会唤醒其中一个进程.
V(S):
    S = S + 1

下面是使用Python实现的一个简单示例，演示如何使用信号量控制对共享资源的访问。假设我们有一个共享计数器，需要多个线程安全地访问。

import threading
import time

# 定义一个信号量，初始值为1（相当于一个互斥锁）
semaphore = threading.Semaphore(1)
counter = 0  # 共享资源

# 定义一个函数，使用信号量控制访问共享资源
def safe_increment():
    global counter
    with semaphore:  # P操作，获取信号量
        temp = counter
        time.sleep(0.1)  # 模拟一些操作
        counter = temp + 1
        print(f'Counter value: {counter}')

# 创建多个线程
threads = []
for i in range(10):
    t = threading.Thread(target=safe_increment)
    threads.append(t)
    t.start()

# 等待所有线程完成
for t in threads:
    t.join()

print(f'Final counter value: {counter}')

在这个示例中，信号量semaphore控制对共享资源counter的访问。每个线程在进入临界区前都会调用P操作（即with semaphore语句），在离开临界区时自动调用V操作（即退出with块）。

看一个更直观的示例代码

Semaphore S = 0;

void P1(){
    code 1;
    code 2;
    V(S);
    code 3;
}

void P2(){
    P(S);
    code 4;
    code 5;
    code 6;
}
// 这样P1先执行，P2后执行

2.9 经典同步互斥问题

操作系统中的同步与互斥问题涉及多个进程或线程在共享资源上的访问协调。它们解决了并发执行时资源共享所可能引发的冲突，确保系统的正确性和稳定性。

  1. 同步问题（Synchronization）：
    同步问题是指多个进程或线程需要按照某种顺序或时序执行，确保彼此之间的操作能够协调一致。同步的目的是保证特定的操作在适当的时机执行，以避免竞争条件和不一致状态。
  2. 互斥问题（Mutual Exclusion）：
    互斥问题是指多个进程或线程在访问共享资源时，必须保证在同一时刻只有一个进程或线程能够访问该资源，避免冲突和不一致。

假设两个线程 A 和 B 都需要访问一个共享的文件资源：

  • 同步：假如 A 必须在 B 完成某个任务后才能开始自己的任务，这时需要同步。
  • 互斥：如果 A 和 B 同时修改文件内容，就需要互斥，确保只有一个线程可以修改文件。

2.9.1 生产者-消费者问题（Producer-Consumer Problem）

生产者-消费者问题描述了两个进程（或线程）之间的协调，一个是生产者，负责生产数据；另一个是消费者，负责消费数据。这个问题的核心是在生产者和消费者之间通过一个缓冲区（Buffer）进行数据传递，生产者和消费者必须正确同步，避免数据丢失或缓冲区溢出。以下是该问题的关键点：

  1. 缓冲区：生产者将生产的数据放入缓冲区，而消费者从缓冲区中取出数据。当缓冲区满时，生产者必须等待，直到消费者消耗了数据；当缓冲区空时，消费者必须等待，直到生产者生产了新数据。

  2. 同步机制：为了避免竞争条件（Race Condition），需要使用同步机制（如信号量、互斥锁或条件变量）来确保生产者和消费者之间的正确协调。例如，信号量（Semaphore）可以控制生产者等待缓冲区有空位，消费者等待缓冲区有数据。

  3. 阻塞和唤醒：生产者和消费者在相应的条件下进行阻塞（等待）和唤醒（通知）。例如，当缓冲区满时，生产者阻塞；当缓冲区有空位时，唤醒生产者。消费者在缓冲区为空时阻塞；当缓冲区有数据时，唤醒消费者。

下面是一个简化的伪代码示例：

// 信号量初始化
semaphore full = 0;        // 表示缓冲区中的数据量
semaphore empty = N;       // 表示缓冲区中的空位数（N为缓冲区大小）
mutex buffer_mutex;        // 互斥锁，保护缓冲区的访问

// 生产者
void producer() {
    while (true) {
        produce_item();            // 生产一个数据项
        wait(empty);               // 等待空位（empty信号量减1）
        wait(buffer_mutex);        // 获取缓冲区互斥锁
        put_item_in_buffer();      // 将数据项放入缓冲区
        signal(buffer_mutex);      // 释放缓冲区互斥锁
        signal(full);              // 通知有新的数据（full信号量加1）
    }
}

// 消费者
void consumer() {
    while (true) {
        wait(full);                // 等待数据（full信号量减1）
        wait(buffer_mutex);        // 获取缓冲区互斥锁
        remove_item_from_buffer(); // 从缓冲区取出数据项
        signal(buffer_mutex);      // 释放缓冲区互斥锁
        signal(empty);             // 通知有新的空位（empty信号量加1）
        consume_item();            // 消费数据项
    }
}

2.9.2 读者-写者问题（Readers-Writers Problem）

读者-写者问题是操作系统中的另一个经典同步问题，涉及多线程的并发控制。它描述了多个线程在共享资源（例如数据库或文件）上执行读和写操作时的协调机制。这个问题的关键在于要确保以下几点：

  1. 读操作和写操作的互斥：多个读者可以同时读取共享资源，但如果有一个写者正在写，则读者必须等待。同样，当有读者在读时，写者也必须等待。

  2. 避免饥饿：即使系统中有多个读者和写者，也要确保每个读者和写者都能最终访问到共享资源，避免某些读者或写者长时间无法获得访问权限。

读者-写者问题的两种常见变体是：

  • 优先读者（Reader-Preference）：当有读者请求时，允许读者先行，写者只有在没有读者时才能进行写操作。这样可能会导致写者饥饿。

  • 优先写者（Writer-Preference）：当有写者请求时，优先允许写者进行写操作，读者在写者完成后才能读取。这有助于避免写者饥饿，但可能会导致读者饥饿。

以下是一个简单的伪代码示例，展示如何通过信号量（Semaphore）和互斥锁（Mutex）实现读者-写者问题的同步机制：

// 信号量和互斥锁初始化
semaphore mutex = 1;   // 保护读者计数器的互斥锁
semaphore wrt = 1;     // 用于写者的信号量
int readcount = 0;     // 记录当前正在读取的读者数量

// 读者
void reader() {
    while (true) {
        wait(mutex);         // 进入临界区，保护readcount
        readcount++;
        if (readcount == 1) {
            wait(wrt);       // 第一个读者阻塞写者
        }
        signal(mutex);       // 退出临界区

        read_data();         // 执行读操作

        wait(mutex);         // 进入临界区
        readcount--;
        if (readcount == 0) {
            signal(wrt);     // 最后一个读者解除写者阻塞
        }
        signal(mutex);       // 退出临界区
    }
}

// 写者
void writer() {
    while (true) {
        wait(wrt);           // 请求写操作
        write_data();        // 执行写操作
        signal(wrt);         // 释放写操作
    }
}

2.9.3 哲学家进餐问题（Dining Philosophers Problem）

哲学家进餐问题用于展示多线程同步和资源共享的挑战。该问题描述了一组哲学家围坐在一张圆桌旁进餐的情景，他们在吃面条时需要使用筷子，但筷子的数量比哲学家少。

场景：有五个哲学家（可以是任意数量）围坐在一张圆桌旁，每个哲学家面前有一个碗和两根筷子。每对相邻的哲学家共享一根筷子，因此总共有五根筷子。

行为：哲学家交替进行思考和吃饭。当哲学家想要吃饭时，他们必须同时拿起左右两边的筷子。如果筷子被其他哲学家使用，则哲学家必须等待。

问题：如何设计一种机制，使得哲学家能够正确地同步使用筷子，避免死锁（即所有哲学家都在等待筷子，最终无人能吃饭）和饥饿（某个哲学家长时间不能吃饭）。

下面是一个简化的伪代码示例，展示如何通过互斥锁（Mutex）和条件变量（Condition Variable）实现哲学家进餐问题的同步机制：

// 互斥锁和条件变量初始化
mutex chopsticks[5]; // 每根筷子一个互斥锁

// 哲学家编号为 0 到 4
void philosopher(int i) {
    while (true) {
        think(); // 哲学家思考
        wait(chopsticks[i]); // 拿起左边的筷子
        wait(chopsticks[(i + 1) % 5]); // 拿起右边的筷子
        eat(); // 哲学家吃面条
        signal(chopsticks[i]); // 放下左边的筷子
        signal(chopsticks[(i + 1) % 5]); // 放下右边的筷子
    }
}

这种简单的方案存在可能的死锁问题，为了避免死锁，可以引入一些改进方法，例如：

  1. 规定顺序：规定所有哲学家必须按照某个顺序（如顺时针）拿筷子，从而避免循环等待。

  2. 允许最多四个哲学家同时拿筷子：限制最多允许四个哲学家同时尝试拿筷子，保证至少有一位哲学家可以吃饭。

  3. 随机背诵策略：引入随机元素，使哲学家在等待过程中进行随机的思考或其他操作，减少发生死锁的概率。

2.10 管程（Monitor）

管程是操作系统中一种用于同步并发进程的高级抽象机制，它为多线程程序提供了一种结构化的方法来管理共享资源的访问。通过管程，可以避免一些常见的并发问题，如死锁和资源竞争。

以下是管程的主要特点和工作原理：

  1. 封装共享资源：管程封装了共享资源（如变量、数据结构等）以及访问这些资源的代码。只有通过调用管程中的方法，才能对共享资源进行访问，这样可以确保对资源的控制。

  2. 互斥访问：管程内部使用互斥锁（Mutex）来确保同一时间只有一个线程能够执行管程中的代码。这种互斥访问机制可以避免多个线程同时访问共享资源时产生的不一致性。

  3. 条件变量：管程中引入了条件变量（Condition Variable）来管理线程的等待和唤醒。线程可以在某个条件不满足时等待，并在条件满足时被唤醒。条件变量通常与互斥锁配合使用，以确保对条件的检查和修改是原子操作。

  4. 简化同步代码：使用管程可以将同步操作封装在管程内，使得并发程序的代码更加简洁和易于维护。这样，开发者不必直接处理低级别的锁和信号量，而是通过调用管程的方法进行同步。

以下是一个简化的伪代码示例，展示如何使用管程来管理共享缓冲区的生产者-消费者问题：

monitor Buffer {
    int buffer[N];         // 共享缓冲区
    int count = 0;         // 当前缓冲区中的数据数量
    condition notFull;     // 缓冲区未满的条件变量
    condition notEmpty;    // 缓冲区未空的条件变量

    // 生产者方法
    void put(int item) {
        if (count == N) {  // 缓冲区满，等待
            wait(notFull);
        }
        buffer[count] = item;
        count++;
        signal(notEmpty);  // 通知消费者缓冲区非空
    }

    // 消费者方法
    int get() {
        if (count == 0) {  // 缓冲区空，等待
            wait(notEmpty);
        }
        int item = buffer[count - 1];
        count--;
        signal(notFull);   // 通知生产者缓冲区未满
        return item;
    }
}

2.11 死锁的产生和处理

死锁（Deadlock） 是操作系统中一种常见的并发问题，它发生在两个或多个进程（或线程）彼此等待对方释放资源，从而导致所有进程都无法继续执行的状态。简单来说，死锁是指一种资源争夺的僵局，进程永远无法获得所需的资源，导致系统停滞。

为了更好地理解死锁，假设有两个进程 $P_1$ 和 $P_2$ ，它们分别需要资源 $R_1$ 和 $R_2$ 来执行任务。以下情况可能导致死锁：

  • 资源保持和等待：进程 $P_1$ 已经持有资源 $R_1$，并请求资源 $R_2$ 但未获得；与此同时，进程 $P_2$ 已经持有资源 $R_2$，并请求资源 $R_1$ 但未获得。

  • 循环等待：由于进程之间互相等待对方释放资源，形成了循环等待链。即 $P_1$ 等待 $P_2$ 释放资源 $R_2$，而 $P_2$ 等待 $P_1$ 释放资源 $R_1$。

以下是一个简单的伪代码示例，展示了两个进程之间如何由于资源请求的顺序导致死锁：

// 假设有两个资源 R1 和 R2，以及两个进程 P1 和 P2

// 进程 P1
void P1() {
    wait(R1);          // 请求资源 R1
    wait(R2);          // 请求资源 R2
    // 执行某些操作
    signal(R2);        // 释放资源 R2
    signal(R1);        // 释放资源 R1
}

// 进程 P2
void P2() {
    wait(R2);          // 请求资源 R2
    wait(R1);          // 请求资源 R1
    // 执行某些操作
    signal(R1);        // 释放资源 R1
    signal(R2);        // 释放资源 R2
}

在这个示例中，进程 P1 先请求资源 R1，然后请求资源 R2；而进程 P2 先请求资源 R2，然后请求资源 R1。如果 P1 已经持有 R1 并且 P2 已经持有 R2，则 P1 会等待 R2，而 P2 会等待 R1，形成一个死锁循环，导致两个进程都无法继续执行。

在理解死锁的时候还要区分其他两个概念：

  1. 饥饿：由于长期得不到想要的资源，某进程无法向前推进的现象。比如：在短进程优先 （SPF）算法中，若有源源不断的短进程到来，则长进程将一直得不到处理机，从而发生长进程“饥饿”
    而发生长进程
  2. 死循环：某进程执行过程中一直跳不出某个循环的现象。有时是因为程序逻辑bug 导致的，有时是
    程序员故意设计的。

2.11.1 死锁产生的条件

死锁的形成通常需要满足以下四个必要条件：

  • 互斥（Mutual Exclusion）：每个资源在一个时刻只能由一个进程使用。

  • 保持并等待（Hold and Wait）：一个进程已经持有一个资源，并且等待其他资源的释放。

  • 不可剥夺（No Preemption）：资源不能被强制从进程中剥夺，必须由持有进程主动释放。

  • 循环等待（Circular Wait）：存在一组进程，每个进程都在等待资源，而这些资源正被这组中的其他进程持有。

所有，可以有一个结论：发生死锁时一定有循环等待，但是发生循环等待时未必死锁（循环等待是死锁的必要不充分条件）

2.11.2 死锁常见问题

问： 什么时候会发生死锁？

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

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

2.11.3 死锁的处理策略

处理死锁通常有有如下3种策略：

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

先讲第1点，预防死锁策略主要是通过破坏死锁产生的四个必要条件中的一个或几个来实现。以下是具体的预防策略：

  1. 破坏互斥条件（Mutual Exclusion）：

这个策略很难完全实现，因为大部分资源都是互斥性的（例如打印机、文件）。但可以尝试将某些资源变为可共享的，例如只读文件可以同时被多个进程访问。这里可以了解一下SPOOLing技术

SPOOLing技术：把独占设备在逻辑上改造成共享设备, 将输出传输到输出进程， 进程端视作完成了输出（打印机）

Spooling技术
  1. 破坏保持并等待条件（Hold and Wait）：

方案一： 进程请求新的资源得不到满足时， 它必须释放所保持的所有资源， 待以后需要时重新申请。

方案二：当某个进程需要的资源被其他进程所占有的时候，可以由操作系统协助，将想要的资源强行剥夺。这种方式一般需要考虑各进程的优先级（比如：剥夺调度方式，就是将处理机资源强行剥夺给优先级更高的进程使用）

该策略的缺点：

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

允许操作系统强制性地从进程中剥夺资源。如果一个进程请求某个资源但被拒绝，操作系统可以强制释放进程已持有的资源，使其他进程可以使用这些资源。

这个策略实现简单，但也有缺点：

  • 有些资源可能需要用很短的时间， 因此如果进程运行期间一直保持， 造成了严重的资源浪费，资源利用率低。
  • 另外，该策略也有可能导致某些进程饥饿。
  1. 破坏循环等待条件（Circular Wait）：

给所有资源定义一个线性顺序，并要求进程按这个顺序请求资源。即进程只能在获得序号较小的资源后，才能请求序号较大的资源。这可以有效避免形成循环等待链。

该策略的缺点：

  • 不方便增加新的设备，因为可能需要重新分配所有的编号。
  • 进程实际使用资源的顺序可能和编号递增顺序不一致，会导致资源浪费。
  • 必须按规定次序申请资源，用户编程麻烦。

现在讲解一下处理死锁的第二种策略，也就是避免死锁。我们引入一个银行家算法的策略。

银行家算法（Banker’s Algorithm） 是由艾兹赫尔·戴克斯特拉（Edsger W. Dijkstra）提出的一种避免死锁的算法，主要用于资源分配系统。它通过模拟银行家为客户分配贷款的过程，判断系统是否会进入不安全状态，从而避免死锁的发生。

以下是银行家算法的基本原理和步骤：

  1. 基本原理：银行家算法假设系统中的每个进程都会声明最大资源需求，并且在实际运行过程中不会超过这个声明。系统在每次资源分配时，都会检查分配后的状态是否安全。如果发现资源分配会导致系统进入不安全状态（即可能发生死锁），则拒绝分配请求。

  2. 关键概念：

    • 最大需求矩阵（Maximum Need Matrix）：表示每个进程可能需要的最大资源数量。

    • 分配矩阵（Allocation Matrix）：表示当前已经分配给每个进程的资源数量。

    • 需求矩阵（Need Matrix）：表示每个进程还需要的资源数量，计算公式为：Need = Maximum - Allocation。

    • 可用资源向量（Available Vector）：表示系统当前可用的资源数量。

  3. 算法步骤：

    • 初始化：根据系统状态，初始化最大需求矩阵、分配矩阵、需求矩阵和可用资源向量。

    • 资源请求：当进程请求资源时，系统会执行以下步骤：

      • 检查请求是否小于等于进程的最大需求（Request ≤ Need）。

      • 检查请求是否小于等于系统的可用资源（Request ≤ Available）。

    • 模拟分配：系统假设满足进程的请求，并更新相应的矩阵和向量：

      • Available = Available - Request

      • Allocation = Allocation + Request

      • Need = Need - Request

  4. 安全性检查：使用安全性算法（Safety Algorithm）检查系统是否处于安全状态。如果系统仍然处于安全状态，则分配请求得到满足；否则，撤销模拟分配，拒绝请求。

示例 ：假设系统有如下资源：

  • 总资源：$[10, 5, 7]$

  • 可用资源：$[3, 3, 2]$

最大需求矩阵：

$$\left[
\begin{matrix}
7 & 5 & 3\\
3 & 2 & 2 \\
9 & 0 & 2 \\
2 & 2 & 2 \\
4 & 3 & 3
\end{matrix}
\right]
$$

分配矩阵：

$$\left[
\begin{matrix}
0 & 1 & 0\\
2 & 0 & 0 \\
3 & 0 & 2 \\
2 & 1 & 1 \\
0 & 0 & 2
\end{matrix}
\right]
$$

需求矩阵（通过最大需求矩阵和分配矩阵计算得到）：

$$\left[
\begin{matrix}
7 & 4 & 3\\
1 & 2 & 2 \\
6 & 0 & 0 \\
0 & 1 & 1 \\
4 & 3 & 1
\end{matrix}
\right]
$$

当一个进程请求资源时，银行家算法会检查系统是否能够在分配资源后保持安全状态，以避免死锁。我们就手动模拟给进程分配资源，然后进程结束收回资源，找到这样一个安全的进程序列的话，那么死锁就可以避免。

银行家算法

现在我们分析处理死锁的第三种策略：死锁的检测和解除

死锁检测

在这个图中的死锁环路形成过程如下：

  1. P3已获得R2资源（绿色实线），同时请求R3资源（红色虚线）
  2. R3已被分配给P4（绿色实线）
  3. P4已获得R3，同时请求R2资源（红色虚线）
  4. R2已被分配给P3（回到第1步）

这形成了一个循环等待：P3等待P4释放R3，而P4等待P3释放R2。由于每个进程都在等待其他进程释放资源，且都不会主动释放自己持有的资源，因此形成了死锁。检测到这种循环等待关系，就意味着检测到了死锁的存在。

我们有如下的死锁的解决办法：

  1. 资源剥夺（Resource Preemption）： 通过强制性剥夺资源，可以打破循环等待链。例如，在图中的死锁情况下，可以选择剥夺 P3 持有的 R2 或剥夺 P4 持有的 R3，然后重新分配这些资源，从而打破死锁。

  2. 终止进程（Process Termination）： 逐一终止进程是比较直接的方法。例如，首先终止 P3，使得 R2 被释放出来，然后 P4 就可以获得 R2，从而打破死锁链。

  3. 资源回收（Resource Reclamation）： 强制进程在某个时间点释放资源（例如通过定时器），可以暂时打破资源占用状态，使得其他进程有机会获得资源。例如，要求 P3 或 P4 在一定时间段内释放资源，从而避免长时间的死锁状态。

3. Memory Management

本章讲解操作系统中的内存管理，主要的重点在虚实地址转换，段页式管理方式，以及页面置换算法。在了解虚实地址转换之前，首先要辨别虚拟地址和物理地址的概念。

在操作系统中，虚拟地址（Virtual Address）和物理地址（Physical Address）是两种不同层级的地址，它们涉及到内存管理的不同方面。理解这两个概念非常重要，因为它们与内存的访问、分配以及操作系统如何管理硬件资源密切相关。

3.1 虚拟地址（Virtual Address）与物理地址（Physical Address）

虚拟地址是由程序（或进程）在运行时所使用的地址。在现代操作系统中，每个进程都认为它有一整块连续的内存空间，这就是所谓的虚拟地址空间（Virtual Address Space）。操作系统通过虚拟内存管理（Virtual Memory Management）来提供这种抽象，使得程序不需要直接操作物理内存地址。

虚拟地址的特点：

  • 独立性（Independence）：每个进程都有独立的虚拟地址空间，彼此之间互不干扰。
  • 抽象性（Abstraction）：程序只能看到虚拟地址，操作系统负责将这些虚拟地址映射到实际的物理内存地址。
  • 安全性（Security）：虚拟地址空间的使用减少了不同进程之间的干扰，增加了系统的安全性。例如，进程无法直接访问其他进程的内存，避免了内存泄漏或数据窃取。

物理地址是计算机硬件（如内存控制器、RAM）直接使用的内存地址，它表示了内存芯片中实际的位置。操作系统将虚拟地址通过一种称为地址映射（Address Mapping）的机制转换为物理地址，从而让 CPU 可以实际访问内存。

物理地址的特点：

  • 实际存在（Real Existence）：物理地址代表的是计算机中的实际内存单元（如 RAM）。
  • 固定性（Fixed Nature）：物理地址通常与硬件布局相关，无法随操作系统的调度变化而变化。

虚拟地址与物理地址的关系：地址映射（Address Mapping）

操作系统通过硬件（通常是内存管理单元，MMU，Memory Management Unit）来实现虚拟地址和物理地址之间的映射。虚拟地址通过页表（Page Table）映射到物理地址。这一过程称为地址转换（Address Translation），它是现代操作系统内存管理的核心。

地址转换的过程：

  1. 分段与分页（Segmentation and Paging）：

    • 分页（Paging）：操作系统将虚拟地址空间分为固定大小的页（Page），每一页会映射到物理内存中的一块区域。页的大小通常为 4 KB、8 KB 或更大。
    • 分段（Segmentation）：虚拟地址空间不仅可以通过分页来管理，还可以通过分段将地址空间分为不同的段（如代码段、数据段、堆栈段等）。

  2. 页表（Page Table）：操作系统通过维护页表来实现虚拟页到物理页的映射。页表记录了虚拟页和物理页之间的对应关系。MMU 会根据虚拟地址中的页号查找页表，从而获取对应的物理页号，完成虚拟地址到物理地址的转换。

  3. TLB（Translation Lookaside Buffer）：为了提高地址转换的效率，操作系统会使用一个硬件缓存（TLB）来存储最近使用的虚拟地址到物理地址的映射。

举个例子： 假设虚拟地址为 0x7fffffff，操作系统通过页表将其映射到物理地址 0x1001ffff，通过这种方式，程序就可以通过虚拟地址访问到实际的内存。

虚拟地址与物理地址的优点：

  • 内存保护（Memory Protection）：虚拟内存使得每个进程只能访问它自己被分配的内存空间，避免了进程间的内存干扰。
  • 进程隔离（Process Isolation）：操作系统能够通过虚拟内存为每个进程提供独立的内存地址空间，防止进程直接访问或修改其他进程的数据。
  • 内存共享（Memory Sharing）：操作系统可以通过映射不同进程的虚拟地址到相同的物理地址，实现进程间共享内存。

最后简单总结一下：

  • 虚拟地址（Virtual Address） 是程序用来访问内存的地址，操作系统通过虚拟内存技术提供给每个进程一个独立的虚拟地址空间。
  • 物理地址（Physical Address） 是实际的内存地址，由硬件使用。
  • 操作系统通过内存管理单元（MMU）和页表（Page Table）将虚拟地址映射到物理地址，从而实现虚拟内存和物理内存之间的映射。

虚拟地址和物理地址的映射机制使得操作系统能够高效、安全地管理内存资源，提供了内存保护、进程隔离以及高效的内存共享等优点。

本章接下来的内容就是深入底层探讨上面的涉及到的内容。

3.2 内存的概念

内存（Memory）是计算机中的一种硬件资源，主要用于存储和快速访问程序和数据。它是计算机系统中非常重要的一部分，负责存放正在运行的程序指令、数据以及操作系统的相关信息。内存主要有两种类型：

  • RAM（随机存取存储器）：用于存储正在运行的程序和数据，是一种易失性存储器，断电后数据会丢失。
  • ROM（只读存储器）：存储系统启动时需要的固件或引导程序，通常是非易失性的。

内存的编址方式有两种主要方式：按字节编址和按字编址。这两种方式的主要区别在于每个地址对应的数据单位的大小不同。

3.2.1 按字节编址（Byte Addressing）

  • 内存地址从 00 开始，每个地址对应一个存储单元：每个内存地址指向 1 字节（8 bit）的数据。
  • 每个存储单元大小为 1 字节：即每个存储单元占用 1 字节（8 bit），1 字节 = 8 bit。
  • 按字节编址：每个地址指向 1 字节。

假设内存的内容如下，每个位置对应一个字节的数据：

地址 数据
00 0x1A
01 0x2B
02 0x3C
03 0x4D
04 0x5E

在这种情况下，每个内存地址对应一个字节（8 bit）的数据。例如：

  • 地址 00 存储的数据为 0x1A
  • 地址 01 存储的数据为 0x2B
  • 地址 02 存储的数据为 0x3C

如果某程序需要访问地址 02 的数据，它将直接访问 0x3C。

3.2.2 按字编址（Word Addressing）

  • 内存地址从 00 开始，每个地址对应一个存储单元：每个内存地址指向 1 个字（通常是 16 位或 2 字节）。
  • 每个存储单元大小为 1 个字：即每个存储单元占用 16 位（2 字节），1 字 = 16 bit。
  • 按字编址：每个地址指向 1 个字。

假设内存的内容如下，每个位置对应一个字（通常是 16 位或 2 字节）的数据：

地址 数据
00 0x1A2B
01 0x3C4D
02 0x5E6F
03 0x7081
04 0x9ABC

在这种情况下，每个内存地址对应一个字（16 bit 或 2 字节）的数据。例如：

  • 地址 00 存储的数据为 0x1A2B
  • 地址 01 存储的数据为 0x3C4D
  • 地址 02 存储的数据为 0x5E6F

如果某程序需要访问地址 01 的数据，它将直接访问 0x3C4D。

3.2.3. 按字节编址与按字编址的区别

特性 按字节编址（Byte Addressing） 按字编址（Word Addressing）
存储单元大小 每个存储单元为 1 字节（8 bit） 每个存储单元为 1 个字（16 bit 或 2 字节）
地址步进 每个内存地址指向 1 字节 每个内存地址指向 1 个字
内存访问单位 字节（Byte） 字（Word）
示例 地址 00 存储 1 字节，地址 01 存储 1 字节 地址 00 存储 1 个字（16 bit），地址 01 存储下一个字（16 bit）
常见应用 现代计算机普遍采用（如 32 位系统、64 位系统） 较早或特定的计算机系统（如 16 位字长的机器）

总结：

  • 按字节编址（Byte Addressing）：每个内存地址对应 1 字节（8 bit），常用于现代计算机系统。
  • 按字编址（Word Addressing）：每个内存地址对应 1 个字（16 bit 或 2 字节），通常出现在字长为 16 位的计算机系统中。

这些编址方式对计算机的内存管理和程序的内存访问模式有重要影响。在字节编址中，内存的访问单位较小，适合处理各种小规模的数据。而在字编址中，内存访问通常更高效，特别是在处理需要 16 位宽度的数据时。

3.3 连续内存分配（Contiguous Memory Allocation）

“连续内存分配”是操作系统中的一种内存管理方式，它要求程序在执行时必须占用一块连续的内存空间。这种方式通常用于简化内存管理，并提高内存访问的效率。它可以通过将程序所需的内存块按顺序分配，避免了碎片化问题，但也带来了一些局限性。

分段（Segmentation） 在某些情况下可以看作是连续内存分配的一种扩展或优化方法。分段是一种逻辑上的内存划分，它把程序划分为多个不同的段（如代码段、数据段、堆栈段等），每个段是连续的，因此每个段的内存空间在物理内存中是连续的。这样，分段的方式不仅保持了连续内存分配的优点，还能够通过合理划分程序的不同部分，提供更好的内存管理和灵活性。

连续内存分配的主要特点：

  • 连续性：每个进程或程序在内存中的存储空间是连续的，没有分散的碎片。分段也是基于这一理念，虽然程序被分成不同的段，但每个段内部仍然是连续分配的。
  • 简单性：实现比较简单，管理方便。分段虽然比纯粹的连续分配稍微复杂，但它仍然保持了分配连续内存的基本结构，只是对程序进行逻辑上的划分。
  • 内存浪费：由于要求分配的内存是连续的，容易造成内存碎片，从而导致内存利用率降低。分段同样也会面临内存碎片问题，尤其是外部碎片。不过，分段通过划分段的方式（例如代码段、数据段等）减少了内存管理的复杂度。

分配方式：

1.固定分区分配：

  • 内存被划分为若干个固定大小的分区。每个分区只能分配给一个进程。分段和这种方式类似，但分段是将进程划分为多个段，而每个段的大小可以不同。

2.动态分区分配：

  • 内存不预先划分为固定大小的分区，而是根据进程的需求动态分配。通过“首次适应算法”、“最佳适应算法”、“最差适应算法”等来寻找合适的内存块。分段的内存分配方式更灵活，可以根据进程的逻辑结构来动态调整段的大小。
内存分配

连续内存分配产生的内存碎片：

  • 外部碎片（External Fragmentation）：内存中的小块空闲空间，由于这些空间不连续，无法分配给新进程。分段同样可能会产生外部碎片，因为每个段的大小是动态的，释放的段可能导致空闲空间分散，无法为其他进程分配大块连续的内存区域。

  • 内部碎片（Internal Fragmentation）：分配的内存块比进程实际需要的内存大，导致分配的内存块内部存在未使用的空间。分段通常较少产生内部碎片，因为段是按需分配的，但如果段的大小过大，仍然可能存在一定的内部分配浪费。

连续内存分配的优缺点：

  • 优点：简单易实现，适用于内存需求较小、较少变化的系统。分段提供了更细粒度的内存分配，适合管理不同类型的内存需求（如代码、数据和堆栈等）。

  • 缺点：内存利用率较低，容易产生内存碎片，难以适应现代操作系统的需求。分段虽能够通过合理划分程序的不同部分来减少碎片，但仍然可能面临外部碎片问题，需要采取紧凑化（Compaction）等技术来缓解。

内存碎片

内存碎片：

  • 紧凑（Compaction）：紧凑是一种用于解决外部碎片问题的技术。它的基本思想是将内存中的所有进程移动到内存的一端，使得所有的空闲分区都集中在内存的另一端，从而形成一个大的、连续的空闲分区。这样，就可以满足大的内存请求，从而解决外部碎片问题。然而，紧凑需要移动进程，因此会产生一定的开销。在分段中，紧凑化同样适用于解决外部碎片问题，但由于段的分配是按逻辑划分的，因此紧凑的过程可能更复杂。

总结：
在 连续内存分配 中，程序的内存是按顺序分配的，保证了每个进程的内存空间是连续的。而 分段（Segmentation） 作为连续内存分配的一种扩展，它通过将程序划分为多个逻辑段（如代码段、数据段、堆栈段等），每个段在内存中仍然是连续的。虽然分段可以提供更多的灵活性，但它仍然面临外部碎片的问题，因此需要通过紧凑化等技术来优化内存使用。

3.3.1 动态分区分配算法

动态分区分配算法用于在内存中动态分配空闲区域，特别是在程序执行过程中。与静态分配不同，动态分区分配是根据程序的实际需求（如内存大小）动态调整内存的分配。主要的动态分区分配算法包括 首次适应（First-fit）、最优适应（Best-fit）、最坏适应（Worst-fit） 和 临近适应（Next-fit） 等。

1.首次适应（First-fit）

首次适应算法从内存的开始位置开始查找，寻找第一个足够大的空闲内存块来满足请求。当找到一个合适的空闲块后，立即分配内存。

过程：

  1. 从内存中的第一个空闲块开始查找。
  2. 遍历空闲块，找到第一个可以满足请求的块。
  3. 如果找到合适的空闲块（Free block），则分配内存。

优缺点：

  • 优点：实现简单，查找速度较快。
  • 缺点：可能导致内存碎片（Memory Fragmentation），因为分配的是第一个找到的块，后续的空闲块可能很小。
首次适应算法

2.最优适应（Best-fit）

最优适应算法遍历整个内存，寻找所有能满足请求的空闲块，并选择最小的空闲块进行分配，即选择一个最接近请求大小的块。

过程：

  1. 遍历所有空闲内存块。
  2. 选择一个大小最合适（最小且足够大）的空闲块。
  3. 分配内存。

优缺点：

  • 优点：可以减少剩余空闲内存块的大小，从而减少碎片。
  • 缺点：查找过程较慢，因为需要遍历所有空闲块，效率较低。
最优适应算法

3.最坏适应（Worst-fit）

最坏适应算法选择一个最大的空闲内存块来进行分配。这种方法的假设是，通过选择最大空闲块，可以避免创建过多的小碎片。

过程：

  1. 遍历所有空闲内存块。
  2. 选择最大的空闲块。
  3. 将内存分配给进程。

优缺点：

  • 优点：通过选择最大的空闲块，减少了碎片化的风险。
  • 缺点：可能会导致较大的空闲块被拆分成小块，减少了可用的空间。
最坏适应算法

4.临近适应（Next-fit）

临近适应算法与首次适应算法类似，不同之处在于，临近适应算法在上次分配的位置继续查找空闲块，而不是从内存的开头重新开始查找。

过程：

  1. 从上次分配位置开始查找。
  2. 遍历空闲块，找到第一个足够大的空闲块。
  3. 分配内存。

优缺点：

  • 优点：避免了每次从内存的开头开始查找，查找过程较快。
  • 缺点：仍然可能会出现碎片化，尤其是在内存末尾。
临近适应算法

动态分区分配算法总结

算法 查找空闲块的顺序 优点 缺点
首次适应 从头开始查找 实现简单，查找速度较快 可能产生较多的碎片
最优适应 遍历所有空闲块 减少剩余碎片，内存利用较好 查找速度较慢，可能产生小碎片
最坏适应 遍历所有空闲块 减少小碎片产生，较为稳定 可能浪费大量内存，产生较大碎片
临近适应 从上次分配位置开始查找 查找速度较快，避免从头开始查找 可能导致末尾碎片或不均匀的碎片分布

这些算法都有各自的应用场景和适用范围，在实际系统中，操作系统可能会根据不同的内存需求，选择合适的分配算法，或采用多种算法的组合来平衡内存的分配效率和碎片化问题。

3.3.2 分段寻址（Segmentation Addressing）

在分段管理中，程序的内存被划分为多个逻辑上的段，如代码段、数据段、堆栈段等。每个段在物理内存中都有一个连续的存储空间。分段寻址是通过两个部分来定位内存中的具体位置：

  1. 段基址（Segment Base Address）：每个段在物理内存中的起始地址。
  2. 段内偏移量（Offset）：在该段内的具体位置，相对于该段的起始位置的偏移。

分段寻址过程：
当程序需要访问某个内存位置时，操作系统会将逻辑地址转换为物理地址。逻辑地址由两个部分组成：

  • 段号（Segment Number）：指示需要访问的段。
  • 内偏移量（Offset）：指示在该段内具体的位置。

计算物理地址的公式：物理地址 = 段基址 + 段内偏移量

假设我们有以下段信息，存放在段表 (Segment Table)：

  • 代码段（Code Segment）：基址为1000，长度为500。
  • 数据段（Data Segment）：基址为2000，长度为300。
  • 堆栈段 (Stack Segment)：基址为2500，长度为400。

步骤：

  1. 查找段号：这里是数据段，段号为2。
  2. 获取段基址：数据段的基址是2000。
  3. 获取偏移量：我们需要访问数据段的第150个字节，所以偏移量是150。
  4. 计算物理地址：
物理地址 = 段基址 + 偏移量 = 2000 + 150 = 2150

因此，访问数据段中第150个字节的物理地址是2150。

分段寻址

3.4 分页（Paging）

在操作系统中，分页（Paging）是一种内存管理方案，它将物理内存分割成大小相等的块，称为页帧（Page Frames），而逻辑内存（也就是程序使用的内存）则被划分为相同大小的块，称为页（Pages）。分页的目标是将内存的使用更加高效地管理，减少内存碎片，提高系统的可用性和性能。

3.4.1 分页的基本概念

  1. 页（Page）：页是逻辑内存的基本单位，通常大小为4KB、8KB或更大。操作系统将程序的虚拟内存划分为若干页，每一页在物理内存中都有一个对应的页帧。
  2. 页帧（Page Frame）：页帧是物理内存中的基本单位。每个页帧与一个页一一对应。物理内存被划分成许多页帧，大小与页一致。
  3. 页表（Page Table）：页表是操作系统用来管理页与页帧之间映射关系的数据结构。每个进程都有自己的页表，页表中的每个条目包含一个页帧号（Page Frame Number），指示该逻辑页对应的物理页帧。
  4. 虚拟地址（Virtual Address）：程序使用的地址，是程序在执行时产生的地址，经过分页后可以转换为物理地址。
  5. 物理地址（Physical Address）：实际的硬件内存地址，通过页表映射从虚拟地址转换得到。
  6. 页表项（Page Table Entry, PTE）：页表中的每个条目，通常包含页帧号以及其他控制信息，如有效位（Valid Bit）、访问权限等。

3.4.2 分页地址转换

在分页机制下，程序使用的是虚拟地址空间，而实际的内存地址是物理地址。分页地址转换的基本过程就是通过页表把虚拟地址转为物理地址。

在简单的分页系统中，虚拟地址通常被分为两部分：

  • 页号（Page Number）：虚拟地址的高位部分，用于索引页表，找到虚拟页号对应的物理页帧号。
  • 页内偏移（Offset）：虚拟地址的低位部分，用来表示数据在该页内的偏移位置。
    这种结构适用于简单的分页机制，每个虚拟地址空间的页表只有一级。

举个例子，在按字节编址的存储器中，有32个页面，每页 1KB；内存为 64KB，页号和物理块号对应表如图所示，计算逻辑地址0x0C5D所对应的物理地址

页号 块号
9 5
2 4
3 8

紧接着，0x0C5D转换为二进制：

0000 1100 0101 1101

紧接着，根据页表大小，$1KB = 2^{10}B$，按字节编址，所以页内偏移需要$10\text{bit}$来表示，即为0001011101

因为存储器有32个页面，$32 = 2^5$,所以我们需要$5 \text{bit}$来表示页号,即为00011,虚拟页号对应十进制的3，通过查表，我们对应到物理地址的8号块，对应2进制1000

内存为 $64 \text{KB} = 2^{16}B$,按字节编址，需要$16 \text{bit}$来表示地址,因此需要补充前导0

因此最终的物理地址：

0010 0000 0101 1101    // 对应0x205D

3.4.3 分页机制中的有效位

在分页机制中，操作系统使用页表（page table）来存储虚拟页和物理页框之间的映射关系。每个页表条目（PTE，Page Table Entry）通常包含以下信息：

  1. 物理页框地址：对应虚拟页映射到的物理页框地址。
  2. 有效位（Valid Bit）：指示当前页是否有效，即该虚拟页是否已经映射到物理内存。
  3. 其他控制位：如访问权限位、修改位（dirty bit）、引用位等。

有效位的作用可以通过以下几种情况来解释：

1. 有效位 = 1

  • 表示该页已经映射到物理内存，即虚拟页存在于物理页框中。操作系统可以直接访问该虚拟页对应的物理内存。
  • 如果 CPU 要访问该虚拟页，硬件就会通过页表查找该页对应的物理页框地址，从而实现地址转换。

2. 有效位 = 0

  • 表示该虚拟页尚未映射到物理内存，或者该页映射不合法（例如，页未加载、该页不在物理内存中，或该页是无效的）。如果 CPU 尝试访问该虚拟页，会触发一个页错误（page fault）。
  • 页错误通常会引发操作系统的处理机制（比如页面置换），它可能会从磁盘（例如交换空间或文件系统）加载该页到物理内存中，或者进行其他处理。

分页机制中的其他相关位：

  1. 修改位（脏位，Dirty Bit）：表示该页自从加载到内存后是否被修改过。如果该页被修改过，操作系统可能会在需要将其写回磁盘时进行相应处理。

  2. 访问位（Access Bit）：用于记录页是否被访问过，这对于实现页面置换算法（如最近最少使用算法，LRU）非常重要。

  3. 保护位（Protection Bit）：用于控制该页的访问权限（如只读、可写、可执行等）。

3.5 段页式管理方式（Segmentation with Paging）

段页式管理（Segmentation with Paging） 结合了上述两种方式的优点。具体来说，段页式管理将进程的地址空间首先分为若干段，每个段再进一步划分为若干页。段页式管理的内存地址由两个部分组成：

  • 段号（Segment Number）：指示访问的是哪个段。
  • 页号和页内偏移（Page Number and Offset）：指示访问的是哪个页和页内的具体位置。

步骤

  1. 段表查找：根据段号查找段表，得到该段的基地址和段长。
  2. 页表查找：根据页号查找页表，得到该页的物理地址。
  3. 物理地址计算：将物理页框基地址与页内偏移合并，得到最终的物理地址。

优点

  • 逻辑清晰与高效利用：既保留了段式存储管理的逻辑单元划分，又利用了分页存储管理的高效内存利用方式。
  • 灵活性高：可以对每个段独立进行保护和管理。
段页式管理方式

段页式地址转换示例，这里假设：

  • 段大小：最大 4KB（$2^{12}$字节）
  • 页大小：1KB（$2^{10}$字节）
  • 每段最多可分4页
  • 逻辑地址结构：3位段号 + 2位页号 + 10位页内偏移

假设逻辑地址：2,1,256（段号2，页号1，偏移256）

段表：

段号 页表基址 段长度
0 12000 2页
1 13000 4页
2 14000 3页
3 15000 1页
4 16000 4页

段2的页表（基址14000）

页号 物理页号
0 20
1 25
2 30

地址转换示例：

  • 逻辑地址：段号=2, 页号=1, 页内偏移=256
  • 段表查找：段号2 → 页表基址14000
  • 页表查找：页号1 → 物理页号25
  • 计算物理地址：25 * 1024 + 256 = 25856

因此逻辑地址2,1,256转换为物理地址25856。

3.6 TLB机制

TLB（Translation Lookaside Buffer） 是一种高速缓存，用于加速虚拟地址到物理地址的转换过程。在现代操作系统中，虚拟内存技术使得程序运行时使用的是虚拟地址，而物理内存使用的是物理地址。每当程序访问内存时，硬件需要将虚拟地址转换为物理地址，这一过程通常由 内存管理单元（MMU） 完成。

TLB机制的作用： 由于地址转换的过程可能涉及多次查找页表，而页表可能非常大，查找过程会比较慢。因此，TLB机制通过缓存最近使用的虚拟地址到物理地址的映射关系，来显著提高地址转换的速度。

TLB的工作原理

  1. TLB命中（Hit）：

    • 当CPU生成一个虚拟地址时，MMU会首先检查TLB是否已经缓存了该虚拟地址到物理地址的映射。如果找到映射（称为“TLB命中”），MMU直接返回物理地址，访问内存。

  2. TLB未命中（Miss）：

    • 如果TLB中没有找到相应的映射（称为“TLB未命中”），MMU会访问页表，查找虚拟地址对应的物理地址，并将该映射加载到TLB中，以便下次访问时加速转换过程。

  3. 替换策略：

    • 当TLB已满且需要缓存新的映射时，硬件会采用一定的替换策略（如LRU，最近最少使用）来选择一个旧的映射项进行替换。
TLB机制

举个例子来加深理解引入TLB之后的地址转换过程

当CPU需要访问内存时，会生成一个逻辑地址（虚拟地址）。MMU（内存管理单元）需要将该虚拟地址转换为物理地址。转换过程的第一步是检查TLB。

TLB是一个小型的、高速缓存，用于存储最近访问的虚拟地址到物理地址的映射。
当虚拟地址生成后，MMU首先使用虚拟页号查找TLB。

如果TLB中存储了虚拟页号对应的物理页框号（即映射），称为TLB命中。
如果命中，TLB直接返回物理页框号，然后将虚拟地址中的页内偏移与该物理页框号结合，形成完整的物理地址。

物理地址 = 物理页框号 + 页内偏移

示例：

假设：

  • 虚拟地址：0x1234 5678
    • 页号（20位）：0x12345
    • 页内偏移（12位）：0x678
  • TLB命中：虚拟页号 0x12345 映射到物理页框 0x78901

则物理地址：

  • 物理地址 = 0x78901 + 0x678
  • 物理地址 = 0x789679

如果在TLB中没有找到对应的映射（即TLB未命中），MMU会执行以下步骤：

  1. 访问页表：MMU会通过访问操作系统维护的页表来查找虚拟页号到物理页框号的映射。页表是一个数据结构，存储虚拟页号与物理页框号之间的关系。

    页表的查找可能会采用多级页表（例如两级、三四级页表），每级页表根据虚拟地址的高位逐级查找。

  2. 更新TLB：一旦页表返回物理页框号，MMU将这个映射加载到TLB中，以便下次访问时可以加速查找。

  3. 生成物理地址：将页表中获取到的物理页框号与虚拟地址中的页内偏移结合，形成最终的物理地址。

物理地址 = 物理页框号 + 页内偏移

示例：

假设：

  • 虚拟地址：0x1234 5678
    • 页号（20位）：0x12345
    • 页内偏移（12位）：0x678
  • TLB未命中：虚拟页号 0x12345 没有映射，需访问页表。
  • 页表查询返回：物理页框号 0x78901

则物理地址：

  • 物理地址 = 0x78901 + 0x678
  • 物理地址 = 0x789679

如果TLB已满，需要替换其中的一个条目。常见的替换策略有：

  • 最佳页面置换算法（Optimal Page Replacement Algorithm）
  • 最近最少使用页面置换算法（Least Recently Used, LRU）
  • 先进先出页面置换算法（First-In-First-Out, FIFO）
  • 时钟页面置换算法（Clock Page Replacement Algorithm）
  • 最不常用页面置换算法（Least Frequently Used, LFU）

最后再简单做一个TLB的总结

TLB的优点 描述
提高性能 由于TLB缓存了常用的虚拟地址到物理地址的映射，能够减少访问页表的次数，从而提高内存访问的速度。
减少延迟 通过快速查找TLB，减少了虚拟地址到物理地址转换的时间，减少了内存访问延迟。
TLB的局限性 描述
缓存命中率受限 TLB的容量通常很小，仅能缓存最近访问的少量地址映射，因此，TLB的命中率可能受到限制。
TLB Miss Penalty 当发生TLB未命中时，访问页表会导致较大的延迟，因此TLB的命中率直接影响系统的性能。

TLB相关的有效内存访问时间计算，就根据概率来进行加权，可以直观理解，这里就不赘述了

3.7 请求调页（Demand Paging）

请求调页是虚拟内存管理的一种机制，指的是：

  • 页面并不是在程序启动时就全部加载到内存，而是只有在程序访问某个页面时，操作系统才会将该页面从磁盘加载到物理内存中。
  • 这种按需加载的方式避免了将整个程序或数据集加载到内存中，从而节省了内存空间。

当程序访问一个尚未加载到内存的页面时，会触发缺页异常（Page Fault）。这时，操作系统会按照以下步骤处理：

  • 缺页异常触发：当进程访问一个不在物理内存中的虚拟页面时，硬件会触发缺页异常。
  • 查找页面的磁盘位置：操作系统查找页表，确定虚拟页面的物理存储位置。如果该页面还未加载到内存中，操作系统会查找存储该页面的磁盘位置，通常是磁盘上的交换空间或文件系统。
  • 从磁盘加载页面：操作系统会将该页面从磁盘加载到物理内存中的一个空闲页框（或通过页面置换腾出空间）。这个页面通常存储在交换空间（swap space）或映射文件中。
  • 更新页表：一旦页面加载到内存中，操作系统会更新页表，将该虚拟页面的映射关系指向新的物理页框。
缺页异常

在这里我们要区分2个重要的概念，分别是缺页（Page Fault）和抖动（Thrashing）

3.7.1 缺页（Page Fault）

缺页是指在虚拟内存管理中，进程尝试访问的页面（虚拟地址空间中的一个块）不在物理内存中，导致操作系统需要处理的事件。

缺页的发生过程：

  1. 进程访问虚拟地址：当进程尝试访问一个虚拟地址时，MMU（内存管理单元）会首先检查该地址是否已经映射到物理内存中的一个页面。
  2. 缺页异常：如果虚拟地址对应的页面不在物理内存中，MMU会触发一个缺页异常（Page Fault）。这是操作系统介入并处理的信号。
  3. 操作系统处理：
    • 操作系统通过查看进程的页表，确认该页面在磁盘上的位置，通常是在交换空间或某个文件中。
    • 操作系统会将该页面从磁盘加载到物理内存中。
    • 如果物理内存已满，操作系统需要使用页面置换算法选择一个页面从内存中换出并写回磁盘，以腾出空间给新的页面。
  4. 恢复程序执行：当页面被加载到内存后，操作系统更新页表，并恢复进程的执行，进程继续访问内存。

缺页的原因：

  • 页面尚未加载：进程访问的页面可能从未加载到内存中。
  • 页面被换出：内存中的页面被操作系统换出到磁盘，以腾出空间给其他页面。
  • 大块数据访问：对于大数据结构或程序，操作系统可能会选择按需加载数据，避免加载整个文件或数据集。

缺页的影响：

  • 缺页会导致内存访问的延迟，因为需要从磁盘加载页面，而磁盘I/O速度远慢于内存。
  • 当缺页频繁发生时，会增加磁盘访问次数，降低系统性能。

缺页的处理策略：

  • 增加物理内存（最直接的办法）
  • 优化程序内存使用
  • 使用页面置换算法
  • 减少并发进程数
  • 使用压缩内存技术
  • 优化内存映射文件的使用
  • 使用合适的磁盘存储和交换空间

3.7.2 抖动（Thrashing）

抖动是指系统由于频繁的页面缺失和页面置换导致的性能急剧下降的现象。抖动通常发生在系统的物理内存不足时，操作系统不停地将页面从内存换出到磁盘，又从磁盘换入新页面，造成大量的磁盘I/O操作，从而使得系统的响应速度极慢，甚至完全停止响应。有的书对抖动也称之为颠簸（Bouncing）。

抖动的发生过程：

  1. 内存不足：系统的物理内存不足以容纳当前运行的所有进程和页面。
  2. 频繁的页面置换：由于内存不足，操作系统不断地将一些页面换出到磁盘，同时又需要加载新的页面。这会导致大量的页面置换操作，频繁的磁盘I/O。
  3. 严重的性能下降：每次页面缺失时，操作系统需要从磁盘加载页面，由于磁盘I/O速度远低于内存，整个过程会非常缓慢。当页面置换频繁发生时，系统的性能会急剧下降，进程的执行几乎停滞。

抖动的症状：

  • CPU利用率低：虽然CPU处于工作状态，但由于大量时间被浪费在页面置换上，CPU的实际工作负载非常低。
  • 高磁盘I/O：系统的磁盘I/O非常高，因为操作系统需要频繁读写磁盘。
  • 响应缓慢：由于缺页和页面置换，进程的响应速度非常慢，甚至可能完全停止。

抖动的原因：

  • 内存过载：系统没有足够的内存来运行当前的程序。当进程需要的内存页数超出了物理内存的容量时，就会频繁发生页面置换。
  • 不合理的页面置换策略：如果页面置换算法选择不当，可能导致过多的页面被频繁换出和换入，从而引发抖动。
  • 大量进程竞争内存：多个进程同时运行并争夺有限的内存资源，也会导致频繁的页面交换。

抖动的解决方法：

  1. 增加物理内存：最直接的方式是增加系统的物理内存容量，从而减少频繁的页面置换。
  2. 优化程序：减少程序的内存使用，尤其是避免大数据结构在内存中的频繁访问。
  3. 改进页面置换算法：选择更合适的页面置换算法，如LRU、时钟算法等，以减少不必要的页面置换。
  4. 减少并发进程数：通过限制同时运行的进程数量，避免多个进程同时占用过多内存。
抖动
注意看，频繁换出换入的页面在闪烁

总结：

  • 缺页是指进程尝试访问的页面不在物理内存中，需要从磁盘加载。
  • 抖动是系统因频繁的页面置换而导致的性能严重下降现象，通常发生在系统内存不足时，频繁的页面缺失和加载导致大量磁盘I/O和系统响应迟缓。

3.8 页面置换算法

页面置换算法是操作系统内存管理中的一个重要机制，用于决定在物理内存已满的情况下，哪一个页面应当被移出内存以腾出空间来加载新的页面。这个过程称为页面置换。页面置换算法的主要目的是提高系统的内存利用效率和整体性能。下面重点讲解一下常见的页面置换算法。

3.8.1 最佳页面置换算法（Optimal Page Replacement Algorithm）

最佳页面置换算法（Optimal Page Replacement Algorithm） 是一种理论上的页面置换算法，它通过预见未来的页面访问模式来做出最优决策，选择在未来最长时间内不会再被访问的页面进行置换。

算法原理：

  • 基本思想：最佳页面置换算法的核心思想是，当内存中的页面已满，操作系统需要选择一个页面将其从内存中移除。该算法通过预测接下来最久不会被访问的页面进行置换，从而最小化缺页率。
  • 理想情况：由于它需要知道未来的页面访问序列，这使得该算法在实际操作系统中无法实现，因为操作系统无法预测未来的页面访问模式。但是，它是评估其他页面置换算法的一个理论基准。

具体操作：

  1. 判断是否缺页：当进程访问某个页面时，操作系统首先检查该页面是否已经在内存中。如果该页面已经在内存中，则继续执行；如果不在内存中，则发生缺页。

  2. 选择页面置换：在内存已满的情况下，操作系统选择一个页面进行置换。最佳页面置换算法选择的是那些在接下来最长时间内不会被访问的页面进行置换。

    • 例如，如果某个页面接下来有很长一段时间不再被访问，而其他页面会在较短时间内被访问到，那么该页面就会被置换。

  3. 更新内存：将被置换的页面从内存中移出，并将新的页面加载到内存中。

优点：

  • 理论最优：最佳页面置换算法在所有页面置换算法中提供了最小的缺页率，因为它总是选择最合适的页面进行置换，最大化内存的利用率。

缺点：

  • 不可实现：实际系统无法预测未来的页面访问顺序，因此无法实现最佳页面置换算法。操作系统只能依赖于当前的页面访问信息做出决策，无法像该算法那样知道未来的访问情况。
  • 计算成本高：如果实现类似的算法，可能需要持续追踪所有页面的未来访问情况，这在实际操作中开销较大。

举个简单的例子：假设有一个内存管理系统，其物理内存有 3 个页框，进程产生的页面访问序列如下：7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2

OPT算法步骤：

  1. 初始状态：页框为空
  2. 访问页面 7：
    • 页面 7 加入内存，[7]
  3. 访问页面 0：
    • 页面 0 加入内存，[7, 0]
  4. 访问页面 1：
    • 页面 1 加入内存，[7, 0, 1]
  5. 访问页面 2（内存已满）：
    • OPT 算法会选择未来最久不使用的页面。此时，7 最久不使用，因此置换掉 7，加入 2，[2, 0, 1]
  6. 访问页面 0：
    • 页面 0 已在内存中，无需置换，[2, 0, 1]
  7. 访问页面 3（内存已满）：
    • OPT 算法选择未来最久不使用的页面。此时，1 最久不使用，因此置换掉 1，加入 3，[2, 0, 3]
  8. 访问页面 0：
    • 页面 0 已在内存中，无需置换，[2, 0, 3]

后面的顺序可以直观理解，这里就不赘述了

最佳页面置换算法在理论上是最优的，但由于实际无法预测未来的页面访问模式，因此无法在实际操作系统中实现,但它为其他页面置换算法（如 LRU 和 FIFO）提供了一个参照标准，帮助我们评估这些算法的性能。

3.8.2 最近最少使用页面置换算法（Least Recently Used, LRU）

LRU 算法选择最近一段时间内最少使用的页面进行置换，基于这样一个假设：最近使用过的页面在未来仍然可能会被使用，而很久没使用的页面将来可能不再使用。

举例说明：假设有一个内存管理系统，其物理内存有 3 个页框，进程产生的页面访问序列如下：7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2

步骤如下：

  1. 初始状态 ：页框为空
  2. 访问页面 7 ：
    • 页面 7 加入内存，[7]
  3. 访问页面 0 ：
    • 页面 0 加入内存，[7, 0]
  4. 访问页面 1 ：
    • 页面 1 加入内存，[7, 0, 1]
  5. 访问页面 2（内存已满）：
    • LRU 算法会选择最近最少使用的页面。此时，7 最近最少使用，因此置换掉 7，加入 2，[2, 0, 1]
  6. 访问页面 0：
    • 页面 0 已在内存中，无需置换，[2, 0, 1]
  7. 访问页面 3（内存已满）：
    • LRU 算法选择最近最少使用的页面。此时，1 最近最少使用，因此置换掉 1，加入 3，[2, 0, 3]
  8. 访问页面 0：
    • 页面 0 已在内存中，无需置换，[2, 0, 3]
  9. 访问页面 4（内存已满）：
    • LRU 算法选择最近最少使用的页面。此时，2 最近最少使用，因此置换掉 2，加入 4，[4, 0, 3]
  10. 访问页面 2（内存已满）：
    • LRU 算法选择最近最少使用的页面。此时，3 最近最少使用，因此置换掉 3，加入 2，[4, 0, 2]
  11. 访问页面 3（内存已满）：
    • LRU 算法选择最近最少使用的页面。此时，0 最近最少使用，因此置换掉 0，加入 3，[4, 3, 2]
  12. 访问页面 0（内存已满）：
    • LRU 算法选择最近最少使用的页面。此时，4 最近最少使用，因此置换掉 4，加入 0，[0, 3, 2]
  13. 访问页面 3：
    • 页面 3 已在内存中，无需置换，[0, 3, 2]
  14. 访问页面 2：
    • 页面 2 已在内存中，无需置换，[0, 3, 2]

通过上述一系列页面访问，LRU 算法有效地将最近最少使用的页面置换出去，优化了内存使用效率。

3.8.3 先进先出页面置换算法（First-In-First-Out, FIFO）

先进先出页面置换算法（FIFO） 是最简单的页面置换算法之一。其基本思想是，当内存已满且需要进行页面置换时，选择最早进入内存的页面进行置换。FIFO 算法的工作方式类似于排队的原理，先到的页面先被移出内存。

  • 基本思路：FIFO 将页面访问序列看作一个队列。每当一个页面被加载到内存时，它会被放到队列的末尾。每当需要置换页面时，操作系统选择队列头部的页面进行置换，即最早进入内存的页面。
  • 页面置换：当进程需要访问一个页面，而该页面不在内存中时，发生缺页。此时操作系统会选择内存中最早加载的页面进行置换。

FIFO算法的工作流程：

  1. 页面访问：进程访问某个页面时，操作系统检查该页面是否已在内存中。如果在内存中，直接访问；如果不在内存中，则发生缺页。
  2. 置换操作：当内存已满时，操作系统根据FIFO算法选择队列头部的页面进行置换，然后将新页面加载到内存中，并将其添加到队列的末尾。

假设有一个内存管理系统，其物理内存有 3 个页框，进程产生的页面访问序列如下：7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2

FIFO算法步骤：

  1. 初始状态：页框为空
  2. 访问页面 7：
    • 页面 7 加入内存，[7]
  3. 访问页面 0：
    • 页面 0 加入内存，[7, 0]
  4. 访问页面 1：
    • 页面 1 加入内存，[7, 0, 1]
  5. 访问页面 2（内存已满）：
    • FIFO 算法会选择最早进入内存的页面。此时，7 最早进入，因此置换掉 7，加入 2，[0, 1, 2]
  6. 访问页面 0：
    • 页面 0 已在内存中，无需置换，[0, 1, 2]
  7. 访问页面 3（内存已满）：
    • FIFO 算法选择最早进入内存的页面。此时，0 最早进入，因此置换掉 0，加入 3，[1, 2, 3]
  8. 访问页面 0：
    • 页面 0 加入内存，替换最早进入的页面 1，[2, 3, 0]
  9. 访问页面 4（内存已满）：
    • FIFO 算法选择最早进入内存的页面。此时，2 最早进入，因此置换掉 2，加入 4，[3, 0, 4]
  10. 访问页面 2（内存已满）：
    • FIFO 算法选择最早进入内存的页面。此时，3 最早进入，因此置换掉 3，加入 2，[0, 4, 2]
  11. 访问页面 3（内存已满）：
    • FIFO 算法选择最早进入内存的页面。此时，0 最早进入，因此置换掉 0，加入 3，[4, 2, 3]
  12. 访问页面 0（内存已满）：
    • FIFO 算法选择最早进入内存的页面。此时，4 最早进入，因此置换掉 4，加入 0，[2, 3, 0]
  13. 访问页面 3：
    • 页面 3 已在内存中，无需置换，[2, 3, 0]
  14. 访问页面 2：
    • 页面 2 已在内存中，无需置换，[2, 3, 0]

通过上述一系列页面访问，FIFO 算法按照进入内存的顺序进行置换，维护了简单的页面管理逻辑。

FIFO算法优点：

  • 简单易懂：FIFO 算法非常简单，易于实现。
  • 实现简单：只需维护一个队列，记录页面的加载顺序。

FIFO算法缺点：

  • 不考虑页面的实际使用频率：FIFO 仅根据页面的加载顺序进行置换，而不考虑页面被访问的频率或最近是否被访问过。因此，它可能会导致页面置换的效率低下。
  • 可能导致“Belady’s Anomaly”：在某些情况下，增加内存的数量反而可能导致缺页率增加，这种现象被称为 Belady’s Anomaly。

Belady现象：当为进程分配的物理块数增大时，缺页次数不减反增。只有FIFO算法发生Belady异常。FIFO实现简单，但不适应，算法性能差

3.8.4 时钟页面置换算法（Clock Page Replacement Algorithm）

时钟页面置换算法是一种改进的最近最少使用（LRU）算法。它通过一个环形缓冲区（类似于时钟）和一个使用位（Use bit）来决定页面的置换。算法的核心思想是对页面进行循环扫描，当发现某个页面的使用位为 0 时，将其置换出去；否则，将其使用位清零，并继续扫描下一个页面。

假设有一个内存管理系统，其物理内存有 4 个页框，进程产生的页面访问序列如下：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

步骤：

  1. 初始状态：页框为空，指针指向第一个页框
  2. 访问页面 1：
    • 页面 1 加入内存，设置使用位为 1，指针指向下一个页框 [1*]
  3. 访问页面 2：
    • 页面 2 加入内存，设置使用位为 1，指针指向下一个页框 [1*, 2*]
  4. 访问页面 3：
    • 页面 3 加入内存，设置使用位为 1，指针指向下一个页框 [1*, 2*, 3*]
  5. 访问页面 4：
    • 页面 4 加入内存，设置使用位为 1，指针指向下一个页框 [1*, 2*, 3*, 4*]
  6. 访问页面 1：
    • 页面 1 已在内存中，设置使用位为 1，指针指向下一个页框 [1*, 2*, 3*, 4*]
  7. 访问页面 2：
    • 页面 2 已在内存中，设置使用位为 1，指针指向下一个页框 [1*, 2*, 3*, 4*]
  8. 访问页面 5（内存已满）：
    • 指针指向页面 1，使用位为 1，将其使用位清零，指针移动
    • 指针指向页面 2，使用位为 1，将其使用位清零，指针移动
    • 指针指向页面 3，使用位为 1，将其使用位清零，指针移动
    • 指针指向页面 4，使用位为 1，将其使用位清零，指针移动
    • 指针指向页面 1，使用位为 0，将其置换为 5，设置使用位为 1，指针移动 [5*, 2, 3, 4]
  9. 访问页面 1：
    • 页面 1 加入内存，置换页面 2，设置使用位为 1，指针移动 [5*, 1*, 3, 4]
  10. 访问页面 2：
    • 页面 2 加入内存，置换页面 3，设置使用位为 1，指针移动 [5*, 1*, 2*, 4]
  11. 访问页面 3：
    • 页面 3 加入内存，置换页面 4，设置使用位为 1，指针移动 [5*, 1*, 2*, 3*]
  12. 访问页面 4：
    • 页面 4 加入内存，置换页面 5，设置使用位为 1，指针移动 [4*, 1*, 2*, 3*]
  13. 访问页面 5：
    • 页面 5 加入内存，置换页面 1，设置使用位为 1，指针移动 [4*, 5*, 2*, 3*]

3.8.5 最不常用页面置换算法（Least Frequently Used, LFU）

最不常用页面置换算法（LFU） 是一种根据页面访问频率进行页面置换的算法。LFU 的核心思想是将最少被访问的页面优先置换出去。即，系统会跟踪每个页面的访问次数，并选择访问次数最少的页面进行置换。

  • 基本思路：LFU 维护一个计数器，用于记录每个页面被访问的频率。每当一个页面被访问时，其访问计数器增加。算法会选择那些访问次数最少的页面进行置换。
  • 页面置换：当内存已满且需要进行页面置换时，LFU 选择访问次数最少的页面。如果多个页面的访问频率相同，则选择其中最久未被访问的页面。

LFU算法的工作流程：

  1. 页面访问：每当一个页面被访问时，操作系统会将该页面的访问频率计数器加 1。
  2. 页面置换：当内存已满时，系统选择访问频率最低的页面进行置换。如果多个页面的访问频率相同，系统将选择最久未被访问的页面进行置换。

假设系统的内存可以存放 3 个页面，且进程的页面访问序列如下：A, B, C, A, B, D, A, B, C, D

初始状态：

  • 内存容量为 3，初始为空。
  • 访问序列：A, B, C, A, B, D, A, B, C, D

按照访问序列进行页面置换

  1. 访问页面 A：加载 A 到内存，访问频率为 1。

    • 内存状态：[A]

  2. 访问页面 B：加载 B 到内存，访问频率为 1。

    • 内存状态：[A, B]

  3. 访问页面 C：加载 C 到内存，访问频率为 1。

    • 内存状态：[A, B, C]

  4. 访问页面 A：A 已经在内存中，访问频率加 1。

    • 内存状态：[A (2), B, C]

  5. 访问页面 B：B 已经在内存中，访问频率加 1。

    • 内存状态：[A (2), B (2), C]

  6. 访问页面 D：内存已满，选择访问频率最低的页面 C 进行置换，加载 D 到内存。

    • 内存状态：[A (2), B (2), D (1)]

  7. 访问页面 A：A 已经在内存中，访问频率加 1。

    • 内存状态：[A (3), B (2), D (1)]

  8. 访问页面 B：B 已经在内存中，访问频率加 1。

    • 内存状态：[A (3), B (3), D (1)]

  9. 访问页面 C：选择访问频率最低的页面 D 进行置换，加载 C 到内存。

    • 内存状态：[A (3), B (3), C (1)]

  10. 访问页面 D：选择访问频率最低的页面 C 进行置换，加载 D 到内存。

    • 内存状态：[A (3), B (3), D (2)]

最终内存状态：

  • 内存状态：[A, B, D]
  • 页面置换序列：[C -> D, C -> D]

LFU算法的优缺点：

优点：

  • 考虑访问频率：LFU 算法通过考虑页面的访问频率，更加合理地选择置换页面，通常可以减少置换不常用的页面，减少缺页率。
  • 适用于长期不变的访问模式：当某些页面频繁访问时，LFU 能够有效保留这些页面，避免频繁置换。

缺点：

  • 需要额外的空间和计算：LFU 需要维护每个页面的访问计数，并且在页面置换时可能需要遍历所有页面来查找访问频率最少的页面，增加了额外的空间和计算开销。
  • 容易受到初始访问模式的影响：如果页面的访问模式变化较大，LFU 可能会将那些短期内访问较少的页面置换出去，导致“页面漂移”问题。

LFU 算法根据页面的访问频率来决定置换哪个页面，优先置换那些访问频率较低的页面。尽管 LFU 能够较好地反映页面的实际访问情况，但它在实现上比较复杂，并且在一些动态变化的访问模式下可能效率较低。

4. File Management

文件的常见属性如下：

  1. 文件名（File Name）

    • 定义：文件名是操作系统用来标识文件的名称，它通常包括文件的主名和扩展名（例如：document.txt）。
    • 特点：在同一目录下，文件名必须唯一，否则会发生冲突。不同操作系统对文件名的长度和字符限制有所不同（例如，Windows不允许使用某些特殊字符，如 *, ?, :, 等）。

  2. 标识符（Identifier）

    • 定义：标识符是操作系统用来唯一标识一个文件的内部名称。它对用户是不可见的。
    • 作用：操作系统通过标识符来区分不同的文件，即使它们的文件名相同。在操作系统内部，每个文件都需要一个独立的标识符，以避免文件冲突或误操作。

  3. 类型（Type）

    • 定义：文件类型指示文件的内容类别或格式（例如，文本文件、图像文件、音频文件等）。
    • 作用：文件类型可以帮助操作系统和用户理解文件的内容，甚至决定如何打开或处理该文件。例如，一个 .txt 文件通常表示纯文本文件，而 .jpg 则表示图像文件。操作系统通过文件扩展名或文件头来判断文件类型。

  4. 位置（Location）

    • 定义：文件位置表示文件在存储设备中的存放路径。
    • 作用：
      • 用户使用的路径：这通常是用户查看和访问文件时所看到的路径，例如 /home/user/documents/file.txt。
      • 操作系统使用的地址：这是文件实际在存储设备（如硬盘）上的物理存放位置。这个信息通常是操作系统内部使用的，用户一般无法直接看到或修改。

  5. 大小（Size）

    • 定义：文件的大小表示文件占用的存储空间量，通常以字节（byte）为单位。
    • 作用：文件大小帮助操作系统了解文件所需的存储空间，并且对用户来说，它是了解文件内容多少的一个重要指标。例如，一个 1MB 的图像文件相较于一个 10KB 的文本文件显然占用了更多的存储空间。

  6. 创建信息、上次修改时间、文件所有者信息（Creation Info, Last Modified Time, File Owner Info）

    • 定义：这些是文件的元数据，记录了文件的创建时间、最后一次修改的时间以及文件的所有者等信息。
    • 作用：
      • 创建信息：记录文件的创建时间，帮助用户或系统追踪文件的生命周期。
      • 上次修改时间：记录文件最后一次被修改的时间，通常用于文件管理和版本控制。
      • 文件所有者信息：记录文件的拥有者和对文件的权限，通常与操作系统的权限管理系统相关，用来决定谁可以访问、修改文件。

  7. 保护信息（Protection Info）

    • 定义：保护信息是文件的访问控制信息，指定哪些用户或程序可以读取、修改或删除文件。
    • 作用：操作系统通常通过权限（如读、写、执行权限）来保护文件，防止未授权的访问或操作。文件的保护信息决定了文件的安全性，确保只有具有适当权限的用户能够进行相关操作。

4.1 文件在外存的存在方式

文件在外存中存在的方式是由操作系统和存储设备的类型（如硬盘、固态硬盘、光盘、磁带等）共同决定的。外存（外部存储）是指计算机系统中的长期存储介质，和内存（RAM）相比，外存具有更大的存储容量，但访问速度较慢。文件在外存中的存储方式涉及文件的组织结构、存储地址分配、数据存储方法等多个方面。以下是文件如何在外存中存储的详细解释：

1.文件的逻辑组织与物理存储

逻辑组织

  • 文件：文件是操作系统管理的基本数据单位，通常由文件名、文件类型、文件内容和元数据（如创建时间、修改时间、权限等）组成。用户通过文件系统对文件进行访问，而不需要关注文件在物理设备上的存储方式。
  • 目录结构：文件在外存中通常通过目录结构进行管理。目录（也叫文件夹）用来组织文件，以便于查找和管理。操作系统通过文件路径来定位文件的位置，路径可以是相对路径或绝对路径。

物理存储

  • 存储介质：外存设备（如硬盘、SSD）提供了文件存储的实际硬件介质。不同的存储设备有不同的存储方式。例如：

    • 硬盘（HDD）存储数据为磁性信号，采用磁头在盘片上移动进行读写。
    • 固态硬盘（SSD）使用闪存芯片存储数据，通过电子信号读写数据。
    • 光盘（CD/DVD）使用激光束读取和写入数据。

    虽然存储介质不同，但大多数情况下文件的存储方式都基于 块（Block） 或 簇（Cluster） 的概念，即文件会被划分成多个小块，分布在存储介质的不同位置。

2.文件在外存中的存储方式

连续存储方式（Contiguous Allocation）

  • 在这种方式下，文件的所有数据块是连续存储的。即文件内容被写入外存时，操作系统会为其分配一段连续的存储空间，确保文件的所有数据都在这段空间内。
  • 优点：读取速度较快，因为文件的数据存储在连续的块中，磁头无需频繁跳转。
  • 缺点：随着文件的增加和删除，外存中的空闲空间可能变得零散，这会导致“外碎片”，并且难以为大型文件分配足够大的连续空间。

链式存储方式（Linked Allocation）

  • 在这种方式下，文件被分成多个数据块，每个数据块都包含一个指向下一个数据块的指针。文件的数据块可以存储在磁盘上的任何位置，操作系统通过指针链接这些数据块。
  • 优点：可以灵活地分配空间，不需要连续的存储块，可以避免外碎片问题。
  • 缺点：由于每个数据块都包含指针，读取时需要多次磁盘寻址，速度相对较慢。

索引存储方式（Indexed Allocation）

  • 在这种方式下，操作系统为每个文件创建一个索引块，该索引块包含指向文件数据块的指针。文件的实际数据块可以存储在磁盘上的任何位置，操作系统通过索引块来查找文件的各个数据块。
  • 优点：提高了查找效率，文件的各个数据块可以非连续存储，避免了外碎片问题。
  • 缺点：需要额外的存储空间来保存索引块，且对于大文件，索引块可能需要多级索引。
文件在外存的存储方式

3.文件系统（File System）

文件系统是操作系统与存储设备之间的桥梁，它定义了文件如何在外存中存储、管理、访问和保护。文件系统负责将逻辑文件映射到物理存储介质上。

常见的文件系统类型

  • FAT（File Allocation Table）：FAT 是一种早期的文件系统，适用于小型存储设备。它采用简单的链式存储方式，通过一个文件分配表记录文件数据块的存储位置。
  • NTFS（New Technology File System）：NTFS 是 Windows 操作系统常用的文件系统，支持更复杂的文件存储方式，如索引存储、文件权限管理、加密等。
  • ext3/ext4：Linux 操作系统常用的文件系统。ext4 是 ext3 的改进版，提供更好的性能、可靠性和更大的文件支持。
  • HFS+：macOS 使用的文件系统，支持元数据和文件权限控制。

文件系统的工作原理

  • 文件分配：操作系统通过文件系统将文件划分成多个数据块，并将这些数据块分配到外存中。不同文件系统可能使用不同的分配策略（如连续分配、链式分配、索引分配等）。
  • 目录管理：文件系统通过目录结构来组织文件。每个文件都有一个唯一的路径，路径帮助操作系统找到文件的位置。目录项通常包含文件名、文件大小、创建时间、修改时间、权限等信息。
  • 文件元数据：文件的元数据（如创建时间、权限等）存储在文件系统的索引节点（inode）或类似结构中。这些元数据有助于文件的管理和访问控制。

4.访问文件

文件一旦存储到外存中，用户或程序就可以通过文件路径访问文件。操作系统通过文件系统将用户的请求转化为磁盘读写操作：

  • 读取文件：操作系统根据文件路径找到文件的索引信息，然后查找文件在外存中的数据块。接着，操作系统读取这些数据块，并将文件内容返回给用户。
  • 写入文件：当文件需要修改时，操作系统会分配新的数据块（如果需要）并将修改后的内容写入外存。同时，文件的元数据（如修改时间）也会被更新。

5.文件的保护与安全

操作系统通过文件系统提供对文件的保护机制，确保文件的安全性和完整性。这些保护措施包括：

  • 权限控制：文件系统通常会为文件设置访问权限（如读、写、执行权限），并为每个用户或用户组设置不同的权限，以限制未授权的访问。
  • 加密与备份：操作系统还可以通过加密技术保护文件的内容，并通过备份机制防止文件丢失或损坏。

4.2 文件管理功能

操作系统向上提供的文件管理功能是通过系统调用来实现的。系统调用是程序与操作系统之间的接口，用户程序通过系统调用请求操作系统执行某些任务，如文件的创建、删除、读写等。以下是每个功能的详细解释：

1.创建文件 (create 系统调用)

功能：

  • create 系统调用用于在文件系统中创建一个新的文件。当用户希望在磁盘或其他外部存储设备上存储数据时，首先需要创建一个文件。

过程：

  • 操作系统首先检查文件名是否有效，以及是否已经存在同名文件。
  • 如果文件名有效且没有同名文件，操作系统会为该文件分配一个唯一的文件标识符，并在文件系统中为文件分配存储空间。
  • 创建文件时，操作系统通常会为该文件生成相关的元数据（如创建时间、权限等）。

返回值：

  • 成功时，返回一个指向新文件的文件描述符（用于后续的读写操作）。
  • 失败时，返回错误代码（如文件已存在、权限不足等）。

2.删除文件 (delete 系统调用)

功能：

  • delete 系统调用用于删除指定的文件。它将文件从文件系统中移除，释放文件所占用的存储空间。

过程：

  • 操作系统首先会检查文件是否存在。如果文件不存在，删除操作将失败。
  • 接着，操作系统会清除文件的目录项，删除与文件相关的元数据。
  • 文件的实际数据块也会被标记为空闲，准备供其他文件使用。
  • 删除文件时，操作系统还会处理可能的文件锁定和权限问题，确保删除操作不会影响正在访问该文件的进程。

返回值：

  • 成功时，文件会被删除，返回成功状态。
  • 失败时，返回错误代码（如文件不存在、权限不足等）。

3.读文件 (read 系统调用)

功能：

  • read 系统调用用于从已经打开的文件中读取数据。进程使用 read 调用将文件中的内容加载到内存中，供程序使用。

过程：

  • 操作系统检查文件是否已经被成功打开。
  • 操作系统会根据文件描述符定位文件的当前读取位置，并从文件中读取指定大小的数据。
  • 读取的数据会存储在用户提供的缓冲区中，供进程使用。
  • 每次读取后，操作系统会更新文件的指针，指向下一个待读取的位置。

返回值：

  • 成功时，返回实际读取的字节数。如果到达文件末尾，返回 0。
  • 失败时，返回错误代码（如文件不存在、权限问题等）。

4.写文件 (write 系统调用)

功能：

  • write 系统调用用于将数据写入到已经打开的文件中。进程通过该调用向文件中存储数据。

过程：

  • 操作系统检查文件是否已经打开并具有写权限。
  • 操作系统根据文件描述符定位文件的当前写入位置，并将数据写入文件。
  • 写入操作可能会涉及到将数据从用户空间传输到内核空间，再由内核空间传输到存储设备（如硬盘）。
  • 操作系统在写入数据后，会更新文件的指针，指向下一个待写入的位置。

返回值：

  • 成功时，返回实际写入的字节数。
  • 失败时，返回错误代码（如磁盘空间不足、权限问题等）。

5.打开文件 (open 系统调用)

功能：

  • open 系统调用用于打开一个现有文件，或者创建一个新文件以供后续读写操作。打开文件时，操作系统会为文件分配一个文件描述符。

过程：

  • 操作系统会检查文件路径和文件名是否有效，并确认文件是否存在。如果文件不存在且请求创建，操作系统会创建新文件。
  • 操作系统会检查文件的访问权限（如读、写、执行等），以确保进程有足够的权限访问该文件。
  • 文件描述符是文件在操作系统中的唯一标识符，打开文件时，操作系统会为文件分配一个文件描述符，并返回给用户进程。
  • 如果成功打开文件，进程可以通过该文件描述符进行后续的读写操作。

返回值：

  • 成功时，返回文件的文件描述符。
  • 失败时，返回错误代码（如文件不存在、权限不足等）。

6.关闭文件 (close 系统调用)

功能：

  • close 系统调用用于关闭一个已经打开的文件，释放文件描述符，使得该文件不再被当前进程使用。

过程：

  • 操作系统检查文件描述符是否有效。如果有效，操作系统会关闭该文件，释放相关的资源。
  • 关闭文件时，操作系统会更新文件的元数据（如最后访问时间），并确保文件的缓冲区数据已经刷新到存储设备中，防止数据丢失。
  • 关闭文件后，文件描述符不再有效，进程无法再通过该描述符进行读写操作。

返回值：

  • 成功时，返回成功状态。
  • 失败时，返回错误代码（如文件描述符无效等）。

4.3 文件控制块(FCB)

操作系统中的 文件控制块（File Control Block，FCB）是操作系统用来管理文件的一种数据结构，它包含了文件的各种信息，支持操作系统对文件的有效管理和访问。每个文件在文件系统中都有一个与之对应的 FCB，当文件被打开时，操作系统会创建一个 FCB 并将其存储在内存中，以便对文件进行操作。

FCB 的主要作用是：

  1. 文件管理：操作系统通过 FCB 来管理文件的存储位置、大小、权限等元数据。
  2. 文件访问：FCB 使得操作系统能够快速、准确地访问文件的相关信息，从而支持对文件的读写操作。
  3. 资源管理：FCB 包含文件的使用信息，帮助操作系统协调对文件的访问，确保文件的安全性和一致性。

FCB 中存储了与文件相关的多种信息，具体包括但不限于以下内容：

  1. 文件名（File Name）：存储文件的名称。文件名用于标识文件，可以是文件的完整路径或仅是文件名。

  2. 文件标识符（File Identifier）：用于唯一标识一个文件。在文件操作中，操作系统通过文件标识符（例如文件描述符）来引用文件。

  3. 文件类型（File Type）：指定文件的类型，例如文本文件、二进制文件、图像文件等。操作系统根据文件类型来决定如何处理文件的内容。

  4. 文件大小（File Size）：文件的当前大小，通常以字节为单位。操作系统根据文件大小来分配空间、管理磁盘存储等。

  5. 文件位置（File Location）：存储文件的数据在磁盘中的位置。操作系统通过这一信息来找到文件的数据块并执行文件的读写操作。可能包含一个或多个数据块的位置信息。

  6. 访问权限（Access Control Information）：包含文件的访问控制信息，指定哪些用户或进程有权读取、写入或执行该文件。常见的权限包括读取权限、写入权限和执行权限。

  7. 文件状态（File Status）：记录文件的当前状态，例如是否被打开、是否被锁定等。操作系统根据文件状态来决定文件的访问和操作。

  8. 文件的创建时间、修改时间和访问时间（Timestamps）：记录文件的创建时间、最后修改时间以及最后访问时间。这些信息对文件的管理、审计和备份等操作非常重要。

  9. 文件的所有者信息（Owner Information）：文件的所有者或创建者的标识。操作系统利用这些信息来实施权限控制和安全性检查。

  10. 文件指针（File Pointer）：文件指针指向文件中当前读取或写入的位置。每次文件读取或写入时，操作系统会更新文件指针的位置，以便下一次操作。

  11. 文件锁定信息（File Locking Information）：用于文件锁定机制中，指示文件是否被某个进程锁定。文件锁定机制可以防止多个进程同时访问同一文件，造成数据冲突或损坏。

文件控制块的工作原理如下：

  1. 文件的创建和打开：

    • 当用户创建或打开一个文件时，操作系统会在内存中为该文件分配一个 FCB。FCB 包含了文件的各种元数据，操作系统会根据 FCB 来管理文件的存储和访问。

  2. 文件的访问：

    • 每当文件被读取或写入时，操作系统会通过 FCB 来获取文件的位置、大小、状态等信息，确保文件操作的正确性和安全性。

  3. 文件的关闭：

    • 当文件操作完成后，操作系统会更新文件的元数据（如修改时间、文件大小等），并释放 FCB。文件控制块在文件关闭时会被销毁。

  4. 文件的删除：

    • 删除文件时，操作系统会首先检查文件的 FCB，然后清除文件的元数据，并释放文件所占用的空间。删除文件的 FCB 通常会从文件控制块表中移除。

文件控制块的具体结构和存储方式会根据不同的文件系统有所不同。例如：

  • FAT（File Allocation Table）文件系统：

    • 在 FAT 文件系统中，文件控制块通常包含一个指向文件分配表的指针。文件分配表记录了文件的数据块位置，因此操作系统可以通过文件控制块快速查找到文件的存储位置。

  • NTFS 文件系统：

    • NTFS 使用称为 “MFT（Master File Table）条目” 的数据结构，每个文件在 MFT 中有一个对应的条目，类似于 FCB。这个条目中保存了文件的各种元数据，包括文件大小、存储位置、权限等。

  • ext3/ext4 文件系统：

    • 在 Linux 的 ext 文件系统中，文件控制块类似于一个 inode（索引节点）。inode 中存储了文件的元数据，但不包括文件名，文件名存储在目录结构中。每个文件都对应一个 inode，操作系统通过 inode 来管理文件的存储。

文件控制块是操作系统中用于管理文件的核心数据结构，它包含了文件的各种元数据，帮助操作系统执行对文件的读取、写入、删除等操作。通过文件控制块，操作系统能够高效地管理文件系统，确保文件的完整性、安全性和一致性。

5. I/O Device Management

I/O（输入/输出）设备管理是操作系统中一个重要的功能模块，它负责管理和调度计算机系统中各种硬件设备的输入和输出操作。I/O 设备管理的主要任务是通过提供统一的接口，使得操作系统和应用程序能够方便、高效地与外部设备进行交互，而不需要直接操控硬件。操作系统通过一组 I/O 控制器（I/O Controllers）和驱动程序（Device Drivers）来实现对硬件设备的控制和管理。

I/O 设备通常分为以下几种类型：

  • 输入设备：如键盘、鼠标、扫描仪、麦克风等。
  • 输出设备：如显示器、打印机、扬声器等。
  • 存储设备：如硬盘、固态硬盘（SSD）、光盘、USB 驱动器等。
  • 网络设备：如网络接口卡（NIC）、无线适配器等。

这些设备通常与计算机的中央处理单元（CPU）之间通过总线连接，操作系统需要负责这些设备的数据传输、缓冲区管理、设备调度等。

I/O 设备管理的核心任务是提供一个抽象层，使得应用程序可以透明地访问不同类型的 I/O 设备。具体包括以下几个方面：

2.1 I/O 调度（I/O Scheduling）

I/O 调度是操作系统负责安排和管理对 I/O 设备的访问。I/O 调度的目标是优化 I/O 操作，提高系统的整体性能和响应速度。常见的 I/O 调度算法有：

  • 先来先服务（FCFS，First-Come, First-Served）：按照 I/O 请求的到达顺序进行处理。虽然简单，但可能导致较长的等待时间。
  • 最短寻道时间优先（SSTF，Shortest Seek Time First）：选择离当前磁头位置最近的 I/O 请求，减少磁盘寻道时间。
  • 扫描算法（SCAN）：磁头从一端扫描到另一端，处理所有请求，然后反向扫描。又称电梯算法（Elevator Algorithm）。
  • 循环扫描算法（C-SCAN）：类似 SCAN，但在到达磁盘的一端后，磁头会跳回另一端，而不是反向扫描。

2.2 I/O 操作的抽象（Device Abstraction）

I/O 操作的抽象指的是将具体的硬件操作（如读写硬盘、打印文件等）转化为更高层次的操作接口。操作系统通过设备驱动程序提供一个标准化的接口，允许用户和应用程序在不考虑底层硬件的情况下进行操作。

例如，应用程序请求读取文件时，操作系统会将该请求转化为对硬件设备的读写操作，而不需要程序了解硬盘是如何工作的。这样，操作系统就屏蔽了硬件细节，为程序提供了统一的访问接口。

2.3 I/O 缓冲（Buffering）

I/O 缓冲是操作系统用来提高 I/O 性能的一种技术。缓冲区是一块在内存中的区域，用于暂时存储从 I/O 设备读取的数据或写入 I/O 设备的数据。通过使用缓冲区，操作系统可以在等待 I/O 操作完成的同时执行其他任务，减少设备的空闲时间和等待时间。

  • 输入缓冲（Input Buffering）：当从输入设备（如键盘、网络等）读取数据时，操作系统会先将数据存放在缓冲区，应用程序再从缓冲区读取数据。
  • 输出缓冲（Output Buffering）：操作系统将待写入输出设备的数据先放到缓冲区中，然后由设备驱动程序将数据写入实际的设备中。

2.4 I/O 错误处理（Error Handling）

由于硬件设备可能会出现各种故障（如设备未响应、硬件损坏等），操作系统需要具备处理 I/O 错误的能力。常见的错误处理策略包括：

  • 重试机制：在发生 I/O 错误时，操作系统可以重试操作，尝试恢复操作。
  • 错误日志记录：操作系统可以记录发生错误的详细信息，以便后续的调试和维护。
  • 设备替换或恢复：如果某个设备出现故障，操作系统可以尝试切换到备用设备或恢复设备的功能。

2.5 设备驱动程序（Device Drivers）

设备驱动程序是操作系统与硬件设备之间的桥梁。它提供了一个标准化的接口，允许操作系统控制各种硬件设备。设备驱动程序通常是为每个硬件设备单独编写的，负责管理设备的初始化、数据传输、错误处理等。

  • 设备初始化：设备驱动程序负责初始化设备，使设备能够正常工作。
  • 数据传输：设备驱动程序负责从设备读取数据或将数据写入设备。
  • 设备控制：设备驱动程序通过控制命令（如启动、停止、暂停）管理设备的状态。

2.6 I/O 同步与异步（Synchronous vs Asynchronous）

I/O 操作可以是同步的（Synchronous）或异步的（Asynchronous）：

  • 同步 I/O：应用程序会等待 I/O 操作完成后才继续执行后续操作。即，程序执行被阻塞，直到 I/O 操作完成。
  • 异步 I/O：应用程序发起 I/O 操作后，不必等待操作完成，可以继续执行其他任务。操作系统会在 I/O 操作完成时通知应用程序。

操作系统通常通过以下几个机制实现对 I/O 设备的管理：

3.1 I/O 控制器

I/O 控制器（I/O Controllers）是硬件组件，用于管理 I/O 设备和 CPU 之间的通信。它负责将来自 CPU 的 I/O 请求转化为适合设备理解的命令，并将设备的响应转化为 CPU 可理解的格式。

3.2 I/O 总线

I/O 总线（I/O Bus）是连接 CPU、内存和 I/O 设备的通信通道。通过 I/O 总线，操作系统可以控制多个设备，同时传输数据。常见的 I/O 总线包括 PCI（Peripheral Component Interconnect）、SATA（Serial ATA）、USB（Universal Serial Bus）等。

3.3 设备独立性

操作系统提供了设备独立性（Device Independence），使得应用程序可以在不关心底层硬件的情况下进行 I/O 操作。设备独立性由设备驱动程序和操作系统的抽象机制提供。

I/O 设备管理是操作系统中至关重要的组成部分，涉及设备调度、错误处理、数据传输、设备驱动程序等多个方面。操作系统通过设备驱动程序和 I/O 调度算法提供了一个统一的接口，使得应用程序能够高效、可靠地与各种硬件设备进行交互。良好的 I/O 管理不仅可以提高系统性能，还能有效提升用户体验。

最后需要简单补充一下2个常用到的技术。

DMA（Direct Memory Access，直接内存存取） 是一种允许外围设备（如硬盘、网络卡等）直接与内存之间进行数据传输的技术，而无需通过CPU。这种方式可以显著减少CPU的负担，提高系统的整体性能。

DMA工作过程

  1. 初始化：CPU首先向DMA控制器发送命令，指定数据传输的源地址、目的地址和传输的数据量。
  2. 传输过程：DMA控制器接管总线的控制权，并在设备和内存之间直接进行数据传输。这时，CPU可以处理其他任务，不需要参与传输过程。
  3. 传输完成：当数据传输完成后，DMA控制器会向CPU发送中断信号，通知CPU传输已经完成。

DMA优点

  • 提高效率：因为CPU不需要直接参与数据传输，所以可以腾出更多资源来处理其他任务。
  • 减少延迟：直接传输数据，减少了数据传输过程中的延迟。
  • 高效处理大量数据：适用于大规模数据传输，如多媒体文件的读取和写入。

DMA应用场景

  • 多媒体处理：视频、音频等大文件的快速传输。
  • 网络数据传输：如网络适配器中数据包的快速处理。
  • 硬盘数据读取/写入：提升硬盘读写速度。
DMA方式

SPOOLing（Simultaneous Peripheral Operations On-Line）是一种将外围设备的输入/输出操作排队等待执行的技术。它通过将任务临时存储在中间存储设备（如硬盘或内存）中，使CPU和外围设备能够同时处理多个任务，从而提高系统的整体效率。

SPOOLing工作过程

  1. 任务提交：作业被提交到系统中，系统将作业存储在一个临时存储区域（如磁盘）中，这个过程称为任务排队。
  2. 任务排队：系统将多个作业排队等待处理。当外围设备空闲时，系统从队列中取出一个作业进行处理。
  3. 任务执行：外围设备（如打印机、磁带机等）根据排队的顺序依次处理每个作业。处理完成后，系统将作业从队列中移除。

优点

  • 提高资源利用率：通过任务排队和并行处理，提高了系统资源（CPU、外围设备等）的利用率。
  • 减少等待时间：作业可以在外围设备空闲时自动开始处理，减少了用户的等待时间。
  • 高效处理大量任务：适用于需要处理大量I/O操作的场景，如打印作业、磁带备份等。

应用场景

  • 打印作业：多个打印任务被排队等待处理，提高打印机的利用率。
  • 磁带备份：备份任务排队等待磁带机处理，提高备份效率。
  • 批处理作业：适用于需要批量处理的任务，如数据处理、报表生成等。
SPOOLing方式

这里再啰嗦一下SPOOling技术，因为我在很多修考题里面看到了对这个名词的解释的题目

6. Large Capacity Storage Structures

操作系统中的大容量存储结构主要用于持久存储大量数据，确保数据的长期保存和高效访问。常见的大容量存储结构包括以下几种：

1.硬盘（Hard Disk Drive, HDD）：硬盘是最常见的大容量存储设备，广泛应用于计算机中。它通过磁性介质（通常是磁盘盘片）来存储数据，使用磁头进行读写操作。

  • 特点：容量大、成本相对低、读写速度较慢。
  • 存储结构：磁盘被划分为多个磁道（Track）和扇区（Sector），数据以块的形式存储。多个磁道组成一个柱面（Cylinder）。

2.固态硬盘（Solid State Drive, SSD）:SSD是近年来发展迅速的存储设备，它使用闪存（Flash Memory）来存储数据，没有机械部件，因此在性能上优于HDD。

  • 特点：读写速度快、抗震、噪音低、功耗低，但成本较高。
  • 存储结构：SSD没有机械盘片，数据存储在NAND闪存单元中，数据存储结构是基于块（Block）和页面（Page），每个块由多个页面组成。

3.光盘（CD/DVD/Blu-ray）:光盘通过激光读取和写入数据，适用于大容量数据的长期存储和归档。

  • 特点：容量较大、价格便宜、便于携带，但读写速度较慢，且不适用于频繁读写。
  • 存储结构：光盘上的数据通过螺旋轨迹排列，可以按块存储数据。常见的结构包括光盘的扇区，和不同容量的光盘（如CD、DVD、Blu-ray）。

4.磁带（Magnetic Tape）:磁带是较早的存储设备，通常用于大规模数据备份和归档。它通过磁性介质进行数据存储。

  • 特点：存储容量大，成本低，但随机访问速度慢，主要用于长期存储和备份。
  • 存储结构：数据以顺序方式存储在磁带上，采用线性存储结构。通过磁头顺序读取数据，适合用于批量处理和备份。

5.网络附加存储（NAS, Network Attached Storage）:NAS是一种通过网络连接的存储设备，允许多个用户和计算机共享存储资源，常用于文件存储和数据备份。

  • 特点：容量可扩展、支持共享存储、易于管理，但性能依赖网络带宽和设备配置。
  • 存储结构：NAS使用文件系统来组织和管理数据，可以支持多种存储结构，如RAID、LUN（Logical Unit Number）等。

6.存储区域网络（SAN, Storage Area Network）:SAN是一种专门为存储设备提供高速网络连接的架构，主要用于数据中心、企业级存储。

  • 特点：高性能、高可扩展性、支持大容量数据存储和快速访问。
  • 存储结构：SAN一般使用块存储，通常配合RAID技术进行冗余存储。通过高速光纤通道（Fibre Channel）或iSCSI协议连接存储设备和服务器。

7.云存储（Cloud Storage）:云存储指通过互联网将数据存储在远程数据中心的服务，通常由第三方提供，如Amazon S3、Google Drive、OneDrive等。

  • 特点：易于扩展、数据安全性高、可以实现跨平台访问，但依赖于网络连接。
  • 存储结构：云存储通常采用对象存储（如Amazon S3）或块存储（如EBS），并通过网络接口与用户的设备进行交互。

8.闪存卡（Flash Card）:闪存卡是一种基于闪存的存储设备，常见的如SD卡、CF卡等，广泛用于移动设备和相机等设备中。

  • 特点：容量适中、速度较快、便于携带。
  • 存储结构：与SSD类似，闪存卡的数据以块和页面为单位存储。

9.RAM磁盘（RAM Disk）:RAM磁盘是一种使用计算机内存作为虚拟磁盘的技术，通常用于需要极高速访问的临时数据存储。

  • 特点：极高的读写速度，但数据会随着断电丢失。
  • 存储结构：RAM磁盘使用系统内存中的一部分区域来模拟磁盘，数据以块的方式进行存储。

10.分布式存储系统分布式存储是通过多个节点（服务器）共同协作，提供一个虚拟化的存储空间，常用于大规模数据存储和处理，如HDFS（Hadoop分布式文件系统）。

  • 特点：高可扩展性、高容错性、适合大规模数据存储。
  • 存储结构：数据通常分布

6.1 磁盘调度算法

磁盘调度算法是操作系统用来决定磁盘请求的处理顺序的策略，目的是优化磁盘的性能，减少磁头的寻道时间，从而提高系统的整体性能。磁盘的读写操作需要移动磁头到不同的磁道，而磁头的移动时间被称为寻道时间。磁盘调度算法通过合理安排请求的处理顺序，减少磁头的移动，提高磁盘的利用效率。

下面介绍一下常见的磁盘调度算法

6.1 先来先服务（FCFS, First-Come First-Served）

FCFS是最简单的一种磁盘调度算法，磁盘请求按照到达的顺序处理，不进行优化。

  • 原理：按请求到达的顺序处理磁盘请求。
  • 优点：
    • 实现简单，易于理解。
    • 无需额外的计算开销。
  • 缺点：
    • 可能导致磁头来回移动，增加寻道时间，特别是当请求在磁盘的两端时。
    • 寻道时间不确定，效率较低。

6.2 最短寻道时间优先（SSTF, Shortest Seek Time First）

SSTF算法每次选择离当前磁头位置最近的请求进行处理，优先处理距离当前磁头最近的磁道请求。

  • 原理：每次处理最接近当前磁头的请求，从而最小化寻道时间。
  • 优点：
    • 比FCFS更高效，因为它减少了磁头的移动。
  • 缺点：
    • 可能会导致“饥饿”现象，即距离磁头较远的请求可能长时间得不到处理。
    • 无法保证所有请求的公平性。

6.3 扫描算法（SCAN）

SCAN算法也叫电梯算法，它模拟电梯的运动方式，磁头在一个方向上扫描，直到达到磁盘的一端，再反向扫描，处理请求。

  • 原理：磁头沿着磁盘扫描，遇到请求就处理，直到扫描到磁盘的边缘，然后反方向扫描。
  • 优点：
    • 较为平衡，能够避免“饥饿”现象。
    • 磁头的运动有规律，寻道时间较为可控。
  • 缺点：
    • 磁头每次扫描到磁盘的最远端后，再反向扫描，可能导致一端的请求处理得较慢。

6.4 循环扫描算法（C-SCAN）

C-SCAN是对SCAN算法的改进。当磁头扫描到一端后，不返回，而是立即跳到另一端继续扫描。

  • 原理：磁头向一个方向扫描，扫描到达磁盘一端后，迅速跳到另一端继续扫描。每次都从一端扫描到另一端。
  • 优点：
    • 提供了更加均衡的响应时间，避免了SCAN中一端请求较慢的问题。
    • 改进了磁头的移动模式，减少了等待时间。
  • 缺点：
    • 可能会浪费一些时间来跳转磁盘的两端。

6.5 LOOK算法

LOOK算法与SCAN类似，不同之处在于磁头在扫描到达请求的最远端后就会反向，而不是继续扫描到磁盘的最端点。

  • 原理：磁头扫描时，遇到磁盘请求后进行处理，但扫描到最远请求后即返回，而不必扫描到磁盘的最后端。
  • 优点：
    • 更高效，因为它避免了不必要的扫描。
  • 缺点：
    • 与SCAN类似，可能造成某些请求的延迟处理。

6.6 C-LOOK算法

C-LOOK是对LOOK算法的进一步优化。当磁头到达最远请求时，它会跳到最远请求的另一端继续扫描，而不继续扫描到磁盘的末端。

  • 原理：类似于C-SCAN，磁头扫描到一个方向的最远请求后，跳转到另一端继续扫描。
  • 优点：
    • 提供更加均衡的响应时间，并减少了不必要的寻道。
  • 缺点：
    • 在某些场景下，跳转过程可能会引入额外的开销。

6.7 最短请求时间优先（SRTF, Shortest Request Time First）

SRTF算法选择响应时间最短的请求优先处理。这种算法与SSTF类似，不过SRTF更加关注请求的响应时间，而不仅仅是距离。

  • 原理：选择响应时间最短的请求进行处理，类似于CPU调度中的最短剩余时间优先（SRTF）算法。
  • 优点：
    • 可以最大化磁盘请求的响应速度。
  • 缺点：
    • 实现较复杂，可能会增加系统的计算开销。

磁盘调度算法的选择取决于具体的应用场景。不同的算法在不同的情况下有不同的优势和劣势。以下是一些选择考虑因素：

  • FCFS：适合请求到达时间比较均匀、对性能要求不高的场景。
  • SSTF：适用于请求较为密集，磁头位置较为接近的场景，但可能会造成“饥饿”现象。
  • SCAN和C-SCAN：适合请求在磁盘两端不均匀的情况，能够减少磁头的频繁反向运动。
  • LOOK和C-LOOK：比SCAN更加高效，适用于对磁头寻道次数要求较高的环境。

磁盘调度算法的核心目标是减少磁头的移动，优化磁盘访问的效率。每种算法都有其适用的场景，了解每种算法的原理和特点，有助于在不同的实际应用中选择最合适的磁盘调度策略。

7. 偷偷说

我写的第四篇关于计算机修考专业科目的笔记终于结束了，太不容易了。操作系统真的是一门非常非常深奥的学问！我已经尝试写完所有我认为能接触到的知识点了，但我觉得这也仅仅是冰山一角，尽管操作系统这篇的字数已经超过算法，机组，数电的总和，甚至还多出1万字…

在写这篇笔记的时候，我觉得异常异常的乏力！乏力的地方在于我很难把从上层到下层的逻辑串起来。我已经很努力的在梳理整个操作系统的框架了，从最上层的进程开始，再下到我们的存储结构，再下到文件系统，再下到我们的输出设备管理，最后下到大容量存储结构。

操作系统我认为也非常体现能计算机体系的精华，我们可以从上面的内容提取到冗余（redundancy）、并行（parallel）、分而治之提升效率等思想。

我在第一次学习操作系统的时候，纯纯的就是在背概念和记题型，并没有深刻体会到操作系统的内涵。现在当我重新串一遍操作系统的知识时，我又有了很多更深入的理解。

催更｜辅导｜私塾兼职｜联系偷偷：LifeGoesOn_Rio

专业科目笔记
#修考 #Computer Architecture
Operating System
http://toutou.zeabur.app/2024/12/11/Operation-System/
Author
toutou
Posted on
December 11, 2024
Licensed under