1个作者和M个读者共同使用相同的项目

Question

假设有这样一个问题： 有2个程序，A和B，1个A的进程，M个B的进程，1个名为var的共享变量。

A
main(){ 
   int i, a[50]; 
   for(i=0;i<50;i++) 
       var = a[i]; 
} 



B
main(){ 
   int i, b[50]; 
   for(i=0;i<50;i++) 
       b[i] = var; 
}

现在，我需要做的是确保A中的每个循环中，每个M个B进程只读取共享变量（一次！）并将其存储在它们的数组中。因此最终，每个B进程都将在其b-arrays中拥有a-array的副本。 这是一个信号量问题，解决方案可以是伪代码，所以语言不重要。

一个初始的解决方案，但并没有起作用： 我使用了一个初始化为0的信号量B，每当A写入时，我就通过M增加B，并进行down(A)。 在每个B循环开始时，我执行down(B)。然后在每个B循环结束时，我检查是否有M个读者已经读取并存储了var，如果有，我就执行up(A)。

显然，上述方法让单个B进程“消耗”了应该分配给M个读者的所有M次使用。 那么，我如何聪明地确保每个B仅读取每个变量一次？一个M个信号量的数组，每个M一个信号量，可以完成任务，但很可能不是这个练习要求的。

- Bimp

---

为什么不使用读写锁？ - fge

每个读者必须为每个A循环进行一次读取，我必须在M个读者上完成同样的工作，不能让读者们协同工作。 - Bimp

Answer 1

你可以使用四个信号量来实现。一个表示“A读取了偶数位置”，一个表示“B写入了偶数位置”，一个表示“A读取了奇数位置”，最后一个表示“B写入了奇数位置”。

A读取a[0]，然后对第一个信号量进行M次信号操作，然后对第二个信号量进行M次等待操作。B写入b[0]，然后对第二个信号量进行一次信号操作。

然后A读取a[1]，对第三个信号量进行M次信号操作，并对第四个信号量进行M次等待操作。B写入b[1]，并对第四个信号量进行一次信号操作。

然后在处理数组的奇偶元素时，在信号量之间切换即可。

显然这是一个作业问题，因为这不像是一个真实的场景。

- Nemo

---

这并不完全是作业（虽然我曾考虑将其标记为作业，但由于它已被弃用而受到了打击），我只是在查看一些旧的考试题。这与我想到的方法非常相似，但无论如何我都会接受它。 - Bimp

Answer 2

实现示例

// Before A and any B run, init 2 x M x 50 semaphores
// (set to 0, but usually they're automatically initialized by the system to
// something equivalent to 0, meaning no-access)

// Create [M][50] semaphores and init to no access for Bs
for (i=0 ; i<M ; i++)
  for (j=0 ; j<50 ; j++)
     asems[i][j] = 0; // no access for Bi index j


// Create [M][50] semaphores to block A before it goes to next iteration
for (i=0 ; i<M ; i++)
  for (j=0 ; j<50 ; j++)
     bsems[i][j] = 0; // no access for A until all B's say ok for that index


// A

for (i=0 ; i<50 ; i++) { 
   var = a[i];

   // release a-sems and, then, wait for b-sems in two separate loops
   // or you may have a deadlock if you use one loop only...
   // (since we don't know if B[i] always ends before B[i+1])
   for (j=0 ; j<M ; j++) {
      release ( asems[j][i] )
   }
   for (j=0 ; j<M ; j++) {
      wait ( bsems[j][i] )
   }
}

// a B

ME = id  // id is the B's unique id from 0 to 49

for (i=0 ; i<50 ; i++) { 
  wait ( asems[ME][i] )
  b[i] = var
  relase ( bsems[ME][i] )
}

可以设计一个更复杂的算法，只使用[50]（而不是[M][50]）信号量。通常，等待和释放类似于这样的东西（由系统处理），它们在临界区中运行。

wait ( sem ) {
   wait_in_sem_fifo_until (sem > 0) 
   sem--
}

release ( sem ) {
   sem++
}

- Déjà vu