操作系統中進程同步算法的仿真研究

李乃健，田紀宏，胥國偉，齊英杰

（濟寧醫學院醫學信息工程學院，日照 276825）

0 引言

計算機真正完成一項具體任務，必須要借助操作系統中的進程來完成，進程是進程實體的運行過程，是系統進行資源分配和調度的一個獨立單位，但從計算機的效率考察，為了減少系統對于并發所帶來的時/空開銷，將擁有資源所有權的仍稱為進程，而調度的單位稱為線程，或輕量級進程，故線程是進程內一個相對獨立的執行流或控制流，是處理機分配的實體。它本身不擁有系統資源，但與同屬一個進程的其他線程共享進程所擁有的全部資源，進程和多線程的關系如圖1所示。

圖1 進程與線程的關系圖

1 進程同步

在操作系統課程中，進程同步是對多個相關進程在執行次序上進行協調，使并發執行的諸進程之間能夠按照一定的規則（或時序）共享系統資源，并能很好地相互合作，從而使程序的執行具有可再現性。從該定義中不難得出：進程同步解決的是同步的諸進程之間執行次序的問題，其目的是協調多個并發進程的執行，使它們高效地共享系統中的資源并更好地相互合作，從而保證程序的執行具有可再現性，使系統資源利用最大化，進而保障系統的穩定性與可靠性。

2 實現進程同步算法的技術

2.1 JJaavvaa內在支持多線程技術

Java語言作為一種面向對象且與平臺無關的多線程動態語言，具有支持多線程、解釋運行效率高、動態性、語法簡單等優點，其中最重要的是支持多線程編程。所有Java類都有一個共同的父類：Object類。Ob?ject類有涉及線程同步的notify（）、notifyAll（）、wait（）、wait（long timeOut）等函數，這些函數可以很好地喚醒或阻塞在當前對象監視器上等待線程。Java中線程有4個狀態，創建狀態、可運行狀態、運行狀態、撤消狀態，如圖2所示。

圖2 Java中線程的狀態轉換

在單個程序中同時運行多個線程完成不同的工作，稱為多線程。進程可以看作程序運行時的一個實例，而線程則可看作單獨地占有CPU執行的代碼，基于這種思想，使用支持多線程的Java語言編程比其他語言更為簡單與高效。Java中實現多線程編程有兩種主要方法：一種是繼承Thread類，通過定義java.lang包中的Thread類的子類并在子類中重寫run（）方法。由于Java不能多重繼承，此方法簡單但不靈活；另一種是實現Runnable接口，該接口只有一個run（）方法，要實現此接口就必須定義run（）方法的具體內容，方法體內可定義用戶要做的操作，然后以這個實現了Runnable接口的類為參數創建Thread類的對象，也就是用Run?nable接口的目標對象初始化Thread類的對象，這樣就可把用戶實現的run（）方法繼承過來。

2.2 多線程編程的重要性

首先，使用多線程技術后，可以在同一時間內運行更多不同種類的任務，在開發難度和性能上都比單線程更好。其次，由于Java語言實現了多線程技術，所以比C、C++等語言實現的算法更為健壯，穩定性更好。再者，Java語言是首個在語言級別提供對多線程程序設計支持的編程語言，借助Java語言的多線程機制，開發多線程應用程序的過程得到大大簡化。而且Java語言引入了并發機制來避免可能出現的數據訪問沖突問題。

3 經典進程同步算法的仿真實現

3.1 生產者-消費者問題

（1）問題分析與設計

生產者-消費者問題是一個經典的進程同步問題，問題描述為：生產者進程與消費者進程能要想并發執行，需在兩者之間設置一個具有n個緩沖區（多緩沖區）的緩沖池，生產者進程將其所生產的產品放入一個緩沖區中；消費者進程可從一個緩沖區中取走產品消費。不允許消費者進程到一個空緩沖區去取產品，也不允許生產者進程向一個已裝滿產品且尚未被取走的滿緩沖區中投放產品。

憑借Java語言多線程編程技術的優勢，用線程模擬生產者與消費者，采用已經在Java語言內部實現了同步機制的阻塞隊列（BlockingQueue）模擬生產者與消費者隊列，利用生產者類Producer與消費者類Consum?er通過實現Runnable接口來的方式創建并實例化線程對象producer與consumer（打破了擴充Thread類與單繼承的限制）。此方法不需要人為地考慮線程何時等待與何時喚醒以及如何清空緩沖區的問題，從而簡化了代碼的編寫，并且減少了系統的開銷，提高了系統的資源利用率與吞吐量，實現系統資源利用最大化，更提高了程序執行的并發度。在代碼中只新建了一個緩沖區類Buffer，并且采用匿名內部類方式創建并實例化生產者、消費者線程對象，重寫了線程的run（）方法作為線程的主體來完成對緩沖隊列LinkedBlockingQueue的操作。阻塞隊列提供的開箱即用的get（）與set（）方法能夠自動地阻塞線程，在主方法中定義了一個大小為3個線程的緩沖區隊列和生產者阻塞隊列Producer、消費者阻塞隊列Consumer，它們都采用FIFO（先進先出）策略對線程進行調度。用同一個緩沖區對象buffer分別實例化了兩個生產者線程與兩個消費者線程，使他們并發執行。通過Random實例化的對象r調用nextInt（100）方法會產生0～100內的隨機數作為實參傳給get（）方法的形參data，完成生產操作；消費者線程通過調用take（）方法從緩沖區隊列中取出產品data完成消費操作。

（2）部分代碼實現

Java部分代碼如下：

3.2 讀者-寫者問題

（1）問題分析與設計

讀者-寫者問題也是一個經典的進程同步問題。所謂讀者-寫者問題（The Reader-Writer Problem），是指保證一個Writer進程必須與其他進程互斥地訪問共享對象的同步問題。該問題主要描述的是怎樣保證系統中的若干個進程對某數據文件或記錄進行正確地讀寫，從而避免出現文件數據的丟失修改與讀臟數據的問題。為了避免讀者與寫者同時對文件進行讀寫操作而引起的數據訪問錯誤，下面主要研究采用寫者優先的方法。所謂寫者優先是指一個寫者申請一個共享資源時，如果有讀者在讀取該資源，則必須封鎖后續到來的讀者，以便寫者對共享資源的修改；當有讀者與寫者同時等待資源時，寫者優先訪問共享資源。解決該問題的關鍵在于解決寫者與寫者、寫者與第一個讀者的同步問題。Java不僅支持多線程，而且在Java包中還提供了Lock接口，為多個線程之間的同步提供了互斥鎖，lock（）可以實現同步訪問。Lock接口的實現提供了更廣泛的鎖定操作的方法，比使用synchronized方法和語句更加靈活，使算法結構更清晰易讀。

代碼中只新建了一個類ReadAndWrite，采用匿名內部類的方式創建并實例化兩個對象，并分別多次循環調用Read（）與Write（）方法對共享數據進行讀與寫操作。代碼中還使用可重入的互斥鎖ReentrantRead?WriteLock實現讀者與寫者的互斥。在Read（）與Write（）方法中設置讀鎖與寫鎖，保證寫者優先，SX類中的讀與寫方法操作的數據是一個0與1000之間整型的隨機數，本算法還采用了try-catch-finally異常處理機制，當發生異常時程序會自動解鎖以處理異常。

（2）部分代碼實現

Java部分代碼如下：

從運行結果看，該算法成功實現了生產者線程與消費者線程的同步，它簡化了開發，可以獨立地或并發地編寫消費者和生產者；生產者和消費者可以以不同的速度執行；分離的消費者和生產者在功能上能寫出更簡潔、可讀、易維護的代碼，故應用多線程技術，大大提高了系統效率。

從運行結果來看，本算法很好地實現了“讀者-寫者”問題中寫者優先的算法，即當有多個寫者等待時后續的讀者全部阻塞，直到所有寫者全部寫完后讀者才能讀取，多個寫者之間并發執行，而且讀者讀取的都是最后一個寫者修改后的數據。以Java多線程技術與提供的同步機制，有效避免了數據訪問沖突與數據操作錯誤，即讀者讀取的數據為最后一個寫者操作后的數據。

4 結語

通過使用Java語言的多線程技術，仿真實現了生產者-消費者、讀者-寫者問題的進程同步算法。實現了生產者與消費者互斥地使用緩沖區，尤其是Runna?ble接口實現了多個線程共同完成一個任務的功能；實現了寫者優先的功能，諸讀者與諸寫者之間各自并發運行，而且保證讀者讀取數據為最后一個寫者操作后的數據，從而避免了很多算法中都未曾處理的潛在的數據沖突和數據訪問錯誤等問題。這些仿真實現，優化了算法的內部結構，補充算法的部分功能，增強算法的可讀性和實用性，提高系統資源的利用率,充分發揮系統的性能。

參考文獻：

[1]孔德鳳，應時.基于Java線程機制研究生產者-消費者問題.信息與電腦[J]，2017（2）.

[2]湯小丹等.計算機操作系統[M].西安：西安電子科技大學出版社，2014.

[3]高洪巖.Java多線程編程核心技術[M].北京：機械工業出版社，2015.

[4]吳仁群.Java基礎教程（第二版）[M].北京：清華大學出版社，2012.

[5]史廣.Java多線程并發機制的應用探討[J].貴州師范大學國際教育學院學報，2016.