How to implement readers-writer lock with timeout, a hard question.

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

How to implement readers-writer lock with timeout, a hard question.

"Chen Jun (陈军)"
Hello everyone, I'm new to mailing list. I think this list is the proper
place to ask my question.

Is there an implementation of readers-writer lock with timeout support
on Linux(no doubt, using glibc). I've known quite some implementation of
readers-writer lock without timeout, like that in boost and ACE(by
Douglas C. Schmidt). By saying "timeout support", I mean, if some thread
acquires read or write lock but fails to get it before "timeout"
elapses, the calling thread returns as if the thread has never acquired
lock.

I had not seen an implementation on Windows 2000/XP either, but I
managed to implement it some months ago, with help of the great
QueueUserAPC Win32 function. Now, I'd like to know how to implement
readers-writer lock with timeout on Linux. Can it be implemented with
glibc or some more kernel functions must be added to fulfill this?
Searching on google for weeks and no luck. Does anyone have an idea.
Thanks in advance.

Reply | Threaded
Open this post in threaded view
|

Re: How to implement readers-writer lock with timeout, a hard question.

Steve Munroe
[hidden email] wrote on 01/15/2008 07:52:15 PM:

> Hello everyone, I'm new to mailing list. I think this list is the proper
> place to ask my question.
>
> Is there an implementation of readers-writer lock with timeout support
> on Linux(no doubt, using glibc). I've known quite some implementation of
> readers-writer lock without timeout, like that in boost and ACE(by
> Douglas C. Schmidt). By saying "timeout support", I mean, if some thread
> acquires read or write lock but fails to get it before "timeout"
> elapses, the calling thread returns as if the thread has never acquired
> lock.
>
> I had not seen an implementation on Windows 2000/XP either, but I
> managed to implement it some months ago, with help of the great
> QueueUserAPC Win32 function. Now, I'd like to know how to implement
> readers-writer lock with timeout on Linux. Can it be implemented with
> glibc or some more kernel functions must be added to fulfill this?
> Searching on google for weeks and no luck. Does anyone have an idea.
> Thanks in advance.
>

look at the posix documentation for pthread_rwlock_*. This API supports
read/write locks with and without time-out.

You can find lots of references using google. For example:

http://www.linuxhowtos.org/manpages/3p/pthread_rwlock_timedrdlock.htm

Reply | Threaded
Open this post in threaded view
|

Re: How to implement readers-writer lock with timeout, a hard question.

"Chen Jun (陈军)"
Steve Munroe 写道:

> [hidden email] wrote on 01/15/2008 07:52:15 PM:
>
>  
>> Hello everyone, I'm new to mailing list. I think this list is the proper
>> place to ask my question.
>>
>> Is there an implementation of readers-writer lock with timeout support
>> on Linux(no doubt, using glibc). I've known quite some implementation of
>> readers-writer lock without timeout, like that in boost and ACE(by
>> Douglas C. Schmidt). By saying "timeout support", I mean, if some thread
>> acquires read or write lock but fails to get it before "timeout"
>> elapses, the calling thread returns as if the thread has never acquired
>> lock.
>>
>> I had not seen an implementation on Windows 2000/XP either, but I
>> managed to implement it some months ago, with help of the great
>> QueueUserAPC Win32 function. Now, I'd like to know how to implement
>> readers-writer lock with timeout on Linux. Can it be implemented with
>> glibc or some more kernel functions must be added to fulfill this?
>> Searching on google for weeks and no luck. Does anyone have an idea.
>> Thanks in advance.
>>
>>    
>
> look at the posix documentation for pthread_rwlock_*. This API supports
> read/write locks with and without time-out.
>
> You can find lots of references using google. For example:
>
> http://www.linuxhowtos.org/manpages/3p/pthread_rwlock_timedrdlock.htm
>
>  
Thank you very much for your answer, I tried it with a simple program on
SuSE 10.1(glibc 2.4 perhaps) and it works as expected.

However, I really want to know how it is implemented, since I'd like to
made some improvement. Such as:
* Recursively acquire the same type of lock should be allowed.
* Write-waiters should have more priority over read-waiters. This
introduces a new behavior: when a write-waiter times out, it should
check whether there have been some read-waiters waiting, if so, wake up
those read-waiters.
* Read-lock owners can upgrade to writer-lock owners without first
release read lock.

I look into the definition of pthread_rwlock_timedrdlock, there is a
mysterious lll_futex_timed_wait to carry out the wait operation. And in
pthread_rwlock_unlock, there is lll_futex_wake to do the wakeup. What
are those futex operations, are they documented somewhere?

My simple test code :

#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <time.h>
#include <assert.h>
#include <pthread.h>

struct SThreadParam
{
        pthread_rwlock_t *prwl;
        int hold_seconds;
};

void * _thread_lock_write(void *param)
{
        SThreadParam *ptp = (SThreadParam*)param;
        pthread_rwlock_t *prwl = ptp->prwl;

        int ret = pthread_rwlock_wrlock(prwl);
        printf("pthread_rwlock_wrlock()=%d\n", ret);
        if(ret!=0)
                return NULL;

        // hold the lock for some seconds
        sleep(ptp->hold_seconds);

        ret = pthread_rwlock_unlock(prwl);
        printf("pthread_rwlock_unlock()=%d\n", ret);

        return NULL;
}


void DoTest()
{
        int re;
        pthread_rwlock_t rwl, *prwl = &rwl;
        re = pthread_rwlock_init(&rwl, NULL);
        assert(re==0);

        SThreadParam tp = {0};
        tp.prwl = &rwl;
        tp.hold_seconds = 5; // hold read-lock for this much seconds.

        pthread_t thrd;
        memset(&thrd, 0, sizeof(thrd));
        re = pthread_create(&thrd, NULL, _thread_lock_write, &tp);
        assert(re==0);

        sleep(2); // !! hopes that _thread_lock_write() has acquired the lock

        // try acquire read lock for 1 second, should fail due to timeout
        time_t endtime = time(NULL)+1;
        timespec end_abstime = { endtime, 0 };
       
        re = pthread_rwlock_timedrdlock(prwl, &end_abstime);
        if(re==ETIMEDOUT)
        {
                printf("Good, first timedrdlock return ETIMEDOUT(%d)\n", ETIMEDOUT);
        }
        else
                printf("Unexpected first timedrdlock ret(%d)\n", re);

        // second try read-lock acquire, should success.
        end_abstime.tv_sec = time(NULL)+5;
        end_abstime.tv_nsec = 0;

        re = pthread_rwlock_timedrdlock(prwl, &end_abstime);
        if(re==0)
        {
                printf("Good, second timedrdlock return success(0)\n");
                pthread_rwlock_unlock(prwl);
        }
        else
                printf("Unexpected second timedrdlock ret(%d)\n", re);

        void *thrd_ret;
        pthread_join(thrd, &thrd_ret);

        pthread_rwlock_destroy(&rwl);
}


int main()
{
        DoTest();

        return 0;
}


Reply | Threaded
Open this post in threaded view
|

Re: How to implement readers-writer lock with timeout, a hard question.

"Chen Jun (陈军)"
Chen(陈)Jun(军) 写道:
>
> I look into the definition of pthread_rwlock_timedrdlock, there is a
> mysterious lll_futex_timed_wait to carry out the wait operation. And
> in pthread_rwlock_unlock, there is lll_futex_wake to do the wakeup.
> What are those futex operations, are they documented somewhere?
>
>
Oh, I've found futex document in Linux man pages, thanks.