oo

Prüfungsteilnehmer Prüfungstermin Einzelprüfungsnummer

Kennzahl:

Frühjahr

Kennwort: 66 1 13
— 2005

Arbeitsplatz-Nr.:

Erste Staatsprüfung für ein Lehramt an Öffentlichen Schulen

- Prüfungsaufgaben -

Fach: Informatik (vertieft studiert)

Einzeiprüfung: Rechnerarchitektur, Datenbanken, Betriebssysteme
Anzahl der gestellten Themen (Aufgaben): 2

Anzahl der Druckseiten dieser Vorlage: 13

Bitte wenden!

Frühjahr 2005 Einzelprüfungsnummer: 66113 Seite: 2

Thema Nr. 1

Sämtliche Teilaufgaben sind zu bearbeiten!

1. Allgemeine Fragen zu Rechnernetzen

Antworten Sie kurz und prägnant.

a)
b)

c)

d)

Wie funktioniert das Selbstlernen bei Bridges und Switches?
Erklären Sie den Unterschied zwischen Zeit- und F requenzmultiplexen!
Beim Datentransport stellen die Anwendungen unterschiedliche Anforderungen an Datenverlust.

Übertragungszeit und Bandbreite, Erläutern Sie anhand der Anwendungen Voice-over-IP und
FTP-Filetrausfer die Gründe hierfür!

>

Was ist der Unterschied zwischen Virtual-Circuit- und Datagram-Netzen?

2. TCP

a)

b)

Erklären Sie die TCP-Prinzipien Slow Start, Congestion Avoidance, Slow Start Threshold und
Incremental Increase! Zeichnen Sie ein Diagramm, das die Entwicklung des Congestion Windows über die Anzahl der getätigten Übertragungen zeigt! Dabei ist auch ein Paketverlust zu berücksichtigen. Markieren Sie die oben beschriebenen Phasen und Schwellwerte.

Betrachten Sie eine TCP-Verbindung zwischen den Hosts A und B. Nach der HandshakingProzedur erwartet Host A die Sequenznummer 314 und Host B die Sequenznummer 271. A sendet nun 60 Bytes, die B korrekt bestätigt. Nun sendet Host A weitere 60 Bytes, diese gehen jedoch verloren. Danach hat Host A keine weiteren Daten zu übertragen. Zeichnen Sie ein Diagramm der zeitlichen Abfolge von Übertragungen (ohne Handshaking) zwischen Host A und B.
Tragen Sie auch die Sequenznummem und Acknowledgement-Nummern in das Diagramm ein.
Verfolgen Sie den Sendeverlaufbis zur erfolgreichen Bestätigung der zuletzt übertragenen 60
Bytes. Es treten keine weiteren Paketverluste auf.

Fortsetzung nächste Seite!

Frühjahr 2005 Einzelprüfungsnummer: 66113 Seite: 3

3. Routing

Betrachten Sie folgendes Netzwerk mit 4 Knoten:

Ahmen Sie die Funktion des Distance Vector Algorithmus (ohne Poisoned Reverse) nach!

Nehmen Sie dazu an, dass alle Knoten simultan und synchron Nachrichten an ihre Nachbam senden
und von diesen empfangen. Erstellen Sie Tabellen mit folgendem Inhalt:

a) Distanztabellen aller Knoten des Netzwerks nach der Initialisierung

b) Distanztabellen aller Knoten des Netzwerks nach dem ersten Nachrichtenaustausch

c) Routingtabellen aller Knoten des Netzwerks nach dem ersten Nachrichtenaustausch

Markieren Sie in den Distanztabellen die Daten, die an die Nachbarknoten gesendet werden müssen!

4. Anforderungen an Datenbanksysteme

Zur Datenspeicherung können neben Datenbanksystemen auch Einzeldateien verwendet werden. Diskutieren Sie die Begriffe Redundanz, Inkonsistenz und Integritätsverletzung und zeigen Sie, wie Datenbanksysteme hierfür Lösungen bereitstellen!

5. Generalisierung und Spezialisierung

Die Entity-Relationship-Methode kennt die Konzepte Generalisierung und Spezialisierung. Definieren
Sie diese, geben Sie Sinn und Zweck an und geben Sie je ein Beispiel!

Bei der Umsetzung ins Relationenmodell werden diese Konzepte nicht direkt unterstützt. Erläutern

Sie dies und zeigen Sie anhand des Beispiels eine Vorgehensweise, wie das Konzept trotzdem im Relationenmodell abgebildet werden kann!

Fortsetzung nächste Seite!

Frühjahr 2005 Einzelprüfungsnummer: 66113 Seite: 4

6. Normalformen

Das Instrument der so genannten Normalformen eines Datenbank-Schemas und der dazu gehörigen
Algorithmen bietet die Möglichkeit, aus der Analyse der semantischen Beziehungen zwischen Daten
eine Beurteilung des vorliegenden Schemas abzuleiten und bei Bedarf automatisch ein " gutes" Datenbank-Schema zu generieren.

Sie haben in diesem Kontext die Update-, Einfüge- und Delete-Anomalie kennen gelernt. Erläutern
Sie diese und geben Sie Beispiele ihres Auftretens, anhand derer Sie die Problematik erläutern!

7. SQL
Gegeben sei folgendes Relationenschema zur Verwaltung von Fußballbundesliga-Daten:

MANNSCHAFT (Vereinsname, Kapitän, Stadion)
SPIELER (SpielerID, Name, Vorname, Wohnort, Vereinsname)
MATCH (MatchID, Datum, Heimverein, Gastverein, ToreHeim, ToreGast)

Beispiel für MATCH:
Bayern München spielt in Köln gegen den 1. FC Köln. Bayern München verliert 2:1.
Dann gilt: ToreHeim=2 und ToreGast=].

Die Primärschlüssel der Relationen sind wie üblich durch Unterstreichen gekennzeichnet.
Kapitän in MANNSCHAFT ist Fremdschlüssel zu SpielerID in SPIELER.

Vereinsname in SPIELER ist Fremdschlüssel zu Vereinsname in MANNSCHAFT.
Heimverein in MATCH ist Fremdschlüssel zu Vereinsname in MANNSCHAFT.
Gastverein in MATCH ist Fremdschlüssel zu Vereinsname in MANNSCHAFT.

Formulieren Sie die folgenden Anfragen in SQL:
a) Wo wohnt der Kapitan der Mannschaft ,1. FC Nürnberg’?
= b) Geben Sie alle Spielbegegnungen an, die mit einem Sieg der Gäste geendet haben. Ihr Ergebnis

soll aus dem Datum des Spiels, der Bezeichnung des Stadions, in dem das Spiel stattgefunden hat,
und der Tordifferenz bestehen.

Fortsetzung nächste Seite!

Frühjahr 2005 Einzelprüfungsnummer: 66113 Seite: 5

8. 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 Fremdschlüsselattribute die Namen der referenzierten Primärschlüsselattribute. Primärschlüsselattribute sind zu unterstreichen, Fremdschlüsselattribute zu überstreichen.

1 n
Flugzeug Flug

hat
Kapazität

Passagier

Sitzklasse

=> a=

9. 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):

Start, Variablen initialisieren

Konfigurationsdatei einlesen

kurze Vorberechnungen durchführen (Dauer: 2 ms)
Berechnungsdaten aus Datei einlesen

Berechnung durchführen (Dauer: 800 ms)

Ergebnis in Datei ausgeben

Ende

ANAM Oe

Fortsetzung nächste Seite!

Frühjahr 2005 Einzelprüfungsnummer: 66113 Seite: 6

- 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, 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 wichti g und in welchen Systemen ist sic verzichtbar?

10. Verklemmungen
a) Welche Bedingungen müssen gegeben sein, damit eine Verklemmung auftreten kann?

b) 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!

11. 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ösglichkeiten gibt es, Seitenflattern zu vermeiden? :

Frühjahr 2005 Einzelprüfungsnummer: 66113 Seite: 7

Thema Nr. 2

Sämtliche Teilaufgaben sind zu bearbeiten!

1. Rechnerarchitektur: Speicherhierarchien

a)

b)

Speicherhierarchien basieren auf dem Konzept der räumlichen und zeitlichen Nähe (Lokalitat).
Was versteht man im Kontext der Speicherhierarchien unter diesen beiden Begriffen?

Es gibt zwei grundsätzliche Strategien für Schreibzugriffe auf einen Cache: write-back (oder
store-back) und write-through (oder store-through). Was ist der Unterschied?

2. Rechnerarchitektur: Befehlssätze

Was versteht man unter einem orthogonalen Befehlssatz und welche Idee steckt dahinter, einen solchen anzustreben?

3. Rechnerarchitektur: Schaltnetze

a)

b)

In dieser Aufgabe ist ein 2-zu-1 Multiplexer zu entwerfen. Der Input für einen solchen Multiplexer sind zwei Eingabekanäle A und B und eine 1-Bit Auswahlleitung S. Die Ausgabe ist ein einziger 1-Bit-Kanal Z. Wenn S = 0 ist, soll Z = A sein, wenn S = J dann Z = B. Geben Sie die
Funktionstabelle, die boolsche Funktion und das Schaltnetz an!

In welcher Relation steht die Anzahl der Eingänge eines Multiplexers mit der Anzahl der benö-
tigten Auswahlleitungen?

4. Rechnerarchitektur: von Neumann

a)

b)

Ausgehend vom Modell eines von-Neumann-Rechners: Erklären Sie kurz, welche Vorteile sich
ergeben, wenn Programm und Daten in demselben Speicher gehalten werden.

Dieser Speicher habe nun 2” Zellen. Jede Zelle soll 4 Byte aufnehmen können. Wie breit muss
der Adressbus sein, um alle Speicherzellen adressieren zu können? Wie breit muss der Datenbus

sein, um in einem Zyklus eine komplette Zelle transportieren zu können?

Was ist der von-Neumannsche-Flaschenhals?

Fortsetzung nächste Seite!

Frühjahr 2005 Einzelprüfungsnummer: 66113 Seite: 8

5. Rechnerarchitektur: Pipelining
a) Sei gegeben eine Befehls-Pipeline mit k Stufen und eine Anzahl von n zu bearbeitenden Operationen. Wie viele Takteinheiten sind minimal notwendig, bis alle Operationen vollständig abgearbeitet sind?

b) Hazards sind der Grund, warum dieser optimale Durchsatz in den meisten Fällen nicht erzielt
werden kann. Erklären Sie, wann Branch Hazards (Control Hazards) auftreten und warum sie die
Performance von Pipelines beeinträchtigen!

c) Skizzieren Sie vier Strategien, mit Branch Hazards umzugehen!

d) Benennen Sie die beiden weiteren Hazard-Typen und erklären Sie kurz, wann Sie eintreten!-Geben Sie für beide Hazard-Typen.an, ob es möglich ist, Prozessoren zu bauen, in denen der jeweilige Hazard nicht eintreten kann!

6. Rechnernetze: Kommunikationsarchitekturen

a) Welche speziellen Probleme treten bei Rechnernetzen im Vergleich zu Einzelsystemen auf?

b) Erklären Sie kurz die Begriffe Dienst und Protokoll. Beschreiben Sie auch deren Zusammenhang!

c) Beschreiben Sie, wie eine N-PDU aus einer N-SDU entsteht. Erklären Sie auch kurz die Abkürzungen JCI und PCI. Welche Rolle spielen diese?

7. Rechnernetze: Die Bitübertragungsschicht

Die Hauptaufgabe der Bitübertragungsschicht (Physical Layer) besteht in der transparenten Übertragung von Bitsequenzen über einen Kommunikationskanal.

a) Welche Teilschritte müssen bei der Digitalisierung analoger Daten erfolgen?

b) Beschriften Sie alle Pfeile in nachfolgender Zeichnung mit den einschlägigen Fachbegriffen.

Daten Signale

diskret _—D—————— digital

analog Te analog

Fortsetzung nächste Seite!

Frühjahr 2005 Einzelprüfungsnummer: 66113 Seite: 9

c) Wie ist der Zusammenhang zwischen Bit/Sekunde und Baud bei der Manchestercodierung?
d) Nennen Sie die wesentlichen Störeinflüsse auf

i) optische Leiter

ii) elektrische Leiter.
8. Rechnernetze: Das TCP/IP-Referenzmodell

Das TCP/IP-Referenzmodell setzt sich im Gegensatz zum OSI-Referenzmodell aus vier Schichten
zusammen. Dabei nimmt das Internet Protokoll (IP) eine wichtige Rolle ein.

a) Nennen Sie die Standard-Adressklassen von IP und erklären Sie, auf welche Eigenschaft der Adresse sich diese Klassifizierung bezieht!

b) Geben Sie 3 Beispiele wichtiger Informationen an, die außer den Adressen in IP-Headern zu finden sind!

c) Erläutern Sie in einem Satz die Aufgaben von ICMP!
d) Nennen Sie vier Erweiterungen von IPv6 gegenüber IPv4 hinsichtlich der Funktionalität!
©) Woraufbezieht sich die Sequenznummer beim TCP-Protokoll?

D Wie wird Flusssteuerung bei TCP geregelt? Welche Parameter spielen dabei eine Rolle?

9. Datenbanksysteme
a) Das Entity-Relationship Modell

In einer Datenbank sind die Daten von Lehrern, Schülern, Klassen und Fächern einer Schule gespeichert. Ein Lehrer hat dabei eine Personalnummer, einen Namen, eine Adresse und eine Gehaltsstufe.
Schüler haben neben einer Identifikationsnummer einen Namen, eine Adresse und gehören einer einzigen Klasse an. Klassen sind eindeutig durch ihre Klassennummer bestimmt und ihnen ist jeweils
genau ein Klassenraum zugeordnet. Eine Klasse wird von genau einem Lehrer in einem Fach unterrichtet. Ein Lehrer kann jedoch dieselbe Klasse in unterschiedlichen Fächern unterrichten. Zusätzlich
hat jeder Lehrer die Leitung maximal einer Klasse inne.

i) Erstellen Sie ein Entity-Relationship-Diagramm für obige Datenbank.

ii) Erläutern Sie, welche Möglichkeiten es gibt, um 1:n-Beziehungen aus dem ERModell im Relationalen Modell darzustellen!

Fortsetzung nächste Seite!

Frühjahr 2005 Einzelprüfungsnummer: 66113 Seite: 10

b) Normalisierungstheorie

Gegeben sei die nachfolgende relationale Datenbank. Sie enthält die Daten der ausgeliehenen Filme

einer Videothek. Dabei kann ein Film in mehreren Kopien vorhanden sein. Ein Kunde kann aber nur
eine Kopie eines Filmes ausleihen:

[Ausleihe [FilmNr | Kdnr | Name | Adresse ] Titl _  ] Leihgebühr |
Müller | München. Fifth Element
Müller | München | Der Schuh des Manitu
Huber | Nürnberg Sixth Sense
Huber | Nürnberg | Der Schuh des Manitu
Meier | Hamburg Romeo & Julia
Meier | München Sissi

2 [en | [eo Ir in
meer [ee
ea fen ja lın eo

i) Erläutern Sie, inwiefern obiges Schema die 2. Normalform verletzt!
li) Geben Sie für obige Datenbank alle vollen funktionalen Abhängigkeiten an!

iii) Überführen Sie das obige Relationenschema in die 3. Normalform! Erläutern Sie die dazu durchzuführenden Schritte jeweils kurz!

c) SQL

Gegeben sei das folgende relationale Datenbankschema (Schlüsselattribute sind jeweils unterstnchen):

Personal (PNR, Name, Adresse, Gehalt, ANR)
Abteilung (ANR, Bezeichnung, Leiter, FNR)
Filiale (FNR, Ort)

In der Datenbank sind die Daten von Angestellten, Abteilungen und Filialen eines Handelsunternehmens gespeichert. Jeder Angestellte hat eine Personalnummer (PNR), einen Namen, eine Adresse,
ein Gehalt und ist in einer bestimmten Abteilung beschäftigt. Jede Abteilung hat eine Abteilungsnummer (ANR), eine Bezeichnung, die Personalnummer des Abteilungsleiters (Leiter) und gehört zu
einer bestimmten Filiale. Jede Filiale hat eine Filialnummer (FNR) und ist in einem Ort beheimatet.

Fortsetzung nächste Seite!

Frühjahr 2005 Einzelprüfungsnummer: 66113 Seite: 11

Formulieren Sie folgende Anfragen in SQL:

i) Bestimmen Sie Name und Adresse aller Angestellten, die in Filialen in Berlin beschäftigt sind!

ii) Geben Sie für jede Abteilung die Nummer und die Bezeichnung der Abteilung zusammen mit der
Personalnummer und dem Namen des Abteilungsleiters aus! Das Ergebnis soll aufsteigend nach
der Abteilungsnummer sortiert werden.

li) Bestimmen Sie die Personalnummern aller Angestellten, die in der gleichen Abteilung wie der
Angestellte mit der Nummer 333 arbeiten und mehr Gehalt verdienen!

iv) Geben Sie für jede Filiale die Filialnummer zusammen mit dem minimalen und dem maximalen
Gehalt der in der Filiale beschäftigten Angestellten aus! Dabei sollen nur Filialen mit mindestens
vier Abteilungen berücksichtigt werden. \

v) Bestimmen Sie die Anzahl derjenigen Angestellten, die weniger als das durchschnittliche Gehalt
aller Angestellten verdienen!

vi) Bestimmen Sie die Liste der Filialnummern derjenigen Filialen, deren Angestellte alle mehr als
500 EUR Gehalt verdienen!

10. Betriebssysteme: Prozess-Fortschrittsdiagramme

Gegeben seien zwei Prozesse A und B. A benötigt zu seiner Ausführung 12 Zeiteinheiten, B
benötigt 10 Zeiteinheiten. Es stehen insgesamt 5 verschiedene, exklusive Betriebsmittel (BM)
zur Verfügung, die von den Prozessen während der Ausführung benötigt werden. Die folgende
Tabelle zeigt, in welchen Intervallen die beiden Prozesse BM belegen:

Prozess | BMI BM2 BM3 BM4 BM5
A |1-3,9-i 6-8 2-5 7-1 2-39-10
B 2-4 3-5,7-9 4-6 4-5,8-9 1-4

Bereiche an! -

Fortsetzung nächste Seite!

Frühjahr 2005 Einzelprüfungsnummer: 66113 Seite: 12

1
1
4
'
i
'

1

’
eg

'

'
het he eh ce Limiter =
'
i
1
1
!

t

1
=>

|

|
©

i
i
i
1
t
rt

t
ew

I

t
r

F
-L

'

4

t

i
TP

I

7--4--

!
t

4
|

co

J
4
'
4
I
ma
1
!
an“ rr IIIPreien
t
wu im br) ee re
!
1
4
1

1
1
TUT TP TAT

f
1

(
t
--r|
i)

i
I
t
1
t

IS

1
t

“4°°
Mn

+

1
t t
t 1
TAT TP TAT TP TT TT
4 '
1

'
Jul a

t

J
na
Co] ==

I

N

|
10 4 12 A

k

sdonbs Jec.odnetod a Je
1
t

{
!
rattan ope
'
wel
(
t
7
(
L
!
'
=
'
is
5
'
or
'

b) Erklären Sie die Bedeutung von unmöglichen und unsicheren Bereichen und deren Zusammenhang mit Deadlocks!

©) Zeichnen Sie 4 verschiedene Pfade im obigen Prozessfortschrittsdiagramm ein, die die Prozesse
A und B terminieren lassen!

11. Betriebssysteme: Second-Chance-Algorithmus

Der Second-Chance-Algorithmus (eine Variante des Clock-Algorithmus) verwendet für die Auswahl der zu verdrängenden Seiten eine zyklische Datenstruktur wie die unten skizzierte

Fortsetzung nächste Seite!

Frühjahr 2005 Einzelprüfungsnummer: 66113 Seite: 13

Der einzige Unterschied zum Clock-Algorithmus besteht darin, dass der Zei ger imuner auf die zuletzt
eingelagerte Seite verweist. Bei einem Zugriff auf eine Seite wird das dazugehörige U-Bit (Use-Bit)
von der Hardware auf 1 gesetzt.

Eine Seite mit der Nummer 10 soll in den Hauptspeicher geladen werden.

a)

b)

2)

d)

Erklären Sie die prinzipielle Funktionsweise des Clock-Algorithmus (2-3 Sätze)!
Welche Seite wird in obigem Beispiel aus dem Hauptspeicher verdrängt werden?
Skizzieren Sie die obige Datenstruktur nach dem Einlagern der neuen Seite!

Was passiert, wenn die U-Bits aller Seiten auf 1 gesetzt sind und ein Zugriff auf eine nicht im
Hauptspeicher befindliche Seite erfolgt?

Der Enhanced-Second-Chan ce-Algorithmus verwendet zusätzlich zum vom Second-ChanceAlgorithmus bekannten Use-Bit (U-Bit) noch ein Modified-Bit (M-Bit), das angibt, ob eine im
Hauptspeicher geladene Seite verändert wurde oder nicht. Jede im Hauptspeicher enthaltene Seite
fällt damit in eine der folgenden Klassen:

eU=0,M=0
eU=1,M=1
 eU=0,M=1
U=1,M=0

i In welcher Reihenfolge sollten Seiten dieser unterschiedlichen Klassen für eine Verdrängung
aus dem Hauptspeicher ausgewählt werden? Begründen Sie kurz Ihre Entscheidung!

ii) Was erhofft man sich durch diese Strategie zu verbessern?

Wie könnte der.(einfache) Second-Chance-Algorithmus verbessert werden, so dass er Least Recently Used (LRU) besser approximiert? (1-2 Sätze)