¿Cuál es la mejor manera de simular java.lang.Thread?

multithreading interpreter

Question

Estoy desarrollando el transformador para Java 6 ^{* 1)} que realiza una especie de evaluación parcial pero consideremos, para simplificar, la interpretación de árbol de sintaxis abstracta de un programa Java.

¿Cómo simular el comportamiento del Thread por un programa interpretado?

Por el momento tengo en mente lo siguiente:

AstInterpreter debe implementar java.lang.Runnable . También debe volver a escribir cada nueva expresión de instancia de java.lang.Thread (o su subclase) reemplazando el objetivo del Thread ( java.lang.Runnable ) con la nueva instancia de AstInterpreter :

EDIT: ejemplos más complejos proporcionados.

EDIT 2: observación 1.

Programa objetivo:

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");
      }
   }
}

programa 1 (ThreadTest - bytecode interpretado):

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

Programa 2 (ThreadTest - AST interpretado):

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){
   //...  

   }
});

¿El programa resultante 2 simula el comportamiento del hilo del programa inicial 1 correctamente?

¹⁾ Actualmente, se acepta el esquema source=8 / target=8 .

Answer 1

No puede realizar una evaluación parcial con sensatez utilizando un intérprete clásico que calcula con valores reales. Necesitas valores simbólicos.

Para una evaluación parcial, lo que desea es calcular el estado del programa simbólico en cada punto del programa y luego simplificar el punto del programa en función del estado conocido en ese punto del programa. Usted comienza su proceso de evaluación parcial al anotar lo que sabe sobre el estado cuando comienza el programa.

Si decoras cada punto del programa con su estado simbólico completo y los mantienes a la vez, te quedarás sin memoria rápidamente. Por lo tanto, un enfoque más práctico es enumerar todas las rutas de flujo de control a través de un método utilizando una búsqueda en profundidad a lo largo de las rutas de flujo de control, calculando el estado simbólico sobre la marcha. Cuando esta búsqueda retrocede, elimina el estado simbólico del último nodo en la ruta actual que se está explorando. Ahora su estado guardado es lineal en el tamaño de la profundidad del gráfico de flujo, que a menudo es bastante superficial en un método. (Cuando un método llama a otro, simplemente extienda la ruta del flujo de control para incluir la llamada).

Para manejar runnables, tiene que modelar las interconexiones de los cálculos en los runnables separados. Entrelazar el estado (enorme) de dos hilos obtendrá enorme rápido. La única cosa que podría ahorrarle aquí es que la mayoría de los estados calculados por un subproceso son completamente locales a ese subproceso, por lo tanto, por definición, son invisibles a otros subprocesos, y no tiene que preocuparse por intercalar esa parte del estado. Así que nos quedamos con la simulación del intercalado del estado visto por ambos hilos, junto con la simulación de los estados locales de cada hilo.

Puede modelar esta intercalación mediante bifurcaciones paralelas implícitas pero simuladas en el flujo de control: en cada paso simulado, uno de los hilos progresa en un paso o el otro (generaliza a N hilos). Lo que obtienes es un nuevo estado para cada punto del programa para cada bifurcación; el estado real para el punto del programa es la separación de los estados generados por este proceso para cada estado.

Puede simplificar la disyunción de estado real tomando "disyunciones" de propiedades de propiedades individuales. Por ejemplo, si sabe que un hilo establece x en un número negativo en un punto de programa particular, y otro lo establece en un número positivo en ese mismo punto, puede resumir el estado de x como "no cero". Necesitará un sistema de tipos bastante rico para modelar posibles caracterizaciones de valores, o puede vivir con uno empobrecido que calcula las disyunciones de las propiedades de una variable de forma conservadora como "no saber nada".

Este esquema asume que los accesos de memoria son atómicos. A menudo no están en código real, así que también tienes que modelar eso. Probablemente sea mejor que el intérprete simplemente se queje de que su programa tiene una condición de carrera si termina con operaciones de lectura y escritura en conflicto en una ubicación de memoria desde dos hilos en el "mismo" paso. Una condición de carrera no hace que su programa sea incorrecto, pero solo el código realmente inteligente utiliza las carreras de manera que no se rompan.

Si este esquema se realiza correctamente, cuando un subproceso A realiza una llamada con un método síncrono en un objeto que ya está utilizando otro subproceso B, puede detener el intercalado A con B hasta que B abandone el método síncrono. Si nunca hay interferencia entre los subprocesos A y B sobre el mismo objeto abstracto, puede eliminar la declaración sincronizada de la declaración del objeto. Creo que este era tu objetivo original

Todo esto no es fácil de organizar, y es probable que sea muy costoso / espacialmente ejecutable. Tratando de trazar un ejemplo de todo esto bastante laborioso, así que no lo haré aquí.

Los verificadores de modelos https://en.wikipedia.org/wiki/Model_checking hacen algo muy similar en términos de generar el "espacio de estado" y tienen problemas de tiempo / espacio similares. Si quieres saber más acerca de cómo administrar el estado, haz esto, leería la literatura sobre esto.

Answer 2

Veo dos opciones:

Opción 1: subprocesos JVM. Cada vez que el programa interpretado llama a Thread.start, también llama a Thread.start y comienza otro hilo con otro intérprete. Esto es simple, le evita tener que implementar bloqueos y otras cosas, pero obtiene menos control.

Opción 2: hilos simulados. Similar a la forma en que se implementa la multitarea en uniprocesadores, utilizando la división del tiempo. Debe implementar bloqueos y suspensiones en el intérprete, y realizar un seguimiento de los subprocesos simulados para saber qué subprocesos están listos para ejecutarse, cuáles han finalizado, cuáles están bloqueados, etc.

Puede ejecutar las instrucciones de un subproceso hasta que se bloquee o transcurra algún tiempo o hasta que se alcance un número de instrucciones, y luego encuentre otro subproceso que pueda ejecutarse ahora y pasar a ejecutar ese subproceso. En el contexto de los sistemas operativos, esto se denomina programación de procesos; es posible que desee estudiar este tema para inspirarse.