摘   要： 分析了FPDMA數(shù)據(jù)傳輸,、隊(duì)列讀/寫(xiě)命令的動(dòng)態(tài)運(yùn)行機(jī)制、支持高速特性的隊(duì)列和協(xié)議性能,，給出了NCQ的性能優(yōu)勢(shì)和存在的問(wèn)題,。
關(guān)鍵詞： 本機(jī)命令隊(duì)列  運(yùn)行機(jī)制  性能

　　本機(jī)命令隊(duì)列NCQ(Native Command Queuing)[1]是SATAⅡ接口中引入的命令協(xié)議，是對(duì)SATA 1.0所做的諸多功能擴(kuò)展中惟一與性能密切相關(guān)的技術(shù),。其原型是1998年發(fā)布的ATA/ATAPI-4的命令隊(duì)列（CQ）技術(shù),。在PATA(Parallel ATA)中采用非對(duì)等輪詢(xún)?cè)L問(wèn)結(jié)構(gòu)，其控制器計(jì)算能力弱,，無(wú)法支撐復(fù)雜的最優(yōu)化命令排序算法,，致使基于CQ的應(yīng)用性能改善和協(xié)議增加的開(kāi)銷(xiāo)相當(dāng)。隨著ASIC,、串行技術(shù),、多線程和超線程系統(tǒng)等技術(shù)的發(fā)展，在SATA中引入NCQ用于增強(qiáng)磁盤(pán)整體性能的條件已經(jīng)具備,。
1  NCQ結(jié)構(gòu)
1.1 工作模型
　　NCQ處理的對(duì)象是隊(duì)列命令,，核心是隊(duì)列機(jī)制，包括創(chuàng)建,、排隊(duì)和在主適配器與盤(pán)體控制器的協(xié)調(diào)等,，工作模型如圖1[2]所示。模型分為兩個(gè)功能相對(duì)獨(dú)立的部分,，它們通過(guò)串行總線交換數(shù)據(jù),，通過(guò)FIS（Frame Information Structure）來(lái)交換LBA、地址偏移,、命令和狀態(tài)信息,。其中,，標(biāo)記Tag是一個(gè)重要的元素，在驅(qū)動(dòng)器緩存中有一個(gè)含有Tag的命令隊(duì)列,，在主機(jī)控制器緩存中有與它對(duì)應(yīng)的Tag標(biāo)志位表,，值域[0，n],，其中n（≤31）是隊(duì)列的深度,，每一條命令都有惟一的標(biāo)記值，應(yīng)用于隊(duì)列化命令的數(shù)據(jù)操作,。

1.2 功能部件
　　NCQ主要由命令隊(duì)列建立部件,、數(shù)據(jù)傳輸部件和命令完成狀態(tài)返回部件組成。其中命令隊(duì)列建立部件的功能是使磁盤(pán)控制器按照命令協(xié)議（如NCQ,、DMA、PIO等）的語(yǔ)義（OpCode）確定是把該命令送到隊(duì)列排隊(duì)(Tag有效)還是立即執(zhí)行(Tag無(wú)效),；數(shù)據(jù)傳輸部件使用FPDMA(First Parity DMA)傳輸機(jī)制完成驅(qū)動(dòng)器和主機(jī)數(shù)據(jù)的傳輸,；命令完成狀態(tài)返回部件的功能是當(dāng)數(shù)據(jù)讀寫(xiě)操作命令發(fā)送或在數(shù)據(jù)傳輸完畢后，將磁盤(pán)命令的執(zhí)行狀態(tài)返回給主機(jī),。
1.3 命令格式
　　FPDMA包含RFQ(Read FPDMA Queued)和WFQ(Write FPDMA Queued)兩條命令,，命令格式見(jiàn)參考文獻(xiàn)[2]。格式中的扇區(qū)計(jì)數(shù)寄存器包含的Tag由主機(jī)驅(qū)動(dòng)程序指定,，命令域區(qū)分為RFQ和WFQ(RFQ.Command=60h,，WFQ.Command=61h)，支持LBA模式和48位地址格式,。
1.4 內(nèi)部寄存器結(jié)構(gòu)
　　把NCQ隊(duì)列機(jī)制應(yīng)用于系統(tǒng)時(shí)采用AHCI[5](Advanced Host Controller Interface)接口技術(shù),，適配器建立在PCI-HBA基礎(chǔ)上，AHCI內(nèi)部的寄存器由HBA寄存器和系統(tǒng)內(nèi)存兩部分組成,。HBA寄存器從結(jié)構(gòu)上又可分為AHCI-PCI配置空間寄存器和HBA內(nèi)存寄存器,。其中前者定義了與PCI接口的標(biāo)準(zhǔn)PCI寄存器，后者用于通用主機(jī)控制和端口控制,，它們通過(guò)AHCI-BAR或PCI配置空間的寄存器BAR聯(lián)系,。AHCI系統(tǒng)內(nèi)存通過(guò)端口00~31和控制寄存器相連,，每個(gè)端口控制寄存器同時(shí)指向內(nèi)存的Px命令列表基址（PxCLB）和Px FIS基址（PxFB）,。其中Px命令列表系統(tǒng)內(nèi)存是為包括命令信息和PRD表的命令表地址的命令列表結(jié)構(gòu)設(shè)計(jì)的，Px FIS系統(tǒng)內(nèi)存是面向接收端口的FIS結(jié)構(gòu)設(shè)計(jì)的,。
2  NCQ運(yùn)行機(jī)制研究
　　由圖1的工作模型和SATA磁盤(pán)模型,，可以抽象出如圖2所示的NCQ支持SATA磁盤(pán)的原理分析模型,。其中的命令排隊(duì)邏輯和算法包括命令的讀取,、命令分析、排隊(duì)策略,、算法代碼等,；FPDAM引擎任務(wù)處理單元包括從控制器獲得命令,、從高速緩存獲得空間或數(shù)據(jù),、與SATA總線進(jìn)行數(shù)據(jù)交換等,；磁盤(pán)任務(wù)處理單元包括從控制器獲得命令,，執(zhí)行磁盤(pán)的旋轉(zhuǎn),、尋道和定位等操作，與高速緩存進(jìn)行數(shù)據(jù)交換等,。其中與NCQ運(yùn)行直接相關(guān)的部分在圖2中用重背景標(biāo)出。
2.1 FPDMA運(yùn)行
　　PATA在內(nèi)存和硬盤(pán)之間采用Ultra DMA數(shù)據(jù)傳輸機(jī)制,。SATA充分借鑒了PATA的技術(shù)思路,，引入了一種新型的數(shù)據(jù)傳輸機(jī)制FPDMA,，其運(yùn)行原理如下：
　　(1)設(shè)置主機(jī)非頁(yè)面化內(nèi)存中的FPDMA矢量表，這個(gè)表有32個(gè)入口,，每個(gè)表入口含命令分散/聚合列表的物理地址(PRD表),，它們都與Tag數(shù)字相對(duì)應(yīng)。其中隊(duì)列化命令的分散/聚集列表是描述數(shù)據(jù)傳輸?shù)闹鳈C(jī)內(nèi)存結(jié)構(gòu),。(2)驅(qū)動(dòng)程序把主機(jī)控制器的隊(duì)列表基址寄存器設(shè)置為FPDMA矢量表的起始物理地址,，主機(jī)驅(qū)動(dòng)器軟件填充隊(duì)列化命令的PRD表,，并在向設(shè)備發(fā)布一條命令前適當(dāng)設(shè)置FPDMA的矢量入口,。(3)當(dāng)主機(jī)控制器從設(shè)備收到一DMA設(shè)置FIS后，它將使用Tag域作為對(duì)FPDMA 矢量表的索引,，并設(shè)置DMA引擎PRD指針到FPDMA 矢量表中的特定值，同時(shí)應(yīng)用DMA設(shè)置FIS中的D位來(lái)設(shè)置DMA的傳輸方向,。(4)進(jìn)行FPDMA數(shù)據(jù)傳輸，并返回傳輸狀態(tài)信息,。
2.2 RFQ/WFQ
　　讀操作(RFQ)是由主機(jī)向磁盤(pán)控制器發(fā)出的數(shù)據(jù)請(qǐng)求,，主機(jī)驅(qū)動(dòng)軟件一旦發(fā)出讀寄存器FIS，主機(jī)控制器的硬件將自主執(zhí)行FPDMA操作,，不需要主機(jī)驅(qū)動(dòng)軟件的參與，直到本條命令執(zhí)行完畢（即捕捉到執(zhí)行完畢的中斷請(qǐng)求位SActive）,。
　　寫(xiě)操作完成隊(duì)列化的命令把數(shù)據(jù)寫(xiě)回驅(qū)動(dòng)器，命令操作原理與讀操作類(lèi)似,。
2.3 錯(cuò)誤處理
　　在SATA協(xié)議棧中,，每層都有錯(cuò)誤發(fā)現(xiàn),、錯(cuò)誤控制和錯(cuò)誤報(bào)告恢復(fù)功能[4],。NCQ工作于傳輸層，其錯(cuò)誤處理機(jī)制簡(jiǎn)單有效,。
　　在主機(jī)發(fā)送給設(shè)備的寄存器FIS中，狀態(tài)寄存器BSY位出現(xiàn)了錯(cuò)誤,，設(shè)備將傳輸一個(gè)設(shè)置了ERR,、BSY和錯(cuò)誤寄存器為適當(dāng)錯(cuò)誤代碼的寄存器FIS到主機(jī)控制器；然后,，設(shè)備等待地址為10h的日志頁(yè)讀日志擴(kuò)展（Read Log Ext）命令（若收到主機(jī)發(fā)送的復(fù)位寄存器FIS,，將立即停止等待）。當(dāng)收到該命令后,，設(shè)備控制器將放棄所有未執(zhí)行的隊(duì)列命令,、清空隊(duì)列，返回詳細(xì)的錯(cuò)誤信息,，發(fā)送Set Device Bits FIS清除主機(jī)所有的Sactive寄存器位,。至此，主機(jī)可以重新發(fā)送放棄的命令和新的命令,。
3  NCQ工作性能分析
3.1 隊(duì)列性能
3.1.1 隊(duì)列分析
　　NCQ的核心是隊(duì)列機(jī)制,，關(guān)鍵是命令的執(zhí)行次序排列和重排。在NCQ中,，命令在隊(duì)列中的分布是采用旋轉(zhuǎn)位置排序（Rotational Position Ordering,，RPO）算法實(shí)現(xiàn)的。具體的策略是綜合考慮減少磁盤(pán)的尋道和旋轉(zhuǎn)延遲,，得到一個(gè)全局時(shí)間最短、執(zhí)行最優(yōu)的命令執(zhí)行序列,。另外，為適應(yīng)磁盤(pán)隨機(jī)動(dòng)態(tài)存儲(chǔ),，NCQ支持RPO動(dòng)態(tài)重排命令序列,，弱化命令存取位置的“震蕩”，保證設(shè)備最優(yōu)性能狀態(tài)的魯棒性,。常用的減少尋道延遲的策略有SSTF(Shortest Seek Time First)[7],、SCAN[6]～[8],。這些算法都是基于面向企業(yè)高中端的SCSI隊(duì)列TCQ(Tagged Command Queue)設(shè)計(jì)的,。而SATA定位于桌面、移動(dòng)存儲(chǔ),、低端服務(wù)器和網(wǎng)絡(luò)存儲(chǔ)模型的近線和低端層次,所以隊(duì)列性能,、精度,、時(shí)間抖動(dòng)等要求相對(duì)低一些，加上控制器計(jì)算性能的大幅提高,，算法的運(yùn)行開(kāi)銷(xiāo)遠(yuǎn)遠(yuǎn)小于磁盤(pán)尋道和定位的代價(jià),。所以，在磁盤(pán)本體上,，使用SSTF、SCAN和其改進(jìn)算法對(duì)隊(duì)列中的命令進(jìn)行排序和重排序是完全可行的,。
　　需要注意的是：SSTF和SCAN算法的依據(jù)一般是數(shù)據(jù)塊的邏輯塊號(hào)；而SATF計(jì)算的依據(jù)是物理塊號(hào),，但由于操作系統(tǒng)沒(méi)有磁盤(pán)結(jié)構(gòu)的物理信息，所以該類(lèi)算法實(shí)現(xiàn)起來(lái)相對(duì)復(fù)雜,。改進(jìn)的策略一是通過(guò)邏輯塊號(hào)-物理塊號(hào)之間的關(guān)系轉(zhuǎn)換,，二是使用“最近塊數(shù)優(yōu)先”近似,。但它們都削弱了算法性能,，增大了時(shí)間誤差。
3.1.2 隊(duì)列仿真比較
　　使用UTSA的磁盤(pán)頭調(diào)度模擬器（DiskHead）[9]模擬上述主要隊(duì)列算法的NCQ性能情況,。DiskHead既是一個(gè)磁盤(pán)負(fù)載產(chǎn)生器，也是一個(gè)負(fù)載調(diào)度器,，通過(guò)仿真配置腳本程序，可以產(chǎn)生兩個(gè)不同的負(fù)載源,。第一個(gè)負(fù)載源（L1）包括16個(gè)塊訪問(wèn),，集中于低磁道區(qū)(100~2000磁道),；第二個(gè)負(fù)載源(L2)也包括16個(gè)塊訪問(wèn),，集中于高磁道區(qū)(10 000~14 000磁道),。然后把負(fù)載按照周期性和隨機(jī)性組合成四種類(lèi)型的混合負(fù)載,，輸入模擬器進(jìn)行仿真。為了顯示隊(duì)列的優(yōu)勢(shì),，削弱CACHE的影響，盡可能加大了負(fù)載的密度和震蕩,。
　　鑒于SCAN算法每次要回歸0道,，所以需要把相應(yīng)的尋道時(shí)間和訪問(wèn)時(shí)間去除掉,。仿真結(jié)果如圖3,、圖4所示。

　　從圖3,、圖4看出，是否支持隊(duì)列的命令重排對(duì)存儲(chǔ)系統(tǒng)的性能影響很大,，不同的負(fù)載特性對(duì)系統(tǒng)的性能影響也不盡相同,。另外,，排隊(duì)算法對(duì)隨機(jī)負(fù)載的性能要優(yōu)于周期負(fù)載,，請(qǐng)求排隊(duì)能大大減少尋道時(shí)間,，從而提高存儲(chǔ)系統(tǒng)的整體I/O性能,。
3.2 協(xié)議性能
　　NCQ屬于一種“輕型”的接口協(xié)議。與PATA比較,，協(xié)議的優(yōu)化性能具體表現(xiàn)在：
　　(1)引入性能優(yōu)于Ultra DMA和DMA的FPDMA簡(jiǎn)單傳輸機(jī)制,，其初始化設(shè)置由主機(jī)驅(qū)動(dòng)器軟件完成,，設(shè)備自動(dòng)選擇DMA狀態(tài)參數(shù),，完成驅(qū)動(dòng)器和主機(jī)數(shù)據(jù)的傳輸,。在傳輸數(shù)據(jù)的過(guò)程中不需要主機(jī)驅(qū)動(dòng)器軟件的參與。
　　(2)協(xié)議隊(duì)列空間調(diào)整采用類(lèi)“滑動(dòng)窗口”策略,，設(shè)備與主機(jī)之間的握手相對(duì)“弱化”,。設(shè)備方收到設(shè)備命令請(qǐng)求后,，就立即返回復(fù)位BSY信號(hào),，從而保持命令發(fā)送窗口的大小,，而不是等待請(qǐng)求完成才返回,，這樣為系統(tǒng)實(shí)現(xiàn)局部并行化提供了條件。這與PATA的設(shè)備請(qǐng)求“封閉”運(yùn)行完全不一樣,，它的設(shè)備請(qǐng)求命令執(zhí)行嚴(yán)格的握手程序,，只有整個(gè)命令請(qǐng)求完成后才返回中斷信號(hào)，系統(tǒng)在接收到中斷返回后,，才能繼續(xù)下一條設(shè)備命令的執(zhí)行周期,。
　　(3)命令的排序在設(shè)備中完成，只要有新的設(shè)備請(qǐng)求命令被送入設(shè)備隊(duì)列,，設(shè)備就要啟動(dòng)一次排序算法進(jìn)行重排序,，保持命令序列執(zhí)行策略的一致性。算法的結(jié)果形成一個(gè)命令執(zhí)行索引表,，該表包含了隊(duì)列命令新的執(zhí)行順序和相關(guān)參數(shù),。
　　(4)Race-free狀態(tài)返回機(jī)制實(shí)現(xiàn)了命令完成返回信息的高度管線化。NCQ允許各磁盤(pán)隨時(shí)返回命令執(zhí)行狀態(tài),，特別是使用中斷聚合把數(shù)條命令的中斷聚合在一起,，達(dá)到數(shù)個(gè)命令執(zhí)行狀態(tài)同時(shí)返回的效果。
通過(guò)對(duì)協(xié)議的改進(jìn)和優(yōu)化,，減少了接口事務(wù),，降低了協(xié)議運(yùn)行開(kāi)銷(xiāo)，提高了NCQ協(xié)議工作的性能,。
4  結(jié)束語(yǔ)
　　NCQ是SATA設(shè)備請(qǐng)求命令的隊(duì)列協(xié)議,，它應(yīng)用了隊(duì)列智能重排序、協(xié)議流化,、硬件自動(dòng)FPDMA設(shè)置等技術(shù),，減少了主機(jī)和設(shè)備的握手次數(shù)和接口事務(wù)數(shù)量，提高了隊(duì)列負(fù)載性能,，減少了尋道和旋轉(zhuǎn)延遲時(shí)間,，使協(xié)議操作高效化，大大提高了SATA磁盤(pán)系統(tǒng)的性能,。Intel的測(cè)試數(shù)據(jù)表明：使用基于AHCI的SATA HDD是ATA HDD綜合性能的1.51倍[5],。盡管如此，NCQ還存在排隊(duì)命令與非排隊(duì)命令不能混合使用,，一旦發(fā)生錯(cuò)誤,，硬盤(pán)將放棄隊(duì)列中的全部命令，專(zhuān)用的接口協(xié)議AHCI發(fā)布滯后等不足之處。
參考文獻(xiàn)
1   Huffman A,，Clark J.Serial ATA Native Command QueuingAn Exciting New Performance Feature for Serial ATA.www.serialata.org，2003
2   Intel Corporation.Serial ATA Ⅱ Native Command Queuing Overview www.intel.com,，Apr 2003
3   Intel Corporation.Serial ATA：Advanced Host Controller Interface(Revision 1.0).www.intel.com,，May 2004
4   Taylor R.Serial ATA：Application Consideration for the Enterprise[S].www.agilysys.com，Apr 2004
5   Huffman A,，Garzik J.AHCI-Take advantage of Serial ATA Features.IDF Fall 2003,，San Jose，Sep 2003
6   Worthington B L,，Ganger G R,，Patt Y L.Scheduling for modern disk drives and non-random workload.In：Michael Ley proceedings.Perfarmance Evaluation Review22(1).proc ACM SIGMETRICS conf.Vanderbilt University，Nashviue Tennessee,，USA,，1994
7   Geist R，Daniel S.A Continuum of Disk Scheduling Algorithms.ACM Trans On Computer System,，1987,；5(1)
8   Thomasian A，Liu C.Some New Disk Scheduling Policies and Their Performance.In：Marina Del Rey,，Proceedings of the International Conference on Measurements and Modeling of Computer Systems(SIGMETRICS 2002),，California USA，2002
9   Robbins S.A Disk Head Scheduling Simulator.In：Proc.35th SIGCSE Technical Symposium on Computer Science Education,，Norfolk Virgina,，2004