c - 如何使用信号量实现屏障

Question

我有以下问题需要解决:

考虑一个应用程序，其中有三种类型的线程:微积分 A、微积分 B 和终结。每当线程类型 Calculus-A 结束时，它都会调用例程 endA()，该例程会立即返回。每当线程类型 Calculus-B 结束时，它都会调用例程 endB()，该例程会立即返回。 Finalization 例程调用 wait() 之类的线程，仅当他们已经完成两个计算 A 线程和 2 个计算 B 线程时才返回。换句话说，对于恰好 2 个微积分 A 的结论和 2 个微积分 B 的结论，一个线程最终化被允许继续。这 3 种类型的线程数量不确定。不知道线程调用例程的顺序。线程完成按到达顺序回答。使用信号量实现例程 endA()、endB() 和 wait()。除了变量初始化，唯一可能的操作是 P 和 V。忙等待的解决方案是 Not Acceptable 。

这是我的解决方案:

semaphore calcA = 2;
semaphore calcB = 2;
semaphore wait = -3;

void endA()
    {
        P(calcA);
        V(wait);
    }

void endB()
    {
        P(calcB);
        V(wait);
    }

void wait()
    {
        P(wait);
        P(wait);
        P(wait);
        P(wait);
        V(calcA);
        V(calcA);
        V(calcB);
        V(calcB);
    }

我相信由于等待的初始化和 if 和 wait() 在 endA() 和 endB() 之前执行，所以会出现死锁。还有其他解决方案吗？

Answer 1

我倾向于将信号量问题视为必须识别“等待源”并为每个信号量和访问协议(protocol)定义的问题。

考虑到这一点，“等待的来源”是

• 完成 CalcA
• 完成 CalcB
• 也许，如果我没理解错的话，等待整个完成组，包括两个 CalcA 和两个 CalcB。我说也许是因为我不确定“Threads Completion are answered in the order of arrival.”是什么意思。

因此，CalcA 和 CalcB 的完成应该增加它们各自的计数器。在另一端，一个 Finalization 线程获得了对计数器的独占访问权，并以任何顺序等待所需数量的完成以构成一个完成组。然后解锁对下一个组的访问权限。

我的代码在下面，尽管因为我不熟悉荷兰语 V 和 P 我将使用 take()/给()。

semaphore calcA    = 0;
semaphore calcB    = 0;
semaphore groupSem = 1;

void endA(){
    give(calcA);
}

void endB(){
    give(calcB);
}

void wait(){
    take(groupSem);
    take(calcA);
    take(calcA);
    take(calcB);
    take(calcB);
    give(groupSem);
}

groupSem 信号量确保全有或全无:进入临界区的线程将完成 CalcA 和 CalcB 中的每一个的下两个完成。如果 groupSem 不存在，第一个进入 wait 的线程可能会占用两个 A 并阻塞，然后被另一个获取两个 A 和两个 B 的线程接管，然后逃跑。

如果 groupSem 不存在，则存在一个更糟糕的问题，如果第二个线程占用两个 A，一个 B，然后阻塞，然后第一个线程获取第二个 B。如果不知何故finalization 的结果允许更多的 CalculationA 和 CalculationB 运行，那么你可能会遇到死锁，因为计算 A 和 B 的实例可能没有更多的机会完成，因此导致 finalization 线程挂起，无法产生更多的计算实例。