Основным контейнером для операций ввода-вывода в ядре является структура bio, которая определена в файле . Эта структура представляет активные операции блочного ввода-вывода в виде списка сегментов (segment). Сегмент — это участок буфера, который является непрерывным в физической памяти, т.е. отдельные буферы не обязательно должны быть непрерывными в физической памяти. Благодаря тому, что буфер может представляться в виде нескольких участков, структура bio даст возможность выполнять операции блочного ввода-вывода, даже если данные одного буфера хранятся в разных местах памяти. Ниже показана структура bio с комментариями, описывающими назначение каждого поля.

struct bio {

 sector_t            bi_sector; /* соответствующий сектор на диске */

 struct bio          *bi_next;         /* список запросов */

 struct block_device *bi_bdev;  /* соответствующее блочное устройство */

 unsigned long       bi_flags;         /* состояние и флаги команды */

 unsigned long       bi_rw;            /* чтение или запись? */

 unsigned short      bi_vcnt;          /* количество структур bio vec

                                          в массиве bi_io_vec */

 unsigned short      bi_idx;    /* текущий индекс в массиве bi_io_vec */

 unsigned short      bi_phys_segments; /* количество сегментов

                                          после объединения */

 unsigned short      bi_hw_segments;   /* количество сегментов после

                                          перестройки отображения */

 unsigned int        bi_size;          /* объем данных для ввода-вывода */

 unsigned int        bi_hw_front_size; /* размер первого

                                          объединяемого сегмента */

 unsigned int        bi_hw_front_size; /* размер последнего объединяемого

                                          сегмента */

 unsigned int        bi_max_vecs;      /* максимально возможное количество

                                          структур bio_vecs */

 struct bio_vec      *bi_io_vec;       /* массив структур bio_vec */

 bio_end_io_t        *bi_end_io;       /* метод завершения ввода-вывода */

 atomic_t            bi_cnb;           /* счетчик использования */

 void                *bi_private;      /* поле для информации создателя */

 bio_destructor_t    *bi_destructor;   /* деструктор */

};

Главное назначение структуры bio — это представление активной (выполняющейся) операции блочного ввода-вывода. В связи с этим большинство полей этой структуры являются служебными. Наиболее важные поля — это bi_io_vecs, bi_vcnt и bi_idx.

Поле bi_io_vecs указывает на начало массива структур bio_vec. Эти структуры используются в качестве списка отдельных сегментов в соответствующей операции блочного ввода-вывода. Каждый экземпляр структуры bio_vec представляет собой вектор следующего вида: <страница памяти, смещение, размер>, который описывает определенный сегмент, соответственно страницу памяти, где этот сегмент хранится, положение блока — смещение внутри страницы — и размер блока. Массив рассмотренных векторов описывает весь буфер полностью. Структура bio_vec определена в файле следующим образом.

struct bio_vec {

 /* указатель на страницу физической памяти, где находится этот буфер */

 struct page *bv_page;

 /* размер буфера в байтах */

 unsigned int bv_len;

 /* смещение в байтах внутри страницы памяти, где находится буфер */

 unsigned int bv_offset;

};

Для каждой операции блочного ввода-вывода создается массив из bi_vcnt элементов типа bio_vec, начало которого содержится в поле bi_io_vecs. В процессе выполнения операции блочного ввода-вывода поле bi_idx используется для указания на текущий элемент массива.

В общем, каждый запрос на выполнение блочного ввода-вывода представляется с помощью структуры bio. Каждый такой запрос состоит из одного или более блоков, которые хранятся в массиве структур bio_vec. Каждая из этих структур представляет собой вектор, который описывает положение в физической памяти каждого сегмента запроса. На первый сегмент для операции ввода-вывода указывает поле bi_io_vec. Каждый следующий сегмент следует сразу за предыдущим. Всего в массиве bi_vcnt сегментов. В процессе того, как уровень блочного ввода-вывода обрабатывает сегменты запроса, обновляется значение поля bi_idx, чтобы его значение соответствовало номеру текущего сегмента. На рис. 13.2 показана связь между структурами bio, bio_vec и page.

Рис. 13.2. Связь между структурами struct bio, struct bio_vec и struct page

Поле bi_idx указывает на текущую структуру bio_vec в массиве, что позволяет уровню блочного ввода-вывода поддерживать частично выполненные операции блочного ввода-вывода. Однако более важное использование состоит в том, что драйверы таких устройств, как RAID (Redundant Array of Inexpensive/Independent Disks, массив недорогих/независимых дисковых устройств с избыточностью — специальный способ использования жестких дисков, при котором один логический том может быть распределен но нескольким физическим дискам для увеличения надежности или производительности), могут одну структуру bio, которая изначально была адресована одному устройству, разбивать на несколько частей, которые предназначаются различным дискам RAID массива. Все, что необходимо сделать драйверу RAID, это создать необходимое количество копий структуры bio, которая предназначалась одному устройству, и изменить для каждой копии значение поля bi_idx, чтобы оно указывало на ту часть массива, откуда каждый диск должен начать свою операцию ввода-вывода.

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

void bio_get(struct bio *bio);

void bio_put(struct bio *bio);

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

И наконец, поле bio_private — это поле данных создателя (владельца) структуры. Как правило, это поле необходимо считывать или записывать только тому, кто создал данный экземпляр структуры bio.

 

Сравнение старой и новой реализаций

Между заголовками буферов и новой структурой bio существуют важные отличия. Структура bio представляет операцию ввода-вывода, которая может включать одну или больше страниц в физической памяти. С другой стороны, заголовок буфера связан с одним дисковым блоком, который занимает не более одной страницы памяти. Поэтому использование заголовков буферов приводит к ненужному делению запроса ввода-вывода на части, размером в один блок, только для того, чтобы их потом снова объединить. Работа со структурами bio выполняется быстрее, эта структура может описывать несмежные блоки и не требует без необходимости разбивать операции ввода-вывода на части.

Переход от структуры struct buffer_head к структурам struct bio позволяет получить также и другие преимущества.

• Структура bio может легко представлять верхнюю память (см. главу 11), так как структура struct bio работает только со страницами физической памяти, а не с указателями.

• Структура bio может представлять как обычные страничные операции ввода- вывода, так и операции непосредственного (direct) ввода-вывода (т.е. те, которые не проходят через страничный кэш; страничный кэш обсуждается в главе 15).

• Структура bio позволяет легко выполнять операции блочного ввода-вывода типа распределения-аккумуляции (scatter-gather), в которых данные находятся в нескольких страницах физической памяти.

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

Тем не менее заголовки буферов все еще необходимы для функций, которые выполняют отображение дисковых блоков на страницы физической памяти. Структура bio не содержит никакой информации о состоянии буфера, это просто массив векторов, которые описывают один или более сегментов данных одной операции блочного ввода-вывода, плюс соответствующая дополнительная информация. Структура buffer_head необходима для хранения информации о буферах. Применение двух отдельных структур позволяет сделать размер обеих этих структур минимальным.

 

Для блочных устройств поддерживаются очереди запросов (request queue), в которых хранятся ожидающие запросы на выполнение операций блочного ввода-вывода. Очередь запросов представляется с помощью структуры request_queue, которая определена в файле . Очередь запросов содержит двухсвязный список запросов и соответствующую управляющую информацию. Запросы добавляются в очередь кодом ядра более высокого уровня, таким как файловые системы. Пока очередь запросов не пуста, драйвер блочного устройства, связанный с очередью, извлекает запросы из головы очереди и отправляет их на соответствующее блочное устройство. Каждый элемент списка запросов очереди— это один запрос, представленный с помощью структуры struct request.

 

Запросы

Отдельные запросы представляются с помощью структуры struct request, которая тоже определена в файле . Каждый запрос может состоять из более чем одной структуры bio, потому что один запрос может содержать обращение к нескольким смежным дисковым блокам. Обратите внимание, что хотя блоки на диске и должны быть смежными, данные этих блоков не обязательно должны быть смежными в физической памяти — каждая структура bio может содержать несколько сегментов (вспомните, сегменты — это непрерывные участки памяти, в которых хранятся данные блока), а запрос может состоять из нескольких структур bio.

 

Простая отправка запросов на устройство ввода-вывода в том же порядке, в котором эти запросы направляет ядро, приводит к очень плохой производительности. Одна из наиболее медленных операций, которые вообще могут быть в компьютере,— это поиск по жесткому диску. Операция поиска — это позиционирование головки жесткого диска на определенный блок, которое может запять много миллисекунд. Минимизация количества операций поиска чрезвычайно критична для производительности всей системы.

Поэтому ядро не отправляет все запросы на выполнение операций блочного ввода-вывода жесткому диску в том же порядке, в котором они были получены, или сразу же, как только они были получены. Вместо этого, оно выполняет так называемые операции слияния (объединения, merging) и сортировка (sorting), которые позволяют значительно увеличить производительность всей системы. Подсистема ядра, которая выполняет эти операции называется планировщиком ввода-вывода (I/O scheduler).

Планировщик ввода-вывода разделяет дисковые ресурсы между ожидающими в очереди запросами ввода-вывода. Это выполняется путем объединения и сортировки запросов ввода-вывода, которые находятся в очереди. Планировщик ввода-вывода не нужно путать с планировщиком выполнения процессов (см. главу 4, "Планирование выполнения процессов"), который делит ресурсы процессора между процессами системы. Эти две подсистемы похожи, но это — не одно и то же. Как планировщик выполнения процессов, так и планировщик ввода-вывода выполняют виртуализацию ресурсов для нескольких объектов. В случае планировщика процессов выполняется виртуализация процессора, который совместно используется процессами системы. Это обеспечивает иллюзию того, что процессы выполняются одновременно, и является основой многозадачных операционных систем с разделением времени, таких как Unix. С другой стороны, планировщики ввода-вывода выполняют виртуализацию блочных устройств для ожидающих выполнения запросов блочного ввода-вывода. Это делается для минимизации количества операций поиска по жесткому диску и для получения оптимальной производительности дисковых операций.

 

Задачи планировщика ввода-вывода

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

Планировщики ввода-вывода выполняют две основные задачи: объединение и сортировку. Объединение — это слияние нескольких запросов в один. В качестве примера рассмотрим запрос, который поставлен в очередь кодом файловой системы, например чтобы прочитать порцию данных из файла (конечно, на данном этапе все уже выполняется на уровне секторов и блоков, а не на уровне файлов). Если в очереди уже есть запрос на чтение из соседнего сектора диска (например, другой участок того же файла), то два запроса могут быть объединены в один запрос для работы с одним или несколькими, расположенными рядом, секторами диска. Путем слияния запросов планировщик ввода-вывода уменьшает затраты ресурсов, связанные с обработкой нескольких запросов, до уровня необходимого на обработку одного запроса. Наиболее важно здесь то, что диск выполняет всего одну команду и обслуживание нескольких запросов может быть выполнено вообще без применения поиска. Следовательно, слияние запросов уменьшает накладные расходы и минимизирует количество операций поиска.

Теперь предположим, что наш запрос на чтение помещается в очередь запросов, но там нет других запросов на чтение соседних секторов. Поэтому нет возможности выполнить объединение этого запроса с другими запросами, находящимися в очереди. Можно просто поместить запрос в конец очереди. Но что если в очереди есть запросы к близкорасположенным секторам диска? Не лучше ли будет поместить новый запрос в очередь где-то рядом с запросами к физически близко расположенным секторам диска. На самом деле планировщики ввода-вывода именно так и делают, Вся очередь запросов поддерживается в отсортированном состоянии по секторам, чтобы последовательность запросов в очереди (насколько это возможно) соответствовала линейному движению по секторам жесткого диска. Цель состоит в том, чтобы не только уменьшить количество перемещений в каждом индивидуальном случае, но и минимизировать общее количество операций поиска таким образом, чтобы головка двигалась по прямой линии. Это аналогично алгоритму, который используется в лифте (elevator) — лифт не прыгает между этажами. Вместо этого он плавно пытается двигаться в одном направлении. Когда лифт доходит до последнего этажа в одном направлении, он начинает двигаться в другую сторону. Из-за такой аналогии планировщик ввода-вывода (а иногда только алгоритм сортировки) называют лифтовым планировщиком (алгоритмом лифта, elevator).

 

Рассмотрим некоторые планировщики ввода-вывода, применяемые в реальной жизни. Первый планировщик ввода-вывода, который мы рассмотрим, называется Linus Elevator (лифтовой алгоритм Линуса). Это не опечатка, действительно существует лифтовой планировщик, разработанный Линусом Торвальдсом и названный в его честь! Это основной планировщик ввода-вывода в ядре 2.4. В ядре 2.6 его заменили другими планировщиками, которые мы ниже рассмотрим. Однако поскольку этот алгоритм значительно проще новых и в то же время позволяет выполнять почти те же функции, то он заслуживает внимания.

Лифтовой алгоритм Линуса позволяет выполнять как объединение, так и сортировку запросов. Когда запрос добавляется в очередь, вначале он сравнивается со всеми ожидающими запросами, чтобы обнаружить все возможные кандидаты на объединение. Алгоритм Линуса выполняет два типа объединения: добавление в начало запроса (front merging) и добавление в конец запроса (back merging). Тип объединения соответствует тому, с какой стороны найдено соседство. Если новый запрос следует перед существующим, то выполняется вставка в начало запроса. Если новый запрос следует сразу за существующим — добавление выполняется в конец очереди. В связи с тем, что секторы, в которых хранится файл, расположены по мере увеличения номера сектора и операции ввода-вывода чаще всего выполняются от начала файла до конца, а не наоборот, то при обычной работе вставка в начало запроса встречается значительно реже, чем вставка в конец. Тем не менее алгоритм Линуса проверяет и выполняет оба типа объединения.

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

Итак, когда запрос добавляется в очередь возможны четыре типа действий. Вот эти действия в необходимой последовательности.

• Если запрос к соседнему сектору находится в очереди, то существующий запрос и новый объединяются в один.

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

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

• И наконец, если такая позиция не найдена, то запрос помещается в конец очереди.

 

Планировщик ввода-вывода с лимитом по времени

Планировщик ввода-вывода с лимитом по времени (Deadline I/O scheduler, deadline-планировщик ввода-вывода) разработан с целью предотвращения задержек обслуживания, которые могут возникать для алгоритма Линуса. Если задаться целью только минимизировать количество операций поиска, то при большом количестве операций ввода-вывода из одной области диска могут возникать задержки обслуживания для операций с другими областями диска, причем на неопределенное время. Более того, поток запросов к одной и той же области диска может привести к тому, что запросы к области диска, которая находится далеко от первой, никогда не будут обработаны. Такой алгоритм не может обеспечить равнодоступность ресурсов.

Хуже того, общая проблема задержки обслуживания запросов приводит к частной проблеме задержки обслуживания чтения при обслуживании записи (writes-starving-reads). Обычно операции записи могут быть отправлены на обработку диском в любой момент, когда ядру это необходимо, причем это выполняется полностью асинхронно по отношению к пользовательской программе, которая сгенерировала запрос записи. Обработка же операций чтения достаточно сильно отличается. Обычно, когда пользовательское приложение отправляет запрос на чтение, это приложение блокируется до тех пор, пока запрос не будет выполнен, т.е. запросы чтения возникают синхронно по отношению к приложению, которое эти запросы генерирует. В связи с этим время реакции системы, в основном, не зависит от латентности записи (времени задержки, которое необходимо на выполнение запроса записи), а задержки чтения (время, которое необходимо на выполнение операции чтения) очень важно минимизировать. Латентность записи мало влияет на производительность пользовательских программ, но эти программы должны "с дрожащими руками" ждать завершение каждого запроса чтения. Следовательно, задержки чтения очень важны для производительности системы.

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

Следует обратить внимание, что уменьшение времени задержки в обслуживании может быть выполнено только за счет уменьшения общего быстродействия системы. Даже для алгоритма Линуса такой компромисс существует, хотя и в более мягкой форме. Алгоритм Линуса мог бы обеспечить и большую общую пропускную способность (путем уменьшения количества операций поиска), если бы запросы всегда помещались в очередь в соответствии с номерами секторов и не выполнялась проверка на наличие старых запросов и вставка в конец очереди. Хотя минимизация количества операций поиска и важна, тем не менее неопределенное время задержки тоже не очень хорошая вещь. Поэтому deadline-планировщик и выполняет много работы для уменьшения задержек в обслуживании. Достаточно сложно одновременно обеспечить равнодоступность и максимизировать общую пропускную способность.

В планировщике ввода-вывода, с лимитом по времени с запросом связано предельное время ожидания (expiration time). По умолчанию этот момент времени равен 500 миллисекунд в будущем для запросов чтения и 5 секунд в будущем для запросов записи. Планировщик ввода-вывода с лимитом по времени работает аналогично планировщику Линуса — он также поддерживает очередь запросов в отсортированном состоянии в соответствии с физическим расположением сектора на диске. Эта очередь называется отсортированной (sorted queue). Когда запрос помещается в отсортированную очередь, то deadline-планировщик ввода-вывода выполняет объединение и вставку запросов так же, как это делается в лифтовом алгоритме Линуса. Кроме того, планировщик с лимитом по времени помещает каждый запрос и во вторую очередь, в зависимости от типа запроса. Запросы чтения помещаются в специальную очередь FIFO запросов чтения, а запросы записи— в очередь FIFO запросов записи. В то время как обычная очередь отсортирована по номеру сектора на диске, две очереди FIFO (first-in first-out— первым поступил, первым обслужен) сортируются по времени поступления запроса, так как новые запросы всегда добавляются в конец очереди. При нормальной работе deadline-планировщик ввода-вывода получает запросы из головы отсортированной очереди и помещает их в очередь диспетчеризации. Очередь диспетчеризации отправляет запросы жесткому диску. Это приводит к минимизации количества операций поиска.

Если же для запроса, который находится в голове FIFO-очереди записи или FIFO-очереди чтения, истекает период ожидания (т.е. текущий момент времени становится большим, чем момент времени, когда истекает период ожидания, связанный с запросом), то deadline-планировщик начинает обрабатывать запросы из соответствующей очереди FIFO. Таким образом планировщик с лимитом по времени пытается гарантировать, что запросы не будут ожидать дольше максимального периода ожидания (рис. 13.3).

Рис. 13.3. Три очереди планировщика ввода-вывода с лимитом по времени

Следует заметить, что deadline-плаиировщик ввода-вывода не дает строгой гарантии времени задержки запроса. Однако он, в общем, позволяет отправлять на обработку запросы до или вскоре после того, как истек их период ожидания. Это позволяет предотвратить ситуацию недостатка обслуживания запросов. Так как для запросов чтения максимальное время ожидания значительно больше, чем для запросов записи, то планировщик с лимитом по времени также позволяет гарантировать, что обслуживание запросов записи не приведет к недостатку обслуживания запросов чтения. Больший приоритет запросов чтения позволяет минимизировать время задержки при операциях чтения.

Код планировщика ввода-вывода с лимитом по времени находится в файле drivers/block/deadline-iosched.с.

 

Прогнозирующий планировщик ввода-вывода

Хотя планировщик с лимитом по времени ввода-вывода и выполняет работу по минимизации задержек чтения, это делается ценой уменьшения глобального быстродействия. Рассмотрим систему с большой активностью записи. Каждый раз, когда приходит запрос на чтение, планировщик сразу же начинает его выполнять. Это приводит к тому, что сразу же запускается операция поиска того места на диске, где будет выполнено чтение и сразу после выполнения чтения снова осуществляется поиск того места, где будет выполнена запись, и так повторяется при каждом запросе чтения. Большой приоритет запросов чтения вещь хорошая, но две операции поиска на каждый запрос чтения (перемещение в точку чтения и обратно в точку записи) очень плохо сказываются на общей дисковой производительности. Цель прогнозирующего планировщика ввода-вывода (anticipatory I/O scheduler) — обеспечение хороших характеристик по задержкам чтения и в то же время обеспечение отличной общей производительности.

Прогнозирующий планировщик построен на базе планировщика ввода-вывода с лимитом но времени. Поэтому он не особо отличается. В прогнозирующем планировщике реализованы три очереди (плюс очередь диспетчеризации) и обработка времени ожидания для каждого запроса, так же как и В случае deadline-планировщика. Главное отличие состоит в наличии дополнительного эвристического прогнозирования (anticipation heuristic).

Прогнозирующий планировщик ввода-вывода пытается минимизировать "шторм операций поиска", который следует за каждым запросом чтения во время выполнения других дисковых операций. Когда поступает запрос на чтение, он обрабатывается в рамках своего времени ожидания как обычно. После того как запрос отправлен жесткому диску, прогнозирующий планировщик сразу не возвращается к выполнению предыдущих запросов и не запускает операцию поиска сразу же. Он абсолютно ничего не делает в течение нескольких миллисекунд (значение этого периода времени можно настраивать, а по умолчанию оно равно 6 миллисекунд). Существует большой шанс, что за эти несколько миллисекунд приложение отправит еще один запрос на чтение. Все запросы к соседним секторам диска выполняются немедленно. После .того как время ожидания истекает, прогнозирующий планировщик возвращается к выполнению ранее оставленных запросов и выполняет поиск соответствующего места на диске.

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

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

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

Код прогнозирующего планировщика находится в файле drivers/block/as-iosched.c дерева исходных кодов ядра.

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

 

Планировщик ввода-вывода с полностью равноправными очередями

Планировщик ввода-вывода с полностью равноправными очередями (Complete Fair Queuing, CFQ) был разработан для определенного типа нагрузок на систему, по на практике он позволяет получить хорошую производительность для широкого диапазона типов нагрузки. Он фундаментальным образом отличается от всех ранее рассмотренных планировщиков ввода-вывода.

Планировщик CFQ распределяет все приходящие запросы ввода-вывода по определенным очередям на основании того, какой процесс прислал этот запрос. Например, запросы от процесса foo идут в очередь foo, запросы от процесса bar — в очередь bar. В пределах каждой очереди запросы объединяются со смежными и сортируются. Таким образом очереди поддерживаются в отсортированном состоянии, так же как и в случае других планировщиков ввода-вывода. Отличие планировщика CFQ состоит в том, что он поддерживает отдельную очередь для каждого процесса, который выполняет операции ввода-вывода.

После этого планировщик CFQ выполняет запросы из разных очередей по круговому алгоритму, выполняя конфигурируемое количество запросов (по умолчанию 4) из каждой очереди, перед тем как перейти к следующей. Это позволяет получить равномерное распределение пропускной способности диска для каждого процесса в системе. Предполагаемое использование такого планировщика — мультимедийные приложения, для которых он позволяет гарантировать, что, например, аудио-проигрыватель всегда будет успевать вовремя заполнять аудиобуферы с диска. Тем не менее планировщик CFQ на практике хорошо работает для многих сценариев загруженности системы.

Код CFQ планировщика находится в файле drivers/block/cfq-iosched.с. Этот планировщик рекомендуется для офисных компьютеров, хотя хорошо работает практически для всех типов нагрузок, за исключением, может быть, уж очень экстремальных типов загруженности.

 

Планировщик ввода-вывода noop

Четвертый, и последний, тип планировщика ввода-вывода — это планировщик noop (no operation, с отсутствием операций). Он назван так потому, что практически ничего не делает. Этот планировщик не выполняет никакой сортировки или других операций для предотвращения поиска по устройству. Ему нет необходимости выполнять ничего, включая алгоритмы, которые минимизируют задержки и были рассмотрены для предыдущих планировщиков.

Планировщик ввода-вывода noop выполняет только объединение приходящих запросов со смежными, которые находятся в очереди. Кроме этого, больше никаких функций у данного планировщика нет. Он просто обслуживает очередь запросов, которые передаются драйверу блочного устройства, в режиме FIFO.

Планировщик noop не является полностью бесполезным. В том, что он ничего не делает, есть большой смысл. Он рассчитан на блочные устройства, которые позволяют выполнять истинно произвольный доступ, такие как платы флеш-памяти. Если для блочного устройства нет накладных затрат, связанных с поиском по устройству, то нет и необходимости выполнять сортировку и вставку вновь приходящих запросов, и планировщик noop — идеальный вариант.

Код планировщика noop находится в файле drivers/block/noop-iosched.с. Он предназначен только для устройств с произвольным доступом.

 

Выбор планировщика ввода-вывода

В ядрах серии 2.6 есть четыре планировщика ввода-вывода. Каждый из этих планировщиков может быть активизирован. По умолчанию все блочные устройства используют прогнозирующий планировщик ввода-вывода. Планировщик можно изменить, указав параметр ядра elevator=<плaниpoвщик> в командной строке при загрузке системы, где <планировщик> — это один из поддерживаемых типов планировщика, которые показаны в табл. 13.2.

Таблица 13.2. Возможные значения параметра elevator

Например, указание параметра elevator=cfq в командной строке ядра при загрузке системы означает, что для всех блочных устройств будет использоваться планировщик с полностью равноправными очередями.