操作系統(tǒng)中進(jìn)程同步算法的仿真研究

李乃健，田紀(jì)宏，胥國(guó)偉，齊英杰

（濟(jì)寧醫(yī)學(xué)院醫(yī)學(xué)信息工程學(xué)院，日照 276825）

0 引言

計(jì)算機(jī)真正完成一項(xiàng)具體任務(wù)，必須要借助操作系統(tǒng)中的進(jìn)程來(lái)完成，進(jìn)程是進(jìn)程實(shí)體的運(yùn)行過(guò)程，是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位，但從計(jì)算機(jī)的效率考察，為了減少系統(tǒng)對(duì)于并發(fā)所帶來(lái)的時(shí)/空開(kāi)銷(xiāo)，將擁有資源所有權(quán)的仍稱(chēng)為進(jìn)程，而調(diào)度的單位稱(chēng)為線程，或輕量級(jí)進(jìn)程，故線程是進(jìn)程內(nèi)一個(gè)相對(duì)獨(dú)立的執(zhí)行流或控制流，是處理機(jī)分配的實(shí)體。它本身不擁有系統(tǒng)資源，但與同屬一個(gè)進(jìn)程的其他線程共享進(jìn)程所擁有的全部資源，進(jìn)程和多線程的關(guān)系如圖1所示。

圖1 進(jìn)程與線程的關(guān)系圖

1 進(jìn)程同步

在操作系統(tǒng)課程中，進(jìn)程同步是對(duì)多個(gè)相關(guān)進(jìn)程在執(zhí)行次序上進(jìn)行協(xié)調(diào)，使并發(fā)執(zhí)行的諸進(jìn)程之間能夠按照一定的規(guī)則（或時(shí)序）共享系統(tǒng)資源，并能很好地相互合作，從而使程序的執(zhí)行具有可再現(xiàn)性。從該定義中不難得出：進(jìn)程同步解決的是同步的諸進(jìn)程之間執(zhí)行次序的問(wèn)題，其目的是協(xié)調(diào)多個(gè)并發(fā)進(jìn)程的執(zhí)行，使它們高效地共享系統(tǒng)中的資源并更好地相互合作，從而保證程序的執(zhí)行具有可再現(xiàn)性，使系統(tǒng)資源利用最大化，進(jìn)而保障系統(tǒng)的穩(wěn)定性與可靠性。

2 實(shí)現(xiàn)進(jìn)程同步算法的技術(shù)

2.1 JJaavvaa內(nèi)在支持多線程技術(shù)

Java語(yǔ)言作為一種面向?qū)ο笄遗c平臺(tái)無(wú)關(guān)的多線程動(dòng)態(tài)語(yǔ)言，具有支持多線程、解釋運(yùn)行效率高、動(dòng)態(tài)性、語(yǔ)法簡(jiǎn)單等優(yōu)點(diǎn)，其中最重要的是支持多線程編程。所有Java類(lèi)都有一個(gè)共同的父類(lèi)：Object類(lèi)。Ob?ject類(lèi)有涉及線程同步的notify（）、notifyAll（）、wait（）、wait（long timeOut）等函數(shù)，這些函數(shù)可以很好地喚醒或阻塞在當(dāng)前對(duì)象監(jiān)視器上等待線程。Java中線程有4個(gè)狀態(tài)，創(chuàng)建狀態(tài)、可運(yùn)行狀態(tài)、運(yùn)行狀態(tài)、撤消狀態(tài)，如圖2所示。

圖2 Java中線程的狀態(tài)轉(zhuǎn)換

在單個(gè)程序中同時(shí)運(yùn)行多個(gè)線程完成不同的工作，稱(chēng)為多線程。進(jìn)程可以看作程序運(yùn)行時(shí)的一個(gè)實(shí)例，而線程則可看作單獨(dú)地占有CPU執(zhí)行的代碼，基于這種思想，使用支持多線程的Java語(yǔ)言編程比其他語(yǔ)言更為簡(jiǎn)單與高效。Java中實(shí)現(xiàn)多線程編程有兩種主要方法：一種是繼承Thread類(lèi)，通過(guò)定義java.lang包中的Thread類(lèi)的子類(lèi)并在子類(lèi)中重寫(xiě)run（）方法。由于Java不能多重繼承，此方法簡(jiǎn)單但不靈活；另一種是實(shí)現(xiàn)Runnable接口，該接口只有一個(gè)run（）方法，要實(shí)現(xiàn)此接口就必須定義run（）方法的具體內(nèi)容，方法體內(nèi)可定義用戶(hù)要做的操作，然后以這個(gè)實(shí)現(xiàn)了Runnable接口的類(lèi)為參數(shù)創(chuàng)建Thread類(lèi)的對(duì)象，也就是用Run?nable接口的目標(biāo)對(duì)象初始化Thread類(lèi)的對(duì)象，這樣就可把用戶(hù)實(shí)現(xiàn)的run（）方法繼承過(guò)來(lái)。

2.2 多線程編程的重要性

首先，使用多線程技術(shù)后，可以在同一時(shí)間內(nèi)運(yùn)行更多不同種類(lèi)的任務(wù)，在開(kāi)發(fā)難度和性能上都比單線程更好。其次，由于Java語(yǔ)言實(shí)現(xiàn)了多線程技術(shù)，所以比C、C++等語(yǔ)言實(shí)現(xiàn)的算法更為健壯，穩(wěn)定性更好。再者，Java語(yǔ)言是首個(gè)在語(yǔ)言級(jí)別提供對(duì)多線程程序設(shè)計(jì)支持的編程語(yǔ)言，借助Java語(yǔ)言的多線程機(jī)制，開(kāi)發(fā)多線程應(yīng)用程序的過(guò)程得到大大簡(jiǎn)化。而且Java語(yǔ)言引入了并發(fā)機(jī)制來(lái)避免可能出現(xiàn)的數(shù)據(jù)訪問(wèn)沖突問(wèn)題。

3 經(jīng)典進(jìn)程同步算法的仿真實(shí)現(xiàn)

3.1 生產(chǎn)者-消費(fèi)者問(wèn)題

（1）問(wèn)題分析與設(shè)計(jì)

生產(chǎn)者-消費(fèi)者問(wèn)題是一個(gè)經(jīng)典的進(jìn)程同步問(wèn)題，問(wèn)題描述為：生產(chǎn)者進(jìn)程與消費(fèi)者進(jìn)程能要想并發(fā)執(zhí)行，需在兩者之間設(shè)置一個(gè)具有n個(gè)緩沖區(qū)（多緩沖區(qū)）的緩沖池，生產(chǎn)者進(jìn)程將其所生產(chǎn)的產(chǎn)品放入一個(gè)緩沖區(qū)中；消費(fèi)者進(jìn)程可從一個(gè)緩沖區(qū)中取走產(chǎn)品消費(fèi)。不允許消費(fèi)者進(jìn)程到一個(gè)空緩沖區(qū)去取產(chǎn)品，也不允許生產(chǎn)者進(jìn)程向一個(gè)已裝滿(mǎn)產(chǎn)品且尚未被取走的滿(mǎn)緩沖區(qū)中投放產(chǎn)品。

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

（2）部分代碼實(shí)現(xiàn)

Java部分代碼如下：

3.2 讀者-寫(xiě)者問(wèn)題

（1）問(wèn)題分析與設(shè)計(jì)

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

代碼中只新建了一個(gè)類(lèi)ReadAndWrite，采用匿名內(nèi)部類(lèi)的方式創(chuàng)建并實(shí)例化兩個(gè)對(duì)象，并分別多次循環(huán)調(diào)用Read（）與Write（）方法對(duì)共享數(shù)據(jù)進(jìn)行讀與寫(xiě)操作。代碼中還使用可重入的互斥鎖ReentrantRead?WriteLock實(shí)現(xiàn)讀者與寫(xiě)者的互斥。在Read（）與Write（）方法中設(shè)置讀鎖與寫(xiě)鎖，保證寫(xiě)者優(yōu)先，SX類(lèi)中的讀與寫(xiě)方法操作的數(shù)據(jù)是一個(gè)0與1000之間整型的隨機(jī)數(shù)，本算法還采用了try-catch-finally異常處理機(jī)制，當(dāng)發(fā)生異常時(shí)程序會(huì)自動(dòng)解鎖以處理異常。

（2）部分代碼實(shí)現(xiàn)

Java部分代碼如下：

從運(yùn)行結(jié)果看，該算法成功實(shí)現(xiàn)了生產(chǎn)者線程與消費(fèi)者線程的同步，它簡(jiǎn)化了開(kāi)發(fā)，可以獨(dú)立地或并發(fā)地編寫(xiě)消費(fèi)者和生產(chǎn)者；生產(chǎn)者和消費(fèi)者可以以不同的速度執(zhí)行；分離的消費(fèi)者和生產(chǎn)者在功能上能寫(xiě)出更簡(jiǎn)潔、可讀、易維護(hù)的代碼，故應(yīng)用多線程技術(shù)，大大提高了系統(tǒng)效率。

從運(yùn)行結(jié)果來(lái)看，本算法很好地實(shí)現(xiàn)了“讀者-寫(xiě)者”問(wèn)題中寫(xiě)者優(yōu)先的算法，即當(dāng)有多個(gè)寫(xiě)者等待時(shí)后續(xù)的讀者全部阻塞，直到所有寫(xiě)者全部寫(xiě)完后讀者才能讀取，多個(gè)寫(xiě)者之間并發(fā)執(zhí)行，而且讀者讀取的都是最后一個(gè)寫(xiě)者修改后的數(shù)據(jù)。以Java多線程技術(shù)與提供的同步機(jī)制，有效避免了數(shù)據(jù)訪問(wèn)沖突與數(shù)據(jù)操作錯(cuò)誤，即讀者讀取的數(shù)據(jù)為最后一個(gè)寫(xiě)者操作后的數(shù)據(jù)。

4 結(jié)語(yǔ)

通過(guò)使用Java語(yǔ)言的多線程技術(shù)，仿真實(shí)現(xiàn)了生產(chǎn)者-消費(fèi)者、讀者-寫(xiě)者問(wèn)題的進(jìn)程同步算法。實(shí)現(xiàn)了生產(chǎn)者與消費(fèi)者互斥地使用緩沖區(qū)，尤其是Runna?ble接口實(shí)現(xiàn)了多個(gè)線程共同完成一個(gè)任務(wù)的功能；實(shí)現(xiàn)了寫(xiě)者優(yōu)先的功能，諸讀者與諸寫(xiě)者之間各自并發(fā)運(yùn)行，而且保證讀者讀取數(shù)據(jù)為最后一個(gè)寫(xiě)者操作后的數(shù)據(jù)，從而避免了很多算法中都未曾處理的潛在的數(shù)據(jù)沖突和數(shù)據(jù)訪問(wèn)錯(cuò)誤等問(wèn)題。這些仿真實(shí)現(xiàn)，優(yōu)化了算法的內(nèi)部結(jié)構(gòu)，補(bǔ)充算法的部分功能，增強(qiáng)算法的可讀性和實(shí)用性，提高系統(tǒng)資源的利用率,充分發(fā)揮系統(tǒng)的性能。

參考文獻(xiàn)：

[1]孔德鳳，應(yīng)時(shí).基于Java線程機(jī)制研究生產(chǎn)者-消費(fèi)者問(wèn)題.信息與電腦[J]，2017（2）.

[2]湯小丹等.計(jì)算機(jī)操作系統(tǒng)[M].西安：西安電子科技大學(xué)出版社，2014.

[3]高洪巖.Java多線程編程核心技術(shù)[M].北京：機(jī)械工業(yè)出版社，2015.

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

[5]史廣.Java多線程并發(fā)機(jī)制的應(yīng)用探討[J].貴州師范大學(xué)國(guó)際教育學(xué)院學(xué)報(bào)，2016.