3 ms·

How does going from awarding the lock in FIFO order to random order help?

T3OU-736 7y ago
Switching to random order from FIFO would increase the chances of breaking the convoy cycle (where a process which initially held a high-contention resource lock comes back at the end of it, to repeat the cycle again and again, since the queue/convoy didn't clear in the time it took for the process to come back) Edit: message cut off due to fat-finger
- andreareina 7y ago
  I'm still not making the connection. If processes enter the queue every N cycles on average, and hold the lock for M cycles, then you'll hit a steady queue state anytime you have N/M runnable processes. If a waiting process becomes unblocked every M cycles how does it matter whether it came from the front, back, or middle of the queue? Isn't the rate of enqueueing and dequeueing processes the same in any case?
  - muststopmyths 7y ago
    At least in Windows, the theory (edit2: theory of lock convoy mitigation) goes something like this: - There is a queue of threads contending on a lock. - There are some threads in that group that release the lock, do some context-switchless work, and need the lock again. - In a lock convoy, these would go back to the end of the queue while any other threads that were waiting on the lock now need to be readied and context-switched in. - By instead making the locking unfair and letting the next ready process grab it, there is a better chance that the threads which have quantum slices left will finish out their use of the lock and exit the convoy. Synchronization objects were redesigned in Vista around this mechanism of taking a ready thread instead of the next thread in a fair queue. I suppose something similar is at play in the article ? I don't see how just randomness fixes anything. (edit: formatting)
  - edwintorok 7y ago
    IIUC if you are holding locks for a very short amount of time you will have a higher probability of finding the lock free if you don't form queues on it in the first place, and you are able to make more progress without context switching. Although this makes the locking unfair, if each process holds onto it for only a very short amount of time avoiding the convoy and context switching overheads may be a good tradeoff for some unfairness. I don't think this would work for all kinds of locks, in particular not for locks that are held for long or unpredictable amounts of time (i.e. those involving I/O), but it should work great for in-memory data structures if you can avoid taking a pagefault while dealing with the data structure.
- IgorPartola 7y ago
  Think of the car analogy. Did fast cars are allowed to pass slow cars, average speed increases.
  - lisper 7y ago
    But that's not what random-dispatch does. You have to wait for the slow car regardless. The difference between FIFO and random dispatch is that with FIFO when the slow car finally releases the lock it gets sent to the back of the line whereas with random dispatch the slow car gets placed in a random location in the line. I don't see how this can do anything other than make the situation worse.
    - IgorPartola 7y ago
      So imagine that your queue looks like this: SSSSSFFFFF Now you will always be struck processing the slow S tasks before getting to fast F tasks. All the work has to be done, but the F tasks will always have to wait a long time. The queue would just rotate doing this. This is in contrast to random dispatch which will result in roughly this: SFSFSFSFSF Now you get to execute more tasks per minute despite not really increasing your throughout capability.
lisper 7y ago
Yeah, I don't get this either, and none of the downstream comments clarify this for me. In a FIFO system, all of the fast processes acquire the lock before the slow process comes up again in the queue. With random dispatch, the slow process will re-acquire the lock while some of the fast processes are still waiting. So I don't see how this can possibly do anything but make the situation even worse than it was.
- tbrownaw 7y ago
  One possibility is if it's not about inherently "fast" or "slow" processes. Suppose all of the processes are doing very similar asynchronous or network I/O, and need the lock at roughly set wall-clock intervals. Say 100ms, to have numbers to play with. In that case, you can dequeue something that's been waiting for 90ms and it will re-enqueue itself after another 10ms, or you can dequeue something that's been waiting for 10ms and it won't re-enqueue itself for another 90ms. In which case, FIFO would mean that processes are doing more of their waiting in the lock queue (and being woken up every time the lock changes hands), while LIFO or random order would put more of their wait time blocked on IO. Random wouldn't be as good as LIFO, but it wouldn't have nearly as high a risk of starvation.
jandrewrogers 7y ago
I think it reduces average lock graph complexity, which in turn would reduce the average number of low productivity context switches required to release lock ownership. It is a vicious cycle problem. Processes with simple lock graphs strictly queued behind processes with complex lock graphs both take a long time to run and contribute to lock graph complexity, which increases the amount of time it takes for the processes with complex lock graphs to make forward progress. Randomization of lock grants will (statistically) continuously clear out some of the simple lock graphs and thereby make forward progress on the complex lock graphs that overlap that set of locks more likely. Databases have to deal with several related problems, such as how to ensure slow operations (e.g. analytic query) do not starve fast operations (e.g. a simple insert). In recent years, designs are moving away from quasi-randomly arbitrated lock graphs and moving toward explicit control of execution scheduling, which can eliminate the need for locks altogether and ensure that all context switches are optimally productive in terms of throughput while bounded by other constraints such as latency distribution.
- sitkack 7y ago
  Are you saying one can schedule perfectly if their view of the universe is offset from our timeline?
karmakaze 7y ago
Randomness breaks pattern cycles. After the peak load passes, the remaining processes should be able to be cleared except where patterns of held locks prevents efficient progress. Think especially about processes that want two of more locks to complete.

Switching to random order from FIFO would increase the chances of breaking the convoy cycle (where a process which initially held a high-contention resource lock comes back at the end of it, to repeat the cycle again and again, since the queue/convoy didn't clear in the time it took for the process to come back) Edit: message cut off due to fat-finger

andreareina 7y ago
I'm still not making the connection. If processes enter the queue every N cycles on average, and hold the lock for M cycles, then you'll hit a steady queue state anytime you have N/M runnable processes. If a waiting process becomes unblocked every M cycles how does it matter whether it came from the front, back, or middle of the queue? Isn't the rate of enqueueing and dequeueing processes the same in any case?
- muststopmyths 7y ago
  At least in Windows, the theory (edit2: theory of lock convoy mitigation) goes something like this: - There is a queue of threads contending on a lock. - There are some threads in that group that release the lock, do some context-switchless work, and need the lock again. - In a lock convoy, these would go back to the end of the queue while any other threads that were waiting on the lock now need to be readied and context-switched in. - By instead making the locking unfair and letting the next ready process grab it, there is a better chance that the threads which have quantum slices left will finish out their use of the lock and exit the convoy. Synchronization objects were redesigned in Vista around this mechanism of taking a ready thread instead of the next thread in a fair queue. I suppose something similar is at play in the article ? I don't see how just randomness fixes anything. (edit: formatting)
- edwintorok 7y ago
  IIUC if you are holding locks for a very short amount of time you will have a higher probability of finding the lock free if you don't form queues on it in the first place, and you are able to make more progress without context switching. Although this makes the locking unfair, if each process holds onto it for only a very short amount of time avoiding the convoy and context switching overheads may be a good tradeoff for some unfairness. I don't think this would work for all kinds of locks, in particular not for locks that are held for long or unpredictable amounts of time (i.e. those involving I/O), but it should work great for in-memory data structures if you can avoid taking a pagefault while dealing with the data structure.
IgorPartola 7y ago
Think of the car analogy. Did fast cars are allowed to pass slow cars, average speed increases.
- lisper 7y ago
  But that's not what random-dispatch does. You have to wait for the slow car regardless. The difference between FIFO and random dispatch is that with FIFO when the slow car finally releases the lock it gets sent to the back of the line whereas with random dispatch the slow car gets placed in a random location in the line. I don't see how this can do anything other than make the situation worse.
  - IgorPartola 7y ago
    So imagine that your queue looks like this: SSSSSFFFFF Now you will always be struck processing the slow S tasks before getting to fast F tasks. All the work has to be done, but the F tasks will always have to wait a long time. The queue would just rotate doing this. This is in contrast to random dispatch which will result in roughly this: SFSFSFSFSF Now you get to execute more tasks per minute despite not really increasing your throughout capability.

lisper 7y ago

Yeah, I don't get this either, and none of the downstream comments clarify this for me. In a FIFO system, all of the fast processes acquire the lock before the slow process comes up again in the queue. With random dispatch, the slow process will re-acquire the lock while some of the fast processes are still waiting. So I don't see how this can possibly do anything but make the situation even worse than it was.

tbrownaw 7y ago
One possibility is if it's not about inherently "fast" or "slow" processes. Suppose all of the processes are doing very similar asynchronous or network I/O, and need the lock at roughly set wall-clock intervals. Say 100ms, to have numbers to play with. In that case, you can dequeue something that's been waiting for 90ms and it will re-enqueue itself after another 10ms, or you can dequeue something that's been waiting for 10ms and it won't re-enqueue itself for another 90ms. In which case, FIFO would mean that processes are doing more of their waiting in the lock queue (and being woken up every time the lock changes hands), while LIFO or random order would put more of their wait time blocked on IO. Random wouldn't be as good as LIFO, but it wouldn't have nearly as high a risk of starvation.

jandrewrogers 7y ago

I think it reduces average lock graph complexity, which in turn would reduce the average number of low productivity context switches required to release lock ownership. It is a vicious cycle problem. Processes with simple lock graphs strictly queued behind processes with complex lock graphs both take a long time to run and contribute to lock graph complexity, which increases the amount of time it takes for the processes with complex lock graphs to make forward progress. Randomization of lock grants will (statistically) continuously clear out some of the simple lock graphs and thereby make forward progress on the complex lock graphs that overlap that set of locks more likely. Databases have to deal with several related problems, such as how to ensure slow operations (e.g. analytic query) do not starve fast operations (e.g. a simple insert). In recent years, designs are moving away from quasi-randomly arbitrated lock graphs and moving toward explicit control of execution scheduling, which can eliminate the need for locks altogether and ensure that all context switches are optimally productive in terms of throughput while bounded by other constraints such as latency distribution.

sitkack 7y ago
Are you saying one can schedule perfectly if their view of the universe is offset from our timeline?

karmakaze 7y ago

Randomness breaks pattern cycles. After the peak load passes, the remaining processes should be able to be cleared except where patterns of held locks prevents efficient progress. Think especially about processes that want two of more locks to complete.