Even in computing, simultaneity is relative

Einstein discovered that simultaneity is relative. This is also true of computing.

People will ask, "Is it okay to do X on one thread and Y on another thread simultaneously?" Here are some examples:

  • X = "close a handle" and Y = "use that handle".
  • X = "call UnregisterWaitForSingleObject on a handle", Y = "call UnregisterWaitForSingleObject on that same handle".

You can answer this question knowing nothing about the internal behavior of those operations. All you need to know are some physics and the answers to much simpler questions about what is valid sequential code.

Let's do a thought experiment with simultaneity.

Since simultaneity is relative, any code that does X and Y simultaneously can be observed to have performed X before Y or Y before X, depending on your frame of reference. That's how the universe works.

So if it were okay to do them simultaneously, then it must also be okay to do them one after the other, since they do occur one after the other if you walk past the computer in the correct direction.

Is it okay to use a handle after closing it? Is it okay to unregister a wait event twice?

The answer to both questions is "No," and therefore it isn't okay to do them simultaneously either.

If you don't like using physics to solve this problem, you can also do it from a purely technical perspective.

Invoking a function is not an atomic operation. You prepare the parameters, you call the entry point, the function does some work, it returns. Even if you somehow manage to get both threads to reach the function entry point simultaneously (even though as we know from physics there is no such thing as true simultaneity), there's always the possibility that one thread will get pre-empted immediately after the "call" instruction has transferred control to the first instruction of the target function, while the other thread continues to completion. After the second thread runs to completion, the pre-empted thread gets scheduled and begins execution of the function body.

Under this situation, you effectively called the two functions one after the other, despite all your efforts to call them simultaneously. Since you can't prevent this scenario from occurring, you have to code with the possibility that it might actually happen.

Hopefully this second explanation will satisfy the people who don't believe in the power of physics. Personally, I prefer using physics.

Comments (31)
  1. Don’t forget that on an MP system, while in physics, things can happen with a great deal more simultaneity than they can on a UP system.

    The same is true for HT machines (which aren’t REALLY MP machines, but behave as if they were for most intents and purposes).

    On the other hand, the NT scheduler’s pretty good at context switching code at the worst possible time, even on UP systems. I’ve been amazed at how often the NT scheduler has shown even tiny race conditions in my code.

  2. There was just a thread on NTDEV the other day discussing synchronizing work items with DPCs. The poster didn’t realize that you have no idea what the relative ordering of execution of DPCs and threads will be, and therefore you have to use synchronization mechanisms to keep things straight.

    I can’t find the link at the moment but it should be indexed by OSR soon.

  3. Paul C. says:

    I’m not sure that I’d use the physics thing to explain it. Rather, I’d tell him that <b>nothing</b> on a computer ever happens simultaneously. Moreover, unless you take steps to guarantee the order in which something happens, you cannot know which thread is going to execute first. Therefore, you can assume that half of the time, X will happen first, and half of the time, Y will happen first. So in the case of closing a file handle and using it "simultaneously", if having their code fail half of the time is acceptable for their program, then by all means they can write their code in that manner. Or, if I was being harsh that day, I’d just tell them it’s a silly question and that they should make their code to be safe in the first place, rather than spend their time wondering about what laziness they can get away with. But that’s just me.

  4. DCD says:

    Not to be anal, but relativity doesn’t break causality – that is if x occurs before y then it will always be true for all frame of references. If John shoots Abe, there are no frame of refrences where Abe shoots John.

  5. Raymond Chen says:

    True, if X and Y are timelike separated then X will always occur before Y. My point was that if X and Y are simultaneous in the rest frame (therefore: spacelike separation), then you can always find a moving observer which will see X before Y and another who will see Y before X.

  6. Ben Hutchings says:

    Merle: I think the handle functions are atomic (in fact they probably have to be to maintain the integrity of the OS) so that isn’t an issue, though it would be something to consider in user-written code.

  7. Ben Hutchings says:

    "Simultaneously" really just means "between two consecutive points at which the two threads are synchronised" here, right?

  8. Skywing says:

    Functions that use a handle will reference it and turn it into an object pointer — it’s at this point where either the function will fail because the handle went away (or refers to the wrong type of object, grants the wrong type of access, etc), or the object’s reference count is incremented so that closing the handle will not make the object go away.

  9. Doug says:

    What makes me shiver is thought of the environment has brought Raymond to be so forceful in explaining basic computer science concepts.

    I’m surprised he’s not in jail for murder. I suspect I would be….

  10. Keith Moore [exmsft] says:

    Just throwing this out for general amusement…

    There is an even more annoying race that can be caused by two threads closing the same handle. This race involves three threads. Consider:

    1. Thread A closes handle H.

    2. Thread B also closes handle H.

    In between sneaks Thread C:

    1.5. Thread C calls some API that creates a handle, and the system happens to return handle H.

    So now, Thread C thinks it has created a handle (to a file or whatever), but Thread B has closed it "behind Thread C’s back".


  11. robdelacruz says:

    Interesting post. However I believe absolute simultaneity is valid given the same point in spacetime. In your example, X = close handle A; Y = use handle A. A would be a single point in 4D spacetime, so it can be measured absolutely.

    What doesn’t work is when you try to compare two different points in spacetime. Ex: X = close handle B; Y = use handle C. B and C are two different points, therefore with special relativity, B and C could occur earlier than the other depending on your frame of reference, but the order is irrelevant. In computer terms, it wouldn’t matter whether X closed handle B before Y used handle C. It is irrelevant.

    To get the laws of physics on your side, you would delegate all handle creation functions to a separate process or service. That way the handle creation would always be occuring on ‘local time’ (the frame of the process or service) which would be a single point of reference.

  12. Raymond Chen says:

    I guess I don’t follow. "Handle A" is not an event. Only events have 4D coordinates.

    Even if you moved the handle operations into a separate process, all that does is move the racing operations from "close handle A" to "issue request to close handle A". The same argument applies.

    (I’m assuming that the two processors occupy different locations in 3space.)

  13. Stuart says:

    Perhaps it would be worthwhile to note that although you can guarantee certain combinations to be *illegal* this way, you can’t use this logic to guarantee that they’re *legal*.

    Just because a function can legally be called twice (many Close() and Dispose() methods have this property in .NET – I think it’s called idempotence) successively doesn’t necessarily mean that it’s threadsafe and will be able to handle having its internal operations interleaved between two threads executing it simultaneously.

  14. robdelacruz says:

    Ah.. right, 4D spacetime is not the right word to use. What was I thinking?

    When two cars bump into each other in an intersection, it is the same event occuring in the same 4D coordinate. Therefore from all points of reference, it occurs ‘simultaneously’. For ‘close handle A’ and ‘use handle A’ events, handle A is the intersection where the cars collide.

    re: Putting handle operations on a separate process – it’s now possible to have a mechanism to use the same thread (single point of reference) for all the ‘use handle’, ‘close handle’ operations, rather than the previous multiple-thread scenario.

  15. Raymond Chen says:

    In the original formulation, the two events are

    X = "close handle A on thread 1"

    Y = "use handle A on thread 2"

    They are two events with two different coordinates (if you assume that the two processors occupy different points in space).

    In your new model – sure consolidating onto one thread makes that the close and use are serialized. But all you did was push the conflict out another level. The new conflict is

    X = "issue close handle A request from thread 1"

    Y = "issue use handle A request from thread 2"

    You have the same problem – X and Y can occur in different orders in different frames.

  16. Konstantin Surkov says:

    First of all, just thought you would be happy to know that general relativity, as latest experiments show, may be wrong, see http://www.economist.com/science/displayStory.cfm?story_id=3104321

    Secondly, I wanted to point out that simultaneity is relative only if events are separated spatially, otherwise it is absolute, but after reading comments found that robdelacruz has already did.

  17. Merle says:

    The physics references are interesting, but probably not quite to the point. Generally one can say "X before Y, or Y before X, depending on frame of reference". But it depends on how atomic X and Y are. And, of course, the frame of reference.

    The computer is one frame of reference. There really isn’t any other, except for a virtual frame in the mind of the coder, where normal laws of physics do not necessarily apply (otherwise they would not ask those questions?). There is no moving frame of reference in the computer. It does not matter "if you walk past the computer in the correct direction" or not. X happened first, or Y did, but a predetermined one and only one of them did — and, contrary to some quantum physics, you can observe with accuracy which one happened (with properly coded X and Y).

    You do mention atomicity. That, to me, is a bigger issue in synchronicity (and simultaneity) than "can I do these two things at the same time".

    Clearly you cannot unregister the same event twice; I would hope the second attempt would throw an exception. Just as clearly, you cannot use a handle after closing it (or while, really). Those aren’t related to physics in my mind. People might ask "can I do these things simultaneously" in the same sense a five-year-old might ask "can I stay up until 3am". They (should) know the answer. You just don’t *do* things like that.

    The bigger problem is that X is "Merle eats a sandwich", and Y is "Raymond eats a sandwich". I might take a half hour break between bites. Worse yet, there might only be *one* sandwich. You might stick dreaded bell peppers into mine half way through, causing a (verbal) exception.

  18. Ben Hutchings says:

    Merle: Another thought occurs to me. Perhaps the people asking the question are vainly *trying* to cause race conditions, with some strange idea in their minds of what the result would be…

  19. Merle says:

    Ben: That’s true, I would *hope* handle functions would be flagged as atomic. But there’s atomic, and there’s synchronous.

    Perhaps I’m using the word "synchronous" incorrectly, from early Java days. What I mean is "no other method in this class can execute while this one is". In which case I would make sure write() was synchronous (definitely with itself!), but close() is just setting a flag, and releasing the OS pointer. It might not be.

    I don’t know if they’re necessarily trying to cause race conditions, but they’re definitely trying to push the boundaries. Even if you *could* do such things, I would actively speak against it… just as being Wrong.

  20. Jon Potter says:

    Am I the only one who doesn’t know what UnregisterWaitForSingleObject() is?

  21. It’s one of the thread pool APIs – RegisterWaitForSingleObject and UnregisterWaitForSingleObject are symetrical.

  22. Tom Guinther says:

    Although Larry Osterman already made this point:

    "Don’t forget that on an MP system, while in physics, things can happen with a great deal more simultaneity than they can on a UP system"

    I just wanted to add that while adding Symmetric Multi-Processor support to Soft-ICE the frequency of simultaneity for various low-level code was quite high. Of course I am taling about interrupt level logic, but the same principle should apply. Maybe this effect is more of a Quantum Mechanics effect that gets lost at the higher level abstraction of your everyday ring-3 thread which is more newtonian in nature?

  23. Mat Hall says:

    It also occurs to me that if "X before Y" and "Y before X" occurred in CPUs depending on which way you were moving relative to it, we’d all have to stand very still or run the risk of instructions being executed in a random order…

  24. David Heffernan says:

    Actually the APIs are UnregisterWait and UnregisterWaitEx.

  25. Jon Potter says:

    These functions seem to be missing from my copy of the SDK :)

  26. Chris Walker says:

    Double closes of handles (or double frees) don’t require multithreading to show themselves. A single thread with weak handle ownership often has these problems. If handle were never re-issued (read: guid or luid) there would be no problem (other than performance).

    At one point in time Windows (NT) delayed as much as possible recycling kernel handles. This doesn’t make the problem go away, but does improve the probability that it won’t cause any problems. (note that this assume the program is already in error)

    The App verifier has an option to raise exceptions if a program attempts to close an invalid handle which is handy to use during testing.

  27. Mike Swaim says:

    What makes me shiver is thought of the

    > environment has brought Raymond to be so

    > forceful in explaining basic computer

    > science concepts.

    I’ve seen worse. I once saw a programmer get upset when I told him that computers executed programs deterministically.

  28. Fei Liu says:

    Special relativity theory is only practically applicable under certain situation, i.e. near light speed motion, or

    sub-microscopic world such as electrons (which move at light speed), etc.

    When you are talking about car collsion, the simultaneity is not equal to the concept of simultaneity under near light speed situation. Simultaneity for things moving near light speed is a relative concept due to the use of reference frame. For one, the events are simultaneous, but for the other, they ain’t.

    Simultaneity of execution of instructions on a single CPU is of course impossible because of sequence principle. On SMP system, two CPUs can execute two instructions simultaneously as long as the two CPUS are not moving near light speed seen by one another (do we have such kind of motherboard yet? :) and stay motionless relative to each other.

  29. Raymond Chen says:

    Even if the two CPUs are motionless relative to each other, an observer can see one or the other instruction execute first (whichever CPU is closer will appear to have executed the instruction first since the light has less distance to travel).

  30. Fei Liu says:

    To the observer at the point between the two cpus, it’s simultaneous.

  31. Raymond Chen says:

    Exactly my point. What is simultaneous to one is not simultaneous to another.

Comments are closed.