Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer Kennzahl: Herbst Kennwort: 66 1 1 4 2006 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 zwei gemäß den untenstehenden Auswahlregeln zu bearbeiten sind! Anzahl der Druckseiten dieser Vorlage: 10 Zu den zwei Themenschwerpunkten A (Datenbanksysteme) und B (Betriebssysteme) ist jeweils entweder die Aufgabe I 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! Herbst 2006 Einzelprüfungsnummer: 66114 Seite: 2 Themenschwerpunkt A Datenbanksysteme AUFGABE 1 E/R und SQL Teilaufgabe 1 Gegeben sei folgende Tabelle einer großen Kinokette: KINO (Name, Stadt, Vorwahl, Telefon, MName, MGebDat, MGehaltsstufe, MGehalt, MHandy, dBZ, SaalNr, Sitzplätze, Soundsystem) Der Buchstabe „M“ steht hierbei für „Manager“, unter „MGebDat“ findet sich also das Geburtsdatum des Leiters des jeweiligen Kinos. „dBZ‘ bezeichnet die durchschnittliche Besucherzahl für ein Kino. Die SaalNr ist für jedes einzelne Kino eindeutig. Es existieren folgende funktionale Abhängigkeiten (auf die Angabe der trivialen Abhängigkeiten wurde verzichtet): e) Stadt > Vorwahl MGehaltsstufe > MGehalt Name, Stadt > Telefon, MName, MGebDat, MGehalt, MHandy, dBZ MName — MGebDat, MGehaltsstufe, MGehalt, MHandy Name, Stadt, SaalNr > Sitzplätze, Soundsystem Die Relation „Kino“ sei in erster Normalform. Was muss für die Attribute der Tabelle gelten? Bestimmen Sie den einzigen Schlüsselkandidaten von „Kino“! Überführen Sie die Relation in die zweite (aber noch nicht dritte) Normalform und erläutern Sie Ihre Schritte kurz! Finden Sie eine Anomalie, die Sie in diesem Beispiel durch Überführung in die zweite Normalform eliminieren konnten, sowie eine andere, die weiterhin vorhanden ist! Überführen Sie nun die Relation, ebenfalls mit kurzer Erläuterung, in die dritte Normalform! Markieren Sie von allen Relationen die Primärschlüssel! Teilaufgabe 2 Es seien folgende Tabellen eines Fahrradladens gegeben: Prophete Damenfahrrad Felix Kinderfahrrad Prophete Pedale Magnum Bügelschloss Hella Speichenreflektoren Harley-Davidson - Street Rod Einheitsgröße XL Einheitsgröße 1 130m Fortsetzung nächste Seite! Herbst 2006 Einzelprüfungsnummer: 66114 Seite: 3 Beschreibung Prophete Herrenfahrrad Prophete Damenfahrrad Felix Kinderfahrrad Prophete Pedale Magnum Bügelschloss Hella Speichenreflektoren a) Geben Sie die SQL-Anweisungen an, um die Tabelle Bestand (ohne Inhalt!) zu erstellen! b) Formulieren Sie folgende Abfragen in SQL: I Welche Artikel, die dem Typ Zubehör angehören, sind verfügbar? II Bestimmen Sie alle Artikel, die Fahrräder sind und mehr als 500 € kosten! III Bestimmen Sie alle Artikel, die Zubehör sind und weniger als 10 € kosten! IV Sortieren Sie alle Artikel alphabetisch (Beschreibung)! V Bestimmen Sie den Durchschnittspreis aller Fahrräder! Teilaufgabe 3 Gegeben sei folgendes Entity-Relationship-Diagramm einer Bank: Personal-) nummer Konto 1 (KGebuns"\ ( } fename) (Kanschrin\ cr) (Konten, /‘Konto> _ datum \KName, QeAnschiiy a) Con) (sand) Fortsetzung nächste Seite! Herbst 2006 Einzelprüfungsnummer: 66114 Seite: 4 a) Geben Sie die Schlüsselkandidaten an! b) Überführen Sie das ER-Modell in ein verfeinertes Relationenschema! c) Markieren Sie alle Fremdschlüssel innerhalb des Relationenschemas! d) Wie würden Sie das Modell ergänzen, wenn die Bank mehrere Filialen unterhält? Gehen Sie davon aus, dass Kontodaten etc. zentral bei der Bank gespeichert werden! AUFGABE 2 1. Normalformenlehre 1.1 Welche Nachteile haben Redundanzen im Datenbestand? Nennen und erklären Sie mindestens zwei Ihnen bekannte Anomalien! 1.2 Annahme: RelationenschemaR sei in 2. Normalform. Welche Eigenschaft muss zusätzlich erfüllt werden, damit R in 3. Normalform ist? 1.3 Für die Zerlegung von Relationsschemata gibt es zwei grundlegende Korrektheitsbeziehungen. Benennen und erklären Sie diese kurz! 2. ER-Modellierung und Relationenmodell 2.1 ER-Modellierung Erstellen Sie das Modell einer fiktiven Tanzschule in E/R-Notation! 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. Führen Sie Surrogatschlüssel nur ein, falls es nötig ist! „Tanzschule“ Tanzschüler werden durch eine eindeutige Nummer, Namen, Geschlecht und Geburtsdatum beschrieben. Jeder Tanzschüler hat genau einen anderen Tanzschüler als „Tanzpartner“. Tänze zeichnen sich durch eine eindeutige Kurzbezeichnung, einen Namen und einen gewissen Stil aus. Ein Tanzschüler hat bestimmte Tänze gelernt, andere nicht. Ein Tanzkurs hat genau einen Tanzlehrer und mindestens einen Teilnehmer. Es werden in jedem Tanzkurs nur ausgewählte Tänze unterrichtet. Ein Tanzkurs hat einen Namen und ein Beginndatum. Er wird durch eine Nummer identifiziert. Ein Tanzschüler kann auch an mehreren Tanzkursen gleichzeitig teilnehmen oder pausieren. Nicht jeder Tanz wird in einem Tanzkurs unterrichtet. Jeder Tanzlehrer kann nur ganz bestimmte Tänze unterrichten. Ein Tanzlehrer hat einen Vorund Nachnamen und eine Zulassung. Er wird durch seinen Nachnamen identifiziert. Er kann keinen, einen oder mehrere Tanzkurse unterrichten. Für jeden Tanz im Repertoire muss es einen Tanzlehrer geben. Dass an einem Kurs nur als Paar teilgenommen werden kann, ist nicht zu modellieren. Fortsetzung nächste Seite! Herbst 2006 Einzelprüfungsnummer: 66114 Seite: 5 2.2 Relationenmodell Ausgehend von der ER-Darstellung ist ein Relationenschema in dritter Normalform (3. NF) zu entwerfen! Primärschlüssel werden dabei durch Unterstreichen, Fremdschlüssel durch Nennung der referenzierten Relation in eckigen Klammern hinter dem Attributsnamen kenntlich gemacht, z.B.: Haus (Straße, OrtId[Ort]) Ort (OrtId, PLZ, Name) Das Attribut Ort Id der Relation Haus verweist als Fremdschlüssel auf das Attribut Ort Id der Relation Ort. 3. SQL Bitte beachten Sie: Primärschlüssel werden dabei durch Unterstreichen, Fremdschlüssel durch Nennung der referenzierten Relation in eckigen Klammern hinter dem Attributsnamen kenntlich gemacht, z.B.: Haus (Straße, OrtId[Ort]) Ort (OrtId, PLZ, Name) Das Attribut Ort Id der Relation Haus verweist als Fremdschlüssel auf das Attribut Ort Id der Relation Ort. Szenario „DJ forever!" Eine Discjockey-Agentur verwendet folgendes einfaches Datenbankschema: Club (CId, Name, AnzahlAreas, ChefDJ[DJ]) DJ (DJId, Name) Booking (DJId[DJ], CId[Club], Tag, Gage) Tag={Mo, Di, Mi, Do, Fr, Sa, So} Jeder Club hat einen ChefDJ. DJs arbeiten an unterschiedlichen Tagen evtl. in verschiedenen Clubs. Aber alle arbeiten regelmäßig, d.h. in der Tabelle „Booking" wird nur der Wochentag, kein konkretes Datum hinterlegt. Primärschlüssel sind unterstrichen. DJId in Booking ist Fremdschlüssel zu DJId in DJ, CId in Booking ist Fremdschlüssel zu CId in Club und Che£fDJ in Club ist Fremdschlüssel zu DJId in DJ. Formulieren Sie folgende Datenbankoperation in SQL: I. Geben Sie alle Namen der DJs aus! Il. Was verdient „DJ Santos“ am Mi? II. Welcher Club zahlt die höchste Gage? IV. Wie oft in einer Woche arbeitet „DJ Oetzi‘? V. Wie hoch ist die Durchschnittsgage aller DJs? VI. Geben Sie Namen aller DJs aus, die „DJ Mike“ als Chef haben! Es soll kein Name doppelt vorkommen. VII. Fügen Sie „DJ Helmut“ mit der DJId „0815“ in die Datenbank ein! VII. „DJ Helmut“ hat mittwochs ein Booking im Club „Almenhof“ mit einer Gage von „80“. Fügen Sie dieses Booking in die Datenbank ein! Herbst 2006 Einzelprüfungsnummer: 66114 Seite: 6 Themenschwerpunkt B Betriebssysteme AUFGABE 1 1. Synchronisation 1.1 Definieren Sie den Begriff Verklemmung! 1.2 Welche Bedingungen müssen erfüllt sein, damit eine Verklemmung entsteht? 1.3 Das Philosophenproblem Fünf Philosophen sitzen an einem runden Tisch, in dessen Mitte ein immer voller Teller mit Nudeln steht. Rechts und links von jedem Philosophen liegt jeweils eine Gabel. Zum Essen benötigt ein Philosoph zwei Gabeln. Die Philosophen sind nur mit zwei Dingen beschäftigt: Denken und Essen. Ist einer hungrig, so greift er zuerst nach der linken und dann nach der rechten Gabel und fängt an zu essen. Ist eine Gabel belegt, so wartet er, bis sie wieder frei ist. Hat der Philosoph sich satt gegessen, so legt er die Gabeln wieder an ihren Platz und fährt fort mit Denken. a) Betrachten Sie unten stehenden Pseudocode, der einen einzelnen Philosophen simuliert! Erläutern Sie in einem Satz, wie es in dieser Lösung zu einer Verklemmung kommen könnte! N=5; Procedure phil(i:INTEGER) WHILE (TRUE) DO think(); //Philosoph denkt nach take_fork(i); //nimm die linke Gabel take_fork((i+1) %N) //nimm die recht Gabel, % ist Modulo-Operator eat(); /lessen put_fork(i); //lege linke Gabel zurück put_fork((i+1) %N); //lege rechte Gabel zurück END; END phil; b) Neben einer Verklemmung könnte noch ein weiteres Problem auftauchen. Erläutern Sie kurz welches! Fortsetzung nächste Seite! Herbst 2006 Einzelprüfungsnummer: 66114 Seite: 7 1.4 Semaphore An einem Flughafen gibt es eine Lagerhalle, an der Transportflugzeuge ihre Ware abliefern und aufnehmen können. Lieferanten bringen jeweils zwei Kisten, während Abholer jeweils nur eine Kiste abholen. Zum Be- und Entladen fliegen die Flugzeuge zuerst über eine Start- und Landebahn ein und fahren dann vor die Lagerhalle. Dort steht ein Kran, der die Flugzeuge be- und entlädt. Danach fliegen die Flugzeuge wieder von der gleichen Start- und Landebahn weg. Beachten Sie folgende Bedingungen: Die Start- und Landebahn kann jeweils nur von einem Flugzeug befahren werden. Vor der Lagerhalle ist unbegrenzt Platz, so dass dort mehrere Lieferanten und Abholer stehen können. Die Lagerhalle hat eine Kapazität von höchstens 30 Kisten. Lieferanten dürfen nur zur Lagerhalle fahren, wenn die Lagerhalle noch für alle Kisten Kapazitäten hat. Ansonsten müssen sie nach dem Landen warten. Abholer dürfen nur zur Lagerhalle fahren, wenn noch mindestens eine Kiste in der Lagerhalle ist. Ansonsten müssen sie nach dem Landen warten. Es gibt nur einen Kran, der Flugzeuge nacheinander be- und entladen kann. Der Kran darf erst zu einem Flugzeug fahren, wenn es zur Lagerhalle gefahren ist. Ein Flugzeug darf erst zur Startbahn fahren, nachdem der Kran vom Flugzeug abgefahren ist. Die Lagerhalle ist zu Beginn leer. VVVV V VV VV Die Prozesse sehen folgendermaßen aus: Lieferant Abholer Kran ‘ate (TRUE) ein (TRUE) while (TRUE) Tan Start- und Landebahn landen> Sant Start- und Landebahn landen> <2 Pakete abliefern> <1 Paket abholen> sAbfahrt von Flugzeug> Vervollständigen Sie mit Hilfe von Semaphoren die obigen Prozesse so, dass es zu keiner Verklemmung kommen kann! Verwenden Sie ganzzahlige Semaphore und geben Sie zu den verwendeten Semaphoren die Startwerte an! Sperrphasen sind möglichst kurz zu halten. 2. Prozess- und Prozessorverwaltung 2.1 Erklären Sie kurz den Unterschied zwischen einem Programm und einem Prozess! 2.2 Nennen Sie die Zustände, die ein Prozess aus Betriebssystemsicht einnehmen kann! Übertragen Sie dafür unten abgebildetes Zustandsdiagramm auf Ihr Arbeitsblatt! Tragen Sie die Zustände in die Kreise ein und benennen Sie die Zustandsübergänge 1 bis 4! Fortsetzung nächste Seite! Herbst 2006 Einzelprüfungsnummer: 66114 Seite: 8 a 2.3 Erläutern Sie kurz die Vorgehensweisen der folgenden Scheduling-Algorithmen: * Round Robin * First-come, First-served * priority scheduling (statisch) Gehen Sie auch auf die Kriterien Fairness, Echtzeitfähigkeit und unterbrechend ein! 2.4 Fünf Stapelverarbeitungsaufgaben A bis E kommen in einem Rechenzentrum an. Die folgende Tabelle zeigt für jede Stapelverarbeitungsaufgabe die Ankunftszeit, die Laufzeit sowie die Priorität. Die Priorität wächst mit steigenden Zahlen. Laufzeit Priorität a) Bestimmen Sie für jeden der in der Aufgabe 2.3 genannten Scheduling-Algorithmen die durchschnittliche Prozessdurchlaufzeit (Verweilzeit)! Vernachlässigen Sie dabei den Overhead des Prozesswechsels! Die Zeitscheibe für Round Robin betrage 2ms. b) Welchen Algorithmus würden Sie auswählen? Begründen Sie kurz Ihre Entscheidung! 3. Speicherverwaltung 3.1 Eine Arbeitsspeicherverwaltung wende dynamische Segmentierung an und habe in der Freispeicherliste noch drei Segmente von 700, 450 und 300 Speichereinheiten zur Verfügung (Reihenfolge wie Aufzählung). Es treffen nun nacheinander Anforderungen von 100, 300, 400, 300 und 250 Speichereinheiten an. Wie würden mit dem first fit- und dem best fit-Verfahren die Speichereinheiten auf die Segmente verteilt werden? Stellen Sie Ihr Ergebnis in einer zu unten stehender äquivalenten Tabelle dar, vergleichen Sie die Ergebnisse und erläutern Sie die Unterschiede! Geben Sie hierbei jeweils die noch freien Speichergrößen an! Anforderung | First Fit | Segment | Semen [Samen 2] Sams | Segms Semen 2 [Soman | 70 | 450 | 30 | Fortsetzung nächste Seite! Herbst 2006 Einzelprüfungsnummer: 66114 Seite: 9 3.2 Als weitere Möglichkeit gibt es das Verfahren worst fit. Erläutern Sie kurz die Verfahrensweise, Vor- und Nachteile! AUFGABE 2: 1. Speicherverwaltung a) Skizzieren Sie (grafisch) die Abbildung einer logischen Adresse in eine physikalische Adresse in einem System mit Segmentierung! b) Was muss das Betriebssystem tun, wenn aufgrund von Hauptspeichermangel ein Segment ausgelagert werden soll? Beschreiben Sie den Ablauf und welche Änderungen in welchen der in Teilaufgabe a beschriebenen Datenstrukturen vorgenommen werden müssen! c) Was passiert, wenn der Prozess nach dem Auslagern erneut auf die Daten des Segments zugreift? Beantworten Sie in Ihrer Beschreibung vor allem die folgenden Fragen: - Welche Einheit des Systems erkennt, dass das Segment nicht vorhanden ist? - Woran wird das erkannt? - Welche Aktivitäten finden daraufhin im Betriebssystem oder in der Anwendung statt? - Welche Datenstrukturen werden in diesem Zusammenhang wie modifiziert? - Welche Prozesszustände nimmt der betroffene Prozess in welcher Phase ein? d) Ein Segment soll von zwei Prozessen gemeinsam genutzt werden. Was muss das Betriebssystem hierfür tun? e) Nennen Sie drei wesentliche Unterschiede zwischen Segmentierung und Seitenadressierung! 2. Prozesse und Prozesskoordination, Teil 1 Gegeben sei folgendes Szenario: Ein Prozess PO erzeugt Daten, die er zur Vorverarbeitung einem Prozess P1 übergibt. Das Ergebnis der Vorverarbeitung übergibt Pl dann an Prozess P2, der eine Weiterverarbeitung vornimmt. Das Ergebnis der Weiterverarbeitung wird entweder an Prozess P3 zur Ausgabe übergeben oder muss - falls es bestimmten Kriterien noch nicht genügt - nochmals an Prozess P | zur erneuten Vorverarbeitung übergeben werden. Die Prozesse P1 bis P3 verfügen jeweils über einen FIFO-Puffer (B1 - B3) mit n Speicherplätzen, über den sie ihre Eingaben entgegen nehmen. Pl hat nur einen solchen Puffer (Bl), über den sowohl PO als auch P2 die Daten bei ihm anliefern. Die Prozesse geben ihre Daten grundsätzlich in Form von Datenpaketen weiter, ein Puffer-Speicherplatz kann ein solches Datenpaket aufnehmen. | Po Pi | al P2 | ry P3 a) Beschreiben Sie, an welchen Stellen Koordinierungsbedarf in diesem Szenario besteht und mit welchen Koordinierungsmechanismen man die Zugriffe jeweils koordinieren kann! Fortsetzung nächste Seite! Herbst 2006 Einzelprüfungsnummer: 66114 Seite: 10 b) Skizzieren Sie nun in einer programmiersprachlichen Form die Operationen put und get: void put (message m) nimmt eine Nachricht entgegen und kopiert sie in den Puffer. Falls gerade kein Platz in dem Puffer frei ist, blockiert die Operation so lange, bis wieder ein Speicherplatz für die Nachricht frei wird. message get () entnimmt die nächste Nachricht aus dem Puffer. Falls der Puffer leer ist, blockiert die Operation so lange, bis wieder eine Nachricht vorliegt. c) Ist Ihre Lösung verklemmungsgefährdet? Begründen Sie Ihre Antwort, indem Sie beschreiben, wann eine Verklemmung auftreten kann bzw. warum Verklemmungen nicht auftreten werden! 3. Prozesse und Prozesskoordination, Teil 2 Gehen Sie von folgendem, gegenüber Aufgabe 2 veränderten Szenario aus: Die Puffer können jeweils nur eine Nachricht aufnehmen. Die Prozesse verarbeiten die Nachricht direkt aus dem Eingangspuffer und schreiben das Ergebnis direkt in den Puffer des empfangenden Prozesses. Beide Puffer werden erst dann wieder freigegeben, wenn die Verarbeitung beendet ist. Der Prozess P2 stellt dabei zu Beginn der Verarbeitung fest, ob eine neue Vorverarbeitung durch P1 oder die Ausgabe durch P3 folgen wird (noch bevor die ersten Ergebnisdaten produziert werden). Bevor ein Prozess seinen Eingabepuffer belegt, überprüft er, ob überhaupt Daten darin vorhanden sind. Liegen keine Daten vor, wartet er 10 Sekunden bevor er es erneut versucht. a) Skizzieren Sie den Ablauf und die Koordinierung in den Verarbeitungfunktionen der Prozesse Pl (Funktion work1 ( )) undP2 (Funktion work2 ( )). b) Welche Bedingungen für Verklemmungen treffen in dem geschilderten Szenario zu? Beschreiben Sie jeweils den Zusammenhang zwischen "abstrakter Bedingung" und konkreter Situation! c) Welche Möglichkeiten zur Verklemmungsvermeidung gibt es in dem geschilderten Szenario ganz konkret? Wie müssten Sie Ihre Funktionen work1 und work2 dafür jeweils ändern?