xv6 MLFQ Scheduling Wiki (1. 과제 구현)
자료구조 선언부
과제 구현부를 설명하기에 앞서서 MLFQ Scheduling을 위해서 추가한 자료 구조들을 먼저 살펴보고, 해당 자료구조를 택한 이유는 구현부에 대한 이야기를 하며 추가로 설명하겠습니다.
이번 과제를 구현하면서 중점적으로 생각한 부분은 시간복잡도입니다.
[#부록][1. State transition] 에서 살펴볼 수 있듯이 기존의 코드에서는 ptable을 순회하며 O(N) 혹은 O(NPROC)의 시간복잡도를 갖는 함수가 많이 있습니다.
시스템 코드에서 이러한 부분이 반복적으로 실행된다면 성능상의 문제를 야기할 수 있다고 생각되어 효율적인 구조를 구현하기 위해서 노력했습니다.
Queue
typedef struct {
struct proc *head;
struct proc *tail;
} queue;MLFQ
struct mlfq {
int global_ticks;
struct proc *lockproc;
struct proc *unlockproc;
queue l_queue[NQUEUE]; // mlfq multilevel queue
queue sleep_queue; // mlfq sleep queue
queue unused_queue; // mlfq unused queue
};Proc
struct proc {
...
//added
int priority; // initial value 3
int queuelevel; // initial value 0
int ticks; // upto l0: 4ticks, l1: 6ticks, l2: 8ticks
struct proc *next; // initial value NULL(0)
struct proc *prev; // inital value NULL(0)
};Unused Queue, Sleep Queue
위의 자료구조중 MLFQ에 존재하는 sleep_queue와 unused_queue에 대해 먼저 살펴보겠습니다.
기존의 코드에서는 UNUSED 상태와 SLEEPING 상태의 프로세스를 찾기 위해서 Ptable.proc 전체를 순회하고 있습니다. O(N)의 시간복잡도를 갖는 이러한 비효율적인 부분을 개선하기 위해서 해당 자료구조를 추가했습니다.
자료구조를 추가함으로서 process를 할당하기 위해서 UNUSED 상태의 프로세스를 찾을 때 아래의 그림과 같이 unused_queue에서 dequeue를 통해 O(1)만에 프로세스를 가져올 수 있습니다.
또한 SLEEPING 상태중에 channel에 맞는 프로세스를 찾기 위해서는 아래의 그림과 같이 sleep_queue를 순회하다가 channel에 맞는 프로세스를 찾으면 되기 때문에 O(k)만에 프로세스를 가져올 수 있습니다. (k: sleeping 상태의 프로세스 수)
Unused Queue, Sleep Queue 사용에 따른 효율성 증가
| 함수 | 개선된 시간복잡도 | 기존 시간복잡도 |
|---|---|---|
| allocproc | O(1) | O(N) |
| wakeup1 | O(k), k: sleeping 상태의 프로세스 수 | O(N) |
head, tail을 갖고있는 MLFQ
MLFQ는 과제에 명시된대로 L0 ~ L2까지 큐를 구현하였습니다. (자세한 자료구조는 [1 - 1. 자료구조] 와 아래의 그림을 함께 참고하시면 됩니다)
Queue마다 head와 tail을 보유하도록 구현한 이유는 priority boosting을 효율적으로 진행하기 위함입니다.
priority boosting시에는 L0 Queue의 끝에 L1 Queue를 연결하고, 뒤이어 L2 Queue를 연결합니다.
위와 같은 작업을 하기 위해서는 L0의 마지막 process, L1의 마지막 process를 각각 알아야합니다.
head만 존재하는 linked list에서는 O(N)만큼의 시간을 요구하기에 tail을 만들어서 O(1)만큼 시간을 단축했습니다.
MLFQ 동작 방식
아래의 코드와 함께 MLFQ의 동작 방식을 살펴보겠습니다.
우리는 timer interrupt가 발생하면 현재 Running중이던 process를 Runnable로 바꾸고, 새로 Running상태로 바꿔줄 프로세스를 찾아야합니다. 또한 각 큐마다 제한된 time quantum과 process들이 소비한 시간인 (ticks)가 같아지면 해당 process를 다음 큐로 내려줘야합니다. 이를 구현하기 위해 아래의 방식으로 함수가 진행됩니다.
yield 함수가 호출되면 먼저 현재 실행중이던 process의 tick을 1 올려줍니다.
(yield에서만 tick을 올려주고 sleep 상태에 빠졌을 때나 다른 상태에서 tick을 올려주지 않는 이유는 사용자와의 interaction이 있을 때 흘러간 1tick만큼의 시간만 의미가 있다고 생각했기 때문입니다.)
그리고 현재 실행중이던 process의ticks이 time quantum과 같아졌는지 먼저 확인합니다.
time quantum과 같은 경우 priority와 queue level 조정을 해줍니다.
그리고 해당 process가 들어가야하는 큐가 L1 또는 L2라면 해당 큐의 맨 뒤로 process를 insert 해주게 됩니다.
void
yield(void)
{
struct proc *p = myproc();
acquire(&ptable.lock); //DOC: yieldlock
p->ticks++;
mlfq.global_ticks++;
myproc()->state = RUNNABLE;
if { ... }
...
else {
// process timequantum check
if(p->ticks == p->queuelevel*2 + 4) {
p->ticks = 0;
if(p->queuelevel == 2) {
p->priority = p->priority == 0 ? 0 : p->priority - 1;
}
p->queuelevel = p->queuelevel == 0 ? 1 : 2;
}
// process insertion
if(p->queuelevel != 2) {
insert(&mlfq.l_queue[p->queuelevel], p, 0);
}
else {
// insert p before higher priority at L2
struct proc *base = higherpriority_proc(p);
insert(&mlfq.l_queue[p->queuelevel], p , base);
}
}
sched();
release(&ptable.lock);
}만일 process가 들어가야하는 큐가 L2라면 process들의 priority를 고려하여 순서에 맞게 큐에 넣어줘야합니다. 우리는 아래의 higherpriority_proc 함수를 통해서 현재 process보다 priority가 낮은(값은 높은) process를 찾습니다.
더 자세히 보자면 l_queue[2]에 있는 프로세스들의 priority를 비교하며 현재 실행중이던 프로세스보다 priority가 큰 프로세스를 찾고 반환합니다.
리턴된 프로세스 base의 앞에 p를 insert 해주어서 L2큐의 process 순서를 정렬해줍니다.
// get process that have higher priority than p
struct proc*
higherpriority_proc(struct proc *p) {
struct proc *tmp;
for(tmp = mlfq.l_queue[2].head; tmp != 0; tmp = tmp->next) {
if(tmp->priority > p->priority)
return tmp;
}
return 0;
}Scheduler 동작 방식
이번에는 아래의 scheduler 함수를 살펴보며 Running 상태로 바꿔줄 process를 찾는 과정을 살펴봅시다.
우리의 L0, L1, L2 큐에는 우리의 설계에 따라 오로지 Runnable 상태의 process만 존재합니다.
(다른 이야기지만 혹시나 Zombie 상태의 process가 존재하지는 않는지 의문이 들 수 있겠지만 해당 상태로 process가 변하게 된다면 어느 큐에도 넣어주지 않습니다. 그대신 wait 함수에서 ptable을 순회하며 Zombie 상태의 process를 unused로 바꿔주게됩니다.)
그렇기 때문에 L1큐부터 순차적으로 각 레벨 큐에 process가 있는지 판단하고 있다면 dequeue를, 없다면 다음 큐로 넘어가서 dequeue를 해주는 작업을 해주면 됩니다.
else 구문을 통해서 모두 process가 없는 경우에 lock을 release해주어 sched 함수 호출을 통해 runnable한 process가 큐에 존재할 수 있도록 여지를 만들어줍니다.
void
scheduler(void)
{
for(;;){
...
// Loop over process table looking for process to run.
acquire(&ptable.lock);
if(!queue_is_empty(&mlfq.l_queue[0])) {
p = dequeue(&mlfq.l_queue[0]);
} else if(!queue_is_empty(&mlfq.l_queue[1])) {
p = dequeue(&mlfq.l_queue[1]);
} else if(!queue_is_empty(&mlfq.l_queue[2])){
p = dequeue(&mlfq.l_queue[2]);
} else {
release(&ptable.lock);
continue;
}
// Switch to chosen process. It is the process's job
// to release ptable.lock and then reacquire it
// before jumping back to us.
c->proc = p;
switchuvm(p);
p->state = RUNNING;
swtch(&(c->scheduler), p->context);
switchkvm();
...
release(&ptable.lock);
}
}process들의 state에 따른 Queue 분리로 인한 효율성 증가
이로 인해서 우리는 기존에 ptable을 순회하며 O(N)동안 RUNNABLE 프로세스를 찾던 과정을 O(1)로 줄이게 되었습니다.
| 함수 | 개선된 시간복잡도 | 기존 시간복잡도 |
|---|---|---|
| scheduler | O(1) | O(N) |
priority boosting 구현부
아래의 그림과 코드를 통해 priority 구현부를 살펴봅시다.
우리는 [1 - 2. MLFQ 구현부] 에서 Queue의 구조를 설계할 때 priority boosting을 고려하여 head와 tail을 만들었다고 얘기했었습니다.
아래의 그림과 같이 L0 큐의 끝에 L1큐를, L1큐의 끝에 L2큐를 연결하고, L0큐로 올라온 모든 프로세스들의 priority, ticks, queuelevel을 초기화해줍니다.
세개의 큐를 연결할시에는 L0, L1, L2 큐가 각각 임의로 비어있는 경우가 있을 수 있기 때문에 이에따른 분기처리를 해줘야하고 merge_queue 함수에서 이를 구현해줬습니다.
queue*
merge_queue(queue *q1, queue *q2) {
if(!queue_is_empty(q1)) {
if(!queue_is_empty(q2)) {
q1->tail->next = q2->head;
q2->head->prev = q1->tail;
q1->tail = q2->tail;
q2->head = 0;
q2->tail = 0;
q1->count = q1->count + q2->count;
q2->count = 0;
}
return q1;
} else {
q1->head = q2->head;
q1->tail = q2->tail;
q1->count = q2->count;
q2->count = 0;
return q2;
}
}
void
priority_boosting()
{
// move concat l0, l1, l2
merge_queue(&mlfq.l_queue[1], &mlfq.l_queue[2]);
merge_queue(&mlfq.l_queue[0], &mlfq.l_queue[1]);
// set sleep queue process queuelevel 0
for(struct proc *p = mlfq.sleep_queue.head; p != 0; p = p->next) {
p->queuelevel = 0;
p->priority = 3;
p->ticks = 0;
}
// set all queue process priority, ticks default
for(struct proc *p = mlfq.l_queue[0].head; p != 0; p = p->next) {
p->queuelevel = 0;
p->priority = 3;
p->ticks = 0;
}
}priority boosting을 해주는 시점을 scheduler의 swtch(&(c→scheduler), p→context)의 아랫부분이 실행되는 부분으로 잡았습니다.
이 시점에는 Running 상태의 process가 없고, 이 시점이 지나고 for문의 초반으로 돌아간 뒤에 Runnable한 process를 찾기 때문에 모든 process들을 boosting하기에 적합한 시간이라고 판단했습니다.
void
scheduler(void)
{
struct proc *p;
struct cpu *c = mycpu();
c->proc = 0;
for(;;){
...
c->proc = p;
switchuvm(p);
p->state = RUNNING;
swtch(&(c->scheduler), p->context);
switchkvm();
// Process is done running for now.
// It should have changed its p->state before coming back.
if(mlfq.global_ticks == 100) {
mlfq.global_ticks = 0;
priority_boosting();
// change queuelevel of process that held lock
c->proc->queuelevel = 0;
// release lock
releasemlfq();
}
c->proc = 0;
release(&ptable.lock);
}
}setPriority
setPriority 과정에서 L2에 있는 프로세스의 priority를 변경하게 되는 경우 순서를 재정렬 해줘야합니다.
이 과정에서 아래의 (higherpriority_proc, setPriority_arrangeQueue) 두 함수들을 사용하게 됩니다.
// get process that have higher priority than p
struct proc*
higherpriority_proc(struct proc *p) {
struct proc *tmp;
for(tmp = mlfq.l_queue[2].head; tmp != 0; tmp = tmp->next) {
if(tmp->priority > p->priority)
return tmp;
}
return 0;
}
// helper function for sys_setPriority
void setPrioity_arrangeQueue(int pid, int priority)
{
struct proc *p = 0;
acquire(&ptable.lock);
for(struct proc *tmp = ptable.proc; tmp < &ptable.proc[NPROC]; tmp++) {
if(tmp->pid == pid) {
p = tmp;
}
}
// 예외처리
if(p != 0 && p->state != UNUSED) {
p->priority = priority;
if(p->queuelevel == 2 && p->state == RUNNABLE) {
struct proc *base = higherpriority_proc(p);
delete(&mlfq.l_queue[2], p);
insert(&mlfq.l_queue[2], p, base);
}
}재정렬 하는 과정에서 priority를 변경한 process를 L2에서 빼내야하는데 그렇게 하기 위해서는 해당 프로세스의 이전과 다음 프로세스를 알아야합니다.
만약 단일 linkedlist로 구현이 되어있다면 이 과정이 O(N)만큼 시간이 들기 때문에 O(1)만큼 시간을 줄이기 위해서 위의 [1 - 1. 자료구조] 에서 볼 수 있듯이 doubly linked list로 구현했습니다.
setPriority 예외처리
위의 코드에서 볼 수 있듯이 pid가 0인 경우 unused process의 priority를 바꾸려는 무의미한 처리이므로 예외처리하였습니다.
또한 ptable을 순회하면서 pid에 맞는 process가 없는 경우 아무 작업도 하면 안되기 때문에 예외처리를 했습니다.
SchedulerLock, SchedulerUnlock 구현부
그림, 코드, [1 - 1. 자료구조] 를 함께 살펴보며 SchedulerLock과 SchedulerUnlock에 대해서 알아봅시다.
특정 process에서 SchedulerLock이 올바른 암호와 함께 호출된다면 그 process가 cpu를 독점하게 됩니다.
제 코드상에서 scheduler는 L0큐부터 dequeue하기 때문에 SchedulerLock을 잡은 프로세스가 yield에 의해 Queue로 돌아갈 때 아래 그림처럼 무조건 L0큐의 맨앞으로 돌아갈 수 있도록 구현했습니다.
아래의 코드를 살펴보면 lock을 하기 위해서는 mlfq.lockproc = myproc()을 하고,
unlock을 하기 위해서는 mlfq.lockproc = 0, mlfq.unlockproc = p를 해줍니다. 또한 unlock한 process를 초기화해줬습니다.
mlfq.unlockproc을 만들어준 이유는 그 아래 yield 코드를 살펴보며 이야기해보겠습니다.
// schedulerLock
void
schedulerLock(int password)
{
struct proc *p = myproc();
if(password != 2017029416) {
cprintf("현재 프로세스 pid: %d, time quantum: %d, queuelevel: %d\n", p->pid, p->ticks, p->queuelevel);
exit();
} else {
acquire(&ptable.lock);
mlfqlock();
release(&ptable.lock);
}
}
// helper function for sys_schedulerLock: hold mlfq lock
void
mlfqlock() {
struct proc *p = myproc();
if(mlfq.lockproc == 0) {
mlfq.lockproc = p;
mlfq.global_ticks = 0;
}
}
// schedulerUnlock
void
schedulerUnlock(int password)
{
struct proc *p = myproc();
if(password != 2017029416) {
cprintf("현재 프로세스 pid: %d, time quantum: %d, queuelevel: %d\n", p->pid, p->ticks, p->queuelevel);
exit();
} else {
acquire(&ptable.lock);
mlfqunlock();
release(&ptable.lock);
}
}
// helper function for sys_schedulerUnlock: release mlfq lock
void
mlfqunlock() {
struct proc *p = myproc();
if(mlfq.lockproc != 0) {
mlfq.lockproc = 0;
mlfq.unlockproc = p;
p->queuelevel = 0;
p->priority = 3;
p->ticks = 0;
}
}우리는 unlock한 프로세스를 L0 큐의 맨 앞에 위치시켜줘야합니다.
그렇게 하기위해서 기존에 lock을 했을 때 L0 큐의 맨 앞으로 process를 넣어주는 코드를 작성했던 위치에 unlock하는 경우에도 진입할 수 있도록 했습니다. 이러한 구현에 있어서 필요한 값이 unlockproc입니다.
void
yield(void)
{
struct proc *p = myproc();
acquire(&ptable.lock); //DOC: yieldlock
p->ticks++;
mlfq.global_ticks++;
myproc()->state = RUNNABLE;
// scheduler lock
if(mlfq.lockproc == p || mlfq.unlockproc == p) {
if(mlfq.unlockproc == p) {
mlfq.unlockproc = 0;
}
insert(&mlfq.l_queue[0], p, mlfq.l_queue[0].head);
} else {
...
}
sched();
release(&ptable.lock);
}추가적으로 schedulerLock, schedulerUnlock을 구현하며 고민했던 부분에 대한 정리를 하며 구현부에 대한 설명을 마무리하겠습니다.
lock을 잡은 process가 yield, sleep, exit 하는 상황에 대한 고민
lock을 잡은 process가 I/O에 의해서 sleep하거나 다른 이유로 exit 했을때는 다른 process가 cpu를 점유해야하기 때문에 lock을 풀어주도록 작업했습니다.
하지만 lock을 잡은 process가 yield를 호출했을 때는 현재 lock을 잡은 프로세스가 block 상태로 간 것이 아니기 때문에 충분히 cpu를 계속해서 잡을 수 있다고 판단했고, yield의 호출은 잘못된 호출이라는 판단을 하도록 하여 lock을 풀지 않고 계속해서 cpu를 점유하고 있도록 작업했습니다.
lock 하지 않은 상태에서 unlock 하는 상황에 대한 고민
lock 하지 않은 상태에서 unlock을 하는 것은 필요 없는 작업이기 때문에 아래와 같이 예외처리를 할 수 있도록 작업햇습니다.
// release mlfq lock
void
releasemlfq()
{
if(mlfq.lockproc != 0) {
mlfq.lockproc = 0;
}
}