Locker with the ability to prevent hard locks.

Sep 7, 2010 at 12:34 AM
Edited Sep 7, 2010 at 7:20 PM

Hello.  I just uploaded a patch (which is not really a patch) that uses your code to design a ReadWriteLocker that is far superior (in my opinion) to the ReaderWriterLockSlim.

Example:

 

Dim Lock As New ThreadSafeReaderWriterLock(True)
Dim List   As New List(Of Integer)(New Integer {0,5,0,4,0,3,0,2,0,1})

Dim DiffLock As New ThreadSafeReaderWriterLock(True)
Dim DiffList As New List(Of Integer)(New Integer {9,8,7,6,5,4,3,2,1,0})

Public Sub FunctionToRunInMultipleThreads()
  Using ReadLock1 As IDisposable = Lock.GetReadLock()
    For Index As Integer = 0 To List.Count - 1
      List(Index) += Index
    Next

    Using WriteLock2 As IDisposable = Lock.GetWriteLock()
      For Index As Integer = 0 To List.Count - 1
        List.Add(List(Index))
      Next
    End Using

    For Index As Integer = 0 To List.Count - 1
      List(Index) -= Index
    Next

    ' Just for robustness and recursive testing.
    Using WriteLock3 As IDisposable = Lock.GetWriteLock()
      Using ReadLock4 As IDisposable = Lock.GetReadLock()
        Using WriteLock5 As IDisposable = Lock.GetWriteLock()
          For Index As Integer = 0 To (List.Count \ 2) - 1
            ' Removes an integer at the end of the list.
            List.RemoveAt(List.Count - 1)
          Next
        End Using
      End Using
    End Using
  End Using

  Using ReadLock6 As IDisposable = DiffLock.GetReadLock()
    For Index As Integer = 0 To DiffList.Count - 1
      DiffList(Index) += Index
    Next

    Using WriteLock7 As IDisposable = DiffLock.GetWriteLock()
      For Index As Integer = 0 To DiffList.Count - 1
        DiffList.Add(DiffList(Index))
      Next
    End Using

    For Index As Integer = 0 To DiffList.Count - 1
      DiffList(Index) -= Index
    Next

    ' Just for robustness and recursive testing.
    Using WriteLock8 As IDisposable = DiffLock.GetWriteLock()
      Using ReadLock9 As IDisposable = DiffLock.GetReadLock()
        Using WriteLock10 As IDisposable = DiffLock.GetWriteLock()
          For Index As Integer = 0 To (DiffList.Count \ 2) - 1
            ' Removes an integer at the end of the list.
            DiffList.RemoveAt(DiffList.Count - 1)
          Next
        End Using
      End Using
    End Using
  End Using
End Sub

 

Notice that there is NO UPGRADE LOCKS.  Upgrade locks only complicate code.  And their purpose is to make you more aware of how thread locking is being done so you don't cause hard locks.  But this locker prevents hard locks, so that isn't an issue.

So each of list can have its own lock since they are unique.  But the ThreadSafeReaderWriterLock (to be renamed in the future) keeps track of all locking that occurs.  So if a hard lock does occur, it recognizes it, and lets just one thread go through.  When that hard lock is finished, it resumes with normal thread locking.  It is fully recursive, both within itself, between multiple locks, and between each type of lock.

With community driven support, and spin locks, I believe Microsoft's poorly implemented ReaderWriterLock and ReaderWriterLockSlim could be depreciated.  With newer non-blocking technologies, all lockers may eventually be depreciated.  But until then, this is our best option.

Hopefully you find this interesting,

TamusJRoyce

Coordinator
Sep 7, 2010 at 7:34 PM

Hi TamusJRoyce, do you mean your lock can solve the following deadlock? (pseudocode)

Thread 1:

lock(A)
{
    lock(B)
    {
    }
}


Thread 2:

lock(B)
{
    lock(A)
    {
    }
}
Sep 8, 2010 at 8:17 AM
Edited Sep 20, 2010 at 2:57 PM

Yes.  If Lock(a) and Lock(b) represents write-locking.

Otherwise if Lock(a) and Lock(b) are any combination of read-locking and write-locking, then yes as well.  But it depends on what types of locks and what order they are done in that would result in a hard lock.  If Lock(a) and Lock(b) where both read locks, no hard locks would occur.  Which is where my my algorithm comes in.

There is a global list which keeps track of how locking occurs.  If the infamous hard lock is detected  (taking into account the Lock Type Pattern), it sets global variable to the threads ManagedId.  Since that global variable holds a value <> -1, it is the only thread allowed to run in both read locking and write locking.  NeedsLockedForReading() and NeedsLockedForWriting() both return false for all threads other than the super thread.  Each time unlocking is done, checking is done to determine if there is no longer any threads in a position to cause hard locking.  Once that has happened, your normal thread locking resumes.

This is probably a different topic (or something you've seen me write before), but I would like a MIT/LGPL/MS-PL tri-license to be used, as I've been reading that the MIT doesn't prevent algorithms from being patented as closed technology, charging for it or preventing its use--even if the source code is open source.  The tri-license would need to be worded such that the user can choose any of the three licenses to take care of the patent issue.  MIT would need to preside over L-GPL, and L-GPL preside over MS-PL, if any conflicts are to occur while using the tri-license, if the user chooses the tri-license instead of selecting a choice between these three.  And all openness on the MIT license would need to be respected.

I can get a working example in VB first, and then C#.  Is Visual Studio 2008 OK?

 


 

Other info:

It really was a fun puzzle to solve.  But I think the worse case scenerio for these checks is O(n^4), where n is the recursive embedding (upgrade/downgrade locks in ReaderWriterLock/ReaderWriterLockSlim).  I haven't dissected it to see if that's true, but that's my guess after writing it.

And that's OK for any instance where ReaderWriterLockSlim is used.  It only allowed 1 of these anyway.

I'm also using this code evasively in a custom list (where for each loops use a read lock, and every public property/method uses appropriate locking using this lock--this is because I don't have .NET 4.0 with its non-blocking lists), and it still seems to perform OK.  But this is where I am really hoping community support could help.

 


 

Edit:  The above algorithm has been revised.  It is no longer O(n^4), as the list tracking to detect when hard locks is gone.  It now almost allows hard locks to occur.  Then right before they do, it sets a super thread which is allowed to run until the otherwise hard locked thread completes.  This drastically improves both memory usage and performance.

Coordinator
Sep 8, 2010 at 8:12 PM
Hi,

Sounds great! So why don't you start a new codeplex project based on your code? I really don't mind if it's based off my code, plus then you could choose the license that you prefer. One of the reasons I wrote this one is so I can use it as a relatively easy-to-understand example on how to use the lock/wait/pulse methods. I suspect that your class is a bit more complicated :)

Regards,
Jean-Paul Mikkers


On 9/8/2010 10:17 AM, TamusJRoyce wrote:

From: TamusJRoyce

Yes.  If Lock(a) represents read-locking, and Lock(b) represents write-locking.

There is a global list which keeps track of how locking occurs.  If the infamous hard lock is detected, it sets global variable to the threads ManagedId.  Since that global variable holds a value <> -1, it is the only thread allowed to run in both read locking and write locking.  NeedsLockedForReading() and NeedsLockedForWriting() both return false for all threads other than that thread.  Each time unlocking is done, that special anti-hard locked thread checks to see if it is no longer in a position to cause hard locking.  Once that occurs, your normal thread locking resumes.

I would like a tri-licensed MIT/LGPL/MS-PL license to be used, as I've been reading that the MIT doesn't prevent algorithms from being patented as closed technology, charging for it or preventing its use--even if the source code is open source.  The tri-license would need to be worded such that the user can choose any of the three licenses to take care of the patent issue.  MIT would need to preside over L-GPL, and L-GPL preside over MS-PL, if any conflicts are to occur while using the tri-license, if the user chooses the tri-license instead of selecting a choice between these three.  And all openness on the MIT license would need to be respected.

I can get a working example in VB first, and then C#.  Is Visual Studio 2008 OK?

 


Sep 9, 2010 at 12:39 AM

That sounds like an excellent idea.  Without the simplicity you've given here, I wouldn't have been able to figure out the complex locker that I have now.

Thinking of it now, I will try to keep your original thread locker in a separate location than the extra functionality I have added, so people trying to learn it's functionality can see its simplicity here.  And if you don't mind me re-licensing it using your MIT and the added choices of choosing L-GPL and MS-PL, then that is what I was wanting most.  Sorry for my fear of my code being patented as non-open source.

Do you mind if I have a link from that project to this one?  You really do deserve credit, since I would have never guessed how to use the pulse method.

Thanks,

TamusJRoyce

Coordinator
Sep 10, 2010 at 9:28 PM
Cool, let me know what the project name will be, I'm looking forward
to it.
Sep 15, 2010 at 2:35 PM

This is now located here (http://nohardlockrwlocker.codeplex.com)

Mar 3, 2011 at 2:50 PM

How do you over come the problems associated with multiple readers upgrading to write locks, without allowing for state corruption between test and action?

vis: Consider the following code:

//A: Read lock taken
using (lock.GetReadLock())
{
   foreach(var obj in myList)
   {
       if (obj.Property == testValue)
      {
         //B: Upgrade to Write lock
         using (lock.GetWriteLock())
         {
            obj.Property = newValue;
         }
      }
   }
}


 

If I am not mistaken, you code would allow the case where two threads (Thread1 and Thread2) are both executing this loop with varying interlacing over the collection. If this is so, then yout could get incosistent results at the end of the loop, where some items have had their final property's value set by Thread1 and others by Thread2.

FYI: It is this case that UpgradeReadLock is made to resolve. Not to resolve deadlocks (which, unless I am mistaken, is what you mean when you refer to hardlocks. If I am wrong please do correct me).