Read Copy Update

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

1. Download a naive implementation with mutexes from git repository:

   git clone https://gitlab.fel.cvut.cz/esw/rcu.git

2. Compile the program (simply run make in the rcu directory)
3. Run the program (./list_mutex <number of reader threads>) and measure read operations and their scalability
4. Replace the mutexes with rwlocks and measure the improvement
5. Replace the list implementation with liburcu (userspace RCU library) list and measure the improvement
6. 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)
7. Upload your solution (the code and the graphs) as an archive to the BRUTE. The graph should look roughly like this:

The rwlock is a part of the pthread library. You can be interested in:

• pthread_rwlock_init()
• pthread_rwlock_wrlock()
• pthread_rwlock_rdlock()
• pthread_rwlock_unlock()
• pthread_rwlockattr_init()
• 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)

The liburcu should work on Linux, Cygwin and MacOS X. You can obtain 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:

  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

• ./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

Article about threads and various types of locks

Article about Userspace RCU library

User-Level Implementations of Read-Copy Update