\newpage

\section{De Geheugenhiërarchie}

%-----------
%Ruben
%-----------
\subsectionauthor[R. van den Berge]{Introductie}

Programmeurs willen het liefst onbeperkt snel geheugen tot hun beschikking hebben. De onderwerpen van dit hoofdstuk beschrijven de illusie dat computers dat daadwerkelijk hebben. Hiervoor geldt het principe van geheugennabijheid (\textit{principle of locality}). Voor dit principe is het belangrijk dat bij het uitvoeren van een programma niet alle data of code tegelijk opgehaald moet worden. Anders zou het onmogelijk zijn om geheugen snel te maken en alsnog groot te houden. Het is dus de bedoeling dat er bij uitvoer van een programma elke keer maar een relatief klein deel van het geheugen op te vragen.  \\

Er zijn twee types geheugennabijheid:
\begin{itemize}
\item \textbf{Tijdelijke geheugennabijheid}: Dit principe stelt dat als een datalocatie is aangeroepen, dat het waarschijnlijk is dat deze locatie redelijk snel weer aangeroepen moet worden.
\item \textbf{Ruimtelijke geheugennabijheid}: Dit principe stelt dat als een datalocatie is aangeroepen, dat datalocaties in de buurt van die locatie waarschijnlijk snel aangeroepen moeten worden.
\end{itemize} 


\noindent Veel programma's gebruiken loops, wat resulteert in een hoog aantal tijdelijk plaatsgeheugen. Omdat instructies normaal gesproken achtereenvolgend opgevraagd worden, resulteert dit ook weer in een hoog aantal ruimtelijk plaatsgeheugen. Bijvoorbeeld bij elementen uit een array wordt er gebruik gemaakt van ruimtelijke geheugennabijheid 

We profiteren van het principe van plaatsgeheugen door een \textbf{geheugenhiërarchie}. Deze bestaat uit lagen van verschillende groottes en snelheden van geheugen. Het snellere geheugen is duurder dan het langzamere en daardoor kleiner. Het doel is om met zo veel mogelijk goedkoop geheugen zo snel als het snelste geheugen te werken. Data heeft een soortgelijke hiërarchie, hoe verder van de processor verwijderd, hoe langzamer. Data is het verst van de processor opgeslagen en wordt dus dichterbij de processor gehouden op het moment dat het nodig is. 

\begin{center}
\includegraphics[width=0.75\textwidth]{5_2.png}
\end{center}

\noindent Een data-hiërarchie werkt met twee lagen tegelijkertijd, dus we focussen ons op twee lagen. De bovenste laag is sneller dan de onderste en ligt dichter bij de processor. Het minimum aan informatie dat aanwezig of niet aanwezig kan zijn in de tweelaagse hiërarchie heet een \textbf{blok (\textit{block})} of een \textbf{regel (\textit{line})}. Als opgevraagde data zich bevindt in de bovenste laag heet dit een \textbf{\textit{hit}}, als dit niet zo is heet het een \textbf{\textit{miss}}. Bij een miss wordt de onderste laag ingeschakeld om de opgevraagde data op te halen.

\begin{center}
\includegraphics[width=0.75\textwidth]{5_1.png}
\end{center}

\noindent De \textbf{\textit{hit rate}} is de kans op een hit in de bovenste laag. De \textbf{\textit{miss rate}} ($1 - hit rate$) is de kans op een miss. \textbf{\textit{Hit time}} is de tijd die nodig is om de bovenste laag te checken voor een hit. De \textbf{\textit{miss penalty}} is de tijd die nodig is om bij een miss een blok uit de bovenste laag te vervangen door het desbetreffende blok uit de onderste laag. Voor een goede performance moeten de \textit{hit rate} en \textit{hit time} goed genoeg zijn om te compenseren voor de \textit{miss penalties} die plaatsvinden.

\subsectionauthor[R. van den Berge]{Geheugen Technologieën}

Er zijn vier primaire technologieën in de geheugenhiërarchieën:
\begin{itemize}
\item \textbf{SRAM technologie}:\\
SRAMs zijn geïntegreerde circuits die geheugenreeksen zijn met een enkele toegangspoort die een \textit{read} of \textit{write} kan uitvoeren. SRAMs hoeven niet ververst te worden dus is de tijd om het te gebruiken bijna gelijk aan de \textit{cycle} tijd. SRAM heeft maar een minimaal aantal energie nodig om zijn data te bewaren in stand by mode. Zolang er stroom op zit wordt de data bewaard. SRAM gebruikt 6 tot 8 transistors per bit om te voorkomen dat de informatie wordt verstoord. 
\item \textbf{DRAM technologie}:\\
De waarden van data op DRAM worden bewaard in een condensator. Een enkele transistor wordt vervolgens gebruikt om deze data te lezen of te overschrijven. Omdat er hier maar één transistor wordt gebruikt is de dichtheid van DRAM veel hoger dan SRAM en daardoor dus goedkoper. Omdat DRAMs de data opslaan op een condensator moet de data om de zoveel tijd ververst worden. Om dit te doen wordt de data gelezen en opnieuw opgeslagen. Dit gebeurt om de ~8 milliseconden. Hiervoor wordt een tweelaagse codeer structuur gebruikt, waardoor een hele rij aan data ververst kan worden.
\item \textbf{Flashgeheugen}: \\
Flash type is een EEPROM (\textit{electrically erasable programmable read-only memory}) memory type. De naam \textit{flash} komt doordat het geheugen in een keer deels of volledig verwijderd kan worden om er iets nieuws in te op te slaan. Dit wordt gebruikt voor o.a. USB-sticks. 
\item \textbf{Schijfgeheugen}: \\
Een magnetische harde schijf bestaat uit allemaal hele dunne metalen platen, die draaien met van 5400 tot 15000 RPM. Deze metalen platen zijn bedekt met magnetisch materiaal om dingen op te slaan. Het oppervlak van zo'n cirkel is onderverdeeld in \textbf{\textit{tracks}}, dit zijn concentrische cirkels die met tienduizenden het oppervlak vormen. \textbf{Sectoren} is de minimale data die opgeslagen of gelezen kan worden (normaal gesproken 512 - 4096 bytes). 

De performance hangt af van 3 stappen:
\begin{itemize}
\item \textbf{\textit{Seek}}:\\
Dit is het plaatsen van de leesnaald van de schijven boven de juiste datalocatie.
\item \textbf{\textit{Rotational delay}}:\\
Er moet worden gewacht tot de sector van de data op de schijf onder de naald gedraaid is. Gemiddelde rotational delay = $\frac{0.5 rotation}{rotations per second}$
\item \textbf{\textit{Transfer time}}:\\
De \textit{transfer time} is de tijd voor het verplaatsen van een blok bits.  
\end{itemize}
\end{itemize}

\subsectionauthor[R. van den Berge]{De basis van caches}

De cache is een plek om veilig dingen op te slaan. Er zijn bij het kijken of het opgevraagde item al aanwezig is in de cache twee vragen: \begin{itemize}
\item Hoe weten we of het item al aanwezig is in de cache? 
\item En zo ja, hoe vinden we die?
\end{itemize}

\noindent De antwoorden op de vragen hangen samen. Als een \textit{word} maar op één plek in de cache opgeslagen kan worden, dan is het heel makkelijk deze ook weer terug te vinden. De locatie waar de \textit{word} wordt opgeslagen is gebaseerd op het adres van de \textit{word}. Deze structuur heet \textbf{\textit{direct mapped}}. De bijna alle \textit{direct-mapped caches} gebruiken de volgende \textit{mapping}
om een blok te vinden:
\begin{itemize}
\item (Blok adres) modulo (het aantal blokken in de cache).
\end{itemize}

\begin{center}
\includegraphics[width=0.75\textwidth]{5_3.png}
\end{center}

\noindent Als het aantal blokken in een cache een macht van twee is, bijvoorbeeld 16, dan gebruikt de cache de laagste $\log_2 16 = 4$ bits van een blok voor het adres. Omdat hierdoor nu bij een adres in de cache meerdere dingen aanwezig kunnen zijn, kunnen we de juiste data vinden door middel van \textbf{\textit{tags}}. Om te kijken of een cache leeg is gebruik je een \textbf{\textit{valid bit}}. Als deze 1 is, dan is de data aanwezig. 0 betekent niet aanwezig.

Er moet een balans worden gevonden tussen de blok grootte en de hoeveelheid blokken in de cache. Als de blok grootte te groot wordt gaat de \textit{miss rate} omhoog omdat er dan minder blokken in de cache kunnen. 

\begin{center}
\includegraphics[width=0.75\textwidth]{5_4.png}
\end{center}

\noindent Bij een cache miss wordt de CPU pijplijn uitgesteld. Hierna wordt het blok uit de memory geladen en in de cache opgeslagen. Als data vanuit het geheugen alleen in de cache wordt opgeslagen, dan staat er na een tijd andere data in de cache dan in het geheugen (inconsistente data). Hierdoor moet dezelfde data in de cache én het geheugen worden aangepast, waardoor de data weer consistent wordt. Dit heet \textbf{\textit{write-through}}. 

Als dit elke keer moet gebeuren dat er data verandert kost dit veel tijd. Een oplossing hiervoor is een \textbf{\textit{write buffer}}. Dit is een rij aan (aangepaste) data die wacht tot hij kan worden opgeslagen in het geheugen.

Een alternatief voor een \textit{write-through} is een \textbf{\textit{write-back}}. Hier wordt data alleen aangepast in het blok in de cache. Op het moment dat het blok uit de cache wordt gehaald, wordt de data in het geheugen overschreven.

\subsectionauthor[R. van den Berge]{Het meten en verbeteren van cache performance}

De cache performance hangt van een aantal dingen af:
\begin{itemize}
\item $CPU\ time = (CPU\ execution\ clock\ cycles + Memory\mhyphen stall\ clock\ cycles) \cdot Clock\ cycle\ time$ 
\item $Memory\mhyphen stall\ clock\ cycles = \frac{Memory accesses}{Program} \cdot miss\ rate \cdot Read\ miss\ penalty\\
= \frac{Instructions}{program} \cdot \frac{Misses}{Instruction} \cdot Miss\ penalty$ 
\item $Memory\mhyphen stall\ clock\ cycles = (Read\mhyphen stall\ cycles + Write\mhyphen stall\ cycles)$
\begin{itemize}
\item$Read\mhyphen stall\ cycles = \frac{Reads}{Program} \cdot Read\ miss\ rate \cdot Read\ miss\ penalty$
\item$Write\mhyphen stall\ cycles = \left(\frac{Writes}{Program} \cdot Write\ miss\ rate \cdot Write\ miss\ penalty \right) + Write\ bu$\textit{ff}$er\ stalls$
\end{itemize}
\item $AMAT\ (\textit{average\ memory\ access\ time}) = Time\ for\ a\ hit + Miss\ rate \cdot Miss\ penalty$
\end{itemize}

\noindent Om de cache performance te verbeteren kun je een aantal dingen doen: 

\begin{itemize}
\item De \textit{hit time} verlagen door:
\begin{itemize}
\item Kleinere cache
\item \textit{Direct mapped} cache
\item Kleinere blokken
\item \textit{Write buffers} gebruiken
\end{itemize}

\item De \textit{miss rate}  verlagen door:
\begin{itemize}
\item Grotere cache
\item Flexibelere plaatsing (\textit{associativity} gebruiken)
\item Grotere blokken
\item Een 'slachtoffer' cache gebruiken om de meest recent weggegooide cache blokken in op te slaan.
\end{itemize}

\item De \textit{miss penalty} verlagen door:
\begin{itemize}
\item Kleinere blokken
\item \textit{Write buffers} gebruiken
\item De \textit{write buffer} bekijken bij een miss, misschien zit het daar wel in voordat je naar het geheugen gaat
\item Bij grotere blokken kijken naar het belangrijkste \textit{word}
\item Meerdere cache lagen gebruiken die niet gebonden zijn aan \textit{clock rate}
\item Bandbreedte van geheugen verbeteren.
\end{itemize}
\end{itemize}

\noindent \textit{Direct mapped} cache had dus maar één adres om blokken in op te slaan. Bij een \textbf{\textit{fully associative}} cache kunnen blokken op elke plek worden opgeslagen. Hierbij moet dus wel elk blok afgezocht worden voor een hit, omdat blokken op elke plek kunnen worden opgeslagen. Een middenweg is \textbf{\textit{set associative}}. Bij een \textit{set associative} cache is er een aantal locaties waar een blok geplaatst kan worden. Een \textit{set-associative} kan een \textit{n} aantal sets hebben. Deze bestaan ook weer uit een \textit{n} aantal blokken. Blokken worden dus gekoppeld aan een set, en daarin kan een blok dus op elke plek worden opgeslagen. Hierbij geldt de dat de set waarin een blok is opgeslagen gevonden kan worden door
\begin{itemize}
\item (Blok nummer) modulo (aantal sets in de cache)
\end{itemize}

\begin{center}
\includegraphics[width=0.75\textwidth]{5_5.png}
\end{center}

\noindent Dus, bij \textit{fully associative} moeten alle tags worden afgezocht, en bij \textit{set associative} slechts alle tags binnen een set. Bij het vervangen van een blok wordt de \textbf{LRU (\textit{least recently used})} vervangen. De computer kijkt dus welk blok relatief het minst belangrijk is en vervangt deze op het moment dat dat nodig is.

%-----------
%Robin
%-----------

\subsectionauthor[R.A.J. Wacanno]{Virtueel Geheugen}

Nu de bovenste lagen van de geheugenhiërarchie uitvoering behandeld zijn, is het ook van belang om te bespreken hoe de onderste lagen van deze piramide geoptimaliseerd kunnen worden om zo tot de gewenste prestaties van een architectuur te komen. 

Een principe welke een cruciale rol speelt bij het \textit{RAM (Random Access Memory)} en de secundaire opslag, in de vorm van een \textit{SSD}- (\textit{Solid State Drive}) of harde schijf, is die van het \textbf{virtuele geheugen}. Dit virtuele geheugen is in de loop der tijd tot stand gekomen ter oplossing van de volgende problematiek:

\begin{itemize}
\item \textbf{Het veilig delen van het geheugen tussen verschillende processen}

Tijdens het schrijven en compileren van een programma kan niet voorspeld worden met welke programma's het bij het uitvoeren het geheugen zal moeten delen. Sterker nog, zelfs tijdens het draaien van het programma kunnen deze omstandigheden sterk veranderen. 

Om dit soort situaties te voorkomen stelt het virtuele geheugen de individuele programma's in staat een eigen \textbf{adresseringsruimte} te benutten. Het virtuele geheugen draagt zorg voor het omzetten van locaties binnen deze adresseringsruimte naar \textbf{fysieke geheugenadressen}.

\item \textbf{Het oplossen van problematiek als gevolg van een gelimiteerde hoeveelheid geheugen}

Dikwijls komt het voor dat een programma meer geheugen nodig heeft---zij het voor data, zij het voor instructies---dan dat er binnen het systeem beschikbaar is. Ook hiervoor biedt het virtuele geheugen een oplossing. Het eerdergenoemde omzetten van geheugenadressen geldt namelijk niet alleen tussen virtuele en fysieke adressen, maar ook tussen \textbf{virtuele adressen} en adressen van secundaire opslagapparaten. Zo kan een draaiend programma dus niet alleen gebruikmaken van het RAM, maar ook van een naar alle waarschijnlijkheid aanwezige secundaire opslageenheid. 

\end{itemize}

\noindent Om het virtuele geheugen beter te kunnen begrijpen is het verstandig een aantal termen en hun bijbehorende definities te belichten. Allereerst is er de \textbf{pagina} (\textit{page}). Dit is een blok geheugen dat in het virtuele geheugen aanwezig is. Wanneer een pagina die is opgevraagd met behulp van een virtueel adres niet in het \textit{RAM} aanwezig is ontstaat er een \textbf{pagina-fout} (\textit{page fault}).\\

\noindent Een voorbeeld van het verbinden van een virtueel en een fysiek adres is in het onderstaande plaatje schematisch uitgebeeld:

\begin{center}
\includegraphics[width=0.75\textwidth]{figr5}
\end{center}

\noindent In het nu volgende plaatje is de opbouw van zowel virtuele als fysieke adressen en de tussenliggende omzetting geïllustreerd:

\begin{center}
\includegraphics[width=0.75\textwidth]{figr6}
\end{center}

\noindent Zoals te zien is, is het virtuele adres opgebouwd uit een \textbf{virtueel paginanummer} en een \textbf{pagina-afstand}. Het fysieke adres is opgebouwd uit een \textbf{fysiek paginanummer} en dezelfde pagina-afstand. 

Het is van belang het een en ander in beschouwing te nemen wanneer men kijkt naar dit figuur. Allereerst is aan de lengte van de paginanummers te zien dat het virtuele adres een groter pagina-adresseringsbereik heeft dan het fysieke adres. Dit spreekt voorzich, aangezien---zoals eerder gezegd---de adresseringsruimte groter kan zijn dan het geheugen dat in een systeem aanwezig is. Wanneer er een virtueel adres opgevraagd wordt die niet aan een locatie in het geheugen is gekoppeld zal deze dus uit de secundaire opslag geladen moeten worden (een pagina-fout). 

Dan is er ook te zien dat dat de pagina-afstand in beide adresvormen met elkaar correspondeert; hetgeen logisch is omdat pagina's in het virtuele en het fysieke geheugen dezelfde grootte hebben. Het is daarom dat deze nummers niet omgezet hoeven te worden en een locatie binnen een pagina in het virtuele en het fysieke geheugen met het zelfde pagina-afstandsnummer opgevraagd kan worden.\\

\noindent Bij het ontwerpen van een virtueel geheugensysteem zijn er een aantal zaken die in acht genomen moeten worden, aangezien het geheugen in sommige gevallen wel 100.000 maal sneller kan zijn dan de secundaire opslag en een pagina-fout dus zeer kostbaar kan zijn. 

\begin{itemize}

    \item Het loont om pagina's groot genoeg te maken zodat de lange opvragingstijd uit de secundaire opslag teniet wordt gedaan.

    \item Veelal worden pagina's volledig associatief geordend om de frequentie van pagina-fouten te verminderen.

    \item Pagina-fouten kunnen door de \textit{software} worden afgehandeld omdat de tijd die dit kost niet significant is vergeleken met de tijd die het kost om de betreffende pagina uit de secundaire opslag te laden. Ook is \textit{software} in staat om pagina's dusdanig te ordenen om zo de kans op pagina-fouten te verminderen.

    \item Omdat het schrijven naar de secundaire opslag te lang duurt maakt virtueel geheugen gebruik van \textit{write-back} in plaats van \textit{write-through}.

\end{itemize}

\subsubsection{Het Plaatsen en Vinden van Pagina's}

Het omzetten van de virtuele naar fysieke adressen gebeurt met behulp van de \textbf{pagina-tabel} (\textit{page table}). Dit is een stuk geheugen dat geïndexeerd is op basis van de virtuele pagina-nummers. Deze index is vervolgens gekoppeld aan het corresponderende fysieke pagina-nummer. Ieder programma bezit zijn eigen pagina-tabel en deze is bij uitvoer te vinden dankzij het \textbf{pagina-tabelregister}. Dit register wijst naar het begin van de desbetreffende pagina-tabel. 

\begin{center}
\includegraphics[width=0.75\textwidth]{figr7}
\end{center}

\noindent Het bovenstaande figuur toont de eerder geziene omzetting van virtuele naar fysieke adressen, maar nu is hier de pagina-tabel en het pagina-tabelregister aan toegevoegd. Ook is hierin de zogenaamde \textit{\textbf{valid bit}} weergeven. Deze bit geeft aan of de met het fysieke pagina-nummer corresponderende pagina in het geheugen aanwezig is. Wanneer deze bit 1 is, is dit het geval. Indien deze 0 is, zal er een pagina-fout optreden. 

\subsubsection{Pagina-fouten in Detail}

Bij het omgaan met pagina-fouten is de centrale rol van het \textbf{besturingssysteem} goed te zien. Wanneer een dergelijke fout namelijk optreed is het de taak van het besturingssysteem om dit in goed banen te leiden. Het besturingssysteem laad de gewenste pagina uit het geheugen maar kan dit niet alleen met het virtuele adres.

Wanneer een programma wordt gestart, maakt het besturingssysteem een \textbf{\textit{swap space}} aan in de secundaire opslag waarin alle pagina's van het programma kunnen staan. Tevens houdt het besturingssysteem bij welke virtuele adressen naar welke locaties in deze \textit{swap space} verwijzen. Dit alles is in het onderstaande figuur weergegeven:

\begin{center}
\includegraphics[width=0.75\textwidth]{figr8}
\end{center}

\noindent Ook registreert het besturingssysteem welke processen en virtuele adressen aan welke fysieke adressen gekoppeld zijn.\\

\noindent Het kan zo nu en dan voorkomen dat het geheugen vol is, maar er voor een bepaald proces toch een pagina uit de secundaire opslag geladen moet worden. In dat geval zal het besturingssysteem op basis van principe van het \textbf{minst recent gebruikte} (\textit{LRU}) een pagina vervangen. Het idee hierachter is dat op deze manier de kans op een pagina-fout geminimaliseerd wordt.


\subsubsection{Terugschrijven naar Secundaire Opslag}

Zoals eerder gezegd baseert het virtuele geheugen het schrijven naar secundair geheugen niet op een \textbf{\textit{write-through}} maar op een \textit{\textbf{write-back}}. Dit betekend dat dat iedere individuele pagina-aanpassing naar het geheugen geschreven wordt en de desbetreffende pagina naar de secundaire opslag wordt gekopieerd wanneer deze in het geheugen wordt vervangen door een andere pagina.

\subsubsection{Versnelling van Adresomzetting}

Aangezien het opvragen van data uit een pagina op basis van het geheugen tweemaal de opvragingstijd van het geheugen kost---omdat zowel het fysieke adres als de data uit het geheugen moeten worden geladen---word in systemen gebruik gemaakt van een speciale \textit{cache} die dit proces versneld. Deze cache, onder de noemer \textbf{\textit{translation-lookaside buffer}} (\textit{TLB}), fungeert op basis van tijdelijke en ruimtelijke geheugennabijheid. Verondersteld wordt namelijk dat, wanneer een virtueel paginanummer is omgezet, de kans groot is dat deze pagina in de toekomst weer gebruikt zal worden

Bij het opvragen van data zal dus eerst in de \textit{TLB} worden gekeken. Om dit goed te laten verlopen zin naast de \textit{valid bit} nog een aantal andere controle-bits nodig. 

\begin{itemize}
\item \textbf{\textit{Dirty bit}}: Deze bit krijgt een waarde van 1 als er een schrijfactie plaatsvindt op de geheugenlocatie van dit adres. 

\item \textbf{Referentie-bit}: Deze bit krijgt een waarde van 1 als het desbetreffende adres in de \textit{TLB} aanwezig is.

\end{itemize}

In het figuur hieronder wordt deze samenhang weergegeven:

\begin{center}
\includegraphics[width=0.75\textwidth]{figr9}
\end{center}

\noindent Wanneer een adres in de \textit{TLB} wordt opgevraagd en deze is niet aanwezig is er sprake van een \textit{TLB miss} en dit kan twee oorzaken hebben:

\begin{itemize}
\item \textbf{Het adres mist enkel in de \textit{TLB}:} In dit geval wordt de processor aan het werk gezet om het missende adres alsnog in de \textit{TLB} te laden.

\item \textbf{Er is sprake van een pagina-fout:} Indien dit gebeurd is het---zoals eerder beschreven---de taak van het besturingssysteem om de pagina-fout af te handelen.

\end{itemize}

\subsubsection{Samenbrengen van Virtueel Geheugen, \textit{TLB} en Cache}

Uiteindelijk is het dan nog zaak om de hogere en de onderste lagen van de geheugenhiërarchie met elkaar te verenigen. Dit wordt in onderstaande afbeelding schematisch toegelicht:

\begin{center}
\includegraphics[width=0.9\textwidth]{figr10}
\end{center}
