RT scheduler: 우선순위별 대기열에서 다음 대상을 고르기

이 코드는 어떤 문제를 푸나요?

RT 스케줄러는 우선순위마다 대기열을 두고, 비어 있지 않은 우선순위를 비트맵으로 빠르게 찾습니다. 같은 우선순위 안에서는 큐의 순서가 중요합니다. 여기서는 pick_next_rt_entity 전체를 읽되 entity가 task 자체와 항상 같은 것은 아니라는 점도 함께 봅니다.

읽을 범위: v6.6 · kernel/sched/rt.c · pick_next_rt_entity 1769–1785행입니다. 아래에 이 범위의 원문과 각 줄의 설명을 실었습니다. 주제 전체의 흐름과 다른 경로는 기존 분석에서 함께 읽으실 수 있습니다.

먼저 알아둘 개념

우선순위 비트맵

대기열에 후보가 있는 우선순위를 비트로 요약합니다. 모든 큐를 순서대로 길게 탐색하지 않고 첫 유효 비트를 찾을 수 있습니다.

내부 우선순위 번호

이 배열에서는 작은 인덱스가 먼저 선택됩니다. 사용자가 보는 RT priority 숫자와 커널 내부 번호를 그대로 같은 방향으로 읽으면 혼동됩니다.

list_entry

연결 리스트 노드의 주소에서 그 노드를 멤버로 가진 구조체의 주소를 구하는 매크로입니다. 데이터를 복사해서 새 entity를 만드는 것이 아닙니다.

처음 읽을 때

우선순위 인덱스 3에 A·B, 인덱스 8에 C가 있다고 가정하세요. 비트맵에서 3을 고르고 그 큐의 첫 entity A를 찾는 두 단계를 그려 보세요.

더 깊이 살펴볼 때

FIFO와 RR의 차이는 이 선택 함수 한 곳에 다 들어 있지 않습니다. 같은 우선순위의 큐 순서를 언제 바꾸는지, RT 그룹에서는 entity를 따라 어떻게 내려가는지 함께 확인하셔야 합니다.

그림으로 보는 변화

GIF 재생1단계 · 멈춰 보기2단계 · 멈춰 보기3단계 · 멈춰 보기

1단계 고정

GIF 원본 열기

1. 비어 있지 않은 우선순위 찾기

sched_find_first_bit(bitmap)

화살표는 선택 순서입니다. 예시에서 작은 내부 인덱스가 더 높은 우선순위입니다.

2. 해당 우선순위 큐 선택

queue = array->queue + idx

배열 인덱스로 대기열 하나를 찾습니다. 모든 task를 한꺼번에 정렬하지 않습니다.

3. 맨 앞 entity 반환

list_entry(queue->next, ..., run_list)

화살표는 리스트 노드에서 포함 구조체로의 참조 변환입니다. 아직 CPU 레지스터 전환은 하지 않습니다.

pick_next_rt_entity를 한 줄씩 읽기

줄 번호는 v6.6 원문 기준입니다. 주석·빈 줄을 포함한 함수 전체를 먼저 보고, 그 아래에서 각 줄을 설명합니다.

static struct sched_rt_entity *pick_next_rt_entity(struct rt_rq *rt_rq)
{
	struct rt_prio_array *array = &rt_rq->active;
	struct sched_rt_entity *next = NULL;
	struct list_head *queue;
	int idx;

	idx = sched_find_first_bit(array->bitmap);
	BUG_ON(idx >= MAX_RT_PRIO);

	queue = array->queue + idx;
	if (SCHED_WARN_ON(list_empty(queue)))
		return NULL;
	next = list_entry(queue->next, struct sched_rt_entity, run_list);

	return next;
}

static struct sched_rt_entity *pick_next_rt_entity(struct rt_rq *rt_rq)

	struct rt_prio_array *array = &rt_rq->active;

	struct sched_rt_entity *next = NULL;

	struct list_head *queue;

	int idx;

	idx = sched_find_first_bit(array->bitmap);

	BUG_ON(idx >= MAX_RT_PRIO);

	queue = array->queue + idx;

	if (SCHED_WARN_ON(list_empty(queue)))

		return NULL;

	next = list_entry(queue->next, struct sched_rt_entity, run_list);

	return next;

함께 생각해 볼 질문

출처와 읽은 범위

Linux stable v6.6 · kernel/sched/rt.c

해당 버전 원본 파일 · 기존 코드 분석 · 설명 원고