Betriebssysteme und hardwarenahe Programmierung bei …home.in.tum.de/~grasso/files/BuhPbdS _Zusammenfassung.pdf · Harvard Architektur bietet zwei getrennte ... Nennen Sie die Funktionseinheiten

Betriebssysteme und hardwarenahe Programmierung bei der SpieleentwicklungBetriebssysteme und hardwarenahe Programmierung bei der Spieleentwicklung

Von Neumann Architektur

VN-FlaschenhalsVerbindung zwischen Hauptspeicher und Prozessor wird zum Engpass.

Grundlegender Nachteil: Speicher für Programme und Daten ist identisch.

Probleme:

VN-Architektur vs. Havard-ArchitekturHarvard Architektur bietet zwei getrennte Blöcke: Programmspeicher und Datenspeicher, die über separate Busse and die CPU angebunden sind. Wenig eingesetzt, da:

• Für den Datentransport sind doppelt so viele Leitungen notwendig (Hardware Mehraufwand)

• Es muss eine Möglichkeit geschaffen werden, neu übersetzte Programme aus dem Daten- in den Programmspeicher zu übertragen

PipeliningPipelining dient dazu,die gesamte Ausführungszeit bei der Abarbeitung von Befehlen zu reduzieren. Um die Effektivität einer Pipeline zu bewerten wird ein SpeedUp ermittelt.

SpeedUp = Zeit ohne PipelineZeit mit Pipeline

SpeedUp = b ⋅ t

t + (b −1) ⋅tn

=n ⋅ b

n+(b −1)

n → Anzahl der Phasen in der Pipelinet → Bearbeitungszeit für einen Befehl(t/n) → Ausführungszeit einer Phaseb → Anzahl der Befehle


Sichtenmodell

Nennen Sie die Funktionseinheiten der Von-Neumann Architektur und beschreiben Sie kurz deren jeweilige Aufgabe.

• Leitwerk/Steuerwerk (control unit) Holt und interpretiert die Maschinenbefehle Erzeugt Steuerkommandos für alle anderen Komponenten

• Rechenwerk (ALU: Arithmetical Logical Unit) Führt alle Befehle aus, bis auf Ein/Ausgabe- und

• Speicher (storage memory) Speichert Programme und Daten

• Ein-/Ausgabewerk (I/O unit) Steuert Ein/Ausgabe-Geräte, inkl. Periphere Speicher

Das „klassische“ Operationsprinzip der von-Neumann Architektur sieht ein Zwei-Phasen-Konzept vor. • Nennen Sie beide Phasen • Wie wird der Inhalt einer Speicherzelle pro Phase jeweils interpretiert bzw.verarbeitet(BitteeineklareZuordnungzudenPhasenherstellen)?

Die interne Befehlsausführung des heutigen Operationsprinzips ist nicht mehr streng sequentiell. • Welches Ziel soll dadurch erreicht werden (bitte genau) • Durch welches Prinzip soll dieses Ziel umgesetzt werden?

• Interpretations-Phase: Speicherzelle wird als Befehl interpretiert • Ausführungs-Phase: Speicherzelle wird als Datenwert verarbeitet • Ziel: Erhöhung des Grenzdurchsatzes • Prinzip: Pipelining und/oder Superskalarprinzip

Hardware-Software-Schnittstelle

Beschreiben Sie jeweils einen Vor- und Nachteil von RISC (Reduced Instruction Set Computer) und CISC (Complex Instruction Set Computer) und einen sich daraus ergebenden Einsatzbereich.

• CISC - Komfortabel und relativ mächtig Vorteile:

einfache Programmierbarkeit, geringer Speicherbedarf Nachteile:

komplexe (langsame) Implementierung insbesondere Dekodierung, evtl. viele Funktionen ungenutzt.

Einsatzbereich: x86, Desktoprechner

• RISC - Minimalistisch auf das absolut Notwendige beschränkt Vorteile:

einfache, effiziente, schnelle Implementierung Schnelle Interrupt-Behandlung

Nachteile: schwierigere Programmierbarkeit

Einsatzbereich: ARM/Embedded aufgrund geringer Speicherbedarf

Nennen Sie die fünf Punkte, welche von der Instruction Set Architecture (ISA) festgelegt werden.

• Datenformate und Datentypen • Adressierung • Befehle • Befehlsformat • Ausfuehrungsmodi,privilegierte Funktionen,Unterbrechungen


Prozessoren & weitere Hardware

Nennen Sie die Klassifikationen von Flynn und geben Sie jeweils ein Beispiel für einen Prozessor. Abkürzungen bitte ausschreiben.

• SISD: Single Instruction Stream Single Data Stream Einprozessor (Uniprocessor) ggf. mit ILP

• SIMD: Single Instruction Stream Multiple Data Stream Vektorrechner, Multimedia Erweiterungen, GPUs

• MISD: Multiple Instruction Stream Single Data Stream nie gebaut

• MIMD: Multiple Instruction Stream Multiple Data Stream Multiprozessoren für TLP

Wie kann eine Leistungssteigerung bei der Verarbeitung von Prozessorbefehlen erreicht werden ohne den Takt zu erhöhen?

Durch Parallelität.

Welches Prinzip steckt hinter dem Einsatz von Caches? Beschreiben Sie die Grundidee hinter dem Prinzip.

Lokalitätsprinzip. Die Idee ist dass beim Ablaufen eines Programms der Zugri# auf nahe beieinander liegenden Daten sehr wahrscheinlich ist.

Angenommen ein Prozessor besitzt 15 Phasen (n) in der Pipeline und es sollen 9.986 Befehle (b) abgearbeitet werden. Bestimmen Sie den Speedup auf zwei Nachkommastellen genau:

SpeedUp = n ⋅ b

n+(b −1)

SpeedUp = 15 ⋅ 9986

15+(9986 −1)= 14,979

NennenSiediebeidenArtenvonParallelität,diezurApplikations-Parallelität gehören. Was wird bei den jeweiligen Arten gleichzeitig verarbeitet? Nennen Sie die vier Arten von Parallelität die zur Rechner-Parallelität gehören. Nennen Sie zu jeder Art die jeweilige Ausprägung im Recher.

• Applikations-Parallelität Data-LevelParallelism(DLP):VieleDatenelementegleichzeitigverarbeiten Task-Level Parallelism (TLP): Viele Aufgaben unabhängig gleichzeitig verarbeiten

• Rechner-Parallelität Instruction-Level Parallelism (ILP): DLP maschinennah sowie spekulative Ausführung Vector Architectures & Graphic Processor Units (GPU): DLP mit jeweils einer Instruktion Tread-LevelParalellism(TrLP):DLPundTLPaufenggekoppelter Hardware nebst Interaktion Request-Level Parallelism (RLP): Parallelisierung großer entkoppelter Aufgaben (OS & Programmierer)


Prozesse

1. Nennen Sie einen Vorteil bei der Verwendung von Threads gegenüber von Prozessen bezüglich des Austauschs von Daten?2. Nennen Sie eine Gefahr, die sich bei der Verwendung von Threads ergeben kann, und nennen Sie einen Mechanismus, um diese zu behandeln?

Leichtgewichtig. Einfacher Austausch von Daten. Gefahren sind Wettlaufsituationen und Deadlocks.Lösung sind Atomare Operationen, Sperrvariablen oder kritische Abschnitte (atomic, spinlock, mutex).

Beschreiben Sie den Unterschied zwischen Benannten Pipes und einer regulären Datei und erläutern Sie den Vorteil für die Prozesskommunikation, welcher unter Verwendung regulärer Dateien nur schwer realisierbar wäre. Ein wesentlicher Unterschied besteht darin, dass eine FIFO-Datei kein „Ende“ hat. Liest man ein Zeichen aus einer leeren, regulären Datei, erhält man den Dateiende-Marker EOF. Bei einer FIFO-Datei wird der Prozess so lange angehalten, bis ein Zeichen in die FIFO-Datei geschrieben wurde. Auch beim Schreiben in die FIFO-Datei wird der Prozess blockiert, bis ein anderer Prozess die FIFO-Datei zum Lesen öffnet. Dadurch lassen sich zwei Prozesse mit Hilfe von FIFO-Dateien synchronisieren, was mit regulären Dateien nur schwer möglich ist.

Worin besteht die Hauptaufgabe eines Prozess-Schedulers? Beschreiben Sie in diesem Zusammenhang kurz die Round Robin-Strategie.

Ein Prozess-Scheduler regelt die zeitliche Ausführung mehrerer Prozesse in Betriebssystemen. Round Robin, Zeitscheibenverfahren: Einem Prozess wird die CPU für eine bestimmte (kurze) Zeitspanne zugeteilt. Danach wird der Prozess wieder hinten in die Warteschlange eingereiht.


Cache-Lines// A // Bstruct DATA struct DATA{ { int a; int a; int b; int b; int c; ]} int d;}

DATA * pMyData;

for(long i =0;i<10*1024*1024;i++){ pMyData[i].a = pMyData[i].b;}

char * p; p = new char[SIZE]; long x = 0; long y = 0;// A // B for(;x<sRowSize;x++) for(;y<nbRows;y++) for(;y<nbRows;y++) for(;x<sRowSize;x++) { { p[x+y*sRowSize]++; p[x+y*sRowSize]++;} }

Programm B läuft 4-mal schneller als Programm A. Die Cache Line spielt hier eine wichtige Rolle. In C/C++, mit row-major memory storage, ist der Zugriff der Daten in kontinuierlichen Reihen vier-mal schneller als der spaltenweise Zugriff.

// A // Bstruct DATA struct DATA { { char a; char a; int b; int b; char c; char c; }; };DATA * pMyData;

long b = 36*1024*1024;

for(long i=0;i<b;i++) { pMyData[i].a++; }

Programm D ist ca. 60% schneller als Programm C. Aufgrund des Compilers sind die Daten im Programm D signifikant besser angeordnet, was schließlich den Geschwindigkeitsunterschied ausmacht.


Pointerarithmetikint* x;→ x ist ein Zeiger auf einen Integer.

int* x[];→ x ist ein Array von von int-Zeigern.

int (*x)[];→ x ist ein Zeiger auf ein Array von Integern.

//Beispiel 1#include<stdio.h> void increment(int *ptr){++ *ptr;} int main(){ int a[]={5,10},i=0; increment(a); // a={6,10}increment(&i); // i = 1increment(&a[i]); // a={6,11}increment(a+i); // a={6,12}printf("\nErgebnis:i=%d\n",i); // i = 1printf("a[0]=%d\n", a[0]); // a[0] = 6printf("a[1]=%d\n",a[1]); // a[1] = 12return 0 ; }

//Beispiel 2#include<stdio.h> #include<stdlib.h> int main(){ int horst; int heiner; int *varEins; struct two_ints{ int a; int b; }; struct two_ints *t; t=(struct two_ints*) malloc(sizeof(struct two_ints)); t->a=1; // a = 1t->b=3; // b = 3varEins=&(t->a); // varEins = *ahorst=(*varEins)++; // horst = 1, a = 2heiner=*varEins; // heiner = 2printf("horst%i\n",horst); // horst 1printf("heiner%i\n",heiner); // heiner 2}

Der ++-Operator ist in diesem Fallein Postfix-Operator.


Vektorarchitekturen

Aufgaben & Funktionen eines Betriebssystems... die Programme eines digitalen Rechensystems, die zusammen mit den Eigenschaften der Rechenanlage die Basis der möglichen Betriebsarten des digitalen Rechensystems bilden und die insbesondere die Abwicklung von Programmen steuern und überwachen.

... eine Software-Schicht, die alle Teile des Systems verwaltet und dem Benutzer eine Schnittstelle oder eine virtuelle Maschine anbietet, die einfacher zu verstehen und zu programmieren ist (als die nackte Hardware).

... ein Programm, das als Vermittler zwischen Rechnernutzer und Rechner-Hardware fungiert. Sein Zweck ist, eine Umgebung bereitzustellen, in der ein Benutzer bequem und effizient Programme ausführen kann.

Betriebssystemarchitekturen Monolithisch Die Struktur dieser Systeme besteht darin, dass sie keine oder nur eine unklare Struktur haben. Meist handelt es sich um evolutionär gewachsene Betriebssysteme, bei denen es anfänglich unwichtig war, einzelne Teilfunktionen klar mit Schnittstellen voneinander abzugrenzen. Beispiel dafür sind MS-DOS und Linux.

Geschichtet Bei dieser Strukturierungsform sind die Betriebssystemfunktionen in viele Teilfunktionen gegliedert, die hierarchisch auf mehrere Schichten verteilt sind. Die Festlegung der Schichtenstruktur ist vom einzelnen Betriebssystem abhängig, eine Standardstruktur gibt es nicht. Funktionen einer höheren Schicht bauen strikt nur auf Funktionen einer tieferen Schicht auf. Jede Schicht realisiert eine bestimmte Funktionsgruppe. Systemaufrufe passieren nach unten alle Schichten, bis sie auf die Hardware einwirken. Eingabedaten durchlaufen umgekehrt alle Schichten von unten bis oben zur Benutzerapplikation.

Mikrokern Nur die allerzentralsten Funktionen sind in einem Kernteil zusammengefasst, alle übrigen Funktionen sind als Serverdienste separat realisiert (z.B. Dateidienste). Der Mikrokern enthält lediglich die vier Basisdienste Nachrichtenübermittlung (message passing), Speicherverwaltung (virtual memory), Prozessorverwaltung (scheduling) und Gerätetreiber (device drivers). Diese sind dabei in ihrer einfachsten Form realisiert. Weiter gehende Funktionen sind in den Serverprozessen enthalten, die im Benutzermodus ausgeführt werden. Dadurch werden die komplexeren Teile in klar abgegrenzte Teile aufgesplittet, wovon man sich eine Reduktion der Komplexität verspricht. Da zudem ein Großteil des Betriebssystemcodes auf die Benutzerebene (Benutzermodus) verschoben wird, sind die empfindlichsten Teile des Systemcodes gegen fehlerhafte Manipulationen aus dieser Richtung geschützt (Kernmodus). Ebenso ist es nur dem eigentlichen Kern erlaubt, auf die Hardware zuzugreifen.

Hybrid Ein Hybridkernel ist ein Kompromiss zwischen einem Mikrokernel und einem monolithischen Kernel. Aus Geschwindigkeitsgründen werden einige Teile von monolithischen Kerneln in den Kern integriert.


Scheduling - Round RobinRound Robin, Zeitscheibenverfahren: Einem Prozess wird die CPU für eine bestimmte (kurze) Zeitspanne zugeteilt. Danach wird der Prozess wieder hinten in die Warteschlange eingereiht.

Quantum q [Zeiteinheiten]Prozesse P1, P2, …Initialpriorität I [int-Vektor]Ankunftszeiten a [int-Vektor]Bedienzeiten b [Zeiteinheiten-Vektor]

Beispiel:q = 2drei Prozesse P1,P2,P3

I = (10,9,14)a = (0,2,0)b = (6,6,8)

Im rechnenden Zustand wird die Priorität des Prozesses je nach 1 Zeiteinheit um 2 erniedrigt.

Im rechenwilligen Zustand wird die Priorität des Prozesses alle 2 Zeiteinheiten um 1 erhöht.

Prioritäten reichen von 0 bis 20, wobei 0 die niedrigste und 20 die höchste Prioritäten darstellen.

In jedem Zeitquantum wird der Prozess mit der höchsten Priorität ausgewählt.

mittlere Wartezeit & mittlere Verweilzeit

n Aufträge (=Prozessanzahl)ci Abgangszeit (fertig)ai Ankunftszeit (●)bi Bedienzeit(▬)

vi = ci – ai Verweilzeitwi = vi – bi Wartezeit

V =1n∑i=1

n

v i mittlere Verweilzeit

W =1n∑i=1

n

wi mittlere Wartezeit


Dispatcher & SchedulerFür die Realisierung von Prozessen auf realen Prozessoren sind Verwaltungsoperationen auszuführen, die die Zustandsübergänge zwischen real rechnend und rechenwillig der Prozesse durchführen. Die entsprechenden Operationen (Programme), die vom Dispatcher definiert werden, sind das Binden eines Prozesses an einen Prozessor und schliesslich das Lösen der Bindung.

Der Scheduler wählt gemäß seiner zugrunde liegenden Schedulingstrategie die Prozesse aus, die als nächstes den Rechenkern zugewiesen bekommen. Er bestimmt somit die Ausführungsfolge der Prozesse.

Der Dispatcher ist für den Prozesswechsel zuständig. Er entzieht also dem rechnenden Prozess den Rechenkern und weist den Rechenkern dem nächsten Prozess zu (der vom Scheduler bestimmt wurde). Scheduler und Dispatcher arbeiten also Hand in Hand.

Prozesszustände Es sei angenommen, ein Prozess kann die folgenden vier Zustände annehmen:

• rechenwillig • rechnend • wartend • ausgelagert

Die Übergänge zwischen diesen Zuständen werden vom Dispatcher realisiert. Dieser koordiniert die Zuweisung des Rechenkerns an den Prozess, so dass dieser rechnen kann. Skizzieren Sie diese Zustände in einem Graphen und benennen Sie die Zustandsübergänge sinnvoll!

add,retire: Prozessentstehung und -terminierung assign, resign: Zuweisung bzw. Entzug des Rechenkerns durch Scheduler block,ready: Prozess wegen I/O Operation, sonstigen Synchronisationsoperation anhalten bzw. fortsetzen swap in,swap out: Ein- und Auslagerung des Prozesses in Arbeitsspeicher

Prozesskontrollblock Ein Speicherbereich, der alle wichtigen Informationen über den Prozess enthält, u.a.:

• Eindeutiger Name, ProzessID • Name des Benutzers, dem der Prozess zugeordnet ist • Momentaner Prozesszustand (wartend, rechnend, rechenwillig, ...)

◦ Falls der Prozess rechnend ist, Angabe der zugeordneten CPU ◦ Falls der Prozess wartend ist, eine Spezifikation des Ereignisses, auf das der Prozess wartet (z.B.

Adresse eines Semaphors) • Ablaufpriorität des Prozesses • Inhalte der programmierbaren Register (die Anzahl ist abhängig von der jeweiligen CPU-Architektur), z.B.

Stack-Pointer • Inhalte der Register, in denen die Anfangsadresse und Länge der prozessspezifischen

Speicherabbildungstabellen enthalten sind (virtuelle Adressierung) • Programmstatuswort (PSW)


Welche Bedeutung hat der PCB für das Scheduling? Welche für das Dispatching?Der Scheduler wählt gemäß seiner zugrundeliegenden Schedulingstrategie die Prozesse aus, die als nächstes den Rechenkern zugewiesen bekommen. Die Informationen (z.B. Priorität) zur Umsetzung dieser Strategie stehen im PCB. Der Dispatcher ist für den Prozesswechsel zuständig. Er entzieht also dem rechnenden Prozess den Rechenkern und weist den Rechenkern dem nächsten Prozess zu. Alle Informationen, die dafür notwendig sind und die Assoziierung des neuen Prozesskontexts, stehen im PCB des jeweiligen Prozesses. Da dem Rechenkern durch seine Prozessbelegung ein Prozesskontext zugewiesen ist, wird dieser Schritt auch Kontextwechsel genannt.

Welche weiteren Informationen (außer dem PCB) werden für einen Prozesswechsel benötigt?Desweiteren wird ein Warteraum für Prozesse benötigt, der die Prozesse hält, die sich im Zustand rechenbereit befinden. Die Operationen auf diesem Warteraum sollen wechselseitig ausgeschlossen ausgeführt werden.

Worin liegt der Unterschied zwischen dem Dispatchen von Prozessen und dem Dispatchen von Threads? Gehen Sie dabei insbesondere auf Benutzer-Level und Kernel-Threads ein!Prozesse und Kernel-Threads werden vom Betriebssystem verwaltet (also auch dispatched), Benutzer-Level Threads vom Elternprozess ohne Kenntnis des Betriebssystems. Das Dispatchen eines Prozesses hat als einziges einen Kontextwechsel zur Folge, da nur hier der Prozesskontext gewechselt wird.

Grenzen Sie die Aufgabe des Dispatchers von der des Schedulers ab! Wie gestaltet sich die Zusammenarbeit dieser beiden Komponenten?Der Scheduler wählt gemäß seiner zugrundeliegenden Schedulingstrategie die Prozesse aus, die als nächstes den Rechenkern zugewiesen bekommen. Er bestimmt somit die Ausführungsreihenfolge der Prozesse. Der Dispatcher ist für den Prozesswechsel zuständig. Er entzieht also dem rechnenden Prozess den Rechenkern und weist den Rechenkern dem nächsten Prozess zu (der vom Scheduler bestimmt wurde). Scheduler und Dispatcher arbeiten also Hand in Hand.

Beschreiben Sie den Ablauf eines Kontextwechsels bzw. des Dispatchings eines Prozesses!1. Maskieren von Interrupts 2. Bestimmung des nächsten zu ladenden Prozesses (BS-spezifisch) 3. Aufruf der Operation zum Kontextwechsel 4. Sichern des PCB des alten Prozesses 5. Laden des PCB des neuen Prozesses 6. Freigabe von Interrupts

Welche Rolle spielt die Größe des Prozesskontrollblocks beim Kontextwechsel? Betrachten Sie diesem Aspekt im Hinblick auf Häufigkeit und Effizienz multipler Kontextwechsel.Je größer der PCB, desto länger dauert der Kontextwechsel.Je häufiger Kontextwechsel durchgeführt werden und je größer ein PCB ist, desto weniger effizient ist ein solcher Ansatz.


Scheduling Stategiendrei Prozesse P1,P2,P3

a = (0,5,2)b = (7,3,4)Ein Kontextwechsel benötigt eine Zeiteinheit.

1. [FCFS] First Come First Served2. [SRPT] Shortest Remaining Processing Time3. Round-Robin mit q = 14. Round-Robin mit q = 2


Was fällt Ihnen beim Vergleich der Round-Robin-Strategien auf? Welche Vorteile haben kurze bzw. lange Zeitquanten in Bezug auf Effizienz und Reaktionszeiten für I/O-Aufträge?Kurze Quanten: häufiger Kontextwechsel→ viel Zeitvergeudung Lange Quanten: seltener Kontextwechsel→ schlechte Fairness; schlechte Reaktionszeit, aber effiziente Zeitnutzung

Prozesse und Threads Prozesse und Kernel-Level-Threads werden vom Betriebssystem verwaltet (also auch dispatched). User-Level-Threads werden vom Elternprozess ohne Kenntnis des Betriebssystems verwaltet. Das Dispatchen eines Prozesses hat als einziges einen Kontextwechsel zur Folge, da nur hier der Prozesskontext gewechselt wird.

Prozesse und Threads BeispielGegeben seien zwei Prozesse mit der gegebenen Anzahl an Kernel-Level-Threads Ki und User-Level-Threads Uj.

Jeder der Prozesse selbst benötigt Rechenzeit, ebenso jeder einzelne Thread. Ein Prozess terminiert erst, wenn alle seine Threads terminiert sind.

Der Kernel-Scheduler arbeitet nach dem nicht-unterbrechbaren Round-Robin-Verfahren (Zeitscheiben), wobei eine Zeitscheibe fünf Einheiten beträgt.(Aktivitäten des Schedulers oder Dispatchers nicht mitgerechnet).

Der Kernel-Scheduler behandelt alle von ihm verwalteten Ausführungsstränge gleich. Sie werden in der Reihenfolge ihrer Startzeit abgearbeitet.

Die Verwaltung der Ausführungsstränge durch den Kernel benötigt ebenfalls Rechenzeit. Jedes mal, wenn der Kernel-Scheduler aktiv wird, benötigt er eine Zeiteinheit. Muss zusätzlich ein Prozess-Kontextwechsel durchgeführt werden, kostet das eine zweite Zeiteinheit.

Der User-Level-Scheduler läuft unabhängig vom Kernel-Scheduler. Gehen Sie davon aus, dass jeder Ausführungsstrang nach zwei Zeiteinheiten oder beim Terminieren die Kontrolle an den User-Level-Scheduler abgibt, der dann den nächsten auswählt. Wie beim Kernel-Scheduler werden die Ausführungsstränge in der Reihenfolge ihrer Ankunft bearbeitet.

Weiterhin startet der User-Level-Scheduler neue Ausführungsstränge sofort : Sobald ein neuer Ausführungsstrang hinzukommt, gibt der laufende den Rechenkern ab und der neue bekommt ihn zugewiesen. Als nächstes ist dann der Strang an der Reihe, der regulär nach dem neuen Strang folgt.

Der Aufwand für das User-Level-Scheduling ist vernachlässigbar klein, kostet also in dieser Aufgabe keine Zeiteinheiten. Tragen Sie im nachfolgenden Gantt-Diagramm ein, welcher Prozess bzw. Thread zu welcher Zeit die CPU erhält. Markieren Sie rechenwillige Prozesse bzw. Threads mit "-" und rechnende Prozesse bzw. Threads mit "X" in der jeweiligen Spalte.


Prozesse und Threads Beispiel → Lösung

Startzeit der Prozesse.

Kernel-Scheduler Zeitscheibe dauert 5 Zeiteinheiten.

Wenn der Kernel-Scheduler aktiv wird, benötigt er eine Zeiteinheit.Muss zusätzlich ein Prozess-Kontextwechsel durchgeführt werden, kostet das eine weitere Zeiteinheit.

Jeder Ausführungsstrang gibt nach zwei Zeiteinheiten oder beim Terminieren die Kontrolle an den User-Level-Scheduler ab.

Weiterhin startet der User-Level-Scheduler neue Ausführungsstränge sofort.

User-Level-Scheduling kostet in dieser Aufgabe keine Zeiteinheit.

Prozess terminiert.

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

P1 X X X X X - - - - - - - - - - - - - X X X X X - - -

P1,K1 - - - - - - - - - - - X X X

P1,K2 - - - - - -

P2 - - - - - X X - - X - - - - - - - - - - - - - -

P2,U1 X X - - - - - - - - - - - - - - -

P2,U2 - - - - - - - - - - - - - X

Sched. / Disp.

X X X X X X X

26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

P1 - - - - - - - - - X X X

P1,K1

P1,K2 - - - - - - X X

P2 - X X - - - - - - - - - - - - - - X X - - X

P2,U1 - - - X - - - - - - - - - - X - - - - - X

P2,U2 X - - - - - - - - - - - - - - X X

Sched. / Disp.

X X X X X X


Deadlock-Vermeidung

Sind folgende Systemzustände sicher (safe) (safe heisst: das System ist nicht verklemmt (deadlocked) und es gibt eine Ausführungsreihenfolge der Prozesse in der kein Deadlock auftritt auch wenn alle Prozesse alle noch anzufordernden Ressourcen anfordern)? Geben Sie jeweils in knappen Stichpunkten die Ausführung des Bankieralgorithmus an! Geben Sie ggf. die Ausführungsreihenfolge der Prozesse an!

1. m =1 n =4 c1 =(2,2,4,8)T r1 =(10,8,4,6)T e =20 a =4

m = number of resources Anzahl Ressoucenn = number of processes Anzahl Prozessec = current resource aktuelle Ressourcer = requested resources angefragte Ressourcene = entive resourcesa = available resources verfügbare Ressourcen

c1 = ( 2 2 4 8 ) r1 = ( 10 8 4 6 ) a = 4 p3 bekommt 4 Einheiten.

c2 = ( 2 2 8 8 ) r2 = ( 10 8 0 6 ) a = 0 p3 kann nun fertig arbeiten und terminiert, dabei werden seine Ressourcen wieder freigegeben.

c3 = ( 2 2 0 8 ) r3 = ( 10 8 0 6 ) a = 8 p2 bekommt 8 Einheiten. Alternativ wäre aber auch denkbar zuerst p4 abzuarbeiten. Laut Tanenbaum ist es unwichtig, welcher der möglichen Prozesse zuerst ausgeführt wird.





c7 = ( 0 0 0 14 ) r7 = ( 0 0 0 0 ) a = 6 p4 terminiert.

c8 = ( 0 0 0 0 ) r8 = ( 0 0 0 0 ) a = 20 Eine mögliche Ausführungsreihenfolge ist somit: (p3 → p2 → p1 → p4)

2. m =1 n =4 c1 =(2,4,4,8)T r1 =(10,6,6,12)T e =20 a = 2

Es liegt eine Verklemmung vor, da kein Prozess mit einer Ressourcenanforderung von maximal 2 Einheiten existiert.

Somit kann kein Prozess fertig ausgeführt werden und ein Weiterarbeiten des Systems ist nicht möglich.


3. m =4 n=5 c1 = (6 0 2 20 2 0 02 2 2 02 2 0 20 0 0 0

) r 1 =(2 2 0 00 2 2 46 2 0 00 0 2 04 2 2 0

)e = (12 6 8 4 ) a = (2 0 4 0)

-----------------------------------------------------------------------------------------------------------------------------

c1 =(6 0 2 20 2 0 02 2 2 02 2 0 20 0 0 0

) r 1 = (2 2 0 00 2 2 46 2 0 00 0 2 04 2 2 0

) a = (2 0 4 0)

p4 bekommt (0 0 2 0)

c2 =(6 0 2 20 2 0 02 2 2 02 2 2 20 0 0 0

) r 2 = (2 2 0 00 2 2 46 2 0 00 0 0 04 2 2 0

) a = (2 0 2 0 )

p4 kann nun fertig arbeiten und terminiert, dabei werden seine Ressourcen wieder freigegeben.

c3 =(6 0 2 20 2 0 02 2 2 00 0 0 00 0 0 0

) r 3 =(2 2 0 00 2 2 46 2 0 00 0 0 04 2 2 0

) a = (4 2 4 2)


c4 =(6 0 2 20 2 0 02 2 2 00 0 0 04 2 2 0

) r 4 =(2 2 0 00 2 2 46 2 0 00 0 0 00 0 0 0

) a = (0 0 2 2 )


c5 =(6 0 2 20 2 0 02 2 2 00 0 0 00 0 0 0

) r 5 = (2 2 0 00 2 2 46 2 0 00 0 0 00 0 0 0

) a = (4 2 4 2)



c6 =(8 2 2 20 2 0 02 2 2 00 0 0 00 0 0 0

) r 6 =(0 0 0 00 2 2 46 2 0 00 0 0 00 0 0 0

) a = (2 0 4 2)


c7 =(0 0 0 00 2 0 02 2 2 00 0 0 00 0 0 0

) r 7 = (0 0 0 00 2 2 46 2 0 00 0 0 00 0 0 0

) a = (10 2 6 4)


c8 = (0 0 0 00 4 2 42 2 2 00 0 0 00 0 0 0

) r 8 =(0 0 0 00 0 0 06 2 0 00 0 0 00 0 0 0

) a = (10 0 4 0)


c9 =(0 0 0 00 0 0 02 2 2 00 0 0 00 0 0 0

) r 9 = (0 0 0 00 0 0 06 2 0 00 0 0 00 0 0 0

) a = (10 4 6 4 )

p3 bekommt (6 2 0 0 )

c10 = (0 0 0 00 0 0 08 4 2 00 0 0 00 0 0 0

) r 10 = (0 0 0 00 0 0 00 0 0 00 0 0 00 0 0 0

) a = (4 2 6 4)


c11 = (0 0 0 00 0 0 00 0 0 00 0 0 00 0 0 0

) r 11 = (0 0 0 00 0 0 00 0 0 00 0 0 00 0 0 0

) a = (12 6 8 4 )

Eine mögliche Ausführungsreihenfolge ist somit: (p4 → p5 → p1 → p2 → p3)


Adressrechnung

Die Breite einer virtuellen Adresse betrage 12 Bit. Als physikalischer Speicher stehen 256 Byte zur Verfügung.

Zählen Sie alle möglichen Seitengrößen auf, bei denen der physikalische Speicher komplett genutzt wird.

Lösung:Es sind nur Seitengrößen sinnvoll, die Teiler der Größe des vorhandenen physikalischen Speichers darstellen. Ansonsten würden nicht alle Teile abgedeckt oder es käme zu Überlagerungen. Also 1,2,4,8,16,32,64,128.256.

Nehmen Sie im Weiteren eine Seitengröße von 32Byte an. Wie viel Speicher (Hintergrundspeicher, physikalischer Speicher, evtl. Puffer) müssen für den Betrieb mindestens zur Verfügung stehen?

Lösung:Bei 12bit-breiter virtueller Adresse werden vom System 212 = 4096 Byte zur Verfügung gestellt. Für das Ein- und Auslagern ist zusätzlich ein Puffer in der Größe einer Seite notwendig, da sonst das Austauschen der Daten nicht möglich ist. Das System muss also insgesamt mindestens über 4096+32 = 4128 Byte Speicher verfügen. Dabei werden dann keine Daten redundant gehalten, sprich die Daten befinden sich dann entweder im Hintergrundspeicher oder im Hauptspeicher. Üblicherweise befindet sich aber der komplette virtuelle Speicher schon auf dem Hintergrundspeicher (also 4096 Byte). Es werden dann die benötigten Teile zusätzlich in den Hauptspeicher (256 Byte) geladen. Dann wird kein weiterer Puffer benötigt. Insgesamt aber dann 4096 + 256 = 4352 Byte Speicher.

Wie viele Bits der virtuellen Adresse entfallen auf die Seitennummer und wie viele auf den Offset?

Lösung:Bei einer Seitengröße von 32 Byte sind für die Adressierung innerhalb der Seite (Offset) 5 Bit notwendig. Von den 12 Bit der virtuellen Adresse bleiben also 7 Bit für die Seitennummer. Es können also 27 = 128 Seiten verwaltet werden.

Berechnen Sie die Anzahl der notwendigen Einträge in einer Seiten-Kachel-Tabelle für alle neun möglichen Kombinationen von:

• Länge der virtuellen Adresse (und damit Größe des virtuellen Speicherbereichs): 16, 32, 64 Bit • Seitengröße: 4 KB, 8 KB, 16 KB

Lösung:Länge der virtuellen Adresse

Seitengröße Offsetbreite 16 Bit 32 Bit 64 Bit

4kB = 4096Byte = 212 Byte 12 216-12 = 24 232-12 = 220 264-12 = 252

8kB = 8192Byte = 213 Byte 13 216-13 = 23 232-13 = 219 264-13 = 251

16kB = 16384Byte = 214 Byte 14 216-14 = 22 232-14 = 218 264-14 = 250

Tipp zum Rechnen ohne Taschenrechner: Man merke sich, dass 1024 Byte = 210 Byte.

Zum Beispiel sind 8192 Byte = 1024 * 8 Byte = 210 * 23 Byte = 213 Byte.


Angenommen, Ihr System bietet 32 Bit-breite virtuelle Adressen und der physikalische Speicher sei über 24 Bit-breite Adressen adressierbar.

Geben Sie nun an, wie viele Bits der jeweiligen Adressen auf Seitennummer s und zugehöriges Offset wv bzw. auf Kachelnummer k und zugehöriges Offset wp für folgende Seitengrößen entfallen: 1 KB, 2 KB, 4 KB, 8 KB.

Lösung:Seitengröße Offsetbreite

(physikalisch) wpOffsetbreite(virtuel) wv

Seitenummers

Kachelnummerk

1kB = 1024Byte = 210 Byte 10Bit 10Bit 32 – 10 = 22 Bit 24 – 10 = 14 Bit

2kB = 2048 Byte = 211 Byte 11 Bit 11 Bit 32 – 11 = 21 Bit 24 – 11 = 13 Bit

4kB = 4096Byte = 212 Byte 12 Bit 12 Bit 32 – 12 = 20 Bit 24 – 12 = 12 Bit

8kB = 8192Byte = 213 Byte 13 Bit 13 Bit 32 – 13 = 19 Bit 24 – 13 = 11 Bit

Cache Hits und Misses Nehmen Sie folgende Speicherarchitektur an: Bytes im Speicher sind einzeln adressierbar und Speicherzugriffe erfolgen auf einzelne Bytes (also nicht z.B. auf 4-Byte-Wörter). Adressen haben eine Größe von 13 Bits. Der Cache ist 2-Wege-assoziativ, benutzt eine Blockgröße von 4 Bytes und 8 Mengen. Der Inhalt des Caches sei der folgende in der untern gezeigten Abbildung. (Hexadezimalzahlen!)

Wie verteilen sich die 13 Bit einer Adresse auf die Teile Blockoffset (CO), Mengenindex (CI) und Tag (CT)? Erläutern Sie die drei Begriffe.

Die niedrigstwertigen Bits werden für das Blockoffset (CO) verwendet. Wir haben Blöcke der Größe 4 Bytes, d.h. wir brauchen zwei Bits (22=4), um jedes Byte in diesen Blöcken adressieren zu können. Die nächsten drei Bits bilden den Mengenindex (CI). Mit drei Bits (23=8) können wir die gegebenen 8 Mengen eindeutig adressieren. Die restlichen (höchstwertigen) acht Bits bilden das Tag (CT), welches Kollisionen, die mit Mengenindex und Blockoffset auftreten können, eindeutig auflöst (weil alle Bits zusammen eben eine eindeutige Adresse bilden).

Nehmen Sie an, ein Programm referenziert ein einzelnes Byte an der physikalischen Speicheradresse 0x0E34. Bestimmen Sie CO, CI, und CT. Gibt es einen Cache-Miss? Welcher Wert wird zurückgegeben (hexadezimal)?

0x0E34

CT (Tag) CI(Megenindex) CO (Offset)

0 0 0 0 1 1 1 0 0 0 1 1 0 1 0 0

0x7 0x1 0x5 0x0

0x0E34 Der Mengenindex lautet 0x5, das Tag 0x71. Der entsprechende Block ist gültig und es handelt sich somit um einen Cache Hit. Das Byte an Blockoffset 0x0 liefert den Rückgabewert 0x0B.


Umsetzung virtuelle nach physikalische AdresseAngenommen ein Computer besitzt einen virtuellen Speicher von 232 Bytes und einen physikalischen Speicher von 218 Bytes. Der virtuelle Speicher ist mittels Paging umgesetzt, wobei die Page Größe 4096 Bytes beträgt. Skizzieren Sie, wie das System bei gegebener logischer Adresse die korrespondierende physikalische Lokation feststellt.

Gegeben sei folgende Seitentabelle:

Berechnen Sie die virtuelle Seitennummer und den Offset für die folgenden dezimalen virtuellen Adressen AL 20000,32768,60000 unter Annahme einer Seitengröße S von 212 Bytes. Verwenden Sie die gegebenen Formeln.

Ap physische Adresse (=Speicheradresse) (pysical address) AL logische Adresse (=Programmadresse bzw. virtuelle Adresse) (virtual/logical address) v Verschiebungsfaktor S Seitengröße (2k, k ist konstant) (page size) Pv Seitennummer (positiver Ganzahlwert inklusive 0) (page number) Pp Seitenrahmennummer (positiver Ganzahlwert inklusive 0) (page frame number)AR Relativadresse (zu Seitenbeginn) (relativ address) PB Seitenrahmenstartadresse (page frame base address)Ap = AL +v S ∗ (1) Pv = AL / S (2) Pp = Pv + v (3) AR = AL % S (4)


Berechnen Sie die virtuelle Seitennummer und den Offset für die folgenden dezimalen virtuellen Adressen AL 20000,32768,60000 unter Annahme einer Seitengröße S von 212 Bytes. Verwenden Sie die gegebenen Formeln.

S = 4096

AL = 20000

PV =AL

S=

200004096

= 4

Pp = 4

v = 0

----------------------------------------------------------------------

S = 4096

AL = 32768

PV =AL

S=

327684096

= 8

Pp = XXX

v = XXX

Page Fault, Seite muss eingelagert werden

----------------------------------------------------------------------

S = 4096

AL = 60000

PV =AL

S=

600004096

= 14

Pp = XXX

v = XXX

Page Fault, Seite muss eingelagert werden


Besprechen Sie mit Ihrem Tutor die Vor- und Nachteile der drei nachfolgenden Seitenersetzungsstrategien.

First-In-First-Out

Optimal

Least Recently Used

First-In-First-Out: + Einfach in der Ausführung und Umsetzung- Nicht sehr Effektiv- Unterliegt der Belady Anomalie- Seiten im Zugriff können ebenfalls entfernt werden (Lösung hierfür: Second Chance)

Optimal: + Niedrigste Page Fault Rate+ Unterliegt nicht der Belady Anomalie- Schwer umzusetzen- Benötigt Voraussicht, d.h. Wissen über die Zukunft

Least Recently Used: + Unterliegt nicht der Belady Anomalie+ Nahe am Optimum- Schwierig zu implementieren- Benötigt besondere Hardware (Lösung: LRU Approximation über die Benutzung des Referenced-Bits)

Sonstige Seitenersetzungs-Alogorithmen:Algorithmus Kommentar

Optimal Unrealisierbar, aber gut für Vergleiche

NRU (NOT Recently Used) Sehr primitiv

FIFO (First-In, First-Out) Auch wichtige Seiten könnten entfernt werden

Second Chance Enorme Verbesserung gegenüber FIFO

Clock Realistisch

LRU (Least Recently Used) Exzellent, aber schwierig zu implementieren

NFU (Not Frequently Used) Unoptimiert mit LRU vergleichbar

Aging Effizienter Algorithmus, der fast LRU erreicht

Working Set Etwas aufwändig zu implementieren

WSClock Guter und effizienter Algorithmus


Ein Computer hat vier Seitenrahmen. Die Tabelle zeigt für jede Seite die Ladezeit, die Zeit des letzten Zugriffs sowie die R- und M-Bits. Die Zeiten sind jeweils in Uhrintervallen angegeben.

Seite Geladen Zugriff R M

0123

126230140110

280265270285

1001

0101

1. Welche Seite ersetzt NRU?

Der Not Recently Used Algorithmus versucht zunächst, eine Seite zu finden, die weder referenziert noch modifiziert wurde. Ist keine solche verfügbar, wird eine lediglich modifizierte Seite ausgelagert, dann eine lediglich referenzierte. Gelingt auch dies nicht, wird eine referenzierte und modifizierte Seite gewählt. In unserem Falle wird Seite 2 ausgelagert.

2. Welche Seite ersetzt FIFO?

Der First-In-First-Out Algorithmus wählt die am frühesten eingelagerte Seite aus, und ersetzt diese. Hier ist dies Seite 3.

3. Welche Seite ersetzt LRU?

Der Least Recently Used Algorithmus wählt die Seite aus zum Auslagern aus, deren Referenzierung am Weitesten zurückliegt. Dies ist hier Seite 1.

4. Welche Seite ersetzt Second-Chance?

Dieser Algorithmus findet zunächst die älteste Seite, und prüft, ob diese das Referenced-Bit gesetzt hat. Ist es gesetzt, wird es nur auf false gesetzt, und die Zeit der Einlagerung aktualisiert. Andernfalls wird die Seite ausgelagert. Im Beispiel werden Seite 3 und Seite 0 mit dem aktuellen Zeitstempel versehen, und das Referenced-Bit auf false gesetzt. Ausgelagert wird Seite 2.

Was versteht man unter Belady’s Anomalie?

Belady’s Anomalie bedeutet, dass mehr Kacheln nicht unbedingt zu weniger Seitenfehlern führen.


Paging, Clock/Second Chance, virtuelle- und physische Adresse

Gegeben sei ein Rechnersystem mit 8 Kacheln, die Seitentabelle sei entsprechend folgender Tabelle belegt.

Seite Kachel Ladezeit R-Bit M-Bit

0 0 110 1 0

1 1 120 0 1

2 2 115 0 0

3 3 130 0 0

… … … … …

9 7 132 0 0

10 - 103 0 0

11 4 101 0 0

12 5 100 1 0

13 6 102 1 0

Geben Sie den Inhalt der Seitentabelle inklusive R-Bit und M-Bit nach der Folge von Schreibzugriffen auf die Seiten 2,5,7,10 an, wenn der Clock"=Seitenersetzungsalgorithmus verwendet wird (oder unter Verwendung des FIFO"=Second"=Chance"=Seitenersetzungsalgorithmus).

Wenn eine Seite eine zweite Chance bekommt, wird ihre Ladezeit auf den aktuellen Wert gesetzt. Nehmen Sie vereinfachend an, dass auf das letzte initiale Laden einer Seite folgend zu allen vollen zehn Zeitschritten ein Schreibzugriff beim Betriebssystem ankommt. Das Setzen eines R-Bits sowie das Zurückschreiben einer Seite auf den Hintergrundspeicher dauert jeweils eine Zeiteinheit.

Für die oben angegebene Aufgabe ist die Adressübersetzung beim Paging näher zu betrachten. Der Computer hat eine Hauptspeichergröße von 64 KB und einen Virtuellen Speicher. Er will 32 virtuelle Seiten adressieren. Sie betrachten die unveränderte Tabelle (siehe oben) als Grundlage für die folgenden Aufgaben.

1. Wie lautet die höchste virtuelle Speicheradresse?

Die Seiten- bzw. Kachelgröße beträgt: 64 KB / 8 Kacheln = 8 KB/Kachel = 8192 Bytes/Kachel

Somit ergibt sich für die höchste virtuelle Speicheradresse: 8 KB/Seite * 32 Seiten - 1 Byte = 213 Byte/Seite * 25 Seiten - 1 Byte = 218 Byte - 1 Byte = 262.143 Byte

Wir können also 262.144 Bytes von 0 bis 262.143 adressieren. Die höchste Adresse ist also 262.143.


2. Wie viele Bits sind für die virtuelle und physische Adresse mindestens zu reservieren?

Die Kacheln (Seitenrahmen, frame) im physischen Hauptspeicher sind das Äquivalent zu den Seiten im virtuellen Speicher. Es sind 8 Kacheln und 32 Seiten gleicher Größe (8 KB) vorhanden.Eine virtuelle Adresse ist wie folgt aufgebaut: Virt. Adr. = <Seitennummer + Offset innerhalb der Seite> Es sind 32 = 25 virtuelle Seiten vorhanden, daher kann die Nummer einer Seite mit 5 Bit dargestellt werden. Um ein beliebiges Byte innerhalb einer Seite zu adressieren, werden 13 weitere Bits benötigt (8192 KB = 213 Bytes). Eine physische Adresse ist wie folgt aufgebaut: Phys. Adr. = <Kachelnummer + Offset innerhalb der Kachel> Es sind 8 = 23 Kacheln vorhanden, woraus folgt, dass 3 Bits für die Kachelnummer nötig sind.

eine virtuelle Adresse braucht 18 Bits und eine physische Adresse braucht 16 Bits.⇒

3. Welche virtuellen Adressen hat ein Programm verwendet, wenn die Hauptspeicher-Zugriffe auf das3.1 Byte #8192 (absolute Adressierung)3.2 Byte #565 (Offset) der Kachel 4

erfolgen ?

HS-Adresse Kachel Offset Virtuelle Seite Virtuelle Adresse

8192 1 0 1 8192 Byte

0x8235 4 565 11 11 * 8 kB + 565 Byte= 11 * 8 * 1024 Byte + 565 Byte= 90677 Byte

Die Seiten- bzw. Kachelgröße beträgt 8192 Byte.

4. Ein Programm liest von den virtuellen Adressen #73868, #90113 und #42871.Welche Hauptspeicheradressen werden angesprochen?

viruelle Adresse Seite Offset Kachel HS

73868 0x1208c 0001 0010 0000 1000 1100 9 0x008c 7 0xe08c

74000 0x12110 0001 0010 0001 0001 0000 9 0x0110 7 0xe110

90113 0x16001 0001 0110 0000 0000 0001 11 0x0001 4 0x8001

42871 0x0a777 0000 1010 0111 0111 0111 5 0x0777 Seitenfehler X

5 Bits für Seitenummer

13 Bits für Offset

Zu beachten ist , dass die viruelle Adresse nur eine Länge von 18 Bits hat.


Strategien zur Speicheralloziierung I Es seien folgende Speicherverwaltungsstrategien gegeben:

first fit next fit best fit worst fit

Für die Bewertung und den Vergleich dieser Strategien zum Belegen und Freigeben von zusammenhängenden Speicherbereichen seien die folgenden Eigenschaften von Interesse:

1. die Ausnutzung des Speichers

2. die Art der Zerstückelung des Speichers, die damit verbundene Anzahl der Freibereiche und der Suchaufwand sowie

3. der Aufwand zur Erstellung und Führung der Verwaltungsstrukturen.

Erklären Sie kurz die Funktionsweise der vier gegebenen Strategien und vergleichen Sie diese im Hinblick auf die vorgenannten Eigenschaften.

First-Fit Die Frei-Bereiche werden in einer Liste verwaltet. Soll ein Bereich der Länge r belegt werden, so wird die Liste ausgehend von dem ersten Listenelement nach einem Bereich der Länge l ≥ r durchsucht und der entsprechende Bereich wird aus der Frei-Bereichs-Liste entfernt. Der Bereich der Länge l wird in zwei Bereiche, nämlich einen Bereich der Länge r und einen der Länge l - r aufgeteilt. Der Bereich der Länge l - r wird wieder in die Frei-Bereichs-Liste eingefügt. Die Verwaltung der Frei-Bereichs-Liste ist einfach. Da der erste passende Bereich belegt wird, ist der Suchaufwand in der Regel nicht sehr hoch. Da bei der First Fit Strategie stets vom Beginn der Liste aus gesucht wird, besteht jedoch die Tendenz, dass sich im Verlauf der Lebenszeit des Systems viele kleine Bereiche am Kopf der Liste ansammeln, die jeweils durchsucht werden müssen, womit zum einen der Suchaufwand ansteigt und zum anderen eine Vielzahl unbrauchbarer aber freier Bereiche verwaltet werden, so dass der zur Verfügung stehende Speicher nur ungenügend ausgenutzt wird

Next-FitNext-Fit funktioniert genauso wie First-Fit, merkt sich aber die Position, an der er zuletzt eine passende Lücke gefunden hat, und beginnt seine nächste Suche an dieser Stelle statt am Anfang des Speichers. Auch hier gibt es die Tendenz zu Erzeugung kleiner Frei-Bereiche, die jedoch durch das Rotieren wesentlich abgeschwächt wird.

Best-FitEs wird wiederum eine Frei-Bereichs-Liste verwaltet. Falls die Liste nicht nach der Größe der freien Bereiche geordnet ist, muss die gesamte Liste nach dem am besten passenden Bereich durchsucht werden. Bei dieser Strategie besteht die Gefahr des Auftretens kleiner und unbrauchbarer Frei-Bereiche noch wesentlich stärker, als bei der First Fit Strategie. Ordnet man die Frei-Bereichs-Liste nach der Größe der Bereiche, so steigt der Aufwand zum Einfügen eines wieder freigegebenen Bereiches in die Liste, der Aufwand zum Belegen eines passenden Bereichs sinkt jedoch.

Worst-FitUm die Erzeugung kleiner und unbrauchbarer Frei-Bereiche zu vermeiden, wird bei der Worst-Fit Strategie versucht, möglichst große Bereiche von dem zu belegenden Bereich wieder abzuspalten und zur Verfügung zu stellen. Der Suchaufwand entspricht dem von Best-Fit.


Strategien zur Speicheralloziierung IIGegeben sei eine Liste freier Speicherbereiche: 100kB - 400kB - 250kB - 200kB - 50kB Wie verhalten sich jeweils die Strategien first fit, next fit, best fit und worst fit auf die nacheinander eingehenden Speicheranforderungen 30kB, 60kB, 120kB, 20kB, 100kB, 250kB?Halten Sie dabei den Zustand nach jeder Speicheranforderung fest. (Tipp: Nutzen Sie eine Tabelle.)

First-Fit / Next Fit (führen in diesem Fall zufälligerweise zum gleichen Ergebnis)

Anfrage Liste freier Speicherbereiche

100kB 400kB 250kB 200kB 50kB

30kB 70kB 400kB 250kB 200kB 50kB

60kB 10kB 400kB 250kB 200kB 50kB

120kB 10kB 280kB 250kB 200kB 50kB

20kB 10kB 260kB 250kB 200kB 50kB

100kB 10kB 160kB 250kB 200kB 50kB

250kB 10kB 160kB 0kB 200kB 50kB

Best-Fit


100kB 400kB 250kB 200kB 50kB

30kB 100kB 400kB 250kB 200kB 20kB

60kB 40kB 400kB 250kB 200kB 20kB

120kB 40kB 400kB 250kB 80kB 20kB

20kB 40kB 400kB 250kB 80kB 0kB

100kB 40kB 400kB 150kB 80kB 0kB

250kB 40kB 150kB 150kB 80kB 0kB

Worst-Fit


100kB 400kB 250kB 200kB 50kB

30kB 100kB 370kB 250kB 200kB 50kB

60kB 100kB 310kB 250kB 200kB 50kB

120kB 100kB 190kB 250kB 200kB 50kB

20kB 100kB 190kB 230kB 200kB 50kB

100kB 100kB 190kB 130kB 200kB 50kB

250kB Kein geeigneter Speicherbereich vorhanden!


Code und Performance Analyse Gegeben sei folgender Code-Abschnitt. Beantworten Sie die darauf folgenden Fragen:

int main(void) { unsigned int size = 10000; float buffer = ∗ malloc(sizeof(float) size 3); ∗ ∗double sum = 0.0;

// ###### Code Variante A ###### for(int i = 0; i < 3 size ; i ++) ∗{ buffer [ i ] = 3.0 f ; // Zu Testzwecken => 3.0f}for(int i = 0; i < size ; i ++) { buffer [2 size+i ] = buffer [1 size+i ] buffer [ i ];∗ ∗ ∗}

sum = 0.0; for(int y = 0; y < size ; y++) { sum += buffer [2 size+y ];∗}printf ("Summe: %f\n", sum);

// ###### Code Variante B ###### for(int i = 0; i < 3 size ; i ++)∗ buffer [ i ] = 3.0 f ; // Zu Testzwecken => 3.0f for(int i = 0; i < 3 size ; i += 3) ∗{ buffer [ i +2] = buffer [ i +1] buffer [ i ];∗}sum = 0.0; for(int y = 2; y < 3 size ; y += 3) ∗{ sum += buffer [y ]; }printf ("Summe: %f\n", sum);// #############################free ( buffer ); return 0;}

1. Was können Sie zur Effizienz der beiden Code-Varianten sagen?Variante A nutzt den Cache bei den Multiplikationen schlecht aus, aber dafür bei der Summe umso besser. Variante B nutzt den Cache bei den Multiplikationen wesentlich besser aus, aber dafuer bei der Summe etwas schlechter.

2. Ist das ’free(buffer)’ hier nötig?Eigentlich wird der Speicher beim beenden des Programms ohnehin freigegeben, aber es weg zu lassen wäre schlechter Programmierstil.

3. Welche CPU Erweiterung könnte man hier generell sinnvoll nutzen, um den Code schneller zu machen?Man koennte Vektorinstruktionen verwenden. (SSE, AVX...)

4. Was sollte man bedenken, wenn man auf die Idee kommt, diesen Code mit einer GPU zu beschleunigen?In diesem Beispiel muessten sehr viele Daten zwischen GPU und Hauptspeicher kopiert werden, obwohl relativ wenig damit gerechnet wird. Es ist also keine enorme Performance Steigerung zu erwarten.


Kommandozeilenparameter

Schreiben Sie ein C-Programm, welches als Komandozeilenparameter einen String einliest und die Anzahl der darin enthaltenen Leerzeichen ausgibt. Achten Sie auf alle möglichen Nutzereingaben und verwenden Sie keine Funktionen aus der String-Library.

int main(int argc , char argv []) ∗{ // 0.5 Punkte if(argc < 2){ perror ("Zu wenig Argumente"); return 1;} // 2 Punkte int count = 0; char *current = argv [1]; while(*( current++) != ’\0’){ if(*current == ’ ’) count++;}// 0.5 Punkte printf ("Anzahl der Leerzeichen: %i", count ); return 0;}


Ausgabe

Welche Ausgabe hat das folgende Programm? Notieren Sie auch die jeweiligen Werte aller Variablen beginnend ab Zeile 14 bis 17. Verwenden Sie für Ihre Lösung das vorgegebene Textfeld. Geben Sie bei Ihren Lösungsvorschlägen jeweils die Zeilennummern mit an.

1 int addv(int a, int b){ 2 return a+b; 3 } 4 5 void addr(int *a, int *b){ 6 *a += *b; 7 *b = *a; 8 } 9 10 int main(int argc , char* argv []) { 11 int a[] = {1, 2, 3, 4, 5}; // a[] = {1,2,3,4,5}12 int b = 2, i = 0; // b = 2 a[] = {1,2,3,4,5}13 b = addv(b, *a); // b = 2+1 = 3 a[] = {1,2,3,4,5} 14 addr(&a[b] , &b); // b = 7, a[] = {1,2,3,7,5} 15 b −= a[3]; // b = 0 a[] = {1,2,3,7,5} 16 *(&(&(*a))[1]) = 3; // b = 0 a[] = {1,3,3,7,5}17 a[b] = addv(b, a[++b ]); // b = 1 a[] = {4,3,3,7,5}18 19 for(; i <5; i ++){ 20 printf ("a[%i]: %i\n", i , a[ i ]); 21 } 22 printf ("b: %i", b); 23 }

Wichtig! *(&(&(*a)) ist das Gleiche wie a, weil & und * sich gegenseitig aufheben.


Analyse

Gegeben sei folgendes Programm.

1. Was gibt dieses Programm auf der Konsole aus?

2. Wurde der Fragezeichen-Operator in Zeile 11 sinnvoll verwendet?

1 int main(void) 2 { 3 char* pointer = NULL; 4 char* bufferA = "xGZboUo?jH.1337.d"; 5 char* bufferB = "x!kNc-_-u0x539:)l"; 6 7 for(int i = 1; i <= 20; i *= 4) 8 { // i = 1 i = 4 i = 169 pointer = bufferA+i ; // p = 'G' p = 'o' p = 'd'1011 ( i > 2 && i < 8) ? printf ("%c%c", // no yes no12 bufferA [ i ] , // --- “o“ ---13 *( pointer +2)) : // --- “o“ ---14 printf ("%c", *(bufferA+i )); // “G“ --- “d“15 } 16 17 for(int y = 16; y >= 1; y /= 2) 18 { 19 if(y >= 16) // y = 16 y = 8 y = 4 y = 220 printf (" "); // “ “ --- --- ---21 22 printf ("%c", bufferB [y]); // “l“ “u“ “c“ “k“23 24 if(y < 2) // --- --- --- ---25 printf ("\n"); 26 }27 28 return 0; 29 }

1. "Good luck!"

2. Nein, etwas lang für einen Einzeiler → Unübersichtlich

Documents

Betriebssysteme und hardwarenahe Programmierung bei …home.in.tum.de/~grasso/files/BuhPbdS _Zusammenfassung.pdf · Harvard Architektur bietet zwei getrennte ... Nennen Sie die Funktionseinheiten