[Linux] 3. 리눅스 스케줄링

리눅스 운영체제는 프로세스나 후에 설명될 스레드에 대해 선점(Preemption) 스케줄링 기법을 제공합니다.

선점 스케줄링은 시분할 시스템에서 한 프로세스의 CPU 독점을 방지하기 위해 주어지는 타임 슬라이스(Time slice)가 소진되었거나, 인터럽트나 시스템 호출 종료 시에 더 높은 우선 순위의 프로세스가 발생하였음을 알았을 때 현 실행 프로세스로부터 강제로 CPU를 회수하여 다른 프로세스에 할당하는 것을 말합니다.

이러한 선점 스케줄링을 사용하는 대부분의 운영체제는 보통 CPU 효율의 극대화, 프로세스에 대한 빠른 응답 및 공평성의 향상 등을 위해 여러 가지 스케줄링 정책과 동적 우선순위 기법을 사용합니다.

3.1 성능 향상을 위한 선점 스케줄링의 고려 사항

 다음은 시분할 선점 스케줄링에서 시스템 효율을 높이기 위한 일반적인 스케줄링 원칙입니다.

 1) 연산 위주 프로세스보다 입출력 위주 프로세스에 높은 우선순위를 줍니다. 이와 같은 우선순위 할당의 이유에는 두 가지가 있습니다. 첫째, 입출력 위주의 프로세스를 먼저 스케줄링하면 이 프로세스는 CPU를 조금만 사용하고 입출력 대기를 위해 CPU를 반환하고 CPU는 다른 프로세스에 할당됩니다. 따라서 결과적으로 CPU와 입출력 장치의 동시 작동(CPU I/O overlap)이 이루어져 자원의 활용도가 증가하게 됩니다. 또 다른 이유는 입출력 위주의 프로세스는 일반적으로 대화형 프로세스여서 빠른 응답을 원하는 경우가 많으므로 우선순위를 높게 할당합니다. 그러나 일반적으로 커널은 실행 프로세스의 성격을 사전에 알 수 없으므로 프로세스들을 실행시켜 가며CPU 활용의 자료를 모아 이를 스케줄링에 점진적으로 반영하게 됩니다.

 2) 실시간 프로세스는 일반적인 프로세스와 대부분의 커널 실행 작업보다도 우선순위가 높습니다. 실시간 프로세스의 실행이 늦는 경우 재앙적 상황이 발생할 수 있기 때문입니다(경성 실시간 프로세스). 멀티미디어 서비스 같은 경우에도 오디오와 비디오 자료의 시간적 동기화가 필요한데, 이러한 시작 제약 때문에 실시간 서비스로 분류되지만, 시간 조건을 어기더라도 재앙적 상황은 발생하지 않으므로 이를 연성 실시간 프로세스라고 합니다.

 3) 타임 슬라이스는 프로세스들의 평균 CPU 반환 시간보다 약간 크게 책정하는 것이 좋습니다. 어느 시스템에서 실행되는 프로세스들의 일반적인 특성이 유사하여 평균 CPU 반환 시간을 알 수 있다면 타임 슬라이스는 이보다 약간 크게 주어야 합니다. 그 이유는 잠시 후에 CPU를 반환할 프로세스에서 CPU를 선점하게 된다면 불필요한 문맥 교환 오버헤드가 생기기 때문입니다.

 4) 일반적으로 프로세스가 시스템 호출을 하여 커널 모드 실행에 있을 때, 프로세스의 대기상태 전이로 CPU를 스스로 반환하기 이전에는 선점이 일어나지 않습니다. 프로세스가 커널 모드 실행 중일 때 타임 슬라이스를 적용이나 기타의 이유로 이를 선점하게 되면 시스템 호출의 재진입에 의한 복잡한 커널 내부적 상호 배제 문제가 많이 발생하기 때문입니다. 그러나 긴급한 실시간 프로세스가 발생하였을 때 이러한 속성은 문제가 되기도 합니다. 커널 내에 프로세스가 진입해 있으면서도 이를 선접할 수 있는 기능을 제공하는 커널을 선점형 커널(Preemptive Kernel)이라 하는데 이러한 기능은 Linux Version 2.6.x 부터 제공되고 있습니다.

3.2 리눅스 스케줄링

 리눅스 스케줄링에서 프로세스(스레드)들은 기본적으로 다음의 스케줄링 그룹으로 구분되는데 이를 스케줄링 정책(policy)라 합니다.

  1) SCHED_OTHERS: 일반적인 사용자 프로세스에 적용되는 스케줄링 정책으로 타임 슬라이스와 커널에 의해 지속적으로 변경되는 동적 우선순위를 사용합니다.

  2) SCHED_FIFO: 긴급한 실시간 프로세스에 사용되는 정책으로 모든 SCHED_OTHERS 그룹보다 높은 고정 우선순위를 가지며 타임 슬라이스의 개념이 없습니다. 타임 슬라이스의 개념이 없다는 의미는 해당 프로세스가 가장 높은 우선순위를 가지고 있을 때, 입출력 요구 등에 의해 스스로 CPU를 반환하기 이전에는 CPU를 계속 사용할 수 있는 것을 의미합니다.

 * FIFO => First In First Out

  3) SCHED_RR: 역시 실시간 프로세스에 사용되는 정책으로 모든 SCHED_OTHERS 그룹보다 높은 고정 우선순위를 가지며, 타임 슬라이스를 줍니다. 같은 우선 순위 등급에서는 타임 슬라이스에 의한 라운드-로빈(Round-Robin) 스케줄링 기법이 적용됩니다. Round-robin 스케줄링은 타임 슬라이스가 다 소진되었을 때 스케줄링 큐의 맨 마지막으로 삽입되어 같은 우선순위의 모든 다른 프로세스의 스케줄링 이후에 CPU를 받게 하는 스케줄링입니다.

 SCHED_FIFO와 SCHED_RR의 프로세스는 슈퍼 유저(Super User) 만이 생성할 수 있고, 고정 우선순위를 사용하므로 스케줄링 기법 상으로는 간단한 모델입니다. 일반적 사용자 프로세스에 적용되는 SCHED_OTEHRS 기법은, 앞서 설명한 연산 위주 프로세스와 입출력 위주 프로세스 중 후자에 우선순위를 높게 주는 정책을 반영하기 위한 것 입니다. 모든 프로세스는 생성 시에 타임 슬라이스를 할당받고 이는 기본 우선순위의 역할을 합니다. 이러한 동적 우선순위 시스템을 이해하기 위해 리눅스 스케줄러의 SCHED_OTHERS 프로세스에 대한 우선순위 계산 식과 타임 슬라이스 소진 시의 새로운 타임 슬라이스를 설정하는 2.4.x 경우의 계산식을 알아보겠습ㄴ니다.

 SCHED_OTEHRS의 경우 타임 슬라이스가 소진되지 않은 새로운 프로세스에 스케줄을 줄 때 프로세스들의 우선순위(goodness) 계산 식은 다음과 같습니다.(단 SCHED_FIFO나 SHCED_RR의 실시간 프로세스는 주어진 고정 우선순위를 갖습니다)

   동적 우선순위 = 남은 타임 슬라이스 + (20 - nice)의 비례 값;

 SCHED_OTHERS 프로세스의 타임 슬라이스 소진 시 새로운 타임 슬라이스 설정은 다음과 같습니다. 한 프로세스의 타임 슬라이스가 소진되면 한 프로세스의 남은 타임 슬라이스를 나타내는 태스크 구조체 내의 counter의 값은 0이 되고, 다른 모든 프로세스의 타임 슬라이스가 소진되기까지 이 값은 변화가 없고 따라서 스케줄링을 받지 못합니다. 모든 프로세스의 counter 값이 0이 되면 각 프로세스의 타임 슬라이스를 재 설정하게 되는데 그 방식은 아래와 같습니다.

   새로운 타임 슬라이스 = (20 - nice)의 비례 값 + 1;

 위에서 타임 슬라이스 소진 이전에 여러 가지 이유로 CPU를 선점당하는 경우에, 그 우선순위는 남은 타임 슬라이스에 의존함을 알 수 있습니다. 즉, 타임 슬라이스가 많이 남은 경우네는 CPU를 덜 사용한 것이 되고, 이 경우에는 높은 우선순위를 줌을 알 수 있습니다.

 위의 우선순위 계산 식과 새로운 타임 슬라이스 설정 식에서 nice 값은 우선순위 계산 시의 벌점과 같이 작용합니다. 즉, nice 값이(-20 ~ 20, 기본 값은 0) 작을수록 동적 우선순위 시스템에서 높은 우선순위와 큰 타임 슬라이스를 가집을 알 수 있습니다. SCHED_OTHERS 프로세스의 경우, 사용자는 직접 우선순위를 조정할 수 없고 단지 nice 값을 상향 조정할 수 있을 뿐입니다. nice를 하향 조정하려면 슈퍼 유저의 권한이 필요합니다. fork 시에 nice 값은 상속받게 됩니다. Linux 2.6.x 이상의 버전에서 SCHED_OTHERS는 CFS(Completely Fair Scheduling) 정책이 사용되고 있는데, 기본적인 개념은 그 이전의 버전과 같은 것으로 보아도 무관합니다.

 

 3.2.1 스케줄링 관련 시스템 호출

  프로세스의 우선순위나 스케줄링 정책 조정을 위한 함수들은 다음과 같습니다. 

 

  우선 생성된 프로세스에 대해 일반적인 시분할 프로세스인 경우 SCHED_OTHERS로 설정하고, 실시간 프로세스의 경우에 SCHED_FIFO와 SCHED_RR 정책과 함께 우선순위를 줄 수 있는 함수들은 다음과 같습니다.

SETSCHEDULER(2)
#include <sched.h>
 
int sched_setscheduler(pid_t pid, int policy, const struct sched_param *p);
 
int sched_getscheduler(pid_t pid);
 
struct sched_param {
    ...
    int sched_priority;
    ...
};
 
 
    입력 값
        - pid: 해당 프로세스 id(0인 경우 자신)
        - policy: SCHED_OTEHRS, SCHED_FIFO, SCHED_RR
        - sched_param: policy에 따라 구조체 내부의 sched_priority 값을 설정한다. SCHED_OTHERS인 경우 0을 주어야하며,
                            실시간 프로세스의 경우는 1 - 99 범위의 값을 준다. SCHED_FIFO와 SCHED_RR은 수퍼 유저만 사용할 수 있다.
        - sched_getscheduler는 policy를 리턴한다.
        
    반환 값
        - 정상: sched_setscheduler -> 0, sched_getscheduler -> policy
        - 에러: -1

  위의 설명에서 알 수 있듯이 이 sched_setscheduler 함수는 SCHED_OTEHRS 일 경우는 무의미합니다. 따라서 이 함수는 실시간 프로세스를 지정하고 고정 우선순위를 주는 데 사용합니다.

  스케줄링 정책을 준 실시간 프로세스에 대해 사용자 임의로 우선순위 조정을 위해 사용하는 함수들은 다음과 같습니다.

SCHED_SETPARAM(2)
#include <sched.h>
 
int sched_setparam(pid_t pid, const struct sched_param *p);
int sched_getparam(pid_t pid, struct sched_param *p)
 
    입력 값
        - pid: 해당 프로세스 id (0인 경우 자신)
        -sched_param: policy에 따라 구조체 내부의 sched_priority 값을 설정한다. 
                        실시간 프로세스의 경우는 1 - 99 범위의 값을 준다.
                      SCHED_FIFO와 SCHED_RR은 수퍼 유저만 사용할 수 있다.
        -sched_getscheduler는 sched_param 구조체를 반환한다.
        
    반환 값
        - 정상: 0
        - 에러: -1
        

  기타 스케줄링 관련 함수들로는 다음과 같은 것들이 있습니다.

SCHED_YIELD(2)
#include <sched.h>
 
int sched_yield(void);

  sched_yield 함수는 커널에 재스케줄링을 요구하여 호출 프로세스는 같은 우선 순위 등급의 큐에서 가장 뒤로 옮겨집니다. sched_yield 후에, 자신보다 높은 우선순위 위의 프로세스 없으면 호출 프로세스가 다시 스케줄을 받습니다. 이와 같은 함수는 어떠한 프로세스가 어떤 조건이 만족하길 기다리는 loop을 수행할 때, 조건이 만족하지 않아도 주어진 타임 슬라이스 동안 계속 loop을 수행할 때, 조건이 만족하지 않아도 주어진 타임 슬라이스 동안 계속 loop을 돌아 CPU 시간을 낭비하는 것을 방지하는 데 사용되는 것이 보통입니다. 즉, 한 번의 조건 테스트로 기다리는 조건이 만족하지 않음을 알았을 때, 다른 프로세스에 스케줄을 일단 양보하고 조건 테스트는 후에 다시 스케줄을 받았을 때 다시 하기 위한 함수입니다. 사용 예는 다음과 같습니다.

while (!condition) { // 조건은 trylock 이나 세마포어의 try wait 등을 예로 들을 수 있다.
    sched_yield();
    
}

  그 외 SCHED_OTEHRS와 SCHED_RR 정책 프로세스의 nice 값을 조정하는 함수는 다음과 같습니다.

NICE(2)
#include <unistd.h>
 
int nice(int inc);

  inc 값이 음수이면 우선순위가 증가하게 되는데, 이는 슈퍼 유저만이 할 수 있습니다. nice 함수는 SCHED_OTEHRS 프로세스의 nice 값을 조정하고 이는 타임 슬라이스와 우선순위 조정에 영향을 미칩니다. 단, SCHED_RR의 실시간 프로세스인 경우는 타임 슬라이스 조정에만 영향을 주고 우선순위는 고정이므로 영향을 미치지 않습니다.

  위에서 설명한 스케줄링 관련 함수들은 일반적으로 nice를 제외하고는 모두 SCHED_FIFO나 SCHED_RR의 실시간 프로세스를 위해 사용되는 것들 입니다. 즉, 본 장의 내용은 실시간 시스템 응용을 작성하는 사용자를 위한 것이라 할 수 있습니다.