模拟 java.lang.Thread 的最佳方法是什么？

Question

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

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

目前我的想法如下：

AstInterpreter 应该实现 java.lang.Runnable。它还应该重写 java.lang.Thread（或其子 class）的每个新实例表达式，用新的 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方案。

Answer 1

我看到两个选项：

选项 1：JVM 线程。每次解释程序调用 Thread.start 时，您也会调用 Thread.start 并使用另一个解释器启动另一个线程。这很简单，使您不必实施锁和其他东西，但您的控制力会减少。

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

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

Answer 2

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

对于部分求值，您需要计算每个程序点的符号程序状态，然后根据该程序点已知的状态简化程序点。您可以通过写下程序启动时您对状态的了解来开始您的部分评估过程。

如果您用完整的符号状态修饰每个程序点并同时将它们全部保存，您会很快运行内存不足。因此，一种更实用的方法是通过使用 depth-first 沿控制流路径搜索的方法枚举所有控制流路径，并在进行时计算符号状态。当此搜索回溯时，它会丢弃正在探索的当前路径上最后一个节点的符号状态。现在，您保存的状态与流程图的深度大小成线性关系，这在方法中通常很浅。（当一个方法调用另一个方法时，只需扩展控制流路径以包含调用）。

要处理运行nables，您必须在单独的运行nables 中对计算的交错进行建模。交错两个线程的（巨大的）状态将变得非常快。在这里可能会为您节省的一件事是，一个线程计算的大多数状态对于该线程来说是完全本地的，因此根据定义对另一个线程是不可见的，您不必担心交错那部分状态。所以我们只剩下模拟两个线程看到的状态交错，以及每个线程的本地状态的模拟。

您可以通过控制流中隐含但模拟的并行分叉对这种交错进行建模：在每个模拟步骤中，一个线程取得一个步骤，或者另一个（概括为 N 个线程）。你得到的是每个分叉的每个程序点的新状态；程序点的实际状态是此过程为每个状态生成的状态的析取。

您可以通过对单个属性的属性进行 "disjunctions" 来简化实际状态分离。例如，如果您知道一个线程在特定程序点将 x 设置为负数，而另一个线程在同一点将其设置为正数，则可以将 x 的状态概括为 "not zero"。您将需要一个非常丰富的类型系统来对可能的值特征进行建模，或者您可以使用一个简陋的系统来保守地计算变量属性的析取，如 "don't know anything".

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

如果这个方案做得对，当一个线程 A 对另一个线程 B 已在使用的对象的同步方法进行调用时，您可以停止 A 与 B 的交错，直到 B 离开同步方法。如果线程 A 和 B 之间永远不会对同一个抽象对象产生干扰，则可以从对象声明中删除同步声明。我认为这是你最初的目标

所有这些都不容易组织，而且可能非常昂贵 time/spacewise 到运行。试图为所有这些非常费力的例子起草一个例子，所以我不会在这里做。

模型检查器 https://en.wikipedia.org/wiki/Model_checking 在生成 "state space" 方面做了非常相似的事情，并且有类似的 time/space 麻烦。如果您想了解更多有关如何管理状态的信息，请阅读相关文献。

模拟 java.lang.Thread 的最佳方法是什么？

What is the best way to simulate java.lang.Thread?

java

multithreading

interpreter

bytecode

abstract-syntax-tree