Prüfungs Themen

Heap

Der dynamische Speicher, auch Heap (engl. für Halde, Haufen), Halden- oder Freispeicher ist ein Speicherbereich, aus dem zur Laufzeit eines Programmes zusammenhängende Speicherabschnitte angefordert und in beliebiger Reihenfolge wieder freigegeben werden können. Die Freigabe kann sowohl manuell als auch mit Hilfe einer automatischen Speicherbereinigung erfolgen. Eine Speicheranforderung vom Heap bzw. Freispeicher wird auch dynamische Speicheranforderung genannt.

Der Unterschied zum Stack (Stapel- oder Kellerspeicher) besteht darin, dass beim Stack angeforderte Speicherabschnitte in der umgekehrten Reihenfolge wieder freigegeben werden müssen, in der sie angefordert wurden. Beim Stack spricht man auch von automatischer Speicheranforderung. Die Laufzeitkosten einer automatischen Speicheranforderung sind in der Regel deutlich geringer als die bei der dynamischen Speicheranforderung. Allerdings ist bei intensiver Nutzung durch sehr große oder sehr viele Anforderungen der für den Stack reservierte Speicher bald aufgebraucht - dann droht ein Programmabbruch wegen Stapelüberlauf.

Selber Speicher verwalten vs. Garbage Collection

Probleme der herkommlichen Speicherverwaltung

Mit der herkommlichen Speicherverwaltung sind insbesondere zwei haufig auftretende Fehlertypen verbunden: Das Speicherleck Von einem Speicherleck (memory leak) spricht man dann, wenn ein Programm im Laufe der Zeit immer mehr Speicher vom Betriebssystem anfordert, ohne dass es tatsachlich so viel Speicher fur seine Aufgabe benotigt. Der Grund ist meist, dass vergessen wurde, Objekte bzw. Speicher, der nicht mehr benotigt wird, freizugeben und so dem allgemeinen Freispeicher-Pool wieder zuzufuhren. Die Hintergrunde solcher Fehler sind sehr unterschiedlich, aber oft existieren gar kei- ne Zeiger mehr in den zuviel belegten Speicher. Es gibt z.B. Funktionen, die Speicher belegen und Zeiger darauf zuruckgeben. Manchmal bietet die Bibliothek, aus der eine solche Funktion stammt, eine Infrastruktur, die nicht mehr benotigten Speicher freigibt, weil er z.B. mit irgendeiner Resource verknupft ist, deren Lebenszeit-Ende an einer an- deren Stelle bekannt wird. Gibt es so etwas nicht, muss sich der Programmierer, der die Bibliothek verwendet, selbst darum kummern, nicht mehr benotigten Speicher wieder freizugeben. In vielen anderen Fallen ist es ein leicht vorkommender Fluchtigkeitsfehler des Pro- grammierers, dass er Objekte anlegen lasst und sie vor Verlassen des Gultigkeitsbereichs des daraufzeigenden Zeigers nicht wieder freigibt. Es kommt auch vor, dass eine Zeiger- variable, die noch einen Zeiger auf ein existierendes Objekt enthalt, mit einem neuen Wertuberschrieben wird, wodurch der Speicher des Objekts, auf das der Zeiger vorher gezeigt hat, nun auch verloren ist, falls nicht noch an einer anderen Stelle ein weiterer Zeiger auf das alte Objekt existiert. Wie auch immer es zu einem Speicherleck gekommen ist; sobald dem Betriebssystem der Speicher ausgeht, fuhrt es zur gewaltsamen Programmbeendigung durch das Be- triebssystem. Es totet dann der Reihe nach die großten Verschwender, um das System wieder in einen bedienbaren Zustand zu versetzen. In aller Regel ist das verursachen- de Programm dabei das erste, welches getotet wird. Dabei gehen ungespeicherte Daten verloren.

Losung durch automatische Speicherverwaltung

Die Losung dieser Probleme liegt darin, dem Programmierer die Aufgabe der Speicher- verwaltung durch ausgeklugelte Algorithmen abzunehmen. Das reduziert die Haufigkeit der genannten Probleme und macht den geschriebenen Codeubersichtlicher. Es muss eine alsasthetisch und sinnvoll erachtete Strukturierung einer objektorientierten Anwendung nicht mehr wegen der Speicherverwaltung abgeandert werden, denn manchmal ist die Ursache fur das Lebenszeitende eines Objekts nicht dort erkennbar, wo sich der Zeiger darauf befindet. Nach der herkommlichen Methode mussten dann Hilfskonstruktionen oder Benachrichtigungskanale geschaffen werden um seine Freigabe zu veranlassen. Die- ser Aufwand entfallt also, wenn die Speicherverwaltung automatisch vorgenommen wird. Letztlich verringert das die Entwicklungszeit und somit auch die Entwicklungskosten.

malloc

A function in the standard C library that performs dynamic allocation of memory. Many people use "malloc" as a verb to mean "allocate dynamically".

Für was?

Um den Benötigten Speicher im Memory zu reservieren.

Wie funktionierts?

1. The malloc statement first looks at the amount of memory available on the heap and asks, "Is there enough memory available to allocate a block of memory of the size requested?" The amount of memory needed for the block is known from the parameter passed into malloc. If there is not enough memory available, the malloc function returns the address zero to indicate the error (another name for zero is NULL and you will see it used throughout C code). Otherwise malloc proceeds.
2. If memory is available on the heap, the system "allocates" or "reserves" a block from the heap of the size specified. The system reserves the block of memory so that it isn't accidentally used by more than one malloc statement.
3. The system then places into the pointer variable (p, in this case) the address of the reserved block. The pointer variable itself contains an address. The allocated block is able to hold a value of the type specified, and the pointer points to it.

Was ist ein Block?

Block is a vague term for an (often contiguous) area of memory(1). Often used to describe memory(2) allocated by an allocator such as malloc.

Was ist ein Chunck?

Chunks map RAM into contiguous virtual addresses. A chunk consists of a reserved region and a committed region. The reserved region is the contiguous set of virtual addresses which may be occupied by the chunk. The committed region is the region in which RAM is actually mapped. The size of a chunk is dynamically alterable, allowing the committed region to vary in size from zero up to the reserved region size, in integer multiples of the processor page size. This allows processes to obtain more memory on demand. Generally the committed region starts at the bottom of the reserved region.

Einfache Speicherreservierung (Zeichnung machen)

Memory allocation is a process that assigns chunks of memory upon request of the various processes running on a machine.

Simple Implementation

 #define MAX_MEMORY 1024 * 1024 * MEMORY_SIZE_IN_MEGABYTES
 int peak;
 void *malloc(size_t size) {
     void *current;
 if( MAX_MEMORY – peak < size ) return null;
     current = (void *)peak;
     peak += size;
     return current;
 }
 
 void free(void *ptr) {
     return;
 }

Shortest path problem erklären

In graph theory, the shortest path problem is the problem of finding a path between two vertices such that the sum of the weights of its constituent edges is minimized. An example is finding the quickest way to get from one location to another on a road map; in this case, the vertices represent locations and the edges represent segments of road and are weighted by the time needed to travel that segment.

Dijkstra's algorithm

Dijkstra's Algorithm finds the shortest path from a starting vertex to all other vertices in a graph. It should be noted that distance between nodes can also be referred to as weight.

1. Create a distance list, a previous vertex list, a visited list, and a current vertex.
2. All the values in the distance list are set to infinity except the starting vertex which is set to zero.
3. All values in visited list are set to false.
4. All values in the previous list are set to -1.
5. Current node is set as the starting vertex.
6. Mark the current vertex as visited.
7. Update distance and previous lists based on those vertices which can be immediately reached from the current vertex.
8. Update the current vertex to the unvisited vertex that can be reached by the shortest path from the starting vertex.
9. Repeat (from step 6) until all nodes are visited.

Vergrösserbare Arrays

Sind arrays, die zur runtime vergrössert bzw. verkleinert werden können.

Hash tabellen

A dictionary in which keys are mapped to array positions by hash functions. Having the keys of more than one item map to the same position is called a collision. There are many collision resolution schemes, but they may be divided into open addressing, chaining, and keeping one special overflow area. Perfect hashing avoids collisions, but may be time-consuming to create.

Garbage Collection

Grundlegende GC Algos

Mark and Scan

Mark-Scan techniques are `stop-the-world' collectors and subsequently can bring the entire distributed environment to its knees for a significant period of time. Going trough all Objects and Just set a bit to mark the items as "found". Then later make a pass through the whole heap and identify anything that isn't marked as "unfindable" stuff that can be reused and free it from memory.

Two space copying

Wie funktionierts? (Generationell) Im grunde hat man 2 Gleichgrosse speicherbereiche und benutzt jeweils nur einen zur gleichen zeit. Wenn der einte space aufgebraucht ist, wird alles durchgescannt und die noch benötigten sachen in den nächsten space kopiert danach kann der space komplett ausgeräumt werden werden.

Reference counting

Sie basiert sie darauf, dass sich an jedem verwalteten Objekt ein Zähler befindet, der beim Einrichten eines Verweises auf dieses Objekt erhöht und beim Löschen eines Verweises verringert wird. Fällt der Zähler auf 0, kann das Objekt selbst und alle in ihm enthaltenen Verweise gelöscht werden.

Reference counting is often known as a garbage collection algorithm where each object contains a count of the number of references to it held by other objects. If an object's reference count reaches zero, the object has become inaccessible, and it is destroyed. Simple reference counts require frequent updates. Whenever a reference is destroyed or overwritten, the reference count of the object it references is decremented, and whenever one is created or copied, the reference count of the object it references is incremented.

Was passiert bei einem Loop?

Vileicht gibts irgendwann ein Buffer overflow?

GC Variablen

???

Compaction

Compaction creates contiguous free memory at the top of the heap by moving chunks of allocated space toward the heaps lower end. Compaction is important because the mark and sweep algorithm will often cause the heap to fragment. To reduce the fragmentation a part of the heap is compacted each garbage collection.

Wie gehts

1. Merke erste freie Ziel adresse
2. Sobald wieder ein Datenblock kommt, ändere die Referenz zum freien zielblock und zähle die differenz vom anfang dieses Blocks bis zum nächsten block zum next_free pointer dazu
3. wiederhole diesen prozess, bis das ganze memory durch ist
4. verschiebe die Blöcke zur vorgemerkten adresse