project2_thread_process
Link:
각 쓰레드는 프로세스내에서 별개의 실행 흐름을 가진다. 같은 프로세스에 속한 쓰레드는 유저주소공간, PCB를 공유한다. PCB를 공유함으로써 open file 정보와 signal같은 os자원들을 공유하게 된다. 쓰레드끼리는 메모리 공간의 code, data, heap 영역도 공유한다. 각 쓰레드는 각각의 스택과 TCB를 갖는다.
처음에는 TCB에 해당하는 구조체를 별도로 만든 후, proc 구조체 내부에 TCB 배열로 TCB를 관리하려 했다. 그러나 기존 xv6 코드의 상당 부분이 proc 구조체에 맞추어 설계되었기에, 별도의 TCB 구조체를 도입하면 기존 코드에 대한 이식성이 매우 떨어진다. 특히 스케쥴러에서 TCB를 기준으로 적절한 스케쥴링이 일어나게 하는 것이 쉽지 않다. (스케쥴러에서 ptable을 순회하는 반복문 내에 TCB를 순회하게 하는 방식은 한 프로세스가 CPU를 장기간 독점하게 된다.)
따라서 기존의 proc구조체를 그대로 활용하여 쓰레드를 구현하기로 결정했다. 같은 프로세스내 쓰레드끼리 페이지테이블(pgdir)을 공유하게 하여 쓰레드끼리 유저 주소 공간을 공유한다. 그러나 해당 구현에서는 PCB를 완벽하게 공유하진 않기에 open file에 대한 정보를 완벽하게 공유하진 못한다는 한계점이 있다. (대신 새로운 쓰레드가 생성되면 파일에 대한 레퍼런스 카운트를 1 증가시키는 방식이다.)
struct proc {
uint sz; // Size of process memory (bytes)
pde_t* pgdir; // Page table
char *kstack; // Bottom of kernel stack for this process
enum procstate state; // Process state
int pid; // Process ID
struct proc *parent; // Parent process
struct trapframe *tf; // Trap frame for current syscall
struct context *context; // swtch() here to run process
void *chan; // If non-zero, sleeping on chan
int killed; // If non-zero, have been killed
struct file *ofile[NOFILE]; // Open files
struct inode *cwd; // Current directory
char name[16]; // Process name (debugging)
// project1 mlfq 관련 정보 추가
int priority;
int qlev;
int used_ticks;
// project2 맴버 추가
int mem_limit;
thread_t tid;
struct proc *main;
int is_main;
void *retval;
int already_call_exit; // thread_exit의 재귀 호출을 방지
int n_stackpage;
};pthread_api와 최대한 비슷하게 작동되게끔 thread를 디자인 하고자 했다. 가령 약식 OS인 xv6에서는 쓰레드 id만으로 다른 그룹의 쓰레드, 즉 다른 프로세스가 쓰레드 자원을 회수할 수 있다. 그러나 원칙적으로 pthread에서는 불가하기에 이러한 부분은 pthread를 따르게 했다. 이외에도 pthread와 마찬가지로 한 쓰레드가 exit을 호출하면 프로세스 전체가 종료되게 하였다. (물론 다른 쓰레드가 실행중일 때 exit을 호출하는 건 바람직하지 못하다. 뿐만 아니라 실제 pthread에서는 자원회수를 보장해주지 못한다. )
다른점:
- thread_exit의 경우 pthread와 달리 메인 쓰레드에서 thread_exit을 호출할 경우 프로세스 전체가 종료되게끔 하였다. pthread의 경우 main 쓰레드만 종료되고 서브 쓰레드들은 종료되지 않는다.
- 자식프로세스 회수는 fork한 쓰레드만이 책임지도록 설계했다. 실제 pthread에서는 쓰레드 그룹 내에 속한 쓰레드라면 해당 프로세스의 자식을 회수할 수 있다.
xv6에 맞춘 쓰레드 디자인
xv6 memory layout
위 그림은 xv6 논리주소공간을 나타낸다. user stack과 heap영역이 경계를 맞대고 있는 구조로 일반적인 메모리 레이아웃과는 다르다. 스택은 높은 주소에서 낮은 주소로 grow하고 힙은 그 반대이기에 stack과 heap이 만나는 경우는 존재하지 않는다. 그럼에도 메모리 프로텍션이 존재하지 않는다면 heap은 커널 코드 영역을, stack은 text and data 영역을 침범할 수 있다. 이를 방지하기 위해 exec시에 stack 아래 가드페이지를 할당한다. exec2 시스템콜은 스택의 크기를 늘림으로써 프로세스가 text and data 영역을 침범하지 않고 보다 많은 메모리 공간을 사용할 수 있게 해준다.
해당 메모리 레이아웃 유지한다면, 쓰레드의 유저 스택은 heap영역에 할당되는 것이 자연스럽다. 따라서 메모리 레이아웃 text and data 섹션 바로 위에 메인 쓰레드의 유저 스택이 존재하고, 그 위에 쓰레드의 유저스택과 malloc등을 통해 할당받은 heap 공간이 혼재하게 된다. 쓰레드가 생성되거나 sbrk(양수)나 malloc을 호출하면 프로세스의 논리 주소 공간이 계속 높은 주소 방향으로 증가한다. (즉 sz값이 계속 커진다.)
쓰레드의 스택 사이즈는 한 페이지로 설정했다. 일반적으로 쓰레드는 서브태스크를 수행하기에 많은 양의 스택 공간이 필요하진 않을 것이라고 생각한다. 쓰레드 역시 스택 바로 밑에 가드 페이지를 두어 할당된 스택 외 영역을 침범하지 않도록 하였다.
쓰레드가 종료되면 해당 쓰레드가 차지하고 있던 스택 공간을 사용하지 않으므로 논리 주소공간에 hole이 생기게 된다. 해당 hole을 재활용하는 방안도 고려해보았으나,
- 논리주소공간의 최대 크기는 0x80000000에 해당하는 아주 큰 값이라는 점
- 쓰레드가 논리 주소공간에서 단지 8K만큼만 차지한다는 점. (가드 페이지 포함)
- hole에 해당하는 주소공간을 재활용하면 메모리 레이아웃의 복잡성이 증가한다는 점 이 세가지를 고려하여 hole에 대한 공간은 재활용하지 않기로 하였다. 한 프로세스가 4GB에 해당하는 메모리를 차지하는 경우는 거의 없을 것이기 때문이다. 비록 논리주소공간의 hole은 재사용하지 않지만, deallocuvm을 통해 피지컬 프레임에 대한 메모리 자원은 회수한다.
한가지 tricky한 것은, heap과 쓰레드의 유저 스택을 완벽히 분리할 수 없기에 한 쓰레드가 다른 쓰레드의 스택에 주소를 통해 접근할 수 있다. (p2_test1.c 코드가 이를 보여준다.)
마지막으로 쓰레드와 시스템 콜의 상호작용을 고려할 때 가장 주의해야할 것은 바로 **‘동기화 문제’**이다. 레이스 컨디션에 놓일 수 있는 변수들을 락을 통해 적절히 보호해주어야 한다. 추가로 자원회수에 관해 세심한 주의가 필요하다.
기본적으로 Process manager는 명령어를 사용자로부터 읽어들인 후, 실행한다는 점에서 쉘의 동작 방식과 유사하다. 이는 fork-exec 테크닉을 통해 구현할 수 있다. 명령어가 주어진 형식에 맞게 입력되므로 파싱시에 공백을 기준으로 하드코딩했다. 명령어가 형식에 맞지 않을 경우 Usage error 메시지를 출력하고, 실행 도중 실패했을 경우 해당 명령어와 함께 실패 메시지를 출력한다.
프로세스의 스택 페이지 개수를 정확히 카운팅하기 위해 proc 구조체 내에 n_stackpage라는 별도의 맴버를 추가하였다. n_stackpage는 메인 쓰레드의 스택 페이지 개수 + 서브 쓰레드 스택 페이지 개수의 총합으로 구성된다.
thread_exit 함수는 fork와 exec 코드의 일부분을 차용하여 구현할 수 있다. 다른 쓰레드나 프로세스와의 동기화 문제가 발생할 수 있기에 락을 통해 이 문제를 해결한다. nextpid, nexttid 같은 공유변수는 물론 curproc→main, main→sz 등의 값을 락을 통해 보호해야 한다. (주석에 상세히 기술)
**xv6 첫 프로세스 유저 스택프레임 및 x86 calling convention**
thread를 생성하기 위해서는 쓰레드 스택 프레임을 x86 calling convention맞게 적절하게 구성해야 한다. allocuvm의 리턴값을 이용하여 스택프레임내 각 위치에 매개변수, 리턴 주소를 알맞게 배치한다. 이후 pc와 스택포인터에 대한 정보를 담는 eip, esp 레지스터에 start_routine 주소와 sp를 할당한다.
Issue 섹션에서 후술하겠지만 중간에 락을 해제했다 다시 잡는 과정에 발생가능한 잠재적 위험이 있다. file정보를 복사하는 과정에서 ptable.lock을 잡을 수 없다. xv6에서는 락을 항상 ‘정해진 순서’로 잡아야 데드락이 발생하지 않기 때문이다. 따라서 중간에 ptable.lock을 해제해야 하는데, 이 사이에 현재 쓰레드 그룹(프로세스)가 kill 당하면 embryo상태의 np만 남아버리는 문제가 생길 수 있다.
thread_exit의 경우 exit 코드와 유사하게 구현할 수 있다. 모든 서브 쓰레드의 종료는 반드시 thread_exit을 통해서 이루어지도록 하였다. (쓰레드가 exit을 호출한 경우, kill된 경우 등등) 단 메인 쓰레드가 exit을 호출하는 경우 내부에서 자동으로 exit을 통해 종료되도록 하였다. thread_exit 이후 join을 통해 회수될 수 있게 해야한다. 따라서 wakeup_pid1이라는 pid에 해당하는, 즉 같은 프로세스 그룹에 존재하는 모든 쓰레드를 깨우는 함수를 사용한다. 쓰레드 그룹내 어떤 쓰레드가 join을 호출했는지 알 수 없기 때문이다. (join할 때 타겟 쓰레드를 chan으로 하여 sleep한다면 join중인 쓰레드만 깨울 수 있긴 하다. 그러나 이 방법은 wakeup, retrieve와의 호환성을 고려할 때 부적절할 수 있다.)
thread_join의 경우 wait과 유사하게 구현할 수 있다. ptable을 순회하며 타겟에 해당하는 쓰레드가 존재하는지 찾는다. 만약 타겟이 좀비 상태이면 자원을 회수하고 종료한다. 좀비 상태가 아니라면 sleep 상태로 들어가 타겟 쓰레드가 thread_exit을 호출할 때까지 기다린다.
만약 현재 프로세스가 kill된 상태라면 즉시 함수를 종료한다. 메인쓰레드가 어차피 모든 서브쓰레드의 자원을 회수할 것이기 때문이다.
pthread의 경우 데드락을 감지하거나 자기 자신을 join하려고 하면 에러로 처리한다. 가령 쓰레드1이 쓰레드2를 join하고 쓰레드 2가 쓰레드 1을 join하면 데드락에 빠지게 된다. 데드락에 관한 부분도 구현하고자 했으나, 시간과 능력이 부족하여 구현하진 못했다.
프로세스의 주소공간 복사 및 np의 맴버 변수를 초기화할 때 락만 추가하면 쓰레드와 동기화 문제없이 호환 가능하다.
thread_exit과 exit의 차이는 exit은 프로세스 전체를 종료시키고 thread_exit은 해당 쓰레드만 종료시킨다. 만약 메인 쓰레드가 exit을 호출했다면, kill_and_retrieve_threads 함수를 통해 서브 쓰레드를 전부 kill한 후 종료를 기다렸다가 자원을 회수한다. 즉 프로세스는 exit할 때 항상 모든 서브쓰레드를 정리한 후 종료된다. 만약 서브 쓰레드가 exit을 호출했다면 메인 쓰레드의 kill 플래그를 설정한 후 자기자신은 thread_exit을 호출하여 종료한다.
trap.c에서 쓰레드가 kill된 경우, 메인 쓰레드면 kill, 서브 쓰레드면 thread_exit을 호출하도록 하였다. 이를 통해 kill_and_retrieve_threads에서 kill 플래그를 통해 모든 서브 쓰레드를 회수할 수 있다.
if(tf->trapno == T_SYSCALL){
// 쓰레드의 경우 kill 플래그가 세워지면 thread_exit을 호출하게 수정
if(myproc()->killed)
myproc()->is_main ? exit() : thread_exit(0);
myproc()->tf = tf;
syscall();
if(myproc()->killed) //h 시스템콜 호출됐는데 상태가 killed면 종료
myproc()->is_main ? exit() : thread_exit(0);
return;
}
if(myproc() && myproc()->killed && (tf->cs&3) == DPL_USER)
myproc()->is_main ? exit() : thread_exit(0);ptable을 순회하며 pid에 해당하는 ‘메인 쓰레드’만 killed 플래그 값을 1로 변경한다. 이후 메인 쓰레드가 exit을 호출하면 자연스레 서브쓰레드도 정리되고 전체 프로세스가 종료된다.
exec를 호출한 쓰레드 외에 다른 쓰레드는 모두 정리되어야 한다. 따라서 exec를 호출한 쓰레드가 서브 쓰레드라면 해당 쓰레드를 새로운 메인 쓰레드로 변경한다. 이후 자원회수를 2단계로 나누어 진행한다. 1. old_main을 기준으로 서브 쓰레드를 전부 회수한다. 2. 남아있는 old_main을 현재 쓰레드가 회수한다. exec를 호출한 쓰레드가 메인 쓰레드라면 별도의 작업없이 바로 kill_and_retrieve_threads 함수를 호출하여 서브 쓰레드들을 정리한다.
if (!curproc->is_main)
{
old_main = change_main_thread(curproc, curproc->main);
kill_and_retrieve_threads(old_main);
kill_old_main_and_retrieve(curproc, old_main);
// 쓰레드 그룹이 완전히 변경된 후 tid와 main 변수 변경
// 해당 정보를 마지막에 초기화 해야 join과 호환 가능.
curproc->tid = 0;
curproc->main = curproc;
}
else
kill_and_retrieve_threads(curproc);exec를 하는 시점에 proc 구조체의 n_stackpage 변수 값을 조정한다.
proc 구조체를 이용하여 쓰레드를 구현했기에 자연스럽게 쓰레드와 호환가능하다. 쓰레드가 sleep 상태에서 프로세스가 kill 될 경우 메인 쓰레드가 모든 서브쓰레드를 kill하고 자원을 회수한다. 따라서 쓰레드가 sleep 상태일지라도 kill에 의해 종료될 수 있다.
int
sys_sbrk(void)
{
int addr;
int n;
if(argint(0, &n) < 0)
return -1;
// 락을 걸어서 페이지 테이블에 대한 레이스 컨디션 방지
acquire(&ptable.lock);
// sbrk 리턴값은 이전 메모리 사이즈 (top of heap)
addr = myproc()->main->sz;
if(growproc(n) < 0)
{
release(&ptable.lock);
return -1;
}
release(&ptable.lock);
return addr;
}sbrk는 논리주소공간의 heap영역을 할당한다. 따라서 당연히 모든 쓰레드가 해당 메모리 공간을 공유할 수 있다. 여러 쓰레드가 메모리 할당 요구를 경쟁하는 상황이 존재할 수 있으므로 해당 영역을 위와 같이 락을 통해 보호한다. 전체 주소공간에 대한 관리는 메인쓰레드의 PCB가 담당하도록 한다. 프로세스에서 사용중인 주소공간 사이즈가 바뀔 때마다 전체 쓰레드의 sz값도 업데이트 해주는 것은 오버헤드가 크다. 따라서 쓰레드의 sz값은 처음 생성하는 시점에만 초기화한 후 업데이트 하지 않는다.
wait에서는 반드시 메인 쓰레드만 회수되도록 해야한다. 서브 쓰레드가 wait에 의해 회수되면 예기치 않은 결과를 야기할 수 있다. 특히 자원이 이중으로 회수되지 않도록 주의해야 한다.
// wait을 통해 자원을 회수할 때 메인 쓰레드인지 반드시 확인한다.
if(p->state == ZOMBIE && p->is_main)
{
// Found one.
pid = p->pid;
clean_proc_slot(p, PROC);
freevm(p->pgdir);
release(&ptable.lock);
return pid;
}파이프는 파일 인터페이스를 이용한다. 따라서 pcb에 존재하는 파일에 관한 정보를 쓰레드에 옮겨주기만 한다면 쓰레드와 문제 없이 호환된다.
기존 exec 시스템콜을 이용하여 구현할 수 있다. 인자가 범위를 벗어나는 경우 예외처리를 해두었다.
//h 스택 개수만큼 할당하도록 변경
// Allocate two pages at the next page boundary.
// Make the first inaccessible. Use the second as the user stack.
sz = PGROUNDUP(sz);
if((sz = allocuvm(pgdir, sz, sz + (stacksize + 1) * PGSIZE)) == 0)
goto bad;
clearpteu(pgdir, (char*)(sz - (stacksize + 1) *PGSIZE));
curproc->n_stackpage = stacksize;
sp = sz;앞서 서술한대로 전체 주소공간에 대한 관리는 메인쓰레드가 책임진다. 따라서 서브 쓰레드에서의 sz과 mem_limit값은 의미있는 값이 아니다. 그렇기에 해당 함수가 호출되면 메인 쓰레드의 mem_limit값만 업데이트 해준다.
// 입력이 '형식'에 정확히 들어맞을 때만 명령어를 실행한다
// 형식: '명령어 옵션1 옵션2개행'
// 명령어, 옵션 앞 뒤의 추가적인 공백이 존재하면 명령어는 실행되지 않는다.
int
runcmd(char *buf)
{
// 함수 포인터 배열
t_exec_cmd exec_cmd[] = {
pm_list,
pm_kill,
pm_execute,
pm_memlim,
pm_exit
};
char cmd[128];
int i;
int cmd_type;
i = 0;
while (buf[i] != 0 && buf[i] != ' ' && buf[i] != '\n')
{
cmd[i] = buf[i];
i++;
}
cmd[i] = '\0';
cmd_type = mapcmd(cmd);
// 개행만 입력된 경우 아무 메시지를 출력하지 않도록 함.
// 대신 eof가 들어오는 경우 메시지 출력
if (cmd_type == NONE)
return (i != 0);
return (exec_cmd[cmd_type](buf, i));
}함수포인터 배열을 통해 명령어에 해당하는 함수를 실행한다. 이후 명령어의 형식에 따라 인풋을 파싱하여 결과가 올바른지 확인한다. sh.c과 같은 방식으로 명령어를 백그라운드에서 실행하기 위해 fork를 두번 한다. 이후 init 프로세스가 백그라운드에서 실행중인 프로세스의 부모가 되어 자식 프로세스에 대한 자원 회수를 책임진다.
기본적으로 주어진 테스트 코드는 전부 성공적으로 실행된다. 그 외 테스트 코드는 전부 p2 접두사를 붙여 사용했다.
p2_script.c 파일에서 fork와 exec를 이용해 원하는 테스트를 반복적으로 실행할 수 있다. 동기화 문제의 경우 에러의 재현이 쉽지 않으므로, 코드를 반복적으로 실행하여 디버깅을 진행했다.
// exec에 원하는 실행파일을 넣어 반복적으로 실행하는 테스트.
int
main(int argc, char *argv[])
{
void (*test[])(void) = {do_test0, do_test1, do_test2, do_test3};
int start;
int end;
start = 0;
end = sizeof(test) / sizeof(void (*)(void)) - 1;
if (argc > 1)
start = atoi(argv[1]);
if (argc > 2)
end = atoi(argv[2]);
while (1)
{
for (int i = start; i <= end; i++)
{
printf(1, "Test %d start\n", i);
test[i]();
printf(1, "Test %d end\n\n\n", i);
}
}
exit();
}p2_fork_nowait은 쓰레드에서 fork후 자식을 회수하지 않을 때, init 프로세스에 의해 정상적으로 회수되는지 검사하는 코드이다.
코드 실행 후 좀비 프로세스가 존재하지 않고 자원이 정상적으로 회수 됐음을 확인할 수 있다.
p2_main_exec는 메인 쓰레드에서 exec가 정상적으로 수행되는지를 테스트 하는 코드이다.
p2_th_call_join은 서브쓰레드에서도 join이 정상적으로 동작하는지 테스트 하는 코드이다. 서브쓰레드에서 이미 회수한 자원은 메인 쓰레드에서 회수되지 않는 것을 확인할 수 있다.
p2_join_exit은 join과 exit의 상호작용을 테스트하는 코드로 sleep의 인자값을 달리주어 두 시스템 콜이 잘 상호작용하는지 확인할 수 있었다.
p2_fork_sbrk는 fork와 sbrk의 상호작용을 테스트 하는 코드로 정상 작동함을 확인할 수 있다.
p2_test1은 쓰레드 간에 주소 공간이 제대로 공유되는지 확인하는 테스트 코드이다.
pmanager 동작 테스트
참고: xv6에서는 free 이후에도 해당 메모리 공간에 접근할 수 있다.
즉 free가 동기화 문제에 영향을 주진 않는다. (실제 OS에서는 접근하면 안되는 것이 원칙이다.)
pthread처럼 쓰레드가 thread_exit을 명시적으로 호출하지 않아도 암시적으로 호출되게끔 하려고 했었다. 이에 쓰레드의 리턴주소에 fake address대신 thread_exit 래퍼함수의 주소를 추가하는 시도를 했다. 그러나 해당 주소는 커널 코드 영역에 해당하기에 애초에 유저 영역에서 실행할 수 없다. 따라서 thread_exit을 암시적으로 호출되게 하기는 어렵다. 모든 쓰레드는 반드시 thread_exit 혹은 exit을 명시적으로 호출해야 한다.
동기화 문제로 인한 오류는 재현이 쉽지 않기에 디버깅을 하는데 꽤 애를 먹었다. trap, panic, 커널 재부팅 등 이슈를 겪었고, 대부분의 경우 레이스 컨디션에 기인한 문제였다. 락을 적절히 활용하여 변수를 보호함으로써 해당 문제를 해결할 수 있었다.
자원회수와 관련해서 커널 코드를 건드리거나 이중으로 회수하면 커널이 재부팅되는 이슈가 있었다. 그렇기에 wait에서 메인 쓰레드의 자원만 회수하게 함으로써 자원 이중회수를 방지했다. 또 exec에서 메인 쓰레드를 교체할 때, old_main→main 과 curproc→tid, curproc→main은 자원회수가 모두 완료한 후에 변경하여 이중회수를 방지했다.
쓰레드-시스템콜, 시스템콜-시스템콜 간의 상호작용과 관련한 다양한 케이스를 모두 고려하는 것이 쉽지 않았다. 예를 들어 1번 쓰레드1, 쓰레드2, 메인 쓰레드가 동시에 exit을 호출하는 상황 2번. 쓰레드1은 join, 쓰레드 2는 exit, 메인 쓰레드는 exit을 호출하는 상황 3번 쓰레드1은 join, 쓰레드2는 exit, 프로세스가 kill 된 상황 4번 kill 과 exit이 동시에 호출되는 상황 이외에도 정말 다양한 케이스가 존재한다. 쓰레드는 반드시 thread_exit을 통해 종료된다는 원칙을 토대로 자원 회수에 유의하여 각 상호작용을 안전하게 구현할 수 있었다.
100번 실행했을 때 1번 정도의 비율로 sbrk_test에서 trap 14 에러가 발생했다. 이는 쓰레드를 생성할 때 sz값이 page aligned 상태가 아닐 때 발생하는 문제였다. eip 주소 및 addr2line 명령어, gdb, err 코드 등을 활용하여 문제를 해결할 수 있었다. trap이 발생하는 시점에 쓰레드간의 sp값이 불연속적었고, 쓰레드가 생성되자마자 arg를 fetch하는 과정에서 trap이 발생함을 확인했다. 따라서 쓰레드의 스택을 할당받기 전에 sz값을 PGROUNDUO 매크로 함수를 통해 page aligned 상태로 변경했다.
Test 3: Sbrk test
sp: 0x5ff8
sp: 0x7ff8
sp: 0x9ff8
Thread 0 start
Thread 1 start
sp: 0x1c000
sp: 0x1e000
Thread 2 start
pid 6 tid 3 thread_test: trap 14 err 7 on cpu 0 eip 0x106 addr 0x1a000--kill proc
pid 6 tid 4 thread_test: trap 14 err 5 on cpu 0 eip 0xb9 addr 0x1c004--kill proc
Thread 4 start
pid 6 tid 5 thread_test: trap 14 err 7 on cpu 0 eip 0x106 addr 0x1a000--kill proc
pid 6 tid 1 thread_test: trap 14 err 7 on cpu 0 eip 0x150 addr 0x1a000--kill proc
Thread 2 returned 0, but expected 2
Test failed!
Test 3 end
Test 3 start
Test 3: Sbrk test
sp: 0x5ff8
sp: 0x7ff8
sp: 0x9ff8
sp: 0xbff8
sp: 0xdff8
Thread 0 start
Thread 1 start
Thread 2 start
Thread 3 sThread 4 start
tart
Test 3 passed
All tests passed!
Test 3 end아래 케이스의 경우 쓰레드 스택 sp가 page aligned이기 때문에 trap이 발생하지 않지만 위의 케이스의 경우 page aligned가 아니기에 trap이 발생하는 것을 확인할 수 있다. eip 0xb9는 쓰레드의 시작을 나타낸다.
addr2line 명령어를 통해 eip 주소에 대응되는 코드 라인 번호를 찾을 수 있다.
페이지폴트 에러비트
sbrk 테스트에서 정말 낮은 확률로 무한루프에 빠지는 현상이 존재했다. (테스트코드의 sleep 인자 및 쓰레드 개수에 따라 발생률이 달라진다. 기존 코드에서는 발생하지 않는다고 봐도 무방하다.) 이는 메인 쓰레드가 join을 통해 서브 쓰레드를 기다리고, 서브 쓰레드는 while (ptr == 0) 반복문을 탈출하지 못하는 경우 프로세스가 영원히 종료되지 않는다. 이는 스케쥴링 상황에 따라 정말 낮은 확률로 발생한다. 처음에는 원인을 분석하지 못했는데 procdump의 backtrace 정보 및 gdb를 활용하여 어떤 상황인지 파악할 수 있었다.
상단 sleep 트레이스 정보를 통해서 join에서 sleep을 호출했음을 확인할 수 있다
gdb에서 주소를 통해 symbol을 확인
sbrk test에서 정말 낮은 확률로 (대략 2000~3000번 중 1번) 하단 코드 부분에서 여러 쓰레드가 메모리 공간을 동시에 요청할 때, 같은 주소를 할당 받는 현상을 확인했다.
for (i = 0; i < 2000; i++) {
int *p = (int *)malloc(65536);
if (p == 0)
printf(1, "Thread: %d tid: %d malloc failed!", val, get_tid());
ptr_arr[val] = (int)p;
for (j = 0; j < 16384; j++)
p[j] = val; //h eip 0x160, 0x158
// 메모리 영역을 겹쳐서 할당받는게 문제인듯.
for (j = 0; j < 16384; j++) {
if (p[j] != val) {
printf(1, "Thread %d tid: %d found %d, p_addr: 0x%x, j: %d\n\n", val, get_tid(), p[j], p, j);
for (int i = 0; i < NUM_THREAD; i++)
printf(1, "Thread %d p_addr: 0x%x\n", i, ptr_arr[i]);
// printf(1, "Thread %d tid: %d found %d, j: %d\n", val, get_tid(), p[j], j);
failed();
}
}
free(p);
}해당 부분은 xv6에서 malloc이 thread safe하지 않기 때문에 발생한 문제로 파악된다. (즉 쓰레드 코드에는 이상이 없다.) malloc은 주소 공간 중 빈 영역을 요청한 쓰레드에게 할당한다. 문제는 malloc 내부에서 사용가능한 메모리를 찾아서 반환하는 과정에서 별도의 락이 존재하지 않는다. 따라서 sbrk를 락으로 보호할지라도 malloc이 thread safe하지 않기에 같은 스케쥴링에 따라 여러 쓰레드가 같은 메모리 주소 공간을 할당받을 수 있다. 기존 xv6에는 쓰레드 기능이 없기에 malloc을 thread safe하지 않게 구현한 것으로 보인다. (프로세스마다 별개의 주소공간을 가지므로 malloc은 process safe하다.)
void*
malloc(uint nbytes)
{
Header *p, *prevp;
uint nunits;
nunits = (nbytes + sizeof(Header) - 1)/sizeof(Header) + 1;
if((prevp = freep) == 0){
base.s.ptr = freep = prevp = &base;
base.s.size = 0;
}
for(p = prevp->s.ptr; ; prevp = p, p = p->s.ptr){
if(p->s.size >= nunits){
if(p->s.size == nunits)
prevp->s.ptr = p->s.ptr;
else {
p->s.size -= nunits;
p += p->s.size;
p->s.size = nunits;
}
freep = prevp;
// 힙에 빈 공간 있으면 sbrk호출 없이 바로 할당한다..
// 대개의 경우 아래 if문으로 진입하지 않음.
// 이 라인 때문에 같은 주소공간 할당받아서 생기는 문제.
return (void*)(p + 1);
}
if(p == freep)
if((p = morecore(nunits)) == 0) // sbrk를 호출하는 부분
return 0;
}
}Test 3 start
Test 3: Sbrk test
Thread 31 tid: 82 found 32, p_addr: 0x268108, j: 14508
Thread 0 p_addr: 0x68008
Thread 1 p_addr: 0x338170
Thread 2 p_addr: 0x88018
Thread 3 p_addr: 0x68008
Thread 4 p_addr: 0x2480F8
...
Thread 31 p_addr: 0x268108
Thread 32 p_addr: 0x268108
Thread 33 p_addr: 0x278110
...
Test failed!
Test 3 end(Thread 31과 32가 같은 주소 공간을 할당받은 모습이다.)
해당 이슈가 실존하는지는 확인하지 못했지만, 잠재적으로 발생 가능해보인다. 실제로 코드를 몇시간 넘게 반복 실행해도 발견되진 않았다.
thread_create와 fork에서 파일시스템 정보를 복사하기 위해 락을 잠시 푼다. 이후 np를 runnable로 바꾸는 시점에 락을 다시 사용한다. 이때 락을 잠시 푼 사이에 프로세스가 종료된다면 np가 embryo 상태로 남은 채 회수되지 않는 문제가 있을 수 있다. 앞서 서술한 대로 xv6는 항상 락을 정해진 순서대로 잡아야 하기에 file 관련 처리를 할 때, 다른 락을 함부로 잡을 수 없다. (이는 xv6 공식 문서에 명시돼 있는 내용이다.)
고아가 된 embryo에 대한 자원 회수를 고민해보았지만 이를 회수할 마땅한 방법이 생각나지 않았다. wait에서 embryo를 회수하게 하면 fork가 동작하지 않을 수 있다. 게다가 파일시스템 정보를 복사하는 시점에서 락을 걸어두지 않는다. 따라서 np의 파일시스템에 관한 자원을 회수할 때, 어디까지 파일시스템 자원이 복사됐는지 알 수 없으므로 정확한 회수가 불가능하다. (존재하지 않는 자원을 회수하려고 하면 에러를 야기할 수 있기 때문이다.) 따라서 현재 구현에서는 해당 부분에 대한 처리를 하지 않았다.
이번 과제의 경우 디버깅이 상당히 쉽지 않았다. 동기화 문제의 경우 특정 조건에서만 발생하기에 에러의 재현이 쉽지 않기 때문이다. 그럼에도 많은걸 배울 수 있는 과제였다고 생각한다. 스택프레임, 가상주소, 동기화, 락킹, sleep 락 방식, 스케쥴링, 자원회수과정 등등 직접 코드를 통해 구현하며 익힐 수 있었다. 직접 쓰레드를 구현해봄으로써 왜 pthread API를 메뉴얼에 적힌 사용법을 준수해야하는지 깨달을 수 있었다. 부가적으로 gdb및 주소값과 스택 backtrace를 통한 디버깅 스킬을 배울 수 있었다.