Главная » Ядро Linux » Стратегия планирования

0

Стратегия (policy)  планирования— это  характеристики поведения  планировщика, которые определяют, что  и  когда  должно  выполняться. определяет глобальный характер   поведения системы и  отвечает  за  оптимальное  использование процессорного времени. Таким образом, это  понятие очень  важное.

Процессы, ограниченные скоростью ввода-вывода и скоростью процессора

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

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

Указанные классификации не  являются взаимно исключающими. Процессы могут сочетать  в  себе  оба  типа  поведения:  сервер   системы  X Windows — это  процесс, который  одновременно  интенсивно  загружает   процессор и  интенсивно выполняет операции  ввода-вывода.  Некоторые  процессы  могут  быть  ограничены  скоростью ввода-вывода,  но  время  от  времени начинают  выполнять интенсивную  процессорную работу.  Хороший пример — текстовый процессор, который обычно ожидает  нажатия  клавиш, но  время  от  времени может  сильно   загружать  процессор, выполняя проверку орфографии.

Стратегия  планировани я  операционно й  системы  должна   стремитьс я  к  удовлетворению двух  несовместных условий:   обеспечение высокой  скорости  реакции процессов  (малого   времени задержки,  low latency)   и  высокой  производительности (throughput). Для  удовлетворения этим  требованиям часто  в планировщиках  применяются  сложные  алгоритмы определения  наиболее подходящего для  выполнения процесса,  которые дополнительно  гарантируют, что  все  процессы,  имеющие более низкий  приоритет, также  будут  выполняться.  В  Unix-подобных операционных системах  стратегия планирования  направлена на  то, чтобы  процессы, ограниченные скоростью ввода-вывода,  имели  больший приоритет. Использование  более  высокого приоритета для  процессов,  ограниченных скоростью ввода-вывода,  приводит к уве-

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

Приоритет процесса

Наиболее  широко  распространенным типом  алгоритмов  планирования является планирование с управлением по приоритетам  (priority-based).  Идея  состоит  в том,  чтобы расположить  процессы  по  порядку  в соответствии  с  их важностью  и необходимостью  использования процессорного  времени.  Процессы  с  более  высоким  приоритетом  будут выполняться   раньше  тех,  которые  имеют  более низкий  приоритет, в то время  как  процессы  с одинаковым  приоритетом  планируются  на выполнение циклически   (по  кругу, round-robin), т.е. периодически  один за другим. В некоторых операционных системах,  включая  Linux,  процессы  с  более  высоким  приоритетом получают также  и более длительный  квант  времени.  Процесс,   который  готов к выполнению,  у которого  еще не закончился  квант  времени  и который  имеет наибольший  приоритет,  будет выполняться  всегда. Как операционная система,  так и пользователь могут устанавливать  значение  приоритета  процесса  и  таким  образом  влиять на  работу планировщика системы.

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

В ядре  Linux используется  два различных диапазона  приоритетов.  Первый — это параметр  nice,  который  может  принимать  значения  в диапазоне  от -20  до  19,  по умолчанию  значение  этого  параметра  равно  0. Большее  значение  параметра  nice соответствует меньшему  значению  приоритета — необходимо  быть более тактичным  к другим процессам  системы (пicе— англ. тактичный,  хороший).  Процессы  с меньшим значением  параметра  nice (большим  значением  приоритета)   выполняются  раньше процессов  с большим  значением  niie (меньшим  приоритетом).  Значение  параметра nice позволяет  также  определить,  насколько  продолжительный   квант  времени  получит процесс.  Процесс  со  значением  параметра  nice равным  -20  получит квант  времени  самой большой  длительности,  в то время как процесс  со значением  параметра nice равным  19 получит наименьшее  значение  кванта  времени.  Использование параметра nice — это стандартный  способ указания  приоритетов  процессов  для всех Unixподобных  операционных систем.

Второй  диапазон значений приоритетов— это  приоритеты реального времени (real-time priority), которые будут рассмотрены ниже.  По  умолчанию диапазон значений  этого  параметра лежит  от 0 до 99.  Все процессы реального времени имеют более высокий приоритет по сравнению с обычными процессами. В операционной системе  Linux приоритеты реального времени реализованы в соответствии со стандартом  POSIX.  В большинстве современных Unix-систем они реализованы по аналогичной схеме.

Квант времени

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

На основе  этих  аргументов можно  сделать  вывод, что любое большое  значение кванта  времени приведет  к ухудшению  интерактивной производительности. При реализации большинства операционных систем  такой  вывод  принимается близко к сердцу  и значение кванта  времени, используемое по умолчанию, достаточно мало, например равно  20 мс. Однако в операционной системе  Linux используется то преимущество, что процесс с самым  высоким приоритетом всегда выполняется. Планировщик ядра Linux поднимает значение приоритета для интерактивных задач, что позволяет им выполняться более  часто.  Поэтому в ОС Linux планировщик использует  достаточно большое  значение кванта  времени (рис 4.1).  Более  того, планировщик ядра  Linux динамически определяет значение кванта  времени процессов в зависимости от их приоритетов. Это  позволяет процессам с более  высоким приоритетом, которые считаются более важными, выполняться более часто  и в течение большего периода времени. Использование динамического определения величины кванта  времени и приоритетов позволяет обеспечить большую  устойчивость и производительность планировщика.

Следует  заметить, что  процесс не  обязательно должен  использовать весь  свой квант  времени за один  раз.  Например, процесс, у которого квант  времени равен

100 мс, не обязательно должен  беспрерывно выполняться в течение  100 мс, рискуя потерять всю оставшуюся неистраченную часть кианта времени. Процесс может  выполняться в течение  пяти  периодов длительностью по 20 мс каждый.

2Вместо термина timeslice (квант  времени) иногда также используется quantum (квант) или processor slice. В ОС Linux применяется термин  timeslice.

Меньший приоритет или          Больший приоритет или

Минимум

По умолчанию

Максимум

5мс

100 мс

800 мс

Рис.  4.1.  Вычисление кванта  времени процесса

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

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

Вытеснение процесса

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

Стратегия  планирования  в действии

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

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

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

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

По теме:

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