[Evgeny_CD 0]

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

Вопросы:

 

* видел ли кто какие наработки по теме?

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

* критика и дополнение моих идей.

[ig_z 0]

* видел ли кто какие наработки по теме?

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

* критика и дополнение моих идей.

 

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

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

 

Из осей вроде OSEK и контики имеют возможность использовать смешанный механизм многозадачности.

[zltigo 2]

* видел ли кто какие наработки по теме?

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

* критика и дополнение моих идей.

- Ну у меня в принципе все "темы" где-то такие.

- FreeRTOS и кооперативные задачи и задачи одного уровня приоритета.

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

[Evgeny_CD 0]

- Ну у меня в принципе все "темы" где-то такие.

- FreeRTOS и кооперативные задачи и задачи одного уровня приоритета.

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

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

Из осей вроде OSEK и контики имеют возможность использовать смешанный механизм многозадачности.

Есть такое. Contiki - это вообще очень интересная ОСька. http://www.sics.se/contiki Adam Dunkels заложил туда массу интересных идей. Есть некий парадок - вроде ОСька маленькая, но она вявляется целыми миром, который изучать можно долго.

 

Про Contiki я помнил, про FreeRTOS тоже, просто интересно, что еще есть на тему.

[Evgeny_CD 0]

Есть еще такая штука, как сети Петри. Мне как-то уже указывали на них. Но тогда я не понял, что это такое и как его надо использовать.

 

Как водится, спустя много времени, потраченного на уединенные размышления, теперь я понимаю, что это!

 

Подборка информации.

 

Экспериментальная версия транслятора сетей Петри в испольняемый код.

http://www.iacp.dvo.ru/lab_11/otchet/ot2000/readme.html

 

10.24 Сети Петри Семенов Ю.А. (ГНЦ ИТЭФ)

http://book.itep.ru/10/petri.htm

 

Отечественный проект!!! VisualPetri is Petri net editor for Windows platform based on GDI Plus library with an integrated simulator. Note: a Petri net is one of several mathematical representations of discrete distributed systems.

http://sourceforge.net/projects/visual-petri/

Поставил. Запускается и работает.

 

Дока от этой софтины

http://www.caree.narod.ru/vpdocs/_content.html

 

 

http://listlib.narod.ru/vichteh2.htm - много интересной литературы. Там найдено:

 

Котов В.Е. Сети Петри.— М.: Наука. Главная редакция физико-математической литературы, 1984.— 160 с.

http://listlib.narod.ru/vichteh/Kotov.djvu

 

Питерсон Дж. Теория сетей Петри и моделирование систем: Пер. с англ.— М.: Мир, 1984.— 264 с.

http://listlib.narod.ru/vichteh/Piterson1.djvu

http://listlib.narod.ru/vichteh/Piterson2.djvu

[Andrew2000 0]

Есть еще такая штука, как сети Петри.

Более близкие к народу (к практике) - IEC61131 - язык SFC

[rezident 0]

ИМХО вытесняющая многозадачность нужна только тогда, когда заранее неизвестно какие именно задачи/приложения будут запускаться и работать совместно и кто и как будет устанавливать их приоритеты? В остальных случаях вполне достаточно кооперативной ОС (даже примитивной "карусели") и набора конечных автоматов, реализующих заранее известные функции с известными приоритетами.

[zltigo 2]

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

... за неизвестное время :( потребляя при этом постоянно большое количесво памяти :(.

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

[vshemm 0]

А что подразумевается под вытесняющей многозадачностью? Если вытеснение одной задачи другой, - тогда понятие "приоритет" теряет смысл, ибо более приоритетная задача должна вытеснять менее приоритетную; так проще применять матаппараты, которые аналитически позволяют строить подобные системы, например, небезызвестный ЧМА (http://mike.qnx.org.ru/files/articles/rms/rms.doc).

 

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

 

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

 

Сети Петри - хорошая штука :) Жаль, только, задача достижимости в общем случае нерешаема. Плюс разные эффекты, связанные с асинхронностью и недерминированностью.

[zltigo 2]

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

А задачи одного приоритета (или разного, но имеющие на данный момент времени одинаковый приоритет) должны выполняться "параллельно".

"Ресурсный" вопрос тоже должен решаться на этапе проектирования (мы же не рассматриваем высоконагруженные сервера или базы данных, верно?

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

В идеале, динамической памяти вообще быть не должно..

Угу, а чего думать - берешь кувалду побольше и ставишь вместо контролера "невысоко нагруженный сервер" :)...

[AlexandrY 3]

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

 

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

 

А вообще хотелось бы рассмотреть проблему на конкретных примерах.

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

 

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

Плюс в книгах по этим сетям рассматривают такие частные и примитивные приложения, что смешно.

 

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

 

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

Вопросы:

 

* видел ли кто какие наработки по теме?

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

* критика и дополнение моих идей.

[vshemm 0]

А задачи одного приоритета (или разного, но имеющие на данный момент времени одинаковый приоритет) должны выполняться "параллельно".

Собственно, это и есть "карусель" (хоть и с квантами), которую тов. rezident отделил от "вытесняющей многозадачности".

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

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

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

Угу, а чего думать - берешь кувалду побольше и ставишь вместо контролера "невысоко нагруженный сервер" :)...

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

[zltigo 2]

К тому же, у задач одинакового приоритета дедлайна не должно быть, иначе зачем им назначать одинаковый приоритет?

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

Динамически менять его тоже не очень хорошая идея, а...

Я реалист, а не идеалист :)

У каналов связи бесконечная пропускная способность, и из них непрерывно сыпятся данные, которые обязательно нужно обработать?

Как-раз с точностью до наоборот. Для "бесконечных" и "непрерывных" нужено взять бесконечно большие ресурсы и никаих проблем :). А вот в реальности, когда обеспечить абсолютно достаточные ресурсы за разумные деньги просто невозможно, тогда и начинается. А c чем-нибудь типа "котроллера светодиода" или на самом деле принципиально от него не отличающегося, например, "MP3 плеера" - проблем в этом смысле нет - ресурсы для них просто обязаны быть достаточными.

Собственно, это и есть "карусель" (хоть и с квантами)...

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

А отстрелить задачу за которой стоит сдохшее железо? А поднять резервный канал?

[Evgeny_CD 0]

Чесно не понял как вы Евгений предлагаете облегчить разработку приложения под 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 3]

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

Потом изголяться и искать там какие-то закономерности. Это бред.

В ваших же книжках написано, что эти сети в основном только для анализа применяются.

Т.е., допустим, уже когда ось готова и хреново работает.

 

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

 

А че мы обсуждаем?

Я что-то нить потерял.

Наличие каких-либо проблем никто так и не подтвердил.

 

А про ресурсы же мы вроде договорились.

Для продвинутой RTOS надо 8 Meг RAM-а и 1/4 от этого для FLASH-а.

Для Линукса на порядок больше.

Кто-то добрый выложил Integrity от GreenHills. Там лишний раз подтверждается оценка для RTOS.

Дальнейшая оптимизация и ужимание особой экономии не принесет.

 

 

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

 

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

 

Видимо, ситуация по памяти выглядит так:

* при инициализации проиходит обращение к malloc

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

* free вызывается только при глобальном завершении процесса на Сервере или типа когда контроллер сдох :)