軟件技術(shù)基礎：操作系統(tǒng)處理器管理

1、3.3 處理器管理在多道程序運行時，操作系統(tǒng)對處理機的管理就是通過對進程的管理來實現(xiàn)的。代表性的進程定義：1 ） 進程是程序的一次執(zhí)行；2）進程是可以和別的計算并發(fā)執(zhí)行的計算；3）進程可定義為一個數(shù)據(jù)結(jié)構(gòu)及能在其上進行操作的一個程序；4）進程是一個程序及其數(shù)據(jù)在處理機上執(zhí)行時所發(fā)生的活動；5）進程是程序在一個數(shù)據(jù)集合上運行的過程，它是系統(tǒng)進行資源分配和調(diào)度的一個獨立單 位。2 .3.1 基本概念與術(shù)語1.作業(yè)和進程作業(yè)是從事物處理看工作的處理過程。進程是從系統(tǒng)處理看工作的處理過程。例：醫(yī)生看病，病人看病需要掛號、預約、就診、驗血、做 CT,就診、取藥等作業(yè)。醫(yī)生診斷過程就是進程。就診的環(huán)節(jié)，病

2、人稱為作業(yè)，醫(yī)生稱為進程診療室就是CPU（ 1 ）作業(yè)、作業(yè)步一個作業(yè)是指在一次應用業(yè)務處理過程中， 從輸入開始到輸出結(jié)束，用戶要求計算機所做的有關該次業(yè)務處理的全部工作。作業(yè)由不同的順序相連的作業(yè)步組成。 作業(yè)步是在一個作業(yè)的處理過程中，計算機所做的相對獨立的工作。（ 2）進程和程序進程與程序的關系? 程序是指令的有序集合，其本身沒有任何運行的含義，是一個靜態(tài)的概念。而進程是程序在處理機上的一次執(zhí)行過程，它是一個動態(tài)的概念。? 程序可以作為一種軟件資料長期存在，而進程是有一定生命期的。程序是永久的，進程是暫時的。? 進程更能真實地描述并發(fā)，而程序不能；進程是由程序和數(shù)據(jù)兩部分組成的。? 進程

3、具有創(chuàng)建其他進程的功能，而程序沒有。? 同一程序同時運行于若干個數(shù)據(jù)集合上，它將屬于若干個不同的進程。也就是說同一程序可以對應多個進程。特權(quán)指令、處理機狀態(tài)特權(quán)指令：只能由操作系統(tǒng)使用非特權(quán)指令：供一般用戶使用管態(tài)（主態(tài)、執(zhí)行狀態(tài)）：此時處理器執(zhí)行特權(quán)指令。目態(tài)（算態(tài)、題目狀態(tài)）：此時處理器處于用戶狀態(tài)。3處理器管理3.4.1 處理機調(diào)度的層次1 . 高級調(diào)度高級調(diào)度又稱為作業(yè)調(diào)度或宏觀調(diào)度。其主要功能是根據(jù)一定的算法，從輸入的一批任務（作業(yè)）中選出若干個作業(yè)，分配必要的資源，如內(nèi)存、外設等，為它建立相應的用戶作業(yè)進程和為其服務的系統(tǒng)進程（如輸入/輸出進程），最后把它們的程序和數(shù)據(jù)調(diào)入內(nèi)存，等

4、待進程調(diào)度程序?qū)ζ鋱?zhí)行調(diào)度，并在作業(yè)完成后作善后處理工作。2 .中級調(diào)度中級調(diào)度涉及進程在內(nèi)外存間的交換。為緩解內(nèi)存緊張問題，在許多系統(tǒng)中設立了中級調(diào)度。中級調(diào)度的主要功能是在內(nèi)存使用緊張時，將一些暫時不能運行的進程從內(nèi)存對換到外存上等待。以后，當內(nèi)存有足夠的空閑空間時，再將合適的進程重新?lián)Q入內(nèi)存，等待進程調(diào)度。引入中級調(diào)度的主要目的是為了提高內(nèi)存的利用率和系統(tǒng)吞吐量。3 .低級調(diào)度低級調(diào)度又稱進程調(diào)度或微觀調(diào)度，其主要功能是根據(jù)一定的算法，將 CPU分派給就緒進程隊列中的一個進程。執(zhí)行低級調(diào)度功能的程序稱為進程調(diào)度程序，由它實現(xiàn)CPU在進程間的切換。進程調(diào)度是操作系統(tǒng)中最基本的一種調(diào)度，在一

5、般的操作系統(tǒng)中都必須有進程調(diào)度，而且它的策略的優(yōu)劣直接影響整個系統(tǒng)的性能。時間片到作業(yè)調(diào)度!就緒隊列作業(yè)交互式用戶中級制度!就緒，掛起隊列阻塞，掛起隊列事件發(fā)生阻塞隊列進程調(diào)度CPU進程完成）中級調(diào)度等待事件4 .3.2作業(yè)調(diào)度1作業(yè)狀態(tài)轉(zhuǎn)換及作業(yè)控制塊提交狀態(tài)：一個作業(yè)被提交給機房后或用戶通過終端鍵盤向計算機鍵入其作業(yè)時所處的狀 態(tài)后備狀態(tài)（收容狀態(tài)）：作業(yè)的全部信息都已通過輸入機輸入，并由操作系統(tǒng)將其存在磁盤 的某些分區(qū)（存放作業(yè)的輸入井）中等待運行。運行狀態(tài)：作業(yè)一旦被作業(yè)調(diào)度程序選中而被送入主存中投入運行。完成狀態(tài)：作業(yè)完成其全部運行，釋放出其所占用的全部資源。準備退出系統(tǒng)時的作業(yè)。作

6、業(yè)控制塊1)2)3)4)5)6)7)作業(yè)標識作業(yè)名估計運行時間優(yōu)先級作業(yè)創(chuàng)建時間作業(yè)狀態(tài)作業(yè)對其他資源的要求2.作業(yè)調(diào)度的功能通常作業(yè)調(diào)度程序要完成以下的工作:(1)(2)(3)(4)按照某種調(diào)度算法，從作業(yè)隊列中選取 作業(yè)進入內(nèi)存。調(diào)用存儲管理和設備管理程序，為選中 的作業(yè)分配內(nèi)存和外設。為選中的作業(yè)建立相應的進程。作業(yè)運行完畢時回收該作業(yè)站用的資源, 程控制塊）與相應的進程。作業(yè)基本情況描述作叱控制描述作業(yè)資掘要求描述要求處理時間內(nèi)存空間外設類型和數(shù)量 處理機優(yōu)先級 庫函數(shù)或?qū)嵱贸绦?等等用戶名作業(yè)務使用悟言名允許最大處理時間 等等控制方式 操作順序 出借處理 等等輸出必要的信息，撤消該作

7、業(yè)的JCB (進1)2)3)4)5)(1)(2)先來先服務算法基于優(yōu)先級的調(diào)度算法 優(yōu)先數(shù)=（等待時間）小作業(yè)可能回等待時間比較長。2-（要求運行時間）-輸出量(3)3.3.3分時和優(yōu)先級相結(jié)合的作業(yè)調(diào)度 進程調(diào)度3.作業(yè)調(diào)度算法調(diào)度算法的設計原則公平提高資源利用率 對資源的均衡使用 提高該系統(tǒng)的吞吐量響應時間短幾種調(diào)度算法:1 .進程的狀態(tài)轉(zhuǎn)換和進程控制塊1.進程的三種基本狀態(tài)所以又稱它進程在運行過程中有 3種基本狀態(tài)。這些狀態(tài)與系統(tǒng)調(diào)度占有處理機密切相關。 們?yōu)檫M程調(diào)度狀態(tài)。運行狀態(tài)（Running）當一個進程已分配到處理機，它的程序正由處理機執(zhí)行時，稱此進程處于執(zhí)行狀態(tài)。就緒狀態(tài)（Rea

8、dy）如果進程已具備執(zhí)行條件，但是因為處理機已由其他進程占用，暫時不能執(zhí)行而等待分配處理機，稱此為就緒狀態(tài)。等待狀態(tài)（ Blocked ，阻塞狀態(tài)）進程因等待某一事件（如等待某一輸入，輸出操作完成）而暫時不能運行的狀態(tài)稱為等待狀態(tài)，此時即使CPU 空閑，它也無法使用。進程控制塊的組成：進程名特征信息進程狀態(tài)信息調(diào)度優(yōu)先權(quán)通信信息現(xiàn)場保護區(qū)資源需求進程實體信息族系關系其他信息2 .進程控制進程控制：系統(tǒng)使用一些具有特定功能的程序段來撤消進程以及完成進程各狀態(tài)間的轉(zhuǎn)換，從而達到多進程高效率并發(fā)執(zhí)行和協(xié)調(diào)，實現(xiàn)資源共享的目的。這種控制是通過原語來實現(xiàn)的。原語：是機器指令的延伸，是由若干條機器指令構(gòu)成

9、的用以完成特定功能的一段程序。原語是操作系統(tǒng)設計的、不可中斷的程序，即具有原子性的程序，它用于實現(xiàn)某種獨立功能并可以被其他進程調(diào)用。為保證操作的正確性，原語在執(zhí)行期間是不可分割的，在許多機器中為了實現(xiàn)上的方便，規(guī)定在執(zhí)行原語操作時，要屏蔽中斷，以保證原語操作的不可分割性。用于進程控制的原語有：1 .進程創(chuàng)建原語2 .進程調(diào)度原語3 .進程阻塞原語（進程等待原語）4 .進程喚醒原語5 .進程撤銷原語3 .進程調(diào)度算法（1 ）優(yōu)先數(shù)法（2） 輪轉(zhuǎn)調(diào)度法（3） 分級調(diào)度法（4） 多道程序并發(fā)運行出現(xiàn)的問題1 .進程的同步和互斥（1） 同步與互斥進程之間的相互制約關系由于進程是并發(fā)執(zhí)行的，多個進程之間

10、必然存在著各種形式的制約關系。一般來說，并發(fā)進程之間存在兩種形式的制約關系。1 ）資源共享關系，又稱為間接相互制約關系，指進程之間本來彼此無關，但因為共享系統(tǒng)資源，如CPU 、內(nèi)存、I/O 設備等而產(chǎn)生的相互制約關系。2)進程合作關系，又稱為直接相互制約關系，指多個進程之間具有合作關系，用于完成 共同的任務，如同一個作業(yè)的輸入、計算、輸出進程之間必然是相互合作的關系，他們必須按照一定的次序運行。所謂進程同步，是指對多個相關進程在執(zhí)行次序上的協(xié)調(diào)，操作系統(tǒng)中用于保證這種協(xié)調(diào)關系的相應機制稱為進程同步機制。對于資源共享關系的進程，應該保證多個并發(fā)進程互斥訪問臨界資源；而對于相互合作的進程，應該保證

11、他們在執(zhí)行次序上的協(xié)調(diào)。臨界資源臨界資源是依次只能被一個進程訪問的資源。獨占設備、內(nèi)存中的公共數(shù)據(jù)結(jié)構(gòu)、 公共變量等都是臨界資源。臨界區(qū)在并發(fā)進程中，對共享變量操作的那段程序叫臨界區(qū)。進程互斥一組并發(fā)進程中的一個或多個程序段，因共享某一公有資源而導致它們必須以一個不 允許交叉執(zhí)行的單位執(zhí)行。即不允許兩個以上的共享該資源的并發(fā)進程同時進入臨界區(qū)稱為 互斥。例如：進程pl, p2都需要使用打印機，如果讓它們同時使用，則兩個進程的輸出交織在 一起，打印出的結(jié)果無法使用。 為了解決這一問題，進程使用之前先要提出申請，一旦系統(tǒng)將打印機分配給它，就一直由它獨占使用，其它申請使用打印機的進程則必須等待。例如

12、：Pi：Ricount;P2R2-count;Pi：Ri-Ri +1;count Ri；P2R2JR2 +1;count JR2；雖然Pi, P2P都又count作了加procedure T1(x)var x:integer ；beginread(x);臨If x>=1-界then x:=x-1; 區(qū) write(x)；end;1,但count中只增加了 1。： p, 卜 6/procedure T2(x) var x:integer ； begin正-g .read(x);臨Aend;1.2.3.4.5.(2)解決同步與互斥的工具P-V操作對彳t號量s (整數(shù)型)操作的定義為P操彳P(

13、s)ss-1If(s<0)thenstatus(q) -"blocked ”將進程 q 置為"阻塞"/Insert(Q,q)將q插入阻塞隊列中ReturnV操彳V(s)1. . s -s+12. If(s<=0)then3. remove(Q,R)/將R移出阻塞隊列 Q4. status(R) -"ready”將 R 置為"就緒"/5. Insert(RL,R)/將R插入就緒隊列中 RL/6. Return(3)用P-V操作實現(xiàn)進程互斥P(s)Rjcountl|5?Rj +1界countV(s)« I «

14、;p_臨+1 界count'*-R；V(s)(4)用P-V操作實現(xiàn)進程同步1)非對稱制約如果進程Pi在執(zhí)彳T到L1處從進程P2獲取某些信息后才能繼續(xù)執(zhí)行，而這些信息卻是P2到達L2處后才能提供，為此著兩個進程必須采用如下方式進行同步：IIL1:產(chǎn)生信息港取信息L：V(s)> ll>> V> V設置s=0,在進程P2尚未完成V(s)操作之前，進程 Pi只能處于等待狀態(tài)。2)雙向制約一生產(chǎn)者和消費者問題防止生產(chǎn)者將物品放入已滿的緩沖區(qū)中，同時也禁止消費者從空緩沖區(qū)中取物品。生產(chǎn)者消費者口： 生產(chǎn)物品6：取內(nèi)P國)從皴沖區(qū)取物品將物品放入綾沖區(qū)V(5L)VCW消費物品

15、Goto LiGato Ci一個緩沖區(qū)時設置初值 & =1 , S2=0。n個緩沖區(qū)時設置初值 S1=n, S2=0O2 .進程通信(1)直接通信方式。發(fā)送進程直接把消息發(fā)送給接收者，并將它掛在接收進程的消息緩沖 隊列上。接收進程從消息緩沖隊列中取得消息，這種通信方式也稱為消息緩沖通信。,接收進程從中取得消息。(2)間接通信。發(fā)送進程將消息發(fā)送到某種中間實體中(信箱) 這種通信方式也稱信箱通信。在網(wǎng)絡中稱為電子郵件系統(tǒng)。3 .死鎖(1)死鎖的原因和必要條件死鎖產(chǎn)生的原因可歸結(jié)為如下兩點：(1)資源有限。當系統(tǒng)中多個進程共享資源，如打印機、公用隊列等，其數(shù)目不足以滿足諸進程的需要，會引起

16、進程對資源的競爭而產(chǎn)生死鎖。(2)并發(fā)進程間的推進順序不當。進程在運行過程中，請求和釋放資源的順序不當，也會 導致產(chǎn)生進程死鎖。得到尺 得到S 釋放及 釋放三,l,_J申請到RA的進度申請到S死鎖的必要條件：互斥條件：涉及的資源是非共享的。不剝奪條件：不能強行剝奪進程擁有的資源。部分分配條件：進程在等待一新資源時繼續(xù)占有 已分配的資源。環(huán)路條件：存在一種進程的循環(huán)鏈， 鏈中的每一 個進程已獲得的資源同時被鏈中的下一個進程 所請求。(2)死鎖的預防通過破壞死鎖存在的 (4個)必要條件來防止死鎖發(fā) 生。(1)破壞互斥條件如果允許系統(tǒng)資源都能共享使用，則系統(tǒng)不會進 入死鎖狀態(tài)。但這種方法不是切實可行

17、的。因為有 資源若是共享使用。 例如：打印機在多進程打印， 能每個進程打印一行，則無法保證其正確性。又如， 對臨界資源的訪問就必須互斥進行。(2)破壞占有等待(二個方法)方法一：進程申請到它所需要的所有資源后，才能開始運行，又稱預先靜態(tài)分配法。例如，一個制表打印進程，需共有打印機，才能運行。此方法雖可保證無死鎖，但是a.資源的利用率低(在程序運行中，打印機空閑)；b.由于所需資源不能在一次中得到全部滿足，而使 作業(yè)無限期延長。方法二：進程提出申請資源前必須釋放已占有的一切資源。這些雖然能提高資源利用率，但要仔細進行程序設計，有時仍需提前申請資源才能保證正確性。這使用戶倍感不便。R注1要考慮無限

18、等待現(xiàn)象(其實質(zhì)與死鎖一樣)。例：P1申請12r3 ,而僅有r3。這時P2申請r3;則把r3給P2 ,某一進程Pi又釋放了 1 r2 ,而P1又因無r3,仍需等待直到餓死P1。我們應有相應的防止措施。比如按申請資源的先后次序給進程賦優(yōu)先級。這種資源預先分配的方法，適于對外存空間的分配。因為作業(yè)運行期間所需外存變化不大。（3）破壞非剝奪性條件在進程主動釋放占有的資源前即予以剝奪，也能保證系統(tǒng)不出現(xiàn)死鎖。方法一：當進程 Pi申請rj類資源時，檢查rj中有無可分配的資源，有則分配給 Pi;否則將 Pi占有的資源全部釋放進入等待狀態(tài)。方法二：當Pi申請rj時，檢查rj中有無可分配的資源，有則分配；否則

19、檢查占有rj類資源的進程Pk。若Pk處于等待資源狀態(tài)， 則剝奪Pk的rj分給Pi;若Pk處于不等待資源狀態(tài)， 則置Pi于等待資源狀態(tài) （此日Pi原占有的資源可能被剝奪。）R注1剝奪資源時，需保存中間信息。因使用資源的進程尚未主動釋放資源，這樣開銷很大。故只宜在CPU和主存這類重要資源的管理上使用。不宜剝奪臨介資源等類型資源。（4）破壞循環(huán)等待條件采用資源順序分配法，可以破壞循環(huán)等待條件。 該方法首先給系統(tǒng)中的資源編號（唯一）,即尋找一個函數(shù) F: R - N （R ：表資源類集合）即r1,r2,，riJJJF（ri） = i1 2i每個進程只能按序號由小到大的順序申請資源，而且對它所必須使用的

20、且屬于某一類的 所有資源，必須一次申請完。比如：某一進程已占有資源r1, r2,，ri,又申請ri+1 ,資源分配程序則檢查是否有對于任意j1,2,i,有F（rj） < F（rj+1）,若不滿足則拒絕分配。采用資源順序分配法，系統(tǒng)不會出現(xiàn)循環(huán)等待。因為在任何時刻，總有一個進程占有較高序號的資源，該進程繼續(xù)請示的資源必然是空閑的。故該進程可一直向前推進。（換言之，系統(tǒng)中總有進程可以順序運行完畢，這個進程執(zhí)行結(jié)束后會釋放它所占有的全部資源喚 醒等待中的進程或滿足其它進程的請求。）優(yōu)點：有序資源分配法提高了資源利用率（比靜態(tài)法）缺點：順序號與實際需要資源的順序不一致，導致資源的浪費。例：輸入機

21、1 #，打印機2#,穿孔機3#,磁盤機4#某進程使用 32,而2-3長 期擱置。事實上用戶使用的資源通常是有一定順序的。2 .避免死鎖死鎖四個必要條件 （互斥、占有等待、非剝奪、循環(huán)等待）死鎖預防是嚴格破壞4個必要條件之一，一定不出現(xiàn)死鎖；而死鎖的避免是不那么嚴格地限制死鎖必要條件的存在，其目的是提高系統(tǒng)的資源利用率。萬一當死鎖有可能出現(xiàn)需申請申源個數(shù)Qaim4已占資占個數(shù)Loan4進程used = loan + claim時，就小心避免這種情況的發(fā) 生。92C712每次進行資源分配時，需要 通過判斷系統(tǒng)狀態(tài)來決定這次 分配后，是否仍存在一條確保系 統(tǒng)不會進入死鎖狀態(tài)的路徑，否 則不予分配。避

22、免死鎖的算法：銀行家算法假設有三個進程 P、Q、R,系統(tǒng)只有某類資源共 10個，而三個進程合計申請資源數(shù)為20個。目前的分配情況如下：而系統(tǒng) 8 + 2 = 10 t T T 已分配剩 共有 Loan Cash Capital此后P、R再申請資源就不能分配了。因為現(xiàn)在只剩下 2個資源，不能滿足它們的最大要求（P:4, R:7）,如果將剩下2個分配給P或R,則會產(chǎn)生死鎖。己占還“1P 53 吐 62I皮02I21R?627然而將2個資源分給Q （只需一個）則系統(tǒng)資源回 收為4個尸44P440 3 0 =>Q可運行結(jié)R27束、桿放 R27此后可將4個資源分組P -即 Q 一 P 一 R由此可

23、見，按銀行家算法來分配資源是不會產(chǎn)生死鎖的。因為按該算法分配資源時，每次分配后總存在一個進程， 如果讓它獨立單獨運行下去，必然可獲得它所需的全部資源，也就是說它能結(jié)束。而它結(jié)束后可以歸還這類資源來滿足其它申請者的需要。這也說明了存在一個合理的系統(tǒng)狀態(tài)序列，可確保系統(tǒng)不會進入死鎖狀態(tài)的路徑。單一種類資源引出的銀行家算法的基本思想也同樣適用于多種類的資源情況：rir2小A I0b100°i110i10IE 1Q0上rlr2%r4F°212421Q11Li_1資源已分配情況最大需求還需（剩余需求）矩陣總共資源數(shù)r = (6, 3, 4, 2)已分資源數(shù)s = (5, 3, 2,

24、2)余下資源數(shù)t = (1,0, 2, 0)先做D 做完后余下資源數(shù)：t = (2, 1,2, 1)再做A 做完后余下資源數(shù)：t = (5, 1,3, 2)再做B 做完后余下資源數(shù)：t = (5, 2, 3, 2)再做C 做完后余下資源數(shù)：t = (6, 3, 4, 2)再做E 做完后余下資源數(shù)：t = (6, 3, 4, 2)的對應to(1)尋找剩余矩陣的某一未標記的行x,使得它的每一個元素都不大于向量t元素，如果找不到轉(zhuǎn)(4)。(2)對于找到的行x,表示可以滿足它，標記此進程，并將它占有的資源加到向量(3)重復上述步驟，轉(zhuǎn)(1)。(4)如果所有進程都已標記，則狀態(tài)是安全的，否則為不安全。(

25、4)死鎖的檢測和恢復矩陣簡化法還需(剩余需求)矩陣總共資源數(shù)r = (6, 3, 4, 2)已分資源數(shù)s = (5, 3, 2, 2)余下資源數(shù) t = (1,0, 2, 0)先做 D t = (2, 1,2, 1)死鎖的恢復一旦發(fā)現(xiàn)死鎖及時排除，是有關排除死鎖的研究。當前系統(tǒng)中使用的死鎖恢復辦法有兩種：(進程撤消，資源剝奪)(1)強制性地從系統(tǒng)中撤消進程，并剝奪它們的資源給剩下的進程使用。(使前面的工作全部損失)(2)使用一個有效的掛起和解掛機構(gòu)來掛起一些進程。其實質(zhì)是從被掛起的進程那里搶占資源以解除死鎖。(即可從死鎖中恢復，又使進程的損失最小)3.3.5多道程序設計基礎一并行程序設計1 .

26、順序程序設計(1)順序性：程序運行時必須嚴格按照程序所規(guī)定的順序執(zhí)行。(2)封閉性：(程序在運行時獨占全機資源)程序運行結(jié)果和它執(zhí)行的速度無關。(3)可再現(xiàn)性：當對某一程序重復執(zhí)行時，只要其初始條件相同，必將獲得相同的結(jié)果。這對程序員檢測，校正程序的錯誤帶來很大的方便。Ajf ARf耐 Bcr/Ct* CL Coy r模塊A模塊B 模塊C2 .并行程序設計(1) 并行性：多個或程序段可以并行執(zhí)行，在單處理器系統(tǒng)中即可互相切換。(并發(fā)性)(2) 共享性：系統(tǒng)中各程序不但共享硬件資源，而且共享軟件資源(程序副本和數(shù)據(jù)集)(3) 同步與互斥：這是并行性和共享性帶來的必然結(jié)果，3 .并行程序設計語言(1) 同步問題說明部分