一条河上架设了由若干个桥墩组成的一座桥。若一个桥墩只能站一个人，过河的人只能沿着桥向前走而不能向后退。过河时，只要对岸无人过，就可以过。但不允许河对岸的两个人同时过，以防止出现死锁。请给出两个方向的人顺利过河的同步算法

假设有两个方向的人，分别从A岸和B岸出发过桥，过桥的人用数字1、2、3……表示。

同步算法如下：

1. 每个人先尝试去获取信号量S1（对岸无人过），若获取成功，则继续执行；若获取失败，则等待。

2. 在获取S1信号量成功后，先尝试获取S2信号量（过桥权限），若获取成功，则可以开始过桥了；若获取失败，则释放S1信号量，等待重新获取。

3. 过桥时，先将自己的方向标志位标记为占用，表示当前方向有人在过桥，防止对岸的人同时过来。然后等待一段时间（比如1秒），模拟过桥时间。

4. 过桥完成后，先释放S2信号量，表示过桥权限已经释放，然后将自己的方向标志位标记为未占用，表示当前方向无人在过桥。

5. 最后释放S1信号量，表示对岸可以继续过桥了。

注意事项：

1. 为了避免死锁，需要确保对岸的人在获取S1信号量时也是阻塞等待的，只有当当前方向的人过桥完成后才能获取S1信号量。

2. 为了防止同时过桥，需要在过桥前将自己的方向标志位标记为占用。在过桥完成后才能释放方向标志位，这样才能保证对岸的人不会同时过来。

3. 为了模拟过桥时间，需要在过桥时等待一段时间，可以使用sleep()函数实现。

相关问题

7．一条河上架设了由若干个桥墩组成的一座桥。若一个桥墩只能站一个人，过河的人只能沿着桥向前走而不能向后退。过河时，只要对岸无人过，就可以过。但不允许河对岸的两个人同时过，以防止出现死锁。请给出两个方向的人顺利过河的同步算法。

这是一个经典的同步问题：河对岸的两个人不能同时过桥，且需要保证所有人都能安全过河。

一种解决方法是使用信号量来实现同步。我们可以定义两个信号量，一个表示左岸有人等待过河，一个表示右岸有人等待过河。将这两个信号量的初值都设置为0。每个人都是一个独立的进程，都需要先获取自己岸边的信号量，然后再获取对岸的信号量，最后过河。过河完成后，先释放对岸的信号量，再释放自己岸边的信号量。

具体伪代码如下：

Semaphore left_wait = 0; // 左岸等待信号量
Semaphore right_wait = 0; // 右岸等待信号量

// 左岸进程
while (true) {
    // 过河前等待左岸信号量
    wait(left_wait);
    // 过河前获取右岸信号量
    wait(right_wait);

    // 过河操作

    // 过河后释放右岸信号量
    signal(right_wait);
    // 过河后释放左岸信号量
    signal(left_wait);
}

// 右岸进程
while (true) {
    // 过河前等待右岸信号量
    wait(right_wait);
    // 过河前获取左岸信号量
    wait(left_wait);

    // 过河操作

    // 过河后释放左岸信号量
    signal(left_wait);
    // 过河后释放右岸信号量
    signal(right_wait);
}

使用信号量可以保证同步，避免死锁，但需要注意的是，如果过河的人数很多，这种方法可能会导致信号量争用，从而导致效率下降。此时可以考虑其他同步机制，如条件变量等。

5.一条河上架设了由若干个桥墩组成的一座桥。若一个桥墩只能站一个人，过河的人只能沿着桥向前走而不能向后退。过河时，只要对岸无人过，就可以过。但不允许河对岸的两个人同时过，以防止出现死锁。请给出两个方向的人顺利过河的同步算法。 分析： ① 约束： a) 桥属于临界资源，两岸的人对该资源进行竞争； b) 桥上的人数是有限制的，设这个桥由N个桥墩构成，桥上同时只能有N个人过桥，其它人要进行等待。相当于共享资源数。

同步算法如下：

1. 初始化：设两岸的人数分别为M和N，桥上没有人。定义两个信号量empty和full，分别表示桥上是否空闲和是否满员。初始状态empty=1，full=0。

2. 两个方向的人都有一个线程，分别称为left和right。每个线程都要从一个岸出发，过桥到另一个岸。

3. left线程的执行过程如下：

a) 尝试获取empty信号量，如果可以获取则表示桥上没有人，可以过桥。

b) 获取到empty后，尝试获取full信号量，如果获取不到则等待，直到获取到full为止。

c) 获取到full后，表示桥上已经有N个人了，可以开始过桥了。过桥的时间是随机的，假设为T1秒。

d) 过桥完成后，释放full信号量，并尝试获取empty信号量，如果获取不到则等待，直到获取到empty为止。

e) 获取到empty后，表示已经到达对岸，线程结束。

4. right线程的执行过程与left类似，只是方向相反。

5. 这个算法满足了约束条件，因为只有获取到empty和full两个信号量的线程才能进入关键区，保证了桥属于临界资源，而且桥上同时只能有N个人过桥，保证了共享资源数的限制。而且这个算法可以避免死锁，因为每个线程都是先获取empty信号量，再获取full信号量，所以不会出现两个人同时进入桥上的情况。