BTW, I'm going to pick on you a bit. I don't like it when people oversimplify things in CS. I think it can be confusing to beginners (and, sometimes, non-beginners). I don't like when people say things like "the scheduler can do whatever it wants," "the OS scheduler can change any time," "the scheduler is non-deterministic," etc., because I know those things aren't true. They may help make a point, but it's also introducing a source of potential confusion.
I say this from the perspective of somebody who has actually done some work on OS schedulers. I mean, to me, the OS never substitutes a new scheduling algorithm any time it likes, though an OS hacker may actually change the algorithm. And, as you may know, kernel hackers take advantage of known limitatations in concurrency (i.e., concurrency that will never "actually happen").
Note that I never said the scheduler is non-deterministic. It is the order of your threads' execution that's non-deterministic.
There are lots of schedulers out there that have a different contract than the one you described ("run threads in any order"). For example, many real-time systems run threads in priority order - you only get preempted if a higher-priority thread wants to run.
Imagine you spin off 10 threads waiting for network requests where one thread per client machine. It cannot be deterministically decided which thread will run first and which will run next. It depends on which client connects to which thread first. That's the non-deterministic nature of the program. Concurrency is the discipline to deal with that problem.