[C++/Java] Come si fa il testing con thread concorrenti ?

[cionci]

Usando JUnit e CPPUnit in una applicazione multithread, come si fa a testare e verificare la correttezza della gestione della concorrenza ?

Cioè mettiamo che ci siano due thread, A e B, che devono accedere ad una classe condivisa, come si fa a scrivere un test che verifica che se A è in sezione critica B non entra in sezione critica se prima A non ne è uscito ?

[lovaz]

In caso di java e' il linguaggio stesso che se ne preoccupa,
quando un blocco e' synchronized il programmatore sa
che solo un thread alla volta ci entrera'.

Per il C++ non so se il supporto e' a livello cosi' "basso".

Se invece intendi dimostrare che un programma non avra' mai
problemi di deadlock e affini mi sembra che il problema
non abbia soluzione per un prog. generico, ma solo
per casi (molto) banali.

[cionci]

In effetti non avevo pensato ai metodi synchronized...
In C++ non ci sono costrutti a livello di linguaggio che permettono di esprimere la mutua esclusione, ma questa deve essere implementata con le syscall del sistema o con alcune librerie non standard...

Quindi limitandoci al C++ e al caso riportato sopra di due o più thread in mutua esclusione come si fa ?
Che poi sarebbe anche il caso in cui un metodo non sia synchronized, ma la sincornizzazione avviene su un determinato oggetto all'interno del metodo...

Non voglio dimostrare l'assenza di deadlock, ma volevo esprimere tramite test la necessità di una mutua esclusione...

Schematicamente:

MioThread A, B;
ClasseCondivisa cl;
A.avvia(cl);
B.avvia(cl);
//mettiamo che A e B girino accedendo a cl diverse volte
while(A.isRunning() || B.isRunning());

assert(cl è stata acceduta in mutua esclusione);

Quali costrutti si potrebbero usare per un simile test ?
L'unica cosa che mi viene in mente è registrare gli accessi alla classe....

[lovaz]

La prima cosa che mi viene in mente:

all'inizio della sezione critica ci metti:

control = <qui metti qualcosa che indica univocamente il thread,
tipo il nome della classe, ecc.>

alla fine fai un assert che controlla che control sia ancora nel suo stato,
altrimenti vuol dire che e' stata "sporcata" da un altro thread.

Potrebbe essere del tutto scorretto, magari aspetta qualche "guru" della
concorrenza, tipo PGI-Bis

[PGI-Bis]

Ma che guru, manco ghiro!

Son talmente guru che, incuriosito dalla faccenda ho provato, in Java, a monitorare l'accesso di un Thread ad un metodo registrando codice hash e tempo di accesso e controllando, ogni volta che un Thread accede al metodo, se questo accesso sia sovrapposto a quello di un altro Thread (entrato e non ancora uscito o entrato e uscito in un periodo intersecante il tempo di accesso del nuovo Thread).

Risultato del test da guinnes dei primati: due thread non sono mai in conflitto o lo sono sempre! A prescindere dalla sincronizzazione!

E i mutex e i lock e i semaphores...TUTTE PALLE! C'ho qui il test c'ho! Carta canta signori! Ho quadrato il cerchio della concorrenza ho quadrato!

Avete problemi di concorrenza? ANTICHI!!! Buttate nel codice il test di PGI-GURU DELLA CONCORRENZA e per magia i vostri Thread o non saranno mai in conflitto o lo saranno sempre!

Ci faccio i miglioni ci faccio!

[cionci]

Posta un po' per curiosità

[lovaz]

Ma va guru dei miei stivali... Sei 'na sola...

[thebol]

Mockare la classe condivisa? o i thread che ci accedono?
l'obbiettivo sarebbe quello di creare con un test una situazione sporca data dalla cattiva concorrenza, ma in pratica non saprei bene come fare...

[cionci]

Avevo pensato anche io a mockare la classe condivisa, ma è un lavoro dispendioso...soprattutto se le classi condivise sono tante...

Diciamo che non voglio testare le situazioni "sporche", anche perchè srebbe impossibile, soprattutto per le catene di lock, che sono troppo time-depend. Principalmente volevo esprimere la necessità di inserire la gestione della concorrenza.... L'obiettivo è di essere obbligati dal test ad inserire la gestione della mutua esclusione (immaginatevi di essere in un ambito Test Driven)

[thebol]

Originariamente inviato da cionci

Avevo pensato anche io a mockare la classe condivisa, ma è un lavoro dispendioso...soprattutto se le classi condivise sono tante...

Diciamo che non voglio testare le situazioni "sporche", anche perchè srebbe impossibile, soprattutto per le catene di lock, che sono troppo time-depend. Principalmente volevo esprimere la necessità di inserire la gestione della concorrenza.... L'obiettivo è di essere obbligati dal test ad inserire la gestione della mutua esclusione (immaginatevi di essere in un ambito Test Driven)

fai 2 mock thread che "apposta" si sovrappongano (senza syncronize o simili) generando una situazione sporca(RED). Poi aggiungi syncronize e il test dovrebbe andare(GREEN). Poi giu di refactoring

[cionci]

Originariamente inviato da thebol

fai 2 mock thread che "apposta" si sovrappongano

Come
Il test ovviamente deve fallire sempre, se non è gestita la mutua esclusione...ma questa condizione non è garantita...

Vediamo forse qualcosa mi viene in mente per testarlo...lo elaboro oggi quando torno a casa... Però mi sa che porta ad un deadlock...

[PGI-Bis]

Posto ma solo per espormi al pubblico dileggio!

Teoricamente non faceva una piega. La prima istruzione del metodo acceduto è la registrazione dell'accesso del Thread che accede e l'ultima è la registrazione dell'uscita da parte dello stesso Thread. Quando è registrato un accesso, il registro controlla se il tempo di "entrata" si sovrappone con un periodo di accesso già registrato per un Thread diverso.

Quello che ho scritto, però, non coincide. Un chiaro caso di cervello distribuito: metà in testa e metà nelle dita .

public class CriticalAccess {
	private final long acquireTime;
	private final int threadId;
	private volatile long releaseTime;
	
	public CriticalAccess(int threadId, long acquireTime) {
		this.acquireTime = acquireTime;
		this.threadId = threadId;
	}
	
	public boolean hasThreadId(int id) {
		return threadId == id;
	}
	
	public long getAcquireTime() {
		return acquireTime;
	}
	
	public long getReleaseTime() {
		return releaseTime;
	}
	
	public void setReleaseTime(long t) {
		releaseTime = t;
	}
	
	public boolean overlaps(long time) {
		if(releaseTime != 0) {
			return time > acquireTime && time < releaseTime;
		} else {
			return time >= acquireTime;
		}
	}
	
	public String toString() {
		return "ID:"+threadId+"...STARTED:"+acquireTime+"...ENDED:"+releaseTime;
	}
}

import java.util.*;

public class CriticalAccessRegistry {
	private final long time0 = System.nanoTime();
	private ArrayList<CriticalAccess> registry = new ArrayList<CriticalAccess>();
	
	private static final CriticalAccessRegistry sharedInstance =
		new CriticalAccessRegistry();
		
	public static CriticalAccessRegistry getSharedInstance() {
		return sharedInstance;
	}

	public void registerAcquire(int threadId) {
		long timeStamp = getTime();
		putAcquire(threadId, timeStamp);
	}
	
	public void registerRelease(int threadId) {
		long timeStamp = getTime();
		putRelease(threadId, timeStamp);
	}
	
	private synchronized void putAcquire(int threadId, long timeStamp) {
		CriticalAccess overlapped = checkOverlaps(threadId, timeStamp);
		CriticalAccess ca = new CriticalAccess(threadId, timeStamp);
		if(overlapped != null) {
			System.out.println(ca + " conflicts with " + overlapped);
		}
		registry.add(ca);
	}
	
	private synchronized void putRelease(int threadId, long timeStamp) {
		CriticalAccess ca = getAccess(threadId);
		if(ca != null) ca.setReleaseTime(timeStamp);
	}
	
	private CriticalAccess checkOverlaps(int id, long time) {
		for(int i = 0; i < registry.size(); i++) {
			CriticalAccess c = registry.get(i);
			if(!c.hasThreadId(id) && c.overlaps(time)) {
				return c;
			}
		}
		return null;
	}
	
	private CriticalAccess getAccess(int threadId) {
		for(int i = 0; i < registry.size(); i++) {
			CriticalAccess c = registry.get(i);
			if(c.hasThreadId(threadId)) return c;
		}
		return null;
	}
	
	private long getTime() {
		return (System.nanoTime() - time0) / 1000000L;
	}
	
	public void dump() {
		for(CriticalAccess c : registry) {
			System.out.println(c);
		}
	}
}

import java.util.*;

public class SharedResource implements Runnable {
	private final Random random = new Random();
	
	public void run() {
		while(true) {
			CriticalAccessRegistry.getSharedInstance().
				registerAcquire(Thread.currentThread().hashCode());
			sharedAccess();
			CriticalAccessRegistry.getSharedInstance().
				registerRelease(Thread.currentThread().hashCode());
			if(Thread.currentThread().isInterrupted()) {
				System.out.println("Threadus interruptus!!!");
				return;
			}
		}
	}
	
	public void sharedAccess() {
		try {
			Thread.sleep(100);
		} catch(InterruptedException swallow) {
			Thread.currentThread().interrupt();
		}
	}
}

public class Test {

	public static void main(String[] args) {
		long testTime = Long.parseLong(args[0]);
		while(CriticalAccessRegistry.getSharedInstance() == null);
		SharedResource res = new SharedResource();
		Thread a = new Thread(res);
		Thread b = new Thread(res);
		a.start();
		b.start();
		long startTime = System.currentTimeMillis();
		while(System.currentTimeMillis() - startTime < testTime);
		a.interrupt();
		b.interrupt();
	}
}

Sempre teoricamente, il test non è quello previsto da cionci perchè è probabilistico: due thread che accedono alla stessa regione di memoria possono sovrapporsi ma non è detto che lo facciano. Per avere un test deterministico bisognerebbe (credo) conoscere i dettagli degli algoritmi di schedulazione del sistema operativo.

Comunque, quella roba lì sopra "la va no", non funziona.

[thebol]

Originariamente inviato da cionci

Come
Il test ovviamente deve fallire sempre, se non è gestita la mutua esclusione...ma questa condizione non è garantita...

Vediamo forse qualcosa mi viene in mente per testarlo...lo elaboro oggi quando torno a casa... Però mi sa che porta ad un deadlock...

2 thread che si conoscono sincronizzati fra di loro per entrare contemporaneamente

ps.sto ipotizzando a livello astratto, non so quanto sia fattibile in generale, e nel tuo caso..

[thebol]

http://en.wikipedia.org/wiki/Monkey_test

qua ipotizza l'utilizzo del monkey test per i thread.

non approfondisce molto, ma magari qualcosa sul web si trova

[cionci]

Cioe' si tratterebbe di fare avanzare N thread casualmente in modo di produrre con alta probabilita' un errore ?

Mi sembra una situazione un po' limite, cioe' significherebbe comunque un test che, in caso di codice errato, comunque ha una certa probabilita' di risultare verde...
Pero' magari con un numero elevato di thread questa probabilita' potrebbe essere molto piccola...boh...

[Angus]

Originariamente inviato da cionci

Cioe' si tratterebbe di fare avanzare N thread casualmente in modo di produrre con alta probabilita' un errore ?

Mi sembra una situazione un po' limite, cioe' significherebbe comunque un test che, in caso di codice errato, comunque ha una certa probabilita' di risultare verde...
Pero' magari con un numero elevato di thread questa probabilita' potrebbe essere molto piccola...boh...

Infatti la vera questione è se questo sia un problema da approcciare con metodologie deterministiche oppure no. Sinceramente non so rispondere, ma a naso scommetterei sull'approccio statistico con il dubbio che qualcosa possa sempre sfuggire.

[cionci]

Mmmmhhh...sinceramente ancora non mi convince... Cercherò di approcciare la cosa in modo diverso

[Angus]

Originariamente inviato da cionci

Mmmmhhh...sinceramente ancora non mi convince... Cercherò di approcciare la cosa in modo diverso

Hai già letto questo?

[cionci]

Sì, l'ho letto qualche giorno fa...