운영체제 #9 — xv6에 LWP와 프로세스 매니저 만들기

두 번째 프로젝트는 두 덩어리였다. xv6에 LWP(스레드)를 만드는 것과, 그걸 활용하는 pmanager라는 프로세스 관리자를 만드는 것이다.

시작하기 앞서 git branch 설정 오류로 master branch가 한 번 날아갔었다. 새로 master를 만들어 진행했고 main은 임시 백업용으로 뒀다. 위키는 master 기준이다.

설계

pmanager

pmanager는 다섯 가지 기능을 지원한다.

• list — 현재 실행 중인 프로세스들의 정보를 출력한다. 스레드별로 출력하지 않고 하나의 프로세스로 출력한다. "실행 중"은 RUNNABLE, RUNNING, SLEEPING 상태를 의미한다. ptable을 for문으로 스캔해 프로세스 정보만 출력한다.
• kill — <pid>를 받아 그 프로세스를 kill 시스템 콜로 죽인다. kill은 성공 시 0, 실패 시 -1을 반환하므로 그걸로 성공 여부를 출력한다.
• execute — <path> <stacksize>를 받아, path의 프로그램을 stacksize만큼의 스택용 페이지를 주면서 실행한다. 기존 exec는 stacksize를 받지 않고 스택용 페이지 1개와 가드용 페이지 1개만 주므로, **exec2**라는 시스템 콜을 새로 만든다. 그리고 실행 후 pmanager가 대기하면 안 되므로 shell의 백그라운드 실행(&) 방식을 참고한다.
• memlim — <pid> <limit>을 받아 setmemorylimit 시스템 콜로 제한한다. limit은 스레드까지 포함한 메모리 크기를 고려한다.
• exit — pmanager를 종료한다.

pmanager도 shell처럼 입력을 받고 그에 맞는 action을 취하므로 sh.c를 참고해서 구현한다.

LWP

LWP는 다른 LWP와 자원과 주소 공간을 공유해서 유저 레벨에서 멀티태스킹을 가능하게 해주는 개념이다. xv6에는 없는 thread를 만든다.

thread 또한 process이고, process 하나 또한 thread이므로 proc 구조체에 필드 몇 개를 추가하는 방식으로 구현한다. pthread를 참고해보면 커널에서는 모든 스레드가 서로 다른 pid를 갖고, 같은 프로세스에 속한 스레드들은 같은 tgid를 갖는 것으로 보인다. 유저가 getpid를 호출했을 때는 그 tgid를 반환하는 것으로 보인다.

만들 함수는 셋이다.

• thread_create(thread_t *thread, void *(*start_routine)(void *), void *arg) — 스레드를 만들고 start_routine에서 시작한다. 첫 인자에 만들어진 스레드 번호를 넣어주고, 세 번째 인자는 start_routine에 넘겨줄 값이다. 성공 시 0, 공간 부족 등의 에러 시 -1을 반환한다. 호출한 프로세스의 pgdir을 공유하게 해서 자원과 주소 공간을 공유한다.
• thread_exit(void *retval) — 스레드를 종료하고 반환값을 전달한다. 이 값은 thread_join에서 받아갈 값이다.
• thread_join(thread_t thread, void **retval) — 해당 스레드가 존재하면 exit할 때까지 sleep한다. 이미 종료되어 zombie라면 자원을 정리한다. thread_exit에서 전달한 리턴값을 retval에 저장한다. 없으면 -1, 정상 종료 시 0을 반환한다. 자원 회수는 free 함수가 메모리를 관리하는 방식을 참고할 생각이었다. 할당 해제를 하지 않고 freelist에 안 쓰는 영역을 넣어뒀다가 다시 꺼내 쓰는 방식이다.

그리고 스레드 환경에서 기존 시스템 콜들이 어떻게 동작해야 하는지를 다시 정의해야 한다. fork는 호출한 스레드만 복사하고, exec는 호출한 스레드를 제외한 모든 스레드를 정리하고, sbrk는 여러 스레드가 동시에 불러도 공간이 겹치면 안 되고, exit과 kill은 프로세스 안의 모든 스레드를 종료시켜야 한다.

구현

proc 구조체

추가한 필드들이다.

• int pid — 모든 프로세스와 스레드가 각자의 pid를 가진다.
• int tgid — 하나의 프로세스에 속한 스레드들이 main thread의 pid를 thread group id로 공유한다.
• void *retval — 스레드가 리턴값을 저장하는 필드. thread_exit에서 인자로 받은 주소를 여기 저장하고, thread_join에서 인자로 넣어준 곳에 전달한다.
• struct proc *mainThread — 가장 처음 프로세스의 기초가 되었던 스레드.
• struct proc *createThread — 이 스레드를 만든 스레드. main이 아닌 스레드에서 thread_create을 호출하면 mainThread != createThread인 경우가 생긴다.
• struct freelist fl[20] — thread_join 후 비게 되는 스택을 담아두는 배열. umalloc.c의 free() 아이디어를 참고했다. valid가 1이면 top 주소가 addr인 빈 스택이 있다는 뜻이고, 0이면 유효하지 않다는 뜻이다. fl[0].valid가 0이면 빈 스택이 없으니 새로 할당받아야 한다.
• uint stack — 이 스레드가 할당받은 스택의 top 주소. 스택을 freelist의 addr에 넣을 때 쓴다.

proc.h — 스레드를 위해 추가한 필드들.

freelist 구조체. valid가 1이면 addr이 top인 빈 스택이 있다는 뜻이다.

이 필드들은 allocproc, userinit, fork, exec(exec2), thread_create에서 초기화한다.

• allocproc — 처음 할당할 때 tgid를 pid와 같게 초기화한다. 스레드가 아닌 프로세스도 기본적으로 자기만의 thread group에 속해 있는 셈이다.
• userinit — 스레드가 아닌 프로세스는 자기 자신이 곧 mainThread이자 createThread다. fl 안의 값들은 모두 0으로 초기화한다. 여분의 스택이 없는 freelist를 만드는 것이다.
• fork — 스레드에서 호출하면 그 스레드만 복사한다. curproc의 createThread가 자신이라면(= 스레드가 아닌 프로세스라면) 기존 흐름과 같아서 createThread는 자신이 되고, 스레드라면 curproc과 같은 createThread를 가진다. fl은 curproc의 것을 그대로 복사한다.
• exec — 스레드에서 호출했을 때도 고려해야 하므로 tgid를 자신의 pid로 세팅한다. createThread, mainThread, fl은 userinit처럼 설정한다.

allocproc — tgid를 자신의 pid와 같게 초기화한다.

thread_create

fork와 exec 코드를 참고했다. 먼저 ptable에서 프로세스를 하나 받아온 뒤, 현재 프로세스(스레드)의 mainThread의 fl에 쓸 수 있는 스택이 있는지 확인한다. 있으면 그걸 쓰고, 없으면 새로 할당받는다. 있으면 새 스택을 할당받기 전 jump label로 건너뛴다.

그리고 새로 만든 스레드의 mainThread와 createThread를 설정하고, exec처럼 스택에 인자로 받은 arg와 fake return address를 넣는다.

• 새로 할당받은 스택이라면 sz가 늘어났을 것이므로 tgid가 같은 모든 스레드의 sz를 늘려준다.
• 스택을 재활용하는 것이라면 새 스레드의 sz에 원래 sz만 넣고, 사용한 addr를 fl에서 제거한다.

thread_create — ptable에서 슬롯을 받고 재사용 가능한 스택을 찾는다.

새 스레드의 mainThread와 createThread 설정.

thread_exit과 thread_join

thread_exit은 file 참조(fd 관련)와 cwd를 close하고(ref 감소), 현재 스레드의 retval에 인자를 저장한다. 그리고 자신을 만들어준 스레드를 깨워 자원을 처리할 수 있게 한다. 만든 스레드가 자신이 만든 것을 치우는 게 자연스러운 흐름이라고 봐서, createThread만이 join을 호출하도록 구현했다.

thread_exit — 자신을 만든 스레드를 깨운다.

thread_join은 tgid가 다른 스레드는 건너뛰고, 인자로 받은 thread와 pid가 같은 같은 프로세스 안의 스레드를 찾는다. 존재하고 zombie라면 kstack을 free하고 user stack 부분을 clear해서 mainThread의 fl에 추가한다. 그리고 retval에 값을 넣고 나머지 자원도 wait처럼 정리한다. 못 찾으면 -1을 리턴하고, 있지만 zombie가 아니라면 sleep한 채로 대기한다. (그래서 thread_exit에서 깨워줘야 한다.)

removeFree()는 mainThread의 fl에서 가장 앞 entry를 제거하고 앞으로 당기는 것이고, addFree(uint stack)은 인자를 addr에 추가하고 valid를 1로 세팅해 fl의 가장 앞에 넣는 것이다.

thread_join — zombie 스레드의 스택을 회수해 freelist에 넣는다.

스레드 환경에 맞춘 시스템 콜

• fork — 스레드만 복사하므로 기존과 같은 방식이다. 필드 초기화 외에는 바꾸지 않았다.
• exec/exec2 — 호출한 스레드를 제외한 나머지를 정리해야 하므로 clearThread()를 만들었다. 자신과 tgid가 같은 스레드들의 자원을 제거한다. 이때 pgdir은 exec에서 정리하므로 freevm은 하지 않아도 된다.
• sbrk — 여러 스레드가 동시에 할당을 요청하면 겹치면 안 되므로 ptable lock을 건다.
• kill — 같은 tgid를 가진 스레드들의 killed를 모두 1로 세팅한다.
• sleep — 기존 그대로 써도 자신만 잠든다. 각 스레드가 서로 다른 pid를 가지도록 구현했기 때문이다.
• pipe — 스레드를 만들 때 fd를 복사해 가므로, pipe를 한 후 스레드를 만들어 그 fd를 쓰면 문제없이 출력된다.
• exit — 모든 스레드가 죽어야 하므로 clearThread를 쓴다.

clearThread() — 자신을 제외하고 같은 tgid인 스레드를 정리한다.

sbrk — 동시 할당이 겹치지 않도록 ptable lock을 건다.

kill — 같은 tgid인 스레드의 killed를 모두 1로 세팅한다.

exec2와 setmemorylimit

**exec2**는 기존 exec에서 2 page만 할당하던 부분을 stacksize + 1로 바꾼 것이다. 가장 밑 한 페이지를 guard용으로 만들 때는 clearpteu를 이용한다.

setmemorylimit(int pid, int limit) 은 limit이 양수이고 이미 차지한 사이즈보다 큰지 확인한 후 유효하면 설정한다. 0은 무제한을 의미한다. 여기서 설정한 값을 growproc이나 스레드를 만들 때 참고해 제한한다.

exec2 — 2 page 할당을 stacksize + 1로 바꾼 부분.

setmemorylimit — limit이 이미 차지한 크기보다 큰지 확인한다.

pmanager

sh.c의 입력 함수를 참고해 getcmd2를 만들고, main에서 그걸 while 조건으로 넣어 에러가 없는 한 무한 루프를 돌게 했다.

• list — 직접 만든 proList 시스템 콜을 호출한다. pid, name, stackpage 수, 메모리 사이즈, 메모리 limit을 출력한다. 메모리 사이즈와 limit은 스레드 전체를 고려한 값이고, stackpage 수는 메인 스레드가 다른 스레드의 스택을 쓰지 못하므로 자기 것만 출력한다.
• kill — 해당 pid가 존재하면 그 pid를 가진 프로세스 전체를 kill한다. (여기서 pid는 tgid를 의미한다.)
• execute — path와 stacksize를 따로 읽는다. stacksize는 atoi로 읽는다. sh.c의 백그라운드 실행을 참고해서 fork()를 두 번 하고, 마지막 자식에서 exec를 하고 첫 번째 자식이 exit()한다. 맨 위 부모는 exit한 자식의 자원만 처리하고, exec한 자식의 자원은 initproc이 처리하게 하는 방식이다.
• memlim — 0이면 무제한, 양수면 그 크기만큼 제한한다. 이미 가진 메모리보다 작게 설정하려 하면 실패를 출력한다.
• 올바르지 않은 command면 <command not found>를 출력한다.

결과

pmanager. thread_test를 execute하고 list를 입력하면 정보가 나온다.

execute로 thread_test를 띄우고 list를 찍은 결과.

memlim은 기존 limit보다 적게 설정하려 할 때는 실패하고, 성공했을 때는 limit이 반영된다.

이미 차지한 크기보다 작은 limit은 실패하고, 유효한 값은 반영된다.

thread_test. 스택 재사용을 확인하려고 create와 join 때 주소값을 출력하게 했다. Test 1(basic)에서 만들어진 스레드의 스택이 잘 회수되었다.

Test 1 — create와 join의 주소가 맞물려 스택이 회수된다.

Test 2(fork)에서는 Test 1에서 쓰였던 32768과 24576이 먼저 재사용되고, 그다음부터 freelist가 비어서 40960, 49152, 57344가 새로 할당되었다. 그리고 다시 모두 freelist로 들어갔다. Test 3(sbrk)에서는 위에서 쓰던 스택을 그대로 재사용했고 sbrk도 겹치지 않았다.

Test 2 — freelist에 남아 있던 스택이 먼저 재사용된다.

• thread_exec / thread_exit / thread_kill — exec는 정상적으로 성공 메시지를 출력했고, exit은 출력하지 않아야 할 메시지를 출력하지 않고 모든 스레드를 종료시켰다. kill은 fork로 다른 프로세스에서 5개씩 스레드를 만든 뒤 thread_2에서 thread_1을 kill하는 테스트였고, 메시지가 정확히 5번 출력되었다.

Trouble Shooting

pmanager

list를 인식하지 못했다. buf[4] = ' '로 해버려서 그랬고, buf[4] = '\n'으로 바꾸니 해결됐다.

kill을 여러 번 하니 안 됐다. 입력값을 확인해보니 전에 입력했던 것이 포함되어 나왔다. pmanager 시작할 때 pid를 0으로 초기화하고 루프 안에서는 초기화하지 않아서 생긴 문제였다. kill문 안에서 0으로 초기화해줬다.

스레드

removeFree 호출 위치. t->stack = ~ 이전에 removeFree를 넣어버려서 실제 할당한 스택 주소와 join 시 memset하는 스택 주소가 달라졌다. 그래서 user 공간에서 trap 14가 발생했다. removeFree를 아래로 옮겨서 해결했다.

중복 acquire. allocproc()을 쓸 때 acquire lock이 중복되어 panic이 났다. allocproc 안에서 이미 acquire를 하기 때문이었다. allocproc 후에 lock을 얻도록 바꿨다.

ustack 인자. thread_create 시 exec처럼 인자 수와 0을 넣어줬더니 스레드가 이상한 값을 읽어왔다. 단순하게 arg를 넣는 방식으로 바꾸니 정상 작동했다.

switchuvm. thread_create 마지막에 switchuvm을 할 때 새로 만든 스레드를 넣어줬더니 panic이 발생했다. curproc으로 바꾸니 정상 작동했다. 같은 pgdir을 공유하니 상관없을 줄 알았는데 아니었다. 이유는 아직 잘 모르겠어서 계속 찾아봐야겠다.

growproc. sbrk 테스트를 할 때 single thread에서는 문제가 없었는데 여러 개를 쓰니 remap panic이 났다. growproc할 때 curproc의 size만 바꿔서 그랬다.

deallocation과 copyuvm. 중간에 끼어 있던 스레드를 join할 때 그 스레드의 스택을 deallocation하려 했더니 copyuvm: page not present 오류가 났다. 알고 보니 copyuvm은 0부터 sz까지 page 단위로 copy하는데, deallocation을 해버리면 PTE_P가 0으로 세팅되어 오류가 난 것이었다. 즉 중간에 끼어 있는 스레드의 스택은 deallocation할 수 없다. *pte = 0으로 처리했다. 그리고 deallocation 이후 fork를 하면 문제가 생기므로, fork 하기 전에 빈 공간을 allocuvm 해줬다. addr는 나중에 fork할 때 참고하려고 지우지 않았다.

copyuvm: page not present — 중간 스레드의 스택을 해제한 뒤 fork한 결과.