[concurrency-interest] lockfree programming and threads of different priorities

Oleksandr Otenko oleksandr.otenko at oracle.com
Thu Jul 3 14:17:27 EDT 2014


On 03/07/2014 18:39, Andy Nuss wrote:
> None of the code in any of the critical sections of my type of lock 
> (which does not use parking) tries to ever acquire other locks.

Then it isn't really */a deadlock/*.

What you describe below seems feasible. But then thread 5 need to keep 
making progress on some other task. If it keeps spinning indefinitely, 
waiting for the lock to be released, then it isn't really lock-free. 
(the definition of the latter is: suspend any one thread - some other 
thread makes progress; here we have thread 4 suspended, no thread making 
progress)

An example of a lock-free scenario would be: all threads computing a 
value and attempt to CAS. Then suspending any thread doesn't preclude 
some other thread succeeding to CAS. (then wait-free is: all threads 
either succeed to CAS, or don't need to recompute the value)

Alex


> Still:
>
> what if a thread at priority 4 calling my remove() method of an object 
> enters the lock() function for the lock owned by the instance 
> implementing remove().  That critical section starts calling a 
> HashMap.remove(...).  At some instant before unlock() is called (while 
> remove()) is in the critical section, a thread of priority 5 wakes up 
> and begins calling the add() method for that same object.  It tries to 
> enter the critical section for the lock being held by the thread of 
> priority 4 (my guess is that that should be suspended now in some 
> multicpu scenarios due to the thread of priority 5), and because the 
> thread of priority 5 is trying to enter this unparking lock, thread 4 
> never leaves its critical section.
>
> If this is all true, then how are lockfree queues implemented in the 
> first place, as they seem to be the basic of a proper parking lock?
>
>
> On Thursday, July 3, 2014 9:26 AM, Nathan Reynolds 
> <nathan.reynolds at oracle.com> wrote:
>
>
> A true deadlock requires a circular wait, no preemption, resource 
> holding and mutual exclusion.  Your lock satisfies the last 3 
> requirements.  So, you simply need to find a circular wait.  This 
> would mean 2 locks and 2 threads which each thread holding a lock and 
> waiting on a lock.  This is easily revealed by taking a stack trace of 
> all of the threads once the deadlock happens.  You then have figure 
> out the N locks and N threads that are in a circular wait.
>
> When implementing locks, threads will park and unpark.  This means a 
> queue of blockers for the lock.  If there is a slight mistake, then 
> threads could end up stuck in the queue because they missed being 
> woken up.  Depending upon the queue implementation, then threads could 
> think they are in the queue but end up being overwritten.  I find that 
> dealing with blocking to be the most tricky part of implementing a lock.
> -Nathan
> On 7/3/2014 7:03 AM, Andy Nuss wrote:
>> Hi,
>>
>> I am using a class that I wrote called SimpleLock.  It holds one 
>> AtomicBoolean and a public lock() and unlock() method as would make 
>> sense.
>>
>> All my datastructures that have unthreadsafe members that are 
>> modified and/or read together (often both) use the model:
>>
>> myprivatelock.lock();
>> try {
>>     ... do some work on unthread safe private members
>> } finally {
>> myprivatelock.unlock();
>> }
>>
>> I am seeing some deadlocks in the SimpleLock.lock() function in my 
>> various pools of threads. My model is to use threadpools, all threads 
>> within each running at the same priority.  However, the various 
>> threadpools run at different priorities.
>>
>> Currently, it is possible in a class:
>>
>> class MyDeadLockingClass {
>>
>> public add ()
>>       {
>> ...use SimpleLock's lock and unlock
>>       }
>>
>> private remove ()
>>       {
>> ...use SimpleLock's lock and unlock
>>       }
>> }
>>
>> For the add() and remove() functions to be called within different 
>> threadpool threads, and thus at different thread priority.  Could 
>> this be a big problem, or is it still safe?  My guess is that it is 
>> safe, and I have to look for the cause of deadlocking elsewhere.
>>
>> Andy
>>
>>
>> _______________________________________________
>> Concurrency-interest mailing list
>> Concurrency-interest at cs.oswego.edu  <mailto:Concurrency-interest at cs.oswego.edu>
>> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
>
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu 
> <mailto:Concurrency-interest at cs.oswego.edu>
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>
>
>
>
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs.oswego.edu/pipermail/concurrency-interest/attachments/20140703/9ce43303/attachment-0001.html>


More information about the Concurrency-interest mailing list