====== Read Copy Update ======

===== Task assignment =====

Imagine that you are developing a multi-threaded application which proceeds concurrently many read and write requests on a shared data structure. Your goal is to speed up the application and achieve processing of 50k write operations per second and as much read operations as possible.

Steps
  - Download a naive implementation with mutexes from git repository: <code>git clone https://gitlab.fel.cvut.cz/matejjoe/list_mutex.git</code>
  - Compile the program (simply run ''make'' in list_mutex directory)
  - Run the program (''./list_mutex <number or reader threads>'') and see how slow the program is
  - Replace the mutexes with rwlocks and measure improvement
  - Replace list with liburcu (userspace RCU library) list and measure improvement
  - For rwlocks and librcu, measure reads with various number of reader threads and plot the results into a graph (for example from one to twenty readers) – use **sufficient hardware** (at least 8 cores -- total number of threads shouldn't be larger than physical cores) – you can use some of remote servers such as k333stu1.felk.cvut.cz (password can be set on [[https://cw.felk.cvut.cz/password/]])
  - Commit the graph and code changes to your tutor (then into upload system). The graph should look roughly like this:
  {{:courses:b4m36esw:labs:rcu.svg.png?nolink&300|}}
==== pthread rwlocks ====
The rwlock is part of pthread library. You could be interested in:
  * [[https://linux.die.net/man/3/pthread_rwlock_init|pthread_rwlock_init()]]
  * [[https://linux.die.net/man/3/pthread_rwlock_wrlock|pthread_rwlock_wrlock()]]
  * [[https://linux.die.net/man/3/pthread_rwlock_rdlock|pthread_rwlock_rdlock()]]
  * [[https://linux.die.net/man/3/pthread_rwlock_unlock|pthread_rwlock_unlock()]]
  * [[https://linux.die.net/man/3/pthread_rwlockattr_init|pthread_rwlockattr_init()]]
  * [[http://man7.org/linux/man-pages/man3/pthread_rwlockattr_setkind_np.3.html|pthread_rwlockattr_setkind_np()]] – reader/writer priority – use PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP and don't forget to init atribute before (pthread_rwlockattr_init)

==== Userspace RCU ====
The liburcu should work on Linux, Cygwin and MacOS X. You can obtain [[http://liburcu.org|liburcu]] from distribution repository or compile yourself. I would recommend you compiling the library because libraries in repositories are usually a bit old. In order to compile and use library do following:
  * Download and compile library
    * <code>wget --no-check-certificate http://www.lttng.org/files/urcu/userspace-rcu-latest-0.10.tar.bz2</code>
    * <code>tar -xjf userspace-rcu-latest-0.10.tar.bz2</code>
    * <code>cd userspace-rcu-0.10.1/</code>
    * <code>./configure --prefix=/home/me/somefolder/mybuild/output/target</code>
    * <code>make -j8</code>
    * <code>make install</code>
  * In ./doc/examples/list/ are useful examples
  * Add library into Makefile
    * add ''-lurcu'' or other rcu flavour into ''$LIBS'' (before ''-lpthread'')
    * add path to include directory ''-I/home/me/somefolder/mybuild/output/target/include'' into ''$INCLUDES''
    * add path to library directory ''-L/home/me/somefolder/mybuild/output/target/lib'' into ''$LFLAGS''

==== Supplementary materials ====

[[http://www.compsci.hunter.cuny.edu/~sweiss/course_materials/unix_lecture_notes/chapter_10.pdf|Article about threads and various types of locks]]

[[https://lwn.net/Articles/573424/|Article about Userspace RCU library]]

[[http://www.efficios.com/pub/rcu/urcu-main.pdf|User-Level Implementations of Read-Copy Update]]