A2-dynamic.tex

\documentclass[alsotrans]{beamerswitch}
\usepackage{iprog}

\title{Динамична памет}

\date[20.12.2021--10.01.2022]{20 декември 2021 г. -- 10 януари 2022 г.}

\usetikzlibrary{arrows.meta}

\tikzset{
  l/.style={-{Stealth}},
  n/.style={
    rectangle,
    minimum width=3ex,
    minimum height=1em,
    text height=0.75em,
    text depth=0.25em,
    fill=diagramblue,
    draw},
  cell/.style={n,very thick},
  m/.style={
    matrix of nodes,
    ampersand replacement=\&,
    nodes=n,
    nodes in empty cells,
    column sep=-\pgflinewidth
  }
}

\begin{document}

\begin{frame}
  \titlepage
\end{frame}

\section{Програмен стек}

\begin{frame}
  \frametitle{Схема на програмната памет}

  \tikzset{
      m/.style={
      matrix of nodes,
      nodes={
        rectangle,
        minimum width=25ex,
        minimum height=2.5em
        }
    }
  }

  \begin{center}
    \begin{tikzpicture}
      \matrix (a) [m] {
        \ldots \\
        |[minimum height=5em,fill=diagramnavy]| Програмен стек \\
        |[fill=diagramnavy]| Статични данни \\
        |[fill=diagramblue]| Програмен код \\
        \ldots \\
      };
      \foreach\x in {east,west} { \draw (a-1-1.north \x) -- (a-5-1.south \x); }
      \foreach\x in {2,...,5} { \draw (a-\x-1.north west) -- (a-\x-1.north east); }
    \end{tikzpicture}
  \end{center}
\end{frame}

\begin{frame}
  \frametitle{Програмен стек}

  \tikzset{
      l/.style={-{Stealth[length=1.5ex]}},
      m/.style={
      matrix of nodes,
      nodes={
        rectangle,
        minimum width=25ex,
        minimum height=2em,
        fill=diagramblue,
        draw=black
      },
      nodes in empty cells
    }
  }

  \begin{center}
    \begin{tikzpicture}
        \matrix (a) [m] {
          |(sborder) [minimum height = 8em]| \ldots \\
          |(stop)|
          данни \\
          данни \\
          данни \\
          |(sbottom)|
          данни \\
        };
        \arrowto{sbottom.south west}{дъно на стека}{above left}
        \arrowto{stop.north east}{връх на стека}{below right}
        \arrowto{sborder.north east}{граница на стека}{below right}
    \end{tikzpicture}
  \end{center}
\end{frame}

\begin{frame}
  \frametitle{Свойства на програмния стек}

  \begin{itemize}[<+->]
  \item Паметта се заделя в момента на дефиниция
  \item Всеки заделен блок памет носи името на променливата
  \item Паметта се освобождава при изход от блока (или функцията), в който е дефинирана променливата
  \item Последно заделената памет се освобождава първа
  \item Програмистът \alert{няма контрол} над управлението на паметта
    \begin{itemize}
    \item Паметта не може да се освободи по-рано (преди края на блока)
    \item Паметта не може да се запази за по-дълго (след края на блока)
    \end{itemize}
  \item Количеството заделена памет до голяма степен е определено по време на компилация
    \begin{itemize}
    \item При какви случаи заделената памет може да варира по време на изпълнение?
    \end{itemize}
  \end{itemize}
\end{frame}

\section{Динамична памет}

\begin{frame}
  \frametitle{Област за динамична памет (heap)}

  \begin{itemize}[<+->]
  \item Динамичната памет може да бъде заделена и освободена по всяко време на изпълнение на програмата
  \item Областта за динамична памет е набор от свободни блокове памет
  \item Програмата може да заяви блок с произволна големина
  \item Операционната система се грижи за управлението на динамичната памет
    \begin{itemize}
    \item поддържа ``карта'' кои клетки са свободни и кои заети
    \item контролира коя част от паметта от коя програма се използва (защитен режим)
    \item позволява използването на външни носители (виртуална памет)
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Схема на динамичната памет}

  \small
  \begin{center}
    \begin{tikzpicture}[->,>=Stealth]
      \matrix [m] {
        \ldots \& \& \& \& \&
        |[cell,minimum width=12ex] (d) | \tt{12.3456}
        \& \&
        |[cell,minimum width=12ex] (s) | \tt{"abcd"}
        \& \&
        |[minimum width=6ex] (i1) | \tt{130}
        \&
        |[minimum width=6ex] (i2)| \tt{62}
        \& \& \& \& \ldots\\
      };
      \draw[very thick] (i1.north west) rectangle (i2.south east);
      \arrowto{d.south west}{}{below}
      \arrowto{s.north west}{}{above}
      \arrowto{i1.south west}{}{below}
    \end{tikzpicture}
  \end{center}
\end{frame}

\begin{frame}
  \frametitle{Заделяне на динамична памет}

  \begin{itemize}[<+->]
  \item Заделянето на динамична памет става с операциите \tta{new} и \tta{new[]}
  \item \tta{new} <тип> --- заделя блок от памет за една променлива от <тип>
  \item \tta{new} <тип>\tta[<брой>\tta] --- заделя блок от памет за масив от <брой> елемента от <тип>
  \item \tta{new} <тип>\tta(<инициализация>\tta) --- заделя блок от памет за една променлива от <тип> и я инициализира със зададените един или повече параметри
  \item връща указател <тип>\tt * към новозаделения блок
  \end{itemize}
\end{frame}

\begin{frame}[fragile]
  \frametitle{Примери за заделяне}

  \small
  \begin{columns}[T,onlytextwidth]
    \begin{column}{.48\textwidth}
      \begin{itemize}[<+->]
        \setlength\itemsep{5ex}
      \item \lst{int* p = new int;}
      \item \lst{float* q = new float(1.2);}
      \item \lst{char* s = new char[6];}\\
        \lst{strcpy(s, "hello");}
      \item \lst{char** ss = new char*(s);}
      \end{itemize}
    \end{column}
    \begin{column}{.52\textwidth}
      \begin{overlayarea}{\textwidth}{38ex}
        \begin{onlyenv}<1->
          \begin{tikzpicture}
            \node (p) [n,label=p] {};
            \matrix [m,right=of p] { \ldots \& |(pc) [minimum width=15ex]| {\tt{?}} \& \ldots \\ };
            \draw[l] (p.center) to [bend left=40] (pc.north west);
          \end{tikzpicture}
        \end{onlyenv}
        \begin{onlyenv}<2->
          \begin{tikzpicture}
            \node (q) [n,label=q] {};
            \matrix [m,right=of q] { \ldots \& |(qc) [minimum width=18ex]| {\tt{1.2}} \& \ldots \\ };
            \draw[l] (q.center) to [bend left=40] (qc.north west);
          \end{tikzpicture}
        \end{onlyenv}
        \begin{onlyenv}<3 |trans:0>
          \begin{tikzpicture}
            \node (s) [n,label=s] {};
            \matrix (a) [m,right=of s] { \ldots \& |(sc)| \tt{h} \& \tt{e} \& \tt{l} \& \tt{l} \& \tt{o} \& \tt{\textbackslash0} \& \ldots \\ };
            \draw[l] (s.center) to [bend left=40] (sc.north west);
          \end{tikzpicture}
        \end{onlyenv}
        \begin{onlyenv}<4>
          \begin{tikzpicture}
            \node (s) [n,label=s] {};
            \matrix (a) [m,right=of s] { \ldots \& |(sc)| \tt{h} \& \tt{e} \& \tt{l} \& \tt{l} \& \tt{o} \& \tt{\textbackslash0} \& \ldots \\ };
            \draw[l] (s.center) to [bend left=40] (sc.north west);
            \node (ss) [n,label=ss,below=of s] {};
            \matrix [m,right=of ss] { \ldots \& |(ssc) [minimum width=12ex]| \& \ldots \\ };
            \draw[l] (ss.center) to [bend left=40] (ssc.north west);
            \draw[l] (ssc.center) to (sc.south west);
          \end{tikzpicture}
        \end{onlyenv}
      \end{overlayarea}
  \end{column}
  \end{columns}
\end{frame}

\begin{frame}
  \frametitle{Освобождаване на памет}

  \begin{itemize}[<+->]
  \item Динамична памет се освобождава с операциите \tta{delete} и \tta{delete[]}
  \item \tta{delete} <указател> --- освобождава блок от памет с начало, сочено от <указател>
  \item \tta{delete[]} <указател> --- освобождава блок от памет, съдържащ масив от обекти, първият от които е сочен от <указател>
    \begin{itemize}
    \item в квадратните скоби не се указва размер, понеже операционната система ``знае'' колко е голям заделения блок
    \end{itemize}
  \end{itemize}
\end{frame}

\section{Особености на работа с динамична памет}

\begin{frame}[fragile]
  \frametitle{Ограничения при освобождаването на памет}

  \begin{itemize}[<+->]
  \item На \lst{delete} може да се подаде само указател, върнат от \lst{new}
  \item Не е позволено освобождаването на памет в програмния стек или областта за програмен код
    \begin{itemize}
    \item \lst{int x; int* p = &x;} ... \sta{delete p;}
%    \item \lst{double (*op)(double) = sin;} ... \sta{delete op;}
%    \item \sta{delete sin; delete main;}
    \end{itemize}
  \item Не е позволено частично освобождаване на памет
    \begin{itemize}
    \item \lst{int* a = new int[10];} ... \sta{delete (a+2);}
    \end{itemize}
  \item Не е позволено използването на памет след като е освободена
  \item Не е позволено повторното освобождаване на една и съща памет
    \begin{itemize}
    \item \lst{int* p = new int[5],*q = p;} \lst{delete p; }\sta{q[1] = 5; delete q;}
    \end{itemize}
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Задачи за динамична памет}

  \begin{enumerate}[<+->]
  \item Да се напише програма, която въвежда няколко положителни дробни числа в динамичната памет и намира средното им аритметично
  \item Да се напише програма, която създава матрица от числа в динамичната памет и я транспонира
  \end{enumerate}
\end{frame}

\begin{frame}
  \frametitle{Особености на динамичната памет}

  \begin{itemize}[<+->]
  \item Програмистът има контрол над заделянето на памет
  \item Програмистът носи отговорност за правилната работа с динамичната памет
  \item Заделената динамична памет остава непокътната до освобождаването ѝ с \lst{delete} или до завършване на програмата
  \item След приключване на програмата, цялата заделена от нея памет се освобождава от операционната система
  \item Честото заделяне и освобождаване на малки блокове памет води до \textbf{фрагментация}
    \begin{center}
      \small
      \begin{tikzpicture}
        \matrix (a) [m] {
          \ldots \& \& \&
          |[cell,minimum width=6ex]|
          \& \& \&
          |[cell,minimum width=6ex]|
          \& \& \& \& \&
          |[cell,minimum width=6ex]|
          \& \& \& \&
          |[cell,minimum width=6ex]|
          \& \& \ldots\\
        };
      \end{tikzpicture}
    \end{center}
  \item Динамично заделените блокове памет не се свързват с имена
  \end{itemize}
\end{frame}

\begin{frame}
  \frametitle{Грешки при работа с динамична памет}

  \begin{itemize}[<+->]
  \item Работа с указател към незаделена или освободена памет
  \item Освобождаване на непозволена памет
  \item ``Загубване'' на указател към заделена памет
  \item Неосвобождаване на неизползвана памет
  \item Изтичане на памет (memory leak)
  \end{itemize}
\end{frame}

\end{document}