My solution involved creating a directory for each entry that was accepted by the system by one of the producers. Each one used a scheme that generated distinct names (and detected collisions with other instances, as mkdir will fail when attempting to create an existing directory).

The consumers would lock an entry by creating a lock directory within the main directory. In my scenario, creating a directory was an atomic operation in the underlying FS where that application was running, and is indeed atomic today in a lot of FS.

After achieving a succesful lock on a directory, the consumer simply procesed the data in the various files within, unlink()ing them as it proceeded. When done, the parent directory and then the lock directory were deleted in that order to prevent a second consumer getting into the same request.

This managed to run a few hundreds of producers and consumers during more than a year, without a single race condition. The overhead of this solution was very small.