面试题：并发与同步：操作系统临界区问题的经典解决方案简述

Question

请简述操作系统中解决临界区问题的经典方法，如 Peterson 算法和信号量机制，说明它们各自是如何实现对临界区的互斥访问以及解决进程同步问题的，并且阐述它们的优缺点。

Answer 1

Peterson 算法

1. 实现互斥访问与进程同步： Peterson 算法通过共享变量和标志位来实现进程间的同步。假设有两个进程 P0 和 P1，算法利用两个标志位（flag[0] 和 flag[1]）表示进程是否想要进入临界区，以及一个变量 turn 来表示轮到哪个进程进入临界区。 当一个进程想要进入临界区时，先设置自己的标志位为 true，表示自己想进入，然后将 turn 设置为对方进程，这就相当于礼让对方。在进入临界区之前，会不断检查对方的标志位以及 turn，如果对方想进入且 turn 是对方，就一直等待。这样就保证了同一时间只有一个进程能进入临界区。
2. 优点：
   • 算法简单，易于理解和实现。
   • 不需要特殊的硬件支持，纯软件实现。
3. 缺点：
   • 只适用于两个进程的情况，扩展性差。如果要支持多个进程，算法的复杂度会显著增加。
   • 忙等待问题，在等待进入临界区时，进程会不断循环检查条件，浪费 CPU 资源。

信号量机制

1. 实现互斥访问与进程同步： 信号量是一个整型变量，通过一个计数器来控制对临界区的访问。当信号量的值大于 0 时，表示有可用的资源（即可以进入临界区），进程可以通过执行 P 操作（也叫 wait 操作）来获取信号量，此时信号量的值减 1。如果信号量的值为 0，表示临界区已被占用，进程会被阻塞，放入等待队列。当进程离开临界区时，执行 V 操作（也叫 signal 操作），使信号量的值加 1，唤醒等待队列中的一个进程。 对于互斥信号量，初始值通常设为 1。这样就保证了同一时间只有一个进程能通过 P 操作进入临界区，实现了互斥访问。对于同步信号量，初始值根据同步需求设置，通过 P、V 操作来协调进程间的执行顺序。
2. 优点：
   • 通用性强，可以很方便地应用于单处理器或多处理器环境，支持多个进程的同步与互斥。
   • 解决了忙等待问题，当信号量为 0 时，进程会被阻塞，不会浪费 CPU 资源。
3. 缺点：
   • 信号量的使用需要谨慎，若 P、V 操作使用不当，可能会导致死锁。
   • 由于涉及到进程的阻塞与唤醒，上下文切换开销较大。