xv6 MLFQ Scheduling Wiki (3. Trouble Shooting)
여러개의 큐 사이에서 올바르게 process들이 이동하는지 확인하기위해서 아래와 같이 L0 Queue, Sleep Queue, Unused Queue만 구현하고 테스트 해봤습니다.
이 때 Runnable process를 sched 함수에서 L0 Queue로 넣어줬었고 여기서 문제가 발생했습니다.
Sleep Queue와 MLFQ가 아래처럼 같은 프로세스를 보유하고 있었습니다.
기존 구현부에서는 아래처럼 sched(void) 함수에서 runnable 상태의 process를 Queue에 삽입해줬습니다.
yield(void) 이후에만 sched(void) 함수를 호출한다고 생각해서 위와같이 구현했으나, sleep 함수 내부에서도 sched(void) 함수를 호출한다는 것을 알 수 있었습니다.
이렇게 sched(void) 함수에서 현재 프로세스를 L0큐에 넣다보니 sleep 함수에서 Sleeping상태에 들어간 process가 L0로도 들어가는 문제가 발생했으며 이로 인해 큐가 엉키게 되었습니다.
이렇게 insert를 해주는 시점을 yield(void) 함수로 변경을 해주어서 올바른 상태의 프로세스를 큐마다 관리할 수 있게 되었습니다.
void
yield(void)
{
struct proc *p = myproc();
acquire(&ptable.lock);
p->ticks++;
myproc()->state = RUNNABLE;
insert(&mlfq_l0_queue, p, 0);
sched();
release(&ptable.lock);
}
<올바른 결과>
usertests 유저프로그램을 실행 해보는데 아래의 그림처럼 Sleep Queue에 zombie status의 process가 있는 상황이 발생했습니다.
종종 unused 상태가 들어가기도 했는데 이와 관련해서 문제가 예상할 수 있었던 부분은 아래와 같습니다.
- zombie 상태로 만들어주는 함수가 구현이 잘 못되었다.
- zombie 상태를 unused로 바꿔주는 함수의 구현이 잘 못되었다.
- Queue에서 process를 삭제하고 삽입하는 부분에 있어서 구현이 잘 못되었다.
디버깅 결과 sleep→runnable로 바뀌는 process가 MLFQ로 이동할 때 제대로 Sleep Queue와의 연결을 끊지 못한다는 결론을 낼 수 있었습니다.
kill 함수에서 아래의 delete에 해당하는 코드 없이 삽입만 해줘서 Sleep Queue에서 빠지지 못했습니다.
Sleep Queue에서 해당 process의 prev process가 계속해서 해당 process를 next로 잡고있었습니다.
int
kill(int pid)
{
struct proc *p;
acquire(&ptable.lock);
for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
if(p->pid == pid){
p->killed = 1;
// Wake process from sleep if necessary.
if(p->state == SLEEPING) {
p->state = RUNNABLE;
delete(&mlfq.sleep_queue, p);
if(p->queuelevel == 2) {
struct proc *base = higherpriority_proc(p);
insert(&mlfq.l_queue[p->queuelevel], p , base);
} else {
insert(&mlfq.l_queue[p->queuelevel], p, 0);
}
}
release(&ptable.lock);
return 0;
}
}
release(&ptable.lock);
return -1;
}sleep queue에서 빼내야하는 프로세스를 제대로 delete해주고 넣어 줘야하는 큐에 insert 해주니 제대로 동작했습니다.
xv6에서 usertests 유저프로그램을 실행하면서 오류를 맞이했습니다.
allocuvm out of memory 메세지가 나오는 시점에 원인 모를 멈춤 현상이 임의로 발생하였습니다.
발생했던 문제는 아래의 그림과 같이 큐의 count값과 해당 큐에 실제로 존재하는 프로세스의 수가 일치하지 않는 문제였습니다.
이와 관련하여 문제의 원인이라고 가정할 수 있었던 부분은 아래와 같습니다.
- Queue의 insert, delete, dequeue 기능이 잘 못 구현되었을것이다.
- priority boosting 기능이 잘 못 구현되었을것이다.
- wakeup이 올바르게 동작하지 않을 것이다.
- sleep 큐에 존재하고, level2 큐에 해당하는 프로세스를 level2 큐에 insert 하는 부분에서 문제가 있을 것이다.
- 위의 프로세스를 level2 큐에 삽입하기 위해서 해당 프로세스보다 우선순위가 낮은 프로세스를 찾는 higherpriority_proc() 함수를 사용한다. 해당 함수가 잘 못 구현되었을 것이다.
디버깅을 해보며 찾아본 결과 3-a에서 함수가 올바르게 작동하지 않음을 알아낼 수 있었습니다.
원래의 코드는 아래와 같습니다.
static void
wakeup1(void *chan)
{
struct proc *p;
for(p = mlfq.sleep_queue.head; p != 0; p = next) {
if(p->chan == chan) {
delete(&mlfq.sleep_queue, p);
p->state = RUNNABLE;
if(p->queuelevel == 2) {
struct proc *base = higherpriority_proc(p);
// 문제 발생 예상 시점
insert(&mlfq.l_queue[p->queuelevel], p , base);
} else {
// 문제 발생 예상 시점
insert(&mlfq.l_queue[p->queuelevel], p, 0);
}
}
}
}여기서 문제점은 wakeup한 process를 삽입하는 순간 발생합니다.
for문을 순회하며 process를 찾은뒤 해당 프로세스를 올바른 큐에 삽입하게된다면, 해당 프로세스의 next 값은 새롭게 삽입된 큐에서 next로 가리키는 값이 될 것 입니다. 우리의 본래 목적대로라면 for문 안에서 p = p→next를 통해 sleep_queue를 순회해야하는데 아래의 그림처럼 갑자기 목적에 맞지 않는 큐를 순회하게 되는 것 입니다.
<sleep_queue에서 p 프로세스를 찾은 시점, p→next 주목>
<p 프로세스를 L2 Queue의 제 위치에 삽입해준 시점, p→next가 L2 Queue의 프로세스로 변화>
이를 해결하기 위해서 아래처럼 기존 sleep_queue에서 p→next에 해당하던 process를 next라는 임시 프로세스에 할당하고 p의 값에 넘겨줬습니다.
static void
wakeup1(void *chan)
{
struct proc *p, *next = 0;
for(p = mlfq.sleep_queue.head; p != 0; p = next) {
// 임시 변수 next에 p->next값을 넣어주고 p의 값을 갱신
next = p->next;
if(p->chan == chan) {
delete(&mlfq.sleep_queue, p);
p->state = RUNNABLE;
if(p->queuelevel == 2) {
struct proc *base = higherpriority_proc(p);
insert(&mlfq.l_queue[p->queuelevel], p , base);
} else {
insert(&mlfq.l_queue[p->queuelevel], p, 0);
}
}
}
}이렇게 예외적인 부분까지 고려해야하는 코드는 좋지 않다고 생각되어 개선할 예정입니다.