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