大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告材料.

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告姓 名：*學(xué) 號：200516104*班級：05級04班所選課題：5、封鎖資源管理子系統(tǒng)目錄需求分析： 1背景介紹1功能要求2概要設(shè)計(jì)3詳纟田設(shè)計(jì)5調(diào)試分析10.1、需求分析：1.1、背景介紹在并發(fā)操作的系統(tǒng)中，許多用戶可能同時(shí)對同一數(shù)據(jù)進(jìn)行操作。 并發(fā)操作帶 來的問題是數(shù)據(jù)的不一致性，并發(fā)控制的主要技術(shù)是封鎖。封鎖資源管理子系統(tǒng)就是通過加鎖來控制用戶對系統(tǒng)資源的并發(fā)使用?；?的封鎖類型有S鎖（共享鎖）和X鎖（排他鎖）。共享鎖：用戶A對資源R加上 S鎖，則只允許A讀取R,但不能修改R,其它的用戶只能再對R加S鎖，直到 A釋放了 R上的S鎖。這就保證了其它用戶可以讀 R但在

2、A釋放R上的S鎖之 前不能對R進(jìn)行修改。排它鎖：用戶 A對資源R加上鎖，則只允許A讀取和修 改R其它用戶不能再對R加任何鎖，直到A釋放了 R上的鎖。兩種封鎖方式的相容矩陣如圖所示：SXSOKNOXNONO相容矩陣用戶使用系統(tǒng)資源前必須申請封鎖，即給出申請封鎖的對象資源號、封鎖方 式和用戶名。其中資源號是取值為一正整數(shù)。子系統(tǒng)受封鎖請求，根據(jù)所保存的 封鎖狀態(tài)信息決定請求是否能夠獲得封鎖， 進(jìn)行相應(yīng)處理，并向用戶反饋處理結(jié) 果。如果獲得封鎖，則賦給該請求一個(gè)批準(zhǔn)號，可以使用該資源；否則需要進(jìn)入 等待隊(duì)列（賦給該請求一個(gè)批準(zhǔn)號）。用戶結(jié)束對某資源的使用后，應(yīng)釋放封鎖（給出封鎖對象的資源號和封鎖批

3、準(zhǔn)號）。系統(tǒng)受理解鎖請求時(shí)必須能迅速找到有關(guān)對象的封鎖狀況信息，以進(jìn)行相應(yīng)處理。1.2、功能要求1）、受理用戶資源請求，把用戶添加進(jìn)等待隊(duì)列或活動隊(duì)列2）、受理用戶釋放資源請求3）、查看資源活動隊(duì)列4）、查看資源等待隊(duì)列5）、查看系統(tǒng)所有資源6）、添加資源7）、用戶讀取使用資源8）、用戶修改資源9）、添加用戶用列圖如下:A dd_Re sourceView_Waier2、概要設(shè)計(jì)此部分為整個(gè)核心設(shè)計(jì)的流程，包括資源結(jié)構(gòu)、用戶結(jié)構(gòu)、鎖結(jié)構(gòu)、等待隊(duì) 列、活動隊(duì)列、資源高效存儲查詢的設(shè)計(jì)，及請求、釋放、讀、寫資源的實(shí)現(xiàn)方 式設(shè)計(jì)。為滿足高效存儲、查詢資源的要求，可采用散列表為資源建索引，并用鏈表 解

4、決沖突，存儲的結(jié)構(gòu)如下圖所示：散宛蔻頭活動隊(duì)列等待隊(duì)列封鎖管理子系統(tǒng)示意圖其中散列表的元素對應(yīng)為封鎖對象，以對象的資源號為散列函數(shù)的自變量（即關(guān)鍵碼值）。散列表中元素僅為一個(gè)指向封鎖對象鏈表的指針。LO為封鎖對 象結(jié)點(diǎn)，對應(yīng)于同一散列地址的封鎖對象鏈接到一個(gè)鏈表中。LR為封鎖請求結(jié)點(diǎn)。每個(gè)封鎖對象結(jié)點(diǎn)帶兩個(gè)封鎖請求隊(duì)列： 活動隊(duì)列中為當(dāng)前持有對該對象的 圭寸鎖請求，等待隊(duì)列中為正在等待對該對象進(jìn)行圭寸鎖的圭寸鎖請求。LO結(jié)點(diǎn)和LR結(jié)點(diǎn)均向子系統(tǒng)自己管理的可利用空間表申請。Hash函數(shù)采用求余的方法，在這個(gè)系統(tǒng)中應(yīng)為資源的個(gè)數(shù)是不確定的，因此hash表的大小也可以隨著資源數(shù)的不同而改變，我的設(shè)計(jì)

5、是當(dāng)記錄的個(gè)數(shù)大于資源個(gè)數(shù)的五倍時(shí)hash表大小翻倍。而S鎖和X鎖的設(shè)計(jì)則采用了多態(tài)的方法，設(shè)計(jì)一個(gè)公共的抽象基類：Lock 里面定義了三個(gè)接口， XLock和SLock類都派生自這個(gè)類，這樣就可以用一個(gè) 指針來操作這兩個(gè)不同的鎖了。而請求的批準(zhǔn)號則是系統(tǒng)自動給的，用戶可以通過查看資源的請求隊(duì)列和活 動隊(duì)列獲得批準(zhǔn)號，等待隊(duì)列和活動隊(duì)列都是基于鏈表的，這樣就不會浪費(fèi)空間。用戶請求資源順序圖如下:UserResourceActi/eQueueWaiterQueue1 requmsp空 u 迸2：iew_state3: requiOuccess, add to activfeQueuer5: re

6、turn|i4: request faiI dd to waiQueueIr用戶釋放資源順序圖如下:門殆衣EoiincoW創(chuàng)上erO用li2：fnd_resource二13: find actor=e nove_actorTS i s_AmplyI6: find WaiterI7: v3iter_add_to_ctiveOifeue8: roturnrIInu3、詳細(xì)設(shè)計(jì)1 ）、資源結(jié)構(gòu)class Resourceprivate :bool x_flag; /X鎖標(biāo)記，為真表示已加X鎖bool s_flag;/S鎖標(biāo)記，為真表示已加S鎖ActiveQueue *aqueue; /對應(yīng)資源的活動

7、隊(duì)列WaitQueue *wqueue;/對應(yīng)資源的等待隊(duì)列vb vcbstring resource; /資源內(nèi)容，x_flag、s_flag隊(duì)它進(jìn)行讀寫控制 int resourceNo; /資源編號，唯一標(biāo)志這個(gè)資源public :;2）、用戶結(jié)構(gòu)class Userprivate :int nice; /定義用戶優(yōu)先級，nice值越大優(yōu)先級越高string userName; / 定義用戶名public :;3 )、鎖結(jié)構(gòu)class Lockpublic :virtual char Get_Lock()=0;virtual bool AddLock(Resource* resource

8、)=0;virtual bool FreeLock(Resource* resource)=0; ;class SLock: public Lockpublic :bool AddLock(Resource* r);/ 對資源 r加X鎖bool FreeLock(Resource* r); / 釋放r的X鎖 char Get_Lock() return S;class XLock: public Lockpublic :boolAddLock(Resource* r);/對資源r加X鎖boolFreeLock(Resource* r);:/釋放r的X鎖char Get_Lock() retur

9、n X;4)、等待隊(duì)列、活動隊(duì)列設(shè)計(jì)用基于鏈表的隊(duì)列設(shè)計(jì)等待和活動隊(duì)列鏈表結(jié)點(diǎn)LR定義如下：static enum LockTypeS,X; / 定義鎖的類型class LRpublic :int request, no;User *user;LockType type;LR(User *u,LockType t, int no)user = u; type=t;request_no=no;等待隊(duì)列按用戶的nice值插入元素，nice值越大優(yōu)先級越高，用戶就插在隊(duì)頭，最先出隊(duì)?；顒雨?duì)列則在隊(duì)尾插入，等用戶釋放資源后就從隊(duì)列中刪除相應(yīng)的結(jié)點(diǎn)。5 )、資源高效存儲查詢的設(shè)計(jì)用hash表存儲資源LO

10、結(jié)點(diǎn)如下：class LOpublic :Resource* in dex;/存儲資源地址int eleme nt;/關(guān)鍵碼值LO *n ext;/next指針LO(int & elemVal,Resource* indexVal) eleme nt = elemVal;in dex = in dexVal; LO(int & elemVal,Resource* indexVal,LO* nextVal) eleme nt = elemVal;in dex = in dexVal; n ext = n extVal; LO(LO* nextVal =NULL) next = n extVal;

11、 ;6)、請求、釋放、讀、寫資源的實(shí)現(xiàn)接口如下：void Init(); /新建hash表并且定義所有資源bool Request(User* , int 丄ock*);/ 用戶請求資源bool FreeResouse( int re_no, int rq_no); / 用戶釋放資源bool Read(User*, int ,string&);bool Write(User*, int ,string);void PrintActor( int re_no);void PrintWaiter( int re_no);void PrintResource();bool AddResourse(

12、int re_no,string re_str);4、調(diào)試分析1 )、測試加鎖的相容性，輸入數(shù)據(jù)源代碼如下：if(hash-search(56,r) /找到編號為的資源if (Request(user1,56,x)e ndl;cout Userl request resource 56 by X lock success ! elsee ndl;coutvv User1 request resource 56 by X lock failed ! if(Request(user2,56,s)cout User2 request resource 56 by S locksuccess ! en

13、dl;elsee ndl;cout User2 request resource 56 by S lock failed !if(Request(user3,56,x)cout User3 request resource 56 by X locksuccess ! search(10,r) /找到編號為的資源if (Request(user1,10,s)cout Userl request resource 10 by S locksuccess ! endl;elsecout User1 request resource 10 by S lock failed !if (Request(u

14、ser2,10,s)cout User2 request resource 10 by S locksuccess ! endl;elsecout User2 request resource 10 by S lock failed !e ndl;e ndl;if (Request(user3,10,x)cout User3 request resource 10 by X locksuccess ! *ee r-esoutce resource Ksource 1*630111*06 r-esouiiceby X lock by lock by X lock by S lack bv S l

15、ock hy 丄ticksuccess： ! failed ! failed ! success * success ! Failed 時(shí)間復(fù)雜度分析：O（ 1 ）因?yàn)槊子胔ash表所有插入是常數(shù)級的2）、讀寫操作測試，輸入數(shù)據(jù)源代碼如下:if (Read(user1,10,temp)cout The userl read resource 10 string is : tempendl; elsecerr The user1 cant read resource 10s string! endl;if(Write(user1,10, update_r10)cout The user1 cha

16、nge resource 10s string to:update_r10 endl;elsecerr The user1 cant change resource 10s string !endl;if(Read(user1,56,temp)cout The user1 read resource 56 string is : tempendl;if(Write(user1,56, update_r56)cout The userl change resource 56s string to:update_r56 endl;elsecerr The user1 cant change res

17、ource 56s string !_ AneNIjCe Lock-TypeReqii.eNOueil183user-2204Resoulpcb NO=56ACTOHQU EUE：:UsGr-_Nane Hice Lock_Tpe HequestNOuserl11(T；譯 m LockType -07J S Lock 丄艾 X Lock.時(shí)間復(fù)雜度分析：O（n）需要遍歷完整個(gè)隊(duì)列，時(shí)間復(fù)雜度與隊(duì)列長度成正比4）、測試等待隊(duì)列，輸入數(shù)據(jù)源代碼如下:Prin tWaiter（IO）;Prin tWaiter(56);輸出如下:蟲、測試等持盹列Pesouic：& NOUsi_ ame user3=1

18、0 UAITPP QUEUE：Nice Loc k_T ype FEEpjim：s1:NO515Rtisouie ND =56 UAI TEB QUEUE：Usei_ ameNice Loclf_Type ReQuestNOUssyS5122H1,注爭莘,Lock_Type ：0S Lock. 1為 34 Lock時(shí)間復(fù)雜度分析：O（n）需要遍歷完整個(gè)隊(duì)列，時(shí)間復(fù)雜度與隊(duì)列長度成正比5) 、請求釋放資源測試，輸入數(shù)據(jù)源代碼如下：if(FreeResouse(56,0) /批準(zhǔn)號為的請求釋放資源cout The request.no : 0 uniock resource 56success !

19、 endlvv 現(xiàn)在資源的活動隊(duì)列和等待隊(duì)列如下： e ndl;Prin tActor(56);Prin tWaiter(56);elsecout The request.no : 0 uniock resource 56 failed !endl;if(FreeResouse(10,3) /批準(zhǔn)號為的請求釋放資源cout The request.no : 3 uniock resource 10success ! endlvv 現(xiàn)在資源的活動隊(duì)列和等待隊(duì)列如下： ZZZXZZZ5、請求將放資源測試zzxzzzzxTJiest_ o - 0 unlocksou.rce 5& success現(xiàn)在

20、資源宓的活動隊(duì)列和等待隊(duì)列如下.Hesouiice NO ： 56 ACT OR QUEUEDUs el*_ anteMice Locke_T ype Re qiteSLtNOutser-2S1_2Ties ouitce ND Usei*_N-ane useirS汚 UAITER QUEUE：Nice LockTvpe RqucstHO291successThe requ.est_no : 3 unlock r-esource 10 現(xiàn)在資源5的活動臥列和等待隊(duì)列如下： Tlesouvce NO ；10 AGTQB QUEUE：Usei*_NineNice Lock_Type RequbstN

21、Ousei*2204Tiesoutce HOWAITER QUEUE：User_Naneusei*3NiceLock_T ypeReQuestNO時(shí)間復(fù)雜度分析：0 (n)需要遍歷完整個(gè)等待隊(duì)列，時(shí)間復(fù)雜度與等待隊(duì)列長度成正比6) 、打印資源，輸入源代碼如下:Prin tResource();輸出如下：L/Z/ZZ/6、打印所有資源hashrAhashtlhashtZrintci*2NONE_LOCKhash31hash4;4 printer)NONE_LOCKpr in te pNONE_LOCK?4printei*HONE_LOCKhas)& :5 prinCer4NONE_LOCK15 printei*NONE_LOCK25printei*NONE_LOCKXliash6 hashLYJhashLB Jhash9時(shí)間復(fù)雜度分析：O( n )需要遍歷元整個(gè)ha