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

[Evgeny_CD]

Есть некий типовой контроллер. 512к FLASH,32к RAM. Такое распределение памяти вызвано объективными технологическими особенностями. И, вероятно так будет долго. Скоро станет 4M FLASH и 256 К SRAM, суть не изменится.

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

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

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

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

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

Типа выбираем блок для обработки, запускаем его с пачкой данных, все остальное копится в буферах. Блок отработал - запустили следующий.

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

Также задача может заказать, через сколько ее надо вызвать.

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

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

Комбинация вытесняющего и невытесняющего механизмов была бы, IMHO, очень эффективной.

Вопросы:

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

[AlexandrY]

Чтобы что-то облегчить, надо что-то нагрузить. ;-)

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

А вообще хотелось бы рассмотреть проблему на конкретных примерах.
Действительно ли там такие проблемы с фрагментацией и ресурсами?

Сети Петри не рассматриваю серьезно, так как уже давно есть Simulink, LabView , Systemview ... который "рвут" эти сети, как говориться, простым брутфорсом.
Плюс в книгах по этим сетям рассматривают такие частные и примитивные приложения, что смешно.

А если отключить таймер, то из вытесняющей RTOS сразу получается кооперативка.

Есть некий типовой контроллер. 512к FLASH,32к RAM. Такое распределение памяти вызвано объективными технологическими особенностями. И, вероятно так будет долго. Скоро станет 4M FLASH и 256 К SRAM, суть не изменится.

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

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

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

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

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

Типа выбираем блок для обработки, запускаем его с пачкой данных, все остальное копится в буферах. Блок отработал - запустили следующий.

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

Также задача может заказать, через сколько ее надо вызвать.

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

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

Комбинация вытесняющего и невытесняющего механизмов была бы, IMHO, очень эффективной.

Вопросы:

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

[Evgeny_CD]

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

Такой задачи не было. Была попытка понять, как максимально эффективно использовать ресурсы контроллера.

Сети Петри не рассматриваю серьезно, так как уже давно есть Simulink, LabView , Systemview ... который "рвут" эти сети, как говориться, простым брутфорсом.
Плюс в книгах по этим сетям рассматривают такие частные и примитивные приложения, что смешно.

Не понял смысла этой фразы. Сети Петри - математический аппарат. Как его можно порвать тупым перебором - не вкурил.

А если отключить таймер, то из вытесняющей RTOS сразу получается кооперативка.

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

Хмм... Про серверы я специально сказал, чтобы разделить эти классы (см. "вариант unix идеологии" в первом посте). Как правило, в узкоспециализированных девайсах можно (и нужно, имхо) избавится от неконтролирумых malloc/free, особенно когда куча/память общая для задач. Только делать это должна не ОС

Разговаривал я тут по душам с разработчкиком одного телемаического сервака. Который принимает данные от 1к+ GSM девайсиков. Первое действие его сервера при запуске - отожрать у ОСи кучу памяти (задается) и запустить поток собственного менеджера памяти

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

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

Еще есть труды Шалыто А.А., в том числе знаменитый

Switch-технология. Алгоритмизация и программирование задач логического управления
http://is.ifmo.ru/books/switch/2

Есть алгоритм решения задачи. Он живет сам по себе.

Есть способы реализации этого алгоритма: структурное, функциональное, логическое, и еще 1001 программирование.

Есть железяка, которая, на самом деле, понимает только один язык - машинные коды.

И вопрос только в том, как корректно преобразовать алгоритм в машинные коды, чтобы:

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

* они должны это гарантированно делать за заданное время.

Сила "обычных" языков программировнаия в том, что они неплохо ложатся на мозги программеров. Но соотнесение их с алгоритмом не так-то просто.

Давайте говорить на чистоту - пока нет способов (точнее, мне они неизвестны), сормальной верификации кода на соотвествие алгоритму. Т.е. есть алгоритм, есть программа, и программе говорит - она реализует этот алгоритм. Проверяем - вроде работает. При этом никакого автоматического способа проверить, соотвествует ли программа алгоритму, нет. И никакой гарантии, что в программе предусмотрена обработка всех состояний, тоже нет.

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

Парадигма многозадачности удобная для восприятия человеком. Она позволяте разбить код на куски, и четко отследить связи между этимми кусками. Что и дают все эти потоки, сигналы, семафоры, m-box, пайпы и сокеты.

Язк программирования + ОСь гарантируют в таком случае изоляцию этих кусков программ. Это возволяет осуществить декомпозицию задачи.

Но плата за это - расход ресурсов среды исполнения.

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

Вот теперь самый главный вопрос - как всю эту систему вызова "миллиона" функций сопоставить с решаемым алгоритмом?

В виде написания "линейного" текста программы точно нет. Вопрос закрыт.

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

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

Вопрос - кто какие системы работы с конечными атвоматами знает - кроме iSTATE и Rapsody?

[AlexandrY]

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

В MATLAB SIMULINK более 1000 функциональных блоков на все случаи жизни. И c дискретным времененм, и с непрерывным, и со смешанным и без времени и вообще че хош. Вот там реально сделать модель над осью и сгенерировать исходники действительно оптимизирующие использование сервисов оси.

А че мы обсуждаем?
Я что-то нить потерял.
Наличие каких-либо проблем никто так и не подтвердил.

А про ресурсы же мы вроде договорились.
Для продвинутой RTOS надо 8 Meг RAM-а и 1/4 от этого для FLASH-а.
Для Линукса на порядок больше.
Кто-то добрый выложил Integrity от GreenHills. Там лишний раз подтверждается оценка для RTOS.
Дальнейшая оптимизация и ужимание особой экономии не принесет.

Такой задачи не было. Была попытка понять, как максимально эффективно использовать ресурсы контроллера.Не понял смысла этой фразы. Сети Петри - математический аппарат. Как его можно порвать тупым перебором - не вкурил.Только вот обычная ОСька малость в осадок выпадет, из-за того что у нее пропадет понятие времени.Разговаривал я тут по душам с разработчкиком одного телемаического сервака. Который принимает данные от 1к+ GSM девайсиков. Первое действие его сервера при запуске - отожрать у ОСи кучу памяти (задается) и запустить поток собственного менеджера памяти

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

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

[Evgeny_CD]

Я как понял эти Петри - просто способ рисовать модели стрелочками, кружочками и квадратиками.
Потом изголяться и искать там какие-то закономерности. Это бред.

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

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

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

[AlexandrY]

Ну и фиг с ними, с этими сетями.
Может они и не бред, но к делу их не пришьешь.
Ладно, я их уважаю.

Моделирование решает задачу когда о среде исполнения известно все и прогнозируете ее поведение при разных воздействиях.

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

А вообще обычно толком не известна ни своя среда ни поведение внешнего мира.

В свете появления фреймворков как PhoneMy, Android, .Net embedded и т.д. среда исполнения становится полным черным ящиком.
Там, кстати, с фрагментацией памяти все схвачено.
Т.е. сведения о критичности фрагментации несколько подустарели.

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

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

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

[Evgeny_CD]

В свете появления фреймворков как PhoneMy, Android, .Net embedded и т.д. среда исполнения становится полным черным ящиком.
Там, кстати, с фрагментацией памяти все схвачено.
Т.е. сведения о критичности фрагментации несколько подустарели.

То, на чем "крутится" PhoneMy, Android, .Net embedded пока, и еще долго будет так, не является SoC в истинном значении этого слова.

Да, вариант проц + внешний флешак + SDRAM 16 мбайт сейча стоит совсем не дорого. Но есть задачи, где SoC должна быть именнно SoC, а не SoB (System on Board).

Кроме того, вот смотрю я на всякие современные PIC32, AVR32 и тихо радуюсь за их создателей. Unix style эти чипы не потянут в чистом виде, без внешней памяти (на 64к ОЗУ сильно в "многопоточность" не наиграешься), "примитивное программирование" не позволит использовать эти чипы на всю катушку (вроятность ошибки при ручном описании сложных автоматов будет экспоненциально возрастать), а вот чего-то среднего в виде сформировавшейся идеологии я пока не вижу.

Собственно, за это и воюю.

А если посмотреть на сегмент Hi-End Low Power, где ATxmega, несомненно, будет королем, то опять-же разбазаривание набортных 8 или 16К под многопоточность является нерациональным. В этом плане искусство создателей Contiki вызывает уважение, а девайс (условно), который может прожить год на батарейке, и при этом может выполнять функции полноценного сетевого узла (с естественными ограничениями из-за батарейности) - очень даже коммерчески востребованная вещь!

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

[zltigo]

А если посмотреть на сегмент Hi-End Low Power, где ATxmega, несомненно, будет королем...

Королем она будет, когда опубликуют не "типовые" цифири а реальный диапазон потребления, причем не только ядра, но и периферии. Пока есть только preliminary даташиты в котором о потреблении той-же периферии "подлежит определению", а по ядру некие "типовые значения".
P.S.
В Риге 17 числа семинар Атмеловский, на котором XMEGA гвоздь программы....

09.00 - 10.00 ATtiny + ATmega (incl.Picopower) family
presentation
*
10 00 - 10.30 XMEGA Presentation
*
10.30 - 10.45 Coffee Break
*
10.45 - 12.00 XMEGA Continued
*
12.00 - 13.00 Coffee break
*
13.00 - 14.00 AVR32 UC3 Presentation
*
14.00 - 15.00 AT91 MPU Family Presentation