Ch4. Process Scheduling

프로세스 스케줄러는 어떤 프로세스를 언제 얼마나 실행할지 결정한다. 한정된 자원과 프로세서 타음을 프로세스들에게 나누어 제공한다. 스케줄러의 결정에 의해 시스템을 가장 효율적으로 사용하고 유저들에게 동시에 실행되는 여러 프로세스를 제공할 수 있다.

1. Multitasking

한개 이상의 프로세스를 동시에 interleave하여 실행할 수 있는 운영체제를 멀티태스킹 운영체제 라고 한다. 리눅스에서는 여러 프로세스가 메모리에 존재하지만, 오직 하나만 실행가능한 상태이다.
멀티태스킹 운영체제는 cooperative한 것과 preemptive한 것 두가지로 나뉜다. 리눅스를 비롯한 대부분의 현대 운영체제들은 preemptive한 멀티태스킹을 구현한다. preemptive한 멀티태스킹에선 스케줄러가 어떤 프로세스를 정지하고 새 프로세스를 시작시킬지 결정한다. 프로세스가 실행되는 시간은 보통 지정되어 있는데, 이를 timeslice라고 한다. 많은 운영체제에서 timeslice를 동적으로 계산하여 지정하는데, 리눅스의 스케줄러는 timeslice 그 자체를 사용하지 않는다.

2. Linux's Process Scheduler

리눅스 2.5 버전에서는 O(1) 스케줄러를 적용하여 기존 스케줄러의 한계를 바로잡았다. 허나 시간이 지나면서 상호작용이 필요한 프로세스들을 스케줄링하는데 심각한 문제를 보이게 되었다.
리눅스 2.6 버전에서는 O(1) 스케줄러의 상호작용 성능을 향상시켜 발표하였고, 후에 Completely Fair Scheduler, 혹은 CFS라고 하여 2.6.23버전에 탑재되었다.

3. Policy

정책은 스케줄러가 어떤것을 언제 실행시킬지 결정하는 행위이다. 프로세서 타임을 최적으로 활용하기 위해선 스케줄러의 역할이 중요하다.

3.1. I/O-Bound VS Processor-Bound Processes

프로세스는 그 성향에 따라 두가지로 분류될 수 있다. I/O-Bound의 프로세스는 대부분의 시간을 I/O 요청을 기다리는데 시간을 사용하는 프로세스로, 짧은 시간동안만 실행된다. Processor-Bound의 프로세스는 대부분의 시간을 코드를 실행하는데 이용된다.
스케줄링 정책은 빠른 프로세스 응답속도(low latency)와 시스템 사용을 극대화(high throughput)하는 방향으로 설계되어야한다. 이 목표를 달성하기 위해 리눅스의 스케줄러는 I/O-bound 프로세스를 더 선호함으로써 좋은 상호작용 반응과 성능을 보여준다.

3.2. Process Priority

보통 스케줄링 알고리즘은 우선순위를 베이스로 한다. 리눅스 커널은 우선순위의 범위를 크게 두가지루 나누었다. 첫번째는 nice value이며, -20 ~ 19사이의 값을 갖는다. 기본값은 0이다. Nice value가 클수록 우선순위는 낮아진다(다른 프로세스들에게 Nice 해지기 때문에 양보하면서 우선순위가 낮아진다고 이해하면 편하다). Nice 값이 적은 프로세스는 시스템 프로세서의 큰 비율을 할당받는다. 두번째는 real-time priority이다. 0-99사이의 값을 가지며, nice value와 다르게, real-time 우선순위도는 값이 높을수록 높은 우선순위를 갖는다. 리눅스는 real-time 우선순위를 유닉스의 표준(특히 POSIX.1b)과 연관지어 구현한다.

3.3. Timeslice

Timeslice는 태스크가 preempted되기 전까지 얼마나 오래 실행될 수 있는지 표현한다. 스케줄러가 이 값을 설정하는데, 타임슬라이스가 너무 길게 설정하면 상호작용 성능이 떨어지고, 타임슬라이스를 너무 짧게 설정하면 프로세서 타임의 대부분이 프로세스의 전환에 사용될 가능성이 높다.
리눅스의 CFS 스케줄러는 타임슬라이스를 직접적으로 설정하지 않는 대신 프로세스에 프로세서의 일부분을 할당한다. 만약 현재 실행중인 프로세스보다 더 적은 양의 프로세서를 할당받았다면, 현재 프로세스를 preempt하고 해당 프로세스를 실행한다.

3.4. Scheduling Policy in Action

Interactive한 프로세스는 필요할 때 바로 쓸 수 있도록 프로세서 타임을 가지고 있어야 하며, 프로세스가 깨어나는 순간 바로 다른 프로세스를 preempt 할 수 있도록 하기 위해 스케줄러는 interactive한 프로세스에 프로세서를 더 많이 할당하는 것이 이상적이라 할 수 있다. 다양한 운영체제에서 interactive한 프로세스에 높은 우선순위를 부여한다. 리눅스는 다른 운영체제들과 방식에서 차이가 있는데, 리눅스는 interaction이 많은 프로세스에게 프로세서의 일부분을 보장한다.
(텍스트 편집기와 비디오 인코더 관련 예제가 있는데, 어떻게 보장하는지는 정확히 이해가 안됨)

4. Linux Scheduling Algorithm

4.1. Scheduler Classes

리눅스의 스케줄러는 클래스 단위로 모듈화 되어있다. 각각의 스케줄러 클래스마다 다른 알고리즘이 공존하며, 우선순위도 존재한다. 베이스 스케줄러는 각각의 스케줄러 클래스를 우선순위대로 순회한다. 리눅스의 CFS는 SCHED_NORMAL로 분류되어있다.

4.2. Process Scheduling in Unix Systems

현대 운영체제는 두가지 개념을 공통적으로 이용한다. Timeslice는 얼마나 오래 프로세스가 실행될 것인지를 나타낸다. Process Priority는 그 값이 높은 프로세스일수록 더 자주 실행되고, 더 높은 timeslice 값을 부여받게 된다. Unix에서는 priority를 nice 값의 형태로 유저 스페이스로 옮겼으나, 여러 문제가 발생했다.
첫째로 각각의 nice 값에 얼마만큼의 absoulte timeslice를 할당하는지에 대한 문제이다.두번째는 상대적인 nice 값과, nice값을 timeslice와 매핑하는 것이다. nice 값이 얼마느냐에 따라 그 결과가 다르다([100,95]와 [10,5]는 상대적인 차이는 같으나, 후자의 경우 두 프로세스의 timeslice가 두배 차이남). 셋째로 nice값을 timeslice와 매핑한다면 absolute timeslice를 할당해야한다. 많은 운영체제에서는 timeslice를 타이머 틱의 정수배로 정한다. 네번째와 다섯번째는 interactive한 태스크를 최적화하고자 하는 우선순위 기반의 스케줄러가 어떤 프로세스를 깨울지 정하는데 발생하는 문제이다. CFS는 variable switching rate를 통해 문제를 해결한다.

4.3. Fair Scheduling

CFS의 기본 개념은 간단하다. 시스템이 이상적이고 완벽하게 멀티태스킹 되는 프로세서를 가지고있다 가정하는 것이다. 그런 경우, 모든 프로세스가 1/n 만큼의 프로세서 타임을 할당받고, 각각의 프로세스는 굉장히 짧은 시간 실행되도록 스케줄될 것이다. CFS는 또한 각각의 프로세스를 round-robin으로 실행시킬 것이다(가장 적게 실행된 프로세스를 다음에 실행시키는 것). CFS는 nice값을 프로세서의 부분을 할당할 가중치로써 이용한다.
CFS는 실질적인 timeslice를 계산하기 위해 무한히 작은 값으로 추정한다. 이를 targeted latency라고 하며, 이 값이 작을수록 더 높은 interactivity를 제공, 완벽한 멀티태스킹을 제공하나 switching cost가 높아져 전반적인 throughput이 안좋다.
프로세스가 무한히 많아지면 각각의 프로세스가 실제로 실행되는 시간이 0에 가까워지므로, CFS는 minimum granularity를 두어 각각의 프로세스에 할당가능한 최소 시간을 제한한다.
CFS는 nice 값의 차이만큼 계산하여 상대적인 값으로 프로세서 타임을 분할하여 할당한다. 또한 nice 값은 기하학적 차이만큼 영향을 미친다.

5. Linux Scheduling Implementation

5.1. Time Accounting

시스템 시간으로 틱이 지날 때 마다 실행중인 프로세스의 timeslice가 틱의 주기만큼 감소된다. Timeslice가 0이 되면, 현재 프로세스는 preempt되고, timeslice가 0이 아닌 다른 프로세스가 실행된다. CFS는 scheduler entity structure인 struct sched_entity 구조체를 이용해 정보를 관리한다. 이 구조체는 process descriptor에 내장되어있고, se라는 멤버 변수로써 존재한다.

struct sched_entity {
	struct load_weight		load;
    struct rb_node			run_node;
    struct list_head		group_node;
    unsigned int			on_rq;
    u64						exec_start;
    u64						sum_exec_runtime;
    u64						vruntime;
    u64						prev_sum_exec_runtime;
    u64						last_wakeup;
    u64						avg_overlap;
    u64						nr_migrations;
    u64						start_runtime;
    u64						avg_wakeup;
}

CFS는 vruntime을 통해 프로세스가 얼마나 오래 실행되었고, 얼마나 더 오래 실행되어야하는지 처리한다.

5.2. Process Selection

vruntime으로 완벽하게 멀티태스킹 하기엔 무리가 있기 때문에, CFS는 프로세스의 vruntime을 균형잡으려 한다. 따라서 CFS는 다음에 실행한 프로세스를 찾기 위해 프로세스의 vruntime이 가장 낮은 프로세스를 선택한다. CFS는 Red-Black tree를 통해 실행가능한 프로세스를 관리하고 vruntime이 작은 프로세스를 빠르게 찾는다. 종합하면, CFS에서 프로세스를 선택하는 알고리즘은 rbtree에서 가장 왼쪽에 있는 노트를 실행하는 것이다.

5.3. Scheduler Entry Point

프로세스 스케줄의 주요한 진입점은 schedule() 함수이다. 이는 커널의 남은 부분이 프로세스 스케줄러를 깨워 프로세스 스케줄링을 하도록 한다. CFS 스케줄러는 높은 우선순위의 스케줄러 클래스부터 차례로 탐색하며 실행 가능한 프로세스가 있는지 확인한다.

5.4. Sleeping and Waking Up

태스크는 어떠한 이벤트를 기다리느라 sleep 상태에 놓인다. 하드웨어 이벤트, 파일 I/O일 수 있고, 혹은 커널의 semaphore를 얻기위해 대기하는 중일때 역시 sleep 상태에 놓인다. 어떤 경우이든, 태스크는 스스로 sleep 상태에 들어가고 wait queue에 넣는다. Runnable한 태스크로 이루어진 red-black tree에서 스스로를 제거하고, 다음 프로세스를 실행하기 위해 schedule()을 실행한다.
Sleeping과 Waking Up에서 가장 중요한 것은 race condition을 피하는 것이다. 만약 sleeping 상태에 들어가는 동안 기다리는 event가 발생하면 해당 프로세스는 무한히 깨어날 수 없을 수 있다. 따라서 해당 로직을 조금 복잡하게 구현하는데, 본문 예시에서는 원하는 이벤트가 발생했는지 두번 확인함으로써 해결한다.
Waking Up에선, 태스크의 상태를 RUNNING으로 바꾸고, red-black tree에 해당 태스크를 추가한다. 만약 깨어난 태스크가 최근의 태스크보다 우선순위가 높다면 need_resched를 설정한다. 태스크가 깨어날때 spurious wake-ups(가짜 깨우기)가 존재한다는 사실을 조심해야한다. 태스크가 깨어났다는 것이 꼭 자신이 기다리던 이벤트가 발생했다는 것은 아니다.

6. Preemption and Context Switching

context_switch()에 의해 실행가능한 태스크에서 다른 태스크로 전환이 발생하고, 이는 크게 두 작업으로 나뉜다. switch_mm()은 가상 메모리 매핑을 전환하고, switch_to()는 프로세서의 상태를 전환한다.
커널은 need_resched 플래그를 제공하여 리스케줄이 필요한지 확인한다. 이 플래그는 프로세스가 preempted 되어야 할 때나 context switch가 일어나야할 때(현재 실행중인 프로세스보다 더 높은 우선순위의 프로세스가 깨어났을 때) 설정된다. 커널은 이 플래그를 확인하고 schedule() 함수를 실행한다.
플래그는 프로세스별로 설정되며, process descriptor 안의 변수를 확인하는게 훨씬 빠르기 때문에 전역으로 설정되지 않는다.

6.1. User Preemption

User Preemption은 커널이 유저 스페이스로 진입할때, need_resched가 설정되어 스케줄러가 실행될 때 발생한다. 이는 결국 system call로부터 user-space로 돌아갈 때, interrupt handler로부터 user-space로 돌아갈때 user preemption이 발생한다고 할 수 있다.

6.2. Kernel Preemption

리눅스 커널은 fully preemptive한 커널이다. 따라서 커널이 리스케줄하기 안전한 상태라면 태스크를 언제든 preempt할 수 있다.

리스케줄하기 안전한 상태의 커널 = lock을 가지고 있지 않은 상태

Kernel preemption을 지원하기 위해, preempt_count를 추가하였다. preempt_count는 0에서 시작하여 lock을 획득하면 증가하고, lock을 해제하면 감소한다. 이 값이 0이 아니면 현재 lock을 획득한 상태로, 리스케줄을 할 수 없다.
혹은 커널의 태스크가 block 되거나, schedule()함수를 호출해도 kernel preemption이 발생할 수 있다.
정리하면 다음과 같은 상황에 kernel preemption이 발생한다

• kernel-space로 돌아가기 전에 interrupt handler가 종료된 경우
• 커널 코드가 preemptible한 경우
• 커널의 태스크가 schedule()함수를 호출하는 경우
• 커널의 태스크가 block되는 경우(결론적으로 schedule()함수를 호출함)

7. Real-Time Scheduling Policies

리눅스는 SCHED_FIFO와 SCHED_RR 두가지의 실시간 스케줄링 정책을 제공한다. 이 실시간 스케줄링 정책들은 CFS가 아닌 특별한 real-time scheduler에 의해 관리된다.
SCHED_FIFO는 timeslice 없이 first-in-first-out 알고리즘으로 스케줄링한다. SCHED_FIFO가 실행 가능해지면 그것이 block 되거나 프로세서를 양보하기 전까지 이론상 무한히 실행된다. 더 높은 우선순위를 가진 SCHED_FIFO나 SCHED_RR 태스크만이 preempt할 수 있다. 같은 우선순위라면 round-robin으로 실행한다.
SCHED_RR은 미리 정해진 timeslice를 다 소진할 때 까지 각 프로세스를 실행할수 있다는 점만 제외하면 SCHED_FIFO와 거의 같다. 즉 SCHED_RR은 SCHED_FIFO에 timeslice가 있는 형태이다.
실시간 스케줄링 정책은 static priorities로 구현된다. 동적인 할당은 허용하지 않는다.
리눅스의 실시간 스케줄링 정책은 soft real-time behavior를 제공한다. 이는 어떤 시간제한까지 스케줄 하려고 하나, 스케줄을 보장하진 않는 방법이다. 리눅스는 실시간 태스크를 스케줄링하는것을 보장하지 않는다.
실시간 우선순위 범위는 0부터 MAX_RT_PRIO - 1까지이다. MAX_RT_PRIO의 기본 값은 100이다. 또한 SCHED_NORMAL 태스크의 nice값과 공간을 공유하는데, 이 때문에 -20 ~ 19의 범위를 가지는 nice 값은 priority space에서 100에서 139의 값을 부여받는다.

8. Scheduler-Related System Calls

8.1. Scheduling Policy and Priority-Related System Calls

sched_setscheduler(); // 스케줄링 정책과 실시간 우선순위를 설정
sched_getscheduler(); // 스케줄링 정책과 실시간 우선순위를 받아옴

sched_setparam(); // 실시간 우선순위를 설정
sched_getparam(); // 실시간 우선순위를 받아옴

nice(); // 프로세스의 정적 우선순위를 주어진 양만큼 증가

8.2. Processor Affinity System Calls

리눅스의 스케줄러는 hard processor affinity를 강요한다. Hard affinity란 동일 프로세서에서 프로세스가 실행되도록 하는 것이다. 이 정보는 비트마스크로써 저장되어 있고, 각 비트가 시스템에서 사용 가능한 프로세서에 매칭된다. 기본적으로 모든 비트가 설정되어 프로세스는 어느 프로세서에서나 실행 가능하다. 비트마스크 설정과 관련된 시스템 콜은 아래와 같다

sched_setaffinity(); // 비트마스크 설정
sched_getaffinity(); // 현재 cpus_allowed 비트마스크를 반환

프로세스가 생성되면, 부모의 affinity mask를 상속받는다. 프로세서의 affinity가 변경되면, 커널은 migration threads를 이용해 태스크를 이용가능한 프로세서로 push한다.

8.3. Yielding Processor Time

리눅스는 sched_yield() 시스템 콜을 통해 프로세스가 명시적으로 프로세서를 양보할 수 있도록 한다. 이는 현재 프로세스를 active array에서 빼고, expired array에 넣음으로써 가능해진다. 실시간 태스크는 만료되지 않기 때문에, 실시간 태스크는 priority list의 가장 마지막으로 옮긴다.

---

Reference

• Linux Kernel Development (3rd Edition) by Robert Love