Второе издание
 Скачать 3.09 Mb.
|
|
Квант времени Квант времени (timeslice 2 ) — это численное значение, которое характеризует, как долго может выполняться задание до того момента, пока оно не будет вытес- нено. Стратегия планирования должна устанавливать значение кванта времени, ис- пользуемое по умолчанию, что является непростой задачей. Слишком большое зна- чение кванта времени приведет к ухудшению интерактивной производительности системы— больше не будет впечатления, что процессы выполняются параллельно. Слишком малое значение кванта времени приведет к возрастанию накладных расхо- дов на переключение между процессами, так как больший процент системного вре- мени будет уходить на переключение с одного процесса с малым квантом времени на другой процесс с малым квантом времени. Более того, снова возникают противо- речивые требования к процессам, ограниченным скоростью ввода-вывода и скорос- тью процессора. Процессам, ограниченным скоростью ввода-вывода, не требуется продолжительный квант времени, в то время как для процессов, ограниченных ско- ростью процессора, настоятельно требуется продолжительный квант времени, на- пример, чтобы поддерживать кэши процессора в загруженном состоянии. На основе этих аргументов можно сделать вывод, что любое большое значение кванта времени приведет к ухудшению интерактивной производительности. При реализации большинства операционных систем такой вывод принимается близ- ко к сердцу и значение кванта времени, используемое по умолчанию, достаточно мало, например равно 20 мс. Однако в операционной системе Linux используется то преимущество, что процесс с самым высоким приоритетом всегда выполняется. Планировщик ядра Linux поднимает значение приоритета для интерактивных задач, что позволяет им выполняться более часто. Поэтому в ОС Linux планировщик ис- пользует достаточно большое значение кванта времени (рис 4.1). Более того, пла- нировщик ядра Linux динамически определяет значение кванта времени процессов в зависимости от их приоритетов. Это позволяет процессам с более высоким при- оритетом, которые считаются более важными, выполняться более часто и в течение большего периода времени. Использование динамического определения величины кванта времени и приоритетов позволяет обеспечить большую устойчивость и про- изводительность планировщика. Следует заметить, что процесс не обязательно должен использовать весь свой квант времени за один раз. Например, процесс, у которого квант времени равен 100 мс, не обязательно должен беспрерывно выполняться в течение 100 мс, рискуя потерять всю оставшуюся неистраченную часть кианта времени. Процесс может вы- полняться в течение пяти периодов длительностью по 20 мс каждый. 2 Вместо термина timeslice (квант времени) иногда также используется quantum (квант) или proces- sor slice. В ОС Linux применяется термин timeslice. Планирование выполнения процессов 69 Минимум По умолчанию Максимум 5мс 100 мс 800 мс Рис. 4.1. Вычисление кванта времени процесса Таким образом, интерактивные задачи также получают преимущество от исполь- зования продолжительного кванта времени, если даже вся продолжительность кван- та времени не будет использована сразу, гарантируется, что такие процессы будут готовы к выполнению по возможности долго. Когда истекает квант времени процесса, считается, что процесс потерял право выполняться. Процесс, у которого нет кванта времени, не имеет права выполнять- ся до того момента, пока все другие процессы не используют свой квант времени. Когда это случится, то у всех процессов будет значение оставшегося кванта времени, равное нулю. В этот момент значения квантов времени для всех процессов пересчи- тываются. В планировщике ОС Linux используется интересный алгоритм для обра- ботки ситуации, когда все процессы использовали свой квант времени. Этот алго- ритм будет рассмотрен далее. Вытеснение процесса Как уже упоминалось, операционная система Linux использует вытесняющую мно- гозадачность. Когда процесс переходит в состояние TASK_RUNNING, ядро проверя- ет значение приоритета этого процесса. Если это значение больше, чем приоритет процесса, который выполняется в данный момент, то активизируется планировщик, чтобы запустить новый процесс на выполнение (имеется в виду тот процесс, кото- рый только что стал готовым к выполнению). Дополнительно, когда квант времени процесса становится равным нулю, он вытесняется и планировщик готов к выбору нового процесса. Стратегия планирования в действии Рассмотрим систему с двумя готовыми к выполнению заданиями: программой для редактирования текстов и видеокодером. Программа для редактирования текстов ограничена скоростью ввода-вывода, потому что она тратит почти все свое время на ожидание ввода символов с клавиатуры пользователем (не имеет значение, с какой скоростью пользователь печатает, это не те скорости). Несмотря ни на что, при на- жатии клавиши пользователь хочет, чтобы текстовый редактор отреагировал сразу же. В противоположность этому видеокодер ограничен скоростью процессора. Если не считать, что он время от времени считывает необработанные данные с диска и записывает результирующий видеоформат на диск, то кодер большую часть времени выполняет программу видеокодека для обработки данных, что легко загружает про- цессор на все 100%. Для этой программы нет строгих ограничений на время выпол- 70 Глава 4 Меньший приоритет или Больший приоритет или нения: пользователю не важно, запустится она на полсекунды раньше или на полсе- кунды позже. Конечно, чем раньше она завершит работу, тем лучше. В такой системе планировщик установит для текстового редактора больший при- оритет и выделит более продолжительный квант времени, чем для видеокодера, так как текстовый редактор — интерактивная программа. Для текстового редактора про- должительности кванта времени хватит с избытком. Более того, поскольку тексто- вый редактор имеет больший приоритет, он может вытеснить процесс видеокодера при необходимости. Это гарантирует, что программа текстового редактора будет не- медленно реагировать на нажатия клавиш. Однако это не причинит никакого вреда и видеокодеру, так как программа текстового редактора работает с перерывами, и во время перерывов видеокодер может монопольно использовать систему. Все это позволяет оптимизировать производительность для обоих приложений. Алгоритм планирования В предыдущих разделах была рассмотрена в самых общих чертах теория работы планировщика процессов в операционной системе Linux. Теперь, когда мы разобра- лись с основами, можно более глубоко погрузиться в то, как именно работает плани- ровщик ОС Linux. Программный код планировщика операционной системы Linux содержится в файле k e r n e l / s c h e d . c . Алгоритм планирования и соответствующий программный код были существенно переработаны в те времена, когда началась разработка ядер серии 2.5. Следовательно, программный код планировщика является полностью но- вым и отличается от планировщиков предыдущих версий. Новый планировщик раз- рабатывался для того, чтобы удовлетворять указанным ниже требованиям. • Должен быть реализован полноценный О(1) -планировщик. Любой алгоритм, использованный в новом планировщике, должен завершать свою работу за по- стоянный период времени, независимо от числа выполняющихся процессов и других обстоятельств. • Должна обеспечиваться хорошая масштабируемость для SMP-систем. Каждый процессор должен иметь свои индивидуальные элементы блокировок и свою индивидуальную очередь выполнения. • Должна быть реализована улучшенная SMP-привязка (SMP affinity). Задания, для выполнения на каждом процессоре многопроцессорной системы, должны быть распределены правильным образом, и, по возможности, выполнение этих задач должно продолжаться на одном и том же процессоре. Осуществлять ми- грацию заданий с одного процессора на другой необходимо только для умень- шения дисбаланса между размерами очередей выполнения всех процессоров. • Должна быть обеспечена хорошая производительность для интерактивных приложений. Даже при значительной загрузке система должна иметь хорошую реакцию и немедленно планировать выполнение интерактивных задач. • Должна быть обеспечена равнодоступность ресурсов (fairness). Ни один про- цесс не должен ощущать нехватку квантов времени за допустимый период. Кроме того, ни один процесс не должен получить недопустимо большое значе- ние кванта времени. Планирование выполнения процессов 71 • Должна быть обеспечена оптимизация для наиболее распространенного слу- чая, когда число готовых к выполнению процессов равно 1-2, но в то же время должно обеспечиваться хорошее масштабирование и на случай большого числа процессоров, на которых выполняется большое число процессов. Новый планировщик позволяет удовлетворить всем этим требованиям. Очереди выполнения Основная структура данных планировщика — это очередь выполнения (runqueue). Очередь выполнения определена в файле kernel/sched.c 3 в виде структуры s t r u c t runqueue. Она представляет собой список готовых к выполнению процес- сов для данного процессора. Для каждого процессора определяется своя очередь выполнения. Каждый гото- вый к выполнению процесс может находиться в одной и только в одной очереди выполнения. Кроме этого, очередь выполнения содержит информацию, необходи- мую для планирования выполнения на данном процессоре. Следовательно, очередь выполнения — это действительно основная структура данных планировщика для каж- дого процессора. Рассмотрим нашу структуру, описание которой приведено ниже. Комментарии объясняют назначения каждого поля. struct runqueue { spinlock_t lock; /* спин-блокировка для защиты этой очереди выполнения*/ unsigned long nr_rinning; /* количество задач, готовых к выполнению */ unsigned long nr_switches; /* количество переключений контекста */ unsigned long expired timestamp; /* время последнего обмена массивами*/ unsigned long nr_uninterruptible; /* количество заданий в состоянии непрерываемого ожидания */ unsigned long long timestamp last tick; /* последняя метка времени планировщика */ struct task_struct *curr; /* текущее задание, выполняемое на данном процессоре */ struct task_struct *idle; /* холостая задача данного процессора */ struct mm_struct *prev_mm; /* поле mm_struct последнего выполняемого задания */ struct prio_array "active; /* указатель на активный массив приоритетов*/ struct prio_array 'expired; /* указатель на истекший массив приоритетов*/ struct prio_array arrays[2]; /* массивы приоритетов */ struct task_3truct *migration_thread; /* миграционный поток для данного процессора */ struct list_head migration_queue; /* миграционная очередь для данного процессора */ atomic_t nr_iowait; /* количество заданий, ожидающих на ввод-вывод */ }; 3 Может возникнуть вопрос: почему используется файл kernel/sched.с, а не заголовочный файл i n c l u d e / l i n u x / s c h e d . h ? Потому что желательно абстрагироваться от реализации кода планиров- щика и обеспечил, доступность для остального кода ядра только лишь некоторых интерфейсов. 72 Глава 4 Поскольку очередь выполнения — это основная структура данных планировщи- ка, существует группа макросов, которые используются для доступа к определенным очередям выполнения. Макрос cpu_rq (processor) возвращает указатель на оче- редь выполнения, связанную с процессором, имеющим заданный номер. Аналогично макрос this_rq () возвращает указатель на очередь, связанную с текущим процессо- ром. И наконец, макрос task_rq(task) возвращает указатель на очередь, в которой находится соответствующее задание. Перед тем как производить манипуляции с очередью выполнения, ее необходимо заблокировать (блокировки подробно рассматриваются в главе 8, "Введение в синхро- низацию выполнения кода ядра"). Так как очередь выполнения уникальна для каждо- го процессора, процессору редко необходимо блокировать очередь выполнения дру- гого процессора (однако, как будет показано далее, такое все же иногда случается). Блокировка очереди выполнения позволяет запретить внесение любых изменений в структуру данных очереди, пока процессор, удерживающий блокировку, выполня- ет операции чтения или записи полей этой структуры. Наиболее часто встречается ситуация, когда необходимо заблокировать очередь выполнения, в которой выпол- няется текущее задание. В этом случае используются функции tapk_rq_lock () и task_rq_unlock(), как показано ниже. struct runqueue *rq; unsigned long flags; rq = task_rq_lock(task, &flags); /* здесь можно производить манипуляции с очередью выполнения */ task_rq_unlock (rq, &flags); Альтернативными функциями выступают функция this_rq_lock (), которая по- зволяет заблокировать текущую очередь выполнения, и функция rq__unlock (struct runqueue *rq), позволяющая разблокировать указанную в аргументе очередь. Для предотвращения взаимных блокировок код, который захватывает блокиров- ки нескольких очередей, всегда должен захватывать блокировки в одном и том же порядке, а именно в порядке увеличения значения адреса памяти очереди (в главе 8, "Введение в синхронизацию выполнения кода ядра", приведено полное описание). Пример, как это осуществить, показан ниже. /* для того, чтобы заблокировать ... */ if (rql < rq2) ( spin_lock (s,rql->lock] ; spin_lock(Srq2->lock) ; } else ( spin_lock(Srq2->lock) ; spin_lock(&rql->lock) /* здесь можно манипулировать обеими очередями ... */ /• для того, чтобы разблокировать ... */ spin_unlock(brql->lock) ; spin_unlock(&rq2->lock); Планирование выполнения процессов 73 } С помощью функций double_rq_lock () и double_rq_unlock () указанные шаги можно выполнить автоматически. При этом получаем следующее. double_rq_lock(rql, rq2); /* здесь можно манипулировать обеими очередями ...*/ double_rq_unlock(rql, rq2) ; Рассмотрим небольшой пример, который показывает, почему важен порядок за- хвата блокировок. Вопрос взаимных блокировок обсуждается в главах 8, "Введение в синхронизацию выполнения кода ядра" и 9, "Средства синхронизации в ядре". Эта проблема касается не только очередей выполнения: вложенные блокировки должны всегда захватываться в одном и том же порядке. Спин-блокировки используются для предотвращения манипуляций с очередями выполнения несколькими задачами одно- временно. Принцип работы этих блокировок аналогичен ключу, с помощью которо- го открывают дверь. Первое задание, которое подошло к двери, захватывает ключ, входит в дверь и закрывает ее с другой стороны. Если другое задание подходит к двери и определяет, что дверь закрыта (потому что за дверью находится первое за- дание), то оно должно остановиться и подождать, пока первое задание на выйдет и не возвратит ключ. Ожидание называется спиннингом (вращением, spinning), так как на самом деле задание постоянно выполняет цикл, периодически проверяя, не возвра- щен ли ключ. Теперь рассмотрим, что будет, если одно задание пытается сначала за- блокировать первую очередь выполнения, а затем вторую, в то время как другое зада- ние пытается сначала заблокировать вторую очередь, а затем — первую. Допустим, что первое задание успешно захватило блокировку первой очереди, в то время как второе задание захватило блокировку второй очереди. После этого первое задание пытается заблокировать вторую очередь, а второе задание — первую. Ни одно из заданий никогда не добьется успеха, так как другое задание уже захватило эту бло- кировку. Оба задания будут ожидать друг друга вечно. Так же как в тупике дороги создается блокировка движения, так и неправильный порядок захвата блокировок приводит к тому, что задания начинают ожидать друг друга вечно, и тоже возникает тупиковая ситуация, которая еще называется взаимоблокировкой. Если оба задания захватывают блокировки в одном и том же порядке, то рассмотренной ситуации произойти не может. В главах 8 и 9 представлено полное описание блокировок. Массивы приоритетов Каждая очередь выполнения содержит два массива приоритетов (priority arrays): ак- тинный и истекший. Массивы приоритетов определены в файле k e r n e l / s c h e d . c в виде описания s t r u c t p r i o _ a r r a y . Массивы приоритетов — это структуры дан- ных, которые обеспечивают 0(1)-планирование. Каждый массив приоритетов содер- жит для каждого значения приоритета одну очередь процессов, готовых к выполне- нию. Массив приоритетов также содержит битовую маску приоритетов (priority bitmap), используемую для эффективного поиска готового к выполнению задания, у которого значение приоритета является наибольшим в системе. struct prio_array ( int nr_active; /* количество заданий */ unsigned long bitmap[BITMAP_SIZE]; /* битовая маска приоритетов */ struct list head queue[MAX_PRIO];/* очереди приоритетов */ 74 Глава 4 }; Константа MAX_PRIO — это количество уровней приоритета в системе. По умолча- нию значение этой константы равно 140. Таким образом, для каждого значения при- оритета выделена одна структура s t r u c t l i s t _ h e a d . Константа BITMAP_SIZE — это размер массива переменных, каждый элемент которого имеет тип unsigned long. Каждый бит этого массива соответствует одному действительному значению приори- тета. В случае 140 уровней приоритетов и при использовании 32-разрядных машин- ных слов, значение константы BITMAP_SIZE равно 5. Таким образом, поле bitmap — это массив из пяти элементов, который имеет длину 160 бит. Все массивы приоритетов содержат поле bitmap, каждый бит этого поля соот- ветствует одному значению приоритета в системе. В самом начале значения всех битов равны 0. Когда задача с определенным приоритетом становится готовой к вы- полнению (то есть значение статуса этой задачи становится равным TASK_RUNNING), соответствующий этому приоритету бит поля bitmap устанавливается в значение 1. Например, если задача с приоритетом, равным 7, готова к выполнению, то устанав- ливается бит номер 7. Нахождение задания с самым высоким приоритетом в системе сводится только лишь к нахождению самого первого установленного бита в битовой маске. Так как количество приоритетов неизменно, то время, которое необходимо затратить на эту операцию поиска, постоянно и не зависит от количества процес- сов, выполняющихся в системе. Более того, для каждой поддерживаемой аппарат- ной платформы в ОС Linux должен быть реализован быстрый алгоритм поиска перво- го установленного бита (find first set) для проведения быстрого поиска в битовой маске. Эта функция называется s c h e d _ f i n d _ f i r s t _ b i t (). Для многих аппаратных плат- форм существует машинная инструкция нахождения первого установленного бита в заданном машинном слове 4 . Для таких систем нахождение первого установленного бита является тривиальной операций и сводится к выполнению этой инструкции не- сколько раз. Каждый массив приоритетов также содержит массив очередей, представленных структурами s t r u c t l i s t _ h e a d . Этот массив называется queue. Каждому значению приоритета соответствует своя очередь. Очереди реализованы в виде связанных списков, и каждому значению приоритета соответствует список всех процессов си- стемы, готовых к выполнению, имеющих это значение приоритета и находящихся в очереди выполнения данного процессора. Нахождение задания, которое будет вы- полняться следующим, является простой задачей и сводится к выбору следующего элемента из списка. Все задания с одинаковым приоритетом планируются на выпол- нение циклически. Массив приоритетов также содержит счетчик n r _ a c t i v e , значение которого со- ответствует количеству готовых к выполнению заданий в данном массиве приорите- тов. |