c++ - 使用简单的两阶段锁定的并发程序

Question

问题:我想使用所谓的两阶段锁定概念同时计算一些方程。

我的方法:创建一个数组，该数组将实时更新每个变量的值。我在创建线程，在算法上应用互斥量/信号量以并发执行的方式上有些卡住。

输入(当然，我将建立更大的方程组以测试并发程序的效率)

2
3 6
&0 = &0 + 4 + 3
&1 = &0 - &1 + 2 + 5
&0 = &1 + 3

输入的描述:

第一行是未知数。 (＆0和＆1是未知数)
第二行是它们各自的初始值。 (＆0等于3，＆1等于6)
下一行是方程式。

输出量

&0 = 14
&1 = 11

在执行方程式的结构下方(可以吗？可以改进吗？)

struct X{
    int id; // the calculated variable
    int sum; // the sum of every constants
    std::string eq; // the row as a string
    std::unordered_map<int, int> unknowns; // store all the unknowns and counts them
    X(std::string);
    void parsing(); // parse eq to get id, sum and unknowns
    void updating(); // update the value of id on a global array when all the unknowns are available
};

Answer 1

1.在分配之间建立依赖关系图

我认为您的目标是尽可能并行地计算分配，同时获得与您依次计算分配相同的结果。为了确定可以并行执行的操作，我建议在您的赋值表达式之间建立一个依赖关系图。

从最后一个赋值开始:任何参与赋值的变量都意味着要对其进行计算，我们需要计算对所涉及变量进行修改的最后一个赋值。通过您给出的示例:

&0 = 3                // A0 (variable initialization)
&1 = 6                // A1 (variable initialization)
&0 = &0 + 4 + 3       // A2
&1 = &0 - &1 + 2 + 5  // A3
&0 = &1 + 3           // A4

依赖项是:

A4 <-- A3         (To compute A4, you need to compute A3 before)
A3 <-- A2 and A1  (To compute A3, you need to compute A2 for the value of &0 and A1 for &1)
A2 <-- A0
A1 <-- no dependency
A0 <-- no dependency

2.递归计算依赖关系

免责声明:我对C++中的锁和线程的使用不是很熟悉。但是我想我可以给出一个通用的方法。

现在，您已经确定了依赖项是什么，您可以尝试计算它们。我可以为线程过程建议这种简单的方法:

computeAssignment(Assignment * as) {
  if (as is not computed) {
    lock Assignment as
    for each dependency of as {
      spawn a thread running computeAssignment(dependency) // Recursion occurs here
    }
    wait for all the threads spawned in the for loop to finish
    compute the result of this assignment
    unlock Assignment as
  }
  return result of as
}

当线程开始检查分配给它的分配时，它首先检查它是否之前已计算过。如果未计算分配，则必须以使第一个线程进行此检查的方式阻止该访问所有其他线程的方式进行此检查。

当第一个线程忙于生成线程以计算依赖关系并计算分配结果时，其他线程在第一次检查时被阻止。当第一个线程最终解锁该分配时，所有正在等待的线程将看到计算结果。

要开始计算，您应该为您拥有的每个变量产生一个线程，并为它们提供最后一个将变量修改为参数的赋值。在您的示例中，这将是2个线程，以分配A4(最后修改＆0)和A3(最后修改＆1)开始。