Paul wrote:

...

Synchronous cancellation may be simulated by setting a simple flag polled by the cancellable thread. (Appropriate memory barriers must be placed after setting and before polling the flag. In the absence of portable memory barrier facilities, one may protect the flag with a mutex, though that's annoyingly heavyweight.) However this does not

just out of curiousity, why do you think you need a memory barrier on a flag? you would have 1 writer and 1 reader... either the reader reads false or true, and once the writer has set it to true... thats it, the reader will read true on the next pass.

even if the reader is reading the same time as the writer is writing, and byte-sized memory writes are not atomic (which i think they are), then the read will still evaluate to true, which is what is desired anyway.

so theres no need for a mutex in this case? even if there were multiple writers, its a one-way flag set operation, all would be trying to set the flag to true if all were writing at the same time, so all would get the desired result?

Paul, When the flag has changed the memory semantics of your system maybe such that your cpu doesn't see the change for quite a while without memory barriers. If it changes, say flip flops between true and false (not relevant to your case above), then you could end up with different values everywhere at once which may be inconvenient to your programs correctness. HTH, Matt. matthurd@acm.org FWIW: Here is memory barrier definition I use on win32, though it is an inapproprite interface for generic consumption: /*___________________________________________________________ created: 2004-12-7 7:18 filename: fence.hpp author: Matt Hurd purpose: ____________________________________________________________*/ #ifndef fence_hpp_2004127 #define fence_hpp_2004127 namespace synch { struct fence { static void load () { __asm lfence; } static void store () { __asm sfence; } static void memory () { __asm mfence; } static void flush () { __asm cpuid; } }; } // namespace #endif

Paul wrote: good lord, assembler? doesn't the 'volatile' keyword fix the problem you describe?

I'm afraid it doesn't. You might want to check the archives for mentions regarding the double checked locking issues which highlight the issue, or read the paper http://www.aristeia.com/Papers/DDJ_Jul_Aug_2004_revised.pdf

if the flag is going to be flipping back and forth, then sure, even with memory barriers you will have threads which think the value is different... eg, you have 2 long-running threads that check the value and do some calculation that take 5 seconds or so. lets assume they dont sync when reading the flag, so then thread A could check the flag and read false, while thread B checked the flag 4 seconds ago and currently thinks its true. so you have inconsistencies there anyway, right?

It depends, there are lock free ways to do things. The important thing is that after the memory barrier, everyone is guaranteed to be on the same pages w.r.t. the value when they next check it.

otherwise, the flag is set and its only a matter of time before the CPU sees the correct value ('die' in the previous email's case) and dies. if the flag is for protecting resources, then of course you need volatile/guards/etc, otherwise it can be just a 'lazy cancel', when the thread finally reads the right value, it quits. how many cycles-lag would that be anyway? is this only a problem on exotic platforms?

I have found it to be a big issue for my work on a simple win32 dual proc box. It can be a surprisingly long time before a value propagates. I'm not entirely certain the value is guaranteed to ever propagate, which is an issue. Another example, checking whether a message queue is empty can be significantly faster ( 2 to 4 times on ia32 ) with the appropriate use of memory barriers rather than a mutex / critical section.

is this cpu-cache problem actually a problem in this 'kill-flag' case, do you really think you need memory barriers on a flag like this?

On a single IA32 processor, no. On a dual processor, maybe, it depends. Also, I'm not sure about the guarantee of the value propagating eventually, I have encountered cases where it does seem to propagate at all probably due to the compiler optimizations. I've been meaning to submit an interface for memory fences based on the work of others I've seen poking around. It seems that to cope with most architectures you need stuff like: load_load, load_store, store_store, store_load barriers and the like to support memory architecture with more relaxed semantics, some of which are no-ops on IA32. This should be a fundamental building block on which boost can build. It would also mean having a different category of builds for such a library, as a compilation would be based on only on the os, compiler and stl, but the hardware architecture as well. For example, pre lfence, sfence and mfence on ia32 you had to do a cpuid as a memory fence. Though a locked bus instruction might have been enough, I think. So an implementation even just on plain ia32 would have to have different architecture #defines or for different generational ia32s. The later fences came with SSE2 for example. Check out http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1680.pdf for some more insight from cleverer people than I. Regards, Matt. matthurd@acm.org

Paul wrote:

...

Synchronous cancellation may be simulated by setting a simple flag polled by the cancellable thread. (Appropriate memory barriers must be placed after setting and before polling the flag. In the absence of portable memory barrier facilities, one may protect the flag with a mutex, though that's annoyingly heavyweight.) However this does not

just out of curiousity, why do you think you need a memory barrier on a flag? you would have 1 writer and 1 reader... either the reader reads false or true, and once the writer has set it to true... thats it, the reader will read true on the next pass.

In practice, if you use "volatile" then the compiler will probably generate code to read the flag from memory every time and the reader will probably see the change, possibly after some small delay for it to work its way through the write queue on the processor that the writer is running on. AFAIK no standard or specification guarantees this.

even if the reader is reading the same time as the writer is writing, and byte-sized memory writes are not atomic (which i think they are),

If they aren't then mutexes won't actually help much. Consider for example char a[2] with access to a[0] and a[1] controlled by different mutexes.

then the read will still evaluate to true, which is what is desired anyway.

so theres no need for a mutex in this case? even if there were multiple writers, its a one-way flag set operation, all would be trying to set the flag to true if all were writing at the same time, so all would get the desired result?

In practice I think that's true, but what do you think guarantees that? If there's no guarantee then it might stop working in future. Ben.

Peter Dimov wrote:

Ben Hutchings wrote:

...

Paul wrote:

...

...

Synchronous cancellation may be simulated by setting a simple flag polled by the cancellable thread. (Appropriate memory barriers must be placed after setting and before polling the flag. In the absence of portable memory barrier facilities, one may protect the flag with a mutex, though that's annoyingly heavyweight.) However this does not

just out of curiousity, why do you think you need a memory barrier on a flag? you would have 1 writer and 1 reader... either the reader reads false or true, and once the writer has set it to true... thats it, the reader will read true on the next pass.

In practice, if you use "volatile" then the compiler will probably generate code to read the flag from memory every time and the reader will probably see the change, possibly after some small delay for it to work its way through the write queue on the processor that the writer is running on. AFAIK no standard or specification guarantees this.

If the cache of the reader CPU isn't notified about the change (which is only guaranteed to happen on an acquire) the reader may never observe the modified value.

I agree that there's no such guarantee, which is why I wouldn't advocate depending on this working. However, without a cache coherency protocol, independent shared variables cannot share a cache line and synchronisation is absurdly slow, and I'm not aware of any multiprocessor systems supporting general multithreading that don't have such a protocol. Write queues are of finite length and are eagerly flushed to cache to avoid stalling later memory-writing instructions where possible. Ben.

Chris Coleman wrote:

Hi Ben, and others.

Many thanks for taking the time to reply to the original questions, they have proved most useful in providing me with a solution to my problem.

...

Depending on why and how the thread is sleeping, it may be possible to interrupt such a sleep by sending the thread a signal or writing to a pipe.

I'm still a little confused by this last sentence.

Under Unix, signals generally interrupt system calls, and you can configure whether the calls will be restarted or whether they will fail with an error code of EINTR (using setsigaction, if I remember correctly). What I don't know is whether Boost's condition variable implementation will restart the wait if it gets EINTR; it might be worth checking the source. I mentioned pipes because if the thread normally waits using select() you can create a pipe to be included in the read set and interrupt the wait at any time by writing an arbitrary byte to that.

At present I have opted for an arbitrary time on a timed wait on the condition variable that was causing the threads to sleep. This seems to work, but obviously there is a delay in the time the thread takes to die of up to the length of the timed wait. All the threads are waiting on the same condition variable, I can find nothing in the Docs about anything else that will cause the threads to wake while waiting on a condition variable.

Notify_one is no good since it is unspecified which thread shall be woken, and notify_all seems a little excessive when only a specific thread needs waking. Although I guess once woken all the other threads will do will be to see that their living flag is still true, and that there are no tasks to process and as such go back to sleep. Whatever solution is chosen it needs to be highly portable.

If all the threads are doing the same thing, does it matter which one you instruct to terminate? Perhaps you could just put a "stop" message on the work queue and use notify_one. Ben.

Roland Schwarz wrote:

It might be a year or so now, that I suggested a thread alert framework that is entirely built on top of the currenty boost thread. And I am sucessfully using it. It provides me almost everything I would have expected from cancellation. (Altough I know it cannot provide true async cancellation.)

As far as I remember I also added an example demonstrating fake cancellation behaviour.

But surprisingly, given the ever popping up questions of cancellation being added to the library I never got any feedback on my proposal.

So I invite you to give it a chance. The thread alert can be downloaded from the file area (the vault).

Sounds interesting. Would you provide a full URL? Thanks, Daniel Krügler