Вопрос тем, кому посчастливилось писать планировщик, Разблокировка задач по списку и вообще по теме Опции

[greezol]

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

[Olej]

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

Варианты

1. Задача заблокировалась на семафор (для простоты семафор может гм иметь только одна задача, остальные ждут, для простоты семафор может гм иметь только одна задача). Сама в списке semaphore_blocked, в TCB - адрес семафора. Планировщик через TCB выходит на семафор, в семафоре - начало списка ожидающих (первый TCB). Предположим, семафор свободен. Отдаем его самой приоритетной задаче, саму задачу в список READY и убираем из списка ожидания самого семафора. Перейти к следующей задаче в списке semaphor_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-...);
- к какому году вы планируете показать свой "эффективный код"?

[greezol]

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

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

[AlexandrY]

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

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

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