atomic flag

[Shayan]

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

 

[Jeff Schwab]

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

 

[Ron Natalie]

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.

 

[Nick Hounsome]

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.

 

[Peter Koch Larsen]

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

 

[Richard Head]

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.

 

[Peter Koch Larsen]

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

 

[Jeff Schwab]

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.

 

[Ron Natalie]

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

 

[Jeff Schwab]

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.

 

[Nick Hounsome]

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


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.

 

[Jeff Schwab]

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.

 

[Peter Koch Larsen]

That's why caching is used.


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

 

[Jeff Schwab]

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

 

[Peter Koch Larsen]

"Jeff Schwab" <[email protected]> skrev i en meddelelse

[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

 

[Jerry Coffin]

[ ... ]

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

 

[Ron Natalie]

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.

 

[Jeff Schwab]

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?

 

[Michael Furman]

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

 

[Ron Natalie]

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.