Linux Kernel (Ядро линукса) (часть 2)

Лифт Anticipatory

Лифт Anticipatory является самым сложным планировщиком ввода/вывода, предлагаемым Linux. Он основан на лифте Deadline, у которого он позаимствовал базовый механизм: две очереди крайнего срока и две отсортированные очереди. Планировщик постоянно сканирует отсортированные очереди, чередуя запросы на чтение с запросами на запись, но отдавая предпочтение первым. Сканирование происходит последовательно, если у какого-то запроса не истек крайний срок выполнения. По умолчанию крайний срок выполнения запросов на чтение составляет 125 мс, а запросов на запись — 250 мс. Впрочем, лифт использует дополнительную эвристику:
- в некоторых случаях лифт может выбрать запрос, стоящий перед текущей позицией в отсортированной очереди, заставляя головку двигаться над диском в обратном направлении. Как правило, это происходит, если расстояние поиска для этого запроса меньше половины расстояния поиска запроса, стоящего после текущей позиции в отсортированной очереди;
- лифт собирает статистику о характере операций ввода/вывода, выполняемых каждым процессом в системе. Сразу после размещения запроса на чтение, поступившего от процесса Р, лифт проверяет, принадлежит ли следующий запрос в отсортированной очереди тому же процессу Р. Если это так, следующий запрос заносится в диспетчерную очередь немедленно. В противном случае лифт просматривает статистику, относящуюся к процессу Р. Если лифт решит, что Р, вероятно, вскоре выдаст еще один запрос на чтение, он подождет некоторое время (по умолчанию 7 мс). Таким образом лифт может предвидеть запрос на чтение от процесса Р, "близкий" на диске к только что размещенному запросу от того же процесса.

Выдача запроса планировщику ввода/вывода

Как было сказано ранее В ЭТОЙ главе, функция generic_make_request ВЫЗЫ- вает метод make request fn дескриптора очереди запросов, чтобы передать запрос планировщику ввода/вывода. Этот метод обычно реализуется функцией make request , которая принимает в качестве параметров дескриптор
request queue (параметр q) и дескриптор bio (параметр bio). Функция выполняет следующие действия:
1. Вызывает функцию bik queue bounce о для установки промежуточного буфера, если он необходим. Если промежуточный буфер уже был создан, функция make request работает с ним, а не с оригинальным bio.
2. Вызывает функцию планировщика eiv_queue_empty, чтобы проверить, имеются ли ждущие запросы в очереди запросов. Обратите внимание, что диспетчерная очередь может быть пуста, но другие очереди планировщика ввода/вывода могут содержать ждущие запросы. Если ждущих запросов нет, описываемая функция вызывает функцию bik piug device о для закупоривания очереди запросов
3. На этот шаг функция попадает, если очередь запросов не пуста. Функция вызывает функцию планировщика eiv merge , которая проверяет, может
ли новый bio быть включен в существующий запрос, и возвращает одно из трех значений:
• elevator no merge — bio не может быть включен в существующий запрос. В таком случае описываемая функция переходит к шагу 5;
• elevator back merge — bio может быть добавлен в качестве последнего дескриптора в некоторый запрос req. В таком случае функция вызывает метод q->back_merge_fn, ЧТОбы Проверить, МОЖНО ЛИ расширить ЭТОТ запрос. Если нельзя, она переходит к шагу 5. В противном случае функция заносит дескриптор bio в конец списка, принадлежащего запросу req и обновляет поля этого запроса. Затем она пытается слить запрос со следующим (не исключено, что новый bio заполнил "дыру” между двумя запросами);
• elevator front merge — bio может быть добавлен в качестве первого дескриптора в некоторый запрос req. В таком случае функция вызывает метод q- > f г on t_me г ge_f п, ЧТОбы Проверить, МОЖНО ЛИ расширить ЭТОТ запрос. Если нельзя, она переходит к шагу 5. В противном случае функция заносит дескриптор bio в начало списка, принадлежащего запросу req и обновляет поля этого запроса. Затем она пытается слить запрос с предыдущим в очереди.
4. Итак, bio вставлен в уже существующий запрос. Функция переходит к шагу 7, чтобы выполнить заключительные действия.
5. На этот шаг функция попадает, если bio должен быть вставлен в новый запрос. Функция выделяет дескриптор нового запроса. В случае нехватки памяти функция приостанавливает текущий процесс, если не установлен флаг bio rw ahead в поле bio->bi_rw, означающий, что данная операция является операцией опережающего чтения Если флаг установлен, функция вызывает функцию bio endio и завершает свою работу, т. к. пересылка данных выполнена не будет. Описание функции bio endio приведено в шаге 1 описания функции generic make request о ранее в этой главе.
6. Инициализирует поля дескриптора запроса. В частности:
• инициализирует различные поля, где хранятся номера секторов, текущий bio и текущий сегмент, в соответствии с содержимым дескриптора
bio;
• устанавливает флаг req cmd в поле flags (нормальная операция чтения или записи);
• если страничный кадр первого сегмента Ыо находится в нижней памяти, функция записывает в поле buffer линейный адрес этого буфера;
• записывает В ПОЛе rq_disk адрес bio->bi_bdev->bd_disk;
• вставляет bio в список запросов;
• присваивает ПОЛЮ start time Значение jiffies.
7. Все сделано. Однако перед завершением работы функция проверяет, установлен ли флаг bio rw sync в поле bio->bi_rw. Если установлен, она вызывает generic unplug device применительно К ОЧереДИ запросов, Чтобы откупорить драйвер 8.

Завершает работу

Если очередь запросов не была пуста перед вызовом функции make_
request , то либо очередь запросов уже откупорена, либо она будет откупорена вскоре, поскольку у каждой закупоренной очереди запросов q, содержащей ждущие запросы, есть включенный динамический таймер q->unpiug_ timer. С другой стороны, если очередь запросов была пуста, функция
make request закупоривает ее. Рано (после выхода ИЗ make_request,
если флаг bio rw sync установлен) или поздно (когда таймер откупоривания закончит отсчет) очередь запросов будет откупорена. Как бы то ни было, в конечном счете, процедура-стратег драйвера блочного устройства позаботится о запросах в диспетчерной очереди
Функция blk_queue_bounce

Функция blk queue bounce анализирует флаги В ПОЛе q->bounce_gfp И ПОрОГ в поле q->bounce_pfn, чтобы определить, требуется ли контроль границ буферов. Необходимость в этом возникает, когда некоторые из буферов запроса расположены в верхней памяти, и аппаратное устройство не может адресовать их.

Старые схемы DMA для шин ISA работали только с 24-битовыми физическими адресами. В этом случае порог контроля границ буферов устанавливается равным 16 Мбайт, что соответствует страничному кадру номер 4096. Однако драйверы блочных устройств обычно не применяют контроля границ буферов, когда работают со старыми устройствами. Вместо этого они предпочитают сразу выделять буферы прямого доступа к памяти в зоне памяти