The question refers to the output of a multi-threaded application, where each thread merely prints its ID (user assigned number) on the standard output. Here all threads have equal priority and compete for CPU quota in order to print on the standard output. However, running the same application a sufficiently large number of times will result in different order of IDs being printed on the screen. This order is due to the OS scheduler which is a piece of software and therefore deterministic. Nonetheless, its behavior seems non-deterministic, which brings me back to the initial question.
This is 100% normal with respect to threading on any and all operating systems. The documentation for your thread library, any examples and tutorials you may find, etc. are likely to make a point of this as it is often confusing to people when they are learning the ropes of threading.
Threads are by default (and by definition) not synchronized.
This means unless you make arrangements to the contrary (via locks, semaphores, whatever), do not expect threads to execute in any particular order. It does not matter what they are doing or how you think they are "likely to happen" based on what they are doing, etc. Put simply: do not think about them this way, that is not what they are or how they are meant to be used. Do not bother coming up with mentalizations such as "I am in single user mode, I am trying to still the system like water because...and..blah blah" ad infinitum, etc., it is a waste of time, there is nothing to learn that way. Water is inevitably not still, that's how liquids are. End of story. Move on and enjoy.
Executing threads that, as you say, do next to nothing on a system that you have set-up to do next to nothing will result in a light load for the scheduler, but note the CPU still runs at full speed and a lot of nothing happening quickly is not necessarily more predictable than any other scenario. The scheduler is not intended to synchronize or predictably order threads and processes. I really really really hope me saying this does not inspire you to concoct a more complicated and pseudo-logical experiment, because as already stated, that is a waste of time, move on.
You can and probably will synchronize them, but notice that is a delicate trick that first requires you understand why they do not just "do it naturally"(clue: because there is no reason for them to do so, they don't).
"What makes a deterministic OS seem non-deterministic?"
Perhaps the analogy of fluid dynamics is not so silly. Fluids seem chaotic -- smoke can even seem to be alive -- and I believe in mathematics the study of fluid dynamics and chaos theory do cross over. However, most people are probably not stunned by this ("Amazing! What could cause such behavior in natural phenomenon? Perhaps it is evidence of God!" ...no) because we can understand how the interaction of deterministic rules (the laws of fluid dynamics) viewed on a certain scale will produce results that are only crudely predictable ("Well, the water will spill out of the glass...") and hence are effectively chaotic or non-deterministic (the pattern of the splash on the table) . Even if that is "only a very small fire" or glass of water, we recognize there is the motion of literally trillions of trillions of particles involved.
If you have ever busy looped with a counter just to see how fast your computer can count, you will know that is on the order of billions of times per second. Keep in mind that most of the "minor" system events constantly going on even with an "idle" system will still be much more substantial than a thread whose activity is measured by the printing of an ID, if that is all the thread is doing. Going with our fluid analogy, even on a day that seems "completely windless" to us, smoke does still not form an orderly column (but we can see more clearly how its own movement affects it).
The scheduler is supposed to ensure that all processes run in a balanced way (gravity will make sure water will spill), however, not by giving each of them exactly 1 nanosecond at a time (which might make your experiment more predictable). This is all well and good since, once again, it is NOT the role of a scheduler to synchronize anything, it is to make everything happen in an appropriately balanced way. These two goals are not the same. When you do get into synchronization, you will appreciate how while synchronization can achieve a clear balance, it comes at the cost of efficiency.
Also, the Linux scheduler uses a red-black tree to organize its queue, it does not simply run everything around in a FILO line (I doubt any modern general purpose scheduler will do that). That implies greater complexity and hence, more apparently chaotic behaviour.
I don't want to encourage you to persist in your fixation, but if you got the threads to perform a more substantial task, one that will actually take them something resembling time to do, and start them offset by a few seconds on an otherwise idle system, then in fact you will see completely deterministic results. Just keep in mind this is not a truly effective means of synchronization -- when the wind kicks up and the water gets rough, you will see the chaos start ;)
"Do you know of any research which studies the influence of these events on the OS scheduler?"
No, because there is nothing truly mysterious about it, as in the case of fluids. The scheduler actually is completely deterministic, just not in the sense or on the scale you are considering. If you put a bunch of informative
printks in the kernel code and understand the algorithm of the scheduler, you won't find anything non-deterministic -- everything will happen exactly the way it is supposed to.
The software cannot be more deterministic than the hardware. First, you have random interrupts that come in from many sources(like mouse, keyboard, network, clock, storage, OS background tasks.).
Even if those interrupts are totally disabled during the execution of your program, general-purpose x86 desktop hardware of 80486 and newer has decidedly non-deterministic execution ordering. (Thus generally unsuited to many real-time tasks, and why the 80386 continued production through 2007, long after Pentium 1 and 2.) Hardware determinism had to be sacrificed to get throughput at a reasonable cost. This is due to cache effects, simultaneous multi-threading(hyper-threads), branch prediction, out-of-order execution, and piplining. Deterministic behavior is the reason an 8bit Arduino is better for precise machine control than a much faster Raspberry-Pi.
Mainline Linux is by default a general purpose OS with a general purpose scheduler all intended for good overall throughput, and good average lag on interactive tasks. Mainline can also be used with "soft real-time" scheduling for things like video calling where you want some bounds on latency and good ordering, but a rare blip can still be tolerated.
There is a real-time patch to make a fully preemptable hard real-time Linux kernel,(even kernel threads can be preempted/delayed/interrupted in favor of a user task.) this will allow bounding the latency of a task to within the deviation limits of the hardware. This hard bounding requirement will often reduce the efficient utilization of the hardware and alter the behavior of the OS. (It is like having some reserved spaces in a parking lot. It reduces the maximum average vehicle count, but for those users of a reserved spot the time to park is now a fixed quantity.) An RTL-kernel is preferred for professional music recording, machine control, banking transactions, precise sensor-data sampling, medical devices and such. Hardware selection will be a core part of the development considerations, especially if your required maximum (not mean, median, or mode) latency variance(not total latency) must be less than about 500k clock cycles.
As for the normal general purpose linux scheduler. The default scheduling for tasks uses uses dynamic priority, which as adjusts priority slightly during runtime based on cpu load and actual task behavior. Actual CPU load and task behavior involves a huge number of variables due to background tasks, different beginning states (eg cache condition at start of execution), and random glitches(eg a spurious interurupt request that causes a task to win or loose a race for the next timeslice and the resulting scheduling cascade of effects.)
I am using PC's from early 8 bit on and are familiar with several programming languages. I discover time after time that the OS of Mint Cinnamon is doing things in the background after doing things that should work but disturb the funktion of the OS in the deep. Rebooting often helps but not always. I have to say that in the end Windows is not better but more predictable in what happens after you change options that the system offers you to change. Being familiar with testing in the past I think Mint is not tested the way it should be.