Sign in Join

Live chat for Free Pascal, Lazarus, Delphi and every Pascal programmer.

Mailing lists / fpc-other / 2011-06

Multi-threaded programming (was: volatile variables)

3 messages · 2 people ·

Reply by email Subscribe to this list Your subscription

Read-only archive. Use j and k to move between messages.

Jonas Maebe

(moved here from fpc-devel)

Hans-Peter Diettrich wrote 12 lines
Vinzent Höfler schrieb: >> When it's up to every coder, to insert explicit synchronization >> whenever required, how to determine the places where explicit code >> is required? > By careful analysis. Although there may exist tools which detect > potentially > un-synchronised accesses to shared variables, there will be no tool > that > inserts synchronisation code automatically for you. I wouldn't like such tools, except the compiler itself :-(

Data races can only be detected without false positives/negatives via dynamic analysis, by intercepting all memory accesses and all synchronization operations.

This will report all potential data races on the execution path of that particular run (i.e., not only the cases where some value actually did get lost due to timing during that particular run, but all of the ones that could have happened during that run), but on the other hand it's also *only* for that particular run (so potential data races on different execution paths will not be caught).

You can read about the principle here: http://escher.elis.ugent.be/publ/Edocs/DOC/P104_116.pdf (and it contains further references to other papers that go into even more detail).

If a program would contain nothing but FPC-compiled code it would in theory be possible to modify the RTL and the compiler to insert all required analysis code, but I would not consider that to be worth the effort. The reason is that it would only work for programs that do not contain assembler code and which do not perform any system calls (system calls can also read/write memory).

Show quoted text 11 lines
Consider the shareable bi-linked list, where insertion requires code like this: list.Lock; //prevent concurrent access ... //determine affected list elements new.prev := prev; //prev must be guaranteed to be valid new.next := next; prev.next := new; next.prev := new; list.Unlock; What can we expect from the Lock method/instruction - what kind of synchronizaton (memory barrier) can, will or should it provide?

Use a critical section as provided by the FPC RTL, and all necessary synchronization will be performed (including the required memory barriers). Manual memory barriers are only required if you use lock- free multithreading (which I would not recommend unless you are already an absolute expert in multi-threaded programming) or when writing your own synchronization primitives.

And to repeat what I mentioned before: the program state cannot become unsynchronized if a thread switches from one core to another in the middle of a critical section. If you (I don't mean you personally here) think that you are observing something like that, you have another bug. Using the standard synchronization primitives is all you need to write correct multi-threaded programs.

Show quoted text 9 lines
My understanding of a *full* cache synchronization would slow down not only the current core and cache, but also all other caches? If so, would it help to enclose above instructions in e.g. Synchronized begin update the links... end; so that the compiler can make all memory references (at least reads) occur read/write-through, inside such a code block?

Even if that were possible, disabling caching does in no way solve any kind of data race. It would slow down programs without any gain whatsoever as far as thread safety is concerned.

As Nikolai mentioned, you need a critical section (or a lock-free equivalent specific to an individual case, but that cannot be automatically generated -- and even the first published papers with manually constructed lock-free algorithms turned out to contain errors afterwards).

After these considerations I'd understand that using Interlocked instructions in the code would ensure such read/write-through, but merely as a side effect - they also lock the bus for every instruction,

They only did so on ancient x86 processors. Nowadays they don't anymore. They also never did on most other architectures.

We need a documentation of the FPC specific means of cache synchronization, with their guaranteed effects on every target[1].

Such documentation is not compiler-specific, but architecture- specific. The FPC documentation is not a tutorial on computer architecture, nor a tutorial on multi-threaded programming.

FPC exports routines that for all existing kinds of memory barriers (ReadBarrier, ReadDependencyBarrier, ReadWriteBarrier and WriteBarrier), as well as for various synchronization primitives (criticalsection/mutex, event/conditional signal, ...). That is the job of the compiler/RTL. Language extensions are of course always possible, but that is unrelated to "documentation of the FPC specific means of cache synchronization, with their guaranteed effects on every target" (language constructs by definition would have the same effect everywhere).

Tutorials and architecture documentation are a separate department.

Furthermore we need concrete examples[2], how (to what extent) it's required to use these special instructions/procedures, in examples like above.

Yes, many people could use tutorials about computer architecture, operating system principles and multi-threading. But again, those are completely unrelated to the development of FPC itself.

A good starter would probably be Module 4 of http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-823-computer-system-architecture-fall-2005/lecture-notes/

Jonas

Reply by email

Jonas Maebe

(moved to fpc-other because unrelated to developing FPC)

Andrew Brunner wrote
It remains to be seen/decided though, who's responsibility is it to ensure/enforce coherency? Jonas was suggesting that the posix implementation (but he probably meant kernel) was already doing that via CriticalSection.

There are two separate things:
a) coherency between two threads: here the programmer is responsible. Either by using mutex primitives from a library (which take care of the necessary memory barriers behind the scenes), or by manually inserting the required memory barriers (in combination with spinlocks or other atomic operations). Using atomic operations inside critical sections is useless if the data is always accessed from within code protected by that same mutex/critical section/... (it only makes code slower).
b) coherency within a single thread that is moved from one core to another core by the kernel: here the kernel is responsible, and the programmer nor compiler has to do anything.

As Hans-Peter mentioned in earlier message in this thread: if the kernel were not responsible for b) or if it had bugs for that functionality, then even single threaded would regularly crash on multi-core systems (the kernel tries to keep a single thread/process on the same cpu for speed reasons, but threads do migrate from time to time for various reasons).

Jonas

Reply by email

Hans-Peter Diettrich
to Jonas Maebe: (moved here from fpc-devel) Data races can only be detected without false…
(moved here from fpc-devel)

okay.

Show quoted text 13 lines
>>> When it's up to every coder, to insert explicit synchronization >>> whenever required, how to determine the places where explicit code >>> is required? >> By careful analysis. Although there may exist tools which detect >> potentially >> un-synchronised accesses to shared variables, there will be no tool that >> inserts synchronisation code automatically for you. > > I wouldn't like such tools, except the compiler itself :-( Data races can only be detected without false positives/negatives via dynamic analysis, by intercepting all memory accesses and all synchronization operations.

That's why I'd prefer to prevent the occurence of race conditions by certain means, eliminating the need for an error-prone and time consuming analysis.

Show quoted text 6 lines
This will report all potential data races on the execution path of that particular run (i.e., not only the cases where some value actually did get lost due to timing during that particular run, but all of the ones that could have happened during that run), but on the other hand it's also *only* for that particular run (so potential data races on different execution paths will not be caught).

Sic!

You can read about the principle here: http://escher.elis.ugent.be/publ/Edocs/DOC/P104_116.pdf (and it contains further references to other papers that go into even more detail).

[...]

Thanks for the link :-)

Show quoted text 18 lines
> Consider the shareable bi-linked list, where insertion requires code > like this: > list.Lock; //prevent concurrent access > ... //determine affected list elements > new.prev := prev; //prev must be guaranteed to be valid > new.next := next; > prev.next := new; > next.prev := new; > list.Unlock; > What can we expect from the Lock method/instruction - what kind of > synchronizaton (memory barrier) can, will or should it provide? Use a critical section as provided by the FPC RTL, and all necessary synchronization will be performed (including the required memory barriers). Manual memory barriers are only required if you use lock-free multithreading (which I would not recommend unless you are already an absolute expert in multi-threaded programming) or when writing your own synchronization primitives.

I'm just unsure about the effect of a (which one?) memory barrier. When EnterCriticalSection makes sure, that the cache is synchronized WRT eventually pending write-backs in other caches, all (my) expected problems have been solved.

Show quoted text 6 lines
And to repeat what I mentioned before: the program state cannot become unsynchronized if a thread switches from one core to another in the middle of a critical section. If you (I don't mean you personally here) think that you are observing something like that, you have another bug. Using the standard synchronization primitives is all you need to write correct multi-threaded programs.

Thanks for the confirmation :-)

Show quoted text 13 lines
> My understanding of a *full* cache synchronization would slow down not > only the current core and cache, but also all other caches? > > If so, would it help to enclose above instructions in e.g. > Synchronized begin > update the links... > end; > so that the compiler can make all memory references (at least reads) > occur read/write-through, inside such a code block? Even if that were possible, disabling caching does in no way solve any kind of data race. It would slow down programs without any gain whatsoever as far as thread safety is concerned.

I assume that you mean programmatical race conditions, resulting from unsynchronized sequences of code, which may run concurrently?

These conditions IMO should be considered only in the determination, whether some element of the standard libraries is inherently thread-unsafe, because it's not protected against concurrent use and can be subject to race conditions. When an element is *designed* for use by multiple threads, I'd protect it against concurrent use, so that race conditions cannot occur at all.

Show quoted text 5 lines
As Nikolai mentioned, you need a critical section (or a lock-free equivalent specific to an individual case, but that cannot be automatically generated -- and even the first published papers with manually constructed lock-free algorithms turned out to contain errors afterwards).

I'll present again my idea in another thread, WRT the combination of reference counting and object locking. I know that locking of *multiple* objects may lead to deadlock situations, that's not of concern here, and its solution (if ever) deserves no special compiler support.

Show quoted text 6 lines
> We need a documentation of the FPC specific means of cache > synchronization, with their guaranteed effects on every target[1]. Such documentation is not compiler-specific, but architecture-specific. The FPC documentation is not a tutorial on computer architecture, nor a tutorial on multi-threaded programming.

Such documentation is *both* compiler- and platform specific. Please note that I separated tutorials from the mere documentation, how the compiler-provided means for synchronization work.

Show quoted text 5 lines
FPC exports routines that for all existing kinds of memory barriers (ReadBarrier, ReadDependencyBarrier, ReadWriteBarrier and WriteBarrier), as well as for various synchronization primitives (criticalsection/mutex, event/conditional signal, ...). That is the job of the compiler/RTL.

Thanks again for the links :-)

Now I only miss a clarification in the documentation, whether "all" (memory reads...) refers to the instructions/statements in the surrounding code, or includes (the caches of) all currently active threads. It would be sufficient to clarify once, what the respective meaning of "memory barrier" is.

Language extensions are of course always possible, but that is unrelated to "documentation of the FPC specific means of cache synchronization, with their guaranteed effects on every target" (language constructs by definition would have the same effect everywhere).

Language definitions tend to mention "compiler specific" or "platform dependent" behaviour, whenever the it's unpredictable whether and how a feature can be implemented on various targets. Sometimes only footnotes are added, when such problems have been encountered only after the language was specified...

Tutorials and architecture documentation are a separate department.

FACK

Show quoted text 7 lines
> Furthermore we need concrete examples[2], how (to what extent) it's > required to use these special instructions/procedures, in examples > like above. Yes, many people could use tutorials about computer architecture, operating system principles and multi-threading. But again, those are completely unrelated to the development of FPC itself.

Again I refer to strictly FPC related tutorials, not to general documentation. When e.g. some general documentation/tutorial mentions "memory barriers", then every user will *also* have to know, how to use such means in *concrete* FPC code. Like one can learn about OOP in general, but needs additional information about the implementation (compiler docs) and usage (language docs) of OOP in FPC. Next came documentation of according libraries (FCL/LCL)...

No requirement that all these documentations must be supplied by the FPC developers, but reliable basic documentation can be supplied only by *official authorities* :-)

A good starter would probably be Module 4 of http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-823-computer-system-architecture-fall-2005/lecture-notes/

Fine, thanks :-)

DoDi

Reply by email