【文章內(nèi)容簡介】 相應(yīng)資源一直被它占有，這就破壞了產(chǎn)生死鎖的部分分配條件。2．破壞環(huán)路條件 對系統(tǒng)提供的每一項資源，由系統(tǒng)設(shè)計者將它們按類型進(jìn)行線性排隊，并賦予不同的序號。3．資源受控動態(tài)分配 為了避免死鎖發(fā)生，操作系統(tǒng)必須根據(jù)預(yù)先掌握的關(guān)于資源用法的信息控制資源分配，使得共同進(jìn)展路徑的下一步不致于進(jìn)入危險區(qū)，即只要有產(chǎn)生死鎖的可能性，就避免把一種資源分配給一個進(jìn)程。 死鎖的檢測和恢復(fù) 1．資源剝奪法 （1）還原算法。即恢復(fù)計算結(jié)果和狀態(tài)。（2）建立檢查點主要是用來恢復(fù)分配前的狀態(tài)。 2．撤消進(jìn)程法 按一定的順序中止進(jìn)程序列，直至已釋放到有足夠的資源來完成剩下的資源為止。第四章，一般都要經(jīng)歷提交、收容、執(zhí)行和完成四個狀態(tài)。一個作業(yè)在其處于從輸入設(shè)備進(jìn)入外部存儲設(shè)備的過程成為提交狀態(tài)。處于提交狀態(tài)的作業(yè)，因其信息尚未全部進(jìn)入系統(tǒng)，所以不能被調(diào)用程序選取。收容狀態(tài)也稱為后備狀態(tài)，輸入管理系統(tǒng)不斷地將作業(yè)輸入到外存中對應(yīng)部分（或稱輸入井，即專門用來存放待處理作業(yè)信息的一組外存分區(qū)）。若一個作業(yè)的全部信息已全部被輸入進(jìn)輸入井，那么，在它還未被調(diào)度去執(zhí)行之前，該作業(yè)處于收容狀態(tài)。作業(yè)調(diào)度程序從后備作業(yè)中選取若干作業(yè)到內(nèi)存投入運行。它為被選中作業(yè)建立進(jìn)程并分配必要的資源，這時，這些被選中的作業(yè)處于執(zhí)行狀態(tài)。當(dāng)作業(yè)運行完畢，但它所占用的資源尚未全部被系統(tǒng)收回時，該作業(yè)處于完成狀態(tài)。一般來說，處理機(jī)調(diào)度可分為4級：作業(yè)調(diào)度、交換調(diào)度、進(jìn)程調(diào)度、線程調(diào)度。 作業(yè)調(diào)度：又稱宏觀調(diào)度或高級調(diào)度，其主要任務(wù)是按一定的原則對外存輸入井上的大量后備作業(yè)進(jìn)行選擇，給選出的作業(yè)分配內(nèi)存、輸入輸出設(shè)備等必要的資源，并建立相應(yīng)的根程序，以使該作業(yè)的進(jìn)程獲得競爭處理機(jī)的權(quán)利，另外，當(dāng)該作業(yè)執(zhí)行完畢時，還負(fù)責(zé)回收系統(tǒng)資源。交換調(diào)度：又稱中級調(diào)度，其主要任務(wù)是按照給定的原則和策略，將處于外存交換區(qū)中的就緒狀態(tài)或就緒等待狀態(tài)的進(jìn)程調(diào)入內(nèi)存，或把處于內(nèi)存就緒狀態(tài)或內(nèi)存等待狀態(tài)的進(jìn)程交換到外存交換區(qū)。交換調(diào)度主要涉及內(nèi)存的管理和擴(kuò)充，一般將它歸在存儲管理之中。進(jìn)程調(diào)度：又稱微觀調(diào)度或低級調(diào)度，其主要任務(wù)是按照某種策略和方法選取一個處于就緒狀態(tài)的進(jìn)程占用處理機(jī)。只有在多道批處理系統(tǒng)中才有作業(yè)調(diào)度，而在分時和實時系統(tǒng)中一般只有進(jìn)程調(diào)度、交換調(diào)度和線程調(diào)度。這是因為在分時和實時系統(tǒng)中，為了縮短響應(yīng)時間或為了滿足用戶需求的截止時間，作業(yè)不是建立在外存中，而是直接建立在內(nèi)存中。作業(yè)調(diào)度的功能：（1）記錄系統(tǒng)中各作業(yè)的狀況，包括執(zhí)行階段的有關(guān)情況。通常，系統(tǒng)為每個作業(yè)建立一個作業(yè)控制表JCB記錄這些有關(guān)信息。作業(yè)控制塊JCB：在作業(yè)調(diào)度的過程中記錄作業(yè)各方面的信息。它隨作業(yè)的創(chuàng)建而產(chǎn)生，隨作業(yè)的撤消而被清除。（2）從后備隊列中選取一部分作業(yè)投入執(zhí)行（3）為被選中的作業(yè)做好執(zhí)行前的準(zhǔn)備工作。（4）在作業(yè)執(zhí)行結(jié)束時做好善后處理工作。作業(yè)調(diào)度目標(biāo)：（1） 對所有作業(yè)應(yīng)該是公平合理的。（2） 應(yīng)使設(shè)備有高的利用率。（3） 每天執(zhí)行盡可能多的作業(yè)（4） 有快的響應(yīng)時間對于批處理系統(tǒng)，作業(yè)的平均周轉(zhuǎn)時間或平均帶權(quán)周轉(zhuǎn)時間，被作為衡量調(diào)度算法優(yōu)劣的標(biāo)準(zhǔn)；對于分時系統(tǒng)和實時系統(tǒng)，外加平均響應(yīng)時間作為衡量調(diào)度算法優(yōu)劣的標(biāo)準(zhǔn)★(1)周轉(zhuǎn)時間：作業(yè)i從提交時刻到完成時刻稱為作業(yè)的周轉(zhuǎn)時間。Ti = Tei TsiTei為作業(yè)i的完成時間，Tsi為作業(yè)的提交時間一個作業(yè)的周轉(zhuǎn)時間說明了該作業(yè)在系統(tǒng)內(nèi)停留的時間,包含兩部分：一是等待時間；二為執(zhí)行時間 Ti = Twi + TriTwi主要是指作業(yè)i由后備狀態(tài)到執(zhí)行狀態(tài)的等待時間，它不包括作業(yè)進(jìn)入執(zhí)行狀態(tài)后的等待時間?！镆慌鳂I(yè)的平均周轉(zhuǎn)時間為： n T==1/n ∑ Ti i=1★帶權(quán)周轉(zhuǎn)時間Wi=Ti/Tri Ti作業(yè)周轉(zhuǎn)時間 Tri作業(yè)執(zhí)行時間★一批作業(yè)的平均帶權(quán)周轉(zhuǎn)時間為 n W=1/n ∑ Wi i=13．進(jìn)程調(diào)度進(jìn)程調(diào)度的功能：①用PCB塊記錄系統(tǒng)中所有進(jìn)程的執(zhí)行情況②按照一定的調(diào)度算法，選擇一個處于就緒狀態(tài)的進(jìn)程，給它分配處理機(jī)(這是最重要的功能)③實施進(jìn)行進(jìn)程上下文的切換引起進(jìn)程調(diào)度的原因：（1） 正在執(zhí)行的進(jìn)程執(zhí)行完畢。這時，如果不選擇新的就緒進(jìn)程執(zhí)行，將浪費處理機(jī)資源。（2） 執(zhí)行中進(jìn)程自己調(diào)用阻塞原語將自己阻塞起來進(jìn)入睡眠等待狀態(tài)。（3） 執(zhí)行中進(jìn)程調(diào)用了P原語操作，從而因資源不足而被阻塞；或調(diào)用了V原語激活了等待資源的進(jìn)程隊列。（4） 執(zhí)行中進(jìn)程提出了I/O請求后被阻塞。（5） 在分時系統(tǒng)中時間片已經(jīng)用完。（6） 在執(zhí)行完系統(tǒng)調(diào)用，在系統(tǒng)程序返回用戶進(jìn)程，可認(rèn)為系統(tǒng)進(jìn)程執(zhí)行完畢，從而可調(diào)度選擇一新的用戶程序執(zhí)行。以上都是CPU執(zhí)行不可剝奪方式下做引起的進(jìn)程調(diào)度的原因，在CPU執(zhí)行方式是可剝奪時，還有：（7） 就緒隊列中的某進(jìn)程的優(yōu)先級變得高于當(dāng)前執(zhí)行進(jìn)程的優(yōu)先級，從而也將發(fā)生進(jìn)程調(diào)度。可剝奪方式：即就緒隊列中一旦有優(yōu)先級高于當(dāng)前進(jìn)程優(yōu)先級的進(jìn)程存在時，便立即發(fā)生進(jìn)程調(diào)度，轉(zhuǎn)讓處理機(jī)。非剝奪方式（不可剝奪方式）：即使在就緒隊列存在有優(yōu)先級高于當(dāng)前執(zhí)行進(jìn)程時，當(dāng)前進(jìn)程仍將繼續(xù)占有處理機(jī)，直到該進(jìn)程因自己調(diào)度調(diào)用原語操作或、等待I/O進(jìn)入阻塞狀態(tài)或時間片用完時才重新發(fā)生調(diào)度讓出處理機(jī)。進(jìn)程調(diào)度性能評價（1）進(jìn)程調(diào)度性能是衡量操作系統(tǒng)性能的一個重要指標(biāo)（2）在大多數(shù)情況下，利用測試或模擬系統(tǒng)響應(yīng)時間的方法來評價進(jìn)程調(diào)度的性能★①先來先服務(wù)(FCFS)算法將用戶作業(yè)和就緒進(jìn)程按提交順序或變成就緒狀態(tài)的先后排成隊列，并按照先來先服務(wù)的方式進(jìn)行調(diào)度處理。優(yōu)點：在一般意義下是公平的，即每個作業(yè)或進(jìn)程都按照它們在隊列中等待時間長短來決定它們是否優(yōu)先享受服務(wù)。缺點：對于那些執(zhí)行時間較短的作業(yè)或進(jìn)程來說，如果它們在某些執(zhí)行時間很長的作業(yè)或進(jìn)程之后到達(dá)，則它們等待很長時間。②(時間片)輪轉(zhuǎn)法(RR)算法描述：就緒隊列按進(jìn)程到達(dá)的時間來排列。處理機(jī)的時間被分為固定大小的時間片。調(diào)度程序總是選擇就緒隊列中的第一個進(jìn)程。一個執(zhí)行進(jìn)程如果在用完一個時間片后還沒有完成其任務(wù)，它就自動釋放處理機(jī)回到就緒隊列的末尾重新排隊，等待下一次被調(diào)度。缺點：只能用來分配那些可搶占資源，而且這種算法只能用于進(jìn)程調(diào)度，不能用于作業(yè)調(diào)度（作業(yè)調(diào)度包含了不可搶占資源）。 時間片的選取非常重要，時間片長度的選擇會直接影響系統(tǒng)開銷和響應(yīng)時間。如果時間片長度過短，則調(diào)度程序剝奪處理機(jī)的次數(shù)增多，這將使進(jìn)程上下文交換次數(shù)也大大增加，加重了系統(tǒng)開銷。如果時間片長度選擇過長(大)，大到一個進(jìn)程足以完成其全部運行工作所需的時間，那么時間片輪轉(zhuǎn)法就退化為先來先服務(wù)策略了。最佳的時間片量值應(yīng)能使分時用戶得到好的響應(yīng)時間。時間片的確定在輪轉(zhuǎn)法中，時間片長度q根據(jù)系統(tǒng)對響應(yīng)時間的要求R和就緒隊列中所能容納的最大進(jìn)程數(shù)Nmax確定的。 q=R/Nmax一種改進(jìn)的方法就是每當(dāng)一輪調(diào)度開始時，系統(tǒng)根據(jù)就緒隊列中當(dāng)前的進(jìn)程數(shù)計算一次q，作為新一輪調(diào)度的時間片。③多級反饋輪轉(zhuǎn)法(進(jìn)程調(diào)度)（1）在時間片輪轉(zhuǎn)法中設(shè)置三個就緒隊列（2）每個隊列建立時按FCFS排列，同一隊列中進(jìn)程的優(yōu)先級相同，不同隊列具有不同的優(yōu)先級優(yōu)先級高的隊列中進(jìn)程的時間片短，優(yōu)先級低的隊列中進(jìn)程的時間片長。（3）進(jìn)程調(diào)度時，先調(diào)度高優(yōu)先級就緒隊列中的進(jìn)程，當(dāng)高優(yōu)先級就緒隊列為空時才調(diào)度優(yōu)先級低的就緒隊列中的進(jìn)程（4）一個進(jìn)程在執(zhí)行過程中要經(jīng)歷不同的就緒隊列④優(yōu)先級法算法描述：按照某種原則給作業(yè)或進(jìn)程確定一個優(yōu)先級，進(jìn)程的就緒隊列或作業(yè)的后備隊列按對象的優(yōu)先級進(jìn)行排列，高前低后。對象進(jìn)入隊列是插入。當(dāng)調(diào)度發(fā)生時，排列在最前面的進(jìn)程或作業(yè)被調(diào)度。確定優(yōu)先級的方法有兩類：動態(tài)法和靜態(tài)法靜態(tài)法是根據(jù)作業(yè)或進(jìn)程的靜態(tài)特性，在作業(yè)或進(jìn)程開始執(zhí)行之前就確定它們的優(yōu)先級，一旦開始執(zhí)行后就不能改變。動態(tài)法：把作業(yè)或進(jìn)程靜態(tài)性和動態(tài)性結(jié)合起來確定作業(yè)或進(jìn)程的優(yōu)先級，隨著作業(yè)或進(jìn)程的執(zhí)行過程，優(yōu)先級不斷變化。作業(yè)調(diào)度中靜態(tài)優(yōu)先級確定原則：（1） 由用戶自己根據(jù)作業(yè)的緊急程度輸入一個適當(dāng)?shù)膬?yōu)先級（2） 由系統(tǒng)或操作員根據(jù)作業(yè)類型指定優(yōu)先級。（3） 系統(tǒng)根據(jù)作業(yè)要求資源情況確定優(yōu)先級。進(jìn)程調(diào)度靜態(tài)優(yōu)先級確定原則：（1） 按照進(jìn)程的類型給與不同的優(yōu)先級。（2） 將作業(yè)的靜態(tài)優(yōu)先級作為它所屬進(jìn)程的優(yōu)先級。由于在進(jìn)程調(diào)度中靜態(tài)優(yōu)先級確定方法的缺陷：系統(tǒng)效率低、調(diào)度性能不高，所以多采用動態(tài)的方法確定優(yōu)先級。進(jìn)程調(diào)度動態(tài)優(yōu)先級確定原則：（1） 根據(jù)進(jìn)程占有CPU時間的長短來決定。一個進(jìn)程占有處理機(jī)時間越長，則在被阻塞后再次獲得調(diào)度的優(yōu)先級越低，反之，獲得調(diào)度的可能性越大（2） 根據(jù)就緒進(jìn)程等待CPU的時間長短來決定。一個就緒進(jìn)程在就緒隊列中等待的時間越長，則它獲得調(diào)度選中的優(yōu)先級就越高。⑤最短作業(yè)優(yōu)先法SJF(作業(yè)調(diào)度)選擇那些估計需要執(zhí)行時間最短的作業(yè)投入執(zhí)行，為它們創(chuàng)建進(jìn)程和分配資源。優(yōu)點：可使得系統(tǒng)在同一時間內(nèi)處理的作業(yè)個數(shù)最多，從而吞吐量也就大于其他調(diào)度方式。缺點：對于一個不斷有作業(yè)進(jìn)入的批處理系統(tǒng)來說，最短作業(yè)優(yōu)先法有可能使得那些長作業(yè)永遠(yuǎn)得不到調(diào)度執(zhí)行的機(jī)會。⑥最高響應(yīng)比優(yōu)先法(作業(yè)調(diào)度)綜合平衡FCFS和SJF，既考慮等待時間長的作業(yè)，也照顧執(zhí)行時間短的作業(yè)。響應(yīng)比：R=(等待時間W+執(zhí)行時間T)/執(zhí)行時間T優(yōu)點：長作業(yè)有機(jī)會獲得調(diào)度執(zhí)行缺點：同一時間內(nèi)處理的作業(yè)數(shù)少于最短作業(yè)優(yōu)先法，吞吐量也小于最短作業(yè)優(yōu)先法 調(diào)度前計算響應(yīng)比，系統(tǒng)開銷增加。算法評價FCFS算法λ ：作業(yè)到達(dá)率；μ ：服務(wù)器(主機(jī))的服務(wù)率；只有當(dāng)λ μ時系統(tǒng)才是穩(wěn)定的。n：系統(tǒng)中的平均作業(yè)個數(shù)；R：系統(tǒng)響應(yīng)時間；ρ ： λ/μ，是系統(tǒng)中存在作業(yè)的概率，1ρ是系統(tǒng)中沒有作業(yè)的概率。 n= ρ/(1ρ)Little結(jié)果：n=λR；R=n/λ FCFS算法的評價： R=n/λ=ρ/(1ρ)*1/λRR算法q：時間片；k：每個進(jìn)程平均需要的時間片數(shù)，即該進(jìn)程到達(dá)等待隊列的次數(shù)；線性優(yōu)先級法的調(diào)度性能1/μ：平均服務(wù)時間，則：1/μ=kqRR算法的評價：已使用過k次時間片的進(jìn)程的響應(yīng)時間是：R(k)=ρ/(λ(1ρ)) =1/(μ(1ρ))=kq/(1ρ)FCFS方式短作業(yè)駐留時間與長作業(yè)相同，對短作業(yè)不利。輪轉(zhuǎn)法所需服務(wù)時間短的顧客響應(yīng)時間將會小于所需服務(wù)時間長的顧客響應(yīng)時間。實時調(diào)度算法分類：靜態(tài)表格驅(qū)動類、靜態(tài)優(yōu)先級驅(qū)動搶先式調(diào)度算法類、動態(tài)計劃調(diào)度算法類、盡力而為調(diào)度算法類。具有代表性的實時調(diào)度算法時限式調(diào)度法（靜態(tài)表格驅(qū)動類代表）：是一種以滿足用戶要求時限為調(diào)度原則的算法。算法描述：時限有兩種：處理開始時限和處理結(jié)束時限，在實際中可以使用任一種時限。頻率單調(diào)調(diào)度（靜態(tài)優(yōu)先級驅(qū)動搶先式調(diào)度算法類代表）：是一種被廣泛用于多周期性實時處理的調(diào)度算法。其基本原理是頻率低（周期越長）的任務(wù)優(yōu)先級越低。第五章：能接收數(shù)據(jù)和保存數(shù)據(jù)、而且能根據(jù)命令提供這些數(shù)據(jù)的裝置。存儲器分成兩類：內(nèi)存儲器（簡稱內(nèi)存、主存、物理存儲器）外存儲器（簡稱外存、輔助存儲器）虛擬存儲器：為用戶提供一種不受物理存儲器結(jié)構(gòu)和容量限制的存儲器的技術(shù)稱為虛擬存儲器，或稱虛擬存儲技術(shù)。虛擬存儲器需要大容量的外存儲器的支持，或稱物資基礎(chǔ)。程序地址：用戶編程序時所用的地址（或稱邏輯地址 、虛地址 ），基本單位可與內(nèi)存的基本單位相同，也可以不相同。程序地址空間（邏輯地址空間、虛地址空間）:用戶的程序地址的集合稱為邏輯地址空間，它的編址總是從0開始的，可以是一維線性空間，也可以是多維空間。物理地址：把內(nèi)存分成若干個大小相等的存儲單元，每個單元給一個編號，這個編號稱為內(nèi)存地址（物理地址、絕對地址、實地址），存儲單元占8位，稱作字節(jié)（byte）。物理地址空間：物理地址的集合稱為物理地址空間（主存地址空間），它是一個一維的線性空間。安排進(jìn)程的地址方法：（1） 按照物理存儲器中的位置賦予實際物理地址。好處：CPU執(zhí)行目標(biāo)代碼時的執(zhí)行速度高。壞處：由于物理存儲器的容量限制，能裝入內(nèi)存并發(fā)執(zhí)行的進(jìn)程數(shù)