Podsystem wejścia/wyjścia

Niskopoziomowa obsługa operacji wejścia/wyjścia

Filip Murlak

Spis rzeczy

1 Wstęp
2 Niskopoziomowa obsługa we/wy - wprowadzenie
3 Struktury danych
4 ll_rw_block()
5 submit_bh()
6 generic_make_request()
7 __make_request()
8 elevator_linus_merge()
9 bh_rq_in_between()

1 Wstęp

Kontekst Dokument niniejszy powstał jako fragment prezentacji przygotowywanej w ramach projektu Scenariusze ćwiczeń z budowy systemu operacyjnego Linux realizowanego na zajęciach z Systemów Operacyjnych na Wydziale Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego w roku akademickim 2001/2002.

Uwagi techniczne Wszystkie informacje dotyczą jądra 2.4.7 i mogą nie być prawdziwe dla późniejszych wersji - dla wcześniejszych na pewno nie są! Opis dotyczy architektury i386. Wydruki kodu są poddane obróbce właściwej dla tej właśnie architektury (dyrektywy preprocesora, warunkowa kompilacja). Definicje struktur i funkcji pochodzą głównie z - odpowiednio - include/linux/blkdev.h i drivers/block/ll_rw_blk.c, poza elevator_s, elevator_merge_linus() i bh_rq_in_between() zdefiniowanymi w include/linux/elevator.h i drivers/block/elevator.c. Gdy obiekt pochodzi z innego pliku, jest to zaznaczone.

1.1 Cel

Celem tego dokumentu jest zaprezentowanie niskopoziomowej obsługi operacji wejścia/wyjścia z naciskiem na ogólne rozwiązania przyjęte podczas realizacji.

1.2 Definicje

bufor: obiekt opisujący zleconą operację we/wy
dolna połówka: bardzo skrótowo: grupa funkcji, którą można wstawić do odpowiedniej kolejki, zostaną one wykonane po pewnym czasie - gdy tego zechcemy; podobnie realizowane są mniej pilne części procedur obsługi przerwań ("dolne połówki") - stąd nazwa
elevator: obiekt realizujący windowe szeregowanie żądań dostępu w wersji C-LOOK
kolejka żądań: struktura przechowująca żądania w pewnej kolejności
metoda: funkcja, która jest dynamicznie przypisywana do pewnych struktur, realizowana przez wskaźnik do funkcji o określonym typie (wywołując ją nie wiemy dokładnie co się wykona, pozostawiamy to w gestii tej struktury, podobnie jak przy programowaniu obiektowym), np. metody make_request_fn() i request_fn() struktury request_queue
nagłówek bufora: deskryptor bufora używanego do operacji we/wy
we/wy: wejście/wyjście
żądanie: obiekt grupujący sąsiednie zlecenia we/wy

1.3 Opis dalszej części dokumentu

W dalszym ciągu opiszemy funkcjonalność niskopoziomowej obsługi operacji we/wy, po czym przedstawimy najciekawsze aspekty jej realizacji. Zaprezentujemy kluczowe struktury danych i najważniejsze z wykorzystywanych funkcji.

2 Niskopoziomowa obsługa we/wy - wprowadzenie

2.1 Ogólny schemat systemu

Jądro Linuxa utrzymuje dla urządzeń blokowych dodatkową tablicę blk_dev[], w której przechowuje przede wszystkim zlecenia operacji na urządzeniach. Realizacja niskopoziomowej obsługi operacji we/wy opiera się na pojęciach bufora (ang. buffer), żądania (ang. request) i kolejki żądań (ang. request queue). Wyższe poziomy oprogramowania posługują się buforami, jednakże dla zmniejszenia narzutu na obsługę zleceń, na niższym poziomie wprowadzono pojęcie żądania, które grupuje pewną ilość sąsiadujących ze sobą fizycznie odwołań do dysku.
$\includegraphics[width=\textwidth]{01arch.eps}$
Nowe zlecenia są ''tłumaczone'' na żądania i wstawiane do kolejki żądań urządzenia według zmodyfikowanego algorytmu szeregowania windowego realizowanego przez obiekt elevator. Kolejka żądań posiada metodę request_fn(), która pobiera kolejne żądania z kolejki i realizuje je. Do synchronizacji służą kolejki procesów wait_for_request (dla każdej kolejki żądań) i blk_buffers_wait oraz kolejka dolnych połówek (ang. bottom half) tq_disk.

2.2 Realizacja żądania we/wy - dzieje bufora

Niskopoziomowa obsługa operacji we/wy rozpoczyna się od wywołania funkcji ll_rw_block(), która jako parametr otrzymuje tablicę buforów. Zadaniem tej funkcji (a także pośredniczących submit_bh() i generic_make_request()) jest zapewnienie poprawności danych i przekazanie każdego bufora do odpowiedniej kolejki poprzez wywołanie metody make_request_fn(). Ta metoda posiłkując się interfejsem oferowanym przez elevator określa dalszy los bufora - czy zostanie doklejony do istniejącego żądania, czy zainicjuje nowe.
$\includegraphics[width=\textwidth]{02dzieje.eps}$
Jeśli wykryje, że bufor można dokleić do istniejącego żądania, to make_request_fn() (standardowo __make_request()) bezpośrednio wstawia bufor do listy buforów wskazanego żądania. W przeciwnym wypadku trzeba z puli wolnych żądań pobrać nowe żądanie (get_request()) z listy request_freelist - być może trochę poczekać jeśli brak wolnych - zainicjować je i wstawić tam gdzie zasugerował elevator (add_request()).
Uwaga: make_request_fn() może być realizowana zupełnie inaczej, jeśli jakieś urządzenie sobie tego życzy. Żądania są pobierane z kolejki queue_head przez request_fn() i po zrealizowaniu wstawiane (puste) do kolejki pending_freelist, a na koniec trafiają z powrotem do request_freelist.
$\includegraphics[width=\textwidth]{03dzieje_re.eps}$

2.3 Synchronizacja żądań

Dla każdej kolejki mamy ograniczoną liczbę wolnych żądań. Nie chcemy również żeby jednocześnie na realizacje czekało dowolnie dużo żądań (stała high_queued_sectors). Do realizacji tych dwóch ograniczeń używamy kolejek - odpowiednio - wait_for_request i blk_buffers_wait.
$\includegraphics[width=\textwidth]{04synch.eps}$
Kolejka zadań tq_disk jest bezpośrednio związana z działaniem urządzenia. Intuicyjnie oczywiste jest, że urządzenie powinno być w jakiś sposób dezaktywowane gdy nie ma do niego żadnych żądań, a następnie w odpowiednim momencie ponownie włączone. Realizuje się to w następujący sposób. Gdy nowy bufor przychodzi do pustej kolejki żądań (make_request_fn()), to zanim go wstawimy, wykonujemy procedurę zwaną zatykaniem kolejki (ang. plugging). Polega to na tym, że oznaczamy kolejkę jako zatkaną (ang. plugged, por. Struktury»request_queue) i do kolejki zadań tq_disk wstawiamy zadanie plug_tq, które w stosownym czasie odetka kolejkę (ang. unplug) i uruchomi ponownie metodę request_fn(). Metoda ta podejmie realizację żądań, które się nazbierały w międzyczasie.
$\includegraphics[width=\textwidth]{05plug.eps}$
Kolejka urządzenia może zostać odetkana także przez proces, mający zamiar umieścić się na wait_for_request. Jeśli bowiem brakuje wolnych żądań, to znaczy, że wszystkie już są w kolejce, więc dalsza blokada urządzenia byłaby szkodliwa. Zadania z tq_disk wypuszczane są przez procesy czekające na zmniejszenie się globalnej liczby oczekujących żądań. Tym razem odetkamy wszystkie urządzenia, bo jeśli czeka tak dużo żądań, to znaczy, że prawdopodobnie wiele urządzeń jest niepotrzebnie zatkanych. Procesy czekające na wait_for_request i blk_buffers_wait są zwalniane przez request_fn() przy zwracaniu wolnego żądania (blkdev_release_request()), oczywiście pod warunkiem, że odpowiednie zasoby są już dostępne.

3 Struktury danych

Podstawowe struktury danych wykorzystywane podczas niskopoziomowej obsługi operacji we/wy przedstawia poniższy rysunek.
$\includegraphics[width=\textwidth]{06struct.eps}$
Implementacja uniwersalnych list znajduje się w pliku include/linux/list.h. Zrealizowano je w niezwykle oszczędny (i niezrozumiały) sposób za pomocą struktury list_head:

struct list_head {
	struct list_head *next;
	struct list_head *prev;
}

Aby umieścić jakąś strukturę na liście, należy dodać do niej pole typu list_head, które będzie reprezentowało tę strukturę na liście. Do operowania listami mamy funkcje:

static __inline__ void list_add (struct list_head *new, struct list_head *head);
static __inline__ void list_add_tail (struct list_head *new, struct list_head *head);
static __inline__ void list_del (struct list_head *entry);
static __inline__ int list_empty (struct list_head *head);
static __inline__ void list_splice (struct list_head *list, struct list_head *head);

i śliczne makro:

#define list_entry(ptr, type, member) \
	((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

które zwraca adres komórki pamięci odpowiednio powyżej (o odległość początku struktury type od jej pola memeber) reprezentanta rekordu, czyli wskaźnik do tegoż rekordu.

3.1 `buffer_head`

Opis:
Bufor dostarczany wraz ze zleceniem operacji we/wy. Jest to najmniejszy logicznie obiekt opisujący zlecenie, do realizacji żądania potrzebny jest jeszcze tylko kierunek transmisji (READ/WRITE). Każde żądanie składa się z pewnej ilości buforów, dotyczących tego samego urządzenia i tej samej operacji.
Definicja w pliku include/linux/buffer.h

Definicja:

struct buffer_head {
	char * b_data;			/* wskaźnik do danych */	
	unsigned long b_state;		/* status bufora */
	atomic_t b_count;		/* ilość użytkowników bufora */

	kdev_t b_dev;			/* urządzenie wirtualne */
	unsigned long b_blocknr;	/* numer bloku urządzenia wirtualnego*/
	unsigned short b_size;		/* rozmiar bloku */

	kdev_t b_rdev;			/* rzeczywiste urządzenie */
	unsigned long b_rsector;	/* numer sektora na prawdziwym dysku */	

					/* procedura zakończenia operacji we/wy */
	void (*b_end_io) (struct buffer_head *bh, int uptodate); 
	struct buffer_head *b_reqnext;	/* następny bufor w żądaniu */	
}

Uwagi:
Pole b_state zawiera m.in. następujące flagi

BH_Uptodate: bufor zawiera aktualne dane
BH_Dirty: bufor jest ''brudny'' - trzeba go zapisać
BH_Lock: bufor jest zablokowany
BH_Req: bufor został zażądany
BH_Mapped: bufor jest odwzorowywany na dysku
BH_Protected: bufor jest chroniony, tzn. nie wolno go opróżnić

3.2 `request`

Opis:
Struktura reprezentująca pojedyncze żądanie we/wy. Zawiera listę buforów, do których (lub z których) mają być skopiowane dane. Każdy bufor musi dotyczyć identycznej operacji, obszary adresowe na urządzeniu muszą ze sobą bezpośrednio sąsiadować, bufory oczywiście nie. Całe żądanie nie może być również za długie (max_sectors[], domyślnie MAX_SECTORS).

Definicja:

struct request {
    struct list_head 	queue;		/* miejsce na liście żądań kolejki q*/	
    int 		elevator_sequence; 
			/* dopuszczalna liczba wyminięć (ang. passover) żądania *
			 * aktualizowana po każdym wstawieniu przed to żądanie  */  
    struct list_head 	table;          /* miejsce na liście wolnych żądań kolejki q*/	
    volatile int 	rq_status;	/* RQ_INACTIVE, RQ_ACTIVE */
    kdev_t 		rq_dev;		/* urządzenie */
    int 		cmd;		/* READ, WRITE */
    int 		errors;		/* błędy */

    unsigned long 	sector;			/* numer sektora */
    unsigned long 	nr_sectors;	 	/* łączna liczba sektorów żądania */
    unsigned long 	hard_sector;		
    unsigned long	hard_nr_sectors;
    unsigned int 	nr_segments;
    unsigned int 	nr_hw_segments;
    unsigned long 	current_nr_sectors;	/* liczba sektorów w bieżącym bloku */
    
    void * 		  special;
    char * 		  buffer;	/* obszar pamięci dla operacji we/wy */	
    struct completion *   waiting;
    struct buffer_head *  bh;		/* pierwszy bufor na liście */
    struct buffer_head *  bhtail;	/* ostatni bufor na liście */
    request_queue_t *	  q;		/* kolejka na której znajduje się żądanie */
}

3.3 `request_queue`

Opis:
Kolejka żądań do urządzenia. Posiada pulę wolnych żądań (tworzonych przy inicjacji urządzenia) podzielonych na pół między czytanie i pisanie oraz kolejkę pełnych żądań czekających na realizację.

Definicja:

struct request_queue {
    struct list_head	request_freelist[2]; 	/* wolne żądania */
    struct list_head	pending_freelist[2]; 	/* oddane wolne żądania */
    int			pending_free[2];    

    struct list_head	queue_head;		/* właściwa lista żądań */
    elevator_t		elevator;
    request_fn_proc * 	request_fn;       	/* prawdziwa procedura obsługi żądania */
    merge_request_fn * 	back_merge_fn;		/* doklejanie z przodu i z tyłu */
    merge_request_fn *	front_merge_fn;
    merge_requests_fn *	merge_requests_fn;	/* sklejanie żądań */
    make_request_fn * 	make_request_fn;	/* obsługa nagłówka bufora */
    plug_device_fn * 	plug_device_fn;		/* zatykanie urządzenia */
	
    void *		queuedata		/* prywatne dane sterownika urządzenia */
    struct tq_struct	plug_tq; 		/* "dolna połówka" odtykająca kolejkę */
			/* standardowo: q->plug_tq == {0, generic_unplug_device(), q} */
    char		plugged; 		/* czy kolejka jest zatkana ?*/
    char		head_active; 		/* czy aktualne żądanie jest aktywne ?*/
    spinlock_t		queue_lock; 		/* kiedyś ma zastąpić io_request_lock */
    wait_queue_head_t	wait_for_request; 	/* procesy czekają tu na wolne żądanie */
};

typedef struct request_queue request_queue_t;

3.4 `blk_dev_struct`

Opis:
Struktura przechowująca dane charakterystyczne dla urządzenia blokowego. Tablica blk_dev[] zawiera po jednej takiej strukturze dla każdego urządzenia.

Definicja:

struct blk_dev_struct {
    request_queue_t		request_queue;  /* kolejka żądań */
    queue_proc *		queue;		/* zwraca kolejkę do urządzenia */
    void *			data;		/* dodatkowe dane */
};

extern struct blk_dev_struct blk_dev[MAX_BLKDEV];

3.5 `elevator_s`

Opis:
Obiekt realizujący windowe szeregowanie dostępu (C-LOOK). Linux-owa wersja S-SCAN różni się nieco od standardowej. Dokładniejsze informacje w opisie bh_rq_in_between.

Definicja:

struct elevator_s {		
				 /* ile razy możemy przełożyć (wyminąć) żądanie... */
    int 			 read_latency;	 		/* ...czytania */
    int 			 write_latency;		 	/* ...pisania */	

    elevator_merge_fn *		 elevator_merge_fn;		
    elevator_merge_cleanup_fn *	 elevator_merge_cleanup_fn; 
				 /* uaktualnia queue->elevator_sequence po wyminięciu */
    elevator_merge_req_fn *	 elevator_merge_req_fn;   
				 /* to samo - po połączeniu dwóch żądań */
    unsigned int 		 queue_ID;		
};

typedef struct elevator_s elevator_t;  /* w /include/linux/blkdev.h */

Uwagi:
Domyślnie atrybut request_queue->elevator jest inicjowany jako ELEVATOR_LINUS zdefiniowany jak następuje:

#define ELEVATOR_LINUS			\
((elevator_t) {				\
	8192,				\
	16384,				\
					\
	elevator_linus_merge,		\
	elevator_linus_merge_cleanup,	\
	elevator_linus_merge_req,	\
	})

Funkcje elevator_linus_merge_cleanup() i elevator_linus_merge_req() są prostą implementacją zadań sformułowanych w komentarzach powyżej, zaś elevator_linus_merge() zostanie omówiona osobno.

4 `ll_rw_block()`

Cel:
Niskopoziomowa obsługa operacji wejścia/wyjścia.

Nagłówek:

void ll_rw_block(int rw, int nr, struct buffer_head *bhs[])

Parametry:

int rw: operacja: WRITE, READ, READ (czytanie z wyprzedzeniem - na tak niskim poziomie oznacza po prostu niższy priorytet)
int nr: ilość nagłówków buforów
struct buffer_head *bhs[]: tablica nagłówków buforów reprezentujących zlecenia. Struktura buffer_head jest zdefiniowana następująco:

Algorytm:

ustalamy poprawny rozmiar bloku (correct_size) dla urządzenia, jeśli 0 to przyjmujemy domyślny: BLOCK_SIZE
sprawdzamy czy zażądane bloki mają rozmiar będący wielokrotnością correct_size;
sprawdzamy czy nie żądają (rw) zapisu na urządzenie tylko do odczytu
dla każdego bufora z *bhs[] robimy co następuje:
- sprawdzamy czy nie przekroczyliśmy limitu skolejkowanych sektorów:
```
 quequed_sectors >= high_quequed_sectors
```
  jeśli tak, to ''wisimy'' na blk_buffers_wait, aż spełniony będzie warunek
```
 quequed_sectors < low_quequed_sectors
```
- jeśli bufor jest zablokowany to ignorujemy go i opuszczamy dalszy ciąg obrotu pętli
- zwiększamy licznik użyć bufora i podstawiamy end_buffer_io_sync() (standardowa obsługa końca buforowej operacji we/wy) pod bh->b_end_io
- jeśli piszemy (rw==WRITE) i bufor jest czysty to goto end_io, wpp zaznaczamy, że już jest czysty (to będzie zauważone dopiero po odblokowaniu bufora); jeśli czytamy (READ lub READA) i bufor aktualny to goto end_io; wpp blad (BUG()) i goto end_io
- end_io: wywołujemy metodę b_end_io i rozpoczynamy następny obrót pętli (tzn. obsługę kolejnego bufora)
wywołujemy submit_bh(rw, bh)

5 `submit_bh()`

Cel:
Przesłanie nagłówka bufora do odpowiedniego urządzenia.

Nagłówek:

void submit_bh (int rw, struct buffer_head * bh)

Parametry:

int rw: operacja: WRITE, READ, READ
struct buffer_head *bh: nagłówek bufora

Algorytm:

jeśli BH_Lock nie ustawiony w bh->b_state to BUG()
ustawiamy BH_Req w bh->b_state
ustawiamy b_rdev na b_dev, inicjujemy b_rsector; jeśli urządzenie to np. RAID to trzeba to zrobić inaczej w sterowniku i nie wywoływać tej funkcji, ale bezpośrednio generic_make_request()
generic_make_request (rw, bh)
uaktualniamy statystyki dotyczące ilości operacji WRITE i READ/A

6 `generic_make_request()`

Cel:
Przesłanie nagłówka bufora do odpowiedniego urządzenia.

Nagłówek:

void  generic_make_request(int rw, struct buffer_head * bh)

Parametry:

int rw: operacja: WRITE, READ, READA
struct buffer_head *bh: nagłówek bufora

Algorytm:

sprawdzamy czy zdefiniowano pole bh->b_end_io
jeśli rozmiar urządzenia się nie zgadza, to wypisujemy komunikat jądra i kończymy (bh->b_end_io)
w pętli:
- pobieramy kolejkę urządzenia q = blk_get_queue(bh->b_rdev)
- wywołujemy q->make_request_fn(q, rw, bh)
aż make_request_fn() zadziała, jeśli jednak za którymś razem blk_get_queue() zwróci null to kończymy z błędem

7 `__make_request()`

Cel:
Stworzenie nowego żądania lub dodanie nagłówka do istniejącego żądania. Standardowa metoda q->make_request_fn ().

Nagłówek:

int  __make_request(request_queue_t * q, int rw, struct buffer_head * bh)

Parametry:

request_queue_t q: kolejka żądań do urządzenia
int rw: operacja: WRITE, READ, READ
struct buffer_head *bh: nagłówek bufora

Algorytm:

again:

insert_here = <koniec kolejki q>
jeśli q jest pusta to zatykamy (ang. plug) urządzenie i goto get_rq
sprawdzamy możliwość dołączenia bh do innego żądania:
q->elevator->elevator_merge_fn (q, &req, head, bh, rw, max_sectors)
- jeśli zwróci ELEVATOR_BACK_MERGE lub ELEVATOR_FRONT_MERGE to próbujemy dokleić bufor do żądania req (po czym ewentualnie połączyc je z następnym lub poprzednim żądaniem) i jeśli się udało to koniec
- jeśli zwróci ELEVATOR_NO_MERGE (lub doklejenie się nie udało), to pod insert_here podstawiamy req (jeśli req==null, to zostawiamy starą wartość); jest to miejsce wybrane przez elevator_merge_fn() do wstawienia nowego żądania

get_rq:

jeśli jeszcze nie mamy wolnego żądania, to je pobieramy (get_request (q, rw)) jeśli się nie udało i zlecenie dotyczy pisania lub zwykłego czytania (nie z wyprzedzeniem) to wywołujemy funkcję __get_request_wait(q, rw), która jest blokująca i goto again bo w między czasie mogło się pojawić żądanie, do którego można dokleić bufor bh.
inicjujemy zmienne składowe nowego żądania (w szczególności wstawiamy jako - na razie - jedyny bufor bh) i wołamy add_request(q, req, insert_here), która wstawia żądanie w podane miejsce

Uwagi:

do zapewniania atomowości czynności używamy spinlock-ów
wymagamy by bufor był odwzorowywany na dysku (a nie np. trzymany w pamięci operacyjnej)

8 `elevator_linus_merge()`

Cel:
Sprawdzamy możliwość dołączenia bufora do istniejącego żądania, jeśli się nie da to proponujemy miejsce wstawienia nowego żądania.

Nagłówek:

int elevator_linus_merge (request_queue_t *q, struct request **req,
			 struct list_head * head,
			 struct buffer_head *bh, int rw,
			 int max_sectors)

Parametry:

request_queue_t *q: kolejka, której dotyczy żądanie
struct request **req: tu podstawimy żądanie, do którego należy dołączyć bh, lub po którym należy wstawić nowe
struct list_head * head: początek listy żądań w kolejce q, przesunięty o jedną pozycję do przodu, jeśli prawdziwy początek był aktywny (ang. active), czyli zablokowany do użytku urządzenia
struct buffer_head *bh: nagłówek bufora
int rw: operacja: WRITE, READ
max_sectors: największa dopuszczalna długość żądania

Algorytm:
Dla każdego elementu listy żądań rq (począwszy od ostatniego):

postarzamy żądanie (elevator_sequence-) i jeśli elevator_sequence < 0 to zwracamy ELEVATOR_NO_MERGE, bo wstawienie bufora gdziekolwiek przed rq (poruszamy się w kierunku początku listy) spowodowałoby dalsze opóźnienie.
jeśli inne urządzenia (przeważnie partycje) to continue
sprawdzamy czy można tu wstawić nowe żądanie (bh_rq_in_between()) i jeśli tak to zapamiętujemy rq w req
jeśli różnią się operacje (READ/WRITE) lub łączna długość żądania i bufora (w sektorach) przekracza max_sectors to continue
elevator_sequence za mały w stosunku do rozmiaru bufora to zwracamy ELEVATOR_NO_MERGE (ale jeśli w 3. można było wstawić nowe żądanie, to zezwalamy na to)
jeśli rq sąsiaduje z żądaniem związanym z bh to zwracamy ELEVATOR_BACK_MERGE lub ELEVATOR_FRONT_MERGE w zależności od okoliczności; wpp. zwracamy ELEVATOR_NO_MERGE

9 `bh_rq_in_between()`

Cel:
Sprawdzamy czy nowe żądanie dla bufora można wstawić za podanym żądaniem. Zwracamy 0 albo 1.

Nagłówek:

int bh_rq_in_between (struct buffer_head *bh,
		     struct request *rq,
		     struct list_head *head)

Parametry:

struct buffer_head *bh: nagłówek bufora
struct request *rq: za tym żądaniem chcemy wstawić nowe
struct list_head * head: początek listy

Algorytm:

jeśli rq jest ostatnie na liście to zwracamy 0
przez next oznaczamy żądanie następujące na liście po rq
jeśli rq i next dotyczą innych urządzeń, to sprawdzamy tylko czy bh jest fizycznie po rq i jeśli tak to zwracamy 1 (wpp. 0)
jeśli rq, bh i next są ustawione w kolejności rosnącej to zwracamy 1
jeśli rq i next są uporządkowane, ale bh nie jest między nimi, to zwracamy 0
jeśli rq i next nie są uporządkowane, ale bh jest fizycznie po rq lub przed next to również zwracamy 1, wpp. 0

Uwagi:

porządek na żądaniach i buforach, to porządek indukowany przez relację między ich pierwszymi sektorami

Filip Murlak
2001-12-13