Einführung in die
Informatik 2

Wichtige Begriffspaare

Kernel-Modus vs. User-Modus

Die CPU kennt zwei Betriebsarten:

• User-Modus: Normale Programme laufen hier. Gefährliche Befehle (direkt auf Geräte oder fremden Speicher zugreifen) sind verboten.
• Kernel-Modus: Nur der BS-Kern läuft hier und darf alles.

Warum sind E/A-Befehle privilegiert (nur Kernel)? Geräte sind gemeinsam genutzt. Dürfte jedes Programm direkt darauf zugreifen, käme es zu Chaos, Datenverlust und Sicherheitslücken. Deshalb entscheidet eine zentrale Instanz (der Kern), wer wann darf.

System Call: die einzige „Tür“ vom User- in den Kernel-Modus. Das Programm bittet das BS um einen Dienst (z. B. „Datei lesen“). Technisch ist es ein Software-Interrupt: kurz in den Kernel-Modus wechseln, Dienst ausführen, zurück in den User-Modus.

Ein Prozess ist nicht ständig am Rechnen. Er wechselt zwischen Zuständen:

7-Zustands-Modell: Reicht der Hauptspeicher nicht, lagert das BS Prozesse auf die Platte aus (Swapping). Es kommen READY/SUSPEND und BLOCKED/SUSPEND dazu = „ausgelagert“.

Die wichtigsten Übergänge (und ihre Auslöser)

• READY → RUNNING: Dispatcher teilt CPU zu.
• RUNNING → READY: Zeitscheibe abgelaufen (Verdrängung).
• RUNNING → BLOCKED: Prozess wartet auf Ereignis (z. B. E/A).
• BLOCKED → READY: erwartetes Ereignis ist eingetreten (Interrupt „fertig“).
• → SUSPEND: ausgelagert auf Platte (Speicher knapp); zurück durch Einlagern.

Ein Thread ist ein einzelner Ausführungsfaden innerhalb eines Prozesses. Ein Prozess kann in mehrere Threads aufgeteilt werden, die parallel laufen. Alle Threads eines Prozesses teilen sich dessen Betriebsmittel: Adressraum, geöffnete Dateien, Geräte.

• Threads erzeugen und zwischen ihnen wechseln ist schneller und braucht weniger Aufwand als bei echten Prozessen (kein Adressraumwechsel).
• Der Prozess bleibt antwortfähig, auch wenn ein einzelner Thread blockiert.
• Mehrere CPUs → echte Parallelität.
• Kehrseite: das BS schützt Threads nicht voreinander (gemeinsamer Speicher → selbst synchronisieren).

Schema in 4 Schritten

1. Zeitachse zeichnen, Ankunftszeiten markieren.
2. An jedem Entscheidungspunkt (Prozessende; bei präemptiv auch jede Ankunft / jedes Quantum-Ende) die Regel anwenden. Nur schon angekommene Prozesse betrachten!
3. GANTT-Balken füllen, bis alle fertig sind.
4. Pro Prozess Endzeit ablesen → Wartezeit-Formel → Mittelwert bilden.

Die zwei Formeln

Mittelwert = Summe ÷ Anzahl der Prozesse. „Bedienzeit“ = „Burst“ = wie lange der Prozess rechnen will.

Drei Begriffe, die oft verwechselt werden

Kritischer Abschnitt: 3 Korrektheits-Kriterien

• Gegenseitiger Ausschluss: nie zwei gleichzeitig drin.
• Fortschritt: ist der Abschnitt frei, darf ein Wartender rein.
• Begrenztes Warten: niemand wartet unendlich lange.

Reihenfolge erzwingen (Blatt 3, Frage 3.1a)

„opA und opB erst nachdem C opC ausgeführt hat.“ C gibt zweimal frei:

init(s, 0);   // niemand darf zuerst
A:            B:            C:
 wait(s);      wait(s);      opC;
 opA;          opB;          signal(s);
                             signal(s);

So warten A und B, bis C fertig ist und zweimal signal gibt. Anfangswert immer hinschreiben — gibt Punkte.

init(mutex, 1);  // schützt Puffer
init(leer, MAX); // freie Plätze
init(voll, 0);   // belegte Plätze

Erzeuger:           Verbraucher:
 erzeuge(item);      wait(voll);
 wait(leer);         wait(mutex);
 wait(mutex);        entnimm(item);
 lege ab(item);      signal(mutex);
 signal(mutex);      signal(leer);
 signal(voll);       verbrauche(item);

Indirekte Kommunikation (Frage 2.7) = über eine Mailbox (Briefkasten), nicht direkt an den anderen Prozess. Antwort c) ist richtig.

Busy Waiting (aktives Warten, Frage 2.10): Der Prozess prüft in einer Schleife dauernd „darf ich schon?“ und verbrennt dabei CPU-Zeit. Alternative: sich blockieren lassen und die CPU freigeben (kostet zwei Kontextwechsel). Ganz vermeiden lässt sich aktives Warten nicht — irgendwo ganz unten (z. B. beim Sperren sehr kurzer Abschnitte / Spinlocks) ist es sinnvoll.

Monitor (Folie 02): bequemere Alternative zum „nackten“ Semaphor — ein Sprachkonstrukt, bei dem immer nur ein Prozess im Monitor aktiv ist (Mutex automatisch). Auf Bedingungen wird mit wait/signal an Bedingungsvariablen gewartet.

Segmentierung (Frage 3.4)

Logische Adresse = (Segmentnummer s, Offset d). Eine Segmenttabelle liefert je Segment Basis und Länge.

Ist d ≥ Länge[s] → unzulässiger Zugriff (Trap). Das ausdrücklich hinschreiben — gibt Punkte.

Paging: Adresse zerlegen (Fragen 3.3 / 3.5)

Der Speicher ist in gleich große Seiten (logisch) bzw. Kacheln/Rahmen (physisch) geteilt.

Bei Seitengröße = Zweierpotenz geht es per Bit-Aufteilung: 256 B = 2⁸ → die unteren 8 Bit sind der Offset (= 2 Hexziffern), der Rest oben ist die Seitennummer.

Schema

1. Tabelle: Spalten = Referenzen, Zeilen = Kacheln.
2. Seite schon drin? → Hit (bei LRU „zuletzt benutzt“ aktualisieren; bei Clock Use-Bit auf 1).
3. Nicht drin? → Seitenfehler markieren, Opferseite nach Strategie wählen, ersetzen.
4. Bei Clock zusätzlich die Zeigerposition mitführen.
5. Fehler erst zählen, wenn alle Kacheln erstmals belegt sind (Konvention der Musterlösung).

Buddy-System (Folie 03)

Schnelle Speichervergabe mit Blockgrößen in Zweierpotenzen. Vorgehen:

1. Anforderung auf die nächste Zweierpotenz aufrunden.
2. Gibt es keinen passenden Block, einen größeren wiederholt halbieren; die zwei Hälften heißen Buddies (sie unterscheiden sich nur im k-ten Adressbit).
3. Beim Freigeben: ist der Buddy auch frei, beide wieder zu einem größeren Block verschmelzen.

+ sehr schnell, einfaches Verschmelzen · − interne Fragmentierung (Aufrunden verschenkt Platz).

TLB — Translation Lookaside Buffer (Folie 03)

Jede Adressumrechnung (virtuell → physisch) müsste eigentlich erst in der Seitentabelle im RAM nachschlagen — ein zusätzlicher Speicherzugriff pro Befehl. Das ist langsam.

Der TLB ist ein kleiner, schneller assoziativer Cache direkt in der MMU, der die zuletzt benutzten Seiten-→-Kachel-Zuordnungen speichert.

• TLB-Hit: Zuordnung im TLB → sofort, kein RAM-Zugriff für die Tabelle.
• TLB-Miss: erst in der Seitentabelle nachschlagen, dann in den TLB übernehmen.

FAT-Prinzip

Das Verzeichnis nennt den Startblock. Eine zentrale Tabelle (FAT) enthält je Block die Nummer des Nachfolgers (oder „nil“ = Ende, „free“, „bad“).

Dann ab dem Startblock genau so viele FAT-Schritte weitergehen. Offset = Byte-Nr mod Blockgröße.

I-Node: maximale Dateigröße (Frage 4.3)

Ein I-Node hat ein paar direkte Blockadressen plus indirekte (einfach/doppelt/dreifach). Eine indirekte Adresse zeigt auf einen Block voller weiterer Adressen.

Beispiel „linode“: Block 4 KiB, Adresse 2 Byte ⇒ 4096÷2 = 2048 Adressen/Block. 7 direkt + 2048 (einfach) + 2048² (doppelt) + 2048³ (dreifach) Blöcke. Mal Blockgröße = max. Dateigröße (≈ 32 TiB). Schema: erst Adressen/Block, dann Blöcke pro Stufe summieren, dann × Blockgröße.

Bitmap (Frage 4.4)

1 Bit pro Block: 1 = belegt, 0 = frei. Es wird immer der freie Block mit der niedrigsten Nummer vergeben (von links). Gelöschte Lücken werden also zuerst wieder gefüllt.

Verkettete Freiliste — Zeiger verloren (Frage 4.5)

Ja, rekonstruierbar: Man durchsucht alle Dateien/Verzeichnisse ab der Wurzel, markiert alle benutzten Blöcke; alles Unmarkierte ist frei. Aufwand wächst linear mit der Dateianzahl.

rename vs. Kopieren+Löschen (Frage 3.8): rename ändert nur den Verzeichniseintrag (schnell, kein neuer Speicher). Kopieren belegt erst neue Blöcke (kann bei voller Platte scheitern) und ändert Attribute wie die Erstellungszeit.

open()/close() (Frage 3.10): open() prüft, ob die Datei existiert und der Prozess Zugriff hat, legt einen Eintrag in der Open-File-Tabelle an und gibt einen Verweis (Handle) zurück. close() entfernt diesen Verweis und gibt Ressourcen frei.

Journaling (Folie 04)

Problem: Stürzt der Rechner während einer Schreiboperation ab, kann das Dateisystem inkonsistent werden (halb geschriebene Daten). Lösung: ein Journal.

1. Geplante Schreiboperationen zuerst in einen reservierten Bereich (das Journal) protokollieren.
2. Zu festen Zeitpunkten das Journal auf den Massenspeicher durchschreiben (Commit).
3. Nach einem Absturz wird das Journal einfach erneut durchgeschrieben → konsistenter Zustand.

Zugriffsrechte & ACL (Folie 04)

Jede Datei trägt in ihren Metadaten (im I-Node) Attribute: Größe, Zeitstempel, Eigentümer und Zugriffsrechte.

• Unix-Klassiker: rwx (read/write/execute) je für Eigentümer, Gruppe, andere.
• ACL (Access Control List): feinere Liste, die einzelnen Nutzern/Gruppen gezielt Rechte gibt.

open() prüft genau diese Rechte, bevor es eine Datei freigibt.

Einzel- vs. Doppelpuffer (Frage 4.6)

Ein Puffer ist ein Zwischenspeicher. Beim Einzelpuffer muss erst gelesen, dann verarbeitet werden — abwechselnd, mit Wartezeiten.

Beim Doppelpuffer gibt es zwei: während Puffer 1 verarbeitet wird, füllt das Gerät schon Puffer 2. Lesen und Verarbeiten überlappen → schneller.

Treiber ohne Neukompilieren (Frage 4.7)

Ein Treiber ist das Programm, das ein bestimmtes Gerät ansteuert. Er wird vom Hersteller geliefert und als dynamische Bibliothek nachgeladen. Bei der Installation trägt das BS in eine nach Gerätenummern sortierte Tabelle Zeiger auf open/close/read/write ein.

Ein System Call mit der Gerätenummer findet darüber die richtige Funktion. Das BS selbst bleibt unverändert — kein Neu-Übersetzen nötig.

Wozu Header? (Kapselung)

Beim Senden fügt jede Schicht ihren eigenen Header (Steuerinfos: Adressen, Nummern, Prüfsummen) vorne an; beim Empfänger entfernt die passende Schicht ihn wieder. So „spricht“ jede Schicht mit ihrer Partnerschicht der Gegenseite.

n Schichten, h Byte Header je Schicht, M Byte Nutzdaten (Frage 4.11).

Schichten-Spielregeln (Frage 4.10)

Eine Schicht darf nur mit (a) der direkt darunter und (b) logisch mit der gleichen Schicht der Gegenseite reden. Schichten überspringen oder „quer durchtelefonieren“ ist ein Verstoß (Klausurtyp: Verstöße in einer Geschichte markieren).

Leitungs- vs. Paketvermittlung (Frage 4.12)

x Bit Nachricht, k Teilstrecken, b bit/s, d Laufzeit je Strecke, s Aufbauzeit, p Paketgröße.

Die Schrittgeschwindigkeit (in Baud) sagt, wie viele Signalschritte pro Sekunde gesendet werden. Die Bitrate hängt zusätzlich davon ab, wie viele Zustände ein Signalschritt unterscheiden kann — je mehr Zustände, desto mehr Bits pro Schritt.

Binär ×1 · ternär ×log₂3 ≈ 1,58 · quaternär ×2 · oktonär ×3.

Stop-and-Wait: Kanalausnutzung (Frage 5.6)

Sende einen Rahmen, dann warte auf die Bestätigung, erst dann den nächsten. Viel Leerlauf, wenn die Leitung lang ist.

T_Frame = L/b (Sendezeit), T_Prop = Signallaufzeit. Für U ≥ 50 %: T_Frame ≥ 2·T_Prop, also L ≥ 2·T_Prop·b.

Go-back-N / Gleitfenster (Frage 5.1)

• n-Bit-Seq.-Nummern → Werte 0…2ⁿ−1; max. Sendefenster = 2ⁿ−1 (bei 3 Bit: höchstens 7).
• Bei Lücke verwirft der Empfänger die Folgerahmen; der Sender wiederholt alle ab dem fehlenden („go back n“).
• Piggybacking: die Bestätigung (ACK) reist im Datenrahmen der Gegenrichtung mit; eigene ACK-Rahmen nur, wenn keine Daten anstehen. NAK (negativ) sofort senden.
• Weg-Zeit-Diagramm: schräge Pfeile (Laufzeit!), jeden Rahmen mit Seq-Nr. und ACK-Feld beschriften.

Idee: An die Nachricht werden Prüfbits angehängt, sodass das Ganze durch ein vereinbartes Generatorpolynom teilbar ist. Beim Empfänger: Rest 0 → ok, Rest ≠ 0 → Fehler.

1. Grad des Generators = r → r Nullen anhängen.
2. Modulo-2-Division (XOR statt Minus, kein Übertrag) durch den Generator.
3. Der Rest (r Bit) ersetzt die angehängten Nullen → das ist die gesendete Folge.
4. Empfänger teilt erneut: Rest 0 = kein erkennbarer Fehler.

CSMA/CD + Binary Exponential Backoff (Frage 5.8)

Bei Ethernet hören Stationen vor dem Senden ab (Carrier Sense). Bei einer Kollision warten beide eine zufällige Zeit, ehe sie es erneut versuchen.

Nach der 5. Kollision: k ∈ {0,…,31} → 32 Werte → P(k=4) = 1/32. Wartezeit = k Slotzeiten.

Hidden Terminal (Frage 5.10)

Funkstationen hören sich nur teilweise. Sendet A an B, können andere Stationen senden, die B nicht stören (außerhalb von B's Reichweite). Antwort bestimmst du, indem du je Station prüfst: Liegt sie in Reichweite des Empfängers? Wenn nein, darf sie parallel senden.

Manchester-Codierung (Frage 5.11)

Jedes Bit hat eine Flanke in der Bitmitte: in der Vorlesungskonvention z. B. Low→High = 1, High→Low = 0. Bitfolge ablesen = Flankenrichtung je Bit notieren.

Erkennen vs. Korrigieren

• Parität (Querparität/VRC): ein Prüfbit pro Zeichen macht die Anzahl der Einsen gerade/ungerade — erkennt einzelne Bitfehler, kann sie aber nicht orten.
• CRC: erkennt ganze Fehlerbündel (siehe oben), korrigiert nicht.
• Fehlerkorrektur (z. B. Hamming): genug Prüfbits, um den Fehler nicht nur zu erkennen, sondern die fehlerhafte Stelle zu finden und umzudrehen. Faustregel über die Hamming-Distanz d: d−1 Fehler erkennbar, ⌊(d−1)/2⌋ korrigierbar.

Rahmenbildung (Framing)

Aus dem Bitstrom müssen Rahmengrenzen erkennbar sein. Verfahren u. a.:

• feste Länge / Längenfeld im Header;
• Byte-/Bit-Stuffing: ein Sonderzeichen markiert Anfang/Ende; kommt das Muster in den Daten vor, wird ein Füllzeichen/-bit eingefügt, das der Empfänger wieder entfernt.

Beispiel-Rahmenformat: IEEE 802.3 (Ethernet) mit Präambel, Adressen, Längen-/Typfeld, Nutzdaten und FCS (CRC).

Schema (VLSM)

1. Bedarf je Subnetz +2 → auf nächste Zweierpotenz aufrunden → Präfix.
2. Größtes Subnetz zuerst platzieren.
3. Der Reihe nach vergeben; jede Subnetzadresse muss ein Vielfaches ihrer Blockgröße sein (Ausrichtung!).
4. Kontrolle: lückenlos? überlappungsfrei? Ausrichtung korrekt?

Dijkstra (Frage 5.2)

1. Startknoten Distanz 0, alle anderen ∞.
2. Den unbesuchten Knoten mit der kleinsten Distanz wählen, als „fertig“ markieren.
3. Seine Nachbarn aktualisieren: ist „aktuelle Distanz + Kante“ kleiner, übernimm sie (Vorgänger merken).
4. Wiederholen, bis alle fertig sind. Ergebnis: kürzeste Distanz + Pfad zu jedem Knoten.

Link-State-Routing / LSA (Frage 5.3)

• Jeder Router misst die Kosten zu seinen direkten Nachbarn und flutet sie als LSA (Link State Advertisement) an alle (Flooding; Sequenznummer + Alter verhindern Schleifen).
• LSA-Inhalt: Absender, Liste (Nachbar, Kosten), Sequenznummer, Alter/TTL.
• Aus allen LSAs baut jeder Router die Distanzmatrix = vollständige Topologie.
• Daraus die Routingtabelle (dst / next-hop / distance) — in der Klausur oft „durch Hinsehen“.

Rund um IP

Distanzvektor vs. Link-State

Hierarchie: Das Internet ist in Autonome Systeme (AS) unterteilt; innerhalb eines AS läuft z. B. RIP/OSPF, zwischen den AS BGP.

a) Verbindungsaufbau (3-Wege-Handshake)

Nr 2 = SYN+ACK des Servers, bestätigt 500+1=501. Nr 3 = ACK des Clients, eigene SeqNo 501, bestätigt 1000+1=1001.

b) Datenphase (Beispiel)

Abbau (c): gleiches Schema mit FIN-Flag; FIN zählt wie 1 Byte, das abschließende ACK bestätigt FIN-SeqNo + 1.

Sendefenster & Window Scaling (Frage 4.14)

Satellit: 800 ms × 24 Mbit/s = 19,2 Mbit = 2,4 MByte.

Problem: Das TCP-Fensterfeld ist nur 16 Bit → max. 2¹⁶−1 = 65 535 Byte. Viel zu klein.

Lösung: Window-Scale-Option (Faktor 2ⁿ, n ≤ 14). Hier n = 6, denn 2¹⁶·2⁶ = 2²² ≥ 2,4·10⁶.

Slow Start (Frage 4.16)

Das Überlastungsfenster startet bei 1 MSS und verdoppelt sich pro RTT-Runde (1, 2, 4, 8, …) bis zur Schwelle ssthresh; danach „Congestion Avoidance“: nur noch +1 pro Runde.

Jacobson-RTT-Schätzung (Frage 4.15)

M = gemessener Wert. Beispiel α = 0,9, Start 30 ms, Messungen 26/32/24: → 29,6 → 29,84 → 29,256 ms. Immer den zuletzt geschätzten Wert einsetzen.

TCP Reno: Verlust erkennen (Frage 4.17)

• Slow Start erkennt man am Verdoppeln pro Runde; Congestion Avoidance am linearen +1.
• Triple Duplicate ACK (3 gleiche ACKs): leichter Verlust → ssthresh = Fenster/2, Fenster = ssthresh (Fast Recovery), kein kompletter Neustart.
• Timeout: schwerer Verlust → ssthresh = Fenster/2, Fenster springt auf 1 (neuer Slow Start).

TCP vs. UDP

Ports & Sockets

Die IP-Adresse adressiert den Rechner, der Port das einzelne Programm darauf. Ein Socket = IP + Port. So weiß das Betriebssystem, welcher Anwendung ein ankommendes Segment gehört (Multiplexing/Demultiplexing).

Flusskontrolle ≠ Überlastkontrolle

• Flusskontrolle: schützt den Empfänger vor Überlauf — er teilt mit seinem Empfangsfenster mit, wie viel er noch aufnehmen kann.
• Überlast-/Staukontrolle (Congestion): schützt das Netz vor Überlastung — Slow Start, Congestion Avoidance, Reaktion auf Verluste (siehe oben).

Namensbestandteile von www.thi.de

• www = Hostname
• thi = Second-Level-Domain
• de = Top-Level-Domain (TLD)
• thi.de = Domänenname der Zone

rekursiv vs. iterativ

Klausurtyp: DNS-Nachrichten als nummerierte Pfeile in eine Topologie einzeichnen. Typisch bei leeren Caches: Client →(rekursiv)→ Resolver →(iterativ)→ Root → TLD → autoritativer Server → Antworten rückwärts. Jede Anfrage kostet eine Umlaufzeit.

HTTP ist das Protokoll, mit dem der Browser Webseiten vom Server holt (Anfrage → Antwort). Es ist zustandslos: der Server merkt sich von sich aus nichts zwischen zwei Anfragen.

Cookies: weil HTTP zustandslos ist, legt der Server eine kleine Kennung (Cookie) beim Client ab; bei jeder weiteren Anfrage schickt der Browser sie mit → der Server erkennt den Nutzer wieder (Login, Warenkorb).

Cache & Proxy: bereits geladene Objekte werden zwischengespeichert (Client-Cache oder Proxy-Server) → schneller, weniger Last. Steuerung per If-Modified-Since (Antwort 304 = noch gültig) und Cache-Control: max-age=….

Ladezeit-Rechnung (Probeklausur 8)

Seite = 1 HTML + 4 Grafiken = 5 Objekte. DNS-Lookup = RTT_ns; je Objekt 1 RTT_web; TCP-Aufbau T_setup, -Abbau T_term. Keine parallelen Verbindungen.

Persistent spart die 4 zusätzlichen Auf-/Abbauten; die 5 Anfrage-RTTs bleiben (ohne Pipelining) gleich. Herleitung zeigen — sie gibt die Punkte.

Die Shell ist die Texteingabe, mit der man dem BS direkt Befehle gibt. Ein Batchscript (.bat) ist eine Datei mit mehreren solchen Befehlen, die nacheinander ausgeführt werden.

• echo Text gibt Text aus. echo Text > datei schreibt ihn in eine Datei.
• @echo off als erste Zeile unterdrückt das Anzeigen der Befehle selbst — nur die Ausgabe erscheint.
• Parameter im Script: %1, %2 stehen für die mitgegebenen Argumente.

Zeitmanagement (90 Minuten)

• Klausur etwa hälftig Betriebssysteme (Themen 1–6) und Rechnernetze (7–11). Keinen Teil weglassen.
• Erst alle Wissensfragen einsammeln (4 OS-Aufgaben, Header, Protokolle, DNS) — schnelle, sichere Punkte.
• Dann die Rechenaufgaben mit festem Schema (Scheduling, Paging, Subnetting, TCP-Tabellen).
• Pro Aufgabe grob 1 Minute je Punkt; bleibst du hängen, markieren und weiter.
• Lösungsweg immer hinschreiben — die Herleitung gibt Punkte, nicht nur das Endergebnis.

Häufige Punktebringer

• Bei Adress-/Paging-Aufgaben: Trap/unzulässig ausdrücklich vermerken, wenn Offset ≥ Länge.
• Bei Semaphoren: Anfangswerte immer angeben.
• Bei Subnetting: Ausrichtung prüfen (Subnetzadresse = Vielfaches der Blockgröße).
• Bei BEB/CSMA: {0…2ⁿ−1} hat 2ⁿ Werte.
• Seitenfehler erst nach der Erstbelegung zählen.

Aufs A4-Blatt gehört (Merksätze)