Fragenkatalog zum Hauptdiplom Informatik - Kurse Betriebssysteme und Datenbanksysteme

(Ursprünglich zusammengestellt von M.Dugas; erweitert und aktualisiert von HG Wefels)

  1. Betriebssysteme

    1. KE1 - Einführung

      1. Welche Aufgaben hat ein Betriebssystem?

        • schließen der sogenannten ‘Semantischen Lücke’ zwischen der Rechnerhardware-/Mikroprogrammebene und der Anwendungsebene durch abstrahieren von der Komplexität der Hardware, stellt Anwendungen eine wesentlich einfachere und dadurch mächtigere Maschinenschnittstelle zur Verfügung
        • Steuerung angeschlossener Peripheriegeräte (I/O, Platten-/Arbeitsspeicher, Datenaustausch und Kommunikation)
        • Überwachung von Zugriffsrechten -> Sicherheit von Programmen und Daten
        • Behandlung von Ausnahmesituationen wie z.B. Division durch 0 (allgemeiner: unzulässige Operation), Störungen in Geräten wie z.B. Papierstau, Leitungsfehler, Programmfehler (Fehler sollten so dicht wie möglich bei der Schicht des Verursachers behandelt werden; so z.B sollten Hardwarefehler so dicht wie möglich an der Hardware selbst behandelt werden)
        • Bereitstellung bestimmter Betriebsarten wie z.B. Batch-, Echtzeit- oder Dialogbetrieb.
        • Prozeßverwaltung/-kommunikation/Synchronisation, Organisation des Mehrprogrammbetriebes (parallele Ausführung, Threading)
        • Verwaltung von Betriebsmitteln (Drucker, Speicher, CPU)
        • Bereitstellung von Kommandosprache(n)
        • Unterstützung von Administrationsaufgaben (Datensicherung, Systemkonfigurierung, Benutzerrechte)
        • Kostenabrechnung

      2. Wie funktionieren Interrupts?

        3. Ein Interrupt ist eine asynchrone Unterbrechung des Programmablaufes. Dabei wird der Zustand des Prozessors und der Zustand der unterbrochenen Anwendung z.B. auf einen Stackspeicher gerettet. Zuvor wird jedoch ausgewertet, ob es sich überhaupt um einen zulässigen (MI=maskable Interrupt) und nicht gesperrten Interrupt handelt oder ob der Interrupt maskiert war, oder ob es sich um einen NMI (=nonmaskable Interrupt) gehandelt hat. Nach dem Retten der Prozessor- und Programmzustände wird dann eine Interrupt Service Routine (ISR) ausgeführt. Nach deren Abarbeitung werden die CPU- und die Programmzustände vom Stack restauriert und die Programmausführung wird fortgesetzt.

      3. Was versteht man unter dem Ebenen- oder Schichtenmodell eines Rechners?

        • Gatter Ebene
        • Mikroprogrammebene
        • konventionelle Maschinenebene
        • Betriebssystemebene API (applikation programming interface, Betriebssystemaufrufe)
        • Assemblerebene
        • Anwendungsebene

    2. KE2 - Geräteverwaltung und Dateisysteme

      1. Welche Speichertypen gibt es?

        • RAM
        • ROM
        • EPROM
        • EEPROM
        • FD
        • HD
        • CD-ROM
        • Band
        • WORM
        • MO

      2. Warum verwendet man HDs?

        HDs sind billiger als RAM (Verhältnis » 1:30 derzeit) und ihr Inhalt überlebt in der Regel eine Rechnersitzung und/oder das Programmende ("nichtflüchtig"). Außerdem ist die verfügbare Speicherkapazität wesentlich größer. HDs können als Medium für Backups, zum Replizieren "Mirroring" von Datenbeständen (‘RAID 0’) oder als Baustein zur Konstruktion fehlertoleranter Disk-Arrays (‘RAID 1-5’) dienen. (Die Zahlen geben den Hamming-Abstand der verwendeten Codes - und damit die Fehlertoleranz - an).

      3. Wie funktionieren HD-Zugriff und Controller?
        Der Controller steuert die Datenübertragung von der Platte in den Rechner und umgekehrt. Er sorgt für die korrekte Positionierung der Schreib-/Leseköpfe, puffert den Datenstrom, adaptiert mech. und elektrisch an den Prozessorbus (Stichwort. Hostadapter), schreibt und liest Daten per DMA direkt aus/in den Hauptspeicher.
        Die mittlere Zugriffszeit einer Festplatte ergibt sich aus Suchzeit(Positionierung) + Latenzzeit(Zeit bis gesuchter Sektor unter den Köpfen erscheint) + Übertragungszeit(Zeit zum Lesen des Sektors)

      4. Welches sind die Eigenschaften virtueller Geräte?
        Virtuelle Geräte stellen durch das Betriebssystem simulierte Geräte mit idealisierten Eigenschaften dar. Bewerkstelligt wird damit die Abstraktion von den Eigenschaften realer Geräte mit dem Ziel der Geräteunabhängigkeit. In der Regel stellen virtuelle Geräte jedem Prozeß eine synchrone Operation zur Verfügung. Dabei kann es erheblich mehr virtuelle als reale Geräte geben: z.B. Druckerspooler simuliert Drucker für jeden Anwender. Beispiele virtueller Geräte: Dateien, Drucker.
        (SPOOL-System: Abk. für Simultaneous Peripheral Operation On Line)
        Virtuelle Geräte können andere Funktionalitäten haben als reale Geräte.

      5. Wie kann ein Prozeß auf Daten auf der Festplatte zugreifen?
        • Das virtuelle Gerät hinter dem die Festplatte verborgen wird, heißt Datei
        • Prozeß öffnet Datei und erhält eine Datei-ID die auf eine Datei Deskriptor tabelle verweist.
        • Adressierung der Sektoren
        • FAT, i-nodes = Sektoradresstabelle (direkte, indirekte, doppelt indirekte, dreifach indirekte Sektoradresse), Sektorfolgen
        • Übertragung Hauptspeicher-> Controller-> Platte
        • Zugriffszeiten (was dauert am längsten? =Positionierung)
          Stichworte: SSN(Shortest-Seek-Next oder Elevator-Algorithmus)
        • Maßnahmen zur Minimierung der Suchzeit
          Rotationsgeschindigkeit, Wahl der Positionierungsstrategie, Interleave
        • Wie teilt der Controller dem BS das Ende der Übertragung mit?
          Durch einen Interrupt oder ein spezielles Register.

    3. KE3 - Prozeß- und Prozessorverwaltung

      1. Was ist ein Prozeß?
        Ein Prozeß ist die Abstraktion eines in Ausführung befindlichen Programms einschließlich der aktuellen Werte des Programmzählers, der Prozessorregister und der Programmvariablen. Jeder quasiparallel ausgeführte Prozeß besitzt konzeptionell gesehen seinen eigenen Prozessor.

      2. Welche Zustände kann ein Prozeß annehmen?
        • initiiert
        • bereit
        • aktiv
        • terminiert
        • blockiert

        Beim Übergang initiiert nach bereit ist der Prozeß bereit zur Prozessorzuteilung und wird in die Warteschlange der bereiten Prozesse aufgenommen.
        Beim Übergang von bereit nach aktiv werden Anweisungen des Prozesses auf dem Prozessor ausgeführt.
        Ursache für einen Übergang von aktiv nach blockiert ist das Warten auf ein bestimmtes Ereignis: (E/A, Speicherzuteilung, etc.)
        Beim Übergang von blockiert nach bereit ist das erwartete Ereignis eingetreten.
        Der Übergang aktiv nach bereit wird durch eine Vorrangunterbrechnung (preemption) durch einen Prozeß höherer Priorität ausgelöst.

      3. Was steht im Widerspruch zu hohem Durchsatz und guter Auslastung?
        Im Widerspruch dazu stehen gutes Antwortzeitverhalten im Dialog- und Stapelbetrieb! Denn hoher Durchsatz und gute Auslastung bedingen viel Prozesse im Rechner, so daß jeder Prozeß nur rel. selten ‘dran’ kommt; d.h. das Antwortzeitverhalten wird schlechter. Auch die Zuteilungsfairneß wird dadurch zunehmend schlechter; d.h. unfairer.

      4. Erklären Sie Round Robin!
        RR ist ein Zeitscheibenverfahren. Jeder neu ins System kommende Prozeß wird an das Ende einer Liste angehängt. Der aktuelle Prozeß wird an das Ende der Liste angehängt. Der aktuelle Prozeß wird bis zum Ende seiner Zeitscheibe, bis zum Ende des Prozesses oder bis zu seinem Blockieren ausgeführt (je nachdem was eher eintrifft). Der Scheduler wechselt dann zum nächsten Prozeß und hängt den alten Prozeß ans Ende der Liste (falls dieser noch nicht terminiert ist).

      5. Nennen Sie Zuteilungsalgorithmen mit Vorrangunterbrechnung (preemptive Verfahren)!
        • Round Robin
        • LCFS (Last come first served)
        • DPRR(Dynamic Priority Round Robin)

    4. KE4 - Hauptspeicherverwaltung

      1. Wie kann der Hauptspeicher vom Betriebssystem verwaltet werden?
        Im Benutzermodus bildet das Betriebssystem die physischen Adressen des Rechners auf logische Adressen ab. Auf diese Art kann das Betriebssystem jedem Prozeß einen eigenen logischen Hauptspeicher zur Verfügung stellen. Man unterscheidet folgende Speicherzuweisungsstrategien:
        • einfache zusammenhängende Speicherzuweisung => nur ein Prozeß im Hauptspeicher
        • mehrfache zusammenhängende Speicherzuweisung => mehrere Prozesse im Hauptspeicher, jeweils kontinuierlicher Adressbereich
          Bei dieser Art der Speicherverwaltung für mehrere Prozesse unterscheidet man (mit Hilfe von Abkürzungen aus der IBM OS/360-Welt :
          • MFT (Multiprogramming with a fixed number of Tasks):
            Speicher wird in Segmente gleicher Größe geteilt => Prozessen werden z.T. zu große Segmente zugewiesen, dies führt zu interner Fragmentierung.
          • MVT (Multiprogramming with a variable Number of Tasks)
            variable Segmentaufteilung => nach der Terminierung von Prozessen entstehen Lücken zwischen Segmenten von ebenso variabler Größe => externe Fragmentierung
          • Strategien zum Auffinden von ‘passenden’ Speichersegmenten:
            First Fit, Rotating First Fit, Best Fit, Worst Fit, Buddy. Beim Buddy-Verfahren wird der Speicher rekursiv solange in zwei Hälften (Buddies) geteilt, bis eine Größe erreicht ist, die der der Prozeßgröße nächstgrößeren 2er Potenz entspricht. Beim Freigeben werden Buddies immer paarweise wiedervereinigt. Verwaltet werden Buddies in Listen oder Baumstrukturen.

        • nicht zusammenhängende Speicherverwaltung
          Trennung von Programm und Daten in verschiedene (kleinere) Segmente. Dadurch können Speicheranforderungen eher befriedigt werden.
        • Seitenorientierte Speicherzuweisung
          Hierbei handelt es sich ebenfalls um eine Form der nicht zusammenhängenden Speicherzuweisung. Der physische Hauptspeicher wird dabei in Abschnitte der Größe p unterteilt, die man pageframe nennt. Der logische Hauptspeicher eines Prozesses wird in Seiten der Länge p unterteilt; eine Speicherzelle berechnet sich dann zu s= x div p (Seitennummern) und d= x mod p (Speicherzellenadresse in der Seite s). Eine Seitentabelle ST verwaltet zu jeder Seite s eines Prozesses die Seitenrahmennummer in der diese Seite gerade gespeichert ist. Der Zusammenhang zwischen physischen und virtuellen Adressen ist gegeben wie folgt: r= ST[v div p] * p + (v mod p). Vorteil: Es werden jeweils nur die benötigten Seiten eingelagert, der logische Hauptspeicher kann problemlos (durch die HD) verlängert werden, Prozesse müssen nicht unbedingt durchgehenden Hauptspeicher besitzen, jede Seite ist individuell schützbar, platzsparender Code durch gemeinsame Nutzung von Seiten (shared memory/shared Libraries) möglich. Außerdem hat diese Strategie keine Probleme mit dynamisch - also zur Laufzeit - erzeugten Variablen, da einfach Speicherseiten angefordert werden können.

      2. Welche Strategien gibt es bei zusammenhängender Speicherverwaltung?
        Einfache Speicherverwaltung, MFT, MVT. Zum Auffinden des passenden Segmentes: First-Fit, Rotating-First-Fit, Best-Fit, Worst-Fit, Buddy

      3. Was versteht man unter einem virtuellen Hauptspeicher?
        Darunter versteht man einen logischen Adressraum, der in der Regel größer ist als der physische Hauptspeicher (Aber auch der umgekehrte Fall ist möglich: Man denke an die EMS-Spezifikation für 8086-Prozessoren). Man erreicht dies durch Einteilung des physischen Speichers in Seitenrahmen, wobei bei Bedarf Seiten auf den Hintergrundspeicher ein- oder ausgelagert werden können (demand Paging).
        Die Beobachtung, daß jeder Prozeß zu einem gegebenen Zeitpunkt mit einer Arbeitsmenge ("Working Set") an Code und Daten auskommt, die wesentlich kleiner ist als der gesamte Prozeß (Lokalitätsannahme), führt auf die Idee des Pagings bzw. Swappings: Es werden nur jeweils diejenigen Seiten in den Hauptspeicher eingelagert, die aktuell zur Arbeitsmenge eines Prozesses gehören. Der physische Speicher besteht aus den Seitenrahmen, während der virtuelle Speicher in Seiten unterteilt ist! Grundlage dieses Speichermodells ist die Lokalitätsannahme (s.o.). Vorteile: Nur ein Teil der Daten muß im Hauptspeicher gehalten werden, fast beliebig große Adressräume möglich, virtueller Speicher muß nicht durchgehend benutzt werden, memory mapped I/O ist möglich; darunter versteht man die ‘Einblendung’ von Speicherseiten aus Dateien in den virtuellen Arbeitsspeicher, so daß diese von einem oder mehreren Prozessen bearbeitet werden können.

      4. Wie werden die Seitenrahmen verwaltet?
        Die Seitenrahmen werden in einer Seitenrahmentabelle verwaltet, diese enthält zu jedem Seitenrahmen die zugehörige Seitennummer sowie den zugehörigen Prozeß.
        Zur Abgrenzung: Zu jedem Prozeß gibt es eine Seitentabelle in der für jede Seite des Prozesses die aktuell zugehörige Seitenrahmennummer verzeichnet ist.

      5. Was passiert wenn alle Seitenrahmen belegt sind?
        Dann müssen Seiten ausgelagert werden. Man vermeidet unnötige Auslagerungen mit Hilfe des sog. Dirty Bits einer Seite: Ist das Dirty-Bit (deutsch verändert oder referenziert Bit) zum Auslagerungszeitpunkt nicht gesetzt, dann existiert auf der Platte noch eine gültige Kopie und man kann sich das teure Zurückschreiben sparen. Auslagerungsstrategien sind: LRU least recently used, FIFO, Clock, Second Chance. LRU ist eine gute Strategie, die die Anzahl der Seitenfehler nahezu minimiert (Minimum erreicht der nur theoretisch denkbare ‘optimale Algorithmus’), LRU’s Hauptproblem ist die ineffiziente Implementierung, denn LRU braucht entweder ziemlich aufwendige Hardware oder benötigt unverhältnismäßig viel Laufzeit (Suchen, verschieben und löschen in verknüpften Listen). Es gibt jedoch ein ‘Aging’ genanntes Derivat von LRU das effizient implementierbar ist. Details in Tanenbaum, Moderne Betriebssysteme.

      6. Wie sollten die Seitenrahmen den einzelnen Prozessen zugeordnet werden? (feste oder variable Anzahl je Prozeß, wonach sollte sich die Zuteilung richten?)
        Ziel dabei ist eine niedrige Seitenfehlerrate und eine effiziente Speicherausnutzung. Den Prozessen werden variable Anzahlen Seiten - auf Verlangen - zugeteilt (‘demand paging’). Jeder Prozeß beginnt mit 0 Seiten - und einem Pagefault
        Durch empirische Ermittlung des Working Sets eines Prozesses bei früheren Läufen wird es möglich die Seiten dieses Working Sets schon vor dem Prozeß-Start zu laden und so die Seitenfehlerrate zu Beginn zu reduzieren.
        Weiter ist es möglich, die Anzahl der Seitenrahmen die einem Prozeß zur Verfügung stehen, bei jedem Seitenfehler zu erhöhen oder bei längerem Nichtzugriff auf bestimmte Rahmen die Anzahl der Seitenrahmen zu erniedrigen. Dieses Zuordnungsverfahren wird auch Arbeitsmengenstrategie genannt.

      7. Was passiert beim Einsatz einer schnelleren Platte?
        Die Seitenfehlerrate steigt, da die Übertragungszeit für Seiten sinkt. Die Anzahl der gleichzeitig ausführbaren Prozesse steigt, da jeder Prozeß nun mit weniger Seitenrahmen - und einer höheren Fehlerrate - ‘leben’ kann.

      8. Welche Problematik tritt bei der Arbeitsmengenstrategie auf?
        Seitenauslagerung durch Herausfallen der Seite aus dem Working Set; Seiten können aus dem Working Set ausgelagert werden, ohne das ein Seitenfehler aufgetreten ist und ohne das für diese Seite eine neue eingelagert worden wäre. Die aktuelle Lokalität wird eben nur approximiert. Die Arbeitsmenge enthält möglicherweise auch Seiten die nur einmal benutzt worden sind; der Übergang zu einer neuen Lokalität erfolgt eben nur allmählich.

      9. Welche Problematik tritt beim Beobachten der Seitenfehlerrate (bei der Seitenfehlerhäufigkeitsstrategie) auf?
        Eine Reaktion kann erst nach dem Auftreten eines Schadens (des Seitenfehlers) erfolgen.

      10. Wie funktionieren dynamische (globale) Seitenaustauschalgorithmen?
        Arbeitsmengenstrategie, Seitenfehlerhäufigkeitsstrategie (PPF page fault frequency) ansonsten s.o.

      11. Welche Gefahr besteht bei Seitenaustauschverfahren?
        Gefahr des Seitenflatterns (Trashing). Bei Überlastung mit zu vielen Prozessen die entweder zu viele Pagefaults produzieren und/oder zuwenig Seitenrahmen zur Verfügung haben, ist der Rechner weitgehend mit dem Ein-/und Auslagern von Seiten beschäftigt und kann an den eigentlichen Aufgaben der Prozesse kaum noch weiterarbeiten. Effektive CPU Auslastung sinkt durch viele Seitenfehler. Weitere Gefahr besteht dann durch zu einfach konstruierte Scheduler, die bei sinkender CPU-Auslastung mit einer höheren Prozeßintensität reagieren.

      12. Was kann man gegen Trashing tun?
        Scheduling einsetzen: Dadurch wird die Anzahl der gleichzeitig aktiven Prozesse verringert und jedem Prozeß stehen mehr Seitenrahmen zur Verfügung.

      13. Wie läuft bei statischer seitenorientierter Speicherverwaltung (besser: Seitenauslagerungsstrategie, denn die Verteilung der Pageframes ist ja statisch) der Seitenaustausch?
        Es wurden drei Strategien behandelt:
        • Optimale Strategie
        • LRU
        • FIFO

      14. Kann es dabei zu Trashing kommen?
        Ja. Z.B. wenn der verfügbare Speicher gleichmäßig auf eine Menge von Prozessen mit großem Speicherbedarf verteilt wird und die zugeteilte Menge für jeden Prozeß zu klein ist.

      15. Was tut man dagegen?
        Man legt einen der Prozesse schlafen und verteilt seine Seitenrahmen auf die übrigen Prozesse.

      16. Kann es bei der Arbeitsmengenstrategie zu Trashing kommen?
        Nein, denn es sind ja jedem Prozeß ausreichend viele Seitenrahmen zur Verfügung gestellt worden. Sind keine freien Seitenrahmen mehr vorhanden, dann wird ein Prozeß ausgelagert und seine Seitenrahmen werden zur Verfügung gestellt.
        Ausnahme: Ein einziger Prozeß ist noch aktiv und die Arbeitsmenge dieses Prozesses wird größer als der verfügbare Hauptspeicher.

      17. Welche dynamischen Seitenaustauschverfahren gibt es?
        • Arbeitsmengenstrategie
        • Kontrolle der Seitenfehlerrate

      18. Wodurch wird die Größe der Arbeitsmenge bestimmt?
        Alle Seiten die in ‘letzter Zeit’ (<100ms) benutzt wurden, gehören zur Arbeitsmenge. ‘In letzter Zeit’ wird auch als Fenster bezeichnet. Die Bestimmung des Zugriffes läuft über Zugriffsbits.

      19. Ist beim Arbeitsmengenverfahren Trashing möglich?
        Szenario: Ein Prozeß bläht sich auf, verdrängt alle anderen Prozesse aus dem Hauptspeicher. Kann dann seine Arbeitsmenge weiter wachsen?
        Erst dann wenn die Arbeitsmenge des verbliebenen Prozesses so groß wird, wie der physische Speicher kann es zum Trashing kommen.

    5. KE5 - Prozeßkommunikation

      1. Warum schaltet ein Prozeß der auf gemeinsame Daten/Resourcen zugreifen möchte, nicht einfach alle Interrupts ab?
        Führt zu keinem optimalen Scheduling, weil dann jeder Prozeß solange die Kontrolle behalten darf wie er will. D.h. die wartenden Prozesse sind auf die Kooperation des gerade laufenden Prozesses angewiesen: Daher kooperatives Multitasking (z.B. MS-Windows 3.XX).

      2. Was sind disjunkte und was sind überlappende Prozesse?
        Zwei Prozesse sind disjunkt, wenn sie nicht auf gemeinsame Daten zugreifen. Dies gilt auch dann, wenn sie zwar gemeinsam auf denselben Daten arbeiten, diese aber nur lesend nutzen. Man spricht erst dann von überlappenden Prozessen, wenn einer der Prozesse die gemeinsamen Daten auch schreibend verändert. Bei DBS heißen solche Transaktionen ‘in konfliktstehend’.

      3. Wie kann der Zugriff auf gemeinsame Daten realisiert werden?
        Unter konkurrenten Prozessen versteht man simultane oder parallele Aktivitäten. Überlappende Prozesse sind solche mit gemeinsam genutzten Daten. In einem kritischen Abschnitt eines Prozesses werden gemeinsam genutzte Ressourcen benutzt und verändert. Nicht gemeinsam benutzbare Betriebsmittel (z.B. periphere Geräte, veränderliche Daten) können von konkurrenten Prozessen nur in kritischen Abschnitten belegt werden um exklusive Ausführung und damit gegenseitigen Ausschluß zu gewährleisten. Man erreicht dies durch Prozeßsynchronisation. Wichtig ist hierbei die Vermeidung von zyklischem Warten (Deadlock).

      4. Wie können Prozesse miteinander kommunizieren?
        Durch Zugriff auf gemeinsame Daten, z.B. gemeinsame Dateien, Pufferspeicher oder shared Memory, Austausch von Nachrichten über Mailboxen, Rendevouz-Konzept (in ADA).

      5. Wie kann man Prozesse synchronisieren?
        Semaphor (globale Synchronisationsvariable), Monitor(=Lock-Manager in DBMS), Nachrichtenaustausch
        Diese Betriebsmittel zur Synchronisation sind äquivalent.

      6. Mechanismen des wechselseitigen Ausschlusses?
        Semaphore, atomare Operationen p(s) und v(s); Nachrichtenaustausch (Kommunikation zweier Prozesse über gemeinsamen Puffer oder Briefkasten); Monitore (Prozeduren oder Datenstrukturen, die nur von einem Prozeß zu einer Zeit benutzt werden können, analog zu einem Raum, für den es nur einen Schlüssel gibt); auf höherer Ebene Transaktionen.

      7. Funktionsweise der Semaphore?
        Semaphore sind ganzzahlige, nichtnegative globale Variable verbunden mit einer Warteschlange w(s). (E.W. Dijkstra, 1968)
        Es gibt zwei atomare Operationen:
        • P(s): if s=0 then wait; s:=s-1; (hol. passeer = hineingehen)
        • V(s): s:=s+1; if Wartelliste nicht leer then wecke nächsten Prozeß; (hol. verlaat = verlassen)

        Die Operation P wird von einem kritischen Prozeß ausgeführt, der einen kritischen Abschnitt betreten möchte. Ist gerade ein anderer Prozeß in dem gemeinsamen Abschnitt dann ist s=0 und es wird gewartet. Der Initialwert des Semaphors s bestimmt, wieviele Prozesse sich gleichzeitig in dem kritischen Abschnitt aufhalten dürfen. Beim Verlassen des kritischen Abschnittes wird s durch die Operation V wieder auf 1 gesetzt bzw. inkrementiert. Die Synchronisation mehrerer Ereignisse kann durch Listen von Semaphoren bewerkstelligt werden: P(s1,.....,sn), V(s1,.....,sn).

      8. Beschreiben Sie ein praktisches Anwendungsbeispiel von Semaphoren wo deren Anzahl bei 5 oder 6 liegt?!
        Bei einer Lösung des Philosophenproblems mit Semaphoren beträgt deren Anzahl beispielsweise 5.

      9. Was ist das Erzeuger-Verbraucher-Problem?
        Var inhalt:semaphor; inhalt:=0;
        Erzeuger Prozeß: repeat ErzeugeWare; BringeWareNachPuffer; V(inhalt); until(false);
        Verbraucher Prozeß: repeat P(inhalt); HoleWareAusPuffer; VerbraucheWare; until false;
        Dies ist das einfachste Beispiel, der Schutz der Operation Bringe/HoleNach/AusPuffer fehlt!

      10. Was versteht man unter Scheduling?
        Unter Scheduling versteht man das Koordinieren von konkurrenten Prozessen, das eine Maximierung der Auslastung und eine Minimierung der Antwortzeiten zum Ziele hat.
        • Scheduling ohne Preemption
          FCFS (First Come First Served)
          SJN (Shortest Job Next)
          HRN (Highest Response Ratio Next; Antwortzeit/Bedienzeit Verhältnis)
        • Scheduling mit Preemption
          Round Robin
          LCFS (Last Come First Served)
          DPRR (Dynamic Priority Round Robin)
        • Adaptive Prozessorzuteilung
          Erster adaptiver Zuteilungsalgorithmus
          (dynamische Änderung der Prozessorzuteilungspriorität)
          Zweiter adaptiver Zuteilungsalgorithmus
          (dynamische Änderung der der Prozessorzuteilungspriorität und dynamische Änderung der Zeitscheiben))

      11. Welche Zuteilungsstrategie sollte man wählen, wenn Bedienzeiten vorher bekannt sind und man die mittlere Antwortzeit minimieren will?
        Shortest Job Next (SJN). Nachteil: Aufträge mit langen Bedienzeiten ‘verhungern’, dies wiederspricht dem Implementationsziel ‘Fairness’.

      12. Warum läßt man nicht einfach alle Prozesse nacheinander vollständig ablaufen?
        Das sollte man im Batchbetrieb so machen, wo die Verweilzeit zu minimieren ist. Im Timesharingbetrieb muß nicht nur der Prozessor ausgelastet werden, sondern es kommt vor allem auf gleichmäßig kurze Antwortzeiten für alle Benutzer an. Dies wird mittels Mehrprogrammbetrieb erreicht.

      13. Welche Ziele verfolgt man mit einer Prozessor-Zuteilungsstrategie?
        • Fairneß ‘jeder kommt mal dran’
        • Effizienz Prozessor ist immer ausgelastet
        • Antwortzeit Antwortzeiten für interaktive Benutzer werden minimiert
        • Verweilzeit Wartezeit für die Ausgabe von Stapelaufträgen wird minimiert.
        • Durchsatz wird maximiert

      14. Welche Strategie ist bei Batch-Verabeitung sinnvoll?
        Die non-preemtive. Begründung:
        Man läßt einfach jeden Batch-Prozeß solange laufen bis er fertig ist (run-to-completion). Vorteil: Kein Overhead durch Prozeßverwaltung/umschaltung, einfach zu implementieren. CPU-Auslastung immer gleichmäßig hoch. Kann man machen, weil beim Batch-Betrieb nicht auf Antwortzeiten optimiert werden muß.

      15. Was bedeutet ‘Deadlock’ und wann liegt ein Deadlock vor (bezogen auf Betriebssysteme)?
        Unter Deadlock versteht man eine Systemverklemmung (zyklisches Warten). Beispiel Buchausleihe: Zwei Entleiher E1 und E2 benötigen jeweils identische Bücher A und B. E1 leiht zuerst A und E2 leiht zuerst B. Jetzt wartet E1 auf die Rückgabe von B und E2 auf die von A => Deadlock.
        Folgende allgemeine Bedingungen müssen für das Zustandekommen eines Deadlocks erfüllt werden:
        d(1) Bedingung des gegenseitigen Ausschlusses, Prozesse erhalten exklusive Kontrolle über Betriebsmittel
        d(2) Bedingung der Nichtunterbrechbarkeit (non preemtive), Betriebsmittel können nicht temporär zurückgegeben werden.
        d(3) Warte-Bedingung: Prozesse belegen exklusiv Betriebsmittel während sie noch auf weitere benötigte Betriebsmittel warten.
        d(4) Bedingung der geschlossenen Kette (circular wait), jeder Prozeß belegt mindestens ein Betriebsmittel das der nächste Prozeß in der Kette benötigt. (Schlingen im Wartegraph)

      16. Welche Prozesse sind an einem Deadlock beteiligt?
        Prozesse die mehrere Betriebsmittel mit jeweils exklusiven Zugriff benötigen.

      17. Wie kann man Deadlocks (im Voraus) erkennen?
        Exakt: Es muß die Unmöglichkeit eines kompletten Ablaufes aller im System befindlichen Prozesse gezeigt werden. Dies ist einerseits ein sehr komplexes Problem und andererseits ist das zukünftige Verhalten der Prozesse meist unbekannt.
        Zur Vereinfachung des Problems, kann jeder Prozeß vorab seine maximale Anforderung von Betriebsmitteln bekannt geben, der Prozeß führt seinen nächsten Schritt nur dann aus, wenn alle zukünftig benötigten Betriebsmittel zur Verfügung stehen (Preclaiming bei DBMS).
        Algorithmisch wird dies durch zyklische Prüfung (für jeden Prozeß) auf Vorhandensein der erforderlichen Betriebsmittel erreicht,

      18. Wie werden Deadlocks beseitigt?
        Abbruch der beteiligten Prozesse und Freigabe der belegten Betriebsmittel (entspricht den optimistischen Sperrverfahren bei DBMS).

      19. Wie werden Deadlocks vermieden?
        Exakte Lösung: Bei jeder Betriebsmittelanforderung wird geprüft, ob diese zu einem Deadlock führt. Nachteil: sehr aufwendig.
        Methode 2: Bei Anforderung zusätzlicher Betriebsmittel werden zunächst alle bisher reservierten Betriebsmittel freigegeben und dann zusammen mit den zusätzlichen Betriebsmitteln erneut angefordert (Form von Preclaiming).
        Methode 3 Betriebsmitteltypen werden linear angefordert (nach Priorität); wenn schon Betriebsmittel reserviert sind, können keine Betriebsmittel, die wichtiger sind als die schon reservierten, angefordert werden. Damit wird zyklisches Warten unmöglich (ähnelt dem 2-Phasen-Sperrprotokoll).
        Problem: Vergabe geeigneter Numerierungen, da reale und abstrakte Betriebsmittel (z.B. Spoolbereiche auf Festplatten)
        Methode 4: Banker Algorithmus: Ein Verfahren zu Erkennung sicherer Systemzustände bei der Verteilung von Ressourcen. Idee: Der Banker hat einen bestimmte Menge einer Ressource. Jeder Kunde hat ein Limit, bis zu dem er Ressourcen vom Banker bekommt. Der Banker hat aber so viele Ressourcen, daß er das größte vorhandene Limit bedienen kann. Der Kunde bekommt die Ressource, falls der Banker danach noch genügend Ressourcen hat, um mindestens einem der Kunden sein komplettes Limit zuteilen zu können.
        Beispiel dazu: Der Banker habe 10 Einheiten einer Ressource zur Verfügung. Das Limit von Kunde A betrage 8 Einheiten; das von Kunde B betrage 7 Einheiten. Aktuelle habe A 5 Einheiten belegt, B hat 2. Falls B nun eine weitere Einheit anfordert dann wird dies verweigert, dann hat der Banker nur noch 10-5-2-1=2 Einheiten übrig. Damit kann er keinem seiner beiden Kunden mehr sein Limit zuteilen und falls beide im nächsten Anforderungsschritt ihr Limit haben möchten müssen beide Prozesse warten => Deadlock. Solch ein Zustand heißt unsicher.
        Würde A noch eine Einheit fordern wäre das oK, da der Banker mit zwei Einheiten die Maximalanforderung von A noch befriedigen könnte. A kann dann sein Vorhaben irgendwann erledigen und seine Schulden zurückzahlen, so daß der Banker dann wieder genug Einheiten hat, um jemand anderem weitere Ressourcen zuzuteilen. Dieser Zustand heißt sicher.
        Schlußfolgerung bezogen auf Betriebssysteme: Jeder Prozeß muß im Voraus sagen, wieviele Einheiten eines Betriebsmittels er maximal braucht.

      20. Warum funktioniert die Deadlock-Vermeidung bei linearer Ordnung (beispielsweise durch eine Numerierung) der Betriebsmittel?
        (ähnelt dem Zeitstempelverfahren bei DBS)
        Dabei wird nach der Regel verfahren: Die Prozesse können alle Betriebsmittel anfordern, aber alle Anforderungen müssen gemäß der Numerierungsreihenfolge geschehen. Somit ist es ausgeschlossen, daß ein Prozeß der ein Betriebsmittel höherer Ordnung besitzt, ein Betriebsmittel niedrigerer Ordnung, das von einem anderen Prozeß belegt ist, anfordern kann. Also werden Schlingen im Wartegraph und damit Deadlocks vermieden (d4 fordert notwendig solche Schlingen!).

      21. Was versteht man unter einem Monitor und wie funktioniert er?
        Ein Monitor besteht aus einer Menge von Prozeduren, Variablen und Datenstrukturen die zu einer besonderen Art von Modul oder Paket zusammengefaßt sind. Dieses Monitormodul verkapselt Semaphore und die Operationen auf diesen Semaphoren. Nützlichste Eigenschaft eines Monitors ist, daß jeweils nur ein Prozeß zu einer Zeit einen Monitor benutzen kann.
        Ein Monitor ist - als Betriebsmittel betrachtet - vielen Prozessen zugänglich, aber nur jeweils ein Prozeß kann den Monitor zu einem gegebenen Zeitpunkt benutzen. Monitore werden häufig zur Verwaltung von Puffern und Geräten eingesetzt.

      22. Nennen Sie die Mechanismen des wechselseitigen Ausschlusses (mutual exclusion)?
        - Semaphore
        - Monitore
        - Signale (Nachrichten)
        - Ereigniszähler (im Kurs nicht behandelt)
        Dies sind Semaphore die nur inkrementiert und nie dekrementiert werden.

    6. KE6 - Sicherheit

      1. Welche Sicherheitsfunktionsbereiche gibt es?
        • Identifikation (User-ID) und Authentisierung (Paßwort): login-Prozedur
        • Zugriffskontrollen: Rechteverwaltung und Rechteprüfung; least privileg principle: jeder Benutzer sollte nur Rechte haben, die er unbedingt braucht; Dateien: r,w,x-Permission für user/group/others
        • Beweissicherung/Audit: Protokollieren sicherheitsrelevanter Ereignisse
        • Initialisierung von Speicherbereichen mit ‘sinnlosem’ Inhalt bevor dieser Bereich dem nächsten Prozeß zugewiesen wird.
        • Gewährleistung der Funktionsfähigkeit: Verhinderung eines provozierten Absturzes oder einer provozierten Fehlfunktion (Robustheit, Stabilität)
        • Sicherung von Datenübertragungen: Identifikation,/Authentisierung, Zugriffskontrolle, Sicherung von Vertraulichkeit und Integrität der Daten.

      2. Welche Arten von Zugriffskontrolle gibt es?
        • diskretionäre Zugriffskontrolle: Besitzer eines Objektes entscheiden ob und wie andere Subjekte auf dieses Objekt zugreifen dürfen => Vertraulichkeit und Integrität der Information kann nicht garantiert werden, weil jedes Subjekt seine Objekte öffentlich zugänglich machen kann. Es gibt folgende Zugriffsmodi: read, write, append, execute, navigate, delete, owner. Der Rechtezustand wird durch eine Zugriffskontrollmatrix (je Zeile ein Subjekt, je Spalte ein Objekt) repräsentiert.
        • granulatorientiert (in diesem Zusammenhang eigentlich objektorientiert): Rechte werden beim Objekt gespeichert (z.B. als Zugriffskontrolllisten ACL, Schutzbits bei UNIX entsprechend einer ACL mit drei Subjekten,
          für persistenten Rechtezustand)
        • subjektorientiert: Rechte werden beim Subjekt gespeichert (z.B. Profile, Capabilities (Ticket für das Objekt), für transienten Rechtezustand)
      3. informationsflußorientierte Zugriffskontrolle: Zugriffsbeschränkungen werden von den von einem Prozeß gelesenen Daten auf die erzeugten Daten vererbt. Label: jedes Objekt/Subjekt wird genau einer Vertraulichkeits- und genau einer Integritätsklasse zugeordnet; einfache Geheimhaltungsbedingung: Prozeß darf Objekt nur lesen, wenn die Vertraulichkeitsklasse des Prozesses dominiert; Ruhe-Prinzip: Ein Prozeß kann die Vertraulichkeitsklasse eines Objektes nicht verändern; Kommunikationsregel: Prozeß P1 darf P2 nur dann Daten senden wenn die Vertraulichkeitsklasse von P2 die von P1 dominiert.

    7. KE7 - Kommadosprachen

  2. Datenbanksysteme

    1. KE1 - Einführung - Architektur eines Datenbanksystems

      1. Was ist eine Datenbank und was unterscheidet sie von einem Filesystem?
        Eine Datenbank ist eine integrierte Ansammlung von Daten, die allen Benutzern eines Anwendungsbereiches als gemeinsame Basis aktueller Information dient. Mit Integration ist hier gemeint, daß die Daten entsprechend den natürlichen Zusammenhängen der Realwelt strukturiert sind und daß bestimmte Aspekte der Realwelt modelliert werden. Die Nutzung erfolgt durch viele Benutzer (die jeweils eine individuelle Sicht auf die Daten erhalten). Die Kontrolle liegt komplett beim DBMS.
        Bei der traditionellen Datenverwaltung mit Filesystemen definiert jeder Anwender seine eigenen Dateien (mit Sätzen die Felder enthalten). Daraus resultiert Redundanz, dadurch teures Update und Daten-Programmabhängigkeit, Inkonsistenzen sind sehr wahrscheinlich, insgesamt ist dieser Ansatz sehr inflexibel. Bei einer Datenbank hingegen erfolgt die Verwaltung der Daten zentral und es wird eine Unabhängigkeit der Daten von den Anwendungsprogrammen erreicht.

      2. Was versteht man unter Datenunabhängigkeit?
        Darunter versteht man die Unabhängigkeit von Anwendungsprogramm und Daten. Unter logischer Datenunabhängigkeit versteht man die Isolierung der Anwendung von Änderungen des konzeptuellen Modells (es ist keine Änderung der Anwendung beim Einfügen eines zusätzlichen Attributes oder eines Beziehungstyps nötig). Physische Datenunabhängigkeit hingegen bedeutet die Isolierung der Anwendung von der physischen Datenorganisation d.h. dem internen Modell (Hash, B-Tree, Heap oder z.B. Anlegen von Indizes - Dateninversion)

      3. Welche Änderungen im konzeptuellen Schema wirken sich auf die Anwendungsprogramme aus und welche nicht: Einfügen eines Attributes, Einfügen eines Entitätstyps, Änderung des Wertebereichs eines Attributes von Integer in Real?
        Nur die Wertebereichsänderung wirkt sich aus. Die übrigen Änderungen wirken sich wegen der Datenunabhängigkeit zwischen Daten und Anwendung nicht aus.

      4. Beschreiben Sie das Schichtenmodell eines Datenbanksystems!
        Sogenanntes Dreischichtenmodell:
        • konzeptuelle Ebene: logische Gesamtsicht, Zusammenfassung der Daten und ihrer Beziehungen auf logischer Ebene, Integritätsbedingungen, Beschreibung durch einen Datenbeschreibungssprache (data description Language = DDL)
        • interne Ebene: physische Datenorganisation; Aufbau der Sätze , Zugriffsmethoden für Sätze, Indizes, Verkettungen, interne Repräsentation der Daten - Speicherstruktur
        • externe Ebene: View für die/den Benutzer, Bearbeitung der Daten durch Datenmanipulationssprache (data manipulation language = DML)

      5. Aufgaben eines DBMS:
        • Definition einer DB
        • Aufnehmen, Verändern, Löschen, Selektieren (Abrufen) von Daten
        • Prüfung und Sicherstellung der Integrität
        • Recovery nach Systemabstürzen
        • Koordination mehrerer Benutzer
        • Datenschutz
        • Bearbeitung von Anfragen: Transformation externes-konzeptuelles-internes Schema
        • Kommunikation mit dem Betriebssystem
        • Steuerung des Systempuffers (DB-Cache)
        • Übergabe der Daten und von Statusinformationen (z.B. in User Working Area).

      6. Wie heißt das Modell für die konzeptuelle Ebene?
        ER-Modell: Entity (Entitätsmenge): Unterscheidbares Objekt der Realwelt, z.B. Projekt, Kunde, Mitarbeiter (Entität: lat. das Dasein eines Dinges gegenüber seiner Wesenheit)
        Relationship (Beziehung): z.B. istMitarbeiterVon.
        Attributierter Beziehungstyp: Attribute werden einer Beziehung zugeordnet.
        Jeder Entitätstyp besitzt Attribute, z.B. Mitarbeiter: name, pers_nr ....
        Schlüssel: Attributmenge um eine Entität zu identifizieren. Komplexität von Beziehungstypen: 1:1 (z.B. verheiratet), 1:n (ist Chef von), n:m (Student belegt Kurs)

      7. Wie werden Entitätsmengen und Beziehungen im ER-Diagramm dargestellt?
        Entitätsmengen: Rechtecke; Beziehungen: Rauten + Kanten, die die beteiligten Entitätsmengen verbinden.

      8. Wie werden Operationen auf Entitätsmengen im ER-Diagramm dargestellt?
        Beziehungen zwischen Entities: B(E1,E2,...,Ek), Beziehungen sind meist zweistellig

      9. Wie erfolgt die Bearbeitung eines DML-Befehls?
        • Interpretation durch das DBMS
        • Ermittlung der zugehörigen konzeptuellen Beschreibung
        • Transformation auf internes Schema/ Ermittlung der Zugriffspfade/Queryoptimierung
        • Ermittlung der Datenseite (Page)
        • prüfen ob Seite im Systempuffer(Cache) enthalten ggf. Anforderung vom Betriebssystem
        • Transformation der gelesenen Daten durch das externe Schema und Bereitstellung in der UWA (user work area) des Anwendungsprogramms
        • Bereitstellung von Statusinformation

    2. KE2 - physische Datenorganisation

      1. Wie sieht ein Index aus?
        Ein Index ist eine Abbildung einer Attributkombination auf Satzzeiger.
        DB-Tabelle A besitzt einen Index für Attributkombination B         ó Tabelle A ist invertiert bezüglich B. Indextabelle: Tabelle mit Einträgen der Form (Attributwert, Zeigerliste). Indexsequentielle Organisation: mehrstufiger Index (=Index für Index); Einfügen: bei nicht dichtem Index Speicherreserve, ggf. Überlaufbereich (‘overflow pages’), in bestimmten Abständen ist eine Reorganisation nötig

      2. Wie ist ein B-Baum definiert?
        Die Knoten eines B-Baumes sind Speicherblöcke gleicher Länge: Für einen B-Baum der Ordnung k gilt je Block mind. k, max 2k Sätze (außer der Wurzel); jeder Satz besteht aus einem Schlüssel K und einem Nichtschlüssel Teil W; Schlüssel sind aufsteigend sortiert; innerer Knoten mit m Schlüsseln hat m+1 Söhne; alle Blätter haben dieselbe Höhe h, e.g. alle Pfadlängen von der Wurzel zu den Blättern sind gleich.

      3. Wie kann man Verbindung zwischen Sätzen unterstützen?
        • durch Invertierung (Erzeugung von Indizes).
        • durch Listen und Ringe
          Die zu verbindenden Sätze werden in Listenstrukturen abgelegt.
          (schwierig bei n:m Beziehungen)
        • durch variable Zeigerfelder
          An jeden Satz wird eine Zeigerfeld variabler Länge angehängt, mit dessen Hilfe auf die zu verbindenden Sätze verwiesen wird.
        • durch Kettsätze
          Bei n:m Beziehungen zwischen Sätzen wird ein neuer Satztyp eingeführt in dem jedes Beziehungspaar durch einen Satzeintrag repräsentiert wird

    3. KE3 - Relationale Datenbanken I

      1. Was ist das relationale Datenmodell?
        Daten werden als Relationen (entsprechen Tabellen, Entitätsmengen) dargestellt; Zeile entspricht Entity, Spalte entspricht Attribut, Schlüssel: minimale Attributmenge die ein Tupel R        Í D1 x D2 x .... x Dn; Di: Domains, identifiziert. Relationsschema R(A1,....,An) spezifiziert eine Relation R mit den Attributen A1,....,An; jedem Attribut Ai ist ein Wertebereich dom(Ai) zugeordnet.

      2. Welche Abfragemöglichkeiten gibt es?
        • Relationenalgebra: Definiert Operationen auf Relationen, die neue Relationen erzeugen.
          Grundoperationen: Vereinigung , Mengendifferenz, kartesisches Produkt, Selektion (Auswahl bestimmter Tupel), Projektion(Auswahl bestimmter Spalten)
          Weitere Operationen: Join, Natural Join.
          Beispiel: (ANGEST[ANGNR=ANGNR]ANG_PRO)[PNR=17][NAME]
        • Relationenkalkül: Durch ein Prädikat (eine Bedingung) wird die Menge der gewünschten Tupel beschrieben;
          Beispiel: {t|q}, dabei ist t eine Liste von Attributnamen, q: Prädikat, z.B. {ANGEST.WOHNORT|ANGEST.BERUF=’Programmierer’}

      3. Welche Unterschiede gibt es zwischen Relationenalgebra und Relationenkalkül?
        Die Relationenalgebra stellt konstruktive Regeln zur Erzeugung neuer Relationen bereit, hier insbesondere die Grundoperationen (Vereinigung, Differenz, kart. Produkt, Selektion, Projektion) und zusätzlich die Operationen Join und Nat. Join.
        Der Relationenkalkül dagegen arbeitet mit deskriptiven Regeln. Mit seiner Hilfe wird die Menge der bei einer Abfrage gewünschten Tupel beschrieben indem eine Bedingung angegeben wird, die die Tupel erfüllen müssen.

      4. Sind Abfrageergebnisse im Voraus beweisbar?
        Bei der Relationenalgebra ist eine sichere Bestimmung des Ergebnisses möglich, da konstruktive Regeln verwendet werden.

      5. Formulieren Sie bitte eine Abfrage in Relationenalgebra und in Relationenkalkül!
        Relationenalgebra: ANGEST[Name=’Meier’][Gehalt]
        Relationenkalkül: {ANGEST.Gehalt|ANGEST.Name=’Meier’}

      6. Wie werden Entitätstypen und Beziehungen in relationalen Datenbanken dargestellt?
        Beide werden als Relationenschemata dargestellt.

      7. Was ist das Ergebnis einer Selektion/Projektion auf einer Relation?
        Wiederum ein Relation.

      8. Was ist die teuerste Operation der Relationenalgebra?
        Der unqualifizierte Join ist die teuerste Operation, denn er ergibt das kartesische Produkt zweier Mengen und bildet somit bei zwei Tabellen der Mächtigkeiten n und m eine neue Relation der Mächtigkeit nm.

      9. Wie stellt man den Join in SQL dar?
        Seien R(A1,.....,An) und S(B1,....,Bm) Relationen.
        In Relationenalgebra: R[Ai=Bj]S
        In SQL: SELECT A1,.....,An,B1,....,Bm FROM R, S WHERE Ai=Bj

      10. Wie stellt man den Natural Join in SQL und in Relationenalgebra dar?
        Seien S(s1,..,sn,a1,..,am) und R(r1,..,rk,a1..am) Relationen mit gleichen Attributennamen a1..am die sowohl in S als auch in R vorkommen.
        • SQL:
          Select S.s1,...,S.sn,S.a1..S.am,R.r1,..,R.rk Where S.a1=R.a1,..,A.am=R.am
        • Relationenalgebra:
          R NATJOIN S:=(RxS)[S.a1=R.a1,..,A.am=R.am][S.s1,...,S.sn,S.a1..S.am,R.r1,..,R.rk]

      11. Wie stellt man einen Join zwischen einer Relation mit sich selbst dar?
        Diese Auto-Join genannte Operation gelingt mit Hilfe der Verwendung von Tupelvariablen:
        1. Relationenkalkül:
          RANGE ANGEST X
          RANGE ANGEST Y
          {Y.Name| (X.Gehalt > Y.Gehalt)           Ù (X.Name = Y.Vorgesetzter)}
        2. Relationenalgebra:
          Y[Y.Gehalt > X.Gehalt][X.Name = Y.Vorgesetzter]X [Y.Name]
        3. SQL: SELECT Y.Name FROM Angest X, Angest Y WHERE X.Name = Y.Vorgesetzter AND Y.Gehalt > X.Gehalt

      12. Wozu benötigt man Tupelvariablen?
        Tupelvariablen sind immer dann nötig , wenn der Verbund einer Relation mit sich selbst gebildet werden soll. (siehe 2.3.10) oder dann, wenn bei einem Join von zwei verschiedenen Tabellen Attribute mit gleichen Namen auftreten.
        Anders ausgedrückt: Immer dann wenn innerhalb einer Abfrage verschiedene Tupel derselben Relation betrachtet werden, braucht man Tupelvariable.

      13. Wohin wird SQL übersetzt?
        SQL wird direkt vom Datenmanager interpretiert.

    4. KE4 - Relationale Datenbanken II

      1. Wozu dienen Normalformen?
        Normalformen dienen der Vermeidung von Anomalien und zur Vermeidung von Redundanz.
        Beispiel:
        LIEFER(Lieferant, Artikel,Adresse, Preis)
        Einfüge-Anomalie: Lieferant ohne Artikel (bisher keine Lieferung) kann nicht berücksichtigt werden.
        Lösch-Anomalie: Löschen eines Artikels führt möglicherweise auch zum Verlust des Lieferanten.
        Änderungsanomalie: Bei einer Preisänderung eines Artikels muß die ganze Relation durchsucht werden

      2. Wie sind die verschiedenen Normalformen definiert und wie kann man sie anschaulich erklären?
        1.NF: Die Attributwerte sind unteilbar. (d.h. keine mengenwertigen Attribute)
        2.NF: Jedes Nichtschlüsselattribut A von R ist voll funktional abhängig von jedem Schlüssel S von R (und nicht nur von Teilen des Schlüssels)
        3.NF: Für alle implizierten Abhängigkeiten S        ® A mit A Ï S gilt: S enthält einen Schlüssel oder A ist Schlüsselattribut(d.h. es gibt keine Abhängigkeiten zwischen Nichtschlüsselattributen einer Relation)
        BCNF (Boyce Codd Normalform): Für jede funktionale Abhängigkeit S        ® A gilt: S enthält einen Schlüssel für R. (d.h. es gibt keine Abhängigkeit zwischen Nichtschlüsselattributen und Schlüsseln)

      3. Was bedeutet funktionale Abhängigkeit?
        Sei R(A1,...,An), X,Y         Í {A1,...,An}
        Y ist voll funktional abhängig von X: X        ® Y: es gibt keine Relation vom Typ R in der 2 Tupel denselben Wert für X aber verschiedene Werte für Y haben (==wenn 2 Tupel denselben Wert für X haben, dann haben sie auch denselben Wert für Y).
        Fd-Menge=Menge der funktionalen Abhängigkeiten (funcional dependencies); F+=Closure von F=Menge der funktionalen Anhängigkeiten die von F impliziert werden.

      4. Was muß man bei der Ausführung von SQL-Anfragen tun?
        • Optimierung der Anfrage
        • Transformation in konzeptuelles und internes Schema
        • Beschaffen der benötigten Sätze und Transformation in externes Schema; Realisierung durch Datenmanager (Mengenschnittstelle); Zugriffsmanager (Ein-Tupel-Schnittstelle); Systempuffer(Cache)Manager (Seitenschnittstelle)

      5. Wie werden relationale Datenbanken implementiert? Schichten eines DB-Systems?
        • Datenmanager: Mengenschnittstelle, Übersetzt und optimiert die Anfragen, Integritäts- und Zugriffskontrolle
        • Zugriffsmanager: 1-Tupel-Schnittstelle, Einfügen/Löschen/Suchen/ Ändern von Tupeln, Operatoren für Schemata, Transaktionsmanagement
        • Systempuffermanager: Seitenschnittstelle (bei Bedarf Anforderung von neuen Seiten vom Betriebssystem; pinned pages (Seiten die im Cache sind und nicht beliebig in die DB geschrieben werden dürfen), forced output (Seiten müssen ‘durchgeschrieben’ werden))

      6. Wie erfolgt die Adressierung für physische Sätze?
        Man unterscheidet physische, seitenbezogene, logische Adressierung.
        Die Adresse besteht aus zwei Komponenten: Adresse der Datei und Position innerhalb der Seite. Der Zugriffsmanager ermittelt die benötigte Seite , diese wird vom Systempuffermanager angefordert, der diese bei Bedarf durch einen Betriebssystemaufruf vom Externspeicher anfordert.

      7. Wie werden Tupeladressen berechnet?
        Der Datenmanager fordert Tupel mit bestimmten Attributwerten an, die Adressen werden über Indizes vom Zugriffsmanager bestimmt.

      8. Wie erfolgt die Optimierung von Abfragen? Was ist bei Projektionen zu beachten?
        • Selektionen möglichst früh vornehmen um die Ergebnismenge klein zu halten
        • Zusammenfassung von Selektionen zu komplexen Selektionen da dies die Zahl der Zugriffe auf die Daten minimal hält.
        • Bei Projektionen zuerst diejenigen Attribute nehmen, die keine Eliminierung von Duplikaten erfordern, dann möglichst früh (also wenn mindestens ein Schlüssel des Relationenschemas erhalten bleibt), sonst möglichst spät.
        • Suche nach gemeinsamen Teilbäumen im Operatorbaum und Vereinigung dieser Bäume (Blätter: Relationen, innere Knoten Operationen, Selektion, Join, Projektion)
        • Joins möglichst spät
        • Optimierung auf physischer Ebene: Ausnutzung von Sekundärindizes (Invertierung), Sortierung, Speicherstruktur der Datenbanktabellen

      9. Wie wird ein Join ausgeführt?
        Beispiel: R(A,D), S(B,C); Gesucht R[A=B]S
        • einfach und ineffizient: für jedes Tupel in R mit A=a wird S durchsucht nach B=a
        • mit Sekundärindex: Index weist jedem a die Tupelmenge in S mit B=a zu
        • mit Sortierung: R und S werden sortiert (bezgl. A bzw. B), dann werden R und S parallel durchlaufen.

    5. KE5 - Netzwerkorientierte/Hierarchische Datenbanken, Transaktionen

      1. Was sind Netzwerkdatenbanken?
        Logischer Satz (entspricht der Entität im Rel. Modell), Felder des Satzes (Attribute), Beziehungstypen: Set-Typ (B:Owner-Typ, Member-Typ), entspricht 1:n Beziehungstyp (beim Netzwerkmodell gibt es nur 1:n Beziehungstypen) vom Owner-Typ zum Member-Typ, Satzweise Verarbeitung; Navigieren mit den Sets; Currency-Konzept: Bezug von DML-Befehlen auf aktuelle Positionen im Netzwerk.

      2. Wie werden bei Netzwerkdatenbanken Beziehungen und Entitäten dargestellt? (Vergleich zu relationalen Datenbanken)
        Entität mit ihren Attributen entspricht dem logischen Satz mit Feldern. 1:n Beziehungstyp entspricht Set-Typ (vom Owner-Typ zum Member-Typ); n:m Beziehungstyp wird indirekt dargestellt: E-E’ => E-EK-E’ (analog zu Kettsätzen); im Unterschied zu relationalen Datenbanken wird bei Netzwerkdatenbanken im Netzwerk navigiert, d.h. mit dem Currency-Konzept auf den jeweils aktuellen Satz zugegriffen.

      3. Wie lautet die Definition der Serialisierbarkeit von Schedules?
        Ein paralleles System von Transaktionen ist serialisierbar genau dann, wenn es eine serielle Ausführung derselben Transaktion gibt , die denselben Datenbankzustand und dieselben Ausgabedaten wie die Summe der Einzel-Transaktionen erzeugen.

      4. Was bedeutet ACID-Prinzip?
        Atomicity, Consistency, Integrity, Durability von Transaktionen

      5. Was passiert alles bei einem Commit?
        • After-Images müssen zu diesem Zeitpunkt im Log stehen
        • Before-Images können verworfen werden
        • Datenbank kann muß aber nicht geschrieben sein (Daten können sich auch noch im Systempuffer befinden)
        • Daten werden für die Außenwelt sichtbar

      6. Was sind die Kostenkriterien einer Transaktion?
        CPU-Intensität, I/O-Intensität

      7. Kann eine Transaktion zwischen BOT und EOT ein Dokument mit rechtlichem Charakter erzeugen?
        Nein, die Daten sind erst nach EOT bzw. nach dem abschließenden Commit ‘amtlich’. Falls eine Dokument zwischen BOT und EOT amtlich wäre, dann wäre im übrigen die Rücksetzbedingung (siehe 2.6.5) verletzt.

      8. Welche Sychronisationsverfahren für Schedules gibt es?
        • verifizierend (optimistisch, validierend): Vor dem Commit wird geprüft, ob eine Transaktion an einer nichtserialisierbaren Schedule beteiligt ist; falls ja, dann wird die Transaktion abgebrochen. (abort)
          Die Prüfung auf Serialisierbarkeit wird auch certification bzw. validation genannt.
        • präventiv (pessimistisch): nicht-serialisierbare Schedules werden verhindert, v.a. durch Sperrverfahren (selten Zeitstempelverfahren)

      9. Wie funktioniert das Sperren bei Datenbanken?
        Verwaltung der Sperren durch den Lock-Manager: Lock a=Objekt wird angefordert; unlock a= Objekt wird freigegeben. Alle Locks werden in einer Sperrtabelle eingetragen.
        • Sperrprotokoll: Wie müssen Sperren gesetzt und freigegeben werden, damit serialisierbare Schedules entstehen? Zwei-Phasen-Sperrprotokoll
        • Sperrmodi - Welche Arten von Sperren benötigt man?
          Shared-Lock, Exclusive-Lock, Intendierter Lock, ‘kurze Sperre’
        • Welches sind die sperrbaren Einheiten in einer Datenbank?
          Databaselock, Tablelock, Datasetlock darüber hinaus noch Arealock um Teile einer Datenbank zu Sperren
        • Sperrhierarchie - Datenbank - Area - Tabelle - Tupel/Seite (Lock-Escalation)
        • Deadlock-Behandlung (tritt bei exklusiven Sperren auf) wobei Schedules wechselweise auf Freigabe einer Sperreinheit warten
        • Livelock: durch wiederholt ungünstige Zuteilung von Sperren kann eine Transaktion permanent blockiert werden.

      10. Wie ist das Deadlock-Problem bei Transaktionen zu behandeln?
        • Verhinderung: Preclaiming, Zeitmarken auf Transaktionen (Timeouts)
        • Erkennung: Timeout und Prüfung des Wartegraphen auf Schlingenfreiheit oder Kombination beider Verfahren (Aufbau des Wartegraphen bei Timeout)

      11. Erläutern sie die Deadlock-Problematik!
        Deadlock: zyklisches Warten durch exklusive Zugriffs-Anforderung (exklusive Locks) mehrerer Schedules auf die gleichen Objekte.

      12. Wie erkennt man Deadlocks und löst sie auf?
        Prüfung auf Zyklen im Warte-Graph; gerichtete Kante von Ti nach Tj, wenn Ti auf Tj wartet. Auflösung: billigste Transaktion wird zurückgesetzt.

      13. Wann prüft man auf Deadlocks?
        Prüfung auf Zyklen im Wartegraphen: nach Einfügen einer Kante, in bestimmten Intervallen, wenn eine Transaktion über eine gewisse Zeit gewartet hat (Timeout)

      14. Was ist der Unterschied zwischen Deadlock und Timeout?
        Timeout: eine bestimmte Transaktion wartet auf ein Objekt länger als eine bestimmte Maximalzeit, trotzdem kann eine korrekte Fortsetzung möglich sein.
        Deadlock: mindestens zwei Transaktionen warten jeweils auf die andere => unendliches Warten. Auflösung ist nur durch Abbruch einer Transaktion möglich.

      15. Man erläutere das 2-Phasen-Sperrprotokoll!
        Nach dem ersten Unlock eines Transaktionssystems werden von dem TS keine weiteren Sperren mehr angefordert. Die Anzahl der Locks durchlaufen also eine Wachstumsphase und eine Schrumpfungsphase, ein solches Transaktionssystems ist serialisierbar.

    6. KE6 - Transaktionsmanagement II, Integrität

      1. Wie sehen optimistische Verfahren aus?
        • Arbeitsphase: nur lesender Zugriff auf die Datenbank (=> kein Rollback nötig), Zwischenspeicherung in privatem Arbeitsbereich
        • Validationsphase: Prüfung auf Nicht-Serialisierbarkeit der entstandenen Schedule ó Abhängigkeitsgraph hat Zyklen
          Definition der Abhängigkeit: (S: Schedule (=Folge von Lese und Schreiboperationen); T:Transaktionen in S; Konflikt zwischen zwei Operationen besteht wenn: Zugriff auf dasselbe Objekt, davon mindestens ein Schreibzugriff, Ty ist abhängig von Tx gdw. es Operationen ax und by gibt die in Konflikt miteinander stehen und ax vor by in S ausgeführt werden soll. Der Abhängigkeitsgraph ist dann G(S)=(T,U); (Ty,Tx)          Î Uó Ty abhängig von Tx
        • Schreibphase: veränderte Objekte werden in die Datenbank geschrieben => Commit.

      2. Was genau passiert in der Validationsphase, welche Operationen werden hier betrachtet?
        Es genügt schreibende Zugriffe parallel ablaufender Transaktionen zu betrachten und zu vergleichen mit den Lese- und Schreiboperationen der Transaktion für die die Validation durchgeführt wird. Prüfung auf Zyklen im Abhängigkeitsgraph (Knoten: Transaktionen; gerichtete Kanten zu jeweils abhängigen Transaktion ; Abhängigkeit: min. eine Operation steht im Konflikt mit einer vorher in der Schedule stehenden Operation einer anderen Transaktion)

      3. Wie kann man Transaktionen synchronisieren?
        Durch den Einsatz von Synchronisationsverfahren:
        • verifizierende Verfahren (optimistisch)
        • präventive Verfahren (pessimistisch)
          z.B. Sperrverfahren, Zeitstempelverfahren

      4. Warum benutzt man bei Datenbanken keine Semaphore?
        Semaphore stellen bei Betriebssystemen den exklusiven Zugriff auf Betriebsmittel durch Prozesse sicher, dies garantiert im Falle der DB-Transaktionen aber keine Serialisierbarkeit! Exklusive Sperren machen Deadlocks erst möglich (siehe Deadlockvoraussetzungen bei Betriebssystemen)!

      5. Wann ist eine Transaktion rücksetzbar?
        • Rücksetzbarkeitsbedingung für Lesen: Transaktion T kann erst dann abgeschlossen werden, wenn alle Transaktionen, von denen T Daten gelesen hat, abgeschlossen sind.
        • Rücksetzbarkeitsbedingung für Schreiben: Eine Transaktion darf ein Objekt erst schreiben, wenn alle Transaktionen, die x zuvor geschrieben haben, abgeschlossen oder abgebrochen sind.
        • strikte Ausführung: Transaktion T darf ein Objekt x erst schreiben oder lesen wenn alle Transaktionen, die x geschrieben haben, abgeschlossen oder abgebrochen sind.

      6. Wie kann man Deadlocks erkennen und behandeln?
        Erkennung durch Prüfung des Wartegraphen auf Schlingenfreiheit, Behandlung durch Abbrechen der billigsten Transaktion bzw. durch den Einsatz von präventiven Synchronisationsverfahren.

      7. Warum ist Deadlockvermeidung unrealistisch?
        Bei Produktionsdatenbanken hat man es mit einer großen Zahl sich fortlaufend ändernder Objekte zu tun. Zwischen diesen Objekten bestehen nahezu beliebig komplexe Querbezüge. Die Anzahl der benötigten Sperren ist in der Regel unbekannt. Beim Preclaiming wird zudem die Parallelität der Transaktionen und damit die Gesamtperformanz eingeschränkt.

      8. Was ist der Unterschied zwischen pessimistischen und optimistischen Verfahren
        Pessimistische Verfahren garantieren die Serialisierbarkeit von Transaktionen, optimistische Verfahren stellen die Parallelisierung in den Vordergrund und brechen beim Eintreten eines Deadlocks eine der beteiligten Transaktionen ab.

      9. Wie arbeiten optimistische Verfahren?
        Abhängigkeitsgraph bei Commit auf Serialisierbarkeit (=Zyklusfreiheit) prüfen. Falls Zyklen auftreten, Transaktion abbrechen

      10. Können bei optimistischen Verfahren Deadlocks entstehen?
        Nein! Ohne Sperren kein Deadlocks!

      11. Bei welchen Synchronisationsverfahren können Deadlocks auftreten?
        Sperrverfahren, wenn man 2-Phasen-Sperrprotokoll oder Sperren bis EOT verwendet.

      12. Wie geht das Rücksetzen einer Transaktion vonstatten?
        Rücksetzen (Undo): Schreiben der before-Images in umgekehrter Reihenfolge; bei optimistischen Verfahren nicht nötig, da Schreiben erst nach der Validationsphase. Im Log befindet sich ein Mitschnitt der Aktivitäten der Transaktionen.
        Im physischen Log werden die Werte von Datenbankobjekten vor und nach Änderungen durch Transaktionen gespeichert (before-/after Image); im Log wird eine Marke für BOT sowie EOT gesetzt. Für ein etwaiges Rollback vor EOT wird ein before Image im Log gesichert. Ebenso wird unmittelbar vor EOT noch ein after-Image der Transaktion ins Log geschrieben. Dies dient zum Recovery nach Speicherfehlern und zum Wiederholen von nach dem letzten Checkpoint beendeten Transaktionen z.B. nach Systemzusammenbrüchen
        Im logischen Log werden die durchgeführten Operationen gespeichert.

      13. Welche Transaktion wird bei einem Deadlock zurückgesetzt?
        Die billigste Transaktion wird zurückgesetzt.
        Kosten stellen hierbei die Anzahl der erforderlichen DB-Zugriffe, die CPU-Zeit und die Anzahl der abzubrechenden Transaktionen (Rollbacks) dar.
        Also sollte diejenige Transaktion mit der geringsten Anzahl an Datenänderungen/-selektionen und mit der geringsten CPU-Intensität zurückgesetzt werden!

      14. Was passiert bei einem Undo?
        Bisherige Änderungen durch die Transaktion werden dadurch rückgängig gemacht, daß aus dem Logfile das before-Image in die Datenbank zurückgeschrieben wird. Beim Undo wird das Log-File rückwärts durchlaufen (bei einem Redo dagegen vorwärts); ggf. wird ein fortgepflanzter Rollback angestoßen, da durch das Rücksetzen einer Transaktion alle von ihr abhängigen Transaktionen auch zurückgesetzt werden müssen.

      15. Welche beiden Nachrichten enthält implizit die Ready-To-Commit-Meldung einer Subtransaktion?
        Es ist jederzeit ein Undo oder ein Redo möglich.

      16. Erläuterung des Recovery bei einem Systemstart (nach einem Absturz):
        Sei TC die Menge der zum Zeitpunkt eines Systemabsturzes aktiven Transaktionen.
        • Undo/Redo: Durchsuche das Log vom Abbruch bis zum letzten Checkpoint, führe ein Undo aus für die in dieser Zeit nicht abgeschlossenen Transaktionen, für die übrigen Transaktionen aus TC ein Redo
        • Undo/No-Reado: physikalisches Schreiben vor dem Commit (schlecht bei Hot-Spots), für die seit dem letzten Checkpoint nicht abgeschlossenen Transaktionen wird ein Undo ausgeführt,
        • No-Undo/Redo: nur abgeschlossene Objekte werden in die Datenbank geschrieben, für die seit dem letzten Checkpoint nicht abgeschlossenen Transaktionen wird ein Redo durchgeführt.
        • No-Undo/No-Redo: Alle Änderungen werden vor Commit in einer einzigen atomaren Operation die Datenbank geschrieben. Damit dies performant machbar ist, wird Shadowing angewendet. Nachteil: Jeder Zugriff auf das DBS ist indirekt, durch das Anfertigen von Kopien (Shadow) werden die Daten in schwer zu kontrollierender Weise über die Hintergrundspeicher verteilt.

      17. Wie lange muß man before und after-images aufheben?
        Before-Images werden für das Rollback von Transaktionen im Falle von Transaktionsfehlern oder Systemzusammenbrüchen benötigt, Speicherung von BOT bis EOT
        After-Images: werden für Recovery nach Speicherfehlern und für das Wiederholen von nach dem letzten Checkpoint beendeten Transaktionen im Falle eines System-Zusammenbruches benötigt. Speicherung unmittelbar vor EOT bis zum nächsten Dump / Checkpoint.

    7. KE7 - neuere Entwicklungen