Что такое шедулер в программировании

Класс Scheduler

Представляет абстракцию для планировщика среды выполнения с параллелизмом.

Синтаксис

class Scheduler; 

Участники

Защищенные конструкторы

Имя	Описание
Планировщик	Объект Scheduler класса может создаваться только с помощью методов фабрики или неявно.
~Планировщик деструктор	Объект Scheduler класса неявно уничтожается, когда все внешние ссылки на него перестают существовать.

Открытые методы

Имя	Описание
Присоединить	Присоединяет планировщик к контексту вызова. После возвращения этого метода вызывающий контекст управляется планировщиком, а планировщик становится текущим планировщиком.
Создание	Создает новый планировщик, поведение которого описано _Policy параметром, помещает начальную ссылку на планировщик и возвращает указатель на него.
CreateScheduleGroup	Перегружен. Создает новую группу расписаний в планировщике. Версия, которая принимает параметр _Placement , приводит к тому, что задачи в созданной группе расписаний будут предвзяты в сторону выполнения в расположении, указанном этим параметром.
GetNumberOfVirtualProcessors	Возвращает текущее количество виртуальных процессоров для планировщика.
GetPolicy	Возвращает копию политики, с помощью которую был создан планировщик.
Id	Возвращает уникальный идентификатор планировщика.
IsAvailableLocation	Определяет, доступно ли данное расположение на планировщике.
Ссылка	Увеличивает число ссылок планировщика.
RegisterShutdownEvent	Вызывает передачу дескриптора событий Windows в _Event параметре при завершении работы планировщика и его уничтожении. В то время, когда событие сигнализирует, все работы, запланированные планировщику, завершены. С помощью этого метода можно зарегистрировать несколько событий завершения работы.
Выпуск	Уменьшает значение счетчика ссылок планировщика.
ResetDefaultSchedulerPolicy	Сбрасывает политику планировщика по умолчанию в среду выполнения по умолчанию. При следующем создании планировщика по умолчанию он будет использовать параметры политики по умолчанию во время выполнения.
ScheduleTask	Перегружен. Планирует задачу с легким весом в планировщике. Упрощенная задача будет размещена в группе расписаний, определенной средой выполнения. Версия, принимающая параметр _Placement , склоняет задачу к выполнению в указанном расположении.
SetDefaultSchedulerPolicy	Позволяет использовать определяемую пользователем политику для создания планировщика по умолчанию. Этот метод можно вызывать только в том случае, если планировщик по умолчанию не существует в процессе. После установки политики по умолчанию он остается в силе до следующего допустимого вызова SetDefaultSchedulerPolicy метода ResetDefaultSchedulerPolicy .

Замечания

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

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

Иерархия наследования

Требования

Заголовок: concrt.h

Пространство имен: concurrency

Attach

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

virtual void Attach() = 0; 

Замечания

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

В будущем необходимо вызвать метод CurrentScheduler::D etach , чтобы разрешить планировщику завершить работу.

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

Этот метод вызовет исключение improper_scheduler_attach , если этот планировщик является текущим планировщиком контекста вызова.

Создание

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

static Scheduler* __cdecl Create(const SchedulerPolicy& _Policy); 

Параметры

_Политики
Политика планировщика, описывающая поведение только что созданного планировщика.

Возвращаемое значение

Указатель на только что созданный планировщик. Этот Scheduler объект имеет начальное число ссылок, помещенное на него.

Замечания

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

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

CreateScheduleGroup

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

virtual ScheduleGroup* CreateScheduleGroup() = 0; virtual ScheduleGroup* CreateScheduleGroup(location& _Placement) = 0; 

Параметры

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

Возвращаемое значение

Указатель на только что созданную группу расписаний. Этот ScheduleGroup объект имеет начальное число ссылок, помещенное на него.

Замечания

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

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

GetNumberOfVirtualProcessors

Возвращает текущее количество виртуальных процессоров для планировщика.

virtual unsigned int GetNumberOfVirtualProcessors() const = 0; 

Возвращаемое значение

Текущее число виртуальных процессоров для планировщика.

GetPolicy

Возвращает копию политики, с помощью которую был создан планировщик.

virtual SchedulerPolicy GetPolicy() const = 0; 

Возвращаемое значение

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

Артикул

Возвращает уникальный идентификатор планировщика.

virtual unsigned int Id() const = 0; 

Возвращаемое значение

Уникальный идентификатор планировщика.

IsAvailableLocation

Определяет, доступно ли данное расположение на планировщике.

virtual bool IsAvailableLocation(const location& _Placement) const = 0; 

Параметры

_Размещения
Ссылка на расположение для запроса планировщика.

Возвращаемое значение

Указание того, доступно ли расположение, указанное _Placement аргументом, на планировщике.

Замечания

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

Ссылка

Увеличивает число ссылок планировщика.

virtual unsigned int Reference() = 0 ; 

Возвращаемое значение

Новое добавочное число ссылок.

Замечания

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

Метод вызывает исключение improper_scheduler_reference , если число ссылок до вызова Reference метода было равно нулю, и вызов выполняется из контекста, который не принадлежит планировщику.

RegisterShutdownEvent

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

virtual void RegisterShutdownEvent(HANDLE _Event) = 0; 

Параметры

_Событие
Дескриптор объекта события Windows, который будет сигнализировать среде выполнения при завершении работы планировщика и его уничтожении.

Выпуск

Уменьшает значение счетчика ссылок планировщика.

virtual unsigned int Release() = 0; 

Возвращаемое значение

Только что отложенное число ссылок.

Замечания

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

ResetDefaultSchedulerPolicy

Сбрасывает политику планировщика по умолчанию в среду выполнения по умолчанию. При следующем создании планировщика по умолчанию он будет использовать параметры политики по умолчанию во время выполнения.

static void __cdecl ResetDefaultSchedulerPolicy(); 

Замечания

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

Планировщик

Объект Scheduler класса может создаваться только с помощью методов фабрики или неявно.

Scheduler(); 

Замечания

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

Вы также можете явно создать планировщик с помощью CurrentScheduler::Create метода или Scheduler::Create метода.

~Планировщик

Объект Scheduler класса неявно уничтожается, когда все внешние ссылки на него перестают существовать.

virtual ~Scheduler(); 

ScheduleTask

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

virtual void ScheduleTask( TaskProc _Proc, _Inout_opt_ void* _Data) = 0; virtual void ScheduleTask( TaskProc _Proc, _Inout_opt_ void* _Data, location& _Placement) = 0; 

Параметры

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

_Данных
Указатель void на данные, которые будут передаваться в качестве параметра в текст задачи.

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

SetDefaultSchedulerPolicy

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

static void __cdecl SetDefaultSchedulerPolicy(const SchedulerPolicy& _Policy); 

Параметры

_Политики
Политика, заданная в качестве политики планировщика по умолчанию.

Замечания

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

Scheduler/Планировщик

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

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

Уместность применения

Шаблон следует применять, если:

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

Преимущества, достигаемые при применении шаблона При использовании шаблона «Планировщик» объект планировщика независим от политики, по которой упорядочиваются потоки, что упрощает повторное использование кода. Недостатки шаблона

1. Отсутствие способа обмена информацией между ведомыми компонентами зачастую существенно усложняет код.

Детали реализацииКлассы class Scheduler < private AutoResetEvent evnt = new AutoResetEvent(false); private Thread runningThread; private Dictionarywaiting = new Dictionary(); public void Enter(IOrdering s) < var thisThread = Thread.CurrentThread; lock (this) < if (runningThread == null) < runningThread = thisThread; return; >waiting.Add(thisThread, s); > lock (thisThread) < while (thisThread != runningThread) < evnt.WaitOne(); evnt.Set(); Thread.Sleep(1); >evnt.Reset(); > lock (this) < waiting.Remove(thisThread); >> public void Done() < lock (this) < if (runningThread != Thread.CurrentThread) throw new ThreadStateException(@"Wrong Thread"); int waitCount = waiting.Count; if (waitCount else if (waitCount == 1) < runningThread = waiting.First().Key; waiting.Remove(runningThread); evnt.Set(); >else < var next = waiting.First(); foreach (var wait in waiting) < if (wait.Value.ScheduleBefore(next.Value)) < next = wait; >> runningThread = next.Key; evnt.Set(); > > > > class BankAccount < private static int transactionID; private Scheduler scheduler = new Scheduler(); private int balance = 0; public void Handle(Transaction transaction) < int try < Console.WriteLine(String.Format(@"Transaction #: enter scheduler", id)); scheduler.Enter(transaction); Console.WriteLine(String.Format(@"Transaction #: start handling", id)); try < transaction.Do(id); balance += transaction.Chng; >finally < scheduler.Done(); Console.WriteLine(String.Format(@"Transaction #: done! Account balance is ", id, balance)); > > catch (Exception) < >> > interface IOrdering < Boolean ScheduleBefore(IOrdering s); >class Transaction : IOrdering < private static DateTime mTime = DateTime.Now; private DateTime time; public DateTime Time < get < return time; >> private int chng; public int Chng < get < return chng; >> public Transaction(int chng) < mTime = mTime.AddSeconds(1); time = mTime; this.chng = chng; >public void Do(int id) < Console.WriteLine(String.Format(@"Transaction #: Start : : Balance change: roubles", id, time, chng)); Thread.Sleep(1000); Console.WriteLine(String.Format(@"Transaction #: Finish : : Balance change: roubles", id, time, chng)); > public Boolean ScheduleBefore(IOrdering s) < if (s is Transaction) < var otherTransaction = (Transaction)s; return (this.Time < otherTransaction.Time); >return false; > >Программа: static BankAccount bankAccount; static void Thread1() < var msg1 = new Transaction(10); var msg2 = new Transaction(15); var msg3 = new Transaction(112); bankAccount.Handle(msg1); bankAccount.Handle(msg2); bankAccount.Handle(msg3); >static void Thread2() < var msg4 = new Transaction(50); var msg5 = new Transaction(100); bankAccount.Handle(msg4); bankAccount.Handle(msg5); >static void Thread3() < var msg6 = new Transaction(-80); var msg7 = new Transaction(20); bankAccount.Handle(msg6); bankAccount.Handle(msg7); >static void Main(string[] args) < bankAccount = new BankAccount(); new Thread(Thread1).Start(); new Thread(Thread2).Start(); //new Thread(Thread3).Start(); Console.ReadKey(); >UML-диаграмма Диаграмма классов: Диаграмма последовательности Литература

1. http://en.wikipedia.org/wiki/Scheduler_pattern
2. http://ru.wikipedia.org/wiki/Scheduler

О многозадачности и планировщике задач (шедулер)

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

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

 /-----\ +-----+ | CPU | | RAM | \-----/ +-----+

Такими были большинство компьютеров со времён их возникновения. В память помещалась программа и данные, которые она обрабатывала. В конце работы программы в памяти хранился результат выполнения. Во время же работы по шине байт за байтом передавались команды и данные процессору. Так что по сути компьютер — это конвейер заданий и данных. Тут сразу у современного пользователя возникает вопрос: а где мышка, клавиатура и монитор? А это уже надстройки над нашим конвейером. Через прерывания контроллера переферийных устройств в стройный ряд инструкций и данных, летящих из памяти вклиниваются и аппаратные команды, которые заставляют наш конвейер прерваться и перейти к определённому адресу, где расположена программа-обработчик прерывания. В Linux можно посмотреть статистику по прерываниям с помощью команды vmstat — под system есть колонка in (сокращение от interrupts) — количество прерываний в секунду (не все они аппаратные). Данная команда будет выводить статистику каждую секунду 5 раз:

 vmstat 1 5

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

Иллюзия многозадачности

В частности, наша система станет однозадачной. Ведь никакой многозадачности нет (особенно, если мы рассматриваем однопроцессорную систему). Однако, потребность в этом есть: на компьютере могут работать несколько пользователей одновременно, а каждый пользователь хочет запустить несколько задач. Поэтому нам нужно сделать из однозадачной системы иллюзию многозадачной. Для этого мы поделим время работы процессора между всеми задачами. Точнее — поделим всё время работы на небольшие части, а в эти небольшие части (time slice), в которые будем исполнять то одну задачу, то другую. Если делать это очень быстро — создаётся иллюзия параллельной обработки нескольких задач одновременно.

И тут появляется планировщик

Возникает логичный вопрос: а кто будет заниматься созданием иллюзии многозадачности? Какая-то программа для управления программами (этакая мета-программа) — как раз планировщик. Причём от него зависит довольно многое — на сколько хорошо будет работать иллюзия параллельного исполнения множества процессов. Поэтому наша программа-планировщик должна стараться раздавать имеющиеся кванты времени “справедливо”. При этом понятие “справедливо” — тоже довольно обширное. К примеру, пользователь будет недоволен, если воспроизведение фильма будет подвисать, при этом не сильно расстроится, если фоновая задача будет притормаживать. Плюсом к этому будет грустно, если задача распределения ресурсов процессора будет съедать сильно много процессорного времени — неприятно, когда управленцы получают больше, чем исполнители. Также важно помнить, что пользователю важен отклик системы. Поэтому планировщик должен быть привязан как-то к реальному времени. И тут есть множество проблем для планировщика. Так, к примеру, нельзя определить, когда программа дойдёт до определённого момента (идеальный момент для переключения) чисто по алгоритмическим причинам. К слову, может быть кто-то знает альтернативные подходы к реализации вычислительных систем, не процессор-шина-память? Что-то может пойти не так и какая-то программа зависнет — что тут делать, как решать, что нужно передать управление, что делать с этой программой? Опять же, понять, что она реально зависла для произвольной программы мы не можем… И тут остаётся использовать те самые аппаратные прерывания. Если программа сама не передаёт управление — через прерывание таймера мы можем понять, что время пришло переключить управление. Ну и в целом — можно по таймеру следить за “справедливостью” выделения процессорного времени. На него ориентироваться при планировании исполнения процессов.

Пара слов о проблемах реализации многозадачности

Работа с системными ресурсами напрямую предполагает работу программы в реальном режиме процессора, а не в защищённом. Работая в GNU/Linux нам невозможно получить доступ напрямую к любому участку памяти, а также работать с регистрами процессора типа sp, ip и т.д. без изменения кода ядра и его пересборки. С другой стороны можно взять более старую ОС, которая не поддерживает многозадачность (равно как и защищённый режим работы процессора) и пофантазировать — что нам нужно сделать, чтобы там можно было получить иллюзию многозадачности. Например, DOS. Здесь, запустив программу из командной строки, мы получаем доступ ко всем ресурсам — ОС никак не защищает ресурсы компьютера от пользовательских программ, а лишь предоставляет набор процедур для более простого программирования. Поэтому мы можем делать всё, что захотим. К примеру, написать программу, которая будет обеспечивать работу других программ псевдо-параллельно. То есть она будет запускать другие программы, отдавать им или прерывать их исполнение, а между запусками хранить их состояние. Например, значения регистров процессора. Куда важнее, сохранить состояние регистра IP (instruction pointer) — регистра, который указывает на исполняемый в текущий момент код. И здесь важно, чтобы программа сохраняла его по условленному адресу в памяти при передаче управления. Тогда планировщик сможет использовать его для возврата управления. Итого, нам нужно как минимум выделить некоторую память под список IP, соответствующих адресам текущих исполняемых команд в процессах. Кроме того — память компьютера доступна всем и сразу, так что нужно договориться, чтобы авторы программ писали в разных областях памяти, чтобы не залезать в чужую. Опять же нужно позаботиться о стеке процессов. В общем, масса проблем. Многие из них сейчас решаются аппаратными средствами, прочее же делает ОС. Как можно было заметить, действий производится довольно много, чтобы одна программа могла работать рядом с другой. При этом очень многое держится чисто на человеческих договорённостях. И любой отход от договорённостей или ошибка в программе может привести к отказу работы всего компьютера. Надеюсь, в общих чертах было ясно, какие действия необходимы и на сколько непросто написать даже такой примитивный планировщик?

Многозадачность и справедливость

Итак, представим, что у нас есть N процессов и 1 процессор. Нам нужно поделить время процессора между всеми процессами справедливым образом. То есть каждому по 1÷N. Однако, пусть мы и справедливы, и все процессы равны, но некоторые всё же “равнее” — есть процессы с низкой потребностью в отзывчивости и ресурсе CPU, есть же критичные — задержку работы которых пользователь сразу заметит. Поэтому процессы приоритезируются. Тогда наша формула принимает следующий вид: “Процент времени процесса = Приоритет ÷ Сумма приоритетов”. Но это в идеальном мире. В реальности же процессы вольно или невольно стараются получить времени больше, или же отдают управление раньше (через тот же sched_yield), чем им выделено. Тем не менее, за условной “справедливостью” следить нужно. При этом от времени процессора также “откусит” и сам планировщик — мы уже видели, что сама операция переключения рабочего процесса довольно затратна. Плюс ещё нужно рассчитать порядок выполнения — работа алгоритма расчёта также займёт какое-то время. Есть 2 основных подхода к многозадачности: кооперативный и вытесняющий. В кооперативной многозадачности процессы сами решают, когда они готовы отдать управление. В вытесняющей многозадачности планировщик ведёт подсчёт времени
исполнения процессов (с помощью таймера) и сам прерывает рабочий процесс, когда тот выходит за выделенный лимит.

Кооперативная многозадачность

В случае кооперативной многозадачности плюсами будут простота реализации планировщика — ему не приходится принимать решения, а также меньший расход времени на переключение задач — предполагается, что задачи будут переключаться, когда они завершили какой-то этап своей работы и, например, запросили новые данные. Среди минусов же — потенциально низкая отзывчивость, а также зависания из-за ошибок в какой-то конкретной программе (не возвращает управление). Среди примеров ОС, работающих по такому принципу — Windows 3.* Кто-нибудь слышал или даже знаком с этой веткой Windows? К примеру, для переключения между тредами может быть использована команда ThreadSwitch. Текущая задача остаётся активной (готовой) и передаёт управление следующей готовой задаче. Хоть внутри и выполняются низкоуровневые операции, для языка программирования высокого уровня данная функциональная возможность выглядит как обычная функция.

 void ThreadSwitch () < old_thread = current_thread; // Текущий тред убрали в конец очереди add_to_queue_tail(current_thread); // Новый активный тред взяли из начала очереди current_thread = get_from_queue_head(); // Сохраняем stack pointer asm < move bx, old_thread push bp move ax, sp move thread_sp[bx], ax move bx, current_thread move ax, thread_sp[bx] pop bp >return; >

Из очереди тредов берётся новый из начала, текущий помещается в конец. Текущий стек сохраняется в предварительно подготовленный map (словарь номер_треда — адрес_стека_треда ), из этого же map берётся адрес стека для нового треда, кладётся в регистр SP (stack pointer), запускается новый тред. К слову, и в Linux можно попросить ОС забрать управление у треда досрочно с помощью вызова pthread_yield . Все помнят, что такое очередь? Как работает FIFO? Аналогично работает async-await в современных языках программирования высокого уровня таких как ECMA Script, Python3 и т.д. На команде await управление передаётся следующему исполняемому потоку. Внутри событийной петли (по сути — той же очереди) они кружат, выполняясь один за другим.

 from asyncio import * # Сопрограмма async def hello(word): counter = 0 while counter < 10: print("from " + word) # Здесь отдаём управление, # как минимум пока не закончится sleep(0.1) await sleep(0.1) counter += 1 loop = get_event_loop() # Запускаем на петле 2 сопрограммы loop.run_until_complete( gather(hello("A"), hello("B")) ) loop.close()

Вытесняющая многозадачность

Из плюсов - бó‎льшая привязка к реальности (планировщик следит за реальным временем исполнения процесса), а значит более прогнозируемая отзывчивость. Также выше стабильность - если какой-то процесс завис - он будет "выедать" только отведённое ему время. Однако, если размер кусков, на которые мы нарезаем процессорное время мал, то из-за частых смен задач (смен контекста) можно получить потерю производительности. За счёт прогнозируемости и отзывчивости данный подход распространился на почти все современные ОС. Говоря о расходе времени при переключении контекста, как вы думаете, на чём же больше всего теряется время?

Смена контекста (context switch)

Само собой, при смене контекста производится много работы. Часть из неё мы уже описали выше, но особого внимания заслуживает отдельный момент, который мы ещё не обсуждали.

Кеш процессора

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

 /-----\ | CPU | | +-----+ +-----+ \---|cache| | RAM | +-----+ +-----+

Именно благодаря этому небольшая память кеша, но низкое время обращения процессора к ней, и даёт значительный прирост производительности на многих задачах. С другой стороны - при переключении контекстов в кеше может не хватать места под оперативные данные всех процессов - тогда кеш будет обновляться (также говорят “прогреваться”) из памяти по мере необходимости. И это может сильно замедлить работу компьютера по сравнению с работой при горячем кеше. В следующем примере мы запустим программу в 8 потоков на 8-ми ядрах. Они будут увеличивать общий счётчик до довольно большого числа. Так как они будут параллельно обрабатывать одни и те же данные, компьютер будет постоянно синхронизировать кеши.

 #include "pthread.h" #include "stdio.h" #include "time.h" #define THREAD_COUNT 8 #define ITERATION_LIMIT 1000000000LL // Общие данные long long count = 0; static void *hello(void* d) < while(count < ITERATION_LIMIT) ++count; // Изменяем общие данные return NULL; >int main() < pthread_t thread[THREAD_COUNT]; // Запускаем треда for (int i = 0; i < THREAD_COUNT; ++i) pthread_create(&thread[i], NULL, &hello, i); // Ждём завершения в основном треде for (int i = 0; i

 clang -lpthread file.c

Для примера, если запустить эту же программу но на одном ядре (пусть и в 8 потоков) - смены контекста также будут происходить, но кеш будет “горячим” - программа выполнится быстрее. Для запуска на определённых процессорах программ (или миграции) используется утилита taskset (или программно sched_setaffinity ).

 $ time taskset 1 ./a.out real 0m1,372s user 0m1,368s sys 0m0,005s $ time ./a.out real 0m5,007s user 0m39,886s sys 0m0,004s

Посмотреть же статистическую информацию о смене контекстов за секунду можно всё также в vmstat . Столбик system, раздел “cs” (от “context switch”).

nice и приоритет исполнения процессов

Если же мы хотим настроить приоритет программы, воспользуемся утилитой nice (или программно с setpriority ). С помощью неё можно указать ОС, с каким приоритетом мы бы хотели запустить программу. Приоритеты в Linux определяются цифрами от -20 до 19. Чем меньше - тем приоритетнее. Для установки приоритета ниже 0 необходимы права супер-пользователя (например, можно установить через sudo ). Есть ещё процесс idle (процесс для простоя процессора, или же программа запущенная с политикой SCHED_IDLE ), приоритет которого ниже 19 и migration_thread (для вытеснения процесса с ядра для миграции его на другой процессор) - у него выше -20. Для примера, запустим параллельно с разными приоритетами несколько экземпляров предыдущей программы:

 #!/bin/bash nice -n 19 ./a.out >> /dev/null && echo 19 & nice -n 18 ./a.out >> /dev/null && echo 18 & nice -n 11 ./a.out >> /dev/null && echo 11 & nice -n 10 ./a.out >> /dev/null && echo 10 & nice -n 1 ./a.out >> /dev/null && echo 1 & nice -n 0 ./a.out >> /dev/null && echo 0 &

И посмотрим на результат выполнения:

 $ ./nice.sh $ 1 0 10 11 18 19

Идут почти в порядке приоритетов. Также есть renice для изменения приоритета процессу, группе процессов или процессам определённого пользователя. Посмотреть же приоритет запущенных процессов можно через утилиту ps , указав, что нам хочется видеть и столбик nice (NI):

 ps ax -o pid,ni,cmd

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

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

 sysctl -A | grep sched | grep -v domain

Особо нас интересует kernel.sched_min_granularity_ns - это как раз размер кванта времени, выделяемого за раз. На пользовательских машинах и серверах значения могут сильно отличаться. К примеру, на моём ноутбуке это 3мс, а на сервере 10мс. Меньше отзывчивость, зато меньше смен контекста. При этом программа может отдать управление раньше, чем закончился выделенный квант - через sched_yield / pthread_yield . Настройки, увиденные вами характерны для текущего планировщика по умолчанию Linux - CFS - Completely Fair Scheduler (полностью честный планировщик). Однако, до него было ещё несколько планировщиков, а также есть альтернативные.

Планировщики в Linux

• планировщик ведёт список процессов, отсортированный по сроку завершения (deadline);
• в работу берётся готовый процесс, имеющий самый близкий deadline;
• при появлении нового процесса — пересортировка.

Программы же должны при запуске указывать через sched_setattr параметры runtime , deadline и period - время исполнения в худшем случае, срок завершения и период.

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

Помимо ресурса процессора также немаловажен ресурс ввода / вывода. С появлением и распространением SSD дела стали лучше, чем при HDD (аж 10мс для перехода к нужному участку носителя), но всё равно это сильно медленнее, чем работа с памятью. Да и в целом ресурсами лучше зря не разбрасываться.

При работе с дисковой подсистемой используется планировщик ввода / вывода. Причём для разных устройств и задач подходят разные планировщики. Так CFQ (Completely Fair Queue) и deadline планировщики сначала будут буферизировать запросы на чтение / запись, чтобы сгруппировать запросы к устройству так, чтобы эффективнее с него считать. Например, чтобы за один оборот диска можно было прочитать сектора для разных процессов.

С другой стороны, если используется сетевое хранилище, или виртуальное - лучше использовать noop - планировщик, который не будет ничего придумывать, а просто писать / читать как есть. Пусть сетевое хранилище или хостовая система думает об эффективности, а мы не будем на это тратить CPU.

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

 cat /sys/block/устройство/queue/scheduler

Записав же туда нужный планировщик с помощью echo - изменить на нужный.

Для приоритизации операций ввода-вывода используется ionice . Для начала разберёмся с классами планирования:

1. Real time - получают первыми доступ к диску. Использование данного класса может помешать работе других программ. Имеет 8 приоритетов.
2. Best effort (по умолчанию) - также имеет 8 приоритетов. Программы с одним приоритетом обслуживаются по очереди (round-robin).
3. Idle - получает доступ к диску, если другим он не нужен.

Приоритеты от 0 до 7. Меньше - приоритетнее.

Не все планировщики используют приоритеты. К примеру, deadline стремится к тому, чтобы ожидание операции не превышало определённого времени. Noop не делает ничего - просто выполняет операции последовательно. С другой стороны, тот же CFQ использует приоритеты - с ним ionice будет работать.

От шедулера к планировщику

Сразу просьба к строгим читателям. Если вы не поняли какой-либо термин из применённых — спросите, я подскажу, что я имел в виду. А если вам нравится другое написание или перевод этого термина — укажите его в комментарии. Я применяю те, которые нравятся мне.

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

Как я уже говорил, шедулер — это просто функция, которая отвечает на вопрос: какую нить и на сколько времени поставить на процессор.

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

Говоря о шедулере нельзя не сказать о приоритетах.

Приоритет — свойство нити (или процесса) влияющее на конкуренцию этой нити с другими нитями за процессор.

Приоритет обычно описывается парой .

На сегодня сформировалась довольно чёткая схема реализации приоритетов. Приоритеты нитей делятся на три класса:

• Реальное время: нити такого класса всегда вытесняют с процессора нити других классов так быстро, как это возможно, и никогда не снимаются с процессора кроме как по наличию нити с более высоким приоритетом реального времени. То есть — такие нити сами должны решать, когда им больше не нужен процессор.
• Разделение времени: нити такого класса всегда вытесняют с процессора нити класса idle, между собой нити разделения времени конкурируют мягко. Две нити такого класса с разными значениями приоритета будут получать разный процент процессорного времени, но обязательно будут его получать, даже если значения приоритетов различаются предельным образом.
• Idle класс: нити такого класса получают процессор только если нет готовых к исполнению нитей других классов, «на сдачу». Лично я не вижу смысла в значении приоритета внутри класса idle. Хотя так тоже бывает.

Кстати. Говорят, Кернигана как-то спросили, что бы он сделал иначе, если бы писал Юникс заново. «Написал бы creat как create», — ответил мэтр. Я бы добавил к списку исправлений ещё мешок несуразностей, начиная с nice — понятие приоритета в Юниксе почему-то первёрнуто. Чем nice меньше, тем приоритет выше.

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

Кому-то, наверное, уже хочется заглянуть в код. Вот он:
Исходный текст Фантомовского шедулера.

Тут мы немного играем в Пушкина 🙂

И вот уже трещат морозы
И серебрятся средь полей…
(Читатель ждет уж рифмы розы;
На, вот возьми ее скорей!)

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

За сим — продолжим.

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

Конкретно в Фантоме это три очереди, согласно классам:

/** Idle prio threads */ static queue_head_t runq_idle = ; /** Normal prio threads */ static queue_head_t runq_norm = ; /** Realtime prio threads */ static queue_head_t runq_rt = ; 

В целом нить по отношению к процессору может находиться в трёх состояниях:

• Заблокирована. Не находится на процессоре, не может быть на него поставлена. Отсутствует в какой-либо run queue.
• Исполняется. Отсутствует в какой-либо run queue.
• Может исполняться. Присутствует в какой-либо run queue.

То есть, в run queue находятся нити, которые хотели бы попасть на процессор.

Отсюда работа планировщика сводится к тому, чтобы:

1. Определиться с тем, нить какого класса приоритета сейчас будем запускать. Это просто — проверить, не пуста ли очередь realtime — если не пуста, то мы запускаем нить realtime, проверить очередь нормальных приоритетов — если не пуста, то запускаем нормальную нить. Иначе — запускаем idle нить. Если и таких нет, отмечаем, что процессор idle и уходим в нить «вечного» сна.
2. Если определились с приоритетом — выбрать правильную нить для исполнения в данном приоритете.
3. Назначить нити временной интервал для исполнения.

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

 // Have some realtime? if( !queue_empty(&runq_rt) ) < int maxprio = -1; phantom_thread_t *best = 0; phantom_thread_t *it = 0; queue_iterate(&runq_rt, it, phantom_thread_t *, runq_chain) < if( it->thread_flags & THREAD_FLAG_NOSCHEDULE ) continue; if( ((int)it->priority) > maxprio ) < maxprio = it->priority; best = it; > > if( best ) < assert(t_is_runnable(best)); return best; >> 

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

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

Здесь надо отметить, что переменная ticks_left в структуре состояния нити определяет, сколько 10 мсек интервалов нить продержится на процессоре.

Сначала рассмотрим, что делает функция t_assign_time():

 it->ticks_left = NORM_TICKS + it->priority; 

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

Что делает сам планировщик? Выбирает нить с максимальным приоритетом и с ненулевым остатком процессорного времени, её и запускает:

 // Have normal one? if( !queue_empty(&runq_norm) ) < // If no normal thread has ticks left, reassign // ticks and retry do < unsigned int maxprio = 0; // NB! not a negative number! phantom_thread_t *best = 0; phantom_thread_t *it = 0; queue_iterate(&runq_norm, it, phantom_thread_t *, runq_chain) < if( it->thread_flags & THREAD_FLAG_NOSCHEDULE ) continue; if( (it->priority > maxprio) && (it->ticks_left > 0) ) < maxprio = it->priority; best = it; > > if( best ) < return best; >> while(t_assign_time()); > 

Когда все остатки у всех нитей кончились — просит t_assign_time() назначить нитям новые остатки.

Вообще-то, сортировка здесь относительно избыточна. Достаточно просто добавлять нити в конец очереди, а выбирать из начала — fair enough. Вообще, сортировать все нити — очевидно плохо, не делайте так. Я тоже этот кусок перепишу более оптимальным образом, например, так как уже описал выше, для realtime.

Кстати, при чтении кода планировщика надо учитывать, что нити не всегда «съедают» свой квант времени — нить может заблокироваться на примитиве синхронизации и часть времени простоять не по своей воле. Этим и обусловлена сортировка: если приоритет нити высок, то нить после разблокирования вернётся на процессор раньше, чем доработают все остальные нити.

Хорошо, перейдём к idle priority class. Мы попадём сюда только если в предыдущих классах все нити спят или отсутствуют.

 // Have idle one? ret = (phantom_thread_t *)queue_first(&runq_idle); if( ret ) < if( ret->thread_flags & THREAD_FLAG_NOSCHEDULE ) goto idle_retry; // Just take first. Switched off thread will become // last on runq, so all idle threads will run in cycle ret->ticks_left = NORM_TICKS; return ret; > else goto idle_no; 

Здесь всё просто — берём первую попавшуюся, запускаем на стандартное время. Поскольку при снятии с процессора она попадёт в конец очереди runq_idle, все такие нити будут запускаться по кругу.

Наконец, если вообще ничего не нашлось, у нас есть специальная idlest thread на этот случай.

 STAT_INC_CNT(STAT_CNT_THREAD_IDLE); percpu_idle_status[GET_CPU_ID()] = 1; // idle return GET_IDLEST_THREAD(); // No real thread is ready to run 

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

 while(1)

Что здесь не учтено.

Interactive thread prio boost: обычно планировщики увеличивают фактический приоритет нитям, которые замечены во вводе-выводе с консоли или другой сущности, за которой, потенциально, прячется интерактивный юзер. Это повышает перцептивную реактивность системы — «операционка меньше тупит» с точки зрения человека. И наоборот — если нить «доедает» свой таймслайс до конца, и делает это стабильно, ей немного понижают приоритет, считая её чисто вычислительной. С той же целью — повысить реактивность системы.

Это, конечно, касается только нитей с обычным классом приоритетов — никто и никогда не трогает приоритеты реального времени.

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

Инверсия приоритетов.

Предположим, у нас есть страшно важная нить R с максимальным приоритетом реального времени, и нить I с приоритетом класса idle, которая занимается несущественной ерундой. А так же обычная нить U, которая работает с юзером — читает команды с консоли. Шелл, например.

Юзер бездействует, ждёт ввода-вывода и нить U.

Нить I получает процессор, решает поделать свою ерунду и хочет для этого выделить себе немного памяти. Функция выделения памяти ядра запирает глобальный мьютекс и начинает выделять. Работая на idle prio, очевидно.

В этот момент просыпается ото сна нить R, которой пора скорректировать положение стержня поглотителя активной зоны реактора. И тоже хочет немного памяти.

(Давайте не будем привередничать и спрашивать, что U и R делают на одной машине — U может быть сервером статистики по TCP, например.)

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

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

Для того, чтобы это не случалось, делают то, что у меня в Фантоме пока не сделано — инверсию приоритетов.

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

То есть, в нашем примере, нить I на время блокировки мьютекса выделения памяти должна была получить приоритет реального времени от нити R, вытеснить к чертям нить U и доделать то, что блокирует нить R. После разблокировки мьютекса её приоритет должен понизиться обратно до idle и процессор перейдёт к R, как и должно быть.

Вот теперь, наверное, всё. 🙂

• Системное программирование
• Программирование микроконтроллеров