Қос салыстыру және ауыстыру: қазіргі заманғы бағдарламалаудағы қолданысы мен мәселелері

Кіріспе

Қос салыстыру және ауыстыру (DCAS немесе CAS2) – белгілі бір параллель бағдарламалау техникаларын қолдау үшін ұсынылған атомдық примитив. DCAS екі міндетті түрде бірімен-бірі жалғасқан емес жад орнын алып, жаңа мәндерді тек алдын ала берілген "күтілетін" мәндермен сәйкес келген жағдайда ғана жазады; осылайша, ол әлдеқайда танымал салыстыру және ауыстыру (CAS) операциясының кеңейтілген нұсқасы болып табылады. DCAS кейде x86 CMPXCHG16B сияқты нұсқаулармен іске асырылатын екі есе кең салыстыру және ауыстыру (DWCAS) операциясымен шатастырылады. Мұнда талқыланған DCAS әдетте көрсеткіш мөлшеріндегі екі жеке жад орнын басқарады, ал DWCAS екі жапсарлас көрсеткіш мөлшеріндегі жад орындарын басқарады. Докторлық диссертациясында Майкл Гринвальд DCAS-ты заманауи аппараттық құралға қосуды ұсынды, оның арқасында оңай қолданылатын, бірақ тиімді бағдарламалық транзакциялық жадты (STM) құруға болатынын көрсетті. Гринвальд DCAS-тың CAS-қа қарағандағы артықшылығы – DCAS арқылы жоғары ретті (көп элементті) CASn операциясын O(n) уақытында іске асыруға болатыны, ал біртұтас CAS үшін O(n log p) уақыты қажет екенін айтады, мұнда p – бәсекелес процестердің саны. DCAS-тың бір артықшылығы – атомдық екі басты тізімдерді (яғни, екі бағытты тізімдерді) салыстырмалы түрде оңай іске асыру мүмкіндігі. Дегенмен, жақында ғана CAS-ты қолдана отырып, ұқсас қасиеттері бар STM-ді іске асыруға болатыны көрсетілді. Бірақ, жалпы алғанда, DCAS – түйіншесі жоқ шешім емес: оны пайдалану арқылы құлыптамау және күтусіз алгоритмдерді іске асыру, әдетте, CAS сияқты күрделі және қатеге ұшырауға бейім. Motorola бір кезде DCAS-ты 68k сериялы процессорлар үшін жасалған нұсқаулар жиынтығына енгізген; алайда, DCAS-тың басқа примитивтерге қарағанда баяу жұмыс істеуі (кэшпен жұмыс істеу мәселелеріне байланысты) практикалық жағдайларда одан бас тартуға әкелді. Қазіргі кезде DCAS ешбір кең таралған процессорда тікелей қолдау көрсетілмейді. DCAS-ты екіден астам адреске кеңейту кейде MCAS (көп сөзді CAS) деп аталады; MCAS-ты LL/SC операциясын біріктіру арқылы іске асыруға болады, бірақ мұндай примитив аппараттық құралда тікелей қол жетімді емес. 2013 жылы Тревор Браун, Фейт Эллен және Эрик Руперт бағдарламалық жасақтамада LL/SC кеңейтуін (олар LLX/SCX деп атады) іске асырды, ол MCAS-қа қарағанда шектеулі болғанымен, автоматтандырылған кодты жасау арқылы ең жақсы өнімділік көрсеткен екілік іздеу ағашын (нақтырақ айтқанда, хроматикалық ағаш) іске асыруға мүмкіндік берді, JDK CAS негізіндегі тізімді сәл басып өтті. Жалпы, DCAS-ты экспрессивті аппараттық транзакциялық жад қамтамасыз ете алады. IBM POWER8 және Intel TSX транзакциялық жадты іске асыруды ұсынады. Sun компаниясының жобасынан бас тартылған Rock процессоры да оны қолдауға тиіс болған.

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 such, it is an extension of the much more popular compare and swap (CAS) operation. DCAS is sometimes confused with the double width compare and swap (DWCAS) implemented by instructions such as x86 CMPXCHG16B. DCAS, as discussed here, handles two discontiguous memory locations, typically of pointer size, whereas DWCAS handles two adjacent pointer sized memory locations. In his doctoral thesis, Michael Greenwald recommended adding DCAS to modern hardware, showing it could be used to create easy to apply yet efficient software transactional memory (STM). Greenwald points out that an advantage of DCAS vs CAS is that higher order (multiple item) CASn can be implemented in O(n) with DCAS, but requires O(n log p) time with unary CAS, where p is the number of contending processes. One of the advantages of DCAS is the ability to implement atomic deques (i. e. doubly linked lists) with relative ease. More recently, however, it has been shown that an STM can be implemented with comparable properties using only CAS. In general however, DCAS is not a silver bullet: implementing lock free and wait free algorithms using it is typically just as complex and error prone as for CAS. Motorola at one point included DCAS in the instruction set for its 68k series; however, the slowness of DCAS relative to other primitives (apparently due to cache handling issues) led to its avoidance in practical contexts. , DCAS is not natively supported by any widespread CPUs in production. The generalization of DCAS to more than two addresses is sometimes called MCAS (multi word CAS); MCAS can be implemented by a nestable LL/SC, but such a primitive is not directly available in hardware. In 2013, Trevor Brown, Faith Ellen, and Eric Ruppert have implemented in software a multi address LL/SC extension (which they call LLX/SCX) that while being more restrictive than MCAS enabled them, via some automated code generation, to implement one of the best performing concurrent binary search tree (actually a chromatic tree), slightly beating the JDK CAS based skip list implementation. In general, DCAS can be provided by a more expressive hardware transactional memory. IBM POWER8 and Intel Intel TSX provide working implementations of transactional memory. Sun's cancelled Rock processor would have supported it as well.