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

[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]

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

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

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