Completely Fair Scheduler

File list

• kernel/sched.c: 기본 스케줄러 코드.
• kernel/sched_fair.c: 리눅스의 일반 프로세스용 스케줄러 클래스.

시간 기록

각 프로세스별로 공정하게 할당된 몫만큼만 프로세서를 사용해야 하므로 프로세스의 실행시간을 기록해야 한다. linux/sched.h에 정의된 struct sched_entity라는 스케줄러 단위 구조체를 사용해 관련 정보를 저장한다.

프로세스 서술자로 사용하는 struct task_struct구조체의 se항목으로 정의되어 있다.

struct task_struct구조체의 vruntime변수에는 프로세스의 가상 실행시간이 저장되는데, 실행 가능한 프로세스 개수에 따라 정규화한 (또는 가중치를 적용한) 실제 실행시간 (프로세스가 실행된 시간)을 뜻한다. 가상 실행시간은 나노초 단위를 사용한다.

가상실행시간은 kernel/sched_fair.c에 정의된 update_curr()함수가 처리한다.

프로세스 선택

가상실행시간(vruntime)을 Key값으로 하는 Red–black tree¹를 사용한다.

• pick_next_entity()
• enqueue_entity(): frok()를 통해 프로세스가 만들어질 때 트리에 추가한다.
• dequeue_entity(): 프로세스가 대기상태(싱행 불가능한 상태)가 되거나 종료되면(없어지는 경우) 프로세스를 트리에서 제거한다.

스케줄러 진입 위치

프로세스 스케줄링 작업을 시작하는 곳은 kernel/sched.c파일에 정의되어 있는 schedule()함수다.

• pick_next_task(): 가장 높은 우선순위의 스케줄러 클래스부터 돌아가면서, 우선순위가 가장 높은 클래스의 우선순위가 가장 높은 프로세스를 찾아낸다.

대기열

대기열(wait queues)을 이용해 휴면 상태를 처리한다. 대기열은 특정 조건이 일어나기를 기다리는 단순한 프로세스 목록이다. 대기열은 커널에서 wake_queue_head_t형으로 정의된다.

• DECLARE_WAITQUEUE(): 정적으로 대기열을 생성한다.
• init_waitqueue_head(): 동적으로 대기열을 생성한다.

휴면과 깨우기 작업을 올바로 구현하지 못하면 경쟁 조건 (race condition)이 발생할 수 있다.

휴면

휴면 처리 작업에 널리 사용하는 간단한 인터페이스가 몇 가지 있다. 하지만 이런 인터페이스에는 경쟁 조건이 발생할 수 있다. 작업을 깨워야 하는 조건이 발생한 이후에 휴면 삳ㅇ태롤 들어가는 일이 벌어질 수 있다.이렇게 되면 이 작업은 영원히 휴면 상태를 벗어날 수 없다. 그래서 커널이 권장하는 휴면 처리 과정은 약간 복잡하다.

DEFINE_WAIT(wait); /* 매크로를 이용해 대기열에 추가할 항목을 만든다. */

/* 'q'는 휴면 상태인 작업이 들어갈 대기열이다. */

add_wait_queue(q, &wait);
while (!condition) { /* condition은 기다리는 조건이 발생한 경우를 뜻한다. */
    prepare_to_wait(&q, &wait, TASK_INTERRUPTIBLE);
    if (signal_pending(current)) {
        /* Signal process. */
    }
    schedule();
}
finish_wait(&q, &wait);

작업을 대기열에 추가할 때 다음 작업을 거친다.

대기열을 사용하는 직접적인 예로 inotify파일 서술자에서 읽기 작업을 처리하는 fs/notify/inotify/inotify_user.c파일의 inotify_read()함수를 들 수 있다.

깨어남

작업을 깨우는 일은 wake_up()함수를 통해 처리하는데, 이 훔수는 주어진 대기열에 있는 모든 작업을 깨운다.

wake_up()함수는 아래와 같은 작업을 거친다.

1. try_to_wake_up(): 작업상태를 TASK_RUNNING으로 변경.
2. enqueue_task(): 작업을 다시 rbtree에 추가한다.
3. 깨어난 작업의 우선순위가 지금 실행중인 작업의 우선순위보다 높으면 need_resched값을 설정한다.

선점과 컨텍스트 전환

실행 중인 한 작업에서 다른 작업으로 전환하는 것을 뜻하는 컨텍스트 전환(Context switching)은 kernel/sched.c에 정의된 context_switch()함수를 통해 처리한다.

context_switch()함수는 아래의 두 가지 작업을 처리한다.

• asm/mmu_context.h에 정의된 switch_mm()함수를 호출해 이전 프로세스의 가상 메모리 매핑(Virtual memory mapping)을 새 프로세스의 것으로 바꾼다.
• asm/system.h에 정의된 switch_to()함수를 호출해 이전 프로세스의 프로세서 상태를 현재 프로세스의 프로세서 상태로 바꾼다. 이 과정에는 아래의 정보를 저장하고 복원하는 일이 포함된다.
  • 프로세서 단위로 관리가 필요한 스택정보
  • 프로세서 레지스터 등의 특정 하드웨어 관련 정보

need_resched flag

need_resched플래그는 커널이 언제 재스케줄이 필요한지 알려준다. 아래는 값을 확인하고 조정하는 함수 목록이다.

• set_tsk_need_resched(): 주어진 프로세스의 플래그를 설정한다.
• clear_tsk_need_resched(): 주어진 프로세스의 플래그를 해제한다.
• need_resched(): 플래그 값을 확인한다.

사용자 공간으로 돌아가거나 인터럽트 처리를 마치고 돌아갈 때마다 need_resched플래그 값을 확인한다.

사용자 선점과 커널 선점

사용자 선점은 다음과 같은 경우 발생한다.

• 시스템 호출에서 사용자 공간으로 돌아갈 때
• 인터럽트 처리를 끝내고 사용자 공간으로 돌아갈 때

커널 선점은 다음과 같은 경우 발생한다.

• 인터럽트 처리를 마치고 커널 공간으로 돌아갈 때
• 커널 코드가 다시 선점 가능한 상태가 되었을 때
• 커널 내부 작업이 명시적으로 schedule()함수를 호출하는 경우
• 커널 내부 작업이 중단돼 대기 상태가 되는, 그래서 결국 schedule() 함수를 호출하게 되는 경우

더욱 구체적인 내용이 필요.

실시간 스케줄링 정책

kernel/sched_rt.c에 정의된 별도의 특별한 스케줄러를 사용하여 실시간 정책을 관리한다.

• SCHED_FIFO: 타임슬라이스 할당이 따로 없는 간단한 FIFO구조의 스케줄링 알고리즘.
• SCHED_RR: 각 프로세스가 미리 정해진 타임 슬라이스를 다 사용할 때까지만 실행된다는 점만 제외하면 SCHED_FIFO와 동일하다. 즉 SCHED_RR은 타임슬라이스가 있는 SCHED_FIFO이다.
• SCHED_NORMAL: 비실시간 스케줄링 정책.

실시간 동작

실시간 스케줄링 정책은 아래와 같은 동작이 있다.

• 부드러운 실시간 동작 (Soft reall-time behavior): 커널이 일정한 기한 안에서 애플리케이션을 스케줄링하려고 노력하지만 항상 그렇게 된다는 것을 보장하지는 않는다.
• 엄격한 실시간 동작 (Hard reall-time behavior): 항상 주어진 기한 내에 모든 스케줄링 요구사항을 만족하는 시스템을 말한다.

리눅스는 실시간 작업 스케줄링에 대해 어떤 것도 보장하지 않는다. ²

실시간 우선순위는 0 부터 MAX_RT_PRIO - 1사이의 값을 가질 수 있다. MAX_RT_PRIO의 기본값을 100이다.

스케줄러 관련 시스템 호출

Favorite site

• CFS에 대한 설명
• linux kernel 강좌 1 - CFS ( Completely Fair Scheduler ) 스케쥴러

References