操作系統(tǒng)原理 -1

1、第二章 進程管理、作業(yè)管理,1、進程概念：理解進程的引入及進程的基本特征；2、進程的同步與互斥：了解進程表示PCB、進程的狀態(tài)；理解并掌握進程調(diào)度的基本算法、并發(fā)進程間的互相制約關系、臨界區(qū)的概念；理解并掌握利用鎖操作法實現(xiàn)互斥，利用信號量及P、V操作實現(xiàn)同步與互斥的方法。經(jīng)典示例：生產(chǎn)者與消費者問題、讀者與寫者問題等3、進程通信：了解進程通信的不同方式（信號、管道、消息緩沖等）；4、死鎖：掌握產(chǎn)生死鎖的必要條件；對付死鎖的策略

2、：死鎖的預防、死鎖的避免（銀行家算法）；死鎖的檢測與解除（進程資源圖及其化簡）。5、了解作業(yè)的概念、作業(yè)管理的基本功能、作業(yè)狀態(tài)及其轉(zhuǎn)換；6、理解并掌握作業(yè)調(diào)度的基本算法、作業(yè)控制的方式。,2,第二章 進程管理、作業(yè)管理,2.1 基本概念作業(yè)（job）：任務（task）作業(yè)步：作業(yè)的工作步驟程序：靜態(tài)概念，指令的集合 前趨圖的定義前趨圖（Precedence Graph）是一個有向無循環(huán)圖。結(jié)點語句、程序段或

3、進程 圖2.2邊偏序或前趨關系 ? （Pi，Pj）Pi ? Pj,前趨關系,4,程序的執(zhí)行方式：順序執(zhí)行和并發(fā)執(zhí)行,一、程序順序執(zhí)行圖2.1 輸入I－>計算C－>打印P順序執(zhí)行的特征順序性：按照程序結(jié)構(gòu)所指定的次序（可能有分支或循環(huán)）封閉性：獨占全部資源，計算機的狀態(tài)只由于該程序的控制邏輯所決定可再現(xiàn)性：初始條件相同則結(jié)果相同。,5,二、多程序并發(fā)執(zhí)行圖2.4Ii －&g

4、t; Ci，Ci －> Pi，Ii －> Ii+1，Ci－> Ci+1，Pi－>Pi+1,6,間斷(異步)性："走走停停"，一個程序可能走到中途停下來，失去原有的時序關系；失去封閉性：共享資源，受其他程序的控制邏輯的影響。如：一個程序?qū)懙酱鎯ζ髦械臄?shù)據(jù)可能被另一個程序修改，失去原有的不變特征。不可再現(xiàn)性：失去封閉性 －>失去可再現(xiàn)性；外界環(huán)境在程序的兩次執(zhí)行期間發(fā)生變化，失去原有的可

5、重復特征。,并發(fā)執(zhí)行的特征：,7,程序并發(fā)執(zhí)行的條件,程序 P(Si) 針對共享變量的讀集和寫集 R(Si)和W(Si)條件：任意兩個程序P(Si)和P(Sj)，有：R(Si)?W(Sj)=?;W(Si)?R(Sj)=?;W(Si)?W(Sj)=?;,并發(fā)執(zhí)行失去封閉性的原因是共享資源的影響，去掉這種影響就行了。1966年，由Bernstein給出并發(fā)執(zhí)行的條件。（這里沒有考慮執(zhí)行速度的影響。）,前兩條保證一個程序的兩次讀之間數(shù)

6、據(jù)不變化；最后一條保證寫的結(jié)果不丟掉。,8,四條語句：S1: a = x +y; R(S1) = {x, y}, W(S1) = {a}S2: b = z +1; R(S2) = {z}, W(S2) = S3: c = a – b; R(S3) = {a, b}, W(S3) = {c}S4: w = c + 1; R(S1) = {c}, W(S1) = {w}S1和S2S1和S3、S2和S

7、3,9,進程的概念,各種定義一個具有一定獨立功能的程序在一個數(shù)據(jù)集合上的一次動態(tài)執(zhí)行過程。進程的特征動態(tài)性：進程具有動態(tài)的地址空間（數(shù)量和內(nèi)容），系統(tǒng)控制信息（進程控制塊的生成和刪除）獨立性：各進程的地址空間相互獨立，除非采用進程間通信手段；并發(fā)性、異步性：,10,進程與程序的區(qū)別,進程是動態(tài)的，程序是靜態(tài)的：程序是有序代碼的集合；進程是程序的執(zhí)行。通常進程不可在計算機之間遷移；而程序通常對應著文件、靜態(tài)和可以復制。進

8、程是暫時的，程序的永久的：進程是一個狀態(tài)變化的過程，程序可長久保存。進程與程序的組成不同：進程的組成包括程序、數(shù)據(jù)和進程控制塊（即進程狀態(tài)信息）。進程與程序的對應關系：通過多次執(zhí)行，一個程序可對應多個進程；通過調(diào)用關系，一個進程可包括多個程序。,11,2.2 進程管理,2.2.1 進程的基本狀態(tài)進程的三種基本狀態(tài)就緒狀態(tài)(Ready)：進程已獲得除處理機外的所需資源，等待分配處理機資源；只要分配CPU就可執(zhí)行。一個或多個就緒

9、隊列 可以按多個優(yōu)先級來劃分隊列，如：時間片用完－>低優(yōu)，I/O完成－>中優(yōu)，頁面調(diào)入完成－>高優(yōu),12,運行狀態(tài)(Running)：占用處理機資源；處于此狀態(tài)的進程的數(shù)目小于等于CPU的數(shù)目。在沒有其他進程可以執(zhí)行時（如所有進程都在阻塞狀態(tài)），通常會自動執(zhí)行系統(tǒng)的idle進程（相當于空操作）。阻塞狀態(tài)(Blocked)：由于進程等待某種條件（如I/O操作或進程同步），在條件滿足之前無法繼續(xù)執(zhí)行。該事件發(fā)生前

10、即使把處理機分配給該進程，也無法運行。如：等待I/O操作的完成。等待或睡眠狀態(tài)原因不同，多個隊列,14,進程的掛起狀態(tài),掛起狀態(tài)的引入終端用戶的需要 用于調(diào)試：在調(diào)試時，掛起被調(diào)試進程（從而對其地址空間進行讀寫）父進程的需求操作系統(tǒng)的需要對換的需要負荷調(diào)節(jié)的需要 實時任務執(zhí)行，內(nèi)存緊張,15,具有掛起狀態(tài)的進程狀態(tài)圖,16,線程,進程：兩個基本屬性 資源分配單位（存儲器、文件）和CPU調(diào)度（分派）單位。

11、又稱為"任務(task)“并發(fā)執(zhí)行 創(chuàng)建、撤銷進程，進程切換 時空開銷大線程：進程兩個屬性分開，只作為CPU調(diào)度單位，而共享進程所擁有的全部資源。只擁有必不可少的資源，如：線程狀態(tài)、寄存器上下文和棧同樣具有就緒、阻塞和執(zhí)行三種基本狀態(tài),17,線程與進程,18,進程和線程的比較,調(diào)度--兩個屬性分開 同一進程中線程上下文切換比不同進程上下文切換要快得多；并發(fā)性--進程之間、線程之間，文件服務-設多個服務線程擁

12、有資源--地址空間和其他資源（如打開文件）：進程間相互獨立，同一進程的各線程間共享，進程內(nèi)的線程對其他進程不可見,19,系統(tǒng)開銷：減小并發(fā)執(zhí)行的時間和空間開銷（線程的創(chuàng)建、退出和調(diào)度），因此容許在系統(tǒng)中建立更多的線程來提高并發(fā)程度。線程的創(chuàng)建時間比進程短；線程的終止時間比進程短；同進程內(nèi)的線程切換時間比進程短；由于同進程內(nèi)線程間共享內(nèi)存和文件資源，可直接進行不通過內(nèi)核的通信；線程間可以直接讀寫進程數(shù)據(jù)段（如全局變量）來進行通信；

13、進程間通信IPC，需要進程同步和互斥手段的輔助，以保證數(shù)據(jù)的一致性,20,2.2.2 進程控制塊(PCB, process control block),進程控制塊是由OS維護的用來記錄進程相關信息的一塊內(nèi)存。PCB是進程存在的唯一標志，常駐內(nèi)存。每個進程在OS中的登記表項（可能有總數(shù)目限制），OS據(jù)此對進程進行控制和管理（PCB中的內(nèi)容會動態(tài)改變）處于核心段，通常不能由應用程序自身的代碼來直接訪問，而要通過系統(tǒng)調(diào)用，或通過如U

14、NIX中的進程文件系統(tǒng)(/proc)直接訪問進程映象(image)。文件名為進程標識（如：00316），權(quán)限為創(chuàng)建者可讀寫。,22,PCB的組織方式,線性表、鏈表、索引表,25,進程控制,原語 -- 若干條機器指令組成的不可中斷的完成特定功能的一段程序。創(chuàng)建、掛起、激活、阻塞、喚醒、撤銷、通訊進程樹,UNIXWindows (Process Explorer),27,2.3 進程調(diào)度,2.3.1 調(diào)度的層次和狀態(tài)1 作業(yè)狀態(tài)及其

15、轉(zhuǎn)換提交 - 收容 - 執(zhí)行 - 完成,29,2 調(diào)度的層次高級調(diào)度 ：又稱為“長程調(diào)度”、“作業(yè)調(diào)度”。從用戶工作流程的角度，一次提交的若干個流程，其中每個程序按照進程調(diào)度。時間上通常是分鐘、小時或天。接納多少作業(yè)接納哪些作業(yè) 調(diào)度算法,30,低級調(diào)度：又稱為“短程調(diào)度”、“進程或線程”。從CPU資源的角度，執(zhí)行的單位。時間上通常是毫秒。因為執(zhí)行頻繁，要求在實現(xiàn)時達到高效率。兩種調(diào)度方式：非搶占方式搶占方式 時

16、間片 優(yōu)先權(quán) 短作業(yè)(進程)優(yōu)先中級調(diào)度：又稱為“中程調(diào)度”，內(nèi)外存交換。從存儲器資源的角度。將進程的部分或全部換出到外存上，將當前所需部分換入到內(nèi)存。指令和數(shù)據(jù)必須在內(nèi)存里才能被CPU直接訪問。,31,2.3.2 選擇調(diào)度方式和算法的若干準則,我們可從不同的角度來判斷處理機調(diào)度算法的性能，如用戶的角度、處理機的角度和算法實現(xiàn)的角度。實際的處理機調(diào)度算法選擇是一個綜合的判斷結(jié)果。1. 面向用戶的調(diào)度性能準則周轉(zhuǎn)時間：作業(yè)從提交到完

17、成（得到結(jié)果）所經(jīng)歷的時間。包括：在收容隊列中等待，CPU上執(zhí)行，就緒隊列和阻塞隊列中等待，結(jié)果輸出等待平均周轉(zhuǎn)時間T平均帶權(quán)周轉(zhuǎn)時間（帶權(quán)周轉(zhuǎn)時間W是 T(周轉(zhuǎn))/T(CPU執(zhí)行)〕,32,響應時間：用戶輸入一個請求（如擊鍵）到系統(tǒng)給出首次響應（如屏幕顯示）的時間－－分時系統(tǒng)截止時間：開始截止時間和完成截止時間－－實時系統(tǒng)，與周轉(zhuǎn)時間有些相似。優(yōu)先權(quán)：可以使關鍵任務達到更好的指標。不因作業(yè)或進程本身的特性而使上述指標過分惡

18、化。如長作業(yè)等待很長時間。,33,2. 面向系統(tǒng)的調(diào)度性能準則吞吐量：單位時間內(nèi)所完成的作業(yè)數(shù)，跟作業(yè)本身特性和調(diào)度算法都有關系－－批處理系統(tǒng)平均周轉(zhuǎn)時間不是吞吐量的倒數(shù)，因為并發(fā)執(zhí)行的作業(yè)在時間上可以重疊。如：在2小時內(nèi)完成4個作業(yè)，而每個周轉(zhuǎn)時間是1小時，則吞吐量是2個作業(yè)/小時處理機利用率：－－大中型主機各種設備的均衡利用：如CPU繁忙的作業(yè)和I/O繁忙（指次數(shù)多，每次時間短）的作業(yè)搭配－－大中型主機,34,2.3.3 調(diào)

19、度算法,通常將作業(yè)或進程歸入各種就緒或阻塞隊列。有的算法適用于作業(yè)調(diào)度，有的算法適用于進程調(diào)度，有的兩者都適用。,1 先來先服務2 短作業(yè)（進程）CPU運行期優(yōu)先3 時間片輪轉(zhuǎn)算法4 優(yōu)先級算法5 高響應比優(yōu)先算法6 多級隊列算法7 多級反饋隊列算法,35,1 先來先服務,按照作業(yè)提交或進程變?yōu)榫途w狀態(tài)的先后次序，分派CPU；當前作業(yè)或進程占用CPU，直到執(zhí)行完或阻塞，才出讓CPU（非搶占方式）。在作業(yè)或進程喚醒后（如I

20、/O完成），并不立即恢復執(zhí)行，通常等到當前作業(yè)或進程出讓CPU。最簡單的算法。,(FCFS, First Come First Served)這是最簡單的調(diào)度算法，按先后順序進行調(diào)度。非搶占式方式,平均周轉(zhuǎn)時間 （a）27 （b）13,37,FCFS的特點,比較有利于長作業(yè)，而不利于短作業(yè)。有利于CPU繁忙的作業(yè)，而不利于I/O繁忙的作業(yè)。,38,2 短CPU運行期優(yōu)先,對預計執(zhí)行時間短的作業(yè)（進程）優(yōu)先分派處理機。通常后來的短

21、作業(yè)不搶先正在執(zhí)行的作業(yè)。,Shortest CPU Burst First（SCBF）又稱為短作業(yè)（進程）優(yōu)先(SJF, Shortest Job First)，“短進程優(yōu)先”SPN(Shortest Process Next)；這是對FCFS算法的改進，其目標是減少平均周轉(zhuǎn)時間。,平均周轉(zhuǎn)時間 （a）15.75 （b）13,40,SCBF（SJF）的特點,優(yōu)點：比FCFS改善平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間，縮短作業(yè)的等待時間

22、；提高系統(tǒng)的吞吐量；缺點：對長作業(yè)非常不利，可能長時間得不到執(zhí)行；未能依據(jù)作業(yè)的緊迫程度來劃分執(zhí)行的優(yōu)先級；難以準確估計作業(yè)（進程）的執(zhí)行時間，從而影響調(diào)度性能。,41,3 時間片輪轉(zhuǎn)(Round Robin)算法,前兩種算法主要用于宏觀調(diào)度，說明怎樣選擇一個進程或作業(yè)開始運行，開始運行后的作法都相同，即運行到結(jié)束或阻塞，阻塞結(jié)束時等待當前進程放棄CPU 。本算法主要用于微觀調(diào)度，說明怎樣并發(fā)運行，即切換的方式；設計

23、目標是提高資源利用率。其基本思路是通過時間片輪轉(zhuǎn)，提高進程并發(fā)性和響應時間特性，從而提高資源利用率；,42,A. 時間片輪轉(zhuǎn)算法,將系統(tǒng)中所有的就緒進程按照FCFS原則，排成一個隊列。每次調(diào)度時將CPU分派給隊首進程，讓其執(zhí)行一個時間片。時間片的長度從幾個ms到幾百ms。在一個時間片結(jié)束時，發(fā)生時鐘中斷。調(diào)度程序據(jù)此暫停當前進程的執(zhí)行，將其送到就緒隊列的末尾，并通過上下文切換執(zhí)行當前的隊首進程。進程可以未使用完一個時間片，

24、就出讓CPU（如阻塞）。,43,B. 時間片長度的確定,時間片長度變化的影響過長－>退化為FCFS算法，進程在一個時間片內(nèi)都執(zhí)行完，響應時間長。過短－>用戶的一次請求需要多個時間片才能處理完，上下文切換次數(shù)增加，響應時間長。對響應時間的要求：T(響應時間)=N(進程數(shù)目)*q(時間片)時間片長度的影響因素：就緒進程的數(shù)目：數(shù)目越多，時間片越小（當響應時間一定時）系統(tǒng)的處理能力：應當使用戶輸入通常在一個時間片內(nèi)能

25、處理完，否則使響應時間，平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間延長。,44,4 優(yōu)先權(quán)算法,適用于作業(yè)調(diào)度和進程調(diào)度，可分成搶先式和非搶先式；A 靜態(tài)優(yōu)先權(quán)創(chuàng)建進程時就確定，直到進程終止前都不改變。通常是一個整數(shù)。依據(jù)：進程類型（系統(tǒng)進程優(yōu)先級較高）對資源的需求（對CPU和內(nèi)存需求較少的進程，優(yōu)先級較高）提交的時間次序用戶要求（緊迫程度和付費多少）,45,B 動態(tài)優(yōu)先權(quán) 在創(chuàng)建進程時賦予的優(yōu)先級，在進程運行過程中可以自

26、動改變，以便獲得更好的調(diào)度性能。如：在就緒隊列中，等待時間延長則優(yōu)先級提高，從而使優(yōu)先級較低的進程在等待足夠的時間后，其優(yōu)先級提高到可被調(diào)度執(zhí)行；進程每執(zhí)行一個時間片，就降低其優(yōu)先級，從而一個進程持續(xù)執(zhí)行時，其優(yōu)先級降低到出讓CPU。,46,5 高響應比優(yōu)先算法,"最高響應比優(yōu)先"HRRN(Highest Response Ratio Next)響應比R = (等待時間 + 要求執(zhí)行時間) / 要求執(zhí)行時間是

27、FCFS和SJF的折衷,47,6 多級隊列算法,根據(jù)作業(yè)或進程的性質(zhì)或類型的不同，將就緒隊列再分為若干個子隊列。每個作業(yè)固定歸入一個隊列。各隊列的不同處理：不同隊列可有不同的優(yōu)先級、時間片長度、調(diào)度策略等。如：系統(tǒng)進程、用戶交互進程、批處理進程等。前臺-時間片輪轉(zhuǎn)、后臺-FCFS,本算法引入多個就緒隊列，通過各隊列的區(qū)別對待，達到一個綜合的調(diào)度目標；,48,7 多級反饋隊列算法,多級反饋隊列算法是時間片輪轉(zhuǎn)算法和優(yōu)先級算法的綜合

28、和發(fā)展。優(yōu)點：為提高系統(tǒng)吞吐量和縮短平均周轉(zhuǎn)時間而照顧短進程為獲得較好的I/O設備利用率和縮短響應時間而照顧I/O型進程不必估計進程的執(zhí)行時間，動態(tài)調(diào)節(jié),49,多級反饋隊列算法,設置多個就緒隊列，分別賦予不同的優(yōu)先級，如逐級降低，隊列1的優(yōu)先級最高。每個隊列執(zhí)行時間片的長度也不同，規(guī)定優(yōu)先級越低則時間片越長，如逐級加倍新進程進入內(nèi)存后，先投入隊列1的末尾，按FCFS算法調(diào)度；若按隊列1一個時間片未能執(zhí)行完，則降低投入到隊列2的末

29、尾，同樣按FCFS算法調(diào)度；如此下去，降低到最后的隊列，則按"時間片輪轉(zhuǎn)"算法調(diào)度直到完成。僅當較高優(yōu)先級的隊列為空，才調(diào)度較低優(yōu)先級的隊列中的進程執(zhí)行。如果進程執(zhí)行時有新進程進入較高優(yōu)先級的隊列，則搶先執(zhí)行新進程，并把被搶先的進程投入原隊列的末尾。,50,性能,終端型作業(yè)用戶短批處理作業(yè)用戶長批處理作業(yè)用戶,51,2.4 進程的同步與互斥,多道程序環(huán)境－>進程之間存在資源共享，運行時間受影響多個進

30、程在對硬件或軟件（如外設、共享代碼段、共享數(shù)據(jù)結(jié)構(gòu)）進行訪問時（如寫入或修改），必須互斥地進行有些共享資源可以同時訪問，如只讀數(shù)據(jù)進程間資源共享關系-訪問沖突共享變量的修改沖突操作順序沖突進程間相互合作關系-制約間接制約：進行競爭－－獨占分配到的部分或全部共享資源，“互斥”直接制約：進行協(xié)作－－等待來自其他進程的信息，“同步” 通訊,52,2.4.1 臨界資源和臨界區(qū),1 臨界資源臨界資源：一次僅允許一個進程使用的資源。

31、互斥：指多個進程不能同時使用同一個資源；死鎖：指多個進程互不相讓，都得不到足夠的資源而互相等待；饑餓：指一個進程一直得不到資源（其他進程可能輪流占用資源）,共享變量的修改沖突,54,2 臨界區(qū),臨界區(qū)(critical section)：進程中訪問臨界資源的一段代碼。進入?yún)^(qū)(entry section)：在進入臨界區(qū)之前，檢查可否進入臨界區(qū)的一段代碼。如果可以進入臨界區(qū)，通常設置相應"正在訪問臨界區(qū)"標志退

32、出區(qū)(exit section)：用于將"正在訪問臨界區(qū)"標志清除。剩余區(qū)(remainder section)：代碼中的其余部分。,臨界區(qū)的進入,56,臨界區(qū)設計原則：,空閑則入：所有進程均不處于臨界區(qū)，選擇一個；忙則等待：已有進程處于其臨界區(qū)，互斥；有限等待：等待進入臨界區(qū)的進程不能"死等"；讓權(quán)等待：不能進入臨界區(qū)的進程，應釋放CPU（如轉(zhuǎn)換到阻塞狀態(tài)），不能“忙等”,57,3 訪問

33、臨界區(qū)的軟件方法 Dekker,有兩個進程P0, P1設立一個公用整型變量 turn：描述允許進入臨界區(qū)的進程標識在進入?yún)^(qū)循環(huán)檢查是否允許本進程進入：turn為i時，進程Pi可進入；在退出區(qū)修改允許進入進程標識：進程Pi退出時，改turn為進程Pj的標識j；設立一個標志數(shù)組flag[2]：描述進程是否在臨界區(qū)，初值均為FALSE，0。先修改，后檢查：在進入?yún)^(qū)修改本進程在臨界區(qū)的標志，檢查另一個進程是否在臨界區(qū)；在退出區(qū)修改本

34、進程在臨界區(qū)的標志；,int flag[2] = {0,0}; int turn;/*進程Pi的程序結(jié)構(gòu)，i=0,1 */turn = i; flag[i]=1;while (flag[j])if (turn == j){flag[i]=0; /*使進程Pj進入臨界區(qū)*/while (turn == j) ; /*循環(huán)等待*/flag[i] = 1;}critical section;turn =

35、j; flag[i]=0;remainder section;/*當Pi為P0時，i=0,j=1；當Pi為P1時,i=1, j=0*/,59,2.4.2 實現(xiàn)臨界區(qū)互斥的鎖操作法,加鎖 － 臨界區(qū) － 開鎖1 開、關中斷 獨占CPUi)單CPU ii)同類臨界區(qū)iii)臨界區(qū)長度 iv)互斥范圍2 鎖操作原語加鎖原語 開鎖原語其讀寫操作由一條指令完成，因而保證讀操作與寫操作不被打

36、斷；Test-and-Set指令Swap指令（或Exchange指令）,利用TS實現(xiàn)進程互斥：每個臨界資源設置一個公共布爾變量lock，初值為FALSE在進入?yún)^(qū)利用TS進行檢查：有進程在臨界區(qū)時，重復檢查；直到其它進程退出時，檢查通過；,互斥算法（TS指令）,利用Swap實現(xiàn)進程互斥：每個臨界資源設置一個公共布爾變量lock，初值為FALSE。每個進程設置一個私有布爾變量key,互斥算法（Swap指令）,62,2.4.3信號量(s

37、emaphore)機制,1 信號量和P、V操作1965年，由荷蘭學者Dijkstra提出，是一種卓有成效的進程同步機制，P、V分別是荷蘭語的test(proberen)和increment(verhogen)。信號量只能通過初始化和兩個標準的原語來訪問－－作為OS核心代碼執(zhí)行，不受進程調(diào)度的打斷初始化指定一個非負整數(shù)值，表示空閑資源總數(shù)（又稱為“資源信號量”）－－若為非負值表示當前的空閑資源數(shù)，若為負值其絕對值表示當前等待進入臨界

38、區(qū)的進程數(shù),63,P原語 wait(s)while (s<=0);/*忙等待*/s = s – 1;V原語 signal(s)s = s + 1;,一、整形信號量,64,二、 記錄型信號量機制,每個信號量*s除一個整數(shù)值s->value（計數(shù)）外，還有一個進程等待隊列s->ptr_of_semque，其中是阻塞在該信號量的各個進程的標識typedef struct {int valu

39、e;PCB *ptr_of_semque;} Semaphore;阻塞等待P、V操作,s->value --;//表示申請一個資源;if (s->value ptr_of_semque; 阻塞調(diào)用進程;},P原語 wait(s),++s->value; //表示釋放一個資源if (s->value ptr_of_semque中取出一個進程P; 進程P進

40、入就緒隊列;},V原語通常喚醒進程等待隊列中的頭一個進程,V原語 signal(s),67,為臨界資源設置一個互斥信號量mutex(MUTual Exclusion)，其初值為{1,NULL}；在每個進程中將臨界區(qū)代碼置于P(mutex)和V(mutex)原語之間必須成對使用P和V原語：遺漏P原語則不能保證互斥訪問，遺漏V原語則不能在使用臨界資源之后將其釋放（給其他等待的進程）；P、V原語不能次序錯誤、重復或遺漏例：并發(fā)的多個售票

41、進程,,2 利用信號量實現(xiàn)互斥(P84),68,前趨關系：并發(fā)執(zhí)行的進程P1和P2中，分別有代碼C1和C2，要求C1在C2開始前完成；為每個前趨關系設置一個信號量S12，其初值為{0, NULL}非對稱同步關系,3. 利用信號量來描述同步關系,例1,例2 司機和售票員問題描述：設公共汽車上，司機和售票員的活動分別是： 司機： 售票員： 啟動車輛

42、 上下乘客 正常行車 關車門 到站停車 售票 開車門 上下乘客雙信號量對稱制約,Semaphore driver_sem = { 0, NULL}; //司機Semapho

43、re conductor_sem = { 0, NULL}; //售票員,program driver{ while (1) { driving; stopping; V(&conductor_sem}; //喚醒售票員開門 P(&driver_sem); //等待售票員關門 start a

44、car; }},program conductor{ while (1) { sell tickets; P(&conductor_sem); //等待司機停車 open the door; close the door; V(&driver_sem); //喚醒司機開車

45、 }},例3 讀者－寫者問題 (the readers-writers problem) P88問題描述：對共享資源的讀寫操作，任一時刻“寫者”最多只允許一個，而“讀者”則允許多個 （Bernstein條件）“讀－寫”互斥，“寫－寫”互斥，"讀－讀"允許雙信號量解法一 寫者饑餓解法二 寫者優(yōu)先，最多10個讀者,采用記錄型信號量機制：Semaphore rwmutex={1,NULL};

46、//寫者與其他進程互斥公共變量 readcount 表示“正在讀”的進程數(shù)，初值是0；Semaphore rmutex ={1,NULL}; //對readcount互斥訪問,Readeri（11個）{ P(&rwmutex); P(&rsem); V(&rwmutex); read data; V(&rsem);},Writerj（2個）{ int i; P(&

47、rwmutex); for (i=1;i<=10;i++) P(&rsem); write or update data; for (i=1;i<=10;i++) V(&rsem); V(&rwmutex);},Semaphore rwmutex={1,NULL},rsem={10,NULL};,rwmutex和rsem值范圍,例4 生產(chǎn)者－消費者問題三信號量：

48、空、滿、互斥，初值如下Semaphore empty = {N, NULL};Semaphore full = { 0, NULL};Semaphore mutex = {1, NULL};,75,2.5 進程通訊,P-V操作 低級通訊 交換信息量少交換信息量多高級通訊2.5.1 消息緩沖區(qū)通訊Hansen Windows GetMessage,PeekMessageTranslateMessage, Dispatch

49、MessageUNIX例 p96~98server.c client.c,2.5.2 管道通訊 (pipe)無名(父子) 有名(FIFO,進程間)UNIX fork( )函數(shù), 產(chǎn)生子進程調(diào)用后, 父子進程均從下一條語句繼續(xù)執(zhí)行#include #include #include main(){ fork(); printf(“Hello\n”); fork(); printf(“world\n”

50、);},例 無名 父子進程通訊 wait, exit 同步文件描述符： fdp[0]-讀， fdp[1]-寫pipe函數(shù)調(diào)用 產(chǎn)生pipe.c2.5.3 共享存儲段2.5.4 網(wǎng)絡通訊,78,2.6 死鎖,若干進程競爭使用資源,每個進程都得不到繼續(xù)執(zhí)行的資源,結(jié)果都處于阻塞狀態(tài)。產(chǎn)生死鎖的原因：系統(tǒng)資源不足進程運行順序不合適,I/O設備共享時的死鎖情況,進程推進順序?qū)λ梨i的影響,81,2.6.1 死鎖必要條件,資源非

51、共享，互斥控制非剝奪控制逐次請求，不釋放已分配資源進程資源循環(huán)鏈例 P、V操作不當 圖2.43例 內(nèi)存分配圖2.44,S1 S2 初值為0,83,2.6.2 預防,死鎖4條件之一不成立假脫機 共享搶占 （級別）資源靜態(tài)分配，一次性分配資源分配次序,84,2.6.3 避免（預測）,1) 銀行家算法最壞可能，過于保守2) Hebemann算法 進程有向圖,85,2.6.4 檢測進程資源循環(huán)鏈進

52、程資源有向圖 檢測化簡后，是否有環(huán)存在2.6.5 解除 （恢復）刪除進程，撤銷剝奪資源,86,作業(yè)管理,功能：控制和調(diào)度作業(yè)的狀態(tài)：提交、后備、執(zhí)行、完成， 作業(yè)調(diào)度程序作業(yè)控制聯(lián)機脫機作業(yè)調(diào)度功能：作業(yè)情況JCB，算法，分配資源，回收資源算法,1、現(xiàn)代操作系統(tǒng)的最基本特征是( )。 A．多道程序設計 B．中斷處理 C．并發(fā)和共享

53、 D．實現(xiàn)分時與實時處理2、允許多個用戶以交互方式使用計算機的操作系統(tǒng)，稱為( )。 A. 批處理操作系統(tǒng) B. 分時操作系統(tǒng) C. 實時操作系統(tǒng) D. 多處理機操作系統(tǒng)3、正在執(zhí)行的進程由于其時間片用完，此時其進程應從執(zhí)行態(tài)變?yōu)? )態(tài)。 A. 就緒 B. 等待 C. 運行 D. 阻塞4、進程與程序之間有密切聯(lián)系，但又是不同的概念。二者的一個本質(zhì)區(qū)

54、別是( )。 A．程序是靜態(tài)概念，進程是動態(tài)概念 B．程序是動態(tài)概念，進程是靜態(tài)概念 C．程序保存在文件中，進程存放在內(nèi)存中 D．程序順序執(zhí)行，進程并發(fā)執(zhí)行,5、若進程沒有掛起狀態(tài)，下列進程狀態(tài)的轉(zhuǎn)換中，哪一個是不正確的( )。 A．就緒一執(zhí)行 B．執(zhí)行一就緒 C．就緒一阻塞 D．阻塞一就緒 6、在引入線程概念的操作系統(tǒng)中，系統(tǒng)進行資源分配的基本單位是(