Fast Biased Locks
Access by multiple threads to a common resource can be controlled using a bias-lock having a single owner thread selected from among the plurality of threads. The bias-lock includes an n-process lock for which non-owner processes compete and a 2-process lock for which the owner and non-owner holder of the n-process lock compete. The owner of the bias-lock can be switched to one of the non-owner threads without suspending the owner thread. An asymmetric lock can be used to eliminate the need for the 2-process lock. Bias-locks can further be extended to provide read/write bias locking mechanisms.
1 . A method for controlling access by a plurality of threads to a common resource using a bias-lock having a single owner selected from among the plurality of threads, a first sub-lock, and a second sub-lock, the method comprising:
in response to receiving a request to lock the bias-lock from a first thread:
testing the bias-lock owner;
in response to determining the first thread is the bias-lock owner, locking the first sub-lock; and
in response to determining the first thread is not the bias-lock owner, locking the second sub-lock and
locking the first sub-lock after successfully locking the second sub-lock.
2 . The method of claim 1 , further comprising:
in response to receiving a request to unlock the bias-lock from the first thread:
testing the bias-lock owner;
in response to determining the first thread is the bias-lock owner, unlocking the first sub-lock; and
in response to a determining the first thread is not the bias-lock owner unlocking the first sub-lock and
unlocking the second sub-lock the after successfully unlocking the first sub-lock.
3 . The method of claim 1 , further comprising:
in response to receiving a request from a second thread to associate the second thread as the bias-lock owner:
locking the second sub-lock;
locking the first sub-lock after successfully locking the second sub-lock;
changing the bias-lock owner to the second thread;
unlocking the first sub-lock;
ensuring a previous lock owner is not requesting to lock the bias-lock, the previous owner being the bias-lock owner prior to unlocking the first sub-lock; and
unlocking the second sub-lock.
4 . The method of claim 3 , wherein in response to receiving a request to lock the bias-lock and the first thread is the bias-lock owner, the method further comprising:
re-testing the ownership of the bias-lock after successfully locking the first sub-lock; and
in response to re-testing the ownership of the bias-lock determining the first thread is not the bias-lock owner,
unlocking the first sub-lock,
locking the second sub-lock, and
locking the first sub-lock after successfully locking the second sub-lock.
5 . The method of claim 4 , further comprising ensuring consistency of the common resource for at least the plurality of threads in response to receiving a request to lock the bias-lock and prior to testing the ownership of the bias-lock.
6 . A method for controlling access by a plurality of threads to a common resource using a bias-lock having a sub-lock and a single owner selected from among the plurality of threads, the method comprising,
in response to receiving a request to lock the bias-lock from a first thread:
testing the bias-lock owner;
in response to determining the first thread is the bias-lock owner,
ensuring the bias-lock is not granted to a non-owner thread, the non-owner thread being another of the plurality of threads; and
in response to determining the first thread is not the bias-lock owner, the first thread being the non-owner thread,
locking the sub-lock,
identifying the bias-lock as requested by the non-owner-thread, and
ensuring the bias-lock owner has granted the bias-lock to the non-owner thread.
7 . The method of claim 6 , further comprising:
in response to receiving a request to unlock the bias-lock from a first thread:
testing the bias-lock owner;
in response to determining the first thread is the bias-lock owner
testing whether the bias-lock is identified as requested by the non-owner-thread and,
in response to determining the bias-lock is identified as requested
by the non-owner-thread,
removing the identification of the bias-lock as requested by the non-owner-thread identification of the bias-lock as requested by the non-owner thread,
ensuring consistency of the common resource for at least the plurality of threads, and
identifying the bias-lock as locked by the non-owner thread; and
in response to determining the first thread is not the bias-lock owner,
ensuring consistency of the common resource for at least the plurality of threads,
removing the identification of the bias-lock as locked by the non-owner thread, and
unlocking the sub-lock.
8 . A method for controlling access by a plurality of threads to a common resource using a bias-lock configured to provide a read-lock and a write-lock and having a single owner selected from among the plurality of threads, a first sub-lock, and a second sub-lock, the method comprising,
in response to receiving a read-lock request from a first thread:
testing the bias-lock owner;
in response to determining the first thread is the bias-lock owner,
identifying the bias-lock as locked for reading by the owner and ensuring a non-owner thread has not acquired the write-lock of the bias-lock; and
in response to determining the first thread is not the bias-lock owner,
obtaining a read-lock of the second sub-lock,
locking the first sub-lock,
testing for a number of threads having the read-lock of the bias-lock,
in response to determining one non-owner thread has the read-lock of the bias-lock,
identifying the bias-lock as having a non-owner-thread-read-lock and
ensuring the owner has not obtained an owner-thread-write-lock, and
unlocking the first sub-lock.
9 . The method of claim 8 , further comprising:
in response to receiving a write-lock request from the first thread:
testing the bias-lock owner;
in response to determining the first thread is the bias-lock owner,
identifying the bias-lock as having the owner-thread-write-lock and
ensuring the bias-lock is not identified as having the non-owner-thread-write-lock and is not identified as having the non-owner-thread-read-lock; and
in response to determining the first thread is not the bias-lock owner,
obtaining a write-lock of the second sub-lock,
identifying the bias-lock as having the non-owner-thread-write-lock and
ensuring the bias-lock is not identified as having the owner-thread-write-lock and is not identified as having the owner-thread-read-lock.
10 . The method of claim 8 further comprising:
in response to receiving a read-unlock-request from the first thread:
testing the bias-lock owner;
in response to determining the first thread is the bias-lock owner,
identifying the bias-lock as not having an owner-thread-read-lock and not having an owner-thread-write-lock; and
in response to determining the first thread is not the bias-lock owner,
locking the first sub-lock,
in response to determining no non-owner-thread have requested a
read-lock of the bias-lock,
identifying the bias-lock as not having a non-owner-thread-read-lock and as not having an non-owner-thread-write-lock,
unlocking the first sub-lock, and
unlocking the second sub-lock.
11 . The method of claim 8 , further comprising:
in response to receiving a write-unlock-request from the first thread:
testing the bias-lock owner;
in response to determining the first thread is the bias-lock owner,
identifying the bias-lock as not having an owner-thread-read-lock and as not having an owner-thread-write-lock; and
in response to determining the first thread is not the bias-lock owner,
identifying the bias-lock as not having an non-owner-thread-read-lock and as not having an non-owner-thread-write-lock and unlocking the second sub-lock.