Hacker News Reader

With that reasoning, you should write your own kernel too -- you realize that the kernel scheduler will take locks at some point, right?

I think that malloc is a sufficiently abstract operation here that its implementation shouldn't constitute whether the algorithm as a whole is lock-free or not.

View on HN

Lock-free algorithms don't usually depend on an OS being present. They could just as easily run in an environment that has no scheduler. But if the algorithm calls malloc, that is a hard dependency.

If an algorithm depends on malloc, it needs to prove that lock-free/wait-free malloc() exists before calling itself lock/wait-free.

Not really. Lots of applications where lock free algorithms are justified usually implement their own memory allocators.

Reply on news.ycombinator.com