Linux Kernel 관련 온라인 강의 요약본입니다.
https://olc.kr/course/course_online_view.jsp?id=35&s_keyword=Kernel&x=0&y=0
What is Process and Thread
이제 프로세스(Process)와 스레드(Thread)의 차이를 설명할 수 있습니다.
프로세스는 독립적인 주소 공간과 자원을 가지는 테스크이며, 부모 테스크의 정보를 Copy-On-Write 방식으로 복사해서 가져와 사용하며 write가 발생하면 분리하여 사용합니다.
반면 스레드의 경우 같은 프로세스 내에서 생성되는 테스크로, 부모 테스크의 정보 중 공유 가능한 부분은 공유하고 최소한의 자원으로 실행되는 테스크입니다.
KT(Kernel Thread)
이제 커널 스레드에 대해서 알아보겠습니다.
Linux 커널은 부팅 시 로드되어 메모리에 상주하며, 커널 내부 작업을 수행하기 위해 별도의 커널 스레드를 생성해 사용합니다.
커널도 프로그램이 실행되는 동안 내부 작업 처리를 위해 kernel_thread()나 kthread_create()을 통해 커널 스레드를 생성합니다.
이렇게 생성된 커널 스레드는 사용자 공간의 스레드와 달리 사용자 주소 공간(mm)을 가지지 않으며, 프로세스 생성에 비해 오버헤드가 적은 Light weight로 커널 내부의 백그라운드 작업을 처리하는 데 사용됩니다.
What is mm_struct
앞에서 본 PCB(Process Control Block)에 저장되는 mm 포인터를 말하는 것이며, mm은 Linux 커널에서 mm_struct로 정의되어 아래의 데이터를 저장하고 있습니다.
struct mm_struct {
struct vm_area_struct * mmap; /* list of VMAs */
struct rb_root mm_rb;
struct vm_area_struct * mmap_cache; /* last find_vma result */
unsigned long free_area_cache; /* first hole */
pgd_t * pgd;
atomic_t mm_users; /* How many users with user space? */
atomic_t mm_count; /* How many references to "struct mm_struct" (users count as 1) */
int map_count; /* number of VMAs */
struct rw_semaphore mmap_sem;
spinlock_t page_table_lock; /* Protects task page tables and mm->rss */
struct list_head mmlist; /* List of all active mm's. These are globally strung
* together off init_mm.mmlist, and are protected
* by mmlist_lock
*/
unsigned long start_code, end_code, start_data, end_data;
unsigned long start_brk, brk, start_stack;
unsigned long arg_start, arg_end, env_start, env_end;
unsigned long rss, total_vm, locked_vm;
unsigned long def_flags;
unsigned long cpu_vm_mask;
unsigned long swap_address;
unsigned dumpable:1;
#ifdef CONFIG_HUGETLB_PAGE
int used_hugetlb;
#endif
/* Architecture-specific MM context */
mm_context_t context;
/* coredumping support */
int core_waiters;
struct completion *core_startup_done, core_done;
/* aio bits */
rwlock_t ioctx_list_lock;
struct kioctx *ioctx_list;
struct kioctx default_kioctx;
};
C
복사
대표적인 부분을 보면 아래와 같습니다.
•
text
start_code, end_code
•
data / bss
start_data, end_data
•
heap
start_brk, end_brk
•
stack
start_stack
•
mmap
vm_area_struct
mm_struct에 저장된 정보는 사용자 공간에서의 주소를 뜻하며, 커널 스레드는 사용자 공간을 점유하지 않기 때문에 mm은 NULL입니다.
커널 스레드의 경우 전용 커널 스택(kernel stack)을 가지고, 해당 커널 스택은 task_struct에서 관리됩니다.
사용자 공간에서의 메모리를 관리하는 구조체는 mm(mm_struct)이며, 커널 공간에서 메모리를 관리하기 위해서 task_struct 구조체를 사용합니다.
즉 커널 스레드를 생성하는 것은 커널의 PCB(task_struct)를 복사하여 해당 테스크에 독립적인 커널 스택과 실행 컨텍스트(ex. CPU State Vector)를 할당하여, 동일한 커널 코드 위에서 서로 다른 커널 작업을 수행하는 것으로 이해할 수 있습니다.
Process State
테스크의 상태(state)에 대해 알아보겠습니다.
#define TASK_RUNNING 0
#define TASK_INTERRUPTIBLE 1
#define TASK_UNINTERRUPTIBLE 2
#define TASK_STOPPED 4
#define TASK_ZOMBIE 8
#define TASK_DEAD 16
C
복사
테스크는 크게 4가지의 상태를 가질 수 있습니다.
1.
ready or running
TASK_RUNNING의 state를 가지고 있습니다.
CPU에서 실행중인 경우 running, ready queue에 있는 경우 ready의 상태로 볼 수 있습니다.
2.
wait
sleep하고 있는 상태입니다.
TASK_INTERRUPTIBLE의 state의 경우 시그널이 오는 경우 TASK_RUNNING로 변경되며, TASK_UNINTERRUPTIBLE의 state는 시그널이 와도 TASK_RUNNING로 변경되지 않습니다. → 주로 I/O 대기
3.
zombie
TASK_ZOMBIE의 state의 경우 프로세스가 종료되어 대부분의 자원은 회수되었지만, 부모에게 전달할 종료 정보만 PCB(task_struct)에 남아 있는 상태입니다. → 부모 프로세스에서 wait()을 호출하면 해당 task_struct는 완전히 제거됩니다.
4.
stopped
TASK_STOPPED의 state의 경우 SIGSTOP, SIGTSTP, SIGTTIN, SIGTTOU 등의 시그널에 의해 프로세스의 실행이 일시적으로 중단된 상태입니다.
5.
dead
TASK_DEAD의 state의 경우 프로세스가 완전히 소멸되는 단계로, task_struct가 제거되기 직전 또는 제거 중인 상태입니다.
Linux Scheduling Policy
스케줄링이란 여러 테스크 중에서 어떤 테스크에게 CPU를 할당할 지 결정하는 작업이며, 단일 코어 CPU의 경우 한 번의 하나의 테스크만 처리 가능합니다.
하나의 테스크만 실행할 수 없기 때문에 여러 개의 테스크이 존재할 경우, 해당 테스크를 번갈아 가면서 수행되도록 관리하는 과정이 필요합니다. → 실제로 노래를 들으면서 카톡을 보내고 영상을 보는 것과 같은 의미, 여러 개의 작업을 동시에 처리해야 함
즉 스케줄링은 테스크가 CPU를 사용하는 순서를 결정하는 알고리즘이라고 볼 수 있습니다.
Priority
전통적인 스케줄러는 어떤 테스크에게 CPU를 할당할지 결정할 때 2가지를 고려하여 CPU를 양도합니다.
1.
timeslice
CPU에서 실행될 수 있는 시간
2.
priority
우선 순위
Time slice
햄 슬라이스을 생각해보면 햄을 얇게 자른 것입니다.
이와 동일하게 타임 슬라이스(time slice)도 CPU 실행 시간을 작은 단위로 나눈 것 입니다.
만약 특정 테스크에게 CPU를 무한정 할당 한다면, 해당 테스크가 종료(exit)될 때 까지 다른 테스크를 실행할 수 없을 것 입니다.
이를 방지하기 위해 테스크에 CPU를 할당할 때는 타임 슬라이스(Time slice)의 단위로 CPU를 할당합니다.
여기서 문제가 발생하는 경우를 보겠습니다.
만약 100ms의 타임 슬라이스를 할당받았는데, 우선 순위(Priority)가 높은 테스크가 CPU를 뺏어가 해당 테스크의 타임 슬라이스가 80ms가 남아 있습니다.
이렇게 남아 있는 시간을 remaining timeslice로 보존되며, 해당 테스크가 다시 스케줄링 될 때 이어서 사용합니다.
Ready Queue
Ready Queue는 실행 가능한 상태(TASK_RUNNING)의 테스크가 존재합니다. 실제 구조체를 보며 어떤 식으로 구현되어 있는지 알아보겠습니다.
Linux 커널은 Ready Queue는 CPU별로runqueue의 구조체로 구현됩니다.
struct runqueue {
spinlock_t lock;
unsigned long nr_running, nr_switches, expired_timestamp,
nr_uninterruptible;
task_t *curr, *idle;
struct mm_struct *prev_mm;
prio_array_t *active, *expired, arrays[2];
int prev_cpu_load[NR_CPUS];
#ifdef CONFIG_NUMA
atomic_t *node_nr_running;
int prev_node_load[MAX_NUMNODES];
#endif
task_t *migration_thread;
struct list_head migration_queue;
atomic_t nr_iowait;
};
C
복사
•
prio_array_t *active
실행 가능한 테스크 Queue
•
prio_array_t *expired
time slice 소진 테스크 Queue
만약 하나의 Ready Queue에 너무 많은 테스크(task_struct)가 할당된다면, 다음 테스크가 CPU를 할당받기 까지 많은 시간이 걸릴 수 있습니다.
이를 해결하기 위해 우선 순위(Priority) 별로 Queue를 만드는 방법으로 해결할 수 있습니다.
우선 순위 별로 Queue를 만들 때 고려할 사항이 존재합니다. 일단 구조체 먼저 보겠습니다.
Ready Queue는 prio_array 구조체를 이용하여 테스크를 관리합니다. 여기서 MAX_PRIO는 가질 수 있는 우선 순위(Priority) 개수가 되며, 총 140개의 우선 순위(Priority)를 사용합니다.
struct prio_array {
int nr_active;
unsigned long bitmap[BITMAP_SIZE];
struct list_head queue[MAX_PRIO];
};
#define MAX_USER_RT_PRIO 100
#define MAX_RT_PRIO MAX_USER_RT_PRIO
#define MAX_PRIO (MAX_RT_PRIO + 40)
C
복사
140개의 우선 순위를 모두 순회한다면, 테스크가 존재하지 않는 Queue에 접근하는 불필요한 연산이 발생합니다.
Linux 커널은 이를 방지하기 위해서 bitmap으로 관리합니다.
우선 순위(Priority) 개수만큼의 bit를 가진 bitmap을 사용하며, 해당 우선 순위 Queue에 테스크가 있다면 1, 없다면 0이 설정됩니다.
이 bitmap을 이용하면 모든 우선 순위 Queue를 순회하지 않고도 테스크가 존재하는 queue[priority]를 빠르게 찾을 수 있습니다.
CPU에서 테스크를 처리하기 위해는 4가지 단계가 존재합니다.
1.
bitmap을 스캔하여 1로 설정된 우선 순위 active Queue의 priority 반환
2.
해당 인덱스에 해당하는 Queue의 테스크를 가져와 CPU에 할당
3.
active Queue에 있는 테스크를 다 처리했다면 expired Queue와 sawp
4.
expired Queue에 존재하는 테스크에 새로운 time slice 할당
잠깐 정리를 하고 넘어가겠습니다.
Linux 커널의 Ready Queue는 CPU별로runqueue 구조체로 구현된다고 했습니다.
•
prio_array_t *active
실행 가능한 테스크 Queue
•
prio_array_t *expired
time slice 소진 테스크 Queue
runqueue에는 active와 expired 두 개의 prio_array가 존재하며, active Queue에 있는 테스크에 CPU를 할당하고 time slice를 소진하면 테스크를 expired Queue로 이동시킵니다.
active Queue가 비여있는 상태가 되면, expired Queue에 있는 테스크를 다시 active Queue로 이동시켜야합니다.
이 과정을 커널에서 어떻게 처리하는지 보겠습니다.
runqueue 구조체 관점으로 봤을 때 active Queue와 expired Queue는 포인터로 존재합니다.
두 Queue는 동일한 prio_array 구조체를 사용하기 때문에, 커널은 테스크를 이동시키는 대신 active Queue와 expired Queue를 가르키는 포인터를 swap하여 논리적으로 Queue를 전환합니다.
array = rq->active;
if (unlikely(!array->nr_active)) {
/*
* Switch the active and expired arrays.
*/
rq->active = rq->expired;
rq->expired = array;
array = rq->active;
rq->expired_timestamp = 0;
}
C
복사
테스크는 active Queue와 expired Queue에 저장되어 CPU를 할당받거나 반납합니다.
이렇게 bitmap을 이용하여, active Queue와 expired Queue를 교체하면서 CPU를 할당하는 것을 O(1) 스케줄링이라고 부릅니다.
Kernel Preemption
지금까지 컨텍스트 스위칭(Context Switching)과 스위칭할 테스크를 선택하는 스케줄링(Scheduling)에 대해서 알아보았습니다.
컨텍스트 스위칭은 한 가지 테스크만 실행하는 것이 아니라 여러 테스크를 실행하기 위해서 필요하며, 여러 테스크를 공정하게 실행하기 위해서 스케줄링이 필요하다는 점까지 이해했습니다.
이제 컨텍스트 스위칭이 발생하는 환경, 즉 컨커런트 컴퓨팅(Concurrent Computing) 상황에서 고려해야할 사항에 대해서 알아보겠습니다.
Mutual Exclusion(상호 배제)
상호 배제(Mutual Exclusion)를 설명하기 전에 하나의 상황 먼저 보겠습니다.
여러 테스크를 동시적으로 실행할 때 공유 자원에 접근하면 문제가 발생할 수 있습니다.
예를 들어 아래의 코드를 실행한다고 가정해보겠습니다.
x++
C
복사
위 코드는 아래의 어셈블리로 컴파일됩니다.
mov eax, DWORD PTR[x] // read
add eax, 1 // operation
mov DWORD PTR[x], eax // write
Assembly
복사
즉 C로 작성한 1줄의 코드도 기계어로 컴파일되는 경우 3단계로 분리되어 실행됩니다.
여기서 x가 Process A와 Process B가 공유하여 접근하는 메모리 주소이며, 공유 메모리에 접근한 횟수를 기록하겠습니다.
문제가 되는 경우 실행 과정을 어셈블리 단계로 분해해서 보겠습니다.
x = 11 //총 접근 횟수 11번
Process A:
mov eax, DWORD PTR[x] //x = 11임으로 eax에 11 저장, 12번째 접근
add eax, 1 // eax = 11 + 1임으로, eax = 12
//아직 x에 업데이트된 12를 저장하지 않은 상태
Context Switching // B 프로세스 실행
Process B:
mov eax, DWORD PTR[x] // x = 11이 저장되어 있는 상태, 13번째 접근
add eax, 1 // eax = 11 + 1임으로, eax = 12
mov DWORD PTR[x], eax // x의 주소에 12를 저장
Context Switching // A 프로세스 실행
Process A:
//레지스터 복원, eax = 12
mov DWORD PTR[x], eax // x의 주소에 12를 저장
x = 12 //총 접근 횟수 13번
Assembly
복사
위 코드에서 x는 두 번 접근하여 13이 되어야 하지만, 저장된 값은 12입니다. 이는 공유 메모리에 경쟁 상태(Race Condition)이 발생한 상황입니다.
예제를 알아보았으니, 용어 정리를 해보겠습니다.
•
임계 구역(critical section)
둘 이상의 테스크가 공유 자원(ex. 공유 메모리, 파일 등등)에 접근하는 코드 영역
•
상호 배제(mutual exclusion)
임계 구역에 동시에 하나의 테스크만 접근하도록 하는 원칙
•
경쟁 상태(race condition)
상호 배제가 제대로 이루어 지지 않아, 논리적으로 예상한 결과와 다르게 동작하는 상황
사용자 모드(User Mode)에서 경쟁 상태로 문제가 발생하면, 일반적으로 해당 프로세스만 종료되면 됩니다.
반면 커널 모드(Kernel Mode)에서 경쟁 상태로 문제가 발생하여 커널이 종료된다면, 커널 패닉(kernel panic, ex. 블루스크린)이 발생하여 시스템을 사용할 수 없는 상태가 됩니다.
이를 확장하여 커널 모드(Kernel Mode)에서는 어떤 메모리든 접근 할 수 있습니다. 커널 모드 테스크 간의 컨텍스트 스위칭이나 선점이 발생하는 경우 공유 메모리에 접근하는 상황이 발생할 수 있습니다.
이를 초기 UNIX 시스템에서는 아래와 같은 방식으로 해결했습니다.
실행 중인 테스크가 사용자 모드로 실행되고 있다면, CPU를 회수하여 컨텍스트 스위칭을 수행합니다.
반면 커널 모드로 실행되는 테스크라면, CPU를 회수하지 않고 사용자 모드로 복귀하는 시점에 CPU를 회수합니다.
이처럼 커널 모드로 실행 중에 선점을 허용하지 않는 방식을 No CPU Preemption in Kernel이라고 합니다.
위 방식에도 문제가 존재합니다.
만약 커널 모드에서 실행 중인 테스크가 사용자 모드로 복귀하기 까지 오랜 시간이 걸린다면, 다른 테스크들은 해당 커널 테스크의 실행이 끝날 때 까지 계속 대기하게 됩니다.
이를 해결하기 위해 커널 모드에서도 CPU를 회수할 수 있도록 수정되었습니다.
Kernel Stack
sh 프로세스와 mail 프로세스가 각각의 PCB(task_struct)를 커널에 가지고 있습니다.
각 프로세스는 고유한 커널 스택을 보유하고 있으며, 시스템 콜이나 인터럽트를 통해 커널 함수를 실행할 때 해당 커널 스택을 사용합니다.
커널 함수에서 지역 변수(Local Variable)에 접근하는 경우, 각 테스크는 개별 커널 스택을 사용하여 경쟁 상태(race condition)가 발생하지 않습니다.
반면 전역 변수(Global Variable)와 같이 커널 내에서 공유되는 데이터에 접근하는 경우, 해당 코드 영역은 임계 구역(critical section)이 됩니다.
이러한 임계 구역(critical section) 실행 중에 컨텍스트 스위칭이 발생하면 경쟁 상태(race condition)로 인해 문제가 발생할 수 있습니다.
이때까지 블로그 글에서 Linux Kernel v2.5.74의 소스 코드를 기준으로 설명했으나, 해당 커널은 비선점(non-preemptive) 방식으로 동작합니다.
강의 자료에서는 Linux kernel v2.6.4 기준으로 설명하고 있어, 이후 코드 분석에서는 Linux kernel v2.6.4로 진행하겠습니다.
유닉스 커널의 경우 커널 모드 실행 중에는 선점을 허용하지 않는(non-preemptive)으로 컨텍스트 스위칭을 하지 않는 방식이였습니다.
Linux 커널은 커널 모드에서 경쟁 상태(race condition)을 방지하기 위해서 lock과 unlock 개념을 도입하여 상호 배제(Mutual Exclusion)을 보장합니다.
비선점(non-preemptive) 방식 → 커널 모드 실행 중에는 CPU 선점을 허용하지 않음
선점(preemptive) 방식 → 커널 모드에서도 임계 구역이 아니라면 CPU 선점을 허용
위에서 공유 자원에 접근하는 경우만 문제가 발생한다고 했습니다.
공유 자원(ex. Global Variable)에 접근하는 경우, 해당 임계 구역 코드에서는 lock을 사용하여 다른 테스크가 접근할 수 없도록 만들고 공유 자원의 접근이 끝나면 unlock 하여 다른 테스크가 접근할 수 있도록 합니다.
lock이 걸려있다면 커널 모드와 사용자 모드 둘다 CPU를 선점하지 못하고, unlock이라면 임계 구역(critical section)이 아니라고 판단하여 CPU를 선점합니다.
Linux 커널은 lock과 unlock으로 상호 배제를 보장하며, 스케줄링을 수행하기 위해 두 개의 변수를 사용합니다.
1.
preempt_count
현재 테스크가 선점이 가능한지 불가능한지 나타내는 카운터입니다.
선점을 비활성화하는 구간(ex. spinlock)에 진입하면 증가하고, 해당 구간을 벗어나면 감소합니다.
preempt_count가 0이 아니라면 임계 구역 코드가 실행중 임으로 CPU를 선점하지 않습니다.
2.
need_resched
스케줄링이 필요할 때 설정되는 플래그입니다.
preempt_count가 0이 아닌 경우 선점되지 않으며, 0이 되는 시점에 스케줄링이 수행됩니다.
즉 선점되는 시점은 아래와 동일하게 preempt_count = 0 AND need_resched가 1인 경우 수행됩니다.
Linux 커널은 task_struct 구조체를 가지고 컨텍스트 스위칭을 진행합니다.
반면 스케줄링 가능 여부는 thread_info 구조체를 통해 판단합니다.
이는 task_struct 구조체의 경우 접근 비용이 크기 때문에, 스케줄링 가능 여부는 빠르게 접근 가능한 thread_info 구조체를 통해 preempt_count 카운터와 need_resched 플래그를 확인합니다.
struct thread_info {
struct task_struct *task; /* main task structure */
struct exec_domain *exec_domain; /* execution domain */
__u32 flags; /* low level flags */
__u32 status; /* thread synchronous flags */
__u32 cpu; /* current CPU */
int preempt_count; /* 0 => preemptable,
<0 => BUG */
mm_segment_t addr_limit;
struct restart_block restart_block;
void __user *sysenter_return;
#ifdef CONFIG_X86_32
unsigned long previous_esp; /* ESP of the previous stack in
case of nested (IRQ) stacks
*/
__u8 supervisor_stack[0];
#endif
int uaccess_err;
};
C
복사
정리
결국 커널 모드에서 안전한 컨텍스트 스위칭을 위해 선점 가능한 경우와 선점이 불가능한 경우를 구분했습니다.
커널 모드에서 임계 구역(critical section)에 접근하는 경우, 경쟁 상태(race condition)를 방지하기 위해 CPU 선점을 허용하지 않고 임계 구역이 아닌 경우 CPU 선점을 허용합니다.
이와 같이 다른 테스크가 동일한 공유 자원에 접근하지 못하도록 하는 것을 상호 배제(mutual exclusion)를 충족한다고 합니다.
이러한 상호 배제를 충족하기 위해 고안된 방식이 lock과 unlock 개념이며, 커널 코드에서는 spinlock으로 구현되어 있습니다.
이번 강의에서 배운 내용을 종합하면, 테스크를 효율적으로 관리하기 위한 스케줄링에 대해 배웠습니다.
스케줄링 과정에서 발생하는 컨텍스트 스위칭 시, 커널 모드에서 실행되는 테스크의 CPU를 선점하기 위해서 고려할 사항이 존재했습니다.
경쟁 상태(race condition)를 방지하기 위해, 임계 구역(critical section)에 접근하는 시점은 lock을 걸어 공유 자원에 대한 다른 테스크의 접근을 차단하고, 선점이 발생하지 않도록 차단합니다.
이후 임계 구역(critical section)을 벗어나면 unlock하여 다시 스케줄링이 가능하도록 합니다.
결국 비선점(non-preempt) 방식으로 작동하던 커널을 선점(preempt) 방식으로 확장하기 위해 필요한 개념들에 대해 알아보았습니다.

















