<div dir="ltr"><div dir="ltr"><p>Hi Daniel,</p>
<p>Thank you so much for your detailed insights in the previous email. I completely agree with your point that ensuring atomicity between the token retrieval (<code>sequenceGenerator.getAndIncrement()</code>) and placing it in the queue (<code>queue.put()</code>) is crucial to avoid issues such as thread interleaving, which could lead to tokens being inserted in an unpredictable order.</p>
<p>That being said, my goal with the original test was to simulate a situation where multiple threads are competing to put items into a queue that’s already full. In this case, I wanted the threads to block naturally when the queue reaches capacity and then resume in the same order when space becomes available. Essentially, I was trying to observe how threads would be blocked in the order of their token retrieval and resume their operations when the queue allows.</p>
<p>I now see that using a <code>ReentrantLock</code> to ensure atomicity across both the token retrieval and the queue insertion can indeed prevent such interleaving. However, a challenge arises when the queue’s capacity is reached. Since <code>LinkedBlockingQueue.put()</code> causes the thread to block when the queue is full, the thread holding the lock will not be able to release it until space becomes available in the queue. This can result in a deadlock-like situation where other threads are unable to acquire the lock to retrieve their own tokens.</p>
<p>In other words, while the use of a lock ensures atomicity, it can inadvertently cause issues when the queue is full. Specifically, the thread holding the lock gets blocked while waiting for space in the queue and cannot release the lock, which in turn prevents other threads from acquiring the lock to retrieve their own tokens. This leads to a situation where multiple threads are stuck waiting for both the lock and space in the queue, causing a deadlock-like scenario.</p>
<p>This was one of the key reasons why I initially implemented the token retrieval and queue insertion steps with non-locking.</p>
<p>In the original approach, I intended for each thread to call <code>put</code>, confirm that it has entered the waiting state, and then allow the next thread to put the next sequence value and also enter the waiting state. This approach was designed to simulate a situation where the queue is already full and each thread has to wait in line for space to become available.</p></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">2024년 9월 4일 (수) 오후 8:11, Daniel Fuchs <<a href="mailto:daniel.fuchs@oracle.com">daniel.fuchs@oracle.com</a>>님이 작성:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Hi Kim,<br>
<br>
When several threads compete to put items in a queue,<br>
regardless of queue locking strategies, nothing guarantees<br>
the order in which items will end up in the queue if<br>
the action of obtaining the next element and putting<br>
it in the queue is not atomic. This is because a thread<br>
can be preempted by the scheduler at any time between<br>
two operations.<br>
<br>
Consider the following scenario:<br>
<br>
you have a sequence of ordered items a, b, c, one queue q,<br>
and two threads T1, T2 and T3:<br>
<br>
T1 starts, obtains element a, and gets preempted (the thread<br>
is paused by the scheduler).<br>
T2 starts, obtains element b and puts it in the queue.<br>
T3 starts, obtains element c and gets preempted.<br>
T1 gets scheduled again and puts a in the queue.<br>
T3 gets scheduled again and puts c in the queue.<br>
<br>
result: the queue contains b a c; regardless of whether<br>
the queue uses fair or unfair locking, the order of items<br>
in the queue will be unpredictable. And in this scenario,<br>
there isn't even any contention on the queue.<br>
<br>
To ensure that items will end up in the queue in the proper<br>
order would require an additional lock at the application<br>
level.<br>
<br>
That is - you would need to use a lock so that taking<br>
an element from the sequenceGenerator and putting it in the<br>
queue becomes atomic (with respect to the queue).<br>
<br>
so in your example you would need something like:<br>
<br>
static ReentrantLock lock = new ReentrantLock();<br>
...<br>
<br>
Thread thread = new Thread(() -> {<br>
lock.lock();<br>
try {<br>
var token = sequenceGenerator.getAndIncrement();<br>
// even if this thread gets preempted here, no<br>
// other thread will be able to obtain the next<br>
// token before our token has been put in the queue<br>
try {<br>
queue.put(token);<br>
} catch (InterruptedException e) {<br>
// restore the sequence<br>
var restored = sequenceGenerator.decrementAndGet();<br>
assert token == restored;<br>
}<br>
} finally {<br>
lock.unlock();<br>
}<br>
<br>
});<br>
thread.start();<br>
<br>
best regards,<br>
<br>
-- daniel<br>
<br>
On 04/09/2024 08:09, 김민주 wrote:<br>
> // This configuration ensures items enter the queue's waiting list in a <br>
> predictable sequence (10, 11, 12, ...) // allowing us to verify if they <br>
> are later consumed in the same order for (int i = 0; i < PRODUCER_COUNT; <br>
> i++) { Thread thread = new Thread(() -> { try { <br>
> queue.put(sequenceGenerator.getAndIncrement()); } catch <br>
> (InterruptedException e) { // ignore } });<br>
<br>
</blockquote></div></div>