湯子瀛-計(jì)算機(jī)操作系統(tǒng)第三版期末總復(fù)習(xí)

1、操作操作系統(tǒng)系統(tǒng)基本概念基本概念處理機(jī)管理處理機(jī)管理設(shè)備管理設(shè)備管理作業(yè)管理作業(yè)管理用戶接口用戶接口存儲(chǔ)管理存儲(chǔ)管理文件管理文件管理操作系統(tǒng)定義操作系統(tǒng)定義OS的作用的作用OS特征特征OS的主要功能的主要功能OS目標(biāo)目標(biāo)OS分類分類多道程序設(shè)計(jì)多道程序設(shè)計(jì)進(jìn)程基本概念進(jìn)程基本概念進(jìn)程同步互斥進(jìn)程同步互斥進(jìn)程間通信進(jìn)程間通信進(jìn)程調(diào)度進(jìn)程調(diào)度死鎖死鎖I/O系統(tǒng)系統(tǒng)I/O控制方式控制方式緩沖技術(shù)緩沖技術(shù)I/O軟件組成軟件組成設(shè)備獨(dú)立性設(shè)備獨(dú)立性設(shè)備分配設(shè)備分配驅(qū)動(dòng)程序驅(qū)動(dòng)程序虛設(shè)備技術(shù)虛設(shè)備技術(shù)通道技術(shù)通道技術(shù)磁盤調(diào)度磁盤調(diào)度文件基本概念文件基本概念文件的邏輯結(jié)構(gòu)文件的邏輯結(jié)構(gòu)文件的物理結(jié)構(gòu)文件的物

2、理結(jié)構(gòu)文件目錄文件目錄外存空間管理外存空間管理文件共享與保護(hù)文件共享與保護(hù)數(shù)據(jù)一致性數(shù)據(jù)一致性用戶接口用戶接口作業(yè)基本概念作業(yè)基本概念批處理系統(tǒng)作業(yè)管理批處理系統(tǒng)作業(yè)管理分時(shí)系統(tǒng)作業(yè)管理分時(shí)系統(tǒng)作業(yè)管理程序的裝入與鏈接程序的裝入與鏈接存儲(chǔ)管理任務(wù)存儲(chǔ)管理任務(wù)動(dòng)態(tài)分區(qū)分配動(dòng)態(tài)分區(qū)分配交換技術(shù)交換技術(shù)頁(yè)式存儲(chǔ)管理頁(yè)式存儲(chǔ)管理段式存儲(chǔ)管理段式存儲(chǔ)管理段頁(yè)式段頁(yè)式虛擬存儲(chǔ)技術(shù)虛擬存儲(chǔ)技術(shù)批處理操作系統(tǒng)批處理操作系統(tǒng)分時(shí)系統(tǒng)分時(shí)系統(tǒng)實(shí)時(shí)操作系統(tǒng)實(shí)時(shí)操作系統(tǒng)個(gè)人計(jì)算機(jī)操作系統(tǒng)個(gè)人計(jì)算機(jī)操作系統(tǒng)網(wǎng)絡(luò)操作系統(tǒng)網(wǎng)絡(luò)操作系統(tǒng)分布式操作系統(tǒng)分布式操作系統(tǒng)操作系統(tǒng)定義操作系統(tǒng)定義OS功能功能OS特征特征OS分類分類硬

3、件運(yùn)行環(huán)境硬件運(yùn)行環(huán)境操作系統(tǒng)設(shè)計(jì)操作系統(tǒng)設(shè)計(jì)并發(fā)并發(fā)共享共享虛擬虛擬異步異步有效管理有效管理合理調(diào)度合理調(diào)度使用方便使用方便吞吐量吞吐量時(shí)間片時(shí)間片虛機(jī)器虛機(jī)器操作系統(tǒng)設(shè)計(jì)目標(biāo)操作系統(tǒng)設(shè)計(jì)目標(biāo)操作系統(tǒng)結(jié)構(gòu)設(shè)計(jì)操作系統(tǒng)結(jié)構(gòu)設(shè)計(jì)CPU狀態(tài)狀態(tài)系統(tǒng)堆棧系統(tǒng)堆棧中斷技術(shù)中斷技術(shù)時(shí)鐘時(shí)鐘通道通道地址映射地址映射存儲(chǔ)保護(hù)存儲(chǔ)保護(hù)處理機(jī)管理處理機(jī)管理存儲(chǔ)管理存儲(chǔ)管理設(shè)備管理設(shè)備管理文件管理文件管理用戶接口用戶接口操作系操作系統(tǒng)基本統(tǒng)基本概念概念進(jìn)程進(jìn)程進(jìn)程狀態(tài)及轉(zhuǎn)換進(jìn)程狀態(tài)及轉(zhuǎn)換進(jìn)程控制塊進(jìn)程控制塊系統(tǒng)并發(fā)度系統(tǒng)并發(fā)度進(jìn)程控制進(jìn)程控制進(jìn)程特性進(jìn)程特性可重入程序可重入程序共享內(nèi)存共享內(nèi)存消息緩沖消息緩沖Se

4、nd/Receive原語原語管道通信管道通信信箱信箱調(diào)度算法選擇原則調(diào)度算法選擇原則算法：算法：先進(jìn)先出先進(jìn)先出時(shí)間片輪轉(zhuǎn)時(shí)間片輪轉(zhuǎn)基于優(yōu)先數(shù)基于優(yōu)先數(shù)高相應(yīng)比優(yōu)先高相應(yīng)比優(yōu)先搶占式搶占式實(shí)時(shí)調(diào)度技術(shù)實(shí)時(shí)調(diào)度技術(shù)進(jìn)程同步進(jìn)程同步進(jìn)程互斥進(jìn)程互斥臨界區(qū)臨界區(qū)進(jìn)程同步機(jī)制進(jìn)程同步機(jī)制信號(hào)量信號(hào)量P、V操作操作生產(chǎn)者與消費(fèi)者問題生產(chǎn)者與消費(fèi)者問題讀者寫者問題讀者寫者問題哲學(xué)家進(jìn)餐問題哲學(xué)家進(jìn)餐問題死鎖的有關(guān)結(jié)論死鎖的有關(guān)結(jié)論產(chǎn)生死鎖的產(chǎn)生死鎖的必要條件必要條件死鎖預(yù)防死鎖預(yù)防死鎖避免死鎖避免死鎖檢測(cè)解除死鎖檢測(cè)解除資源分配圖資源分配圖多道程序設(shè)計(jì)多道程序設(shè)計(jì)進(jìn)程基本概念進(jìn)程基本概念進(jìn)程同步互斥進(jìn)程同

5、步互斥進(jìn)程間通信進(jìn)程間通信進(jìn)程調(diào)度進(jìn)程調(diào)度死鎖死鎖順序環(huán)境順序環(huán)境并發(fā)環(huán)境并發(fā)環(huán)境與時(shí)間有關(guān)的錯(cuò)誤與時(shí)間有關(guān)的錯(cuò)誤不可在現(xiàn)性不可在現(xiàn)性進(jìn)程進(jìn)程管理管理一、生產(chǎn)者消費(fèi)者問題n同步關(guān)系： PCn互斥關(guān)系：互斥訪問BUF設(shè)：生產(chǎn)進(jìn)程資源私用量e：BUF中空的buf數(shù) 消費(fèi)進(jìn)程資源私用量f：BUF中產(chǎn)品數(shù)目 pc公用信號(hào)量m： 互斥訪問BUF設(shè)：指針i指向首空buf j指針指向首產(chǎn)品初值 en f0 m1 ij0 ij BUF空 （i+1）mod nj BUF滿0123n-1e +f=nijp進(jìn)程產(chǎn)品buf（i）i（i+1）mod n V（f）生產(chǎn)一件產(chǎn)品P（e）P（m）v（m）c進(jìn)程V（m）消費(fèi)產(chǎn)品

6、P（f）P（m）從buf（j）中取出產(chǎn)品j（j+1）mod nv（e）下述兩段執(zhí)行序列是否正確？請(qǐng)分析可能出現(xiàn)的問題，并說明理由。 wait (mutex)；“臨界段代碼”；wait (mutex)；“臨界段代碼”；（沒有對(duì)信號(hào)量的訪問）解答：錯(cuò)誤（1）分析: 將signal (mutex)誤寫成wait (mutex). （2）后果: 進(jìn)程使用臨界資源完畢后將無法釋放資源, 若該資源緊張則可能導(dǎo)致死鎖, 違背了空閑讓進(jìn)的原則. （2）錯(cuò)誤（1）分析: wait操作和signal操作缺失. （2）后果: 進(jìn)程將自由進(jìn)入臨界區(qū)使用臨界資源，將導(dǎo)致資源被破壞的嚴(yán)重后果（2）7n1.假定系統(tǒng)中有五個(gè)

7、進(jìn)程P0,P1,P2,P3,P4和三類資源A,B,C，各種資源的數(shù)量分別為10，5，7，在T0時(shí)刻的資源分配情況： 資源 情況進(jìn)程MaxAllocationNeedAvailableA B CA B CA B CA B CP07 5 30 1 03 3 2P13 2 22 0 0P29 0 23 0 2P32 2 22 1 1P44 3 30 0 27 4 3 2 2 0 00 1 14 3 182.P1請(qǐng)求資源Request1（1，0，2），系統(tǒng)按銀行家算法進(jìn)行檢查： Request1（1，0，2）=Need1(1,2,2)Request1（1，0，2）= Available 1(3,3,2

8、) 資源 情況進(jìn)程MaxAllocationNeedAvailableA B CA B CA B CA B CP07 5 30 1 02 3 0P13 2 23 0 2P29 0 23 0 2P32 2 22 1 1P44 3 30 0 27 4 30 2 0 0 00 1 14 3 19存在安全序列P1,P3,P4,P2,P0,因此，系統(tǒng)是安全的，可用立即將P1所申請(qǐng)的資源分配給他。 資源 情況進(jìn)程WorkNeedAllocationWork+AllocationFinish A B CA B CA B CA B CPPPPP10（3）P4請(qǐng)求資源，Request4（3，3，0），系統(tǒng)按銀行

9、家算法進(jìn)行檢查： Request4（3，3，0）= Available 4(2,3,0),讓P4等待。（4）P0請(qǐng)求資源，Request0（0，2，0），系統(tǒng)按銀行家算法進(jìn)行檢查： Request0（0，2，0）=Need0(7,4,3) Request0（0，2，0）= Available 0(2,3,0) 系統(tǒng)暫時(shí)先假定可為P0分配資源，并修改數(shù)據(jù)。 MaxAllocationNeedAvailableA B CA B CA B CA B CP07 5 30 3 02 1 0P13 2 23 0 2P29 0 23 0 2P32 2 22 1 1P44 3 30 0 27 2 30 2 0

10、 0 00 1 14 3 111n2.某系統(tǒng)中四個(gè)進(jìn)程的到達(dá)時(shí)間和要求服務(wù)時(shí)間如下表，請(qǐng)采用SPF（不搶占）調(diào)度算法進(jìn)行分析，求進(jìn)程執(zhí)行序列和平均周轉(zhuǎn)時(shí)間。要求有分析過程。 12n3.考慮一個(gè)有150個(gè)存儲(chǔ)器單元的系統(tǒng)，如下分配給三個(gè)進(jìn)程：n進(jìn)程 最大需求已分配nn1 7045n2 6040n3 6015n使用銀行家算法，以確定下面的任何一個(gè)請(qǐng)求是否安全：na第4個(gè)進(jìn)程到達(dá)，最多需要60個(gè)存儲(chǔ)單元，最初需要25個(gè)單元；nb第4個(gè)進(jìn)程到達(dá)，最多需要60個(gè)存儲(chǔ)單元，最初需要35個(gè)單元；n如果安全給出安全序列；若不安全給出結(jié)果分配簡(jiǎn)表。13第四章第四章 存儲(chǔ)管理存儲(chǔ)管理15段式存儲(chǔ)管理段式存儲(chǔ)管理頁(yè)

11、式存儲(chǔ)管理頁(yè)式存儲(chǔ)管理段頁(yè)式存儲(chǔ)管理段頁(yè)式存儲(chǔ)管理虛擬存儲(chǔ)器虛擬存儲(chǔ)器虛擬存儲(chǔ)技術(shù)虛擬存儲(chǔ)技術(shù)程序局部性原理程序局部性原理虛擬頁(yè)式管理虛擬頁(yè)式管理虛擬段式管理虛擬段式管理頁(yè)面淘汰算法頁(yè)面淘汰算法用戶程序劃分用戶程序劃分邏輯地址邏輯地址內(nèi)存空間劃分內(nèi)存空間劃分內(nèi)存分配內(nèi)存分配管理考慮管理考慮硬件支持硬件支持地址映射過程地址映射過程裝入與鏈接裝入與鏈接對(duì)換技術(shù)對(duì)換技術(shù)高速緩存高速緩存內(nèi)存內(nèi)存磁盤磁盤系統(tǒng)區(qū)系統(tǒng)區(qū)用戶區(qū)用戶區(qū)內(nèi)存管理分配回收內(nèi)存管理分配回收存儲(chǔ)共享存儲(chǔ)共享存儲(chǔ)保護(hù)存儲(chǔ)保護(hù)內(nèi)存擴(kuò)充內(nèi)存擴(kuò)充地址映射地址映射存儲(chǔ)體系存儲(chǔ)體系存儲(chǔ)管理任務(wù)存儲(chǔ)管理任務(wù)存儲(chǔ)管理方案存儲(chǔ)管理方案虛擬存儲(chǔ)管理虛擬存

12、儲(chǔ)管理其他其他存儲(chǔ)存儲(chǔ)管理管理16n1、在一個(gè)請(qǐng)求分頁(yè)系統(tǒng)中，假如系統(tǒng)分配給一個(gè)作業(yè)的物理塊數(shù)為 4，且此作業(yè)的頁(yè)面走向?yàn)椋?，3，2，1，5，2，4，5，3，2，5，2。試用FIFO（先進(jìn)先出）和OPT（最佳）兩種算法分別計(jì)算出程序訪問過程中所發(fā)生的缺頁(yè)次數(shù)（假設(shè)開始執(zhí)行時(shí)主存中沒有頁(yè)面，凡第一次用到的頁(yè)面都產(chǎn)生一次缺頁(yè)中斷。要求列表計(jì)算）。LRU?3 ?頁(yè)面置換次數(shù)頁(yè)面置換次數(shù)1718 例例2 2：已知某分頁(yè)系統(tǒng)，主存容量為：已知某分頁(yè)系統(tǒng)，主存容量為64K64K，頁(yè)面大，頁(yè)面大小為小為1K1K，對(duì)一個(gè)，對(duì)一個(gè)4 4頁(yè)大的作業(yè)，其頁(yè)大的作業(yè)，其0 0、1 1、2 2、3 3頁(yè)頁(yè)分別被分配到

13、主存的分別被分配到主存的2 2、4 4、6 6、7 7塊中。塊中。 （1 1）將十進(jìn)制的邏輯地址）將十進(jìn)制的邏輯地址10231023、25002500、35003500、45004500轉(zhuǎn)換成物理地址？轉(zhuǎn)換成物理地址？ （2 2）以十進(jìn)制的邏輯地址）以十進(jìn)制的邏輯地址10231023為例畫出為例畫出地址變地址變換過程圖換過程圖？19 答答：邏輯地址邏輯地址10231023：1023/1K1023/1K，得頁(yè)號(hào)為，得頁(yè)號(hào)為0 0，頁(yè)內(nèi)地址，頁(yè)內(nèi)地址為為10231023，查頁(yè)表找到對(duì)應(yīng)的物理塊號(hào)為，查頁(yè)表找到對(duì)應(yīng)的物理塊號(hào)為2 2，故物理地，故物理地址為址為2 21K+1023=30711K+10

14、23=3071 邏輯地址邏輯地址25002500：2500/1K2500/1K，得頁(yè)號(hào)為，得頁(yè)號(hào)為2 2，頁(yè)內(nèi)地址，頁(yè)內(nèi)地址為為452452，查頁(yè)表找到對(duì)應(yīng)的物理塊號(hào)為，查頁(yè)表找到對(duì)應(yīng)的物理塊號(hào)為6 6，故物理地，故物理地址為址為6 61K+452=65961K+452=6596 邏輯地址邏輯地址35003500：3500/1K3500/1K，得頁(yè)號(hào)為，得頁(yè)號(hào)為3 3，頁(yè)內(nèi)地址，頁(yè)內(nèi)地址為為428428，查頁(yè)表找到對(duì)應(yīng)的物理塊號(hào)為，查頁(yè)表找到對(duì)應(yīng)的物理塊號(hào)為7 7，故物理地，故物理地址為址為7 71K+428=75961K+428=7596 邏輯地址邏輯地址45004500：4500/1K45

15、00/1K，得頁(yè)號(hào)為，得頁(yè)號(hào)為4 4，頁(yè)內(nèi)地址，頁(yè)內(nèi)地址為為404404，因頁(yè)號(hào)不小于頁(yè)表長(zhǎng)度，故產(chǎn)生，因頁(yè)號(hào)不小于頁(yè)表長(zhǎng)度，故產(chǎn)生越界中斷越界中斷。20 （2）地址變換過程圖地址變換過程圖21小小結(jié)結(jié) 方法方法功能功能單一單一連續(xù)區(qū)連續(xù)區(qū)分區(qū)式分區(qū)式頁(yè)式頁(yè)式段式段式段頁(yè)式段頁(yè)式固定固定可變可變靜態(tài)靜態(tài)動(dòng)態(tài)動(dòng)態(tài)適用環(huán)適用環(huán)境境單道單道多道多道多道多道多道多道多道多道虛擬空虛擬空間間一維一維一維一維一維一維二維二維二維二維重定位重定位方式方式靜態(tài)靜態(tài)靜態(tài)靜態(tài) 動(dòng)態(tài)動(dòng)態(tài)動(dòng)態(tài)動(dòng)態(tài)動(dòng)態(tài)動(dòng)態(tài)動(dòng)態(tài)動(dòng)態(tài)分配方分配方式式靜態(tài)連續(xù)靜態(tài)連續(xù)區(qū)區(qū)靜態(tài)靜態(tài) 動(dòng)態(tài)連續(xù)區(qū)動(dòng)態(tài)連續(xù)區(qū)靜態(tài)或動(dòng)態(tài)頁(yè)靜態(tài)或動(dòng)態(tài)頁(yè)為單位非連續(xù)為單

16、位非連續(xù)動(dòng)態(tài)段為單位動(dòng)態(tài)段為單位非連續(xù)非連續(xù)動(dòng)態(tài)分配頁(yè)為動(dòng)態(tài)分配頁(yè)為單位非連續(xù)單位非連續(xù)釋放釋放執(zhí)行完后執(zhí)行完后全部釋放全部釋放執(zhí)行完后全執(zhí)行完后全部釋放部釋放分區(qū)分區(qū)釋放釋放執(zhí)行執(zhí)行完后完后釋放釋放淘汰與執(zhí)淘汰與執(zhí)行完后釋行完后釋放放淘汰與執(zhí)行完淘汰與執(zhí)行完后釋放后釋放淘汰與執(zhí)行淘汰與執(zhí)行完后釋放完后釋放保護(hù)保護(hù)越界保護(hù)越界保護(hù)越界保護(hù)與保護(hù)鍵越界保護(hù)與保護(hù)鍵越界保護(hù)與控越界保護(hù)與控制權(quán)保護(hù)制權(quán)保護(hù)越界保護(hù)與控越界保護(hù)與控制權(quán)保護(hù)制權(quán)保護(hù)越界保護(hù)與越界保護(hù)與控制權(quán)保護(hù)控制權(quán)保護(hù)內(nèi)存擴(kuò)內(nèi)存擴(kuò)充充覆蓋與交覆蓋與交換換覆蓋與交換覆蓋與交換覆蓋覆蓋交換交換虛擬存虛擬存儲(chǔ)儲(chǔ)虛擬存儲(chǔ)虛擬存儲(chǔ)虛擬存儲(chǔ)虛擬

17、存儲(chǔ)共享共享不能不能不能不能較難較難方便方便方便方便硬件支硬件支持持保護(hù)用寄保護(hù)用寄存器存器保護(hù)用寄存器，重保護(hù)用寄存器，重定位機(jī)構(gòu)定位機(jī)構(gòu)地址變換機(jī)構(gòu)，地址變換機(jī)構(gòu)，中斷機(jī)構(gòu)，保護(hù)中斷機(jī)構(gòu)，保護(hù)機(jī)構(gòu)機(jī)構(gòu)段式地址變換機(jī)構(gòu)，段式地址變換機(jī)構(gòu)，保護(hù)與中斷機(jī)構(gòu)，保護(hù)與中斷機(jī)構(gòu)，動(dòng)態(tài)連接機(jī)構(gòu)動(dòng)態(tài)連接機(jī)構(gòu)段式地址變換機(jī)段式地址變換機(jī)構(gòu)，保護(hù)與中斷構(gòu)，保護(hù)與中斷機(jī)構(gòu)，動(dòng)態(tài)連接機(jī)構(gòu)，動(dòng)態(tài)連接機(jī)構(gòu)機(jī)構(gòu)設(shè)備管理重要性設(shè)備管理重要性設(shè)備獨(dú)立性設(shè)備獨(dú)立性設(shè)備分類設(shè)備分類設(shè)備管理任務(wù)設(shè)備管理任務(wù)I/O通道通道DMA控制方式控制方式用戶進(jìn)程用戶進(jìn)程與設(shè)備無關(guān)軟件與設(shè)備無關(guān)軟件設(shè)備驅(qū)動(dòng)程序設(shè)備驅(qū)動(dòng)程序中斷處理程序中斷處理

18、程序SPOOLing技術(shù)技術(shù)共享打印機(jī)共享打印機(jī)設(shè)備管理設(shè)備管理設(shè)備分配回收設(shè)備分配回收獨(dú)占設(shè)備分配獨(dú)占設(shè)備分配共享設(shè)備分配共享設(shè)備分配 基本概念基本概念I(lǐng)/O軟件組成軟件組成緩沖技術(shù)緩沖技術(shù)設(shè)備處理設(shè)備處理虛設(shè)備技術(shù)虛設(shè)備技術(shù)設(shè)備驅(qū)動(dòng)程序設(shè)備驅(qū)動(dòng)程序設(shè)備設(shè)備管理管理磁盤訪問時(shí)間磁盤訪問時(shí)間磁盤調(diào)度磁盤調(diào)度l先來先服務(wù)先來先服務(wù)l最短尋道時(shí)間優(yōu)先最短尋道時(shí)間優(yōu)先l掃描（電梯算法）掃描（電梯算法）lCSCAN磁盤存儲(chǔ)管理磁盤存儲(chǔ)管理第五章設(shè)備管理的重點(diǎn)、難點(diǎn)第五章設(shè)備管理的重點(diǎn)、難點(diǎn)n 設(shè)備管理的主要任務(wù)設(shè)備管理的主要任務(wù)n 什么叫通道技術(shù)什么叫通道技術(shù)n 如何解決因通道不足而產(chǎn)生的瓶頸問題如何

19、解決因通道不足而產(chǎn)生的瓶頸問題n I/O I/O 控制方式：四種控制方式：四種I/O I/O 方式的基本原理方式的基本原理；I/O I/O 方式由低方式由低到高效的演變的推動(dòng)因素是什么？到高效的演變的推動(dòng)因素是什么？n緩沖的概念，為什么引入緩沖緩沖的概念，為什么引入緩沖n中斷處理程序的處理過程中斷處理程序的處理過程n 設(shè)備分配方式設(shè)備分配方式第五章設(shè)備管理的重點(diǎn)、難點(diǎn)第五章設(shè)備管理的重點(diǎn)、難點(diǎn)虛擬設(shè)備和虛擬設(shè)備和SPOOLing SPOOLing 技術(shù)技術(shù)n什么是虛擬設(shè)備什么是虛擬設(shè)備n什么是什么是SPOOLingSPOOLing技術(shù)，技術(shù)，SPOOLingSPOOLing系統(tǒng)的組成系統(tǒng)的組成

20、n如何利用如何利用SPOOLingSPOOLing技術(shù)實(shí)現(xiàn)共享打印機(jī)技術(shù)實(shí)現(xiàn)共享打印機(jī)磁盤調(diào)度磁盤調(diào)度n磁盤調(diào)度的磁盤調(diào)度的目標(biāo)目標(biāo)n磁盤訪問時(shí)間磁盤訪問時(shí)間的計(jì)算的計(jì)算nFCFSFCFS、SSTFSSTF、SCANSCAN、CSCAN CSCAN 等算法的應(yīng)用等算法的應(yīng)用及這些調(diào)度算法及這些調(diào)度算法的演變過程，分別解決了哪些問題；各算法的性能比較的演變過程，分別解決了哪些問題；各算法的性能比較25一個(gè)磁盤系統(tǒng)，平均尋道時(shí)間為一個(gè)磁盤系統(tǒng)，平均尋道時(shí)間為12ms，轉(zhuǎn)速為，轉(zhuǎn)速為10000轉(zhuǎn)轉(zhuǎn)/分，每個(gè)磁道有分，每個(gè)磁道有18個(gè)扇區(qū)，每個(gè)扇區(qū)個(gè)扇區(qū)，每個(gè)扇區(qū)512個(gè)字節(jié)。個(gè)字節(jié)。請(qǐng)問要讀取一個(gè)扇

21、區(qū)所花的時(shí)間是多少？請(qǐng)問要讀取一個(gè)扇區(qū)所花的時(shí)間是多少？ 解：解： TS = 12msTR = 1/2r = 60100000.5 = 3ms TA=b/rN = (51260)(1851210000)= 0.33ms TT = TS + TR + TA =12 + 3 + 0.33 = 15.33ms答：讀取一個(gè)扇區(qū)所花的時(shí)間是答：讀取一個(gè)扇區(qū)所花的時(shí)間是15.33ms。 例例26 磁盤調(diào)度磁盤調(diào)度 目標(biāo)：減少尋道時(shí)間目標(biāo)：減少尋道時(shí)間1 1、FCFSFCFS（Fisrt Come First ServedFisrt Come First Served）先來先服務(wù)）先來先服務(wù)n特點(diǎn)：公平、簡(jiǎn)

22、單，尋道時(shí)間長(zhǎng)，相當(dāng)于隨機(jī)特點(diǎn)：公平、簡(jiǎn)單，尋道時(shí)間長(zhǎng)，相當(dāng)于隨機(jī)訪問模式。訪問模式。n僅適用于請(qǐng)求磁盤僅適用于請(qǐng)求磁盤I/OI/O的進(jìn)程數(shù)目較少的場(chǎng)合。的進(jìn)程數(shù)目較少的場(chǎng)合。2 2、SSTFSSTF（最短尋道優(yōu)先）最短尋道時(shí)間優(yōu)先（最短尋道優(yōu)先）最短尋道時(shí)間優(yōu)先nSSTFSSTF比比FCFSFCFS有更好的尋道性能有更好的尋道性能n貪心的算法貪心的算法n饑餓現(xiàn)象饑餓現(xiàn)象n不能保證平均尋道時(shí)間最短不能保證平均尋道時(shí)間最短 ？273 3、SCAN SCAN 掃描算法（也稱為電梯算法）。掃描算法（也稱為電梯算法）。n進(jìn)程進(jìn)程“饑餓現(xiàn)象饑餓現(xiàn)象”SSTFSSTF存在。存在。nSCANSCAN算法：算

23、法：n在移動(dòng)方向固定的情況下采用了在移動(dòng)方向固定的情況下采用了SSTFSSTF，以避，以避免饑餓現(xiàn)象免饑餓現(xiàn)象 4 4、循環(huán)掃描、循環(huán)掃描CSCANCSCANn磁頭單向移動(dòng)磁頭單向移動(dòng)n一個(gè)方向讀完，不是象一個(gè)方向讀完，不是象SCANSCAN那樣回頭，而是循那樣回頭，而是循環(huán)掃描。環(huán)掃描。28例n假設(shè)一個(gè)活動(dòng)頭磁盤有200道, 編號(hào)從0-199. 當(dāng)前磁頭正在143道上服務(wù), 并且剛剛完成了125道的請(qǐng)求?，F(xiàn)有如下訪盤請(qǐng)求序列(磁道號(hào)): 86, 147, 91, 177, 94, 150, 102, 175, 130n 試給出采用下列算法后磁頭移動(dòng)的順序和移動(dòng)總量(總磁道數(shù)).n (1) 先

24、來先服務(wù)(FCFS)磁盤調(diào)度算法. (2) 最短尋道時(shí)間優(yōu)先(SSTF)磁盤調(diào)度算法.n(3) 掃描法(SCAN)磁盤調(diào)度算法.(假設(shè)沿磁頭移動(dòng)方向不再有訪問請(qǐng)求時(shí), 磁頭沿相反方向移動(dòng))29n答、n（1）磁道訪問順序?yàn)椋?6，147，91，177，94，150，102，175，130n磁頭移動(dòng)的總磁道數(shù) = 57+61+56+86+83+56+48+73+45 = 565 （3分）n （2）當(dāng)前磁頭在143道上：n 磁道訪問順序?yàn)椋?47，150，130，102，94，91，86，175，177n 磁頭移動(dòng)的總磁道數(shù) = 4+3+20+28+8+3+5+89+2 = 162（3分）n（3）當(dāng)

25、前磁頭在143道上，并且剛剛完成125道的請(qǐng)求n 磁道訪問順序?yàn)椋?47，150，175，177，130，102，94，91，86n 磁頭移動(dòng)的總磁道數(shù) = 4+3+25+2+47+28+8+3+5 = 125（4分）30例n若干個(gè)等待訪問磁盤者依次要訪問的磁道為20，44，40，4，80，12，76，假設(shè)每移動(dòng)一個(gè)磁道需要3毫秒時(shí)間，移動(dòng)臂當(dāng)前位于40號(hào)柱面，請(qǐng)按下列算法分別寫出訪問序列并計(jì)算為完成上述各次訪問總共花費(fèi)的尋道時(shí)間。n（1）先來先服務(wù)算法；（2）最短尋道時(shí)間優(yōu)先算法。n（3）掃描算法（當(dāng)前磁頭移動(dòng)的方向?yàn)榇诺肋f增）31n解：（1）磁道訪問順序?yàn)椋?0，44，40，4，80，12

26、，76n尋道時(shí)間 =（20+24+4+36+76+68+64）*3=292*3=876（3分）n（2）磁道訪問順序?yàn)椋?0，44，20，12，4，76，80n尋道時(shí)間 =（0+4+24+8+8+72+4）*3=120*3=360（3分）n（3）磁道訪問順序?yàn)椋?0，44，76，80，20，12，4n尋道時(shí)間 =（0+4+32+4+60+8+8）*3=116*3=348（4分）32磁盤訪問時(shí)間由哪幾部分組成？每部分時(shí)間應(yīng)如何計(jì)算？n解：磁盤訪問時(shí)間由下述部分組成：n（1）尋道時(shí)間Ts ：指把磁臂(磁頭)移動(dòng)到指定磁道上所經(jīng)歷的時(shí)間。該時(shí)間是啟動(dòng)磁臂的時(shí)間s與磁頭移動(dòng)n條磁道所花費(fèi)的時(shí)間之和，即Ts=mn+s 。（2分）n（2）旋轉(zhuǎn)延遲時(shí)間Tr：這是指定扇區(qū)移動(dòng)到磁頭下面所經(jīng)歷的時(shí)間。（2分）n（3）傳輸時(shí)間Tt：從磁盤讀出或?qū)懭隻個(gè)字節(jié)數(shù)據(jù)所經(jīng)歷的時(shí)間。n其中，r為磁盤每秒鐘的轉(zhuǎn)數(shù)；N為一條磁道上的字節(jié)數(shù)。（3分）n因此，訪問時(shí)間Ta表示為： （3分）文件控制塊文件控制塊文件目錄文件目錄目錄文件目錄文件目錄項(xiàng)目錄項(xiàng)樹型目錄結(jié)構(gòu)樹型目錄結(jié)構(gòu)目錄項(xiàng)分解法目錄項(xiàng)分解法目錄檢索目錄檢索文件文件文件系統(tǒng)文件系統(tǒng)文件分類文件分類文件管理功能