Budowa dysku:
Adres dyskowy: numer napędu, nr powierzchni, nr ścieżki (cylindra), nr sektora.
Czas przeszukiwania (ang. seek time): czas przesunięcia głowicy na właściwą ścieżkę (nast. elektronicznie wybiera się właściwą powierzchnię).
Czas oczekiwania (ang. latency time): czas oczekiwania aż głowica znajdzie się nad właściwym sektorem (to dysk się kręci); określony przez prędkość rotacji dysku.
Czas transmisji: czas potrzebny na odczytanie/zapisanie danych.
Jednostka transmisji: sektor lub grupa sektorów.
SO traktuje dysk jak jednowymiarową tablicę: numery bloków rosną wzdłuż sektorów na ścieżce, następnie wzdłuż ścieżek w cylindrze, następnie od cylindra 0 do ostatniego. Niech s - liczba sektorów na ścieżce, t - liczba ścieżek w cylindrze:
(powierzchnia j, cylinder i, sektor k) --> blok b
b = k + s * (j + i*t)
czas obsługi żądania = czas przeszukiwania + czas oczekiwania + czas transmisji
Charakterystyka żądania dyskowego:
W systemie wieloprogramowym w kolejce do dysku może oczekiwać więcej niż jedno żądanie.
FCFS: Kolejka prosta, obsługa w kolejności przybywania żądań.
SSTF (ang. Shortest Seek Time First): do obsługi wybiera żądanie z najmniejszym czasem przeszukiwania względem bieżącej pozycji głowicy.
SCAN (winda): głowica startuje od jednego końca dysku i przemieszcza się w kierunku przeciwnego, obsługując żądania do mijanych ścieżek, aż dotrze do drugiego końca. Wówczas zmienia kierunek ruchu.
C-SCAN: jak SCAN, ale żądania są obsługiwane tylko podczas ruchu głowicy w jednym kierunku (dysk jest traktowany jak powierzchnia cykliczna).
C-LOOK: wariant (praktyczny) C-SCAN, głowica przesuwa się do skrajnego żądania (nie ścieżki) w każdym kierunku.
F-SCAN (N-Step SCAN): ruch głowicy jak w SCAN, ale są obsługiwane tylko te żądania, które nadeszły przed rozpoczęciem ruchu w danym kierunku.
Tworzenie kolejek do sektorów
Efektywność algorytmu szeregowania może zależeć od metody przydziału miejsca na plik, rozmieszczenia na dysku katalogów i bloków indeksowych.
Rysunek: Skaładniki jądra uczestniczące w obsłudze operacji blokowych (Źródło: Bovet, Ceasti, "Linux Kernel")
Wirtualny System Plików (VFS): funkcja systemowa read() przekazuje sterowanie do odpowiedniej funkcji z poziomu VFS. Warstwa VFS zapewnia jednolity model obsługi dla wszystkich systemów plików.
Funkcja z poziomu VFS stwierdza, czy dane są już dostępne (w pamięci podręcznej w RAM), a jeśli nie, to jak wykonać operację czytania.
Jeśli jądro musi wczytać dane z dysku, to musi określić ich fizyczną lokalizację. Korzysta w tym celu z warstwy odpowiedzialnej za odwzorowanie (ang. mapping layer), zwykle działającej w dwóch krokach:
Jądro generuje żądanie wejścia-wyjścia do urządzenia blokowego. Korzysta z ogólnej warstwy blokowej (ang. generic block layer), która inicjuje operacje transmisji danych. Ponieważ dane nie muszą zajmować spójnego obszaru na urządzeniu, więc warstwa może zainicjować kilka operacji wejścia-wyjścia. Każda operacja jest reprezentowana przez strukturę blokowego wejścia-wyjścia (block I/O structure lub w skrócie bio structure), w której są zebrane wszystkie informacje niezbędne niższym warstwom do realizacji żądania. Ogólna warstwa blokowa zasłania szczegóły sprzętowe urządzeń.
Wreszcie podprogram obsługi urządzenia blokowego zabiera się za transmisję danych wysyłając odpowiednie polecenia do interfejsu sprzętowego sterownika dysku.
Rysunek: Typowy układ strony zawierającej dane dyskowe (Źródło: Bovet, Ceasti, "Linux Kernel")
Sterowniki sprzętowych urządzeń blokowych transmitują dane w jednostkach o ustalonym rozmiarze zwanych sektorami. Zatem moduł szeregujący wejścia-wyjścia i podprogam obsługi urządzenia blokowego zarządzają sektorami danych. W większości dyskach sektor ma rozmiar 512 bajtów (choć zdarzają się większe sektory). W Linuksie numer sektora jest pamiętany na zmiennej typu sector_t.
VFS, warstwa odwzorowania i systemy plików grupują dane na dysku w jednostki logiczne zwane blokami. Blok odpowiada najmniejszej jednostce dysku w ramach systemu plików i obejmuje jeden lub więcej sąsiadujących ze sobą sektorów. W Linuksie rozmiar bloku musi być potegą dwójki i nie może być większy od ramki. Musi także być wielokrotnością rozmiaru sektora. W architekturze 80 x 86 dopuszczalne rozmiary to 512, 1024, 2048 i 4096 bajtów. Rozmiar bloku nie jest specyficzny dla urządzenia, o jego wyborze może decydować administrator. Każdy blok wymaga własnego bufora w pamięci RAM. Bufor ma nagłówek typu buffer_head zawierający informacje wymagane przez jądro.
Podprogramy obsługi urządzeń blokowych obsługują segmenty danych. Każdy segment jest stroną pamięci lub częścią strony obejmującą dane umieszczone fizycznie obok siebie na dysku. Transmisja danych odbywa się najczęściej w trybie DMA, pojedyncza transmisja DMA musi dotyczyć sektorów położonych fizycznie obok siebie na dysku. Nowsze sterowniki dysków mogą realizować także transmisje DMA do nieciągłych obszarów pamięci. (ang. scatter-gather DMA transfers).
Pamięci podręczne dysku działają na stronach danych, każda strona mieści się w ramce.
Ogólna warstwa blokowa skleja górne i dolne warstwy, zatem musi wiedzieć o sektorach, blokach, segmentach i stronach danych.
Każda struktura bio zawiera identyfikator obszaru na dysku - początkowy numer sektora i liczbę sektorów - oraz jeden lub więcej segmentów opisujących obszary pamięci. Każdy segment w bio jest reprezentowany przez strukturę bio_vec, zawierającą wskaźnik do deskryptora strony ramki na segment, wielkość segmentu w bajtach oraz przesunięcie w ramach ramki.
Dysk jest logicznym urządzeniem blokowym obsługiwanym przez ogólną warstwę blokową. Zwykle odpowiada urządzeniu fizycznemu, ale może także być urządzeniem wirtualnym zbudowanym z kilku fizycznych partycji dyskowych lub obszarem pamięci ulokowanym w dedykowanych stronach RAM. W każdym przypadku wyższe warstwy jądra obsługują dyski w ten sam sposób. Dysk jest reprezentowany przez obiekt gendisk.
Sekwencja kroków wykonywanych przez jądro przy przekazywaniu operacji wejścia-wyjścia do ogólnej warstwy blokowej
Żądania wejścia-wyjścia do urządzeń blokowych są na poziomie jądra obsługiwane asynchronicznie, a podprogramy obsługi urządzeń są sterowane przerwaniami. Ogólna warstwa blokowa wywołuje moduł szeregujący, by utworzyć nowe żądanie lub powiększa jedno z już istniejących, a następnie kończy pracę. Później jest aktywowany podprogram obsługi urządzenia, który wykonuje 'procedurę strategii' (ang. strategy routine) w celu wyboru czekającego żądania i jego realizacji poprzez wysłanie odpowiednich poleceń do kontrolera dysku. Po zakończeniu obsługi żądania wejścia-wyjścia kontroler generuje przerwanie, a wtedy właściwy podprogram obsługi ponownie wykonuje procedurę strategii w celu wyboru kolejnego żądania.
Każdy podprogram obsługi urządzenia utrzymuje własną kolejkę żądań, zawierającą żądania czekające na obsługę w danym urządzeniu. Jeśli kontroler dysku obsługuje kilka dysków, to utrzymywana jest osobna kolejka żądań do każdego fizycznego urządzenia blokowego. Szeregowanie odbywa się osobno dla każdej kolejki.
Kolejka żądań to lista dwukierunkowa, której elementami są deskryptory żądań (struct request). Uporządkowanie elementów w kolejce jest specyficzne dla konkretnego podprogramu obsługi urządzenia, moduł odpowiedzialny za szeregowanie żądań wejścia-wyjścia oferuje kilka predefiniowanych metod szeregowania. Każde żądanie składa się z jednego lub kilku struktur bio. Najpierw na liście pojawia się pierwsze bio, ale później mogą być do niego dołączane kolejne. Tak się dzieje, gdy nowe dane fizycznie przylegają do danych, których dotyczą już istniejące elementy żądania.
Każda kolejka ma ograniczenie na liczbę oczekujących żądań czytania i pisania (domyślnie po 128). Jeśli liczba oczekujących żądań czytania (pisania) osiągnie górny limit, to kolejka jest oznaczana jako pełna, a procesy, które będą chciały dodać do kolejki nowe żądania zostaną zawieszone w oczekiwaniu na wolne miejsce (o ile można je będzie uśpić).
Moduł odpowiedzialny za szeregowanie żądań wejścia-wyjścia (ang. I/O scheduler) określa dokładną pozycję nowego żądania w kolejce. Żądania są posortowane w kolejce w kolejności sektorów.
Linux 2.6 oferuje cztery typy algorytmów szeregowania:
Domyślny algorytm określa się w trakcie inicjalnego ładowania systemu (wartość parametru jądra elevator = <nazwa>). Jeśli żaden nie zostanie podany, to jądro używa Anticipatory. Ponadto administrator może podmienić moduł do szeregowania żądań wejścia-wyjścia podczas działania jądra (wstawia się nazwę modułu szeregującego do pliku /sys/block/hda/queue/scheduler) w systemie plików sysfs.
jmd@westa:/dev$ cat /sys/block/hda/queue/scheduler
noop anticipatory deadline [cfq]
jmd@westa:/dev$ ls /sys/block/hda/queue/iosched/
back_seek_max fifo_expire_async quantum slice_async slice_idle
back_seek_penalty fifo_expire_sync queued slice_async_rq slice_sync
Algorytm szeregowania użyty w kolejce żądań jest reprezentowany przez obiekt typu elevator_t:
struct request_queue
{
elevator_t *elevator;
/*
* the queue request freelist, one for reads and one for writes
*/
struct request_list rq;
....
}
Obiekt ten zawiera kilka metod do obsługi wszystkich możliwych operacji wykonywanych przez 'windę'.
Wszystkie algorytmy szeregowania korzystają z dispatch queue (kolejki żądań wybranych do realizacji) zawierającej wszystkie żądania posortowane zgodnie z porządkiem, w jakim powinny być obsługiwane przez podprogram obsługi urządzenia - następne obsługiwane żądanie jest zawsze pierwszym elementem w kolejce. dispatch queue to kolejka żądań podłączona do pola queue_head deskryptora request_queue. Wszystkie algorytmy dopuszczają dodawanie struktur bio do istniejących żądań i sklejanie sąsiadujących żądań.
Algorytm 'Noop'
Najprostszy możliwy algorytm szeregowania. Nie ma uporządkowanej kolejki, nowe żądania zawsze są dodawane na początku lub na końcu dispatch queue, a następnym obsługiwanym żądaniem jest pierwsze żądanie z kolejki.
Według RedHat: The noop scheduler is suitable for devices where there are no performance penalties for seeks. Examples of such devices are ones that use flash memory. noop can also be suitable on some system setups where I/O performance is optimized at the block device level, with either an intelligent host bus adapter, or a controller attached externally.
Algorytm 'CFQ'
Głównym celem algorytmu CFQ jest zapewnienie sprawiedliwego podziału przepustowości wejścia-wyjścia pomiędzy procesy generujące żądania. Aby osiągnąć ten cel w algorytmie wykorzystuje się dużą liczbę posortowanych kolejek (domyślnie 64), w których przechowywane są żądanią pochodzące od różnych procesów. Gdy dociera nowe żądanie jest wywoływana funkcja mieszająca, która przekształca identyfikator grupy wątków procesu (zwykle jest to PID) w indeks w kolejce. Następnie nowe żądanie jest wstawiane na koniec tej kolejki. Zatem żądania pochodzące od tego samego procesu zawsze trafiają do tej samej kolejki. Wypełnianie dispatch queue polega na tym, że kolejki są przeglądane w kolejności round-robin i zawartość niepustych kolejek jest przesuwana na koniec dispatch queue.
Według RedHat: CFQ is well suited for most medium to large multi-processor systems and for systems which require balanced I/O performance over multiple Logical Unit Numbers and I/O controllers.
Algorytm 'Deadline'
W tym algorytmie oprócz dispatch queue korzysta się z czterech dodatkowych kolejek. Dwie z nich - posortowane zgodnie z numerami sektorów - zawierają, odpowiednio, żądania czytania i pisania. Dwie pozostałe - deadline - zawierają te same żądania czytania i pisania, ale posortowane zgodnie z ich deadlinem (czyli budowane zgodnie z porządkiem FIFO). Ich zadaniem jest przeciwdziałanie zagłodzeniu żądań. Dla żądania czytania termin upływa (ang. expires) domyślnie po 500 milisekundach, a dla żądania pisania po 5 sekundach. Żądania czytania są uprzywilejowane, gdyż zwykle powodują blokowanie procesów, od których pochodzą.
W chwili gdy powinno się wypełnić ponownie dispatch queue, najpierw sprawdza się typ kolejnego żądania. Jeśli są dostępne zarówno żądania czytania, jak i pisania, to wybierane jest 'czytanie', o ile kierunek 'pisanie' nie był pomijany zbyt wiele razy.
Nastepnie sprawdzana jest kolejka deadline dla wybranego typu żądania. Jeśli dla pierwszego żądania w kolejce już upłynął termin, to żądanie jest przesuwane na koniec dispatch queue. Przenosi także do dispatch queue żądania z kolejki posortowanych, począwszy od żądania następującego po żądaniu, dla którego upłynął termin. Liczba przenoszonych żądań jest większa, gdy żądania są położone na dysku blisko siebie i krótsza w przeciwnym przypadku.
Jeśli dla żadnego żądania nie upłynął termin, to do dispatch queue są pobierane żądania z kolejki posortowanych począwszy od żądania następnego za ostatnio wziętym z tej kolejki. Po dojściu do końca kolejki, poszukiwanie jest rozpoczynane od jej początku.
Algorytm zmniejsza opóźnienia dla żądań czytania, ale robi to kosztem globalnej przepustowości.
Według RedHat: The deadline scheduler aims to keep latency low, which is ideal for real-time workloads.
Algorytm 'Anticipatory'
To najbardzie wyrafinowany algorytm szeregowania. Jest rozwinięciem algorytmu Deadline. Tutaj też utrzymuje się cztery kolejki. Moduł szeregujący przegląda kolejki posortowane, przełączając się pomiędzy żądaniami czytania i pisania, lecz faworyzując żądania czytania. Przeglądanie jest zasadniczo sekwencyjne, chyba, że dla żądania upływa termin. Dla żądań czytania termin upływa po - domyślnie - 125 milisekundach, a dla żądań pisania po 250 milisekundach. Stosowane są dodatkowe heurystyki:
W pewnych przypadkach algorytm może wybrać żądanie poza bieżącą pozycją w kolejce posortowanej, wymuszając zmianę ruchu głowicy. Zwykle ma to miejsce, gdy odległość żądania w przeciwnym kierunku jest mniejsza niż połowa odległości żądania za bieżącą pozycją w kolejce posortowanej.
Algorytm zbiera statystyki o wzorcu zachowań operacji wejścia-wyjścia dla każdego procesu w systemie. Po wybraniu żądania czytania pochodzącego od procesu P, sprawdzane jest czy następne żądanie w kolejce posortowanej pochodzi od tego samego procesu. Jeśli tak, to natychmiast jest wybierane następne żądanie. Wpp sprawdza się zebrane statystyki na temat procesu P, jeśli wynika z nich, że proces P wkrótce wygeneruje następne żądanie czytania, to zamiera na krótki okres czasu (domyślnie 7 milisekund). Zatem algorytm może przewidzieć żądanie czytania pochodzące od procesu P położone blisko na dysku względem ostatnio wybranego żądania.
Algorytm nadal dobrze obsługuje żądania czytania, ale ma szansę zapewnić lepszą globalną przepustowość.
Według RedHat: This algorithm is intended to optimize systems with small or slow disk subsystems. One artifact of using the AS scheduler can be higher I/O latency caused by numerous enforced delays. For the most part, the anticipatory scheduler performs well on most personal workstations, but very poorly for server-type workloads.
Figure 1 shows the results of running an Oracle 10G OLTP workload on a 2-CPU/2-HT Xeon with 4 GB of memory across 8 LUNs on an LSIlogic megraraid controller. The Online Transaction Processing (OLTP) load ran mostly 4k random I/O with a 50% read/write ratio. The Decision Support System (DSS) workload consists of 100% sequential read queries using large 32k-256k byte transfer sizes.
The CFQ scheduler was chosen as the default since it offers the highest performance for the widest range of applications and I/O system designs. We have seen CFQ excel in both throughput and latency on multi-processor systems with up to 16-CPUs and for systems with 2 to 64 LUNs for both UltraSCSI and Fiber Channel disk farms. In addition, CFQ is easy to tune by adjusting the nr_requests parameter in /proc/sys/scsi subsystem to match the capabilities of any given I/O subsystem.
The Deadline scheduler excelled at attempting to reduce the latency of any given single I/O for real-time like environments. A problem which depends on an even balance of transactions across multiple HBA, drives or multiple file systems may not always do best with the Deadline scheduler. The Oracle 10G OLTP load using 10 simultaneous users spread over eight LUNs showed improvement using Deadline relative to Red Hat Enterprise Linux 3's I/O elevator, but was still 12.5% lower than CFQ.
The NOOP scheduler indeed freed up CPU cycles but performed 23% fewer transactions per minute when using the same number of clients driving the Oracle 10G database. The reduction in CPU cycles was proportional to the drop in performance, so perhaps this scheduler may work well for systems which drive their databases into CPU saturation. But CFQ or Deadline yield better throughput for the same client load than the NOOP scheduler.
The AS scheduler excels on small systems which have limited I/O configurations and have only one or two LUNs. By design, the AS scheduler is a nice choice for client and workstation machines where interactive response time is a higher priority than I/O latency.
The short summary of our study indicates that there is no SINGLE answer to which I/O scheduler is best.
The good news is that with Red Hat Enterprise Linux 4 an end-user can customize their scheduler with a simple boot option. Our data suggests the default Red Hat Enterprise Linux 4 I/O scheduler, CFQ, provides the most scalable algorithm for the widest range of systems, configurations, and commercial database users. However, we have also measured other workloads whereby the Deadline scheduler out-performed CFQ for large sequential read-mostly DSS queries. Other studies referenced in the section "References" explored using the AS scheduler to help interactive response times. In addition, noop has proven to free up CPU cycles and provide adequate I/O performance for systems with intelligent I/O controller which provide their own I/O ordering capabilities.
Workload Dependent Performance Evaluation of the
Linux 2.6 I/O Schedulers
by Steven L. Pratt, Dominique A. Heger,
Proceedings of the Linux Symposium, July 21th-24th, 2004, Ottawa
| Janina Mincer-Daszkiewicz |