[운영체제] 실시간 스케줄링

실시간 시스템

• Inverted Pendulm, 막대의 기울기나 속도 정보등을 시스템으로 전달한다. 시스템이 그를 분석하여 엑추에이터를 통해 막대의 위치를 조정하여 막대가 쓰러지지 않도록 한다.
• 연성 실시간 시스템 : 데드라인을 만족한다는 것이 90%같은 확률로 표현된다. 중요한 실시간 프로세스가 그렇지 않은 프로세스에 비해 우선권만 가지고 있다.
• 경성 실시간 시스템 : 데드라인을 100% 만족한다는 엄격한 요구조건을 만족시켜야 한다. 데드라인이 지난 후에 서비스를 받는 것은 서비스를 전혀 받지 않는 것과 동일하다.

지연 시간의 최소화

• 이벤트 : 타이머가 만료되었을 때와 같은 소프트웨어적인 이벤트 / 원격으로 제어되던 장치가 방해물을 만났을 때와 같은 하드웨어적인 이벤트
• 사건지연 시간 (event latency) : 이벤트가 발생했을 때 시스템에서 그에 맞는 서비스를 수행할 때까지 소요되는 시간이다. 인터럽트 지연시간과 디스패치 지연시간으로 나뉜다.
• 인터럽트 지연시간 (interrupt latency) : 인터럽트 발생시점부터 ISR까지 소요되는 시간이다. 인터럽트 발생 시 운영체제는 수행중인 CPU 명령어를 마무리하고 인터럽트의 종류를 결정한다. 그리고 본격적인 인터럽트 처리 이 전에 현재까지 수행 중이던 프로세스의 문맥을 보존해놓아야 한다. (문맥교환) 실시간 작업이 즉시 수행될 수 있도록 이러한 인터럽트 지연 시간을 최소화하는 것이 실시간 시스템에 있어서는 매우 중요하다. 경성 실시간 시스템에서는 이러한 인터럽트 지연 시간이 정해진 시간보다 작아야 하기 때문에 요구조건이 엄격하다.
• 디스패치 지연시간 (dispatch latency) : 인터럽트 처리 후 그 결과를 실행하기 위해 진행 중인 프로세스, 즉 인터럽트에 의해 비자발적 문맥교환을 거치고 다시 준비상태로 되돌아온 프로세스가 있다. 그러한 프로세스를 블록시키고 우선 순위가 높은 다른 프로세스를 시작시키는 데에 걸리는 시간을 말한다. 인터럽트에 따라서 시급히 반응하여 CPU를 즉시 사용해야하는 실시간 작업이 있을 수 있으므로, 이러한 디스패치 지연시간도 최소화해야 한다.
• 디스패치 지연시간에 영향을 주는 것은 충돌요소이다. 충돌요소로는 첫번째로 커널에서 수행중인 작업이 있어 선점할 수 없는 경우가 있다. 비선점커널을 사용할 시 특히 그런데, 선점형 커널의 사용으로 최소화가 가능하다. 두번째 충돌 요소로는 높은 우선순위의 프로세스가 필요로 하는 자원을 낮은 우선순위의 프로세스가 선점하고 있는 경우이다. 이럴 경우 낮은 우선순위의 프로세스가 해당 자원을 릴리즈할 때까지 기다려야 한다.
• 실시간 스케줄러를 선점이 가능하고 우선순위를 기반으로 작동하도록 하면 연성 실시간 시스템에서는 어느정도 사용이 가능하다. 하지만 경성 실시간 시스템의 경우엔 이러한 조치로 부족하다. 따라서 특수한 스케줄링 기법이 요구된다.

실시간 태스크

• 일반적으로 실시간 시스템에서는 프로세스라는 용어보다는 태스크라는 영어를 많이 쓴다. 따라서 해당 장에서는 실시간 프로세스 대신 실시간 태스크라는 용어를 사용하겠다.
• 작업(job) : 실시간 태스크의 가장 기본적인 단위이다. Inverted Pendulm의 예에서 본다면 센서로부터 인터럽트를 통해 값이 들어오는 것이 하나의 job이 되는 것이다. 자원(파일, 공유변수, 동기화 요소 등)과 타이밍 파라미터(주기, 마감시간, 수행시간)를 그 속성으로 가진다. 자원이라는 것은 job의 실행 시 필요한 파일이나 공유변수 등이다.
• 이러한 job의 연속을 실시간 태스크라고 한다. 단 이는 비주기적(Aperiodic)일 수도 있고 주기적(Periodic)일 수도 있다. 하지만 주기적 태스크에 주안점을 두고 설명하겠다.
• 주기적 태스크 : 주기(period, p), 마감시간(deadline, d), 수행시간(execution Time, t)로 구성된다. 주기적 실시간 태스크를 설명할 땐 이 중 p와 t를 주로 사용한다. t는 CPU 버스트 타임의 최대 예측치를 감안하여 명시한다. 세 파라미터의 관계는 t < d < p 가 될 것이다.
• 이용률(Utilization) : t/p
• 빈도(Rate) : 1/p

실시간 스케줄링

• 동시에 여러 개의 실시간 태스크들이 존재할 때 각 테스크 간의 작업의 수행 순서를 결정해주는 것이다.
• 모든 태스크의 모든 작업이 매번 주기가 끝나기 전에 실행이 완료되는 스케줄을 구하는 것은 쉽지 않을 것이다.
• 따라서 이러한 문제를 원리적 차원에서 풀어가기로 했다.
• 이에는 정적우선순위 스케줄링과 동적 우선순위 스케줄링이 있다.

RM(Rate Monotonic) 스케줄링 : 정적 우선순위 스케줄링

• 선점 가능한 정적 우선순위 정책을 이용해 주기 태스크들을 스케줄링한다. 낮은 우선순위의 태스크의 작업이 실행 중에 있고, 높은 우선 순위 태스크의 작업이 준비되면, 높은 우선순위의 태스크가 낮은 우선순위의 태스크를 선점한다.
• 각각의 주기 태스크들은 시스템에 진입하면서 주기에 따라 우선순위가 결정된다. 주기가 짧을수록 우선순위가 된다. 즉, CPU를 더 자주 필요로 하는 태스크에게 더 높은 우선순위를 준다.
• 예를 들어 두 태스크 P1(50,20)과 P2(100,35)가 있으면, P1이 우선순위를 갖는다. P2가 처리되다가도 P1이 들어오면 작업을 멈추고 P1이 우선처리된다. (P(주기,수행시간))
• 태스크가 두 개일 때 RM 스케줄링의 이용률 상한선은 83%이다. 두 태스크의 CPU 이용률을 구해보면 각각 0.40과 0.35로 합치면 약 75%가 된다. 마감시간을 다음 주기가 되기 이전이라고 가정하면, 두 태스크는 모두 마감시간을 충족시킬 수 있다.
• RM 스케줄링은 정적 우선순위 스케줄링의 최적이라고 할 수 있다. 해당 기법으로 스케쥴 할 수 없는 태스크의 집합이 있다하면 다른 정적 우선순위를 사용하는 알고리즘들 역시 이 집합을 스케쥴링 할 수 없기 때문이다.
• 태스크의 개수가 N일 때, N(2^(1/N) - 1)이 태스크들의 CPU 이용률의 합보다 크다면 일반적으로 스케줄링이 가능하다. 이 공식에 무한대를 취해보면 약 0.69 정도로 수렴하는데, 이는 태스크의 개수가 많아지면 CPU의 69%정도밖에 사용할 수 없다는 의미이다. 해당 공식을 만족시키지 못하면 deadline missing이 발생할 수 있다.

EDF(Earliest Deadline First) 스케줄링 : 동적 우선순위 스케줄링

• 마감시간에 따라 우선순위를 동적으로 부여한다. 스케줄링이 일어나는 시점에서 마감시간이 빠를수록 우선순위가 높아진다. 실행해야 될 태스크가 정해지면 그 태스크의 마감시간에 맞추어 우선순위가 재조정된다.
• 마감시간만 스케줄러에게 알려주면 수행시간도 특별히 정해질 필요가 없다. (마감시간만으로 우선순위를 판단하기 때문)
• EDF 스케줄링에서는 CPU 이용률의 합이 100%보다 작기만 하면 수행이 가능하다. 즉, EDF 스케줄링을 사용하면 RM 스케줄링에서 deadline missing이 발생하던 케이스도 해결할 수 있다는 것이다.
• 하지만 이는 이론상 가능한 것이고, 실제로는 문맥교환의 비용 때문에 사실상 100%는 불가능하다.
• 만약 EDF 이용 중 태스크의 CPU이용률 합이 100%보다 큰 과부하가 일어날 경우 연속으로 Deadline missing이 발생하는 Domino effect가 발생할 수 있다. 몇가지 태스크를 포기하는 알고리즘을 추가하는 것으로 도미노 현상을 막을 수 있다.

RM vs EDF

• RM : 구현이 상대적으로 단순하고, 우선순위가 고정되기 때문에 예측성이 좋다. 하지만 CPU의 이용률이 좋지 않다는 단점이 있다.
• 따라서 태스크의 개수가 정해져 있고, 주기와 수행시간 등이 정확히 파악되어 있다면 RM을 사용하는 것이 유리할 수 있다.
• EDF : 이론적으로 최적이고, CPU이용률이 거의 100%에 수렴한다. 하지만 과부하시 도미노 현상이 발생할 위험이 있다.
• EDF는 분명 RM보다 뛰어나지만, 실제로 실시간 시스템을 개발하는 엔지니어들은 어느 한가지를 특별히 선호하지는 않는다.

POSIX 실시간 스케줄링 지원 API : POSIX.1b

• 시스템 콜들의 표준인 POSIX에서 자체적으로 제공한다. 실시간 쓰레드를 위해 두 개의 스케줄링 클래스를 정의한다. (SCHED_FIFO, SHED_RR)
• SCHED_FIFO는 FIFO 큐를 사용하여 먼저 온 것을 먼저 처리하는 정책이다. 스스로 종료되거나 블록될 때까지 CPU할당을 보장한다.
• SCHED_RR은 라운드 로빈 정책으로 쓰레드들에 타임슬라이스를 순환적으로 제공한다.
• 이러한 스케쥴링 정책을 사용할 수 있도록 함수 두개가 제공되는데, attr_getschedpolicy는 현재의 스케쥴링 정책을 가져오는 함수이고, attr_setschedpolicy는 스케줄링 정책을 설정하는 함수이다.
• 실시간 쓰레드임에도 RM이나 EDF가 아니라 FIFO와 RR을 사용하는 이유는, 기본적으로 리눅스 계열 운영체제가 범용 컴퓨팅을 위해 설계된 것이라 커널 내부 구조가 실시간 컴퓨팅을 목적으로 설계되지 않았기 때문이다.
• 아래는 이러한 함수들을 활용하는 예제이다.

#include <pthread.h>
#include <stdio.h>
#define NUM_THREADS 5
int main(int argc, char *argv[])
{
    int i, policy;
    pthread_t tid[NUM THREADS];
    pthread_attr_t attr; /* get the default attributes */
    pthread_attr_init(&attr); /* get the current scheduling policy */
    if (pthread_attr getschedpolicy(&attr, &policy) != 0)
        fprintf(stderr, "Unable to get policy.\n");
    else {
    if (policy == SCHED OTHER)
        printf("SCHED OTHER\n");
    else if (policy == SCHED RR)
        printf("SCHED RR\n");
    else if (policy == SCHED FIFO)
        printf("SCHED FIFO\n");
    } 
    /* set the scheduling policy - FIFO, RR, or OTHER */
    if (pthread_attr_setschedpolicy(&attr, SCHED_RR) != 0)
        fprintf(stderr, "Unable to set policy.\n");
    /* create the threads */
    for (i = 0; i < NUM THREADS; i++)
        pthread_create(&tid[i],&attr,runner,NULL);
    /* now join on each thread */
    for (i = 0; i < NUM THREADS; i++)
    pthread_join(tid[i], NULL);
}
/* Each thread will begin control in this function */
void *runner(void *param)
{
    /* do some work ... */
    pthread_exit(0);
}

• Pthread_attr_t 타입의 구조체 attr과 변수 policy의 포인터를 pthread_attr_getschedpolicy에 넘기면 값이 넘어 오게 되어 있다.
• Pthread_attr_setschedpolicy 함수 호출을 통해 스케줄러를 SCHED_RR로 지정하는 것을 볼 수 있다.