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

[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

[AlexandrY]

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

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

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