Semaphor grafisch darstellen < Sonstige < Schule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:45 Mi 03.09.2008 | | Autor: | tomu |
Hallo,
ich habe zwei Prozesse mit Semaphoroperationen:
Prozess1: p(S2) .. v(S2) .. p(S2) .. v(S2)
Prozess2: p(S2) .. v(S2) .. p(S1) .. v(S1)
Wie kann ich das am besten grafisch darstellen um eine evtl. Verklemmung festzustellen?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:55 Mi 03.09.2008 | | Autor: | smarty |
Hallo Tomu,
und herzlich ![[willkommenvh]](/images/smileys/willkommenvh.png "[willkommenvh]")
gibt es zu der Aufgabe noch mehr Informationen?
Grüße
Smarty
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:02 Mi 03.09.2008 | | Autor: | tomu |
Hallo Smarty,
leider nicht viel mehr..
Nur das man bei diesen beiden Prozessen die "parallel" laufen, herausfinden soll, ob hier eine Verklemmung (also ein deadlock) entsteht. Und das ganze dann auch noch "Beweisen". Beim Beweisen habe ich gedacht das es am besten grafisch gezeigt werden kann. Aber ich weiß eben noch nicht was hier eine gute und verständliche Lösung ist...
Das ist auch nur eine Aufgabe von vielen. Die anderen sind aber ähnlich aufgebaut.
|
|
|
| |
|
> Hallo,
>
> ich habe zwei Prozesse mit Semaphoroperationen:
> Prozess1: p(S2) .. v(S2) .. p(S2) .. v(S2)
> Prozess2: p(S2) .. v(S2) .. p(S1) .. v(S1)
>
> Wie kann ich das am besten grafisch darstellen um eine
> evtl. Verklemmung festzustellen?
Dafür verwendet man in der Regel einen "resource allocation graph" mit zwei Arten von Knoten: Prozessknoten und Resourceknoten. Ein Pfeil von einem Prozessknoten zu einem Resourceknoten bedeutet: der Prozess versucht die Resource zu allozieren. Ein Pfeil von einer Resource zu einem Prozess bedeutet: die Resouce ist dem betreffenden Prozess zugeteilt worden. Ganz grob vereinfachend bedeutet Deadlock in einen solchen Graphen die Existenz eines gerichteten Zyklus. (Vereinfachend: es wird insbesondere angenommen, dass kein nachträgliches Entziehen einer bereits zugeteilten Resource möglich ist und dass eine Resource auch nicht mehreren Prozessen zugeteilt werden kann.) Für die Details: suche auf dem Netz einfach nach "resource allocation graph", eventuell mit dem zusätzlichen Stichwort "deadlock".
Ein offensichtliches Problem ist natürlich, dass der resource allocation graph eigentlich nur ein Schnappschuss der augenblicklichen Situation darstellt. Weshalb man zur Klärung der Frage der Existenz eines Deadlocks alle Zustände des resource allocation graphs untersuchen müsste, die aufgrund der Programmlogik überhaupt möglich sind.
Allerdings frage ich mich, ob es Deine Aufgabe wirklich erfordert, mit einem so "primitiven" Synchronisationsmechanismus wie Semaphoren zu arbeiten. Kannst Du nicht einen etwas "strukturierteren" Synchronisationsmechanismus wie z.B. "Monitore" oder Lösungen eines bereits hinreichend analysierten Synchronisationsproblems wie dem (multiple)Reader/(multiple)Writer-Problem (z.B. synchronized message queues) verwenden?
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:56 Do 04.09.2008 | | Autor: | tomu |
Hi,
danke für die Antwort.
Ich habs jetzt mal so dargestellt:
[Dateianhang nicht öffentlich]
Beim unteren Teil sollte es keine Probleme geben, Prozess1 greift auf S2 zu und Prozess2 auf S1.
Im oberen Teil wollen beide Prozesse S2 zur gleichen Zeit nutzen. Aber eigentlich kann es doch gar nicht zu einem deadlock kommen, wenn das ganze durch Semaphoren abgesichert ist, oder?
Irgendwie scheint mir da nochwas unklar zu sein...
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
|
|
|
| |
|
> Hi,
>
> danke für die Antwort.
>
> Ich habs jetzt mal so dargestellt:
> [Dateianhang nicht öffentlich]
> Beim unteren Teil sollte es keine Probleme geben, Prozess1
> greift auf S2 zu und Prozess2 auf S1.
> Im oberen Teil wollen beide Prozesse S2 zur gleichen Zeit
> nutzen. Aber eigentlich kann es doch gar nicht zu einem
> deadlock kommen, wenn das ganze durch Semaphoren
> abgesichert ist, oder?
Bei dieser speziellen Reihenfolge der Verwendung der Semaphoren kann es, wie Du richtig bemerkst, nicht zu einem Deadlock kommen: dies liegt einfach daran, dass keiner der Prozesse eine $p$-Operation auf einer der Semaphoren ausführt, während er sich bezüglich einer anderen Semaphore zwischen einer $p$ und der zugehörigen $v$-Operation befindet. Er gibt also jede Resource (hier: Semaphore) wieder frei, bevor er sich um eine weitere Resource bewirbt.
> Irgendwie scheint mir da nochwas unklar zu sein...
Wenn Dein System keine Prozesse mit in einander verschachtelten, mittels [mm] $p(S_n)\ldots v(S_n)$ [/mm] geschützte Codeblöcke besitzt, kann kein Deadlock auftreten. Denn jeder Prozess gibt nach einer [mm] $p(S_n)$-Operation [/mm] in endlicher Zeit die Semaphore [mm] $S_n$ [/mm] mittels [mm] $v(S_n)$ [/mm] wieder frei, ohne daran durch eine blockierende [mm] $p(S_m)$-Operation [/mm] auf einer anderen Semaphore [mm] $S_m$ [/mm] gehindert werden zu können. Gefährlich wird's erst, wenn Dein Code (dynamisch) in einander verschachtelte [mm] $p(S_n)\ldots v(S_n)$ [/mm] Blöcke besitzt. Wichtig ist der Zusatz: dynamisch. Du musst also die Möglichkeit in Betracht ziehen, dass eine solche Verschachtelung im Quellcode nicht unmittelbar (statisch) sichtbar ist.
|
|
|
|
![[]](/images/popup.gif){kind=small}
http://dbs.uni-leipzig.de/buecher/mrdbs/mrdbs-83.html#MARKER-9-103
