【文章內(nèi)容簡(jiǎn)介】 理解作業(yè)的四種狀態(tài)：提交、后備、執(zhí)行、完成 – ⒊理解作業(yè)調(diào)度與進(jìn)程調(diào)度的關(guān)系 – ⒋掌握常用調(diào)度算法的評(píng)價(jià)指標(biāo)：吞吐量、周轉(zhuǎn)時(shí)間、平均周轉(zhuǎn)時(shí)間、帶權(quán)周轉(zhuǎn)時(shí)間、平均帶權(quán)周轉(zhuǎn)時(shí)間 – ⒌掌握三種基本調(diào)度算法的實(shí)現(xiàn)思想，并能進(jìn)行評(píng)價(jià)指標(biāo)的計(jì)算?？梢岳脠D表形式列出各作業(yè)或進(jìn)程的有關(guān)時(shí)間值，如到達(dá)時(shí)間、運(yùn)行時(shí)間、結(jié)束時(shí)間等，利用評(píng)價(jià)公式計(jì)算出各指標(biāo)的值。 – ⒍了解一般 SHELL命令的執(zhí)行過(guò)程 處理機(jī)調(diào)度級(jí)別 ? 處理機(jī)調(diào)度是操作系統(tǒng)的主要功能之一，它的實(shí)現(xiàn)策略決定了操作系統(tǒng)的類型，其調(diào)度算法的優(yōu)劣直接影響整個(gè)系統(tǒng)的性能。 ? 處理機(jī)調(diào)度的任務(wù)是選出待分派的作業(yè)或進(jìn)程，為之分配處理 機(jī) 。一般來(lái)說(shuō)，處理機(jī)調(diào)度可分為三個(gè)級(jí)別，分別是高級(jí)調(diào)度、中級(jí)調(diào)度和低級(jí)調(diào)度。 – 高級(jí)調(diào)度又稱作業(yè)調(diào)度，作業(yè)就是用戶程序及其所需的數(shù)據(jù)和命令的集合，作業(yè)管理就是對(duì)作業(yè)的執(zhí)行情況進(jìn)行系統(tǒng)管理的程序的集合。作業(yè)調(diào)度程序的主要功能是審查系統(tǒng)是否能滿足用戶作業(yè)的資源要求以及按照一定的算法來(lái)選取作業(yè)。 – 引入中級(jí)調(diào)度的主要目的是為了提高內(nèi)存的利用率和系統(tǒng)吞吐量，使得暫時(shí)不運(yùn)行的進(jìn)程從內(nèi)存對(duì)換到外存上。 – 低級(jí)調(diào)度又稱進(jìn)程調(diào)度，其主要功能是根據(jù)一定的算法將 CPU分派給就緒隊(duì)列中的一個(gè)進(jìn)程。進(jìn)程調(diào)度是操作系統(tǒng)中最基本的一種調(diào)度，其調(diào)度策略的優(yōu)劣直接影響整個(gè)系統(tǒng)的性能。 作業(yè)調(diào)度和進(jìn)程調(diào)度的功能 ? 作業(yè)調(diào)度主要功能 – 是審查系統(tǒng)是否能滿足用戶作業(yè)的資源要求以及按照一定的算法來(lái)選取作業(yè)。主要有： – 記錄系統(tǒng)中各個(gè)作業(yè)的情況； – 按照某種調(diào)度算法從后備作業(yè)隊(duì)列中挑選作業(yè)； – 為選中的作業(yè)分配內(nèi)存和外設(shè)等資源； – 為選中的作業(yè)建立相應(yīng)的進(jìn)程； – 作業(yè)結(jié)束后進(jìn)行善后處理工作。 ? 進(jìn)程調(diào)度 主要功能 – 保存將放棄 CPU進(jìn)程的現(xiàn)場(chǎng)； – 根據(jù)一定的調(diào)度算法，從就緒隊(duì)列中挑選一個(gè)待運(yùn)行進(jìn)程； – 為選中的進(jìn)程恢復(fù)現(xiàn)場(chǎng)，并把 CPU的控制權(quán)交給該進(jìn)程 作業(yè)調(diào)度的常用算法 ? 先來(lái)先服務(wù)法（ FCFS） 如同 “排隊(duì)買票 ”，先來(lái)先做 ? 時(shí)間片輪轉(zhuǎn)法（ RR） 輪流坐莊 ? 優(yōu)先級(jí)法 優(yōu)先級(jí)別高的 “急事 ”先辦 ? 其他調(diào)度算法： – 短作業(yè)優(yōu)先法 – 最短剩余時(shí)間優(yōu)先法 – 多級(jí)隊(duì)列法 – 多級(jí)反饋隊(duì)列法等。 調(diào)度性能的評(píng)價(jià) ? 不同的調(diào)度算法有不同的特性，往往適用于某一類進(jìn)程的運(yùn)行。一般來(lái)說(shuō)，評(píng)價(jià) CPU調(diào)度算法的常用準(zhǔn)則有： – （ 1） CPU利用率 – （ 2）吞吐量 單位時(shí)間內(nèi) CPU完成作業(yè)的數(shù)量。 – （ 3）周轉(zhuǎn)時(shí)間 從作業(yè)提交到作業(yè)完成的時(shí)間間隔。 – （ 4）就緒等待時(shí)間 – （ 5）響應(yīng)時(shí)間 從提交第一個(gè)請(qǐng)求到產(chǎn)生第一個(gè)響應(yīng)所用的時(shí)間。 UNIX常用調(diào)度命令 ? nohup：以忽略掛起和退出的方式執(zhí)行指定的命令。 at：指定命令執(zhí)行的時(shí)間。 ? batch：命令執(zhí)行的優(yōu)先級(jí)低于 at命令。 ? jobs：顯示當(dāng)前 shell下正在運(yùn)行哪些作業(yè)（后臺(tái)作 業(yè)） ? fg： 把指定的后臺(tái)作業(yè)移到前臺(tái)。 ? bg：把前臺(tái)進(jìn)程換到后臺(tái)執(zhí)行 SHELL命令的執(zhí)行過(guò)程 ? UNIX系統(tǒng)中， shell命令是用戶與操作系統(tǒng)之間的界面，它以用戶態(tài)運(yùn)行，執(zhí)行過(guò)程如下： – 讀命令：在 $提示符下，鍵入用戶命令，回車，即可讀入用戶命令。 – 判對(duì)錯(cuò)：終端進(jìn)程分析用戶鍵入的命令是否正確。 – 建子進(jìn)程：終端進(jìn)程調(diào)用 fork，建立子進(jìn)程。 – 等待完成 – 子進(jìn)程運(yùn)行 – 子進(jìn)程終止 – 父進(jìn)程運(yùn)行 – 發(fā)提示符 SHELL命令執(zhí)行過(guò)程流程圖 ? 終端進(jìn)程 讀入命令行 命令有錯(cuò) 典型例題 1 ? 設(shè)有 4道作業(yè)，它們的提交時(shí)間及執(zhí)行時(shí)間如下： ? 試計(jì)算在單道程序環(huán)境下，采用先來(lái)先服務(wù)算法和短作業(yè)優(yōu)先算法的平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間 作業(yè)號(hào) 提交時(shí)間 執(zhí)行時(shí)間 1 2 3 4 解答 ? (1)若采用先來(lái)先服務(wù)調(diào)度算法，其調(diào)度順序?yàn)? 4 ? 平均周轉(zhuǎn)時(shí)間： T=（ +++)/4= ? 平均帶權(quán)周轉(zhuǎn)時(shí)間 W=(1+++11)/4= 作業(yè)號(hào) 提交時(shí)間 執(zhí)行時(shí)間 開(kāi)始時(shí)間 完成時(shí)間 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間 1 2 3 4 作業(yè)號(hào) 提交時(shí)間 執(zhí)行時(shí)間 開(kāi)始時(shí)間 完成時(shí)間 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間 1 4 3 2 ?平均周轉(zhuǎn)時(shí)間： T=（ +++)/4= ?平均帶權(quán)周轉(zhuǎn)時(shí)間 W=(1+6++)/4= (2)若采用短作業(yè)優(yōu)先算法，則其調(diào)度順序?yàn)? 2 例題 2 ? 在單 CPU和兩臺(tái)輸入 /輸出設(shè)備 (I1,I2)的多道程序設(shè)計(jì)環(huán)境下 ,同時(shí)投入三個(gè)作業(yè) JOB JOB JOB3運(yùn)行。這三個(gè)作業(yè)對(duì) CPU和輸入輸出設(shè)備的使用順序和時(shí)間如下所示： – 1： I2(30ms)。CPU(10ms)。I1(30ms)。CPU(10ms)。I2(20ms) – 2： I1(20ms)。CPU(20ms)。I2(40ms) – 3： CPU(30ms)。I1(20ms)。CPU(10ms)。I1(10ms) ? 假定 CPU、 I I2都能并行工作， JOB1優(yōu)先級(jí)最高， JOB2次之，JOB3最低，優(yōu)先級(jí)高的作業(yè)可以搶占優(yōu)先級(jí)低的作業(yè) 的 CPU但不搶占 I1和 I2。試求： （ 1）三個(gè)作業(yè)從投入到完成分別需要的時(shí)間 （ 2）從投入到完成的 CPU利用率 （ 3）輸入輸出設(shè)備利用率 解答 ? 三個(gè)作業(yè)并發(fā)執(zhí)行的情況如下： – ㈠從圖式中可以看出， JOB1從投入到運(yùn)行完成需要 110ms，JOB2從投入到運(yùn)行完成需要 90ms， JOB3從投入到運(yùn)行完成需要 110ms – ㈡ CPU在時(shí)間段 60ms至 70ms， 80ms至 90ms， 100ms至 110ms空閑，所以 CPU的利用率為 (11030)/110=% – ㈢設(shè)備 I1在時(shí)間段 20ms至 40ms,90ms至 100ms期間空閑 ,設(shè)備 I2在時(shí)間段 30ms至 50ms期間空閑 ,所以 I I2的利用率分別為：(11030)/110=%； (11020)/110=% 第四章 存儲(chǔ)器管理 ? 學(xué)習(xí)重點(diǎn)： – (1) 用戶程序的主要處理階段； – (2) 存儲(chǔ)器管理的功能； – (3) 有關(guān)地址 、 重定位 、 虛擬存儲(chǔ)器 、 分頁(yè) 、 分段等概念； – (4) 分頁(yè)存儲(chǔ)管理技術(shù)的實(shí)現(xiàn)思想； – (5) 分段存儲(chǔ)管理技術(shù)的實(shí)現(xiàn)思想； – (6) 頁(yè)面置換及先進(jìn)先出法 。 教學(xué)要求 ? (1)理解三級(jí)存儲(chǔ)器結(jié)構(gòu)：高速緩存 ， 內(nèi)存 ， 外存 。 ? (2)記住用戶程序的主要處理階段：編輯 、 編譯 、 連接 、 裝入 、運(yùn)行 。 ? (3)結(jié)合 ， 理解存儲(chǔ)器管理的功能：內(nèi)存分配 、 地址映射 、內(nèi)存保護(hù) 、 內(nèi)存擴(kuò)充 。 ? (4)牢固掌握以下概念：邏輯地址 、 物理地址 、 可重定位地址 、重定位 、 靜態(tài)重定位 、 動(dòng)態(tài)重定位 、 碎片 、 虛擬存儲(chǔ)器 。 ? (5)理解虛擬存儲(chǔ)器的基本特征：虛擬擴(kuò)充 、 部分裝入 、 離散分配 、 多次對(duì)換 。 虛存容量主要受到哪些方面的限制 ？ ? (6)掌握分頁(yè)和分段概念 ， 二者的主要區(qū)別 。 ? (7)掌握分頁(yè)存儲(chǔ)管理技術(shù)的實(shí)現(xiàn)思想 ， 如何實(shí)現(xiàn)從邏輯地址到物理地址的轉(zhuǎn)換 。 ? (8)理解分段存儲(chǔ)管理技術(shù)的實(shí)現(xiàn)思想 。 ? (9)理解對(duì)換技術(shù)的實(shí)現(xiàn)思想 。 ? (10)理解頁(yè)面置換的先進(jìn)先出法；了解最佳置換法 （ OPT） 和最近最少使用置換法 （ LRU） 。 存儲(chǔ)器的層次 ? 三級(jí)存儲(chǔ)器結(jié)構(gòu) : 程序和數(shù)據(jù)必須先移到內(nèi)存 ,才能被 CPU存取 高速緩存器 CPU 內(nèi)存 外存 程序和數(shù)據(jù)可以被 CPU直接存取 存儲(chǔ)器存取時(shí)間減少 存儲(chǔ)器存取速度增加 每位存儲(chǔ)器成本增加 存儲(chǔ)器容量減少 用戶程序的主要處理階段 ? 用戶的源程序（用高級(jí)語(yǔ)言或匯編語(yǔ)言編寫的程序）進(jìn)入計(jì)算機(jī)系統(tǒng)，到該程序在計(jì)算機(jī)上運(yùn)行，主要經(jīng)歷 5個(gè)處理階段。 – 編輯階段：利用計(jì)算機(jī)提供的編輯程序，入 UNIX中的 vi，將用戶編好的程序輸入到計(jì)算機(jī)內(nèi)。生成源程序文件。 – 編譯階段：把源程序經(jīng)過(guò)翻譯或匯編處理，生成目標(biāo)代碼。編譯過(guò)程即把高級(jí)語(yǔ)言翻譯成計(jì)算機(jī)理解的低級(jí)語(yǔ)言。 – 連接階段：將編譯后得到的一組目標(biāo)模塊以及它們所需的庫(kù)函數(shù)裝配成一個(gè)完整的裝入模塊。 – 裝入階段：將裝入模塊放入分到的內(nèi)存區(qū)中。這時(shí)需要進(jìn)行重定位，即將裝入模塊的邏輯地址轉(zhuǎn)變?yōu)閮?nèi)存的實(shí)際物理地址。 – 運(yùn)行階段：運(yùn)行可執(zhí)行的程序 。 用戶程序的主要處理階段 存儲(chǔ)器管理的相關(guān)概念 ? 邏輯地址 用戶程序經(jīng)編譯后，每個(gè)目標(biāo)模塊以 0為基地址進(jìn)行的順序編址。邏輯地址又稱相對(duì)地址，相對(duì)基地址而言。 ? 物理地址 內(nèi)存中各物理存儲(chǔ)單元的地址從統(tǒng)一的基地址進(jìn)行的順序編址。物理地址又稱絕對(duì)地址，它是數(shù)據(jù)在內(nèi)存中的實(shí)際存儲(chǔ)地址。 ? 重定位 把邏輯地址轉(zhuǎn)變?yōu)閮?nèi)存的物理地址的過(guò)程 – 靜態(tài)重定位 ：是在目標(biāo)程序裝入內(nèi)存時(shí)，由裝入程序?qū)δ繕?biāo)程序中的指令和數(shù)據(jù)進(jìn)行修改，即把程序中邏輯地址都改成實(shí)際的內(nèi)存地址。 過(guò)程如圖所示 – 動(dòng)態(tài)重定位：是在程序執(zhí)行期間每次訪問(wèn)內(nèi)存之前進(jìn)行重定位。需要一個(gè)重定位寄存器 BR。用 BR寄存器的內(nèi)容加上操作對(duì)象的邏輯地址就得到實(shí)際的內(nèi)存地址。過(guò)程如圖所示 實(shí)存管理 ? 單一連續(xù)區(qū)分配 – 最簡(jiǎn)單的存儲(chǔ)分配方法，即整個(gè)主存區(qū)域的用戶空間均歸一個(gè)用戶作業(yè)使用。 ? 分區(qū)管理：由于多道程序設(shè)計(jì)技術(shù)的產(chǎn)生，幾個(gè)作業(yè)得以共享主存儲(chǔ)區(qū)，因此可以采取分區(qū)法分配內(nèi)存。分區(qū)法通常有： – （ 1）固定分區(qū)：在系統(tǒng)建立時(shí)確定每個(gè)分區(qū)的大小及分區(qū)的個(gè)數(shù)； – （ 2）動(dòng)態(tài)分區(qū)：在轉(zhuǎn)入作業(yè)時(shí)確定分區(qū)的個(gè)數(shù)及每個(gè)分區(qū)的大??；回收分區(qū)時(shí)，合并相鄰空閑分區(qū)從而避免分區(qū)越來(lái)越小 – （ 3）可重定位分區(qū)：在裝入作業(yè)時(shí)，根據(jù)需要及時(shí)地將空閑存儲(chǔ)區(qū)拼接在一起，以消除碎片，滿足作業(yè)對(duì)存儲(chǔ)空間的要求； ? 對(duì)換：當(dāng)主存空間不能滿足作業(yè)要求時(shí)，通過(guò)對(duì)換技術(shù)來(lái)解決。對(duì)換是指系統(tǒng)把內(nèi)存中暫時(shí)不能運(yùn)行的進(jìn)程換出到外存上，騰出空間，把具備運(yùn)行條件的進(jìn)程從外存換入內(nèi)存。對(duì)換是以時(shí)間來(lái)?yè)Q取空間，減少對(duì)換的信息量和時(shí)間是設(shè)計(jì)時(shí)要考慮的問(wèn)題 。 虛擬存儲(chǔ)器組織 ? 問(wèn)題的引入：①內(nèi)存不夠用的矛盾②作業(yè)全部裝入造成內(nèi)存浪費(fèi)③程序執(zhí)行具有局部性規(guī)律 ? 虛擬存儲(chǔ)器（ Virtual Memory）：是一種存儲(chǔ)管理技術(shù)，用以完成用小的內(nèi)存實(shí)現(xiàn)在大的虛空間中程序的運(yùn)行工作。虛擬存儲(chǔ)器是由操作系統(tǒng)提供的一個(gè)假想的特大存儲(chǔ)器。 ? 虛擬存儲(chǔ)器所具有的基本特征是： – （ 1）虛擬擴(kuò)充：不是物理上、而是邏輯上擴(kuò)充了內(nèi)存容量； – （ 2）部分裝入：每個(gè)作業(yè)不是全部一次性地裝入內(nèi)存，而是只裝入一部分； – （