Zum Inhalt springen
L

Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).

Vorlesung Betriebssysteme - 05 Synchronisation

Horst Schirmeier1:36:20 2.703 Aufrufe veröffentlicht Auf YouTube

Das Wichtigste aus dem Video

Tipp auf eine Zeit – das Video springt genau dorthin.

Transkriptautomatisch erstellt · 647 Zeilen
Herunterladen
  1. Ja, willkommen zurück zu Betriebssysteme. Ähm, auch heute wieder ein paar Ankündigungen,
  2. zunächst mal etwas unerfreuliches. Ähm, wir haben ja letzte Woche die letzten Abgaben zu Aufgabe null bekommen und wir haben tatsächlich äh so ein paar
  3. mehrfachabgaben gefunden. Ja, also sprich ähm Gruppen, die scheinbar unabhängig voneinander, vielleicht auch nicht, ähm dieselben
  4. Abgaben getätigt haben. Ähm das können wir kann ich so nicht durchgehen lassen. Also wir werden mit den betreffenden Leuten mal sprechen.
  5. Also im Raum steht tatsächlich die Androhung äh dass diejenigen Leute die Studienleistung dieses Semester nicht mehr ja erbringen können. Ähm, also ich
  6. möchte Sie noch mal darauf hinweisen, noch mal explizit bitten, dass Sie die Aufgaben selbst lösen. Ja, also wenn Sie da irgendwie Schwierigkeiten haben, es
  7. gibt den Helptesk, ja, da weiß ich auch hier gleich in der nächsten Zeile noch mal explizit drauf hin. Ähm, wenn Sie Schwierigkeiten mit den Aufgaben haben,
  8. nutzen Sie den Helpdesk, dafür ist er da. Ja, und im Zweifelsfall, also wenn es wirklich irgendwie kurz vor der Abgabe Deadline ist und sie haben noch
  9. nicht die komplette Aufgabe gelöst, dann geben Sie sie teilweise ab. Ja, ich möchte keine Plagiate, keine mehrfachabgaben sehen und äh wir werden
  10. die angekündigten ja Konsequenzen auch durchziehen, wenn das äh wenn es notwendig ist. Ähm ja, auch
  11. heute gibt's wieder einen Live Q&A Termin oder äh Fragestunde äh 1515 bis 16:45. Ähm, ich freue mich auch, wenn Sie vorab
  12. wieder Fragen einreichen. Bis jetzt habe ich noch keine bekommen heute. Das ist entweder ein gutes Zeichen, weil sie alles verstanden haben, durchschauen,
  13. was es bei um was es bei Betriebssystem geht. Ähm vielleicht ist es auch kein gutes Zeichen, ja, dass ich sie alle abgehängt
  14. habe. Ich wäre wäre sehr dankbar, wenn ich da Feedback bekommen würde und vielleicht ein paar Fragen, die ich da besprechen kann. Ähm und wenn Sie das
  15. vorher einreichen, dann habe ich eben noch ein bisschen eine Chance, das vorzubereiten. Und jetzt mal noch was in äh
  16. Betriebssystem fremder Sache. Ähm es findet ab dieser Woche, ab Mittwochabend die Kiff die Kiff 48,0, das ist die äh die Konferenz der Informatik oder die
  17. Konferenz, doch die glaub die Konferenz der Informatikschaften. Ähm die sollte eigentlich endlich mal wieder in Dortmund stattfinden. Das
  18. passiert natürlich jetzt nicht, sondern sie findet im Neuland statt, um in der Formulierung der Veranstalter zu sprechen. Ähm geht am Mittwochabend los,
  19. soweit ich weiß, kann man auch durchaus noch ähm sich anmelden, teilnehmen und ähm ja, die freuen sich sicherlich über noch mehr äh noch mehr Besucher.
  20. Soweit zum organisatorischen kann man mich eigentlich verstehen. Also, der Vorlesungschatraum ist ganz ganz ruhig momentan.
  21. Akustisch, visuell, alles in Ordnung oder auch nicht? Da kommt was. Okay, anscheinend kann man mich verstehen. Das ist schon mal hilfreich.
  22. Okay. Ähm, soweit dazu. Letztes Mal haben wir Moment,
  23. viel zu viele Fenster offen. Letztes Mal haben wir über Scheduling gesprochen. Ich bin etwas leise. Okay, dann schaue
  24. ich mal, ob ich das hier noch hochdrehen kann. Das ist immer so ein bisschen so ein Warbon Spiel zwischen zu laut und übersteuert und zu leise.
  25. Man versteht es nicht. Jetzt habe ich mal den Mic Gay noch ein bisschen hochgedreht. Ja, letztes Mal haben wir über äh
  26. Scheduling gesprochen und zunächst mal haben wir da über äh ja Abfertigungszustände gesprochen und da haben wir unter anderem letztendlich
  27. diese Zustandsübergänge angeschaut. Ja, also es waren diese Einplanungsebenen ähm
  28. letztendlich kurzfristig, mittelfristig und langfristig. Ja, langfristig sind ist um diese Einplanung, wann werden überhaupt Prozesse gestartet? Wann
  29. werden sie beendet? Na, das sind Dinge, die z.B. regulär in so Rechenklustern stattfinden. Medium term oder mittelfristig sind so
  30. Dinge wie das Einlagern und Auslagern von Prozessen. Ja, also wenn festgestellt wird, dass nicht genug Hauptspeicher da ist, dann kann es eben
  31. kann das das Betriebssystem sich eben entscheiden oder der Scheduler sich entscheiden, einen Prozess auszulagern. Und das Short Term scheduling, das
  32. trifft eben so Entscheidungen zwischen lauffähig, also ready tatsächlich laufend, also der hat die CPU zugeteilt bekommen oder blockiert, wenn ein
  33. Prozess auf eine Ausgabe wartet, ne? Und diese vier hier rot äh oder mit mit Zahlen markierten Zustandsübergänge waren die vier ähm bei denen der
  34. Scheduler tatsächlich Entscheidungen trifft. Ja, und dann haben wir uns klassische CPU Zuteilungsstrategien angeschaut.
  35. Ähm, da will ich jetzt ein bisschen schneller drüber fliegen, weil das kann ich nicht noch mal alles wiederholen. Ähm, angefangen hatten wir letztendlich
  36. mit dem einfachsten Verfahren, dass man sich so wahrscheinlich vorstellen kann. erstmal äh das ist FCFS, First Come. First served
  37. ähm da haben wir unter anderem den sogenannten Konvoyeffekt gesehen. Ja, also wir hatten hier vier Prozesse, A, B, C, D, ähm, von denen zwei, nämlich B
  38. und D, sehr langlaufend waren. Sie haben eine sehr lange Bedienzeit, also belegen die haben einen sehr langen CPU-Soß und das sorgt dafür, dass alle Prozesse,
  39. die nach so einem Prozess mit lang mit langen CPU-stoß ähm dass die sehr lange warten müssen, bis sie dran kommen. Ja, und dieser Prozess hier, der hat äh
  40. letztendlich eine Ankunftszeit von 2, läuft aber erst los zum Zeitpunkt 101. Ja, und wenn man dann die normalisierte Durchlaufzeit anguckt, dann stellt man
  41. fest, dass die sehr sehr hoch ist. Ja, das ist was ähm was man insbesondere bei äh bei so interaktiven Prozessen interaktiven Systemen eigentlich nicht
  42. haben will. Und dann hatten wir uns in der Folge äh das Round Robin Verfahren angeguckt, dass das eben behebt oder versucht zu
  43. beheben, indem es Präion hinzufügt, ne? Also da haben wir eben die Zeitscheiben dazu bekommen, die dafür wo eben mit dem Timerbaustein und Unterbrechungen dafür
  44. gesorgt wird, dass einem Prozess die CPU entzogen wird, wenn er wenn er zu lange rechnet. Da haben wir dann auch festgestellt, die
  45. Prozesse, die viel ein Ausgabe machen, die also regelmäßig vor Ende ihrer Zeitscheibe die CPU abgeben, die werden hier benachteiligt, weil nämlich die
  46. Restzeit in ihrer Zeitscheibe verfällt. Und dann haben wir das Virtual Round Robin Verfahren uns angeschaut, VRR, was das wiederum behebt durch eine
  47. Vorzugsliste, ne? das Prozesse, die also vorzeitig die CPU abgegeben haben, ähm in eine Vorzugsliste kommen, die vor der normalen Bereitliste abgearbeitet wird,
  48. wo die Prozesse den die Restlaufzeit aus ihrer letzten Zeitscheibe äh zunächst mal noch äh fertig oder weiterrechnen können.
  49. Dann hatten wir uns noch ähm Shortest Process Next angeguckt, ähm wo letztendlich der Prozess geschul wird, der die kürzeste CPU Laaufzeit haben
  50. wird. Ja, und das hört man jetzt schon an der an der Beschreibung, äh dass man dadurch, also dafür braucht man letztendlich eine Vorhersage, muss also
  51. irgendwie die Zukunft vorgreifen können, um zu wissen, welcher welcher von den von den rechenbereiten Prozessen derjenige mit der kürzesten CPU, dem
  52. kürzesten CPU Stoß ist. Ähm und das haben wir letztendlich über z.B. über so eine exponentielle Glättung gemacht. Wir hatten noch zwei weitere ähm Verfahren
  53. uns angeguckt. SRTF und HP Response Ratio Next, die letztendlich auch vorhersagebasiert arbeiten. Und last but not least hatten wir uns noch das das
  54. Feedback Scheduling angeguckt, wo also Prozesse ähm hier von oben nach unten wandern, äh wenn sie wenn sie jedes Mal auf jeder Ebene wieder die Zeitscheibe
  55. aufbrauchen. Ja, das also sorgt dafür, dass also Prozesse mit langen CPUstößen immer weiter runter immer weiter runterwandern,
  56. möglicherweise mal durch so eine Anti-Aging Maßnahme wieder nach oben kommen können. Und ähm
  57. da haben wir uns im selben Kontext auch noch mal ganz kurz über Prioritäten unterhalten, ja, unterschieden zwischen statischen und dynamischen Prioritäten.
  58. Ähm bei den dynamischen Prioritäten ähm erfolgt eben die die Aktualisierung von den Prioritäten. ähm vor allem auch im Betriebssystem. Ja, und ähm diese
  59. Verfahren Shortest Process Next, STF, HRN und Feedback waren eben Spezialfälle, die eben äh zur Laufzeit äh die Prioritäten von Prozessen
  60. anpassen. Also bei Feedback z.B. wie eben die Prozesse, die sehr CPU lastig sind, die werden letztendlich kontinuierlich äh weiter in der
  61. Priorität abgesenkt und hatten uns dann am Schluss noch angeschaut Multilevel Scheduling ähm was äh ja das Ganze noch ein bisschen
  62. verallgemein hat. Das ist jetzt zunächst mal Multilevel Schedulings erstmal ein ein Verfahren, wo also jeder Prozess zunächst mal nach seiner nach seiner
  63. Sorte irgendwie äh einfach eine Priorität zugeordnet wird, ne? Also hier oben haben wir z.B. ist die Systemprozesse, die hier die höchste
  64. Priorität bekommen haben, die Studentenprozesse, die die niedrigste haben. Beim normalen Multilevel Scheduling ist zunächst mal kein
  65. Feedback vorgesehen, also spricht, dass ein Prozess seine Priorität wechselt. Ähm ja, das heißt also ein niederpriorer Studentenprozess bleibt auch
  66. niederprior, ein hochpriorer Systemprozess bleibt hochprior. Das kann man aber auch noch kombinieren und dann hat man multilevel Feedback. Ja, und das
  67. ist ein sehr allgemeines Verfahren, wo man letztendlich auch auf jeder Ebene entscheiden kann, nach welchem Scheduling Verfahren wird hier äh
  68. gescheduled und nach bestimmten Kriterien äh können Prozesse dann auch die Ebene wechseln, ne? Z.B. wenn sie sehr CPU lastig sind, weiter nach unten
  69. geschoben werden. Dann hatten wir kurz über äh Bewertungskriterien gesprochen, also welche
  70. Ziele äh bei einem bei einem äh Scheduling äh Verfahren ähm ja durchgesetzt werden sollen. Da haben wir Unterschieden zwischen benutzerentierten
  71. und systemorientierten Zielen oder Bewertungskriterien, die jeweils für völlig unterschiedliche Anwendungszwecke sinnvoll sind.
  72. Ähm, dann hatten wir uns noch ein Beispiel angeschaut, nämlich Unix. Skatering oder Unix. Das ist jetzt nur noch mal ein kleiner Auszug. Ähm, wo wir
  73. also gesehen haben, dass z.B. diese dieses äh diese diese äh diese exponentielle Glättung auch wirklich in der Realität eingesetzt wird. Und das
  74. ist so der Punkt, wo wir das letzte Mal stehene geblieben sind. Ähm, ich mache jetzt mal diesen Foliensatz noch fertig. Da gab es noch ein Beispiel zu Thema
  75. Windows und ähm dann gucken wir mal, ob es zum zu diesem Vorhinsatz noch Fragen gibt. Ähm
  76. ja, dazu sollte ich mir vielleicht auch mal die Frag jetzt Seite aufmachen nebenan Fragen auch bei mir ankommen. Da sind schon ein paar eingegangen. Ich äh
  77. gehe gleich drauf ein. Ja, Windows äh Art macht natürlich auch Scheduling. Ja, seit Windows int ähm gibt's Prioritätsklassen
  78. und ähm da werden letztendlich wird auch letztendlich Präumtion benutzt. Ja, also präumtive
  79. äh Prioritäts und zeitscheibenbasierte Einplanung passiert da. Ähm und Verdrängung, also Präion passiert auch dann, wenn es ein Thread ist, der im
  80. Kern ist. Ja, also selbst ein Betriebssystem eigener Thread, der wirklich Betriebssystem interne Dinge tut, kann
  81. verdrängt werden. Ja, bei Unix ist das klassischerweise nicht der Fall gewesen. Ähm, prioritätsbasiert, ja, das heiß, wir
  82. haben Prioritätsebenen, in dem Fall von 0 bis 31 und wenn wenn man zwei Prozesse oder zwei Threats hat, die auf derselben
  83. Prioritätsebene sind, dann wird Round Robin gemacht. Ja, die waren also rei um äh dran genommen und haben eine Zeitscheibe
  84. und ähm da gibt's jetzt eendlich verschiedene Prioritätsklassen. Ja, die Klasse Null ist reserviert für ein so so eine Hintergrund Aufgabe, die Wus
  85. regelmäßig durchführen muss. Ähm von 1 bis 5, das sind die sogenannten Variablen Prioritäten und von 16 bis 31 sind die sogenannten
  86. Echtzeitprioritäten. Ähm, so und dann gibt es bei Windows eben so
  87. äh ja, Eigenschaften, die sich sehr stark auf die Desktop Betriebssystem Natur von Windows beziehen. Ja, also z.B. die Art eines Threads ähm bestimmt,
  88. wie groß das Zeitquantum, also die Zeitscheibe äh eines Threads ist. Ja, also ob es ein Vordergrundthreat ist oder ein Hintergrundthread. Ja, also ist
  89. das ein tatsächlich ist es ein Fenster, das im Vordergrund ist oder ist das ein Fenster äh das im Hintergrund ist? Ja, und äh so eine Zeitscheibe, die kann
  90. zwischen 6 und 36 Einheiten groß sein und eine Einheit äh entspricht, ne, so einem Tick und so ein so so ein Tick kann je nachdem welche Version das von
  91. dem von Windows NT ist, kann z. 10 oder 15 Millisekunden z.B. sein. Ähm und ähm dieses Quantum, das verringert sich mit jedem Tick um 3 oder um eins. Ja, und
  92. das kommt jetzt wieder drauf an, wie sich dieser Thread in letzter Zeit verhalten hat. Ähm, wenn also nein, Moment, um 3 in der Regel und nur um
  93. eins, wenn der Thread äh ein IO Burst macht, also in den Wartezustand geht und die Zeitscheibenlänge, die sich die da daraus letztendlich resultiert, die
  94. kann jetzt variieren zwischen 20 Millisekunden, das war so ein Beispiel, dass ich das letzte Mal gebracht hatte, bis zu 180 Millisekunden. Ja, und das
  95. unterscheidet sich z.B. bei Server und Desktopversionen von Windows. Ja. Ähm was jetzt noch dazu kommt und das ist letztendlich so eine Heuristik, die
  96. die sich äh die sich die Firma Microsoft hier ausgedacht hat, ist ähm also zunächst mal sowas die die Basispriorität von einem Prozess, ja,
  97. also die die der Prozess so als Hülle für mehrere Theds, der hat erstmal eine Basispriorität, dann kann ein Thed innerhalb dieses Prozesses noch eine
  98. relative Priorität haben, plus minus irgendwie irgendeine Konstante und dann kommt noch ein sogenannter Boost dazu. Ja, der Boost
  99. ähm der kommt zum kommt zum Zuge, wenn man auf irgendeine Art und Weise mit dem Prozess z.B. interagiert. Ja, wenn bestimmte Ereignisse ähm auftreten, dann
  100. bekommt so ein Prozess kurzzeitig oder so ein Thread kurzzeitig eine höhere Priorität. Z.B. wenn ein Prozess eine Festplatte von äh eine Festplatten eine
  101. Ausgabe irgendwie fertig gestellt hat, also der hat eine ein aus ein Ibst gestartet, der ist fertig geworden. Ähm und es wird ein Block von der Festplatte
  102. geliefert, z.B. Ja, da wird der Prozess kurzzeitig in der Priorität angehoben. Ähm, noch viel witziger ist sowas wie die Mausbewegung oder Tastaturingaben.
  103. Ja, wenn Sie auf so ein Fenster drauf klicken unter Windows, dann wird die Priorität von dem von dem äh von dem Thread, der dahinter steckt, kurzzeitig
  104. um 6 angehoben. Ja, das heißt, also wenn Sie irgendwann mal ganz äh ganz dringend auf das Fertigstellen von irgendeiner
  105. rechtintensiven Arbeit von ihrem auf ihrem Windows Rechner gewartet haben und sie haben so nervös auf dem auf dem Fenster rum geklickt und das Gefühl
  106. gehabt, der wird jetzt schneller fertig, dann hatten sie vielleicht gar nicht so unrecht mit dem Gefühl. [räuspern] Ja, also Prozess wird tatsächlich dynamisch
  107. angehoben, wenn äh wenn er Eingaben vom Nutzer bekommt. Ja, und es gibt noch weitere Ereignisse, die die das die das also verursachen
  108. können, dass man so ein so einen Boost bekommt und dieser Boost, den man da also bekommt, also z. dieses + 6, das wird jetzt mit jedem Tick wieder
  109. reduziert. Ja, das heißt also z.B. nach sechs Ticks ist dann dieses dieser Boost, den man durch die Mausbewegung oder die Tastatureingabe bekommen hat,
  110. wieder weg. Und eine weitere Sache ähm macht Windows noch beim beim Scheduling, nämlich es liefert eine sogenannte
  111. Fortschrittsgarantie, ähm die also dafür sorgt, dass Threads nicht aushungern. Ja, also alle drei bis 4 Sekunden werden irgendwie bis zu zehn in letzter Zeit
  112. benachteiligte äh Threats für zwei Zeitscheiben noch ordentlich angehoben ähm auf die höchste variable Priorität, ja, aus diesen variablen Prioritäens
  113. Spektrum. Und ähm das führt dazu, dass äh das letztendlich das Aushungern verhindert wird.
  114. Ja, und man sieht bei Windows ähm da wurde letztendlich wahrscheinlich auch eine Menge äh Forschung betrieben mit Nutzern, die also beobachtet wurden,
  115. wie sich wie wie sie letztendlich auf das Systemverhalten so ansprechen und entsprechend wurde ähm wurde dieses Scheduling, diese Scheduling Horistik
  116. hier so angepasst, dass sich das System eben ein bisschen interaktiver anfühlt. zusammenfassend zum Thema Scheduling. Ja, also wir hatten diese drei diese
  117. drei äh ähm na ab diese drei Einplanungsebenen gesehen, also langfristig, mittelfristig, kurzfristig
  118. und die betrachteten Verfahren jetzt aus dieser Vorlesung, ja, also FCFS und Co, äh die gehören alle zum Shortterm Scheduling. Ja, wir haben verschiedene
  119. Benutzer und systemorientierte Kriterien gesehen, wie man diese Verfahren beurteilen kann und welches Verfahren letztendlich das Beste ist für ihren
  120. Anwendungsfall, für ihren Rechner, der möglicherweise irgendwie in eingebetteten System äh sitzt und irgendwie mit z.B. mit der mit der
  121. physikalischen Umgebung irgendwie interagieren muss. Ähm, das kommt letztendlich darauf an, was der Uscase genau ist. Ja, und das kann sich sehr
  122. stark dann unterscheiden, wie die wie die Leistung unterm Strich dann ist. So, jetzt schauen wir mal, ob es Fragen gibt.
  123. Ähm, wenn die Prozesse dem Scheduler mitteilen, wie lange ihre Bedienzeit sein soll, warum müssen wir noch die
  124. voraussichtliche Laufzeit vorhersagen? Der Prozess sagt uns ja schon, wie lange er laufen will bei einigen Scheduling Methoden. Also, das Prozesse dem
  125. Scheduler sagen, wie lange sie laufen wollen, das ist nicht der Regelfall. Ich wüsste jetzt da so für dafür noch nicht mal ein Beispiel.
  126. Ähm, das einzige Beispiel, wo wir eben nicht vorhersagen müssen, z.B. durch dieses äh durch diese
  127. exponentielle Glättung, ähm das ist eben im Bereich ähm ja Batchge Batchge Computing, also letztendlich so, ne, wenn man hier in dem Lido Cluster
  128. rechnen möchte, dann muss man bei seinem Rechenjob dazu sagen, wie lange der ungefähr laufen wird, ne? Läuft der 10 Minuten, läuft der eine Stunde, läuft
  129. der ein Tag? Das muss man muss man da ankündigen. Und nachdem dieses Zeitfenster dann abgelaufen ist, wird der Prozess auch wirklich weggeschossen
  130. von dem System. Ja, das ist aber, würde ich jetzt mal sagen, nicht der Regelfall. Im Regelfall ähm muss letztendlich der Scheduler eine
  131. Vorhersage treffen. Ja, man sieht es ein Prozess von außen erstmal so ohne weiteres nicht an wie die sich verhält, sondern man muss ihn halt beobachten und
  132. aus den Beobachtungen, aus den letzten Endbeobachtungen die nächste ähm Zeitscheibenlänge oder ne die letzte nächste CPU Burst Länge vorhersagen.
  133. Ich hoffe, das beantwortet diese Frage. Ähm, was bedeutet Variabel und Echtzeit bei den Prioritäten? Das sind zunächst mal nur Namen für die beiden Klassen.
  134. Ähm, na, nicht ganz beim Echtzeitscheduling äh die Echtzeit, diese Echtzeitklasse, also
  135. wir reden gerade noch mal von Windows NT von diesen von diesen Prioritäten von 0 bis 31 und bei den Klassen äh bei den Prioritäten 1 bis 15, bei diesen
  136. variablen Prioritäten, da wird Drown Robin gemacht. Ja, also da wird gibt's letztendlich einfach Zeitscheiben. Ähm bei den höheren Prioritäten, also bei
  137. den Echtzeitprioritäten ab 16 ähm laufen diese äh diese diese Threads, also wird wird keine Präsion gemacht, soweit ich mich düster erinnere. Das
  138. müsste ich vielleicht noch mal nachgucken, aber ich meine, dass das letztendlich FCFS entspricht. Ja, das heißt also, wenn da ein äh ein ein äh
  139. ein Thread seine die CPU nicht hergibt, dann kann er keine wirklich das System lahm legen. Das meine ich war der Unterschied. Gucke ich aber noch mal
  140. nach. Gibt es da denn jetzt ein besser oder schlechter, was das Scheduling in Unix
  141. und Windows angeht? ähm bestimmt. Also letztendlich ähm kommt es auf ihren
  142. Anwendungsfall an. Ja, also ich denke, dass Microsoft da schon sehr viel Zeit investiert hat, um dieses diese Geschichte z.B. mit diesem Dynamic
  143. Dynamic Boost ähm so lange zu optimieren, bis sich das eben für den Normalnutzer besonders fluffig anfühlt.
  144. Ähm ich kann mir aber sehr gut vorstellen, dass es auch Anwendungsfälle gibt, wo das eben nicht der Fall ist. Ja, also wo möglicherweise dann einfach
  145. so ein Unix, Linux, sonst wie Scheduler, ähm einfach bezüglich eines anderen äh Benutzer oder auch systemorientierten Kriteriums ja einfach besser aussieht.
  146. Ja, also wie wie so oft muss man hier sagen, kommt drauf an, was ihr Anwendungsfall ist.
  147. Woher weiß man eigentlich bei dem Lido System, also bei dem Klaster, wie lange das Programm läuft? kommt ja auch auf die Systemleistung, also
  148. Prozessorgeschwindigkeit, die Anzahl der Kerne und so weiter an. Ähm, na ja, letztendlich ist das eine Schätzung, die der Nutzer hier ähm hier
  149. angibt. Der schätzt der schätzt natürlich äh großzügig nach oben ab und ähm er weiß auch, wie die Maschinen beschaffen sind, auf den er arbeitet.
  150. Also in diesem Lidluster, da gibt es sehr, sehr viele gleichage Maschinen und da kann auch einfach mal ausprobieren und messen. Ja, aber letztendlich kann
  151. es natürlich immer passieren, dass man da einen Rechenjob laufen lassen möchte, der doch länger dauert, als man geschätzt hat. Ja, weil es sich die
  152. Laufzeit von so einem Prozess natürlich nicht nur darauf ankommt, wie schnell der Prozessor ist, äh wie sondern auch wie z.B. die Eingabedaten sind. Ja, je
  153. nachdem, wie die Eingabedaten sind, kann so ein Programm völlig unterschiedliche Laufzeiten haben. Ähm und dann hat man möglicherweise Pech gehabt. Ja, also im
  154. schlimmsten Fall muss man halt das diesen diesen Job noch mal starten mit einer höheren Schätzung. Ja, aber das ist natürlich ein Problem.
  155. Ja, wenn man überabschätzt, äh ja, überabschätzen ist mal die sicherere Sache, da wird der Prozess nicht
  156. vorzeitig weggeschossen. Hat aber den Nachteil, dass in der in der Regel langlaufende oder Prozesse, bei denen der Nutzer ankündigt, dass die
  157. langelaufen werden, äh dass die mit niederer niedriger Priorität geschulted werden. Ja, das heißt, also wenn man also einen Job in das System reinsteckt,
  158. wo man sagt, der läuft vier Tage durchgehend, ähm dann kann es sein, dass man auch durchaus mal ein z D Tage warten muss,
  159. bis der überhaupt losläuft. Ja, und wenn man Job ins System schiebt, wo man sagt, der wo man ankündigt, der läuft nur 10 Minuten, der kommt in der
  160. Regel sofort dran. Ja, also das ist ein Üste ist tatsächlich ein Problem. Letztendlich kann man nur messen und hoffen.
  161. Der Ton ist doppelt. Das ist natürlich in der Tat schlecht, wenn sie das ein bisschen Moment, jetzt schau ich mal, ob ich hier
  162. irgendeinen Unsinn gemacht habe mit meinem Ja, ich verstehe jetzt auch, was das Problem ist.
  163. So, jetzt hoffe ich mal, der Ton ist besser geworden. Schauen mal, ob der Turm besser geworden ist. Bei mir ist alles okay. Eigentlich
  164. nicht. Hier ist auch alles okay, nicht? Also ich ich spreche jetzt einfach mal bisschen weiter. Sie können ja mal kommentieren, ob der Ton sich auf
  165. irgendeine Art und Weise verändert hat. Ton ist jetzt okay. Okay, der Ton war vorher auch schon okay. Na gut, wir üben das noch.
  166. Ähm ja, so viel zum Thema Scheduling. Ähm heute machen wir weiter mit ähm ja letztendlich dem, was darauf
  167. folgt. Ja, wenn ich ähm ja, wenn ich wenn ich äh System mit mehreren konkurrenten Prozessen habe, dann kann es auch sein, dass ich die
  168. synchronisieren muss. Deswegen ist das Thema der heutigen Vorlesung Synchronisation.
  169. Ähm, was möchte ich mit ihm besprechen? Noch mal ganz kurz wiederholen. Da wollen wir schnell drüber springen. Ähm, dann werde ich versuchen erstmal das
  170. Problem noch ein bisschen klarer zu machen, ja, ein paar Begriffe ähm auf den Tisch legen. Ähm, und dann werden wir uns über verschiedene Lösungsansätze
  171. unterhalten, ähm wie man synchronisieren kann. Ja, also zunächst mal quasi die Athoklösung. Ja, wie würde man da jetzt rangehen, wenn man nicht Betriebssysteme
  172. gehört hat? Vielleicht was ist der Nachteil davon, wenn man das so tut. Ähm, dann w wir uns über Hardwareunterstützung zur
  173. Synchronisation unterhalten. Es ist wieder leise geworden. Weiß ich doch. Be Absicht. Ich mach's noch mal lauter. So.
  174. Ähm, Betriebssystem Unterstützung ähm für Synchronisation unterhalten und am Schluss über Sprachunterstützung. Ähm, ja, Prozesse sind Programme in
  175. Ausführung. Ja, also die Abstraktion für Kontrollflüsse äh in Rechnensystemen und zunächst mal sind die konzeptionell unabhängig voneinander. Ja, also
  176. konzeptionell sind es wirklich komplett nebenläufige Kontrollflüsse äh die so aus aus Nutzersicht auch wirklich gleichzeitig laufen, was sie natürlich
  177. technisch nicht machen. Ja, technisch findet ein Multiplexing der CPU statt. Es darf immer nur einer tatsächlich auf der CPU laufen und ähm das der
  178. Schedeling Verfahren entscheidet also wann wird ein Prozess verdrängt und ähm in welcher Reihenfolge kommen die die lauffähigen Prozesse dran. Ja, in
  179. welcher Reihenfolge werden die ausgeführt? Prozesse haben einen Adressraum. Ja, über logische und physische Adressen werden wir uns später
  180. noch unterhalten. Logische Adressen werden durch die Hardware let durch die durch die Memory Management Unit auf physische Speicheradressen abgebildet.
  181. Und ähm Prozesse können sich auch und das ist jetzt ein Problem, dass wir uns gleich mit dessen Folgen wir uns gleich anschauen werden, können sich auch Code
  182. und vor allem Datenbereiche teilen. Ja, also bei leicht und viertergewichtigen Prozessen hatten wir schon gesehen, die teilen sich denselben Adressraum, die
  183. können auf denselben Datenstrukturen arbeiten. Ähm und das Betriebssystem kann mit Hilfe der MMU, ja, das ist wieder auf
  184. der technischen Ebene, ähm einen Speicherbereich mehrere Adressräume einblenden. Ja, was dafür sorgt, dass wirklich zwei auch Prozesse, auch zwei
  185. schwägewichtige Prozesse ähm auf demselben Speicher, auf den selben Datenstrukturen arbeiten können. Ja, und auch im Betriebssystem selbst werden
  186. Daten, Strukturen, Daten geteilt. Ja, das gucken wir uns auch später noch mal an. Ähm, ja, was ist das Problem? Jetzt
  187. gucken wir uns mal eine einfache Datenstruktur an, die vielleicht im C auf den ersten Blick nicht so einfach aussieht für diejenigen, für die C neu
  188. ist. Ähm ist aber keine Raketenwissenschaft. Ich werde es mal kurz versuchen zu erklären. Ähm wir wollen eine verkettete Liste in C
  189. implementieren. Ja, also haben wir ein Struct element, wo also das das letztendlich die die Datastruktur für ein einzelnes Element
  190. in dieser Dataststruktur ist. Jedes Element hat eine Payload. Ja, in diesem Fall jetzt einfach ein Character, das könnte aber auch irgendwas komplexeres
  191. sein. Ja, es ist die Nutzlast, also das, was wir in dieser in dieser verketteten Liste verwalten wollen. Zeichen. So, und jedes Element hat, wie das halt
  192. so ist bei einer verketteten Liste, einen Nextzeiger auf das nächste Element ähm in unserer Liste. So, die eigentliche Liste ähm besteht
  193. letztendlich aus zwei Zeigern. Das eine ist ein, ne, wenn man liest ja immer von rechts nach links, ne? Head ist ein Zeiger auf ein Structement.
  194. Das ist also der Zeiger auf das erste Element in der Liste. Und dann wird hier so ein kleiner Kniff ähm gewählt. Also der dieser Tail
  195. Zeiger, das ist kein Zeiger auf das letzte Element, sondern das ist der Zeiger auf das auf den Nextiger im letzten Element. Ja, also Tail zeigt auf
  196. den Nextiger im letzten Element. So, warum das so ist, werden wir gleich an dem Beispiel bisschen sehen. Letztendlich sorgt dieser Kniff dafür,
  197. dass man bei diesen bei dieser bei diesem Einhängeschritt hier unten, der hier unten implementiert ist, äh dass man hier nicht unterscheiden muss, ist
  198. die Liste gerade leer oder ist sie nicht leer. Ja, wenn das hier einfach nur ein Zeiger auf das letzte Listenelement wäre, dann wäre diese Implementierung da
  199. unten ein bisschen komplexer. ist jetzt vielleicht äh für das eigentliche zu zeigende Problem
  200. gar nicht so relevant. Ähm, letztendlich ist aber das die Implementierung, die ich jetzt in diesem Beispiel hier zeigen werde.
  201. Ähm, so, das ist die also die Implementierung von der Funktion oder man könnte jetzt sagen, wenn man so objektorientiert das Ganze betrachtet,
  202. das ist die Methode NQ auf der Datenstruktur Liste. Ja, also die hängt ein neues, die hängt also hier in die in die Liste List ein neues
  203. Element Item ein. Ja, und dazu werden diese drei Schritte hier durchgeführt. Das gucken wir uns jetzt gleich mal in dem Beispiel an.
  204. Ähm, zuvor das vollständige Szenario. Wir haben zwei Fres, Faden 1, Faden 2, die laufen zum Nebenläufig vor sich hin und beide machen irgendwann mal in ihrer
  205. Laufzeit mal ein NQ auf dieselbe Liste. Ja, und da werden wir jetzt gleich sehen, dass ein Problem auftreten wird möglicherweise oder zumindest auftreten
  206. kann. Ja, also F 1 macht irgendwann mal ein NQ auf diese Liste hier von dem Element 1. Das ist dieses Ding hier unten links. Also letztendlich Thed 1
  207. möchte ein A in die Liste einhängen. Th 2 möchte ein B in die Liste einhängen. Okay. Und diese be diese Liste und auch diese
  208. ganzen Listenelementobjekte äh die liegen alle im in dem gemeinsamen Adressraum. Was man jetzt hier sieht, ist die leere
  209. Liste. Ja, und zwar ist das hier der Headpointer. Ja, wenn die wenn die Liste leer ist, zeigt der Headpointer auf einfach auf null, also auf nichts.
  210. Und der Tail Pointer zeigt auf das den eigenen Headpointer. Ja, das ist einfach der definierte Zustand für die leere Liste. Ja, das ist
  211. das, was ein Listenkonstruktor in der an der Stelle ähm so einrichten würde, dass die Liste so momentan inzahl so aussieht. Und diese beiden
  212. Elementobjekte hier ähm die haben hier schon mal in dem in diese diesen Payload jeweils ein ein Zeichen eingetragen bekommen und ihr jeweiligen Nextiger,
  213. der zeigt noch auf irgendwas. Ja, das ist erstmal nicht initialisiert. So, und jetzt gucken wir uns mal an, was passiert, wenn zunächst mal Faden 1 ein
  214. NQ macht auf das E1 und danach Faden 2 ein NQ auf das E2. Ja, und das sind jetzt einfach diese drei Schritte aus der NQ Funktion, die
  215. wir uns jetzt nacheinander angucken. Das ist also die Initial, der Initialzustand von unserer Liste L und das sind die beiden Elemente E1 und E2. So, jetzt
  216. wird zunächst mal dafür gesorgt, dass der Next Pointer von unserem Item, das ist in dem Fall hier das Element E1, ja, also das ist der Nextzeiger, der
  217. momentan noch nicht initialisiert ist, dass der mit Nalle initialisiert wird. Ja, das Ding wird jetzt mit Nalle initialisiert. Das tut diese Zuweisung
  218. hier. So, es gab eine Zwischenfrage, die wurde gleich wieder gelöscht. Ich vermute mal, ich habe es ja einfach
  219. mal schon beantwortet. Ähm, so was passiert jetzt hier in diesem zweiten Schritt? Also, hier wird
  220. zunächst mal die Liste genommen. Ja, das ist also dieses Objekt hier. Von dieser Liste wird das Tail Element, das ist das hier, das dieser Zeiger hier
  221. genommen. Und das Ganze wird dereferenziert. Ja, das heißt also das Dereferenzieren sorgt dafür, wir folgen dem Pointer dorthin, wo er hinzeigt. Ja,
  222. dorthin und dort wird Item zugewiesen. Das sorgt also dafür, dass dieser Zeiger jetzt ja, das ist also hier die erm noch mal ein Z
  223. ein dasselbe dasselbe, dass dieser Zeiger jetzt auf unser Item E1 zeigen soll. Ja, diese Zuweisung sorgt dafür, dass dieser Zeiger aufs nächste zeigt.
  224. So und im dritten Schritt wird wird noch mal hier das [räuspern] Listenelement die Liste genommen. Davon das der Tail Zeiger der hier und der
  225. soll jetzt [räuspern] zeigen auf den Next Zeiger von unserem Item. Ja, also der wird jetzt umgebogen von hier nach da.
  226. So und jetzt ist dieses erste NQ fertig. Und was wir jetzt hier sehen, ist also eine Liste, die ein Element beinhaltet. Ja, der Headpointer von der Liste zeigt
  227. auf das erste Element. Der Tailpointer zeigt auf den Next Pointer von dem letzten Element in unserer Liste, was gleichzeitig auch das
  228. erste Element ist. So, und jetzt kommt hier das äh das zweite NQ. Ja, das habe ich jetzt hier
  229. nicht noch durchanimiert. Letztendlich sorgt es dafür, dass der Headpointer nach wie vor auf das erste Element zeigt. Der Next Pointer zeigt auf das
  230. nächste und der Tail Pointer zeigt auf dem Nextinter vom letzten Element. Ja, so soll die Liste aussehen, wenn nacheinander E1 und dann E2 in die Liste
  231. enced wurden. So, das ist auch völlig richtig. So, so muss das aussehen, wenn das äh wenn das wenn das
  232. wenn die beiden fertig encute sind. Jetzt ist aber die Frage, was passiert, wenn diese beiden Threads ja ungünstig äh umgeschaltet werden? Ja,
  233. also wir hatten ja wir hatten ja gehört, das ist immer es kann immer nur ein Thread auf der CPU laufen und jetzt nehmen an, wir haben so
  234. irgendein PR prämitives Scheduling Verfahren, Robin z.B. und das sorgt dafür, dass an dieser Stelle hier ein Prozesswechsel stattfindet. Ja, also
  235. wird gesagt, die Zeitscheibe von diesem von dem Thread 1 ist jetzt abgelaufen. Jetzt darf Thread 2 mal dran kommen. Und jetzt macht dummerweise Thread 2 auch
  236. ein NQ. Ja, also wir haben jetzt den Fall Faden 1, Faden 2, überlapp Faden 1. Ja, also Faden 1 läuft aber nur bis hierhin, dann wird findet ein
  237. Prozesswechsel statt. Faden 2 macht hier sein NQue und dann findet wieder ein Prozesswechsel irgendwann statt. Wieder zurück zu Faden 1. Und jetzt gucken wir
  238. mal, was mit unserer Liste passiert. Also auch hier wird wieder erstmal dieser Nextiger. Moment, doch, nee, E1 wird eingehängt. Also der Nextiger hier
  239. wird auf Nah gesetzt. Ja, und der ähm na also List Tail zeigt hierhin und das wird gesetzt auf Item. Also es wird
  240. letztendlich dieser Zeiger hier ein eingefügt. Ist aber noch nicht ganz fertig, ne? Also um um das NQ komplett fertig zu machen, müsste man ja
  241. eigentlich diesen Schritt noch machen, der dafür sorgt, dass dieser Zeiger hier auf den Nextiger von E1 zeigt. Ja, und das äh fehlt noch. Wird jetzt
  242. halt vorzeitig unterbrochen. Ja, es kommt also passiert also Kontextwechsel zum Faden 2. Und was passiert jetzt? Ja, das ist also zunächst mal die Situation
  243. von oben kopiert. Was wird jetzt gemacht? Das wird also das Item den das Item ist in dem Fall das E2 wird hier also der dieser Nallzeiger erstmal
  244. eingetragen. Das ist noch völlig unkritisch, weil dieses Element, das sieht ja noch kein anderer Prozess oder kein anderer Th der der daneben daneben
  245. läuft. Was passiert jetzt? Ja, es wird wieder List Tail genommen, ne? List Tail ist dieser Zeiger hier. Den wird mit dem Sternchenoperator
  246. wird das wird dieser Zeiger dereferziert. Wir folgen also dem Zeiger dorthin, wo er hinzeigt. Und das wird gesetzt auf Item. Das heißt
  247. also dieser Zeiger hier wird übermalt durch einen Zeiger, der auch dieses Item hier zeigt. Und dann wird list tail, das ist dieser
  248. Zeiger hier wird gesetzt auf den Next Zeiger von dem Element 2. Ja, jetzt sind wir hier und wir sehen also das Zwischenergebnis
  249. ist jetzt momentan schon mal das, was der Fed 1 gemacht hat, wurde rückgängig gemacht. Ja, also momentan haben wir eine gültige Liste, aber in dieser Liste
  250. ist nur Element 2 eingehängt. Element 1 ist nicht mehr eingehängt. So, jetzt passiert wieder Prozesswechsel. Wir wechseln also zurück
  251. zu Thread 1. Und jetzt macht er natürlich hier noch seinen letzten Schritt. Ja, wenn er seinen letzten Schritt hier macht, dann wird ne nimmt
  252. nimmt er hier List Tail, das ist dieser Zeiger oder dieser Zeiger hier und der wird gesetzt auf in dem Fall wieder E1. Next. Heiß der Ted Zeiger zeig jetzt
  253. hier drauf. Ja. Und jetzt haben wir eine Listenatenstruktur, die völlig kaputt ist. Ja, also das ist keine gültige
  254. Liste mehr. Ja, die Liste ist so, wenn wir jetzt auf dieser Liste irgendwie weiterarbeiten, ähm dann werden wir je nachdem, was wir
  255. mit dieser Liste machen, ähm ja, einzelne Elemente nicht mehr drin sehen. Die sind da halt nicht mehr drin. Ja, also z.B. eine Operation, die versucht
  256. die Liste einfach komplett auszugeben. Die würde diesem Headpointer z.B. folgen, bis es hier bis es irgendwie in der Kette Nullpointer findet und dann
  257. bei diesem drüber iterieren würde dieses Element A hier nie auftauchen. Ja, und alle weiteren Elemente, die angehängt werden, die werden hier immer an den
  258. Tailpointer angehängt. Ja, die hängen also dann alle letztendlich direkt oder indirekt an diesen Zeiger hier dran und ähm
  259. die gehen verloren. Ja, also die sehen wir nicht mehr, wenn wir über die Liste eterieren. Ja, also kaputte Datenstruktur irgendwie schlecht.
  260. Ähm ja, was vielleicht noch dazu zu sagen ist, also das ist was jetzt hier irgendwie so aussieht, das wäre es ein Problem von C. Ähm ist es aber nicht.
  261. Ja, also das kann in Java passieren, das kann in jeder anderen Programmierprache passieren, wo sich nebenläufige Prozesse Datenstrukturen teilen können. Ja, das
  262. ist ein allgemeines Problem. Ja, wo gibt's das sonst noch? Ja, also gemeinsamer Speicher, also Shared Memory
  263. ähm z.B. Ne, da könnt da können wirklich schwergewichtige Prozesse sich Speicher teilen. Da kann man den selben Speicher
  264. in in zwei schwergewichtige Prozesse einblenden und dort drin gemeinsame Datenstrukturen ablegen. Ja, das Beispiel, das wir jetzt gerade
  265. gesehen haben, das würde jetzt am ehesten noch so einem leichtgewichtigen Prozess, also einem Thread entsprechen, ja, wo letztendlich einfach nebenläufig
  266. auf Variablen, auf dieselben Variablen zugegriffen wird. Ähm, im Betriebssystem selbst kann das passieren, ja, Betriebssystematen äh die
  267. gebraucht werden, um den Zugriff von Prozessen auf unteilbare Betriebsmittel zu koordinieren. Also um z.B. ähm Operation auf äh Dateisystemstrukturen
  268. zu machen. Ja, das Dateisystem ist eine geteilte Ressource, die letztendlich alle Prozesse sich teilen. Ja, Operation auf der Prozessstabelle,
  269. Speicherverwaltung, ja, oder auch das Nutzen von Geräten. Ja, also wenn ein Drucker z.B. nur exklusiv benutzt werden darf von einem Prozess, dann muss man
  270. den Zugriff darauf irgendwie koordinieren. Ja. Ähm, kleiner Vorg auf eine Masterveranstaltung, Betriebssystembau, ja, da kommt kommt
  271. man letztendlich auch auf ein ähnliches Problem, nämlich das der Unterbrechungssynchronisation. Ähm, wenn also eine Unterbrechung
  272. auftritt, dann kann das kann natürlich auch diese Unterbrechungsbehandlung auf Datenstrukturen arbeiten, äh auf den andere äh Kontrollfüße auch gerade
  273. arbeiten. Ja, wobei die Verfahren, die wir jetzt jetzt angucken, nicht notwendigerweise auch bei Unterbrechungen funktionieren. Ja, das
  274. nur so als Randnotiz. Ja, was sehen wir hier eigentlich? Das ist eine sogenannte Race Condition, ja,
  275. oder die halbgare Übersetzung Wettlaufsituation. Ja. Ähm, was ist eine Race condition? Das ist
  276. das ist noch nicht der Fall, wo wirklich ein Problem auftritt. Also eine Race Condition ist einfach nur eine Situation, wo mehrere Prozesse
  277. konkurrierend auf dieselben Daten zugreifen. Ja, und mindestens einer dieser dieser Prozesse manipuliert diese Daten auch.
  278. ähm und welchen Wert diese gemeinsamen Daten letztendlich haben, das kommt das das kommt bei einer Racing Condition darauf an, in welcher Reihenfolge die
  279. Prozesse zugreifen. Ja, welches Ergebnis letztendlich dabei rauskommt, ist im allgemeinen erstmal nicht vorhersagbar und kann, wie wir
  280. jetzt in dem Beispiel gerade gesehen haben, kann aber muss nicht, kann ähm bei überlappenden Zugriffen sogar inkorrekt sein. Ja, also in dem Beispiel
  281. von dieser Liste, da hatten wir ja letztendlich zwei Fälle jetzt betrachtet, ja, zwei Abläufe und in dem einen Ablauf ähm gab's gar keine
  282. Überlappung und letztendlich war das Ergebnis am Schluss korrekt. Ja, dem anderen Ablauf gab es eine Überlappung und die hat in dem Fall tatsächlich
  283. dafür gesorgt, dass die Datenstruktur ähm ja defekt war hinterher. So. Und was kann man tun, um Race Conditions zu vermeiden?
  284. Man muss synchronisieren. Ja, die konkurrentenprozesse müssen synchronisiert werden. So, was heißt synchronisieren?
  285. Synchronisation ist die Koordination der Kooperation und Konkurrenz zwischen Prozessen. Ja, das ist also die Definition aus äh aus so einem
  286. klassischen äh Nebenläufigkeitsbuch. Ja, Hertwig Hommel. Ähm, Synchronisation bringt die Aktivitäten
  287. verschiedener nebenläufiger Prozesse in eine Reihenfolge. Ja. Ähm, man sorgt also dafür, dass obwohl
  288. diese Prozesse konkurrierend nebenläufig auf diesen Datenstrukturen arbeiten wollen, sorgt man dafür, dass dass diese Operationen in eine definierte
  289. Reihenfolge gebracht werden. Und durch diese Synchronisation sorgt man also prozessübergreifend dafür, was innerhalb eines Prozesses einfach
  290. dadurch erledigt wird, äh dass bestimmte Datenstrukturzugriffe im weiteren Sinne Aktivitäten ohnehin sequenziell sind. Ja, also wenn man innerhalb eines eines
  291. Prozesses ist, dann hat man einfach eine Operation auf einer Datstruktur. NQ von Element 1 und danach NQ von Element 2. Ja, das ist einfach das ist sequentiell,
  292. da können keine Race conditions auftreten. Wenn man das aber Prozess übergreifend haben möchte, muss man synchronisieren.
  293. So, und jetzt kommt noch ein Begriff, der ein bisschen vorgreift. werden wir gleich sehen, was das konkret heißt, nämlich der des kritischen Abschnitts.
  294. Ähm bei Race Conditions streiten sich n Prozesse. Ja, also in unserem Beispiel waren es jetzt zwei, aber es können natürlich auch beliebig viele mehr sein,
  295. um den Zugriff auf gemeinsame Daten. Und ähm dieser Zugriff, der passiert durch der Regel nicht besonders lange Codefragmente, Codeabschnitte. Ja, also
  296. in dem in unserem Fall waren das ein paar wenige Zeilen in dieser NQ Funktion, ja, die letztendlich wirklich auf die
  297. Datenstruktur zugegriffen haben und deren Zugriffe dafür gesorgt haben, dass eine Race Condition auftritt und diese Codefragmente nennt man
  298. kritische Abschnitte. Ja, und was man letztendlich die Synchronisation sicherstellen möchte, ist, dass sich immer nur ein Prozess von
  299. unseren Prozessen, die sich hier streiten, äh in seinem kritischen Abschnitt oder in einem kritischen Abschnitt aufhält oder und aufhalten
  300. kann. Ja, man muss das erzwingen. So, und jetzt gucken wir uns mal an, wie geht das eigentlich?
  301. Ja. Ähm Lösungsansatz ist äh mit die ist ist das Einführen einer sogenannten Schlossvariablen.
  302. Ja, Schlossvariable hier Datentyp Log. Das ist einfach zunächst mal ein abstrakter Datentyp. Ja, da legen wir also hier auch eine Instanz davon an.
  303. Und dieser abstrakte Datentyp, der hat zwei Operationen, Acquire und Release. Ja, wie die letztendlich heißen, ist ist jetzt nicht so wichtig, aber
  304. letztendlich dieses dieses Aquired, das verschließt ein Schloss und das Release äh öffnet das Schloss wieder. Dieses Aquire hat noch eine zusätzliche
  305. Eigenschaft, nämlich, dass es den Prozess, der dieses Aquir aufruft, so lange verzögert, bis dieses bis das zugehörige Schloss frei ist. Ja, und
  306. wenn das Schloss frei ist, dann wird das Schloss von innen verschlossen. Ja, dann sind wir also in unserem kritischen Abschnitt und am Ende von dem kritischen
  307. Abschnitt wird dieses Schloss wieder freigegeben, ja, oder geöffnet, ohne dass irgendjemand weiterhin verzögert wird.
  308. wie dieses diese abstrakte Datentyp letztendlich implementiert ist. Ja, wie man wie man das tatsächlich umsetzt. Ähm das gucken wir uns jetzt gleich noch an.
  309. Da gibt's verschiedene Möglichkeiten. Allgemein nennt man solche Implementierungen dieses dieser dieser Schlossvariablen Schlossalgorithmen.
  310. Ja. So. Was hat Log denn für ein Basisdatentyp? Wie gesagt, das ist ein abstrakter Datentyp. Das das ist
  311. letztendlich die Basisklasse, würde ich jetzt mal sagen. Ja, also die Basisklasse aller Schlossalgorithmen heißt jetzt in unserem Kontext hier
  312. erstmal log. So, jetzt entferne ich mal wieder ein bisschen Dinge aus dem Frag jetzt.
  313. Okay. Ähm, wie kann man jetzt letztendlich so ein Schlossalgorithmus tatsächlich konkret bauen?
  314. Ähm, jetzt gucken wir uns erstmal den Adruck Lösungsansatz an oder sogar mehrere Adrucklösungsansätze äh wie man wie man sowas bauen könnte.
  315. Ja, das ist jetzt zunächst mal der naive Lösungsansatz. Ich versuche den mal kurz zu erklären. Wir sagen jetzt einfach, dass unser Logdatentyp, das ist einfach
  316. einsign. Ja, also in in C kann man mit Typed einen Datentyp neuen Datentyp anlegen und quasi den als Alias für einen
  317. anderen Datentyp anlegen. Letztendlich entspricht log einfach uns car, also einem vorzeichenlosen 8 Bit Integer vereinfacht gesagt.
  318. So und was macht das Aququire? Das Aquirer kriegt einen Pointer auf so einen Char übergeben. Ja, ich das Logobjekt übergeben.
  319. Und jetzt wird hier in einer Endlosschleife. Ja, wir sehen hier, der Schleifenrumpf ist leer, deswegen ist hier ein Semikron. Sie werden das in den
  320. Folgefolien direkt hinter diesem While hier finden. Ich habe das hier nur auf dieser ersten Folie mal in die nächste Zeile gezogen, damit es noch ein
  321. bisschen offensichtlicher wird, dass es also eine Schleife ist, die in ihrem Rumpf überhaupt nichts tut, sondern einfach nur wiederholt diese Bedingung
  322. hier überprüft. Ja, was ist was ist diese Bedingung? Diese Bedingung ist einfach der Wert von diesem Char, das hinter dem Lock steckt. Ja. und ein tar
  323. oder im weiteren Sinne eine Ganzzahl ist in C wahr, wenn sie ungleich 0 ist und sie ist falsch, wenn sie gleich 0 ist. Ja, das heißt also letztendlich diese
  324. Schleife hier dreht sich so lange im Kreis, wie dieses Lock hier z.B. 1 ist oder bis so sol so lange im Kreis wie dieses Log
  325. hier ungleich null ist. Ja. Oder anders gesagt, diese Schleife wartet so lange, bis log den Wert null hat.
  326. So, wenn Log den Wert null hat, dann gehen wir hier runter und setzen, ne, wir nehmen hier den diesen Logzeiger, diezen, in schreiben dort eine einzeln.
  327. Und damit haben wir das Log belegt. Ja, wenn jetzt ein anderer äh Prozess im weiteren Sinne kommt und auch das Aquir aufruft, dann wird der hier diese
  328. Funktion hier betreten. Hier in dieser While Schl feststellen, aha, Sternlog ist 1 und einfach hier end also endlos, na ja, sich so lange im Kreis drehen,
  329. bis das nicht mehr der Fall ist. Ja, und das klingt ja jetzt erstmal so, als ob man damit so ein so ein Schlossalgorithmus implementieren kann.
  330. Ja, das Release, das setzt letztendlich dieses Log wieder auf null. Das heißt, wenn ich also Aquire mache, schreibe ich da eine eins hin. Wenn ich
  331. das Release mache, schreibe ich da eine Null hin. Und der nächste, der während während ich in dieser ich mich in meinem kritischen Abschnitt befinde, versucht
  332. Acquirreed zu machen, der wird halt hier in dieser in dieser Warteschleife hier stehen bleiben. Ja, da wird solange nicht weiterkommen. So, jetzt steht aber
  333. schon mal ganz groß in rot über diese Folie falsch. Das ist die spannende Frage, warum steht da falsch ist.
  334. Ähm, so es gibt's ja schon ein paar Kommentare. Also zum einen, wie rechenintensiv ist die Schleife ohne Inhalt, wenn diese permanent
  335. weiterläuft? Ja, das ist auf jeden Fall Nachteil. Die ist die ist ziemlich rechenintensiv, ne? So, die die führt
  336. kontinuierlich CPU Instruktionen aus. Ja, da wird also wird keine Rechenzeit irgendwie an irgendjemand anders
  337. abgegeben. Also ist erstmal Rechenzeitverschwendung, könnte man sagen. Ähm,
  338. so und jetzt gibt's noch den noch einen weiteren Kommentar hier von Joachim, der vorschlägt, dass es vielleicht doch möglich sei, dass zwei Threads
  339. gleichzeitig Lock auf eins setzen. Das verstehe ich jetzt aber nicht. Also anders gesagt, ja, ich glaube schon, dass Sie recht haben, aber können
  340. Sie das mal konkretisieren? Also was muss denn passieren, dass zwei Threads das gleichzeitig tun? Wirklich gleichzeitig gibt's bei uns ja nicht.
  341. Ja, wir haben ein Uniprozessorsystem. Das heißt, also der Scheduler kann immer nur genau einen Prozess oder einen Thread ähm laufen lassen, die CPU
  342. zuteilen. Das läuft immer nur ein Thread auf unser einen CPU, aber trotzdem kann es passieren, dass zwei Threads dieses Log auf eins setzen.
  343. Ja, Vorschläge. [seufzt] Genau. Ja, hier kommt der Vorschlag. Wird nach der nach der
  344. Wildschleife unterbrochen. Ja, also wir haben diese Wildschleife. Wir stellen fest, aha, log ist null. Juhu,
  345. wir können das Log jetzt nehmen. Die While Schleife wird verlassen. Jetzt befinden wir uns hier und jetzt findet ein Prozesswechsel statt.
  346. Jetzt kommt ein anderer Prozess, ruft auch das Aququire auf. Stellt fest, aha, log ist null. Juhu, ich kann das Log nehmen. Geht hierhin,
  347. setzt log auf 1, betritt den kritischen Abschnitt, tut irgendwelche Dinge auf unserer geteilten Q und so weiter. Irgendwann passiert wieder ein
  348. Prozesswechsel zu dem Thread vorher. Der befand sich gerade direkt vor dieser Zuweisung 1. Ja, der weiß jetzt Lock, dass immer noch den Wert 1 hat von dem
  349. anderen Prozess. wieder die ein zu. Jetzt haben wir zweimal zwei Prozesse, die dem Log eine ein zugewiesen haben und beide gehen
  350. jetzt in ihren kritischen Abschnitt. Ja, das genau das, was wir verhindern wollten. So, also was ist das Problem?
  351. Der kritische Abschnitt, den wir sichern, also der kritische Abschnitt, den wir sichern wollen, äh ist ist kritisch, aber das Aquirer selbst ist
  352. auch kritisch, nämlich wenn wir genau hier zwischen diesen beiden Zeilen hier äh verdrängt werden. Ja, also genau der Moment nach dem Verlassen von der
  353. Mateschleife vor dem Setzen der Schlossvariablen äh ist das Problem. Ja, und das kann eben dazu führen, dass jetzt mindestens zwei, wenn ich sogar
  354. noch mehr Prozesse, diesen eigentlich durch Aquire oder letztendlich durch unser Log gesicherten kritischen Abschnitt äh überlappt ausführen. Ja,
  355. also genau das, was wir verhindern wollten. Und ähm die, sag mal, die klassische Lösung zunächst mal aus algorithmischer
  356. Sicht ist der sogenannte Bäckereialgorithmus. Ähm, wir werden auch gleich noch ganz kurzen Blick auf eine mögliche
  357. Implementierung werfen. Die den werde ich jetzt aber nicht vertiefen. Ähm, zunächst mal auf abstrakter Ebene ähm bekommt einen Prozess, der einen
  358. kritischen Abschnitt betreten will, eine Warteummer. Ja, der wie sich wie man sich das beim Amt vorstellen kann. Man zieht eine Nummer
  359. und dann erfordert erfolgt die Zulassung in den kritischen Abschnitt in der Reihenfolge der Nummern. Ja, so wie man sich das halte vom Amt
  360. vorstellt. Das heiß, wenn der kritische Abschnitt frei ist, dann darf der Prozess mit der niedrigsten Warenummer
  361. den kritischen Abschnitt betreten. Ja, und wenn der kritische Abschnitt wieder verlassen wird, dann wird die Wartenummer weggeschmissen. Ja, im
  362. Prinzip, wie man sich das vorstellt beim Amt oder in der Bäckerei. Ja, wobei das in deutschen Bäckereien jetzt vielleicht normalerweise so nicht funktioniert.
  363. Ähm n es gibt noch ein kleines Randproblem, was man bei der Implementierung auch sieht, wenn man sie sich genau anguckt, nämlich dass der
  364. Algorithmus, dieser Bäckereialgorithmus nicht garantiert, dass eine Wartennummer nur einmal vergeben wird. Ja, also es gibt so ein so so eine Stelle, wo es
  365. möglich ist, äh dass mehrere Prozesse dieselbe Warteummer kriegen, wo dann natürlich nach dem bisherigen Kriterium noch nicht klar ist, welcher als erstes
  366. dran darf. Und in diesem Fall entscheidet die Prozess ID, ja, also die äh z.B. für die niedrigst mögliche Prozesside ID unter denen mit derselben
  367. Warenummer darf als erstes. So, ich gehe gleich noch auf die Fragen ein.
  368. Jetzt mache ich aber erstmal den Bäckerealgorithmus noch fertig. Ähm, das ist jetzt so eine Pseudo Code Implementierung. Ja, also da ist das ist
  369. diese Logstruktur ein bisschen komplexer. Da gibt es also ein booli array choosing der Größe N. Ja, wir nehmen
  370. jetzt zunächst mal an, wir haben wir haben n Prozesse, die die hier konkurrieren. Ja, und dieses N wirkt sich auch direkt hier auf die
  371. Dimensionierung von diesem Choosing Array hier aus. Und wir haben ein Number Array, das auch die Größe N hat. Und diese beiden diese beiden Arrays werden
  372. letztendlich verwendet, um zu synchronisieren. Und das Aququire sieht so aus, dieses in dem I landet die aktuelle Prozess ID.
  373. Ja, und dann wird zunächst mal in dem Choosing Array hier die das eigene Feld auf True gesetzt. Ja, also jeder Prozess, der gerade der
  374. sich der gerade beim Warteummer ziehen ist, der schreibt hier erstmal ein T rein. Wenn er mit Warteummer ziehen fertig ist, schreibt er wieder ein False
  375. rein und dazwischen schreibt er in die eigene Number. Wir haben n ein Feld der Größe Numbers, ne? Das sind einfach die die Wartenummern aller beteiligten
  376. Prozesse und die Warteummer, die hier gezogen wird, ist das Maximum aus allen Wartenummern, die bis jetzt hier
  377. versammelt sind, + 1. Ja, das ist so die nächste Warteummer, die die hier äh die hier gezogen wird. Und das ist jetzt letztendlich auch die
  378. Zeile, wo es passieren kann, dass ähm dass mehrere Prozesse hier ähm in dieses Number Array dieselbe Warteummer eintragen. Ja, weil dieser Abschnitt
  379. hier eben nicht synchronisiert ist. Ja, also es kann passieren, dass hier mehrere Prozesse gleichzeitig diese dieses Maximum hier ausrechnen, eins
  380. drauf addieren und es kommt dann dieselbe äh dieselbe Wartenummer raus. Ähm, das löst sich aber gleich eben durch diese weitere Priorisierung durch
  381. die Prozess ID. Was wird hier unten gemacht? Hier wird letztendlich komm über das dieses komplette Choosing und das komplette Number Array gelaufen,
  382. also j = 0 bis N. Und das ist jetzt wieder so eine so eine so eine Wchleife mit einem leeren Rumpf. Ja, das den Semikolon hier dürfen Sie nicht
  383. übersehen. Ähm und jetzt wird erstmal gewartet, bis keiner mehr in keiner mehr gerade beim Auswählen einer Warenummer ist. beim Ziehen einer Warenummer.
  384. Ja, und dann wird letztendlich ähm Nein, Unsinn. Es wird jetzt erstmal geguckt, dass der der Prozess äh mit der
  385. Nummer J, dass der ähm nicht mehr wartet. Und dann wird geguckt, wartet äh hat der eine Warteummer. Ja, also wenn der wenn der hier eine Null
  386. eingetragen hat, dann wartet dieser Prozess gerade sowieso nicht. Wenn er wartet, dann wird geguckt, ist äh die Wartenummer von dem Konkurrenten kleiner
  387. als die eigene Warenummer. Ja, und hier unten ist noch diese Geschichte mit der Prozess ID Priorisierung äh codiert, aber letztendlich hier in dieser Zeile
  388. steckt drin, ich dieser Schlossalgorithmus äh di dieses dieser Bäckereialgorithmus, der wartet hier in einer in einer Whitechleife, die
  389. sonst nichts tut, solange dieser Konkurrent hier eine kleinere Warenummer hat. Ja, und wenn man sich das Verfahren
  390. genau anguckt, stellt man fest, also wenn diese Schleife hier durch ist, dann gibt es keinen mehr in der ähm in diesem Number Array, der also eine Wernummer
  391. gezogen hat, die kleiner ist als die eigene. Ja, und damit ist die eigene Warteummer die kleinste, die noch da ist. und dann darf man dementsprechend
  392. den äh den kritischen Abschnitt betreten. Ja, und bei dem Release wird jetzt endlich einfach in die in dieses in
  393. dieses Number Feld hier wieder eine Null eingetragen, ne? Das ist das das bildliche Wegwerfen von dem von dieser ähm
  394. von der Warteummer. So. Und dieser Algorithmus ähm der funktioniert. Ja, das kann man auch
  395. beweisen, dass das dass der korrekt ist, aber er hat ein paar Probleme. Ja, also zum einen weiß man in der Regel nicht vorher, wie viele Prozesse um den
  396. Eintritt in diesem kritischen Abschnitt konkurrieren werden. Also dieses groß n äh liegt in der Regel nicht fest. Ja, Prozess IDs liegen normalerweise auch
  397. nicht im Wertebereich von 0 bis n -1. Da könnte man wahrscheinlich noch irgendwie eine Abbildung finden. Das ist jetzt nicht das größte Problem, aber zumindest
  398. würde es dann nicht eins zu eins funktionieren. Ähm und was vor allem ein Problem ist, diese Funktion Aquire, die hat eine große Laufzeit. Ja, also auch
  399. diese auch hier haben wir wieder dieses aktive Warten, also in einer Schleife CPUZeit verbrennen ähm bis man also den bis man also den kritischen Abschnitt
  400. betreten darf. Und ähm diese Funktion Aquire hat äh auch eine eine Laufzeit, die linear mit der Anzahl der beteiligten Prozesse ist.
  401. Ja, also O von N, selbst wenn gerade überhaupt kein anderer Prozess im kritischen Abschnitt ist, selbst wenn, also der kritische Abschnitt gerade
  402. komplett frei ist. Okay, was man jetzt hier eigentlich haben wollen würde, wäre also ein Algorithmus,
  403. der nicht so kompliziert ist, ja, nicht so komplex ist in der Laufzeit. und aber gleichzeitig so einfach äh also der korrekt ist und aber auch so
  404. einfach wie der naive Ansatz, ja, das was wir vorhin gesehen haben, diese Schleife, die letztendlich selber kritisch war. Ja, das wäre eigentlich
  405. schön, wenn es das gäbe und da gucken wir uns gleich Lösungen dazu an. So, und jetzt gucke ich mir mal noch ein paar Fragen an hier.
  406. Ähm, ist durch dieses Problem dann bei Windows z.B., dass man z.B., wenn man eine PDF Datei aufhat, die dann nicht mit anderen Programmen editieren kann,
  407. heißt das Windows unterstützt das gar nicht. Also ähm bin jetzt kein regulärer Windows User äh
  408. wenn man eine Datei geöffnet hat mit einem Programm, dann kann es natürlich sein, dass dieses Programm dem Betriebssystem irgendwie signalisiert,
  409. ich habe jetzt hier meine meine Clown auf dieser Datei. Ja, und das andere Programme diese Datei deswegen dann gar nicht öffnen wollen. Ähm,
  410. prinzipiell könnten sich Programme genauso unter Windows natürlich äh beliebig synchronisieren und auch gleichzeitig z.B. auf dem auf derselben
  411. PDF-Datei arbeiten. Ja, das ist aber nicht so ohne weiteres äh immer möglich, ne? je nachdem, welche Operation auf dieser
  412. PDFdatei passieren sollen. So. Ähm, jetzt gibt's hier die Frage, ich verstehe noch nicht wirklich, warum
  413. eine Wild Schleife ohne Rumpf nicht in einer Endlusschleife endet. Ähm, na ja, nur weil eine Wild Schleife, gehen wir mal zurück zu der einfachen
  414. hier, warum warum diese Wchleife nicht in einer Endlosschleife endet. Ähm, na, diese Weschleife beendet endet
  415. genau dann, wenn das wenn die Bedingung hier in der Klammer den Wahrheitswert falsch bekommt. Ja, und ein char oder im weiteren Sinne ein int äh gilt
  416. in einer Bedingung als falsch, wenn es null ist. Ja, das heißt also sobald ein anderer Prozess herkommt und dieses Log auf null
  417. setzt, wird diese Bedingung hier falsch und die Schleife wird verlassen. Ja, das muss keine Schleife sein. Natürlich, wenn man jetzt nur lokal
  418. dieses Stück Code hier betrachtet, dann sieht das so aus, als ob die Schleife nie beendet werden kann. Ja, weil wenn die Schleife ein, also
  419. wenn diese Bedingung einmal wahr ist, dann gibt es erstmal keine keine ersichtliche Codstelle, die die äh die Wahrheit dieser Bedingung
  420. äh ändern könnte. Ja, dazu muss ein anderer Prozess kommen, der das Acquire äh der das Release aufruft, ja, der z. Gerade, also der sein kritischen
  421. Abschnitt verlässt, der ruft das Release auf und das Release, wie man hier unten sieht, setzt das Log auf null. Ja, und der andere Prozess, der hier in der
  422. Wchleife wartet, der kann dann der verlässt dann diese White Schleife, sobald er wieder äh rechnen darf.
  423. Warum benutzt man für Lock nicht einen Booli statt eines Chars? Äh täst genauso. Wäre letztendlich bei einem Maschinencode hinten rausfällt
  424. sogar dasselbe, vermute ich mal ganz stark. Ja, also auch ein Boolian ist klassischerweise in C ein 8 Bit Integer, aber
  425. das würde würde das Problem genauso lösen. Haben Sie völlig recht. Hat C eine Standard Logfunktion dafür? Äh nein, C
  426. hat zunächst mal kein Ja, stimmt nicht. C11 hat schon irgendwann das das auch das Konzept von Nebenläufigkeit. Äh letztendlich kommen da halt einfach
  427. Threads mit dazu und dann gibt's sowas wie Lock und Unlock und so weiter gibt's auch. Ähm ältere CSstandards haben überhaupt kein Konzept von
  428. Nebenläufigkeit. Ja, weil letztendlich muss man dann z.B. die Betriebssystemstellen dafür verwenden, die die für die
  429. Synchronisation da sind. Die gucken wir uns dann gleich an. Wie wahrscheinlich ist der Fall, dass zwei Prozesse Log auf ein setzen?
  430. Ja, das kommt auf an. Äh das kommt drauf an, wie lang z.B. für diese kritischen Abschnitte sind. Äh das kommt auff an, wie häufig diese kritischen Abschnitte
  431. überhaupt aufgerufen werden sollen oder wie oft das Aququire und äh letztendlich aufgerufen wird. Ja, also wenn sie zwei Prozesse haben, die einfach ständig in
  432. einer Endoschleife Acquire release Acquire release acquire release machen, dann wird's relativ wahrscheinlich. Ja, dann wird das innerhalb von ein paar
  433. Millisekunden tatsächlich auch passieren. Ähm, wenn Sie äh Prozesse haben, die nur sehr selten mal einen kritischen Abschnitt ausführen, dann
  434. wird das halt Größenordnungen unwahrscheinlicher. Das ist auch richtig gemein. Ja, dann haben sie also einen fiesen äh Synchronisationsfehler,
  435. Synchronisationsbug in ihrem Code, den sie aber bei durch Testen möglicherweise gar nicht finden, sondern das passiert, der tritt dann erst in 10
  436. 000 m Höhe beim Kunden auf. Ähm, deswegen ist das so wichtig, was ich heute erzähle. Ja, also je äh je unwahrscheinlicher diese dieser
  437. Fall eintritt, desto hässlicher ist dieser Bug eigentlich, weil irgendwann passiert doch mal und kann dann natürlich beliebige Resultate haben,
  438. wenn äh wenn das also z.B. ein ein Rechensystem ist, das Teil von einem Flugzeug ist oder so. Ja, wenn da irgendwie kaputte Datenstrukturen sind
  439. und das Flugzeug deswegen vom Himmel fällt, werden die Arrays dann beim Bäckereialgorithmus unendlich groß? Ähm
  440. ja, natürlich nicht. Also, erstes mal war natürlich AR grundsätzlich nicht unendlich groß werden können. Ähm und zum zweiten, weil man den in der Praxis
  441. auch nicht einsetzt. Ja, warum werden wir gleich noch mal ein bisschen genau besprechen. Was ist die maximale Array Größe in C? Ich weiß nicht, ob der
  442. C-Standard irgendwas vorschreibt. Äh letztendlich wird das in der Regel daran scheitern, äh wie groß ihr Hauptspeicher ist und oder der Stack
  443. ist, z.B. Ja, aber ich ich wäre jetzt ich wüsste jetzt keine keine Limitierung, die der CSstandard vorschreibt.
  444. Okay, Bäckereialgorithmus. Ähm, jetzt gucken wir uns mal andere Lösungen an. Ja, also aktives Warten ist
  445. ähm nachteiligt. Das woran es jetzt liegt, werden wir gleich noch sehen. Jetzt gucken wir jetzt erstmal Hardware Unterstützung für das Problem ist, dass
  446. wir jetzt gerade noch haben, nämlich sie erinnern sich an diesen an diesen kleinen Momenten nach der Wild Schleife vor dem Setzen von dem Lock. Ja, wenn
  447. genau dazwischen äh die Verdrängung passiert, dann haben wir wieder ein äh ja wieder eine Race Condition, wieder zwei Prozesse, die die in den kritischen
  448. Abschnitt reinkommen. Ja, und dafür gibt's Hardware Unterstützung. Ähm, die einfachste oder vermeintlich einfachste Möglichkeit ist einfach Unterbrechungen
  449. ausschalten, Unterbrechungen unterdrücken. Ja, allein der Unterbrechungsmechanismus in der CPU sorgt dafür, dass der CPU
  450. innerhalb des kritischen Abschnitts die CPU entzogen werden kann. Also z.B. wenn der Timerbaustein eine Interrupt auslöst und damit dem Scheduler signalisiert,
  451. die Zeitscheibe von dem gerade laufenden Prozess ist abgelaufen. Scheduler entscheidet jetzt, es kommt jetzt ein anderer Prozess dran und macht ein
  452. Kontextwechsel. Das ist die eigentliche der ist der einzige Grund, der dazu führen kann, dass also äh ja hinterher unsere
  453. Datruktur kaputt gehen kann durch eine Race Condition. Ähm und das kann ich zunächst mal ganz einfach verhindern, indem ich halt bei
  454. dem Aquir einfach sag, ne? Ich ich rufe diese CPU Instruktion CLI auf, die schaltet einfach die Interupts aus und das Release schaltet halt die
  455. Interrupts wieder ein. Ganz einfach. Oder me eine Idee, warum das vielleicht eine dumme Idee ist?
  456. Vorschläge, warum das warum man das vielleicht nicht machen sollte. gibt letztendlich zwei gute Gründe.
  457. Trudeln Vorschläge ein, wenn mein kritischer Abschnitt 2 Stunden dauert, das ist ganz schlecht, ganz genau. Ja, also wenn man zwei Stunden lang die
  458. Inupts abschaltet, dann wird zi Stunden lang das System keine vernünftigen Dinge mehr tun. Ja, also z.B. wird diesen Prozess die CPU zwei Stunden lang nicht
  459. mehr entzogen, zumindest nicht durch ein Timer Interrupt, der das Zeitscheibenende signalisiert. Ja, also plötzlich können Prozesse auch in dem
  460. System mit äh mit Prätion wieder die CPU monopolisieren. Das ist definitiv ein Problem. Ja, und auch können in diesen zwei zwei Stunden
  461. keine anderen Interrupts durchkommen. Also z.B. auch keine Tastatur äh Tasten keine Tastendrücke, Mausbewegungen, sonst wie. Ja, die werden alle nicht
  462. mehr ans Betriebssystem zugestellt, weil die alle letztendlich interupt getrieben arbeiten.
  463. Ähm, wenn das Programm selbst ein Interrupt aufruft, ja, Programme können kein Interrupt aufrufen in dem Sinn,
  464. sondern die lösen Bhaupt, dann lösen die Traps auf aus und die gehen immer noch. Ähm, genau. Wenn man den kritischen Abschnitt hat mit einer Endlosschleife,
  465. das geht natürlich in dieselbe Richtung wie die wie der zwei Stunden Vorschlag, ja, dann passiert halt endlos kein kein großer Fortschritt mehr in dem System.
  466. Nutzer Interaktion sind nicht mehr möglich. Genau. Tastatur Maus geht nicht mehr. Eingabe Ausgabegeräte tun nichts mehr.
  467. So und jetzt kommt natürlich auch noch ein weiterer Punkt. Ja, hat ein Programm überhaupt nötigen Rechte sowas zu machen? Nein, hat's nicht. Ja, also
  468. normales Anmeldungsprogramm darf diese beiden Instruktionen gar nicht ausführen. Ja, das ist wieder die Trennung zwischen äh zwischen
  469. Systemmodus oder Supervisor Modus und User Mode. Ja, im User Mode können diese beiden Instruktionen einfach nicht ausgeführt werden. Ja, das ist halt
  470. einfach nicht erlaubt. Genau aus dem Grund oder aus den gerade genannten Gründen. Ähm ja und letztendlich ähm wird eben
  471. letztendlich das komplette Betriebssystem, alle anderen Prozesse, Gerätetreiber, wird alles beeinträchtigt, wenn ich das mache. Ja,
  472. deswegen darf man es nicht. Aber es wäre zumindest für kurze kritische Abschnitte eine Möglichkeit, eine mögliche Lösung. Also man z.B. Ihr seht, wenn man gerade
  473. sowieso im Systemmodus ist, ähm also letzt nicht im Betriebssystem äh so eine Synchronisation machen möchte, ein kritischen Abschnitt sichern möchte,
  474. dann ist es eine Möglichkeit, die man nicht komplett vom Tisch wischen darf. Ja, das ist durchaus manchmal sinnvoll, das zu machen, wenn man sich sehr sicher
  475. ist, dass der kritische Abschnitt sehr kurz ist und definitiv auch endet. Ja, aber jetzt gucken wir uns noch mal das Problem an mit dieser Wild Schleife
  476. und dem Setzen auf eins in der Zeite darauf, wo wir eben dazwischen unterbrochen wurden. Und dafür gibt's auch ähm eine Hardwareösung, nämlich die
  477. sogenannten atomaren Operationen. Ja, viele CPUs unterstützen unteilbare Leseemodifikations und Schreibzyklen, mit denen sich ähm so so äh
  478. Schlossalgorithmen implementieren lassen. Ja, also z.B. Ähm hier Motorola ist das die Instruktion Test and Set. Ja, was macht
  479. diese Operation? Die testet in dem Fall hier Bit 7 von dem Zieloperanten Log, das ist also z.B. schon wieder ein 8 Bit Character.
  480. Ähm, die testet also dieses Bit und setzt dieses Bit und liefert den den vorherigen Zustand von diesem Bit in einem Condition Code.
  481. Ja, und abhängig abhängig von diesem Condition Code kann man jetzt hier springen oder nicht springen. Oder anders gesagt, wenn das Bit vorher schon
  482. eins war, dann wird einfach wieder zurückgesprungen zu dem Aquire. Ja, das heißt, wir haben also hier schon das hier ist es nichtich wiederum unsere
  483. Schleife. Ja, also die Instruktion, die Instruktion, die Instruktion, die die Instruktion. Wenn dieses Test und Set
  484. hier feststellt, dass dieses höchstwertige oder nee, wenn das höchstwertige Bit null war, dann setzt diese Instruktion dieses Bit
  485. und merkt sich den alten Zustand von diesem Bit wieder in so ein Condition Code und dann springt diese Sprunginstruktion eben nicht, ne? Und
  486. dann kann man ab hier in den kritischen Abschnitt gehen und weiß eben, dass das Bit vorher null war, durch mich jetzt auf eins gesetzt wurde. Ja, oder anders
  487. gesagt, diese Instruktion vereinigt eben das Testen und das Setzen. Ja, deswegen heißt sie Test and Set. Ja, die kann eben nicht noch noch
  488. weiter unterbrochen werden. Auf X86 gibt's eine ähnliche Instruktion, ne? kann man dafür letztendlich diese Exchange Instruktion
  489. verwenden. Von der Semantik her ziemlich ziemlich ähnlich wie in der Motorola Variante. Ja, auf Power PC gibt's was ähnliches. Letztendlich haben alle,
  490. Entschuldigung, letztendlich haben alle modernen Instruk moderne CPUs so eine so ein Lesemodifikationsschreibzyklusinstruktion.
  491. Ähm, so, aber die bis jetzt gezeigten Schlossalgorithme, die haben alle einen großen Nachteil, nämlich die warten
  492. aktiv. Ja, also schon die erste, dieser erste naive Vorschlag, der also einfach in der Wchleife arbeitet, der dieses dieses kleine Problem hatte, dass er
  493. halt in einem ungünstigen Zeitpunkt verdrängt werden kann, aber letztendlich wartete aktiv. Genauso der Bäckereialgorithmus. Ja, da
  494. waren letztendlich eine Menge von Wchleifen, die halt in ihrem Rumpf ein Semikolon stehen hatten, die aber halt einfach so lange äh sich im Kreis
  495. drehen, bis wieder irgendein Zustand erreicht ist. Ja, die warten aktiv. Ähm genauso diese atomanoperationen, ja, das sind auch letztendlich Schleifen,
  496. die ständig testen und setzen und testen und setzen und testen und setzen so lange, bis äh der getestete Wert null ist. Ja, also bis der bis das Log frei
  497. ist. und der ähm der kritische Abschnitt betreten werden kann. Ja, und dieses aktive Warten, das hat eine ganze Reihe Nachteile. Ähm zunächst mal der Prozess,
  498. der wartet, ja, der darauf wartet, dass Log z.B. null wird, der kann selbst überhaupt keine Änderung dieser Bedingung
  499. hervorrufen oder herbeiführen. Ähm, auf also Änderung der Bedingung herbeiführen, auf die er wartet. Ja, also der sorgt selbst nicht dafür, dass
  500. das Lock jemals null wird, sondern der wartet darauf, dass jemand anderes dieses Lock auf null setzt. Also ein anderer Prozess,
  501. ja? Trotzdem dreht er sich in der Schleife und rechnet. Mit anderen Worten, ähm z.B. Wenn ja, dieser Prozess läuft ja
  502. gerade der, nehmen wir mal an, wir sind irgendwie im im äh prämit Zeitscheiben Scheduling irgendwie, dann verbraucht er seine komplette Zeitscheibe mit
  503. iterieren und testen dieser Logariablen, also die kompletten 20 Millisekunden hindurch wird einfach nur in der Endlosschleife oder nicht in einer
  504. Endoschleife, in einer Testschleife äh ständig getestet, ob sich dieses Lock dann endlich mal auf null geändert hat. Ja, hat's aber natürlich nicht, weil
  505. dieser Prozess selbst das gar nicht machen kann auf dem und auf dem Uniprozessorsystem, der weil auch kein anderer Prozess dran kommen kann, der
  506. dieses, der vielleicht gerade im kritischen Abschnitt ist und dieses Log auf null setzen könnte. Ja, also er behindert ähm
  507. alle anderen Prozesse, weil er seine Zeitscheibe mit unnützen Schleifendrehen ähm äh ja verbrennt. Ja, also andere Prozesse, die sonstige
  508. sonstige sinnvolle Arbeit leisten können, die jetzt mit unserem kritischen Abschnitt überhaupt nichts zu tun haben und letztendlich schadet er auf sich
  509. selbst. Warum? Weil je länger dieser Prozess wartet, damit die CPU behält, ja, also auf dem auf dem Prozessor CPUZit verbrennt, desto länger muss er
  510. ja auch drauf warten, dass endlich ein anderer Prozess dran kommt, seinen kritischen Abschnitt beendet und Log auf null setzt.
  511. Ja, das heißt also das aktive Warten ist auf einem Uniprozessorsystem einfach nicht schlau. Es funktioniert,
  512. aber es ist nicht schlau. Nur bei dem Multiprozessorsystem wird es ein bisschen aufgeweicht, weil natürlich bei einem Multiprozessorsystem
  513. der andere Prozess, der das Log gerade hält in seinem kritischen Abschnitt ist, wirklich gleichzeitig auf eine anderen CPU weiterrechnen kann und das Log dann
  514. auf null setzen kann. Da kann das sinnvoll sein. Ja. Auf einem Uniprozessorsystem ist es nicht schlau aktiv zu warten
  515. und deswegen ist das was man eigentlich macht das sogenannte passive Warten. Ja, und dafür braucht man letztendlich Betriebssystem
  516. Unterstützung. Ja, und im Betriebssystem wird eine ähm primitive dafür verwendet. Das sind die Semmerapforen und die ermöglichen das und das gucken wir uns
  517. jetzt an. Ja, also passives Warten ist die das, wo wir hin wollen und da ist eben die Idee,
  518. während ein Prozess darauf wartet, dass eine Ereignis eintritt, ja, also z.B. das Log frei wird, gibt der Prozess einfach die Kontrolle über die CPU ab.
  519. Ja, das kennen wir schon von den IOBSTs, von den von den ein Ausgabestößen, ja, auch im Synchronisationsfall, also in dem Fall, dass ich auf ein Log warten
  520. möchte. blockiert sich der Prozess auf ein Ereignis, geht in den Zustand blockt. Ja, der Prozess Kontrollblock dieses
  521. Prozesses wird in eine Warteschlange eingereiht, die also auf dieses Ereignis in dem Fall die Freigabe dieses Logs warten. Und wenn das Ereignis eintritt,
  522. also das ein anderer Prozess dann dieses Lock freigibt, z.B., Dann wird ein darauf wartender Prozess deblockiert.
  523. Ja, das heißt also ein Prozess, der wartet, ist nicht mehr im Zustand running wie beim aktiven Warten, sondern im Zustand blocked.
  524. Ja, die Wartephase eines Prozesses auf das Freiwerden eines eines Logs wird als Blockadephase, ja, das was wir bis jetzt schon als ein Ausgabestoß kennen,
  525. ausgelegt. Also, wenn ich ein Log auf einem auf einer auf einem Lock, das gerade ein Aqu, das gerade gesperrt ist, dann wird
  526. der Ablauf Plan für die Prozesse aktualisiert. Also, es passiert wieder so eine Scheduling so ein Scheduling Schritt. Es wird ein anderer gerade
  527. schon gerade laufwähliger Prozess ganz normal plangemäß abgefertigt. Also der vorderste aus der aus der Ready Liste rausgenommen wird also dispatchted
  528. und wenn es gerade überhaupt keinen Laufwegen Prozess gibt, dann ähm läuft die CPU leer. Ja, das ist also so eine Eidelphase, wo die wo die wo das
  529. Betriebssystem einfach mal kurzzeitig gar nichts macht. Ja, kann sich z. Du kannst z.B. den Prozessor in niedrigeren ähm Energiemodus versetzen, so in so ein
  530. in so ein so ein leichten Schlafmodus, wo also das ganze System weniger Strom braucht, so lange bis wieder irgendeiner lauffähig wird.
  531. Ja, und wenn ähm so ein Prozess blockiert, also von Running auf blocked geht, weil er auf den Lock wartet, endet damit natürlich
  532. auch sein CPU-Soß. Ja, also man kann sich jetzt konzeptionell das Warten auf ein Log vorstellen wie das Starten eines ein Ausgabestoßes.
  533. Beginn eines ein Ausgabestoßes. Ja, genauso wie äh Einausgabe von der Festplatte oder von der Tastatur oder sowas.
  534. Ähm die Betriebssystemabstraktionen, die man dafür verwendet, sind die sogenannten Semmerapforen.
  535. Ja, was ist ein Semmeraphor? Das ist eine Betriebssystem Abstraktion, die in den 60ern von dem Herrn Dextstra beschrieben wurde, der bestimmt dem
  536. einen oder anderen ein Begriff ist. Ähm, das ist eine nicht negative ganze Zahl, ja, 0 1 2 3 4 5 und für diese nicht negativen ganzen Zahlen sind zwei
  537. unteilbare Operationen definiert. P das steht für niederländisch Prol. Das liegt einfach daran, dass der Herr
  538. Dextra halt ein Niederländer war. ist. Glaub den gibt's auch noch. Muss ich noch mal nachgucken. Ich glaube, den gibt's noch. Ähm, also pro lach oder
  539. erniedrige, ja, oder auch down oder weight. Und das äh hat folgende Semantik. Wenn diese dieser Semmervor den Wert null
  540. hat, dann wird der laufende Prozess blockiert. Ja, und sonst nichts. Und ansonsten wird
  541. der Semmerform 1 dekrementiert. Ja, also wenn der vorher den Wert 1 hatte, hatte hat er einfach hinterher den Wert null.
  542. Ja, und dieses P ist unteilbar. Also, es kann nicht passieren, dass man während der Ausführung eines Ps ähm verdrängt wird. Ja, das ist so die so die
  543. Grundidee und das V macht das gegenteilige. Ja, verhoch, erhöhe ab Signal, das sind so die verschiedenen Varianten. Ähm, wenn es einen auf diesen
  544. Semmervor wartenden Prozess gibt, also einen blockierten Prozess, der also darauf wartet, dass der dieser Semmervor frei wird, dann wird der bei einem bei
  545. einem Vlockiert und ansonsten wird der Semmer vor um eins inkrementiert. Ja, und dieses diese Semmerformen können
  546. eben verwendet werden, um zwischen nebenläufig arbeitenden Prozessen sogenannte Synchronisationssignale ähm auszutauschen.
  547. Was das ähm genau bedeutet, das werden wir gleich an dem Beispiel sehen. Ähm, das ist tatsächlich die
  548. Implementierung von Semmern in einem in dem OOstups, das objektorientierte Studentenbetriebssystem. Das ist so ein so ein System, dass man in der
  549. Masterveranstaltung Betriebssystem Bau äh hier selbst baut. Das ist die das ist so ein Teil von der Semmervorimplementierung und da sieht
  550. man das was das Weight halt genau tut. Ja, das Weight, also das P guckt ist der Counter null. Ja, der also der eingebaute die eingebaute nicht negative
  551. ganze Zahl. Ja, und wenn der Counter null ist, dann kann natürlich der Selmerform nicht mehr weiter dekrementiert werden und dann wird die W
  552. letztendlich diese Schritte hier durchgeführt, die letztendlich dafür sorgen, dass der Prozess, der dieses Weight aufgerufen hat, blockiert wird
  553. und im anderen Fall wird einfach der Counter erniedrigt. Ja, und beim Signal wird geguckt, gibt es einen einen Prozess, der auf diese Semphore wartet.
  554. Ja, wenn es einen gibt, dann wird der geweckt, ja, also wieder ready gesetzt und anderenfalls wird der Counter um eins erhöht.
  555. Ja, und letztendlich ist so ein Semmerfor abgeleitet von der Klasse Waiting Room. Waiting Room ist letztendlich einfach eine Liste von
  556. Prozesskontrollblöcken, ja, also eine eine Warteschlange von Prozessen. Der Scheduler, der lieitstellen, die halt hier die auch verwendet werden.
  557. Ja, das ist dieses Active, dieses Block. Und dieses Wakeup, ja, und dieses Active sagt letztendlich, welcher ist der gerade laufwä laufende Prozess. Block
  558. blockiert einen gerade laufenden Prozess und Wakeup setzt einen blockierten Prozess wieder auf die Ready Liste.
  559. So und so benutzt man Semmer und damit sind wir eigentlich fast wieder am Anfang der Vorlesung. Ja, also Semapfor ist einfach eine konkrete
  560. Log, also eine konkrete konkreter Datentyp, den man also als Schlossalgorithmus als Schloss äh Algorithmen Schlossviablen Datentyp
  561. verwenden kann. Also ein Semmer hat klassischerweise äh initial den Wert 1, z.B. Normalerweise muss man das einfach
  562. einfach zuweisen. Ähm und wenn man also wenn man ihn als äh als Schlossvariable in dem Sinne verwenden will, um gegenseitigen Ausschluss äh
  563. hinzubekommen, dann setzt man den eben in Zal auf eins. Und das ist jetzt wieder unser NQ aus dem Beispiel vom Anfang. Also se also mit dem Weight das
  564. Log diese dieser Semmer vor dekrementiert um ein, dann ist er null und dann plus wird er mit Signal wieder um ein erhöht, dann ist er wieder eins.
  565. Und wenn ein zweiter Prozess versucht gleichzeitig in diesen kritischen Abschnitt zu kommen, dann blockiert er hier. Ja, alle weiteren Prozesse, die
  566. versuchen hier reinzukommen, während das Log den Wert null hat, dieser Semmer vor den Wert null hat, blockieren hier und mit dem Signal wird einer dieser
  567. blockierenden wieder aufgeweckt. Ja, das sorgt eben dafür, dass immer nur ein Prozess in diesem kritischen Abschnitt drin sein kann.
  568. Ähm, Hauer hat nachgeguckt, Extra lebt nicht mehr. Okay, dann war es einer der anden der
  569. anderen alten Hasen, die es die erstaunlicherweise noch leben. Ähm, man kann selber mal vor, aber lass die
  570. auch noch andere Dinge benutzen, z.B. die sogenannte einseitige Synchronisation. Ja, das ist also ein Erzeugerverbraucherszenario z.B., ne?
  571. Wir haben hier eine äh wir haben hier eine Listendatenstruktur und die neben unter der Annahme, dass dieses NQ jetzt irgendwie auf irgende also das NQ und
  572. das DQ auf irgendwie auf andere Art und Weise synchronisiert ist, z.B. durch eine äh durch gegenseitigen Ausschluss. Dann kann man hier mit einer Semaphore,
  573. die die Anzahl der Elemente zählt, die gerade in der Liste drin stecken, einseitig synchronisieren, ne? Jedes Mal, wenn ein Element reingesteckt
  574. wurde, sagt man Signal. Das erhöht also dieses diesen Element Counter hier um eins und jedes Mal bevor man ein Element dqmen möchte sagt man wait. Ja, und das
  575. und wartet eben darauf, dass mindestens ein Element in der Q drin steckt. Das die sogenannte einseitige Synchronisation, die heißt einseitig,
  576. weil immer nur eine Seite we hier, aber hier nur eine Seite blockieren kann, nämlich die Consumer Seite natürlich. Ja, das Weight ist ist es ist von den
  577. beiden Operationen auf der Semaphore die einzige, die blockieren kann, ne? nur eine Seite kann blockieren, nämlich die Consumerseite.
  578. Ähm und dann gibt's noch die Betriebsmittelorientierte Synchronisation. Na, da wird die funktioniert letztendlich so ähnlich wie
  579. die ähm dies die Synchronisation mit gegenseitigem Ausschluss. Ja, also macht macht vor der Benutzung einer einer Ressource macht man Weight, nach der
  580. Benutzung macht man ein Signal und setzt diese Semfor letztendlich aber nicht auf den Wert 1, sondern auf irgendeinen Wert, der Größe 1 ist. Ja,
  581. also wenn von einem Betriebsmittel z.B. Zeh zur Verfügung stehen, dann initialisiert man das halt mit Zeh. Dann können sich bis zu zeh Prozesse in dem
  582. kritischen Abschnitt befinden, ne? Weil jeder dann eine von diesen zehn Ressourcen benutzen kann.
  583. So, man kann mit se vorne aber auch noch komplexere Dinge tun. Ja, ähm z.B. das erste Leserschreiberproblem. Das ist so ein klassisches Synchronisationsproblem.
  584. Ähm, da soll also ein kritischer Abschnitt geschützt werden, wo es als Arbeit zwei Klassen von beteiligten, konkurrierenden Prozessen gibt, nämlich
  585. die Schreiber und die Leser. Und die Schreiber, die wollen Daten ändern an dieser Datenstruktur und dementsprechend muss ein Schreiber exklusiven
  586. Zugriff auf diese Datastruktur bekommen. Ja, also es darf immer nur ein Schreiber ganz alleine auf dieser Datenstruktur arbeiten oder beliebig viele
  587. gleichzeitige Leser. Ja, lesen kann man ja problemlos gleichzeitig. Ähm, aber sobald einer schreiben möchte, darf eben dann nur der schreiben und
  588. auch keiner kann anderer gleichzeitig schreiben und kann anderer gleichzeitig lesen. Auch das kann man mit Semmerform und synchronisieren.
  589. Das ist jetzt aber schon ein bisschen komplizierter, ja? Ähm, letztendlich brauchen wir hier zwei Semaphoren. Eine, die wir hier Newtext
  590. nennen und ein die wir WD für WR nennen und ein Read Count, ne? Der Read Count soll zählen, wie viele Leser lesen gerade gleichzeitig. Das sind so die
  591. Initialwerte. Gerade z. liest keiner ähm Initial. Und was so ein Schreiber machen muss, der muss einfach diese right Semaphore von 1 auf null setzen
  592. oder dran blockieren, dann darf er schreiben, dann darf es wieder freigeben. Ja, das ist jetzt ganz normaler gegenseitiger Ausschluss. Immer
  593. nur ein Schreiber darf schreiben. Leser ist jetzt aber schon ein bisschen komplizierter. Ja, da wird es erstmal eine Mutex
  594. belegt. Dann wird der Read Count um eins erhöht, dann wird geguckt, bin ich der erste Leser, ja? Oder gibt's schon andere Leser? Wenn ich der erste Leser
  595. bin, muss ich hier mit dem Weight WD hierfür sorgen, dass kein Schreiber hier rein hier reinkommt. Ja, wenn ich der erste Leser
  596. bin, muss ich dafür sorgen, dass während ich lese und auch möglicherweise andere lesen kein Schreiber schreiben darf. Ja, so und dann wird hier tatsächlich
  597. gelesen auf der Datenstruktur und am Schluss wird wieder mit der Mutex gesichert. Hier dieser Read Count im eins erhöht. Dann wird geguckt, bin ich
  598. der letzte Leser, der fertig geworden ist mit lesen. Wenn ich der letzte bin, dann muss ich hier diese WRD Semaphore wieder freigeben, damit wenn hier ein
  599. Schreiber gerade blockiert und warte darauf, dass er schreiben darf, in diesen Schreibeabschnitt ähm hinein darf.
  600. Das ist schon so ein bisschen fancy. Da muss man schon ein bisschen drüber nachdenken, ob das wirklich in allen Fällen so richtig funktioniert. Ähm, das
  601. ist sogar nur das erste Leserschreiberproblem. Ja, die verschiedenen Leserschreiberprobleme unterscheiden
  602. sich dadurch, wer Priorität hat. Ja, die Schreiber oder die Leser. Wenn man sich diesen Code hier ein bisschen genauer anguckt, dann wird man feststellen, äh,
  603. dass hier die Leser Priorität haben. Ja, also sobald ein Schreiber ansteht da unten, dann darf der wirklich erst rein, wenn der letzte Leser fertig ist. Und es
  604. dürfen auch jederzeit noch weitere Leser kommen. Es gibt noch noch ein anderes Leserschreiberproblem, wo sobald ein Schreiber z.B. schreiben
  605. möchte, die Leser, also kein neuer Leser mehr zugelassen wird, ne? wird gewartet, bis alle Leser dann fertig sind, damit der Schreiber endlich drankommt. Je
  606. nachdem, wie wie die Priorisierung hier aussieht, ähm ist es das erste oder das zweite Leserschreiberproblem.
  607. Ähm, es gibt von Semfor noch ein paar Varianten ähm oder Erweiterungen. Ja, also
  608. Biennähre Semforen, das da haben wir jetzt gerade schon Beispiel gesehen, ja, Semfore, die einfach nur auf null oder auf eins steht, die man letztendlich
  609. verwendet, in der Regel verwendet, um einen kritischen Abschnitt immer einen kritischen Abschnitt für für gegenseitigen Ausschluss zu sorgen. Ähm,
  610. die nennt man auch Mutex, ja? Mutex für Mutual Exclusion, also gegenseitigen Ausschluss. Ähm von dem Weight oder dem P gibt es
  611. auch Varianten, die nicht blockieren, also wo dafür gesorgt wird, dass also wo man tatsächlich über einen Parameter noch steuern kann, was passieren soll,
  612. wenn das Ding gerade belegt ist. Ja, da kann man quasi so ein so das Belegend testen und wenn es aber nicht klappen würde, dann kann man einen anderen
  613. Gruppfahrt wählen, anstatt zu blockieren. Ähm, weight mit Timeout gibt es noch, also wo das ähm wo man das nicht
  614. einstellen kann. Ich möchte zwar blockieren, aber nur für 2 Sekunden. Wenn innerhalb von 2 Sekunden der der diese Semmerfor immer noch nicht frei
  615. wird, dann möchte ich nicht weiter blockieren. Oder es gibt Implementierungen, wo man nicht nur eine Semmerfor hat, sondern ein ganzes Array
  616. von Semmaforen. Ja, das klingt jetzt erstmal so, als wäre das keine Besonderheit. Die Besonderheit da ist äh dass auf diesem Array auch atomare
  617. Operationen durchgeführt werden können. Also z.B. erhöhe die erste Semaphore, erniedrige die zweite und teste die dritte auf einen Wert oder so. Und nur
  618. wenn wenn alle drei Operationen klappen, werden sie auch durchgeführt und das ganze Atom. Ja, das ist so der der die die POS 5 die System 5 AP z.B. für für
  619. SF und die kann das. Ähm und was es bei Semfor auch noch gibt, sind eben Fehlerquellen. Ja. Ähm zum einen
  620. entsteht die Gefahr von Verklemmungen. Was das ist, das gucken wir uns in der nächsten Vorlesung an. komplexere Synchronisationsmuster, wie
  621. wir das jetzt hier gesehen haben, äh die können durchaus schwierig werden. Na, also das Leserschreiberproblem ist nicht das einzige Synchronisationsproblem, was
  622. man in dem Kontext finden kann. Da gibt's noch ganz andere hässliche. Ähm, eine definitive Fehlerquelle ist, dass
  623. die kooperierenden Prozesse, die also alle auf derselben Datenstruktur arbeiten, dass die alle ein bestimmtes Synchronisationsprotokoll wirklich
  624. einhalten müssen. Ja, sobald ein Prozessor irgendwie durch einen Programmierfehler z.B. aus der Reihe tanzt, ähm können trotzdem Race Racing
  625. Conditions und möglicherweise Datenkorruption eintreten. Ja, also jeder muss die Protokolle exakt anhalten. Es gibt nichts, was das
  626. erzwingt, ähm weswegen man sich eigentlich sowas wünscht wie Unterstützung durch die Programmiersprachen.
  627. Und das gucken wir uns aber das nächste Mal an, ja, das Monitor Konzept. Okay. Ähm, an der Stelle möchte ich für heute einen Strich machen. Ich schaue
  628. jetzt noch mal ein bisschen Fragen an. Ähm, wie wird festgelegt, welcher der blockierten Prozesse freigegeben wird, wenn es z.B. drei blockierte Prozesse
  629. gibt? Ja, also wir haben ähm wir haben einen kritischen Abschnitt mit der mit der mit einer Mutex, also mit einer binären Semapore abgesichert. Ähm
  630. ein einer von diesen einer von den Prozessen geht in den kritischen Abschnitt. Die Semaphore ist jetzt null und jetzt kommen noch drei andere, die
  631. auch versuchen, die Semaphore zu dekrementieren mit dem Weight oder dem P. Und jetzt verlässt der, also und diese
  632. drei Prozesse, die blockieren jetzt alle. Und jetzt verlässt der erste Prozess wieder den kritischen Abschnitt und ruft das das Signal oder das V auf
  633. der Semapore auf. Welcher von den wartenden Prozessen wird jetzt denn deblockiert? Ähm, da werden wir auch in dem in dem Rest
  634. der Vorlesung noch mal ganz kurz drüber sprechen. Äh, also nächstes Mal ähm letztendlich kann man irgendeinen Verfahren wählen.
  635. Ja, also z.B. F Kampf. So, wer zuerst blockiert hat, darf als erstes wieder deblockiert werden. Normalerweise sollte man an der Stelle
  636. versuchen, äh den zu deblockieren, der auch nach der drüber liegenden Scheduling Strategie die höhere Priorität hat. Ja, also solche ein
  637. hochpriorer Prozess sollte als erstes deblockiert werden vor einem niederprierioren Prozess. Ja, das sind z.B. für Dinge, die man da entscheiden
  638. muss. Ähm, sonst kann es passieren, dass man Entscheidungen trifft, die der der gerade aktiven Schedulingstrategie zu
  639. Wiederlaufen. So, Dextra ist nicht der redanische Geheim, weiß ich nicht. Vielleicht
  640. gibt's auch einen redanischen Geheimnischef, der Dikstra heißt. Kenne ich nicht. Ist Dextra nicht ein Algorithmus, um den
  641. kürzesten Weg in einem Grafen zu finden? Nein, Digstra ist der Informatiker, der einen Algorithmus für einen kürzesten Weg in einem Grafen
  642. vorgeschlagen hat, den man auch deswegen den Digra Algorithmus nennt, aber ähm der hat noch andere Sachen gemacht, z.B. Semmer vorn erfunden.
  643. Okay, gibt's noch weitere Fragen zum Thema Synchronisation? Ansonsten freue ich mich auf vorab oder auch währenddessen eingereichte Fragen für
  644. die Q&A Sitzung in knapp einehalb Stunden, also 15:15 Uhr geht's los. Fragen auf den üblichen Kanälen im Channel auf frag jetzt per
  645. E-Mail, per Gumakkasten, wie Sie möchten. Einer tippt noch.
  646. Einer tippt noch. Einer hat wieder aufgehört zu tippen. Dann würde ich vorschlagen, wenn Sie die Frage doch noch haben, dann
  647. stellen Sie sie in der Kund a Sitzung in knapp einerhalb Stunden. Vielen Dank. M.

Zum Nachlesen

Nicht-blockierende SynchronisationNicht-blockierende Synchronisation (englisch non-blocking oder auch lock-free synchronization) ist eine Technik in der Informatik, um parallele Prozesse zu … MutexEin kritischer Abschnitt (engl. critical section oder critical region) ist derjenige Teil im ausführbaren Code, in dem ein wegen des Mutex ungestörter … ProzesssynchronisationGemeinsamer Zugriff auf Daten. Dabei muss verhindert werden, dass durch gleichzeitigen Zugriff Inkonsistenzen in den Daten entstehen. Dies wird durch Mutex- … SpinlockEs ist eine Sperre (Lock) zum Schutz einer gemeinsam genutzten Ressource durch konkurrierende Prozesse bzw. Threads (siehe Kritischer Abschnitt) nach dem …