Prüfungsteilnehmer | Prüfungstermin Einzelprüfungsnummer Kennzahl: Kennwort: Herbst 661 1 A 2009 Fach: . Informatik (vertieft studiert) Einzelprüfung: Datenbank- und Betriebssysteme Anzahl der gestellten Themen (Aufgaben): 4 Aufgaben, von denen zwei gemäß untenstehender Auswahlregeln zu bearbeiten sind! Anzahl der Druckseiten dieser Vorlage: 14 Zu den zwei Themenschwerpunkten A (Datenbanksysteme) und B (Betriebssysteme) ist jeweils entweder die Aufgabe 1 oder 2 zu wählen. Auf der Vorderseite des Kopfbogens sind im Feld „gewähltes Thema: Nr.“ die Nummern der beiden gewählten Aufgaben anzugeben (z.B. A2, Bl)! Bitte wenden! Herbst 2009 Einzelprüfungsnummer 66114 Seite 2 Themenschwerpunkt A (Datenbanksysteme) Aufgabe 1 1. ER-Modellierung Sie wurden beauftragt, eine Internetanwendung zu entwickeln, die deren Nutzern folgende Möglichkeiten geben soll: 1. Ein Benutzer soll sich am Portal anmelden können. Der Zugang ist passwortgeschützt. Vorname und Name sowie die Emailadresse sollen im Profil gespeichert, aber veränderbar sein. 2. Ein Benutzer kann die Utensilien seiner Küche, also Töpfe, Pfannen, Kochlöffel usw. in seinem Profil speichern. 3. Ein Benutzer soll Gerichte finden können. Jedes Gericht soll über ein Foto, eine Geschichte und eine Anleitung, dem Kochrezept, verfügen. Weiterhin soll bekannt sein, welche Utensilien zur Zubereitung benötigt werden. So können auf Wunsch auch nur die Gerichte angezeigt werden, die mit dem Besitz des Kochfreundes zubereitet werden können. 4. Bei Wahl eines Gerichtes soll auf Wunsch eine Zutatenliste ausgegeben werden können. Erstellen Sie ein minimales E/R-Diagramm für die zugrunde liegende Datenbank eines fiktiven Webportals für Kochfreunde! Attribute von Beziehungen und Entitäten sind anzugeben. Kennzeichnen Sie die Schlüsselattribute durch Unterstreichen. Die Kardinalitäten von Beziehungen sind anzugeben. Verwenden Sie zur Angabe der Kardinalität die (Min, Max)-Notation. Modellieren Sie die Zutaten als Entität, die Menge und Maß (Prise, Gramm, Liter,...) enthält. 2. Relationenmodell Überführen Sie folgendes ER-Diagramm in ein Relationenschema in dritter Normalform (3. NF)! Wie gewohnt werden dabei Primärschlüssel durch Unterstreichen, Fremdschlüssel durch Überstreichen kenntlich gemacht! Fortsetzung nächste Seite! Herbst 2009 _ Einzelprüfungsnummer 66114 Seite 3 Agenturen 0 0 Schauspieler Produzenten Budget Filme en) — . C eter) drehen ene» — Regisseure 3. SQL Gegeben sei folgende Datenbank, die das Ausleihwesen einer Bibliothek unterstiitzt: LESER(LsNr, Name, Wohnort, GebDat) BUCH(ISBN, Titel, Seitenzahl, Verlag, Erscheinungsjahr, Anzahl-Exemplare) VERLAG(Verlag, Verlagsort, Adresse) EXEMPLAR(ISBN, ExpNr, InventarNr, Standort) AUSLETHECSBN, ExpNr, LsNr, Ausleihdatum) Datenänderungen: a) Geben Sie eine SOL-Anweisung an, um einen neuen Datensatz für den Leser Bernd Bücherwurm aus München anzulegen, der sein Geburtsdatum vergessen hat. Die zugewiesene Leser-Nummer (LsNr) soll um 1 größer als die bisher größte sein. b) Formulieren Sie folgenden SQL-Code in natürlicher Sprache: DELETE FROM Ausleihe WHERE Ausleihdatum < 16.8.2008 AND LsNr = (SELECT LsNr FROM Leser WHERE Name=’Bernd Biicherwurm’) Bemerkung: Es gibt nur einen Leser mit diesem Namen. Fortsetzung nächste Seite! Herbst 2009 | Einzelprüfungsnummer 66114 Seite 4 Anfragen: c) Welche Leser (Name) haben ein Buch mit dem Titel „Der Zauberberg“ ausgeliehen? d) Welche Leser (LsNr) haben mehr als ein Exemplar desselben Buchs ausgeliehen? e) An wie vielen Orten sind die Verlage ansässig, von denen die Bibliothek Bücher hat? f) Wie viele Buchexemplare gibt es in der Bibliothek von Büchern, die zwischen 1978 und: 1983 (Jahreszahlen jeweils inklusive) erschienen sind und die im Titel die Wörter „Informatik“ oder „Mathematik“ enthalten, und wie hoch ist ihre durchschnittliche Seitenzahl? Fortsetzung nächste Seite! Herbst 2009 Einzelprüfungsnummer 66114 Seite 5 Aufgabe 2 1 Datenbanksysteme und Modelle Die Entwicklung der ersten Datenbanksysteme begann in den frühen 60er Jahren. Seitdem haben sie die Datenverwaltung auf der Grundlage einfacher Betriebssystemdateien auf vielen Gebieten abgelöst. a) b) c) 2 Definieren Sie den Begriff Datenbanksystem und grenzen Sie die Funktionalitäten eines Datenbanksystems von denen eines Dateisystems ab! Nennen Sie die Phasen des Datenbankentwurfsprozesses und charakterisieren Sie diese kurz! Entity-Relationship-Modell - Erläutern Sie die nachfolgenden Konzepte eines ER-Modells! - Entitat Relationship/Beziehungstyp Attribut Kardinalitat Konsistenz in Datenbanksystemen Transaktionen sind ein wichtiges Konzept in Datenbanksystemen. Sie führen stets eine Datenbank von einem konsistenten Zustand in einen konsistenten Zustand über. a) b) c) d) e) Was bedeutet Konsistenz im Zusammenhang mit Datenbanken? Was versteht man unter dem ACID-Prinzip? Welche Konsequenzen im Verhalten des Datenbanksystems hat das ACID-Prinzip für den Anwender und Entwickler? Darf innerhalb einer Transaktion ein inkonsistenter Zustand vorliegen? Begründen Sie die Antwort! Welche Arten von Integritätsbedingungen können Sie mit SQL darstellen? Geben Sie Beispiele! - Was ist ein Trigger und wie funktioniert er? Fortsetzung nächste Seite! Herbst 2009 Einzelprüfungsnummer 66114 Seite 6 3 ER-Modellierung und Relationenmodell 3.1 ER-Modellierung Eine Stadtbücherei möchte ein neues Ausleihsystem entwickeln. Erstellen Sie ein Modell der beschriebenen Stadtbücherei in ER-Notation. Wo möglich bzw. sinnvoll, sollen ternäre Beziehungen, schwache Entitätstypen und Generalisierung/Spezialisierung verwendet werden. Attribute von Entitäten und Beziehungen sind anzugeben; Schlüsselattribute werden durch Unterstreichen gekennzeichnet. Die Kardinalitäten von Beziehungen und - falls nötig — Rollennamen sollen ins Diagramm aufgenommen werden. Personen und Einrichtungen der Bibliothek werden wie folgt beschrieben: ¢ Für Personen werden folgende Informationen aufgezeichnet: Ausweisnummer, Vorname, Nachname, Adresse (Land, PLZ, Ort, Straße, Hausnummer), Geburtstag und eine Liste von Telefonnummern. - Sachbearbeiter sind eine Gruppe von Personen, die durch zusätzliche Eigenschaften charakterisiert sind: Personalnummer, Fachrichtung, Zimmernummer, Gebäude, Anstellungsdatum und Gehalt. - Einige Mitarbeiter sind Führungskräfte (Sachgebietsleiter, Spezialbibliotheksleiter oder Büchereileiter), für die zu den Angaben der Sachbearbeiter noch weitere Charakteristika hinzukommen: Sachgebiet (Musikbibliothek, alte Schriften etc.) und Gehaltsstufe (A16, BI etc.) - Darüber hinaus gibt es eine weitere Personengruppe, die Bürger. Zusätzlich zu den Eigenschaften der Personen besitzen sie folgende Attribute: Bibliotheksausweisenummer, Beruf (Student, Rentner etc.) und Datum der Ausweiserstellung. - Jedes Sachgebiet wird durch seinen Namen, der übergeordneten Bibliotheksabteilung, zu der es gehört, und die Anzahl seiner Planstellen beschrieben. - Die Bibliothek hat Medien, die sie verleiht. Jedes Medium hat eine eindeutige Nummer, aus der das zugeordnete Sachgebiet abgeleitet werden kann, Tag der Anschaffung und im Fall von Büchern eine ISBNNummer. In den übrigen Fällen wird das Medium durch Hersteller und Produktname beschrieben. Büchermedien sind Büchern über ISBN-Nummern zuzuordnen. - Bücher werden durch ISBN-Nummer, Titel, Jahr der Veröffentlichung, Auflage, mehrere Suchbegriffe, Seitenzahl und eine Autorenliste beschrieben. - Buchverlage sollen durch Namen und Ort repräsentiert werden. - Autoren werden lediglich durch Vor- und Nachname identifiziert. Eine weitere Identifikation’braucht nicht zu erfolgen. . e Mitarbeiter und Bürger können Bücher bei der Bibliothek ausleihen. Die Ausleihfrist beträgt jeweils 14 Tage. Bei einer Überschreitung dieser Frist werden Gebühren (5 EUR) erhoben. Überschreiten die kumulierten Gebühren, die eine Person zu entrichten hat, eine vorgegebene Grenze (20 EUR), so kann die betreffende Person keine weiteren Bücher ausleihen. - Einige Führungskräfte sind Sachgebietsleiter; für jedes Sachgebiet gibt es aber höchstens einen Leiter. *® Bücher werden von Verlagen herausgegeben und von Autoren geschrieben. - Medien sind immer einem Sachgebiet zugeordnet. Im Fall von Büchern wird ein Medium auch immer einem Buch zugeordnet. 3.2 Relationenmodell Entwerfen Sie ausgehend von der ER-Darstellung ein Relationenschema in dritter Normalform (3. NF). Primärschlüssel werden durch Unterstreichen, Fremdschlüssel durch die Nennung der entsprechenden Relation kenntlich gemacht. Beispiel: Abteilung(Abteilungsnummer, Abteilungsname) Mitarbeiter(Mitarbeiternummer, Abteilung[Abteilung)) Fortsetzung nächste Seite! Herbst 2009 Einzelprüfungsnummer 66114 Seite 7 4 SQL Gegeben ist folgende Datenbank: SQL> select * from buecher; BUCH_NR | TITEL AUTOR 1 Oracle9i G.Stuerner 2 Informix D.Petkovic 6.0/7.1 3 SYBASE D.McGovera n SQL> select * from leser; LESER N |NAME R 1 G. Schroeder 2 H. Kohl 3 A. Merkel SQL> select * from ausleihe; _ |BUCH_NR |LESER NR |EIN AUS [DATUM AUS 19. Jun 95 AUS 01. Jul 95 EIN 03. Jul 95 3 3 AUS 09. Jun 08 2 2 AUS 11. Jun 08 1 1 AUS 12. Jun 08 3 3 EIN 13. Jun 08 1 1 EIN 15. Jun 08 1 2 AUS 17. Jun 08 2 3 EIN 27. Jun 08 2 2 EIN 18. Jun 08 2 3 AUS 19. Jun 08 1 2 EIN 22. Jun 08 2 3 EIN 07. Jun 08 3 1 EIN 30. Jun 08 3 1 3 1 3 i Fortsetzung nächste Seite! Herbst 2009 Einzelprüfungsnummer 66114 Seite 8 In buecher ist BUCH_NR Primärschlüssel. In leser ist LESER_NR Primärschlüssel. In ausleihe besteht der Primärschlüssel aus BUCH_NR und LESER_NR. EIN_AUS beschreibt, ob ein Buch entliehen wurde („AUS") oder zurückgebracht wurde („EIN"). 4.) Erstellung der Tabellen a) Schreiben Sie die nötigen SQL-Befehle, um die oben beschriebenen Tabellen zu erstellen. b) Wie müssten die Tabellen angelegt werden, damit dasselbe Buch vom selben Leser mehr als einmal ausgeliehen werden kann? c) Wie kann sichergestellt werden, dass das Rückgabedatum stets größer ist als das Entleihdatum und dass nur Bücher entliehen werden können, die auch zurückgegeben wurden (beim Einfügen von Rows in Table ausleihe)? 42 SQL-Anfragen Geben Sie zu folgenden Anfragen das SQL-Statement an: a) Welche Bücher wurden noch nie entliehen? b) Welche Bücher sind im Moment entliehen? c) Wie viele Bücher hat A. Merkel im Moment entliehen und noch nicht zurückgebracht? d) In einer Statistik sollen alle abgeschlossenen Ausleihvorgänge erfasst werden (TITEL, NAME, AUSGANG, EINGANG, DAUER). €) In einer weiteren Statistik soll die durchschnittliche Ausleihzeit pro Buch bestimmt werden (TITEL, DURCHSCHNITTSDAUER). Herbst 2009 Einzelprüfungsnummer 66114 Seite 9 Themenschwerpunkt B (Betriebssysteme) Aufgabe 1: 1. Synchronisation mit Semaphoren Gegeben sei folgendes Szenario: Fahrzeuge befahren aus zwei Richtungen eine Brücke mit Engstelle: m Brücke Die Brücke darf nur von zwei Fahrzeugen gleichzeitig befahren werden. Die Streckenabschnitte A, X und Y können nur jeweils ein Fahrzeug aufnehmen. Die Fahrzeuge aus den beiden Richtungen können folgendermaßen formalisiert werden: R-Fahrzeug L-Fahrzeug { { while (TRUE) while (TRUE) { { “Anfahrt bis Ri>; ; «von Ri nach X>; ; «von A nach A>; ; “von A mach Lis; ; “; ; } } } + Es sind beliebig viele R-Fahrzeuge und L-Fahrzeuge möglich. Synchronisieren Sie die Fahrzeuge auf der Brücke, indem Sie in geeigneter Weise Semaphore deklarieren und Semaphor-Operationen einfügen. Geben Sie zu den verwendeten Semaphoren die Startwerte an. Folgende Bedingungen müssen erfüllt sein: Fortsetzung nächste Seite! Herbst 2009 Einzelprüfungsnummer 66114 Seite 10 - Maximal zwei Fahrzeuge dürfen gleichzeitig die Brücke, also die Streckenabschnitte A, X und Y, befahren. - Es dürfen keine Kollisionen auf der Brücke auftreten. Auch Auffahrunfälle, d. h. Kollisionen zwischen Fahrzeugen aus der selben Richtung, sind zu verhindern. - Sperrphasen sind möglichst kurz zu halten. - Estreten keine Verklemmungen auf. Zu Beginn sind alle Streckenabschnitte frei. Die Streckenabschnitte L1, L2, Ri und R2 müssen nicht synchronisiert werden. 2. Process Scheduling a) Untersuchen Sie die Schedulingverfahren first-come-first-served, shortest-jobs-first, round robin und statische Priorität bezüglich folgender Kriterien: - unterbrechend oder nicht unterbrechend b) Welche Konsequenzen hat der Aspekt, ob ein Scheduling-Verfahren unterbrechend oder nicht unterbrechend ist, auf die Kriterien Fairness und Echtzeitfähigkeit? Welchen generellen Vorteil hat ein nicht unterbrechendes Verfahren? c) Welches Verfahren hat den höchsten Durchsatz? Wieso wird dieses Verfahren trotzdem kaum implementiert? d) Berechnen Sie den Durchsatz für die Prozessfolge Pl (Dauer 50 ms), P2 (Dauer 70 ms), P3 (Dauer 10 ms), P4 (Dauer 30 ms) für die Schedulingverfahren shortest-jobs-first und round robin (Zeitscheibe 20 ms). Es wird angenommen, dass alle Prozesse gleichzeitig starten und ein Prozesswechsel 2ms dauert. Fortsetzung nächste Seite! Herbst 2009 Einzelprüfungsnummer 66114 3. Memory Management Seite 11 a) Sei eine Menge von Seiten (pages) N = {0, 1, 2, 3, 4, 5, 6} und eine Menge von Seitenrahmen (frames) F = { fı, R, f3 } gegeben. Nun wird in folgender Reihenfolge auf die Seiten zugegriffen: 0a=6256446131 forderung f, f fy ie 6 2 5 6 4 4 6 1 3 1 b) Welches Verfahren hat im Beispiel die bessere Performanz? Volizichen Sie die Seitenersetzungs-Strategien LRU (Least Recently Used) und FIFO (First In First Out) schrittweise nach, indem Sie zwei Tabellen nach folgendem Muster anlegen c) Nennen Sie für jedes der beiden Verfahren einen Vorteil und einen Nachteil! Fortsetzung nächste Seite! Herbst 2009 Einzelprüfungsnummer 66114 Seite 12 4. Deadlocks a) Nennen und erläutern Sie kurz die 4 Deadlock-Bedingungen (Coffman-Bedingungen)! b) Nennen und erläutern Sie kurz 4 Möglichkeiten der Verklemmungs-Verhinderung (DeadlockPrevention)! c) Verklemmungs-Vermeidung (Deadlock-Avoidance): "Qu Wir gehen aus von 3 Prozessen (pı, p>, p3), die um 3 Sorten von Ressourcen (Sorte 1: DVD-Brenner, Sorte 2: Grafikkarten, Sorte 3: TV-Karten) im System konkurrieren. Es seien die Zahlen der existierenden Instanzen der verschiedenen Ressourcen-Sorten durch das Tupel (e1, &2, &3) gegeben und die Zahlen der im Moment noch freien Instanzen der Ressourcen-Sorten durch das Tupel (aı, a2, a3). Die aktuelle Belegung von Instanzen der verschiedenen Ressourcen-Sorten durch Prozesse sei durch die 3 x 3 Matrix c und die aktuelle maximale Rest-Anforderung von Instanzen der Ressourcen-Sorten durch Prozesse durch die 3 x 3 Matrix r gegeben: 40 3 c=] 0 38 0 323 430 r = ( 033 \ \ 003 } - = (9,6,8) a = (2,1, 2) In den Matrizen c und r seien die Zeilen den Prozessen und die Spalten den RessourcenSorten zugeordnet. (Beispiel zur Verdeutlichung: Dem Prozess 3 entspricht in den Matrizen c und r jeweils die dritte Zeile. Das heißt, Prozess p; hat im Moment 3 Instanzen der Ressourcen-Sorte 1 (also 3 DVD-Brenner), 2 Instanzen der Ressourcen-Sorte 2 (also zwei Grafikkarten) und 3 Instanzen der Ressourcen-Sorte 3 (also 3 TV-Karten). Prozess 3 möchte in Zukunft bspw. maximal noch 0 DVD-Brenner, 0 Grafikkarten und 3 TV-Karten haben.) Solite im aktuellen Zustand eine Anforderung eines DVD-Brenners durch den Prozess pı vom Betriebssystem erfüllt werden? Beantworten Sie die Frage durch Anwendung des Banker-Algorithmus! Stellen Sie alle Ihre Ausführungsschritte so dar, dass die Ausführung des Algorithmus nachzuvollziehen ist! Fortsetzung nächste Seite! Herbst 2009 Einzelprüfungsnummer 66114 Seite 13 Aufgabe 2: Ein Verwaltungsprogramm für ein Drucksystem mit mehreren Druckern arbeite folgendermaßen: i, il. ili. iv. Druckaufträge werden in Form von Auftragsdateien in einem Dateiverzeichnis "/var/spool/printg" abgelegt. Der Name einer Auftragsdatei ist folgendermaßen aufgebaut: cpid . pid ist ist dabei die Prozess-Id des Prozesses, der den Druckauftrag erzeugt (z. B. Auftragsdatei „c4711“ für einen Auftrag des Prozesses mit der pid 4711). Das Verwaltungsprogramm liest beim Start das Dateiverzeichnis durch und erzeugt für jeden Druckauftrag eine Verwaltungsstruktur, in der der Name der Auftragsdatei und der Zeitpunkt der Auftragserstellung eingetragen werden. Diese Datenstrukturen werden in eine Warteschlange eingetragen. Für jeden vorhandenen Drucker wird nun ein Prozess erzeugt, der Aufträge aus der Warteschlange entnimmt und den Inhalt der zugehörigen Auftragsdatei jeweils auf „seinem" Drucker ausdruckt. Das Verwaltungsprogramm blockiert sich nach dem initialen Einrichten der Warteschlange und wird „geweckt", sobald ein Benutzerprozess einen neuen Auftrag in die Warteschlange eingetragen hat. Prozesse, Dateien a) Da Prozess-Ids in vielen Betriebssystemen wiederverwendet werden, kann es theoretisch passieren, dass es eine Auftragsdatei mit der zu vergebenden Nummer bereits gibt. Wie kann ein Programm, das einen Auftrag absetzen möchte, solch einen drohenden Konflikt erkennen und was könnte man zur Behebung des Konflikts tun? b) Die Prozesse, die Aufträge absetzen, laufen unter der normalen Berechtigung ihrer Benutzer. Was muss man hinsichtlich der Zugriffsrechte der Auftragsdateien und des Dateiverzeichnisses für die Auftragsdateien berücksichtigen, damit (1) solche Aufträge überhaupt erzeugt werden können, (2) es nicht möglich ist, dass ein böswilliger Benutzer fremde Aufträge löscht, un (3) niemand fremde Druckaufträge lesen kann? c) Skizzieren Sie in einer Programmiersprachen-ähnlichen Form den Ablauf vom Start des Verwaltungsprogramms bis zur vollständigen Einrichtung der Warteschlange mit den Datenstrukturen. d) Wie könnte man das Aufwecken des Verwaltungsprogramms in Punkt iv realisieren? Fortsetzung nächste Seite! Herbst 2009 Einzelprüfungsnummer 66114 Seite 14 a) b) d) 4 Speicher Wie kann der Speicherbereich für die Warteschlange aus Punkt ii als gemeinsamer Speicher in einem Betriebssystem mit Seitenadressierung realisiert werden? In welchen Datenstrukturen des Betriebssystems müssen hierzu welche Einträge erfolgen? Skizzieren Sie die logischen Adressräume von zwei Drucker-Prozessen und den usammenhang zu dem physikalischen Hauptspeicher. Worauf müsste man achten, wenn man die Warteschlange als verkettete Liste der Datenstrukturen realisieren wollte? Warum ist die Realisierung in Form eines Feldes einfacher? Wie könnte man mit der Situation umgehen, in der die Größe des Feldes nicht ausreicht, um alle anstehenden Druckaufträge aufnehmen zu können? Prozesse, Threads Die beschriebene Realisierung mit Hilfe von Prozessen ist Ressourcenaufwändig. Warum? Eine Realisierung mit Hilfe von Threads wäre günstiger. Welche Arten von Threads kennen Sie, wodurch unterscheiden sie sich, was ist der Unterschied zu Prozessen? Welche Thread-Art ist für die beschriebene Aufgabe geeignet und sollte statt einer Realisierung mit Prozessen genutzt werden? Welche Kosten spart man dadurch ein, welche Abläufe werden effizienter? Warum ist die andere Thread-Art für die Aufgabe nicht geeignet? Koordinierung Beschreiben Sie nun die Koordinierung der Warteschlange mit den Auftragsverwaltungsstrukturen zwischen dem Prozess, der das Verwaltungsprogramm ausführt, und den Drucker-Prozessen: a) b) c) d) Welche Zugriffskonflikte bestehen potentiell? Welche Warte-/Aufwecksituationen gibt es? Welche Koordinierungsmittel sind jeweils dafür geeignet? Skizzieren Sie die Koordinierung auf der Seite des Verwaltungsprogramms und auf der Seite der Drucker-Prozesse jeweils in Programmiersprachen-ähnlicher Form.