Semaphore in Java

[herrnerz]

Hi

ich könnte dringend Hilfe gebrauchen bei der folgenden Aufgabe:

<-----L1--------___________________<------X--------- o <------R1------

____________o<----------A---------->o

------L2------>____________________------Y---------> o ------R2------->

____________Beginn Brücke______________________Ende Brücke

Bei der Zeichnung handelt es sich um 7 Streckenabschnitte, von denen A, X und Y auf einer Brücke liegen. Diese darf nur von 2 FAhrzeugen gleichzeitig befahren werden. Die Abschnitte A, X und Y können immer nur ein Fahrzeug aufnehmen.

Synchronisieren sie mittels Semahoren.

Beachte: Keine Kollisionen (auch keine Auffahrunfälle), Sperrphasen möglichst kurz halten, keine Verklemmungen dürfen auftreten.

Zu Beginn ist alles frei, L1, L2, R1, R2 müssen nicht synchronisiert werden.

So. jetzt hab ich mal versucht das in Java zu schreiben, bin mir aber ganz und gar nicht sicher ob das so stimmt und bin für jeden Kommentar äußerst dankbar!

package semaphore;


public class Bridge {


	Semaphor xfrei   = new Semaphor(1);

	Semaphor yfrei   = new Semaphor(1);

	Semaphor afrei   = new Semaphor(1);

	Semaphor brueckefrei   = new Semaphor(2);


	public void Rfahrzeug {

		while (1 == 1) {

			brueckefrei.P();

			xfrei.P();

			// R1 -> X			

			afrei.P();

			// X -> A			

			xfrei.V();

			// A -> L1

			brueckefrei.V();

			afrei.V();			

		}

	}


	public void Lfahrzeug {

		while (1 == 1) {

			brueckefrei.P();

			afrei.P();

			// L2 -> A

			yfrei.P();

			// A -> Y

			afrei.V();

			// Y -> R2

			brueckefrei.V();

			yfrei.V();			

		}

	}

}

Bearbeitet 16. September 2011 von herrnerz

[flashpixx]

Sperrungen kann man dedektieren: Der Serialisierungsgraph muss azyklisch sein, damit kein Deadlock entsteht. Wenn für Dein Beispiel Dir diesen aufmalst und es eben kein Kreis ist, dann tritt hast Du den Deadlock ausgeschlossen. Zusätzlich gebe ich mal den Hinweis, dass ein 2-Phasen-Locking besser ist :-P Ein Bsp dafür wäre

lock(a)

do(a)

lock(

do(

free(

free(a)

[/code]

Du hast in Deinem Beispiel ein 1-Phasen-Locking verwendet

Das Berechnen der optimalen Lösung ist np-hart, sollte aber bei diesem Beispiel noch möglich sein.

[herrnerz]

aber wie soll ich dass denn hier realisieren?

ich kann ja nicht erst die brücke reservieren und dann reinfahren, weil ich noch zusätzlich prüfen muss, ob der erste abschnitt auch frei ist.

genausowenig kann ich erst den kleinen abschnitt prüfen, reinfahren, und dann die brücke prüfen, weil ja am anfang die zwei anderen abschnitte belegt sein könnten und ich gar nicht in den einzelabschnitt fahren darf.

also folgt doch, dass ich auf jeden fall erst die brücke prüfen muss. dann kann ich aber noch nichts machen, also muss ich danach den abschnitt prüfen.

oder seh ich das falsch?

btw heißt 2 phase locking einfach, dass man das erste lockt und dann gleich ausführt, dann das zweite lockt und ausführt?

[flashpixx]

btw heißt 2 phase locking einfach, dass man das erste lockt und dann gleich ausführt, dann das zweite lockt und ausführt?

Das 2-Phasen-Locking besagt, dass ein Thread nicht direkt hintereinander die gleiche Resource blockiert und dass eben eine Reihenfolge existiert wie Locks gesetzt und wieder gelöst werden.

Du hast bei Deinem Problem mehrere Resourcen (Deine Strecken) und diese dürfen nur in einer gewissen Art und Weise blockiert werden, z.B. wenn R1 durch eine Strecke gefahren und die nächste passieren will, dann kann man sich überlegen, dass die Locks jetzt für R1 (wenn man ihn mal unabhängig betrachtet) wie eine "Welle" durchlaufen, d.h. man sollte versuchen, wenn R1 durch läuft eben die Resourcen nicht gelockt sind.

[herrnerz]

hm ich verstehs einfach nicht ganz, sorry

könntest du mirs mal anhand meines beispiels erläutern? wär sehr nett!

[flashpixx]

so etwas wäre verboten:

while (true) {

lock(a)

do(a)

free(a)

}

weil folgendest entstehen kann:

lock(a)

do(a)

free(a) <<=


lock(a) <<=

do(a)

free(a)

es entsteht die Freigabe von a und direkt wieder ein lock von a. Man müsste nach dem ersten free(a) sicherstellen, dass nun alle anderen Threads ihre Arbeit machen dürfen, bevor erst wieder a arbeiten darf.