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 mechanims. %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 call it as an example of multi-version concurrency control.

\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}


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 using
one of the traditional mechanisms such as spin locks or mutexes while updating. Following an update, the new readers gets to access the updated version. However readers who came in before `publishing` the update would still be guaranteed to see the older version which will get reclaimed only after all the pre-existing readers have gone away.


RCU is becoming increasingly relevant today with a userspace implementation also being released and used~\cite{urcu}.%cite urcu paper and the flocking using RCU paper ~\cite{goulet:thesis},~\cite{urcu-crowd}