設(shè)備管理2優(yōu)秀公開課課件

第五章設(shè)備管理MANAGINGI/ODEVICES5.1I/O系統(tǒng)的組成5.1.1I/O設(shè)備分類按傳輸速率:低速(<KB/s),中速,高速(>100KB/s)按塊設(shè)備:字符設(shè)備:按共享屬性分類獨占設(shè)備、共享設(shè)備、虛擬設(shè)備數(shù)據(jù)信號線設(shè)備到控制器的接口I/O設(shè)備狀態(tài)信號線控制信號線控制邏輯轉(zhuǎn)換器緩沖到設(shè)備控制器5.1.2設(shè)備控制器控制器是CPU與I/O設(shè)備之間的接口；接收從CPU發(fā)來的命令,并控制I/O設(shè)備工作?？刂破魇且粋€可編址設(shè)備,例如PC中硬盤控制器的I/O端口地址為1F0~1F7。

從物理上看,控制器是一塊接口卡或主板上的一個功能模塊。2.設(shè)備控制器的功能地址識別:識別I/O端口地址,使I/O操作與設(shè)備對應(yīng)。

接收和識別命令指揮設(shè)備執(zhí)行

接收CPU通過I/O總線發(fā)來的命令和參數(shù),存儲在控制器中相應(yīng)的控制寄存器中,并對它進行譯碼識別,轉(zhuǎn)換成適當(dāng)?shù)碾娦盘?通過控制器與設(shè)備的接口向設(shè)備發(fā)送,指揮設(shè)備執(zhí)行特定的操作。接收和記錄設(shè)備的狀態(tài)

接收從設(shè)備發(fā)來的電信號,進行轉(zhuǎn)換和解釋,變?yōu)樵O(shè)備的狀態(tài)信息,將此結(jié)果記錄在控制器的狀態(tài)寄存器上,供CPU了解。數(shù)據(jù)交換、數(shù)據(jù)緩沖、差錯控制實現(xiàn)CPU?控制器?設(shè)備的數(shù)據(jù)交換,從而實現(xiàn)了CPU到設(shè)備的數(shù)據(jù)傳遞和設(shè)備到CPU的數(shù)據(jù)傳遞。舉例:

典型的設(shè)備控制器是磁盤控制器,它從I/O總線上接收發(fā)來的諸如“寫這個數(shù)據(jù)塊”之類的高級命令,并對它進行譯碼識別,轉(zhuǎn)換成諸如“把磁頭定位在正確的磁道上”和“把數(shù)據(jù)寫入這個磁道”之類的低級磁盤操作的電信號,指揮磁盤驅(qū)動器執(zhí)行這些操作,每執(zhí)行一步都要將磁盤驅(qū)動器的發(fā)來的電信號進行轉(zhuǎn)換和解釋,變?yōu)樵O(shè)備的數(shù)據(jù)狀態(tài)信息,將此結(jié)果記錄在控制器的狀態(tài)寄存器上,供CPU了解。CPU根據(jù)此狀態(tài)信息確定下一步如何操作。設(shè)備文件設(shè)備文件是用來表示操作系統(tǒng)（Unix類）所支持的大部分I/O設(shè)備。設(shè)備文件的主要屬性：文件名、類型、主設(shè)備號、次設(shè)備號舉例5.1.3I/O通道

1.通道設(shè)備的引入為了建立獨立的I/O操作

I/O傳送獨立、I/O組織管理獨立把CPU從繁雜的I/O任務(wù)中解脫出來

CPU只需向通道發(fā)出一條I/O指令。減輕單總線的負擔(dān),增加I/O通道I/O通道的特點

I/O通道是一種特殊的處理機具有執(zhí)行I/O指令的能力通過執(zhí)行通道程序來控制I/O操作指令類型單一,沒有自己的內(nèi)存2.通道類型字節(jié)多路通道(p149圖5-3)

含有許多非分配型子通道(幾十到幾百),每個子通道連結(jié)一臺低速或中速字節(jié)設(shè)備,子通道按時間片輪轉(zhuǎn)方式共享主通道,只要掃描一輪的速率足夠塊,便不會丟失信息。數(shù)組選擇通道可連結(jié)多臺高速塊設(shè)備,但由于只含有一個分配型子通道,當(dāng)某臺設(shè)備占用了該通道,便由它獨占,直到用完釋放為止,顯然它的利用率低。數(shù)組多路通道將以上兩種結(jié)合,它含有多個非分配型子通道,極有很高的傳輸速率,又有滿意的通道利用率。3.解決瓶頸問題通道往往成為I/O的瓶頸如圖:(p149圖5-4)存儲器通道1通道2控制器1控制器2控制器3控制器4設(shè)備1設(shè)備2設(shè)備3設(shè)備4設(shè)備5設(shè)備6設(shè)備75.1.4總線型I/O系統(tǒng)

1.微機I/O系統(tǒng)控制器與設(shè)備接口磁盤控制器打印機控制器磁盤驅(qū)動器打印機內(nèi)存CPUPC的I/O體系結(jié)構(gòu)CPUI/O總線I/O端口I/O控制器I/O端口I/O設(shè)備控制器與設(shè)備接口I/O端口(I/Oport)每個連接到I/O總線上的設(shè)備控制器都有自己的I/O地址集,即一組I/O端口,所以每個設(shè)備對應(yīng)一組端口;在IBMPC體系結(jié)構(gòu)中,I/O地址空間共提供了65,536個8位I/O端口。(I/O總線)

有四條專用匯編指令允許CPU對I/O端口進行讀寫。 即：in、ins、out和outs

在執(zhí)行指令時,CPU用地址總線選擇所請求的I/O端口,用數(shù)據(jù)總線在CPU和設(shè)備控制器之間傳送數(shù)據(jù)。5.1.4總線技術(shù)1.總線的基本概念：在計算機系統(tǒng)內(nèi)各種子系統(tǒng)如CPU、內(nèi)存、I/O設(shè)備等之間構(gòu)建公用的信號或數(shù)據(jù)傳輸通道這種可共享連接的傳輸通道稱為總線總線的分類CPU-內(nèi)存總線I/O總線數(shù)據(jù)總線地址總線控制總線（非本課程范圍）2.總線的分類微型計算機總線的種類和發(fā)展PC／XT總線ISA總線EISA總線VESA總線PCI總線USB總線…...1394總線SCSI總線3.USB技術(shù)

USB(UniversalSerialBus)通用串行總線,是一種連接I/O串行設(shè)備的技術(shù)標準沖破了計算機技術(shù)發(fā)展的兩個歷史局限性：（1）由于I/O設(shè)備的接口標準的不一致和有限的接口數(shù)量已無法滿足各種應(yīng)用迫切需要（2）傳統(tǒng)的I/O設(shè)備的接口無法滿足實時數(shù)據(jù)傳輸與多媒體應(yīng)用的需求

USB以WDM(WindowsDriverModel)模型為基礎(chǔ)，WDM含通用的I/O服務(wù)和二進制兼容的設(shè)備驅(qū)動程序

USB支持同步數(shù)據(jù)傳輸方式和異步數(shù)據(jù)傳輸方式,其數(shù)據(jù)傳輸率有低速1.5Mbps和全速12Mbps兩種,比標準串口快100倍，比標準并口快10倍

USB可以主動為外部設(shè)備提供電源,允許外部設(shè)備快速連接,具有即插即用的功能

USB允許外部設(shè)備的熱插拔5.即插即用技術(shù)(PlugandPlay）插入就可用，不需要進行任何設(shè)置操作PnP技術(shù)的產(chǎn)生由于一個系統(tǒng)可以配置多種外部設(shè)備,設(shè)備也經(jīng)常變動和更換,它們都要占有一定的系統(tǒng)資源，彼此間在硬件和軟件上可能會產(chǎn)生沖突。因此在系統(tǒng)中要正確地對它們進行配置和資源匹配;當(dāng)設(shè)備撤除、添置和進行系統(tǒng)升級時,配置過程往往是一個困難的過程。PnP技術(shù)的特點：（1）支持I/O設(shè)備及部件的自動配置，使用戶能夠簡單方便地使用系統(tǒng)擴充設(shè)備（2）減少由制造商裝入的種種用戶支持和限制，簡化部件的硬件跳接設(shè)置，使I/O附加卡和部件不再具有人工跳接線設(shè)置電路（3）在主機板和附加卡上保存系統(tǒng)資源的配置參數(shù)和分配狀態(tài)，有利于系統(tǒng)對整個I/O資源的分配和控制（4）支持和兼容各種操作系統(tǒng)平臺，具有很強的擴展性和可移植性。（5）在一定程度上具有"熱插入"、"熱拼接"技術(shù)5.2I/O控制方式程序I/O方式中斷驅(qū)動I/O控制方式

DMA控制方式

I/O通道控制方式5.2.2中斷驅(qū)動I/O控制方式當(dāng)某進程要啟動某個I/O設(shè)備工作時,便由CPU向相應(yīng)的設(shè)備控制器發(fā)出一條I/O指令,然后立即返回繼續(xù)繼續(xù)執(zhí)行原來的任務(wù)。設(shè)備控制器便按該指令的要求去控制指定的I/O設(shè)備。此時,CPU可以去做其它事情與I/O設(shè)備并行工作。例如,在輸入時,當(dāng)設(shè)備控制器收到CPU發(fā)來的讀命令后,便去控制相應(yīng)的輸入設(shè)備讀數(shù)據(jù)。數(shù)據(jù)進入數(shù)據(jù)寄存器后,設(shè)備控制器通過中斷控制器和控制總線向CPU發(fā)出中斷信號,CPU響應(yīng)中斷,讀設(shè)備控制器狀態(tài)檢查是否出錯,若無錯,則通過數(shù)據(jù)總線從設(shè)備控制器中讀出數(shù)據(jù),寫入存儲器。P152圖5-7(b)CPUI/OI/OCPUI/OCPUCPU內(nèi)存向I/O控制器發(fā)讀命令啟動輸入機讀I/O控制器狀態(tài)檢查狀態(tài)就緒出錯從I/O控制器中讀字向存儲器中寫字P152圖5-7(b)完成？NY下條指令從輸入機讀字到控制器數(shù)據(jù)寄存器CPU作其它事響應(yīng)中斷中斷請求request_irq()函數(shù)原形intrequest_irq(

unsignedintirq,/*中斷請求號*/

void(*handler)(int,void*,structpt_regs*),

/*指向中斷服務(wù)子程序*/

unsignedlongirqflags,/*中斷類型*/

constchar*devname,/*設(shè)備的名字*/

void*dev_id

/*設(shè)備標識符*/)；中斷描述符表(IDT)

中斷服務(wù)程序(及異常處理程序)的入口地址依照中斷源位置組成IDT表,入口地址就是中斷門(中斷向量)。

LinuxIDT表共有256個中斷向量,即0至255,其中0到31由Intel公司留給異常事件處理程序。

CPU根據(jù)IDT表和中斷源,可轉(zhuǎn)入相應(yīng)的中斷服務(wù)程序中斷處理程序執(zhí)行的四個基本操作在內(nèi)核棧中保存IRQ的值和寄存器的內(nèi)容。為正在給IRQ線服務(wù)的PIC發(fā)送一個應(yīng)答,這將允許

PIC進一步發(fā)出中斷。執(zhí)行共享這個IRQ的所有設(shè)備的中斷服務(wù)例程(ISR)

跳到ret_from_intr()的地址后中斷結(jié)束。把IRQ分配給I/O設(shè)備的一個例子IRQ 中斷向量 硬件設(shè)備0 32 時鐘1 33 鍵盤2 34 PIC級連3 35 第二個串口4 36 第一個串口6 38 軟盤8 40 系統(tǒng)時鐘11 43 網(wǎng)絡(luò)接口12 44 PS/2鼠標13 45 數(shù)學(xué)協(xié)處理器14 46 EIDE磁盤控制器的一級鏈15 47 EIDE磁盤控制器的二級鏈5.2.3DMA(directmemoryaccess)控制方式DMA控制方式的引入中斷方式是以字節(jié)(字)為單位進行I/O的,每完成一個字節(jié)(字)CPU要處理一次中斷,這種方法用于塊設(shè)備效率極低,為了進一步減少CPU對I/O的干預(yù),提高CPU與I/O設(shè)備的并行讀引入DMA控制方式。

DMA方式的特點為：數(shù)據(jù)傳送的基本單位是數(shù)據(jù)塊。數(shù)據(jù)是直接在設(shè)備─內(nèi)存之間傳送的。僅在傳送一個或多個數(shù)據(jù)塊的開始和結(jié)束時才需要CPU對I/O的干預(yù),傳送工作本身是由DMA控制器完成的。DMA控制器的組成主機與DMA控制器的接口數(shù)據(jù)寄存器(DR)

內(nèi)存地址寄存器(MAR)數(shù)據(jù)計數(shù)器(DC)命令/狀態(tài)寄存器(CR)DMA控制器與塊設(shè)備的接口I/O控制邏輯DRMARDCCRI/O控制邏輯塊設(shè)備接口控制器與內(nèi)存CPUcoutDMA方式從磁盤讀入數(shù)據(jù)塊的工作流程:P154圖5-9

CPU將讀命令發(fā)送到控制器的寄存器CR將目標地址和數(shù)據(jù)計數(shù)送到MAR和DC中將磁盤的源地址送至它的I/O控制邏輯上啟動DMA傳送命令先從磁盤讀入數(shù)據(jù)字送到DR再挪用存儲器周期將數(shù)據(jù)送到內(nèi)存存儲器地址增加1字計數(shù)器DC減1DC=0請求中斷CPU做其他工作CPU讀DMA的狀態(tài)CR繼續(xù)下條指令響應(yīng)中斷NYDMA工作原理——竊取總線控制權(quán)存放輸入數(shù)據(jù)的內(nèi)存起始地址、要傳送的字節(jié)數(shù)送入

DMA控制器的內(nèi)存地址寄存器和傳送字節(jié)計數(shù)器;中斷允許位和啟動位置成1,啟動設(shè)備。發(fā)出傳輸要求進程進入等待狀態(tài),其他進程占據(jù)CPU。DMA控制器不斷竊取總線控制權(quán),數(shù)據(jù)不斷寫入內(nèi)存。傳送完畢,發(fā)出中斷信號。

CPU接到中斷信號轉(zhuǎn)入中斷處理程序處理。中斷處理結(jié)束,CPU返回原進程或切換到新的進程。DMA方式與中斷的主要區(qū)別中斷方式的數(shù)據(jù)傳送到存儲器是由CPU控制完成的。而DMA方式的數(shù)據(jù)傳送到存儲器則不經(jīng)過CPU,由DMA控制器直接完成。中斷方式在設(shè)備控制器的數(shù)據(jù)緩沖寄存區(qū)滿后,發(fā)中斷請求,CPU進行中斷處理將緩沖區(qū)數(shù)據(jù)傳送到內(nèi)存。而DMA方式則是在所要求傳送的數(shù)據(jù)塊全部傳送到內(nèi)存結(jié)束時,發(fā)中斷請求,CPU進行中斷處理。大大減少了CPU進行中斷處理的次數(shù)和時間。

DMA控制器按目標存儲地址,從第一字(節(jié))開始,反復(fù)進行數(shù)據(jù)傳送(竊取總線控制權(quán)),每傳一字節(jié),計數(shù)器值減1;直到值為0時,發(fā)出中斷請求,通知CPU操作完成。

CPU提供命令被讀塊磁盤地址目標存儲地址待讀取字節(jié)數(shù)DMA工作示例(以硬盤為例)

CPU發(fā)出命令后去處理其它任務(wù)。MARDCCR內(nèi)存CPUcout磁盤接口DR內(nèi)存地址計數(shù)器命令/狀態(tài)I/O控制邏輯5.2.4I/O通道控制方式1.通道控制方式的引入

DMA方式傳送的是連續(xù)的數(shù)據(jù)塊。當(dāng)需要一次讀多個離散的數(shù)據(jù)塊并將它們傳送到不同的內(nèi)存區(qū)域時。怎么辦？為了進一步減少CPU對I/O的干預(yù)引入通道控制方式,它是DMA方式的發(fā)展。

DMA方式由控制器的I/O控制邏輯來執(zhí)行讀、寫等I/O操作,只能傳送一個連續(xù)的數(shù)據(jù)塊。而通道方式則由通道內(nèi)的通道程序來指揮控制器并由控制器執(zhí)行I/O操作,比較靈活,能傳送多個連續(xù)數(shù)據(jù)塊。2.通道程序通過執(zhí)行通道程序,并與設(shè)備控制器共同完成對I/O設(shè)備的控制,通道程序的每條指令含如下信息:操作碼,內(nèi)存地址,計數(shù),結(jié)束位P,記錄結(jié)束R通道可實現(xiàn)CPU、通道和I/O設(shè)備三者并行工作。例：操作PR計數(shù)內(nèi)存起始地址Write0080810Write001401340Write01605810Write013002000Write002501650Write112502820課后題P1812,4,6,8以一個具體的實例全面描述中斷處理過程（如時鐘中斷、鍵盤中斷等等）。以ISA（或PCI）總線的DMA為例，說明DMA的工作過程。（以上說明可以結(jié)合具體的操作系統(tǒng)）5.3緩沖管理為什么要使用緩沖？由哪幾種緩沖方式？緩沖區(qū)處在何處？緩沖區(qū)由誰管理？怎樣管理？5.3.1為什么引入緩沖緩和CPU與I/O設(shè)備速度不匹配的矛盾減少對CPU的中斷頻率，放寬對中斷響應(yīng)時間的限制。提高CPU和設(shè)備之間的并行性5.3.2I/O緩沖方式1.單緩沖(SingleBuffer)塊設(shè)備輸入時,輸入到緩沖區(qū)的時間為T,OS將數(shù)據(jù)從緩沖區(qū)傳到用戶區(qū)的時間為M,CPU處理這塊數(shù)據(jù)的時間為C;顯然T和C是可以并行的。T1M1C1T2M2C2T3M3C3T4工作區(qū)緩沖區(qū)輸入(T)傳送(M)I/O設(shè)備處理(C)用戶進程字符設(shè)備輸入輸出時,緩沖區(qū)用于暫存一行數(shù)據(jù)。2.雙緩沖(DoubelBuffer)

為了加快I/O速度提高設(shè)備利用率,又引入了雙緩沖機制(緩沖對換BufferS);如果C<T,塊設(shè)備可連續(xù)輸入。T1(緩沖1)M1C1T2(緩沖2)M2C2T3(緩沖1)M3C3T4(緩沖2)工作區(qū)緩沖區(qū)1I/O設(shè)備緩沖區(qū)2用戶進程如果要實現(xiàn)兩臺機器之間同時雙向通信,必須在兩臺機器中都設(shè)置兩個緩沖區(qū),一個發(fā)送一個接收。3.循環(huán)緩沖

I/O進程和計算進程對緩沖區(qū)的使用相當(dāng)于生產(chǎn)者消費者問題,當(dāng)兩者之間速度基本相匹配時,雙緩沖能獲得較好的效果,但兩者之間速度變化很大相差很遠時效果不理想;可將多個緩沖組成循環(huán)形式。以輸入為例,空緩沖區(qū)為R,已裝滿數(shù)據(jù)的緩沖區(qū)為G,正在使用的工作緩沖區(qū)為C,使用時要考慮進程的同步:RRGGGGNextiNextgRRCGGGNextiCurrentNextg當(dāng)計算進程要用緩沖區(qū)的數(shù)據(jù)時調(diào)用Getbuf(Nextg)過程,將Nextg指示的緩沖區(qū)提供給計算進程使用,并令Current指針指向它的第一單元,Nextg移向下一個G。當(dāng)輸入進程要空緩沖區(qū)輸入數(shù)據(jù)時調(diào)Getbuf(Nexti)過程,將Nexti指示的緩沖區(qū)供給輸入進程,Nexti下移。當(dāng)計算進程把當(dāng)前緩沖區(qū)C中的數(shù)據(jù)提取完時,調(diào)用Releasebuf()過程,將該空緩沖區(qū)釋放,將其狀態(tài)該為R。當(dāng)輸入進程把緩沖區(qū)裝滿時,也應(yīng)調(diào)用Releasebuf()過程,將該空緩沖區(qū)釋放,將其狀態(tài)該為G。

注意:計算進程和輸入進程的同步,Nexti和Nextg追趕。5.3.3緩沖池(BufferPool)1.緩沖池的組成空緩沖鏈隊列emp:由空緩沖區(qū)組成輸入緩沖鏈隊列inq:由裝滿輸入數(shù)據(jù)的緩沖區(qū)組成輸出緩沖鏈隊列out:由裝滿輸出數(shù)據(jù)的緩沖區(qū)組成4種工作緩沖區(qū)收容輸入、提取輸入、收容輸出、提取輸出。從某隊列上取下來操作完后再掛到另一隊列上2.對緩沖池隊列操作的兩個過程緩沖池中的隊列是臨界資源要考慮互斥與同步3.緩沖區(qū)工作方式提取輸出收容輸入提取輸入收容輸出緩沖池hinsinsouthout用戶程序empinqout收容輸入的工作方式:當(dāng)輸入進程需要輸入數(shù)據(jù)時調(diào)用Getbuf(emp,hin)過程,從emp隊列首摘下空緩沖區(qū)作為收容輸入工作緩沖區(qū)hin(2)把數(shù)據(jù)輸入到工作緩沖區(qū)hin(3)調(diào)用Putbuf(inq,hin),將hin掛到inq隊列尾提取輸入工作方式：當(dāng)計算進程需要提取輸入數(shù)據(jù)時(1)調(diào)用Getbuf(inq,sin)過程,從inq隊列頭摘下緩沖區(qū)作為提取輸入工作緩沖區(qū)sin(2)計算進程從工作緩沖區(qū)sin中提取數(shù)據(jù)(3)調(diào)用Putbuf(emp,sin),將sin掛在emp隊列尾ProcedureGetbuf(q,buf);從q隊列頭摘下緩沖區(qū)bufbeginWait(RS(q));信號量RS(q)是隊列q的長度Wait(MS(q));MS(q)是對q操作的互斥信號量buf:=Takbuf(q);Signal(MS(q));endProcedurePutbuf(q,buf);buf加到q隊列的隊尾beginWait(MS(q));Addbuf(q,buf);Signal(MS(q))Signal(RS(q));end5.4設(shè)備分配多道程序環(huán)境下用戶進程提出I/O請求，設(shè)備分配程序按一定策略把用戶所需的設(shè)備分配給用戶進程。OS是怎樣對設(shè)備進行分配的？采用了哪些數(shù)據(jù)結(jié)構(gòu)？5.4.1設(shè)備分配中的數(shù)據(jù)結(jié)構(gòu)具有通道的I/O系統(tǒng)結(jié)構(gòu)存儲器通道1通道2控制器1控制器2設(shè)備1設(shè)備2設(shè)備3設(shè)備41.系統(tǒng)設(shè)備表（SDT）表目1...表目i...設(shè)備類型設(shè)備標識符設(shè)備狀態(tài):忙/閑等待控制器通道標志指向控制器表的指針重復(fù)執(zhí)行次數(shù)或時間驅(qū)動程序入口設(shè)備控制表DCT系統(tǒng)設(shè)一張系統(tǒng)設(shè)備表,紀錄系統(tǒng)中全部設(shè)備的情況,每個設(shè)備占一個表目。2.控制器控制表、通道控制表COCTCHCT每個控制器設(shè)一張COCT,每個通道設(shè)一張CHCT控制器標識符控制器狀態(tài):忙/閑指向相連通道表的指針控制器隊列的首指針控制器隊列的尾指針通道標識符通道狀態(tài):忙/閑相連控制器表的指針通道隊列的首指針通道隊列的尾指針5.4.2設(shè)備分配時涉及的問題1.設(shè)備的固有屬性獨占、共享、虛擬2.設(shè)備分配算法先來先服務(wù)、優(yōu)先級高者優(yōu)先3.設(shè)備分配的安全性安全分配方式:進程發(fā)出I/O請求便被阻塞直到I/O完成不安全分配方式:進程發(fā)出I/O請求后繼續(xù)執(zhí)行,需要時又發(fā)出第二個第三個I/O請求,滿足請求保持條件可能引起死鎖。進程推進速度塊。4.設(shè)備的獨立性5.4.3設(shè)備獨立性1.設(shè)備獨立性(DeviceIndependence)為了提高OS的可適應(yīng)性和可擴展性,現(xiàn)代OS都實現(xiàn)了設(shè)備獨立性(設(shè)備無關(guān)性),引入了邏輯設(shè)備和物理設(shè)備兩個概念,使應(yīng)用程序用邏輯設(shè)備名來請求某類設(shè)備,獨立于具體的物理設(shè)備。OS將邏輯設(shè)備名轉(zhuǎn)換為具體的物理設(shè)備。帶來的好處是:(1)設(shè)備分配的靈活性(2)易于實現(xiàn)I/O的重定向2.設(shè)備獨立性軟件(1)執(zhí)行所有設(shè)備的公有操作對獨立設(shè)備的分配和回收將邏輯設(shè)備名映射為物理設(shè)備名找到驅(qū)動程序?qū)υO(shè)備進行保護緩沖管理差錯控制(2)向用戶層軟件提供統(tǒng)一接口

I/O軟件組織成一種層次結(jié)構(gòu),低層軟件用來屏蔽具體設(shè)備細節(jié),高層軟件則為用戶提供一個簡潔規(guī)范的界面。它體現(xiàn)了I/O設(shè)計的關(guān)鍵的概念:設(shè)備無關(guān)性,其含義就是使程序員寫的軟件無須修改,就能進行不同設(shè)備上的I/O操作。如對各種設(shè)備的讀操作都使用read;對各種設(shè)備的寫操作都使用write。I/O軟件的層次結(jié)構(gòu)及功能進行I/O;格式化I/O命名;保護;緩沖;分配;阻塞建立設(shè)備寄存器;檢測狀態(tài)I/O結(jié)束時喚醒服務(wù)子程序執(zhí)行I/O操作中斷處理程序設(shè)備驅(qū)動程序設(shè)備無關(guān)軟件I/O應(yīng)答I/O請求用戶進程硬件3.邏輯設(shè)備名到物理設(shè)備名映射(1)邏輯設(shè)備表(LUT)邏輯設(shè)備名物理設(shè)備名 驅(qū)動程序入口地址/dev/tty 3 1024/dev/print 5 2048(2)邏輯設(shè)備表的設(shè)置整個系統(tǒng)只設(shè)一張LUT不允許有相同的邏輯設(shè)備名,用在單用戶系統(tǒng)中。每個用戶設(shè)一張LUT,用戶登錄建立進程時,建立一張LUT并將該表放入該進程的PBC中,用在多用戶系統(tǒng)中。(1)分配設(shè)備:根據(jù)物理設(shè)備名,查找系統(tǒng)設(shè)備表SDT,找出該設(shè)備的設(shè)備控制表DCT,再根據(jù)DCT中的設(shè)備狀態(tài)字忙否執(zhí)行,若忙將請求I/O的進程掛在設(shè)備等待隊列上,否則檢查安全性,安全則分配。(2)分配控制器:分到設(shè)備后,再到DCT中找出與之連結(jié)的控制器控制表COCT,再根據(jù)COCT中的狀態(tài)字忙否執(zhí)行等待或分配控制器。(3)分配通道:在COCT中找到與之連結(jié)的通道控制表CHCT,再根據(jù)CHCT中的狀態(tài)字忙否執(zhí)行等待或分配通道。5.4.4獨占設(shè)備的分配程序5.4.5SPOOLing技術(shù)

SimultaneousPeripheralOperationsOn-Line

脫機輸入輸出是利用外圍機脫機進行I/O操作。

SPOOLing是聯(lián)機情況的同時外圍操作(假脫機操作)用輸入進程SPI模擬脫機輸入時外圍機的功能,把低速輸入設(shè)備的數(shù)據(jù)送到高速磁盤上。用輸出進程SPO模擬脫機輸出時外圍機的功能,把高速磁盤的數(shù)據(jù)送到低速輸出設(shè)備上。SPOOLing系統(tǒng)特點提高了I/O速度,緩和CPU高速與I/O慢速的矛盾。將獨占設(shè)備改造為共享設(shè)備。實現(xiàn)虛擬設(shè)備,一臺物理設(shè)備變?yōu)槎嗯_邏輯設(shè)備。SPOOLing系統(tǒng)的組成(1)輸入井、輸出井:收容輸入/出的數(shù)據(jù)(2)輸入/出緩沖區(qū)Bi/Bo:內(nèi)存緩沖區(qū),暫存輸入/出數(shù)據(jù)(3)輸入/出進程SPi/SPo:模擬脫機輸入/出時的外圍機輸入緩沖區(qū)Bi輸出緩沖區(qū)Bo高速磁盤輸入進程SPi輸出進程SPo輸入井輸出井輸入設(shè)備輸出設(shè)備實例:共享打印機把一臺打印機改造為多個用戶可共享(1)由輸出進程SPo將打印的數(shù)據(jù)從內(nèi)存送到輸出井(2)由SPo將用戶要求填入請求打印表中,并將請求打印表掛到請求打印隊列上(4)若打印機空閑,SPo將從請求打印隊列的隊首取一張請求打印表,根據(jù)打印要求將打印數(shù)據(jù)從輸出井送到Bo,再由打印機打印。課后題:P18110,12,14,185.5設(shè)備驅(qū)動5.5.1設(shè)備驅(qū)動程序的功能和特點1.設(shè)備驅(qū)動程序的功能(1)將接受到的抽象(邏輯)要求轉(zhuǎn)化為具體(物理)要求。(2)檢查用戶I/O請求的合法性,讀出和檢查I/O設(shè)備的狀態(tài),傳遞有關(guān)參數(shù),設(shè)置設(shè)備的工作方式。(3)發(fā)出I/O命令,若設(shè)備空閑則啟動的I/O設(shè)備,否則將請求進程掛到設(shè)備等待隊列上。(4)及時響應(yīng)由控制器或通道發(fā)來的中斷請求,并根據(jù)中斷類型調(diào)用相應(yīng)的中斷處理程序進行處理。(5)對于設(shè)置通道的計算機系統(tǒng),驅(qū)動程序還應(yīng)能夠根據(jù)用戶的I/O請求,自動地構(gòu)造通道程序。2.設(shè)備處理方式(1)為每類設(shè)備設(shè)置一個I/O進程。(2)整個系統(tǒng)設(shè)置一個I/O進程。(3)只為各類設(shè)備設(shè)置相應(yīng)的設(shè)備處理程序供調(diào)用。3.設(shè)備驅(qū)動程序的特點(1)驅(qū)動程序主要是在請求I/O的進程與設(shè)備控制器之間的一個通信程序。(2)驅(qū)動程序與I/O設(shè)備的特性密切相關(guān)。(3)驅(qū)動程序與I/O控制方式相關(guān)。(4)有些驅(qū)動程序固化在ROM上。將抽象的要求轉(zhuǎn)化為具體的要求如:將邏輯盤塊號轉(zhuǎn)換為具體的盤面、磁道和扇區(qū)2.檢查I/O請求的合法性如:打印機請求讀,以讀方式打開磁盤后請求寫3.讀出并檢查設(shè)備的狀態(tài)如:讀并查狀態(tài)是否為就緒,確定啟動控制器或等待4.傳送必要的參數(shù)如:啟動磁盤,先將字節(jié)數(shù)和內(nèi)存起始地址送控制器5.工作方式的設(shè)置如:異步通信,先設(shè)置波特率、校驗方式、停止位等6.啟動I/O設(shè)備:向控制器發(fā)送控制命令,

將自己阻塞進入睡眠狀態(tài)。由控制器控制下進行指定的I/O操作。7.完成I/O后,設(shè)備控制器向CPU發(fā)出中斷請求;CPU響應(yīng)轉(zhuǎn)向中斷處理程序喚醒相應(yīng)的設(shè)備驅(qū)動進程。5.5.2設(shè)備驅(qū)動程序的處理過程在設(shè)備控制器的控制下,設(shè)備完成I/O操作后,設(shè)備控制器便向CPU發(fā)出一個中斷請求;CPU響應(yīng)后,轉(zhuǎn)向中斷處理程序,中斷處理含以下幾個步驟：(1)喚醒被阻塞的驅(qū)動(程序)進程(2)保護被中斷進程的CPU環(huán)境(3)分析中斷原因轉(zhuǎn)入相應(yīng)的設(shè)備處理程序(4)進行中斷處理(5)恢復(fù)被中斷進程的現(xiàn)場5.5.3I/O完成中斷處理程序的處理過程恢復(fù)被中斷進程的現(xiàn)場繼續(xù)執(zhí)行被中斷進程喚醒被阻塞的驅(qū)動程序進程保護被中斷進程的CPU環(huán)境分析中斷原因轉(zhuǎn)入相應(yīng)的設(shè)備處理程序打印機中斷處理程序鍵盤中斷處理程序…5.5.4Linux設(shè)備管理提供一個統(tǒng)一而簡單的I/O系統(tǒng)調(diào)用接口。

I/O子系統(tǒng)可分為上下兩部分：下層:與設(shè)備有關(guān)的稱為設(shè)備驅(qū)動程序。上層:與設(shè)備無關(guān)的,根據(jù)I/O請求,通過特定設(shè)備驅(qū)動程序接口,與設(shè)備進行通信。一、設(shè)備驅(qū)動程序基礎(chǔ)總線I/O空間I/O數(shù)據(jù)傳送字符設(shè)備與塊設(shè)備主設(shè)備號與次設(shè)備號設(shè)備文件設(shè)備驅(qū)動程序接口1.總線

CPU和I/O設(shè)備是通過總線連接起來的?？偩€定義了設(shè)備之間進行通訊的協(xié)議；遵循同一種協(xié)議的硬件可在同一條總線上協(xié)調(diào)工作。常用PC總線：ISA、VESA、EISA、PCI等。2.I/O空間計算機的I/O空間由所有設(shè)備的寄存器組成。

I/O空間的配置分為兩種情況：

I/O空間與內(nèi)存空間相互獨立：如intel386

I/O寄存器作為內(nèi)存的一部分：如Motorla680x0

對于要使用專門的I/O語句：inb和outb

Linux系統(tǒng)所使用的I/O空間,可以查看文件：/proc/ioports:3.I/O數(shù)據(jù)傳送查詢、中斷、DMA4.字符設(shè)備與塊設(shè)備字符設(shè)備:按順序訪問,不使用緩沖技術(shù)。塊設(shè)備:隨機訪問,使用緩沖技術(shù)。Linux所使用的設(shè)備查看文件:/proc/devices5.主設(shè)備號和次設(shè)備號主設(shè)備號相同設(shè)備用相同驅(qū)動程序。次設(shè)備號用來區(qū)分具體設(shè)備實例。主設(shè)備號和次設(shè)備號共同來標識一個具體設(shè)備。6.設(shè)備驅(qū)動程序接口

I/O子系統(tǒng)向內(nèi)核其它部分提供了統(tǒng)一標準的設(shè)備接口,通過結(jié)構(gòu)實現(xiàn)。struct{lseek()；/*重新定位讀寫位置*/read();/*從設(shè)備中讀數(shù)據(jù)*/write()；/*向設(shè)備寫數(shù)據(jù)*/readdir()；/*無用,只用于文件系統(tǒng),而非設(shè)備*/

ioctl()；/*控制字符設(shè)備*/mmap()；/*將設(shè)備內(nèi)存映射到進程地址空間*/

open()；/*打開并初始化設(shè)備;可以為NULL,這樣每次打開設(shè)備總會成功,而且不通知設(shè)備驅(qū)動程序*/

release()；/*關(guān)閉設(shè)備,并釋放資源*/fsync()；/*實現(xiàn)內(nèi)存與設(shè)備(如硬盤)間的同步*/

fasync()；/*實現(xiàn)內(nèi)存與設(shè)備(如鼠標)間的異步通信*/check_media_change();/*用來檢查設(shè)備介質(zhì)(如軟盤)是否自上次操作后發(fā)生了變化,僅用于塊設(shè)備*/revalidate();/*僅用于塊設(shè)備,該函數(shù)與緩沖區(qū)有關(guān)*/};Linux內(nèi)核為了將來自硬件設(shè)備的中斷傳遞到相應(yīng)的設(shè)備驅(qū)動程序,在驅(qū)動程序初始化的時候就將其對應(yīng)的中斷程序進行了登記,即通過調(diào)用函數(shù)request_irq()使中斷號和中斷服務(wù)子程序聯(lián)系起來。函數(shù)原形為：intrequest_irq(unsignedintirq,/*中斷請求號*/void(*handler)(int,void*,structpt_regs*), /*指向中斷服務(wù)子程序*/unsignedlongirqflags,/*中斷類型*/constchar*devname,/*設(shè)備的名字*/void*dev_id)；/*設(shè)備標識符*/request_irq()函數(shù)中斷在驅(qū)動程序工作的過程中的作用用戶發(fā)出某種輸入/輸出請求;用驅(qū)動程序的read()函數(shù)或request()函數(shù)，將完成輸入/輸出的指令送給設(shè)備控制器，現(xiàn)在設(shè)備驅(qū)動程序等待操作的發(fā)生。一小段時間以后，硬設(shè)備準備好完成指令的操作，并產(chǎn)生中斷信號標志事件的發(fā)生。中斷信號導(dǎo)致調(diào)用驅(qū)動程序的中斷服務(wù)子程序，它將所要的數(shù)據(jù)從硬設(shè)備復(fù)制到設(shè)備驅(qū)動程序的緩沖區(qū)中，并通知正在等待的read()函數(shù)或request()函數(shù)，現(xiàn)在數(shù)據(jù)可供使用。在數(shù)據(jù)可供使用時，read()或request()函數(shù)現(xiàn)在可將數(shù)據(jù)提供給用戶進程。二、設(shè)備驅(qū)動程序的框架

1.驅(qū)動程序的注冊與注銷系統(tǒng)引導(dǎo)時,通過sys_setup()進行系統(tǒng)初始化。而sys_setup()又調(diào)用device_setup()進行設(shè)備初始化。設(shè)備初始化分為塊設(shè)備初始化blk_dev_init()

與字符設(shè)備初始化chr_dev_init()

字符設(shè)備初始化通過register_chrdev()函數(shù)向內(nèi)核注冊

externintregister_chrdev(unsignedintMajor,constchar*name,struct*fops)

若注冊成功,內(nèi)核就可向請求的進程提供操作的入口地址進而啟動驅(qū)動程序進行工作,完成進程的請求操作。注銷函數(shù)unregister_chrdev(unsignedintmajorconstchar*name)2.設(shè)備的打開與釋放打開設(shè)備用open()完成;如打印機用lp_open()打開。打開設(shè)備過程需要執(zhí)行如下操作：檢查與設(shè)備相關(guān)的錯誤如果是首次打開，則初始化設(shè)備如果需要，分配且設(shè)置設(shè)備文件的私有數(shù)據(jù)遞增設(shè)備使用的計數(shù)器釋放設(shè)備是由release()完成的遞減設(shè)備使用的計數(shù)器釋放文件中的私有數(shù)據(jù)所占的內(nèi)存空間如果屬于最后一個釋放，則關(guān)閉設(shè)備3.舉例：一個簡單的字符設(shè)備mouse假設(shè)有一個進程打開/dev/logibm文件(主設(shè)備號為10)

VFS調(diào)用主設(shè)備號為10的通用open()函數(shù)。因為這類設(shè)備包括很多不同種類的設(shè)備,因此有一個名為misc_open()的函數(shù)。這個函數(shù)根據(jù)次設(shè)備號裝載一組更專用的文件操作。最終結(jié)果是,該文件的f_op域指向bus_mouse_fops表，并調(diào)用open_mouse()函數(shù)檢查總線鼠標是否被連接。請求總線鼠標所使用的IRQ線,也就是IRQ5,并注冊mouse_interrupt()中斷服務(wù)例程。初始化一個類型為mouse_status的mouse數(shù)據(jù)結(jié)構(gòu),該結(jié)構(gòu)存放總線鼠標的有關(guān)狀態(tài)信息。這些狀態(tài)信息包括哪個鍵被按下,以及最后一次讀取設(shè)備文件之后鼠標指針的水平、垂直位移。向0x23e控制寄存器中寫入0，從而啟用總線鼠標中斷(總線鼠標使用從0x23c到0x23f的I/O端口)。open_mouse()函數(shù)mouse數(shù)據(jù)結(jié)構(gòu)的填充是異步進行的:每次用戶移動鼠標或者按下一個鼠標鍵時,鼠標控制器都會產(chǎn)生一個中斷,從而激活mouse_interrupt()函數(shù);該函數(shù)執(zhí)行以下操作：通過向0x23e控制寄存器寫入適當(dāng)?shù)拿?并從0x23c輸入寄存器中讀取相應(yīng)的值來查詢鼠標設(shè)備的狀態(tài)。更新mouse數(shù)據(jù)結(jié)構(gòu)。向0x23e控制寄存器中寫入0來重新啟用鼠標中斷(鼠標中斷每次發(fā)生時,鼠標設(shè)備都會自動將其禁用)mouse_interrupt()函數(shù)進程要讀取/dev/logibm文件的內(nèi)容才能獲得鼠標的狀態(tài);每個read()系統(tǒng)調(diào)用最終都會調(diào)用read_mouse()函數(shù),也就是文件操作的read函數(shù);該函數(shù)執(zhí)行以下操作:1.查進程是否最少請求了3個字節(jié),否則返回-EINVAL2.檢查對/dev/logibm的最后一次讀操作之后鼠標狀態(tài)是否有已發(fā)生變化;如果沒有,就返回-EAGAIN。3.調(diào)用disable_irq()來禁止IRQ5的中斷處理,讀取mouse數(shù)據(jù)結(jié)構(gòu)中所存放的值;然后通過調(diào)用enable_irq()來重新啟用IRQ5的中斷處理。4.最后一次讀操作之后把代表鼠標狀態(tài)(鍵狀態(tài),水平位置,垂直位置)的3個字節(jié)寫入用戶態(tài)緩沖區(qū);如果進程所請求的內(nèi)容超過3個字節(jié),就用0填充用戶態(tài)緩沖區(qū)。5.返回所寫字節(jié)的數(shù)量。read_mouse()函數(shù)5.6磁盤存取設(shè)備管理5.6.1磁盤性能簡述1.磁盤的特點和結(jié)構(gòu):容量大,斷電后仍可保存信息,存取速度較塊,成本較低,可實現(xiàn)直接(隨機)存取,存取磁盤上任一物理塊的時間不依賴于該物理塊所處的位置。盤設(shè)備由兩部分組成:驅(qū)動部分+存儲介質(zhì)(磁盤)磁盤以恒定轉(zhuǎn)速旋轉(zhuǎn),磁臂沿徑向驅(qū)動磁頭移動到所要求的磁道上,并等待所要求的扇區(qū)開始位置旋轉(zhuǎn)到磁頭下,開始讀寫數(shù)據(jù),在磁頭和緩沖區(qū)間傳輸數(shù)據(jù)。柱面扇區(qū)磁臂磁頭磁道2.磁盤數(shù)據(jù)組織和格式信息記錄在磁道上,多個盤片,正反兩面都用來記錄信息,每面一個磁頭,所有盤面中處于同一磁道號上的所有磁道組成一個柱面。物理地址形式:

磁頭號(盤面號)、磁道號(柱面號)、扇區(qū)號

磁盤格式化的一種形式：p172圖5-22每個物理扇區(qū)600個字節(jié)包含：

標識符字段數(shù)據(jù)字段

Track#:磁道號 Gap:為間隙 Head#:磁頭號 Synch:為定界符 Sector#:扇區(qū)號 CRC:用于校驗 GapIDFieldGapDataFieldGap1774151520SynchTrack#Head#Sector#CRC12112SynchDataCRC151223.磁盤類型：磁盤分為硬盤和軟盤,單片盤和多片盤,固定頭磁盤和移動頭磁盤等。固定頭磁盤:每個磁道設(shè)置一個磁頭,所有磁頭都被安裝在一個剛性磁臂中,各磁頭并行讀寫,磁頭不需要機械移動,速度快但成本高,用于大容量硬盤上。移動頭磁盤:一個盤面只有一個磁頭,變換磁道時需要移動磁頭,速度慢但成本低,微機上配置的軟盤和硬盤(溫盤)都采用這種結(jié)構(gòu)?；顒佑脖P:增加靈活性和便攜性。4.磁盤訪問時間（Ta)尋道時間Ts:把磁頭移動定位到指定磁道所經(jīng)歷的時間,啟動時間s與移動n條磁道時間之和Ts=mn+s一般為5~30ms旋轉(zhuǎn)時間Tr等待指定扇區(qū)旋轉(zhuǎn)移動到磁頭下面所經(jīng)歷的時間5400r/min=90r/sec的硬盤:平均Tr=1/2r=5.55ms傳輸時間Tt

從磁盤到內(nèi)存讀寫數(shù)據(jù)實際經(jīng)歷的時間:Tt=b/rN其中b為讀寫字節(jié)數(shù)N為一條磁道總字節(jié)數(shù)訪問時間:Ta=Ts+1/2r+b/rN主要與Ts有關(guān)5.6.2磁盤調(diào)度當(dāng)多個進程都需要訪問磁盤時,訪盤請求在等待,應(yīng)采用一定的策略,對這些請求的服務(wù)順序調(diào)整安排,旨在降低平均磁盤服務(wù)時間,達到公平、高效。公平：一個I/O請求在有限時間內(nèi)滿足。高效：減少設(shè)備機械運動所帶來的時間浪費。

磁盤調(diào)度考慮的問題：一次訪盤時間=尋道時間+旋轉(zhuǎn)延遲時間+存取時間(1)減少尋道時間(活動頭磁盤)(2)減少延遲時間(固定頭磁盤)磁盤調(diào)度算法:1.先來先服務(wù)FCFS(First-ComeFirstServed)按訪問請求到達的先后次序服務(wù)優(yōu)點：簡單,公平；缺點：效率低,相臨兩次請求可能會造成最內(nèi)到最外的柱面尋道,使磁頭反復(fù)移動,增加了平均尋道時間設(shè)磁盤訪問序列:80,55,58,39,18,90,160,150,38,184183839555880901501601842.最短尋道時間優(yōu)先SSTF(ShortestSeekTimeFirst)優(yōu)先選擇距當(dāng)前磁頭最近的訪問請求進行服務(wù)，主要考慮尋道優(yōu)先優(yōu)點：磁盤的平均尋道時間最小缺點：進程"饑餓"現(xiàn)象,有時會造成與當(dāng)前磁道距離遠的訪問請求長期等待得不到服務(wù)(不公平)磁盤訪問序列:80,55,58,39,18,90,160,150,38,184183839555880901501601843.掃描算法SCAN電梯調(diào)度算法克服最短尋道優(yōu)先的缺點,既考慮距離,又考慮方向具體做法:當(dāng)設(shè)備無訪問請求時,磁頭不動;當(dāng)有訪問請求時,磁頭按一個方向移動,在移動過程中對遇到的訪問請求進行服務(wù),然后,判斷該方向上是否還有訪問請求,如果有則繼續(xù)掃描;否則改變移動方向,并為經(jīng)過的訪問請求服務(wù),如此反復(fù)。183839555880901501601844.循環(huán)掃描(CSCAN)算法

SCAN算法對兩端磁道請求不利,可改進為循環(huán)掃描算法CSCAN。本算法規(guī)定磁頭單向移動(如向外),移動到最外磁道后立即返回最里面要訪問的磁道,構(gòu)成循環(huán)掃描。183839555880901501601845.N-Step-SCAN和FSCAN算法(1)磁臂粘著現(xiàn)象:進程對某一磁道反復(fù)訪問,從而壟斷了整個磁盤,引起磁臂粘著(2)N-Step-SCAN和FSCAN算法:將磁盤請求隊列按請求順序分為多個(或2個)長度為N的子隊列,每個子隊列用SCAN算法;當(dāng)N很大時接近于SCAN算法,當(dāng)N=1時蛻化為FCFS算法。FSCAN算法是2個子隊列的N-Step-SCAN算法,一個是由當(dāng)前所有磁盤請求形成的隊列,按SCAN算法進行處理;掃描期間新的磁盤請求放入另一個等待隊列,前一個隊列處理完后,再處理新隊列。如此反復(fù),公平合理。5.6.3磁盤高速緩存(DiskCache)1.磁盤高速緩存的形式(1)專用:在內(nèi)存中單獨開辟一塊固定的區(qū)域?qū)Ｓ谩?2)共享:所有空閑內(nèi)存為緩沖池與請求分頁系統(tǒng)共享2.數(shù)據(jù)交付方式(1)數(shù)據(jù)交付(2)指針交付3.置換算法常用的算法有:最近最久未使用算法LRU,最近未使用算法NRU和最少使用算法LFU。許多系統(tǒng)除了考慮最近最久未使用這一原則外還要考慮：訪問頻率、可預(yù)見性、數(shù)據(jù)的一致性。4.周期性地寫回磁盤根據(jù)LRU算法,經(jīng)常訪問的盤塊可能長期不被回寫,可能導(dǎo)致丟失數(shù)據(jù),可采用周期性(幾十秒)地寫回磁盤。5.6.4提高磁盤I/O速度的其他方法1.提前讀預(yù)先將下一盤塊數(shù)據(jù)一次讀入減少讀盤次數(shù)。2.延遲寫考慮緩沖區(qū)的數(shù)據(jù)不久之后可能還會訪問故暫時不寫入磁盤,將它掛在空閑隊列的末尾,當(dāng)它最久未被訪問到了隊列之首要被淘汰時在寫入磁盤。3.優(yōu)化物理塊的分布分配物理塊時,把有可能順序存取的塊放在一起,盡量分布在同一柱面或相鄰柱面上,從而減少磁盤臂的移動次數(shù)。但采用線性鏈表來組織空閑塊時比較困難,此時,將同一磁道的若干個盤塊