【学习笔记】计算机操作系统（二）—— 进程的描述与控制

第二章 进程的描述与控制

2.1 前趋图和程序执行

2.1.1 前趋图

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

• 图中的每个结点可用来表示一个进程或程序段，乃至一条语句,

• 结点间的有向边则表示两个结点之间存在的偏序(Partial Order)或前趋关系(Precedence Relation)。

  • P_i -> P_j 或 （P_i, P_j) ∈ -> 表示在P_j开始执行之前P_i必须完成。P_i是P_j的直接前趋，P_j是P_i的直接后继。

• 把没有前趋的结点称为初始结点(Initial Node)

• 把没有后继的结点称为终止结点(Final Node)

• 每个结点还具有一个重量(Weight)，用于表示该结点所含有的程序量或程序的执行时间。

2.1.2 程序顺序执行

通常，一个应用程序由若干个程序段组成，每一个程序段完成特定的功能，它们在执行时，都需要按照某种先后次序顺序执行，仅当前一程序段执行完后，才运行后一程序段。

程序顺序执行时的特征

• 顺序性:指处理机严格地按照程序所规定的顺序执行,即每一操作必须在下一个操作开始之前结束
• 封闭性:指程序在封闭的环境下运行，即程序运行时独占全机资源，资源的状态(除初始状态外)只有本程序才能改变它，程序一旦开始执行，其执行结果不受外界因素影响
• 可再现性:指只要程序执行时的环境和初始条件相同，当程序重复执行时，可获得相同的结果。

2.1.3 程序并发执行

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

程序并发执行时的特征

• 间断性。程序在并发执行时，由于它们共享系统资源，以及为完成同一项任务而相互合作，致使在这些并发执行的程序之间形成了相互制约的关系。

  例如：I、C和P是三个相互合作的程序，当计算程序完成 C_i-1 的计算后，如果输入程序 I_i 尚未完成数据的输入，则计算程序 C_i 就无法进行数据处理，必须暂停运行。只有当使程序暂停的因素消失后(如I_i已完成数据输入)，计算程序便可恢复执行。
  相互制约将导致并发程序具有“执行–暂停–执行”这种间断性的活动规律。

• 失去封闭性。其中任一程序在运行时，其环境都必然会受到其它程序的影响。

• 不可再现性。计算结果必将与并发程序的执行速度有关。

  例如：有两个循环程序A和B，它们共享一个变量N。

  程序A每执行一次时，都要做N=N+1操作;

  程序B每执行一次时，都要执行Print(N)操作，然后再将N置成“0”。

  假定某时刻变量N的值为n：

  • ① N=N+1在 Print(N)和N=0之前，此时得到的N值分别为n+1,n+1,0。
  • ② N=N+1在 Print(N)和N=0之后，此时得到的N值分别为n,0，1。
  • ③ N=N+1在 Print(N)和N=0之间，此时得到的N值分别为n，n+1，0。

2.2 进程的描述

2.2.1 进程的定义和特征

定义

进程控制块(Process Control Block，PCB)：系统利用 PCB 来描述进程的基本情况和活动过程，进而**控制和管理进程**。

进程实体(又称进程映像)：简称为进程。由程序段【程序的代码(指令序列)】、相关的数据段【运行过程中产生的各种数据(如:程序中定义的变量)】和 PCB【进程描述信息 + 进程控制和管理信息 + 资源分配清单 + 处理机相关信息】 三部分便构成。

PCB 是给操作系统用的；程序段、数据段是给进程自己用的，与进程自身的运行逻辑有关

• 创建进程，实质上是创建进程实体中的PCB;
• 撤消进程，实质上是撤消进程实体中的PCB。

进程：

• 进程是进程实体的运行过程。

• 进程是程序的一次执行。

• 进程是一个程序及其数据在处理机上顺序执行时所发生的活动。

• 进程是具有独立功能的程序在一个数据集合上的运行过程，是系统进行资源分配和调度的一个独立单位。

进程是动态的，进程实体(进程映像)是静态的。

特征

• 动态性。由创建而产生，由调度而执行，由撤消而消亡。—— 进程实体有一定的生命期。

  程序则只是一组有序指令的集合，并存放于某种介质上，其本身并不具有活动的含义，因而是静态的。

  程序: 是静态的。
  进程(Process): 是动态的。
  当进程被创建时，操作系统会为该进程分配一个唯一的、不重复的“身份证号”-- PID(Process lD，进程ID)

• 并发性。是指多个进程实体同存于内存中，且能在一段时间内同时运行。而程序(没有建立PCB)是不能参与并发执行的。

• 独立性。在传统的OS中，独立性是指进程实体是一个能独立运行、独立获得资源和独立接受调度的基本单位。凡未建立PCB的程序都不能作为一个独立的单位参与运行。

• 异步性。是指进程是按异步方式运行的，即按各自独立的、不可预知的速度向前推进。

2.2.2 进程的基本状态及转换

三个基本状态

就绪(Ready)状态

就绪状态：指进程已处于准备好运行的状态，即进程已分配到除 CPU以外的所有必要资源后，只要再获得CPU，便可立即执行。

就绪队列：系统中有许多处于就绪状态的进程，它们按一定的策略(如优先级策略)排成的一个队列

执行(Running)状态

执行状态：进程已获得 CPU，其程序正在执行的状态。

对任何一个时刻而言，在单处理机系统中，只有一个进程处于执行状态，
而在多处理机系统中，则有多个进程处于执行状态。

阻塞(Block)状态

阻塞状态 / 等待状态 / 封锁状态：正在执行的进程由于发生某事件(如等待某种系统资源的分配，或者等待其他进程的响应等)暂时无法继续执行时的状态，即进程的执行受到阻塞。此时引起进程调度，OS把处理机分配给另一个就绪进程，而让受阻进程处于阻塞状态。

阻塞队列：将处于阻塞状态的进程排成一个队列。【根据阻塞原因的不同，会设置多个阻塞队列。】

两个常见状态

创建状态

进程的创建通常包括以下步骤：

• 申请空白 PCB：操作系统为进程分配一个空白 进程控制块（PCB），用于存储进程的管理和控制信息。
• 填写 PCB：向 PCB 中填写进程的基本信息，如进程 ID、优先级、状态、程序计数器、寄存器状态等。
• 分配资源：为该进程分配运行所需的资源，如内存空间、文件描述符、设备等。
• 转入就绪状态：如果资源分配成功，将进程状态设置为 就绪状态，并将其插入就绪队列，等待调度执行。

创建状态：在资源分配过程中，系统无法满足进程的资源需求（例如内存不足），则进程的创建无法完成的状态。【创建状态是为了确保进程的调度只能在创建工作完成后进行，从而保证对 PCB 操作的完整性。】

终止状态

进程的终止可以通过以下几种方式触发【触发之后就进入终止状态，进程不再执行】：

• 自然结束：进程完成其任务，达到程序中的结束点（如 main 函数的返回）。
• 无法克服的错误：进程在执行过程中遇到致命错误（如访问非法内存、除以零等），无法继续运行。
• 操作系统终止：操作系统主动终止进程，例如因为系统资源不足或进程违反系统规则。
• 其他进程终止：具有终止权的进程（如父进程或特权进程）主动终止目标进程。

进程终止通常分为两个步骤：

• 善后处理：进程不再执行，但是操作系统会保留一个记录，其中保存状态码和一些计时统计数据，供其他进程收集。
• 删除进程：将进程的 进程控制块（PCB） 清零，并将空白PCB归还给系统，以便复用。

状态转换

• NULL → 创建：一个新进程产生时，该进程处于创建状态
• 创建状态 → 就绪状态：当其获得了所需的资源以及对其 PCB 的初始化工作完成后，由创建转变为就绪
• 就绪状态 → 执行状态：在调度程序为处于就绪状态的进程分配了处理机之后便可执行，由就绪转变为执行
• 执行状态 → 终止状态：进程主动结束或被动结束（无法克服的错误，操作系统/其他进程终止），由执行转变为终止
• 执行状态 → 就绪状态：正在执行的进程(当前进程)因分配的时间片已用完而被剥夺处理机暂停执行时，由执行转为就绪
• 执行状态 → 阻塞状态：正在执行的进程由于发生某事件暂时无法继续执行时，由执行状态转变为阻塞状态。
• 阻塞状态 → 就绪状态：阻塞的进程所等待的事件已经发生，即进程已分配到除 CPU以外的所有必要资源，由阻塞转变为就绪

进程的组织：链式方式 和 索引方式

2.2.3 挂起操作和进程状态的转换

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

• 如果进程正在执行，它将暂停执行。
• 如果进程正在就绪，则该进程此时暂不接受调度。
• 与挂起操作对应的操作是激活(Active)操作。

引入挂起操作的原因

• 终端用户的需要。终端用户在自己的程序运行期间可以暂停自己的程序的运行，以便研究其执行情况或对程序进行修改。
• 父进程请求。父进程希望挂起自己的某个子进程，以便考查和修改该子进程或者协调各子进程间的活动。
• 负荷调节的需要。当实时系统中的工作负荷较重，已可能影响到对实时任务的控制时，可由系统把一些不重要的进程挂起，以保证系统能正常运行。
• 操作系统的需要。操作系统有时希望挂起某些进程，以便检查运行中的资源使用情况或进行记账。

状态转换进阶版

当进程处于未被挂起的就绪状态时，称此为活动就绪状态 —— 可以接收调度，该进程表示为 Readya。

当进程处于已被 Suspend挂起的就绪状态时，称此为静止就绪状态 —— 不可以被调度，该进程表示为 Readys。

当进程处于未被挂起的阻塞状态时，称它此为活动阻塞状态 —— 该进程表示为 Blockeda。

当进程处于已被 Suspend挂起的阻塞状态时，称此为静止阻塞状态—— 该进程表示为 Blockeds。

• 创建状态 → 活动就绪状态：在当前系统性能和内存容量均允许的情况下，已完成对进程创建的必要操作，由创建转变为活动就绪。
• 创建状态 → 静止就绪状态：考虑到系统当前资源状况和性能的要求，不分配给新建进程所需资源【主要是主存】，而被安置在外存，不参与调度，此时进程创建工作尚未完成，由创建转变为静止就绪。
• 活动就绪 → 静止就绪。活动就绪的进程被Suspend挂起，由活动就绪转变为静止就绪。
• 静止就绪 → 活动就绪。处于静止就绪状态的进程被激活原语 Active 激活后，由静止就绪转变为活动就绪。
• 活动阻塞 → 静止阻塞。活动阻塞的进程被Suspend挂起，由活动阻塞转变为静止阻塞。
• 静止阻塞 → 活动阻塞。处于静止阻塞状态的进程被激活原语 Active 激活后，由静止阻塞转变为活动阻塞。
• 静止阻塞 → 静止就绪。处于静止阻塞状态的进程在其所期待的事件出现后，由静止阻塞变为静止就绪。
• 活动阻塞 → 活动就绪。处于活动阻塞状态的进程在其所期待的事件出现后，由活动阻塞变为活动就绪。

2.2.4 进程管理中的数据结构

操作系统中用于管理控制的数据结构

资源信息表或进程信息表：在计算机系统中，对于每个资源和每个进程都设置了一个数据结构，其中包含了资源或进程的标识、描述、状态等信息以及一批指针。通过这些指针，可以将同类资源或进程的信息表，或者同一进程所占用的资源信息表分类链接成不同的队列，便于操作系统进行查找。

一般分为以下四类:内存表、设备表、文件表 和 用于进程管理的进程表（进程控制块 PCB）

进程控制块 PCB(Process Control Block)

系统是通过 PCB感知进程的存在的。PCB已成为进程存在于系统中的唯一标志。【当系统创建一个新进程时，就为它建立了一个PCB。进程结束时又回收其PCB，进程于是也随之消亡。】用于描述进程的当前情况以及管理进程运行的全部信息。

PCB 的作用是使一个在多道程序环境下不能独立运行的程序(含数据)成为一个能独立运行的基本单位，一个能与其他进程并发执行的进程。PCB作用的具体阐述:

• 作为独立运行基本单位的标志。当一个程序(含数据)配置了 PCB 后，就表示它已是一个能在多道程序环境下独立运行的、合法的基本单位，也具有取得 OS服务的权利。
• 能实现间断性运行方式。
  • 当进程因阻塞而暂停运行时，它必须保留自己运行时的CPU现场信息，再次被调度运行时，还需要恢复其 CPU 现场信息。
  • 在有了PCB 后，系统就可将 CPU 现场信息保存在被中断进程的 PCB 中，供该进程再次被调度执行时恢复 CPU 现场时使用。
• 提供进程管理所需要的信息。
  • 调度程序调度到某进程运行时，只能根据该进程PCB中记录的程序和数据在内存或外存中的始址指针，找到相应的程序和数据;
  • 在进程运行过程中，当需要访问文件系统中的文件或 I/O 设备时，也都需要借助于 PCB 中的信息。
  • 可根据 PCB中的资源清单了解到该进程所需的全部资源等。
• 提供进程调度所需要的信息。
  • 在 PCB中就提供了进程处于何种状态的信息。
  • 其他信息，如进程的优先级、进程的等待时间和已执行的时间等。
• 实现与其它进程的同步与通信。
  • 进程同步机制是用于实现诸进程的协调运行的，在采用信号量机制时，它要求在每个进程中都设置有相应的用于同步的信号量。
  • 在PCB中还具有用于实现进程通信的区域或通信队列指针等。

进程控制块中的信息

• 进程标识符：进程标识符用于唯一地标识一个进程。PID
  • 外部标识符。为了方便用户(进程)对进程的访问。它是由创建者提供的，通常由字母、数字组成。
  • 内部标识符。为了方便系统对进程的使用，每一个进程拥有一个唯一的数字标识符，通常是一个进程的序号。
• 处理机状态 - 处理机的上下文：主要是由处理机的各种寄存器中的内容组成的
  • ①通用寄存器，又称为用户可视寄存器，用户程序可以访问的，用于暂存信息
  • ②指令计数器，其中存放了要访问的下一条指令的地址
  • ③ 程序状态字 PSW，其中含有状态信息，如条件码、执行方式、中断屏蔽标志等
  • ④ 用户栈指针，指每个用户进程都有一个或若干个与之相关的系统栈，用于存放过程和系统调用参数及调用地址。栈指针指向该栈的栈顶。
• 进程调度信息：
  • ①进程状态，指明进程的当前状态
  • ②进程优先级，是用于描述进程使用处理机的优先级别的一个整数，优先级高的进程应优先获得处理机
  • ③进程调度所需的其它信息，与所采用的进程调度算法有关，比如，进程已等待CPU的时间总和、进程已执行的时间总和等
  • ④事件，是指进程由执行状态转变为阻塞状态所等待发生的事件，即阻塞原因。
• 进程控制信息 - 用于进程控制所必须的信息：
  • ①程序和数据的地址，进程实体中的程序和数据的内存或外存地(首)址
  • ②进程同步和通信机制，实现进程同步和进程通信时必需的机制，如消息队列指针、信号量等
  • ③资源清单，在该清单中列出了进程在运行期间所需的全部资源(除CPU 以外), 另外还有一张已分配到该进程的资源的清单
  • ④链接指针，本进程(PCB)所在队列中的下一个进程的 PCB 的首地址。

PCB组织方式

• 线性方式，即将系统中所有的PCB都组织在一张线性表中，将该表的首址存放在内存的一个专用区域中。该方式实现简单、开销小，但每次查找时都需要扫描整张表，因此适合进程数目不多的系统。
• 链接方式，即把具有相同状态进程的 PCB 分别通过 PCB 中的链接字链接成一个队列。可以形成就绪队列、若干个阻塞队列和空白队列等。
  • 就绪队列：往往按进程的优先级将PCB从高到低进行排列，将优先级高的进程PCB排在队列的前面。
  • 阻塞队列：阻塞状态进程的 PCB 根据其阻塞原因的不同，排成多个。
• 索引方式，即系统根据所有进程状态的不同，建立几张索引表。把各索引表在内存的首地址记录在内存的一些专用单元中，在每个索引表的表目中，记录具有相应状态的某个 PCB 在 PCB 表中的地址。

2.3 进程控制

进程控制就是要实现进程状态转换

2.3.1 操作系统内核

OS内核：功能模块安排在紧靠硬件的软件层次中，且常驻内存【一般将OS划分为若干层次,再将OS的不同功能分别设置在不同的层次中】

• 与硬件紧密相关的模块(如中断处理程序等)
• 各种常用设备的驱动程序
• 运行频率较高的模块(如时钟管理、进程调度和许多模块所公用的一些基本操作)

如此安排目的：

• 便于对这些软件进行保护，防止遭受其他应用程序的破坏
• 可以提高 OS 的运行效率。

处理机的执行状态分类: 【将应用程序与 操作系统内核 隔离，防止 OS本身及关键数据(如PCB等)遭受到应用程序有意或无意的破坏。】

• ① 系统态: 又称为管态，也称为内核态。它具有较高的特权，能执行一切指令，访问所有寄存器和存储区，传统的OS都在系统态运行。
• ② 用户态: 又称为目态。具有较低特权的执行状态，仅能执行规定的指令，访问指定的寄存器和存储区。一般情况下，应用程序只能在用户态运行，不能去执行 OS 指令及访问 OS区域，就可以防止应用程序对OS的破坏。

系统态与内核的关系

• 系统态是内核的执行环境：
  • 当 CPU 运行在系统态时，操作系统内核可以访问和控制所有硬件资源，执行所有指令（包括特权指令）。
  • 内核代码运行在系统态，负责管理整个系统的运行。
• 内核是系统态的主体：
  • 操作系统内核是唯一能够在系统态下运行的软件组件。
  • 用户程序无法直接运行在系统态，必须通过内核提供的接口（如系统调用）请求服务。

用户态与应用程序的关系

• 用户态是应用程序的执行环境：
  • 当 CPU 运行在用户态时，应用程序只能执行非特权指令，无法直接访问硬件资源或执行特权操作。
  • 应用程序代码运行在用户态，依赖于操作系统提供的服务。
• 应用程序是用户态的主体：
  • 应用程序是运行在用户态的主要软件组件。
  • 操作系统内核无法直接运行在用户态，但提供了接口（如系统调用、库函数）供应用程序访问系统资源和服务。

OS内核包含的两个功能

• 支撑功能

  • 中断处理

    • 各种类型的系统调用
    • 键盘命令的输入
    • 进程调度
    • 设备驱动等

  • 时钟管理

    • 在时间片轮转调度中，每当时间片用完时，便由时钟管理产生一个中断信号，促使调度程序重新进行调度
    • 在实时系统中的截止时间控制
    • 批处理系统中的最长运行时间控制等

  • 原语操作

    • 原语(Primitive)，就是由若干条指令组成的，用于完成一定功能的一个过程。是“原子操作”。原语在执行过程中不允许被中断。

    • 原子操作(Action Operation)，一个操作中的所有动作是一个不可分割的基本单位，要么全做，要么全不做。原子操作在系统态下执行，常驻内存。

      原子性实现：

      用“关中断指令”和“开中断指令”这两个特权指令实现原子性

      • 正常情况：每执行完一条指令，就需要判断是否有外部中断信号

      • 原子性实现：CPU执行了关中断指令之后，就不再例行检查中断信号，直到执行开中断指令之后才会恢复检查。即关中断、开中断 之间的这些指令序列就是不可被中断的，这就实现了“原子性”。

• 资源管理功能

  • 进程管理。
    • 由于各个功能模块的运行频率较高：进程的调度与分派、进程的创建与撤消等
    • 由于被多种功能模块所需要：用于实现进程同步的原语、常用的进程通信原语等
  • 存储器管理。
    • 用于实现将用户空间的逻辑地址变换为内存空间的物理地址的地址转换机构
    • 内存分配与回收的功能模块
    • 实现内存保护和对换功能的模块等。
  • 设备管理。由于设备管理与硬件(设备)紧密相关，因此其中很大部分也都设置在内核中
    • 各类设备的驱动程序
    • 用于缓和CPU与I/O速度不匹配矛盾的缓冲管理
    • 用于实现设备分配和设备独立性功能的模块等

2.3.2 进程的创建

进程的层次结构

• UNIX

  父进程(Parent Process)：创建进程的进程

  子进程(Progeny Process)：被创建的进程

  孙进程：子进程继续创建的进程

  进程家族(组)：进程与其子孙进程共同组成的

  在PCB中设置了家族关系表项【标识进程之间的家族关系】，标明自己的父进程及所有的子进程。

  • 子进程可以继承父进程所拥有的资源。进程不能拒绝其子进程的继承权。
  • 当子进程被撤消时，应将其从父进程那里获得的资源归还给父进程。
  • 在撤消父进程时，也必须同时撤消其所有的子进程。

• Windows：不存在任何进程层次结构的概念，所有的进程都具有相同的地位。

  • 进程之间的关系不是层次关系，而是获得句柄与否、控制与被控制的简单关系：
    一个进程创建另外的进程时创建进程获得了一个句柄，其作用相当于一个令牌，可以用来控制被创建的进程。这个句柄是可以进行传递的，获得了句柄的进程就拥有控制对应进程的权力。

进程图（Process Graph）：用于描述进程之间关系的一棵有向树

结点：代表进程；有向边：代表进程之间的父子关系；树的根节点：进程家族的祖先（Ancestor）

例子：在进程P_i 创建了进程P_j之后,称P_i是P_j的父进程，P_j是P_i的子进程。

触发进程创建(Creation of Process)的事件:

• 系统内核为用户创建一个新进程:

  • 用户登录。在分时系统中，用户在终端键入登录命令后，若登录成功，系统将为该用户建立一个进程，并把它插入就绪队列中。

  • 作业调度。在多道批处理系统中，当作业调度程序按一定的算法调度到某个(些)作业时，便将它(们)装入内存，为它(们)创建进程，并把它(们)插入就绪队列中。

  • 提供服务。当运行中的用户程序提出某种请求后，系统将专门创建一个进程来提供用户所需要的服务，

• 由用户进程自己创建新进程

  • 应用请求。使新进程以和其创建者进程并发运行的方式完成特定任务

进程创建过程：

系统中在出现了创建新进程的请求后，OS就调用进程创建原语 Creat创建一个新进程:

• 申请空白PC。为新进程申请获得唯一的数字标识符，并从PCB 集合中索取一个空白 PCB。
• 为新进程分配其运行所需的资源，包括各种物理和逻辑资源。这些资源或从操作系统或仅从其父进程获得。
  例如，为新进程的程序和数据以及用户栈分配必要的内存空间时，操作系统必须知道新进程所需内存的大小:
  • 批处理作业，其大小可在用户提出创建进程要求时提供;
  • 应用进程创建子进程，也应是在该进程提出创建进程的请求中给出所需内存的大小;
  • 交互型作业，用户可以不给出内存要求而由系统分配一定的空间
  • 如果新进程要共享某个已在内存的地址空间(即已装入内存的共享段)，则必须建立相应的链接。
• 初始化进程控制块(PCB)。PCB的初始化包括:
  • 初始化标识信息，将系统分配的标识符和父进程标识符填入新PCB中;
  • 初始化处理机状态信息，使程序计数器指向程序的入口地址，使栈指针指向栈顶;
  • 初始化处理机控制信息，将进程的状态设置为就绪状态或静止就绪状态；
    对于优先级，通常是将它设置为最低优先级，除非用户以显式方式提出高优先级要求。
• 如果进程就绪队列能够接纳新进程，便将新进程插入就绪队列。

2.3.3 进程的终止

触发进程终止(Termination of Process)的事件：

• 正常结束，表示进程的任务已经完成，准备退出运行。
  • 在批处理系统中, 可利用Holt指令。
  • 在分时系统中，可利用Logs off指令。
• 异常结束，是指进程在运行时发生了某种异常事件，使程序无法继续运行。常见的异常事件有:
  • 越界错，这是指程序所访问的存储区，已越出该进程的区域;
  • 保护错，指进程试图去访问一个不允许访问的资源或文件，或者以不适当的方式进行访问，例如，进程试图去写一个只读文件；
  • 非法指令，指程序试图去执行一条不存在的指令。出现该错误的原因可能是程序错误地转移到数据区，把数据当成了指令；
  • 特权指令错，指用户进程试图去执行一条只允许 OS执行的指令；
  • 运行超时，指进程的执行时间超过了指定的最大值;
  • 等待超时，指进程等待某事件的时间超过了规定的最大值;
  • 算术运算错，指进程试图去执行一个被禁止的运算，例如，被0除；
  • I/O 故障，这是指在 I/O过程中发生了错误等。
• 外界干预，是指进程应外界的请求而终止运行。这些干预有:
  • 操作员或操作系统干预，指如果系统中发生了某事件，例如，发生了系统死锁；
  • 进程请求，指当子进程已完成父进程所要求的任务时，父进程可以提出请求结束该子进程;
  • 因父进程终止，指当父进程终止时，它的所有子进程也都应当结束。因此，OS在终止父进程的同时，也将它的所有子孙进程终止

进程终止过程：

• 根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态;
• 若被终止进程正处于执行状态，应立即终止该进程的执行(立即剥夺CPU，将CPU分配给其他进程)，并置调度标志为真，用于指示该进程被终止后应重新进行调度;
• 若该进程还有子孙进程，还应将其所有子孙进程也都予以终止，以防它们成为不可控的进程;
• 将被终止进程所拥有的全部资源或者归还给其父进程，或者归还给系统;
• 将被终止进程(PCB)从所在队列(或链表)中移出，等待其它程序来搜集信息。

2.3.4 进程的阻塞与唤醒

触发进程的阻塞与唤醒的事件：

• 向系统请求共享资源失败。进程在向系统请求共享资源时，由于系统已无足够的资源分配给它，此时进程因不能继续运行而转变为阻塞状态。

  例如，一进程请求使用打印机，由于系统已将打印机分配给其它进程，已无可以再可分配的打印机，这时请求者进程只能被阻塞，仅在其它进程释放出打印机时，请求进程才被唤醒。

• 等待某种操作的完成。当进程启动某种操作后，如果该进程必须在该操作完成之后才能继续执行，则应先将该进程阻塞起来，以等待操作完成。

  例如，进程启动了某 I/O设备，如果只有在 I/O 设备完成了指定的 I/O 操作任务后进程才能继续执行，则该进程在启动了 I/O设备后便应自动进入阻塞状态去等待。在I/O操作完成后，再由中断处理程序将该进程唤醒。

• 新数据尚未到达。对于相互合作的进程，如果一个进程需要先获得另一进程提供的数据后才能对该数据进行处理，只要其所需数据尚未到达，进程便只有阻塞。

  例如，有两个进程，进程 A用于输入数据，进程B对输入数据进行加工。假如A尚未将数据输入完毕，则进程 B将因没有所需处理的数据而阻塞;一旦进程A把数据输入完毕，便可去唤醒进程 B。

• 等待新任务的到达。在某些系统中(特别是在网络环境下的OS)，往往设置一些特定的系统进程，每当这种进程完成任务后便把自己阻塞起来，等待新任务的到来。

  例如，在网络环境中的发送进程，其主要任务是发送数据包，若已有的数据包已全部发送完成，而又无新的数据包发送，这时发送进程将把自己阻塞起来;仅当有新的数据包到达时，才将发送进程唤醒。

进程阻塞过程：

• 正在执行的进程，如果发生了触发阻塞事件，进程便通过调用阻塞原语block将自己阻塞。【阻塞是进程自身的一种主动行为。】

• 进入block过程后，由于该进程还处于执行状态，所以应先立即停止执行，把进程控制块中的现行状态由“执行”改为“阻塞”，并将 PCB插入阻塞队列。【如果系统中设置了因不同事件而阻塞的多个阻塞队列，则应将本进程插入到具有相同事件的阻塞队列。】

• 进程上下文切换（Context Switching）- 运行环境信息：保留被阻塞进程的处理机状态，按新进程的PCB中的处理机状态设置CPU 的环境。

  • 保存被阻塞进程的处理机状态：操作系统保存该进程的 执行上下文：包括程序计数器（PC）、寄存器状态、程序状态字（PSW）等关键信息，并将其存储到该进程的 进程控制块PCB中，以便后续恢复执行。
  • 加载新进程的 PCB 设置 CPU 环境：操作系统从就绪队列中选择一个进程进行调度，并将其 PCB 中存储的上下文信息（如程序计数器、寄存器值等）加载到 CPU 中，从而为这个新调度的进程设置执行环境，使其能够继续或开始执行。

• 步骤：

  • 找到要阻塞的进程对应的PCB
  • 保护进程运行现场，将PCB状态信息设置为“阻塞态"，暂时停止进程运行
  • 将PCB插入相应事件的等待队列

进程唤醒过程：

当被阻塞进程所期待的事件发生时，由有关进程(比如提供数据的进程)调用唤醒原语wakeup，将等待该事件的进程唤醒：

• 首先把被阻塞的进程从等待该事件的阻塞队列中找到并移出
• 将其PCB中的现行状态由阻塞改为就绪
• 再将该PCB插入到就绪队列中，等待被调度。

block 原语和wakeup 原语是一对作用刚好相反的原语。在使用它们时，必须成对使用。

2.3.5 进程的挂起与激活

进程挂起过程：

OS将利用挂起原语suspend 将指定进程或处于阻塞状态的进程挂起：

• 首先，检查被挂起进程的状态：
  • 处于活动就绪状态的进程，将其改为静止就绪
  • 处于活动阻塞状态的进程，将其改为静止阻塞;
• 然后，为了方便用户或父进程考查该进程的运行情况，而把该进程的PCB复制到某指定的内存区域。
• 最后，若被挂起的进程正在执行，则转向调度程序从就绪队列中选择另一个合适的进程开始执行

进程激活过程：

OS将利用激活原语active，将指定进程激活。

• 激活原语先将进程从外存调入内存，检查该进程的现行状态：
  • 若是静止就绪，便将之改为活动就绪;
  • 若为静止阻塞，便将之改为活动阻塞。
• 假如采用的是抢占调度策略，则每当有静止就绪进程被激活而插入就绪队列时，将由调度程序将被激活的进程与当前进程两者的优先级进行比较：
  • 如果被激活进程的优先级低，就不必重新调度;
  • 如果被激活进程的优先级高，就需要立即剥夺当前进程的运行，把处理机分配给刚刚被激活的进程。

2.4 进程同步

2.4.1 进程同步的基本概念

进程同步机制的主要任务是：对多个相关进程在执行次序上进行协调，使并发执行的诸进程之间能按照一定的规则(或时序)共享系统资源，并能很好地相互合作，从而使程序的执行具有可再现性。
【多个相互关联的进程同时运行时，需要对它们的执行顺序进行安排和管理，让它们按照一定的规矩（或时间顺序）来使用系统的资源（比如内存、CPU、缓冲区等），并能够很好地配合工作。这样一来，不管程序运行多少次，结果都能保持一致，不会出现混乱或者错误。】

1. 两种形式的制约关系

间接相互制约关系 - 临界资源的互斥访问：

• 定义：多个并发执行的程序因**共享系统资源（如CPU、打印机、磁带机等）**而产生的相互制约关系。
• 特点：
  • 需要对临界资源进行互斥访问，即同一时间只能有一个进程使用。
  • 资源的分配由系统统一管理，进程需先申请资源，不能直接使用。

直接相互制约关系 - 进程间的协作与同步：

• 定义：某些应用程序创建多个进程，这些**进程为完成同一任务而合作，因共享特定资源（如缓冲区）**而产生的相互制约关系。
• 特点：
  • 进程间存在协作关系，如输入进程A向计算进程B提供数据。
  • 当共享资源（如缓冲区）为空或满时，进程会被阻塞，等待对方唤醒。

进程的异步性：

• 定义：进程在运行过程中是否能获得CPU以及运行速度无法由自身控制，受系统调度和制约关系影响。
• 问题：
  • 可能导致对共享变量或数据结构的访问顺序错误。
  • 引发与时间相关的错误，导致进程每次执行结果不一致。
• 解决方法：
  • 使用进程同步机制（如信号量、互斥锁）协调进程执行顺序。
  • 确保进程对资源的访问有序进行。

2. 临界资源(Critical Resouce)

生产者-消费者(producer-consumer) 问题：

生产者进程与消费者进程能并发执行，在两者之间设置了一个具有n个缓冲区的缓冲池，生产者进程将其所生产的产品放入一个缓冲区中；消费者进程可从一个缓冲区中取走产品去消费。

所有的生产者进程和消费者进程都是以异步方式运行的，但它们之间必须保持同步，既不允许消费者进程到一个空缓冲区去取产品，也不允许生产者进程向一个已装满产品且尚未被取走的缓冲区中投放产品。

一个数组 buffer来表示上述的具有n个缓冲区的缓冲池 - 循环缓冲。一个整型变量 counter，其初始值为 0

生产者：每投入一个产品时, 缓冲池 buffer 中暂存产品的数组单元指针 in加1【in=(in+1)%n - 循环缓冲】，counter 加1。

消费者：每取出一个产品时, 缓冲池 buffer 中已取走产品的空闲单元的数组单元指针 out加1【out=(out+1)%n - 循环缓冲】，counter 减1。

当(in+1)%n=out 时表示缓冲池满；而in=out 则表示缓冲池空。

生产者和消费者两进程共享下面的变量:

int in=0, out=0, count=0;
item buffer[n];

生产者：

void producer() {//在生产者进程中使用一局部变量nextp，用于暂时存放每次刚刚生产出来的产品;while(1){produce an item in nextp;...while (counter==n);buffer [in]= nextp;in = (in+1) % n;counter++;}
};

消费者：

void consumer()
{//在消费者进程中，则使用一个局部变量 nextc,用于存放每次要消费的产品。while(1){while (counter==0);nextc=buffer[out];out =(out+1)% n;counter--;consumer the item in nextc;}
};

生产者程序和消费者程序在分别看时都是正确的，而且两者在顺序执行时其结果也会是正确的，但若并发执行时就会出现差错，问题就在于这两个进程共享变量counter。

用机器语言实现时，形式描述：

生产者：

register1=counter；
register1=register1+1;
counter=register1;

消费者：

register2=counter；
register2=register2-1;
counter=register2;

假设:counter的当前值是5。

存在情况一：

register1=counter；(register1=5)
register1=register1+1; (register1=6)
counter=register1; (counter=6)
register2=counter；(register2=6)
register2=register2-1; (register2=5)
counter=register2; (counter=5)

存在情况二：

register1=counter；(register1=5)
register1=register1+1; (register1=6)
register2=counter；(register2=5)
register2=register2-1; (register2=4)
counter=register1; (counter=6)
counter=register2; (counter=4)

解决此问题的关键是应把变量counter 作为临界资源处理，令生产者进程和消费者进程互斥地访问变量counter。

3. 临界区(critical section)

临界区(critical section)：在每个进程中访问临界资源的那段代码

进入区(entry section)：在临界区前面增加一段用于进行检查的代码

• 检查欲访问的临界资源是否正被访问：

  • 如果此刻临界资源未被访问，进程便可进入临界区对该资源进行访问，并设置它正被访问的标志

  • 如果此刻该临界资源正被某进程访问，则本进程不能进入临界区。

退出区(exit section)：将临界区正被访问的标志恢复为未被访问的标志，在临界区后面加上的一段代码

剩余区：除上述进入区、临界区及退出区之外的其它部分的代码

4.同步机制应遵循的规则

实现进程互斥地进入自己的临界区，可用软件方法，更多的是在系统中设置专门的同步机构来协调各进程间的运行。所有同步机制都应遵循下述准则:

• 空闲让进。当无进程处于临界区时，表明临界资源处于空闲状态，应允许一个请求进入临界区的进程立即进入临界区，可有效地利用临界资源。
• 忙则等待。当已有进程进入临界区时，表明临界资源正在被访问，因而其它试图进入临界区的进程必须等待，以保证对临界资源的互斥访问。
• 有限等待。对要求访问临界资源的进程，应保证在有限时间内能进入自己的临界区，以免陷入“死等”状态。
• 让权等待。当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”状态。

2.4.2 硬件同步机制

在对临界区进行管理时，可以将标志看做一个锁。

• 初始时锁是打开的。
• 每个要进入临界区的进程必须先对锁进行测试：
  • 当锁是未打开的时候，则必须等待，直至锁被打开。
  • 当锁是打开的时候，则应立即把其锁上，以阻止其它进程进入临界区。

为防止多个进程同时测试到锁为打开的情况，测试和关锁操作必须是连续的，不允许分开进行。

1. 关中断

关中断是为了在临界区代码执行期间不会被中断打断，从而确保临界区代码的原子性。关中断的具体作用包括：

• 避免进程切换：中断可能导致进程切换（如时钟中断触发调度），关中断可以防止这种情况。
• 防止其他中断干扰：硬件中断（如磁盘IO完成）可能影响临界区代码的执行，关中断可以屏蔽这些中断。

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

关中断的缺点:

• 滥用关中断权力可能导致严重后果
• 关中断时间过长，会影响系统效率，限制了处理器交叉执行程序的能力
• 关中断方法也不适用于多CPU 系统，因为在一个处理器上关中断并不能防止进程在其它处理器上执行相同的临界段代码。

2. 利用 Test-and-Set 指令实现互斥

借助一条硬件指令“测试并建立”指令 TS(Test-and-Set)，该指令是一条原语。

为每个临界资源设置一个全局的布尔变量lock——代表该资源的状态（可把它看成一把锁）：

• lock初值为FALSE，表示该临界资源空闲。
• 进程在进入临界区之前，先用TS指令测试lock：
  • 如果其值为 FALSE，则表示没有进程在临界区内，可以进入。并将lock赋值 TRUE，关闭了临界资源，使任何进程都不能进入临界区；
  • 如果其值为 TRUE，则表示该资源正在被使用。

伪代码：

bool lock = false; // 全局锁变量bool TestAndSet(bool *lock) {bool original_value = *lock; // 1. 测试 lock 的原始值*lock = true;               // 2. 设置 lock 为 truereturn original_value;      // 3. 返回原始值
}void enter_critical_section() {while (TestAndSet(&lock)) { // 忙等待// 如果 lock 为 true，等待}// 进入临界区
}void leave_critical_section() {lock = false; // 释放锁
}

3. 利用 Swap 指令实现进程互斥

Swap指令称为对换指令，在Intel 80x86 中又称为XCHG指令。

• 为每个临界资源设置一个全局的布尔变量lock，用于表示临界区是否被占用。初始时为 FALSE，表示临界区空闲。
• 每个进程在进入临界区前，使用 Swap 指令将局部布尔变量key（ key = TRUE）与 lock 交换。根据交换后的 lock 值判断能否进入临界区。
  • 如果交换后 lock = FALSE，说明临界区空闲，进程可以进入。
  • 如果交换后 lock = TRUE，说明临界区已被占用，进程需要等待。

伪代码：

bool lock = false; // 全局锁变量void Swap(bool *a, bool *b) {bool temp = *a;*a = *b;*b = temp;
}void enter_critical_section() {bool key = true; // 局部变量do {Swap(&key, &lock); // 原子交换 key 和 lock 的值} while (key == true); // 如果 key 为 true，忙等待// 进入临界区
}void leave_critical_section() {lock = false; // 释放锁
}

2.4.3 信号量机制

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

1. 整型信号量 —— P、V操作

整型信号量：一个用于表示资源数目的整型量S(整数)。除初始化外，仅能通过两个标准的原子操作(Atomic Operation)wait(S)和signal(S)来访问。

P 操作（荷兰语 Proberen，意为“测试”）在英文中常被称为 wait

wait(S) {while (S <= 0) {// 阻塞或忙等待}S--; // 申请资源，信号量减 1
}

V 操作（荷兰语 Verhogen，意为“增加”）在英文中常被称为 signal。

signal(S) {S++; // 释放资源，信号量加 1// 唤醒等待该资源的进程
}

wait(S)和 signal(S)是两个原子操作，即它们在执行时是不可中断的。【在一个进程对信号量进行操作的过程中，其他进程不能同时对该信号量进行任何操作。】

存在的问题:不满足“让权等待”原则，会发生“忙等”

• 忙等（Busy Waiting）：线程/进程在等待某个条件（如锁、资源、信号量）时，持续占用 CPU 资源，通过循环反复检查条件是否满足

• 让权等待（Yield Waiting / Blocking Wait）：线程/进程在等待时主动释放 CPU，进入阻塞状态（如睡眠、挂起），让其他线程/进程运行，直到条件满足后再被唤醒。

2. 记录型信号量

整型信号量：在整型信号量机制中的wait 操作，只要是信号量S≤0，就会不断地测试。使进程处于“忙等”的状态。

记录型信号量：采取了“让权等待”策略

增加一个用于代表资源数目的整型变量 value，还增加一个进程链表指针 list（队列），用于存放因信号量不可用而被阻塞的进程。

typedef struct {int value,  //资源数目struct process_control block *list;  //链接等待的进程
}semaphore;

S->value 的初值表示系统中某类资源的数目，因而又称为资源信号量

• 对它的每次 wait 操作，表示进程请求一个单位的该类资源，使系统中可供分配的该类资源数减少一个，因此描述为S->value–;
• 对它的每次 signal 操作，表示执行进程释放一个单位资源，使系统中可供分配的该类资源数增加一个，因此描述为S->value++。

【“让权等待”准则】：

当 S->value < 0时，表示该类资源已分配完毕，因此进程应调用 block 原语进行自我阻塞，放弃处理机，并插入到信号量链表S->list 中。此时 S->value 的绝对值表示在该信号量链表中已阻塞进程的数目。

若signal 操作加1后仍是S-> value ≤ 0，则表示在该信号量链表中仍有等待该资源的进程被阻塞，还应调用wakeup 原语，将S->list 链表中的第一个等待进程唤醒。

如果S->value 的初值为1，表示只允许一个进程访问临界资源，此时的信号量转化为互斥信号量，用于进程互斥。

// 定义信号量的 wait 操作
void wait(semaphore *S) {// 将信号量的值减 1，表示占用一个资源S->value--;              // 如果信号量的值小于 0，表示没有可用资源if (S->value < 0) {      // 将当前进程阻塞，并将其加入到信号量的等待队列中 - block 原语进行自我阻塞(进程从运行态→阻塞态)，主动放弃处理机block(S->list);       }
}// 定义信号量的 signal 操作
void signal(semaphore *S) {// 将信号量的值加 1，表示释放一个资源S->value++;               // 如果信号量的值小于等于 0，表示有进程在等待资源if (S->value <= 0) {      // 从信号量的等待队列中唤醒一个进程 -  wakeup 原语唤醒等待队列中的第一个进程(被唤醒进程从阻塞态→就绪态)wakeup(S->list);     }
}

若考试中出现 P(S)、V(S)的操作，除非特别说明，否则默认s为记录型信号量。

3. AND型信号量

一个进程往往需要获得多个共享资源后方能执行其任务；

AND同步机制的基本思想是: 将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。【对若干个临界资源的分配采取原子操作方式:要么把它所请求的资源全部分配到进程，要么一个也不分配。】从而避免了死锁情况的发生。

死锁：

两个进程A和B，它们都要求访问共享数据（临界资源）D和E，为这两个数据分别设置用于互斥的信号量 Dmutex 和 Emutex，并令它们的初值都是1。相应地，在两个进程中都要包含两个对Dmutex和Emutex的操作：

process A:

wait(Dmutex);
wait(Emutex);

process B:

wait(Emutex);
wait(Dmutex);

若进程A和B按下述次序交替执行wait操作:

process A:wait(Dmutex);   于是Dmutex=0
process B:wait(Emutex);    于是Emutex=0
process A: wait(Emutex);    于是Emutex=-1A阻塞
process B:wait(Dmutex);    于是Dmutex=-1 B阻塞

最后，进程A和B就将处于僵持状态。在无外力作用下，两者都将无法从僵持状态中解脱出来。此时的进程A和B已进入死锁状态

Swait(S1, S2, ..., Sn)
{while (TRUE){if (S1 >= 1 && S2 >= 1 && ... && Sn >= 1){// 所有资源都可用，分配资源for(i = 1; i <= n; i++) Si--;break; // 退出循环，任务继续执行}else{// 有资源不可用，阻塞任务// 将任务加入等待队列，并释放 CPUblock();}}
}Ssignal(S1, S2, ..., Sn)
{for(i = 1; i <= n; i++){Si++; // 释放资源}// 唤醒等待这些资源的所有任务wakeup_all();
}

4. 信号量集

信号量集核心思想：当进程申请某类临界资源时，在每次分配之前，都必须测试资源的数量，判断是否大于可分配的下限值，决定是否予以分配。

信号量S_i的资源分配下限 t_i ; 进程对该资源的需求值为d_i，即表示资源占用量

• 记录型信号量机制：每次只能对某类临界资源进行一个单位的申请或释放。分配下限t_i = 1， 需求值为d_i = 1，进行S_i=S_i - 1操作。

• 信号量集：资源分配下限t_i，要求S_i ≥ t_i，否则不予分配。进程对该资源的需求值为d_i，进行S_i=S_i - d_i操作。

信号量对应的Swait 和 Ssignal 格式为: Swait(S_i, t_i, d_i, …, S_n, t_n, d_n); Ssignal(S_i, d_i, …, S_n, d_n);

一般“信号量集”还有下面几种特殊情况:

• Swait(S,d,d)。此时在信号量集中只有一个信号量S，但允许它每次申请d个资源, 当现有资源数少于d时，不予分配。
• Swait(S,1,1)。此时的信号量集已蜕化为一般的记录型信号量(S>1时)或互斥信号量(S =1 时)。
• Swait(S,1,0)。当S≥1时，允许多个进程进入某特定区；当S=0后，将阻止任何进程进入特定区。

2.4.4 信号量的应用

利用信号量实现进程互斥 - 互斥问题，信号量初值为1

互斥信号量mutex - 进入临界区的名额，设其初始值为1。取值范围为(-1,0,1)。

• 当mutex=1时，表示两个进程皆未进入需要互斥的临界区;
• 当mutex=0时,表示有一个进程进入临界区运行,另外一个必须等待，挂入阻塞队列;
• 当mutex=-1时，表示有一个进程正在临界区运行，另外一个进程因等待而阻塞在信号量队列中，需要被当前已在临界区运行的进程退出时唤醒。

注意：wait(mutex)和signal(mutex)必须成对地出现：

• 缺少wait(mutex)将会导致系统混乱，不能保证对临界资源的互斥访问
• 缺少signal(mutex)将会使临界资源永远不被释放，从而使因等待该资源而阻塞的进程不能被唤醒

注意：对不同的临界资源需要设置不同的互斥信号量。

利用信号量实现前趋关系 - 本质是多级同步问题，信号量初值为0

设有两个并发执行的进程P₁和P₂。P₁中有语句S₁;P₂中有语句S₂。希望在S₁执行后再执行S₂。为实现这种前趋关系，只需使进程P₁和 P₂共享一个公用信号量S，并赋予其初值为0，将 signal(S)操作放在语句S1后面，而在S2语句前面插入 wait(S)操作，即

• 在进程P₁中，用S₁; signal(S);
• 在进程P₂中，wait(S); 用 S₂;

由于S被初始化为0,这样,若P₂先执行必定阻塞,只有在进程P₁执行完S₁;signal(S); 操作后使S增为1时，P₂进程方能成功执行语句S₂。

S₁→S₂，S₁→S₃ 的前趋关系, 应分别设置信号量a和b，S₂→S₄，S₂→S₅，S₃→S₆，S₄→S₆和S₅→S₆，设置信号量c，d，e，f，g。

p1() { S1;   signal(a);   signal(b);}
p2() { wait(a);   S2;   signal(c);   signal(d); }
p3() { wait(b);   S3;   signal(e);}
p4() { wait(c);   S4;   signal(f);}
p5() { wait(d);   S5;   signal(g);}
p6() { wait(e);   wait(f);   wait(g);    S6;}

在“前操作”之后执行 V(S)；在“后操作”之前执行 P(S)

2.4.5 管程(Monitors)机制

1. 管程

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

【将某个资源的所有信息（数据结构）以及对资源的操作（比如读、写、修改等）都打包在一起，并且提供了统一的访问方式。】

管程由四部分组成:

管程的组成部分	类的组成部分	详细描述
①管程的名称	类名	标识这个管程是做什么的
②局部于管程的共享数据结构说明	属性（变量）	管程内部的共享变量，类似于类的属性， 用来描述管程管理的资源状态。
③对数据结构进行操作的一组过程	方法	管程提供的操作接口，类似于类的方法/函数， 用来对共享资源进行操作。
④对共享数据设置初始值的语句	构造函数或初始化块	管程创建时对共享数据进行初始化， 类似于类的构造函数或初始化块。

管程的基本特征:

• 局部于管程的数据只能被局部于管程的过程所访问
• 一个进程只有通过调用管程内的过程(管程提供的特定入口)才能进入管程访问共享数据 - 通过管程的过程间接修改管程的数据结构
• 每次仅允许一个进程在管程内执行某个内部过程。- 互斥特性是由编译器负责实现

管程主要有以下特性:

• 模块化，即管程是一个基本程序单位，可以单独编译;
• 抽象数据类型，指管程中不仅有数据，而且有对数据的操作;
• 信息掩蔽，指管程中的数据结构只能被管程中的过程访问，这些过程也是在管程内部定义的，供管程外的进程调用，而管程中的数据结构以及过程(函数)的具体实现外部不可见。

封装

管程将共享资源的数据结构及其操作逻辑封装在内部，外部只能通过管程提供的接口间接访问资源。这种机制隐藏了实现细节，实现了资源的集中管理和安全性。

互斥访问

管程通过同步机制确保同一时间只有一个进程进入管程并操作资源。如果有多个进程想操作资源，管程会让他们排队。进程请求访问时，管程检查资源状态：若资源被占用，则进程等待；若资源空闲，则进程进入。这避免了竞争条件，保证了资源的互斥访问。

管程和进程不同:

区别点	进程	管程
数据结构	定义私有数据结构（如 PCB）	定义公共数据结构（如消息队列）
操作方式	通过顺序程序执行操作数据结构	主要进行同步操作和初始化操作数据结构
目的	实现系统的并发性	解决共享资源的互斥使用问题
工作方式	主动工作方式，通过调用管程中的过程操作共享数据结构	被动工作方式，由进程调用其内部过程
并发性	进程之间能并发执行	管程不能与其调用者并发
生命周期	动态性，由创建而诞生，由撤销而消亡	静态性，作为操作系统的资源管理模块，供进程调用

2. 条件变量

条件变量：主要用于处理在管程内被阻塞或挂起的进程。一个进程被阻塞或挂起的条件(原因)可有多个，因此在管程中设置了多个条件变量，对这些条件变量的访问只能在管程中进行。

• 管程中对每个条件变量都须予以说明，其形式为: condition x,y;

• 对条件变量的操作仅仅是 wait 和 signal，可表示为 x.wait 和 x.signal；

  • x.wait: 正在调用管程的进程因x条件需要被阻塞或挂起，则调用 x.wait , 将自己插入到x条件的等待队列上，并释放管程，直到x条件变化。此时其它进程可以使用该管程。
  • x.signal: 正在调用管程的进程发现x条件发生了变化，则调用 x.signal，重新启动一个因x条件而阻塞或挂起的进程，如果存在多个这样的进程，则选择其中的一个，如果没有，继续执行原进程，而不产生任何结果。

• 每个条件变量保存了一个链表, 用于记录因该条件变量而阻塞的所有进程。

假设有两个进程 P 和 Q：

• 进程 Q 因为某个条件 x 不满足而被阻塞了。
• 进程 P 运行在管程中，执行了 x.signal() 操作，唤醒了等待条件 x 的进程 Q。

问题是：进程 P 和进程 Q 都被激活了，该让谁先执行，谁等待？

方式一：P 等待，Q 先执行

• P 执行 x.signal() 后，立即把自己挂起，进入等待状态。
• Q 被唤醒后，继续执行，直到 Q 离开管程或因为其他条件再次被阻塞。
• 然后，P 才能继续执行。
• Hoare 管程采用这种方式。

方式二：P 先执行，Q 等待

• P 执行 x.signal() 后，继续执行，直到 P 离开管程或因为其他条件被阻塞。
• 然后，Q 才能被重新启动并执行。
• MESA 管程采用这种方式。

方式三：折中 - 规定 signal 操作必须是管程中过程的最后一个操作。

• P 执行 x.signal() 后，必须立即退出管程，没有其他操作了。
• Q 被唤醒后，可以立即执行，而不需要和 P 竞争。
• Hansan 管程采用这种方式。

2.5 经典进程的同步问题

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

1. 利用记录型信号量解决生产者-消费者问题

// 全局变量定义
int in = 0, out = 0;          // in 和 out 是缓冲区的索引，in 指向下一个空位，out 指向下一个待消费的位置
item buffer[n];               // 缓冲区，大小为 n
semaphore mutex = 1;          // 互斥信号量，实现对缓冲区的互斥访问
semaphore empty = n;          // 空槽位信号量，初始值为缓冲区的大小 n  -  同步信号量，表示空闲缓冲区的数量
semaphore full = 0;           // 满槽位信号量，初始值为 0 - 同步信号量，表示产品的数量，也即非空缓冲区的数量// 生产者函数
void producer() {do {// 生产一个 itemitem nextp = produce_item();  // 假设 produce_item() 是一个生产 item 的函数wait(empty);                 // 消耗一个空闲缓冲区wait(mutex);                 // 进入临界区，实现对缓冲区的互斥访问 - ***实现互斥的P操作一定要在实现同步的P操作之后***buffer[in] = nextp;          // 将生产的 item 放入缓冲区in = (in + 1) % n;           // 更新 in 索引，循环使用缓冲区signal(mutex);               // 离开临界区，释放互斥锁signal(full);                // 增加满槽位信号量，通知消费者有新的 item 可用 - 增加一个产品} while (TRUE);                  // 无限循环
}// 消费者函数
void consumer() {do {wait(full);                  //  消耗一个产品(非空缓冲区)wait(mutex);                 // 进入临界区，实现对缓冲区的互斥访问item nextc = buffer[out];    // 从缓冲区中取出一个 itemout = (out + 1) % n;         // 更新 out 索引，循环使用缓冲区signal(mutex);               // 离开临界区，释放互斥锁signal(empty);               // 增加空槽位信号量，通知生产者有空槽位可用 - 增加一个空闲缓冲区consume_item(nextc);         // 消费 item（假设 consume_item() 是一个消费 item 的函数）} while (TRUE);                  // 无限循环
}// 主函数
void main() {// 并发执行生产者和消费者cobeginproducer();                  // 启动生产者consumer();                  // 启动消费者coend
}

1. empty = n

• 表示初始时缓冲区中有 n 个空槽位（即 n 个资源未被使用）。
• 生产者生产一个 item 时会占用一个空槽位，因此需要先 wait(empty)，检查是否有空槽位可用。
• 如果 empty > 0，生产者可以继续生产；如果 empty = 0，表示缓冲区已满，生产者需要等待。

2. full = 0

• 表示初始时缓冲区中没有已生产的 item（即没有资源被操作）。
• 消费者消费一个 item 时会释放一个空槽位，因此需要先 wait(full)，检查是否有已生产的 item 可以消费。
• 如果 full > 0，消费者可以继续消费；如果 full = 0，表示缓冲区为空，消费者需要等待。

实现互斥的P操作一定要在实现同步的P操作之后

2. 利用 AND 信号量解决生产者-消费者问题

// 定义共享变量和信号量
int in = 0, out = 0;                // 生产者和消费者的索引
item buffer[n];                     // 容量为 n 的缓冲区
semaphore mutex = 1, empty = n, full = 0; // 互斥信号量 mutex，空槽位信号量 empty，已生产项信号量 full// 生产者函数
void producer() {do {// 生产一个 itemitem nextp = produce_item();  // 假设 produce_item() 是一个生产 item 的函数// 等待空槽位和互斥锁Swait(empty, mutex);         // 等待空槽位（empty--），同时获取互斥锁（mutex--）// 将 item 放入缓冲区buffer[in] = nextp;in = (in + 1) % n;           // 更新生产者索引// 释放互斥锁和增加已生产项Ssignal(mutex, full);        // 释放互斥锁（mutex++），并增加已生产项（full++）} while (TRUE);                  // 无限循环，持续生产
}// 消费者函数
void consumer() {do {// 等待已生产项和互斥锁Swait(full, mutex);          // 等待已生产项（full--），同时获取互斥锁（mutex--）// 从缓冲区取出 itemitem nextc = buffer[out];out = (out + 1) % n;         // 更新消费者索引// 释放互斥锁和增加空槽位Ssignal(mutex, empty);       // 释放互斥锁（mutex++），并增加空槽位（empty++）// 消费 itemconsume_the_item(nextc);     // 模拟消费 item} while (TRUE);                  // 无限循环，持续消费
}

• 用 Swait(empty，mutex)来代替 wait(empty)和 wait(mutex);

• 用 Ssignal(mutex, full)来代替 signal(mutex)和 signal(full);

• 用 Swait(full,mutex)代替 wait(full)和 wait(mutex)；

• 用 Ssignal(mutex，empty)代替Signal(mutex)和 Signal(empty)。

3. 利用管程解决生产者-消费者问题

// 定义生产者消费者问题的 Monitor —— Monitor 内部的所有方法是互斥执行的，即同一时刻只能有一个线程执行 Monitor 中的方法。
Monitor ProducerConsumer {item buffer[N];         // 容量为 N 的缓冲区int in, out;    // 共享变量：缓冲区的读写索引condition notfull;      // 条件变量：缓冲区未满condition notempty;     // 条件变量：缓冲区不为空int count;          // 缓冲区中当前的 item 数量 - 由于 Monitor 互斥性，count 的修改和访问不会发生竞争条件，即使它在多个线程之间共享。public:// 向缓冲区中放入 itemvoid put(item x) {// 如果缓冲区已满，则等待 "未满" 条件if (count >= N) {cwait(notfull);   // 阻塞当前线程，等待缓冲区未满}// 将 item 放入缓冲区buffer[in] = x;in = (in + 1) % N;    // 更新生产者索引，实现循环缓冲区count++;              // 增加缓冲区中的 item 数量// 通知消费者缓冲区不为空csignal(notempty);    // 唤醒等待 "不为空" 条件的线程}// 从缓冲区中取出 itemvoid get(item &x) {// 如果缓冲区为空，则等待 "不为空" 条件if (count <= 0) {cwait(notempty);  // 阻塞当前线程，等待缓冲区不为空}// 从缓冲区中取出 itemx = buffer[out];out = (out + 1) % N;  // 更新消费者索引，实现循环缓冲区count--;              // 减少缓冲区中的 item 数量// 通知生产者缓冲区未满csignal(notfull);     // 唤醒等待 "未满" 条件的线程}// 初始化缓冲区和条件变量ProducerConsumer() {in = 0;out = 0;count = 0;}
} PC;  // 定义 Monitor 实例 PC// 生产者线程函数
void producer() {item x;  // 定义 item 变量 x，用于存储生产的 itemwhile (TRUE) {  // 无限循环，持续生产 itemproduce an item in x;  // 生产一个 item 并存入 xPC.put(x);             // 将 item x 放入缓冲区}
}// 消费者线程函数
void consumer() {item x;  // 定义 item 变量 x，用于存储从缓冲区中取出的 itemwhile (TRUE) {  // 无限循环，持续消费 itemPC.get(x);             // 从缓冲区中取出一个 item 并存入 xconsume the item in x; // 消费 item x}
}// 主函数
void main() {cobegin                  // 启动并发执行producer();          // 启动生产者线程consumer();          // 启动消费者线程coend                    // 并发执行结束
}

1. 生产者线程 (producer)：

   • 生产者不断生产 item，并将其放入缓冲区。
   • 使用 PC.put(x) 方法将生产出的 item x 放入缓冲区。

2. 消费者线程 (consumer)：

   • 消费者不断从缓冲区中取出 item，并消费它。
   • 使用 PC.get(x) 方法从缓冲区中取出 item x。

3. 通过 Monitor PC 保证了缓冲区的线程安全访问。

   条件变量的使用：

   • 使用 cwait 阻塞线程，等待条件满足。
   • 使用 csignal 唤醒等待条件的线程。

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

问题设定

• 场景：5 位哲学家围坐在一张圆桌旁，桌上摆放 5 根筷子（每两位哲学家之间共享一根）。
• 哲学家行为：
  • 思考（Thinking）：哲学家长时间思考，不占用任何筷子。
  • 饥饿（Hungry）：哲学家感到饥饿，试图拿起 左右两边最靠近他的筷子 准备进餐。
  • 进餐（Eating）：如果成功拿到两根筷子，哲学家开始进餐，进餐结束后放下筷子继续思考。【只有在拿到两只筷子时才能进餐】
• 每个哲学家进程需要同时持有两个临界资源才能开始吃饭。需要避免临界资源分配不当造成的死锁现象

1. 利用记录型信号量解决哲学家进餐问题

//--------------------有死锁风险------------------
// 定义5个信号量，分别表示5根筷子，初始值均为1（表示筷子可用）
semaphore chopstick[5] = {1, 1, 1, 1, 1};// 哲学家i的行为
do {// 尝试获取左边的筷子（i号筷子）wait(chopstick[i]);// 尝试获取右边的筷子（(i+1)%5号筷子）wait(chopstick[(i + 1) % 5]);// 哲学家成功拿到两根筷子，开始进餐eat();// 进餐结束后，释放左边的筷子（i号筷子）signal(chopstick[i]);// 进餐结束后，释放右边的筷子（(i+1)%5号筷子）signal(chopstick[(i + 1) % 5]);// 哲学家开始思考think();
} while (TRUE); // 无限循环

假如五位哲学家同时饥饿而各自拿起左边的筷子时，就会使五个信号量chopstick均为0;当他们再试图去拿右边的筷子时，都将因无筷子可拿而无限期地等待。对于这样的死锁问题，可采取以下几种解决方法:

• 至多只允许有四位哲学家同时去拿左边的筷子

  Semaphore philospher=4;
  Semaphore chopsticks[5]={1,1,1,1,1};
  Philospher i(){while(1){P(philospher);P(chopsticks[i];P(chopsticks[(i+1)%5];开始进餐;V(chopsticks[i]);V(chopsticks[(i+1)%5]);V(philospher);
  }
  

• 一次仅有一位哲学家可以访问临界资源筷子 - 一个哲学家在拿筷子拿到一半时被阻塞，也不会有别的哲学家会继续尝试拿筷子。

  semaphore chopsticks[5]={1,1,1,1,1};//五个哲学家进程
  semaphore mutex=1;    //互斥资源，设置的互斥信号量
  philosopher i(){while(1){//用p v操作框起来，保证了左右两边都有筷子P(mutex);P(chopsticks[i]);//去左边的筷子P(chopsticks[(i+1)%5]);//取右边的筷子       开始进餐；V(mutex);       //先释放互斥锁可以保证其他哲学家取用筷子不会被阻碍V(chopsticks[i]);v(chopsticks[(i+1)%5]);思考；
  }
  

• 规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子;而偶数号哲学家则相反。

  semaphore chopsticks[5]={1,1,1,1,1};//五个哲学家进程
  void process(int i){while(1){if(i%2==0)//偶数号先拿右边的筷子{P(chopsticks[(i+1)%5]);//取右边的筷子P(chopsticks[i]);//去左边的筷子开始进餐；V(chopsticks[(i+1)%5]);V(chopsticks[i]);}else  //奇数号先拿左边的筷子{P(chopsticks[i]);//去左边的筷子P(chopsticks[(i+1)%5]);//取右边的筷子开始进餐；V(chopsticks[i]);V(chopsticks[(i+1)%5]);    }   }
  }
  

2. 利用 AND 信号量解决哲学家进餐问题

// 声明并初始化5个信号量，表示5根筷子，初始状态均为可用（1）
semaphore chopstick[5] = {1, 1, 1, 1, 1};// 哲学家i的循环行为
do {// 思考阶段think();// 同步请求两根筷子（防止死锁的关键点）// Sswait(chopstick[(i+1)%5], chopstick[i]) 是一个原子操作：// 1. 先尝试获取右边的筷子（(i+1)%5号）// 2. 再尝试获取左边的筷子（i号）// 如果任一筷子不可用则阻塞，避免循环等待Sswait(chopstick[(i + 1) % 5], chopstick[i]);// 成功获取两根筷子后开始进餐eat();// 原子性地同时释放两根筷子// Ssignal会按请求顺序的逆序释放资源：// 1. 先释放左边的筷子（i号）// 2. 再释放右边的筷子（(i+1)%5号）Ssignal(chopstick[(i + 1) % 5], chopstick[i]);} while (TRUE);  // 无限循环

2.5.3 读者-写者问题（Reader-Writer Problem）

问题描述

与消费者进程不同,读者进程在读数据后并不会将数据清空，并不会改变数据，因此多个读者可同时访问共享数据

读进程与写进程同时共享数据，可能导致读出的数据不一致的问题

两个写进程同时共享数据，可能导致数据错误覆盖的问题

• 多个 读者（Readers） 和多个 写者（Writers） 共享同一个数据对象（如文件、数据库、共享内存等）。

• 读者：只读取数据，不会修改数据（可并发执行）。

• 写者：会写入数据，必须独占访问（互斥访问）。

• 关键约束条件：

  1. 读写互斥：一个写者不能和任何读者或其他写者同时访问数据。

  2. 优先级：

     • 读者优先：只要存在读者，写者会被阻塞。
       ✅ 读者不会等待：多个读者可以并发读，无需互斥。
       ❌ 可能导致写者饥饿：如果一直有新的读者到来，写者可能永远无法执行。
       🔹 适用场景：读操作远多于写操作，且要求高读取并发性（如数据库查询）。

     • 写者优先：当有写者在等待时，新来的读者必须等待正在执行的读者完成，旧读者完成后，写者先执行，之后才允许新读者进入。

       ✅ 写者不会被饿死：只要有写者在等待，新读者就不能进入临界区。
       ❌ 读者可能等待较久：但不会完全饿死。
       🔹 适用场景：写操作频率较高，且要求数据一致性（如日志系统、内存缓存）。

     • 公平策略：通过FIFO调度读者和写者——即读者和写者按到达顺序执行，确保公平性。
       🔹 适用场景：读写比例均衡的系统

1. 利用记录型信号量解决读者-写者问题

//------------------------------读者优先--------------------------
semaphore rmutex = 1;   // 保护 readcount 的互斥锁（读者间互斥）
semaphore wmutex = 1;   // 读写互斥锁（保证写者独占）
int readcount = 0;      // 当前正在读取的读者数量//--------------------- 读者线程 ---------------------//
void reader() {do {// 1. 进入临界区，保护 readcountwait(rmutex);        if (readcount == 0)  // 如果是第一个读者，需要占用写锁wait(wmutex);     // 阻止写者进入readcount++;          // 增加读者计数signal(rmutex);       // 释放 readcount 锁// 2. 执行读操作（此时允许多个读者并发读）/* perform read operation */  // 3. 离开临界区，更新 readcountwait(rmutex);         readcount--;          if (readcount == 0)   // 如果是最后一个读者，释放写锁signal(wmutex);    // 允许写者进入signal(rmutex);       } while (TRUE);           // 循环执行
}//--------------------- 写者线程 ---------------------//
void writer() {do {wait(wmutex);          // 获取写锁（独占访问）/* perform write operation */  // 执行写操作signal(wmutex);        // 释放写锁} while (TRUE);            // 循环执行
}//--------------------- 主程序 ---------------------//
void main() {cobegin                     // 并发执行读者和写者reader();writer();coend
}

1. 信号量作用：
   • rmutex：保护 readcount 变量，防止多个读者同时修改导致竞争。
     • 互斥修改 readcount
       • 通过 wait(rmutex)/signal(rmutex) 确保同一时间只有一个线程能修改 readcount。
     • 避免重复获取 wmutex
       • 第一个读者（readcount == 0）会获取 wmutex，后续读者跳过这一步。
       • 最后一个读者（readcount == 0）会释放 wmutex。
       • rmutex 保证这一判断和操作的原子性，防止多个读者竞争 wmutex。
   • wmutex：实现读写互斥，保证写者独占访问
2. 读者逻辑：
   • 进入时：第一个读者获取 wmutex，后续读者只需递增 readcount。
   • 退出时：最后一个读者释放 wmutex，允许写者执行。
3. 写者逻辑：
   • 必须独占 wmutex，因此会等待所有读者完成（readcount == 0）

2. 利用信号量集解决读者-写者问题

增加了一个限制，即最多只允许RN个读者同时读

//------------------------------写者优先--------------------------
int RN;                   // 最大支持的读者数量
semaphore L = RN;         // 控制读者并发数（初始值为RN）
semaphore mx = 1;         // 写锁（保证写操作的互斥性）// ========== 读者线程 ==========
void reader() {do {// Swait(L,1,1): 申请一个L信号量（若L≥1则减1，否则阻塞）Swait(L, 1, 1);           // 占用一个读者名额// Swait(mx,1,0): 检查mx是否为0（不阻塞，仅测试）Swait(mx, 1, 0);          // 检查是否有写者正在写/* 执行读操作（多个读者可并发读） */// Ssignal(L,1): 释放一个L信号量（读者退出）Ssignal(L, 1);            // 释放读者名额} while (TRUE);
}// ========== 写者线程 ==========
void writer() {do {// Swait(mx,1,1; L,RN,0): 同时申请mx锁并检查无读者（L==RN）Swait(mx, 1, 1; L, RN, 0);  // 1. 独占mx锁；2. 确保无活跃读者（L==RN）/* 执行写操作（写者独占访问） */// Ssignal(mx,1): 释放mx锁Ssignal(mx, 1);            // 允许其他写者或读者进入} while (TRUE);
}// ========== 主程序 ==========
void main() {cobeginreader();  // 启动读者线程writer();  // 启动写者线程coend
}

1. RN

   • 表示系统允许的 最大读者并发数，初始化时 L = RN 表示所有读者名额可用。

2. Swait(L,1,1)（读者线程）

   • 申请一个读者名额：若 L ≥ 1 则减少 L，否则阻塞。
   • 保证当前活跃读者数 不超过 RN。

3. Swait(mx,1,0)（读者线程）

   • 非阻塞检查写锁：仅测试 mx 是否为 0（无写者），不影响信号量值。
   • 确保 无写者正在写 时才允许读。

4. Swait(mx,1,1; L,RN,0)（写者线程）

   • 同时满足两个条件：

     • mx = 1：获取写锁（保证互斥）。
     • L = RN：确保 所有读者名额均未被占用（即无活跃读者）。

   • 写者优先于新读者（防止读者饥饿）。

     写者通过 Swait(mx,1,1; L,RN,0) 严格抢占资源

     • 写者在进入临界区时，必须同时满足两个条件：
       • (1) 获得写锁 mx（保证互斥）。
       • (2) 检查读者信号量 L == RN（即当前没有活跃的读者）。
     • 这意味着：
       • 只要有读者在读写者必须等待（L < RN 时写者会被阻塞）。
       • 但在写者竞争时，新的读者无法抢占资源（因为 L 已经被占用）。

5. Ssignal 操作

   • 读者退出时释放 L，允许新读者进入。
   • 写者退出时释放 mx，允许其他写者或读者竞争。

2.5.4 可生产单种产品的多生产者-多消费者问题

2.5.5 吸烟者问题 - 可生产多种产品的单生产者-多消费者问题

2.6 进程通信

进程通信(Inter-Process Communication, IPC)是指进程之间的信息交换。

2.6.1 进程通信的类型

高级通信机制可归结为四大类: 共享存储器系统、管道通信系统、消息传递系统以及客户机-服务器系统。

1、共享存储器系统 (Shared-Memory System)

相互通信的进程共享某些数据结构或共享存储区，进程之间能够通过这些空间进行通信。可分成以下两种类型:

• 低级通信：基于共享数据结构的通信方式。【如在生产者-消费者问题中的有界缓冲区】
  操作系统仅提供共享存储器，由程序员负责对公用数据结构的设置及对进程间同步的处理。仅适于传递相对少量的数据，通信效率低下。
• 高级通信：基于共享存储区的通信方式。
  需要通信的进程在通信前，先向系统申请获得【共享存储区域：在内存中划出的且所有进程都可进行读或写交换信息的，且访问是互斥的】共享存储区域中的一个分区，并将其附加到自己的地址空间中，便可对其中的数据进行正常读、写交换信息，实现通信；读写完成或不再需要时，将其归还给共享存储区。数据的形式和位置甚至访问控制都是由进程负责，而不是OS。可传输大量数据。

2、管道(pipe)通信系统

“管道”，是指用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件，又名 pipe 文件。可有效地传送大量数据。
本质是在内存中开辟一个大小固定的内存缓冲区，读写数据先进先出。管道是循环队列

• 输入的发送进程(即写进程)：以字符流形式将大量的数据送入管道;
• 输出的接收进程(即读进程)：从管道中接收(读)数据。

管道机制必须提供以下三方面的协调能力:

• ①互斥：即当一个进程正在对 pipe 执行读/写操作时，其它(另一)进程必须等待。【各进程要互斥地访问管道(由操作系统实现)】
• ②同步：
  • 指当写(输入)进程把一定数量的数据写入 pipe，便去睡眠等待，直到读(输出)进程取走数据后再把它唤醒。
    写进程往管道里写数据：如果管道满了，写进程会"阻塞"（睡眠等待），等读进程取走数据后(管道未满)，就可 “叫醒”（唤醒）继续写。
  • 当读进程读一空 pipe 时，也应睡眠等待，直至写进程将数据写入管道后才将之唤醒。
    读进程从管道里读数据：如果管道是 空的，读进程会 “阻塞”（睡眠等待），等写进程往里写了新数据后(管道未空)，就可 “叫醒”（唤醒）继续读。
• ③确定对方是否存在：只有确定了对方已存在时才能进行通信。

管道只能采用华双工通信，某一时间段内只能实现单向的传输。如果要实现双向同时通信，则需要设置两个管道。

管道中的数据一旦被读出，就彻底消失。因此，当多个进程读同一个管道时，可能会错乱。对此，通常有两种解决方案:①一个管道允许多个写进程，一个读进程(2014年408真题高教社官方答案);②允许有多个写进程，多个读进程，但系统会让各个读进程轮流从管道中读数据(Linux的方案)。

3、消息传递系统 (Message passing system)

进程不借助任何共享存储区或数据结构，是以格式化的消息(message)为单位，将通信的数据封装在消息中，并利用操作系统提供的一组通信命令(原语)，在进程间进行消息传递，完成进程间的数据交换。

基于消息传递系统的通信方式属于高级通信方式，可分成两类:

• 直接通信方式，是指发送进程利用OS所提供的发送原语，直接把消息发送给目标进程:
• 间接通信方式，是指发送和接收进程都通过共享中间实体(称为邮箱)的方式进行消息的发送和接收，完成进程间的通信。

4、客户机-服务器系统 (Client-Server system)

主要的实现方法分为三类:套接字、远程过程调用和远程方法调用

• 套接字

  • 概念：

    • 一个套接字就是一个通信标识类型的数据结构，包含了通信目的的地址、通信使用的端口号、通信网络的传输层协议、进程所在的网络地址，以及针对客户或服务器程序提供的不同系统调用(或 API函数)等。
    • 是进程通信【同一台计算机内部的进程通信】和网络通信【网络环境中不同计算机间的进程通信】的基本构件。
    • 每个套接字拥有唯一的套接字号(也称套接字标识符)，系统中所有的连接都持有唯一的一对套接字及端口连接，能区分来自不同应用程序进程或网络连接的通信

  • 套接字是为客户/服务器模型而设计的，通常，套接字包括两类:

    • 基于文件型: 通信进程都运行在同一台机器的环境中，套接字是基于本地文件系统支持的，一个套接字关联到一个特殊的文件，通信双方通过对这个特殊文件的读写实现通信，其原理类似于前面所讲的管道。

    • 基于网络型: 该类型通常采用的是非对称方式通信，即发送者需要提供接收者命名。
      通信双方的进程运行在不同主机的网络环境下，被分配了一对套接字，一个属于接收进程(或服务器端)，一个属于发送进程(或客户端)。

      发送进程(或客户端)发出连接请求时，随机申请一个套接字，主机为之分配一个端口，与该套接字绑定，不再分配给其它进程。

      接收进程(或服务器端) 拥有全局公认的套接字和指定的端口(如ftp 服务器监听端口为 21，http服务器监听端口为 80)，并通过监听端口等待客户请求。任何进程都可以向接收进程发出连接请求和信息请求。

      • 接收进程(或服务器端)一旦收到请求，就接受来自发送进程(或客户端)的连接，完成连接，即在主机间传输的数据可以准确地发送到通信进程，实现进程间的通信;
      • 当通信结束时，系统通过关闭接收进程(或服务器端)的套接字撤销连接。

• 远程过程调用和远程方法调用

  • 概念：

    • 远程过程(函数)调用 RPC(Remote Procedure Call)，是一个通信协议，用于通过网络连接的系统。
    • 该协议允许运行于一台主机(本地)系统上的进程调用另一台主机(远程)系统上的进程。
    • 如果涉及的软件采用面向对象编程，那么远程过程调用亦可称做远程方法调用。

  • 角色：

    • 进程有两个：本地客户进程 ➕ 远程服务器进程，这两个进程通常也被称为网络守护进程，主要负责在网络间的消息传递

      一般情况下，这两个进程都是处于阻塞状态，等待消息。

    • 存根(stub)有两个：一般也是处于阻塞状态，等待消息。

      • 📌在本地客户端，每个能够独立运行的远程过程都拥有一个客户存根(Client Stub)

        客户存根(Client Stub): 伪装成远程服务，让本地代码以为在调用本地方法，其实是将本地调用转为网络请求。

        ✔️ 核心职责

        • 伪装成远程服务
          • 在代码中，客户端存根会暴露和远程服务完全相同的接口方法（例如GetUser(id)）。
          • 开发者调用client.GetUser(123)时，并不知道该方法实际会触发网络通信，仿佛在调用本地代码。
        • 本地调用 → 网络请求的转换
          • 接收本地参数：存根获取方法名（GetUser）和参数（id=123）。
          • 序列化参数：将参数转换为网络传输格式（如Protobuf / JSON）。
          • 协议封装：按协议（如HTTP/gRPC）构造协议头并打包请求数据。
        • 隐藏网络细节
          • 开发者无需处理：Socket连接、数据分包、超时重试、负载均衡等底层问题。

      • 📌在每个远程进程所在的服务器端，其所对应的实际可执行进程也存在一个服务器存根(Server Stub)。

        服务器存根(Server Stub)： 接收、解析客户端请求，并驱动真实业务逻辑执行，最终封装结果返回给客户端

        ✔️ 核心职责

        • 接收网络请求
          • 监听特定协议（如 HTTP/gRPC）的端口，接收客户端发来的二进制数据流。
        • 反序列化请求
          • 解析协议头（如 gRPC 的 Content-Type），提取方法名和参数。
          • 将二进制数据还原为编程语言对象（如 Protobuf → Go 结构体）。
        • 调用真实服务
          • 根据方法名（如 GetUser）找到服务端注册的业务实现类（如 UserService）。
          • 传入反序列化后的参数，执行实际逻辑（如查询数据库）。
        • 封装响应
          • 将业务结果（或异常）序列化为网络格式（如 Protobuf/JSON）。
          • 按协议组装响应头（如 HTTP 状态码、gRPC 的 grpc-status）。

  • 步骤：

    • 本地过程调用者以一般方式调用远程过程在本地关联的客户存根，传递相应的参数，然后将控制权转移给客户存根;
    • 客户存根执行，完成包括过程名和调用参数等信息的消息建立，将控制权转移给本地客户进程;
    • 本地客户进程完成与服务器的消息传递，将消息发送到远程服务器进程:
    • 远程服务器进程接收消息后转入执行，并根据其中的远程过程名找到对应的服务器存根，将消息转给该存根;
    • 服务器存根接到消息后，由阻塞状态转入执行状态，拆开消息从中取出过程调用的参数，然后以一般方式调用服务器上关联的过程;
    • 在服务器端的远程过程(真实服务-业务逻辑的代码)运行完毕后，将结果返回给与之关联的服务器存根:
    • 该服务器存根获得控制权运行，将结果打包为消息，并将控制权转移给远程服务器进程;
    • 远程服务器进程将消息发送回客户端;
    • 本地客户进程接收到消息后，根据其中的过程名将消息存入关联的客户存根，再将控制权转移给客户存根;
    • 客户存根从消息中取出结果，返回给本地调用者进程，并完成控制权的转移。

2.6.2 消息传递通信的实现方式

进程通信分为直接和间接两种通信方式

1、直接消息传递系统 - 直接通信

发送进程利用OS所提供的发送命令(原语)，直接把消息发送给目标进程。

直接通信原语

• 对称寻址方式：要求发送进程和接收进程都必须以显式方式提供对方的标识符。
  发送一个消息给接收进程 send(receiver, message); - 将消息message发送给接收进程receiver
  接收 Sender 发来的消息 receive(sender,message); - 接收由sender发来的消息message。

  缺点：一旦改变进程的名称，则可能需要检查所有其它进程的定义，有关对该进程旧名称的所有引用都必须查找到修改为新名称【不利于实现进程定义的模块化】

• 非对称寻址方式：在接收进程的原语中，不需要命名发送进程，只填写表示源进程的参数；发送进程仍需要命名接收进程。

  发送一个消息给进程P send(P,message);
  接收来自任何进程的消息 receive (id,message); id变量可为发送方进程 id 或名字。

消息的格式 : 可采用变长的消息格式，即进程所发送消息的长度是可变的。

进程的同步方式 - 协调通信 ：三种情况:

• ①发送进程阻塞，接收进程阻塞。这种情况主要用于进程之间紧密同步，发送进程和接收进程之间无缓冲时。
• ②发送进程不阻塞、接收进程阻塞。应用最广。
  • 发送进程平时不阻塞，可以尽快地把一个或多个消息发送给多个目标;
  • 接收进程平时则处于阻塞状态，直到发送进程发来消息时才被唤醒。
• ③发送进程和接收进程均不阻塞。较常见的。平时，发送进程和接收进程都在忙于自己的事情，仅当发生某事件使它无法继续运行时，才把自己阻塞起来等待。

通信链路
发送进程和接收进程之间建立一条通信链路进行通信。

• 建立通信链路有两种方式：
  • 由发送进程在通信之前用显式的“建立连接”命令(原语)请求系统为之建立一条通信链路，在链路使用完后拆除链路。这种方式主要用于计算机网络中。
  • 发送进程无须明确提出建立链路的请求，只须利用系统提供的发送命令(原语)，系统会自动地建立一条链路。这种方式主要用于单机系统中。
• 链路分成两种:
  • 单向通信链路，只允许发送进程向接收进程发送消息，或者相反;
  • 双向通信链路，既允许由进程A向进程B发送消息，也允许进程 B同时向进程A发送消息。

2、信箱通信 - 间接通信

• 进程之间的通信，需要通过某种中间实体(如共享数据结构等)来完成。
• 该实体建立在随机存储器的公用缓冲区上，用来暂存发送进程发送给目标进程的消息;
• 接收进程可以从该实体中取出发送进程发送给自己的消息，通常把这种中间实体称为邮箱(或信箱);
• 每个邮箱都有一个唯一的标识符。
• 实现实时通信，又可实现非实时通信。

信箱结构

在逻辑上，可以将其分为两个部分: 消息的传递可以单向传递，也可以是双向的

• 信箱头，用以存放有关信箱的描述信息，如信标识符、信的拥有者、信箱口信箱的空格数等;
• 信箱体，由若干个可以存放消息(或消息头)的信箱格组成，信箱格的数目以及每格的大小是在创建信箱时确定的。

信箱通信原语

• 邮箱的创建和撤消。
  • 进程可利用邮箱创建原语来建立一个新邮箱，创建者进程应给出邮箱名字、邮箱属性(公用、私用或共享);
    对于共享邮箱，还应给出共享者的名字。
  • 当进程不再需要读邮箱时，可用邮箱撤消原语将之撤消。
• 消息的发送和接收。当进程之间要利用邮箱进行通信时，必须使用共享邮箱，并利用系统提供的下述通信原语进行通信。
  • 将一个消息发送到指定邮箱 Send(mailbox，message);
  • 从指定邮箱中接收一个消息 Receive(mailbox,message);

信箱的类型
邮箱可由操作系统创建，也可由用户进程创建，创建者是邮箱的拥有者。据此，可把邮箱分为以下三类:

• 私用邮箱。
  • 用户进程可为自己建立一个新邮箱，并作为该进程的一部分。
  • 邮箱的拥有者有权从邮箱中读取消息，其他用户则只能将自己构成的消息发送到该邮箱中。
  • 采用单向通信链路的邮箱来实现。
  • 当拥有该邮箱的进程结束时,邮箱也随之消失。
• 公用邮箱。
  • 由操作系统创建，并提供给系统中的所有使用。
    核准进程（Authorized Process）是指经过系统安全机制验证，具备特定权限或资源访问资格的进程。其核心目的是防止未授权的代码或用户执行特权操作
  • 核准进程既可把消息发送到该邮箱中，也可从邮箱中读取发送给自己的消息。
  • 采用双向通信链路的邮箱来实现。
  • 公用邮箱在系统运行期间始终存在。
• 共享邮箱。
  • 由某进程创建，在创建时或创建后指明它是可共享的，同时须指出共享进程(用户)的名字。
  • 邮箱的拥有者和共享者都有权从邮箱中取走发送给自己的消息。

在利用邮箱通信时,在发送进程和接收进程之间, 存在以下四种关系:

• 一对一关系。发送进程和接收进程可以建立一条两者专用的通信链路，使两者之间的交互不受其他进程的干扰。
• 多对一关系。允许一个服务(接收)进程与多个用户(发送)进程之间进行交互，也称为客户/服务器交互(client/server interaction)。
• 一对多关系。允许一个发送进程与多个接收进程进行交互，使发送进程可用广播方式向接收者(多个)发送消息。
• 多对多关系。允许建立一个公用邮箱，让多个进程都能向邮箱中投递消息; 也可从邮箱中取走属于自己的消息。

2.6.3 直接消息传递系统实例

消息缓冲队列通信机制被广泛应用于本地进程之间的通信中。

• 发送进程利用Send 原语将消息直接发送给接收进程
• 接收进程则利用 Receive 原语接收消息。

1、消息缓冲队列通信机制中的数据结构

• 消息缓冲区

type struct message_buffer {int sender;                                        // 发送者进程标识符int size;                                            // 消息长度char *text;                                        // 消息正文struct message_buffer *next;            // 指向下一个消息缓冲区的指针
}

• PCB中有关通信的数据项。
  • 消息队列队首指针，用于对消息队列进行操作
  • 用于实现同步的互斥信号量mutex
  • 资源信号量sm

type struct processcontrol_block {...struct message_buffer *mq;   // 消息队列队首指针semaphore mutex;                // 消息队列互斥信号量semaphore sm;                     // 消息队列资源信号量...
}PCB ;

2、发送原语

• 发送进程在利用发送原语发送消息之前，应先在自己的内存空间设置一发送区a
• 把待发送的消息正文、发送进程标识符、消息长度等信息填入发送区a中
• 调用发送原语，把消息发送给目标(接收)进程。
• 发送原语首先根据发送区a中所设置的消息长度来申请一缓冲区
• 接着把发送区a中的信息复制到缓冲区中
• 将缓冲区挂在接收进程的消息队列(临界资源)上。

void send(receiver, a)  // receiver为接收进程标识符，a为发送区首址
{// 根据 a.size 申请缓冲区;getbuf(a.size, i);   // 将发送区a中的信息复制到消息缓冲区i中;copy(i.sender, a.sender);  i.size = a.size;copy(i.text, a.text);i.next = 0;// 获得接收进程内部的标识符j;getid(PCBset, receiver.j);wait(j.mutex);// 将消息缓冲区插入消息队列;insert(&j.mq, i);signal(j.mutex);signal(j.sm);
}

3、接收原语

• 接收进程调用接收原语receive(b)
• 从自己的消息缓冲队列中摘下第一个消息缓冲区
• 并将其中的数据复制到以b为首址的指定消息接收区内
• 释放消息缓冲区。

void receive(b){// j为接收进程内部的标识符;j = internal name;wait(j.sm);wait(j.mutex);// 将消息队列中第一个消息移出;remove(j.mq, i);signal(j.mutex);// 将消息缓冲区i中的信息复制到接收区 b;copy(b.sender, i.sender);b.size = i.size;copy(b.text, i.text);// 释放消息缓冲区;releasebuf(i);
}

2.7 线程(Threads)的基本概念

引入进程的目的是为了使多个程序能并发执行，以提高资源利用率和系统吞吐量。

引入线程的目的是为了减少程序在并发执行时所付出的时空开销，使OS具有更好的并发性。

2.7.1 线程的引入

1、进程的两个基本属性

• 进程是一个可拥有资源的独立单位：一个进程要能独立运行，它必须拥有一定的资源，包括用于存放程序正文、数据的磁盘和内存地址空间，以及它在运行时所需要的 I/O 设备、已打开的文件、信号量等;

• 进程同时又是一个可独立调度和分派的基本单位。每个进程在系统中有唯一的PCB，系统可根据其PCB感知进程的存在，也可以根据其 PCB 中的信息，对进程进行调度，还可将断点信息保存在其PCB中。反之，再利用进程 PCB 中的信息来恢复进程运行的现场。

  调度（Scheduling）：决定哪个就绪进程将来获得CPU（决策过程）。

  分派（Dispatching）：执行调度的决策，实际将CPU分配给该进程（动作过程），使其从就绪态转为运行态的过程。

2、程序并发执行所需付出的时空开销

为使程序能并发执行，系统必须进行以下的一系列操作:

• 创建进程，系统在创建一个进程时，必须为它分配其所必需的、除处理机以外的所有资源，如内存空间、I/O设备，以及建立相应的PCB
• 撤消进程，系统在撤消进程时，又必须先对其所占有的资源执行回收操作，然后再撤消PCB
• 进程切换，对进程进行上下文切换时，需要保留当前进程的CPU环境，设置新选中进程的 CPU 环境，因而须花费不少的处理机时间。

2.7.2 线程与进程的比较

由于线程具有许多传统进程所具有的特征，所以又称之为轻型进程(Light-Weight Process)或进程元

把传统进程称为重型进程(Heavy-Weight Process)，相当于只有一个线程的任务。

1、调度的基本单位

• 进程作为独立调度和分派的基本单位——进程是能独立运行的基本单位。在每次被调度时，都需要进行上下文切换，开销较大。

• 线程作为调度和分派的基本单位——线程是能独立运行的基本单位。当线程切换时，仅需保存和设置少量寄存器内容，切换代价远低于进程。

  在同一进程中，线程的切换不会引起进程的切换，但从一个进程中的线程切换到另一个进程中的线程时，必然就会引起进程的切换。

  传统进程机制中，进程是资源分配、调度的基本单位
  引入线程后，进程是资源分配的基本单位，线程是调度的基本单位

2、并发性

• 进程之间可以并发执行
• 在一个进程中的多个线程之间（甚至所有线程）可并发执行
• 不同进程中的线程也能并发执行

例子：在文字处理器中可以设置三个线程

• 第一个线程用于显示文字和图形
• 第二个线程从键盘读入数据
• 第三个线程在后台进行拼写和语法检查

3、拥有资源

• 进程可以拥有资源，并作为系统中拥有资源的一个基本单位。
• 线程拥有少量资源【一组寄存器和堆】, 以保证独立运行。
  • 在每个线程中都应具有一个用于控制线程运行的线程控制块 TCB
  • 用于指示被执行指令序列的程序计数器
  • 保留局部变量
  • 少数状态参数
  • 返回地址。
• 允许多个线程共享该进程所拥有的资源:
  • 属于同一进程的所有线程都具有相同的地址空间——线程可以访问该地址空间中的每一个虚地址
  • 可以访问进程所拥有的资源，如已打开的文件、定时器、信号量机构等的内存空间和它所申请到的I/O设备等。

4、独立性

在同一进程中的不同线程之间的独立性要比不同进程之间的独立性低得多。

• 【为防止进程之间彼此干扰和破坏】每个进程都拥有一个独立的地址空间和其它资源，除了共享全局变量外，不允许其它进程的访问。
• 同一进程中的不同线程之间可以相互合作，它们共享进程的内存地址空间和资源。

5、系统开销

进程创建或撤消时大于线程所付出的开销:

• 在创建或撤消进程时，系统都要为之分配和回收进程控制块、分配或回收其它资源，如内存空间和 I/O 设备等。
• 在进程切换时，涉及到进程上下文的切换，系统开销大; 线程间并发，如果是同一进程内的线程切换，则不需切换进程环境，系统开销小。
• 在一些OS中，线程的切换、同步和通信都无需操作系统内核的干预。

6、支持多处理机系统

• 在多处理机系统中，对于传统的进程，即单线程进程，不管有多少处理机，该进程只能运行在一个处理机上。
• 在多处理机系统中，对于多线程进程，可以将一个进程中的多个线程分配到多个处理机上，使它们并行执行。

2.7.3 线程的状态和线程控制块

1、线程运行的三个状态

• 执行状态，表示线程已获得处理机而正在运行;
• 就绪状态，指线程已具备了各种执行条件，只须再获得CPU便可立即执行;
• 阻塞状态，指线程在执行中因某事件受阻而处于暂停状态。

2、线程控制块 TCB

每个线程配置了一个线程控制块TCB,将所有用于控制和管理线程的信息记录在线程控制块中。

线程控制块通常有这样几项:

• ① 线程标识符，为每个线程赋予一个唯一的线程标识符;
• ② 一组寄存器，包括程序计数器PC、状态寄存器和通用寄存器的内容;
• ③ 线程运行状态，用于描述线程正处于何种运行状态;
• ④ 优先级，描述线程执行的优先程度;
• ⑤ 线程专有存储区，用于线程切换时存放现场保护信息，和与该线程相关的统计信息等;
• ⑥ 信号屏蔽，即对某些信号加以屏蔽；
• ⑦ 堆栈指针，每个线程需设置一个堆栈，用它来保存局部变量和返回地址【在线程运行时，经常会进行过程调用，而过程的调用通常会出现多重嵌套的情况，就必须将每次过程调用中所使用的局部变量以及返回地址保存起来。】。在TCB中须设置两个指向堆栈的指针:
  • 指向用户自己堆栈的指针：当线程运行在用户态时，使用用户自己的用户栈来保存局部变量和返回地址
  • 指向核心栈的指针：当线程运行在核心态时使用系统的核心栈。

3、多线程 OS 中的进程属性

• 进程是一个可拥有资源的基本单位。在多线程OS中，进程仍是作为系统资源分配的基本单位，任一进程所拥有的资源都包括:
  • 用户的地址空间
  • 实现进程(线程)间同步和通信的机制
  • 已打开的文件
  • 已申请到的I/O 设备
  • 一张由核心进程维护的地址映射表，该表用于实现用户程序的逻辑地址到其内存物理地址的映射。
• 多个线程可并发执行。通常一个进程都含有若干个相对独立的线程(至少要有一个线程)。
  • 把传统进程的执行方法称为单线程方法。
  • 将每个进程支持多个线程执行的方法称为多线程方法。
• 进程已不是可执行的实体。在多线程OS中，是把线程作为独立运行(或称调度)的基本单位。
  • 进程仍具有与执行相关的状态——所谓进程处于“执行”状态，实际上是指该进程中的某线程正在执行。
  • 对进程所施加的与进程状态有关的操作也对其线程起作用。
    例如，在把某个进程挂起时，该进程中的所有线程也都将被挂起；又如，在把某进程激活时，属于该进程的所有线程也都将被激活、

2.8 线程的实现

2.8.1 线程的实现方式

1、内核支持线程 KST(Kernel Supported Threads) - 内核空间

• 特点：

  • 在内核空间中实现的：在OS中的所有进程【无论是系统进程还是用户进程】，都是在操作系统内核的支持下运行的。
  • 内核支持线程KST同样也是在内核的支持下运行的，它们的创建、阻塞、撤消和切换等，也都是在内核空间实现的。
  • 在内核空间也为每一个内核线程设置了一个线程控制块，内核根据该控制块感知某线程的存在，并对其加以控制和管理。
  • 调度是以线程为单位进行的

• 优点：

  • 在多处理器系统中，内核能够同时调度同一进程中的多个线程并行执行;
  • 并发能力强：如果进程中的一个线程被阻塞了，内核可以调度该进程中的其它线程占有处理器运行，也可以运行其它进程中的线程;
  • 内核支持线程具有很小的数据结构和堆栈，线程的切换比较快，切换开销小;
  • 内核本身也可以采用多线程技术，可以提高系统的执行速度和效率。

• 缺点：

  • 对于用户的线程切换而言，其模式切换的(CPU 需要变态)开销较大：在同一个进程中，从一个线程切换到另一个线程时，需要从用户态转到核心态进行，这是因为用户进程的线程在用户态运行，而线程调度和管理是在内核实现的，系统开销较大。

2、用户级线程 ULT(User Level Threads) - 用户空间

• 特点：

  • 用户级线程是与内核无关：对线程的创建、撤消、同步与通信等功能，都无需内核的支持，内核完全不知道用户级线程的存在。
  • 是在用户空间中实现的：线程的任务控制块都是设置在用户空间，线程所执行的操作也无需内核的帮助 - 不需要CPU变态。
  • 是应用程序通过线程库实现的。
  • 调度是以进程为单位进行的。

• 优点：

  • 线程切换不需要转换到内核空间，开销小。
    • 所有线程管理数据结构（TCB） 存放在进程的用户空间，切换时 不涉及内核模式（避免用户态→内核态切换开销）。
    • 线程切换由用户级线程库直接管理，不依赖操作系统内核。
  • 调度算法可以是进程专用的。在不干扰 OS 调度的情况下，每个进程可定制独立的线程调度策略。
  • 用户级线程的实现与OS平台无关。对于线程管理的代码是属于用户程序的一部分，所有的应用程序都可以对之进行共享。线程机制不依赖 OS 内核支持。即使 OS 本身不支持线程（如早期 Unix），用户程序仍可模拟多线程（基于协程、状态机）。

用户级线程（ULT）和 内核级线程（KLT）对比：

优点	用户级线程（ULT）	内核级线程（KLT）
切换速度	快（无内核介入）	慢（需切换至内核态）
调度控制	进程可自定义调度策略	由 OS 统一调度
多核并行	不真正并行（OS 仅调度单进程）	可多核并行
跨平台性	强（不依赖内核支持）	依赖 OS 线程机制（如 Windows CreateThread）

缺点	用户级线程（ULT）	内核级线程（KLT）
系统调用阻塞	整个进程/某一个线程阻塞，所有线程暂停	仅阻塞当前线程，其他线程可运行
多核并行	多个线程不可在多核处理机上并行运行（单进程单CPU分配）	线程可分配到不同核心并行执行

3、组合

把用户级线程和内核支持线程两种方式进行组合，提供了组合方式ULT/KST线程。在组合方式线程系统中，

• 内核支持多个内核支持线程的建立、调度和管理;
• 也允许用户应用程序建立、调度和管理用户级线程。

组合方式线程中，同一个进程内的多个线程可以同时在多处理器上并行执行，而且在阻塞一个线程时并不需要将整个进程阻塞。

由于用户级线程和内核支持线程连接方式的不同，从而形成了三种不同的模型:

• 多对一模型，即将用户线程映射到一个内核控制线程。
  • 这些用户线程一般属于一个进程，运行在该进程的用户空间，对这些线程的调度和管理也是在该进程的用户空间中完成。
    仅当用户线程需要访问内核时，才将其映射到一个内核控制线程上，但每次只允许一个线程进行映射。
  • 优点：线程管理的开销小，效率高
  • 缺点：如果一个线程在访问内核时发生阻塞，则整个进程都会被阻塞; 此外，在任一时刻，只有一个线程能够访问内核，多个线程不能同时在多个处理机上运行。
• 一对一模型，即将每一个用户级线程映射到一个内核支持线程。
  • 为每一个用户线程都设置一个内核控制线程与之连接。
  • 优点：当一个线程阻塞时，允许调度另一个线程运行，所以它提供了比多对一型更好的并发功能。此外，在多处理机系统中，它允许多个线程并行地运行在多处理机系统上。
  • 缺点：每创建一个用户线程，相应地就需要创建一个内核线程，开销较大，因此需要限制整个系统的线程数。
• 多对多模型，即将许多用户线程映射到同样数量或更少数量的内核线程上。
  • 内核控制线程的数目可以根据应用进程和系统的不同而变化，可以比用户线程少，也可以与之相同。
  • 该模型结合上述两种模型的优点
    • 可以像一对一模型那样，使个进程的多个线程并行地运行在多处理机系统上
    • 也可像多对一模型那样，减少线程的管理开销和提高效率。

​

2.8.2 线程的实现

不论是进程还是线程，都必须直接或间接地取得内核的支持。

1、内核支持线程的实现

• 系统在创建一个新进程时，便在内核空间为它分配一个任务数据区 PTDA(Per Task Data Area)，其中包括若干个线程控制块 TCB 空间。
• 在每一个TCB中可保存线程标识符、优先级、线程运行的 CPU状态等信息。
• 每当进程要创建一个线程时，便为新线程分配个TCB，将有关信息填入该TCB中，并为之分配必要的资源。
• 当PTDA中的所有TCB 空间已用完，而进程又要创建新的线程时，只要其所创建的线程数目未超过系统的允许值(通常为数十至数百个)，系统可再为之分配新的 TCB 空间。
• 在撤消一个线程时，也应回收该线程的所有资源和 TCB。
  有的系统中为了减少在创建和撤消一个线程时的开销，在撤消一个线程时并不立即回收该线程的资源和 TCB——当以后再要创建一个新线程时，便可直接利用已被撤消但仍保持有资源的 TCB作为新线程的TCB。
• 内核支持线程的调度和切换与进程的调度和切换十分相似，也分抢占式方式和非抢占方式两种。
• 在线程的调度算法上，同样可采用时间片轮转法、优先权算法等。

2、用户级线程的实现

• 用户级线程是在用户空间实现的。

• 所有的用户级线程都具有相同的结构，它们都运行在一个中间系统上。当前有两种方式实现中间系统，即运行时系统和内核控制线程。

  • 运行时系统（Runtime System）

    本质：一组用于管理和控制线程的函数（过程）的集合，包含：

    • 线程生命周期管理（创建、撤销）
    • 线程同步与通信（互斥锁、信号量、条件变量）
    • 线程调度（选择合适的就绪线程执行）

    作用：

    • 使用户级线程无需依赖内核（纯用户空间实现）。
    • 充当用户级线程与内核之间的接口（但本身不进入内核）。

    线程切换机制：

    • 传统进程切换：必须进入内核态（user → kernel），由 OS 完成上下文切换。
    • 用户级线程切换：
      • 完全在用户空间完成，由运行时系统的线程切换函数处理：
        1. 保存当前线程状态（CPU 寄存器、栈指针）到线程的私有堆栈。
        2. 选择新线程（根据调度算法从就绪队列中选取）。
        3. 加载新线程状态（从堆栈恢复寄存器、更新栈指针和程序计数器）。
      • 优势：线程的切换无须进入内核，切换操作简单且速度极快。

    系统资源：

    • 进程是利用OS提供的系统调用来请求系统资源的，系统调用通过软中断(如tap)机制进入OS内核，由内核来完成相应资源的分配。
    • 用户级线程是不能利用系统调用的。当线程需要系统资源时，是将该要求传送给运行时系统，由后者通过相应的系统调用来获得系统资源。

  • 内核控制线程, 又称为轻型进程 LWP(Light Weight Process)

    本质：介于 用户级线程（ULT） 和 内核级线程（KLT） 之间的桥梁，用于赋予 ULT 部分内核支持线程的能力。

    特点：

    • 每个 LWP 拥有独立的 TCB（栈、寄存器状态、优先级），但共享进程资源（如内存、文件描述符）。
    • 通过系统调用访问内核（与内核级线程类似），但由用户线程运行时系统动态绑定。
    • 通过 LWP，ULT 获得与内核通信的能力（如 I/O 请求）。

    LWP 的核心机制:

    • LWP 线程池（缓冲池）

      • 背景：用户级线程可能数量庞大（如协程池），而内核无法直接管理 ULT。

      • 解决方案：进程维护一个 LWP 池（数量远少于 ULT），动态分配给 ULT 使用。

      • 工作方式：

        • 当一个 ULT 需要访问内核（如系统调用），它必须绑定到一个 空闲的 LWP。
        • 如果 LWP 池耗尽（例：5 个 ULT 请求 I/O，但仅有 4 个 LWP），则超出的 ULT 必须等待。

    • LWP 与内核线程的关系

      • LWP一对一绑定到内核级线程（KLT）：

        • 内核只能看到 LWP（即 KLT），无法感知 ULT 的存在。
        • 调度单位是 LWP（内核按 LWP 分配 CPU 时间片）。

      • ULT 通过 LWP 间接访问内核：当 ULT 执行系统调用时，需绑定到 LWP，由 LWP 代理请求内核。

    阻塞

    • 在内核级线程执行操作时，如果内核级线程发生阻塞，则与之相连接的多个LWP也将随之阻塞，进而使连接到 LWP 上的用户级线程也被阻塞。
    • 如果进程中只包含了一个LWP，该进程实际上也应阻塞。
    • 如果在一个进程中含有多个LWP，则当一个LWP阻塞时，进程中的另一个LWP可继续执行。
    • 即使进程中的所有LWP全部阻塞，进程中的线程也仍然能继续执行，只是不能再去访问内核。

2.8.3 线程的创建和终止

1、线程的创建

• 应用程序在启动时，通常仅有一个线程在执行，人们把线程称为“初始化线程”，主要功能是用于创建新线程。
• 在创建新线程时，需要利用一个线程创建函数(或系统调用)，并提供相应的参数——如指向线程主程序的入口指针、堆栈的大小，以及用于调度的优先级等。
• 在线程的创建函数执行完后，将返回一个线程标识符供以后使用。

2、线程的终止

线程终止的两种情况

• 正常终止
  • 线程主动完成任务后，调用终止函数（如 pthread_exit）退出。
• 强制终止
  • 线程因异常（如段错误、未捕获信号）或被其他线程终止（如 pthread_cancel）。

线程终止后的资源处理

• 资源不会立即释放：
  • 线程终止后，其占用的资源（如栈、寄存器状态、线程描述符）可能被保留。
  • 需其他线程显式调用分离函数（如 pthread_detach）才能释放资源。
• 未分离的线程可被复用：
  • 其他线程可通过连接（join）操作获取已终止线程的状态，并回收资源。
  • 若线程未被分离，其资源会一直保留，直到被连接（pthread_join）。

系统线程的特殊性

长期运行的线程：

• 某些系统线程（如内核守护线程）一旦启动，会持续运行，不被显式终止。
• 通常由操作系统管理，用户无法直接干预其生命周期。

线程连接（Join）机制

• 作用：允许一个线程等待另一个线程终止，并获取其退出状态。
• 阻塞与非阻塞：
  • 若目标线程仍在运行：调用 pthread_join 的线程会阻塞，直到目标线程终止。
  • 若目标线程已终止：调用线程立即继续执行，并回收资源。
• 连接后资源释放：成功连接后，目标线程的资源会被系统回收。
• ✅ pthread_join 是唯一获取线程返回值的方式（如果不关心返回值，可以传 NULL）。
• 只有 非分离（non-detached）线程 才能被 join

分离（Detach）机制

• 作用：显式声明线程终止后自动释放资源，无需其他线程连接。
• 使用场景：如果 不关心线程的返回值，并且 希望线程结束后自动释放资源，可调用 pthread_detach 避免资源泄露。
• 不可逆性：线程一旦**被分离**，不能再通过 join 连接。

关键函数对比

操作	函数（POSIX线程）	效果
终止线程	pthread_exit	线程主动退出，资源保留到被连接或分离。
强制终止线程	pthread_cancel	请求终止目标线程，终止行为取决于线程的取消状态（延迟或异步）。
等待线程终止并回收	pthread_join	阻塞调用者直到目标线程终止，回收资源。
分离线程	pthread_detach	线程终止后自动释放资源，无需连接。

2.8.4 线程的状态与转换 + 组织与控制

---

参考：

教材：
计算机操作系统（第四版） (汤小丹) (Z-Library).pdf

视频：
王道计算机考研 操作系统

博客：
哲学家进餐