[Operating System] xv6 Multilevel Feedback Queue (MLFQ), Monopoly Queue (MoQ)
운영체제 과제로 진행한 xv6 project2에 대한 설명입니다.
정확하지 않은 내용일 수 있으므로 참고만 하시길 바랍니다.
전체 코드는 아래 링크에서 확인하실 수 있습니다.
https://github.com/LeeHyo-Jeong/HYU-ELE3021
[Design]
Synchronizatioin
multitasking 환경에는 여러 프로세스(또는 스레드)가 공유하는 자원이 있다.
이 때 race condition이 발생하면 공유 자원의 신뢰성이 떨어진다.
이 문제를 해결하기 위한 메커니즘이 synchronization이다.
critical section은 프로세스가 공유 자원에 접근하는 영역이다.
synchronization 메커니즘을 이용해 critical section에 한 번에 하나의 프로세스만 접근할 수 있도록 하여 race condition을 막는다.
Race condition
여러 프로세스가 공유 자원에 동시에 접근할 때 접근 순서에 따라 실행 결과가 달라질 수 있는 상황을 일컫는다.
race condition은 공유 자원의 일관성을 해칠 수 있다.
Lock
동시에 하나의 프로세스만이 특정한 코드 영역이나 자원에 접근할 수 있도록 하는 synchronization 도구이다.
xv6에서는 acquire()와 release()를 사용해 Lock을 구현하고, 이를 통해 critical section에 대한 동시 접근을 제어한다.
// only one process or thread can access the code section (critical section)
// between acquire and release
acquire(&lock);
...
release(&lock);Scheduling
스케줄링은 운영체제가 프로세스에 CPU를 할당하는 방법을 정의한다.
스케줄러는 CPU 자원이 여러 프로세스에게 공정하게 분배되도록 보장한다.
Round-Robin
시분할 시스템을 위해 설계된 스케줄링이다.
프로세스들 사이에 priority를 두지 않고, 순서대로 time quantum만큼 CPU를 할당하는 방식이다.
CPU 자원을 사용할 수 있는 기회를 프로세스들에게 공정하게 부여하기 위한 방법으로, 프로세스가 주어진 time quantum을 모두 사용하면 timer device로부터 interrupt가 와서 ready queue의 끝으로 밀려나게 된다.
RR은 context switch의 overhead가 있지만 특정 프로세스의 독점을 방지할 수 있고, 응답이 빨라야 하는 실시간 시스템에 적합하다.
Multi-Level Feedback Queue
MLFQ는 여러 계층의 큐를 가지며, 우선순위가 높은 큐부터 작업을 처리한다.
MLFQ는 다음 두 가지 문제를 해결하기 위해 고안됐다.
- 짧은 작업(e.g. I/O bound job)에게 먼저 CPU를 준다.
- 응답이 빨라 보이도록 한다.
MLFQ는 큐 간의 스케줄링 알고리즘, 큐 내에서 프로세스의 스케줄링 알고리즘이 존재한다.
이번 project에서 MLFQ는 L0~L3 총 4개의 큐로 이루어져 있고, 수가 작을수록 우선순위가 높은 큐이다.
스케줄러는 우선순위가 높은 큐의 프로세스부터 스케줄링 한다.
L0, L1, L2는 Round Robin 정책을 따르고, L3은 priority 스케줄링을 한다.
L0 큐에서 실행된 프로세스가 time quantum을 모두 사용했을 때 pid(process id)가 홀수인 프로세스들은 L1 큐로 내려가고, pid가 짝수인 프로세스들은 L2 큐로 내려간다. L1이나 L2 큐에서 실행된 프로세스가 time quantum을 모두 사용했을 때 프로세스는 L3 큐로 내려가게 된다.
Monopoly Queue
사용자의 요청에 따라 CPU 자원을 길게 사용해야 할 프로세스가 있을 수 있다. 해당 프로세스들의 스케줄링을 위해 FCFS 정책을 따르는 Monopoly Queue가 존재한다.
MoQ에 속한 프로세스들은 평소에는 스케줄링 되지 않다가 monopolize 시스템 콜이 호출되면 즉시 스케줄링 된다.
- 먼저 큐에 들어온 프로세스가 먼저 스케줄링 된다.
- MoQ를 스케줄링 하는 동안 priority boosting은 발생하지 않는다.
Process State
모든 프로세스는 항상 다음 상태들 중 하나의 상태로 존재한다.new
프로그램이 커널에 PCB를 부여받은 상태
운영체제는 프로세스를 생성한 후 주기억장치 공간이 여유로운지 확인하고
공간이 충분하면 프로세스 주소 공간을 할당한 후 프로세스를 Ready 상태로 바꾸어준다.Ready
실행 가능한 준비 상태, CPU가 주어지면 언제든 실행될 수 있다.
Running
CPU에 의해 현재 실행 중인 상태Waiting
프로세스가 실행되다가 할당받은 CPU를 반납하고 I/O 작업이 완료되어 interrupt가 올 때까지 대기하는 상황
Terminated
프로그램 실행이 종료
[Implement]
Structures
proc
// Per-process state
struct proc {
int priority; // priority of process in the MLFQ
int proctick; // tick of process
int queuelevel; // level of the queue containing the process
int isMoQ;
struct proc* next; // pointer to next process in the queue
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)
};기존의 proc 구조체에서 새로 추가한 부분은 다음과 같다.int priority
MLFQ 안에 있는 프로세스의 priority int proctick
process가 자신의 job을 수행한 시간
MLFQ에서 proctick이 queue의 time quantum보다 커지면 주어진 time quantum 내에 모든 job을 수행하지 못한 것이다. int queuelevel
process가 들어가있는 MLFQ의 level int isMoQ
process가 MoQ 안에 있어서 MoQ 스케줄링을 받을 대상인지 나타내는 flag struct proc* next
queue 안에 있는 다음 프로세스를 가리키는 포인터이다. queue가 Linked list 형식이므로 다음 process를 찾을 때 사용된다.
Queue
struct Queue{
struct proc* front; // first process of the queue
struct proc* rear; // last process of the queue
struct spinlock lock; // lock of the queue
int tq; // time quantum of the queue
int level;
int size; // # of unfinished process, used for MoQ
};Queue는 Linked list 형식으로 구현된다. 다음은 Queue의 대략적인 구조이다.
struct proc* front
Queue의 첫 번째 프로세스를 가리키는 포인터 struct proc* rear
Queue의 마지막 프로세스를 가리키는 포인터 int tq
Round Robin 스케줄링을 하는 큐(MLFQ)의 time quantum, MoQ에서는 사용되지 않는다. int level
MLFQ의 level, MoQ에서는 사용되지 않는다.int size
MoQ의 크기(MoQ에서 RUNNABLE한 프로세스의 개수), MLFQ에서는 사용되지 않는다.
구조체 내에서 proc 구조체가 갖는 next 필드를 이용해 프로세스간 연결을 해준다.
Global Variables
MLFQ
struct Queue mlfq[4]mlfq는 다음과 같은 구조를 갖는다.
MLFQ의 각 레벨별로 front, rear 프로세스를 갖고 같은 큐 내의 프로세스들은 연결되어있다.
MLFQ에서는 Queue 구조체의 size 필드는 사용되지 않는다.
MoQ
struct Queue moqmoq는 다음과 같은 구조를 갖는다.
MoQ는 front, rear 프로세스를 갖고 같은 큐 내의 프로세스들은 연결되어있다.
MoQ에서는 Queue 구조체의 tq, level 필드는 사용되지 않는다.
ticks
xv6 시스템 내에 선언되어있는 global tick이다.
case T_IRQ0 + IRQ_TIMER:
if(cpuid() == 0){
// cprintf("ticks = %d, pid = %d, name = \"test_printf\"", ticks, myproc()->pid);
acquire(&tickslock);
ticks++;trap.c의 trap 함수에서 timer interrupt가 발생할 때마다 global tick인 ticks 변수를 1씩 증가시킨다.
isMoQ
현재 MoQ 스케줄링이 일어나고 있는지 여부를 나타내는 flag 변수이다.
monolock
isMoQ 변수에 대한 lock이다.
isMLFQ
현재 MLFQ 스케줄링이 일어나고 있는지 여부를 나타내는 flag 변수이다.
mlfqlock
isMLFQ 변수에 대한 lock이다.
extern struct spinlock tickslock;
extern uint isMoQ;
extern struct spinlock monolock;
extern uint isMLFQ;
extern struct spinlock mlfqlock;isMoQ, monolock, isMLFQ, mlfqlock 변수들을 trap.c에 전역변수로 선언하고 defs.h에서 extern 해주어서 다른 파일에서도 접근할 수 있게 하였다.
System Calls
yield
yield는 현재 실행중인 프로세스가 다른 프로세스에게 cpu를 양보하게 한다.
Round Robin에서 프로세스가 주어진 time quantum을 모두 사용하면 호출되어 RUNNABLE 상태인 프로세스에게 cpu를 양보하게 된다.
void
yield(void)
{
acquire(&ptable.lock); //DOC: yieldlock
myproc()->state = RUNNABLE;
sched();
release(&ptable.lock);
}getlev
프로세스가 속한 큐의 레벨을 반환한다.
MoQ에 속한 프로세스인 경우 99를 반환한다.
int getlev(void){
return myproc()->queuelevel;
}proc 구조체에 추가한 queuelevel 필드를 반환한다.
setpriority
특정 pid를 가지는 프로세스의 priority를 설정한다.
priority 설정에 성공한 경우 0, 주어진 pid를 가진 프로세스가 없는 경우 -1, priority가 0과 10 사이의 정수가 아닌 경우 -2를 반환한다.
int setpriority(int pid, int priority){
if(0 > priority || 10 < priority) return -2;
acquire(&ptable.lock);
struct proc* find;
for(find = ptable.proc; find < &ptable.proc[NPROC] ; find++){
if(find->pid == pid){
find->priority = priority;
release(&ptable.lock);
return 0;
}
}
// process not found
release(&ptable.lock);
return -1;
}특정 pid를 갖는 프로세스를 찾기 위해 ptable을 조회한다.
ptable은 시스템의 모든 프로세스에 대한 정보를 저장하는 구조체이다. ptable 구조체의 선언은 다음과 같다.
struct {
struct spinlock lock;
struct proc proc[NPROC];
} ptable;ptable은 모든 프로세스에 의해 공유되므로 여러 프로세스가 동시에 이 테이블을 읽거나 수정할 경우 데이터의 일관성과 무결성이 손상될 수 있다. 따라서 ptable에 접근하기 전에 lock을 획득한다. lock을 얻은 후 ptable을 순회하며 특정 pid를 갖는 프로세스를 찾으면 priority를 설정해주고 0을 리턴한다.
ptable을 모두 조회했는데 해당 pid를 갖는 프로세스가 없다면 -1을 리턴한다.
setmonopoly
특정 pid를 가진 프로세스를 MoQ로 이동한다. 인자로 독점 자격을 증명할 암호를 받는다.
암호가 일치할 경우(2022077510), MoQ의 크기 즉, MoQ 내에 존재하는 RUNNABLE한 프로세스의 개수를 반환한다. pid가 존재하지 않는 프로세스인 경우 -1을 반환한다. 암호가 일치하지 않는 경우 -2를 반환한다.
int setmonopoly(int pid, int password){
if(password != 2022077510){
cprintf("Invalid password\n");
kill(pid);
return -2;
}
struct proc* p;
for(p = ptable.proc ; p < &ptable.proc[NPROC] ; p++){
if(p->pid == pid){
// move the process from MLFQ to MoQ
moq_move(p);
p->isMoQ = 1;
return moq.size;
}
}
return -1;
}password가 일치하지 않는 경우 프로세스를 강제로 종료시키고 -2를 반환한다.
암호가 일치하는 경우 ptable을 순회하며 해당 pid를 가진 프로세스를 찾은 후 찾는다면 프로세스가 MoQ에 존재한다는 것을 나타내기 위해 isMoQ 필드를 1로 변경하고 MoQ의 크기를 반환한다.
monopolize
MoQ의 프로세스가 CPU를 독점하여 사용하도록 한다.
void monopolize(){
acquire(&monolock);
isMoQ = 1;
release(&monolock);
acquire(&mlfqlock);
isMLFQ = 0;
release(&mlfqlock);
}monopolize가 호출되었음을 알리기 위해 전역변수 isMoQ를 1로 바꾸고 isMLFQ를 0으로 바꾼다. 두 변수는 모든 프로세스가 공유하는 변수이므로 변경하는 코드 앞뒤로 lock을 걸어준다.
unmonopolize
독점적 MoQ 스케줄링을 중지하고 기존의 MLFQ 스케줄링으로 돌아간다.
void unmonopolize(){
acquire(&monolock);
isMoQ = 0;
release(&monolock);
acquire(&moq.lock);
struct proc* p;
for(p = moq.front ; p != 0 ; p = p->next){
if(p->state == ZOMBIE && p->isMoQ == 1){
moq_dequeue(p);
}
}
release(&moq.lock);
ticks = 0;
acquire(&mlfqlock);
isMLFQ = 1;
release(&mlfqlock);
}MoQ 스케줄링을 중지해야 하므로 전역변수 isMoQ를 0으로 변경한다. 이후 moq에서 실행이 모두 종료된 ZOMBIE 상태의 프로세스들을 제거하기 위해 moq를 순회하며 dequeue한다. 여기서도 마찬가지로 순회하기 전에 moq에 lock을 얻고 순회 후 lock을 해제한다. MLFQ 스케줄링으로 돌아가기 전에 isMLFQ를 1로 변경해 스케줄러에게 알리고 global tick을 0으로 변경한다.
Functions
priority_boosting
starvation을 막기 위해 global tick이 100 ticks가 될 때마다 모든 프로세스들을 L0 큐로 재조정한다. priority boosting이 일어날 때 모든 프로세스들의 time quantum은 초기화된다.
void
trap(struct trapframe *tf)
{
...
switch(tf->trapno){
...
case T_IRQ0 + IRQ_TIMER:
if(cpuid() == 0){
// cprintf("ticks = %d, pid = %d, name = \"test_printf\"", ticks, myproc()->pid);
acquire(&tickslock);
ticks++;
if(isMoQ == 0 && ticks >= 100){
priority_boosting();
ticks = 0;
//cprintf("Priority Boosting done\n");
}
wakeup(&ticks);
release(&tickslock);
}
...
}trap.c의 trap 함수에서 timer interrupt가 올 때마다 global tick을 1씩 증가시키다가 global tick이 100이 되면 priority_boosting을 호출한다. MoQ를 스케줄링 하는 동안은 priority boosting이 발생하지 않으므로 if(isMoQ == 0 && ticks >= 100)을 만족할 때만 호출한다. priority_boosting 함수는 다음과 같다.
void priority_boosting(void){
// priority boosting is called when ticks >= 100 (implemented in trap.c)
struct proc* p;
acquire(&ptable.lock);
for(p = ptable.proc ; p < &ptable.proc[NPROC] ; p++){
// move only MLFQ processes
if(p->isMoQ == 1) continue;
// move all L1~L3 processes to L0
if(p->queuelevel == 1 || p->queuelevel == 2 || p->queuelevel == 3){
dequeue(p, &mlfq[p->queuelevel]);
enqueue(p, 0);
p->proctick = 0;
}
}
release(&ptable.lock);
mlfq[1].front = 0;
mlfq[2].front = 0;
mlfq[3].front = 0;
}ptable을 순회하며 L1, L2, L3 레벨에 있는 모든 프로세스들을 해당 큐에서 L0 큐로 이동시킨다. 이 때 모든 프로세스들의 time quantum을 초기화한다. 그리고 L1, L2, L3 큐를 비워준다.
enqueue
프로세스를 MLFQ에 넣어주기 위한 함수이다. parameter로 프로세스와 들어갈 MLFQ의 레벨을 받는다.
void enqueue(struct proc* p, int level){
if(p->queuelevel != -1){
return;
}
if(level < 0 || level > 3){
cprintf("out of level range\n");
return;
}
// if the queue is empty
if(mlfq_empty(level)){
acquire(&mlfq[level].lock);
mlfq[level].front = p;
mlfq[level].rear = p;
release(&mlfq[level].lock);
}
// if the queue is not empty
else{
acquire(&mlfq[level].lock);
// set the process p as the last process of the queue
mlfq[level].rear->next = p;
mlfq[level].rear = p;
release(&mlfq[level].lock);
}
// the next process of the last process is null
p->next = 0;
p->queuelevel = level;
p->proctick = 0;
p->priority = 0;
}
priority boosting이 일어날 때 프로세스의 동기화에 문제가 생기는 것을 방지하기 위해 프로세스의 queuelevel이 -1인지 검사한다. queuelevel이 -1인 프로세스는 다음과 같다.
- 큐에서 dequeue된 프로세스
- allocproc 함수에 의해 새롭게 할당된 프로세스
프로세스가 이 둘 중 하나의 상태가 아니라면 enqueue가 잘못 호출된 것이므로 함수의 실행을 종료시킨다.
또한 프로세스가 들어갈 수 있는 레벨은 L0에서 L3까지이므로, 레벨의 범위가 맞지 않는다면 실행을 종료시킨다.
정상적으로 호출되었다면 프로세스를 해당하는 레벨의 MLFQ에 넣어주고 queuelevel을 level로, proctick(process time quantum)을 0으로 초기화한다.
dequeue
프로세스를 MLFQ에서 빼내기 위한 함수이다. parameter로 프로세스와 프로세스가 속해있는 queue를 받는다.
void dequeue(struct proc* p, struct Queue* q){
// synchronization
if(p->queuelevel != q->level){
return;
}
int level = p->queuelevel;
if(level < 0 || level > 3){
cprintf("out of level range\n");
return;
}
if(mlfq_empty(level)){
cprintf("Empty queue\n");
return;
}
// find the given process in the queue
// and if it is found, dequeue it from the queue
// if the process to be dequeued is front of the queue
if(p == mlfq[level].front){
acquire(&mlfq[level].lock);
mlfq[level].front = p->next;
if(mlfq[level].front == 0) mlfq[level].rear = 0;
p->next = 0;
release(&mlfq[level].lock);
}
// else, find the process in the queue
else{
struct proc* find = q->front;
while(find->next != p) find = find->next;
find->next = p->next;
if(q->rear == p) q->rear = find;
p->next = 0;
}
p->queuelevel = -1;
} 프로세스가 인자로 받은 큐에 존재하지 않거나 비어있는 큐라면 함수의 실행을 종료시킨다.
아니라면 큐의 rear에 프로세스를 넣어준다.
동기화를 위해 MLFQ에 접근할 때는 lock을 얻고, 접근이 끝나면 lock을 해제한다. dequeue가 성공적으로 일어났다면 queuelevel을 -1로 바꾸어 이후 enqueue되어 스케줄링 될 수 있도록 한다.
move
프로세스를 한 MLFQ에서 빼내서(dequeue) 다른 레벨의 MLFQ로 이동(enqueue)시킨다.
moq_dequeue
MoQ에서 프로세스를 빼내기 위한 함수이다.
void moq_dequeue(struct proc* p){
if(p->isMoQ != 1){
cprintf("This process is not in MoQ\n");
return;
}
// if the process to be dequeued is front of MoQ
if(p == moq.front){
acquire(&moq.lock);
moq.front = p->next;
// if the queue is empty after dequeue operation
if(moq.front == 0) moq.rear = 0;
p->next = 0;
release(&moq.lock);
}
else{
acquire(&moq.lock);
// find previous process of p in MoQ
struct proc* find = moq.front;
while(find->next != p) find = find->next;
find->next = p->next;
if(moq.rear == p) moq.rear = find;
p->next = 0;
release(&moq.lock);
}
p->isMoQ = 0;
}프로세스가 MoQ에 있지 않다면 함수를 강제로 종료시킨다.
아니라면 MoQ에서 빼내고 프로세스의 isMoQ를 0으로 변경한다. 마찬가지로 MoQ에 접근할 때는 lock을 얻고 접근이 끝나면 lock을 해제한다.
moq_move
setmonopoly를 호출해서 프로세스를 MoQ로 이동시킬 때 사용된다.
void moq_move(struct proc* p){
if(p == 0) return;
int level = p->queuelevel;
// dequeue the process from previous MLFQ
dequeue(p, &mlfq[level]);
acquire(&ptable.lock);
if(p->queuelevel != -1) return;
// enqueue the process in MoQ
// if MoQ is empty
if(moq.front == 0){
moq.front = p;
moq.rear = p;
}
// if MoQ is not empty
else{
moq.rear->next = p;
moq.rear = p;
p->next = 0;
}
// number of RUNNABLE process of MoQ increases
if(p->state == RUNNABLE) moq.size++;
release(&ptable.lock);
p->isMoQ = 1;
p->queuelevel = 99;
}프로세스를 MoQ로 이동하기 전에 기존에 프로세스가 존재하던 MLFQ에서 dequeue한다. 이 때 dequeue가 성공적으로 이루어졌다면 프로세스의 queuelevel이 -1이어야한다. 따라서 dequeue 이후 프로세스의 queuelevel이 -1이 아니라면 함수를 강제로 종료한다.
이후 프로세스를 MoQ에 집어넣고 MoQ의 크기를 1만큼 증가시킨다. 프로세스의 isMoQ를 1로 바꾸어 MoQ 스케줄링의 대상이 된다는 것을 나타내고 queuelevel을 99로 변경시켜준다.
Scheduler
// Common CPU setup code.
static void
mpmain(void)
{
cprintf("cpu%d: starting %d\n", cpuid(), cpuid());
idtinit(); // load idt register
xchg(&(mycpu()->started), 1); // tell startothers() we're up
scheduler(); // start running processes
}main.c의 mpmain 함수에서 프로세스들이 공통으로 사용하는 CPU를 초기화하고 proc.c의 scheduler 함수를 호출해 프로세스 스케줄링을 시작한다.
Entire Scheduler
전체 scheduler 코드는 다음과 같다.
scheduler 코드 보기
void scheduler(void){
struct proc* p = 0;
struct cpu* c = mycpu();
// there is no process which is using this cpu
c->proc = 0;
// set up time quantum and level for each queue
for(int i = 0 ; i < 4 ; i++){
mlfq[i].tq = 2 * i + 2;
mlfq[i].level = i;
}
for(;;){
// check if monopolize called
// if monopolize called, execute MoQ scheduler
if(isMoQ == 1 && isMLFQ == 0) {
for(p = moq.front ; p != 0 ; p = p->next){
if(p->state != RUNNABLE) continue;
// run the process in MoQ
// to switch context, acquire ptable lock
acquire(&ptable.lock);
c->proc = p;
switchuvm(p);
p->state = RUNNING;
swtch(&(c->scheduler), p->context);
switchkvm();
release(&ptable.lock);
c->proc = 0;
if(p->state == ZOMBIE){
moq_dequeue(p);
}
// if MoQ is empty, call unmonopolize
if(moq.front == 0){
unmonopolize();
}
}
}
// if monopolize not called
// execute MLFQ scheduler
else if(isMLFQ == 1 && isMoQ == 0){
sti();
acquire(&ptable.lock);
for(int level = 0 ; level < 3 ; level++){
for(p = mlfq[level].front ; p != 0 ; p = p->next){
if(p->state != RUNNABLE) continue;
// run the process
c->proc = p;
switchuvm(p);
p->state = RUNNING;
p->proctick++;
swtch(&(c->scheduler), p->context);
switchkvm();
// process done running
c->proc = 0;
// if the process end up its job during time quantum
if(p->state == ZOMBIE){
dequeue(p, &mlfq[level]);
}
// to avoid moving SLEEPING process, check if the process if RUNNABLE
else if(p->state == RUNNABLE){
// L0 process used up its time quantum
// and it has even pid
if(p->queuelevel == 0 && p->proctick >= mlfq[0].tq){
if(p->pid % 2 == 0){
move(p, 2);
}
// it has odd pid
else if(p->pid % 2 != 0){
move(p, 1);
}
}
else if(p->queuelevel == 1 && p->proctick >= mlfq[1].tq){
move(p, 3);
}
else if(p->queuelevel == 2 && p->proctick >= mlfq[2].tq){
move(p, 3);
}
}
}
}
// L3
if(mlfq[3].front != 0 && mlfq[1].front == 0 && mlfq[2].front == 0){
struct proc* max = mlfq[3].front;
struct proc* find = 0;
int max_priority = max->priority;
// find a process that has maximum priority in L3
for(find = mlfq[3].front ; find != 0 ; find = find->next){
if(find->state != RUNNABLE) continue;
if(find->priority > max_priority){
max_priority = find->priority;
max = find;
}
}
if(max == 0){
release(&ptable.lock);
continue;
}
// run the process
c->proc = max;
switchuvm(max);
max->state = RUNNING;
max->proctick++;
swtch(&(c->scheduler), max->context);
switchkvm();
// process done running
c->proc = 0;
// if the process end up its job during time quantum
if(max->state == ZOMBIE){
dequeue(max, &mlfq[3]);
}
// if the process has used up its time quantum
if(max->state == RUNNABLE && max->proctick >= mlfq[3].tq){
max->proctick = 0;
setpriority(max->pid, (max->priority)-1);
}
}
release(&ptable.lock);
}
}
}MoQ Scheduler
scheduler 함수 내에서 MoQ 스케줄러 파트는 다음과 같다.
// check if monopolize called
// if monopolize called, execute MoQ scheduler
if(isMoQ == 1 && isMLFQ == 0) {
for(p = moq.front ; p != 0 ; p = p->next){
if(p->state != RUNNABLE) continue;
// run the process in MoQ
// to switch context, acquire ptable lock
acquire(&ptable.lock);
c->proc = p;
switchuvm(p);
p->state = RUNNING;
swtch(&(c->scheduler), p->context);
switchkvm();
release(&ptable.lock);
c->proc = 0;
if(p->state == ZOMBIE){
moq_dequeue(p);
}
// if MoQ is empty, call unmonopolize
if(moq.front == 0){
unmonopolize();
}
}
}
scheduler에서 무한루프를 돌며 monopolize가 호출되면 MoQ 스케줄러를 실행한다. monopolize가 호출되어 isMoQ가 1이 되고 isMLFQ가 1이 되면 위의 코드를 실행한다.
MoQ를 순회하며 RUNNABLE한 프로세스를 찾고 FCFS 방식으로 스케줄링한다. MoQ 내의 프로세스가 모두 실행되어 MoQ가 비게 되면 unmonopolize를 호출해 다시 MLFQ 스케줄링으로 돌아간다.
MLFQ Scheduler
scheduler 함수 내에서 MLFQ 스케줄러 파트는 다음과 같다.
// if monopolize not called
// execute MLFQ scheduler
else if(isMLFQ == 1 && isMoQ == 0){
sti();
acquire(&ptable.lock);
for(int level = 0 ; level < 3 ; level++){
for(p = mlfq[level].front ; p != 0 ; p = p->next){
if(p->state != RUNNABLE) continue;
// run the process
c->proc = p;
switchuvm(p);
p->state = RUNNING;
p->proctick++;
swtch(&(c->scheduler), p->context);
switchkvm();
// process done running
c->proc = 0;
// if the process end up its job during time quantum
if(p->state == ZOMBIE){
dequeue(p, &mlfq[level]);
}
// to avoid moving SLEEPING process, check if the process if RUNNABLE
else if(p->state == RUNNABLE){
// L0 process used up its time quantum
// and it has even pid
if(p->queuelevel == 0 && p->proctick >= mlfq[0].tq){
if(p->pid % 2 == 0){
move(p, 2);
}
// it has odd pid
else if(p->pid % 2 != 0){
move(p, 1);
}
}
else if(p->queuelevel == 1 && p->proctick >= mlfq[1].tq){
move(p, 3);
}
else if(p->queuelevel == 2 && p->proctick >= mlfq[2].tq){
move(p, 3);
}
}
}
}
// L3
if(mlfq[3].front != 0 && mlfq[1].front == 0 && mlfq[2].front == 0){
struct proc* max = mlfq[3].front;
struct proc* find = 0;
int max_priority = max->priority;
// find a process that has maximum priority in L3
for(find = mlfq[3].front ; find != 0 ; find = find->next){
if(find->state != RUNNABLE) continue;
if(find->priority > max_priority){
max_priority = find->priority;
max = find;
}
}
if(max == 0){
release(&ptable.lock);
continue;
}
// run the process
c->proc = max;
switchuvm(max);
max->state = RUNNING;
max->proctick++;
swtch(&(c->scheduler), max->context);
switchkvm();
// process done running
c->proc = 0;
// if the process end up its job during time quantum
if(max->state == ZOMBIE){
dequeue(max, &mlfq[3]);
}
// if the process has used up its time quantum
if(max->state == RUNNABLE && max->proctick >= mlfq[3].tq){
max->proctick = 0;
setpriority(max->pid, (max->priority)-1);
}
}
release(&ptable.lock);
}
}monopolize가 호출되었는지 확인하고, 호출되지 않았다면 MLFQ 스케줄링을 시작한다.
L0에 RUNNABLE한 프로세스가 없으면 L1, L1에 RUNNABLE한 프로세스가 없으면 L2, L1 및 L2에 RUNNABLE한 프로세스가 없으면 L3를 스케줄링한다.
L0->L1->L2 순으로 큐에서 RUNNABLE한 프로세스를 찾고 프로세스에게 CPU를 주어서 실행시키고 프로세스의 tick을 1만큼 증가시킨다. 프로세스가 run을 끝냈을 때 ZOMBIE상태라면 자신의 job을 끝낸 것이므로 큐에서 빼낸다.
프로세스가 실행되는 중에 sleep system call이 와서 프로세스가 SLEEPING 상태가 될 수 있다. 프로세스가 SLEEPING 상태라면 이동시켜서는 안되므로 프로세스의 state가 RUNNABLE인지 다시 한 번 확인한다.
만약 L0에 존재하는 프로세스가 주어진 time quantum을 모두 사용하고도 job을 끝내지 못했다면 홀수 pid를 가진 프로세스는 L1으로, 짝수 pid를 가진 프로세스는 L2로 이동시킨다.
L1 또는 L2에 존재하는 프로세스가 time quantum을 모두 사용하고도 job을 끝내지 못했다면 L3로 이동시킨다.
L1과 L2에 RUNNABLE한 프로세스가 존재하지 않는다면 L3 스케줄링을 시작한다.
L3는 priority가 높은 프로세스부터 스케줄링하므로, 큐를 순회하며 priority가 높은 프로세스를 찾고 CPU를 주어서 실행시킨다.
L3도 마찬가지로 프로세스의 수행이 끝나 ZOMBIE 상태가 되면 큐에서 빼내준다.
만약 L3에 존재하는 프로세스가 time quantum을 사용하고도 job을 끝내지 못했다면 priority를 1만큼 낮추어준다.
global tick이 100이 될 때마다 priority boosting을 호출하므로 priority가 낮은 프로세스가 다른 프로세스에 의해 실행되지 못하는 starvation 문제는 없어진다.
[Result]
proc.c에는 scheduler 함수가 두 개 존재한다. 하나는 기존에 xv6에 구현되어있던 기본 스케줄러이고, 다른 하나는 내가 구현한 MLFQ와 MoQ 스케줄러이다. 컴파일러가 하나의 스케줄러만 보도록 조건부 컴파일을 이용하였다.
#ifdef MLFQ_MOQ
void scheduler(void){
...
}
#else
void
scheduler(void)
{
...
}
#endif해당 프로젝트에서는 CMake를 사용하므로 Makefile을 다음과 같이 수정했다.
# Try to infer the correct QEMU
ifndef QEMU
QEMU = $(shell if which qemu > /dev/null; \
...
endif
SCHED_TYPE = DEFAULT
CC = $(TOOLPREFIX)gcc
...
CFLAGS = -fno-pic -static -fno-builtin -fno-strict-aliasing -O2 -Wall -MD -ggdb -m32 -Werror -fno-omit-frame-pointer
CFLAGS += -D$(SCHED_TYPE)
...Inputs
다음 명령어를 차례대로 입력한다.
make cleanmake SCHED_TYPE=MLFQ_MOQmake fs.img./bootxv6.shTest에서 각 프로세스는 자신이 속해 있는 큐의 레벨(L0~L3 및 MoQ)를 각각 카운트한다. Test의 결과는 다음과 같다.
Test1
모든 프로세스가 자신에게 주어진 time quantum을 전부 쓰고 비슷한 시기에 낮은 레벨로 내려가므로 비슷한 시기에 끝나게 된다.
L0에서 pid가 홀수인 프로세스는 L1으로, 짝수인 프로세스는 L2로 내려가는데 L1 큐가 L2 큐보다 우선순위가 높으므로 pid가 홀수인 프로세스가 대체로 먼저 끝나게 된다.
Test2
pid가 큰 프로세스에게 더 높은 우선순위를 부여한다. pid가 큰 프로세스가 더 먼저 끝날 확률이 높다.
Test3
pid가 큰 프로세스에게 더 높은 우선순위를 부여한다.
각 프로세스는 loop를 돌 때마다 sleep 시스템 콜을 호출한다. sleep 상태에 있는 동안은 스케줄링 되지 않고 다른 프로세스가 실행될 수 있기 때문에 거의 동시에 작업을 마무리하게 된다.
프로세스가 대부분 L0에 머무르기 때문에 pid가 작은 프로세스가 먼저 끝날 확률이 높다.
Test4
pid가 홀수인 프로세스를 MoQ에 저장한다. 새로운 프로세스가 추가될 때마다 MoQ에 존재하는 프로세스의 개수를 출력한다.
마지막 자식 프로세스(pid 36)은 monopolize를 호출하고 exit()를 호출한다.
MoQ에 존재하는 프로세스들은 FCFS 방식으로 스케줄링 되므로 pid가 작은 프로세스가 먼저 종료된다.
이후 기존 MLFQ 스케줄링으로 돌아와 나머지 프로세스들을 실행한다.
[Trouble Shooting]
console.c: In function 'cgaputc': error: implicit declaration of function 'inb'
건들지도 않은 파일에서 다음과 같은 에러가 났다.
찾아보니 세미콜론이나 괄호를 똑바로 닫지 않은 것과 관련된 문제라고 했다. 그래서 내가 수정했던 모든 파일들을 찾아보니 struct를 선언할 때 마지막에 세미콜론을 빼먹은 것을 발견했다.
shell을 실행했을 때 무한로딩
cpu0: starting을 출력하고선 아무 입력도 받지 않았다. 그래서 cscope로 이 출력을 어디서 하는지 찾아보았다.
출력은 main.c의 mpmain 함수에서 하고있었다. main 함수에서 mpmain 함수를 호출해서 출력되는 것이었다. main 함수에서는 mpmain 함수 뿐만 아니라 userinit 함수도 호출한다. userinit 함수에서는 allocproc을 호출해 프로세스가 실행될 때 필요한 것들을 할당해준다. 그런데 여기서 만들어준 프로세스를 enqueue해주지 않아서 스케줄링의 대상이 되지 않았던 것이다. 그래서 allocproc에서 프로세스를 enqueue해주었다.
panic: no pagedir
시스템에서 프로세스는 실행되려면 페이지 디렉토리가 필요하다. 시스템이나 함수가 프로세스의 context switching을 할 때 초기화 된 pgdir을 찾지 못하면 이런 오류가 발생한다.
userinnit에서 프로세스를 RUNNABLE하게 바꾸어주는 코드를 제외한 다른 곳에서 프로세스를 RUNNABLE하게 해주는 코드를 모두 지웠더니 해결되었다.
정확한 이유는 알 수 없지만 동기화 이슈로 인해 dequeue된 프로세스의 상태가 RUNNABLE해져서 이미 page directory가 해제된 프로세스로의 context switch가 일어나 이런 문제가 발생했다고 예상된다.
panic: release
이미 release된 lock을 또 release하거나, 잘못된 lock을 release하면 발생하는 문제라고 한다.
하지만 나는 그 어느 곳에서도 lock을 두 번 release한 적이 없었다.
MLFQ에서는 발생하지 않던 문제가 MoQ만 실행하면 발생해서 MoQ의 코드를 관찰해보았다. 알고보니 context switch가 일어나기 전에 ptable에 대한 lock을 걸지 않아서 발생하는 문제였다. CPU가 현재 프로세스에서 다른 프로세스로 switch하기 전에 PCB(ptable)에 현재 state를 저장하고 새로운 프로세스의 PCB로부터 context를 가져와 restore해야하므로 PCB에 접근해야하는데, lock을 걸지 않아 이런 문제가 발생한 것 같다.