Reading/Writing from STL Map in multithreaded environment

Question

Problem: I need to write a function which returns a value for a input key from a map. If function can't found the value in map it will fetch the value from database, write into map for future use and return the same. There can be multiple threads calling this function.

I am thinking on this line:

string GetData (const int key)
{

    pthread_rwlock_rdlock(&rwlock); //read lock
    string result = "not found";
    my_map::const_iterator iter = m.find(key);
    if ( iter != m.end() )//found
    {
       result = iter->second;
    }
    else //missing
    {
        pthread_rwlock_wrlock(&rwlock); // write lock
        //fetch value from data base


        //if successful, add to the map
          m[key] = "missing data";
          result = "missing data";
     pthread_rwlock_unlock(&rwlock); // unlock write lock
    }
    pthread_rwlock_unlock(&rwlock); // unlock read lock
    return result;
}

Is this fuction thread safe? Isn't it possible for two or more threads to queue up on write lock and query the same key from database? If yes, how can I avoid that scenario?

Answer 1

This function is not thread-safe because it results in undefined behavior. When you attempt to obtain the write lock, you already hold a read lock. From the documentation for pthread_rwlock_wrlock:

Results are undefined if the calling thread holds the read-write lock (whether a read or write lock) at the time the call [to pthread_rwlock_wrlock] is made.

This solution is also not exception-safe. If an exception is thrown while the lock is held, the lock will not be released and your application will undoubtedly deadlock. You should use a C++ threading library (Boost.Thread, OpenThreads, just::thread, or something similar) that provides a C++-oriented design supporting things like scoped_lock (or lock_guard).

As for making the algorithm correct, you need something along the lines of:

obtain read lock
attempt to find object
if object exists
    return object
else
    release read lock
    obtain write lock
    if object exists
        return object
    else
        insert object
        return object

[If you use some sort of lock_guard, you don't need to worry about releasing held locks when you return]

Answer 2

You might fix it looking for the value again once you have acquired the write lock. That should be enough to fix the problem you are describing. Something like:

string GetData (const int key)
{

    pthread_rwlock_rdlock(&rwlock); //read lock
    string result = "not found";
    my_map::const_iterator iter = m.find(key);
    if ( iter != m.end() )//found
    {
        result = iter->second;
    }
    else //missing
    {
        // change from read mode to write mode
        pthread_rwlock_unlock(&rwlock); // unlock read lock
        pthread_rwlock_wrlock(&rwlock); // write lock

        // Try again
        iter = m.find(key);
        if (iter != m.end()) {
            result = iter->second;
        } else {
            //if successful, add to the map
            m[key] = "missing data";
            result = "missing data";
        }
    }
    pthread_rwlock_unlock(&rwlock); // unlock read/write lock
    return result;
}

Answer 3

Not properly implemented. You can't take the write lock while still holding the read lock, for fear of deadlock. From the man page for pthread_rwlock_wrlock on my Linux box:

The pthread_rwlock_wrlock() function shall apply a write lock to the read-write lock referenced by rwlock. The calling thread acquires the write lock if no other thread (reader or writer) holds the read-write lock rwlock. Otherwise, the thread shall block until it can acquire the lock. The calling thread may deadlock if at the time the call is made it holds the read-write lock (whether a read or write lock).

Further, you should check the return value of the calls... for example, there's an implementation-defined limit to the number of simultaneous readers.

There are also the usual issues with exception safety... consider a scope guard or try/catch block.