第6章設備管理(2)課件

1、12022-2-46.7 6.7 緩沖管理緩沖管理6.7.16.7.1緩沖的引入緩沖的引入緩沖技術的主要原因是:#緩和CPU與I/O設備間速度不匹配的矛盾。 計算機系統(tǒng)中的各種設備(包括中央處理機)的運行速度差異甚大，CPU的運行速度是以微秒甚至以納秒計，而設備的運行速度則是以毫秒甚至以秒計；（速度的差異） 事實上，凡在數(shù)據(jù)到達速率與其離去速率不同的地方，都可設置緩沖區(qū)，以緩和它們之間的速率不匹配的矛盾。22022-2-4#減少對CPU中斷頻率，放寬對CPU中斷的響應時間的限制。例（p209） #解決數(shù)據(jù)粒度不匹配的問題。#為了提高CPU與外設的并行程度 緩沖的引入可顯著的提高CPU和I/P設

2、備間的并行操作程度，提高系統(tǒng)在吞吐量和設備的利用率。32022-2-4圖 5-10 利用緩沖寄存器實現(xiàn)緩沖 1位緩沖9.6 Kb/s8位緩沖寄存器送內存9.6 Kb/s8位緩沖寄存器9.6 Kb/s送內存(b)(a)(c)42022-2-4#如用一位緩沖來接收，則必須在每收到一位數(shù)據(jù)時便中斷一次CPU，并在下一位數(shù)據(jù)到來之前要求CPU進行中斷處理以取走輸入數(shù)據(jù) #若設一個8位的緩沖，則可每收8位數(shù)據(jù)中斷一次CPU，但在第9位數(shù)據(jù)到來之前仍必須完成中斷處理#若再增加8位的緩沖，則可每收8位數(shù)據(jù)中斷一次CPU，并允許CPU在下8位數(shù)據(jù)到來期間處理前8位數(shù)據(jù)的中斷。52022-2-4常用的緩沖技術常

3、用的緩沖技術1 1、單緩沖、單緩沖2 2、雙緩沖、雙緩沖3 3、環(huán)形緩沖、環(huán)形緩沖4 4、緩沖池、緩沖池 62022-2-46.7.2 單緩沖單緩沖最簡單的一種緩沖形式。當進程發(fā)出一最簡單的一種緩沖形式。當進程發(fā)出一I/O請求請求時，時，OS為之分配一緩沖區(qū)。為之分配一緩沖區(qū)。對于輸入：設備先將數(shù)據(jù)送入緩沖區(qū)，對于輸入：設備先將數(shù)據(jù)送入緩沖區(qū)，OS再將再將數(shù)據(jù)傳給進程。數(shù)據(jù)傳給進程。對于輸出：進程先將數(shù)據(jù)傳入緩沖區(qū)，對于輸出：進程先將數(shù)據(jù)傳入緩沖區(qū)，OS再將再將數(shù)據(jù)送出到設備。數(shù)據(jù)送出到設備。72022-2-4n單緩沖：只為設備設置一個緩沖區(qū)的情形稱為單緩沖：只為設備設置一個緩沖區(qū)的情形稱為“

4、單緩沖單緩沖”。圖是單緩沖的工作示意，它表示產(chǎn)。圖是單緩沖的工作示意，它表示產(chǎn)生數(shù)據(jù)者（即生產(chǎn)者）不是把數(shù)據(jù)直接送給接收生數(shù)據(jù)者（即生產(chǎn)者）不是把數(shù)據(jù)直接送給接收數(shù)據(jù)者（即接收者），而是把數(shù)據(jù)送入到所設置數(shù)據(jù)者（即接收者），而是把數(shù)據(jù)送入到所設置的緩沖區(qū)中。接收數(shù)據(jù)者總是從緩沖區(qū)中去取所的緩沖區(qū)中。接收數(shù)據(jù)者總是從緩沖區(qū)中去取所需要的數(shù)據(jù)。需要的數(shù)據(jù)。n對于塊設備：系統(tǒng)處理時間為對于塊設備：系統(tǒng)處理時間為MAX(C,T)+M工作區(qū)處理(C )緩沖區(qū)傳送(M )輸入(T )I/O 設備(a )T1M1C1T2M2C2T3M3C3T4t(b )用戶進程82022-2-4雙緩沖技術雙緩沖技術為了加快

5、輸入輸出速度，引入雙緩沖技術。為了加快輸入輸出速度，引入雙緩沖技術。原理：原理：設置兩個緩沖區(qū)buf1和buf2。讀入數(shù)據(jù)時，首先輸入設備向buf1填入數(shù)據(jù)，然后進程從buf1提取數(shù)據(jù)，在進程從buf1提取數(shù)據(jù)的同時。輸入設備向buf2中填數(shù)據(jù)。當buf1取空時，進程又從buf2中提取數(shù)據(jù)，與此同時輸入設備向buf1填數(shù)。如此交替使用兩個緩沖區(qū)，使CPU和設備的并行操作的程度進一步提高。 92022-2-4雙緩沖技術雙緩沖技術工作區(qū)用戶進程緩沖區(qū)1緩沖區(qū)2I/O 設備T1(緩沖1)M1C1M2C2M3C3T2(緩沖2)T3(緩沖3)M4C4T4(緩沖4)(a)(b)對于一塊數(shù)據(jù)的處理時間約為對

6、于一塊數(shù)據(jù)的處理時間約為Max(C,T)102022-2-4雙緩沖技術雙緩沖技術#對于字符設備，若采用行輸入方式，則采用雙緩沖通常能消除用戶的等待時間，即用戶在輸入完第一行后，在CPU執(zhí)行第一行中的命令時，用戶可繼續(xù)向第二緩沖區(qū)輸入下一行數(shù)據(jù) #雙向通信（P211)緩沖區(qū)緩沖區(qū)A機B機(a) 單緩沖發(fā)送緩沖區(qū)接收緩沖區(qū)接收緩沖區(qū)發(fā)送緩沖區(qū)A機B機(b) 雙緩沖112022-2-46.7.3 6.7.3 環(huán)形緩沖技術環(huán)形緩沖技術 當生產(chǎn)和消費數(shù)據(jù)的速度基本匹配時，當生產(chǎn)和消費數(shù)據(jù)的速度基本匹配時，雙緩沖能獲得較好效果。但若雙緩沖能獲得較好效果。但若兩者速度相差兩者速度相差甚遠時，效果不太理想甚遠

7、時，效果不太理想。但隨著緩沖區(qū)的數(shù)。但隨著緩沖區(qū)的數(shù)量增加，使情況有所改善。因此引入環(huán)形緩量增加，使情況有所改善。因此引入環(huán)形緩沖技術。沖技術。122022-2-4環(huán)形緩沖技術是在主存中分配一組大小相等的存儲區(qū)作為緩沖區(qū)，并將這些緩沖區(qū)鏈接起來。系統(tǒng)中有個緩沖區(qū)鏈首指針，指向第一個緩沖區(qū)，每個緩沖區(qū)中有一個指向下一個緩沖區(qū)的指針，最后一個緩沖區(qū)中的指針指向第一個緩沖區(qū)，從而形成循環(huán)緩沖區(qū)鏈。如圖所示。系統(tǒng)可循環(huán)使用這些緩沖區(qū)。環(huán)形緩沖區(qū)用于輸入(輸出)時，還要有兩個指針I(yè)N和OUT。132022-2-4圖圖142022-2-4 環(huán)形緩沖的組成環(huán)形緩沖的組成n 多個緩沖區(qū)（R，G，C）n 多個指

8、針 圖 5-14 循環(huán)緩沖 RGGGRG165423NextiNextgRGGGRC165423NextiNextgcurrent152022-2-42. 環(huán)形緩沖的使用環(huán)形緩沖的使用n Getbuf過程n Releasebuf過程 圖 5-14 循環(huán)緩沖 RGGGRG165423NextiNextgRGGGRC165423NextiNextgcurrent162022-2-43.進程同步進程同步 圖 5-14 循環(huán)緩沖 RGGGRG165423NextiNextgRGGGRC165423NextiNextgcurrentNexti指針追趕上Nextg指針。系統(tǒng)受計算限制(2) Nextg指針

9、追趕上Nexti指針。 系統(tǒng)受I/O限制172022-2-46.7.4 6.7.4 緩沖池緩沖池循環(huán)緩沖區(qū)一般用于特定的進程，屬于專用緩沖區(qū)，當系統(tǒng)較大時，將會有許多這樣的環(huán)形緩沖區(qū)，這不僅要消耗大量的內存空間，利用率也不高。為了提高緩沖區(qū)的利用率，目前廣泛流行公用緩沖池，池中的緩沖區(qū)可供多個進程共享。 182022-2-46.7.4 6.7.4 緩沖池緩沖池 緩沖池由內存中一組大小相等的緩沖區(qū)組成，池中各緩沖區(qū)的大小與用于I/O的設備的基本信息單位相似，緩沖池屬于系統(tǒng)資源，由系統(tǒng)進行管理。緩沖池中各緩沖區(qū)可用于輸出信息，也可用于輸入信息，并可根據(jù)需要組成各種緩沖區(qū)隊列。 192022-2-4

10、n緩沖池：系統(tǒng)為同類型的緩沖池：系統(tǒng)為同類型的I/O設備設置一個公共緩沖設備設置一個公共緩沖隊列，既用于輸入，也用于輸出。它是多緩沖的一隊列，既用于輸入，也用于輸出。它是多緩沖的一種變異，以避免緩沖區(qū)使用上忙閑不均的現(xiàn)象。種變異，以避免緩沖區(qū)使用上忙閑不均的現(xiàn)象。n緩沖池組成：緩沖池組成： 3類緩沖區(qū)類緩沖區(qū),3個隊列和個隊列和4種工作緩沖區(qū)種工作緩沖區(qū)。n無論現(xiàn)在用于輸入的還是用于輸出的，它們在用完無論現(xiàn)在用于輸入的還是用于輸出的，它們在用完后，都歸還到空閑的緩沖區(qū)隊列中，受系統(tǒng)的統(tǒng)一后，都歸還到空閑的緩沖區(qū)隊列中，受系統(tǒng)的統(tǒng)一管理和調配。管理和調配。202022-2-42. Getbuf過

11、程和過程和Putbuf過程過程 （互斥與同步）（互斥與同步） Procedure Getbuf(type) begin Wait(RS(type); Wait(MS(type); B(number) =Takebuf(type); Signal(MS(type); end Procedure Putbuf(type, number) begin Wait(MS(type); Addbuf(type, number); Signal(MS(type); Signal(RS(type); end 212022-2-43. 緩沖區(qū)的工作方式緩沖區(qū)的工作方式收容輸入；提取輸入；收容輸出；提取輸出收容輸

12、入；提取輸入；收容輸出；提取輸出 圖 5-15 緩沖區(qū)的工作方式 hinsoutsinhout收 容 輸 入提 取 輸 出用 戶程 序提 取 輸 入收 容 輸 出緩 沖 池222022-2-4n在利用在利用RS-232接口進行通信時，其通信速率接口進行通信時，其通信速率為為9.6kb/s(b為為bit)。如果在通信接口中僅設。如果在通信接口中僅設置了一個置了一個8位寄存器作為緩沖寄存器，這意味位寄存器作為緩沖寄存器，這意味著大約每隔（）的時間便要中斷一次著大約每隔（）的時間便要中斷一次CPU，且要求且要求CPU必須在（）時間內予以響應。必須在（）時間內予以響應。nA、80us B、0.1ms

13、C、0.8ms D、1msnE、8ms232022-2-4n假定把磁盤上一個數(shù)據(jù)塊中的信息輸入到一單緩沖假定把磁盤上一個數(shù)據(jù)塊中的信息輸入到一單緩沖區(qū)的時間區(qū)的時間T為為100us，將緩沖區(qū)中的數(shù)據(jù)傳送到用戶，將緩沖區(qū)中的數(shù)據(jù)傳送到用戶區(qū)的時間為區(qū)的時間為50us，而，而CPU對這一塊數(shù)據(jù)進行計算對這一塊數(shù)據(jù)進行計算的時間為的時間為50us。這樣，系統(tǒng)對每一塊數(shù)據(jù)的處理。這樣，系統(tǒng)對每一塊數(shù)據(jù)的處理時間為時間為()；如果將單緩沖改為雙緩沖，則系統(tǒng)對每；如果將單緩沖改為雙緩沖，則系統(tǒng)對每一塊數(shù)據(jù)的處理時間為（）一塊數(shù)據(jù)的處理時間為（）nA、50us 、100us C、150us D、200usn

14、E、250us242022-2-4n緩沖技術中的緩沖池在緩沖技術中的緩沖池在_中中.A、內存、內存 、外存、外存 C、ROM D、寄存器、寄存器n如果如果I/O所花費的時間比所花費的時間比CPU處理時間短得多處理時間短得多的話的話,則緩沖區(qū)則緩沖區(qū)_.A、最有效、最有效 B、幾乎無效、幾乎無效C、均衡、均衡 D、以上都不是、以上都不是252022-2-4操作系統(tǒng)中采用緩沖技術的目的是為了增強系操作系統(tǒng)中采用緩沖技術的目的是為了增強系統(tǒng)（）能力；為了使多個進程能有效地同時統(tǒng)（）能力；為了使多個進程能有效地同時處理輸入和輸出，最好使用（）處理輸入和輸出，最好使用（）nA、串行操作、串行操作 、并行

15、操作、并行操作 C、控制操作、控制操作D、中斷操作中斷操作nA、緩沖池、緩沖池 、單緩沖、單緩沖 C、雙緩沖、雙緩沖 D、循環(huán)緩沖、循環(huán)緩沖n引入緩沖區(qū)能使引入緩沖區(qū)能使 CPU與與I/O設備之間速度不匹設備之間速度不匹配的情況得到改善，但并不能減少設備中斷配的情況得到改善，但并不能減少設備中斷CPU的次數(shù)。的次數(shù)。 （ ）262022-2-4n2011n2013272022-2-46.8 6.8 磁盤存儲器管理磁盤存儲器管理 目前，幾乎所有隨機存取的文件，都是目前，幾乎所有隨機存取的文件，都是存放在磁盤上，磁盤存放在磁盤上，磁盤I/O速度的高低將直接速度的高低將直接影響文件系統(tǒng)的性能。影響文

16、件系統(tǒng)的性能。282022-2-4n磁盤設備可包括一或多個盤片，每片分為兩磁盤設備可包括一或多個盤片，每片分為兩面，每面可分成若干條磁道，各磁道之間留面，每面可分成若干條磁道，各磁道之間留有必要的間隙，每條磁道上可存儲相同數(shù)目有必要的間隙，每條磁道上可存儲相同數(shù)目的二進制位。的二進制位。n磁盤密度：每英寸中所存儲的位數(shù)，顯然而磁盤密度：每英寸中所存儲的位數(shù)，顯然而內層磁道的密度較外層磁道的密度高。內層磁道的密度較外層磁道的密度高。n每條磁道又分成若干個扇區(qū)，每個扇區(qū)的大每條磁道又分成若干個扇區(qū)，每個扇區(qū)的大小相當于一個盤塊，各扇區(qū)之間也保留一定小相當于一個盤塊，各扇區(qū)之間也保留一定的間隙。的間

17、隙。6.8.1 磁盤性能簡述磁盤性能簡述292022-2-4柱面柱面扇區(qū)扇區(qū)磁臂磁臂磁頭磁頭側視圖側視圖302022-2-4磁道磁道扇區(qū)扇區(qū)俯視圖俯視圖312022-2-4n信息記錄在磁道上，多個盤片，正反兩面都信息記錄在磁道上，多個盤片，正反兩面都用來記錄信息，每面一個用來記錄信息，每面一個磁頭磁頭n所有盤面中處于同一磁道號上的所有磁道組所有盤面中處于同一磁道號上的所有磁道組成一個成一個柱面柱面n物理地址形式：物理地址形式：n 柱面號（磁道號）柱面號（磁道號）n 磁頭號磁頭號n 扇區(qū)號扇區(qū)號柱面、磁頭、扇區(qū)柱面、磁頭、扇區(qū)322022-2-4柱面、磁頭、扇區(qū)柱面、磁頭、扇區(qū)332022-2-

18、4柱面、磁頭、扇區(qū)柱面、磁頭、扇區(qū)342022-2-4典型參數(shù)典型參數(shù)n20G：n 39813 柱面柱面n 16 頭頭n 63 扇區(qū)扇區(qū)n60G：n 28733 柱面柱面n 16 頭頭n 255 扇區(qū)扇區(qū)352022-2-4n溫盤：溫盤：IBM公司推出的公司推出的Winchester(溫氏溫氏)硬硬盤，它的特點是：盤，它的特點是：“工作時，磁頭懸浮在高工作時，磁頭懸浮在高速轉動的盤片上方，而不與盤片直接接觸。速轉動的盤片上方，而不與盤片直接接觸。使用時，磁頭沿高速旋轉的盤片上做徑向移使用時，磁頭沿高速旋轉的盤片上做徑向移動動”，這便是現(xiàn)在所有硬盤的雛形。今天高，這便是現(xiàn)在所有硬盤的雛形。今天高

19、端硬盤容量雖然高達上百端硬盤容量雖然高達上百GB，但它卻仍然沒，但它卻仍然沒有脫離有脫離“溫徹斯特溫徹斯特”的動作模式。的動作模式。 磁盤的格式化磁盤的格式化362022-2-4n溫盤中一條磁道格式化的情況。每條磁道含溫盤中一條磁道格式化的情況。每條磁道含有有3030個固定大小的扇區(qū)，每個扇區(qū)容量為個固定大小的扇區(qū)，每個扇區(qū)容量為600600個字節(jié)，其中個字節(jié)，其中512512個字節(jié)存放數(shù)據(jù)，其余用作個字節(jié)存放數(shù)據(jù)，其余用作存放控制信息。每個扇區(qū)包括兩個字段：存放控制信息。每個扇區(qū)包括兩個字段：n標識符字段標識符字段n數(shù)據(jù)字段數(shù)據(jù)字段 磁盤的格式化磁盤的格式化372022-2-4磁盤的格式化磁

20、盤的格式化Gap102031292293Field Gap Field GapGap Field Gap Field Gap17741515201774151520IDDataIDDataGap1292293Field Gap Field1774151520IDDataSectorPhysical Sector 0Physical Sector 1Physical Sector 29BytesSynchByteTrack#Head#Sector#Bytes 1211CRC3SynchByteDataCRC15122600 Bytes/SectorGap圖 5-22 磁盤的格式化 382022-

21、2-4n常見的分類有常見的分類有: :n硬盤和軟盤硬盤和軟盤n單片盤和多片盤單片盤和多片盤n固定頭磁盤和活動頭磁盤固定頭磁盤和活動頭磁盤磁盤的類型磁盤的類型392022-2-4n固定頭磁盤：每個磁道設置一個磁頭，變換固定頭磁盤：每個磁道設置一個磁頭，變換磁道時不需要磁頭的機械移動，速度快但成磁道時不需要磁頭的機械移動，速度快但成本高本高n移動頭磁盤：一個盤面只有一個磁頭，變換移動頭磁盤：一個盤面只有一個磁頭，變換磁道時需要移動磁頭，速度慢但成本低磁道時需要移動磁頭，速度慢但成本低磁盤的類型磁盤的類型402022-2-4n磁盤啟動時，磁頭首先處于磁盤啟動時，磁頭首先處于0磁道，磁盤磁道，磁盤從接

22、到命令到向目標扇區(qū)讀取或寫入數(shù)據(jù)從接到命令到向目標扇區(qū)讀取或寫入數(shù)據(jù)完畢共經(jīng)歷三個階段：完畢共經(jīng)歷三個階段： u尋道尋道 ：磁頭沿徑向移動，移到目標扇區(qū)所在磁頭沿徑向移動，移到目標扇區(qū)所在磁道的上方（注意，不是目標扇區(qū)，而是目磁道的上方（注意，不是目標扇區(qū)，而是目標扇區(qū)所在的磁道）標扇區(qū)所在的磁道）u旋轉延遲：旋轉延遲：找到目標磁道后通過盤片的旋轉，找到目標磁道后通過盤片的旋轉，使得要目標扇區(qū)轉到磁頭的下方使得要目標扇區(qū)轉到磁頭的下方 u數(shù)據(jù)傳輸：數(shù)據(jù)在磁盤與內存之間的實際傳數(shù)據(jù)傳輸：數(shù)據(jù)在磁盤與內存之間的實際傳輸輸磁盤的訪問過程磁盤的訪問過程412022-2-4n尋道時間尋道時間Ts：這是指

23、把磁臂(磁頭)移動到指定磁道上所經(jīng)歷的時間。該時間是啟動磁臂的時間s與磁頭移動n條磁道所花費的時間之和， 即nTs=mn+sn其中，m是一常數(shù)，與磁盤驅動器的速度有關，對一般磁盤， m=0.2；對高速磁盤，m0.1, 磁臂的啟動時間約為2 ms。 這樣，對一般的溫盤， 其尋道時間將隨尋道距離的增加而增大， 大體上是530 ms。 磁盤的訪問時間磁盤的訪問時間422022-2-4n旋轉延遲時間旋轉延遲時間Tr：這是指定扇區(qū)移動到磁頭下面所經(jīng)歷的時間。對于硬盤，典型的旋轉速度大多為5400 r/min，每轉需時11.1 ms。n最大最小的平均值即旋轉半周的時間作為平均旋轉延遲時間，有的書上稱為平均

24、等待時間。平均旋轉延遲時間T為5.55 msn對于軟盤，其旋轉速度為300 r/min或600 r/min，這樣，平均T為50100 ms。磁盤的訪問時間磁盤的訪問時間432022-2-4磁盤的訪問時間磁盤的訪問時間n數(shù)據(jù)傳輸時間數(shù)據(jù)傳輸時間Tt：這是指把數(shù)據(jù)從磁盤讀出或向磁盤寫入數(shù)據(jù)所經(jīng)歷的時間。 Tt的大小與每次所讀/寫的字節(jié)數(shù)b和旋轉速度有關： rNbTtrNbrTTsa21其中，r為磁盤每秒鐘的轉數(shù)；N為一條磁道上的字節(jié)數(shù)， 當一次讀/寫的字節(jié)數(shù)相當于半條磁道上的字節(jié)數(shù)時，Tt與T相同， 因此， 可將訪問時間Ta表示為： 442022-2-4練習練習n若磁盤的轉速提高一倍，則_。n供選

25、擇的答案：供選擇的答案：nA. 平均存取時間減半 B. 平均尋道時間減半nC. 存儲道密度提高一倍 D. 平均尋道時間不變 452022-2-4磁盤的訪問時間磁盤的訪問時間n由此看出在訪問時間中，尋道時間和旋轉延遲時由此看出在訪問時間中，尋道時間和旋轉延遲時間基本上都與所讀寫數(shù)據(jù)的多少無關，而且它通間基本上都與所讀寫數(shù)據(jù)的多少無關，而且它通常占據(jù)了訪問時間的大頭。常占據(jù)了訪問時間的大頭。n適當?shù)募袛?shù)據(jù)傳輸將有利于提高傳輸效率適當?shù)募袛?shù)據(jù)傳輸將有利于提高傳輸效率462022-2-4練習練習n磁盤上的每一個物理塊要用三個參數(shù)來定位，首先磁盤上的每一個物理塊要用三個參數(shù)來定位，首先要把移動臂移動

26、并定位到不同盤面上具有相同編號要把移動臂移動并定位到不同盤面上具有相同編號的磁道位置，表示該位置的參數(shù)稱（）號。的磁道位置，表示該位置的參數(shù)稱（）號。A柱面柱面 B盤面盤面 C扇區(qū)扇區(qū) D磁頭磁頭n設磁盤的轉速為設磁盤的轉速為10ms/轉，盤面劃分轉，盤面劃分10個扇區(qū)，當個扇區(qū)，當前磁頭在第三塊的開始位置，則花費（）毫前磁頭在第三塊的開始位置，則花費（）毫秒的時間可以把第二塊的信息讀到主存（假設，旋秒的時間可以把第二塊的信息讀到主存（假設，旋轉是按由塊號從小到大方向的）轉是按由塊號從小到大方向的）nA、1B、2 C、9 D、10123472022-2-4分析分析n要提高磁盤的訪問速度主要應從

27、以下兩方面要提高磁盤的訪問速度主要應從以下兩方面入手：入手：n數(shù)據(jù)的合理組織數(shù)據(jù)的合理組織n磁盤的調度算法磁盤的調度算法482022-2-46.8.2 磁盤調度算法磁盤調度算法n當多個訪盤請求在等待時，采用一定的策略，對這當多個訪盤請求在等待時，采用一定的策略，對這些請求的服務順序調整安排，旨在降低平均磁盤服些請求的服務順序調整安排，旨在降低平均磁盤服務時間，達到公平、高效務時間，達到公平、高效n公平：一個公平：一個I/O請求在有限時間內滿足請求在有限時間內滿足n高效：減少設備機械運動所帶來的時間浪費高效：減少設備機械運動所帶來的時間浪費n1 先來先服務先來先服務FCFSn2 最短尋道時間優(yōu)先

28、最短尋道時間優(yōu)先SSTFn3 SCAN算法算法n4 循環(huán)掃描算法循環(huán)掃描算法CSCAN492022-2-4n根據(jù)進程請求訪問磁盤的先后次序進行調度根據(jù)進程請求訪問磁盤的先后次序進行調度n優(yōu)點：簡單，公平，每個進程的請求都能依優(yōu)點：簡單，公平，每個進程的請求都能依次得到處理；次得到處理；n缺點：效率不高，相鄰兩次請求可能會造成缺點：效率不高，相鄰兩次請求可能會造成最內到最外的柱面尋道，使磁頭反復移動，最內到最外的柱面尋道，使磁頭反復移動，增加了服務時間，對機械也不利增加了服務時間，對機械也不利n僅適應于請求磁盤僅適應于請求磁盤I/O的進程數(shù)目較少的場合的進程數(shù)目較少的場合1 先來先服務先來先服務

29、502022-2-4n假設磁盤訪問序列：假設磁盤訪問序列：98，183，37，122，14，124，65，67n讀寫頭起始位置：讀寫頭起始位置：53n安排磁頭服務序列安排磁頭服務序列n計算磁頭移動總距離（道數(shù)）計算磁頭移動總距離（道數(shù)）例例512022-2-4圖解圖解98，183，37，122，14，124，65，67磁頭走過的總道數(shù)：磁頭走過的總道數(shù)：640522022-2-4例例圖 5-23 FCFS調度算法532022-2-4n優(yōu)先選擇距當前磁頭最近的訪問請求進行優(yōu)先選擇距當前磁頭最近的訪問請求進行服務，主要考慮尋道優(yōu)先服務，主要考慮尋道優(yōu)先n 優(yōu)點：改善了磁盤平均服務時間；優(yōu)點：改善了

30、磁盤平均服務時間；n 缺點：造成某些訪問請求長期等待得不到缺點：造成某些訪問請求長期等待得不到服務，服務，“饑餓現(xiàn)象饑餓現(xiàn)象”2 最短尋道時間優(yōu)先最短尋道時間優(yōu)先542022-2-4圖解圖解65，67 ， 37， 14 ，98，122，124， 183 磁頭走過的總道數(shù)：磁頭走過的總道數(shù)：22498，183，37，122，14，124，65，67552022-2-4例例圖 5-24 SSTF調度算法 562022-2-4n克服了最短尋道優(yōu)先的缺點，既克服了最短尋道優(yōu)先的缺點，既考慮了距離考慮了距離，同時又同時又考慮了方向考慮了方向n具體做法：當設備無訪問請求時，磁頭不動；具體做法：當設備無訪問

31、請求時，磁頭不動；當有訪問請求時，磁頭按一個方向移動，在當有訪問請求時，磁頭按一個方向移動，在移動過程中對遇到的訪問請求進行服務，然移動過程中對遇到的訪問請求進行服務，然后判斷該方向上是否還有訪問請求，如果有后判斷該方向上是否還有訪問請求，如果有則繼續(xù)掃描；否則改變移動方向，并為經(jīng)過則繼續(xù)掃描；否則改變移動方向，并為經(jīng)過的訪問請求服務，如此反復的訪問請求服務，如此反復3 SCAN算法（電梯算法）算法（電梯算法）572022-2-4圖圖582022-2-4圖解圖解37，14， 65，67 ， 98， 122， 124， 183磁頭走過的總道數(shù)：磁頭走過的總道數(shù)：20898，183，37，122，

32、14，124，65，67592022-2-4例例圖 5-24 SCAN調度算法 602022-2-4n（磁頭單向移動）（磁頭單向移動）n電梯算法杜絕了饑餓，但當請求對磁道的電梯算法杜絕了饑餓，但當請求對磁道的分布是均勻時，磁頭回頭，近磁頭端的請分布是均勻時，磁頭回頭，近磁頭端的請求很少（因為磁頭剛經(jīng)過），而遠端請求求很少（因為磁頭剛經(jīng)過），而遠端請求較多，這些請求等待時間要長一些。較多，這些請求等待時間要長一些。例如：總是自里向外移動，當磁頭移動到最例如：總是自里向外移動，當磁頭移動到最外的磁道并訪問后，立即返回到最里的欲外的磁道并訪問后，立即返回到最里的欲訪問的磁道，返回時不為任何的等待訪問

33、訪問的磁道，返回時不為任何的等待訪問者服務。返回后可再次從里向外進行掃描者服務。返回后可再次從里向外進行掃描 。稱為循環(huán)掃描算法稱為循環(huán)掃描算法4 循環(huán)掃描調度算法循環(huán)掃描調度算法612022-2-4圖解圖解622022-2-4例例圖 5-24 CSCAN調度算法 632022-2-4n1) N-Step-SCAN算法n 在SSTF、 SCAN及CSCAN幾種調度算法中， 都可能出現(xiàn)磁臂停留在某處不動的情況， 例如，有一個或幾個進程對某一磁道有較高的訪問頻率， 即這個(些)進程反復請求對某一磁道的I/O操作，從而壟斷了整個磁盤設備。 我們把這一現(xiàn)象稱為“磁臂粘著”(Armstickiness)

34、。在高密度磁盤上容易出現(xiàn)此情況。 nN步SCAN算法是將磁盤請求隊列分成若干個長度為N的子隊列，磁盤調度將按FCFS算法依次處理這些子隊列。 而每處理一個隊列時又是按SCAN算法，對一個隊列處理完后，再處理其他隊列。 當正在處理某子隊列時，如果又出現(xiàn)新的磁盤I/O請求，便將新請求進程放入其他隊列，這樣就可避免出現(xiàn)粘著現(xiàn)象。 當N值取得很大時，會使N步掃描法的性能接近于SCAN算法的性能； 當N=1時， N步SCAN算法便蛻化為FCFS算法。 5 N-Step-SCAN和和FSCAN調度算法調度算法 642022-2-4n2) FSCAN算法n FSCAN算法實質上是N步SCAN算法的簡化， 即

35、FSCAN只將磁盤請求隊列分成兩個子隊列。一個是由當前所有請求磁盤I/O的進程形成的隊列，由磁盤調度按SCAN算法進行處理。在掃描期間，將新出現(xiàn)的所有請求磁盤I/O的進程， 放入另一個等待處理的請求隊列。這樣，所有的新請求都將被推遲到下一次掃描時處理。 5 N-Step-SCAN和和FSCAN調度算法調度算法 652022-2-4調度算法的選擇調度算法的選擇n實際系統(tǒng)相當普遍采用實際系統(tǒng)相當普遍采用最短尋道時間優(yōu)先算最短尋道時間優(yōu)先算法，因為它簡單有效，性價比好。法，因為它簡單有效，性價比好。n掃描算法更適于磁盤負擔重的系統(tǒng)。掃描算法更適于磁盤負擔重的系統(tǒng)。n磁盤負擔很輕的系統(tǒng)也可以采用先來先

36、服務磁盤負擔很輕的系統(tǒng)也可以采用先來先服務算法算法n一般要將磁盤調度算法作為操作系統(tǒng)的單獨一般要將磁盤調度算法作為操作系統(tǒng)的單獨模塊編寫，利于修改和更換。模塊編寫，利于修改和更換。662022-2-4練習練習活動頭磁盤的訪問時間包括活動頭磁盤的訪問時間包括_、_和和_。(1)什么是先來先服務磁盤調度調度算法什么是先來先服務磁盤調度調度算法?(2) 什么是最短尋道時間優(yōu)先磁盤調度算法什么是最短尋道時間優(yōu)先磁盤調度算法?(3) 什么是掃描磁盤調度算法什么是掃描磁盤調度算法? 磁盤調度主要是為了優(yōu)化磁盤調度主要是為了優(yōu)化_（1）尋道時間）尋道時間 （2）旋轉延遲時間）旋轉延遲時間 （3） 傳輸傳輸時

37、間時間672022-2-4練習練習n下列磁盤調度算法中，平均尋道時間較短，下列磁盤調度算法中，平均尋道時間較短，但容易產(chǎn)生饑餓現(xiàn)象的是（），電梯調度算但容易產(chǎn)生饑餓現(xiàn)象的是（），電梯調度算法是（），能避免磁臂粘著現(xiàn)象的算法是法是（），能避免磁臂粘著現(xiàn)象的算法是（）。（）。n（1）SSTF （2）FCFSn（3）SCAN （4）CSCANn（5）FSCANn在磁盤調度策略中有可能使在磁盤調度策略中有可能使I/O請求無限期等請求無限期等待的調度算法是待的調度算法是_. 682022-2-4練習練習n假定有一個具有假定有一個具有200個磁道（編號為個磁道（編號為0-199）的移動頭磁盤，在完成了磁道的移動頭磁盤，在完成了磁道125處的請求后，處的請求后，當前正在磁道當前正在磁道143處為一個請求服務。若請求處為一個請求服務。若請求隊列以隊列以FIFO次序存放，即次序存放，即86，147，91，177，94，150，102，175，130，計算下列，計算下列各算法中磁頭移動次數(shù)各算法中磁頭移動次數(shù)nFCFS SSTF SCAN CSCAN692022