CSF 스케줄러(공정 스케줄러)와 구성요소

CSF(Completely Fair Scheduler ) 스케줄러란?

2.6.23커널 버전에서 등장한 리눅스의 일반 프로세스용 스케줄러입니다.

프로세스의 응답시간을 빠르게 하고 시스템 사용률을 최대화 하기 위해 사용됩니다.

 

CFS를 이루는 구성요소(개념)

타임슬라이스(time slice)

프로세스가 부여한 실행 시간입니다. 주어진 타임슬라이스값을 다 사용하면 선점 스케줄링 대상이 되고

이후 문맥교환이 이루어집니다.

시스템 클럭이 한 틱 지날 때 마다 그 틱에 해당하는 시간만큼 타임슬라이스가 줄어듭니다, 0이되면 타임슬라이스가 0보다 큰 프로세스가 해당 프로세스를 선점합니다.

기본값은 1ms입니다. 이 값을 최소 세밀도(minimum granualarity)라고합니다.

 

프로세스 우선순위(priority)

스케줄러가 다음에 실행할 프로세스를 선택하는 기준입니다.

실행가능한 프로세스 중 타임슬라이스가 남아 있고 우선순위가 가장 높은 프로그램을 스케줄러는 실행합니다.

0 ~ 99 : 실시간 프로세스

100 ~ 139 : 일반 프로세스

리눅스 커널의 우선순위 단위

1. nice값

-20 ~ +19 까지의 값을 가지며 기본값은 0입니다. 이 값은 커널 공간에서 100~139 사이 값으로 변환되어 관리합니다.

nice값이 낮을수록(nice하지 않을수록) nice값이 높은 프로세스보다 더 많은 할당시간을 가지게 됩니다. 

스케줄러에서는 절대적인 nice값이 아니라 nice값에 따른 가중치에 따라 타임슬라이스를 할당받습니다.

2. 실시간 우선 순위

0 ~ 99 까지의 값을 가집니다. nice값과 다르게 클수록 우선순위가 높습니다. 모든 실시간 프로세스는 일반 프로세스보다 우선순위가 높습니다, 즉 실시간 우선 순위값과 nice값은 별도의 값입니다.

 

아래 명령어를 통해 프로세스 목록과 각각의 실시간 우선 순위(rtprio)를 확인할 수 있습니다. 

- 값은 실시간 프로세스가 아니라는 의미입니다.

ps -eo state,uid,pid,ppid,rtprio,time,comm

 

가상실행시간(vruntime)

프로세스가 실행한 시간을 정규화한 값입니다.

CFS는 실행 대기 프로세스 중 가상실행시간이 가장 낮은 프로세스를 다음 실행 프로세스로 선택합니다.

우선순위가 높을수록 vruntime이 서서히 증가합니다.

 

CFS는 가상실행시간이 낮은 프로세스를 찾기 위해 레드블랙트리(red-black tree)알고리즘을 사용합니다.

 

vruntime은 특정 프로세스의 실행시간을 정확하게 반영하여, 다음 실행 프로세스 선택의 기준으로 작용합니다, 아래는 kernel 2.6버전의 vruntime을 기록하는 커널의 메소드입니다.

1. update_curr

static void update_curr(struct cfs_rq *cfs_rq) // 현재 함수의 실행시간을 계산에 delta_exec에 저장
 {
         struct sched_entity *curr = cfs_rq->curr;
         u64 now = rq_of(cfs_rq)->clock;
         unsigned long delta_exec;
 
         if (unlikely(!curr))
                 return;
 
         /*
          * Get the amount of time the current task was running
          * since the last time we changed load (this cannot
          * overflow on 32 bits):
          * 지난번 갱신 시점 이후 현재 작업이 실행된 시간을 구합니다. (32bit를 넘을 수 없음)
          *
          */
         delta_exec = (unsigned long)(now - curr->exec_start);
         if (!delta_exec)
                 return;
 
 		/*
        * 계산된 실행값을 __update_curr함수에 전달합니다,
        * __update_curr함수는 전체 실행중인 프로세스 갯수를 고려해 가중치를 계산합니다.
        * 이 가중치 값을 추가하여 현재 프로세스의 vruntime에 저장합니다.
        */
         __update_curr(cfs_rq, curr, delta_exec);  
         curr->exec_start = now;
 
         if (entity_is_task(curr)) {
                 struct task_struct *curtask = task_of(curr);
 
                 trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime);
                 cpuacct_charge(curtask, delta_exec);
                 account_group_exec_runtime(curtask, delta_exec);
         }
 }

2. __update_curr

/* 현재 작업의 실행시간 통계를 갱신합니다. 해당 스케줄링 클래스에 속하지 않는 작업은 무시합니다. 
* 시스템 타이머를 통해 주기적으로 실행되며, 프로세스가 실행 가능 상태로 바뀌거나 대기상태가 되어 실행이 중단되어도
* 호출됩니다.
*/
static inline void __update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr,
               unsigned long delta_exec)
 {
         unsigned long delta_exec_weighted;
 
         schedstat_set(curr->exec_max, max((u64)delta_exec, curr->exec_max));
 
         curr->sum_exec_runtime += delta_exec;
         schedstat_add(cfs_rq, exec_clock, delta_exec);
         delta_exec_weighted = calc_delta_fair(delta_exec, curr);
 
         curr->vruntime += delta_exec_weighted;
         update_min_vruntime(cfs_rq);
 }

 

CFS의 프로세스 추가,선택,삭제

위에서 말씀드린대로 CFS에서는 레드블랙트리(rbtree) 알고리즘을 이용해 vruntime이 가장 작은 프로세스를 선택합니다.

출처 : 위키백과

트리에 프로세스 추가

sched_fair.c 파일 안에 __enqueue_entity에 의해 추가됩니다.

 /*
  * enqueue_entity 함수에 의해 실행됩니다
  * enqueue_entity에서 하는일
  * 1. vruntenqueue_entity에서 하는일ime을 갱신하기 전에, update_curr() 함수를 호출해 min_vruntime을 조정합니다.
  * 2. 실행시간과 관련된 통계값을 '현재 값'으로 갱신합니다.
  *
  * Enqueue an entity into the rb-tree
  * 레드블랙트리에 프로세스 추가
  */
 static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
         struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
         struct rb_node *parent = NULL;
         struct sched_entity *entry;
         s64 key = entity_key(cfs_rq, se);
         int leftmost = 1;
 
         /*
          * 레드블랙트리에 추가할 위치를 찾습니다 
          */
         while (*link) {
                 parent = *link;
                 entry = rb_entry(parent, struct sched_entity, run_node);
                 
                 /* 키 값이 현재 노드의 키 값보다 작은 경우, 왼쪽 자식 노드로 이동 
                    큰 경우에는 오른쪽으로 이동합니다.
                    이동한 자식노드가 없으면 link값이 null이 되어 루프가 끝나게 됩니다.
                    
                    노드가 왼쪽으로만 이동했다면 leftmost는 1로 유지됩니다.
                 */
                 if (key < entity_key(cfs_rq, entry)) {
                         link = &parent->rb_left;
                 } 
                 /* 한번이라도 오른쪽으로 이동한적이 있다면 추가할 프로세스는 
                    최좌측으로 이동 할 수 없으므로 leftmost값을 0으로 설정됩니다.
                 */
                 else { 
                         link = &parent->rb_right;
                         leftmost = 0;
                 }
         }
 
         /*
          * 자주 사용되는 가장 왼쪽 노드(CFS에서 다음 작업을 선택하는 노드) 항목을 캐시에 저장합니다. 
          */
         if (leftmost)
                 cfs_rq->rb_leftmost = &se->run_node;
 
 		/*
        * 새로 추가할 프로세스를 자식 노드로 만듭니다.
        */
         rb_link_node(&se->run_node, parent, link);
         rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
 }

 

트리에서 프로세스 제거

sched_fair.c 파일 안에 dequeue_entity에 의해 삭제됩니다.

static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
         /*
         * rb_leftmost 캐시 갱신
         */
         if (cfs_rq->rb_leftmost == &se->run_node) {
                 struct rb_node *next_node;
 				
                /* 제거할 프로세스가 가장 왼쪽 노드였다면 다음 왼쪽노드를 찾아서 캐시합니다. */
                 next_node = rb_next(&se->run_node);
                 cfs_rq->rb_leftmost = next_node;
         }
 		 /*
         * 레드블랙트리에서 프로세스 제거
         */
         rb_erase(&se->run_node, &cfs_rq->tasks_timeline);
 }

 

다음 작업 선택

/**
*  CFS가 다음에 실행해야 할 프로세스를 반환하는 함수
*/
static struct sched_entity *__pick_next_entity(struct cfs_rq *cfs_rq)
 {
         struct rb_node *left = cfs_rq->rb_leftmost; 
         # rb_leftmost 캐시된 가장 왼쪽 노드 포인터
 
         if (!left)
                 return NULL;
 
         return rb_entry(left, struct sched_entity, run_node);
 }

만들어진 트리에서  vruntime값이 가장 작은, 즉 CFS에 의해 선택되는 프로세스는 가장 왼쪽에 있는 노드입니다.

해당 노드가 null을 반환하게 된다면 CFS는 아무일도 하지 않는 비가동(idle) 작업을 실행합니다.

 

스케줄링

schedule() 함수에 의해 스케줄링이 됩니다.

스케줄링 중에 pick_next_task() 함수를 통해 가장 높은 우선순위 스케줄러 클래스부터 돌아가면서 가장 높은 우선순위 프로세스를 찾아냅니다.

/*
 * 가장 우선순위가 높은 작업을 선택하는 함수
 */
 static inline struct task_struct *
pick_next_task(struct rq *rq)
{
        const struct sched_class *class;
        struct task_struct *p;

        /*
         * Optimization: we know that if all tasks are in
         * the fair class we can call that function directly:
         */
        if (likely(rq->nr_running == rq->cfs.nr_running)) {
                p = fair_sched_class.pick_next_task(rq);
                if (likely(p))
                        return p;
        }

        class = sched_class_highest;
        /*
        * 우선순위가 높은 순서대로 돌아갑니다.
        * null이 아닌 값을 처음으로 반환하는 클래스의 프로세스를 다음 실행 프로세스로 선택합니다.
        */
        for ( ; ; ) {
                p = class->pick_next_task(rq);
                if (p)
                        return p;
                class = class->next;
        }
}

 

휴면(sleep)상태와 대기(blocked)상태

출처 : http://nyx.skku.ac.kr/wp-content/uploads/2015/03/Lecture-7-Process-Management.pdf

 

위 두가지 상태의 작업은 실행 불가능한 상태입니다.

어떤 작업이 두 상태가 되는 조건은 다양합니다.

일정 시간이 지나 상태가 변하거나, 파일 입출력, 하드웨어 이벤트, 사용중인 커널의 세마포어를 얻으려는 경우에도 대기상태가 됩니다.

하지만 어떤 이유건 커널에서의 동작은 동일합니다.

 

1. 작업이 스스로 대기 상태임을 표시

2. 대기열에 들어감

3. 실행 가능한 프로세스의 레드블랙트리에서 자신을 제거

4. schedule() 함수를 통해 새 프로세스를 선택해 실행합니다.

 

깨어나는 과정은 위 과정의 역순으로 진행됩니다.

작업을 깨우는 일은 대기열에 들어가 있는 모든 작업을 깨웁니다.