Systemy Operacyjne – semestr drugi
Wyk ad trzynasty
ł
Warstwa operacji blokowych w Linuksie
Blokowe urz dzenia wej cia – wyj cia s bardziej skomplikowane w obs udze ni urz dzenia znakowe. W przeciwie stwie 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 enia wska nika danych wzgl dem bie
cej
ć
ę
ć
ś
ą
ą
ę
ł ż
ź
ę
żą
pozycji. Wszystkie urz dzenia blokowe s wyposa one w system plików okre lonego typu. Najcz
ciej spotykanymi urz dzeniami blokowymi s oczywi cie dyski twarde,
ą
ą
ż
ś
ęś
ą
ą
ś
ale istniej równie inne urz dzenia, które zaliczamy do tej kategorii (CD, DVD, pami ci flash). Czas dost pu do tych urz dze (w szczególno ci 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 bniono osobny podsystem, zajmuj cy si obs ug takich urz dze , który
ą
ę
ą
ę
ł
ą
ą
ń
nazywa si warstw blokowych operacji wej cia –
ę
ą
ś
wyj cia (
ś
ang. block IO layer).
Urz dzenia blokowe przechowuj dane w sektorach, które najcz
ciej maj wielko
512 bajtów (cho nie jest to regu ). Sektor jest równocze nie najmniejsz
ą
ą
ęś
ą
ść
ć
łą
ś
ą
jednostk pami ci urz dzenia blokowego, któr mo na zaadresowa .
ą
ę
ą
ą
ż
ć Pojedyncza operacja wej cia – wyj cia mo e obejmowa jeden lub wi ksz liczb sektorów.
ś
ś
ż
ć
ę
ą
ę
Wi kszo
systemów operacyjnych nie pos uguje si bezpo rednio sektorami, ale
czy je w zazwyczaj wi ksze jednostki zwane blokami
ę
ść
ł
ę
ś
łą
ę
. Blok mo e mie taki sam
ż
ć
rozmiar jak sektor, lub jego rozmiar mo e by
ż
ć wielokrotno ci
ś ą 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 operacyjnej, w
ą
ą
ę
buforach. Ka dy z takich buforów wyposa ony jest w nag ówek okre lony struktur
ż
ż
ł
ś
ą
typu struct buffer_head, przechowuj cy dane niezb dne 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 lony jednym lub kilkoma znacznikami nale
cymi do wyliczenia
ż
ć
ś
żą
bh_state_bits. Znacznik
BH_Uptodate oznacza, e bufor zawiera zsynchronizowane z no nikiem dane,
ż
ś
BH_Dirty – e zawarto
bufora zosta a zmodyfikowana i powinna zosta zapisana na
ż
ść
ł
ć
no niku,
ś
BH_Lock – bufor jest chroniony przed dost pem wspó bie nym na czas realizowanej w a nie operacji wej cia – wyj cia,
ę
ł
ż
ł ś
ś
ś
BH_Req – bufor jest u ywany
ż
w realizowanym zleceniu, BH_Update_Lock – u ywany do oznaczenia pierwszego bufora ze wszystkich znajduj cych si na stronie jako chronionych przed
ż
ą
ę
wspó bie nym dost pem na czas realizacji operacji wej cia-wyj cia,
ł
ż
ę
ś
ś
BH_Mapped – bufor jest poprawnym buforem odwzorowanym w bloku urz dzenia,
ą
BH_New – bufor
zosta przydzielony, ale jeszcze nie by wykorzystywany,
ł
ł
BH_Async_Read – bufor jest u ywany w operacji asynchronicznego odczytu,
ż
BH_Async_Write – bufor jest
u ywany w operacji asynchronicznego zapisu,
ż
BH_Delay – bufor nie zosta jeszcze skojarzony z blokiem urz dzenia.,
ł
ą
BH_Boundary – bufor opisuje blok graniczny
ci g ego obszaru bloków, nast pny blok nie nale y ju do tego obszaru,
ą ł
ę
ż
ż
BH_Write_EIO – wyst pi b d podczas zapisu bufora na no nik,
ą ł
łą
ś
BH_Eopnotsupp – wyst pi
ą ł
b d „nierealizowalna operacja” dla bufora,
łą
BH_Unwritten – zosta o przydzielone miejsce na no niku dla bufora, ale dane z niego nie zosta y jeszcze w tym miejscu
ł
ś
ł
zapisane, BH_Quiet – b dy operacji na buforze nie b d zg aszane. 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 dej z operacji dotycz cej danego bufora, gdy zapobiega to jego wcze niejszemu zwolnieniu. Pole
ł ń
ć
ę
ż
ą
ż
ś
b_dev
zawiera identyfikator urz dzenia 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 lona warto ci 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 lony zawarto ci pola
ś
ś ą
b_size.
Nag ówek bufora w wersjach j dra systemu wcze niejszych ni 2.6 przechowywa równie informacje dotycz ce operacji jakie by y wykonywane na buforze. Taka
ł
ą
ś
ż
ł
ż
ą
ł
sytuacja powodowa a nisk efektywno takich operacji, gdy pojedynczy zapis lub odczyt z urz dzenia wymaga pos u enia 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 ówek bufora i stworzy now
ł
ł
ł
ą
ę
ć
ł
ć
ą
struktur , o nazwie
ę
bio, która osobno przechowuje dane zwi zane z operacjami wej cia – wyj cia. Reprezentuje ona takie operacje w trakcie ich trwania za pomoc listy
ą
ś
ś
ą
segmentów
1
. 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 cia – wyj cia na jednym buforze równocze nie. Najwa niejsze 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 ywanych
ż
w danej operacji wej cia – wyj cia. Ka dy z elementów tej tablicy jest opisany trójk :
ś
ś
ż
ą <page, offset, len>, (strona, przemieszczenie, d ugo ). Ca a tablica opisuje wi c
ł
ść
ł
ę
sumaryczn przestrze stworzon z segmentów buforów i wyznaczon dla operacji. Drugie pole struktury
ą
ń
ą
ą
bio okre la 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 ycie 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 dej z tych kopii innej warto ci 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 puj ce korzy ci:
ł
ę
ą
ś
blokowe operacje wej cia – wyj cia 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 cia – wyj cia, 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 ówków buforów.
ł
ż
ł
ł
Wi kszo
sterowników urz dze blokowych utrzymuje struktury przechowuj ce zlecenia operacji wej cia – wyj cia 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 cych. Ka dy z elementów tych kolejek jest opisany struktur
ą
ż
ą struct request i reprezentuje pojedyncze zlecenie. Je li 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ą
segmenty zaanga owane w dan operacj .
ż
ą
ę
Za szeregowanie zlece w opisywanej kolejce odpowiedzialny jest planista operacji wej cia – wyj cia (
ń
ś
ś
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 owicy w dysku twardym), co pozwala na osi gni cie
ń
ł żą
ą
ł
ą
ę
maksymalnej redniej przepustowo ci oraz unikanie zag odzenia
da . Planista dokonuje tego wykonuj c operacje scalania i sortowania
ś
ś
ł
żą
ń
ą
2
. Kiedy nowe
danie trafia
żą
do kolejki, wówczas planista stara si je scali z
daniami, które dotycz przyleg ych sektorów. Je li takowych
da nie ma, to planista stara si umie ci je po ród
ę
ć
żą
ą
ł
ś
żą
ń
ę
ś ć
ś
da , które dotycz sektorów le
cych w pobli u, dzi ki czemu nie b dzie konieczna cz sta zmiana kierunku ruchu g owicy
żą
ń
ą
żą
ż
ę
ę
ę
ł
3
. W j drach serii 2.6 jest u ywany jeden
ą
ż
z czterech
4
algorytmów szeregowania
da . 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
ż
1
Które nie maj nic wspólnego z segmentami, którymi pos uguj 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.
4
Liczba ta ulega co jaki czas zmianie. W wersjach j dra 3.0 i nowszych s dost pne tylko trzy takie algorytmy.
ś
ą
ą
ę
1
