7.2.2 Szeregowanie zadan

Spis tresci

• Struktury danych
• Szeregowanie zadan
• Procedura strategii
• Zrodla informacji

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.

Funkcja add_request

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

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);		    
}

• 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

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;
}

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);
}

• 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.

1. Pliki z kodem zrodlowym Linuxa:
   • include/linux/blk.h
   • include/linux/blkdev.h
   • drivers/block/ll_rw_blk.c
   • drivers/block/hd.c
2. Michael K. Johnson: Kernel Hackers' Guide - artykuly o urzadzeniach blokowych
3. Michael K. Johnson: Writing Linux Device Drivers