I am trying to write a general purpose locking algorithm which allows me to lock a range of contiguous values in a sorted array. To start with, these could be exclusive locks - so two concurrent locks must be non-overlapping. What could be a good, scalable algorithm to do this? (Scalable ~ concurrent)

A specific example could be locking a range of contiguous bytes in a file for writing.

Concretely: Let's say {a_i} is a valid sequence, for i = 0 through N-1, such that:

  1. a_j < a_k for all j, k such that 0 <= j < k < N.
  2. lock(a_j, a_k) locks all elements from a_j through a_k.
  3. While the above lock is held, another request lock(a_x, a_y) will succeed only if either a_x > a_k, or else a_y < a_j.
  • 1
    $\begingroup$ You may want to clarify "scalable". Is it more about $N$ or about the number of locks? $\endgroup$ – John L. Dec 23 '18 at 4:28
  • $\begingroup$ I would say number of locks, more concurrent. $\endgroup$ – CppNoob Dec 23 '18 at 4:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.