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

Question

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

我的方法：创建一个数组来实时更新每个变量的值。我有点坚持我应该创建线程的方式，在算法上应用 mutex/semaphore 来并发执行它。

输入（当然，我会建立一个更大的方程组来测试并发程序的效率）

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）开始。

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

concurrent program using simple two phase locking

c++

multithreading

two-phase-commit

1。在分配之间构建依赖关系图

2。递归计算依赖关系