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


Лифт Noop

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

Лифт CFQ

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

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

Лифт Deadline

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

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

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

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

Предыдущая страница | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 | Следующая страница




Возможно, Вас также заинтересует:

ОС Knoppix - это Linux без про...

ВведениеЕсли вы цените свое время, умеете считать деньги и знаете стоимость информации, то эта книга...

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

Спин-блокировкаСпин-блокировка необходима в многопроцессорной системе, потому что могут возникнуть...

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

Копирование при записи В системах Unix первых поколений создание процесса было реализовано довольно...

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

Буферы блоков и головы буферовУ каждого буфера есть дескриптор голова буфера, имеющий тип buffer...