4 ms·

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 loc

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.

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.