Reader / writer locking algorithm

Question

I'm pretty sure there's a textbook solution to this problem, but I haven't figured it out.

I have fixed-size blocks of data arranged in a sequence: block 0, block 1, etc.. There are reader threads that read through the blocks sequentially. There are writer threads that append new data to the empty space in the last block, and then allocate a new block and continue writing if there is overflow.

You can only have one writer at a time, obviously, or they will clobber each other. You can have multiple readers at a time.

I have primitives available to add a read-lock or a write-lock to a block. The system will block until the appropriate lock is available.

I have complete control over the contents of each block. I can add flags, pointers, anything. I can also do copy-on-write and swap in blocks atomically.

So, what algorithm do I use to minimize contention?

The naive algorithm is for readers to get a read lock on the first block before they read, and writers to get a write lock on the first block before they write. A writer will then be able to write safely, but readers will all be blocked. This is essentially a single global lock.

I'm pretty sure there's a better way. What is it?

Answer 1

I think you should be able to do it with a single read/write lock and a single atomic integer variable.

Here's what I propose.

The global data:

in_last_block : rwlock
last_block : atomic int <- 0

A writer thread would look something like this:

acquire an exclusive lock on in_last_block
repeat
    write data into last_block
    if the last block is full then
        append a new block
        memory write barrier
        atomic increment last_block <- last_block + 1
until writing is done
release the exclusive block on in_last_block 

A reader thread would look something like this:

current_block <- 0
last_known_block <- atomic read last_block

do
    memory read barrier
    while current_block < last_known_block:
        scan current_block
        current_block <- current_block + 1
    last_known_block <- atomic read last_block
while current_block < last_known_block

acquire a shared lock on in_last_block
    last_known_block <- atomic read last_block
    while current_block <= last_known_block do
        scan current_block
        current_block <- current_block + 1
release the shared lock on in_last_block

Intuitively, in_last_block protects only last partly-filled (or possibly empty) block. The atomic variable last_block records which block is unsafe to read in a lock-free manner.

Then reader threads are allowed to freely do anything before, but not including, the last block. They only must acquire the shared lock in order to read the last block.

Exercises:

• What happens if a writer thread appends something while a scanner thread is between the do/while loop and the shared lock?
• Why are the memory barriers needed?
• Why is a memory barrier not needed in the last loop of the reader thread?