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?