|
Вопрос тем, кому посчастливилось писать планировщик, Разблокировка задач по списку и вообще по теме |
|
|
|
Feb 12 2007, 01:00
|
Участник

Группа: Участник
Сообщений: 33
Регистрация: 29-01-07
Пользователь №: 24 831

|
Пописываю небольшую вытесняющую ось для небольших проектов и в учебных целях (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
|
|
|
|
Сообщений в этой теме
greezol Вопрос тем, кому посчастливилось писать планировщик Feb 12 2007, 01:00 haker_fox Понимаю, конечно, что вопрос пустой, но все-таки з... Feb 12 2007, 03:43 greezol Цитата(haker_fox @ Feb 12 2007, 03:43) По... Feb 12 2007, 11:04 Olej Цитата(greezol @ Feb 12 2007, 02:00) Тепе... Feb 12 2007, 18:07 AlexandrY А что, где то можно посмотреть исходники ядра QNX?... Feb 12 2007, 19:31  Olej Цитата(AlexandrY @ Feb 12 2007, 20:31) А ... Feb 12 2007, 22:12 greezol Сильно не пинайте если что:
2Olej:
Про семафоры:... Feb 12 2007, 22:58  AlexandrY Не, а всетаки откуда память будете брать для списк... Feb 13 2007, 02:15   zltigo Цитата(AlexandrY @ Feb 13 2007, 01:15) Не... Feb 13 2007, 04:13    AlexandrY Ха, молодец, раскусил. Да, я описывал механизм раб... Feb 13 2007, 09:37     zltigo Цитата(AlexandrY @ Feb 13 2007, 08:37) Ха... Feb 13 2007, 11:00      AlexandrY Похоже перехвалил, о механизмах планировки еще раз... Feb 13 2007, 17:07       zltigo Цитата(AlexandrY @ Feb 13 2007, 16:07) Кс... Feb 13 2007, 17:55     AndrewN Цитата(AlexandrY @ Feb 13 2007, 09:37) [.... Mar 15 2007, 19:04 greezol 2 Olej, в дополнение к моему посту выше:
из Введе... Feb 12 2007, 23:17  Olej Цитата(greezol @ Feb 13 2007, 00:17) 2 Ol... Feb 13 2007, 00:26   greezol Цитата(Olej @ Feb 13 2007, 00:26) Цитата(... Feb 13 2007, 12:28    zltigo Цитата(greezol @ Feb 13 2007, 11:28) Для ... Feb 13 2007, 12:42 AlexandrY Много зависит от того хотите лы вы сделать из нее ... Feb 12 2007, 19:58 zltigo Цитата(greezol @ Feb 12 2007, 00:00) Попи... Feb 13 2007, 04:30 Andreas1 ЦитатаВопрос только в том, что лично мне хотелось-... Feb 13 2007, 11:18 zltigo Цитата(Andreas1 @ Feb 13 2007, 10:18) Уже... Feb 13 2007, 12:28  Andreas1 Цитата(zltigo @ Feb 13 2007, 12:28) 1. не... Feb 13 2007, 13:33   zltigo Цитата(Andreas1 @ Feb 13 2007, 12:33) Так... Feb 13 2007, 18:18
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0
|
|
|