Пописываю небольшую вытесняющую ось для небольших проектов и в учебных целях (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, вместо этого регистрировать в ядре все семафоры и просто проходиться по ним, в случае необходимости улаживая все спорные вопросы между, как сейчас модно говорить, партнерами.

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

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

Сообщение отредактировал greezol - Feb 12 2007, 01:06

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

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

Всё не совсем так просто:
- все 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() и т.п.)

Сообщение отредактировал greezol - Feb 12 2007, 23:07

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 наследовали этот подход. Имеют право.

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

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