<
>
Download

Prüfungstipps
Informatik

Technische Universität Wien - TU

Erstellungsjahr: 2011

Mario K. ©
5.30

0.67 Mb
sternsternsternsternstern_0.2
ID# 34515







Technische Universität Betriebssysteme


Prüfungsvorbereitung – Klausurtipps

1.Synchronisation


Allgemeine zu verwendende Funktionen


initS(Semaphor, init) Legt einen Semaphor mit dem angegebenen Namen Semaphor an und initialisiert ihn mit der Zahl init. Danach können die Funktonen P(Semaphor) und V(Semaphor) auf den Semaphor angewendet werden.


Zu verwendende Funktionen für die Schreibzugriffe:


write_mem1()     Mit dieser Funktion wirf in den Speicher 1 geschrieben.

write_mem2()     Mit dieser Funktion wirf in den Speicher 2 geschrieben.


Zu verwendende Funktionen für den Ausgabeprozess:


read_mem1()  Liest die Daten vom Speicher 1 und gibt sie aus.

read_mem2()  Liest die Daten vom Speicher 2 und gibt sie aus.


Initialisierungen


initS(input,1);

initS(read,0);

initS(out, 0);

initS(write, 0);




Prozess P1:

Prozess P2

P(write);

write_mem1();

P(input);

V(input);

V(read);

P(write);

write_mem2();

P(input);

V(input);

V(read);



Definition für Hilfsvariablen:

Prozess out:






2.Scheduling

Task

Arrival Time

Service Time

P1

0

5

P2

2

2

P3

3

6

P4

8

4

P5

10

2

Beim Round Robin Verfahren soll Zeitscheibenlänge  q=2 verwendet werden.

Scheduling nach dem RR-Verfahren

P1

à

P1

P1

P1

P1





P1

ß











P2



à



P2

P2

ß














P3




à




P3

P3


P3

P3





P3

P3

ß



P4









à




P4

P4



 


P4

P4

ß

P5











à




P5

P5

ß





            0     1      2     3     4      5     6     7      8     9     10   11    12   13   14    15   16   17   18    19   20

Scheduling nach dem SRT-Verfahren

P1

à

P1

P1



P1

P1

P1

ß













P2



à

P2

P2

ß
















P3




à





P3







P3

P3

P3

P3

P3

ß

P4









à

P4

P4

P4

P4

ß








P5











à



P5

P5

ß






            0     1      2     3     4      5     6     7      8     9     10   11    12   13   14    15   16   17   18    19   20


2.1 Real-Time Scheduling


Task

Ausführungszeit

Periodendauer

A

1

6

B

2

8

C

1

9

D

3

11

E

1

13

Scheduling nach dem RMS-Verfahren                      Erfolgreich:          nein

A

A






A






A








B


B

B






B

B











C




C







C










D





D

D


D




D








E





















     0     1      2     3     4      5     6     7      8     9     10   11    12   13   14    15   16   17   18    19   20

                                   Deadline von E

2.2 Verständnisfragen: Was versteht man unter dem Begriff Starvation?Nennen Sie ein Scheduling Verfahren, bei dem es zu Starvation kommen kann.

Ein Prozess wartet auf eine Ressorce, diese bekommt er aber nicht, weil sie von anderen Prozessen gebrauchtwird. Der Prozess kann nicht termieren und der Benutzer des Prozesses muss ewig auf das Resultat warten.Bsp. Shortest Remaining Time(SRT)

Prüfung 29.04.2010

3. Deadlock

P1

P2

  1: a=8;

  2: get(R1);

  3: get(R2);

  4: get(R1);

  5: b=3;

  6: a=b+2;

  7: c=b*a;

  8: b=c-a;

  9: free(R2);

10: a=b*3;

11: free(R1);

12: b=a;

13: free(R1);

14: return;

  1: a=54;

  2: get(R1);

  3: get(R2);

  4: get(R2);

  5: get(R1);

  6: c=a+b;

  7: free(R2);

  8: a=2*b*c;

  9: free(R1);

10: free(R2);

11: a=b*5;

12: free(R1);

13: b=5*d;

14: return;
































P2






















14























13























12























11























10























9























8























7























6























5




C



















4























3























2


B





















1

A














P1

R2


R2


R1


R1


1

2

3

4

5

6

7

8

9

10

11

12

13

14









R1














































R1














































R2














































R2
















 

A… Diedlockfreie Zone

B… Diedlock unvermeidbar

C… Unerreichbarer Bereich

Prüfung 29.04.2010

4. Betriebssysteme, Prozesse und Threads

1. Was versteht man unter einem Microkernel-Betriebssystem? Welche Services stellt ein Microkernel zur Verfügung? Welche Eigenschaften zeichnen ein solches Betriebssystem aus?

Microkernel: Implementiert nur Basisservices (Process Switching, Basic MM, Interrupts, Basic I/O, IPC) im Kernel. Rest wird durch Server-Prozesse realisiert, die im User-Mode laufen. nicht zentrale BS Services als Server Prozesse, Nachrichtenkommunikation zw.

BS/Prozessen, VT: sehr klein, flexibel und leicht erweiterbar Microkernel Services: Process Switching, Basic Memory Management, Interrupts und Hardware, Access (I/O), Nachrichtenaustausch und Nachrichtenkontrolle Eigenschaften: Einheitliche Interfaces, Flexibilität und Erweiterbarkeit, Portabilität, Unterstützung von Verteilung, Kernelgröße: 300KB, 140, Sys.

Calls 1 12KB(1.Generation), 7 Sys. Calls(2. Generation).

2. Was ist ein Mode Switch? Was ist ein Process Switch? Erklären die beiden Begriffe. Geben Sie an, wozu diese Switches benötigt werden und erläutern Sie, welcher Zusammenhang zwischen Mode Switch und Process Switch besteht.

Process Switch: Umschalten des aktiven Prozesses in den Running State, immer dann möglich, wenn das BS im Besitz der CPU ist:– Supervisor Call,expliziter Aufruf durch das Programm (I/O, …), – Trap, Auftreten eines Fehlers, – Interrupt, Ursache liegt außerhalb des Prozesses, Kontrolle geht an Interrupt Handler und BS Mode Swicht: ist Basis für Process Switch, nicht jeder Mode Switch bewirkt Process Switch, Mode Switch zwischen  User/Kernel Mode, – Interrupt, Trap oder Supervisor Call, Switch von User zu Kernel Mode; Starten der Abarbeitung von Interrupts; Beziehung: Mode Switch => Kernel Mode => ISR => Process switch

3. Nennen Sie die drei Kategorien von Ereignissen, mit deren Hilfe das Betriebssystem die Kontrolle über das Computersystem übernimmt. Geben Sie für jede der Kategorie ein Beispiel ein: Trap-Auftreten eines Fehlers, Supervisor Call-expliziter Aufruf durch das Programm(z.B. I/O), Interrupt-Ursache liegt außerhalb des Prozesses

4. Beschreiben Sie User-Level Threads und Kernel-Level Threads. Wodurch unterscheiden sich diese beiden Arten der Thread-Implementierung?

User-Level Threads: BS sieht keine Threads, Threads werden mittels eigener Library implementiert, Thread-Switch daher im User Mode, BS scheduled Prozesse _ Prozess scheduled Threads,

NT: Blockieren einzelner Threads nicht möglich, nur ganzer Prozesse,

VT: Kein Mode-Switch notwendig für Thread-Switch innerhalb eines Prozesses -schneller  Kernel-Level Threads: Thread-Management durch Kernel, Kernel stellt Thread-API zur Verfügung, Scheduling auf Thread-Basis,

VT: Threadweises blockieren möglich, gleichzeitiges scheduling mehrerer Threads eines Prozesses bei Mehrprozessorsystemen möglich, NT: Mode-Switch notwendig für Thread-Switch auch innerhalb eines Prozesses





Prüfung 25.01.2010

1.Synchronisation


init:


initS(BretterStapel, 1);

initS(SchiffALieferbereit, 0);

initS(SchiffBLieferbereit, 0);

initS(SchiffALadebereit, 1);

initS(SchiffBLadebereit, 1);

Prozess Kran A:

Prozess Kran B:


/* Schrauber */


bewege(UZS);

nimm();

bewege(GUZS);

P(SchiffALadebereit);

lege_ab();


 /* Bretter */


P(BretterStapel);

bewege(GUZS);

nimm();

bewege(UZS);

V(BretterStapel);

lege_ab();


/* lieferbereit */

V(SchiffALieferbereit);

/* Bretter */


P(BretterStapel);

bewege(UZS);

nimm();

bewege(GUZS);

V(BretterStapel);

P(SchiffBLadebereit);

lege_ab();


 /* Nägel */


bewege(GUZS);

nimm();

bewege(UZS);

lege_ab();


 /* lieferbereit */

V(SchiffBLieferbereit);



Prozess SchiffA:

Prozess SchiffB:


/* Warten bis lieferbereit dann liefern */

P(SchiffALieferbereit);

lieferung();

 /* zurück und ladebereit */

V(SchiffALadebereit);

/* Warten bis lieferbereit dann liefern */

P(SchiffBLieferbereit);

lieferung();

 /* zurück und ladebereit */

V(SchiffBLadebereit);

Prüfung 25.01.2010

2.Memory Management

2.1 Was ist der unterschied zwischen lokalem und globalem Page Replacement?

 Lokal  : Austausch innerhalb der Seiten des Prozesses

Global : Austauschstrategie wird auf alle Seiten des Hauptspeichers angewandt






PID

page

offset


PID

page

offset


PID

page

Offset


PID

page

offset


PID

page

offset





1

0

00a0


1

0

00a2


1

4

0002


2

3

fffe


2

4

0000





Phys. address


Phys. address


Phys. address







1          00a0


1             00a2


6             0002


2       fffe


3        0000
























PID

page

use


PID

Page

Use


PID

Page

Use


PID

Page

Use


PID

Page

Use


PID

Page

use

1

5

1

0

1

5

0


1

5

0


1

5

0


1

5

0


1

5

0

3

1

0

1

1

0

1


1

0

1


1

0

1


1

0

1


1

0

1

2

3

0

2

2

3

0


2

3

0


2

3

0


2

3

1


2

4

0

2

1

0

3

2

1

0


2

1

0


2

1

0


2

1

0


2

4

1

1

2

1

4

1

2

1


1

2

1


1

2

1


1

2

1


1

2

1

1

3

1

5

1

3

0


1

3

0


1

3

0


1

3

0


1

3

0

1

4

1

6

1

4

0


1

4

0


1

4

1


1

4

1


1

4

1

3

3

1

7

3

3

0


3

3

0


3

2

0


3

3

0


3

3

0
























Rep.

point


5




2




2




2




2




4

Prüfung 25.01.2010

3. Deadlock

Im folgenden Beispiel konkurrieren 5 Prozesse um 4 verschiedene Ressourcen. Zi, betrachteten Zeitpunkt sind 2 Ressourcen vom Typ1, und keine Ressource des Typ2,3 oder 4 verfügbar. Kann in dieser Situation ein Deadlock vorliegen? Führen sie Deadlock Detection Algorithmus um diese Frage zu beantworten.

                        

-Markiere P3 (belegt keine Ressourcen);

-Q1i (Anforderungen von P1) <=Wi (W=(2 0 0 0) ), daher markiere P1 und setze

W = W + (2 0 1 1) = (4 0 1 1);

-Q2i (Anforderungen von P2 )<=Wi (W=(4 0 1 1) ), daher markiere P2 und setze

W = W + (4 0 1 1)= (5 1 1 4);

Algorithmus terminiert  und liefert Deadlock von P4 und P5.


3.1 Ein Deadlock kann aufgehoben werden, in dem den Prozessen einige Ressourcen entzogen werden. Wie kann im vorangegangenen Beispiel durch das Entziehen genau einer allokierten Ressource sichergestellt werden, dass kein Deadlock mehr vorliegt?

Ressourcen Typ2 kann entzogen werden. Damit kann P4 markiert werden. Nachdem W gerechnet wird(daher wird W (5 1 2 4) sein), kann man P5 weiter markieren. Da Anforderungen von P5 sind auch kleiner als W.

Deadlock Prevention: Verhindern einer der 4 Deadlock Bedingungen.

Deadlock Avoidance: Ressourcenreservierungen, die zu Deadlock führen könnten,

                                   werden nicht gewährt. 


3.3 Beschreiben Sie eine Möglichkeit, um das Auftreten der notwendigen Deadlock Bedingung „circular wait“ auszuschließen (direct deadlock prevention). Die gleichzeitige Nutzung unterschiedlicher Ressourcen soll weiterhin möglich sein.

Verhinderung des circular wait umsetzun mittel Einführung einer Linearen Ordnung unter den Ressourcen. Ressourcen erden immer in der Reihenfolge angefordert, dass Ressourcen höherer Ordnung nur nach der Anforderung aller Ressourcen niedrigerer Ordnung angefordert werden können.

3.4 Welche weiteren Bedingungen sind für einen Deadlock notwendig? Erklären Sie deren Bedeutung.

1. Mutual Exclusion:  Ressourcen können nur von einem Prozess gleichzeitig verwendet werden.

2. Hold and Wait:  Prozess kann Ressourcen halten, während er auf andere Ressourcen wartet

3. No Preemption: zugewiesene Ressourcen werden den Prozessen nicht weggenommen

  4. Circular WaitGeschlossene Kette von Prozessen, von denen jeder Prozess mindestens eine Ressource, die von einem anderen Prozess benötigt wird, hält

Prüfung 25.01.2010

4. Input- Output

4.1 Nennen Sie die beiden wiedersprechenden Hauptziele, die bei der Realisierung eines I/O-Systems für ein General Purpose Betriebssystem verfolgt werden. Geben Sie für jedes der beiden Ziele an, welche Auswirkungen  es auf das Design des Betriebssystems hat.

– Flexibilität: für Einfachheit, geringere Fehlermöglichkeiten von I/O-Operationen,

Ersetzbarkeit, Austauschbarkeit von Geräten, einheitliche Schnittstellen erforderlich   (zB: Zugriffsfunktionen wie open, close, lock, unlock,…).

4.2 Beschreiben Sie die hierarchische Ebenestruktur, die bei der Realisierung von I/O-Funktionen Anwendung findet. Geben Sie Name und Funktion für jede Ebene.

Schichtungsebenen:

– Logical I/O: logische Bedienung des Gerätes (z.B.: open, close, read,…)

– Device I/O: Übersetzung von Operationen in Sequenz von I/O- und Kontroll-Kommandos; Pufferung

Scheduling and – control: Queuing, Verwaltung von I/O-Operationen, Interrupt-handling, Lesen des I/O-Status.

Puffer: Zwischenspeicher für Daten bei I/O-Transfer

• Zusammenfassung von low-level I/O-Operationen

• Pufferung im Kontext des Betriebssystems; Entkopplung I/O – Swapping

• Verwendung von mehreren Puffern für I/O-Aktivitäten zum Abfangen von Spitzenlastfällen,  Langzeit-Performance nie besser als Device Performance

• Kosten: Puffermanagement, Zuordnung: Puffer – Prozesse)

4.4 Nennen Sie zwei Verfahren, die beim Disk-Scheduling zur „Minimierung der Seek Time“ verwendet (nicht FIFO, LIFO und Prioritätsverfahren). Beschreiben Sie für jedes der von Ihnen genannten Verfahren kurz Funktionsweise, Vor- und Nachteile.

Seek Time TS: benötigte Zeit, um Disk-Arm zur gewünschten Spur zu bewegen.

-Auftrag mit der kürzesten Distanz zum aktuellen Auftrag wird ausgeführt

-minimiert mittlere Antwortzeit

-hoher Durchsatz

-unfair, „entfernt“ liegende Aufträge werden benachteiligt,

-Verhungern möglich: durch kontinuierliches Eintreffen neuer „naher“ Forderungen werden entfernte Forderungen blockiert.

-SCAN (Elevator Alg.):

-unidirektionale Bewegung des Kopfes, Abarbeitung aller Aufträge, die passiert werden

-Bewegung des Kopfes: bis zum Ende der Platte oder bis keine Aufträge in dieser Richtung mehr anstehen (LOOK),

-danach Umkehrung der Richtung und wiederum unidirektionale Bewegung usw.

-etwas schlechtere mittlere Antwortzeit als SSTF, da schlechtere Ausnutzung der Lokalität

-Benachteiligung der äußeren Sektoren -Aufträge, die in der aktuellen Bewegungsrichtung des Kopfes liegen, werden bevorteilt


| | | | |
Tausche dein Hausarbeiten