操作系统进程互斥的四种软件实现和三种硬件实现

进程互斥是操作系统中保证多个进程不会同时访问共享资源的一种机制。

进程互斥的四种软件实现方式：

一、单标志法

• 核心思想：使用一个布尔变量（或称为标志位）来表示临界区的访问权限。该变量为true时表示允许某个进程访问临界区，为false时表示不允许。

• 实现方式：

  • 初始化时，标志位设为false，表示没有进程可以访问临界区。
  • 进程在进入临界区之前，会检查这个标志位。如果标志位为false，则进程会等待（通常是通过循环检查）；如果标志位为true，则进程可以进入临界区，并将标志位设为false，表示其他进程不能进入。
  • 进程退出临界区时，将标志位重新设为true，表示允许其他进程进入。

// 假设有一个全局布尔变量 flag，初始化为 false
boolean flag = false;// 进程 A 的代码
while (true) {while (flag); // 忙等待，直到 flag 为 falseflag = true;  // 进入临界区// 临界区代码flag = false; // 退出临界区// 非临界区代码
}// 进程 B 的代码与进程 A 类似，只是变量名和逻辑上是独立的（但在这个例子中共享了 flag）

• 优缺点：

  • 优点：实现简单。
  • 缺点：不遵循“空闲让进”原则，即如果当前进程不访问临界区，即使临界区空闲，其他进程也无法访问。

二、双标志先检查法

• 核心思想：使用两个布尔变量（或称为标志数组）分别表示两个进程是否想要进入临界区。

• 实现方式：

  • 每个进程在进入临界区之前，先检查另一个进程的标志位。如果另一个进程的标志位为false（表示不想进入临界区），则将自己的标志位设为true，并尝试进入临界区。
  • 如果另一个进程的标志位为true，则当前进程会等待。

// 假设有两个全局布尔变量 flagA 和 flagB，分别表示进程 A 和进程 B 是否想要进入临界区
boolean flagA = false, flagB = false;// 进程 A 的代码
while (true) {flagA = true; // 表示想要进入临界区while (flagB); // 如果进程 B 也想进入临界区，则等待// 临界区代码flagA = false; // 退出临界区// 非临界区代码
}// 进程 B 的代码与进程 A 类似，只是使用 flagB 而不是 flagA

注意：双标志先检查法存在竞态条件，即两个进程可能同时修改标志位并同时进入临界区。

• 优缺点：

  • 优点：相比单标志法，双标志先检查法在一定程度上提高了灵活性。
  • 缺点：违反了“忙则等待”原则，因为在“检查”和“上锁”之间可能发生进程切换，导致两个进程同时进入临界区。

三、双标志后检查法

• 核心思想：也是对双标志先检查法的改进，采用先“上锁”后“检查”的方法来避免两个进程同时进入临界区的问题。

• 实现方式：

  • 进程在进入临界区之前，先将自己的标志位设为true，表示想要进入临界区。
  • 然后检查另一个进程的标志位。如果另一个进程的标志位也为true，则当前进程会放弃进入临界区，并将自己的标志位重新设为false。
  • 如果另一个进程的标志位为false，则当前进程可以进入临界区。

// 假设有两个全局布尔变量 wantA 和 wantB，以及一个整型变量 turn，初始化为 0（表示先让进程 A）
boolean wantA = false, wantB = false;
int turn = 0; // 0 表示进程 A 的回合，1 表示进程 B 的回合// 进程 A 的代码
while (true) {wantA = true; // 表示想要进入临界区turn = 1;     // 设置 turn 为 B 的回合（但这一步是“后检查”的一部分）while (wantB && turn == 1); // 如果进程 B 也想进入且是 B 的回合，则等待// 临界区代码wantA = false; // 退出临界区// 非临界区代码
}// 进程 B 的代码与进程 A 类似，只是使用 wantB 和将 turn 设置为 0

注意：双标志后检查法解决了双标志先检查法中的竞态条件问题。

• 优缺点：

  • 优点：解决了双标志先检查法中两个进程可能同时进入临界区的问题。
  • 缺点：违背了“空闲让进”和“有限等待”原则，可能导致某些进程长期无法访问临界资源，产生“饥饿”现象。

四、Peterson算法

• 核心思想：通过引入一个额外的变量（通常称为turn）和一个“让权”机制来解决进程互斥问题。

• 实现方式：

  • 初始化时，turn变量设为某个进程的编号（假设为0）。
  • 进程在进入临界区之前，会检查turn变量是否等于自己的编号。如果不等，则进程会等待（通常是通过循环检查）。
  • 如果turn变量等于自己的编号，进程还需要检查另一个进程的标志位是否为false。如果为true，则进程也会等待。
  • 只有当turn变量等于自己的编号且另一个进程的标志位为false时，进程才能进入临界区。
  • 进程退出临界区时，会将自己的标志位设为false，并将turn变量设为另一个进程的编号，表示允许另一个进程进入临界区。

• 优缺点：

  • 优点：Peterson算法遵循了“空闲让进”、“忙则等待”和“有限等待”三个原则。
  • 缺点：未遵循“让权等待”原则，即进程在等待进入临界区时会持续占用CPU进行忙等。

// 假设有一个全局信号量 mutex，初始化为 1
Semaphore mutex = 1;// 进程 A 的代码
while (true) {P(mutex); // 请求进入临界区（P 操作是“等待”信号量的意思）// 临界区代码V(mutex); // 退出临界区（V 操作是“释放”信号量的意思）// 非临界区代码
}// 进程 B 的代码与进程 A 类似，只是逻辑上是独立的（但在这个例子中共享了 mutex）

注意：信号量是实现进程同步和互斥的一种有效机制，但这里的伪代码只是为了说明概念。在实际应用中，你需要使用操作系统提供的信号量 API（如 POSIX 信号量）来实现。

在实际编程中，你通常会使用操作系统提供的同步原语（如互斥锁、信号量等）来实现进程互斥，而不是直接编写这些低级的算法。这些同步原语通常已经过优化和测试，能够提供更好的性能和可靠性。

进程互斥的硬件实现方式:
中断屏蔽方法、TestAndSet（TS）指令和Swap指令。

一、中断屏蔽方法

• 核心思想：利用“开/关中断指令”实现进程互斥。即在某进程开始访问临界区到结束访问为止都不允许被中断，也就不能发生进程切换，因此也不可能发生两个进程同时访问临界区的情况。

• 实现方式：在进程访问临界区之前，先执行一个关中断指令，阻止当前进程被中断。直到当前进程访问完临界区后，再执行开中断指令，允许其他进程被调度和执行。

• 优缺点：

  • 优点：简单、高效。由于中断被屏蔽，因此不会出现进程切换，从而保证了进程互斥。
  • 缺点：只适用于单处理机系统，并且只适用于操作系统内核进程，不适用于用户进程。因为开/关中断指令只能运行在内核态，如果用户进程能够随意使用这组指令，将会对系统的稳定性和安全性造成威胁。

二、TestAndSet（TS）指令

• 核心思想：TestAndSet指令是一种硬件支持的原子操作，用于检测并设置某个变量的值。在进程互斥的实现中，该指令可以用于检测临界区是否被锁定，并尝试设置锁定标志。

• 实现方式：

  • 初始化时，设置一个布尔变量（如lock）为false，表示临界区未被锁定。
  • 进程在进入临界区之前，执行TestAndSet指令。该指令会原子地检查lock的值，如果为false，则将其设置为true，并返回false；如果为true，则返回true。
  • 如果TestAndSet指令返回false，表示临界区未被锁定，进程可以进入临界区。如果返回true，则表示临界区已被其他进程锁定，当前进程需要等待。

• 优缺点：

  • 优点：实现简单，适用于多处理机环境。由于TestAndSet指令是硬件实现的原子操作，因此不需要担心逻辑漏洞。
  • 缺点：不满足“让权等待”原则。当临界区被锁定时，等待的进程会占用CPU并循环执行TestAndSet指令，导致“忙等”。这可能会浪费CPU资源，并降低系统的吞吐量。

三、Swap指令

• 核心思想：Swap指令（也称为Exchange指令或XCHG指令）是另一种硬件支持的原子操作，用于交换两个变量的值。在进程互斥的实现中，Swap指令可以用于交换临界区的锁定标志和当前进程的标志。

• 实现方式：

  • 初始化时，设置一个布尔变量（如lock）为false，表示临界区未被锁定。同时，为每个进程设置一个标志变量（如old），用于记录临界区的锁定状态。
  • 进程在进入临界区之前，执行Swap指令。该指令会原子地交换lock和old的值。
  • 如果Swap指令执行后，old的值为false，表示之前没有其他进程对临界区上锁，因此当前进程可以进入临界区。如果old的值为true，则表示临界区已被其他进程锁定，当前进程需要等待。

• 优缺点：

  • 优点：实现简单，适用于多处理机环境。与TestAndSet指令类似，Swap指令也是硬件实现的原子操作，因此不需要担心逻辑漏洞。
  • 缺点：同样不满足“让权等待”原则。当临界区被锁定时，等待的进程会占用CPU并循环执行Swap指令，导致“忙等”。