Транзакциялық жад: Параллель бағдарламалауды жеңілдету жолы

Кіріспе

Компьютерлік ғылым мен инженерияда транзакциялық жад бір мезгілде бағдарламалауды жеңілдетуге бағытталған, жүктеу және сақтау нұсқауларының тобын атомдық түрде орындауға мүмкіндік береді. Бұл, бір мезгілдегі есептеулерде ортақ жадқа қол жеткізуді басқару үшін деректер базасы транзакцияларына ұқсас, бір мезгілделікті басқару механизмі. Транзакциялық жад жүйелері, төменгі деңгейдегі жиектерді синхрондаудың орнына жоғары деңгейдегі абстракцияны ұсынады. Бұл абстракция, параллель жүйелерде ортақ деректерді бір мезгілде оқу және жазуды үйлестіруге мүмкіндік береді.

Мотивация

Бір мезгілдегі бағдарламалауда, қатарлы жіптер ортақ ресурсқа қол жеткізуге тырысқанда синхронизация қажет. Құлыптар сияқты төмен деңгейлі жіп синхронизациясы құрылымдары пессимистік болып табылады және маңызды бөлімнен тыс жіптерге маңызды бөліммен қорғалған кодты орындауға тыйым салады. Құлыптарды қолдану және босату процесі көбінесе жіптер арасында келіспеушілік аз болған кезде қосымша жүктеме ретінде жұмыс істейді. Транзакциялық жад, жіптерге минималді кедергімен қатар жұмыс істеуге мүмкіндік беру арқылы оптимистік қатарлы басқаруды қамтамасыз етеді. Транзакциялық жад жүйелерінің мақсаты – атомдық қасиеттерді, дәйектілікті және оқшаулануды сақтап, транзакция ретінде белгіленген код аймақтарын ашық түрде қолдау. Транзакция – бұл қақтығыс болмаған жағдайда өзгерістерді орындап, бекітетін операциялардың жиынтығы. Егер қақтығыс анықталса, транзакция бастапқы күйіне (өзгерістер жасау алдында) қайта оралады және барлық қақтығыстар жойылғанға дейін қайтадан орындалады. Сәтті бекітуге дейін транзакция ішіндегі кез келген операцияның нәтижесі болжамды болып табылады. Деректердің бұзылуын болдырмау үшін операцияларды тізбектеп орындауға негізделген құлыптау синхронизациясына қарағанда, транзакциялар ортақ ресурсты өзгертуге тырысатын операциялар аз болғанда қосымша параллелизмге мүмкіндік береді. Бағдарламашы құлыптарды немесе олардың қолданылу ретін нақты анықтауға жауапты болмағандықтан, транзакциялық жадты пайдаланатын бағдарламалар өлі тұруға (deadlock) әкелмейді. Аппараттық транзакциялық жад жүйелері процессорларға, кэш жадына және транзакцияларды қолдау үшін шина протоколына өзгерістер енгізуі мүмкін. Транзакциядағы болжамды мәндер буферде сақталуы керек және басқа жіптерге бекітілгенге дейін көрінбеуі керек. Үлкен буферлер болжамды мәндерді сақтау үшін қолданылады, сонымен бірге негізгі кэш жадының сәйкестік протоколы арқылы жазудың таралуын болдырмайды. Дәстүрлі түрде буферлер жад иерархиясындағы әртүрлі құрылымдарды, мысалы, сақтау кезектерін немесе кэш жадыны пайдалана отырып іске асырылады. Процессордан алыс орналасқан L2 кэш сияқты буферлер көбірек болжамды мәндерді (бірнеше мегабайтқа дейін) сақтай алады. Коммерциялық бағдарламаларда транзакциялардың қолданылуы шектеулі болғандықтан буфердің оңтайлы көлемі әлі де талқыланып жатыр және минималды аппараттық қолдауды қажет етеді (әдетте, атомдық салыстыру және алмастыру операциясы немесе оған баламасы). Алайда, бағдарламалық іске асырулар аппараттық шешімдермен салыстырғанда өнімділік жоғалтуына әкелуі мүмкін. Аппараттық үдеткіш бағдарламалық транзакциялық жадпен байланысты кейбір қосымша шығындарды азайта алады. Қазіргі іске асырулардағы аппараттық транзакциялық жадтың шектеулі мүмкіндіктеріне байланысты, оны пайдаланатын бағдарламаларға толыққанды пайда алу үшін кең ауқымды жөндеулер қажет болуы мүмкін. Мысалы, динамикалық жадты бөлуші өнімділікке елеулі әсер етуі мүмкін, ал құрылымды толтыру кэш жадының сәйкестігі және жалған ортақтастыру мәселелеріне байланысты өнімділікке әсер етуі мүмкін; виртуалды машина контекстінде әртүрлі фоновые жіптер күтпеген транзакцияны тоқтатуға себеп болуы мүмкін.

In concurrent programming, synchronization is required when parallel threads attempt to access a shared resource. Low level thread synchronization constructs such as locks are pessimistic and prohibit threads that are outside a critical section from running the code protected by the critical section. The process of applying and releasing locks often functions as an additional overhead in workloads with little conflict among threads. Transactional memory provides optimistic concurrency control by allowing threads to run in parallel with minimal interference. The goal of transactional memory systems is to transparently support regions of code marked as transactions by enforcing atomicity, consistency and isolation. A transaction is a collection of operations that can execute and commit changes as long as a conflict is not present. When a conflict is detected, a transaction will revert to its initial state (prior to any changes) and will rerun until all conflicts are removed. Before a successful commit, the outcome of any operation is purely speculative inside a transaction. In contrast to lock based synchronization where operations are serialized to prevent data corruption, transactions allow for additional parallelism as long as few operations attempt to modify a shared resource. Since the programmer is not responsible for explicitly identifying locks or the order in which they are acquired, programs that utilize transactional memory cannot produce a deadlock. Hardware transactional memory systems may comprise modifications in processors, cache and bus protocol to support transactions. Speculative values in a transaction must be buffered and remain unseen by other threads until commit time. Large buffers are used to store speculative values while avoiding write propagation through the underlying cache coherence protocol. Traditionally, buffers have been implemented using different structures within the memory hierarchy such as store queues or caches. Buffers further away from the processor, such as the L2 cache, can hold more speculative values (up to a few megabytes). The optimal size of a buffer is still under debate due to the limited use of transactions in commercial programs. and requires minimal hardware support (typically an atomic compare and swap operation, or equivalent). As the downside, software implementations usually come with a performance penalty, when compared to hardware solutions. Hardware acceleration can reduce some of the overheads associated with software transactional memory. Owing to the more limited nature of hardware transactional memory (in current implementations), software using it may require fairly extensive tuning to fully benefit from it. For example, the dynamic memory allocator may have a significant influence on performance and likewise structure padding may affect performance (owing to cache alignment and false sharing issues); in the context of a virtual machine, various background threads may cause unexpected transaction aborts.

Тарих

Транзакциялық жадтың ең алғашқы іске асырылған түрлерінің бірі – Transmeta компаниясының Crusoe және Efficeon процессорларында қолданылған есікті сақтау буфері. Дегенмен, бұл тек екілік кодты аудармалау арқылы болжамды оңтайландыруды жеңілдету үшін ғана пайдаланылды, емес, кез келген түріндегі болжамды көп өрісті жұмыспен немесе бағдарламашыларға тікелей қолжетімді ету үшін. Azul Systems Java құрылғыларын жылдамдату мақсатында аппараттық транзакциялық жадты іске қосты, бірақ ол да сыртқы қолданушылардан жасырын болды. Sun Microsystems өзінің Rock процессорында аппараттық транзакциялық жадты және шектеулі болжамды көп өрістілікті іске асырды. Бұл іске асыру, оның құлыптауларды (lock) жою және транзакциялар аппараттық және бағдарламалық қамтамасыз етудің үйлесімімен жүзеге асырылатын күрделі гибридтік транзакциялық жад жүйелері үшін қолданылуы мүмкін екенін көрсетті. Rock процессоры 2009 жылы Oracle компаниясы сатып алғанға дейін тоқтатылды; нақты өнімдер жарыққа шықпады, бірақ зерттеушілерге прототиптік жүйелердің бірнеше үлгісі қолжетімді болды. GCC 4.7 нұсқасынан бастап гибридтік іске асыруды қолданатын транзакциялық жадқа арналған эксперименталды кітапхана бар. Python тілінің PyPy нұсқасы да осы тілге транзакциялық жадты енгізеді.