【正文】 外存的支持。綜合應(yīng)用題1. 多道系統(tǒng)、作業(yè)調(diào)度、進程調(diào)度、搶占式調(diào)度、非搶占式調(diào)度、周轉(zhuǎn)時間、帶權(quán)周轉(zhuǎn)時間（1）概念作業(yè)調(diào)度：是指按一定的作業(yè)調(diào)度算法，從外存的后備作業(yè)隊列中選擇若干個作業(yè)調(diào)入主存的過程。進程調(diào)度：按一定的進程調(diào)度算法，從已在內(nèi)存的進程中選擇一個進程并把CPU分配給它的過程。 作業(yè)周轉(zhuǎn)時間：從作業(yè)提交進入系統(tǒng)到結(jié)束退出系統(tǒng)所經(jīng)歷的一段時間。平均周轉(zhuǎn)時間：多道作業(yè)周轉(zhuǎn)時間的平均值。系統(tǒng)吞吐量(吞吐率)：單位時間系統(tǒng)所完成的總工作量（一般用作業(yè)數(shù)表示）。（2）調(diào)度可分為三個層次：作業(yè)調(diào)度：也稱高級調(diào)度或長期調(diào)度，決定每次接收多少個作業(yè)和接納哪些作業(yè)的問題。交換調(diào)度：主要負(fù)責(zé)內(nèi)外存上的進程交換。一般通過“掛起”和“解掛”的方法來實現(xiàn)，也稱“中期調(diào)度”。進程/線程調(diào)度：將處理器分配給一個或多個進程/線程的調(diào)度方法，也稱“低級調(diào)度”和“短期調(diào)度”和“處理器調(diào)度”。帶權(quán)周轉(zhuǎn)時間=周轉(zhuǎn)時間/運行時間例1：先來先服務(wù)調(diào)度（非搶占）執(zhí)行次序提交時刻運行時間等待時間開始時刻完成時刻周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間10234作業(yè)平均周轉(zhuǎn)時間作業(yè)平均帶權(quán)周轉(zhuǎn)時間在一個單道批處理系統(tǒng)中，一組作業(yè)的提交時刻和運行時間如下表所示，請計算其平均周轉(zhuǎn)時間T和平均帶權(quán)周轉(zhuǎn)時間W。作業(yè)提交時刻運行時間1234例2：若采用搶占的 高優(yōu)先級調(diào)度算法，進程的調(diào)度次序是什么？（假定優(yōu)先數(shù)越小的作業(yè)，優(yōu)先權(quán)越高。）作業(yè)提交時刻運行時間時間： 作業(yè)： 1 2 3(2) 4 3(4) 1(3)(1)優(yōu)先數(shù)13213241例3：短作業(yè)優(yōu)先調(diào)度（短作業(yè)優(yōu)先調(diào)度算法產(chǎn)生的平均周轉(zhuǎn)時間短，系統(tǒng)吞吐量大。非搶占）作業(yè)提交時刻執(zhí)行次序提交時刻運行時間開始時刻完成時刻周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間1342作業(yè)平均周轉(zhuǎn)時間作業(yè)平均帶權(quán)周轉(zhuǎn)時間運行時間1234例4：最短剩余時間優(yōu)先調(diào)度（最短作業(yè)優(yōu)先調(diào)度算法產(chǎn)生的平均周轉(zhuǎn)時間最短，系統(tǒng)吞吐量最大。搶占式）作業(yè)提交時刻執(zhí)行次序提交時刻運行時間開始時刻完成時刻周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間1342作業(yè)平均周轉(zhuǎn)時間作業(yè)平均帶權(quán)周轉(zhuǎn)時間運行時間1234例5：時間片輪轉(zhuǎn)調(diào)度算法（是一種基于時間片的搶占式調(diào)度算法。），不考慮切換開銷。作業(yè)提交情況如下表所示：作業(yè)提交時刻執(zhí)行次 序提交時 刻運行時間 運行及 完成時刻周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間1234作業(yè)平均周轉(zhuǎn)時間作業(yè)平均帶權(quán)周轉(zhuǎn)時間運行時間1234例6：高響應(yīng)比調(diào)度（非搶占）響應(yīng)比Rp= 等待時間+要求服務(wù)時間 = 響應(yīng)時間要求服務(wù)時間 要求服務(wù)時間作業(yè)提交時刻執(zhí)行次序提交時刻運行時 間等待時 間開始時 刻完成時 刻周轉(zhuǎn)時 間帶權(quán)周轉(zhuǎn) 時間1234作業(yè)平均周轉(zhuǎn)時間作業(yè)平均帶權(quán)周轉(zhuǎn)時間運行時間1234eg1：執(zhí)行次序提交時刻運行時間優(yōu)先數(shù) 運行及 完成時刻周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間A10:0040分鐘5B10:2030分鐘3C10:3050分鐘4D10:5020分鐘6作業(yè)平均周轉(zhuǎn)時間作業(yè)平均帶權(quán)周轉(zhuǎn)時間在一個具有兩道作業(yè)的批處理系統(tǒng)中，作業(yè)調(diào)度采用短作業(yè)優(yōu)先的調(diào)度算法，進程調(diào)度采用優(yōu)先數(shù)為基礎(chǔ)的搶占式調(diào)度算法（作業(yè)優(yōu)先數(shù)即為進程優(yōu)先數(shù)，優(yōu)先數(shù)越小優(yōu)先權(quán)越高），忽略進程切換和調(diào)度開銷。問題：根據(jù)下表求它們的平均周轉(zhuǎn)時間。作業(yè)名到達時間運行時間優(yōu)先數(shù)A10：0040分鐘5B10：2030分鐘3C10：3050分鐘4D10：5020分鐘6eg2:在某多道程序系統(tǒng)中，用戶當(dāng)前可使用的系統(tǒng)資源：內(nèi)存空間100K，磁帶機2臺，打印機1臺。系統(tǒng)采用可變式分區(qū)分配方式管理內(nèi)存，對磁帶機和打印機采用靜態(tài)分配方式，并假設(shè)輸入輸出操作的時間忽略不計。假設(shè)作業(yè)調(diào)度采用先來先服務(wù)算法，內(nèi)存分配采用首次適應(yīng)算法且不準(zhǔn)移動已在內(nèi)存中的作業(yè)，進程調(diào)度采用短作業(yè)優(yōu)先的調(diào)度算法。作業(yè)序列情況如下表。作業(yè)號提交時間運行時間內(nèi)存需求申請磁帶機打印機18：0030分鐘15K1128：2010分鐘30K0138：2020分鐘60K1048：3020分鐘20K1058：3515分鐘10K11問題：（1）求作業(yè)調(diào)度的次序，并給出每道作業(yè)進駐內(nèi)存的時刻（5分）。（2）計算每道作業(yè)的周轉(zhuǎn)時間（5分）。解：（1）（5分） 作業(yè)調(diào)度的順序：1→3→4→2→5 進駐內(nèi)存的時刻分別為：8：00，8：20，8：30， 8：50，9：00 ……(5分)（2）（5分）作業(yè)的周轉(zhuǎn)時間=作業(yè)的完成時間 作業(yè)到達系統(tǒng)的時間。每道作業(yè)的周轉(zhuǎn)時間如下：1號作業(yè)：30（分鐘） 2號作業(yè)：40（分鐘） 3號作業(yè)：30（分鐘） 4號作業(yè)：65（分鐘） 5號作業(yè)：40（分鐘）2. 虛擬頁式存儲器管理系統(tǒng)（頁表、快表、虛地址、物理地址、快表命中、頁表命中、頁面淘汰算法（LRU、CLOCK），駐留集、置換策略、抖動、缺頁中斷）（1）頁表：放在系統(tǒng)空間的頁表區(qū)，存儲邏輯頁與物理頁幀之間的對應(yīng)關(guān)系。每個進程的PCB表中有一個指向頁表的指針，即每一進程擁有一張頁表。有效地址結(jié)構(gòu)： 邏輯地址 = p(頁號)*頁面大小+d(頁內(nèi)位移) 物理地址 = f(頁幀號) )*頁面大小+d(同上)p = 線性邏輯地址 / 頁面大??； d = 線性邏輯地址 p*頁面大小。例如：頁面的大小為1KB，求邏輯地址4101的頁號和頁內(nèi)位移。15 1413 1211 109 86 65 43 21 00 00 10 00 00 00 00 10 1得到頁號p=4，頁內(nèi)位移d=5進程被調(diào)度占用CPU時，進程頁表始址被裝入頁表地址寄存器。例如：有一個32位的分頁存儲器管理系統(tǒng)，頁面的大小規(guī)定為1KB，每個頁表項占4個字節(jié)，求頁表所占的最大內(nèi)存空間？32位計算機系統(tǒng)的邏輯地址空間應(yīng)是232，頁表長度（頁表項的個數(shù)）為： 232/ 210=222頁表所占的內(nèi)存空間：22222=224個字節(jié)，即16MB。訪問權(quán)限進程號物理塊號頁號（2）快表：由一組高速緩沖寄存器組成，用來存放當(dāng)前訪問過的頁表項，以減少地址轉(zhuǎn)換過程中的時間花費。快表的表目結(jié)構(gòu)：（3）命中率：選用812項組成的聯(lián)想存儲器，并采用適當(dāng)?shù)奶鎿Q策略，在聯(lián)想存儲器中匹配成功的可能性可達8090%。（4）等效訪問時間：設(shè)訪問主存時間為750ns，搜索聯(lián)想存儲器的時間為50ns，若聯(lián)想存儲器的命中率為80%，則一次訪問主存的平均時間為（假設(shè)先查聯(lián)想存儲器再查頁表）： 80% *（750+50）+ 20% *（750+50+750）= 950ns （5）虛擬地址：在虛存管理系統(tǒng)中，通常把運行進程訪問的指令和數(shù)據(jù)的邏輯地址（目標(biāo)程序中的相對地址）稱為虛擬地址。虛擬地址的集合稱為虛擬地址空間或邏輯空間。（6）實地址：主存儲器單元的實際地址。主存也稱為實地址空間或物理空間。（7）最近最久未使用（LRU）算法原理 根據(jù)頁面在內(nèi)存中的使用情況，選擇最近最久未使用的頁面予以淘汰。即以“最近的過去”預(yù)測“最近的將來”，即淘汰上次使用距當(dāng)前最遠的頁。 216。 棧實現(xiàn)的LRU法——存放當(dāng)前使用的各頁面的頁號。 實現(xiàn)原理：當(dāng)進程訪問某頁時，就將該頁的頁號從棧底移出壓入棧頂，或?qū)⑿略L問的頁號壓入棧頂。處于棧底的就是最近最久未使用的頁面號。（7）時鐘（Clock）頁面置換算法將二次機會置換算法中的FIFO鏈組織成一個環(huán)狀隊列，設(shè)一指針指向當(dāng)前最老的頁面。當(dāng)產(chǎn)生缺頁中斷時，如果指針?biāo)赶虻捻撁娴脑L問位為“0”，則淘汰，將新調(diào)入的頁面插入到指針指向的位置，指針前移；如果訪問位為“1”，則將其清“0”，指針前移，直到找到一個訪問位為“0”的頁面。（8）頁面分配的有關(guān)策略①最小物理塊數(shù)的確定 最小物理塊數(shù)是指能保證進程正常運行所需要的最少物理塊數(shù)。相關(guān)因素：機器指令的格式、功能 和尋址方式。②頁面分配和置換策略216。 固定分配局部置換216。 可變分配全局置換：系統(tǒng)維護一個空閑物理塊隊列216。 可變分配局部置換：根據(jù)缺頁率來動態(tài)增加或減少分配給每個進程的物理塊數(shù)。頁面置換算法實現(xiàn)目標(biāo)：不發(fā)生抖動現(xiàn)象，缺頁率正常。（9）駐留集：進程的合法頁集合。（10）抖動：如果分配給進程的存儲塊數(shù)量小于進程所需要的最小值，進程的運行將很頻繁地產(chǎn)生缺頁中斷，這種頻率非常高的頁面置換現(xiàn)象稱為抖動。（11）缺頁中斷——當(dāng)前訪問的頁面不再主存時產(chǎn)生缺頁中斷。缺頁中斷與一般中斷的區(qū)別：①在指令執(zhí)行期間產(chǎn)生和處理中斷信號②一條指令執(zhí)行期間可能產(chǎn)生多次缺頁中斷編 程信號量P、V操作的編程 生產(chǎn)者——消費者問題 讀—寫問題步驟：（1）抽象為幾類進程 （2）分析進程之間的直接和間接制約關(guān)系 （3）設(shè)置信號量及其初值 (4）為各類進程編寫代碼補 充？進程控制塊。（1）為使程序能并發(fā)執(zhí)行，且為了對并發(fā)執(zhí)行的程序加以描述和控制，人們引入了進程的概念。（2）進程控制塊PCB是進程實體的一部分，是操作系統(tǒng)中作重要的記錄型數(shù)據(jù)結(jié)構(gòu)。PCB中記錄了操作系統(tǒng)所需的。用于描述進程的當(dāng)前情況以及控制進程運行的全部信息。進程控制塊的作用是使一個在多道程序環(huán)境下不能獨立運行的程序，成為一個能獨立運行的基本單位，一個能與其他進程發(fā)生并發(fā)執(zhí)行的進程。PCB是進程存在的唯一標(biāo)識。特權(quán)指令：只能由操作系統(tǒng)使用的指令。特權(quán)指令的執(zhí)行一般會引起處理器的狀態(tài)切換。處理器的狀態(tài): 根據(jù)運行程序?qū)Y源和機器指令的使用權(quán)限將處理器設(shè)置為不同狀態(tài)：多數(shù)系統(tǒng)將處理器工作狀態(tài)劃分為管態(tài)和目態(tài)：管態(tài)：操作系統(tǒng)管理程序運行的狀態(tài)，又稱為特權(quán)態(tài)、系統(tǒng)態(tài)、管理態(tài)或核心態(tài)目態(tài)：用戶程序運行時的狀態(tài)，又稱為普通態(tài)或、用戶態(tài)有些系統(tǒng)將處理器狀態(tài)劃分核心狀態(tài)，管理狀態(tài)和用戶程序狀態(tài)（目標(biāo)狀態(tài)）三種管態(tài)和目態(tài)的比較: 216。 處理器處于管態(tài)時252。 可以執(zhí)行全部指令（包括特權(quán)指令）252。 可使用所有資源252。 具有改變處理器狀態(tài)的能力216。 處理器處于目態(tài)時：只能執(zhí)行非特權(quán)指令252。 特權(quán)級別不同，可運行指令集合也不同252。 特權(quán)級別越高，可以運行指令集合越大252。 高特權(quán)級別對應(yīng)的可運行指令集合包含低特權(quán)級的，進程的掛起與激活（1）引起進程阻塞與喚醒的事件216。 進程請求系統(tǒng)為之服務(wù)216。 啟動某種操作216。 需要的數(shù)據(jù)不能及時到達216。 本進程無工作可做（如發(fā)送進程）（2）進程的阻塞過程 進程的阻塞通過阻塞原語來實現(xiàn)，阻塞是進程的一種主動行為，過程：216。 將進程狀態(tài)由運行變?yōu)樽枞?16。 將阻塞進程插入對應(yīng)的阻塞隊列216。 設(shè)調(diào)度標(biāo)志為“真” ，進程調(diào)度程序調(diào)度新的就緒進程運行。（3）進程的喚醒過程 進程的喚醒通過喚醒原語實現(xiàn)，喚醒是一種被動行為，過程：216。 將要喚醒的進程從阻塞隊列中移出216。 將該進程的狀態(tài)由阻塞變?yōu)榫途w216。 將該進程插入就緒隊列等待CPU調(diào)度（4）進程的掛起（一個進程只能解掛自己的子孫進程，而不能解掛其他族系的進程。）進程的掛起通過掛起原語來實現(xiàn)，主要過程：檢查將要被掛起的進程的狀態(tài)若狀態(tài)為：執(zhí)行 停止，設(shè)置CPU調(diào)度標(biāo)志為“真” 活動就緒 靜止就緒活動阻塞 靜止阻塞（5）進程的激活進程的激活過程通過激活原語實現(xiàn)，過程：檢查將要被掛起的進程的狀態(tài)：靜止就緒 活動就緒靜止阻塞 活動阻塞檢查是否要進行重新調(diào)度 例如：請判斷下列說法哪些的正確的？ 答案：（2）、（3）（1）進程可以由自己創(chuàng)建 （2）進程可以由自己阻塞