实现临界区互斥的基本方法

🧑‍💻 作者: 一可爱小白兔

📦 版本: 1.0.0

📄 字数(字): 0

⏳ 时长(min): 0

⏱️ 更新于: 2026-02-03

单标志法

• 算法思想： 规定 turn = 0 时，允许 P0 访问临界区；turn = 1 时，允许 P1 访问临界区

• 伪代码

int turn = 0;

cobegin
P0() {
    while(turn != 0)
        ;
    critical section;
    turn = 1;
    remainder section;
}

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

Notes

(1) 违背【空闲让进】
(2) 两个进程必须轮流访问(只适合两个进程)；如果此时允许 P0 进程访问，但 P0 进程不访问，则 P1 进程永远无法访问临界区

双标志法先检查法

• 算法思想

  • 规定 flag[i] = true 表示 Pi 进程想要进入临界区
  • 每个进程先检查对方是否想进入临界区，若对方没有意愿，则将自身的 flag[i] = ture，之后再访问临界区

• 伪代码

bool flag[2] = {};

cobegin
P0() {
    while (flag[1])    // 进入区 [1]
        ;
    flag[0] = true;    // 进入区 [2]
    critical section;
    flag[0] = false;
    remainder section;
}

P1() {
    while(flag[0])     // 进入区 [3]
        ;
    flag[1] = true;    // 进入区 [4]
    critical section;
    flag[1] = false;
    remainder section;
}
coend

Notes

(1) 违背【忙则等待】
(2) 若按照[1]、[3]、[2]、[4]···的顺序执行，P0和P1会同时访问临界区

双标志后检查法

• 伪代码

bool flag[2] = {};

cobegin
P0() {
    flag[0] = true;    // 进入区 [1]
    while (flag[1])    // 进入区 [2]
        ;
    critical section;
    flag[0] = false;
    remainder section;
}

P1() {
    flag[1] = true;   // 进入区 [3]
    while(flag[0])    // 进入区 [4]
        ;
    critical section;
    flag[1] = false;
    remainder section;
}
coend

Notes

(1) 违背【空闲让进】和【有限等待】
(2) 若按照[1]、[3]、[2]、[4]···的顺序执行，P0 和 P1 都会陷入 while 死循环，都无法进入临界区，造成了“饥饿”

Peterson 算法

• 伪代码

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

cobegin
P0() {
    flag[0] = true;               // 进入区 [1]
    turn = 1;                     // 进入区 [2]
    while (flag[1] && turn == 1)  // 进入区 [3]
        ;
    critical section;
    flag[0] = false;
    remainder section;
}

P1() {
    flag[1] = true;               // 进入区 [4]
    turn = 0;                     // 进入区 [5]
    while (flag[0] && turn == 0)  // 进入区 [6]
        ;
    critical section;
    flag[1] = false;
    remainder section;
}
coend

Notes

(1) 进程可互斥访问临界区，不会出现“饥饿”现象 (2) 单标志和双标志后检查的合体 (3) 违背【让权等待】 (4) flag[] 和 turn 的作用

变量	作用	类比
flag[i]	表达意愿：flag[i] = true 表示进程 Pi 想进入临界区。它是进入临界区的前提条件。	就像举起手说：“我想发言”。
turn	解决争端：当两个进程都想进时，turn 决定谁先谁后。它实现了公平的礼让机制。	就像说：“你先请”，最后说“你先请”的人，实际上是在等待对方。

• 典型场景
  • 情况 1：P1 不想进 (flag[1] == false)
    • 条件 (false && ...) 为 false
    • P0 立即跳出循环，进入临界区。turn 的值无关紧要
  • 情况 2：P1 想进 (flag[1] == true) 但 turn == 0
    • turn == 0 意味着是 P1 设置了 turn = 0，表示“我让 P0 先”
    • 条件 (true && false) 为 false
    • P0 立即跳出循环，进入临界区。P1 会因为 turn == 0 而等待。
  • 情况 3：P1 想进 (flag[1] == true) 且 turn == 1
    • 条件 (true && true) 为 true。
    • P0 进入自旋等待。
    • 此时，P1 也在执行它的代码。P1 会检查 (flag[0] && turn == 0)。
      • flag[0] 是 true (P0 想进)。
      • turn 是 1 (不是 0)。
      • 所以 P1 的条件 (true && false) 为 false，P1 跳出循环，进入临界区。
    • P0 一直等到 P1 离开临界区（flag[1] = false），条件变为 false，然后 P0 才能进入。

TS 指令

• 算法思想
  • 为每个临界资源设置一个共享布尔变量 lock （临界资源的状态），初值为 false，true 表示被占用，false 表示未被占用

读出标志并设置为 true，并返回旧值

• 伪代码

bool TS(bool *lock) {  // 原子操作
    bool old = *lock;
    *lock = true;
    return old;
}

bool lock = false; // 全局锁变量

cobegin
Pi() {
    while(TS(&lock))   // 加锁：自旋等待直到 TS 返回 false
         ;
    critical section;
    lock = false;      // 解锁
    remainder section;
}
coend

Notes

(1) 执行 while(TS(&lock)) 时，自旋等待中自身进程一直处于运行态，不会主动放弃 CPU，时间片到，转为就绪态
(2) 违背【让权等待】

Swap 指令

• 算法思想

  • 为每个临界资源设置一个共享布尔变量 lock （临界资源的状态），初值为 false，true 表示被占用，false 表示未被占用
  • 为每个进程设置一个局部变量 key，初值为 true，用于获取锁

• 伪代码

void Swap(int *a, int *b) {  // 原子操作
    int temp = *a;
    *a = *b;
    *b = temp;
}

bool lock = false;            // 全局锁变量

cobegin
Pi() {
    bool key = true;          // 进程程本地钥匙变量，每个试图获取锁的进程都拥有一个钥匙变量
    while(key)                // 加锁：自旋直到交换成功且 key 被设为 false
        Swap(&lock, &key);
    critical section;
    lock = false;             // 解锁
    remainder section;
}
coend

Notes

违背【让权等待】