Locking with multiple readers

[tom9876543]

Hello

I have been reading about Semaphores and Mutexes etc. If I understand correctly they don't allow for multiple readers.

I would like to know the best way to implement a lock that allows multiple readers.

I have a possible "api" below.

What do u think? Also some code hasn't been written I have to work out the best way of implementing it.

Tom

Code: Select all

lock.getReadOnlyLock()
{

if ( this.status == READ_MODE )
  {
  //some sort of "housekeeping" to register thread has lock
  return SUCCESS;
  }

// status can only be READ or WRITE, so this must be WRITE mode
return FAIL;

}


lock.getWriteLock()
{

if ( this.status == READ_MODE )
  {
  this.status = WRITE_MODE;

  //wait until all readers have released lock (a possible deadlock)
  //also consider allowing a timeout value
  }

return SUCCESS;

}

lock.releaseReadLock()
{

//do some "housekeeping" to unattach thread

return SUCCESS;

}

lock.releaseWriteLock()
{

this.status = READ_MODE; //reset back to shared mode

return SUCCESS;

}

[bewing]

Hi,

I must assume that you are only programming for a single CPU/core at this point? You have to be a lot more careful than the code you wrote above, if any memory address can be modified at any time by multiple CPUs.

The only thing I can say about your above code, in a uniprocessor environment, is that you really want to keep a count of the number of locks -- when dealing with a multi-locking object. Not just a single flag. When the lock count goes to 0, the object is free. If you just use flags, then you're always going to need to be polling to see if freeing a particular lock was sufficient to completely free the object or not.

Oh, and I think timeouts are a really good idea. On rare occasions, bits in a computer can flip all by themselves, by accident. It's very nice to have a "brute force" method for recovering from any situation that could lock up an app, a driver, or your kernel.

[Kevin McGuire]

You might just want an atomic write and read. Such that _instead_ of the reader and writer being responsible for acquiring and releasing the lock. The support code can do this in an atomic way.

pointer-to-local-copy lockRead(pointer-to-local-copy);
So that what the resource data ever could be is copied locally for the reader.

void lockWrite(pointer-to-local-copy);
The local copy is written.

The operation should be pretty much deterministic instead of relying on tons of other factors including the many different forms of code doing a manual lock and unlock including bugs introduced by other code doing it manually.

[Combuster]

Depending on what you want, you might want to consider the lock functions to block until the lock has been acquired.

Specifically using a system optimized for reader-writer locking can be advantageous over using existing code.

Modified bakery algorithm you can use (note, increment() and fetch_and_increment() are atomic, on x86s they can be implemented with LOCK INC and lock xadd):

Code: Select all

int entries = 0;
int exits = 0;
int ticket = 0;
int readermode = writer;

lock_read()
{
  int ticket = fetch_and_increment(&ticket)
  while (ticket > entries) sleep();
  while (readermode != reader && exits != entries) sleep();
  readermode = reader;
  increment(&entries)
}

lock_write()
{
  int ticket = fetch_and_increment(&ticket)
  while (ticket > entries) sleep();
  while (exits != entries) sleep();
  readermode = writer;
  increment(&entries);
}

unlock()
{
  increment(&exits);
}

Looking at Read-Copy-Update locks might be insightful as well.

[Avarok]

Well, there's a thing about this too. You can have 50 CPU's all read the same variable at the same time just fine. They just need to lock it as "being read" so it's not writable. Writes on the other hand need to be "lock inc/lock dec'd"?

The less information we need to care about the more likely we are to realize the solution.

Is it possible to foist all the badness onto writes, since they're heuristically less common and also the most exclusive case? Make them lock it all up for a moment to write, but reads are free?

This also would encourage completing something and *then* sharing it, sharing files, copying before write, and then only flushing when we're sure. Sort of follows alot of heuristic patterns I see developing in "more efficient" systems.

[Crazed123]

You need to combine a counting variable (for reading) with a mutex (for writing).

When the write mutex is down, nobody can read or write until it comes up. When the the write mutex is up and someone tries to read, increment the read counter (to count readers) and let them read. However, nobody can down the write mutex while the read counter has a value greater than 0.

You need the read counter because otherwise the first reader of 20 to finish would mark the variable "free for writing" and the other 19 readers would wind up with inconsistent data as they try to read while the newly unblocked writer writes.

[Combuster]

If you want to provide a consistent state to all threads, then whatever you try to do, you must at least:
- have a way to stop readers from locking
- be able to tell that the resource is free.

If you don't require consistancy to some degree, then you should read on RCU

My implementation resolves to counting the amount of threads having the lock. In any case, the lockedness state of a thread must be gotten somewhere. Consider that having to synchronize caches among many CPUs for a large number of threads might cost just as much as eager searches, plus that some methods require the participating threads to be known in advance.
I wrote the code above for correctness and simplicity and being independent of the number of threads. Besides, if you make the lock section uninterruptible unless you are waiting for a writer, you can achieve high throughputs since the wait steps are skipped for all readers.

A readers-dont-write-much alternative would be something like the following. (It has writer preference and is not starvation free)

Code: Select all

char ** reader_threads_locked;
int locked;
mutex writer_lock;

lock_reader()
{
  *reader_threads_locked[thread_id] = 1;
  while (locked)
  {
    *reader_threads_locked[thread_id] = 0;
    while(locked) sleep();
    *reader_threads_locked[thread_id] = 1;
  }
}

unlock_reader()
{
  *reader_threads_locked[thread_id] = 0;
}

lock_writer()
{
  mutex_lock(writer_lock);
  locked = 1;
  for (int i = 0; i < num_threads; i++)
    while (*reader_threads_locked[thread_id] == 1) sleep();
}

unlock_writer()
{
  locked = 0;
  mutex_unlock(writer_lock);
}

In the optimal case, the locking for readers costs two writes and one read. When a writer locks, all cache coherency protocols are stressed, and all potential readers have to be checked before the lock is granted, which can cause significant delays in the processing. Besides, in the odd case that there happen to be many writers, the readers have to wait indefinately.

Crazed's solution also suffers from starvation, a more likely one at that too: if there are enough readers, the writers will have no chance ever to take down the mutex, which IMO is a serious offence.

[tom9876543]

Thanks for your ideas.

I have come up with an implementation that I think is better than the ones provided.

In terms of performance the read lock in the best case scenario consists only of an atomic increment and a comparison. Read unlock consists of only a single decrement operation.

I don't see any way to optimize further!


C# has a "single writer multiple reader" class, I got the idea of "ugradeLockToWrite" from C#.

My implementation uses win32 events - i hope there is a unix pthreads equivalent?

This lock is specifically designed to allow multiple threads to read an object and the allow only one thread to update the object. This guarantees there will never be a "race" (if used properly).

The only thing missing is timeout support.

Let me know if you have any suggestions....

Code: Select all

lock.getReadOnlyLock()
{
int tmpCount;

tmpCount = this.numReaders++; //atomic operation

if ( tmpCount < 0 )
  {
  //lock is in write mode - this should be the rare case

  //operating system suspends thread until event is ready
  wait_for_event(this.write_event);

  //redo increment as releaseWriteLock resets count
  this.numReaders++; //atomic operation
  }


//shared read lock is held

return SUCCESS;
}


//this method requires that the thread already holds a read lock
//it must prevent multiple readers doing a write....

lock.upgradeToWriteLock()
{
int tmpCount;

tmpCount = this.numWriters++; //atomic operation

if ( tmpCount == 1 )
  {
  //lock the event object so reading threads wait
  set_event(this.write_event);

  //force numReaders to negative (assume there's never 1 billion threads!)
  this.numReaders -= (2 << 30); //atomic operation

  //wait for numReaders to equal -(2 << 30) + 1
  //the +1 is necessary because this thread also held a read lock
  while ( this.numReaders > -(2 << 30) + 1 )
    sleep(0.1 seconds);

  //all existing readers have finished, lock is held
  }
else
  {
  //another thread has write lock

  return ERROR_OBJECT_MODIFIED;
  }

return SUCCESS;
}


lock.releaseReadLock()
{

//very simple....
this.numReaders--; //atomic operation

return SUCCESS;
}


lock.releaseWriteLock()
{

//reset count of readers to zero
this.numReaders = 0;

//unlock event - causes any waiting read threads to resume
reset_event(this.write_event);

//reset count of writers
this.numWriters = 0;

//lock is "unlocked"

return SUCCESS;
}

[tom9876543]

Here is an example of using the lock class. Note that it handles races by forcing the code to "retry".

Code: Select all

//local variables
int tmpA, tmpB;

anObject.lock.getReadLock();


//copy variables onto thread local stack, anObject state is always consistent
//if another writer takes ownership repeat read to get new object state
do
  {
  //as many reads as you like....
  tmpA = anObject.aVar;
  tmpB = anObject.bVar;
  }
while ( anObject.lock.upgradeToWriteLock() != SUCCESS )

//anObject is exclusively held by this thread so do as many updates as you like...
if ( tmpA > 0 )
  anObject.aVar = tmpA + tmpB;   //stupid example...

//release object lock
anObject.releaseWriteLock();

[Combuster]

The code will deadlock when a reader attempts to access the lock when a writer is waiting for it - the thread will incremented the counter and never release it causing both the reader to wait for the writer to finish, and the writer waiting for a reader that holds the lock indefinately.

tmpCount = this.numReaders++; //atomic operation

For all intents and purposes do NOT count on that line being atomic. None of the common x86 C compilers will generate the required instructions to perform that task. Even if increments are guaranteed to be atomic, this operation requires an load and an increment. To make this work you are required to generate the required LOCK XADD instruction manually.

[tom9876543]

Hi Combuster

I realise that C compilers may not produce the correct assembly code (for atomic fetch + increment), that is why I put the comment there. When its rewritten for each architecture it will have to be manually written.

Thank you for finding the mistake in the code. I have to fix getReadOnlyLock:


if ( tmpCount < 0 )
{
//lock is in write mode - undo count to allow writer to proceed
this.numReaders--; //atomic operation

[Combuster]

it should be a while() instead of an if(), if a second writer immediately follows the previous writer, both the new writer and the woken reader will be in the critical section:

t1: read lock
t1: write lock
t2: read lock (wait)
t1: unlock
t1: read lock
t1: write lock
t2: continues, also thinks he got the lock

[tom9876543]

Thank you Combuster for fixing up my mistakes. I have updated the code. Is there any other way to improve it?

Code: Select all

lock.getReadOnlyLock() 
{ 
int tmpCount; 

tmpCount = this.numReaders++; //atomic operation 

while ( tmpCount < 0 )
  { 
  //lock is in write mode - this should be the rare case 

  //lock is in write mode - undo count to allow writer to proceed
  this.numReaders--; //atomic operation

  //operating system suspends thread until event is ready 
  wait_for_event(this.write_event); 

  //redo increment as releaseWriteLock resets count 
  this.numReaders++; //atomic operation 
  } 


//shared read lock is held 

return SUCCESS; 
} 


//this method requires that the thread already holds a read lock 
//it must prevent multiple readers doing a write.... 

lock.upgradeToWriteLock() 
{ 
int tmpCount; 

tmpCount = this.numWriters++; //atomic operation 

if ( tmpCount == 1 ) 
  { 
  //lock the event object so reading threads wait 
  set_event(this.write_event); 

  //force numReaders to negative (assume there's never 1 billion threads!) 
  this.numReaders -= (2 << 30); //atomic operation 

  //wait for numReaders to equal -(2 << 30) + 1 
  //the +1 is necessary because this thread also held a read lock 
  while ( this.numReaders > -(2 << 30) + 1 ) 
    sleep(0.1 seconds); 

  //all existing readers have finished, lock is held 
  } 
else 
  { 
  //another thread has write lock 

  return ERROR_OBJECT_MODIFIED; 
  } 

return SUCCESS; 
} 


lock.releaseReadLock() 
{ 

//very simple.... 
this.numReaders--; //atomic operation 

return SUCCESS; 
} 


lock.releaseWriteLock() 
{ 

//reset count of readers to zero 
this.numReaders = 0; 

//unlock event - causes any waiting read threads to resume 
reset_event(this.write_event); 

//reset count of writers 
this.numWriters = 0; 

//lock is "unlocked" 

return SUCCESS; 
} 

[nick8325]

I think there's still a race condition here...if t1 calls getReadOnlyLock() at the same time as t2 calls releaseWriteLock(), then the following can happen:

t1: tmpCount = this.numReaders++
t2: this.numReaders = 0
t2: reset_event(this.write_event)
t1: this.numReaders--

Now numReaders is -1, even though no-one holds a write lock, and future calls to getReadOnlyLock() will never return.

Maybe, instead of "this.numReaders = 0", you should do something like "this.numReaders += (2 << 30) - 1". Or, if you replaced releaseWriteLock() with downgradeToReadLock(), you could do "this.numReaders += (2 << 30)", the opposite of what you do in upgradeToWriteLock().

[tom9876543]

Thanks Nick for figuring out my mistake.

releaseWriteLock has changed:

//reset count to zero
this.numReaders = 0

to

//reset count of readers
this.numReaders -= 1; //this thread had a read lock
this.numReaders += (2 << 30) //atomic - allow readers to continue


It is a good idea to do thing symetrically ie if you minus (2<<30) then add it back afterwards....