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

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

Imagine that you are developing a multi-threaded application which proceeds concurrently many read and some write requests on a shared data structure. Your goal is to speed up the application so that there is as much read operations as possible while keeping the same amount of write operations.

Steps
  - Download a naive implementation with mutexes from git repository: <code>git clone https://gitlab.fel.cvut.cz/matejjoe/rcu.git</code>
  - Compile the program (simply run ''make'' in rcu directory)
  - Run the program (''./list_mutex <number of reader threads>'') and measure read operations and their scalability
  - 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 our server called Ritchie ''ssh username@ritchie.ciirc.cvut.cz'' (KOS 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. If you want to use your own machine, I would recommend you to use library from distribution repository (`sudo apt install liburcu-dev`). In order to compile and use the library do the following:
  * Download and compile the library: <code sh>
wget https://lttng.org/files/urcu/userspace-rcu-latest-0.11.tar.bz2
tar -xjf userspace-rcu-latest-0.11.tar.bz2
cd userspace-rcu-0.11.1/
./configure --prefix=/home/me/somefolder/mybuild/output/target
make -j8
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''

Examples how to use liburcu are available also on github: ''https://github.com/urcu/userspace-rcu/tree/master/doc/examples/list''
==== Ritchie ====
If you want to share your session with me, type ''tmux-share joel''.

==== 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]]