Vorlesung Betriebssysteme - 05 Synchronisation
Horst Schirmeier
https://www.youtube.com/watch?v=LQGon_EqOFM

Transkript (automatisch erstellt)

0:02 Ja, willkommen zurück zu Betriebssysteme. Ähm, auch heute wieder ein paar Ankündigungen,
0:09 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
0:19 mehrfachabgaben gefunden. Ja, also sprich ähm Gruppen, die scheinbar unabhängig voneinander, vielleicht auch nicht, ähm dieselben
0:29 Abgaben getätigt haben. Ähm das können wir kann ich so nicht durchgehen lassen. Also wir werden mit den betreffenden Leuten mal sprechen.
0:39 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
0:50 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
0:59 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,
1:07 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
1:14 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
1:26 die angekündigten ja Konsequenzen auch durchziehen, wenn das äh wenn es notwendig ist. Ähm ja, auch
1:36 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
1:46 wieder Fragen einreichen. Bis jetzt habe ich noch keine bekommen heute. Das ist entweder ein gutes Zeichen, weil sie alles verstanden haben, durchschauen,
1:54 was es bei um was es bei Betriebssystem geht. Ähm vielleicht ist es auch kein gutes Zeichen, ja, dass ich sie alle abgehängt
2:02 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
2:10 vorher einreichen, dann habe ich eben noch ein bisschen eine Chance, das vorzubereiten. Und jetzt mal noch was in äh
2:17 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
2:30 Konferenz, doch die glaub die Konferenz der Informatikschaften. Ähm die sollte eigentlich endlich mal wieder in Dortmund stattfinden. Das
2:37 passiert natürlich jetzt nicht, sondern sie findet im Neuland statt, um in der Formulierung der Veranstalter zu sprechen. Ähm geht am Mittwochabend los,
2:46 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.
3:01 Soweit zum organisatorischen kann man mich eigentlich verstehen. Also, der Vorlesungschatraum ist ganz ganz ruhig momentan.
3:10 Akustisch, visuell, alles in Ordnung oder auch nicht? Da kommt was. Okay, anscheinend kann man mich verstehen. Das ist schon mal hilfreich.
3:19 Okay. Ähm, soweit dazu. Letztes Mal haben wir Moment,
3:28 viel zu viele Fenster offen. Letztes Mal haben wir über Scheduling gesprochen. Ich bin etwas leise. Okay, dann schaue
3:37 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.
3:46 Man versteht es nicht. Jetzt habe ich mal den Mic Gay noch ein bisschen hochgedreht. Ja, letztes Mal haben wir über äh
3:53 Scheduling gesprochen und zunächst mal haben wir da über äh ja Abfertigungszustände gesprochen und da haben wir unter anderem letztendlich
4:01 diese Zustandsübergänge angeschaut. Ja, also es waren diese Einplanungsebenen ähm
4:09 letztendlich kurzfristig, mittelfristig und langfristig. Ja, langfristig sind ist um diese Einplanung, wann werden überhaupt Prozesse gestartet? Wann
4:17 werden sie beendet? Na, das sind Dinge, die z.B. regulär in so Rechenklustern stattfinden. Medium term oder mittelfristig sind so
4:27 Dinge wie das Einlagern und Auslagern von Prozessen. Ja, also wenn festgestellt wird, dass nicht genug Hauptspeicher da ist, dann kann es eben
4:35 kann das das Betriebssystem sich eben entscheiden oder der Scheduler sich entscheiden, einen Prozess auszulagern. Und das Short Term scheduling, das
4:43 trifft eben so Entscheidungen zwischen lauffähig, also ready tatsächlich laufend, also der hat die CPU zugeteilt bekommen oder blockiert, wenn ein
4:53 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
5:02 Scheduler tatsächlich Entscheidungen trifft. Ja, und dann haben wir uns klassische CPU Zuteilungsstrategien angeschaut.
5:13 Ä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
5:20 mit dem einfachsten Verfahren, dass man sich so wahrscheinlich vorstellen kann. erstmal äh das ist FCFS, First Come. First served
5:30 ä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
5:40 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,
5:50 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
5:59 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
6:09 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
6:18 haben will. Und dann hatten wir uns in der Folge äh das Round Robin Verfahren angeguckt, dass das eben behebt oder versucht zu
6:25 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
6:34 gesorgt wird, dass einem Prozess die CPU entzogen wird, wenn er wenn er zu lange rechnet. Da haben wir dann auch festgestellt, die
6:43 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
6:52 Restzeit in ihrer Zeitscheibe verfällt. Und dann haben wir das Virtual Round Robin Verfahren uns angeschaut, VRR, was das wiederum behebt durch eine
7:02 Vorzugsliste, ne? das Prozesse, die also vorzeitig die CPU abgegeben haben, ähm in eine Vorzugsliste kommen, die vor der normalen Bereitliste abgearbeitet wird,
7:10 wo die Prozesse den die Restlaufzeit aus ihrer letzten Zeitscheibe äh zunächst mal noch äh fertig oder weiterrechnen können.
7:20 Dann hatten wir uns noch ähm Shortest Process Next angeguckt, ähm wo letztendlich der Prozess geschul wird, der die kürzeste CPU Laaufzeit haben
7:32 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
7:41 irgendwie die Zukunft vorgreifen können, um zu wissen, welcher welcher von den von den rechenbereiten Prozessen derjenige mit der kürzesten CPU, dem
7:50 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
8:04 uns angeguckt. SRTF und HP Response Ratio Next, die letztendlich auch vorhersagebasiert arbeiten. Und last but not least hatten wir uns noch das das
8:14 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
8:25 aufbrauchen. Ja, das also sorgt dafür, dass also Prozesse mit langen CPUstößen immer weiter runter immer weiter runterwandern,
8:33 möglicherweise mal durch so eine Anti-Aging Maßnahme wieder nach oben kommen können. Und ähm
8:42 da haben wir uns im selben Kontext auch noch mal ganz kurz über Prioritäten unterhalten, ja, unterschieden zwischen statischen und dynamischen Prioritäten.
8:48 Ä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
8:59 Verfahren Shortest Process Next, STF, HRN und Feedback waren eben Spezialfälle, die eben äh zur Laufzeit äh die Prioritäten von Prozessen
9:07 anpassen. Also bei Feedback z.B. wie eben die Prozesse, die sehr CPU lastig sind, die werden letztendlich kontinuierlich äh weiter in der
9:14 Priorität abgesenkt und hatten uns dann am Schluss noch angeschaut Multilevel Scheduling ähm was äh ja das Ganze noch ein bisschen
9:25 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
9:33 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
9:40 Priorität bekommen haben, die Studentenprozesse, die die niedrigste haben. Beim normalen Multilevel Scheduling ist zunächst mal kein
9:47 Feedback vorgesehen, also spricht, dass ein Prozess seine Priorität wechselt. Ähm ja, das heißt also ein niederpriorer Studentenprozess bleibt auch
9:55 niederprior, ein hochpriorer Systemprozess bleibt hochprior. Das kann man aber auch noch kombinieren und dann hat man multilevel Feedback. Ja, und das
10:03 ist ein sehr allgemeines Verfahren, wo man letztendlich auch auf jeder Ebene entscheiden kann, nach welchem Scheduling Verfahren wird hier äh
10:09 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
10:16 geschoben werden. Dann hatten wir kurz über äh Bewertungskriterien gesprochen, also welche
10:25 Ziele äh bei einem bei einem äh Scheduling äh Verfahren ähm ja durchgesetzt werden sollen. Da haben wir Unterschieden zwischen benutzerentierten
10:35 und systemorientierten Zielen oder Bewertungskriterien, die jeweils für völlig unterschiedliche Anwendungszwecke sinnvoll sind.
10:46 Ä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
10:53 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
11:03 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
11:11 Windows und ähm dann gucken wir mal, ob es zum zu diesem Vorhinsatz noch Fragen gibt. Ähm
11:20 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
11:29 gehe gleich drauf ein. Ja, Windows äh Art macht natürlich auch Scheduling. Ja, seit Windows int ähm gibt's Prioritätsklassen
11:40 und ähm da werden letztendlich wird auch letztendlich Präumtion benutzt. Ja, also präumtive
11:48 ä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
11:59 Kern ist. Ja, also selbst ein Betriebssystem eigener Thread, der wirklich Betriebssystem interne Dinge tut, kann
12:06 verdrängt werden. Ja, bei Unix ist das klassischerweise nicht der Fall gewesen. Ähm, prioritätsbasiert, ja, das heiß, wir
12:16 haben Prioritätsebenen, in dem Fall von 0 bis 31 und wenn wenn man zwei Prozesse oder zwei Threats hat, die auf derselben
12:22 Prioritätsebene sind, dann wird Round Robin gemacht. Ja, die waren also rei um äh dran genommen und haben eine Zeitscheibe
12:30 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
12:39 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
12:46 Echtzeitprioritäten. Ähm, so und dann gibt es bei Windows eben so
12:54 ä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,
13:06 wie groß das Zeitquantum, also die Zeitscheibe äh eines Threads ist. Ja, also ob es ein Vordergrundthreat ist oder ein Hintergrundthread. Ja, also ist
13:14 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
13:23 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
13:34 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
13:48 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
13:57 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
14:07 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
14:15 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
14:24 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,
14:32 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
14:40 relative Priorität haben, plus minus irgendwie irgendeine Konstante und dann kommt noch ein sogenannter Boost dazu. Ja, der Boost
14:51 ä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
15:00 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
15:08 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
15:17 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.
15:26 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
15:37 um 6 angehoben. Ja, das heißt, also wenn Sie irgendwann mal ganz äh ganz dringend auf das Fertigstellen von irgendeiner
15:45 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
15:53 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
16:00 angehoben, wenn äh wenn er Eingaben vom Nutzer bekommt. Ja, und es gibt noch weitere Ereignisse, die die das die das also verursachen
16:09 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
16:17 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,
16:26 wieder weg. Und eine weitere Sache ähm macht Windows noch beim beim Scheduling, nämlich es liefert eine sogenannte
16:34 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
16:43 benachteiligte äh Threats für zwei Zeitscheiben noch ordentlich angehoben ähm auf die höchste variable Priorität, ja, aus diesen variablen Prioritäens
16:53 Spektrum. Und ähm das führt dazu, dass äh das letztendlich das Aushungern verhindert wird.
17:04 Ja, und man sieht bei Windows ähm da wurde letztendlich wahrscheinlich auch eine Menge äh Forschung betrieben mit Nutzern, die also beobachtet wurden,
17:14 wie sich wie wie sie letztendlich auf das Systemverhalten so ansprechen und entsprechend wurde ähm wurde dieses Scheduling, diese Scheduling Horistik
17:22 hier so angepasst, dass sich das System eben ein bisschen interaktiver anfühlt. zusammenfassend zum Thema Scheduling. Ja, also wir hatten diese drei diese
17:32 drei äh ähm na ab diese drei Einplanungsebenen gesehen, also langfristig, mittelfristig, kurzfristig
17:40 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
17:50 Benutzer und systemorientierte Kriterien gesehen, wie man diese Verfahren beurteilen kann und welches Verfahren letztendlich das Beste ist für ihren
17:58 Anwendungsfall, für ihren Rechner, der möglicherweise irgendwie in eingebetteten System äh sitzt und irgendwie mit z.B. mit der mit der
18:05 physikalischen Umgebung irgendwie interagieren muss. Ähm, das kommt letztendlich darauf an, was der Uscase genau ist. Ja, und das kann sich sehr
18:13 stark dann unterscheiden, wie die wie die Leistung unterm Strich dann ist. So, jetzt schauen wir mal, ob es Fragen gibt.
18:22 Ähm, wenn die Prozesse dem Scheduler mitteilen, wie lange ihre Bedienzeit sein soll, warum müssen wir noch die
18:32 voraussichtliche Laufzeit vorhersagen? Der Prozess sagt uns ja schon, wie lange er laufen will bei einigen Scheduling Methoden. Also, das Prozesse dem
18:41 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.
18:47 Ähm, das einzige Beispiel, wo wir eben nicht vorhersagen müssen, z.B. durch dieses äh durch diese
18:56 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
19:04 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
19:11 der ein Tag? Das muss man muss man da ankündigen. Und nachdem dieses Zeitfenster dann abgelaufen ist, wird der Prozess auch wirklich weggeschossen
19:20 von dem System. Ja, das ist aber, würde ich jetzt mal sagen, nicht der Regelfall. Im Regelfall ähm muss letztendlich der Scheduler eine
19:30 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
19:37 aus den Beobachtungen, aus den letzten Endbeobachtungen die nächste ähm Zeitscheibenlänge oder ne die letzte nächste CPU Burst Länge vorhersagen.
19:49 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.
19:59 Ähm, na, nicht ganz beim Echtzeitscheduling äh die Echtzeit, diese Echtzeitklasse, also
20:09 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
20:17 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
20:24 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
20:35 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
20:44 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
20:51 nach. Gibt es da denn jetzt ein besser oder schlechter, was das Scheduling in Unix
21:02 und Windows angeht? ähm bestimmt. Also letztendlich ähm kommt es auf ihren
21:11 Anwendungsfall an. Ja, also ich denke, dass Microsoft da schon sehr viel Zeit investiert hat, um dieses diese Geschichte z.B. mit diesem Dynamic
21:20 Dynamic Boost ähm so lange zu optimieren, bis sich das eben für den Normalnutzer besonders fluffig anfühlt.
21:28 Ä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
21:35 so ein Unix, Linux, sonst wie Scheduler, ähm einfach bezüglich eines anderen äh Benutzer oder auch systemorientierten Kriteriums ja einfach besser aussieht.
21:47 Ja, also wie wie so oft muss man hier sagen, kommt drauf an, was ihr Anwendungsfall ist.
21:57 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
22:04 Prozessorgeschwindigkeit, die Anzahl der Kerne und so weiter an. Ähm, na ja, letztendlich ist das eine Schätzung, die der Nutzer hier ähm hier
22:13 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.
22:24 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
22:31 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
22:39 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
22:49 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
22:57 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.
23:06 Ja, wenn man überabschätzt, äh ja, überabschätzen ist mal die sicherere Sache, da wird der Prozess nicht
23:14 vorzeitig weggeschossen. Hat aber den Nachteil, dass in der in der Regel langlaufende oder Prozesse, bei denen der Nutzer ankündigt, dass die
23:23 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,
23:30 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,
23:38 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
23:44 Regel sofort dran. Ja, also das ist ein Üste ist tatsächlich ein Problem. Letztendlich kann man nur messen und hoffen.
23:55 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
24:05 irgendeinen Unsinn gemacht habe mit meinem Ja, ich verstehe jetzt auch, was das Problem ist.
24:14 So, jetzt hoffe ich mal, der Ton ist besser geworden. Schauen mal, ob der Turm besser geworden ist. Bei mir ist alles okay. Eigentlich
24:25 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
24:34 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.
24:46 Ähm ja, so viel zum Thema Scheduling. Ähm heute machen wir weiter mit ähm ja letztendlich dem, was darauf
24:59 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
25:08 synchronisieren muss. Deswegen ist das Thema der heutigen Vorlesung Synchronisation.
25:14 Ä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
25:21 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
25:32 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
25:42 gehört hat? Vielleicht was ist der Nachteil davon, wenn man das so tut. Ähm, dann w wir uns über Hardwareunterstützung zur
25:47 Synchronisation unterhalten. Es ist wieder leise geworden. Weiß ich doch. Be Absicht. Ich mach's noch mal lauter. So.
26:00 Ähm, Betriebssystem Unterstützung ähm für Synchronisation unterhalten und am Schluss über Sprachunterstützung. Ähm, ja, Prozesse sind Programme in
26:09 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
26:21 konzeptionell sind es wirklich komplett nebenläufige Kontrollflüsse äh die so aus aus Nutzersicht auch wirklich gleichzeitig laufen, was sie natürlich
26:30 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
26:39 Schedeling Verfahren entscheidet also wann wird ein Prozess verdrängt und ähm in welcher Reihenfolge kommen die die lauffähigen Prozesse dran. Ja, in
26:48 welcher Reihenfolge werden die ausgeführt? Prozesse haben einen Adressraum. Ja, über logische und physische Adressen werden wir uns später
26:54 noch unterhalten. Logische Adressen werden durch die Hardware let durch die durch die Memory Management Unit auf physische Speicheradressen abgebildet.
27:03 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
27:10 und vor allem Datenbereiche teilen. Ja, also bei leicht und viertergewichtigen Prozessen hatten wir schon gesehen, die teilen sich denselben Adressraum, die
27:17 können auf denselben Datenstrukturen arbeiten. Ähm und das Betriebssystem kann mit Hilfe der MMU, ja, das ist wieder auf
27:26 der technischen Ebene, ähm einen Speicherbereich mehrere Adressräume einblenden. Ja, was dafür sorgt, dass wirklich zwei auch Prozesse, auch zwei
27:35 schwägewichtige Prozesse ähm auf demselben Speicher, auf den selben Datenstrukturen arbeiten können. Ja, und auch im Betriebssystem selbst werden
27:45 Daten, Strukturen, Daten geteilt. Ja, das gucken wir uns auch später noch mal an. Ähm, ja, was ist das Problem? Jetzt
27:53 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
28:01 ist. Ähm ist aber keine Raketenwissenschaft. Ich werde es mal kurz versuchen zu erklären. Ähm wir wollen eine verkettete Liste in C
28:10 implementieren. Ja, also haben wir ein Struct element, wo also das das letztendlich die die Datastruktur für ein einzelnes Element
28:18 in dieser Dataststruktur ist. Jedes Element hat eine Payload. Ja, in diesem Fall jetzt einfach ein Character, das könnte aber auch irgendwas komplexeres
28:25 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
28:34 so ist bei einer verketteten Liste, einen Nextzeiger auf das nächste Element ähm in unserer Liste. So, die eigentliche Liste ähm besteht
28:45 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.
28:55 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
29:05 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
29:18 den Nextiger im letzten Element. So, warum das so ist, werden wir gleich an dem Beispiel bisschen sehen. Letztendlich sorgt dieser Kniff dafür,
29:27 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
29:35 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
29:44 unten ein bisschen komplexer. ist jetzt vielleicht äh für das eigentliche zu zeigende Problem
29:53 gar nicht so relevant. Ähm, letztendlich ist aber das die Implementierung, die ich jetzt in diesem Beispiel hier zeigen werde.
29:59 Ähm, so, das ist die also die Implementierung von der Funktion oder man könnte jetzt sagen, wenn man so objektorientiert das Ganze betrachtet,
30:07 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
30:18 Element Item ein. Ja, und dazu werden diese drei Schritte hier durchgeführt. Das gucken wir uns jetzt gleich mal in dem Beispiel an.
30:26 Ä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
30:40 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
30:50 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
31:02 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
31:10 ganzen Listenelementobjekte äh die liegen alle im in dem gemeinsamen Adressraum. Was man jetzt hier sieht, ist die leere
31:18 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.
31:29 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
31:42 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
31:49 Elementobjekte hier ähm die haben hier schon mal in dem in diese diesen Payload jeweils ein ein Zeichen eingetragen bekommen und ihr jeweiligen Nextiger,
31:58 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
32:09 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
32:19 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
32:27 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
32:35 momentan noch nicht initialisiert ist, dass der mit Nalle initialisiert wird. Ja, das Ding wird jetzt mit Nalle initialisiert. Das tut diese Zuweisung
32:44 hier. So, es gab eine Zwischenfrage, die wurde gleich wieder gelöscht. Ich vermute mal, ich habe es ja einfach
32:51 mal schon beantwortet. Ähm, so was passiert jetzt hier in diesem zweiten Schritt? Also, hier wird
32:59 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
33:09 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,
33:17 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
33:26 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.
33:38 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
33:50 soll jetzt [räuspern] zeigen auf den Next Zeiger von unserem Item. Ja, also der wird jetzt umgebogen von hier nach da.
34:02 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
34:12 auf das erste Element. Der Tailpointer zeigt auf den Next Pointer von dem letzten Element in unserer Liste, was gleichzeitig auch das
34:21 erste Element ist. So, und jetzt kommt hier das äh das zweite NQ. Ja, das habe ich jetzt hier
34:29 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
34:35 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
34:48 enced wurden. So, das ist auch völlig richtig. So, so muss das aussehen, wenn das äh wenn das wenn das
34:57 wenn die beiden fertig encute sind. Jetzt ist aber die Frage, was passiert, wenn diese beiden Threads ja ungünstig äh umgeschaltet werden? Ja,
35:07 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
35:14 irgendein PR prämitives Scheduling Verfahren, Robin z.B. und das sorgt dafür, dass an dieser Stelle hier ein Prozesswechsel stattfindet. Ja, also
35:23 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
35:31 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
35:40 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
35:48 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
35:56 wird auf Nah gesetzt. Ja, und der ähm na also List Tail zeigt hierhin und das wird gesetzt auf Item. Also es wird
36:09 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
36:17 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
36:26 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
36:34 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
36:43 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
36:51 läuft. Was passiert jetzt? Ja, es wird wieder List Tail genommen, ne? List Tail ist dieser Zeiger hier. Den wird mit dem Sternchenoperator
37:02 wird das wird dieser Zeiger dereferziert. Wir folgen also dem Zeiger dorthin, wo er hinzeigt. Und das wird gesetzt auf Item. Das heißt
37:09 also dieser Zeiger hier wird übermalt durch einen Zeiger, der auch dieses Item hier zeigt. Und dann wird list tail, das ist dieser
37:18 Zeiger hier wird gesetzt auf den Next Zeiger von dem Element 2. Ja, jetzt sind wir hier und wir sehen also das Zwischenergebnis
37:30 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
37:39 ist nur Element 2 eingehängt. Element 1 ist nicht mehr eingehängt. So, jetzt passiert wieder Prozesswechsel. Wir wechseln also zurück
37:46 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
37:53 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
38:04 hier drauf. Ja. Und jetzt haben wir eine Listenatenstruktur, die völlig kaputt ist. Ja, also das ist keine gültige
38:15 Liste mehr. Ja, die Liste ist so, wenn wir jetzt auf dieser Liste irgendwie weiterarbeiten, ähm dann werden wir je nachdem, was wir
38:23 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
38:32 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
38:39 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
38:47 Tailpointer angehängt. Ja, die hängen also dann alle letztendlich direkt oder indirekt an diesen Zeiger hier dran und ähm
38:57 die gehen verloren. Ja, also die sehen wir nicht mehr, wenn wir über die Liste eterieren. Ja, also kaputte Datenstruktur irgendwie schlecht.
39:06 Ä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.
39:14 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
39:24 ist ein allgemeines Problem. Ja, wo gibt's das sonst noch? Ja, also gemeinsamer Speicher, also Shared Memory
39:34 ähm z.B. Ne, da könnt da können wirklich schwergewichtige Prozesse sich Speicher teilen. Da kann man den selben Speicher
39:42 in in zwei schwergewichtige Prozesse einblenden und dort drin gemeinsame Datenstrukturen ablegen. Ja, das Beispiel, das wir jetzt gerade
39:51 gesehen haben, das würde jetzt am ehesten noch so einem leichtgewichtigen Prozess, also einem Thread entsprechen, ja, wo letztendlich einfach nebenläufig
39:57 auf Variablen, auf dieselben Variablen zugegriffen wird. Ähm, im Betriebssystem selbst kann das passieren, ja, Betriebssystematen äh die
40:06 gebraucht werden, um den Zugriff von Prozessen auf unteilbare Betriebsmittel zu koordinieren. Also um z.B. ähm Operation auf äh Dateisystemstrukturen
40:15 zu machen. Ja, das Dateisystem ist eine geteilte Ressource, die letztendlich alle Prozesse sich teilen. Ja, Operation auf der Prozessstabelle,
40:23 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
40:32 den Zugriff darauf irgendwie koordinieren. Ja. Ähm, kleiner Vorg auf eine Masterveranstaltung, Betriebssystembau, ja, da kommt kommt
40:44 man letztendlich auch auf ein ähnliches Problem, nämlich das der Unterbrechungssynchronisation. Ähm, wenn also eine Unterbrechung
40:50 auftritt, dann kann das kann natürlich auch diese Unterbrechungsbehandlung auf Datenstrukturen arbeiten, äh auf den andere äh Kontrollfüße auch gerade
40:59 arbeiten. Ja, wobei die Verfahren, die wir jetzt jetzt angucken, nicht notwendigerweise auch bei Unterbrechungen funktionieren. Ja, das
41:05 nur so als Randnotiz. Ja, was sehen wir hier eigentlich? Das ist eine sogenannte Race Condition, ja,
41:14 oder die halbgare Übersetzung Wettlaufsituation. Ja. Ähm, was ist eine Race condition? Das ist
41:22 das ist noch nicht der Fall, wo wirklich ein Problem auftritt. Also eine Race Condition ist einfach nur eine Situation, wo mehrere Prozesse
41:30 konkurrierend auf dieselben Daten zugreifen. Ja, und mindestens einer dieser dieser Prozesse manipuliert diese Daten auch.
41:39 ähm und welchen Wert diese gemeinsamen Daten letztendlich haben, das kommt das das kommt bei einer Racing Condition darauf an, in welcher Reihenfolge die
41:47 Prozesse zugreifen. Ja, welches Ergebnis letztendlich dabei rauskommt, ist im allgemeinen erstmal nicht vorhersagbar und kann, wie wir
41:56 jetzt in dem Beispiel gerade gesehen haben, kann aber muss nicht, kann ähm bei überlappenden Zugriffen sogar inkorrekt sein. Ja, also in dem Beispiel
42:04 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
42:14 Ü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
42:21 dafür gesorgt, dass die Datenstruktur ähm ja defekt war hinterher. So. Und was kann man tun, um Race Conditions zu vermeiden?
42:31 Man muss synchronisieren. Ja, die konkurrentenprozesse müssen synchronisiert werden. So, was heißt synchronisieren?
42:39 Synchronisation ist die Koordination der Kooperation und Konkurrenz zwischen Prozessen. Ja, das ist also die Definition aus äh aus so einem
42:48 klassischen äh Nebenläufigkeitsbuch. Ja, Hertwig Hommel. Ähm, Synchronisation bringt die Aktivitäten
42:57 verschiedener nebenläufiger Prozesse in eine Reihenfolge. Ja. Ähm, man sorgt also dafür, dass obwohl
43:06 diese Prozesse konkurrierend nebenläufig auf diesen Datenstrukturen arbeiten wollen, sorgt man dafür, dass dass diese Operationen in eine definierte
43:16 Reihenfolge gebracht werden. Und durch diese Synchronisation sorgt man also prozessübergreifend dafür, was innerhalb eines Prozesses einfach
43:25 dadurch erledigt wird, äh dass bestimmte Datenstrukturzugriffe im weiteren Sinne Aktivitäten ohnehin sequenziell sind. Ja, also wenn man innerhalb eines eines
43:35 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,
43:45 da können keine Race conditions auftreten. Wenn man das aber Prozess übergreifend haben möchte, muss man synchronisieren.
43:56 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.
44:04 Ä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,
44:13 um den Zugriff auf gemeinsame Daten. Und ähm dieser Zugriff, der passiert durch der Regel nicht besonders lange Codefragmente, Codeabschnitte. Ja, also
44:24 in dem in unserem Fall waren das ein paar wenige Zeilen in dieser NQ Funktion, ja, die letztendlich wirklich auf die
44:31 Datenstruktur zugegriffen haben und deren Zugriffe dafür gesorgt haben, dass eine Race Condition auftritt und diese Codefragmente nennt man
44:40 kritische Abschnitte. Ja, und was man letztendlich die Synchronisation sicherstellen möchte, ist, dass sich immer nur ein Prozess von
44:50 unseren Prozessen, die sich hier streiten, äh in seinem kritischen Abschnitt oder in einem kritischen Abschnitt aufhält oder und aufhalten
44:58 kann. Ja, man muss das erzwingen. So, und jetzt gucken wir uns mal an, wie geht das eigentlich?
45:10 Ja. Ähm Lösungsansatz ist äh mit die ist ist das Einführen einer sogenannten Schlossvariablen.
45:21 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.
45:30 Und dieser abstrakte Datentyp, der hat zwei Operationen, Acquire und Release. Ja, wie die letztendlich heißen, ist ist jetzt nicht so wichtig, aber
45:38 letztendlich dieses dieses Aquired, das verschließt ein Schloss und das Release äh öffnet das Schloss wieder. Dieses Aquire hat noch eine zusätzliche
45:50 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
46:00 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
46:08 Abschnitt wird dieses Schloss wieder freigegeben, ja, oder geöffnet, ohne dass irgendjemand weiterhin verzögert wird.
46:15 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.
46:23 Da gibt's verschiedene Möglichkeiten. Allgemein nennt man solche Implementierungen dieses dieser dieser Schlossvariablen Schlossalgorithmen.
46:35 Ja. So. Was hat Log denn für ein Basisdatentyp? Wie gesagt, das ist ein abstrakter Datentyp. Das das ist
46:44 letztendlich die Basisklasse, würde ich jetzt mal sagen. Ja, also die Basisklasse aller Schlossalgorithmen heißt jetzt in unserem Kontext hier
46:51 erstmal log. So, jetzt entferne ich mal wieder ein bisschen Dinge aus dem Frag jetzt.
47:05 Okay. Ähm, wie kann man jetzt letztendlich so ein Schlossalgorithmus tatsächlich konkret bauen?
47:14 Ä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.
47:25 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
47:35 einsign. Ja, also in in C kann man mit Typed einen Datentyp neuen Datentyp anlegen und quasi den als Alias für einen
47:44 anderen Datentyp anlegen. Letztendlich entspricht log einfach uns car, also einem vorzeichenlosen 8 Bit Integer vereinfacht gesagt.
47:55 So und was macht das Aququire? Das Aquirer kriegt einen Pointer auf so einen Char übergeben. Ja, ich das Logobjekt übergeben.
48:06 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
48:13 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
48:20 bisschen offensichtlicher wird, dass es also eine Schleife ist, die in ihrem Rumpf überhaupt nichts tut, sondern einfach nur wiederholt diese Bedingung
48:28 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
48:42 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
48:54 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
49:06 hier ungleich null ist. Ja. Oder anders gesagt, diese Schleife wartet so lange, bis log den Wert null hat.
49:17 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.
49:25 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
49:37 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,
49:47 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.
49:55 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
50:04 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
50:11 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
50:20 schon mal ganz groß in rot über diese Folie falsch. Das ist die spannende Frage, warum steht da falsch ist.
50:30 Ähm, so es gibt's ja schon ein paar Kommentare. Also zum einen, wie rechenintensiv ist die Schleife ohne Inhalt, wenn diese permanent
50:37 weiterläuft? Ja, das ist auf jeden Fall Nachteil. Die ist die ist ziemlich rechenintensiv, ne? So, die die führt
50:46 kontinuierlich CPU Instruktionen aus. Ja, da wird also wird keine Rechenzeit irgendwie an irgendjemand anders
50:53 abgegeben. Also ist erstmal Rechenzeitverschwendung, könnte man sagen. Ähm,
51:01 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
51:07 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
51:16 Sie das mal konkretisieren? Also was muss denn passieren, dass zwei Threads das gleichzeitig tun? Wirklich gleichzeitig gibt's bei uns ja nicht.
51:26 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
51:38 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.
51:51 Ja, Vorschläge. [seufzt] Genau. Ja, hier kommt der Vorschlag. Wird nach der nach der
52:03 Wildschleife unterbrochen. Ja, also wir haben diese Wildschleife. Wir stellen fest, aha, log ist null. Juhu,
52:11 wir können das Log jetzt nehmen. Die While Schleife wird verlassen. Jetzt befinden wir uns hier und jetzt findet ein Prozesswechsel statt.
52:20 Jetzt kommt ein anderer Prozess, ruft auch das Aququire auf. Stellt fest, aha, log ist null. Juhu, ich kann das Log nehmen. Geht hierhin,
52:30 setzt log auf 1, betritt den kritischen Abschnitt, tut irgendwelche Dinge auf unserer geteilten Q und so weiter. Irgendwann passiert wieder ein
52:39 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
52:48 anderen Prozess. wieder die ein zu. Jetzt haben wir zweimal zwei Prozesse, die dem Log eine ein zugewiesen haben und beide gehen
52:55 jetzt in ihren kritischen Abschnitt. Ja, das genau das, was wir verhindern wollten. So, also was ist das Problem?
53:04 Der kritische Abschnitt, den wir sichern, also der kritische Abschnitt, den wir sichern wollen, äh ist ist kritisch, aber das Aquirer selbst ist
53:12 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
53:21 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
53:32 noch mehr Prozesse, diesen eigentlich durch Aquire oder letztendlich durch unser Log gesicherten kritischen Abschnitt äh überlappt ausführen. Ja,
53:41 also genau das, was wir verhindern wollten. Und ähm die, sag mal, die klassische Lösung zunächst mal aus algorithmischer
53:51 Sicht ist der sogenannte Bäckereialgorithmus. Ähm, wir werden auch gleich noch ganz kurzen Blick auf eine mögliche
53:57 Implementierung werfen. Die den werde ich jetzt aber nicht vertiefen. Ähm, zunächst mal auf abstrakter Ebene ähm bekommt einen Prozess, der einen
54:05 kritischen Abschnitt betreten will, eine Warteummer. Ja, der wie sich wie man sich das beim Amt vorstellen kann. Man zieht eine Nummer
54:14 und dann erfordert erfolgt die Zulassung in den kritischen Abschnitt in der Reihenfolge der Nummern. Ja, so wie man sich das halte vom Amt
54:22 vorstellt. Das heiß, wenn der kritische Abschnitt frei ist, dann darf der Prozess mit der niedrigsten Warenummer
54:30 den kritischen Abschnitt betreten. Ja, und wenn der kritische Abschnitt wieder verlassen wird, dann wird die Wartenummer weggeschmissen. Ja, im
54:37 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.
54:45 Ä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
54:51 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
54:59 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
55:07 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
55:16 Warenummer darf als erstes. So, ich gehe gleich noch auf die Fragen ein.
55:27 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
55:35 diese Logstruktur ein bisschen komplexer. Da gibt es also ein booli array choosing der Größe N. Ja, wir nehmen
55:42 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
55:52 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
56:01 letztendlich verwendet, um zu synchronisieren. Und das Aququire sieht so aus, dieses in dem I landet die aktuelle Prozess ID.
56:08 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
56:18 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
56:24 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
56:35 Prozesse und die Warteummer, die hier gezogen wird, ist das Maximum aus allen Wartenummern, die bis jetzt hier
56:44 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
56:54 Zeile, wo es passieren kann, dass ähm dass mehrere Prozesse hier ähm in dieses Number Array dieselbe Warteummer eintragen. Ja, weil dieser Abschnitt
57:07 hier eben nicht synchronisiert ist. Ja, also es kann passieren, dass hier mehrere Prozesse gleichzeitig diese dieses Maximum hier ausrechnen, eins
57:15 drauf addieren und es kommt dann dieselbe äh dieselbe Wartenummer raus. Ähm, das löst sich aber gleich eben durch diese weitere Priorisierung durch
57:24 die Prozess ID. Was wird hier unten gemacht? Hier wird letztendlich komm über das dieses komplette Choosing und das komplette Number Array gelaufen,
57:32 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
57:40 übersehen. Ähm und jetzt wird erstmal gewartet, bis keiner mehr in keiner mehr gerade beim Auswählen einer Warenummer ist. beim Ziehen einer Warenummer.
57:52 Ja, und dann wird letztendlich ähm Nein, Unsinn. Es wird jetzt erstmal geguckt, dass der der Prozess äh mit der
58:02 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
58:12 eingetragen hat, dann wartet dieser Prozess gerade sowieso nicht. Wenn er wartet, dann wird geguckt, ist äh die Wartenummer von dem Konkurrenten kleiner
58:21 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
58:29 steckt drin, ich dieser Schlossalgorithmus äh di dieses dieser Bäckereialgorithmus, der wartet hier in einer in einer Whitechleife, die
58:37 sonst nichts tut, solange dieser Konkurrent hier eine kleinere Warenummer hat. Ja, und wenn man sich das Verfahren
58:46 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
58:56 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
59:06 den äh den kritischen Abschnitt betreten. Ja, und bei dem Release wird jetzt endlich einfach in die in dieses in
59:14 dieses Number Feld hier wieder eine Null eingetragen, ne? Das ist das das bildliche Wegwerfen von dem von dieser ähm
59:21 von der Warteummer. So. Und dieser Algorithmus ähm der funktioniert. Ja, das kann man auch
59:29 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
59:38 Eintritt in diesem kritischen Abschnitt konkurrieren werden. Also dieses groß n äh liegt in der Regel nicht fest. Ja, Prozess IDs liegen normalerweise auch
59:46 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
59:53 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
1:00:01 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
1:00:11 betreten darf. Und ähm diese Funktion Aquire hat äh auch eine eine Laufzeit, die linear mit der Anzahl der beteiligten Prozesse ist.
1:00:21 Ja, also O von N, selbst wenn gerade überhaupt kein anderer Prozess im kritischen Abschnitt ist, selbst wenn, also der kritische Abschnitt gerade
1:00:28 komplett frei ist. Okay, was man jetzt hier eigentlich haben wollen würde, wäre also ein Algorithmus,
1:00:37 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
1:00:48 einfach wie der naive Ansatz, ja, das was wir vorhin gesehen haben, diese Schleife, die letztendlich selber kritisch war. Ja, das wäre eigentlich
1:00:54 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.
1:01:03 Ä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,
1:01:15 heißt das Windows unterstützt das gar nicht. Also ähm bin jetzt kein regulärer Windows User äh
1:01:25 wenn man eine Datei geöffnet hat mit einem Programm, dann kann es natürlich sein, dass dieses Programm dem Betriebssystem irgendwie signalisiert,
1:01:32 ich habe jetzt hier meine meine Clown auf dieser Datei. Ja, und das andere Programme diese Datei deswegen dann gar nicht öffnen wollen. Ähm,
1:01:42 prinzipiell könnten sich Programme genauso unter Windows natürlich äh beliebig synchronisieren und auch gleichzeitig z.B. auf dem auf derselben
1:01:50 PDF-Datei arbeiten. Ja, das ist aber nicht so ohne weiteres äh immer möglich, ne? je nachdem, welche Operation auf dieser
1:01:58 PDFdatei passieren sollen. So. Ähm, jetzt gibt's hier die Frage, ich verstehe noch nicht wirklich, warum
1:02:07 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
1:02:16 hier, warum warum diese Wchleife nicht in einer Endlosschleife endet. Ähm, na, diese Weschleife beendet endet
1:02:27 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
1:02:40 in einer Bedingung als falsch, wenn es null ist. Ja, das heißt also sobald ein anderer Prozess herkommt und dieses Log auf null
1:02:50 setzt, wird diese Bedingung hier falsch und die Schleife wird verlassen. Ja, das muss keine Schleife sein. Natürlich, wenn man jetzt nur lokal
1:02:59 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
1:03:07 wenn diese Bedingung einmal wahr ist, dann gibt es erstmal keine keine ersichtliche Codstelle, die die äh die Wahrheit dieser Bedingung
1:03:16 ä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
1:03:25 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
1:03:32 Wchleife wartet, der kann dann der verlässt dann diese White Schleife, sobald er wieder äh rechnen darf.
1:03:43 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
1:03:52 sogar dasselbe, vermute ich mal ganz stark. Ja, also auch ein Boolian ist klassischerweise in C ein 8 Bit Integer, aber
1:04:01 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
1:04:12 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
1:04:20 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
1:04:29 Nebenläufigkeit. Ja, weil letztendlich muss man dann z.B. die Betriebssystemstellen dafür verwenden, die die für die
1:04:36 Synchronisation da sind. Die gucken wir uns dann gleich an. Wie wahrscheinlich ist der Fall, dass zwei Prozesse Log auf ein setzen?
1:04:44 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
1:04:52 ü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
1:05:01 einer Endoschleife Acquire release Acquire release acquire release machen, dann wird's relativ wahrscheinlich. Ja, dann wird das innerhalb von ein paar
1:05:08 Millisekunden tatsächlich auch passieren. Ähm, wenn Sie äh Prozesse haben, die nur sehr selten mal einen kritischen Abschnitt ausführen, dann
1:05:17 wird das halt Größenordnungen unwahrscheinlicher. Das ist auch richtig gemein. Ja, dann haben sie also einen fiesen äh Synchronisationsfehler,
1:05:24 Synchronisationsbug in ihrem Code, den sie aber bei durch Testen möglicherweise gar nicht finden, sondern das passiert, der tritt dann erst in 10
1:05:32 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
1:05:44 Fall eintritt, desto hässlicher ist dieser Bug eigentlich, weil irgendwann passiert doch mal und kann dann natürlich beliebige Resultate haben,
1:05:51 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
1:06:00 und das Flugzeug deswegen vom Himmel fällt, werden die Arrays dann beim Bäckereialgorithmus unendlich groß? Ähm
1:06:08 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
1:06:16 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
1:06:23 C-Standard irgendwas vorschreibt. Äh letztendlich wird das in der Regel daran scheitern, äh wie groß ihr Hauptspeicher ist und oder der Stack
1:06:32 ist, z.B. Ja, aber ich ich wäre jetzt ich wüsste jetzt keine keine Limitierung, die der CSstandard vorschreibt.
1:06:44 Okay, Bäckereialgorithmus. Ähm, jetzt gucken wir uns mal andere Lösungen an. Ja, also aktives Warten ist
1:06:54 ä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
1:07:01 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
1:07:10 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
1:07:19 Abschnitt reinkommen. Ja, und dafür gibt's Hardware Unterstützung. Ähm, die einfachste oder vermeintlich einfachste Möglichkeit ist einfach Unterbrechungen
1:07:28 ausschalten, Unterbrechungen unterdrücken. Ja, allein der Unterbrechungsmechanismus in der CPU sorgt dafür, dass der CPU
1:07:38 innerhalb des kritischen Abschnitts die CPU entzogen werden kann. Also z.B. wenn der Timerbaustein eine Interrupt auslöst und damit dem Scheduler signalisiert,
1:07:46 die Zeitscheibe von dem gerade laufenden Prozess ist abgelaufen. Scheduler entscheidet jetzt, es kommt jetzt ein anderer Prozess dran und macht ein
1:07:54 Kontextwechsel. Das ist die eigentliche der ist der einzige Grund, der dazu führen kann, dass also äh ja hinterher unsere
1:08:02 Datruktur kaputt gehen kann durch eine Race Condition. Ähm und das kann ich zunächst mal ganz einfach verhindern, indem ich halt bei
1:08:10 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
1:08:19 Interrupts wieder ein. Ganz einfach. Oder me eine Idee, warum das vielleicht eine dumme Idee ist?
1:08:28 Vorschläge, warum das warum man das vielleicht nicht machen sollte. gibt letztendlich zwei gute Gründe.
1:08:53 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
1:09:01 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
1:09:09 mehr entzogen, zumindest nicht durch ein Timer Interrupt, der das Zeitscheibenende signalisiert. Ja, also plötzlich können Prozesse auch in dem
1:09:19 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
1:09:28 keine anderen Interrupts durchkommen. Also z.B. auch keine Tastatur äh Tasten keine Tastendrücke, Mausbewegungen, sonst wie. Ja, die werden alle nicht
1:09:35 mehr ans Betriebssystem zugestellt, weil die alle letztendlich interupt getrieben arbeiten.
1:09:43 Ähm, wenn das Programm selbst ein Interrupt aufruft, ja, Programme können kein Interrupt aufrufen in dem Sinn,
1:09:51 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,
1:10:00 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.
1:10:08 Nutzer Interaktion sind nicht mehr möglich. Genau. Tastatur Maus geht nicht mehr. Eingabe Ausgabegeräte tun nichts mehr.
1:10:15 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
1:10:22 normales Anmeldungsprogramm darf diese beiden Instruktionen gar nicht ausführen. Ja, das ist wieder die Trennung zwischen äh zwischen
1:10:31 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
1:10:40 einfach nicht erlaubt. Genau aus dem Grund oder aus den gerade genannten Gründen. Ähm ja und letztendlich ähm wird eben
1:10:50 letztendlich das komplette Betriebssystem, alle anderen Prozesse, Gerätetreiber, wird alles beeinträchtigt, wenn ich das mache. Ja,
1:10:56 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
1:11:04 sowieso im Systemmodus ist, ähm also letzt nicht im Betriebssystem äh so eine Synchronisation machen möchte, ein kritischen Abschnitt sichern möchte,
1:11:13 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
1:11:22 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
1:11:32 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
1:11:42 sogenannten atomaren Operationen. Ja, viele CPUs unterstützen unteilbare Leseemodifikations und Schreibzyklen, mit denen sich ähm so so äh
1:11:51 Schlossalgorithmen implementieren lassen. Ja, also z.B. Ähm hier Motorola ist das die Instruktion Test and Set. Ja, was macht
1:12:00 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.
1:12:11 Ähm, die testet also dieses Bit und setzt dieses Bit und liefert den den vorherigen Zustand von diesem Bit in einem Condition Code.
1:12:21 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
1:12:27 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
1:12:34 Schleife. Ja, also die Instruktion, die Instruktion, die Instruktion, die die Instruktion. Wenn dieses Test und Set
1:12:39 hier feststellt, dass dieses höchstwertige oder nee, wenn das höchstwertige Bit null war, dann setzt diese Instruktion dieses Bit
1:12:49 und merkt sich den alten Zustand von diesem Bit wieder in so ein Condition Code und dann springt diese Sprunginstruktion eben nicht, ne? Und
1:12:55 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
1:13:05 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
1:13:13 weiter unterbrochen werden. Auf X86 gibt's eine ähnliche Instruktion, ne? kann man dafür letztendlich diese Exchange Instruktion
1:13:21 verwenden. Von der Semantik her ziemlich ziemlich ähnlich wie in der Motorola Variante. Ja, auf Power PC gibt's was ähnliches. Letztendlich haben alle,
1:13:30 Entschuldigung, letztendlich haben alle modernen Instruk moderne CPUs so eine so ein Lesemodifikationsschreibzyklusinstruktion.
1:13:43 Ähm, so, aber die bis jetzt gezeigten Schlossalgorithme, die haben alle einen großen Nachteil, nämlich die warten
1:13:53 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
1:14:03 halt in einem ungünstigen Zeitpunkt verdrängt werden kann, aber letztendlich wartete aktiv. Genauso der Bäckereialgorithmus. Ja, da
1:14:11 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
1:14:17 drehen, bis wieder irgendein Zustand erreicht ist. Ja, die warten aktiv. Ähm genauso diese atomanoperationen, ja, das sind auch letztendlich Schleifen,
1:14:27 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
1:14:38 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,
1:14:49 der wartet, ja, der darauf wartet, dass Log z.B. null wird, der kann selbst überhaupt keine Änderung dieser Bedingung
1:14:59 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
1:15:09 das Lock jemals null wird, sondern der wartet darauf, dass jemand anderes dieses Lock auf null setzt. Also ein anderer Prozess,
1:15:16 ja? Trotzdem dreht er sich in der Schleife und rechnet. Mit anderen Worten, ähm z.B. Wenn ja, dieser Prozess läuft ja
1:15:26 gerade der, nehmen wir mal an, wir sind irgendwie im im äh prämit Zeitscheiben Scheduling irgendwie, dann verbraucht er seine komplette Zeitscheibe mit
1:15:35 iterieren und testen dieser Logariablen, also die kompletten 20 Millisekunden hindurch wird einfach nur in der Endlosschleife oder nicht in einer
1:15:43 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
1:15:53 dieser Prozess selbst das gar nicht machen kann auf dem und auf dem Uniprozessorsystem, der weil auch kein anderer Prozess dran kommen kann, der
1:15:59 dieses, der vielleicht gerade im kritischen Abschnitt ist und dieses Log auf null setzen könnte. Ja, also er behindert ähm
1:16:08 alle anderen Prozesse, weil er seine Zeitscheibe mit unnützen Schleifendrehen ähm äh ja verbrennt. Ja, also andere Prozesse, die sonstige
1:16:20 sonstige sinnvolle Arbeit leisten können, die jetzt mit unserem kritischen Abschnitt überhaupt nichts zu tun haben und letztendlich schadet er auf sich
1:16:26 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
1:16:37 ja auch drauf warten, dass endlich ein anderer Prozess dran kommt, seinen kritischen Abschnitt beendet und Log auf null setzt.
1:16:44 Ja, das heißt also das aktive Warten ist auf einem Uniprozessorsystem einfach nicht schlau. Es funktioniert,
1:16:53 aber es ist nicht schlau. Nur bei dem Multiprozessorsystem wird es ein bisschen aufgeweicht, weil natürlich bei einem Multiprozessorsystem
1:17:00 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
1:17:09 auf null setzen kann. Da kann das sinnvoll sein. Ja. Auf einem Uniprozessorsystem ist es nicht schlau aktiv zu warten
1:17:18 und deswegen ist das was man eigentlich macht das sogenannte passive Warten. Ja, und dafür braucht man letztendlich Betriebssystem
1:17:27 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
1:17:36 jetzt an. Ja, also passives Warten ist die das, wo wir hin wollen und da ist eben die Idee,
1:17:46 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.
1:17:58 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
1:18:07 möchte. blockiert sich der Prozess auf ein Ereignis, geht in den Zustand blockt. Ja, der Prozess Kontrollblock dieses
1:18:15 Prozesses wird in eine Warteschlange eingereiht, die also auf dieses Ereignis in dem Fall die Freigabe dieses Logs warten. Und wenn das Ereignis eintritt,
1:18:25 also das ein anderer Prozess dann dieses Lock freigibt, z.B., Dann wird ein darauf wartender Prozess deblockiert.
1:18:34 Ja, das heißt also ein Prozess, der wartet, ist nicht mehr im Zustand running wie beim aktiven Warten, sondern im Zustand blocked.
1:18:44 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,
1:18:53 ausgelegt. Also, wenn ich ein Log auf einem auf einer auf einem Lock, das gerade ein Aqu, das gerade gesperrt ist, dann wird
1:19:03 der Ablauf Plan für die Prozesse aktualisiert. Also, es passiert wieder so eine Scheduling so ein Scheduling Schritt. Es wird ein anderer gerade
1:19:10 schon gerade laufwähliger Prozess ganz normal plangemäß abgefertigt. Also der vorderste aus der aus der Ready Liste rausgenommen wird also dispatchted
1:19:19 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
1:19:28 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
1:19:37 in so ein so ein leichten Schlafmodus, wo also das ganze System weniger Strom braucht, so lange bis wieder irgendeiner lauffähig wird.
1:19:44 Ja, und wenn ähm so ein Prozess blockiert, also von Running auf blocked geht, weil er auf den Lock wartet, endet damit natürlich
1:19:52 auch sein CPU-Soß. Ja, also man kann sich jetzt konzeptionell das Warten auf ein Log vorstellen wie das Starten eines ein Ausgabestoßes.
1:20:02 Beginn eines ein Ausgabestoßes. Ja, genauso wie äh Einausgabe von der Festplatte oder von der Tastatur oder sowas.
1:20:11 Ähm die Betriebssystemabstraktionen, die man dafür verwendet, sind die sogenannten Semmerapforen.
1:20:18 Ja, was ist ein Semmeraphor? Das ist eine Betriebssystem Abstraktion, die in den 60ern von dem Herrn Dextstra beschrieben wurde, der bestimmt dem
1:20:27 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
1:20:38 unteilbare Operationen definiert. P das steht für niederländisch Prol. Das liegt einfach daran, dass der Herr
1:20:47 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
1:20:56 erniedrige, ja, oder auch down oder weight. Und das äh hat folgende Semantik. Wenn diese dieser Semmervor den Wert null
1:21:05 hat, dann wird der laufende Prozess blockiert. Ja, und sonst nichts. Und ansonsten wird
1:21:13 der Semmerform 1 dekrementiert. Ja, also wenn der vorher den Wert 1 hatte, hatte hat er einfach hinterher den Wert null.
1:21:19 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
1:21:28 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
1:21:39 Semmervor wartenden Prozess gibt, also einen blockierten Prozess, der also darauf wartet, dass der dieser Semmervor frei wird, dann wird der bei einem bei
1:21:47 einem Vlockiert und ansonsten wird der Semmer vor um eins inkrementiert. Ja, und dieses diese Semmerformen können
1:21:57 eben verwendet werden, um zwischen nebenläufig arbeitenden Prozessen sogenannte Synchronisationssignale ähm auszutauschen.
1:22:05 Was das ähm genau bedeutet, das werden wir gleich an dem Beispiel sehen. Ähm, das ist tatsächlich die
1:22:15 Implementierung von Semmern in einem in dem OOstups, das objektorientierte Studentenbetriebssystem. Das ist so ein so ein System, dass man in der
1:22:23 Masterveranstaltung Betriebssystem Bau äh hier selbst baut. Das ist die das ist so ein Teil von der Semmervorimplementierung und da sieht
1:22:29 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
1:22:39 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
1:22:46 letztendlich diese Schritte hier durchgeführt, die letztendlich dafür sorgen, dass der Prozess, der dieses Weight aufgerufen hat, blockiert wird
1:22:53 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.
1:23:03 Ja, wenn es einen gibt, dann wird der geweckt, ja, also wieder ready gesetzt und anderenfalls wird der Counter um eins erhöht.
1:23:14 Ja, und letztendlich ist so ein Semmerfor abgeleitet von der Klasse Waiting Room. Waiting Room ist letztendlich einfach eine Liste von
1:23:21 Prozesskontrollblöcken, ja, also eine eine Warteschlange von Prozessen. Der Scheduler, der lieitstellen, die halt hier die auch verwendet werden.
1:23:31 Ja, das ist dieses Active, dieses Block. Und dieses Wakeup, ja, und dieses Active sagt letztendlich, welcher ist der gerade laufwä laufende Prozess. Block
1:23:41 blockiert einen gerade laufenden Prozess und Wakeup setzt einen blockierten Prozess wieder auf die Ready Liste.
1:23:53 So und so benutzt man Semmer und damit sind wir eigentlich fast wieder am Anfang der Vorlesung. Ja, also Semapfor ist einfach eine konkrete
1:24:02 Log, also eine konkrete konkreter Datentyp, den man also als Schlossalgorithmus als Schloss äh Algorithmen Schlossviablen Datentyp
1:24:11 verwenden kann. Also ein Semmer hat klassischerweise äh initial den Wert 1, z.B. Normalerweise muss man das einfach
1:24:21 einfach zuweisen. Ähm und wenn man also wenn man ihn als äh als Schlossvariable in dem Sinne verwenden will, um gegenseitigen Ausschluss äh
1:24:29 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
1:24:39 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.
1:24:46 Und wenn ein zweiter Prozess versucht gleichzeitig in diesen kritischen Abschnitt zu kommen, dann blockiert er hier. Ja, alle weiteren Prozesse, die
1:24:53 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
1:25:01 blockierenden wieder aufgeweckt. Ja, das sorgt eben dafür, dass immer nur ein Prozess in diesem kritischen Abschnitt drin sein kann.
1:25:11 Ähm, Hauer hat nachgeguckt, Extra lebt nicht mehr. Okay, dann war es einer der anden der
1:25:20 anderen alten Hasen, die es die erstaunlicherweise noch leben. Ähm, man kann selber mal vor, aber lass die
1:25:30 auch noch andere Dinge benutzen, z.B. die sogenannte einseitige Synchronisation. Ja, das ist also ein Erzeugerverbraucherszenario z.B., ne?
1:25:38 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
1:25:46 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,
1:25:56 die die Anzahl der Elemente zählt, die gerade in der Liste drin stecken, einseitig synchronisieren, ne? Jedes Mal, wenn ein Element reingesteckt
1:26:04 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
1:26:13 und wartet eben darauf, dass mindestens ein Element in der Q drin steckt. Das die sogenannte einseitige Synchronisation, die heißt einseitig,
1:26:20 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
1:26:29 beiden Operationen auf der Semaphore die einzige, die blockieren kann, ne? nur eine Seite kann blockieren, nämlich die Consumerseite.
1:26:38 Ähm und dann gibt's noch die Betriebsmittelorientierte Synchronisation. Na, da wird die funktioniert letztendlich so ähnlich wie
1:26:43 die ähm dies die Synchronisation mit gegenseitigem Ausschluss. Ja, also macht macht vor der Benutzung einer einer Ressource macht man Weight, nach der
1:26:50 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,
1:26:59 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
1:27:07 kritischen Abschnitt befinden, ne? Weil jeder dann eine von diesen zehn Ressourcen benutzen kann.
1:27:19 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.
1:27:29 Ähm, da soll also ein kritischer Abschnitt geschützt werden, wo es als Arbeit zwei Klassen von beteiligten, konkurrierenden Prozessen gibt, nämlich
1:27:39 die Schreiber und die Leser. Und die Schreiber, die wollen Daten ändern an dieser Datenstruktur und dementsprechend muss ein Schreiber exklusiven
1:27:49 Zugriff auf diese Datastruktur bekommen. Ja, also es darf immer nur ein Schreiber ganz alleine auf dieser Datenstruktur arbeiten oder beliebig viele
1:27:58 gleichzeitige Leser. Ja, lesen kann man ja problemlos gleichzeitig. Ähm, aber sobald einer schreiben möchte, darf eben dann nur der schreiben und
1:28:07 auch keiner kann anderer gleichzeitig schreiben und kann anderer gleichzeitig lesen. Auch das kann man mit Semmerform und synchronisieren.
1:28:14 Das ist jetzt aber schon ein bisschen komplizierter, ja? Ähm, letztendlich brauchen wir hier zwei Semaphoren. Eine, die wir hier Newtext
1:28:22 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
1:28:32 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
1:28:45 oder dran blockieren, dann darf er schreiben, dann darf es wieder freigeben. Ja, das ist jetzt ganz normaler gegenseitiger Ausschluss. Immer
1:28:52 nur ein Schreiber darf schreiben. Leser ist jetzt aber schon ein bisschen komplizierter. Ja, da wird es erstmal eine Mutex
1:28:59 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
1:29:06 bin, muss ich hier mit dem Weight WD hierfür sorgen, dass kein Schreiber hier rein hier reinkommt. Ja, wenn ich der erste Leser
1:29:14 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
1:29:22 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
1:29:30 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
1:29:38 Schreiber gerade blockiert und warte darauf, dass er schreiben darf, in diesen Schreibeabschnitt ähm hinein darf.
1:29:45 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
1:29:52 ist sogar nur das erste Leserschreiberproblem. Ja, die verschiedenen Leserschreiberprobleme unterscheiden
1:29:57 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,
1:30:05 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
1:30:14 dürfen auch jederzeit noch weitere Leser kommen. Es gibt noch noch ein anderes Leserschreiberproblem, wo sobald ein Schreiber z.B. schreiben
1:30:20 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
1:30:28 nachdem, wie wie die Priorisierung hier aussieht, ähm ist es das erste oder das zweite Leserschreiberproblem.
1:30:36 Ähm, es gibt von Semfor noch ein paar Varianten ähm oder Erweiterungen. Ja, also
1:30:45 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
1:30:52 verwendet, in der Regel verwendet, um einen kritischen Abschnitt immer einen kritischen Abschnitt für für gegenseitigen Ausschluss zu sorgen. Ähm,
1:30:59 die nennt man auch Mutex, ja? Mutex für Mutual Exclusion, also gegenseitigen Ausschluss. Ähm von dem Weight oder dem P gibt es
1:31:08 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,
1:31:15 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
1:31:22 Gruppfahrt wählen, anstatt zu blockieren. Ähm, weight mit Timeout gibt es noch, also wo das ähm wo man das nicht
1:31:31 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
1:31:37 wird, dann möchte ich nicht weiter blockieren. Oder es gibt Implementierungen, wo man nicht nur eine Semmerfor hat, sondern ein ganzes Array
1:31:44 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
1:31:53 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
1:32:01 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
1:32:13 SF und die kann das. Ähm und was es bei Semfor auch noch gibt, sind eben Fehlerquellen. Ja. Ähm zum einen
1:32:23 entsteht die Gefahr von Verklemmungen. Was das ist, das gucken wir uns in der nächsten Vorlesung an. komplexere Synchronisationsmuster, wie
1:32:30 wir das jetzt hier gesehen haben, äh die können durchaus schwierig werden. Na, also das Leserschreiberproblem ist nicht das einzige Synchronisationsproblem, was
1:32:38 man in dem Kontext finden kann. Da gibt's noch ganz andere hässliche. Ähm, eine definitive Fehlerquelle ist, dass
1:32:46 die kooperierenden Prozesse, die also alle auf derselben Datenstruktur arbeiten, dass die alle ein bestimmtes Synchronisationsprotokoll wirklich
1:32:54 einhalten müssen. Ja, sobald ein Prozessor irgendwie durch einen Programmierfehler z.B. aus der Reihe tanzt, ähm können trotzdem Race Racing
1:33:02 Conditions und möglicherweise Datenkorruption eintreten. Ja, also jeder muss die Protokolle exakt anhalten. Es gibt nichts, was das
1:33:09 erzwingt, ähm weswegen man sich eigentlich sowas wünscht wie Unterstützung durch die Programmiersprachen.
1:33:17 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
1:33:26 jetzt noch mal ein bisschen Fragen an. Ähm, wie wird festgelegt, welcher der blockierten Prozesse freigegeben wird, wenn es z.B. drei blockierte Prozesse
1:33:36 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
1:33:45 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
1:33:51 auch versuchen, die Semaphore zu dekrementieren mit dem Weight oder dem P. Und jetzt verlässt der, also und diese
1:33:59 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
1:34:05 der Semapore auf. Welcher von den wartenden Prozessen wird jetzt denn deblockiert? Ähm, da werden wir auch in dem in dem Rest
1:34:13 der Vorlesung noch mal ganz kurz drüber sprechen. Äh, also nächstes Mal ähm letztendlich kann man irgendeinen Verfahren wählen.
1:34:22 Ja, also z.B. F Kampf. So, wer zuerst blockiert hat, darf als erstes wieder deblockiert werden. Normalerweise sollte man an der Stelle
1:34:30 versuchen, äh den zu deblockieren, der auch nach der drüber liegenden Scheduling Strategie die höhere Priorität hat. Ja, also solche ein
1:34:42 hochpriorer Prozess sollte als erstes deblockiert werden vor einem niederprierioren Prozess. Ja, das sind z.B. für Dinge, die man da entscheiden
1:34:49 muss. Ähm, sonst kann es passieren, dass man Entscheidungen trifft, die der der gerade aktiven Schedulingstrategie zu
1:34:57 Wiederlaufen. So, Dextra ist nicht der redanische Geheim, weiß ich nicht. Vielleicht
1:35:07 gibt's auch einen redanischen Geheimnischef, der Dikstra heißt. Kenne ich nicht. Ist Dextra nicht ein Algorithmus, um den
1:35:13 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
1:35:23 vorgeschlagen hat, den man auch deswegen den Digra Algorithmus nennt, aber ähm der hat noch andere Sachen gemacht, z.B. Semmer vorn erfunden.
1:35:35 Okay, gibt's noch weitere Fragen zum Thema Synchronisation? Ansonsten freue ich mich auf vorab oder auch währenddessen eingereichte Fragen für
1:35:45 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
1:35:55 E-Mail, per Gumakkasten, wie Sie möchten. Einer tippt noch.
1:36:06 Einer tippt noch. Einer hat wieder aufgehört zu tippen. Dann würde ich vorschlagen, wenn Sie die Frage doch noch haben, dann
1:36:13 stellen Sie sie in der Kund a Sitzung in knapp einerhalb Stunden. Vielen Dank. M.