軟件技術(shù)基礎(chǔ) (11)處理器管理2

1、NO：1 第四章第四章 操作系統(tǒng)操作系統(tǒng)4.2 4.2 處理器管理處理器管理 閱讀者寫入者問題閱讀者寫入者問題 一些讀者和一些寫者對同一黑板進(jìn)行讀寫。多個讀者一些讀者和一些寫者對同一黑板進(jìn)行讀寫。多個讀者可同時讀黑板，但一個時刻只能有一個寫者，讀者、寫者可同時讀黑板，但一個時刻只能有一個寫者，讀者、寫者不能同時使用黑板。不能同時使用黑板。 分析：分析： 對于讀者來說：對于讀者來說： 1) 無讀者、寫者，新讀者可以讀無讀者、寫者，新讀者可以讀 2) 有寫者等，但有其他讀者正在讀，則新讀者也可以讀有寫者等，但有其他讀者正在讀，則新讀者也可以讀 3) 有寫者，新讀者等有寫者，新讀者等 對于寫者來說：

2、對于寫者來說： 1) 無讀者，新寫者可以寫無讀者，新寫者可以寫 2) 有讀者，新寫者等待有讀者，新寫者等待 3) 有其他寫者，新寫者等待有其他寫者，新寫者等待NO：2 第四章第四章 操作系統(tǒng)操作系統(tǒng)設(shè)置設(shè)置2個信號量，個信號量，w控制誰使用黑板，控制誰使用黑板，mutex保護(hù)臨界區(qū)，保護(hù)臨界區(qū)，初值都為初值都為1讀者：讀者：P(mutex)Readcount+if(Readcount=1)P(w)V(mutex)讀數(shù)據(jù)讀數(shù)據(jù)P(mutex)Readcount - -if(readcount=0)V(w)寫者：寫者：P(w)寫數(shù)據(jù)寫數(shù)據(jù)V(w)V(mutex)上述方法其實是上述方法其實是”讀者優(yōu)

3、先讀者優(yōu)先”，只要有一個讀者，就允許其后只要有一個讀者，就允許其后的讀者訪問數(shù)據(jù)。如果一直有的讀者訪問數(shù)據(jù)。如果一直有新的讀者陸續(xù)到來，寫者將被新的讀者陸續(xù)到來，寫者將被嚴(yán)重推遲。嚴(yán)重推遲。NO：3為了防止為了防止”讀者優(yōu)先讀者優(yōu)先”導(dǎo)致的導(dǎo)致的寫者饑餓寫者饑餓，可以考慮，可以考慮寫者優(yōu)先寫者優(yōu)先。當(dāng)共享區(qū)被讀者占用時，后續(xù)緊鄰到達(dá)的讀者可以繼續(xù)進(jìn)入。當(dāng)共享區(qū)被讀者占用時，后續(xù)緊鄰到達(dá)的讀者可以繼續(xù)進(jìn)入。若此時有一個寫者到來且阻塞等待，則寫者后面到來的若干若此時有一個寫者到來且阻塞等待，則寫者后面到來的若干讀者全部阻塞等待。讀者全部阻塞等待。換句話說，只要有一個寫者申請寫數(shù)據(jù)，則不允許新的讀者

4、換句話說，只要有一個寫者申請寫數(shù)據(jù)，則不允許新的讀者進(jìn)入讀數(shù)據(jù)。這樣，寫者只需等先于它到來的讀者完成其讀進(jìn)入讀數(shù)據(jù)。這樣，寫者只需等先于它到來的讀者完成其讀數(shù)據(jù)，就可以寫入。數(shù)據(jù)，就可以寫入。 第四章第四章 操作系統(tǒng)操作系統(tǒng)4.2 4.2 處理器管理處理器管理NO：4讀者進(jìn)程讀者進(jìn)程 寫者進(jìn)程寫者進(jìn)程 P(z) P(y) P(rsem) writecount+ P(x) if writecount = 1 readcount+ P(rsem) if readcount = 1 V(y) P(wsem) P(wsem) V(x) : V(rsem) : V(z) 寫數(shù)據(jù)寫數(shù)據(jù) : : 讀讀 :

5、: V(wsem) P(x) P(y) readcount- writecount- if readcount = 0 if writecount=0 V(wsem) V(rsem) V(x) V(y)x 互斥對互斥對readcount訪問訪問y 互斥對互斥對writecount訪問訪問rsem 當(dāng)至少有當(dāng)至少有1個寫進(jìn)程申請個寫進(jìn)程申請寫數(shù)據(jù)時，互寫數(shù)據(jù)時，互斥新的讀進(jìn)程斥新的讀進(jìn)程讀數(shù)據(jù)讀數(shù)據(jù)z rsem阻塞隊阻塞隊列僅允許一個列僅允許一個讀者排隊等待，讀者排隊等待，其后來的讀者其后來的讀者將在信號量將在信號量z的的阻塞隊列中等阻塞隊列中等待待NO：5一個簡單例子：一個簡單例子：/Defi

6、ne a global variable. long g_x = 0;DWORD WINAPI ThreadFunc1(PVOID pvParam) g_x+; return(0); DWORD WINAPI ThreadFunc2(PVOID pvParam) g_x+; return(0); 第四章第四章 操作系統(tǒng)操作系統(tǒng)線程同步問題線程同步問題MOV EAX, g_xINC EAX MOV g_x, EAXNO：6 第四章第四章 操作系統(tǒng)操作系統(tǒng)線程同步問題線程同步問題 兩個線程不可能在完全相同的時間內(nèi)執(zhí)行這個代碼。因兩個線程不可能在完全相同的時間內(nèi)執(zhí)行這個代碼。因此，如果一個線程在另一

7、個線程的后面執(zhí)行這個代碼，那么此，如果一個線程在另一個線程的后面執(zhí)行這個代碼，那么下面就是實際的執(zhí)行情況：下面就是實際的執(zhí)行情況： MOV EAX, g_x ; Thread 1INC EAX MOV g_x, EAX MOV EAX, g_x ; Thread 2INC EAX MOV g_x, EAX當(dāng)兩個線程都將當(dāng)兩個線程都將 g _ x 的值遞增之的值遞增之后，后， g _ x 中的值就變成了中的值就變成了2。 但但 Wi n d o w s是個是個搶占式搶占式多線程環(huán)境。多線程環(huán)境。一個線程可以隨時中斷運行，而另一一個線程可以隨時中斷運行，而另一個線程則可以隨時繼續(xù)執(zhí)行個線程則可以隨

8、時繼續(xù)執(zhí)行。 NO：7 第四章第四章 操作系統(tǒng)操作系統(tǒng)線程同步問題線程同步問題MOV EAX, g_x ; Thread 1INC EAX ; Thread 1MOV EAX, g_x ;Thread 2INC EAX ;Thread 2MOV g_x, EAX ;Thread 2MOV g_x, EAX ;Thread 1如果代碼按這種形式來運行，如果代碼按這種形式來運行， g _ x中的最后值就不是中的最后值就不是2，而是，而是1。 編譯器生成代碼的方法，哪個編譯器生成代碼的方法，哪個C P U在執(zhí)行這個代碼，以在執(zhí)行這個代碼，以及主計算機(jī)中安裝了多少個及主計算機(jī)中安裝了多少個C P U等

9、因素，決定了產(chǎn)生的結(jié)果等因素，決定了產(chǎn)生的結(jié)果可能是不同的。這就是該環(huán)境的運行情況，我們對此無能為力。可能是不同的。這就是該環(huán)境的運行情況，我們對此無能為力。但是，但是， 操作系統(tǒng)確實提供了一些函數(shù)，如果正確地使用這些操作系統(tǒng)確實提供了一些函數(shù)，如果正確地使用這些函數(shù)，就能確保產(chǎn)生應(yīng)用程序的代碼得到的結(jié)果。函數(shù)，就能確保產(chǎn)生應(yīng)用程序的代碼得到的結(jié)果。 NO：8多個線程同時訪問同一個全局變量，如果都是讀取操作，則多個線程同時訪問同一個全局變量，如果都是讀取操作，則不會出現(xiàn)問題。如果不會出現(xiàn)問題。如果一個線程負(fù)責(zé)一個線程負(fù)責(zé)改變改變此變量的值此變量的值，而，而其他其他線程負(fù)責(zé)線程負(fù)責(zé)同時讀取同時讀

10、取變量內(nèi)容變量內(nèi)容，則不能保證讀取到的數(shù)據(jù)是經(jīng)，則不能保證讀取到的數(shù)據(jù)是經(jīng)過寫線程修改后的。過寫線程修改后的。為了確保讀線程讀取到的是經(jīng)過修改的變量，就必須在為了確保讀線程讀取到的是經(jīng)過修改的變量，就必須在向變量向變量寫入數(shù)據(jù)時禁止其他線程對其的任何訪問寫入數(shù)據(jù)時禁止其他線程對其的任何訪問，直至賦值，直至賦值過程結(jié)束后再解除對其他線程的訪問限制。象這種保證線程過程結(jié)束后再解除對其他線程的訪問限制。象這種保證線程能了解其他線程任務(wù)處理結(jié)束后的處理結(jié)果而采取的保護(hù)措能了解其他線程任務(wù)處理結(jié)束后的處理結(jié)果而采取的保護(hù)措施即為線程同步。施即為線程同步。 第四章第四章 操作系統(tǒng)操作系統(tǒng)VC+ 對線程同步

11、的處理對線程同步的處理NO：9臨界區(qū)（臨界區(qū)（Critical Section）是一段獨占對某些共享資源訪問的是一段獨占對某些共享資源訪問的代碼，在任意時刻代碼，在任意時刻只允許一個線程只允許一個線程對共享資源進(jìn)行訪問。如對共享資源進(jìn)行訪問。如果有多個線程試圖同時訪問臨界區(qū)，那么在有一個線程進(jìn)入果有多個線程試圖同時訪問臨界區(qū)，那么在有一個線程進(jìn)入后其他所有試圖訪問此臨界區(qū)的線程將被掛起，并一直持續(xù)后其他所有試圖訪問此臨界區(qū)的線程將被掛起，并一直持續(xù)到進(jìn)入臨界區(qū)的線程離開。臨界區(qū)在被釋放后，其他線程可到進(jìn)入臨界區(qū)的線程離開。臨界區(qū)在被釋放后，其他線程可以繼續(xù)搶占，并以此達(dá)到用以繼續(xù)搶占，并以此達(dá)

12、到用原子方式原子方式操作共享資源的目的。操作共享資源的目的。 第四章第四章 操作系統(tǒng)操作系統(tǒng)4.2 4.2 處理器管理處理器管理NO：10臨界區(qū)在使用時以臨界區(qū)在使用時以CRITICAL_SECTION結(jié)構(gòu)對象保護(hù)結(jié)構(gòu)對象保護(hù)共享資源，并分別用共享資源，并分別用EnterCriticalSection（）（）和和LeaveCriticalSection（）（）函數(shù)去標(biāo)識和釋放一個臨界區(qū)。所用函數(shù)去標(biāo)識和釋放一個臨界區(qū)。所用到的到的CRITICAL_SECTION結(jié)構(gòu)對象必須經(jīng)過結(jié)構(gòu)對象必須經(jīng)過InitializeCriticalSection（）（）的初始化后才能使用，而且必須的初始化后才能使

13、用，而且必須確保所有線程中的任何試圖訪問此共享資源的代碼都處在此確保所有線程中的任何試圖訪問此共享資源的代碼都處在此臨界區(qū)的保護(hù)之下。否則臨界區(qū)將不會起到應(yīng)有的作用，共臨界區(qū)的保護(hù)之下。否則臨界區(qū)將不會起到應(yīng)有的作用，共享資源依然有被破壞的可能。享資源依然有被破壞的可能。 第四章第四章 操作系統(tǒng)操作系統(tǒng)4.2 4.2 處理器管理處理器管理NO：11例：通過例：通過兩個線程兩個線程來分別對來分別對全局變量全局變量g_cArray10進(jìn)行寫入進(jìn)行寫入操作，用臨界區(qū)結(jié)構(gòu)對象操作，用臨界區(qū)結(jié)構(gòu)對象g_cs來保持線程的同步，并在開啟來保持線程的同步，并在開啟線程前對其進(jìn)行初始化。線程前對其進(jìn)行初始化。為

14、了使實驗效果更加明顯，體現(xiàn)出臨界區(qū)的作用，在線程函為了使實驗效果更加明顯，體現(xiàn)出臨界區(qū)的作用，在線程函數(shù)對共享資源數(shù)對共享資源g_cArray10的寫入時，以的寫入時，以Sleep（）函數(shù)延遲（）函數(shù)延遲1毫秒，使其他線程同其搶占毫秒，使其他線程同其搶占CPU的可能性增大。如果不使的可能性增大。如果不使用臨界區(qū)對其進(jìn)行保護(hù)，則共享資源數(shù)據(jù)將被破壞，而使用用臨界區(qū)對其進(jìn)行保護(hù)，則共享資源數(shù)據(jù)將被破壞，而使用臨界區(qū)對線程保持同步后則可以得到正確的結(jié)果。臨界區(qū)對線程保持同步后則可以得到正確的結(jié)果。 第四章第四章 操作系統(tǒng)操作系統(tǒng)4.2 4.2 處理器管理處理器管理NO：12 第四章第四章 操作系統(tǒng)操

15、作系統(tǒng)4.2 4.2 處理器管理處理器管理2 進(jìn)程通信進(jìn)程通信進(jìn)程間的通信機(jī)制（進(jìn)程間的通信機(jī)制（IPC），就是多進(jìn)程間相互通訊、交還），就是多進(jìn)程間相互通訊、交還信息的方法。信息的方法。Linux中提供了下面幾種通信機(jī)制。中提供了下面幾種通信機(jī)制。 管道（管道（pipe） 命名管道（命名管道（FIFO） System V機(jī)制，包括消息隊列、信號量和共享內(nèi)存機(jī)制，包括消息隊列、信號量和共享內(nèi)存 網(wǎng)絡(luò)網(wǎng)絡(luò)socket方式方式NO：13 第四章第四章 操作系統(tǒng)操作系統(tǒng)4.2 4.2 處理器管理處理器管理 管道通信管道通信 PIPE管道就是將一個進(jìn)程的管道就是將一個進(jìn)程的標(biāo)準(zhǔn)輸出標(biāo)準(zhǔn)輸出和另一個進(jìn)程

16、的和另一個進(jìn)程的標(biāo)準(zhǔn)輸入標(biāo)準(zhǔn)輸入聯(lián)聯(lián)系到一起，以供二個進(jìn)程互相通信的方法。系到一起，以供二個進(jìn)程互相通信的方法。當(dāng)一個進(jìn)程創(chuàng)建了管道時，系統(tǒng)內(nèi)核為使用管道準(zhǔn)備了當(dāng)一個進(jìn)程創(chuàng)建了管道時，系統(tǒng)內(nèi)核為使用管道準(zhǔn)備了二個二個文件描述符文件描述符，一個用于管道輸入，也就是，一個用于管道輸入，也就是往管道寫入往管道寫入數(shù)據(jù)；數(shù)據(jù)；另一個用戶管道輸出，也就是另一個用戶管道輸出，也就是從管道讀出從管道讀出數(shù)據(jù)。數(shù)據(jù)。用戶進(jìn)程用戶進(jìn)程fd0fd1管道管道內(nèi)內(nèi) 核核NO：14 第四章第四章 操作系統(tǒng)操作系統(tǒng)4.2 4.2 處理器管理處理器管理管道只能用于有管道只能用于有相同祖先相同祖先的進(jìn)程之間的通信，通常是一個

17、進(jìn)的進(jìn)程之間的通信，通常是一個進(jìn)程創(chuàng)建管道后，調(diào)用程創(chuàng)建管道后，調(diào)用fork函數(shù)創(chuàng)建子進(jìn)程，而這個管道就是函數(shù)創(chuàng)建子進(jìn)程，而這個管道就是用于用于父進(jìn)程和子進(jìn)程間的通信父進(jìn)程和子進(jìn)程間的通信。int fd2;int fd2;pid_t pid;pid_t pid;.if ( if ( pipe(fd)pipe(fd) 0) printf(stderr, pipe error); exit(1); 0) printf(stderr, pipe error); exit(1); if (if (pid=fork()pid=fork()0) printf(stderr, fork error); ex

18、it(1); ) 0pid 0) /) /* *父進(jìn)程父進(jìn)程* */ / close( close(fd0fd0); write(); write(fd1fd1, how are you ?n, 12);, how are you ?n, 12);else /else /* * 子進(jìn)程子進(jìn)程 * */ / close( close(fd1fd1); n= read(); n= read(fd0fd0, line, MAXLINE); , line, MAXLINE); . 管道是半雙工方式，如果要父子雙方互相傳遞數(shù)據(jù)，需要建立二道管道管道是半雙工方式，如果要父子雙方互相傳遞數(shù)據(jù)，需要建立二道管

19、道NO：15 第四章第四章 操作系統(tǒng)操作系統(tǒng)4.2 4.2 處理器管理處理器管理 命名管道命名管道 FIFO命名管道又叫命名管道又叫先進(jìn)先出隊列先進(jìn)先出隊列，類似于前面介紹的管道。但可，類似于前面介紹的管道。但可用于沒有任何聯(lián)系的進(jìn)程間通信（不局限于父子進(jìn)程之間）用于沒有任何聯(lián)系的進(jìn)程間通信（不局限于父子進(jìn)程之間）管道管道PIPE是在內(nèi)核中存儲的，程序運行結(jié)束后不復(fù)存在，而是在內(nèi)核中存儲的，程序運行結(jié)束后不復(fù)存在，而命名管道命名管道FIFO是作為是作為特殊設(shè)備文件特殊設(shè)備文件存儲在文件系統(tǒng)中。除非存儲在文件系統(tǒng)中。除非刪除該文件，否則不會消失。刪除該文件，否則不會消失。命名管道創(chuàng)建：命名管道創(chuàng)

20、建： int mkfifo ( const char * pathname, mode_t mode); int mknod ( char * pathname, mode_t mode, dev_t dev); NO：16 第四章第四章 操作系統(tǒng)操作系統(tǒng)4.2 4.2 處理器管理處理器管理命名管道的應(yīng)用命名管道的應(yīng)用 : 簡單的客戶服務(wù)器模式簡單的客戶服務(wù)器模式 服務(wù)器打開一個所有客戶進(jìn)程都可以訪問的命名管道，服務(wù)器打開一個所有客戶進(jìn)程都可以訪問的命名管道，通過這個管道接收客戶進(jìn)程的信息。通過這個管道接收客戶進(jìn)程的信息。服務(wù)器服務(wù)器客戶都可訪客戶都可訪問的問的FIFOreadread客客 戶

21、戶客客 戶戶writewritewritewriteNO：17 第四章第四章 操作系統(tǒng)操作系統(tǒng)4.2 4.2 處理器管理處理器管理 System V IPC機(jī)制機(jī)制三種機(jī)制：三種機(jī)制：消息隊列消息隊列、信號量信號量、共享內(nèi)存共享內(nèi)存 消息隊列消息隊列：消息隊列是一條由消息連接而成的鏈表，它消息隊列是一條由消息連接而成的鏈表，它保存在內(nèi)核中，通過消息隊列的引用標(biāo)識符來訪問。保存在內(nèi)核中，通過消息隊列的引用標(biāo)識符來訪問。 創(chuàng)建或打開消息隊列創(chuàng)建或打開消息隊列 int msgget( key_t key, int flag ); 向消息隊列發(fā)送消息向消息隊列發(fā)送消息 int msgsnd(int m

22、sqid, const void *ptr, size_t nbytes, int flag); 從消息隊列中接收消息從消息隊列中接收消息 int msgrcv(int msqid, void *ptr, size_t nbytes, long type, int flag);NO：18 第四章第四章 操作系統(tǒng)操作系統(tǒng)4.2 4.2 處理器管理處理器管理 信號量信號量：與先前與先前PV操作中的相同，實際上是個整數(shù)計數(shù)操作中的相同，實際上是個整數(shù)計數(shù)器，用來控制多個進(jìn)程對共享資源的訪問。器，用來控制多個進(jìn)程對共享資源的訪問。 創(chuàng)建信號量創(chuàng)建信號量 int semget( key_t key, i

23、nt flag ); 對信號量操作對信號量操作 int semop(int semid, struct sembuf semoparray, size_t nops); int semctl(int sem_id, int semnum, int cmd,/*union semun arg*/); NO：19 第四章第四章 操作系統(tǒng)操作系統(tǒng)4.2 4.2 處理器管理處理器管理 共享內(nèi)存：共享內(nèi)存：多個進(jìn)程共享一塊內(nèi)存，達(dá)到交換信息的目的。多個進(jìn)程共享一塊內(nèi)存，達(dá)到交換信息的目的。由于沒有中間介質(zhì)，如消息隊列、管道等延遲，數(shù)據(jù)直接由由于沒有中間介質(zhì)，如消息隊列、管道等延遲，數(shù)據(jù)直接由內(nèi)存映射到進(jìn)

24、程空間。是目前內(nèi)存映射到進(jìn)程空間。是目前速度最快速度最快的一種進(jìn)程通信機(jī)制。的一種進(jìn)程通信機(jī)制。 使用是需要一定的同步機(jī)制來控制多個進(jìn)程對同一塊內(nèi)存使用是需要一定的同步機(jī)制來控制多個進(jìn)程對同一塊內(nèi)存的讀寫。常常和信號量控制結(jié)合在一起使用。的讀寫。常常和信號量控制結(jié)合在一起使用。NO：20 第四章第四章 操作系統(tǒng)操作系統(tǒng)4.2 4.2 處理器管理處理器管理3 死鎖死鎖 兩個或兩個以上的進(jìn)程中的每一個都在等待其中另一個進(jìn)兩個或兩個以上的進(jìn)程中的每一個都在等待其中另一個進(jìn)程釋放資源而被封鎖，它們都無法向前推進(jìn)，這種現(xiàn)象稱為程釋放資源而被封鎖，它們都無法向前推進(jìn)，這種現(xiàn)象稱為死鎖死鎖。 死鎖問題是一種

25、具有普遍性的現(xiàn)象，日常生活中屢見不鮮。死鎖問題是一種具有普遍性的現(xiàn)象，日常生活中屢見不鮮。例如例如北北北北南南西西車隊死鎖問題車隊死鎖問題NO：21 第四章第四章 操作系統(tǒng)操作系統(tǒng)4.2 4.2 處理器管理處理器管理在計算機(jī)系統(tǒng)中，這種現(xiàn)象比較多。進(jìn)程產(chǎn)生死鎖是因在計算機(jī)系統(tǒng)中，這種現(xiàn)象比較多。進(jìn)程產(chǎn)生死鎖是因競爭資競爭資源源而引起的，與而引起的，與執(zhí)行順序執(zhí)行順序有關(guān)。如將車隊視為進(jìn)程，馬路視為有關(guān)。如將車隊視為進(jìn)程，馬路視為資源，在計算機(jī)系統(tǒng)中有各種資源，如外設(shè)、數(shù)據(jù)、文件等資源，在計算機(jī)系統(tǒng)中有各種資源，如外設(shè)、數(shù)據(jù)、文件等例如系統(tǒng)有兩個進(jìn)程例如系統(tǒng)有兩個進(jìn)程P1 和和P2，以及一個打印

26、機(jī)（，以及一個打印機(jī)（R1）和輸入）和輸入機(jī)（機(jī)（R2）。在運行程中，）。在運行程中， P1 占用了占用了 R1和和P2占用占用了了 R2，此時，此時P1又又申請申請輸入機(jī)而輸入機(jī)而P2又又申請申請打印機(jī)，那么這時打印機(jī)，那么這時P1 和和P2均無法均無法運行，系統(tǒng)進(jìn)入死鎖狀態(tài)。用下圖所示。運行，系統(tǒng)進(jìn)入死鎖狀態(tài)。用下圖所示。進(jìn)程循環(huán)鏈進(jìn)程循環(huán)鏈P1P2R1R2由由進(jìn)程進(jìn)程指向指向資源資源的箭頭的箭頭表示對資源的表示對資源的申請申請，而，而由由資源資源指向指向進(jìn)程進(jìn)程的箭頭的箭頭表示資源的表示資源的分配分配NO：22 第四章第四章 操作系統(tǒng)操作系統(tǒng)4.2 4.2 處理器管理處理器管理 死鎖的原

27、因和必要條件死鎖的原因和必要條件 產(chǎn)生死鎖的原因為產(chǎn)生死鎖的原因為 系統(tǒng)資源不足系統(tǒng)資源不足 進(jìn)程推進(jìn)的順序不當(dāng)進(jìn)程推進(jìn)的順序不當(dāng) 產(chǎn)生死鎖的產(chǎn)生死鎖的必要必要條件為條件為 互斥條件互斥條件：存在互斥使用的資源存在互斥使用的資源 占有等待條件占有等待條件：進(jìn)程在等待新資源時，繼續(xù)占用已分進(jìn)程在等待新資源時，繼續(xù)占用已分配到的資源配到的資源一次只能給一一次只能給一個進(jìn)程使用的個進(jìn)程使用的資源資源NO：23 第四章第四章 操作系統(tǒng)操作系統(tǒng)4.2 4.2 處理器管理處理器管理 非剝奪條件非剝奪條件：一個進(jìn)程占有的資源不能被別的進(jìn)程強一個進(jìn)程占有的資源不能被別的進(jìn)程強行搶占。行搶占。 循環(huán)等待條件循環(huán)

28、等待條件：一個進(jìn)程獲得的資源同時被另一個進(jìn)一個進(jìn)程獲得的資源同時被另一個進(jìn)程所請求，從而形成一個進(jìn)程的循環(huán)鏈。程所請求，從而形成一個進(jìn)程的循環(huán)鏈。 隨著系統(tǒng)的不斷增大和復(fù)雜化，產(chǎn)生死鎖的可能性也隨隨著系統(tǒng)的不斷增大和復(fù)雜化，產(chǎn)生死鎖的可能性也隨著增加，著增加，解決死鎖的方法解決死鎖的方法大致有以下三類：大致有以下三類： 死鎖的預(yù)防死鎖的預(yù)防 死鎖的避免死鎖的避免 死鎖的檢測和恢復(fù)死鎖的檢測和恢復(fù)NO：24 第四章第四章 操作系統(tǒng)操作系統(tǒng)4.2 4.2 處理器管理處理器管理 死鎖的預(yù)防死鎖的預(yù)防:在系統(tǒng)設(shè)計時就確定資源分配的算法，在系統(tǒng)設(shè)計時就確定資源分配的算法，使得系統(tǒng)在運行時不會發(fā)生死鎖，這

29、是一種使得系統(tǒng)在運行時不會發(fā)生死鎖，這是一種靜態(tài)措施靜態(tài)措施。 死鎖的避免死鎖的避免:一種判定和發(fā)現(xiàn)死鎖的方法，即每當(dāng)申一種判定和發(fā)現(xiàn)死鎖的方法，即每當(dāng)申請一個資源時，都要依據(jù)一定的算法判斷是否許可這次申請一個資源時，都要依據(jù)一定的算法判斷是否許可這次申請，如有死鎖發(fā)生的可能就不許可。這是一種請，如有死鎖發(fā)生的可能就不許可。這是一種動態(tài)措施動態(tài)措施。 死鎖的檢測和恢復(fù)死鎖的檢測和恢復(fù):既不預(yù)防死鎖的發(fā)生，也不在系既不預(yù)防死鎖的發(fā)生，也不在系統(tǒng)運行時避免，而是允許死鎖的發(fā)生，只是在死鎖發(fā)生后統(tǒng)運行時避免，而是允許死鎖的發(fā)生，只是在死鎖發(fā)生后消除死鎖。是消除死鎖。是善后措施善后措施。NO：25 第

30、四章第四章 操作系統(tǒng)操作系統(tǒng)4.2 4.2 處理器管理處理器管理 死鎖的預(yù)防死鎖的預(yù)防 由產(chǎn)生死鎖的必要條件可知：由產(chǎn)生死鎖的必要條件可知： D C1C2C3C4 則有則有: C1 C2 C3 C4 D 因此只要保證系統(tǒng)中有一個必要條件不成立，就能保證系因此只要保證系統(tǒng)中有一個必要條件不成立，就能保證系統(tǒng)中不會出現(xiàn)死鎖。統(tǒng)中不會出現(xiàn)死鎖。 破壞互斥條件破壞互斥條件 較難實現(xiàn)，因為有些系統(tǒng)資源的性質(zhì)是較難實現(xiàn)，因為有些系統(tǒng)資源的性質(zhì)是非共享的，但可以采用非共享的，但可以采用假脫機(jī)假脫機(jī)技術(shù)將非共享設(shè)備變成共享設(shè)技術(shù)將非共享設(shè)備變成共享設(shè)備來實現(xiàn)。備來實現(xiàn)。NO：26 第四章第四章 操作系統(tǒng)操作系

31、統(tǒng)4.2 4.2 處理器管理處理器管理 破壞占有等待條件破壞占有等待條件 常用的方法是預(yù)先靜態(tài)分配法，規(guī)定常用的方法是預(yù)先靜態(tài)分配法，規(guī)定各進(jìn)程所需的全部資源只能事先各進(jìn)程所需的全部資源只能事先一次一次申請，并在沒有獲得全申請，并在沒有獲得全部資源之前，不能運行。實現(xiàn)較容易，但分配到的資源可能部資源之前，不能運行。實現(xiàn)較容易，但分配到的資源可能使用時間很短，而被某個進(jìn)程長時間占用，資源利用率低。使用時間很短，而被某個進(jìn)程長時間占用，資源利用率低。 破壞非剝奪條件破壞非剝奪條件 根據(jù)申請資源的優(yōu)先級別高低來剝奪根據(jù)申請資源的優(yōu)先級別高低來剝奪占用的資源。該方法目前主要用在處理機(jī)和存儲資源調(diào)度上，

32、占用的資源。該方法目前主要用在處理機(jī)和存儲資源調(diào)度上，而對某些設(shè)備就不合適，如對打印機(jī)的剝奪就會使各個用戶而對某些設(shè)備就不合適，如對打印機(jī)的剝奪就會使各個用戶輸出的信息混雜在一起。輸出的信息混雜在一起。 NO：27 第四章第四章 操作系統(tǒng)操作系統(tǒng)4.2 4.2 處理器管理處理器管理這樣，進(jìn)程與資源請求不會產(chǎn)生循環(huán)等待問題，即不會出現(xiàn)環(huán)這樣，進(jìn)程與資源請求不會產(chǎn)生循環(huán)等待問題，即不會出現(xiàn)環(huán)路。該方法提高了資源利用率，但進(jìn)程實際需要資源的順序不路。該方法提高了資源利用率，但進(jìn)程實際需要資源的順序不一定與資源的編號一致，因此仍會造成資源浪費。一定與資源的編號一致，因此仍會造成資源浪費。破壞循環(huán)等待條

33、件破壞循環(huán)等待條件 常采用有序資源使用方法，即資源按類常采用有序資源使用方法，即資源按類型賦予一個型賦予一個唯一唯一的代號。如令輸入機(jī)的代號。如令輸入機(jī)=1,打印機(jī)打印機(jī)=2,穿孔機(jī)穿孔機(jī)=3, 磁盤磁盤=4等，所有進(jìn)程對資源的請求必須嚴(yán)格按照等，所有進(jìn)程對資源的請求必須嚴(yán)格按照序號遞增次序號遞增次序序進(jìn)行，并且要求在前一要求得到滿足的前提下，才能進(jìn)一進(jìn)行，并且要求在前一要求得到滿足的前提下，才能進(jìn)一步請求。步請求。例如：進(jìn)程例如：進(jìn)程PA，使用資源的順序是，使用資源的順序是R1，R2； 進(jìn)程進(jìn)程PB，使用資源的順序是，使用資源的順序是R2，R1；若采用動態(tài)分配有可能形成若采用動態(tài)分配有可能形

34、成環(huán)路條件環(huán)路條件，造成死鎖。，造成死鎖。采用有序資源分配法：采用有序資源分配法：R1的編號為的編號為1，R2的編號為的編號為2； PA：申請次序應(yīng)是：申請次序應(yīng)是：R1，R2 PB：申請次序應(yīng)是：申請次序應(yīng)是：R1，R2 這樣就破壞了環(huán)路條件，避免了死鎖的發(fā)生。這樣就破壞了環(huán)路條件，避免了死鎖的發(fā)生。NO：28 第四章第四章 操作系統(tǒng)操作系統(tǒng)4.2 4.2 處理器管理處理器管理 死鎖的避免死鎖的避免 在避免死鎖的方法中，允許進(jìn)程動態(tài)地申請在避免死鎖的方法中，允許進(jìn)程動態(tài)地申請資源，但系統(tǒng)在進(jìn)行資源分配之前，應(yīng)先計算此次資源分配資源，但系統(tǒng)在進(jìn)行資源分配之前，應(yīng)先計算此次資源分配的安全性。若此

35、次分配不會導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)，則將的安全性。若此次分配不會導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)，則將資源分配給進(jìn)程；資源分配給進(jìn)程； 否則，令進(jìn)程等待。下面介紹一種死鎖避否則，令進(jìn)程等待。下面介紹一種死鎖避免的算法免的算法 - 銀行家算法銀行家算法 安全狀態(tài)和不安全狀態(tài)安全狀態(tài)和不安全狀態(tài) 安全狀態(tài)：安全狀態(tài)：所謂安全狀態(tài)是指系統(tǒng)能夠按照某種所謂安全狀態(tài)是指系統(tǒng)能夠按照某種進(jìn)程進(jìn)程順序順序，如，如(稱其為稱其為安全序列安全序列),分別為這分別為這n個進(jìn)程個進(jìn)程分配所需資源，直至最大需求，使每個進(jìn)程都能順利完成。分配所需資源，直至最大需求，使每個進(jìn)程都能順利完成。若系統(tǒng)不存在這樣一個安全序列，則稱系統(tǒng)處于

36、若系統(tǒng)不存在這樣一個安全序列，則稱系統(tǒng)處于不安全狀態(tài)不安全狀態(tài) 系統(tǒng)處于安全狀態(tài)，且按照安全序列分配資源，可以保系統(tǒng)處于安全狀態(tài)，且按照安全序列分配資源，可以保證系統(tǒng)不會出現(xiàn)死鎖。因此，避免死鎖的實質(zhì)在于證系統(tǒng)不會出現(xiàn)死鎖。因此，避免死鎖的實質(zhì)在于避免系統(tǒng)避免系統(tǒng)進(jìn)入不安全狀態(tài)。進(jìn)入不安全狀態(tài)。NO：29 第四章第四章 操作系統(tǒng)操作系統(tǒng)4.2 4.2 處理器管理處理器管理下面通過一個例子說明安全性。假定系統(tǒng)有下面通過一個例子說明安全性。假定系統(tǒng)有3 3個進(jìn)程個進(jìn)程P1P1, ,P2P2, ,P3P3共有共有1414臺打印機(jī)臺打印機(jī)。進(jìn)程。進(jìn)程P1P1共要求共要求1212臺打印機(jī)臺打印機(jī)，P2P

37、2和和P3P3分別要分別要求求4 4臺臺和和9 9臺臺打印機(jī)。假定打印機(jī)。假定T0T0時刻時刻, ,進(jìn)程進(jìn)程P1,P2P1,P2和和P3P3分別獲得分別獲得5 5臺臺,2,2臺和臺和4 4臺臺, ,尚有尚有3 3臺空閑臺空閑未分配，如下表未分配，如下表進(jìn)程進(jìn)程最大需求最大需求已分配已分配還需要還需要可用可用P112573P2422P3945經(jīng)分析發(fā)現(xiàn)，在經(jīng)分析發(fā)現(xiàn)，在T0T0時刻是安全的。因為，存在一個安全序時刻是安全的。因為，存在一個安全序列列,系統(tǒng)按此序列分配資源，每個進(jìn)程可以順利系統(tǒng)按此序列分配資源，每個進(jìn)程可以順利完成。完成。NO：30 第四章第四章 操作系統(tǒng)操作系統(tǒng)4.2 4.2 處

38、理器管理處理器管理進(jìn)程進(jìn)程最大需求最大需求已分配已分配還需要還需要可用可用P1P112126 66 62P2P24 42 22 2P3P39 94 45 5 由安全狀態(tài)向不安全狀態(tài)轉(zhuǎn)換由安全狀態(tài)向不安全狀態(tài)轉(zhuǎn)換假設(shè)在假設(shè)在T0T0時刻時刻P1P1要求要求6 6臺臺打印機(jī)，則系統(tǒng)進(jìn)入不安全狀態(tài)。因打印機(jī)，則系統(tǒng)進(jìn)入不安全狀態(tài)。因為如果把剩余的為如果把剩余的2 2臺臺分配給分配給P2P2，當(dāng)，當(dāng)P2P2完成后，僅能釋放出完成后，僅能釋放出4 4臺臺，既不能滿足既不能滿足P1P1的要求，也不能滿足跡的要求，也不能滿足跡P3P3的要求。這樣的要求。這樣P1P1和和P3P3都無法執(zhí)行都無法執(zhí)行完成，彼此

39、都阻塞等待對方釋放資源，結(jié)果將完成，彼此都阻塞等待對方釋放資源，結(jié)果將導(dǎo)導(dǎo)致死鎖致死鎖。NO：31 第四章第四章 操作系統(tǒng)操作系統(tǒng)4.2 4.2 處理器管理處理器管理銀行家算法銀行家算法 銀行家算法把銀行家算法把操作系統(tǒng)操作系統(tǒng)比作是一個比作是一個銀行家銀行家，它占有有限的，它占有有限的資源，而要求資源的資源，而要求資源的進(jìn)程進(jìn)程好比要貸款的好比要貸款的顧客顧客。算法規(guī)定：。算法規(guī)定： 1. 每個用戶必須預(yù)先申請它所需的每個用戶必須預(yù)先申請它所需的貸款總數(shù)貸款總數(shù)，且數(shù)值不，且數(shù)值不能超過銀行資金總數(shù)。能超過銀行資金總數(shù)。 2. 每個用戶每次只能向銀行申請每個用戶每次只能向銀行申請一個單位一個

40、單位貸款數(shù)。貸款數(shù)。 3. 銀行根據(jù)當(dāng)時的資金情況，銀行根據(jù)當(dāng)時的資金情況，可能立即滿足可能立即滿足用戶申請，用戶申請，或需要用戶或需要用戶等待一段等待一段有限時間。有限時間。 4. 當(dāng)用戶貸款總數(shù)達(dá)到申請數(shù)后，必須在有限時間內(nèi)當(dāng)用戶貸款總數(shù)達(dá)到申請數(shù)后，必須在有限時間內(nèi)一次性歸還一次性歸還所有貸款。所有貸款。NO：32 第四章第四章 操作系統(tǒng)操作系統(tǒng)4.2 4.2 處理器管理處理器管理態(tài)態(tài)狀狀行行銀銀甲甲乙乙丙丙例如某銀行資金總數(shù)為例如某銀行資金總數(shù)為10萬元萬元，用戶甲、乙、丙申請貸款，用戶甲、乙、丙申請貸款總數(shù)分別為總數(shù)分別為8萬元萬元、3萬元萬元、9萬元萬元。用戶每次向銀行申請。用戶每

41、次向銀行申請貸款數(shù)為貸款數(shù)為1萬元。萬元。 A為初始狀態(tài)，銀行庫存為初始狀態(tài)，銀行庫存10萬元，甲乙丙申請貸款萬元，甲乙丙申請貸款分別為分別為萬元。萬元。 當(dāng)借貸進(jìn)行到狀態(tài)當(dāng)借貸進(jìn)行到狀態(tài)B時，甲、乙、丙分別得到貸款時，甲、乙、丙分別得到貸款4，2，2萬元。括號中的數(shù)字為尚可申請的貸款數(shù)。萬元。括號中的數(shù)字為尚可申請的貸款數(shù)。NO：33 第四章第四章 操作系統(tǒng)操作系統(tǒng)4.2 4.2 處理器管理處理器管理 若甲乙丙繼續(xù)提出貸款申請，銀行要考慮庫存與各用戶若甲乙丙繼續(xù)提出貸款申請，銀行要考慮庫存與各用戶尚可申請的貸款數(shù)，為使借貸安全，只同意繼續(xù)提供用尚可申請的貸款數(shù)，為使借貸安全，只同意繼續(xù)提供用

42、戶戶乙乙的貸款，而的貸款，而甲和丙甲和丙暫時暫時等待等待，待用戶，待用戶乙乙獲得全部貸獲得全部貸款并在有限時間內(nèi)款并在有限時間內(nèi)全部歸還后全部歸還后再考慮貸款。如此進(jìn)行下再考慮貸款。如此進(jìn)行下去，各用戶均能獲得貸款，而銀行也可以如數(shù)收回資金，去，各用戶均能獲得貸款，而銀行也可以如數(shù)收回資金，其過程如下頁表所示：其過程如下頁表所示：態(tài)態(tài)狀狀行行銀銀甲甲乙乙丙丙NO：34 第四章第四章 操作系統(tǒng)操作系統(tǒng)4.2 4.2 處理器管理處理器管理狀態(tài)狀態(tài)銀行銀行甲甲乙乙丙丙NO：35 第四章第四章 操作系統(tǒng)操作系統(tǒng)4.2 4.2 處理器管理處理器管理 非銀行算法可能引起的死鎖狀態(tài)非銀行算法可能引起的死鎖狀

43、態(tài)狀態(tài)狀態(tài)銀行銀行甲甲乙乙丙丙 如果銀行隨意給各申請用戶貸款，則可能出現(xiàn)銀行庫存滿如果銀行隨意給各申請用戶貸款，則可能出現(xiàn)銀行庫存滿足不了甲、乙、丙的申請余額，使它們永不歸還貸款，從而足不了甲、乙、丙的申請余額，使它們永不歸還貸款，從而使銀行無法收回資金，系統(tǒng)處于使銀行無法收回資金，系統(tǒng)處于死鎖狀態(tài)死鎖狀態(tài)，如下表所示。，如下表所示。NO：36 第四章第四章 操作系統(tǒng)操作系統(tǒng)4.2 4.2 處理器管理處理器管理Habermann算法算法：用戶對多類資源提出的請求用戶對多類資源提出的請求根據(jù)系統(tǒng)中進(jìn)程數(shù)和所需資源寫出進(jìn)程請求矩陣根據(jù)系統(tǒng)中進(jìn)程數(shù)和所需資源寫出進(jìn)程請求矩陣B 例如：某系統(tǒng)由例如：某

44、系統(tǒng)由4個個進(jìn)程進(jìn)程P1,P2,P3和和P4組成，其相應(yīng)的請求組成，其相應(yīng)的請求矩陣為：矩陣為：bij表示第表示第i個進(jìn)程對第個進(jìn)程對第j類資源的需求情況，如果類資源的需求情況，如果 bij=0 則說則說明進(jìn)程明進(jìn)程 Pi 對資源對資源 Rj 沒有要求沒有要求NO：37 第四章第四章 操作系統(tǒng)操作系統(tǒng)4.2 4.2 處理器管理處理器管理死鎖的檢測是采用進(jìn)程有向圖死鎖的檢測是采用進(jìn)程有向圖 , E，其中其中 = P1,P2,Pn, eE，有向邊，有向邊eik=Pi,Pk 表示進(jìn)程表示進(jìn)程Pi申請的資申請的資源源Rj也可能為進(jìn)程也可能為進(jìn)程Pk所申請。每當(dāng)有向圖出現(xiàn)環(huán)路時，認(rèn)為所申請。每當(dāng)有向圖出

45、現(xiàn)環(huán)路時，認(rèn)為該進(jìn)程的資源請求將導(dǎo)致死鎖，系統(tǒng)拒絕分配。該進(jìn)程的資源請求將導(dǎo)致死鎖，系統(tǒng)拒絕分配。 開始開始P1P2P3P4 P1請求請求R1P1P2P3P4NO：38 第四章第四章 操作系統(tǒng)操作系統(tǒng)4.2 4.2 處理器管理處理器管理 P2請求請求R3P1P2P3P4 P2請求請求R2P1P2P3P4P1,P2形成環(huán)路，拒形成環(huán)路，拒絕分配，絕分配，P2阻塞阻塞 P3請求請求R2P1P2P3P4P1,P2,P3形成環(huán)路，形成環(huán)路，拒絕分配，拒絕分配，P3阻塞阻塞 P4請求請求R4P1P2P3P4 P1請求請求R2P1P2P3P4 P1運行完畢運行完畢P2P3P4釋放釋放R1,R2，喚醒，喚醒

46、P2，把把R2分配給分配給P2NO：39 第四章第四章 操作系統(tǒng)操作系統(tǒng)4.2 4.2 處理器管理處理器管理(3) 死鎖的檢測與恢復(fù)死鎖的檢測與恢復(fù)如果系統(tǒng)不愿意附加太多的約束來預(yù)防死鎖，也不希望系統(tǒng)額如果系統(tǒng)不愿意附加太多的約束來預(yù)防死鎖，也不希望系統(tǒng)額外開銷預(yù)測并避免死鎖，那么只能外開銷預(yù)測并避免死鎖，那么只能允許允許死鎖的發(fā)生，但能在適死鎖的發(fā)生，但能在適當(dāng)時間當(dāng)時間檢測出來檢測出來，并設(shè)法進(jìn)行，并設(shè)法進(jìn)行恢復(fù)恢復(fù)。死鎖檢測算法通常針是檢。死鎖檢測算法通常針是檢測否存在進(jìn)程的循環(huán)鏈。測否存在進(jìn)程的循環(huán)鏈。資源分配圖資源分配圖P1P2r1r2凡屬于凡屬于E中的一個邊中的一個邊eE，都連接，

47、都連接著著P中的一個結(jié)點中的一個結(jié)點和和R中的一個結(jié)中的一個結(jié)點點，e=pi, rj是是資源請求邊資源請求邊，由進(jìn)，由進(jìn)程程pi指向資源指向資源rj，它表示進(jìn)程，它表示進(jìn)程pi請請求一個單位的求一個單位的rj資源。資源。e=rj, pi是是資源分配邊資源分配邊，由，由資源資源rj指向進(jìn)程指向進(jìn)程pi, 它表示把一個單位的資源它表示把一個單位的資源rj分配給分配給進(jìn)程進(jìn)程pi。NO：40 第四章第四章 操作系統(tǒng)操作系統(tǒng)4.2 4.2 處理器管理處理器管理查找圖中非孤立進(jìn)程結(jié)點查找圖中非孤立進(jìn)程結(jié)點Pi，其全部請求能夠滿足，說明它能，其全部請求能夠滿足，說明它能得到需要的所有資源，順利向前推進(jìn)，直至最后完成，并釋放得到需要的所有資源，順利向前推進(jìn)，直至最后完成，并釋放所有占用的資源。這樣可以所有占用的資源。這樣可以去掉去掉Pi的的請求邊請求邊和和分配邊分配邊，使