xv6-mlfq-scheduler

xv6의 기본 Round Robin 스케줄러를 분석하고, 실행 패턴 기반 동적 우선순위 조정이 가능한 Multi-Level Feedback Queue(MLFQ) 스케줄러로 확장 구현한 프로젝트

1. 프로젝트 개요

본 프로젝트는 xv6 커널 내부의 스케줄링 구조를 분석한 뒤,
기존의 단순 순회 기반 Round Robin 구조를 동적 우선순위 기반 MLFQ 구조로 재설계

단순히 큐를 추가하는 것이 아니라,
스케줄러의 의사결정 구조 자체를 재설계에 초점을 둠.

설계 목표

• 실행 패턴 추적 구조 설계
• tick 기반 런타임 데이터 수집
• 우선순위 결정 정책 수립
• Aging 메커니즘 도입
• 공정성과 응답성 사이의 균형 설계

이를 통해 커널 내부 스케줄링 정책을 상태 기반 의사결정 구조로 확장

---

2. 기존 xv6 스케줄러 구조 분석

MLFQ 구현에 앞서, 기존 xv6 스케줄링 흐름을 함수 단위로 분석

2.1 Process Table과 struct proc 구조

xv6는 모든 프로세스를 전역 구조체 ptable에서 관리

struct {
  struct spinlock lock;
  struct proc proc[NPROC];
} ptable;

각 프로세스는 struct proc에 의해 관리되며 6가지의 상태 중 하나를 가지게 됨.

• UNUSED
• EMBRYO
• SLEEPING
• RUNNABLE
• RUNNING
• ZOMBIE

스케줄러는 이 state 값을 기준으로 실행 여부를 판단 즉, 기존 xv6 스케줄링의 의사결정 기준 = "RUNNABLE 상태인가 아닌가"

---

2.2 scheduler() 동작 흐름

scheduler()는 무한 루프 구조로 동작

동작 과정

1. sti()를 통해 인터럽트 활성화
2. ptable.lock 획득
3. process table 선형 순회
4. RUNNABLE 프로세스 선택
5. 상태를 RUNNING으로 변경
6. swtch()를 통한 context switching
7. 실행 종료 후 scheduler로 복귀

특징

• 선형 탐색 구조
• 모든 프로세스 동일 time slice
• 정책 기반 선택이 아닌 순회 기반 선택

---

2.3 yield()와 sched()

yield()는 실행 중인 프로세스가 CPU를 양보할 때 호출됨.

• 현재 프로세스를 RUNNABLE 상태로 변경
• sched() 호출
• scheduler로 복귀

Timer interrupt 발생 시 강제로 yield()가 호출되어
선점형 Round Robin 스케줄링이 수행

공정성은 보장되지만,
프로세스의 실행 성향은 반영되지 않음.

---

2.4 trap()과 Timer Interrupt

trap()은 시스템 콜 및 인터럽트를 처리

Timer interrupt 발생 시:

• 전역 tick 증가
• 실행 중 프로세스 yield() 호출

그러나 프로세스별 실행 이력은 저장되지 않기 때문에 CPU-bound / I/O-bound 구분 불가

---

2.5 기존 구조의 한계

• 실행 패턴 추적 구조 부재
• 동적 우선순위 조정 불가
• Aging 메커니즘 없음
• 동일 조건에서 실행 순서 비결정성

위와 같은 한계점을 해결하기 위해 MLFQ 기반 구조로 확장하고자 함.

---

3. MLFQ 기반 확장 설계

3.1 struct proc 확장

실행 패턴 추적을 위해 다음 필드를 추가

• q_level : 현재 큐 레벨
• cpu_burst : 현재 time slice 사용량
• cpu_wait : RUNNABLE 상태 대기 시간
• io_wait_time : SLEEP 상태 대기 시간
• cpu_usage : 누적 CPU 사용량
• end_time : 실행 종료 기준 tick

정책 설계 이전에 데이터 추적 구조를 먼저 설계하고,
이를 정책 설계에 연결할 수 있도록 함.

---

3.2 4단계 큐 구조

Level	Time Quantum
0	10 ticks
1	20 ticks
2	40 ticks
3	80 ticks

• 낮은 레벨일수록 높은 우선순위
• CPU를 오래 사용하는 프로세스는 하위 큐 이동
• I/O가 많은 프로세스는 상위 큐 유지

---

3.3 우선순위 결정 정책

프로세스 선택 기준:

1. 낮은 q_level 우선
2. 동일 레벨 → io_wait_time 큰 프로세스 우선
3. 동일 조건 → cpu_wait 큰 프로세스 우선 (tie-break)

동일 조건에서의 실행 순서를 명확히 정의하여
결정성을 확보했습니다.

---

3.4 큐 이동 정책

• Time Quantum 초과 → 하위 큐 이동
• 동일 큐에서 250 tick 이상 대기 → 상위 큐 승격 (Aging)
• 최하위 큐는 강등 없음

Aging을 통해 starvation 문제를 해결했습니다.

---

3.5 Tick 기반 상태 갱신

Timer interrupt 발생 시 매 tick마다:

• RUNNING → cpu_burst++
• RUNNABLE → cpu_wait++
• SLEEPING → io_wait_time++

이 구조를 통해 실행 패턴 기반 스케줄링이 가능해졌습니다.

---

4. 구현 요약

• scheduler() 수정
• yield() 수정
• trap() 내 tick 갱신 로직 추가
• time_quantum() 함수 구현
• aging() 구현
• set_proc_info() 시스템 콜 추가

---

5. 테스트

• 단일 CPU 환경에서 실행
• debug 모드 로그 출력
• Time Quantum 초과 시 강등 확인
• 250 tick 이상 대기 시 승격 확인
• 다양한 end_time 값으로 동작 검증

---

6. 배운점

처음에는 MLFQ 구현을 단순히 큐를 여러 개 두는 문제라고 생각했다.
그러나 실제로 xv6 커널 코드를 분석하고 수정하면서,
스케줄러는 단순 반복문이 아니라 프로세스 상태를 기반으로 의사결정을 수행하는 정책 엔진이라는 것을 깨달았다.

특히 정책 설계 전에,
프로세스의 실행 패턴을 추적할 수 있는 데이터 구조가 먼저 설계되어야 한다는 점이 인상 깊었다.
q_level, cpu_wait, io_wait_time과 같은 필드를 추가하지 않았다면
어떤 정책도 의미 있게 동작할 수 없었다.

또한 작은 조건 하나가 전체 시스템 동작에 큰 영향을 준다는 것을 경험했다.
예를 들어, tie-break 기준을 변경하거나 aging 임계값을 조정하는 것만으로도
프로세스 실행 순서와 체감 응답성이 달라졌다.

이 과정에서 공정성과 응답성 사이에는 항상 trade-off가 존재한다는 것을 체감할 수 있었다.
모든 프로세스를 공평하게 처리하려 하면 응답성이 떨어질 수 있고,
응답성을 높이면 특정 프로세스가 오래 대기할 가능성이 생긴다. (starvation 상태)

운영체제 레벨에서 정책을 설계해본 경험은
이후 백엔드 시스템에서 요청 처리 흐름을 설계하거나
상태 기반 로직을 구현할 때도 동일하게 적용될 수 있는 관점을 제공했다.
단순 기능 구현을 넘어서, “어떤 기준으로 선택할 것인가”를 고민하는 경험이 되었다.

---

7. 실행 방법

7.1 Requirements

• Ubuntu / Linux 환경
• gcc
• qemu
• make

---

7.2 Build & Run

make clean
make qemu

# 단일 CPU 환경에서 디버그 모드로 실행할 경우
make clean
make qemu CPUS=1

---

8. 주요 구현 Snippets

8.1 struct proc 확장

// proc.h
int q_level;        // 현재 큐 레벨
int cpu_burst;      // 현재 타임슬라이스 사용량
int cpu_wait;       // RUNNABLE 상태 대기 시간
int io_wait_time;   // SLEEP 상태 대기 시간
int cpu_usage;      // 누적 CPU 사용량
int end_time;       // 종료 기준 tick

실행 패턴 기반 스케줄링을 위해
프로세스 단위의 상태 데이터 확장

---

8.2 scheduler() 내 우선순위 선택 로직

// proc.c
if(p->state != RUNNABLE)  
  continue;  

if(next_proc == 0) {  
  next_proc = p;  
}  
else if(p->q_level < next_proc->q_level) {  
  next_proc = p;  
}  
else if(next_proc->q_level == p->q_level) {  
  if(next_proc->io_wait_time < p->io_wait_time) {  
    next_proc = p;  
  }  
  else if(next_proc->io_wait_time == p->io_wait_time  
                      && next_proc->cpu_wait > p->cpu_wait) {  
    next_proc = p;  
  }  
}  

우선순위 결정 기준

• 낮은 q_level
• 높은 io_wait_time
• 높은 cpu_wait

동일 조건에서도 실행 순서를 명확하게 정의하여 결정성을 확보

---

8.3 Timer Interrupt 기반 tick 갱신

// trap.c
for(p = ptable.proc; p < &ptable.proc[NPROC]; p++) {  
  if (p && p->state == RUNNING) {  
    p->cpu_burst++;  
   }  
  else if(p && p->state == RUNNABLE) {

    // cpu_wait >= 250인 경우, 해당 프로세스 aging 수행  
    if(p->cpu_wait >= 250 && p->cpu_usage < p->end_time) {  
      aging(p);  
    }  
    p->cpu_wait++;  
  }  
  else if(p && p->state == SLEEPING) {  
    p->io_wait_time++;  
  }  
}  

Timer Interrupt마다 실행 패턴 데이터를 갱신하여
동적 우선순위 조정이 가능하도록 구현함.