軟件事務存儲系統(tǒng)設計選擇

1、軟件事務存儲系統(tǒng)設計選擇摘要：多核微處理器的發(fā)展為線程級并行編程帶來了新的機遇和挑戰(zhàn)。面對傳統(tǒng)鎖機制應用對并行開發(fā)帶來的諸多困難，借鑒數據庫中事務的概念提出事務存儲技術。軟件事務存儲系統(tǒng)的性能受設計上各方面因素的影響，比如基于字或基于對象、基于鎖或無阻塞、直寫或回寫、早檢測或晚檢測。對此進行了論述。關鍵詞：軟件事務存儲；設計選擇；數據組織方式；更新控制方式0引言多核微處理器的發(fā)展為線程級并行編程帶來新的機遇和挑戰(zhàn)。新的摩爾定律指出，在基本不變的主頻下，單個芯片上的處理器核的數目每一代(約兩年)增加一倍。當前，程序性能的提高只能依靠并行，并行算法和并行編程是今后幾十年計算機科學和軟件界必須突破的

2、科學問題和關鍵技術。并行程序設計將越來越大眾化，對提高并行程序設計的產出率(Productivity)的要求越來越高，提供易用高效的并行編程手段顯得尤為關鍵。傳統(tǒng)的用于線程間同步的鎖機制編程困難，可擴展性差，并不適于未經專業(yè)培訓的一般程序員使用：粗粒度鎖由于一次性地對本地大量數據進行保護，即使兩個線程之間理論上并不存在干擾，也可能因粗粒度鎖而產生沖突，因此粗粒度鎖不適于拓展，性能較低；細粒度鎖雖然性能高，但在實現上很難保證其準確性及避免死鎖。同時，鎖技術容易致使線程脆弱，即線程更加容易失敗或延遲。比如，持有鎖的線程會阻塞其它線程。研究人員為解決以上問題，借鑒數據庫中的事務概念提出事務存儲(Tr

3、ansactionalMemory，TM)技術，希望獲得一種像粗粒度一樣容易使用、性能接近細粒度鎖的同步手段。事務存儲技術在事務存儲技術中，線程事務采用原子執(zhí)行單元來替代鎖。各線程事務以原子的方式執(zhí)行，把維持事務特性的工作交給編譯器、運行時庫或硬件完成，進一步的性能調優(yōu)可以在系統(tǒng)層完成。比如，如下計算直方圖的代碼塊：atomichistarrayij+；程序員可將其看作是一個臨界區(qū)，TM實現來決定如何將該臨界區(qū)與其它線程隔離運行。根據事務存儲系統(tǒng)實現方法的不同，目前的事務存儲系統(tǒng)的研究主要有3個方向：基于硬件實現的硬件事務存儲系統(tǒng)(HTM，HardwareTransactionMemory),

4、女口Stanford大學的TCC;基于運行時庫實現的軟件事務存儲系統(tǒng)(STM,SoftwareTransactionMemory)，如Rochester大學的RSTM；結合軟硬件實現的混合事務存儲系統(tǒng)(HybridTransactionMemory)，女口Rajwar等提出的VTM。HTM系統(tǒng)主要由硬件實現，速度最快，并行粒度是cache行或內存字；STM以計算機語言實現，并行力度是對象或內存字，速度較慢，但比較靈活；HyTM由適當的軟件或硬件實現，性能介于HTM與STM之間。本文主要研究軟件事務存儲技術。事務存儲實現方式為了實現事務的特性，一般來說，軟件事務存儲的實現必須具備三大功能。沖突檢

5、測。事務在執(zhí)行過程中，要根據具體的情況適時地檢測沖突，只有在無沖突發(fā)生的情況下，事務才能提交。一致性校驗。事務在執(zhí)行過程中始終要保持共享對象的一致性狀態(tài)。在共享對象不一致的狀態(tài)下，計算可能會產生無法控制的結果，如死循環(huán)或除零錯。所以，即使執(zhí)行過程中沒有檢測到沖突，事務還是可能進行一致性校驗。沖突消解。當沖突發(fā)生后，需要采取一定的措施來消解沖突。當前的各種STM通過不同手段來實現上述三大功能。早檢測與晚檢測對于沖突的檢測，可以分為早檢測(earlydetect)和晚檢測(lazydetect)。早檢測即每當事務讀或寫時，都會去檢測是否有沖突事務存在，以此來保持共享對象的一致性。因此，早檢測策略需

6、要事務的讀集(readse)及寫集(writeset)對所有的事務都是可見的，我們將這種設計稱之為可見讀(visibleread)設計。Harris于2003年提出不可見讀，與之相應的是晚檢測策略，只有在事務提交時才依靠對讀集的檢測來確定是否存在沖突事務。一般來說，早檢測能比晚檢測更加及時地發(fā)現沖突，從而避免沖突事務執(zhí)行不必要的操作，且檢測手段的實現相對簡單，但早檢測的執(zhí)行開銷明顯大于晚檢測?；阪i與無阻塞鑒于前面提到的鎖機制的各種缺陷，早期的STM研究將無阻塞(nonblocking)作為實現目標。無阻塞算法能夠保證進程不會因不活躍的線程而阻塞，從而避免優(yōu)先級倒置或線程死鎖。其中，Herli

7、hy等人提出的無干擾同步算法(obstructionfreesynchronization)是比較典型的無阻塞算法。然而，無阻塞算法無論在其結構還是運行時的CAS(compareandswap操作都比較復雜，相應的無阻塞的STM性能遠遠低于良好實現的鎖機制。為應對這種情況，基于鎖的(lockbased)STM應運而生。基于鎖的STM采用互斥版本鎖(versionedmutualexclusior)技術，如圖1。該技術支持普通的互斥語義且提供對版本號(versionnumber)的訪問，通過版本號來統(tǒng)計加鎖和解鎖的次數。當事務第一次讀取某對象時，記錄其版本號。事務提交之前必須保證該版本號未改變，

8、即不存在其它事務對該對象進行修改?；コ獍姹炬i技術比較靈活，可以支持大多數的STM實現，既可以在事務執(zhí)行過程中對其訪問的共享對象加鎖，比如BartokSTM，也可以只在提交時加鎖?；谧峙c基于對象軟件事務存儲系統(tǒng)根據其數據組織方式可分為基于對象(objectbased)即面向對象的實現和基于字(wordbasec)即面向內存單元的實現。面向對象的實現由Herlihy提出。事務通過共享對象的封裝容器(Locator)來訪問對象，如圖2,共享對象在封裝容器中被分為兩個部分：新版本(NewVersion)和舊版本(OldVersions)，事務訪問共享對象時根據操作類型判斷獲得哪個版本,并在提交或放棄

9、時更新兩個版本對象中的內容。典型的基于字的STM實現有DSTM,OSTM,ASTM等?；谧值腟TM直接對內存中的數據進行訪問,且使用獨立的結構來維持其自身元數據(metadata，女口BartokSTM通過將字地址映射至事務字(TMW，transactinalmetadata中來管理數據。直寫與回寫現有的STM系統(tǒng)基本分為兩種控制更新方式：直寫(writethrough)和回寫(writeback)。直寫方式允許事務直接將修改內容寫到內存之中，并將更新信息保存至撤銷日志(undolog)當中。當事務遇到沖突而被迫放棄時，依據撤銷日志將內存內容恢復至更新之前。采用回寫方式的STM系統(tǒng)的每個事務

10、各自維持一個緩存，事務將要更新的內容寫入到緩存之中，事務提交時，再將緩存內容寫入內存。結語相對于鎖機制，一方面TM技術為程序員提供了更高層次的抽象，使程序員不再糾結于同步機制的算法細節(jié)；另一方面，TM技術在程序的拓展性與實現之間提供了一個較好的權重。雖然一個良好設計的鎖也具有良好的拓展性，但設計起來具有相當的技術難度。另外，TM技術能夠很好地避免死鎖。雖然可能會出現導致活鎖的現象，即相沖突的進程不斷地搶占或放棄共享資源，致使每個進程都無法向前，但這種情況明顯比死鎖要好解決得多。如何在保證性能的情況下很好地避免活鎖，是TM技術目前的一個研究重點。參考文獻：LANCEHAMMOND，BRIAND，

11、CARLSTROM，etal.Programmingwithtransactionalcoherenceandconsistency（tcc）C.InProceedingsofthe1thinternationalconferenceonArchitecturalsupportforprogramminglanguageandoperatingsystem，sASPLOSXI，pages113，NewYork，NY，USA，2004.ACM.ROCHER.RstmrochestersoftwaretransactionalmemoryEB/OL.http：RAVIRAJWAR，MAURICEH

12、ERLIHY，KONRADLAI.VirtualizingtransactionalmemoryC.InProceedingsofthe32ndannualinternaltionalsymposiumonComputerArchitecture，ISCA5，pages494505，Washington，DC，USA，2005.IEEEComputerSociety.MHERLIHYV，LUCHANGCO，MMOIR.SoftwaretransactionalmemoryfordynamicsizeddatastructuresC.PODC03：ProceedingsoftheTwentysecondAnnualSymposiumonPrinciplesofDistributedComputing.ACM，NewYork，NY，USA，2003.MHERLIHY，VLUCHANGCO，MMOIR.Obstructionfreesynchronization：doubleendedqueuesasanexampleC.Proc.23rdIEEEIntlConf.DistributedComputingSystems（ICDCS03），IEEECSPress，2003.（PLDI06），ACMPress，2006.KFRASER.Practicallockfreedom，docto