Double Compare And Swap

Double Compare And Swap

Double Compare And Swap (DCAS or CAS2) is an atomic primitive proposed to support certain concurrent programming techniques. DCAS takes two memory locations and writes new values into them only if they match pre-supplied "expected" values; as such, it is an extension of compare-and-swap (CAS).

In his doctoral thesis, Greenwald recommended adding DCAS to modern hardware, showing it could be used to create easy-to-apply yet efficient software transactional memory (STM). More recently, however, it has been shown that an STM can be implemented with comparable properties using only CAS.

The major advantage of DCAS is the ability to implement atomic deques (i.e. doubly-linked lists) [ [http://www.google.com/search?q=cache:7LkV4ABc5b0J:research.sun.com/scalable/Papers/TCS02.pdf ] ] .

DCAS is no silver bullet: implementing lock-free and wait-free algorithms using it is typically just as complex and error-prone as for CAS. As such, it seems unlikely that DCAS will ever be supported natively on any modern platform. Indeed, as of 2006, it's not supported by any widespread CPUs. For a while Motorola included it in the instruction set for its 68k series [ [http://68k.hax.com/CAS2 CAS2] ] ; however its relative slowness [ [http://www-dsg.stanford.edu/papers/non-blocking-osdi/node15.html Experimental Implementation] ] led to programmer apathy. It is no longer included in the instruction set. CAS remains popular.

Sun's new Rock processor (shipping second half 2009) which supports hardware scouts and best effort hardware transactional memory also supports DCAS, which they claim provides algorithmic power [(Mark Moir) [http://blogs.sun.com/HPC/entry/video_transactional_memory_on_rock Sun HPC Watercooler] ] .

References

* M. Greenwald. "Non-Blocking Synchronization and System Design". Stanford University Technical Report STAN-CS-TR-99-1624 [http://elib.stanford.edu/TR/STAN:CS-TR-99-1624] .Dead link|date=September 2008
* "DCAS is not a silver bullet for nonblocking algorithm design". 16th annual ACM symposium on Parallelism in algorithms and architectures, 2004, pp. 216–224 [http://portal.acm.org/citation.cfm?id=1007945] .

External links

* [http://www.osdata.com/topic/language/asm/coproc.htm Multiprocessor and Coprocessor Instructions in Assembly Language]
* [http://freepatentsonline.com/4584640.html US Patent 4584640 "Method and apparatus for a compare and swap instruction"]


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Double compare-and-swap — (DCAS or CAS2) is an atomic primitive proposed to support certain concurrent programming techniques. DCAS takes two not necessarily contiguous memory locations and writes new values into them only if they match pre supplied expected values; as… …   Wikipedia

  • Compare-and-swap — In computer science, the compare and swap (CAS) CPU instruction is a special instruction that atomically compares the contents of a memory location to a given value and, only if they are the same, modifies the contents of that memory location to… …   Wikipedia

  • Comparison of cricket and baseball — Cricket and baseball are the best known members of a family of related bat and ball games. While many of their rules, terminology, and strategies are similar, there are many differences some subtle, some major between the two games. Other present …   Wikipedia

  • Business and Industry Review — ▪ 1999 Introduction Overview        Annual Average Rates of Growth of Manufacturing Output, 1980 97, Table Pattern of Output, 1994 97, Table Index Numbers of Production, Employment, and Productivity in Manufacturing Industries, Table (For Annual… …   Universalium

  • Health and Disease — ▪ 2009 Introduction Food and Drug Safety.       In 2008 the contamination of infant formula and related dairy products with melamine in China led to widespread health problems in children, including urinary problems and possible renal tube… …   Universalium

  • School of Oriental and African Studies — The School of Oriental and African Studies Arms of SOAS Motto Knowledge is Power Established 1916 Type Public …   Wikipedia

  • DCAS — may be: Deputy Chief of the Air Staff Derive computer algebra system Double compare and swap Downloadable Conditional Access System Dynamic Computer Algebra System Devon and Cornwall Archery Society Department of Citywide Administrative Services …   Wikipedia

  • CAS2 (disambiguation) — CAS2 is an airport code for Moose Lake (Lodge) Airport.CAS2 may refer to:*Double Compare And Swap, in computers, machine level instruction *CAS Latency, Column Access Strobe , a timing associated with some kinds of computer memory …   Wikipedia

  • ABA problem — In multithreaded computing, the ABA problem occurs during synchronization, when a location is read twice, has the same value for both reads, and value is the same is used to indicate nothing has changed . However, another thread can execute… …   Wikipedia

  • Проблема ABA — В многозадачных вычислениях, проблема ABA возникает при синхронизации, когда ячейка памяти читается дважды, оба раза прочитано одинаковое значение, и признак «значение одинаковое» трактуется как «ничего не менялось». Однако, другой поток может… …   Википедия

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”