【正文】 調(diào)度，短程調(diào)度）主要是決定就緒隊列中的哪個進程應獲得處理機，然后由分派程序（Dispatcher）分派處理機。兩種調(diào)度方式：1)非搶占方式：簡單、系統(tǒng)開銷小，實時性差 (如win31)2)搶占方式：（1）優(yōu)先權(quán)原則（2）短進程優(yōu)先原則（3）時間片原則（中程調(diào)度）：為提高系統(tǒng)吞吐量和內(nèi)存利用率而引入的一 內(nèi)外存對換功能（換出時，進程為掛起或就緒駐外存狀態(tài)） 面向用戶的準則（1）周轉(zhuǎn)時間短（常用于批處理系統(tǒng)）概念：：駐外存等待調(diào)度時間；駐內(nèi)存等待調(diào)度時間；執(zhí)行時間；阻塞時間平均周轉(zhuǎn)時間：平均帶權(quán)時間： （可見帶權(quán)w越小越好,Ts為實際服務時間。）面向系統(tǒng)的準則（1）吞吐量高（特別是批處理）：單位時間完成作業(yè)數(shù)（2）處理機利用率好：（因CPU貴，特別是大中型多用戶系統(tǒng)）（3）各類資源的平衡利用。先來先服務和短作業(yè)（進程）優(yōu)先調(diào)度算法特點：簡單，有利于長作業(yè)（進程） 即CPU繁忙性作業(yè),不利于短作業(yè)（進程）（進程）優(yōu)先調(diào)度算法：SJ(P)F提高了平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間（從而提高了系統(tǒng)吞吐量）特點：對長作業(yè)不利，有可能得不到服務估計時間不易確定 計算：帶權(quán)周轉(zhuǎn)時間=周轉(zhuǎn)時間/服務時間；完成時間：FCFS按順序完成作業(yè)，SJF完成第一個作業(yè)后選擇服務時間最短的作業(yè)依次完成；：1）非搶占式優(yōu)先權(quán)算法2）搶占式優(yōu)先權(quán)算法，實時性更好。優(yōu)先權(quán)類型：1）靜態(tài)優(yōu)先權(quán)：進程優(yōu)先權(quán)在整個運行期不變。特點：簡單，但低優(yōu)先權(quán)作業(yè)可能長期不被調(diào)度（饑餓）。2）動態(tài)優(yōu)先權(quán)：進程優(yōu)先級可隨進程的推進或等待時間的增加而改變。優(yōu)點：長短兼顧 缺點：需經(jīng)常計算各進程優(yōu)先級高響應比優(yōu)先調(diào)度算法：（短作業(yè)RP大）響應比Rp=（Tw+Ts）/Ts=（等待時間+要求服務時間）/要求服務時間=優(yōu)先權(quán)=響應時間/要求服務時間：系統(tǒng)能在給定的時間內(nèi)響應所有用戶的請求時間片大小的確定：太大：退化為FCFS；太?。合到y(tǒng)開銷過大作業(yè)名ABCDE平均到達時間01234服務時間43424RRq＝1完成時間151216917周轉(zhuǎn)時間151114613帶權(quán)周轉(zhuǎn)時間3RRq＝4完成時間47111317周轉(zhuǎn)時間4691013帶權(quán)周轉(zhuǎn)時間125時間片大小不同時帶權(quán)周轉(zhuǎn)時間于完成時間也不同；實時調(diào)度：對用戶的實時響應實現(xiàn)實時調(diào)度的基本條件1．提供必要的調(diào)度信息（1）就緒時間；（2）開始/完成截止時間；（3）處理時間；（4）資源要求；（5）優(yōu)先級；2．系統(tǒng)處理能力強1）剝奪方式：一般都采用此方式2）非剝奪方式（實現(xiàn)簡單）：一般應使實時任務較小，以及時放棄CPU。1）具有快速響應外部中斷能力。2）快速任務分派死鎖：指多個進程在運行過程中因爭奪資源而造成的一種僵局。產(chǎn)生死鎖的原因。競爭資源引起死鎖。產(chǎn)生死鎖的必要條件1．）互斥條件（資源的臨界性）2．）請求和保持條件3．）不剝奪條件4．）環(huán)路等待條件處理死鎖的基本方法 1．預防死鎖： 破壞4個條件之一：有效，使資源利用率低。2．避免死鎖：防止進入不安全態(tài)。3．檢測死鎖：檢測到死鎖再清除。4．解除死鎖：與“檢測”配套。）互斥條件是資源固有屬性，不能避免。）摒棄請求和保持條件）摒棄“不剝奪”條件，增加系統(tǒng)開銷，且進程前段工作可能失效。）摒棄“環(huán)路”條件有序資源分配法：為資源編號，申請時需按編號進行。缺點：（1）新增資源不便，（原序號已排定）（2）資源與進程使用順序不同造成浪費（3）用戶不自由在“避免死鎖”方法中的判斷條件 安全狀態(tài)：能找到安全序列的狀態(tài)為安全狀態(tài)。（系統(tǒng)按某種順序并發(fā)進程都能達到獲得最大資源而順序完成的序列為安全序列。）例：進程最大需求已分配可用P11053P242P392安全序列：p2p1p3 銀行家算法避免死鎖 available[j]=k: 系統(tǒng)現(xiàn)有Rj類資源k個；max[i,j]=k: 進程i需要Rj的最大數(shù)k個；alloc[i,j]=k: 進程i已得到Rj類資源k個； need[i,j]=k: 進程i需要Rj類資源k個有：need[i,j]= max[i,j]－alloc[i,j]（requesti 進程i請求資源數(shù)；worki：進程i執(zhí)行完后系統(tǒng)應有資源數(shù)（也即可用數(shù)）finish[i]：布爾量，表進程i能否順序完成。 ）Allocation：已分配；Available：可分配 Need：需求 ：=Available；[i]=false need=work則Finish[i]=true。=Available+work； 直到進程的Finish[i]都為true時系統(tǒng)處于安全狀態(tài)死鎖的解除1） 剝奪資源。2) 撤消進程。 第四章1. 高速緩存：是現(xiàn)代計算機結(jié)構(gòu)中的一重要部件，其容量大于或遠大于寄存器，而比內(nèi)存約小兩到三個數(shù)量級左右，從幾十KB到幾MB,訪問速度快于主存儲器.2. 磁盤緩存：本身并不是一種實際存在的存儲介質(zhì)，它依托于固定磁盤，提供對主存儲空間的擴充，即利用主存中的存儲空間，來暫存從磁盤中讀出（或?qū)懭耄┑男畔ⅰ?. 程序的裝入方式分為：絕對裝入方式：編譯后，裝入前已產(chǎn)生了絕對地址（內(nèi)存地址），裝入時不再作地址重定位,適用于單道系統(tǒng)?？芍囟ㄎ谎b入方式：靜態(tài)重定位：裝入時完成，主要工作是對相對地址中的指令和數(shù)據(jù)地址的調(diào)整過程；可重定位裝入方式在裝入后不能移動程序動態(tài)運行時裝入方式：該情況一般在執(zhí)行時才完成相對和絕對地址的轉(zhuǎn)換且有硬件的支持,能保證進程的可移動性4. 連續(xù)分配方式分為：單一連續(xù)分配：是最簡單的一種存儲管理方式，但只能用于單用戶、單任務的操作系統(tǒng)中?？砂褍?nèi)存分為系統(tǒng)和用戶兩個部分系統(tǒng)區(qū)僅提供給OS使用，通常是放在內(nèi)存的低址部分，用戶區(qū)是系統(tǒng)區(qū)以外的全部內(nèi)存空間，提供給用戶使用。固定分區(qū)分配：是最簡單的一種可運行多道程序的存儲管理方式，是將內(nèi)存用戶空間分為若干個固定大小的區(qū)域，在每個分區(qū)中只裝入一道作業(yè)，這樣把用戶空間劃分為幾個分區(qū)，便允許有多到作業(yè)并發(fā)運行。特點：簡單，有碎片（內(nèi)零頭）,浪費。劃分分區(qū)大小的方法：分區(qū)大小相等；分區(qū)大小不等。內(nèi)存分配：將分區(qū)按大小排序，建立分區(qū)使用表，并將其地址、分配標識作記錄動態(tài)分區(qū)分配：是根據(jù)進程的實際需要，動態(tài)地為之分配內(nèi)存空間。分區(qū)分配中常用的數(shù)據(jù)結(jié)構(gòu)有兩種形式：空閑分區(qū)表；空閑分區(qū)。分區(qū)分配算法：首次適應算法FF：要求：空閑分區(qū)鏈以地址遞增的次序鏈接；特點：找到第一個大小滿足的分區(qū)，劃分，有外零頭，低址內(nèi)存使用頻繁，增加系統(tǒng)開銷循環(huán)首次適應算法：從上次找到的空閑分區(qū)的下一個開始查找。特點：空閑分區(qū)分布均勻，提高了查找速度；缺乏大的空閑分區(qū)。最佳適應算法：每次分配內(nèi)存是總是把能滿足要求、又是最小的空閑區(qū)分配給作業(yè)，避免大材小用。分區(qū)按大小遞增排序；分區(qū)釋放時需插入到適當位置最壞適應算法：選一個最大的空閑區(qū)分割給作業(yè)使用。優(yōu)點：使剩下的空閑區(qū)不至太小，產(chǎn)生碎片的幾率最小對中小作業(yè)有利，查找效率高。缺點：缺乏大的空閑分區(qū)快速適應算法：按空閑分區(qū)容量分類，對每類相同容量的所有空閑分區(qū)，單獨設(shè)立一個空閑分區(qū)鏈表，管理索引表。優(yōu)點：查找效率高；缺點：算法復雜，系統(tǒng)開銷大。5. 動態(tài)分區(qū)存儲管理中主要操作（分區(qū)分配操作）：分配內(nèi)存：系統(tǒng)應用某種算法，從空閑分區(qū)鏈（表）中找到所需大小的分區(qū)回收內(nèi)存：上鄰空閑區(qū)：合并，改大小。下鄰空閑區(qū)：合并，改大小，首址。上、下鄰空閑區(qū)：合并，改大小。不鄰接，則建