Systemy Operacyjne – semestr drugi

Wyk a

ł d trzynasty

Warstwa operacji blokowych w Linuksie

Blokowe urz d

ą zenia wej c

ś ia – wyj c

ś ia są bardziej skomplikowane w obsłudze niż urządzenia znakowe. W przeciwie s ń twie do tych ostatnich pozwalają one bowiem na

swobodny dostęp do zgromadzonych w nich danych. Oznacza to, e

ż umożliwiają one wyszukiwanie pozycji gdzie są zgromadzone interesujące nas dane lub gdzie jest miejsce, w którym te dane chcemy zapisać. Musi więc istnieć jakiś mechanizm pozwalający na dwukierunkową zmianę poło en ż

ia wska n

ź ika danych wzgl d

ę em bieżącej

pozycji. Wszystkie urządzenia blokowe są wyposa on

ż

e w system plików okre l

ś onego typu. Najcz

c

ęś iej spotykanymi urządzeniami blokowymi są oczywi c

ś ie dyski twarde,

ale istnieją również inne urz d

ą zenia, które zaliczamy do tej kategorii (CD, DVD, pamięci flash). Czas dostępu do tych urządzeń (w szczególno c ś i do dysku twardego) jest

jednym z najbardziej znaczących czynników mających wpływ na wydajność całego systemu komputerowego. Z tego względu, a tak e ż z uwagi na skomplikowanie

zagadnienia, w jądrze systemu Linux wyodr b

ę niono osobny podsystem, zajmuj c

ą y się obs u

ł gą takich urz d

ą zeń, który nazywa się warstwą blokowych operacji wej c

ś ia –

wyj c

ś ia (ang. block IO layer).

Urządzenia blokowe przechowują dane w sektorach, które najcz

c

ęś iej mają wielkość 512 bajtów (choć nie jest to regułą). Sektor jest równocze n ś ie najmniejszą

adresowalną jednostką pamięci urządzenia blokowego. Pojedyncza operacja wej c ś ia – wyj c

ś ia mo e

ż obejmować jeden lub większą liczbę sektorów. Większość systemów

operacyjnych nie pos u

ł guje si

ę bezpo r

ś ednio sektorami, ale ł c

ą zy je w zazwyczaj wi k

ę sze jednostki zwane blokami. Blok mo e

ż mie

ć taki sam rozmiar jak sektor, lub jego

rozmiar mo e

ż by

ć wielokrotno c

ś ią rozmiaru sektora. W systemie Linux przyjęto, celem uproszczenia kodu jądra, e ż bloki będą miały wielkość mniejszą lub równą jednej

stronie, choć to ograniczenie w przyszłych wersjach systemu mo e ż znikną .

ć Bloki na dane pochodzące z odczytu lub zawierające dane do zapisu do urządzenia blokowego są umieszczone w pamięci w buforach. Ka d

ż y z takich buforów wyposa on

ż

y jest w nagłówek określony strukturą typu struct buffer_head, przechowujący dane niezb d

ę ne do prawidłowego zarządzania takim buforem. Do tych danych należą między innymi: stan bufora, który jest przechowywany w polu b_state tej struktury. Stan ten mo e

ż być okre l

ś ony jednym lub kilkoma znacznikami należącymi do wyliczenia bh_state_bits. Znacznik BH_Uptodate oznacza, e ż bufor zawiera

poprawne dane, BH_Dirty – e

ż zawartość bufora zosta a

ł zmodyfikowana i powinna zostać zapisana na dysk, BH_Lock – bufor jest chroniony przed dost p ę em

współbie n

ż ym na czas realizowanej wła n

ś ie operacji wej c

ś ia – wyj c

ś ia, BH_Req – bufor jest u y

ż wany w realizowanym zleceniu, BH_Mapped – bufor jest poprawnym

buforem odwzorowanym w bloku dyskowym, BH_New – bufor został przydzielony, ale jeszcze nie był wykorzystywany, BH_Async_Read – bufor jest u y ż wany w operacji

asynchronicznego odczytu, BH_Async_Write – bufor jest u y

ż wany w operacji asynchronicznego zapisu, BH_Delay – bufor nie został jeszcze skojarzony z blokiem dyskowym., BH_Boundary – bufor opisuje blok graniczny ciągłego obszaru bloków, następny blok nie nale y ż już do tego obszaru. Wyliczenie bh_state_bits zawiera

również dodatkowy znacznik BH_PrivateStart, który informuje, e

ż kolejne, starsze od niego bity pola b_state są wykorzystywane przez sterownik urządzenia blokowego do własnych celów. Kolejne pole tej struktury o nazwie b_count jest licznikiem odwołań do bufora. Jego wartość jest zwiększana przy pomocy funkcji get_bh(), a zmniejszana przy pomocy put_bh(). Obie funkcje są funkcjami inline. Licznik odwołań powinien być zwiększany przed wykonaniem ka d ż ej z operacji dotyczącej

danego bufora, gdyż zapobiega to jego wcze n

ś iejszemu zwolnieniu. Pole b_dev zawiera identyfikator urz d

ą zenia fizycznego na którym znajduje się blok skojarzony

z buforem, a pole b_blocknr zawiera numer tego bloku. Strona na której znajduje się bufor jest okre l ś ona warto c

ś ią pola b_page. Adres, od którego zaczyna się obszar

bufora na tej stronie jest umieszczony w polu b_data. Rozmiar tego bufora jest okre l ś ony zawarto c

ś ią pola b_size.

Nagłówek bufora w wersjach jądra systemu wcześniejszych niż 2.6 przechowywał również informacje dotycz c ą e operacji jakie były wykonywane na buforze. Taka

sytuacja powodowała niską efektywność takich operacji, gdy

ż pojedynczy zapis lub odczyt z urz d

ą zenia wymagał posłu en

ż

ia się kilkoma takimi nagłówkami, dodatkowo

rozmiar nagłówka był porównywalny z rozmiarem bufora, który opisywał. W najnowszej serii jądra postanowiono więc „odchudzi ”

ć nag ów

ł

ek bufora i stworzyć nową

struktur ,

ę która osobno przechowuje dane związane z operacjami wej c

ś ia – wyj c

ś ia. Reprezentuje ona takie operacje w trakcie ich trwania za pomocą listy segmentów1.

Segment w tym przypadku jest definiowany jako ciągły fragment bufora. Bufory, których segmenty są zgromadzone na liście nie muszą tworzyć ciągłego obszaru.

Dodatkowo dzięki tej strukturze można realizować kilka operacji wej c

ś ia – wyj c

ś ia na jednym buforze równocześnie. Najwa n

ż iejsze pola struktury bio to bi_io_vecs,

bi_vcnt oraz bi_idx. Pierwsze z nich zawiera adres tablicy struktur bio_vec, która jest wykorzystywana jako lista poszczególnych segmentów u y ż wanych w danej

operacji wej c

ś ia – wyj c

ś ia. Ka d

ż y z elementów tej tablicy jest opisany trójką: <page, offset, len>, (strona, przemieszczenie, długoś ) ć . Ca a

ł tablica opisuje więc całość

bufora wyznaczonego dla operacji. Drugie pole struktury bio okre l ś a ile elementów z opisywanej tablicy bierze udział w operacji. Bieżącą pozycję w tej tablicy reprezentuje ostatnie z wymienionych pól, którego zawartość jest aktualizowana na bieżąco. U y ż cie tego pola pozwala na podział struktury bio, co ma znaczenie w

przypadku takich sterowników, jak sterowniki macierzy RAID. Podział polega na kilkukrotnym skopiowaniu tej struktury i ustawieniu dla ka d ż ej z tych kopii innej

warto c

ś i pola indeksującego. Podobnie jak nagłówek bufora również struktura bio posiada licznik odwołań. Jego wartość jest zwiększana przy pomocy funkcji bio_get(), a zmniejszana przy pomocy bio_put(). Pole bi_private mo e

ż być wykorzystywane dla danych twórcy struktury bio. Zastosowanie struktury bio przyniosło nast p ę uj c

ą e

korzyści:

blokowe operacje wej c

ś ia – wyj c

ś ia mogą w prosty sposób korzysta

ć z wysokiej pamięci, gdy

ż struktura bio posługuje się strukturami page,

struktura bio może reprezentowa

ć zarówno zwykłe operacje I/O, jak i również operacje bezpośrednie, które nie korzystają z buforów jądra,

ułatwiona jest realizacja operacji wej c

ś ia – wyj c

ś ia, w których dane pochodzą z wielu rozłącznych stron pamięci (tzw. operacje z rozproszonym r ź ódłem),

obsługa takiej struktury jest mniej skomplikowana niż obsługa nag ów

ł

ków bloków.

Wi k

ę szość sterowników urządzeń blokowych utrzymuje struktury przechowujące zlecenia operacji wej c ś ia – wyj c

ś ia przeznaczone dla obsługiwanych przez nie

urządzeń. Te struktury są nazywane kolejkami zleceń. Są one reprezentowane strukturą request_queue i zawierają dwukierunkową listę zleceń i skojarzonych z nimi informacji steruj c

ą ych. Każdy z elementów tych kolejek jest opisany strukturą struct request. Je l ś i kolejka nie jest pusta, to pierwsze zlecenie znajdujące się na niej jest przekazywane przez sterownik do urządzenia, które je realizuje. Każde zlecenie mo e ż zawiera

ć wiele struktur bio, które opisują bloki zaanga ow

ż

ane w daną operacj .

ę

Za szeregowanie zleceń w opisywanej kolejce odpowiedzialny jest planista operacji wej c ś ia – wyj c

ś ia (ang. I/O scheduler). Jego zadaniem jest zminimalizowanie liczby

przestawień mechanizmu s u

ł żącego do odczytywania i zapisywania danych w urządzeniu blokowym (np. g ow ł

icy w dysku twardym), co pozwala na osi g

ą ni c

ę ie

maksymalnej r

ś edniej przepustowo c

ś i oraz unikanie zagłodzenia żądań. Planista dokonuje tego wykonując operacje scalania i sortowania2. Kiedy nowe żądanie trafia do kolejki, wówczas planista stara się je scalić z żądaniami, które dotyczą przyległych sektorów. Je l ś i takowych ż d

ą ań nie ma, to planista stara się umie c

ś ić je po r

ś ód

żądań, które dotyczą sektorów leżących w pobliżu, dzięki czemu nie b d

ę zie konieczna częsta zmiana kierunku ruchu g ow

ł

icy3. W jądrach serii 2.6 jest u y

ż wany jeden

z czterech algorytmów szeregowania ż d

ą ań. Dwa z nich są wzorowane na algorytmie, który był wykorzystywany w wersji 2.4, wi c ę on jako pierwszy zostanie opisany.

Planista I/O w jądrach wersji 2.4 działał w oparciu o algorytm nazwany Windą Linusa (ang. Linus Elevator). Algorytm ten stosuje scalanie obustronne. Oznacza to, e ż

nowe zlecenie mo e

ż być umieszczone przed istniejącymi już zleceniami lub za, je l

ś i tylko będą one dotyczyły spójnego obszaru sektorów. Pierwszy rodzaj scalania nazywany jest scalaniem frontowym, drugi scalaniem tylnym. Zazwyczaj ten drugi rodzaj występuje cz c

ęś iej. Je l

ś i nowego zlecenia nie da się scalić z innymi, które są

obecne w kolejce, to nast p

ę uje etap sortowania. W tym etapie planista stara się znaleźć miejsce w kolejce dla nowego zlecenia, takie e ż otaczaj c

ą e je inne zlecenia b d

ę ą

dotyczyły sektorów znajduj c

ą ych się w pobliżu. Je l

ś i nie znajdzie takiego miejsca, to umieszcza dane zlecenie na końcu kolejki. Może tak postąpić jeszcze w jednym przypadku, kiedy podczas przeszukiwania kolejki znajdzie przeterminowane zlecenie. Takie postępowanie ma na celu wyeliminowanie zagłodzenia żąda , ń ale niestety

nie jest skuteczne i algorytm Windy Linusa prowadzi do zagłodzenia żądań.

1

Które nie mają nic wspólnego z segmentami, którymi pos u

ł gują si

ę procesory Intela i pokrewne do adresowania pamięci operacyjnej.

2

W tym wypadku chodzi tu o dwie odrębne operacje a nie o operację sortowania przez scalanie.

3

Podobnie jak w metodzie LOOK omawianej w poprzednim semestrze.

1

Systemy Operacyjne – semestr drugi

W jądrze 2.6 postanowiono wi c

ę go zast p

ą ić czterema innymi rozwiązaniami. Pierwszym z nich jest planista terminowy (ang. deadline I/O scheduler). Zapobiega on g od

ł

zeniu żądań, oraz preferuje operacje odczytu nad operacjami zapisu. Okazuje się bowiem, e ż opó n

ź ienia odczytu mają większy wpływ na spadek wydajno c

ś i

systemu niż opó n

ź ienia operacji zapisu. Planista terminowy stosuje cztery struktury danych: g ów ł

ną kolejkę zleceń, kolejkę zleceń odczytu, kolejkę zleceń zapisu i kolejkę rozdziału. Mechanizm ten przydziela każdemu zleceniu termin realizacji. Domyślnie wynosi on 500 ms dla operacji odczytu i 5 s dla operacji zapisu. Nowe zlecenia są wstawiane równocze n

ś ie do kolejki g ów

ł

nej, gdzie realizowane są operacje scalania i sortowania, oraz w zale n

ż o c

ś i od rodzaju zlecenia do kolejki zapisu lub

odczytu. Te dwie ostatnie kolejki są rzeczywi c

ś ie kolejkami FIFO. Planista terminowy pracuje w dwóch trybach: w trybie normalnym pobiera pierwsze żądanie i wstawia je do kolejki rozdziału, z której trafi ono pó n

ź iej bezpo r

ś ednio do urządzenia. Planista przełącza się w drugi tryb jeśli zbli a

ż się termin realizacji operacji

z kolejek FIFO. Wówczas do kolejki rozdziału trafia zadanie z której

ś z tych kolejek.

Drugim planistą stosowanym w jądrach serii 2.6 jest planista przewiduj c

ą y4. W przeciwieństwie do planisty terminowego pozwala on uniknąć sytuacji, kiedy ci g ą i

operacji zapisu są przerywane przez pojedyncze żądania operacji odczytu. W działaniu jest on bardzo podobny do planisty terminowego, ale stosuje tzw. heurystykę przewidywania. W momencie przekazania zlecenia odczytu do kolejki rozdziału planista nie wraca od razu do realizacji kolejnych zleceń, lecz wstrzymuje swe działanie na 6 ms5. Je l

ś i po tym czasie aplikacja wygeneruje żądanie odczytu dotyczące obszaru leżącego w pobli u ż tego, którego dotyczyło poprzednie żądanie, to jest ono

realizowane natychmiast. Aby ten czas oczekiwania nie był czasem straconym, sytuacje takie, jak opisywana powy ej ż

powinny mieć cz s

ę to miejsce. Planista

przewidujący stara się okre l

ś i

ć mo l

ż iwość wystąpienia takiej sytuacji prowadząc statystykę działań aplikacji i stosując heurystyki.

Planista przewiduj c

ą y był domyślnym planistą wejścia-wyj c

ś ia do czasu wydania jądra w wersji 2.6.18 (choć w niektórych dystrybucjach przestał nim być już wcze n

ś iej). Zastąpił go planista CFQ (ang. Complete Fair Queuing), który po raz pierwszy pojawił się w wersji 2.6.6 jądra. Jego dzia a ł nie mo n

ż a krótko

scharakteryzować jako połączenie planowania z u y

ż ciem kolejek wielopoziomowych, algorytmu rotacyjnego i przewidywania. Ten planista wprowadza również nową cechę procesów u y

ż tkownika: priorytet wej c

ś ia-wyj c

ś ia. Ka d

ż emu z procesów, który wykonuje operacje blokowe przydzielana jest dynamicznie kolejka na zlecenia synchronicznych operacji wejścia-wyj c

ś ia. Liczba zlece ,

ń które mogą jednocze n

ś ie znaleźć się w takiej kolejce jest ograniczona i uzale n ż iona od wspomnianego

priorytetu. Zlecenia operacji asynchronicznych trafiają do wspólnych kolejek, których zazwyczaj jest mniej niż kolejek żądań operacji synchronicznych. Planista przegląda kolejki procesów poczynając od kolejek o najwyższym priorytecie, a skończywszy na kolejkach o najni s ż zym. Z ka d

ż ej z tych kolejek zdejmuje tyle zlece ,

ń ile

mo e

ż zrealizować w ci g

ą u przedziału czasu, którego d u

ł gość determinuje priorytet wej c

ś ia-wyj c

ś ia procesu. Dla tych kolejek realizuje również opcję przewidywania,

czyli zatrzymuje na krótki czas realizację zleceń, jeśli się pojawią nowe zlecenia, w oczekiwaniu na kolejne ż d ą ania. Po obsłu en

ż

iu kolejek operacji synchronicznych

przechodzi do kolejek operacji asynchronicznych, ale w ich przypadku nie stosuje opcji przewidywania.

Czwarty algorytm szeregowania żądań I/O jest bardzo prosty w działaniu – realizuje wyłącznie operację scalania. Ten algorytm nosi nazw ę noop.

Planistę operacji wej c

ś ia-wyj c

ś ia mo n

ż a wybrać na etapie kompilacji, spo r

ś ód czterech opisanych wy ej

ż , lub w czasie wykonania dokonuj c

ą odpowiednich wpisów do

plików w katalogu /sys. W przypadku urządzeń blokowych o prawdziwie swobodnym dost p ę ie (np.: pami c

ę i flash) najlepszym planistą jest noop.

4

Mo n

ż a go te

ż „ładnie” nazwać planistą antycypującym.

5

Czas ten mo n

ż a konfigurowa .

ć

2