[thmt]

Alistarh et al. (https://arxiv.org/abs/1311.3200) show that assuming we have a kinder, non-malicious scheduler, the situation looks even better: lock-free (some process can make progress) algorithms have a stronger progress property of being wait-free (every process can make progress).

As omazurov mentioned as a top-level comment, threads can also die, which is rather like never being scheduled. In practice, I suspect that you're right that it's often too extreme of a model—many programs use locks and don't worry too much about this issue.