본 위키는 commit 기준 Real Finish에 맞추어 작성되어 있습니다.
12299_2019030991_홍정범
우선 가장 처음 결정한 것은 Queue를 직접 만들어서 데이터를 동적으로 관리할 것인가, 아니면 ptable을 for문을 순회하면서 스케줄링을 해줄 것인가 이었다. 만약에 단지 ptable을 순회하면서 스케줄링을 할 수 있다면 굳이 큐를 만들어서 관리해주는 수고를 덜어도 될 것이라고 초기에 판단, 그래서 ptable을 순회하여 스케줄링을 하기로 마음먹었다.
ptable을 순회하면서 어떤 process를 찾을지 결정할 것이기 때문에 기본적으로 각 프로세스는 자신이 어느 큐에 속해 있는지에 대한 정보를 가지고 있어야 한다. 그리고 타임인터럽트의 발생으로 인한 q_lv 및 priorioty의 변경이 일어나야 하므로 각 프로세스는 자신이 얼마나 일을 했는지에 대한 정보를 가지고 있어야 한다. 그러려면 당연히 priorioty 값도 가지고 있어야 한다. 그래서 3개의 변수를 추가해 주었다.
// Per-process state
struct proc {
int priority; // Scheduling prioriy
int tq; // Time quantum
int q_lv; // Queue level
..
}
그리고 처음 실행된 프로세스는 가장 높은 레벨의 큐에 들어가야 하므로 allocproc() 함수에서 초기화를 해주었다.
found:
p->state = EMBRYO;
p->pid = nextpid++;
p->q_lv = 0;
p->tq = 0;
p->priority = 3;
처음에 발상한 방식은 이러했다. L0 큐의 runnable한 프로세스가 없을 경우 L1을 스케줄링 해야하고, L1큐의 runnable한 프로세스가 없을 경우 L2를 스케줄링 해야한다는 것을 그대로 적용했다.
<aside> ⚙ 1. ptable을 0~63 모두 순회하면서 q_lv = 0인 프로세스를 찾는다. 2. 가장 앞에있는 q_lv = 0인 프로세스를 실행하고 tq와 q_lv등을 변경해준다. 3. ptable에 q_lv = 0인 프로세스가 없다면 이제 q_lv=1인 프로세스를 찾는 방식으로 1번부터 반복한다.
</aside>
물론, 당연히 이렇게 단순한 알고리즘으로 코드를 구성하고 스케줄러를 만드려고 하니 전혀 진척이 없었다. 우선 필요 이상으로 ptable을 많이 도는 경우가 발생했고, L1이나 L2 큐를 찾아보아야 하는 상황에 새로운 프로세스가 실행되어 L0에 프로세스가 들어온다던지 하는 예외를 처리하는 것이 만만치 않았으며, priority 계산을 하는 것도 쉽지 않았다. 그러다 문득 굳이 L0,1,2,3를 따로 찾아보아야할까..? 라는 생각이 들었다. ptable을 한 번 순회하는 것으로 지금 실행하고 싶은 프로세스를 찾을 수 있지 않을까? 즉, ptable을 한 바퀴 다 돌아 “ 지금 가장 우선적으로 처리해줘야할 프로세스를 고르자 “ 라는 방식으로 알고리즘을 구현하기로 했다.
<aside> ⚙ 1. running_p라고 하는 빈 proc 구조체를 선언해준다. 2. ptable을 순회하며 running_p를 가장 우선순위가 높은 process로 초기화 시킨다 → 큐의 레벨과 priority를 비교하여 running_p를 찾는다. / ex) q_lv이 0인 process가 q_lv이 1인 process보다 먼저 실행되어야한다. 3. running_p를 실행하고 나서 다시 ptable을 순회하며 우선순위가 가장 높은 process를 찾는다.
</aside>
원래는 for문을 돌면서 해당 q_lv와 일치하면 context switching을 발생시켜 일을 하고, 스케줄러로 돌아와서 다시 찾는 방식이었다면, 바뀐 방식에서는 우선 ptable을 모두 순회한 다음, ptable에서 가장 우선도가 높은 process를 for문에서 가지고 나와 context switching을 발생. 그리고 다시 포문으로 진입하는 방식으로 바꾸었다.
time interrupt가 발생하는 trap.c 파일을 좀 읽어보았는데 코드 위쪽에서 global ticks를 하나 더해주고 아래쪽에서 yield()를 해주는 형식을 띄고 있었다. yield함수는 결국 현재 프로세스가 cpu를 놓치고 스케줄러를 다시 호출하는 함수이므로, 이 아래쪽에서 타임 인터럽트 처리 후 스케줄러로 돌아간다는 사실을 이해했다. trap.c에 들어와 yield함수를 발생시켰다는 것은 time interrupt가 발생했다는 것이니까, 이 때 process의 tq와 q_lv, priority 등을 컨트롤해주면 편리하겠다 라는 생각이들었다. 그래서 yield 전에 time quantum을 눌려주고 그 늘어난 time quantum을 기준으로 q_lv을 바꿔주는 디자인을 하기로 했다. Priority의 경우에도 L2 에서 일을하다가 time quantum을 다 소모하면 priority를 올려주고 time quantum도 초기화 해주어야 하므로 여기서 처리해주는 것으로 디자인했다.