[TIL/크래프톤 정글] DAY 65

배재준·2025년 5월 13일
8기Priority SchedulingTILThreadkrafton junglepintosthread lifecycleweek09기본 우선순위 스케줄링

크래프톤 정글 - TIL

목록 보기
58/93
post-thumbnail

2025.05.13

TIL(TODAY I LEARN)

  • 오늘한 내용 : PintOS - Project1: Threads - 기본 Priority Scheduling 구현 / 개념 - thread init, thread lifecycle, 우선순위 기부 양보 차이

  • WEEK 09 : 정글 끝까지(PintOS) - Threads

Priority Scheduling

항목작성 예시
Ready 리스트 정렬은 어떻게 하나요?list_insert_ordered()로 Ready 리스트 정렬
우선순위 변경 시 재정렬 필요 여부thread_set_priority() 호출 시 yield() 필요
새 스레드가 Ready 상태가 될 때 어떻게 하나요?thread_unblock()에서 정렬 삽입
어디서 수정해야 하나요?thread_unblock(), thread_yield(), schedule()
주의할 점은?같은 priority라면 round-robin 유지해야 함

구현 목표

  • Ready 상태의 스레드 중 우선순위가 가장 높은 스레드가 먼저 실행됨

설계

  • thread->priority 필드 사용
  • Ready list를 list_insert_ordered()로 정렬 삽입
  • 스레드가 unblock될 때 현재 실행 중인 스레드보다 우선순위 높으면 yield
  • thread_yield()에서 ready list의 가장 높은 priority 비교

수정 함수

  • thread_create()
  • thread_unblock()
  • thread_yield()
  • schedule(), next_thread_to_run()

테스트

테스트 이름의미
priority-change우선순위가 바뀔 때 스케줄러가 적절히 반응하는지
priority-preempt더 높은 우선순위 스레드가 나타나면 선점되는지 확인
priority-fifo같은 priority이면 FIFO 순서로 동작하는지

Bootstrapping & Idle 스레드 동작 흐름

부트스트랩 ── thread_init() ──┐
                             ↓
               초기 스레드 (BOOT) ─ thread_start() ─┐
                                                   ↓
                                            idle 스레드 생성
                                                   ↓
                              인터럽트 활성화 → 타이머 IRQ 발생
                                                   ↓
                                             schedule()
                                                   ├─ Ready 큐 비어 있으면 idle 실행 (hlt 루프)
                                                   └─ Ready 큐에 스레드 있으면 해당 스레드 실행
                                                   ↓
                                          thread_launch() → 실행

  1. thread_init() 단계

    • 락, 리스트 등 스레드 서브시스템 초기화
    • initial_thread 구조체로 Bootstrap(메인) 스레드 생성, 기본 상태 THREAD_RUNNING 설정

  2. thread_start() 단계

    1. struct semaphore idle_started; 선언 및 sema_init(&idle_started, 0); 호출
      • 초기 카운트 0
    2. idle 스레드 생성: thread_create("idle", PRI_MIN, idle, &idle_started);
      • 이 시점에 idle() 함수와 &idle_started가 스레드에 전달됨
    3. 인터럽트 활성화: intr_enable() 호출 → 타이머 인터럽트 수신 시작
    4. Bootstrap 블록: sema_down(&idle_started) 호출
      • 이때 idle() 스레드가 처음 실행되면 내부에서 sema_up(&idle_started)를 호출해 Bootstrap 스레드를 깨움

  3. intr_enable() 호출 → 타이머 인터럽트 수신 시작

    1. sema_down(&idle_started); 호출 → idle 스레드가 sema_up()을 호출할 때까지 Bootstrap 스레드 블록

  4. idle 스레드 초기 실행

    static void idle(void *idle_started_) {
  sema_up(idle_started_);   // Bootstrap 깨우기
  for (;;) {
    intr_disable();
    asm volatile ("hlt");  // CPU 절전 모드 진입
    intr_enable();
  }
}
    • sema_up()으로 Bootstrap 스레드 READY 복귀
    • 이후 레디 큐가 비어 있으면 idle만 선택되어 hlt 루프 실행

  5. 스케줄러 흐름 (schedule())

    • 레디 큐에서 우선순위 최고 스레드 선택
    • 레디 큐가 비면 idle 선택
    • thread_launch()로 컨텍스트 전환

  6. Bootstrap vs Idle 실행 조건

    • 친절한 설명
      • 다른 작업 스레드가 생기면 스케줄러가 그걸 우선 선택하니 idle은 전혀 실행되지 않음.
      • 작업 스레드가 하나도 없고, bootstrap 스레드가 동기화 대기 등으로 BLOCKED 될 때만 idle이 실행돼서 CPU를 절전 모드로 전환.
      • 타임슬라이스 만료로 인한 yield()는 BLOCKED가 아니라 READY 상태로 돌아가기 때문에, bootstrap이 다시 선택되고 idle은 여전히 대기 상태.
      • 결론적으로 idle은 “다음 실행 대상이 없거나 bootstrap이 BLOCKED 됐을 때” 안전망 역할을 하는 거고, 평소에는 bootstrap 스레드만 계속 돌게 됨.
    • 작업 스레드 존재: Bootstrap(또는 다른 READY 스레드)만 실행, idle은 선택되지 않음
    • 작업 스레드 부재: Bootstrap이 블록되거나 READY 큐가 완전 비면 idle이 실행
      • 부트스트랩 스레드가 BLOCKED 상태로 빠질 수 있는 경우들:
      1. thread_start() 안의 sema_down(&idle_started)
        • idle 스레드가 준비될 때까지 의도적으로 블록.
        • 이건 부트 시 딱 한 번 일어나는 동기화 용도.
      2. 동기화 대기
        • sema_down(), lock_acquire(), cond_wait() 같은 함수 호출 시 블록.
        • 예를 들어 부트스트랩이 I/O 초기화나 어떤 리소스 획득용 락을 기다리면 BLOCKED.
      3. 명시적 thread_block() 호출
        • 코드 어딘가에 부트스트랩이 직접 블록되도록 작성돼 있으면(잘 쓰이지 않지만 가능).
      4. 페이지 폴트 등 커널 예외 처리
        • 드물지만 유저 프로그램 디버그나 메모리 할당 과정에서 부트스트랩도 잠깐 BLOCKED 될 수 있음.
    • idle 실행 중 인터럽트로 깨어나면 다시 스케줄링

  7. 핵심 포인트

    • Bootstrap 스레드: 커널 초기화 및 주 실행 스레드
    • Idle 스레드: READY 큐 안전망, CPU 절전 루프 담당
    • 항상 READY 큐가 비지 않도록 설계되어 스케줄러 예외 방지

양보와 기부의 차이

양보는 실행중이더라도 우선순위가 높은 새로운 쓰레드가 생기면(언블럭이 되든, 새로운 쓰레드가 들어오든) 멈춰서 양보해준다?

기부는 임계영역에서 똑같은 자원을 사용해야되는데 우선순위 낮은애가 그거 락하고 있으면 먼저 락한 낮은 우선순위의 스레드가 그걸 다써야 풀어주는데 우선순위 높은 애가 빨리 쓰게하려고 낮은 애한테 우선순위 빌려줘서 락 빨리 풀게 하고 H를 쓰게 해준다?

  • 양보(yield)
    • 실행 중인 스레드라도 더 높은 우선순위 스레드가 준비(ready)되면 즉시 멈추고 CPU를 양보한다.
    • 준비 조건:
      • thread_unblock()로 깨워진 스레드의 우선순위가 현재 실행 중인 스레드보다 높을 때
      • thread_set_priority()로 우선순위를 낮춰서 READY 큐 맨 앞 스레드보다 낮아졌을 때
  • 우선순위 기부(donation)
    • 낮은 우선순위 스레드(L)가 락을 잡고 있을 때, 더 높은 우선순위 스레드(H)가 그 락을 기다리면
    • H의 우선순위를 L에게 임시로 “빌려줘서” L이 CPU를 빨리 얻어 락을 해제하게 만든다.
    • 락 해제 후에는 L이 원래 우선순위(또는 남은 기부 중 최고)로 돌아간다.

기본 우선순위 스케줄링

  • 목표: 준비 큐를 우선순위 순으로 정렬하고, 높은 우선순위 스레드에게 선점 보장
  • 수정 파일: threads/thread.c 및 threads/thread.h
    • thread.h
      • struct thread에 int priority, int base_priority, struct list donations, struct lock *waiting_lock 필드 추가
    • thread_unblock() / thread_yield() / thread_create() 등에서
      • list_insert_ordered(&ready_list, &t->elem, cmp_priority, NULL) 사용
    • next_thread_to_run()
      • ready_list.front에서 우선순위 높은 스레드 반환

함수 설명

  • thread_create() → thread_unblock() 호출
  • thread_unblock() → list_insert_ordered() + 양보 검사
  • thread_yield() → list_insert_ordered() + schedule()
  • schedule() → next_thread_to_run() → thread_launch()

수정한 함수

* thread.c

thread_unblock() - ready_list 삽입 시 ordered로 변환
	thread_unblock() - 끝부분 현재스레드와 삽입스레드 우선순위 비교
											/ 현재스레드가 idle이 아닐때 yield 진행
thread_yield() - ready_list 삽입 시 ordered로 변환
	thread_piroity_greater() 구현 - 내림차순

How?

  1. thread_unblock() & thread_yield() ← ready_list에 삽입할 때 정렬을 진행
	list_insert_ordered(&ready_list, &t->elem, thread_priority_greater, NULL);
  1. thread_unblock() 마지막에 우선순위 비교 및 현재 스레드 ≠ idle 일 때
if (thread_current() != idle_thread && t->priority > thread_get_priority())
	{
		if (intr_context())
			intr_yield_on_return();
		else
			thread_yield();
	}
profile
배재준
^_^
이전 포스트

[TIL/크래프톤 정글] DAY 64

다음 포스트

[TIL/크래프톤 정글] DAY 66

0개의 댓글