进程与并发

Posted Jun 11, 2026

By 何翌闻

26 min read

进程与并发

进程的概念、组成、特征

概念

程序是静态的、存放在磁盘里的可执行文件

进程(Process)是动态的、是程序的一次执行过程

同一个程序会对应多个进程

组成

进程实体的组成：PCB、程序段（程序的代码【指令序列】）、数据段（运行过程中产生的各种数据【如：程序中定义的变量】）
PCB是给操作系统用的，而程序段和数据段是给进程自己用的

如何区分不同的进程 — PID：唯一的、不重复的，进程的“身份证号”

struct task_struct

操作系统需要记录：

进程描述信息：PID、UID：进程所属用户ID
资源分配清单 — 给进程分配了哪些资源（分配多少内存、正在使用哪些I/O设备、正在使用哪些文件）
进程控制和管理信息 — 进程的运行情况（CPU使用时间、磁盘使用情况、网络流量使用情况，进程当前状态【就绪态、阻塞态…】）
处理机相关信息 — 如PSW、PC等各种寄存器的值，用户实现进程切换

这些信息都会被记录在PCB(Process Control Block)中，即进程控制块

PCB是进程存在的唯一标志，当进程被创建时，操作系统会为其创建PCB，当进程结束时，会回收其PCB

进程是动态的，而进程实体是静态的

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

一个进程被“调度”，就是指操作系统决定让这个进程上CPU运行

特征

动态性（最基本的特征）、并发性、独立性、异步性、结构性

异步性：各进程按各自独立的、不可预知的速度向前推进，操作系统要提供“进程同步机制”来解决异步问题

进程的状态与状态转换

状态

创建态：进程正在被创建时，状态就是“创建态”，在这个阶段，操作系统会为进程分配资源、初始化PCB

当进程创建完成后，就进入“就绪态”，处于就绪态已经具备运行条件，但是由于没有空闲CPU，所以暂时不能运行

当CPU空闲下来，操作系统就会选择一个就绪态进程，让他上处理机运行

如果一个进程在CPU上运行，那么这个进程就处于“运行态”，CPU会执行改进程对应的程序

在进程运行的过程中，可能会请求等待某个事件的发生，在这个事件发生前，进程无法继续往下执行，此时操作系统会让这个进程下CPU，并让他进入“阻塞态”

当这个“等待的事件”发生之后，就又回到了就绪态

一个进程可以执行 exit 系统调用，请求操作系统终止该进程。此时该进程会进入“终止态”，操作系统会让该进程下CPU，并回收内存空间等资源，最后还要回收该进程的PCB。当终止进程的工作完成之后，这个进程就彻底消失了。

组织方式

链式

索引

进程控制

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

怎么实现进程控制 — 原语

进程控制相关原语

作业：还放在外存里的、没有运行的程序

进程间通信

Inter-Process Communication，IPC：两个进程之间产生数据交互

为什么进程通信需要OS支持？

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

共享存储

shm_open申请共享存储区

mmap将共享内存区映射到进程自己的地址空间

通过“增加页表项/段表项”即可将同一片共享内存区映射到各个进程的地址空间中

消息传递

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

格式化的消息分为两个部分：消息头（发送进程ID、接受进程ID、消息长度等格式化的信息）、消息体

消息传递：直接通信方式（消息发送进程要指明接收进程的ID）、间接通信方式（通过“信箱”间接地通信）

管道通信

一个只能从头部写，一个只能从头部读，先进先出 — 循环队列

信号

区分：信号量 semaphore：实现进程间的同步、互斥

信号 signal：实现进程间通信IPC

信号用于通知进程某个特定的事件已经发生。进程收到一个信号后，对该信号进行处理

无法区分是哪个进程发的信号

什么时候处理信号？ — 当进程从内核态转为用户态时（如系统调用返回、或中断处理返回时），例行检查是否有待处理信号，如果有，就处理信号

具体屏蔽哪些信号由进程自己决定

pending & ~blocked

信号可以作为异常的配套机制，让进程对操作系统的异常处理进行补充

有些异常可以由内核完成全部处理，如缺页异常

而有些不行，可能还需要用户进程配合

线程

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

线程是一个基本的CPU执行单元，也是程序执行流的最小单位。引入线程之后，不仅是进程之间可以并发，进程内的各线程之间也可以并发，从而进一步提升了系统的并发度，使得一个进程内也可以并发处理各种任务（如QQ视频、文字聊天、传文件）引入线程后，进程只作为除CPU之外的系统资源的分配单元（如打印机、内存地址空间等都是分配给进程的）。

实现方式

用户级线程ULT

历史背景：早期OS只支持进程，当时的线程是由线程库实现的

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

内核级线程KLT

内核级线程作为处理机调度的基本单位，而进程只作为分配资源的基本单位，因此在多核CPU下，几个线程可以在不同CPU下并行执行

内核级线程的管理工作由操作系统内核完成。
线程调度、切换等工作都由内核负责，因此内核级线程的切换必然需要在核心态下才能完成。
操作系统会为每个内核级线程建立相应的TCB（Thread Control Block，线程控制块），通过TCB对线程进行管理。“内核级线程”就是“从操作系统内核视角看能看到的线程”
优缺点
1. 优点：当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行。
2. 缺点：一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大

多线程模型

一对一模型：一个用户级线程映射到一个内核级线程。每个用户进程有与用户级线程同数量的内核级线程。优点：当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行。缺点：一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大。

多对一模型：多个用户级线程映射到一个内核级线程。且一个进程只被分配一个内核级线程。优点：用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行【因为只有内核级线程是处理机分配的基本单位】

状态与转换

调度

基本概念

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

作业：一个具体的任务

用户向系统提交一个作业 = 用户让操作系统启动一个程序（来处理一个具体的任务）

但是内存空间有限，有时无法将用户提交的作业全部放入内存

高级调度（作业调度）：按一定的原则从外存的作业后备队列中挑选一个作业调入内存，并创建进程。每个作业只调入一次，调出一个，作业调入时会建立PCB，调出时才撤销PCB【也就是好几个程序需要启动，到底先启动哪个】

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

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

内存不够时，可将某些进程的数据调出外存，等内存空闲或者进程需要运行时再重新调入内存。暂时调到外存等待的进程状态称为挂起状态，被挂起的进程PCB会被组织成挂起队列。

中级调度（内存调度）：按照某种策略决定将哪个处于挂起状态的进程重新调入内存

进程调度的时机

如：打印机打印完成前，不应该让进程独占CPU又不做任何事情

进程调度的方式

调度器和闲逛进程

实际的系统中，CPU永远不可能空闲

闲逛进程就是调度程序永远的备胎，在没有其它就绪进程时，就运行闲逛进程idle

特性：

优先级最低
可以是0地址指令，占一个完整的指令周期（指令周期末尾例行检查中断）
能耗低

调度的目标（调度算法的评价）

CPU利用率：CPU忙碌的时间占总时间的比例，即忙碌的时间/总时间

也可以计算设备的利用率

对于多道程序并发执行的情况，可以用甘特图解答！

系统吞吐量：单位时间内完成作业的数量，即总共完成了多少道作业/总共花了多少时间，单位如：道/秒

周转时间：从作业被提交给系统开始，道作业完成为止的这段时间间隔。等于作业完成时间-作业提交时间

平均周转时间 = 各作业周转时间之和/作业数

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

调度算法

学习思路：算法思想、算法规则、用于作业调度还是进程调度、抢占式还是非抢占式、优缺点、是否会导致饥饿（某进程/作业长期得不到服务）

FCFS：先来先服务算法

SJF：短作业优先算法

HRRN：高响应比优先算法

RR：时间片轮转算法

优先级调度算法

多级反馈队列调度算法

多级队列调度算法

多处理机调度

用调度算法决定让哪个就绪进程优先上处理机
还需决定被调度的进程上哪个处理机

— 负载均衡、处理机亲和性

负载均衡：尽可能让每个处理机（CPU）同等忙碌

处理机亲和性：尽量让一个进程调度到同一个CPU上运行，以发挥CPU中缓存的作用（Cache）

同步与互斥

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

把一个时间段内只允许一个进程使用的资源称为临界资源，对临界资源的访问需要互斥地进行

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

进程互斥的软件实现方法

单标志法

问题：只能轮流访问，但是如果此时轮到P0使用，但是P0一直不使用？ — 违反空闲让进的原则

双标志先检查

双标志后检查

Peterson算法

未遵循让权等待

进程互斥的硬件实现方法

中断屏蔽方法（关中断）

TestAndSet指令

Swap指令

互斥锁

信号量机制

整型信号量

记录型信号量

用信号量机制实现进程互斥与同步机制

信号量的值 = 这种资源的剩余数量 — 若小于零，说明此时有进程在等待这种资源

P(S) = 申请一个资源S，如果资源不够就阻塞等待

V(S) = 释放一个资源S，如果有进程在等待该资源，则唤醒一个进程

生产者-消费者问题

多生产者-多消费者

苹果橘子盘子问题：

   父亲 ──放苹果──┐                  ┌──吃苹果── 女儿
                 ├──▶ [盘子 plate]──┤
    母亲 ──放橘子──┘   (容量只有 1)   └──吃橘子── 儿子

  规则:盘子一次只能放一个水果;父亲只放苹果、母亲只放橘子;女儿只吃苹果、儿子只吃橘子。
  
  
  错误的视角:"进程视角" → 组合爆炸

  如果你盯着"哪个进程必须在哪个进程之后"来分析,你会列出这些"一前一后"约束:

    女儿取苹果 ──之后──▶ 父亲才能放      ┐
    女儿取苹果 ──之后──▶ 母亲才能放      │  2×2 = 4 个
    儿子取橘子 ──之后──▶ 父亲才能放      │  "进程对"关系
    儿子取橘子 ──之后──▶ 母亲才能放      ┘
    
    → 你会误以为要设 4 个信号量。更糟的是,如果有 M 个放水果的、N 个取水果的,这个数字会变成M×N——组合爆炸。

⚠️ 这就是”从单个进程行为角度分析”的陷阱:你把”谁来执行”也当成了约束的一部分,于是约束数量随进程数的乘积膨胀。

"要把'一前一后'发生的事看做两种'事件'的前后关系"。

  换个眼光看那 4 条约束——它们左边都是同一件事,右边也都是同一件事:

          进程视角(4个)                事件视角(1个)
    ┌──────────────────────┐
    │ 女儿取苹果 ┐          │      "盘子变空"事件
    │ 儿子取橘子 ┘ 都是 →   │  ────────────┐
    │                       │              ▼
    │ 父亲放    ┐           │      "放水果"事件
    │ 母亲放    ┘ 都是 →    │  ◀───────────┘
    └──────────────────────┘   一条事件因果链:空了→才能放

  - "盘子变空" 这个事件:女儿吃 OR 儿子吃,都算。它们是同一类事件。
  - "放水果" 这个事件:父亲放 OR 母亲放,都算。也是同一类事件。

🔑 核心洞察:4 对”进程关系”在事件层面其实是同一条因果链:”盘子变空” → “放水果”。

一条事件关系,只需要一个同步信号量 plate 就够了。这正是图右边画的:父亲、母亲都做P(plate)(等盘子空);女儿、儿子都做 V(plate)(吃完使盘子变空)。