3 ms·

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 stat

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.

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.