Some threads might be starved because of the exponential back-off time.
khans
This approach is maximally unfair because threads that have to wait for resources, have to wait longer and are less likely to grab the lock because of the exponential back-off.
woohoo
Can we just set a random delay amount to increase fairness?
ask
According to my understanding, exponential back-off might be a bad idea when there is periodic window of high contention. On the other hand, exponential back-off might work reasonably well when the contention windows are sparse.
googlebleh
@woohoo Sure, that might be fair, but it could result in poor performance, especially with a small number of threads. In order to implement this, you should probably adjust the range of values you randomly choose from based on the number of threads who could potentially grab the lock.
Adding a random delay also doesn't solve the starvation and scalability problems.
vasua
This sort of exponential backoff is also used in a number of other applications, particularly in network applications such as with Ethernet and WiFi. We talked about it briefly in 18-349.
https://en.wikipedia.org/wiki/Exponential_backoff
o__o
Why would you use exponential backoff?
hdd
Exponential backoff in simple analogy is a way of reducing contention by saying to a thread seeking a lock: Instead of requesting every clock cycle, request for a lock by some random amount of time selected ( but this random time is exponentially increasing after every attempt). This prevents contention of the lock and allows other threads seeking the lock to acquire the lock.
If all the threads implement this, then there is hardly any contention, as each thread is exponentially backed off by a different amount, and when they try to acquire for a lock, they might be the only thread attempting for the action. So if the lock is free, the thread will get it. However, there are issues of starvation if the lock is not served after a few backoffs.
fxffx
Exponential back-off can cause severe unfairness because a loser thread will have lower and lower chance to try for the lock, and possibly remain a loser forever.
Some threads might be starved because of the exponential back-off time.
This approach is maximally unfair because threads that have to wait for resources, have to wait longer and are less likely to grab the lock because of the exponential back-off.
Can we just set a random delay amount to increase fairness?
According to my understanding, exponential back-off might be a bad idea when there is periodic window of high contention. On the other hand, exponential back-off might work reasonably well when the contention windows are sparse.
@woohoo Sure, that might be fair, but it could result in poor performance, especially with a small number of threads. In order to implement this, you should probably adjust the range of values you randomly choose from based on the number of threads who could potentially grab the lock.
Adding a random delay also doesn't solve the starvation and scalability problems.
This sort of exponential backoff is also used in a number of other applications, particularly in network applications such as with Ethernet and WiFi. We talked about it briefly in 18-349.
https://en.wikipedia.org/wiki/Exponential_backoff
Why would you use exponential backoff?
Exponential backoff in simple analogy is a way of reducing contention by saying to a thread seeking a lock: Instead of requesting every clock cycle, request for a lock by some random amount of time selected ( but this random time is exponentially increasing after every attempt). This prevents contention of the lock and allows other threads seeking the lock to acquire the lock. If all the threads implement this, then there is hardly any contention, as each thread is exponentially backed off by a different amount, and when they try to acquire for a lock, they might be the only thread attempting for the action. So if the lock is free, the thread will get it. However, there are issues of starvation if the lock is not served after a few backoffs.
Exponential back-off can cause severe unfairness because a loser thread will have lower and lower chance to try for the lock, and possibly remain a loser forever.