Share Library (C++)

% \date{15. května 2007}
% \setyear{2007}
% \author{Kamil Dudka}
% \title{Knihovna pro~práci s~objekty ve~sdílené~paměti}
% \FITproject{BP}
 
\chapter{Úvod}
Sdílená paměť představuje efektivní nástroj pro meziprocesovou komunikaci, který je dostupný ve všech moderních operačních systémech. Využití nalézá při zpracování větších bloků dat (např. objemová obrazová data). V současnosti však neexistují efektivní a jednoduché nástroje pro její využití v C++. Předmětem této práce je návrh a implementace knihovny, která tento nedostatek řeší.
 
Kapitola \ref{theory} obsahuje informace o meziprocesorové komunikaci v obecné rovině, jsou zde vysvětleny základní technické pojmy, se kterými návrh knihovny pracuje. Kapitola \ref{stateOfArt} popisuje současný stav operačních systémů, překladačů a dostupných knihoven z hlediska práce se sdílenou pamětí. V kapitole \ref{design} je vysvětlen návrh knihovny v několika krocích -- zejména jsou zde popsány a zdůvodněny jednotlivé části rozhraní knihovny. Kapitola \ref{implementation} shrnuje implementaci knihovny a popisuje některé zajímavé implementační detaily. Experi\-menty s knihovnou a jejich výsledky jsou uvedeny v kapitole \ref{results}.
 
Neodmyslitelnou pomůckou při práci s knihovnou je dokumentace knihovního API (\textit{Appli\-cation Programming Interface}), která se nachází na přiloženém CD. V příloze \ref{samples} se nachází ukázka zrojového kódu, který s knihovnou pracuje.
 
\vfill\hfill {\footnotesize Tento dokument byl vysázen systémem \LaTeX.}
 
\chapter{Teoretická část}\label{theory}
V této kapitole jsou vysvětleny problémy, které vznikají při komunikaci procesů, a jejich možná řešení. Dále je představena sdílená paměť jako prostředek meziprocesorové komunikace, jsou zmíněny její výhody a nevýhody. Jde však pouze o přehled a seznámení čtenáře s použitou terminologií. Přesné definice jednotlivých pojmů je možné najít v odkazované literatuře.
 
\section{Správa procesů v moderních OS}\label{process}
\textit{Proces} je abstrakce definovaná operačním systémem (OS), která představuje program zavedený do paměti. Operační systém poskytuje procesu prostředky (procesor, paměť, ...) k~tomu, aby mohl vykonávat potřebnou práci. Moderní OS umožňují spouštět více procesů současně, podporují tzv. multi-tasking. Aby mohly procesy běžet na jednom stroji nezávisle na sobě, snaží se je operační systém co nejvíc oddělit od sebe. Pokud například jeden proces havaruje, nechceme, aby jeho havárie negativně ovlivnila ostatní procesy běžící na stroji.
 
Správu procesů zajišťuje jádro operačního systému, zejména jeho části \textit{plánovač} a~\textit{správ\-ce virtuální paměti}. Tyto mechanismy jsou pro proces zcela transparentní. Proces samotný se~chová, jako by měl celý procesor pro sebe. Stejně tak ve svém adresovém prostoru nemůže číst data ostatních procesů běžících na stroji.
 
Na jednom procesoru může v jednom čase běžet pouze jeden proces. Procesorů máme však omezený počet, často jich máme méně než současně běžících procesů. Procesy potom běží \textit{pseudoparalelně} -- dochází k jejich přepínání na jednom procesoru. Spolu s přepínáním procesů se musí přepínat \textit{kontext procesu}. Kontext procesu představuje stavové informace procesoru (nejčastěji množinu registrů procesoru, která je přístupná uživatelskému procesu\footnote{Kromě těchto registrů obsahují procesory také registry, které jsou dostupné pouze v privilegovaném režimu. O obsah těchto registrů se stará výhradně OS. Více informací najdete např. v \cite{IA32}}). Přepínání kontextu zajišťuje plánovač. Více o činnosti plánovače si můžete přečíst např. v \cite{IOS}.
 
% TODO: Správce virtuální paměti, adresový prostor procesu
 
\section{Větvení procesů}
Pokud v jednom programu potřebujeme využívat funkcionalitu jiného programu, máme dvě možnosti, jak to udělat:
\begin{itemize}
 \item Budeme volat program nebo jeho část v rámci jednoho procesu.
 \item Požádáme OS o vytvoření nového procesu a v něm program spustíme.
\end{itemize}
 
Obě varianty mají své výhody i nevýhody. Výhoda první varianty spočívá v její jednoduchosti. Volající program se pozastaví na dobu běhu volaného programu. Nemusíme se tedy zabývat synchronizací procesů -- to je dáno už tím, že máme ve skutečnosti proces jenom jeden. Oba programy budou také sdílet stejný adresový prostor.
% Nabízí se otázka, je-li to výhoda či nevýhoda. Pokud volaný program havaruje, může poškodit i data volajícího programu. Tak jako tak bude při havárii celý proces ukončen a jeho data (aspoň pro uživatele) ztracena.
 
Pokud vytvoříme nový proces, poběží oba programy paralelně\footnote{Na stroji s jedním procesorem poběží pseudoparalelně, na stroji s více procesory mohou běžet skutečně paralelně.}. Každý proces bude mít svůj oddělený adresový prostor. Havárie jednoho procesu nemusí nutně znamenat havárii druhého. Tento způsob vyžaduje nějakou práci navíc při vývoji aplikace a také nějakou režii při běhu. Moderní aplikace se však bez větvení procesů neobejdou.
 
Takový přístup se často používá např. u GUI aplikací, které umožňují komunikovat s~uživatelem během provádění časově náročné operace.
% Jako příklad bych uvedl aplikaci typu bitmapový editor.
% 
% TODO obrázek
% 
% TODO dva scénáře
 
\section{Meziprocesorová komunikace}
Jak bylo uvedeno v kapitole \ref{process}, procesy jsou od sebe zcela oddělené. Každý proces pracuje se svým kontextem a se svým adresovým prostorem. Přesto však někdy potřebujeme, aby spolu procesy komunikovaly -- pracovaly nad společnými daty, nebo aby jeden proces informoval druhý o průběhu výpočtu, apod.
 
Operační systémy umožňují otevřít jeden soubor více procesy -- je tedy možné komunikovat přes běžný soubor nacházející se někde na disku. Možnosti práce se souborem jsou však omezené, navíc některé OS mají problémy se sdílením souborů více procesy.
 
Naštěstí soubor na disku není jediný prostředek, pomocí kterého mohou procesy komunikovat. OS nabízí k tomuto účelu celou řadu mechanismů. Souhrnně se tyto mechanismy nazývají \textit{IPC (Inter Process Comunication)}. Následuje přehled těch nejpoužívanějších:
\begin{itemize}
 \item roury -- pojmenované/anonymní
 \item signály
 \item zprávy
 \item sockety
 \item Remote Procedure Call (RPC)
 \item Sdílená paměť
\end{itemize}
 
Ke každému způsobu komunikace je možné najít celou řadu příkladů použití. Některé druhy IPC jsou specifické pro konkrétní OS. Například signály se používají na Linuxu pro~synchronizaci a plánování procesů. Zprávy používá systém Microsoft Windows pro~komunikaci mezi GUI aplikacemi. Sockety a RPC jsou zase typické pro aplikace orientované na komunikaci přes síť. Na obrázku \ref{pipe_diagram} je znázorněno použití anonymní roury, nevýhoda této metody spočívá v sekvenčním přístupu k datům.
 
\begin{figure}[h]
  \begin{center}\includegraphics[scale=0.5]{img/pipe.png}\end{center}
  \caption{Použití roury:  Kolona procesů \texttt{ls | grep .c | wc} -- obrázek převzatý z \cite{upp}}\label{pipe_diagram}
\end{figure}
% Tato práce se zabývá komunikací přes sdílenou paměť.
 
\section{Sdílená paměť}
Při studiu sdílené paměti jsem čerpal z \cite{ALP}. Sdílená paměť je jedna z nejjednodušších IPC metod. Umožňuje dvěma nebo více procesům sdílet stejný kus paměti. Když jeden proces změní obsah paměti, všechny ostatní procesy změnu vidí.
 
Před použitím sdílené paměti musí nějaký proces alokovat segment sdílené paměti. Každý proces, který chce využívat přístup ke sdílenému segmentu, si jej potom musí připojit. Připojení spočívá v namapování sdíleného segmentu do adresového prostoru procesu\footnote{Sdílený segment se může v jednotlivých procesech mapovat na různé adresy. To je jeden z hlavních problémů, které bylo potřeba vyřešit při návrhu knihovny.}. Po~ukončení práce se sdíleným segmentem je potřeba, aby se každý proces odpojil od sdíleného segmentu. Nakonec musí být sdílený segment uvolněn.
\begin{figure}[h]
  \begin{center}\includegraphics[scale=0.3]{img/shm.png}\end{center}
  \caption{Sdílená paměť -- obrázek převzatý z \cite{upp}}
\end{figure}
 
Přístup ke sdílené paměti je stejně rychlý jako přístup k nesdílené paměti procesu. Jakmile je sdílená paměť namapována do adresového prostoru procesu, není už dále potřeba volat služby OS pro přístup k paměti. Tím se můžeme vyhnout nadbytečnému kopírování dat z paměti do paměti (nebo na jiné úložiště).
 
Operační systém Microsoft Windows nabízí jako alternativu ke sdílené paměti \textit{soubor mapovaný do paměti}\footnote{Mapování souboru do paměti nabízí také Linux, v knihovně však byla použita sdílená paměť.}. Práce se souborem mapovaným do paměti je podobná jako, kdybychom pracovali se segmentem sdílené paměti. Nějaký proces musí vytvořit mapování procesu do paměti. Každý proces, který chce využívat přístup k mapovanému souboru, se musí k~mapování připojit. Po~ukončení práce s mapovaným souborem se proces odpojí. Nakonec je potřeba mapování souboru zrušit. Tento přístup je obecnější než sdílená paměť -- kromě komunikace mezi procesy jej lze využít také pro přístup k běžným souborům operačního systému v rámci jednoho procesu.
 
Protože operační systém nesynchronizuje přístupy ke sdílené paměti, je potřeba provádět vlastní synchronizaci přístupu ke sdíleným datům mezi procesy. Například proces nesmí číst data ze sdílené paměti, která tam ještě nebyla zapsána. Stejně tak dva procesy nesmí psát do jednoho místa v paměti ve stejnou dobu. Operační systém nemá prostředky k tomu, aby tyto konflikty detekoval a může tak dojít k poškození sdílených dat. Použití \textit{semaforu}, které tento problém řeší, je probráno v následující kapitole.
 
% \bigskip
% Práce se sdílenou pamětí má následující výhody:
% \begin{itemize}
%  \item Umožňuje náhodný přístup ke sdíleným datům.
%  \item Má nízkou režii při práci s velkými objemy dat.
%  \item Její velikost je omezena jen volnou virtuální pamětí a limity nastavenými admini\-strátorem systému.
%  \item Přístup ke sdílené paměti je z pohledu překladače stejný jako k běžně alokované paměti -- vztahují se na něj tím pádem stejné optimalizace při překladu.
%  \item TODO
% \end{itemize}
% 
% \bigskip
% TODO: aplikace typu bitmapový editor, sdílená paměť, ...
 
\section{Semafory}\label{semaphores}
Popis práce se semafory v systému Linux najdete rovněž v \cite{ALP}. Semafor je synchronizační prostředek poskytovaný operačním systémem. Zapouzdřuje čítač typu \texttt{int}, který má vždy kladnou hodnotu a poskytuje dvě základní operace:
\begin{itemize}
 \item Operace \texttt{wait} sníží hodnotu čítače o 1. Pokud je již hodnota čítače nulová, proces je pozastaven dokud není hodnota opět kladná (v důsledku operace \texttt{signal} jiného procesu).
 \item Operace \texttt{signal} zvýší hodnotu čítače o 1. Pokud byla hodnota čítače nulová a jiný proces byl zablokován během volání \texttt{wait}, bude tímto voláním odblokován.
\end{itemize}
 
Operační systém zaručuje, že tyto operace jsou bezpečné vzhledem k současnému běhu procesů. Pomocí semaforů je tedy možné synchronizovat přístup k datům ve sdílené paměti, jak ukazuje obrázek \ref{semaphore_diagram}. Semafory je potřeba alokovat a dealokovat podobně jako sdílené segmenty.
 
\begin{figure}[h]
  \begin{center}\includegraphics[scale=0.5]{img/semaphore.png}\end{center}
  \caption{Sekvenční diagram běhu dvou procesů při použití semaforu}\label{semaphore_diagram}
\end{figure}
 
Semafory představují nízkoúrovňový synchronizační nástroj operačního systému. Pomocí semaforů lze řešit klasické synchronizační problémy, práce s nimi je však příliš složitá a proto se málokdy používají přímo. Existují různé abstrakce vybudované nad semafory, které řeší konkrétní situace. Synchronizačními problémy a jejich řešením se zabývá \cite{IOS}.
 
% citace??
\textit{Monitor} je abstraktní datový typ, který zapouzdřuje sdílená data. Nad sdílenými daty je možné v rámci monitoru implementovat určité operace, přičemž je zaručeno, že v jednom čase bude vždy rozpracována pouze jedna z těchto operací.
 
% \section{Algoritmy pro alokaci paměti}
% TODO: Přidat odkazy na literaturu
 
\section{Virtuální metody}\label{virtual}
Jazyk C++ má, stejně jako většina objektově orientovaných jazyků, podporu pro \textit{dynamický polymorfismus}\footnote{Kromě dynamického polymorfismu disponuje jazyk C++ také statickým polymorfismem ve formě šablon.}. Definice polymorfismu podle Wikipedie\cite{polymorphism}:
\begin{quote}
 Odkazovaný objekt se chová podle toho, jaký je jeho skutečný typ. Pokud několik objektů poskytuje stejné rozhraní, pracuje se s nimi stejným způsobem, ale jejich konkrétní chování se liší. V praxi se tato vlastnost projevuje např. tak, že na místo, kde je očekávána instance nějaké třídy, můžeme dosadit i instanci libovolné její podtřídy (třídy, která přímo či nepřímo z této třídy dědí), která se může chovat jinak, než by se chovala instance rodičovské třídy, ovšem v rámci mantinelů, daných popisem rozhraní.
\end{quote} 
Dynamický polymorfismus je v C++ realizován pomocí \textit{virtuálních metod}. Virtuální metody jsou metody volané nepřímo -- před samotným voláním se provede výběr správné metody na základě typu objektu, pro který je metoda volána. Úvod do virtuálních metod lze nalézt v \cite{Prata}, podrobnější informací pak v \cite{Stroustrup}.
 
\medskip\noindent Citace z \cite{ICP}:
\begin{quote}
Pro pochopení virtuálních metod je vhodné vědět, jak je uvedený mechanismus obvykle implementován:
\begin{itemize}
 \item Každá třída s virtuálními metodami má tzv. tabulku virtuálních metod (VMT - Virtual Method Table), ve které jsou odkazy na~všechny virtuální metody třídy.
 \item Při dědění (při překladu) se převezme obsah VMT bázové třídy, odkazy na~virtuální metody, které byly předefinovány se nahradí novými a na~konec VMT se doplní odkazy na případné nové virtuální metody.
 \item Každý objekt třídy s virtuálními metodami obsahuje odkaz na tabulku virtuálních metod.
 \item Polymorfní volání použije ukazatel v objektu, vybere odpovídající položku z VMT a zavolá metodu.
\end{itemize}
\end{quote}
 
\chapter{Současný stav}\label{stateOfArt}
Dnes dostupné překladače jazyka C++ nemají vestavěnou podporu pro práci se sdílenou pamětí. Jsme tedy odkázáni na API operačního systému, pomocí kterého je sdílená paměť zpřístupňována. Stejně tak ve standardu C++ nejsou zahrnuté prostředky pro synchronizaci procesů. Některé překladače umožňují např. definovat kritickou sekci, ale tato řešení jsou platformově závislá.  Neexistuje jednotné API pro práci se sdílenou pamětí a synchronizačními prostředky. Pokud tedy píšeme multiplatformní aplikaci, nezbývá než implementovat práci se sdílenou pamětí na každém OS jinak.
 
V důsledku nízké podpory překladače je sdílení objektů jazyka C++ velmi omezené. Překladače splňující nějaký standard jazyka C++ se zavazují implementovat synta\-xi a~sé\-man\-tiku jazyka, kterou standard předepisuje. Samotný překlad do binárního kódu však standardizován není. Budeme-li definovat ve dvou různých překladačích objekt stejným způsobem, není zaručeno, že bude v paměti stejně uložen.
 
Při používání objektů jazyka C++ jako komunikačního prostředku, se tedy může projevit binární nekompatibilita mezi komunikujícími programy. Existuje podmnožina objektů, zvaných POD, pro které je binární kompatibilita zaručena. Zkratka POD znamená \textit{Plain Old Data}, definici můžete nalézt v \cite{POD}. Jednoduše řečeno, jedná se o data, která lze kopírovat bit po bitu. Pokud chceme mít zajištěnou binární kompatibilitu mezi aplikacemi, které komunikují přes sdílenou paměť, měli bychom komunikovat pomocí objektů POD\footnote{Typový systém jazyka C (předchůdce C++) je založený pouze na objektech POD.}.
 
Součástí standardu C++ je také STL (\textit{Standard Template Library}). Jedná se o knihovnu šablon implementující běžně používané typy kontejnerů pro objekty (zásobník, vektor, ...) a algoritmů, které s nimi umí pracovat (řazení, vyhledávání, ...). Úvod do práce s STL naleznete např. v \cite{Stroustrup}. Návrh STL realizuje nezávislost kontejnerů na fyzickém umístění dat pomocí tzv. \textit{alokátorů}. Implicitní alokátor používá run-time jazyka C++ a jeho správu dynamicky alokované paměti. Můžeme si však vytvořit vlastní alokátor, který bude ukládat data do sdílené paměti\footnote{Alokátor objektů využívající sdílenou paměť představuje jeden typ alokátoru. Je možné vytvořit také alokátor perzistentních objektů uložených na disku apod.}. Způsob vytvoření alokátoru a jeho využití při práci s STL je popsáno rovněž v \cite{Stroustrup}. Bohužel některé implementace STL nepracují s alokátory tak, jak je uvedeno v této knize.
 
V současné době existuje otevřená implementace alokátoru pro STL\footnote{\texttt{http://allocator.sourceforge.net/}}, který pracuje se~sdílenou pamětí. Podrobnosti o návrhu alokátoru lze nalézt v \cite{rtlinux}. Tento projekt byl však zastaven, podle autora, z důvodu bugu\footnote{Podrobnosti zaslaném bugu naleznete na \texttt{http://gcc.gnu.org/bugzilla/show\_bug.cgi?id=21251}} v překladači GCC. Vývojáři překladače však tento bug označili za neplatný. Od té doby se projekt dále nevyvíjí. Navíc podle dostupných informací alokátor nefunguje na současné stabilní verzi překladače GCC.
 
Implementace platformově závislé části knihovny vychází z toolkitu MDSTk\cite{MDSTk} pro segmentaci medicínských dat. Tento toolkit obsahuje mimo jiné knihovnu, která umožňuje práci se sdílenou pamětí a semafory na systémech Linux a Microsoft Windows. Tyto prostředky operačního systému jsou na obou platformách zpřístupňovány se stejným rozhraním. Tím je vytvářena transparentní vrstva pro aplikace, které knihovnu používají.
 
\chapter{Návrh řešení}\label{design}
Při návrhu bylo hlavním cílem knihovny zjednodušit práci s objekty ve sdílené paměti. Každý programátor C++ umí pracovat s objekty jazyka C++. Bylo tedy potřeba práci s~objekty ve sdílené paměti maximálně připodobnit práci s nesdílenými objekty.
 
\section{Alokace sdílených objektů}
V jazyce C++ existují dva způsoby, jak vytvořit instanci třídy -- \textit{objekt}:
\begin{enumerate}
 \item \textbf{Staticky} -- Data objektu jsou uložena přímo na zásobníku běžícího procesu. Konstrukci a destrukci objektu řídí překladač automaticky na základě vstupu a výstupu z bloku, ve kterém je objekt definován.
  \begin{verbatim}
  MyClass myObject(...);
  \end{verbatim} 
 \item \textbf{Dynamicky} -- Data objektu jsou uložena na hromadě. Konstrukci a destrukci řídí programátor voláním \verb|new| a \verb|delete|.
  \begin{verbatim}
  MyClass *myObject = new MyClass(...);
  ...
  delete myObject;
  \end{verbatim} 
\end{enumerate}
 
Je zřejmé, že statické objekty nelze sdílet -- umístění objektů na zásobník zajišťuje překladač již v době překladu\footnote{Jazyk C již od verze ISO C99 umožňuje za běhu stanovit rozměr pole uloženého na zásobníku. Z pohledu objektového jazyka C++ však tato možnost není tolik přínosná.}. Navíc nemáme zcela pod kontrolou dobu existence objektů. Příznivější (z hlediska sdílení) je situace u dynamicky alokovaných objektů. Stačí místo volání \verb|new| a \verb|delete| volat odpovídající metody v rozhraní knihovny a tím získat kontrolu nad životem objektů.
 
Uživatel knihovny by však nebyl příliš nadšený, kdyby musel zasahovat do stávajícího kódu a zaměňovat veškeré operátory \verb|new| a \verb|delete| za volání nějakých metod. Jazyk C++ však s touto situací počítá a umožňuje operátory \verb|new| a \verb|delete| \textbf{přetížit}. Pro stávající kód pracující s objektem se tak změna úložiště stává zcela transparentní -- v kódu jsou nadále použity operátory \verb|new| a \verb|delete|, mají však odlišnou implementaci.
 
% Třídy se deklarují nebo definují????
Tím je vyřešen problém s vytvořením instance sdíleného objektu. Nyní je třeba zvolit vhodnou strategii pro tvoření samotných tříd, jejichž objekty se budou sdílet. Při návrhu jsem vycházel ze zásady \quotedblbase{Skrývejte informace\textquotedblleft} z \cite{Sutter}. Přetížení operátorů jsem zapouzdřil do samostatné třídy, kterou jsem nazval \verb|SharedObject|. Když bude uživatel knihovny deklarovat třídu umožňující sdílení, stačí použít \textbf{jednoduchou dědičnost}, jak ukazuje obr. \ref{SharedObject_SI}. Pokud je třída odvozena z třídy \verb|SharedObject|, neznamená to samozřejmě, že není možné objekty této třídy alokovat na zásobníku nebo na hromadě. Pokud není připojen sdílený segment, chování objektu se nijak neliší od původního (viz. dále).
\begin{figure}[h]
  \begin{center}\includegraphics[scale=0.5]{img/SharedObject_SI.png}\end{center}
  \caption{Deklarace nové třídy umožňující sdílení.}\label{SharedObject_SI}
\end{figure}
 
Můžeme se však dostat do situace, že máme třídu již hotovou a chceme pro ni zajistit sdílení tak, abychom ji nemuseli měnit. I v tomto případě je možné použít třídu \verb|SharedObject| -- tentokrát pomocí \textbf{vícenásobné dědičnosti}. Již existující třídu je třeba spolu se třídou \verb|SharedObject| obalit novou třídou, jak je znázorněno na  obr. \ref{SharedObject_MI}. Na první pohled by se mohlo zdát, že se tím zvětší velikost alokovaných objektů. Třída \verb|SharedObject| má však nulovou velikost, protože neobsahuje členská data. Odvozená třída tedy bude mít stejnou velikost, jako třída původní.
\begin{figure}[h]
  \begin{center}\includegraphics[scale=0.5]{img/SharedObject_MI.png}\end{center}
  \caption{Obalení existující třídy.}\label{SharedObject_MI}
\end{figure}
 
\noindent Odpovídající kus kódu v jazyce C++ bude vypadat takto:
\begin{verbatim}
  class MyClassWrappered:
    public MyClass,
    public SharedObject
    { };
\end{verbatim}
 
\section{Ukazatel na sdílený objekt}
V předchozí kapitole byl vyřešený problém s alokací objektů uvnitř sdíleného segmentu v~rámci jednoho procesu. To však samo o sobě nepřináší žádný užitek. Alokované objekty je potřeba sdílet mezi procesy.
 
Při úspěšném volání \verb|new| v uvedeném příkladu bude ukazatel \verb|myObject| ukazovat na~nově alokovaný objekt v připojeném sdíleném segmentu. Pomocí tohoto ukazatele můžeme s~objektem pracovat uvnitř procesu, který objekt alokoval. Problém nastane, když se snažíme ukazatel předat procesu, se kterým komunikujeme.
 
Jak bylo řečeno v kapitole \ref{process}, každý proces pracuje se svým paměťovým prostorem, o~který se stará správce virtuální paměti. Sdílený segment se může v jednotlivých procesech mapovat na různé adresy. Ukazatel na objekt, který byl získán při alokaci objektu v jednom procesu, může být v kontextu jiného procesu neplatný.
 
Ukazatel tedy nelze jednoduše sdílet mezi více procesy -- je potřeba zohlednit adresu, na které je sdílený objekt v každém procesu namapovaný. Ukazatel lze pro tento účel rozdělit na dvě části, jak je znázorněno na obr. \ref{RelocPtr_diagram}.
\begin{figure}[h]
  \begin{center}\includegraphics[scale=0.5]{img/RelocPtr.png}\end{center}
  \caption{Ukazatel na sdílený objekt v adresovém prostoru procesu}\label{RelocPtr_diagram}
\end{figure}
První část je adresa namapovaného sdíleného segmentu. Druhá část představuje umístění objektu vzhledem k počátku sdíleného segmentu. Je zřejmé, že druhá část ukazatele bude pro všechny připojené procesy stejná. Pro účely návrhu knihovny jsem tuto část nazval \textit{relativní ukazatel}. Celý ukazatel (vrácený voláním \verb|new|) jsem pak pro rozlišení označil jako \textit{absolutní ukazatel}.
 
Komunikující procesy si mohou mezi sebou předávat relativní ukazatele na objekty. Pokud však chtějí s objektem pracovat, musí použít absolutní ukazatel. Při komunikaci je proto potřeba provádět \textit{překlad adres} -- převádět relativní ukazatele na absolutní a naopak. Překlad adres by měl být automatický a pokud možno skrytý před uživatelem knihovny. Za tímto účelem jsem definoval vlastní typ ukazatele na sdílený objekt -- \verb|RelocPtr|\footnote{Přesněji řečeno, jedná se o šablonu \texttt{RelocPtr<T>}, kde \texttt{T} je typ sdíleného objektu.}.
 
Ukazatele tohoto typu lze bez problémů sdílet mezi procesy, uvnitř je totiž uložena pouze relativní adresa objektu. Navenek se však tváří jako běžný ukazatel, tj. absolutní. Toho je dosaženo přetížením operátorů \verb|->|, \verb|*|, \verb|[]| a operátorů ukazatelové aritmetiky. Aby bylo možné ukazatele samotné umisťovat do sdíleného segmentu voláním \verb|new|, je třída \verb|RelocPtr| odvozena ze třídy \verb|SharedObject| uvedené v předchozí kapitole.
 
Ukazatel \verb|RelocPtr| nemá sám o sobě dost informací k výpočtu absolutního ukazatele, výpočet proto neprovádí přímo metody třídy \verb|RelocPtr|. K tomuto účelu je v každém procesu instance třídy \verb|ShareManager|, která mimo jiné zajišťuje připojení sdíleného segmentu. Má tedy k dispozici potřebné informace pro překlad adres.
 
\section{Rozhraní knihovny}
V přiloženém CD se nachází dokumentace knihovního API (Application Programming Interface). V této dokumentaci lze najít kompletní popis rozhraní knihovny. Dokumentace je rozdělena do několika částí podle účelu dokumentovaných tříd.
 
Hlavní část rozhraní knihovny tvoří třída \verb|ShareManager|. Při jejím návrhu byl použit návrhový vzor \textit{Singleton}, který je podrobně popsán v \cite{Gamma}. Tento návrhový vzor zajistí, aby byla v jednom procesu vytvořena vždy maximálně jedna instance této třídy a byla dostupná ze všech částí zdrojového kódu. Třída \verb|ShareManager| umožňuje:
\begin{itemize}
 \item Vytvořit nový sdílený segment
 \item Připojit/odpojit již existující sdílený segment
 \item Alokovat bloky paměti uvnitř sdíleného segmentu
 \item Převádět relativní ukazatele na absolutní a naopak
\end{itemize}
 
K provedení těchto operací třída \verb|ShareManager| využívá třídy nižší vrstvy knihovny, jak je uvedeno na obr. \ref{ShareManager_diagram}.
\begin{figure}[h]
  \begin{center}\includegraphics[scale=0.5]{img/ShareManager.png}\end{center}
  \caption{Diagram spolupráce třídy \texttt{ShareManager}}\label{ShareManager_diagram}
\end{figure}
Objekt třídy \verb|SegmentHeader| je umístěn na začátku každého sdíleného segmentu, je tedy sdílen všemi připojenými procesy. Třída \verb|SharedSegment| zapouzdřuje připojený sdílený segment a tvoří platformově nezávislou vrstvu pro práci se~sdíle\-nou pamětí. Implementace těchto tříd je popsána v kapitole \ref{implementation}.
 
Součástí knihovního rozhraní je také šablona pro STL alokátor -- \verb|Allocator<T>|. Pomocí~této šablony je možné sdílet kontejnery STL. V kapitole \ref{implementation} je ukázáno, jak se tato šablona používá.
 
% Návrh řešení - výběr vhodné metody, jak to všechno bude fungovat.
% Požadavky kladené na knihovnu:
% \begin{itemize}
%  \item Velmi jednoduché rozhraní
%  \item Přenositelnost na různé platformy
%  \item Definování alokátoru pro STL
%  \item Možnost alokovat odvozené objekty ve sdílené i lokální paměti
%  \item TODO: Počítadlo referencí?
%  \item TODO: Synchronizace?
% \end{itemize}
% 
% \bigskip
% Diskuze na téma \uv{Práce s N sdílenými segmenty najednou}...
 
\section{Omezení při práci s knihovnou}
V této kapitole jsou popsána a zdůvodněna omezení, která jsou kladena na programy pracující s knihovnou.
\begin{description}
 \item[Virtuální metody]~\\
   Hlavní omezení kladené na programy, které knihovnu využívají, se týká virtuálních metod (viz. kapitola \ref{virtual}). Tak jako nelze sdílet absolutní ukazatel na sdílený objekt mezi procesy, nelze sdílet ani ukazatel na tabulku virtuálních metod.
 
   Tento ukazatel se nastavuje při vytváření objektu -- je tedy platný v kontextu procesu, který jej vytvořil. Ukazatel na tabulku virtuálních metod se však sdílí spolu s členskými daty a v kontextu jiného procesu může být neplatný. Pokud zavoláme virtuální metodu sdíleného objektu z jiného procesu, může program havarovat.
 
   Manipulace s ukazatelem na tabulku virtuálních metod je řízena výhradně překlada\-čem. Není tedy v silách knihovny tento problém nějak řešit. Při použití knihovny je proto nutné s tímto omezením počítat -- \textbf{sdílené objekty nesmí obsahovat žádné virtuální funkce}.
   \bigskip
 
 \item[Počet současně připojených segmentů]~\\
   O připojení/odpojení sdíleného segmentu se stará samotný singleton \verb|ShareManager|, přičemž připojený segment není nijak identifikován. Z toho vyplývá, že \textbf{nelze připojit najednou více sdílených segmentů}.
 
   Příčinou samozřejmě není existence singletonu. Byla zvažována také varianta návrhu pracující s více sdílenými segmenty. Problém je však s výkonem. Nejslabším místem knihovny po stránce výkonu je překlad adres. V současné verzi knihovny spočívá překlad adres pouze v přičtení adresy připojeného segmentu k relativnímu ukazateli\footnote{Ikdyž může graf volání při překladu adres vypadat hrozivě, většina funkcí je \texttt{inline} -- to znamená, že se funkce rozbalí při příkladu místo použití volací konvence. Výsledek potom v binární podobě vypadá mnohem jednodušeji.}.
 
   Při práci s více segmenty by bylo vždy potřeba nastavit aktivní segment. Při každém překladu adres by potom bylo nutné zjistit, který segment je v danou chvíli aktivní. To je časově velmi náročná operace vzhledem k četnosti překladu adres. Pokud by navíc programátor zapomněl nastavit aktivní segment, překlad adres by se provedl špatně -- tím by se zvýšilo riziko chyby v programech, které knihovnu používají.
 
   Z těchto důvodů byla zvolena varianta návrhu umožňující připojit pouze jeden sdílený segment a přijato tohle omezení.
   \bigskip
\end{description}
 
\chapter{Implementace}\label{implementation}
Z hlediska implementace se třídy knihovny dělí do následujících částí:
\begin{itemize}
 \item Třídy jádra knihovny
 \item Odlehčená implementace některých STL kontejnerů
 \item Utilita \texttt{sharectl}
 \item Interní třídy knihovny
\end{itemize}
Implementační detaily naleznete v dokumentaci knihovního API na přiloženém CD. Kromě popisu jednotlivých tříd obsahuje dokumentace také odkazy přímo do zdrojového kódu knihovny. Následuje stručný popis jednotlivých částí.
 
\medskip
\begin{description}
 \item[Třídy jádra knihovny]~\\
   Do této části spadají třídy tvořící rozhraní knihovny, které byly uvedeny v kapitole~\ref{design}. Knihovna dále definuje vlastní typ výjimky -- \verb|Share::Exception|. Tato výjimka je odvozena od \verb|std::bad_alloc|, navíc však obsahuje textový řetězec, který popisuje chybu. Tento řetězec může být využit pro účely ladění.
 
   Z implementačního hlediska jsou zajímavé šablony \verb|TReference<T>| a \verb|TVoidPointer<T>|. Jedná se o tzv. \textit{rysy} (anglicky \textit{traits}). Šablona \verb|TReference<T>| zabraňuje vytvoření reference na \verb|void| v šablonách, které ji používají. Šablona \verb|TVoidPointer<T>| definuje typ ukazatele na \verb|void|, přičemž ponechá konstantní ukazatel konstantním. Informace o tom, jak rysy fungují, naleznete v \cite{Alexandrescu}.
 
   Strukturu \verb|Allocator::rebind<U>| používají STL kontejnery k vytvoření jiného typu alokátoru na základě existujícího typu. Proč je tohle potřeba, vysvětluje \cite{Stroustrup}. Názorný příklad použití naleznete v implementaci kontejneru \verb|Share::Map|.
   \bigskip
 
 \item[Odlehčená implementace některých STL kontejnerů]~\\
   Součástí knihovny je odlehčená implementace některých STL kontejnerů. Tyto kontejnery si nekladou za cíl nahradit stávající implementace STL. Pouze demonstrují možnosti jádra knihovny a ukazují, že je možné kontejnery sdílet mezi procesy\footnote{Běžně používané implementace STL při testech nepracovali s knihovním alokátorem správně, více v~kapitole \ref{results}.}.
 
   Tyto kontejnery implementují pouze podmnožinu operací běžných STL kontejnerů. Jejich rozhraní se může lišit v některých detailech. Jsou však názorně použity v testovacích příkladech. V tabulce \ref{stlTable} se nachází přehled implementovaných kontejnerů.
   \begin{table}[h]
    \begin{center}
      \begin{tabular}{|l|l|}\hline
       \multicolumn{1}{|c|}{\textbf{STL}}&\multicolumn{1}{c|}{\textbf{Share}}\\\hline
       \verb|std::vector|&\verb|Share::Vector|\\
       \verb|std::string|&\verb|Share::String|\\
       \verb|std::map|&\verb|Share::Map|\\\hline
      \end{tabular} 
    \end{center}
    \caption{Názvy implementovaných STL kontejnerů}
    \label{stlTable}
   \end{table}
 
   Kontejnery používají abstrakci alokátoru, stejně jako standardní kontejnery. Jako výchozí alokátor je nastaven \verb|std::allocator|. Pokud jsou použity kontejnery s tímto alokátorem, jsou nezávislé na práci se sdílenou pamětí.
 
   Pokud chceme kontejnery sdílet, je nutné nastavit jako alokátor \verb|Share::Alocator|. Následující ukázka (převzata z testovacího programu \texttt{test2\_wordcount}) ukazuje, jak uvnitř sdíleného objektu vytvořit mapování z řetězce na číslo:
\begin{verbatim}
class WordCount: public Share::SharedObject {
  typedef Share::String <Share::Allocator <char> > TString;
  typedef Share::Allocator <Share::Pair <TString, int> > TAllocator;
  typedef Share::Map<TString, int, TAllocator> THashTable;
 
  THashTable hashTable_;
  ...
};
\end{verbatim}
\bigskip
 
 \item[Utilita \texttt{sharectl}]~\\
   Spolu s knihovnou je také dodávána konzolová aplikace \texttt{sharectl}, která s knihovnou spolupracuje. Tato aplikace umožňuje sledovat sdílené segmenty. To se hodí při ladění aplikací, které pracují s knihovnou, a také při ladění knihovny samotné.
 
   Kromě výpisu základních statistik sdíleného segmentu dokáže tato utilita například odstranit sdílený segment, který zůstane v paměti po havárii aplikace. Také lze touto utilitou ručně volat operace nad sdíleným segmentem, jako je alokace bloku paměti, zvýšení počtu počítadla referencí, apod.
 
   Nápovědu k \texttt{sharectl} lze nalézt v programové dokumentaci, nebo pomocí příkazu:
\begin{verbatim}
  sharectl --help
\end{verbatim}
\bigskip
 
 \item[Interní třídy knihovny]~\\
   Do této části spadají třídy, kterou jsou uživateli knihovny skryty. Nejnižší vrstvu knihovny tvoří třídy zajišťující platformovou nezávislost zbytku knihovny -- \texttt{SharedSeg\-ment} a \verb|Mutex|. Při implementaci těchto tříd byly použity zdrojové kódy MDSTk\cite{MDSTk}.
 
   Sdílená data knihovny pro každý segment jsou uložena v objektu \verb|SegmentHeader|, který je umístěn na začátku sdíleného segmentu. Tento objekt spojuje funkcionalitu alokátoru a počítadla referencí. Sám se navíc chová jako monitor (viz. kapitola \ref{semaphores}), čímž zajišťuje bezpečnost alokace a počítání referencí při paralelním běhu procesů.
   \begin{figure}[h]
     \begin{center}\includegraphics[scale=0.5]{img/SegmentHeader.png}\end{center}
     \caption{Diagram spolupráce třídy \texttt{SegmentHeader}}\label{SegmentHeader_diagram}
   \end{figure}
 
   Vzájemné vyloučení procesů je zajištěno třídou \verb|Mutex|, graf spolupráce je na obr \ref{SegmentHeader_diagram}. Třídy \texttt{DefaultAllocator} a \verb|DefaultRefCounter| lze nahradit jinými (dokonalejšími) třídami změnou definice typů \verb|TSegmentAllocator| a \texttt{TSeg\-ment\-RefCounter} v souboru \texttt{SegmentHeader.h}.
 \end{description}
 
% Implementace - krátká kapitolka o implementaci. Jaké jste použili knihovny, jak jste implementovali algoritmy, jaké problemy bylo nutné vyřešit, atd.
 
\chapter{Výsledky}\label{results}
Předmětem této práce je knihovna. Knihovna samotná se však testuje velmi špatně. Aby bylo možné vyzkoušet funkci knihovny a zhodnotit její vlastnosti, napsal jsem sadu testovacích programů. Tyto programy jsou distribuovány spolu s knihovnou.
 
\section{Testovací programy}
Základním diagnostickým nástrojem při práci s knihovnou je utilita \texttt{sharectl}, která byla uvedena v kapitole \ref{implementation}. Na rozdíl od ostatních programů a testovacích skriptů pracuje s~interními třídami knihovny -- slouží tedy k diagnostice knihovny na nejnižší úrovni.
 
Pomocí této utility lze ladit ostatní testovací programy, ale také knihovnu samotnou. Umožňuje například zjistit nekompatibilitu s operačním systémem nebo jeho konfigurací. Pomáhá také překonat některá omezení OS, která jsou uvedena v následující kapitole. Dále jsou k dispozici tři jednoduché testovací programy, na kterých jsou funkce knihovny předvedeny:
\begin{description}
 \item[\texttt{test1\_string}]~\\
  Tento jednoduchý testovací program představuje práci s knihovnou ve své nejjedno\-duš\-ší podobě. Na začátku je deklarována třída sdíleného objektu, který obsahuje řetězec\footnote{Implementace této třídy je velmi jednoduchá, bohužel však na úkor efektivity. Pokud potřebujete sdílet řetězec, použijte kontejner \texttt{Share::String}.}. Samotná funkce \verb|main()| potom rozlišuje mezi dvěma režimy -- proces se~chová buď jako producent, nebo jako konzument.
 
  Pokud je program spuštěn s jedním parametrem (jménem sdíleného segmentu), chová se jako producent. Vytvoří sdílený segment o velikosti \verb|MAX_DATA_SIZE| a v něm alokuje sdílený objekt. Potom jsou načítány řádky ze standardního vstupu a ukládány do~sdíle\-ného objektu.
 
  Pokud je program spuštěn s parametrem navíc (relativní adresou objektu), chová se jako konzument. Připojí se ke sdílenému segmentu, převede relativní adresu na ukazatel a vypíše obsah objektu na standardní výstup. Během komunikace není prováděna žádná synchronizace mezi procesy.
  \bigskip
 
 \item[\texttt{test2\_wordcount}]~\\
  Program \texttt{test2\_wordcount} jde v testování knihovny ještě dál. Uvnitř sdíleného objektu jsou sdíleny také STL kontejnery. Nejedná se o standardní STL kontejnery, ale o jejich knihovních ekvivalenty \texttt{Share::String} a \texttt{Share::Map}, které lépe pracují s~alokátorem Share::Allocator.
 
  Program, jak jeho název napovídá, slouží k počítání slov. Inicializace je provedena pří spuštění programu s jedním parametrem -- názvem již alokovaného sdíleného segmentu. Po úspěšné inicializaci je vypsána relativní adresa alokovaného objektu, kterou je nutné programu předávat při jeho dalších voláních.
 
  Pokud je jako třetí parametr zadáno jméno souboru, jsou do statistik zahrnuta slova v něm obsažená. Je-li program spuštěn pouze se dvěma parametry, jsou vypsány statistiky počtu slov. Datové struktury obsahující statistiky jsou uloženy ve sdíleném segmentu a tím jsou perzistentní vzhledem k jednotlivým voláním programu.
  \bigskip
 
 \item[\texttt{test3\_benchmark}]~\\
  Tento testovací program, stejně jako jeho předchůdce, počítá slova. Na rozdíl od programu \texttt{test2\_wordcount} však nezobrazuje statistiky počtu slov, ale dobu počítání slov. Program tedy slouží k měření výkonnostních charakteristik knihovny.
 
  Během jednoho spuštění programu je postupně provedeno 24 různých testů. Popis jednotlivých testů spolu s naměřenými výsledky jsou uvedeny v kapitole \ref{power}. Během~pro\-vádění jednotlivých testů nedochází k meziprocesorové komunikaci.
  \bigskip
 
\end{description}
 
\section{Testování knihovny na jednotlivých platformách}
\begin{description}
 \item[Linux (64bit)]~\\
  Sestavení knihovny na operačním systému Linux je zajišťováno pomocí \texttt{GNU make}. Vývoj knihovny probíhal na distribuci \textit{Gentoo Linux}. Překlad knihovny byl testován na překladačích \texttt{GCC 3.4.6} a \texttt{GCC 4.1.1}. Pomocí programu \texttt{Doxygen} je možné vygene\-rovat programovou dokumentaci.
 
  Testovací programy pracují s velkými bloky sdílené paměti. Pro správnou funkci těchto programů je nutné nastavit odpovídající limity pro práci se sdílenou pamětí v jádru. To lze provést změnou obsahu následujících souborů v souborovém systému \texttt{proc}\footnote{Pro zápis do těchto souborů je nutné mít odpovídající oprávnění.}:
\begin{verbatim}
  /proc/sys/kernel/shmmni
  /proc/sys/kernel/shmall
  /proc/sys/kernel/shmmax
\end{verbatim} 
 
  Implementace sdílené paměti na systému Linux umožňuje uchovat v paměti sdílený segment, ke kterému není připojený žádný proces. To je výhoda proti systému Microsoft Windows, který automaticky odstraňuje sdílené segmenty po ukončení posled\-ního připojeného procesu.
 
  Tohle chování však někdy může dělat problémy -- segment zůstane \quotedblbase{viset\textquotedblleft} v paměti, když program havaruje. Takový segment je potom možné odstranit voláním:\
\begin{verbatim}
  sharectl --force-destroy SEGMENT_NAME
\end{verbatim} 
\bigskip
 
 \item[Microsoft Windows (32bit)]~\\
  K sestavení knihovny na systému Microsoft Windows je potřeba mít nainstalované \textit{Microsoft Visual Studio 2005} s podporou jazyka C++. Stačí otevřít soubor řešení \texttt{sharelib.sln} a kliknout na položku \textit{Build solution} v menu \textit{Build}. Tím se sestaví knihovna, utilita \texttt{sharectl} i testovací programy. Knihovna byla testována na \textit{Windows XP Professional} a \textit{Windows Vista Business}, které běžely na 32-bitovém virtuálním stroji \textit{VMware Server}.
 
  Jak bylo řečeno, Microsoft Windows automaticky odstraňují nepoužívané sdílené segmenty. To je většinou nežádoucí a v aplikacích, které s knihovnou pracují, je nutné s~tímto chováním počítat. Pro účely ladění lze vytvořit sdílený segment pomocí příkazu:
\begin{verbatim}
  sharectl --create-and-wait SEGMENT_NAME SEGMENT_SIZE
\end{verbatim} 
  Utilita vytvoří sdílený segment s danými parametry a před návratem do příkazové řádky počká na stisk klávesy. Do stisknutí klávesy se potom chování sdíleného segmentu podobá chování na Linuxu.
  \bigskip
\end{description}
 
\section{STL std::string}
Knihovní alokátor \texttt{Share::Allocator} byl navrhnut za účelem sdílení STL kontejnerů. Při~testech však nefungoval podle plánu -- STL kontejnery interně pracovaly s jiným typem ukazatele než definoval alokátor. To mělo za následek, že ke sdíleným datům nebylo možné přistupovat z více procesů.
 
Z tohoto důvodu disponuje knihovna vlastní odlehčenou implementací některých STL kontejnerů. Jejich srovnání se standardní implementací STL po stránce výkonu naleznete v následující kapitole.
 
Kromě toho jsem se pokusil upravit stávající implementaci STL tak, aby pracovala správně s knihovním alokátorem. Pro experiment jsem použil implementaci \texttt{std::string} v knihovně STL, která byla nainstalovaná na mé distribuci Linuxu. Navzdory její robustnostnosti byla samotná úprava knihovny velmi jednoduchá -- stačilo změnit jediný řádek v~hlavičkovém souboru \verb|bits/basic_string.h|. Původní úsek změněného kódu vypadal takto:
\begin{verbatim}
    struct _Alloc_hider : _Alloc
    {
      _Alloc_hider(_CharT* __dat, const _Alloc& __a)
      : _Alloc(__a), _M_p(__dat) { }
 
      _CharT* _M_p; // The actual data
    };
\end{verbatim} 
Změněný úsek kódu potom vypadal takto:
\begin{verbatim}
    struct _Alloc_hider : _Alloc
    {
      _Alloc_hider(_CharT* __dat, const _Alloc& __a)
      : _Alloc(__a), _M_p(__dat) { }
 
      pointer _M_p; // The actual data.
    };
\end{verbatim} 
Po provedení této jednoduché úpravy bylo možné \texttt{std::string} sdílet mezi procesy a pracovat s ním stejně jako s \texttt{Share::String}. Standardní implementace je však oproti knihovní implementaci mnohem bohatější v počtu metod a spolupracujících algoritmů.
 
\section{Výkon aplikací při práci s knihovnou}\label{power}
K měření výkonu při práci s knihovnou slouží testovací program \texttt{test3\_benchmark}. Jádro programu vychází z třídy \texttt{WordCount} z programu \texttt{test2\_wordcount}, tentokrát jde však o~šablonu třídy. Parametry šablony jsou následující:
\begin{itemize}
 \item Typ kontejneru použitý pro řetězec
 \item Typ kontejneru použitý pro mapování řetězce na číslo
 \item Typ alokátoru
\end{itemize}
Třída je pak postupně vytvářena s různými parametry šablony, testování je tak provedeno na osmi různých specializacích šablony \texttt{WordCount}. Kromě toho jsou objekty alokovány třemi možnými způsoby:
\begin{itemize}
 \item Na zásobníku
 \item Na hromadě
 \item V připojeném segmentu sdílené paměti
\end{itemize}
Celkem je tedy provedeno 24 různých testů, u každého z nich je změřen čas potřebný pro~spočítání slov. Výsledky testů pro jednotlivé platformy jsou v tabulkách \ref{t3bLinux} a \ref{t3bWin32}. Jako vstupní soubor jsem použil databázi slov knihovny \textit{CrackLib}. Celkově horší časy na~platformě MS Windows jsou způsobeny mimo jiné tím, že testy běžely na virtuálním stroji.
 
Při testech 1-4 používal program standardní alokátor. Ikdyž byl objekt vytvořen ve~sdíle\-né paměti (poslední sloupeček tabulky), data kontejneru byla alokována na hromadě. Zajíma\-vostí je, že při použití knihovní implementace řetězce byla rychlost \textbf{2x větší} než u \texttt{std::\-string}.
 
Plně funkční specializaci šablony \texttt{WordCount}, která byla použita v testovacím programu \texttt{test2\_wordcount}, představuje test č. 8. Tato varianta používá výhradně třídy knihovny. Její rychlost je asi \textbf{3-5x nižší} než varianta s klasickou STL bez využití sdílené paměti (test č. 1).
 
Zajímavostí je také rozdíl mezi časy při statické a dynamické alokaci objektu \texttt{WordCount}. Tento rozdíl je pravděpodobně způsoben nižší lokalitou odkazů při alokaci objektu na~zásob\-níku -- část dat kontejneru se totiž nachází na zásobníku a část na hromadě.
 
%Výsledky - dosažené výsledky, grafy z různých testování, co funguje dobře, co nefunguje, co je třeba vylepšit a jak, ...
%
\bigskip
%Problémy s alokátorem STL -- experimenty s STLport, implementace stringu, ...
%
%\bigskip
%Rozdíl výkonu na lokálních a sdílených objektech
\begin{table}[p]
  \begin{sffamily}
%     \begin{small}
      \begin{center}
        \begin{tabular}{|c|r|r|r|r@{.}l@{ s }|r@{.}l@{ s }|r@{.}l@{ s }|}\hline
          \textbf{Test č.}&\multicolumn{1}{c|}{\textbf{TString}}&\multicolumn{1}{c|}{\textbf{TMap}}&\multicolumn{1}{c|}{\textbf{TAllocator}}&\multicolumn{2}{c|}{\textbf{Stack}}&\multicolumn{2}{c|}{\textbf{Heap}}&\multicolumn{2}{c|}{\textbf{SHM}}\\\hline
          1&\texttt{  std::string}&\texttt{  std::map}&\texttt{  std::allocator}&0&24&0&14&0&14\\
          2&\texttt{Share::String}&\texttt{  std::map}&\texttt{  std::allocator}&0&17&0&09&0&07\\
          3&\texttt{  std::string}&\texttt{Share::Map}&\texttt{  std::allocator}&0&23&0&11&0&11\\
          4&\texttt{Share::String}&\texttt{Share::Map}&\texttt{  std::allocator}&0&21&0&1&0&09\\\hline
          5&\texttt{  std::string}&\texttt{  std::map}&\texttt{Share::Allocator}&0&35&0&17&0&39\\
          6&\texttt{Share::String}&\texttt{  std::map}&\texttt{Share::Allocator}&0&53&0&26&0&65\\
          7&\texttt{  std::string}&\texttt{Share::Map}&\texttt{Share::Allocator}&0&34&0&18&0&41\\
          8&\texttt{Share::String}&\texttt{Share::Map}&\texttt{Share::Allocator}&0&44&0&24&0&64\\
          \hline
        \end{tabular} 
      \end{center}
%     \end{small}
  \end{sffamily}
  \caption{Výsledky testovacího programu \texttt{test3\_benchmark} na systému Linux.}
  \label{t3bLinux}
\end{table}
 
\begin{table}[p]
  \begin{sffamily}
%     \begin{small}
      \begin{center}
        \begin{tabular}{|c|r|r|r|r@{.}l@{ s }|r@{.}l@{ s }|r@{.}l@{ s }|}\hline
          \textbf{Test č.}&\multicolumn{1}{c|}{\textbf{TString}}&\multicolumn{1}{c|}{\textbf{TMap}}&\multicolumn{1}{c|}{\textbf{TAllocator}}&\multicolumn{2}{c|}{\textbf{Stack}}&\multicolumn{2}{c|}{\textbf{Heap}}&\multicolumn{2}{c|}{\textbf{SHM}}\\\hline
          1&\texttt{  std::string}&\texttt{  std::map}&\texttt{  std::allocator}&1&063&0&219&0&203\\
          2&\texttt{Share::String}&\texttt{  std::map}&\texttt{  std::allocator}&0&656&0&203&0&187\\
          3&\texttt{  std::string}&\texttt{Share::Map}&\texttt{  std::allocator}&0&687&0&187&0&187\\
          4&\texttt{Share::String}&\texttt{Share::Map}&\texttt{  std::allocator}&0&453&0&219&0&219\\\hline
          5&\texttt{  std::string}&\texttt{  std::map}&\texttt{Share::Allocator}&1&062&0&266&9&953\\
          6&\texttt{Share::String}&\texttt{  std::map}&\texttt{Share::Allocator}&1&5&0&39&15&359\\
          7&\texttt{  std::string}&\texttt{Share::Map}&\texttt{Share::Allocator}&0&61&0&157&8&579\\
          8&\texttt{Share::String}&\texttt{Share::Map}&\texttt{Share::Allocator}&0&609&0&266&13&406\\
        \hline
        \end{tabular} 
      \end{center}
%     \end{small}
  \end{sffamily}
  \caption{Výsledky testovacího programu \texttt{test3\_benchmark} na systému MS Windows.}
  \label{t3bWin32}
\end{table}
 
\chapter{Závěr}
% Závěr - Jednou větou čím se práce zabývala. Jaké metody řešení byly zvoleny, jaké jsou výsledky a jak by se dalo pokračovat (future work).
Práce se zabývala návrhem knihovny a experimentováním s její implementací. Hlavním cílem návrhu bylo jednoduché rozhraní knihovny a tento cíl byl splněn. Přestože možnosti současné verze knihovny nejsou vyčerpávající, počítá návrh knihovny se spoustou rozšíření, které je možné doprogramovat v dalších verzích.
 
Při implementaci knihovny byly použity moderní programovací techniky, jako jsou šablony jazyka C++ a návrhové vzory. Knihovna funguje (s drobnými odchylkami) stejně na platformách Linux a Microsoft Windows, její rozhraní je pro obě platformy jednotné. Díky~testování knihovny na obou platformách byly odhaleny (a opraveny) nejrůznější chyby, které by jinak zůstaly skryty.
 
Použití knihovny bylo předvedeno na jednoduchých programech, přičemž byl vidět přínos knihovny -- práce se sdílenou pamětí se skutečně zjednodušila. Nevýho\-dou zůstává omezení kladené na typ sdílených objektů. Sdílené objekty nesmí obsahovat virtuální meto\-dy, není tedy možné počítat s dynamickým polymorfismem u sdílených objektů.
 
Sdílená paměť se ukázala jako velmi efektivní forma meziprocesorové komunikace a tato knihovna se snaží programátorům práci se sdílenou pamětí maximálně zjednodušit.
 
% ----------------------------------------------
% Použitá literatura
\bibliographystyle{./czechiso}
\begin{flushleft}
\bibliography{bp}
\end{flushleft}
 
\renewcommand{\appendixname}{Příloha}
\appendix
\chapter{Ukázka práce s knihovnou}\label{samples}
\noindent Deklarace třídy zapouzdřující vektor bodů, která podporuje sdílení:
\begin{quote}
\begin{verbatim}
#include <sharelib.h>
#include <iostream>
 
// Plain structure
struct Point {
  int x;
  int y;
  Point(int ix, int iy): x(ix), y(iy) { }
};
 
// Shared object's class
class PointVector: public Share::SharedObject {
public:
  void insert(Point);
  void print();
private:
  // Shared vector container
  typedef Share::Allocator<Point> TAllocator;
  typedef Share::Vector<Point, TAllocator> TVector;
  TVector vector_;
};
 
// Shareable pointer to class
typedef Share::RelocPtr<PointVector> TPointVectorPtr;
\end{verbatim}
\end{quote}
 
\newpage
\noindent Těla metod se nijak neliší od nesdílených objektů:
\begin{quote}
\begin{verbatim}
// Insert point p to vector
void PointVector::insert(Point p) {
  vector_.push_back(p);
}
 
// Print all points to std::cout
void PointVector::print() {
  TVector::const_iterator i;
  for (i=vector_.begin(); i!=vector_.end(); i++) {
    Point p = *i;
    std::cout << "[" << p.x << "," << p.y << "]" << std::endl;
  }
}
\end{verbatim}
\end{quote}
 
\bigskip
\noindent Konstrukce sdíleného objektu uvnitř nově vytvořeného sdíleného segmentu:
\begin{quote}
\begin{verbatim}
const size_t cbSize = 1024 * 1024;
const char szName[] = "test";
 
// Create new shared segment
Share::ShareManager::instance()-> createSegment(szName, cbSize);
 
// Create new PointVector object inside shared segment
TPointVectorPtr pv = new PointVector;
 
// Work with shared object
pv-> insert(Point(-1,3));
pv-> insert(Point( 0,2));
pv-> insert(Point( 5,4));
 
// Get relative object address
TPointVectorPtr::relative_pointer relAddr = pv.toRel();
...
\end{verbatim}
\end{quote}
 
\newpage
\noindent Připojení k již existujícímu sdílenému segmentu a práce se sdíleným objektem:
\begin{quote}
\begin{verbatim}
const char szName[] = "test";
 
// Attach existing shared segment
Share::ShareManager::instance()-> attachSegment(szName);
 
// Create pointer from relative object address
TPointVectorPtr pv = TPointVectorPtr::fromRel(relAddr);
 
// Work with shared object
pv-> insert(Point(0,0));
pv-> print();
...
\end{verbatim}
\end{quote}
 
\end{document}