[JAVA] Vraagje mbt. Threads en concurrency

[Macros]

Ik ben een kleine applicatie aan het bouwen die bepaalde dingen simuleerd. Die app wil ik ook draaien op iets snellere machines met meer dan 1 cpu. Nu heb ik een tijdje geleden met MPI gewerkt op een redelijke cluster, wat erg fijn werkte. Daarbij moest ik op arrays en matrices werken, dat deed je dan door dezelfde code te hebben voor elke node, maar dat elke node een andere range van de array bewerkte.
Nu moet ik in deze app ook met arrays werken, waarbij elke thread dus fijn zijn gedeelte van de array neemt. Na een tijdje denken, heb ik besloten om een soort alternatieve versie van Thread en Runnable te maken, de MultiThread en MultiRunnable. Daarbij heb ik dan alvast een AbstractMultiRunnable gemaakt, die heel wat handige dingen implementeerd. Waaronder een soort van sync functie. In MPI werkte bijna alle functies als een soort sync functie, ben even de naam kwijt. Daarmee bedoel ik dat alle threads/processes pas doorgaan als ze allemaal daar zijn gekomen.
Ik heb nu een implementatie, maar volgens mij gaat ie niet werken.

Java:

public abstract class AbstractMultiRunnable implements MultiRunnable{
    private int id;
    private boolean[] ready;
    private int size;
    
    public AbstractMultiRunnable(){
        Arrays.fill(ready, false);
    }
    public void syncAllThreads(int id){
        ready[id] = true;
        notifyAll();
        while(!othersAreReady()){
            try {
                wait();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
        ready[id] = false;
    }
    public boolean othersAreReady(){
        for(int i = 0; i < ready.length; i++)
            if(!ready[i])//one other is not ready
                return false;
        return true;
    }
}

Ik heb dus een array met booleans, als processes 'out of sync' zijn, dan is zijn boolean false. Als ze gaan syncen, dan zetten ze hun boolean op true. Ze mogen de methode syncAllThreads() dus pas verlaten als iedereen op true staat. Als dat niet het het geval is gaan ze wachten, totdat ze door een andere thread weer wakker worden gemaakt, omdat hij op zijn punt is gekomen.
Opzich lijkt het goed te gaan, maar nu het probleem. Als ze allemaal daar zijn beland, dan moet de boolean weer op false worden gezet. Als er 1 al aan het verlaten is, terwijl een ander nog aan het testen is, dan verlaat de ene, maar blijft de ander hangen.
Ik besef me nu dat ik ook een syncronized int veld kon gebruiken en die ophogen met 1 als een thread klaar is en controleren of hij even groot is als size (het aantal threads). Maar dan houd ik hetzelfde probleem met dat veld resetten.
Ik kan natuurlijk een sleep van een aantal milliseconden aan het einde van de sync zetten, zodat ik (bijna) zeker weet dat niemand meer aan het testen is de booleans terug gezet worden.

Ik heb nu ineens een andere ideetje...
Maar misschien hebben jullie ook nog iets briljants...

[Soultaker]

Ik neem aan dat die Java-code bedoelt was als pseudo-code, of is het de bedoeling dat ik alle lompe fouten erin ga aanwijzen?

[Macros]

Het is niet de complete code, maar er zitten geen lompe fouten in

[Soultaker]

Inhoudelijk: volgens mij kun je hier best een soort semafoor voor gebruiken; je krijgt dan een implementatie met een tellertje zoals je zelf al zei. Elke thread kijkt of 'ie de laatste is, zo niet, dan gaat 'ie slapen tot 'ie wakker gemaakt wordt. De laatste thread reset de teller en maakt alle threads wakker:

Java:

class Synch
{
    protected int waiting, total;

    Synch(int totalThreads) {
        total = totalThreads;
    };

    synchronized void synch() {
        if(++waiting < total)
        {
            try { 
                wait(); 
            } catch (InterruptedException e) { 
                --waiting; // of misschien niet; hangt er vanaf wat je hier wil.
                e.printStackTrace(); 
            }
        }
        else
        {
            waiting = 0;
            notifyAll();
        }
    }
}

edit:
Die InterruptedException in Java is dus weer gruwelijk irritant. Waarom hebben ze dat ding in godsnaam verzonnen?! Ik zou denken dat je in dit geval misschien wel het beste die InterruptedException door zou kunnen gooien, want als een thread niet succesvol kan wachten dan kun je het algoritme niet goed uitvoeren. Als soort van hack zou je dan kunnen gaan spinlocken en dan wordt je code zoiets:

Java:

    synchronized void synch() {
        ++waiting;
        if(waiting < total)
        {
            while(waiting > 0)
            {
                try { 
                    wait(); 
                } catch (InterruptedException e) { 
                    // ignored.
                }
            }
        }
        else
        {
            waiting = 0;
            notifyAll();
        }
    };

Maar dit werkt alleen perfect als Java FIFO gedrag garandeert van notifyAll (dat wil zeggen: als het niet mogelijk is dat een thread opnieuw join() uitvoert voordat alle threads uit een vorige iteratie de synch() methode verlaten hadden).

[ Voor 49% gewijzigd door Soultaker op 14-07-2004 00:25 ]

[Macros]

Als synch() zelf synchronized is, dan worden andere threads toch geblocked? Of niet als ze aan het slapen zijn in hun wait()?

Hmm, ziet er wel strak uit.

[Soultaker]

Bij een call naar wait() releast de huidige thread de monitor lock (en zodra 'ie retourneert krijgt 'ie 'm weer terug). Dit soort code is typisch voor het gebruik van monitors als synchronisatieprimitieve.

[Macros]

Ik wilde net een opmerking maken over hoe je code fout was, maar ik zie dat je het al verbeterd hebt

[Soultaker]

Wat was dat dan? Ik geloof niet dat ik inhoudelijk wat veranderd heb (alleen een : vervangen door een ; ).

[Macros]

Die code na je edit:, dus die spinlock. Er is niks mis met spinlocks!
Nog een vraagje, de totale code is nog niet af, dus ik kan het nu niet goed testen, maar werkt dit ook als alle threads op een eigen instantie van het object waar deze functie in draait werken?
int waiting moet dan wel static zijn natuurlijk.

[ Voor 61% gewijzigd door Macros op 14-07-2004 00:34 ]

[Soultaker]

Die tweede code werkt dus niet goed, omdat Java geen FIFO werking garandeert. Dat is natuurlijk wel te fixen, maar het blijft ranzig.

De eerste code werkt alleen goed als de thread nooit interrupted wordt; het is maar de vraag wat je dan moet doen. Je kunt het nauwelijks 'goed' afhandelen. In dit geval zou ik de exception het liefst gewoon helemaal negeren (en de synch() methode 'm dus ook laten gooien).

[Macros]

Hoe gooit het dan een kink in de kabel vanwege non-fifo?

[Soultaker]

Stel: je hebt een interrupted thread die niet als laatste syncht en dus aan het spinlocken is, laten we 'm X noemen. Uiteindelijk komt er een laatste thread, genaamd Y, die notifyAll() aanroept en daarmee alle wachtende threads in de ready queue gooit, waiting op 0 zet en vervolgens retourneert.

Nu wordt er een thread wakker gemaakt en laten we even zeggen dat dat thread Z is. Deze thread retourneert en niets weerhoudt 'm ervan om synch() weer aan te roepen nog voordat thread X uit synch() is geraakt (simpelweg omdat Z op een singleprocessorsysteem binnen z'n timeslice blijft of omdat er eerst nog andere threads wakker gemaakt zijn). Als 'ie dit doet, dan verhoogt 'ie waiting met 1. Omdat waiting nu groter dan 0 is zal X nooit meer uit z'n spinlock komen en aangezien hij dus ook nooit meer waiting zal ophogen, raken alle threads die synch() aanroepen deadlocked.

Als Java zou garanderen dat threads unlocked worden in volgorde waarop ze genotified werden, dan zou thread Z blocken op de call naar synch() totdat alle threads die er nog in zaten maar al genotified waren, inclusief thread X, klaar waren. In dat geval gaat het dus goed. Er zijn wel systemen die dit soort garanties bieden (of waarvan je de monitor kan configuren om dit soort garanties te geven) maar zoals duidelijk gedocumenteerd staat bij Object.notify() geeft de JVM deze garantie niet.

[ Voor 3% gewijzigd door Soultaker op 14-07-2004 00:45 ]

[Macros]

Maar een nachtje over slapen hoe we dat weer op kunnen lossen...
Misschien kan je elke thread even laten yielden voordat ie uit de functie stapt. Zodat iedereen even tijd krijgt om uit de lock te komen?

[Soultaker]

Ik lees net dat de interrupted status gecleared wordt na die InterruptException. Als je 'm dus negeert dan kun je gewoon weer in wait() gaan. Ik moet zeggen dat mij niet helemaal duidelijk is of 'ie ook de monior terugkrijgt als die exception gegooid wordt. Ik neem aan van wel, maar dat zou dus betekenen dat die exception niet altijd 'direct' gegooid kan worden.

Nadeel is wel dat je zo dus de interrupted status helemaal cleared en dat een interrupt() call vanuit een andere thread op deze manier verloren gaat. Het is een beetje de vraag of je dat wil; Java's eigen functies (zoals I/O functies die niet interrupted kunnen worden) bewaren de interrupted status tot na hun uitvoeren. Je zou dan dus de code moeten uitbreiden zo, dat je bijhoudt of de thread interrupted was. Samen wordt de code dan zoiets:

Java:

    synchronized void synch() {
        if(++waiting < total)
        {
            boolean interrupted = false;
            while(true)
                try { 
                    wait(); 
                    break;
                } catch (InterruptedException e) { 
                    interrupted = true;
                }
            if(interrupted)
                Thread.interrupt();
        }
        else
        {
            waiting = 0;
            notifyAll();
        }

Oplossingen met 'even yielden' helpen voor theoretische veiligheid niet. In de praktijk kan het iets schelen, maar mijn ervaring is dat de wet van de grote getallen er voor zorgt dat situaties die in theorie met een hele kleine kans voor kunnen komen in de praktijk vroeger of later wel voorkomen en problemen veroorzaken. Je kunt het mijns inziens dus beter in een keer goed doen.

edit:
Het is laat, dus ik durf niet de garanderen dat de code zo 100% correct is. Ik hoop dat morgen nog iemand anders een kritische blik op dit topic werpt...

[ Voor 7% gewijzigd door Soultaker op 14-07-2004 01:01 ]

[Baron]

Er is een goed Java concurrency bibliotheek beschikbaar.

http://gee.cs.oswego.edu/...urrent/CyclicBarrier.html

Deze wordt geïmplementeerd in jdk1.5

[Macros]

Baron schreef op 14 juli 2004 @ 09:37:
Er is een goed Java concurrency bibliotheek beschikbaar.

http://gee.cs.oswego.edu/...urrent/CyclicBarrier.html

Deze wordt geïmplementeerd in jdk1.5

Mooi, die CyclicBarrier ga ik waarschijnlijk gebruiken. Misschien ook wel die low overheid Tasks/Threads.