Linux Kernel OS 2(작성중)

mohadang·2023년 5월 13일
0
post-thumbnail

상태 전이(State Transition)와 실행 수준 변화

태스크가 kernel에 의해 운영 되면서 여러 상태로 전이를 한다(ready, running, dead ...)
이는 태스크가 요청했던 자원이 사용 가능해지면 다시 수행시켜 줌으로써 보다 높은 시스템 활용률을 제공하려 한다

일단 태스크가 생성되면 그 태스크는 준비 상태TASK_RUNNING(ready)가 된다

TASK_RUNNING 상태는 구체적으로 준비 - TASK_RUNNING(ready)와 실제 CPU 자원을 할당받아 명령어 들을 처리하고 있는 실행 - TASK_RUNNING(running) 상태로 나뉘게 된다

TASK_RUNNING(running) 상태에서 실제 수행되던 태스크가 자신에게 할당된 CPU 시간을 모두 사용하였거나, 보다 높은 우선순위를 가지는 태스크로 인해 TASK_RUNNING(ready) 상태로 전환 될 수 있다

n 개의 CPU를 갖는 시스템에서는 임의의 시점에 최대 n개의 태스크가 실제 CPU 자원을 할당 받아 실행 상태에 있을 수 있다

EXIT_ZOMBIE와 EXIT_DEAD는 task_struct 구조체의 exit_state 필드에 저장되는 값이며, 그 이외의 상태들은 state 필드에 저장된다

태스크가 자신이 해야 할 일을 다 끝내곡 exit()를 호출하면(혹은 kill 되거나) task_struct 구조체 내에 존재하는 exit_state 값과 조합하여 TASK_DEAD(EXIT_ZOMBIE) 상태로 전이 된다.

ZOMBIE 상태는 말 그대로 죽어있는 상태로써, 태스크에 할당되어 있던 자원을 대부분 커널에게 반납한 상태이다 그러나 자신이 종료된 이유(ex: error 번호), 자신이 사용한 자원의 통계 정보 등을 부모 태스크에게 알려주기 위해 "유지" 되고 있는 상태이다
부모 태스크가 wait()등의 함수를 호출하면 자식 태스크의 상태는 TASK_DEAD(EXIT_DEAD) 상태로 바뀌게 되며, 부모는 자식의 종료 정보를 넘겨받게 된다

부모 태스크가 자식 태스크에게 wait()등의 함수를 호출하기 전에 먼저 종료가 되면 부모가 없는 ZOMBIE 상태의 자식 태스크 즉, 고아 상태가 된다. 이러한 문제를 해결하기 위해 커널은 고아 태스크의 부모를 init 태스콜 바꾸어 주며 init 태스크가 wait()등의 함수를 호출할 때 고아 태스크는 최종 소멸된다
이 때문에 task_struct 구조체에 real_parent와 parent라는 2개의 필드가 존재한다. real_parent는 실제 태스크를 생성하 부모이고 parent는 현재 부모 즉 init 태스크이다

SIGSTOP, SIGTSTP, SIGTTIN< SIGTTOU 등의 시그널을 받은 태스크는 TASK_STOPPED 상태로 전이되며, 추후 SIGCONT 시그널을 받아 다시 TASK_RUNNING(ready) 상태로 전환된다

디버거의 ptrace() 호출에 의해 디버깅 되고 있는 태스크는 시그널을 받는 경우 TASK_TRRACED 상태로 전이 될 수 있다

TASK_RUNNING(running) 상태에 있던 태스크가 특정한 사건을 기다려야 할 필요가 있으면 대기 상태 - TASK_INTERRUPTIBLE, TASK_UNINTERRUPTIBLE, TASK_KILLABLE로 전이 한다. 태스크가 디스크 같은 주변 장치에 요청을 보내고 그 요청이 완료되기까지 기다리거나, 사용 중인 시스템 자원 대기 등이 대표적인 예이다(블록 상태)

TASK_INTERRUPTIBLE, TASK_UNINTERRUPTIBLE 모두 특정 사건(event)를 기다린다는 면에서는 유사하나 TASK_UNINTERRUPTIBLE 상태는 시근널에 반응하지 않는다는 점에서 TASK_INTERRUPTIBLE과 구분된다

TASK_UNINTERRUPTIBLE 상태의 태스크가 시그널에 반응하지 않기 때문에 생기는 문제점(ex: kill -9 PID 등의 명령을 수행해도 태스크가 종료되지 않는 상황) 등으로 인해 SIGKILL과 같은 중요한 시그널(fatal signal)에만 반응하는 TASK_KILLABLE 상태가 도입되었다

커널 레벨 전이

사용자 레벨 실행 상태에서 커널 레벨 실행 상태로 전이 할 수 있는 방법은 두 가지가 있다

  1. 시스템 호출
  2. 인터럽트 발생

커널 스택

리눅스 커널은 태스크가 생성될 때마다 태스크 별로 8Kb 혹은 16Kb(물론 이 크기는 커널 버전과 설정에 따라 변하기도 한다). A 라는 태스크가 시스템 호출을 요청 했다면 이를 처리하기 위해 리눅스 커널은 A에게 할당해 주었던 커널 스택을 사용하여 요청된 작업을 수행

태스크 당 할당되는 커널 스택은 thread_union이라 불리며 thread_info 구조체를 포함하고 있다. thread_info 구조체를 리눅스에선 프로세스 디스크립터라 부르기도 한다
이 구조체 안에는 해당 태스크의 task_struct를 가리키는 포인터와, 스케줄링의 필요성 여부를 나타내는 플래그, 태스크의 포맷을 나타내는 exec_domain 등의 필드가 존재한다

thread_info {
  *task     ->    task_struct
  flags(need_resched...)
}

커널과 사용자 영역의 컨텍스트 스위칭

커널과 사용자 수준간이ㅡ 변화 시에 현재까지의 작업 상황을 어딘가에 저장해 놓아야 한다
이는 커널로 진입되는 시점에서 커널 스택 안에 현재 레지스터의 값들을 구조체를 이용하여 일목요연하게 저장함으로써 이뤄진다
pt_regs라는 이름으로 표시된 공간이 이 목적으로 사용된다

런 큐와 스케줄링

여러 개의 태스크들 중에서 다음번 수행시킬 태스크를 선택하여 CPU라는 자원을 할당하는 과정을 스케줄링이라 부른다
"실시간 태스크"와 "일반 태스크"로 나뉘며 각각을 위해 별도의 스케줄링 알고리즘이 구현되어 있다

리눅스는 140 단계의 우선순위를 제공한다. 숫자가 낮을 수록 높은 우선순위를 나타낸다

실시간 태스크 : 0 ~ 99 단계 사용
일반 태스크 : 100 ~ 139 단계 사용

실시간 태스크는 항상 일반 태스크 보다 우선하여 실행된다

런 큐와 태스크

수행 가능한 상태의 태스크를 자로구조를 통해 관리한다. 리눅스에서는 이 자료구조를 런 큐(Runqueue)라 한다. OS 구현에 따라 런큐는 한 개 혹은 여러 개 존재할 수 있으며 자료구조의 모양이나 관리 방법 역시 달라진다

리눅스의 런큐는 ~/kernel/sched/sched.h 파일 내에 strucgt rq 라는 이름으로 정의되어 있으며, 부팅이 완료된 이후 각 CUP 별로 하나씩의 런큐가 유지된다

태스크가 처음 생성되면 init_task를 헤드로 하는 이중 연결 리스트에 삽입된다.
결국 리눅스 시스템에 존재하는 모든 태스크들은 이 태스크 리스트에 연결되어 있다
이 중에서 TASK_RUNNING 상태인 태스크는 시스템에 존재하는 런 큐 중 하나에 소속된다

새로 생성되어 TASK_RUNNING 상태가 된 태스크(wakt_up_new_task())와 이벤트를 대기하다 깨어난(wakt_up()) 태스크는 런 큐로 삽입된다

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

대기 상태에서 깨어난 태스크는 대기 전에 수행되던 CUP의 런 큐로 삽입된다. 이 또한 캐시 친화력을 활용하기 위합니다

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

cpus_allowed 필드는 wakt_up_new_task()가 수행될 때 부하 균등을 고려하여 수정된다

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

  1. 어떤 태스크를 선택할 것인가 ?
    이를 위해 리눅스는 일반 태스크를 위한 CFS(Completely Fair Scheduler)를 사용
    실시간 태스크를 위해서는 FIFO, RR< DEADLINE 정책을 제공
  1. 런 큐간의 부하가 균등하지 않은 경우 어떻게 할 것인가 ?
    이를 위해서 리눅스에서는 부하 균등(load balancing)기법을 제공. load_balance() 함수가 이를 담당
    이 함수에서는 특정 CUP가 많은 작업을 수행하고 있느라 매우 바쁘고 다른 CPU들은 한가하담녀 다른 CPU로 태스크를 이주(migration) 시켜서 시스템의 전반적인 성능 향상을 시도한다.

태스크 이주

특정 태스크를 이주시키기로 결정했다면 어느 CPU로 이주 시켜야 하는가
태스크 이주시 성능을 고려하는데 이때 캐시 공유 상태와 CPU의 메모리 접근성을 고려한다

이를 관리하기 위해 리눅스는 그룹이라는 개념으로 부르며 struct sched_group 이라는 자료구조를 사용한다
또한 그룹을 하드웨어적인 특성에 따라 도메인으로 분류하며, 이는 각 레벨별로 sruct sched_domain이라는 자료구조 관리된다 이를 통해 태스크의 이주 대상 CUP 선정 시 성능 저하를 최소화할 수 있는 CUP 검색을 가능케 한다

SMP(Summetric Multi Process) : 각 CPU가 동등하기 때문에 태스크가 어느 곳에서든 수행될 수 있다
NUMA(Non-Uniform Memory Access) : locad_balance() 함수에서 CUP 부하뿐만 아니라 메모리 접근 시간의 차이 등도 고려하여 부하 균등을 시도한다. load_balance() 함수는 tick 타이머 인터럽트에 기반 하여 주기적으로 호출되거나, 특정 CPU의 런 큐가 비게 되는 경우, 혹은 태스크의 상태 전이에 의해 호출된다

리눅스 태스크 스케줄링

리눅스의 태스크는 실시간 태스크와 일반 태스크로 나뉘며, 실시간 태스크를 위해 3개, 일반 태스크를 위해 3개, 총 6개의 스케줄링 정책이 존재한다

실시간 태스크 : SCHED_FIFO, SCHED_RR, SCHED_DEADLINE
일반 태스크 : SCHED_NORMAL, SCHED_IDLE(중요하지 않은 일ㅇ르 수행하는 태스크가 CUP를 점유하는 것을 막기 위해 가장 낮은 우선순위로 스케줄링되는 정책), SCHED_BATCH(사용자와의 상호 작용이 없는 CPU 중심의 일괄 작업(batch job) 태스크를 위한 정책)

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

컴퓨터 시스템의 가장 중요한 자원 중 하나인 CPU를 효율적이고 높은 처리율을 낼 수 있어야 한다
또한 가장 급한 태스크를 한가한 태스크보다 먼저 수행될 수 있도록 해준다면 보다 높은 반응성을 보일 수 있어야 한다

이를 위해 task_struct 구조체는 policy, prio, rt_priority 등의 필드가 존재한다
policy : 이 태스크가 어떤 스캐줄링 정책을 사용하는지 나타낸다

실시간 태스크는 SCHED_FIFO, SCHED_RR, SCHED_DEADLINE 정책을 사용하는 태스크를 의미한다
실시간 태스크를 생성하는 별도의 함수가 존재하는 것이 아니라 sched_setscheduler() 등의 함수를 통해 태스크의 스케줄링 정책을 위 세가지 중 하나로 바꾸게 되면 실시간 태스크가 되는 것이다

RR인 경우 동일 우선순위를 가지는 태스크가 복수개인 경우 타임 슬라이스 기반으로 스케줄링 된다. 만약 동일 우선순위를 가지는 RR 태스크가 없는 경우라면 FIFO와 동일하게 동작된다

또한 실시간 정책을 사용하는 태스크는 고정 우선순위를 가지게 된다. 따라서 우선순위가 높은 태스크가 낮은 태스크보다 먼저 수행된다는 것을 보장한다

SCHED_FIFO, SCHED_RR 우선순위가 가장 높은 태스크를 찾는 방법

kernel 2.4 : 연결된 리스트에서 순서대로 뒤지면서 실시간 태스크(FIFO or RR)중 가장 높은 우선순위의 태스크를 골라내는 방법. 시간 복잡도 O(n), 스케줄링에 소모되는 시간을 예측할 수 없음

개선 : 모든 우선순위 레벨(0 ~ 99)을 표현할 수 있는 비트맵을 준비. 태스크가 생성되면 비트맵에서 그 태스크의 우선순위에 해당하는 비트를 1로 set한 뒤 태스크의 우선순위에 해당되는 큐에 삽입

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

DEADELINE 정책

잘 알려진 실시간 태스크 스케줄링 기법 중 하나인 EDF(Earliest Deadline First) 알고리즘을 구현한 것

실시간 태스크 스케줄링 정책은 우선순위에 기반하여 스케줄링 대상을 선정하는데 반해, DEADLINE 정책은 잠시 후 설명될 데드라인이 가장 가까운(즉, 가장 급한) 태스크를 스케줄링 대상으로 선정

ex) 동영상을 재생하는 태스크가 수행중 이라고 가정. 만약 끊김 없이 화면을 재생하기 위해 초단 30프레임을 디코딩 하여 화면에 출력해야 한다면, 이 태스크는 초당 30 번씩 '해야하는 일'을 가지고 있다고 볼 수 있다. 즉 정확한 완료시간 조건이 정해져 있다

리눅스의 DEADLINe 정책에서는 완료시간을 deadline, 작업량은 runtime, 초당 30회라는 주기성을 period라고 부른다

정상적인 동작을 위해서는 태스크의 runtime과 deadline은 (현재시간 + runtime < deadline)의 조건을 만족해야 하며 DEADLINE 정책을 사용하는 태스크들의 runtime 합은 CPU의 최대 처리량을 넘어선 안 된다. "이러한 확정성은 실시간 스케줄링 기법의 가장 중요한 요소 중 하나이다"

실제 스케줄링 과정은 비교적 간단한다. DEADLINE 정책을 사용하는 각 태스크들은 데드라인을 이용하여 RBTree에 정렬되어 있으며 스케줄러가 호출되면 가장 가까운 데드라인을 가지는 태스크를 스케줄링 대상으로 선정한다. "즉 DEADLINE 정책을 사용하는 태스크의 경우 우선순위는 의미가 없다"

따라서 FIFO나 RR등 기존의 우선순위 기반 스케줄링 정책 대비, 기아현상(starvation - 특정 태스크가 CPU 자원을 할당 받지 못함)등의 문제에 효율적이며, 주기성을 가지는 실행활의 많은 프로그램들(영상, 음성, 스트리밍 등)과 제약 시간을 가지는 수많은 응용들에게 효과적으로 적용이 가능하다

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

리눅스가 일반 태스크를 위해 사용하고 있는 스케줄링 기법은 CFS(Completely Fair Schedluer)라 불린다

공평한 CPU 사용시간 분배란 A, B 두 개의 태스크가 수행 중이라면, A와 B의 CPU 사용시간이 항상 1:1로 같아야 하는 것이다

CFS는 정해진 '시간 단위'로 봤을 때, 시스템에 존재하는 태스크들에게 공평한 CUP 시간을 할당하는 것을 목표로 한다.
ex) 1초를 '시간 단위'로 한다면, 0.5초 동안 A 태스크를 수행시키고, 그런 뒤 0.5초간 B 태스크를 수행시킴으로써 1초가 지난 이후 A와 B의 CPU 사용시간이 1:1이 되도록 하는 것이다

profile
mohadang

0개의 댓글