Какие структуры данных используются в операционных системах РВ для хранения информации о свободных блоках в куче?

Куча — есть длинный отрезок адресов памяти, поделенный на подряд идущие блоки различных размеров.

Блоки бывают свободные и занятые. Для возможности выделения памяти путем повторного использования свободного блока (без дорогостоящего увеличения кучи в целом — требует системного вызова) в том или ином виде нужен список свободных блоков.

Для сокращения списка свободных блоков с целью уменьшения времени его обхода всегда имеет смысл сливать 2 или 3 подряд идущих свободных блока в один. Если свободен последующий блок, то его легко найти, отступив вперед на размер освобождаемого блока. С предыдущим блоком все сложнее, и потому имеет смысл хранить размер предыдущего блока (для его поиска) в заголовке любого блока.

Список свободных блоков может быть организован по-разному, и от его организации прямо зависит производительность кучи. Дело в том, что главное время в операции выделения тратится именно на поиск в этом списке.

Очень хорошей реализацией является несколько списков, каждый для своего размера. Это позволяет быстро проигнорировать заведомо слишком маленькие свободные блоки целыми списками, без проверки каждого персонально.

Какая стратегия выбора свободного блока памяти в куче используется в ОС QNX Neutrino?

Выбирается первый свободный подходящий блок памяти в куче.