Skip to content

Backoff Lock uses an atomic value for critical section execution, and is suitable for memory-limited architectures.

License

Notifications You must be signed in to change notification settings

javaf/backoff-lock

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

6 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Exponential Backoff Lock uses an atomic value for indicating that some thread has engaged the lock and is executing its critical section (CS).

Each thread that wants to enter CS waits until the atomic lock is disengaged. Then it tries to reengage it, but as several threads might be trying the same, it may or may not succeed. So it checks if it succeeded (with the same atomic operation), and if so it done. If not it backs off for a random interval which is doubled every retry (hence exponential), and retries it all over again.

Once the thread is done with CS, it simply disengages the lock.

As all thread wait (spin) for the lock to disengage at the same time, but backoff if they fail in reengaging the lock, contention is reduced. However, this does not provide first-come-first-served fairness. But, as it only uses a single atomic value per lock it is suitable for medium-contention memory-limited architectures.

Exponential back off is a well-known technique used in Ethernet routing, presented in the context of multiprocessor mutual exclusion by Anant Agarwal and Mathews Cherian.

Course: Concurrent Data Structures, Monsoon 2020
Taught by: Prof. Govindarajulu Regeti

lock():
1. When thread wants to access critical
   section, it checks to see if lock is already
   engaged, and if so, waits (spins).
2. Once lock is disengaged it tries to reengage
   it. So do all other threads wanting to enter
   CS. Its a race between threads. So this
   thread checks to see it was the one who was
   successful, and if so its done.
3. If not, then it backs off (sleeps) for a
   random interval, and then retries again.
   Each retry the range of backoff interval
   is increased so reduce high-contention.
unlock():
1. When a thread is done with its critical
   section, it simply sets the "locked" state
   to false.

See BackoffLock.java for code, Main.java for test, and repl.it for output.

references

About

Backoff Lock uses an atomic value for critical section execution, and is suitable for memory-limited architectures.

Topics

Resources

License

Stars

Watchers

Forks

Languages