Multi Threading: Philosophenproblem

  • VB.NET

Es gibt 8 Antworten in diesem Thema. Der letzte Beitrag () ist von petaod.

    Multi Threading: Philosophenproblem

    Hallo,
    Ich bin ein Informatik Schüler der 12. KLasse. Mir wurde eine Aufgabe gestellt, die ich momentan nicht komplett schaffe zu lösen.
    Wir sollen mit VB das Philosophenproblem (de.wikipedia.org/wiki/Philosophenproblem) Multithreaded lösen.
    Ich habe auch schon einiges geschafft aber ich habe das Problem, das die Threads so nacheinander auf ein Array zugreifen, das sie quasi Ressourcen nutzen die nicht mehr vorhanden sind.
    Wenn ihr wisst was das Philosphen Problem ist, dann können also quasi zwei Philosphen gleichzeitig essen obwohl keine Gabeln vorhanden sein sollten.
    Ich habe hier mal die Sub() die die Threads behandeln:

    VB.NET-Quellcode

    1. Private Sub Schleife(ByVal i As Integer)
    2. Dim time As Integer = rnd.Next(10, 100)
    3. While Not fertig = True
    4. Thread.Sleep(time)
    5. If denken(i) = True Then
    6. While Gabelnda(i) And Gabelnda((i + 1) Mod Gabelnda.Length - 1) = False
    7. Thread.Sleep(200)
    8. End While
    9. Gabelnda(i) = False And Gabelnda((i + 1) Mod Gabelnda.Length - 1) = False
    10. essen(i) = True
    11. denken(i) = False
    12. Else
    13. Gabelnda(i) = True And Gabelnda((i + 1) Mod Gabelnda.Length - 1) = True
    14. essen(i) = False
    15. denken(i) = True
    16. End If
    17. End While
    18. End Sub


    Hat jemand eine idee wie und wo ich die Threads blockieren muss, so das dieser Fehler nicht auftritt?

    Verschoben. ~Thunderbolt

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Thunderbolt“ ()

    @David S. Willkommen im Forum. :thumbup:
    Vielleicht beschreibst Du erst mal verbal, wier Du das Problem lösen willst.
    Wenn wir das verstanden haben, können wir Dir besser helfen.
    Bis dahin essen wir Deine Spaghetti auf. :thumbsup:
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!
    1. Philosoph 1 fragt: Ist Gabel 1 vorhanden? Ja, sie ist vorhanden.
    2. Philosoph 2 fragt: Ist Gabel 1 vorhanden? Ja, sie ist vorhanden.
    3. Philosoph 1 nimmt Gabel 1, weil er vorhin festgestellt hat, dass sie vorhanden ist.
    4. Philosoph 2 nimmt Gabel 1, weil er vorhin festgestellt hat, dass sie vorhanden ist.

    Und zack! Beide Philosophen nehmen die gleiche Gabel.

    Mir stellt sich die Frage, wofür hier überhaupt Multithreading verwendet werden soll. Parallelisierung macht nur Sinn, wenn die Threads möglichst unabhängig voneinander arbeiten können. Das ist hier aber überhaupt nicht der Fall. Die Threads machen ja nichts anderes, als gemeinsam verwendete Ressourcen hin und her zu schieben.

    Der nächste, wichtige Punkt ist, dass diese Simulation komplett deterministisch sein könnte. Aber aus irgend einem Grund bestehen Lehrer wohl darauf, Dinge zu verkomplizieren. War bei mir im Studium auch so: Scheduling Begriffe & Vorgehen Der Lehrer wollte, dass wir das mit Multithreading simulieren und er wollte sich nicht einreden lassen, dass dafür weder Multithreading, noch eine Realtime-Simulation nötig ist.

    Die einfachste Herangehensweise, um das tatsächlich mit Multithreading zu lösen, ist die, dass Du um jeden Lesen-und-Verändern-Zugriff auf das Gabel-Array einen SyncLock-Block packst. Also das Prüfen, ob eine Gabel auf dem Tisch liegt, und das aufheben ebenjener Gabel müssen im selben Block stehen.

    Eigentlich sollte euch der Lehrer diese Grundlagen genau erklären. Und wenn er schon solche Aufgaben gibt, dann sollte er eigentlich auch erklären, dass zum Beispiel eine Instanz von System.Random nicht von mehreren Threads gleichzeitig verwendet werden darf. Steht glasklar in der Dokumentation: msdn.microsoft.com/en-us/libra…tem.random(v=vs.110).aspx
    Ganz unten:

    Thread Safety
    Any public static ( Shared in Visual Basic) members of this type are thread safe. Any instance members are not guaranteed to be thread safe.

    Oben weiter wird das auch genauer erklärt. Als Lösung wird da vorgeschlagen, dass man Zugriffe auf die Instanz in einen SyncLock-Block packen soll. Das ist aber in vielen Fällen unerwünscht, da sich die Threads dann erst wieder in die Quere kommen. Stattdessen solltest Du für jeden Thread eine neue Instanz erzeugen. Entweder als lokale Variable in der von menreren Threads ausgeführten Methode, oder als statisches Feld, das mit ThreadStatic gekennzeichnet ist.

    Wie gesagt: Ich finde, der Lehrer sollte euch diese Möglichkeiten zeigen, bevor er euch solche Aufgaben gibt. Multithreading ist kein Pappenstiel. Es gibt viel Spielraum für Fehler.


    Noch ein paar andere Sachen:

    Bitte verwende im Forum die VB-Tags, damit man den Code besser lesen kann: [Forum] Wie füge ich Quellcode korrekt im Forum ein?

    Deutsche Bezeichner sind eigentlich ein großes No-Go. Es schädigt den Lesefluss, wenn man immer zwischen Deutsch und Englisch hin und her wechseln muss.

    Ähnlich verhält es sich mit If TheThing.IsFrobnicated = True Then. Das redundante = True stört und ändert den Lesefluss von "If the thing is frobnicated, then..." zu "If it's the case that the thing is frobnicated, then...".
    Für negationen gibt's If Not TheThing.IsFrobnicated Then und für Ungleichheit gibt's If TheThing.FrobnicationLevel <> 0 Then. (If Not TheThing.FrobnicationLevel = 0 Then sieht übrigens aus wie If (Not TheThing.FrobnicationLevel) = 0 Then, also bitweises Negieren.)

    Do While (1 = 1)

    Der Unterschied zwischen And und AndAlso/Or und OrElse

    (i + 1) Mod Gabelnda.Length - 1
    Setze bei solchen Sachen lieber mehr Klammern, damit klarer ist, was Du meinst. Der Code ist nämlich äquivalent zu ((i + 1) Mod Gabelnda.Length) - 1, was mir jetzt nicht sofort klar war. Davon abgesehen: Im Falle von i = Gabelnda.Length - 1 kommt hier -1 raus, was kein gültiger Array-Index ist.
    "Luckily luh... luckily it wasn't poi-"
    -- Brady in Wonderland, 23. Februar 2015, 1:56
    Desktop Pinner | ApplicationSettings | OnUtils

    Niko Ortner schrieb:

    Und zack! Beide Philosophen nehmen die gleiche Gabel.
    Da beide die linke Gabel zuerst nehmen sollen, sollte es da keine Schwierigkeiten geben.
    ====
    In so nem Teambildungsseminar wurden wir auch mal mit Spielen "unterhalten", das war so was wie Quartett mit offenen Karten.
    Es gibt Zustände, da ist es sinnvoll, wenn einer alle seine Karten in den Pool schiebt.
    Genau so sollten sich die Herren Philosophen verhalten, wenn nix geht, legen sie die eine Gabel wieder ab.
    Das wäre dann die Auflösung des Deadlock.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!
    @RodFromGermany
    Ich meinte mit "Gabel 1" nicht "die erste Gabel, die der jeweilige Philosoph aufhebt", sondern "Gabel 1 auf dem Tisch". Also Gabel 1 würde in dem Beispiel rechts von Philosoph 1 und links von Philosoph 2 liegen.
    "Luckily luh... luckily it wasn't poi-"
    -- Brady in Wonderland, 23. Februar 2015, 1:56
    Desktop Pinner | ApplicationSettings | OnUtils

    David S. schrieb:

    Hat jemand eine idee wie und wo ich die Threads blockieren muss, so das dieser Fehler nicht auftritt?
    ich tät mal sagen, dass in deinem Code nur ein einziger Thread vorkommt.
    Also besteht das (Philosophen-)Problem überhaupt nicht. Und es gibt auch keine mehrere Threads, die du iwie blockieren müsstest.

    Oder anders: Dein erstes Problem sollte sein, das Philosophen-Problem überhaupt erstmal richtig abzubilden - mit mehreren Threads.

    Imo brauchst du dafür ein Datenmodell, mit mindestens einer Klasse Philosoph, und so ein Philosoph (jeder) muss - im eigenen Thread - zufallsgesteuert denken und essen.
    @ErfinderDesRades Jou. Wenn ich da ein wenig drüber nachdenke, fallen mir solch Worte ein: Mutex, Semaphore, ManualResetEvent, dafür sollt sich @David S. mal interessieren.
    Ich hab den Verdacht, dass der Lehrer unsere Dozenten-Schmähposts gelesen hat. :thumbsup:
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!
    hmm - wie's genau lösen gibts wohl viele Wege (und ich wüsste grad nichtmal, wie).
    Nur wie gesagt: Bevor nichtmal das Problem korrekt nachgestellt ist, braucht man den TE nicht mit Lösungsansätzen zu verwirren.

    Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „ErfinderDesRades“ ()

    Lege für jeden Platz einer Gabel eine ConcurrentQueue an.
    Jeder Philosoph versucht regelmässig beiden für ihn vorgesehenen Queues eine Gabel zu entnehmen (TryDequeue).
    Nach dem Essen legt er die Gabeln in die jeweilige Queue zurück (Enqueue).

    Deadlock lösen:
    Wenn ein Philosoph eine Gabel hat und nicht innerhalb einer bestimmten Zeit eine zweite Gabel bekommt, muss er seine Gabel wieder zurücklegen und eine kurze Zeit warten.

    Jetzt kannst du jeden Philosophen in einen eigenen Thread verlagern.

    Für die Variante des Spiels, wo alle Gabeln in der Mitte liegen, reicht eine einzige ConcurrentQueue für alle Gabeln.
    --
    If Not Program.isWorking Then Code.Debug Else Code.DoNotTouch
    --