Ready List 자료구조 분석 — Linked List·Bitmap·O(1) Scheduler

#한 줄 요약

“Ready list는 스케줄러의 거의 전부” — 다음에 실행할 task를 얼마나 빨리 찾느냐가 곧 RTOS의 latency 한계입니다.

#스케줄러가 푸는 문제

매 tick마다, 매 system call마다, 매 ISR-exit마다 스케줄러가 같은 질문을 던집니다.

“지금 ready 상태인 task 중 가장 높은 priority는 누구인가?”

이 질문에 대한 답이 일정한 시간 안에 나오지 않으면 RTOS의 determinism은 무너집니다. 그래서 ready list 자료구조는 다음 세 조건을 모두 만족해야 합니다.

• 다음 task 찾기가 O(1) 또는 O(log N)
• task 삽입·삭제도 O(1)
• 임베디드답게 메모리가 작아야 함

이 조건을 어떻게 만족하느냐로 RTOS 마다 색깔이 나뉩니다.

#가장 단순한 시도 — 정렬된 단일 list

1
List_t xReadyList;  // priority 내림차순 정렬
2

3
// 다음 task — head
4
TCB_t *next = listGET_OWNER_OF_HEAD_ENTRY(&xReadyList);
5

6
// insert — 적절한 위치 찾기
7
for (item = head; item != end; item = item->next) {
8
    if (item->priority < new_task->priority) break;
9
}

찾기는 O(1)이지만 삽입이 O(N) 입니다. block/unblock이 빈번한 RTOS에서는 받아들이기 어렵습니다.

#FreeRTOS 기본 — Array of Lists (Generic)

각 priority 별로 별도 doubly-linked list를 둡니다.

1
List_t pxReadyTasksLists[configMAX_PRIORITIES];

32 priority면 list 32개입니다. 같은 priority 안에서는 round-robin이 자연스럽게 됩니다.

#다음 task 찾기

1
// configUSE_PORT_OPTIMISED_TASK_SELECTION = 0
2
UBaseType_t uxTopReadyPriority = 0;
3
while (listLIST_IS_EMPTY(&pxReadyTasksLists[uxTopReadyPriority])) {
4
    if (++uxTopReadyPriority >= configMAX_PRIORITIES) break;
5
}
6
pxCurrentTCB = listGET_OWNER_OF_NEXT_ENTRY(
7
    &pxReadyTasksLists[uxTopReadyPriority]);

위에서부터 비어있지 않은 list를 찾을 때까지 순회합니다. O(P) — priority 수에 비례합니다. 32 priority면 최악의 경우 32회 비교가 필요합니다.

#Insert / Remove

1
vListInsert(&pxReadyTasksLists[priority], &task->xStateListItem);
2
uxListRemove(&task->xStateListItem);

doubly-linked list라 양쪽 다 O(1)입니다.

이 generic 방식은 어떤 CPU에서도 동작하는 안전한 선택입니다. Cortex-M0처럼 비트 연산이 빈약한 코어가 그 대상입니다.

#FreeRTOS 최적화 — Bitmap + CLZ

configUSE_PORT_OPTIMISED_TASK_SELECTION = 1로 켜면 Cortex-M3 이상에서 진짜 O(1) 으로 바뀝니다.

1
volatile UBaseType_t uxTopReadyPriority;  // bit N = priority N에 ready task 있음
2
List_t pxReadyTasksLists[configMAX_PRIORITIES];

uxTopReadyPriority는 32 bit bitmap입니다. priority 5에 task가 하나라도 있으면 bit 5가 켜집니다.

Ready list의 자료구조를 그림으로 보면 이렇습니다. priority bitmap의 set bit 위치가 곧 list array의 index가 되고, CLZ 한 명령으로 가장 높은 priority를 찾습니다.

#CLZ — 1 cycle로 가장 높은 priority 찾기

1
// ARM CLZ (Count Leading Zeros) intrinsic
2
unsigned int uxTopPriority = (31UL - __clz(uxTopReadyPriority));
3
pxCurrentTCB = listGET_OWNER_OF_NEXT_ENTRY(
4
    &pxReadyTasksLists[uxTopPriority]);

__clz(x)는 상위 비트부터 0의 개수를 셉니다. ARMv7-M 이상의 CLZ 명령은 1 cycle입니다. 32 priority도 1 cycle에 답이 나옵니다.

생성되는 어셈블리는 두 줄짜리입니다.

1
clz r1, r0          @ r1 = leading zero count of bitmap
2
rsb r1, r1, #31     @ r1 = 31 - r1

#bitmap 유지

Insert와 remove 때 bitmap을 함께 갱신합니다.

1
// Insert — 비어있던 list라면 bit set
2
portRECORD_READY_PRIORITY(priority, uxTopReadyPriority);
3
vListInsertEnd(&pxReadyTasksLists[priority], item);
4

5
// Remove — list가 비면 bit clear
6
uxListRemove(item);
7
if (listLIST_IS_EMPTY(&pxReadyTasksLists[priority])) {
8
    portRESET_READY_PRIORITY(priority, uxTopReadyPriority);
9
}

portRECORD_READY_PRIORITY는 보통 uxTopReadyPriority |= (1UL << priority) 한 줄, reset도 &= ~(1UL << priority) 한 줄입니다. 단일 명령으로 끝납니다.

💡 CLZ는 ARMv7-M (Cortex-M3/M4/M7), ARMv8-M부터 있습니다. Cortex-M0/M0+ (ARMv6-M)에는 없어서 자동으로 generic 모드로 떨어집니다. 이 차이를 모르고 M0에서 최적화를 켜면 빌드가 깨집니다.

#uC/OS-III — 8 × 8 Bitmap + Lookup Table

CLZ 명령이 없던 시절의 우아한 답입니다. 256 priority를 2단 bitmap으로 다룹니다.

1
CPU_INT08U  OSPrioRdyGrp;                    // group bit (1 byte)
2
CPU_INT08U  OSPrioTbl[OS_CFG_PRIO_MAX / 8];  // detail (32 byte for 256 prio)

priority p를 group = p / 8, bit = p % 8로 나눕니다. group에 ready task가 있으면 OSPrioRdyGrp의 해당 bit가 켜집니다.

#Lookup Table

1
// 8-bit pattern → 가장 낮은 bit 위치
2
static const CPU_INT08U OSUnMapTbl[256] = {
3
    0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
4
    /* ... 256 entries ... */
5
};
6

7
CPU_INT08U group = OSUnMapTbl[OSPrioRdyGrp];
8
CPU_INT08U bit   = OSUnMapTbl[OSPrioTbl[group]];
9
CPU_INT08U prio  = (group << 3) + bit;

LUT 두 번 lookup으로 priority가 나옵니다. 8-bit MCU에서도 진정한 O(1)입니다. 256 byte LUT가 필요하지만, ROM에 두면 RAM은 거의 안 씁니다.

#Linux CFS — Red-Black Tree

Linux Completely Fair Scheduler는 priority 대신 virtual runtime을 기준으로 합니다. RB tree에 task들을 vruntime 순서로 넣고, 가장 왼쪽 노드가 다음 task입니다.

1
struct cfs_rq {
2
    struct rb_root_cached tasks_timeline;
3
    struct sched_entity *curr;
4
};
5

6
// 다음 task — cached leftmost
7
se = rb_first_cached(&cfs_rq->tasks_timeline);
8

9
// insert / remove
10
__enqueue_entity(cfs_rq, se);  // O(log N)
11
__dequeue_entity(cfs_rq, se);  // O(log N)

찾기는 cache 덕에 O(1), 삽입·삭제는 O(log N)입니다. task 1000개라도 약 10 비교면 끝납니다.

CFS는 fair share를 추구하므로 RTOS와 목적이 다릅니다. 임베디드 RTOS가 priority-O(1)을 고집하는 이유는 throughput이 아니라 latency가 목표이기 때문입니다.

#한 표로 비교

임베디드 RTOS는 거의 예외 없이 bitmap + linked-list-per-priority 조합으로 수렴합니다.

#Wait list — Ready list와 짝

ready list만 있으면 RTOS는 동작하지 않습니다. semaphore·mutex·queue 각자가 대기 중 task를 보관하는 wait list를 가집니다.

1
typedef struct {
2
    int count;
3
    List_t xTasksWaitingToTake;   // priority-sorted
4
} Semaphore_t;
5

6
// 자원 해제 시 — 가장 높은 priority부터 wake
7
TCB_t *next = listGET_OWNER_OF_HEAD_ENTRY(&xTasksWaitingToTake);
8
move_to_ready_list(next);

wait list는 priority-sorted로 두는 게 일반적입니다. wake 시 head만 보면 가장 우선해야 할 task가 즉시 나옵니다.

#TCB가 두 list에 동시 link

여기서 흥미로운 디테일이 있습니다. 한 task는 동시에 ready list와 wait list 양쪽에 들어가야 할 때가 있습니다.

1
typedef struct {
2
    /* ... */
3
    ListItem_t xStateListItem;    // ready / blocked / suspended 중 하나
4
    ListItem_t xEventListItem;    // 특정 이벤트 wait list
5
} tskTCB;

FreeRTOS는 TCB에 두 개의 ListItem을 둡니다. 하나는 상태 list용, 다른 하나는 이벤트 list용입니다. 이렇게 하면 timeout이 걸린 semaphore wait의 경우 delayed list와 wait list 양쪽에 자연스럽게 들어갑니다. 둘 중 어느 쪽에서 먼저 깨어나든 일관된 처리가 가능합니다.

#Delayed list — Timeout이 있는 task

vTaskDelay()나 timeout 있는 xSemaphoreTake()를 호출한 task는 delayed list로 갑니다. tick마다 expired task를 ready로 옮깁니다.

1
static List_t xDelayedTaskList1;   // wake-up tick 오름차순
2
static List_t xDelayedTaskList2;   // tick overflow 대비 swap
3

4
// tick ISR 안
5
while (xTickCount >= listGET_ITEM_VALUE_OF_HEAD_ENTRY(&xDelayedTaskList1)) {
6
    TCB_t *t = listGET_OWNER_OF_HEAD_ENTRY(&xDelayedTaskList1);
7
    uxListRemove(&t->xStateListItem);
8
    move_to_ready_list(t);
9
}

list 두 개를 두는 이유는 tick counter wrap-around 때문입니다. wrap이 일어나는 순간 두 list를 교환합니다. 자세한 동작은 2-08편에서 다룹니다.

#자주 하는 실수

⚠️ priority를 32단계 다 쓰기

대부분의 시스템은 5~10단계로 충분합니다. priority를 잘게 나눌수록 메모리도 늘고 우선순위 설계도 어려워집니다. 같은 priority의 task는 round-robin으로 도니 합쳐도 큰 문제가 없습니다.

⚠️ wait list 순서를 가정

priority-sorted라고 가정했는데 실제 구현이 FIFO면 가장 우선해야 할 task가 맨 뒤에 있을 수 있습니다. RTOS 별로 정책이 다르니 문서 확인이 필요합니다.

⚠️ Generic mode와 Opt mode를 혼동

Cortex-M0에서 configUSE_PORT_OPTIMISED_TASK_SELECTION = 1로 두면 CLZ가 없어 빌드가 깨집니다. 반대로 Cortex-M4에서 generic mode로 두면 *공짜 O(1)*을 버리는 셈입니다.

#정리

• Ready list는 priority 별 doubly-linked list 배열이 사실상 표준입니다.
• Bitmap + CLZ가 Cortex-M3+ 에서 O(1) 스케줄러를 만듭니다. 단 두 명령이면 답이 나옵니다.
• uC/OS-III의 8×8 bitmap + LUT는 CLZ가 없는 시대의 우아한 답입니다.
• Linux CFS는 RB tree + vruntime으로 fairness를 추구합니다. RTOS와는 목표 자체가 다릅니다.
• TCB가 두 ListItem을 가져 ready list와 wait list 양쪽에 동시에 link 됩니다. 임베디드 linked-list의 트릭입니다.

다음 편은 Blocked List 자료구조 — timeout 정렬과 delta list 기법을 다룹니다.

#관련 항목

• 1-02: Task와 Thread 개념
• 2-02: Blocked List 자료구조
• 2-03: Scheduler 알고리즘 구현
• 2-04: Context Switch 원리