[brianberns]

> your worst enemy could simply never schedule that thread again

That seems too extreme to me. If the scheduler itself is potentially malicious, then no multi-threaded implementation is safe, since we can't assume that any thread we start will ever actually run.

[johnbender]

This is an important observation!

If the properties of concern for your thread or program are only safety properties (“never does a bad thing”) then the fact that the program may never do anything at all is just fine!

Then, if you want some liveness properties (“eventually does something good”) you’ll need to embed some assumption about fairness/scheduling/progress just as you’ve said!

This appears in early concurrency literature (TLA etc which I can’t be bothered to look for)

[manicdee]

This isn’t about malice.

Remembering that you are your own worst enemy, what this implies is that some other perfectly sane decision you made in the past has come to bite you in the arse.

[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.

[colanderman]

"Malice" doesn't need to come into play. A thread could simply be waiting in line behind a non-preemptible thread which does not relinquish the CPU due to a bug.

[nyanpasu64]

One real-world example is assuming that the audio thread (scheduled at realtime priority if possible) is guaranteed to run, while the GUI thread may or may not run, or get descheduled at any point. Even if the GUI thread locks up (for example the user is resizing the window), the audio thread should not stop producing sound.

[insulanus]

"your worst enemy" can be a stand-in for "a faulty algorithm running on another thread".

Or, another way to look at it - a lock-free algorithm that allows starvation or livelock/deadlock.

[jganetsk]

It assumes that at least 1 thread is running at all times. There are algorithms that can make progress this way.

[read_if_gay_]

A thread that never ran can’t lock up, so I guess it’s still technically lock free?

[brianberns]

Yes, it’s lock-free, but it doesn’t actually work.