häfungsteilnehmer

Prüfungstermin

Einzelprüfungsmunmer

Kennzahl:

Herbst
Kennwort:

2000

66113

Arbeitsplatz-Nr.:

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

Informatik (vertieft studiert)

Eirzelprüfung:

Rechnerarchitelitur,Datenb.,Betriebssys.

Anzahl der gestelltenThemen(Aufgaben):

z

Arzahl der DruckseitendieserVorlage:

7

Bitte wenden!

Herbst2000

Einzelprüfungsnummer:
66113

Seite:2

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

Aufgabe 1:

Mikroprogrammierung

a) Vergleichen Sie festverdrahtetemit mikroprogrammierter Steuerung.
b) Frktären Sie horizontale und vertikale Mikroprogrammierung, beschreibenSie die Unterschiede
und leiten Sie darausVor- und Nachteileab.
c) Welche Art der SteuerungerscheintIhnen für eine Rlsc-Architektur am bestengeeignet?Begründen Sie Ihre Aussagel

Aufgabe 2:

Vennittlungsarten

a) was sind die Merkmale von verbindungsorientierterund verbindungsloserübertragung?
b) Erläutern Sie die verschiedenenVermittlungsarten:
(i)

Leitungsvermittlungbzw. Durchschaltevermittlung

(ii) Nachrichtenvermittlung
(iii) Pakewermiulung
c) Erklliren Siedie Begriffe:
(i) virnrelleVerbindung
(ii) Datagramm

Aufgalie 3:

Routing

a) Was verstehtman unter Wegewahl(Routing)rrndwelcheZiele werdenhierbei verfolgt?
b) Auf welcher/welchenEbene/ndesoSI Referenzmodellsfindet eine wegewahl statt?
c) NennenSie Methodenzur Wegewahlund klassifizierenSie diese.
d) Beschreiben
SiedenVorgangdes"directory-routing".
e) Was verstehtmanunterder "hot-Dotato"-Technik?
FortsetzungnächsteSeite!

Herbst2000

Arrfgabe4:

r : 66LL3
Einzelprüfungsnumme

Seite:3

Medienzugriffsverfahren

Eigena) NennenSie drei Medienzugriffsverfahren
und diskutierenSie ihre charakteristischen
schaften.
kennenSie?Warummussbei dem CSMA/CDb) WelcheVariantendesCSMA/CD-Verfahrens
verfalrrenderKonflilaparamerer
K << 1sein? (*= rr ,*tr',Stg:"uyfrcü
,*\
\-- Nachrichtenübertragungszeit)
NennenSie charakteristische
wird in einemFDDI-LAN verwendet?
c) WelchesZugriffsverfatrren
eines
FDDI-LANs.
Eieenschaften

Aufgabe 5:

Client-Server Konzept

a) Was verstehtman unter dem ClienrServer-Modell und welchenEinfluss hat es auf die heutigen
Rechnerarchitekturen?
kennenSie für verteilte Systeme?
b) Welche weiterenStruktuderungsmodelle

Aufgabe 6:
BMo vonBetriebsminelnkonGegebenseiendie ProzesseP,, ..., Pr, die umvier ArtenBM,
über
Zahlenangaben
entziehbar.
kurrieren. Alle Betriebsmittel seienexklusiv und nicht
/nr\

t ' l
lTtol

Betriebsmittelwerdenim folgendenals Vekfor i = ,;
I I
It - tt

wobeidie i-te
geschrieben,

\nq)

Velqtorkomponentefür q Eintreitender BetriebsmittelartBM' (i : 1, .. ., 4) steht.
Im Folgenden bezeichne
. ä die Gesamtarzahl aller Betriebsmittel
' bi die Arzatrl der Betriebsmittel, die Prozess
.h

4 besitzt

die Anzahl der Betriebsmittel, die ProzessP, zusätzlichfordert

0 - 1 ,. . . , 5 )

FortsetzungnächsteSeite!

Herbst2000

Einzelprüfungsnummer:
66113

Seite:4

a) Geben Sie den Prozess-Betriebsmittel-Graphenflir die folgenden Werte an:
/{ \
./r!

\

l J l

l

.

l

1
6l l
t

C

l

l

a

l

l

l r l
I

t

| 'tl
t

\-/
+

t

r0)
I
I

/n\
" l

f

l
i
ll \ nJ l l

r

l
F
l
t
01 = | ^ I
i u l

t

t l l
\./

.
l

t
h a = l

. .
f

t.
l

J t

l
l

v

t

lt 0 l l
[o,l

l

l

l

I

l )
|
l ' l

tl / r I l
\L)

) 3 =l l0ol i
0
t
l

.7
J t

^

l ^

|

l\.0,' l

''

l

t

: .
a

l

l r l

Ii=1",1
t v l
t l
\'0,/

l "I

\O,J

IOJ

11)
l
^

l

l

- O 5 =l ^ l

l'l

r

l r I

ro)
lol

i

0 t = l ^ l

r1)

l

l lo il

4
a

\-,/

/n\

t
t

r')
l+l

i-l

I L \l

l

t
t
l n l
l / l
I

I

l

/o\

t
t

l 0t l

r0)
t l

\^

r+
+
l . a

-

lLl
|
|

I
|

l1l

[+J

l

l

\^

"

JJ
?l \

r0)
'
l
| t I
|
|

i
|

ioi

\2)

b) UntersuchenSie mit llilfe destiblichen Reduktionsalgorithmus,ob der Zustandin Teilaufgabea)
verklemmungsbedrohtist. Falls nicht, gebenSie eine Reihenfolgean, in der alle Prozessebeendet werdenkönnen.

Atrgabe 7:
Gegeben
seieinunterSeitenadressierung
laufenderProzessP, derin der folgendenReihenfolgeauf
seineSeiten{A, ..., E} zugreift:
A, B, C, D, A, B, E, A, B, C, D, E
a) StellenSiedasVerhaltender folgendenVerdrängungsstrategien
dar für denFall; dassP zu Beginn keineKachelnim Arbeitsspeicher
zugeordnet
sind:
(i)
(ü)
(üi)
(iv)

FIFOmitn = 3 Aöeitsspeicherkacheln
FIFO mit n = 4 Arbeitsspeicherkacheln
LRU mit n = 4 Arbeitsspeicherkacheln
Working-Setmit Fenstergröße
k=4

GebenSiehierzuan, welcheSeitenvon P sichzujedemZeitpunktim Arbeitsspeicher
befinden,und
wa"mSeite-fehlt-Alarme
aufoeten.
WelcheBesonderheit
bzgl. derAnzahlderSeite-fehlt-Alarme
ergibtsichfür die FlFO-Strategie?
b) ZeigenSie,dassdie LRU-Verdrängungsstategie
für jedengegebenen
Seitenreferenzstring
eines
Prozesses
P die folgendeEigenschaft
aufoeist:
Mit wachsender
Anzablvon KacheladesArbeitsspeichers
gleichenAnnimmt(beiansonsten
fangsbedingungen)
die Seit+fehlt-Rate
desProzesses
P monotonab.
Fortsetzung
nächsteSeite!

66113
Einzelpnifungsnummer:

Herbst2000

Seite:5

von n € h,{ KachelnbezeichneS,G)(i e bb) die
Anleitung: Für eine Arbeitsspeichergröße
Menge der Seitendes ProzessesP, die sich nachdem i-ten Seitenzugriffvon P unter
Verwendungder l,RU-Strategieim Arbeitsspeicherbefinden.Der Einfachheithalfer sei lSfDl= n für alle i e \
-angenommen.
für jede Seites e S,(o)sei ti-e,(d1s)der Zeitstempelvon s gemäßLRU-strategie.
Zeigen Sie zunächst(durch vollst?indigeInduktion) flir alle i e n5 die folgendenInvarianten:
(D S,(")g S.(n+D
(ii) timei(d(s): fiqrs'('+1r13)
für alle s e S,(')
r)(s)ist minimal unter allen Seiten
(iii) Für diejenigeSeites mit {s} : Si("+r\Si(")
g t: timei(n+
auss.(o*').
dass(i) - (iii) zum Startzeitpunkti : 0 erfüllt sind.
Dabei sei vorausgesetzt,
Eigeruchaftder LRU-Strategie?
Warum folgt ausden obigenInvariantendie zu beweisende

Aufgabe 8:
.

ist unterstrichen.Die
Gegebensei eine RelationRoin der erstenNormalfoim. Der Prim?irschlüssel
firnktionalenAbh2ingigkeitensind durch Pfeile kenntlich gemacht.

I

v

,,l,

lrl

&(4Uon,^r, Bi, 82, 4,Cr,Cr)
-:
t

t

^

t

^

l

Man überfütre dieseNormalformin die zweiteund dritte und begrtindedie Schritte.

-6Herbst2000

Einzelpnifungsnummer:
66113

Seite:6

Thema Nr. 2
Sämfliche Teilaufgaben sind zu bearbeiten!
Aufgabe 1: CacheMemory
a) Was ist ein CacheMemory?
b) Erklären Sie folgendeEinheitenund erläuternSie derenZweck:
Befehls-Cache,
Daten-Cache,
Primär/Sekundär-Cache
c) Erklären Sieund gebenSie typischeZahlenwertean für: Kapazität,Blockgröße,Trefferverhältnis
(hit ratio), miss ratio (berücksichtigenSie nur prirnäre CacheMemories)
d) ErklärenSie: Start(Compulsory)Misses,CapacityMisses,ConflictMisses
e) GebenSie eine Formel für die mittlere hryiffszeit zum CacheMemory an!
f) welchen Einfluss hat das cache Memory auf den Durchsatzam Buch und am speicher?wovon
hängt der Durchsatzab?
g) Was geschiehtbei Schreiboperationen,
wenn der Prozessorein CacheMemory hat? (Unterscheiden sie, ob daszu ver?inderndewort bereitsim cache Memory stehtoder nicht, und berücksichtigenSie dasKonsistenzproblem!)
h) was spricht für die Adressierungdes cache Memorysin Programm-bzw. prozessadressen?

Aufgabe2: Ereignis und Prozesssysteme
a) Definieren Sie: Aktion, Ereignis, Zustandsänderung
b) Was heißt ,,atomar" in diesem Zusammenhangund auf welchen der oben genanntenBegriffe
trifft diesesPrädikat zu?
WaS heisst ,,zeitlich atomar" und ,,funktionell atomar"?
c) BeschreibenSie ein uninterpretiertesEreignissystemeinschließlichder Begriffe Vorrangrelation,
Vorbereich, Nachbereich, Speicher
d) Was ist ein interpretiertesEreignissystem?
e) Was ist ein uninterpretiertes/interpretiertes
Prozesssystem?
Was sind Prozesse(im Sinne dieses
Modells!), Initialisierungs-und Terminierungsereignisse?
f1 Was ist eine Ausftihrungsfolge eines Prozesssystems?

FortsetzungnächsteSeite!

Herbst2000

Eirzelprüfungsnumm
er: 66It3

Seite:7

g) Erklären Sie: konkurrenteProzesse,paralleleProzesse,sequentielle(serielle) Ausflihnrngsfolge,
linearesProzesssystem
h) Was ist ein determiniertes(man sagtauch:fun}tionales)Prozesssystem?
Wann ist es schwachdeterminiert?
i) Was besagtdie Bernstein-Bedingung?
j) Ein Prozesssystem
umfassedie Aufträge[1..6] und die lesJschreibbaren
Objekte[A..G]. Die
Vorrangrelationist
(1,2), (r,3), (1,4),(l,s), (1,6),(2,3),Q,s), (2,6),(3,5),(3,6),(4,6),(5,6)).
ZeichnenSie einenVorranggraphen-Die Prozesseverwendendie folgendenObjektezum Lesen
bzw. Schreiben:
Prozess

Lesen

Schreiben

1
2
3
4
5
6

A,B,C

A
C
E,F
D
G
G

A
A,C,E
D
E
A,B

Ist das Prozesssystem
determiniert?WelchePaarekann man in der Vorrangrelationweglassen,
ohnedassdie Determiniertheitzerstörtwird? Weshalbist die Reduktionder Vorransrelationvon
technischemInteresse?

-

Aufgabe 3: Routing in Rechnernetzen
a) Worin bestehtdie AufgabedesRoutingsin Rechnernetzen
und wodurch zeichnensich gute Lösungenaus (nennenSie mehrereKriterien!)
b) Erklären Sie: Routingtafel,Quellen-Senken-Baum
c) SkizzierenSie den Shortest-De1ay-Time-First-Algorithmus!
d) NennenSie Beispielefür nicht adaptivesRouting!
e) BeschreibenSie Flooding! Mit welchenergänzenden
Maßnahmenund unter welchenUmständen
ist Flooding ein sinnvollesRoutingverfahren?
f) Was ist Hot-Potato-Routing?
g) Wie unterscheidensich isoliertesadaptivesRoutingund gemeinsames
adaptivesRouting?
h) ErklärenSieOSPFund BGPI