Re: [Threads-devel] shared_mutex strategy

Subject: Re: [Threads-devel] shared_mutex strategy
From: Chris M. Thomasson (cristom_at_[hidden])
Date: 2010-05-20 12:18:49

"Chris M. Thomasson" <cristom_at_[hidden]> wrote in message 
news:ht1k6u$rde$1_at_dough.gmane.org...
> "Damien R" <damienrg+list_at_[hidden]> wrote in message 
> news:4BF3A2C0.6010606_at_gmail.com...
>> Anthony Williams wrote:
>>> If a reader gets the lock first, then more readers will be allowed to 
>>> get the lock until a waiting writer wakes and registers its intent.
>>
>> Yes, so in the worst case, only one reader will be able to read because
>> when the last reader unlocks the mutex, it notifies all waiters. For eg:
>> ----
[...]
>> ----
>>
>> Do you agree ?
>
> I have no time to make a proper response; sorry! Anyway...
>
>
> FWIW, I have created another "contention strategy" for an older read/write 
> mutex algorithm of mine that totally eliminates any possible chance of 
> starvation and is 100% fair.
[...]
> Here is some further context:
>
>
> http://relacy.pastebin.com/f3cab2025
> (the algorithm implemented in Relacy Race Detector)
[...]

Read all:

http://software.intel.com/en-us/forums/intel-threading-building-blocks/topic/65822

One more thing Damien... You mentioned that you only have a single writer 
that seldom requests exclusive access. IMHO, you should try experimenting 
with a simple distributed rw-mutex design. Here is some pseudo-code:
_____________________________________________________________
struct thread
{
    mutex m_mutex;

    void read_lock()
    {
        m_mutex.lock();
    }

    void read_unlock()
    {
        m_mutex.unlock();
    }

};

struct rwmutex
{
    collection<thread*> m_threads;
    mutex m_mutex;

    void register(thread* t)
    {
        mutex::scoped_lock lock(m_mutex);
        m_threads.push(t);
    }

    void unregister(thread* t)
    {
        mutex::scoped_lock lock(m_mutex);
        m_threads.pop(t);
    }

    void write_lock()
    {
        m_mutex.lock();

        for each thread in `m_threads' as i
        {
            i->read_lock();
        }
    }

    void write_unlock()
    {
        for each thread in `m_threads' as i
        {
            i->read_unlock();
        }

        m_mutex.unlock();
    }

};

_____________________________________________________________

This has some fairly decent scalability characteristics  and, registration 
aside for a moment, moves the heavy lifting to writers which should be few 
and far between. IIRC, this type of lock is called a `brlock' in Linux. One 
other thing... This design is extremely portable!

:^)