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

Systemy Operacyjne – semestr drugi

nowe zlecenie mo e by umieszczone przed istniej cymi ju zleceniami lub za, je li 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

ciej. Je li nowego zlecenia nie da si scali z innymi, które s

ę

ęś

ś

ę

ć

ą

obecne w kolejce, to nast puje etap sortowania. W tym etapie planista stara si znale

miejsce w kolejce dla nowego zlecenia, takie e otaczaj ce je inne zlecenia b d

ę

ę

źć

ż

ą

ę ą

dotyczy y sektorów znajduj cych si w pobli u. Je li 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 g odzenia

da , ale niestety nie

ę

ł

żą

ń

jest skuteczne i algorytm Windy Linusa mo e doprowadzi do g odzenia

da .

ż

ć

ł

żą

ń

W j drze 2.6 postanowiono wi c go zast pi czterema innymi rozwi zaniami. Pierwszym z nich jest planista terminowy (ang.

ą

ę

ą ć

ą

deadline I/O scheduler). Zapobiega on

g odzeniu

da , oraz faworyzuje operacje odczytu przed operacjami zapisu. Okazuje si bowiem, e opó nienia odczytu maj wi kszy wp yw na wydajno ci systemu ni

ł

żą

ń

ę

ż

ź

ą

ę

ł

ś

ż

opó nienia operacji zapisu. Planista terminowy stosuje cztery struktury danych: g ówn 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 nie do kolejki g ównej, gdzie realizowane s operacje scalania i sortowania, oraz w zale no ci od rodzaju zlecenia do kolejki zapisu lub odczytu

ś

ł

ą

ż

ś

5

. Te dwie

ostatnie kolejki s typowymi kolejkami FIFO. Planista terminowy pracuje w dwóch trybach: w trybie normalnym pobiera pierwsze

danie z kolejki g ównej i

ą

żą

ł

wstawia

je do kolejki rozdzia u, z której trafi ono pó niej bezpo rednio 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

danie z której z tych kolejek.

ł

żą

ś

Drugim planist stosowanym w j drach serii 2.6 jest planista przewiduj cy

ą

ą

ą

6

. W przeciwie stwie do planisty terminowego pozwala on unikn

sytuacji, kiedy ci gi

ń

ąć

ą

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 ms

7

. Je li 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 sto miejsce. Planista

ł

ż

ć

ę

przewiduj cy stara si okre li mo liwo wyst pienia takiej sytuacji prowadz c statystyk dzia a aplikacji i stosuj c heurystyki. Planist przewiduj cego usuni to

ą

ę

ś ć

ż

ść

ą

ą

ę

ł ń

ą

ę

ą

ę

z j dra systemu w wersji 2.6.33.

ą

Planista przewiduj cy by domy lnym planist wej cia-wyj cia do czasu wydania j dra w wersji 2.6.18 (cho w niektórych dystrybucjach przesta nim by ju

ą

ł

ś

ą

ś

ś

ą

ć

ł

ć

ż

wcze niej). 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 anie mo na krótko

ł

ę

ą

ł

ż

scharakteryzowa jako po czenie planowania z u yciem kolejek wielopoziomowych, algorytmu rotacyjnego i przewidywania. Ten planista wprowadza równie now

ć

łą

ż

ż

ą

cech procesów u ytkownika: priorytet wej cia-wyj cia. Ka demu z procesów, który wykonuje operacje blokowe przydzielana jest dynamicznie kolejka na zlecenia

ę

ż

ś

ś

ż

synchronicznych operacji wej cia-wyj cia. 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 szym. Z ka dej z tych

ą

ą

ż

ń

ż

ż

kolejek zdejmuje tyle zlece , ile mo e zrealizowa w ci gu okre lonego dla kolejki przedzia u czasu. Kwant czasu i liczba zlece dla kolejki s zdeterminowane przez

ń

ż

ć

ą

ś

ł

ń

ą

priorytet wej cia-wyj cia jej procesu. Dla tych kolejek planista CFQ realizuje równie opcj przewidywania, czyli po opró nieniu danej kolejki zatrzymuje si na krótki

ś

ś

ż

ę

ż

ę

czas, sprawdzaj c, czy nie pojawi si w niej nowe zlecenia. Je li tak si stanie, to s one realizowane natychmiast. Po obs u eniu kolejek operacji synchronicznych

ą

ą

ę

ś

ę

ą

ł ż

planista 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 cia-wyj cia mo na wybra na etapie kompilacji, spo ród czterech (trzech od wersji j dra 2.6.33) 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 pie (np.: pami ci flash) najlepszym

ę

ę

planist jest

ą

noop.

5

Dok adniej: do tych kolejek zapisywany jest wska nik na to zlecenie.

ł

ź

6

Mo na go te „ adnie” nazwa planist antycypuj cym.

ż

ż ł

ć

ą

ą

7

Czas ten mo na konfigurowa .

ż

ć

2