Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

ReaderWriterLockSlim.EnterUpgradeableReadLock() Always A Deadlock?

I'm very familiar with ReaderWriterLockSlim but tried my hand at implementing EnterUpgradeableReadLock() recently in a class... Soon after I realized that this is almost certainly a guaranteed deadlock when 2 or more threads run the code:

Thread A --> enter upgradeable read lock
Thread B --> enter upgradeable read lock
Thread A --> tries to enter write lock, blocks for B to leave read
Thread B --> tries to enter write lock, blocks for A to leave read
Thread A --> waiting for B to exit read lock
Thread B --> waiting for A to exit read lock

What am I missing here?

EDIT

Added code example of my scenario. The Run() method would be called by 2 or more threads concurrently.

public class Deadlocker
{
    private readonly ReaderWriterLockSlim _lock = new ReaderWriterLockSlim(LockRecursionPolicy.SupportsRecursion);

    public void Run()
    {
        _lock.EnterUpgradeableReadLock();
        try
        {
            _lock.EnterWriteLock();
            try
            {
                // Do something
            }
            finally
            {
                _lock.ExitWriteLock();
            }
        }
        finally
        {
            _lock.ExitUpgradeableReadLock();
        }
    }
}
like image 353
Haney Avatar asked Jan 28 '14 16:01

Haney


2 Answers

A long time after the OP, but I don't agree with the currently accepted answer.

The statement Thread B --> enter upgradeable read lock is incorrect. From the docs

Only one thread can be in upgradeable mode at any time

And in response to your comments: it is intended for a very different usage to a Read-Write pattern.

TL;DR. Upgradeable mode is useful:

  • if a writer must check a shared resource before writing to it, and (optionally) needs to avoid race conditions with other writers;
  • and it should not stop readers until it is 100 % sure it must write to the shared resource;
  • and it is quite likely a writer will decide it should not write to the shared resource once it has performed the check.

Or, in pseudocode, where this:

// no other writers or upgradeables allowed in here => no race conditions
EnterUpgradeableLock(); 
if (isWriteRequired()) { EnterWriteLock(); DoWrite(); ExitWriteLock(); } 
ExitUpgradeableLock();

gives "better performance" ÷ than this:

EnterWriteLock(); if (isWriteRequired()) { DoWrite(); } ExitWriteLock();

It should be used with care if the exclusive lock sections take a very long time due to it's use of SpinLock.


A similar lock construct

The Upgradeable lock is surprisingly similar to a SQL server SIX lock (Shared with Intent to go eXclusive) .

  • To rewrite the statement above in these terms, an Upgradeable lock says "a writer Intends to write to a resource, but wants to Share it with other readers while it [double]checks a condition to see if it should eXclusively lock and perform the write" .

Without the existence of an Intent lock, you must perform the "should I make this change" check inside an eXclusive lock, which can hurt concurrency.

Why can't you share Upgradeable?

If the Upgradeable lock was shareable with other Upgradeable locks it would be possible to have a race condition with other Upgradeable lock owners. You would therefore require yet another check once inside the Write lock, removing the benefits of doing the check without preventing other reads in the first place.

Example

If we view all lock wait/entry/exit events as sequential, and the work inside a lock as parallel, then we can write a scenario in "Marble" form (e enter; w wait; x exit; cr check resource; mr mutate resource; R Shared/Read; U Intent/Upgradeable; W eXclusive/Write):

1--eU--cr--wW----eW--mr--xWxU--------------
2------eR----xR----------------eR--xR------
3--------eR----xR--------------------------
4----wU----------------------eU--cr--xU----

In words: T1 enters the Upgradeable/Intent lock. T4 waits for the Upgradeable/Intent lock. T2 and T3 enter read locks. T1 meanwhile checks the resource, wins the race and waits for an eXclusive/Write lock. T2&T3 exit their locks. T1 enters the eXclusive/Write lock and makes the change. T4 enters the Upgradeable/Intent lock, doesn't need to make it's change and exits, without blocking T2 which does another read in the meantime.

In 8 bullet points...

The Upgradeable lock is:

  1. used by any Writer;
  2. who is likely to check first and then decide not to perform the Write for any reason (losing a race condition, or in a Getsert pattern);
  3. and who should not block Readers until it knows it must perform the Write;
  4. whereupon it will take out an exclusive lock and do so.

Upgradeable is not required if one of the following apply (including but not limited to):

  1. Contention rates between readers and writers who writelock-check-nowrite-exit are approximately zero (the write-condition check is super fast) - i.e. an Upgradeable construct doesn't help Reader throughput;
  2. The probability of having a writer which Writes once in a Write lock is ~1 because either:

    • ReadLock-Check-WriteLock-DoubleCheck is so fast it only causes race losers once per trillion writes;
    • all changes are unique (all changes must happen, races can't exist); or
    • the "last change wins" (all changes still must happen, even though they aren't unique)

It is also not required if a lock(...){...} is more appropriate, i.e.:

  1. the probability of overlapping read and/or write windows is low (locks can be as much about preventing very rare events as protecting highly likely events, not to speak of simple Memory Barrier requirements)
  2. All your lock acquisitions are Upgradeable or Write, never Read ('duh')

÷Where "performance" is up to you to define

If you view the lock object as the table, and the protected resources as the resources lower in the hierarchy, this analogy approximately holds

The initial check in a Read lock would be optional, the check within the Upgradeable lock is mandatory, therefore it can be used in a single or double check pattern.

like image 83
Andy Brown Avatar answered Nov 12 '22 04:11

Andy Brown


I recommend avoiding EnterUpgradeableReadLock(). Just use EnterWriteLock() instead. I know that seems inefficient, the upgradeable read lock is almost as bad as a write lock anyway.

  • http://ayende.com/blog/4349/using-readerwriterlockslims-enterupgradeablereadlock
  • http://joeduffyblog.com/2007/02/07/introducing-the-new-readerwriterlockslim-in-orcas
  • http://ayende.com/blog/4349/using-readerwriterlockslims-enterupgradeablereadlock
  • Is ReaderWriterLockSlim.EnterUpgradeableReadLock() essentially the same as Monitor.Enter()?
like image 1
Moby Disk Avatar answered Nov 12 '22 04:11

Moby Disk