Подтвердить что ты не робот

Каков наилучший способ моделирования java.lang.Thread?

Я разрабатываю трансформатор для Java 6 * 1), который выполняет своего рода частичную оценку, но рассмотрим для простоты абстрактно-синтаксическую древовидную интерпретацию Java-программу.

Как имитировать поведение Thread интерпретируемой программой?

В данный момент я имею в виду следующее:

AstInterpreter должен реализовать java.lang.Runnable. Он также должен переписать каждое новое выражение-экземпляр java.lang.Thread (или его подкласса), заменяя Thread target (java.lang.Runnable) новым экземпляром AstInterpreter:

EDIT: более сложные примеры.

EDIT 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 правильно моделирует поведение Thread для начальной программы 1?

1) В настоящее время принята схема source=8 / target=8.

4b9b3361

Ответ 1

Я вижу два варианта:

Вариант 1: потоки JVM. Каждый раз, когда интерпретируемая программа вызывает Thread.start, вы также вызываете Thread.start и запускаете другой поток с другим интерпретатором. Это просто, избавляет вас от необходимости выполнять блокировки и другие вещи, но вы получаете меньше контроля.

Вариант 2: имитируемые потоки. Подобно тому, как многозадачность реализована на однопроцессорных компьютерах - с использованием временного среза. Вы должны реализовать блокировки и сны в интерпретаторе и отслеживать смоделированные потоки, чтобы знать, какие потоки готовы к запуску, которые были завершены, которые заблокированы и т.д.

Вы можете выполнять инструкции одного потока до тех пор, пока он не завершится или не истечет какое-то время или не будет достигнут какой-либо счетчик команд, а затем найдите другой поток, который может выполняться прямо сейчас и переключиться на выполнение этого потока. В контексте операционных систем это называется процессом планирования - вы можете изучить этот вопрос для вдохновения.

Ответ 2

Вы не можете сделать частичную оценку разумно, используя классический интерпретатор, который вычисляет с фактическими значениями. Вам нужны символические значения.

Для частичной оценки вы хотите вычислить состояние символической программы в каждой программной точке, а затем упростить программную точку на основе состояния, известного в этой программной точке. Вы начинаете процесс частичной оценки, записывая то, что вы знаете о состоянии при запуске программы.

Если вы украсили каждую программную точку своим полным символическим состоянием и сохранили их все сразу, у вас быстро закончилась бы память. Таким образом, более практичный подход состоит в том, чтобы перечислить все пути потока управления с помощью метода, используя поиск по глубине вдоль путей потока управления, вычисляя символическое состояние по мере продвижения. Когда этот поиск отступает, он отбрасывает символическое состояние для последнего node в текущем изучаемом пути. Теперь ваше сохраненное состояние является линейным по размеру глубины потока, что часто довольно мелко по методу. (Когда метод вызывает другой, просто добавьте путь потока управления, чтобы включить вызов).

Чтобы обрабатывать runnables, вы должны моделировать перемежения вычислений в отдельных runnables. Чередование (огромного) состояния двух потоков будет очень быстрым. Единственное, что может вас сэкономить, - это большинство состояний, вычисленных потоком, полностью локально для этого потока, поэтому по определению невидимо для другого потока, и вам не нужно беспокоиться о чередовании этой части состояния. Таким образом, нам остается симулировать перемежение состояния, наблюдаемое обоими двумя потоками, наряду с имитацией локальных состояний каждого потока.

Вы можете моделировать это чередование подразумеваемыми, но имитируемыми параллельными вилами в потоке управления: на каждом смоделированном этапе либо один поток делает шаг вперед, либо другой (обобщают на N потоков). Вы получаете новое состояние для каждой точки программы для каждой вилки; фактическое состояние для программной точки - это дизъюнкция состояний, генерируемых этим процессом для каждого состояния.

Вы можете упростить фактическую дизъюнкцию состояния, взяв "дизъюнкции" свойств отдельных свойств. Например, если вы знаете, что один поток устанавливает x на отрицательное число в определенной программной точке, а другой устанавливает его на положительное число в этой же точке, вы можете суммировать состояние x как "не ноль". Вам понадобится довольно богатая система типов, чтобы моделировать возможные значения характеристик, или вы можете жить с обедневшим, который вычисляет отклонения свойств переменной консервативно как "ничего не знаю".

Эта схема предполагает, что обращения к памяти являются атомарными. Они часто не в реальном коде, поэтому вы тоже должны моделировать это. Вероятно, лучше всего, чтобы интерпретатор просто жаловался, что ваша программа имеет условие гонки, если вы закончите конфликтующие операции чтения и записи в ячейку памяти из двух потоков на "том же" шаге. Состояние гонки не делает вашу программу неправильной, но только действительно умный код использует гонки таким образом, чтобы они не были нарушены.

Если эта схема выполняется правильно, когда один поток A вызывает вызов синхронного метода для объекта, уже используемого другим потоком B, вы можете остановить перемежение A с B до тех пор, пока B не оставит синхронный метод. Если между потоками A и B не существует помех над одним и тем же абстрактным объектом, вы можете удалить синхронизированное объявление из объявления объекта. Я думаю, что это была ваша первоначальная цель.

Все это нелегко организовать, и это, вероятно, очень дорогое время/пробел для запуска. Попытка составить пример всего этого довольно кропотливого, поэтому я не буду здесь этого делать.

Шашки модели https://en.wikipedia.org/wiki/Model_checking делают очень схожую вещь с точки зрения создания "пространства состояний" и имеют схожие проблемы времени и пространства. Если вы хотите узнать больше о том, как управлять государством, я должен прочитать литературу по этому вопросу.