江 波

(賀州學(xué)院 計(jì)算機(jī)科學(xué)與工程系,廣西 賀州 542800)

讀者優(yōu)先級(jí)調(diào)度和寫者優(yōu)先級(jí)調(diào)度算法的改進(jìn)

江 波

(賀州學(xué)院 計(jì)算機(jī)科學(xué)與工程系,廣西 賀州 542800)

用P/V操作來(lái)解決操作系統(tǒng)中的讀寫者問題,是并發(fā)技術(shù)的基本功能。文章對(duì)讀者具有優(yōu)先權(quán)、寫者具有優(yōu)先權(quán)和讀者/寫者公平競(jìng)爭(zhēng)算法進(jìn)行研究,并對(duì)讀者優(yōu)先和寫者優(yōu)先算法進(jìn)行改進(jìn)。仿真實(shí)驗(yàn)表明,改進(jìn)的算法在各種測(cè)試數(shù)據(jù)下能用正確的時(shí)序解決讀寫者問題,對(duì)臨界資源的訪問也是正確的。

P/V操作;讀者優(yōu)先級(jí)調(diào)度;寫者優(yōu)先級(jí)調(diào)度;讀者與寫者公平競(jìng)爭(zhēng)

1 引 言

并發(fā)是操作系統(tǒng)的一個(gè)基本特征,是操作系統(tǒng)設(shè)計(jì)的基礎(chǔ)[1]P157-169。在早期的多道程序設(shè)計(jì)系統(tǒng)中,一個(gè)關(guān)鍵的問題就是要解決并發(fā)進(jìn)程中的同步、互斥和死鎖,這也是研究者所關(guān)注的熱點(diǎn)[2]P203-206。隨著計(jì)算機(jī)技術(shù)和網(wǎng)絡(luò)技術(shù)的不斷發(fā)展,又涌現(xiàn)出對(duì)稱多處理器和分布式操作系統(tǒng)(如集群系統(tǒng)、對(duì)等網(wǎng)絡(luò)系統(tǒng)和網(wǎng)格等),同步和互斥在這些新出現(xiàn)的操作系統(tǒng)中也得到了擴(kuò)充和更新[3]P58-72。進(jìn)程間通信是用P/V操作來(lái)實(shí)現(xiàn)讀寫者問題,其解決方案主要有讀者具有優(yōu)先權(quán)、寫者具有優(yōu)先權(quán)、讀者與寫者公平競(jìng)爭(zhēng)方案[4]P65-69。

2 P/V操作實(shí)現(xiàn)讀/寫者問題

讀/寫者問題需要為數(shù)據(jù)庫(kù)訪問建立了一個(gè)模型:具有一個(gè)數(shù)據(jù)區(qū)(可以是一個(gè)文件、主存的一個(gè)空間塊,或者是一組寄存器),多個(gè)進(jìn)程可以其數(shù)據(jù);存在一些只讀數(shù)據(jù)進(jìn)程(reader,讀者)和一些寫數(shù)據(jù)的進(jìn)程(writer,寫者)。

2.1 讀者優(yōu)先級(jí)調(diào)度

讀者優(yōu)先級(jí)調(diào)度必須滿足兩個(gè)條件:

2.1.1 有寫者正在寫數(shù)據(jù)時(shí),讀者必須等待。

2.1.2 無(wú)讀者正在讀數(shù)據(jù)時(shí),寫者才可以寫數(shù)據(jù)。

為了滿足這兩個(gè)條件,引入記錄當(dāng)前正在運(yùn)行的讀者進(jìn)程數(shù)(ReaderCount,全局整型量), ReaderCount賦初值0,當(dāng)一個(gè)讀者進(jìn)程進(jìn)入系統(tǒng)時(shí),ReaderCount執(zhí)行加1操作;當(dāng)ReaderCount由0變?yōu)閘時(shí),表示第一個(gè)讀者進(jìn)程進(jìn)入該系統(tǒng),需要該讀者進(jìn)程對(duì)控制寫者進(jìn)程的互斥信號(hào)量mutex-wsem執(zhí)行P操作,以便與寫者進(jìn)程互斥;當(dāng)ReaderCount由非0值增加時(shí),表示不是第一個(gè)讀者進(jìn)程進(jìn)入系統(tǒng),不需要再對(duì)互斥信號(hào)量mutex-wsem執(zhí)行P操作;當(dāng)有讀者進(jìn)程退出系統(tǒng)時(shí),必須對(duì)ReaderCount執(zhí)行減1操作;當(dāng)如ReaderCount等于0時(shí),表明最后一個(gè)讀者進(jìn)程退出系統(tǒng),需要該讀者進(jìn)程對(duì)mutex-wsem執(zhí)行V操作,讓寫者進(jìn)程能夠進(jìn)入系統(tǒng)。

2.2 寫者優(yōu)先級(jí)調(diào)度

寫者優(yōu)先級(jí)調(diào)度必須滿足兩個(gè)條件:

2.2.1 無(wú)寫者時(shí)才允許讀者讀數(shù)據(jù)。

2.2.2 喚醒時(shí)優(yōu)先考慮寫者。

在讀者優(yōu)先算法的基礎(chǔ)上,引入寫者處于等待狀態(tài)的注冊(cè)標(biāo)記(mutex-rsem,互斥信號(hào)量),用于在寫者進(jìn)程到達(dá)時(shí)封鎖后續(xù)的讀者進(jìn)程。引入記錄當(dāng)前寫者數(shù)(WriterCount,全局整型量),當(dāng)WriterCount等于0時(shí),表明所有的寫者執(zhí)行的操作結(jié)束,需要釋放讀者進(jìn)程等待隊(duì)列中的一個(gè)讀者。

2.3 讀者與寫者公平競(jìng)爭(zhēng)算法

讀者與寫者公平競(jìng)爭(zhēng)要求讀者和寫者完全遵循先來(lái)先服務(wù)的原則使用數(shù)據(jù)。

讀者優(yōu)先算法之造成寫者暫時(shí)不能訪問數(shù)據(jù),被隨后源源不斷而來(lái)的讀者插隊(duì)而長(zhǎng)時(shí)間掛起,主要的原因是:如果已經(jīng)有讀者在讀數(shù)據(jù),則說明目前沒有寫者在訪問數(shù)據(jù),因此該讀者不需要再進(jìn)行與寫者進(jìn)程間對(duì)數(shù)據(jù)的競(jìng)爭(zhēng)嘗試,從而直接進(jìn)入讀狀態(tài)。該算法的最大缺陷是只考慮到有沒有寫者正在訪問數(shù)據(jù),卻沒有考慮可能已經(jīng)有寫者在等待訪問數(shù)據(jù)。同理,寫者優(yōu)先算法同樣具有缺陷。

3 讀/寫者算法的改進(jìn)

3.1 改進(jìn)的讀者優(yōu)先級(jí)調(diào)度算法

當(dāng)有多個(gè)讀者進(jìn)程共享一個(gè)數(shù)據(jù)區(qū),根據(jù)所執(zhí)行的不同任務(wù),將讀者進(jìn)行分為兩組,分屬1組和2組。不同組中的讀者不會(huì)同時(shí)讀數(shù)據(jù),但同組中的讀者可以同時(shí)讀數(shù)據(jù)。為了記錄兩組當(dāng)前正在運(yùn)行的讀者進(jìn)程數(shù),分別引入全局整型量Reader1Count、Reader2Count和互斥信號(hào)量mutex-Reader1Count、mutex-Reader2Count。

3.2 改進(jìn)的寫者優(yōu)先級(jí)調(diào)度

參照改進(jìn)的讀者優(yōu)先級(jí)調(diào)度算法,寫者也分屬1組和2組。不允許多個(gè)寫者(同組或者不同組)同時(shí)對(duì)數(shù)據(jù)進(jìn)行寫操作,每個(gè)寫者在已知有本組寫者正在寫文件的情況下,進(jìn)入等待狀態(tài),但具有比另外一組中處于等待狀態(tài)的寫者優(yōu)先的喚醒權(quán)。為了記錄兩組當(dāng)前正在運(yùn)行的寫者進(jìn)程數(shù),分別引入全局整型量Writer1Count、Writer2Count和互斥信號(hào)量mutex Writer1Count、mutex Writer2Count。

4 系統(tǒng)仿真實(shí)驗(yàn)

測(cè)試系統(tǒng)為Windows XP,編程工具為Microsoft Visual C++6.0,在thread.dat文件中輸入讀者和寫者狀態(tài),運(yùn)行程序。在選擇界面選擇所要使用的算法(如圖1),就會(huì)得出讀者和寫者執(zhí)行的序列。4.1測(cè)試的過程必須包含各方面的數(shù)據(jù)(如表1所示),以便對(duì)算法更好地進(jìn)行測(cè)試。由于只是判斷這兩個(gè)算法的功能以及它們的運(yùn)行結(jié)果是否和預(yù)知的結(jié)果一致,因此在實(shí)驗(yàn)的過程中采用黑盒測(cè)試方法,考慮三種情況:

圖1 算法選擇界面

4.1.1 輸入的所有線程都是讀者,讀者在同一時(shí)刻競(jìng)爭(zhēng)資源。

4.1.2 輸入的所有線程都是寫者,寫者在同一時(shí)刻競(jìng)爭(zhēng)資源。

4.1.3 輸入的線程包含讀者和寫者,讀者和寫者在同一時(shí)刻競(jìng)爭(zhēng)資源。

4.2 讀者優(yōu)先級(jí)調(diào)度算法測(cè)試結(jié)果

采用讀者優(yōu)先級(jí)調(diào)度算法對(duì)三組測(cè)試數(shù)據(jù)進(jìn)行實(shí)驗(yàn),得到的結(jié)果如圖2-4所示。

從圖2-4可以看出,實(shí)驗(yàn)結(jié)果和預(yù)期的結(jié)果一致。

4.3 寫者優(yōu)先算法測(cè)試結(jié)果

采用寫者優(yōu)先級(jí)調(diào)度算法對(duì)三組測(cè)試數(shù)據(jù)進(jìn)行實(shí)驗(yàn),得到的結(jié)果如圖5-7所示。

圖5 第一組數(shù)據(jù)的寫者優(yōu)先算法結(jié)果

從圖5-7可以看出,實(shí)驗(yàn)結(jié)果和預(yù)期的結(jié)果一致。

5 結(jié)論

用P/V操作來(lái)解決操作系統(tǒng)中的讀寫者問題,是并發(fā)技術(shù)的基本功能。通過本文的仿真實(shí)驗(yàn)結(jié)果可以看出。改進(jìn)的算法能正確的解決讀寫者問題,在各種測(cè)試數(shù)據(jù)下能用正確的時(shí)序解決問題,對(duì)臨界資源的訪問也是正確的,給每個(gè)線程設(shè)置一個(gè)時(shí)間變量來(lái)記錄等待時(shí)間,當(dāng)?shù)却龝r(shí)間過長(zhǎng)時(shí),可以提高其優(yōu)先級(jí),讓其進(jìn)入臨界區(qū)執(zhí)行,從而解決餓死問題。

[1]B.Brandenburg,J.Calandrino,and J.Anderson.On the scalability of real-time scheduling algorithms on multicore platforms:A case study.In Proc.of the 29th IEEE Real-Time Systems Symposium,2008.

[2]申雪琴.計(jì)算機(jī)操作系統(tǒng)中死鎖問題研究.計(jì)算機(jī)與數(shù)字工程,2008,36(7).

[3]張俊然,陳 波.基于進(jìn)化算法的嵌入式操作系統(tǒng)并發(fā)性能測(cè)試.計(jì)算機(jī)工程,2005,31(23).

[4]王欣明,金蓓弘,張 昕.用不對(duì)稱的P/V操作設(shè)計(jì)并發(fā)算法[J].計(jì)算機(jī)工程與應(yīng)用,2005,41(12).

The Improved Algorithms of Readers Priority Scheduling and Writers Priority Scheduling

Jiang Bo

(Department of Computer Science and Engineering,Hezhou University,Guangxi Hezhou,542800,China)

To solve the problem of reading and writing problems in the operating system with the P/V operations is a basic function in the concurrency control technique.In this paper,we study the readers priority scheduling algorithm,writers priority scheduling algorithm and readers/writer algorithm for fair competition and improve the readers priority scheduling algorithm,writers priority scheduling algorithm.Simulation results show that the improved algorithm can solve the problem of reading and writing problems correctly.In a variety of test data,it can be used under the right timing to solve the problem and the access to critical resources is corrected.

P/V operations;readers priority scheduling algorithm;writers priority scheduling algorithm;readers/writer algorithm for fair competition

TP316.4

A

1673-8861(2010)02-0122-04

2010-04-01

江 波(1970-),男,廣西賀州市人,賀州學(xué)院講師。主要研究方向:數(shù)據(jù)挖掘、計(jì)算機(jī)教育、網(wǎng)絡(luò)安全。