3 ms·

> Afraid of deadlocks making in mutex code? No. You literally cannot use a mutex in interrupt service routines. If you fail to understand why, then you don't

> Afraid of deadlocks making in mutex code? No. You literally cannot use a mutex in interrupt service routines. If you fail to understand why, then you don't understand fundamental OS and/or device driver issues and need to study up on that a bit more. This isn't something you use userland tools to solve either. You're arguing for a methodology in a use case where its literally impossible to use mutexes and/or locking. The only reasonable software engineering decision here is to write lock-free code with guarantees of forward progress in these situations. Its not easy. A lot of people mess it up. But that's what you have to do. No one ever said kernel hacking was easy. Someone has to write this code, and whoever does will likely use a lock-free methodology. This is where atomics and barriers shine. > Lock-free code by itself doesn't guarantee forward progress. I don't think you understand what lock-free code means. It literally means code that has guarantees for forward progress. Its very difficult to write lock-free code. Very, very difficult. But the methodology is well known and well documented. (https://preshing.com/20120612/an-introduction-to-lock-free-programming/ https://preshing.com/20120612/an-introduction-to-lock-free-p...) You use these guarantees of forward progress (ex: on a 128-core computer, if all are doing compare_exchange_strong at the same time, then 1x of them will succeed, and 127x of them will fail. This is guaranteed, _SOMEONE_ succeeds and makes forward progress with lock-free primitives like compare_exchange_strong). That means that if all 128x threads/cores call "compare_exchange_strong" 1x each, then after 128x calls every thread will have succeeded (ie: worst case, one thread will have to call it 128x times). No. This isn't sufficient to have lock-free code yet. You now need to prove that you don't deal with live-lock issues or other such complex issues that come up (and you'll only get here in the first place if you wrote your memory-barriers correctly and lined everything else up perfectly). But its a start. And with enough effort, study, sweat and tears, you'll be able to write a lock-free something and have a good functioning interrupt service routine.

kccqzy 3y ago
Ah I had a reading comprehension fail. I never noticed in your first sentence you said interrupt code. Well then I do not profess to understand much about that. > Lock-free code by itself doesn't guarantee forward progress. I think we have some definition differences here. What I have seen and have alluded to previously when you use tools like compare_exchange_strong is that the underlying machine does not guarantee forward progress. When you have 128 cores calling compare_exchange_strong at the same time, yes 1 of them will succeed and 127 of them will fail. But there is no guarantee that for a particular core, it will eventually succeed; it could always be among the 127 failing ones. I often see that on NUMA systems where many cores running on a single CPU are competing against one core running on a remote CPU. Due to the way hardware works, that remote CPU consistently takes longer to do each atomic operation, leading it to always fail. So no, after 128x calls not every thread will succeed.
- dragontamer 3y ago
  > So no, after 128x calls not every thread will succeed. I don't think you understand the situation I setup. Lemme try again from first principles. ----------- In general, as long as you have proven that there is a *FINITE* amount of work to do, then when you prove forward progress (ie: at least one thread makes progress), you prove forward progress for the whole system. Even if the "slowest-thread" loses every single time, eventually the 127x other threads run out of work, and the final thread can finally call compare_exchange_strong by itself. When it is the only thread calling the atomic, it will succeed (no one else can contradict, because everyone else has run out of work and is out of the loop). Its as simple as "finite work" + "forward progress" == "eventual completion". Even in an imbalanced system where thread #128 is 128x slower than thread#1 and "loses the race" every single time... eventually thread#1 runs out of work (it succeeded so many times, its done). And the other threads get to finally run. ------- Writing code that guarantees forward progress is the hard part however.
  - kccqzy 3y ago
    In a general RPC system (which is where I have the most experience with) there cannot be finite amount of total work. What is finite is the rate of incoming work. If a thread finishes work early, the load balancer gives it more work. On the other hand if a thread doesn't make progress due to badly written atomics, or even an unfair mutex, that thread is stuck processing that one request indefinitely, which then reduces the rate of incoming work. That said, your comment is very illuminating and I thank you for it. I'm glad we've resolved our definitional and perspective differences.
    - dragontamer 3y ago
      Yeah, the math for your situation is Queuing Theory, btw. A somewhat unrelated subject. I'd say lock-free programming doesn't necessarily help that problem. Performance improvements are one of the keys, as the faster your code executes, the "shorter the queues get" because you're processing everyone faster in the system. Queuing Theory is one of the weirder maths in Comp. Sci. I have mixed opinions on whether or not its really worth studying, as it covers very obvious truths. (The faster your code executes, the shorter lines get. Etc. etc.). I've seen the arguments that Queuing Theory is a lot of "obvious math" that you'll keep solving over-and-over again in parallel systems / code optimization however, so might as well formalize the concepts. ----------- Queuing Theory is that all systems can be modeled as queues (aka: lines), where people stand in line waiting to be served. And "servers", who serve these people waiting in line. When someone is served, they move on to another queue / line up and wait for the next server to serve them. You then do a bunch of math to see how long these lines get (ie: representing how much RAM you need to save all of these jobs) in a variety of random-distributions (poisson arrival times, etc. etc.).

kccqzy 3y ago

Ah I had a reading comprehension fail. I never noticed in your first sentence you said interrupt code. Well then I do not profess to understand much about that. > Lock-free code by itself doesn't guarantee forward progress. I think we have some definition differences here. What I have seen and have alluded to previously when you use tools like compare_exchange_strong is that the underlying machine does not guarantee forward progress. When you have 128 cores calling compare_exchange_strong at the same time, yes 1 of them will succeed and 127 of them will fail. But there is no guarantee that for a particular core, it will eventually succeed; it could always be among the 127 failing ones. I often see that on NUMA systems where many cores running on a single CPU are competing against one core running on a remote CPU. Due to the way hardware works, that remote CPU consistently takes longer to do each atomic operation, leading it to always fail. So no, after 128x calls not every thread will succeed.

dragontamer 3y ago
> So no, after 128x calls not every thread will succeed. I don't think you understand the situation I setup. Lemme try again from first principles. ----------- In general, as long as you have proven that there is a *FINITE* amount of work to do, then when you prove forward progress (ie: at least one thread makes progress), you prove forward progress for the whole system. Even if the "slowest-thread" loses every single time, eventually the 127x other threads run out of work, and the final thread can finally call compare_exchange_strong by itself. When it is the only thread calling the atomic, it will succeed (no one else can contradict, because everyone else has run out of work and is out of the loop). Its as simple as "finite work" + "forward progress" == "eventual completion". Even in an imbalanced system where thread #128 is 128x slower than thread#1 and "loses the race" every single time... eventually thread#1 runs out of work (it succeeded so many times, its done). And the other threads get to finally run. ------- Writing code that guarantees forward progress is the hard part however.
- kccqzy 3y ago
  In a general RPC system (which is where I have the most experience with) there cannot be finite amount of total work. What is finite is the rate of incoming work. If a thread finishes work early, the load balancer gives it more work. On the other hand if a thread doesn't make progress due to badly written atomics, or even an unfair mutex, that thread is stuck processing that one request indefinitely, which then reduces the rate of incoming work. That said, your comment is very illuminating and I thank you for it. I'm glad we've resolved our definitional and perspective differences.
  - dragontamer 3y ago
    Yeah, the math for your situation is Queuing Theory, btw. A somewhat unrelated subject. I'd say lock-free programming doesn't necessarily help that problem. Performance improvements are one of the keys, as the faster your code executes, the "shorter the queues get" because you're processing everyone faster in the system. Queuing Theory is one of the weirder maths in Comp. Sci. I have mixed opinions on whether or not its really worth studying, as it covers very obvious truths. (The faster your code executes, the shorter lines get. Etc. etc.). I've seen the arguments that Queuing Theory is a lot of "obvious math" that you'll keep solving over-and-over again in parallel systems / code optimization however, so might as well formalize the concepts. ----------- Queuing Theory is that all systems can be modeled as queues (aka: lines), where people stand in line waiting to be served. And "servers", who serve these people waiting in line. When someone is served, they move on to another queue / line up and wait for the next server to serve them. You then do a bunch of math to see how long these lines get (ie: representing how much RAM you need to save all of these jobs) in a variety of random-distributions (poisson arrival times, etc. etc.).