Systemy Wejścia-Wyjścia
Szeregowanie żądań urządzeń blokowych

Wstęp

Struktury

struct blk_dev_struct {
	//kolejka żądań
	request_queue_t		request_queue;
	
	//funkcja zwracająca kolejkę żądań
	queue_proc		*queue;
	(...)
};

struct blk_dev_struct blk_dev[MAX_BLKDEV]

struct request_queue
{
	//lista z wolnymi żądaniami (jedna do czytania, druga do pisania) 
	struct list_head	request_freelist[2];
	
	//wskaźnik na początek kolejki
	struct list_head	queue_head;
	
	//algorytm windy dla przetwarzania zleceń
	elevator_t		elevator;
	
	//wskaźnik na funkcję odpowiedzialną za realizację żądań
	request_fn_proc		* request_fn;
	
	//wskaźniki na funkcje odpowiadające za łączenie żądań (np. sąsiadujących obok siebie)
	merge_request_fn	* back_merge_fn;
	merge_request_fn	* front_merge_fn;
	merge_requests_fn	* merge_requests_fn;
	
	//wskaźnik na funkcję odpowiadającą za odpowiednie dodawanie nowych żądań
	//ona też wywołuje request_fn 
	make_request_fn		* make_request_fn;
	
	//struktura i wskaźnik na funkcje realizującą spiętrzenie żądań
	plug_device_fn		* plug_device_fn;
	struct tq_struct	plug_tq;
	
	//prawda lub fałsz, jeżeli kolejka jest zakorkowana lub nie
	char			plugged;

	//wartość logiczna oznaczająca czy bieżące żądanie jest aktywne czy nie
	char			head_active;

 	//wartość używana między innymi do testowania błędów IO 
	char                    oneshot_error;
	 
	//W przyszłości ma chronić kolejkę io_request_lock 
	spinlock_t		queue_lock;

	//Kolejka zadań czekająca na wolne żądania, ponieważ kolejki żądań mają stały rozmiar
	wait_queue_head_t	wait_for_request;
	(...)
};

Kolejka żądań ma określony stały rozmiar zdefiniowany:
total_ram = nr_free_pages() << (PAGE_SHIFT - 10);
total_ram = (total_ram + MB(32) - 1) & ~(MB(32) - 1);
	if ((queue_nr_requests = total_ram >> 9) > QUEUE_NR_REQUESTS)
		queue_nr_requests = QUEUE_NR_REQUESTS;

struct request {
	(...)
	//sekwencja pomocnicza dla algorytmu windy
	int elevator_sequence;

	//status żądania przyjmujący odpowiednio wartości:
	volatile int rq_status;	/* should split this into a few status bits */
#define RQ_INACTIVE		(-1) //żądanie jest nieaktywne
#define RQ_ACTIVE		1	 //żądanie jest aktywne (przetwarzane)
#define RQ_SCSI_BUSY		0xffff //statusy specjalne
#define RQ_SCSI_DONE		0xfffe
#define RQ_SCSI_DISCONNECTING	0xffe0
	
	//opis urządzenia, na które zostało skierowane żądanie
	kdev_t rq_dev;
	
	//czy piszemy czy czytamy
	int cmd;		
	
	//ilość błędów dla danego żądania
	int errors;
	
	//dane żądania
	unsigned long start_time;
	unsigned long sector;
	unsigned long nr_sectors;
	unsigned long hard_sector, hard_nr_sectors;
	unsigned int nr_segments;
	unsigned int nr_hw_segments;
	unsigned long current_nr_sectors;
	void * special;
	char * buffer;
	struct completion * waiting;
	
	//wskaźnik na początek i koniec bufora danego żądania
	struct buffer_head * bh;
	struct buffer_head * bhtail;
	
	//wskaźnik na kolejkę żądań
	request_queue_t *q;
};

Przetwarzanie żądań

void ll_rw_block(int rw, int nr, struct buffer_head * bhs[])
{
	//na początku następuje określenie poprawnego rozmiaru bloku dla urządzenia.
	// Następnie sprawdzane jest czy rozmiar buforów bhs[] jest odpowiedni	
	for (i = 0; i < nr; i++) {
		if (bh->b_size % correct_size) {
			goto sorry;
		}
		if (buffer_delay(bh) || !buffer_mapped(bh))
			BUG();
	}

	//sprawdzane jest także czy dane urządzenie jest do zapisy w przypadku 
	//żądania zapisu
	if ((rw & WRITE) && is_read_only(bhs[0]->b_dev)) {
		goto sorry;
	}
	
	//następnie dla każdego bufora wykonujemy
	for (i = 0; i < nr; i++) {
	
		//jeżeli ilość sektorów zablokowanych jest za duża to 
		//kolejka jest odkorkowywana i następuje czekanie aż nie zostanie osiągnieta
		//dolna bariera zablokowanych sektorów 
		if (atomic_read(&queued_sectors) >= high_queued_sectors) {
			run_task_queue(&tq_disk);
			wait_event(blk_buffers_wait,atomic_read(&queued_sectors) < low_queued_sectors);
		}

		(...)
		
		//po synchronizacji i zapewnieniu poprawności bufor jest wstawiany jako żądanie
		submit_bh(rw, bh);
	}
	return;

sorry:
	//czyszczenie
}

total_ram = nr_free_pages() << (PAGE_SHIFT - 10);
high_queued_sectors = (total_ram * 2) / 3;
low_queued_sectors = high_queued_sectors / 3;
	if (high_queued_sectors - low_queued_sectors > MB(128))
		low_queued_sectors = high_queued_sectors - MB(128);
high_queued_sectors <<= 1;
low_queued_sectors <<= 1;

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

1. Korkuje pustą kolejkę
2. Jeżeli kolejka nie jest pusta to używa elevator oraz scala żądania (o ile jest to możliwe)
3. Aby pobrać obiekt request niezbędne jest, aby ilość zaalokowanych żądań była mniejsza niż pewna ustalona stała. Jeżeli nie ma wolnego miejsca na żądanie, wykonywane jest odblokowanie kolejki.
4. Wstawia nowe żądanie do kolejki.