OS緩沖管理中數(shù)據(jù)處理時間函數(shù)研究

張剛園，邱傳曦

(西華師范大學(xué) 計算機學(xué)院，四川 南充 637009)

在現(xiàn)代操作系統(tǒng)中，幾乎所有的I/O設(shè)備在與處理機交換數(shù)據(jù)時都用到了緩沖區(qū)。操作系統(tǒng)的緩沖技術(shù)大致可分為單緩沖、雙緩沖、多緩沖、循環(huán)緩沖(環(huán)形緩沖)、緩沖池等。本文僅研究單緩沖和雙緩沖機制下系統(tǒng)對數(shù)據(jù)塊處理的時間函數(shù)。

1 存在的問題

在塊設(shè)備輸入時，從磁盤把1個數(shù)據(jù)塊(緩沖區(qū)裝滿即為一個數(shù)據(jù)塊，最后一塊可能裝不滿)輸入到緩沖區(qū)的時間為T，將緩沖區(qū)中的數(shù)據(jù)塊傳送到用戶區(qū)的時間為M，CPU對一個數(shù)據(jù)塊的計算時間為C，則系統(tǒng)對1個數(shù)據(jù)塊處理的時間，對單緩沖而言,多數(shù)著作認為是Max(T,C)+M[1-6]；對雙緩沖而言，文獻[1-2,4]給出的結(jié)論是可以粗略地認為是Max(C，T)，文獻[3]給出的時間函數(shù)為Max(T，M+C)，文獻[5-6]給出的結(jié)論是:當CT時為Max(C,T)+M。而文獻[7-10]未對數(shù)據(jù)塊處理時間進行分析。

綜合分析上述結(jié)論，主要存在如下問題：

(1)缺乏前提條件

上述系統(tǒng)對1個數(shù)據(jù)塊的處理時間結(jié)論，缺乏如下前提條件：系統(tǒng)中只有輸入進程和計算進程，按單道方式運行和非搶占方式調(diào)度，進程切換所花時間忽略不計。缺乏這些條件，則上述結(jié)論不成立。

(2)忽略了緩沖區(qū)大小與工作區(qū)大小對數(shù)據(jù)塊處理時間的影響

上述文獻中在單緩沖機制得出的對1個數(shù)據(jù)塊的處理時間函數(shù)，在緩沖區(qū)大小與工作區(qū)大小相同時成立，而在緩沖區(qū)遠小于工作區(qū)時，則不成立；在雙緩沖機制下，給出的數(shù)據(jù)塊處理時間的結(jié)論不一致，不完整，完全沒有考慮緩沖區(qū)大小和工作區(qū)大小對處理時間的影響，對問題的分析不夠全面。

2 單緩沖機制下數(shù)據(jù)處理時間函數(shù)分析

2.1 單緩沖區(qū)工作機制

單緩沖是系統(tǒng)所提供的最簡單類型緩沖區(qū)設(shè)置，如圖1所示。當用戶進程發(fā)出一I/O請求時，系統(tǒng)為其分配一個緩沖區(qū)。對于塊設(shè)備來說，先將1個數(shù)據(jù)塊輸入到緩沖區(qū)，然后將緩沖區(qū)中的數(shù)據(jù)傳送到工作區(qū)，最后由系統(tǒng)對其進行計算處理[1]。

2.2 單緩沖機制下數(shù)據(jù)塊處理時間函數(shù)的分析

當數(shù)據(jù)塊為1時，系統(tǒng)對該數(shù)據(jù)塊處理的總時間為T+M+C；而要處理大量的數(shù)據(jù)塊時，分為如下幾種情況。

2.2.1 緩沖區(qū)大小等于工作區(qū)大小

1)T

假設(shè)T=10，M=1，C=20。該情況下單緩沖工作過程圖和數(shù)據(jù)塊處理時間表如圖2及表1所示：

表1 數(shù)據(jù)塊處理時間表(緩沖區(qū)大小=工作區(qū)大小，T

從圖2和表1可知：數(shù)據(jù)塊傳輸完成后即可開始第1數(shù)據(jù)塊的計算,同時進行后一數(shù)據(jù)塊的輸入，即Ti與Ci-1兩個操作并行；由于緩沖區(qū)大小=工作區(qū)大小，所以后一數(shù)據(jù)塊必須等待前一數(shù)據(jù)塊計算完成后才能開始傳輸，即Ci-1完成后進行Mi操作。

由上述可得，當T

2)T>C

假設(shè)T=20，M=1，C=10。該情況下單緩沖工作過程圖和數(shù)據(jù)塊處理時間表如圖3及表2所示：

表2 數(shù)據(jù)塊處理時間表(緩沖區(qū)大小=工作區(qū)大小，T>C)

從圖3和表2可知：數(shù)據(jù)塊輸入完成后開始數(shù)據(jù)塊的傳輸，傳輸完成后開始第1數(shù)據(jù)塊的計算，同時進行后1數(shù)據(jù)塊的輸入，即Ti與Ci-1兩個操作并行；由于T>C，后1數(shù)據(jù)塊輸入完成時，工作區(qū)已經(jīng)被“抽空”，所以后1數(shù)據(jù)塊可以立即傳入工作區(qū)。此時，除第1數(shù)據(jù)塊外，系統(tǒng)對后續(xù)的每一數(shù)據(jù)塊的處理時間為M+T，即Max(C,T)+M。

所以，在緩沖區(qū)大小等于工作區(qū)大小時，系統(tǒng)對每一數(shù)據(jù)塊處理的時間函數(shù)為Max(C,T)+M。

2.2.2 緩沖區(qū)大小遠小于工作區(qū)大小

在此情況下，數(shù)據(jù)塊由緩沖區(qū)傳送到工作區(qū)不受影響，緩沖區(qū)裝滿即可傳送至工作區(qū)。

1)T

假設(shè)T=10，M=1，C=20。該情況下單緩沖工作過程圖和數(shù)據(jù)塊處理時間表如圖4及表3所示：

表3 數(shù)據(jù)塊處理時間表(緩沖區(qū)大小<<工作區(qū)大小，T

從圖4和表3可知：數(shù)據(jù)塊輸入完成時即可傳輸數(shù)據(jù)塊，傳輸完成時開始后1數(shù)據(jù)塊的輸入，由于緩沖區(qū)遠小于工作區(qū)，所以輸入完成后可以立即傳入工作區(qū)。此時，Ti+Mi與Ci-1兩個操作并行。所以，此情況下除第1數(shù)據(jù)塊外，系統(tǒng)對每1數(shù)據(jù)塊的處理時間為C；進一步分析當T

表4 數(shù)據(jù)塊處理時間表(緩沖區(qū)大小<<工作區(qū)大小，T>C )

2)T>C

假設(shè)T=20，M=1，C=10。該情況下單緩沖工作過程圖和數(shù)據(jù)塊處理時間表如圖5及表4所示

從圖5和表4可知：數(shù)據(jù)塊輸入完成時開始傳輸，傳輸完成時開始計算，同時進行下個數(shù)據(jù)塊的輸入，即Ti與Ci-1兩個操作并行，此時，除第1數(shù)據(jù)塊外，系統(tǒng)對每個數(shù)據(jù)塊的處理時間為T+M，即可表示為Max(T，C)+M。

所以，除第1塊數(shù)據(jù)塊外，在緩沖區(qū)大小遠小于工作區(qū)大小時，當T+MC時，處理時間為T+M。即系統(tǒng)對每一塊數(shù)據(jù)的處理時間為Max(T+M,C)。

綜上所述，在緩沖區(qū)大小等于工作區(qū)大小時，系統(tǒng)對每一數(shù)據(jù)塊處理的時間函數(shù)為Max(C,T)+M；在緩沖區(qū)大小遠小于工作區(qū)大小時，系統(tǒng)對每一塊數(shù)據(jù)的處理時間函數(shù)為Max(T+M,C)。

3 雙緩沖機制下數(shù)據(jù)處理時間函數(shù)分析

3.1 雙緩沖區(qū)工作機制

為了提高輸入/輸出設(shè)備的速度效率，提高系統(tǒng)的并行能力，在內(nèi)存中開辟雙緩沖區(qū)。雙緩沖區(qū)是指操作系統(tǒng)為一個用戶分配兩個緩沖區(qū)，如圖3.1所示。在輸入數(shù)據(jù)時，首先輸入設(shè)備將數(shù)據(jù)輸入緩沖區(qū)1，在緩沖區(qū)1裝滿后在輸入緩沖區(qū)2。如果緩沖區(qū)1已經(jīng)被輸入數(shù)據(jù)裝滿，在操作系統(tǒng)將緩沖區(qū)1中的數(shù)據(jù)取到工作區(qū)期間，緩沖區(qū)2可以接收輸入數(shù)據(jù)。如果緩沖區(qū)2已經(jīng)被輸入數(shù)據(jù)裝滿，在操作系統(tǒng)將緩沖區(qū)2中的數(shù)據(jù)取到工作區(qū)期間，緩沖區(qū)1可以接收輸入數(shù)據(jù)。緩沖區(qū)1和緩沖區(qū)2交替使用，只要緩沖區(qū)中的數(shù)據(jù)輸入到工作區(qū)后，處理器就可以執(zhí)行用戶進程[1]。

3.2 雙緩沖機制下數(shù)據(jù)塊處理的時間函數(shù)分析

當系統(tǒng)只處理1個數(shù)據(jù)塊時，系統(tǒng)對該數(shù)據(jù)塊的處理時間同單緩沖一致；當需要處理的數(shù)據(jù)僅有2個數(shù)據(jù)塊時，處理的總時間為Max(C,T)+T+M+C；而要處理大量的數(shù)據(jù)塊時，分為如下幾種情況。

3.2.1 緩沖區(qū)大小等于工作區(qū)大小

1)T

假設(shè)T=10，M=1，C=20。該情況下雙緩沖工作過程圖和數(shù)據(jù)塊處理時間表如圖7及表5所示：

從圖7和表5可知：除前2個數(shù)據(jù)塊外，與圖2和表1完全一致，所以在該情況下系統(tǒng)處理1個數(shù)據(jù)塊的時間函數(shù)為Max(C,T)+M，這與文獻[1-2，4]結(jié)論顯然不同，雖然M比T或C小得多，但如果處理的數(shù)據(jù)塊數(shù)量特別大時，偏差就會很大 。

表5 數(shù)據(jù)塊處理時間表(緩沖區(qū)大小=工作區(qū)大小，T

2)T>C

假設(shè)T=20，M=1，C=10。該情況下雙緩沖工作過程圖和數(shù)據(jù)塊處理時間表如圖8及表6所示：

從圖8和表6可知：數(shù)據(jù)塊輸入完成后開始傳輸數(shù)據(jù)，同時將下一數(shù)據(jù)塊向緩沖區(qū)2輸入，傳輸完成時開始計算。即Ti與Mi-1+Ci-1兩個操作并行，所以，此情況下除前2個數(shù)據(jù)塊外，系統(tǒng)對每一個數(shù)據(jù)塊的處理時間為T，進一步分析當C

表6 數(shù)據(jù)塊處理時間表(緩沖區(qū)大小=工作區(qū)大小，T>C)

所以，在緩沖區(qū)大小等于工作區(qū)大小時，除前2個數(shù)據(jù)塊外，當T>M+C時，處理時間為T；當T

3.2.2 緩沖區(qū)大小遠小于工作區(qū)大小

1)T

假設(shè)T=10，M=1，C=20。該情況下雙緩沖工作過程圖和數(shù)據(jù)塊處理時間表如圖9與表7所示：

表7 數(shù)據(jù)塊處理時間表(緩沖區(qū)大小<<工作區(qū)大小，T

從圖9和表7可知：數(shù)據(jù)塊輸入完成后進行數(shù)據(jù)傳輸，同時下一數(shù)據(jù)塊開始輸入，計算完成便進行下一數(shù)據(jù)塊的計算。所以，Ti+Mi與 Mi-1+Ci-1兩個操作并行，當T+M

2)T>C

假設(shè)T=20，M=1，C=10。該情況下雙緩沖工作過程圖和數(shù)據(jù)塊處理時間表如圖10及表8所示：

表8 數(shù)據(jù)塊處理時間表(緩沖區(qū)大小<<工作區(qū)大小，T>C)

從圖10和表8可知：數(shù)據(jù)塊輸入完成后進行數(shù)據(jù)傳輸，同時下一數(shù)據(jù)塊開始輸入，傳輸完成便進行計算。因此，Ti與Mi-1+Ci-1兩個操作并行，當T>C+M時，該情況下數(shù)據(jù)的處理時間為T。進一步分析當C

所以，在緩沖區(qū)大小遠小于工作區(qū)大小時，當TC時，處理時間為T。除前2塊數(shù)據(jù)塊外，系統(tǒng)對每一塊數(shù)據(jù)的處理時間為Max(T,C)。在深入分析發(fā)現(xiàn)輸入、傳輸、輸出三個過程是并行的，由于數(shù)據(jù)的傳輸在內(nèi)存中進行速度非常的快，即M遠小于T和C，所以可得到上述結(jié)論，也可以把這種情況下的時間函數(shù)準確表示為Max(T,M,C)。

綜上所述在緩沖區(qū)大小等于工作區(qū)大小時，系統(tǒng)對每一數(shù)據(jù)塊的處理時間為Max(T,C+M)；當緩沖大小遠小于工作區(qū)大小時，系統(tǒng)對每一塊數(shù)據(jù)處理時間為Max(T,M,C)。

4 總結(jié)

在系統(tǒng)按單道方式運行，并按非搶占方式調(diào)度，進程切換所花時間忽略不計的前提下，在單緩沖機制中，當緩沖區(qū)大小等于工作區(qū)大小時，系統(tǒng)對1個數(shù)據(jù)塊的處理時間函數(shù)為Max(C,T)+M；當緩沖區(qū)遠小于工作區(qū)大小，系統(tǒng)對每塊數(shù)據(jù)塊的計算函數(shù)也為Max(C,T+M)；在雙緩沖機制中，當緩沖區(qū)大小等于工作區(qū)大小時，系統(tǒng)對1個數(shù)據(jù)塊的處理時間函數(shù)為Max(T,C+M)。當T

參考文獻：

[1] 湯小丹，梁紅兵，哲鳳屏，等.計算機操作系統(tǒng)[M].第四版.西安:西安電子科技大學(xué)出版社，2014.

[2] STALLINGS W.Operating systems internals and design principles[M].6th ed.北京：機械工業(yè)出版社，2010.

[3] 許曰濱，孫英華，趙 毅，等.計算機操作系統(tǒng)[M].第一版.北京：北京郵電大學(xué)出版社，2007.

[4] 范 策，李 暢，黃紅桃，等.操作系統(tǒng)教程[M].第一版.北京：北京清華大學(xué)學(xué)研大廈A座，2011.

[5] 費翔林，駱 斌.操作系統(tǒng)教程[M].第五版.北京:高等教育出版社，2014.

[6] 孫鐘秀，費翔林，駱 斌，等.操作系統(tǒng)教程[M].第三版.北京:高等教育出版社，2003.

[7] 張麗芬，劉美華.操作系統(tǒng)原理教程[M].第三版.北京:電子工業(yè)出版社，2013.

[8] 謝青松.操作系統(tǒng)原理[M].第一版.北京:人民郵電出版社，2005.

[9] 王 紅.操作系統(tǒng)原理及運用(Linux)[M].第一版.北京：中國水利電出版社，2005.

[10] DAVIS W S，RAJKUMAR T M.Operating Systems:Systematic View[M].5th ed.北京：電子工業(yè)出版社，2003.