Read Copy Update

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

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

   git clone https://gitlab.fel.cvut.cz/matejjoe/list_mutex.git

2. Compile the program (simply run make in list_mutex directory)
3. Run the program (./list_mutex <number or reader threads>) and see how slow the program is
4. Replace the mutexes with rwlocks and measure improvement
5. Replace list with liburcu (userspace RCU library) list and measure improvement
6. 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/)
7. Commit the graph and code changes to your tutor (then into upload system). The graph should look roughly like this:

The rwlock is part of pthread library. You could 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 init atribute before (pthread_rwlockattr_init)

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

  • wget --no-check-certificate http://www.lttng.org/files/urcu/userspace-rcu-latest-0.10.tar.bz2

  • tar -xjf userspace-rcu-latest-0.10.tar.bz2

  • cd userspace-rcu-0.10.1/

  • ./configure --prefix=/home/me/somefolder/mybuild/output/target

  • make -j8

  • make install

• 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

Article about threads and various types of locks

Article about Userspace RCU library

User-Level Implementations of Read-Copy Update