如何模拟java.lang.Thread的最佳方法？

Question

我正在开发适用于Java 6^*1)的变压器，它执行一种部分评估，但为了简单起见，我们考虑一下 Java 程序的抽象语法树解释。

如何通过一个解释程序模拟Thread的行为？

目前我想到了以下方法： AstInterpreter应该实现java.lang.Runnable。它还应该重写每个java.lang.Thread（或其子类）的新实例表达式，将Thread的目标(java.lang.Runnable)替换为新的AstInterpreter实例: 编辑：提供更复杂的示例。 编辑2：备注1。 目标程序:

class PrintDemo {
   public void printCount(){
    try {
         for(int i = 5; i > 0; i--) {
            System.out.println("Counter   ---   "  + i );
         }
     } catch (Exception e) {
         System.out.println("Thread  interrupted.");
     }
   }
}

class ThreadDemo extends Thread {
   private Thread t;
   private String threadName;
   PrintDemo  PD;

   ThreadDemo( String name,  PrintDemo pd){
       threadName = name;
       PD = pd;
   }
   public void run() {
     synchronized(PD) {
        PD.printCount();
     }
     System.out.println("Thread " +  threadName + " exiting.");
   }

   public void start ()
   {
      System.out.println("Starting " +  threadName );
      if (t == null)
      {
         t = new Thread (this, threadName);
         t.start ();
      }
   }
}

public class TestThread {
   public static void main(String args[]) {
      PrintDemo PD = new PrintDemo();

      ThreadDemo T1 = new ThreadDemo( "Thread - 1 ", PD );
      ThreadDemo T2 = new ThreadDemo( "Thread - 2 ", PD );

      T1.start();
      T2.start();

      // wait for threads to end
      try {
         T1.join();
         T2.join();
      } catch( Exception e) {
         System.out.println("Interrupted");
      }
   }
}

程序1（ThreadTest - 字节码解释）：

new Thread( new Runnable() {
   public void run(){
      ThreadTest.main(new String[0]);
   }
});

程序2（ThreadTest-AST解释）：

final com.sun.source.tree.Tree tree = parse("ThreadTest.java");

new Thread( new AstInterpreter() {
   public void run(){
      interpret( tree );
   }

   public void interpret(com.sun.source.tree.Tree javaExpression){
   //...  

   }
});

请问生成的程序2是否能够正确模拟初始程序1中线程的行为？

¹⁾ 目前只接受source=8 / target=8的方案。

- Anton Danilov

---

是的，您可以编写自己的类来实现Runnable接口，并且该Runnable类可以在Thread中运行。我不明白您的AstInterpreter类有什么作用，而一个新的Runnable类不能做到的。 - Gilbert Le Blanc

所以如果我理解正确，您想要构建类似于自助JIT编译器的东西？从任何地方获取一个 .java 文件并执行它？ - dryman

有一些（我猜是很多）机器翻译程序会阻止某些特定形式的MT翻译成ST。例如：通过有限阻塞队列（ArrayBlockingQueue）实现的2线程生产者-消费者模式。 - Victor Sorokin

如果您的“解释器”使用具体值进行经典解释运行程序，那么除了常量折叠之外，您不太可能获得有关“专业化”的大量信息。这需要对程序进行符号推理。符号模拟是一个特殊情况。现在，模拟可运行程序必须模拟所有可能的交错，而不仅仅是一个。您可以执行的其他符号操作将使用静态分析来启用代码的各种优化，利用您声明为常量的那些值。解释是不足够的。 - Ira Baxter

如果你想简化Runnables，我会倾向于查看将可执行代码中的单个语句提取到调用Runnable之前的代码位置。如果您可以对Runnable代码的每个语句都这样做，那么剩下的就是在空程序上运行的Runnable，可以被消除，然后Runnable就消失了。 - Ira Baxter

Answer 1

我看到两个选择：

选择1：JVM线程。每次解释程序调用Thread.start时，您也会调用Thread.start并启动另一个带有另一个解释器的线程。这很简单，可以节省您实现锁和其他东西的时间，但您会失去一些控制。

选择2：模拟线程。类似于在单处理器上实现多任务处理-使用时间片轮转方式。您必须在解释器中实现锁定和睡眠，并跟踪模拟线程以了解哪些线程已准备好运行，哪些已完成，哪些已阻塞等等。

您可以执行一个线程的指令，直到它被阻塞或某段时间过去或达到某个指令计数，然后找到另一个可能运行的线程并切换到运行该线程。在操作系统的上下文中，这称为进程调度-您可能想研究此主题以获取灵感。

- Sergej Koščejev

---

特别是，如果没有执行交错，你的解释器中就 没有 对“可运行对象”进行建模。Sergej 是正确的。 - Ira Baxter

Answer 2

使用计算实际值的经典解释器无法明智地进行部分求值。您需要使用符号值。

对于部分求值，您想要的是在每个程序点计算符号程序状态，然后根据该程序点已知的状态简化程序点。您可以通过写下程序开始时关于状态的已知信息来启动部分求值过程。

如果您为每个程序点都添加了完整的符号状态并将它们全部保留，那么您很快就会耗尽内存。因此，更实用的方法是使用深度优先搜索沿着控制流路径枚举方法中的所有控制流路径，并在搜索过程中计算符号状态。当此搜索回溯时，它会丢弃当前正在探索的路径上最后一个节点的符号状态。现在，您保存的状态与流程图深度的大小成线性关系，而在方法中，流程图深度通常相对较浅。（当一个方法调用另一个方法时，只需扩展控制流路径以包括该调用）。

处理可运行对象，您必须对单独的可运行对象中的计算交错进行建模。交错两个线程的（巨大）状态会快速变得庞大。唯一可能挽救您的是，大多数线程计算的状态完全局限于该线程，因此根据定义对另一个线程不可见，您无需担心交错该部分状态。因此，我们要模拟两个线程看到的状态交错，以及每个线程本地状态的模拟。

您可以通过隐含但模拟的控制流并行分支来模拟这种交错：在每个模拟步骤中，要么一个线程取得一步进展，要么另一个线程取得进展（推广到N个线程）。您得到的是每个程序点的新状态，对于每个分支生成的状态，程序点的实际状态是它们的析取。

您可以通过对单个属性的属性进行“析取”来简化实际状态的析取。例如，如果您知道一个线程在特定程序点将x设置为负数，而另一个线程在同一点将其设置为正数，则可以将x的状态总结为“非零”。您需要一个相当丰富的类型系统来模拟可能的值特征，或者您可以使用一个计算变量属性析取的贫乏类型系统，保守地表示“不知道任何东西”。

这种方案假设内存访问是原子的。但在实际代码中，它们通常不是，因此您必须对其进行建模。如果您在“同一”步骤中从两个线程对内存位置进行冲突读写操作，则最好让解释器简单地抱怨您的程序存在竞争条件。竞争条件并不会使您的程序出错，但只有真正聪明的代码才会以不破坏的方式使用竞争。

如果正确执行此方案，则当一个线程A对已被另一个线程B使用的对象调用同步方法时，您可以停止交错A和B，直到B离开同步方法。如果线程A和B之间从未发生过同一抽象对象的干扰，则可以从对象声明中删除同步声明。我想这就是您最初的目标。

所有这些都不容易组织起来，而且很可能在时间/空间上非常昂贵。试图列举所有这些的例子相当费力，所以我不会在这里做。

模型检查器 https://en.wikipedia.org/wiki/Model_checking 在生成“状态空间”方面做了非常类似的事情，并且存在类似的时间/空间问题。如果您想了解如何管理状态，请阅读相关文献。

- Ira Baxter

---

非常感谢您提供的帮助性答案。 在我的转换器中，我没有使用经典解释器。这只是为了简单起见而提到。 我使用“驱动”（实际上是“抽象解释”）等技术，以及所谓的“超级编译”。 虽然它与PE、砍林和其他一些众所周知的技术有很多共同之处，但它是一个实验性领域（至少超出了函数式编程领域）。 - Anton Danilov

抽象解释：好的，所以你正在使用一种符号模拟，很好。您应该能够沿着任何控制路径执行此操作，因此答案的其余部分适用。但是应该清楚的是，使用Java解释器本身进行分叉（Sergej的选项1）是行不通的。我的答案是对Sergej选项2的详细说明，重点是模拟线程的（潜在）交错。 - Ira Baxter

请纠正我如果我错了：在我看来，使用ReentrantLock的子类记录获取线程信息可以大大减少（甚至消除）对线程模拟的需求。我用我的锁类替换了标准锁（上述两者都提到了），并用lock()/unlock()替换了synchronized语句。因此，可能我将有足够的关于线程干扰的信息，而不需要额外的努力。 - Anton Danilov

我的回答的重点是运行另一个线程不会帮助你的符号解释，至少我不知道如何做到。 - Ira Baxter

运行新线程意味着运行新的符号解释器实例，对吧？我可能会说我高估了并发模拟的无用性。 - Anton Danilov

你可能要运行一个新的、额外的符号解释器，但那么做并不能模拟并发的影响。你似乎没有理解重点：你必须模拟可能的交织效应，而两个单独但并行的符号解释器无法完成这项任务；他们必须相互合作才能实现。并行线程可能不会使这种建模变得更容易；按照我描述的方式，你的符号解释器可能更适合模拟并发。 - Ira Baxter