361
為什麼我們需要STM（Software Transactional Memory）
update: 2013-8-20
從pypy的博客上看，他們早已實現了STM版的pypy：https://morepypy.blogspot.com/2013/08/update-on-stm.html，不過，貌似還有很多問題。
最近看到一個國內牛人的博客：https://www.cnblogs.com/coryxie/，上麵有很多關於無鎖算法，STM的東東。
才知道原來無論是軟件事務內存，還是硬件事務內存，都早有實現了。。
---------------------------------------------------------------------------------
原文：https://morepypy.blogspot.com/2011/08/we-need-software-transactional-memory.html
這是pypy開發者寫的一篇blog，裏麵提到了Python，Java等多線程實現的情況，還有一個很有意思的東東：STM（Software Transactional Memory）。
簡單記錄下一些心得和想法（很可能有不對的地方:) ）。
大部分腳本語言都沒有多線程機製（支持coroutine，但這實際上是單線程執行的）。why?
為什麼Java能原生地支持多線程？為什麼在執行那些錯誤的不同步的多線程代碼時JVM不會崩潰？
我們都知道，像C/C++如果執行錯誤的不同步的多線程代碼，程序很容易崩潰。因為指針什麼的，多個線程一起亂搞，內存馬上就亂了，程序自然也潰崩了。
程序運行的虛擬機必須要提供這樣的保證：
當一個線程在讀或者寫一個對象時，有另一個線程在寫這個對象，
程序隻會讀到舊的對象，或者新的對象，不會出現除此之外的情況（即讀取到另一個線程寫了一半的數據等）。
並且，虛擬機不會crash（即使用戶寫了錯誤的代碼）。
首先考慮Java的實現，因為Java並沒有內置的list和dict，對於java.util.HashMap，並不保證多線程的安全性（盡管可能拋出一個異常，但是這個異常是HashMap的代碼中拋出的，非語言本身的機製）。所以在Java中，隻要解決對象的引用即可。而在32位機器上，CPU保證4字節的讀寫原子性，所以Java不用加鎖，如果修改對象，直接修改引用的即可。
再考慮Python，Python原生支持list和dict，所以它必須要提供對這兩者原子性的操作（當然還有其它的一些東東也要支持原子操作）。比如dict的get和remove操作，如果不是原子性的，那麼在多線程情況下，dict就會被破壞。
來看下python解析器是怎樣實現的：
CPython使用GIL（Global Interpreter Lock），為每塊bytecode加鎖，大約是100條（有很多人對CPython有誤解，以為它隻能單線程執行，實際上它是可以多線程運行的）。
jpython利用java級的鎖，為每一個需要的操作都加鎖。因為Java的優化很牛B了，所以效率還可以接受（為什麼不用C來實現這個，或者說CPython為什麼不也這麼做，因為要做很多的工作，而且很可能會帶來很多微妙的bug）。
pypy 和Cpython類似。
STM是什麼
STM有點像數據庫的事務，不過STM是對於程序執行來說的，大概是這樣的一個過程：
在程序開始執行"bytecode"時，先開啟一個事務，用一個ThreadLocal的東東來記錄事務中的log
記錄讀取的所有的對象和修改對象的記錄
在上麵的過程中“探測”有沒有修改，比如檢查一個對象的最後修改時間是否和事務開始時一致。
如果執行到"bytecode"的最後，沒有發現修改，則把修改的內存"commit"，如果有修改，則"rollback"。
換一個說法，就是在CPython的開始獲得CIL時，開始事務，在釋放CIL時，提交事務。
在CPython調用係統調用時（釋放CIL），結束事務，在係統調用結束時（獲得CIL），開始事務。
話說STM的確是個很有意思的東東。不過pypy目前還沒有實現，不知道效率會怎樣。
不過我個人感覺，這東東即使實現了，恐怕效率也很難跟得上。想像一個有數百個線程的統計程序，共享一個結果變量count，這樣的話，基本每次執行的代碼都要"rollback"，這樣比單線程更悲劇。
最後更新：2017-04-02 16:48:06