0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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?
$\endgroup$
2
  • $\begingroup$ I think this just shifts the global lock from the first block to the last block. That can be helpful if processing a block takes a non-trivial amount of time, but I wonder if we can do better by making copies of blocks and fiddling with atomic pointers to them. $\endgroup$
    – ccleve
    Oct 11 at 17:48
  • $\begingroup$ You might be able to do that. I would be looking into read-copy-update for a solution along those lines. $\endgroup$
    – Pseudonym
    Oct 11 at 22:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.