Peterson Algorithmus

[UnWissender2012]

Guten Tag,

ich summiere bei folgendem Code eine Variable hoch, dazu benutze ich zwei Threads.
Insgesamt müsste die Variable nach dem beide Threads fertig sind, auf 400000 stehen.
Das tut sie aber nicht.

Habe ich den Peterson Algorithmus nicht richtig angewendet?

public class Uebung_10_Peterson extends Thread
{
	public static int count = 0;
	
	public void run ()
	{
		sum_up ();
	}
	
	public static void increment ()
	{
		count ++;
	}
	
	public static void sum_up ()
	{
		for (int i = 0; i < 200000; i++)
		{
			increment ();
		}
	}
	
	public static void main (String[] args) throws InterruptedException
	{
		boolean flag0 = false, flag1 = false;
		int turn;
		Thread t1 = new Uebung_10_Peterson ();
		Thread t2 = new Uebung_10_Peterson ();
		
		// Prozess 1
		flag0 = true;
		turn = 1;
		while (flag1 && (turn == 1)) {}	// Busy-waiting
		t1.start ();
		flag0 = false;
		
		// Prozess 2
		flag1 = true;
		turn = 0;
		while (flag0 && (turn == 0)) {}	// Busy-waiting
		t2.start();
		flag1 = false;
		
		t1.join();
		t2.join();
		
		System.out.println("Summe: " + count);
	}
}

 

[Final_Striker]

Bei mir kommt raus:

 Summe: 400000

?

 

[UnWissender2012]

Summe: 223212

Summe: 214866

Summe: 209982

Drei durchläufe, immer überschreiben sich viele viele Variable^^

 

[diggaa1984]

Bei mir kommt raus:

 Summe: 400000

?

bei mir nich ^^

wenn ich aber sowas einbaue klappts logischerweise

public static Object lock = new Object();

public static void increment () {
    synchronized(lock) {
        count ++;
    }
}

 

[diggaa1984]

Vielleicht kann mir aber einer von den Wissenden, mal erklären, warum ein volatile in dem Fall nicht funktioniert/ausreicht?! Hatte es damit auch getestet und es hat nich geklappt.

 

[Lybrial]

Aber der Peterson-Algorithmus ist doch ein fester Algorithmus der ohne zusätzliche Locks, Semaphore oder Mutexe funktionieren sollte oder nicht? Hab mir grad mal in Wikipedia den Algo angeguckt der stimmt mit dem von Unwissender2012 überein (und zwar 1 zu 1, ob das ein Zufall ist )

 

[diggaa1984]

hm hab ihn mir nich angeschaut aber ich bekomme ebenfalls nicht erwünschte aufgabe ohne veränderungen .. meine frage bleibt aber in dem fall dennoch, warum ein volatile das problem nicht löst und ich erst mit nem lock das ziel erreiche ???:L

Zusätzlich natürlich die verwunderung, dass es bei Final_Striker klappt

 

[Firephoenix]

Böse gesagt:
Kommt davon wenn man ohne nachzudenken abkopiert, vor allen Dingen wenn man aus einer anderen Sprache kopiert...

// Prozess #0
// ...
flag0 = true;
turn = 1;
while (flag1 && (turn == 1)) {} // busy waiting
// <kritischer Abschnitt>
flag0 = false;
// ...

Das hier ist Code der in Prozess 0 ausgeführt wird, kritischer abschnitt ist durch die Kritische Methode zu ersetzen, gleiches gilt hierfür:

// Prozess #1
// ...
flag1 = true;
turn = 0;
while (flag0 && (turn == 0)) {} // busy waiting
// <kritischer Abschnitt>
flag1 = false;
// ...

Der Code der im Thread ausgeführt wird ist die run-Methode, folglich benötigt man 2 verschiedene Threads, folgendes Beispiel läuft bei mir durch:

public class Uebung_10_Peterson
{
    // globale Variablendeklaration
    private boolean flag0 = false, flag1 = false;

    private int turn;

    public int count = 0;

    public void increment()
    {
        count++;
    }

    public void sum_up()
    {
        for ( int i = 0; i < 200000; i++ )
        {
            increment();
        }
    }

    public Uebung_10_Peterson()
        throws InterruptedException
    {
        Thread t1 = new Prozess1();
        Thread t2 = new Prozess2();
        t1.start();
        t2.start();

        t1.join();
        t2.join();

        System.out.println( "Summe: " + count );
    }

    public static void main( String[] args )
        throws InterruptedException
    {

        new Uebung_10_Peterson();

    }

    public class Prozess1
        extends Thread
    {
        @Override
        public void run()
        {
            // Prozess #0
            // ...
            flag0 = true;
            turn = 1;
            while ( flag1 && ( turn == 1 ) )
            {
            } // busy waiting
              // <kritischer Abschnitt>
            sum_up();
            flag0 = false;
        }
    }

    public class Prozess2
        extends Thread
    {
        @Override
        public void run()
        {
            // Prozess #1
            // ...
            flag1 = true;
            turn = 0;
            while ( flag0 && ( turn == 0 ) )
            {
            } // busy waiting
              // <kritischer Abschnitt>
            sum_up();
            flag1 = false;
        }
    }
}

Gruß

 

[UnWissender2012]

Hallo,

danke erstmal für die zahlreichen Antworten. Ich habe das nun versucht umzusetzen,
allerdings macht folgender Code überhaupt nichts, außer viel Rechenleistung zu schlucken....

Wenn ich jedoch aus der main z.B. das t2.join() auskommentiere, dann arbeitet ein Thread
zu ende und gibt 200000 aus. Der zweite Thread macht garnichts....
Wenn ich beide joins() rausmache, kommt ein komplett falsches Ergebnis (Z. B. 3028).

Beide Joins drinen scheinen sich irgendwie zu behindern...

public class Übung_10_Peterson
{
	public static void main (String[] args) throws InterruptedException
	{
		CountUp countUp = new CountUp ();
		
		Thread t1 = new ProcessOne (countUp);
		Thread t2 = new ProcessTwo (countUp);
		
		t1.start();
		t2.start();
		
		t1.join();
		t2.join();
	 
	    System.out.println( "Summe: " + countUp.count );
	}
}

public class CountUp
{
	public boolean flag0 = false, flag1 = false;
	public int turn;
    public int count = 0;
    
    public void increment ()
    {
        count ++;
    }
    
    public void sumUp ()
    {
        for (int i = 0; i < 200000; i++)
        {
            increment ();
        }
    }
}

public class ProcessOne extends Thread
{
	private CountUp countUp;
	
	public ProcessOne (CountUp countUp)
	{
		this.countUp = countUp;
	}
	
	public void run ()
	{
		countUp.flag0 = true;
	    countUp.turn = 1;
	    
	    while (countUp.flag1 && (countUp.turn == 1)) {}
	    
	    countUp.sumUp ();
	    countUp.flag0 = false;    
	}
}

public class ProcessTwo extends Thread
{
	private CountUp countUp;
	
	public ProcessTwo (CountUp countUp)
	{
		this.countUp = countUp;
	}
	
	public void run ()
	{
		countUp.flag1 = true;
		countUp.turn = 0;
	    
	    while (countUp.flag0 && (countUp.turn == 0)) {}
	    
	    countUp.sumUp ();
	    countUp.flag1 = false;    
	}
}

 

[TetraTetra]

Schonmal Debugger angeschmissen?

 

[UnWissender2012]

Der Debugger kann mir nicht helfen, da auch er garnicht erst startet....

 

[Garlic]

Vielleicht bei den Threads ein paar Ausgabe-prints setzen?

 

[UnWissender2012]

Hallo,

ja wenn ich mit den System.outs arbeite, stelle ich fest das er manchmal
ewig darauf wartet das Thread 1 sich beendet...
Ganz selten kommt es vor, das beid Threads zum Ende kommen.

Was ist denn das für ein seltsamer Fehler? ^^

 

[UnWissender2012]

Ahhhh....
ich hab gerade festgestellt, wenn ich nach t1.start() nen Thread.sleep() einbaue
funktioniert es. Das heißt wohl das sich die Threads durch Optimierungen (compiler)
in die quere kommen, ist das richtig?
Muss ich volatile verwenden?