dynamischespeicherverwaltung.tex

\section{Dynamische Speicherverwaltung}
Mit den bisher eingeführten Grundlagen der Programmiersprache C kann man einfache Probleme lösen.
Das haben wir am Beispiel des Einfügesortierens gesehen.
Im folgenden zweiten Teil werden wir versuchen, die Kenntnis von C zu vertiefen und zu erweitern.

Dafür werden wir den Quelltext für das Sortieren von Zahlen in drei Richtungen versuchen zu verbessern:
\begin{enumerate}
\item Bei der Benutzung von Arrays muss man immer schon zur Zeit der Übersetzung wissen, wie groß das Array maximal werden darf.
  Das ist eine relativ starke Einschränkung, die sehr ineffizient sein kann.
  Entweder, man hat viel zu viel Speicher bereitgestellt, oder zu wenig.
  Genau passen wird es selten.
  Diese Einschränkung werden wir mit Hilfe der dynamischen Speicherverwaltung überwinden.

\item Man kann sich relativ schnell klar machen, dass der Einfügesortier-Algorithmus im schlechtesten Fall (\emph{worst case}) Größenordnung $n^2$ Operation benötigt, um das korrekte Ergebnis zu erzeugen.
  Nehmen Sie eine Folge von Zahlen, die absteigend sortiert ist.
  Dann braucht man $1 + 2 + 3 + ... + n = n(n+1)/2$ Vergleichs- und Vertauschoperationen, um die Folge aufsteigend zu sortieren.
  Für sehr große $n$ ergibt das Ordnung $n^2$ Operationen.
  Man sagt auch, der Algorithmus ist von der Ordnung $O(n)$.
  Es gibt Algorithmen, die eine wesentlich besseres worst case Skalierungsverhalten haben. 

\item Beim Einlesen haben wir bisher den Standardeingabe benutzt.
  Das können wir verbessern, indem wir direkt aus Dateien einlesen.
\end{enumerate}
Darüber hinaus werden wir diskutieren, wie man Quelltext sinnvoll in verschiedene Dateien verteilt.
Damit soll die Übersicht einfacher und das Programmieren weniger fehleranfällig werden.
Beim Beispiel Einfügesortieren hatten wir bereits Unterprobleme in jeweils eigene Funktionen ausgelagert.
Diese werden wir auf mehrere Dateien verteilen und zeigen, wie man ein solches Projekt effizient übersetzt.

Zuerst diskutieren wir, wie man Speicher dynamisch reserviert, zugreift und wieder freigibt.
Der Speicher, der einem Programm zugeteilt ist, kann in zwei Kategorien unterteilt werden.
\begin{enumerate}
\item Statischer Speicher\\
  Dieses Teil haben wir schon kennengelernt. 
  Im statischen Speicher befindet sich der Programmcode selbst, und der Speicher aller Variablen, die wir bisher deklariert haben.
  Seine Größe ist zum Zeitpunkt des Übersetzens festgelegt.

\item Dynamische Speicher\\
  Diesen Teil haben wir bisher noch nicht benutzt, aber jedes Programm kann eine bestimmte Menge an dynamischen Speicherplatz nutzen.
  Allerdings muss man sich zur Laufzeit des Programms selbst um das Reservieren und Freigeben dieses Speichers kümmern.
\end{enumerate}
Wenn wir also in einem Programm zum Beispiel einen Zeiger
\begin{lstlisting}
int *list;
\end{lstlisting}
deklarieren, so liegt dieser Zeiger selbst im statischen Speicherbereich.
Er kann aber auf Speicher zeigen, der im dynamischen Speicherbereich liegt.
Dies ist in Abbildung~\ref{abmem} illustriert.

\begin{figure}[!ht]
% Generated with LaTeXDraw 2.0.8
% Tue Feb 28 11:46:41 CET 2017
% \usepackage[usenames,dvipsnames]{pstricks}
% \usepackage{epsfig}
% \usepackage{pst-grad} % For gradients
% \usepackage{pst-plot} % For axes
\scalebox{0.5} % Change this value to rescale the drawing.
{
\begin{pspicture}(0,-1.2792188)(31.8,1.2792188)
\psframe[linewidth=0.04,dimen=outer](31.8,1.1657813)(0.0,-1.0342188)
\psline[linewidth=0.04cm](5.6,1.1657813)(5.6,-1.0342188)
\rput(1.3,0.7 ){\LARGE Statischer}
\rput(7.2,0.7 ){\LARGE Dynamischer}
\rput(1.1,0.1 ){\LARGE Speicher}
\rput(7.2,0.1 ){\LARGE Speicher}
\psline[linewidth=0.04cm](3.4,1.1657813)(3.4,-1.0342188)
\psline[linewidth=0.04cm](4.0,1.1657813)(4.0,-1.0342188)
%\usefont{T1}{ptm}{m}{n}
\rput(4.416406,-1.5){\LARGE Zeiger}
\psframe[linewidth=0.04,dimen=outer](19.2,1.1657813)(14.4,-1.0342188)

\rput(16,0.7 ){\LARGE Reservierter}
\rput(16.5,0.1 ){\LARGE Speicherbereich}

\pscustom[linewidth=0.04]
{
\newpath
\moveto(4.,-2)
%\lineto(7.5,1.5)
\curveto(6,-3.)(10.5,-5.)(14.5,-1.5)
}
\psline[linewidth=0.04cm](14.1,-1.6)(14.5,-1.5)
\psline[linewidth=0.04cm](14.3,-2.0)(14.5,-1.5)

\end{pspicture} 
}
\vspace{0.6cm}
\caption{\label{abmem} Illustration zu dynamischem und statischem Speicher eines Programms.}
\end{figure}

Um Speicher dynamisch zu reservieren, nutzt man Funktionen aus der Standardbibliothek \verb|stdlib.h|.
Das Reservieren erledigt die Funktion \verb|malloc|, was für \emph{memory allocation} steht.
\verb|malloc| hat die folgenden Syntax:
\begin{myexampleblock}{Definition \texttt{malloc}}
\begin{lstlisting}
void *malloc(size_t size);
\end{lstlisting}
  \vspace{-0.7cm}
  Reserviert Speicherzellen von der Größe \verb|size| bytes.
  \begin{itemize}
    \itemsep0.2pt
  \item Rückgabewert: Wenn die Reservierung erfolgreich war, einen Zeiger auf den Anfang des
    reservierten Speicherbereiches, andernfalls \verb|NULL|.
  \item Eingabeparameter \verb|size|: die Größe des zu reservierenden Speicherbereiches in bytes.
  \item Beispielcode:
\begin{lstlisting}
int *array = (int *)malloc(sizeof(int) * 10);
\end{lstlisting}
  \end{itemize}
  \vspace{-0.7cm}
  Man beachte, dass der reservierte Speicherbereich mit der Funktion \verb|free| (siehe unten) wieder freigegeben werden muss, wenn er nicht mehr benötigt wird. 
  Ansonsten steht er für das Programm nicht mehr zur Verfügung.
  Am Ende des Programms wird aller vom Programm reservierte Speicher automatisch freigegeben.
\end{myexampleblock}
Wir haben schon den Rückgabewert \verb|void| kennengelernt, der für keinen Rückgabewert steht.
Ein Zeiger auf \verb|void| repräsentiert einen Zeiger ohne Typ.
Er kann bzw. muss später mit einem \emph{cast} in jeden anderen Zeigertyp umgewandelt werden.
Deshalb wird im Beispielcode ein expliziter \emph{cast} nach \verb|int *| durchgeführt, den man immer bei der Benutzung von \verb|malloc| machen sollte.

Den Zeiger \verb|NULL| haben wir schon kennen gelernt. 
\verb|malloc| gibt \verb|NULL| zurück, falls das reservieren nicht erfolgreich war, aus welchem Grund auch immer.
Daher ist es sehr wichtig bei jedem Aufruf von \verb|malloc| den Rückgabewert auf \verb|NULL| zu testen!
Die Größe eine Typs in byte liefert die Funktion \verb|sizeof|.

Wie schon angedeutet, dynamisch reservierter Speicher muss wieder freigegeben werden, wenn er nicht mehr benötigt wird.
Dafür gibt es die Funktion \verb|free|:
\begin{myexampleblock}{Funktion Definition \texttt{free}}
\begin{lstlisting}
void free(void *memory);
\end{lstlisting}
  \vspace{-0.7cm}
  Gibt einen mit \verb|malloc| reservierten Speicherbereich wieder frei.
  \begin{itemize}
  \item Eingabeparameter: Zeiger auf einen Speicherbereich, der mit \verb|malloc| reserviert wurde.
  \item Beispiel:
\begin{lstlisting}
int *array = (int *)malloc(sizeof(int) * 10);
free(array);
\end{lstlisting}
  \end{itemize}
  \vspace{-0.7cm}
\end{myexampleblock}
Wendet man \verb|free| auf einen Zeiger an, der nicht auf den Anfang eines mit \verb|malloc| reservierten Bereiches zeigt, so erhält man einen Laufzeitfehler.

\subsection{Mehrdimensionale Arrays}

Bisher haben wir uns auf eindimensionale Arrays beschränkt.
Als Beispiel für ein mehrdimensionales Array betrachten wir eine Drehmatrix in zwei Dimensionen um den Winkel $\alpha$. 
Es handelt sich um eine lineare Abbildung, die einen zweidimensionalen Vektor $(x,y)^t$ auf den Vektor $(x',y')^t$ wie folgt abbildet:
\begin{equation}
  \left(\begin{array}{c}x^{,}\\y^{,}\end{array}\right)=
  \left(\begin{array}{cc} \cos\left(\alpha\right) & \sin\left(\alpha\right) \\
    -\sin\left(\alpha\right) & \cos\left(\alpha\right) 
  \end{array}\right)
  \left(\begin{array}{c}x\\y\end{array}\right)
\end{equation}
Die entsprechende Matrix kann man in C mit Hilfe von zweidimensionalen Arrays darstellen.
Die Deklaration eines statische $2\times2$ Arrays sieht wie folgt aus:
\begin{lstlisting}
double rotate2d[2][2];
\end{lstlisting}
Von dieser Deklaration kann man sehen, dass ein zweidimensionales Array ein Array von Arrays ist.
Daher entspricht ein solches zweidimensionales Array auch einem Zeiger auf einen Zeiger auf einen Typ.
Diskutieren wir wieder ein Beispiel:
\begin{lstlisting}
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
int main()
{
  const int SPACEDIM = 2;
  const double M_PI = 3.1415;

  // Speicher reservieren
  double **array2d;
  if ((array2d = (double **)malloc(sizeof(double *) * SPACEDIM)) == NULL)
    {
      printf("Fehler in malloc\n");
      return (-1);
    }
  for (int i = 0; i < SPACEDIM; ++i)
    {
      if ((array2d[i] = (double *)malloc(sizeof(double) * SPACEDIM)) == NULL)
        {
          printf("Fehler in malloc\n");
          return (-2);
        }
    }
  // Werte zuweisen
  array2d[0][0] = cos(M_PI / 4.);
  array2d[0][1] = sin(M_PI / 4.);
  array2d[1][0] = -sin(M_PI / 4.);
  array2d[1][1] = cos(M_PI / 4.);
  // Ausgabe
  for (int i = 0; i < SPACEDIM; ++i)
    {
      for (int j = 0; j < SPACEDIM; ++j)
        {
          printf("%e ", array2d[i][j]);
        }
      printf("\n");
    }
  // Speicher freigeben
  for (int i = 0; i < SPACEDIM; ++i)
    {
      free(array2d[i]);
    }
  free(array2d);
  return (0);
}
\end{lstlisting}
\verb|array2d| ist jetzt als \verb|double**| deklariert, also als Zeiger auf einen \verb|double| Zeiger. 
Dann wird zunächst Speicher für ein Array von \verb|double*| Zeigern reserviert.
Das geschieht in Zeile $10$.
Man beachte, wie an dieser Stelle der Rückgabewert von \verb|malloc| auf \verb|NULL| getestet wird.
Eine Zuweisung der Form \verb|(x = y)| hat selbst den Wert von \verb|x|.
Anschließend wird in der Schleife, die in Zeile $14$ anfängt, für jedes Element des Arrays von \verb|double*| Zeigern selbst wieder Speicher reserviert.
Das muss nun Speicher für \verb|double| selbst sein.
Wieder testen wir den Rückgabewert von \verb|malloc| auf \verb|NULL|.

Es ist wichtig, sich klar zu machen, dass \verb|array2d| vom Typ \verb|double**| ist.
Dementsprechend zeigt es auf Elemente vom Typ \verb|double*|, die dann selbst auf Elemente vom Typ \verb|double| zeigen.
Dies ist in Abbildung~\ref{mem2d} dargestellt.

\begin{figure}[!ht]
% Generated with LaTeXDraw 2.0.8
% Tue Feb 28 15:43:57 CET 2017
% \usepackage[usenames,dvipsnames]{pstricks}
% \usepackage{epsfig}
% \usepackage{pst-grad} % For gradients
% \usepackage{pst-plot} % For axes
\center
\scalebox{0.75} % Change this value to rescale the drawing.
{
\begin{pspicture}(0,-5)(14.8,4.1)

\pscustom[linewidth=0.04]
{
\newpath
\moveto(3.2,1.)
%\lineto(7.5,1.5)
\curveto(3.2,1.5)(4.8,3.5)(6.7,2.2)
}
\psline[linewidth=0.04cm](6.5,2.6)(6.7,2.2)
\psline[linewidth=0.04cm](6.3,2.3)(6.7,2.2)



\psframe[linewidth=0.04,dimen=outer](3.0,0.8725)(0.0,-0.1275)
\rput(1.6, 1.3){Typ: double **}
\rput(1.6, 0.3){Wert:0x1deb430}
\rput(1.6,-0.7){Adresse: 0x7fff541bdbc8}


\pscustom[linewidth=0.04]
{
\newpath
\moveto(9.,2.1)
%\lineto(7.5,1.5)
\curveto(9.,2.5)(10.1,3.1)(11,3.8)
}
\psline[linewidth=0.04cm](10.6,3.7)(11,3.8)
\psline[linewidth=0.04cm](10.6,3.2)(11,3.8)


\psframe[linewidth=0.04,dimen=outer](8.8,1.8)(5.2,0.8)
\rput(6.8, 2.0){Typ: double *}
\rput(6.8, 1.4){Wert:0x1deb450}
\rput(6.8, 0.4){Adresse: 0x1deb430}

\pscustom[linewidth=0.04]
{
\newpath
\moveto(9.,-0.2)
%\lineto(7.5,1.5)
\curveto(9.,-0.2)(10.1,-0.4)(11,-0.9)
}
\psline[linewidth=0.04cm](10.5,-0.5)(11,-0.9)
\psline[linewidth=0.04cm](10.3,-0.7)(11,-0.9)

\psframe[linewidth=0.04,dimen=outer](8.8,-0.25)(5.2,-1.25)
\rput(6.8, -0.1){Typ: double *}
\rput(6.8, -0.7){Wert:0x1deb470}
\rput(6.8, -1.7){Adresse: 0x1deb438}




\psframe[linewidth=0.04,dimen=outer](14.8,3.9)(11.2,2.9)
\rput(13., 4.05){Typ: double }
\rput(13., 3.5){Wert: $\pi$/4}
\rput(13., 2.6){Adresse: 0x1deb450}

\psframe[linewidth=0.04,dimen=outer](14.8,1.7)(11.2,0.7)
\rput(13., 1.85){Typ: double }
\rput(13., 1.3){Wert: $\pi$/4}
\rput(13., 0.4){Adresse: 0x1deb458}

\psframe[linewidth=0.04,dimen=outer](14.8,-0.7)(11.2,-1.7)
\rput(13., -0.55){Typ: double }
\rput(13., -1.1){Wert: -$\pi$/4}
\rput(13., -2.){Adresse: 0x1deb470}

\psframe[linewidth=0.04,dimen=outer](14.8,-2.9)(11.2,-3.9)
\rput(13., -2.65){Typ: double }
\rput(13., -3.2){Wert: $\pi$/4}
\rput(13., -4.1){Adresse: 0x1deb478}


\rput(1.464063,-4.8){\large Zeiger auf double Zeiger.}
\rput(7.271094,-4.8){\large Zeiger auf double.}
\rput(13.05875,-4.8){\large double}
\end{pspicture} 
}
\caption{\label{mem2d} Illustration Zeiger auf Zeiger.}
\end{figure}

Es bietet sich an für die Speicherreservierung einer zweidimensionalen Matrix eine eigene Funktion zu schreiben.
Es ist schließlich ziemlich wahrscheinlich, dass mehr als eine solche Matrix benötigt wird.
Der entsprechende Quelltext könnte beispielsweise so aussehen:
\begin{lstlisting}
#include <math.h>
#include <stdio.h>
#include <stdlib.h>

double **create2darray(const int dim)
{
  double **p1 = NULL;
  if ((p1 = (double **)malloc(sizeof(double *) * dim)) == NULL)
    {
      return (NULL);
    }
  for (int i = 0; i < dim; ++i)
    {
      if ((p1[i] = (double *)malloc(sizeof(double) * dim)) == NULL)
        {
          return (NULL);
        }
    }
  return (p1);
}

int main()
{
  const int SPACEDIM = 2;
  const double M_PI = 3.1415;

  double **array2d;
  if ((array2d = create2darray(SPACEDIM)) == NULL)
    {
      printf("Fehler in malloc\n");
      return (-1);
    }
  // Zuweisen
  array2d[0][0] = cos(M_PI / 4.);
  array2d[0][1] = sin(M_PI / 4.);
  array2d[1][0] = -sin(M_PI / 4.);
  array2d[1][1] = cos(M_PI / 4.);
  for (int i = 0; i < SPACEDIM; ++i)
    {
      for (int j = 0; j < SPACEDIM; ++j)
        {
          printf("%e ", array2d[i][j]);
        }
      printf("\n");
    }
  // hier sollte noch der Speicher freigegeben werden!
  return (0);
}
\end{lstlisting}
Die Funktion \verb|create2darray| liefert als Rückgabewert eine Variable vom Typ \verb|double**|, also genau das, was wir benötigen.
In der Funktion selbst geschieht dann das, was wir im obigen Beispiel schon gezeigt hatten.
Mit \verb|return| wird dann das Objekt zurückgegeben, für das wir Speicher reserviert haben.

An dieser Stelle sieht man einen wichtigen Unterschied zwischen einer normalen Variablen Deklaration und dem Reservieren von Speicher mit \verb|malloc|.
Währen beispielsweise die Variable \verb|p1| in der Funktion \verb|create2darray| natürlich nur in der Funktion selbst sichtbar ist, bleibt der mit \verb|malloc| reservierte Speicher auch außerhalb der Funktion reserviert.
Und indem wir die Adresse zu dieser Speicherstelle von der Funktion an die aufrufende Funktion übergeben, können wir den reservierten Speicherbereich auch außerhalb der Funktion nutzen.

Das bedeutet aber auch, dass Speicher, der mit \verb|malloc| reserviert wurde, und dessen Adresse wir nicht mehr kennen, nicht mehr nutzbar ist.
Auf diese Art und Weise kann man recht einfach versehentlich Programme schreiben, die den gesamten Hauptspeicher eines Rechners reservieren, ohne ihn zu nutzen.
Das führt relativ schnell zur Unbenutzbarkeit des entsprechenden Rechners.
Ein Beispiel für einen solchen Fehler ist der folgende (nicht besonders sinnvolle) Code Abschnitt
\begin{lstlisting}
int list[50];
for (int i = 0; i < 50; i++)
  {
    double *p = malloc(sizeof(double));
    *p = i * i;
    list[i] = *p + (*p) * (*p);
  }
free(p); // falsch, p ist hier nicht mehr sichtbar!
\end{lstlisting}
In jedem Durchlauf der Schleife wird Speicher für \verb|p| reserviert, ohne ihn wieder frei zu geben.
Nach Ende der Schleife ist keine der Adressen all dieser Reservierungen mehr verfügbar.
D.h. man kann den Speicher weder weiter benutzen, noch kann man ihn nachträglich frei geben.

\endinput