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

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

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

目前,我的想法如下:

AstInterpreter 应该实现 .它还应该重写(或其子类)的每个新实例表达式,将 的目标 () 替换为新的 AstInterpreter 实例:java.lang.Runnablejava.lang.ThreadThreadjava.lang.Runnable

编辑:提供更复杂的示例。

编辑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 (线程测试 - 解释字节码):

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

程序 2(线程测试 - 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 的 Thread 行为?

1)目前,方案已被接受。source=8 / target=8


答案 1

我看到两个选项:

选项 1:JVM 线程。每次解释的程序调用 Thread.start 时,你也会调用 Thread.start 并使用另一个解释器启动另一个线程。这很简单,使您不必实现锁和其他事情,但是您获得的控制较少。

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

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


答案 2

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

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

如果你用它的完整符号状态装饰每个程序点,并将它们一次保持在周围,你就会很快耗尽内存。因此,更实用的方法是使用沿控制流路径的深度优先搜索来枚举通过方法的所有控制流路径,并随时计算符号状态。当此搜索回溯时,它会丢弃正在浏览的当前路径上最后一个节点的符号状态。现在,您保存的状态在流图的深度大小上是线性的,这在方法中通常很浅。(当一个方法调用另一个方法时,只需扩展控制流路径以包含调用)。

要处理可运行项,您必须对单独的可运行项中计算的交错进行建模。交错两个线程的(巨大)状态将变得巨大。在这里,可能为您节省的一件事是,线程计算的大多数状态对该线程完全是本地的,因此根据定义,对另一个线程不可见,并且您不必担心交错该状态的这一部分。因此,我们只能模拟两个线程所看到的状态的交错,以及每个线程的局部状态的模拟。

您可以通过控制流中隐含但模拟的并行分叉来模拟这种交错:在每个模拟步骤中,一个线程要么使一个步骤进度,要么另一个线程(泛化为 N 个线程)。你得到的是每个分叉的每个程序点的新状态;程序点的实际状态是此过程为每个状态生成的状态的析取。

您可以通过对单个属性的属性进行“析取”来简化实际状态析取。例如,如果您知道一个线程在特定程序点将 x 设置为负数,而另一个线程在同一点将其设置为正数,则可以将 x 的状态汇总为“不为零”。你需要一个相当丰富的类型系统来模拟可能的值表征,或者你可以忍受一个贫穷的系统,它保守地计算变量属性的析取作为“什么都不知道”。

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

如果此方案正确完成,当一个线程 A 对另一个线程 B 已在使用的对象上的同步方法进行调用时,可以停止将 A 与 B 交错,直到 B 离开同步方法。如果线程 A 和 B 之间从不在同一抽象对象上发生冲突,则可以从对象声明中删除同步声明。我认为这是你最初的目标

所有这些都不容易组织,并且运行时间/空间可能非常昂贵。试图为所有这些举一个非常费力的例子,所以我不会在这里做。

模型检查器 https://en.wikipedia.org/wiki/Model_checking 在生成“状态空间”方面做非常相似的事情,并且具有类似的时间/空间问题。如果你想了解更多关于如何管理状态的信息,我会阅读这方面的文献。