introduction.tex

Parallel programming is already mainstream these days. There are a wide variety
of mechanisms being used to provide synchronization and serialization.
Operating systems are a popular example for utilizing various synchronization
mechanisms. %Add citations here for spinlocks, mutexes and for RCU, with possibly links to the sourcse as opposed to publications for Linux/BSD/Solaris
With scalability being extremely important for the Operating Systems,
techniques have been proposed to reduce the overheads by utilizing lock-free
techniques. Read Copy Update~\cite{paulmck:TechReport} is one such technique which is
heavily used in the Linux Kernel. RCU has been described as a publish-subscribe
technique. Some people have also characterized it as a \emph{copy on write} tecnique, while
others have also called it an example of multi-version concurrency control.

In its simplest form, readers disable preemption when they enter the RCU read critical
section and reenable premption while exiting the
critical section. A very simple implementation can be seen in Figure ~\ref{fig:rcusimpleread}.
On the other hand updaters synchronize with the use
of one of the traditional mechanisms such as spin locks or mutexes while updating.
Following an update, any new readers gets to access the updated version. However
readers who came in before the update was `published` would still be guaranteed
to the see the older version which is reclaimed only after all the pre-existing
readers have gone away.

\begin{figure}[b]
\centering
\begin{lstlisting}
#define rcu_read_lock \
		preempt_disable
#define rcu_read_unlock \
		preempt_enable
\end{lstlisting}
\caption{A simple implementation of RCU read side primitives}\label{fig:rcusimpleread}
\end{figure}

RCU is becoming increasingly relevant today with a userspace implementation also
being released and used~\cite{urcu}~\cite{goulet:thesis}~\cite{urcu-crowd}