Ready Queue는 진짜 큐(FIFO)일까?

---

들어가며

CS 면접 대비를 하며 운영체제 공부를 하다 보니 Ready Queue, Device Queue 같은 용어를 자연스럽게 받아들이게 되었다.

근데 내가 공부한 큐 자료구조 쓸 때랑 다른데..? 라는 생각이 들었고 다음과 같이 생각하게 되었다.

프로세스마다 우선순위가 다른데, 왜 FIFO 구조인 "큐"를 쓴다고 표현할까?
우선순위 필드를 가진 연결 리스트나 트리 구조가 더 적합하지 않나?

지금 생각해도 이 의문은 꽤나 타당하긴 한데..

결론부터 말하면, 실제 커널 구현체는 우리가 배운 "큐"라는 단어 그대로의 자료구조가 아닌 경우가 대부분이다.

---

책에서 설명한 "큐"는 자료구조 명칭이 아니라 개념적 추상화

운영체제 교재에서 Ready Queue, Device Queue라고 부르는 것은 "프로세스들이 특정 상태로 대기하고 있는 집합"이라는 개념을 표현하는 용어일 뿐, 실제 구현 방식을 의미하는 게 아니다.

• Ready Queue: CPU 할당을 기다리는 프로세스들의 집합
• Device Queue: 특정 입출력 장치의 작업 완료를 기다리는 프로세스들의 집합

이 집합을 실제로 어떤 자료구조로 구현할지는 운영체제와 스케줄링 정책에 따라 완전히 달라진다.

---

FCFS라면 진짜 FIFO 큐로 충분하다

내가 생각했을 때는 진짜 큐라면 다음 다룰 내용들처럼 동작하니까 차라리 링크드 리스트 같은 자료구조가 낫지 않나? 생각했다.

스케줄링 정책이 단순히 "먼저 온 프로세스부터 처리"(FCFS, First-Come First-Served)라면, 진짜 FIFO 큐나 단순 연결 리스트로 구현해도 문제가 없다.

삽입은 뒤에, 추출은 앞에서 하면 되는 O(1) 연산이기 때문이다.

---

우선순위가 있다면 이야기가 달라진다

문제는 우선순위 스케줄링이나 시분할 스케줄링처럼 "다음 실행 대상"을 매번 다시 계산해야 하는 경우다.

나는 처음에 이렇게 생각했다. "진짜 큐(FIFO)로는 이 상황을 감당할 수 없으니, 차라리 우선순위 필드를 가진 연결 리스트가 낫지 않을까?"

이렇게 하면 최고 우선순위 프로세스를 찾는 건 여전히 리스트를 처음부터 끝까지 훑어야 하니 O(N)이지만, 일단 찾고 나면 그 노드를 지우는 건 앞뒤 포인터만 바꾸면 되니 O(1)라서 단순하게 FIFO보다는 구조가 나아 보였다.

여기서 한 걸음 더 나가서, 아예 전역 변수로 "지금 우선순위가 제일 높은 노드"를 가리키는 포인터를 하나 들고 있으면 어떨까 생각했다. 그러면 조회는 항상 O(1)이 되고, 상수 시간만에 작업을 끝낼 수 있다고 생각했다.

---

이렇게 안쓰는 이유가 있겠지

그런데 내가 생각했던 이 방식엔 함정이 있었다.

그 포인터가 가리키던 노드가 바로 실행되어 리스트에서 빠지는 순간, 다음 1등이 누군지는 알 수가 없어진다. 결국 다음 후보를 찾으려면 리스트 전체를 다시 훑어야 하고, 최악의 경우 여전히 O(N)이 반복된다. 포인터 하나를 캐싱해두는 것만으로는 근본적인 해결이 안 됐던 것이다.

---

그래서 실제 큐는 어떻게 사용되어지고 있는지 구글링을 좀 해보니, 커널 수준에서 널리 쓰이는 방식은 다음과 같았다.

• 우선순위 큐(힙, Heap): 최우선 프로세스를 O(log n)에 삽입/추출
• 레드-블랙 트리(Red-Black Tree): 정렬 상태를 유지하면서 삽입/삭제/검색이 모두 O(log n)
• Multilevel Queue: 우선순위 레벨별로 별도의 큐를 두고, 상위 레벨부터 순회

 

실제 사례: Linux 스케줄러

이론이 아니라 실제 구현을 보면 이 논리가 더 명확해진다. (리눅스를 기준으로 구글링 했다)

CFS (Completely Fair Scheduler)는 2007년부터 Linux의 기본 스케줄러로 오랫동안 쓰여왔다. 동작 방식을 간단히 풀면 이렇다.

• 각 프로세스마다 "지금까지 CPU를 얼마나 썼는지"를 나타내는 vruntime이라는 값을 하나씩 붙여준다.
• 이 vruntime 값을 기준으로 모든 프로세스를 레드-블랙 트리에 정렬해서 저장한다.
• CPU가 놀면, 트리에서 vruntime이 가장 작은 프로세스(= 지금까지 CPU를 상대적으로 가장 적게 쓴, 즉 가장 "억울한" 프로세스)를 골라서 실행시킨다.
• 트리 구조라서 이 프로세스는 O(1)에 바로 찾을 수 있고, 새 프로세스를 넣거나 빼는 작업도 O(log n)으로 빠르게 처리된다.

실제 레드-블랙 트리의 빨강/검정 밸런싱 규칙은 생략, vruntime 기준 정렬과 leftmost 캐싱 개념만 단순화해서 표현했습니다

 

즉 "누가 CPU를 덜 썼는지"로 줄을 세운 트리라고 보면 된다. (참고로 트리 탐색 자체는 원래 O(log n)이지만, 가장 작은 값 노드를 rb_leftmost 포인터로 미리 캐싱해두기 때문에 다음 실행 프로세스를 뽑는 것만 O(1)이다. 쓰면서 헷갈릴까봐 추가로 정리 함ㅎㅎ..)

 

2023년 10월, 커널 6.6부터 Linux는 CFS 대신 EEVDF(Earliest Eligible Virtual Deadline First)라는 새 스케줄러를 기본값으로 쓰기 시작했다.

EEVDF도 CFS처럼 트리 구조를 쓰지만, "CPU를 얼마나 썼는가" 대신 "언제까지 실행해줘야 하는가(가상 마감 시간)"를 기준으로 순서를 정한다는 점이 다르다.

CFS를 오래 쓰다 보니 지연 시간을 줄이기 위한 임시방편 패치들이 계속 쌓이는 문제가 있었고, 이를 근본적으로 해결하기 위해 도입된 것이다.

정리하면, "Linux는 단순 큐가 아니라 트리 구조로 스케줄링한다"는 결론은 CFS든 EEVDF든 똑같이 맞다. 다만 "지금 Linux는 CFS를 쓴다"고 말하면 최신 커널 기준으로는 틀린 얘기가 된다.

막상 글 쓰다보니.. OS 알면 알 수록 재미없고 어렵다..😨

---

정리

구분	설명
교과서의 "Ready Queue / Device Queue"	프로세스 대기 집합이라는 개념적 표현 (추상)
FCFS 같은 단순 정책	실제 FIFO 큐/연결 리스트로 구현 가능
우선순위 기반 정책	힙, 레드-블랙 트리 등으로 구현
Linux 스케줄러 (~커널 6.5)	CFS, 레드-블랙 트리 기반 (vruntime 키)
Linux 스케줄러 (커널 6.6~)	EEVDF, 트리 기반 (가상 마감 시간 키)

 

"왜 O(1) 탐색이 가능한 구조를 안 쓰냐"는 나의 질문은, "큐"라는 단어를 문자 그대로의 FIFO 자료구조로 해석했을 때 나올 수 있는 자연스러운 의문이었다.

결론적으로 실제로는 정반대였다.

성능이 중요한 커널 스케줄러일수록 오히려 더 정교한 트리/힙 구조를 쓴다. 교과서 용어와 실제 구현 사이의 차이를 인지하고 있으면, 추후에 운영체제 개념을 더 정확하게 이해하는 데 도움이 될 것 같다.

 

글을 작성하면서.. 이렇게 자세히 적을 의도는 없었지만 글이 많이 딥해졌다 😂

그럼 오늘도 20000!

---

참고 자료

• Linux Kernel Documentation, "CFS Scheduler" / "EEVDF Scheduler"
• Wikipedia, "Completely Fair Scheduler"