pintOS › pintOS 쓰레드 이론 정리 두 번째(Week8_Day3)
오늘은 어제에 이어서 pintOS 1주차의 개념을 정리한다.
쓰레드(Threads)
쓰레드의 생성과 실행
쓰레드가 처음 생성 될 때, 새로운 실행 컨텍스트를 생성하는 것으로 이 컨텍스트에서 실행 될 함수를 thread_create()의 인자로서 전달한다.
쓰레드가 처음 실행 될 때, 해당 함수는 main()함수처럼 함수의 처음 부터 실행 되며 함수가 리턴되면 쓰레드 또한 종료된다.
쓰레드 스케쥴링과 컨텍스트 스위치
어떠한 시점에서든 쓰레드는 딱 하나만 실행되고 나머지 쓰레드들은 비활성화 된다.
스케쥴러는 어떤 쓰레드를 다음에 실행할지를 결정하고, 실행할 준비가 된 쓰레드가 없다면 idle()이 내장된 idle 쓰레드가 실행된다.
다른 쓰레드의 작업을 기다려야 하는 쓰레드가 있다면 동기화를 통해 컨텍스트 스위치를 강제 할 수 있다.
컨텍스트 스위치는 현재 실행 중인 쓰레드의 상태를 저장하고, 스위칭할 쓰레드의 상태를 복원한다.(자세한 메커니즘은 이해하지 않아도 괜찮다)
실행할 때는 GDB 디버거를 사용해서 컨텍스트 스위치가 어떻게 일어나는지 살펴보도록하자. shecule()함수에서 시작하여 쓰레드의 주소와 상태를 살펴보고 각 쓰레드의 콜스택에는 어떤 작업이 있는지, 한 쓰레드가 do_iret() 에서 iret를 실행하면 새로운 쓰레드가 실행 된다는 것을 알 수 있을 것이다.
pintOS에서는 각 쓰레드 들이 약 4kb의 고정된 스택을 할당하고 있다.
스택 오버플로우를 확실하게 탐지할 수 없기 때문에 큰 데이터 구조를 로컬 변수로 선언하면 터질 수 있다.
때문에 페이지 할당기나, 블록 할당기를 사용하는 것을 추천한다.
Page Allocater
페이지 할당기는 페이지 단위로 메모리를 할당하며(4KB) 메모리를 두 개의 풀(커널, 사용자)로 나누어 기본적으로 둘은 반반을 차지한다.
페이지 할당기는 메모리의 사용상태를 비트맵으로 추적하며 각 페이지가 사용중인지 아닌지를 표시한다. 페이지 할당은 선착순으로 연속된 페이지를 찾고 해당 비트를 설정하여 사용중으로 표기한다.
페이지를 할당 받을 때 페이지 단위로 할당하므로 메모리 단편화를 야기한다.
한 페이지를 할당한다.
1
palloc_get_page()
여러 페이지를 연속으로 할당한다.
1
palloc_get_multiple()
한 페이지를 해제한다.
1
palloc_free_page()
여러 페이지를 해제한다.
1
palloc_free_mulitple()
메모리 할당에 실패하면 커널이 패닉 상태가 되도록 한다.
이는 커널의 초기화 중에만 사용하고, 유저 프로세스는 절대로 커널을 패닉시켜서는 안된다.1
PAL_ASSERT할당된 페이지의 내용을 0으로 초기화 한다.
1
PAL_ZERO사용자 풀에서 페이지를 할당 받는다(기본적으로는 커널 풀에서 할당받는다).
1
PAL_USER
Block Allocator
블록할당기는 페이지 할당기 위에 레이어드 된 메모리 할당기이다.
블록은 크기가 다양한 메모리 조각을 할당받는데 사용되며, 커널 풀에서 메모리를 할당받는다.
요청된 블록 크기가 1KB 이하일 경우에는 블록 크기를 2의 제곱으로 올림하여 페이지 내에서 할당하고, 블록크기가 1KB를 초과하게 되면 해당 크기와 약간의 오버헤드를 포함하여 페이지 단위로 페이지를 요청한다.
새로운 블록을 커널 풀로부터 받아 반환하며 최소 바이트 길이의 블록을 반환하고, 크기가 0이거나 메모리를 할당 받지 못할 경우 NULL 포인터를 반환한다.
1
malloc(size_t size)
마찬가지로 새로운 블록을 받환하는데, 최소 a * b 바이트 길이의 블록을 반환하며 블록의 내부를 0으로 초기화 하여 제공한다. a 또는 b가 0이면(a*b = 0) 또는 충분한 크기의 메모리가 없으면 NULL 포인터를 반환한다.
1
calloc(size_t a, size_t b)
블록을 주어진 새로운 사이즈로 재조정을 하기위해 사용하며, 성공하면 새로운 블록을 반환하고, 실패하면 NULL 포인터를 반환하며 기존의 블록은 유효하게 유지된다. block포인터가 NULL이라면 malloc과 같은 역할을 한다. size 가 0이라면 free의 역할을 한다.
1
realloc(void *block, size_t new_size)
할당 해제 함수
1
free(void *block)
페이지 할당기와 블록 할당기 모두 interrupt 컨텍스트에서는 호출할 수 없고, 메모리를 해제할 때는 블록의 모든 바이트를 0xcc로 초기화 한다.
Priority Scheduling(우선순위 스케쥴링)
우선순위 스케쥴링이란 말 그대로 각 쓰레드에 할당된 우선순위를 바탕으로 높은 우선 순위를 가진 쓰레드가 먼저 CPU를 사용할 수 있도록 하는 것이다.
- 새로운 쓰레드가 준비 리스트에 추가될 때
만약 현재 실행 중인 쓰레드 보다 새로운 쓰레드의 우선순위가 높다면, CPU를 양보해야 한다. - 락, 세마포어, 조건 변수에서 대기중 일 때
가장 우선순위가 높은 쓰레드가 깨어난다. - 쓰레드가 자신의 우선순위를 낮추는 경우
즉시 CPU를 양보해야 한다.
이를 구현하기 위해서는 우선순위 필드를 추가하여 각 쓰레드의 우선순위를 표기하고, 쓰레드를 스케쥴링 할 때마다 우선순위를 비교하며 가장 높은 우선순위의 쓰레드를 선택해야한다. 현재 쓰레드의 우선순위가 낮아졌을 때는 더 높은 우선순위의 쓰레드에게 CPU를 양보한다.
Priority Donation(우선순위 기부)
우선순위 기부는 우선순위 역전을 해결하기 위한 방법으로, 높은 우선순위를 가진 쓰레드가 낮은 우선순위의 쓰레드에게 블록을 당할 때 발생하는 것이 우선순위 역전이다.
이를 단순하게 해결하는 것이 어 그럼 낮은 애를 높은애로 만들면 되네? 였다.
즉 높은 우선순위의 쓰레드의 우선순위를 낮은 쓰레드에게 기부하여 더 빨리 실행될 수 있도록 하는 것이다.
만약 A라는 락을 보유한 쓰레드가 실행중이고, B라는 쓰레드가 A의 락을 기다리고 있다면, A의 우선순위를 B보다 높게 하고(기부) 락이 해제 될 때, 다시 기존의 우선순위로 복원 하게 된다.
이는 단지 두 쓰레드 사이에서만 일어나는 것이 아니라, 여러 쓰레드가 하나의 쓰레드에게 우선순위를 기부할 수도 있다.
예를 들어 A가 B에게 기부하고, B가 C에게 기부를 하면, 중첩 되어 모두 C에게 전달되게 된다.
이를 구현하기 위해서는, 각 쓰레드의 실제 우선순위와, 기부된 우선순위를 따로 관리할 필드가 필요하고, 락 구조체를 수정하여 누가 락을 소유하고 있는지 추적하여 우선순위를 기부 받을 수 있도록 하여야 한다.
기부된 우선순위를 기준으로 쓰레드의 우선순위를 고려하며, 잊지않고 락이 해제될 때 원래 우선순위로 복원한다.
위의 마지막 처럼 중첩된 우선순위 기부가 발생했을 경우 우선순위 역전이 발생하지 않도록, 각 기부체인을 따라가며 우선순위를 복원한다.
해당 함수는 아래와 같다.
현재 쓰레드를 new_priority 로 설정한다. 물론 설정 후에 현재 쓰레드가 가장 높지 않다면 CPU를 양보한다.
1
thread_set_priority(int new_priority)
현재 쓰레드의 우선순위를 반환하며, 우선순위 기부가 발생했을 경우에는 기부 된 우선순위 중 가장 높은 값을 반환한다.
1
thread_get_priority(void)
Advanced Scheduler
pintOS에서는 Advanced Scheduler의 구현을 4.4BSD스케쥴러와 유사한 다단계 피드백 큐 스케쥴러(Multilevel Feedback Queue Scheduler, MLFQ)를 만드는 것이다.
이 스케줄러는 최근 CPU 사용량과 niceness 값을 기반으로 쓰레드의 우선순위를 동적으로 조절한다. 이는 CPU 연산을 많이 하는 작업과 I/O를 많이하는 작업 사이의 균형을 통해 쓰레드가 행동과 우선순위에 적절하게 배치되도록 하는 것을 추구한다.
MLFQ 스케줄러는 여러개의 Ready Queue를 가지고 있다. 각 큐는 같은 우선순위를 가진 쓰레드 들로 구성되어 있으며, 스케줄러는 비어있지 않은 가장 높은 우선순위를 가진 Ready Q에서 라운드 로빈 방식으로 고르게 된다.
RR방식(라운드 로빈) : 쓰레드간의 우선순위를 두지 않고 순서대로 정해진 시간 단위로 CPU를 할당하며, 실행 후 리스트의 맨 뒤로 이동한다.
Niceness 값은 각 쓰레드가 다른 쓰레드에게 얼마나 친절(양보해야)하는가 를 나타내며 -20 ~ 20 사이의 값을 가진다. 기본값은 0 이다.
양수는 우선순위를 낮추어 양보를 하게 하고 음수값은 우선순위를 높여 더 많은 CPU 시간을 갖도록 한다.
쓰레드는 언제든지 nice값을 설정하여 자신의 우선순위를 변경 할 수 있도록 하고, 4틱마다 우선순위는 재계산 되며 시스템이 재조정될 때 더 이상 최고 우선순위가 아니면 즉시 CPU를 양보한다.
CPU 사용 시간이 많을 수록 우선순위는 낮아지며, 골고루 CPU 시간을 사용할 수 있도록 하는 목적이 있다.