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信号量，所以不会出现两个人同时进入桥上的情况。

相关问题

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);
}

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

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

这是一个经典的同步问题，可以使用信号量实现。

首先，我们需要定义两个信号量：一个信号量表示河对岸可以过河的人数，初始值为桥上的桥墩数量；另一个信号量表示桥上可以行走的人数，初始值为1，因为同一时间只能有一个人在桥上行走。

对于从岸上来的人，每个人都需要获取桥上可以行走的信号量，如果信号量为0，则等待；如果信号量为1，则获取信号量，并且将桥上可以行走的信号量减1。之后，获取河对岸可以过河的人数信号量，如果信号量为0，则等待；如果信号量不为0，则获取信号量，并且将河对岸可以过河的人数信号量减1，表示有一个人已经过了河。最后，释放桥上可以行走的信号量，表示自己已经下桥了。

对于从河对岸来的人，每个人需要获取河对岸可以过河的人数信号量，如果信号量为0，则等待；如果信号量不为0，则获取信号量，并且将河对岸可以过河的人数信号量减1，表示有一个人已经到达桥上。之后，获取桥上可以行走的信号量，如果信号量为0，则等待；如果信号量为1，则获取信号量，并且将桥上可以行走的信号量减1。最后，释放河对岸可以过河的人数信号量，表示自己已经过了河。

下面是同步算法的伪代码：

# 定义信号量
bridge_sem = Semaphore(1)  # 桥上可以行走的人数
people_sem = Semaphore(num_pillars)  # 河对岸可以过河的人数

# 从岸上来的人
def cross_from_bank():
    bridge_sem.acquire()  # 获取桥上可以行走的信号量
    people_sem.acquire()  # 获取河对岸可以过河的人数信号量
    bridge_sem.release()  # 释放桥上可以行走的信号量

# 从河对岸来的人
def cross_from_river():
    people_sem.acquire()  # 获取河对岸可以过河的人数信号量
    bridge_sem.acquire()  # 获取桥上可以行走的信号量
    bridge_sem.release()  # 释放桥上可以行走的信号量
    people_sem.release()  # 释放河对岸可以过河的人数信号量

# 创建线程，并且让线程开始执行
for i in range(num_people):
    if i < num_people / 2:
        t = Thread(target=cross_from_bank)
    else:
        t = Thread(target=cross_from_river)
    t.start()

在这个算法中，从岸上来的人和从河对岸来的人都需要获取一个信号量，如果信号量不可用，则等待。当获取到信号量之后，需要将信号量减1，表示这个资源已经被占用，其他线程需要等待。当线程执行完毕之后，需要释放信号量，表示这个资源可以被其他线程使用了。