지난 주 학습과의 관련
지난 주까지 Web Proxy를 학습하면서 CSAPP의 8장(예외적인 제어흐름), 10장(시스템 수준 입출력), 11장(네트워크 프로그래밍), 12장(동시성 프로그래밍)에 있는 내용들을 부분적으로 학습을 해야 했었는데, 이번 프로젝트를 통해 인터럽트가 어떻게 발생하는지, 스레드는 어떻게 만들어지고 어떻게 컨텍스트 스위칭이 일어나는지, 어떻게 동기화를 하는 지 등을 알아볼 수 있었다.
프로젝트를 완성하고 이해하기 위해 필요한 운영체제 사전지식
- 인터럽트에 대한 기본적인 이해
- 스레드
- 동기화(세마포어, 락, 모니터 등)
이번 프로젝트는 어떤 프로젝트인가?
스레드는 어떻게 만들어지고 어떤 구조로 생겼는지 파악하고, 자원에 대한 동기화를 여러 방법으로 진행해본다.
pintos project1은 스레드와 동기화 관한 이야기이다. 스레드에 대해 학습을 하다보면 user thread와 kernel thread를 구분 짓는 것을 찾아 볼 수 있을 것인데, 이 pintos project1는 kernel thread를 다루는 프로젝트이다.
pintos 프로젝트는 틀이 만들어진 상태에서 운영체제 및 컴퓨터 시스템에 대한 지식을 가지고, 부분적인 문제를 개선하고, 필요한 것들을 만드는 프로젝트라고 할 수 있는데 양이 워낙 방대하기 때문에 프로젝트의 의도를 잘 파악하여 프로젝트를 진행하는 것이 바람직하다고 느껴진다.
예를 들어, 학습을 하다보면 인터럽트에 대한 내용을 만날 것인데 256가지의 모든 인터럽트에 대한 내용을 학습하기는 힘들 것이고 context switching, 또는 다른 칩과의 연동을 위한 초기화를 위해 어셈블리어가 작성이 되어 있을 것인데, 이 어셈블리어를 왜 이렇게 쓰는지 완벽하게 이해하고자 한다면, x86-84의 칩 구성 및 ISA에 대해서도 알아야 할 것이다.
이렇듯 딥하게 공부하고자 한다면 정말 끝도 없는 영역이 될 수 있기 때문에 이미 구현된 것들을 인터페이스 처럼 받아들여서 감각적으로 이해하고 넘어가는 영역도 충분히 필요한 프로젝트라 할 수 있겠다.
핀토스 프로젝트는 어떻게 실행되는가?
핀토스 프로젝트는 어떤 과정을 거쳐 실행이 될까? 나는 이 부분이 어느정도 감각적으로 이해하고 넘어가야 하는 부분 중 하나라고 생각한다.
- 로딩은 pintos의 부팅 과정을 나타낸다. 부팅이란 컴퓨터가 구동하여 기초적인 초기화 작업을 수행하고 운영 체제를 읽어오는 일련의 작업을 의미한다.
- BIOS는 컴퓨터가 구동된 후 연결된 storage를 탐색해서 해당 장치가 부팅 가능한 정보를 가지고 있는 지 검사 후 부팅이 가능하다면 로더(loader)를 메모리에 올린다. 그리고 loader를 통해 커널을 디스크에서 찾아 메모리에 올린다. 핀토스 프로젝트에서 로더에 대한 코드는 thread/loader.S에 있다.
- 로더가 실행이 되었다면 이제 제어가 kernel의 entry point로 들어가게 된다. 이 커널의 entry point는 핀토스 프로젝트에서 thread/start.S 파일이라 할 수 있고 이 start.S가 실행되면서 low - level Kerenl Initialization이 수행된다.
- main 함수를 call한다.
정확하지는 않을 수 있겠지만 위와 같은 과정을 거친 후, thread/init.c에 있는 main함수를 실행시키면서 많은 것들을 초기화 하며 High - Level Kernel Initialization을 한다고 이해하면 되겠다.
main 함수를 통한 init에서 살펴볼 만한 함수들을 살펴보고 전체적인 구조 파악해보기
- intr_init()
- thread_init()
- thread_start()
- timer_init()
위의 함수들의 실행을 타고 들어가다보면 thread가 어떻게 되어 있는지 TCB를 나타내는 struct thread의 구조체는 어떻게 되어 있는지, 어디서 page를 alloc하여 스레드를 만드는지, intr_handler가 어디서 부터 call이 되어 idt와 함께 인터럽트를 처리하고자 하는지 등을 알아볼 수 있다. (이 또한 완벽한 이해는 힘들다)
나는 아래의 그림과 같이 함수의 시작부터 해서 하나씩 타고 들어가고 주석을 읽고 모르는 것이 나오면 검색을 해보면서 전체적인 구조를 이해해보고자 했다.
그리고 gdb 디버깅하는 방법을 배운 후 call stack을 확인하면서 함수가 어디서 어떻게 호출되는지 보면서 이해를 높여갔다.
위 그림은 처음에 전체적인 구조를 파악하기 위했던 일이고, 한글이 이리저리 적혀 있는데 틀린 내용도 있고, 추측성 내용도 많다.
인터럽트 관련
- PIC(Programmable Interrupt Controller)라는 controller가 존재하는데 이 칩은 인터럽트 입력 소스를 단일 인터럽트 출력으로 결합한다.
- intr_init()안의 pic_init() 함수는 out 인스트럭션으로 pic칩으로 데이터를 전송하면서 칩과의 세팅을 하고, pic 세팅이 끝나고 난 후 idt(interrupt descriptor table)을 초기화 한다.
- 최종적으로는 intr_handler()라는 함수에서 모든 인터럽트를 처리한다.(불이 났을 때와 같은 그런 인터럽트를 제외하고)
타이머 관련
- timer_init()함수를 통햇 PIT(Programmable Interval Timer)를 셋팅한다. 여기서는 8254칩이 PIT이다.
- timer_interrupt 또한 intr_handler를 통해 call이 된다.
- 타이머 인터럽트가 계속발생하면서 thread_tick()이 실행되는데 이때 thread_tick을 기준으로 특정 기준이 넘어가면 thread를 yield하도록 설계되어 있다. 즉, 라운드 로빈이 구현되어 있는 것이다.
스레드를 만들고 실행시키는 일
이전에는 스레드라는 것을 어떤 흐름이라는 추상적인 것으로 이해했다면, 이번 프로젝트를 통해 사실 스레드는 어떤 instruction이 실행될 수 있는 stack영역이 생기고, 그 stack영역 내에서 instruction들이 실행 될 수 있게 register의 값들이 바뀌고 struct thread라는 구조체에 context라고 할 수 있는 것들을 저장해 두는 것이다. 이 상황에서 스레드는 프로세서만 있으면 스레드에서 실행하고자 하는 일을 실행할 수 있다.
문맥교환
멀티 프로세스 또는 멀티 스레드 환경에서 하나의 제어를 다른 제어로 넘어갈 때 이때 제어를 안전하게 넘어가고 안전하게 돌아오게 하기 위해 그에 필요한 Context를 PCB 또는 TCB에 저장하고, 실행하고자 하는 새로운 프로세스, 스레드에 대한 PCB,TCB로 부터 값을 읽어 들여 register를 갱신하는 작업을 문맥교환이라고 한다.
즉, 레지스터 값을 변경한다는 말은 제어를 변경한다는 것이 되고, 프로세스나 스레드가 실행 중에 변경되어야 하기 때문에 context에 대한 구체적 정보를 저장하고 있어야 하는데 이런 부분을 PCB, TCB인 것이다.
pintos 프로젝트에서 TCB는 struct thread라는 구조체로 선언이 되고 스레드에 대한 스케쥴링을 바꾸다 보면 이 안의 값들도 변경해야하게 되는 경우들을 겪게 된다.
자원 및 동기화 그리고 멀티 스레드
자원이라고 하면 프로세서, 메모리라는 물리적인 자원이 될 수 도 있고 어떤 특정 데이터가 될 수 도 있다. 멀티스레드 환경에서 스레드가 차지하고 싶은 자원은 프로세서가 될 수 도 있고 어떤 변수나 데이터가 될 수도 있다. 즉, 이번 프로젝트는 이 자원에 대한 동기화 문제를 다뤄보는 프로젝트 인 것이다. 프로세서라는 자원, 특정 데이터에 대한 동기화 문제가 동시에 발생할 수 있고 그것도 해결해 본다.
전체적인 구조를 잘 이해하고 동기화, 스레드에 대한 개념이 잘 잡혀있다면 핀토스 PPT에서 설명하는 것들이 이해가 잘 될 수 있을 것이다.
alarm - clock
기존에 busy-waiting으로 구현되어 있는 pintos 프로젝트를 alarm - clock으로 구현을 한다. 기존 busy-waiting은 개념적으로는 ready와 run을 반복하는 상태이고, 코드 상으로는 모든 스레드들이 interrupt에 따라 계속해서 자원을 쓸 수 있는 지 확인하는 일이기 때문에 상당히 많은 context-switching을 유발한다.
그래서 스레드를 ready 상태로 주지 않고 block(sleep) 바꾼다. 이때, 현재 스레드가 언제 ready 상태가 되면 되면 될 지 시간을 저장할 수 있도록 한다.
priority scheduling
기존에 구현한 alarm-clock에서의 thread들은 FIFO 방식으로 스케쥴링된다. 단순히 FIFO 방식으로 구현이 되는 것을 우선순위를 주는 방식으로 개선을 해볼 수 있다. 이것이 priority scheduling이다.
ready_list에 들어가는 스레드들이 우선순위순으로 정렬이 되도록 하면 된다. 이때 조금 신경써서 생각해야 할 부분은 현재 실행 중인 스레드보다 우선순위가 더 높은 스레드가 만들어질 때 선점이 일어나도록 구현을 해야한다.
그리고 스레드들은 preemptive해서 우선순위가 높은 스레드가 생긴다면 자원을 빼앗길 수 있다.
priority scheduling - syncronization
이전까지는 동기화 해야하는 자원이 프로세서였다면, 그 상태에서 다른 공유자원까지 동기화가 되어야 하는 상황이다. 이를 동기화를 위해서 semaphore, lock, condvar(monitor, 정확히는 monitor에서 특수한 상황)을 이용하고, 그 자원들에 대해서 우선순위가 높은 스레드가 높은 우선순위를 가지고 대기할 수 있도록 한다.
주의) lock, semaphore을 쓴다는 것은 임계영역이 생긴다는 것이고, 임계영역에서는 atomic하게 실행될 수 있어야 한다. 더 높은 우선순위를 가진 스레드가 이 공유자원까지 preempt해버린다고 생각해버리면 안된다.
즉, synchronization하고자 하는 자원이 어떤 자원인지 잘 구별해서 생각해야한다. 이전까지는 공유하는 자원은 프로세서였고 preemptive가 가능한 상황이었고, 이런 상황에서 다른 공유자원이 있는데 임계영역에 대해서는 atomic하게 이뤄져야 한다. 그래서 프로세서를 빼앗길 수는 있어도 지금 lock을 건 공유자원을 빼앗겨서는 안된다.
바로 이 글을 본다면 이해가 안될 수 있지만, priority inversion problem을 donation으로 해결하는 과정을 통해 위 말이 어떤 말인지 이해할 수 있을 것이다.
위는 waiters가 FIFO로 구현되어 있는 상황이다.
위는 waiters를 priority로 개선한 것인데, 눈치가 빠른사람이라면, 여기서 core 개수가 thread 수 보다 충분히 많아서 preemption이 일어나지 않는 상황을 전제로 한 것이다. -> 이 문제는 아래의 priority inversion problem이라는 상황에서 donation이라는 기법을 통해 해결하는 것을 알 수 있다.
priority inversion problem - donation
위와 같은 상황에서는 core의 개수가 충분하여 preemption이 일어나지 않는 상황을 가정했다면 이번에는 그런 상황이 아니라, thread의 우선순위에 따라 preemption이 일어나고 그랬을 때 발생하는 priorty inversion problem을 donation으로 해결하는 상황이다.
아래의 그림과 같이 preemption이 일어나면 우선순위가 높으 스레드가 우선순위가 낮은 스레드를 기다리는 priority inversion problem이 일어난다.
Lock을 걸었으면 critical area를 침범하지 않으면서 프로세스가 진행되어야 하는데 파란색 스레드는 lock을 요구하지 않고, critical area에 접근하지 않는 스레드라고 보면 된다.
위와 같은 상황을 아래의 donation으로 해결할 수 있다.
위는 donation을 하면서 inversion problem이 일어나지 않는 것을 확인할 수 있다. 또한 lock 영역에 대해 atomic하게 하는 효과를 보이는듯(?) 하기도 하다.
추가적으로 multiple donation과 nested donation이 발생하는 상황을 고려할 수 있는데, 이는 위 개념을 제대로 이해했다면 핀토스 pdf자료를 바탕으로 이해할 수 있을 것이다.
구현 코드
priority inversion problem을 donation으로 해결 했다.
구현의 과정은 핀토스 pdf를 참고하는 게 좋고, 구현한 내용은 아래 링크로 첨부한다.
