But it can’t be turtles all the way down? Isn’t a semaphore counter also shared state that needs to be protected if several threads want to “down” the value? Can it become negative?
Well at the bottom of the turtle stack you have harware primitives that guarantee atomicity of a bunch of word sized arithmetic operations (at the minimum CAS or LL/SC).