Алгоритм планирования CFQ

Question

Алгоритм CFQ использует упорядоченный набор очередей на основе приоритета ввода-вывода процессов, которые выполняли запросы. Это означает, что есть очередь для процесса приоритета, допустим, 1, другая для приоритета 2 и т. Д.

Я понимаю, что алгоритм берет первый запрос из каждой очереди, сортирует их (чтобы избежать ненужных движений головы) и поместите их в очередь отправки для обработки. Но поскольку один запрос может иметь много блоков для чтения (не обязательно смежных), как это возможно? То есть, если у меня есть:

Request1 = [1,2,345,6,423] 

и

Request2 = [3,4,2344,664] 

будучи [а, б, в] список блоков а, В и С, как являются resquests 1 и 2, помещенные в очередь отправки? Как видите, у них есть непустое пересечение (например, блок 6 находится после блоков 3 и 4)

Другое дело, что я не получаю, опять же, поскольку запрос может иметь кратные блоки для чтения, что в нем делается вид планирования? FCFS? или он заказывает блоки?

Например, предположим, что у нас есть запрос, который содержит следующий список блоков следующим образом:

[1,23,5,76,3] 

Как бы алгоритм справиться с этим?

по FCFS:

[1,23,5,76,3] 

или путем сортировки блоков:

[1,3,4,23,76] 

Может быть, я не понял алгоритм, не мог найти достаточно документации. Если у кого есть ссылка на бумагу с более подробным объяснением, пожалуйста, обратитесь к ней.

Answer 1

I my understandig, CFQ не назначает запросы на одну дорожку, а также временные интервалы для нескольких запросов. Цитата IA64wiki:

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

Каждый процесс, выдающий ввод-вывод, получает временной срез, в течение которого он имеет эксклюзивный доступ для синхронных запросов. Временной срез ограничен двумя параметрами: slice_sync с поправкой на приоритет ввода-вывода процесса дает длину в миллисекундах каждого фрагмента; и quantum дает количество запросов, которые могут быть выданы.

Все процессы совместно используют набор из 17 очередей для асинхронного ввода-вывода, один для каждого эффективного приоритета ввода-вывода. Каждая очередь получает временной срез на основе slice_async, скорректированный по приоритету), а очереди обрабатываются round-robin.

В пределах каждого среза, запросы будут объединены (как спереди, так и сзади), а выпускается в соответствии с SCAN, с отсталой стремится к back_seek_max разрешенной, но необъективно по сравнению с back_seek_penalty вперед стремится. CFQ будет ждать до slice_idle мс внутри среза для процесса , чтобы выдавать больше ввода-вывода. Это позволяет прогнозировать, а также улучшает справедливость, когда процесс выдает всплеск ввода-вывода; но в целом он снижает производительность .