Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming.threads > #2125

Suggestions needed for problem in lockless synch

Show all headers | View raw

Hi Group,

I am experimenting with lockless synchronization, and I would like to ask for
the group's advice. I have the basics of the technique worked out, I think,
but I am facing a problem I don't know how to solve. Let me explain.

This is for my 'libnifty' project, which is hosted at SourceForge if you are
curious (http://sourceforge.net/projects/libnifty/), but I only wish to discuss
one aspect of the project, having to to with "handles".

libnifty assigns a unique handle to each object, and API clients can only access
the object (such as a queue) via its handle. This is a technique that we have
all seen before. Unique handles are generated by incrementing a global counter:

   unsigned new_handle = NextHandle++;

We need to be able to map handles to their associated object. This is easily
done by using an array that we index via the handle. One detail is that our
handle values are unlimited, but our Map array is of finite size, so we must
access the Map via modulo:

   foo * object = Map[ handle % MapSize ];

This means that multiple handles could alias to the same map slot. We must
prevent this, so when we allocate a new handle, we check if its Map slot is
already in use, and if so, we simply discard that handle and try the next.
All this works very nicely, and to make it thread-safe, you simply protect
all manipulations of the Map table with a mutex.

While global mutexes are seldom ideal, it is not especially painful here.
The most common operation is lookup, which holds the mutex very briefly:

        unsigned slot = handle % MapSize;
        if (handle == Map[slot].handle) {
            object =  Map[slot].object;
            object->reference_count++;
        }

But the global mutex can be painful when allocating a handle, if the Map
array is almost full, because we conduct a linear search through the Map
to find an empty slot. This case would benefit from a lockless approach,
because other threads would not be locked out of the Map during the search.

However, when the Map table has completely filled, we would like to be able
to enlarge the Map table to create free space. For this purpose, the global
mutex works very nicely, because exclusive access is just what is needed.

So that's where I am. I have a lockless method for managing the handle Map,
which I can describe in more detail if anyone is curious. The lockless code
permits concurrent access to the Map for allocation, lookup, and discard
of handles. But, this method does not allow any thread to gain exclusive
access to the Map table, so the table cannot be enlarged when it fills.

My first thought is to use a global Posix readers/writer lock, where threads
would first acquire a reader lock before doing lockless operations. A thread
that is trying to allocate a new handle, and finds that the Map is full,
would promote its lock to writer, and than enlarge the table. I think this
approach would work, but it would be nice to avoid the added overhead.

Does anyone have suggestions?

Back to comp.programming.threads | Previous | Next | Find similar

Thread

Suggestions needed for problem in lockless synch Sean Burke <snburke@gmail.com> - 2014-03-23 12:57 -0700

csiph-web