<commit_before>\makeatletter \@ifundefined{rootpath}{\input{../../setup/preamble.tex}}\makeatother
\worksheetstart{Implementation}{0}{Februar 10, 2015}{}{../../}
This chapter describes the \ac{STM} implemented in the C\# programming language.
\label{chap:implementation}
\section{\acs{STM} System}
\subsection{Selection of Implementation Strategy}
Various implementation strategies have been proposed for \ac{STM} of which a few were described in \bsnameref{sec:intro_related_work}. This section will cover the considerations which went into selecting a implementation strategy. Specific attention is payed to the requirements and design choices made in \bsref{sec:stm_requirements} and \bsref{chap:stm_design}. Based on this overview a known algorithm will be selected. The authors\andreas{We?} assume the reader has knowledge of terminology related to implementation of \ac{STM} system, such as eager vs. lazy updating. If this is not the case a description of the terminology can be found in our previous study\cite[p. 53]{dpt907e14trending}.

\subsubsection{Strong Atomicity}
As described in \bsref{sec:design_strong_weak_atomicity} strong atomicity ensures atomicity between transactional and non-transactional access. As \stmnamesp is required to support strong atomicity the implementation strategy should facilitate such access.

Lazy updating inherently supports non-transactional reads as the value associated with transactional variables are always the most recently committed value\cite[p. 2084]{herlihy2011tm}\cite[p. 21]{harris2010transactional}. As a result a non-transactional read can never read a non-committed value and atomicity is ensured because a single non-transactional read always reads the most recently committed value of a transactional variable. Ensuring atomicity for non-transactional reads is however also possible using eager updating. As an example DSTM\cite{herlihy2003software} uses a \bscode{locator} to represent the transactional variables value. The \bscode{locator} object contains a reference to the transaction that created the \bscode{locator}, the new and the old value. Based on the status of the transaction that created the current \bscode{locator}, a non-transactional read can choose to read the new value if the status is committed or the old value if status is aborted or active, thereby ensuring that the most recently committed value is always read. Choosing the correct value to read, as opposed to simply reading the most recently committed value which lazy updating allows, does however cause some overhead.

While non-transactional writes to transactional variables cannot conflict with one another, they must be tracked by the \ac{STM} system in order to ensure that any transactions with which they conflict are aborted and retried. \cite{hindman2006atomicity} proposes expanding non-transactional access to mini transactions allowing the \ac{STM} system to track their actions. Their approach goes even further supplying optimized non-transactional access which skips much of the unnecessary logging required for normal transactions. \stmnamesp could benefit from a similar approach and the selected \ac{STM} algorithm should therefore support such an approach.
 
\subsubsection{Conditional Synchronization}
The \bscode{retry} construct described in \bscode{sec:req_conditional} require knowledge of what transactional variables has been read up to the point where a retry is requested\cite{harris2005composable}. As such the \ac{STM} system needs to maintain a set of transactional variable which has been read, for all active transactions, so that a transaction can be blocked until one of these variables change. Such as set is often referred to as a read-set\cite{dice2006transactional}\cite{harris2010transactional}\cite{herlihy2012art}. \ac{STM} systems employing lazy conflicts detection commonly use such as set to record reads for validation when the transaction is about to commit\cite{dice2006transactional}\cite{mohamedin2013bytestm}. Choosing a algorithm which already maintains a read-set will limit the overhead of the \bscode{retry} statement and should be be a priority.

\subsubsection{Opacity}
\subsubsection{Library Implementation}

\subsubsection{Final Selection}
\ac{STM} algorithms can coarsely be divided into blocking and non-blocking algorithms\cite[p. 47]{harris2010transactional}. Blocking algorithms employ some form of locking in order to ensure atomicity while non-blocking do not\cite[p. 59]{herlihy2012art}. Non-blocking algorithms guarantee that the failure of one thread does not keep other threads from making progress\cite[p. 47]{harris2010transactional}\cite[p. 142]{herlihy1991wait}\cite[p. 59]{herlihy2012art}. This  makes it impossible to employ locking as the failure of some thread $T$, which is holding a lock, will keep other threads from acquiring the lock, and thereby from progressing. Non-blocking algorithms can further be distinguished by the progress guarantees they provide. Wait-freedom is the strongest of these, and guarantees that any thread makes progress on its own work if it keeps executing\cite[p. 124]{herlihy1991wait}\cite[p. 59]{herlihy2012art}. Lock-freedom is less strict as it only guarantees that if a thread $T$ keeps executing then some thread (not necessarily $T$) makes progress\cite[p. 47]{harris2010transactional}\cite[p. 60]{herlihy2012art}. The least strict progress guarantees is call obstruction-freedom\cite[p. 47]{harris2010transactional}\cite{herlihy2003obstruction}\cite[p. 61]{herlihy2012art}. As mentioned in \bsref{sec:intro_related_work}, obstruction-freedom guarantees that any thread which runs for long enough without encountering a synchronization conflict makes progress\cite{herlihy2003obstruction}[p. 1]. While all of these progress guarantees precludes deadlocks, only wait-freedom and lock-freedom precludes livelocks\cite[p. 47]{harris2010transactional}. Obstruction free algorithms have been shown to provide efficient implementations in practice\cite[p. 61]{herlihy2012art}. Especially when paired with techniques such as exponential backoff\cite[p. 147]{herlihy2012art} and contention managers\cite[p. 51]{harris2010transactional}.  Whether \ac{STM} implementations needs to be wait-free, lock-free, obstruction-free or even provide any of these guarantees at all is a ongoing discussion. Arguments have been made for even obstruction-freedom being too strong a guarantee and that \ac{STM} can be made faster by employing controlled locking\cite{ennals2006software}. Due to the observations above we choose to focus on obstruction-free and blocking algorithms.
\andreas[inline]{Vi argumenterer ikke rigtigt for vores valg. Måske referer til nogle kriterier}

\subsection{STM Algorithm}
\kasper[inline]{obstruction freedom useful in practice}
\kasper[inline]{pending commit, permissiveness}
\andreas[inline]{Analysis of privatization techniques is done by \cite{spear2007privatization}. Strong atomicity is the technique with less restrictions, but worst performance}<commit_msg>Minor language corrections and a comment<commit_after>\makeatletter \@ifundefined{rootpath}{\input{../../setup/preamble.tex}}\makeatother
\worksheetstart{Implementation}{0}{Februar 10, 2015}{}{../../}
This chapter describes the \ac{STM} implemented in the C\# programming language.
\label{chap:implementation}
\section{\acs{STM} System}
\subsection{Selection of Implementation Strategy}
Various implementation strategies have been proposed for \ac{STM} of which a few were described in \bsnameref{sec:intro_related_work}. This section will cover the considerations which went into selecting a implementation strategy. Specific attention is payed to the requirements and design choices made in \bsref{sec:stm_requirements} and \bsref{chap:stm_design}. Based on this overview a known algorithm will be selected. The authors\andreas{We?} assume the reader has knowledge of terminology related to implementation of \ac{STM} system, such as eager vs. lazy updating. If this is not the case a description of the terminology can be found in our previous study\cite[p. 53]{dpt907e14trending}.

\subsubsection{Strong Atomicity}
As described in \bsref{sec:design_strong_weak_atomicity} strong atomicity ensures atomicity between transactional and non-transactional access. As \stmnamesp is required to support strong atomicity the implementation strategy should facilitate such access.

Lazy updating inherently supports non-transactional reads as the value associated with transactional variables are always the most recently committed value\cite[p. 2084]{herlihy2011tm}\cite[p. 21]{harris2010transactional}. As a result a non-transactional read can never read a non-committed value and atomicity is ensured because a single non-transactional read always reads the most recently committed value of a transactional variable. Ensuring atomicity for non-transactional reads is however also possible using eager updating. As an example DSTM\cite{herlihy2003software} uses a \bscode{locator} to represent the transactional variables value. The \bscode{locator} object contains a reference to the transaction that created the \bscode{locator}, the new and the old value. Based on the status of the transaction that created the current \bscode{locator}, a non-transactional read can choose to read the new value if the status is committed or the old value if status is aborted or active, thereby ensuring that the most recently committed value is always read. Choosing the correct value to read, as opposed to simply reading the most recently committed value which lazy updating allows, does however cause some overhead.

While non-transactional writes to transactional variables cannot conflict with one another, they must be tracked by the \ac{STM} system in order to ensure that any transactions with which they conflict are aborted and retried. \cite{hindman2006atomicity} proposes expanding non-transactional access to mini transactions allowing the \ac{STM} system to track their actions. Their approach goes even further supplying optimized non-transactional access which skips much of the unnecessary logging required for normal transactions. \stmnamesp could benefit from a similar approach and the selected \ac{STM} algorithm should therefore support such an approach.
 
\subsubsection{Conditional Synchronization}
The \bscode{retry} construct described in \bsref{sec:req_conditional} requires knowledge of which transactional variables has been read up to the point where a retry is requested\cite{harris2005composable}. As such the \ac{STM} system needs to maintain a set of transactional variables which has been read, for all active transactions, so that a transaction can be blocked until one of these variables change. Such a set is often referred to as a read-set\cite{dice2006transactional}\cite{harris2010transactional}\cite{herlihy2012art}. \ac{STM} systems employing lazy conflicts detection commonly use such a set to record reads for validation when the transaction is about to commit\cite{dice2006transactional}\cite{mohamedin2013bytestm}. Choosing an algorithm which already maintains a read-set will limit the overhead of the \bscode{retry} statement and should be be a priority.\andreas[inline]{Maybe mention, that we do not focus on performance, but it will also limit the simplicity of the implementation, as we do not have to mix two strategies, but leverage the existing read-set}

\subsubsection{Opacity}
\subsubsection{Library Implementation}

\subsubsection{Final Selection}
\ac{STM} algorithms can coarsely be divided into blocking and non-blocking algorithms\cite[p. 47]{harris2010transactional}. Blocking algorithms employ some form of locking in order to ensure atomicity while non-blocking do not\cite[p. 59]{herlihy2012art}. Non-blocking algorithms guarantee that the failure of one thread does not keep other threads from making progress\cite[p. 47]{harris2010transactional}\cite[p. 142]{herlihy1991wait}\cite[p. 59]{herlihy2012art}. This  makes it impossible to employ locking as the failure of some thread $T$, which is holding a lock, will keep other threads from acquiring the lock, and thereby from progressing. Non-blocking algorithms can further be distinguished by the progress guarantees they provide. Wait-freedom is the strongest of these, and guarantees that any thread makes progress on its own work if it keeps executing\cite[p. 124]{herlihy1991wait}\cite[p. 59]{herlihy2012art}. Lock-freedom is less strict as it only guarantees that if a thread $T$ keeps executing then some thread (not necessarily $T$) makes progress\cite[p. 47]{harris2010transactional}\cite[p. 60]{herlihy2012art}. The least strict progress guarantees is call obstruction-freedom\cite[p. 47]{harris2010transactional}\cite{herlihy2003obstruction}\cite[p. 61]{herlihy2012art}. As mentioned in \bsref{sec:intro_related_work}, obstruction-freedom guarantees that any thread which runs for long enough without encountering a synchronization conflict makes progress\cite{herlihy2003obstruction}[p. 1]. While all of these progress guarantees precludes deadlocks, only wait-freedom and lock-freedom precludes livelocks\cite[p. 47]{harris2010transactional}. Obstruction free algorithms have been shown to provide efficient implementations in practice\cite[p. 61]{herlihy2012art}. Especially when paired with techniques such as exponential backoff\cite[p. 147]{herlihy2012art} and contention managers\cite[p. 51]{harris2010transactional}.  Whether \ac{STM} implementations needs to be wait-free, lock-free, obstruction-free or even provide any of these guarantees at all is a ongoing discussion. Arguments have been made for even obstruction-freedom being too strong a guarantee and that \ac{STM} can be made faster by employing controlled locking\cite{ennals2006software}. Due to the observations above we choose to focus on obstruction-free and blocking algorithms.
\andreas[inline]{Vi argumenterer ikke rigtigt for vores valg. Måske referer til nogle kriterier}

\subsection{STM Algorithm}
\kasper[inline]{obstruction freedom useful in practice}
\kasper[inline]{pending commit, permissiveness}
\andreas[inline]{Analysis of privatization techniques is done by \cite{spear2007privatization}. Strong atomicity is the technique with less restrictions, but worst performance}
{'fraction_non_alphanumeric': 0.05910297610730753, 'fraction_numerical': 0.023752969121140142, 'mean_word_length': 5.829675572519084, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2554168', 'n_tokens_mistral': 3790, 'n_tokens_neox': 3392, 'n_words': 1718}