Хуже того, общая проблема задержки обслуживания запросов приводит к частной проблеме задержки обслуживания чтения при обслуживании записи (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.с.
Прогнозирующий планировщик ввода-вывода
Хотя планировщик с лимитом по времени ввода-вывода и выполняет работу по минимизации задержек чтения, это делается ценой уменьшения глобального быстродействия. Рассмотрим систему с большой активностью записи. Каждый раз, когда приходит запрос на чтение, планировщик сразу же начинает его выполнять. Это приводит к тому, что сразу же запускается операция поиска того места на диске, где будет выполнено чтение и сразу после выполнения чтения снова осуществляется поиск того места, где будет выполнена запись, и так повторяется при каждом запросе чтения. Большой приоритет запросов чтения вещь хорошая, но две операции поиска на каждый запрос чтения (перемещение в точку чтения и обратно в точку записи) очень плохо сказываются на общей дисковой производительности. Цель прогнозирующего планировщика ввода-вывода (anticipatory I/O scheduler) — обеспечение хороших характеристик по задержкам чтения и в то же время обеспечение отличной общей производительности.
Прогнозирующий планировщик построен на базе планировщика ввода-вывода с лимитом но времени. Поэтому он не особо отличается. В прогнозирующем планировщике реализованы три очереди (плюс очередь диспетчеризации) и обработка времени ожидания для каждого запроса, так же как и В случае deadline-планировщика. Главное отличие состоит в наличии дополнительного эвристического прогнозирования (anticipation heuristic).
Прогнозирующий планировщик ввода-вывода пытается минимизировать "шторм операций поиска", который следует за каждым запросом чтения во время выполнения других дисковых операций. Когда поступает запрос на чтение, он обрабатывается в рамках своего времени ожидания как обычно. После того как запрос отправлен жесткому диску, прогнозирующий планировщик сразу не возвращается к выполнению предыдущих запросов и не запускает операцию поиска сразу же. Он абсолютно ничего не делает в течение нескольких миллисекунд (значение этого периода времени можно настраивать, а по умолчанию оно равно 6 миллисекунд). Существует большой шанс, что за эти несколько миллисекунд приложение отправит еще один запрос на чтение. Все запросы к соседним секторам диска выполняются немедленно. После .того как время ожидания истекает, прогнозирующий планировщик возвращается к выполнению ранее оставленных запросов и выполняет поиск соответствующего места на диске.
77
Однако все же не желательно задерживать операции записи на неопределенное время. Запросы записи также должны немедленно отправляться на диск, но это не так критично, как в случае запросов чтения.
78
Для deadline-планировщика операция вставки в начало запроса выполняется опционально. Обычно невыполнение вставки в начало запроса не приводит к проблемам, так как в большинстве случаев количество запросов, которые могут быть добавлены в начало, очень незначительно.