Для начала хочу напомнить, что дисковая адресация состоит из трех параметров CHS - цилиндры, головки и сектора. Набор этих трех параметров дает точное месторасположение физического блока. Изначально, чтобы обратиться к нужному блоку нужно знать эти параметры, но современные диски не заставляют операционную систему обладать такими знаниями. Вместо этого у них есть собственные таблицы уникальных номеров блоков, где каждый блок имеет свой номер и соответствующую ему триаду CHS. А современные операционные системы умеют этим пользоваться при помощи механизма LBA - logical block address. То есть другими словами, операционная система передает диску только номер блока, а тот сам по таблице находит куда ему идти. Однако есть очень важный факт: в такой таблице адреса не последовательны. То есть если после номера блока 412 идет блок 413, это еще не означает, что на диске эти блоки расположены последовательно.
Файловые системы, будучи чисто программной сущностью, оперируют своими логическими блоками. Как правило один логический блок файловой системы это целое число физических блоков диска.
Теперь о скедулерах. У скедулера есть две базовые задачи: слияние нескольких запросов в один единый и упорядочивание запросов.
Слияние. Например поступила задача обратиться к блокам 218, 372, 750. Следом поступила вторая задача, обратиться к блоку 501. Скедулер затолкает второй запрос в первый и сделает ряд: 218, 372, 750, 501. Считать придется столько же информации, но количество операций ввода-вывода сократится ровно вдвое.
Упорядочивание. Это основная и самая сложная задача скедулера. Самый простой вариант выглядит так: поступила задача считать блоки 200, 539, 107 и 688. Скедулер переставляет местами блоки: 107, 200, 539, 688. Делается это для того, чтобы не гонять головку по всему блину туда-сюда, потому что это лишний расход времени, а пройтись ровненько от начала до конца, тем самым увеличив производительность.
Так как операции чтения выполняются в синхронном режиме (каждая последующая ждет пока не закончится предыдущая), то в случае задержки операции, тормозится вся очередь. Кроме того, очевидно, что операции чтения должны предоставить актуальные данные, а значит в случае, если страничный кэш их не дает, то запрос блокируется и ждет. Тогда вся последующая очередь опять же задерживается на еще дольший период. Это называется read latency.
Операции записи наоборот могут быть произведены всей кучей. Для всех запросов одновременно начинается операция ввода-вывода и это делает большой скачок нагрузки на диск. Получается, что операции чтения, при такой агрессии операций записи, вообще в состоянии обиженных вниманием и начинается перекос. Этот феномен называется writes-starving-reads (запись-обделяет-чтение).
В случае, если скедулер начинает слепо вставлять новые запросы по порядку блоков в общий ряд, то значит, что все запросы недалеко от центра шпинделя будут выполняться быстро, а те, что обращаются к краям "блина" очень не скоро. Это также сильно бьет по производительности. Таким образом одна из основных задач скедулера - не допустить обделения крайних блоков вниманием.
Для этого придумали алгоритм Linus Elevator. Я нашел в двух разных источниках два метода его работы. Какой из них на самом деле, я не знаю, потому опишу оба:
1) Скедулер все же сортирует запросы по месторасположению блоков, но если появляются запросы, которые подозрительно долго стоят в очереди, то очередь начинает сливаться без сортировки. Как толькоо таких запросов не будет, то он опять начинает сортировать.
2) Скедулер выстраивает запросы как элеватор - вставлено будет все, но обработано только то, в какую сторону движется этот элеватор. Например он прошел блоки 17, 190, 404. В этот момент вставляется блок 512. Он его так же проходит. Затем вставляется блок 391. Элеватор не возврашается к нему назад, он продолжает намеченные блоки только по возрастанию. Дойдя до края, он возвращается назад к центру и уже тогда после какого-нибудь 439-го блока будет считан 391.
Время ожидания операции чтения/записи у этого алгоритма регулируется утилитой elvtune.
Теперь более подробно про каждый скедулер.
NCQ I/O Scheduler.
Единственный в списке аппаратный скедулер, встроенный в SATA-диски.
Проверить, поддерживает ли Ваш диск его, можно командой:
Noop I/O Scheduler.
Это самый простой скедулер. Не делает вообще ничего. Единственно его правило: FIFO (первый вошел - первый вышел). Запросы совсем не сортируются.
Используется только там, где нету проблемы беготни головки. Например SSD-диски, Flash-диски и так далее.
Deadline I/O Scheduler
Так же, как и стандартный скедулер обладает сортированной очередью, где следующий обслуживаемый запрос находится в ее голове. Но кроме нее у него есть еще две очереди, где запросы не сортированы и лежать в порядке FIFO, то есть по времени создания запроса. По одной очереди на чтение и на запись. У каждой из этих очередей есть своё время дедлайна. Через предложение объясню зачем.
Как только появляется новый запрос, он встает сразу в две очереди: в свою (в зависимости от того чтение он или запись) FIFO-очередь и в общую сортированную.
По началу элеватор идет по стандартной очереди, в которой запросы упорядочены по номеру запрашиваемого блока, но если в одной из FIFO-очередей появляется запрос старше, чем время дедлайна для данной очереди, то скедулер начинает разбирать эту очередь.
Таким образом решена, ну или сведена к минимуму, проблема writes-starves-reads.
Anticipatory I/O Scheduler
Например был обслужен некоторый запрос для конкретного приложения. Результат запроса отдан приложению, скедулер возвращается к очереди и, получив оттуда следующее задание, заставляет головку уходить в другую часть диска. Но приложению, которое получило предыдущий результат, захотелось опять из старого места считать данные. Тогда оно вынуждено еще раз отстоять в очереди и сгонять на старое место головку. Получается, что головка дважды ходила в одно и то же место, хотя можно было бы все считать оттуда сразу. Но приложение не может выдать все задачи сразу, ее последующие задачи зависят от результата предыдущих.
Для этого взяли старый Deadine I/O и прибавили к нему механизм упреждения anticipatory.
Работает так: головка получила задачу и ушла в нужную часть диска. Прочитала оттуда данные и вернула приложению. Теперь она замирает на 6 миллисекунд и ждет, не понадобится ли приложению считать данные с этого участка еще раз. Если понадобилось, то этот запрос пропускается вперед очереди и выполняется, после чего снова 6-ти миллисекундное ожидание. Ну если нет, так нет - возвращается к обработке отсортированной очереди.
CFQ I/O Scheduler
Этот скедулер уже отличается кардинально тем, что уже начинает оперировать не на уровне слепопришедших запросов, а знает от кого они пришли. На каждое приложение он выстраивает свою очередь и кружится между очередями по кругу как барабан Якубовича. Переход к следующей очереди осуществляется либо по истечению таймаута либо если очередь опустела. Во втором случае делается 10-ти миллисекундная задержка на случай пополнения очереди.
В таком случае уже не реализовать механизм защиты от writes-starves-reads, так как очереди принадлежат разным приложениям, а потому операции чтения имеют приоритет над операциями записи для восполнения этого пробела.
BFQ I/O Scheduler
Основанный на CFQ, этот скедулер отличается тем, что выбирает чью очередь обслуживать не на основе временных отрезков, а на основе количества уже прочитанных запросами этой очереди секторов. А это уже открывает новые горизонты - стало возможно регулировать пропускную способность для каждого процесса. Кому-то дать за один обход считать с очереди 100 секторов, а кому-то 300. Например можно для процессов аудио- и видео-потоков ограничивать объем считываемой информации.
К сожалению, это еще совсем свежий скедулер и потому не попал в апстрим ядро. Но зато он есть в Zen-Kernel. Доступен в Gentoo и Ubuntu.
Кроме перечисленных скедулеров есть контроллеры приоритетов, которые можно ставить поверх любого скедулера. Такие контроллеры уже умеют раздавать тикеты на обработку скедулером на основе веса и прочих прелестей. В том числе они управляют и асинхронными очередями.
К сожалению, я не могу рассказать о них, дабы не потерять конкурентное преимущество над другими хостерами, но придет время - расскажу и о них.
Файловые системы, будучи чисто программной сущностью, оперируют своими логическими блоками. Как правило один логический блок файловой системы это целое число физических блоков диска.
Теперь о скедулерах. У скедулера есть две базовые задачи: слияние нескольких запросов в один единый и упорядочивание запросов.
Слияние. Например поступила задача обратиться к блокам 218, 372, 750. Следом поступила вторая задача, обратиться к блоку 501. Скедулер затолкает второй запрос в первый и сделает ряд: 218, 372, 750, 501. Считать придется столько же информации, но количество операций ввода-вывода сократится ровно вдвое.
Упорядочивание. Это основная и самая сложная задача скедулера. Самый простой вариант выглядит так: поступила задача считать блоки 200, 539, 107 и 688. Скедулер переставляет местами блоки: 107, 200, 539, 688. Делается это для того, чтобы не гонять головку по всему блину туда-сюда, потому что это лишний расход времени, а пройтись ровненько от начала до конца, тем самым увеличив производительность.
Так как операции чтения выполняются в синхронном режиме (каждая последующая ждет пока не закончится предыдущая), то в случае задержки операции, тормозится вся очередь. Кроме того, очевидно, что операции чтения должны предоставить актуальные данные, а значит в случае, если страничный кэш их не дает, то запрос блокируется и ждет. Тогда вся последующая очередь опять же задерживается на еще дольший период. Это называется read latency.
Операции записи наоборот могут быть произведены всей кучей. Для всех запросов одновременно начинается операция ввода-вывода и это делает большой скачок нагрузки на диск. Получается, что операции чтения, при такой агрессии операций записи, вообще в состоянии обиженных вниманием и начинается перекос. Этот феномен называется writes-starving-reads (запись-обделяет-чтение).
В случае, если скедулер начинает слепо вставлять новые запросы по порядку блоков в общий ряд, то значит, что все запросы недалеко от центра шпинделя будут выполняться быстро, а те, что обращаются к краям "блина" очень не скоро. Это также сильно бьет по производительности. Таким образом одна из основных задач скедулера - не допустить обделения крайних блоков вниманием.
Для этого придумали алгоритм Linus Elevator. Я нашел в двух разных источниках два метода его работы. Какой из них на самом деле, я не знаю, потому опишу оба:
1) Скедулер все же сортирует запросы по месторасположению блоков, но если появляются запросы, которые подозрительно долго стоят в очереди, то очередь начинает сливаться без сортировки. Как толькоо таких запросов не будет, то он опять начинает сортировать.
2) Скедулер выстраивает запросы как элеватор - вставлено будет все, но обработано только то, в какую сторону движется этот элеватор. Например он прошел блоки 17, 190, 404. В этот момент вставляется блок 512. Он его так же проходит. Затем вставляется блок 391. Элеватор не возврашается к нему назад, он продолжает намеченные блоки только по возрастанию. Дойдя до края, он возвращается назад к центру и уже тогда после какого-нибудь 439-го блока будет считан 391.
Время ожидания операции чтения/записи у этого алгоритма регулируется утилитой elvtune.
Теперь более подробно про каждый скедулер.
NCQ I/O Scheduler.
Единственный в списке аппаратный скедулер, встроенный в SATA-диски.
Проверить, поддерживает ли Ваш диск его, можно командой:
dmesg |grep NCQ
Noop I/O Scheduler.
Это самый простой скедулер. Не делает вообще ничего. Единственно его правило: FIFO (первый вошел - первый вышел). Запросы совсем не сортируются.
Используется только там, где нету проблемы беготни головки. Например SSD-диски, Flash-диски и так далее.
Deadline I/O Scheduler
Так же, как и стандартный скедулер обладает сортированной очередью, где следующий обслуживаемый запрос находится в ее голове. Но кроме нее у него есть еще две очереди, где запросы не сортированы и лежать в порядке FIFO, то есть по времени создания запроса. По одной очереди на чтение и на запись. У каждой из этих очередей есть своё время дедлайна. Через предложение объясню зачем.
Как только появляется новый запрос, он встает сразу в две очереди: в свою (в зависимости от того чтение он или запись) FIFO-очередь и в общую сортированную.
По началу элеватор идет по стандартной очереди, в которой запросы упорядочены по номеру запрашиваемого блока, но если в одной из FIFO-очередей появляется запрос старше, чем время дедлайна для данной очереди, то скедулер начинает разбирать эту очередь.
Таким образом решена, ну или сведена к минимуму, проблема writes-starves-reads.
Anticipatory I/O Scheduler
Например был обслужен некоторый запрос для конкретного приложения. Результат запроса отдан приложению, скедулер возвращается к очереди и, получив оттуда следующее задание, заставляет головку уходить в другую часть диска. Но приложению, которое получило предыдущий результат, захотелось опять из старого места считать данные. Тогда оно вынуждено еще раз отстоять в очереди и сгонять на старое место головку. Получается, что головка дважды ходила в одно и то же место, хотя можно было бы все считать оттуда сразу. Но приложение не может выдать все задачи сразу, ее последующие задачи зависят от результата предыдущих.
Для этого взяли старый Deadine I/O и прибавили к нему механизм упреждения anticipatory.
Работает так: головка получила задачу и ушла в нужную часть диска. Прочитала оттуда данные и вернула приложению. Теперь она замирает на 6 миллисекунд и ждет, не понадобится ли приложению считать данные с этого участка еще раз. Если понадобилось, то этот запрос пропускается вперед очереди и выполняется, после чего снова 6-ти миллисекундное ожидание. Ну если нет, так нет - возвращается к обработке отсортированной очереди.
CFQ I/O Scheduler
Этот скедулер уже отличается кардинально тем, что уже начинает оперировать не на уровне слепопришедших запросов, а знает от кого они пришли. На каждое приложение он выстраивает свою очередь и кружится между очередями по кругу как барабан Якубовича. Переход к следующей очереди осуществляется либо по истечению таймаута либо если очередь опустела. Во втором случае делается 10-ти миллисекундная задержка на случай пополнения очереди.
В таком случае уже не реализовать механизм защиты от writes-starves-reads, так как очереди принадлежат разным приложениям, а потому операции чтения имеют приоритет над операциями записи для восполнения этого пробела.
BFQ I/O Scheduler
Основанный на CFQ, этот скедулер отличается тем, что выбирает чью очередь обслуживать не на основе временных отрезков, а на основе количества уже прочитанных запросами этой очереди секторов. А это уже открывает новые горизонты - стало возможно регулировать пропускную способность для каждого процесса. Кому-то дать за один обход считать с очереди 100 секторов, а кому-то 300. Например можно для процессов аудио- и видео-потоков ограничивать объем считываемой информации.
К сожалению, это еще совсем свежий скедулер и потому не попал в апстрим ядро. Но зато он есть в Zen-Kernel. Доступен в Gentoo и Ubuntu.
Кроме перечисленных скедулеров есть контроллеры приоритетов, которые можно ставить поверх любого скедулера. Такие контроллеры уже умеют раздавать тикеты на обработку скедулером на основе веса и прочих прелестей. В том числе они управляют и асинхронными очередями.
К сожалению, я не могу рассказать о них, дабы не потерять конкурентное преимущество над другими хостерами, но придет время - расскажу и о них.
Комментариев нет:
Отправить комментарий