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

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