Главная » Ядро Linux » Лифтовой алгоритм Линуса – ЧАСТЬ 2

0

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

Очередь FIFO запросов чтения

Очередь FIFO запросов записи

Отсортированная очередь

Очередь диспетчеризации

Диск

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

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

4    Для  deadline-планировщика  операция  вставки в  начало   запроса выполняется  опционально.  Обычно невыполнение вставки в начало запроса не  приводит к  проблемам, так  как  в  большинстве случаев количество запросов, которы е  могут  быть  добавлены в  начало, очен ь  незначительно.

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

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

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

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

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

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

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

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

Уровень блочного ввода-вывода

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

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

as-iosched. с  дерева   исходных кодов   ядра.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Значение                                        Тип планировщика

as cfq  deadline noop

Прогнозирующий

С полностью  равноправными очередями

С лимитом  по времени

С отсутствием  операций  (nоор)

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

Резюме

В этой главе были  рассмотрены основы работы  устройств блочного ввода-вывода, а также  структуры данных, используемые для  работы  уровня  ввода-вывода блоками: структура  bio , которая представляет выполняемую операцию ввода-вывода; структура  buffer_head , которая представляет отображение блоков  на страницы памяти; структура  request , которая представляет собой  отдельный запрос ввода-вывода. После  рассмотрения запросов ввода-вывода был описан их короткий, но важный путь, кульминацией которого является прохождение через  планировщик ввода-вывода. Были рассмотрены дилеммы, возникающие при планировании операций ввода-вывода, и четыре  типа планировщика, которые на данный момент существуют в ядре  Linux, а также  планировщик ввода  вывода  из  ядра  2.4 — лифтовой алгоритм Линуса.

Далее мы рассмотрим адресное пространство процесса.

Адресное пространство процесса

главе  11,  "Управление  памятью",  было  рассказано о  том, как  ядро  управляет физической намятью. В дополнение к тому, что  ядро  должно управлять своей памятью, оно  также  должно, управлять и  адресным пространством процессов— тем, как  память видится для  каждого процесса в системе. Операционная система Linux — это  операционная  система с  виртуальной памятью  (virtual  memory operating system), т.е.  для  всех  процессов выполняется  виртуализация  ресурсов памяти. Для  каждого процесса создается иллюзия того, что  он  один  использует всю  физическую память в системе.  Еще  более  важно, что  адресное пространство процессов  может  быть  даже значительно больше объема  физической памяти. В этой  главе  рассказывается о том,

как  ядро  управляет адресным пространством  процесса.

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

32или  64-битовое адресное пространство. Термин  "плоское" обозначает, что  адресное  пространство  состоит из  одного   диапазона адресов   (например,  32-разрядное адресное пространство занимает диапазон  адресов   от  0 до  429496729).   Некоторые операционные  системы предоставляют сегментированное адресное пространство — адресное пространство состоит больше чем  из  одного  диапазона адресов, т.е. состоит из  сегментов. Современные  операционные  системы обычно предоставляют плоское адресное пространство. Размер адресного пространства зависит от аппаратной  платформы. Обычно для  каждого процесса существует свое  адресное пространство.  Адрес  памяти в адресном пространстве одного  процесса не  имеет  никакого отношения к такому  же  адресу  памяти в адресном пространстве другого  процесса. Тем не  менее  несколько процессов могут  совместно использовать одно  общее  адресное пространство. Такие процессы называются потоками.

Значение адреса  памяти — это  заданное значение из диапазона адресов  адресного пространства, как,  например, 41021f000.  Это  значение идентифицирует определенный  байт  в 32-битовом адресном пространстве. Важной частью  адресного пространства  являются интервалы адресов  памяти, к которым процесс имеет  право  доступа, как,  например,  08048000-0804с000. Такие интервалы разрешенных адресов   называются  областями  памяти  (memory  area).  С  помощью ядра  процесс может  динамически добавлять и  удалять  области памяти своего  адресного пространства.

Процесс имеет право доступа только к действительным областям памяти. Более того, на область памяти могут быть установлены права только для чтения или запрет на выполнение. Если процесс обращается к адресу памяти,  который не находится в  действительной области памяти,  или доступ к действительной области выполняется запрещенным  образом,  то ядро уничтожает процесс с ужасным сообщением "Segmentation Fault" (ошибка сегментации).

Области памяти могут содержать следующую нужную информацию.

• Отображение выполняемого кода из выполняемого файла в область  памяти процесса, которая называется сегментом кода  (text section).

Отображение инициализированных переменных из выполняемого файла в  область памяти процесса, которая называется сегментом данных (data section).

• Отображение страницы памяти, заполненной нулями, в область памяти  процесса, которая содержит неинициализированные глобальные  переменные и называется  сегментом bss1  (bss section). Нулевая страница памяти  (zero page, страница памяти, заполненная нулями) — это страница памяти,  которая полностью заполнена нулевыми значениями и используется,  например, для указанной выше цели.

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

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

• Все файлы, содержимое которых отображено в память.

• Все области совместно используемой памяти.

• Все анонимные отображения в память, как, например, связанные с  функцией malloc() 2   .

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

1    Термин  "BSS" сложился историческ и  и  является достаточн о  старым.  Он  означает block    started by     symbol (блок,     начинающийся  с       символа). Неинициализированны е  переменны е  в  выполняемом файле не хранятся , поскольку с ним и не связано никакого значения . Тем не менее стандарт язык а С требует, чтобы неинициализированны м переменны м присваивалось  определенно е значение по умолчанию  (обычн о все заполняетс я нулями). Поэтому  ядро загружает  переменны е (без их значений) из выполняемого файла в память и отображает в эту память нулевую  страницу, тем самым переменным  присваивается  нулевое значение без необходимости зря тратит ь место в объектном файле на ненужную инициализацию.

2   В более новых  версиях  библиотеки  giibc фушщия  malloc( )   реализована  через системный вызов

ттар(),  а  не  через  вызов  brk() .

Источник: Лав,  Роберт. Разработка ядра  Linux, 2-е  издание. : Пер.  с англ.  — М.  : ООО  «И.Д.  Вильяме» 2006. — 448 с. : ил. — Парал. тит. англ.

По теме:

  • Комментарии