Valid HTML 4.01!

Podsystem wejścia-wyjścia - urządzenia blokowe

Spis treści

UWAGA: wszystkie rysunki w tych materiałach pochodzą z Internetu


Struktura dysku

Budowa dysku:

Adres dyskowy: numer napędu, nr powierzchni, nr ścieżki (cylindra), nr sektora.

struktura dysku

struktura dysku

struktura dysku

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)

Szeregowanie żądań do dysku


     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.

Strategie szeregowania żądań dyskowych

Efektywność algorytmu szeregowania może zależeć od metody przydziału miejsca na plik, rozmieszczenia na dysku katalogów i bloków indeksowych.


Podprogramy obsługi urządzeń blokowych w Linuksie

Składniki jądra uczestniczące w realizacji operacji na urządzeniu blokowym

Kernel components affected by a block device operation

Rysunek: Skaładniki jądra uczestniczące w obsłudze operacji blokowych (Źródło: Bovet, Ceasti, "Linux Kernel")

  1. 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.

  2. 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.

  3. 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:

  4. 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ń.

  5. Poniżej ogólnej warstwy blokowej moduł szeregowania żądań (ang. I/O scheduler) sortuje czekające żądania transmisji danych zgodnie z wybranym algorytmem. Celem jest zgrupowanie żądań do danych położonych blisko siebie na urządzeniu fizycznym.

  6. Wreszcie podprogram obsługi urządzenia blokowego zabiera się za transmisję danych wysyłając odpowiednie polecenia do interfejsu sprzętowego sterownika dysku.

Jednostki danych obsługiwane przez składniki jądra

Typical layout of a page including disk data

Rysunek: Typowy układ strony zawierającej dane dyskowe (Źródło: Bovet, Ceasti, "Linux Kernel")

Struktura bio

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.

Reprezentowanie dysków i partycji dyskowych

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.

Generowanie żądania

Sekwencja kroków wykonywanych przez jądro przy przekazywaniu operacji wejścia-wyjścia do ogólnej warstwy blokowej


Szeregowanie żądań do dysku w Linuksie

Żą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.

Algorytmy szeregowania

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ń.


Porównanie linuksowych strategii szeregowania żądań do dysku

Porównanie

Red Hat Enterprise Linux 4 IO schedulers
vs. Red Hat Enterprise Linux 3
for database Oracle 10G oltp/dss (relative performance)
(Źródło: RedHat)

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.

Inne eksperymenty

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