atomic flag

[Jerry Coffin]

Even a write through cache doesn't guarantee atomic access.

Oh, I realize that -- I was just trying to address the idea that memory
is always coherent with the cache, which simply isn't the case. It's
true that being coherent with the cache isn't enough, but even if it
was, most caches wouldn't provide it anyway.

Some machines can't store a partial word without doing a Read-Modify-Write
cycle. It's possible that these may interfere with each other.

Under the wrong circumstances, a machine may not even be able to write a
full word as an atomic operation. Just for one example, writing a dword
to an odd address on some x86 chips would happen in three separate bus
cycles. Likewise, if a value happens to cross a cache-line boundary,
there's almost no chance of it being written atomically.

 

[Jerry Coffin]

[ ... ]

What is the program-visible effect of a non-atomic write?

Reading a bad value is the most common result.

 

[Jeff Schwab]

Interesting question. If we have one writer that replaces old value "xold"
by a new value "xnew", and one
reader that is reading, I could imagine 2 cases:

1. reader reads value that is neither "xold" nor "xnew".
2. reader repeatedly reads and at some point it gets "xold" after "xnew".

anything else?

It could be much worse if there are more then one writer - even if they
write to different
(but adjacent) memory locations...

regards,
Michael

You've described reads after write (RAW), not just a single write.
Nobody here is claiming that a read after write is atomic without
special CPU-level instructions.

 

[Jeff Schwab]

The value may fail to get stored.

Imagine the following:

struct { char a, b, c, d; } x;

If you have one processor writing to x.a and another writing to x.b they
may interfere with one another.

You've described two writes, not one.

 

[Jeff Schwab]

[ ... ]

What is the program-visible effect of a non-atomic write?

Reading a bad value is the most common result.

You've described a read after write, not just a write. I've claimed
only that a write is atomic, not the write and any subsequent read.

 

[Jerry Coffin]

[ ... ]

You've described a read after write, not just a write. I've claimed
only that a write is atomic, not the write and any subsequent read.

The problem I'm talking about arises from the write itself not being
atomic. Obviously, if you write a value and NEVER attempt to read it,
lack of atomicity in that write won't show up much, simply because no
matter how badly it gets munged, you're not reading it to see the munged
value.

 

[Jeff Schwab]

[ ... ]

You've described a read after write, not just a write. I've claimed
only that a write is atomic, not the write and any subsequent read.

The problem I'm talking about arises from the write itself not being
atomic. Obviously, if you write a value and NEVER attempt to read it,
lack of atomicity in that write won't show up much, simply because no
matter how badly it gets munged, you're not reading it to see the munged
value.

But how does it get "munged?"

Btw, the fact that this is obvious hasn't stopped people from arguing
it, and flabbergasting me.

 

[Jeff Schwab]

You've described two writes, not one.

To clarify: The OP was discussing the setting of a boolean flag, not
multiple variables. Clearly, in the case you've described, an attempt
to write the entire structure may not be atomic. I'm not sure what the
problem with one thread setting x.a and the other setting x.b is,
though. How could they possibly interfere?

 

[David Harmon]

to write the entire structure may not be atomic. I'm not sure what the
problem with one thread setting x.a and the other setting x.b is,
though. How could they possibly interfere?

The buss width is 32 bits. In order to modify part of it, the CPU must
read/modify/write the whole thing.

 

[Jeff Schwab]

The buss width is 32 bits. In order to modify part of it, the CPU must
read/modify/write the whole thing.

You mean the "bus" to the shared memory? Access to the memory is
mutexed in hardware. Some memories allow multiple simultaneous writes,
as long as they don't interfere.

 

[Alexander Terekhov]

Jeff Schwab wrote:
[...]

Access to the memory

http://www.google.com/groups?th=a562b8fac4cbacbd
(Subject: Memory isolation)

regards,
alexander.

 

[Jeff Schwab]

Jeff Schwab wrote:
[...]

Access to the memory

http://www.google.com/groups?th=a562b8fac4cbacbd
(Subject: Memory isolation)

regards,
alexander.

The author describes a system in which a "write" instruction generates a
read, followed by the write. Redefining "write" to mean "write after
read" is a bastardization. I would define a "write" of a boolean flag
to be the flipping of a bit in memory; until the memory is succesfully
changed, the write has not occurred. The current example then shows
only a failed write, resulting from an improperly used (defective?) memory.

Although such a system certainly could exist, I have never heard of any.
I would be grateful to see any example.

 

[Jeff Schwab]

Jeff Schwab wrote:
[...]

Access to the memory

http://www.google.com/groups?th=a562b8fac4cbacbd
(Subject: Memory isolation)

regards,
alexander.

The author describes a system in which a "write" instruction generates a
read, followed by the write. Redefining "write" to mean "write after
read" is a bastardization. I would define a "write" of a boolean flag
to be the flipping of a bit in memory; until the memory is succesfully
changed, the write has not occurred. The current example then shows
only a failed write, resulting from an improperly used (defective?) memory.

Although such a system certainly could exist, I have never heard of any.
I would be grateful to see any example.

To the nitpickers who may shortly begin ranting about caches: I mean
the above according to the "as-if" rule, not literally. It is the job
of a cache to make the program behave "as if" the above were the
implementation, but with improved performance.

 

[Alexander Terekhov]

Jeff Schwab wrote:
[...]

To the nitpickers who may shortly begin ranting about caches: I mean

http://google.com/[email protected]

regards,
alexander.

 

[Michael Furman]

Michael Furman wrote:
[...]

Interesting question. If we have one writer that replaces old value "xold"
by a new value "xnew", and one
reader that is reading, I could imagine 2 cases:

1. reader reads value that is neither "xold" nor "xnew".
2. reader repeatedly reads and at some point it gets "xold" after "xnew".

anything else?

It could be much worse if there are more then one writer - even if they
write to different
(but adjacent) memory locations...

regards,
Michael

You've described reads after write (RAW), not just a single write.
Nobody here is claiming that a read after write is atomic without
special CPU-level instructions.

If you just write and nobody ever read it, what is your definition of
"atomic"?
You can replace your write instruction by "no operation" - nobody ever
see the change!

My post was actually a try to define atomic. I believe that write is atomic,
if
result of read instruction executed at time T will be:
xold - if T < T0
xnew - if T >= T0

And of cause T0 should be close to the time of executing "write"
instruction.

Does it have sense? Is there a better definition of atomicity?

Regards,
Michael

 

[Jerry Coffin]

[ ... ]

But how does it get "munged?"

By being written as a number of operations instead of a single atomic
one. I thought I'd already mentioned the situation with an x86 writing
to a 4 byte value at an odd address. It writes it in three separate bus
operations -- a single byte write, a two byte write, and finally a
single byte write.

Writing two bytes to an odd address (with the same processor) happens in
two operations.

On other machines, especially if a boolean is stored in a single byte,
we run into a different problem: most RISCs (for example) can't read or
write anything smaller than a whole (32-bit) word. To modify only one
byte, the read the whole word, modify it, then write back the result --
again, a non-atomic operation unless (expensive and non-portable) bus
locks are used to make it atomic.

In the specific case of a boolean, most of these problems are likely to
be covered up by the fact that in a boolean, only one bit is really
significant. The rest of the storage unit in which the boolean is
stored may be modified non-atomically, but it's difficult for the
modification of one bit to be non-atomic.

OTOH, I don't think there's any requirement or guarantee that a boolean
be stored as a single bit -- an implementation might (for example) store
0 and 0xffff for false and true respectively. In this case, if it reads
what's supposed to be a boolean, but happens to contain (for example)
0x00ff, it might decide something is defective, and halt the program
entirely. I'm not sure such an implementation exists, but I'm far from
certain it can't either.

Btw, the fact that this is obvious hasn't stopped people from arguing
it, and flabbergasting me.

I think most people have taken for granted that if a variable is being
modified, the intent is that it be available for reading later --
there's no point in writing a value if you're certain it will never be
used.

 

[Jeff Schwab]

Michael Furman wrote:
[...]

Interesting question. If we have one writer that replaces old value

"xold"

by a new value "xnew", and one
reader that is reading, I could imagine 2 cases:

1. reader reads value that is neither "xold" nor "xnew".
2. reader repeatedly reads and at some point it gets "xold" after

"xnew".

anything else?

It could be much worse if there are more then one writer - even if they
write to different
(but adjacent) memory locations...

regards,
Michael

You've described reads after write (RAW), not just a single write.
Nobody here is claiming that a read after write is atomic without
special CPU-level instructions.

If you just write and nobody ever read it, what is your definition of
"atomic"?
You can replace your write instruction by "no operation" - nobody ever
see the change!

My post was actually a try to define atomic. I believe that write is atomic,
if
result of read instruction executed at time T will be:
xold - if T < T0
xnew - if T >= T0

And of cause T0 should be close to the time of executing "write"
instruction.

Does it have sense? Is there a better definition of atomicity?

It makes sense, and I like your definition; however, the "write" and the
subsequent "read" are not atomic, and there is a chance of interference
between those two operations. I think everybody agrees on that.

 

[Jeff Schwab]

Jeff Schwab wrote:
[...]

To the nitpickers who may shortly begin ranting about caches: I mean

http://google.com/[email protected]

regards,
alexander.

That has nothing to do with whether a write is atomic. It only points
out that the order of writes and reads from multiple simultaneous thread
may not be WYE.

 

[Jeff Schwab]

[ ... ]

But how does it get "munged?"

By being written as a number of operations instead of a single atomic
one. I thought I'd already mentioned the situation with an x86 writing
to a 4 byte value at an odd address. It writes it in three separate bus
operations -- a single byte write, a two byte write, and finally a
single byte write.

Writing two bytes to an odd address (with the same processor) happens in
two operations.

When the OP mentioned setting a "boolean flag," I assumed "bit," or
"fundamental unit of storage." Perhaps I should have made this more
clear. Writing something bigger clearly is not atomic. You don't need
odd addressing schemes to see that. Serializing a large object to a
tape drive is a "non-atomic write."

On other machines, especially if a boolean is stored in a single byte,
we run into a different problem: most RISCs (for example) can't read or
write anything smaller than a whole (32-bit) word. To modify only one
byte, the read the whole word, modify it, then write back the result --
again, a non-atomic operation unless (expensive and non-portable) bus
locks are used to make it atomic.

This was mentioned in a thread linked by Alexander up-stream.

In the specific case of a boolean, most of these problems are likely to
be covered up by the fact that in a boolean, only one bit is really
significant. The rest of the storage unit in which the boolean is
stored may be modified non-atomically, but it's difficult for the
modification of one bit to be non-atomic.

That's all I've been saying!

OTOH, I don't think there's any requirement or guarantee that a boolean
be stored as a single bit -- an implementation might (for example) store
0 and 0xffff for false and true respectively. In this case, if it reads
what's supposed to be a boolean, but happens to contain (for example)
0x00ff, it might decide something is defective, and halt the program
entirely. I'm not sure such an implementation exists, but I'm far from
certain it can't either.

For such a value to get into an inconsistent state (in the absence of
Alpha hits or the like), the write would have to be non-atomic.

I think most people have taken for granted that if a variable is being
modified, the intent is that it be available for reading later --
there's no point in writing a value if you're certain it will never be
used.

It's okay to consider that the variable may, eventually, be read.
The write and subsequent read are not collectively atomic without
special hardware support, though. The write itself is the only part
I've claimed to be atomic.

 

[Alexander Terekhov]

Jeff Schwab wrote:
[...]

That has nothing to do with whether a write is atomic.

http://groups.google.com/[email protected]
http://groups.google.com/[email protected]

regards,
alexander.