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

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

Imagine that you are developing a multi-threaded application which performs many read and some write requests on a shared data structure concurrently. 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/esw/rcu.git</code>
  - Compile the program (simply run ''make'' in the 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 the improvement
  - Replace the list implementation with liburcu (userspace RCU library) list and measure the improvement
  - For rwlocks and librcu implementations, measure the number of reads per second for different 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)
  - Upload your solution (the code and the graphs) as an archive to the [[https://cw.felk.cvut.cz/brute/|BRUTE]]. The graph should look roughly like this:
  {{:courses:b4m36esw:labs:rcu.svg.png?nolink&300|}}
==== pthread rwlocks ====
The rwlock is a part of the pthread library. You can 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 initialize the attribute before (pthread_rwlockattr_init)

==== Userspace RCU ====
The liburcu should work on Linux, Cygwin and MacOS X. You can obtain [[http://liburcu.org|liburcu]] from your Linux distribution repository or compile it yourself. If you want to use your own machine, I recommend to use the library from your Linux distribution repository (`sudo apt install liburcu-dev`). 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.13.tar.bz2
tar -xjf userspace-rcu-latest-0.13.tar.bz2
cd userspace-rcu-0.13.1/
./configure --prefix=/home/me/somefolder/mybuild/output/target
make -j8
make install</code>
  * ''./doc/examples/list/'' contains useful examples
  * Add the library into your Makefile
    * add ''-lurcu'' or other rcu flavour into ''$LIBS'' (before ''-lpthread'')
    * add a path to the include directory ''-I/home/me/somefolder/mybuild/output/target/include'' into ''$INCLUDES''
    * add a path to the library directory ''-L/home/me/somefolder/mybuild/output/target/lib'' into ''$LFLAGS''

Examples how to use the liburcu are available also on github: ''https://github.com/urcu/userspace-rcu/tree/master/doc/examples/list''


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