Atomically unlock mutex and lock other one

SAn

Hi!

I have simple Cache class consisting of Cache::Line objects. Each cache line consists of key and value. Values are stored as shared_ptr .

The cache should be thread-safe. So I have one mutex to protect the whole cache (more precise, to protect its keys), and also per-line mutexes to protect corresponding pointers.

When I have cache request (key given), I first lock whole-cache mutex, then examine the cache trying to find required line. Here I have 2 cases:

Line not found. In this case I add line with required key and null pointer. Then I lock line mutex. Then unlock whole-cache mutex so the cache may be usable by other threads while the object is being constructed, then I construct object, update pointer, then I unlock line mutex and return corresponding pointer.
Line is found. In this case I lock line mutex, read corresponding pointer, unlock both line and cache mutexes, and return the pointer.

In step 2 I must lock line mutex before reading the pointer, or else there is risk of reading null pointer (in case the object is still being constructed in concurrent thread).

The problem is that when per-line mutex is busy, the whole cache is locked while waiting for per-line mutex to be taken. What I need is to lock line mutex while atomically unlocking whole-cache mutex.

I feel that I miss something here, because I effectively need FIFO queue of threads for each cache line, where the order of threads is determined by orders of their acquisition of whole-cache mutex.

Any ideas?