计数抽样检验程序aql抽样计划正常

著作權所有 旗標出版股份有限公司,1,第3章 行程間通訊與同步,著作權所有 旗標出版股份有限公司,2,合作行程,會與其他行程共享資訊，或是影響其他行程所執行之指令的行程行程間通訊：合作行程之間必定需要某些溝通的機制，以傳遞所需的指令或資料 同步：行程合作過程中所牽涉到的協調問題與處理機制,著作權所有 旗標出版股份有限公司,3,3-1 行程間通訊 （IPC）,共用的檔案：行程間最常見的資訊共享方式，傳遞的資訊量僅受限於檔案系統的最大長度共享記憶體：由作業系統提供某種機制，讓不同行程可以同時存取到某塊記憶體比共用檔案的傳遞速度快，但長度比較受到限制 執行緒本身就內含了共享記憶體的概念 信號：當行程A想要告知行程B某事發生或完成時，可以傳送特定的信號給行程B可以用來進行事件的告知，但是如果需要傳送特定資訊時，還需要搭配其他的行程間通訊機制,著作權所有 旗標出版股份有限公司,4,Unix的信號種類與處理常式設定,行程可以使用kill系統呼叫來傳送信號給其他行程int kill (int pid, int sig);行程收到信號的處理方式 捕捉信號：提供信號處理函式忽略信號 使用預設的處理方式 （見下表）使用signal系統呼叫來設定所需的處理方式 int (*signal (int sig, void (*func) (int) (int);,著作權所有 旗標出版股份有限公司,5,Unix中一些常見的信號定義,著作權所有 旗標出版股份有限公司,6,Unix的kill系統呼叫,kill的語法：int kill (int pid, int sig);pid：指定要將信號傳送給哪個行程，0表示要將信號傳送給屬於傳送行程擁有者的所有行程 sig：指定要傳送的信號種類Kill的範例：送出信號終止父行程：Kill (getppid(), SIGTERM);送出使用者自定信號給特定行程（pid=sv_pid）：Kill ( sv_pid, SIGUSR1);,著作權所有 旗標出版股份有限公司,7,Kill系統呼叫 vs. Kill命令,Unix也提供kill命令，讓使用者可以在shell之下送出信號給特定行程Kill命令會去執行kill系統呼叫，來完成信號傳遞的工作Ex. 假設使用者要終止自己的a.out（pid=21160)行程，可以在shell的提示字串下輸入：kill -9 21160相當於送出SIGKILL的信號給a.out，強迫它結束也可以使用特定的終端機字元來產生信號，例如：Ctrl-C會送出SIGINT來終止正在執行的行程Ctrl-會送出SIGQUIT，終止行程執行，並產生行程的core影像檔,著作權所有 旗標出版股份有限公司,8,訊息傳遞系統-直接溝通,溝通雙方必須要知道對方的身分，一個通訊鏈結只有2個行程參與，可單向 / 雙向系統通常會提供2個函式send_process(pid, message)receive_process(pid, message),著作權所有 旗標出版股份有限公司,9,訊息傳遞系統-間接溝通,通訊鏈結可以由數個行程共享 涉及許多權限管理的問題 系統通常會提供4個函式 create_mailbox(mbx)delete_mailbox(mbx)send_mailbox(mbx, message)receive_mailbox(mbx, message),著作權所有 旗標出版股份有限公司,10,阻隔式傳送 vs. 非阻隔式接收,不論是直接或間接形式的溝通，都會面臨收送雙方不同步的情況。 阻隔式傳送/阻隔式接收：讓等待的一方進入懸置狀態，直到資訊被接收後再繼續非阻隔式通訊：非阻隔式傳送：傳送端行程送出訊息之後，不必等訊息被接收，就可以繼續執行後面的動作非阻隔式接收：接收端行程在嘗試讀取訊息之後，不論是否有收到訊息，都可以繼續執行後續的動作當傳送端與接收端都是使用阻隔式通訊時，兩者之間就會同步,著作權所有 旗標出版股份有限公司,11,Windows 2000/XP的IPC,信號：行程與外界的一種低階通訊方式 共享記憶體：可以使用在行程間的大量資料通訊，需要同步機制來確保資料的完整性 Pipe：在行程間使用位元組串流形式的通訊鏈結 郵件槽：類似信箱的非阻隔式通訊機制，使用可變長度的訊息，是主從式架構的單向鏈結socket：以TCP/IP協定為基礎的網路通訊機制,著作權所有 旗標出版股份有限公司,12,行程間通訊的設計考量,通訊鏈結的類型：直接或間接 共享通訊鏈結的行程數目通訊鏈結的方向性：單向或雙向訊息長度：固定長度或可變長度 傳送的是訊息複本或是訊息的參照位址單方行程片面終止時要如何處理,著作權所有 旗標出版股份有限公司,13,討論題,當傳送端的速度遠快於接收端時，會發生什麼問題？要如何改善？,著作權所有 旗標出版股份有限公司,14,圖3-1 通訊鏈結的緩衝,(a) 無緩衝區的資料傳遞,(b) 有緩衝區的資料傳遞,當傳送端的速度遠快於接收端時，傳送端就會經常處於等待的狀況可以利用緩衝區來改善,必須另外確認資料已被讀取,著作權所有 旗標出版股份有限公司,15,3-2 同步,合作行程之間可能在不同的時機點發生交互影響在單處理器系統：合作行程是根據排程的結果輪流在CPU中交錯執行，使得結果看起來好像是同時執行一樣在多處理器系統：合作行程不但可能交錯執行，甚至可能確實是同時執行同步機制：確保在多個合作行程同時執行的環境中，不同行程的運算不會相互干擾,著作權所有 旗標出版股份有限公司,16,合作行程間的可能問題,飢餓死結競賽狀況共享資料的不一致現象,著作權所有 旗標出版股份有限公司,17,臨界區,合作行程所執行的程式碼中，有些區段會涉及共用資源，不能讓其他行程也同時存取，因此稱為臨界區 臨界區的結構： Enter_section(); 入口區 臨界區 Exit_section(); 出口區入口區：通常會做些動作來取得進入臨界區的許可等待進入的行程可以採取忙碌等待的方式，或是進入懸置狀態，等待被喚醒 出口區：將當初所取得的許可權釋放，以便其他行程可以進入臨界區,著作權所有 旗標出版股份有限公司,18,臨界區的設計條件,互斥：如果某個行程正處於臨界區中，且該區段會存取一組共用資源R1、R2、Rn，則其他行程都不能進入會存取到R1、R2、Rn其中任何一項共享資源的臨界區中進行：如果目前沒有行程處於臨界區中，而且有行程在等待進入臨界區，則必須讓其中一個等待的行程能在有限的時間內進入臨界區中有限等待：行程從請求進入臨界區到獲准進入之間的時間必須是有限的，不能因為飢餓或死結而無法進入臨界區,著作權所有 旗標出版股份有限公司,19,3-3 臨界區的實作-方法1,題目：為兩個具有相同臨界區的行程P0、P1設計同步機制做法：設定共用變數turn；當turn為0的時候，行程P0可以進入臨界區，當變數為1時，則輪到行程P1P0的虛擬程式碼如下： while (turn != 0); /* 入口區；等待輪到自己 */turn = 1; /* 出口區；將使用權設給別人 */ P1則是將0、1互換即可問題：只滿足互斥的要求， 但無法滿足進行的條件,著作權所有 旗標出版股份有限公司,20,臨界區的實作-方法2,修改為記錄每個行程目前的臨界區請求P0的虛擬程式碼：flag0 = true; /* 入口區 */while (flag1); flag0 = false; /* 出口區 */問題：如果有一個行程在入口區的執行過程中發生行程切換，則雙方都可能進入無窮迴圈,著作權所有 旗標出版股份有限公司,21,圖3-2 臨界區的實作問題,P0,flag0 = true;,P1,flag1 = true;while (flag0);,行程切換,進入迴圈,P0,while (flag1);,行程切換,進入迴圈,著作權所有 旗標出版股份有限公司,22,臨界區的實作-麵包店演算法,先發給請求臨界區的行程一個編號，當目前使用臨界區的行程離開之後，每個等待行程必須先比較所有等待行程所拿到的編號如果自己的號碼最早，就可以進入臨界區中如果有號碼早於自己者，則必須先進入迴圈等待 基本上是採取FCFS的規則，因此可以確保進行與有限等待的要求，並且可適用於多個行程的臨界區實作,著作權所有 旗標出版股份有限公司,23,麵包店演算法的虛擬程式碼,行程Pi的虛擬程式碼,flagi = true;numberi = max(number0, , numbern-1) + 1; /* 取得號碼牌 */flagi = false; for (j=0; jnumberi = 0; /* 出口區；歸還號碼牌 */,著作權所有 旗標出版股份有限公司,24,課堂練習,將麵包店演算法套用在兩個行程P0 、 P1的情境下，並寫出P0的虛擬程式碼,著作權所有 旗標出版股份有限公司,25,練習解答,flag0 = true;number0 = max(number0, number1) + 1; flag0 = false; while (flag1); while (number1 !=0 ,著作權所有 旗標出版股份有限公司,26,圖3-3 麵包店演算法的實作範例,P0,flag0 = true;number0 = 1;flag0 = false;,P1,flag1 = true;number1 = 2flag1 = false;while (flag0);while (number0!=0 ,行程切換,離開迴圈,P0,while (flag1);while (number1!=0 ,行程切換,離開迴圈,取得號碼牌,取得號碼牌,等號碼小的先執行,離開迴圈,進入臨界區,著作權所有 旗標出版股份有限公司,27,硬體支援的同步機制,完全利用軟體來實作同步機制，不僅費時，而且很難驗證它的正確性 硬體支援的同步機制：抑制中斷 TestAndSet swap 號誌,著作權所有 旗標出版股份有限公司,28,抑制中斷,如果是在單處理器的系統中，行程一旦取得CPU的控制權之後，如果能夠先抑制作業系統的中斷 ，就可以一直執行下去，而避免在臨界區的中途被中斷 它的虛擬程式碼：,Disable_Interrupt(); /* 入口區；抑制中斷的系統原式（primitive） */ /* 臨界區 */Enable_Interrupt(); /* 出口區；開啟中斷的系統原式 */,著作權所有 旗標出版股份有限公司,29,抑制中斷法的缺點,不適用於多處理器的環境影響中斷的處理影響排程可能造成其他等待進入臨界區行程的飢餓問題,著作權所有 旗標出版股份有限公司,30,TestAndSet指令,提供特殊的硬體指令TestAndSet，並保證該指令在執行過程中不會被中斷-不可分割性TestAndSet指令的運作：boolean TestAndSet (Boolean locked) if (locked) return true;else locked = true;return false;,著作權所有 旗標出版股份有限公司,31,測試臨界區的實作 - TestAndSet,使用具有不可分割性的TestAndSet指令來設計臨界區：while (TestAndSet(lock); /* 入口區 */ lock = false; /* 出口區*/保證互斥與進行，但是不保證符合有限等待,著作權所有 旗標出版股份有限公司,32,TestAndSet-改良版,waitingpid = true;wait_lock = true;while (waitingpid ,記錄正等待進入臨界區的行程,臨界區的門鎖,著作權所有 旗標出版股份有限公司,33,課堂練習,請驗證改良版的TestAndSet符合臨界區的三個條件,著作權所有 旗標出版股份有限公司,34,練習解答,互斥：因為TestAndSet是原子式運算，所以只要有一個行程取得lock，其他行程執行TestAndSet的結果就會為true，而一直停留在while迴圈中進行：當臨界區的行程出來的時候，如果有行程在等待，它會根據行程代碼的順序，藉由設定waitingnext_pid = false，選擇在它之後的下一個等待行程有限等待：因為是依照行程代碼順序，所以每個等待的行程最多只要等候N-1個行程執行完畢，就會輪到自己,著作權所有 旗標出版股份有限公司,35,swap,Swap：原子式運作的硬體指令，可以交換兩個字組的內容Swap指令的運作：,void swap(boolean a, boolean b)boolean temp;temp = b;b = a;a = temp;,著作權所有 旗標出版股份有限公司,36,臨界區的實作 - swap,將共用變數lock初值設為 false,key = true;while (key)swap (lock, key);lock = false;,同樣無法提供有限等待的保證,著作權所有 旗標出版股份有限公司,37,號誌,用佇列來實作阻隔式等待，以避免忙碌等待 號誌是一個整數值，並且有兩個對應的原子式運算：wait與signal 號誌的值：大於0：表示行程可以進入臨界區等於0：表示臨界區的容量已滿，不能夠再進入，但目前沒有人在等待；小於0：表示已經有行程在佇列中等待,struct semaphore int count;ProcessQueue queue; ,著作權所有 旗標出版股份有限公司,38,號誌的運算,Wait：void wait(semaphore s) s.count-; if (s.count 0) insert process to s.queue; block(); Signal：void signal(semaphore s) s.count+; if (s.count = 0) remove process P from s.queue; wakeup(P); ,著作權所有 旗標出版股份有限公司,39,臨界區的實作 號誌,將號誌mutex的初值設定為1,wait(mutex); signal(mutex);,如果等待佇列是採取先進先出的方式，就可以保證符合有限等待的條件；否則就有可能發生飢餓的問題 假設將mutex的初值設為n，表示同時最多可允許n個行程進入臨界區 注意：號誌提供簡潔的臨界區同步機制，但是並不能保證程式一定會互斥，也無法完全避免死結,著作權所有 旗標出版股份有限公司,40,計數號誌與二元號誌,計數號誌：能夠設定為任意正值的號誌，又稱為通用號誌 二元號誌：限定為只能是0與1的號誌二元號誌可以利用硬體對二元數值的運算來實作二元號誌也可以用來實作計數號誌,著作權所有 旗標出版股份有限公司,41,利用二元號誌來實作計數號誌,整數C代表計數號誌的值二元號誌S1提供C的存取控制（初值為1）二元號誌S2模擬計數號誌的等待效果（初值為0）,void wait (S) wait (S1);C-;if (C 0) signal (S1);wait (S2);signal (S1);,void signal (S) wait (S1);C+;if (C = 0)signal (S2);elsesignal (S1);,著作權所有 旗標出版股份有限公司,42,Linux的旋轉鎖,旋轉鎖是Linux最基本的同步機制之一 被擋在門外的人必須一直去檢查門鎖是否已經打開 在單處理器系統中，這種做法會造成忙碌等待因此，在Linux核心中，旋轉鎖的實作spin_lock()與spin_unlock()都分成單處理器與多處理器兩個版本 單處理器版本的spin_lock()實作就是利用preempt_disable()讓在核心模式下執行的行程是不可搶先的，以確保旋轉鎖的執行期間不會發生內文切換 然後在 spin_unlock()中使用preempt_enable回復可搶先式排程 比較適合使用在處理時間很短的情境,著作權所有 旗標出版股份有限公司,43,3-4 同步問題的經典範例,有限緩衝區問題 讀取者與寫入者問題 哲學家的晚餐問題,著作權所有 旗標出版股份有限公司,44,有限緩衝區問題,假設在一個空間有限的緩衝區中最多可以存放n項的資料，就好像是在倉庫中一共有n個棧板，可以用來存放n筆貨物，如圖3-4在這個倉庫中，有一個生產者行程負責將資料放入棧板，有另一個消費者行程負責將資料取出 目標：生產者在倉庫滿了的時候能夠先暫停生產消費者在倉庫空了的時候能夠等待生產者與消費者都能正確地存取資料而不會發生任何錯誤,著作權所有 旗標出版股份有限公司,45,圖3-4 有限緩衝區範例,0號棧板,1號棧板,2號棧板,3號棧板,4號棧板,n-1號棧板,n-2號棧板,out,in,count = 2,著作權所有 旗標出版股份有限公司,46,圖3-5 有限緩衝區的環狀佇列實作,buffer0,buffer1,buffern-1,out,in,bufferm,Full = m 1Empty = n m + 1,著作權所有 旗標出版股份有限公司,47,有限緩衝區實作 生產者（無臨界區控制）,while (1) 生產下筆資料next_pdata;while (counter = n); bufferin = next_pdata; in = (in + 1) % n; counter+; ,著作權所有 旗標出版股份有限公司,48,有限緩衝區實作 消費者 （無臨界區控制）,while (1) while (counter = 0); next_cdata = bufferout; out = (out + 1) % n; counter-; 使用取出的next_cdata;,著作權所有 旗標出版股份有限公司,49,有限緩衝區實作的問題,假設生產者正在產生一筆新資料，而消費者正在讀取一筆資料如果在這兩者都在更新counter的過程中發生行程切換，counter的值可能會發生錯誤可以利用臨界區來解決這個問題 通用號誌empty：代表空白欄位的總數，初值為n通用號誌full：代表已填入欄位的總數，初值為0二元號誌mutex：作為對緩衝區的存取控制,著作權所有 旗標出版股份有限公司,50,圖3-6行程執行順序與 counter的值,將counter讀入暫存器將暫存器的值加1將暫存器寫回counter,生產者(P)：,轉成機器碼,Counter+;,消費者(C)：,Counter;,將counter讀入暫存器將暫存器的值減1將暫存器寫回counter,a.低階指令對照,將counter讀入暫存器將暫存器的值加1將暫存器寫回counter將counter讀入暫存器將暫存器的值減1將暫存器寫回counter,暫存器1=3暫存器1=4counter=4暫存器2=4暫存器2=3counter=3,b.行程切換發生在更新完成之後,將counter讀入暫存器將counter讀入暫存器將暫存器的值減1將暫存器寫回counter將暫存器的值加1將暫存器寫回counter,暫存器1=3暫存器2=3暫存器2=2counter=2暫存器1=4counter=4,c.生產者讀入counter後發生行程切換,轉成機器碼,PPPCCC,PCCCPP,行程 執行指令 結果,行程 執行指令 結果,將counter讀入暫存器將暫存器的值減1將counter讀入暫存器將暫存器的值加1將暫存器寫回counter將暫存器寫回counter,暫存器2=3暫存器2=2暫存器1=3暫存器1=4counter=4counter=2,d.消費者尚未更新counter前發生行程切換,CCPPPC,行程 執行指令 結果,著作權所有 旗標出版股份有限公司,51,改寫後的生產者程式,while (1) 生產下筆資料next_pdata;wait (empty); wait(mutex); bufferin = next_pdata;in = (in + 1) % n;signal(mutex); signal(full); ,著作權所有 旗標出版股份有限公司,52,改寫後的消費者程式,while (1) wait(full); wait(mutex); next_cdata = bufferout;out = (out + 1) % n;signal(mutex); signal(empty); 使用取出的next_cdata;,著作權所有 旗標出版股份有限公司,53,讀取者與寫入者問題,假設有數個行程共享同一份資料物件，其中有些行程只需要讀取資料，稱為讀取者，而有些行程只負責更新資料，稱為寫入者如果有兩個讀取者同時讀取資料，並不會造成任何問題但是如果在寫入者正在寫入資料時，有一個讀取者正在讀取資料，或是有另一個寫入者也在寫入資料，就可能造成資料不一致的問題目標：當一個寫入者更改資料時，其他行程都不可以讀取或寫入資料當任意數目的讀取者讀取資料時，任何寫入者都不可以寫入讀取者與讀取者之間沒有任何限制,著作權所有 旗標出版股份有限公司,54,讀取者與寫入者問題的臨界區實作,共用變數read_cnt：記錄目前正在讀取共用資料的讀取者數目，初值為0號誌mutex：用來控制read_count的存取，初值為1號誌wrt：用來控制寫入資料時的同步，初值為1寫入者的程式碼：,wait(wrt);寫入資料signal(wrt);,著作權所有 旗標出版股份有限公司,55,讀取者的程式碼,可以解決資料不一致的問題，但是卻可能造成飢餓問題,wait(mutex); read_cnt+if (read_cnt = 1) wait(wrt);signal(mutex); 讀取資料 wait(mutex); read_cnt-;if (read_cnt = 0) signal(wrt);signal(mutex);,著作權所有 旗標出版股份有限公司,56,圖3-7 挨餓的寫入者範例,讀取者1,寫入者2,Wrt佇列,等待,寫入者1,共用資料,寫入者2,Wrt佇列,等待,讀取者1,寫入者1離開,寫入者2,Wrt佇列,等待,讀取者1、2、3.,讀取者2、3、進入,飢餓中,著作權所有 旗標出版股份有限公司,57,以讀取者與寫入者為例，假設將程式中釋放wrt與釋放mutex的順序交換，就會發生錯誤：wait(mutex);read_cnt-;signal(mutex);if (read_cnt = 0) signal(wrt);,容易出錯的號誌程式設計,著作權所有 旗標出版股份有限公司,58,圖3-8號誌程式設計的錯誤範例,wait(mutex);read_cnt-;signal(mutex);,if (read_cnt = 0) signal(wrt);,wait(mutex); read_cnt+if (read_cnt = 1) wait(wrt);,wait(mutex);,讀取者1,讀取者2,讀取者3,讀取者1,不成立，沒有釋放wrt離開出口區,等待wrt，尚未釋放mutex,等待mutex,wait(mutex);,讀取者4,等待mutex,wait(mutex);,讀取者n,等待mutex,著作權所有 旗標出版股份有限公司,59,哲學家的晚餐問題,假設有5個哲學家圍坐在圓桌上共進晚餐，桌上只有5支筷子，每2個哲學家共用1支筷子哲學家們坐在餐桌上仍舊思考著哲學問題當哲學家覺得餓的時候，他會從左右各拿起一支筷子來進食 拿齊2支筷子的哲學家們可以同時進食，但是不能搶奪別人手中的筷子 吃飽之後，哲學家會將2支筷子都放下，繼續思考哲學問題，其他的哲學家則可以使用放下的筷子,著作權所有 旗標出版股份有限公司,60,圖3-9 哲學家的晚餐,著作權所有 旗標出版股份有限公司,61,用號誌實作哲學家的晚餐,分別用一個號誌（chopsticki）代表每支筷子，並且將它們的初值設為1 第i位哲學家的程式碼：,do wait(chopsticki);wait(chopstick (i + 1) % 5);進食;signal(chopsticki);signal(chopstick (i + 1) % 5);思考; while (1);,著作權所有 旗標出版股份有限公司,62,哲學家的死結問題,當每個哲學家都拿起右手的筷子，並且等待左手的筷子時，就會發生死結可能的解決方法：在桌上放置n+1支筷子，或是限制最多只有n-1位哲學家可以同時進餐。規定哲學家必須要同時拿起左右2支筷子。規定奇數座位的哲學家要先拿左邊的筷子，而偶數座位的哲學家要先拿右邊的筷子。這是在應用程式層次，針對問題特性來解決死結問題；另一種是在系統層次來解決,著作權所有 旗標出版股份有限公司,63,課堂練習-哲學家晚餐的修正版,請利用前面的提示，改寫出新的哲學家程式碼，以避免死結問題,著作權所有 旗標出版股份有限公司,64,練習解答,假設我們規定奇數座位的哲學家要先拿左邊的筷子，而偶數座位的哲學家要先拿右邊的筷子第i位哲學家的程式碼為：,do if (i % 2) wait(chopsticki);wait(chopstick (i + 1) % 5); else wait(chopstick(i + 1) % 5);wait(chopsticki);進食;signal(chopsticki);signal(chopstick (i + 1) % 5);思考; while (1);,著作權所有 旗標出版股份有限公司,65,3-5 監督器,為了解決號誌使用不當時，容易發生錯誤這個問題所發展的由編譯器負責產生臨界區前後用來控制存取的程式碼由一組初始化程式碼、共享資料物件、以及存取這些物件的函式所組成 監督器的特性任何外部函式都無法存取到監督器內的區域資料行程可以透過呼叫監督器的函式來進入監督器同一時間只能有一個行程在監督器內執行；其他呼叫監督器函式的行程，將會被放入佇列中等待,著作權所有 旗標出版股份有限公司,66,監督器的語法架構,monitor X/* 共用變數宣告 */int i;/* 條件變數宣告 */condition c;/* 臨界區存取函式宣告 */void CriticalSectionEntryPoint1();void CriticalSectionEntryPoint2();X/* X的初始化程式碼 */,著作權所有 旗標出版股份有限公司,67,Condition對應的運算,cwait：將呼叫該函式的行程暫停，並且放入該條件變數的佇列中。等待中的行程並不被認為是在監督器中。csignal：喚醒等待該條件變數的行程繼續執行；如果同時有多個行程暫停，則會從其中選擇一個喚醒。如果沒有行程在等待，則csignal就沒有任何作用。,著作權所有 旗標出版股份有限公司,68,有限緩衝區的實作 監督器 (1),monitor boundedBufferchar bufferN;int in, out, cnt;condition notempty, notfull;void append(char x) if (cnt = n)notfull.cwait();bufferin = x;in = (in + 1) % n;cnt+;notempty.csignal();,著作權所有 旗標出版股份有限公司,69,有限緩衝區的實作 監督器 (2),void take(char *x)if (cnt = 0)notempty.cwait();*x = bufferout;out = (out + 1) % n;cnt-;notfull.csignal();in =0; out = 0; cnt = 0;,著作權所有 旗標出版股份有限公司,70,有限緩衝區的實作 監督器 (3),void producer()char x;生產下筆資料x;append(x);void consumer()char x;take(,著作權所有 旗標出版股份有限公司,71,監督器的使用,使用監督器的方式：如果要生產資料：呼叫 boundedBducer()如果要取用資料：呼叫 boundedBuffer.consumer()優點：原本設計中必須處理的同步號誌，現在都可以交由監督器負責解決將同步機制的除錯，侷限在監督器的範圍內,著作權所有 旗標出版股份有限公司,72,3-6 死結,只要雙方都掌握了某些資源，也都需要對方手上的另外一些資源，就可能發生無限等待，而造成死結問題 死結發生的條件：互斥：資源必須是不可共享的 佔用且等候：行程在等候其他資源的時候，仍舊佔用某些資源 不可搶先：不能強制從已經取得資源的行程手中搶走它的資源 循環等待：兩個或更多行程形成一個封閉迴路，每個行程都在等待迴路中的下個行程所佔用的某些資源,著作權所有 旗標出版股份有限公司,73,圖3-10 循環等待的資源配置圖,行程 P1,行程 P2,請求,請求,佔用,佔用,資源 R1,資源 R2,著作權所有 旗標出版股份有限公司,74,死結的處理方式,預防避免偵測,著作權所有 旗標出版股份有限公司,75,預防死結,預防互斥：不可行；無法同時共用的資源本身一定具有互斥的特性 預防佔用且等候：要確保每個行程只有在不佔用資源的情況下，才可以請求資源 預防不可搶先：僅適用於可以輕易地保存狀態的資源 預防循環等待：為資源定義一個線性的優先權順序，規範行程在請求資源時，必須依照優先順序提出請求,著作權所有 旗標出版股份有限公司,76,避免死結,如果判斷某項資源配置請求會導致死結發生，就不要進行這項配置 安全狀態：系統能夠以某種安全執行序列為每個行程配置資源，並且避免死結的狀態安全執行序列：必須保證在序列後方之行程所需的資源數量，一定會小於系統目前尚未配置的資源數目，加上前方所有行程所持有的資源總數 當系統中存在這樣的一個安全序列時，我們可以確定當行程P1到Pi（1 = i n）結束的時候，行程Pi+1一定可以取得所有需要的資源當系統中找不出來這樣一組序列時，表示系統處於不安全狀態，也就是有發生死結的可能,著作權所有 旗標出版股份有限公司,77,圖3-11 安全的資源配置,安全執行序列,系統中擁有的R總數=12，目前閒置的R總數=3,著作權所有 旗標出版股份有限公司,78,圖3-12 不安全的資源配置,可能的配置情況：,系統中擁有的R總數=12，目前閒置的R總數=2,因為 4 小於P1 、P3 所需的數量 5，所以陷入死結狀態。,著作權所有 旗標出版股份有限公司,79,課堂練習,請根據行程的資源需求與配置情況，判斷下列系統是否處於安全狀態；如果是的話，請寫出它的安全執行序列,系統一：資源R的總數為11,系統二：資源R的總數為11,著作權所有 旗標出版股份有限公司,80,練習解答,系統一：處於不安全的狀態，找不到安全執行序列系統二：處於安全狀態，安全執行序列為P2P3P1,著作權所有 旗標出版股份有限公司,81,銀行家演算法,利用安全狀態的概念，藉由防止系統進入不安全狀態，來避免死結問題 主要包含兩個部份安全演算法資源請求演算法,著作權所有 旗標出版股份有限公司,82,銀行家演算法的資料結構,AvailableR：目前可用的資源數AllocationPR：每個行程目前配置的資源數量MaxPR：每個行程所需的最大資源數目NeedPR：每個行程之後還需要的資源數量（Need = Max Allocation）,著作權所有 旗標出版股份有限公司,83,安全演算法,1. 建立陣列WorkR與FinishP 並設定初值：Work=Available，Finishi=false（i=0到P-1）2. 尋找i，能夠滿足Finishi=false，且Needi =Needi，則結束3. 如果Requesti Available，則等待 4. 模擬配置後的情況： Available = Available Requesti; Allocationi = Allocationi + Requesti; Needi = Needi Requesti;5. 執行安全演算法，驗證系統是否安全。6. 如果不安全，則 Pi必須等待，並且 將Available、Allocationi、Needi 回復到模擬配置前的值,著作權所有 旗標出版股份有限公司,85,圖3-13 銀行家演算法範例,表格現況安全狀態，存在安全序列： P5 P3 P2 P1 P4,(a) P5要求（3, 1, 1)後安全狀態，存在安全序列： P5 P3 P2 P1 P4 允許配置,(b) P4要求（2, 1, 2)後不安全狀態，不存在安全序列不允許配置,著作權所有 旗標出版股份有限公司,86,偵測死結,如果系統並沒有去預防或避免死結，也可以藉由提供死結的偵測與回復，來保障所有行程的正常執行 當系統中的每種資源只有一份時，我們可以利用等候圖來偵測死結 等候圖是將資源配置圖的資源端點移除，而以PiPj表示Pi正在等候Pj所擁有的某項資源 當等候圖中的某些行程間形成一個封閉迴圈時，表示這些行程之間已經形成死結 如果每種資源的數量超過一個，則必須利用類似銀行家演算法中的安全演算法來作判斷,著作權所有 旗標出版股份有限公司,87,圖3-14 資源配置圖與等候圖,資源R2,行程P1,行程P2,行程P1,資源R1,資源R3,行程P3,行程P4,資源R4,行程P1,行程P2,行程P1,行程P3,行程P4,a. 資源配置圖,b. 等候圖,著作權所有 旗標出版股份有限公司,88,多份資源的死結偵測,類似安全演算法來進行死結的偵測 所需的資料結構：AvailableR：目前可用的資源數AllocationPR：每個行程目前配置的資源數量NeedPR ：每個行程目前需要的資源數量由於不需要做預防，因此不需要Max的資料，且N