Prüfungsteilnehmer

Prüfungstermin

Einzelprüfungsnummer

l(snnzahl:

Frühjahr
Kennwort:

2002

66113

Arbeitsplatz-Nr.:

Erste Staatsprüfiurgfür ein Lehramt an öffentlichen Schulen
PrüfungsaufgabenFach:

Informatik (vertieft studiert)

Einzelprüfung:

Rechnerarchitektur,Datenb.rBetriebssys.

Anzahlder gestelltenThemen(Aufgaben): 2
Anzahlder Druckseiten
dieserVorlaee:

10

Bitte wenden!

Frühjahr 2002

Einzelprüfungsnuulmer:
66L13

Seite:2

Thema Nr. L

Sämtliche Teilaufgaben sind zu bearbeiten!

Aufgabe I : Relationale Datenbankanfragen

In einer Datenbankbefinden sich Relationenmit den foleendenRelationenschemata
( Schlüsselattribute sind j eweils unterstrichen):
Lieferant lLNr I LName I LOrt

I Rechtsform

Waren

Kundenlrx.

lrNamelrort I

BestellunglLNr lKNr lWNr lDatum

1. Geben Sie für die folgendenverbal formulierten Anfragenjeweils Anfrageformulierungenin zwei
verschiedenenAnfragesprachenbzw. -formalismenan (zur Auswatrl stehendabei SQL, Relationenalgebra,Tupelkalkül und QBE (Query by Example))!

a) Geben Sie alle Paarevon Lieferanten(-namen)und Kunden (-namen) aus,bei denender Kunde
bei dem LieferantenWaren bestellt hat und Kunde und Lieferant sich am eleichenOrt befinden!

b) Geben Sie alle Waren (mit allen Attributen) aus,zu denenes mindestenszwei Lieferantenmit
unterschiedlicherRechtsformgibt, bei denenKunden dieseWaren bestellt haben!
2. Formulieren Sie die folgendenAnfragen in SQL:
a) BerechnenSie für jeden Lieferantendie Anzahl der Kunden, die Waren bei diesemLieferanten
bestellt haben! Geben Sie dazu Lieferanterulamenund die Anzahl der Kunden aus!
b) Geben Sie für jeden Tag die Gesamtanzatrlan bestelltenWaren aus!
c) BerechnenSie für jeden Kunden (unter Angabe desKundennamens)den Gesamtpreisaller von
dem Kunden bestelltenWaren!
FortsetzungnächsteSeite!

Frühjalu 2002

Seite:3

: 66LL3
Eirzelprüfungsnummer

Aufgabe 2 : Medienzugriffsprotokolle
l. SkizzierenSie kwz dasVerhalten des Token- Ring- Verfahrens und des CSMA/CDVerfahrens (Ethernet)unter extrem hoher Last. Leiten Sie darausab, inwieweit die Verfahren für
Umgebungenmit Echtzeitanforderungengeeignetsind.

Hinweis: Berücl<sichtigenSie dabeivor allem die Zugrffizeiten der Stationenauf das Medium
atz.
und den Nutzdaten-Grenzdurclts

2. SkrzzierenSie nun dasVerhalten beider Verfatren unter niedriger Last! BerücksichtigenSie
dabei vor allem dieZuwrfßzeiten der Stationenauf das Medium!

Aufgabe 3: ISO-OSI-Schicht 1
1. Auf einemKanal stehteine Bandbreitevon 6 MHz zur Verfügung. Welche Daterrrate(in
Bit/Sekunde)kann bei Verwendung vierstufiger Kodierung erreichtwerden?
Z.Erklaren Sie den UnterschiedzwischenBit/Sekundeund Baud! Wie ist der Zusammenhangbei
Verwendung der Manchestercodi erung?
3. NennenSie die wesentlichenStöreinflüsseauf:
a) elektrischeLeiter
b) optischeLeiter

4. Auf welche Art von Leitern lässt sich dasNyquist-Theoremanwenden?(kurze Begrtindung)

nächsteSeite!
Fortsetzung

Frtihjahr 2002

Einzelprüfungsnummer:
66113

Seite:4

Aufgabe 4: ISO-OSI-Schicht 3
l. Nennen Sie 3 Vermittlungsverfahrenund beschreibenSie diesekurz!
2. Welches Vermittlungsverfährenwird im Internet (IP) verwendet?
3. Nennen Sie Eigenschaften,die zur Klassifizierungvon Routingverfahrenverwendetwerden
können!
4. BeschreibenSie die Funktion des RoutingverfahrensÄ.IPl
5. Erklären Sie, warum k[P zunehmenddurch OSPF ersetztwird!

Aufgabe 5: von Neumann Rechner
Gegebensei ein von NeumarurRechner.
1. Welche Aufgaben habender Daten- und der Befehlsprozessor?
2. Erklären Sie kurz, welcher Vorteil sich ergibt, wenn Programmund Daten in dem selben
Speichergehaltenwerden?
3. Der Speicherhat2" Zellen. JedeZelle kann 4Byte aufirehmen.Wie breit müssenjeweils Adressund Datenbussein, d.h. auswie vielen Leitungenbestehendie Busseunter der Annahme, dass
pro Leitung I Bit kodiert werden kann?
4. Was ist der von NeumannscheFlaschenhals?

FortsetzungnächsteSeite!

Frühjahr 2002

Einzelprüfungsnurlmer
: 66LI3

Seite:5

Aufgabe 6: Seitenadressierung
Gegebensei ein Systemmit Seitenadressierung.
Die Seitengrößebetragep.
1. NennenSie Gninde, die für eine Wahl eineskleinen bzw. großenWertes für die Seitengrößep
sprechen!
2. Was verstehtman im Fall von Seitenadressierung
unter interner Fragmentierung?
3. Welche Information muss in der Seitentabelleunabhängigvon der gewähltenSeitenverdrängungsstrategie
mindestensenthaltensein?
4. Es sei e die Größeeines Seitentabelleneintrags
und s die dwchschnittliche Größeeinesim
HauptspeichergehaltenenPrograrnms.Bei welchem Wert für die Seitengrößep wird die Summe
ausinterner Fragmentierung und Grö/3eder Seitentabelleminimal?
5. WelcherWert ergibt sich nach Teilaufgabe4. für die optimale Seitengrößepbei s:32 KByte und
e:8 Bye?

Aufgabe 7: Deadlocks
GebenSie die vier Voraussetzungenfür die EntstehungeinesDeadlocks an sowie wie diese verletzt
werdenkönnen.um Deadlockszu verrneiden!

-6Frtrtrjahr 2002

Einzelprüfungsnummer
: 66LL3

Seite:6

Thema Nr. 2
Sämtliche Teilaufgaben sind zu bearbeiten!

Aufgabe I
a) ErläutemSie anhandeiner Skizzedie Bildung derphysikalischenAdressebei Seitenadressierung.
WelcheVorteile versprichtman sichvon ihrer Benutzung?WelcheNachteilebringt ihr Einsatzmit
sich?
-

b) In denEinträgender Seiten-Kachei-Tabelle
werdenmeist noch Indikatorenmitgeführt, die
anzeigen,ob
1. die Seiteim Arbeitsspeicher
anwesend
ist (Anwesenheits-Bit),
2. die Seiteim Arbeitsspeicher
wurde@enutzt-Bit)
angesprochen
3. die Seiteim Arbeitsspeicher
modifiziertwurde(Modifikations-Bit).

Wozu werdendieseInformationenbei t iachladenauf Verlangen(demandpaging)'vom
Betriebssystem
benutzt?
c) Bei der Implementierungvon Programmen,die große,in einerDatei hinterlegteDatenbestlinde
bearbeiten,ist es einehäufig benutzteVorgehensweise,
die Zugriffe entsprechendder Ideedes
Nachladerns
auf Verlangen'zugestalten(d. h. ein'SoftwarePaging'zuimplementieren).
Zu
diesemZweck wird eine Anzahl Kachelnvereinbart.Der Zugriff auf die Daten erfolgt
ausschließlichüber eine Prozedurschreibe_Zeichen
zum SchreibeneinesDatenelementes
und eine
Funktion lies Zeichenzum Lesen!

nächsteSeite!
Fortsetzung

Frühjahr2002

Seite:7

Einzelprüfungsnummer:
66LL3

Zum Lesenund Schreibender einzelnenDateiseitenexistierenzwei Prozeduren(die jedoch nur durch
verwendetwerden
die Funktion zum Lesenund die Prozedurzum Schreibenvon Datenelermenten
sollen).Damit ergibt sich die untenstehende
GrundstnrktureinessolchenProgramms(wobei zur
wird, dassessich um eineTextdatei
Vereinfachungder Implernentienrngsüberlegungen
angenommen
handelt).Entwickein Sie durch schrittweiseVerfeinerungdie Rümpfezw Prozedurschreibe_Zeichen
und zur Funktion lies_Zeichen!Als Ersetzungsstrategie
soll entweder'SecondChance'oder 'Least
RecentlyUsed'verwendetwerden.
an!
GebenSie auchdie notwendigenErgänzungender Variablen-Vereinbarungen

aucheineKachel-SeitenHinweis:Es ist zweckm?ißig,
zusätzlichzu einerSeiten-Kachel-Tabelle
Tabellezu führen!

programTextdatei(input,output);
vor. *)
constm = ...;(* DasProgrammsiehtm+l 'Software-Kacheln'
*)
k = ...; (* JedeKachelkarurk+l Zeichenaufirehmen
o: ...' (*Die Dateibesteheausn+l SeitenderLängek+I. *)
var Kacheln:array[0.. m] of array[O.. k] of char;
...;

procedureschreiblin_Datei(Datei_Seitennummer:integer;
Kachelnummer:integer);
(* Die Prozedurüberhägtden Inhalt von Kacheln[Kachelnummer]in
angegebene
die durchDatei_Seitennummer
Seiteder Datei. *)

procedurelies_aus_Datei(Datei_Seitennummer
:integer;
Kachehummer:integer);
(* Die Prozedurüberträgtdie angegebene
Seiteder Datei nachKacheln[Kachelnummer].*)
...:

procedureschreibe_Zeichen(
integer;
Zeichennummer:
Zeichen:char);
.-;

integer):char;
function lies_Zeichen(Zeichennummer:
...;

nächsteSeite!
Fortsetzung

Frühjahr 2002

Einzelprüfungsnummer
: 66L13

Seite:8

Aufgabe2
a) Entwickeln Sie (filr Einbenutzerbetrieb)eineDatenstrukturzur Speicherungeines
Telefonverzeichnisses,
wobei die EinträgeName,Vomameund Telefonnummerenthaltensein
sollen!
Die Datenstruktu soll sowohl eine effiziente Vorgehensweise
beim EinfügenneuerEinträgeals
auchbei der SuchenachEinträgenermöglichen(Uischenbrauchtnicht vorgesehenzu werden).Als
Basissoll ein Betriebssystem
mit 'Anforderungauf Verlangen@emandPaging)'dienen.
Die Frage
desAblegensder Datensürrlcturin einerDatei bzw. desWiederladenskönnenSie unberücksichtigt
lassen.
_ErläutemSie anhandvon Beispielendie Vorgehensweise
beim Einfügenund beim Suchen!
b) EntwickelnSieeinenicht-rekursive
Prozedur,die dasVerzeichnisalphabetisch
sortiertausgibt.Die
Prozedursoll direkt auf der Datenstrukturarbeiten,d. h. ohneVerwendungder Such-Prozedur!
DabeikönnenSieunterstellen.
dasseile Prozedurzum DruckeneinesEintraesbereitsexistiert.

FortsetzungnächsteSeite!

Frühjahr 2002

Einzelprüfungsnumm
er: 66LL3

Seite:9

Aufgabe 3: Funktionale Abhängigkeiten, Normalisierung

Gegebenseiendie folgendenRelationenschemata
R1, R2, R: und R+ mit ihren Attributen und
zugehörigen funktionalenAbhiingigkeiten (FDs):
RI:ABCD

FDs: A+BCD,
B+C,
C-+D

R2E
: FGH

FDs: E F +G,
F-+H

R I :I K L M

FDs: I -> K,
K-+L,
L+M

RaO
: PQR

F D sO
: P +Q,
P eR,
QR JP,
R

-+O

1. BestimmenSie für jede Relationalle möglichenSchlüssel(-kandidaten)!
2. GebenSie fürjedes der oben aufgeführtenRelationenschemata
an, ob es in 2. Normalform (2I.IF)
und ob es in 3. Normalform (3I.IF) ist. BegründenSie diesjeweils kurz!
3. Fär die Relationenschemata,
die nicht in 2NF bzw.3NF sind, gebenSie bitte neue
Relationenschemata
in 3NF an. Erläutern Sie die dazu durchzuführendenSchrittejeweils kurz!

Fortsetzung
nächsteSeite!

Frühjahr 2002

Einzelprüfungsnummer
: 66113

Seite:10

Aufgabe 4 : Verbindungsmanagement

1. Fenstertechniken(Sliding Window) zur Flußkontrolle beschränkenden maximalen Durchsatzauf
einer Verbindung,wenn eine maximale Fenstergröße(Window Size) festgeleglwird. Begründung?

2. GehenSienun von einerFenstergröße
von 8, einer (festen)Paketlängevon 1000bit (Nutzdaten)
und einemRoundtrip-Delayvon 0.25saus!WelchermaximaleDurchsatzist unter dieser
Voraussetzungmöglich? Yereinfachende
Annahmen: Reahionszeitder Stationenund Nachrichtenübertragungszeitsind vernachlässigbar.

3. Ein Roundtrip-Delayvon 0.25serscheintauf dem DataLink Layer als sehroder sogarunrealistisch
hoch - für welchesEinsatzszenarioist dieserWert durchausrealistisch?Kurze Begründung!

Aufgabe5: Kontroll- und Datenpfad

1. Erkläen SiedenUnterschied
zwischeneinemSingle-Cycleund Multi-Cyc1e-Datenpfad.
2. ErklärenSie,warum der Single-Cycle-Datenpfad
heutzutageunter Performance-Gesichtspunkten
nicht eingesetztwird.

3. Wie bestimmtman die LängeeinerPipelinestufe,d.h. wie lang mussdasZeitintervall für eine Stufe
mindestenssein?

4. Warum müssendie Pipelinestufeneinegleich langeAusführungszeitbesitzen?
5. Wovon hängl der LeistungsgewirureineridealenPipelineab (also ohneBerücksichtigungvon
Konflikten)?
6. WelcheArten von Konflikten Q{azards)gibt esbeim Pipelining?GebenSieje ein Beispiel an!
7. WelcheMöglichkeiten gibt es(a:.rer DelayedBranch)Pipeline-StallsnacheinemBranch-Befehl
zu verhindem?