tag:blogger.com,1999:blog-8383004232931899216.post2376262857356730909..comments2023-11-01T11:47:57.046-04:00Comments on Designing ParaSail, a new programming language: Work stealing and mostly lock-free accessTucker Tafthttp://www.blogger.com/profile/08866496974237052847noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-8383004232931899216.post-39857410334557627282012-09-27T11:11:50.649-04:002012-09-27T11:11:50.649-04:00Right you are. C1x and C++11 do have the notion o...Right you are. C1x and C++11 do have the notion of atomic variables which ensure sequential consistency, but alas, these are probably not yet implemented in most C/C++ compilers. Luckily, the ParaSail run-time is currently implemented in Ada 95, where the rules specifically allow synchronization using atomic variables. Again, that doesn't prove that all implementations ensure that, but they have had more time to do so. ;-)<br /><br />The other approach is to just rely on a very efficient implementation of a mutex (e.g. a Linux futex), which special cases the no-contention situation. Probably the only way to know which has the best performance is to do experiments, which will be the next job.Tucker Tafthttps://www.blogger.com/profile/08866496974237052847noreply@blogger.comtag:blogger.com,1999:blog-8383004232931899216.post-85489360515053569422012-09-26T05:43:59.524-04:002012-09-26T05:43:59.524-04:00Declaring an object volatile definitely does not i...Declaring an object volatile definitely does not introduce a memory barrier in C (let's say C99) or C++.<br /><br />In these languages atomics have to be implemented manually (usually through inlined asm) and "typical" atomic operations implementations, also do not incur barriers: they are expensive and people using atomics are supposed to understand what they are doing! E.g., see Linux kernel Documentation/atomic_ops.txt:<br /><br />"*** WARNING: atomic_read() and atomic_set() DO NOT IMPLY BARRIERS! ***"<br />nikitahttps://www.blogger.com/profile/09403336533089968821noreply@blogger.comtag:blogger.com,1999:blog-8383004232931899216.post-79445504870179600802012-09-25T11:43:27.671-04:002012-09-25T11:43:27.671-04:00I believe memory barriers should be provided autom...I believe memory barriers should be provided automatically as needed if you declare the object as atomic/volatile in languages such as C, C++, Java, or Ada.<br /><br />Mutex implementations need not use queuing if you use the priority ceiling approach on a monoprocessor, and busy waiting on a multiprocessor. This is the implementation I am presuming. I also should have made it clear that the nonowner-waiting queue is not itself a concurrent data structure -- it relies on the mutex to protect against simultaneous access. (In Ada, it would be an entry queue associated with the protected object used to represent the mutex.)Tucker Tafthttps://www.blogger.com/profile/08866496974237052847noreply@blogger.comtag:blogger.com,1999:blog-8383004232931899216.post-52439089504079578942012-09-25T04:12:18.331-04:002012-09-25T04:12:18.331-04:00I would like to add a couple of observations:
...I would like to add a couple of observations:<br /><br /> * you definitely need memory barriers between flag manipulations (atomic operations are not necessarily memory barriers);<br /><br /> * typical mutex implementation already does something similar to your flag-set-check protocol and it also has a queue of waiters inside of the mutex, so it might be easier to just to mutex_lock();... mutex_unlock(); without much ado.nikitahttps://www.blogger.com/profile/09403336533089968821noreply@blogger.com