런큐(Runqueue)란

• 런큐는 실행 대기 상태인 프로세스(TASK_RUNNING)와 CPU 코어에서 실
  행 중인 current 프로세스를 관리하는 스케줄링의 핵심 자료구조
• 프로세스가 CPU에서 실행되려면 먼저 런큐에 삽입됨
• 스케줄러는 런큐에 삽입된 프로세스 중에서 우선순위(vruntime)를 계산해
  서 다음 프로세스를 선택

실전 개발에서 런큐(Runqueue)란

• 시스템의 상태를 알 수 있는 가장 중요한 정보를 저장 (crash dump)
• 디버깅 과정에서 가장 많이 체크
• 가장 중요한 자료 구조 중 하나

런큐의 특징

• percpu 타입의 전역변수
• RT, CFS, Deadline 서브 런큐를 관리
• 실행 요청을 한 프로세스가 런큐에 삽입됨
• CPU를 점유하면서 실행 중인 current 프로세스를 관리

런큐(Runqueue) 자료구조

struct rq 구조체

https://elixir.bootlin.com/linux/v5.15.30/source/kernel/sched/sched.h
struct rq {
/* runqueue lock: */
raw_spinlock_t lock; // 런큐 자료구조를 변경할 때 사용되는 락
unsigned int nr_running; // 런큐에 삽입된 모든 프로세스 개수
...
u64 nr_switches; // 컨텍스트 스위칭을 수행한 횟수
...
struct cfs_rq cfs; // CFS 런큐
struct rt_rq rt; //RT(실시간) 런큐
...
/* 런큐에 있는 프로세스 중 TASK_UNINTERRUPTIBLE 상태의 프로세스 개수 */
unsigned long nr_uninterruptible;
/* 해당 런큐에서 CPU를 점유하면서 실행 중인 프로세스의 태스크 디스크립터 */
struct task_struct __rcu *curr;

런큐 접근 함수

cpu_rq() 함수

• percpu 타입의 runqueues 변수에서 CPU 오프셋을 적용한 주소에 접근

https://elixir.bootlin.com/linux/v5.15.30/source/kernel/sched/sched.h
#define cpu_rq(cpu) (&per_cpu(runqueues, (cpu)))
#define this_rq() this_cpu_ptr(&runqueues)

예제

• cpu_rq() 함수 사용 예제

https://elixir.bootlin.com/linux/v5.15.30/source/kernel/sched/fair.c
1 static unsigned long scale_rt_capacity(int cpu)
2 {
3 struct rq *rq = cpu_rq(cpu); // cpu번호 전달

this_rq() 함수

• percpu 타입의 runqueues 런큐 변수에 cpu 오프셋을 적용해 주소를 얻어 옴
• this_rq() 함수는 cpu 번호를 지정하지 않아도 현재 실행 중인 CPU 번호의 런큐의 주소
  를 반환

예제

https://elixir.bootlin.com/linux/v5.15.30/source/kernel/sched/core.c
1 static int migration_cpu_stop(void *data)
2 {
3 struct migration_arg *arg = data;
4 struct task_struct *p = arg->task;
5 struct rq *rq = this_rq();

런큐 자료구조

• 프로세스의 태스크 디스크립터인 task_struct 구조체의 &se->group_node 필드의 주소
  를 rq 런큐 구조체의 cfs_tasks 필드에 저장

런큐의 정체

런큐 디버깅
crash64> runq -m
CPU 0: [0 01:10:11.687] PID: 0 TASK: ffffffd17553fac0 COMMAND: "swapper/0" // TASK : curr
CPU 1: [0 01:10:11.687] PID: 0 TASK: ffffff80402b1e40 COMMAND: "swapper/1"
CPU 2: [0 00:00:00.000] PID: 1591 TASK: ffffff805d66dac0 COMMAND: "bash"
CPU 3: [0 01:10:11.686] PID: 0 TASK: ffffff80402b5ac0 COMMAND: "swapper/3"
crash64> p runqueues // p : 전역변수 보기
PER-CPU DATA TYPE: 
struct rq runqueues; // 전역변수 구조체
PER-CPU ADDRESSES: // percpu 오프셋을 더한 주소가 각각의 percpu 어드레스
[0]: ffffff80fb788bc0
[1]: ffffff80fb7a4bc0
[2]: ffffff80fb7c0bc0
[3]: ffffff80fb7dcbc0

crash64> runq
CPU 0 RUNQUEUE: ffffff80fb788bc0
CURRENT: PID: 0 TASK: ffffffd17553fac0 COMMAND: "swapper/0"
RT PRIO_ARRAY: ffffff80fb788e00 // 
[no tasks queued] // 큐잉된 목록이 안보임. 시스템에 오버헤드가 발생하지 않을 것이다.
CFS RB_ROOT: ffffff80fb788c70
[no tasks queued]
…
CPU 2 RUNQUEUE: ffffff80fb7c0bc0
CURRENT: PID: 1591 TASK: ffffff805d66dac0 COMMAND: "bash"
RT PRIO_ARRAY: ffffff80fb7c0e00
[no tasks queued]
CFS RB_ROOT: ffffff80fb7c0c70
[no tasks queued]
CPU 3 RUNQUEUE: ffffff80fb7dcbc0
CURRENT: PID: 0 TASK: ffffff80402b5ac0 COMMAND: "swapper/3"
RT PRIO_ARRAY: ffffff80fb7dce00
[no tasks queued]
CFS RB_ROOT: ffffff80fb7dcc70

CFS(Completely Fair Scheduler)란

• 커널 2.6.23 버전 이후로 적용된 리눅스의 기본 스케줄러
• CFS라는 용어를 그대로 풀면 ‘완벽하게 공정한 스케줄러’
• 런큐에서 실행 대기 상태로 기다리는 프로세스를 공정하게 실
  행하도록 기회를 부여하는 스케줄러

타임 슬라이스

• 운영체제에서 쓰는 용어로서 ‘스케줄러가 프로세스에게 부여한 실행 시간’을
  의미 (RTOS: 크레딧)
• CFS는 프로세스마다 실행할 수 있는 단위 시간을 부여하며 이를 타임 슬라이
  스라고 명시
• 프로세스는 주어진 타임 슬라이스를 모두 소진하면 컨텍스트 스위칭됨
• 타임 슬라이스로 프로세스를 관리하는 가장 큰 이유는 실행 대기 상태에 있
  는 모든 프로세스에게 최대한 CPU에서 실행할 수 있는 기회를 부여하기 위
  함

CFS스케줄러는 우선순위가 높은 프로세스에 대해 다음과 같이 처리

• 가장 먼저 CPU에서 실행
• 더 많은 타임 슬라이스를 할당

vruntime

• 커널에서 vruntime은 프로세스가 그동안 실행한 시간을 정규화한 시간 정보
• CFS 스케줄러가 프로세스를 선택할 수 있는 load weight와 같은 지표가 고려된 실행 시
  간
• CFS 스케줄러는 런큐에 등록된 프로세스 중 vruntime이 가장 작은 프로세스를 다음에
  실행할 프로세스로 선택
• update_curr() 함수에서 vruntime을 업데이트
• calc_delta_fair() 함수를 호출해서 얻은 vruntime 증가분을 curr->vruntime 필드에
  저장

vruntime의 특징

• CFS는 vruntime이 가장 작은 프로세스를 다음에 실행할 프로세스로 선택
• vruntime은 프로세스가 실행을 하면 할수록 계속 증가함
• vruntime이 천천히 커질수록 스케줄러에 의해 선택될 확률이 높음
• 우선순위가 높은 중요한 프로세스는 vruntime이 서서히 증가
• 프로세스가 잠든 상태(휴면)이면 vruntime은 업데이트되지 않음