[OS] 리눅스 스케줄링

스케줄링(Scheduling)

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

 

스케줄링 유형

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

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

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

선점형(Preemptive) 스케줄링

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

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

 

관련 용어

타임 슬라이스(Time Slice)

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

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

 

우선순위(Priority)

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

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

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

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

 

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

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

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

 

리눅스의 스케줄링

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

 

CFS(Completely Fair Scheduler)

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

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

 

동작 방식

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에 따라 동적으로 조정된 실행 시간을 사용한다.

 

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

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

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

 

스케줄링 정책

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

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

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

 

SCHED_NORMAL (or SCHED_OTHER)

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

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

SCHED_IDLE

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

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

SCHED_BATCH

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

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

SCHED_FIFO

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

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

SCHED_RR

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

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

SCHED_DEADLINE

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

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

 

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

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

 

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