{"id":195948,"date":"2013-10-08T10:02:07","date_gmt":"2013-10-08T06:02:07","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=195948"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=195948","title":{"rendered":"Lock-free \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445. \u041e\u0441\u043d\u043e\u0432\u044b: \u0410\u0442\u043e\u043c\u0430\u0440\u043d\u043e\u0441\u0442\u044c \u0438 \u0430\u0442\u043e\u043c\u0430\u0440\u043d\u044b\u0435 \u043f\u0440\u0438\u043c\u0438\u0442\u0438\u0432\u044b<\/span>"},"content":{"rendered":"
\t
\u041f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u0435 lock-free \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440 \u0434\u0430\u043d\u043d\u044b\u0445 \u0437\u0438\u0436\u0434\u0435\u0442\u0441\u044f \u043d\u0430 \u0434\u0432\u0443\u0445 \u043a\u0438\u0442\u0430\u0445 \u2013 \u0430\u0442\u043e\u043c\u0430\u0440\u043d\u044b\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f\u0445 \u0438 \u0441\u043f\u043e\u0441\u043e\u0431\u0430\u0445 \u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0435\u043d\u0438\u044f \u0434\u043e\u0441\u0442\u0443\u043f\u0430 \u043a \u043f\u0430\u043c\u044f\u0442\u0438. \u0412 \u044d\u0442\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0435 \u0440\u0435\u0447\u044c \u043f\u043e\u0439\u0434\u0435\u0442 \u043e\u0431 \u0430\u0442\u043e\u043c\u0430\u0440\u043d\u043e\u0441\u0442\u0438 \u0438 \u0430\u0442\u043e\u043c\u0430\u0440\u043d\u044b\u0445 \u043f\u0440\u0438\u043c\u0438\u0442\u0438\u0432\u0430\u0445.<\/p>\n

\u0410\u043d\u043e\u043d\u0441<\/b>. \u0421\u043f\u0430\u0441\u0438\u0431\u043e \u0437\u0430 \u0442\u0435\u043f\u043b\u044b\u0439 \u043f\u0440\u0438\u0435\u043c \u041d\u0430\u0447\u0430\u043b<\/a>! \u0412\u0438\u0436\u0443, \u0447\u0442\u043e \u0442\u0435\u043c\u0430 lock-free \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u0430 \u0445\u0430\u0431\u0440\u0430\u0441\u043e\u043e\u0431\u0449\u0435\u0441\u0442\u0432\u0443, \u044d\u0442\u043e \u043c\u0435\u043d\u044f \u0440\u0430\u0434\u0443\u0435\u0442. \u042f \u043f\u043b\u0430\u043d\u0438\u0440\u043e\u0432\u0430\u043b \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u0442\u044c \u0446\u0438\u043a\u043b \u043f\u043e \u0430\u043a\u0430\u0434\u0435\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u043c\u0443 \u043f\u0440\u0438\u043d\u0446\u0438\u043f\u0443, \u043f\u043b\u0430\u0432\u043d\u043e \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u044f \u043e\u0442 \u043e\u0441\u043d\u043e\u0432 \u043a \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430\u043c, \u043f\u043e\u043f\u0443\u0442\u043d\u043e \u0438\u043b\u043b\u044e\u0441\u0442\u0440\u0438\u0440\u0443\u044f \u0442\u0435\u043a\u0441\u0442 \u043a\u043e\u0434\u043e\u043c \u0438\u0437 libcds. \u041d\u043e \u0447\u0430\u0441\u0442\u044c \u0447\u0438\u0442\u0430\u0442\u0435\u043b\u0435\u0439 \u0442\u0440\u0435\u0431\u0443\u0435\u0442 \u0437\u0440\u0435\u043b\u0438\u0449<\/s> \u043d\u0435 \u043c\u0435\u0448\u043a\u0430\u044f \u043f\u043e\u043a\u0430\u0437\u0430\u0442\u044c, \u043a\u0430\u043a \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u043e\u0439, \u043e\u0441\u043e\u0431\u043e \u043d\u0435 \u0440\u0430\u0441\u0441\u0443\u0441\u043e\u043b\u0438\u0432\u0430\u044f. \u042f \u0441\u043e\u0433\u043b\u0430\u0441\u0435\u043d, \u0432 \u044d\u0442\u043e\u043c \u0435\u0441\u0442\u044c \u0441\u0432\u043e\u0439 \u0440\u0435\u0437\u043e\u043d. \u0412 \u043a\u043e\u043d\u0435\u0447\u043d\u043e\u043c \u0441\u0447\u0435\u0442\u0435, \u0438 \u043c\u043d\u0435 \u043d\u0435 \u0442\u0430\u043a \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e, \u0447\u0442\u043e \u0442\u0430\u043c \u0432\u043d\u0443\u0442\u0440\u0438 boost<\/a>, \u2014 \u043e\u043f\u0438\u0448\u0438\u0442\u0435, \u043a\u0430\u043a \u0435\u0433\u043e \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u0442\u044c! \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u0441\u0432\u043e\u0439 \u044d\u043f\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u0446\u0438\u043a\u043b \u044f \u0440\u0430\u0437\u0434\u0435\u043b\u044e \u043d\u0430 \u0442\u0440\u0438 \u0447\u0430\u0441\u0442\u0438: \u041e\u0441\u043d\u043e\u0432\u044b<\/i>, \u0412\u043d\u0443\u0442\u0440\u0438<\/i> \u0438 \u0418\u0437\u0432\u043d\u0435<\/i>. \u041a\u0430\u0436\u0434\u0430\u044f \u0441\u0442\u0430\u0442\u044c\u044f \u044d\u043f\u043e\u043f\u0435\u0438 \u0431\u0443\u0434\u0435\u0442 \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0441\u044f \u043a \u043e\u0434\u043d\u043e\u0439 \u0438\u0437 \u0447\u0430\u0441\u0442\u0435\u0439. \u0412 \u041e\u0441\u043d\u043e\u0432\u0430\u0445<\/i> \u0431\u0443\u0434\u0435\u0442 \u0440\u0430\u0441\u0441\u043a\u0430\u0437\u044b\u0432\u0430\u0442\u044c\u0441\u044f \u043e \u043d\u0438\u0437\u043a\u043e\u0443\u0440\u043e\u0432\u043d\u0435\u0432\u044b\u0445 \u0432\u0435\u0449\u0430\u0445, \u0432\u043f\u043b\u043e\u0442\u044c \u0434\u043e \u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f \u0441\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u043e\u0440\u043e\u0432; \u044d\u0442\u043e \u0447\u0430\u0441\u0442\u044c \u0434\u043b\u044f \u043f\u043e\u0447\u0435\u043c\u0443\u0447\u0435\u043a \u0432\u0440\u043e\u0434\u0435 \u043c\u0435\u043d\u044f. \u0412\u043d\u0443\u0442\u0440\u0438<\/i> \u0431\u0443\u0434\u0435\u0442 \u043e\u0441\u0432\u0435\u0449\u0430\u0442\u044c \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u044b\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0438 \u043f\u043e\u0434\u0445\u043e\u0434\u044b \u0432 \u043c\u0438\u0440\u0435 lock-free, \u2014 \u044d\u0442\u043e \u0441\u043a\u043e\u0440\u0435\u0435 \u0442\u0435\u043e\u0440\u0438\u044f \u043e \u0442\u043e\u043c, \u043a\u0430\u043a \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c lock-free \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0434\u0430\u043d\u043d\u044b\u0445, libcds \u0431\u0443\u0434\u0435\u0442 \u043d\u0435\u0438\u0441\u0447\u0435\u0440\u043f\u0430\u0435\u043c\u044b\u043c \u0438\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u043e\u043c C++ \u043a\u043e\u0434\u0430. \u0412 \u0418\u0437\u0432\u043d\u0435<\/i> \u0431\u0443\u0434\u0443\u0442 \u0441\u0442\u0430\u0442\u044c\u0438 \u043e \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0435 \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u044f libcds, \u2014 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u043d\u044b\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u044f, \u0441\u043e\u0432\u0435\u0442\u044b \u0438 FAQ. \u0418\u0437\u0432\u043d\u0435<\/i> \u0431\u0443\u0434\u0435\u0442 \u043f\u0438\u0442\u0430\u0442\u044c\u0441\u044f \u0432\u0430\u0448\u0438\u043c\u0438 \u0432\u043e\u043f\u0440\u043e\u0441\u0430\u043c\u0438\/\u0437\u0430\u043c\u0435\u0447\u0430\u043d\u0438\u044f\u043c\u0438\/\u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u0438\u044f\u043c\u0438, \u0434\u043e\u0440\u043e\u0433\u0438\u0435 \u0445\u0430\u0431\u0440\u0430\u0436\u0438\u0442\u0435\u043b\u0438.<\/p>\n

\u0410 \u043f\u043e\u043a\u0430 \u044f \u0441\u0443\u0434\u043e\u0440\u043e\u0436\u043d\u043e \u0433\u043e\u0442\u043e\u0432\u043b\u044e \u043d\u0430\u0447\u0430\u043b\u043e \u0418\u0437\u0432\u043d\u0435<\/i>, \u2014 \u043f\u0435\u0440\u0432\u0430\u044f \u0447\u0430\u0441\u0442\u044c \u041e\u0441\u043d\u043e\u0432<\/i>. \u0421\u0442\u0430\u0442\u044c\u044f \u0432\u043e \u043c\u043d\u043e\u0433\u043e\u043c \u043d\u0435 \u043e C++ (\u0445\u043e\u0442\u044f \u0438 \u043e \u043d\u0435\u043c \u0442\u043e\u0436\u0435) \u0438 \u0434\u0430\u0436\u0435 \u043d\u0435 \u043e lock-free (\u0445\u043e\u0442\u044f \u0431\u0435\u0437 atomic lock-free \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u043d\u0435\u0440\u0430\u0431\u043e\u0442\u043e\u0441\u043f\u043e\u0441\u043e\u0431\u043d\u044b), \u0430 \u043e \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u0430\u0442\u043e\u043c\u0430\u0440\u043d\u044b\u0445 \u043f\u0440\u0438\u043c\u0438\u0442\u0438\u0432\u043e\u0432 \u0432 \u0441\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u043e\u0440\u0430\u0445 \u0438 \u043e \u0431\u0430\u0437\u043e\u0432\u044b\u0445 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0430\u0445, \u0432\u043e\u0437\u043d\u0438\u043a\u0430\u044e\u0449\u0438\u0445 \u043f\u0440\u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0438 \u0442\u0430\u043a\u0438\u0445 \u043f\u0440\u0438\u043c\u0438\u0442\u0438\u0432\u043e\u0432.
\u0410\u0442\u043e\u043c\u0430\u0440\u043d\u043e\u0441\u0442\u044c \u2014 \u044d\u0442\u043e \u043f\u0435\u0440\u0432\u044b\u0439 \u043a\u0440\u0443\u0433 \u0430\u0434\u0430<\/s> \u043d\u0438\u0437\u043a\u0438\u0439 \u0443\u0440\u043e\u0432\u0435\u043d\u044c \u0438\u0437 \u0434\u0432\u0443\u0445.
<\/a>
\u0410\u0442\u043e\u043c\u0430\u0440\u043d\u044b\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0434\u0435\u043b\u044f\u0442\u0441\u044f \u043d\u0430 \u043f\u0440\u043e\u0441\u0442\u044b\u0435 \u2014 \u0447\u0442\u0435\u043d\u0438\u0435 \u0438 \u0437\u0430\u043f\u0438\u0441\u044c \u2014 \u0438 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0430\u0442\u043e\u043c\u0430\u0440\u043d\u043e\u0433\u043e \u0438\u0437\u043c\u0435\u043d\u0435\u043d\u0438\u044f (read-modify-write, RMW). \u0410\u0442\u043e\u043c\u0430\u0440\u043d\u0443\u044e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044e \u043c\u043e\u0436\u043d\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c \u043a\u0430\u043a \u043d\u0435\u0434\u0435\u043b\u0438\u043c\u0443\u044e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044e: \u043e\u043d\u0430 \u043b\u0438\u0431\u043e \u0443\u0436\u0435 \u043f\u0440\u043e\u0438\u0437\u043e\u0448\u043b\u0430, \u043b\u0438\u0431\u043e \u0435\u0449\u0451 \u043d\u0435\u0442; \u043c\u044b \u043d\u0435 \u043c\u043e\u0436\u0435\u043c \u0443\u0432\u0438\u0434\u0435\u0442\u044c \u043d\u0438\u043a\u0430\u043a\u0438\u0445 \u043f\u0440\u043e\u043c\u0435\u0436\u0443\u0442\u043e\u0447\u043d\u044b\u0445 \u0441\u0442\u0430\u0434\u0438\u0439 \u0435\u0451 \u0432\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f, \u043d\u0438\u043a\u0430\u043a\u0438\u0445 \u0447\u0430\u0441\u0442\u0438\u0447\u043d\u044b\u0445 \u044d\u0444\u0444\u0435\u043a\u0442\u043e\u0432. \u0412 \u044d\u0442\u043e\u043c \u0441\u043c\u044b\u0441\u043b\u0435 \u0434\u0430\u0436\u0435 \u043f\u0440\u043e\u0441\u0442\u044b\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 \u0447\u0442\u0435\u043d\u0438\u044f\/\u0437\u0430\u043f\u0438\u0441\u0438, \u0432 \u043f\u0440\u0438\u043d\u0446\u0438\u043f\u0435, \u043c\u043e\u0433\u0443\u0442 \u0431\u044b\u0442\u044c \u043d\u0435 \u0430\u0442\u043e\u043c\u0430\u0440\u043d\u044b\u043c\u0438; \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0447\u0442\u0435\u043d\u0438\u0435 \u043d\u0435\u0432\u044b\u0440\u0430\u0432\u043d\u0435\u043d\u043d\u044b\u0445 \u0434\u0430\u043d\u043d\u044b\u0445 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043d\u0435\u0430\u0442\u043e\u043c\u0430\u0440\u043d\u044b\u043c: \u0432 \u0430\u0440\u0445\u0438\u0442\u0435\u043a\u0442\u0443\u0440\u0435 x86 \u0442\u0430\u043a\u043e\u0435 \u0447\u0442\u0435\u043d\u0438\u0435 \u043f\u0440\u0438\u0432\u0435\u0434\u0435\u0442 \u043a \u0432\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u0435\u043c\u0443 \u0438\u0441\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u044e, \u0437\u0430\u0441\u0442\u0430\u0432\u043b\u044f\u044e\u0449\u0435\u043c\u0443 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u043e\u0440 \u0447\u0438\u0442\u0430\u0442\u044c \u0434\u0430\u043d\u043d\u044b\u0435 \u0447\u0430\u0441\u0442\u044f\u043c\u0438, \u0432 \u0434\u0440\u0443\u0433\u0438\u0445 \u0430\u0440\u0445\u0438\u0442\u0435\u043a\u0442\u0443\u0440\u0430\u0445 (Sparc, Intel Itanium) \u2013 \u043a \u0444\u0430\u0442\u0430\u043b\u044c\u043d\u043e\u0439 \u043e\u0448\u0438\u0431\u043a\u0435 (segmentation fault), \u043a\u043e\u0442\u043e\u0440\u0443\u044e, \u0432 \u043f\u0440\u0438\u043d\u0446\u0438\u043f\u0435, \u043c\u043e\u0436\u043d\u043e \u043f\u0435\u0440\u0435\u0445\u0432\u0430\u0442\u0438\u0442\u044c \u0438 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c, \u043d\u043e \u043e\u0431 \u0430\u0442\u043e\u043c\u0430\u0440\u043d\u043e\u0441\u0442\u0438 \u0440\u0435\u0447\u0438 \u0437\u0434\u0435\u0441\u044c \u0431\u044b\u0442\u044c \u0443\u0436\u0435 \u043d\u0435 \u043c\u043e\u0436\u0435\u0442. \u0412 \u0441\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u043e\u0440\u0430\u0445 \u0433\u0430\u0440\u0430\u043d\u0442\u0438\u0440\u0443\u0435\u0442\u0441\u044f \u0430\u0442\u043e\u043c\u0430\u0440\u043d\u043e\u0441\u0442\u044c \u0447\u0442\u0435\u043d\u0438\u044f\/\u0437\u0430\u043f\u0438\u0441\u0438 \u0442\u043e\u043b\u044c\u043a\u043e \u0432\u044b\u0440\u0430\u0432\u043d\u0435\u043d\u043d\u044b\u0445<\/b> \u043f\u0440\u043e\u0441\u0442\u044b\u0445 (integral) \u0442\u0438\u043f\u043e\u0432 \u2013 \u0446\u0435\u043b\u044b\u0445 \u0447\u0438\u0441\u0435\u043b \u0438 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u0435\u0439. \u0421\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0439 \u043a\u043e\u043c\u043f\u0438\u043b\u044f\u0442\u043e\u0440 \u0433\u0430\u0440\u0430\u043d\u0442\u0438\u0440\u0443\u0435\u0442 \u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u043e\u0435 \u0432\u044b\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u043d\u0438\u0435 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 \u0431\u0430\u0437\u043e\u0432\u044b\u0445 \u0442\u0438\u043f\u043e\u0432, \u0445\u043e\u0442\u044f \u043d\u0430\u043f\u0438\u0441\u0430\u0442\u044c \u043f\u0440\u0438\u043c\u0435\u0440 \u043d\u0435\u0432\u044b\u0440\u0430\u0432\u043d\u0435\u043d\u043d\u043e\u0433\u043e \u043e\u0431\u0440\u0430\u0449\u0435\u043d\u0438\u044f, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043a \u0446\u0435\u043b\u043e\u043c\u0443, \u043d\u0435 \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 \u0442\u0440\u0443\u0434\u0430. \u0415\u0441\u043b\u0438 \u0436\u0435 \u0432\u044b \u0445\u043e\u0442\u0438\u0442\u0435 \u0430\u0442\u043e\u043c\u0430\u0440\u043d\u043e \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u0441\u043e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u043e\u0439 (\u043f\u043e \u0440\u0430\u0437\u043c\u0435\u0440\u0443 \u0432\u043b\u0435\u0437\u0430\u044e\u0449\u0435\u0439 \u0432 4 \u2013 8 \u0431\u0430\u0439\u0442), \u0442\u043e \u0441\u043b\u0435\u0434\u0443\u0435\u0442 \u0441\u0430\u043c\u0438\u043c \u043f\u043e\u0437\u0430\u0431\u043e\u0442\u0438\u0442\u044c\u0441\u044f \u043e \u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u043e\u043c \u0432\u044b\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u043d\u0438\u0438 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0434\u0438\u0440\u0435\u043a\u0442\u0438\u0432 (\u0430\u0442\u0440\u0438\u0431\u0443\u0442\u043e\u0432) \u043a\u043e\u043c\u043f\u0438\u043b\u044f\u0442\u043e\u0440\u0430 (\u043a\u0430\u0436\u0434\u044b\u0439 \u043a\u043e\u043c\u043f\u0438\u043b\u044f\u0442\u043e\u0440 \u043f\u043e\u0434\u0434\u0435\u0440\u0436\u0438\u0432\u0430\u0435\u0442 \u0441\u0432\u043e\u0439 \u0443\u043d\u0438\u043a\u0430\u043b\u044c\u043d\u044b\u0439 \u0441\u043f\u043e\u0441\u043e\u0431 \u0443\u043a\u0430\u0437\u0430\u043d\u0438\u044f \u0432\u044b\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u043d\u0438\u044f \u0434\u0430\u043d\u043d\u044b\u0445\/\u0442\u0438\u043f\u043e\u0432). \u041a\u0441\u0442\u0430\u0442\u0438, \u0431\u0438\u0431\u043b\u0438\u043e\u0442\u0435\u043a\u0430 libcds<\/a> \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u043d\u0430\u0431\u043e\u0440 \u0432\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u0442\u0438\u043f\u043e\u0432 \u0438 \u043c\u0430\u043a\u0440\u043e\u0441\u043e\u0432, \u0441\u043a\u0440\u044b\u0432\u0430\u044e\u0449\u0438\u0445 \u043a\u043e\u043c\u043f\u0438\u043b\u044f\u0442\u043e\u0440\u043d\u043e-\u0437\u0430\u0432\u0438\u0441\u0438\u043c\u0443\u044e \u0447\u0430\u0441\u0442\u044c \u043f\u0440\u0438 \u043e\u0431\u044a\u044f\u0432\u043b\u0435\u043d\u0438\u0438 \u0432\u044b\u0440\u0430\u0432\u043d\u0435\u043d\u043d\u044b\u0445 \u0434\u0430\u043d\u043d\u044b\u0445.<\/p>\n

Compare-and-swap<\/h2>\n

\u041f\u0440\u0438\u0434\u0443\u043c\u0430\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c lock-free \u043a\u043e\u043d\u0442\u0435\u0439\u043d\u0435\u0440\u0430, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0449\u0435\u0433\u043e \u0442\u043e\u043b\u044c\u043a\u043e \u0447\u0442\u0435\u043d\u0438\u0435\/\u0437\u0430\u043f\u0438\u0441\u044c, \u0434\u043e\u0432\u043e\u043b\u044c\u043d\u043e \u0441\u043b\u043e\u0436\u043d\u043e, \u0435\u0441\u043b\u0438 \u0432\u043e\u043e\u0431\u0449\u0435 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e (\u043c\u043d\u0435 \u0442\u0430\u043a\u0438\u0435 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445 \u0434\u043b\u044f \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u043b\u044c\u043d\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u043f\u043e\u0442\u043e\u043a\u043e\u0432 \u043d\u0435 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u044b). \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u0447\u0438\u043a\u0438 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u043e\u0440\u043d\u044b\u0445 \u0430\u0440\u0445\u0438\u0442\u0435\u043a\u0442\u0443\u0440 \u0432\u043d\u0435\u0434\u0440\u0438\u043b\u0438 RMW-\u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438, \u0441\u043f\u043e\u0441\u043e\u0431\u043d\u044b\u0435 \u0430\u0442\u043e\u043c\u0430\u0440\u043d\u043e \u0432\u044b\u043f\u043e\u043b\u043d\u0438\u0442\u044c \u0447\u0442\u0435\u043d\u0438\u0435 \u0432\u044b\u0440\u0430\u0432\u043d\u0435\u043d\u043d\u043e\u0439 \u044f\u0447\u0435\u0439\u043a\u0438 \u043f\u0430\u043c\u044f\u0442\u0438 \u0438 \u0437\u0430\u043f\u0438\u0441\u044c \u0432 \u043d\u0435\u0451: compare-and-swap (CAS), fetch-and-add (FAA), test-and-set (TAS) \u0438 \u043f\u0440. \u0412 \u0430\u043a\u0430\u0434\u0435\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u0441\u0440\u0435\u0434\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f compare-and-swap (CAS) \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u043a\u0430\u043a \u0431\u0430\u0437\u043e\u0432\u0430\u044f; \u0435\u0451 \u043f\u0441\u0435\u0432\u0434\u043e\u043a\u043e\u0434 \u043f\u0440\u043e\u0441\u0442: <\/p>\n

bool CAS( int * pAddr, int nExpected, int nNew ) atomically {     if ( *pAddr == nExpected ) {          *pAddr = nNew ;          return true ;     }     else         return false ;  } <\/code><\/pre>\n
  \u0421\u043b\u043e\u0432\u0430\u043c\u0438: \u0435\u0441\u043b\u0438 \u0442\u0435\u043a\u0443\u0449\u0435\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u043e\u0439 \u043f\u043e \u0430\u0434\u0440\u0435\u0441\u0443 pAddr<\/code> \u0440\u0430\u0432\u043d\u043e \u043e\u0436\u0438\u0434\u0430\u0435\u043c\u043e\u043c\u0443 nExpected<\/code>, \u0442\u043e \u043f\u0440\u0438\u0441\u0432\u043e\u0438\u0442\u044c \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u043e\u0439 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 nNew<\/code> \u0438 \u0432\u043e\u0437\u0432\u0440\u0430\u0442\u0438\u0442\u044c true<\/code>, \u0438\u043d\u0430\u0447\u0435 \u0432\u043e\u0437\u0432\u0440\u0430\u0442\u0438\u0442\u044c false<\/code>, \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u043e\u0439 \u043d\u0435 \u0438\u0437\u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f. \u0412\u0441\u0451 \u044d\u0442\u043e \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f \u0430\u0442\u043e\u043c\u0430\u0440\u043d\u043e, \u0442\u043e \u0435\u0441\u0442\u044c \u043d\u0435\u0434\u0435\u043b\u0438\u043c\u043e \u0438 \u0431\u0435\u0437 \u0432\u0438\u0434\u0438\u043c\u044b\u0445 \u0447\u0430\u0441\u0442\u0438\u0447\u043d\u044b\u0445 \u044d\u0444\u0444\u0435\u043a\u0442\u043e\u0432. \u0427\u0435\u0440\u0435\u0437 CAS \u043c\u043e\u0436\u043d\u043e \u0432\u044b\u0440\u0430\u0437\u0438\u0442\u044c \u0432\u0441\u0435 \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u0435 RMW-\u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, fetch-and-add \u0431\u0443\u0434\u0435\u0442 \u0432\u044b\u0433\u043b\u044f\u0434\u0435\u0442\u044c \u0442\u0430\u043a:<\/p>\n
int FAA( int * pAddr, int nIncr ) {      int ncur ;      do {           ncur = *pAddr ;      } while ( !CAS( pAddr, ncur, ncur + nIncr ) ;      return ncur ; } <\/code><\/pre>\n
  \u201c\u0410\u043a\u0430\u0434\u0435\u043c\u0438\u0447\u0435\u0441\u043a\u0438\u0439\u201d \u0432\u0430\u0440\u0438\u0430\u043d\u0442 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 CAS \u043d\u0435 \u0432\u0441\u0435\u0433\u0434\u0430 \u0443\u0434\u043e\u0431\u0435\u043d \u043d\u0430 \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0435, \u0432\u0435\u0434\u044c \u0437\u0430\u0447\u0430\u0441\u0442\u0443\u044e \u043f\u0440\u0438 \u043d\u0435\u0443\u0434\u0430\u0447\u0435 CAS \u043d\u0430\u043c \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e, \u0447\u0442\u043e \u0436\u0435 \u0437\u0430 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442\u0441\u044f \u0441\u0435\u0439\u0447\u0430\u0441 \u0432 \u044f\u0447\u0435\u0439\u043a\u0435. \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u0447\u0430\u0441\u0442\u043e \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u044e\u0442 \u0442\u0430\u043a\u043e\u0439 \u0432\u0430\u0440\u0438\u0430\u043d\u0442 CAS (\u0442\u0430\u043a \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u043c\u044b\u0439 valued CAS<\/i>, \u0442\u0430\u043a\u0436\u0435 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f \u0430\u0442\u043e\u043c\u0430\u0440\u043d\u043e):  <\/p>\n
int CAS( int * pAddr, int nExpected, int nNew ) atomically {       if ( *pAddr == nExpected ) {            *pAddr = nNew ;            return nExpected ;        }        else             return *pAddr  } <\/code><\/pre>\n
  \u0412 C++11 \u0444\u0443\u043d\u043a\u0446\u0438\u044f compare_exchange<\/code> (\u0441\u0442\u0440\u043e\u0433\u043e \u0433\u043e\u0432\u043e\u0440\u044f, \u0432 C++11 \u043d\u0435\u0442 \u0442\u0430\u043a\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438, \u0435\u0441\u0442\u044c \u0435\u0451 \u0440\u0430\u0437\u043d\u043e\u0432\u0438\u0434\u043d\u043e\u0441\u0442\u0438 compare_exchange_strong<\/code> \u0438 compare_exchange_weak<\/code>, \u043d\u043e \u043e\u0431 \u043d\u0438\u0445 \u044f \u0440\u0430\u0441\u0441\u043a\u0430\u0436\u0443 \u043f\u043e\u0437\u0436\u0435) \u043f\u043e\u043a\u0440\u044b\u0432\u0430\u0435\u0442 \u043e\u0431\u0430 \u044d\u0442\u0438 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u0430:  <\/p>\n
bool compare_exchange( int volatile * pAddr, int& nExpected, int nNew ); <\/code><\/pre>\n
  \u0410\u0440\u0433\u0443\u043c\u0435\u043d\u0442 nExpected<\/code> \u043f\u0435\u0440\u0435\u0434\u0430\u0435\u0442\u0441\u044f \u043f\u043e \u0441\u0441\u044b\u043b\u043a\u0435 \u0438 \u043d\u0430 \u0432\u0445\u043e\u0434\u0435 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u043e\u0436\u0438\u0434\u0430\u0435\u043c\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u043e\u0439 \u043f\u043e \u0430\u0434\u0440\u0435\u0441\u0443 pAddr<\/code>, \u0430 \u043d\u0430 \u0432\u044b\u0445\u043e\u0434\u0435 \u2013 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043f\u0435\u0440\u0435\u0434 \u0438\u0437\u043c\u0435\u043d\u0435\u043d\u0438\u0435\u043c. \u0412\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u0435\u0442 \u0436\u0435 \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u043f\u0440\u0438\u0437\u043d\u0430\u043a \u0443\u0441\u043f\u0435\u0445\u0430: true<\/code>, \u0435\u0441\u043b\u0438 \u043f\u043e \u0430\u0434\u0440\u0435\u0441\u0443 \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 nExpected<\/code> (\u0432 \u044d\u0442\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043e\u043d\u043e \u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f \u043d\u0430 nNew<\/code>), false<\/code> \u0432 \u0441\u043b\u0443\u0447\u0430\u0435 \u043d\u0435\u0443\u0434\u0430\u0447\u0438 (\u0442\u043e\u0433\u0434\u0430 nExpected<\/code> \u0431\u0443\u0434\u0435\u0442 \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0442\u044c \u0442\u0435\u043a\u0443\u0449\u0435\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u043e\u0439 \u043f\u043e \u0430\u0434\u0440\u0435\u0441\u0443 pAddr<\/code>). \u0422\u0430\u043a\u043e\u0435 \u0443\u043d\u0438\u0432\u0435\u0440\u0441\u0430\u043b\u044c\u043d\u043e\u0435 \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 CAS \u043f\u043e\u043a\u0440\u044b\u0432\u0430\u0435\u0442 \u043e\u0431\u0430 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u0430 \u201c\u0430\u043a\u0430\u0434\u0435\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e\u201d \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f CAS, \u043d\u043e \u043d\u0430 \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0435 \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u0435 compare_exchange<\/code> \u0447\u0440\u0435\u0432\u0430\u0442\u043e \u043e\u0448\u0438\u0431\u043a\u0430\u043c\u0438, \u0442\u0430\u043a \u043a\u0430\u043a \u043d\u0430\u0434\u043e \u043f\u043e\u043c\u043d\u0438\u0442\u044c, \u0447\u0442\u043e \u0430\u0440\u0433\u0443\u043c\u0435\u043d\u0442 nExpected<\/code> \u043f\u0435\u0440\u0435\u0434\u0430\u0435\u0442\u0441\u044f \u043f\u043e \u0441\u0441\u044b\u043b\u043a\u0435 \u0438 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0438\u0437\u043c\u0435\u043d\u0435\u043d, \u0447\u0442\u043e \u043d\u0435 \u0432\u0441\u0435\u0433\u0434\u0430 \u043f\u0440\u0438\u0435\u043c\u043b\u0435\u043c\u043e. 
  \u0421 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435\u043c compare_exchange<\/code> \u043f\u0440\u0438\u043c\u0438\u0442\u0438\u0432 fetch-and-add, \u043f\u043e\u043a\u0430\u0437\u0430\u043d\u043d\u044b\u0439 \u0432\u044b\u0448\u0435, \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u043d\u0430\u043f\u0438\u0441\u0430\u043d \u0442\u0430\u043a:  <\/p>\n
int FAA( int * pAddr, int nIncr ) {      int ncur = *pAddr;      do {} while ( !compare_exchange( pAddr, ncur, ncur + nIncr ) ;      return ncur ; } <\/code><\/pre>\n
ABA-\u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0430<\/h2>\n
  \u041f\u0440\u0438\u043c\u0438\u0442\u0438\u0432 CAS \u0432\u0441\u0435\u043c \u0445\u043e\u0440\u043e\u0448, \u043d\u043e \u043f\u0440\u0438 \u0435\u0433\u043e \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u0438 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u0430 \u0441\u0435\u0440\u044c\u0435\u0437\u043d\u0430\u044f \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0430, \u043f\u043e\u043b\u0443\u0447\u0438\u0432\u0448\u0430\u044f \u043d\u0430\u0437\u0432\u0430\u043d\u0438\u0435 ABA-\u043f\u0440\u043e\u0431\u043b\u0435\u043c\u044b<\/i>. \u0414\u043b\u044f \u0435\u0451 \u043e\u043f\u0438\u0441\u0430\u043d\u0438\u044f \u0441\u043b\u0435\u0434\u0443\u0435\u0442 \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0435\u0442\u044c \u0442\u0438\u043f\u0438\u0447\u043d\u044b\u0439 \u043f\u0430\u0442\u0442\u0435\u0440\u043d \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438 CAS:  <\/p>\n
int nCur = *pAddr ; while (true) {     int nNew = \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u043c \u043d\u043e\u0432\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435     if ( compare_exchange( pAddr, nCur, nNew ))         break; } <\/code><\/pre>\n
  \u0424\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u0438, \u043c\u044b \u201c\u0434\u043e\u043b\u0431\u0438\u043c\u0441\u044f\u201d \u0432 \u0446\u0438\u043a\u043b\u0435 \u0434\u043e \u0442\u0435\u0445 \u043f\u043e\u0440, \u043f\u043e\u043a\u0430 CAS \u043d\u0435 \u0441\u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442; \u0446\u0438\u043a\u043b \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c, \u0442\u0430\u043a \u043a\u0430\u043a \u043c\u0435\u0436\u0434\u0443 \u0447\u0442\u0435\u043d\u0438\u0435\u043c \u0442\u0435\u043a\u0443\u0449\u0435\u0433\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u043e\u0439 \u043f\u043e \u0430\u0434\u0440\u0435\u0441\u0443 pAddr<\/code> \u0438 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0435\u043c \u043d\u043e\u0432\u043e\u0433\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f nNew<\/code> \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u0430\u044f \u043f\u043e \u0430\u0434\u0440\u0435\u0441\u0443 pAddr<\/code> \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0438\u0437\u043c\u0435\u043d\u0435\u043d\u0430 \u0434\u0440\u0443\u0433\u0438\u043c \u043f\u043e\u0442\u043e\u043a\u043e\u043c.<\/p>\n
  
  ABA-\u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0430 \u043e\u043f\u0438\u0441\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c: \u0434\u043e\u043f\u0443\u0441\u0442\u0438\u043c, \u043f\u043e\u0442\u043e\u043a X \u0447\u0438\u0442\u0430\u0435\u0442 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 A \u0438\u0437 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0440\u0430\u0437\u0434\u0435\u043b\u044f\u0435\u043c\u043e\u0439 \u044f\u0447\u0435\u0439\u043a\u0438, \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0449\u0438\u0439 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u043d\u0430 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0434\u0430\u043d\u043d\u044b\u0435. \u0417\u0430\u0442\u0435\u043c \u0434\u0440\u0443\u0433\u043e\u0439 \u043f\u043e\u0442\u043e\u043a, Y, \u0438\u0437\u043c\u0435\u043d\u044f\u0435\u0442 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u044d\u0442\u043e\u0439 \u044f\u0447\u0435\u0439\u043a\u0438 \u043d\u0430 B \u0438 \u043e\u043f\u044f\u0442\u044c \u043d\u0430 A, \u043d\u043e \u0442\u0435\u043f\u0435\u0440\u044c \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c A \u0443\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442 \u043d\u0430 \u0434\u0440\u0443\u0433\u0438\u0435 \u0434\u0430\u043d\u043d\u044b\u0435. \u041a\u043e\u0433\u0434\u0430 \u043f\u043e\u0442\u043e\u043a X \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u043f\u0440\u0438\u043c\u0438\u0442\u0438\u0432\u0430 CAS \u043f\u044b\u0442\u0430\u0435\u0442\u0441\u044f \u043f\u043e\u043c\u0435\u043d\u044f\u0442\u044c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u044f\u0447\u0435\u0439\u043a\u0438, \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044f \u0441 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0438\u043c (\u043f\u0440\u043e\u0447\u0442\u0435\u043d\u043d\u044b\u043c) \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435\u043c A \u0443\u0441\u043f\u0435\u0448\u043d\u043e, \u0438 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442 CAS \u0443\u0441\u043f\u0435\u0448\u0435\u043d, \u043d\u043e A \u0442\u0435\u043f\u0435\u0440\u044c \u0443\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442 \u043d\u0430 \u0441\u043e\u0432\u0435\u0440\u0448\u0435\u043d\u043d\u043e \u0434\u0440\u0443\u0433\u0438\u0435 \u0434\u0430\u043d\u043d\u044b\u0435! \u0412 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0435 \u043f\u043e\u0442\u043e\u043a \u043c\u043e\u0436\u0435\u0442 \u043d\u0430\u0440\u0443\u0448\u0438\u0442\u044c \u0432\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u0438\u0435 \u0441\u0432\u044f\u0437\u0438 \u043e\u0431\u044a\u0435\u043a\u0442\u0430 (\u0447\u0442\u043e, \u0432 \u0441\u0432\u043e\u044e \u043e\u0447\u0435\u0440\u0435\u0434\u044c, \u043c\u043e\u0436\u0435\u0442 \u043f\u0440\u0438\u0432\u0435\u0441\u0442\u0438 \u043a \u043a\u0440\u0430\u0445\u0443).<\/p>\n
  \u0412\u043e\u0442 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f lock-free \u0441\u0442\u0435\u043a\u0430, \u043f\u043e\u0434\u0432\u0435\u0440\u0436\u0435\u043d\u043d\u043e\u0433\u043e ABA-\u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0435 [Mic04]:  <\/p>\n
\/\/ Shared variables static NodeType * Top = NULL; \/\/ Initially null  Push(NodeType * node) {              do {  \/*Push1*\/ \t   NodeType * t = Top; \/*Push2*\/\t   node->Next = t; \/*Push3*\/   } while ( !CAS(&Top,t,node) ); }  NodeType * Pop() {            Node * next ;           do {  \/*Pop1*\/        NodeType * t = Top; \/*Pop2*\/        if ( t == null ) \/*Pop3*\/             return null; \/*Pop4*\/        next = t->Next; \/*Pop5*\/   } while ( !CAS(&Top,t,next) ); \/*Pop6*\/   return t; } <\/code><\/pre>\n
  \u0421\u043b\u0435\u0434\u0443\u044e\u0449\u0430\u044f \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u0439 \u043f\u0440\u0438\u0432\u043e\u0434\u0438\u0442 \u043a \u043d\u0430\u0440\u0443\u0448\u0435\u043d\u0438\u044e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0441\u0442\u0435\u043a\u0430 (\u0437\u0430\u043c\u0435\u0442\u0438\u043c, \u0447\u0442\u043e \u044d\u0442\u0430 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u043d\u0435 \u0435\u0434\u0438\u043d\u0441\u0442\u0432\u0435\u043d\u043d\u0430\u044f, \u0438\u043b\u043b\u044e\u0441\u0442\u0440\u0438\u0440\u0443\u044e\u0449\u0430\u044f ABA-\u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0443):  <\/p>\n\n\n\n\n\n
Thread X<\/b><\/td>\nThread Y<\/b><\/td>\n<\/tr>\n
 \u0412\u044b\u0437\u044b\u0432\u0430\u0435\u0442 Pop()<\/code>. 
   \u0412\u044b\u043f\u043e\u043b\u043d\u0435\u043d\u0430 \u0441\u0442\u0440\u043e\u043a\u0430 Pop4<\/code>, 
   \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445: t == A<\/code> 
    next == A->next<\/code>    <\/td>\n		 <\/td>\n<\/tr>\n
 <\/td>\n  NodeType * pTop = Pop()<\/code>
  pTop<\/code> == \u0432\u0435\u0440\u0448\u0438\u043d\u0435 \u0441\u0442\u0435\u043a\u0430, \u0442\u043e \u0435\u0441\u0442\u044c A
  Pop()<\/code>
  Push( pTop )<\/code>
  \u0422\u0435\u043f\u0435\u0440\u044c \u0432\u0435\u0440\u0448\u0438\u043d\u0430 \u0441\u0442\u0435\u043a\u0430 \u2013 \u0441\u043d\u043e\u0432\u0430 A
  \u0417\u0430\u043c\u0435\u0442\u0438\u043c, \u0447\u0442\u043e A->next<\/code> \u0438\u0437\u043c\u0435\u043d\u0438\u043b\u043e\u0441\u044c   <\/td>\n<\/tr>\n
 \u0412\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f \u0441\u0442\u0440\u043e\u043a\u0430 Pop5<\/code>. 
   CAS \u0443\u0441\u043f\u0435\u0448\u0435\u043d, \u043d\u043e \u043f\u043e\u043b\u044e Top->next<\/code> 
   \u043f\u0440\u0438\u0441\u0432\u0430\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435, 
   \u043d\u0435\u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u044e\u0449\u0435\u0435 \u0432 \u0441\u0442\u0435\u043a\u0435, 
   \u0442\u0430\u043a \u043a\u0430\u043a \u043f\u043e\u0442\u043e\u043a Y \u0432\u044b\u0442\u043e\u043b\u043a\u043d\u0443\u043b 
   \u0438\u0437 \u0441\u0442\u0435\u043a\u0430 A \u0438 A->next<\/code>,
   \u0430 \u043b\u043e\u043a\u0430\u043b\u044c\u043d\u0430\u044f \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u0430\u044f next<\/code>
   \u0445\u0440\u0430\u043d\u0438\u0442 \u0441\u0442\u0430\u0440\u043e\u0435<\/i> \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 A->next<\/code>   <\/td>\n		 <\/td>\n<\/tr>\n<\/table>\n
  ABA-\u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0430 \u2013 \u044d\u0442\u043e \u0431\u0438\u0447 \u0432\u0441\u0435\u0445 lock-free \u043a\u043e\u043d\u0442\u0435\u0439\u043d\u0435\u0440\u043e\u0432, \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u043d\u044b\u0445 \u043d\u0430 \u043f\u0440\u0438\u043c\u0438\u0442\u0438\u0432\u0435 CAS. \u041e\u043d\u0430 \u043c\u043e\u0436\u0435\u0442 \u0432\u043e\u0437\u043d\u0438\u043a\u043d\u0443\u0442\u044c \u0442\u043e\u043b\u044c\u043a\u043e \u0432 \u043c\u043d\u043e\u0433\u043e\u043f\u043e\u0442\u043e\u0447\u043d\u043e\u043c \u043a\u043e\u0434\u0435 \u0432\u0441\u043b\u0435\u0434\u0441\u0442\u0432\u0438\u0435 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 A \u0438\u0437 \u043a\u043e\u043d\u0442\u0435\u0439\u043d\u0435\u0440\u0430 \u0438 \u0437\u0430\u043c\u0435\u043d\u044b \u0435\u0433\u043e \u043d\u0430 \u0434\u0440\u0443\u0433\u043e\u0439 (B), \u0430 \u0437\u0430\u0442\u0435\u043c \u043e\u043f\u044f\u0442\u044c \u043d\u0430 A (\u043e\u0442\u0441\u044e\u0434\u0430 \u0438 \u043d\u0430\u0437\u0432\u0430\u043d\u0438\u0435 "ABA<\/i>-\u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0430"), \u0432 \u0442\u043e \u0432\u0440\u0435\u043c\u044f \u043a\u0430\u043a \u0434\u0440\u0443\u0433\u043e\u0439 \u043f\u043e\u0442\u043e\u043a \u0434\u0435\u0440\u0436\u0438\u0442 \u0443\u043a\u0430\u0437\u0430\u0442\u0435\u043b\u044c \u043d\u0430 \u0443\u0434\u0430\u043b\u044f\u0435\u043c\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442. \u0414\u0430\u0436\u0435 \u0435\u0441\u043b\u0438 \u043f\u043e\u0442\u043e\u043a \u0444\u0438\u0437\u0438\u0447\u0435\u0441\u043a\u0438 \u0443\u0434\u0430\u043b\u0438\u0442 A (delete A<\/code>), \u0430 \u0437\u0430\u0442\u0435\u043c \u0432\u044b\u0437\u043e\u0432\u0435\u0442 new<\/code> \u0434\u043b\u044f \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u044f \u043d\u043e\u0432\u043e\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430, \u043d\u0435\u0442 \u043d\u0438\u043a\u0430\u043a\u0438\u0445 \u0433\u0430\u0440\u0430\u043d\u0442\u0438\u0439, \u0447\u0442\u043e \u0430\u043b\u043b\u043e\u043a\u0430\u0442\u043e\u0440 \u043d\u0435 \u0432\u043e\u0437\u0432\u0440\u0430\u0442\u0438\u0442 \u0430\u0434\u0440\u0435\u0441 A (\u0445\u043e\u0440\u043e\u0448\u0438\u0435 \u0430\u043b\u043b\u043e\u043a\u0430\u0442\u043e\u0440\u044b \u0438\u043c\u0435\u043d\u043d\u043e \u0442\u0430\u043a \u0438 \u0441\u0434\u0435\u043b\u0430\u044e\u0442). \u0427\u0430\u0441\u0442\u043e \u043e\u043d\u0430 \u043f\u0440\u043e\u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0431\u043e\u043b\u0435\u0435 \u0438\u0437\u043e\u0449\u0440\u0435\u043d\u043d\u044b\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u0447\u0435\u043c \u043e\u043f\u0438\u0441\u0430\u043d\u043e \u0432\u044b\u0448\u0435, \u0437\u0430\u0442\u0440\u0430\u0433\u0438\u0432\u0430\u0435\u0442 \u043d\u0435 \u0434\u0432\u0430, \u0430 \u0431\u043e\u043b\u0435\u0435 \u043f\u043e\u0442\u043e\u043a\u043e\u0432 (\u0432 \u044d\u0442\u043e\u043c \u0441\u043c\u044b\u0441\u043b\u0435 \u043c\u043e\u0436\u043d\u043e \u0433\u043e\u0432\u043e\u0440\u0438\u0442\u044c \u043e ABCBA-\u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0435, ABABA-\u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0435 \u0438 \u0442.\u0434., \u043d\u0430\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0445\u0432\u0430\u0442\u0438\u0442 \u0444\u0430\u043d\u0442\u0430\u0437\u0438\u0438), \u0438 \u0435\u0451 \u0438\u0434\u0435\u043d\u0442\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u044f \u0432\u0441\u0435\u0433\u0434\u0430 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043d\u0435\u0442\u0440\u0438\u0432\u0438\u0430\u043b\u044c\u043d\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0435\u0439. \u0421\u0440\u0435\u0434\u0441\u0442\u0432\u043e \u0431\u043e\u0440\u044c\u0431\u044b \u0441 ABA-\u043f\u0440\u043e\u0431\u043b\u0435\u043c\u043e\u0439 \u2013 \u043e\u0442\u043b\u043e\u0436\u0435\u043d\u043d\u043e\u0435 \u0444\u0438\u0437\u0438\u0447\u0435\u0441\u043a\u043e\u0435<\/i> \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435 (deferred deallocation<\/i>, \u0438\u043b\u0438 safe memory reclamation<\/i>) \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0432 \u043c\u043e\u043c\u0435\u043d\u0442, \u043a\u043e\u0433\u0434\u0430 \u0435\u0441\u0442\u044c \u043f\u043e\u043b\u043d\u0430\u044f \u0433\u0430\u0440\u0430\u043d\u0442\u0438\u044f, \u0447\u0442\u043e \u043d\u0438\u043a\u0442\u043e (\u043d\u0438 \u043e\u0434\u0438\u043d \u0438\u0437 \u043a\u043e\u043d\u043a\u0443\u0440\u0438\u0440\u0443\u044e\u0449\u0438\u0445 \u043f\u043e\u0442\u043e\u043a\u043e\u0432) \u043d\u0435 \u0438\u043c\u0435\u0435\u0442 \u043d\u0438 \u043b\u043e\u043a\u0430\u043b\u044c\u043d\u044b\u0445, \u043d\u0438 \u0433\u043b\u043e\u0431\u0430\u043b\u044c\u043d\u044b\u0445 \u0441\u0441\u044b\u043b\u043e\u043a \u043d\u0430 \u0443\u0434\u0430\u043b\u044f\u0435\u043c\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442. 
  \u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0438\u0437 lock-free \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0434\u0432\u0443\u0445\u0444\u0430\u0437\u043d\u044b\u043c:  <\/p>\n