4

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
  • 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, 2013 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, 2013 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, 2013 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, 2013 at 7:20

3 Answers 3

9

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.

5
  • 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, 2013 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, 2013 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, 2013 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, 2013 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, 2013 at 15:51
0

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

-2

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.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .