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

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

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

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

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

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

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

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

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

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

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

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; 區 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 (整數型)操作的定義為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操作實現進程互斥P(s)Rjcountl|5?Rj +1界countV(s)« I «

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

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

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

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

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

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

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

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

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

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

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

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

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