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.

  • 4
    Is that application the only thing running on your system? No window manager, shells, network device, keyboard controler, USB controller, timer devices, ... which all participate in global, system-wide scheduling? – Mat Feb 24 '13 at 19:34
  • Funny you should ask that. When I asked a rather similar question earlier, it got voted down 3 times. To answer your question it is not the only thing running on my system. Even when I boot in single user mode there are many processes that run in the background. – Benny Feb 24 '13 at 21:03
  • 1
    @Benny, that is your answer: The scheduler selects the next task to run each time from among the tasks ready to run (that includes tasks internal to the kernel). This is moreover affected by other, unpredictable events: hardware interrupts, layout of stuff in memory can generate (or not) paging requests, and so on. – vonbrand Feb 25 '13 at 0:54
  • 1
    @vonbrand indeed I was aware that the processes running in the background may cause this influence. However, you also mentioned a few other interesting unpredictable events. This is close to the answer I'm looking for. Do you know of any research which studies the influence of these events on the OS scheduler? (I know I can look at the source code of the scheduler if I want to do it myself) – Benny Feb 25 '13 at 7:20

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.

  • Even though your answer is not false, it does not really answer my question. I am asking "why it is so?" and you are saying "because that is how its supposed to be". I am not saying it is not supposed to be that way. I know the standard textbook material on threading and I am not trying to synchronize threads without any synchronization mechanisms. The question goes beyond standard textbook stuff and the comment given by @vonbrand is much closer to the answer I am looking for. You can also see the question as: "What makes a deterministic OS seem non-deterministic?" – Benny Feb 25 '13 at 6:18
  • Vonbrand's comment was already there when I wrote this, and I agree with what he has said. If you already knew it was supposed to be this way, you should have made that clear ;) I've incorporated your question "What makes a deterministic OS seem non-deterministic?" into my answer, see the edit that starts there above. – goldilocks Feb 25 '13 at 13:26
  • thank you for your interest in this question. I think the analogy of fluid dynamics and chaos theory is very good. There is no doubt in my mind that the scheduler is non-deterministic that I already said in my question. Moreover, it is not synchronization what I am interested in, but the exact opposite. Since this wind (you are talking about) is not very controllable, do you think it could be a good source of entropy for a random number generator? – Benny Feb 25 '13 at 15:22
  • I believe that one source of "truly" random data used in, eg, cryptography (as opposed to the pseudo randomness that rand() usually gets) is exactly that, or at least, something involving the system state, since the system viewed as a whole is complex enough to produce a lot of entropic effects in certain places (like the execution order of minor identical threads). – goldilocks Feb 25 '13 at 15:41
  • I totally agree. Of course when you publish a scientific paper about this it is not sufficient to say that the system viewed as a whole is complex and you have to give more explanations to why this is. Hence my initial question. Moreover I honestly think it is VERY hard (if not impossible) to replicate the same state of a system such that you would get the same behavior leading to the same output sequence of the RNG twice. Please correct me if I'm wrong. Thanks again for the help. – Benny Feb 25 '13 at 15:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.