linux系統下實現銀行家算法

1 實驗題目要求

1.1

在銀行中，客戶申請貸款的數量是有限的，每個客戶在第一次申請貸款時要聲明完成該項目所需的最大資金量，在滿足所有貸款要求時，客戶應及時歸還。銀行家在客戶申請的貸款數量不超過自己擁有的最大值時，都應盡量滿足客戶的需要。在這樣的描述中，銀行家就好比操作系統，資金就是資源，客戶就相當于要申請資源的進程。銀行家算法是一種最有代表性的避免死鎖的算法。在避免死鎖方法中允許進程動態地申請資源，但系統在進行資源分配之前，應先計算此次分配資源的安全性，若分配不會導致系統進入不安全狀態，則分配，否則等待。為實現銀行家算法，系統必須設置若干數據結構。

要解釋銀行家算法，必須先解釋操作系統安全狀態和不安全狀態。

特別要注意實現部分。 注意命令行參數 ./a.out 10 5 7 僅是個列子，你所涉及的程序需要支持n個線程對m個資源的并發訪問請求，因此需要對上面的命令行進行擴展。

1.2

在實驗過程中，能夠通過屏幕或者文件，保存每個客戶線程申請資源的情況—申請多少；是否被分配等。（每個客戶線程每次申請資源量不超過它們的need數組相應值）。

1.3

完成的報告需要有詳細的設計、代碼及注釋、實驗結果及分析說明。

2 準備知識

2.1 銀行家算法

2.1.1什么是銀行家算法?

銀行家算法（Banker’s Algorithm）是一個避免死鎖（Deadlock）的著名算法，是由艾茲格·迪杰斯特拉在1965年為T.H.E系統設計的一種避免死鎖產生的算法。它以銀行借貸系統的分配策略為基礎，判斷并保證系統的安全運行。

在銀行中，客戶申請貸款的數量是有限的，每個客戶在第一次申請貸款時要聲明完成該項目所需的最大資金量，在滿足所有貸款要求時，客戶應及時歸還。銀行家在客戶申請的貸款數量不超過自己擁有的最大值時，都應盡量滿足客戶的需要。在這樣的描述中，銀行家就好比操作系統，資金就是資源，客戶就相當于要申請資源的進程。

銀行家算法是一種最有代表性的避免死鎖的算法。在避免死鎖方法中允許進程動態地申請資源，但系統在進行資源分配之前，應先計算此次分配資源的安全性，若分配不會導致系統進入不安全狀態，則分配，否則等待。為實現銀行家算法，系統必須設置若干數據結構。

2.1.2銀行家算法中的數據結構

為了實現銀行家算法，在系統中必須設置這樣四個數據結構，分別用來描述系統中可利用的資源、所有進程對資源的最大需求、系統中的資源分配，以及所有進程還需要多少資源的情況。

(1) 可利用資源向量 Available。這是一個含有 m 個元素的數組，其中的每一個元素代表一類可利用的資源數目，其初始值是系統中所配置的該類全部可用資源的數目，其數值隨該類資源的分配和回收而動態地改變。如果 Available[j] = K，則表示系統中現Rj類資源K個。

(2) 最大需求矩陣Max。這是一個n x m的矩陣，它定義了系統中n個進程中的每個進程對m類資源的最大需求。如果Max[i,j] = K，則表示進程i需要Rj 類資源的最大數目為K。

(3) 分配矩陣 Allocation。這也是一個n x m的矩陣，它定義了系統中每一類資源當前已分配給每一進程的資源數。如果 Allocation[i,jl = K，則表示進程i當前己分得Rj類資源的數目為K。

(4) 需求矩陣Need.這也是一個n×m的矩陣，用以表示每一個進程尚需的各類資源數。如果Need[i,j] = K，則表示進程i還需要Rj類資源K個方能完成其任務。

上述三個矩陣間存在下述關系:

Need[i,j] = Max[i,j] - allocation[i, j]

2.1.3 銀行家算法詳述

設 Request；是進程Pi的請求向量，如果 Requesti[j] = K，表示進程Pi需要K個Rj類型的資源。當Pi發出資源請求后，系統按下述步驟進行檢査:

(1) 如果 Requesti[j] ≤ Need[i,j]便轉向步驟(2)；否則認為出錯，因為它所需要的資源數已超過它所宣布的最大值。

(2) 如果 Requesti[j] ≤ Available[j]，便轉向步驟(3)；否則，表示尚無足夠資源，Pi須等待。

(3) 系統試探著把資源分配給進程Pi，并修改下面數據結構中的數值

Available[j] = Available[j] - Requesti[j];

Allocation[i,j] = Allocation[i,j] + Requesti[j];

Need[i,j] = Need[i,j] - Requesti[j];

(4) 系統執行安全性算法，檢查此次資源分配后系統是否處于安全狀態。若安全，才正式將資源分配給進程Pi，以完成本次分配；否則，將本次的試探分配作廢，恢復原來的資源分配狀態，讓進程Pi等待。

2.1.4安全性算法

系統所執行的安全性算法可描述如下:

(1) 設置兩個向量:①工作向量Work，它表示系統可提供給進程繼續運行所需的各類資源數目，它含有m個元素，在執行安全算法開始時，Work = Available；② Finish:它表示系統是否有足夠的資源分配給進程，使之運行完成。開始時先做 Finish[i] = false；當有足夠資源分配給進程時，再令Finish[i] = true。

(2) 從進程集合中找到一個能滿足下述條件的進程

① Finish[i] = false;

② Need[i,j] ≤ Work[j];

若找到，執行步驟(3)，否則，執行步驟(4)。

(3)當進程Pi獲得資源后，可順利執行，直至完成，并釋放出分配給它的資源，故應執行:

Work[j] = Work[j] + Allocation[i,j];

Finish[i] = true;

go to step 2;(goto語句不推薦使用 _ )

(4)如果所有進程的 Finish[i] =true都滿足，則表示系統處于安全狀態；否則，系統處于不安全狀態。

2.1.5難點透析

本程序的難點在于安全性算法，對于一個安全的系統來說，此步驟較為容易，難在于判斷不安全的系統。為什么這么說呢？由于本程序再設計尋找安全序列的部分使用while循環，就需要找到分別處理安全系統與不安全系統的終止循環條件，對于安全的系統，滿足條件 Finish[i] = false 和 Need[i,j] ≤ Work[j] 的，必定也會按照預期的將 Finish[i] 向量全部置為true，那是不是就可以設置一個變量來累加計數，當該變量與進程數量相等的時候，就說明已經全部置為true了，終止循環，也就是說系統安全。

對于不安全的系統，上述方法肯定是不行的，因為不可能將向量 Finish[i] 都置為 true ，必定存在 false。就得尋求一個跳出循環的條件，但是由于需要不斷循環查找并嘗試分配，尋求一個安全序列，到底該怎么算是已經找不到安全路徑了呢？下面說本程序的解決辦法，首先需要想到的是，當我們尋找一輪都沒有找到一個可以安全執行的進程，是不是就說明往后也找不到了呢？沒錯，就是這樣的！所以我們每次在記錄 Finish[i] = true 的次數的時候，不妨把這個次數再使用另一個變量存放起來，然后在判斷語句當中判斷當尋找一輪下來，該值未發生改變，說明已經找不到安全的進程了，即可跳出循環，該系統不安全！

2.2 互斥鎖

當多個線程幾乎同時修改某一個共享數據的時候，需要進行同步控制

線程同步能夠保證多個線程安全訪問競爭資源，最簡單的同步機制是引入互斥鎖。

互斥鎖為資源引入一個狀態：鎖定/非鎖定

某個線程要更改共享數據時，先將其鎖定，此時資源的狀態為“鎖定”，其他線程不能更改；直到該線程釋放資源，將資源的狀態變成“非鎖定”，其他的線程才能再次鎖定該資源。互斥鎖保證了每次只有一個線程進行寫入操作，從而保證了多線程情況下數據的正確性。

threading模塊中定義了Lock類，可以方便的處理鎖定：

創建鎖

mutex = threading.Lock()

#鎖定

mutex.acquire()

釋放

mutex.release()

注意：

如果這個鎖之前是沒有上鎖的，那么acquire不會堵塞

如果在調用acquire對這個鎖上鎖之前 它已經被 其他線程上了鎖，那么此時acquire會堵塞，直到這個鎖被解鎖為止

定義：

1.pthread_mutex_t mutex=PTHREAD_MUTEX_INITIALIZER; 2.pthread_mutex_t mutex; pthread_mutex_init(&mutex); 以上兩種方式都行

實現

pthread_mutex_t mutex=PTHREAD_MUTEX_INITIALIZER;//創建互斥鎖并初始化 pthread_mutex_lock(&mutex)；//對線程上鎖，此時其他線程阻塞等待該線程釋放鎖

要執行的代碼段

pthread_mutex_unlock(&mutex);//執行完后釋放鎖

上鎖解鎖過程

當一個線程調用鎖的acquire()方法獲得鎖時，鎖就進入“locked”狀態。

每次只有一個線程可以獲得鎖。如果此時另一個線程試圖獲得這個鎖，該線程就會變為“blocked”狀態，稱為“阻塞”，直到擁有鎖的線程調用鎖的release()方法釋放鎖之后，鎖進入“unlocked”狀態。

線程調度程序從處于同步阻塞狀態的線程中選擇一個來獲得鎖，并使得該線程進入運行（running）狀態。

2.3 多線程創建

2.3.1pthread方法

在Linux系統下，與線程相關的函數都定義在pthread.h頭文件中。

創建線程函數———pthread_create函數

#include int pthread_create(pthread_t * thread, const pthread_arrt_t* attr,void*(*start_routine)(void *), void* arg);

（1）thread參數是新線程的標識符,為一個整型。

（2）attr參數用于設置新線程的屬性。給傳遞NULL表示設置為默認線程屬性。

（3）start_routine和arg參數分別指定新線程將運行的函數和參數。start_routine返回時,這個線程就退出了

（4）返回值:成功返回0,失敗返回錯誤號。

線程id的類型是thread_t,它只在當前進程中保證是唯一的,在不同的系統中thread_t這個類型有不同的實現，調用pthread_self()可以獲得當前線程的id 進程id的類型時pid_t,每個進程的id在整個系統中是唯一的,調用getpid()可以獲得當前進程的id,是一個正整數值。

#include #include #include void* myfun(void* arg); int main(int argc, char *argv[]) { pthread_t pthread = 0; //創建一個子線程 int ret = pthread_create(&pthread, NULL, myfun, NULL); printf("parent thread id: %ld\n", pthread_self); sleep(2); //避免主線程運行后，就死亡了，而子線程沒機會 for (int i = 0; i < 5; i++) { //驗證子線程，并不會執行這里面的代碼，只會執行回調函數 muyfun 里面的 printf("i = %d\n", i); } return 0; } void* myfun(void* arg) { printf("child thread id: %ld\n", pthread_self); return NULL; }

2.3.2 fork()函數

調用 fork 時，系統將創建一個與當前進程相同的新進程。通常將原有的進程稱為父進程，把新創建的進程稱為子進程。子進程是父進程的一個拷貝，子進程獲得同父進程相同的數據，但是同父進程使用不同的數據段和堆棧段。子進程從父進程繼承大多數的屬性，但是也修改一些屬性。

#include #include int main() { pid_t pid=fork();//創建子進程 //如果創建子進程失敗，pid的返回值小于0,子進程創建出現錯誤 //如果創建子進程成功，pid返回值有兩個，子進程返回0,父進程返回子進程ID if(pid<0) { printf("創建子進程失敗！\n"); } if(pid==0) { printf("這個是執行子進程的輸出結果，pid=%d\n",getpid()); printf("他的父進程的pid為，pid=%d\n",getppid()); } else { printf("這個是執行父進程的輸出結果，pid=%d\n",getpid()); printf("父進程創建的子進程的pid為，pid=%d\n",pid); } }

3 銀行家算法實現

3.1 流程圖

3.2代碼

#include #include #include #include #include #include #define random_1(a,b) ((rand()%(b-a))+a) //隨機值將含a不含b int nResources=0,nProcesses=0;//定義輸入的資源種類和進程數量 int resources[99];//資源數 int allocated[99][99];//為每個進程分配的實例數量 int maxRequired[99][99];//每個進程的最大需求 int need[99][99];//每個進程還需要的資源 int safeSeq[99];//判斷系統是否處于安全狀態 int nProcessRan = 0;//已經執行過的進程數量 pthread_mutex_t lockResources;//進程互斥鎖 pthread_cond_t condition;//進程等待 //系統如果處于安全狀態返回true，不安全返回false bool getSafeSeq(); // 多進程互斥部分代碼 void* processCode(void* ); int main() { srand((int)time(NULL)); //設置隨機數種子，防止每次產生的隨機數相同 printf("請輸入進程的數量：\n "); scanf("%d", &nProcesses); printf("請輸入資源類型的種類：\n "); scanf("%d", &nResources); printf("請依次輸出每種資源目前可得到的數量：\n"); for(int i=0; i

3.3 運行結果(隨機性)

編譯時不要忘記加-pthread

Linux 任務調度

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。