Peterson算法&&信号量实现屏障

Q1：详细分析Peterson算法如何实现进程互斥，并且分析方法巧妙之处。

完整的Peterson算法如下，其中最主要的进程互斥部分用红色标出。

两个主要的全局变量为：interested[i]，用来表示i进程是否要访问临界区；turn代表轮到谁去访问临界区域了。

在while()这一行中，当轮到process访问但另一个进程正在访问时，则会堵塞。整个算法 最精妙的部分就在这里，下面我将分别讨论如果这两个条件只有其中一个是否能够完成任务。

1. 当只有turn时。此时也就代表轮到谁谁就可以访问，而另一个只能等待。又因为turn指向的永远是两个进程中的一个，而进程又不是时时刻刻都需要访问临界区，这时候就可能出现turn所指向的进程占用临界区但不使用内部数据的情况，导致另一个进程也无法访问临界区。
2. 当只有interested[i]时。考虑其代码结构的堵塞部分为while(interested[other] == true);，倘若两个进程同时需要访问，这时数组几乎同时置为true，这也就导致两个进程的while()都将会执行，且陷入死循环中。

因此将两个标志进行结合，能够有效的解决上述情况：

1. 针对情况1，interested[i]数组能够控制是否访问临界区。
2. 针对情况2，turn能够保证始终指向其中一个进程，使另外一个的(turn == process) == False，跳出循环访问临界区，避免死循环。

---

Q2：如何使用信号量方法实现屏障（Barrier）

在这里给出实现的伪代码：

// 定义全局变量和信号量
count = 0  // 计数器，跟踪到达屏障的进程数量
mutex = Semaphore(1)  // 互斥信号量，保护对计数器的访问
barrier = Semaphore(0)  // 屏障信号量，用于控制进程的等待和释放
// 进程在屏障处执行的代码
function barrier_code():
    // 执行自己的任务
    // ...

    // 进入屏障之前的代码
    mutex.wait()  // 互斥操作，防止多个进程同时修改计数器
    count = count + 1  // 将计数器递增1
    mutex.signal()  // 释放互斥信号量

    // 检查是否所有进程都到达屏障
    if count == num_processes:
        barrier.signal()  // 释放屏障信号量，唤醒等待的进程

    barrier.wait()  // 进程进入等待状态，等待其他进程到达屏障
    barrier.signal()  // 释放屏障信号量，允许其他进程继续执行

下面我将对其进行详细的解释：

1. mutex：这是对计数器的保护。能够注意到其初值为1，当有一个进程需要count+1时候，mutex会因为wait()函数减一而变为0，此时其它进程走到这里时变会进行等待，知道计数器加1后执行了signal()，其它进程 才能够继续访问计数器。

2. barrial：进程到达之前都是0或者负值，到达后取正值。其初始值为0，当count<num_processes时，其他进程都会执行到barrier.wait()后进行等待，因为barrier的值一直小于等于0。知道if判断条件成立后，barrier.signal()使得队列中第一个等待的进程被激活，而后最后一个进程进入等待队列。因为第一个进程下一条语句为barrier.signal()，因此队列中的进程再次被释放。以此类推形成连锁反应，最终所有进程都被释放，也就达到了所有进程在此处同时继续运行的效果。而barrier的数值最终会变为
   $$
   barrier_ori + num_{signal} - num_{wait}=0+num_processes+1-num_processes=1
   $$

整个系统以最基本的信息量为基础，通过barrier与mutex的PV操作，实现了barrier，实现了多进程的并发。