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

배재준·2025년 5월 10일

8기 TIL Thread gitbook krafton jungle pintos week09

크래프톤 정글 - TIL

목록 보기

55/93

2025.05.10

TIL(TODAY I LEARN)

오늘한 내용 : OS - gitbook1장 - Project1: Threads 정리
WEEK 09 : 정글 끝까지(PintOS) - Threads

KAIST CS330’s Pintos project

과제 할일 요약

Project 1: Threads 과제 요약

1. 알람 시계(Alarm Clock)

목표: timer_sleep()을 busy‐wait 대신 블록/언블록 방식으로 재구현
수정 파일: devices/timer.c
- void timer_sleep(int64_t ticks)
  - 슬립 리스트에 (wake_tick, cur_thread) 추가 후 thread_block()
- timer_interrupt()
  - 매 틱마다 current_ticks++ → 슬립 리스트 순회 → 기상 시점 도달 스레드 thread_unblock()

2. 기본 우선순위 스케줄링

목표: 준비 큐를 우선순위 순으로 정렬하고, 높은 우선순위 스레드에게 선점 보장
수정 파일: 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에서 우선순위 높은 스레드 반환

3. 우선순위 기부(Priority Donation)

목표: 우선순위 역전 상황에서 락 보유 스레드에 일시 기부
수정 파일: threads/synch.c (lock_acquire(), lock_release())
- lock_acquire()
  1. 대기 중인 락의 holder가 있으면
    - cur->waiting_lock = lock
    - donate_priority(cur, lock->holder) (재귀적 중첩 기부 허용)
- lock_release()
  1. sema_up(&lock->semaphore)
  2. 해당 락 관련 기부자 제거 (remove_donations_for_lock())
  3. current_thread->priority = max(base_priority, highest_donation())

4. 우선순위 조정 API

수정 파일: threads/thread.c
- void thread_set_priority(int new_priority)
  - cur->base_priority = new_priority → refresh_priority(cur) → 양보 조건 시 thread_yield()
- int thread_get_priority(void)
  - return current_thread->priority;

5. 고급 스케줄러(Optional, `mlfqs` 모드)

목표: 4.4BSD MLFQ 스케줄러 구현 (선택 과제)
수정 파일: threads/thread.c, threads/thread.h, devices/timer.c
- thread_mlfqs 옵션 분기
- thread_get_nice() / thread_set_nice(int)
- thread_get_recent_cpu() / thread_get_load_avg()
- recent_cpu, load_avg 갱신 로직 (timer_interrupt(), 1초·4틱 주기)
- priority 계산 공식 반영 (update_priority())

전체 플로우

타이머 인터럽트: timer_interrupt() → 슬립 처리 + recent_cpu++ + load_avg/recent_cpu/priority 갱신
락/세마포어/조건 변수: 동기화 객체 내부 대기열 관리 + 우선순위 기부
스케줄러: schedule() → next_thread_to_run() → 우선순위 기반 문맥 전환

이 네 단계와 주요 함수들을 중심으로 수정·확장하면 Project 1 요구사항을 모두 충족할 수 있습니다.

소스 트리 개요

원문 해석
- threads/: 프로젝트 1부터 수정할 기본 커널 소스 코드이다.
- userprog/: 프로젝트 2부터 수정할 사용자 프로그램 로더 소스 코드이다.
- vm/: 거의 비어 있는 디렉터리이다. 프로젝트 3에서 가상 메모리를 구현하는 곳이다.
- filesys/: 기본 파일 시스템 소스 코드이다. 프로젝트 2부터 사용하지만 프로젝트 4 전까지는 수정하지 않는다.
- devices/: 키보드, 타이머, 디스크 등의 I/O 장치 인터페이스 소스 코드이다. 프로젝트 1에서 타이머 구현만 수정하면 된다.
- lib/: 표준 C 라이브러리의 하위 집합을 구현한 디렉터리이다. 커널과 사용자 프로그램 모두에 컴파일된다.
- include/lib/kernel/: 커널 전용 C 라이브러리 일부가 포함된 디렉터리이다. 비트맵, 이중 연결 리스트, 해시 테이블 등의 구현이 포함된다.
- include/lib/user/: 사용자 프로그램 전용 C 라이브러리 일부가 포함된 디렉터리이다.
- tests/: 각 프로젝트 테스트 코드가 위치한 디렉터리이다. 테스트 실행 전에는 원본으로 복원된다.
- examples/: 프로젝트 2부터 참조할 예제 사용자 프로그램 모음이다.
- include/: 헤더 파일(.h) 소스 코드가 위치한 디렉터리이다.

프로젝트 1

threads/: 프로젝트 1부터 수정할 기본 커널 소스 코드이다.
devices/: 키보드, 타이머, 디스크 등의 I/O 장치 인터페이스 소스 코드이다. 프로젝트 1에서 타이머 구현만 수정하면 된다.
tests/: 프로젝트 1 테스트 코드가 위치한 디렉터리이다. 테스트 실행 전에는 원본으로 복원된다.

프로젝트 2

userprog/: 프로젝트 2부터 수정할 사용자 프로그램 로더 소스 코드이다.
filesys/: 프로젝트 2부터 사용하는 기본 파일 시스템 소스 코드이다. (프로젝트 4 전까지는 수정하지 않는다)
examples/: 프로젝트 2부터 참조할 예제 사용자 프로그램 모음이다.
`tests/:` 프로젝트 2 테스트 코드가 위치한 디렉터리이다. 테스트 실행 전에는 원본으로 복원된다.

프로젝트 3

vm/: 프로젝트 3에서 가상 메모리를 구현할 거의 비어 있는 디렉터리이다.
tests/: 프로젝트 3 테스트 코드가 위치한 디렉터리이다. 테스트 실행 전에는 원본으로 복원된다.

프로젝트 4

filesys/: 프로젝트 4에서 수정할 파일 시스템 소스 코드이다.
tests/: 프로젝트 4 테스트 코드가 위치한 디렉터리이다. 테스트 실행 전에는 원본으로 복원된다.

공통 라이브러리 및 헤더

lib/: 표준 C 라이브러리의 하위 집합을 구현한 디렉터리이다. 커널과 사용자 프로그램 모두에 컴파일된다.
include/lib/kernel/: 커널 전용 C 라이브러리 일부가 포함된 디렉터리이다. 비트맵, 이중 연결 리스트, 해시 테이블 등의 구현이 포함된다.
include/lib/user/: 사용자 프로그램 전용 C 라이브러리 일부가 포함된 디렉터리이다.
include/: 헤더 파일(.h) 소스 코드가 위치한 디렉터리이다.

Project1: Threads

동기화(synchronization) 먼저 읽고 오기

Understanding Threads

1. 초기 스레드 시스템 구성 요소

스레드 생성/종료: thread_create() → 스레드 함수 실행 → 함수 반환 시 자동 종료
스케줄러: 여러 스레드 간 문맥 전환 (선점형/타이머 인터럽트, thread_yield(), 동기화 블록)
동기화 원시: 세마포어, 락, 조건 변수, 최적화 배리어

2. `thread_create()` 동작 흐름

새 문맥(context) 생성
함수 포인터 등록 (스레드 “main” 역할)
준비 큐(runnable) 등록

3. 스레드 실행과 종료

최초 실행
- 스케줄러가 실행할 스레드를 선택 → thread_launch() 호출 → 함수 시작 지점으로 점프
함수 반환 시
- 스레드 자동 종료(cleanup) → 리소스 해제

4. 문맥 전환 발생 시점

타이머 인터럽트 (선점형 커널)
동기화 블록 (sema_down(), lock_acquire() 등 블록 시)
명시적 양보 (thread_yield() 호출시)
Idle 스레드: 준비 큐가 비어있으면 idle() 스레드 실행

5. 문맥 전환 내부 메커니즘

thread_launch()
1. 현재 스레드 레지스터·스택 상태 저장
2. 다음 스레드 상태 복원
3. iret 실행 → 새로운 스레드로 제어 이동

6. GDB 디버깅

break schedule
step 로 한 단계씩 추적
각 스레드의 struct thread 주소·상태 확인
do_iret() 이후 다른 스레드가 실행됨 관찰

7. 스택 크기 주의

커널 스택 크기: 약 4 KB 고정
주의: 큰 로컬 배열(int buf[1000];) 사용 시 오버플로우 가능
대안:
- 페이지 할당기(palloc)
- 블록 할당기(malloc)

정리

기본 스레드 프레임워크를 컴파일·실행하며 thread_create()→thread_launch() 흐름 파악
문맥 전환은 thread_launch(), 타이머 인터럽트, 동기화 블록, thread_yield()에서 발생
GDB로 스레드 전환 과정을 단일 단계로 디버깅
커널 스택 오버플로우 방지를 위해 큰 데이터는 힙에 할당

Source Files Overview

1. threads 디렉터리

loader.S / loader.h
- 512바이트 부트스트랩 로더. PC BIOS가 메모리에 넣고 bootstrap()으로 진입. (수정 불필요)
start.S
- 64비트 롱 모드 전환 및 초기화 코드. 커널 일부.
kernel.lds.S
- 링커 스크립트. 커널 로드 주소 및 start.S 위치 지정.
init.c / init.h
- 커널 초기화(main()) 코드. 초기화 순서 확인 및 추가 코드 삽입 가능.
thread.c / thread.h
- 스레드 생성·종료, 스케줄러, 문맥 전환 구현. struct thread 정의.
palloc.c / palloc.h
- 4 KB 페이지 단위 메모리 할당기.
malloc.c / malloc.h
- 커널용 간단 malloc()/free() 구현.
interrupt.c / interrupt.h
- 인터럽트 등록·처리 및 intr_enable()/intr_disable() 함수.
intr-stubs.S / intr-stubs.h
- 저수준 인터럽트 스텁(어셈블리).
synch.c / synch.h
- 세마포어, 락, 조건 변수, 최적화 배리어 등 동기화 원시.
mmu.c / mmu.h
- x86-64 페이지 테이블 조작 함수.
io.h
- I/O 포트 접근 함수.
vaddr.h / pte.h
- 가상 주소, 페이지 테이블 엔트리 매크로.
flags.h
- x86-64 플래그 레지스터 비트 매크로.

2. devices 디렉터리

timer.c / timer.h
- 시스템 타이머(기본 100 Hz). Project 1 알람 시계 구현 대상.
vga.c / vga.h
- VGA 텍스트 드라이버 (printf() 사용).
serial.c / serial.h
- 시리얼 포트 드라이버 (printf() 사용).
block.c / block.h
- 블록 장치 추상화(IDE 디스크, 파티션). Project 2부터 사용.
ide.c / ide.h
- 최대 4개의 IDE 디스크 섹터 읽기/쓰기.
partition.c / partition.h
- 디스크 파티션 구조 분석.
kbd.c / kbd.h, input.c / input.h, intq.c / intq.h
- 키보드/시리얼 입력 큐 처리.
rtc.c / rtc.h
- 실시간 시계 드라이버(난수 시드용).
speaker.c / speaker.h
- PC 스피커 음성 출력.
pit.c / pit.h
- 8254 Programmable Interrupt Timer 설정.

3. lib 및 lib/kernel 디렉터리

표준 C 라이브러리
- ctype.h, inttypes.h, limits.h, stdarg.h, stdbool.h,stddef.h, stdint.h, stdio.c/.h, stdlib.c/.h, string.c/.h
debug.c / debug.h
- 디버깅 유틸리티 함수·매크로.
random.c / random.h
- 결정론적 의사 난수 생성기.
round.h
- 반올림 매크로.
syscall-nr.h
- 시스템 호출 번호 정의 (Project 2부터 사용).
kernel/list.c / list.h
- 이중 연결 리스트 구현.
kernel/bitmap.c / bitmap.h
- 비트맵 자료구조 구현.
kernel/hash.c / hash.h
- 해시 테이블 구현 (Project 3 유용).
kernel/console.c / console.h / stdio.h
- printf() 등 콘솔 출력 구현.

작업해야할 주요 파일

threads/thread.c
- 스레드 구조체(struct thread)에 새 필드를 추가하고, 스케줄러(schedule(), next_thread_to_run())를 확장합니다.
- 문맥 전환 코드(thread_launch())는 그대로 두되, 우선순위나 MLFQS 같은 고급 스케줄링 기능을 여기에 구현합니다.
- 스레드 생성·종료 로직(thread_create(), thread_exit())도 필요에 따라 수정합니다.
threads/thread.h
- struct thread에 우선순위, 티켓, 계층별 큐 포인터 등 프로젝트 요구사항에 맞는 필드를 선언합니다.
- API 사양(우선순위 getter/setter 등)을 맞추기 위해 함수 프로토타입을 추가·변경합니다.
devices/timer.c
- timer_sleep(int64_t ticks) 구현을 busy-wait에서 슬립 리스트+인터럽트 방식으로 바꿉니다.
- timer_interrupt() 핸들러에 “깨어날 스레드 체크 → thread_unblock()” 로직을 추가합니다.
(선택) threads/synch.c / synch.h
- 기본 세마포어·락·조건 변수는 이미 구현되어 있지만, 필요하다면 우선순위 기부(priority donation) 같은 확장 기능을 여기에 넣을 수도 있습니다.
(부수적) threads/interrupt.c
- 스레드와 타이머 인터럽트 간 데이터 공유를 위해, intr_disable()/intr_enable() 범위를 조절해야 할 수 있습니다.

요약

작업 내용	수정 파일
스레드 구조체·스케줄러 확장	`threads/thread.cthreads/thread.h`
`timer_sleep()` 재구현	`devices/timer.c`
조건부 우선순위 기부 등 동기화 확장	`threads/synch.c` / `synch.h` (선택)
(필요 시) 인터럽트 동기화 범위 조정	`threads/interrupt.c`

gpt 추천 구현 순서

기본 환경 점검
- threads/ 디렉터리에서 make → pintos run alarm-multiple 실행
- 기본 스레드 생성·종료, 스케줄러, 동기화 원시가 동작하는지 확인
스레드 구조체와 스케줄러 살펴보기
- threads/thread.h 의 struct thread
- threads/thread.c 의 thread_init(), schedule(), next_thread_to_run() 읽기
- GDB로 schedule()에 breakpoint 걸고 문맥 전환 흐름 파악
Alarm Clock (timer_sleep) 재구현
- devices/timer.c 에서 timer_sleep() 을 슬립 리스트 + timer_interrupt() 내 thread_unblock() 방식으로 교체
- timer_msleep/usleep/nsleep() 은 건드리지 않아도 자동 호출됨
우선순위 필드 추가 및 초기화
- struct thread 에 int priority 필드 추가
- thread_create() 와 thread_init() 에서 기본 우선순위(예: PRI_DEFAULT) 설정
준비 큐 우선순위 순 정렬
- next_thread_to_run() 또는 schedule() 에서 ready list 를 우선순위 비교 함수로 뽑아오도록 수정
- thread_yield(), thread_unblock() 등에서 리스트 삽입 시 list_insert_ordered() 사용
Lock에 우선순위 기부(priority donation) 적용
- threads/synch.c 의 lock_acquire()/lock_release() 에 다음 로직 추가
  1. 낮은 우선순위 스레드가 락을 쥐고 있을 때, 높은 우선순위 대기 스레드가 기부
  2. 락 해제 후에는 기부된 우선순위를 복원
동기화 테스트와 디버깅
- threads 디렉터리에서 make check → 실패한 테스트 확인
- threads/alarm-priority, threads/priority-donate 등 관련 테스트 집중 실행
코드 정리 및 최종 검토
- 불필요한 printf() 또는 디버깅용 인터럽트 비활성화 제거
- 스택 오버플로우 유발 여지를 점검
- 주석과 문서 보강
아카이브 생성 및 제출
```
cd threads
TEAM=<번호> make archive
```
- 생성된 team<번호>.tar.gz 파일을 제출

Synchronization

1. 기본 원칙

인터럽트 비활성화만으로는 경쟁 조건을 막을 수 있지만, 전체 동기화를 이 방법에만 의존하지 말 것
대신 세마포어, 락, 조건 변수 같은 동기화 원시(primitive)를 사용해 대부분의 문제를 해결

2. 인터럽트 비활성화가 필요한 경우

커널 스레드 ↔ 인터럽트 핸들러 간 데이터 공유
- 인터럽트 핸들러는 잠들(sleep) 수 없으므로 락을 사용할 수 없음
- 따라서 커널 스레드 쪽에서 짧은 범위로 인터럽트를 껐다 켜서 보호해야 함

3. 유의사항

필요 최소 범위에서만 인터럽트를 비활성화
- 지나치게 길면 타이머 틱이나 입출력 이벤트를 놓치고 시스템 반응성이 떨어짐
디버깅 용도로도 인터럽트 차단 사용 가능하나, 제출 전 모두 제거(주석 처리 금지)

4. 동기화 원시 구현

threads/synch.c 내부에서 이미 인터럽트 비활성화를 이용해 원자성(atomicity)을 보장
필요하다면 비활성화 구간을 최소로 확장하여 사용하되, 과도한 차단은 피할 것

5. 금지 사항

busy waiting 금지
- while (...) thread_yield(); 같은 루프는 CPU 낭비
- 반드시 블록 가능한 동기화 기법을 사용할 것

요약

세마포어·락·조건 변수를 우선 사용
커널 스레드↔인터럽트 핸들러 공유 시에만 인터럽트 비활성화
최소 범위 차단, 디버깅 코드 제거
busy waiting 절대 금지

Development Suggestions

Early and Frequent Integration

과제를 여러 조각으로 나누어 마지막에 합치는 방식은 비추천
충돌 발생 시 막바지 디버깅 과부하 유발
코드가 컴파일되지 않거나 부팅되지 않을 위험

Version Control 활용

Git 등 소스 관리 도구 사용
팀원 전체가 실시간으로 변경사항을 확인·공유
코드 리뷰를 통해 버그 발행 시점 빠르게 파악 및 복원

디버깅 도구 적극 활용

“Debugging Tools” 부록과 Backtraces 섹션 재검토
커널 패닉이나 assertion 실패 시 유용한 정보 확보

Mindset

복잡한 버그는 언제든 발생할 수 있음을 인지
“읽기 → 시도 → 디버깅 → 재검토” 과정을 반복하며 문제 해결 능력 강화

Alarm Clock (devices/timer.c)

목적

timer_sleep(int64_t ticks)
- 호출한 스레드를 최소 ticks 타이머 틱만큼 대기시킨다.
- 정확히 그 순간에 깨울 필요는 없으며, 대기 시간이 지난 뒤 준비 큐(ready queue) 에 넣어 스케줄러가 다시 실행하도록 한다.
- 단위는 타이머 틱(default 초당 100회, TIMER_FREQ).

기본(제공) 구현 문제점

busy waiting

void timer_sleep(int64_t ticks) {
  int64_t start = timer_ticks();
  while (timer_ticks() < start + ticks)
    thread_yield();
}

개선 방안

원래 `timer_sleep()` 동작 방식

스레드가 루프를 돌며 매 틱마다 자신 차례가 오면
1. timer_ticks()로 현재 틱 수를 읽고
2. 목표 틱에 도달했는지 비교
3. 아직 미도달이면 thread_yield()로 CPU를 양보
단점: 대기 중인 스레드가 계속 깨어나 검사하므로 CPU 낭비가 심함

개선된 동작 방식

슬립 리스트에 (wake_tick, 스레드)를 등록 후 thread_block()
타이머 인터럽트 핸들러에서만
- current_tick 증가 직후
- 슬립 리스트를 순회하며 wake_tick ≤ current_tick인 스레드를 thread_unblock()
깨어난 스레드는 준비 큐에서 다시 스케줄 대기

핵심 차이

원래: 각 스레드가 스스로 매 틱 검사 → 계속 깨어나 문맥 전환
개선: 인터럽트 핸들러가 한 번 리스트 검사 → 깨어날 스레드만 선별 → 나머지 스레드는 블록 상태로 CPU 전혀 사용 안 함

정리

개선된 방식은 검사 주체를 중앙집중화해 불필요한 검사와 문맥 전환을 제거
wake_up_tick 라는 추가 변수를 기준으로 시간이 되었는지를 슬립 리스트 안에서 조건 검사하는 방식
결과적으로 CPU 부하와 오버헤드를 크게 줄인다

Priority Scheduling & Priority Donation

1. 우선순위 스케줄링 구현

준비 큐(ready list)
- 새로운 스레드가 준비 큐에 추가될 때,
  - 현재 실행 중인 스레드보다 우선순위가 높으면 즉시 양보thread_yield()
블록 → 준비 큐 복귀
- 락·세마포어·조건변수 대기열에서 깨어날 때도 가장 높은 우선순위 스레드를 먼저 thread_unblock()
우선순위 조정 시
- 스레드가 자신의 우선순위를 낮추면, 더 높은 우선순위 스레드가 준비 큐에 있으면 즉시 양보
우선순위 범위
- PRI_MIN (0) ~ PRI_MAX (63)
- 기본값: PRI_DEFAULT (31)

2. 우선순위 기부 (Priority Donation)

문제: 우선순위 역전(priority inversion)
- H(높음) → L(낮음) 보유 락 대기 → M(중간) 실행 지속 → H 굶주림
- 낮은 우선순위(L) 스레드가 락을 먼저 획득하고 임계영역에서 실행 중
- 높은 우선순위(H) 스레드가 같은 락을 요청 → L이 락 해제할 때까지 블록
- 이 상태 그대로라면, 스케줄러는 계속해서 다른 준비 스레드를 돌려가며 L에게 CPU를 주지 않으므로 H는 영원히 대기
해결: 기부 메커니즘
1. H가 L의 락을 기다리면, H의 우선순위를 L에게 일시 기부
2. L이 락을 해제할 때 기부 회수 및 우선순위 복원
추가 요구사항
- 다중 기부: 여러 스레드가 동일 대상에 기부
- 중첩 기부: H→M→L 락 체인에서는 모두 H의 우선순위로 상승
- 깊이 제한: 합리적 최대 단계(예: 8단계) 허용

3. 우선순위 관련 함수

void thread_set_priority(int new_priority);
// 현재 스레드 우선순위 설정
// 더 이상 최고가 아니면 즉시 yield

int thread_get_priority(void);
// 기부 포함된 실제 우선순위 반환

Advanced Scheduler (4.4BSD MLFQ)

고급 스케줄러(Advanced Scheduler) 원문 해석

시스템에서 실행되는 작업들의 평균 응답 시간을 줄이기 위해, 4.4BSD 스케줄러와 유사한 다단계 피드백 큐 스케줄러를 구현하라.

우선순위 스케줄러와 마찬가지로, 고급 스케줄러도 스레드 우선순위를 기준으로 실행 대상을 결정한다. 다만, 우선순위 기부(priority donation) 기능은 포함하지 않는다.

코드 작성 시 부팅 시점에 스케줄링 정책을 선택할 수 있도록 해야 한다. 기본값은 우선순위 스케줄러가 동작하지만, -mlfqs 옵션을 주면 4.4BSD 스타일 고급 스케줄러가 대신 동작해야 한다.

mlfqs 모드에서는 스레드가 스스로 우선순위를 설정하거나 thread_set_priority()를 호출해도 무시된다. 대신 스케줄러가 nice 값과 recent_cpu를 기반으로 동적으로 우선순위를 계산한다.

1. 왜 고급 스케줄러인가?

목표:
- CPU 바운드(계산 위주) 스레드와 I/O 바운드(입출력 위주) 스레드는 서로 다른 요구를 가진다.
- 계산 위주 스레드는 긴 CPU 할당이 필요하고,
- 입출력 위주 스레드는 반응 속도가 중요하지만 CPU 점유 시간은 짧아도 된다.
단일 스케줄링 정책으로 이 둘을 모두 만족시키기 어려우니,
스레드 특성에 따라 우선순위를 동적으로 조정하는 방식이 필요하다.

2. 다단계 피드백 큐(MLFQ)란?

여러 개의 준비 큐(ready queue)를 우선순위 별로 만든다.
- 큐 0: 가장 낮은 우선순위
- …
- 큐 63: 가장 높은 우선순위
실행할 스레드는 항상 가장 높은(숫자가 큰) 비어 있지 않은 큐에서 꺼낸다.
한 큐 안에 여러 스레드가 있다면 라운드 로빈 방식으로 차례차례 실행.

3. 동작 흐름

매 타이머 틱
- 실행 중인 스레드의 recent_cpu를 1 증가시킨다.
매 1초 (timer_ticks() % TIMER_FREQ == 0)
- 모든 스레드의 recent_cpu를 지수 가중 이동 평균으로 갱신
- load_avg(시스템 부하 평균)를 갱신

매 4틱 또는 필요할 때

각 스레드 우선순위를
공식으로 재계산

```markdown
priority = PRI_MAX - (recent_cpu/4) - (nice*2)

recent_cpu = (2load_avg)/(2load_avg + 1) * recent_cpu + nice

load_avg = (59/60)*load_avg + (1/60)*ready_threads

- 정수만 지원 → **17.14 고정소수점** 사용
- 곱셈: `((int64_t)x*y)/f`, 나눗셈: `((int64_t)x*f)/y`
```

스케줄러 호출
- 위 64개 큐 중 가장 높은 큐에서 실행할 스레드를 선택

4. 구성 요소

nice (–20~20)
- “친절도”를 나타내는 값
- 크면(더 ‘친절’하면) 우선순위가 더 낮아져 다른 스레드에게 양보
recent_cpu
- 스레드가 최근 얼마나 CPU를 썼는지 추정
- 많이 쓰면 다음 차례 우선순위가 낮아짐
load_avg
- 지난 1분간 평균 준비 스레드 수
- 시스템 전체의 부하 상태 반영

항목	빈도	시점
recent_cpu	매 틱(실행 스레드)	timer interrupt
recent_cpu	1초마다	`timer_ticks() % TIMER_FREQ == 0`
load_avg	1초마다	`timer_ticks() % TIMER_FREQ == 0`
priority	매 4틱 또는 1초마다	recent_cpu / nice 변경 시

이렇게 구현하면,

CPU를 많이 쓴 스레드는 잠시 우선순위를 낮춰 다른 스레드에 기회를 주고,
입출력 대기 후 깨어난 스레드는 우선순위를 올려 빠른 반응을 유지하며,
시스템 전반의 공정성과 반응성을 모두 잡을 수 있습니다.

5. 구현 포인트

thread_get_nice(), thread_set_nice()
thread_get_recent_cpu(), thread_get_load_avg()
우선순위 재계산 로직 삽입 (thread_tick(), thread_update_priority())
mlfqs 플래그에 따라 스케줄러 분기 처리

Arithmetic	C
Convert `n` to fixed point	`n * f`
Convert `x` to integer (rounding toward zero)	`x / f`
Convert `x` to integer (rounding to nearest)	`(x + f / 2) / f` if `x >= 0`
	`(x - f / 2) / f` if `x <= 0`
Add `x` and `y`	`x + y`
Subtract `y` from `x`	`x - y`
Add `x` and `n`	`x + n * f`
Subtract `n` from `x`	`x - n * f`
Multiply `x` by `y`	`((int64_t) x) * y / f`
Multiply `x` by `n`	`x * n`
Divide `x` by `y`	`((int64_t) x) * f / y`
Divide `x` by `n`	`x / n`

FAQ

1. 얼마나 많은 코드를 작성해야 하나요?

레퍼런스 솔루션: 6개 파일, 330행 삽입/12행 삭제
- devices/timer.c (29행)
- include/threads/fixed-point.h (10행, 새 파일)
- include/threads/synch.h (4행)
- include/threads/thread.h (21행)
- threads/synch.c (143행)
- threads/thread.c (135행)

2. 새 소스 파일 추가 시 Makefile 업데이트 방법은?

해당 서브디렉터리의 targets.mk 에 .c 파일을 dir_SRC 변수에 추가
헤더 파일(.h)은 Makefile 수정 불필요

3. `warning: no previous prototype for func` 경고는?

비-정적 함수가 헤더에 프로토타입 없이 정의되었음
해결: 헤더에 함수를 선언하거나, 외부에서 사용하지 않으면 static으로 변경

4. 타이머 인터럽트 간격은?

TIMER_FREQ 번/초 (기본 100Hz, devices/timer.h)

5. 타임 슬라이스 길이는?

TIME_SLICE 틱/슬라이스 (기본 4, threads/thread.c)

6. 테스트 실행 방법은?

make 후 pintos run <test-name> 또는 make check 참조
테스트 실행 방법
1. 전체 테스트 한 번에 돌리기
```
cd threads
make check
```
  - threads/ 디렉터리에서 make check를 실행하면 제공된 모든 테스트가 순차적으로 실행됩니다.
2. 개별 테스트 실행하기
```
pintos -- run <test-name>
```
  예를 들어
```
pintos -- run alarm-priority
pintos -- run priority-sema
```
  처럼 원하는 테스트 이름을 지정해서 돌릴 수 있습니다.
3. 결과 확인
  - make check나 개별 pintos run 명령 후 출력되는 로그를 보고, 실패한 테스트 이름과 백트레이스를 확인하세요.
  
  참고: 테스트 이름은 threads/tests/ 디렉터리 안에 있는 소스 파일 이름과 대응됩니다.

7. `pass()` 테스트 실패 시 백트레이스 혼동?

실제로는 fail() → debug_panic() 호출
debug_panic()은 NO_RETURN, 복귀 코드가 없어 백트레이스가 옆 함수를 가리킴

8. `schedule()` 후 인터럽트 재활성화 시점은?

새 스레드가 첫 실행 시 intr_enable() 호출
나머지는 thread_yield(), sema_down(), idle() 등 경로에서 복원

9. 타이머 값 오버플로우에 신경 써야 하나요?

64비트 signed 값, 100Hz 기준 약 2.9억 년 후에야 오버플로우 → 걱정 불필요

10. 우선순위 스케줄링이 기아(starvation)를 초래하나요?

예, 엄격한 우선순위는 기아 가능
고급 스케줄러(MLFQS)는 동적 우선순위 조정으로 완화

11. 락 해제 후 어떤 스레드를 실행하나요?

해당 락 대기열에서 가장 높은 우선순위 스레드를 깨워 준비 큐로 이동

12. 최고 우선순위 스레드가 `yield()`하면?

같은 우선순위가 여러 개면 라운드로빈
단일 최고 우선순위면 계속 실행

13. 기부한 스레드의 우선순위는 어떻게 변하나요?

기부자는 변경 없음
수혜자 우선순위는 기부한 값 중 최대값

14. 준비 큐에 있는 스레드 우선순위가 변할 수 있나요?

예, 락 기부로 인해 thread_unblock() 후 우선순위 상승 가능

15. 블록된 스레드 우선순위 변할 수 있나요?

예, 락 보유 중 대기 스레드가 기부하면 블록 상태 스레드 우선순위 상승

16. 준비 큐에 추가된 스레드가 즉시 선점하나요?

네, 즉시 thread_yield() 호출로 선점해야 함

17. `thread_set_priority()`와 기부 상호작용은?

base_priority를 설정하고 priority = max(base_priority, donated_max)
기부 해제 후에는 base_priority로 복원

18. 출력이 두 번씩 겹치는 이유는?

두 스레드가 거의 동시에 printf() 호출 → 출력이 중첩
우선순위 스케줄러 버그 시그널

19. 기부와 고급 스케줄러는 함께 동작하나요?

테스트되지 않음. 동시 구현 불필요

20. 64개 큐 대신 하나의 자료구조 사용 가능?

네, 동작만 같으면 구현 방식은 자유

추가 테스트 실패 시

실패한 테스트 소스 확인

고정소수점 연산(overflow) 점검

타이머 인터럽트 핸들러 과부하 여부 확인

배재준

^_^

이전 포스트

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

다음 포스트

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

크래프톤 정글 - TIL

TIL(TODAY I LEARN)

KAIST CS330’s Pintos project

과제 할일 요약

Project 1: Threads 과제 요약

1. 알람 시계(Alarm Clock)

2. 기본 우선순위 스케줄링

3. 우선순위 기부(Priority Donation)

4. 우선순위 조정 API

5. 고급 스케줄러(Optional, mlfqs 모드)

전체 플로우

소스 트리 개요

프로젝트 1

프로젝트 2

프로젝트 3

프로젝트 4

공통 라이브러리 및 헤더

Project1: Threads

Understanding Threads

1. 초기 스레드 시스템 구성 요소

2. thread_create() 동작 흐름

3. 스레드 실행과 종료

4. 문맥 전환 발생 시점

5. 문맥 전환 내부 메커니즘

6. GDB 디버깅

7. 스택 크기 주의

정리

Source Files Overview

1. threads 디렉터리

2. devices 디렉터리

3. lib 및 lib/kernel 디렉터리

작업해야할 주요 파일

요약

gpt 추천 구현 순서

Synchronization

1. 기본 원칙

2. 인터럽트 비활성화가 필요한 경우

3. 유의사항

4. 동기화 원시 구현

5. 금지 사항

Development Suggestions

Early and Frequent Integration

Version Control 활용

디버깅 도구 적극 활용

Mindset

Alarm Clock (devices/timer.c)

목적

기본(제공) 구현 문제점

개선 방안

원래 timer_sleep() 동작 방식

개선된 동작 방식

핵심 차이

정리

Priority Scheduling & Priority Donation

1. 우선순위 스케줄링 구현

2. 우선순위 기부 (Priority Donation)

3. 우선순위 관련 함수

Advanced Scheduler (4.4BSD MLFQ)

고급 스케줄러(Advanced Scheduler) 원문 해석

1. 왜 고급 스케줄러인가?

2. 다단계 피드백 큐(MLFQ)란?

3. 동작 흐름

4. 구성 요소

5. 구현 포인트

FAQ

1. 얼마나 많은 코드를 작성해야 하나요?

2. 새 소스 파일 추가 시 Makefile 업데이트 방법은?

3. warning: no previous prototype for func 경고는?

4. 타이머 인터럽트 간격은?

5. 타임 슬라이스 길이는?

6. 테스트 실행 방법은?

7. pass() 테스트 실패 시 백트레이스 혼동?

8. schedule() 후 인터럽트 재활성화 시점은?

9. 타이머 값 오버플로우에 신경 써야 하나요?

10. 우선순위 스케줄링이 기아(starvation)를 초래하나요?

11. 락 해제 후 어떤 스레드를 실행하나요?

12. 최고 우선순위 스레드가 yield()하면?

13. 기부한 스레드의 우선순위는 어떻게 변하나요?

14. 준비 큐에 있는 스레드 우선순위가 변할 수 있나요?

5. 고급 스케줄러(Optional, `mlfqs` 모드)

2. `thread_create()` 동작 흐름

원래 `timer_sleep()` 동작 방식

3. `warning: no previous prototype for func` 경고는?

7. `pass()` 테스트 실패 시 백트레이스 혼동?

8. `schedule()` 후 인터럽트 재활성화 시점은?

12. 최고 우선순위 스레드가 `yield()`하면?

17. `thread_set_priority()`와 기부 상호작용은?