[정글] WEEK09 - WIL : 정글끝까지 PintOS Proj_2 User Program 회고

PintOS Proj_2 User Program

Project 1 에서는 커널에 있는 thread와 커널에서 일어나는 일들, interrupt handler와 scheduling 등에 대한 과제를 수행했다. 이번주차부터는 User Program을 실행시키기 위한 작업들을 해나간다. 그 중에서도 Project 2는 user program 실행시 입력된 argument들을 program에서 사용할 수 있도록 user영역에 넘겨주는 작업 Argument Passing, user가 system call을 호출할 때 전달한 인자의 유효성을 검사하는 작업 User Memory, user가 호출한 system call을 수행하고, 적합한 return값을 돌려주는 작업 System Calls, user process가 종료될 때 종료메세지를 띄워주는 작업 Process Termination Messages, 실행 중인 파일에 대해 수정되지 않도록 조치하는 작업 Denying Writes to Executables 을 수행한다.

Argument Passing

PintOS는 부팅되면서 먼저 kernel의 thread, interrupt, timer, syscall 등의 기능들에 대해 초기화한다. 이후 입력된 인자를 바탕으로 User Program을 실행시킬 준비를 한다.

먼저 커널은 들어온 command line에서 filename을 parsing하고 해당 name으로 program을 실행시키기 위한 thread(process : PintOS에서는 멀티쓰레딩이 지원되지 않아 process는 thread와 동일시될 수 있다)를 생성한다.link

filename으로 생성된 thread가 schedule되면 이 thread는 User Program이 실행될 수 있도록 여러가지 환경을 만들어준다: interrupt frame, user memory(initializing, loading), arguments.link

Interrupt Frame link
Context를 switching할때는 실행되던 context를 나중에 그대로 되살릴 수 있도록 저장해두어야 한다. 이는 schedule로 인한 thread간의 switching 뿐만 아니라 동일 thread에서 kernel과 user간의 switching 시에도 필요하다. 이를 위해 context를 저장하는 frame을 PintOS에서는 interrupt frame(if)이라고 한다. thread간의 switching에서는 tcb(thread control block)에 위치한 if을 사용하며(thread launch() in schedule()), kernel-user간 switching에는 kernel thread의 stack영역에 if를 쌓아 사용한다. kernel-user간 switching은 user mode로 process 실행 도중 interrupt 발생 또는 exception, trap(syscall) 발생 등에 의해 일어난다.

User Memory link
Process들은 각각 독립된 가상 메모리 영역을 갖는다. 따라서 User Program을 실행할 때마다 가상 메모리 공간을 세팅해야 하며, 실행가능한 파일 형식인 ELF(Executable and Linkable Format)의 세그먼트 정보에 따라 program을 물리 메모리로 load하고 가상 메모리 주소와 mapping 시킨다.

Arguments link
User program을 실행시키기 위해 입력된 Command line은 한 줄로 되어있다. 따라서 kernel은 arguments를 parsing해야하며 실제 user program이 실행될 때 이 arguments를 사용할 수 있도록 인자로 전달해주어야 한다. user program은 user 가상 메모리 영역 안에 있는 data에 접근할 수 있기 때문에 user의 stack영역에 arguments를 setting하고 if를 통해 user program이 실행될 때 main함수의 인자로 argc와 argv가 전달될 수 있도록 if의 rdi, rsi에 값과 해당 포인터를 저장한다. stack에 쌓인 arguments 바로 아래엔 fake return address를 넣어주고, if의 rsp를 fake return address가 저장된 곳을 가리키도록 변경해준다.

이러한 환경이 모두 완성되면 kernel은 작성한 if를 인자로 do_iret(interrupt return)함수를 실행하고 cpu의 register들을 if에 저장된 값으로 바꾸어 줌으로써 User program을 실행시킨다.

User Memory

Process(또는 thread)가 진행되는 동안 실행되는 instruction 중 일부는 특별한 권한이 있어야만 실행할 수 있도록 되어있다. 이를 Privileged Instruction 이라고 한다. 이러한 instruction은 kernel(ring0)만 실행될 수 있고 user(ring3)는 실행할 수 없다. 이는 하드웨어가 가장 높은 권한을 가지고 있으며 하드웨어가 kernel만 해당 instruction을 실행할 수 있도록 정해두었기 때문에 그렇다. 하드웨어는 code를 실행할 때 해당 segment에서 권한을 표시하는 특정 bit를 확인하고 cpu의 mode bit를 설정한다. 그리고 이 mode bit에 따라서 instruction을 수행할지 말지 결정한다.

User는 Previleged Instruction을 직접 수행할 수 없지만 때로는 해당 instruction들이 실행되어야 한다. 예를 들면 디스크에서 파일을 읽고 쓰거나 자식 프로세스를 생성해야하는 경우 등이 있다. 이를 위해 운영체제는 사용자를 대신하여 kernel이 이 instruction을 수행할 수 있도록 system call을 지원한다.

X86 Architecture에서 system call은 일반적인 exception과 동일한 방식으로 동작하였다고 한다. 이 일반적인 방식이란 exception이 먼저 발생하고 exception vector table에서 해당되는 handler를 찾아 실행되는 방식이다. 이와 다르게 X86_64 에서는 syscall이라는 instruction을 지원하여 user가 system call을 호출하면 trap이 발생하고 바로 syscall handler로 진행되도록 한다.

User가 System call을 호출하여 인자를 넘겨주면 kernel에서는 해당 인자가 유효한지 확인해야한다. 특히 들어온 인자가 virtual address라면 해당 주소가 유효한 주소인지 (kernel 영역을 접근하고 있지는 않은지, NULL을 넘겨준 것은 아닌지, User에게 할당된 영역이 맞는지) 반드시 확인한 후 해당되는 함수를 진행해야 한다.

System Calls

운영체제는 부팅할 때 system call이 호출되면 어떠한 instruction들을 수행한 뒤 handler 함수를 진행하도록 하드웨어를 설정한다. 이후 user program이 실행되고 user program에서 system call을 호출하면 하드웨어는 설정된 instruction들을 수행하고 system call handler를 실행한다.

PintOS에서는 syscall 호출시 syscall_entry.S에 작성된 instruction을 먼저 수행한다. 이는 tss로부터 저장된 kernel stack에서의 stack pointer를 가져와 rsp에 세팅하고, kernel stack으로 이동하여 user mode에서 실행되던 context를 stack에 interrupt frame 형식으로 쌓는다. 그리고 마지막 rsp의 값(if를 가리키는 주소)를 rdi에 저장하고 handler 함수로 이동함으로써 함수의 인자로 if를 전달한다.

System call handler에서는 인자로 들어온 if의 rax값을 확인(syscall을 수행하기 전에 syscall number를 rax에 저장하기 때문)하여 해당되는 syscall 요청에 따라 함수를 수행한다. 인자로 들어온 값들이 정상적이라면 syscall number에 따라 요청받은대로 작업을 진행한 뒤 if의 rax에 return 값을 setting하고, if을 인자로하여 do_iret함수를 호출함으로써 syscall을 호출한 user에게 해당되는 return값을 돌려주게 된다. 이로써 system call이 완료된다.

---

System call interface에는 exit, wait, exec, fork 등의 process 관련 함수들과 open, read, write, close 등의 file system 관련 함수들이 존재한다. 이들 중에서도 필자가 느끼기에는 fork가 가장 system call 동작 방식을 이해하기에 적합하다고 느꼈다.

Fork system call은 fork를 호출한 process와 동일한 자식 process를 생성하는 함수이다. 특이한 점은 return을 두 번 한다는 점이다. 부모에게는 자식의 pid(tid)를 return하지만 자식에게는 0을 return 한다. 이로써 부모와 자식에 따라 다른 code를 실행하도록 분기할 수 있다. 그렇다면 kernel은 fork를 어떻게 처리해야하며, 어떻게 해야 두 번의 return을 진행할 수 있을까?

우선 user가 fork를 호출하면 다른 system call과 동일하게 trap이 발생된 뒤 kernel mode에서 syscall handler가 실행되고, syscall number가 저장된 if의 rax의 값에 따라 해당되는 함수가 실행된다. 실행된 함수에서는 들어온 인자(fork의 경우 user에서 자식 process의 name을 인자로 전달함)가 유효한지 확인하고, 유효하다면 fork를 진행한다.

우선 부모 process의 kernel mode에서, 자식 process를 생성하기 위해 실제 fork를 진행하는 함수와 user context가 담긴 if를 인자로하여 thread를 create한다. 이때 create을 진행하면서 생성되는 자식 thread를 부모 thread의 자식 리스트에, 그리고 부모 thread를 자식 thread의 부모 필드에 저장한다. 또한 부모는 자식 process가 fork를 마치기까지 기다려야하므로 자식 thread의 fork_sema를 0으로 초기화한다. 자식 thread의 create을 마치면, 부모 process는 자식 thread의 fork_sema를 sema down하여 자식 process가 fork를 마치고 신호를 줄 때까지 대기한다.

자식 thread가 schedule되면 본격적으로 부모 process를 fork한다. 여기서 중요한 점은, fork의 대상은 fork를 호출한 부모 process의 user관련 context라는 점이다. 부모와 동일한 process를 생성한다고 하면 kernel mode에서 실행되던 context까지 전부 동일해야 할 것 같지만, 사실 user mode로 실행되던 context만 동일하게 만들면 되는 것이다(자식 thread가 schedule 되어 실행되는 순간부터 이미 부모와 자식은 다른 kernel context를 실행하고 있다). 이러한 점에서 fork가 어떻게 부모와 자식에게 다른 return값을 전달하게 되는지 의문이 풀리게 된다.

자식 thread는 thread create시 인자로 전달된 함수와 인자로 fork를 진행한다. 부모 process의 user if를 kernel stack에 복제하고 가상 메모리 공간과 메모리들을 모두 복제한다. 또한 부모의 file descriptor table과 file table들을 그대로 복제하여 자식 process의 그것들에 setting 한다. 이러한 일련의 작업들이 성공적으로 진행되면 자신의 thread에 있는 fork_flag를 갱신하고 fork_sema 를 sema up하여 fork가 완료되기를 기다리는 부모 process를 깨워준다. 마지막으로 부모로부터 복제했던 if의 rax값을 0으로 setting한 뒤 do_iret을 실행하여 user에게 return하게 된다.

Sema down하고 기다리고 있었던 부모 thread가 schedule되면 자식의 fork_flag를 통해 fork가 정상적으로 이루어졌는지 확인하고, 정상적이라면 자식의 pid값을 if의 rax에 담고 do_iret을 실행하여 user에게 또한 return 한다. 이로써 부모와 자식은 kernel mode의 각각 다른 위치(부모는 system call handler, 자식은 do_fork)에서 if - rax 값을 setting하고 return하였지만 user process는 동일한 fork를 실행한 결과로 각각 다른 return 값을 받게 된다.

Process Termination Messages

User process가 자식 process를 생성하면 부모 process는 자식 process를 청소할 의무(?)가 생긴다. 부모 process가 만일 자식 process보다 먼저 종료되면 자식 process는 실행하지도 종료하지도 못하는 상태(좀비 process)가 되기 때문이다. 따라서 부모 process는 어느 시점에서 자식 process가 termination 되기를 wait 한다.

자식 process의 user program이 main함수에서 0을 return하거나 exit(0)을 호출하면 exit system call이 실행된다. 그 결과로 kernel mode에서는 user program을 위해 사용되었던 file descriptor table과 file table, 가상 메모리 공간 등을 모두 청소하고 exit여부와 exit status를 저장하며 자신의 exit_sema를 sema up한 뒤 다른 thread를 schedule함으로써 process를 종료한다.

자식 process를 wait하던 부모 process가 schedule 되면 자식이 종료된 것을 확인하고 자식 thread를 청소하며 자식의 exit status를 if - rax에 저장한 뒤 user에 return한다.

PintOS는 termination message를 통해 자식 process의 exit과 부모 process의 wait이 정상적으로 작동되는지 확인한다. 하여 해당 chapter에서는 exit system call에서 exit되는 thread name과 exit status를 출력하도록 구현한다.

Denying Writes to Executables

User Program이 load될 때 loader는 실행파일을 open하고 ELF 정보를 읽어 실행시키는데 필요한 segment를 memory로 load한다. 이후에 기존에 구현되어있는 PintOS에서는 해당 file을 close하고 program을 실행시키도록 되어있다. 그러나 파일이 실행되는 중간에 코드가 변경되는 등의 파일 수정이 발생하면 예상치 못한 상황이 생길 수 있기에 실행되고 있는 파일은 수정될 수 없도록 보호할 필요가 있다.

File을 open하면 file system은 file로부터 metadata를 inode 구조체 형식으로 읽어온다. 그리고 이 inode를 가리키며 파일을 읽거나 쓰는 위치를 가리키는 offset pointer를 갖는 file 구조체를 만든다. Kernel은 process마다 file의 pointer를 저장하는 배열을 만들어 관리하며, 이것을 file descriptor table이라 하고 이 table의 file을 구분할 수 있는 구분자 index를 file descriptor라고 한다.

inode는 모든 process를 통틀어 동일한 file이라면 한 개만 생성된다. 즉, 모든 process는 동일한 file에 대해 유일한 inode를 갖는다(== 다른 process가 수정하면 모든 process에서도 수정된다 == inode는 공유자원이다). 이 inode의 member중에 하나(deny_write_cnt)가 파일을 수정할 수 있는지의 여부를 저장한다. 값이 0이면 수정 가능하며 1이상이면 수정이 불가하다. 대표적인 파일 수정 interface인 write함수에서도 이 값을 확인하고 수정이 가능할 때 수정을 진행하는걸 확인할 수 있다. 이렇듯 파일의 수정여부를 inode에 저장하며 inode는 공유자원이므로 해당 값을 1 이상으로 변경함으로써 다른 process로부터 file이 수정되는 것을 막을 수 있다.

File system은 이러한 값을 변경할 수 있도록 파일의 수정을 막기위한 file_deny_write와 파일의 수정을 허용하는 file_allow_write interface를 제공한다. 추가로 file을 닫는 file_close는 file_allow_write를 내장하고 있다. 따라서 program load시 file open 직후 file의 수정을 막도록 조치하고 file을 close하지 않은 상태로 유지한 뒤, program 종료시 해당 file을 close 함으로써 실행중인 파일이 수정되는 것을 막을 수 있다.

회고

지난 Project에서는 kernel에서 일어나는 일만 다루다가 user program으로 넘어오면서 헷갈리고 어려운 부분들이 많이 있었다. 쓰레드는 어디에 위치하는 것이며 지난주부터 등장했던 인터럽트 프레임은 도대체 어디에 쓰이는 것인가... 가상메모리 영역에도 스택이 있는데 커널 쓰레드에도 스택이 있고 그럼 rsp는 대체 어딜 가리키고 있는 것인가... 처음에 이런 질문에 부딪히면서 골치아프고 힘들었지만, 이 의문들이 해소되고나서는 이후의 문제들은 어렵지 않게 풀어갈 수 있었던 것 같다. 위에서 그런 내용들을 잘 정리해두긴 했지만, 들었던 의문점들에 대해 다시한번 정리해보려 한다.

1. 쓰레드는 어디에 위치하는 것인가? 지난 Project에서도 thread를 다루었는데 그럼 kernel의 일을 하는 thread가 있고 User program을 위한 thread가 따로 있는 것인가? 그럼 User program을 위한 thread는 user의 가상메모리 영역에 있는 것인가???
-> (실제 linux 등의 운영체제는 다르겠지만 PintOS에서는) 커널의 일을 하기위한 쓰레드가 따로 존재하는건 아니다. 지난 Project에서는 테스트를 위해 여러개의 쓰레드를 만들고 sleep 시키는 등을 했지만, 실제로는 PintOS가 부팅될 때 main thread를 만들고 main thread에서 User program을 실행시키기 위한 쓰레드를 만든다. 물론 timer, disk, syscall등을 initialization하지만 이들을 위한 쓰레드가 따로 있는 것은 아니다. User process에서 interrupt나 system call과 같이 kernel의 권한으로 실행되어야하는 instruction이 있을 때 동일한 thread 내에서 user mode에서 kernel mode로 이동되며, 이때 kernel에서 준비된 code들을 실행하게 되는 것이다.
-> User program을 위한 thread는 기존에 thread가 생성될 때 그러하였듯이 page allocator에 의해 동일한 kernel영역에 만들어진다. Kernel mode로 code가 진행될 때에는 이 kernel영역에 있는 thread 내의 stack을 사용한다. 그래서 kernel-user mode 전환시 interrupt frame이 쌓이는 곳도 바로 이 stack이다. User mode에서 user code가 진행될 때에는 user를 위한 가상메모리 영역의 stack을 사용한다. 멀티쓰레딩이 가능한 OS에서는 이 user stack영역을 thread마다 할당하여 나누어 사용하지만, PintOS에서는 One Process-One Thread이기 때문에 user stack영역은 따로 나누어지지 않고 해당 process가 전부 사용한다. 멀티쓰레딩이 가능한 OS의 경우 하나의 kernel thread에 여러개의 user thread가 매칭될 수도 있고, 여러개의 kernel thread가 여러개의 user thread에 매칭될 수도 있다.

2. 도대체 인터럽트 프레임은 무엇인가? 인터럽트 발생시 정보를 담고있는 구조체? 그렇다면 왜 register 정보를 담고있는거지? 어디에 사용되고 있는건가??
-> 기본적으로 인터럽트 처리를 위해 사용되는 frame이 맞다. Frame 안에 있는 vec_no 로 해당 interrupt가 어떤 interrupt인지 판단하고 interrupt handler를 가리키고있는 vector table에서 해당 interrupt를 해결하기 위한 handler가 실행되도록 할 수 있다. 이 외에도 interrupt를 처리한 뒤 interrupt가 발생하기 전의 context로 돌아갈 수 있도록 해당 context를 저장하는 역할을 한다. Interrupt 발생시 intr_stubs.S의 intr_entry가 실행되어 rsp를 user stack에서 kernel stack으로 이동하며 kernel stack에 현재 register를 interrupt frame형식으로 저장한다. Interrupt handler 진행이 완료되면 interrupt frame에 저장되어있는 context를 다시 cpu로 restore시켜 기존의 user program context로 돌아갈 수 있게 된다.
-> 하지만 이 interrupt frame은 이 외에도 가능한 context switching에서 사용된다. System call 발생시에도 동일한 방법으로 kernel-user mode간에 전환이 일어난다. 또한 schedule에 의한 thread간의 switching에서도 interrupt frame이 사용되는데, 이 때에는 user program의 context가 아닌 kernel mode에서의 context가 필요하므로(schedule은 timer interrupt의 handler처리 후 종료시점에서 일어나거나 system call 처리 중 sema down/up하는 경우 등 kernel mode에서만 발생함) thread의 tcb에 구성해둔 interrupt frame을 사용하여 switching 전 thread의 context를 저장하고 switching 대상 thread의 interrupt frame을 restore하여 switching하게 된다.

이번 Project에서는 code가 어떻게 진행되는지 이해하기 위해 assembly 언어를 이해할 필요성을 많이 느꼈다. 기계어와 맞닿아있는 부분이라 많이 어렵지만 확실히 assembly를 이해하려고 노력하다보니 어떠한 방법으로 운영체제가 user program을 실행시키고 요청사항을 처리해주는지 잘 이해할 수 있었다.