操作系统笔记——进程管理 2026.01.15 操作系统

进程基本概念

程序（Program） vs 进程（Process） vs 线程（Thread）

• 程序：是状态机的静态描述，是一组指令的有序集合
• 进程：是整个程序动态运行起来的状态机，有四个性质
• 线程：进程状态机中最小的独立执行控制流，是被调度的基本单元

进程包含了程序，数据（栈），PCB

进程的特点

• 并发性：多个进程在同一时间段内交替执行，是操作系统资源复用能力的体现。
• 动态性：进程是程序的执行过程，具有从创建到终止的完整生命周期。
• 独立性：每个进程拥有独立的资源和地址空间，一个进程的运行不影响其他进程。
• 异步性：由于调度和资源竞争，进程的执行速度不可预测，推进顺序不确定。

进程状态及转换

三种基本主要状态：就绪态，运行态，堵塞态

• 就绪态：被调度或分派 跳转 运行态
• 运行态：时间片用完回到 就绪态，遇到I/O等的等待事件，进入堵塞态
• 堵塞态：等待事件完成进入就绪态

扩展到五种状态就是多一个创建态和终止态

• 创建态：创建完成进程进入就绪态
• 终止态：运行完毕进入终止态

PCB（Process Control Block）

操作系统要管理上千个进程，为每个进程保存一些元数据，存储元数据的就是PCB

其描述进程的元数据信息，PCB 是进程的所有控制信息集合，是操作系统管理进程的元数据结构。

PCB 是进程存在的唯一标志，操作系统通过 PCB 来管理进程。

PCB 基本包含以下 5 类信息：

• 进程标识信息（PID）：唯一标识：进程号 PID，父进程号 PPID，用户 ID 等
• 处理机状态信息：保存进程被中断时的 CPU 现场，如 PC、各类寄存器、PSW。
• 进程调度信息：行进程状态（就绪/运/阻塞），调度优先级，时间片信息，等待队列指针
• 进程控制信息：进程使用的资源，打开的文件列表，消息队列/信号量等 IPC 信息，运行时间统计，进程间关系（父子进程）
• 内存管理信息：页表基址，段表，代码段/数据段所在地址

进程控制

详情见 博客（程序与进程&进程管理API）

进程同步

基本概念

• 临界资源：一次只允许一个进程使用的资源，例如：打印机，共享数据结构，全局变量
• 临界区：进程中访问临界资源的那一段代码。

同步机制四条准则

• 空闲让进：资源空闲,允许一个立即进入
• 忙则等待：资源被访问，其他进程必须等待
• 有限等待：保证等待访问的进程能在有限时间内进入
• 让权等待：不能进入临界区的进程应立即释放 CPU

进程互斥问题

进程互斥问题是操作系统中并发控制的一个基本问题，指的是：当多个进程（或线程）并发执行，并且需要访问同一临界资源时，必须保证在任意时刻只有一个进程进入临界区进行访问，否则会导致数据不一致或系统错误。

利用硬件方法 解决进程互斥问题

禁止中断

原理：

• 进程进入临界区前 关闭中断
• 离开临界区后 打开中断
• 由于单核 CPU 在关中断期间不会发生进程切换，因此可保证互斥

缺点：

• 不适用于多处理机，只能用于单处理机系统
• 影响系统响应性，增加风险

TSL（TAS Test-and-Set）指令实现互斥

bool TSL(bool *lock) {
  bool old = *lock;  // 测试
  *lock = true;      // 上锁
  return old;        // 返回旧值
}

原理：

• 通过一些手段将TSL函数原子化：早期主要依赖“内存总线封锁”，现代 CPU 多依赖“缓存一致性协议 + 缓存行锁定”。
• 使用方式： while (TestAndSet(&lock)) ;

缺点：会产生忙等待，不保证公平性，可能发生饥饿。

没有实现让权等待：“当进程因请求资源而不能继续执行时，应立即释放处理器（让出 CPU），而不是占用 CPU 等待。”

TSL并没有堵塞，而是反复持续运行循环，即自旋等待（忙等待）

SWAP 指令实现互斥

SWAP（Exchange）指令是一条硬件原子指令，用于原子地交换两个变量的值。

原理：

• SWAP函数本身就是原子的，和TSL类似。
• 使用方式：

do {
    key = true;
    SWAP(&lock, &key);
} while (key);

缺点：仍然是忙等待，仍然违背让权等待原则。

利用软件方法 解决进程互斥问题

严格轮换法（Strict Alternation）

原理：

• 用一个共享变量 turn
• 规定进程轮流进入临界区

int turn =0;// 0：P0，1：P1

// P0
while (turn !=0) ;
/* 临界区 */
turn =1;

// P1
while (turn !=1) ;
/* 临界区 */
turn =0;

缺点：仍然是忙等待，仍然违背让权等待原则。

标志法（Flag / Interested Variables）

原理：

• 每个进程用一个标志表示“是否想进入临界区”

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

// Pi
flag[i] =true;
while (flag[j]) ;
/* 临界区 */
flag[i] =false;

缺点：可能发生死锁，不保证互斥的正确推进，设置布尔值并非原子操作，违背忙则等待，让权等待。

Peterson算法

原理：

• 结合标志法与严格轮换法
• 用 flag[i] 表示进程是否想进入临界区
• 用 turn 表示在竞争时让谁优先
• 通过“先声明意愿，再主动让权”避免死锁并保证公平

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

// Pi (i = 0 or 1, j = 1 - i)
flag[i] =true;// 表示 Pi 想进入临界区
turn = j;// 主动让对方优先
while (flag[j] && turn == j) ;
/* 临界区 */
flag[i] =false;// Pi 离开临界区

缺点：

• 仍然是忙等待（自旋等待，占用 CPU）
• 违背让权等待原则（等待时不阻塞而是循环检查）
• 只适用于两个进程
• 对内存可见性和顺序一致性有假设（现代多核需内存屏障）

面包店算法（Bakery Algorithm）

原理：

• 由 Lamport 提出
• 模拟“面包店取号排队”的思想
• 进程进入临界区前先取一个递增的号码
• 号码小的优先进入，若号码相同则按进程号比较
• 适用于多个进程的互斥问题

#define N// 进程数

bool choosing[N] = {false};// 是否正在取号
int number[N] = {0};// 进程的号牌，0 表示未取号

// Pi
choosing[i] =true;
number[i] =1 + max(number[0..N-1]);
choosing[i] =false;

for (int j =0; j < N; j++) {
while (choosing[j]) ;// 等待 Pj 取号完成
while (number[j] !=0 &&
          (number[j] < number[i] ||
          (number[j] == number[i] && j < i))) ;
}

/* 临界区 */

number[i] =0;// 离开临界区，放弃号牌

缺点：

• 忙等待（自旋等待，占用 CPU）
• 违背让权等待原则
• 取号和比较过程开销较大
• 对共享变量的读写频繁，效率较低

利用锁机制

原理：

• 使用一个共享的锁变量表示临界资源的占用情况
• 进入临界区前必须先获取锁
• 退出临界区时释放锁

信号量机制

原理：

• 由 Dijkstra 提出
• 用一个整型变量表示可用资源数
• 通过两个原子操作实现同步与互斥：
  • P()（wait）
  • V()（signal）
• 当资源不可用时，进程阻塞等待

PV函数

P(S):
    S = S - 1;
    if (S < 0)  // 无资源，进程进入阻塞队列
        block(this_process);
        
V(S):
    S = S + 1;
    if (S <= 0)
        wakeup(one_process);  // 唤醒堵塞队列中的一个线程

使用方法：

semaphore S = 1;   // 互斥信号量
// Pi
P(S);              // 申请资源，若 S < 0 则阻塞
/* 临界区 */
V(S);              // 释放资源，唤醒等待进程

缺点：可能发生死锁

利用前驱图完成信号量设计

flowchart TB
    S1 -->|a| S2
    S1 -->|b| S3

    S2 -->|c| S4
    S2 -->|d| S5

    S3 -->|e| S6
    S4 -->|f| S6
    S5 -->|g| S6

设计信号量 abcdefg

• S1：{ S1, V(a), V(b) }
• S2：{ P(a), S2, V©, V(d) }
• S3：{ P(b), S3, V(e) }
• S4：{ P©, S4, V(f) }
• S5：{ P(d), S5, V(g) }
• S6：{ P(e), P(f), P(g), S6 }

每个状态“P 所有前驱信号，V 所有后继信号”，即可严格实现图中的并发与同步关系。

经典进程同步问题

进程关系分析方法

一共有两种约束，互斥约束和同步约束。

互斥约束需要考虑：是否有共享的资源，对于共享资源互斥

同步约束需要考虑：是否有先后的关系，某个操作必须在某个之后，通常和 full 满了，empty 空了 有关

生产者-消费者问题

问题描述

系统中存在两类并发进程：生产者进程和消费者进程。生产者进程负责生成数据（产品），并将其放入一个共享的有限缓冲区；消费者进程从该缓冲区中取出数据并进行处理。缓冲区的容量是有限的。

进程关系分析

• 互斥约束

  由于缓冲区是共享资源，任意时刻只允许一个进程对缓冲区进行操作，以防止数据不一致。

• 同步约束

  • 当缓冲区已满时，生产者必须等待；
  • 当缓冲区为空时，消费者必须等待。

因此设计信号量三个：Mutex队列锁，Full满信号，empty空信号

semaphore mutex = 1;   // 互斥信号量，保护缓冲区
semaphore empty = N;   // 空缓冲区数量
semaphore full  = 0;   // 满缓冲区数量

生产者进程（Producer）

Producer() {
    while (true) {
        produce_item();     // 生产产品

        P(empty);           // 等待空缓冲区
        P(mutex);           // 进入临界区

        put_item_into_buffer();

        V(mutex);           // 离开临界区
        V(full);            // 增加产品数量
    }
}

消费者进程（Consumer）

Consumer() {
    while (true) {
        P(full);            // 等待产品
        P(mutex);           // 进入临界区

        get_item_from_buffer();

        V(mutex);           // 离开临界区
        V(empty);           // 增加空缓冲区数量

        consume_item();     // 消费产品
    }
}

哲学家进餐问题

问题描述

哲学家进餐问题是由 Dijkstra 提出的一个经典并发同步与资源分配问题。

系统中有 5 位哲学家 围坐在一张圆桌旁，相邻的两位哲学家之间放置一根筷子，共 5 根筷子。哲学家的行为在以下两种状态之间反复交替：

• 思考（Thinking）
• 进餐（Eating）

每位哲学家在进餐时，必须同时拿起左右两根筷子；思考时不需要筷子。

进程关系分析

• 互斥约束

  每根筷子都是一种共享资源，同一时刻只能被一个哲学家占用，因此对筷子的访问必须满足互斥条件。

• 同步约束

  • 若哲学家未能同时获得左右两根筷子，则必须等待；

• 潜在问题

  若所有哲学家同时先拿起左边的筷子，再等待右边的筷子，则会形成循环等待，从而导致死锁。

信号量设计

为避免死锁，引入一个额外的信号量，限制最多只有 N−1N-1N−1 位哲学家同时尝试拿筷子，从而破坏循环等待条件。

semaphore room =4; // 最多允许 4 位哲学家进入竞争
semaphore chopstick[5] = {1,1,1,1,1}; // 每根筷子一个互斥信号量

哲学家进程（Philosopher i）

Philosopher(i) {
while (true) {
        think();// 思考

        P(room);// 进入餐厅，限制并发数量
        P(chopstick[i]);// 拿左筷子
        P(chopstick[(i +1) %5]);// 拿右筷子

        eat();// 进餐

        V(chopstick[i]);// 放下左筷子
        V(chopstick[(i +1) %5]);// 放下右筷子
        V(room);// 离开餐厅
    }
}

读者–写者问题

问题描述

系统中存在两类并发进程：

• 读者进程（Reader）：只读取共享数据，不修改数据；
• 写者进程（Writer）：对共享数据进行写操作。

共享数据在同一时刻允许多个读者同时读取，但写者必须独占共享数据。即：

• 读–读：允许并发
• 读–写：互斥
• 写–写：互斥

进程关系分析

• 互斥约束
  • 写者在写共享数据时，必须独占资源；
  • 任意时刻不能同时存在写者和其他读者或写者。
• 同步约束
  • 当有写者正在写时，后续读者必须等待；
  • 当有读者正在读时，写者必须等待。

不同策略

• 读者优先：只要系统中存在读者，写者就不能进入；读者无需等待其他读者，可直接进入读操作。写者可能饥饿；
• 写者优先：写者一旦到来，就阻塞所有后续到达的读者，直到所有写者完成写操作。但读者可能饥饿；
• 公平策略：所有到达的读者和写者按到达顺序排队，谁先到谁先服务。避免饥饿。

信号量设计（读者优先）

semaphore mutex =1;// 保护读者计数
semaphore wrt   =1;// 控制对共享数据的访问
int readcount =0;// 当前读者数量

读者进程（Reader）

Reader() {
while (true) {
    P(mutex);
    readcount++;
		if (readcount ==1)
      P(wrt);// 第一个读者阻止写者
    V(mutex);

    read_data();// 读共享数据

    P(mutex);
    readcount--;
		if (readcount ==0)
        V(wrt);// 最后一个读者释放写权限
    V(mutex);
  }
}

写者进程（Writer）

Writer() {
while (true) {
    P(wrt);// 独占访问
    write_data();// 写共享数据
    V(wrt);
  }
}

理发师问题（Sleeping Barber Problem）

问题描述

系统中有：

• 1 名理发师
• 1 把理发椅
• N 把等候椅

理发师在没有顾客时会睡觉；顾客来到理发店时：

• 若理发师空闲，则立即理发；
• 若理发师正在理发：
  • 若等候椅未满，顾客坐下等待；
  • 若等候椅已满，顾客离开。

进程关系分析

• 互斥约束
  • 理发椅同一时刻只能服务一个顾客；
  • 等候椅数量有限，需要互斥访问计数。
• 同步约束
  • 顾客到来时需要唤醒正在睡觉的理发师；
  • 理发师在没有顾客时应阻塞（睡眠），而不是忙等待。

信号量设计

semaphore customers =0;// 等待理发的顾客数
semaphore barber =0;// 理发师是否就绪
semaphore mutex =1;// 保护等候椅计数
int waiting =0;// 当前等待顾客数
constint CHAIRS = N;// 等候椅数量

理发师进程（Barber）

Barber() {
while (true) {
        P(customers);// 若无顾客则睡觉
        P(mutex);
        waiting--;// 顾客进入理发椅
        V(barber);// 唤醒一个顾客
        V(mutex);
        cut_hair();// 理发
    }
}

顾客进程（Customer）

Customer() {
    P(mutex);
if (waiting < CHAIRS) {
        waiting++;// 坐到等候椅
        V(customers);// 通知理发师有顾客
        V(mutex);
        P(barber);// 等待理发师
        get_haircut();// 理发
    }else {
        V(mutex);// 等候椅满，离开
        leave_shop();
    }
}

管程机制

管程就是统一封装共享资源。

管程的引入

早期常用的同步工具是信号量（Semaphore）。然而，信号量是一种低级同步机制，需要程序员显式地进行 P/V 操作，容易出现很多问题

为降低并发程序设计的复杂度、减少同步错误，Hoare 提出了管程（Monitor）机制，将共享资源及其同步控制统一封装，从程序结构上保证正确性。

管程的定义

管程将共享数据、对共享数据的操作以及同步机制封装在一个模块中，并由系统保证任意时刻只有一个进程能够进入管程，从而实现自动互斥。

条件变量（Condition Variable）

条件变量的作用

在管程中，虽然自动实现了互斥，但进程仍可能因为条件不满足而无法继续执行，此时需要一种机制让进程等待并被唤醒。

为此，管程引入了条件变量。

条件变量的基本操作

条件变量通常支持两种操作：

wait(c);    // 在条件变量 c 上等待
signal(c);  // 唤醒在条件变量 c 上等待的一个进程

其语义为：

• wait(c)：调用进程阻塞，并释放管程的使用权；
• signal(c)：唤醒一个因等待条件 c 而阻塞的进程。

条件变量的语义说明

在实际系统（如 Java、POSIX）中，普遍采用 Mesa 管程语义：

• signal 只是通知；
• 被唤醒进程需重新竞争进入管程；
• 条件判断应使用 while 而非 if。

利用管程解决生产者–消费者问题

问题回顾

系统中存在生产者和消费者进程，二者共享一个有限缓冲区：

• 缓冲区满时，生产者必须等待；
• 缓冲区空时，消费者必须等待；
• 对缓冲区的访问需要互斥。

管程设计

monitor BoundedBuffer {
  item buffer[N];
	int count =0;
	int in =0, out =0;
  condition notFull;
  condition notEmpty;

  procedureinsert(item x) {
		while (count == N)
	    wait(notFull);
	
    buffer[in] = x;
    in = (in +1) % N;
    count++;

    signal(notEmpty);
	 }

  procedureremove(item &x) {
		while (count ==0)
	    wait(notEmpty);

    x = buffer[out];
    out = (out +1) % N;
    count--;

    signal(notFull);
  }
}

生产者进程

Producer() {
while (true) {
    item x = produce_item();
    BoundedBuffer.insert(x);
  }
}

消费者进程

Consumer() {
while (true) {
    item x;
    BoundedBuffer.remove(x);
    consume_item(x);
  }
}

进程调度算法

进程提供很多属性作为调度算法的依据：

• 到达时间：进程创建提交的时间刻
• 估计运行时间：进程运行需要的时间长度
• 优先级：标识进程的优先顺序
• 等待时间：进程在就绪队列中等待被 CPU 调度执行的累计时间。

对于调度后的结果：

• 周转时间：完成时间 − 到达时间
• 加权周转时间：周转时间 / 运行时间

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

思想：

按照进程到达就绪队列的先后顺序运行，非抢占式。

特点：

• 实现简单
• 公平但可能导致 长作业阻塞短作业（队头效应 / Convoy Effect）

适用场景： 批处理系统、不要求响应速度的场合。

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

思想：

优先运行估计运行时间最短的进程。

特点：

• 平均等待时间最小、理论最优
• 需要预知作业运行时间 → 难以精确获得
• 非抢占式的 SJF，抢占式版本称 SRTF

问题：

可能导致长作业长期得不到调度 → 饥饿（Starvation）

高响应比优先（HRRN, Highest Response Ratio Next）

思想：

使用动态优先级解决 SJF 的饥饿问题。

公式：

响应比 = (等待时间 + 运行时间) / 运行时间

特点：

• 等待越久的进程响应比越高 → 不会饥饿
• 折中方案：短作业优先，同时保证公平性
• 非抢占式

优先级调度（Priority Scheduling）

思想：

进程携带优先级字段（系统/用户指定）；优先级高的先运行。

类型：

• 抢占式：运行中被更高优先级剥夺 CPU
• 非抢占式：只在进程切换时比较优先级

问题：

低优先级进程可能长期不被执行 → 饥饿

解决：

优先级老化（Aging）——等待越久，优先级逐步提高。

时间片轮转（RR, Round Robin）

思想：

每个进程按顺序轮流获得等长时间片（Quantum），时间片到即切换。

特点：

• 抢占式
• 非常适合交互式系统（如终端、GUI）
• 时间片过大 → 像 FCFS
• 时间片过小 → 上下文切换过多（开销大）

多级队列调度（Multilevel Queue Scheduling）

思想：

根据进程类型划分多个队列，每个队列独立调度策略，队列之间有固定优先级。

示例队列：

• 系统进程队列（最高优先级）
• 交互进程队列
• 批处理作业队列

特点：

• 不同队列之间优先级严格固定 → 下层队列可能饥饿
• 每个队列内部可使用 FCFS / RR / SJF 等

关键点：

队列之间 固定优先级，不允许进程跨队列移动。

多级反馈队列调度（MLFQ, Multilevel Feedback Queue）

思想：

最常用的交互式系统调度器，提供“动态优先级”。

规则核心（三大法则）：

1. 新进程进入最高优先级队列
2. 如果时间片用完 → 降低一个队列等级
3. 如果进程经常阻塞（I/O 频繁）→ 保持高优先级

特点：

• 自动分辨 I/O 型与 CPU 型进程
• 交互型进程响应极快
• CPU 密集型逐渐降到低优先级

现代实现：

Linux CFS 不直接是 MLFQ，但遵循类似思想。

进程通信

进程通信是指不同进程之间交换信息和进行协作的机制。由于进程具有独立的地址空间，一个进程不能直接访问另一个进程的数据，因此必须通过操作系统提供的通信机制完成信息交换与同步。

进程通信类型

共享存储器系统通信

基本思想：

由操作系统在多个进程的地址空间中映射同一块物理内存区域，进程通过读写该共享区域实现通信。共享内存区（Shared Memory），共享变量、共享缓冲区。

特点：

• 通信效率高（不需要内核频繁介入）
• 需要配合同步机制（如信号量、管程）防止数据不一致

优缺点：

• 优点：速度最快
• 缺点：同步控制复杂，易出现竞态条件

消息传递系统通信

基本思想：

进程之间不直接共享内存，而是通过发送/接收消息完成通信，所有消息由操作系统管理。

通信方式：

• 直接通信：指定发送进程和接收进程，由OS实现的send和receive。
• 间接通信：通过信箱（Mailbox）（私用信箱，公用信箱，共享信箱）或消息队列

特点：

• 通信效率高，简化编程复杂度，信箱实现非实时通信

典型机制：

• 消息队列
• Socket（套接字）
• RPC（远程过程调用）

管道通信

基本思想：

管道是一种半双工的字节流通信机制，数据只能单向流动。

用于连接一个发送进程和一个接收进程，以实现它们之间通信的共享文件(pipe文件,又称为FIFO文件) 。每个管道文件被打开后,都有两个文件描述符fd[0] (用于从管道读数据)和fd[1] (用于向管道写数据)

类型：

• 匿名管道：仅用于具有亲缘关系的进程（如父子进程），临时文件存储在高速缓存中
• 命名管道（FIFO）：可用于无亲缘关系进程，可长期存储在磁盘

特点：

• 数据按 FIFO 顺序传输
• 无结构字节流
• 读空阻塞、写满阻塞

应用场景：

• Linux 命令行：ls | grep txt

客户-服务器系统通信（C/S模式）

基本思想

通信双方分为：：

• 客户进程（Client）：发出请求
• 服务器进程（Server）：提供服务并返回结果

通信机制：

• Socket
• 消息队列
• RPC / RMI

特点：

• 支持分布式系统
• 扩展性强
• 通信过程复杂

消息缓冲队列通信机制

基本思想

消息缓冲队列通信是一种以消息为单位的进程通信方式。

操作系统为每个进程维护一个消息队列，进程之间通过发送和接收消息缓冲区进行通信。

消息本身不直接在进程之间共享，而是通过内核管理的消息缓冲区完成传递，从而实现进程间的隔离与安全通信。

相关数据结构

消息缓冲区

struct message_buffer {
    int sender;          // 发送进程ID
    int receiver;        // 接收进程ID
    int type;            // 消息类型
    int size;            // 消息长度
    char data[];         // 消息正文
    struct message_buffer *next; // 下一个消息指针
};

维护一个消息队列

发送原语：send

功能：将一条消息从发送进程传送到指定接收进程的消息队列中。

步骤：

1. 发送进程事先在自身地址空间中设置发送区，并填入待发送的消息；
2. 发送进程调用 send 原语，向操作系统申请一个消息缓冲区；
3. 操作系统将发送区中的消息复制到该消息缓冲区中；
4. 操作系统将该消息缓冲区挂入接收进程的消息队列；
5. 若接收进程因等待消息而阻塞，则将其唤醒。

接收原语：receive

功能：从本进程的消息队列中接收一条消息。

步骤：

1. 若本进程消息队列为空，则接收进程阻塞等待；
2. 从自身的消息队列中取出一个消息缓冲区；
3. 将消息缓冲区中的数据复制到自己的接收区；
4. 释放该消息缓冲区，归还给系统。

进程死锁

死锁是指一组进程相互等待对方占有的资源，导致所有进程都无法继续执行。

判断是否存在死锁

构建资源分配图 / 等待图：

• 无环：一定没有死锁
• 有环：
  • 每一类资源只有一个实例：必定死锁
  • 每一类资源不只有一个实例：可能死锁

预防死锁

死锁预防的基本思想是：

在系统设计阶段，主动破坏死锁产生的四个必要条件之一或多个，从而保证死锁不可能发生。

死锁的四个必要条件：

• 互斥
• 占有且等待
• 不可剥夺
• 循环等待

破坏“占有且等待”条件

占有且等待是指：

进程已占有部分资源，同时又申请新的资源，并在申请未满足时保持对已占有资源的占有。

破坏方式两种：

• 一次性申请所有资源，即进程在开始执行前：
  • 必须一次性申请它运行所需的全部资源，若资源不满足，则不分配任何资源
  • 进程要么全拿到，要么一个都不拿，不存在“占有一部分再等待”的情况
• 申请新资源前先释放已占有资源，即进程在申请新资源前：
  • 必须释放已占有的所有资源
  • 之后再重新申请所需资源

优点：

• 实现简单
• 能从根本上消除占有且等待

缺点：

• 资源利用率低
• 可能造成进程长期饥饿
• 进程难以预先准确知道所需全部资源

破坏“不可剥夺”条件（**仅适用于可剥夺资源：**CPU、内存等）

不可剥夺是指：

进程已获得的资源，在未使用完之前，不能被强制剥夺，只能由进程主动释放。

破坏方式：

当进程请求某资源失败时：

• 系统强制剥夺该进程已占有的资源，进入堵塞
• 或者判断是否能从其他堵塞进程进行剥夺
• 等该进程重新获得所需资源后，再继续执行

优点：

• 可打破进程之间的“僵持状态”

缺点：

• 实现复杂
• 易造成进程回滚和性能下降
• 可能造成进程饥饿

破坏“循环等待”条件

循环等待是指：

存在一个进程集合，集合中的每个进程都在等待下一个进程所占有的资源，形成环路。

破坏方式（资源有序分配法）：

• 对系统中所有资源类型进行统一编号
• 规定：进程只能按资源编号递增的顺序申请资源

例如：

• R1 → R2 → R3
• 进程申请顺序只能是 R1 再 R2，再 R3
• 不允许先申请 R3 再申请 R1

优点：

• 理论上最干净、最彻底
• 广泛用于数据库系统、文件锁设计

缺点：

• 编程不灵活
• 对资源使用顺序限制严格
• 可能降低并发度

避免死锁

对于线程而言，会有非常多种资源，每个资源都有一定的数量。

一个进程需求各种资源，例如在某个时刻，可能对A类型要3个，B类型要1个，某时刻A类型要1个，B类型要3个。

最大资源需求：是每一种资源都计算最大数量。例如上面的例子就是 3, 3

安全状态

如果系统存在一个进程序列 ⟨P1, P2, …, Pn⟩，使得： 对序列中的每一个进程 Pi，在它提出最大资源需求时，系统当前可用资源 + 所有排在它前面的进程最终释放的资源，都能够满足 Pi 的最大需求，则称系统处于安全状态，该序列称为安全序列。

安全状态不可能死锁，不安全状态可能死锁。

银行家算法

系统中有 m 类资源，n 个进程。

可用资源向量 Available

Available[j]：系统中第 j 类资源的可用数量

最大需求矩阵 Max ： Max[i][j] 进程 i 对第 j 类资源可能需要的最大数量

已分配矩阵 Allocation ： Allocation[i][j] 当前已分配给进程 i 的第 j 类资源数量

需求矩阵 Need ： Need[i][j] = Max[i][j] − Allocation[i][j]

资源请求算法（Request Algorithm）

当进程 Pi 请求资源 Request[i] 时：

1. 合法性检查

   Request[i] ≤ Need[i] ？

   否 → 错误请求

2. 可用性检查

   Request[i] ≤ Available ？

   否 → 进程阻塞等待

3. 试探性分配

   Available -= Request[i]
   Allocation[i] += Request[i]
   Need[i] -= Request[i]

4. 安全性检查

   • 若系统仍安全 → 正式分配
   • 否 → 回滚分配，进程等待

死锁检测与解除

Coffman算法

Coffman 算法用于分析和判断死锁产生的必要条件。

该算法指出：当系统同时满足四个必要条件时，可能发生死锁；若破坏其中任意一个条件，则可以避免或解除死锁。

Coffman 死锁四个必要条件

1. 互斥条件（Mutual Exclusion）

   至少存在一种资源在同一时刻只能被一个进程占有。

2. 请求并保持条件（Hold and Wait）

   进程在已占有部分资源的情况下，又继续请求新的资源，并保持已占有资源不释放。

3. 不可剥夺条件（No Preemption）

   进程已获得的资源在使用完之前，不能被系统强制剥夺，只能由进程主动释放。

4. 循环等待条件（Circular Wait）

   系统中存在一个进程循环等待链，每个进程都在等待下一个进程所占有的资源。

结论

• 四个条件同时成立 → 系统可能发生死锁
• 破坏任意一个条件 → 可避免或解除死锁