Szeregowanie zadan
do spisu tresci tematu 7
7.2.2 Szeregowanie zadan
Spis tresci
Struktury danych
Szeregowanie zadan
Procedura strategii
Zrodla informacji
Struktury danych
Kazde urzadzenie blokowe, a wlasciwie program jego obslugi, ktory moze obslugiwac
kilka urzadzen, ma w opisujacej go strukturze
blk_dev_struct wskaznik na
posortowana liste zadan (nie mylic z zadaniami). Kazde zadanie opisane jest
przez dluga strukture request zdefiniowana w pliku
include/linux/blkdev.h.
struct request {
volatile int rq_status;
kdev_t rq_dev;
int cmd;
int errors;
unsigned long sector;
unsigned long nr_sectors;
unsigned long current_nr_sectors;
char * buffer;
struct semaphore * sem;
struct buffer_head * bh;
struct buffer_head * bhtail;
struct request * next;
}
rq_status
moze przyjmowac wartosc: RQ_ACTIVE - zwykle zadanie, RQ_INACTIVE - zadanie
juz wykonane, RQ_SCSI_BUSY, RQ_SCSI_DONE, RQ_SCSI_DISCONNECTING - jak
latwo sie domyslec dotycza urzadzen SCSI,
rq_dev
okresla urzadzenie (numer glowny i drugorzedny), do ktorego skierowane jest
zadanie
cmd
rodzaj zadania, moze byc rowny READ albo WRITE;
errors
licznik bledow otrzymanych podczas realizowania zadania - jesli przekroczy
pewna wartosc, okreslana przez program obslugi urzadzenia, to zadanie zostaje
usuniete i nieobsluzone,
sector, nr_sectors
kazde zadanie dotyczy zwartego fragmentu urzadzenia, opisywanego przez poczatkowy
sektor i dlugosc fragmentu,
current_nr_sectors
liczba sektorow, ktora pozostala do wczytania/zapisania,
buffer
wskaznik do danych zawartych w buforach
bh, bhtail
wskazniki na poczatek i koniec listy buforow odpowiadajacych fragmentowi urzadzenia
sem
semafor uzywany przez programy obslugi urzadzen SCSI i przy korzystaniu
z pliku wymiany;
Zadania dla wszystkich urzadzen blokowych znajduja sie w tablicy
all_requests o wielkosci 64 elementow, z czego 2/3 moze byc
zajete przez zadania zapisu. Proces, ktory chce zlecic urzadzeniu operacje
wejscia-wyjscia, a nie znajdzie wolnej pozycji w tablicy all_requests
zawiesza sie na kolejce wait_for_request.
Po wstawieniu do tablicy, kazde nowe zadanie wstawiane jest na liste zadan dla
konkretnego programu obslugi urzadzenia. Tak zwany Algorytm windy
(
Elevator algorithm) wstawia zadanie na wlasciwe miejsce utrzymujac liste
posortowana leksykograficznie po numerach drugorzednych urzadzenia, do ktorego
zadanie jest skierowane (numery glowne urzadzen w obrebie kolejki sa takie same),
i po pierwszym sektorze, ktorego zadanie dotyczy. W starszych wersjach Linuxa
zadania czytania umieszczane byly przed zadaniami zapisu, stwierdzono jednak
lepsze dzialanie systemu przy rownorzednym traktowaniu operacji.
Szeregowanie zadan
Funkcja ll_rw_block zdefiniowana w pliku
drivers/block/ll_rw_blk.c jest uzywana przez wszystkie urzadzenia
blokowe, a sluzy do spelniania skierowanych do nich zadan. Zanim opisze ja
dokladniej, przedstawie pomocnicze funkcje uzywane do utworzenia nowego zadania
i wstawienia go do kolejki.
Funkcja
add_request
wstawia zadanie umieszczone juz w tablicy
all_requests na wlasciwe miejsce w kolejce zadan urzadzenia.
DEFINICJA:
void add_request( struct blk_dev_struct * dev,
/* wskaznik na strukture opisujaca urzadzenie */
struct request * req )
/* wskaznik na strukture opisujaca zadanie */
{
wylacz przerwania (cli);
zaznacz bufor zadania jako czysty (mark_buffer_clean);
if( w kolejce urzadzenia nie ma zadan )
{
wstaw zadanie na poczatek kolejki;
wywolaj procedure strategii urzadzenia;
przywroc przerwania (sti);
return;
}
wstaw zadanie na wlasciwe miejsce;
if( urzadzenie jest typu SCSI )
wywolaj procedure strategii urzadzenia;
przywroc przerwania;
}
Funkcja
make_request
zajmuje sie utworzeniem nowego zadania i wstawieniem go do tablicy
all_requests
DEFINICJA:
static void make_request( int major, /* glowny numer urzadzenia */
int rw, /* rodzaj zadania */
struct buffer_head * bh ) /* bufor
ktorego zapisania lub odczytania zadamy */
{
if( bufor zajety )
return
zajmij bufor (lock_buffer);
if ( rw == READ i bufor zawiera aktualne dane ) {
zwolnij bufor;
return;
}
if ( rw == WRITE i bufor nie jest "brudny" (dirty) )
zwolnij bufor;
return;
}
wylacz przerwania (cli);
przejdz kolejke zadan urzadzenia, dla kazdego zadania:
sprawdz czy bufor bh mozna dolaczyc na poczatku lub na koncu
listy buforow zadania tak, zeby otrzymac uporzadkowana liste
kolejnych blokow urzadzenia, jesli tak, to
{
dolacz bufor do tej kolejki;
uaktualnij opis zadania;
przywroc przerwania;
return;
}
sprobuj znalezc wolne miejsce w tablicy all_requests;
if( nie ma miejsca i zadanie dotyczy operacji z wyprzedzeniem ) {
zwolnij bufor;
return;
}
czekaj na wolne miejsce w tablicy all_request (add_wait_queue);
wypelnij strukture request;
wstaw strukture do kolejki zadan urzadzenia (add_request);
}
Sama funkcja ll_rw_block dostaje jako parametr liste buforow
do ktorych ma wczytac dane, nastepnie:
sprawdza, czy wielkosc buforow odpowiada wielkosci blokow urzadzenia
sprawdza, czy urzadzenie nie jest tylko do odczytu, jesli zadanie dotyczy
zapisu danych
wywoluje dla kazdego bufora funkcje make_request
Procedura strategii
Wiemy juz jak zadania wczytania i zapisania danych znajduja sie w kolejce zadan
do urzadzenia - robi to wspolna dla wszystkich urzadzen blokowych funkcja
ll_rw_block. Oczywiscie obsluga zadan nalezy juz do konkretnego
sterownika, zajmuje sie tym jego funkcja strategii (Strategy routine)
uzywajac niskopoziomowych funkcji do zapisywania i odczytywania danych.
Schemat dzialania programu obslugi urzadzenia
Najpierw funkcja pomocnicza wywolywana przez procedure strategii po zakonczeniu
przetwarzania pojedynczego zadania:
DEFINICJA:
static void end_request( byte uptodate ) /* 1 - gdy zadanie zakonczylo
sie pomyslnie, 0 w p.p */
{
zadanie - aktualnie obslugiwane zadanie;
aktualny bufor - bufor, ktorego dotyczyla ostatnia operacja;
if( uptodate == 0 ) {
wypisz komunikat o bledzie (printk);
}
if( uptodate == 1)
zaznacz aktualny bufor jako zawierajacy aktualne dane;
zwolnij aktualny bufor;
if( lista zadania zawiera wiecej buforow )
nastepny bufor z listy staje sie aktualnym buforem;
return;
}
zaznacz zadanie jako wykonane (ustaw RQ_INACTIVE);
przesun wskaznik zadan na nastepne zadanie na liscie urzadzenia;
obudz procesy czekajace na miejsce w tablicy zadan;
}
Teraz ogolny algorytm dzialania procedury strategii - wlasciwe wszytkie urzadzenia
blokowe uzywaja podobnych algorytmow - zobacz
opis sterownika dysku twardego.
void procedura_strategii( void )
{
if( lista zadan pusta )
wylacz obsluge przerwan od urzadzenia;
return;
if( ustawiona obsluga przerwania (co znaczy ze czekamy na
zakonczenie obslugi jakiegos zadania) )
return;
zadanie - pierwsze zadanie z listy;
if( zadanie dotyczy zapisu )
ustaw procedure obslugi przerwania;
wywolaj niskopoziomowa procedure zapisu;
return;
if( zadanie dotyczy odczytu )
ustaw procedure obslugi przerwania - inna
niz dla zapisu;
wywolaj niksopoziomowa procedure odczytu;
return;
nieznane polecenie - panikuj (panic);
}
Uwagi:
Wywolanie procedury strategii "opakowane" jest w procedure ktora
wylacza sprzetowe przerwanie od urzadzenia przed wywolaniem strategii
i wlacza je po powrocie z procedury strategii.
Procedury obslugi przerwan ustawione przed zainicjowaniem zapisu
lub odczytu z urzadzenia:
odczytuja status urzadenia (z portow wejscia-wyjscia);
odczytuja z portow dane (jesli obsluguja odczytywanie danych);
jesli kolejka zadan do urzadzenia nie jest pusta, to wywoluja
procedure strategii.
Dokladne omowienie procedury strategii i precedur obslugi przerwan
znajduje sie w nastepnym rozdziale, poswieconym programowi obslugi
dysku.
Zrodla informacji
Pliki z kodem zrodlowym Linuxa:
include/linux/blk.h
include/linux/blkdev.h
drivers/block/ll_rw_blk.c
drivers/block/hd.c
Michael K. Johnson: Kernel Hackers' Guide - artykuly o urzadzeniach blokowych
Michael K. Johnson: Writing Linux Device Drivers
Artur Zawlocki
Wyszukiwarka
Podobne podstrony:
Linux714 (3)Linux714Linux735linux721Linux712 (4)Linux736 (4)Linux736 (3)Linux713 (2)więcej podobnych podstron