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

Лифт Noop

Это простейший алгоритм планирования ввода/вывода. Упорядоченная очередь отсутствует, новые запросы всегда добавляются либо в начало, либо в конец диспетчерной очереди, а следующий запрос, подлежащий обработке, всегда стоит первым.

Лифт CFQ

Основной целью лифта CFQ является гарантия справедливого разделения пропускной способности диска между всеми процессами, выдавшими запросы на ввод/вывод. Для достижения этой цели лифт пользуется большим количеством отсортированных очередей (по умолчанию 64), которые содержат запросы, поступающие от различных процессов. Когда запрос передается лифту, ядро вызывает хеш-функцию, преобразующую идентификатор группы потоков текущего процесса (обычно этот идентификатор соответствует PID) в индекс очереди. Затем лифт добавляет новый запрос в конец этой очереди. Таким образом, запросы, поступившие от одного процесса, всегда находятся в одной очереди.

Для заполнения диспетчерной очереди лифт сканирует очереди по кругу, выбирает первую непустую и переносит из нее пакет запросов в диспетчерную очередь.

Лифт Deadline

Кроме диспетчерной очереди, лифт Deadline использует еще четыре очереди. Две из них, отсортированные очереди, содержат, соответственно, запросы на чтение и на запись, упорядоченные по первым номерам секторов. Две других, очереди крайнего срока, содержат те же запросы, упорядоченные по ”край- ним срокам” их выполнения. Эти очереди призваны не допустить "голодной смерти” запросов, т. е. ситуации, при которой лифт долгое время игнорирует отдельные запросы, предпочитая обрабатывать те, что находятся ближе к последнему обработанному запросу. Крайний срок выполнения запроса определяется таймером, который стартует, когда запрос передается лифту. По умолчанию время ожидания запросов на чтение составляет 500 мс, а запросов на запись — 5 с. Запросы на чтение имеют более высокий приоритет, чем запросы на запись, потому что они обычно блокируют процессы, выдавшие их. Крайний срок выполнения гарантирует, что планировщик обработает запрос, долго ждущий своей очереди, даже если запрос находится далеко от начала списка.

Когда лифт должен пополнить диспетчерную очередь, он вначале определяет направление движения данных у следующего запроса. При наличии запросов, как на чтение, так и на запись, лифт выбирает направление "чтение”, если только направление запись” не было отвергнуто много раз (голодная смерть” запросов на запись недопустима).

Затем лифт просматривает очередь крайнего срока для выбранного направления. Если крайний срок выполнения первого запроса в очереди истек, лифт переносит этот запрос в конец диспетчерной очереди. Кроме того, он переносит туда пакет запросов из отсортированной очереди, начиная с запроса, следующего за тем, у которого истек крайний срок. Длина такого пакета зависит от того, относятся ли запросы в нем к физически смежным порциям данных на диске (чем больше смежных” запросов, тем длиннее пакет).

Если же ни у одного запроса крайний срок еще не истек, лифт переносит в диспетчерную очередь пакет запросов, начиная с запроса, следующего за последним запросом, взятым из отсортированной очереди. Когда курсор достигает конца отсортированной очереди, ее просмотр возобновляется с начала (так называемый лифт с односторонним движением).