Алгоритм планирования linux реферат

Обновлено: 04.07.2024

Алгоритм планирования процессов Linux-O (1) и алгоритм планирования CFS

Алгоритм выбора расписания для обычных процессов основан на приоритете процесса, и планировщик выбирает процесс с наивысшим приоритетом. В версии 2.4 счетчик временных интервалов также указывает приоритет процесса. В 2.6 временной интервал представлен полем time_slice в дескрипторе задачи, а приоритет представлен prio (обычный процесс) или rt_priority (процесс в реальном времени). Планировщик поддерживает два массива очередей процессов для каждого ЦП: активный массив, указывающий на активную очередь выполнения, и массив с истекшим сроком действия, указывающий на просроченную очередь выполнения. Элементы в массиве содержат указатели очереди процесса определенного приоритета. Система имеет 140 различных приоритетов, поэтому оба массива имеют размер 140. Они обслуживаются в порядке очереди. Задачи, запланированные для выполнения, добавляются в конец списка приоритетов соответствующих очередей выполнения. Каждая задача имеет интервал времени, в зависимости от того, как долго системе разрешено выполнять задачу. Первые 100 списков приоритетов очереди выполнения зарезервированы для задач реального времени, а последние 40 - для пользовательских задач, см. Рисунок ниже:

Рисунок 1. Структура очереди выполнения планировщика

Рисунок 2 Процесс вторичного опроса RSDL

В алгоритме SD процессы с низким приоритетом в нижней части лестницы должны ждать завершения всех процессов с высоким приоритетом, прежде чем они смогут получить ЦП. Таким образом, время ожидания для процессов с низким приоритетом не может быть определено. В RSDL, когда группа процессов с высоким приоритетом исчерпывает свою Tg (то есть квоту времени группы), все процессы, принадлежащие группе, принудительно сокращаются до следующего приоритета, независимо от того, существуют ли процессы в группе, которые еще не исчерпали Tp Группа процессов. Таким образом, задачи с низким приоритетом могут быть запланированы в предсказуемом будущем. Тем самым улучшается справедливость календарного планирования. Это то, что Срок означает в RSDL.
Когда процесс исчерпывает свой временной интервал (временной интервал Tslice на рисунке ниже), он будет помещен в соответствующую очередь начальных приоритетов, на которую указывает массив expire (приоритет 1).

Рисунок 3 Обработка, когда временной интервал заканчивается

Рисунок 4 Пример красно-черного дерева

struct task_struct
volatile long state; /* -1 unrunnable, 0 runnable, >0 stopped */
void *stack;
atomic_t usage;
unsigned int flags; /* per process flags, defined below */
unsigned int ptrace;
/* . */
int prio, static_prio, normal_prio;
unsigned int rt_priority;
const struct sched_class *sched_class;
struct sched_entity se;
struct sched_rt_entity rt;
/* . */
>;

Рисунок 5 Иерархическая структура данных планирования процессов

Соотношение между различными структурами показано на рисунке выше. На корень дерева ссылаются через элемент rb_root через структуру cfs_rq (в ./kernel/sched.c). Листья красно-черного дерева не содержат информации, но внутренние узлы представляют одну или несколько задач, которые можно выполнить. Каждый узел красно-черного дерева представлен rb_node, который содержит только дочерние ссылки и цвет родительского объекта. rb_node содержится в структуре sched_entity, которая содержит ссылки на rb_node, веса загрузки и различную статистику. Наиболее важно, что sched_entity содержит vruntime (64-битное поле ), которое представляет количество времени, в течение которого задача выполняется, и служит индексом красно-черного дерева. Наконец, task_struct находится вверху, которая полностью описывает задачу и содержит структуру sched_entity.
Что касается части CFS, функция планирования очень проста. В ./kernel/sched.c вы увидите общую функцию schedule (), которая в первую очередь выгружает текущую задачу (если только она не выгружается сначала с помощью yield ()). Обратите внимание, что CFS не имеет концепции истинного квантования времени для вытеснения, потому что время вытеснения является переменным. Текущая выполняемая задача (задача, которая сейчас прервана) возвращается в красно-черное дерево путем вызова put_prev_task (через класс диспетчеризации). Когда функция расписания начинает определять следующую задачу, которая должна быть запланирована, она вызывает функцию pick_next_task. Эта функция также является общей (в ./kernel/sched.c ), но она вызывает планировщик CFS через класс планировщика. Функция pick_next_task в CFS находится в ./kernel/sched_fair.c (она называется pick_next_task_fair ()). Эта функция просто получает крайнюю левую задачу из красно-черного дерева и возвращает связанный sched_entity. С этой ссылкой простой вызов task_of () определяет возвращаемую ссылку task_struct. Общий планировщик наконец-то предоставляет процессор для этой задачи.
(2) Объект планирования: struct sched_entity
Структура в ./linux/include/linux/sched.h представляет планируемую сущность (процесс, группу процессов и т. д.). Он содержит полную информацию о планировании и используется для реализации планирования для одной задачи или группы задач. Объект планирования не может быть связан с процессом.

Это включает в себя вес нагрузки, соответствующий узел красно-черного дерева run_node, виртуальное время выполнения vruntime (представляет время выполнения процесса и служит индексом красно-черного дерева), время начала выполнения, время последнего запуска, различные статистические данные, CFS запускает информацию очереди cfs_rq для группового планирования и так далее.
(3) Класс планирования: struct sched_class
Класс планирования также находится в sched.h. Он является объектно-ориентированной абстракцией операции планировщика и помогает различным задачам планировщика ядра. Класс планирования является ядром диспетчера планировщика, и каждый модуль алгоритма планирования должен реализовывать набор функций, предлагаемых struct sched_class.

Здесь sched_rt.c, sched_fair.c, sched_idletask.c и т. Д. (Все в каталоге kernel /) - это разные алгоритмы планирования. Не забывайте, что класс планирования является частью самой структуры задачи (см. Task_struct). Это упрощает работу задачи независимо от ее класса планирования. Поскольку в дескрипторе процесса есть ссылка на sched_class, различные операции в классе планирования могут вызываться непосредственно через дескриптор процесса. В классе планирования по мере увеличения области планирования его функции также увеличиваются. Эти домены позволяют группировать один или несколько процессоров в иерархических отношениях для балансировки нагрузки и изоляции. Один или несколько процессоров могут совместно использовать политики планирования (и поддерживать балансировку нагрузки между ними) или реализовывать независимые политики планирования.
Однако сам планировщик Linux не был модульным. Это место, которое можно улучшить. Например, для платформы планировщика Pluggable CPU, планировщик по умолчанию может быть выбран при компиляции ядра, и другие планировщики CPU также могут быть выбраны путем передачи параметров ядру при запуске.
(4) Запускаемая очередь: struct rq
Каждый раз, когда планировщик переключается между процессами, он выбирает лучший процесс из выполняемой очереди для запуска. Ядро Linux использует структуру данных rq (структура в предыдущем ядре представляла собой очередь выполнения) для представления информации об ожидаемой очереди (то есть о готовой очереди). Каждый ЦП имеет только одну такую структуру. Эта структура в kernel / sched.c не только описывает рабочее состояние (TASK_RUNNING) каждого процессора, но также описывает информацию о планировании процессора. Следующим образом:

Есть корневой узел красно-черного дерева, указатель, который указывает на запущенный процесс в текущей очереди, листовая очередь leaf_cfs_rq_list, используемая для балансировки нагрузки, и значение веса добавленной нагрузки task_weight.
(6) Узлы красного и черного дерева: struct rb_node, struct rb_root

Планирование – это процесс распределения ресурсов системы для выполнения задач. В статье мы рассмотрим его вариант, в котором ресурсом является одно или несколько ядер процессора, а задачи представлены потоками или процессами, которые нужно выполнить.

Само планирование осуществляется планировщиком, который нацелен:

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

Типы процессов в Linux

В Linux процессы делятся на два типа:

Процессы реального времени.
Условные процессы.

В качестве примера можно привести процесс переноса, отвечающий за распределение рабочей нагрузки между ядрами ЦПУ.

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

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

У каждого типа процессов есть свой алгоритм планирования. При этом пока есть готовые к выполнению процессы реального времени, выполняться будут они, оставляя условные процессы в ожидании.

Планирование в реальном времени

В случае с планированием в реальном времени используются две политики, SCHED_RR и SCHED_FIFO .

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

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

SCHED_FIFO

В данной политике планировщик выбирает процесс, ориентируясь на время его поступления (FIFO = первым вошел, первым вышел).

SCHED_RR

SCHED_RR подразумевает циклическое планирование.

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

Для лучшего понимания рассмотрим пример, где в очереди находятся три процесса, A B C , все из которых работают по политике SCHED_RR .

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

Обобщение по планированию в реальном времени

Процесс реального времени может планироваться по двум разным политикам, SCHED_FIFO и SCHED_RR .

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

Условное планирование

Здесь мы знакомимся с Completely Fair Scheduler (CFS, абсолютно справедливый планировщик), представляющим алгоритм планирования условных процессов, появившийся в версии Linux 2.6.23.

Помните метрики планирования, которые мы затронули в начале статьи? Так вот CFS фокусируется на одной из них – он стремится к максимальной равноправности процессов, то есть обеспечивает выделение всем процессам равных квантов времени ЦПУ.

Обратите внимание, что процессы с повышенным приоритетом все равно могут получать на обработку больше времени.

Для лучшего понимания принципа работы CFS нужно познакомиться с новым термином – виртуальное время выполнения ( vruntime ).

Виртуальное время выполнения

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

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

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

CFS —Абсолютно справедливый планировщик

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

CFS задействует красно-черное дерево, представляющее бинарное дерево поиска – то есть добавление, удаление и поиск выполняются за O(logN) , где N выражает количество процессов.

Ключом в этом дереве выступает виртуальное время выполнения процесса. Новые процессы или процесс, возвращающиеся из ожидания в состояние готовности, добавляются в дерево с ключом vruntime = min_vruntime . Это очень важный момент, который позволяет избежать дефицита внимания ЦПУ для старых процессов.

Вернемся к самому алгоритму. В первую очередь он устанавливает себе лимит времени – sched_latency .

В течение этого времени алгоритм стремится выполнить все готовые процессы – N . Это означает, что каждый процесс получит интервал времени равный временному лимиту, поделенному на количество процессов: Qi = sched_latency/N .

Когда процесс исчерпывает свой интервал ( Qi ), алгоритм выбирает в дереве следующий процесс с наименьшим виртуальным временем.

Рассмотрим ситуацию, которая может стать проблематичной для такой схемы работы алгоритма.

Предположим, что алгоритм выбрал лимит времени 48мс при наличии 6 процессов – в этом случае каждый процесс получит на выполнение по 8мс.

Но что произойдет, если система окажется перегружена процессами? Предположим, что лимит времени остается равен 48мс, но теперь у нас 32 процесса. В результате каждый получит уже всего по 1.5мс на выполнение, что приведет к замедлению работы всей системы.

Почему?

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

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

Предположим, что на него уходит 1мс. В первом примере, где каждому процессу у нас отводилось по 8мс, это вполне допустимо. Так мы тратим 1мс на переключение контекста и 7мс на фактическое выполнение процесса.

А вот во втором примере на выполнение каждого процесса останется уже всего по 0.5мс – то есть большая часть времени уходит на переключение контекста, отсюда и проблема с выполнением.

Представим, что min_granularity = 6мс , и вернемся к нашему примеру, где лимит времени равен 48мс при наличии 32 процессов.

С помощью той же формулы, что и прежде, мы получаем по 1.5мс на каждый процесс, но теперь такой вариант не допускается, так как min_granularity задает минимальный квант времени, который должен получить каждый процесс.

В данном случае, где Qi , мы берем Qi равным min_granularity , то есть 6мс, и соответствующим образом изменяем временной лимит. В результате он составит Qi x N = 6мс x 32 = 192мс .

На данный момент отличия между CFS и RR могут оказаться недостаточно наглядны, поскольку они оба определяют временные интервалы и организуют порядок выполнения процессов. Для лучшего обобщения и понимания различий между этими алгоритмами я приведу краткую таблицу:

Квант времени статичен и не зависит от количества процессов в системе.

Квант времени динамичен и может изменяться в соответствии с количеством процессов в системе.

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

По исчерпанию процессом его кванта времени, CFS выбирает очередной процесс с наименьшим виртуальным временем из красно-черного дерева.

Надеюсь, что статься помогла вам лучше понять реализацию планирования задач в ядре Linux.

Прошу обратить внимание, что автор оригинальной статьи Eliran поблагодарил читателей за интерес и отдельно пригласил желающих со знанием английского языка в свой блог Coding Kaiser для ознакомления с множеством материалов по смежным и другим интересным темам, а также обмена идеями.

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

Запрос на исполнение в режиме ядра может возникнуть в двух случаях:

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

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

Linux использует два метода для защиты критических секций:

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

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

Службы обработки прерываний делятся на верхнюю половину ( top half ) и нижнюю половину ( bottom half ):

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

Эта архитектура дополняется механизмом для выбора нижних половин при исполнении обычного кода ядра.

На рис. 25.4 изображены уровни защиты прерываний.

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

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

Linux использует два алгоритма планирования процессов:

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

Класс планирования процесса определяет, какой именно алгоритм применить.

Для процессов с разделением времени Linux использует алгоритм на основе доверия (credits) с приоритетами ( priority ). Правило credits := credits / 2 + priority учитывает как историю процесса, так и его приоритет. По такой системе автоматически определяются приоритеты интерактивных процессов или исполняющих ввод-вывод.

Linux реализует классы планирования : FIFO и round-robin ; в обоих случаях каждый процесс имеет приоритет, а не только определенный класс планирования .

Планировщик запускает процесс с наивысшим приоритетом; для процессов с одним и тем же приоритетом, он исполняет процесс, который дольше всего ждал.

FIFO – процессы исполняются до их завершения или блокировки.

round-robin – процесс будет прерван через некоторое время и помещен в конец очереди планирования, так что RR-процессы одинакового приоритета автоматически разделяют время между собой.

Версия Linux 2.0 была первым ядром Linux, поддерживающим SMP -оборудование; различные процессы или потоки могут исполняться параллельно на нескольких процессорах.

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

Ключевые термины

GNU General Public License (GPL) – лицензия , согласно которой используется и распространяется Linux: программист, использующий Linux, либо создающий свои собственные системы на базе Linux, не имеет права превращать свой продукт в коммерческий; программное обеспечение , распространяемое на основе GPL , не может распространяться только в виде двоичного кода (т.е. в поставку Linux должен быть включен исходный код).

Загружаемый модуль ядра ( loadable kernel module, LKM ) – механизм Linux, обеспечивающий возможность компиляции, загрузки и выгрузки отдельных модулей кода ядра, независимо от остальной части ядра.

Идентификатор процесса (PID) - уникальный идентификатор процесса (число), используемое для указания процессов в операционной системе.

Контекст процесса – состояние исполняемой программы в любой момент времени; состоит из контекста планирования, контекста системы файлов, таблицы обработчиков сигналов и контекста виртуальной памяти.

Окружение процесса – системная структура, состоящая из двух векторов, завершающихся нулями: вектор аргументов командной строки процесса и вектор ( переменных) окружения процесса.

Краткие итоги

Система Linux – популярная ОС, созданная в начале 1990-х гг. с целью разработки UNIX -совместимой ОС с открытым исходным кодом. Создатель Linux – Линус Торвальдс. Основная часть Linux полностью оригинальна и не содержит ведомственного конфиденциального кода.

Linux использует разработки BSD UNIX , AT&T UNIX , библиотеку X Windows . Разработка Linux поддерживается сетью разработчиков, связанных через Интернет .

Дистрибутивы Linux имеют стандартный формат ( RPM ), что обеспечивает совместимость между многочисленными диалектами Linux.

Ядро Linux распространяется на условиях GNU General Public License , суть которых в том, что разработки на основе кода Linux нельзя использовать для коммерческих целей, и распространение ПО , разработанного на основе Linux, должно включать исходные коды.

Linux в основном используется как серверная ОС . Доля ее использования как клиентской ОС очень мала.

Linux – свободно распространяемая полнофункциональная ОС с полным набором UNIX -совместимых инструментов. Обеспечивается совместимость с POSIX . Linux API соответствует UNIX SVR4 , но не UNIX BSD .

Linux состоит из ядра, системных библиотек и системных утилит. Код ядра исполняется в привилегированном режиме. Системные библиотеки и утилиты исполняются в пользовательском режиме.

Важное новшество в Linux – механизм динамически загружаемых модулей ядра , который дает возможность отдельно компилировать, загружать, запускать и выгружать модули ядра . Компоненты модуля ядра – управление загрузкой модуля, регистрация драйверов и разрешение конфликтов .

Для управления процессами в Linux для каждого процесса создаются и используются его идентификация , окружение и контекст .

Для поддержки многопоточности в Linux используется системный вызов clone , который создает новый процесс в адресном пространстве процесса -родителя.

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

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

При планировании процессов в Linux учитываются кредиты и приоритеты. Используются классы планирования FIFO и round-robin .

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

Рубрика	Программирование, компьютеры и кибернетика
Вид	статья
Язык	русский
Дата добавления	17.11.2020
Размер файла	20,7 K

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

ЭВОЛЮЦИЯ ПЛАНИРОВЩИКОВ ЗАДАЧ В ОПЕРАЦИОННОЙ СИСТЕМЕ LINUX

Степанов А.В., г. Москва

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

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

Ключевым моментом в обеспечении корректной работы ОС является планировщик выполнения задачмикропроцессорной техники вызывает сложные проблемы организации эффективного решения планирования. .

Архитектура планировщика в ОС Linux непрерывно изменялась. Рассмотрение эволюции планировщика задач данной ОС является необходимым для определения путей дальнейшего совершенствования механизмов выполнения программ. Исследованию этих вопросов посвящены отдельные работы таких ученых, как Таненбаум Э. С., Вудхалл А.С и др [5,6,7].

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

Основная задача планировщика состоит в выполнении максимального объёма работы в условиях ограничений.

Автором планировщика ОС Linux для ядер серии 2.6.x является Инго Молнар (Ingo Molnar) [10;11].

На вход планировщику поступает очередь задач, которую необходимо выполнить. Длина этой очереди определяет время работы планировщика ОС Linux ядер серии 2.4.x. но не 2.6.x серии.

0(n) - эта запись используется для отображения того факта, что с возрастанием количества входных данных, возрастает время работы самого планировщика.

0(1) - запись показывает что, время работы алгоритма константное. Алгоритм, который характеризуется 0(1), гарантирует завершиться за некий период времени вне зависимости от размера входящей очереди задач. Каждая часть такого алгоритма выполняется за некое константное время.

Работа планировщика ядра 2.6.x базируется на использовании следующих понятий:

Runqueue - очередь задач готовых к выполнению. Каждый ЦПУ имеет свою очередь задач.

Priority array - массив приоритетов. Очередь задач связана с двумя массивами приоритетов: один активный другой пассивный. Массивы приоритетов меняются местами, когда активный массив приоритетов опустошается. Задача массива приоритетов сводится к нахождению задачи с наибольшим приоритетом за константное время. Массив приоритетов представляет собой битовое поле, которое отображает приоритеты для активных задач.

Интерактивные кредиты - позволяют лучше распределять процессорное время между интерактивными задачами. Задача получает интерактивный кредит, когда долго спала, и наоборот, теряет интерактивный кредит, когда значительное время занимала ЦПУ.

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

Классификации нитей является одним из ключевых мест работы планировщика ядра 2.6.x. Планировщик, для работы на пользовательских системах, ставит нитям В/В высокий приоритет доступа к ЦПУ. Это делается с целью повышения интерактивности. Без этого подхода, при большой нагрузке ЦПУ, в моменты больших вычислений, пользователь будет ощущать не достаточно быструю реакцию компьютера на свои действия.

Также известно, что нити В/В занимают много времени и их лучше запустить на выполнение как можно раньше. Например, программа, ожидающая данные из дискового накопителя, значительное время будет находиться в режиме ожидания, прежде чем она получи свои данные. Пока будут извлекаться данные из диска, ЦПУ сможет выполнить другую полезную работу.

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

Планировщик ядра ОС Linux 2.6.x позволяет приложениям реального времени (РВ) указывать очень жёсткие по времени предельные сроки выполнения (deadline), но не гарантирует их соблюдения. Под мягким планированием (soft RT scheduling) понимают, отсутствие гарантии, что задача будет выполнена к некоторому желаемому сроку (deadline).

Нити РВ выделяются в отдельный класс. Планировщик дает нитям РВ приоритет над всеми другими нитями в системе:

задачи РВ имеют приоритеты в диапазоне 0-99;

обычные задачи отображаются в диапазон 100-140.

Поскольку задачи РВ имеют приоритет "ниже" чем обычные задачи, они всегда вытесняют обычные задачи. В момент выполнения задач РВ, выполнения других задач невозможно. Это связано с тем, что задачи РВ работают с другими схемами планирования:

Обычные задачи маркируются как SCHED_NORMAL.

Планирование задач РВ по схеме SCHED_FIFO. Если процессор содержит SCHED_FIFO (First In First Out) задачу она вытесняет любую другую задачу и выполняется так долго, сколько ей необходимо. Такая задача не имеет ограничений по времени выполнения. Если в очереди задач несколько SCHED_FIFO задач, то планировщик распределит выполнение задач по приоритетам: задачи с более высоким приоритетом вытеснят задачи с более низким приоритетом.

Планирование задач РВ по схеме SCHED_RR. Механизм планирования SCHED_RR (Round-Robin) задач очень похож на планирование SCHED_FIFO задач. Отличие состоит в том что:

a) для каждой SCHED_RR задачи указано как много она может использовать процессорного времени (timeslice);

b) любая SCHED_RR задача будет безоговорочно вытеснена SCHED_FIFO задачей. SCHED_FIFO нити имеют более высокий приоритет, чем SCHED_RR нити.

SCHED_RR задачи планируются согласно своим приоритетам по кругу (round-robin). Задача, которая использовала отведённое ей процессорное время, помещается в конец очереди.

Каждая SCHED_RR задача согласно своему приоритету выполняется в течение отведённого ей процессорного времени, а потом заносится в конец списка очереди согласно своему приоритету (priority array queue).

Вначале файла kernel/sched.c определено несколько макросов. Изменяя определения этих макросов можно достичь желаемой работы планировщика.

Рассмотрим более раннюю реализацию планировщика ОС Linux в серии ядер 2.4.х. Он имеет надёжный дизайн. Но существует ряд нежелательных характеристик. Планировщик делит время на эпохи. Эпоха - период времени, за которое каждая задача может использовать своё процессорное время. В начале наступления новой эпохи для каждой задачи планировщик подсчитывает сколько времени она может выполнятся O(n) итераций.

Каждой задачи присваивается базовое значение в течении которого она может использовать ЦПУ. Это значение определяется пользователем с помощью утилиты nice. Установленное значение масштабируется в некое количество тактов микропроцессора. Значение 0 примерно масштабируется в 200 мили секунд.

Когда происходит подсчёт сколько процессорного времени выделить для задачи, это базовое значение может изменится в зависимости является ли задача В/В. Каждая задача имеет переменную counter. Эта переменная содержит количество оставшихся тактов микропроцессора. За всю эпоху, задача могла не использовать все выделенное ей процессорное время, т.е. значение переменной counter > 0. Это могло произойти например если задача спала находилась в ожидании операции В/В. Тогда в конце эпохи задаче будет выделено больше процессорного времени.

Когда задача порождает потомка, то, процессорное время родителя разделяется с потомком, что предотвращает захват ЦПУ размножением.

Функуия schedule() чтобы выбрать задачу для выполнения, вызывает функцию goodness(). Функция goodness() проверяет наличие задачи, которая может выполнится в текущем адресном пространстве (p->mm == prev->mm), и если есть, то ей отдаётся предпочтение.

· Плохая масштабируемость (scalability) == 0(n). Планировщик назначает всем задачам приоритеты (цикл через все активные задачи).

· Планировщик ищет задачу с наивысшим приоритетом (также цикл через все задачи).

· Если существует 100 активных нитей, и одна нить с более низким приоритетом чем все остальные нити, то этой нити придётся ждать своего выполнения 20 сек: 200 мс * 100

· Если существует несколько интерактивных задач с более высоким приоритетом, обычные задачи будут голодать и долго ожидать времени выполнения. Пример: WEB-сервер получив данные c ресурса В/В будет очень долго формировать ответ.

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

Автор текущей реализации планировщика (2.6.x) Инго Молнар предложил полностью переписать подсистему планирования в ядре Linux. Тем не менее, Молнар заметил, что планировщик должен оставаться универсальным и пригодным для использования в пользовательских настольных системах и высокопроизводительных серверах.

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

Особенностью предложенного Молнаром подхода является то, что выбор алгоритма должен происходить на этапе компиляции ядра Linux.

В качестве базового модуля автор данной идеи предлагает использовать Completely Fair Scheduler (CFS) - полностью справедливый планировщик. Замысел алгоритма CFS вполне радикален: он не использует очередей задач (runqueues), а использует отсортированную во времени структуру Red Black Tree (сбалансированное красно-черное дерево). Эта структура используется для построения очередности выполнения задач. По заявлению автора, этот алгоритм избавлен недостатков текущего планировщика, источником которых были переключаемые массивы задач. Задачи помещаются в дерево согласно их приоритету (времени, оставшемуся от timeslice), и дерево постоянно перемешивается (подобно тому, как раньше массивы менялись местами). Алгоритм подсчитывает время, оставшееся от выделенного процессу на исполнение в данный интервал, что и является приоритетом.

Планировщик CFS использует наносекундный учет времени выполнения задач и не зависит от других рабочих характеристик ЦПУ, например его частоты.

Алгоритм CFS не учитывает процессорное время, выделенное задаче, или эвристические данные о потоке выполнения задач. Единственный способ управлять работой планировщика предусмотрен изменением параметра в файле /proc/sys/kernel/sched_granularity_ns. Таким образом, изменяя значение этого параметра, можно подстраивать функционирование ОС для работы в режиме:

сервера - задачи хорошо укомплектованы;

рабочей станции - минимальное время реакции на действия пользователя.

В любом случае, необходимые поправки, изменения, дополнения в работу алгоритма CFS можно внести в модуль sched_fair.c. Предполагается, что данный подход позволит упростить подсистему планирования.

Время работы алгоритма CFS оценивается в O(log(n)) по сравнению с O(1) в текущей реализации планировщика.

Модуль sched_rt.c содержит алгоритмы планирования для обслуживания выполнения задач в реальном времени. По заявлению автора, реализация механизма по обслуживанию задач реального времени по принципу SCHED_FIFO и SCHED_RR значительно упрощена. Используется только 100 очередей задач соответствующих каждому уровню приоритета (вместо 140 очередей в текущем ядре). Также, нет необходимости использовать массив для учета просроченных задач.

Аналогичный подход к организации подсистемы планирования был предложен раньше Кон Коливас (Con Kolivas) [8,9]. Коливас первым предложил идею модульной организации планировщика, и выдвинул на обсуждение свою первую реализацию. Тем не менее, автор ядра Linux - Линус Торвальдс (Linus Torvalds) отклонил предложенную реализацию. Принципиальное отличие варианта Коливаса от Молнара заключается в возможности выбора нужного алгоритма планировщика в момент функционирования ОС. Это разногласие послужило поводом к бурным спорам в обществе ОС Linux. По мнению Молнара и Торвальдса планировщик задач является очень низкоуровневой частью ОС, должен четко и предсказуемо функционировать, и быть пригодным для использования во многих случаях, и пользователь должен довольствоваться стандартным планировщиком. Коливас же настаивает, что пользователь должен иметь право выбора нужного ему планировщика, и предлагает более гибкую архитектуру для построения необходимой среды выполнения.

В качестве замены стандартного алгоритма планировщика ядра 2.6.x, Коливас предложил свою реализацию алгоритма Staircase Deadline(SD) или же Rotating Staircase Deadline (RSDL).

На основе анализа работ Коливаса кратко опишем свойства этого алгоритма:

нет суждения об интерактивности нитей;

нет бонусного механизма;

фактически полное справедливое распределение ЦПУ, основано на статическом приоритете (nice) задач;

маленькое время задержки (latency) с эффективным deadline механизмом;

отличная интерактивность задач в допустимых пределах ограничений, накладываемых предыдущими пунктами;

время работы планировщика оценивается в O(1);

также как и в текущем планировщике ядра 2.6.х используется двойной битовый массив (что в некоторой мере вносит недостатки);

использование статических приоритетов (nice) для распределения времени ЦПУ очень эффективно.

На наш взгляд, подход Коливаса представляется более практичным, хотя он и был отклонен. Гораздо удобней передать ядру параметр, который бы указывал, какой планировщик использовать. В данном походе отпала бы необходимость перекомпиляции ядра для изменения алгоритма планирования. Несомненным плюсом также оказалась бы возможность использовать один планировщик в окружении другого планировщика по иерархической структуре. Такая схема позволяет более гибко создавать необходимую инфраструктуру для выполнения задач.

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

Литература

linux планировщик задача многоцелевой

1. Вахалия Ю. UNIX изнутри. - СПб.: Питер, 2003. - 848 с.

2. Клаудия Зальзберг Родригес, Гордон Фишер, Стивен Смолски Linux. Азбука ядра. - М.: КУДИЦ-Пресс, 2007. - 448 с.

3. Роберт Лав. Разработка ядра Linux. - М.: Вильямс, 2006. - 448с.

4. Скотт Максвелл. Ядро Linux в комментариях. М.: ДиаСофт, 2000. - 488 с.

Операционная система – комплекс взаимосвязанных системных
программ, назначение которого – организовать взаимодействие пользователя
с компьютером и выполнение всех других программ. Операционная система
выполняет роль связующего звена между аппаратурой компьютера и
выполняемыми программами, а также пользователем.
Наибольшей популярностью в мире пользуются операционные
системы фирмы Microsoft. Их доля составляет 95% среди всех операционных
систем. Наиболее устойчивые системы этой фирмы основаны на технологии
NT (Windows NT/2k/XP). В последние шесть лет возрастает популярность
операционной системы под названием Linux.

Нет нужной работы в каталоге?

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

Цены ниже, чем в агентствах и у конкурентов

Вы работаете с экспертами напрямую. Поэтому стоимость работ приятно вас удивит

Бесплатные доработки и консультации

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

Если работа вас не устроит – мы вернем 100% суммы заказа

Техподдержка 7 дней в неделю

Наши менеджеры всегда на связи и оперативно решат любую проблему

Строгий отбор экспертов

Требуются доработки?
Они включены в стоимость работы

Работы выполняют эксперты в своём деле. Они ценят свою репутацию, поэтому результат выполненной работы гарантирован

Читайте также: