Linux에서 스케줄링

도입

운영체제를 공부하다보니 리눅스는 CFS 스케줄링 방식을 사용한다는 것을 알게 되었다. 이에 조금더 자세히 찾아보게 되었고, linux의 스케줄링에 대해 공부했다. 공부해보니 무조건 CFS를 사용하는건 아니고, 작업의 특성에 따라 달라진다는 것을 알게 되었다.
공부하다가 정리한 내용이라 결론이 궁금한 사람은 마무리 부분만 읽어도 될거 같다.

Scheduling class

리눅스 커널 v2.6.23 부터 scheduling class 라는 것이 도입되었다. 이를 통해 다양한 상황에 맞게 스케줄링 정책을 모듈화할 수 있도록 했다. → 스케줄러 코드의 확장성을 향상

리눅스에서는 스케줄러를 2가지 파트로 나눈다.

💡

1. common part : 코어 스케줄링 파트를 의미한다.

2. specific part : 각 스케줄러마다 다른 특성을 나타내는 파트를 의미한다.

코어 스케줄링 코드에서 specific scheduling class 를 호출하는 식으로 스케줄링이 수행된다. specific part에서는 struct sched_class 구조체를 작성해서 코어에 등록해야한다.

• struct sched_class 구조체

struct sched_class {
	....
    
	void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);
	void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);
	....
    
	void (*check_preempt_curr)(struct rq *rq, struct task_struct *p, int flags);
	struct task_struct *(*pick_next_task)(struct rq *rq);
	....
};

• enqueue_task: 프로세스(task_struct)를 현재 스케줄러가 관리하는 런큐(rq)에 삽입
• dnqueue_task: 프로세스(task_struct)를 현재 스케줄러가 관리하는 런큐(rq)에서 제거
• check_preempt_curr : 프로세스가 생성되거나 wakeup 했을 때, preemption 가능 여부를 체크한다. 가능할 경우 TIF_NEED_RESCHED 가 flag로 설정되어 있다.
• pick_next_task : 런큐(rq)에서 실행하기 적합한 프로세스(task_struct)를 선택한다. 스케줄러에서 가장 핵심적인 부분

---

리눅스 커널에서는 어떤 스케줄링 클래스가 존재할까?

v6.5 기준으로 5개가 존재한다.

// kernel/sched/sched.h - v6.5
extern const struct sched_class stop_sched_class;
extern const struct sched_class dl_sched_class;
extern const struct sched_class rt_sched_class;
extern const struct sched_class fair_sched_class;
extern const struct sched_class idle_sched_class;

모든 프로세스는 하나의 scheduling strategy에 대응되고, 각 scheduling strategy는 하나의 scheduling class에 대응된다. 스케줄러는 위에서 부터 아래로 내려가며 대응되는 스케줄링이 있는지 확인한다.

Scheduling policies

스케줄링 전략을 이야기하기 위해서는 스케줄링 정책도 알아야될 것 같다. 리눅스에서는 6개의 정책이 존재하고, 크게 두 가지로 분류할 수 있다.

time-sharing policies	SCHED_OTHER, SCHED_BATCH, SCHED_IDLE
real-time policies	SCHED_DEADLINE, SCHED_FIFO, SCHED_RR

• 1. Normal policies : normal priority 를 갖는 스레드를 의미한다. 흔히, time-sharing scheduling 이라고 불린다.
• 2. Realtime policies : time-sensitive 스레드를 의미한다. 그리고, 이 스레드들은 time-slice 가 종속되지 않는다.

Scheduling Class	Scheduling policies	Comment
stop_sched_class		따로 스케줄링 정책이 없다. 유저 입장에서 본다면 가장 강력한 우선순위를 가진다.
이 클래스는 cpu migration을 담당하는 커널 스레드에서만 작동된다.
dl_sched_class	SCHED_DEADLINE	스레드에 SCHED_DEADLINE 정책을 설정 시 이 클래스가 사용된다.
rt_sched_class	SCHED_FIFO, SCHED_RR	스레드에 SCHED_FIFO, SCHED_RR 정책을 설정 시 이 클래스가 사용된다.
fair_sched_class	SCHED_OTHER, SCHED_BATCH, SCEHD_IDLE
idle_sched_class		idle_task에 의해서만 선택되는 클래스이다. 이 스레드는 각 cpu 런큐에 실행 가능한 스레드가 없을 경우에 실행된다.

priority

리눅스에서 우선순위는 1~139 를 가지고 있다. 1 ~ 99 는 static priority, 100~139는 dynamic priority로 나눠진다.

• static priority: 스케줄러가 우선순위를 변경할 수 없고, 사용자가 nice() 시스템 콜을 통해서 우선 순위를 조절할 수 있다. SCHED_FIFO, SCHED_RR 타입에 해당 우선순위를 사용한다.
• dynamic priority: 스케줄러가 IO-bound 작업에 대한 보상으 우선순위를 높이거나, CPU-bound 작업에 대해 우선순위를 낮출 수 있다. 이렇게 변경된 우선순위를 작업의 dynamic priority라고 부른다.

CFS

Completely Fair Scheduler의 약자로, time slice에 대한 개념이 없이, ‘CPU 사용 시간 비율’ 개념을 사용한다. 만약 우선순위가 같은 두 개의 프로세스가 존재한다면, 각각 50%씩 CPU 사용 시간을 할당할 것이다.

그런데, 우선 순위가 같더라도 가중치를 다르게 가져가고 싶을 때는 어떻게 할까?

• weight 개념을 도입하여 weight가 클수록 더 많은 CPU 타임을 받게할 수 있다
• [-20, 19]의 범위를 가지는nice 개념을 도입하여 nice 값이 작을수록 더 큰 우선순위를 가진다.

이 내용들은 SCHED_OTHER, SCHED_BATCH 스케줄링 정책에 부합한다. 즉, nice와 weight 개념은 time-sharing 정책에서 사용된다고 할 수 있다.

Scheduling period

CFS는 CPU 사용시간 비율을 할당하기 위해, 스케줄링 주기를 두어 그 주기마다 프로세스들에게 CPU 사용시간을 할당할 것이다. 그런데, 만약 프로세스의 수가 많아진다면, 프로세스가 할당받는 time slice가 작아지고 context switch로 인한 오버헤드도 커질 것이다.

이에 CFS에서는 0.75ms 최소 time slice를 보장해준다.

💡

1. 현재 실행가능한 태스크 개수 <= 8 : 스케줄링 주기를 6ms 로 고정

2. 현재 실행가능한 태스크 개수 > 8 : 현재 실행가능한 태스크 개수 * 0.75ms

virtual time

CFS에서는 각 작업의 실행시간을 누적해서 가지고 있다. CFS에서는 이 값을 통해서 각 작업에게 공정한 시간을 할당하게 된다.

virtual time이라는 개념을 통해 스케줄링이 이루어지는데 다음과 같은 식을 통해 virtual time이 결정된다.

Why does CFS user rb-tree?

min-heap 방식과 rb-tree를 비교하며 알아보자

1. 메모리 연속성

   비교하기 앞서 array와 linkedlist를 비교해보자. array의 경우 메모리에 연속적으로 올라가야하기 때문에, array의 크기가 커질수록 메모리에 적재하는게 쉽지 않을 것이다. linkedlist의 경우 비 연속적인 메모리 기반이기 때문에 부담이 덜할 것이다.

   리눅스에서의 min-heap은 배열로 구현되어 있다. 스케줄링이라는 것은 엄청난 양의 프로세스와 스레드를 관리해야할 것이다. 이 측면에서 보면 rb-tree가 더 유리할 것이라고 생각할 수 있다.

2. 성능

   min-heap을 사용할 경우 최고 우선순위를 가진 프로세스를 찾는 것은 $O(1)$의 시간 복잡도를 가져 $O(log(n))$의 시간 복잡도를 가진 rb-tree보다 빠르지만.

   업데이트, 삭제 연산까지 고려한다면 min-heap은 $O(n)$, rb-tree는 $O(log(n))$을 가지기 때문에 rb-tree가 더 효율적이라고 할 수 있다. 프로세스가 blocked 상태로 전환되기 위해 ruqueue에서 삭제 작업이 이루어진다는 점을 보면,
   삭제 작업이 생각보다 많이 이루어진다는 점에서 미루어보아 rb-tree가 사용되는 이유을 알 수 있을거 같다.

run queue

CPU마다 런큐를 가지고 있고, 각각의 스케줄링 클래스 또한 자신의 런큐를 가지고 있다. 예를들어 dl_sched_class는 dl_rq를 가지고, rt_sched_class는 rt_rq를, fair_sched_class는 cfs_rq를 가질 것이다.

CFS는 virtual time을 기준으로 red-black tree를 정렬한다. 즉, 런큐(rb-tree)에 삽입되어 있는 실행가능한 작업들은 모두 virtual 타임을 기반으로 정렬되어있다.

마무리

지금까지 정리한 내용을 통해, 내가 궁금했던 부분을 해소해보자.

Linux 운영체제는 우선순위가 높은 sched_class 부터 낮은 클래스를 돌면서 스케줄링 가능한 프로세스가 있을 경우 그 프로세스를 선택한다.

// 위에서 부터 내려갈 수록 우선순위가 내려간다.(위에서 아래로 탐색)
extern const struct sched_class stop_sched_class;
extern const struct sched_class dl_sched_class;
extern const struct sched_class rt_sched_class;
extern const struct sched_class fair_sched_class;
extern const struct sched_class idle_sched_class;

// kernel/sched/core.c - v6.5
static inline struct task_struct *pick_task(struct rq *rq)
{
	const struct sched_class *class;
	struct task_struct *p;
	
	// 각각의 sched_class를 돌면서 스케줄링 가능한 작업이 있을 경우 선택
	for_each_class(class) {
		p = class->pick_task(rq);
		if (p)
			return p;
	}

	BUG(); /* The idle class should always have a runnable task. */
}

각각의 sched_class는 스케줄링을 위한 rq를 가질 것이고 rq에 스케줄 가능한 작업이 있을 경우 해당 작업이 선택될 것이다.

만약 hard realtime 작업의 경우 dl_sched_class의 rq에 들어있을 것이기 때문에 다른 작업들보다 더 빠르게 수행될 것이다. 추가로 DEADLINE 정책에서는 rq는 deadline을 기반으로 rb-tree에 정렬되어있고 EDF 스케줄링 방식을 사용할 것이다.

soft realtime 작업은 rt_sched_class의 rq 에 있을 것이므로, hard realtime 작업이 rq에 없다면 선택될 것이다. 내부적으로는 RR, FIFO 스케줄링은 사용한다.

마지막으로 normal task는 fair_sched_class의 rq에서 관리되며, 스케줄링 알고리즘은 CFS, rq는 vruntime 기반의 rb-tree 자료구조 형태로 이루어져 있다고 할 수 있겠다.

결국 알고 싶던 내용은 위 세문장이 전부인거 같은데, 너무 힘들게 돌아왔다 ㅋ쿠ㅜ 개인적으로 schduling class, run queue 개념이 이해에 도움이 된 것 같다.

참고

[리눅스 커널] Scheduler - Basic