Мне нравится treaps - за простую, все же эффективную идею наложить структуру "кучи" со случайным приоритетом над деревом двоичного поиска для балансировки его.
Я не работал с системами реального времени, но я знаю, что это и это . Я надеюсь, что это поможет или, по крайней мере, направит вас на верный путь.
Вопрос в том, действительно ли вам нужна жесткая RTOS?
Возможно, вы сможете сойдет с рук что-то вроде uClinux http://www.uclinux.org/
Если вы выбрали процессор, я предлагаю вам найти плату или комплект для разработки и использовать рекомендованную операционную среду. Включая средства разработки и ОС.
Если вам нужна коммерческая поддержка, посетите montavista.