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

Question

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

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

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

AstInterpreter должны осуществлять java.lang.Runnable. Кроме того, следует переписывать каждое новое-экземпляра выражение java.lang.Thread (или его подкласса) замена целевого показателя в Thread «ы (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 - АСТ интерпретированы):

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

    } 
}); 

Выполняет ли полученная в результате программа поведение нити исходной программы правильно?

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

Answer 1

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

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

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

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

Answer 2

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

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

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

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

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

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

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

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

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

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