[OS] 리눅스 스케줄링

1. 스케줄링(Scheduling)

• 여러 작업에 CPU 시간을 할당하여 자원을 효율적으로 사용할 수 있도록 하는 메커니즘
• 리눅스는 선점형 멀티태스킹 시스템으로, 프로세스의 스레드와 우선순위와 정책에 따라 CPU 시간을 동적으로 할당한다.
  • 선점형 멀티태스킹(Preemptuve Multitasking): 운영체제가 필요에 따라 강제로 프로세스의 실행을 중단하여 다른 프로세스에게 CPU를 할당하는 멀티태스킹 방식
  • 이를 통해 여러 프로세스가 동시에 실행되는 것처럼 보이게 한다.

 

1.1. 스케줄링 유형

1.1.1. 비선점형(Non-Preemptive) 스케줄링

어떤 프로세스가 CPU를 할당받으면 그 프로세스가 종료되거나 자발적으로 중지될 때(주로 I/O에 의해)까지 계속 실행되도록 보장한다.

• 순서대로 처리되므로 실행 순서가 예측 가능하고, 문맥 교환에 의한 오버헤드가 적다.
• 실행 시간이 긴 프로세스가 짧은 프로세스를 오랫동안 대기시킬 수 있으므로 처리율이 떨어질 수 있다.
• ex. 전통적인 UNIX 시스템의 스케줄링

1.1.2. 선점형(Preemptive) 스케줄링

CPU에서 실행 중인 프로세스를 중지하고 CPU를 강제로 점유할 수 있다.

• 모든 프로세스에게 CPU 사용 시간을 동일하게 부여할 수 있어 빠른 응답시간을 요하는 대화식 시분할 시스템에 적합하다.
• 문맥 교환이 자주 발생하기 때문에 오버헤드가 있다.
• ex. 리눅스 커널 2.6 이상에서 사용되는 CFS는 선점형 방식 (대부분의 운영체제는 선점형 방식을 사용한다.)

 

1.2. 관련 용어

1.2.1. 타임 슬라이스(Time Slice)

스케줄러가 프로세스에게 부여한 실행 시간(CPU 최대 사용 시간)

• 프로세스는 주어진 타임 슬라이스를 모두 소진하면 컨텍스트 스위칭된다.

 

1.2.2. 우선순위(Priority)

프로세스가 CPU를 할당받는 순서를 결정하는 데 사용된다.

• 우선순위가 높은 프로세스를 가장 먼저 CPU에서 실행시킨다.
• 리눅스는 총 140단계의 우선순위를 제공한다. 값이 낮을수록 우선순위가 높다.
  • 0 ~ 99: RT(실시간) 프로세스
  • 100 ~ 139: 일반 프로세스

https://blog.naver.com/crushhh/221484639057?viewType=pc

• 종류
  • 정적 우선순위: 프로세스가 생성될 때 설정되고 이후 변경되지 않는 값. 실시간 스케줄링에서 사용된다.
  • 동적 우선순위: 시스템의 상태와 프로세스의 행동에 따라 변경될 수 있는 값. 일반 사용자 프로세스에서 사용된다.

 

1.2.3. 가상 실행 시간(vruntime, Virtual Runtime)

각 프로세스가 그동안 실행한 시간을 정규화한 시간 정보로, 프로세스가 공정하게 CPU 시간을 받을 수 있도록 하기 위한 메커니즘

• 각 프로세스의 가상 실행 시간은 프로세스가 실행되는 동안 증가하며, 가상 실행 시간이 가장 짧은 프로세스가 다음에 실행된다.
• 우선순위가 높은 프로세스는 가상 실행 시간이 더 천천히 증가하도록 조정된다.

 

2. 리눅스의 스케줄링

실행 중인 프로세스나 스레드에 CPU 시간을 할당하는 방식

 

2.1. CFS(Completely Fair Scheduler)

모든 프로세스가 공평하게 CPU 시간 분배를 목표로 하는 스케줄러로, 리눅스의 기본 스케줄러(커널 2.6 이상부터)

• 시분할 스케줄링(Time-Sharing Scheduling)
  • 여러 프로세스가 일정 시간 동안 CPU를 번갈아 가면서 사용하도록 하는 방식
  • 응답 모든 작업이 동시에 진행되는 것처럼 보이는 대화식 처리가 가능하다.
• CFS에서는 동적 우선순위(nice 값)를 사용하여 프로세스의 우선순위를 결정한다. 
• 각 프로세스의 실행 시간(vruntime)을 추적하고, 가장 적게 CPU 시간을 할당받은 프로세스에게 우선적으로 CPU를 할당한다.

 

2.1.1. 동작 방식

1. Red-Black Tree

• 모든 프로세스는 vruntime을 기준으로 정렬된 RB 트리에 저장된다.
• RB 트리는 균형 이진 검색 트리 ➡️ 삽입/삭제/검색 연산 수행 시간은  O(logN)으로 빠르다.

2. 프로세스 선택

• CFS는 항상 vruntime이 가장 작은 프로세스를 선택해서 실행한다.
• 트리에서 가장 왼쪽에 있는 프로세스가 가장 작은 vruntime을 가지므로 이 프로세스를 선택한다. ➡️ O(1)

3. 프로세스 실행 및 vruntime 업데이트

• 선택한 프로세스에 CPU를 할당한다.
• 실행되는 동안 vruntime이 증가되고, 프로세스가 아직 종료되지 않았다면 다시 트리에 삽입한다.

4. 트리 조정

• 실시간으로 vruntime과 트리 구조를 업데이트한 뒤 위의 과정을 반복하며, 모든 프로세스가 공정하게 CPU 시간을 할당받을 수 있도록 한다.

💡 타임 슬라이스, 우선순위, 가상 실행 시간의 관계
nice 값이 낮은(높은 우선순위) 프로세스는 vruntime이 더 천천히 증가하여 상대적으로 더 많은 CPU를 할당받을 수 있도록 한다. 높은 우선순위의 프로세스는 상대적으로 더 긴 타임 슬라이스를 할당받아 더 오래 실행될 수 있다. CFS에서는 고정된 타임 슬라이스 대신 vruntime에 따라 동적으로 조정된 실행 시간을 사용한다.

 

2.2. 실시간 스케줄링(Real-Time Scheduling)

응답 시간과 절대적인 우선순위가 중요한 실시간 작업을 위한 방식

• 주로 고정 우선순위 기반의 선점형 스케줄링 알고리즘을 사용한다.

 

3. 스케줄링 정책

각 스케줄링 내에서 실제로 적용되는 세부 규칙으로, 프로세스들이 CPU 시간을 어떻게 할당받을지를 규정한다.

http://jake.dothome.co.kr/scheduler/

리눅스 커널에는 5개의 스케줄러가 있다. 이 중 Stop과 Idle-task 스케줄러는 커널이 자체적으로만 사용하므로 사용자들이 선택할 수 없으므로 이를 제외한 3개의 스케줄러에 대해서만 알아보자.

 

3.1. SCHED_NORMAL (or SCHED_OTHER)

일반적인 사용자 프로세스에 적용되는 스케줄링 정책으로 리눅스에서 기본적으로 사용하는 스케줄링 정책이다.

• CFS에 의해 구현된다.
• 타임 슬라이스와 커널에 의해 지속적으로 변경되는 동적 우선순위를 사용한다.
• 프로세스는 가상 실행 시간에 기반하여 스케줄링된다. 가상 실행 시간이 짧은 프로세스가 먼저 실행된다.
• 사용자는 직접 우선순위를 조정할 수 없고 단지 nice 값을 상향 조정만 할 수 있다.
  • 하향 조정하려면 root 권한이 필요하다.

3.2. SCHED_IDLE

시스템이 유휴 상태일 때 실행되는 가장 낮은 우선순위의 백그라운드 작업을 위한 정책

• 다른 프로세스가 모두 실행된 후에야 CPU를 사용할 수 있다.

3.3. SCHED_BATCH

배치 작업을 위한 정책으로, 긴 시간 동안 CPU를 많이 사용하는 작업에 적합하다.

• 대화형 응답성보다는 처리량이 중요한 작업에 사용된다.
• SCHED_OTHER와 동일하게 nice 값을 통해 우선순위를 설정할 수 있다.

3.4. SCHED_FIFO

실시간 프로세스에 사용되는 정책으로, 고정 우선순위 기반의 선입선출 방식

• 모든 SCHED_OTHER보다 높은 고정 우선순위를 가지며, 타임 슬라이스의 개념이 없다.
• 가장 높은 우선순위의 프로세스가 종료되거나 입출력 요구 등에 의해 스스로 CPU를 반환하기 전까지 계속 실행된다.
• 슈퍼 유저(root)만 생성할 수 있다.

3.5. SCHED_RR

실시간 프로세스에 사용되는 정책으로, 같은 우선순위 등급에서는 타임 슬라이스에 의한 라운드로빈(Round-Robin) 기법이 적용된다.

• 모든 SCHED_OTHER보다 높은 고정 우선순위를 가지며, 타임 슬라이스를 사용하여 순환한다.
• 슈퍼 유저(root)만 생성할 수 있다.

3.6. SCHED_DEADLINE

엄격한 실시간 요구사항을 가진 작업을 위한 정책

• 각 작업은 특정한 데드라인(기한) 내에 완료되어야 한다.

 

💡 nice 값 조정 시 필요한 권한
- 상향 조정(우선순위 낮춤): 일반 사용자도 가능
- 하향 조정(우선순위 높임): 시스템 자원 독점 방지를 위해 root 권한이 필요함

💡 실시간 스케줄링 정책 생성 시 슈퍼 유저(root) 권한이 필요한 이유는?
실시간 스케줄링(SCHED_FIFO, SCHED_RR)은 시스템 자원에 매우 민감하게 반응하며 높은 우선순위로 동작하므로, 일반 사용자가 쉽게 접근할 수 있도록 하면 시스템 성능 저하나 자원 독점 등의 문제가 발생할 수 있다. 따라서 시스템 안정성과 성능을 유지하기 위해 슈퍼 유저만 설정할 수 있다.

 

3.7. Ref

https://haena02.tistory.com/46

https://ko.wikipedia.org/wiki/%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81_(%EC%BB%B4%ED%93%A8%ED%8C%85)

https://blog.naver.com/alice_k106/221149061940

https://velog.io/@roycewon/CPU-%EC%8A%A4%EC%BC%80%EC%A5%B4%EB%A7%81

https://svalaks.medium.com/linux-internals-completely-fair-scheduling-cfs-cpu-scheduler-algorithm-7412c08d2e37

https://dataonair.or.kr/db-tech-reference/d-lounge/technical-data/?mod=document&uid=236896

https://docs.kernel.org/scheduler/sched-design-CFS.html

https://puzzle-puzzle.tistory.com/entry/%EC%8A%A4%EC%BC%80%EC%A5%B4%EB%9F%AC-%EA%B8%B0%EC%B4%88