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

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

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

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

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

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

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

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

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

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

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

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг

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

Из книги Fedora 8 Руководство пользователя автора Колисниченко Денис Николаевич

7.2.2.3. Планировщик ввода-вывода В ядре 2.6 появилась возможность самостоятельно выбирать планировщик ввода-вывода. Всего используется четыре плани-ровщика.• noop - самый простой планировщик ввода-вывода, практически ничего не умеет, создавался в расчете на использование


5.4.1. Потоки ввода-вывода

Из книги Linux для пользователя автора Костромин Виктор Алексеевич

5.4.1. Потоки ввода-вывода Когда программа запускается на выполнение, в ее распоряжение предоставляются три потока (или канала): • стандартный ввод (standard input или stdin). По этому каналу данные передаются программе; • стандартный вывод (standard output или stdout). По этому каналу


5.2. Перенаправление ввода/вывода

Из книги Linux-сервер своими руками автора Колисниченко Денис Николаевич

5.2. Перенаправление ввода/вывода Практически все операционные системы обладают механизмом перенаправления ввода/вывода, и Linux не является исключением из этого правила. Обычно программы вводят текстовые данные с консоли (терминала) и выводят данные на консоль. При вводе


19.7.2. Перенаправление ввода/вывода

Из книги Основы AS/400 автора Солтис Фрэнк

19.7.2. Перенаправление ввода/вывода Перенаправление ввода/вывода уже рассматривалось в гл. 5, поэтому я лишь напомню общий формат команд:команда > (>>) файлсписок > (>>) файлКак вы уже знаете, при использовании одного знака больше файл, в который переназначен вывод,


Система ввода-вывода

Из книги Linux: Полное руководство автора Колисниченко Денис Николаевич

Система ввода-вывода Ввод-вывод — это Родни Дэнжерфилд[ 76 ] (Rodney Dangerfield) вычислительных систем: на него никто не обращает внимания. Всеобщий любимчик — процессор, а подсистема ввода-вывода рядом с ним — падчерица. Вот пример: когда надо охарактеризовать производительность


Операции ввода-вывода в AS/400

Из книги Операционная система UNIX автора Робачевский Андрей М.

Операции ввода-вывода в AS/400 Теперь от аппаратной архитектуры ввода-вывода AS/400 перейдем к совместной работе OS/400, SLIC и аппаратуры при выполнении операции ввода-вывода для прикладной программы. Сначала рассмотрим объекты, поддерживающие ввод-вывод, затем — многоуровневую


Компоненты ввода-вывода

Из книги Разработка ядра Linux автора Лав Роберт

Компоненты ввода-вывода 4 Денис! Эту сноску — на поля! Таблица по старому изданию, сравнить с новым. Для верстальщика: по-моему, стоит убрать рамку — будет красивееТаблица 10.1. Язык ввода-вывода AMQ Очередь свободных сообщений BCT Таблица управления шиной BCU Устройство


3.4.6. Потоки ввода-вывода

Из книги UNIX — универсальная среда программирования автора Пайк Роб

3.4.6. Потоки ввода-вывода Как я уже сказал, каждому процессу сопоставлена таблица открытых им файлов. Три первых позиции в этой таблице заняты всегда: каждый процесс открывает потоки (помните, что в UNIX файл — это и есть поток данных?) для ввода и вывода данных, а также вывода


Подсистема ввода/вывода

Из книги Конец холивара. Pascal vs C автора Кривцов М. А.

Подсистема ввода/вывода Подсистема ввода/вывода выполняет запросы файловой подсистемы и подсистемы управления процессами для доступа к периферийным устройствам (дискам, магнитным лентам, терминалам и т.д.). Она обеспечивает необходимую буферизацию данных и


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

Из книги Описание языка PascalABC.NET автора Коллектив РуБоард

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


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

Из книги автора

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


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

Из книги автора

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


Процедуры ввода и вывода

Из книги автора

Процедуры ввода и вывода Для ввода исходных данных применяются процедуры READ и READLN. После выполнения процедуры READ значение следующего данного читается из этой же строки, а при выполнении процедуры READLN – с новой строки.READ – читатьНапример: READ (X);READLN – читать с новой


Процедуры ввода и вывода

Из книги автора

Процедуры ввода и вывода Стандартная библиотека ввода-вывода языка C подключается с помощью директивы препроцессора #include <stdio. h>Форматный ввод данных пользователя с клавиатуры производится функцией scanf ().scanf (CONTROL, ARG1, ARG2, …);Данная функция осуществляет чтение


Подпрограммы ввода-вывода

Из книги автора

Подпрограммы ввода-вывода procedure Read(a,b,...); Вводит значения a,b,... с клавиатуры procedure Readln(a,b,...); Вводит значения a,b,... с клавиатуры и осуществляет переход на следующую строку function ReadInteger: integer; Возвращает значение типа integer, введенное с клавиатуры function ReadReal: