处理器管理课件

處理器管理

處理器管理概述處理器管理的功能程式的執行處理器管理的功能處理器管理的主要任務是對處理器進行分配，並對其運行進行有效地控制和管理。處理器管理的主要功能進程控制進程同步進程通信進程調度程式的執行程式執行的描述前趨圖程式的順序執行程式的併發執行前趨圖概念：前趨圖是一個有向無迴圈圖。要求每個結點可用於表示一條語句、一個程式段等結點間的有向邊表示在兩個結點之間存在的前趨關係例如：圖2-1所示程式的順序執行概念：程式在執行時，必須按某種先後次序逐個執行操作，只有當前一個操作執行完後，才能執行後一個操作。特徵：順序性封閉性可再現性程式的併發執行概念：是指在一個時間段內執行多個程式。特徵：間斷性失去封閉性不可再現性程式併發執行的判斷方法：Bernstein條件利用前趨圖Bernstein條件原理：不同運算（或程式）的讀集與寫集的交集和寫集與寫集的交集的並集為空集時，這幾個運算（或程式）可以併發執行。解釋：運算的讀集是指在運算執行期間引用的所有變數的集合；運算的寫集是指在運算執行期間要改變的所有變數的集合。例子：例2-2利用前趨圖原理：畫出程式執行的前趨圖，根據該程式或運算在前趨圖中的位置關係，可以判斷其能否併發執行。解釋：在程式或運算的先後順序上，只有前後相鄰的的程式或運算不能併發執行，其餘程式和運算都可以併發執行。例子：例2-3進程描述進程的概念進程的狀態進程的掛起狀態進程的概念進程的定義一個程式在一個數據集合上的一次運行過程。所以一個程式在不同數據集合上運行，乃至一個程式在同樣數據集合上的多次運行都是不同的進程。進程的特徵動態性併發性獨立性非同步性結構性進程的狀態進程的三種基本狀態進程的其他兩種狀態進程狀態間的轉換進程的三種基本狀態就緒狀態當進程以分配到除處理器（CPU）以外的所有必要資源後，只要再獲得處理器就可以立即執行，這時進程的狀態稱為就緒狀態。執行狀態處於就緒狀態的進程一旦獲得了處理器，就可以運行，進程狀態也就處於執行狀態。阻塞狀態正在執行的進程因為發生某些事件（如請求輸入/輸出、申請額外空間等）而暫停運行，這種受阻暫停的狀態稱為阻塞狀態，也可以稱為等待狀態。進程的其他兩種狀態新狀態當一個新進程剛剛建立，還未將其放入就緒佇列時的狀態，稱為新狀態。終止狀態當一個進程已經正常結束或異常結束，操作系統已將其從系統佇列中移出，但尚未撤銷，這時稱為終止狀態。進程狀態間的轉換新狀態→就緒狀態就緒狀態→執行狀態執行狀態→阻塞狀態執行狀態→就緒狀態阻塞狀態→就緒狀態執行狀態→終止狀態如圖2-5所示進程的掛起狀態引入掛起狀態主要原因：用戶的需求父進程的需求操作系統的需求對換的需求引入掛起狀態後的進程狀態轉換執行狀態→靜止就緒活動就緒→靜止就緒靜止就緒→活動就緒活動阻塞→靜止阻塞靜止阻塞→活動阻塞靜止阻塞→靜止就緒進程控制進程控制塊PCB進程的創建與撤銷進程的阻塞與喚醒進程控制塊PCB進程控制塊的作用進程控制塊的內容進程控制塊的組織方式進程控制原語進程控制塊的作用概念進程控制塊是進程實體的重要組成部分，是操作系統中最重要的記錄型數據，在進程控制塊PCB（ProgramContralBlock）中記錄了操作系統所需要的、用於描述進程情況及控制進程運行所需要的全部資訊作用通過PCB，使得原來不能獨立運行的程式（數據），成為一個可以獨立運行的基本單位，一個能夠併發執行的進程。進程控制塊是進程存在的唯一標誌。進程控制塊的內容進程標識資訊進程識別字用於標識一個進程，一個進程通有外部識別字和內部識別字兩種說明資訊說明資訊是有關進程狀態等一些與進程調度有關的資訊。

現場資訊現場資訊是用於保留進程存放在處理器中的各種資訊，主要由處理器內的各個寄存器的內容組成。

管理資訊管理資訊包括進程資源、控制機制等一些進程執行所需要的資訊。

進程控制塊的組織方式鏈接方式把具有相同狀態的PCB，用其中的鏈接指針鏈接成佇列。如圖2-7所示。索引方式系統根據所有進程的狀態，建立幾張索引表。在每個索引表的表目中，記錄著具有相同狀態的各個PCB在表中的地址。如圖2-8所示。進程控制原語原語的概念原語是指具有特定功能的不可被中斷的過程。它主要用於實現操作系統的一些專門控制操作。原語的分類創建原語：用於為一個進程分配工作區和建立PCB，置該進程為就緒狀態。撤銷原語：用於一個進程工作完後，收回它的工作區和PCB。阻塞原語：用於進程在運行過程中發生等待事件時，把進程的狀態改為等待態。喚醒原語：用於當進程等待的事件結束時，把進程的狀態改為就緒態。

進程的創建引起進程創建的事件用戶登錄作業調度提供服務應用請求

進程創建的過程為新進程分配唯一的進程識別字，並從PCB佇列中申請一個空閒PCB。為新進程的程式和數據，以及用戶棧分配相應的主存空間及其它必要分配資源。初始化PCB中的相應資訊，如標識資訊、處理器資訊、進程控制資訊等。如果就緒佇列可以接納新進程，便將新進程加入到就緒佇列中。

進程的撤銷引起進程撤銷的事件進程正常結束在進程運行期間，由於出現某些錯誤和故障而使得進程被迫中止進程應外界的請求而中止運行

進程撤銷的過程根據被終止進程的識別字，從PCB集合中檢索該進程的PCB，讀出進程狀態。若該進程處於執行狀態，則立即終止該進程的執行。若該進程有子孫進程，還要將其子孫進程終止。將該進程所佔用的資源回收，歸還給其父進程或操作系統。將被終止進程的PCB從所在佇列中移出，並撤銷該進程的PCB。

進程的阻塞引起進程阻塞的事件請求系統服務啟動某種操作新數據尚未到達無新工作可做進程阻塞的過程立即停止執行該進程。修改進程控制塊中的相關資訊。把進程控制塊中的運行狀態由“執行”狀態改為“阻塞”狀態，並填入等待的原因，以及進程的各種狀態資訊。把進程控制塊插入到阻塞佇列。根據阻塞佇列的組織方式，把阻塞進程的進程控制塊插入到阻塞佇列中。轉調度程式重新調度，運行就緒佇列中的其他進程。

進程的喚醒引起進程喚醒的事件請求系統服務得到滿足啟動某種操作完成新數據已經到達有新工作可做進程喚醒的過程從阻塞佇列中找到該進程。修改該進程控制塊的相關內容。把阻塞狀態改為就緒狀態，刪除等待原因等等。把進程控制塊插入到就緒佇列。按照就緒佇列的組織方式，把被喚醒的進程的進程控制塊插入到就緒佇列中。

線程的基本概念1線程的概念線程是進程中的一個實體，是被系統獨立調度和執行的基本單位。線程與進程的比較調度單位不同併發形式不同擁有資源不同線程的基本概念2線程的類型系統級線程：是依賴於系統控制的，即無論是用戶進程中的線程，還是系統進程中的線程，它們的創建、撤銷、切換都是由系統控制實現的。用戶級線程：是由用戶控制，對於用戶級線程的創建、撤銷、切換，都與系統控制無關，完全由用戶自己管理。超線程超線程的概念超線程技術就是利用特殊的硬體指令，在一顆實體處理器中放入兩個邏輯處理單元，從而模擬成兩個工作環境，讓單個處理器都能使用線程級並行計算，同時處理多項任務，提升處理器資源的使用率。

超線程的工作超線程處理器被視為兩個分離的邏輯處理器，應用程式不須修正就可使用這兩個邏輯處理器。每個邏輯處理器都可獨立回應中斷。第一個邏輯處理器可追蹤一個軟體線程，而第二個邏輯處理器則可同時追蹤另一個軟體線程。由於兩個線程共同使用同樣的執行資源，因此不會產生一個線程執行的同時，另一個線程閒置的狀況。進程同步與互斥進程的併發性進程的同步與互斥利用PV操作實現互斥與同步管程的基本概念進程的併發性概念在併發執行的系統中，若干個作業可以同時執行，而每個作業又需要有多個進程協作完成。在這些同時存在的進程間具有併發性併發進程之間的關係無關關係：這些進程間彼此毫無關係，互不影響相關關係：這些進程間彼此往往相關，互相影響，要進行合理的控制和協調才能正確執行資源共用關係相互合作關係進程的同步與互斥進程同步與互斥的概念進程同步機制應遵循的原則利用鎖機制實現同步進程同步與互斥的概念臨界資源在系統中有許多硬體或軟體資源，在一段時間內只允許一個進程訪問或使用，這種資源稱為臨界資源。

臨界區每個進程中訪問臨界資源的那段代碼稱為臨界區

進程同步進程同步是指多個相關進程在執行次序上的協調，這些進程相互合作，在一些關鍵點上需要相互等待或相互通信。

進程互斥進程互斥是指當一個進程進入臨界區使用臨界資源時，另一個進程必須等待，當佔用臨界資源的進程退出臨界區後，另一個進程才被允許使用臨界資源。

進程同步機制應遵循的原則空閒讓進忙則等待有限等待讓權等待利用鎖機制實現同步鎖的概念在同步機構中，常用一個變數來代表臨界資源的狀態，並稱它為鎖。通常用“0”表示資源可用，用“1”表示資源已被佔用。鎖的操作關鎖操作解鎖操作利用PV操作實現互斥與同步整型信號量的概念信號量的操作利用PV操作實現互斥利用PV操作實現同步利用PV操作實現進程的同步加互斥整型信號量的概念概念信號量就是一種特殊變數，它用來表示系統中資源的使用情況。而整型信號量就是一個整型變數。說明：當其值大於“0”時，表示系統中對應可用資源的數目；當其值小於“0”時，其絕對值表示因該類資源而被阻塞的進程的數目；當其值等於“0”時，表示系統中對應資源已經都被佔用，並且沒有因該類資源而被阻塞的進程。信號量的操作（1）P操作：記為P（S），描述為：

P（S）

{S=S-1；

if（S<0）W（S）；

}（2）V操作：記為V（S），描述為：

V（S）

{S=S+1；

if（S<=0）R（S）；

}利用PV操作實現互斥概念：互斥信號量是根據臨界資源的類型設置的。有幾種類型的臨界資源就設置幾個互斥信號量。它代表該類臨界資源的數量，或表示是否可用，其初值一般為“1”。例題【例2-4】在一個只允許單向行駛的十字路口，分別有若干由東向西，由南向北的車輛在等待通過十字路口。為了安全，每次只允許一輛車通過。當有車輛通過時其他車輛必須等候，當無車輛在路口行駛時則允許一輛車通過。請用PV操作實現保證十字路口安全行駛的自動管理系統。

【例2-5】有4位哲學家圍著一個圓桌在思考和進餐，每人思考時手中什麼都不拿，當需要進餐時，每人需要用刀和叉各一把，餐桌上的佈置如圖2-12所示，共有2把刀和2把叉，每把刀或叉供相鄰的兩個人使用。請用信號量及PV操作說明4位哲學家的同步過程。【例2-6】在南開大學和天津大學之間有一條彎曲的小路，其中從S到T有一段路每次只允許一輛自行車通過，但其中有一個小的安全島M（同時允許兩輛自行車停留），可供兩輛自行車錯車時使用，如圖2-14所示。試設計一個演算法使來往自行車可以順利通過。利用PV操作實現同步概念同步信號量是根據進程的數量設置的。一般情況下，有幾個進程就設置幾個同步信號量，表示該進程是否可以執行，或表示該進程是否執行結束。其初值一般為“0”。例子【例2-7】圖2-16給出了4個進程合作完成某一任務的前趨圖，試說明這4個進程間的同步關係，並用PV操作描述它們。方法一：同步信號量用來表示該進程是否可以開始。方法二：同步信號量用來表示該進程是否已經結束。例子【例2-8】桌上有一個空盤子，只允許放一個水果。爸爸可以向盤中放蘋果，也可以向盤中放桔子，兒子專等吃盤中的桔子，女兒專等吃盤中的蘋果。規定當盤空時，一次只能放一只水果，請用PV操作實現爸爸、兒子、女兒3個併發進程的同步。【例2-9】有3個進程PA、PB、PC合作解決記錄列印問題：PA將記錄從磁片讀入主存的緩衝區1，每執行一次讀一個記錄；PB將緩衝區1的記錄複製到緩衝區2，每執行一次複製一個記錄；PC將緩衝區2的記錄列印出來，每執行一次列印一個記錄；緩衝區的大小等於一個記錄的PA、PB、PC大小。請用PV操作來保證記錄的正確列印。

使用PV操作實現進程的同步加互斥

概念例子【例2-10】某資料庫有一個寫進程，多個讀進程，它們之間讀、寫操作的互斥要求是：寫進程運行時，其他讀、寫進程不能對數據庫操作，讀進程之間不互斥，可以同時讀數據庫。請用信號量及PV操作描述這一組進程的工作過程。例題【例2-11】設有一個具有N個資訊元素的環形緩衝區，A進程順序地把資訊寫進緩衝區，B進程依次地從緩衝區中讀出資訊，用PV操作表示A、B進程的同步演算法。【例2-12】理髮師理髮問題。有一個理髮師，一把理髮椅和n把等候理髮顧客坐的椅子。如果沒有顧客，則理髮師在理發椅上睡覺；當一個顧客到來時，必須喚醒理髮師，進行理髮；如果理髮師正在理髮，又有顧客來到時，如果有空椅子可坐，他就坐下來等候，如果沒有空椅子，他就離開。請為理髮師和顧客各編一個程式表述他們的行為。同步與互斥的解題思路①分清哪些是互斥問題（互斥訪問臨界資源的），哪些是同步問題（具有前後執行順序要求的）。②對互斥問題要設置互斥信號量，不管有互斥關係的進程有幾個或幾類，通常只設置一個互斥信號量，且初值為1，代表一次只允許一個進程對臨界資源訪問。③對同步問題要設置同步信號量，通常同步信號量的個數與參與同步的進程種類有關，即同步關係涉及幾類進程，就有幾個同步信號量。同步信號量表示該進程是否可以開始或該進程是否已經結束。④在每個進程中用於實現互斥的PV操作必須成對出現；用於實現同步的PV操作也必須成對出現，但可以分別出現在不同的進程中；在某個進程中如果同時存在互斥與同步的P操作，則其順序不能顛倒，必須先執行對同步信號量的P操作，再執行對互斥信號量的P操作，但V操作的順序沒有嚴格要求。同步與互斥的解題步驟（1）確定進程。包括進程的數量、進程的工作內容，可以用流程圖描述。（2）確定同步互斥關係。根據是否使用的是臨界資源，還是處理的前後關係，確定同步與互斥，然後確定信號量的個數、含義，以及對信號量的P、V操作。（3）用類C語言描述同步或互斥演算法。管程的基本概念概念管程實際上是定義了一個數據結構和在該數據結構上的能為併發進程所執行的一組操作，這組操作能同步進程和改變管程中的數據。說明：管程由3部分組成：局部於管程的共用變數說明、對該數據結構進行操作的一組過程、對局部於管程的數據設置初始值的語句。每個管程都應該有唯一的名字來標識。

進程通信概念進程通信是指進程間的資訊交換。類型共用記憶體系統消息傳遞系統管道通信系統共用記憶體系統概念在共用記憶體系統中，相互通信的進程共用某些數據結構或共用存儲區，進程之間能夠通過它們進行通信。方式共用數據結構方式相互通信的諸進程公用某些數據結構，並通過這些數據交換資訊。共用存儲區方式是在記憶體中劃出一塊共用存儲區，相互通信的諸進程可以通過對共用存儲區中的數據進行讀或寫來實現通信。消息傳遞系統概念進程間的數據交換以消息為單位，用戶直接利用系統中提供的一組通信命令（原語）進行通信。方式直接通信方式發送進程使用發送原語直接將消息發送給接收進程，並將它掛在接收進程的消息緩衝佇列上，接收進程使用接收原語從消息緩衝佇列中取出消息。間接通信方式發送進程使用發送原語直接將消息發送到某種中間實體中，接收進程使用接收原語從該中間實體中取出消息。管道通信系統管道管道是指連接讀進程和寫進程，以實現它們之間通信的共用檔。管道通信系統向管道提供輸入的發送進程（寫進程），以字元流形式將大量的數據送入管道，而接受管道輸出的接收進程（讀進程），可以從管道中接收數據。進程調度進程調度的類型選擇進程調度演算法的原則常用的進程調度演算法進程調度的類型高級調度低級調度中級調度高級調度基本原理高級調度又稱為作業調度或長程調度，用於決定把外存上處於後備佇列中的哪些作業調入主存，並為它們創建進程、分配必要的資源，然後將新創建的進程排入就緒佇列，準備執行。需要解決的問題一是接納多少個作業。二是接納哪些作業。低級調度基本原理低級調度通常又稱為進程調度或短程調度。它決定主存中的就緒佇列上的哪個進程（單處理器系統）將獲得處理器，然後把處理器分配給該進程，使其執行。

方式非搶佔方式在某個進程正在佔用處理器執行時，不允許其他任何進程搶佔處理器。搶佔方式把處理器分配給某個進程後，在該進程尚未終止或阻塞時，允許系統調度程式根據某種原則，暫停正在執行的進程，回收已經分配的處理器，並將處理器重新分配給其他更為緊急的進程。中級調度基本原理系統將那些暫時不能運行的進程從主存調到外存（仍然保持進程狀態）上的特定區域，這些在外存存放的進程所處的狀態稱為就緒駐外狀態或掛起狀態。當這些進程的運行條件具備，且主存又有空閑時，在中級調度的控制下，再將處於外存上的那些重新具備運行條件的就緒駐外進程調入主存，並將其狀態修改為就緒狀態，放入就緒佇列，等待進程調度。目的是為了進一步提高主存的利用率和系統的吞吐量。選擇進程調度演算法的原則面向用戶的原則周轉時間短回應時間快截止時間有保證優先權原則面向系統的原則系統吞吐量高處理器利用率好各類資源的平衡利用

常用的進程調度演算法先來先服務調度演算法短進程優先調度演算法時間片輪轉調度演算法優先數調度演算法回應比高者優先調度演算法多級佇列調度演算法先來先服務調度演算法原理每次調度是從就緒佇列中，選擇一個最先進入就緒佇列的進程，把處理器分配給該進程，使之得到執行。該進程一旦佔有了處理器，它就一直運行下去，直到該進程完成或因發生事件而阻塞，才退出處理器。特點利於長進程，而不利於短進程。短進程優先調度演算法原理它是從就緒佇列中選擇一個估計運行時間最短的進程，將處理器分配給該進程，使之佔有處理器並執行，直到該進程完成或因發生事件而阻塞，然後退出處理器，再重新調度。特點照顧到了系統中占大部分的短進程，有效地降低了進程的平均等待時間，提高了系統的吞吐量，但對長進程不利。時間片輪轉調度演算法原理系統將所有的就緒進程按進入就緒佇列的先後次序排列。每次調度時把CPU分配給隊首進程，讓其執行一個時間片，當時間片用完，由計時器發出時鐘中斷，調度程式則暫停該進程的執行，使其退出處理器，並將它送到就緒佇列的末尾，等待下一輪調度執行。特點為了保證人機交互的及時性，系統使每個進程依次按時間片方式輪流地執行。優先數調度演算法原理它是從就緒佇列中選擇一個優先權最高的進程，讓其獲得處理器並執行。方式非搶佔式優先數調度演算法系統一旦把處理器分配給就緒佇列中優先權最高的進程後，該進程就佔有處理器一直運行下去，直到該進程完成或因發生事件而阻塞，才退出處理器。

搶佔式優先數調度演算法系統同樣把處理器分配給當前就緒佇列中優先權最高的進程，使之執行。但在其執行期間，仍然會不斷的有新的就緒進程進入就緒佇列，如果出現某個進程，其優先權比當前正在執行的進程的優先權還高時，進程調度程式就會立即暫停當前進程的執行，而將處理器收回，並將處理器分配給新出現的優先權更高的進程，讓其執行。

回應比高者優先調度演算法原理它是從就緒佇列中選擇一個回應比最高的進程，讓其獲得處理器執行，直到該進程完成或因等待事件而退出處理器為止。特點既照顧了短進程，又考慮了進程到達的先後次序，也不會使長進程長期得不到服務，因此是一個比較全面考慮的演算法，但每次進行調度時，都需要對各個進程計算回應比。所以系統開銷很大，比較複雜。多級佇列調度演算法原理是根據進程的類型或性質的不同，將就緒進程分為若干個獨立佇列，不同類型或性質的進程固定地分屬於一個佇列，每個佇列可以採用適合的調度演算法，不同的佇列可使用不同的調度演算法。特點同時具有多種操作方式的進程調度進程死鎖死鎖的基本概念死鎖的預防死鎖的避免死鎖的檢測與解除死鎖的