The efficiency of using a pthread_rwlock when there are a lot of readers

Question

While I am looking the man page of pthread_rwlock_unlock function, I noticed that the func will return EPERM if the calling thread does not have the ownership of a rwlock.

Since the rdlock allows multiple threads to get the lock, there must be a data structure like a link or array to store the ownerid of one specific rwlock.

Here comes the question:

The rwlock is designed to achieve efficiency when the read operation is far more frequent than write operations, but if there are large number of different threads got the read lock, each time I call a pthread_rwlock_unlock(), it takes time to find out weather the calling thread is a valid owner. what is the time complexity of this scenario..

Thanks a lot guys :)

Answer 1

n.m has provided a good answer. Your assumption of structures to hold the lock ownership is wrong on the linux implementation you tagged and is similar to the count method n.m. touches upon.

Here is an edited version of the pthread_rwlock_t type from /usr/include/bits/pthreadtypes.h

  struct
  {
    int __lock;
    unsigned int __nr_readers;
    unsigned int __readers_wakeup;
    unsigned int __writer_wakeup;
    unsigned int __nr_readers_queued;
    unsigned int __nr_writers_queued;
    int __writer;
    int __shared;
    unsigned int __flags;
  } __data;

You can see the count fields. Also pthread_rwlock_unlock.c does not return EPERM and most of the work revolves around checking writer ownership in pthread_rwlock_wrlock.c and pthread_rwlock_rdlock.c.

You can test this with a small program to declare and initialize a lock and then just unlock it.

So time complexity seem close enough to constant in this implementation but is earned by bailing on some features you may have thought or wanted to be there.

Answer 2

Note that the implementation is not required to return EPERM. The result of unlocking someone else's lock is undefined, as specified by the standard.

It is easy to achieve O(1) if the lock only stores a usage count instead of a list of owning threads. If the implementation insists on checking lock ownership, it can make the thread remember the locks it owns. Number of such locks should normally be small. Even if it isn't, multiple locks are normally acquired in the LIFO order, so the common case is covered by a stack of owned locks in the thread.