0%

# Introduction

RCU, this barrier-based mechanism, allows for simple epoch-based reclamation of the old copies, and the mechanism as a whole eliminates many of the atomic read-modify-write instructions, memory barriers, and cache misses that are so expensive on modern multicore systems.

• Novel extension of RCU framework that support read-only traverals concurrently with multiple updates.
• In a semi-automated way.
• Removes from the programmer the burder of handcrafting the concurrent copy management using only single pointer manipulations.
• Can be API-compatible with RCU.

• Clock-based logging mechanism.

# Algorithms

## Idea

The writer’s modifications are:

• avoid conflicts with concurrent writes.

In the following figure, the order of updating new value, 23, at write-clock and global-clock is important. Because all new object copies of the write-log become visible at once to all concurrent RLU protected section after the increment of global clock.

Many of the lock mentioned is not really calling pthread_mutex_lock() but just performing a update at a specific filed in data.

## Synchronizing Write Operations

Two approaches:

• Execute writers serially.
• Fine-grained locks.

### Execute Writers Serially

Using a global lock for each writer is simplicity of the code and the concurrency that does exist between read-only and write operations.

But the drawback is a lack of scalability.

### Fine-grained Locks

Each object that a writer modifies is logged and locked (as shown in the former figure) by the RLU mechanism.

## Fine-grained Locking Using RLU

RLU locks can be used as a fine-grained locking mechanism.

For standard lock, it is necessary to execute post-lock customized verifications to ensure that the state of the object is still the same as it was before locking. This action is unnecessary for RLU locks.

## Data Structures

Global:

• a global clock
• a global array of threads

• two write-logs: new object copies
• a pointer: point to the actual object
• the object size
• a special pointer value that indicates this is a copy (constant)
• a run counter: the thread is active or not
• a local clock: stealing mechanism
• write clock for each thread: stealing mechanism
• write clock of a thread is initially $\infty$ and write clock is updated first (than global clock), so stealing from a thread is only possible when is updates the write clock during the commit