NCQ (Native Command Queuing) – natywne kolejkowanie zadań

NCQ to programowe rozszerzenie interfejsu SATA polegające na kolejkowaniu zadań zapisu/odczytu (I/O) w taki sposób, by zwiększyć wydajność (liczbę operacji I/O na sekundę) zarówno dysków HDD, jak i SSD.

W tradycyjnych dyskach twardych (HDD) odbywa się to poprzez zbuforowanie do 32 poleceń i dobranie ich kolejności tak, by dysk wykonał zadania przy minimalnej liczbie obrotów talerza i ruchów głowicy. Pozwala to na zmniejszenie czasu niezbędnego do przeprowadzenia operacji I/O oraz spowalnia starzenie się elementów elektromechanicznych dysku.

Rys.1. Wykonywanie operacji odczytu/zapisu przez dyski: (a) bez NCQ, (b) z NCQ

Przedstawiony na rys. 1 dysk zrealizuje operacje I/O: (a) z wyłączoną obsługą NCQ – w kolejności od A do F, wykonując przy tym 3,5 obrotu talerza; (b) z obsługą NCQ – w kolejności C → A → B → D → F → E w trakcie niecałych 2 obrotów talerza.

NCQ jest rozwinięciem idei kolejkowania zawartej w technologii TCQ (Tagged Command Queuing) zastosowanej pierwotnie w dyskach SCSI, a następnie zaimplementowanej w dyskach ATA i częściowo w SATA-I. Różni się od pierwowzoru przede wszystkim liczbą jednocześnie przetwarzanych operacji I/O oraz tym, że NCQ pozwala na wydanie kolejnego polecenia przez hosta w trakcie pracy HDD nad innym zadaniem.
Natywne kolejkowanie zadań zostało wprowadzone wraz z pojawieniem się dysków z interfejsem SATA-II (później zaimplementowane w części dysków SATA-I).

Za funkcjonalność NCQ odpowiadają trzy kluczowe protokoły:

- Mechanizm informacji zwrotnej o stanie procesu (Status Return Mechanism) – funkcja ta umożliwia samodzielne przekazanie informacji o zakończeniu dowolnego (jednego lub wielu) planowanego zadania I/O. Host nie jest już informowany o rozpoczęciu przetwarzania procesu I/O, a jedynie o jego zakończeniu.

- Ograniczenie liczby przerwań do maksymalnie jednego na planowane zadanie I/O (Interrupt Aggregation) – host powinien zostać poinformowany o zakończeniu każdego wykonanego polecenia I/O. Zadania odnoszące się do danych zawartych fizycznie blisko siebie na dysku są grupowane i odpowiednio kolejkowane. Doprowadza to do sytuacji, w której kilka poleceń I/O kończy się jednocześnie lub w krótkim czasie. Możliwe jest więc wysłanie informacji o zakończeniu, np wszystkich 32 operacji w jednym 64-bitowym pakiecie zamiast w 64 pakietach, jak miałoby to miejsce bez NCQ. W SATA-I i w ATA wymagane były dwa przerwania na każdą z wykonywanych operacji I/O (jedna o rozpoczęciu procedowania polecenia, druga o jego zakończeniu).

- Mechanizm bezpośredniego dostępu do pamięci operacyjnej (First Party DMA – FPDMA) – NCQ zaprojektowano w taki sposób, by HDD mógł wybrać, które zadanie związane z transferem danych będzie wykonane jako następne. Dysk wysyła tag/identyfikator polecenia I/O do kontrolera pamięci hosta. Dokonuje tym samym rezerwacji miejsca na buforowane dane bezpośrednio w pamięciach operacyjnych. W ten sposób dysk jest w stanie skutecznie zmieniać kolejność rozpatrywanych poleceń, gdyż może blokować miejsce na bufor bez angażowania do tego celu oprogramowania hosta.

W interfejsie SATA-III wprowadzono wiele zmian w funkcjonowaniu NCQ. Poprawiono m.in. zarządzanie kolejkowaniem oraz dodano polecenia związane z lepszą obsługą przesyłu strumieniowego treści multimedialnych, dzięki zezwoleniu hostowi na przekazywanie informacji czy i które operacje mają być zatrzymane, a którym należy zwiększyć priorytet. W wyniku tego nastąpiła ogólna poprawa wydajności systemu, a nie tylko zwiększenie liczby wykonywanych przez dysk operacji I/O na sekundę.
Zastosowano również izochroniczny transfer danych, umożliwiając tym samym płynną transmisję do aplikacji wymagających dużych przepustowości (audio/wideo) oraz równoległe wykonywanie transferu dla zadań o niższym priorytecie.

NCQ zaimplementowane w interfejsie SATA-II mogło również wpływać negatywnie na wykonywanie niektórych planowanych zadań I/O, powodując spadek wydajności systemu operacyjnego. Algorytm ten nie miał ustalonych czasów na wykonanie poszczególnych operacji I/O. Także liczba przesunięć konkretnego planowanego zadania I/O na koniec kolejki nie była ograniczona. Wykonanie jednego polecenia I/O mogło więc być odwlekane w czasie na rzecz coraz nowszych zapytań, prowadząc do tzw. zagłodzenia procesu.
Sytuację taką zaobserwowano w systemie operacyjnym LINUX z macierzą dyskową RAID-5. W trakcie przeprowadzonego testu zadanie o niższym priorytecie zostało wykonane po upływie 57 118 ms (z wyłączonym NCQ po 2 021 ms). W 2008 roku Google Inc. przeprowadziło własne testy, w których dowiodło, że w specyficznych okolicznościach wykonanie niektórych planowanych procesów I/O może zostać opóźnione nawet o 2 s (niezależnie od systemu operacyjnego).
Powyższe problemy zostały rozwiązane wraz z pojawieniem się interfejsu SATA-III – poprzez dodanie do zarządzania kolejką podrozkazu "Deadline Handling", który steruje limitami czasu dla operacji I/O o najniższym priorytecie.

Ze względu na budowę dysków SSD (wiele kości pamięci NAND podłączonych do jednego kontrolera oraz brak elementów mechanicznych) zadania NCQ realizowane są w odmienny sposób – poprzez tzw. głębokie kolejkowanie. Polega to na grupowaniu przez kontroler planowanych zadań I/O i wykonywaniu ich jednocześnie na wielu kościach pamięci NAND.

NCQ może być obsługiwane tylko w przypadku współpracy HDD/SSD z kontrolerem dysków wspierającym tę technologię.