「銀行家算法(操作系統(tǒng))」.doc

操作系統(tǒng)實(shí)驗(yàn)報(bào)告題目：銀行家算法班級：網(wǎng)絡(luò)工程姓名：朱錦濤學(xué)號：E31314037一、實(shí)驗(yàn)?zāi)康?用代碼實(shí)現(xiàn)銀行家算法，了解通過銀行家算法避免死鎖的思想。通過代碼的具體實(shí)現(xiàn)，加深對算法的核心的理解。二、實(shí)驗(yàn)原理 我們可以把操作系統(tǒng)看作是銀行家，操作系統(tǒng)管理的資源相當(dāng)于銀行家管理的資金，進(jìn)程向操作系統(tǒng)請求分配資源相當(dāng)于用戶向銀行家貸款。操作系統(tǒng)按照銀行家制定的規(guī)則為進(jìn)程分配資源，當(dāng)進(jìn)程首次申請資源時(shí)，要測試該進(jìn)程對資源的最大需求量，如果系統(tǒng)現(xiàn)存的資源可以滿足它的最大需求量則按當(dāng)前的申請量分配資源，否則就推遲分配。當(dāng)進(jìn)程在執(zhí)行中繼續(xù)申請資源時(shí)，先測試該進(jìn)程已占用的資源數(shù)與本次申請的資源數(shù)之和是否超過了該進(jìn)程對資源的最大需求量。若超過則拒絕分配資源，若沒有超過則再測試系統(tǒng)現(xiàn)存的資源能否滿足該進(jìn)程尚需的最大資源量，若能滿足則按當(dāng)前的申請量分配資源，否則也要推遲分配。三、實(shí)驗(yàn)內(nèi)容源程序：#include#include#includetypedef struct Procedureint Max3; /滿足此進(jìn)程需要三類資源的數(shù)量int Allocation3; /系統(tǒng)已經(jīng)為該進(jìn)程分配的資源情況int Need3; /該進(jìn)程還需要資源數(shù)量int flag; /標(biāo)志位，執(zhí)行完之前為0，執(zhí)行完之后為1char p; /在執(zhí)行完之后，給出相應(yīng)的編號，如P1，P2struct Procedure * pNext;Pro,*PNODE; /如果系統(tǒng)資源足夠多的話，那么所有的安全序列的數(shù)量就會是5*4*3*2*1=120個(gè)PNODE create_list(int &len);void traverse_list(PNODE pHead);int cnt_exe(PNODE pHead,int *system,int i); /計(jì)算目前系統(tǒng)能夠執(zhí)行的進(jìn)程數(shù)int work(PNODE pHead,int *system);int main()int ok;int len;srand(time(0);int system3 = rand()%5+10,rand()%5+2,rand()%5+5;printf(系統(tǒng)中可用的各類資源數(shù)分別為:%d %d %dn,system0,system1,system2);Pro *pHead = create_list(len);traverse_list(pHead);int cnt = cnt_exe(pHead,system,3);if(cnt = 0)printf(對不起，不存在安全序列n);return 0;elseint ok = work(pHead,system);if(ok = len)printf(恭喜！存在安全序列！n);elseprintf(很抱歉！不存在安全序列！n);return 0;PNODE create_list(int &len)int i,j;char c = A; /用來臨時(shí)存放用戶輸入的結(jié)點(diǎn)的值/分配了一個(gè)不存放有效數(shù)據(jù)的頭結(jié)點(diǎn)PNODE pHead = (PNODE)malloc(sizeof(Pro);if (NULL = pHead)printf(分配失敗, 程序終止!n);exit(-1);PNODE pTail = pHead;pTail-pNext = NULL;printf(請輸入您需要生成的鏈表節(jié)點(diǎn)的個(gè)數(shù):);scanf(%d, &len);for (i=0; ilen; +i)PNODE pNew = (PNODE)malloc(sizeof(Pro);if (NULL = pNew)printf(分配失敗, 程序終止!n);exit(-1);for(j=0;jMaxj = rand()%5+4;pNew-Allocationj = rand()%5;pNew-Needj = pNew-Maxj - pNew-Allocationj;pNew-flag = 0;pNew-p = c;pTail-pNext = pNew;pNew-pNext = NULL;pTail = pNew;c+;return pHead;void traverse_list(PNODE pHead)PNODE p = pHead-pNext;int i = 1;while (NULL != p)printf(第%d個(gè)資源的需要資源總數(shù)各為:%d %d %d,i, p-Max0,p-Max1,p-Max2);printf(n);printf(第%d個(gè)資源已分配資源總數(shù)各為:%d %d %d,i, p-Allocation0,p-Allocation1,p-Allocation2);printf(n);printf(第%d個(gè)資源還需要資源總數(shù)各為:%d %d %d,i, p-Need0,p-Need1,p-Need2);printf(n);printf(n);p = p-pNext;i+;printf(n);return;int cnt_exe(PNODE pHead,int *system,int i)PNODE p;p = pHead-pNext; /p指向第一個(gè)節(jié)點(diǎn)int count = 0;while(p != NULL)if(system0 = p-Need0 & system1 = p-Need1 & system2 = p-Need2)count+;p = p-pNext;return count;int work(PNODE pHead,int *system)PNODE p;p = pHead-pNext; /p指向第一個(gè)節(jié)點(diǎn) int ok = 0;while(p != NULL)if(system0 = p-Need0 & system1 = p-Need1 & system2 = p-Need2)system0 += p-Allocation0;system1 += p-Allocation1;system2 += p-Allocation2;p-flag = 1;ok+;printf(系統(tǒng)已經(jīng)為您執(zhí)行了進(jìn)程：%cn,p-p);PNODE q;q = pHead; /尋找q的前一個(gè)節(jié)點(diǎn)，方便刪掉q節(jié)點(diǎn)while( q-pNext != p )q = q-pNext; q-pNext = p-pNext;free(p);p = NULL;p = pHead-pNext;/p又重新指向第一個(gè)節(jié)點(diǎn)elsep = p-pNext;return ok;存在安全序列的情況：不存在安全序列的情況：四、實(shí)驗(yàn)小結(jié)用隨機(jī)數(shù)為系統(tǒng)分配三類資源的個(gè)數(shù)，隨后系統(tǒng)為每個(gè)作業(yè)分配每個(gè)資源需要的個(gè)數(shù)和已經(jīng)分配的資源數(shù)量，那么還需要資源的數(shù)量則有最大分配量減去已經(jīng)分配的數(shù)量。 系統(tǒng)在隊(duì)列中尋找能滿足當(dāng)前條件的作業(yè)，運(yùn)行完之后，將其資源釋放，把各類資源重新還給系統(tǒng)。把運(yùn)行完之后的作業(yè)從隊(duì)列中刪除，系統(tǒng)再從隊(duì)列開頭重新