信息與計(jì)算科學(xué)畢業(yè)論文通用數(shù)據(jù)庫(kù)的c語言實(shí)現(xiàn)

1、<p><b>　　本科畢業(yè)論文</b></p><p><b>　?。?0 屆）</b></p><p>　　通用數(shù)據(jù)庫(kù)的C語言實(shí)現(xiàn)</p><p>　　所在學(xué)院 </p><p>　　專業(yè)班級(jí) 信息與計(jì)算科學(xué)

2、 </p><p>　　學(xué)生姓名 學(xué)號(hào) </p><p>　　指導(dǎo)教師 職稱 </p><p>　　完成日期 年 月 </p><p><b>　　摘要</b></p>

3、<p>　　Dbm是在UNIX系統(tǒng)中很流行的數(shù)據(jù)庫(kù)函數(shù)庫(kù), 其主要的兩個(gè)特點(diǎn)是動(dòng)態(tài)散列算法和鍵值查找方式. 至今, dbm有許多版本, 許多的不足的得到了改進(jìn). 但是, 這些實(shí)現(xiàn)都有一個(gè)根本的缺點(diǎn)，就是它們都沒有提供并發(fā)控制(如記錄鎖). 本文就是針對(duì)dbm數(shù)據(jù)庫(kù)函數(shù)庫(kù)的這點(diǎn)不足, 開發(fā)一個(gè)類似的dbm庫(kù)--MyDbm, 增加了并發(fā)控制機(jī)制, 從而允許多進(jìn)程同時(shí)更新同一數(shù)據(jù)庫(kù). 具體并發(fā)控制策略主要有兩個(gè)部分: 一是采用進(jìn)

4、程非集中式訪問數(shù)據(jù)庫(kù); 二是對(duì)文件加鎖時(shí), 采用細(xì)瑣, 即加鎖鎖定的區(qū)域?yàn)槲募械哪硞€(gè)字節(jié)段而非整個(gè)文件, 從而在理論上能提供更高的并發(fā)度.</p><p>　　關(guān)鍵字: dbm數(shù)據(jù)庫(kù)函數(shù)庫(kù); 并發(fā); 非集中式訪問; 文件鎖</p><p><b>　　Abstract</b></p><p>　　dbm is very popular dat

5、abase library in the UNIX system. Two main features of dbm are the dynamic hashing algorithm and the search fashion of key value. So far, there are many Dbm versions, many of the shortage have been improved. However, one

6、 fundamental drawback of the existing implementations is that they can not provide concurrency control (such as record locks). With respect to the shortcoming of dbm database, in the thesis, a kind of dbm library, MyDbm,

7、 is developed. In the new dbm library</p><p>　　Keywords: DBM database library; Concurrent control; Non-centralized access; File lock</p><p><b>　　目錄</b></p><p><b>　

8、　中文摘要I</b></p><p>　　英文摘要錯(cuò)誤!未定義書簽。</p><p><b>　　1前言1</b></p><p><b>　　2并發(fā)2</b></p><p><b>　　2.1 讀鎖2</b></p><p>&

9、lt;b>　　2.2 寫鎖2</b></p><p><b>　　2.3 粗鎖2</b></p><p><b>　　2.4 細(xì)鎖2</b></p><p>　　3進(jìn)程訪問數(shù)據(jù)庫(kù)的方式4</p><p>　　3.1 集中式訪問數(shù)據(jù)庫(kù)4</p><p&g

10、t;　　3.2 非集中式訪問數(shù)據(jù)庫(kù)4</p><p><b>　　4實(shí)現(xiàn)概述6</b></p><p><b>　　5具體實(shí)現(xiàn)9</b></p><p>　　5.1 MyDbm_Open9</p><p>　　5.2 MyDbm_Close錯(cuò)誤!未定義書簽。</p><

11、p>　　5.3 MyDbm_Select10</p><p>　　5.4 MyDbm_Insert12</p><p>　　5.5 MyDbm_Update, MyDbm_Rewind和MyDbm_NextRecord13</p><p><b>　　6性能分析15</b></p><p>　　6.1 單進(jìn)

12、程的結(jié)果16</p><p>　　6.2 多進(jìn)程的結(jié)果17</p><p><b>　　7小結(jié)18</b></p><p><b>　　參考文獻(xiàn)19</b></p><p>　　致謝錯(cuò)誤!未定義書簽。</p><p><b>　　附件20</b&g

13、t;</p><p><b>　　前言</b></p><p>　　dbm是在UNIX系統(tǒng)中很流行的數(shù)據(jù)庫(kù)函數(shù)庫(kù), 它是由Ken Thompson開發(fā)的, 當(dāng)時(shí)使用了動(dòng)態(tài)散列結(jié)構(gòu). 最初, dbm與V7系統(tǒng)一起提供, 并在所有的BSD版本中出現(xiàn), 其中也包含在SVR4的BSD兼容函數(shù)庫(kù)中[AT&T 1990c]. BSD的開發(fā)者擴(kuò)充了dbm函數(shù)庫(kù), 并將其改名

14、為ndbm. ndbm函數(shù)庫(kù)包括在BSD和SVR4中. ndbm函數(shù)被標(biāo)準(zhǔn)化后成為Single UNIX Specification的XSI擴(kuò)展部分[1]. 而在Linux系統(tǒng)上, 開發(fā)者們用gdbm庫(kù)來支持dbm函數(shù)庫(kù)和ndbm函數(shù)庫(kù)[1]. dbm函數(shù)庫(kù)所管理的數(shù)據(jù)庫(kù)是一個(gè)輕量級(jí)的數(shù)據(jù)庫(kù), 不是標(biāo)準(zhǔn)意義上的數(shù)據(jù)庫(kù), 不支持SQL(不過可以在它的基礎(chǔ)上開發(fā)), 純粹以二進(jìn)制儲(chǔ)存的一種數(shù)據(jù)庫(kù), 常用于系統(tǒng)底層的數(shù)據(jù)庫(kù), 在其他一些很少更

15、新內(nèi)容的地方也可以使用[2]. </p><p>　　dbm函數(shù)庫(kù)主要的兩個(gè)特點(diǎn)是動(dòng)態(tài)散列算法和鍵值查找方式. Seltzer和Yigit在文中詳細(xì)介紹了dbm函數(shù)庫(kù)使用的動(dòng)態(tài)散列結(jié)構(gòu)的歷史. 采用動(dòng)態(tài)散列算法時(shí)在查找數(shù)據(jù)時(shí)非?？焖? 當(dāng)然其付出的代價(jià)就是插入數(shù)據(jù)異常的緩慢[1]. 另外對(duì)于鍵值查找方式, dbm數(shù)據(jù)庫(kù)是通過包括兩個(gè)基本元素?cái)?shù)據(jù)塊, 一塊是想要保存起來的數(shù)據(jù), 另一塊是對(duì)其進(jìn)行檢索時(shí)用做關(guān)鍵字的數(shù)

16、據(jù). 對(duì)于每個(gè)dbm數(shù)據(jù)庫(kù)而言, 保存在其中的每一個(gè)數(shù)據(jù)塊都必須有一個(gè)獨(dú)一無二的關(guān)鍵字. 對(duì)于關(guān)鍵字和數(shù)據(jù)本身倒沒有什么限制, 對(duì)使用超長(zhǎng)數(shù)據(jù)或超長(zhǎng)關(guān)鍵字的情況也沒有定義什么錯(cuò)誤. 技術(shù)規(guī)范里倒是允許在具體實(shí)現(xiàn)時(shí)將關(guān)鍵字/數(shù)據(jù)對(duì)的最大長(zhǎng)度限制在1024個(gè)字節(jié), 但這個(gè)限制通常并沒有什么意義, 因?yàn)榫唧w實(shí)現(xiàn)出來的東西往往比技術(shù)規(guī)范的要求更靈活[2]. 關(guān)鍵字的取值被用做檢索儲(chǔ)存數(shù)據(jù)的索引, 就如同書簽一般. </p><

17、;p>　　至今, dbm有許多版本, 許多的不足的得到改進(jìn). 但是, 這些實(shí)現(xiàn)都有一個(gè)根本的缺點(diǎn)是: 他們都不支持多個(gè)進(jìn)程對(duì)數(shù)據(jù)庫(kù)的并發(fā)更新. 它們都沒有提供并發(fā)控制(如記錄鎖). 絕大部分商用數(shù)據(jù)庫(kù)函數(shù)庫(kù)提供多進(jìn)程同時(shí)更新數(shù)據(jù)庫(kù)所需要的并發(fā)控制[3]. 這些系統(tǒng)一般都使用建議記錄鎖, 不過, 它們也常常實(shí)現(xiàn)自己的鎖原語, 以避免為獲得一把無競(jìng)爭(zhēng)的鎖而需的系統(tǒng)調(diào)用開銷[4]. 本文就是針對(duì)dbm數(shù)據(jù)庫(kù)函數(shù)庫(kù)的這點(diǎn)不足, 開發(fā)一個(gè)類

18、似的dbm庫(kù)MyDbm, 但增加了并發(fā)控制機(jī)制, 從而允許多進(jìn)程同時(shí)更新同一數(shù)據(jù)庫(kù). 具體并發(fā)控制主要有兩個(gè)部分, 一是采用進(jìn)程非集中式訪問數(shù)據(jù)庫(kù). 二是對(duì)文件加鎖時(shí). </p><p>　　接下來, 本文將首先介紹進(jìn)程訪問數(shù)據(jù)庫(kù)的兩種方式和文件加鎖的概念. </p><p><b>　　并發(fā)</b></p><p>　　并發(fā)控件的方式之一是對(duì)

19、進(jìn)程要訪問的文件進(jìn)行加鎖. 按訪問文件的方式來分, 可將鎖分為讀鎖和寫鎖:</p><p><b>　　讀鎖</b></p><p>　　讀鎖相對(duì)于文件的讀操作, 即文件必須從操作系統(tǒng)那獲取一把讀鎖, 才有權(quán)限來讀取文件的內(nèi)容[4]. 由于讀操作不影響文件內(nèi)容, 因而同一時(shí)間可以有多個(gè)進(jìn)程獲取同一文件的讀鎖. 其數(shù)量?jī)H由系統(tǒng)的限制進(jìn)程數(shù)決定.</p>&

20、lt;p><b>　　寫鎖</b></p><p>　　寫鎖相對(duì)于文件的寫操作, 只有獲取了寫鎖, 進(jìn)程才能修改文件的內(nèi)容[1]. 由于寫操作將修改文件內(nèi)容(不管你是否真的有修改過), 故同一時(shí)間只能有一個(gè)進(jìn)程擁有寫鎖. 否則, 將導(dǎo)致文件內(nèi)容的不一致.</p><p>　　讀鎖與寫鎖的關(guān)系是互斥的, 即一個(gè)文件不能同時(shí)加上這兩把鎖[5]. 當(dāng)文件首先被一個(gè)進(jìn)程

21、加上讀鎖, 那么它將拒絕被加上寫鎖, 但可以被加上其他進(jìn)程的讀鎖. 只有當(dāng)文件上的所有讀鎖被釋放, 其它進(jìn)程才有可能獲取該文件的寫鎖. 但文件若被一個(gè)進(jìn)程加上寫鎖, 其他進(jìn)程的讀鎖和寫鎖的申請(qǐng)都將失敗, 直到擁有該文件的進(jìn)程釋放了其寫鎖. </p><p>　　從粒度粗細(xì)的角度, 鎖又可以被分為粗鎖和細(xì)鎖.</p><p><b>　　粗鎖</b></p>

22、<p>　　若獲取的文件鎖的鎖定范圍是整個(gè)文件, 就稱之為粗鎖[6]. 由于粗鎖鎖定了整個(gè)文件, 加上讀寫鎖的互斥性, 因而其在最大程度上限制了并發(fā)性. 以上對(duì)讀鎖和寫鎖的介紹就是基于粗鎖的, 因而可見其對(duì)進(jìn)程并發(fā)度的限制.</p><p>　　假設(shè)要修改一個(gè)大文件的一小段內(nèi)容, 則在一個(gè)進(jìn)程加了寫鎖之后, 文件的其他內(nèi)容就不允許其他進(jìn)程進(jìn)行讀取和修改, 這對(duì)于數(shù)據(jù)庫(kù)這樣的大型文件集是無法接受的.&

23、lt;/p><p><b>　　細(xì)鎖</b></p><p>　　細(xì)瑣就是為了改進(jìn)粗鎖的并發(fā)性而提出來的. 其對(duì)文件加讀寫鎖時(shí), 是針對(duì)文件的某一區(qū)域, 而非整個(gè)文件[3]. 因而, 在同一時(shí)間, 一個(gè)文件可以擁有多把讀鎖和寫鎖. 但對(duì)于同一區(qū)域, 依然體現(xiàn)讀寫鎖的互斥性.</p><p>　　從以上介紹可看出, 細(xì)瑣在進(jìn)程并發(fā)性上相對(duì)于粗鎖有巨大

24、優(yōu)勢(shì), 特別在于數(shù)據(jù)庫(kù)這種大型的結(jié)構(gòu)化文件中, 更加體現(xiàn)的淋漓盡致. 當(dāng)然, 細(xì)瑣相對(duì)粗鎖實(shí)現(xiàn)起來更加復(fù)雜, 也需要更多的系統(tǒng)資源, 但相比其獲得的并發(fā)度, 這種交換是十分有意義的. 因而在實(shí)現(xiàn)MyDbm數(shù)據(jù)庫(kù)時(shí), 采用了細(xì)瑣來實(shí)現(xiàn)并發(fā)控制.</p><p>　　這里對(duì)并發(fā)進(jìn)行討論, 所依據(jù)的是對(duì)數(shù)據(jù)庫(kù)函數(shù)庫(kù)的簡(jiǎn)單需求, 商業(yè)系統(tǒng)一般有更多的需要[7].</p><p>　　進(jìn)程訪問數(shù)據(jù)庫(kù)

25、的方式</p><p>　　當(dāng)多個(gè)進(jìn)程訪問數(shù)據(jù)庫(kù)時(shí), 可以采用集中式和非集中式這兩個(gè)方案來實(shí)現(xiàn)庫(kù)函數(shù)[8]. 使用這兩種方案的數(shù)據(jù)庫(kù)系統(tǒng)都有[8], 下面將分別介紹.</p><p><b>　　集中式訪問數(shù)據(jù)庫(kù)</b></p><p>　　其實(shí)現(xiàn)方式是, 讓一個(gè)進(jìn)程作為管理數(shù)據(jù)庫(kù)的管理員, 只有它才能對(duì)數(shù)據(jù)庫(kù)文件進(jìn)行訪問和相關(guān)操作, 其他進(jìn)程

26、想要和數(shù)據(jù)庫(kù)通信只有通過IPC(進(jìn)程間通信機(jī)制[6])機(jī)制和管理進(jìn)程聯(lián)系, 從而間接的操作數(shù)據(jù)庫(kù). 圖3.1描述了集中式訪問數(shù)據(jù)庫(kù)的過程.</p><p>　　圖3.1集中式訪問數(shù)據(jù)庫(kù)</p><p><b>　　非集中式訪問數(shù)據(jù)庫(kù)</b></p><p>　　每個(gè)進(jìn)程通過庫(kù)函數(shù)獨(dú)立申請(qǐng)并發(fā)控制(加鎖), 然后再訪問數(shù)據(jù)庫(kù)文件[9]. 圖3.2

27、描述了非集中式訪問數(shù)據(jù)庫(kù)的過程.</p><p>　　圖3.2非集中式訪問數(shù)據(jù)庫(kù)</p><p>　　集中式訪問的優(yōu)點(diǎn)是能夠根據(jù)需要對(duì)操作模式進(jìn)行調(diào)整. 例如, 管理進(jìn)程通過給不同用戶進(jìn)程分配不同的優(yōu)先級(jí). 優(yōu)先級(jí)將影響管理進(jìn)程對(duì)MyDbm數(shù)據(jù)庫(kù)接口的調(diào)用.</p><p>　　而非集中式訪問很難做到這一點(diǎn), 在這種情況下只能依賴操作系統(tǒng)內(nèi)核的調(diào)度策略. 例如, 當(dāng)

28、3個(gè)用戶進(jìn)程同時(shí)調(diào)用MyDbm數(shù)據(jù)庫(kù)的調(diào)用接口對(duì)數(shù)據(jù)文件加鎖時(shí), 誰會(huì)分配到鎖呢? 結(jié)果只能依賴操作系統(tǒng)在實(shí)際運(yùn)行時(shí)調(diào)度. </p><p>　　集中式訪問的另一個(gè)優(yōu)點(diǎn)是, 復(fù)原要比非集中式方法容易[10]. 在集中式方法中, 所有狀態(tài)信息都集中保存在一個(gè)地方, 所以如若殺死了數(shù)據(jù)庫(kù)管理進(jìn)程, 只需查看該處以識(shí)別需要解決的的未完成事務(wù), 然后將數(shù)據(jù)庫(kù)恢復(fù)到一致狀態(tài). </p><p>　　

29、但是非集中式在細(xì)鎖策略下, 并發(fā)度較好. 從上面2圖可看出, 由于集中式訪問數(shù)據(jù)庫(kù)是通過數(shù)據(jù)庫(kù)管理進(jìn)程完成, 所以同一時(shí)間只有單進(jìn)程訪問數(shù)據(jù)庫(kù). 但非集中式訪問通過細(xì)鎖來鎖定文件的不同區(qū)域, 可實(shí)現(xiàn)較多進(jìn)程同時(shí)訪問數(shù)據(jù)庫(kù). 在多進(jìn)程訪問數(shù)據(jù)庫(kù)時(shí), 無疑非集中式比集中式具有優(yōu)勢(shì). </p><p>　　還可以通過融合這兩種方式的優(yōu)點(diǎn), 實(shí)現(xiàn)半集中式訪問數(shù)據(jù)庫(kù)的訪問[11]. 即數(shù)據(jù)庫(kù)管理進(jìn)程數(shù)量擴(kuò)充為多個(gè), 他們采

30、用非集中式訪問數(shù)據(jù)庫(kù), 用戶進(jìn)程采用集中式方法, 通過IPC跟某一數(shù)據(jù)庫(kù)管理進(jìn)程通信, 間接訪問數(shù)據(jù)庫(kù). 由于這種方法實(shí)現(xiàn)起來比較復(fù)雜, 故暫時(shí)不采用. </p><p>　　綜上所述, MyDbm數(shù)據(jù)庫(kù)實(shí)現(xiàn)時(shí)采用非集中式訪問的方法. </p><p><b>　　實(shí)現(xiàn)概述</b></p><p>　　大多數(shù)訪問數(shù)據(jù)庫(kù)的函數(shù)庫(kù)使用兩個(gè)文件來存儲(chǔ)

31、信息: 一個(gè)索引文件和一個(gè)數(shù)據(jù)文件. 索引文件包含索引值(鍵)和指向數(shù)據(jù)文件中對(duì)應(yīng)數(shù)據(jù)記錄的指針. 有許多技術(shù)可用來組織索引文件, 以提高按鍵查詢的速度和效率. 這里采用固定大小的散列表來組織索引文件結(jié)構(gòu), 并采用鏈表來解決散列沖突. 在實(shí)現(xiàn)過程中, 用.idx后綴的文件作為索引文件, .dat后綴的文件作為數(shù)據(jù)文件(UNIX不以后綴來判別文件類型, 此后綴只為本程序識(shí)別文件所用). </p><p>　　索引文

32、件的基本單位: 索引, 由鍵和由null結(jié)尾的字符串組成. 這樣的好處是函數(shù)簡(jiǎn)單, 也使數(shù)據(jù)庫(kù)文件在不同平臺(tái)間移植比較容易(如果采用二進(jìn)制, 就會(huì)碰到不同平臺(tái)間二進(jìn)制存儲(chǔ)格式不統(tǒng)一的問題). 當(dāng)然其代價(jià)是更多的磁盤空間. </p><p>　　在本文的實(shí)現(xiàn)中, 每個(gè)索引的鍵, 只有一條對(duì)應(yīng)的記錄, 有些數(shù)據(jù)庫(kù)系統(tǒng)允許多條記錄使用相同的鍵, 并提供方法訪問與一個(gè)鍵有關(guān)的所用記錄. 另外, 由于只有一個(gè)索引文件, 所

33、以每條記錄只有一個(gè)鍵(不支持多鍵). 當(dāng)然對(duì)于多鍵的支持, 只需添加索引文件, 每個(gè)鍵對(duì)應(yīng)一個(gè)索引文件, 當(dāng)修改記錄時(shí), 同時(shí)更新所用索引文件即可. </p><p>　　索引文件的結(jié)構(gòu)如圖4.1:</p><p>　　圖4.1 索引文件結(jié)構(gòu)</p><p>　　這里的指針是由4個(gè)ASCII字符組成, 這樣保證了可移植性. 指針由4個(gè)字符組成也限制了文件最大的字節(jié)數(shù)

34、為10000B, 當(dāng)然這種限制可以修改指針的字符數(shù)加以解決. </p><p>　　空閑索引指針指向空閑鏈表. 當(dāng)一條數(shù)據(jù)被刪除時(shí), 對(duì)應(yīng)的索引記錄也被刪除, 其偏移量將被加到空閑鏈表中, 以重復(fù)利用此文件空間. </p><p>　　鏈表指針個(gè)數(shù)可是隨意定制的, 具有相同哈希值的鍵將被放入相同的鏈表中, 鏈表指針指向了鏈表的第一元素, 若其值為0, 表示該鏈表為空. </p>

35、<p>　　以上這兩個(gè)部分組成索引文件的第一行. 接下的內(nèi)容就是索引記錄, 索引記錄的結(jié)構(gòu)如圖4.2:</p><p>　　圖4.2 索引記錄結(jié)構(gòu)</p><p>　　鏈表指針指向同一鏈表的下一個(gè)元素, 若為0, 表示此記錄是該哈希鏈表的最后一條記錄. 通過這個(gè)區(qū)域, 可以訪問到這個(gè)鏈表的所有的記錄. </p><p>　　接下來是索引記錄長(zhǎng)度, 由于

36、索引記錄接下的內(nèi)容數(shù)據(jù)長(zhǎng)度是不定的, 必須通過這個(gè)區(qū)域來確定索引記錄的長(zhǎng)度. </p><p>　　鍵是存儲(chǔ)鍵值查找中的鍵值, 這是索引文件的關(guān)鍵部分. </p><p>　　該結(jié)構(gòu)中的兩個(gè)分隔符是為了分離各個(gè)不定長(zhǎng)的區(qū)域. </p><p>　　數(shù)據(jù)記錄的偏移量也是一個(gè)由字符組成的指針, 它指向了該記錄中的鍵所對(duì)應(yīng)的值, 在數(shù)據(jù)文件中的偏移量, 它和數(shù)據(jù)記錄的長(zhǎng)度

37、就能確定數(shù)據(jù)記錄的內(nèi)容了. </p><p>　　數(shù)據(jù)文件的結(jié)構(gòu)比較簡(jiǎn)單, 它只是簡(jiǎn)單的由一系列數(shù)據(jù)記錄組成. 數(shù)據(jù)記錄的格式如圖4.3:</p><p>　　圖4.3數(shù)據(jù)記錄格式</p><p>　　定位數(shù)據(jù)和確定長(zhǎng)度的信息都在索引文件中, 此文件主要負(fù)責(zé)的就是數(shù)據(jù)的存儲(chǔ). </p><p>　　以上是對(duì)數(shù)據(jù)庫(kù)文件結(jié)構(gòu)的大概解釋, 更多細(xì)節(jié)

38、將在下文中介紹. </p><p>　　MyDbm的數(shù)據(jù)庫(kù)函數(shù)庫(kù)接口主要分為兩大類: 數(shù)據(jù)庫(kù)連接類和數(shù)據(jù)庫(kù)存取類(這里的類是類別, 非面對(duì)對(duì)象思想中的類). </p><p>　　數(shù)據(jù)庫(kù)連接類負(fù)責(zé)打開和關(guān)閉數(shù)據(jù)庫(kù)文件, 其功能不像ADO.NET的DbConnection負(fù)責(zé)與數(shù)據(jù)庫(kù)的通信. 其主要有兩個(gè)接口函數(shù)MyDbm_Open和MyDbm_Close. 其功能和c函數(shù)庫(kù)中的fopen和

39、fclose類似, 只負(fù)責(zé)數(shù)據(jù)文件的打開和關(guān)閉. 其實(shí)MyDbm_Open和MyDbm_Close只是重新封裝UNIX系統(tǒng)提供文件操作類API的open()和close(). </p><p>　　數(shù)據(jù)庫(kù)存取類提供對(duì)數(shù)據(jù)的更新, 插入, 檢索, 其對(duì)應(yīng)的函數(shù)接口分別是: MyDbm_Update , MyDbm_Insert , MyDbm_Select. 還可以通過MyDbm_Rewind和MyDbm_ Ne

40、xtRrecord來遍歷數(shù)據(jù)庫(kù)數(shù)據(jù). 由于采用散列算法, 所以對(duì)訪問類型的操作十分的快, 但存儲(chǔ)上則性能將偏低. </p><p>　　應(yīng)用進(jìn)程通過數(shù)據(jù)庫(kù)函數(shù)庫(kù)訪問數(shù)據(jù)庫(kù)文件的過程如圖4.4:</p><p>　　圖4.4 應(yīng)用進(jìn)程訪問數(shù)據(jù)庫(kù)過程</p><p>　　接下來闡述MyDbm的具體實(shí)現(xiàn)細(xì)節(jié). </p><p><b>　

41、　具體實(shí)現(xiàn)</b></p><p>　　系統(tǒng)首先定義了DBHANDLE類型為void *, DBHANDLE類型表示對(duì)數(shù)據(jù)庫(kù)的一個(gè)有效引用, 用于隔離應(yīng)用程序和數(shù)據(jù)庫(kù)的現(xiàn)實(shí)細(xì)節(jié), 函數(shù)庫(kù)對(duì)數(shù)據(jù)庫(kù)操作都是通過DBHANDLE進(jìn)行的. </p><p>　　然后是數(shù)據(jù)庫(kù)結(jié)構(gòu)DB, 類似于C函數(shù)庫(kù)中的文件結(jié)構(gòu). 其中定義了索引文件號(hào)和數(shù)據(jù)文件號(hào)(UNIX系統(tǒng)訪問文件時(shí), 都會(huì)配一個(gè)文

42、件號(hào)給進(jìn)程), 索引記錄和數(shù)據(jù)記錄的緩沖區(qū)指針. 還有其它的一些狀態(tài)信息. </p><p>　　下面將通過介紹函數(shù)庫(kù)系統(tǒng)的接口函數(shù)來對(duì)整個(gè)函數(shù)庫(kù)做一個(gè)具體完整的介紹. 其中每個(gè)接口函數(shù)都會(huì)調(diào)用函數(shù)庫(kù)內(nèi)私有函數(shù)(除函數(shù)庫(kù)內(nèi)的函數(shù)外其它程序不能訪問), 私有函數(shù)的函數(shù)名前綴為一個(gè)下劃線.</p><p>　　MyDbm_Open</p><p>　　其函數(shù)原型為 DB

43、HANDLE MyDbm_Open(const char *pathName , int oflag , …);</p><p>　　其調(diào)用結(jié)構(gòu)如圖5.1:</p><p>　　圖5.1 MyDbm_Open 調(diào)用結(jié)構(gòu)</p><p>　　MyDbm_Open函數(shù)的參數(shù)與UNIX系統(tǒng)的Open調(diào)用相同. 如果調(diào)用者想要?jiǎng)?chuàng)建數(shù)據(jù)庫(kù)文件, 那么可選擇的第三個(gè)參數(shù)指

44、定文件權(quán)限. MyDbm_Open函數(shù)打開索引文件和數(shù)據(jù)文件, 在必要時(shí)初始化索引文件. 該函數(shù)調(diào)用_MyDbm_Alloc來為DB結(jié)構(gòu)分配空間, 并初始化此結(jié)構(gòu)并為其分配緩存. 調(diào)用者通過pathName參數(shù)指定數(shù)據(jù)庫(kù)文件名, 函數(shù)內(nèi)部添加后綴.idx以構(gòu)成數(shù)據(jù)庫(kù)索引文件的名字. </p><p>　　如果調(diào)用者要?jiǎng)?chuàng)建數(shù)據(jù)庫(kù)文件, 那么使用C函數(shù)庫(kù)<stdarg.h>中的可變參數(shù)函數(shù)以找到可選的第三

45、個(gè)參數(shù), 然后, 使用UNIX系統(tǒng)調(diào)用open來創(chuàng)建和打開索引文件和數(shù)據(jù)庫(kù)文件. 數(shù)據(jù)文件與索引文件的文件名是相同的, 只是后綴為.dat. 在建立數(shù)據(jù)庫(kù)的過程中, 函數(shù)會(huì)調(diào)用WriteLock(宏定義函數(shù))來數(shù)據(jù)庫(kù)文件加鎖. 并在創(chuàng)建結(jié)束后調(diào)用UnLock解鎖. 最后初始化索引文件相關(guān)內(nèi)容, 數(shù)據(jù)庫(kù)算創(chuàng)建完成. </p><p>　　如果在打開或創(chuàng)建任一數(shù)據(jù)文件時(shí)出錯(cuò), 則調(diào)用_MyDbm_Free清除DB結(jié)構(gòu)

46、, 然后對(duì)調(diào)用者返回NULL. 如果一切正常工作, 則函數(shù)會(huì)調(diào)用MyDbm_Rewind把數(shù)據(jù)庫(kù)重置到”起始狀態(tài)”, 將索引文件的文件偏移量定位在索引文件的一條索引記錄(今跟在散列表之后). 最后返回?cái)?shù)據(jù)庫(kù)的引用指針. 供調(diào)用者與數(shù)據(jù)庫(kù)通信. </p><p>　　MyDbm_Close</p><p>　　其函數(shù)原型為void MyDbm_Close(DBHANDLE handle);&

47、lt;/p><p>　　其很簡(jiǎn)單, 就是調(diào)用_MyDbm_Free, MyDbm_Close在這里的作用是作為一個(gè)類型轉(zhuǎn)換器, 將DBHANDLE轉(zhuǎn)換為DB結(jié)構(gòu)指針. </p><p>　　MyDbm_Open在打開索引文件和數(shù)據(jù)文件時(shí)如果發(fā)生錯(cuò)誤, 也會(huì)調(diào)用MyDbm_Free. 該函數(shù)的作用是釋放所有DB結(jié)構(gòu)所分配到的內(nèi)存緩存, 并關(guān)閉索引和數(shù)據(jù)文件, 如果它們還是處于打開狀態(tài). <

48、/p><p>　　MyDbm_Select</p><p>　　其函數(shù)原型為char * MyDbm_Select(DBHANDLE handle , const char *key);</p><p>　　函數(shù)MyDbm_Select根據(jù)給定的鍵來讀取一條記錄. 它首先調(diào)用_MyDbm_FindAndLock在數(shù)據(jù)庫(kù)中查找記錄, 若不能找到記錄, 則將返回NULL值,

49、 由于從_MyDbm_FindAndLock時(shí), 數(shù)據(jù)庫(kù)索引文件是加鎖的, 所以要先解鎖, 然后再返回. </p><p>　　如果找到了記錄, 則調(diào)用_MyDBm_ReadDat讀取相應(yīng)的數(shù)據(jù)記錄. 在返回前, 調(diào)用UnLock對(duì)索引文件解鎖, 然后, 返回所找到的記錄的指針. </p><p>　　_MyDbm_FindAndLock函數(shù)原型為:</p><p>

50、;　　static int _MyDbm_FindAndLock(DB *db , const char *key , int writelock)</p><p>　　其作用是在函數(shù)庫(kù)內(nèi)部用于按給定的鍵查找記錄, 在搜索記錄時(shí), 如果想在索引文件上加一把寫鎖, 則將writelock參數(shù)設(shè)置為非0, 如果將其設(shè)置為0, 則在搜索記錄時(shí), 在索引文件上加讀鎖. </p><p>　　_My

51、Dbm_FindAndLock中準(zhǔn)備遍歷散列鏈?zhǔn)? 通過_MyDbm_Hash將鍵變換為散列值, 用其計(jì)算在文件中相應(yīng)散列鏈的起始地址. 在遍歷散列鏈前, 等待獲得鎖. 該鎖為細(xì)瑣, 只鎖定散列鏈開始處的第1個(gè)字節(jié), 這種方式允許多個(gè)進(jìn)程同時(shí)搜索不同的散列鏈, 因此增加了并發(fā)性. 然后再while循環(huán)內(nèi)遍歷散列鏈的每一條索引記錄, 并比較鍵. 如果沒有找到記錄則返回-1, 找到數(shù)據(jù)則返回0, 并將相關(guān)信息填入db所指中DB結(jié)構(gòu)中. &l

52、t;/p><p>　　_MyDbm_Hash根據(jù)給定的鍵計(jì)算散列值, 它將鍵中的每一個(gè)ASCII字符乘以這個(gè)字符在字符串中以1開始的索引號(hào), 將這些結(jié)果加起來, 除以散列記錄項(xiàng)數(shù), 將余數(shù)作為這個(gè)鍵的散列值. 散列表記錄項(xiàng)通常為素?cái)?shù), 素?cái)?shù)散列通常提供良好的分布特性. </p><p>　　在_MyDbm_FindAndLock循環(huán)內(nèi)遍歷散列鏈的每一條索引記錄時(shí), 會(huì)用到兩個(gè)內(nèi)部函數(shù)_MyDb

53、m_ReadPtr和_MyDbm_ReadIdx</p><p>　　_MyDbm_ReadPtr函數(shù)讀取以下三種不同鏈表指針中的任意一種:(1)索引文件最開始處指向空閑鏈表中第一條索引記錄的指針；(2) 散列表中指向散列鏈的第一條索引記錄的指針；(3)存放在每條索引記錄開始處、指向下一條記錄的指針(這里的索引記錄既可以處于一條散列鏈中, 也可以處于空閑鏈表中). 返回前, 會(huì)將指針從ASCII形式變換為長(zhǎng)整型.

54、 </p><p>　　_MyDbm_ReadIdx函數(shù)用于從索引文件的指定編譯量處讀取索引記錄. 如果成功, 該函數(shù)將返回鏈表中下一條記錄的偏移量. 并將相關(guān)信息填入DB結(jié)構(gòu)的許多字段中. </p><p>　　MyDbm_Delete</p><p>　　其函數(shù)原型為int MyDbm_Delete(DBHANDLE handle , const char *k

55、ey);</p><p>　　MyDbm_Delete函數(shù)用于刪除與給定鍵匹配的一條記錄. 首先調(diào)用_MyDbm_FindAndLock判斷在數(shù)據(jù)庫(kù)中該記錄是否存在, 如果存在, 則調(diào)用_MyDBm_ DoDelete函數(shù)執(zhí)行刪除該記錄的操作. _MyDbm_FindAndLock的第3個(gè)參數(shù)控制對(duì)散列鏈?zhǔn)羌幼x鎖, 還是寫鎖. </p><p>　　_MyDB_DoDelete函數(shù)執(zhí)行從數(shù)

56、據(jù)庫(kù)中刪除一條記錄的所有操作. 此函數(shù)的大部分工作僅僅是更新兩個(gè)鏈表:空閑鏈表以及與鍵對(duì)應(yīng)的散列鏈. 當(dāng)一條記錄被刪除后, 將其鍵和數(shù)據(jù)記錄設(shè)為空. </p><p>　　在更新空閑鏈表是, 先對(duì)空閑鏈表進(jìn)行加寫鎖, 這樣能防止兩個(gè)進(jìn)程同時(shí)刪除不同散列鏈上的記錄時(shí)產(chǎn)生相互影響, 因?yàn)橐獙⒈粍h除的記錄移到空閑鏈表上, 這將改變空閑鏈表指針, 而一次只能有一個(gè)進(jìn)程能這樣做. </p><p>

57、　　_MyDBm_DoDelete會(huì)調(diào)用函數(shù)_MyDbm_WriteDat清空數(shù)據(jù)記錄, 此時(shí)_MyDBm_WriteDat無需對(duì)數(shù)據(jù)文件加寫鎖, 因?yàn)镸yDbm_Delete對(duì)這條記錄的散列鏈已經(jīng)加了寫鎖, 這便保證不再會(huì)有其他進(jìn)程能夠讀寫該記錄. </p><p>　　要?jiǎng)h除的記錄通過_MyDbm_WriteDat清空數(shù)據(jù)后, 會(huì)將其偏移地址加入到空閑鏈中, 還在其原來的散列鏈中, 其前面的記錄會(huì)將指針修改為

58、其后記錄的偏移量, 這樣記錄就被刪除了. </p><p>　　MyDbm_Insert</p><p>　　其函數(shù)原型為int MyDbm_Insert(DBHANDEL handle , const char *key , const char *data );</p><p>　　MyDbm_Insert函數(shù)用于將一條記錄加到數(shù)據(jù)庫(kù)中. 首先查明數(shù)據(jù)記錄長(zhǎng)度是

59、否有效, 如果無效, 則返回一個(gè)出錯(cuò)狀態(tài). 然后調(diào)用_MyDbm_FindAndLock以查看這個(gè)記錄是否已經(jīng)存在. 如果記錄存在(通過比較鍵值), 也將返回一個(gè)出錯(cuò)狀態(tài). 因?yàn)镸yDbm_Insert要修改散列鏈, 所以用MyDbm_FindAndLock時(shí), 最后一個(gè)參數(shù)要指明要對(duì)散列鏈加寫鎖. </p><p>　　在調(diào)用_MyDbm_FindAndLock后, 程序分成兩種情況. </p>

60、<p>　　情況一:在調(diào)用_MyDbm_FindFree時(shí), 在空閑鏈表中搜索一條已刪除的記錄, 它的鍵長(zhǎng)度和數(shù)據(jù)長(zhǎng)度與要添加key和data相同. 這時(shí)會(huì)將空記錄從空閑鏈表上移下來, 寫入新的索引記錄和數(shù)據(jù)記錄. 然后將新紀(jì)錄加到對(duì)應(yīng)的散列鏈的鏈?zhǔn)? </p><p>　　情況二:沒有找到對(duì)應(yīng)大小的記錄. 這意味著要將這條記錄添加到索引文件和數(shù)據(jù)文件的末尾. 調(diào)用_MyDbm_WriteDat寫數(shù)據(jù)部

61、分,調(diào)用_MyDbm_WriteIdx寫索引部分, 再調(diào)用_MyDbm_WritePtr將新記錄加到對(duì)應(yīng)的散列鏈的鏈?zhǔn)? </p><p>　　在正常情況下, 設(shè)置表示成功的返回碼, 然后進(jìn)入公共返回邏輯. 對(duì)散列鏈解鎖(這把鎖是由調(diào)用(MyDbm_FindAndLock而加上的), 然后返回調(diào)用者. </p><p>　　_MyDbm_FindFree函數(shù)試圖找到一個(gè)指定大小的空閑索引記

62、錄和相關(guān)的數(shù)據(jù)記錄. _MyDbm_FindFree需要對(duì)空閑鏈表加寫鎖以避免與其他使用空閑鏈表的進(jìn)程戶型干擾. 在對(duì)空閑鏈表加寫鎖后, 得到空閑鏈表鏈?zhǔn)椎闹羔樀刂? </p><p>　　_MyDbm_FindFree會(huì)在循環(huán)中遍歷空閑鏈表, 以搜尋一個(gè)有匹配鍵長(zhǎng)度和數(shù)據(jù)長(zhǎng)度的記錄項(xiàng). 在這個(gè)簡(jiǎn)單的現(xiàn)實(shí)中, 只有當(dāng)一個(gè)已刪除記錄的鍵長(zhǎng)度及數(shù)據(jù)長(zhǎng)度與要加入的新記錄的鍵長(zhǎng)度及數(shù)據(jù)長(zhǎng)度一樣時(shí), 才重用已刪除記錄的空間

63、. 其他更好的重用刪除空間的方法一般更復(fù)雜. 如果找不到具有所要求的鍵長(zhǎng)度和數(shù)據(jù)長(zhǎng)度的可用記錄, 則設(shè)置表示失敗的返回碼. 否則, 將已找到的記錄的下一個(gè)鏈表指針值寫至前一記錄的鏈表指針, 這樣就從空閑鏈表中移除了該記錄. </p><p>　　一旦結(jié)束對(duì)空閑鏈表的操作, 就釋放寫鎖, 然后對(duì)調(diào)用者返回狀態(tài)碼. </p><p>　　MyDbm_Update, MyDbm_Rewind和M

64、yDbm_NextRecord</p><p>　　其函數(shù)原型為int MyDbm_Update(DBHANDEL handle , const char *key , const char *data );</p><p>　　MyDbm_Updatet函數(shù)用于將一條記錄按要求更新. 首先查明數(shù)據(jù)記錄長(zhǎng)度是否有效, 如果無效, 則返回一個(gè)出錯(cuò)狀態(tài). 然后調(diào)用_MyDbm_FindAndL

65、ock以查看這個(gè)記錄是否已經(jīng)存在. 如果記錄不存在(通過比較鍵值), 也將返回一個(gè)出錯(cuò)狀態(tài). 因?yàn)镸yDbm_Updatet不要修改散列鏈, 所以用MyDbm_FindAndLock時(shí), 最后一個(gè)參數(shù)資源只需要加讀鎖. </p><p>　　在調(diào)用_MyDbm_FindAndLock后, 要替換的數(shù)據(jù)存在, 而新數(shù)據(jù)記錄的長(zhǎng)度與以存在記錄的長(zhǎng)度不一樣. 先調(diào)用_MyDbm_DoDelete將老記錄刪除, 該記錄將

66、放在空閑鏈表的鏈?zhǔn)? 然后, 調(diào)用_MyDbm_WriteDat和_MyDbm_WrtieIdx將新記錄添加到索引文件和數(shù)據(jù)文件的末尾(也可以用其他方法, 如可以再查找是否有數(shù)據(jù)大小正好的以刪除的記錄項(xiàng)). 最后調(diào)用_MyDbm_WritePtr將新記錄加到對(duì)應(yīng)的散列鏈的鏈?zhǔn)? </p><p>　　如果要替換的數(shù)據(jù)記錄的長(zhǎng)度與已存在的記錄的長(zhǎng)度恰好一樣. 這是最容易的情況, 只需要重寫數(shù)據(jù)記錄即可. <

67、/p><p>　　在正常情況下, 設(shè)置表示成功的返回碼, 然后進(jìn)入公共返回邏輯. 對(duì)散列鏈解鎖(這把鎖是由調(diào)用(MyDbm_FindAndLock而加上的), 然后返回調(diào)用者. </p><p>　　MyDbm_Rewind</p><p>　　其函數(shù)原型為 void MyDbm_Rewind(DBHANDLE handle);</p><p>

68、;　　MyDbm_Rewind函數(shù)用于把數(shù)據(jù)庫(kù)重置到”起始狀態(tài)”, 將索引文件的文件偏移量定位在索引文件的第一條索引記錄(緊跟在散列表之后). </p><p>　　MyDbm_NextRecord</p><p>　　其函數(shù)原型為 char * MyDbm_NextRecord(DBHANDLE handle , char *key);</p><p>　　MyD

69、bm_NextRecord函數(shù)返回?cái)?shù)據(jù)庫(kù)的下一條記錄, 返回值是指向數(shù)據(jù)緩沖的指針. 如果調(diào)用值提供的Key參數(shù)非空, 那么相應(yīng)鍵復(fù)制到該緩沖中. 調(diào)用者負(fù)責(zé)分配可以存放鍵的足夠大的緩沖. 記錄按它們?cè)跀?shù)據(jù)庫(kù)文件中存放的順序逐一返回. 因此, 記錄并不按鍵值的大小排列. 另外, MyDbm_NextRecord并不跟隨散列鏈表, 所以也可能讀到已刪除的記錄, 只是不向調(diào)用者返回這種以刪除記錄. </p><p>

70、　　以上就是MyDbm數(shù)據(jù)庫(kù)對(duì)外的接口函數(shù), 在介紹它們的同時(shí), 也附加介紹了它們所依賴的內(nèi)部私有函數(shù). 接下就該數(shù)據(jù)庫(kù)函數(shù)庫(kù)性能分析. </p><p><b>　　性能分析</b></p><p>　　為了測(cè)試這個(gè)數(shù)據(jù)庫(kù)函數(shù)庫(kù), 也為了獲得一些與典型應(yīng)用的數(shù)據(jù)訪問模式有關(guān)的時(shí)間測(cè)試數(shù)據(jù), 本文應(yīng)用了[3]中的一個(gè)測(cè)試程序. 該程序接受兩個(gè)命令行參數(shù): 要?jiǎng)?chuàng)建的子進(jìn)

71、程的個(gè)數(shù)以及每個(gè)進(jìn)程向數(shù)據(jù)庫(kù)寫的數(shù)據(jù)庫(kù)記錄的條數(shù)(records), 然后創(chuàng)建一個(gè)空的數(shù)據(jù)庫(kù)(通過調(diào)用MyDbm_Open), 通過forks創(chuàng)建指定數(shù)據(jù)的子進(jìn)程, 并等待所有子進(jìn)程結(jié)束. 每個(gè)子進(jìn)程執(zhí)行以下步驟:</p><p>　　(1) 向數(shù)據(jù)庫(kù)寫records條記錄. </p><p>　　(2) 通過鍵值讀回records條記錄. </p><p>　　(

72、3) 執(zhí)行下面的循環(huán)records*5次.</p><p>　　(a) 每循環(huán)37次, 隨機(jī)刪除一條記錄. </p><p>　　(b) 每循環(huán)11次, 添加一條新記錄并讀回這條記錄. </p><p>　　(c) 每循環(huán)17次, 隨機(jī)替換一條記錄為新記錄. 在連續(xù)兩次替換中, 一次用同樣大 小的記錄替換, 一次用比以前更長(zhǎng)的記錄替換.</p>

73、<p>　　(4) 將此子進(jìn)程寫的所有記錄刪除. 每刪除一條記錄, 隨機(jī)尋找10條記錄.</p><p>　　隨機(jī)讀一條記錄. 當(dāng)records為500時(shí), 每個(gè)子進(jìn)程的較典型的操作數(shù)表6.1. </p><p>　　表6.1 當(dāng)records為500時(shí), 每個(gè)子進(jìn)程的較典型的操作數(shù)表</p><p>　　讀取的次數(shù)大約是存儲(chǔ)或刪除的10倍, 這可能是許多

74、數(shù)據(jù)庫(kù)應(yīng)用程序的典型情況. </p><p>　　每個(gè)子進(jìn)程只對(duì)孩子進(jìn)程所寫的記錄執(zhí)行這些操作(讀取,儲(chǔ)存和刪除). 由于所有的子進(jìn)程對(duì)同一數(shù)據(jù)庫(kù)進(jìn)行操作(雖然對(duì)不同的記錄), 所以會(huì)使用并發(fā)控制. 數(shù)據(jù)庫(kù)中的記錄總條數(shù)與子進(jìn)程數(shù)成比例增加. (當(dāng)只有一個(gè)子進(jìn)程時(shí), 一開始有records條記錄寫入數(shù)據(jù)庫(kù), 當(dāng)有兩個(gè)子進(jìn)程是, 一開始有records*2條記錄寫入數(shù)據(jù)庫(kù), 依次類推. )</p>&

75、lt;p>　　通過運(yùn)行測(cè)試程序來測(cè)試三個(gè)不同版本的MyDbm函數(shù)庫(kù)來比較加粗鎖和加細(xì)瑣提供的并發(fā), 并且比較三種不同的加鎖方式(不加鎖, 建議性鎖和強(qiáng)制鎖). 第一個(gè)版本加細(xì)鎖, 采用本文的源代碼; 第二個(gè)版本通過改變加鎖調(diào)用而使用粗鎖; 第三個(gè)版本將所有加鎖調(diào)用均去掉, 這樣可以計(jì)算加鎖的開銷. </p><p><b>　　單進(jìn)程的結(jié)果</b></p><p&g

76、t;　　表6.2顯示了只有一個(gè)子進(jìn)程運(yùn)行時(shí)的結(jié)果, records分別為500,1000和2000.</p><p>　　表6.2 單子進(jìn)程, 不同的records和不同的加鎖方法</p><p>　　最后12列顯示的是以秒為單位的時(shí)間. 在所有的情況下, 用戶CPU時(shí)間加上系統(tǒng)CPU時(shí)間都近似地等于時(shí)鐘時(shí)間. 這一組測(cè)試受CPU限制而不是受磁盤操作限制. </p><

77、p>　　中間6列(建議性鎖)對(duì)加粗鎖和加細(xì)鎖的結(jié)果基本一樣. 這是可以理解的, 因?yàn)閷?duì)于單個(gè)進(jìn)程來說加粗鎖和加細(xì)瑣并沒有區(qū)別. </p><p>　　比較不加鎖和加建議性鎖, 可以看到加鎖調(diào)用在系統(tǒng)CPU時(shí)間上增加了2%~31%. 即使這些鎖實(shí)際上并沒有使用過(由于只有一個(gè)進(jìn)程). 另外, 注意到用戶CPU時(shí)間對(duì)于四種不同的加鎖方案基本上一樣, 這是因?yàn)橛脩舸a基本上是一樣的. </p>&l

78、t;p>　　最后的測(cè)試時(shí)嘗試有多個(gè)子進(jìn)程的不加鎖的程序. 與預(yù)想的一樣, 結(jié)果是隨機(jī)的錯(cuò)誤. 一般情況包括:加入到數(shù)據(jù)庫(kù)的記錄找不到, 測(cè)試程序異常退出等等. 幾乎每次運(yùn)行測(cè)試程序, 就有不同的錯(cuò)誤發(fā)生. 這是典型的競(jìng)爭(zhēng)狀態(tài)—多個(gè)進(jìn)程在沒有任何加鎖的情況下修改同一個(gè)文件, 錯(cuò)誤情況不可預(yù)測(cè). </p><p><b>　　多進(jìn)程的結(jié)果</b></p><p>　

79、　下一組測(cè)試主要查看粗鎖和細(xì)瑣的不同. 前面說過, 由于加細(xì)瑣時(shí)數(shù)據(jù)庫(kù)的各個(gè)部分被其他進(jìn)程鎖住的時(shí)間比加粗鎖少, 所以憑直覺加細(xì)瑣應(yīng)該能夠提供更好到并發(fā)性. 表6.3顯示了對(duì)nrec取500, 子進(jìn)程數(shù)目從1到12的測(cè)試結(jié)果. </p><p>　　表6.3 records=500時(shí), 不同加鎖方法的比較</p><p>　　所有的用戶時(shí)間, 系統(tǒng)時(shí)間和時(shí)鐘時(shí)間的單位均為秒, 所有這些時(shí)間

80、均為父進(jìn)程與所有子進(jìn)程的總和. </p><p>　　第8列(標(biāo)志為“△Clock”)是加建議粗鎖與加建議細(xì)瑣的時(shí)鐘時(shí)間的時(shí)間差, 從該度量中可以看出使用細(xì)瑣得到了多大的并發(fā)度. 在運(yùn)行測(cè)試測(cè)試程序的系統(tǒng)上, 當(dāng)并發(fā)進(jìn)程數(shù)不多于7時(shí), 加粗鎖與加細(xì)瑣的效果大致相當(dāng)；即使多于7個(gè)進(jìn)程, 使用細(xì)瑣的時(shí)間減少也不大(一般少于3%). </p><p>　　我們希望從粗鎖到細(xì)瑣時(shí)鐘時(shí)間會(huì)減少, 最

81、后也確實(shí)如此, 對(duì)粗鎖而言, 保持這種鎖的時(shí)間比較長(zhǎng), 于是增加了其他進(jìn)程因這種鎖而阻塞的可能性；而對(duì)細(xì)瑣而言, 由于加鎖的時(shí)間較短, 于是進(jìn)程為此而阻塞的機(jī)會(huì)也就比較少. 如果分析運(yùn)行12個(gè)數(shù)據(jù)庫(kù)進(jìn)程的系統(tǒng)行為, 將會(huì)看到加粗鎖時(shí)的進(jìn)程切換次數(shù)是加細(xì)瑣時(shí)的3倍. 這就意味著在使用細(xì)瑣時(shí), 進(jìn)程在鎖上阻塞的機(jī)會(huì)要少的多. </p><p>　　最后一列是從加建議細(xì)瑣到強(qiáng)制細(xì)瑣的系統(tǒng)CPU時(shí)間的百分比增量. 這與在

82、表6.2看到的強(qiáng)制性鎖顯著增加系統(tǒng)時(shí)間是一致的. </p><p><b>　　小結(jié)</b></p><p>　　本文是在dbm數(shù)據(jù)庫(kù)函數(shù)庫(kù)的基礎(chǔ)上通過添加并發(fā)控制機(jī)制, 是dbm能在多進(jìn)程的環(huán)境下被用戶安全使用. </p><p>　　MyDbm數(shù)據(jù)庫(kù)函數(shù)庫(kù)數(shù)據(jù)庫(kù)采用的是非集中式方式, 加鎖的策略來盡可能的提高數(shù)據(jù)庫(kù)函數(shù)并發(fā)性. 從最后的性能

83、分析上也看出了這點(diǎn). 當(dāng)然, 運(yùn)行的進(jìn)程越多, 其并發(fā)優(yōu)越性更能體現(xiàn). </p><p>　　雖然MyDbm與商業(yè)級(jí)別的數(shù)據(jù)相比, 相距甚遠(yuǎn). 但是對(duì)于那些輕量級(jí)的應(yīng)用完全足夠[11]. 由于其是一種文件數(shù)據(jù)儲(chǔ)存數(shù)據(jù), 采用哈希結(jié)構(gòu)進(jìn)行連接, 因此與普通文本數(shù)據(jù)庫(kù)相比, 具有穩(wěn)定, 檢索速度快和支持量大的優(yōu)點(diǎn). 由于MyDbm是從Unix系統(tǒng)中移植來的, 因此在UNIX系統(tǒng)中優(yōu)點(diǎn)比較明顯, 加之其多進(jìn)程訪問能力,

84、 更加發(fā)揮出UNIX環(huán)境的優(yōu)勢(shì). </p><p>　　當(dāng)然MyDbm也存在一些不足的地方需要改進(jìn). 比如重用刪除空間的算法過于簡(jiǎn)單呆板, 使刪除空間重用率降低, 可以采用更好的算法提高之.</p><p><b>　　參考文獻(xiàn)</b></p><p>　　(美)W.Richard Stevens, Setphen A Rago. Advanc

85、ed Programming in the UNIX Environment [M]. 人民郵電出版社, 2006: 709-750.</p><p>　　(英)Neil Matthew, Richard Stones著, 楊曉云等譯. Linux程序設(shè)計(jì)(第二版) [M]. 機(jī)械工業(yè)出版社, 2002:100-120.</p><p>　　薩師煊, 王珊. 數(shù)據(jù)庫(kù)系統(tǒng)概論(第四版) [M

86、]. 高等教育出版社, 2006: 1-20.</p><p>　　王珊, 孟小峰. 數(shù)據(jù)庫(kù)系統(tǒng)導(dǎo)論(第七版) [M]. 機(jī)械工業(yè)出版社, 2000: 50-80.</p><p>　　Abnhrmx Silbersehaa. 數(shù)據(jù)庫(kù)系統(tǒng)概念 [M]. 機(jī)械工業(yè)出版, 2006: 130-160.</p><p>　　(美)沃爾特, 本-甘, 薩卡. Microso

87、ft SQL Server 2005技術(shù)內(nèi)幕-T-SQL程序設(shè)計(jì) [M]. 北京:電子工業(yè)出版社, 2007: 50-80.</p><p>　　微軟公司著. 熊盛新, 許志慶, 李欽譯. Visual C# .NET語言參考手冊(cè) [M]. 北京:清華大學(xué)出版社, 2002年: 160-180.</p><p>　　(美)Kaili Watson . C#2005數(shù)據(jù)庫(kù)編程經(jīng)典教程 [M

88、]. 人民郵電出版社, 2007: 90-120.</p><p>　　劉乃麗. 精通ASP.NET2.0+SQLServer 2005項(xiàng)目開發(fā) [M]. 北京:人民郵電出版社, 2007: 100-150.</p><p>　　Craig Hunt. Linux Sendmail Administration (Craig Hunt Linux Library) [M]. Sybex,

89、 2001-2.</p><p>　　歐立奇, 康祥順, 馬煜編著. Visual C# .NET 案例開發(fā)集錦 [M]. 北京:電子工業(yè)出版社, 2006: 233-245.</p><p><b>　　附件</b></p><p>　　以下給出本函數(shù)庫(kù)的文件，其中包括MyDbm.h(函數(shù)庫(kù)的頭文件), MyDbm.c(函數(shù)庫(kù)的實(shí)現(xiàn)文件,這里

90、只顯示對(duì)外的幾個(gè)函數(shù)).</p><p>　　MyDbm.h文件的代碼如下:</p><p>　　#ifndef _MYDBM_H</p><p>　　#define _MYDBM_H</p><p>　　typedef void * DBHANDLE;</p><p>　　DBHANDLE MyDbm_Open(

91、const char *pathName, int oflag, ...);</p><p>　　void MyDbm_Close(DBHANDLE handle);</p><p>　　char *MyDbm_Select(DBHANDLE handle , const char *key);</p><p>　　int MyDbm_

92、Update(DBHANDLE handle , const char *key , const char *data);</p><p>　　int MyDbm_Insert(DBHANDLE handle , const char *key , const char *data);</p><p>　　int MyDbm_Delete(DBHANDLE, con

93、st char *);</p><p>　　void MyDbm_Rewind(DBHANDLE);</p><p>　　char *MyDbm_NextRecord(DBHANDLE, char *);</p><p><b>　　/*</b></p><p><b>　　* 系統(tǒng)限制<

94、;/b></p><p><b>　　*/</b></p><p>　　#define IDXLEN_MIN 6 /* key, sep, start, sep, length, \n */</p><p>　　#define IDXLEN_MAX 1024 /* arbitrary */</p>&l

95、t;p>　　#define DATLEN_MIN 2 /* data byte, newline */</p><p>　　#define DATLEN_MAX 1024 /* arbitrary */</p><p><b>　　/*</b></p><p>　　* 鎖函數(shù)和在其基礎(chǔ)上構(gòu)建的各種宏</p>

96、;<p><b>　　*/</b></p><p>　　int lock_reg(int, int, int, off_t, int, off_t);</p><p>　　#define read_lock(fd, offset, whence, len) \</p><p>　　lock_reg((fd), F_SETL

97、K, F_RDLCK, (offset), (whence), (len))</p><p>　　#define readw_lock(fd, offset, whence, len) \</p><p>　　lock_reg((fd), F_SETLKW, F_RDLCK, (offset), (whence), (len))</p><p>　　#define

98、write_lock(fd, offset, whence, len) \</p><p>　　lock_reg((fd), F_SETLK, F_WRLCK, (offset), (whence), (len))</p><p>　　#define writew_lock(fd, offset, whence, len) \</p><p>　　lock_reg(

99、(fd), F_SETLKW, F_WRLCK, (offset), (whence), (len))</p><p>　　#define un_lock(fd, offset, whence, len) \</p><p>　　lock_reg((fd), F_SETLK, F_UNLCK, (offset), (whence), (len))</p><p>　

100、　#endif /* MyDbm_H */</p><p>　　MyDbm.c的文件如下：</p><p>　　#include "MyDbm.h"</p><p>　　#include <stdio.h></p><p>　　#include <unistd.h></p><p

101、>　　#include <fcntl.h></p><p>　　#include <stdarg.h></p><p>　　#include <errno.h></p><p>　　#include <sys/uio.h></p><p><b>　　/*</b>&l

102、t;/p><p><b>　　* 符號(hào)定義</b></p><p>　　* 這些定義的符號(hào)將用在索引文件和數(shù)據(jù)文件中</p><p><b>　　*/</b></p><p>　　#define IDXLEN_SZ 4 /* 索引指針長(zhǎng)度 */</p><p>　

103、　#define SEP ':' /* 索引記錄分隔符 */</p><p>　　#define SPACE ' ' /* 空格符 */</p><p>　　#define NEWLINE '\n' /* 換行符 */</p><p><b>　　/*

104、</b></p><p>　　*哈希鏈和空閑鏈表的定義</p><p><b>　　*/</b></p><p>　　#define PTR_SZ 6 /* 鏈指針長(zhǎng)度*/</p><p>　　#define PTR_MAX 999999 /* 最大文件位移10

105、的PTR_SZ次-1 */</p><p>　　#define NHASH_DEF 137 /* 默認(rèn)的哈希數(shù)組長(zhǎng)度 */</p><p>　　#define FREE_OFF 0 /* 空閑指針域的文件位移 */</p><p>　　#define HASH_OFF PTR_SZ /* 哈希表在索引文件

106、的位移 */</p><p>　　typedef unsigned long DBHASH; /* 哈希表類型*/</p><p>　　typedef unsigned long COUNT; /* 計(jì)數(shù)器類型*/</p><p><b>　　/*</b></p><p>　　* 數(shù)據(jù)庫(kù)描述符，類似文件描述符&

107、lt;/p><p><b>　　*/</b></p><p>　　typedef struct {</p><p>　　int idxfd; /* 索引文件文件描述符 */</p><p>　　int datfd; /* 數(shù)據(jù)文件文件描述符 */</p><p>　　char *id

108、xbuf; /* 索引記錄緩沖 */</p><p>　　char *datbuf; /* 數(shù)據(jù)記錄緩沖 */</p><p>　　char *name; /* 打開的數(shù)據(jù)庫(kù)名 */</p><p>　　off_t idxoff; /* 索引記錄在索引文件的位移*/</p><p>　　size_t idxlen; /* 索引記錄長(zhǎng)

109、度 */</p><p>　　off_t datoff; /* 數(shù)據(jù)記錄在數(shù)據(jù)文件的位移*/</p><p>　　size_t datlen; /* 數(shù)據(jù)記錄長(zhǎng)度 */</p><p>　　off_t ptrval; /* 索引項(xiàng)的內(nèi)容 */</p><p>　　off_t ptroff; /* 索引指針的值 */</p>

110、<p>　　off_t chainoff; /* 索引記錄所在哈希鏈的位移*/</p><p>　　off_t hashoff; /* 哈希表在索引文件的位移*/</p><p>　　DBHASH nhash; /* 當(dāng)前數(shù)據(jù)庫(kù)的哈希表大小 */</p><p><b>　　} DB;</b></p>&l

111、t;p><b>　　/*</b></p><p><b>　　* 內(nèi)部私有函數(shù)</b></p><p><b>　　*/</b></p><p>　　static DB *_MyDbm_Alloc(int);</p><p>　　static void _M

112、yDbm_DoDelete(DB *);</p><p>　　static int _MyDbm_FindAndLock(DB *, const char *, int);</p><p>　　static int _MyDbm_Findfree(DB *, int, int);</p><p>　　static void _MyDbm_Fre