0

某个计算会生成两个数组a，b这样
a[i]=f(i) for 0 ≤ i < n and b[i] = g(a[i]) for 0 ≤ i < n。假设这个计算被分解成两个并发进程，X计算数组并​​计算数组。这些过程使用两个二进制信号量和，都初始化为零。该数组由两个进程共享。进程的结构如下所示。YXaYbRSa

Process X:                         
private i;                         
for (i=0; i < n; i++) {            
    a[i] = f(i);                       
    ExitX(R, S);                       
 }                                 

Process Y:
private i;
for (i=0; i < n; i++) {
    EntryY(R, S);
    b[i]=g(a[i]);
}

以下哪一项代表 和 的正确ExitX实现EntryY？

（一个）

ExitX(R, S) {
    P(R);
    V(S);
}

EntryY (R, S) {
    P(S);
    V(R);
}

(乙)

ExitX(R, S) {
    V(R);
    V(S);
}

EntryY(R, S) {
    P(R);
    P(S);
}

（C）

ExitX(R, S) {
    P(S);
    V(R);
}

EntryY(R, S) {
    V(S);
    P(R);
}

(四)

ExitX(R, S) {
    V(R);
    P(S);
}
EntryY(R, S) {
    V(S);
    P(R);
}

我相信答案应该是（B），因为在Y执行关键部分之前不应该执行进程中的关键部分X（a[i]首先填充，必须用于b[i]），所以之后X执行然后根据选项（B）在Y我们会发现临界区的入口R=1，S=1所以现在临界区Y就可以执行了。

问题：正确答案是（C），我错在哪里？

4

2 回答 2

2

如果它们不是二进制信号量，“B”将起作用：在这种情况下，X 可以创建一个元素，增加一个信号量，而 Y 可以等待该信号量并使用这些项目。信号量可以计算有多少项目可供处理。一个信号量就足够了。

但是，您有二进制信号量。因此，您最多只能数一个，例如 X 可以创建一个元素，发出信号量，但随后不能继续创建元素，因为它不能将该信号量值提高到“2”（或更多）。所以它必须等待那个单个元素被 Y 识别。并且这个等待引入了第二个信号量，当当前元素被处理时向 X 发出信号。重要的是要记住，P 会在必要时等待信号量增加（而 V 会增加），因此 X 不能等待单个信号量回到 0，因为没有这样的操作。

这就是“C”正在做的事情，S 实际上是“数据就绪”信号，R 是“确认”。X 说，它准备好了，然后等待确认。Y 等待就绪并发送确认。

于 2017-11-06T00:53:54.330 回答
2

首先，考虑一下为什么我们在这里甚至需要两个信号量。原因是我们这里有两件事要协调，

  1. Y 循环无法i在 X 循环完成之前开始i
  2. X 循环不能i+1在 Y 完成之前开始i。

所以有两个信号量，每个信号量在上面管理一个点。

信号量达到 1 需要调用Pfrom ExitX。并且EntryY需要打电话V。所以B已经不在了。要实现 2，我们需要VinExitX和Pin EntryY。

所以看看A，没有人增加任何东西，所以这是一个僵局。

C 完成这项工作。

D 不太正确，因为在调用任何信号量之前，两者X都Y可能会命中V两次。P

于 2017-11-06T01:01:55.137 回答