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

А чем, по-вашему, принципиально отличается вытесняющий планировщик от ОС? Точнее, в каком окружении он живёт, и как можно назвать совокупность этого окружения и планировщика?

для меня к примеру тем что наверняка существуют программы (standalone) которые работают по такому принципу*(http://chipenable.ru/index.php/programming-c/110-scheduler.html), и есть ОСи, предоставляющие сервисы и имеющие интерфейсы для приложений.

Автомат на прерываниях с разрешением вложенности.

спасибо, можно немного подробнее?

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

У меня работает сферический конь в вакууме.

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

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

Но полностью на си написать такое - врядли.
Сам переключатель задач - на ассемблере - строк 50, думаю.
А вот планировщик - наверное все 100 (Это вместе с утилитами, типа добавить процесс, убить процесс и прочая).

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

Возьмём пример:
система должна принимать данные от АЦП, обробатывать их блоками, передавать по UART (по 3-м сразу и независимо), весли лог работы на SD-карту, работать с часами реального времени....
вобщем пример класический)

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

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


Это проще попробовать. Желательно не на навороченном проекте, а на небольшом, несложном. Если понравится (почти наверняка), то потом будете применять ОС вне зависимости от задачи

а если я вижу программу для ОС, и там тоже переключение потоков организовано, получается ОС в ОС?)

возможно, это неправильное применение ОС? Хотя, я имею ввиду именно простейшие, не Lin

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

А по поводу отдать квант времени - это всего лишь одна ассемблерная команда SWI. Т.е. переключает контекст вместо (и наравне) с таймером. А уж если таймер вмешивается после SWI, то он просто не переключает на новую задачу. Ибо знает, что за мгновенье до этого это сделано другим способом.

Сам планировщик, который работает в прерывании (Сишный) занимает примерно 4-5 операторов Си.

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

http://martin.hinner.info/ARM-Microcontrol...er-HOWTO-7.html

Вот я с этой статьи начинал. Чутка добавил, чутка убавил.

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

Посмотрите AVR учебный курс на http://easyelectronics.ru/
Кажется какой-то простенький планировщик там был(видел краем глаза, деталей не помню).

И где тут вытесняющая многозадачность?

А как же setjmp/longjmp ?

Переключатель задач по таймеру прерывает процесс. Участие в этом действии со стороны процесса - не требуется.
Это определение вытесняющей многозадачности.

Хотя процесс и имеет возможность прервать сам себя... И это не противоречит вытесняющей многозадачности.

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

---
Что такое setjump узнал только сейчас. (Я Си специально не изучал никогда).
Может и можно. Но по-моему быстрее скопипастить два десятка ассемблерных строк переключателя, чем разбираться в том, что именно на самом деле делают упоминаемые функции Си.
--
В том плане, что к примеру для АРМ там надо ж сохранять контекст в режиме работы процесса...Т.е. setjump должен из режима прерывания сохранить контекст другого режима (режима задачи).
Что-то сомневаюсь, что он это делает. Ибо такая функция будучи универсальной должна как-то разбираться в конкретных режима процессора... Что все сильно усложняет...
А меня, лично, сложное всегда сильно пугает.

система должна принимать данные от АЦП, обробатывать их блоками, передавать по UART (по 3-м сразу и независимо), весли лог работы на SD-карту, работать с часами реального времени....
вобщем пример класический)

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

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

Мда... На каком контроллере? Есть конкретные результаты сравнения? Можно ли с ними ознакомиться?

Вполне тянет на минимум кандидатскую диссертацию. Ваши интересы не затрону?

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

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

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

удачи вам
(круглый)

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

а вообще вы нечто вроде этого имели ввиду?:

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

спасибо.
говоря о приоритетах прерываний в MSP430 вы скорее всего имели ввиду аппаратные прерывания, но как быть, если мне нужно отреагировать на программное событие (накопился блок данных АЦП например). С "суперлупой" это организуется циклическим опросом флагов.

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

Или все отладку хотят выдать через уарт.... Ну и так далее.

Вот мне дяденька добрй дал задание. Сделай, говорит, маленькую радиостанцию, каналы, то, се. (Вроде как задачка для авр...). А заодно, говорит, присобачь для комплекта ФМ-радио, МР3 плеер, фоторамку. И чтоб цветно было и 3D. И вот громоздить суперпупер лупы - даже предположить опасаюсь...

а я в очередь ставлю через шаг. 1 3 5 7. и у меня 3 приоритета.

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

Катит только для архитектур с одним SP. Для ARM7, например, требует внешних костылей для сохранения User SP. Для CM3 - только в режиме с одним стеком.

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

Да вы сначала реализуйте просто по очереди.
Тут все просто как в зоопарке.

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

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

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

хидер



соурсе




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

спасибо большущее, как я и думал, здесь кольцевая очеред, но не совсем понятно где задаётся приоритет и как читается?

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

Таким образом, если возникает событие, требующее обработки немедленно (реалтайм), то оно в любом случае ждёт своей очереди, не прерывая обрабатываемое в данный момент событие.
Это вытеснение?

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

понятно, вобщем кольцевая очередь низкоприоритетных задач + прерывания.
Просто вы писали обозначая приоритеты цифрами (0,1,2...) вот я и подумал что это както задаётся программно.
Теперь ясно.
Получается что необходимо разрешать прервания в прерываниях.
но например для MSP430 :
Микроконтроллеры семейства MSP430 имеют особенность – когда вложенные прерывания разрешены, любое прерывание, возникающее во время выполнения одной подпрограммы обработки прерывания, вызовет выполнение своей подпрограммы, несмотря на приоритеты прерываний.

Получается для MSP430 такое провернуть не удастся.

Спасибо за пожелание удачи, но простите, немного непонятно - вы против ОС или планировщиков? Планировщик был "изобретен" мной 2 месяца назад в силу незнания что они уже изобретены, когда потребовалось условно говоря, варить борщ, смотреть телек, укладывать ребенка, играть одновременно 10 партий в шахматы на 10 досках и иметь возможность впустить гостя, позвонившего в дверь внезапно и потом ещё уделять ему время - и все это асинхронно и без потери реального времени! Я был очень доволен, когда придумал как это осуществить. Без ОС, без вытеснения, без почтовых ящиков, просто по крестьянски, но с реальным временем. А тут ваше такое мнение....

Во-первых: вытесняющая многозадачность -- стек на каждый поток исполнения. Возможность его переполнения.

Во-вторых: оно Вам зачем надо? чтобы параллельно несколько потоков выполнялось? А наверно вы хотите чтоб одни потоки работали бесконечно а другие их вытесняли время от времени? Тогда вам и приоритет поди понадобиться? Дак почему бы не взять простейшую ОС? что сложного то -- несколько доп файлов в проект и всё.

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


Очень такой большой плюс. :-)

раскройте секрет реализации подробнее. Очень интересно.



а как же ChibiOS? там "чистый" С

)) возможно я, что то не понимаю в данной терминологии но имхо - несовместимо.

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

т.е. в осадке имеем только
1) я сделал и жалко выкидывать, тем более модняво
2) теперь я могу абстрагироваться от других мелких под задачек...ура!!! ура!!! ура!!! но надо не забыть что шина разделяема, что юсарт разделяем, что..ой чёрт дай ка я заведу мьютексы, семафорчики и критические секции на всяк случай...ура!!! ура!!! ура!!! а вот мне нужно чётко нарезать по 1 микросекунде, ой блин тут надо приоритеты явно заводить...ну или там блокировку или не вытеснять... ура..ура..ура...


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

Да простит меня MrYuran, который забадался уже читать мои наблюдения по поводу прототредов
Если дополнить прототредовский контекст 1 байтом, содержащим информацию, например, о подписке треда на некоторое событие, то из обработчика этого события можно вызывать только те треды, которые его ожидают. Итого, вся вытеснялка у нас базируется на физических источниках событий-прерываниях. Реалтаймовые костыли налицо.

А как же папочка os/ports там и ассемблерные файлы имеются.

всё же вы говорили о неприменимости C.

Сорри, но почему не получится?
Грубо говоря, нам необходимо в прерывании манипулировать значением program counter.
Это, мне кажется, можно сделать и на си...

А как вы push-pop регистрового контекста из си реализуете?

Например, IAR AVR использует раздельные стеки возвратов и данных.

А в другом компиляторе общий стек.
Вопрос не в организации стека.
Как вы будете читать и писать регистры СОЗУ, которые, кстати говоря, могут и не мапиться в ОЗУ.