[Operating System] xv6 Light Weight Process (LWP)
운영체제 과제로 진행한 xv6 project3에 대한 설명입니다.
정확하지 않은 내용일 수 있으므로 참고만 하시길 바랍니다.
전체 코드는 아래 링크에서 확인하실 수 있습니다.
https://github.com/LeeHyo-Jeong/HYU-ELE3021
[Design]
Light Weight Process
일반적으로 프로세스는 서로 독립적으로 실행되고, 자원을 공유하지 않으며 서로 별개의 주소 공간과 file descriptor를 가진다. 그러나 Light Weight Process(Thread)는 같은 프로세스 내의 다른 LWP와 자원과 주소 공간 등을 공유해 멀티태스킹을 가능하게 해준다.
같은 프로세스 내에 있는 스레드들은 프로세스 내의 code section, data section, open files을 공유하면서 실행된다.
따라서 한 스레드가 프로세스 자원을 변경하면, 같은 프로세스 내에 있는 스레드들은 그 결과를 즉시 확인 수 있다.
그러나 스레드들은 독립적으로 실행될 수 있도록 자신만의 레지스터와 스택을 갖는다.
OS마다 다르지만 프로세스는 작업을 수행하기 위해 32~64MB의 물리 메모리를 점유한다. 그러나 스레드는 1MB 이내의 메모리만 점유한다. 따라서 스레드를 Light Weight Process라고 부른다.
스레드를 사용하면 프로세스 내 자원들과 메모리를 공유하기 때문에 메모리 공간과 시스템 자원의 소모가 줄어들며, multicore CPU에서는 각각의 스레드가 다른 프로세서에서 병렬로 수행될 수 있으므로 병렬성이 증가한다.
main thread
메인 스레드는 프로그램이 시작하면 가장 먼저 실행되는 스레드이다.
모든 스레드는 메인 스레드로부터 생성되며, 모든 스레드들이 종료된 후 메인 스레드에서 join이 종료된다.
[Implement]
type
proc
기존에 정의되어있는 proc 구조체에 다음 필드들을 추가해 LWP의 기능을 할 수 있도록 하였다.
struct proc {
...
thread_t tid;
struct proc* main;
int threadFlag;
int mainFlag;
void* retval;
};thread_t
types.h에 새로운 타입을 정의하였다.
thread_t 타입 변수는 tid를 값으로 가지므로 다음과 같이 정의하였다.
typedef int thread_t;allocproc
xv6의 main 함수에서 userinit을 호출하고, userinit에서는 allocproc을 호출하여 첫 번째 프로세스를 생성한다.
allocproc을 통해 생성된 프로세스를 메인 스레드로 설정하기 위해 allocproc을 다음과 같이 수정한다.
static struct proc* allocproc(void){
...
found:
p->state = EMRYO;
p->pid = nextpid++;
p->mainFlag = 1;
p->main = p;
p->threadFlag = 1;
p->tid = nexttid++;
...
}growproc
malloc에서 growproc을 호출하여 프로세스 또는 스레드의 메모리 공간을 늘리거나 줄인다.
스레드에서 malloc을 호출해 메모리 공간을 늘리면 같은 프로세스 내의 다른 스레드들에게도 메모리 공간이 늘어났음을 알려야 한다. 따라서 ptable을 돌며 같은 프로세스 내의 스레드들의 sz 필드를 업데이트 해준다.
int growproc(int n){
...
main->sz = sz;
curproc->sz = sz;
for(p = ptable.proc ; p < &ptable.proc[NPROC] ; p++){
if(p->pid == curproc->pid)
p->sz = curproc->sz;
}
...
}exit
하나의 스레드에서 exit이 호출되면 그 프로세스 내의 모든 스레드가 종료되어야 한다.
따라서 ptable을 돌며 같은 프로세스 내의 스레드를 종료하도록 수정하였다.
void exit(void){
...
for(p = ptable.proc ; p < &ptable.proc[NPROC] ; p++){
if(p->pid == curproc->pid && p->tid != curproc->tid){
kfree(p->kstack);
p->kstack = 0;
p->pid = 0;
p->tid = 0;
p->parent = 0;
p->main = 0;
p->name[0] = 0;
p->killed = 0;
p->state = UNUSED;
p->threadFlag = 0;
p->mainFlag = 0;
p->retval = 0;
}
}
....
}thread_create
새 스레드를 생성하고 시작한다.
기존에 xv6에 구현되어 있는 exec.c의 exec, proc.c의 fork 함수를 참고하였다.
int thread_create(thread_t *thread, void *(start_routine)(void *), void *arg)thread: 해당 주소에 스레드의 id를 저장한다.start_routine: 스레드가 시작할 함수를 지정한다. 새로운 스레드가 만들어지면 그 스레드는 start_routine이 가리키는 함수에서 시작한다.arg: 스레드의 start_routine에 전달할 인자이다.return: 스레드가 성공적으로 만들어졌으면 0, 에러가 있다면 0이 아닌 값을 반환한다.
함수의 전반적인 흐름은 다음과 같다.
새로운 스레드 할당
allocproc 함수를 사용해 새로운 스레드를 할당한다.
allocproc 함수에서 mainFlag를 1로 초기화한다. 그러나 thread_create로 만들어지는 스레드는 메인 스레드가 아니므로 mainFlag를 0으로 바꾸어준다. 또한 allocproc에서 nextpid를 1 증가시키지만 thread_create 함수 내에서는 allocproc을 이용해 프로세스가 아니라 스레드를 할당한 것이므로 증가시킨 nextpid를 다시 1 감소시켜준다.
// allocate light weight process
if((np = allocproc()) == 0)
return -1;
nextpid--;
np->mainFlag = 0;메인 스레드 탐색
myproc()으로 얻은 현재 스레드가 메인 스레드가 아니라면 메인 스레드를 찾아서 변수 p에 할당한다.
// if curproc is not a main thread, find main thread
acquire(&ptable.lock);
if(curproc->mainFlag == 0){
for(p = ptable.proc ; p < &ptable.proc[NPROC] ; p++){
if(p->pid == curproc->pid && p->threadFlag == 1 && p->mainFlag == 1){
break;
}
}
}
else{
p = curproc;
}스레드 스택 설정
스레드의 메모리 크기를 페이지 경계로 반올림하고, 새로운 스레드 스택을 위한 메모리를 할당한다.
p->sz = PGROUNDUP(p->sz);
if((p->sz = allocuvm(p->pgdir, p->sz, p->sz + 2*PGSIZE)) == 0)
return -1;
clearpteu(p->pgdir, (char*)((p->sz)-2*PGSIZE));스레드 공유 메모리 공간 업데이트
같은 프로세스 내의 스레드들은 메모리를 공유한다. 메모리의 크기가 변동되었으므로 모든 스레드의 sz 필드를 새로운 값으로 업데이트 해준다.
// every thread in same process shares size
struct proc* q;
for(q = ptable.proc ; q < &ptable.proc[NPROC] ; q++){
if(q->pid == p->pid){
q->sz = p->sz;
switchuvm(q);
}
}스택 초기화 및 context 설정
사용자 스택을 초기화하고 인자로 전달될 값을 스택에 설정한다.
copyout 함수를 통해 스택 값을 스레드 주소 공간에 복사한다.
trapframe의 레지스터를 초기화해 thread_create가 자식에서 0을 반환하도록 하고 스레드의 시작 지점을 start_routine으로 설정한다.
if(copyout(np->pgdir, sp, ustack, 8) < 0)
return -1;
// clear %eax so that thread_create returns 0 in the child
np->tf->eax = 0;
np->tf->eip = (uint)start_routine;
np->tf->esp = sp;file descriptor 설정
file descriptor를 복사해 새로운 스레드가 동일 파일을 열도록 설정한다.
for(i = 0 ; i < NOFILE ; i++){
if(p->ofile[i])
np->ofile[i] = filedup(p->ofile[i]);
}
np->cwd = idup(p->cwd);
safestrcpy(np->name, p->name, sizeof(p->name));
switchuvm(curproc);스레드를 스케줄링 대상에 포함
새롭게 생성된 스레드를 RUNNABLE하게 바꾸어 스케줄러가 스케줄링 할 대상에 포함시키도록 한다.
acquire(&ptable.lock);
np->state = RUNNABLE;
release(&ptable.lock);thread_exit
스레드를 종료하고 값을 반환한다. 모든 스레드는 반드시 이 함수를 통해 종료한다.
기존에 xv6에 구현되어 있는 proc.c의 exit 함수를 참고하였다.
void thread_exit(void *retval)retval: 스레드를 종료한 후 join 함수에서 받아갈 값이다.
함수의 전반적인 흐름은 다음과 같다.
openfile 닫기
현재 스레드가 열어 놓은 모든 파일을 닫는다.
// close all open files
for(fd = 0 ; fd < NOFILE ; fd++){
if(curproc->ofile[fd]){
fileclose(curproc->ofile[fd]);
curproc->ofile[fd] = 0;
}
}종료 후 부모 메인 스레드 깨우기
메인 스레드가 현재 스레드가 종료되기를 기다리고 있을 수 있으므로 메인 스레드를 깨운다.
// main might be sleeping in wait()
//wakeup1(curproc->main);
if(curproc->mainFlag == 0){
wakeup1(curproc->main);
}
else{
wakeup1(curproc);
}고아 스레드 처리
현재 스레드가 종료되었으므로 현재 스레드의 자식 스레드들의 부모를 initproc으로 설정하여 initproc이 자식 스레드들이 종료 후 리턴 값을 받을 수 있도록 한다.
// pass abandoned children in init
for(p = ptable.proc ; p < &ptable.proc[NPROC] ; p++){
if(p->parent == curproc){
p->parent = initproc;
if(p->state == ZOMBIE)
wakeup1(initproc);
}
}리턴 값 저장
join 함수에서 받을 리턴 값을 저장한다.
// save return value
curproc->retval = retval;thread_join
지정한 스레드가 종료되기를 기다리고, 스레드가 thread_exit을 통해 반환한 값을 받아온다. 스레드가 이미 종료되었다면 즉시 반환한다.
기존에 xv6에 구현되어 있는 proc.c의 wait 함수를 참고하였다.
int thread_join(thread_t thread, void **retval)thread: join할 스레드의 idretval: 스레드가 반환할 값 지정return: 정상적으로 join했다면 0을, 그렇지 않다면 0이 아닌 값을 반환한다.
함수의 전반적인 흐름은 다음과 같다.
ZOMBIE 상태인 자식 스레드 탐색 후 해제
ptable을 돌며 thread_exit을 호출해 ZOMBIE상태가 된 자식 스레드를 탐색한 후 종료한다.
acquire(&ptable.lock);
for(;;){
havekids = 0;
// scan through table looking for exited thread
for(p = ptable.proc ; p < &ptable.proc[NPROC] ; p++){
if(p->tid != thread)
continue;
havekids = 1;
if(p->state == ZOMBIE){
// found one
*retval = p->retval;
kfree(p->kstack);
p->kstack = 0;
p->pid = 0;
p->tid = 0;
p->parent = 0;
p->main = 0;
p->name[0] = 0;
p->killed =0;
p->state = UNUSED;
p->threadFlag = 0;
p->mainFlag = 0;
p->retval = 0;
release(&ptable.lock);
return 0;
}
}exit_threads
exec이 실행되는 순간 같은 프로세스 내의 다른 스레드들은 모두 종료되어야 한다.
따라서 exec.c의 exec 함수에서 다른 스레드들을 종료시키기 위해 만든 system call이다.
ptable을 순회하며 pid가 같은 스레드들 중 현재 스레드를 제외한 모든 스레드를 종료시킨다.
exec 함수에서 다음과 같이 사용해 exec을 실행하는 순간 같은 프로세스 내의 다른 스레드들은 모두 종료되고 exec을 실행한 스레드를 메인 스레드로 변경한다.
...
struct proc *curproc = myproc();
exit_threads(curproc->pid);
curproc->main = curproc;
begin_op();
...
[Result]
thread_test
test 1
스레드 API의 기본적인 기능 (create, exit, join)과 스레드 사이에서 메모리가 잘 공유되는지를 평가한다.
스레드 0은 바로 종료하고, 스레드 1은 2초 후 종료한다. 두 스레드가 모두 종료된 후 메인 스레드에서 join이 잘 종료되어 test1을 통과한다.
test 2
스레드 내에서 fork 했을 때 올바르게 동작하는지 평가한다.
fork 이후 부모 프로세스는 기존 프로세스의 주소 공간에서 계속 동작해야 하고, 자식 프로세스는 분리된 주소 공간에서 동작해야 한다.
부모 프로세스와 자식 프로세스가 독립적인 공간을 가져 스레드 내에서 fork 했을 때 올바르게 동작하여 test2도 잘 통과한다.
test 3
스레드 내에서 sbrk가 올바르게 동작하는지 평가한다. malloc을 사용하면 내부적으로 sbrk가 할당된다.
한 스레드에서 메모리를 할당받은 뒤 다른 스레드들이 접근하는 데에 문제가 없는지 확인한다.
여러 스레드들이 각자 메모리를 할당 받아도 겹치는 주소에 중복 할당 되지 않고, 동시에 할당 받고 해제해도 문제가 발생하지 않아 test3을 잘 통과한다.
따라서 모든 test들이 정상적으로 통과된 것을 알 수 있다.
thread_exec
스레드에서 exec이 올바르게 동작하는지 평가한다.
만들어지는 스레드 중 하나가 exec으로 hello_thread.c 프로그램을 실행하여 "Hello, thread!"가 출력된다.
exec이 실행되는 순간 다른 스레드들은 모두 종료된다.
thread_exit
스레드에서 exit이 올바르게 동작하는지 평가한다.
하나의 스레드에서 exit이 호출되면 그 프로세스 내의 모든 스레드가 종료되어야 한다.
"Exiting..." 출력 이후 바로 쉘로 잘 빠져나간다.
thraed_kill
프로세스가 kill 되었을 때 그 프로세스 내의 모든 스레드가 올바르게 종료되는지 확인한다.
프로그램이 fork를 통해 두 개의 프로세스로 나누어진 뒤, 각각 5개의 스레드를 생성한다.
그 중 부모 프로세스쪽의 스레드 하나가 자식 프로세스를 kill 한다.
부모 프로세스의 스레드는 kill에 영향을 받지 않고, 자식 프로세스의 스레드들은 모두 즉시 종료된다.
zombie 프로세스 또한 발생하지 않는다.
Lock / Unlock
test function
기존의 pthread_lock_linux.c에 구현되어 있는 test code에서는 race condition이 잘 일어나지 않아 thread_func 함수를 수정하고 test 함수를 추가하였다.
test 함수는 한 스레드가 일 하는 시간을 길게 만들고 결국 매개변수에 1을 더한 값을 리턴하여 thread_func 함수 안에 있는 for loop의 각 iteration마다 shared_resource의 값이 1씩 커진다.
...
int test(int n){
int cnt = 0;
for(int i = 0 ; i < 100 ; i++) cnt += i;
return n + 1;
}
...
void* thread_func(void* arg){
int tid = *(int*)arg;
lock(&s);
for(int i = 0 ; i < NUM_ITERS ; i++){
shared_resource = test(shared_resource);
}
unlock(&s);
pthread_exit(NULL);
}
...NUM_ITERS = 100, NUM_THREADS = 1000으로 바꾸고 테스트를 진행하였다.
lock / unlock을 사용하지 않는 경우
10번 테스트를 진행하였을 때 race condition이 일어나 shared_variable의 최종 값이 계속 변하는 것을 알 수 있다.
lock / unlock을 사용한 경우
10번 테스트를 진행하였을 때 모두 race condition이 일어나지 않았다.
100개의 스레드가 각각 shared_variable을 1000씩 증가시켜서 shared_variable의 값이 100000이 된 것을 알 수 있다.
[Trouble Shooting]
panic: acquire
wakeup1과 wakeup 함수를 혼동해서 사용해 생긴 문제이다.
proc.c를 보면 wakeup에서 lock을 얻고 wakeup1을 호출해 실제로 wakeup1에서 ptable을 순회하며 프로세스들을 RUNNABLE하게 바꾸어준다.
thread_exit 함수를 구현할 때 이미 ptable을 순회하기 위해 lock을 얻은 상태이므로 wakeup이 아닌 wakeup1을 호출해야했는데, wakeup을 호출하여 ptable에 대한 lock을 두 번 얻으려 해서 panic:acquire 문제가 발생하였다.
// inside proc.c thread_exit function
if(curproc->mainFlag == 0){
//wakeup(curproc->main); 을 다음과 같이 수정
wakeup1(curproc0>main);
}
else{
//wakeup(curproc); 을 다음과 같이 수정
wakeup1(curproc);
}panic: remap
panic: remap은 스레드의 스택을 제대로 설정하지 않아 발생한 문제이다.
thread_create에서 다음과 같은 코드를 추가해 같은 프로세스 안에 있는 스레드들의 메모리 크기를 같도록 설정해 주어서 이 문제를 해결하였다.
// inside proc.c thread_create function
struct proc* q;
for(q = ptable.proc ; q < &ptable.proc[NPROC] ; q++){
if(q->pid == p->pid){
q->sz = p->sz;
switchuvm(q);
}
}프로그램이 종료되자마자 쉘이 재부팅 되는 문제
쉘에서 실행 결과는 정상적으로 나오는데 프로그램이 종료되자마자 쉘이 재부팅되는 문제가 발생했다.
여러 원인이 있겠지만 나의 경우에는 스레드가 exit을 호출하면 같은 프로세스 내의 스레드를 모두 종료시켜야 하는데, exit 함수 내에 이 메커니즘을 구현하지 않아서 발생한 문제였다. exit 함수 내에 이 메커니즘을 구현하여 문제를 해결했다.
// inside proc.c exit function
acquire(&ptable.lock);
for(p = ptable.proc ; p < &ptable.proc[NPROC] ; p++){
if(p->pid == curproc->pid && p->tid != curproc->tid){
kfree(p->kstack);
p->kstack = 0;
p->pid = 0;
p->tid = 0;
p->parent = 0;
p->main = 0;
p->name[0] = 0;
p->killed = 0;
p->state = UNUSED;
p->threadFlag = 0;
p->mainFlag = 0;
p->retval = 0;
}
}
release(&ptable.lock);