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