Qual è il modo migliore per simulare java.lang.Thread?

Question

sto sviluppando il trasformatore per Java 6 ^{* 1)} che esegue una sorta di valutazione parziale Ma consideriamo, per semplicità, astratto-sintassi-albero interpretazione di un programma Java.

Come simulare il comportamento di Thread da un programma interpretato?

Al momento ho in mente quanto segue:

AstInterpreter dovrebbero attuare java.lang.Runnable. Dovrebbe anche riscrivere ogni nuova istanza espressione del java.lang.Thread (o la sua sottoclasse) sostituendo porta s' il Thread (java.lang.Runnable) con la nuova istanza AstInterpreter:

EDIT: esempi più complessi disponibile.

EDIT 2: osservazione programma 1.

cliente:

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

programma 1 (ThreadTest - bytecode interpretato):

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

programma 2 (ThreadTest - AST interpretato):

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

    } 
}); 

Condivide la risultante programma di 2 simulare il comportamento del thread del programma iniziale 1 correttamente?

¹⁾ Attualmente, lo schema source=8/target=8 è accettato.

Answer 1

vedo due opzioni:

Opzione 1: thread JVM. Ogni volta che il programma interpretato chiama Thread.start, chiama anche Thread.start e inizia un'altra discussione con un altro interprete. Questo è semplice, ti evita di dover implementare serrature e altre cose, ma ottieni meno controllo.

Opzione 2: fili simulati. Simile al modo in cui il multitasking è implementato su uniprocessori, utilizzando il time slicing. È necessario implementare blocchi e dorme nell'interprete e tenere traccia dei thread simulati per sapere quali thread sono pronti per l'esecuzione, quali terminati, quali bloccati, ecc.

È possibile eseguire le istruzioni di un thread finché non blocca o trascorre qualche tempo o viene raggiunto un certo numero di istruzioni, quindi trova un altro thread che può essere eseguito ora e passa all'esecuzione di quel thread. Nel contesto dei sistemi operativi questo è chiamato scheduling dei processi: potresti voler studiare questo argomento come fonte di ispirazione.

Answer 2

Non è possibile eseguire una valutazione parziale in modo sensato utilizzando un interprete classico che calcola con valori effettivi. Hai bisogno di valori simbolici.

Per la valutazione parziale, ciò che si desidera è calcolare lo stato del programma simbolico in ciascun punto del programma e quindi semplificare il punto del programma in base allo stato noto in quel punto del programma. Inizi il tuo processo di valutazione parziale annotando ciò che sai sullo stato all'avvio del programma.

Se hai decorato ciascun punto del programma con il suo stato simbolico completo e li hai tenuti tutti intorno in una volta, esaurirai la memoria velocemente. Quindi un approccio più pratico è quello di enumerare tutti i percorsi del flusso di controllo attraverso un metodo che utilizza una ricerca in profondità lungo i percorsi del flusso di controllo, calcolando lo stato simbolico mentre si va. Quando questa ricerca torna indietro, getta via lo stato simbolico per l'ultimo nodo sul percorso corrente che viene esplorato. Ora il tuo stato salvato è lineare nella dimensione della profondità del diagramma di flusso, che è spesso piuttosto superficiale in un metodo. (Quando un metodo chiama un altro, basta estendere il percorso del flusso di controllo per includere la chiamata).

Per gestire i runnable, è necessario modellare gli intrecci dei calcoli nei runnables separati. Interlacciare lo stato (enorme) di due thread diventerà enorme velocemente. L'unica cosa che potrebbe salvarti qui è che la maggior parte dello stato calcolato da un thread è completamente locale a quel thread, quindi è per definizione invisibile a un altro thread e non devi preoccuparti di interlacciare quella parte dello stato. Quindi rimaniamo con la simulazione dell'interleaving di stato visto da entrambi i due thread, insieme alla simulazione degli stati locali di ciascun thread.

È possibile modellare questo interleaving mediante forcelle parallele implicite ma simulate nel flusso di controllo: ad ogni fase simulata, uno dei due thread fa avanzare un passaggio o l'altro (generalizza a N thread). Quello che ottieni è un nuovo stato per ogni punto del programma per ogni fork; lo stato attuale per il punto del programma è la disgiunzione degli stati generati da questo processo per ogni stato.

È possibile semplificare la disgiunzione dello stato effettivo prendendo "disgiunzioni" delle proprietà delle singole proprietà. Ad esempio, se si sa che un thread imposta x su un numero negativo in un punto particolare del programma e un altro lo imposta su un numero positivo nello stesso punto, è possibile riepilogare lo stato di x come "non zero". Avrai bisogno di un sistema di tipo piuttosto ricco per modellare possibili caratterizzazioni del valore, oppure puoi vivere con un povero che calcola le disgiunzioni delle proprietà di una variabile in modo conservativo come "non so nulla".

Questo schema presuppone che gli accessi alla memoria siano atomici. Spesso non sono in codice reale, quindi devi anche modellarlo. Probabilmente è meglio avere l'interprete che si lamenta semplicemente che il programma ha una condizione di competizione se si finisce con operazioni di lettura e scrittura in conflitto su una posizione di memoria da due thread allo stesso "passo". Una condizione di gara non rende il tuo programma sbagliato, ma solo il codice veramente intelligente usa gare in modi che non sono infranti.

Se questo schema viene eseguito correttamente, quando un thread A effettua una chiamata su un metodo sincrono su un oggetto già utilizzato da un altro thread B, è possibile interrompere l'interleaving A con B finché B lascia il metodo sincrono. Se non c'è mai interferenza tra i thread A e B sullo stesso oggetto astratto, è possibile rimuovere la dichiarazione sincronizzata dalla dichiarazione dell'oggetto. Penso che questo fosse il tuo obiettivo originale

Tutto questo non è facile da organizzare, ed è probabile che sia molto costoso il tempo/lo spazio per l'esecuzione. Cercando di stilare un esempio di tutto questo piuttosto laborioso, quindi non lo farò qui.

I correttori di modello https://en.wikipedia.org/wiki/Model_checking fanno una cosa molto simile in termini di generazione dello "spazio di stato" e hanno problemi di tempo/spazio simili. Se vuoi saperne di più su come gestire lo stato, leggi la documentazione al riguardo.