By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
459,977 Members | 1,642 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 459,977 IT Pros & Developers. It's quick & easy.

atomic flag

P: n/a
Is there a boolean flag that can be set atomically without needing to
wrap it in a mutex? This flag will be checked constantly by multiple
threads so I don't really want to deal with the overhead of mutexes or
semaphores. Thanks.

Shayan
Jul 22 '05 #1
Share this Question
Share on Google+
42 Replies


P: n/a
Shayan wrote:
Is there a boolean flag that can be set atomically without needing to
wrap it in a mutex? This flag will be checked constantly by multiple
threads so I don't really want to deal with the overhead of mutexes or
semaphores. Thanks.

I believe setting a flag /is/ an atomic action. It's when you want to
bundle multiple operations as an atom that problems may occur

Jul 22 '05 #2

P: n/a

"Shayan" <ss*****@harris.com> wrote in message news:69**************************@posting.google.c om...
Is there a boolean flag that can be set atomically without needing to
wrap it in a mutex? This flag will be checked constantly by multiple
threads so I don't really want to deal with the overhead of mutexes or
semaphores. Thanks.


There's no concept of atomicity in general. C has a sig_atomic_t
type, but even that only applies to signal handling.

Jul 22 '05 #3

P: n/a

"Shayan" <ss*****@harris.com> wrote in message
news:69**************************@posting.google.c om...
Is there a boolean flag that can be set atomically without needing to
wrap it in a mutex? This flag will be checked constantly by multiple
threads so I don't really want to deal with the overhead of mutexes or
semaphores. Thanks.

Shayan


1. No there isn't.
2. There is no simple mechanism even in assembler that will do this
correctly on a MP system.
3. In my experience waiting on a condition/semaphore can be faster than busy
waiting.

Jul 22 '05 #4

P: n/a

"Jeff Schwab" <je******@comcast.net> skrev i en meddelelse
news:88********************@comcast.com...
Shayan wrote:
Is there a boolean flag that can be set atomically without needing to
wrap it in a mutex? This flag will be checked constantly by multiple
threads so I don't really want to deal with the overhead of mutexes or
semaphores. Thanks.

I believe setting a flag /is/ an atomic action. It's when you want to
bundle multiple operations as an atom that problems may occur

You are wrong - at least on systems with multiple processors.

/Peter
Jul 22 '05 #5

P: n/a
On Wed, 14 Jan 2004 11:28:01 +0100, Peter Koch Larsen wrote:

"Jeff Schwab" <je******@comcast.net> skrev i en meddelelse
news:88********************@comcast.com...
Shayan wrote:
> Is there a boolean flag that can be set atomically without needing to
> wrap it in a mutex? This flag will be checked constantly by multiple
> threads so I don't really want to deal with the overhead of mutexes or
> semaphores. Thanks.

I believe setting a flag /is/ an atomic action. It's when you want to
bundle multiple operations as an atom that problems may occur

You are wrong - at least on systems with multiple processors.

/Peter


Not true Oh wise one. Some machine architectures have special
'interlocked' machine instructions of the sort TSTI, INCI, DECI,
etc which are garanteed to use a single bus transaction regardless
of how many processors (i.e. read/write without freeing the bus).
Some other machines use interlocked transactions by default and
others no such instructions. But if the processor can be used in
a multiprocessor then there is defintely some feature that
supports these functions which can be accessed by assembly and
maybe by your compiler.

You will have to examine the machine language for the particular
architecture. If you find such instructions then you need to
test to see if your compiler will generate such instruction or
use the asm directive.

Jul 22 '05 #6

P: n/a

"Richard Head" <rh***@comcast.net> skrev i en meddelelse
news:pa****************************@comcast.net...
On Wed, 14 Jan 2004 11:28:01 +0100, Peter Koch Larsen wrote:

"Jeff Schwab" <je******@comcast.net> skrev i en meddelelse
news:88********************@comcast.com...
Shayan wrote:
> Is there a boolean flag that can be set atomically without needing to
> wrap it in a mutex? This flag will be checked constantly by multiple
> threads so I don't really want to deal with the overhead of mutexes or > semaphores. Thanks.
I believe setting a flag /is/ an atomic action. It's when you want to
bundle multiple operations as an atom that problems may occur

You are wrong - at least on systems with multiple processors.

/Peter


Not true Oh wise one. Some machine architectures have special
'interlocked' machine instructions of the sort TSTI, INCI, DECI,
etc which are garanteed to use a single bus transaction regardless
of how many processors (i.e. read/write without freeing the bus).
Some other machines use interlocked transactions by default and
others no such instructions. But if the processor can be used in
a multiprocessor then there is defintely some feature that
supports these functions which can be accessed by assembly and
maybe by your compiler.

You will have to examine the machine language for the particular
architecture. If you find such instructions then you need to
test to see if your compiler will generate such instruction or
use the asm directive.

And how do you do that in C++?

/Peter
Jul 22 '05 #7

P: n/a
Peter Koch Larsen wrote:
"Jeff Schwab" <je******@comcast.net> skrev i en meddelelse
news:88********************@comcast.com...
Shayan wrote:
Is there a boolean flag that can be set atomically without needing to
wrap it in a mutex? This flag will be checked constantly by multiple
threads so I don't really want to deal with the overhead of mutexes or
semaphores. Thanks.

I believe setting a flag /is/ an atomic action. It's when you want to
bundle multiple operations as an atom that problems may occur


You are wrong - at least on systems with multiple processors.


No, I'm not. The machines I use most have from two to fourteen
processors. All the processors on a given machine share some memory.

Jul 22 '05 #8

P: n/a

"Jeff Schwab" <je******@comcast.net> wrote in message news:27********************@comcast.com...
Peter Koch Larsen wrote:
"Jeff Schwab" <je******@comcast.net> skrev i en meddelelse
news:88********************@comcast.com...
Shayan wrote:

Is there a boolean flag that can be set atomically without needing to
wrap it in a mutex? This flag will be checked constantly by multiple
threads so I don't really want to deal with the overhead of mutexes or
semaphores. Thanks.
I believe setting a flag /is/ an atomic action. It's when you want to
bundle multiple operations as an atom that problems may occur


You are wrong - at least on systems with multiple processors.


No, I'm not. The machines I use most have from two to fourteen
processors. All the processors on a given machine share some memory.


That doesn't say anything about automic operations. More is involved then
just sharing memory. Do these things have cache? It's extremely rare to
see a machine the memory itself is synchronized (the HEP was unique in
this regard).

Jul 22 '05 #9

P: n/a
Ron Natalie wrote:
"Jeff Schwab" <je******@comcast.net> wrote in message news:27********************@comcast.com...
Peter Koch Larsen wrote:
"Jeff Schwab" <je******@comcast.net> skrev i en meddelelse
news:88********************@comcast.com...
Shayan wrote:
>Is there a boolean flag that can be set atomically without needing to
>wrap it in a mutex? This flag will be checked constantly by multiple
>threads so I don't really want to deal with the overhead of mutexes or
>semaphores. Thanks.
I believe setting a flag /is/ an atomic action. It's when you want to
bundle multiple operations as an atom that problems may occur
You are wrong - at least on systems with multiple processors.
No, I'm not. The machines I use most have from two to fourteen
processors. All the processors on a given machine share some memory.

That doesn't say anything about automic operations.


Yes, it does. The memory -- the place where the datum is stored -- is
shared among the processors. A write is atomic.
More is involved then
just sharing memory. Do these things have cache? It's extremely rare to
see a machine the memory itself is synchronized (the HEP was unique in
this regard).


Keeping the cache in sync with the memory is done at a much lower level.
It's the concern of the hardware & the OS.

Jul 22 '05 #10

P: n/a

"Jeff Schwab" <je******@comcast.net> wrote in message
news:R7********************@comcast.com...
Ron Natalie wrote:
"Jeff Schwab" <je******@comcast.net> wrote in message news:27********************@comcast.com...
Peter Koch Larsen wrote:

"Jeff Schwab" <je******@comcast.net> skrev i en meddelelse
news:88********************@comcast.com...
>Shayan wrote:
>
>
>>Is there a boolean flag that can be set atomically without needing to
>>wrap it in a mutex? This flag will be checked constantly by multiple
>>threads so I don't really want to deal with the overhead of mutexes or>>semaphores. Thanks.
>
>
>I believe setting a flag /is/ an atomic action. It's when you want to
>bundle multiple operations as an atom that problems may occur
>

You are wrong - at least on systems with multiple processors.

No, I'm not. The machines I use most have from two to fourteen
processors. All the processors on a given machine share some memory.

That doesn't say anything about automic operations.


Yes, it does. The memory -- the place where the datum is stored -- is
shared among the processors. A write is atomic.
More is involved then
just sharing memory. Do these things have cache? It's extremely rare to see a machine the memory itself is synchronized (the HEP was unique in
this regard).


Keeping the cache in sync with the memory is done at a much lower level.
It's the concern of the hardware & the OS.


I'm with Ron on this one:
The memory can't be kept totally in sync in the way that I think is being
discussed here -
think about it - it would hammer performance.
The OS helps but only at certain points which means that you have to use
things like mutexes for memory shared between
processors. The locking and unlocking of the mutexes consitute 'memory
barriers'
Locking the mutex throws out cached reads so that you get any new stuff in
the memory.
Unlocking the mutex flushes out cached writes.
Obviously it is possible to have an machine code instruction that does the
whole lot - that is how mutexes in shared memory are written.

Anyway the original poster seemed to want:

volatile bool* flag;

while(flag)
;
flag = true;

This is unlikely to work even on a single processor machine.

Getting back to C++ - I think I read somewhere that there is a clash between
C++ and the POSIX threads decls but
I have never had any problems.
Jul 22 '05 #11

P: n/a
Nick Hounsome wrote:
"Jeff Schwab" <je******@comcast.net> wrote in message
news:R7********************@comcast.com...
Ron Natalie wrote:
"Jeff Schwab" <je******@comcast.net> wrote in message
news:27********************@comcast.com...
Peter Koch Larsen wrote:
>"Jeff Schwab" <je******@comcast.net> skrev i en meddelelse
>news:88********************@comcast.com...
>
>
>
>>Shayan wrote:
>>
>>
>>
>>>Is there a boolean flag that can be set atomically without needing to
>>>wrap it in a mutex? This flag will be checked constantly by multiple
>>>threads so I don't really want to deal with the overhead of mutexes
or
>semaphores. Thanks.
>>
>>
>>I believe setting a flag /is/ an atomic action. It's when you want to
>>bundle multiple operations as an atom that problems may occur
>>
>
>You are wrong - at least on systems with multiple processors.

No, I'm not. The machines I use most have from two to fourteen
processors. All the processors on a given machine share some memory.

That doesn't say anything about automic operations.
Yes, it does. The memory -- the place where the datum is stored -- is
shared among the processors. A write is atomic.

More is involved then
just sharing memory. Do these things have cache? It's extremely rare
to
see a machine the memory itself is synchronized (the HEP was unique in
this regard).


Keeping the cache in sync with the memory is done at a much lower level.
It's the concern of the hardware & the OS.

I'm with Ron on this one:
The memory can't be kept totally in sync in the way that I think is being
discussed here -
think about it - it would hammer performance.


That's why caching is used.
The OS helps but only at certain points which means that you have to use
things like mutexes for memory shared between
processors. The locking and unlocking of the mutexes consitute 'memory
barriers'
Locking the mutex throws out cached reads so that you get any new stuff in
the memory.
Unlocking the mutex flushes out cached writes.
Obviously it is possible to have an machine code instruction that does the
whole lot - that is how mutexes in shared memory are written.


How do you think mutexes work? They rely on the fact that a write is
atomic. Keep in mind that the OP was not asking about a read after
write ("RAW"), only a single write.

Jul 22 '05 #12

P: n/a

"Jeff Schwab" <je******@comcast.net> skrev i en meddelelse
news:Ve********************@comcast.com...
Nick Hounsome wrote:
"Jeff Schwab" <je******@comcast.net> wrote in message
news:R7********************@comcast.com...
Ron Natalie wrote:

"Jeff Schwab" <je******@comcast.net> wrote in message


news:27********************@comcast.com...
>Peter Koch Larsen wrote:
>
>
>>"Jeff Schwab" <je******@comcast.net> skrev i en meddelelse
>>news:88********************@comcast.com...
>>
>>
>>
>>>Shayan wrote:
>>>
>>>
>>>
>>>>Is there a boolean flag that can be set atomically without needing to>>>>wrap it in a mutex? This flag will be checked constantly by multiple>>>>threads so I don't really want to deal with the overhead of mutexes


or
>>>>semaphores. Thanks.
>>>
>>>
>>>I believe setting a flag /is/ an atomic action. It's when you want to>>>bundle multiple operations as an atom that problems may occur
>>>
>>
>>You are wrong - at least on systems with multiple processors.
>
>No, I'm not. The machines I use most have from two to fourteen
>processors. All the processors on a given machine share some memory.
>
That doesn't say anything about automic operations.

Yes, it does. The memory -- the place where the datum is stored -- is
shared among the processors. A write is atomic.
More is involved then
just sharing memory. Do these things have cache? It's extremely rare


to
see a machine the memory itself is synchronized (the HEP was unique in
this regard).

Keeping the cache in sync with the memory is done at a much lower level.
It's the concern of the hardware & the OS.

I'm with Ron on this one:
The memory can't be kept totally in sync in the way that I think is being discussed here -
think about it - it would hammer performance.


That's why caching is used.
The OS helps but only at certain points which means that you have to use
things like mutexes for memory shared between
processors. The locking and unlocking of the mutexes consitute 'memory
barriers'
Locking the mutex throws out cached reads so that you get any new stuff in the memory.
Unlocking the mutex flushes out cached writes.
Obviously it is possible to have an machine code instruction that does the whole lot - that is how mutexes in shared memory are written.


How do you think mutexes work? They rely on the fact that a write is
atomic. Keep in mind that the OP was not asking about a read after
write ("RAW"), only a single write.


Mutexes work because they use specialpurpose instructions - on the intel
cpu's using the "lock"-prefix. You can not do that in (portable) C++.

Kind regards
Peter
Jul 22 '05 #13

P: n/a
Peter Koch Larsen wrote:
"Jeff Schwab" <je******@comcast.net> skrev i en meddelelse
news:Ve********************@comcast.com...
Nick Hounsome wrote:
"Jeff Schwab" <je******@comcast.net> wrote in message
news:R7********************@comcast.com...
Ron Natalie wrote:
>"Jeff Schwab" <je******@comcast.net> wrote in message

news:27********************@comcast.com...
>>Peter Koch Larsen wrote:
>>
>>
>>
>>>"Jeff Schwab" <je******@comcast.net> skrev i en meddelelse
>>>news:88********************@comcast.com.. .
>>>
>>>
>>>
>>>
>>>>Shayan wrote:
>>>>
>>>>
>>>>
>>>>
>>>>>Is there a boolean flag that can be set atomically without needing
to
>>>wrap it in a mutex? This flag will be checked constantly by
multiple
>>>threads so I don't really want to deal with the overhead of mutexes

or
>>>>>semaphores. Thanks.
>>>>
>>>>
>>>>I believe setting a flag /is/ an atomic action. It's when you want
to
>>bundle multiple operations as an atom that problems may occur
>>>>
>>>
>>>You are wrong - at least on systems with multiple processors.
>>
>>No, I'm not. The machines I use most have from two to fourteen
>>processors. All the processors on a given machine share some memory.
>>
>
>
>That doesn't say anything about automic operations.

Yes, it does. The memory -- the place where the datum is stored -- is
shared among the processors. A write is atomic.

>More is involved then
>just sharing memory. Do these things have cache? It's extremely rare

to
>see a machine the memory itself is synchronized (the HEP was unique in
>this regard).

Keeping the cache in sync with the memory is done at a much lower level.
It's the concern of the hardware & the OS.

I'm with Ron on this one:
The memory can't be kept totally in sync in the way that I think is
being
discussed here -
think about it - it would hammer performance.


That's why caching is used.

The OS helps but only at certain points which means that you have to use
things like mutexes for memory shared between
processors. The locking and unlocking of the mutexes consitute 'memory
barriers'
Locking the mutex throws out cached reads so that you get any new stuff
in
the memory.
Unlocking the mutex flushes out cached writes.
Obviously it is possible to have an machine code instruction that does
the
whole lot - that is how mutexes in shared memory are written.


How do you think mutexes work? They rely on the fact that a write is
atomic. Keep in mind that the OP was not asking about a read after
write ("RAW"), only a single write.

Mutexes work because they use specialpurpose instructions - on the intel
cpu's using the "lock"-prefix. You can not do that in (portable) C++.


Mutexes can be provided without any such instructions. It might
interest you to look at some of the many-splendored implementations of
the "wait" and "signal" semaphore functions. At any rate, you don't
need a mutex to make a write atomic, unless you're implementing a cache
and are using "write" to mean "input to cache."

And as far as portable C++ goes, a write certainly is atomic, since the
standard provides no support for multiple simultaneous threads of
execution. Beyond that, I don't believe I've ever seen a system where a
write was not an atomic operation. In fact, if thread 1 writes
succesfully to a variable, and thread 2 immediately reads from the same
variable and sees anything other than the value written by thread 1,
then thread 2 is not accessing the same variable. A write is atomic by
definition. If you don't believe so, then we mean different things by
"write."
Jul 22 '05 #14

P: n/a

"Jeff Schwab" <je******@comcast.net> skrev i en meddelelse
news:7L********************@comcast.com...
Peter Koch Larsen wrote:
"Jeff Schwab" <je******@comcast.net> skrev i en meddelelse
news:Ve********************@comcast.com...

[snip]


Mutexes work because they use specialpurpose instructions - on the intel
cpu's using the "lock"-prefix. You can not do that in (portable) C++.
Mutexes can be provided without any such instructions. It might
interest you to look at some of the many-splendored implementations of
the "wait" and "signal" semaphore functions. At any rate, you don't
need a mutex to make a write atomic, unless you're implementing a cache
and are using "write" to mean "input to cache."

And as far as portable C++ goes, a write certainly is atomic, since the
standard provides no support for multiple simultaneous threads of
execution.


Standard C++ has no notion of threads (yet), but this does not mean that you
can't call portable C++ code from a multi-threading program.
Beyond that, I don't believe I've ever seen a system where a
write was not an atomic operation. In fact, if thread 1 writes
succesfully to a variable, and thread 2 immediately reads from the same
variable and sees anything other than the value written by thread 1,
then thread 2 is not accessing the same variable. A write is atomic by
definition. If you don't believe so, then we mean different things by
"write."


I am sorry, but you are simply plain wrong. But do not take my word for it -
go to comp.programming.threads and study some of the many threads discussing
this very issue.

/Peter
Jul 22 '05 #15

P: n/a
In article <Ve********************@comcast.com>, je******@comcast.net
says...

[ ... ]
I'm with Ron on this one:
The memory can't be kept totally in sync in the way that I think is being
discussed here -
think about it - it would hammer performance.
That's why caching is used.


Yes, but what you're advocating would negate (most of) the benefits of
the cache.

Specifically, if you keep the memory in synch with the contents of the
cache, you have a write-through cache.

Most modern systems use write-back caches. These allow the system
memory to become out of synch with the contents of the cache. In this
situation, the cache typically marks the cache line as modified.

In a machine that wants to do so, it's still possible to provide a
coherent view of memory with a write-back cache though. All the
processors snoop all bus transactions. When there's a read transaction
on a location that's held in a modified cache line, the processor puts
the transaction on hold, then writes its modified cache line back to
memory, and finally allows the original bus transaction to complete.

This works well for a small number of processors (e.g. 8 or fewer
processors). You can extend it a little bit by adding some direct
processor-processor links, so instead of writing the data to memory, and
then the second processor reading it back from memory, the processor
with the modified line sends it directly to the processor that needs it.

Beyond a few dozen or so processors, that starts to break down again.
If you want to support a really large number of processors (e.g. tens of
thousands) you nearly NEED to decouple the processors from each other to
a greater degree. In the process, you essentially always end up with a
situation where processors do not have a coherent view of memory unless
you do something special to cause it (and you generally want to avoid
that something special, because it's almost inevitably extremely
expensive).
How do you think mutexes work? They rely on the fact that a write is
atomic. Keep in mind that the OP was not asking about a read after
write ("RAW"), only a single write.


No -- a mutex usually works by internally doing things that are non-
portable.

In the end, the bottom line is pretty simple: the C++ standard really
only addresses atomicity in one very limited area -- in the presence of
signals, sig_atomic_t is a type that can be manipulated atomically.

That doesn't guarantee you _anything_ about threads though. For small
scale-multiprocessing, chances are it'll work, but there's never any
guarantee that it will, and beyond a certain scale it's almost
guaranteed to fail (though, if it's any comfort, so is nearly everything
that's portable).

--
Later,
Jerry.

The universe is a figment of its own imagination.
Jul 22 '05 #16

P: n/a

"Jerry Coffin" <jc*****@taeus.com> wrote in message news:MP************************@news.clspco.adelph ia.net...
Specifically, if you keep the memory in synch with the contents of the

cache, you have a write-through cache.

Even a write through cache doesn't guarantee atomic access.
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.

There is just no way to assume atomic operations.
Jul 22 '05 #17

P: n/a
Ron Natalie wrote:
"Jerry Coffin" <jc*****@taeus.com> wrote in message news:MP************************@news.clspco.adelph ia.net...
Specifically, if you keep the memory in synch with the contents of the


cache, you have a write-through cache.


Even a write through cache doesn't guarantee atomic access.
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.

There is just no way to assume atomic operations.


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

Jul 22 '05 #18

P: n/a

"Jeff Schwab" <je******@comcast.net> wrote in message
news:f-********************@comcast.com...
Ron Natalie wrote:
"Jerry Coffin" <jc*****@taeus.com> wrote in message news:MP************************@news.clspco.adelph ia.net...
Specifically, if you keep the memory in synch with the contents of the

cache, you have a write-through cache.


Even a write through cache doesn't guarantee atomic access.
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.

There is just no way to assume atomic operations.


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


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
Jul 22 '05 #19

P: n/a

"Jeff Schwab" <je******@comcast.net> wrote in message news:f-********************@comcast.com...
What is the program-visible effect of a non-atomic write?


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.

Jul 22 '05 #20

P: n/a
In article <40***********************@news.newshosting.com> ,
ro*@sensor.com says...

"Jerry Coffin" <jc*****@taeus.com> wrote in message news:MP************************@news.clspco.adelph ia.net...
Specifically, if you keep the memory in synch with the contents of the cache, you have a write-through cache.

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.

--
Later,
Jerry.

The universe is a figment of its own imagination.
Jul 22 '05 #21

P: n/a
In article <f-********************@comcast.com>, je******@comcast.net
says...

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


Reading a bad value is the most common result.

--
Later,
Jerry.

The universe is a figment of its own imagination.
Jul 22 '05 #22

P: n/a
Michael Furman wrote:
"Jeff Schwab" <je******@comcast.net> wrote in message
news:f-********************@comcast.com...
Ron Natalie wrote:
"Jerry Coffin" <jc*****@taeus.com> wrote in message
news:MP************************@news.clspco.adelph ia.net...
Specifically, if you keep the memory in synch with the contents of the

cache, you have a write-through cache.
Even a write through cache doesn't guarantee atomic access.
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.

There is just no way to assume atomic operations.


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

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.

Jul 22 '05 #23

P: n/a
Ron Natalie wrote:
"Jeff Schwab" <je******@comcast.net> wrote in message news:f-********************@comcast.com...

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

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.

Jul 22 '05 #24

P: n/a
Jerry Coffin wrote:
In article <f-********************@comcast.com>, je******@comcast.net
says...

[ ... ]

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.

Jul 22 '05 #25

P: n/a
In article <4a********************@comcast.com>, je******@comcast.net
says...

[ ... ]
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.


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.

--
Later,
Jerry.

The universe is a figment of its own imagination.
Jul 22 '05 #26

P: n/a
Jerry Coffin wrote:
In article <4a********************@comcast.com>, je******@comcast.net
says...

[ ... ]

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.

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.

Jul 22 '05 #27

P: n/a
Jeff Schwab wrote:
Ron Natalie wrote:
"Jeff Schwab" <je******@comcast.net> wrote in message
news:f-********************@comcast.com...

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


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.


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?

Jul 22 '05 #28

P: n/a
On Sat, 17 Jan 2004 00:30:33 -0500 in comp.lang.c++, Jeff Schwab
<je******@comcast.net> was alleged to have written:
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.

Jul 22 '05 #29

P: n/a
David Harmon wrote:
On Sat, 17 Jan 2004 00:30:33 -0500 in comp.lang.c++, Jeff Schwab
<je******@comcast.net> was alleged to have written:
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.


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.

Jul 22 '05 #30

P: n/a

Jeff Schwab wrote:
[...]
Access to the memory


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

regards,
alexander.
Jul 22 '05 #31

P: n/a

"Jeff Schwab" <je******@comcast.net> wrote in message
news:4a********************@comcast.com...
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
Jul 22 '05 #32

P: n/a
In article <A9********************@comcast.com>, je******@comcast.net
says...

[ ... ]
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.

--
Later,
Jerry.

The universe is a figment of its own imagination.
Jul 22 '05 #33

P: n/a
Michael Furman wrote:
"Jeff Schwab" <je******@comcast.net> wrote in message
news:4a********************@comcast.com...
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. :)

Jul 22 '05 #34

P: n/a
Alexander Terekhov wrote:
Jeff Schwab wrote:
[...]
To the nitpickers who may shortly begin ranting about caches: I mean

http://google.com/groups?selm=3D81DF...F9B50%40web.de

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.

Jul 22 '05 #35

P: n/a
Jerry Coffin wrote:
In article <A9********************@comcast.com>, je******@comcast.net
says...

[ ... ]

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


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.

Jul 22 '05 #36

P: n/a

Jeff Schwab wrote:
[...]
That has nothing to do with whether a write is atomic.


http://groups.google.com/groups?selm...3DFC9%40web.de
http://groups.google.com/groups?selm...FD5EA%40web.de

regards,
alexander.
Jul 22 '05 #37

P: n/a

"Jerry Coffin" <jc*****@taeus.com> wrote in message
news:MP************************@news.clspco.adelph ia.net...
In article <A9********************@comcast.com>, je******@comcast.net
says...

[ ... ]
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.


End even more - even in case of one bit, I don't think that there's any
requirement or guarantee, that if you change false->true, every reader
will see sequence "false.false.....true.true..." rather then
"false.false.true.false.true.true.....".
For example I worked with flash memory, that gave some strange values
for some time period after write (actually one bit was flashing and other
bits were undefined).

Regards,
Michael
Jul 22 '05 #38

P: n/a
> In fact, if thread 1 writes
succesfully to a variable, and thread 2 immediately reads from the same
variable and sees anything other than the value written by thread 1,
then thread 2 is not accessing the same variable.


:O

Try that on an Itanium...

Ever heard of memory visibility?!?!?!

;(
Jul 22 '05 #39

P: n/a
Jeff Schwab wrote:
[SNIP]
Mutexes can be provided without any such instructions. It might
interest you to look at some of the many-splendored implementations of
the "wait" and "signal" semaphore functions. At any rate, you don't
need a mutex to make a write atomic, unless you're implementing a
cache and are using "write" to mean "input to cache."

And as far as portable C++ goes, a write certainly is atomic, since
the standard provides no support for multiple simultaneous threads of
execution. Beyond that, I don't believe I've ever seen a system
where a write was not an atomic operation.
I have only seen such systems. For example on Intel, writing a word sized
thing in C/C++ is not guaranteed to be atomic, since it might happen not to
start on word boundary. But being atomic is more than being
non-interruptable!
In fact, if thread 1
writes succesfully to a variable, and thread 2 immediately reads from
the same variable and sees anything other than the value written by
thread 1, then thread 2 is not accessing the same variable.
And this is exactly what happens in a multi-CPU (SMP) system, if you write
without locking and flushing (memory read/write barriers). Even reading
such thing might need a barrier, depending on the architecture.
A write is atomic by definition.
If you don't believe so, then we mean
different things by "write."


A write does not even happen - by definition - when you think it should.
CPUs might rearrange reads and writes to different areas into a more
preferrable (faster) sequence. Defferred reads and writes they are called,
IIRC. In any case: write (on the C and C++ level) is not atomic and it is
definitely not guaranteed to be atomic in regards to threads. Especially on
SMP. In C and C++ *only* the reading and writing the type sig_atomic_t is
guaranteed to be atomic and *only* in the face of signals.

And I guess I know what I am talking about, because I have implemented
atomic read, write and icrement/decrement etc. in assembly for Sparc as well
as for Intel. And - believe me - it looks pretty different from the code a
C or C++ compiler generates.

--
Attila aka WW
Jul 22 '05 #40

P: n/a
> Try that on an Itanium...

Ever heard of memory visibility?!?!?!


This applies only to cpus that require barriers.

In order to get it to work you would use simple atomic ops coupled with
acquire/release memory semantics on the shared value.

Mutexs of all sorts have to use some sort of acquire/release barriers:

Lock()
{
int iSpins = 0;

// Atomic, with acquire
while ( CAS_Acquire( &m_lockstate, 0, 1 ) )
{
// Contention point!

// See if we should spin or wait
if ( ( ++iSpins ) < CPU's*2 )
{
// pause opcode

sched_yield();
}

else
{
// Atomic add to kernel waitset, and wait
}
}

// Acquire says we own all the updates, AFTER good cas
}
Unlock()
{
// Atomic, with release
int iRet = CAS_Release( &m_lockstate, 1, 0 );

assert( iRet == 1 );

// Release says we released all the updates we made, BEFORE good cas

// Atomic check for waiters, and wake one
}

For a lock-free version you would simply omit the slow path and treat it as
a traditional CAS loop, and have the CAS work DIRECTLY on your own provided
state.
Jul 22 '05 #41

P: n/a
> And I guess I know what I am talking about, because I have implemented
atomic read, write and icrement/decrement etc. in assembly for Sparc as well as for Intel. And - believe me - it looks pretty different from the code a C or C++ compiler generates.


Imagine if the compiler treated every ' someval++ ' as:

lock xadd [...], ... /* with a barrier */

!

:O
Jul 22 '05 #42

P: n/a
SenderX wrote:
And I guess I know what I am talking about, because I have
implemented atomic read, write and icrement/decrement etc. in
assembly for Sparc as well as for Intel. And - believe me - it
looks pretty different from the code a C or C++ compiler generates.


Imagine if the compiler treated every ' someval++ ' as:

lock xadd [...], ... /* with a barrier */


Still would not work on certain architectures.

--
Attila aka WW
Jul 22 '05 #43

This discussion thread is closed

Replies have been disabled for this discussion.