Browse Prior Art Database

Avoiding waiting on locks for duplicate operations

IP.com Disclosure Number: IPCOM000249077D
Publication Date: 2017-Feb-01
Document File: 2 page(s) / 51K

Publishing Venue

The IP.com Prior Art Database

Abstract

Outlined are simple methods of limiting the number of threads waiting on a lock to perform identical operations thus reducing lock contention

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 52% of the total text.

Avoiding waiting on locks for duplicate operations

Often in a computing system with multiple threads of execution, those threads synchronise access to resources with locks.

In some cases, where each thread will perform identical work to other threads, one thread of execution needs to take a lock to perform an operation but if it could be sure that another thread was already waiting to carry out the same operation it would not need to wait as well.

An example of this would be a thread that has finished using an area of memory and as a final action will perform a garbage collection sweep of the area, freeing up the memory for other processes.

The lock that controls garbage collection of the area of memory in question may already be taken. However, this other process may have already finished the sweep but not yet released the lock. This means the previous thread will either need to wait for the lock to be released or continue processing and the memory will not get cleaned until the next time a garbage collection is started.

In its simplest embodiment, this idea would consist of combining the main lock the user wants to avoid waiting on with another auxiliary "waiting" lock. An example of the process would be:

1) Try to take main lock. If succeed goto step 5. If cannot take main lock go to step 2

2) Try to take waiting lock. If succeed, no other thread is waiting goto step 3. If not succeed another thread is waiting and will perform operation, goto end

3) Wait to take main lock when acquired proceed to step 4 4) release waiting lock 5) perform operation requiring the main lock 6) unlock the main lock 7) end. In the above description, each lock can be a spinlock, mutex or other

implementation - the idea is not sensitive to the lock implementation If instead of a maximum of one thread waiting, a different maximum needs to

be set, a semaphore can be used instead of the auxiliary waiting lock. This might be advantageous if the operation is probabilistic and repeating it may improve the results. If the user does not want to rely on a particular implementation of a semaphore it is easy to implement this auxiliary waiterCount using atomic integer operations (e.g. using gcc 4.x's __sync_add_and_fetch() and __sync_sub_and_fetch()) as the user will not wait on the semaphore. In pseudo code this would be:

1) Try to take main lock. If succeed goto step 6. If cannot take main lock go to step...