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

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

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

3、進(jìn)程 圖2.2邊偏序或前趨關(guān)系 ? （Pi，Pj）Pi ? Pj,前趨關(guān)系,4,程序的執(zhí)行方式：順序執(zhí)行和并發(fā)執(zhí)行,一、程序順序執(zhí)行圖2.1 輸入I－>計(jì)算C－>打印P順序執(zhí)行的特征順序性：按照程序結(jié)構(gòu)所指定的次序（可能有分支或循環(huán)）封閉性：獨(dú)占全部資源，計(jì)算機(jī)的狀態(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,間斷(異步)性："走走停停"，一個(gè)程序可能走到中途停下來(lái)，失去原有的時(shí)序關(guān)系；失去封閉性：共享資源，受其他程序的控制邏輯的影響。如：一個(gè)程序?qū)懙酱鎯?chǔ)器中的數(shù)據(jù)可能被另一個(gè)程序修改，失去原有的不變特征。不可再現(xiàn)性：失去封閉性 －>失去可再現(xiàn)性；外界環(huán)境在程序的兩次執(zhí)行期間發(fā)生變化，失去原有的可

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

6、據(jù)不變化；最后一條保證寫的結(jié)果不丟掉。,8,四條語(yǔ)句：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,進(jìn)程的概念,各種定義一個(gè)具有一定獨(dú)立功能的程序在一個(gè)數(shù)據(jù)集合上的一次動(dòng)態(tài)執(zhí)行過程。進(jìn)程的特征動(dòng)態(tài)性：進(jìn)程具有動(dòng)態(tài)的地址空間（數(shù)量和內(nèi)容），系統(tǒng)控制信息（進(jìn)程控制塊的生成和刪除）獨(dú)立性：各進(jìn)程的地址空間相互獨(dú)立，除非采用進(jìn)程間通信手段；并發(fā)性、異步性：,10,進(jìn)程與程序的區(qū)別,進(jìn)程是動(dòng)態(tài)的，程序是靜態(tài)的：程序是有序代碼的集合；進(jìn)程是程序的執(zhí)行。通常進(jìn)程不可在計(jì)算機(jī)之間遷移；而程序通常對(duì)應(yīng)著文件、靜態(tài)和可以復(fù)制。進(jìn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

42、 上下乘客 正常行車 關(guān)車門 到站停車 售票 開車門 上下乘客雙信號(hào)量對(duì)稱制約,Semaphore driver_sem = { 0, NULL}; //司機(jī)Semapho

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

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

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

46、//寫者與其他進(jìn)程互斥公共變量 readcount 表示“正在讀”的進(jìn)程數(shù)，初值是0；Semaphore rmutex ={1,NULL}; //對(duì)readcount互斥訪問,Readeri（11個(gè)）{ P(&rwmutex); P(&rsem); V(&rwmutex); read data; V(&rsem);},Writerj（2個(gè)）{ 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)者－消費(fèi)者問題三信號(hào)量：

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

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

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

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

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

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

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