Work stealing issue while holding a lock in JDK 11

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

Work stealing issue while holding a lock in JDK 11

JSR166 Concurrency mailing list
Hi everyone,

We encountered a new issue with the new JDK 11 work stealing algorithm.

Here is a simple description of what is happening using a family analogy:
- A task has its uncle task stolen by a thread.
- Then it takes a lock and creates new subtasks
- One of its subtasks is stolen by a third thread.
- When joining the stolen subtask, it helps its uncle and steals a
cousin task (this was not the case with JDK 8)
- The cousin task is executed and the issue happens as this task uses
the same lock and the thread already owns the lock

In our case the stealing happens in a critical section:
- If the critical section is protected by reentrant lock, the thread
will interleave 2 critical sections thus creating an inconsistent state.
- If the critical section is protected by a non reentrant lock, the
thread will block itself.

You can find the source code to reproduce the issue (and a graphical
representation of the task tree) here:
https://gist.github.com/benoitbr/7f81d131673b0fd925f703a29103c3e2

Question:
Is it legitimate to spawn subtasks in a critical section?
If the answer is no, it will be difficult to respect this and code
encapsulation at the same time...

Regards,
Benoit Brouard
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
Reply | Threaded
Open this post in threaded view
|

Re: Work stealing issue while holding a lock in JDK 11

JSR166 Concurrency mailing list
On 5/2/19 4:54 AM, Benoit Brouard via Concurrency-interest wrote:

> Here is a simple description of what is happening using a family analogy:
> - A task has its uncle task stolen by a thread.
> - Then it takes a lock and creates new subtasks
> - One of its subtasks is stolen by a third thread.
> - When joining the stolen subtask, it helps its uncle and steals a
> cousin task (this was not the case with JDK 8)
> - The cousin task is executed and the issue happens as this task uses
> the same lock and the thread already owns the lock

In general, you can't rely on details of stealing beyond the property
that they maintain forward progress (unless saturated). But ...

>
> In our case the stealing happens in a critical section:
> - If the critical section is protected by reentrant lock, the thread
> will interleave 2 critical sections thus creating an inconsistent state.
> - If the critical section is protected by a non reentrant lock, the
> thread will block itself.

It seems that you want a form of keyed lock, reentrant on holding a key
rather than a thread-id. We don't supply these, but it is possible to
create one using AbstractQueuedSynchronizer. It is also possible that
StampedLock would apply here, depending on exactly how you are using it.

-Doug
_______________________________________________
Concurrency-interest mailing list
[hidden email]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest