Пописываю небольшую вытесняющую ось для небольших проектов и в учебных целях (AVR-ARM), с минимальным сервисом и желательно побыстрее (пока общие fifo буфера, мутексы/семафоры, очереди сообщений из указателей на тело собщения, сигналы, bottom halfes).

Маленький интро из соображений, с удовольствием принимаются поправки:

1. Можно поместить задачу в список suspended_list, а потом проверять задачу на причину блокировки с помощью регистра состояния в TCB, но получится нагромождение switch() case. Решил поэтому разбить на несколько списков с однородными причинами блокировки (по delay(), по семафору, send-, receive- блокировка (как в qnx), и т.д., а также еще по одному виду списка на каждую причину, но с таймаутом), с целью максимально избавиться от многочисленных проверок условий. задача может находиться одновременно только в одном списке. также в TCB указан адрес ресурса, по которому блокирована задача и 2 пары указателей prev-next - соотв. для расположения в двусторонних списках: принадлежности к списку причин блокировок и списку принадлежности к ресурсу (очередь ожидания ресурса).

2. Из READY-списка в список ожидания задачу переносит непосредственно системная функция (с последующей отдачей управления ядру), обратно - планировщик. Например: send() - поставили в очередь сообщение другой задаче, задали что надо в TCB, и ушли в send-блокировку. перед этим добавили системное событие в очередь ядру - "послано сообщение такой-то задаче" (чтоб планировщик проверяя системные события вывел последнюю из receive-блокировки). Можно конечно "просить" ядро, чтобы он переместил отправителя в send_blocked список, но зачем нагромождать промежуточные ступени?


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

Варианты

1. Задача заблокировалась на семафор (для простоты семафор может гм иметь только одна задача, остальные ждут, но мутекс нецелесообразен т.к. ресурс удерживается долго). Сама в списке semaphore_blocked, в TCB - адрес семафора. Планировщик через TCB выходит на семафор, в семафоре - начало списка ожидающих (первый TCB). Предположим, семафор свободен. Отдаем его самой приоритетной задаче, саму задачу в список READY и убираем из списка ожидания самого семафора. Перейти к следующей задаче в списке semaphor_blocked. Если попадаем на тот же самый семафор, он уже занят.

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

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



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

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

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

Понимаю, конечно, что вопрос пустой, но все-таки задам: а чем какая-нибудь готовая ось не устраивает?

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

Всё не совсем так просто:
- все IPC-механизмы (семафоры, мютексы, сигналы и др.) - имеют строго предписанную семантику, а не "как хочу - так и верчу"...
- мне кажется (это только IMHO), что вы не до конца чётко представляете семантику каждого из механизмов....
- "для простоты семафор может гм иметь только одна задача"(с) - задача (процесс, поток) - не может "иметь" семафор, у семафора нет захватившего его владельца, что принципиально отличает семафор от мютекса, который всегда имеет владельца...
- "для простоты семафор может гм иметь только одна задача" - при чём здесь "долго" применительно к выбору? мютекс, кстати, по всей своей логике и семантике - гораздо более "лёгкий" механизм, по сравнению с семафором...
- "Предположим, семафор свободен. Отдаем его самой приоритетной задаче," - то же самое: семафор не бывает свободен или занят, даже если он бинарный, на нём только выполняются P/W операции, которые ещё Э.Дейкстрой строго регламентированы... и уж тем более не может быть отдан задаче - N-я задача может заблокироваться на семафоре, но разблокировать её (задачу!) может любая из других N-1, ... чего никогда нельзя сделать на мютексе.
- ещё куда более сложные детали будут на сигналах (момент и порядок доставки и т.д.) ... по крайней мере, если это сигналы POSIX;
- я бы советовал очень детально свериться с POSIX 1003.b Rationale и POSIX, чтобы следовать поведению IPC...
- конечно, можно сделать IPC-прмитивы: my-semaphore, my-mutex, my-signal etc. .... Но тогда они и никому кроме вас нужны не будут.

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

P.P.S. вот здесь:
http://www.qnxclub.net/files/articles/invers/invers.html
- есть, очень старый правда вариант, текста, который только "намечает" эти пункты, может чем полезен может быть ... + POSIX Rationale + ... QNX 6.3 документация (открытая!) - там на частных примерах, но всё очень понятно.



Может
В QNX 6.x POSIX IPC механизмы реализованы в высшей степени эффективно, независимо от 10-ка платформ ею поддерживамых.
Это достигается:
- все механизмы синхронизации являются непосредственно объектами микроядра ("ядра" - это 1-й +, а "микро" - это 2-й +, т.к. в микроядре ничего кроме объектов синхронизации и потоков - и нет);
- этот механизм в микроядре обкатывается почти без изменений с 1984г. (QNX 1 - QNX2 - QNX4 - QNX6-...);
- к какому году вы планируете показать свой "эффективный код"?

А что, где то можно посмотреть исходники ядра QNX?

Много зависит от того хотите лы вы сделать из нее RTOS.
Вроде бы у вас очевидная задача экономии памяти, но вы почему-то придумываете много списков.
Каждый список требует резервирования памяти, резервировать конечно будете предлагать юзерам с запасом. Происходит перерасход, однако.
Далее необоснованное как кажется разделение на мьютексы, семафоры, таймауты и т.д.
У всех них одна суть - это события, а значит и список для всего этого хозяйства должен быть один.
В этом списке находится структуры описывающие события с некоторыми специфическими полями для детализации свойственной разным типам событий, эти поля вносят, конечно, небольшую избыточность, но не бОльшую чем доп. списки с неясной емкостью.
Итого имеем всего два списка: список TCB и список созданных событий.
У каждого события не один хозяин, а несколько - это задачи ожидающие события. (все это относится и к мьютексам, семафорам и проч.)
И теперь главное, в хорошей RTOS работа планировшика не должна зависеть от количества задач и событий созданных в системе, т.е. в планировщике не должен использоваться цикл для просмотра каких либо списков. При заходе в планировщик одним проходом вычисляется задача с максимальным приоритетом и ей сразу же передается управление. Так же с событиями, при заходе в кукую-либо сервисную функцию RTOS, например OSMboxPend или OSMutexPost за один проход вычисляется один из хозяев события с максимальмальным приоритетом и ему сразу же передается управление.
Цикл остается только один, когда в процедуре обслуживания прерывания просматривается весь список TCB на предмет декремента таймаутов. И в случает истечения какого либо корректируется указатель на задачу готовую к выполнению и при этом с максимальным приоритетом.

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

Естественно, исходники ядра QNX посмотреть негде, по одной простой причине ... как бы лучше это сказать по-русски - что у QNX просто нет ядра, у него есть микроядро, размером в несколько десятков Кб, и всё - всё остальное в системе не имеет касательства к ядерным механизмам.
А всё, что вам понравилось в цитируемом фрагменте (я его для краткости опустил), и ещё многое другое - так для этого абсолютно не нужно смотреть исходники микроядра - "курите RFM"© : POSIX 1003.b / POSIX Rationale / RTFM QNX (именно документацию, а не какие-то коды).

Сильно не пинайте если что:

2Olej:

Про семафоры:

у меня они да, бинарные. Я думал что мутекс работает как spin-lock в Linux (там даже рекомендация не захватывать мутекс более, чем на 1-2 time-slice), тогда как задача, попросившая семафор может надолго леч в спячку.

Извините не удержался, из "Linux Kernel Development Second Edition"
The fact that a contended spin lock causes threads to spin (essentially wasting processor time) while waiting for the lock to become available is important. This behavior is the point of the spin lock. It is not wise to hold a spin lock for a long time. This is the nature of the spin lock: a lightweight single-holder lock that should be held for short durations


>семафор не бывает свободен или занят, даже если он бинарный, на нём только выполняются P/W >операции, которые ещё Э.Дейкстрой строго регламентированы...

Semaphores in Linux are sleeping locks - может это просто не соответствует real-time осям?
Если симафор бинарный - можно тогда (ну неформально) сказать что у него есть владелец (один), а не несколько, как в небинарных семафорах? ну не владелец, а совладелец

>В QNX 6.x POSIX IPC механизмы реализованы в высшей степени эффективно, независимо от 10-ка ?>платформ ею поддерживамых.

Думаю, для AVR даже QNX будет великоват. У разных архитектур и наверное компиляторов (я только IAR правда знаю) есть в чем то общие, а в чем то разные рекомендации по написанию кода, хотя наверное большинство работы делает компилятор, но рекомендации не зря есть.


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

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

> я бы советовал очень детально свериться с POSIX 1003.b Rationale и POSIX, чтобы следовать ?>поведению IPC...

спасибо, почитаю

============================

2AlexandrY:

>Мого зависит от того хотите лы вы сделать из нее RTOS

Точно так, да

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

Юзер будет один, но это неважно. Я не придумываю списков, для которых требуется резервировать память. Пусть будет двуторонний список - TCB* next и TCB* previous в TCB задачи, соответственно расходы по увеличению и уменьшению списка будут иметь только временной характер. Конечно есть только одна переменная ядра на каждый список - указывает на начало списка (первый TCB), но одна переменная это не куча переменных.


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

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

>эти поля вносят, конечно, небольшую избыточность, но не бОльшую чем доп. списки с неясной >емкостью

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


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

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

может я не совсем правильно понял - а если эта задача хочет но не может? к тому же тогда нужна сортировка "общего" (да и любого) списка по приоритету, а это как ни крути (выбор места в списке для помещения в него, либо обычная сотрировка потом) потребует while{}.


>Так же с событиями, при заходе в кукую-либо сервисную функцию RTOS, например OSMboxPend или >OSMutexPost за один проход вычисляется один из хозяев события с максимальмальным приоритетом и >ему сразу же передается управление.

не вопрос, тут сразу имеем задачу, на статус котоорй влияет системный вызов. но если такая задача не одна? одна recieve-блокированная получила сообщений, а другая, более приоритетная, получила ресурс. смотреть то всех придется; по крайней мере, кто затронул IPC (ну плюс delay() и т.п.)

2 Olej, в дополнение к моему посту выше:

из Введение в QNX, Роб Кёртен:

"Простые" (бинарные) семафоры работают точно так же, как и мутексы.

В этом месте Р.Кёртен упрощает , поверьте:
http://www.books.ru/shop/books/357604
Проверено

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

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

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

В "хорошей" это с планировщиком а-ля uCOS типа 32 задачи и у каждой свой приоритет? Спасибо не надо

А как-же критерий "хорошести" когда от числа задач "работа планировщика не зависит"?
И при каком количестве задач прокрутка кучи таймерных счетчиков станет накладнее, чем обслуживание очереди к таймеру?

Постановка задачи некорректна - ARM и AVR слишком разные для "универсального", "простого" и
"оптимального" решения. Практически Вы будете закладываться на слабейшего - ARM7 жалко
На него и так тянут или с восьмибитников все подряд, или уж Линуксообразных монстриков.

Ха, молодец, раскусил. Да, я описывал механизм работы uCOS.
Только там нынче поддерживается 65536 задач и при этом ничего не изменилось в планировщике принципиально.
А Time Slice делается в uCOS довольно просто с помощью одной дополнительной высокоприоритетной задачи. На сайте Infineon в одном аппноте, было разжевано как это делается.

Ну а 'Ха' чего? Там действительно лет двадцать тому впервые был заложен (похоже тогда в студенческой работе) знакомый ныне до боли механизм планировки. Немерянное количество OS наследовали этот подход. Имеют право.

Да к сожалению не изменилось в планировщике ничего контроллеры растут а в планировшике за счет разрядности подняли число задач и все

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

Уже в нескольких ветках вы ссылаетесь на эту "бескомпромисность" одних ОС (FreeRTOS,..?) относительно других (TNKernel, uCOS,...?), как на важнейший критерий вашего выбора оси. Не могли бы вы пояснить, что имеете в виду.

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



Блин, для списоков не нужно каких-то массивов.




Правильно я понял(упрощенно): структура "получено сообщение", в ней - список задач, получивших сообщения,
планировщик их смотрит и разблокирует если они receive-блокированные

А можно привести пример системы, если она с открытыми исходниками? Чтоб поподробнее, что представляет эта event структура?






Для начала берутся разные типы данных для порта (примерно как portCHAR, portXXX во freertos-e)
Сначала хочу отработать механизм на слабейшем, а переписывать - для ARM7.. Еще вопрос, как себя компилятор будет вести может и не надо переписывать. Вообще это все сейчас пока не так важно.

Для ясности:
1. не в нескольких ветках, а кроме этой только в одной по TN-Kernel
2. речь шла более конкретно - о шедулерах.

Так уж вышло, что еще с 90x годов (практически доинтернетовской эпохи) приходилось писать "свои" системки гордясь большей частью экономией байтов и тактов и обходя вылезающие проблемы многочисленными наслоениями. Когда почти два года назад в качестве новой базы выбрал ARM линейку контроллеров, то решил (и не пожалел!) не продолжать практику перетаскивания своего кода, а взять готовую базу для RTOS и дорабатывать уже ее.
Критериями выбора исходя из предыдущего разнообразного опыта на тот момент были -
Поддержка задач с одинаковыми приоритетами. Возможность динамического создания и удаления задач, что сразу тянет за собой автоматически и третье условие - наличие менеджера памяти.
Не хотелось и ограничивать число задач. Приятным бонусом в последствии явилось появление на выбранной платформе возможности запускать часть задач в невытесняющем режиме.

Речь вел не проблемах портирования а о соразмерности системы используемому контроллеру
Ну это как если движок созданный для, например Жигулей простым увеличением его геометрических размеров использовать для автомобиля класса, например, Ягуара. Ездить-то он будет, но ведь "что-то", согласитесь, не так .
Портируется-то легко...

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

Един да един-это два, а несколько-это более одного.


Так этим условиям(кроме последнего?) удовлетворяют и FreeRTOS, и TNKernel. Поэтому, прежде чем начать более глубоко разбираться с обеими(или сразу выбрать одну), интересно мнение того, кто уже копал обе. Чем не устроил шедулер TNKernel и понравился FreeRTOS? В предыдущих ветках вы часто их сравнивали(более двух раз ), но как-то невнятно(для меня ).

Похоже перехвалил, о механизмах планировки еще разговора не было.
Идет пока речь только о реализации механизмов синхронизации.
И они в действительности очень разные.
В ThreadX, например реально сделано более топорно и именно на основе нескольких разнородных списков для семафоров отдельно, для очередей отдельно и т.д.
Кстати это в ThreadX всего 32 приоритета.
Но операционка тем не менее для ARM-ов очень популярная.
В ThreadX память для элементов списка выделяется самим юзером, в отличие от uCOS. И такая практика на мой взгляд плохая. Одна ошибка в процедуре выделения-восстановления памяти в одной задаче и посыпется вся Ось. В uCOS такого не будет.

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

Есть еще более популярные решения - "а зачем вообще эта операционка". Ну и что?

Немеряно!

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

TNKernel 2.x весьма привлекательна, о чем я уже ранее писал. Но FreeRTOS появилась в пригодном ( для меня ) к стартовому использованию варианте раньше, что и обусловило выбор. На данный момент вопросы перехода на что-то другое не рассматриваются ввиду больших собственных доработок и наработок, ну и отсутствия сколь-нибудь обьективной необходимости. Все устраивает

В кодах 2.83, 2.84 поддерживается до 256 приоритетов = мах числу задач.
В коде 2.52 максимальное число приоритетов = 64. (за вычетом Idle и если используется,
Stat процессов, 255 и 63 или 254 и 62 соответственно)

Конечно, можно увеличить priority bitmap до размера 8KB и переменную группы
соответственно, чтобы отыскать младший установленный бит в 65536-битовом
числе.



TS в системе где нет двух процессов с равным приоритетом? Проще (и логичнее)
переделать алгоритм планировщика uCOS, чем моделировать тоже самое из уровня
приложения...

--
Андрей