3 ms·

This seems very similar to the centralized counting barrier described in [1] where each thread, upon hitting the barrier, decrements the count and spins until a

This seems very similar to the centralized counting barrier described in [1] where each thread, upon hitting the barrier, decrements the count and spins until a global "sense" boolean is reversed. The last thread to hit the barrier, resets the counter and flips the "sense" freeing up all other threads. I guess the difference is this one treats the bool as odd/even values of an integer, but does that work for n_threads > 2? [1]http://web.mit.edu/6.173/www/currentsemester/readings/R06-scalable-synchronization-1991.pdf http://web.mit.edu/6.173/www/currentsemester/readings/R06-sc...

hinkley 5y ago
These boolean arrangements ("flipping") fail when the number of watchers is high and the interval is small. The toggle can switch twice while you're queued to be run again, and then all bets are off, because it looks to you like nothing has happened. Your messaging rate can only be half of the frequency guaranteed by the kernel for waking every thread. And many OSes offer no ironclad guarantee.
- ativzzz 5y ago
  How? Only one thread, the last one when the counter is 0, flips the switch. Before the switch is flipped, the counter is reset, so the next flip will only happen when every thread once again hits the next barrier and the counter decrements to 0.
  - hinkley 5y ago
    State observed by thread 1: counter = 5, state = blue; State observed by threads 2-4: counter = [4,5,1,2,3,4,5,6], state = [blue, green, blue] Thread 1 wakes up, sees counter = 6, state = blue; Logical conclusion: system state is counter++, state unchanged. Actual scenario: counter+=6, state+=2 I believe this was first covered in my distributed computing class, but was probably most concretely illustrated in the case of concurrent garbage collection. Any unfairness in the thread scheduler can lead to some threads getting way more clock cycles than others. In low frequency scenarios you can convince yourself it's not a problem, only to be punished by success into finding out you're wrong when you have 10,000 active users instead of 10. This is especially true with spinlocks, because it's a greedy algorithm that trades fairness for responsiveness. It can result in low throughput or even priority inversion. They are a very sharp knife. Indispensable for very specific tasks, certain bloodshed for others.
    - gpderetta 5y ago
      It can be probably classified as an instance of the ABA problem.
      - hinkley 5y ago
        Precisely. I forgot the moniker but that's exactly it.
    - ativzzz 5y ago
      The counting barrier in the paper I linked is meant specifically for shared memory multiprocessors, not distributed systems, so what you're saying makes more sense. Both the counter and the state are shared variables across all threads. This clearly doesn't scale well with number of threads/processors due to cache contention, but the idea is to have a "simple" barrier. There are a few barrier implementations that operate via message passing further in the paper. But either way, the counter can never be 6 since the max counter is set to the number of threads, and each thread at the barrier decrements the counter. Once a thread is spinning, it doesn't care about the counter anymore, only the state. Once the last thread reaches the barrier, the state flips, and all threads awaken. Each thread maintains a local copy of what the "reversed state" should be to awaken. If one thread gets preference and advances to the next barrier, it will decrement the counter it reset and will spin for the global state to flip again. So even if it reaches the second barrier before any of the other threads awaken from the first, it will wait for the rest of the threads to catch up.
      - hinkley 5y ago
        The differences between multiprocessing and IPC are smaller than you think, and they have a habit of disappearing and coming back in different hardware refresh cycles. Multicore systems have hardware support for some consensus algorithms. Speed of light is practically a rounding error, but not always. And clock synchronization is... I'll use the word attenuated, since I hesitate to call it 'solved' or 'avoided'.

hinkley 5y ago

These boolean arrangements ("flipping") fail when the number of watchers is high and the interval is small. The toggle can switch twice while you're queued to be run again, and then all bets are off, because it looks to you like nothing has happened. Your messaging rate can only be half of the frequency guaranteed by the kernel for waking every thread. And many OSes offer no ironclad guarantee.

ativzzz 5y ago
How? Only one thread, the last one when the counter is 0, flips the switch. Before the switch is flipped, the counter is reset, so the next flip will only happen when every thread once again hits the next barrier and the counter decrements to 0.
- hinkley 5y ago
  State observed by thread 1: counter = 5, state = blue; State observed by threads 2-4: counter = [4,5,1,2,3,4,5,6], state = [blue, green, blue] Thread 1 wakes up, sees counter = 6, state = blue; Logical conclusion: system state is counter++, state unchanged. Actual scenario: counter+=6, state+=2 I believe this was first covered in my distributed computing class, but was probably most concretely illustrated in the case of concurrent garbage collection. Any unfairness in the thread scheduler can lead to some threads getting way more clock cycles than others. In low frequency scenarios you can convince yourself it's not a problem, only to be punished by success into finding out you're wrong when you have 10,000 active users instead of 10. This is especially true with spinlocks, because it's a greedy algorithm that trades fairness for responsiveness. It can result in low throughput or even priority inversion. They are a very sharp knife. Indispensable for very specific tasks, certain bloodshed for others.
  - gpderetta 5y ago
    It can be probably classified as an instance of the ABA problem.
    - hinkley 5y ago
      Precisely. I forgot the moniker but that's exactly it.
  - ativzzz 5y ago
    The counting barrier in the paper I linked is meant specifically for shared memory multiprocessors, not distributed systems, so what you're saying makes more sense. Both the counter and the state are shared variables across all threads. This clearly doesn't scale well with number of threads/processors due to cache contention, but the idea is to have a "simple" barrier. There are a few barrier implementations that operate via message passing further in the paper. But either way, the counter can never be 6 since the max counter is set to the number of threads, and each thread at the barrier decrements the counter. Once a thread is spinning, it doesn't care about the counter anymore, only the state. Once the last thread reaches the barrier, the state flips, and all threads awaken. Each thread maintains a local copy of what the "reversed state" should be to awaken. If one thread gets preference and advances to the next barrier, it will decrement the counter it reset and will spin for the global state to flip again. So even if it reaches the second barrier before any of the other threads awaken from the first, it will wait for the rest of the threads to catch up.
    - hinkley 5y ago
      The differences between multiprocessing and IPC are smaller than you think, and they have a habit of disappearing and coming back in different hardware refresh cycles. Multicore systems have hardware support for some consensus algorithms. Speed of light is practically a rounding error, but not always. And clock synchronization is... I'll use the word attenuated, since I hesitate to call it 'solved' or 'avoided'.