用於將在多線程上工作的程序的程序代碼變換為鎖衝突少的程序代碼的方法及其計算機...的製作方法

2023-06-12 16:02:51 2

專利名稱：用於將在多線程上工作的程序的程序代碼變換為鎖衝突少的程序代碼的方法及其計算機 ...的製作方法
技術領域：
本發明涉及用於將在多線程上工作的程序的程序代碼變換為鎖衝突少的程序代碼的方法及其電腦程式和計算機系統。
背景技術：
近幾年，在處理器設計中，正在轉向將多個CPU核封入一個中央運算處理裝置(下面稱CPU :central Processing Unit)的內部的所謂多核。多核被認為是在外部有一個 CPU，但在內部有兩個CPU。通過多核，在主要進行並行處理的環境下，能夠提高CPU核整體的處理能力，實現系統性能提高。多核使處理器能夠同時執行的硬體線程數量飛躍增加。例如，SUN (商標)Niagara〗(商標)能夠在一個CPU上執行64個線程。在能夠同時執行多個線程的處理器上執行以往的程序的情況下，由於鎖衝突引起的處理器的性能降低成為問題。在此，所謂鎖衝突是在某一線程為了進入需要排他執行的臨界區而獲得鎖的情況下，在其他線程中在上述鎖解除之前不執行下一步驟的狀態。典型而言，不執行下一步驟的線程成為自旋環(spin loop)或休眠(sl^p)狀態。發生鎖衝突的原因多種多樣。例如，考慮從隊列取出數據的處理在多個線程頻繁執行的程序的情況。此外，考慮在上述程序的程序代碼中，在用於記載需要排他執行的處理的同步塊中記載有關於上述取出處理的語句。在執行時，上述程序每次調出上述取出處理時都獲得鎖。因此，頻繁地發生鎖衝突。所以，由於頻繁地發生的鎖衝突，可能引起系統性能上的問題。在SUN(商標)BUG DateBase中報告了在能夠執行32個硬體線程的計算機系統中， 與上述程序代碼相似的構造的程序代碼的程序成為系統性能上的瓶頸(http://bugS. sun. com/bugdatabase/view_bug. do ？ bug_id = 6525425)。通過該報告，具有上述類似構造的程序代碼的 SUN JDK1. 5. 013 的 java. lang. ref. RereferenceQueue 類中確認了上述問題。上述類的方法即與上述取出處理對應的pollO方法在SUNJDK1. 5. 014中修正。在該修正中，在polio方法的安裝中，在關於獲得鎖的處理的語句之前插入關於判斷隊列是否為空並在判斷為空時退出方法的處理的語句。下述非專利文獻1記載向程序代碼附加marked bit，利用該附加的marked bit 和compareAndSwap (CAQ命令，由此程序代碼能夠變形為同時並行性(concurrency)高的程序代碼。在下述非專利文獻1中，手動進行上述marked bit的附加。非專利文獻1 Martin Vechev, Eran Yahav, Deriving Linearizable Fine-Grained Concurrent Objects，PLDI，08，ACM 978-1-59593-860-2/08/06，2008 年 6 月 7 日 13 日

發明內容
每次發生由鎖衝突引起的性能降低的問題時，需要確定其原因，通過人工修正程序代碼的作業。但是，從現有的程序代碼的量考慮，該作業需要大量工作負荷所以不可能接近。因此，需要自動確定上述問題將要發生的位置，自動修正該位置的方法。本發明提供將在多線程上工作程序的程序代碼變換為鎖衝突少的程序代碼的方法。該方法使計算機系統執行下述步驟。所述步驟包括檢索步驟，向存儲器內讀出上述程序代碼，從該讀出的程序代碼檢索在同步塊內且向對該同步塊沒有副作用的路徑分支的第一條件句，沒有上述副作用是指基於上述同步塊內的語句處理中的值無法由上述同步塊外的語句參照；複製步驟，向上述同步塊外複製由上述檢索出的第一條件句分支的沒有副作用的路徑；追加步驟，與上述複製相應地在上述程序代碼內追加第二條件句，上述第二條件句是向上述複製的沒有副作用的路徑分支的條件句。通過上述方法，在向沒有副作用的路徑分支時，不執行同步塊內的第一條件句。因此，鎖衝突減少。上述方法特別在有一個條件句兩個分支的情況下有效。在本發明的一個實施方式中，上述第一條件句包含第一條件式。該第一條件式定義為基於第一變量的讀出、常量或這些的組合選擇路徑。所述第一變量不是僅調用包含所述第一條件句的子例程的例程中為有效範圍的變量。本發明的一個實施方式中，上述第二條件句包含基於用於存儲上述第一條件式的結果的變量根據上述第一條件式的結果選擇路徑的第二條件式。本發明的一個實施方式中，上述檢索的步驟包含從上述讀出的程序代碼進一步檢索更新句的步驟，上述更新句在上述同步塊內且更新上述第一變量，上述追加的步驟包括如下步驟向從緊接上述檢索出的更新句之後到上述同步塊結束句為止之間，還追加包含用於存儲上述第一條件式的結果的變量和向該變量代入的上述第一條件式的結果的語句。在本發明的一個實施方式中，上述檢索步驟包括如下步驟從上述讀出的程序代碼和其他程序代碼的至少一個進一步檢索更新句，上述更新句在與上述同步塊同步的其他同步塊內且更新上述第一變量，上述追加的步驟包括如下步驟向從緊接上述檢索出的更新句之後到上述同步塊結束句為止之間，還追加包含用於存儲上述第一條件式的結果的變量和向該相同變量代入的上述第一條件式的結果的語句。在本發明的一個實施方式中，上述追加步驟包括如下步驟在用於存儲上述第一條件式的結果的變量首次被參照的語句之前，還追加初始化變量的語句，該變量用於使用上述第二條件句執行包含上述同步塊的路徑的值或使用上述第一條件式的結果存儲上述第一條件式的結果。在本發明的一個實施方式中，上述副作用是不容易取消執行結果的處理。在本發明的一個實施方式中，上述副作用是執行線程間的同步的處理、向實例變量代入值的處理、向類變量代入值的處理、執行輸入輸出的處理、調用本地代碼的處理或向表示排列要素的位置的編號代入值的處理。在本發明的一個實施方式中，在上述第一條件式的數量為2以上的情況下，上述2 以上的第一條件式的結果通過上述2以上的第一條件式的組合求出。
在本發明的一個實施方式中，在通過上述第一條件式選擇的路徑的數量為3條以上的情況下，用於存儲上述第一條件式的結果的變量與上述3條以上的路徑中沒有副作用的路徑分別對應。在本發明的一個實施方式中，用於存儲上述第一條件式的結果的變量是保證原子性的數據型的變量。在本發明的一個實施方式中，上述檢索步驟包括如下步驟從上述程序代碼和其他程序代碼的至少一個進一步檢索與上述同步塊同步的其他同步塊，隨著上述檢索的結束，執行上述複製步驟。在本發明的一個實施方式中，上述檢索步驟包括如下步驟還檢索包含於上述程序代碼和其他程序代碼的至少一個且從上述同步塊外的語句參照上述第一變量的語句，隨著上述檢索的結束，執行上述複製步驟。在本發明的一個實施方式中，在上述同步塊內包含啟動線程的語句的情況下，上述檢索步驟包括如下步驟還從包含於上述程序代碼和其他程序代碼的至少一個且記載上述線程的安裝的語句檢索與上述同步塊內的語句同步地執行的語句，上述方法還使計算機系統執行如下步驟根據檢索上述同步地執行的語句，將包含啟動上述線程的語句判定為具有副作用的路徑。在本發明的一個實施方式中，在上述同步塊內包含啟動線程的語句的情況下，上述檢索步驟還包括如下步驟要求用戶判斷包含啟動上述線程的語句的路徑是否是沒有副作用的路徑。在本發明的一個實施方式中，在用於確定執行上述同步塊的線程的執行順序的變量在上述同步塊內定義的情況下，上述檢索步驟包括如下步驟從上述同步塊外進一步檢索包含於上述程序代碼和其他程序代碼的至少一個且參照上述使用的變量的語句，上述方法還使計算機系統執行如下步驟根據檢索參照上述使用的變量的語句， 將包含上述使用的變量的路徑判定為具有副作用的路徑。在本發明的一個實施方式中，在用於確定執行上述同步塊的線程的執行順序的變量在上述同步塊內定義的情況下，上述檢索步驟還包括如下步驟要求用戶判斷包含上述使用的語句的路徑是否是沒有副作用的路徑。在本發明的一個實施方式中，上述追加步驟包括如下步驟向上述讀出的程序代碼還追加聲明用於存儲上述第一條件式的結果的變量的語句，在共有變量包含於上述程序代碼和其他程序代碼的至少一個且從上述同步塊外的語句被訪問的情況下，上述聲明包含抑制與存儲器的訪問順序有關的最優化的指定和保證原子性的指定，上述共有變量包含於沒有上述副作用的路徑，且能夠從多個線程被訪問，在不進行上述訪問的情況下，上述聲明包含保證原子性的指定。在本發明的一個實施方式中，上述檢索步驟還包括如下步驟允許用戶判斷是否具有與上述同步塊同步的其他同步塊。而且，上述方法使計算機系統在上述允許步驟之後執行上述複製步驟。在本發明的一個實施方式中，上述檢索步驟還包括如下步驟允許用戶判斷是否具有參照上述第一變量的語句。而且，上述方法使計算機系統在上述允許步驟之後執行上述複製步驟。在本發明的一個實施方式中，在包含於上述第二條件式的變量為指定了抑制與存儲器的訪問順序有關的最優化的變量的情況下，在還追加代入上述第一條件式的結果的語句的步驟中，在緊接上述同步塊的結束語句之前，追加代入上述第一條件式的結果的語句。本發明還提供將多線程上工作的程序的程序代碼變換為鎖衝突少的程序代碼的方法。該方法使計算機系統執行如下步驟。該步驟包括檢索步驟，向存儲器內讀出上述程序代碼，從該讀出的程序代碼檢索在同步塊內且向對該同步塊沒有副作用的路徑分支的第一條件句，沒有上述副作用是指基於上述同步塊內的語句處理中的值無法由上述同步塊外的語句參照；複製步驟，向上述同步塊外複製通過上述檢索出的第一條件句分支的沒有副作用的路徑；追加步驟，與上述複製相應地，在上述程序代碼內追加第二條件句，上述第二條件句是向上述複製的沒有副作用的路徑分支的條件句，上述第一條件句包含第一條件式，該第一條件式基於實例變量或類變量的讀出、 常量或這些的組合，在向沒有副作用的路徑分支的情況下定義為其結果變為true，另一方面，在向具有副作用的路徑分支的情況下定義為其結果變為false，上述第二條件句包含第二條件式，該第二條件式基於用於存儲上述第一條件式的結果的boolean型的變量，定義為根據上述第一條件式的結果選擇路徑。本發明還提供使計算機執行上述方法的任一種所述的方法的各步驟。本發明還提供將在多線程上工作的程序的程序代碼變換為鎖衝突少的程序代碼的計算機系統。該計算機系統包括檢索部，向存儲器內讀出上述程序代碼，從該讀出的程序代碼檢索在同步塊內且向沒有對該同步塊的副作用的路徑分支的第一條件句，沒有上述副作用是指基於上述同步塊內的語句處理中的值無法由上述同步塊外的語句參照；複製部，向上述同步塊外複製通過上述檢索出的第一條件句分支的沒有副作用的路徑；追加部，與上述複製相應地，在上述程序代碼內追加第二條件句，上述第二條件句是向上述複製的沒有副作用的路徑分支的條件句。在本發明的一個實施方式中，上述檢索部，從上述讀出的程序代碼進一步檢索更新句，上述更新句在上述同步塊內且更新上述第一變量，上述追加部，向從緊接上述檢索出的更新句之後到上述同步塊結束句為止之間， 還追加包含用於存儲上述第一條件式的結果的變量和向該變量代入的上述第一條件式的結果的語句。在本發明的一個實施方式中，上述檢索部，從上述讀出的程序代碼和其他程序代碼的至少一個進一步檢索更新句，上述更新句在與上述同步塊同步的其他同步塊內且更新上述第一變量，上述追加部，向從緊接上述檢索出的更新句之後到上述同步塊結束句為止之間，還追加包含用於存儲上述第一條件式的結果的變量和向該變量代入的上述第一條件式的結果的語句。
在本發明的一個實施方式中，上述追加部，在用於存儲上述第一條件式的結果的變量首次被參照的語句之前，還追加初始化變量的語句，該變量用於使用上述第二條件句執行包含上述同步塊的路徑的值或使用上述第一條件式的結果存儲上述第一條件式的結^ ο在本發明的一個實施方式中，上述檢索部，從上述程序代碼和其他程序代碼的至少一個進一步檢索與上述同步塊同步的其他同步塊，在本發明的一個實施方式中，上述檢索部，還檢索包含於上述程序代碼和其他程序代碼的至少一個且從上述同步塊外的語句參照上述第一變量的語句，在本發明的一個實施方式中，在上述同步塊內包含啟動線程的語句的情況下，上述檢索部，還從包含於上述程序代碼和其他程序代碼的至少一個且記載上述線程的安裝的語句檢索與上述同步塊內的語句同步地執行的語句，上述計算機系統還包括判定部，該判定部根據檢索上述同步地執行的語句，將包含啟動上述線程的語句判定為具有副作用的路徑。在本發明的一個實施方式中，在上述同步塊內包含啟動線程的語句的情況下，上述檢索部還包括判斷部，該判斷部允許用戶判斷包含啟動上述線程的語句的路徑是否為沒有副作用的路徑。在本發明的一個實施方式中，在用於確定執行上述同步塊的線程的執行順序的變量在上述同步塊內定義的情況下，上述檢索部，從上述同步塊外進一步檢索包含於上述程序代碼和其他程序代碼的至少一個且參照上述使用的變量的語句，上述計算機系統還包括判定部，該判定部根據檢索參照上述使用的變量的語句， 將包含啟動上述使用的變量的路徑判定為具有副作用的路徑。在本發明的一個實施方式中，在用於確定執行上述同步塊的線程的執行順序的變量在上述同步塊內定義的情況下，上述檢索還包括判斷部，該判斷部允許用戶判斷包含上述使用的變量的路徑是否為沒有副作用的路徑。在本發明的一個實施方式中，上述追加部，向上述讀出的程序代碼還追加聲明用於存儲上述第一條件式的結果的變量的語句，在共有變量包含於上述程序代碼和上述其他程序代碼的至少一個且從上述同步塊外的語句被訪問的情況下，上述聲明包含抑制與存儲器的訪問順序有關的最優化的指定和保證原子性的指定，上述共有變量包含於沒有上述副作用的路徑，且能夠從多個線程被訪問，在不進行上述訪問的情況下，上述聲明包含保證原子性的指定。在本發明的一個實施方式中，上述檢索部還包括判斷部，該判斷部允許用戶判斷是否具有與上述同步塊同步的其他同步塊。在本發明的一個實施方式中，上述檢索步驟還包括判斷部，該判斷部允許用戶判斷是否具有參照上述第一變量的語句。根據本發明的實施方式，從同步塊中的第一路徑中自動發現雖然沒有獲得鎖但能夠執行的第二路徑。而且，該發現的第二路徑和用於不獲得鎖而執行第二路徑的條件句追加到程序代碼中的上述第一路徑之外。通過上述追加，程序代碼執行時的鎖衝突時間減少， 能夠防止多線程上的CPU效率的降低。


圖1示出本發明實施方式中的、表示用於變換程序代碼的系統具有的功能的功能框圖。圖2示出本發明實施方式中的、圖1所示的變換之前的程序代碼的例。圖3示出本發明實施方式中的、在圖1所示的變換程序中執行的處理步驟中取得變換所需的信息的處理步驟的例。圖4示出本發明實施方式中的、在圖1所示的變換程序中執行的處理步驟中進行變換的處理步驟的例。圖5示出本發明實施方式中的、圖4所示的步驟317的處理的詳細情況。圖6示出本發明實施方式中的、用於具體說明圖3 圖5所示的各步驟的工作所使用的輸入數據CL。圖7示出本發明實施方式中的、圖4所示的步驟316的處理被執行後的方法 dequeue 0圖8示出本發明實施方式中的、對圖6執行圖3 圖5所示的步驟的處理後的輸入數據(變換後的程序代碼)。圖9示出本發明實施方式中的、用於具體說明圖3 圖5所示的各步驟的工作所使用的輸入數據CL。圖10示出本發明實施方式中的、圖4所示的步驟316的處理被執行後的方法 dequeue 0圖11示出本發明實施方式中的、對圖9執行圖3 圖5所示的各步驟的處理的輸入數據(變換後的程序代碼)。圖12示出本發明實施方式中的、由第一條件句選擇的路徑為三條以上的情況下的、圖3 圖5所示的各步驟的處理被執行前的程序代碼的一部分和被執行後的程序代碼的一部分。圖13示出本發明實施方式中的、圖1的系統具有的計算機硬體的框圖。
具體實施例方式在本發明的實施方式中，「在多線程上工作的程序的程序代碼」是指生成多個被稱為線程的處理單位，按每個該生成的線程分配CPU時間，由此能夠並行地進行多個處理的程序的原始碼。該原始碼例如使用Java(商標)語言或C++語言記述。在本發明的實施方式中，「鎖」是指當在一個線程執行處理時在其他線程不執行上述處理本身和與上述處理相關的處理。例如，在第一線程開始上述鎖的對象的處理的情況下，在第二線程不執行上述處理或與上述處理有關的處理。上述第二線程中的上述處理或與上述處理有關的處理等待直到上述第一線程中的處理結束，在上述結束後可以執行。在本發明的實施方式中，「鎖衝突」是指以下狀態由於在一個線程執行的處理為鎖的對象，在其他線程執行的上述處理自身以及與上述處理有關的處理等待執行直到在上述第一線程執行的處理結束。此外，「鎖衝突少」表示鎖衝突發生的頻度少以及由鎖衝突引起的上述執行等待的時間短。使用本發明的實施方式變換的程序代碼與變換前的程序代碼相比，鎖衝突變少。在本發明的實施方式中，「同步塊」是記載有作為上述鎖的對象的處理的程序代碼上的語句。該程序代碼上的語句由同步塊的開始句、同步塊的結束句以及由上述開始句和結束句包圍的語句構成。同步塊的開始句在上述程序代碼由例如Java(商標)語言記載的情況下，例如為記載synchronized聲明的語句或記載由synchronized修飾符修飾的方法名的語句。同樣地，在上述程序代碼通過例如Java (商標)語言記載的情況下，同步塊的結束句為表示上述開始句的結束位置的「} 」。子例程的調用包含於由上述開始句和結束句包圍的語句(即同步塊內)的情況下，記載該子例程的安裝的語句可以包含於上述同步塊內。為了在記載該子例程的安裝的語句中包含其他子例程的調用，子例程的調用成為階層狀的情況下，記載所有子例程的安裝語句可以進一步包含於上述同步塊。在此，子例程例如是方法。在本發明的實施方式中，「與同步塊同步的其他同步塊」是例如通過作為鎖的對象的處理被訪問的變量通用或指定的鎖對象通用的同步塊。在此，鎖對象是在Java(商標) 語言的synchronized聲明中指定的變量。例如，在聲明第一同步塊的synchronized聲明中指定鎖對象lock且在聲明第二同步塊的synchronized聲明中指定鎖對象lock的情況下，第二同步塊是與第一同步塊同步的其他同步塊。此外，在第一同步塊是方法且聲明第二同步塊的synchronized聲明中指定表示上述方法的this的情況下，第二同步塊是與第一同步塊同步的其他同步塊。在本發明的實施方式中，「對同步塊的副作用」是基於同步塊內的語句的處理(處理A)的結果能夠由基於同步塊外的語句的處理(處理B)參照的處理A。對同步塊的副作用還是不容易取消處理結果的處理。對同步塊的副作用是例如記載在同步塊內的其他同步塊內的處理、向實例變量代入值的處理、向類變量代入值的處理、執行輸入輸出的處理、調用本地代碼中包含的處理的處理、或向表示排列要素的位置的編號代入值的處理，但不限定於這些。上述副作用通過例如用戶在列表中登記關於上述處理的語句，計算機系統參照在該列表中登記的語句進行判斷。上述輸入輸出，例如是向畫面、文件或網絡的輸入輸出，但不限於這些。此外，上述本地代碼是由機器語言記載的程序。本地代碼例如是彙編完成的程序。包含於本地代碼的處理例如由 Java Native Interface(JNI)調用。在本實施方式中，「沒有對同步塊的副作用」是基於同步塊內的語句的處理中的值無法由上述同步塊外的語句參照。沒有副作用是指不是引起副作用的處理，例如不是記載在同步塊內的其他同步塊內的處理、向實例變量代入值的處理、向類變量代入值的處理、執行輸入輸出的處理、調用本地代碼中包含的處理的處理、或向表示排列要素的位置的編號代入值的處理的任何一種。在本實施方式中，「路徑」是與在程序執行時執行的處理對應的程序代碼上的一系列語句。該語句可以是0。在本發明的實施方式中，「對同步塊沒有副作用的路徑」是與在程序執行時對上述同步塊沒有副作用的處理對應的上述一系列語句。在本發明的實施方式中，「條件句」是在程序中用於實現處理的分支的記載在程序代碼上的語句。條件句包括條件式。條件句也可以包含表示選擇的路徑的範圍的記號。程序代碼例如由Java(商標)記載的情況下，上述記號是例如「 {」和「} 」。條件句根據條件式的結果選擇執行的路徑。程序代碼例如由Java (商標)記載的情況下，條件句例如是if語句或switch語句。在本發明的實施方式中，「條件句」是用於選擇路徑使用的式子。條件式包含變量、 常量以及運算符的至少一個。條件句例如為if語句的語句「if (X == 0) {y = 1 ;} 」的情況下，條件式為「(X = = 0) 」。此外，條件句例如為switch語句或select case語句的情況下，將與兩句相關的case的值和存儲該值的變量進行比較的式子作為條件式。條件句例如為 switch 語句(switch(χ) {case 1 :y = 1 ；break ；})的情況下，條件式為「 (x == 1)，，。對於一個條件句，條件式的數量不一定是一個。(1)條件句例如為if語句的語句"if(x == 0) {y = 0 ；}else if (χ == 1) {y = 1 ；}else {y = 2}，，的情況下，"(χ = =0)」、「(χ== 1)」以及「其他」的至少一個可以為條件式。此外，可以組合從多個條件式例如「(χ == 0) 」、「 (χ== 1) 」以及「其他」選擇的兩個以上作為新的條件式。在此，所謂組合是將上述條件式之間例如進行邏輯運算。(2)條件句例如為switch語句
(switch ( χ) { case 1: y=l; break; case 2: y=2; break;
default: y=3; break; })的情況下，「(χ== 1)」、「(χ ==2)」以及「其他」的至少一個可以為條件式。此外，可以組合從多個條件式例如「(X == 1) 」、「 (χ ==2)，，以及「其他」選擇的兩個以上作為新的條件式。在本發明的實施方式中，「第一變量」是用於使第一條件式選擇路徑的一個變量。 「第一變量」例如至多是一個變量。程序代碼例如由Java語言記載的情況下，第一變量是一個實例變量或一個類變量。在本發明的實施方式中，「第一條件式的結果」是通過第一條件式或多個第一條件式的組合表示的值。(1)條件句例如是if語句的情況下，第一條件式的結果例如用真或假表示。上述真或假可以用與記載程序代碼的語言的上述條件式的方式相配合的值表達，或可以用用戶確定的值表達。例如，可以將表示真的值設為true，表示假的值設為false，或者表示真的值設為0，表示假的值設為-1。上述表示真或假的值是true或false的情況下，用於存儲第一條件式的結果變量例如是boolean型。上述表示真或假的值是0或-1的情況下，用於存儲第一條件式的結果變量例如是支持負值的數值型。此外，if語句包含例如elseif語句所以在上述if語句中具有多個第一條件式的情況下，第一條件式的結果可以組合通過多個第一條件式表示的值求出。上述組合是例如對表示條件式的值之間進行邏輯運算。(2)條件句例如是switch語句的情況下，第一條件式的結果例如通過表示在 switch語句中指定的變量是case句指定的值的值(以下為示值)或與該示值對應的值表示。上述示值例如可以是由上述case句指定的值。上述對應的值例如是用戶確定的值。用戶在上述對應的值例如使用連續編號。將上述示值作為第一條件式的結果的情況下，用於存儲第一條件式的結果的變量是例如與上述指定的變量相同的數據型。此外，第一條件式的結果可以組合多個上述示值或多個上述對應的值求出。上述組合是例如根據上述示值或上述對應的值所取的範圍進行分組。在本發明的實施方式中，「保證原子性的數據型變量」是通過一次操作執行向存儲器讀入變量的數據型的變量，是根據記載程序代碼的語言的方式保證該執行的數據型變量。上述語言例如為Java (商標)語言且上述程序代碼在32位以上的OS上執行的情況下，例如boolean型、byte型、short型、int型或float型為保證原子性的數據型。在本發明的實施方式中，「其他程序代碼」是從變換前的程序代碼連結的程序代碼。在此，連結是指例如調用或共有變量，但不限於此。此外，其他程序代碼是通過本發明的實施方式能夠解析的程序代碼。其他程序代碼是例如原始碼或字節碼。在本發明的實施方式中，「抑制與存儲器的訪問順序有關的最優化」是彙編變換前的程序代碼時，不通過彙編進行與存儲器的訪問順序有關的最優化。例如在變換前的程序代碼用Java(商標)記載的語言的情況下，抑制最優化的指定用修飾符volatile修飾變量。下面按照

本發明的實施方式。本實施方式用於說明本發明的優選方式， 可以理解為沒有意圖將本發明的範圍限定於此處所示例。此外，下面的附圖中，只要不是特別說明，相同的標號表示相同的對象。圖1示出本發明實施方式中的表示用於變換程序代碼的系統具有的功能的功能框圖。計算機系統(101)包括存儲器(102)、檢索部(103)、複製部(104)、追加部 (105)、判定部(106)以及判斷部(107)。此外，存儲部(108)可以包含於計算機系統(101)， 或包含於其他系統。計算機系統(101)從存儲部(108)向存儲器內(102)讀出變換前的程序代碼
(109)。在此，計算機系統(101)可以從存儲部(108)向存儲器內(10 讀出其他程序代碼
(110)。檢索部(103)檢索向上述存儲器讀出的程序代碼(109)以及任意其他程序代碼 (110)。通過該檢索，檢索部(10 檢索在同步塊內的第一條件句、更新句、與同步塊同步的其他同步塊、參照來自同步塊外的語句的第一變量的語句、記載與啟動線程的同步塊內的語句同步地執行的其他線程的安裝的語句、或參照用於確定線程的執行順序的變量的語句。檢索部(103)包括判斷部(107)。
判斷部(107)在用於上述檢索的信息不充分的情況下，允許用戶輸入該信息。判斷部(107)還為了進一步限定上述檢索的條件允許用戶輸入該條件。判定部(106)從檢索部(10 接收檢索結果。判定部(106)根據上述檢索結果判定程序代碼(109)中的沒有副作用的路徑。複製部(104)將上述判定的沒有副作用的路徑複製到程序代碼(109)的同步塊外。追加部(10 將向上述複製的沒有副作用的路徑分支的第二條件句追加到向上述存儲器讀出的程序代碼(109)。追加部(10 還將包含用於存儲第一條件式的結果的變量和代入該變量的上述第一條件式的結果的語句、初始化該變量的語句或聲明該變量的語句追加到向上述存儲器讀出的程序代碼(109)。圖2示出本發明的實施方式中的圖1所示的變換前的程序代碼。程序代碼(200)是變換前的程序代碼。下面以該程序代碼(200)為例說明說明書中記載的各用語。與「類」對應的語句是滿足格式「class類名{類的安裝}」的語句。因此，在變換前的程序代碼O00)中與「類」對應的語句是類WQ01A)以及類W201B)。與「方法」對應的語句是滿足格式「返回值方法名(參數型參數名)方法的安裝}，， 的語句。因此，在變換前的程序代碼O00)中與「方法」對應的語句是方法enqUeUe(WW) (202A)以及dequeue (202B)。此外，在方法內記載的語句中包含其他的方法調用的情況下，記載該其他的方法的安裝的語句也作為在上述同步方法內記載的語句處理。與「同步塊」對應的語句例如是進行了 synchronized塊的聲明的語句或指定了 synchronized修飾符的方法。因此，在變換前的程序代碼Q00)中與「同步塊」對應的語句是第一同步塊(203A)、第二同步塊Q03B)以及第三同步塊O03C)。「同步塊的鎖對象」是例如通過上述synchronized塊的聲明或指定了上述 synchronized修飾符的方法的參數指定的變量。因此，第一同步塊Q03A)的鎖對象是 w(204A)o第二同步塊Q03B)的鎖對象是lOcH204B)。第三同步塊Q03C)的鎖對象是 lock(204C)。此外，記載在同步塊內的語句中包含方法調用的情況下，記載該方法的安裝的語句也作為記載在上述同步塊內的語句處理。與「條件句」對應的語句是例如「IF」語句、「SWITCH」語句或記載有「三元運算子」 的語句。因此，在變換前的程序代碼(200)中與「條件句」對應的語句是第一條件句(205A)、 第二條件句(205B)、第三條件句Q05C)以及第四條件句O05D)。「條件式」是包含於條件分支句用於選擇執行路徑的式子。因此，第一條件句 (205A)的條件式是w. val = = nulK206A)。第二條件句O05B)的條件式是head = = null(206B)o第三條件句(205C)的條件式是head ！ = null(206C)o第四條件句(205D) 的條件式是 w. next == w (206D)。在執行了程序代碼000)的情況下，與「路徑」對應的語句是存在處理的可能性的語句。例如，方法enqueue (Ww) (202A)被執行結束之前的路徑是路徑(207A)，以及方法 dequeue (202B)被執行結束之前的路徑是路徑O07B)。此外，條件句被執行結束之前的路徑是從開始各自的分支處理的語句到結束各自的分支處理的語句。(1)對於第一條件句Q05A)，在從方法enqueue (Ww) (202A)退出的處理(208A和 208B)的下一語句中結束各自的分支的處理。因此，第一條件句O05A)被執行結束之前的路徑是在條件式O06A)成立時執行的路徑Q09A)以及在條件式Q06A)不成立時執行的路徑(209B)。(2)第二條件句(205B)具有與 「 if (head == null) {w. next = w ;} else {w. next =head ；}」相同的意思。因此，在將w或head代入w. next的處理的下一語句中結束各自的分支的處理。因此，第二條件句O05B)被執行結束之前的路徑是在條件式O06B)成立時執行的路徑(w. next = w；)以及在條件式Q06B)不成立時執行的路徑(w. next = head ；)。⑶對於第三條件句(205C)，在從方法dequeue (202B)退出的處理(208C和 208D)的下一語句結束各自的分支的處理。因此，第三條件句O05C)被執行結束之前的路徑是在條件式O06C)成立時執行的路徑Q09C)以及在條件式Q06C)不成立時執行的路徑(209D)。(4)第四條件句 Q05D)具有與「if (w. next = = w) {head = null ；} else {head = w. next ；}」相同的意思。因此，在將null或w. next代入head的處理的下一語句中結束各自的分支的處理。因此，第四條件句O05D)被執行結束之前的路徑是在條件式O06D) 成立時執行的路徑(head = null ；)以及在條件式Q06D)不成立時執行的路徑(head = w. next ；) ο「第一變量」是用於判斷分支的變量。因此，第一條件句O05A)的第一變量是 w. val(210A)o第二條件句(205B)的第一變量是headQlOB)。第三條件句(205C)的第一變量是heacK210C)。第四條件句(205D)的第一變量是w. next Q10D)。「更新句」是包含上述第一變量的同步塊內的語句，是更新上述第一變量的語句。更新w.vaK210A)的更新句不包含於包含w. val O10A)的第一同步塊Q03A)。更新 head(210B)的更新句是更新句QllB)。更新headQlOC)的更新句是更新句QllC)。更新 w. next(210D)的更新句是更新句QllD)。圖3 圖5示出本發明實施方式的圖1所示的變換程序中執行的處理步驟的例子。下面以變換前的程序代碼是用Java(商標)語言記載的程序代碼的情況為例進行說明。計算機系統(101)將變換前的程序代碼(下面稱為CL)設為輸入數據。計算機系統除了該CL之外，還可以將從上述CL連結的其他程序代碼(下面稱為其他CL)作為輸入數據。在此，輸入數據是能夠從上述變換程序參照的數據。圖3是本發明實施方式的圖1所示的變換程序中執行的處理步驟中取得變換所需的信息的處理步驟的例子。步驟301是上述變換處理的開始。在步驟301中，計算機系統將上述輸入數據例如讀入存儲器。隨著該讀入結束，該處理進入步驟302。在步驟302中，計算機系統準備用於存儲用於上述變換的信息的變量i、集合變量 M、集合變量S以及集合變量C。變量i是存儲用於識別在下述步驟315中聲明的變量(下面為第二變量)的變量。變量i例如使用向上述第二變量分配的連續編號。也可以不準備變量。在不準備變量i的情況下，計算機系統在每次聲明第二變量時對第二變量標註能夠唯一識別的變量名。上述能夠唯一識別的變量名可以例如由用戶確定，也可以不重複地隨機確定。集合變量是用於集合具有不同意思的數據進行處理的組。集合變量例如用排列或構造體表示。集合變量M按上述每個方法存儲關於執行上述CL時處理能夠到達的方法的信息的集合變量。上述方法的信息，是能夠從程序代碼確定記載對應的方法的安裝的語句即可。 關於上述方法的信息例如是記載方法的安裝的語句的開始位置、記載方法的安裝的語句的結束位置或者記載方法的安裝的語句，但不限於這些。集合變量S按上述每個同步塊設定關於分別執行上述方法時處理能夠到達的同步塊的信息的集合變量。關於上述同步塊的信息是同步塊的鎖對象(下面為S的第一信息)、同步塊的程序代碼上的開始結束位置(下面為S的第二信息)以及同步塊內的語句 (下面為S的第三信息)。集合變量C是按每個上述執行路徑設定關於包含於各上述同步塊的滿足預定條件的執行路徑的信息的集合變量。關於上述執行路徑的信息，是與上述執行路徑對應的上述同步塊的鎖對象(下面為C的第一信息)、與上述執行路徑對應的上述同步塊的程序代碼上的開始結束位置(下面為C的第二信息)以及能夠從程序代碼確定的上述執行路徑的信息(下面為C的第三信息)。上述C的第三信息例如是執行路徑的開始位置、執行路徑的結束位置、或記載執行路徑的語句，但不限於此。計算機系統在變量i、集合變量S和集合變量C的上述準備中向該變量i、該集合變量S和該集合變量C設定初始值。上述初始值例如是表示空的值。計算機系統例如設定 0或1作為變量i的初始值。此外，集合變量S和C例如是包含數值型變量和文字型變量的構造體的情況下，計算機系統例如向數值型變量的初始值設定0，向文字型變量的初始值設定NULL作為集合變量S和C的初始值。計算機系統還在集合變量M的上述準備中向上述集合變量M設定關於上述方法的信息。計算機系統檢索包含於CL的方法，將關於檢索出的方法的信息設定到集合變量M。 在上述檢索中，可以預先由用戶指定設為對象的方法，可以檢索包含於CL的所有方法。通過執行包含於CL的方法能夠到達的方法例如可以從上述其他CL檢索。此外，可以代替上述檢索，由用戶向集合變量M設定關於上述方法的信息。隨著上述準備結束，該處理進入步驟303。步驟303中，表示關於集合變量M的反覆開始。步驟303中，計算機系統從集合變量M取出一件關於方法的信息(下面為m)。隨著該取出結束，該處理進入步驟304。在步驟304中，計算機系統向集合變量S設定數據。計算機系統檢索與上述取出的m對應的方法被執行時處理能夠到達的同步塊。 在上述方法自身是同步塊的情況下，上述方法自身也成為被檢索的同步塊。CL例如是 Java(商標)記載的程序代碼的情況下，計算機系統例如從上述CL檢索「synchronized」。 在與m對應的方法由「synchronized」修飾的情況下，上述修飾的「synchronized」也還是被檢索的 「synchronized，，。
計算機系統從該檢索出的同步塊取得關於上述檢索的同步塊各自的、鎖對象(S 的第一信息)、程序代碼上的開始結束位置(S的第二信息)以及同步塊內的語句(S的第三信息)，按每個同步塊向集合變量S設定該取得的S的第一 第三信息作為一組信息。關於在檢索的同步塊中已經檢索而設定了信息的同步塊，不需要進行上述設定。隨著結束上述設定，該處理進入步驟305。步驟305表示關於集合變量M的反覆的結束。在所有m取出完成的情況下，該處理進入步驟306。在存在未取出的m的情況下， 該處理返回步驟303。步驟306表示關於集合變量S的反覆的開始。步驟306中，計算機系統從集合變量S取出一件關於同步塊的上述一組信息(下面為s)。隨著該取出結束，該處理進入步驟307。在步驟307中，計算機系統判定在向與上述取出的s對應的集合變量S設定的同步塊內的語句(下面為s的第三信息)中是否包含沒有發生副作用的路徑。該判定在包含於同步塊內的語句(s的第三信息)路徑且關於各執行的路由的路徑(下面為執行路徑) 的全部中執行。在該判定中，計算機系統例如判定引起記載在下述副作用列表的副作用的原因是否包含於上述執行路徑。副作用列表例如預先由用戶製作。用戶預先將引起副作用的原因例如方法或變量登記到副作用列表。方法例如是關於I/O的方法或JOT的方法。變量例如是實例變量或類變量。計算機系統在上述判定中，在上述執行路徑中例如發現了向上述方法或變量寫入的情況下，將上述執行路徑判定為發生副作用的路徑，在沒有發現的情況下，將上述執行路徑判定為沒有發生副作用的路徑。上述登記可以自動地通過計算機系統執行。計算機系統例如在步驟302中從上述CL或上述其他CL的至少一個取得引起副作用的原因，將該取得的引起副作用的原因登記到副作用列表。此外，計算機系統通過調查包含於執行路徑的變量的種類能夠執行上述判定。計算機系統例如通過調查上述變量的聲明記載在上述CL的何處或上述變量的範圍設定在CL 上的哪個範圍，能夠執行上述判定。在上述執行路徑中存在沒有發生副作用的路徑的情況下，該處理進入步驟308。在上述執行路徑全部是發生副作用路徑的情況下，該處理進入步驟310。在步驟308中，計算機系統判定不發生上述副作用的執行路徑和用於執行該執行路徑的條件句是否滿足以下條件。上述條件是上述執行路徑包含實例變量或類變量的至多一個的讀出，上述條件句評價該讀出和常量。在滿足條件的條件句存在即使一個的情況下，該處理進入步驟309。在滿足條件的條件句不存在的情況下，該處理進入步驟310。在步驟309中，計算機系統關於通過滿足上述條件的條件句執行的各路徑，分別將作為上述S的第一信息的鎖對象(C的第一信息)、作為上述S的第二信息的程序代碼上的開始結束位置(C的第二信息)、以及能夠從程序代碼確定通過滿足上述條件的條件句執行的執行路徑的信息(C的第三信息)向集合變量C設定作為一組信息。隨著上述設定的結束，該處理進入步驟310。在所有s取出完成的情況下，該處理進入步驟311。在存在未取出的s的情況下，該處理返回步驟306。圖4示出本發明實施方式中的、圖1所示變換程序中執行的處理步驟中進行變換的處理步驟的例子。步驟311示出關於集合變量C的反覆的開始。在步驟311中，計算機系統從集合變量C取出一件關於執行路徑的上述一組信息 (下面為c)。計算機系統從關於通過程序代碼早執行的執行路徑的信息起依次進行上述取出。隨著該取出結束，該處理進入步驟312。在步驟312中，計算機系統判定向與上述取出的c對應的集合變量C設定的鎖對象(下面為c的第一信息)是否僅在CL內使用。在該判定中，例如在CL用Java(商標) 語言記載的情況下，檢查在鎖對象(c的第一信息)的定義使用private修飾符或在上述其他CL中不包含使用上述鎖對象(c的第一信息)的記載。通過該檢查，在鎖對象(c的第一信息)的定義使用了 private修飾符或在上述其他CL中不包含使用上述鎖對象(c的第一信息)的記載的情況下，計算機系統判定鎖對象(c的第一信息)僅在CL內使用。在此，例如，由於沒有給予上述其他CL作為輸入數據或提供上述其他CL作為二進位數據使得原始碼的記載不明的理由，存在無法執行上述檢查的情況。在無法執行上述檢查的情況下，計算機系統例如可以判定為鎖對象(c的第一信息)不是僅在CL內使用。此外，計算機系統例如可以使監控器顯示用於進行上述判定的信息，使用戶進行上述判定。在僅在CL內使用的情況下，該處理進入步驟314。在CL外也使用的情況下，該處理進入步驟313。步驟313中，計算機系統判定執行與上述c對應的集合變量C的第三信息(下面為c的第三信息)所對應的路徑的條件句中包含的所有變量是否僅在CL內定義。該判定中檢查在上述其他CL中不包含上述參照的變量的定義。通過該檢查，在上述其他CL中不包含上述參照的變量的定義的情況下，計算機系統判定為參照的變量僅在CL內定義。在此， 例如，由於沒有給予上述其他CL作為輸入數據或提供上述其他CL作為二進位數據使得原始碼的記載不明的理由，存在上述檢查無法執行的情況。在無法執行上述檢測的情況下，計算機系統例如可以判定為上述參照的變量不是僅在CL內定義。此外，計算機系統例如可以使監控器顯示用於進行上述判定的信息，使用戶進行上述判定。在僅在CL內定義上述參照的變量的情況下，該處理進入步驟314。在並非僅在CL內定義上述參照的變量的情況下，該處理進入步驟318。在步驟314中，計算機系統向CL內追加聲明變量(下面為第二變量)的語句。上述追加的情況下，根據記述CL的程序語言的規格而不同。第二變量的聲明是保證原子性的數據型、能夠指定靜態的而且抑制最優化的數據型的第二變量的聲明。在此，保證原子性根據語言規格保證用一次操作執行向存儲器讀入變量。如果是Java(商標)語言，例如boolean 型、byte型、short型、int型或float型是大小在32位以下的數據型，是例如在32位以上的CPU上執行用上述Java (商標)語言記載的程序的情況下，保證用一次操作執行向存儲器讀入變量的數據型。靜態的是指在CL內僅具有一個實體。例如，在Java(商標)語言的情況下，變量是靜態可以用修飾符static指定。此外，抑制最優化是指例如抑制在彙編中程序代碼進行與存儲器的訪問順序有關的最優化。例如，在Java(商標)語言的情況下，抑制變量的最優化可以用修飾符volatile指定。通過導入volatile聲明，保證存儲器命令和向同步塊外變更的可視性。
第二變量的變量名只要是不與其他變量重複的名字，可以是任意名字。該名字例如可以通過包含變量i識別。CL如果是用作為第二變量能夠使用排列的語言記載的程序代碼，則上述名字可以是將變量i作為添標的排列。在上述第二變量的聲明中，聲明第二變量是靜態變量。此外，從向S設定了信息的同步塊內的語句以外訪問與上述c的第三信息對應的路徑中包含的共有變量的情況下，在上述第二變量聲明中，還聲明上述第二變量是抑制最優化的對象的變量。在此，共有變量是具有從多個線程訪問的可能性的變量。在記述CL的程序語言是Java(商標)語言的情況下，上述共有變量是實例變量和類變量。上述訪問通過詳查例如CL或上述其他CL求出。在此，例如，由於沒有給予上述其他CL作為輸入數據或提供上述其他CL作為二進位數據使得原始碼的記載不明的理由，存在無法執行上述詳查的情況。在無法執行上述詳查的情況下， 計算機系統可以從同步塊的外側訪問共有變量。此外，計算機系統例如可以在監控器顯示使用戶判斷是否從同步塊的外側訪問共有變量的信息，使用戶進行上述判斷。隨著上述追加結束，該處理進入步驟315。在步驟315中，計算機系統從執行與上述c的第三信息對應的執行路徑的條件句製作語句。上述製作的語句在用於執行上述執行路徑的條件成立時和條件不成立時分別將不同的值代入上述第二變量的語句。例如，上述第二變量是boolean型的變量bl，上述條件句的條件式是(χ ！= null)的情況下，上述製作的語句可以設為「bl = (χ ！=皿11)； 」。在其他例子中，上述第二變量是int型的變量il，上述條件句的條件式是(y ==0)的情況下，上述製作的語句例如可以設為 「if(y == 0) {il = 0 ;} else {il = = 1 ;}；，，。此外，上述條件句例如是分支為三條以上的路徑的條件句「if (χ == 0) {if (y = =0) {χ++ ；y-} else {c2++ ；}}else {cl++ ；} (cl和c2都是局部變量)」的情況下，上述製作的語句例如可以設為「b = (χ ！ == 0) ？! (y ！ = = 0) ？ 2:0 ； 」。在此，代入變量b的值表示從不具有副作用的路徑中選擇哪一個。在上述例中，製作b為1的情況下選擇執行 "cl++ ；，，的路徑，b為2的情況下選擇執行「c2++ ；，，的路徑的語句。然後計算機系統在上述條件式中包含實例變量的情況下，從上述第二變量的聲明刪除為上述靜態變量的聲明。例如在Java(商標)語言的情況下，上述刪除是刪除修飾符 static。隨著結束上述刪除，該處理進入步驟316。在步驟316中，計算機系統將與上述c的第三信息對應的路徑複製到緊接用上述c 的第二信息表示的CL上的同步塊的開始位置之前。然後計算機系統在上述第二變量的值為成立值的情況下開始從上述追加的執行路徑的處理，另一方面在上述第二變量的值是不成立值的情況下將開始從上述同步塊的處理的條件句追加到CL上。上述條件句的終端，在值為成立值的情況和值為不成立值的情況下都在緊接用上述c的第二信息表示的CL上的同步塊的結束位置之後。隨著結束上述條件句的追加，該處理進入步驟317。在步驟317中，計算機系統執行關於與上述c的第三信息對應的執行路徑有關的同步塊的處理。關於該處理，將在下述圖5中詳細描述。關於上述同步塊的處理，可以向CL 追加新的語句。此外，關於上述同步塊的處理中，可以刪除在步驟314和316中向CL追加的語句。隨著關於上述同步塊的處理結束，該處理進入步驟318。步驟318表示關於集合變量C的反覆的結束。在所有c完成取出的情況下，該處理進入步驟319。存在沒有取出的c的情況下， 該處理返回步驟311。在步驟319中，計算機系統關於第二變量，在聲明上述第二變量的語句與上述第二變量對應的上述步驟314和316向CL追加的語句或與上述第二變量對應的同步塊的語句且最早執行的語句之間，追加向上述第二變量設定初始值的語句。設定上述初始值的語句是在步驟315中生成的語句。在此，上述初始值可以是上述不成立值。上述語句的追加對定義的所有第二變量執行。隨著上述追加的結束，該處理進入步驟320。步驟320是上述變換處理的結束。圖5示出本發明實施方式的圖4所示的步驟317的處理的詳細情況。步驟321示出步驟317的處理的開始。步驟322中，計算機系統從集合變量S取出一件關於方法的信息(s)。隨著該取出結束，該處理進入步驟323。在步驟323中，計算機系統判定上述c的第一信息即鎖對象和上述s的第一信息即鎖對象是否相同。在相同的情況下，該處理進入步驟324。在不同的情況下，該處理進入步驟幻9。在步驟324中，計算機系統判定由上述s的第三信息表示的同步塊中是否包含更新在步驟315中製作的語句中包含的變量的語句。在包含上述更新的語句的情況下，該處理進入步驟325。在不包含上述更新的語句的情況下，該處理進入步驟329。在步驟325中，計算機系統判定在由上述s的第三信息表示的同步塊中是否包含啟動使用上述c的第一信息即鎖對象取得鎖的線程的語句。該判定通過計算機系統詳查上述同步塊執行。在上述詳查中，存在發現使上述鎖對象在上述同步塊內使用的語句(下面為第一語句)的情況。上述第一語句例如是將上述鎖對象作為參數的方法。在發現了上述第一語句的情況下，計算機系統例如詳查上述其他CL，求出通過上述第一語句執行的執行路徑。計算機系統通過詳查上述求出的執行路徑，能夠發現啟動線程的語句。通過上述詳查沒有發現啟動上述線程的語句的情況下，該處理進入步驟326。在發現了的情況下，該處理進入步驟328。在此，例如由於沒有給予上述其他CL作為輸入數據或提供上述其他CL作為二進位使得原始碼記載不明的理由，存在無法執行上述詳查的情況。在無法執行上述詳查的情況下，計算機系統可以判定為啟動上述線程的語句包含於與上述c的第三信息對應的執行路徑。此外，計算機系統例如在監控器顯示輸入是否包含啟動上述線程的語句的信息，使用戶進行上述判定。在步驟326中，計算機系統判定與上述s的第三信息對應的同步塊內定義的變量是否在上述同步塊外參照且用於線程間的執行排序。該判定通過計算機系統詳查上述程序代碼執行。通過上述詳查，在沒有發現上述變量的情況下，該處理進入步驟327。在發現了的情況下，該處理進入步驟328。在此，例如，由於沒有給予上述其他CL作為輸入數據或提供上述其他CL作為二進位使得原始碼記載不明的理由，存在無法執行上述詳查的情況。在無法執行上述詳查的情況下，計算機系統可以判定為上述變量包含於與上述c的第三信息對應的執行路徑。此外， 計算機系統例如在監控器顯示輸入是否包含上述變量的信息，使用戶進行上述判定。在步驟327中，計算機系統向CL追加在步驟315中製作的語句。在此，第二變量為指定了抑制變量的最優化的變量的情況下，上述追加對與s對應的同步塊執行。此外，上述追加的CL上的位置在緊接用於從與上述s對應的同步塊退出的語句之前。第二變量為沒有指定抑制變量的最優化的變量的情況下，上述追加的CL上的位置為在上述步驟3M發現的上述更新的語句之後，在退出與上述s對應的同步塊的處理之
、r -刖。隨著上述追加結束，該處理進入步驟329。在步驟328中，計算機系統在步驟314和316中刪除向CL追加的語句。隨著上述刪除結束，關於步驟322的反覆結束，該處理進入步驟330。步驟3 表示關於集合變量S的反覆的結束。在所有s取出完成的情況下，計算機系統使變量i遞增。隨著該遞增結束，該處進入步驟330。在存在未取出的s的情況下，該處理返回步驟322。步驟330表示步驟317的處理的結束。在下述圖6 圖8以及圖9 圖11中示出圖3 圖5的各步驟的工作的具體例。圖6示出本發明的實施方式中的、用於具體說明圖3 圖5所示的各步驟的工作的輸入數據CL。圖6 圖8所示的例子表示步驟325和步驟326中向用戶進行詢問的情況。計算機系統將輸入數據001)作為輸入數據CL啟動變換程序。在步驟302中，計算機系統向變量設定以下的值。集合變量 M= {void enqueue (Ww) public W dequeue }變量i = 1集合變量S = { Φ }集合變量C= {φ}隨著上述設定結束，該處理進入步驟303。步驟303 步驟305的反覆中，計算機系統對m = "Boolean enqueue (Ww)，，以及 m = "public W dequeue 」各自執行步驟304。通過該執行，向集合變量S保存
S={
(以下為 sl), 〈lock、(S03,S07)、(S04，S05，S06>(WTSs2)，
〈lock、(T01,T09)、(T02，T03，T04，T05，T06，T07，T08>0^TSs3) }隨著上述保存結束，該處理進入步驟306。在步驟306 步驟310的反覆中，計算機系統對包含於上述集合變量S的sl s3執行步驟307 步驟309。該執行的結果是，向集合變量C保存C = {〈lock、(SOI, S09)、T02, T07, T08> (以下為 c)，}在此，在包含S03的路徑上具有同步的副作用。此外，在包含S04行和T05行的路徑上存在向實例變量代入的副作用。因此，包含S03行、S04行和T05行的路徑不滿足步驟 307的條件。因此，包含S03行、S04行和T05行的路徑在步驟309中不保存在集合變量C。 此外，例如，在S02行，參照從w的方法的參數提供的局部變量。因此，S02行不滿足步驟308 的條件。因此，S02行在步驟309不保存在集合變量C。然後，該處理進入步驟311。在步驟311 步驟318的反覆中，計算機系統對包含於上述集合變量C的c執行步驟312 317。在步驟312和步驟313中，執行關於上述c的判定。在此，包含於c的「lock」是用private聲明的變量，是無法從CL外參照的變量。因此，c滿足步驟312和步驟313的條件，所以該處理進入步驟314。在步驟314中，計算機系統向CL追加聲明變量的語句。在此，共有變量head僅在 si內被訪問。因此，計算機系統向CL追加實例變量的聲明「private static boolean bl」。在步驟315中，計算機系統使用T02行的條件句(head ！ = null)，生成「bl = (head ！ null)」的語句。此外，head是實例變量，所以計算機系統從在步驟314追加的聲 BJ "private static boolean bl，，.[JB 「static，，。在步驟316中，計算機系統在TOl行之前生成T02行、T07行以及T08行。此外， 計算機系統用「 (bl) 」置換包含於c的條件句。計算機系統是T02行的then節向具有副作用的路徑的分支，所以將上述then節與向同步塊的代碼相連。圖7示出本發明實施方式的圖4所示的步驟316的處理被執行後的方法 dequeue 。通過步驟316的處理，向CL的方法dequeue 追加語句(412)。在上述步驟316中，隨著執行上述追加，該處理進入步驟317。在步驟317中，計算機系統執行步驟322 步驟329的反覆。在步驟322 步驟3 的反覆中，計算機系統對包含於上述集合變量S的si s3 各自執行步驟323 步驟328。滿足步驟322的條件的si s3是〈lock、(S03, S07)、(S04, S05, S06) > (s2)以及〈lock、(T01, T09)、(T02, T03, T04, T05, T06, T07, T08) > (s3)在步驟323中，計算機系統調查在關於滿足上述步驟322的條件的s2或s3的路徑是否存在至少一個向b0的代入語句的右邊參照的變量的代入。在s2或s3中，檢索進行向head代入的處理。上述檢索的結果是，s2或s3滿足步驟323的條件。在步驟324中，計算機系統關於由上述s2或s3表示的同步塊，生成新的線程，檢查生成的線程是否將獲得與由上述s2或s3表示的同步塊相同的鎖對象。通過該檢查，發現在由s2表示的同步塊的S06行包含以LO為參數調用方法bar (lock)的處理。在此，在輸入僅為CL的情況下，安裝上述方法bar (lock)的程序的程序代碼不明。因此，計算機系統使用戶判定是否將進行上述獲得。計算機系統例如在監控器顯示「foo. bar (lock)啟動線禾呈，關於 lock 是否調出 synchronized block 或 synchronized method，，, 對用戶進行詢問。用戶回答「否」的情況下，該處理進入步驟326，用戶回答「是」的情況下， 該處理進入步驟328。步驟326中，計算機系統檢查由s2或s3表示的同步塊內定義的變量是否在同步塊外參照且用於決定至少兩個線程間的執行順序。在此，S06行的共有變量lock存在從foo.baHlock)退出從其他線程被訪問的可能性。因此，計算機系統例如在監控器顯示 「lock是否用於決定與其他線程決定執行順序？ 」，對用戶進行詢問。用戶回答「否」的情況下，該處理進入步驟327，用戶回答「是」的情況下，該處理進入步驟328，退出上述反覆。在步驟327中，計算機系統決定追加在步驟315中生成的語句「bl = (head ！= null) 」的位置。bl沒有進行volatile聲明，所以計算機系統將上述生成的語句追加到更新head的語句之後。該追加的場所例如關於s2是在S06行之後，關於s3是在T06行之前和T08行之前。隨著上述步驟322 步驟329的反覆結束，該處理進入步驟319。在步驟319中，計算機系統向在步驟314中追加的聲明追加「bl = (head ！= null)； 」。隨著上述追加，該處理結束。圖8示出對圖6執行圖3 圖5所示的步驟的處理後的輸入數據(下面為變換後的程序代碼(421))。通過圖3 圖5的步驟的處理，向變換後的程序代碼(421)追加語句(422)。變換後的程序代碼021)在head為null的情況下，bl成為false。因此，變換後的程序代碼G21)被執行，head為null時調用dequeue 方法時，該處理不會突入同步塊而返回null。因此，解決所衝突的問題。圖9示出本發明實施方式的用於具體說明圖3 圖5所示的各步驟的工作的輸入數據CL。圖9 圖11所示的例子是在上述CL之外存在其他CL (未圖示)，在步驟325和步驟326中不向用戶進行詢問的情況的例子。電腦程式將輸入數據(501)作為輸入CL，啟動變換程序。在步驟302中，計算機系統向變量設定以下的值。集合變量 M= {Boolean enqueue (W w) public W dequeue }變量 i = 1集合變量S= {φ}集合變量C= {φ}隨著上述設定結束，該處理進入步驟303。步驟303 步驟305的反覆中，計算機系統對m = "boolean enqueue (Ww)，，以及 m = "public W dequeue ，，各自執行步驟304。通過該執行，向集合變量S保存S={
(以下為 sl)， 〈lock、(S03,S07)、(S04，S05，S06>(WTSs2)， 0^TSs3)
}隨著上述保存結束，該處理進入步驟306。在步驟306 步驟310的反覆中，計算機系統對包含於上述集合變量S的sl s3 分別執行步驟307 步驟309。該執行的結果是，向集合變量C保存C = {〈lock、(SOI, S09)、T02, T07, T08> (以下為 c)，}在此，在包含S03的路徑上具有同步的副作用。此外，在包含S04行和T05行的路徑上存在向實例變量代入的副作用。因此，包含S03行、S04行和T05行的路徑不滿足步驟 307的條件。因此，包含S03行、S04行和T05行的路徑在步驟309中不保存在集合變量C。 此外，例如，在S02行，參照從w的方法的參數提供的局部變量。因此，S02行不滿足步驟308 的條件。因此，S02行在步驟309不保存在集合變量C。然後，該處理進入步驟311。在步驟311 步驟318的反覆中，計算機系統對包含於上述集合變量C的c執行步驟312 317。在步驟312和步驟313中，執行關於上述c的判定。在此，包含於c的「lock」是用private聲明的變量，是無法從CL外參照的變量。因此，c滿足步驟312和步驟313的條件，所以該處理進入步驟314。在步驟314中，計算機系統向CL追加聲明變量的語句。在此，共有變量head僅在 sl內被訪問。因此，計算機系統向CL追加實例變量的聲明「private static boolean bl」。在步驟315中，計算機系統使用T02行的條件句(head ！ = null)，生成「bl = (head ！ null)」的語句。此外，head是實例變量，所以計算機系統從在步驟314追加的聲 BJ "private static boolean bl，，.[JB 「static，，。在步驟316中，計算機系統在TOl行之前生成T02行、T07行以及T08行。此外， 計算機系統用「 (bl) 」置換包含於c的條件句。計算機系統是T02行的then節向具有副作用的路徑的分支，所以將上述then節與向同步塊的代碼相連。圖10示出本發明實施方式中的、執行圖4所示的步驟316的處理後的方法 dequeue 。通過步驟316的處理，向CL的方法dequeue 追加語句(512)。在上述步驟316中，隨著執行上述追加，該處理進入步驟317。在步驟317中，計算機系統執行步驟322 步驟329的反覆。在步驟322 步驟3 的反覆中，計算機系統對包含於上述集合變量S的sl s3 各自執行步驟323 步驟328。滿足步驟322的條件的sl s3是
〈lock、(S03, S07)、(S04, S05, S06) > (s2)以及〈lock、(T01, T09)、(T02, T03, T04, T05, T06, T07, T08) > (s3)在步驟323中，計算機系統調查在關於滿足上述步驟322的條件的s2或s3的路徑是否存在至少一個向b0的代入語句的右邊參照的變量的代入。在s2或s3中，檢索進行向head代入的處理。上述檢索的結果是，s2或s3滿足步驟323的條件。在步驟324中，計算機系統關於由上述s2或s3表示的同步塊，生成新的線程，檢查生成的線程是否將獲得與由上述s2或s3表示的同步塊相同的鎖對象。在由s2或s3表示的同步塊中不包含生成新線程的語句。因此，計算機系統在該檢查中判斷為不獲得與由上述s2或s3表示的同步塊相同的鎖對象。根據不進行該獲得，該處理進入步驟326。步驟326中，計算機系統檢查由s2或s3表示的同步塊內定義的變量是否在同步塊外參照且用於決定至少兩個線程間的執行順序。在此，共有變量lock進行private聲明， 所以不從CL外訪問。此外，共有變量lock在CL內僅在同步塊內被訪問。因此，計算機系統在該檢查中判斷為共有變量lock不用於決定執行順序。根據該不用於，該處理進入步驟 327。在步驟327中，計算機系統決定追加在步驟315中生成的語句「bl = (head ！= null) 」的位置。bl沒有進行volatile聲明，所以計算機系統將上述生成的語句追加到更新head的語句之後。該追加的場所例如關於s2是在S06行之後，關於s3是在T06行之前和T08行之前。隨著上述步驟322 步驟329的反覆結束，該處理進入步驟319。在步驟319中，計算機系統向在步驟314中追加的聲明追加「bl = (head ！= null)； 」。 隨著上述追加，該處理結束。圖11示出本發明實施方式中的、對圖9執行圖3 圖5所示的步驟的處理後的輸入數據(下面為變換後的程序代碼(521))。通過圖3 圖5的步驟的處理，向變換後的程序代碼(521)追加語句(522)。變換後的程序代碼(521)在head為null的情況下，bl成為false。因此，執行變換後的程序代碼001)，head為null時調用dequeue 方法時，該處理不會突入同步塊而返回null。因此，解決所衝突的問題。圖12示出本發明的實施方式中的、通過第一條件式選擇的路徑為三條以上時的、 執行圖3 圖5所示的各步驟的處理前的程序代碼的一部分以及執行後的程序代碼的一部分。程序代碼(601)的同步塊包含兩個第一條件式「 (x==0) 」和「(y == 0) 」。此外，通過上述兩個第一條件式選擇三條路徑(602 604)。在此，在cl和c2為局部變量的情況下，路徑(60 和路徑(604)是沒有副作用的路徑。路徑(60 包含更新與第一變量對應的χ和y的兩個變量，所以是具有副作用的路徑。程序代碼(611)示出對程序代碼(601)執行圖3 圖5所示的各步驟的處理的結^ ο程序代碼(611)中向程序代碼(601)的同步塊追加聲明第二變量的聲明句(612)、 第二條件句(613)以及步驟315中製作的語句(614)。
在上述各步驟的處理中，向第二變量準備可以取表示從沒有副作用的路徑(603 和604)中選擇哪一路徑的值的變量。因此，向程序代碼(611)追加聲明作為選擇路徑(603) 的值可以取2，作為表示路徑(604)的值可以取1的變量b的聲明句(612)。此外，向程序代碼(611)追加第二條件句(613)，作為根據上述第二變量執行沒有副作用的路徑(603和 604)的條件句。向程序代碼(611)還在緊接更新第一變量即χ和y的更新句之後追加在求變量b 的值的語句即步驟315中製作的語句(614)。根據本發明的實施方式，通過執行圖3 圖5的各步驟，能夠解決java. lang. ref. ReferenceQueue中的鎖衝突的問題。圖13示出本發明的實施方式中的、圖1的系統具有的計算機硬體的框圖。本發明的實施方式的計算機系統(701)包括CPU(702)和主存儲器(703)，這些連接於路徑(704)。優選，CPU(702)基於32位或64位的系統結構，例如可以使用英特爾公司的Xeon (商標)系列，Core (商標)系列、Atom (商標)系列，Pentium (商標)系列， Celeron (商標)系列，AMD公司的Phenom (商標)系列、Althlon (商標)系列、Turion (商標)系列或kmpron (商標)等。在路徑(704)上經由顯示器控制器(70 連接有IXD監控器等顯示器(706)。顯示器(706)用於為了計算機系統的管理將經由通信線連接於網絡的計算機系統有關的信息和在該計算機系統上工作中的軟體有關的信息在適當的圖形界面顯示。在路徑(704)上還經由IDE或SATE控制器(707)連接有硬碟或矽盤(708)和 CD-ROM、DVD 驅動器或 Blu-ray 驅動器(709)。在硬碟(708)中以可下載的方式在主存儲器(70 存儲有作業系統、提供J2EE等 Java(商標)處理環境的程序、其他程序以及數據。CD-ROM、DVD驅動器或Blu_ray驅動器(709)根據需要用於從CD-ROM、DVD或 Blu-ray盤向硬碟追加導入程序。在路徑(704)上還經由鍵盤滑鼠控制器(710)連接有鍵盤(711)和滑鼠(712)。通信接口(714)例如按照乙太網協議。通信接口(714)經由通信控制器(713)連接於路徑(704)，發揮物理連接計算機系統和通信線(715)的作用，對計算機系統的作業系統的通信功能的TCP/IP通信協議提供網絡接口層。通信線可以是有線LAN環境、或者例如基於IEEE802. lla/b/g/n等無線LAN連接規格的無線LAN環境。
權利要求
1.一種將在多線程上工作的程序的程序代碼變換為鎖衝突少的程序代碼的方法，上述方法包括檢索步驟，向存儲器內讀出上述程序代碼，從該讀出的程序代碼檢索在同步塊內且向對該同步塊沒有副作用的路徑分支的第一條件句，沒有上述副作用是指基於上述同步塊內的語句處理中的值無法由上述同步塊外的語句參照；複製步驟，向上述同步塊外複製通過上述檢索出的第一條件句分支的沒有副作用的路徑；追加步驟，與上述複製相應地在上述程序代碼內追加第二條件句，上述第二條件句是向上述複製的沒有副作用的路徑分支的條件句。
2.根據權利要求1所述的方法，其中，上述第一條件句包含第一條件式，該第一條件式定義為基於第一變量的讀出、常量或這些的組合選擇路徑，所述第一變量不是僅調用包含所述第一條件句的子例程的例程中為有效範圍的變量。
3.根據權利要求2所述的方法，其中，上述第二條件句包含第二條件式，該第二條件式基於用於存儲上述第一條件式的結果的變量，根據上述第一條件式的結果選擇路徑。
4.根據權利要求3所述的方法，其中，上述檢索步驟包含從上述讀出的程序代碼進一步檢索更新句的步驟，上述更新句在上述同步塊內且更新上述第一變量，上述追加步驟包括如下步驟向從緊接上述檢索出的更新句之後到上述同步塊結束句為止之間，還追加包含用於存儲上述第一條件式的結果的變量和向該變量代入的上述第一條件式的結果的語句。
5.根據權利要求3所述的方法，其中，上述檢索步驟包括如下步驟從上述讀出的程序代碼和其他程序代碼的至少一個進一步檢索更新句，上述更新句在與上述同步塊同步的其他同步塊內且更新上述第一變量，上述追加步驟包括如下步驟向從緊接上述檢索出的更新句之後到上述同步塊結束句為止之間，還追加包含用於存儲上述第一條件式的結果的變量和向該變量代入的上述第一條件式的結果的語句。
6.根據權利要求3所述的方法，其中，上述追加步驟包括如下步驟在用於存儲上述第一條件式的結果的變量首次被參照的語句之前，還追加初始化變量的語句，該變量用於使用上述第二條件句執行包含上述同步塊的路徑的值或使用上述第一條件式的結果存儲上述第一條件式的結果。
7.根據權利要求2所述的方法，其中，在上述第一條件式的數量為2以上的情況下，上述2以上的第一條件式的結果通過上述2以上的第一條件式的組合求出。
8.根據權利要求3所述的方法，其中，在通過上述第一條件式選擇的路徑的數量為3條以上的情況下，用於存儲上述第一條件式的結果的變量與上述3條以上的路徑中沒有副作用的路徑分別對應。
9.根據權利要求3所述的方法，其中，用於存儲上述第一條件式的結果的變量是保證原子性的數據型的變量。
10.根據權利要求1所述的方法，其中，上述檢索步驟包括如下步驟從上述程序代碼和其他程序代碼的至少一個進一步檢索與上述同步塊同步的其他同步塊，隨著上述檢索的結束，執行上述複製步驟。
11.根據權利要求2所述的方法，其中，上述檢索步驟包括如下步驟還檢索包含於上述程序代碼和其他程序代碼的至少一個且從上述同步塊外的語句參照上述第一變量的語句， 隨著上述檢索的結束，執行上述複製步驟。
12.根據權利要求1所述的方法，其中， 在上述同步塊內包含啟動線程的語句的情況下，上述檢索步驟包括如下步驟從包含於上述程序代碼和其他程序代碼的至少一個且記載上述線程的安裝的語句，進一步檢索與上述同步塊內的語句同步地執行的語句，還包括如下步驟根據檢索上述同步地執行的語句，將包含啟動上述線程的語句判定為具有副作用的路徑。
13.根據權利要求1所述的方法，其中， 在上述同步塊內包含啟動線程的語句的情況下，上述檢索步驟還包括如下步驟要求用戶判斷包含啟動上述線程的語句的路徑是否為沒有副作用的路徑。
14.根據權利要求1所述的方法，其中，在用於確定執行上述同步塊的線程的執行順序的變量在上述同步塊內定義的情況下， 上述檢索步驟包括如下步驟從上述同步塊外進一步檢索包含於上述程序代碼和其他程序代碼的至少一個且參照上述使用的變量的語句，上述方法還包括如下步驟根據檢索參照上述使用的變量的語句，將包含上述使用的變量的路徑判定為具有副作用的路徑。
15.根據權利要求1所述的方法，其中，在用於確定執行上述同步塊的線程的執行順序的變量在上述同步塊內定義的情況下， 上述檢索步驟還包括如下步驟要求用戶判斷包含所述使用的變量的路徑是否為沒有副作用的路徑。
16.根據權利要求3所述的方法，其中，上述追加步驟包括如下步驟向上述讀出的程序代碼還追加聲明用於存儲上述第一條件式的結果的變量的語句，在共有變量包含於上述程序代碼和上述其他程序代碼的至少一個且從上述同步塊外的語句被訪問的情況下，上述聲明包含抑制與存儲器的訪問順序有關的最優化的指定和保證原子性的指定，上述共有變量包含於沒有上述副作用的路徑，且能夠從多個線程被訪問， 在不進行上述訪問的情況下，上述聲明包含保證原子性的指定。
17.根據權利要求1所述的方法，其中，上述檢索步驟還包括如下步驟允許用戶判斷是否具有與上述同步塊同步的其他同步塊，在上述允許步驟之後，執行上述複製步驟。
18.根據權利要求2所述的方法，其中，上述檢索步驟還包括如下步驟允許用戶判斷是否具有參照上述第一變量的語句， 在上述允許步驟之後執行上述複製步驟。
19.一種計算機系統，將在多線程上工作的程序的程序代碼變換為鎖衝突少的程序代碼，上述計算機系統包括檢索部，向存儲器內讀出上述程序代碼，從該讀出的程序代碼檢索在同步塊內且向對該同步塊沒有副作用的路徑分支的第一條件句，沒有上述副作用是指基於上述同步塊內的語句處理中的值無法由上述同步塊外的語句參照；複製部，向上述同步塊外複製通過上述檢索出的第一條件句分支的沒有副作用的路徑；追加部，與上述複製相應地在上述程序代碼內追加第二條件句，上述第二條件句是向上述複製出的沒有副作用的路徑分支的條件句。
20.一種將多線程上工作的程序的程序代碼變換為鎖衝突少的程序代碼的方法，該方法包括檢索步驟，向存儲器內讀出上述程序代碼，從該讀出的程序代碼檢索在同步塊內且向對該同步塊沒有副作用的路徑分支的第一條件句，沒有上述副作用是指基於上述同步塊內的語句處理中的值無法由上述同步塊外的語句參照；複製步驟，向上述同步塊外複製通過上述檢索出的第一條件句分支的沒有副作用的路徑；追加步驟，與上述複製相應地在上述程序代碼內追加第二條件句，上述第二條件句是向上述複製的沒有副作用的路徑分支的條件句，上述第一條件句包含第一條件式，該第一條件式基於實例變量或類變量的讀出、常量或這些的組合，在向沒有副作用的路徑分支的情況下定義為其結果變為true，另一方面，在向具有副作用的路徑分支的情況下定義為其結果變為false，上述第二條件句包含第二條件式，該第二條件式基於用於存儲上述第一條件式的結果的boolean型的變量，定義為根據上述第一條件式的結果選擇路徑。
21.一種電腦程式，使計算機執行根據權利要求1 18任一項所述的方法的各步驟。
全文摘要
需要自動確定將要發生由鎖衝突引起的性能下降的問題的位置，自動修正該位置的方法。本發明提供將在多線程上工作的程序的程序代碼變換為鎖衝突少的程序代碼的方法。該方法包括檢索步驟，向存儲器內讀出上述程序代碼，從該讀出的程序代碼檢索在同步塊內且向對該同步塊沒有副作用的路徑分支的第一條件句；複製步驟，向上述同步塊外複製通過上述檢索出的第一條件句分支的沒有副作用的路徑；追加步驟，與上述複製相應地向上述程序代碼內追加第二條件句，上述第二條件句是向上述複製的沒有副作用的路徑分支的條件句。
文檔編號G06F9/52GK102292709SQ201080005431
公開日2011年12月21日 申請日期2010年4月22日 優先權日2009年4月28日
發明者石崎一明 申請人:國際商業機器公司