Карусельный переключатель задач

[Sergey A. Borshch]

Приветствую всех.

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

Пока я представляю себе так: Отделить от TBaseProcess все, связанное со стеком в
наследника. Наследника сделать родителем обычных (теперешних) процессов. И
сделать второго наследника, который вместо одного стека содержит в себе карту
дополнительных процессов, имеющих одинаковый приоритет. Так мы можем на каждый
приоритет иметь либо один процесс, либо до 32 процессов с карусельным
переключением. Отсюда уже рукой подать до создания/удаления этих процессов
внутри одного приоритета на лету.

Так вот, возвращаясь к основному вопросу: у кого-нибудь остались в архивах
какие-то материалы от предыдущей идеи реализации?

--
Regards,
Sergey A. Borshch mailto: sb...@sourceforge.net
SB ELDI ltd. Riga, Latvia

[Sergey A. Borshch]

On 10.04.2015 09:44, Sergey A. Borshch wrote:
> Приветствую всех.

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

Подумал еще немного. Видится два варианта:
1) Карусельный переключатель можно сделать обычным процессом. тогда можно
реализовать его как расширение, ценой лишнего вызова переключателя контекста
(переключение на карусель->переключение на конкретный процесс).
2) Карусельный переключатель реализуется как отдельный класс-процесс без
собственного стека, переключение на нужный процесс карусели происходит в
обратном вызове переключателя задач. Тогда обратный вызов должен быть
виртуальной функцией-членом процесса. В обычном процессе он может вызывать
context_switch_user_hook(), в карусельном переключателе - подставлять контекст
нужного процесса из карусели и вызывать context_switch_user_hook(). Цена -
лишний вызов виртуальной функции в основном переключателе при каждой перепланировке.

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

[Harry Zhurov]

10.04.2015 12:44, Sergey A. Borshch пишет:

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

Это я немного волну гнал - на элхе с закусились с VslavX по
скоростям/функционалу, он апеллировал к тому, что у tnkernel есть
карусельный режим (мол, да, не жизненно необходимая фича, но
представляется удобной, ему нравится и т.п.). Так вот, в пылу дискуссии
возникла идея, как сделать такой функционал на scmRTOS достаточно просто
и не меняя ничего в оси - через механизм расширений. Наверное, я
заикался тут об этом (раз ты помнишь), но вот сообщение не нахожу.

Суть идеи была в следующем: создаётся специальный объект (типа
карусельного манагера), в котором регистриуются процессы, подлежающие
"катанию на карусели" - адреса объектов, параметры вызова (timeslice) и
т.п. Далее, из хука системного таймера вызывается исполняемая функция
этого карусельного манагера (КМ), которая обслуживает список
зарегистрированных процессов, и если, скажем, выясняет, что timeslice
одного процесса истёк и наступила очередь следующего, то она производит
усыпление активного и пробуждение очередного.

Особенность (фича) такой реализации состоит в том, что тут нет привязки
к приоритетам - на карусели катаются любые зарегистрированные в КМ
процессы. Логично, конечно, туда совать низкоприоритетные, но технически
ничего не мешает туда поместить любые, в т.ч. и самый приоритетный, и он
будет как и все остальные прерываться и отдавать управление другим - но
это всё в руках разработчика, как хочет, так и делает. В том числе,
можно задавать и разные длительности timeslice для разных процессов -
одному, например, 1 тик, другому - 2, а третьему хоть 5.

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

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

Будет ли такой КМ интерферировать с сервисами, глубоко не думал,
навскидку не увидел конфликтов. Всякие побочные эффекты типа - захватил
процесс мутекс, и тут бац! - его ссадили с карусели, а ожидающий процесс
будет ждать мутекса - это не гуд. Но это надо продумывать на этапе
дизайна программы. Если ожидающий процесс тоже катается на карусели, то
он, ткнувшись в мутекс, уйдёт в ожидание, т.е. освободит своё место на
карусели - до захватившиего мутекс очередь быстрее дойдёт.

Вообще, тут (КМ&сервисы) надо хорошенько подумать - реализация КМ должна
предусматривать возможные коллизии и нивелировать их.

Вот как-то так. Руки так и не дошли и пока на работе напряг, не могу
серьёзно этим заниматься.

--
HZ

[Harry Zhurov]

10.04.2015 20:44, Harry Zhurov пишет:

> Будет ли такой КМ интерферировать с сервисами, глубоко не думал,
> навскидку не увидел конфликтов. Всякие побочные эффекты типа -
> захватил процесс мутекс, и тут бац! - его ссадили с карусели, а
> ожидающий процесс будет ждать мутекса - это не гуд. Но это надо
> продумывать на этапе дизайна программы. Если ожидающий процесс тоже
> катается на карусели, то он, ткнувшись в мутекс, уйдёт в ожидание,
> т.е. освободит своё место на карусели - до захватившиего мутекс
> очередь быстрее дойдёт.

Вдогонку. Таких КМ может быть несколько, т.е. можно создать несколько
каруселей и крутить их независимо одну от другой. Единственно, наверное,
надо следить, чтобы один и тот же процесс не катался на разных каруселях
(а то штаны лопнут), хотя и тут, вроде, фатального не видно - ну, будет
некая, скажем так, слабопредсказуемость его активности - например,
только один КМ его покатил, тут второй ссдадил. Или наоборот - только
слез одной, поехал на другой. Наверное, это не то, что хочет
разработчик, но такой ситуации, имхо, легко избежать при наличии
должного понимания происходящего.

--
HZ

[Sergey Pinigin]

Добрый день всем.

> Так вот, возвращаясь к основному вопросу: у кого-нибудь остались в архивах
> какие-то материалы от предыдущей идеи реализации?

Тема "Пул одноранговых процессов" от 22 апреля 2012 года.


--
С уважением,
Sergey Pinigin

[Anton Gusev]

Sergey Pinigin пишет 11.04.2015 17:47:

> Тема "Пул одноранговых процессов" от 22 апреля 2012 года.

Для тех, у кого эта тема не сохранилась, вот она:

------------------------------------------

Тема: Пул одноранговых процессов
От: Kirill Akulov
Дата: 20.04.2012 02:27

Привет всем.

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

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

Может кто уже реализовывал?

------------------------------------------

Тема: Пул одноранговых процессов
От: "Harry Zhurov"
Дата: 20.04.2012 09:00

Greeting Kirill!
You wrote on Fri, 20 Apr 2012 00:27:09 +0400

KA> Есть идея выделить часть приоритетов как одноранговые,
KA> в общем случае где-то посередине или даже маской с разрывами.

KA> Логика следующая - если системный таймер тикнул во время выполнения
KA> процесса из пула, то переключиться на следующий готовый процесс из пула.

"Шо, опять?" (с) :)

Опять тема про round-robin планирование. Я смотрю, это стало популярным.
Неужели
действительно такая настоятельная необходимость есть?

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

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

--
H.Z.

### Работа не волк, но и 3.14здюли тоже не зайчата.

------------------------------------------

Тема: Пул одноранговых процессов
От: "Harry Zhurov"
Дата: 20.04.2012 12:24

Greeting All!

Мысли вслух на тему.

Возможно, всё не так мутно, как поначалу казалось. Фактически механизм
round-robin не требует никаких завязок на сервисы ОС и прочие нюансы
реализации.
Более того, тут не требуется даже нарушать работу штатного планировщика. Для
организации очерёдного исполнения процессов нужен критерий, который будет
объединять процессы логические группы, внутри которых и строится "карусель".
Традиционно таким критерием является значение приоритета - т.е. процессы с
одинаковым приоритетом крутятся на своей карусели. Но никто не обязывает
использвать в качестве такого критерия именно значение приоритета. Таким
критерием может быть что угодно - как вот, например, было предложено автором
темы - "пулы одноранговых процессов".

Например, можно создать служебный объект - "карусельный манагер" :), в
котором
будут зарегистрированы процессы, которые требуется каруселить. Этот
объект (а он
может быть не один - "каруселей" может быть много) обрабатывается в ISR
системного таймера, где процессы просто переводятся в состояние
готовых/неготовых
к выполнению, и последующий штатный вызов планировщика произведёт
перепланирование обычным образом. Процессы из списка "карусельного манагера"
усыпляются и пробуждаются в соответствии с указанными значениями тиков
системного
таймера. Таким образом, можно, например, указать разные значения для разных
процессов, и перераспределить нагрузку неравномерно. Причём, менять это
распределение можно прямо на рантайме, затрат ноль.

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

Если в системе ни одной "карусели" не заюзано, то всё получается ровно
так, как
есть - все параметры и накладные расходы не изменяются.

Вот такое видение. Возможно, что-то важное упустил. Если кто что видит
или вообще
есть мнения, будет интересно послушать. :)

--
H.Z.

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

------------------------------------------


Тема: Re: Пул одноранговых процессов
От: Oleksandr Redchuk
Дата: 20.04.2012 16:44

2012/4/20 Harry Zhurov:

HZ> Например, можно создать служебный объект - "карусельный манагер" :), в
Тоже думал в этом направлении, suspend/wakeup по кругу.

HZ> (а он может быть не один - "каруселей" может быть много)
Если в одной из каруселей все приоритеты выше, чем в другой, то вторая
карусель может и не получить время.
Разве что в карусели <<выше>> все заснули по доброй воле в ожидании событий.
Если приоритеты между уровнями пересекаются, то вообще будет каша.

HZ> обрабатывается в ISR системного таймера, где процессы просто
переводятся в
HZ> состояние готовых/неготовых к выполнению, и последующий штатный вызов
Только в случае, если они сейчас не ждут события. Заставлят такие
процессы всё делать поллингом, т.е. перестать пользоваться вызовами
методов очередей и т.п. с ожиданием события -- невежливо.
Если ждут -- сразу переходить маской к следующему из карусели.
Если ждут все -- повезло кому-то с приоритетом ниже приоритетов в
карусели :-)

Для неравномерного распределения нужно как-то <<брезенхемить>>/DDA-шить,
чтобы имеющий больше тиков получал их чаще понемногу, а не один раз
большой пачкой.
Как поступать с квотой, если процесс и так ждёт события -- не знаю.
Похоже, делать вид, что он от своего тика отказался в пользу
малоимущих, т.е. на потом ему не откладывать.

HZ> Если в системе ни одной "карусели" не заюзано, то всё получается
ровно так,
HZ> как есть - все параметры и накладные расходы не изменяются.
Это самое главное :-)


-- wbr, ReAl


------------------------------------------

Тема: Пул одноранговых процессов
От: "Harry Zhurov"
Дата: 20.04.2012 18:32

Greeting Oleksandr!
You wrote on Fri, 20 Apr 2012 13:44:54 +0300


HZ>> (а он может быть не один - "каруселей" может быть много)
OR> Если в одной из каруселей все приоритеты выше, чем в другой, то вторая
OR> карусель может и не получить время.
OR> Разве что в карусели <<выше>> все заснули по доброй воле в ожидании
OR> событий. Если приоритеты между уровнями пересекаются, то вообще
будет каша.

Так это естественно - в духе приоритетной оси. Если надо, чтобы и
"нижние" тоже
получали процессорное время, то их тогда тоже включать в эту карусель.
Объединять
в карусель только соседние приоритеты, это ограничение.

HZ>> обрабатывается в ISR системного таймера, где процессы просто
переводятся в
HZ>> состояние готовых/неготовых к выполнению, и последующий штатный вызов
OR> Только в случае, если они сейчас не ждут события.

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

OR> Для неравномерного распределения нужно как-то <<брезенхемить>>/DDA-шить,
OR> чтобы имеющий больше тиков получал их чаще понемногу, а не один раз
OR> большой пачкой.

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

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

Если процесс ждёт события, т.е. неактивен, то он просто не участвует в
карусели -
её менеджер его пропускает при ротации.


--
H.Z.