Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer Kennzahl: Frühjahr 66114 2007 Kennwort: Arbeitsplatz-Nr.: , Erste Staatsprüfung für ein Lehramt an öffentlichen Schulen — Prüfungsaufgaben — Fach: Informatik (vertieft studiert) Einzelprüfung: Datenbank- und Betriebssysteme Anzahl der gestellten Themen (Aufgaben): 4 Aufgaben, von denen 2 gemäß untenstehender Auswahlregeln zu bearbeiten Anzahl der Druckseiten dieser Vorlage: 11 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. Al, B2)! Bitte wenden! Frühjahr 2007 Einzelprüfungsnummer: 66114 Seite: 4 7. Datenbankentwurf Datenbanksysteme dienen der Speicherung und effizienten Verarbeitung von Daten. Das Datenbankschema lässt sich mit Hilfe von Entity-Relationship-Diagrammen entwerfen. Das folgende Entity-Relationship-Diagramm (ERD) beschreibt einen Ausschnitt aus der Datenbank eines Flugbuchungssystems. Bestimmen Sie das zu diesem ERD gehörige Relationenschema! Verwenden Sie als Namen für Fremschlüsselattribute die Namen der referenzierten Primärschlüsselattribute. Primärschlüsselattribute sind zu unterstreichen, Fremdschlüsselattribute zu überstreichen! Passagier Sitzkiasse 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) Definieren Sie den Begriff Datenbanksystem und grenzen Sie die Funktionalitäten eines Datenbanksystems von denen eines Dateisystems ab! b) Nennen Sie die Phasen des Datenbankentwurfsprozesses und charakterisieren Sie diese kurz! c) Entity-Relationship-Modell: Erläutern Sie die nachfolgenden Konzepte eines ER-Modells! Entität, Relationship/Beziehungstyp, Attribut, Kardinalitat Fortsetzung nächste Seite! Frühjahr 2007 Einzelprüfungsnummer: 66114 Seite: 5 d) Relationales Modell: Erläutern Sie informell die folgenden Begriffe! Gehen Sie insbesondere auf die Bedeutung der verschiedenen Begriffe für die Anwendungsmodellierung ein! Schlüsselkandidat, Primärschlüssel, Fremdschlüssel e) Sie haben sowohl die Grundoperationen der relationalen Algebra als auch die daraus abgeleiteten Operationen kennen gelernt. Definieren Sie die Operation „Division“! f) Sie haben die Normaiformenlehre kennen gelernt. Welchen Sinn und Zweck hat die Normalformenlehre? g) Transaktionen sind ein wichtiges Konzept in Datenbanksystemen. Was versteht man unter dem ACID-Prinzip? Welche Konsequenzen im Verhalten des Datenbanksystems hat das ACID- -Prinzip für den Anwender und Entwickler? 2. ER-Modellierung und Relationenmodell a) ER-Modellierung Es soll ein Modell der beschriebenen universitären Welt in ER-Notation erstellt werden! Dabei können alle Ihnen bekannten Modellierungskonstrukte verwendet werden. Wo möglich bzw. sinnvoll, sollen 3-fache Beziehungen 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! Das folgende Beispiel beschreibt einen Ausschnitt der universitären Welt. Personen und Einrichtungen der Universität werden durch folgende Typen von Objekten beschrieben: - Für Personen werden folgende Informationen aufgezeichnet: Ausweisnummer, Vorname, Nachname, Adresse (Land, PLZ, Ort, Straße, Hausnummer), Geburtstag und eine Liste von Telefonnummern. - Mitarbeiter sind eine Gruppe von Personen, die durch zusätzliche Eigenschaften charakterisiert sind: Personalnummer, Fachrichtung, Zimmernummer, Gebäude, Anstellungsdatum und Gehalt. - Einige Mitarbeiter sind Professoren, für die noch weitere Charakteristika hinzukommen: Lehrstuhl und Gehaltsstufe (C3, C4 etc.). - Darüber hinaus gibt es eine weitere Personengruppe, die Studenten. Zusätzlich zu den Eigenschaften der Personen besitzen sie folgende Attribute: Matrikelnummer, Studienfach und Immatrikulationsdatum. - Jeder Lehrstuhl wird durch seine Fachrichtung, das Institut, zu dem er gehört, und die Anzahl seiner Planstellen beschrieben. Fortsetzung nächste Seite! Frühjahr 2007 Einzelprüfungsnummer: 66114 Seite: 6 Darüber hinaus enthält die abzubildende universitäre Miniwelt noch Ausprägungen folgender Typen: °e Die Universitätsbibliothek enthält eine Reihe von Büchern, die durch ISBN-Nummer, Titel, Jahr der Veröffentlichung, Auflage, mehrere Suchbegriffe und eine Autorenliste beschrieben werden. Die Anzahl ihrer Seiten und ihr Preis sollen ebenfalls aufgenommen werden. - Buchverlage sollen durch Namen und Ort repräsentiert werden. - Vorlesungen haben eine Bezeichnung, eine vorgegebene Zahl von Semesterwochenstunden und werden im Sommer- oder Wintersemester abgehalten. Für den Besuch einer Vorlesung kann der vorherige Besuch einer Reihe anderer Vorlesungen, in denen Grundlagen vermittelt werden, gefordert sein. Zwischen Instanzen der beschriebenen Objekttypen bestehen eine ganze Reihe von Beziehungen. In jedem der folgenden Punkte können eine oder mehrere Beziehungen beschrieben sein: - Mitarbeiter und Studenten 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. - Professoren empfehlen den Studenten Bücher für ihre Vorlesungen. « Einige Professoren sind Lehrstuhlinhaber; für jeden Lehrstuhl gibt es aber höchstens einen Lehr-: stuhlinhaber. - Professoren halten ihre Vorlesungen entweder im Winter- oder im Sommersemester. Jeder Student kann mehrere Vorlesungen in einem Semester besuchen. Jede Vorlesung kann eine beliebige Zahl anderer Vorlesungen voraussetzen (Vorkenntnisse). - Bücher werden von Verlagen herausgegeben. - Studenten werden von Professoren in unterschiedlichen Fächern geprüft. Die Leistungen in jeder Prüfung werden mit einer Note bewertet. b) Relationenmodell Ausgehend von der ER-Darstellung ist ein Relationenschema in dritter Normalform (3. NF) zu entwerfen. Wie gewohnt, werden dabei Primärschlüssel durch Unterstreichen, Fremdschlüssel durch _ Überstreichen kenntlich gemacht. Fortsetzung nächste Seite! Frühjahr 2007 Einzelprüfungsnummer: 66114 Seite: 7 3.SQL a) Szenario 1: Bücher und Verlag Für die Verwaltung ihrer Bestände in einer Datenbank verwendet eine kleine Buchhandlung die folgenden Relationen: BUCH (ISBN, Autor_Nachname, Titel, Verlags_Id, Lagerbestand) VERLAG (Verlags Id, Verlagsname, Verlagsadresse) Die Primärschlüssel der Relationen sind unterstrichen, Verlags_Id in BUCH ist Fremdschlüssel zu Verlags Id in VERLAG. Formulieren Sie die folgenden Datenbankoperationen in SQL und geben Sie - falls möglich - die zugehörigen Ausdrücke in relationaler Algebra an! 1. Welche ISBN hat das Buch "Kaufmännische Datenbanken" von Wedekind? . 2. Welche Adresse hat der Verlag, in dem das Buch mit der ISBN 2-411-16541-3 erschienen ist? 3. Die Buchhandlung erwirbt fünf Exemplare des bei Adisson-Wesley erschienenen Buchs "Objektorientierte Datenbanken" von Andreas Heuer, ISBN 3-89319-315-4. Der Verlag ist bereits in der Relation VERLAG vorhanden und hat die ID "AW1". Formulieren Sie die Anweisungen für den Eintrag der Daten! 4. Löschen Sie den "Pleite-Verlag", "Erfolglosenstr. 13, 90439 Nürnberg"! Gehen Sie davon aus, dass von dem Verlag nie ein Buch gelagert wurde! b) Szenario 2: Personaldatenbank Für die Personalabteilung eines Unternehmens soll eine Personaldatenbank erstellt werden. Das Unternehmen ist in mehrere Abteilungen untergliedert. Jeder Angestellte gehört zu genau einer Abteilung; jede Abteilung hat einen Abteilungsleiter. Die folgenden Relationen stellen einen kleinen Ausschnitt aus der erarbeiteten Datenbankanwendung dar: ABTEILUNG (ANTr, Bezeichnung) PERSONAL ( Pnr, Name, Geburtsdatum, Gehalt, ANr) LEITER (ANr, Phr) Die Fremdschlüsselbeziehungen sind sprechend und gemäß der Beschreibung gewählt. Fortsetzung nächste Seite! Frühjahr 2007 Einzelprüfungsnummer: 66114 Seite: 8 Geben Sie SQL-Anweisungen für folgende Problemstellungen an: 1. Erstellung des beschriebenen Relationenschemas mit Tabellen, Primary Key Constraints und Foreign Key Constraints. 2. Frau Schneider (geb. 12.5.61) wird zur Leiterin der neu gegründeten Abteilung "Kundensupport". Sie erhält die Personalnummer 4497. 3. Herr Müller (PNr 2371) scheidet aus dem Unternehmen aus. 4. Wie viele Personen arbeiten in der Abteilung, die von Frau Ziegler (geb. 30.12.58) geleitet wird? 5. Wie viele Mitarbeiter hat die Abteilung, in der Herr Schuster (geb. 18.1.83) arbeitet? 6. Wie hoch ist das Durchschnittsgehalt in den einzelnen Abteilungen? 7. Wessen Gehalt liegt über dem Durchschnittsgehalt der Abteilung, in der er beschäftigt ist? Frühjahr 2007 Einzelprüfungsnummer: 66114 Seite: 9 Themenschwerpunkt B (Betriebssysteme) Aufgabe 1: 1. Speicherverwaltung = a) Beschreiben Sie die Seitenersetzungsstrategie LRU (Least Recently Used). Gehen Sie dabei ein auf Funktionsweise und Motivation der Strategie sowie auf Probleme bei der Realisierung! b) Welche Strategien zur näherungsweisen Realisierung von LRU gibt es? Erläutern Sie an einem Beispiel detailliert die Funktionsweise! Warum und wie werden durch die von Ihnen beschriebene Strategie die Probleme von LRU vermieden? c) Was versteht man unter Seitenflattern (Thrashing)? Was sind die Ursachen? Welche Möglichkeiten gibt es, Seitenflattern zu vermeiden? 2. Prozesse a) Skizzieren Sie die Zustände, die ein Prozess unter einem Mehrbenutzer-Betriebssystem wie z. B. UNIX typischerweise einnehmen kann! b) Ein Prozess habe folgenden Ablauf (grob skizziert): 1. Start, Variablen initialisieren 2. Konfigurationsdatei einlesen 3. kurze Vorberechnungen durchführen (Dauer: 2 ms) 4. Berechnungsdaten aus Datei einlesen 5. Berechnung durchführen (Dauer: 800 ms) 6. Ergebnis in Datei ausgeben 7. Ende - Nehmen Sie zunächst an, das Betriebssystem arbeitet mit einer "First Come First Served"- Scheduling-Strategie. Welche Zustände nimmt der Prozess während dieses Ablaufs ein, wodurch werden welche Zustandsübergänge ausgelöst? - Nehmen Sie nun an, das Betriebssystem arbeitet mit der Strategie "Round Robin" und es gibt weitere, laufbereite Prozesse im System. Die Zeitscheibenlänge sei 300 ms. Wie sieht der Ablauf des Prozesses (Zustände, Zustandsübergänge, Ursachen) aus? c) In vielen Betriebssystemen wird zwischen einem Benutzermodus und einem Systemmodus unterschieden. Beschreiben Sie die Eigenschaften und Unterschiede der beiden Modi. Wie erfolgt die Umschaltung zwischen den Modi? Was sind die Ziele dieser Unterscheidung? In welchen Rechensystemen ist die Unterscheidung sinnvoll oder sogar wichtig und in welchen Systemen ist sie verzichtbar? Fortsetzung nächste Seite! Frühjahr 2007 Einzelprüfungsnummer: 66114 Seite: 10 3. Verklemmungen a) b) Welche Bedingungen miissen gegeben sein, damit eine Verklemmung auftreten kann? Welche drei grundsätzlichen Verfahren gibt es, um mit der Verklemmungsproblematik umzugehen? Beschreiben Sie jedes Verfahren! Wie ist jeweils die grundsätzliche Vorgehensweise? Geben Sie ein Beispiel für einen Algorithmus an, der bei einem dieser Verfahren zum Einsatz kommt und beschreiben Sie den Algorithmus! 4. Dateisysteme \ a) Was sind die grundlegenden Aufgaben eines Dateisystems? b) Welche Informationen und Attribute werden zu einer Datei von einem Betriebssystem typischerweise verwaltet? c) Skizzieren Sie in einer programmiersprachlichen Form den Ablauf eines Programms wie /s unter UNIX oder dir unter Windows! Aufgabe 2: 1. Prozesse und Threads a) b) Erläutern Sie die Begriffe Programm, Prozess und Thread! - Wie entstehen Programme, Prozesse bzw. Threads? - Wie werden sie vom Betriebssystem verwaltet? - Welche Eigenschaften, Attribute etc. werden für die Verwaltung benutzt? Was haben diese Konzepte miteinander zu tun, wo legen die Unterschiede? Beschreiben Sie die unterschiedlichen Möglichkeiten zur Realisierung von Threads! Was sind jeweils die Vor- und Nachteile? 2. Scheduling a) b) Beschreiben Sie die grundlegenden Scheduling-Strategien und ihre Eigenschaften! Wie könnte eine realistische Scheduling-Strategie für ein Mehrbenutzer- und MehrprogrammBetriebssystem aussehen? - Welche Ziele sollte solch eine Scheduling-Strategie haben? - Über welche Parameter muss man bei der Strategie entscheiden und was sind die Auswirkungen der Parameter? - Welche Probleme können unter sehr starker.Systemlast entstehen und was kann man dagegen tun? Fortsetzung nächste Seite! Frühjahr 2007 Einzelprüfungsnummer: 66114 Seite: 11 3. Speicherverwaltung a) Skizzieren und beschreiben Sie den Ablauf einer Adressumrechung von einer virtuellen Adresse in eine reale Hauptspeicheradresse in einem seitenadressierten System! b) Wie ist der Ablauf, wenn sich die adressierte Seite nicht im Hauptspeicher befindet? c) Wie groß ist heute typischerweise eine Seite? d) Welche Probleme würden sich ergeben, wenn man die Adressabbildung in ihrer einfachsten Form auf einem heute gebräuchlichen PC realisieren würde? Welche Konzepte gibt es, diese Probleme zu mildern? 4. Dateisystem a) Was sind die grundlegenden Aufgaben eines Dateisystems? b) Wie ist ein Dateisystem unter UNIX oder Windows prinzipiell strukturiert? Welche Verwaltungseinheiten gibt es? c) Welche Informationen und Attribute werden zu einer Datei von einem Betriebssystem typischerweise verwaltet? d) Skizzieren Sie in einer programmiersprachlichen Form den Ablauf eines Programms wie Is unter UNIX oder dir unter Windows! 5, Synchronisation a) b) c) d) Welche Verfahren/Konzepte zur Absicherung eines kritischen Abschnitts gibt es? Charakterisieren Sie diese Verfahren jeweils (Vor- und Nachteile, wo werden sie eingesetzt?)! Wie funktionieren die P- und V- Operationen von Semaphoren? Skizzieren Sie den Ablauf der Operationen in einer programmiersprachlichen Form! Was ist bei der Implementierung der P- Operation zu beachten? Skizzieren Sie in einer programmiersprachlichen Form die Abläufe in einem ErzeugerVerbraucher-System, das die vollen und leeren Pufferplätze über zählende Semaphore koordiniert!