6월21일 System Context, 런 큐와 스케줄링, CFS, 문맥교환, 시그널

태스크를 관리하는 정보 집합

 

• 태스크 정보 : pid, uid, euid, suid, ...
• 태스크 상태 : 실행 상태, READY 상태, 수면 상태, ...
• 태스크의 가족 관계 : p_pptr, p_cptr, next_task, next_run
• 스케줄링 정보 : policy, priority, counter, rt_priority, need_resched
• 태스크가 접근한 파일 정보 : file descriptor
• 시그널 정보
• 그 외 : 수행 시간 정보, 수행 파일 이름, 등등 (kernel dependent)

 

 

Multi-CPU를 위한 리눅스 특징

 

스케줄링

Run queue per each CPU

일반 task : SCHED_NORMAL, SCHED_BATCH, SCHED_IDLE

100~139(-20~19)

실시간 task : SCHED_FIFO, SCHED_RR, SCHED_DEADLINE, 0~99

 

 

런 큐와 스케줄링 75p

 

런 큐와 태스크

 

일반적으로 운영체제는 스케줄링 작업 수행을 위해, 수행 가능한 상태의 태스크를 자료구조를 통해 관리한다. 리눅스에서는 이 자료구조를 런 큐(Runqueue)라 한다.

~/kernel/sched/sched.h strucnt rq 부팅 이후 각 CPU벼로 하나씩의 런큐가 유지

 

태스크가 처음 생성되면 init_task를 헤드로 하는 이중 연결 리스트에 삽입 (tasklist) 리눅스 시스템에 존재하는 모든 태스크들은 tasklist에 연결되어 있다.

TASK_RUNNING상태인 태스크는 시스템에 존재하는 런 큐 중 하나에 소속된다.

 

다중 CPU환경에서 런 큐가 여러 개라면 새로이 생성된 태스크는 어느 런 큐에 삽입될까?

일반적으로, 새로 생성되는 태스크는 부모 태스크가 존재하던 런 큐로 삽입. 자식 태스크가 부모 태스크와 같은 CPU에서 수행될 때 더 높은 캐시 친화력(cache affinity)을 얻을 수 있기 때문.

대기 상태에서 깨어난 태스크는 대기 전에 수행되던 CPU의 런큐로 삽입

 

리눅스에서는 task_struct의 cpus_allowed 필드에 태스크가 수행될 수 있는 CPU의 번호가 들어 있고, 이를 이용해 삽입될 런 큐 결정.

 

스케줄러가 수행되면 해당 CPU의 런 큐에서 다음번 수행시킬 태스크를 골라낸다. 이때의 고려사항

1. 어떤 태스크를 선택할 것인가. CFS(Completely Fair Scheduler)를 사용 실시간 태스크를 위해서는 FIFO, RR, DEADLINE 정책을 제공

2. 런 큐간의 부하가 균등하지 않은 경우 어떻게 할 것인가. 부하 균등(load balancing)기법 제공.

load_balance()함수 : 특정 CPU가 많은 작업을 수행하고 있느라 매우 바쁘고 다른 CPU가 한가하다면 다른 CPU로 태스클를 이주(migration) 시켜서 시스템의 전반적인 성능 향상을 시도함

 

특정 태스크를 이주시키기로 결정했다면 어디로 이주시킬 것인기 결정해야함.

리눅스는 부팅 과정을 정상적으로 종료한 뒤에는, 0~7번까지 총 8개의 논리적인 CPU가 존재하는 것으로 인식 

각 최소 연산 단위를 '그룹'이라 부른다. struct sched_group 자료구조 사용. 하드웨어적 특성에 따라 '도메인'으로 분류, 각 레벨별로 strcut_ sched_domain이라는 자료구조로 관리. 이를 통해 태스크의 이주 대상 CPU 선정 시 성능 저하를 최소화 할 수 있는 CPU 검색을 가능케 한다.

 

SMP(Symmetric Multi Processor) 각 CPU가 동등하기 때문에 태스크가 어느 곳에서든 수행 가능

 

NUMA(Non-Uniform Memory Access) 구조의 시스템에서는 load_balance() 함수에서 CPU 부하뿐만 아니라 메모리 접근 시간의 차이 등도 고려하여 부하 균등을 시도.

load_balance() 함수는 tick 타이머 인터럽트에 기반 하여 주기적으로 호출되거나, 특정 CPU의 런 큐가 비게 되는 경우, 혹은 실시간 태스크의 상태 전이에 의해 호출된다.

 

실시간 태스크 스케줄링 (FIFO, RR and DEADLINE)

 

CPU는 공정하고 효율적이고 급한 태스크를 먼저 수행하게 해주어 높은 반응성을 보여야함.

 

task_struct 구조체에 policy, prio, rt_priority 등의 필드등을 근거로 태스크를 골라냄

policy 필드는 이 태스크가 어떤 스케줄링 정책을 사용하는지를 나타낸다. 리눅스의 태스크는 실시간 태스크와 일반 태스크로 나뉘며, 실시간 태스크를 위해 3개, 일반 태스크를 위해 3개, 총 6개의 스케줄링 정책이 존재.

실시간 태스크를 위해서는 SCHED_FIFO, SCHED_RR, SCHED_DEADLINE 정책이 사용

일반 태스크를 위해서는 SCHED_NORMAL 정책이 사용

중요하지 않은 일을 수행하는 태스크가 CPU를 점유하는 것을 막기 위해 가장 낮은 우선순위로 스케줄링 되는 SCHED_IDLE 정책, 사용자와 상호 작용이 없는 CPU 중심의 일괄 작업(batch job) 태스크를 위한 SCHED_BATCH 정책이 존재.

 

실시간 태스크

실시간 태스크를 생성하는 별도의 함수가 존재하는 것이 아니라 sched_setscheduler() 등의 함수를 통해 태스크의 스케줄링 정책을 실시간 태스크 정책으로 바꾸면 실시간 태스크가 되는 것이다.

우선순위 결정을 위해 task_struct 구조체의 rt_priority 필드를 사용 

rt_priority : 0~99 우선순위를 가질 수 있다. 태스크가 수행을 종료하거나 스스로 중지하거나, 자신의 타임 슬라이스를 다 쓸때까지(SCHED_RR 정책만 해당됨) CPU를 사용한다. RR인 경우 동일 우선순위를 가지는 태스크가 복수개인 경우 타임 슬라이스 기반으로 스케줄링. 동일 우선순위를 가지는 RR태스크가 없는 경우 FIFO와 동일하게 동작. 또한 실시간 정책을 사용하는 태스크는 고정 우선순위를 가지게 된다. 따라서 우선순위가 높은 태스크가 먼저 수행된다는 것을 보장

 

우선순위가 가장 높은 태스크는 어떻게 찾는가?

tasklist를 이용 가장 높은 우선순위 태스크를 골라낸다. but 태스크의 개수가 늘어나면 스케줄링에 걸리는 시간도 선형적으로 증가(O(n)의 시간복잡도), 스케줄링에 소모되는 시간 예측 불가 (과거 리눅스 커널 버전 2.4의 스케줄러)

 

이를 해결하기위해 FIFO or RR 정책을 사용하는 실시간 태스크들이 가질 수 있는 모든 우선순위 레벨(0~09)을 표현할 수 있는 비트맵을 준비.

태스크가 생성되면 비트맵에서 그 태스크의 우선순위에 해당하는 비트를 1로 set, 태스크의 우선순위에 해당되는 큐에 삽입. 커널은 비트맵에서 가장 처음으로 set되어 있는(가장 우선순위가 높은 태스크)비트를 찾아, 그 우선순위 큐에 매달려 있는 태스크를 선택

고정된 크기의 비트맵에서 최우선 비트를 찾아내는 것은 상수시간안에 가능하므로 스케줄링 작업이 고정시간 내에 완료 가능.

 

DEADLINE 정책은 EDF(Earliest Deadline First) 알고리즘을 구현 한 것. deadline이 가장 가까운 ( 가장 급한) 태스크를 스케줄링 대상으로 선정.

완료시간 : deadline, 작업량 : runtime, 주기성 : period

runtime과 deadlin은 (현재시간 + runtime < deadlin)의 조건을 만족해야 한다.

태스크들의 runtime 합은 CPU의 최대 처리량을 넘으면 안된다. 새로운 태스크가 DEADLINE 정책을 사용하려 할 때, DEADLINE 정책을 사용하는 기존 태스크들의 runtime과 period를 이용해 해당 태스크의 성공적인 완료 여부를 확정적(deterministic)으로 결정 할 수 있다는 의미이며, 이러한 확정성은 실시간 스케줄링 기법의 가장 중요한 요소

 

실제 과정 : DEADLINE 정책을 사용하는 각 태스크들은 deadline을 이용하여 RBTree (Red-Black Tree)에 정렬, 스케줄러가 호출되면 가장 가까운 deadline을 가지는 태스크를 스케줄링 대상으로 선정. 우선순위 의미 X

FIFO or RR 등 기존의 우선순위 기반 스케줄링 정책 대비, 기아현상(starvation) 등의 문제에 효율적, 주기성을 가지는 실생활의 많은 프로그램들(영상, 음성, 스트리밍 등)과 제약 시간을 가지는 수많은 응용들에 효과적으로 적용이 가능

 

CPU당 하나씩 존재하는 런 큐 자료구조인 struct rq 내에는 FIFO, RR, DEADLIN 스케줄링 기법에서 사용하는

strcut rt_rq(비트맵과 큐가 존재)

struct dl_rq(RBtree 관련 자료구조가 존재)

그룹과 도메인을 관리하기 위한 자료구조 역시 연결되어있다.

 

 

일반 태스크 스케줄링 (CFS)

 

CFS는 공평한 스케줄링을 추구. CPU사용시간의 공평한 분배를 의미한다. 그러나 두 태스크가 번갈아 가며 수행되므로 임의의 시점에 두 태스크의 CPU 사용 시간이 항상 1:1로 같을 수는 없다. 따라서 CFS는 정해진 '시간 단위'로 봤을 때 시스템에 존재하는 태스크들에게 공평한 CPU 시간을 할당하는 것을 목표로 한다.

 

런 큐에 N개의 태스크가 존재한다면, 정해진 '시간 단위'를 N으로 나누어 N개의 태스크에게 할당해 주면 된다.

태스크의 우선순위는 어떻게 반영하는가 ? 우선순위가 높은 태스크에게 가중치를 두어 좀 더 긴 시간을 주면 어떨까 ?

이를 위해 리눅스는 vruntime 개념을 도입했다. 각 태스크는 자신만의 vruntime 값을 가지며, 이 값은 스케줄링되어 CPU를 사용하는 경우 사용시간과 우선순위를 고려하여 증가 된다. 일반 태스크의 우선순위는 별도의 지정(nice()같은 시스템 호출)이 없다면 부모의 우선순위와 같다. 항상 실시간 태스크보다 우선순위가 낮음

 

리눅스는 주기적으로 발생되는 타이머 인터럽트 핸들러에서 scheduler_tick()함수를 호출해 현재 수행중인 태스크의 vruntime 값을 갱신한다.

우선순위가 높은 태스크의 경우 ( 좀 더 긴 시간 CPU를 사용할 수 있도록) 시간이 느리게 흘러가는 것처럼 관리하고, 우선 순위가 낮은 태스크의 경우 시간이 빠르게 흘러가는 것처럼 관리한다

 

스케줄링 대상이 되는 태스크를 어떻게 빠르게 골라낼것인가 ?

가장 작은 vruntime 값을 가지는 태스크가 가장 과거에 CPU를 사용했음을 으미. 이러한 태스크를 다음번 스케줄링의 대상으로 선정해 공평한 스케줄링을 수행하려 노력한다.

가장 낮은 vruntime 값을 찾기 위해 RBTree 자료구조를 이용. 각 태스크는 RBTree에 정렬되어있으며, 가장 좌측에 존재하는 태스크(vruntime이 가장 작은 태스크)가 다음번 스케줄링의 대상이 된다(rb_leftmost 필드).

스케줄링이 된 태스크는 수행 될수록 키 값이 증가되며 따라서 트리의 가장 좌측에서 점차 우측으로 이동. 반면 스케줄링 되지 않은 태스크는 대기하는 동안 점점 자신의 키 값이(상대적으로)감소되며 점차 트리의 좌측으로 이동하게 된다.

 

수행된 시간만큼 태스크의 vruntime 값이 증가되며, 항상 가장 작은 vruntime값으 가지는 태스크가 스케줄링 된다면, 너무 자주 스케줄링이 발생하지는 않을까?

리눅스는 각 태스크별로 선점되지 않고 CPU를 사용할 수 있는 시간(타임 슬라이스)이 미리 지정되어 있으며, 타임슬라이스가 작은 태스크 간의 빈번한 스케줄링을 막기 위해 스케줄링간 최소 지연 시간도 정의되어 있다.

 

태스크의 우선순위에 따라 각 태스크에게 타임 슬라이스를 어떻게 분배하는가 ?

'시간 단위'를 태스크의 우선순위, 즉 가중치에 기반하여 각 태스크에게 분배한다. 계산 과정은 커널의 sched_slice() 함수에 구현 되어 있다. 이때 '시간 단위'는 너무 잦은 스케줄링으로 인한 오버헤드를 최소화하기 위해 시스템에 존재하는 태스크의 개수를 고려하여 정해지며, 커널의 __sched_period()함수에서 계산된다.

 

스케줄러는 어떻게 호출될까?

1. 직접적으로 schedule() 함수를 호출하는 방법

2. 현재 수행 되고 있는 태스크의 thread_info 구조체 내부에 존재하는 flags필드 중 need_resched라는 필드를 설정하는 방법

 

스케줄러는 언제 호출될까?

1. 주기적으로 타이머 인터럽트가 발생하는데 이 인터럽트의 서비스 루틴이 종료되는 시점에 현재 수행되고 있는 태스크의 need_resched 필드를 살펴보고 스케줄링 할 필요가 있다면 스케줄러를 호출한다.

2. 현재 수행되고 있는 태스크가 자신의 타임 슬라이스를 모두 사용했거나, 이벤트를 대기하는 경우

3. 새로 태스크가 생성되거나, 대기 상태의 태스크가 깨어나는 경우

4. 현재 태스크가 sched_setscheduler() 같은 스케줄링 관련 시스템 콜을 호출하는 경우

 

CFS의 그룹 스케줄링 정책. config시 CONFIG_FAIR_GROUP_SCHED가 설정되어 있어야 하며 스크는 SCHED_NORMAL, SCHED_BATCH정책 중 하나를 사용해야 함.

그룹 스케줄링 기법

1. 사용자 ID 기반 그룹 스케줄링

- 특정 사용자 간에 공평하게 CPU를 배분하는 정책.

2. cgroup 가상 파일시스템 기반 그룹 스케줄링

- 사용자가 지정한 태스크들을 하나의 그룹으로 취급하며 그룹 간에 공평하게 CPU를 배분하는 정책.

 

 

리눅스는 CFS와 함께 스케줄링 클래스라는 개념을 도입.

이를 통해 구체적인 스케줄러의 구현과 인터페이스를 분리하였다. 스케줄링 클래스는 각각의 스케줄링 정책이 구현되어 있는 함수에 대한 포인터를 담고 있는 구조체이다. 따라서 임의의 시점에 스케줄링 관련 함수를 호출해야 할 때에는 구체적인 함수의 이름이 아닌 이 구조체를 이용하여 일관된 인터페이스를 유지할 수 있다.

task_struct 구조체는 자신이 속해있는 스케줄링 정책에 따라 적절한 sched_class를 가리킨다.

 

 

문맥 교환

 

문맥 교환(context switch) : 수행 중이던 태스크의 동작을 멈추고 다른 태스크로 전환하는 과정

문맥 저장(context save) : 리눅스 커널이 태스크가 문맥교환 되는 시점에 어디까지 수행했는지, 현재 CPU의 레지스터 값은 얼마인지 등을 저장해 두는 것

 

즉, 스케줄링이 일어나면 문맥교환이 발생하고, 문맥교환 시엔 현재 수행 중이던 태스크의 문맥을 저장해 두어야 한다. 이때 문맥은 CPU 레지스터 즉, H/W context를 뜻한다.

task_struct에 H/W context를 담아 두기 위한 필드가 존재. 필드의 이름은 thread이며, struct thread_struct 형태로 정의

 

thread_struct 구조는 태스크가 실행하다가 중단되어야 할 때 태스크가 현재 어디까지 실행했는지 기억하는 공간.

 

어떤 정보를 유지해야하는가?

우선 태스크가 어떤 명령어까지 수행했으며, 다음에 수행해야할 명령어가 어디인지 알아야 한다. 이 정보는 CPU의 pc(program counter, 인털 CPU에서는 eip레지스터라고 불림) 레지스터를 이용해 알 수 있다. 한편 태스크는 중지할 때 현재의 스택 사용 위치(top)가 어디인지 알아야 한다. 이 정보는 CPU의 sp(stack pointer) 레지스터를 이용해 알 수 있다. 뿐만 아니라 태스크가 실행 중에 이용한 CPU의 범용 레지스터 값들도 기억해야 한다. 이는 태스크가 중지되면 다른 태스크가 CPU를 사용할 것이며, 따라서 다른 태스크가 CPU의 레지스터 내용을 변경할 수 있기 때문.

그 외에 CPU 상태를 나타내는 eflags, 세그먼트를 관리하는 cs, ds 등의 레지스터 내용도 기억해야한다.

 

 

 

태스크와 시그널

 

시그널 : 태스크에게 비동기적인 사건의 발생을 알리는 매커니즘

태스크가 시그널을 원활히 처리하려면 3가지 기능을 지원해야 한다.

1. 다른 태스크에게 시그널을 보낼 수 있어야 한다. 이를 위해 리눅스 커널은 sys_kill() 이라는 시스템 호출을 제공한다.
2. 자신에게 시그널이 오면 시그널을 수신할 수 있어야 한다. 이를 위해 task_struct에는 signal, pending이라는 변수가 존재
3. 자신에게 시그널이 오면 시그널을 처리할 수 있는 함수를 지정할 수 있어야 한다. 이를 위해 sys_signal()이라는 시스템 호출이 존재하며, task_struct 내에 sighand라는 변수가 존재

 

PID를 공유하고 있는 모든 쓰레드들(쓰레드 그룹)간에 시그널을 공유하는 매커니즘이 필요. 여러 태스크들 간에 공유해야 하는 시그널이 도착하게 되면 이를 task_struct 구조체의 signal 필드에 저장해 둔다. 이러한 시그널을 보내는 작업은 sys_kill()과 같은 시스템 호출을 통해 이뤄진다.

 

특정 태스크에게만 시그널을 보내야 하는 경우

공유하지 않는 시그널은 task_struct 구조체의 pending 필드에 저장해 둔다. 시그널을 signal 필드나 pending필드에 저장할 때는 시그널 번호 등을 구조체로 정의하여 큐에 등록시키는 구조를 택하고 있으며, 이를 위해 sys_kill()과 같은 시스템 호출을 도입하였다.

 

각 태스크는 특정 시그널이 발생했을 때 수행될 함수 즉, 시그널 핸들러를 지정할 수 있다. 이때 사용자 지정 시그널 핸들러를 설정하게 해주는 함수가 sys_signal()이다. 태스크가 지정한 시그널 핸들러는 task_struct 구조체의 sighand 필드에 저장 된다. 또한 태스크는 특정 시그널을 받지 않도록 설정할 수 있는데 이는 task_struct 구조체의 blocked필드를 통해 이뤄진다. 태스크에서 sigprocmask()와 같은 함수를 사용하면 인자로 넘긴 시그널 번호에 해당되는 비트를 blocked 필드에서 설정함으로써 특정 시그널을 받지 않도록 할 수 있다.(SIGKILL, SIGSTIP은 받지않도록 설정하거나 무시가 불가능)

 

다른 태스크에게 시그널을 보내는 과정

해당 태스크의 task_struct 구조체를 찾아내, 보내려는 시그널 번호를 통해 siginfo 자료 구조를 초기화, 시그널의 성격에 따라 task_struct의 signal이나 pending필드에 매달아 준다. 이때 blocked 필드를 검사하여 받지 않도록 설정한 시그널이 아닌지 검사.

 

수신한 시그널의 처리는 태스크가 커널 수준에서 사용자 수준 실행 상태로 전이할 때 이루어진다. 커널은 pending 필드의 비트맵이 켜져 있는지, 혹은 signal 필드의 count가 0이 아닌지 검사를 통해 처리를 대기 중인 시그널이 있는지 확인 할 수 있다. 이들 변수가 0이 아니라면 어떤 시그널이 대기 중인지 검사, 이 시그널이 블록되어 있지 않다면 시그널 번호에 해당되는 시그널 핸들러를 sighand 필드의 action 배열에 찾아서 수행시켜준다. 명시적으로 핸들러를 등록시키지 않은 경우 커널은 시그널 무시, 태스크 종료, 태스크 중지 등과 같은 디폴트 액션을 취한다.

 

인터럽트와 트랩과 시그널 간의 차이

인터럽트와 트랩이 사건의 발생을 커널에게 알리는 방법이라면, 시그널은 사건의 발생을 태스크에게 알리는 방법